Back to paper library
arXiv 2018ICML 2018OptimizersPaper notes

Shampoo

Before the conditioner

Original paper

Shampoo: Preconditioned Stochastic Tensor Optimization

Paper authors

Vineet Gupta · Tomer Koren · Yoram Singer

Publication
ICML 2018Conference
First submitted to arXiv
arXiv:1802.09568
Cite this paper · BibTeX

The citation identifies the linked source version. It cites the original paper and its authors.

@misc{optimizersshampoo2018,
  title = {{Shampoo: Preconditioned Stochastic Tensor Optimization}},
  author = {Vineet Gupta and Tomer Koren and Yoram Singer},
  year = {2018},
  eprint = {1802.09568},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.09568}
}
On this page

The paper's name is tucked away in a footnote on page 2: “We call it Shampoo because it has to do with preconditioning.”

Conditioner is what goes on your hair, so pre-conditioning is whatever comes before it, which is obviously shampoo. The acknowledgments also give special thanks to Roy Frostig for coming up with the name.

Jokes aside, the paper tackles a very practical headache. An optimizer that wants to see how parameters pull on one another has to maintain a matrix the size of the parameter count squared. Vineet Gupta and Tomer Koren of Google Brain and Yoram Singer of Princeton wanted a way to avoid actually storing that matrix.

Defining the problem

What preconditioning does

In the plainest gradient descent, every parameter moves against its gradient with the same learning rate. A preconditioned method first multiplies the gradient by a matrix before taking the step:

wt+1=wt−η Ht−1gtw_{t+1} = w_t - \eta\, H_t^{-1} g_t

If HtH_t is diagonal, the effect is to scale each parameter's step separately; Adam and AdaGrad both belong here. If HtH_t is a full matrix, it can also “turn” the gradient. When the loss landscape is a long, narrow valley running diagonally, two parameters have to move together to follow the valley floor. A diagonal matrix can only scale the two coordinate axes separately; it takes a full matrix to rotate that slanted valley straight.

Full-matrix AdaGrad is too big

AdaGrad has a full-matrix version whose preconditioner is the square root of the accumulated outer products of the gradients:

Ht=(∑s=1tgsgs⊤)1/2H_t = \Big(\sum_{s=1}^{t} g_s g_s^\top\Big)^{1/2}

Its theoretical properties are better than the diagonal version's, but nobody can afford it. Take a 1024×10241024 \times 1024 fully connected layer. Flattened, it has 220≈1.052^{20} \approx 1.05 million parameters, so HtH_t is 220×2202^{20}\times 2^{20}, about 1.1×10121.1\times10^{12} entries, which takes more than 4 TB in single precision; on top of that, every step needs its square root and inverse, at a cost of O(m3n3)O(m^3n^3).

There were a few ways out at the time. Diagonal approximations are cheap but throw away every correlation between parameters. Sketching and other estimation methods the authors judge “seldom practical at large scale.” K-FAC also uses a Kronecker factorization, but what it approximates is the Fisher matrix; it has to sample from the model's predictive distribution and relies on the backpropagation structure of feed-forward networks, so a new architecture means a new derivation.

Neural network parameters are matrices and tensors to begin with. A fully connected layer is m×nm\times n, and a convolution kernel has four dimensions. The question this paper asks is whether we can keep that shape and approximate the huge preconditioner with a few small matrices.

Solving the problem

One on each side

In the matrix case, Shampoo keeps two preconditioners for an m×nm\times n weight matrix, an m×mm\times m one on the left and an n×nn\times n one on the right (Algorithm 1):

Lt=Lt−1+GtGt⊤Rt=Rt−1+Gt⊤GtWt+1=Wt−η Lt−1/4 Gt Rt−1/4\begin{aligned} L_t &= L_{t-1} + G_t G_t^\top \\ R_t &= R_{t-1} + G_t^\top G_t \\ W_{t+1} &= W_t - \eta\, L_t^{-1/4}\, G_t\, R_t^{-1/4} \end{aligned}

They start at L0=ϵImL_0=\epsilon I_m and R0=ϵInR_0=\epsilon I_n. GtGt⊤G_tG_t^\top accumulates correlations between rows, which for a fully connected layer means between output units; Gt⊤GtG_t^\top G_t accumulates correlations between columns, that is, between input features. In the update, the gradient is multiplied once from the left and once from the right.

For the same 1024×10241024\times1024 layer, LL and RR together hold 2×220≈2.12\times 2^{20}\approx 2.1 million entries, 8 MB in single precision. Memory drops from m2n2m^2n^2 to m2+n2m^2+n^2, and the cost of computing the matrix powers drops from O(m3n3)O(m^3n^3) to O(m3+n3)O(m^3+n^3).

These two small matrices are really one big matrix in disguise. By the Kronecker-product identity in the paper's Lemma 4, flattening L−1/4GR−1/4L^{-1/4} G R^{-1/4} gives (L1/4⊗R1/4)−1\big(L^{1/4}\otimes R^{1/4}\big)^{-1} times the flattened gradient. So Shampoo is effectively using an mn×mnmn\times mn preconditioner Ht=Lt1/4⊗Rt1/4H_t = L_t^{1/4}\otimes R_t^{1/4}; it just never assembles that matrix.

In code, the update for one matrix parameter is only a few lines:

python
import torch

def matrix_power(A, p):
    """p-th power of a symmetric positive-definite matrix: eigendecompose, then raise only the eigenvalues to p"""
    lam, Q = torch.linalg.eigh(A)
    return Q @ torch.diag(lam ** p) @ Q.T

class ShampooMatrix:
    """Algorithm 1: Shampoo for one m×n weight matrix"""
    def __init__(self, m, n, lr, eps=1e-4):
        self.L = eps * torch.eye(m)   # L_0 = εI_m
        self.R = eps * torch.eye(n)   # R_0 = εI_n
        self.lr = lr

    @torch.no_grad()
    def step(self, W, G):
        self.L += G @ G.T             # accumulate the m×m left statistic
        self.R += G.T @ G             # accumulate the n×n right statistic
        W -= self.lr * matrix_power(self.L, -0.25) @ G @ matrix_power(self.R, -0.25)

The paper's own implementation is in TensorFlow and computes the matrix powers with an SVD; the approach is the same.

Why 1/4

AdaGrad takes a square root, so shouldn't the exponent be −1/2-1/2? Shampoo uses −1/4-1/4 instead, once on each side.

The answer is in Lemma 8. Assuming every gradient matrix has rank at most rr, the authors prove

ϵImn+1r∑tgtgt⊤  ⪯  (ϵIm+∑tGtGt⊤)1/2⊗(ϵIn+∑tGt⊤Gt)1/2\epsilon I_{mn} + \frac{1}{r}\sum_t g_t g_t^\top \;\preceq\; \Big(\epsilon I_m + \sum_t G_tG_t^\top\Big)^{1/2} \otimes \Big(\epsilon I_n + \sum_t G_t^\top G_t\Big)^{1/2}

The left side is the full AdaGrad statistic. The proof has two steps. It first shows 1rgg⊤⪯Im⊗G⊤G\frac1r gg^\top \preceq I_m\otimes G^\top G and 1rgg⊤⪯GG⊤⊗In\frac1r gg^\top \preceq GG^\top\otimes I_n separately, an upper bound from each side; then, using the monotonicity of the matrix geometric mean, it raises each bound to the 1/21/2 power and multiplies them. That's where the first 1/21/2 comes from.

AdaGrad's preconditioner takes one more square root of the statistic. The square root preserves order on positive semidefinite matrices, so taking the 1/21/2 power of both sides gives

(∑tgtgt⊤)1/2⪯r (Lt1/4⊗Rt1/4)\Big(\sum_t g_tg_t^\top\Big)^{1/2} \preceq \sqrt{r}\,\big(L_t^{1/4}\otimes R_t^{1/4}\big)

So 1/4=1/2×1/21/4 = 1/2\times 1/2, with one half from the geometric mean and the other from AdaGrad's square root. Shampoo's HtH_t is a Kronecker-structured matrix sitting on top of the full AdaGrad preconditioner. The authors point out that the small eigenvalues of the full-matrix preconditioner, the ones that matter most for preconditioning, do not vanish under this approximation.

The paper also offers an intuition. This exponent makes the overall step size decay as O(1/t)O(1/\sqrt{t}), a rate common in stochastic optimization. When gradient magnitudes are steady, LtL_t and RtR_t grow roughly linearly with the step count tt; L−1/4L^{-1/4} and R−1/4R^{-1/4} each contribute t−1/4t^{-1/4}, which together make exactly t−1/2t^{-1/2}.

This 1/41/4 is a by-product of the upper bound in the proof. Later implementations made the exponent tunable and often switch to 1/21/2; we'll come back to that in the discussion.

The tensor version

Convolution kernels are four-dimensional. The general form of Shampoo (Algorithm 2) keeps an ni×nin_i\times n_i preconditioner HtiH^i_t for each dimension ii of the tensor, whose statistic is the matrix obtained by contracting the gradient over all the other dimensions. The update multiplies by (Hti)−1/2k(H^i_t)^{-1/2k} one dimension at a time, where kk is the tensor's order. For a matrix, k=2k=2, which brings back −1/4-1/4.

Original Figure 1: a 3×4×5 gradient tensor G (yellow cube), with one preconditioning matrix for each of its three directions, blue L, red U and green R, each responsible for a single dimension.
Original Figure 1, Gupta et al., from PDF page 2, arXiv license, scholarly quotation.

Take the largest convolution kernel in the paper's CIFAR-100 experiment, (256,3,3,256)(256, 3, 3, 256). It has 589,824 parameters, and the full AdaGrad preconditioner would have about 3.5×10113.5\times10^{11} entries. Shampoo needs only four matrices, 2562+32+32+2562=131,090256^2+3^2+3^2+256^2 = 131{,}090 entries, with an exponent of −1/8-1/8.

The convergence guarantee and its conditions

The theory is proved in the online convex optimization framework (Theorem 7). With gradient rank at most rr, the regret is bounded by

∑t=1Tft(Wt)−∑t=1Tft(W⋆)≤2r D Tr(LT1/4) Tr(RT1/4)\sum_{t=1}^{T} f_t(W_t) - \sum_{t=1}^{T} f_t(W^\star) \le \sqrt{2r}\,D\,\mathrm{Tr}\big(L_T^{1/4}\big)\,\mathrm{Tr}\big(R_T^{1/4}\big)

DD is the largest distance between WtW_t and the optimum over the iterations. If the gradients' spectral norm is at most 1, each trace grows as T1/4T^{1/4} and the total regret is O(T)O(\sqrt{T}), already the best possible rate in online convex optimization. The tensor version (Theorem 10) works the same way, with rr replaced by the geometric mean of the per-dimension ranks.

Read the conditions carefully. The loss must be convex. DD can grow with TT, and keeping it bounded requires projecting WtW_t back into a ball at every step, using the norm induced by (Lt,Rt)(L_t, R_t). That projection is expensive, so the authors leave it out of the algorithm and accept a “slightly looser” bound. Deep networks are not convex; this proof is where the algorithm comes from and what motivated it, while the experiments are the evidence for how it does on neural networks.

Compromises in practice

The implementation makes two trade-offs. Each parameter tensor is handled on its own, so the overall preconditioner is block-diagonal and correlations between layers are simply ignored. When a dimension is too large (the threshold in the experiments is about 1200), that dimension automatically switches to the diagonal version (Algorithm 3 in Appendix A) and stores only the diagonal entries. On top of that, the experiments add two heuristics: the matrix roots are recomputed only every 20 to 100 steps, and the gradient gets momentum with a coefficient of 0.9. The authors say the former has “almost no impact” on accuracy.

Discussion

The experiments are small

Every experiment uses a batch size of 128, and the preconditioners are updated with the batch-averaged gradient. Image classification uses a 32-layer ResNet with 2.4M parameters and a small Inception with 1.65M parameters on CIFAR-10, plus a 55-layer ResNet without BatchNorm with 13.5M parameters on CIFAR-100; each optimizer sweeps 10 learning rates between 0.01 and 10. For this part the paper plots only training-loss curves, with no table comparing test accuracy.

The language model is a 9.8M-parameter Attention model on LM1B, whose largest tensor is (2000,256)(2000, 256).

Original Figure 4: test log-perplexity of the Attention model on LM1B against training steps, with the horizontal axis running to 5×10^5 steps. Red Shampoo is lowest from the start and ends around 4.18; green AdaGrad slowly falls to about 4.24; black Momentum stalls around 4.37; blue Adam stalls around 4.5.
Original Figure 4, Gupta et al., from PDF page 14, arXiv license, scholarly quotation.

The red line is lowest from its very first point and sits around 4.18 at 500k steps; green AdaGrad is around 4.24, black Momentum around 4.37, and blue Adam levels off near 4.5 early on.

The comparison in this figure isn't symmetric. Shampoo simply uses the default learning rate η=1.0\eta=1.0, while for the other methods the authors “explored various different settings,” without listing which values Adam was swept over. Adam trails AdaGrad by a wide margin on this Attention model. Our reading is that this sits poorly with the later experience of Transformers being trained almost universally with Adam, and the gap most likely comes from uneven tuning; factor that in when reading this figure.

How much more each step costs

The paper answers “won't the matrix operations be too slow?” with a table of steps per second (Tesla K40, batch 128):

ExperimentSGDShampooRatio
ResNet-32 (C10)2.1842.15198%
Inception (C10)3.6383.50696%
ResNet-55 (C100)1.2101.249103%
Attention (LM1B)4.9193.50971%

Compiled from Table 1 of the paper; the ratios are our calculation. Adam and AdaGrad are close to SGD and omitted.

On convolutional networks there's almost no difference, and ResNet-55 is even slightly faster than SGD. On LM1B, steps per second drop to 71% of SGD's, and the paper doesn't analyze why; the model's largest tensor is (2000,256)(2000, 256), and with the roughly 1200 threshold used in the experiments, the dimension of 2000 would switch to the diagonal version. These numbers were measured on models of only a few million parameters, with roots computed every 20 to 100 steps.

Shampoo after this paper

The 2018 original was a long way from large-scale training. The two versions that followed were mostly engineering.

Distributed Shampoo, Anil et al. (2020). The authors include all three from the original paper, and the paper is titled “Scalable Second Order Optimization for Deep Learning.” They found that in real models LtL_t and RtR_t have enormous condition numbers, so the matrix roots have to be computed in double precision, which is expensive on TPUs. The changes include:

  1. The accelerators only accumulate statistics each step; every NN steps, the inverse pp-th roots are computed asynchronously on the host CPUs, spread across all cores, without blocking the training loop;
  2. Coupled Newton iterations replace the SVD for the inverse roots, with warm starts;
  3. Layers with dimensions in the millions, such as embeddings and softmax, are preconditioned on one side only, and large fully connected layers are split into blocks preconditioned separately;
  4. The preconditioners are updated only every few hundred steps;
  5. Grafting: the direction comes from Shampoo and the step size from a tuned first-order method (for example, diagonal AdaGrad), grafted layer by layer;
  6. The exponent becomes a tunable hyperparameter, and the statistics use an exponential moving average.

On WMT'14 English-to-French, the Transformer needed half as many steps and 45% less wall-clock time (from about 12 hours down to 6.7 hours).

The PyTorch version, Shi et al. (2023). A Meta team rewrote it for data-parallel training on GPUs. Each worker preconditions only some of the parameter blocks, and the resulting directions are gathered with AllGather, so per-step wall-clock time is at most 10% more than with diagonal methods. The matrix roots switch to torch.linalg.eigh, and they found single precision is usually enough. Small dimensions are merged and large ones split into blocks, with a block size cap of 2048 in the ImageNet experiments; grafting, bias correction, decoupled weight decay and Nesterov are all included. On ResNet-50 for ImageNet, Shampoo reaches in 60 epochs the validation accuracy SGD-Nesterov reaches in 90, finishing 1.35 times faster in total wall-clock time.

AlgoPerf 2024. In August 2024, MLCommons announced the results of the first AlgoPerf training algorithms competition. The winner of the external tuning track was this PyTorch Distributed Shampoo, with a score of 0.78, about 28% faster than the NAdamW baseline on average. The post-competition analysis paper has the more interesting details. Of the eight workloads, it was fastest on only two, Criteo 1TB and ViT; on WMT it took more than twice as long as the fastest submission; and on ResNet it failed to reach the target reliably within the time budget. It won by being consistently decent on almost everything.

The Gemini 1.5 technical report from the same year also says that 1.5 Flash “is trained with higher-order preconditioned methods,” citing AdaGrad among other works without naming the method.

1/4 or 1/2

The exponent question was eventually settled. Anil et al. note in their appendix that treating the exponent as a hyperparameter sometimes works better, and their autoencoder experiments use L−1/2GR−1/2L^{-1/2}GR^{-1/2}; Shi et al.'s implementation suggests that for networks dominated by fully connected layers you can override the exponent to p=2p=2, again −1/2-1/2, or multiply the original exponent by 1.82. Morwani et al. (2024) explained why. L⊗RL\otimes R is exactly the result of one step of power iteration toward the best Kronecker approximation of the full AdaGrad statistic, and it lands very close to that best approximation. Since L⊗RL\otimes R is itself approximating ∑gg⊤\sum gg^\top, mimicking AdaGrad's −1/2-1/2 power means taking −1/2-1/2 on each side. Looking back from Morwani et al. (2024), we would sum up the original paper's 1/41/4 as an exponent produced by a bound that isn't tight enough.

The 1/41/4 wasn't wasted, though. Drop the accumulation and look only at the current step's gradient G=UΣV⊤G = U\Sigma V^\top:

(GG⊤)−1/4 G (G⊤G)−1/4=UΣ−1/2U⊤  UΣV⊤  VΣ−1/2V⊤=UV⊤(GG^\top)^{-1/4}\,G\,(G^\top G)^{-1/4} = U\Sigma^{-1/2}U^\top\; U\Sigma V^\top\; V\Sigma^{-1/2}V^\top = UV^\top

Every singular value is squashed to 1, which is exactly Muon's orthogonalized update. On Shampoo's first step, the statistics hold a single gradient, so with a small ε the direction it moves in is −UV⊤-UV^\top. Taking one step with the code above on a random 6×46\times4 gradient, the result differs from −UV⊤-UV^\top only by the offset ε introduces, mostly on the order of 10−410^{-4}. Keller Jordan's December 2024 post introducing Muon also notes that Shampoo without accumulation, plus momentum, is Muon; the difference is that Shampoo computes inverse fourth roots, while Muon approximates them cheaply with Newton–Schulz iterations.

Conclusion

Shampoo approximates full-matrix AdaGrad's unstorable preconditioner with the Kronecker product of two small matrices, cutting memory from m2n2m^2n^2 to m2+n2m^2+n^2, and proves O(T)O(\sqrt{T}) regret in the convex setting. The paper's experiments stop at around ten million parameters and mainly show that each step isn't much slower.

If you want to try it today, go straight to Meta's Distributed Shampoo. Start tuning from Adam grafting, an exponent of −1/2-1/2 and preconditioner updates every few dozen steps, and first measure how much the largest dimension in your model slows each step down. Keep the original code for understanding the algorithm.

Page 12 of the paper says, “We plan to implement Shampoo in PyTorch in the near future.” The version that went on to win AlgoPerf was indeed a PyTorch one, written by a Meta team five years later.