← All setups

Muon with Finite-Variance Matrix Gradients

Descriptions may be stale. Consult the linked Lean sources.

Muon with Finite-Variance Matrix Gradients

We consider a differentiable, possibly nonconvex objective f:E→R on E=Rm×n with the Frobenius inner product, where m,n are nonnegative integers. Its gradient is L-Lipschitz from the spectral norm to the nuclear norm, with L≥0, and a given x0∈E has gap at most Δ≥0 above a global lower bound. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with row standard deviations summing to at most s≥0 in a fixed orthonormal basis. The specified Muon variant must return a measurable x¯ satisfying ∥∇f(x¯)∥∗≤ε with probability at least 1−δ, where ∥⋅∥∗ is the nuclear norm, ε>0, and δ∈(0,1).

The underlying optimization problem is infx∈Ef(x). Write ⟨X,Y⟩F=tr(X⊤Y) and ∥X∥F for the Frobenius inner product and norm. The spectral norm ∥X∥op is the induced operator norm of X:Rn→Rm with Euclidean norms, and ∥X∥∗ is its dual norm under this inner product. Gradients are taken with respect to the Frobenius inner product. The algorithm receives m,n,L,Δ,s,ε,δ, and x0; the noise law and the basis and row bounds described below are not inputs.

Our assumptions:

Assumption 1 (Spectral-to-nuclear smoothness). The function f is Fréchet differentiable everywhere, and ∥∇f(x)−∇f(y)∥∗≤L∥x−y∥op,x,y∈E.

Assumption 2 (Initial objective gap). There exists flow∈R such that flow≤f(x)for every x∈E,f(x0)−flow≤Δ.

Assumption 3 (Unbiased gradients with a row variance profile). There is a probability law ν on a measurable sample space Ω and a jointly measurable map g:E×Ω→E. For every x∈E, g(x,⋅) is Bochner integrable and Eξ∼ν[g(x,ξ)]=∇f(x). There exist an orthonormal basis (vi)i=1m of Rm and nonnegative numbers (σi)i=1m such that ∑i=1mσi≤s,Eξ∼ν[∥(g(x,ξ)−∇f(x))⊤vi∥22]≤σi2,x∈E,1≤i≤m. Each row-error map in this display belongs to L2(ν;Rn). At successive calls, the oracle uses measurable, mutually independent samples ξ0,ξ1,…, each with law ν, and returns g(x,ξℓ) at the queried point x. Algorithm randomness is independent of this sample sequence.

Our formulation is algorithm-specific: we analyze Muon with momentum, polar updates, and a sampled-candidate selection rule. Define the polar map by the minimum-Frobenius-norm maximizer polar(M)=operatorname∗argminU∈S(M)∥U∥F,S(M)=argmax∥V∥op≤1⟨M,V⟩F. The algorithm chooses parameters 0<α≤1,η>0,ρ>0,T,k,q∈Z≥0,b∈Z≥1. Starting from the given x0 and M0=0, it queries the training points xt for t=0,…,T, with replies Gt=g(xt,ξt). The candidate trajectory is defined by Mt+1=(1−α)Mt+αGt,xt+1=xt−ηpolar(Mt+1),0≤t<T. Thus there are T+1 training queries, including the query at xT.

Using its own randomness, the algorithm draws q+1 independent indices I0,…,Iq, uniformly distributed on {0,…,T}, and sets yi=xIi. At each yi, it collects k+1 batches of b further oracle replies. With zero-based indices, these batch means are aij=T+1+b(k+1)i+bj,Bij=1b∑u=0b−1g(yi,ξaij+u),0≤i≤q,0≤j≤k. For each candidate, define Ji={j∈{0,…,k}:2|{ℓ∈{0,…,k}:∥Bij−Biℓ∥∗≤ρ}|>k+1}. Let ji be the smallest element of Ji when it is nonempty, and let ji=0 otherwise. Set G^i=Biji. The output rule is i∗=minargmin0≤i≤q∥G^i∥∗,x¯=yi∗. This procedure uses T+1+b(k+1)(q+1) oracle calls. Its output remains the same after any additional calls. The family also includes a constant-output alternative: when 2LΔ≤ε2, the algorithm may return x0 at every stage.

Queries may be made at any point of E. The required output is measurable and satisfies PP(∥∇f(x¯)∥∗>ε)≤δ, where P is the joint law of the algorithm randomness and the independent oracle sample sequence.

Results

Differentiable f:Rm×n→R satisfies f≥fmin, f(X0)−fmin≤Δ, and ∥∇f(X)−∇f(Y)∥∗≤L∥X−Y∥op. The jointly measurable, integrable oracle uses IID samples, with EG(X)=∇f(X) and, in a fixed orthonormal row basis (ui), E∥(G(X)−∇f(X))⊤ui∥22≤σi2, σi≥0, ∑iσi≤s. Here L,Δ,s≥0, ε>0, 0<δ<1. Target: Pr(∥∇f(X^)∥∗>ε)≤δ, over sampling and algorithm randomness. The setup restricts algorithms to exact-polar EMA Muon with random candidate selection and batched robust validation (or returning X0 when already certified).

Finite-variance spectral-smooth optimization: FiniteVarianceSpectralSmooth.
Result Oracle complexity Novelty Limitations
(1) FiniteVarianceMuonHighProbability (Ours) (⋆⋆) (review) O(A[R+RJ2]) stochastic-gradient calls, including validation.
(2) Minibatch spectral-normalized SGD, derived bound from (Hübler et al. 2025, Thm. 4), with validation O(A[Rℓ+ℓ(ℓ+log⁡ℓ)]) calls on the shared row-profile setup; batch size O(A). (1): high-probability persistent momentum with one-sample training. Up to an ℓ-factor cost saving, only when Rℓ≳J2; no uniform speedup. (1): validation remains batched. Worse for fixed δ when R≪[1+log⁡(AR)]2, or for ℓ≫R (up to R factor).
(3) Muon (Hübler et al. 2026, Thm. 3.5), expected guarantee O(R+dLΔs2ε4+d3/2s3ε3) calls at p=2, σ=s; expected average nuclear gradient norm ≤ε. (1): high-probability guarantee for persistent Muon. Dimension-free bound on the row-profile class; rates are not directly comparable across probability and expectation. (1) needs the stronger row profile and p=2; (3) permits nuclear central p-moments, 1<p≤2. The dimension difference reflects this stronger noise assumption.
(4) Clipped normalized momentum (Cutkosky and Mehta 2021, Thm. 2); special case: m=1 OL,Δ,G(1+ε−4[1+log⁡1+ε−1δ]4) calls at p=2; high-probability average gradient norm ≤ε. Fixed tuning; parameter dependence not extracted. (1): extends to matrix nuclear stationarity; on the Euclidean overlap, central variance replaces bounded noncentral moments, allowing unbounded gradients and unclipped momentum. Rates not comparable as stated. (1) covers only p=2; (4) allows 1<p≤2 under E∥G(X)∥∗p≤Gp and a 2-smooth dual norm.

Abbr: ∥⋅∥∗: nuclear norm; ∥⋅∥op: spectral norm; ∥⋅∥2: Euclidean norm; d=min(m,n); A=1+s2/ε2; R=1+LΔ/ε2; ℓ=1+log⁡(1/δ); J=1+log⁡(AR/δ); p: noise moment order; σ: nuclear central-moment scale; G: noncentral-moment scale. OL,Δ,G holds with these parameters and tuning fixed. EMA: exponential moving average; IID: independent, identically distributed.

Cutkosky, Ashok, and Harsh Mehta. 2021. High-Probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails. https://doi.org/10.48550/arXiv.2106.14343.
Hübler, Florian, Ilyas Fatkhullin, and Niao He. 2025. “From Gradient Clipping to Normalization for Heavy Tailed SGD.” Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, Proceedings of machine learning research, vol. 258: 2413–21. https://doi.org/10.48550/arXiv.2410.13849.
Hübler, Florian, Thomas Pethick, and Suvrit Sra. 2026. Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success. https://doi.org/10.48550/arXiv.2606.14560.

Lean setup