Gradient descent

Walking downhill

Imagine you're on a hillside in thick fog and you want the bottom of the valley. You can't see it, but you can feel which way the ground tilts under your feet. So you take a step downhill, and then another. For a function f(x, y) the direction of steepest climb is the gradient \nabla f = \langle f_x, f_y \rangle, so the direction of steepest descent is -\nabla f, and gradient descent repeats one rule [1]:

\mathbf{x}_{k+1} = \mathbf{x}_k - \eta\,\nabla f(\mathbf{x}_k) .

The number \eta is the step size, which machine learning calls the learning rate. As you near the bottom the ground flattens, \nabla f shrinks and your steps shrink with it. The lab finds the gradient by central differences, f_x \approx \frac{f(x + h, y) - f(x - h, y)}{2h}, so it works on any function you type.

How large a step

Take tiny steps and you'll be walking all day. Take huge ones and you leap right over the bottom. A quadratic tells you exactly where the line is. For f = x^2 + 10y^2 the gradient is \langle 2x, 20y \rangle, so each step multiplies x by 1 - 2\eta and y by 1 - 20\eta. Both factors must lie between -1 and 1, which needs \eta < 0.1. Just under that, the y factor is close to -1, so the ball overshoots the valley floor on every step and bounces from wall to wall as it slowly closes in. Just over it, each bounce is bigger than the last, and the ball gets flung out.

The deeper trouble is the condition number, the ratio of the steepest curvature to the shallowest, here 20/2 = 10. Your step has to be small enough for the steep direction, which makes it tiny for the shallow one, so the number of steps grows in proportion to the condition number [1]. Long, narrow valleys are slow going.

Momentum

Real balls don't stop dead after each step. Polyak's heavy ball method gives yours a velocity that remembers where it's been [2]:

\mathbf{v}_{k+1} = \beta\,\mathbf{v}_k - \eta\,\nabla f(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{v}_{k+1} .

With \beta between 0 and 1, the pushes across the valley flip sign each time and mostly cancel, while the pushes along the floor all point the same way and add up. On the narrow valley, at the same small step, momentum gets there in about a fifth of the steps.

Newton's method

Gradient descent only feels the slope. Newton's method also feels the curvature, through the Hessian matrix H of second derivatives, and jumps straight to the bottom of the quadratic that matches f where you stand [1]:

\mathbf{x}_{k+1} = \mathbf{x}_k - H^{-1}\,\nabla f(\mathbf{x}_k) .

On a quadratic that's the exact answer, in one step, whatever the condition number. Near a minimum it converges quadratically, roughly doubling the number of correct digits each step, and you'll see the log plot plunge faster and faster. There's a price. The Hessian is expensive in many variables, and Newton's method has a blind spot: it solves \nabla f = 0, so it heads for whatever critical point is nearest, a saddle or a maximum as happily as a minimum.

Rosenbrock's valley

In 1960 Rosenbrock built f = (1 - x)^2 + 100(y - x^2)^2 as a test that's easy to write down and hard to minimise [3]. Its minimum, f = 0 at (1, 1), sits at the end of a long, curved valley with an almost flat floor. Descent drops into the valley in a few steps and then crawls, because the curvature across the valley is a hundred times the curvature along it. More than sixty years on, it's still a standard benchmark for optimisation methods.

Things to try in the lab

• Downhill in a round bowl: the easy case, every step aimed at the centre.
• Zigzag down a narrow valley and One step too far: the same valley at \eta = 0.09 and \eta = 0.11, either side of the limit 0.1.
• Crawling with a safe step and Momentum rolls through: the same small step without and with momentum, 388 steps against 76.
• Rosenbrock's banana: drop in at once, then creep along the floor; watch the log plot flatten.
• Race the three methods: the three balls from one start on Rosenbrock's valley.
• Newton lands on the saddle: then switch the method to gradient descent and watch it roll off instead.
• Which valley you reach: drag the start between Himmelblau's four basins and see which minimum each start leads to.
• Type your own surface, such as x^4 + y^4 - 4xy, with two minima and a saddle between them, and compare where each method goes.

Reading the instruments

Steps taken counts iterations. |∇f| is the length of the gradient at the first ball. It falls to zero at any critical point, and the log plot shows how fast. f at the ball is the height. A ring marks the start, and you can drag it. Small circles mark the known minima of the preset surfaces.

References

[1] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. (Springer, 2006), chapters 2 and 3 on steepest descent, step lengths and Newton's method. DOI: 10.1007/978-0-387-40065-5

[2] B. T. Polyak, "Some methods of speeding up the convergence of iteration methods," USSR Computational Mathematics and Mathematical Physics 4, 1-17 (1964). DOI: 10.1016/0041-5553(64)90137-5

[3] H. H. Rosenbrock, "An automatic method for finding the greatest or least value of a function," The Computer Journal 3, 175-184 (1960). DOI: 10.1093/comjnl/3.3.175