# A Characterization of List Learnability

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 7 Nov 2022.

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

- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [List-Decodable Mean Estimation via Iterative Multi-Filtering](https://mlsanity.com/paper/2006.10715/) (2020)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [On statistical learning via the lens of compression](https://mlsanity.com/paper/1610.03592/) (2016)
- [Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension](https://mlsanity.com/paper/1412.6265/) (2014)
- [List Learning with Attribute Noise](https://mlsanity.com/paper/2006.06850/) (2020)

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

- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (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)
- [List Sample Compression and Uniform Convergence](https://mlsanity.com/paper/2403.10889/) (2024)
- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [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)
- [Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions](https://mlsanity.com/paper/2510.08382/) (2025)
- [High-Accuracy List-Decodable Mean Estimation](https://mlsanity.com/paper/2511.17822/) (2025)
- [(α,β)-Stability for Boosting Vector-Valued Prediction](https://mlsanity.com/paper/2602.18866/) (2026)
- [Optimistic Rates for Multiclass PAC Learning](https://mlsanity.com/paper/2608.10869/) (2026)
- [Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon](https://mlsanity.com/paper/2609.29694/) (2026)
- [The Statistical Benefits of Multiple Responses for Learning from Demonstrations](https://mlsanity.com/paper/2609.33291/) (2026)

## Abstract (arXiv)

A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work we consider list PAC learning where the goal is to output a list of k predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to k-list learn a hypothesis class? We completely characterize k-list learnability in terms of a generalization of DS dimension that we call the k-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is k-list learnable if and only if the k-DS dimension is finite.