ASGO: Adaptive Structured Gradient Optimization

Kang An, Yuxing Liu , Rui Pan, Yi Ren, Shiqian Ma, Donald Goldfarb, Tong Zhang · 2025

Read ASGO: Adaptive Structured Gradient Optimization by Kang An, Yuxing Liu , Rui Pan, Yi Ren, Shiqian Ma, Donald Goldfarb, Tong Zhang (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-2503-20762.txt.

Introduction

Training deep networks is a matrix problem at heart, yet the most popular optimizers treat the weights as one long vector and ignore that shape. Kang An and co-authors present ASGO in this 2025 paper, an optimizer built to exploit the structure. Gradients tend to be low-rank, and curvature tends to split into blocks; ASGO's preconditioner adapts to both.

Their theory shows faster convergence than rival structured methods, with gains that grow when the low-rank and block patterns are strong. Practical tweaks make the method usable, and tests on language model tasks confirm its edge. The authors share their code. The paper speaks to anyone training large models who wants each step to respect how the parameters are really arranged.

Catalog record

CREATORKang An, Yuxing Liu , Rui Pan, Yi Ren, Shiqian Ma, Donald Goldfarb, Tong Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20762

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ASGO: Adaptive Structured Gradient Optimization Kang An, Yuxing Liu , Rui Pan, Yi Ren, Shiqian Ma, Donald Goldfarb, Tong Zhang Abstract Training deep neural networks is a structured optimization problem, because the parameters are naturally represented by matrices and tensors rather than by vectors. Under this structural representation, it has been widely observed that gradients are low-rank and Hessians are approximately block diagonal. These structured properties are crucial for designing efficient optimization algorithms, but are not utilized by many current popular optimizers like Adam. In this paper, we present a novel optimization algorithm ASGO that capitalizes on these properties by employing a preconditioner that is adaptively updated using structured gradients. By a fine-grained theoretical analysis, ASGO is proven to achieve superior convergence rates compared to existing structured gradient methods. Based on this convergence theory, we further demonstrate that ASGO can benefit from low-rank gradients and block diagonal Hessians. We also discuss practical modifications of ASGO and empirically verify ASGO’s effectiveness on language model tasks. Code is available at https://github.com/infinity-stars/ASGO . 1 Introduction Numerical optimization algorithms, especially those that can efficiently train large foundation models ( Devlin et al., 2018 ; Brown et al., 2020 ; Touvron et al., 2023a ; Touvron et al., 2023b ; Ouyang et al., 2022 ) , play an important role in the modern machine learning field. Among them, adaptive gradient methods like AdaGrad ( Duchi et al., 2011 ) and Adam ( Kingma and Ba, 2014 ) are popular choices, gaining huge success in training state-of-the-art models in many tasks. These algorithms typically apply a diagonal matrix preconditioner to the gradient g_{t} to update the deep neural network (DNN) parameters w_{t} ; \displaystyle w_{t+1}=w_{t}-\eta_{t}\Lambda_{t}^{-1}g_{t},\text{ where $w_{t}\in\mathbb{R}^{d}$, $g_{t}\in\mathbb{R}^{d}$, and $\Lambda_{t}\in\mathbb{R}^{d\times d}$ is a diagonal matrix}. This coordinate-wise step size design has been theoretically verified to be effective as it can exploit the sparsity of the gradient vectors g_{t} ( Duchi et al., 2011 ) . Also, when the Hessian is well-approximated by a diagonal matrix whose diagonal entries have very different scales, adaptive gradient methods have been proven to be beneficial ( Liu et al., 2024 ; Jiang et al., 2024a ; Xie et al., 2024 ) . While these results seem to be convincing, common DNNs do not necessarily have sparse gradients or Hessians that are well-approximated by ill-conditioned diagonal matrices. Instead, if we take the matrix structure of gradients in DNNs into account, it has been widely observed that these structured gradients are usually low-rank ( Zhao et al., 2021 ; Yang et al., 2023 ; Cosson et al., 2023 ) , and the Hessians are well-approximated by block diagonal matrices ( Collobert, 2004 ; Zhang et al., 2024a ; Zhang et al., 2024b ) . Since adaptive gradient methods like Adam, treat the parameters as vectors and ignore the matrix structure of gradients, they are generally unable to exploit these structured properties. This leads us to ask the following question: How can we effectively use the matrix structure of gradients to exploit their low-rank and block diagonal properties? One possible answer is provided by Shampoo ( Gupta et al., 2018 ) : \displaystyle W_{t+1}=W_{t}-\eta_{t}L_{t}^{-\frac{1}{4}}G_{t}R_{t}^{-\frac{1}{4}},\text{ where $W_{t},G_{t}\in\mathbb{R}^{m\times n}$ and $L_{t}\in\mathbb{R}^{m\times m}$, $R_{t}\in\mathbb{R}^{n\times n}$ are full matrices.} The main motivation for such a design is that if we apply vectorization to the update, the Shampoo preconditioner is a single matrix that is the Kronecker product of L_{t}^{-\frac{1}{4}} and R_{t}^{-\frac{1}{4}} , which approximates the full-matrix preconditioner for AdaGrad ( Duchi et al., 2011 ) . However, the theoretical convergence of Shampoo is worse than that for AdaGrad or even SGD when the dimension is large. Also, Shampoo needs more memory and much heavier computation than adaptive gradient methods because it requires two preconditioners, making it less suitable for training large-scale DNNs. In this paper, we provide an answer to the aforementioned question by proposing ASGO ( A daptive S tructured G radient O ptimization), which significantly improves the convergence guarantees of Shampoo while requiring less memory and computation. In light of the analysis that demonstrates the benefits of adaptive gradient methods ( Duchi et al., 2011 ; Liu et al., 2024 ; Jiang et al., 2024a ; Xie et al., 2020 ) , we use appropriate assumptions to enable a more fine-grained convergence analysis, that yields superior convergence results and an explanation of how ASGO can benefit from the low-rank and block diagonal properties of a given problem. We also discuss the connection between ASGO and Muon ( Jordan et al., 2024 ) , a structured gradient method based upon the steepest descent algorithm with respect to the spectral norm, to conjecture a relation between ASGO and Muon analogous to the relation between AdaGrad and SignSGD ( Bernstein et al., 2018 ; Kunstner et al., 2023 ) . Furthermore, we develop an efficient design for query-key attention parameters in transformer models and examine its empirical performance on pretraining transformer model tasks. Our main contributions are summarized as follows. • We propose the structured gradient based algorithm ASGO, theoretically analyze its convergence, and show that it converges faster than full-matrix AdaGrad and Shampoo. • We further demonstrate that ASGO can effectively exploit the low-rankness of gradients as well as the approximate block diagonal property of Hessians that is typically observed in training DNNS, indicating good theoretical properties under realistic settings. • We develop a practical implementation of ASGO that is efficient while enhancing ASGO’s effectiveness. We further empirically validate the effectiveness and efficiency of this implementation on language model tasks, demonstrating the algorithm’s great potential in real applications. 2 Related Work Adaptive Gradient Methods. Adaptive gradient methods that use diagonal preconditioners to speedup convergence are extremely popular for solving many real-world optimization problems. To the best of our knowledge, the first method of this kind for machine learning, AdaGrad ( Duchi et al., 2011 ; Streeter and McMahan, 2010 ) , was developed based on rigorous theory that showed the benefits of using this kind of preconditioner. Adam ( Kingma and Ba, 2014 ; Loshchilov and Hutter, 2017 ) modified AdaGrad and has become the default choice for training large foundation models. In theory, it has been proven that adaptive gradient methods can benefit from sparse gradients and approximately ill-conditioned Hessians ( Duchi et al., 2011 ; Liu et al., 2024 ; Jiang et al., 2024a ; Xie et al., 2024 ) . It is worth noting that the original AdaGrad paper ( Duchi et al., 2011 ) also proposed a version of AdaGrad that uses a full-matrix preconditioner instead of the diagonal one, which is believed to perform even better. However, this full-matrix AdaGrad method suffers from large memory costs for storing the preconditioner, while having no better convergence guarantee compared to diagonal AdaGrad and SGD under the assumption of objective function convexity as described in Section 4 below. Optimization with Matrix Structure. In the standard optimization literature (i.e., excluding areas such as conic optimization), it is common to consider variables as vectors. However, recently, optimization methods for machine learning that consider variables as matrices have been rapidly gaining attention. Adafactor ( Shazeer and Stern, 2018 ) , LAMB ( You et al., 2019 ) , and Adam-mini ( Zhang et al., 2024b ) consider the

Read the complete text