The Sample Complexity of Multiclass Learning

21 concepts11 papers2 proposals

In binary classification, statistical learning theory enjoys a beautiful symmetry. A single metric—the Vapnik-Chervonenkis (VC) dimension—perfectly characterizes whether a hypothesis class can be learned. If the VC dimension is finite, the class is learnable, and the simplest possible algorithmic template, Empirical Risk Minimization (ERM), achieves optimal sample complexity.

However, when we transition from two labels to multiple labels, this elegant framework shatters. As Daniely et al. demonstrated, moving to multiclass classification introduces fundamental gaps between what is learnable, how many samples are required, and which algorithms can succeed. Understanding this research direction requires unpacking why binary intuition fails and how new combinatorial dimensions attempt to restore order.

The Failure of Empirical Risk Minimization

Why does multiclass learning break the binary paradigm? The core issue begins with the algorithm itself. In binary classification, any ERM learner (an algorithm that simply picks a hypothesis minimizing training error) is guaranteed to generalize well if the class is learnable.

In the multiclass setting, this is no longer true. Daniely et al. proved a startling result: ERM is not the gold standard for multiclass learning. A generic ERM can fail entirely on problems that are otherwise perfectly learnable by more sophisticated algorithms. To achieve optimal sample complexity, a learner must often be improper—meaning it must output a hypothesis that lies outside the target hypothesis class itself, such as the one-inclusion graph algorithm.

This introduces a "properness barrier." As explored by Asilis et al., there is currently no universal metric that characterizes the proper learnability of multiclass classes, making it difficult to predict when restricting a model to its own class renders a problem impossible. Even aggregating proper learners into ensembles, as studied by Asilis et al., reveals a strict divide between problems that can be solved via ensembling and those that require fundamentally improper approaches.

The Search for the Multiclass VC Dimension

If the VC dimension is insufficient for multiclass spaces, what replaces it? Historically, researchers proposed several combinatorial generalizations. The most prominent is the Natarajan dimension, which measures the complexity of a multiclass function class by evaluating its ability to "shatter" combinations of labels, a metric for which Jin established upper bounds across decision trees and neural networks. Another common metric is the Graph dimension.

However, these dimensions often yield conflicting predictions. Daniely et al. showed a significant sample complexity gap between optimal and suboptimal learners: a suboptimal learner's sample requirements might scale with the Graph dimension, whereas an optimal learner requires far fewer samples. For years, it remained an open question which mathematical property truly governed the fundamental data requirements of multiclass spaces, as existing dimensions failed to provide tight bounds (Daniely et al.).

The DS Dimension and the Super-Linear Gap

The search for a definitive metric culminated in a breakthrough by Brukhim et al.. The authors proved that multiclass PAC learnability is fully characterized by the finiteness of the DS (Daniely-Shalev-Shwartz) dimension, finally resolving the search for a true successor to the VC dimension for problems with unbounded label sets.

Yet, even with the true dimension identified, a profound structural gap remains between binary and multiclass learning. In binary classification, the number of samples required scales linearly with the VC dimension. In contrast, Brukhim et al. showed that multiclass upper bounds exhibit a super-linear dependence on the DS dimension—specifically scaling to the power of $d^{1.5}$. Whether this higher-order dependency is an unavoidable tax of multiclass learning or an artifact of current proof techniques remains an active open question.

Narrowing the Bounds

To close these theoretical gaps, researchers are actively refining upper and lower bounds. For instance, Hanneke et al. significantly narrowed the sample complexity upper bound by reducing multiple logarithmic factors down to a single $\log(1/\epsilon)$ factor, bringing the field closer to a tight characterization.

Simultaneously, this framework is being pushed beyond standard PAC boundaries:

  • Alternative Frameworks: Kalavasis et al. note that existing tree-based dimensions require further refinement to fully capture how multiclass error rates decay when moving beyond worst-case distribution assumptions.
  • Multi-label Extensions: Samei et al. extended these dimension-based bounds to multi-label settings, proving that a sample compression size equal to the dimension is always possible for maximum classes.
  • Robustness: Xu et al. demonstrated that standard dimensions fail under adversarial conditions, necessitating new metrics like the Adversarial Natarajan and Adversarial Graph dimensions to characterize robust multiclass learnability.

Ultimately, understanding the multiclass sample complexity gap is about moving away from computationally prohibitive, heavy mathematical constructs (Asilis et al.) toward a clean, unified theory of how models scale when forced to choose among many worlds instead of just two.

Key Foundational Work

Multiclass Learnability and the ERM principle (2011) — contributed 4 concept elements to this direction.
Optimal learners for multiclass problems (2014) — contributed 3 concept elements to this direction.
Sample Compression for Multi-label Concept Classes (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multiclass_sample_complexity_gap_e63b7a2f,
  title = {multiclass sample complexity gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiclass-sample-complexity-gap/rdr_e63b7a2f36c447e18fdd0804ff29c414},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_multiclass_sample_complexity_gap_e63b7a2f_v1,
  title = {multiclass sample complexity gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiclass-sample-complexity-gap/rdr_e63b7a2f36c447e18fdd0804ff29c414/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake