Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization
Abstract
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 ε. 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 ε 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.
Related
- On Minimax Optimality and Uniqueness of Fixed-Step First-Order Methods for Smooth Convex Optimization
- Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
- Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization
- The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
BibTeX
@misc{sarkar2026minimax,
title = {{Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization}},
author = {Abir Sarkar and Nirmalya Mandal and Martin T. Wells},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16923},
eprint = {2610.16923},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16923},
}
RIS
TY - UNPB
TI - Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization
AU - Abir Sarkar
AU - Nirmalya Mandal
AU - Martin T. Wells
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16923
UR - https://arxiv.org/abs/2610.16923
AB - 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 ε. 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 ε 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.
ER -