Probably approximately correct learning, usually called PAC learning, is a mathematical framework for specifying when a learning procedure can infer a reliable prediction rule from a finite collection of examples. Introduced by Leslie Valiant in 1984, it gives a precise meaning to successful learning: with high probability over the examples supplied, the learner must produce a hypothesis whose prediction error is small. “Probably” refers to the confidence in this outcome, while “approximately correct” refers to the tolerated error on future examples.
The framework is central to machine learning because it separates several questions that empirical performance alone does not answer: whether the available observations contain enough information, how many observations are required, and whether a computationally efficient algorithm can extract that information. It connects supervised learning, statistics, and computational complexity through explicit assumptions about sampling, prediction, and computational resources.
Classical PAC learning concerns binary concepts learned from independently sampled, correctly labeled examples. Its extensions accommodate noisy labels, competing hypothesis classes, real-valued losses, and alternative sources of information. The resulting theory explains both the possibility of generalization and important limits on what a learning guarantee actually establishes.
The learning problem and its quantifiers
In the classical setting, an instance space contains the objects to be classified. A concept is a function , and a concept class is a specified collection of possible target functions. For example, instances might be points on a line and concepts might indicate whether a point lies above a threshold. A hypothesis class contains the functions that the learner may output; it need not equal .
An unknown probability distribution determines which instances occur. The learner receives training data
where the are independent draws from . This is the realizable setting: the labels are generated by a target belonging to the stipulated concept class. For a hypothesis , its population error is
This error concerns fresh draws from the distribution, not merely disagreements on the observed sample.
A learner satisfies a PAC guarantee if, for every allowed target , every allowed distribution , and all accuracy and confidence parameters , sufficiently many examples ensure
Here is the output of the learning algorithm, and the probability includes internal randomness when the algorithm is randomized. A sample bound must work uniformly over the targets and distributions covered by the definition. The learner does not normally know , and it is not permitted to select an easier distribution after observing the data.
The two probability levels are essential. The inner quantity measures the frequency of prediction errors for a fixed output hypothesis. The outer probability measures how often the training process produces an acceptable hypothesis. Thus and mean that at least 99 percent of independent executions produce a classifier with population error at most 5 percent. They do not mean that each individual prediction carries a 99 percent probability of correctness.
The standard distribution-free definition requires the guarantee for every on the instance space. Distribution-specific learning instead restricts , for example to a known uniform distribution. In statistical discussions, PAC learnability often refers principally to the existence of a finite sample bound. In computational learning theory, efficient PAC learnability additionally requires polynomial bounds on sample use and running time, measured against appropriate representation parameters, , and .
Finite hypothesis classes and consistency
The simplest PAC argument concerns a finite hypothesis class containing a correct target. A hypothesis is consistent with a sample if it makes no errors on the observed labels. Suppose a particular hypothesis has true error greater than . Because examples are independent, the probability that all observations miss its error region is at most
A bad hypothesis can therefore appear perfect on a small sample, but its chance of doing so declines exponentially with sample size.
There may be many bad hypotheses, and the learning procedure can select among them after seeing the sample. The union bound controls this selection effect:
where
is empirical error. Consequently, every consistent output is accurate with confidence at least whenever
The argument does not depend on how a consistent hypothesis is found.
This bound shows why class size enters logarithmically rather than linearly. If every hypothesis can be encoded by a distinct binary string of a fixed length , then , giving the sufficient condition
This counting argument is an early form of the connection between learning and description length. A shorter available representation can support a stronger generalization guarantee, provided the encoding scheme is fixed independently of the sample or its selection is properly accounted for.
Boolean conjunctions provide a concrete example. For Boolean variables, consider conjunctions in which each variable is absent, appears positively, or appears negatively. There are syntactic choices, apart from optional conventions for the identically false concept. A realizable learner can begin with all literals and remove any literal contradicted by a positive example. The remaining conjunction includes every positive example. Since literals belonging to the target are never removed, the result also excludes every negative example. The finite-class argument therefore gives a sample requirement of order
Consistency is a statistical property, not a universal computational solution. For some representations, finding a consistent member is difficult even when one is known to exist. It also becomes unsuitable when labels contain contradictions or when no hypothesis in the class fits perfectly. Nevertheless, the finite-class proof establishes a recurring principle: fitting the observed data is informative only after accounting for how many alternative explanations the learning procedure could have selected.
Infinite classes and Vapnik–Chervonenkis dimension
Counting hypotheses is insufficient for many basic learning problems. The class of thresholds on the real line is uncountable, although it has a simple learning rule. What matters is not the number of functions on the entire instance space, but the diversity of labelings they can produce on finite samples. The Vapnik–Chervonenkis dimension, or VC dimension, measures this diversity for binary-valued classes.
A class shatters a finite set of points if every binary labeling of those points is realized by some member of . Its VC dimension is the largest size of a shattered set, or infinity if arbitrarily large finite sets can be shattered. Thresholds have VC dimension 1. They can label a single point either way, but cannot label two ordered points as positive followed by negative. Intervals on the line have VC dimension 2: two points can receive every labeling, whereas three ordered points cannot receive the labeling positive–negative–positive.
The growth function is the maximum number of distinct labelings that induces on points. The Sauer–Shelah lemma states that, for finite VC dimension ,
When , this is at most . Thus a class may contain infinitely many functions while producing only polynomially many distinct behaviors on any finite sample. This bound replaces finite cardinality in generalization arguments.
A standard realizable VC bound ensures that a consistent learner succeeds with
examples. Subject to standard measurability conditions, a binary class is distribution-free PAC learnable exactly when its VC dimension is finite. The qualification matters because arbitrary collections of functions can present measurability difficulties; conventional geometric and algorithmically represented classes generally satisfy the regularity assumptions used in the theory.
VC dimension often differs substantially from the number of available hypotheses or the precision of their parameters. Affine halfspaces in , for example, have VC dimension , although their coefficients range over infinitely many real values. Conversely, a class that can independently assign labels to arbitrarily many points has infinite VC dimension and lacks a distribution-free finite-sample PAC guarantee.
The logarithmic factor in the standard consistent-learner bound is not always necessary. More refined, potentially improper learning constructions achieve general realizable upper bounds of order
This is the optimal general dependence in the worst case. It should not be confused with a statement that every consistent learning rule, or every proper learner for every class, achieves the optimal rate.
Agnostic learning and noisy observations
Realizability is a strong assumption. Labels may be noisy, the chosen representation may omit relevant information, or the underlying relationship may not belong to the hypothesis class. Agnostic learning removes the requirement that a single target in generates all labels. Instead, examples are drawn independently from an arbitrary distribution on .
For binary classification, population risk becomes
The learner is compared with the best achievable risk within its designated class:
An agnostic PAC guarantee requires
The tolerance now bounds excess risk, not total error. If every classifier in the class has error at least 20 percent, an excess-risk guarantee of 1 percent promises an output with error at most 21 percent, not 1 percent.
Empirical risk minimization chooses a hypothesis minimizing observed average loss. Its statistical justification often uses uniform convergence: with high probability, empirical and population risks are close simultaneously for every hypothesis. For a finite class and binary loss, Hoeffding’s inequality gives
If this uniform deviation is at most , an exact empirical minimizer has excess risk at most . Approximate optimization adds the corresponding empirical optimization error.
For VC classes, the optimal general agnostic sample scale is
with matching worst-case lower bounds up to constants in standard parameter regimes. Compared with realizable learning, the general dependence on accuracy changes from approximately to . Distinguishing two hypotheses with very similar nonzero risks can require many observations because random fluctuations may obscure their small difference.
Specific noise assumptions can permit sharper conclusions. In classification noise, labels are independently flipped with a fixed probability . More general bounded-noise models allow the flip probability to vary with the instance while remaining uniformly below one half. Other assumptions control how frequently instances lie near an ambiguous decision boundary. Such conditions can produce faster statistical rates, but they impose structure absent from fully agnostic learning. Agnostic guarantees remain relative to the chosen class; they do not establish that the class itself captures the best possible predictor.
Sample efficiency, computation, and representation
A sample-complexity theorem answers how much information is sufficient, but it does not necessarily provide a practical algorithm. A learner could enumerate all hypotheses, test each against the sample, and eventually return an acceptable one. For a finite class this may prove learnability while requiring time exponential in the input dimension or the length of a compact description of the target.
Computational PAC learning therefore specifies representation and access assumptions. Instances may be -bit strings; targets may have a description size ; and an efficient learner is commonly required to run in time polynomial in , , , and . The details vary because some classes are naturally indexed by dimension, formula size, circuit size, or another structural parameter. Simply stating that runtime is polynomial is incomplete unless the relevant input sizes and numerical encodings are identified.
The distinction between proper and improper learning is also important. A proper learner outputs a member of the target class . An improper learner may output a hypothesis in a different class, provided it meets the required error guarantee and has an acceptable evaluation cost. For instance, a target represented by a short logical expression might be approximated by a larger voting classifier. Allowing a different output language can change computational feasibility and sometimes sample complexity.
Finding a perfectly consistent hypothesis can encode a difficult combinatorial search problem. In some proper-learning settings, consistency is NP-hard, but such a result alone does not prove that every PAC learner is inefficient. A learner may tolerate small error, exploit random sampling, or use an improper representation. Computational lower bounds must therefore match the exact learning model. Conversely, an efficient procedure for optimizing training error is not enough by itself: the hypothesis class must also have an appropriate statistical guarantee.
Cryptography supplies a different source of learning hardness. Under suitable cryptographic assumptions, families of pseudorandom functions are efficiently evaluable but computationally indistinguishable from random functions to efficient procedures with the specified access. A learner that predicted such functions substantially better than chance on fresh random inputs could violate that indistinguishability. These arguments establish conditional barriers to efficient learning even when targets possess compact computational descriptions.
Numerical representation introduces further distinctions. A geometric algorithm may use a polynomial number of arithmetic operations while manipulating numbers whose bit lengths grow excessively. A full running-time analysis must account for precision and encoding cost, not just operation count. PAC analysis consequently separates three resources: the information supplied by examples, the representation used to express predictions, and the computation needed to construct and evaluate the resulting hypothesis.
Real-valued prediction and richer complexity measures
Although binary classification supplied the original setting, PAC-style guarantees extend to real-valued prediction and general loss functions. A hypothesis may predict a numerical response, a probability, or a vector. With loss , its risk is
The learning objective remains a high-probability bound on risk or excess risk. However, the mathematical assumptions must now control both the richness of the function class and the magnitude or tails of the loss.
For bounded loss, uniform convergence can be established using covering numbers or other measures of function-class complexity. The pseudo-dimension extends VC dimension to real-valued functions by asking whether function values can realize all above-threshold and below-threshold patterns at selected points, with a separate fixed threshold for each point. It is useful for regression classes in which exact function values matter rather than only binary decisions.
The fat-shattering dimension introduces an explicit scale. A set is shattered at scale when all binary patterns can be realized while keeping function values at least above or below appropriate thresholds. This scale sensitivity is important because two real-valued functions may differ mathematically while being nearly indistinguishable at the accuracy relevant to prediction. For bounded real-valued classes under standard formulations, finite fat-shattering dimension at every positive scale characterizes uniform convergence.
Rademacher complexity measures how well a function class can correlate with independent random signs. For a fixed sample , one common definition is
where each independently equals or with equal probability. A class that fits random signs strongly has greater capacity to exploit sampling fluctuations. Unlike a single worst-case dimension, this quantity can depend on the observed data and can yield bounds reflecting their geometry.
These tools help explain norm-based and margin-based guarantees for linear predictors and support vector machines. A class may have many parameters but still admit useful bounds when input norms, weight norms, and classification margins are controlled. Regularization can impose such restrictions explicitly, while an optimization procedure may also favor a restricted subset of possible solutions.
Unbounded losses need additional care. Squared error can become arbitrarily large, so a sample may fail to reveal rare outcomes that dominate population risk. Moment assumptions, tail conditions, truncation, or robust estimation may then be necessary for finite high-probability guarantees. A binary-classification theorem cannot simply be transferred to unrestricted regression by changing the output type; the loss and distributional assumptions are part of the learning problem.
Alternative access models and extensions
The examples available to a learner are a defining part of its task. Classical PAC learning supplies passive, independently sampled labeled observations. In active learning, the learner can choose which available instances to have labeled, or can interact with a specified query mechanism. The central resource may then be label complexity rather than the total number of unlabeled observations. Under favorable assumptions, labels can be substantially more informative when selected adaptively.
Threshold learning illustrates this difference. If a learner may ask for labels at chosen points in a known ordered interval and the labels follow a noiseless threshold, binary search localizes the boundary using a logarithmic number of queries in the desired spatial precision. Passive examples instead depend on where the sampling distribution places probability mass. Spatial accuracy and distributional prediction error are different objectives, so query-learning and passive PAC bounds must be compared using matching assumptions.
Membership queries ask directly for the label of a chosen instance. Equivalence-query models ask whether a proposed hypothesis is correct and, if not, receive a counterexample. These access models can make some classes efficiently learnable even when random examples alone do not yield known efficient algorithms. Their conclusions do not automatically apply to situations where arbitrary instances cannot be constructed or reliably labeled. For example, a synthetically generated input may have no unambiguous label in the application.
The statistical query model, introduced by Michael Kearns in the 1990s, gives access to approximate expectations of bounded functions of labeled examples rather than direct access to individual records. Many noise-tolerant learning procedures can be expressed this way. Statistical-query lower bounds limit algorithms within this access model, but do not establish hardness for every possible sample-based algorithm. Parity learning is a standard illustration: noiseless parity functions can be learned efficiently from examples by linear algebra, while unrestricted parity classes are difficult for statistical-query procedures at useful tolerances.
PAC-style reasoning also appears in differentially private learning, where the output must satisfy a stability requirement under changes to individual training records. Privacy creates additional constraints beyond ordinary prediction accuracy, so classical sample bounds need not remain sufficient. In semi-supervised learning, unlabeled examples can reveal the marginal distribution of inputs, but they do not by themselves determine how labels relate to that distribution. Benefits require assumptions that connect distributional structure with the target.
A separate framework, PAC-Bayesian theory, provides high-probability risk bounds for distributions over predictors. Typical bounds relate empirical performance to a divergence between a data-dependent posterior and a prior chosen independently of the training sample. The shared terminology reflects a common emphasis on probabilistic accuracy guarantees, but PAC-Bayesian analysis is not merely a synonym for classical concept-class PAC learnability.
Scope, assumptions, and limits of the guarantee
A PAC theorem is conditional on its sampling model. The standard setting assumes that training examples are independent and identically distributed and that future prediction error is measured under the same distribution. Temporal dependence, adaptive data collection, or changes in the operating environment require additional analysis. Under distribution shift, a classifier can satisfy a valid training-distribution guarantee while performing poorly on the deployment distribution.
The phrase “distribution-free” is sometimes misunderstood. It means that the theorem holds separately for every fixed distribution in the allowed family, with a sample bound that does not depend on which one was chosen. It does not mean that the learner can train under one arbitrary distribution and automatically generalize to another. Results for domain adaptation need further restrictions, such as relationships between source and target distributions or assumptions about how labels behave across domains.
PAC accuracy is an average-risk statement. A classifier with low total error can still perform badly on a rare subgroup or a small region of the instance space. Likewise, ordinary classification error does not establish probability calibration, causal validity, interpretability, or robustness to deliberately chosen inputs. Adversarial examples concern perturbed or strategically selected instances, whereas a classical PAC bound averages over ordinary draws from the stipulated distribution.
The choice of hypothesis class is another substantive assumption. Without restrictions on possible target functions, successful extrapolation from a finite sample cannot generally be guaranteed. If every labeling of unseen points remains possible, observed labels provide no universal basis for choosing among contradictory predictions there. This is the role of inductive bias: learning depends on a restriction, preference, or structural assumption connecting observed and unobserved cases. Finite VC dimension makes one such restriction mathematically explicit.
Worst-case upper bounds can also be conservative. A theorem must cover every distribution and target in its scope, including configurations unlike those encountered in a particular application. A bound larger than the available sample does not prove that the trained model will perform poorly; it means that this bound fails to certify the desired performance. Conversely, good empirical results on a few tasks do not establish distribution-free PAC learnability of an entire class.
Independent evaluation addresses a different question. A fixed classifier evaluated on a fresh test set can receive a high-confidence estimate of its error without requiring a capacity bound for the entire training procedure. Repeatedly inspecting the same test set to select models weakens that independence and can introduce data leakage. PAC theory distinguishes guarantees about a learning method before training from statistical assessment of a particular trained predictor afterward.
Historical development and relations to other learning theories
Valiant introduced the framework in the 1984 paper A Theory of the Learnable. Its distinctive contribution was to combine approximate correctness, high confidence, and computational efficiency in a common formal model. Earlier accounts of learning had already studied inference from examples, but PAC learning gave theoretical computer science a systematic language for asking which concept classes admit efficient learning procedures.
The statistical foundations partly predated this formulation. Vladimir Vapnik and Alexey Chervonenkis developed uniform-convergence results and the combinatorial dimension bearing their names in work published in 1971. Norbert Sauer and Saharon Shelah independently established the central combinatorial growth bound in 1972. These results became the machinery for relating the expressive capacity of infinite binary classes to sample requirements.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth developed the connection between Occam-style arguments and learnability in 1987, and gave a foundational treatment of learnability and VC dimension in 1989. Their work clarified why short descriptions and bounded combinatorial complexity support generalization. David Haussler’s 1992 work on decision-theoretic generalizations helped extend the framework beyond noiseless binary concepts toward broader prediction and loss settings.
Another major development concerned boosting. Robert Schapire showed in 1990 that, in the PAC framework, weak learning can be converted into strong learning under the appropriate assumptions. A weak learner achieves an advantage over random guessing, while a strong learner can reach arbitrarily small error with controlled confidence and resources. Yoav Freund and Schapire subsequently developed AdaBoost in the 1990s, connecting this theoretical question to a practical ensemble-learning method. The reduction repeatedly emphasizes different parts of the example distribution and combines weak hypotheses into a stronger predictor.
PAC learning differs from online learning, where predictions are made sequentially and performance is often measured by mistakes or regret against a comparator. The distinction is substantive: online learning may require guarantees against adversarial sequences rather than random samples. Nevertheless, online-to-batch conversions can transform suitable sequential guarantees into statistical ones when data are sampled appropriately. The relevant capacity measures can also differ; finite VC dimension alone does not characterize learnability in the fully adversarial online classification model.
Developments in deep learning have renewed attention to the gap between worst-case class complexity and the behavior of specific training procedures. Large neural networks can have enough capacity to fit arbitrary labels while still generalizing on structured tasks. This does not contradict PAC theory: a bound based on the entire unrestricted class may simply be too coarse. Research therefore examines norms, margins, compression, algorithmic stability, and properties of optimization to identify more informative guarantees for the predictors actually produced.