Source
Gupta, Koren and Singer (2018), LIT-621 (ICML 2018), read in NOTE-480 from arXiv v2: sections 1–6 and Appendix A, with the proofs of Lemmas 8–9 and Theorem 7 followed; the tensor proofs in Appendices B and C skimmed.
What was actually shown
The update (Algorithm 1). For a weight matrix W with gradients G_t, L = εI + Σ G Gᵀ and R = εI + Σ GᵀG, and W ← W − η L^{-1/4} G R
Lemma 9. For G of rank at most r, with g its vectorisation, (1/r) g gᵀ ⪯ I_m ⊗ (GᵀG) and (1/r) g gᵀ ⪯ (G Gᵀ) ⊗ I_n.
Lemma 8. εI_{mn} + (1/r) Σ g_t g_tᵀ ⪯ (εI_m + Σ G_t G_tᵀ)^{1/2} ⊗ (εI_n + Σ G_tᵀ G_t)^{1/2}, by the operator monotone geometric mean of commuting PSD matrices (Ando et al.).
Theorem 7. Regret ≤ √(2r) D Tr(L_T^{1/4}) Tr(R_T^{1/4}). With ‖G_t‖₂ ≤ 1 and ε = 0 the traces are at most m T^{1/4} and n T^{1/4}, so regret is O(√T). Theorem 10 gives the same for order-k tensors, with power −1/2k per dimension; Theorem 13 a diagonal variant.
What could have come out otherwise. The Kronecker product of the two small statistics could have failed to dominate the full statistic in some directions, in which case the factored preconditioner would not inherit AdaGrad’s guarantee. Lemma 8 shows it dominates, up to the rank.
What this does not say
- That Shampoo trains deep networks better. That evidence is four curves without repeated seeds; on LM1B Shampoo ran at its default while only the baselines were swept (C3, weak to moderate).
- That the bound is uniform. D, the largest distance from the optimum, is uncontrolled without the projection step the implementation omits.
- That the Kronecker structure comes from the network. Lemma 8 is pure matrix analysis with no statistical model of the network. Class-indexed Kronecker structure in a Fisher matrix (THEORY-085) is structure in a different, model-defined object.
- That −1/4 is the right exponent for training. It comes from the analysis.
- Anything about curvature across layers. The preconditioner is block-diagonal over tensors by construction.
Connections
- K-FAC (LIT-622) is the other factored preconditioner, contrasted in §1.2 and not compared experimentally. The record’s account of where its class-averaged factors go wrong is THEORY-085.
- Natural gradient is defined relative to the Fisher metric (THEORY-082); Shampoo’s statistics are gradient second moments, not a Fisher, and its guarantee is a regret bound, not Fisher efficiency.
- LIT-621 carries an instruction for practice and is flagged
anthology-candidate; this document states only the mathematical result.