# Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2015.

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

- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [Modeling Multi-Label Action Dependencies for Temporal Action Localization](https://mlsanity.com/paper/2103.03027/) (2021)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Generalization for multiclass classification with overparameterized linear models](https://mlsanity.com/paper/2206.01399/) (2022)
- [Model-agnostic Measure of Generalization Difficulty](https://mlsanity.com/paper/2305.01034/) (2023)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Towards Exact Computation of Inductive Bias](https://mlsanity.com/paper/2406.15941/) (2024)
- [Fine-grained Generalization Analysis of Structured Output Prediction](https://mlsanity.com/paper/2106.00115/) (2021)
- [Classification of Data Generated by Gaussian Mixture Models Using Deep ReLU Networks](https://mlsanity.com/paper/2308.08030/) (2023)
- [Linear Algorithms for Robust and Scalable Nonparametric Multiclass Probability Estimation](https://mlsanity.com/paper/2205.12460/) (2022)
- [Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbacks](https://mlsanity.com/paper/2509.07499/) (2025)
- [Generalization Analysis on Learning with a Concurrent Verifier](https://mlsanity.com/paper/2210.05331/) (2022)
- [Demystifying the Optimal Fair Classifier in Multi-Class Classification](https://mlsanity.com/paper/2606.00656/) (2026)

## Abstract (arXiv)

This paper studies the generalization performance of multi-class classification algorithms, for which we obtain, for the first time, a data-dependent generalization error bound with a logarithmic dependence on the class size, substantially improving the state-of-the-art linear dependence in the existing data-dependent generalization analysis. The theoretical analysis motivates us to introduce a new multi-class classification machine based on ℓp-norm regularization, where the parameter p controls the complexity of the corresponding bounds. We derive an efficient optimization algorithm based on Fenchel duality theory. Benchmarks on several real-world datasets show that the proposed algorithm can achieve significant accuracy gains over the state of the art.