The Optimal Sample Complexity of PAC Learning
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.
Cite
Text
Hanneke. "The Optimal Sample Complexity of PAC Learning." Journal of Machine Learning Research, 2016.Markdown
[Hanneke. "The Optimal Sample Complexity of PAC Learning." Journal of Machine Learning Research, 2016.](https://mlanthology.org/jmlr/2016/hanneke2016jmlr-optimal/)BibTeX
@article{hanneke2016jmlr-optimal,
title = {{The Optimal Sample Complexity of PAC Learning}},
author = {Hanneke, Steve},
journal = {Journal of Machine Learning Research},
year = {2016},
pages = {1-15},
volume = {17},
url = {https://mlanthology.org/jmlr/2016/hanneke2016jmlr-optimal/}
}