Descriptions may be stale. Consult the linked Lean sources.
Spectral-Smooth Muon and
Adam Comparison
We consider nonconvex minimization of a differentiable function ,
where , with the Frobenius
inner product. The gradient is -Lipschitz from the spectral norm to the
nuclear norm, where , and a
given point has gap at most
above a global lower
bound. For with
, 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 with , 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
Write ,
with inner product and Frobenius norm . The spectral norm
is the
induced operator norm on maps from to , and is its dual under this inner
product. Gradients are taken with respect to the Frobenius inner
product. The algorithm receives , and ; the oracle model and its rowwise
noise profile are not inputs.
Our assumptions:
Assumption 1 (Spectral smoothness). The function
is Fréchet
differentiable everywhere, and
Assumption 2 (Initial gap). There exists such that
Assumption 3 (Stochastic gradients and rowwise
moments). There are a measurable sample space , a probability measure on , and a jointly measurable map
. For every
, the random matrix is Bochner integrable for , and There exist a fixed orthonormal basis of and numbers such that For
every and , the vector belongs
to and
satisfies At call , a query receives . The measurable sample
variables 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 Thus the minimum-Frobenius-norm maximizer
specifies the direction also when
is singular. The method chooses a constant step size , a batch size with , and a horizon from its inputs.
Starting at the given , it uses
Each of the queries in batch is made at . A measurable index , drawn using the algorithm’s
randomness, is uniform on , and the output is . The prescribed run uses
oracle calls, including
the batch at . After these
calls, the output remains 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 denote the joint law of
the algorithm’s randomness and the independent oracle sample sequence.
The output must be measurable, must be integrable under , and the required accuracy is
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
calls. Their recurrences and query rules likewise apply to every
possible reply sequence.
For Adam, consider every constant tuning satisfying and every and . With the batch average at its own iterate
, the analyzed bias-corrected
variant initializes and
uses 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 .
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 calls implies The objective and oracle
may depend on the competing algorithm and its tuning.
For batched stochastic gradient descent, consider every constant
, every and , and every algorithm following
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 calls implies
These two comparison requirements are part of the task, in addition to
the expected stationarity requirement for the Muon output.