Logistic Regression

The log-likelihood, its convexity, the Hessian as a weighted Gram matrix, and what happens when the data is separable.

Classical MLCore⏱ 1 hour6 min readlogistic regressionmaximum likelihoodconvexityirlsseparability

AssumesLinear, Ridge and Lasso Regression · Convex Sets, Convex Functions, Smoothness and Strong Convexity

Model and likelihood

With $y\in\{0,1\}$ and $\sigma(t) = (1+e^{-t})^{-1}$ , the model is

\P(y=1\mid x) = \sigma\big(\ip{w}{x}\big) =: p_w(x).

PropositionNegative log-likelihood and its derivatives

The negative log-likelihood of an i.i.d. sample is

\mathcal{L}(w) = -\sum_{i=1}^n\Big[y_i\log p_w(x_i) + (1-y_i)\log\big(1-p_w(x_i)\big)\Big] = \sum_{i=1}^n\Big[\log\big(1+e^{\ip{w}{x_i}}\big) - y_i\ip{w}{x_i}\Big],

with

\nabla\mathcal{L}(w) = X^\top(p - y), \qquad \nabla^2\mathcal{L}(w) = X^\top S X, \quad S = \diag\big(p_i(1-p_i)\big),

where $p_i = p_w(x_i)$ .

TheoremConvexity

$\mathcal{L}$ is convex. It is strictly convex if and only if $\rank X = p$ and no $p_i\in\{0,1\}$ ; under those conditions the Hessian is positive definite.

Algorithm — IRLS / Newton's method for logistic regression

Initialise $w_0 = 0$ , so $p_i = 1/2$ and $S = \tfrac14 I$ .
Repeat: compute $p_i = \sigma(\ip{w_t}{x_i})$ and $S = \diag(p_i(1-p_i))$ .
Solve the weighted least-squares system $(X^\top SX)\,\delta = X^\top(y-p)$ .
Update $w_{t+1} = w_t + \delta$ (optionally with a line search for robustness).
Until $\norm{X^\top(y-p)}_\infty$ is below tolerance.

Because $\nabla^2\mathcal{L}$ is a weighted Gram matrix, each Newton step is a weighted least-squares solve — hence the name iteratively reweighted least squares. By the local quadratic convergence theorem, this converges in a handful of iterations when a maximiser exists.

Separability

PropositionThe MLE does not exist under separability

Suppose there is $w_0$ with $\ip{w_0}{x_i}>0$ whenever $y_i=1$ and $\ip{w_0}{x_i}<0$ whenever $y_i=0$ . Then $\mathcal{L}(cw_0)\to0$ strictly decreasing as $c\to\infty$ , so $\inf_w\mathcal{L}(w)=0$ is not attained and $\norm{w}_2\to\infty$ along any minimising sequence.

Key idea

Unregularised logistic regression on separable data diverges. The standard fixes are ridge regularisation, which makes the objective coercive and restores a unique minimiser, or early stopping. But the direction of divergence is not arbitrary: Soudry et al. prove that $w_t/\norm{w_t}_2$ converges to the maximum-margin direction — the hard-margin SVM solution. So gradient descent on the logistic loss implicitly performs margin maximisation. This is the cleanest rigorous instance of the implicit bias phenomenon discussed on the deep learning theory page, and it is worth knowing that the result is a genuine theorem in this setting, unlike its deep-network analogues.

PropositionThe score equations enforce calibration

At any stationary point, $X^\top p = X^\top y$ . In particular, if the design includes an intercept column of ones, $\sum_ip_i = \sum_iy_i$ : the predicted number of positives equals the observed number.

This is a real but limited form of calibration: it holds in-sample and only along the $p$ feature directions. It says nothing about out-of-sample calibration, and nothing about calibration within subgroups not expressible as feature directions — which is why post-hoc calibration methods (temperature scaling, isotonic regression) exist.

Problems

Convexity of the logistic lossProof · Beginner · 15 min Logistic regression diverges on separable dataProof · Intermediate · 30 min IRLS is a weighted least-squares solveProof · Intermediate · 30 min In-sample calibration of logistic regressionProof · Intermediate · 30 min

References

BookTrevor Hastie, Robert Tibshirani and Jerome Friedman (2009). The Elements of Statistical Learning
BookPeter McCullagh and John A. Nelder (1989). Generalized Linear Models
PaperDaniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar and Nathan Srebro (2018). The Implicit Bias of Gradient Descent on Separable Data

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionThe logistic negative log-likelihood and its derivativesproof includedGradient equals the design matrix times the residual; Hessian is a variance-weighted Gram matrix.
TheoremThe logistic loss is convex, and strictly convex iff the design has full rankproof includedConvexity follows from the PSD Hessian; strictness requires full column rank and non-degenerate probabilities.
PropositionThe maximum likelihood estimate does not exist under separabilityproof includedIf the classes are linearly separable the likelihood has no maximiser and the norm of the iterates diverges.
PropositionThe score equations enforce calibration on the feature directionsproof includedAt the optimum the predicted probabilities match the observed labels in every feature direction.

Problems (4)

All problems