Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 38 · Gradient Descent

Conditioning and Strong Convexity

Understand strong convexity, the condition number L/μ and why ill-conditioned problems make gradient descent slow. Includes linear convergence experiments.

The O(1/k) rate from the previous lesson is a worst case. When the function curves upward by at least a certain amount everywhere, gradient descent becomes dramatically faster: the error shrinks by a constant factor each step. This lesson explains that extra structure, strong convexity, and the number that controls the speed, the condition number.

Strong convexity

A differentiable function f is μ-strongly convex (μ > 0) if for all x, y

Text
f(y) ≥ f(x) + ∇f(x)ᵀ(y - x) + (μ/2)‖y - x‖²

Plain convexity says the graph lies above its tangent. Strong convexity says it lies above a tangent plus a parabola: the function curves up at least as much as (μ/2)‖·‖². For twice-differentiable f, it means all Hessian eigenvalues are at least μ.

Together with L-smoothness (all eigenvalues at most L), a quadratic f(x) = ½xᵀQx has μ = λ_min(Q) and L = λ_max(Q). Strong convexity guarantees a unique minimizer.

The condition number

Text
κ = L / μ  ≥ 1

The condition number measures how stretched the bowl is. κ = 1 is a perfectly round bowl. Large κ is a long narrow canyon: steep across, almost flat along.

With step t = 1/L, gradient descent on a μ-strongly convex, L-smooth function satisfies

Text
‖x_k - x*‖² ≤ (1 - μ/L)^k · ‖x₀ - x*‖²

This is linear convergence (also called geometric): the error is multiplied by at most 1 - 1/κ per iteration. Number of iterations to reach accuracy ε is about κ · ln(1/ε). Doubling the accuracy needs only a constant number of extra steps, but a large κ multiplies the whole cost.

Experiment: round versus stretched

Python Iterations versus condition number

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 iteration count grows roughly in proportion to κ, as the theory says. At κ = 1 the first step lands on the minimum.

Linear convergence on a plot

On a semi-log plot (log error versus iteration) linear convergence is a straight line, and its slope depends on κ.

Python Straight lines on a semi-log plot

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 larger κ, the flatter the line, meaning the slower the convergence.

Why conditioning hurts

With one step size for all directions, t must be small enough for the stiffest direction (curvature L), otherwise that direction oscillates and diverges. But then the flattest direction (curvature μ) moves only a fraction μ/L of the way each step. The method is held hostage by the stiffest direction.

Fixes: scaling and preconditioning

If you know the curvature, you can rescale variables so the bowl is rounder. Changing variables x = Dz with a diagonal D turns Q into DQD. If the diagonal of Q varies widely, choosing D = diag(1/√Qᵢᵢ) makes the new diagonal all ones. This is the idea of preconditioning: multiply the gradient by a matrix P ≈ Q⁻¹ so the effective problem has κ near 1. Newton's method is the extreme case, using P = ∇²f⁻¹, which solves a quadratic in one step.

Python Diagonal preconditioning

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.

Plain gradient descent is still far from zero after 100 steps, because the flat direction moves 1% per step. The preconditioned run reaches essentially zero, and Newton's method solves the quadratic in a single step.

In deep learning, adaptive methods such as Adam and RMSProp act as cheap diagonal preconditioners: they rescale each coordinate by its recent gradient size.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A μ-strongly convex function has Hessian eigenvalues that are

    Strong convexity is a lower bound on the curvature in every direction.
  2. 2. The condition number of a quadratic ½xᵀQx is

    κ = L/μ is the ratio of the largest to the smallest curvature.
  3. 3. With step 1/L, the number of iterations for accuracy ε grows like

    Each step shrinks the error by a factor (1 - 1/κ), giving linear convergence.
  4. 4. Preconditioning aims to

    Multiplying the gradient by an approximate inverse Hessian makes the landscape rounder.

Summary

  • μ-strong convexity means curvature is at least μ everywhere; it gives a unique minimizer and linear convergence.
  • The condition number κ = L/μ measures how stretched the problem is.
  • Gradient descent needs about κ ln(1/ε) iterations; large κ means slow progress and zigzag.
  • Scaling and preconditioning reduce κ; Newton's method removes it for quadratics.

Next: Momentum and Accelerated Gradient