# The Optimal Sample Complexity of Multiclass and List Learning

Source: [The Optimal Sample Complexity of Multiclass and List Learning](<https://www.sota2.com/research/paper/69f03f6055a3c32af89fa41c>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-08-15T05:00:08.502Z

Authors: Chirag Pabbaraju

Published: 2026-04-27T17:54:12.000Z

## Abstract

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 $\\sqrt{\\text{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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [List Learning on List Learning (realizable)](<https://www.sota2.com/research/sota/list-learning-on-list-learning-realizable.md>): List Learning; List Learning (realizable); Sample Complexity: 1.

- [List Learning on List Learning Agnostic](<https://www.sota2.com/research/sota/list-learning-on-list-learning-agnostic.md>): List Learning; List Learning Agnostic; Sample Complexity: 4.

- [Multiclass Learning Realizable setting](<https://www.sota2.com/research/sota/multiclass-learning-realizable-setting.md>): Multiclass Learning; Multiclass Learning Realizable setting; Sample Complexity: 1.

- [Sample Complexity Analysis on Multiclass Learning Agnostic Setting](<https://www.sota2.com/research/sota/sample-complexity-analysis-on-multiclass-learning-agnostic-setting.md>): Multiclass Learning; Multiclass Learning Agnostic; Sample Complexity Bound: 1.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2604.24749>)

[PDF](<https://arxiv.org/pdf/2604.24749.pdf>)