Accelerating LMO-Based Optimization via Implicit Gradient Transport
Won-Jun Jang, Si-Hyeon Lee · 2026
Read Accelerating LMO-Based Optimization via Implicit Gradient Transport by Won-Jun Jang, Si-Hyeon Lee (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-2605-05577.txt.
Introduction
Optimizers like Lion and Muon normalize gradient momentum through a linear minimization oracle, and they train large models well. Won-Jun Jang and Si-Hyeon Lee set out to speed up that family without paying for extra gradient evaluations. Earlier variance-reduction tricks accelerated these methods but cost too much computation.
Their approach, LMO-IGT, transports gradients implicitly to cut variance cheaply. They also unify the theory across constrained and unconstrained settings, introducing a stationarity measure called the regularized support function. The new measure bridges gradient-based and oracle-based viewpoints, clarifying when these optimizers can be trusted to converge.
Catalog record
| CREATOR | Won-Jun Jang, Si-Hyeon Lee |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05577
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accelerating LMO-Based Optimization via Implicit Gradient Transport Won-Jun Jang, Si-Hyeon Lee Abstract Recent optimizers such as Lion and Muon have demonstrated strong empirical performance by normalizing gradient momentum via linear minimization oracles (LMOs). While variance reduction has been explored to accelerate LMO-based methods, it typically incurs substantial computational overhead due to additional gradient evaluations. At the same time, the theoretical understanding of LMO-based methods remains fragmented across unconstrained and constrained formulations. Motivated by these limitations, we propose LMO-IGT , a new class of stochastic LMO-based methods leveraging implicit gradient transport (IGT). We further introduce a unified framework for stochastic LMO-based optimization together with a new stationarity measure, the regularized support function (RSF), which bridges gradient-norm and Frank–Wolfe-gap notions within a common framework. By evaluating stochastic gradients at transported points, LMO-IGT accelerates convergence while retaining the single-gradient-per-iteration structure of standard stochastic LMO. Our analysis establishes that stochastic LMO achieves an iteration complexity of 𝒪 ( ε − 4 ) \mathcal{O}(\varepsilon^{-4}) , variance-reduced LMO achieves 𝒪 ( ε − 3 ) \mathcal{O}(\varepsilon^{-3}) at the cost of additional gradient evaluations, and LMO-IGT achieves 𝒪 ( ε − 3.5 ) \mathcal{O}(\varepsilon^{-3.5}) using only a single stochastic gradient per iteration. Empirically, LMO-IGT consistently improves over stochastic LMO counterparts with negligible overhead. Among its instantiations, Muon-IGT achieves the strongest overall performance across evaluated settings, demonstrating that IGT provides an effective and practical acceleration mechanism for modern LMO-based optimization. 1 Introduction Deep learning has achieved remarkable success in recent years, increasing the need for reliable optimization methods for training large-scale neural networks. Training such models involves high-dimensional and non-convex optimization problems, making efficient and stable algorithms essential. Consequently, efficient stochastic gradient-based optimizers such as Adam ( 30 ) and AdamW ( 33 ) have long been the standard choice. Recently, new optimizers such as Lion ( 10 ) and Muon ( 26 ) have attracted significant attention due to their strong empirical performance. A common feature of these methods is that they normalize the gradient momentum during optimization, a property closely related to the linear minimization oracle (LMO). Following this, a line of work has focused on improving the convergence of LMO-based methods, where techniques such as variance reduction achieve faster theoretical rates ( 25 ; 47 ; 6 ; 41 ) . However, these approaches typically require additional gradient evaluations, which can be computationally expensive in large-scale settings. This raises a natural question: can LMO-based methods achieve accelerated convergence while avoiding the substantial computational overhead associated with variance reduction? From a theoretical perspective, LMO originates from the Frank–Wolfe method for constrained optimization ( 25 ; 41 ; 36 ) . However, the role of LMO-type updates in modern stochastic optimization is not yet fully understood. In particular, existing analyses often rely on different stationarity measures for unconstrained and constrained problems, preventing a unified treatment across settings. This leads to a second question: can stochastic LMO-based optimization be understood within a unified framework? We address the above questions through the following contributions. Low-overhead acceleration for LMO-based optimization. To accelerate LMO-based methods while avoiding the substantial computational overhead of variance reduction, we draw inspiration from implicit gradient transport (IGT), which constructs momentum using gradients evaluated at a lookahead point ( 1 ; 11 ) . While IGT has been studied in normalized gradient methods, we extend it to LMO-based optimization. We observe that LMO updates inherently perform a form of momentum normalization, making them well-suited for IGT-style acceleration. Based on this insight, we propose a new class of methods, termed LMO-IGT, that achieves accelerated convergence without additional gradient evaluations. Unified framework and analysis. We develop a unified framework for stochastic LMO-based optimization, encompassing three classes: stochastic LMO, variance-reduced LMO (LMO-VR), and the proposed LMO-IGT. To enable a unified analysis across both unconstrained and constrained settings, we introduce a new stationarity measure, the regularized support function (RSF) , which bridges gradient-based and Frank–Wolfe-type measures. Under this framework, we establish unified convergence results: stochastic LMO achieves an iteration complexity of O(\epsilon^{-4}) , LMO-VR achieves O(\epsilon^{-3}) , and LMO-IGT attains O(\epsilon^{-3.5}) , while incurring only modest computational overhead. Empirical validation. We instantiate LMO-IGT with different LMO sets, yielding practical algorithms such as Lion-IGT and Muon-IGT. In particular, Muon-IGT achieves the strongest empirical performance without requiring extra gradient evaluations, demonstrating the effectiveness of the proposed approach in large-scale settings. Table 1 summarizes the three classes in our unified framework, together with representative algorithms, the associated LMO sets, and their corresponding iteration complexities. Table 1: Unified framework for stochastic LMO-based optimization and the corresponding convergence results. For a gradient momentum matrix g , we write its singular value decomposition (SVD) as g=U\text{diag}(\sigma)V^{\top} . See Section II for the definition of the LMO and the set \mathcal{C} . Class Algorithm LMO set \mathcal{C} LMO {}_{\mathcal{C}}(g) Iteration Complexity \begin{array}[]{c}\text{Stochastic}\\ \text{LMO}\\ \text{\footnotesize(1 gradient eval.)}\end{array} Normalized SGD ( 22 ) \|\cdot\|_{2} –ball -g/||g|| O(\epsilon^{-4}) signSGD ( 4 ) \|\cdot\|_{\infty} –ball - sign (g) Signum ( 4 ) Lion ( 10 ) Muon ( 26 ) \|\cdot\|_{\text{op}} –ball ∗ -UV^{\top} \begin{array}[]{c}\text{LMO-VR}\\ \text{(2 gradient eval.)}\end{array} Lion-VR ( 25 ) \|\cdot\|_{\infty} –ball - sign (g) O(\epsilon^{-3}) MARS-Shampoo ( 47 ) \|\cdot\|_{\text{op}} –ball ∗ -UV^{\top} Muon-VR ( 41 ) \begin{array}[]{c}\text{LMO-IGT}\\ \text{(1 gradient eval.)}\end{array} NIGT ( 11 ) \|\cdot\|_{2} –ball -g/||g|| O(\epsilon^{-3.5}) Lion-IGT (this work) \|\cdot\|_{\infty} –ball - sign (g) Muon-IGT (this work) \|\cdot\|_{\text{op}} –ball ∗ -UV^{\top} ∗ operator norm ball for matrices: \mathcal{C}=\{X\,|\,\sigma_{1}(X)\leq 1\} . 2 Problem Setting and Preliminaries Let \xi denote a random variable capturing the stochasticity of the oracle, and let f(\cdot;\xi) denote the corresponding sample-wise loss function. We consider the stochastic first-order minimization problem \displaystyle\min_{w\in\mathcal{P}}F(w),\qquad F(w):=\mathbb{E}_{\xi}[f(w;\xi)], (1) where F:\mathbb{R}^{d}\to\mathbb{R} and f are non-convex, differentiable functions. We assume that the feasible set \mathcal{P}\subseteq\mathbb{R}^{d} is convex and compact. We make the following assumptions: Assupmtion 1 ( L -smoothness) . The function F is L -smooth: \|\nabla F(x)-\nabla F(y)\|\leq L\|x-y\|,\qquad\forall x,y\in\mathbb{R}^{d}. Assupmtion 2 (Bounded variance) . The stochastic gradients have bounded variance: \mathbb{E}_{\xi}\!\left[\|\nabla f(w;\xi)-\nabla F(w)\|^{2}\right]\leq\sigma^{2},\qquad\forall w\in\mathbb{R}^{d}. Assupmtion 3 (Averaged smoothness) . There exists L>0 such that \mathbb{E}_{\xi}\!\left[\|\nabla f(x;\xi)-\nabla f(y;\xi)\|^{2}\right]\leq L^{2}\|x-y\|^{2},\qquad\forall x,y\in\mathbb{R}^{d}. Assupmtion 4 (Second-order smoothness) . The Hessian of F is \rho -Lipschitz: \|\nabla^{2}F(x)-\nabla^{2}F(y)\|_{\mathrm{op}}\leq\rho\|x-y\|,\qquad\forall x,y\in\mathbb{R}^{d}. Assumptions 1 and 2 are standard in stochastic optimization. Assumption 3 is commonly used in variance-reduced methods, while Assumption 4 is a standard second-order regularity condition in analyses of IGT ( 11 ) . In the rest of this section, we introduce the necessary preliminaries. We begin by describing the update rule of LMO-based optimization methods, followed by their Frank–Wolfe interpretation and the associated stationarity measure, the Frank–Wolfe gap. We then summarize the convergence behavior of stochastic LMO methods and discuss variance reduction as an acceleration technique. Finally, we present IGT as an alternative acceleration mechanism. A more detailed discussion of related work is provided in Appendix A . 2.1 LMO-Based Updates To solve ( 1 ), both normalized SGD and LMO-based optimization methods (e.g., Lion and Muon) compute, given a gradient or momentum estimate g , the linear minimization oracle (LMO) \operatorname{LMO}_{\mathcal{C}}(g)\in\arg\min_{v\in\mathcal{C}}\langle g,v\rangle. Here, \mathcal{C}\subseteq\mathbb{R}^{d} is a compact convex set containing the origin. Equivalently, the oracle returns the point in \mathcal{C} most aligned with the descent direction -g . The specific form of \operatorname{LMO}_{\mathcal{C}}(\cdot) depends on \mathcal{C} . For example, if