Convergence Rate Analysis of SOAP with Arbitrary Orthogonal Projection Matrices
Huan Li, Zhouchen Lin · 2026
Read Convergence Rate Analysis of SOAP with Arbitrary Orthogonal Projection Matrices by Huan Li, Zhouchen Lin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21616.txt.
Introduction
Huan Li and Zhouchen Lin analyze SOAP, a widely used matrix-style optimizer that trains deep neural networks. They prove its convergence rate for the first time. Their result covers a broader variant that accepts arbitrary orthogonal projection matrices, provided each matrix stays conditionally independent of the current stochastic gradient. Since such matrices may be built from all information available before the current step, the analysis applies to practical implementations that update projections from past data.
Catalog record
| CREATOR | Huan Li, Zhouchen Lin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41599 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.21616
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence Rate Analysis of SOAP with Arbitrary Orthogonal Projection Matrices Huan Li, Zhouchen Lin Abstract In this short note, we establish, for the first time, the convergence rate of SOAP, an efficient and popular matrix-based optimizer for training deep neural networks. Our analysis extends to a more general variant of SOAP that admits arbitrary orthogonal projection matrices and requires only that these matrices be conditionally independent of the current stochastic gradient at each iteration. For example, they may be constructed from information available up to the preceding step. 1 Introduction Pre-training large language models incurs substantial computational costs. Over the past decade, the Adam family of algorithms, including AdaGrad ( 4 ; 18 ) , RMSProp ( 22 ) , Adam ( 11 ) , and AdamW ( 17 ) , has served as the de facto standard for optimizing deep neural networks. These methods treat the network’s parameters as a single high-dimensional vector. More recently, matrix-based optimizers, which exploit the inherent matrix structure of deep neural network parameters, have garnered increasing attention and demonstrated the potential to outperform their vector-based counterparts. Prominent examples include Shampoo ( 7 ) , Muon ( 10 ) , SOAP ( 23 ) , Splus ( 5 ) , and ARO ( 6 ) . The latter three approaches can be collectively classified as projection-based optimizers. Although the convergence behavior of vector-based optimizers has been thoroughly studied in the literature ( 3 ; 21 ; 14 ; 24 ; 9 ; 12 ; 13 ) , the theoretical understanding of matrix-based optimizers remains comparatively underdeveloped. Among matrix-based methods, Muon constitutes a notable exception: owing to its relatively simple structure, its convergence properties have been extensively investigated and are now largely understood ( 16 ; 20 ; 2 ; 19 ) . For more intricate optimizers, recent progress includes the work of 15 , who established rigorous convergence guarantees for the practical AdamW-style implementation of Shampoo. Nevertheless, with the exception of these two cases, the convergence analysis of other matrix-based optimizers remains an open problem to the best of our knowledge, especially the representative SOAP optimizer. The work by 8 perhaps constitutes the most closely related study, analyzing a variant of the GaLore algorithm ( 25 ) . However, their approach replaces the structured SVD-based orthogonal projection employed by GaLore and SOAP with a random projection, and it utilizes momentum stochastic gradient descent (MSGD) within the projected space, whereas GaLore and SOAP leverage the adaptive mechanisms of Adam. Consequently, the analytical techniques developed in ( 8 ) are far from sufficient to establish the convergence of the full SOAP algorithm. In this short note, we address the theoretical behavior of SOAP and establish the following convergence rate \displaystyle\begin{aligned} \frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\left\|\nabla f(\mathbf{X}_{k})\right\|_{*}\right]\leq{\cal O}\left(\sqrt{mn}\sqrt[4]{\frac{\sigma_{F}^{2}L\left(f(\mathbf{X}_{1})-f^{*}\right)}{K}}\right),\end{aligned} (1) where the relevant notations can be found in Section 1.1 . Notably, our analysis extends to a considerably more general variant of SOAP, as presented in Algorithm 2 , which accommodates arbitrary orthogonal projection matrices. In other words, the projection operators may be generated through any procedure. The only requirement is that, at each iteration, the projection matrices be conditionally independent of the current stochastic gradient. Formally, in the proof for Algorithm 2 we use the identity \mathbb{E}_{k}\left[\mathbf{P}_{k-1}^{T}\mathbf{G}_{k}\mathbf{Q}_{k-1}|\mathcal{F}_{k-1}\right]=\mathbf{P}_{k-1}^{T}\mathbb{E}_{k}\left[\mathbf{G}_{k}|\mathcal{F}_{k-1}\right]\mathbf{Q}_{k-1} . This flexibility is substantial: for instance, the projection matrices may be constructed adaptively from the entire optimization history up to the preceding step—by employing, for example, the eigenvectors of the one-step-delayed preconditioning matrices used in the original SOAP (Algorithm 1 ), or the left and right singular vectors of the momentum or gradient from the previous iteration. Consequently, the theoretical guarantees we establish not only apply directly to the original SOAP algorithm but also shed light on a broader class of projection-based matrix optimizers, including Splus ( 5 ) and ARO ( 6 ) , thereby offering a unified analytical framework for understanding the convergence behavior of such methods. Algorithm 1 SOAP Hyper parameters: \eta,\theta,\beta,\varepsilon Initialize \mathbf{X}_{1} , \mathbf{M}_{0}=\mathbf{0} , \mathbf{V}_{0}=\mathbf{0} , \mathbf{P}_{0} , \mathbf{Q}_{0} , \mathbf{L}_{0} , \mathbf{R}_{0} . for k=1,2,\cdots,K do \mathbf{G}_{k}=\mbox{GradOracle}(\mathbf{X}_{k}) \mathbf{M}_{k}=\theta\mathbf{M}_{k-1}+(1-\theta)\mathbf{G}_{k} \mathbf{G}_{k}^{\prime}=\mathbf{P}_{k-1}^{T}\mathbf{G}_{k}\mathbf{Q}_{k-1} , \mathbf{M}_{k}^{\prime}=\mathbf{P}_{k-1}^{T}\mathbf{M}_{k}\mathbf{Q}_{k-1} \mathbf{V}_{k}=\beta\mathbf{V}_{k-1}+(1-\beta)(\mathbf{G}_{k}^{\prime})^{2} \mathbf{X}_{k+1}=\mathbf{X}_{k}-\eta\mathbf{P}_{k-1}\frac{\mathbf{M}_{k}^{\prime}}{\sqrt{\mathbf{V}_{k}+\varepsilon}}\mathbf{Q}_{k-1}^{T} \mathbf{L}_{k}=\beta\mathbf{L}_{k-1}+(1-\beta)\mathbf{G}_{k}\mathbf{G}_{k}^{T} \mathbf{R}_{k}=\beta\mathbf{R}_{k-1}+(1-\beta)\mathbf{G}_{k}^{T}\mathbf{G}_{k} if k\mod T=0 then \mathbf{P}_{k}=\mbox{Eigenvector}(\mathbf{L}_{k}) \mathbf{Q}_{k}=\mbox{Eigenvector}(\mathbf{R}_{k}) else \mathbf{P}_{k}=\mathbf{P}_{k-1} , \mathbf{Q}_{k}=\mathbf{Q}_{k-1} end if end for Algorithm 2 Generalized SOAP Hyper parameters: \eta,\theta,\beta,\varepsilon Initialize \mathbf{X}_{1} , \mathbf{M}_{0}=\mathbf{0} , \mathbf{V}_{0}=\mathbf{0} , \mathbf{P}_{0} , \mathbf{Q}_{0} . for k=1,2,\cdots,K do \mathbf{G}_{k}=\mbox{GradOracle}(\mathbf{X}_{k}) \mathbf{M}_{k}=\theta\mathbf{M}_{k-1}+(1-\theta)\mathbf{G}_{k} \mathbf{G}_{k}^{\prime}=\mathbf{P}_{k-1}^{T}\mathbf{G}_{k}\mathbf{Q}_{k-1} , \mathbf{M}_{k}^{\prime}=\mathbf{P}_{k-1}^{T}\mathbf{M}_{k}\mathbf{Q}_{k-1} \mathbf{V}_{k}=\beta\mathbf{V}_{k-1}+(1-\beta)(\mathbf{G}_{k}^{\prime})^{2} \mathbf{X}_{k+1}=\mathbf{X}_{k}-\eta\mathbf{P}_{k-1}\frac{\mathbf{M}_{k}^{\prime}}{\sqrt{\mathbf{V}_{k}+\varepsilon}}\mathbf{Q}_{k-1}^{T} \mbox{Generate orthonogal matrices }\mathbf{P}_{k}\mbox{ and }\mathbf{Q}_{k} end for 1.1 Problem Settings, Notations, and Assumptions We study the following nonconvex problem with matrix parameter in this note \min_{\mathbf{X}\in\mathbb{R}^{m\times n}}f(\mathbf{X}), (2) where f(\mathbf{X})=\mathbb{E}_{\zeta\in\mathcal{P}}[f(\mathbf{X};\zeta)] and \zeta is the sample drawn from the data distribution \mathcal{P} . We denote vectors by lowercase bold letters and matrices by uppercase bold letters. For vectors, denote \|\cdot\| as the \ell_{2} Euclidean norm. For matrices, denote \|\cdot\|_{F} , \|\cdot\|_{op} , \|\cdot\|_{*} , and \|\cdot\|_{1} as the Frobenius norm, spectral norm (largest singular value), nuclear norm (sum of singular values), and entrywise \ell_{1} norm (sum of absolute entries), respectively. Denote \mathbf{X}_{k,i,j} , \mathbf{X}_{k,i,:} , and \mathbf{X}_{k,:,j} to be the (i,j) -th element, i -th row, and j -th column of matrix \mathbf{X} at iteration k , respectively. For matrices \mathbf{X} and \mathbf{Y} , denote \frac{\mathbf{X}}{\mathbf{Y}} , \mathbf{X}^{2} , and \sqrt{\mathbf{X}} as the element-wise division, square, and square root (different from the matrix power, with a slight abuse of terminology), respectively. Denote \mathcal{F}_{k}=\sigma(\zeta_{1},\zeta_{2},\cdots,\zeta_{k}) to be the sigma field of the stochastic samples up to k , denote \mathbb{E}_{\mathcal{F}_{k}}[\cdot] as the expectation with respect to \mathcal{F}_{k} and \mathbb{E}_{k}[\cdot|\mathcal{F}_{k-1}] the conditional expectation with respect to \zeta_{k} given \mathcal{F}_{k-1} . For the sake of brevity, \mathbb{E}_{\mathcal{F}_{K}}[\cdot] will be denoted as \mathbb{E}[\cdot] . We make the following assumptions throughout this note: 1. Smoothness: \|\nabla f(\mathbf{Y})-\nabla f(\mathbf{X})\|_{F}\leq L\|\mathbf{Y}-\mathbf{X}\|_{F},\forall\mathbf{X},\mathbf{Y} , 2. Unbiased estimator: \mathbb{E}_{k}\left[\mathbf{G}_{k}\big|\mathcal{F}_{k-1}\right]=\nabla f(\mathbf{X}_{k}) , 3. Bounded noise variance: \mathbb{E}_{k}\left[\|\mathbf{G}_{k}-\nabla f(\mathbf{X}_{k})\|_{F}^{2}\big|\mathcal{F}_{k-1}\right]\leq\sigma_{F}^{2} , \mathbb{E}_{k}\left[\|\mathbf{G}_{k}-\nabla f(\mathbf{X}_{k})\|_{op}^{2}\big|\mathcal{F}_{k-1}\right]\leq\sigma_{op}^{2} . 2 Convergence Rate of SOAP We establish the following theorem for the generalized SOAP algorithm presented in Algorithm 2 , which includes the original SOAP as a special case. The rate in ( 3 ) recovers the convergence rate of Adam in the projection space in terms of the entrywise \ell_{1} norm, and it matches the lower bound for stochastic nonconvex optimization ( 1 ) in the idealized regime where \|\mathbf{X}\|_{1}=\Theta(\sqrt{mn})\|\mathbf{X}\|_{F} . However, because the \ell_{1} norm is not unitarily invariant, the orthogonal projection matrices appearing on the left-hand side of ( 3 ) cannot be eliminated. In contrast, the rate in ( 4 ) employs the nuclear norm, which directly measures the gradient magnitude in the primal space. Despite this advantage, the rate in ( 4 ) is \sqrt{\min\{m,n\}} times slower than the rate achieved by AdamW-style Shampoo ( 15 ) and at least \sqrt{\max\{m,n\}} times slower than the theoretical lower bound. In particular, if we choose \mathbf{P}_{k-1} and \mathbf{Q}_{k-1} to be the left and right singular vector matrices of \nabla f(\mathbf{X}_{k}) , we obtain \left\|\mathbf{P}_{k-1}^{T}\nabla f(\mathbf{X}_{k})\mathbf{Q}_{k-1}\right\|_{1}=\left\|\nabla f(\mathbf{X}_{k})\right\|_{*} and rate ( 3 ) reduces to rate ( 4 ). Theorem 1 Suppose that Assumptions 1-3 hold. Let \hat{\sigma}_{F}^{2}=\max\left\{\sigma_{F}^{2},\frac{L\left(f(\mathbf{X}_{1})-f^{*}\right)}{K\gamma^{2}}\right\} with any \gamma\in(0,1] , 1-\theta=\sqrt{\frac{L\left(f(\mathbf{X}_{1})-f^{*}\right)}{K\hat{\sigma}_{F}^{2}}} , 0\leq\beta<1 , \varepsilon=\sigma_{op}^{2} , and \eta=\sqrt{\frac{\varepsilon\left(f(\mathbf{X}_{1})-f^{*}\right)}{4LK\hat{\sigma}_{F}^{2}}} . Then for Algorithm 2 , we have \displaystyle\begin{aligned} \frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\left\|\mathbf{P}_{k-1}^{T}\nabla f(\mathbf{X}_{k})\mathbf{Q}_{k-1}\right\|_{1}\right]\leq 10\sqrt{\frac{\hat{\sigma}_{F}^{2}L\left(f(\mathbf{X}_{1})-f^{*}\right)}{K\sigma_{op}^{2}}}+4\sqrt{mn}\sqrt[4]{\frac{\hat{\sigma}_{F}^{2}L\left(f(\mathbf{X}_{1})-f^{*}\right)}{K}},\end{aligned} (3) and \displaystyle\begin{aligned} \frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\left\|\nabla f(\mathbf{X}_{k})\right\|_{*}\right]\leq 10\sqrt{\frac{\hat{\sigma}_{F}^{2}L\left(f(\mathbf{X}_{1})-f^{*}\right)}{K\sigma_{op}^{2}}}+4\sqrt{mn}\sqrt[4]{\frac{\hat{\sigma}_{F}^{2}L\left(f(\mathbf{X}_{1})-f^{*}\right)}{K}}.\end{aligned} (4) The proof presented below follows the technical framework of AdamW