The optimal sample complexity of PAC learning

MaRDI QIDQ2810825zbMATH OpenFDO

Authors Steve Hanneke

Publication date 6 June 2016

Published in Journal of Machine Learning Research (JMLR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.00473, http://jmlr.csail.mit.edu/papers/v17/15-389.html

zbMATH Keywords

learning algorithmminimax analysisPAC learningsample complexitystatistical learning theory

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• The optimal PAC bound for intersection-closed concept classes
• scientific article; zbMATH DE number 1445318
• Sample size lower bounds in PAC learning by Algorithmic Complexity Theory
• Improved bounds on the sample complexity of learning
• Bounding sample size with the Vapnik-Chervonenkis dimension

Cited in

(35)

• Sample size lower bounds in PAC learning by Algorithmic Complexity Theory
• Testing piecewise functions
• On the sample complexity of weak learning
• RotEqNet: rotation-equivariant network for fluid systems with symmetric high-order tensors
• A similarity function for feature pattern clustering and high dimensional text document classification
• The complexity of exact learning of acyclic conditional preference networks from swap examples
• When are epsilon-nets small?
• Decision tree classification with bounded number of errors
• The optimal PAC bound for intersection-closed concept classes
• Tangible reduction in learning sample complexity with large classical samples and small quantum system
• The sample complexity of learning linear predictors with the squared loss
• Statistical learning theory: a pack-based strategy for uncertain feasibility and optimization problems
• scientific article; zbMATH DE number 408770 (Why is no real title available?)
• scientific article; zbMATH DE number 1104347 (Why is no real title available?)
• PAC learning with simple examples
• Optimal quantum sample complexity of learning algorithms
• scientific article; zbMATH DE number 6866335 (Why is no real title available?)
• scientific article; zbMATH DE number 1445318 (Why is no real title available?)
• General feasibility bounds for sample average approximation via Vapnik-Chervonenkis dimension
• Learning time dependent choice
• Shapley homology: topological analysis of sample influence for neural networks
• PAC-MDL bounds.
• Safe multi-agent pathfinding with time uncertainty
• String Matching: Communication, Circuits, and Learning.
• Computational sample complexity and attribute-efficient learning
• PAC-learning with approximate predictors
• Geometric decision procedures and the VC dimension of linear arithmetic theories
• An algorithm for learning representations of models with scarce data
• Property testing of LP-type problems
• Consistency checking problems: a gateway to parameterized sample complexity
• Adversarially robust learning with tolerance
• A sharp lower bound for agnostic learning with sample compression schemes
• Testing support size more efficiently than learning histograms
• Generalized universal inference on risk minimizers
• On statistical learning of simplices: unmixing problem revisited

This page was built for publication: The optimal sample complexity of PAC learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810825)