# Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization

arXiv: https://arxiv.org/abs/2610.16923 · HTML: https://mlsanity.com/paper/2610.16923/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 43 of its 60 references that are in the map.
- First posted on arXiv 12 Oct 2026.

## Builds on (most cited first, 30 of 43)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Continual Lifelong Learning with Neural Networks: A Review](https://mlsanity.com/paper/1802.07569/) (2018)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [CORe50: a New Dataset and Benchmark for Continuous Object Recognition](https://mlsanity.com/paper/1705.03550/) (2017)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Understanding plasticity in neural networks](https://mlsanity.com/paper/2303.01486/) (2023)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [The CLEAR Benchmark: Continual LEArning on Real-World Imagery](https://mlsanity.com/paper/2201.06289/) (2022)
- [A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale](https://mlsanity.com/paper/2309.06497/) (2023)
- [Benchmarking Optimizers for Large Language Model Pretraining](https://mlsanity.com/paper/2509.01440/) (2025)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [A New Perspective on Shampoo's Preconditioner](https://mlsanity.com/paper/2406.17748/) (2024)
- [Slow and Steady Wins the Race: Maintaining Plasticity with Hare and Tortoise Networks](https://mlsanity.com/paper/2406.02596/) (2024)
- [Disentangling Adaptive Gradient Methods from Learning Rates](https://mlsanity.com/paper/2002.11803/) (2020)
- [Structured Preconditioners in Adaptive Optimization: A Unified Analysis](https://mlsanity.com/paper/2503.10537/) (2025)
- [Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization](https://mlsanity.com/paper/2101.11075/) (2021)
- [Purifying Shampoo: Investigating Shampoo's Heuristics by Decomposing its Preconditioner](https://mlsanity.com/paper/2506.03595/) (2025)
- [4-bit Shampoo for Memory-Efficient Network Training](https://mlsanity.com/paper/2405.18144/) (2024)
- [A Stable Whitening Optimizer for Efficient Neural Network Training](https://mlsanity.com/paper/2506.07254/) (2025)
- [Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions](https://mlsanity.com/paper/2302.03764/) (2023)
- [Stochastic Optimization under Distributional Drift](https://mlsanity.com/paper/2108.07356/) (2021)
- [Domain-independent Dominance of Adaptive Methods](https://mlsanity.com/paper/1912.01823/) (2019)

## Abstract (arXiv)

We develop a comprehensive theoretical analysis of Matrix Shampoo for tracking time-varying optima in nonstationary stochastic optimization. We derive 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 parameter (β1) and stabilization parameter (varepsilon). These bounds reveal an explicit drift--noise and stability--geometry tradeoffs: noise-dominated regimes favor larger β1, which provides stronger first-moment averaging and greater suppression of gradient noise, whereas drift-dominated regimes favor smaller β1, allowing faster adaptation to moving optimizer. Larger varepsilon reduces the preconditioner-perturbation term while weakening Shampoo's ability to exploit matrix geometry, thereby reducing adaptivity. We establish a matching minimax lower bound under squared path-variation constraint, proving the information-theoretic optimality of Shampoo over the class of causal optimization procedures. Under a constant stepsize, we establish high-probability bounds for the average projected stationarity gap along general nonstationary nonconvex objectives. We validate our theoretical findings on both synthetic and multiple real-world problems.