PAC Learning

Let $\mathcal{X}$ be an instance space (e.g., feature vectors) and $\mathcal{Y} = \{0,1\}$ a label space. Assume examples $(x,y)$ are drawn i.i.d. from an unknown distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$. A hypothesis class $\mathcal{H}$ is a set of functions $h: \mathcal{X} \to \mathcal{Y}$ that the learner is allowed to choose from. The true (generalization) error of a hypothesis is

Since $\mathcal{D}$ is unknown, the learner only observes a training sample $S = \{(x_1,y_1), \dots, (x_m,y_m)\}$ drawn i.i.d. from $\mathcal{D}$, and can compute the empirical error

A learning algorithm $A$ takes $S$ and outputs a hypothesis $h_S = A(S) \in \mathcal{H}$. The realizable case assumes some $h^\star \in \mathcal{H}$ achieves $L_{\mathcal{D}}(h^\star) = 0$. A hypothesis class $\mathcal{H}$ is PAC learnable if there exists an algorithm $A$ and a function $m_{\mathcal{H}}(\epsilon,\delta)$ such that for every distribution $\mathcal{D}$, every labeling consistent with some $h^\star \in \mathcal{H}$, and every $\epsilon, \delta \in (0,1)$: given a sample of size $m \ge m_{\mathcal{H}}(\epsilon,\delta)$ drawn i.i.d. from $\mathcal{D}$, the algorithm outputs $h_S$ satisfying

The word "probably" refers to the confidence $1-\delta$ over the random draw of the sample; the word "approximately correct" refers to the accuracy tolerance $\epsilon$ on the true error. Crucially, $m_{\mathcal{H}}$ must not depend on $\mathcal{D}$ — the guarantee is distribution-free — and for efficient (computationally) PAC learning, $m_{\mathcal{H}}$ and the algorithm's running time must be polynomial in $1/\epsilon$, $1/\delta$, and the representation size of the problem. The agnostic version drops the realizability assumption entirely: there need be no perfect hypothesis. The goal becomes competing with the best hypothesis in the class, $h^\star = \arg\min_{h\in\mathcal{H}} L_{\mathcal{D}}(h)$, guaranteeing $L_{\mathcal{D}}(h_S) \le L_{\mathcal{D}}(h^\star) + \epsilon$ with probability $\ge 1-\delta$. This matches real-world settings where no hypothesis in $\mathcal{H}$ is perfect (label noise, model misspecification) and is the version most directly connected to Empirical Risk Minimization as used in practice.

The canonical PAC learning algorithm for the realizable, finite-hypothesis-class setting is simply ERM: return any hypothesis consistent with all training examples. The theoretical content is not in a clever algorithm but in the proof that ERM's output generalizes, and in computing precisely how large $m$ must be.

Step 1 — Define "bad" hypotheses. Call $h \in \mathcal{H}$ bad if $L_{\mathcal{D}}(h) > \epsilon$. We want to bound the probability that ERM ever returns a bad hypothesis.

Step 2 — Bound the failure probability of one bad hypothesis. If $h$ is bad ($L_{\mathcal{D}}(h) > \epsilon$) but is realizable-consistent with the sample ($L_S(h)=0$), that is a fluke. Since examples are i.i.d.,

Step 3 — Union bound over all bad hypotheses. There are at most $|\mathcal{H}|$ hypotheses total, so

Step 4 — Solve for $m$. Setting the right side $\le \delta$ and solving gives the sample complexity bound derived formally below. The pseudocode below implements ERM for a finite hypothesis class in the realizable setting, together with the sample-size calculation that gives the PAC guarantee. ``` ALGORITHM PAC-ERM-FiniteH INPUT: hypothesis class H (finite, |H| known), accuracy eps, confidence delta, sample oracle SAMPLE() that draws i.i.d. (x, y) ~ D OUTPUT: hypothesis h_S with Pr[ L_D(h_S) <= eps ] >= 1 - delta 1. m <- ceil( (1/eps) ( ln(|H|) + ln(1/delta) ) ) // sample complexity 2. S <- {} 3. for i = 1 to m: 4. (x_i, y_i) <- SAMPLE() 5. S <- S + {(x_i, y_i)} 6. // ERM step: find ANY hypothesis consistent with all of S 7. for h in H: 8. if all (x,y) in S satisfy h(x) == y: 9. return h // guaranteed to exist if realizable 10. return FAIL // should not happen if H is realizable for this D ``` Line 1 is the theoretical core: it is not a tuning knob but a derived formula guaranteeing the PAC bound. Lines 7–9 are a brute-force search; in practice a concrete hypothesis class comes with an efficient consistency-finding algorithm (e.g., linear programming for halfspaces, a decision-tree induction routine, etc.), and computational efficiency of that search is a separate question from the statistical* question this pseudocode answers. The figure below shows the logical structure of the argument: the full hypothesis space, the (usually small) island of "bad" hypotheses that also happen to fit the sample, and how the union bound shrinks that island's probability mass as $m$ grows.

Sample complexity derivation. From Step 3 above, we want

Taking logarithms:

So the sample complexity is

This is honest and tight up to constants: the $1/\epsilon$ dependence is unavoidable (a matching lower bound $\Omega(1/\epsilon)$ can be shown via a two-hypothesis "coin-flip" construction), and $\ln|\mathcal{H}|$ captures that richer hypothesis classes need more data — but only logarithmically many more, since a union bound over an exponentially large class still only costs a linear increase in required $m$. This is why classes like "all decision trees over $n$ boolean features of depth $d$," with $|\mathcal{H}| \approx 2^{2^d}$-ish combinatorial size, still have manageable sample complexity in terms of $d$ and $n$ as long as $\ln|\mathcal{H})$ is polynomial in the description length.

Correctness argument (why the bound guarantees PAC learning). Run ERM with $m \ge m_{\mathcal{H}}(\epsilon,\delta)$ samples. By realizability, ERM always finds some $h_S$ with $L_S(h_S) = 0$ (line 9 always succeeds). The only way this returned hypothesis can fail the guarantee is if $h_S$ is bad ($L_{\mathcal{D}}(h_S) > \epsilon$) and consistent with $S$ ($L_S(h_S)=0$) — exactly the event bounded in Step 3. By the choice of $m$, that event has probability at most $\delta$. Hence with probability at least $1-\delta$ over the sample, every consistent hypothesis (in particular $h_S$) has $L_{\mathcal{D}}(h_S) \le \epsilon$. This is the entire proof; no assumption about the algorithm's internal search strategy is needed beyond "return something consistent."

Where Hoeffding's inequality enters (agnostic case). In the agnostic setting there is no perfect hypothesis, so instead we bound, for a fixed $h$, the deviation between empirical and true error using Hoeffding's inequality:

A union bound over $|\mathcal{H}|$ hypotheses again gives a uniform convergence guarantee, and choosing $h_S = \arg\min_h L_S(h)$ yields $L_{\mathcal{D}}(h_S) \le L_{\mathcal{D}}(h^\star) + \epsilon$ with probability $\ge 1-\delta$, at sample complexity $m = O\!\left(\frac{\ln|\mathcal{H}| + \ln(1/\delta)}{\epsilon^2}\right)$ — note the worse $1/\epsilon^2$ dependence, reflecting the harder task of estimating errors rather than merely detecting zero error.

Time complexity of the algorithm itself. The pseudocode's ERM search (lines 7–9) costs $O(m \cdot |\mathcal{H}|)$ in the naive brute-force form — checking each hypothesis against each sample. This is not generally polynomial, since $|\mathcal{H}|$ can be exponential in the problem's natural parameters (e.g., all boolean functions on $n$ bits has $|\mathcal{H}| = 2^{2^n}$). Efficient PAC learning additionally requires a polynomial-time algorithm to find a consistent hypothesis — this is a separate, often much harder, computational question (some classes are statistically learnable with few samples but are NP-hard to learn efficiently, e.g., learning 3-term DNF formulas).

Tradeoffs to be honest about:

• The bound is distribution-free (worst-case over $\mathcal{D}$), so it is often loose for "easy" real-world distributions — practical sample needs are frequently far smaller.
• Finite-$|\mathcal{H}|$ bounds don't directly apply to continuous hypothesis classes (e.g., all linear separators over $\mathbb{R}^d$), which have $|\mathcal{H}| = \infty$; this motivates replacing $\ln|\mathcal{H}|$ with the VC Dimension, a combinatorial measure of effective capacity.
• The realizable-case bound ($1/\epsilon$) is statistically better than the agnostic bound ($1/\epsilon^2$), so assuming realizability when it doesn't hold can give false confidence.

Consider learning conjunctions of boolean literals over $n=10$ boolean features (each feature can appear positively, negatively, or not at all in the conjunction) — a classic PAC-learnable class. The hypothesis class size is

Suppose we want accuracy $\epsilon = 0.1$ (at most 10% true error) with confidence $1-\delta = 0.95$ (so $\delta = 0.05$).

So with only 140 labeled i.i.d. training examples, running ERM (find any conjunction consistent with all 140 examples — efficiently doable by the standard "eliminate contradicted literals" algorithm for this class) guarantees that, with probability at least 95%, the returned conjunction has true error at most 10%. Now watch how sensitively $m$ scales. Suppose the number of features grows to $n = 100$ (a 10× increase), keeping $\epsilon, \delta$ fixed:

A 10× increase in features (an exponential blow-up in $|\mathcal{H}|$ from $3^{10}$ to $3^{100}$) only causes roughly an 8× increase in required samples — this is the logarithmic dependence on $|\mathcal{H}|$ paying off exactly as the derivation promised. Compare this to demanding tighter accuracy: halving $\epsilon$ from $0.1$ to $0.05$ at $n=10$ gives

a clean doubling, confirming the $1/\epsilon$ linear dependence on accuracy.

PAC-style sample complexity reasoning underlies how practitioners estimate labeled-data budgets before launching a data collection effort, especially in domains like medical diagnosis models or fraud detection where labels are expensive. The theoretical distinction between statistical learnability (how much data suffices) and computational learnability (whether a fast algorithm exists) explains why certain hypothesis classes — like small decision trees or halfspaces — are preferred in practice: they are efficiently PAC learnable, whereas classes like arbitrary boolean circuits are not known to be, under standard cryptographic hardness assumptions. The framework's descendants are everywhere in applied machine learning theory: generalization bounds quoted in papers on neural network capacity, the theoretical justification for cross-validation and regularization strength selection, and PAC-Bayes bounds used to certify generalization for stochastic and Bayesian neural networks. Boosting algorithms (AdaBoost and its descendants, used in gradient-boosted tree libraries like XGBoost and LightGBM) trace their theoretical origin directly to Kearns and Valiant's PAC-theoretic question of whether "weak" learners (barely better than random guessing) can be combined into a "strong" learner. Model-complexity-aware training — early stopping, weight decay, and architecture search — is philosophically downstream of the PAC insight that hypothesis class richness must be paid for in sample size, a relationship made precise for infinite classes through the VC Dimension and generalized in The Bias-Complexity Tradeoff.

Ask the tutor: How does the PAC sample complexity formula change when moving from a finite hypothesis class to one with infinite hypotheses but finite VC dimension?