Intuition. A preconditioner adjusts a proposed gradient step using past gradients, reducing repeated overshooting along strongly scaled directions. Shampoo remembers how rows and columns move together instead of treating every matrix entry as an unrelated knob. For a 2×3 weight matrix, its two preconditioners contain 4+9 entries; a full preconditioner over all six weights contains 36.
Reading the math. G is the current gradient matrix; L accumulates GGᵀ and R accumulates GᵀG, with small positive diagonal terms for stability. The update L⁻¼ G R⁻¼ rescales the gradient from both sides. Matrix powers act on eigenvalues, so the rescaling can follow tilted directions as well as coordinate axes.
Shampoo preconditions matrix and tensor gradients using one accumulated second-moment matrix per tensor dimension. It retains correlations within those dimensions while avoiding a full preconditioner over every flattened parameter. The paper proves rank-dependent regret bounds for online convex optimization and reports faster progress per training step in several neural-network experiments. Those experiments use nonconvex models and practical modifications; they are separate evidence from the convex theorem. Complete figures, algorithms, mathematical displays, and all fifteen formal statements are retained.
1 Introduction
A full preconditioner for a flattened tensor can be too large to store or factor. Shampoo instead exploits the tensor’s existing shape, building modest matrices along each mode. Figure 1 illustrates the idea, and Algorithm 1 gives the matrix case. This is a structured second-moment method, not direct computation of a neural network’s Hessian or Fisher inverse. Its theoretical development uses online convex optimization, while its practical motivation includes deep learning.
Figure 1: Illustration of Shampoo for a -dimensional tensor
.Algorithm 1: Shampoo, matrix case.Accessible original algorithm markup
Initialize
fordo
Receive loss function
Compute gradient
{}
Update preconditioners:
Equation
Update parameters:
Equation
For an m×n parameter matrix, Shampoo accumulates left and right gradient Gram matrices, then multiplies the gradient by their inverse fourth roots. Storage for the preconditioners is m²+n² rather than m²n²; dense factorization costs scale as m³+n³ rather than m³n³. Tensor shape therefore matters. The equivalent flattened update uses a Kronecker-product metric without forming it explicitly. The fourth-root exponents are essential: replacing them with arbitrary inverse powers changes both the update and the analysis.
1.2 Related work
The method is closely related to full-matrix AdaGrad [6], but uses a structured implicit preconditioner instead of a dense matrix or an entirely elementwise approximation. K-FAC also uses Kronecker factors, but approximates a generative model’s Fisher matrix using network-specific gradient structure and statistical assumptions. Shampoo uses ordinary gradients and tensor dimensions in a more general optimization setting. Shared factorization ideas do not make these algorithms mathematically identical.
2 Background and technical tools
The analysis uses positive-semidefinite ordering, matrix powers defined spectrally, metric-induced norms, spectral norms, and Frobenius inner products. Negative matrix powers require positive-definite regularization or an explicitly defined generalized-inverse convention; a singular PSD matrix does not have an ordinary inverse. The preserved source definitions should be interpreted with that domain restriction.
2.1 Online convex optimization
In online convex optimization, the learner chooses an iterate, receives a convex loss, and competes with one fixed comparator over the full sequence. Regret measures the cumulative difference. Online-to-batch conversion gives stochastic convex optimization guarantees under the corresponding sampling and averaging setup. This framework does not directly prove convergence to a global minimum for the neural experiments.
Equation
2.2 Adaptive regularization in online optimization
Adaptive online mirror descent minimizes a linearized loss plus a time-dependent quadratic regularizer. On an unconstrained domain this becomes a preconditioned gradient step; on a constrained domain it includes a metric projection. Lemma 1 separates regret into a changing-distance term and accumulated dual gradient norms. Lemma 2 bounds those norms through a potential-minimization argument, supplying the main machinery for Shampoo’s proof.
Equations 1
(1)
Lemma 1.
For any sequence of matrices , the regret of online
mirror descent is bounded above by,
Let be a sequence of vectors, and let
for .
Given a function over PSD matrices, define
Equation
(and assume that a minimum is attained for all ).
Then
Equation
2.3 Kronecker products
The paper uses row-major vectorization, explicitly distinguishing it from a common column-major convention. Kronecker identities connect left/right matrix multiplication with a single linear transformation of that vectorization. The exact transposes and ordering matter when reproducing the update. The PSD comparisons and inverse-power identities used in the proof require their stated positivity and invertibility assumptions; they are not arbitrary identities for unordered or singular matrices.
Equations
Lemma 3.
Let be matrices of appropriate dimensions.
The following properties hold:
(i)
;
(ii)
;
(iii)
If , then for any it holds that , and in particular, if then ;
(iv)
If and then ,
and in particular, if then ;
(v)
;
(vi)
for any two column vectors .
Lemma 4.
Let , and .
Then, one has
Equation
2.4 Matrix inequalities
The proof needs operator monotonicity of weighted geometric means for commuting PSD matrices and of scalar powers with exponent between zero and one. The relevant Kronecker factors commute because they act on separate tensor modes. This special structure permits the comparison without incorrectly commuting arbitrary covariance matrices.
Theorem 7 bounds matrix-case regret by a comparator-distance factor, a gradient-rank factor, and the product of two fourth-root traces. With bounded gradients and a controlled comparator distance, the traces yield O(√T) regret. The distance D is the maximum iterate–comparator separation and need not remain bounded for the unprojected algorithm; the paper discusses a metric projection that would control it but omits that expensive operation in practice.
Lemma 9 uses the gradient’s singular-value decomposition and a rank-dependent quadratic inequality to dominate the vectorized gradient outer product by two simpler PSD matrices. Summing over time and taking a commuting geometric mean gives Lemma 8’s comparison with the full accumulated second moment. The proof then expresses Shampoo as mirror descent, bounds the changing metric term, and uses Lemma 2 to control accumulated dual norms. Selecting the displayed learning rate balances the two terms. This is a regret comparison under convexity and rank assumptions, not a claim that every direction of a neural weight matrix moves equally or that Shampoo is an exact natural gradient.
Theorem 7.
Assume that the gradients are matrices of
rank at most .
Then the regret of Algorithm1 compared to any
is bounded as follows,
Equation
where
Equation
Lemma 8.
Assume that are matrices of
rank at most . Let denote the vectorization of for
all . Then, for any ,
Equation
Lemma 9.
Let be an matrix of rank at most and denote . Then,
The general algorithm applies the same construction to tensors of arbitrary order. It needs explicit definitions of flattening, matricization, mode multiplication, and contraction before extending the matrix proof.
4.1 Tensors: notation and definitions
A mode-wise matricization stacks vectorized tensor slices as rows. Contracting a gradient with itself over every other mode gives that mode’s Gram matrix. Multiplication along distinct modes commutes, allowing the preconditioners to be applied in any mode order. Rank-one tensor identities connect these operations to Kronecker products. These definitions distinguish tensor order from the rank of a particular matricization; the theorem’s rank factors refer to the latter.
Equations
4.2 The algorithm
Algorithm 2 maintains one Gram accumulator per mode of an order-k gradient and applies its inverse 1/(2k) power along that mode. Theorem 10 extends the regret bound using the geometric mean of bounds on the ranks of all matricizations. Its trace product has O(√T) growth under the stated boundedness conditions. As in the matrix case, the unprojected algorithm’s comparator-distance term remains an assumption-dependent quantity rather than an automatic constant.
Algorithm 2: Shampoo, general tensor case.Accessible original algorithm markup
Initialize: ;
fordo
Receive loss function
Compute gradient
{}
{ is preconditioned gradient}
fordo
Update:
Theorem 10.
Assume that for all and it holds that , and let .
Then the regret of Algorithm2 compared to any is
Equation
where for all and
.
4.3 Analysis
Lemma 11 compares the accumulated outer products of flattened gradients with a Kronecker product of mode-wise accumulators, including the geometric-mean rank factor. Lemma 12 proves that applying a Kronecker product to a flattened tensor equals applying the corresponding matrices along its modes. Together they convert Algorithm 2 to mirror descent with an implicit metric, so the matrix proof extends. Appendix B supplies the technical details rather than leaving this tensor generalization merely intuitive.
Lemma 11.
Assume that are all order tensors of dimension , and let and for all .
Let denote the bound on the rank of the matricization of , namely,
for all and . Denote .
Then, for any it holds that
Equation
Lemma 12.
Let be an dimensional tensor and be an for , then
Equation
Equation
5 Implementation details
The TensorFlow implementation uses tensor contractions and SVD-based matrix powers. It treats each model tensor separately, so the overall preconditioner is block diagonal across tensors: cross-tensor correlations are ignored. For an excessively large mode, it switches only that mode to diagonal preconditioning, using a threshold near 1,200 in these experiments. This limits memory and factorization costs without requiring every other mode to become diagonal.
6 Experimental results
The practical experiments use batch size 128, momentum 0.9, and roots recomputed every 20–100 steps. Accumulators are updated from averaged mini-batch gradients, not separate outer products for every example. These choices change the exact theoretical pseudocode and are evaluated empirically. Table 1 reports throughput on a Tesla K40. Shampoo has similar throughput on the image models, but the language-model case is 3.509 steps/s versus Adam’s4.871; faster progress per step should not be presented as automatically faster wall-clock convergence.
Table 1: Average number of steps per second (with batch size of 128) in each experiment, for each of the algorithms we tested.
6.1 Image Classification
The image experiments compare learning curves for residual and inception networks on CIFAR-10 and a residual network without batch normalization on CIFAR-100. Each optimizer receives a learning-rate sweep, and the figures show training loss against epochs. The text gives test-error levels reached by these architectures, but the plots are not replicated test-accuracy comparisons with uncertainty intervals. They support the reported optimization behavior in these settings rather than universal superiority across architectures.
Figure 2: Training loss for a residual network and an inception network on CIFAR-10.Figure 3: Training loss for a residual network on CIFAR-100 (without batchnorm).
6.2 Language Models
The LM1B experiment uses a 9.8M-parameter attention model and plots test log-perplexity against steps. Shampoo uses its default learning rate 1.0 while alternatives receive several learning-rate settings. The observed curve improves faster in steps, but the throughput table shows a meaningful per-step cost. This historical small-model experiment does not establish compute savings for today’s large language-model pretraining.
Diagonal Shampoo keeps only each mode accumulator’s diagonal. In the matrix case this uses O(m+n) preconditioner storage and O(mn) update time; it can also be mixed with full preconditioning on another mode. Theorem 13 replaces the Frobenius comparator-distance factor with an entrywise infinity-norm factor. Its proof adapts the changing-metric term using diagonal PSD matrices and applies diagonal extraction to the structured/full-moment comparison. The complete Algorithm 3 and formal bound are retained.
Equation
Algorithm 3: Diagonal version of Shampoo, matrix case.Accessible original algorithm markup
Initialize
fordo
Receive loss function
Compute gradient
{}
Update preconditioners:
Equation
Update parameters:
Equation
Theorem 13.
Assume that the gradients are matrices of rank at most .
Then the regret of Algorithm3 compared to any is bounded as
Equation
where
Equation
(Here, is the entry-wise norm of a matrix , i.e., .)
Equations
Appendix B Tensor case: Technical proofs
Lemma 14 establishes the tensor identities needed by the later proofs. It verifies vectorization and matricization on rank-one outer products, proves the boundary-mode vectorization equalities, and checks how mode multiplication appears after matricization. Linearity then extends these identities to arbitrary tensors. These bookkeeping steps preserve the ordering convention that the Kronecker proof requires.
Lemma 14.
For any column vectors and order- tensor it holds that:
(i)
;
(ii)
;
(iii)
;
(iv)
.
Equations
B.1 Proof of Lemma 11
Lemma 15 shows that a PSD inequality expressed after one matricization is equivalent to the corresponding inequality in the canonical tensor flattening. The proof evaluates both quadratic forms on an arbitrary test tensor and expands coordinates to show equality. Applying the matrix rank bound to each matricized gradient, transporting it back, and summing over time yields one inequality per mode. Their right-hand factors commute, so the geometric-mean inequality combines them into Lemma 11 with its rank multiplier.
Lemma 15.
Let be an order tensor of dimension , and an
matrix. Let and . Then
Equation
Equations
B.2 Proof of Lemma 12
The proof of Lemma 12 inducts on tensor order. It isolates the last mode through its matricization, applies the matrix vectorization identity, and uses the induction hypothesis independently on each lower-order slice. Stacking those slices and restoring the last mode gives the full Kronecker/mode-multiplication identity. The original displayed chain retains the transposes that make the dimensions consistent.
Equations
Appendix C Additional proofs
C.1 Proof of Lemma 2
Lemma 2 follows a follow-the-leader/be-the-leader induction. The potential-minimizing metric at the preceding round cannot improve the previous objective over its minimizer; substituting the final-round metric and adding the new dual-gradient term yields the desired telescoping comparison. The existence of each metric minimizer is an explicit assumption in the lemma.
Equations
C.2 Proof of Lemma 4
The matrix vectorization identity is proved first for a rank-one matrix. Both the Kronecker expression and the left/right matrix product reduce to the same tensor product of two vectors. Decomposing any matrix into rank-one terms and using linearity completes the proof. This closes the algebraic link underlying the efficient implementation.
Equations
24 references
[1]
M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin,
S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga,
S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden,
M. Wicke, Y. Yu, and X. Zheng.
Tensorflow: A system for large-scale machine learning.
In 12th USENIX Symposium on Operating Systems Design and
Implementation (OSDI 16), pages 265–283, 2016.
[4]
N. Cesa-Bianchi, A. Conconi, and C. Gentile.
On the generalization ability of on-line learning algorithms.
IEEE Transactions on Information Theory, 50(9):2050–2057, 2004.
[5]
C. Chelba, T. Mikolov, M. Schuster, Q. Ge, T. Brants, P. Koehn, and
T. Robinson.
One billion word benchmark for measuring progress in statistical
language modeling.
Technical report, Google, 2013.
[6]
J. Duchi, E. Hazan, and Y. Singer.
Adaptive subgradient methods for online learning and stochastic
optimization.
Journal of Machine Learning Research, 12(Jul):2121–2159, 2011.
[7]
M. A. Erdogdu and A. Montanari.
Convergence rates of sub-sampled newton methods.
In Proceedings of the 28th International Conference on Neural
Information Processing Systems-Volume 2, pages 3052–3060. MIT Press, 2015.
[10]
V. Gupta, T. Koren, and Y. Singer.
A unified approach to adaptive regularization in online and
stochastic optimization.
arXiv preprint arXiv:1706.06569, 2017.
[17]
J. Martens and R. Grosse.
Optimizing neural networks with Kronecker-factored approximate
curvature.
In International conference on machine learning, pages
2408–2417, 2015.
[18]
B. Neyshabur, R. R. Salakhutdinov, and N. Srebro.
Path-sgd: Path-normalized optimization in deep neural networks.
In Advances in Neural Information Processing Systems, pages
2422–2430, 2015.
[20]
M. Pilanci and M. J. Wainwright.
Newton sketch: A near linear-time optimization algorithm with
linear-quadratic convergence.
SIAM Journal on Optimization, 27(1):205–245, 2017.
[22]
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez,
Ł. Kaiser, and I. Polosukhin.
Attention is all you need.
In Advances in Neural Information Processing Systems, pages
6000–6010, 2017.
[23]
P. Xu, J. Yang, F. Roosta-Khorasani, C. Ré, and M. W. Mahoney.
Sub-sampled newton methods with non-uniform sampling.
In Advances in Neural Information Processing Systems, pages
3000–3008, 2016.
[24]
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.
Understanding deep learning requires rethinking generalization.
In 5th International Conference on Learning Representations,
ICLR 2017, 2017.