Low-rank orthogonalization for large-scale matrix optimization with applications to foundation model training
Chuan He, Zhanwang Deng, Zhaosong Lu · 2025
Read Low-rank orthogonalization for large-scale matrix optimization with applications to foundation model training by Chuan He, Zhanwang Deng, Zhaosong Lu (2025) 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-2509-11983.txt.
Introduction
Training giant neural networks is, underneath, a huge matrix optimization problem, and Chuan He with two co-authors exploit that fact in 2025. Their starting point is Muon, an optimizer whose strong results in foundation model training come partly from orthogonalizing gradient matrices.
Full orthogonalization is expensive, so the authors note that gradients during training are nearly low-rank and orthogonalize only that lean structure. Two algorithms follow: a low-rank signed gradient method and a low-rank Muon. Tests on GPT-2 and LLaMA pretraining match or beat the carefully tuned original, with the clearest gains on larger models. Theory backs the practice, giving iteration complexity bounds for both methods, including a version that tolerates heavy-tailed noise in the stochastic setting.
Catalog record
| CREATOR | Chuan He, Zhanwang Deng, Zhaosong Lu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-11983
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Low-rank orthogonalization for large-scale matrix optimization with applications to foundation model training Chuan He, Zhanwang Deng, Zhaosong Lu Abstract Neural network (NN) training is inherently a large-scale matrix optimization problem, yet the matrix structure of NN parameters has long been overlooked. Recently, the optimizer Muon [ 28 ] , which explicitly exploits this structure, has gained significant attention for its strong performance in foundation model training. A key component contributing to Muon’s success is matrix orthogonalization. In this paper, we propose low-rank orthogonalization , which explicitly leverages the low-rank nature of gradients during NN training. Building on this, we propose low-rank matrix-signed gradient descent and a low-rank variant of Muon. Our numerical experiments demonstrate the superior performance of low-rank orthogonalization, with the low-rank Muon achieving promising results in GPT-2 and LLaMA pretraining—surpassing the performance of the carefully tuned vanilla Muon. Theoretically, we establish the iteration complexity of the low-rank matrix-signed gradient descent for finding an approximate stationary solution, as well as that of low-rank Muon for finding an approximate stochastic stationary solution under heavy-tailed noise. Keywords: Orthogonalization, Muon, foundation model training, iteration complexity, heavy-tailed noise Mathematics Subject Classification: 49M37, 90C30, 90C90 1 Introduction Training neural networks (NNs) [ 32 ] , particularly recent foundation models [ 8 ] , has consistently posed challenging large-scale optimization problems. Over the past decade, NN training has been dominated by vector-variate optimization methods—including SGD [ 9 ] , AdaGrad [ 18 ] , RMSprop [ 25 ] , Adadelta [ 55 ] , Adam [ 29 ] , and AdamW [ 37 ] . Nonetheless, these methods disregard the inherent matrix structure of NN parameters—such as those in multi-layer perceptrons [ 45 ] , convolutional layers [ 33 ] , and the query, key, and value projections in attention mechanisms [ 52 ] . Recently, a shift has taken place: optimization methods that exploit matrix structure are receiving increasing attention and have begun to demonstrate strong performance in foundation model training [ 28 , 35 , 41 ] . These methods focus on solving the matrix optimization problem: \displaystyle\min_{X\in\mathbb{R}^{m\times n}}f(X). (1) In particular, Shampoo, developed in [ 5 , 21 ] , applies left and right preconditioning matrices as follows: \displaystyle X^{k+1}=X^{k}-\eta_{k}(L^{k})^{-1/4}G^{k}(R^{k})^{-1/4}, (2) where \eta_{k}>0 is the step size, G^{k}\in\mathbb{R}^{m\times n} denotes the (stochastic) gradient of f at X^{k} , and L^{k}\in\mathbb{R}^{m\times m} and R^{k}\in\mathbb{R}^{n\times n} are the left and right preconditioning matrices, respectively. Shampoo updates the left and right preconditioners \{L^{k}\} and \{R^{k}\} using the second-order statistics of the accumulated gradients, similarly to AdaGrad, and has demonstrated comparable performance to popular vector-variate optimizers such as Adam and AdamW on foundation model training. Following Shampoo, other matrix-variate optimizers that use two-sided preconditioners, such as CASPR [ 19 ] and SOAP [ 53 ] , were also developed. A preconditioned Riemannian gradient descent method was developed in [ 7 ] for low-rank matrix recovery, which adopts only the diagonal part of the Shampoo preconditioners. Moreover, one-sided preconditioned variants of Shampoo were developed in [ 4 , 54 ] . In addition to Shampoo and its variants, another matrix-variate optimizer, Muon [ 28 ] , has attracted significant attention for outperforming standard optimizers such as Adam and AdamW in foundation model training [ 3 , 35 ] . At each iteration, Muon performs the update: \displaystyle M^{k}=(1-\theta_{k-1})M^{k-1}+\theta_{k-1}G(X^{k};\xi^{k}),\quad X^{k+1}=X^{k}-\eta_{k}\mathrm{msgn}(M^{k}), (3) where G(\cdot;\xi) is the stochastic gradient of f(\cdot) , and \mathrm{msgn}(M^{k})=U^{k}(V^{k})^{T} denotes the matrix sign of M^{k} , with U^{k} and V^{k} being the left and right singular vectors of M^{k} , respectively. The matrix sign computation is often referred to as matrix orthogonalization, because calculating \mathrm{msgn}(M) is equivalent to finding the (semi-)orthogonal matrix closest to M with respect to the Frobenius norm (see, e.g., [ 6 , Proposition 4] ). Muon’s empirical success has sparked significant research interest, including efforts to understand its relationship with other algorithms, establish its convergence guarantees, and propose new variants (see, e.g., [ 4 , 14 , 15 , 20 , 30 , 31 , 34 , 36 , 38 , 41 , 43 , 46 , 47 , 48 ] ). A popular interpretation of Muon is from the perspective of a linear minimization oracle with respect to the spectral norm (e.g., see [ 6 , 14 , 20 , 30 , 31 , 43 ] ). That is, the matrix sign computation in ( 3 ) can be recast as: \displaystyle-\mathrm{msgn}(M^{k})=\underset{\|\Delta\|\leq 1}{\arg\min}\{\langle M^{k},\Delta\rangle\}, where \|\cdot\| denotes spectral norm. Based on this interpretation, algorithmic designs leveraging general matrix-induced norms \|\cdot\|_{p\to q} have been discussed in [ 6 , 14 , 20 , 43 ] . In addition, Muon is also connected to earlier algorithms and can be viewed as a special case of Shampoo, despite not explicitly using preconditioners. As discussed in [ 28 ] , by taking L^{k}=G^{k}(G^{k})^{T} and R^{k}=(G^{k})^{T}G^{k} in ( 2 ), the Shampoo updates reduce to the matrix-signed update: X^{k+1}=X^{k}-\eta_{k}\mathrm{msgn}(G^{k}) . Furthermore, convergence guarantees for Muon have been extensively studied (e.g., see [ 4 , 15 , 30 , 34 , 43 , 46 , 47 , 48 ] ), and numerous new variants—such as SWAN [ 38 ] , Scion [ 41 ] , Gluon [ 43 ] , PolarGrad [ 31 ] , Dion [ 1 , 2 ] , and AdaMuon [ 49 ] —have been proposed. Beyond applying orthogonalization, a key innovation of Muon is the use of a more GPU-friendly method—specifically, Newton-Schulz iterations (typically with five steps)—to perform inexact orthogonalization, which makes Muon well-suited for modern foundation model training. In fact, several earlier methods, including spectral gradient descent [ 10 , 11 , 12 ] and orthogonalized gradient descent [ 51 ] , have applied orthogonalization using SVD to matrix optimization problems. However, since SVD is not computationally efficient in GPU environments, these methods fail to scale to foundation model training. Inspired by Muon and its orthogonalization subroutine, we aim at developing a faster, lightweight orthogonalization method to be implemented in Muon and its variants. Specifically, our design leverages the widely observed phenomenon that the gradient matrices of NN parameters are often low-rank (see, e.g., [ 23 , 26 , 39 , 57 ] ). To exploit this low-rank property, we propose performing low-rank orthogonalization by incorporating well-known matrix approximation techniques for low-rank matrices [ 16 , 22 ] . Our approach first constructs a low-rank projection of the gradient matrix using QR decomposition on a sketched matrix, and then performs orthogonalization on the projected matrix by leveraging its structure. Our proposed low-rank orthogonalization offers two main advantages over common orthogonalization: • Computational efficiency: Orthogonalization can be seen as computing the polar factor of a given full matrix. In contrast, our low-rank orthogonalization first computes the Q factor of a smaller sketched matrix, followed by the polar factor of a projected matrix constructed using the Q factor. Since both the QR decomposition and polar decomposition are performed on much smaller matrices, our low-rank approach enjoys substantial computational savings for large-scale problems. • Noise robustness: In the presence of noise, singular vectors associated with small singular values often vary significantly, leading to instability in orthogonalization via Newton–Schulz iterations. By contrast, our low-rank orthogonalization method clips these singular vectors to eliminate unstable estimates