Descriptions may be stale. Consult the linked Lean sources.
Muon with
Spectral Smoothness
We consider a differentiable, possibly nonconvex objective on the Frobenius space
, where
are nonnegative integers. The
gradient is Lipschitz from the spectral norm to the nuclear norm, and a
given point has a bounded
gap to a global lower bound. The oracle returns unbiased stochastic
gradients from independent, identically distributed samples, with
bounded rowwise second moments in a fixed orthonormal basis. For , Muon must return a
random iterate satisfying
, where is the nuclear norm and the
expectation includes sampling and algorithm randomness. Success
additionally requires worst-case implications for two alternative
momentum directions.
The optimization problem is Equip with the
Frobenius inner product and norm . Write for the induced
operator norm of and for its dual nuclear norm.
Gradients are taken with respect to the Frobenius inner product. The
algorithm receives ,
with
Our assumptions:
Assumption 1 (Spectral smoothness and initial gap).
The function is Fréchet
differentiable everywhere, and There exists such that
Assumption 2 (Independent stochastic gradients).
There are a probability law on
a measurable space and a
jointly measurable map . For every , the
map is Bochner
integrable and There exist a fixed orthonormal basis of and numbers with such that, for
every and , the random vector
belongs to
and At call ,
the oracle returns at
the queried point . The
measurable samples
are mutually independent with common law , and are independent of the
algorithm’s randomness.
Our result is algorithm-specific: we analyze Muon with a constant
step size and batched momentum. Define its polar direction by The minimum-norm selection specifies the
direction also for rank-deficient matrices, including . The algorithm
chooses , an integer , and an integer from its inputs. Starting from the
given and , it uses All
queries in batch are made at
. A measurable index , drawn from the algorithm’s randomness
independently of the samples, is uniform on . After calls, the output is ; it remains this same output
after any additional calls. These query and output rules must hold for
every realization of the algorithm’s randomness and every possible reply
sequence.
The output must be measurable, its gradient nuclear norm must be
integrable, and it must satisfy where
is the joint law of the algorithm’s randomness and the independent
oracle samples.
The task also includes two worst-case requirements, which are part of
success rather than additional assumptions on . Set and define For each , whenever
the following statement is required. For every , integers and , and every algorithm satisfying
the same initialization, batching, uniform-index output, and output
persistence rules with update there exist
an objective and a stochastic oracle satisfying the assumptions above
with the same inputs such that success after exactly calls implies Here success in this implication
means that the resulting output is measurable, its gradient nuclear norm
is integrable, and its expected gradient nuclear norm is at most under its joint randomness
law. The objective and oracle in each implication may depend on the
alternative-direction algorithm and its tuning.