The Descent Lemma: A Bowl That Bounds Every Step
An interactive live film: an orange paraboloid touches the loss at the current point and lies above it everywhere, so a gradient step of size α lowers the loss by at least α(1 − Lα/2)‖∇f‖², most at α = 1/L and nothing at 2/L.
Narration
This surface is a loss with a curved valley, and the black point is where gradient descent stands now. Its gradient never changes faster than a rate L, and here L equals two.
The descent lemma puts an orange bowl over it. The bowl touches the surface at the point, has the same slope there, and curves up with strength L. It stays above the surface everywhere.
The rest of the narration is in the book's Companion.
More from Chapter 12
Interactive1:08Gradient Descent in an Ill-Conditioned ValleyChapter 12
Preview1:33Heavy-Ball Momentum: Zig-Zags Cancel, the Valley Floor Adds UpChapter 12
Preview1:43A Large Step Selects a Flatter MinimumChapter 12
Preview2:12Sophia: Newton Steps with a ClipChapter 12
Preview2:14Adam and AdamW: A Step Size for Every CoordinateChapter 12
Preview1:55Backtracking Line Search and the Armijo ConditionChapter 12
Preview1:50Proximal Gradient and Soft-Thresholding: Exact ZerosChapter 12
Preview1:53KKT Conditions: the Saddle Point of the LagrangianChapter 12
Preview1:52Mirror Descent Stays Inside the SimplexChapter 12
Preview1:55The Polyak-Łojasiewicz ConditionChapter 12