# Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise

arXiv: https://arxiv.org/abs/2506.04192 · HTML: https://mlsanity.com/paper/2506.04192/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 77 of its 105 references that are in the map.
- First posted on arXiv 4 Jun 2025.

## Builds on (most cited first, 30 of 77)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SOAP: Improving and Stabilizing Shampoo using Adam](https://mlsanity.com/paper/2409.11321/) (2024)
- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be](https://mlsanity.com/paper/2304.13960/) (2023)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Linear attention is (maybe) all you need (to understand transformer optimization)](https://mlsanity.com/paper/2310.01082/) (2023)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [A Note on the Convergence of Muon](https://mlsanity.com/paper/2502.02900/) (2025)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs)](https://mlsanity.com/paper/2505.13416/) (2025)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [A New Perspective on Shampoo's Preconditioner](https://mlsanity.com/paper/2406.17748/) (2024)
- [Implicit Bias of AdamW: ℓ_∞ Norm Constrained Optimization](https://mlsanity.com/paper/2404.04454/) (2024)
- [Rotational Equilibrium: How Weight Decay Balances Learning Across Neural Networks](https://mlsanity.com/paper/2305.17212/) (2023)
- [PolarGrad: A Class of Matrix-Gradient Optimizers from a Unifying Preconditioning Perspective](https://mlsanity.com/paper/2505.21799/) (2025)
- [Lion Secretly Solves Constrained Optimization: As Lyapunov Predicts](https://mlsanity.com/paper/2310.05898/) (2023)
- [Stochastic Sign Descent Methods: New Algorithms and Better Theory](https://mlsanity.com/paper/1905.12938/) (2019)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)

## Built on by (most cited first, 30 of 41)

- [Muon Optimizes Under Spectral Norm Constraints](https://mlsanity.com/paper/2506.15054/) (2025)
- [Isotropic Curvature Model for Understanding Deep Learning Optimization: Is Gradient Orthogonalization Optimal?](https://mlsanity.com/paper/2511.00674/) (2025)
- [On the Convergence of Muon and Beyond](https://mlsanity.com/paper/2509.15816/) (2025)
- [LiMuon: Light and Fast Muon Optimizer for Large Models](https://mlsanity.com/paper/2509.14562/) (2025)
- [Low-rank Orthogonalization for Large-scale Matrix Optimization with Applications to Foundation Model Training](https://mlsanity.com/paper/2509.11983/) (2025)
- [MuonEq: Balancing Before Orthogonalization with Lightweight Equilibration](https://mlsanity.com/paper/2603.28254/) (2026)
- [Cautious Weight Decay](https://mlsanity.com/paper/2510.12402/) (2025)
- [MARS-M: When Variance Reduction Meets Matrices](https://mlsanity.com/paper/2510.21800/) (2025)
- [Muon Does Not Converge on Convex Lipschitz Functions](https://mlsanity.com/paper/2605.08980/) (2026)
- [On Provable Benefits of Muon in Federated Learning](https://mlsanity.com/paper/2510.03866/) (2025)
- [Muon is Provably Faster with Momentum Variance Reduction](https://mlsanity.com/paper/2512.16598/) (2025)
- [Convergence Analysis of the Lion Optimizer in Centralized and Distributed Settings](https://mlsanity.com/paper/2508.12327/) (2025)
- [Muown: Row-Norm Control for Muon Optimization](https://mlsanity.com/paper/2605.10797/) (2026)
- [A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent](https://mlsanity.com/paper/2511.20584/) (2025)
- [Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2608.26288/) (2026)
- [DeMuon: A Decentralized Muon for Matrix Optimization over Graphs](https://mlsanity.com/paper/2510.01377/) (2025)
- [OLion: Approaching the Hadamard Ideal by Intersecting Spectral and ℓ∞ Implicit Biases](https://mlsanity.com/paper/2602.01105/) (2026)
- [Communication-Efficient Gluon in Federated Learning](https://mlsanity.com/paper/2604.10689/) (2026)
- [MiMuon: Mixed Muon Optimizer with Improved Generalization for Large Models](https://mlsanity.com/paper/2605.19619/) (2026)
- [CacheMuon: Using Temporal Preconditioning To Approximate Polar Factor](https://mlsanity.com/paper/2606.16371/) (2026)
- [Federated Stochastic Minimax Optimization under Heavy-Tailed Noises](https://mlsanity.com/paper/2511.04456/) (2025)
- [When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds](https://mlsanity.com/paper/2605.06615/) (2026)
- [Tight Complexity of Muon under Heavy-Tailed Noise](https://mlsanity.com/paper/2605.18528/) (2026)
- [LionMuon: Alternating Spectral and Sign Descent for Efficient Training](https://mlsanity.com/paper/2605.19811/) (2026)
- [Convergence of Spectral Descent for Non-smooth Optimization](https://mlsanity.com/paper/2605.26977/) (2026)
- [Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success](https://mlsanity.com/paper/2606.14560/) (2026)
- [When to use what Schatten-p norm in deep learning?](https://mlsanity.com/paper/2606.15268/) (2026)
- [Towards Understanding the Power and Limits of the Muon Optimizer: A River-Valley Perspective](https://mlsanity.com/paper/2606.21514/) (2026)
- [Muse: Representation Geometry of Muon Beyond Normalized Momentum](https://mlsanity.com/paper/2607.14536/) (2026)
- [CLion: Efficient Cautious Lion Optimizer with Enhanced Generalization](https://mlsanity.com/paper/2604.14587/) (2026)

## Abstract (arXiv)

Stochastic Frank-Wolfe is a classical optimization method for solving constrained optimization problems. On the other hand, recent optimizers such as Lion and Muon have gained quite significant popularity in deep learning. In this work, building on recent initiatives, we provide a unifying perspective by interpreting these seemingly disparate methods through the lens of Stochastic Frank-Wolfe. Specifically, we show that Lion and Muon with weight decay can be viewed as special instances of a Stochastic Frank-Wolfe, and we establish their convergence guarantees in terms of the Frank-Wolfe gap, a standard stationarity measure in non-convex optimization for Frank-Wolfe methods. We further find that convergence to this gap implies convergence to a KKT point of the original problem under a norm constraint for Lion and Muon. Moreover, motivated by recent empirical findings that stochastic gradients in modern machine learning tasks often exhibit heavy-tailed distributions, we extend Stochastic Frank-Wolfe to settings with heavy-tailed noise by developing two robust variants with strong theoretical guarantees that hold for general compact convex sets without the need for a large batch size, filling the gap in the literature on Stochastic Frank-Wolfe for non-convex optimization. Our contributions in the later part of this work, in turn, yield new variants of Lion and Muon, that better accommodate heavy-tailed gradient noise, thereby enhancing their practical scope.