Research map / Optimization / Implicit bias and generalization
Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes implicit bias of normalized steepest descent and momentum steepest descent (incl. Spectral Descent, Muon, Adam) on multiclass linear separable data with cross-entropy, proving margin convergence to max-margin solutions w.r.t. the same p-norm at O(1/sqrt t)-type rates.
Problem
Implicit bias of spectral descent and Muon (and related normalized steepest descent/momentum methods) when training linear multiclass classifiers on separable data with cross-entropy loss; which norm-margin solution they converge to and at what rate.
Approach
A per-sample softmax proxy function G(W)=mean(1 - s_{i,y_i}) sandwiches the loss and lower-bounds the gradient dual norm for any entry-wise or Schatten p-norm; using the ordering max-norm <= p-norm <= sum-norm reduces all p-norm cases to the max-norm analysis, and a per-class decomposition handles momentum.
Key results
- NSD with respect to any entry-wise or Schatten p-norm converges to the max-margin solution for that norm with margin gap rate O((log t + n)/t^{1/2}) (Theorem for NSD).
- NMD (including Muon) achieves margin gap O((d log t + dn)/t^{1/2}); Adam's max-norm margin convergence is shown at rate O((d log t + nd)/t^{1/3}) in the appendix.
- In experiments, SignGD, NGD and Spectral-GD/Muon correlate with max-norm, 2-norm and spectral-norm max-margin separators respectively.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SignGD instead of a 2-norm-preferring optimizer | Linear multiclass classifier · Synthetic multiclass separable data | margin preference | Mixed |
| Use NGD instead of a max-norm-preferring optimizer | Linear multiclass classifier · Synthetic multiclass separable data | margin preference | Mixed |
| Use spectral-norm steepest descent | Linear multiclass classifier · Synthetic multiclass separable data | margin preference | Helped |
| Use spectral-norm momentum steepest descent | Linear multiclass classifier · Synthetic multiclass separable data | margin preference | Helped |
| Use Spectral-GD or Muon rather than the other algorithms | Two-layer neural network · MNIST | spectral-norm margin growth | Helped |
| Use Signum rather than a 2-norm-preferring momentum optimizer | Linear multiclass classifier · Synthetic multiclass separable data | margin preference | Mixed |
| Use NMD-GD rather than a max-norm-preferring momentum optimizer | Linear multiclass classifier · Synthetic multiclass separable data | margin preference | Mixed |
Surprising findings
- The Adam rate proven is O(t^{-1/3}), weaker than the O(t^{-1/2}) rate for NSD/NMD, reflecting analysis looseness rather than observed behavior.
Limitations
- Analysis restricted to linear models; nonlinear results are only empirical on a two-layer network.
- NMD rate carries an extra factor d compared with NSD; Adam rate is slower (t^{-1/3}).
- Assumes bounded 1-norm of data and separability.
Experimental setup
Datasets: synthetic Gaussian multiclass data MNIST
Benchmarks: synthetic separable data MNIST subset (two-layer network)
Metrics: relative margin gap correlation with max-margin separators spectral-norm margin of iterates
Baselines: SignGD NGD Spectral-GD Signum NMD-GD Adam
Builds on: Muon Adam normalized gradient descent Spectral descent
Closest papers by meaning
- The Implicit Bias of Steepest Descent with Mini-batch Stochastic Gradient (ICML 2026 · similarity 0.91)
- The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networks (ICML 2026 · similarity 0.90)
- The Implicit Bias of Gradient Descent on Separable Multiclass Data (NeurIPS 2024 · similarity 0.88)
- Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks (ICML 2025 · similarity 0.87)
- Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks (ICLR 2025 · similarity 0.87)
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.