Probably approximately correct learning

Probably approximately correct learning, usually abbreviated PAC learning, is a mathematical framework for analyzing when a machine-learning algorithm can infer a sufficiently accurate rule from finitely many observations. The framework separates two forms of uncertainty. The word “approximately” permits a bounded rate of prediction error, while “probably” permits a bounded probability that the learning process fails to achieve that accuracy. Both bounds are specified explicitly rather than interpreted colloquially.

Leslie Valiant introduced the PAC model in 1984 as a distribution-independent theory of learnability. The original formulation combined statistical requirements with limits on computational resources, thereby distinguishing the existence of an accurate hypothesis from the existence of an efficient algorithm that can find one. Subsequent formulations connected PAC learning with VC dimension, empirical risk minimization, agnostic learning, and computational complexity theory.

Formal setting

Let (\mathcal X) be an instance space, and let an unknown probability distribution (D) govern the production of instances (x\in\mathcal X). In the realizable binary-classification setting, an unknown target concept

[ c:\mathcal X\rightarrow{0,1} ]

assigns the correct label to each instance. A sample of size (m) consists of independently drawn labeled examples

[ S=\bigl((x_1,c(x_1)),\ldots,(x_m,c(x_m))\bigr), \qquad x_i\sim D. ]

A learning algorithm receives (S) and returns a hypothesis (h) from a hypothesis class (\mathcal H). Its population error is

[ \operatorname{err}D(h) =\Pr{x\sim D}\bigl[h(x)\neq c(x)\bigr]. ]

For accuracy parameter (\varepsilon\in(0,1)) and confidence parameter (\delta\in(0,1)), the required guarantee is

[ \Pr_{S\sim D^m} \left[ \operatorname{err}_D(h_S)\leq\varepsilon \right] \geq 1-\delta. ]

The outer probability concerns the random training sample and any randomness internal to the learning algorithm. It does not state that each individual prediction is correct with probability (1-\delta). Instead, it states that the entire training procedure returns a hypothesis whose population error is at most (\varepsilon), except on a set of training outcomes having probability at most (\delta).

A concept class (\mathcal C) is PAC learnable by (\mathcal H) when such a guarantee holds for every target (c\in\mathcal C), every distribution (D), and every admissible pair ((\varepsilon,\delta)), using a sample size bounded polynomially in the relevant representation size, (1/\varepsilon), and (\log(1/\delta)). Efficient PAC learnability additionally requires polynomial running time. When (\mathcal H=\mathcal C), the learner is called proper; otherwise, it is an improper learning algorithm.

Distribution independence

The PAC model imposes no parametric assumption on (D). The same learner must satisfy its guarantee for every distribution over (\mathcal X), although the learned hypothesis and its error are evaluated relative to the particular distribution that generated the sample. This requirement is commonly described as distribution-free learning.

Distribution independence does not imply that all regions of the instance space receive equal attention. A hypothesis may behave arbitrarily on a region to which (D) assigns negligible probability while still having small population error. PAC accuracy therefore concerns expected predictive behavior under the data-generating distribution rather than pointwise agreement throughout (\mathcal X).

The assumption that examples are independent and identically distributed is mathematically separate from distribution independence. Standard PAC analysis permits an arbitrary fixed distribution but ordinarily requires each observation to be drawn independently from it. Learning under temporal dependence or distributional change belongs to modified frameworks such as online learning and domain adaptation.

Finite hypothesis classes

For a finite hypothesis class, a direct counting argument gives a basic sample-complexity bound. Suppose the realizability assumption holds and the learner returns a hypothesis consistent with all (m) training examples. Any hypothesis with true error greater than (\varepsilon) has probability at most

[ (1-\varepsilon)^m\leq e^{-\varepsilon m} ]

of agreeing with the entire sample. Applying the union bound over (\mathcal H) shows that the probability of selecting any consistent hypothesis whose error exceeds (\varepsilon) is at most

[ |\mathcal H|e^{-\varepsilon m}. ]

Consequently, the sufficient condition

[ m\geq \frac{\ln|\mathcal H|+\ln(1/\delta)}{\varepsilon} ]

ensures PAC accuracy at confidence (1-\delta).

This calculation illustrates the role of model complexity. The sample requirement depends logarithmically on the number of available hypotheses because the learner must control the possibility that at least one inaccurate hypothesis fits the observed data by chance. The quantity (\ln|\mathcal H|) is closely related to the number of bits needed to identify a hypothesis, linking finite-class PAC bounds with information theory.

Infinite classes and VC dimension

Cardinality is unsuitable for many natural hypothesis classes because even simple parameterized families can contain uncountably many functions. Their statistical complexity is instead characterized by the patterns they can realize on finite subsets of the instance space.

A binary hypothesis class (\mathcal H) shatters a set ({x_1,\ldots,x_n}) when every one of the (2^n) possible binary labelings of that set is induced by some hypothesis in (\mathcal H). The VC dimension, written (\operatorname{VCdim}(\mathcal H)), is the largest shattered-set size, or infinity when arbitrarily large finite sets can be shattered.

Work by Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth established the central relationship between finite VC dimension and distribution-free learnability. For binary concept classes under standard measurability conditions, finite VC dimension characterizes PAC learnability in the realizable setting.

If (d=\operatorname{VCdim}(\mathcal H)), uniform-convergence arguments yield realizable-case sample bounds of the form

[ m= O!\left( \frac{ d\log(1/\varepsilon)+\log(1/\delta) }{ \varepsilon } \right). ]

Sharper analyses and algorithms remove the additional logarithmic dependence on (1/\varepsilon) in the optimal asymptotic rate, giving

[ m= \Theta!\left( \frac{d+\log(1/\delta)}{\varepsilon} \right) ]

up to universal constants. These expressions describe information-theoretic sample requirements and do not by themselves imply that the relevant hypothesis can be computed efficiently.

Confidence amplification

A learner that succeeds with a fixed confidence greater than one half can be transformed into a learner with failure probability (\delta) by repeated training and independent validation. The repetition count grows logarithmically with (1/\delta), which explains why confidence generally enters PAC sample bounds through (\log(1/\delta)) rather than (1/\delta).

During the late 1980s, You Watanabe formalized a validation-based confidence-amplification result for distribution-free learners. The analysis separated the data used to construct candidate hypotheses from the data used to compare their errors. Concentration bounds on the validation sample then ensured that a candidate with low population error was retained with probability at least (1-\delta). This formulation became part of the standard connection between constant-confidence learning guarantees and arbitrary-confidence PAC guarantees.

Confidence amplification changes the probability of obtaining an acceptable hypothesis without changing the target accuracy criterion. It is therefore distinct from boosting, which transforms a weak learner whose hypotheses have a small predictive advantage into a strong learner with arbitrarily low error under the relevant assumptions. Robert Schapire established the general equivalence between weak and strong learnability in the PAC setting, while later boosting methods supplied explicit iterative constructions.

Agnostic PAC learning

The realizable model assumes that some hypothesis represents the labeling rule exactly. Agnostic PAC learning removes this assumption by treating the sample as drawn from a distribution (P) over (\mathcal X\times{0,1}). Labels may contain noise, and the best member of (\mathcal H) may retain nonzero error.

The risk of a hypothesis becomes

[ R_P(h)= \Pr_{(x,y)\sim P}[h(x)\neq y]. ]

An agnostic learner returns (\hat h) satisfying

[ R_P(\hat h) \leq \inf_{h\in\mathcal H}R_P(h)+\varepsilon ]

with probability at least (1-\delta). The guarantee is comparative: the output need not have small absolute error, but its error must be close to that of the best hypothesis available within the specified class.

For a finite class, uniform concentration gives a sample complexity of order

[ O!\left( \frac{\ln|\mathcal H|+\ln(1/\delta)}{\varepsilon^2} \right). ]

For a class of VC dimension (d), the optimal agnostic dependence has the form

[ \Theta!\left( \frac{d+\ln(1/\delta)}{\varepsilon^2} \right). ]

The quadratic dependence on (1/\varepsilon) contrasts with the linear dependence in realizable PAC learning. The difference arises because the agnostic learner must estimate and compare nonzero risks rather than merely exclude hypotheses that contradict an error-free sample.

The systematic study of this setting developed through work by researchers including Michael Kearns, David Haussler, and Robert Schapire. Agnostic learning subsequently became a standard formal model for analyzing statistical learning without a perfect-model assumption.

Statistical and computational learnability

PAC analysis distinguishes sample efficiency from computational efficiency. A class can admit a polynomial sample bound while lacking a known polynomial-time learning algorithm. This occurs when the available data contain enough information to identify an accurate hypothesis, but extracting that hypothesis requires solving a computationally difficult optimization or search problem.

The distinction is visible in empirical risk minimization. Uniform convergence can establish that an empirical risk minimizer generalizes from the sample to the population. It does not establish that minimization over (\mathcal H) can be performed within feasible computational resources. Efficient PAC learnability therefore depends on the representation of hypotheses, the form of sample access, and the complexity of the optimization problem induced by the class.

Cryptographic constructions provide conditional separations between information-theoretic and computational learning. Under standard assumptions concerning one-way functions, certain concept classes have compact statistical descriptions but resist efficient prediction. Such results connect PAC learning with average-case computational hardness rather than with sample complexity alone.

Interpretation and scope

PAC learning is a framework for guarantees rather than a single algorithm. Its principal objects are a hypothesis class, a data-generating distribution, a loss criterion, and a learning procedure whose sample and computational requirements are analyzed as functions of (\varepsilon) and (\delta). Different algorithms can satisfy the same PAC definition while relying on unrelated optimization methods.

The framework also distinguishes generalization from training fit. A hypothesis with zero empirical error need not have low population error when the hypothesis class is too expressive relative to the sample size. Capacity measures such as VC dimension quantify the extent to which empirical agreement constrains unseen behavior.

PAC guarantees are finite-sample statements. They specify how much data suffices to attain a stated accuracy and confidence, rather than only describing convergence as the sample size approaches infinity. This finite-sample orientation places the framework within statistical learning theory and connects it with concentration inequalities, combinatorial dimension, and computational models of inference.