Historical milestone · 1984
Probably Approximately Correct learning
Reviewed through September 18, 2026
1984 · Historical milestone
Probably Approximately Correct learning
- Era
- 1980s
- Theme
- Machine-learning foundations
- Evidence form
- Defined learnability by sample complexity, computational efficiency, accuracy, and confidence under a distribution
- School / paradigm
- Computational learning theory
- Institution / context
- Harvard University
- Researchers
- Leslie Valiant
Researcher index
Leslie Valiant
Computational learning theory · Harvard
PAC learning
Why it still matters. Defined learnability through accuracy, confidence, samples, and computation.
Representative source for this researcher — not necessarily the source of this milestone: https://doi.org/10.1145/1968.1972 (opens in a new tab)
School of thought
Computational learning theory
Matched on school name.
Learning should be defined by explicit assumptions about samples, computational resources, accuracy, confidence, and adversaries.
Critique. Worst-case abstractions may not predict empirical deep-learning behavior or open-ended environments.
Modern descendants. Generalization, robust training, benchmark design, data requirements, and formal assurance.
Understand
Plain-language record, transferred from the reviewed source module.
Theory or experimental setup. Put generalization on a formal footing and linked learning to complexity theory.
Result / historical claim. Classical assumptions can be far from modern deep learning; worst-case guarantees may be loose in practice.
Apply
Professional implication, only where the reviewed record states one.
The checked-in record does not state a separate professional application for this entry. The topic page places it in the wider research lineage: .
Verify
Evidence status, stated limitations, and the external sources this record actually carries.
Evidence form. Defined learnability by sample complexity, computational efficiency, accuracy, and confidence under a distribution
Limitation / debate. Sample efficiency, generalization bounds, learnability, and evaluation under specified distributions.
Source status. This milestone row does not carry a primary-source URL in the approved export, and we do not have a verified link for it in our own research. We do not guess one.
No primary-source URL is recorded for this entry in our reviewed data. Rather than manufacture a citation, we link the Implement Agentic research page that carries the record.
Reproduce
A reproduction tutorial is linked only when one exists for this exact record.
A reproduction tutorial is not yet available for this entry. The closest reviewed material is .
Cite or share
APA-like: This historical record carries a year only, and no author or publisher of record in the checked-in data. An APA reference would have to invent that metadata.
BibTeX: BibTeX requires an author and publication venue. Historical lineage entries store a narrative record and its source link, not structured authorship, so the field would be fabricated.