Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 · Gradient Descent

Step Size and Line Search

See what happens with steps too small or too large, learn the safe step 1/L, and implement backtracking line search with the Armijo condition in Python.

The step size t decides whether gradient descent crawls, flies or explodes. Too small and you waste thousands of iterations. Too large and the iterates overshoot the valley and diverge. This lesson shows each behavior, derives a safe choice and builds an automatic method, backtracking line search, that needs no tuning by hand.

Three behaviors on a simple bowl

Take f(x) = x², with gradient 2x. The update is x ← x - t·2x = (1 - 2t)x. So each step multiplies x by (1 - 2t).

  • If 0 < t < 1, then |1 - 2t| < 1 and x shrinks to 0: convergence.
  • If t = 1, the factor is -1: x flips sign forever and never improves.
  • If t > 1, the factor has magnitude above 1: divergence.
Python Small, good and huge steps

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.

Notice t = 0.5 lands on zero in one step (the factor is exactly 0), t = 0.01 has barely moved after 30 steps, and t = 1.1 has grown.

A safe step: 1/L

For general functions the right limit depends on how fast the gradient can change. A function has an L-Lipschitz gradient (we say it is L-smooth) if

Text
‖∇f(x) - ∇f(y)‖ ≤ L‖x - y‖    for all x, y

For a twice-differentiable f, L is the largest eigenvalue of the Hessian over the domain. For x², f'' = 2, so L = 2. The classic safe choice is t = 1/L. With it, each step guarantees

Text
f(x_{k+1}) ≤ f(x_k) - (1/(2L)) ‖∇f(x_k)‖²

so the objective always decreases. Steps up to t < 2/L still converge for convex quadratics, which matches the experiment above (2/L = 1).

For least squares with f(θ) = (1/2n)‖Aθ - y‖², the Hessian is AᵀA/n, so L is its largest eigenvalue.

Python Computing L for least squares

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 estimate should be close to [1, -2, 0.5, 3, 0], the coefficients used to make the data.

Often you do not know L, or the function is not quadratic. Backtracking finds a good step each iteration by trying a big step and shrinking it until it makes enough progress. "Enough" is the Armijo condition:

Text
f(x - t∇f(x)) ≤ f(x) - α · t · ‖∇f(x)‖²

with a small constant α such as 0.3 (the common range is 0 to 0.5). The predicted drop from the tangent line is t‖∇f‖²; Armijo asks for at least a fraction α of it. Start with t = 1; while the condition fails, set t ← β·t with β such as 0.5.

Python Backtracking line search

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.

Both reach the origin. Backtracking adapts the step as the iterates move, and it works even when L is unknown; the fixed step is simple but depends on a correct L.

For quadratics, the best step along the gradient can be computed exactly. For f(x) = ½xᵀQx - bᵀx with gradient g, minimizing f(x - tg) over t gives

Text
t = (gᵀg) / (gᵀQg)

This "steepest descent with exact line search" never overshoots, yet it still zigzags on badly scaled problems.

Python Exact line search on a quadratic

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.

In machine learning, a learning-rate schedule (large at first, smaller later) plays the role of line search when evaluating the full objective is too costly.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. For f(x) = x² and gradient descent with step t, the iterates multiply by

    x_new = x - t·2x = (1 - 2t)x.
  2. 2. If f is L-smooth, a safe fixed step size is

    With t = 1/L every step decreases f by at least ‖∇f‖²/(2L).
  3. 3. In backtracking, if the Armijo condition fails you

    Shrinking the step eventually satisfies the condition because small steps follow the tangent line well.
  4. 4. For a convex quadratic, L equals

    L bounds how fast the gradient can change, which is the largest curvature.

Summary

  • A step that is too small is slow; too large can diverge (for quadratics, t < 2/L converges).
  • t = 1/L is a safe fixed step for L-smooth functions.
  • Backtracking line search shrinks the step until the Armijo condition holds and needs no knowledge of L.
  • For quadratics, the exact best step along the gradient is gᵀg / gᵀQg.

Next: Convergence Rates of Gradient Descent