The History of AI

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

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.

Open in the interactive timeline