Multiclass Online Learning and Uniform Convergence
Preprint
Abstract
We study multiclass classification in the agnostic adversarial online learning setting. As our main result, we prove that any multiclass concept class is agnostically learnable if and only if its Littlestone dimension is finite. This solves an open problem studied by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011,2015) who handled the case when the number of classes (or labels) is bounded. We also prove a separation between online learnability and online uniform convergence by exhibiting an easy-to-learn class whose sequential Rademacher complexity is unbounded. Our learning algorithm uses the multiplicative weights algorithm, with a set of experts defined by executions of the Standard Optimal Algorithm on subsequences of size Littlestone dimension. We argue that the best expert has regret at most Littlestone dimension relative to the best concept in the class. This differs from the well-known covering technique of Ben-David, Pál, and Shalev-Shwartz (2009) for binary classification, where the best expert has regret zero.Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Adversarial Laws of Large Numbers and Optimal Regret in Online ClassificationSIAM Journal on Computing, 2023
- Weak Convergence and Empirical ProcessesJournal of the American Statistical Association, 1997
- Characterizations of Learnability for Classes of {0, ..., n)-Valued FunctionsJournal of Computer and System Sciences, 1995
- Sharper Bounds for Gaussian and Empirical ProcessesThe Annals of Probability, 1994