PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Maria-Eleni Sfyraki, Jun-Kun Wang

arXiv:2506.04192v4math.OCstat.ML

TL;DR

Stochastic Frank-Wolfe has limited analysis for heavy-tailed noise, while its practical effectiveness as a neural-network optimizer remains unclear. This paper unifies Lion and Muon with Stochastic Frank-Wolfe and develops clipped variants for heavy-tailed settings. It establishes Frank-Wolfe-gap guarantees, including an O(1/ϵ^3) expected-gap result under bounded variance without a gigantic average batch size.

  • Problem

    Little is known about Stochastic Frank-Wolfe with a linear optimization oracle under bounded p-th-moment noise, an assumption that can capture heavy-tailed gradients beyond bounded variance.

    Source: §1 · p. 2

  • Method

    The paper analyzes Stochastic Frank-Wolfe as a general method, connects Lion and weight-decayed Muon to norm-constrained instances, and develops clipping-based variants for heavy-tailed noise.

    Source: §1 · p. 2, §4.2 · p. 8

  • Results

    O(1/ϵ^3) stochastic gradient evaluations suffice for an expected ϵ Frank-Wolfe gap under bounded variance, without a gigantic average batch size across iterations.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework extends convergence guarantees to general convex constraint sets and yields Lion and Muon variants with guarantees under heavy-tailed noise.

    Source: §4.2 · p. 8, §6 · p. 10

    Whether the heavy-tailed high-probability bounds can adapt to the noise level σ, including improved rates in the noiseless setting, remains open.

    Source: §6 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The paper connects Lion and Muon to Stochastic Frank-Wolfe, and extends Stochastic Frank-Wolfe analysis to heavy-tailed noise. It gives convergence guarantees for these methods and derives heavy-tailed variants of Lion and Muon.

1 Introduction

  • Lion is exactly Stochastic Frank-Wolfe under an ℓ∞-norm constraint, while Muon with weight decay is Stochastic Frank-Wolfe under a spectral-norm constraint.For both, convergence in Frank-Wolfe gap implies convergence to a KKT point of the corresponding norm-constrained problem.Source: §1 · pp. 1–2
  • For bounded p-th-moment noise with p ∈ (1, 2], the paper proposes two Stochastic Frank-Wolfe variants: one with gradient clipping and another with clipping plus variance reduction.The p < 2 setting captures heavy-tailed noise, which may have unbounded variance.Source: §1 · p. 2
  • The clipping-plus-variance-reduction method has an improved high-probability Frank-Wolfe-gap rate, with the guarantee requiring Lipschitz stochastic gradients.The supplied passage does not specify the rate expression.Source: §1 · p. 2
  • The heavy-tailed Stochastic Frank-Wolfe results yield new Lion and Muon variants with guarantees under heavy-tailed noise.The paper frames this extension for stochastic optimization with a linear optimization oracle, where little was known under bounded p-th-moment noise.Source: §1 · p. 2
  • With bounded variance, the proposed method needs O(1/ϵ^3) stochastic gradient evaluations for an expected ϵ Frank-Wolfe gap, without a gigantic average batch size across iterations.The guarantee relies on smoothness and the averaged Lipschitz gradient assumption.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the constrained stochastic optimization setting, assumptions, and Frank-Wolfe gap used in the analysis. They also review Lion and Muon and their update rules.

2.1 Notations and assumptions

  • The Frank-Wolfe gap is zero exactly at stationary points and, for convex objectives, upper-bounds the optimality gap.The paper studies minimizing an expected stochastic objective over a convex, compact set in a Hilbert space.Source: §2.1 · pp. 2–3
  • The feasible set C is convex and compact with diameter D, and the stated assumptions use Hilbert-space norms.The objective is assumed bounded below; results invoke only the assumptions they explicitly require.Source: §2.1 · p. 3
  • The noise assumption requires an unbiased stochastic gradient with bounded p-th moment noise for some p ∈ (1, 2]; p = 2 gives bounded variance.The setup also lists smoothness, gradient-Lipschitz, and bounded-gradient-norm assumptions.Source: §2.1 · p. 3

2.2 Lion and Muon

  • Lion updates use the sign of a momentum-gradient combination with weight decay, while Muon updates use a momentum matrix projected to a semi-orthogonal matrix with weight decay.The Lion overview relates it to ℓ∞-norm constrained optimization; the Muon overview describes it as a preconditioned-gradient method.Source: §2.2 · pp. 3–4

3 Lion and Muon as a Stochastic FW

The section interprets Lion and Muon with weight decay as stochastic Frank-Wolfe methods under different norm constraints. It relates Frank-Wolfe-gap convergence on norm-ball constraints to obtaining a KKT point.

3 Lion and Muon as a Stochastic FW

  • Frank-Wolfe updates use a linear minimization oracle followed by convex averaging, which can be less expensive than projection for some constraint sets.For norm constraints, the oracle direction is a scaled steepest-descent direction.Source: §3 · p. 4
  • Lion is a stochastic Frank-Wolfe instance under an ℓ∞-norm ball, while Muon with weight decay is an instance under a spectral-norm ball.Muon with an additional Nesterov momentum step also falls within the stochastic Frank-Wolfe framework.Source: §3 · pp. 4–5
  • O(1/ϵ^4) stochastic first-order oracle calls suffice for an expected ϵ-gap in the stated corollary, with batch size growing with T.The rate matches the cited existing Stochastic Frank-Wolfe rates.Source: §3 · p. 6
  • Algorithm 5 attains the same stochastic first-order oracle complexity up to a logarithmic factor with batch size one, while Algorithm 6 improves complexity and also uses batch size one.These variants address the large-batch requirement of the corollary.Source: §3 · p. 6
  • On a norm-ball constraint, convergence to a Frank-Wolfe gap is equivalent to obtaining a KKT point.The section gives the ℓ∞ norm for Lion and the matrix spectral norm for Muon.Source: §3 · p. 6
  • The paper’s unified convergence result applies to both Lion and Muon, and its Frank-Wolfe-gap measure connects their convergence to KKT points.The authors contrast this shared result with earlier guarantees for each optimizer separately.Source: §3 · pp. 6–7

4 A deeper investigation of Stochastic FW methods under the bounded moment noise

This section develops Stochastic Frank-Wolfe methods for bounded-moment noise, covering both the bounded-variance regime and heavy-tailed noise. Its guarantees include variance reduction for the light-tailed case and clipping-based methods for heavy-tailed noise, including variants of Lion and Muon.

4.1 Light-tailed regime

  • Algorithm 4 integrates STORM variance reduction into Algorithm 3; the resulting result avoids large batches throughout the iterations.The result requires a large batch only at initialization and does not require Hessian assumptions or additional data-distribution structure compared with Zhang et al. [2020b].Source: §4.1 · p. 7
  • Corollary 2 gives an expected ϵ-gap in T = O(1/ϵ^3) iterations, with an initialization batch of T^1/3 and batch size one thereafter.The amortized average batch size is at most 2, and the paper says the complexity matches the best-known bounds.Source: §4.1 · p. 7

4.2 Heavy-tailed regime

  • For p ∈ (1, 2], the section develops Stochastic Frank-Wolfe guarantees under bounded p-th-moment noise, addressing a setting where bounded variance may be inappropriate.The cited prior Frank-Wolfe work uses different noise assumptions, assumes convexity, and requires a large batch, unlike the proposed batch-size-one methods.Source: §4.2 · p. 8
  • Algorithm 5 integrates clipping into Stochastic Frank-Wolfe and yields LION+ and MUON+ by replacing their stochastic-gradient steps with clipped gradients.The paper names these clipped variants LION+ and MUON+.Source: §4.2 · p. 8
  • Theorem 5’s Frank-Wolfe-gap guarantee holds with stochastic-gradient batch size one at every iteration.The result parallels clipping-based SGD results for obtaining an expected gradient norm.Source: §4.2 · p. 8
  • Algorithm 6 combines clipping with variance reduction, and its improved-complexity guarantee over Theorem 5 also holds with batch size one.The paper presents Theorem 6 as a counterpart to a heavy-tailed SGD result by Liu et al. [2023].Source: §4.2 · pp. 8–9
  • Theorem 6 improves on Theorem 5’s complexity under an additional structural assumption; both are among the first such results for non-convex Stochastic Frank-Wolfe under heavy-tailed noise.The paper identifies Theorem 6’s extra condition as Assumption 3-b.Source: §4.2 · p. 9

5 Experiments

The experiments compare LION+ and MUON+ with Lion and Muon on nanoGPT trained on Shakespeare. In this setting, the clipped variants reach the stated validation-loss threshold in fewer steps.

5 Experiments

  • The evaluation trained nanoGPT on Shakespeare, compared each proposed variant with its corresponding original optimizer, and averaged results over five seeds.Muon and MUON+ used Newton-Schulz orthogonalization; AdamW optimized one-dimensional parameters with fixed hyperparameters.Source: §5 · p. 9
  • LION+ reached validation loss below 1.47 in 2950 steps, approximately 19.18% fewer steps than Lion’s 3650.The reported training and validation loss curves are averages over five runs.Source: §5 · p. 9
  • MUON+ reached validation loss below 1.47 in 4000 steps, approximately 5.88% fewer steps than Muon’s 4250.The reported training and validation loss curves are averages over five runs.Source: §5 · p. 9

6 Discussion and Future Directions

The discussion consolidates Stochastic Frank-Wolfe guarantees across bounded-variance and heavy-tailed settings, relates the framework to Lion and Muon, and identifies open theoretical boundaries. The related-work survey situates these results among prior Lion, Muon, SignSGD, and variance-reduced Frank-Wolfe analyses.

6 Discussion and Future Directions

  • The framework covers non-convex Stochastic Frank-Wolfe with bounded variance, variance reduction, and clipping under heavier-tailed noise, extending its guarantees to convex constraint sets.For norm-ball constraints, Frank-Wolfe-gap convergence translates into convergence to a KKT point; the paper also reports improved convergence of enhanced variants over baseline ones.Source: §6 · pp. 9–10
  • Figure 1 tracks nanoGPT training and validation loss on Shakespeare, sampled every 10 and 50 steps, respectively, and averaged over three seeds.The discussion reports improved convergence of enhanced variants over baseline ones.Source: Figure 1 · p. 10, §6 · p. 10
  • Heavy-tail high-probability bounds do not adapt to the noise level σ, leaving their expected improvement in the noiseless setting unresolved.The analysis also leaves open extensions to Banach-space norms and does not cover Lion or Muon variants without weight decay.Source: §6 · p. 10

A More Related Works

  • Earlier Lion studies cover its ℓ∞-constrained formulation [Chen et al., 2024a], KKT convergence [Dong et al., 2024], and distributed optimization.The survey also describes work on Lion variants, subspace descent, and preconditioned methods.Source: A More Related Works · p. 18
  • Pethick et al. [2025] recover weight-decayed Muon as a constrained variant but omit momentum extrapolation, so their formulation does not recover Lion or Nesterov-momentum Muon.The paper positions its broader Stochastic Frank-Wolfe analysis as extending to these optimizer connections.Source: A More Related Works · p. 18
  • Prior SignSGD variance-reduction complexity results target an ε-small expected gradient norm.The survey discusses SignSVRG, SignRVR, SignRVM, and SSVR as examples.Source: A More Related Works · p. 19

B.1 Proof of Theorem 1

The proof establishes Lion as a Stochastic Frank-Wolfe instance by matching its update parameters and maintaining equivalence between the two algorithms’ iterates.

B.1 Proof of Theorem 1

  • Lion’s updates are equivalent to a Stochastic Frank-Wolfe instance under the theorem’s parameter choices.The proof uses induction to maintain equality between corresponding algorithm states and updates.Source: §B.1 · p. 20

B.2 Proof of Theorem 2

The appendix proves that Muon and its Nesterov-momentum variant are Stochastic Frank-Wolfe instances through parameter matching. It also outlines a proof strategy for the bounded-variance result using an objective-and-estimator-error potential.

B.2 Proof of Theorem 2

  • Muon is shown to be a Stochastic Frank-Wolfe instance under matched momentum, step-size, and constraint-set choices.The proof maintains equivalence of the two algorithms’ updates by induction.Source: §B.2 · p. 21

B.3 Muon with Nesterov-momentum

  • Muon with Nesterov momentum is likewise identified as a Stochastic Frank-Wolfe instance under a corresponding parameter mapping.The proof proceeds by induction and follows the structure of the Muon equivalence proof.Source: §B.3 · pp. 22–23

B.4 Proof of Theorem 3

  • The bounded-variance proof tracks objective value and gradient-estimator error together in a potential function to bound the Frank-Wolfe gap.Its inequalities use smoothness, the constraint-set diameter, and the linear oracle’s optimality.Source: §B.4 · pp. 23–24

C.1 Proof of Theorem 4

Theorem 4’s proof controls the gradient-estimator error in a variance-reduced analysis, while the appendix specifies the LION+ and MUON+ update rules and their required parameters.

C.1 Proof of Theorem 4

  • Theorem 4’s proof controls estimator error using gradient differences and a potential function, with parameter schedules specified for the algorithm.The proof uses the averaged Lipschitz-gradient assumption in its error bound.Source: §C.1 · pp. 26–27

C.2 LION+ and MUON+

  • LION+ and MUON+ are specified with clipping parameter M and weight decay λ, alongside momentum and step-size parameters.LION+ updates with sign(ct), while MUON+ uses an oracle projection of its momentum matrix before updating.Source: §C.2 · p. 29

C.3 Proof of Theorem 5

Theorem 5’s proof uses martingale and concentration arguments for Stochastic Frank-Wolfe under p-th-moment noise. The section also specifies clipped Lion++ and Muon++ updates as instances of the method.

C.3 Proof of Theorem 5

  • The proof builds on Normalized SGD with clipping and momentum machinery from Liu et al. [2023].It uses martingale-difference arguments and induction to establish the result.Source: §C.3 · pp. 30, 31, 33
  • The proof’s lemmas use the constraint-set diameter and martingale bounds to control terms in the convergence argument.The section defines D as the diameter of C and introduces lemmas for the proof’s estimates.Source: §C.3 · pp. 30–31
  • Theorem 5 supposes Assumptions 3-a, 4, and 5 hold, with p ∈ (1, 2]; the supplied excerpts do not expose the theorem’s bound itself.Source: §C.3 · p. 33

C.4 LION++ and MUON++

  • LION++ updates its clipped, momentum-based direction and applies sign-based steps with weight decay.Its update also includes a difference of gradients evaluated at consecutive iterates using the same sample.Source: §C.4 · p. 35

C.5 Proof of Theorem 6

Theorem 6’s proof uses martingale concentration, smoothness, and bounded constraint-set diameter. The section also gives the MUON++ update as a momentum and orthogonalization-based step with weight decay.

C.5 Proof of Theorem 6

  • MUON++ updates its momentum matrix, projects it by Frobenius-norm orthogonalization, then takes a weight-decayed step.The update includes a same-sample gradient difference between consecutive iterates.Source: §C.5 · p. 35
  • The proof controls martingale-difference terms using smoothness, the constraint-set diameter, and a concentration bound.It applies a martingale inequality to obtain a bound holding across the iterations with high probability.Source: §C.5 · pp. 35–36
  • Theorem 6 states a guarantee under Assumptions 3-a, 3-b, 4, and 5 for p∈(1, 2].The supplied theorem fragments do not expose the resulting bound.Source: §C.5 · p. 36

D Hyperparameter Settings for nanoGPT

The nanoGPT Shakespeare experiments tune learning rate and weight decay by grid search, with additional clipping-threshold tuning for LION+ and MUON+. The section reports the training configuration and five-seed loss curves.

D Hyperparameter Settings for nanoGPT

E.1 Synthetic Heavy-tailed Dataset

On synthetic objectives, LION++ and MUON++ show their clearest advantages under heavy-tailed noise with unbounded variance, especially in higher dimensions. On CIFAR-10, both variants improve test accuracy over their respective baselines, with LION++ showing a more pronounced final-epoch advantage.

E.1 Synthetic Heavy-tailed Dataset

  • The Lion comparison uses quadratic objectives at d=1 and d=1000, with Normal and Pareto noise and 10^5 runs of 100 iterations.The Pareto settings represent finite variance at p=2.5 and infinite variance at p=1.5; average gradient norm across iterations is the convergence criterion.Source: §E.1 · p. 40
  • The Muon comparison uses quadratic matrix objectives at n=2 and n=30 with the same three noise types and 10^5 runs of 100 iterations.The reported curves show median and δ and 1−δ quantiles, with δ=10^-4.Source: §E.1 · p. 40
  • Under unbounded-variance noise, Lion++ and Muon++ improve convergence and upper-quantile robustness; in higher dimensions, both tend toward lower average gradient norms, especially in that setting.With small dimensions and light-tailed noise, comparison algorithms perform similarly; under bounded-variance heavy-tailed noise, the ++ variants have a slight advantage.Source: §E.1 · p. 40

E.2 Multi-class Image Classification

  • The CIFAR-10 experiment trains ResNet18 and reports test loss and accuracy curves over 200 epochs.The setup and selected hyperparameters are described for the image-classification experiment.Source: §E.2 · p. 44
  • LION++ consistently lowers test loss versus Lion, while both ++ variants improve test accuracy over their baselines on CIFAR-10.LION++’s accuracy advantage is more consistent and pronounced during the final epochs; MUON++’s test-loss improvement is especially notable early in training.Source: Figure 9 · p. 44, §E.2 · p. 44
Loading 2506.04192v4…