← All setups

Muon Width Separation — Muon and Scheduled Momentum Comparisons

Descriptions may be stale. Consult the linked Lean sources.

Muon and Scheduled Momentum Comparisons · Lean proof

Muon and Scheduled Momentum Comparisons

We consider nonconvex minimization of a differentiable function f:Rm×n→R, where m,n are positive integers. The gradient is Lipschitz from the spectral norm to the nuclear norm with constant L>0, and a given starting point x0 has gap at most Δ≥0 above a global lower bound. The oracle returns unbiased stochastic gradients with independent, identically distributed samples and rowwise second moments controlled by s≥0. For ε>0, batched Muon must return x¯ with E∥∇f(x¯)∥∗≤ε, where ∥⋅∥∗ is the nuclear norm and expectation includes sampling and algorithm randomness. The task also requires worst-case oracle-call comparisons for scheduled SGD and normalized SGD with momentum.

The optimization problem is infx∈Rm×nf(x). Equip the matrix space with the Frobenius inner product ⟨X,Y⟩F=tr(XTY) and norm ∥⋅∥F; gradients are taken with respect to this inner product. Write ∥⋅∥op for the induced Euclidean operator norm and ∥⋅∥∗ for its dual nuclear norm. Set r=min{m,n}. The parameters satisfy r≥2,L>0,Δ,s≥0,ε>0,72ε2≤LΔ. The algorithm receives m,n,L,Δ,s,ε, and x0; the objective and the stochastic oracle model are accessed only through oracle replies.

Our assumptions:

Assumption 1 (Spectral smoothness and initial gap). The function f is differentiable everywhere, and ∥∇f(x)−∇f(y)∥∗≤L∥x−y∥op,x,y∈Rm×n. There exists flow∈R such that f(x)≥flowfor every x,f(x0)−flow≤Δ.

Assumption 2 (Unbiased oracle with a rowwise variance profile). Let ν be a probability measure on a measurable sample space Ω. The oracle is a jointly measurable map g:Rm×n×Ω→Rm×n. For each x, g(x,⋅) is Bochner integrable and Eξ∼ν[g(x,ξ)]=∇f(x). There exist an orthonormal basis (bi)i=1m of Rm and numbers σi≥0 with ∑i=1mσi≤s such that, for every x and i, the vector (g(x,ξ)−∇f(x))Tbi belongs to L2(ν;Rn) and Eξ∼ν[∥(g(x,ξ)−∇f(x))Tbi∥22]≤σi2. At call k, a query x receives g(x,ξk), where the measurable random variables (ξk)k≥0 are independent with common law ν. Algorithm randomness is independent of this sample sequence. Queries may be made anywhere in the matrix space.

Our formulation is algorithm-specific: we analyze batched Muon with a constant step size and no momentum. Define polar(G) to be the minimum-Frobenius-norm element of argmax∥U∥op≤1⁡⟨G,U⟩F. The algorithm chooses η>0, an integer batch size B≥1, and an integer T≥0 from its inputs. Starting at the given x0, it queries B times at each xt and follows Gt=1B∑j=0B−1g(xt,ξBt+j),xt+1=xt−ηpolar(Gt),0≤t≤T. After N=B(T+1) calls, it returns x¯=xJ, where J is a measurable function of algorithm randomness, uniform on {0,…,T}. The same output is retained after any additional calls. Thus the batch at xT is counted even though xT+1 is not an output candidate. These query and output rules must hold for every realization of algorithm randomness and every possible reply sequence.

For any objective and oracle satisfying the assumptions, the required stationarity criterion is EP[∥∇f(x¯)∥∗]≤ε, with x¯ measurable and ∥∇f(x¯)∥∗ integrable under P, the joint law of algorithm randomness and oracle samples.

The task additionally includes two worst-case comparisons at the same parameter values. The comparison methods are SGD with momentum and Frobenius-normalized SGD with momentum, with directions dSGD(M)=M,dNSGD(M)={M/∥M∥F,M≠0,0,M=0. For either direction d, fix any β∈[0,1), any real-valued schedule (ηt)t≥0, and integers B≥1 and T≥0. The comparison recurrence, initialized at (y0,M0)=(x0,0), is Ht=1B∑j=0B−1g(yt,ξBt+j),Mt+1=βMt+(1−β)Ht,yt+1=yt−ηtd(Mt+1),0≤t≤T. Every batch consists of B queries at yt. After N=B(T+1) calls the output is y¯=yJ, with J uniform on {0,…,T} and drawn measurably from algorithm randomness independently of the oracle samples; this output is retained after additional calls. The recurrence, queries, and output rule are required for every possible reply sequence and every realization of algorithm randomness.

For every such SGD algorithm, the required comparison asserts the existence of an objective and oracle satisfying the assumptions for which measurable, integrable expected stationarity of y¯ at tolerance ε implies (1−β)(r−1)LΔs≤81ε3N. For every such normalized SGD algorithm, a possibly different objective and oracle satisfying the assumptions must exist for which the same stationarity criterion implies at least one of (1−β)(r−1)LΔs≤288ε3(2+log⁡(1+srε))N,(1−β)2(r−1)s2≤24ε2N. These existential comparisons are part of the required task, together with the expected stationarity requirement for batched Muon.

Proved result

(⌈16⋅s2ε2⌉++1)⋅(⌈8⋅L⋅Δε2⌉++1)

OracleTemplate.Convergence LongTails.Setups.ScheduledMomentumComparison.spec
  LongTails.Theorems.MuonWidthSeparation.budget

Relevant previous results

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