Gradient Descent Rate Explained with Worked Examples

For a function that is -strongly convex with -Lipschitz gradient, gradient descent with step satisfies .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Gradient descent rate (strongly convex) means

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.

What is it used for?

The rate of gradient descent is set by the condition number: the more elongated the valley, the slower the progress.

How to use gradient descent rate (strongly convex)

  1. Find and (the smallest and largest eigenvalues of the Hessian for a quadratic).
  2. Compute the factor .
  3. The error after steps is at most factor times the initial error.
  4. Solve factor to find the number of steps.

Graph

Bounds 0.9^k (κ = 10) and 0.99^k (κ = 100) on the remaining errork = 10: 0.349010203040506000.20.40.60.81Bounds 0.9^k (κ = 10) and 0.99^k (κ = 100) on the remaining erroriterations kerror factorcondition number 10condition number 100Graph with x from 0 to 60 and y from 0 to 1.05. Shows the curve condition number 10; the curve condition number 100; point k = 10: 0.349 at (10, 0.3487).

The badly conditioned problem decays far more slowly than the well-conditioned one.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: the factor

For , find the contraction factor and the bound after 10 steps.

Worked example
Answer
0.9, 0.34870.9,\ 0.3487
  1. μ and L
  2. Factor
  3. After 10 steps

Example 2: steps for 10⁻⁶

How many steps guarantee an error reduction of with factor 0.9?

Worked example
Answer
132132
  1. Inequality
  2. Solve

Example 3: a worse condition number

With the factor is 0.99. How many steps reduce the error by ?

Worked example
Answer
13751375
  1. Solve
  2. Evaluate

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

μ = 1, L = 4

factor 1 − μ/L

0.75.

k = 3

bound

0.4219.

k = 5

bound

0.2373.

μ/L = 0.1

factor

0.9.

Word problems

With step 1/L, f(x_k) − f* ≤ (1 − μ/L)ᵏ (f(x₀) − f*). A larger condition number L/μ means slower convergence.

Factor

μ = 1, L = 4.

  1. 1 − 0.25
  2. Check: ✓0.75

k = 3

0.75³.

  1. 0.4219
  2. Check: ✓0.4219

k = 5 Higher

0.75⁵.

  1. 0.2373
  2. Check: ✓0.2373

Ill-conditioned Higher

μ/L = 0.1.

  1. 1 − 0.1
  2. Check: ✓0.9

Common mistakes

Factor μ/L

μ/L ✗

1 − μ/L ✓

Remaining error.

Step size 1/μ

μ ✗

1/L ✓

Safe step.

Faster for ill-conditioned

faster ✗

slower ✓

Large L/μ.

Works without convexity

always ✗

needs strong convexity ✓

Condition.

Exam tips

  1. Factor 1 − μ/L.
  2. Step 1/L.
  3. Condition number L/μ.
  4. Linear convergence.
  5. Take k steps.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Factor for μ = 2, L = 8 Foundation

0.75

2. Bound after 2 steps for factor 0.5 Foundation

0.25

3. Factor for μ = 1, L = 100 Foundation

0.99

4. Bound after 4 steps, factor 0.9, 4 dp Higher

0.6561

5. Factor for μ = 3, L = 6 Higher

0.5

6. Bound after 3 steps, factor 0.8 Higher

0.512

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Strong convexity (μ)
Curvature lower bound.
Lipschitz gradient (L)
Curvature upper bound.
Linear rate
Geometric decrease.
Condition number
L/μ.
Step size
1/L.
Optimality gap
f(x) − f*.

Frequently asked questions

What is the rate of gradient descent?

(1 − μ/L)ᵏ for step 1/L.

Why is a large condition number bad?

The factor is close to 1.

What step size is used?

1/L.

What type of convergence?

Linear (geometric).

Which page covers the condition number?

condition number.

Which page covers conjugate gradient?

conjugate gradient step.

More in Numerical methods and optimisation and the formula sheets.