Optimization Landscape Marble Race (3D): Gradient Descent, Momentum, Adam and Newton on a Display Table

Setting up the display table...

Presets

Live readouts

Graphs

Error f(x_k) - f* against iteration (log scale): how fast each method converges

Gradient norm |grad f| against iteration (log scale)

Distance to the nearest true minimum against iteration (log scale)

Numerical checks

running...

How to use

The same race on a real-looking landscape: steel marbles roll down a height field standing on a round display table. Height is drawn on a logarithmic scale of the error. Drag to orbit, wheel to zoom, tap the surface to plant the start flag. Use the camera buttons for top, low and side views, and the controls to change the step sizes, the momentum or the noise.

The science

The problem. Find the point that minimises a function f(x, y) using only local information: its value, its gradient g = grad f and, for Newton, its Hessian matrix H of second derivatives.

Gradient descent. x_{k+1} = x_k - lr * g(x_k) On a quadratic f = (x^2 + kappa y^2) / 2 every coordinate shrinks by a fixed factor: y_k = (1 - lr*kappa)^k y_0. It converges only if lr < 2 / L, where L is the largest curvature, and the best fixed step lr = 2 / (L + mu) gives the contraction factor (kappa - 1) / (kappa + 1), with kappa = L / mu the condition number. A stretched bowl (large kappa) is therefore slow: the page checks that rate.

Momentum (heavy ball) and Nesterov. v_{k+1} = beta v_k - lr g(x_k), x_{k+1} = x_k + v_{k+1} The velocity averages past gradients, so the zig-zag across a narrow valley cancels while progress along it adds up. With the optimal tuning the quadratic rate improves from (kappa-1)/(kappa+1) to about (sqrt(kappa)-1)/(sqrt(kappa)+1) per step, which the page measures. Nesterov evaluates the gradient at the look-ahead point x + beta v.

RMSprop and Adam. Each coordinate gets its own step size, divided by a running estimate of its gradient magnitude: m = b1 m + (1-b1) g, s = b2 s + (1-b2) g^2, x -= lr * (m/(1-b1^k)) / (sqrt(s/(1-b2^k)) + eps) This is why they cope with badly scaled problems and noisy gradients, but their paths are not straight and their final accuracy is limited by lr.

Newton. x_{k+1} = x_k - (H + lambda I)^(-1) g(x_k) Newton models f as a quadratic and jumps to its minimum, so a true quadratic is solved in one step whatever the condition number (checked in the page). Far from a minimum the Hessian can be indefinite (a saddle), so the page shifts it until it is positive definite; that keeps the step a descent direction. Each step is more expensive in high dimension because H is a d x d matrix.

Noise. The noise slider adds Gaussian noise of standard deviation sigma to each gradient, a crude model of stochastic gradient descent on mini-batches. A constant step then settles in a noise ball instead of at the exact minimum.

Honest simplifications. (1) Two variables only; real problems have millions, where the Hessian is usually not formed. (2) No line search or trust region; step sizes are fixed so that the effect of the step size stays visible. (3) The Hessian shift is a simple heuristic, not a full Levenberg-Marquardt scheme. (4) The 3-D height is drawn on a logarithmic scale so that the valley floor stays visible.

Checks run in the page. (a) gradient descent on a bowl against the closed form (1 - lr kappa)^k; (b) Newton lands on the minimum of a quadratic in one step; (c) analytic gradients against central finite differences on 80 random points of four functions; (d) the optimal-step contraction (kappa-1)/(kappa+1); (e) the heavy-ball rate sqrt(beta).