# List Sample Compression and Uniform Convergence

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 22 references that are in the map.
- First posted on arXiv 16 Mar 2024.

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

- [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)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Loss Functions for Top-k Error: Analysis and Insights](https://mlsanity.com/paper/1512.00486/) (2015)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Multiclass Learnability Does Not Imply Sample Compression](https://mlsanity.com/paper/2308.06424/) (2023)
- [Online Learning and Disambiguations of Partial Concept Classes](https://mlsanity.com/paper/2303.17578/) (2023)

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

- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (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)
- [Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks](https://mlsanity.com/paper/2410.13577/) (2024)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [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)

## Abstract (arXiv)

List learning is a variant of supervised classification where the learner outputs multiple plausible labels for each instance rather than just one. We investigate classical principles related to generalization within the context of list learning. Our primary goal is to determine whether classical principles in the PAC setting retain their applicability in the domain of list PAC learning. We focus on uniform convergence (which is the basis of Empirical Risk Minimization) and on sample compression (which is a powerful manifestation of Occam's Razor). In classical PAC learning, both uniform convergence and sample compression satisfy a form of `completeness': whenever a class is learnable, it can also be learned by a learning rule that adheres to these principles. We ask whether the same completeness holds true in the list learning setting. We show that uniform convergence remains equivalent to learnability in the list PAC learning setting. In contrast, our findings reveal surprising results regarding sample compression: we prove that when the label space is Y=0,1,2, then there are 2-list-learnable classes that cannot be compressed. This refutes the list version of the sample compression conjecture by Littlestone and Warmuth (1986). We prove an even stronger impossibility result, showing that there are 2-list-learnable classes that cannot be compressed even when the reconstructed function can work with lists of arbitrarily large size. We prove a similar result for (1-list) PAC learnable classes when the label space is unbounded. This generalizes a recent result by arXiv:2308.06424.