← All setups

Muon with Spectral Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Muon with Spectral Smoothness

We consider a differentiable, possibly nonconvex objective f:E→R on the Frobenius space E=Rm×n, where m,n are nonnegative integers. The gradient is Lipschitz from the spectral norm to the nuclear norm, and a given point x0∈E has a bounded gap to a global lower bound. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with bounded rowwise second moments in a fixed orthonormal basis. For ε>0, Muon must return a random iterate x¯ satisfying E∥∇f(x¯)∥∗≤ε, where ∥⋅∥∗ is the nuclear norm and the expectation includes sampling and algorithm randomness. Success additionally requires worst-case implications for two alternative momentum directions.

The optimization problem is infx∈Ef(x). Equip E with the Frobenius inner product ⟨X,Y⟩F=tr(XTY) and norm ∥⋅∥F. Write ∥X∥op for the induced operator norm of X:Rn→Rm and ∥X∥∗ for its dual nuclear norm. Gradients are taken with respect to the Frobenius inner product. The algorithm receives m,n,L,Δ,s,ε,β,x0, with L>0,Δ,s≥0,ε>0,0≤β<1.

Our assumptions:

Assumption 1 (Spectral smoothness and initial gap). The function f is Fréchet differentiable everywhere, and ∥∇f(x)−∇f(y)∥∗≤L∥x−y∥op,x,y∈E. There exists flb∈R such that flb≤f(x)for every x∈E,f(x0)−flb≤Δ.

Assumption 2 (Independent stochastic gradients). There are a probability law ν on a measurable space Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable and Eξ∼ν[g(x,ξ)]=∇f(x). There exist a fixed orthonormal basis (bi)i=1m of Rm and numbers σi≥0 with ∑i=1mσi≤s such that, for every x∈E and i, the random vector (g(x,ξ)−∇f(x))Tbi belongs to L2(ν;Rn) and Eξ∼ν[∥(g(x,ξ)−∇f(x))Tbi∥22]≤σi2. At call k, the oracle returns g(x,ξk) at the queried point x∈E. The measurable samples (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness.

Our result is algorithm-specific: we analyze Muon with a constant step size and batched momentum. Define its polar direction by S(M)=argmax∥U∥op≤1⟨M,U⟩F,polar(M)=argminU∈S(M)∥U∥F. The minimum-norm selection specifies the direction also for rank-deficient matrices, including polar(0)=0. The algorithm chooses η>0, an integer B≥1, and an integer T≥0 from its inputs. Starting from the given x0 and M0=0, it uses Gt=1B∑j=0B−1g(xt,ξBt+j),Mt+1=βMt+(1−β)Gt,xt+1=xt−ηpolar(Mt+1),0≤t≤T. All B queries in batch t are made at xt. A measurable index J, drawn from the algorithm’s randomness independently of the samples, is uniform on {0,…,T}. After N=B(T+1) calls, the output is x¯=xJ; it remains this same output after any additional calls. These query and output rules must hold for every realization of the algorithm’s randomness and every possible reply sequence.

The output must be measurable, its gradient nuclear norm must be integrable, and it must satisfy EP[∥∇f(x¯)∥∗]≤ε, where P is the joint law of the algorithm’s randomness and the independent oracle samples.

The task also includes two worst-case requirements, which are part of success rather than additional assumptions on f. Set r=min{m,n} and define did(M)=M,dF(M)={M/∥M∥F,M≠0,0,M=0. For each d∈{did,dF}, whenever r≥2,1024ε2≤LΔ, the following statement is required. For every η>0, integers B≥1 and T≥0, and every algorithm satisfying the same initialization, batching, uniform-index output, and output persistence rules with update xt+1=xt−ηd(Mt+1), there exist an objective and a stochastic oracle satisfying the assumptions above with the same inputs such that success after exactly N=B(T+1) calls implies n−r+1≤4N2or(r−1)LΔs2(1−β)3≤221ε4N. Here success in this implication means that the resulting output is measurable, its gradient nuclear norm is integrable, and its expected gradient nuclear norm is at most ε under its joint randomness law. The objective and oracle in each implication may depend on the alternative-direction algorithm and its tuning.

Results

Differentiable f:Rm×n→R satisfies ∥∇f(X)−∇f(Y)∥∗≤L∥X−Y∥op and f(X0)−fmin≤Δ, with f≥fmin, L,ε>0, Δ,s≥0, and fixed 0≤β<1. IID samples give jointly measurable, integrable unbiased gradients G(X) with E∥(G(X)−∇f(X))⊤bi∥2≤σi2 in a fixed orthonormal row basis, σi≥0, ∑iσi≤s. The setup requires batched exact-polar EMA updates and a uniform iterate Xτ; the target is E∥∇f(Xτ)∥∗≤ε.

Comparison for MomentumSpectralSmooth.
Result Oracle complexity Novelty Limitations
(1) MuonMomentumSeparation (Ours) (⋆⋆) (review) O((1+LΔ/ε2)(s2ε2+11−β)) calls. Also, fixed-β SGD-M and Frobenius-normalized NSGD-M require N=Ω(min{n−r+1,(r−1)(1−β)3LΔs2ε4}) when r≥2, LΔ≥1024ε2.
(2) Batched Muon, derived bound from (Tao et al. 2026), Theorem 4 O((1+LΔ/ε2)(1+s2/ε2)) calls; row-profile specialization of the descent analysis, without momentum. (1): Matches known rate at β=0. Adds a fixed-β NSGD-M separation when noise dominates, (r−1)(1−β)3>233 and n−r+1≳(213LΔs2/ε4)2; no upper-rate improvement. (1): Deterministic term increases by 1/(1−β). Separation needs extreme width; vanishes as β→1, and gives no useful tall-matrix separation.

Abbr: r=min(m,n); ∥⋅∥∗ and ∥⋅∥op are nuclear and spectral norms. N=B(T+1) counts individual stochastic-gradient calls, including all batches. EMA denotes exponential moving average; SGD-M uses the EMA directly, NSGD-M normalizes it in Frobenius norm. Lower bounds quantify over constant positive steps and batches at the same β; Ω denotes a necessary worst-case cost. Expectations include IID oracle samples and the independent uniform output index.

Tao, Hongyi, Dingzhi Yu, and Lijun Zhang. 2026. When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-Norm Lower Bounds. https://doi.org/10.48550/arXiv.2605.06615.

Lean setup