Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization

Abir Sarkar, Nirmalya Mandal, Martin T. Wells

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…