← All setups

Spectral-Smooth Muon and Adam Comparison

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Differentiable f:Rr×r→R, r≥4, L,ε>0, LΔ≥128ε2; f≥fmin and f(X0)−fmin≤Δ; ∥∇f(X)−∇f(Y)∥∗≤L∥X−Y∥op. IID samples of a jointly measurable, integrable oracle G satisfy ∫G(X,ω)dp(ω)=∇f(X) and, for a fixed orthonormal basis (bi), ∫∥(G(X,ω)−∇f(X))⊤bi∥22dp(ω)≤σi2, with σi≥0 and ∑iσi≤ε. The setup requires constant-step batched exact-polar Muon with a uniform-iterate output X^; the target is ∫∥∇f(X^)∥∗dP≤ε, where P combines IID oracle samples and independent output randomization. Success also includes worst-case Adam and SGD lower bounds.

Comparison for SpectralSmoothAdamComparison.
Result Oracle complexity Novelty Limitations
(1) MuonAdamSgdSeparation (Ours) (⋆⋆) (review)

Muon: O(LΔ/ε2) calls.

Adam: Ω(min{r,(rLΔ/ε2)1/3}).

SGD: Ω(rLΔ/ε2).

Lower bounds: every constant tuning and batch size; uniform-iterate output. Adam is bias-corrected, η>0, τ≥0, 0≤β1,β2<1, β12≤β2.

(2) Muon (Tao et al. 2026), Thm. 4

O(1+LΔ/ε2+LΔs2/ε4).

One-sided covariance: E[ZZ⊤∣F]⪯Σ2, s=∥Σ∥∗. At s=ε: O(LΔ/ε2).

(1): Adds an Adam lower bound. Matches known Muon rate at s=ε; row-profile relaxation already appears in (3). (1) fixes s=ε, square matrices, r≥4, LΔ≥128ε2; requires IID samples and gradient-Lipschitz smoothness.
(3) Repository Muon guarantee and SGD lower bound (LongTails, n.d.-a, n.d.-b)

Muon: O((1+s2/ε2)(1+LΔ/ε2)).

At s=ε, square matrices and LΔ≥128ε2: Muon O(LΔ/ε2); SGD Ω(rLΔ/ε2).

(1): Adds the full two-moment Adam lower bound; reuses the Muon guarantee and SGD separation on the common setup. (1) specializes the Muon guarantee to square matrices, r≥4, s=ε, LΔ≥128ε2.
(4) One-step SignGD comparison (Wang et al. 2025), Thm. 5.3 One-step learning-imbalance result, not a stationarity complexity bound. Restricted to β1=β2=0, zero initialization, orthonormal embeddings and two imbalanced class groups in an associative-memory model; rates not comparable. (1): Multistep, batch-uniform Adam lower bound yields asymptotic separation when r/Q2→∞: Muon O(Q) versus Adam Ω(min{r,(rQ)1/3}). Explicit constants require r≳9.5⋅1015 at Q=128.
(5) Adam nonconvergence (Reddi et al. 2018), Thm. 3 Nonconvergence on a one-dimensional constrained stochastic convex instance, β1<β2, steps α/t; no nuclear-stationarity complexity bound. Rates not comparable. (1): Quantitative finite-budget lower bound for constant-parameter Adam on unconstrained matrix problems, uniform over batches and damping. Method-specific separation; no improved problem-class upper bound. (1) does not cover decreasing steps; its Adam bound is limited to uniform-iterate output, excluding last or averaged outputs and AdamW.

Abbr: Q=LΔ/ε2; s is the noise scale (equal to ε in (1)); Z=G−∇f; F is the sampling history; Σ⪰0 is a fixed covariance envelope. ∥⋅∥∗ and ∥⋅∥op are nuclear and spectral norms. Costs count individual gradient samples, including all batches; N=B(T+1) in (1). η is the step size, β1,β2 are Adam moment parameters, and τ is denominator damping.

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.
Reddi, Sashank J., Satyen Kale, and Sanjiv Kumar. 2018. “On the Convergence of Adam and Beyond.” International Conference on Learning Representations. https://doi.org/10.48550/arXiv.1904.09237.
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.
Wang, Shuche, Fengzhuo Zhang, Jiaxiang Li, et al. 2025. Muon Outperforms Adam in Tail-End Associative Memory Learning. https://doi.org/10.48550/arXiv.2509.26030.

Lean setup