New theory paper proves linear decay is the unique minimax-optimal stepsize schedule for SGD
konstmish · x · 2026-11-02
An arXiv paper by Benjamin Grimmer and Qining Shen analyzes stepsize schedules for SGD in smooth convex optimization, assuming conditionally zero-mean gradient noise with bounded variance.
- For problems with dimension d ≥ N+1, it gives an exact worst-case analysis of expected suboptimality of the final iterate for any schedule of N stepsizes in [0,1.5]^N, with matching objectives and noise distributions attaining the bound.
- When the variance bound is at least Ω(1/√N), the theory yields the minimax-optimal stepsize schedule and proves its uniqueness.
- The optimal stepsizes decrease monotonically — i.e., linear decay — ruling out accelerations from fixed fractal schedules seen in the deterministic setting.
More from Research
- Xiaomi MiMo's CodeSpecWeave trains coding agents on interdependent specs for long-horizon coding — XiaomiMiMo · 2026-11-02
- Mistral Large 4 writes a quantum chemistry SCF solver from scratch with one short prompt — MistralAI · 2026-11-02
- Hunting for the most concrete "curing cancer with AI" roadmap of 2025 — iskander · 2026-11-02
- Karpathy's nanochat: the best ChatGPT $100 can buy, near 60k GitHub stars — karpathy · 2026-11-02
- After reading 46 resources on agent evals, one author explains why her 95% score was misleading — blaizedsouza · 2026-11-02
- Meta & MIT paper: looping transformer layers beats adding depth at fixed size — rohanpaul_ai · 2026-11-02