MIT proves tighter limits on step-size-scheduled gradient descent: n^-1.63 finite-horizon bound
burkov · x · 2026-09-03
Gradient descent is usually taught with a fixed step size, but recent work shows it can be sped up just by choosing step sizes in a carefully designed sequence. A new MIT CSAIL paper studies how far this idea can go on smooth convex problems:
- It analyzes two settings: a finite-horizon schedule (known number of steps) and an "anytime" schedule that works well regardless of when optimization stops.
- It proves substantially stronger convergence lower bounds: roughly n^-1.6342 for the finite-horizon case and n^-1.2408 for the anytime case.
- The anytime bound also shows that a single fixed infinite schedule cannot match the best achievable rate.
The result gives a sharper theoretical picture of how much acceleration is possible without changing the algorithm itself.
More from Research
- Eigenfaces revisited: interactive demos of the pioneering computer vision technique — CSProfKGD · 2026-09-03
- Three-Paper Series Decomposes Human-Like RSI into ASPIRE, S³Gym and HarnessDev — teortaxesTex · 2026-09-03
- Noematrix's Noe-0 trains embodied models with zero teleoperation data — jiqizhixin · 2026-09-03
- New research shows user feedback signals like "that's wrong" can be leveraged for training — LChoshen · 2026-09-03
- Study finds all 13 major LLMs flip truth judgments on speaker gender, up to 23.6% of statements — anthara_ai · 2026-09-03
- R³ paper: robots learn to think before acting with carefully done RL on explaining demo data — aviral_kumar2 · 2026-09-03