acceptodds
Under review as a conference paper at ICLR 2027

Convergence of Rotation-based Matrix Optimizers: A Unified Analysis of SOAP, Conda, and SPlus

Abstract

In this work, we develop a unified theoretical framework for analyzing the convergence of rotation-based matrix optimizers, which apply orthogonal transformations to map the momentum into a rotated space, perform coordinate-wise or normalized updates there, and then rotate the updates back. Our framework encompasses prominent matrix optimizers, including SOAP, Conda, and truncated SPlus, as well as matrix-parameterized Adam as a special case. As our main result, we establish, for the first time, the convergence rate of SOAP with sharp dimension dependence, as well as the convergence rate of Adam measured by the nuclear norm of the gradient. Our framework also covers a more general variant of rotation-based optimizers that permits arbitrary orthogonal rotation matrices, which may depend on the current stochastic gradient at each iteration. Technically, our framework leverages a row-column trace control argument that converts elementwise bounds into bounds on two diagonal control matrices, thereby improving the dimension dependence of the resulting bound.

Primary area:
optimization
Keywords:
LLM Optimizers, Rotation-based Matrix Optimizers, SOAP, Convergence

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_bPvrOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies rotation-based matrix optimizers, which rotate the momentum into another basis, take a coordinate-wise normalized step there, and rotate the step back. It first brings these methods into one form. In Algorithm 1 the update is Xk+1=Xk−ηPkΦkQk⊤X_{k+1}=X_k-\eta P_k\Phi_kQ_k^\top with Φk=Pk⊤MkQk/Dk\Phi_k=P_k^\top M_kQ_k/D_k, where MkM_k is the momentum, PkP_k and QkQ_k are orthogonal matrices that may depend on the current stochastic gradient, and DkD_k is a positive normalizer applied entry by entry, which the analysis requires to be at least δ\delta. SOAP, Conda and SPlus differ only in the choice of PkP_k, QkQ_k and DkD_k, and Adam is the case Pk=IP_k=I, Qk=IQ_k=I.

For this common form the paper derives a bound of one general shape. The assumptions are LL-smoothness, an unbiased gradient oracle and noise variance at most σ2\sigma^2, all in the Frobenius norm. Lemma 1 builds on the momentum argument of the AdamW analysis in [5] and bounds the normalized rotated gradient for any rotations and any normalizer with Dk≥δD_k\ge\delta, using that orthogonal rotations do not change the Frobenius and nuclear norms. Lemma 2, the row-column trace control, bounds DkD_k by row maxima bib_i and column maxima cjc_j with bicj≥Dk,ij\sqrt{b_ic_j}\ge D_{k,ij} and, through a Schatten-Hölder step, reduces the average nuclear norm of the gradient to the quantity of Lemma 1 and the traces of diag(b)\mathrm{diag}(b) and diag(c)\mathrm{diag}(c). Once these traces are bounded for a given normalizer, the result takes the form 1K∑k=1KE∥∇f(Xk)∥∗≤Cm+n(σ^2LΔ/K)1/4\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\Vert\nabla f(X_k)\Vert_{\ast}\le C\sqrt{m+n}(\hat\sigma^2L\Delta/K)^{1/4}, where Δ=f(X1)−f∗\Delta=f(X_1)-f^{\ast} and σ^2=max⁡{σ2,LΔ/(Kγ2)}\hat\sigma^2=\max\lbrace\sigma^2,L\Delta/(K\gamma^2)\rbrace.

The special cases are then worked out. For a generalized SOAP with ε=τσ^2/(m+n)\varepsilon=\tau\hat\sigma^2/(m+n) and δ=ε\delta=\sqrt{\varepsilon}, Theorem 1 gives C=2+16/τC=2+16/\sqrt{\tau}. The same bound covers SOAP, Conda and, with Pk=IP_k=I and Qk=IQ_k=I, Adam. The authors present it as the first rate for SOAP and the first nuclear-norm rate for Adam, of the same order as the rate for AdamW-style Shampoo in [4]. For a truncated SPlus, in which the sign of each entry xx is replaced by x/max⁡{∣x∣,δ}x/\max\lbrace\vert x\vert,\delta\rbrace with δ=τσ^/m+n\delta=\tau\hat\sigma/\sqrt{m+n}, Theorem 2 gives C=4+11/τC=4+11/\tau. Appendix D replaces the row-column control by a one-sided one and obtains min⁡{m,n}\sqrt{\min\lbrace m,n\rbrace} in place of m+n\sqrt{m+n} at ε=τσ^2/min⁡{m,n}\varepsilon=\tau\hat\sigma^2/\min\lbrace m,n\rbrace (Theorem 3). There are no experiments.

Critical strengths

The paper gives a convergence analysis for four methods: SOAP, Conda, a truncated version of SPlus and, as a special case, Adam with matrix-valued parameters. I went through the proofs of Lemmas 1, 2, 3, 7, 8, 9 and 10 and of Theorems 1 to 3 and could not find an error. The paper is short and easy to follow, and Algorithm 1 puts these methods into one notation. Rotations that depend on the current stochastic gradient, which SPlus and Conda need, are handled correctly. The Limitations paragraph is open about the truncation of SPlus, the lower bound on DkD_k and the problem-dependent parameters, and Appendix D states the one-sided variant.

Critical weaknesses

W1. The claimed contributions are overstated and do not match what the paper shows.

The paper presents its analysis as unified, but it is not unified in the usual sense of the word. A unified analysis proves one theorem under a parametric assumption, and the rate of each method in the framework follows as a corollary that recovers or improves the known rate for that method [1], [2]. Here only Lemma 1 and Lemma 2 are shared. The bound on the traces, which sets the rate, is proved separately for each normalizer (Lemma 3 and Lemma 9), and Theorems 1, 2 and 3 are assembled one by one. The bounds of the framework do not recover the known rate of the simplest method that Algorithm 1 contains. With Pk=IP_k=I, Qk=IQ_k=I and the constant normalizer Dk≡δD_k\equiv\delta, Algorithm 1 is plain SGD with momentum and step (1−θ)/(2L)(1-\theta)/(2L). For this algorithm the paper's own Lemma 1 gives ∑kE∥∇f(Xk)∥F2≤7KR2\sum_k\mathbb{E}\Vert\nabla f(X_k)\Vert_F^2\le7KR^2 with R=(σ^2LΔ/K)1/4R=(\hat\sigma^2L\Delta/K)^{1/4}, so 1K∑kE∥∇f(Xk)∥F≤7R\frac{1}{K}\sum_k\mathbb{E}\Vert\nabla f(X_k)\Vert_F\le\sqrt{7}R, and with ∥A∥∗≤min⁡{m,n}∥A∥F\Vert A\Vert_{\ast}\le\sqrt{\min\lbrace m,n\rbrace}\Vert A\Vert_F the nuclear-norm bound 7min⁡{m,n}R\sqrt{7\min\lbrace m,n\rbrace}R. The route of the framework, Lemma 1 with Lemma 2 and bi=cj=δb_i=c_j=\delta, gives 3.5(m+n)R\sqrt{3.5(m+n)}R for the same algorithm. Read in the Frobenius norm through ∥A∥F≤∥A∥∗\Vert A\Vert_F\le\Vert A\Vert_{\ast}, this is (m+n)/2\sqrt{(m+n)/2} times worse than the standard rate, and in the nuclear norm it is worse for every non-square matrix.

The final bounds of Theorems 1 to 3 contain only mm, nn, LL, σ^\hat\sigma, Δ\Delta, KK and a numerical factor τ∈(0,1]\tau\in(0,1], with δ\delta set to ε=τ/(m+n)σ^\sqrt{\varepsilon}=\sqrt{\tau/(m+n)}\hat\sigma on page 8. The rotations PkP_k and QkQ_k, the form of DkD_k and the parameter β\beta do not enter, and SOAP and the truncated SPlus differ only in the numerical constant, 2+16/τ2+16/\sqrt{\tau} against 4+11/τ4+11/\tau. It seems to me that the reason is visible in vectorized form. The update is momentum SGD with the preconditioner (Qk⊗Pk)Diag(1/vecDk)(Qk⊗Pk)⊤(Q_k\otimes P_k)\mathrm{Diag}(1/\mathrm{vec}D_k)(Q_k\otimes P_k)^\top, the rotation fixes only its eigenvectors, and the proofs use only bounds on its eigenvalues. The theorems therefore hold for every rotation, including a random one or one chosen to make the method as slow as possible. A bound that holds for the worst rotation cannot be better than the rate of that rotation, so it cannot show any gain from a good rotation. But the choice of basis is the core of SOAP, Conda and SPlus, and it matters in practice [3]. Since the bound is the same for all rotations, it does not show which rotation is better or why SOAP outperforms Adam

Contribution 3, "the first nuclear-norm convergence rate for Adam with matrix-valued parameters", is overstated as well. Writing AA as the sum of the mnmn rank-one matrices Aijeiej⊤A_{ij}e_ie_j^\top gives ∥A∥∗≤∑i,j∣Aij∣\Vert A\Vert_{\ast}\le\sum_{i,j}\vert A_{ij}\vert, so the ℓ1\ell_1 bound for AdamW of [5], quoted on page 8, is already a nuclear-norm bound of order mnR\sqrt{mn}R. At the value ε=σ^2/(mn)\varepsilon=\hat\sigma^2/(mn) used in [5], which Theorem 1 allows with τ=(m+n)/(mn)\tau=(m+n)/(mn), Theorem 1 gives (2m+n+16mn)R(2\sqrt{m+n}+16\sqrt{mn})R, again of order mnR\sqrt{mn}R. The factor m+n\sqrt{m+n} therefore comes only from taking ε\varepsilon larger by mn/(m+n)mn/(m+n).

[1] Eduard Gorbunov, Filip Hanzely, Peter Richtárik. A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent. AISTATS 2020.

[2] Filip Hanzely, Peter Richtárik. One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods. arXiv:1905.11266, 2019.

[3] Tianyue H. Zhang et al. Understanding Adam Requires Better Rotation Dependent Assumptions. NeurIPS 2025.

[4] Huan Li, Yiming Dong, Zhouchen Lin. Convergence Rate Analysis of the AdamW-style Shampoo: Unifying One-Sided and Two-Sided Preconditioning. ICML 2026.

[5] Huan Li, Yiming Dong, Zhouchen Lin. On the O(d/K1/4)O(\sqrt{d}/K^{1/4}) Convergence Rate of AdamW Measured by ℓ1\ell_1 Norm. NeurIPS 2025.

Questions for authors

Q1 Is there a choice of PkP_k and QkQ_k for which the framework gives a strictly better bound than Pk=IP_k=I, Qk=IQ_k=I? If SOAP works because of the eigenbasis, which assumption, for example a smoothness or noise constant measured in the rotated basis, would let the analysis show it?

Q2 On page 8 the paper says that ε\varepsilon can be "chosen much smaller than δ2\delta^2, consistent with practical settings". Lemma 1 uses Dk,ij≥δD_{k,ij}\ge\delta along the whole path and δ\delta sets the step, so this seems to need Vk,ij≥cσ^2/(m+n)V_{k,ij}\ge c\hat\sigma^2/(m+n), for some constant cc, for all mnmn entries and at all iterations. How is this compatible with the gradient going to zero, and under which conditions does the claim hold?

3 comments
AuthorsOpenReview ↗

Part 1: Response to the weakness

We sincerely thank the reviewer for their valuable suggestions. Below are our responses to the major concerns.

Weakness 1: Overstate the contribution and the analysis is not unified in the usual sense of the word.

Reply: Following the reviewer's suggestion, we can present our analysis in a unified framework with the following single meta-theorem in the parametric form of Gorbunov et al. (2020) and Hanzely & Richtarik (2019):

Meta-theorem. Suppose that Assumptions 1-3 and condition Dk,i,j≥δD_{k,i,j}\geq\delta hold, and the control matrices Bk,CkB_k,C_k satisfy the parametric trace-control condition

∑k=1KE[trBk]≤K(c1mσ^+c2mh)+c3SK\sum_{k=1}^KE[tr B_k]\leq K\big(c_1\sqrt{m}\hat\sigma+c_2mh\big)+c_3 S_K and ∑k=1KE[trCk]≤K(c1nσ^+c2nh)+c3SK\sum_{k=1}^K E[tr C_k]\leq K\big(c_1\sqrt{n}\hat\sigma+c_2nh\big)+c_3 S_K,

where h≤σ^m+nh\leq\frac{\hat\sigma}{\sqrt{m+n}} is the regularization scale. Let σ^2=max⁡(σ2,L(f(X1)−f∗)Kγ2)\hat\sigma^2=\max\left(\sigma^2,\frac{L\left(f(X_1)-f^{\ast}\right)}{K\gamma^2}\right) with any γ∈(0,1]\gamma\in(0,1], 1−θ=L(f(X1)−f∗)Kσ^21-\theta=\sqrt{\frac{L\left(f(X_1)-f^{\ast}\right)}{K\hat\sigma^2}}, and η=δ2(f(X1)−f∗)4LKσ^2\eta=\sqrt{\frac{\delta^2\left(f(X_1)-f^{\ast}\right)}{4LK\hat\sigma^2}}. Then for the general Algorithm 1, we have

1K∑k=1KE[∥∇f(Xk)∥∗]≤C(m+n+σ^δ)σ^2L(f(X1)−f∗)K4\frac{1}{K}\sum_{k=1}^KE[\lVert\nabla f(X_k)\rVert_*]\leq C\left(\sqrt{m+n}+\frac{\hat{\sigma}}{\delta}\right) \sqrt[4]{\frac{ \hat{\sigma}^{2} L\left(f\left(X_{1}\right)-f^{*}\right)}{K}},

where c1,c2,c3c_1,c_2,c_3 are positive constants and C=127(c12+c22)+7c3C=\frac{1}{2}\sqrt{7\left(\frac{c_1}{\sqrt{2}}+\frac{c_2}{2}\right)}+7\sqrt{c_3}.

Lemma 3 (generalized SOAP, Conda, Adam) verifies the condition with (c1,c2,c3,h)=(2,1,4,ε)(c_1,c_2,c_3,h)=(\sqrt{2},1,4,\sqrt{\varepsilon}); Lemma 9 (truncated SPlus) verifies it with (c1,c2,c3,h)=(213,2,1,δ)(c_1,c_2,c_3,h)=(2\sqrt{13},2,1,\delta); Theorems 2-3 then follow as corollaries. This is exactly ''one theorem under a parametric assumption, with each method's rate as a corollary.''

Weakness 2: The bounds of the framework do not recover the known rate of the simplest SGD with momentum.

Reply: We agree with the reviewer's computation for the two-sided control. However, the gap is an artifact of the two-sided route, and our one-sided control (Remark 1, Appendix D of our original submitted manuscript) removes it exactly, which replaces m+nm+n by min⁡(m,n)\min(m,n) in the theorems. For the special case of X∈Rm×1X\in R^{m\times1}, where min⁡(m,n)=1\min(m,n)=1, under the setting of Theorem 4 in Appendix D, we have ε=τσ^2min⁡(m,n)=σ^2\varepsilon=\frac{\tau\hat\sigma^2}{\min(m,n)}=\hat\sigma^2 with τ=1\tau=1, δ=σ^\delta=\hat\sigma, η=f(X1)−f∗4LK\eta=\sqrt{\frac{f(X_1)-f^{\ast}}{4LK}}, and the convergence rate

1K∑k=1KE[∥∇f(Xk)∥∗]≤(3min⁡(m,n)+17σ^δ)σ^2L(f(X1)−f∗)K4=20σ^2L(f(X1)−f∗)K4.\frac{1}{K}\sum_{k=1}^KE[\lVert\nabla f(X_k)\rVert_*]\leq \left(3\sqrt{\min(m,n)}+17\frac{\hat{\sigma}}{\delta}\right)\sqrt[4]{\frac{ \hat{\sigma}^{2} L\left(f\left(X_{1}\right)-f^{\ast}\right)}{K}}=20\sqrt[4]{\frac{ \hat{\sigma}^{2} L\left(f\left(X_{1}\right)-f^{\ast}\right)}{K}}.

Since ∥X∥∗=∥X∥F\lVert X\rVert_*=\lVert X\rVert_F for X∈Rm×1X\in R^{m\times1}, our framework recovers the convergence rate of SGD measured by the vector Frobenius norm. This applies to SGD with momentum (setting Dk,i,j=δD_{k,i,j}=\delta, Pk=IP_k=I, and Qk=1Q_k=1), vector Adam (setting Pk=IP_k=I and Qk=1Q_k=1), and one-sided vector SOAP (setting Qk=1Q_k=1). However, a larger ε\varepsilon makes Adam in the rotated space of SOAP behave more like SGD. Accordingly, we did not regard the min⁡(m,n)\min(m,n) dependence as a primary contribution of this work.

Weakness 3: The theory cannot show any gain from a good rotation. Since the bound is the same for all rotations, it does not show which rotation is better or why SOAP outperforms Adam.

Reply: See the common response.

Weakness 4: ''the first nuclear-norm convergence rate for Adam with matrix-valued parameter'', is overstated as well.

Reply: From ∥A∥∗≤∥A∥1\lVert A\rVert_*\leq \lVert A\rVert_1 and the convergence rate of Adam in [1], we directly obtain the nuclear-norm convergence rate

1K∑k=1KE[∥∇f(Xk)∥∗]≤1K∑k=1KE[∥∇f(Xk)∥1]≤[1]O(mnmax⁡(σ2L△K4,L△K)).\frac{1}{K}\sum_{k=1}^K E[\lVert\nabla f(X_k)\rVert_*]\leq\frac{1}{K}\sum_{k=1}^K E[\lVert\nabla f(X_k)\rVert_1]\overset{[1]}\leq O\left(\sqrt{mn}\max\left(\sqrt[4]{\frac{\sigma^2 L\triangle}{K}},\sqrt{\frac{L\triangle}{K}}\right)\right).

Furthermore, [2] proved that the above rate is optimal when measured by the ℓ1\ell_1 norm, particularly with respect to the dimension. Therefore, although a nuclear-norm rate for Adam can be obtained directly from [1], it is slower by a factor of mnm+n\sqrt{\frac{mn}{m+n}} than both our rate and the existing AdamW-style Shampoo rate. Moreover, the ℓ1\ell_1 route cannot reach the m+n\sqrt{m+n} dependence because the ℓ1\ell_1 rate is tight in the dimension regardless of the choice of ε\varepsilon [2]. Our analysis shows that Adam can attain the m+n\sqrt{m+n} nuclear-norm rate of AdamW-style Shampoo through the proposed row-column trace control argument, at the cost of requiring a larger value of ε\varepsilon. In the contribution section, we stated that we provide the first nuclear-norm convergence rate for Adam with the emphasis that it is of the same order as that of matrix optimizers such as AdamW-style Shampoo.

AuthorsOpenReview ↗

Part 2: Response to the questions

Question 1: Is there a choice of PkP_k and QkQ_k for which the framework gives a strictly better bound than Pk=IP_k=I, Qk=IQ_k=I? If SOAP works because of the eigenbasis, which assumption, for example a smoothness or noise constant measured in the rotated basis, would let the analysis show it?

Reply: See the common response. As pointed out by the reviewer, making stronger assumptions may allow one to prove the superiority of SOAP’s rotation matrix, such as the problem-dependent assumptions or an instance-dependent convergence analysis. We leave this question for future work.

Question 2: When ε\varepsilon is chosen much smaller than δ2\delta^2, how is the condition Dk,i,j≥δD_{k,i,j}\geq\delta compatible with the gradient going to zero, and under which conditions does the claim hold?

Reply: (1) Within the theorem: with ε=τσ^2/(m+n)\varepsilon=\tau\hat\sigma^2/(m+n) and δ=ε\delta=\sqrt\varepsilon, the condition Vk,ij+ε≥ε=δ\sqrt{V_{k,ij}+\varepsilon}\ge\sqrt\varepsilon=\delta holds deterministically at every iteration, so the guarantee needs no assumption on the trajectory.

(2) The practical remark that ε\varepsilon may be chosen much smaller than δ2\delta^2 is a statement beyond the theorem, and its correct form is conditional: it holds whenever Vk,i,j≥σ^2/(m+n)V_{k,i,j}\geq \hat\sigma^2/(m+n) for all kk. Because VkV_k aggregates the stochastic gradient GkG_k, this condition does not require the true gradient to stay away from zero, it requires only that the noise remains non-negligible. However, we admit that for isotropic noise the typical entry of VkV_k is of order σ2/(mn)\sigma^2/(mn), smaller than σ^2/(m+n)\hat\sigma^2/(m+n), and in the deterministic case the condition can fail, which is exactly why the theorem uses ε=τσ^2/(m+n)\varepsilon=\tau\hat\sigma^2/(m+n).

[1]. On the O(d/K1/4)O(\sqrt{d}/K^{1/4}) Convergence Rate of AdamW Measured by ℓ1\ell_1 Norm. NeurIPS 2025.

[2]. On the Optimality of Adam under Heavy-Tailed Noise. https://openreview.net/forum?id=OjDxyU2Td2.

Thank you authors for the detailed response. Most of my concerns have been addressed. I still believe that the work would benefit from a more detailed examination of the convergence rates of the individual methods. Therefore, I am raising my rating only to weak accept.

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

the paper proposes new, tighter bounds on the convergence of rotation based optinizers, relative to Li et al 2025. Two main technical points are (1) relyin gon the orthongolality propery ||QXP||_F = ||X||_F, and (2) a row/column-wise bound on the denominator factor D. An interesting corollary of the paper is a bound on Adam's convergence.

Critical strengths

It's great that we have a bound which cover several optimizers.

I enjoyed reading the paper through. If you used AI to write this, you did a nice job: there's clear pedagogy in the writing.

Critical weaknesses

The authors bound the nuclear norm of the matrix, cf Frob norm in previous work. What are the implications?

We have a bound on the convergence of Adam that matches that of the rotated methods... so this new bound does not explain why rotation helps. In this sense, the paper does not push the field forward as much as we might hope.

Questions for authors

the new bound is on the convergence of the nuclear norm. I think this warrants more discussion! What does it mean for the convergence of the network as a whole? It seems to me that if you have two matrices appearing adjacently in the model, AB, then each matrix A, B could converge without the product converging?

2 comments

We sincerely thank the reviewer for their valuable suggestions. Below are our responses to the major concerns.

Weakness 1: The authors bound the nuclear norm of the matrix, cf Frob norm in previous work. What are the implications?

Reply: Under Assumptions 1–3, SGD achieves the rate O(σ2L△K4)O\left(\sqrt[4]{\frac{\sigma^2 L\triangle}{K}}\right), measured in the Frobenius norm, whereas Adam employs the ℓ1\ell_1 norm and achieves the rate O(mnσ2L△K4)O\left(\sqrt{mn}\sqrt[4]{\frac{\sigma^2 L\triangle}{K}}\right). Both rates are optimal [1,2], albeit with respect to different norms. Our paper uses the nuclear norm and obtains the rate O(m+nσ2L△K4)O\left(\sqrt{m+n}\sqrt[4]{\frac{\sigma^2 L\triangle}{K}}\right). The nuclear norm can be viewed as the ℓ1\ell_1 norm in the singular-value space. It captures the spectral perspective of SOAP/Shampoo/Muon and has therefore also been employed in the closely related Shampoo and Muon analyses. These norms are equivalent in the sense that ∥x∥2≤∥x∥1≤d∥x∥2\lVert x\rVert_2\leq \lVert x\rVert_1\leq \sqrt{d}\lVert x\rVert_2 and ∥X∥F≤∥X∥∗≤min⁡(m,n)∥X∥F\lVert X\rVert_F\leq \lVert X\rVert_*\leq \sqrt{\min(m,n)}\lVert X\rVert_F. Therefore, convergence in the nuclear norm also implies convergence in the Frobenius norm.

Weakness 2: The bound of Adam matches that of the rotated methods. The theory does not explain why rotation helps.

Reply: See the common response.

Question 1: What does it mean for the convergence of the network as a whole? It seems to me that if you have two matrices appearing adjacently in the model, ABAB, then each matrix AA, BB could converge without the product converging?

Reply: (1). This paper considers the problem min⁡X∈Rm×nf(X)\min_{X\in R^{m\times n}} f(X) with a single matrix parameter XX for simplicity. Practical networks typically involve multiple matrices and our analysis can be readily extended to this case. See the settings in Section 2 of [3] for such an extension.

(2). We always have AkBk→ABA_kB_k\rightarrow AB whenever Ak→AA_k\rightarrow A and Bk→BB_k\rightarrow B, by the continuity of matrix multiplication.

(3). Denote G=∇f(AB)G=\nabla f(AB), then ∂f(AB)∂A=GBT\frac{\partial f(AB)}{\partial A}=GB^T and ∂f(AB)∂B=ATG\frac{\partial f(AB)}{\partial B}=A^TG. If GBT=0GB^T=0 and BB has full column rank, then G=0G=0. Similarly, if ATG=0A^TG=0 and AA has full row rank, then G=0G=0. However, when AA and BB are low rank, GBT=0GB^T=0 and ATG=0A^TG=0 do not necessarily imply G=0G=0. For example, let G=[0,0;0,1]G=[0,0;0,1] and A=B=[1,0;0,0]A=B=[1,0;0,0], then GBT=0GB^T=0 and ATG=0A^TG=0, but G≠0G\neq 0. This rank-deficiency pathology is a property of factorized parametrizations and applies identically to every per-parameter analysis (SGD and Adam included), not to our framework in particular.

[1]. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165–214, 2023.

[2]. On the Optimality of Adam under Heavy-Tailed Noise. https://openreview.net/forum?id=OjDxyU2Td2.

[3]. A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muon. arXiv: 2604.17423, 2026.

this paper is a weak accept for me. There's nothing wrong as far as I can tell, and the contribution is interesting.

I think the fact that all reviewers had similar queries, and caused you to write a common response is a strong signal that you should consider some of the paper's positioning.

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

This work developed a theoretical framework for the analysis of optimization algorithms where the update can be captured by a rotation of a gradient (or momentum) matrix, an element wise transformation, and then a rotation back in to the parameter space. The authors give a generalized algorithm that includes special cases of SOAP, Conda, SPlus, and Adam, and define which choices of rations and element wise updates would lead to these algorithms (or similar variants of them). Following this setup, the authors bound the mean update norm under some assumptions. The authors identify that a bound derived from this bound in previous work is loose due to an element wise condition, and tighten it to depend on the sum of the matrix dimensions by applying a condition to the rows and columns instead of each entry. The authors use properties of the rows and columns of the elementwise update portion of each optimizers update to formulate their new bound. From there, matrices controlling this condition on the rows and columns are developed for each of the aforementioned optimization methods. The authors draw distinction between between algorithms where the element wise normalization step is momentum based versus an instantaneous update based on each batch’s statistics.

Critical strengths

The paper is well written and fairly easy to understand which is appreciable for a theoretical contribution. The work is indeed relevant, as more and more of the field is concerned with rotation based or dense preconditioning methods. The generality of the framework is nice, although this comes with it’s own drawbacks as noted in the next section.

Critical weaknesses

My concern about this approach is that I worry the theory is not powerful enough to capture the distinction between algorithms, and predict which algorithm should enjoy superior downstream performance. For example, in section 3.3.2 the authors show that AdamW and Shampoo should attain the same nuclear norm convergence rate. This is in contrast to much empirical evidence that Shampoo can show superior performance. It is possible that this framework is in fact too general, notably the design of the control matrices only depends on the elementwise normalizer for each optimizer. Allowing the rotation matrices to be arbitrary allows flexibility, but at the cost of being uninformative to what an effective rotation matrix is. This is a weakness as the more novel contribution of the studied optimization algorithm is in determining what is the most effective basis to run optimization in. The authors additionally point out that in order to fit some of their choices of optimizers into this framework, nontrivial modifications have been made that do not fully reflect the practical algorithms used.

I will also note that while this is a paper with strictly theoretical contributions, it would be Ince to see the authors empirically verify their bounds in a simple setting. For example, Assumptions 1-3 could be satisfied by a deterministic quadratic optimization and the constants should be computable. It would be nice to see that at least on these simple cases the bounds indeed hold, or methods of adding empirical insights to the authors theory.

Given these weaknesses, I will vote for a weak rejection. I do feel the authors could add commentary on how this framework can be used for gaining further insights rather than matching previously known bounds through a new framework. It could be the case that their framework could lead to many interesting results, I just feel the current set of results is a bit small for acceptance. I am open to raising my score, I just feel like the authors need to engage in these weaknesses as their entire contribution is this framework.

Questions for authors
  • Do the authors see how this theory could incorporate structure of the rotation matrices? Many concurrent and previous works show that optimizer performance often heavily depends on the choice of the rotation so this seems like it is missing in the theory
  • Do the authors feel truncated SPlus is actually a fair representation of SPlus? If the entries are near zero, the described new version would blow them up where as SPlus would be immune to this.
  • The Adam result for convergence in the nuclear norm is interesting, but there have been numerous attempts to show convergence rates for Adam under various assumptions and geometries, how do the authors feel this compares to the vast literature of previous work on that topic?
  • Do the authors think that Adam and Shampoo having the same convergence rate under their framework reflects their framework not being very powerful or that these algorithms should actually have some underlying similarity leading to this.
2 comments

We sincerely thank the reviewer for their valuable suggestions. Below are our responses to the major concerns.

Weakness 1 and Question 4: The theory does not capture the distinction between algorithms. Adam and Shampoo have the same convergence rate under the framework in this paper.

Reply: The worst-case rate is indeed too coarse to explain Shampoo's practical advantage. For example, under Assumptions 1–3, the convergence rate of SGD matches the lower bound and is therefore optimal [1]. However, this does not mean that SGD is the best choice for all stochastic nonconvex optimization, nor does it mean that proving convergence rates for other algorithms is meaningless, for example, for the empirically effective Adam, Shampoo, and SOAP, whose worst-case convergence rates cannot improve upon that of SGD under the same assumptions. These algorithms must have some underlying distinction that is not captured by the worst-case convergence rate.

Weakness 2 and Question 1: The theory does not characterize what constitutes an effective rotation matrix and does not predict which algorithm should enjoy superior downstream performance.

Reply: See the common response.

Weakness 3: Suggest to empirically verify the bounds in a simple deterministic quadratic setting.

Reply: We consider the simple problem min⁡W∈Rm×n1N∑i=1N∥\mboxsoftmax(Wxi)−yi∥2\min_{W\in R^{m\times n}} \frac{1}{N}\sum_{i=1}^N\lVert\mbox{softmax}(Wx_i)-y_i\rVert^2. We set m=n=N=100m=n=N=100, generate each element of xi∈Rnx_i\in R^n from the normal distribution N(0,1)\mathcal N(0,1), and set yiy_i to the one-hot encoding of a randomly assigned class. We initialize W0W_0 from N(0,1)\mathcal N(0,1) so that f(W0)≈1.76f(W_0)\approx 1.76 and obtain the stochastic gradient by perturbing the true gradient with random noise generated from N(0,σ2mn)\mathcal N(0,\frac{\sigma^2}{mn}), so that E[∥∇f(W)−G∥F2]≤σ2E[\lVert\nabla f(W)-G\rVert_F^2]\leq \sigma^2. The Lipschitz constant LL is unknown and we approximate it as L=max⁡A,B∥∇f(A+B)−∇f(A)∥F∥B∥F≈0.03L=\max_{A,B} \frac{\lVert\nabla f(A+B)-\nabla f(A)\rVert_F}{\lVert B\rVert_F}\approx 0.03 using 100 random pairs (A∼N(0,1),B∼N(0,10−4))(A\sim \mathcal N(0,1),B\sim \mathcal N(0,10^{-4})). We set K=107K=10^7, σ=1\sigma=1, θ=1−L(f(W0)−f∗)Kσ2\theta=1-\sqrt{\frac{L(f(W_0)-f^{\ast})}{K\sigma^2}} with f∗f^{\ast} lower bounded by 0, β=0.9\beta=0.9, δ2=ε=σ2m+n\delta^2=\varepsilon=\frac{\sigma^2}{m+n}, η=δ2(f(W0)−f∗)4LKσ2\eta=\sqrt{\frac{\delta^2(f(W_0)-f^{\ast})}{4LK\sigma^2}} for SOAP, Adam, and Adam-style Shampoo, following the parameter choices in Theorem 2. The table below reports the averaged gradient nuclear norm 1k∑t=1k∥∇f(Wt)∥∗\frac{1}{k}\sum_{t=1}^k\lVert\nabla f(W_t)\rVert_*. The theoretical upper bound can also be computed as m+nσ2L(f(W0)−f∗)K4=0.12069\sqrt{m+n}\sqrt[4]{\frac{\sigma^2L(f(W_0)-f^{\ast})}{K}}=0.12069, which confirms that the theoretical bound holds in this simple setting.

Epoch10310^310410^410510^510610^610710^7
SOAP1.021720.954670.538340.133180.02723
Adam1.021710.954520.540730.134360.02663
Shampoo1.021790.992890.553510.146230.03777

Question 2: Splus and truncated SPlus: If the entries are near zero, the truncated SPlus would blow them up where as SPlus would be immune to this.

Reply: When an entry xx is near zero with ∣x∣<δ|x|<\delta, we can't distinguish whether xx contains the true signal or noise. The sign update in the original SPlus, \mboxsign(x)=±1\mbox{sign}(x)=\pm 1, would blow up the noise. In contrast, truncated SPlus uses a soft sign update, xmax⁡(∣x∣,δ)=xδ\frac{x}{\max(|x|,\delta)}=\frac{x}{\delta}, and is therefore strictly more conservative on noise-dominated entries. Thus, the ''blow-up'' of near-zero entries applies to the original SPlus, whereas truncated SPlus is immune to this issue. Indeed, this trick, also known as the clipping trick, has been used in various settings, such as Clipped SGD and Sophia.

Question 3: Compare to the literature of Adam.

Under comparable assumptions (LL-smoothness, unbiased oracle, bounded noise variance), the closest results are as follows:

AdamW [2]: ℓ1\ell_1-norm rate with dimension factor mn\sqrt{mn};

Adam [3]: ℓ2\ell_2-norm rate under relaxed smoothness assumptions;

AdamW-style Shampoo [4]: nuclear norm rate with dimension factor m+n\sqrt{m+n};

Ours: nuclear norm rate with dimension factor m+n\sqrt{m+n}.

For other related work on Adam, see the reference in [2]. The significance of our finding is that Adam with the coordinate-wise update attains a nuclear-norm convergence rate of the same order as that of AdamW-style Shampoo [6], even though it does not employ any full-matrix preconditioning.

[1]. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165–214, 2023.

[2]. On the O(d/K1/4)O(\sqrt{d}/K^{1/4}) Convergence Rate of AdamW Measured by ℓ1\ell_1 Norm. NeurIPS, 2025.

[3]. Convergence of Adam under relaxed assumptions. NeurIPS, 2023.

[4]. Convergence Rate Analysis of the AdamW-Style Shampoo: Unifying One-Sided and Two-Sided Preconditioning. ICML, 2026.

I thank the authors for their detailed response to reviewers. It seems myself along with all the other reviewers were indeed concerned more or less about the same thing: what new results can actually be proven with this framework. I understand the authors arguments regarding these rates being worst case and how choice of rotation cannot tighten those, however I do feel appealing to this argument does not really strengthen the paper. My thoughts is that more insights would be offered by a further analysis of any individual algorithm rather than claiming a strong contribution by finding the same or similar worst case rates for a class of quite similar algorithms. While other reviewers appear to have been more convinced on the contribution, I am sure I agree that the work raises to the level of a full publication and I am inclined to keep my score. I will further consider changing it throughout the AC-Reviewer discussion period, but I do feel the work has some fundamental weaknesses in its current form as I have discussed.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Response to the Common Question

We sincerely thank the reviewers for their constructive feedback. We have addressed each point below and revised the manuscript accordingly. All changes in our resubmitted manuscript are marked in blue.

We first reply to the concern shared by all reviewers.

Common Question: The theory does not characterize what constitutes an effective rotation matrix, does not demonstrate any gain from rotation, and does not predict which rotation is better. (pJRZ W2/Q1, TuCc W1, bPvr W3/Q1)

Reply: (1). What the framework certifies. Before this work, no convergence rate was known for SOAP, Conda, or (truncated) SPlus. Theorems 2-3 establish that all of them attain the O(m+nσ2L△K4)O\left(\sqrt{m+n}\sqrt[4]{\frac{\sigma^2 L\triangle}{K}}\right) worst-case convergence rate measured by nuclear norm, the same order as the state-of-the-art rate for AdamW-style Shampoo. We emphasize that this is not a recovery of previously known bounds: for these methods no bounds existed. This is the paper's primary contribution: a positive guarantee that these rotation-based methods converge at a rate no worse, in order, than the best known matrix-preconditioned method.

(2). Significance of our work. Our framework provides a certificate for any future rotation-based optimizer that fits the framework of Algorithms 4 and 6: such an optimizer inherits the convergence guarantee for arbitrary orthogonal rotation matrices. In this sense, the framework frees algorithm designers from having to re-prove convergence: they need only focus on choosing rotations for practical performance and automatically obtain a convergence guarantee.

(3). The mechanism of SOAP's rotation. In the original SOAP paper [1], the authors designed SOAP as running Adam in a rotated eigen-space: when Gk→GG_k\rightarrow G with G=UΣVTG=U\Sigma V^T being its SVD, we have Mk→GM_k\rightarrow G, Lk→GGTL_k\rightarrow GG^T, Pk→UP_k\rightarrow U, Rk→GTGR_k\rightarrow G^TG, Qk→VQ_k\rightarrow V, and Vk→Σ2V_k\rightarrow\Sigma^2. Therefore, the update PkPkTMkQkVk+εQkT→UΣΣ2+εVTP_k\frac{P_k^TM_kQ_k}{\sqrt{V_k+\varepsilon}}Q_k^T\rightarrow U\frac{\Sigma}{\sqrt{\Sigma^2+\varepsilon}}V^T. In other word, the normalizer in Adam acts on the spectrum of the gradient rather than on its coordinates.

However, the above explanation remains merely at the level of intuitive mechanistic interpretation. Providing a rigorous theoretical proof is challenging, as it relies on too many approximations. Moreover, it remains unclear why running Adam in the eigen-space works (similarly, the mechanism underlying Muon also remains an open problem, one that is of great current interest to the community.). Thus, the most feasible theoretical contribution at present is a rigorous worst-case convergence rate together with an intuitive mechanistic interpretation. Our paper provides the former, whereas the original papers on SOAP/SPlus/Conda and the subsequent papers [2,3] provide the latter, which may intuitively explain what constitutes an effective rotation matrix and why rotation works better than Adam.

(4). The Limits of worst-case optimality. In optimization theory, convergence rates are almost always established in the worst case, i.e., they hold uniformly for all problems in a given class. Under Assumptions 1-3, SGD's rate O(σ2L△K4)O\left(\sqrt[4]{\frac{\sigma^2 L\triangle}{K}}\right) is optimal when measured by the Frobenius norm [4] and Adam’s rate of O(mnσ2L△K4)O\left(\sqrt{mn}\sqrt[4]{\frac{\sigma^2 L\triangle}{K}}\right) is optimal when measured by the ℓ1\ell_1 norm [5]. Analogously, since ∥X∥1=Θ(mn)∥X∥F\lVert X\rVert_1=\Theta(\sqrt{mn})\lVert X\rVert_F and ∥X∥∗=Θ(min⁡(m,n))∥X∥F\lVert X\rVert_*=\Theta(\sqrt{\min(m,n)})\lVert X\rVert_F in the ideal case, we conjecture that our rate O(min⁡(m,n)σ2L△K4)O\left(\sqrt{\min(m,n)}\sqrt[4]{\frac{\sigma^2 L\triangle}{K}}\right) (Theorem 4 in Appendix D) is also optimal in the nuclear norm. If this conjecture holds, then this worst-case rate is tight under arbitrary orthogonal rotations and cannot be improved further. Hence, the choice of rotation matrices cannot improve the worst-case convergence rate. From the perspective of worst-case convergence rates alone, we cannot demonstrate the gain from rotation or prove that rotation is better than Pk=IP_k=I, Qk=IQ_k=I. This is an inherent limitation of worst-case convergence rates. Establishing such a benefit requires either stronger problem-dependent assumptions or an instance-dependent convergence analysis.

[1]. SOAP: Improving and stabilizing Shampoo using Adam. ICLR, 2025.

[2]. Understanding and improving Shampoo and SOAP via Kullback-Leibler minimization. ICLR, 2026

[3]. Understanding SOAP from the perspective of gradient whitening. arXiv:2509.22938, 2025.

[4]. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165–214, 2023.

[5] On the Optimality of Adam under Heavy-Tailed Noise. https://openreview.net/forum?id=OjDxyU2Td2.

thanks for the clarifications!

We sincerely thank the reviewers for their thorough discussion. We fully agree that it is important to prove faster convergence rates for widely used optimizers individually and to characterize the fundamental reason for their success in DL/LLM training, including Adam and Muon. We regard this as one of the most important open problems in the machine learning optimization community. However, even for the most well-known optimizer, Adam (whose algorithmic structure is simpler than that of SOAP), we are not aware of such a rigorous theoretical analysis. Current work remains at the stage of proposing intuitions/claims followed by empirical validation. Some preliminary progress has been made for algorithms with relatively simpler structures. For example, under the per-coordinate noise assumption E[∣∇if(x)−gi∣2]≤σi2E[|\nabla_i f(x)-g_i|^2]\leq\sigma_i^2 and coordinate-wise smoothness assumption ∣f(y)−f(x)−⟨∇f(x),y−x⟩∣≤∑iLi2∣yi−xi∣2|f(y)-f(x)-\left\langle\nabla f(x),y-x \right\rangle|\leq \sum_i \frac{L_i}{2}|y_i-x_i|^2, [1,2] proved that AdaGrad achieves a faster convergence rate than SGD in certain constant factors, and under the spectral smoothness assumption ∥∇f(Y)−∇f(X)∥∗≤L∥Y−X∥op\lVert\nabla f(Y)-\nabla f(X)\rVert_*\leq L\lVert Y-X\rVert_{op}, [3] proved that Muon has a better dimension dependence than SGD. However, these assumptions are mainly tailored to better match the structure of these algorithms. In our view, they still do not yet capture the fundamental reasons why these optimizers are better suited to training deep networks. We would also welcome the SAC and the AC to join the discussion during the AC–reviewer discussion period.

[1]. Provable complexity improvement of adaGrad over SGD: Upper and lower bounds in stochastic non-convex optimization. COLT, 2025.

[2]. AdaGrad under anisotropic smoothness. ICLR, 2025.

[3].On the Convergence Analysis of Muon. TMLR, 2026.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.