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.
Figures & tables
Figure 1: Momentum drift–noise tradeoff. Results for Kronecker (left), Huber (center), and phase retrieval (right). High-drift/Low-noise regime, (Δ,σ2)=(0.15,10−2) (top), Low-drift/High-noise regime, (Δ,σ2)=(0.003,1) (bottom). Enlarged markers indicate the empirically optimal value of β1 over T=500 iterations. Across all three objectives, the optimal β1 shifts from zero in the drift-dominated regime towards right in the noise-dominated regime, illustrating that short memory facilitates tracking while longer memory suppresses stochastic noise.
Figure 2: Empirical validation of the minimax tracking rate. Results for the Kronecker (left), Huber (center), and soft-label logistic (right) problems under the path-variation regimes DT≍logT,T1/3,T1/2 , and T . Across all three problems, the normalized errors remain overall stable over the horizon, supporting the minimax scaling.
Figure 3: Ridge stability–geometry tradeoff. Average tracking error for convex and average projected-stationarity gap for non-convex objectives. In high-drift, low-noise regime (top), the realized preconditioned filtered-noise energy is small, so the preconditioner-perturbation term Gδ/ε2 dominates, decreasing tracking error as ε increases. In the other regime, ZTQ(ε) becomes dominant as ε increases, exhibiting the complementary behavior.
Figure 4: CNN performance on CLEAR-10 and CORe50. Mean classification error at bucket-end iterations on the training (left) and test (right) splits for SGD and for momentum-SGD, Adam, and Shampoo with β1∈{0.5,0.99} . Shampoo performs consistently across the β1 values, whereas Adam exhibits substantial instability with shorter memory and SGDM deteriorates under longer memory [ 18 ] .
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Empirical validation of the minimax tracking rate. Results for phase retrieval (left) and the cosine objective (right) under the path-variation regimes DT≍logT,T1/3,T1/2 , and T . The average tracking error is normalized by rT⋆=σ4/3DT1/3/(μ4/3T1/3) . The normalized errors remain overall stable over the horizon, supporting the predicted minimax scaling.
Figure 6: Ridge stability–geometry tradeoff. Average tracking error for convex objectives and average projected-stationarity gap for nonconvex objectives. In the high-drift, low-noise regime (top), the preconditioned filtered-noise energy ZTQ(ε) remains small, and the decreasing error with increasing ε is consistent with dominance of the preconditioner-perturbation contribution Gδ/ε2 . In the low-drift, high-noise regime (bottom), ZTQ(ε) becomes increasingly important as ε grows, producing the complementary behavior.
Figure 7: Shampoo tracking trajectories for convex objectives. Results for Kronecker quadratic , Huber , and soft-label logistic (top to bottom) under high drift/low noise (Δ,σ2)=(0.15,0.01) (left) and low drift/high noise (0.003,1) (right); fixing β2=0.999 . Curves show the ten-seed mean cumulative average tracking error, with one-standard-error bands. Overall, strong drift generally favors shorter first-moment memory, whereas higher noise can favor moderate memory, with the size of this benefit depending on the objective.
Figure 8: Shampoo tracking trajectories for non-convex objectives. Results for Phase retrieval , cosine-perturbed matrix , and low-rank matrix factorization (top to bottom) under high drift/low noise (Δ,σ2)=(0.15,0.01) (left) and low drift/high noise (0.003,1) (right); fixing β2=0.999 . Curves show the ten-seed mean cumulative average stationary gap, with one-standard-error bands. Overall, strong drift generally favors shorter first-moment memory, whereas higher noise can favor moderate memory, with the size of this benefit depending on the objective.
Shampoo is attracting considerable attention for its superior performance on large-scale optimization benchmarks; yet it faces a significant practical bottleneck: the prohibitive computational overhead of matrix inversion. To mitigate this, practitioners typically rely on stale preconditioner updates, creating a fundamental trade-off between computational efficiency and optimization fidelity. In this work, we provide a theoretical study of staleness through the complementary lenses of convergence and stability. While staleness improves computational efficiency, it inherently degrades performance and introduces numerical instability. Crucially, we identify that damping, acting as a numerical stabilizer, can effectively suppress these negative effects. Guided by this analysis, we propose FOAM, an adaptive algorithm that stabilizes training by dynamically controlling both the damping factor and the eigendecomposition frequency based on an approximation of the staleness-oriented error. Experimental results demonstrate that FOAM reduces wall-clock time compared to standard Shampoo while maintaining robust convergence.
Modern deep learning optimization features heterogeneous parameter structures, noisy gradients, and highly nonconvex landscapes, posing significant challenges for both algorithm design and theoretical analysis. Motivated by the limitations of SGD and the success of adaptive optimizers, we propose {\it Schattor}, a family of adaptive first-order methods based on Schatten norms. Schattor unifies SGD and the recently proposed matrix-variate adaptive optimizer Muon within a single Schatten-norm-based framework. We establish dimension-free stationarity guarantees for methods in the Schattor family for stochastic matrix optimization problems via a novel matrix martingale moment bound. We also develop multi-block extensions that adaptively balance block-wise optimization progress and prove dimension-free stationarity guarantees in this more general setting.
Bohao Ma, Junyu Zhang, Chuan He
School of Data Science, The Chinese University of Hong Kong (Shenzhen), Shenzhen, Guangdong, China · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore · Department of Mathematics, Linköping University, Sweden
Recently, Jiang et al. [2026] developed Leon, a practical variant of One-sided Shampoo [Xie et al., 2025a, An et al., 2025] algorithm for online convex optimization, which does not require computing a costly quadratic projection at each iteration. Unfortunately, according to the existing analysis, Leon requires tuning an additional hyperparameter in its preconditioner and cannot achieve dimension-independent convergence guarantees for convex optimization problems beyond the bounded gradients assumption. In this paper, we resolve this issue by proving certain stability properties of Leon's preconditioner. Using our improved analysis, we show that tuning the extra hyperparameter can be avoided and, more importantly, develop the first practical variant of One-sided Shampoo with Nesterov acceleration, which does not require computing projections at each iteration. As a side contribution, we obtain improved dimension-independent rates in the non-smooth non-convex setting and develop a unified analysis of the proposed algorithm, which yields accelerated projection-free adaptive SGD with (block-)diagonal preconditioners.