Risky Giant Steps Can Solve Optimization Problems Faster | Quanta Magazine

gradient-descentoptimizationconvex-optimizationstep-sizemachine-learning

Abstraction: Oversized gradient descent steps with cyclical patterns converge nearly 3x faster

Key points:

Ben Grimmer (Johns Hopkins, 2023) proved gradient descent can converge nearly 3x faster by breaking the long-held rule of capping step size at 2; one large "giant" step mid-sequence is optimal
For a repeating k-step sequence, the central step should be large: 4.9 for 3-step, 29.7 for 15-step, and 370 for a 127-step sequence — even though these overshoot the minimum, subsequent steps recover
Das Gupta et al. (2022) first found the effect numerically by computer-solving a meta-optimization for best 50 step-lengths; one step reached length ~37 vs. the conventional cap of 2
The optimal step-length sequences have a near-fractal symmetric structure — a big central step surrounded by smaller steps, recursively — whose underlying theory remains unexplained
Result applies only to smooth convex functions; the souped-up gradient descent variants used in ML (non-convex, noisy) already surpass this 3x speedup via other techniques
Gradient descent, pioneered by Cauchy in 1847 for astronomical calculations, remains the backbone of modern ML training

Connections: Quanta Magazine · Gradient Descent · Convex Optimization · Optimization