# Multiclass Online Learning and Uniform Convergence

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 22 references that are in the map.
- First posted on arXiv 30 Mar 2023.

## Builds on (most cited first, 4 of 4)

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [On statistical learning via the lens of compression](https://mlsanity.com/paper/1610.03592/) (2016)

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

- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models](https://mlsanity.com/paper/2602.09402/) (2026)
- [Online Infinite-Dimensional Regression: Learning Linear Operators](https://mlsanity.com/paper/2309.06548/) (2023)
- [On the Learnability of Multilabel Ranking](https://mlsanity.com/paper/2304.03337/) (2023)
- [Smoothed Online Classification can be Harder than Batch Classification](https://mlsanity.com/paper/2405.15424/) (2024)
- [Learning in Structured Stackelberg Games](https://mlsanity.com/paper/2504.09006/) (2025)
- [Partial Feedback Online Learning](https://mlsanity.com/paper/2601.21462/) (2026)
- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)
- [The Complexity of Sequential Prediction in Dynamical Systems](https://mlsanity.com/paper/2402.06614/) (2024)
- [Universal Multiclass Transductive Online Learning](https://mlsanity.com/paper/2605.30479/) (2026)
- [A Combinatorial Characterization of Supervised Online Learnability](https://mlsanity.com/paper/2307.03816/) (2023)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [Robust Online Learning](https://mlsanity.com/paper/2602.06775/) (2026)
- [Online Prediction of Stochastic Sequences with High Probability Regret Bounds](https://mlsanity.com/paper/2602.16236/) (2026)

## Abstract (arXiv)

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'al, and Shalev-Shwartz (2009) for binary classification, where the best expert has regret zero.