Gradient descent

The negative gradient is the steepest-descent direction; gradient descent simply takes repeated steps along it. It is the algorithm under nearly every model trained today. This lesson derives the update from a local quadratic model, explains the step-size tradeoff, and proves it makes progress on smooth functions.

The update

Gradient descent generates iterates by

where $\eta > 0$ is the step size (learning rate). Each step moves opposite the gradient, downhill, by an amount scaled by $\eta$[1].

Derivation from a local model

The update is the minimizer of a local model of $f$. Approximate $f$ near $x_t$ by its first-order Taylor expansion plus a quadratic proximity penalty that distrusts large steps:

Setting $\nabla \hat f(x) = \nabla f(x_t) + \frac{1}{\eta}(x - x_t) = 0$ gives $x = x_t - \eta\,\nabla f(x_t)$, the gradient step. The step size $\eta$ is the inverse weight on the trust penalty: small $\eta$ trusts the linear model only nearby, large $\eta$ ventures further.

The descent lemma

Progress is guaranteed when the gradient does not change too fast. $f$ is $L$-smooth if its gradient is $L$-Lipschitz, $\lVert \nabla f(x) - \nabla f(y)\rVert \le L\lVert x - y\rVert$, which for twice- differentiable $f$ means $\nabla^2 f \preceq L I$. Smoothness gives a quadratic upper bound:

Descent lemma. Take a gradient step $y = x - \eta\nabla f(x)$ and substitute:

For any step size $0 < \eta < 2/L$ the bracket is positive, so $f(y) < f(x)$ whenever the gradient is nonzero: the objective strictly decreases. The largest guaranteed per-step decrease is at $\eta = 1/L$, giving $f(y) \le f(x) - \frac{1}{2L}\lVert\nabla f(x)\rVert^2$[2].

The step-size tradeoff

The descent lemma makes the tradeoff concrete. Too small an $\eta$ wastes the allowed decrease and crawls. Too large ($\eta \ge 2/L$) breaks the guarantee: the quadratic penalty term dominates and the iterates can oscillate or diverge. On a quadratic with curvature $L$, the threshold $\eta = 2/L$ is exactly where the update starts to amplify the error instead of shrinking it.

Numbers fix the scale. The quadratic in the code block below has Hessian $A$ with rows $(3, 1)$ and $(1, 2)$, whose eigenvalues are $1.382$ and $3.618$, so $L = 3.618$ and the safe range is $0 < \eta < 2/L = 0.553$. Reading the bracket $1 - L\eta/2$ across that range:

• $\eta = 0.05$ (well below the optimum): the step decreases $f$ but barely, throwing away most of the allowed per-step drop.
• $\eta = 1/L = 0.276$: the bracket is $1/2$, the largest guaranteed decrease, clean convergence.
• $\eta = 0.50$ (just under $2/L$): still convergent, but the bracket has shrunk to $0.096$, so each step buys almost nothing and the path oscillates.
• $\eta = 2.5/L = 0.691$: past the threshold, the bracket is negative, and the iterates blow up to infinity.

Check it on arrays

import numpy as np

# Minimize f(x) = 0.5 x^T A x - b^T x, gradient A x - b, minimum at x* = A^{-1} b.
A = np.array([[3.0, 1.0], [1.0, 2.0]])           # symmetric PD
b = np.array([1.0, -1.0])
f = lambda x: 0.5 * x @ A @ x - b @ x
grad = lambda x: A @ x - b
x_star = np.linalg.solve(A, b)

L = np.linalg.eigvalsh(A).max()                  # smoothness = largest eigenvalue
eta = 1.0 / L

x = np.zeros(2)
for t in range(60):
    x = x - eta * grad(x)
print("GD solution:", np.round(x, 6), " exact:", np.round(x_star, 6))

# Monotone decrease at eta = 1/L
x, prev = np.array([5.0, 5.0]), np.inf
decreasing = True
for t in range(50):
    fx = f(x)
    decreasing &= (fx <= prev + 1e-12)
    prev = fx
    x = x - eta * grad(x)
print("monotone decrease at eta=1/L:", decreasing)

# Divergence when eta > 2/L
eta_big = 2.5 / L
x = np.array([5.0, 5.0])
for t in range(40):
    x = x - eta_big * grad(x)
print("eta>2/L diverges:", not np.all(np.isfinite(x)) or np.linalg.norm(x) > 1e6)

Gradient descent at $\eta = 1/L$ converges to the exact minimizer with a monotone decrease, and pushing past $2/L$ diverges, matching the descent lemma.

Exercises

Exercise 1. Derive the gradient-descent update by minimizing the local model $\hat f(x) = f(x_t) + \nabla f(x_t)^\top (x - x_t) + \tfrac{1}{2\eta}\lVert x - x_t\rVert^2$.

Exercise 2. Starting from the descent lemma $f(y) \le f(x) - \eta(1 - \tfrac{L\eta}{2})\lVert\nabla f(x)\rVert^2$, find the step size $\eta$ that maximizes the guaranteed per-step decrease, and state that decrease.

Exercise 3 (code). For the quadratic $f(x) = \tfrac12 x^\top A x - b^\top x$ with $A$ having rows $(3,1)$ and $(1,2)$ and $b = (1, -1)$, scan step sizes across the safe range and verify empirically that the descent lemma bracket $1 - L\eta/2$ predicts whether $f$ keeps decreasing: descent for $\eta < 2/L$, divergence past it.

import numpy as np

A = np.array([[3.0, 1.0], [1.0, 2.0]])
b = np.array([1.0, -1.0])
f = lambda x: 0.5 * x @ A @ x - b @ x
grad = lambda x: A @ x - b
L = np.linalg.eigvalsh(A).max()

def converges(eta, steps=400):
    x = np.array([5.0, 5.0])
    for _ in range(steps):
        x = x - eta * grad(x)
    return np.all(np.isfinite(x)) and np.linalg.norm(x) < 1e6

# Bracket positive (eta < 2/L) predicts descent; negative predicts blow-up.
for eta in [0.05, 1.0 / L, 0.50, 2.5 / L]:
    bracket = 1 - L * eta / 2
    assert converges(eta) == (bracket > 0)
    print(f"eta={eta:.3f}  bracket={bracket:+.3f}  converges={converges(eta)}")

print("2/L threshold =", round(2 / L, 4))

The next lesson quantifies how fast convergence is, using smoothness and strong convexity.