← All setups

Finite Variance Muon High Probability — Muon with Finite-Variance Matrix Gradients

Descriptions may be stale. Consult the linked Lean sources.

Muon with Finite-Variance Matrix Gradients · Lean proof

Muon with Finite-Variance Matrix Gradients

We consider a differentiable, possibly nonconvex objective f:E→R on E=Rm×n with the Frobenius inner product, where m,n are nonnegative integers. Its gradient is L-Lipschitz from the spectral norm to the nuclear norm, with L≥0, and a given x0∈E has gap at most Δ≥0 above a global lower bound. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with row standard deviations summing to at most s≥0 in a fixed orthonormal basis. The specified Muon variant must return a measurable x¯ satisfying ∥∇f(x¯)∥∗≤ε with probability at least 1−δ, where ∥⋅∥∗ is the nuclear norm, ε>0, and δ∈(0,1).

The underlying optimization problem is infx∈Ef(x). Write ⟨X,Y⟩F=tr(X⊤Y) and ∥X∥F for the Frobenius inner product and norm. The spectral norm ∥X∥op is the induced operator norm of X:Rn→Rm with Euclidean norms, and ∥X∥∗ is its dual norm under this inner product. Gradients are taken with respect to the Frobenius inner product. The algorithm receives m,n,L,Δ,s,ε,δ, and x0; the noise law and the basis and row bounds described below are not inputs.

Our assumptions:

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

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

Assumption 3 (Unbiased gradients with a row variance profile). There is a probability law ν on a measurable sample space Ω and a jointly measurable map g:E×Ω→E. For every x∈E, g(x,⋅) is Bochner integrable and Eξ∼ν[g(x,ξ)]=∇f(x). There exist an orthonormal basis (vi)i=1m of Rm and nonnegative numbers (σi)i=1m such that ∑i=1mσi≤s,Eξ∼ν[∥(g(x,ξ)−∇f(x))⊤vi∥22]≤σi2,x∈E,1≤i≤m. Each row-error map in this display belongs to L2(ν;Rn). At successive calls, the oracle uses measurable, mutually independent samples ξ0,ξ1,…, each with law ν, and returns g(x,ξℓ) at the queried point x. Algorithm randomness is independent of this sample sequence.

Our formulation is algorithm-specific: we analyze Muon with momentum, polar updates, and a sampled-candidate selection rule. Define the polar map by the minimum-Frobenius-norm maximizer polar(M)=operatorname∗argminU∈S(M)∥U∥F,S(M)=argmax∥V∥op≤1⟨M,V⟩F. The algorithm chooses parameters 0<α≤1,η>0,ρ>0,T,k,q∈Z≥0,b∈Z≥1. Starting from the given x0 and M0=0, it queries the training points xt for t=0,…,T, with replies Gt=g(xt,ξt). The candidate trajectory is defined by Mt+1=(1−α)Mt+αGt,xt+1=xt−ηpolar(Mt+1),0≤t<T. Thus there are T+1 training queries, including the query at xT.

Using its own randomness, the algorithm draws q+1 independent indices I0,…,Iq, uniformly distributed on {0,…,T}, and sets yi=xIi. At each yi, it collects k+1 batches of b further oracle replies. With zero-based indices, these batch means are aij=T+1+b(k+1)i+bj,Bij=1b∑u=0b−1g(yi,ξaij+u),0≤i≤q,0≤j≤k. For each candidate, define Ji={j∈{0,…,k}:2|{ℓ∈{0,…,k}:∥Bij−Biℓ∥∗≤ρ}|>k+1}. Let ji be the smallest element of Ji when it is nonempty, and let ji=0 otherwise. Set G^i=Biji. The output rule is i∗=minargmin0≤i≤q∥G^i∥∗,x¯=yi∗. This procedure uses T+1+b(k+1)(q+1) oracle calls. Its output remains the same after any additional calls. The family also includes a constant-output alternative: when 2LΔ≤ε2, the algorithm may return x0 at every stage.

Queries may be made at any point of E. The required output is measurable and satisfies PP(∥∇f(x¯)∥∗>ε)≤δ, where P is the joint law of the algorithm randomness and the independent oracle sample sequence.

Proved result

{02⋅L⋅Δ≤ε2⌈245⋅(1+s2ε2)⋅(1+L⋅Δε2+1+L⋅Δε2⋅(log⁡(256⋅(1+s2ε2)⋅(1+L⋅Δε2)δ))2)⌉+otherwise

OracleTemplate.Convergence LongTails.Setups.FiniteVarianceSpectralSmooth.spec
  LongTails.Theorems.FiniteVarianceMuonHighProbability.budget

Relevant previous results

  • Rui Pan, Yang Luo, Yuxing Liu, Yang You, Tong Zhang. Unbiased Gradient Low-Rank Projection. 2025, preprint v1. Complexity: O(1+LΔ/ε2+v2/ε2+LΔv2/ε4) stochastic-gradient calls for GUM with sampling probability q=1/2, achieving expected nuclear gradient norm at most ε at a uniformly sampled period-start iterate; v=∥V∥∗, where the noise Z(X) satisfies E[Z(X)Z(X)⊤]⪯VV⊤ uniformly.
  • Hongyi Tao, Dingzhi Yu, Lijun Zhang. When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ₁-norm Lower Bounds. 2026, preprint v1. Complexity: O((1+LΔ/ε2)(1+v2/ε2)) stochastic-gradient calls, including batches, for minibatched Muon achieving E∥∇f(XR)∥∗≤ε at a uniformly sampled iterate; v=tr(Σ), where E[Z(X)Z(X)⊤]⪯Σ2 uniformly and Σ⪰0.