# Optimal Learners for Multiclass Problems

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2014.

## Built on by (most cited first, 30 of 65)

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Minimax Optimal Online Imitation Learning via Replay Estimation](https://mlsanity.com/paper/2205.15397/) (2022)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [A Theory of PAC Learnability under Transformation Invariances](https://mlsanity.com/paper/2202.07552/) (2022)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [A Trichotomy for Transductive Online Learning](https://mlsanity.com/paper/2311.06428/) (2023)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [Multiclass Boosting: Simple and Intuitive Weak Learning Criteria](https://mlsanity.com/paper/2307.00642/) (2023)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [Multiclass Learnability Does Not Imply Sample Compression](https://mlsanity.com/paper/2308.06424/) (2023)
- [Active Learning with Label Comparisons](https://mlsanity.com/paper/2204.04670/) (2022)
- [Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem](https://mlsanity.com/paper/2304.08712/) (2023)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization](https://mlsanity.com/paper/2410.23461/) (2024)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)

## Abstract (arXiv)

The fundamental theorem of statistical learning states that for binary classification problems, any Empirical Risk Minimization (ERM) learning rule has close to optimal sample complexity. In this paper we seek for a generic optimal learner for multiclass prediction. We start by proving a surprising result: a generic optimal multiclass learner must be improper, namely, it must have the ability to output hypotheses which do not belong to the hypothesis class, even though it knows that all the labels are generated by some hypothesis from the class. In particular, no ERM learner is optimal. This brings back the fundmamental question of "how to learn"? We give a complete answer to this question by giving a new analysis of the one-inclusion multiclass learner of Rubinstein et al (2006) showing that its sample complexity is essentially optimal. Then, we turn to study the popular hypothesis class of generalized linear classifiers. We derive optimal learners that, unlike the one-inclusion algorithm, are computationally efficient. Furthermore, we show that the sample complexity of these learners is better than the sample complexity of the ERM rule, thus settling in negative an open question due to Collins (2005).