Lecture 22: Gradient Descent - Downhill to a Minimum

What this lecture covers

This lecture develops gradient descent, the central optimization algorithm behind deep learning, by working through a fully solvable example: minimizing a quadratic x1^2 + B x2^2. Because the example has an exact closed-form solution, it lets you see precisely how fast steepest descent converges and why. Along the way Strang reviews the gradient and Hessian, connects the Hessian to convexity, works a full example of minimizing a general quadratic 1/2 x^T S x - a^T x, and touches on the convex log-determinant function.

This is the second lecture in the optimization unit, following the introduction of Newton's method and convexity. After watching, you should be able to compute the gradient and minimizer of a quadratic function, explain what arg min means, and describe why the condition number of the Hessian controls how quickly gradient descent converges.

Key ideas

• Condition number: for a symmetric matrix, the ratio of the largest to the smallest eigenvalue, lambda_max / lambda_min; a large condition number (small lambda_min relative to lambda_max) means slow convergence for gradient descent.
• Gradient and level sets: the gradient points in the direction of steepest increase and is perpendicular to the level set through that point; steepest descent moves in the opposite direction, -gradient(f).
• Hessian and convexity: a function is convex where its Hessian is positive semidefinite, and strictly convex where the Hessian is positive definite; a purely linear function is convex but not strictly convex.
• Minimizing a quadratic: for f(x) = 1/2 x^T S x - a^T x with S positive definite, the gradient is Sx - a, so the minimizer (arg min) is x* = S^{-1} a, and the minimum value is -1/2 a^T S^{-1} a.
• arg min vs. minimum value: arg min f is the point where the minimum is reached, distinct from f_min, the value of the function at that point.
• Step size choices: gradient descent needs a step size (learning rate) at each step; options include a fixed step, an exact line search that minimizes f along the current direction, and a backtracking line search that halves the step until progress is satisfactory.
• Zigzagging on elongated level sets: when the quadratic's level sets are long, thin ellipses (small B), gradient descent repeatedly overshoots across the narrow direction, producing a slow zigzag path controlled by the ratio (1 - B)/(1 + B).

Walkthrough

Gradient, Hessian, and convexity review (4:05)

Using a simple linear function f(x,y) = 2x + 5y, Strang reviews how the gradient gives the direction of steepest increase and is perpendicular to the level surface, while a zero Hessian confirms the function is convex but not strictly convex. This sets up the connection between the Hessian's definiteness and the strength of convexity.

Minimizing a general quadratic (12:17)

Working with f(x) = 1/2 x^T S x - a^T x, Strang derives the gradient Sx - a, identifies the minimizer arg min f = S^{-1} a, and computes the minimum value f_min = -1/2 a^T S^{-1} a by substituting the minimizer back into f. He also clarifies the notation arg min, distinguishing the location of the minimum from its value.

An aside on the log-determinant function (23:28)

As an example of a convex function beyond quadratics, Strang introduces -log(det(X)) as a function of a matrix X, noting its gradient is (up to sign) the entries of X^{-1}, derived from the cofactor expansion of the determinant.

Setting up gradient descent (33:43)

Gradient descent is defined as x_{k+1} = x_k - s_k * gradient(f)(x_k), with the step size s_k as the key design choice: too large causes oscillation, too small is slow to converge. Strang describes both exact line search, which finds the best step along the current direction, and backtracking line search, which starts with a step and repeatedly halves it.

The solvable quadratic example (40:50)

For f(x,y) = x^2 + B y^2 starting at (B, 1) with exact line search, Strang gives the closed-form iteration: x_k = B * r^k, y_k = r^k, and f_k = r^k * f_0, where r = (1 - B)/(1 + B). This shows directly that convergence is fast when B is close to 1 (well-conditioned) and very slow when B is small (poorly conditioned).

Zigzagging and level sets (46:58)

Visualizing the level sets of x^2 + B y^2 as long, thin ellipses when B is small, Strang explains why steepest descent zigzags: each step moves perpendicular to the current level set, overshooting across the narrow direction of the valley and making slow net progress toward the minimum. This sets up the next lecture's introduction of momentum to fix the zigzagging.

Before you watch

• Review the gradient, Hessian, and convexity definitions from the previous lecture on Newton's method and optimization.
• Recall positive definiteness and eigenvalues of symmetric matrices from earlier in the course.

Check your understanding

1. Why does the minimizer of f(x) = 1/2 x^T S x - a^T x equal S^{-1} a?
2. What is the difference between arg min f and f_min?
3. Why does gradient descent converge slowly when the condition number of the Hessian is large?
4. Why does steepest descent zigzag on level sets that are long, thin ellipses?