Step Sizes and the Descent Lemma in Gradient Descent

The update x ← x − η∇f(x) is one line of arithmetic, and every property that makes it useful or useless lives in the scalar η. A step that is too small wastes iterations; a step that is too large makes the objective oscillate, then diverge. The set of admissible step sizes is fixed by one property of the objective, the rate at which its gradient can change, and the inequality that converts that property into a guaranteed decrease per iteration is the descent lemma. Reading the lemma backwards gives the step size, gives the convergence rate, and gives the precise sense in which the rate is pessimistic.

The quadratic model that sets the scale

Take the one-dimensional quadratic f(x) = (L/2)x², with L > 0. Its gradient is Lx, and one gradient step multiplies the iterate by 1 − ηL. The error therefore contracts geometrically when |1 − ηL| < 1, that is, when 0 < η < 2/L. At η = 2/L the iterate alternates in sign with unchanged magnitude forever. For η > 2/L the magnitude grows without bound. The useful interval is bounded above by a constant divided by the curvature, and the best single choice among fixed steps is η = 1/L, which sends the error to zero in a single step.

A general smooth objective behaves like that quadratic locally, with different curvature in different directions. For a quadratic form with Hessian eigenvalues in the interval [μ, L], the same analysis applies to each eigendirection independently: convergence needs η < 2/L, and the slowest direction, the one with curvature μ, contracts by the factor 1 − ημ per iteration. The ratio κ = L/μ is the condition number, and it is the quantity that separates a problem that takes tens of iterations from one that takes millions. A quadratic with κ = 10³ and η = 1/L shrinks the error along the flat direction by a factor of 1 − 10⁻³ per step, so roughly 10³ · ln(1/ε) iterations are needed for accuracy ε. Rescaling the variables does not change the problem but does change L, μ, and the step size that works: gradient descent is not invariant to reparametrization, which is why the diagonal preconditioning described in adaptive step sizes can change iteration counts by orders of magnitude on the same objective.

The descent lemma and the bound on η

The local quadratic approximation is made rigorous by a smoothness assumption. A differentiable f is L-smooth, in the sense of Lipschitz continuity of the gradient, when ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖ for all x, y. That single inequality is equivalent to the quadratic upper bound

f(y) ≤ f(x) + ∇f(x)ᵀ(y − x) + (L/2)‖y − x‖²,

which is the descent lemma. It states that the function never rises above a parabola anchored at x with curvature L. Substituting the gradient step y = x − η∇f(x) into it gives

f(x⁺) ≤ f(x) − η(1 − ηL/2)‖∇f(x)‖².

The prefactor η(1 − ηL/2) is positive exactly when η < 2/L, and it is maximized at η = 1/L, where it equals 1/(2L). So smoothness alone guarantees a decrease proportional to the squared gradient norm, provided the step stays below 2/L, and a step of 1/L gives the largest guaranteed decrease. This is the whole content of the classical analysis: no convexity, no randomness, no assumption that the iteration converges to anything in particular.

Two features of the bound matter in practice. First, it is a worst-case statement about one iteration: the actual decrease can be much larger, and the bound is tight for quadratics. Second, the required L is global. If the objective has one narrow valley and a large flat region, the global L is set by the steepest curvature, and the resulting step size throttles progress everywhere else. Local estimates of L, measured along the last step direction, recover much of the loss, and that is the mechanism behind the line search below.

Driving a real iteration with backtracking

The Armijo condition turns the descent lemma into a terminating search: accept a step only if the realized decrease is at least a fixed fraction c₁ of the decrease predicted by the directional derivative. Starting from a trial step and halving until the condition holds terminates, because for small enough η the linear model dominates the quadratic error term.

def backtracking_step(f, grad, x, d, eta=1.0, rho=0.5, c1=1e-4, nmax=50):
    """Largest eta * rho**k among a few halvings that satisfies Armijo."""
    g = grad(x)
    fx = f(x)
    slope = sum(gi * di for gi, di in zip(g, d))   # directional derivative
    if slope >= 0:
        raise ValueError('not a descent direction')
    for _ in range(nmax):
        if f([xi + eta * di for xi, di in zip(x, d)]) <= fx + c1 * eta * slope:
            return eta
        eta *= rho
    return eta          # fall back to the smallest step tried

The slope check is not decoration. Any direction with a non-negative directional derivative cannot be accepted by Armijo for η > 0, and the loop would shrink the step to nothing. With rho = 0.5 and nmax = 50, the smallest trial step is 2⁻⁵⁰ times the initial one, far below double-precision relevance; the iteration would stall rather than fail loudly, which is exactly the kind of silent degeneracy that makes a stalled training run hard to attribute. Armijo alone also accepts steps that are too small, so production implementations pair it with the curvature condition in the Wolfe conditions, discussed in quasi-Newton methods and the L-BFGS recursion, where the accuracy of the step size directly determines whether the curvature estimate is usable.

Rates under convexity, and what the constants hide

Adding convexity converts per-iteration decrease into a rate. With η = 1/L, convexity and the descent lemma together give

f(x_k) − f* ≤ L‖x₀ − x*‖² / (2k),

so the function-value gap falls as O(1/k) and reaching accuracy ε costs O(1/ε) iterations. Adding μ-strong convexity upgrades the rate to linear: the gap contracts by roughly (1 − 1/κ) per iteration, giving O(κ log(1/ε)) iterations. The distinction is not cosmetic. 1/ε growth means that improving a solution by one decimal digit costs ten times more iterations, whereas log(1/ε) growth means the same improvement costs a fixed additive budget.

The constants deserve as much attention as the exponents. The convex bound depends on the squared initial distance ‖x₀ − x*‖², which grows with the dimension and with the scale of initialization. The strongly convex bound carries κ in the exponent through (1 − 1/κ), so a condition number of 10⁶ needs on the order of 10⁶ · ln(1/ε) iterations. Both bounds assume the step is exactly 1/L; a step of 0.5/L is safe but halves the contraction per step, and a step chosen adaptively without a global L yields the same asymptotic exponents with worse constants. The gap between these worst-case bounds and observed iteration counts is large for structured problems, which is why the practical literature on step schedules is dominated by heuristics informed by the bounds rather than derived from them.

The same inequality seen as a trust region

The descent lemma can be read as a statement about a model rather than a step size. Write the local model m(p) = f(x) + ∇f(x)ᵀp + (L/2)‖p‖². Its unconstrained minimizer is p = −∇f(x)/L, which is exactly the gradient step at η = 1/L. Constrain the model instead by a radius, ‖p‖ ≤ Δ, and the minimizer becomes p = −Δ · ∇f(x)/‖∇f(x)‖: a step of fixed length that ignores the gradient magnitude. That is the trust-region rule, and its practical advantage is that Δ is a length in the same units as x, so it adapts to scale without any estimate of L.

The adaptation is driven by the ratio of realized to predicted decrease. If the ratio is below a conventional threshold such as 0.25, the model is untrustworthy and Δ shrinks, typically by half. If it exceeds a conventional threshold such as 0.75, the model underestimated the curvature and Δ grows, often doubling. The two quantities are the same object viewed from different sides: Δ plays the role of η‖∇f‖, so a large gradient forces a short step in trust-region language and a fixed η forces a short step in the other. Trust-region sizes also compose with the Gauss–Newton and quasi-Newton directions where the curvature estimate can be indefinite, which is why the framework persists in solvers that never use plain gradient descent.

Where the guarantee stops applying

The descent lemma needs a finite L, and several common objectives do not have one. The absolute value, the hinge loss, and the ℓ₁ norm have a kink at zero, so no finite Lipschitz constant exists; gradient descent with any fixed step either stalls or oscillates around the kink. Subgradient and proximal methods handle these cases by replacing the gradient step with a different operator, as covered in projected and proximal gradient methods. Second, and larger in practice, the gradient may be replaced by a stochastic estimate, whose noise moves the iterate off the deterministic trajectory and replaces the monotone decrease with a guarantee only in expectation; the noise floor is the subject of stochastic gradient descent and step decay.

There are also failure modes that the inequality permits. The guarantee is on function value, not on distance to a minimizer, so an iteration can decrease the objective steadily while the iterate wanders. A step of 1/L derived from a loose upper bound on curvature produces a rate that is correct and useless. And in floating-point arithmetic the decrease 1/(2L)‖∇f‖² becomes smaller than the representable difference between two nearby function values, at which point the line search accepts the first trial step by accident and the loop stops making progress without any error being raised.