Non-monotonic convergence of gradient descent with large stepsize
summary
Shows that for a simplified but rigorous setting — linear models on perfectly separable data — gradient descent with any constant step size provably drives training loss to zero, despite violating the descent lemma. Empirical plots on a 3-layer classifier exhibit the edge of stability: large stepsize causes sustained non‑monotonic oscillations in loss yet still reaches near‑zero training error. Proof uses Taylor/quadratic intuition and a reduction to linear dynamics; asymptotic rates match small steps but give a clear finite‑time speedup.
AI-written summary · about
chapters (4)
related talks
13mThe dynamical view of machine learning: implicit biases of large learning rates
13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient Descent
58mFirst-Order Stochastic Optimization
31mGradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale
46mGradient Descent: The Ultimate Optimizer
28mStability and Convergence Trade-Off of Iterative Optimization Algorithms
01h 18mOptimization I
46mAnalyzing Optimization and Generalization in Deep Learning via Trajectories of Gradient Descent