Does PAC learning require a finite hypothesis class?

No. Other measures, including VC dimension in binary classification, allow analysis of many infinite classes.

Must the data distribution be known?

Not in the standard distribution-free setting, although examples must satisfy the assumed sampling conditions.

Can PAC learning handle noisy problems?

Agnostic and other extensions address settings beyond perfect realizability, with different guarantees and sample requirements.

AI Glossary / Graphs and symbolic AI / Advanced

PAC learning

Definition

PAC learning, short for probably approximately correct learning, is a mathematical framework for studying when an algorithm can learn a predictor from examples with a specified accuracy and confidence. Its guarantees depend on explicit assumptions about data, hypothesis classes and the learning procedure.

What it means

“Approximately correct” allows a small prediction error, usually controlled by a number called epsilon. “Probably” allows a small chance that the learning process returns a predictor exceeding that error, usually controlled by delta.

These are different quantities. An error tolerance of 5% and failure probability of 1% do not mean the model is 94% accurate. They describe a statement about how reliably training produces a predictor whose true error meets a target.

The framework concerns performance on new examples drawn according to the assumed distribution. It does not promise correctness for every imaginable input. A distribution-free guarantee applies across the allowed distributions, but training and evaluation must still satisfy the theorem's sampling assumptions.

How it works

In a basic realizable classification setting, labeled examples are drawn independently from the same distribution, and some hypothesis in the chosen class labels them perfectly. A consistent learner selects a hypothesis that makes no training mistakes.

A learning theorem bounds how many examples suffice to make poor hypotheses unlikely to survive this consistency test. For a finite hypothesis class H, a familiar sufficient bound is m ≥ (ln|H| + ln(1/delta))/epsilon. Here ln is the natural logarithm, and the bound applies under the realizable assumptions just described.

Agnostic PAC learning removes the requirement of a perfect hypothesis. Its accuracy target is typically closeness to the best achievable error within the class. Computationally efficient learning additionally asks whether the required learning procedure can run within appropriate resource bounds. Statistical learnability alone does not make exhaustive search practical.

Three practical examples

A researcher compares hypothesis classes by how many labeled examples their learning guarantees require.
A developer uses a simple finite-class bound to understand the tradeoff between allowable error, confidence and model flexibility.
A project reviewer checks whether a claimed learning guarantee assumes independent observations, realizable labels or an efficient optimization procedure.

Think of it this way

Think of specifying both the acceptable defect rate of a produced item and the reliability of the production process. One number describes the quality target; another describes how often the process might miss that target.

The analogy is bounded: PAC learning studies a mathematical training procedure, not a factory inspection certificate. Its probability is over the training sample and any included algorithmic randomness, and its guarantee cannot be transferred to a changed data-generating process without justification.

Worked example

Suppose an invented problem has a fixed class of 20 binary classifiers. Assume independent, identically distributed examples, a perfectly correct classifier in the class, and a learner that returns a classifier consistent with all training labels.

Choose epsilon = 0.05 and delta = 0.01. The sufficient finite-class bound gives m ≥ ln(20/0.01)/0.05 = ln(2000)/0.05 ≈ 152.02. Rounding up gives 153 examples.

Under those assumptions, the chance that the learned classifier has true error greater than 5% is at most 1%. This is not a claim that every training sample succeeds, or that the next 100 predictions contain exactly five mistakes.

The bound is sufficient, not a proven minimum for this invented task. If noisy labels prevent any classifier from being correct everywhere, the realizable theorem no longer supplies this guarantee; an appropriate agnostic analysis is needed instead.

Illustrative case study

The fictional Birch Learning team proposes a small rule-based classifier and quotes the 153-example calculation to a project sponsor. During review, the team discovers that many collected rows repeat the same underlying cases and that experts sometimes disagree about labels.

Birch stops presenting the realizable calculation as a certificate for its dataset. It documents the assumptions, investigates the dependence and labeling process, and uses a relevant empirical evaluation alongside any suitable theoretical analysis.

The fictional lesson is that a numerical theorem becomes useful through an explicit connection to the actual task. A precise calculation cannot compensate for assumptions that the project does not satisfy.

Common misconceptions and mistakes

PAC means a particular model is certified accurate. It describes guarantees for specified learning settings and procedures, not a generic badge.
Delta is the model's prediction error. Delta controls failure of the learning guarantee; epsilon controls the allowed error or excess error.
A larger hypothesis class is automatically better. Greater flexibility can increase the amount of evidence needed.
Learnability means fast training. Finding a suitable hypothesis may still be computationally difficult.
Distribution-free means immune to distribution shift. The standard sampling relationship still matters.

Business use

PAC reasoning helps teams ask disciplined questions about evidence: what family of predictors is considered, what error is acceptable, how confident must the result be, and which sampling assumptions apply?

For operational decisions, mathematical sample bounds can be conservative and may not describe a complex deployed system directly. Use them to clarify tradeoffs and inspect claims, alongside task-specific validation and monitoring.

When a supplier cites a PAC result, request the actual theorem, loss function, hypothesis class and assumptions. Also ask whether the guarantee concerns a theoretical learner or the implemented algorithm. The distinction is especially important when optimization is approximate or preprocessing changes the effective model family.

Check your understanding

With epsilon = 0.05 and delta = 0.01, what does the 1% quantity describe?

Answer: It bounds the probability that training returns a predictor whose true error exceeds the allowed 5%, under the theorem's assumptions. It is not the fraction of individual predictions expected to be wrong.

Related terms

Learn next

Write down a small finite set of classifiers and identify the assumptions needed for a realizable guarantee. Calculate the sufficient bound for two epsilon values and two delta values. Then explain which assumptions would fail if examples repeat or labels contain noise.

Sources

Shalev-Shwartz and Ben-David develop PAC learning, realizability and agnostic learning in their textbook: https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

Carnegie Mellon learning-theory course materials present finite-class bounds: https://www.cs.cmu.edu/~aarti/Class/10701_Spring14/slides/LearningTheoryII.pdf

The 20-classifier calculation and Birch Learning case are original illustrations; they do not establish a guarantee for a real dataset.

Previous: P-value Next: PACELC design principle