Muon Converges under Heavy-Tailed Noise: Nonconvex Hölder-Smooth Empirical Risk Minimization

Hideaki Iiduka

In the high-stakes world of large-scale deep learning, the choice of optimizer can be the difference between a state-of-the-art model and a wasted million-dollar training run. Recently, the Muon optimizer has gained traction for its ability to stabilize training by enforcing orthogonality in parameter updates. But while Muon works well in practice, the theoretical "why" has lagged behind—especially when dealing with the messy, unpredictable noise found in real-world data.

A new paper by Hideaki Iiduka, titled "Muon Converges under Heavy-Tailed Noise," provides the mathematical heavy lifting needed to justify Muon’s success. The research proves that Muon isn't just stable; it actually converges faster than standard Stochastic Gradient Descent (SGD) when faced with non-smooth functions and "heavy-tailed" noise.

TL;DR

This paper provides the first rigorous convergence analysis of the Muon optimizer under realistic, "nasty" conditions: nonconvex functions with Hölder-smooth gradients and heavy-tailed stochastic noise. The core finding is that Muon’s strategy of projecting gradients onto the Stiefel manifold allows it to achieve a significantly faster convergence rate than mini-batch SGD in these settings.

What Problem Does This Paper Address?

Most theoretical proofs for optimizers rely on two "nice" assumptions:

  1. Smoothness: The gradient of the loss function changes predictably (Lipschitz continuity).
  2. Light-Tailed Noise: The "errors" in our mini-batch gradients have a bounded variance (they follow a roughly Normal distribution).

In reality, deep learning is rarely that polite. Loss landscapes can be jagged (only Hölder-smooth), and stochastic noise often exhibits heavy-tailed behavior—meaning we frequently encounter "outlier" gradients that are much larger than average. Standard SGD can struggle or even diverge under these conditions. Muon was designed to be robust, but until now, we didn't have a formal proof that it could handle these specific mathematical hurdles.

Methods

The author analyzes the Muon optimizer, which differs from SGD in one crucial way: instead of updating parameters directly along the stochastic gradient, Muon finds the "closest" point on the Stiefel manifold (the set of matrices with orthonormal columns) and uses that as the update direction.

Key components of the analysis include:

  • Hölder Smoothness: A generalization of standard smoothness that allows for more "jagged" functions.
  • $p$-variance: Instead of assuming standard variance (where $p=2$) is bounded, the author assumes $p$-variance is bounded for $p \in (1, 2]$. This mathematically accounts for the "spikes" in heavy-tailed noise.
  • Newton-Schulz Iteration: The paper acknowledges the practical implementation of Muon, which uses this iterative method to approximate the orthogonal projection efficiently.
  • Super Martingale Convergence: The author uses advanced probabilistic tools to prove that the gradient will eventually shrink to zero (stationary point) "almost surely."

Datasets

This is a purely theoretical paper. It does not perform experiments on standard benchmarks like ImageNet or GLUE. Instead, it provides mathematical examples (specifically Example 2.1) to demonstrate that common loss functions used in deep learning satisfy the rigorous assumptions required for the proofs.

Key Insights and Ideas

  • Geometry as a Stabilizer: The "aha moment" is that by forcing updates to be orthogonal (projecting onto the Stiefel manifold), Muon effectively ignores the extreme magnitudes of heavy-tailed noise. While a massive "outlier" gradient might throw SGD off track, Muon simply looks at the direction of that gradient and maps it to a stable, orthonormal update.
  • Superior Convergence Rates: The paper reveals a stark difference in speed. Under the same noise conditions, the convergence rate for SGD is roughly the square root of the rate for Muon.
  • Fewer Constraints: Theoretically, SGD requires very specific, often unrealistic conditions on step sizes and batch sizes to guarantee convergence under heavy-tailed noise. Muon, by contrast, converges under much simpler and more flexible conditions.

Key Results

The paper provides a quantitative comparison of the convergence rates (the speed at which the gradient reaches zero):

  • Mini-batch SGD: $O\left(\frac{1}{T^{\frac{1-a}{2}}}\right)$
  • Muon: $O\left(\frac{1}{T^{1-a}}\right)$

(Where $T$ is the number of iterations and $a$ is a step-size parameter).

In plain English: Muon is significantly faster. Because the exponent for Muon is larger (1-a vs (1-a)/2), it requires fewer iterations to reach the same level of precision as SGD when the noise is heavy-tailed.

Limitations and Future Work

  • Theoretical vs. Empirical Gap: While the math says Muon is faster, this paper doesn't show how much that translates to wall-clock time on a GPU, especially given the extra overhead of the Newton-Schulz iterations.
  • Finite Minimizers: The proofs assume the existence of a local minimizer ($f^*$ is finite), which is standard but worth noting.
  • Hyperparameter Sensitivity: The analysis focuses on the existence of a convergence path; future work could explore how sensitive this path is to the choice of the momentum parameter ($\beta$) in practical settings.

By bridging the gap between empirical success and theoretical necessity, this paper solidifies Muon’s place as a mathematically sound alternative to SGD for the next generation of large-scale models.

Summary updated

Abstract

Muon is a recently proposed optimizer that enforces orthogonality in parameter updates by projecting gradients onto the Stiefel manifold, leading to stable and efficient training in large-scale deep neural networks. Meanwhile, the previously reported results indicated that stochastic noise in practical machine learning may exhibit heavy-tailed behavior, violating the bounded-variance assumption. In this paper, we consider the problem of minimizing a nonconvex Hölder-smooth empirical risk that works well with the heavy-tailed stochastic noise. We then show that Muon converges to a stationary point of the empirical risk under the boundedness condition accounting for heavy-tailed stochastic noise. In addition, we show that Muon converges faster than mini-batch SGD.
BibTeX
@misc{iiduka2026muon,
  author = {Hideaki Iiduka},
  title = {{Muon Converges under Heavy-Tailed Noise: Nonconvex Hölder-Smooth Empirical Risk Minimization}},
  year = {2026},
  eprint = {2603.15059},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.15059},
}
Figure