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.

References in corpus (1)

• Refined Error Bounds for Several Learning Algorithms

Cited by in corpus (23)

• Combating Reinforcement Learning's Sisyphean Curse with Intrinsic Fear
• Optimal Quantum Sample Complexity of Learning Algorithms
• Quantum statistical query learning
• Quantum Coupon Collector
• Binary Classification with Classical Instances and Quantum Labels
• Analysis on the Nonlinear Dynamics of Deep Neural Networks: Topological Entropy and Chaos
• Tight Bounds for Collaborative PAC Learning via Multiplicative Weights
• Proper Learning, Helly Number, and an Optimal SVM Bound
• Optimal learning via local entropies and sample compression
• The Power of Comparisons for Actively Learning Linear Classifiers
• Refined Error Bounds for Several Learning Algorithms
• Robust learning under clean-label attack
• Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
• Effective Parallelisation for Machine Learning
• A Survey on Large-scale Machine Learning
• Beyond Dropout: Feature Map Distortion to Regularize Deep Neural Networks
• Decidability of Sample Complexity of PAC Learning in finite setting
• The information-theoretic value of unlabeled data in semi-supervised learning
• Bounded Memory Active Learning through Enriched Queries
• When are epsilon-nets small?
• Testing Piecewise Functions
• A New Lower Bound for Agnostic Learning with Sample Compression Schemes
• Shapley Homology: Topological Analysis of Sample Influence for Neural Networks