Interactive demo · Probabilistic Machine Learning · Chapter 8

Line search, Newton, BFGS and trust regions

Six ways to choose the next step on a function of two variables. Gradient descent needs a step size: a constant one (too small is slow, too large oscillates), Armijo backtracking (8.27), or for a quadratic the exact line search (8.26), which zig-zags when the condition number is large. Newton's method (Algorithm 8.1) rescales the gradient by the inverse Hessian and converges in a few steps near a minimum, but it is attracted to any stationary point, saddles included; Tikhonov damping (8.52) and trust regions (8.49) repair that. BFGS (8.44)–(8.48) builds a Hessian approximation from gradients alone. Click the contour plot to move the starting point.

Function

Condition number κ

Methods

Constant step η (gradient descent)

Damping λ (Newton) and radius r (trust region)

Iterations

Try these

Armijo backtracking starts from η = 1 and halves it until (8.27) holds with c = 10−4. BFGS starts from the identity, uses the same backtracking, and updates the inverse Hessian by (8.48) only when yTs > 0. The trust-region method solves the subproblem in the ball exactly through the eigenvalues of the Hessian, shrinks the radius by 4 when the actual decrease is less than a quarter of the predicted one, doubles it (up to r) when the model is good, and rejects steps whose ratio is below 0.1. Exact line search is available for the quadratic only.

In the lecture notes