PAPERS-13-002 · Paper — A Theory of the Learnable (PAC Learning)

The paper

"A Theory of the Learnable (PAC Learning)" by Leslie Valiant, published in 1984 in Communications of the ACM, is a landmark because it gave machine learning a precise mathematical definition of what it means to learn from examples and set the stage for a theory of learnability.

Before this paper

Before this work, machine learning was mostly a bag of heuristics with no formal way to answer the basic question of when a concept can be learned from examples. Researchers lacked a clear definition of learnability and had no systematic way to ask how many examples would be sufficient. This gap left the field without rigorous guarantees about generalization. Consequently, progress was limited to empirical tricks rather than provable results.

The key idea

Valiant introduced the Probably Approximately Correct (PAC) framework, which says a concept is learnable if an algorithm, given a reasonable number of random examples, can with high probability output a hypothesis whose error is small. The terms "probably" and "approximately" are quantified by two parameters: confidence delta and accuracy epsilon. This turns learning into a question about sample and computational complexity rather than intuition alone.

How it works

The learner first draws examples from an unknown but fixed distribution over inputs, each labeled by the target concept. It then runs an algorithm that searches within a predefined hypothesis class for a hypothesis that fits the observed data. The algorithm must guarantee that, for any desired epsilon (target error) and delta (failure probability), the number of examples needed grows only polynomially in 1/epsilon, 1/delta, and the size of the problem. After processing the samples, the algorithm outputs a hypothesis. With probability at least 1‑delta, this hypothesis has error less than epsilon on future examples drawn from the same distribution.

See it — probably approximately correct

flowchart TD
  A["Draw samples<br/>from a distribution"] --> B["Pick a hypothesis<br/>that fits them"]
  B --> C["Enough samples =><br/>low error"]
  C --> D["Probably (1-delta)<br/>Approximately (eps)"]

What they showed

Valiant showed that a concept class is PAC‑learnable exactly when its sample complexity is polynomial in 1/epsilon, 1/delta, and the problem size, providing a rigorous complexity‑theoretic foundation for learning. He demonstrated that efficient learning is possible only for those classes that meet this polynomial bound, linking learnability to computational feasibility.

What it changed

The paper founded computational learning theory, giving the field a precise language for generalization guarantees. It earned Valiant the 2010 Turing Award and introduced the vocabulary—PAC learning, sample complexity, and generalization bounds—that still underpins modern machine‑learning theory. By connecting learning to complexity theory, it clarified when efficient learning can be expected. Next: VC Dimension.

The one-line takeaway

PAC learning shows that learnability is a matter of polynomial sample and computational resources.

Read it / meet it

Reading the original paper reveals the elegant simplicity of the PAC framework and its lasting influence. Today you encounter its legacy in every textbook on learning theory and in modern generalization bounds that trace back to Valiant’s ideas.