The Optimal Sample Complexity of PAC Learning: The Optimal Realizable Sample Complexity BoundResearch Paper
The sample complexity of a learning problem is the number of labelled examples needed to learn to a prescribed accuracy with a prescribed confidence. In Valiant's probably approximately correct (PAC) model it is the basic quantity of statistical learning theory: it says how much data is necessary and sufficient, as a function of the complexity of the…