A Worked Step-Halving Rescue for Logistic Regression

Why a Newton step may need rescuing

Newton’s method uses local curvature to propose a parameter update. In logistic regression, this can be an efficient way to move toward a likelihood maximum, but the calculation is local: a step that looks appropriate near the current estimate may travel too far for the likelihood to keep increasing. Step-halving addresses this by keeping the proposed direction and testing progressively shorter moves.

The focus here is a concrete rescue. We will calculate a logistic-regression Newton direction, evaluate the likelihood after the full step, and halve the step size until the update meets a stated acceptance rule. The central distinction is between choosing a direction and choosing how far to travel along it.

Logistic likelihood and the step-halving rule

For independent Bernoulli responses \(Y_i\in\{0,1\}\) with fixed predictor vectors \(x_i\), logistic regression specifies \(P(Y_i=1)=p_i\), where \(p_i=\exp(\eta_i)/(1+\exp(\eta_i))\) and \(\eta_i=x_i^\mathsf{T}\beta\). The log-likelihood, score, and observed information are

where \(X\) has rows \(x_i^\mathsf{T}\), \(p\) has entries \(p_i\), and \(W\) is diagonal with entries \(p_i(1-p_i)\). If \(I(\beta)\) is invertible, the Newton ascent direction is \(d=I(\beta)^{-1}U(\beta)\). The full Newton proposal is \(\beta+d\); a damped proposal is \(\beta+\alpha d\), with \(0<\alpha\leq 1\).

This acceptance rule asks only that the likelihood not decrease. It does not require a particular size of improvement. More stringent sufficient-increase rules are also used, but the examples here use nondecrease so that each decision can be checked directly.

Worked rescue in a balanced logistic model

The calculations show why the word “Newton” does not by itself guarantee likelihood improvement. The direction is computed from the local score and curvature at \(\eta=3\). The full move is so long that it lands on the other side of the maximum, far enough away to have a worse likelihood. Halving changes the distance traveled without changing that proposed direction.

A longer halving sequence

The accepted eighth-step is still only an update, not a declaration of convergence. Its role is to make progress while retaining the Newton direction. The score and curvature at the updated parameter may then imply a quite different direction and a different useful step size.

Why a sufficiently short ascent step can work

Step-halving is especially useful when the proposed direction is an ascent direction. The following result explains why, under a local smoothness condition, repeatedly halving such a direction will eventually find a likelihood-increasing trial.

Proof. Differentiability at \(\beta\) gives, as \(\alpha\) tends to zero,

Write \(c=\nabla\ell(\beta)^\mathsf{T}d>0\). By the limit, for all sufficiently small positive \(\alpha\), \(|r(\alpha)|/\alpha<c/2\). For these values, \(\ell(\beta+\alpha d)-\ell(\beta)>\alpha c-\alpha c/2=\alpha c/2>0\). The sequence \(2^{-k}\) tends to zero, so some tested step is sufficiently small. This proves the claim. \(\square\)

For a Newton direction \(d=I(\beta)^{-1}U(\beta)\), if the observed information \(I(\beta)\) is positive definite and \(U(\beta)\ne0\), then

The strict inequality follows because the inverse of a positive-definite matrix is positive definite. Thus the Newton direction is an ascent direction under these conditions, and the theorem applies. If the information is singular or the direction is not an ascent direction, this argument does not establish that halving will find an improving step.

What the acceptance rule does—and does not—establish

If each accepted update satisfies \(\ell(\beta_{\mathrm{new}})\geq\ell(\beta_{\mathrm{old}})\), then the sequence of accepted likelihood values is nondecreasing. This follows directly at every iteration from the acceptance test; applying the inequality successively gives \(\ell(\beta_k)\geq\ell(\beta_0)\) for each accepted iteration \(k\). The parameters themselves need not move monotonically in any coordinate, and this fact alone does not prove that they converge to a finite estimate or to a maximizer.

The logistic log-likelihood is concave in the coefficients, but concavity does not mean that every full Newton step increases it. Concavity describes the shape of the objective; it does not prevent a locally computed update from overshooting. The balanced example makes this concrete: the log-likelihood is concave, yet the full step from \(3\) lowers its value.

A common mistake is to calculate a Newton direction and accept it automatically because it is called an ascent direction. The direction may indeed have a positive directional derivative, while the full finite move decreases the likelihood. The correction is to distinguish the local derivative from the actual likelihood difference: calculate \(\ell(\beta+\alpha d)\), compare it with \(\ell(\beta)\), and shorten the step when the chosen acceptance rule fails.

In practical computation, keep track of the current likelihood, the proposed direction, each tested step size, and each trial likelihood. Accept the first trial that meets the stated rule, then recompute at the accepted point. This makes the rescue reproducible and prevents a rejected trial from silently becoming the new iterate.