Sharper Regret Bounds for Shampoo

Shampoo is a Kronecker-structured second-order optimizer widely used for large-scale deep learning, yet existing regret analyses exhibit an unfavorable dependence on the gradient rank, leading to guarantees that are uniformly weaker than those of optimizers such as Adagrad and One-sided Shampoo. We provide a uniformly and substantially sharper regret bound for the full two-sided Shampoo update, yielding bounds that can compete with full-matrix Adagrad and more recent structured variants such as One-sided Shampoo. By further analysis, we also establish the first sublinear convergence guarantee for the commonly implemented variant Shampoo${}^2$ by introducing a principled scaling factor. Our analysis holds for a continuum of exponent choices $p\in (0,\frac{1}{2}]$, also providing the first sublinear guarantees for Shampoo${}^{4p}$ with exponents other than $p=1/4$.