# List Online Classification

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 21 references that are in the map.
- First posted on arXiv 27 Mar 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case](https://mlsanity.com/paper/1902.02244/) (2019)

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

- [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)
- [List Sample Compression and Uniform Convergence](https://mlsanity.com/paper/2403.10889/) (2024)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [Apple Tasting: Combinatorial Dimensions and Minimax Rates](https://mlsanity.com/paper/2310.19064/) (2023)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models](https://mlsanity.com/paper/2602.09402/) (2026)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Learning from Snapshots of Discrete and Continuous Data Streams](https://mlsanity.com/paper/2412.06079/) (2024)
- [PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting](https://mlsanity.com/paper/2605.25678/) (2026)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [Ambiguous Online Learning](https://mlsanity.com/paper/2506.19810/) (2025)
- [The Statistical Benefits of Multiple Responses for Learning from Demonstrations](https://mlsanity.com/paper/2609.33291/) (2026)

## Abstract (arXiv)

We study multiclass online prediction where the learner can predict using a list of multiple labels (as opposed to just one label in the traditional setting). We characterize learnability in this model using the b-ary Littlestone dimension. This dimension is a variation of the classical Littlestone dimension with the difference that binary mistake trees are replaced with (k+1)-ary mistake trees, where k is the number of labels in the list. In the agnostic setting, we explore different scenarios depending on whether the comparator class consists of single-labeled or multi-labeled functions and its tradeoff with the size of the lists the algorithm uses. We find that it is possible to achieve negative regret in some cases and provide a complete characterization of when this is possible. As part of our work, we adapt classical algorithms such as Littlestone's SOA and Rosenblatt's Perceptron to predict using lists of labels. We also establish combinatorial results for list-learnable classes, including an list online version of the Sauer-Shelah-Perles Lemma. We state our results within the framework of pattern classes -- a generalization of hypothesis classes which can represent adaptive hypotheses (i.e. functions with memory), and model data-dependent assumptions such as linear classification with margin.