2016
JMLR
JMLR 2016
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. [abs] [ pdf ][ bib ] © JMLR 2016. (edit, beta)
🐣
Hot Topic Early Bird
— sample complexity
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Data Science & Analytics, Deep Learning, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics
🌉
Interdisciplinary Bridge
— Machine Learning and Mathematics & Optimization