The Probably Approximately Correct Learning Model in Computational Learning Theory

2025/11/11 by Rocco A. Servedio, Servedio, Rocco A. · 1 voice · 1 citation
#stat.ML #cs.LG

paper · pdf · doi:10.48550/arxiv.2511.08791

Abstract

This survey paper gives an overview of various known results on learning classes of Boolean functions in Valiant's Probably Approximately Correct (PAC) learning model and its commonly studied variants.

Citations

• Learning Behaviors of Automata from Multiplicity and Equivalence Queries

Cited by

• Connecting the concepts of quantum state tomography and molecular representations for machine learning

Discussions

• How did I miss this?! A recent (2025) survey by Rocco Servedio on PAC learning and its variants, and recent results in these learning models: arxiv.org/abs/2511.08791 (Anything by Rocco is worth readi [bsky, 36 points, 1 comments]

Related

• PAC Learning is just Bipartite Matching (Sort of)
• A Theory of Machine Learning
• Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
• Sampling and Learning for Boolean Function
• Combining Models of Approximation with Partial Learning