mlsanityData to 14 Oct 2026

Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data

arXiv 2502.04664 ↗First posted 7 Feb 2025cs.LG math.OCcited by 41

Not on the map. Why?

Abstract (arXiv)

Different gradient-based methods for optimizing overparameterized models can all achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. We provide the first complete characterization of implicit optimization bias for p-norm normalized steepest descent (NSD) and momentum steepest descent (NMD) algorithms in multi-class linear classification with cross-entropy loss. Our key theoretical contribution is proving that these algorithms converge to solutions maximizing the margin with respect to the classifier matrix's p-norm, with established convergence rates. These results encompass important special cases including Spectral Descent and Muon, which we show converge to max-margin solutions with respect to the spectral norm. A key insight of our contribution is that the analysis of general entry-wise and Schatten p-norms can be reduced to the analysis of NSD/NMD with max-norm by exploiting a natural ordering property between all p-norms relative to the max-norm and its dual sum-norm. For the specific case of descent with respect to the max-norm, we further extend our analysis to include preconditioning, showing that Adam converges to the matrix's max-norm solution. Our results demonstrate that the multi-class linear setting, which is inherently richer than the binary counterpart, provides the most transparent framework for studying implicit biases of matrix-parameter optimization algorithms.

Key facts. Cited by 41 papers in the map (data through 14 Oct 2026). Builds on 59 of its 79 references that are in the map. First posted on arXiv 7 Feb 2025.

Builds on

59 of 79 references.

References · 59

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2021Convex optimizationcited by 2,515
  4. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  5. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  6. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  7. 2018Adafactor: Adaptive Learning Rates with Sublinear Memory Costcited by 905
  8. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  9. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  10. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  11. 2018Shampoo: Preconditioned Stochastic Tensor Optimizationcited by 426
  12. 2017Implicit Regularization in Matrix Factorizationcited by 322
38 more
  1. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  2. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  3. 2024Old Optimizer, New Norm: An Anthologycited by 193
  4. 2024SOAP: Improving and Stabilizing Shampoo using Adamcited by 192
  5. 2020Directional convergence and alignment in deep learningcited by 178
  6. 2016A Kronecker-factored approximate Fisher matrix for convolution layerscited by 141
  7. 2020Momentum Improves Normalized SGDcited by 139
  8. 2024Adam-mini: Use Fewer Learning Rates To Gain Morecited by 137
  9. 2024Why Transformers Need Adam: A Hessian Perspectivecited by 124
  10. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 119
  11. 2018Convergence of Gradient Descent on Separable Datacited by 110
  12. 2021Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticitycited by 110
  13. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  14. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 86
  15. 2025A Note on the Convergence of Muoncited by 83
  16. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  17. 2022Imbalance Trouble: Revisiting Neural-Collapse Geometrycited by 80
  18. 2023A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scalecited by 77
  19. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 76
  20. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 61
  21. 2020Gradient descent follows the regularization path for general lossescited by 59
  22. 2023Max-Margin Token Selection in Attention Mechanismcited by 58
  23. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  24. 2023Benchmarking Neural Network Training Algorithmscited by 52
  25. 2020The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networkscited by 46
  26. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42
  27. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  28. 2019Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalizationcited by 40
  29. 2015Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selectioncited by 39
  30. 2024The Implicit Bias of Adam on Separable Datacited by 36
  31. 2013Margins, Shrinkage, and Boostingcited by 35
  32. 2019The Impact of Regularization on High-dimensional Logistic Regressioncited by 35
  33. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
  34. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  35. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  36. 2022Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficientlycited by 26
  37. 2021Does Momentum Change the Implicit Regularization on Separable Data?cited by 22
  38. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 22

50 most cited of 59 All 59 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 7; 2026: 34.

41 papers.

Sort:

  1. 2025Isotropic Curvature Model for Understanding Deep Learning Optimization: Is Gradient Orthogonalization Optimal?cited by 37
  2. 2025On the Convergence of Muon and Beyondcited by 31
  3. 2026Preconditioning Benefits of Spectral Orthogonalization in Muoncited by 30
  4. 2025An Exploration of Non-Euclidean Gradient Descent: Muon and its Many Variantscited by 28
  5. 2025AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updatescited by 23
  6. 2026The Newton-Muon Optimizercited by 18
  7. 2026Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memorycited by 14
  8. 2026Muon is Not That Special: Random or Inverted Spectra Work Just as Wellcited by 14
  9. 2026The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networkscited by 11
  10. 2026Can Muon Fine-tune Adam-Pretrained Models?cited by 7
  11. 2026Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrievalcited by 6
  12. 2026Stabilizing Native Low-Rank LLM Pretrainingcited by 6
29 more
  1. 2026Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimizationcited by 5
  2. 2025Ky Fan Norms and Beyond: Dual Norms and Combinations for Matrix Optimizationcited by 4
  3. 2026Never Saddle for Reparameterized Steepest Descent as Mirror Flowcited by 4
  4. 2026Phases of Muon: When Muon Eclipses SignSGDcited by 3
  5. 2026The Spectral Dynamics and Noise Geometry of Muoncited by 3
  6. 2026Muon learns balanced solutions in matrix factorization without slow saddle-to-saddle dynamicscited by 3
  7. 2025Implicit Bias of Per-sample Adam on Separable Data: Departure from the Full-batch Regimecited by 2
  8. 2025Diagonalizing the Softmax: Hadamard Initialization for Tractable Cross-Entropy Dynamicscited by 2
  9. 2026Tight Complexity of Muon under Heavy-Tailed Noisecited by 2
  10. 2026Convergence of Spectral Descent for Non-smooth Optimizationcited by 2
  11. 2026Stability Annealing Selects the Implicit Bias of Smoothed Sign Descent: A Rate-Indexed Barrier Path on Separable Datacited by 2
  12. 2026Muonp: Muon with Fractional Spectral Powerscited by 1
  13. 2026Reassessing Muon for Matrix Factorizationcited by 1
  14. 2026Spectral Allocation: Why Muon Outperforms Adam, and How to Improve Muoncited by 1
  15. 2026Dual Space Preconditioning for Gradient Descent in the Overparameterized Regimecited by 0
  16. 2026Towards The Implicit Bias on Multiclass Separable Data Under Norm Constraintscited by 0
  17. 2026Optimizer-Induced Mode Connectivity: From AdamW to Muoncited by 0
  18. 2026HORST: Composing Optimizer Geometries for Sparse Transformer Trainingcited by 0
  19. 2026The Implicit Bias of Depth: From Neural Collapse to Softmax Codescited by 0
  20. 2026Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamicscited by 0
  21. 2026The Loss Does Not See the Basis, but Adam Doescited by 0
  22. 2026Optimizer-dependent training dynamics converge to the same one-third optimal data scalingcited by 0
  23. 2026The Row Normalization Puzzle in Muoncited by 0
  24. 2026Muon Learns Facts Better: Understanding the Role of Spectral Orthogonalizationcited by 0
  25. 2026Optimizer Geometry Sets the Pace: Spectral Learning Dynamics in Matrix Factorizationcited by 0
  26. 2026Simulating Training Spikes of Deep Neural Networks by Layer-wise Random Feature Modelscited by 0
  27. 2026From Parallel to Sequential: Small-Batch Noise Restores Simplicity Bias of Muoncited by 0
  28. 2026Which Optimizer Leaks Most? Optimizer Implicit Bias as a Training-Data Privacy Controllercited by 0
  29. 2026From Spectral to Frobenius: When Muon Loses Its Spectral Implicit Biascited by 0