The Optimal Sample Complexity of PAC Learning
The Optimal Sample Complexity of PAC Learning
Steve Hanneke
2015 · DOI: 10.5555/2946645.2946683
Journal of machine learning research · 170 Citations
TLDR
This work establishes a new upper bound on the number of samples sufficient for PAC learning in the realizable case that matches known lower bounds up to numerical constant factors.
Abstract
This work establishes a new upper bound on the number of samples sufficient for PAC learning in the realizable case. The bound matches known lower bounds up to numerical constant factors. This solves a long-standing open problem on the sample complexity of PAC learning. The technique and analysis build on a recent breakthrough by Hans Simon.