Multiclass learnability and the ERM principle
arXiv:1308.2893
Abstract
We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist multiclass hypothesis classes for which some Empirical Risk Minimizers (ERM learners) have lower sample complexity than others. Furthermore, there are classes that are learnable by some ERM learners, while other ERM learners will fail to learn them. We propose a principle for designing good ERM learners, and use this principle to prove tight bounds on the sample complexity of learning {\em symmetric} multiclass hypothesis classes---classes that are invariant under permutations of label names. We further provide a characterization of mistake and regret bounds for multiclass learning in the online setting and the bandit setting, using new generalizations of Littlestone's dimension.
Cited by in corpus (18)
- VC Classes are Adversarially Robustly Learnable, but Only Improperly
- Model selection for contextual bandits
- Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
- Learning From An Optimization Viewpoint
- Maximum Margin Multiclass Nearest Neighbors
- Tight Risk Bounds for Multi-Class Margin Classifiers
- Proper Learning, Helly Number, and an Optimal SVM Bound
- A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts
- Unconfused ultraconservative multiclass algorithms
- On the Equivalence between Online and Private Learnability beyond Binary Classification
- Semi-supervised Vector-valued Learning: Improved Bounds and Algorithms
- On statistical learning via the lens of compression
- Optimizing Black-box Metrics with Iterative Example Weighting
- Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
- Data-dependent Generalization Bounds for Multi-class Classification
- Realizable Learning is All You Need
- Distilling Double Descent
- Minimax bounds for structured prediction