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 \(\beta_1\) and stabilization parameter \(\varepsilon\). These bounds reveal an explicit drift--noise and stability--geometry tradeoffs: noise-dominated regimes favor larger $\beta_1$, which provides stronger first-moment averaging and greater suppression of gradient noise, whereas drift-dominated regimes favor smaller $\beta_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.