Mathematics.

numerical optimization

Gradient Descent and First-Order Methods

Mathematical Optimization60 minDifficulty6 out of 10

You should know: convex functions, gradient

Overview

Gradient descent is an iterative first-order optimisation algorithm that moves in the direction of steepest descent of a function. For convex functions it converges to a global minimum; for non-convex functions it converges to a stationary point. Variants including stochastic gradient descent (SGD), momentum methods, and Nesterov's accelerated gradient are the workhorses of modern machine learning and large-scale optimisation.

Intuition

Gradient descent is like descending a foggy mountain by always stepping in the direction that goes most steeply downhill. The step size (learning rate) controls how far to step each time: too large and you overshoot; too small and convergence is slow. Momentum methods remember recent steps to avoid oscillating in narrow valleys.

Formal Definition

Definition

Given a differentiable function f: ℝⁿ → ℝ, the gradient descent iteration with step size α > 0 is:

x(k+1)=x(k)−α∇f(x(k))x^{(k+1)} = x^{(k)} - \alpha \nabla f(x^{(k)})
Gradient descent update
f(x(k+1))≤f(x(k))−α(1−Lα2)∥∇f(x(k))∥2f(x^{(k+1)}) \le f(x^{(k)}) - \alpha\left(1 - \frac{L\alpha}{2}\right)\|\nabla f(x^{(k)})\|^2
Descent lemma (L-smooth f, α ≤ 1/L)
f(x(k))−f(x∗)≤L∥x(0)−x∗∥22k(rate for smooth convex f)f(x^{(k)}) - f(x^*) \le \frac{L\|x^{(0)} - x^*\|^2}{2k} \quad \text{(rate for smooth convex } f\text{)}
Convergence rate O(1/k)
x(k+1)=x(k)−αk∇f(x(k)),xNesterov(k+1)=y(k)−α∇f(y(k))x^{(k+1)} = x^{(k)} - \alpha_k \nabla f(x^{(k)}),\quad x^{(k+1)}_\text{Nesterov} = y^{(k)} - \alpha \nabla f(y^{(k)})
Nesterov momentum extrapolation step

Notation

NotationMeaning
α,  αk\alpha,\; \alpha_kStep size (learning rate)
LLLipschitz constant of ∇f: ‖∇f(x)-∇f(y)‖ ≤ L‖x-y‖
μ\muStrong convexity constant: f(y) ≥ f(x)+∇f(x)ᵀ(y-x)+μ/2‖y-x‖²
κ=L/μ\kappa = L/\muCondition number — governs convergence rate

Properties

Convergence for smooth convex functions

f(x(k))−f∗≤L∥x(0)−x∗∥22kwith step size α=1/Lf(x^{(k)}) - f^* \le \frac{L\|x^{(0)}-x^*\|^2}{2k} \quad \text{with step size } \alpha = 1/L

Linear convergence for strongly convex functions

∥x(k)−x∗∥2≤(1−μL)k∥x(0)−x∗∥2\|x^{(k)} - x^*\|^2 \le \left(1 - \frac{\mu}{L}\right)^k \|x^{(0)}-x^*\|^2

Nesterov acceleration

f(x(k))−f∗≤2L∥x(0)−x∗∥2(k+1)2(rate O(1/k2))f(x^{(k)}) - f^* \le \frac{2L\|x^{(0)}-x^*\|^2}{(k+1)^2} \quad \text{(rate } O(1/k^2)\text{)}

Worked Examples

  1. 1

    ∇f(x) = 2x.

    ∇f(x)=2x\nabla f(x) = 2x
  2. 2

    x¹ = 4 - 0.3·2·4 = 4 - 2.4 = 1.6.

    x(1)=4−0.3⋅8=1.6x^{(1)} = 4 - 0.3 \cdot 8 = 1.6
  3. 3

    x² = 1.6 - 0.3·3.2 = 1.6 - 0.96 = 0.64.

    x(2)=1.6−0.3⋅3.2=0.64x^{(2)} = 1.6 - 0.3 \cdot 3.2 = 0.64
  4. 4

    x³ = 0.64 - 0.3·1.28 = 0.256.

    x(3)=0.64−0.384=0.256x^{(3)} = 0.64 - 0.384 = 0.256

✓ Answer

After 3 steps: x ≈ 0.256, converging to x* = 0. Each step multiplies error by (1-2α) = 0.4.

Practice Problems

Mediumfree response

Show that for f(x) = (1/2)xᵀQx (Q symmetric PD) gradient descent with α = 1/λ_max(Q) converges linearly with rate (1 - λ_min/λ_max).

Common Mistakes

Common Mistake

Choosing a step size that is too large

If α > 2/L (where L is the Lipschitz constant of ∇f), gradient descent can diverge. The safe choice is α ≤ 1/L.

Quiz

Nesterov's accelerated gradient method achieves convergence rate:

Historical Background

The basic gradient descent idea dates to Cauchy (1847). Nesterov's 1983 accelerated gradient method achieved the optimal convergence rate O(1/k²) for smooth convex functions, matching an information-theoretic lower bound. Stochastic gradient descent, popularised by Robbins and Monro (1951) and rediscovered for neural networks in the 1980s-90s, now drives deep learning.

  1. 1847

    Cauchy proposes gradient descent (the 'method of steepest descent')

    Augustin-Louis Cauchy

  2. 1951

    Robbins-Monro stochastic approximation framework

    Herbert Robbins, Sutton Monro

  3. 1983

    Nesterov's accelerated gradient method with O(1/k²) rate

    Yurii Nesterov

Summary

  • Gradient descent: x^(k+1) = x^(k) - α∇f(x^(k)); step toward steepest descent.
  • For L-smooth convex f with α=1/L: convergence rate O(1/k) in function value.
  • For strongly convex f: linear (geometric) convergence rate 1-μ/L per step.
  • Nesterov acceleration achieves optimal O(1/k²) rate via momentum extrapolation.

References

  1. BookBoyd, S. and Vandenberghe, L. — Convex Optimization (2004), Chapter 9. Free at https://web.stanford.edu/~boyd/cvxbook/
  2. BookNesterov, Y. — Introductory Lectures on Stochastic Optimization (2004), Springer
  3. WebsiteWikipedia — Gradient descent