PAC Learning Framework

Overview & Motivation

The Concentration Inequalities topic gave us quantitative tools for controlling how random quantities deviate from their expectations. Hoeffding’s inequality bounds the gap between a sample average and its mean. McDiarmid’s inequality extends this to general functions of independent variables. But those tools answer a specific question — how fast does an average concentrate? — without addressing the deeper question that drives machine learning: when can a learning algorithm generalize at all?

Consider the standard machine learning setup. We have a hypothesis class $\mathcal{H}$ — a collection of candidate classifiers. We observe a finite training sample and pick the hypothesis that performs best on that sample (empirical risk minimization). The training error is an observable quantity. The true error — performance on unseen data — is not. The gap between them is the generalization gap, and controlling it is the central problem of statistical learning theory.

PAC learning theory answers three fundamental questions:

1. Feasibility. For which hypothesis classes is generalization possible — that is, for which $\mathcal{H}$ can we guarantee that training error approximates true error given enough data?
2. Sample complexity. How many training examples suffice to achieve a desired accuracy $\varepsilon$ with confidence $1 - \delta$?
3. Complexity measures. What properties of $\mathcal{H}$ determine the answers to (1) and (2)?

We will build the theory in three stages. First, we handle finite hypothesis classes using the concentration tools from the previous topic — the union bound and Hoeffding’s inequality give clean sample complexity bounds. Second, we introduce the VC dimension as the combinatorial measure that governs learnability for infinite classes, and prove the Sauer–Shelah lemma that makes infinite classes tractable. Third, we develop Rademacher complexity as a data-dependent alternative that often gives tighter bounds. The culmination is the Fundamental Theorem of Statistical Learning, which shows these perspectives are equivalent: a hypothesis class is learnable if and only if its VC dimension is finite.

---

The Learning Problem

We begin by formalizing the setup that machine learning algorithms operate in. The formalization may seem pedantic at first, but each definition isolates an assumption that will matter when we prove our main results.

The setup. We have an instance space $\mathcal{X}$ (the set of all possible inputs — think feature vectors in $\mathbb{R}^d$), a label space $\mathcal{Y} = \{0, 1\}$ (binary classification), and an unknown probability distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$ that governs the data-generating process. A hypothesis is a function $h: \mathcal{X} \to \mathcal{Y}$ — a candidate classifier. A hypothesis class $\mathcal{H}$ is a collection of hypotheses that our learning algorithm considers.

We observe a training sample $S = \{(x_1, y_1), \ldots, (x_n, y_n)\}$ drawn i.i.d. from $\mathcal{D}$. The fundamental tension: we can evaluate how well a hypothesis performs on $S$, but we care about how well it performs on fresh data from $\mathcal{D}$.

The true risk is the probability of misclassification on a fresh example drawn from $\mathcal{D}$. It is the quantity we want to minimize but cannot compute, since $\mathcal{D}$ is unknown.

The empirical risk is computable — it is the training error. For any fixed hypothesis $h$, the empirical risk is the average of i.i.d. Bernoulli random variables with mean $R(h)$, so by the law of large numbers, $\hat{R}_S(h) \to R(h)$ as $n \to \infty$. The question is: does this convergence happen uniformly over all $h \in \mathcal{H}$ simultaneously, and how fast?

ERM is the most natural learning strategy: pick the hypothesis that fits the training data best. Whether this strategy actually works — whether low training error implies low true error — depends on the hypothesis class $\mathcal{H}$, and characterizing when it works is the central goal of PAC theory.

Realizability is a strong assumption: it says our hypothesis class is rich enough to contain a perfect classifier. Most real-world problems are not realizable — the best classifier in $\mathcal{H}$ still makes some errors. We will handle both cases: the realizable setting first (where the analysis is cleaner), then the agnostic setting (where no assumptions are made about $\mathcal{D}$).

---

Realizable PAC Learning

We are now ready to state the central definition of this topic. The name “PAC” — Probably Approximately Correct — captures both sources of uncertainty: the sample is random (so guarantees are probabilistic, “probably”), and we cannot expect perfect accuracy from finite data (so we settle for approximation, “approximately”).

Let’s unpack this carefully. The definition quantifies over all distributions $\mathcal{D}$ (where $\mathcal{H}$ is realizable) and all accuracy/confidence parameters $\varepsilon, \delta$. It asks: is there a single algorithm $A$ and a sample size $n$ (depending on $\varepsilon, \delta$, and possibly $\mathcal{H}$, but not on $\mathcal{D}$) such that $A$ produces a hypothesis with true risk at most $\varepsilon$ with high probability? The algorithm does not know $\mathcal{D}$ — it only sees the sample $S$.

Our first main result shows that every finite hypothesis class is PAC learnable, and ERM is the learning algorithm.

The following code verifies the theoretical bound via Monte Carlo simulation. We create a finite hypothesis class of 50 linear classifiers in $\mathbb{R}^5$, run ERM on random samples of varying sizes, and compare the empirical success probability with the theoretical guarantee.

n_trials = 2000
H_size_sim = 50
d = 5
epsilon_target = 0.1

H_weights = rng.standard_normal((H_size_sim, d))
H_biases = rng.standard_normal(H_size_sim)
h_star_idx = 0  # First hypothesis is the ground truth

sample_sizes_sim = [10, 20, 50, 100, 200, 500]
empirical_success = []

for n_s in sample_sizes_sim:
    successes = 0
    for _ in range(n_trials):
        X_sim = rng.standard_normal((n_s, d))
        y_sim = (X_sim @ H_weights[h_star_idx] + H_biases[h_star_idx] > 0).astype(int)

        # ERM: find hypothesis with lowest training error
        best_h, best_err = None, float('inf')
        for h_idx in range(H_size_sim):
            preds = (X_sim @ H_weights[h_idx] + H_biases[h_idx] > 0).astype(int)
            err = np.mean(preds != y_sim)
            if err < best_err:
                best_err = err
                best_h = h_idx

        # Evaluate true risk on fresh test data
        X_test = rng.standard_normal((5000, d))
        y_test = (X_test @ H_weights[h_star_idx] + H_biases[h_star_idx] > 0).astype(int)
        true_risk = np.mean(
            (X_test @ H_weights[best_h] + H_biases[best_h] > 0).astype(int) != y_test
        )

        if true_risk <= epsilon_target:
            successes += 1

    empirical_success.append(successes / n_trials)

# Compare with theoretical bound: P(success) >= 1 - |H| * exp(-n * epsilon)
theoretical_bound = [
    1 - min(H_size_sim * np.exp(-n_s * epsilon_target), 1.0)
    for n_s in sample_sizes_sim
]

---

Agnostic PAC Learning

The realizable setting is instructive but unrealistic. In practice, we rarely know whether our hypothesis class contains a perfect classifier. The agnostic setting drops the realizability assumption entirely: the distribution $\mathcal{D}$ can be arbitrary, and the best hypothesis in $\mathcal{H}$ may still have nonzero risk. The goal shifts from finding a hypothesis with small absolute risk to finding one whose risk is close to the best achievable within $\mathcal{H}$.

The key technique for proving agnostic bounds is uniform convergence: ensuring that empirical risk approximates true risk simultaneously for all hypotheses in $\mathcal{H}$.

This proposition reduces the learning problem to a concentration problem: we need to show that $\hat{R}_S(h) \approx R(h)$ uniformly over $\mathcal{H}$. For finite classes, this follows directly from Hoeffding’s inequality and the union bound.

The following simulation illustrates uniform convergence empirically: we draw 50 random hypotheses, compute their empirical risks over 500 trials, and compare the distribution of the supremum gap $\sup_h |\hat{R}_S(h) - R(h)|$ against the Hoeffding + union bound prediction.

n_sample = 100
n_hyp = 50
rng2 = np.random.default_rng(123)

true_risks = rng2.beta(2, 5, n_hyp)
emp_risks = np.zeros((n_hyp, 500))

for trial in range(500):
    for h_idx in range(n_hyp):
        outcomes = rng2.binomial(1, true_risks[h_idx], n_sample)
        emp_risks[h_idx, trial] = outcomes.mean()

# Supremum gap over all hypotheses
sup_gap = np.max(np.abs(emp_risks - true_risks[:, None]), axis=0)

# Theoretical bound: Hoeffding + union bound
eps_theory = np.linspace(0.001, 0.4, 200)
p_exceed_hoeffding_ub = np.minimum(
    2 * n_hyp * np.exp(-2 * n_sample * eps_theory**2), 1.0
)

# Empirical exceedance probability for comparison
empirical_survival = [np.mean(sup_gap > e) for e in eps_theory]

PAC Bound Comparator

Realizable finiteAgnostic finiteVC boundRademacher

|H| (hypotheses): 100

VC dim d: 10

δ (failure prob): 0.0501

---

The VC Dimension

For finite hypothesis classes, the story is complete: both realizable and agnostic PAC learning are possible, with sample complexity logarithmic in $|\mathcal{H}|$. But most interesting hypothesis classes are infinite — the class of all linear classifiers in $\mathbb{R}^d$, for instance, has uncountably many elements. The union bound over $|\mathcal{H}|$ is useless when $|\mathcal{H}| = \infty$.

The key insight is that an infinite hypothesis class, when restricted to a finite sample, can only produce finitely many distinct labeling patterns. The effective complexity of $\mathcal{H}$ on $n$ points is not $|\mathcal{H}|$ but the number of distinct behaviors on those points. This leads us to the VC dimension.

Even if $\mathcal{H}$ is infinite, $\mathcal{H}_C$ is always finite — it has at most $2^m$ elements (the total number of possible binary labelings of $m$ points). The question is: for how large an $m$ can we achieve the maximum $|\mathcal{H}_C| = 2^m$?

Shattering means $\mathcal{H}$ is maximally expressive on $C$ — no matter how the points are labeled, some hypothesis in $\mathcal{H}$ fits perfectly. This is the combinatorial analog of overfitting: if $\mathcal{H}$ can shatter large sets, it can memorize arbitrary patterns, which makes generalization harder.

The VC dimension measures the largest set of points that $\mathcal{H}$ can label in all possible ways. It is a worst-case combinatorial measure: we only need one set of size $d$ that is shattered, but no set of size $d+1$ can be shattered. Let’s see some examples.

Shattering Explorer

Thresholds (d = 1)Intervals (d = 2)Linear classifiers (d = 3)Rectangles (d = 4)Reset

Total

—

Realized

—

|H_C|

Shattered?

—

VCdim = 1

The most important example for machine learning is linear classifiers, whose VC dimension has a clean characterization.

This result connects the VC dimension to the geometric dimension of the feature space: linear classifiers in $\mathbb{R}^d$ have VC dimension $d+1$. This is why the number of features matters for generalization — it directly controls the complexity of the hypothesis class.

---

Sauer–Shelah Lemma and Growth Functions

The VC dimension tells us the boundary at which shattering becomes impossible: $\mathcal{H}$ cannot shatter any set of size $d+1$ or larger. But we need a more quantitative statement: exactly how many labelings can $\mathcal{H}$ produce on a set of $m$ points when $m > d$? The growth function captures this.

The Sauer–Shelah lemma is the remarkable fact that once $\Pi_{\mathcal{H}}$ drops below $2^m$, it doesn’t just decrease slightly — it collapses from exponential to polynomial growth. This is the combinatorial engine that makes infinite hypothesis classes learnable.

The significance of Corollary 1 cannot be overstated. The growth function transitions from $\Pi_{\mathcal{H}}(m) = 2^m$ (exponential) for $m \leq d$ to $\Pi_{\mathcal{H}}(m) \leq (em/d)^d$ (polynomial in $m$ with degree $d$) for $m > d$. This phase transition at $m = d$ is what allows the VC theory to work: we can replace $|\mathcal{H}|$ in the union bound by $\Pi_{\mathcal{H}}(n) \leq (en/d)^d$, which is polynomial rather than infinite.

The following code computes the growth function exactly and demonstrates the phase transition:

from scipy.special import comb

m_range = np.arange(1, 31)

# Growth function for several VC dimensions
for d in [1, 2, 3, 5, 10]:
    growth = np.array([
        sum(comb(m, i, exact=True) for i in range(d + 1))
        for m in m_range
    ])

# Sauer-Shelah bound tightness
d = 3
m_range2 = np.arange(d, 51)
exact = np.array([
    sum(comb(m, i, exact=True) for i in range(d + 1))
    for m in m_range2
])
upper = (np.e * m_range2 / d) ** d  # Simplified bound

# Phase transition: ratio Pi(m) / 2^m drops at m = d
d_val = 5
m_range3 = np.arange(1, 25)
growth_exact = np.array([
    sum(comb(m, i, exact=True) for i in range(d_val + 1))
    for m in m_range3
])
ratio = growth_exact / 2.0**m_range3

Growth Function & Sauer–Shelah Bound

VC dimension d: 5

Show phase transition at m = d

---

The Fundamental Theorem of Statistical Learning

We now have all the ingredients to state the deepest result in PAC learning theory. The Fundamental Theorem shows that four seemingly different properties of a hypothesis class are equivalent — they are four views of the same underlying phenomenon.

The VC bound establishes uniform convergence for any class with finite VC dimension. Combined with Proposition 1 (uniform convergence implies agnostic PAC), this gives us one direction of the Fundamental Theorem. The full result establishes equivalence.

---

Rademacher Complexity

The VC dimension is a combinatorial complexity measure — it depends on $\mathcal{H}$ but not on the data distribution $\mathcal{D}$ or the specific sample $S$. This universality is a strength (the VC bound holds for all distributions) but also a weakness (the bound may be loose for specific distributions). Rademacher complexity provides a data-dependent alternative that can yield tighter bounds.

The intuition is simple: a complex hypothesis class can “fit random noise” — it can correlate with random labels. Rademacher complexity measures this ability.

The expression inside the expectation asks: given random signs $\sigma_i$, how well can the best function in $\mathcal{F}$ correlate with these signs? If $\mathcal{F}$ contains a function that correlates highly with random noise, the class is complex. If no function can do better than random chance, the class is simple.

The main result connects Rademacher complexity to generalization through two applications of concentration inequalities from the previous topic: McDiarmid’s inequality for the concentration step and symmetrization for the expectation bound.

Two structural results connect Rademacher complexity to our earlier measures.

Proposition 3 shows that the Rademacher bound is never worse than the VC bound (up to constants). But because $\hat{\mathfrak{R}}_S(\mathcal{F})$ depends on the specific sample $S$, it can be much tighter when the data has favorable structure — for instance, when the data is low-dimensional or when most hypotheses behave similarly on typical inputs.

The following code estimates empirical Rademacher complexity via Monte Carlo simulation:

def estimate_rademacher(H_preds, n_rad=500):
    """
    Estimate empirical Rademacher complexity via Monte Carlo.
    H_preds: (num_hypotheses, sample_size) predictions matrix
    n_rad: number of random sign trials
    Returns: mean of max correlation with random signs
    """
    n_s = H_preds.shape[1]
    maxcorr = []
    for _ in range(n_rad):
        sigma = rng.choice([-1, 1], size=n_s)
        maxcorr.append(np.max(H_preds @ sigma / n_s))
    return np.mean(maxcorr)

# How Rademacher complexity scales with |H|
n_data = 200
X_data = rng.standard_normal((n_data, 2))
H_sizes_test = [5, 10, 25, 50, 100, 200, 500]
rad_c = []

for H_s in H_sizes_test:
    W = rng.standard_normal((H_s, 2))
    b = rng.standard_normal(H_s)
    preds = np.sign(X_data @ W.T + b)
    rad_c.append(estimate_rademacher(preds.T))

# Compare with theoretical: O(sqrt(log|H| / n))
theory_rc = np.sqrt(2 * np.log(np.array(H_sizes_test)) / n_data)

---

Applications and Worked Examples

The abstract theory developed above has direct implications for understanding the generalization behavior of concrete machine learning methods. We discuss four applications.

Linear Classifiers

For halfspaces in $\mathbb{R}^d$, we know $\mathrm{VCdim} = d+1$ (Theorem 3). The VC bound gives sample complexity $O(d/\varepsilon^2)$ for agnostic PAC learning. This provides a formal justification for the common wisdom that the number of training examples should grow with the number of features. In practice, if we have $d = 100$ features and want $\varepsilon = 0.05$ accuracy, the VC bound suggests we need on the order of $100/0.0025 = 40{,}000$ samples — conservative, but in the right ballpark for linear methods on moderately difficult problems.

Neural Networks

The VC dimension of a neural network with $W$ real-valued weights is $O(W \log W)$ (due to Bartlett, Harvey, Liaw & Mehrabian, 2019). For a network with millions of parameters, this gives a sample complexity bound in the millions — but modern networks generalize well with far fewer samples than the VC theory predicts. This theory-practice gap is one of the most active research areas in learning theory. Several explanations have been proposed: the effective capacity of trained networks is much smaller than the architectural capacity, optimization with SGD implicitly regularizes, and the data distribution has favorable structure that tighter measures like Rademacher complexity can exploit.

Decision Trees

A decision tree with $k$ internal nodes on $d$-dimensional binary features has VC dimension at most $O(k \log(kd))$. This shows that the sample complexity scales with the tree complexity (number of splits), not with the ambient dimension $d$. Pruning a decision tree reduces its VC dimension, which the theory predicts should improve generalization — consistent with the well-known observation that unpruned trees overfit.

Structural Risk Minimization

The bias-complexity tradeoff (also called the bias-variance tradeoff in some contexts) is a direct consequence of the PAC framework. Given a nested sequence of hypothesis classes $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots$ with increasing VC dimensions $d_1 < d_2 < \cdots$:

• The approximation error $\min_{h \in \mathcal{H}_k} R(h)$ decreases with $k$ (larger classes contain better approximations).
• The estimation error (the generalization gap, bounded by the VC bound) increases with $k$ (larger classes are harder to learn from finite data).

Structural Risk Minimization (SRM) selects the hypothesis class $\mathcal{H}_{k^*}$ that minimizes the sum of empirical risk and the VC complexity penalty. This is the learning-theoretic justification for regularization: by controlling model complexity, we balance the two sources of error.

Structural Risk Minimization Dashboard

n (samples): 500

Approx. decay b: 0.08

δ (failure prob): 0.05

Optimal model complexity d* = 1 — balances approximation error (decreasing with complexity) against estimation error from the VC bound (increasing with complexity).

---

Connections & Further Reading

Connections Map

Topic	Domain	Relationship
Concentration Inequalities	Probability & Statistics	Direct prerequisite — Hoeffding + union bound give sample complexity for finite classes; McDiarmid’s inequality proves the Rademacher generalization bound
Measure-Theoretic Probability	Probability & Statistics	Foundational — the convergence hierarchy and expectation operator underpin the definitions of true risk and uniform convergence
PCA & Low-Rank Approximation	Linear Algebra	The VC dimension of linear subspace classifiers relates to effective dimension captured by PCA; sample covariance concentration connects to agnostic learning bounds
Simplicial Complexes	Topology	The combinatorial proof of Sauer–Shelah (induction on point removal) has structural analogues in extremal and topological combinatorics
Bayesian Nonparametrics	Probability & Statistics	Bayesian model selection provides an alternative to SRM for balancing model complexity; posterior contraction rates parallel PAC sample complexity

Key Notation Summary

Symbol	Meaning
$R(h) = \Pr_{(x,y) \sim \mathcal{D}}[h(x) \neq y]$	True risk (generalization error)
$\hat{R}_S(h) = \frac{1}{n}\sum_i \mathbf{1}[h(x_i) \neq y_i]$	Empirical risk (training error)
$h_S^{\mathrm{ERM}} = \arg\min_{h \in \mathcal{H}} \hat{R}_S(h)$	Empirical risk minimizer
$n_{\mathcal{H}}(\varepsilon, \delta)$	Sample complexity
$\mathcal{H}_C$	Restriction of $\mathcal{H}$ to set $C$
$\mathrm{VCdim}(\mathcal{H})$	Vapnik–Chervonenkis dimension
$\Pi_{\mathcal{H}}(m)$	Growth function (shattering coefficient)
$\hat{\mathfrak{R}}_S(\mathcal{F})$	Empirical Rademacher complexity
$\mathfrak{R}_n(\mathcal{F})$	Population Rademacher complexity