Scores and probabilities
A binary classifier may report more than a hard label. For a feature vector , let and define
This is a model of conditional probabilities, not a guarantee that its numbers are calibrated on new data. A threshold at predicts when and when ; at a tie rule must be chosen. Different decision costs can justify a different threshold.
From likelihood to a loss
For observed labels and features , the probability assigned to the observed label is , where . Indeed . If the labels are conditionally independent given the features under the model, the negative log-likelihood per example is
Without that independence assumption the same expression can still be chosen as a loss, but this product-likelihood interpretation has not been justified. A large positive signed score gives small loss; a large negative one gives large loss. The sign of the score controls a hard prediction, while its magnitude affects the loss.
Definition 6.1.1
(Signed score and strict separability)
For a parameter and an example with , the signed score is . The training set is strictly linearly separable if some gives for every .
Proposition 6.1.2
(Convexity and gradient of the logistic loss)
The loss is convex and differentiable, and with ,
Proof
(A convex scalar loss composed with affine scores)
For the scalar function we have and , so is convex. Each signed score is an affine function of , and a convex function of an affine function is convex; an average of convex functions is convex. By the chain rule, and , with . Averaging over gives the displayed gradient.
Convexity alone does not guarantee a finite minimizer or strict convexity in every parameter: an unused feature, for example, can leave a whole direction unchanged.
A separable two-point example
Worked example 6.1.3
(Two points with a zero intercept)
Take one-dimensional features and fix the intercept to zero. With data and , both signed scores equal , so the mean loss becomes
For every finite , the loss is positive, but as . Numerically , and . Thus the infimum is zero and no finite attains it. Both examples are classified correctly for every , yet the probability loss continues to reward increasing the margin. This demonstrates a failure of attainment for this dataset; it is not a claim that every convex loss has this behavior.
The same mechanism works for every strictly separable training set.
Theorem 6.1.4
(Separable data have no logistic minimizer)
If the training set is strictly linearly separable, then for every but . Hence has no minimizer and no stationary point.
Proof
(Scaling a separator)
Every term is positive, so everywhere. Let separate the data, with signed scores , and let , which is positive because the set is finite. For the parameter has signed scores , so
Thus , and since the infimum is never attained. A stationary point of a differentiable convex function is a global minimizer, so there is none.
Proof X-ray
Where strictness and scaling enter
Two ingredients carry the proof. Strictness, , lets one scale factor enlarge all margins at once; with a zero margin that example's loss would stay at along the ray. Positivity of every term shows the infimum is never reached. Convexity is not used to show non-attainment; it is used only to rule out stationary points. A closed bounded region cannot capture the minimizing sequence: on a fixed interval the continuous loss does attain a minimum, but enlarging the interval pushes that minimum further out. The conclusion fails once some margin cannot be made positive, as the next example shows.
Common mistake
(Expecting the gradient to vanish on separable data)
For the two-point example for every , so the equation has no solution. Solving the gradient equation, or running gradient descent until the gradient is small, then returns a weight set by the stopping rule: the gradient size falls below only once exceeds about , and a smaller tolerance gives a larger weight. The weight returned is an artifact of the stopping rule, not an estimate of a minimizer that exists.
Worked example 6.1.5
(Conflicting labels at one point)
Take two examples with the same feature and opposite labels , , with the intercept fixed at zero. No separator exists: the signed scores are and , which are never both positive. The loss is
Because is strictly increasing, has the sign of , so decreases before and increases after it. Moreover . The unique minimizer is , with and both probabilities equal to , an honest answer for contradictory labels. A finite minimizer exists here exactly because the data are not separable.
What a penalty changes
Worked example 6.1.6
(A quadratic penalty restores a minimizer)
For the zero-intercept example with data and , add a quadratic penalty with :
Now . The derivative is continuous and strictly increasing, has value at zero, and tends to as . The intermediate value theorem gives exactly one positive zero of . Strict monotonicity of shows decreases before and increases after it, so this is the unique global minimizer. It is characterized by
For the equation gives , and compared with . If stayed bounded as , the left side would tend to while the right side stays positive, so : the penalized solution approaches the behavior of the unpenalized loss.
A penalty also does not by itself establish out-of-sample accuracy. Which parameters the penalty touches matters.
Counterexample mode
Penalizing only the weights need not give a minimizer
Claim: adding a quadratic penalty on the weights always gives a penalized logistic loss with a finite minimizer. Take one feature and two examples , , both with label . The signed scores are and , so
At we get as . Hence is not attained, and no finite is a minimizer. The penalty controls , but the unpenalized intercept alone can make every signed score large. Penalizing the intercept as well, with , makes the objective strongly convex and restores a unique minimizer.
Exercises with solutions
Quick check
(What probabilities does the model assign at ?)
Evaluate .
Solution · Answer
Both are . A hard prediction there requires the stated tie rule.
Quick check
(In the two-point example, what are and ?)
Substitute into the formulas.
Solution · Answer
and .
Quick check
(Why is the penalized example's minimizer positive?)
Look at the sign of and the monotonicity of .
Solution · Answer
is strictly increasing, , and its unique zero lies to the right of zero.
Quick check
(Does a convex differentiable loss necessarily have a finite minimizer?)
Recall the unpenalized two-point loss.
Solution · Answer
No. The unpenalized two-point loss is convex but approaches its infimum only as .