The Implicit Bias of Gradient Descent on Separable Multiclass Data

Hrithik Ravi, Clayton Scott, Daniel Soudry, Yutong Wang

Introduction

In modern machine learning, models are frequently overparameterized, possessing significantly more parameters than training examples. Theoretically, such models are capable of interpolating training data in numerous ways, many of which should lead to poor generalization. However, in practice, gradient descent (GD) consistently identifies solutions that generalize well. This phenomenon is attributed to implicit bias: the tendency of an optimization algorithm to favor specific, often simpler or higher-margin, solutions without explicit regularization.

While the implicit bias of gradient descent is well-established for binary classification—where it is known to converge toward the hard-margin Support Vector Machine (SVM) solution—the theory for multiclass classification has remained less developed. Previous research primarily focused on specific loss functions like cross-entropy. This paper bridges this gap by establishing a general framework for understanding implicit bias across a broad class of multiclass loss functions.

The PERM Loss Framework and the ET Property

To generalize the theory of implicit bias, the authors utilize the Permutation Equivariant and Relative Margin-based (PERM) loss framework. A loss function is considered PERM if it satisfies two conditions:

  1. Permutation Equivariance: The loss remains invariant if class labels are swapped.
  2. Relative Margin-based: The loss depends on the differences (relative margins) between the score of the correct class and the scores of all other classes.

By focusing on relative margins, the authors decouple the specific labels from the scores, simplifying the mathematical analysis of multiclass dynamics. The core technical innovation of this work is Definition 2.2: The Multiclass Exponential Tail (ET) Property. In binary settings, an exponential tail implies that the loss decreases exponentially as the margin grows. The authors extend this to the multiclass setting by requiring that the gradient of the loss template is bounded by exponential functions. This property is shown to hold for standard cross-entropy, multiclass exponential loss, and the PairLogLoss.

Theoretical Results: Convergence to the Hard-Margin SVM

The primary contribution of the paper is Theorem 3.4, which characterizes the asymptotic behavior of gradient descent iterates $w(t)$ when applied to a convex, smooth, and strictly decreasing PERM loss satisfying the ET property. The authors prove that the iterates evolve according to the following relationship:

$$w(t) = \hat{w} \log(t) + \rho(t)$$

In this expression, $\hat{w}$ represents the hard-margin multiclass SVM solution, and $\rho(t)$ is a bounded residual term. A critical consequence of this theorem is directional convergence: as time $t$ approaches infinity, the normalized weight vector $\frac{w(t)}{\|w(t)\|}$ converges exactly to the normalized SVM solution $\frac{\hat{w}}{\|\hat{w}\|}$.

This result demonstrates that the implicit bias toward maximum-margin solutions is not a unique feature of cross-entropy but is a fundamental property of any multiclass loss function that satisfies the ET property. This unifies the understanding of multiclass optimization under a single theoretical umbrella that mirrors the classic binary case.

Experimental Validation

The authors validated their theoretical findings through simulations on linearly separable multiclass datasets:

  • Synthetic Visualizations: Using small-scale data ($N=10, d=2, K=3$), they visualized decision boundaries to confirm they align with SVM expectations.
  • High-Dimensional Analysis: In larger simulations ($N=100, d=10, K=3$), they tracked GD iterates over 100,000 iterations. The results confirmed that even for non-standard losses like PairLogLoss, the iterates consistently converged toward the SVM solution in direction.

Limitations and Future Directions

While this work provides a significant advancement in optimization theory, several avenues for future research remain:

  • Linearity Constraints: The current proofs are limited to linear classifiers. Extending these results to deep, non-linear neural networks is a necessary next step.
  • Data Separability: The analysis assumes the data is linearly separable. Future studies could investigate "quasi-separable" or non-separable datasets.
  • Optimization Variants: The study focuses on vanilla gradient descent. The impact of adaptive optimizers (e.g., Adam) or stochastic gradient descent (SGD) on multiclass implicit bias remains an open question.
  • Non-Exponential Tails: The ET property is central to this proof; losses with different tail behaviors (such as polynomial tails) may exhibit different biases or lack them entirely.

Summary updated

BibTeX
@inproceedings{ravi2024implicit,
  author = {Hrithik Ravi and Clayton Scott and Daniel Soudry and Yutong Wang},
  title = {{The Implicit Bias of Gradient Descent on Separable Multiclass Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=JlWn80mTJi},
}
Figure