Tight Complexity of Muon under Heavy-Tailed Noise
Abstract
A growing lesson from neural network optimization is that optimizer design should respect how the model is parametrized. The layerwise input-output structure of neural networks motivates Muon and Scion, whose updates also support hyperparameter transfer. At the same time, stochastic gradient noise in deep learning is often far from sub-Gaussian and may exhibit heavy tails. These observations have shaped recent algorithmic principles for training neural networks, yet their joint theoretical consequences are underexplored. In particular, it is unclear what dimension dependence is unavoidable for gradient-based methods when the problem class is defined using an input-output norm and the stochastic gradient noise is heavy-tailed, and if higher-order smoothness can accelerate optimization. We study these questions through nonconvex smooth stochastic optimization over ℝm× n equipped with general norms and under pth-moment heavy-tailed noise, where the goal is to achieve an ε-stationary point in the dual norm. Our first contribution is a dimension-dependent lower bound: when max{m,n} is large enough, any method using only the stochastic gradients requires Ω(min{m, n}ε−(3p−2)/(p−1)) oracle calls for the problem class defined by the spectral norm, which is a common input-output matrix norm. We prove that a batched Muon method with the spectral norm can achieve the matching upper bound of O(min{m, n}ε−(3p−2)/(p−1)). To exploit higher-order smoothness, we propose a transported Muon method and improve the bound to O(min{m, n}ε−(5p−3)/(2p−2)) when the norm is spectral and the Hessian is Lipschitz. Finally, we incorporate practical heuristics into our transported method and evaluate it across multiple architectures and model sizes, showing its compatibility with neural network training.
Related
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
- Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition
- Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
- Accelerated Stochastic Method under (H0,H1)-Smoothness and Heavy-Tailed Noise
- Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
BibTeX
@misc{zhang2026tight,
title = {{Tight Complexity of Muon under Heavy-Tailed Noise}},
author = {Jiayu Zhang and Tianyi Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.18528},
eprint = {2605.18528},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.18528},
}
RIS
TY - UNPB
TI - Tight Complexity of Muon under Heavy-Tailed Noise
AU - Jiayu Zhang
AU - Tianyi Lin
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2605.18528
UR - https://arxiv.org/abs/2605.18528
AB - A growing lesson from neural network optimization is that optimizer design should respect how the model is parametrized. The layerwise input-output structure of neural networks motivates Muon and Scion, whose updates also support hyperparameter transfer. At the same time, stochastic gradient noise in deep learning is often far from sub-Gaussian and may exhibit heavy tails. These observations have shaped recent algorithmic principles for training neural networks, yet their joint theoretical consequences are underexplored. In particular, it is unclear what dimension dependence is unavoidable for gradient-based methods when the problem class is defined using an input-output norm and the stochastic gradient noise is heavy-tailed, and if higher-order smoothness can accelerate optimization. We study these questions through nonconvex smooth stochastic optimization over ℝ^m× n equipped with general norms and under p^th-moment heavy-tailed noise, where the goal is to achieve an ε-stationary point in the dual norm. Our first contribution is a dimension-dependent lower bound: when max{m,n} is large enough, any method using only the stochastic gradients requires Ω(min{m, n}ε^−(3p−2)/(p−1)) oracle calls for the problem class defined by the spectral norm, which is a common input-output matrix norm. We prove that a batched Muon method with the spectral norm can achieve the matching upper bound of O(min{m, n}ε^−(3p−2)/(p−1)). To exploit higher-order smoothness, we propose a transported Muon method and improve the bound to O(min{m, n}ε^−(5p−3)/(2p−2)) when the norm is spectral and the Hessian is Lipschitz. Finally, we incorporate practical heuristics into our transported method and evaluate it across multiple architectures and model sizes, showing its compatibility with neural network training.
ER -