Research map / Optimization / Implicit bias and generalization

The Implicit Bias of Gradient Descent on Separable Multiclass Data

NeurIPS 2024 · Optimization › Implicit bias and generalization · approach: Implicit bias in linear networks · 1 citations (OpenAlex)

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.

Extends the binary exponential-tail implicit bias result to multiclass classification via PERM losses, showing GD on separable multiclass data converges in direction to the multiclass hard-margin SVM.

Problem

Implicit bias of gradient descent for multiclass classification beyond cross-entropy: existing multiclass results are restricted to cross-entropy, and no multiclass analogue of the binary exponential tail property existed.

Approach

Uses the PERM (permutation equivariant, relative margin-based) loss framework to define a multiclass exponential tail property on the gradient of the loss template, and extends the binary proof of directional convergence to the hard-margin multiclass SVM, mirroring the binary argument side by side.

Key results

• Proves that for almost all linearly separable multiclass datasets, GD on a convex, beta-smooth, strictly decreasing ET PERM loss has w(t) = w_hat log(t) + rho(t) with bounded residual, implying directional convergence to the multiclass hard-margin SVM.
• Verifies the PERM exponential tail property for cross-entropy, multiclass exponential loss, and PairLogLoss.
• Experiments on 100 synthetic datasets per (d, K) choice confirm the auxiliary existence assumption on tilde-w holds.

Limitations

• Existence of the auxiliary solution tilde-w is assumed for the multiclass case rather than proven (only conjectured for almost all datasets).
• Analysis restricted to convex, beta-smooth PERM losses; convexity not needed in binary case.
• Only vanilla full-batch gradient descent analyzed; non-ET losses, SGD and other methods left open.

Experimental setup

Datasets: synthetically generated linearly separable datasets

Metrics: directional convergence to hard-margin multiclass SVM verification of existence of tilde-w assumption

Baselines: cross-entropy implicit bias results (Soudry et al.) Lyu and Li Ji and Telgarsky

Builds on: Soudry et al. implicit bias of gradient descent on separable data PERM losses exponential tail property

Closest papers by meaning

• The Implicit Bias of Gradient Descent on Separable Data (ICLR 2018 · similarity 0.89)
• The Implicit Bias of AdaGrad on Separable Data (NeurIPS 2019 · similarity 0.88)
• Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data (NeurIPS 2025 · similarity 0.88)
• Faster Margin Maximization Rates for Generic Optimization Methods (NeurIPS 2023 · similarity 0.87)
• Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification (NeurIPS 2024 · similarity 0.84)
• Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.84)