Probably approximately correct learning, usually called PAC learning, is a mathematical framework for studying whether a learning procedure can infer an accurate prediction rule from a finite collection of examples. Introduced by Leslie Valiant in 1984, it gives precise meanings to successful learning: the rule should be approximately correct, allowing a specified amount of prediction error, and should satisfy that requirement probably, with a specified high probability over the examples used to construct it. The framework is foundational to machine learning and computational learning theory because it separates the amount of information needed to learn from the computation needed to use that information.
In its standard form, a learner receives independently sampled, labeled examples from an unknown probability distribution. It must produce a predictor whose error on fresh examples from the same distribution is small. PAC analysis asks how the required sample size depends on accuracy, confidence, and the complexity of the possible prediction rules. It also asks whether a suitable predictor can be found in polynomial time. These questions connect generalization, computational complexity, and the statistical structure of prediction problems.
The original framework assumes that some rule in a specified class labels every example correctly. Later formulations allow label noise and model misspecification, compare a learner against the best available rule rather than a perfect one, and accommodate other losses and sampling arrangements. PAC guarantees are conditional mathematical statements: their force depends on the hypothesis class, the sampling model, and the computational resources included in the definition.
Historical origins and intellectual setting
Valiant introduced the framework in “A Theory of the Learnable,” published in 1984 in Communications of the ACM. His central objective was to make learning a subject of computational analysis, rather than merely a description of successful behavior. A learning problem would be specified by a class of possible concepts, access to examples, an accuracy requirement, and a resource bound. The resulting question was whether one algorithm could learn every concept in the class under the stipulated conditions.
The framework combined two traditions. Statistical research had long examined how observations support inference about an unknown population. Vladimir Vapnik and Alexey Chervonenkis developed a theory of uniform convergence in the late 1960s and early 1970s, including their influential 1971 work on empirical frequencies. Computer science, meanwhile, had developed precise distinctions between efficiently solvable problems and problems requiring excessive computational resources. PAC learning brought these concerns together: sufficient data do not automatically imply an efficient learning procedure.
An important feature of Valiant’s formulation was its tolerance for error. Requiring a learner to recover the exact target rule from finitely many random examples is generally too demanding, particularly when the instance space is infinite. PAC learning instead requires small error under the distribution that generates examples. A learner may therefore disagree with the target on some inputs, provided those inputs have sufficiently little probability mass. This makes learnability sensitive to prediction performance rather than exact symbolic reconstruction.
The distribution-free requirement was equally consequential. The learner was not ordinarily given the underlying distribution and had to succeed for every distribution satisfying the sampling assumptions. “Distribution-free” did not mean that the data lacked a distribution; it meant that the theorem did not restrict that distribution to a particular parametric family. This made it possible to state general results about classes of Boolean functions and other prediction rules.
The modern synthesis was strengthened by the work of Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth. Their 1987 work on Occam’s razor related short descriptions to generalization, and their 1989 paper “Learnability and the Vapnik–Chervonenkis Dimension” connected distribution-free learnability to a combinatorial measure of class complexity. Michael Kearns and Umesh Vazirani’s 1994 textbook helped systematize computational learning theory. These developments established a durable distinction between statistical learnability, which concerns the existence of adequate finite samples, and efficient learnability, which also requires a feasible algorithm.
The formal learning problem
In binary classification, let be an instance space and let be a concept class, a collection of functions . An unknown target assigns labels, while an unknown distribution determines how often different instances occur. The learner observes training data
The abbreviation “iid” means independent and identically distributed. Independence supports concentration arguments, while identical distribution connects observed examples to the future population on which performance is evaluated.
The learner returns a hypothesis . Its population error is
For accuracy parameter and confidence parameter , a PAC guarantee requires
The outer probability is over the random sample and any internal randomness of the learning algorithm . The inner error concerns a fresh instance. Thus and describe different uncertainties: allowable population error and allowable probability that training produces an excessively inaccurate predictor.
A class is distribution-free PAC learnable if there is an algorithm and a finite sample bound that satisfy this guarantee for every target in the class and every allowed distribution. The bound must not depend on the particular unknown target or distribution. This ordering of quantifiers matters. An algorithm that works for one favorable distribution does not establish distribution-free learnability, and a collection of target-specific algorithms does not establish that a single learner can solve the whole problem.
The hypothesis class from which the learner outputs predictions need not equal . A proper learner outputs an element of the target class; an improper learner may use a different representation. For example, a class described by restricted formulas might be learned using a more expressive voting representation. Improper learning does not relax the accuracy requirement, but it can change the computational difficulty of producing a suitable predictor.
The distinction between statistical and computational definitions must be stated explicitly. In a statistical treatment, PAC learnability may require only a finite sample bound and an abstract learning rule. In computational learning theory, efficient PAC learning usually requires sample size and running time polynomial in , , the input dimension, and an appropriate target-description parameter. Reading examples, constructing the hypothesis, and evaluating its predictions all depend on the representation. A running-time claim is therefore incomplete without an encoding model.
Finite classes, consistency, and Occam bounds
The simplest general PAC argument applies to a finite hypothesis class in the realizable setting, where some member labels all examples correctly. A hypothesis is consistent with a sample if it makes no training errors. Suppose a particular hypothesis has true error greater than . Because examples are independent, its probability of remaining consistent on examples is at most
A seriously inaccurate rule can escape detection, but the chance decreases exponentially with the sample size.
There may be many inaccurate hypotheses, so the analysis must control the possibility that any of them fits the sample. The union bound gives
Consequently, every consistent hypothesis has error at most , with probability at least , whenever
This is a sufficient sample bound, not a guarantee that a consistent hypothesis can be found quickly. Exhaustively searching a finite class may require time exponential in the length of its representation.
The logarithmic dependence on class size explains why an enormous number of candidate rules need not imply an enormous sample requirement. A class containing hypotheses contributes to the numerator. For a class of 1,024 hypotheses, , and , the displayed bound is satisfied by 199 examples after rounding upward. The theorem is conservative and distribution-free: an individual problem may need substantially fewer examples.
This argument underlies a learning-theoretic version of Occam’s razor. If hypotheses can be specified by binary descriptions of at most bits, their number is less than . A short consistent explanation therefore has a controlled generalization bound. The relevant notion of simplicity is description length within a specified coding system, not aesthetic elegance. Changing the representation changes which rules are short, connecting the argument to inductive bias.
Occam bounds can also handle countable collections of hypotheses with different description lengths by allocating different failure probabilities to different rules. A prefix-free code, whose codewords cannot be prefixes of one another, permits such allocation through its code lengths. This relates PAC analysis to minimum description length, although the two are not identical theories. The essential mechanism remains a probability budget: more complex hypotheses receive weaker individual guarantees unless supported by more data. A short description helps because it limits the effective number of alternatives that could have fit the sample by chance.
Concrete examples: thresholds, conjunctions, and intervals
Threshold classification gives a transparent example of learning from geometry. Let and define when , with label otherwise. A sample constrains the unknown threshold to lie between the largest observed negative point and the smallest observed positive point, when both exist. A consistent threshold can be chosen in this gap, with appropriate conventions when only one label is observed.
The learner need not estimate accurately in ordinary Euclidean distance. A wide interval containing almost no probability mass can be harmless, whereas a narrow interval containing substantial mass matters greatly. If a candidate threshold misclassifies a region of probability greater than , obtaining no sample from that region has probability at most . More refined endpoint arguments show that thresholds can be learned using a sample size of order . The guarantee remains valid for discrete, continuous, and mixed input distributions.
Boolean conjunctions illustrate how a large class can admit an efficient consistency procedure. Consider Boolean variables and conjunctions of literals such as . Starting with all positive and negative literals, the learner removes every literal contradicted by any positive example. Every literal in the true target survives, because a positive example must satisfy it. The remaining conjunction therefore contains the target’s literals and possibly additional ones.
This procedure classifies every negative example correctly: any point satisfying the learned conjunction necessarily satisfies the true conjunction. Positive training examples are also classified correctly because all surviving literals agree with them. There are noncontradictory conjunctions, corresponding to including a variable positively, negatively, or not at all, together with the constant-false function if that concept is allowed. The finite-class bound therefore gives sample complexity of order , while processing the sample takes time proportional to under a direct implementation.
Intervals offer a related example on the real line. If positive instances lie within an unknown interval, the smallest interval containing all observed positive points is consistent in the realizable setting. Errors occur only in unobserved portions near the target interval’s ends. Each sufficiently massive missed portion is unlikely to remain unobserved. In higher dimensions, axis-aligned rectangles can be learned by taking coordinatewise minima and maxima of positive observations; elementary analyses control missed probability mass near their faces.
These examples distinguish prediction from parameter recovery. The threshold or rectangle itself may not be uniquely identifiable from finite data, and no sample can reveal features of a target confined to a zero-probability region. PAC learning nevertheless succeeds if the unresolved distinctions have small probability under the evaluation distribution. Identifiability of a symbolic target and learnability of its predictions are different mathematical requirements.
VC dimension and infinite hypothesis classes
Finite-class counting does not directly handle all thresholds or all linear separators, since these classes may contain uncountably many functions. Vapnik–Chervonenkis dimension, or VC dimension, measures their effective classification capacity without counting hypotheses themselves. A class shatters a finite set if it can realize every possible assignment of binary labels on that set. Its VC dimension is the largest size of a shattered set, or infinity if shattered sets of arbitrarily large finite size exist.
Thresholds on the real line have VC dimension . A single point can receive either label by moving the threshold, but two ordered points cannot receive the pattern positive then negative for thresholds oriented toward increasing values. Intervals have VC dimension : two points can be labeled arbitrarily, but three ordered points cannot realize positive, negative, positive with one interval. Affine halfspaces in have VC dimension . These examples show why an infinite parameter space can still have finite statistical complexity.
The growth function is the largest number of distinct labelings that can induce on points. The Sauer–Shelah lemma implies that, for VC dimension and ,
Without a capacity restriction, the number could be . Finite VC dimension therefore converts potentially exponential growth in sample labelings into polynomial growth for fixed . This combinatorial restriction supports uniform bounds over all hypotheses.
Under standard measurability conditions, finite VC dimension characterizes distribution-free PAC learnability for binary classification. In the realizable case, a consistent learner has a standard sufficient sample bound of order
The logarithm in is not necessary for optimal learning in general. More sophisticated, potentially improper learners attain worst-case sample complexity of order
matching lower bounds up to universal constants in the usual nondegenerate parameter ranges. This sharper statement concerns the best possible learner, not every arbitrary consistency rule.
Infinite VC dimension yields a complementary impossibility argument. On a sufficiently large shattered set, every labeling is possible. A distribution can spread probability across that set while a limited sample leaves many points unseen. Since their labels remain unconstrained, no learner can reliably predict all of them. This establishes a statistical obstruction before computational resources are considered. Measurability qualifications matter for completely unrestricted mathematical classes, but ordinary classes used in finite-dimensional learning generally avoid these pathologies.
Agnostic learning, noise, and excess risk
The realizable assumption excludes mislabeled examples and assumes that the chosen class contains a perfect predictor. Agnostic learning removes both restrictions. Examples are drawn independently from an arbitrary joint distribution on , and the population risk is
An agnostic PAC learner aims, with probability at least , to return a hypothesis satisfying
The guarantee is relative to the best predictor in the comparison class, not necessarily the best predictor of any conceivable form.
The central quantity is excess risk, the difference between the learner’s risk and the class’s optimal risk. A class can be agnostically learnable even when its best achievable error is large. For example, if labels are independent fair coin flips, every deterministic classifier has error ; being close to the best classifier does not imply high absolute accuracy. This distinction is crucial when interpreting theoretical guarantees for a poorly matched model class.
Empirical risk minimization selects a hypothesis minimizing average training loss,
If every hypothesis’s empirical risk differs from its population risk by at most , an empirical minimizer has excess risk at most . The two contributions arise from estimating the selected hypothesis’s risk and estimating the best comparison hypothesis’s risk. Approximate minimization adds its optimization error to this bound.
For a finite class, Hoeffding’s inequality and a union bound imply
Setting yields a sufficient sample size proportional to . For binary classes of VC dimension , optimal worst-case agnostic sample complexity is of order . The quadratic accuracy dependence contrasts with the realizable case’s linear dependence.
Specific noise assumptions can yield intermediate or faster rates. Under random classification noise, labels are independently flipped with a probability below ; this preserves exploitable structure that arbitrary agnostic noise need not preserve. Conditions controlling how frequently the conditional label probability lies near also affect achievable rates. For more general tasks, the indicator loss can be replaced by another bounded loss function. Squared loss on unrestricted real-valued outputs requires additional boundedness or tail assumptions; the binary classification bounds do not transfer unchanged.
Computational efficiency and representation dependence
Statistical sample bounds do not solve the computational search problem. A finite class may require only a modest number of examples because its logarithmic size is small, while searching it still takes exponential time. Similarly, finite VC dimension establishes an information-theoretic possibility, not a polynomial-time implementation. The distinction is analogous to knowing that a solution is determined by an input without having an efficient method for finding it.
Efficient learning depends on how instances, targets, and hypotheses are represented. A Boolean function may have a short decision tree, a short circuit, or a short disjunctive formula, and these descriptions need not have comparable lengths. An algorithm polynomial in truth-table size can be exponential in the number of input variables, because a truth table has entries. Meaningful efficiency statements therefore specify both the input dimension and the representation size against which time is measured.
Properness can impose additional computational constraints. Finding the best rule within a restricted representation may be hard even when a predictor outside that representation achieves the same population accuracy efficiently. However, showing that one particular empirical optimization problem is NP-hard does not automatically prove that the corresponding class is not PAC learnable. A learner might avoid exact optimization, use a different representation, or exploit the random-example setting. Hardness of learning requires a reduction tailored to the actual guarantee and access model.
Cryptography supplies stronger conditional barriers. Under suitable assumptions about the existence of pseudorandom function families, a polynomial-time learner cannot efficiently learn certain efficiently evaluable function classes to nontrivial prediction accuracy. Otherwise, the learned predictor could help distinguish a pseudorandom function from a genuinely random one on fresh inputs. The argument illustrates a fundamental separation: a target can be quick to evaluate once its description is known while remaining difficult to infer from examples.
Access to information also changes learnability. In the ordinary PAC model, the learner receives random examples from the unknown distribution. A membership-query learner can request the label of an instance it chooses. Other models provide equivalence queries, noisy statistical expectations, or unlabeled observations. Algorithms with these additional resources solve different formal problems; a query-based result cannot simply be treated as a random-example PAC result. The statistical query model, introduced by Michael Kearns in 1993, is particularly important because it models learning through approximate expectations of bounded functions of examples and supports both noise-tolerant algorithms and computational lower bounds.
Weak learning, strong learning, and boosting
A strong PAC learner can achieve every requested error level . A weak learner is required only to perform slightly better than chance in binary classification. A typical weak-learning guarantee promises error at most , with high confidence, for some positive advantage . For efficiency claims, that advantage must be large enough to exploit computationally, commonly at least inverse-polynomial in the relevant problem parameters.
The distributional quantifier is essential. A weak learner must obtain its advantage under every distribution permitted by the model, not merely under one original training distribution. A rule that predicts the majority class can perform well on a particular imbalanced population but offers no distribution-free advantage. Boosting relies on this stronger condition because it repeatedly changes which examples or regions receive the most weight.
Michael Kearns and Leslie Valiant posed the question of whether weak learning implies strong learning in their 1989 work. Robert Schapire established the equivalence in the distribution-free PAC setting in 1990. The result showed that a weak learner could be called repeatedly on carefully constructed distributions, with the resulting hypotheses combined to obtain arbitrarily low error. It transformed a qualitative statement—slightly useful prediction exists—into a quantitative route to highly accurate prediction.
Yoav Freund developed further boosting methods, and Freund and Schapire introduced AdaBoost in 1995. In its standard binary form, boosting assigns weights to training examples, calls a base learner, and increases the relative influence of examples that the current predictor handles poorly. AdaBoost combines base hypotheses through a weighted vote. If , the final predictor has the form
The coefficients reflect the performance of each base hypothesis on its weighted training distribution.
Under the usual empirical weak-learning condition, if every round achieves weighted error at most , AdaBoost’s training error is bounded by . Thus a number of rounds proportional to suffices to reduce training error below . This statement concerns fit to the observed sample; a population guarantee additionally requires control of the combined class’s complexity, margins, or another suitable generalization quantity.
Boosting also exposes limits of the realizable abstraction. Under arbitrary label noise, repeatedly emphasizing difficult examples may emphasize mislabeled observations. Moreover, a weak learner for realizable distributions does not automatically satisfy the assumptions needed for agnostic boosting. Practical success of a boosted ensemble and the theorem equating weak and strong PAC learning are related but distinct claims: the theorem specifies exact distributional, accuracy, and computational conditions.
Extensions beyond basic binary classification
Multiclass classification replaces two labels with a larger label set. Its capacity theory requires distinctions that binary classification does not reveal. The Natarajan dimension, for example, measures whether a class can choose independently between two specified alternative labels at each point. For finite label sets, it helps characterize sample requirements, although label-set size and the particular learning procedure can introduce additional factors. Simply inserting the number of classes into a binary VC formula is not a general solution.
For real-valued prediction, pseudo-dimension and fat-shattering dimension play related roles. Pseudo-dimension measures the ability to realize comparisons against point-specific real thresholds. Fat-shattering additionally demands a positive separation margin and is therefore sensitive to scale. Such notions matter for regression and function approximation, where distinguishing values separated by may be irrelevant to a task whose tolerated error is much larger. Bounded outputs or controlled tails remain necessary for many finite-sample risk guarantees.
PAC-Bayesian learning develops high-probability bounds for distributions over hypotheses. A typical bound relates empirical loss and population loss to a divergence , where is a prior distribution fixed independently of the analyzed sample and is a data-dependent posterior distribution. Here “posterior” need not mean a posterior obtained through ordinary Bayesian updating. The divergence measures how far the selected distribution moves from the reference distribution. Data-dependent priors require additional constructions or corrections rather than unrestricted reuse of the same data.
Online learning studies sequential prediction, often without independent sampling. Performance is commonly measured through regret: cumulative loss relative to the best fixed predictor in hindsight. For binary classes, the Littlestone dimension characterizes realizable online learnability in the adversarial setting. This differs from VC dimension. Thresholds on a continuous ordered domain have finite VC dimension but infinite Littlestone dimension, demonstrating that a class can be PAC learnable while lacking a uniform finite mistake bound against an adaptive adversary.
Active learning allows a learner to choose which available instances should be labeled. For favorable distributions, this can reduce label requirements dramatically; under a uniform distribution, noiseless threshold learning can exploit binary-search-like querying among unlabeled points. Such improvements concern label complexity, not necessarily total sample acquisition or computation. Domain adaptation changes another assumption by distinguishing source and target distributions. A target guarantee then requires information connecting the domains, such as a controlled change in input frequencies and stable conditional label behavior.
The terminology also extends to reinforcement learning. PAC-style reinforcement-learning results may bound how many interactions occur before, or outside of periods when, an agent acts near optimally with high probability. These guarantees must incorporate exploration, state transitions, and delayed rewards. They preserve the accuracy-and-confidence logic of PAC analysis, but they are not direct applications of the independent labeled-example model.
Interpretation, limitations, and modern relevance
A PAC guarantee is a statement about a learning procedure under specified conditions, not an unconditional certificate attached to a trained model. In the standard setting, the guarantee averages prediction error over the same distribution that generated the training examples. It does not ensure correctness on every input, every subgroup, or every rare event. A region with probability below could be classified entirely incorrectly while the overall error still meets the target. Additional requirements need their own definitions and analysis.
Likewise, confidence does not mean that a particular prediction is correct with probability . It bounds the frequency with which random training samples lead to a predictor whose population error exceeds the stated threshold. Probability calibration concerns a different property: whether reported predictive probabilities agree with observed outcome frequencies. A classifier can satisfy a PAC error guarantee without producing probabilities at all, and calibrated probabilities do not by themselves establish a PAC learning guarantee.
Independent evaluation illustrates the distinction between learning and estimating performance. For a fixed predictor evaluated on an independent test set of size , Hoeffding’s inequality gives
This bound does not require knowing the complexity of the class used to produce the predictor, because the predictor is fixed relative to the test sample. If the same test observations are repeatedly used to select models, however, that independence is lost. Data leakage and adaptive selection therefore change which performance bounds are justified.
Distribution shift creates another boundary. Low error under a training distribution need not imply low error under a different deployment distribution. A class can be distribution-free PAC learnable while a particular trained model still fails after the distribution changes: distribution-free learning requires success when training and evaluation use the same arbitrary distribution, not when evaluation can switch arbitrarily after training. Robustness to adversarial examples similarly replaces ordinary error with an error notion involving allowed perturbations and requires separate assumptions.
Modern deep learning raises questions about how best to express effective complexity. A worst-case VC bound based on an entire neural-network architecture can be much larger than the available sample size, producing a mathematically valid but numerically uninformative bound. Analyses based on margins, norms, algorithmic stability, PAC-Bayesian divergences, and sample compression seek more informative descriptions of the predictor actually selected by training. These approaches study different properties and do not supply a universal explanation of every successful network.
Regularization and hyperparameter optimization also fit into this perspective. Selecting among many model families makes the effective learning procedure more complex than fitting within one family chosen in advance. Validation protocols, complexity penalties, and explicit allocation of confidence across candidate classes can account for parts of that selection. The relevant object is the complete data-dependent procedure, including preprocessing and model choice, rather than only its final optimization step.