- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper provides a new theoretical framework for analyzing Shampoo, a 2nd order optimizer that has gained significant interest in the community. The paper then uses the proposed framework to justify the recently proposed KL variant that had until now only demonstrated empirical success against vanilla Shampoo. The paper also further proposes a new partially coupled variant of Shampoo informed by the theory, which provides an improvement to Shampoo at equal computational overhead. The partial coupling provides a neat tradeoff to the fully coupled method by using less computation but making more of an approximation in Kronecker factor estimation.
Critical strengths
- Insightful theoretical framework, filling a missing piece in the literature, providing a regret bound for empirically successful variants of Shampoo presented without such a guarantee. Further uses the framework to design a new optimizer that demonstrates the predictive power and thus utility of the theory.
- Strong empirical validation of the methods using AlgoPerf against winning methods and adequate hyperparameter coverage to be convincing
Critical weaknesses
- Missing comparison to KL-Shampoo. Since the paper starts by presenting it as a motivating algorithm, and equivalences were even established, why not include it?
- The claim to "introducing a Loewner order constraint" omits Mei, Moreno, and Walters (2023), "KrADagrad: Kronecker approximation-domination gradient preconditioned stochastic optimization" (in UAI), which uses the same Loewner order constraint to prove a regret bound with arbitrarily small for coupled Kronecker factorization in online convex optimization. The claim could be narrowed to using the Loewner order and as a first for an exact regret bound, closing the suboptimality gap in the literature.
- Minor:
- Tightness of the regret bound. The regret bound is big-Oh style, so this is admittedly difficult to demonstrate. However, the factor seems loose. Some additional interpretation of the factors could be helpful.
- Mentioning CASPR and SOAP in the abstract is somewhat misleading, as neither are compared. It appears CASPR could be feasibly addressed with the framework presented, but SOAP may not fit into it and isn't even mentioned again in main text.
- The upper bound on in Theorem 3.2 (from Lemma A.8) seems trivial. It is already stated that . As defined, , so the RHS is . Given this, it seems to add little over the Theorem 7 from the original Shampoo analysis in Gupta (2018).
Questions for authors
- How do the LogDet and specifically connect to regret? It seems like does not appear in Theorem 3.4, so that piece of the analysis, while interesting in theory, seems to serve more as motivation rather than a piece of the full framework.
Thank you for the careful review and the pointers. Short answers below.
KL-Shampoo comparison. The experiments target the partially coupled variant, which is the new algorithm and has Shampoo's cost (Sec 3.6), so Shampoo, the AlgoPerf winner, was the direct comparison (Sec 4.2). We agree KL-Shampoo belongs there and will add it on all 7 workloads with the same tuning budget in the final version.
KrADagrad. We will cite it in Sec 2 and narrow the claim (abstract, Sec 1) as you suggest. The domination constraint appears in KrADagrad. Ours gives the exact O(T) rate for coupled factors (Thm 3.4), closing the Tϵ gap, and ties the constraint to LogDet divergence (Sec 3.3), which yields the coupled updates and covers KL-Shampoo (Sec 3.5).
Minor 1 (the mn factor). It comes from bounding tr(LT1/2) by mλmax(LT), likewise for RT (Lemma A.17 Step 3, Lemma A.20), so it is the flat-spectrum worst case. Shampoo's Thm 7 gives the same mngrT under the same assumption. The data-dependent form (Thm A.14, A.15) is much smaller for decaying spectra, and we will say so after Thm 3.4.
Minor 2 (CASPR and SOAP). CASPR is compared in Table 1. The abstract names SOAP because it builds its eigenbasis from the same uncoupled L,R statistics as Shampoo, and we do not claim the regret analysis covers it. We will say this in Sec 2 and add SOAP as a baseline in the final version.
Minor 3 (bound on κ~). Fair point: under H~t⪰Ht that bound is implied by κ~≤1. The informative half of Lemma A.8 is κ=ρ(HT−1H~T), which satisfies κ+1/κ≤ST+2 (its Step 3) and gives tr(H~T1/2)≤κtr(HT1/2). So the regret is within a factor (1+κ)/2 of full-matrix Adagrad's bound (Lemma 3.1), and we will restate Thm 3.2 and Thm A.9 this way.
Minor 3 (relation to Gupta et al., Thm 7). Thm 7 is specific to Shampoo's uncoupled factors. Thm 3.2 holds for any preconditioner satisfying the Loewner constraint (Lemma A.10), which is how Thm A.14 and A.15 follow for coupled factors, and it measures the gap to full-matrix Adagrad through LogDet.
Question. The T rate needs only the Loewner constraint (Lemma A.10), so Thm 3.4 does not use the refinement (end of Sec 3.2). LogDet enters in the constant, through the κ bound above, and in the choice of preconditioner: minimizing the LogDet gap to H~t−1+gtgt⊤ over Kronecker products (Eq. 7) gives the coupled updates (Lemma 3.3).