New Proof Shows Shampoo Optimizer Is Minimax Optimal for Nonstationary Stochastic Optimization
_arohan_ · x · 2026-10-25
Researchers at Cornell and NC State (Abir Sarkar, Nirmalya Mandal, Martin T. Wells) posted an arXiv paper giving a comprehensive theoretical analysis of Matrix-Shampoo for tracking time-varying optima in nonstationary stochastic optimization.
Key results:
- Finite-horizon high-probability bounds for average tracking error that disentangle initialization, optimizer drift, momentum-induced drift penalty, stochastic noise, and adaptive preconditioning, with explicit dependence on momentum β₁ and stabilization ε.
- Explicit tradeoffs: noise-dominated regimes favor larger β₁ for stronger first-moment averaging; drift-dominated regimes favor smaller β₁ for faster adaptation. Larger ε reduces preconditioner perturbation but weakens exploitation of matrix geometry.
- A matching minimax lower bound under a squared path-variation constraint, proving Shampoo's information-theoretic optimality over causal optimization procedures.
- High-probability bounds for the projected stationarity gap on general nonstationary nonconvex objectives with constant stepsize, validated on synthetic and real-world problems.
Relevant to anyone studying second-order/adaptive optimizers (Shampoo, Muon lineage) under nonstationary training objectives.
More from Research
- Molecular Cell review maps emerging frontiers of AI in single-cell genomics — anshulkundaje · 2026-10-25
- Harvard's Zitnik lab unveils CONCERT, a generative model for spatial perturbation responses — marinkazitnik · 2026-10-25
- Sander Dieleman's 84-minute deep dive: flow maps learn the integral of diffusion models to speed up sampling — sedielem · 2026-10-25
- AI science loops have too much textbook, not enough Newton-style curiosity — generativist · 2026-10-25
- Stanford's Finn lab proposes Generative Value Classifier, recasting Q-learning via action likelihoods — chelseabfinn · 2026-10-25
- Economist: skeptics were right about AI growth, bottlenecks still misunderstood — Afinetheorem · 2026-10-25