Armijo Backtracking for GLM Optimization

Why Require More Than a Positive Likelihood Change?

A Newton or Fisher-scoring update can point uphill at the current coefficient vector and still be too large to work well. The log-likelihood may increase only slightly, or even decrease, after taking the full step. A line search addresses this by keeping the direction fixed while reducing the distance moved along it. The Armijo condition makes the acceptance test more informative than simply asking whether the likelihood went up: it requires an increase proportional to the step length and the local directional derivative.

Write the GLM log-likelihood as $\ell(\beta)$, where $\beta$ is the coefficient vector, and let $U(\beta)=\nabla\ell(\beta)$ be its score vector. Given a proposed direction $d$, the trial coefficient vector at step length $\alpha>0$ is $\beta+\alpha d$. The directional derivative at the current point is $U(\beta)^{T}d$. A positive value means that sufficiently small positive steps along $d$ increase the log-likelihood, provided the likelihood is differentiable there.

Definition: For a differentiable log-likelihood, current coefficient vector $\beta$, direction $d$, and constants $c\in(0,1)$, $\rho\in(0,1)$, the Armijo sufficient-increase condition accepts a trial step length $\alpha$ when $$ \ell(\beta+\alpha d)\ \geq\ \ell(\beta)+c\alpha\,U(\beta)^T d. $$ The right-hand increment is a fraction $c$ of the first-order increase predicted at the current point. Armijo backtracking tests $\alpha_j=\alpha_0\rho^j$, for $j=0,1,2,\ldots$, starting from a chosen $\alpha_0>0$, and takes the first trial satisfying the condition.

For maximization, the usual setting is an ascent direction, $U(\beta)^T d>0$. Then the Armijo right-hand side is strictly greater than the current log-likelihood, so any accepted step must give a genuine increase. Common choices include $\alpha_0=1$ and $\rho=1/2$, but these are conventions rather than requirements of the condition. The parameter $c$ controls how demanding the sufficient-increase test is: a larger $c$ requires a larger fraction of the local linear prediction.

Applying the Backtracking Test

The calculation has a fixed order. First evaluate the current log-likelihood and the directional derivative $U(\beta)^T d$. Then compute the Armijo threshold for the current trial length, evaluate the log-likelihood at the trial coefficients, and compare the two sides. If the condition fails, reduce $\alpha$ by the factor $\rho$ and repeat. The direction does not change during this line search.

Check ascent.
Compute $g=U(\beta)^T d$. For the standard sufficient-increase guarantee, require $g>0$.

Set a trial length.
Choose $\alpha=\alpha_0$ and calculate the required increase $c\alpha g$.

Evaluate the trial.
Accept if $\ell(\beta+\alpha d)-\ell(\beta)\geq c\alpha g$. Otherwise replace $\alpha$ by $\rho\alpha$ and test again.

Worked Example: A Logistic Trial That Passes at Full Length

Suppose four Bernoulli observations are modeled with a logistic intercept $\beta$: three outcomes are successes and one is a failure. Ignoring constants that do not depend on $\beta$, the log-likelihood is $$ \ell(\beta)=3\beta-4\log(1+e^\beta). $$ At $\beta=0$, take the proposed direction $d=2$, with $\alpha_0=1$ and $c=0.1$. This direction is chosen for illustration; it need not be the Newton direction.

The score is $U(\beta)=3-4e^\beta/(1+e^\beta)$, so $U(0)=3-2=1$. Thus the directional derivative is $U(0)d=1(2)=2$, and the Armijo threshold at $\alpha=1$ is $0.1(1)(2)=0.2$.

The trial coefficient is $0+1(2)=2$. Its log-likelihood change is $$ \ell(2)-\ell(0)=6-4\log\!\left(\frac{1+e^2}{2}\right). $$ Using $e^2\approx7.389056$, $(1+e^2)/2\approx4.194528$, and $\log(4.194528)\approx1.43378$, the change is approximately $6-4(1.43378)=0.265$. Since $0.265>0.2$, Armijo backtracking accepts the full step. The check uses the likelihood change, not merely its positivity: the trial exceeds the required increase of $0.2$.

Worked Example: A Poisson Newton Step Is Shortened

Let $Y_1=1$ and $Y_2=5$ be independent Poisson observations with the same log mean $\beta$, so each mean is $e^\beta$. Up to terms independent of $\beta$, $$ \ell(\beta)=6\beta-2e^\beta. $$ At $\beta=0$, the score is $U(0)=6-2=4$, and the observed information is $2e^0=2$. The Newton direction obtained by dividing the score by this information is $d=4/2=2$. Its directional derivative is therefore $U(0)d=4(2)=8$. This product matters: using $4$ instead of $8$ would give an incorrect Armijo threshold.

Set $\alpha_0=1$, $\rho=1/2$, and $c=0.1$. At the full step, the required increase is $0.1(1)(8)=0.8$, while the actual change is $$ \ell(2)-\ell(0)=12-2(e^2-1)\approx12-2(6.389056)=-0.778. $$ The trial decreases the log-likelihood and fails the condition. Backtrack to $\alpha=0.5$. The required increase is now $0.1(0.5)(8)=0.4$, and the actual change is $$ \ell(1)-\ell(0)=6-2(e-1)\approx6-2(1.718282)=2.563. $$ Since $2.563\geq0.4$, the half-step is accepted. This calculation shows how the condition rejects an oversized full update while retaining the original direction.

Worked Example: The Choice of Armijo Constant Changes Acceptance

Consider two Bernoulli observations, both successes, under a logistic intercept model. The log-likelihood, up to a constant, is $$ \ell(\beta)=2\beta-2\log(1+e^\beta). $$ At $\beta=0$, the score is $2-1=1$. Take the ascent direction $d=3$, initial length $\alpha_0=1$, reduction factor $\rho=1/2$, and Armijo constant $c=0.5$. The directional derivative is $1(3)=3$.

For $\alpha=1$, the threshold is $0.5(1)(3)=1.5$. The trial change is $$ \ell(3)-\ell(0)=6-2\log\!\left(\frac{1+e^3}{2}\right)\approx1.29. $$ It is positive, but it is less than $1.5$, so the Armijo test rejects it. At $\alpha=0.5$, the threshold is $0.5(0.5)(3)=0.75$, and the change is $$ \ell(1.5)-\ell(0)=3-2\log\!\left(\frac{1+e^{1.5}}{2}\right)\approx0.984. $$ This exceeds $0.75$, so backtracking accepts $\alpha=0.5$. A positive change alone would have accepted the full step; the sufficient-increase requirement rejects it because its improvement is too small relative to the local prediction.

Why Backtracking Terminates for an Ascent Direction

The guarantee behind backtracking is local. It does not require the log-likelihood to be globally concave, nor does it claim that every accepted step is close to an optimum. It says that, under differentiability and a genuine ascent direction, sufficiently short steps satisfy the Armijo condition. The geometric sequence of trial lengths eventually reaches such a step.

Theorem: Suppose $\ell$ is finite and differentiable on an open neighborhood of $\beta$, $d$ is a fixed direction with $g=U(\beta)^Td>0$, $c\in(0,1)$, $\rho\in(0,1)$, and $\alpha_0>0$. Then Armijo backtracking with trial lengths $\alpha_0\rho^j$ accepts a step after finitely many reductions.

Proof. Define the one-dimensional function $\phi(t)=\ell(\beta+td)$ for $t$ in a sufficiently small neighborhood of zero. Since the parameter domain is open, these points are in the domain for all sufficiently small $t$. Differentiability of $\ell$ at $\beta$ gives $\phi'(0)=U(\beta)^Td=g$. By the definition of derivative, $$ \lim_{t\downarrow0}\frac{\phi(t)-\phi(0)}{t}=g. $$ Because $g>0$ and $c<1$, we have $g>cg$. Therefore, by the definition of this limit, there is a $\delta>0$ such that for every $t$ with $0<t<\delta$, $$ \frac{\phi(t)-\phi(0)}{t}>cg, $$ or, equivalently, $\ell(\beta+td)>\ell(\beta)+ctg$. The trial sequence $\alpha_0\rho^j$ tends to zero because $0<\rho<1$. Hence some finite $j$ has $0<\alpha_0\rho^j<\delta$, and that trial satisfies the Armijo condition. $\square$

This proof uses only differentiability at the current point and the convergence of the geometric trial lengths. It does not rely on interchanging a limit and an integral, or on a global shape condition for the likelihood. The conclusion can fail if the proposed direction is not an ascent direction, if the likelihood is undefined at the trials, or if the numerical implementation cannot evaluate the trials reliably.

When a Newton or Scoring Direction Is an Ascent Direction

For a common construction of a direction, the ascent check follows from positive curvature information. Let $A$ be a symmetric positive-definite matrix and define $d$ by $Ad=U(\beta)$. This covers a Newton-type ascent direction when the matrix used in the solve is positive definite; in a GLM it may be an observed or expected information matrix. The positive-definiteness condition is important: the algebra below does not assert that every Newton direction is an ascent direction.

Result: If $A$ is symmetric positive definite, $Ad=U(\beta)$, and $U(\beta)\ne0$, then $U(\beta)^Td>0$.

Proof. Since $Ad=U(\beta)$, multiply on the left by $d^T$ to obtain $$ U(\beta)^Td=d^TAd. $$ The vector $d$ is nonzero: otherwise $Ad=0$ would imply $U(\beta)=0$, contrary to the assumption. Positive definiteness therefore gives $d^TAd>0$. It follows that $U(\beta)^Td>0$, as claimed. $\square$

Thus, when the information matrix used in the update is positive definite and the score is nonzero, the direction passes the ascent check required by the termination result. If the matrix is not positive definite, this argument does not apply; the directional derivative should be checked directly rather than presumed positive.

Common Mistakes and Practical Interpretation

Using the wrong directional derivative. The Armijo prediction is $U(\beta)^Td$, not just the score, not just the step length, and not necessarily a single coordinate of either vector. For the Poisson example, $U(0)=4$ and $d=2$, so the product is $8$.
Accepting any positive increase. A trial can increase the likelihood and still fail Armijo, as the full step in the third example does. The required increase is $c\alpha U(\beta)^Td$.
Changing the direction during backtracking. Backtracking tests shorter lengths along the same $d$. Recomputing a Newton or scoring direction after each rejection is a different procedure.
Assuming termination without its hypotheses. The guarantee requires a differentiable finite likelihood near the current point and $U(\beta)^Td>0$. It is not a promise that an arbitrary direction or an invalid trial will be accepted.
Interpreting acceptance as proof of a maximum. Armijo acceptance certifies a sufficient local increase for that trial only. It does not establish that the likelihood has reached a maximum.

Key takeaway: Armijo backtracking compares the actual log-likelihood gain with a fraction of the directional first-order prediction. For a differentiable likelihood and an ascent direction, repeatedly shrinking the step geometrically must eventually produce a sufficient increase.

Check Your Understanding

Use the directional derivative and the Armijo threshold explicitly in each answer.

For $U(\beta)^Td=5$, $c=0.2$, and $\alpha=0.4$, what minimum likelihood increase is required?
Why does a positive likelihood change not by itself establish that a trial satisfies the Armijo condition?
If $\alpha_0=1$ and $\rho=1/2$, write the first four trial lengths, starting with the initial trial.
Which assumptions in the termination result ensure that sufficiently small steps satisfy the condition?
If $Ad=U(\beta)$ with $A$ symmetric positive definite and $U(\beta)\ne0$, what identity establishes that $d$ is an ascent direction?