#machine learning
Apr 2026
The Optimal Sample Complexity of Multiclass and List Learning
It is shown that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension, which proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014) and determines the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.
Chirag Pabbaraju
· arXiv.org · 7 citations
· ⚡4