Descriptions may be stale. Consult the linked Lean sources.
Muon
and Scheduled Momentum Comparisons
We consider nonconvex minimization of a differentiable function ,
where are positive integers.
The gradient is Lipschitz from the spectral norm to the nuclear norm
with constant , and a given
starting point has gap at most
above a global lower
bound. The oracle returns unbiased stochastic gradients with
independent, identically distributed samples and rowwise second moments
controlled by . For , batched Muon must
return with , 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
Equip the matrix space with the Frobenius inner product and norm ;
gradients are taken with respect to this inner product. Write for the induced
Euclidean operator norm and for its dual nuclear norm.
Set . The parameters
satisfy The
algorithm receives , and ; the objective and the stochastic
oracle model are accessed only through oracle replies.
Our assumptions:
Assumption 1 (Spectral smoothness and initial gap).
The function is differentiable
everywhere, and There exists such that
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 . For each , is Bochner integrable and
There exist an orthonormal basis of and numbers with such that, for
every and , the vector
belongs to
and At call ,
a query receives , where the measurable random
variables 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 to be the
minimum-Frobenius-norm element of The algorithm chooses , an integer batch size , and an integer from its inputs. Starting at the
given , it queries times at each and follows After calls, it returns , where is a measurable function of algorithm
randomness, uniform on . The same output is
retained after any additional calls. Thus the batch at is counted even though 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 with measurable and integrable under
, 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 For either direction , fix any , any real-valued schedule
, and integers
and . The comparison recurrence,
initialized at ,
is Every batch consists of queries at . After calls the output is , with uniform on 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 at tolerance implies 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 These existential comparisons are part of the
required task, together with the expected stationarity requirement for
batched Muon.