Gradient Descent Convergence, in depth: the descent lemma, O(1/k) and linear rates, acceleration, backtracking and the SGD noise floor

Assumptions that decide the rate

We minimise a differentiable function f over real vectors x. Gradient descent with step size eta produces the sequence x(k+1) = x(k) - eta * grad f(x(k)). Everything below rests on a few assumptions about f, and the first habit to build is naming which ones hold before quoting any rate.

For a twice-differentiable f, L-smoothness means every eigenvalue of the Hessian is at most L in magnitude, and strong convexity means every eigenvalue is at least mu. The ratio kappa = L / mu is the condition number, and it sets how many iterations every first-order method needs.

Least squares, linear regression and L2-regularised logistic regression satisfy all of the convex assumptions. Deep networks satisfy none of them globally, so for training the nonconvex bound is the relevant one.

The descent lemma

L-smoothness gives a quadratic upper bound on f around any point. This is the descent lemma: f(y) <= f(x) + grad f(x)^T (y - x) + (L/2) |y - x|^2. Substitute the gradient step y = x - eta * grad f(x) and the inner product and the square both become multiples of |grad f(x)|^2:

f(x - eta*g) <= f(x) - eta*|g|^2 + (L/2)*eta^2*|g|^2
             =  f(x) - eta*(1 - L*eta/2)*|g|^2

Read the bracket. If 0 < eta < 2/L the coefficient is positive, so every step strictly decreases f unless the gradient is already zero. The decrease is largest at eta = 1/L, where the guaranteed progress is |g|^2 / (2L). That is why 1/L appears in every textbook proof: it is the step that maximises this worst-case bound, not a magic constant. Above 2/L there is no guarantee at all, and on a quadratic the component along the steepest direction is multiplied by |1 - eta*L| > 1 every step, so the iterates grow without bound.

Each rate below combines this per-step decrease with a lower bound on |g|^2 in terms of f(x) - f*; the strength of that lower bound decides the rate.

Four guarantees from one inequality

Nonconvex, L-smooth. Sum the per-step decrease from k = 0 to K - 1 with eta = 1/L. The left side telescopes to f(x0) - f(xK), which is at most f(x0) - f*. So the sum of squared gradient norms is at most 2L (f(x0) - f*), and the smallest one satisfies min |grad f(x(k))|^2 <= 2L (f(x0) - f*) / K. This guarantees an approximately stationary point, not a minimum: it could be a saddle.

Convex, L-smooth. Convexity relates the gradient to the distance from the minimiser, and a short argument gives f(xK) - f* <= L |x0 - x*|^2 / (2K). This is O(1/k): halving the error doubles the iterations.

Strongly convex or PL. The PL inequality says |g|^2 >= 2 mu (f - f*). Insert it into the descent lemma with eta = 1/L: f(x(k+1)) - f* <= (1 - mu/L)(f(x(k)) - f*). The error shrinks by a constant factor every step, so f(xK) - f* <= (1 - 1/kappa)^K (f(x0) - f*). Taking logs, you need about kappa * ln(1/epsilon) iterations for relative accuracy epsilon. Strong convexity implies PL, so this covers both, and PL also holds for some nonconvex problems, including least squares with a rank-deficient design matrix where strong convexity fails.

Accelerated. Nesterov's method adds a momentum extrapolation, y = x(k) + beta (x(k) - x(k-1)), and takes the gradient step from y. For convex f it achieves f(xK) - f* <= 2L |x0 - x*|^2 / (K + 1)^2, and with the constant beta = (1 - sqrt(1/kappa)) / (1 + sqrt(1/kappa)) on strongly convex f it needs on the order of sqrt(kappa) ln(1/epsilon) iterations. Nesterov also proved lower bounds showing that no method using only gradient information at the visited points can beat these rates by more than a constant factor on worst-case smooth convex functions. Acceleration is optimal, not merely better.

Worked example: measured iterations against the bounds

Take the quadratic f(x) = (1/2)(10 x1^2 + 0.1 x2^2), so L = 10, mu = 0.1 and kappa = 100, start at x0 = (1, 1), where f(x0) = 5.05, and stop when f has dropped by a factor of a million. The script below runs four methods and counts iterations.

import math

LAM = [10.0, 0.1]                    # Hessian eigenvalues: L = 10, mu = 0.1
L, MU = max(LAM), min(LAM)

def f(x):
    return 0.5 * sum(l * v * v for l, v in zip(LAM, x))

def grad(x):
    return [l * v for l, v in zip(LAM, x)]

X0 = [1.0, 1.0]
TOL = 1e-6 * f(X0)

def gd(step):
    x, k = list(X0), 0
    while f(x) > TOL:
        x = [v - step * g for v, g in zip(x, grad(x))]
        k += 1
    return k

def nesterov():
    q = MU / L
    beta = (1 - math.sqrt(q)) / (1 + math.sqrt(q))
    x = y = list(X0)
    k = 0
    while f(x) > TOL:
        x_new = [v - g / L for v, g in zip(y, grad(y))]
        y = [a + beta * (a - b) for a, b in zip(x_new, x)]
        x, k = x_new, k + 1
    return k

def armijo(t0=1.0, c=0.5, shrink=0.5):
    x, k, evals = list(X0), 0, 0
    while f(x) > TOL:
        g = grad(x)
        gg = sum(v * v for v in g)
        t = t0
        while True:
            trial = [v - t * gi for v, gi in zip(x, g)]
            evals += 1
            if f(trial) <= f(x) - c * t * gg:
                break
            t *= shrink
        x, k = trial, k + 1
    return k, evals

print("GD, step 1/L      ", gd(1 / L))
print("GD, step 2/(L+mu) ", gd(2 / (L + MU)))
print("Nesterov          ", nesterov())
print("Armijo (iters, f evals)", armijo())
print("Bound kappa*ln(1e6)", math.ceil(math.log(1e-6) / math.log(1 - MU / L)))

Three lessons come out of these numbers. First, the bound is a worst case: the measured 458 is a third of the 1,375 the bound predicts, because the slow coordinate starts with only 1 percent of the error, and its error, measured in f, shrinks by (1 - mu/L) squared per step rather than once. Bounds give scaling, not exact counts. Second, Nesterov's 63 against 458 is the sqrt(kappa) story in action; at kappa = 10,000 the gap would be roughly a hundredfold. Third, a step just 5 percent above 2/L does not converge slowly, it explodes. The safe region has a hard edge, and a learning-rate warmup exists in part to keep early steps away from it while the curvature is still unknown.

When L is unknown: backtracking line search

In practice you rarely know L, and guessing it wrong either wastes iterations or diverges. Backtracking line search removes the guess. Start each iteration with a trial step t0, and while f(x - t g) > f(x) - c t |g|^2 multiply t by beta. Common choices are c = 1e-4 to 0.5 and beta = 0.5.

The descent lemma guarantees the loop terminates: any t at most 2(1 - c)/L satisfies the condition, so the accepted step is at least beta times that. All of the rates above therefore survive with L replaced by a constant multiple of it. You pay in function evaluations, 397 against 117 gradients in the example, which is a good deal whenever a function value costs no more than a gradient. When f is a mini-batch loss, function values are noisy and the condition becomes unreliable, which is one reason deep learning uses schedules instead of line searches.

Stochastic gradients and the noise floor

Replace grad f with an unbiased estimate g whose variance is at most sigma^2, as in mini-batch training. The descent lemma now holds in expectation with an extra term, (L/2) eta^2 sigma^2, that does not shrink as you approach the minimum. For a mu-strongly convex f with a constant step eta <= 1/L the result is:

E[f(x_k)] - f*  <=  (1 - eta*mu)^k * (f(x_0) - f*)   +   eta * L * sigma^2 / (2 * mu)
                    ---------------------------          -------------------------------
                    forgets the start, linearly          noise floor, set by the step size

This one line explains most learning-rate folklore. A constant step converges quickly to a neighbourhood whose size is proportional to eta, then stalls. Halving the step halves the floor but also halves the contraction speed. Decaying the step, for example eta(k) proportional to 1/k on strongly convex problems or 1/sqrt(k) on general convex ones, drives the floor to zero at the price of sublinear rates: O(1/k) and O(1/sqrt(k)) respectively. Larger batches divide sigma^2 by the batch size, which lowers the floor without slowing the contraction, and that is the theoretical case for growing batch size late in training. Adaptive methods change the geometry of the step and are compared in SGD versus Adam math.

Stopping rules

Four stopping rules are used in practice, and each fails differently.

For strongly convex problems the PL inequality turns the gradient norm into a certified bound: f(x) - f* <= |grad f(x)|^2 / (2 mu). If you know or can lower-bound mu, a gradient test is an optimality test. For training, combine a budget with a held-out metric and treat the loss curve as evidence, not proof.

Failure modes

• Step above 2/L. Divergence that starts slowly, often after a curvature increase partway through training. Watch for loss spikes and use gradient clipping as a guard rail, not as a substitute for a sound step.
• Ill-conditioning mistaken for a bug. kappa of 1e6 means millions of plain GD iterations. Rescale features, precondition or switch to a second-order or accelerated method before debugging the code.
• Mistaking the noise floor for convergence. A flat SGD loss with a constant step means you reached the floor, not the minimum. Decay the step or grow the batch and see whether it moves.

Trade-offs

What to do next

1. Write down which assumptions your objective satisfies (smooth, convex, strongly convex, PL) before quoting any convergence rate.
2. Estimate L by power iteration on Hessian-vector products, or with a backtracking run, and keep the step below 2/L.
3. Run the worked-example script, then change kappa to 1,000 and 10,000 and confirm that plain GD scales with kappa and Nesterov with sqrt(kappa).
4. For SGD, plot loss against step for two constant learning rates; if both flatten at different levels you are seeing the noise floor, so schedule a decay.
5. Pick a stopping rule from the table, document it, and for strongly convex problems use the |g|^2 / (2 mu) certificate.