The Optimal Sample Complexity of Multiclass and List Learning

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 had remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of √DS had persisted between the upper and lower bounds on sample complexity.

 

A recent work by Hanneke et al. (2026) shows a novel and elegant algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, in this talk, we will see how the maximum hypergraph density of any multiclass hypothesis class may be upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014), and as a consequence, determines the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.