acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Regularization through Coupled Kronecker Factoring

Abstract

Adaptive regularization based optimization algorithms have been widely used in deep learning. While diagonal preconditioners such as Adam and Adagrad are scalable for large numbers of parameters, methods utilizing Kronecker factoring have recently found success. Notably, Shampoo, CASPR, and SOAP share identical axes preconditioners which are developed independently to optimize regret. However, there remain theoretical gaps regarding how to develop these preconditioner factors jointly and in an online fashion to minimize regret in online convex optimization. To address this, we first build a novel Loewner order constraint for approximate preconditioners, when followed, leads to a regret upper bound in online convex optimization. We show a correlation between LogDet matrix divergence of approximate preconditioner with full-matrix Adagrad and our regret upperbound. We then utilize both the Loewner order constraint and LogDet divergence to develop a Kronecker-structured preconditioner with factors jointly optimized to approximate full-matrix Adagrad. We show that a fully coupled Kronecker product is equivalent to Shampoo-KL, an existing algorithm, and propose a novel partially coupled version which uses the same number of matmuls as Shampoo, unlike Shampoo-KL. The Loewner order constraint and further analysis of the coupling between the axes preconditioners sets us up to show that fully coupled and partially coupled optimizers are optimal in online convex optimization. Our method improves generalization by up to 8% and accelerates training, improving time-to-target by up to 20%.

Primary area:
optimization
Keywords:
Adaptive Regularization, Online Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_2HSAOpenReview ↗
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 O(T1/2+ϵ)O(T^{1/2+\epsilon}) regret bound with arbitrarily small ϵ\epsilon 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 O(T)O(\sqrt{T}) regret bound, closing the ϵ\epsilon 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 mnmn 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 κ~\tilde\kappa in Theorem 3.2 (from Lemma A.8) seems trivial. It is already stated that κ~≤1\tilde\kappa\le 1. As defined, SˉT≥St≥0\bar{S}_T \ge S_t \ge 0, so the RHS is ≥2\ge 2. 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 κ~\tilde\kappa specifically connect to regret? It seems like κ~\tilde\kappa 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.
1 comment

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)O(\sqrt{T}) rate for coupled factors (Thm 3.4), closing the TϵT^{\epsilon} 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 mnmn factor). It comes from bounding tr(LT1/2)\mathrm{tr}(L_T^{1/2}) by mλmax⁡(LT)m \sqrt{\lambda_{\max}(L_T)}, likewise for RTR_T (Lemma A.17 Step 3, Lemma A.20), so it is the flat-spectrum worst case. Shampoo's Thm 7 gives the same mngrTmn g \sqrt{rT} 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,RL, 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 κ~\tilde\kappa). Fair point: under H~t⪰Ht\tilde H_t \succeq H_t that bound is implied by κ~≤1\tilde\kappa \le 1. The informative half of Lemma A.8 is κ=ρ(HT−1H~T)\kappa = \rho(H_T^{-1} \tilde H_T), which satisfies κ+1/κ≤ST+2\kappa + 1/\kappa \le S_T + 2 (its Step 3) and gives tr(H~T1/2)≤κtr(HT1/2)\mathrm{tr}(\tilde H_T^{1/2}) \le \sqrt{\kappa} \mathrm{tr}(H_T^{1/2}). So the regret is within a factor (1+κ)/2(1+\sqrt{\kappa})/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\sqrt{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 κ\kappa bound above, and in the choice of preconditioner: minimizing the LogDet gap to H~t−1+gtgt⊤\tilde H_{t-1} + g_t g_t^\top over Kronecker products (Eq. 7) gives the coupled updates (Lemma 3.3).

Reviewer_gzzgOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies Kronecker approximations to full-matrix Adagrad. It introduces a Loewner order constraint and uses LogDet divergence to derive coupled updates for the Kronecker factors. The paper proposes fully and partially coupled variants, where the fully coupled method is equivalent to Shampoo-KL. The partially coupled method has the same number of matrix multiplications as Shampoo. The paper also provides O(sqrt(T)) regret bounds and experiments on 7 AlgoPerf benchmarks, showing improvements over Shampoo and CASPR.

Critical strengths
  1. The Loewner order constraint provides an interesting way to analyze approximate preconditioners. The connection with LogDet divergence and the derivation of coupled Kronecker updates are also useful.

  2. The partially coupled method is interesting as it introduces coupling without additional matrix multiplications compared to Shampoo.

  3. The experimental results are promising on some benchmarks, particularly LibriSpeech Conformer and DeepSpeech, where the method improves both final performance and time-to-target.

Critical weaknesses
  1. I am not entirely convinced by the theoretical contribution. The fully coupled method is already proposed in Shampoo-KL. While the paper provides O(sqrt(T)) regret bounds, this rate is also achievable by simpler methods such as OGD. Moreover, the final bound has a large dependence on the matrix dimensions and does not clearly explain why coupling should perform better than Shampoo. The LogDet refinement in Theorem 3.2 is also not used to establish the final regret rate.

  2. The experimental results are not entirely convincing. Table 1 reports a single value for each method without variance across seeds. Some improvements are very small, such as 0.12361 vs 0.12362 on Criteo. The method is also worse on ResNet-50 and WMT test metrics. Moreover, there is no comparison with Shampoo-KL or SOAP, which seem to be important baselines for this work.

Questions for authors
  1. Do the theoretical guarantees continue to hold for the practical implementation with EMA and c_t = 1? If not, how much do the theoretical results explain the observed improvements?

  2. What preconditioner exponents are used for Shampoo and the proposed method? Are the results still similar when the exponents are matched?

  3. In Appendix A.10, the update for R_t appears to divide the entire expression by m. Would this not cause the previous statistics to shrink repeatedly? Is this a typo or the actual implementation?

  4. Can the authors provide results with multiple seeds and include Shampoo-KL or SOAP as baselines? If the partially coupled method still performs better or achieves similar performance with lower overhead, this would strengthen the paper considerably.

1 comment

Thank you for the review. Short answers below.

W1 (novelty). Shampoo-KL proposes the fully coupled update without a regret guarantee (Sec 2, Sec 3.5). We prove the first O(T)O(\sqrt{T}) bounds for coupled factors (Thm 3.4) and add the partially coupled method at Shampoo's cost (Sec 3.6).

W1 (rate, dimension). O(T)O(\sqrt{T}) is minimax optimal in OCO, so OGD, Adagrad and Shampoo share it and differ in the data-dependent factor, here tr(LT1/2)tr(RT1/2)\mathrm{tr}(L_T^{1/2}) \mathrm{tr}(R_T^{1/2}) (Thm A.14, A.15). Its mnmn worst case (Lemma A.17, A.20) is the same mngrTmn g \sqrt{rT} that Shampoo's Thm 7 gives under the same assumption, and it is much smaller for decaying spectra.

W1 (why coupling). Shampoo solves subproblem (7) with the other factor frozen at identity (after Lemma 3.3). The coupled update minimizes that LogDet gap at each step, and Thm 3.2 ties it to the regret constant (see the κ\kappa form in our reply to Reviewer 2HSA). The rate needs only Lemma A.10, so Thm 3.4 skips the refinement (end of Sec 3.2).

W2 (seeds). Table 1 reports the best of 50 random hyperparameter trials per optimizer (Sec 4.1, search space in Table 2), with the same budget for every method, and Fig 1 is the median over 3 seeds (Sec 4.2). We will add mean and standard deviation over seeds to Table 1 in the final version.

W2 (size of gains). Criteo is flat across optimizers (all within 0.2%), with ours ahead of Shampoo. Over Shampoo we gain 3 to 8% WER on Conformer, about 5% on DeepSpeech and 2 to 3% on GNN (Table 1). On WMT we are within 0.15 BLEU and reach the target 18% faster (Fig 1). Only on ResNet-50 does coupling help in neither Table 1 nor Fig 1.

Q1 (ct=1c_t = 1). Yes. The proofs use ct≤1c_t \le 1, so ct=1c_t = 1 (App. A.10) only enlarges RtR_t. The Loewner constraint (Lemma A.12, A.19) still holds and Thm 3.2 applies through Lemma A.10, with at most an extra log⁡T\sqrt{\log T} factor (the harmonic sum in App. A.8.1).

Q1 (EMA). The regret analysis uses cumulative sums, and EMA (App. A.10) is the usual practical counterpart, as for Adam and Shampoo. The mechanism is the same in both: coupling fits the gradient second moment more closely in LogDet than Shampoo's uncoupled factors (Lemma 3.3). App. A.5 converts the regret rate to a non-convex stationarity rate.

Q2. Shampoo uses its standard L−1/4,R−1/4L^{-1/4}, R^{-1/4} (exponent_override = 0, Table 4) and ours uses Lt−1/2,Rt−1/2L_t^{-1/2}, R_t^{-1/2} (Thm A.14, App. A.10). These are matched where it matters: both apply the power −1/2-1/2 to their approximation of HtH_t, which is L1/2⊗R1/2L^{1/2} \otimes R^{1/2} for Shampoo and Lt⊗RtL_t \otimes R_t for ours (Thm 3.2). We will add Shampoo with exponent 1/2 in the final version.

Q3. This is a typo in App. A.10, thank you for catching it. The 1/m1/m multiplies only the new term, Rt=β2ctRt−1+(1−β2)Gt⊤Lt−1Gt/mR_t = \beta_2 c_t R_{t-1} + (1-\beta_2) G_t^\top L_t^{-1} G_t / m, as in Eq. (8). History decays by β2ct\beta_2 c_t only, so there is no repeated shrinkage.

Q4. Yes, we will report multiple seeds and add both Shampoo-KL and SOAP as baselines in the final version. The lower-overhead part holds by construction: the partially coupled update uses Shampoo's 4 matmuls per step (Sec 3.6), two fewer than the fully coupled one (Sec 1).

Reviewer_L6X7OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies coupled Kronecker approximations of full-matrix AdaGrad. It uses a LogDet objective to derive fully and partially coupled updates, and proves O(T)O(\sqrt{T}) regret bounds for specific cumulative and regularized variants. It also evaluates a practical partially coupled optimizer on several neural-network training tasks.

Critical strengths
  1. The paper studies an important problem: how to design structured preconditioners that balance optimization performance and computational cost.

  2. The paper provides regret bounds for both fully and partially coupled variants under the stated assumptions.

  3. The partially coupled design offers a simple way to reduce computation, and the experiments cover several tasks and model architectures.

Critical weaknesses
  1. The contribution beyond KL-Shampoo is not sufficiently clear. The paper acknowledges its connection to KL-Shampoo [1], but the added value needs stronger support. Gaussian KL and the LogDet divergence used here are equivalent up to a constant, and KL-Shampoo already uses coupled factor updates. Eq. (9) changes the online target and update order, but the benefit of these changes is not demonstrated. The paper also lacks a direct empirical comparison with KL-Shampoo.

  2. The theoretical guarantees do not directly cover the practical implementation. The LogDet-derived updates, the updates analyzed in the regret proofs, and the practical updates are different. The O(T)O(\sqrt{T}) results use cumulative updates with specific rank-dependent scaling. In contrast, Appendix A.10 uses EMA updates with ct=1c_t=1 and different regularization. The paper does not establish the same guarantee for this practical version, which limits the connection between the theory and the experimental results.

  3. The partially coupled design lacks important ablation studies. The paper does not compare the current partial variant with a version that reverses the coupling direction. It also lacks a controlled comparison between fully and partially coupled updates. These experiments are needed to understand whether the chosen side matters and what performance is gained or lost by reducing the coupling.

[1] Lin et al. Understanding and Improving Shampoo and SOAP via Kullback-Leibler Minimization. ICLR 2026.

Questions for authors
  1. Could the authors clearly state the algorithmic and theoretical contributions beyond KL-Shampoo and provide a direct comparison under the same training and tuning budgets? Please also clarify why KL-Shampoo is described as concurrent work.

  2. Could the authors evaluate the method in more settings? For example, an LLM pretraining experiment and comparisons with additional baselines, such as Muon and KL-Shampoo, would be useful.

  3. Which theoretical results apply to the practical algorithm in Appendix A.10? How do EMA, ct=1c_t=1, the scaling changes, and the practical damping affect the assumptions used in the proofs? If the current guarantees do not cover this implementation, please clarify their scope and restate the contribution relative to KL-Shampoo.

  4. Could the authors provide a controlled ablation comparing the current partial variant, the partial variant with the coupling direction reversed, the fully coupled variant, and an uncoupled baseline? Please keep the other implementation choices and tuning budgets fixed, and report both training performance and wall-clock cost.

  5. The related work omits recent theoretical studies of structured and one-sided preconditioners [1–3]. Could the authors discuss the connections between their work and these papers?

[1] Xie et al. A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent. ICLR 2026.

[2] Xie et al. Structured Preconditioners in Adaptive Optimization: A Unified Analysis. ICML 2025.

[3] An et al. ASGO: Adaptive Structured Gradient Optimization. Neurips 2025.

1 comment

Thank you for the detailed review. Short answers to each point below.

W1, Q1. We agree Gaussian KL and LogDet coincide, and Sec 3.5 already equates the fully coupled update (Eq. 9) with KL-Shampoo. We add the first O(T)O(\sqrt{T}) regret bounds for coupled Kronecker factors (Thm 3.4, proofs in App. A.7, A.8), which KL-Shampoo lacks, and the new partially coupled method (Eq. 8) at Shampoo's 4 matmuls per step (Sec 3.6).

W1 (benefit of Eq. 9). The online target H~t−1+gtgt⊤\tilde H_{t-1} + g_t g_t^\top in Eq. (7) is the right-hand side of the Loewner constraint (Eq. 10, Lemma A.10), so fitting it step by step is what makes the regret proof possible. Updating LtL_t first also lets RtR_t reuse Lt−1/2GtL_t^{-1/2} G_t, which the step computes anyway (Sec 3.6).

Q1 (comparison, "concurrent"). We will add KL-Shampoo on all 7 AlgoPerf workloads with the same 50-trial budget (Sec 4.1) in the final version. We derived the fully coupled update independently, hence "concurrent" in Sec 3.5. It is now published (ICLR 2026), so we will call it prior work throughout, as the abstract and Sec 2 already do.

Q2. AlgoPerf fixes the workloads, targets and budgets (Table 3) and spans vision, speech, translation, graphs and recommendation, including transformers (ViT, WMT, Conformer). We will add an LLM pretraining experiment and Muon, KL-Shampoo and SOAP baselines in the final version.

W2, Q3 (three updates). All three read Rt=atRt−1+bGt⊤Lt−1GtR_t = a_t R_{t-1} + b G_t^\top L_t^{-1} G_t for the partially coupled method. Here ata_t is the mean eigenvalue of Lt−1/2Lt−1Lt−1/2L_t^{-1/2} L_{t-1} L_t^{-1/2} in the LogDet solution (Eq. 8), its largest eigenvalue in the regret proof (Eq. 11), and 1 in practice (App. A.10). The constant bb only rescales RtR_t, which the learning rate and grafting absorb.

Q3 (ct=1c_t = 1 and damping). The proofs use ct≤1c_t \le 1, so ct=1c_t = 1 only enlarges RtR_t. The Loewner constraint (Lemma A.12, A.19) still holds and Thm 3.2 applies through Lemma A.10, at the price of at most a log⁡T\sqrt{\log T} factor (the harmonic sum in App. A.8.1). Damping corresponds to the diagonal regularization analyzed in Thm 3.4 (proofs in App. A.8.4).

Q3 (EMA and scope). The regret results (Sec 3.4) are for cumulative statistics, and EMA (App. A.10) is their standard practical counterpart, just as Shampoo is analyzed with sums and run with EMA. We will state this scope in Sec 4. KL-Shampoo has no guarantee in either form, so our contribution relative to it stands as in W1.

W3, Q4 (uncoupled baseline). Shampoo is the uncoupled case: set the other factor to identity in Lemma 3.3 (see also App. A.9). It is already compared under the same code, blocking, grafting and tuning budget (Table 1, Fig 1, settings in Table 4).

W3, Q4 (direction, full coupling). The reversed direction is our method applied to Gt⊤G_t^\top, so the theory (Lemma A.12, Thm A.14) and the cost (Sec 3.6) are unchanged. We will add the reversed and fully coupled variants with wall-clock in the final version.

Q5. We will add all three to Sec 2. Xie et al. (ICML 2025, ICLR 2026) need preconditioner sets that form a matrix subalgebra, which covers one-sided L⊗IL \otimes I (ASGO too) but not two-sided L⊗RL \otimes R. Ours (Eq. 8) is the one-sided method when Rt=IR_t = I, plus a right factor fitted to Lt−1/2GtL_t^{-1/2} G_t that the Loewner constraint (Lemma A.10) lets us analyze.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.