Motivation
A convex classification loss is useful because it can be optimized, but optimization alone does not explain why its minimizer should classify well. Hinge loss asks for a signed margin. Logistic loss asks for a probability estimate. The quantity eventually reported as a classification error is different from either objective. We need a theorem that connects these quantities without confusing them.
The right comparison starts with the best prediction permitted by the data distribution itself. At an input where the positive label occurs with probability , even the best deterministic classifier makes an error with probability . We should charge a learning rule for its error above this unavoidable amount. Such an excess risk distinguishes label noise from a poor decision.
We will first solve the prediction problem separately at each input, then integrate the resulting inequalities. This gives complete hinge and logistic risk comparisons. Finally, we will reconnect them to empirical risk minimization. That last step matters: a loss can have the correct unrestricted optimum while a small or poorly chosen model class prevents us from approaching it.
Definitions
Let have a fixed probability distribution, with . Assume a measurable version of the conditional probability is available. Every statement involving is understood up to a set of inputs of probability zero. This assumption holds, for example, for finite input spaces and for the usual real-vector input models. A classifier is a measurable function taking values in ; its risk is .
Definition 15.1.1
(Scores, the tie rule, and conditional risk)
A score is a finite real-valued measurable function. Its classifier is when and otherwise. Thus a zero score predicts positive. For a nonnegative margin loss , define
Here is a conditional risk at a fixed input, while averages over inputs as well as labels. For the scores compared below, assume . Write , where the infimum is over all finite measurable scores, and .
Our two losses are and . All logarithms are natural. A risk infimum need not be attained by a finite score. We will prove the relevant infimum identities rather than silently exchange an infimum and an expectation.
The comparison point for every classifier is the rule that decides by the more probable label.
Definition 15.1.2
(Bayes rule and excess classification risk)
The Bayes rule is if , and otherwise. At , either decision is optimal; choosing positive fixes one representative. Define and .
Theorem/proposition
Theorem 15.1.3
(Bayes risk and the cost of a wrong decision)
The Bayes rule attains the minimum classification risk, and
In particular, disagreeing with a Bayes decision has little cost near , and a larger cost when one label is much more probable.
Theorem 15.1.4
(Calibration for hinge and logistic losses)
For every score with finite corresponding surrogate risk,
The unrestricted surrogate infima are
where and . Thus convergence to the unrestricted surrogate infimum implies convergence to Bayes classification risk. The comparisons concern excess risks; the raw logistic risk is not a classification error probability.
The word calibration here describes this implication from small surrogate excess to small classification excess. The displayed inequalities quantify the implication for these two losses. They do not assert the same constants, or even the same implication, for an arbitrary loss.
Counterexample mode
A convex loss that is not calibrated
Claim: every convex margin loss is calibrated. Take the convex nonnegative loss and one input with . Then , so and the zero score has surrogate excess zero. By the tie rule it predicts positive, with classification risk against the Bayes risk : classification excess . Indeed minimizes for every , so this loss ignores the label probabilities. The repair is a standard result, not proved here: a convex margin loss is calibrated exactly when it is differentiable at with , as the hinge, logistic and squared losses are.
Proof sketch or proof idea
We give full conditional arguments.
Proof
(Pointwise comparison of the two decisions)
At an input with conditional positive probability , the error of predicting positive is , and that of predicting negative is . Their smaller value is . Choosing the other decision increases the error by . This also gives zero when , independently of the selected tie representative. Taking expectations proves the first theorem.
Proof
(Hinge calibration from the piecewise conditional risk)
For the hinge loss, the complete conditional graph is piecewise affine:
The minimum is . A score is a minimizer for , and is a minimizer for . The measurable score therefore attains the expected conditional minimum, proving the hinge infimum identity.
Suppose a score makes the wrong Bayes decision. If , this means ; the piecewise formula gives . If , it means , and the same bound holds. Consequently its conditional surrogate excess is at least . A correct decision has zero conditional classification excess and a nonnegative surrogate excess. The same is true at . Integration gives , including the stated zero-score convention.
Proof
(Logistic calibration through relative entropy)
For logistic loss, let , so . Rewriting the two logarithms gives
where is the binary relative entropy. For fixed , consider it as a function of . At its value and first derivative are zero, while
Integrating this second-derivative inequality on the interval between and gives . Continuity in extends the result to and . In particular, relative entropy is nonnegative. Its minimum zero is attained at when , corresponding to .
At the conditional loss decreases to zero as , and at it decreases to zero as . There is no finite minimizer in either case. To justify the global infimum, truncate the log odds to , assigning the endpoints and at and . These are finite measurable scores. Their conditional risks decrease pointwise to as and lie between and : the truncation moves from zero toward a conditional minimizer. Dominated convergence, with bound , gives risks tending to . Every score has risk at least this amount by nonnegativity of . This proves the logistic infimum identity and .
If a score makes the wrong decision, and lie on opposite sides of , allowing equality at the boundary on the side fixed by the tie rule. Thus . Its conditional classification excess satisfies
The first inequality also holds for a correct decision, since its left side is zero. Taking expectations and applying Cauchy–Schwarz to and the constant random variable one proves the logistic comparison.
Proof X-ray
How the logistic argument closes
The logistic proof rests on one identity and two inequalities. The identity splits conditional risk into an unavoidable part and a divergence, so the excess is an expected divergence once the infimum identity is known. That identity is the delicate step: at no finite score is optimal, so the proof cannot evaluate the risk at a minimizer. Truncated log odds give finite scores whose conditional risks decrease as grows, because the convex function falls as moves from toward its minimizer, and are bounded by . Dominated convergence then passes to the limit.
The non-obvious move is the curvature bound , which converts relative entropy into a squared distance between probabilities, . The tie rule enters only in the wrong-decision step: for a zero score gives and predicts positive, and holds with equality. The argument closes with Cauchy–Schwarz, equivalently Jensen for the concave square root. That is why the logistic bound carries a square root, while the hinge bound, read off a piecewise-affine conditional risk with no curvature step, is linear.
Worked examples
Worked example 15.1.5
(The Bayes error is not zero, and ties matter)
Let take values with probabilities , and let , . The Bayes decisions are positive at and negative at , giving risk . Take scores , . Both decisions are wrong relative to Bayes, including the positive decision at the zero score. Their risk is , so the excess is . The Bayes identity gives the same number: .
The conditional hinge risks are and . Thus , whereas . The surrogate excess is , which is above as the theorem requires. Comparing the classification excess with the raw hinge risk would lose the distinction between unavoidable noise and the cost of the chosen scores.
Worked example 15.1.6
(A probability estimate and a decision convey different information)
At a single input, let . The score with is negative and has classification excess . Its logistic excess is
The bound gives , which is valid but not exact. A positive score would instead have zero classification excess, while its logistic excess would usually remain positive: the sign can be correct before the probability estimate is accurate.
Worked example 15.1.7
(Deterministic labels: hinge attains its infimum, logistic does not)
Take a single input with . The hinge conditional risk is , which is zero for every , so the infimum is attained by a finite score. The logistic conditional risk is for every finite and tends to only as ; at it equals . Every positive score has classification excess zero, while the logistic bound for gives only .
For the negative score , the classification excess is . The hinge excess is , and the logistic excess is , with . Both comparisons hold at this boundary value of , where the truncation step of the proof is needed.
Counterexample mode
Calibration is measured against the unrestricted optimum
Consider one input with , and restrict the score family to the two constants and . Score has classification risk and hinge risk . Score has classification risk and hinge risk . Therefore the hinge minimizer inside this family has the worse classification risk. There is no contradiction: the unrestricted hinge optimum is , attained at score , which the family omits. For the selected score , the classification excess is and the unrestricted hinge excess is , consistent with calibration. Its hinge excess relative to the two-element family's minimum is zero; substituting that zero into the theorem would be incorrect.
Common mistakes
Finite empirical error does not identify , and small training surrogate risk does not by itself bound population surrogate excess. To use calibration after learning, let be a nonempty score class and define its approximation error
Assume all population risks in the comparison are finite. On an event where , suppose the learned score has empirical risk at most , with . For any competitor in the class,
Taking an infimum over competitors does not require attainment. Subtracting proves . Hinge classification excess is bounded by this sum; logistic classification excess is bounded by the square root of twice this sum. The three terms record different obstacles: a class that misses suitable scores, finite-sample estimation, and unfinished optimization. If all three tend to zero, with the estimation event having probability tending to one, the resulting classification risks converge to Bayes risk in probability. Neither increasing the number of parameters alone nor solving one fixed optimization problem establishes all three conditions.
Common mistake
(Applying bounded-loss concentration to unrestricted scores)
Logistic and hinge losses are unbounded over arbitrary scores. For an i.i.d. sample, a fixed data-independent finite class of size , and scores satisfying almost surely for every class member, their losses lie in , with for hinge and for logistic. Hoeffding and a union bound then give with probability at least . Applying a bounded-loss bound to unrestricted scores drops a necessary hypothesis. A class selected from the same training sample needs separate control; conditioning on its selection does not restore the fixed-class argument automatically.
Common mistake
(Reading raw logistic risk as an error probability)
At an input with , every score has logistic conditional risk , yet every classifier there errs with probability exactly and is Bayes optimal. The raw risk exceeds every possible error rate. Only the excess is compared with .
Quick check
Quick check
(At an input where , does a negative score disagree with the selected Bayes rule, and does that disagreement contribute to classification excess?)
Solution · Answer
It disagrees: the selected Bayes rule predicts positive at . It contributes nothing to classification excess, because its weight is zero. Logistic risk can nevertheless penalize a confidently negative score, because then differs from the true probability .
Exercises
Quick check
(At a single input with , calculate the classification risk and hinge excess risk for scores . For score zero, also calculate the logistic excess risk and verify the logistic comparison. Keep the positive tie convention.)
Solution · Answer
The Bayes rule is negative and its risk is . Scores respectively have classification risks , hence excesses . Their hinge risks are , while the unrestricted hinge optimum is . The hinge excesses are therefore , each at least the corresponding classification excess. At score zero, and logistic excess is . Thus . The score-zero equality in the hinge comparison also illustrates why the tie convention must be fixed.
Exercise 15.1.8
(For squared margin loss , put . Prove and , and show that no universal finite constant gives for all distributions and scores.)
CoreProof
Solution(4)
- 1
Complete the square in
Expanding gives . The finite measurable score attains the conditional and population infima, so .
- 2
Bound the classification excess on a wrong decision
Key step
If the decision is wrong and , then , which is exactly the conditional classification excess on that event. A correct decision, or , has excess zero. Hence everywhere.
Because: A wrong decision puts on the other side of zero from , the tie included.
- 3
Integrate and apply Cauchy–Schwarz
.
- 4
Rule out a linear comparison
∎Use one input with , , and score zero. Classification excess is , but squared-loss excess is . Their ratio is , unbounded as tends to zero.
Quick check
(A fixed finite score class has size , all scores satisfy , and i.i.d. training observations are used. Its population hinge approximation error is at most and the returned score has empirical optimization error at most . Give a classification-excess bound holding with probability at least , and state which given quantity could not be inferred from counting the class members.)
Solution · Answer
The hinge loss is bounded by , and gives . Hence classification excess is at most with the requested probability. The approximation error describes how the population distribution and available score functions fit together; the number alone cannot establish it. The optimization error is also a separate property of the returned solution, not a consequence of the class size.
Exercise 15.1.9
(Let the input space contain exactly points, with an arbitrary distribution, and let contain all score functions taking only values . Prove that hinge empirical minimization over is classification empirical minimization, and obtain a Bayes-excess classification guarantee for an exact empirical minimizer that keeps the factor gained from this score choice.)
SynthesisProof
Solution(4)
- 1
Compute hinge loss on -valued scores
For such scores, hinge loss is zero for a correct prediction and two for an incorrect prediction. Both empirical and population hinge risks equal twice their classification counterparts, so the two empirical minimizations select the same scores.
- 2
Identify the approximation error
The class contains the Bayes rule as a score on all input points. Its hinge risk is , so the hinge approximation error is zero and for every class member.
- 3
Apply the finite-class bound
Key step
With , with probability at least , exact empirical minimization gives with .
Because: The class is fixed, has members, and its hinge losses lie in .
- 4
Translate back to classification excess
∎From , . The general calibration inequality would lose a factor of two. The bound may be replaced by its minimum with one, since an excess classification risk never exceeds one.