Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success

• URL: http://arxiv.org/abs/2606.14560v1
• Date: Fri, 12 Jun 2026 15:37:36 GMT
• Title: Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success
• Abstract summary: We show that nonfracean Transformer updates can perform competitively in certain settings.<n>Surprisingly, this sample is optimal for all first-order methods under nuclear-normarity.<n>Our results suggest that other spectral geometry can perform competitively in certain settings.
• Score: 26.792629169897747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-Euclidean optimisation methods with matrix-valued updates, such as Muon and Scion, have recently shown strong empirical performance for training Transformer models, yet their theoretical advantages over Euclidean methods remain poorly understood. We address this gap in the heavy-tailed non-convex regime, where stochastic gradients have bounded $p$-th central moments, $p \in (1,2]$. We show that certain non-Euclidean methods achieve optimal sample complexity under stronger stationarity measures, while Euclidean methods incur additional dimension-dependent costs. As a consequence, for $m \times n$ matrices, Muon finds an $\varepsilon$-stationary point in nuclear norm within $\mathcal{O}\left(\min\{m, n\} \frac{Δ_1 L}{\varepsilon^2} \left(\frac σ\varepsilon \right)^{\frac p {p-1}}\right)$ samples, absorbing heavy-tailed noise without extra dimension dependence, unlike Euclidean methods. We further prove this sample complexity, including its dimension dependence, is optimal for all first-order methods under nuclear-norm stationarity. Experiments on large language models support our theory. Surprisingly, our results suggest that other Schatten geometries beyond the spectral geometry of Muon can perform competitively in certain settings.

Related papers

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Entropic Riemannian Neural Optimal Transport [41.69130102668252]
  We propose a unified framework that combines intrinsic entropic OT and amortized out-of-sample evaluation.<n>Our method matches or improves over Euclidean, tangent-space, and log-Euclidean baselines on benchmarks over $mathbbS2$, $mathrmSO(3)$, $mathrmSPD(3)$, $mathrmSE(3)$, and $mathbbH2$.
  arXiv  Detail & Related papers  (2026-05-05T19:43:03Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization [55.002497070656624]
  Broximal Point Method (BPM) offers an idealized optimization framework based on iteratively minimizing the objective function over norm balls centered at the current iterate.<n>It enjoys striking global convergence guarantees, converging linearly and in a finite number of steps for proper, closed and convex functions.<n>In this note, we ask whether the convergence theory of BPM can be extended to this more general, non-Euclidean setting.
  arXiv  Detail & Related papers  (2025-10-01T12:32:52Z)
• Approximating fixed size quantum correlations in polynomial time [8.099700053397278]
  We show that $varepsilon$-additive approximations of the optimal value of fixed-size two-player free games can be computed in time.<n>Our main result is based on novel Bose-symmetric quantum de Finetti theorems tailored for constrained quantum separability problems.
  arXiv  Detail & Related papers  (2025-07-16T15:01:45Z)
• Local Averaging Accurately Distills Manifold Structure From Noisy Data [4.63748375343038]
  Local averaging is a cornerstone of state-of-the-art provable methods for manifold fitting and denoising.<n>We provide theoretical analyses of a two-round mini-batch local averaging method applied to noisy samples drawn from a $d$-dimensional manifold.<n>The proposed method can serve as a preprocessing step for a wide range of provable methods designed for lower-noise regimes.
  arXiv  Detail & Related papers  (2025-06-23T15:32:16Z)
• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
  This work introduces a hybrid non-Euclidean optimization method which generalizes norm clipping by combining steepest descent and conditional gradient approaches.<n>We discuss how to instantiate the algorithms for deep learning and demonstrate their properties on image classification and language modeling.
  arXiv  Detail & Related papers  (2025-06-02T17:34:29Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  We study high-probability convergence in online learning, in the presence of heavy-tailed noise.<n>We provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments.
  arXiv  Detail & Related papers  (2024-10-17T18:25:28Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization [30.26365073195728]
  We study the generalization performance of gradient methods in the fundamental convex optimization setting. We show that an application of the same construction technique provides a similar $Omega(sqrtd)$ lower bound for the sample complexity of SGD to reach a non-trivial empirical error.
  arXiv  Detail & Related papers  (2024-01-22T15:50:32Z)
• Fermionic partial tomography via classical shadows [0.0]
  We propose a tomographic protocol for estimating any $ k $-body reduced density matrix ($ k $-RDM) of an $ n $-mode fermionic state. Our approach extends the framework of classical shadows, a randomized approach to learning a collection of quantum-state properties, to the fermionic setting.
  arXiv  Detail & Related papers  (2020-10-30T06:28:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.