[2403.10889] List Sample Compression and Uniform Convergence

Computer Science > Machine Learning arXiv:2403.10889 (cs) [Submitted on 16 Mar 2024 (v1), last revised 4 Mar 2026 (this version, v2)] Title:List Sample Compression and Uniform Convergence Authors:Steve Hanneke, Shay Moran, Tom Waknine View a PDF of the paper titled List Sample Compression and Uniform Convergence, by Steve Hanneke and 2 other authors View PDF HTML (experimental) Abstract: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...