← All setups

Muon Adam Sgd Separation — Spectral-Smooth Muon and Adam Comparison

Descriptions may be stale. Consult the linked Lean sources.

Spectral-Smooth Muon and Adam Comparison · Lean proof

Spectral-Smooth Muon and Adam Comparison

We consider nonconvex minimization of a differentiable function f:Rr×r→R, where r≥4, with the Frobenius inner product. The gradient is L-Lipschitz from the spectral norm to the nuclear norm, where L>0, and a given point x0 has gap at most Δ≥0 above a global lower bound. For ε>0 with 128ε2≤LΔ, the oracle returns unbiased stochastic gradients from independent, identically distributed samples, with rowwise standard deviations summing to at most ε in a fixed orthonormal basis. The task requires batched, momentum-free Muon to return x¯ with E∥∇f(x¯)∥∗≤ε, where ∥⋅∥∗ is the nuclear norm and expectation includes sampling and algorithm randomness, together with worst-case call constraints for Adam and stochastic gradient descent.

The optimization problem is infx∈Rr×rf(x). Write E=Rr×r, with inner product ⟨x,y⟩=tr(x⊤y) and Frobenius norm ∥⋅∥F. The spectral norm ∥⋅∥op is the induced operator norm on maps from Rr to Rr, and ∥⋅∥∗ is its dual under this inner product. Gradients are taken with respect to the Frobenius inner product. The algorithm receives r,L,Δ,ε, and x0; the oracle model and its rowwise noise profile are not inputs.

Our assumptions:

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

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

Assumption 3 (Stochastic gradients and rowwise moments). There are a measurable sample space Ω, a probability measure ν on Ω, and a jointly measurable map g:E×Ω→E. For every x∈E, the random matrix g(x,ξ) is Bochner integrable for ξ∼ν, and Eξ∼ν[g(x,ξ)]=∇f(x). There exist a fixed orthonormal basis (bi)i=1r of Rr and numbers σi≥0 such that ∑i=1rσi≤ε. For every x∈E and i∈{1,…,r}, the vector (g(x,ξ)−∇f(x))⊤bi belongs to L2(ν;Rr) and satisfies Eξ∼ν[∥(g(x,ξ)−∇f(x))⊤bi∥22]≤σi2. At call k≥0, a query x∈E receives g(x,ξk). The measurable sample variables (ξk)k≥0 are mutually independent with common law ν, and the algorithm’s randomness is independent of the entire sample sequence.

Our result is algorithm-specific: we analyze batched Muon without momentum. Define the polar direction by polar(G)=argminU∈S(G)∥U∥F,S(G)=argmax∥V∥op≤1⟨G,V⟩. Thus the minimum-Frobenius-norm maximizer specifies the direction also when G is singular. The method chooses a constant step size η>0, a batch size B∈N with B≥1, and a horizon T∈N0 from its inputs. Starting at the given x0, it uses Gt=1B∑j=0B−1g(xt,ξBt+j),xt+1=xt−ηpolar(Gt),0≤t≤T. Each of the B queries in batch t is made at xt. A measurable index J, drawn using the algorithm’s randomness, is uniform on {0,…,T}, and the output is x¯=xJ. The prescribed run uses N=B(T+1) oracle calls, including the batch at xT. After these calls, the output remains xJ even if further replies are supplied. These query and output rules hold for every realization of the algorithm’s randomness and every possible reply sequence.

Let P denote the joint law of the algorithm’s randomness and the independent oracle sample sequence. The output must be measurable, ∥∇f(x¯)∥∗ must be integrable under P, and the required accuracy is EP[∥∇f(x¯)∥∗]≤ε.

The task additionally requires two worst-case comparison statements at the same fixed inputs. The competing methods use the same batching, starting point, uniform output rule, and requirement that the output remain unchanged after N=B(T+1) calls. Their recurrences and query rules likewise apply to every possible reply sequence.

For Adam, consider every constant tuning satisfying η>0,0≤β1<1,0≤β2<1,β12≤β2,τ≥0, and every B≥1 and T≥0. With Gt the batch average at its own iterate xt, the analyzed bias-corrected variant initializes m0=v0=0 and uses mt+1=β1mt+(1−β1)Gt,vt+1=β2vt+(1−β2)Gt⊙2,m^t+1=mt+11−β1t+1,v^t+1=vt+11−β2t+1,xt+1=xt−ηm^t+1v^t+1+τ,0≤t≤T. Squares, square roots, and the final quotient are entrywise, and τ is added to every denominator entry. Division by zero is defined to return zero, so the rule includes τ=0.

For every such tuning, batch size, horizon, and algorithm following these Adam rules, there must exist an objective and oracle satisfying the assumptions above for which measurable, integrable output meeting the stated accuracy criterion after N calls implies r−1≤64N2or(r−1)LΔ≤4096ε2N3. The objective and oracle may depend on the competing algorithm and its tuning.

For batched stochastic gradient descent, consider every constant η>0, every B≥1 and T≥0, and every algorithm following xt+1=xt−ηGt,0≤t≤T, with the same uniform output rule. For each such algorithm there must exist an objective and oracle satisfying the assumptions above for which measurable, integrable output meeting the stated accuracy criterion after N calls implies (r−1)LΔ≤1728ε2N. These two comparison requirements are part of the task, in addition to the expected stationarity requirement for the Muon output.

Proved result

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

OracleTemplate.Convergence LongTails.Setups.SpectralSmoothAdamComparison.spec
  LongTails.Theorems.MuonAdamSgdSeparation.budget

Relevant previous results

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