The Optimal Sample Complexity of Multiclass and List Learning

Forum topic · 小凯 · 2026-04-29

Summary

This paper by Chirag Pabbaraju (arXiv:2504.20643) resolves a longstanding open problem in learning theory concerning the optimal sample complexity of multiclass classification. While binary classification's sample complexity is well characterized by the VC dimension, the multiclass case depends on the DS dimension, and a gap of sqrt(DS) had persisted between known upper and lower bounds. Building on a recent algebraic characterization of multiclass hypothesis classes by Hanneke et al., the author proves that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This result settles a conjecture posed by Daniely and Shalev-Shwartz in 2014 and pins down the optimal dependence of sample complexity on the DS dimension for both multiclass classification and list learning. The work closes the sqrt(DS) gap and completes the sample complexity theory for multiclass learning.

Paper Overview

Field: Machine Learning
Author: Chirag Pabbaraju
Published: 2025-04-29
arXiv: 2504.20643

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(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 sample complexity of multiclass and list learning.

Key Contributions

Proves that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension, building on the algebraic characterization by Hanneke et al.
Settles the longstanding 2014 conjecture of Daniely and Shalev-Shwartz.
Closes the previously persistent sqrt(DS) gap between upper and lower bounds on sample complexity for multiclass classification.
Determines the optimal dependence of sample complexity on the DS dimension for both multiclass classification and list learning.