# Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification

arXiv: https://arxiv.org/abs/2505.22359 · HTML: https://mlsanity.com/paper/2505.22359/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 26 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 16 of 16)

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Gradient descent follows the regularization path for general losses](https://mlsanity.com/paper/2006.11226/) (2020)
- [Gradient Methods Never Overfit On Separable Data](https://mlsanity.com/paper/2007.00028/) (2020)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [The Implicit Bias of Gradient Descent on Separable Multiclass Data](https://mlsanity.com/paper/2411.01350/) (2024)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)
- [Characterizing the implicit bias via a primal-dual analysis](https://mlsanity.com/paper/1906.04540/) (2019)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)
- [Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization](https://mlsanity.com/paper/2412.04274/) (2024)

## Built on by (most cited first, 2 of 2)

- [Post-Training with Policy Gradients: Optimality and the Base Model Barrier](https://mlsanity.com/paper/2603.06957/) (2026)
- [SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws](https://mlsanity.com/paper/2609.07868/) (2026)

## Abstract (arXiv)

We study the generalization performance of unregularized gradient methods for separable linear classification. While previous work mostly deal with the binary case, we focus on the multiclass setting with k classes and establish novel population risk bounds for Gradient Descent for loss functions that decay to zero. In this setting, we show risk bounds that reveal that convergence rates are crucially influenced by the geometry of the loss template, as formalized by Wang and Scott (2024), rather than of the loss function itself. Particularly, we establish risk upper bounds that holds for any decay rate of the loss whose template is smooth with respect to the p-norm. In the case of exponentially decaying losses, our results indicates a contrast between the p=∞ case, where the risk exhibits a logarithmic dependence on k, and p=2 where the risk scales linearly with k. To establish this separation formally, we also prove a lower bound in the latter scenario, demonstrating that the polynomial dependence on k is unavoidable. Central to our analysis is a novel bound on the Rademacher complexity of low-noise vector-valued linear predictors with a loss template smooth w.r.t.~general p-norms.