Valiant's PAC learning
Era 3 · From the expert boom to the statistical turn (1980–2011) › Statistical learning and probabilistic models
- Lineage
- Data and learning
- Kind
- Theory
Who
Harvard University
What happened
Leslie Valiant of Harvard University publishes "A Theory of the Learnable" in Communications of the ACM, defining what it means for a machine to learn a concept from examples.
Why it mattered
Probably approximately correct (PAC) learning gives machine learning a mathematical theory: how many examples and how much computation it takes to learn well.
The full story
In the early 1980s machine learning had programs and experiments but no precise definition of what learning was. Valiant, a specialist in the theory of computation, set out to treat learning the way complexity theory treats computation: as something that can be measured.
The definition asks for two concessions. The result need not be perfect, only approximately correct, with a small error on new cases. And it need not always work, only with high probability, because the examples arrive at random and may be unrepresentative. A class of concepts is learnable if there is an algorithm that, with a reasonable number of examples and computational steps, reaches that error level with that probability.
The framework made it possible to prove what can and cannot be learned efficiently, and it gave statistics and theoretical computer science a common language. A question posed within it, whether a learner slightly better than chance can be turned into a highly accurate one, gave rise to boosting.
Valiant received the 2010 Turing Award, announced in 2011. The ACM cited PAC theory first, crediting it with helping to create computational learning theory.
Leads to
AdaBoost (1995)
Documented direct influence
Boosting answers a question posed within the PAC framework: whether a learner slightly better than chance can be turned into a highly accurate one
Sources
Original source
Scholarship and context
How to cite
“Valiant's PAC learning.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/valiant-pac-learning
This entry was last reviewed on November 13, 2026.