Gradient descent

Walking downhill

Gradient descent repeats one move: step against the gradient, $\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$. The number $\eta>0$ is the step size, often called the learning rate. A small $\eta$ is safe but slow. A large $\eta$ overshoots the valley and the iterates can bounce further away each time.

On the simplest bowl the update multiplies $w$ by $1-\eta a$ each time, so the iterates shrink to zero exactly when $|1-\eta a|<1$, that is when $\eta<2/a$. The choice $\eta=1/a$ lands on the minimum in one step, and any $\eta$ between $1/a$ and $2/a$ still converges but alternates sign on the way. Beyond $2/a$ the factor has size above one and the iterates explode.

In several variables the curvature differs by direction. The largest Hessian eigenvalue $L$ caps the usable step ($\eta<2/L$) and the smallest $\mu$ sets how slowly the flattest direction is crossed. Their ratio $\kappa=L/\mu$ is the condition number. With the best fixed step $\eta=2/(L+\mu)$ the error shrinks by about the factor $(\kappa-1)/(\kappa+1)$ per step, so a large $\kappa$ means a factor close to one and a slow zig-zag down a long narrow valley. For the covariance matrix of twelve large US stocks since 2010, $\kappa$ is about $33$: the factor is $0.941$ and cutting the error 100-fold takes about 76 steps.

• Safe step: $\eta<2/L$, where $L$ is the largest Hessian eigenvalue; otherwise the iterates diverge.
• Speed: set by the condition number $\kappa=L/\mu$; the larger it is, the slower the descent.
• Stopping: stop when $\lVert\nabla f\rVert$ is below a tolerance, with a cap on the number of iterations.

Lab · what's graded

• The first step15 pts
• The second step10 pts
• The largest stable step15 pts
• A step that is too big15 pts
• A condition number15 pts
• The best contraction factor15 pts
• Why ill-conditioning is slow15 pts