Lecture 23: Accelerating Gradient Descent (Use Momentum)

What this lecture covers

Building on the previous lecture's analysis of plain steepest descent, this lecture shows how adding a momentum term speeds up convergence. Strang works through the algebra of momentum-based gradient descent by tracking each eigenvector of the Hessian separately, reducing the problem to a small matrix whose eigenvalues control the convergence rate, then optimizes the step size and momentum coefficient to minimize that rate. The lecture closes with a brief look at Nesterov's alternative acceleration method.

This is the third lecture in the optimization sequence, following plain steepest descent's zigzag behavior on elongated level sets. After watching, you should be able to explain why momentum reduces the zigzag problem, state how the accelerated convergence rate compares to plain gradient descent's, and describe the eigenvector-tracking technique used to analyze both.

Key ideas

• Momentum term: gradient descent is modified by adding a memory of the previous step, z_k = gradient(f)(x_k) + beta * z_{k-1}, with x_{k+1} = x_k - s * z_k; this is described as modeling a heavy ball that carries momentum through a valley instead of bouncing perpendicular to each level set.
• Second-order structure: adding momentum turns the update into a three-level recursion (depending on steps k-1, k, k+1), analogous to going from a first-order to a second-order differential equation, with the momentum term acting like a damping coefficient.
• Eigenvector tracking: because the underlying matrix S is symmetric positive definite, the coupled update can be analyzed one eigenvector at a time, reducing the vector recursion to a 2x2 matrix R acting on scalar coefficients for each eigenvalue lambda.
• Optimized step size and momentum: choosing s = 2 / (sqrt(M) + sqrt(m))^2 and beta = ((sqrt(M) - sqrt(m)) / (sqrt(M) + sqrt(m)))^2, where M and m are the largest and smallest eigenvalues of S, minimizes the worst-case eigenvalue of R.
• Improved convergence rate: with optimized momentum, the convergence factor becomes (1 - sqrt(B)) / (1 + sqrt(B)), compared to (1 - B) / (1 + B) for plain gradient descent, a substantial improvement when the condition number 1/B is large.
• Condition number: the ratio lambda_max / lambda_min of the Hessian's eigenvalues (called kappa) continues to govern difficulty; momentum reduces its effective impact by working with its square root instead.
• Nesterov's method: an alternative acceleration approach that evaluates the gradient at a shifted point x_k + gamma(x_k - x_{k-1}) rather than at x_k itself, analyzed with the same eigenvector technique and achieving a comparable convergence factor.

Walkthrough

Reviewing the zigzag problem (1:02)

Strang revisits the level-set picture from the previous lecture: steepest descent on long, thin elliptical level sets zigzags back and forth, converging at a rate governed by (1 - B)/(1 + B). This motivates the need for an improvement.

Introducing the momentum term (9:11)

Momentum is introduced by defining a new search direction z_k that combines the current gradient with a multiple beta of the previous search direction, giving the update some memory of where it has been moving, likened to a heavy ball rolling down a valley instead of bouncing between its walls.

Reducing to a second-order system and tracking eigenvectors (16:15)

Since the momentum update depends on three time levels, Strang rewrites it as two coupled first-order equations, analogous to converting a second-order differential equation into a system of first-order ones. Assuming x_k and z_k stay aligned with a single eigenvector Q of S, the vector recursion reduces to a 2x2 matrix R acting on scalar coefficients, with R depending on the eigenvalue lambda, the step size s, and beta.

Optimizing step size and momentum (28:28)

The task becomes choosing s and beta to minimize the largest eigenvalue of R, over the whole range of eigenvalues lambda between m and M. Strang presents the resulting optimal choices for s and beta and shows the best achievable convergence factor is (1 - sqrt(B))/(1 + sqrt(B)) in the example problem, a clear improvement over the non-momentum rate.

Nesterov's alternative acceleration (44:42)

Strang briefly presents Nesterov's method, which evaluates the gradient at a shifted point involving both x_k and x_{k-1} rather than at x_k directly. Though the details differ, the same eigenvector-based analysis applies, and it achieves a similarly improved convergence factor.

Before you watch

• Watch the previous lecture on gradient descent, since this lecture builds directly on its zigzag analysis and the ratio (1 - B)/(1 + B).
• Review eigenvectors and eigenvalues of symmetric matrices, since the entire analysis relies on tracking them individually.

Check your understanding

1. Why does adding a momentum term turn the gradient descent recursion into a second-order system?
2. How does tracking a single eigenvector reduce the momentum update to a 2x2 matrix problem?
3. Why does the optimized convergence factor with momentum depend on sqrt(B) rather than B itself, and why is that an improvement?
4. What is the key difference between how momentum and Nesterov's method modify the basic gradient descent update?