Descent Methods and Momentum

Corresponds to Chapters 3–4. The simplest possible algorithm — repeatedly step in the direction of steepest descent, $-\nabla f(x)$ — is the baseline every later method is compared against, with convergence rate depending sharply on how much structure $f$ has (general smooth: sublinear; convex: faster sublinear; strongly convex: linear/geometric). Line search covers the practical question of how far to step; mirror descent generalizes steepest descent to non-Euclidean geometries via a Bregman divergence (the same object in adversarial-linear-bandits‘s FTRL/mirror-descent treatment), and the KL/PL properties identify a class of nonconvex functions where linear convergence still holds. Momentum methods are motivated by treating gradient descent as a discretized differential equation (learning-as-a-dynamical-system covers gradient flow directly) and adding a “velocity” term to accelerate convergence; Nesterov’s method achieves the provably optimal rate for smooth convex optimization using only gradient information, matched by a lower bound showing no first-order method can do better, with conjugate gradient methods as a related, exact-arithmetic-optimal approach for quadratics.

Outline (TODO — flesh out each)

• Descent directions
• The steepest-descent method — general, convex, strongly convex cases
• Comparison between convergence rates
• Descent methods — general convergence theory
• Line-search methods — choosing the direction and the steplength (and why Algorithm 3.1 is an effective line-search technique)
• Convergence to approximate second-order necessary points
• Mirror descent
• The KL and PL properties
• Momentum — motivation from differential equations
• Nesterov’s method for convex quadratics
• Convergence for strongly convex and for weakly convex functions
• Conjugate gradient methods
• Lower bounds on convergence rates