Summary
While the optimal sample complexity of binary classification in terms of the VC dimension is well established, the optimal sample complexity of multiclass classification has remained an open problem. The appropriate complexity measure for multiclass classification is the DS dimension, and despite significant effort, a gap of sqrt(DS) has persisted between the upper and lower bounds on sample complexity. Building on a recent algebraic characterization of multiclass hypothesis classes by Hanneke et al., this paper by Chirag Pabbaraju proves that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This resolves a longstanding conjecture of Daniely and Shalev-Shwartz (2014) and settles the optimal dependence of sample complexity on the DS dimension for both multiclass and list learning. The paper was posted to arXiv on April 29, 2025 under identifier 2504.20643.
Paper Overview
Research area: Machine Learning
Author: Chirag Pabbaraju
Published: 2025-04-29
arXiv: 2504.20643
Summary
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 in terms of the DS dimension.
---
*Auto-collected on 2026-04-29*
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/177618878