Gradient descent: choosing the step and knowing the rate

Gradient descent is one line repeated:

$x_{k+1} = x_k - \eta \nabla f(x_k)$

The gradient points uphill, so you step against it. Everything interesting is in $\eta$, the step size.

Too small and you crawl, spending thousands of iterations covering ground a larger step crosses in ten. Too large and you overshoot the valley floor onto the opposite wall, higher than where you started, and the iterates diverge.

What makes this a mathematical question rather than a matter of taste is that the boundary between those regimes is computable. For a convex function with bounded curvature there is a threshold above which divergence is guaranteed and below which decrease is guaranteed, and it depends on exactly one constant.

Assume $f$ is $L$-smooth, meaning its gradient is Lipschitz with constant $L$, equivalently $\nabla^2 f \preceq L I$. That single assumption produces the descent lemma, the workhorse of the whole theory:

$f(y) \le f(x) + \nabla f(x)^\top (y - x) + \frac{L}{2}\|y - x\|^2$

Read it as a picture. At any point you have the tangent line, and smoothness says the function never rises faster than a fixed quadratic sitting on top of that tangent. You cannot be surprised by more curvature than $L$.

Key idea: Convexity gave a lower bound on the function, since the tangent underestimates it. Smoothness gives an upper bound. Squeezed between a linear floor and a quadratic ceiling, the step size stops being guesswork.

Put the gradient step $y = x - \eta \nabla f(x)$ into the descent lemma:

$f(x - \eta \nabla f(x)) \le f(x) - \eta \|\nabla f(x)\|^2 + \frac{L \eta^2}{2}\|\nabla f(x)\|^2 = f(x) - \eta\left(1 - \frac{L\eta}{2}\right)\|\nabla f(x)\|^2$

The bracket is positive whenever $\eta < 2/L$, so every step strictly decreases $f$ unless the gradient is already zero. Minimising the guaranteed decrease over $\eta$ puts the optimum at $\eta = 1/L$, which gives

$f(x_{k+1}) \le f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2$

So $2/L$ is where divergence begins and $1/L$ is the best fixed step the bound can justify. Neither number was tuned; both fell out of one curvature assumption.

How fast the error shrinks depends on whether the function is merely convex or strongly convex.

The gap is enormous. Under plain convexity, ten times the accuracy costs ten times the work. Under strong convexity, error falls by a constant factor every iteration, so each additional decimal digit costs a fixed number of steps.

The price is the condition number $\kappa = L/\mu$ sitting in front of the logarithm. Strong convexity buys you a fast regime; conditioning decides how fast that fast regime actually is.

Take the strongly convex bound $(1 - 1/\kappa)^k$ and plot it for a well-conditioned and a badly-conditioned problem.

At $\kappa = 10$ the error is under one percent by iteration 50. At $\kappa = 100$ it has not yet halved. Both problems are convex, both have the theoretical guarantee, and one of them is useless in practice. Conditioning, not convexity, is what people are fighting when optimization runs slowly.

Real problems reach condition numbers far worse than 100.

The geometry explains the arithmetic. On a badly conditioned quadratic the level sets are long thin ellipses, and the gradient points nearly perpendicular to the valley floor rather than along it.

So each step crosses the valley rather than travelling down it. The iterates zigzag between the walls, making rapid progress on the steep direction, which was never the bottleneck, and almost none along the shallow direction where the solution actually lies.

Gotcha: This is a property of the parameterisation, not of the underlying problem. Rescaling the variables changes $\kappa$ and therefore changes the convergence rate, without changing the geometry of the solution at all. Feature normalisation in machine learning is exactly this trick: it is conditioning work dressed as data preparation.

On a diagonal quadratic $f(x) = \tfrac{1}{2} x^\top A x$ the constants are readable off the matrix: $L$ is the largest eigenvalue, $\mu$ the smallest.

import numpy as np

def run(kappa, steps=100):
    A = np.diag([1.0, kappa])        # mu = 1, L = kappa
    x = np.array([1.0, 1.0])
    eta = 1.0 / kappa                # the safe step, 1/L
    for _ in range(steps):
        x = x - eta * (A @ x)
    return 0.5 * x @ A @ x           # f(x), optimal value is 0

for k in (10, 100, 1000):
    print(k, f"{run(k):.3e}")
# 10   1.16e-05
# 100  2.05e-01
# 1000 4.53e-01

The step size is forced down by the largest eigenvalue while progress is governed by the smallest, which is the condition number acting through the algorithm rather than merely appearing in its bound.

Nesterov's accelerated gradient adds a momentum term, taking the step from a point extrapolated past the current iterate rather than from the iterate itself. The cost per iteration is unchanged: still one gradient.

Key idea: Nesterov also proved a matching lower bound: no method that only queries gradients can beat $O(1/k^2)$ on this function class. Acceleration is not a clever heuristic that might be improved on later. It is the end of the road for first-order information, and getting past it requires using second derivatives, which is the next lesson.

Every rate above assumes an exact gradient, a known $L$, and a fixed step. Practice violates all three.

• Gradients are estimated. Stochastic gradient descent uses a minibatch, so the variance floor means a fixed step converges to a neighbourhood of the optimum rather than the optimum, and the step must decay to close that gap.
• $L$ is unknown. Backtracking line search shrinks a trial step until the descent lemma is satisfied, recovering the guarantee without ever computing $L$.
• Steps are adapted. Adam and its relatives keep per-coordinate scales, an approximation of the rescaling that conditioning arguments say you want.

In practice: These methods are chosen because they behave well empirically, not because the convex rates transfer. The theory tells you what governs speed. It does not certify the optimiser in your training script.

Everything here used one piece of local information: the slope. That is enough to guarantee progress, and the lower bound says it is not enough to do better than $O(1/k^2)$.

The missing information is curvature. Gradient descent takes the same shaped step in every direction and lets a scalar $\eta$ mediate, which is why an elongated valley defeats it. A method that knows the Hessian can take a differently shaped step in every direction at once, and stops caring about conditioning entirely.

That is Newton's method, and layering it on top of a barrier function is what turned constrained optimization from a heuristic craft into something with polynomial-time guarantees. Before that, the next lesson in this path covers the constrained machinery those methods rely on: the Lagrangian, duality, and the KKT conditions.