Step-Halving With Likelihood-Based Acceptance

Why Reduce a GLM Update?

A Newton or Fisher-scoring update is computed from the score and a curvature matrix at the current coefficient vector. The update uses this local information to propose a new vector, but a full update can be too large for the likelihood to increase. Step-halving provides a simple safeguard: evaluate the actual log-likelihood at the proposed point, and, if it has decreased, repeatedly shorten the step until the acceptance rule is met.

The safeguard changes the distance traveled in the proposed direction; it does not change that direction. Its guarantee is correspondingly limited: when a suitable ascent direction is supplied and the log-likelihood is smooth near the current point, sufficiently small positive steps improve the likelihood. Step-halving tests a sequence of such steps rather than assuming the full update is safe.

Definition: Let $\beta$ be the current coefficient vector, $\ell(\beta)$ the GLM log-likelihood, and $d$ a proposed update direction. Step-halving tests the trial vectors $$ \beta_j=\beta+2^{-j}d,\qquad j=0,1,2,\ldots. $$ It accepts the first trial vector for which $\ell(\beta_j)\geq \ell(\beta)$. Thus the step fractions are $1,\frac12,\frac14,\frac18,\ldots$, and acceptance requires a nondecreasing value of the actual log-likelihood.

For a differentiable log-likelihood, write $U(\beta)=\nabla\ell(\beta)$ for the score and $H(\beta)=\nabla^2\ell(\beta)$ for the Hessian. A Newton direction $d$ solves $H(\beta)d=-U(\beta)$. A Fisher-scoring direction solves $I(\beta)d=U(\beta)$, where $I(\beta)$ is the expected information. Step-halving can be applied to either direction. The likelihood used for acceptance is $\ell$, not the quadratic approximation used to construct the direction.

How the Acceptance Test Works

At each iteration, a practical implementation first computes $d$, then evaluates the likelihood at $\beta+d$. If this is less than the current value, it tries $\beta+d/2$, then $\beta+d/4$, and so on. The first trial satisfying the specified inequality is accepted as the next coefficient vector. In applications with a restricted parameter domain, a trial outside that domain must also be rejected; the local guarantee below assumes the current point has a neighborhood in which the likelihood is defined.

Compute a direction.
Use the Newton or Fisher-scoring equations at the current coefficient vector to obtain $d$.

Test the full step.
Evaluate $\ell(\beta+d)$. Accept if it is at least $\ell(\beta)$; otherwise continue.

Halve the step.
Test $\ell(\beta+2^{-j}d)$ for successively larger $j$, stopping at the first acceptable trial.

Worked Example: A Full Logistic Update Is Accepted

Suppose four independent Bernoulli observations are modeled with an intercept $\beta$ and the logit link. There are three successes and one failure. Up to a constant that does not depend on $\beta$, the log-likelihood is $$ \ell(\beta)=3\beta-4\log(1+\exp(\beta)). $$ Start at $\beta=0$. The fitted success probability is $p=1/2$, so the score and observed information are $$ U(0)=3-4p=1,\qquad -H(0)=4p(1-p)=1. $$ The Newton equation gives $d=U(0)/[-H(0)]=1$. At the current point, $$ \ell(0)=-4\log 2\approx -2.7726. $$ The full trial is $\beta_0=0+1=1$, and its likelihood is $$ \ell(1)=3-4\log(1+\exp(1))\approx -2.2530. $$ Since $-2.2530>-2.7726$, the full step is accepted. No halving is needed. This example also illustrates why the exact expression should be evaluated before rounding: the stated four-decimal value is approximately $-2.2530$.

Worked Example: A Poisson Scoring Step

Let $Y$ have a Poisson distribution with mean $\mu=\exp(\beta)$, and suppose the observed count is $y=2$. Omitting the constant $-\log(2!)$, the log-likelihood is $$ \ell(\beta)=2\beta-\exp(\beta). $$ At $\beta=0$, the score is $U(0)=2-\exp(0)=1$, and the expected information is $I(0)=\exp(0)=1$. Thus the Fisher-scoring equation $I(0)d=U(0)$ gives $d=1$.

The current log-likelihood is $\ell(0)=-1$. The full trial is $\beta=1$, with $$ \ell(1)=2-\exp(1)\approx -0.7183. $$ Because $-0.7183>-1$, the likelihood-based test accepts the full scoring step. The constant omitted from the likelihood would be added to both values and would not affect their comparison.

Why Halving Eventually Finds an Improvement

The key condition is that the proposed direction is locally ascending at the current point. Specifically, if the directional derivative $U(\beta)^{\mathsf T}d$ is positive, then sufficiently small positive multiples of $d$ increase $\ell$. Since the step fractions $2^{-j}$ tend to zero, one of the tested fractions must eventually be small enough.

Theorem: Suppose $\ell$ is differentiable on an open neighborhood of $\beta$, and $d$ is a fixed direction satisfying $U(\beta)^{\mathsf T}d>0$. Then there is a finite integer $j\geq 0$ such that $$ \ell(\beta+2^{-j}d)>\ell(\beta). $$ Consequently, exact step-halving with the nondecreasing-likelihood acceptance rule accepts after finitely many halvings.

Proof. Define $g(t)=\ell(\beta+td)$ for $t$ in a neighborhood of zero. Differentiability of $\ell$ implies differentiability of $g$ at zero, with $$ g'(0)=U(\beta)^{\mathsf T}d>0. $$ By the definition of the derivative, $$ \lim_{t\downarrow 0}\frac{g(t)-g(0)}{t}=g'(0). $$ Let $c=g'(0)$, which is positive. There is an $\varepsilon>0$ such that for every $t$ with $0<t<\varepsilon$, $$ \frac{g(t)-g(0)}{t}>\frac{c}{2}>0. $$ Multiplying by $t>0$ gives $g(t)>g(0)$. The sequence $2^{-j}$ tends to zero, so some finite $j$ has $0<2^{-j}<\varepsilon$. For that $j$, $\ell(\beta+2^{-j}d)>\ell(\beta)$, and the acceptance test succeeds no later than that trial. $\square$

This argument gives a local existence guarantee, not a bound on how many halvings will be needed. It also relies on a positive directional derivative. If that derivative is zero or negative, the proof does not apply, and repeated halving need not find an improving step.

Result: If $I(\beta)$ is symmetric positive definite and $U(\beta)\ne 0$, the Fisher-scoring direction $d=I(\beta)^{-1}U(\beta)$ has positive directional derivative: $$ U(\beta)^{\mathsf T}d =U(\beta)^{\mathsf T}I(\beta)^{-1}U(\beta)>0. $$ The inequality follows because the inverse of a symmetric positive-definite matrix is also positive definite. Therefore, when the log-likelihood is differentiable on an open neighborhood of $\beta$, the theorem guarantees that sufficiently repeated halving of this direction gives a strict likelihood increase. The same conclusion holds for a Newton direction if $-H(\beta)$ is symmetric positive definite and $U(\beta)\ne 0$.

For the Newton case, the direction satisfies $(-H(\beta))d=U(\beta)$. If $-H(\beta)$ is symmetric positive definite, then $$ U(\beta)^{\mathsf T}d =d^{\mathsf T}(-H(\beta))d>0 $$ for every nonzero $d$. This verifies the theorem’s ascent condition under the stated curvature assumption. If the score is zero, these arguments do not provide a strictly improving direction; at such a point there may be no need for an update, but that is a separate algorithmic decision.

Worked Example: Halving Rescues an Oversized Logistic Update

Use the same four-observation logistic intercept model, with three successes and one failure, but start at $\beta=-4$. Here $p=1/(1+\exp(4))\approx0.0179862$, so $$ U(-4)=3-4p\approx2.928055,\qquad -H(-4)=4p(1-p)\approx0.0706508. $$ The Newton direction is therefore $d\approx2.928055/0.0706508\approx41.44$. The current likelihood is $$ \ell(-4)=-12-4\log(1+\exp(-4))\approx-12.0726. $$

The full-step candidate is approximately $37.44$. For this large positive value, $\log(1+\exp(\beta))$ is approximately $\beta$, so its log-likelihood is approximately $3\beta-4\beta=-\beta\approx-37.44$, a decrease. The half-step candidate is approximately $16.72$, with log-likelihood approximately $-16.72$, also a decrease. These approximations are far enough from the current value to establish that both trials are rejected.

The quarter-step candidate is approximately $-4+41.44/4=6.36$. At this value, $$ \ell(6.36)=3(6.36)-4\log(1+\exp(6.36))\approx-6.37. $$ This is greater than $-12.0726$, so the quarter step is accepted. The direction was useful, but the full Newton update was too large; step-halving retained the direction while reducing its length until the actual likelihood improved.

What the Guarantee Does—and Does Not—Say

The theorem concerns a fixed direction and exact likelihood evaluations. It says that positive directional derivative plus local differentiability is enough for an improving dyadic trial to exist. It does not say that every Newton or scoring direction is ascending, that the full step will be accepted, or that the accepted step is the largest possible improving step. Those questions depend on the current model, coefficient vector, and likelihood geometry.

In particular, an update derived from a local quadratic approximation should not be accepted merely because it solves the Newton or scoring equations. Those equations determine a proposal; the likelihood comparison determines whether that proposal, at its tested length, is accepted. This distinction is why the acceptance test evaluates the actual fitted-model log-likelihood rather than only the approximation used to compute $d$.

Common Mistake

Wrong reasoning: “The Newton or Fisher-scoring equations produced this update, so the full step must increase the log-likelihood.” Those equations use local score and curvature information and do not, by themselves, guarantee an increase over a full step.
Correction: Evaluate $\ell(\beta+d)$ and compare it with $\ell(\beta)$. If the full step fails the nondecrease test, try $\beta+d/2$, then successive halvings. The local theorem guarantees eventual strict improvement only when the direction has positive directional derivative and the likelihood is differentiable in a neighborhood of the current point.

Key takeaway: Step-halving is a likelihood-based acceptance safeguard: it tests progressively shorter versions of a proposed Newton or Fisher-scoring direction and accepts the first one that does not decrease the actual log-likelihood. Positive directional derivative and local differentiability ensure that this search eventually finds a strictly improving step.

Check Your Understanding

Answer each question using the definitions and conditions in this tutorial.

Write the first four trial step fractions used by step-halving, and state the likelihood condition for acceptance.
Why does a positive value of $U(\beta)^{\mathsf T}d$ imply that sufficiently small positive steps improve a differentiable log-likelihood?
For a Fisher-scoring direction with symmetric positive-definite information, show why a nonzero score gives a positive directional derivative.
In the logistic example starting at $\beta=-4$, why was the quarter step accepted even though the full and half steps were rejected?
Does the finite-acceptance result apply when $U(\beta)^{\mathsf T}d=0$? Explain what condition the proof uses.