Gradient descent · Calculus × Computing

What is it?

Repeat $\theta \leftarrow \theta - \eta\,\nabla L(\theta)$ : take a small step against the gradient. Cauchy proposed it in 1847; today it (and its stochastic, adaptive variants) trains essentially every neural network.

Why does it exist?

Setting $\nabla L = 0$ and solving is impossible for a network with millions of parameters and a non-linear loss. But evaluating $\nabla L$ at one point is cheap (backpropagation), and the gradient says which direction decreases the loss fastest. Iterate.

Intuition

A ball rolling downhill in fog, one step at a time. The learning rate $\eta$ is the step length: too small and it crawls; too large and it overshoots, bouncing between valley walls or flying off. In a narrow valley the gradient points across the valley rather than along it, so the path zigzags — try the elongated bowl in the demo.

Formal definition

\theta_{k+1} = \theta_k - \eta\,\nabla L(\theta_k).

If $\nabla L$ is $L$ -Lipschitz and $\eta \le 1/L$ , then $L(\theta_{k+1}) \le L(\theta_k) - \frac\eta2\norm{\nabla L(\theta_k)}^2$ (descent lemma): the loss decreases at every step and $\min_{j\le k}\norm{\nabla L(\theta_j)}^2 = O(1/k)$ . If $L$ is $\mu$ -strongly convex, convergence is linear with rate $1 - \mu/L$ .

Formulas

$\theta_{k+1} = \theta_k - \eta\,\nabla L(\theta_k)$; $L(\theta - \eta g) \approx L(\theta) - \eta\,\norm{g}^2 \quad (g = \nabla L)$
why it works: first-order Taylor

How is it computed?

θ = initial guess
for k in 1..K:
    g = ∇L(θ)          # backpropagation
    θ = θ − η · g
    if ‖g‖ < tol: break

Interactive visualization

f(x, y)optimizerη

Click anywhere to drop the ball there. Colour is height (log scale), lines are level curves; the gradient is perpendicular to them. Try the narrow valley with plain gradient descent, then with momentum.

Why does it matter?

It is the inner loop of the AI industry: trillions of gradient steps per day. Every optimizer used in practice (SGD, momentum, Adam) is a modification of this one line.

The mathematics behind it

Derivative★★★★★fundamental
Each step moves the parameter against the derivative of the loss: $w \leftarrow w - \eta\,L'(w)$ .
Gradient★★★★★fundamental
The update $\theta \leftarrow \theta - \eta\nabla L(\theta)$ is the gradient, used as a direction.
Lipschitz continuity★★★★★fundamental
The safe learning rate is set by the Lipschitz constant of the gradient: $\eta < 2/L$ .
Convergence of sequences★★★★★frequent
Convergence theorems guarantee $f(x_k) \to f^\ast$ under conditions on the step size.
Critical points and derivative tests★★★★★fundamental
Gradient descent stops where the derivative vanishes — at a critical point.
Order of convergence★★★★★frequent
On strongly convex problems GD converges linearly, at a rate set by the condition number $L/\mu$ .
Taylor polynomial★★★★★fundamental
The first-order model $f(x - \eta g) \approx f(x) - \eta\norm g^2$ is why a small step downhill decreases $f$ .
Directional derivative★★★★★fundamental
Among unit steps, $u = -\nabla f/\norm{\nabla f}$ minimizes $D_u f$ : the justification of the method.
Euler's method★★★★★advanced
GD is explicit Euler on $\dot\theta = -\nabla L$ ; the learning rate is the time step and inherits its stability limit.
Equilibria and stability★★★★★advanced
Strict minima are stable fixed points of GD exactly when $\eta < 2/\lambda_{\max}(H)$ .
Monotone and bounded sequences★★★★★frequent
With a small enough step the loss decreases monotonically and is bounded below, so the loss values converge.
Mean value theorem★★★★★advanced
Convergence proofs bound the decrease per step with the MVT applied to the gradient.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

ℒ AI and machine learning

Learning rate★★★★★
Backpropagation★★★★★
Stochastic gradient descent (SGD)★★★★★
Loss landscape★★★★★
Reinforcement learning★★★★★
Second-order (Hessian-based) optimization★★★★★
+5

⇄ Optimization and systems

Recommender systems★★★★★

What depends on it

Exercises

1AI

For $L(\theta) = \frac a2\theta^2$ , show that GD converges iff $0 < \eta < 2/a$ . What happens at $\eta = 1/a$ ?

Solution

$\theta_{k+1} = (1 - \eta a)\theta_k$ , which tends to 0 iff $|1 - \eta a| < 1$ . With $\eta = 1/a$ it jumps to the minimum in one step.