← All setups

Muon and Scheduled Momentum Comparisons

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Differentiable f:Rm×n→R satisfies ∥∇f(X)−∇f(Y)∥∗≤L∥X−Y∥op and f(X0)−fmin≤Δ, where f≥fmin. Here r≥2, L,ε>0, s,Δ≥0, and LΔ≥72ε2. Jointly measurable, integrable unbiased gradients use IID samples; in a fixed orthonormal row basis, E∥N⊤bi∥22≤σi2 and ∑iσi≤s. The setup requires constant-step, momentum-free batched polar updates and uniform-random output, targeting E∥∇f(X^)∥∗≤ε, together with the comparator lower bounds below.

Scheduled momentum comparison under ScheduledMomentumComparison.
Result Oracle complexity Novelty Limitations
(1) MuonWidthSeparation (Ours) (⋆⋆) (review) O(LΔ/ε2+LΔs2/ε4) gradient calls. Comparator lower bounds, any deterministic schedule, batch size and fixed 0≤β<1, uniform-random output: NSGD≥c(1−β)(r−1)LΔs/ε3; NNSGD≥c(r−1)min{(1−β)LΔsε3ℓ,(1−β)2s2ε2}.
(2) Muon (Tao et al. 2026), Thm. 4 O(1+LΔ/ε2+LΔs2/ε4). One-sided covariance model: E[NN⊤]⪯Σ2, s=∥Σ∥∗. (1): Matches known rate; formalization and row-profile noise extension. Adds method-specific scheduled-momentum lower bounds, not improved problem-class complexity. (1) requires r≥2, LΔ≥72ε2 and IID sampling.
(3) (LongTails, n.d.-a, n.d.-b) O(1+LΔ/ε2+LΔs2/ε4). Constant-step, momentum-free SGD lower bound: N≥c(r−1)LΔs2/ε4 for LΔ≥128ε2. (1): Comparator scope extends to arbitrary deterministic schedules and fixed momentum; batch coefficient improves fourfold. SGD separation needs (1−β)(r−1)≳s/ε+ε/s, s>0. (1): At β=0, SGD certificate is weaker by order s/ε for s≫ε. At β=1−1/r, it loses width growth.
(4) SGD (Tao et al. 2026), Thm. 3; diagonal restriction Lower bound only: N≥c(rLΔ/ε2+r∥σ∥22LΔ/ε4). Constant step, no momentum, B=1; expected minimum gradient norm. (1): Extends comparator coverage to deterministic schedules, fixed momentum and batching, including normalized SGD. Lower-bound extension, not an upper-complexity improvement over (4). (1) certifies only uniform-random output; its lower bounds lack a deterministic term and vanish at s=0.

Abbr: r=min(m,n); ∥⋅∥∗,∥⋅∥op: nuclear and spectral norms; N: total individual gradient calls, including all batches; N=B(T+1) in (1). N in the noise model denotes gradient error. β: EMA momentum; NSGD: Frobenius-normalized SGD; ℓ=1+log⁡(1+sr/ε); c>0: universal constant. σ: coordinate noise profile in (4). Expectations include oracle and output randomness.

LongTails: MuonNoiseSeparation. n.d.-a. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/MuonNoiseSeparation.lean.
LongTails: SeparationLower. n.d.-b. Repository SGD lower-bound statement. https://github.com/k3nfalt/longtails/blob/main/LongTails/Proofs/SeparationLower.lean.
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