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

Abstract

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 ${\ell }_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.

References in corpus (2)

• Moments and Absolute Moments of the Normal Distribution
• Conditional Probability Tree Estimation Analysis and Algorithms

Cited by in corpus (11)

• Structured Prediction Theory Based on Factor Graph Complexity
• Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm
• A Generalization Error Bound for Multi-class Domain Generalization
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
• Local Rademacher Complexity Bounds based on Covering Numbers
• Optimistic bounds for multi-output prediction
• Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
• MEMOIR: Multi-class Extreme Classification with Inexact Margin
• Rademacher Complexity and Generalization Performance of Multi-category Margin Classifiers
• Predicting Classification Accuracy When Adding New Unobserved Classes