mlsanityData to 7 Oct 2026

The Optimal Sample Complexity of Multiclass and List Learning

arXiv 2604.24749 ↗First posted 27 Apr 2026cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of √DS has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 11 of its 23 references that are in the map. First posted on arXiv 27 Apr 2026.

Builds on

11 of 23 references.

References · 11

  1. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  2. 2022A Characterization of Multiclass Learnabilitycited by 66
  3. 2014Optimal Learners for Multiclass Problemscited by 65
  4. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  5. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  6. 2022A Characterization of List Learnabilitycited by 22
  7. 2023List Online Classificationcited by 16
  8. 2023Multiclass Boosting: Simple and Intuitive Weak Learning Criteriacited by 11
  9. 2025Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Backcited by 9
  10. 2024A Characterization of List Regressioncited by 6
  11. 2026An Optimal Sauer Lemma Over k-ary Alphabetscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 8.

8 papers.

  1. 2026Tight Generalization Bounds for Noiseless Inverse Optimizationcited by 4
  2. 2026The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thoughtcited by 0
  3. 2026A Rate Separation for Agnostic Direct Sumscited by 0
  4. 2026Optimistic Rates for Multiclass PAC Learningcited by 0
  5. 2026When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classificationcited by 0
  6. 2026Two Dimensions Govern Agnostic Multiclass Transductive Learningcited by 0
  7. 2026Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learningcited by 0
  8. 2026Adversarial Online Classification with a Previewcited by 0