Interactive demo · Foundations of Deep Learning · Chapter 7

Step size versus condition number

Near a minimum the error is a quadratic, E = ½(λminα12 + λmaxα22) in the eigen-coordinates αi = uiT(w − w*) of the Hessian (7.11). Gradient descent multiplies αi by 1 − ηλi at every step (7.27). Here λmax = 1 and λmin = 1/κ, so the condition number κ sets how elongated the bowl is. Watch which direction limits the step size and which one limits the speed.

Method

Condition number κ = λmax/λmin

Learning rate η (λmax = 1)

Momentum μ

Steps

Set the parameters

Try these

Heavy ball is momentum (7.31): αt+1 = (1 + μ − ηλ)αt − μαt−1. Nesterov (7.34): αt+1 = (1 + μ)(1 − ηλ)αt − μ(1 − ηλ)αt−1. Their contraction per step is the larger modulus of the roots of the matching quadratic; the dashed grey line in the lower panel is gradient descent with its best fixed step, for comparison. Start: α = (1, 1).

In the lecture notes