mlsanityData to 14 Oct 2026

A Characterization of List Learnability

arXiv 2211.04956 ↗First posted 7 Nov 2022stat.ML cs.DS cs.LGcited by 22

Not on the map. Why?

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.

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

14 of 35 references.

References · 14

  1. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
  2. 2016Learning from Untrusted Datacited by 90
  3. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  4. 2022A Characterization of Multiclass Learnabilitycited by 67
  5. 2014Optimal Learners for Multiclass Problemscited by 65
  6. 2020A Theory of Universal Learningcited by 60
  7. 2021A Theory of PAC Learnability of Partial Concept Classescited by 60
  8. 2019List-Decodable Linear Regressioncited by 42
  9. 2019List Decodable Learning via Sum of Squarescited by 37
  10. 2020List-Decodable Mean Estimation via Iterative Multi-Filteringcited by 18
  11. 2022Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classescited by 14
  12. 2016On statistical learning via the lens of compressioncited by 10
2 more
  1. 2014Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimensioncited by 6
  2. 2020List Learning with Attribute Noisecited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 2; 2025: 6; 2026: 9.

22 papers.

Sort:

By area:

  1. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  2. 2023List Online Classificationcited by 16
  3. 2023List and Certificate Complexities in Replicable Learningcited by 13
  4. 2022The One-Inclusion Graph Algorithm is not Always Optimalcited by 11
  5. 2023Multiclass Boosting: Simple and Intuitive Weak Learning Criteriacited by 11
  6. 2026The Optimal Sample Complexity of Multiclass and List Learningcited by 11
  7. 2024List Sample Compression and Uniform Convergencecited by 10
  8. 2025A Characterization of List Language Identification in the Limitcited by 9
  9. 2025Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Backcited by 9
  10. 2024A Characterization of List Regressioncited by 6
  11. 2025From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewardscited by 4
  12. 2026An Optimal Sauer Lemma Over k-ary Alphabetscited by 4
10 more
  1. 2026Simultaneous Blackwell Approachability and Applications to Multiclass Omnipredictioncited by 3
  2. 2025Private List Learnability vs. Online List Learnabilitycited by 2
  3. 2026PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Settingcited by 2
  4. 2026The Sample Complexity of Multiclass and Sparse Contextual Banditscited by 1
  5. 2025Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functionscited by 0
  6. 2025High-Accuracy List-Decodable Mean Estimationcited by 0
  7. 2026(α,β)-Stability for Boosting Vector-Valued Predictioncited by 0
  8. 2026Optimistic Rates for Multiclass PAC Learningcited by 0
  9. 2026Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenoncited by 0
  10. 2026The Statistical Benefits of Multiple Responses for Learning from Demonstrationscited by 0