Skip to content
conftrace_
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)

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization
🐣 Hot Topic Early Bird - pac learning

Authors

Steve Hanneke

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Optimization & Theory > Theory Mathematics & Optimization > Mathematics > Statistics

Keywords

learning theory sample complexity pac learning realizable case
Download PDF

More from JMLR 2016

All JMLR 2016 papers →
OLPS: A Toolbox for On-Line Portfolio Selection
A Bounded p-norm Approximation of Max-Convolution for Sub-Quadratic Bayesian Inference on Additive Factors
Hybrid Orthogonal Projection and Estimation (HOPE): A New Framework to Learn Neural Networks
End-to-End Training of Deep Visuomotor Policies
On Quantile Regression in Reproducing Kernel Hilbert Spaces with the Data Sparsity Constraint
BayesPy: Variational Bayesian Inference in Python