AI RESEARCH
The Optimal Sample Complexity of Multiclass and List Learning
arXiv CS.LG
•
ArXi:2604.24749v1 Announce Type: new 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 shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension.