Descriptions may be stale. Consult the linked Lean sources.
Muon with
Finite-Variance Matrix Gradients
We consider a differentiable, possibly nonconvex objective on with the
Frobenius inner product, where
are nonnegative integers. Its gradient is -Lipschitz from the spectral norm to the
nuclear norm, with , and a
given has gap at most
above a global lower
bound. The oracle returns unbiased stochastic gradients from
independent, identically distributed samples, with row standard
deviations summing to at most in a fixed orthonormal basis. The
specified Muon variant must return a measurable satisfying
with probability at least ,
where is the nuclear
norm, , and .
The underlying optimization problem is Write and for the
Frobenius inner product and norm. The spectral norm is the induced
operator norm of with
Euclidean norms, and is its
dual norm under this inner product. Gradients are taken with respect to
the Frobenius inner product. The algorithm receives , and
; the noise law and the basis
and row bounds described below are not inputs.
Our assumptions:
Assumption 1 (Spectral-to-nuclear smoothness). The
function is Fréchet
differentiable everywhere, and
Assumption 2 (Initial objective gap). There exists
such
that
Assumption 3 (Unbiased gradients with a row variance
profile). There is a probability law on a measurable sample space and a jointly measurable map . For every , is Bochner integrable and
There exist an orthonormal basis of and nonnegative numbers
such that Each row-error map in this display belongs to
. At
successive calls, the oracle uses measurable, mutually independent
samples , each
with law , and returns at the queried point . 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 The algorithm chooses parameters Starting from the given and , it queries the training points
for , with replies . The candidate
trajectory is defined by Thus there are training queries, including the query
at .
Using its own randomness, the algorithm draws independent indices , uniformly distributed on
, and sets . At each , it collects batches of further oracle replies. With zero-based
indices, these batch means are For each candidate, define Let be the smallest element of when it is nonempty, and
let otherwise. Set . The output rule
is This procedure uses oracle calls. Its output
remains the same after any additional calls. The family also includes a
constant-output alternative: when , the algorithm
may return at every stage.
Queries may be made at any point of . The required output is measurable and
satisfies where is the
joint law of the algorithm randomness and the independent oracle sample
sequence.