Towards The Implicit Bias on Multiclass Separable Data Under Norm Constraints

Shengping Xie; Zekun Wu; Quan Chen; Kaixu Tang

cs.LGMar 24, 2026

Towards The Implicit Bias on Multiclass Separable Data Under Norm Constraints

Authors: Shengping Xie, Zekun Wu, Quan Chen, Kaixu Tang

Organizations: School of Mathematical Sciences, Peking University

Abstract

Implicit bias induced by gradient-based algorithms is essential to the generalization of overparameterized models, yet its mechanisms can be subtle. This work leverages the Normalized Steepest Descent} (NSD) framework to investigate how optimization geometry shapes solutions on multiclass separable data. We introduce NucGD, a geometry-aware optimizer designed to enforce low rank structures through nuclear norm constraints. Beyond the algorithm itself, we connect NucGD with emerging low-rank projection methods, providing a unified perspective. To enable scalable training, we derive an efficient SVD-free update rule via asynchronous power iteration. Furthermore, we empirically dissect the impact of stochastic optimization dynamics, characterizing how varying levels of gradient noise induced by mini-batch sampling and momentum modulate the convergence toward the expected maximum margin solutions.Our code is accessible at: https://github.com/Tsokarsic/observing-the-implicit-bias-on-multiclass-seperable-data.

Figures & tables

Method	Norm Constraint	Update $\bm{\Delta}$	Reference
NGD	Unit $\\|\cdot\\|_{2}$ -ball	$\frac{\bm{G}}{\\|\bm{G}\\|_{2}}$	Hazan et al. [ 11 ]
NMD-GD	Unit $\\|\cdot\\|_{2}$ -ball	$\frac{\bm{M}}{\\|\bm{M}\\|_{2}}$	Cutkosky and Mehta [ 12 ]
SignGD	Unit $\\|\cdot\\|_{\text{max}}$ -ball	$\text{sign}(\bm{G})$	Bernstein et al. [ 13 ]
Signum	Unit $\\|\cdot\\|_{\text{max}}$ -ball	$\text{sign}(\bm{M})$	Bernstein et al. [ 13 ]
Spectral-GD	Unit $\\|\|\cdot\|\\|_{\infty}$ -ball	$UV^{T}$	Bernstein and Newhouse [ 14 ]
Muon	Unit $\\|\|\cdot\|\\|_{\infty}$ -ball	$\tilde{U}\tilde{V}^{T}$	Liu et al. [ 5 ]

Table 1: Summary of existing algorithms under the framework of NSD under respective norm constraints. Here

U,V,\tilde{U},\tilde{V}

are computed by the SVD decomposition of the gradient or momentum, and the algorithms listed above each group correspond to the momentum-free method.

Panel of Figure 1 — Figure 1: Correlations and spectrum for max margin solutions under different norm

Figure 2: The Weight Heatmap of max margin solutions under different norm

Panel of Figure 3 — Figure 3: NucGD experiments: (a) singular value spectra of max-margin solutions under different norms; (b) normalized-margin error along NucGD measured against different max-margin references; (c) correlations between NucGD iterates and different max-margin directions; (d) singular value spectra of final solutions produced by different NSD algorithms.

Panel of Figure 4 — Figure 4: Effect of noise controlled by batch size $B$

Panel of Figure 5 — Figure 5: Effect of momentum weight $\mu$ , mini-batch training

Panel of Figure 6 — Figure 6: Effect of momentum weight $\mu$ , full-batch training

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: Correlation between GD based solution and optimal solution corresponding to specific norm

Panel of Figure 8 — Figure 8: Margin error between GD based solution and optimal solution corresponding to specific norm

Implicit Bias

Implicit bias studies how training algorithms and model structure favor particular solutions, representations, and generalization behaviors without explicit penalties.

See all 30 papers

From Spectral to Frobenius: When Muon Loses Its Spectral Implicit Bias
Oct 14, 2026Yongtao Wu, Mahdi Mansouri, Zhenyu ZhuMuon Optimizer Implicit Regularization
The University of Hong Kong
From Geometry to Generalization: Why Row Normalization Can Beat Adam and Muon
Oct 8, 2026Jihwan Kim, Dogyoon Song, Chulhee YunAdaptive Gradient Methods Classification
Seoul National University · KAIST InnoCORE LLM · University of California, Davis +1
Minor First, Major Last: A Depth-Induced Implicit Bias of Sharpness-Aware Minimization
Mar 9, 2026Chaewon Moon, Dongkuk Si, Chulhee YunSharpness-Aware Minimization Implicit Bias
Kim Jaechul Graduate School of AI, KAIST · Mobilint, Inc.

Oct 14, 2026J/K move · Enter open · S save

From Spectral to Frobenius: When Muon Loses Its Spectral Implicit Bias

Yongtao Wu, Mahdi Mansouri, Zhenyu Zhu

The University of Hong Kong

Muon Optimizer Implicit Regularization Gradient Descent Dynamics Newton-Schulz Iteration

Open paper AskPDF arXiv

Prior work on implicit bias shows that gradient descent selects the Frobenius max-margin direction on linearly separable problems, whereas Fan et al. (2025) established spectral max-margin behavior for spectral-norm steepest descent methods, including idealized Muon with exact orthogonalization. In practice, however, Muon approximates orthogonalization using finite Newton-Schulz iterations and a positive stabilization constant. We prove that these implementation choices cause Muon to select the Frobenius rather than the spectral max-margin direction in linear classification with separable data. We also establish this behavior for both exponential moving average and Nesterov-style momentum. The key technical ingredient is a summable perturbation argument showing that the resulting parameter trajectories remain at bounded distance from those of gradient descent. We then disentangle the roles of Newton-Schulz iteration count, the stabilization constant, and the Newton-Schulz polynomial, revealing distinct asymptotic behaviors, including directions that achieve neither Frobenius nor spectral max-margin. Finally, we show that Muon can recover its spectral max-margin bias with Newton-Schulz iterations growing logarithmically over training.

Abstract

Implicit Bias

Explore similar work

From Spectral to Frobenius: When Muon Loses Its Spectral Implicit Bias

From Geometry to Generalization: Why Row Normalization Can Beat Adam and Muon

Minor First, Major Last: A Depth-Induced Implicit Bias of Sharpness-Aware Minimization