The Optimal Sample Complexity of Multiclass and List Learning
Chirag Pabbaraju's paper resolves a 2014 conjecture by proving the optimal sample complexity for multiclass and list learning. It closes the gap between upper and lower bounds, showing complexity scales linearly with the DS dimension. This result makes learning in data-scarce fields, like medical diagnosis, more theoretically and practically feasible.