← All setups

Muon Momentum Separation — Muon with Spectral Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Muon with Spectral Smoothness · Lean proof

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.

Proved result

(⌈128⋅(1−β)⋅s2ε2⌉++1)⋅(⌈32⋅L⋅Δε2+161−β⌉++1)

OracleTemplate.Convergence LongTails.Setups.MomentumSpectralSmooth.spec LongTails.Theorems.MuonMomentumSeparation.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.