Spectral-Smooth Muon and Adam Comparison
Descriptions may be stale. Consult the linked Lean sources.
Spectral-Smooth Muon and Adam Comparison
We consider nonconvex minimization of a differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Spectral smoothness). The function
Assumption 2 (Initial gap). There exists
Assumption 3 (Stochastic gradients and rowwise
moments). There are a measurable sample space
Our result is algorithm-specific: we analyze batched Muon without
momentum. Define the polar direction by
Let
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
For Adam, consider every constant tuning satisfying
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
For batched stochastic gradient descent, consider every constant
Results
Differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) MuonAdamSgdSeparation
(Ours) |
Muon: Adam: SGD: Lower bounds: every constant tuning and batch size; uniform-iterate
output. Adam is bias-corrected, |
||
| (2) Muon (Tao et al. 2026), Thm. 4 | One-sided covariance: |
(1): Adds an Adam lower
bound. Matches known Muon rate at |
(1) fixes |
| (3) Repository Muon guarantee and SGD lower bound (LongTails, n.d.-a, n.d.-b) | Muon: At |
(1): Adds the full two-moment Adam lower bound; reuses the Muon guarantee and SGD separation on the common setup. | (1) specializes the Muon
guarantee to square matrices, |
| (4) One-step SignGD comparison (Wang et al. 2025), Thm. 5.3 | One-step learning-imbalance result, not a
stationarity complexity bound. Restricted to |
(1): Multistep,
batch-uniform Adam lower bound yields asymptotic separation when |
|
| (5) Adam nonconvergence (Reddi et al. 2018), Thm. 3 | Nonconvergence on a one-dimensional
constrained stochastic convex instance, |
(1): Quantitative finite-budget lower bound for constant-parameter Adam on unconstrained matrix problems, uniform over batches and damping. Method-specific separation; no improved problem-class upper bound. | (1) does not cover decreasing steps; its Adam bound is limited to uniform-iterate output, excluding last or averaged outputs and AdamW. |
Abbr: