Optimization: Gradient Descent
Claude prompt
This page was generated by Claude Code from the following prompt (with additional prompting):
The second demo for lecture 140-Gradient-Descent should include the existing 1-d solution content, along with a 2-d gradient-descent demo on gaussians with different eigenvalue ratios.
In the gradient demo, no need for the angle theta, and no need for the 3d plot. Variable step size will be in the next lecture, so don't do the golden-section line search. Put the start x and y on the same line and iteration below it. Make it just quadratic, not exp.
Split the 1d search and gradient descent into two demos, but both linked to the gradient descent lecture in the lecture table.
In more than one dimension there is no bracket to shrink around a minimum. Gradient descent instead takes a step downhill, against the gradient: \[ \vec{x}_{k+1} = \vec{x}_k - \alpha\, \nabla f(\vec{x}_k). \] The test function is a quadratic bowl, \[ f(x, y) = \tfrac{1}{2}\, \vec{x}^\mathsf{T} A\, \vec{x} = \tfrac{1}{2}\left(x^2 + r\,y^2\right), \qquad A = \begin{bmatrix} 1 & 0 \\ 0 & r \end{bmatrix}, \] whose minimum is at the origin. Its Hessian is \(A\) everywhere, with eigenvalues \(\lambda_1 = r\) (steep, in \(y\)) and \(\lambda_2 = 1\) (shallow, in \(x\)), so the ratio \(\lambda_1 / \lambda_2 = r\) sets how stretched the contours are. Click on the contour plot to move the starting point.
With a ratio of 1 the contours are circles, the gradient points straight at the minimum, and one well-chosen step lands on it. As the ratio grows the gradient points across the narrow valley rather than along it: a step size small enough to be stable in the steep direction (\(\alpha < 2/\lambda_1\) ) crawls along the shallow one, and a larger one zig-zags across the valley or diverges. No single \(\alpha\) is good in both directions at once, which is the motivation for choosing the step size adaptively, the subject of the next lecture.