# The Optimal Sample Complexity of Multiclass and List Learning

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

## Key facts

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

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [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 PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Multiclass Boosting: Simple and Intuitive Weak Learning Criteria](https://mlsanity.com/paper/2307.00642/) (2023)
- [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)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)

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

- [Tight Generalization Bounds for Noiseless Inverse Optimization](https://mlsanity.com/paper/2605.08866/) (2026)
- [Learning to Reason with Curriculum II: Compositional Generalization](https://mlsanity.com/paper/2606.27721/) (2026)
- [The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought](https://mlsanity.com/paper/2607.07423/) (2026)
- [A Rate Separation for Agnostic Direct Sums](https://mlsanity.com/paper/2608.06951/) (2026)
- [Optimistic Rates for Multiclass PAC Learning](https://mlsanity.com/paper/2608.10869/) (2026)
- [When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification](https://mlsanity.com/paper/2608.20480/) (2026)
- [Two Dimensions Govern Agnostic Multiclass Transductive Learning](https://mlsanity.com/paper/2608.25326/) (2026)
- [Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning](https://mlsanity.com/paper/2608.26516/) (2026)
- [Adversarial Online Classification with a Preview](https://mlsanity.com/paper/2608.29503/) (2026)
- [Efficient Active Auditing of Multi-Group Fairness with Bias Probes](https://mlsanity.com/paper/2609.40034/) (2026)
- [The optimal information complexity of VC learning](https://mlsanity.com/paper/2610.10600/) (2026)

## 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.