Research map / Optimization / Implicit bias and generalization
Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification
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.
Studies finite-time generalization of unregularized gradient descent on separable multiclass linear classification, showing risk depends on the smoothness norm p of the loss template (log k for p=∞ vs linear k for p=2, with a matching L2 lower bound).
Problem
Finite-time generalization of unregularized gradient descent for separable multi-class linear classification, and how risk bounds depend on the number of classes k and on the loss template's geometry rather than only its decay rate.
Approach
Shows that multiclass GD risk bounds depend on the loss template's smoothness with respect to the L_p norm, not just its tail decay: the p-dependent factor k^{2/p} in bounds, a new low-noise Rademacher complexity bound for vector-valued predictors, and step size tuned via template smoothness.
Key results
- For exponentially tailed losses with L_infinity-smooth templates (e.g., cross-entropy), GD population risk is O~(1/(gamma^2 T) + 1/(gamma^2 n)) with only log k dependence on classes.
- For p=2, a lower bound Omega~(k/(gamma^2 T) + k/(gamma^2 n)) shows a linear dependence on k is unavoidable for exponentially tailed templates.
- General upper bound O~(beta k^{2/p} rho^{-1}(eps/k)^2 / (gamma^2 min{T,n})) for any tail-decaying loss with L_p-smooth template.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a larger smoothness norm index p for the loss template | Gradient Descent for separable multiclass classification · Separable multiclass classification | population risk upper-bound dependence on k: k^{\frac{2}{p}} | Helped |
| Use an L_∞-smooth template instead of an L_2-smooth template | Gradient Descent with exponentially-tailed losses · Separable multiclass classification | population risk dependence on k: logarithmically on k; linear dependence on the number of classes | Helped |
| Use cross-entropy, whose template is smooth w.r.t. L_∞ | Gradient Descent · Separable multiclass classification | population risk upper bound: \widetilde{O}\left( \frac{1}{\margin^2T}+ \frac{1}{\margin^2n}\right) | Helped |
| Use an L_2-smooth template with exponential decay | Gradient Descent · Separable multiclass classification | population risk lower bound: \widetilde {\Omega}\left( \frac{k}{\margin^2T}+ \frac{k}{\margin^2n}\right) | Hurt |
Surprising findings
- Risk bounds depend on the L_p smoothness geometry of the template, contrary to the binary case where only the decay rate matters and to prior claims that exponential-tailed losses behave similarly asymptotically.
Limitations
- Analysis restricted to linear predictors and separable data with margin.
- Bounds contain polylogarithmic factors and an unspecified constant C depending on k, n, and M.
- Results are theoretical with no empirical validation.
Experimental setup
Metrics: population risk bounds
Baselines: Lei and Ying (2020) VVP Rademacher bounds Li et al. (2018) VVP bounds Richards and Kuzborskij (2023) binary GD bounds
Builds on: PERM framework local Rademacher complexity binary smooth-loss GD generalization bounds
Closest papers by meaning
- A Universal Growth Rate for Learning with Smooth Surrogate Losses (NeurIPS 2024 · similarity 0.89)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.89)
- Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification (NeurIPS 2024 · similarity 0.87)
- Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses (NeurIPS 2025 · similarity 0.87)
- Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data (NeurIPS 2025 · similarity 0.87)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.