Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 · Gradient Descent

Convergence Rates of Gradient Descent

Learn the O(1/k) guarantee for smooth convex functions, check it numerically, and see why 'rate' means how fast the error shrinks as iterations grow.

"It converges" is not enough. How many iterations will you need to get a given accuracy? A convergence rate answers that question. In this lesson you meet the standard guarantee for gradient descent on smooth convex functions, test it numerically, and learn to read rate statements such as O(1/k).

Setting

Assume f is convex and L-smooth (its gradient is L-Lipschitz), and that a minimizer x* exists with optimal value f*. Run gradient descent with the fixed step t = 1/L. The standard theorem says

Text
f(x_k) - f* ≤ (L · ‖x₀ - x*‖²) / (2k)

Read it like this: the suboptimality f(x_k) - f* falls at least as fast as 1/k. We write O(1/k). To halve the error you need to double the iterations. To reach accuracy ε you need about L‖x₀ - x*‖² / (2ε) steps, so ten times more accuracy costs ten times more work.

The bound depends on two things you can feel: the curvature L (rougher function, slower) and the distance from the start to the optimum (farther start, slower).

Where the bound comes from

A short sketch, with no heavy algebra. Smoothness gives a descent inequality: each step lowers f by at least ‖∇f(x_k)‖²/(2L). Convexity gives f(x_k) - f* ≤ ∇f(x_k)ᵀ(x_k - x*). Combining the two, the distance ‖x_k - x*‖² never increases, and summing the per-step inequalities over k steps telescopes to give the bound. The sketch is enough to remember the shape: smoothness controls progress, convexity links progress to the remaining distance.

Testing the bound numerically

We need a convex function whose gradient is L-smooth. Take f(x) = x₁⁴ + x₂⁴ + x₃⁴, started at (2, -2, 2). Its minimizer is the origin, with f* = 0, and its curvature 12xᵢ² vanishes there, so it is convex but not strongly convex. Gradient descent only moves toward zero here, so the iterates stay in the box [-2, 2]³, where the second derivative is at most 12 · 4 = 48. So L = 48 works for this run, and the starting distance is ‖x₀ - x*‖² = 12. The bound predicts a gap of at most L · 12 / (2k) = 288 / k.

Python Checking the O(1/k) bound

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The measured gap sits below the bound at every checkpoint. The bound is a worst-case guarantee: actual progress is often faster.

A plot on log scales

Plotting the gap against the iteration number on log-log axes turns 1/k into a straight line of slope -1.

Python Error versus iterations

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The measured curve stays below the dashed guarantee line. Because the function is very flat near its minimizer, progress is slow there, which is the situation the O(1/k) bound is made for. When the function also curves upward strongly, as the next lesson explains, convergence becomes much faster.

Reading rate notation

Rate Meaning Iterations for error ε
O(1/√k) slow (nonsmooth subgradient methods) about 1/ε²
O(1/k) gradient descent, smooth convex about 1/ε
O(1/k²) accelerated methods about 1/√ε
O(ρᵏ), ρ < 1 linear ("geometric") about log(1/ε)

Better rates need more structure in f, such as strong convexity, or smarter algorithms such as momentum.

Rates describe worst-case bounds for a class of functions. They do not say your problem converges exactly that fast, and constants such as L and ‖x₀ - x*‖ can be huge.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. For convex L-smooth f with step 1/L, the suboptimality after k steps is at most about

    This is the standard O(1/k) bound.
  2. 2. To reduce the guaranteed error by a factor of 10 under an O(1/k) rate, you need about

    Error ∝ 1/k, so dividing the error by 10 requires multiplying k by 10.
  3. 3. On a log-log plot, an O(1/k) error curve looks like

    log(error) = -log(k) + constant, a line of slope -1.
  4. 4. The bound gets worse when

    Both L and ‖x₀ - x*‖² appear in the numerator.

Summary

  • For convex, L-smooth f and step 1/L, f(x_k) - f* ≤ L‖x₀ - x*‖²/(2k).
  • O(1/k) means ten times more accuracy costs ten times more iterations.
  • Rates are worst-case guarantees; real runs can be faster.
  • More structure (strong convexity) or acceleration improves the rate.

Next: Conditioning and Strong Convexity