Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization

arXiv:2610.16923v1 Announce Type: cross 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 (eta_1) and stabilization parameter (arepsilon). These bounds reveal an explicit drift--noise and stability--geometry tradeoffs: noise-dominated regimes favor larger eta_1, which provides stronger first-moment averaging and greater suppression of gradient noise, whereas drift-dominated regimes favor smaller eta_1, allowing faster adaptation to moving optimizer. Larger arepsilon 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.

Source: arXiv cs.LG | 2026-10-14