A loss for binary labels
A score can rank two classes, but a training objective must also specify how errors and confidence are penalized. Logistic loss is smooth and convex; neither property alone ensures that an unregularized minimum exists.
Fix observations and labels . A constant coordinate may be included in for an intercept. The objective studied on this page is the following.
Definition 8.1.1
(Regularized logistic objective)
For let be the margin of example , and define
The first sum is the empirical logistic loss and is the penalty weight. A minimizer is a point with for every .
We penalize every coordinate, including an intercept if present. This is an empirical objective for fixed data; convexity is not a guarantee of population calibration or generalization.
Writing , a model may assign to label and to label . The first term is then the average negative log probability assigned to the observed label. That probabilistic interpretation is a model choice, not proof that its probabilities equal real frequencies.
Common mistake
(Using labels in the formula)
The margin presupposes . If labels are stored as and and substituted unchanged, every example with contributes the constant , whatever is, so that class is ignored by the gradient. Recode with , or use the equivalent 0/1 form .
Gradient, curvature and a step-size bound
Theorem 8.1.2
(Convexity and smoothness)
Let . Then
The objective is convex for . Its gradient is Lipschitz with the valid bound
When , the minimizer exists and is unique.
Proof
(Differentiate, bound the curvature, then use coercivity)
Differentiating gives and second derivative . By the chain rule with , and since , the gradient and Hessian have the displayed forms. Each outer product is positive semidefinite and each weight is nonnegative, so the Hessian is positive semidefinite and is convex.
Also . For any vector , Cauchy–Schwarz gives , hence
A positive semidefinite matrix whose quadratic form is at most has operator norm at most . Writing therefore gives .
If , the logistic terms are nonnegative, so . The sublevel set is then closed and bounded, and the continuous function attains its minimum on it; that point is a global minimizer. The Hessian is at least , so is strictly convex and the minimizer is unique. This coercivity argument uses the penalty on every coordinate.
Proof X-ray
Which bound does which job
The label convention enters exactly once, through , which removes the labels from the Hessian: curvature depends on the features only. The bound , with equality at , together with Cauchy–Schwarz produces the upper curvature constant , which is what a step-size rule needs. Convexity itself uses only the sign of the weights.
Existence is the step that needs a hypothesis. The key move is to discard the loss and keep only . This lower bound grows in every direction, so the search is confined to a bounded sublevel set, where continuity finishes the argument. With the lower bound is and confines nothing; the counterexample below shows that the minimum can then fail to exist. The same lower curvature supplies uniqueness, so one hypothesis closes both halves.
The curvature constant also controls a single gradient step.
Lemma 8.1.3
(One-step decrease of gradient descent)
Let be the constant of the theorem, , and with . Then
In particular, gives .
Proof
(Integrate the gradient along the step)
Put . By the fundamental theorem of calculus along the segment from to ,
The Lipschitz bound gives , and . Hence , which is the claim. If , then .
This is a one-step exact-arithmetic guarantee for the stated objective and bound; it does not certify an implementation or a chosen stopping tolerance. If , all features and are zero, and the objective is constant.
A finite optimum and a missing one
Worked example 8.1.4
(Conflicting labels at the same feature)
Take , , , , and . Then
Its derivative is , using . It vanishes only at and changes sign there, so the unique minimum is , with value . The data cannot be strictly separated by this score. Here is a valid curvature bound.
Worked example 8.1.5
(One gradient step with a penalty)
Take one observation , and , so and . The theorem gives ; take .
From : , so . The lemma guarantees a decrease of at least . Directly,
a decrease of about , just above the guaranteed . The minimizer solves ; since , one step has already brought to within about of it ().
Worked example 8.1.6
(Separable data: the penalized minimizer escapes as the penalty vanishes)
Take and . Both margins equal , so . For there is no minimizer (see the counterexample below).
For the unique minimizer solves . Since and is increasing, ; since , . If stayed below some along a sequence , then , a contradiction. Hence as . This is the edge case of the theorem: the minimizer exists for every positive , but its size is controlled only by the penalty.
Counterexample mode
Convex does not mean the minimum is attained
With one observation and , the loss is positive for every finite and tends to zero as . Its infimum is zero but it has no finite minimizer. More generally, if a vector has for every training example, then as while every finite loss is positive. Adding with all coordinates penalized restores a unique finite minimizer, but changes the objective.
For numerical work, evaluate with a stable softplus implementation rather than directly forming a potentially overflowing exponential. Data scaling affects the curvature bound and practical step sizes. The finite-data proof does not establish that a classifier is accurate, calibrated, fair or robust on new data.
Common mistake
(Leaving the intercept unpenalized and still claiming existence)
If and the penalty is applied only to the slope, the lower bound is lost. For example, if every label is , then at slope and intercept the objective is as and is positive for every finite , so no minimizer exists although . Existence must then be argued separately for the unpenalized directions.
Exercises
Quick check
(With , , , compute and explain why no finite minimum exists.)
Look at the sign of the derivative.
Solution · Answer
for every finite , so is strictly decreasing. A minimizer would need ; instead the loss tends to zero as but never reaches it.
Quick check
(In the conflicting-label example, find the minimizer and its loss.)
Solution · Answer
The derivative vanishes only at , so the minimizer is and .
Quick check
(If for every and , give a valid and a step-size range from the lemma.)
Solution · Answer
, so is a valid bound (a larger constant is still a Lipschitz constant). Then gives the guaranteed decrease .
Quick check
(Why is penalizing every coordinate relevant to the existence proof?)
Solution · Answer
The proof bounds the objective below by , which forces it to infinity in every direction and confines the search to a bounded set. If some direction is unpenalized, that bound says nothing along it, and an unpenalized intercept with all labels equal already has no minimizer.
Further reading
Stanford statistics notes on logistic regression discuss the likelihood, derivatives and convexity.