μ = 1, L = 4
factor 1 − μ/L
0.75.
For a function that is -strongly convex with -Lipschitz gradient, gradient descent with step satisfies .
This page is easier if you are comfortable with:
The error shrinks by at least the factor per step, where is the condition number. Take with : , , factor . From , , and one step with size gives , , a decrease by 0.0736, much better than the guaranteed 0.9. The basic method is in gradient descent.
The factor tells you how many steps are needed. To reduce the error by with factor 0.9 needs , so 132 steps. With the factor is 0.99 and about 1375 steps are needed. A badly conditioned problem therefore converges slowly: the iterates zig-zag across a narrow valley; see the conjugate gradient step for a faster remedy.
The proof combines convexity (convex functions) with the descent inequality. Compare with the linear convergence of fixed-point iteration, where the factor is , and the much faster quadratic convergence of Newton's method. The logarithm used is described in the definition of a logarithm.
The rate of gradient descent is set by the condition number: the more elongated the valley, the slower the progress.
The badly conditioned problem decays far more slowly than the well-conditioned one.
These examples are worked by hand, step by step, so you can compare your own working.
For , find the contraction factor and the bound after 10 steps.
How many steps guarantee an error reduction of with factor 0.9?
With the factor is 0.99. How many steps reduce the error by ?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
factor 1 − μ/L
0.75.
bound
0.4219.
bound
0.2373.
factor
0.9.
With step 1/L, f(x_k) − f* ≤ (1 − μ/L)ᵏ (f(x₀) − f*). A larger condition number L/μ means slower convergence.
μ = 1, L = 4.
0.75³.
0.75⁵.
μ/L = 0.1.
μ/L ✗
1 − μ/L ✓
Remaining error.
μ ✗
1/L ✓
Safe step.
faster ✗
slower ✓
Large L/μ.
always ✗
needs strong convexity ✓
Condition.
Try each one on paper, then open the answer. Use the solver above to see the full working.
0.75
0.25
0.99
0.6561
0.5
0.512
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
(1 − μ/L)ᵏ for step 1/L.
The factor is close to 1.
1/L.
Linear (geometric).
condition number.
conjugate gradient step.
More in Numerical methods and optimisation and the formula sheets.