Probably Approximately Correct learning (PAC learning)

E345811

computational learning theory framework learning theory model theoretical framework in machine learning

Probably Approximately Correct (PAC) learning is a foundational framework in computational learning theory that formalizes what it means for an algorithm to efficiently learn a concept from examples with high probability and small error.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (9)

Label	Occurrences
"A Theory of the Learnable"	2
Gold’s theorem in language learnability	1
PAC learning	1
PAC learning framework	1
PAC learning with noise	1
Probably Approximately Correct	1
Probably Approximately Correct learning (PAC learning) canonical	1
Probably Approximately Correct learning model	1
“A Theory of the Learnable”	1

How this entity was disambiguated

This entity first appeared as the object of triple T3308894 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Probably Approximately Correct learning (PAC learning)
Context triple: [Leslie Valiant, knownFor, Probably Approximately Correct learning (PAC learning)]

A. P, NP, and NP-Completeness: The Basics of Complexity Theory
"P, NP, and NP-Completeness: The Basics of Complexity Theory" is a foundational textbook by Oded Goldreich that introduces the core concepts, problems, and techniques of computational complexity theory, with a focus on the classes P, NP, and NP-complete problems.
B. Statistical Decision Functions
Statistical Decision Functions is a foundational work in decision theory and statistics that systematically develops the theory of optimal decision-making under uncertainty.
C. Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
D. Bayesian Occam factor
The Bayesian Occam factor is a term in Bayesian model comparison that automatically penalizes overly complex models by integrating over their larger parameter spaces, thereby implementing Occam’s razor in probabilistic inference.
E. Interactive Proofs and the Hardness of Approximating Cliques
"Interactive Proofs and the Hardness of Approximating Cliques" is a seminal theoretical computer science paper that introduced powerful interactive proof techniques to show that finding near-maximum cliques in graphs is computationally intractable to approximate within strong bounds.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Probably Approximately Correct learning (PAC learning)
Target entity description: Probably Approximately Correct (PAC) learning is a foundational framework in computational learning theory that formalizes what it means for an algorithm to efficiently learn a concept from examples with high probability and small error.

A. P, NP, and NP-Completeness: The Basics of Complexity Theory
"P, NP, and NP-Completeness: The Basics of Complexity Theory" is a foundational textbook by Oded Goldreich that introduces the core concepts, problems, and techniques of computational complexity theory, with a focus on the classes P, NP, and NP-complete problems.
B. Statistical Decision Functions
Statistical Decision Functions is a foundational work in decision theory and statistics that systematically develops the theory of optimal decision-making under uncertainty.
C. Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
D. Bayesian Occam factor
The Bayesian Occam factor is a term in Bayesian model comparison that automatically penalizes overly complex models by integrating over their larger parameter spaces, thereby implementing Occam’s razor in probabilistic inference.
E. Interactive Proofs and the Hardness of Approximating Cliques
"Interactive Proofs and the Hardness of Approximating Cliques" is a seminal theoretical computer science paper that introduced powerful interactive proof techniques to show that finding near-maximum cliques in graphs is computationally intractable to approximate within strong bounds.
F. None of above. chosen

Statements (50)

Predicate	Object
instanceOf	computational learning theory framework ⓘ learning theory model ⓘ theoretical framework in machine learning ⓘ
appliesTo	binary classification ⓘ multiclass classification ⓘ some regression settings ⓘ
assumes	access to labeled examples ⓘ i.i.d. examples from an unknown distribution ⓘ
confidenceParameterSymbol	delta ⓘ
contrastsWith	exact learning models ⓘ heuristic, non-probabilistic learning notions ⓘ
coreConcept	agnostic case ⓘ concept class ⓘ distribution over instances ⓘ generalization error ⓘ hypothesis class ⓘ learning algorithm ⓘ realizable case ⓘ sample complexity ⓘ target concept ⓘ
definesProperty	PAC learnability ⓘ efficient learnability ⓘ
errorParameterSymbol	epsilon ⓘ
field	computational learning theory ⓘ linked to: Computational Learning Theory
formalizes	learning from examples ⓘ learning with high probability and small error ⓘ notion of efficient learnability ⓘ
goal	achieve confidence at least 1 - delta ⓘ find hypothesis with error at most epsilon ⓘ
hasAbbreviation	PAC learning ⓘ
hasVariant	PAC learning with noise ⓘ linked to: Probably Approximately Correct learning (PAC learning) agnostic PAC learning ⓘ distribution-free PAC learning ⓘ distribution-specific PAC learning ⓘ
influenced	VC dimension theory ⓘ active learning frameworks ⓘ boosting algorithms ⓘ statistical learning theory ⓘ
introducedBy	Leslie Valiant ⓘ
introducedIn	"A Theory of the Learnable" ⓘ linked to: Probably Approximately Correct learning (PAC learning)
publicationYear	1984 ⓘ
publishedIn	Communications of the ACM ⓘ
relatedTo	VC dimension ⓘ empirical risk minimization ⓘ uniform convergence ⓘ
requires	polynomial sample complexity in 1/epsilon, 1/delta, and size parameters ⓘ polynomial-time learning algorithm for efficient PAC learning ⓘ
usedFor	analyzing learnability of concept classes ⓘ characterizing when learning is computationally feasible ⓘ deriving bounds on sample complexity ⓘ