VC Dimension and the Fundamental Theorem of Statistical Learning — from Scratch

Definition (The Learning Problem)

• Instance space \(\mathcal{X}\): the set of all possible inputs (images, documents, feature vectors, etc.).
• Label space \(\mathcal{Y} = \{0, 1\}\): binary labels.
• Distribution \(\mathcal{D}\): an unknown probability distribution over \(\mathcal{X} \times \mathcal{Y}\). Nature draws \((x, y) \sim \mathcal{D}\).
• Hypothesis class \(\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}\): a fixed set of classifiers \(h : \mathcal{X} \to \{0,1\}\) that the learner is allowed to pick from.
• Training sample \(S = ((x_1, y_1), \ldots, (x_m, y_m))\): drawn i.i.d. from \(\mathcal{D}\).

Example (Spam Classification) Suppose \(\mathcal{X}\) = all possible emails and \(\mathcal{Y} = \{0, 1\}\) where 1 = spam. Nature has some distribution \(\mathcal{D}\) over (email, label) pairs — this captures both which emails show up and how they're labeled. We don't know \(\mathcal{D}\); we only see a training set of \(m\) labeled emails.

The true risk \(L_{\mathcal{D}}(h)\) is the probability that classifier \(h\) misclassifies a random future email. We never know this exactly — it involves all emails that could ever arrive.

The empirical risk \(L_S(h)\) is the fraction of training emails that \(h\) gets wrong. This we can compute.

The fundamental question: when does small \(L_S(h)\) guarantee small \(L_{\mathcal{D}}(h)\)?

Example (PAC Learning in Practice) Suppose \(\mathcal{H}\) = linear classifiers in \(\mathbb{R}^2\) and we want:

• \(\epsilon = 0.05\): the learner's error is within 5% of the best linear classifier.
• \(\delta = 0.01\): this guarantee holds 99% of the time.

PAC learnability means there's a magic number \(m_{\mathcal{H}}(0.05, 0.01)\) such that if we collect at least that many labeled examples, any distribution over \(\mathbb{R}^2 \times \{0,1\}\) will produce a training set from which a good classifier can be found.

If no such \(m\) exists (i.e., for any sample size, some adversarial distribution defeats the learner), then \(\mathcal{H}\) is not PAC learnable.

Example (Uniform vs. Pointwise) Imagine \(\mathcal{H} = \{h_1, h_2\}\) with two hypotheses, and you have \(m = 100\) training points.

• Pointwise: \(L_S(h_1)\) is close to \(L_{\mathcal{D}}(h_1)\), AND separately \(L_S(h_2)\) is close to \(L_{\mathcal{D}}(h_2)\). Each guarantee might hold with probability 0.99.
• Uniform: BOTH gaps are small at the same time, with probability 0.99. This is stronger because bad luck on \(h_1\) and bad luck on \(h_2\) might coincide.

With two hypotheses, the difference is minor (union bound costs a factor of 2). But when \(\mathcal{H}\) is infinite, pointwise convergence is essentially free (law of large numbers) while uniform convergence may or may not hold — and it's uniform convergence that determines whether ERM works.

Concrete Scenario Suppose \(\mathcal{H} = \{h_1, h_2, h_3\}\) and the true risks (which we can't see) are:

• \(L_{\mathcal{D}}(h_1) = 0.20\) — this is the best hypothesis (\(h^* = h_1\)).
• \(L_{\mathcal{D}}(h_2) = 0.35\).
• \(L_{\mathcal{D}}(h_3) = 0.50\).

Now suppose uniform convergence holds with \(\epsilon = 0.03\). This means every hypothesis's training error is within 0.03 of its true error. One possible training set might give:

• \(L_S(h_1) = 0.22\) (true: 0.20, gap: 0.02 \(\leq\) 0.03 \(\checkmark\))
• \(L_S(h_2) = 0.33\) (true: 0.35, gap: 0.02 \(\leq\) 0.03 \(\checkmark\))
• \(L_S(h_3) = 0.48\) (true: 0.50, gap: 0.02 \(\leq\) 0.03 \(\checkmark\))

ERM picks \(h_1\) (lowest training error: 0.22). The true error of ERM's pick is \(L_{\mathcal{D}}(h_1) = 0.20\). The best possible true error is also 0.20. ERM nailed it.

But what if the training errors shift around? Uniform convergence allows gaps up to \(\epsilon = 0.03\), so another training set might give:

• \(L_S(h_1) = 0.23\)
• \(L_S(h_2) = 0.32\)
• \(L_S(h_3) = 0.52\)

Now ERM picks \(h_1\) again (0.23 is still the lowest). True error of the pick is still 0.20. Fine.

Worst case: The gaps conspire maximally against us:

• \(L_S(h_1) = 0.23\) (true 0.20, shifted UP by 0.03)
• \(L_S(h_2) = 0.32\) (true 0.35, shifted DOWN by 0.03)
• \(L_S(h_3) = 0.47\) (true 0.50, shifted DOWN by 0.03)

Now ERM picks \(h_1\) (0.23 vs 0.32 vs 0.47 — still the smallest). Even in this worst case, ERM picks the right answer. But could it pick the wrong one?

Near-worst case with a different class: Suppose \(L_{\mathcal{D}}(h_1) = 0.20\) and \(L_{\mathcal{D}}(h_2) = 0.22\). With \(\epsilon = 0.03\):

• \(L_S(h_1) = 0.23\) (shifted up by 0.03)
• \(L_S(h_2) = 0.19\) (shifted down by 0.03)

ERM picks \(h_2\) (training error 0.19 < 0.23). The true error of ERM's pick is 0.22, while optimal is 0.20. The gap is 0.02, which is less than \(2\epsilon = 0.06\). ERM picked the "wrong" hypothesis, but its true error is still close to optimal.

Uniform Convergence \(\Rightarrow\) ERM Works (The Three-Step Argument)

Assume uniform convergence: \(|L_S(h) - L_{\mathcal{D}}(h)| \leq \epsilon\) for every \(h \in \mathcal{H}\).

Let \(\hat{h}\) be the hypothesis ERM picks (minimizes training error), and let \(h^*\) be the truly best hypothesis (minimizes true error). We want to show \(L_{\mathcal{D}}(\hat{h})\) is close to \(L_{\mathcal{D}}(h^*)\).

Step 1. \(L_{\mathcal{D}}(\hat{h}) \leq L_S(\hat{h}) + \epsilon\).

Why: Uniform convergence says training error is within \(\epsilon\) of true error for every hypothesis, including \(\hat{h}\). So \(L_{\mathcal{D}}(\hat{h}) - L_S(\hat{h}) \leq \epsilon\), which rearranges to give Step 1. (The true error of ERM's pick can't be much worse than its training error.)

Step 2. \(L_S(\hat{h}) \leq L_S(h^*)\).

Why: This is just the definition of ERM. ERM picks \(\hat{h}\) to have the lowest training error among all hypotheses. So its training error is at most that of any other hypothesis, including \(h^*\). (This step has nothing to do with uniform convergence — it's purely about what ERM does.)

Step 3. \(L_S(h^*) \leq L_{\mathcal{D}}(h^*) + \epsilon\).

Why: Uniform convergence again, this time applied to \(h^*\). The training error of \(h^*\) is within \(\epsilon\) of its true error. (The training error of the best hypothesis can't be much higher than its true error.)

Chaining Steps 1–3:

$$ \underbrace{L_{\mathcal{D}}(\hat{h})}_{\text{true error of ERM's pick}} \leq \underbrace{L_S(\hat{h})}_{\text{training error of ERM's pick}} + \epsilon \leq \underbrace{L_S(h^*)}_{\text{training error of best}} + \epsilon \leq \underbrace{L_{\mathcal{D}}(h^*)}_{\text{true error of best}} + 2\epsilon. $$

Verifying with Numbers From the near-worst-case example above: \(L_{\mathcal{D}}(h_1) = 0.20\), \(L_{\mathcal{D}}(h_2) = 0.22\), \(\epsilon = 0.03\). ERM picked \(\hat{h} = h_2\) with \(L_S(h_2) = 0.19\).

• Step 1: \(L_{\mathcal{D}}(h_2) = 0.22 \leq 0.19 + 0.03 = 0.22\). \(\checkmark\)
• Step 2: \(L_S(h_2) = 0.19 \leq L_S(h_1) = 0.23\). \(\checkmark\) (ERM picked \(h_2\) because 0.19 < 0.23.)
• Step 3: \(L_S(h_1) = 0.23 \leq 0.20 + 0.03 = 0.23\). \(\checkmark\)

Chain: \(0.22 \leq 0.19 + 0.03 \leq 0.23 + 0.03 \leq 0.20 + 0.06\). That is, \(0.22 \leq 0.26\).

ERM's true error (0.22) is within \(2\epsilon = 0.06\) of optimal (0.20). The actual gap is 0.02, well within the bound. The bound is loose here, but it's a worst-case guarantee that holds no matter how the errors shift around.

Example 1 Suppose a company's average salary is $60,000. What can we say about the fraction of employees earning at least $200,000?

Markov says: \(\Pr(\text{Salary} \geq 200{,}000) \leq 60{,}000 / 200{,}000 = 0.3.\) At most 30% of employees earn $200K+. The bound is loose but completely distribution-free.

Proof

Step 1: Convexity bound. Since \(e^{sx}\) is convex and \(x \in [a, b]\), the function lies below the chord connecting \((a, e^{sa})\) and \((b, e^{sb})\):

$$ e^{sx} \leq \frac{b - x}{b - a}\, e^{sa} + \frac{x - a}{b - a}\, e^{sb}. $$

Step 2: Take expectations. Using \(\mathbb{E}[X] = 0\):

$$ \mathbb{E}[e^{sX}] \leq \frac{b}{b-a}\, e^{sa} + \frac{-a}{b-a}\, e^{sb}. $$

Step 3: Simplify with substitution. Let \(p = \frac{-a}{b-a}\) (so \(1 - p = \frac{b}{b-a}\)) and \(u = s(b-a)\). Then:

$$ \mathbb{E}[e^{sX}] \leq (1 - p)\, e^{-pu} + p\, e^{(1-p)u} = e^{-pu}\bigl(1 - p + p\, e^{u}\bigr). $$

Define \(\varphi(u) = -pu + \ln(1 - p + pe^{u})\), so the bound is \(\mathbb{E}[e^{sX}] \leq e^{\varphi(u)}\).

Step 4: Taylor bound on \(\varphi\). We compute:

• \(\varphi(0) = 0\),
• \(\varphi'(u) = -p + \frac{pe^{u}}{1 - p + pe^{u}}\), so \(\varphi'(0) = -p + p = 0\),
• \(\varphi''(u) = \frac{pe^u(1-p)}{(1 - p + pe^u)^2}\).

Writing \(t = \frac{pe^u}{1-p+pe^u} \in (0,1)\), we get \(\varphi''(u) = t(1-t) \leq \frac{1}{4}\).

By Taylor's theorem with the Lagrange remainder: \(\varphi(u) = \varphi(0) + \varphi'(0)\,u + \frac{1}{2}\varphi''(c)\,u^2\) for some \(c\). Since \(\varphi''(c) \leq 1/4\):

$$ \varphi(u) \leq \frac{u^2}{8} = \frac{s^2(b-a)^2}{8}. \quad \square $$

Proof

Let \(S_n = \sum_{i=1}^n X_i\). We bound \(\Pr(S_n - \mathbb{E}[S_n] \geq nt)\).

Step 1: Chernoff trick. For any \(s > 0\):

$$ \Pr(S_n - \mathbb{E}[S_n] \geq nt) = \Pr\!\left(e^{s(S_n - \mathbb{E}[S_n])} \geq e^{snt}\right) \leq e^{-snt}\, \mathbb{E}\!\left[e^{s(S_n - \mathbb{E}[S_n])}\right] $$

where the last step is Markov's inequality applied to the non-negative random variable \(e^{s(S_n - \mathbb{E}[S_n])}\).

Step 2: Factor by independence. Since \(X_1, \ldots, X_n\) are independent:

$$ \mathbb{E}\!\left[e^{s(S_n - \mathbb{E}[S_n])}\right] = \prod_{i=1}^n \mathbb{E}\!\left[e^{s(X_i - \mathbb{E}[X_i])}\right]. $$

Step 3: Apply Hoeffding’s lemma. Each \(X_i - \mathbb{E}[X_i]\) is zero-mean and bounded in an interval of width \(b_i - a_i\), so:

$$ \mathbb{E}\!\left[e^{s(X_i - \mathbb{E}[X_i])}\right] \leq \exp\!\left(\frac{s^2(b_i - a_i)^2}{8}\right). $$

Step 4: Combine and optimize.

$$ \Pr(S_n - \mathbb{E}[S_n] \geq nt) \leq \exp\!\left(-snt + \frac{s^2}{8}\sum_{i=1}^n (b_i - a_i)^2\right). $$

The exponent is a quadratic in \(s\), minimized at \(s^* = \frac{4nt}{\sum (b_i - a_i)^2}\). Substituting:

$$ \Pr(\bar{X} - \mathbb{E}[\bar{X}] \geq t) \leq \exp\!\left(\frac{-2n^2 t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right). \quad \square $$

Example (Coin Flips Revisited) Flip a fair coin \(n = 100\) times. Each \(X_i \in \{0,1\}\), so \(b_i - a_i = 1\) and \(\mathbb{E}[\bar{X}] = 0.5\). What is \(\Pr(\bar{X} \geq 0.9)\)?

Hoeffding: \(\Pr(\bar{X} - 0.5 \geq 0.4) \leq e^{-2 \cdot 100 \cdot 0.16} = e^{-32} \approx 1.3 \times 10^{-14}\).

Compare this to Markov's bound of \(\approx 0.556\) from earlier. Hoeffding is astronomically tighter because it uses independence and boundedness, not just the mean.

Proof

Step 1: Fix a single \(h\). The empirical risk \(L_S(h) = \frac{1}{m}\sum_{i=1}^m \mathbf{1}[h(x_i) \neq y_i]\) is the average of \(m\) i.i.d. random variables, each in \([0, 1]\), with mean \(L_{\mathcal{D}}(h)\). By Hoeffding's two-sided inequality:

$$ \Pr\!\left[|L_S(h) - L_{\mathcal{D}}(h)| > \epsilon\right] \leq 2e^{-2m\epsilon^2}. $$

Step 2: Union bound over \(\mathcal{H}\).

$$ \Pr\!\left[\exists\, h \in \mathcal{H} : |L_S(h) - L_{\mathcal{D}}(h)| > \epsilon\right] \leq \sum_{h \in \mathcal{H}} 2e^{-2m\epsilon^2} = 2|\mathcal{H}|\, e^{-2m\epsilon^2}. \quad \square $$

Example (Thresholds) \(\mathcal{H} = \{h_a : h_a(x) = \mathbf{1}[x \geq a],\ a \in \mathbb{R}\}\).

\(\operatorname{VCdim} \geq 1\): Take \(C = \{5\}\). Setting \(a = 3\) gives label 1; setting \(a = 7\) gives label 0. Both labelings are realized. \(\checkmark\)

\(\operatorname{VCdim} \leq 1\): Take any \(C = \{x_1, x_2\}\) with \(x_1 < x_2\). The labeling \((1, 0)\) — where \(x_1\) is labeled 1 and \(x_2\) is labeled 0 — requires \(x_1 \geq a\) and \(x_2 < a\), which is impossible since \(x_1 < x_2\). So no two-element set is shattered.

Conclusion: \(\operatorname{VCdim}(\mathcal{H}) = 1\).

Example (Intervals) \(\mathcal{H} = \{h_{a,b} : h_{a,b}(x) = \mathbf{1}[a \leq x \leq b],\ a \leq b\}\).

\(\operatorname{VCdim} \geq 2\): Take \(C = \{1, 3\}\).

• Label \((0,0)\): choose \(a = 5, b = 6\) (interval misses both).
• Label \((1,0)\): choose \(a = 0.5, b = 1.5\) (hits only 1).
• Label \((0,1)\): choose \(a = 2.5, b = 3.5\) (hits only 3).
• Label \((1,1)\): choose \(a = 0.5, b = 3.5\) (hits both).

All four labelings realized. \(\checkmark\)

\(\operatorname{VCdim} \leq 2\): Take any \(C = \{x_1, x_2, x_3\}\) with \(x_1 < x_2 < x_3\). The labeling \((1, 0, 1)\) requires \(x_1, x_3\) inside the interval but \(x_2\) outside it. Since intervals are contiguous, this is impossible.

Conclusion: \(\operatorname{VCdim}(\mathcal{H}) = 2\).

Proof of Radon’s Theorem

The goal. We want to split \(d+2\) points into two groups \(I\) and \(J\) and find a point \(q\) that is simultaneously in the convex hull of both groups. That means we need:

$$ q = \sum_{i \in I} \alpha_i\, p_i = \sum_{j \in J} \beta_j\, p_j $$

where the \(\alpha_i\) are non-negative and sum to 1 (making the left side a convex combination of the \(I\)-points) and the \(\beta_j\) are non-negative and sum to 1 (making the right side a convex combination of the \(J\)-points).

The trick is to rewrite this condition in a form that linear algebra can hand us for free.

Step 1: Reformulate as a single equation. Move everything to one side:

$$ \sum_{i \in I} \alpha_i\, p_i - \sum_{j \in J} \beta_j\, p_j = 0. $$

Define new variables: \(\lambda_i = \alpha_i\) for \(i \in I\) (positive) and \(\lambda_j = -\beta_j\) for \(j \in J\) (negative). Then the equation becomes:

$$ \sum_{k=1}^{d+2} \lambda_k\, p_k = 0. \qquad \text{(Equation 1)} $$

What about the constraint that the \(\alpha\)'s sum to 1 and the \(\beta\)'s sum to 1? That means \(\sum_{i \in I} \alpha_i - \sum_{j \in J} \beta_j = 1 - 1 = 0\), which in terms of the \(\lambda\)'s is:

$$ \sum_{k=1}^{d+2} \lambda_k = 0. \qquad \text{(Equation 2)} $$

So the two equations together are exactly the condition for overlapping convex hulls, repackaged into a form where all the unknowns \((\lambda_1, \ldots, \lambda_{d+2})\) appear in one system. The positive \(\lambda\)'s correspond to one group, the negative \(\lambda\)'s to the other.

But we don't yet know the partition \((I, J)\) — that's what we're trying to find! The insight: solve the linear system first, then read off the partition from the signs of the solution.

Step 2: The system always has a non-trivial solution. Let's count equations vs. unknowns:

• Equation 1 (\(\sum \lambda_k p_k = 0\)): Since each \(p_k \in \mathbb{R}^d\), this is really \(d\) scalar equations, one per coordinate. In \(\mathbb{R}^2\) for example, it splits into an \(x\)-equation and a \(y\)-equation.
• Equation 2 (\(\sum \lambda_k = 0\)): This is 1 scalar equation.

Total: \(d + 1\) equations in \(d + 2\) unknowns. Since there are more unknowns than equations, the system is underdetermined: linear algebra guarantees at least one non-trivial solution exists. (Formally: the null space of a \((d+1) \times (d+2)\) matrix has dimension \(\geq 1\).)

Step 3: Read off the partition. Fix a non-trivial solution \((\lambda_1, \ldots, \lambda_{d+2})\). Equation 2 says \(\sum \lambda_k = 0\), and not all \(\lambda_k\) are zero, so there must be at least one positive and at least one negative \(\lambda_k\). (If they were all \(\geq 0\) and summed to zero, they'd all be zero — contradicting non-triviality.) Define:

$$ I = \{k : \lambda_k > 0\}, \qquad J = \{k : \lambda_k \leq 0\}. $$

Both \(I\) and \(J\) are non-empty. Let \(\Lambda = \sum_{i \in I} \lambda_i\). Since \(\sum_k \lambda_k = 0\), we get \(\Lambda = -\sum_{j \in J} \lambda_j > 0\).

Step 4: Extract the intersection point. From Equation 1 (\(\sum \lambda_k p_k = 0\)), move the negative terms to the other side:

$$ \sum_{i \in I} \lambda_i\, p_i = -\sum_{j \in J} \lambda_j\, p_j = \sum_{j \in J} |\lambda_j|\, p_j. $$

Divide both sides by \(\Lambda\):

$$ \underbrace{\sum_{i \in I} \frac{\lambda_i}{\Lambda}\, p_i}_{\text{convex combination of } \{p_i\}_{i \in I}} = \underbrace{\sum_{j \in J} \frac{|\lambda_j|}{\Lambda}\, p_j}_{\text{convex combination of } \{p_j\}_{j \in J}}. $$

Why are these convex combinations?

• Left side: Each \(\lambda_i / \Lambda\) is positive (since \(i \in I\) means \(\lambda_i > 0\)), and they sum to \(\Lambda / \Lambda = 1\). So this is a weighted average of the \(I\)-points, which lies in \(\operatorname{conv}(\{p_i : i \in I\})\).
• Right side: Each \(|\lambda_j| / \Lambda\) is non-negative, and they sum to \((\sum_{j \in J} |\lambda_j|) / \Lambda = \Lambda / \Lambda = 1\). So this is a weighted average of the \(J\)-points, which lies in \(\operatorname{conv}(\{p_j : j \in J\})\).

Both sides are equal, so the common point lies in both convex hulls. \(\square\)

Radon’s Theorem: Worked Example in \(\mathbb{R}^2\)

Take the 4 points \(p_1 = (0,0),\ p_2 = (3,3),\ p_3 = (3,0),\ p_4 = (0,3)\) from the figure above. We need \(\lambda_1 p_1 + \lambda_2 p_2 + \lambda_3 p_3 + \lambda_4 p_4 = 0\) and \(\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 = 0\).

Writing out the equations:

• \(x\)-coordinates: \(0\lambda_1 + 3\lambda_2 + 3\lambda_3 + 0\lambda_4 = 0 \implies \lambda_2 + \lambda_3 = 0\).
• \(y\)-coordinates: \(0\lambda_1 + 3\lambda_2 + 0\lambda_3 + 3\lambda_4 = 0 \implies \lambda_2 + \lambda_4 = 0\).
• Sum: \(\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 = 0\).

From the first two: \(\lambda_3 = -\lambda_2\) and \(\lambda_4 = -\lambda_2\). Substituting into the sum: \(\lambda_1 + \lambda_2 - \lambda_2 - \lambda_2 = 0 \implies \lambda_1 = \lambda_2\).

Choose \(\lambda_2 = 1\): then \(\lambda_1 = 1,\ \lambda_3 = -1,\ \lambda_4 = -1\).

Partition: \(I = \{1, 2\}\) (positive \(\lambda\)'s), \(J = \{3, 4\}\) (negative \(\lambda\)'s). \(\Lambda = 1 + 1 = 2\).

Intersection point:

$$ \frac{1}{2}p_1 + \frac{1}{2}p_2 = \frac{1}{2}(0,0) + \frac{1}{2}(3,3) = (1.5, 1.5). $$ $$ \frac{1}{2}p_3 + \frac{1}{2}p_4 = \frac{1}{2}(3,0) + \frac{1}{2}(0,3) = (1.5, 1.5). \quad \checkmark $$

The midpoint of the diagonal \(p_1 p_2\) equals the midpoint of the diagonal \(p_3 p_4\). Both convex hulls pass through \((1.5, 1.5)\).

Proof that \(\operatorname{VCdim}(\text{halfspaces in } \mathbb{R}^d) \leq d + 1\)

Take any set of \(d+2\) points \(\{p_1, \ldots, p_{d+2}\} \subseteq \mathbb{R}^d\). By Radon's theorem, there is a partition into non-empty sets \(I\) and \(J\) with a point \(q \in \operatorname{conv}(\{p_i\}_{i \in I}) \cap \operatorname{conv}(\{p_j\}_{j \in J})\).

Consider the labeling that assigns 1 to all points in \(I\) and 0 to all points in \(J\). We'll show no halfspace can realize this labeling.

Suppose for contradiction that some halfspace \(h_{w,b}\) realizes it. Then:

• For all \(i \in I\): \(\langle w, p_i \rangle + b \geq 0\) (labeled 1).
• For all \(j \in J\): \(\langle w, p_j \rangle + b < 0\) (labeled 0).

Since \(q \in \operatorname{conv}(\{p_i\}_{i \in I})\), we can write \(q = \sum_{i \in I} \alpha_i p_i\) with \(\alpha_i \geq 0\) and \(\sum \alpha_i = 1\). Then:

$$ \langle w, q \rangle + b = \sum_{i \in I} \alpha_i \underbrace{(\langle w, p_i \rangle + b)}_{\geq\, 0} \geq 0. $$

Since \(q \in \operatorname{conv}(\{p_j\}_{j \in J})\), we can also write \(q = \sum_{j \in J} \beta_j p_j\) with \(\beta_j \geq 0\) and \(\sum \beta_j = 1\). Then:

$$ \langle w, q \rangle + b = \sum_{j \in J} \beta_j \underbrace{(\langle w, p_j \rangle + b)}_{<\, 0} < 0. $$

So \(\langle w, q \rangle + b\) is both \(\geq 0\) and \(< 0\). Contradiction.

Therefore the labeling "1 on \(I\), 0 on \(J\)" cannot be realized by any halfspace, so these \(d+2\) points are not shattered. Since the points were arbitrary, no set of \(d+2\) points can be shattered. \(\square\)

Concrete Failure in \(\mathbb{R}^2\)

With the 4 points from our Radon example, the labeling \(p_1 = 1, p_2 = 1, p_3 = 0, p_4 = 0\) asks for a line that puts \((0,0)\) and \((3,3)\) on one side and \((3,0)\) and \((0,3)\) on the other. But the segment from \((0,0)\) to \((3,3)\) and the segment from \((3,0)\) to \((0,3)\) cross at \((1.5, 1.5)\). Any line separating the two pairs would have to separate a point from itself. Impossible.

Example (Infinite VC Dimension) Let \(\mathcal{X} = \mathbb{R}\) and \(\mathcal{H} = \{0,1\}^{\mathbb{R}}\) (all functions from \(\mathbb{R}\) to \(\{0,1\}\)). Then for any set \(C\) of any size, every labeling is realized by some function. So \(\operatorname{VCdim}(\mathcal{H}) = \infty\).

As we'll see, this class is not PAC learnable — a hypothesis class that can represent anything can learn nothing.

Example: Intervals (\(d = 2\)) on \(m = 5\) Points With 5 points on the real line and the interval hypothesis class (VC dim = 2):

• Subsets of size 0: \(\binom{5}{0} = 1\) (the empty labeling).
• Subsets of size 1: \(\binom{5}{1} = 5\) (each individual point can be labeled 1 while the rest are 0).
• Subsets of size 2: \(\binom{5}{2} = 10\) (each pair of adjacent or non-adjacent points can form an interval — actually, intervals can only shatter contiguous pairs, but the bound counts all subsets of size \(\leq d\) as a worst-case upper bound).

Total: \(\Phi(5, 2) = 1 + 5 + 10 = 16\). And indeed, we verified earlier that intervals produce exactly 16 distinct patterns on 5 ordered points.

Numerical Checks at Scale

• \(d = 1, m = 10\): \(\Phi(10,1) = 1 + 10 = 11\), versus \(2^{10} = 1024\).
• \(d = 3, m = 10\): \(\Phi(10,3) = 1 + 10 + 45 + 120 = 176\), versus \(2^{10} = 1024\).
• \(d = 3, m = 100\): \(\Phi(100,3) = 1 + 100 + 4950 + 161700 = 166{,}751\), versus \(2^{100} \approx 10^{30}\).

For large \(m\), the growth function is \(O(m^d)\) instead of \(2^m\). This is a dramatic reduction: polynomial instead of exponential.

Proof of the Sauer–Shelah Lemma

We prove: for any finite set \(S\) with \(|S| = m\), \(|\mathcal{H}_S| \leq \Phi(m, d)\).

Induction on \(m\).

Base case \(m = 1\): \(|\mathcal{H}_S| \leq 2 = 1 + 1 = \Phi(1, d)\) for any \(d \geq 1\). If \(d = 0\), then \(\mathcal{H}\) cannot shatter any single point, so each point gets at most one label, giving \(|\mathcal{H}_S| \leq 1 = \Phi(1, 0)\). \(\checkmark\)

Inductive step. Fix a set \(S\) with \(|S| = m \geq 2\). Pick any point \(x \in S\) and let \(S' = S \setminus \{x\}\).

Partition the restriction patterns in \(\mathcal{H}_S\) according to how they behave on \(x\):

• Let \(\mathcal{H}_{S'}\) be the restriction of \(\mathcal{H}\) to \(S'\) (ignoring \(x\)). Each pattern in \(\mathcal{H}_{S'}\) is a sequence in \(\{0,1\}^{m-1}\).
• Some patterns on \(S'\) appear with both labels on \(x\) (both 0 and 1). Call the set of such patterns \(\mathcal{H}^{\pm}\).
• The remaining patterns on \(S'\) appear with only one label on \(x\).

Counting: Each pattern in \(\mathcal{H}_{S'} \setminus \mathcal{H}^{\pm}\) contributes 1 to \(|\mathcal{H}_S|\) (one label on \(x\)), and each pattern in \(\mathcal{H}^{\pm}\) contributes 2. So:

$$ |\mathcal{H}_S| = |\mathcal{H}_{S'}| + |\mathcal{H}^{\pm}|. $$

Key claim: \(\operatorname{VCdim}(\mathcal{H}^{\pm}) \leq d - 1\).

Why? Suppose \(\mathcal{H}^{\pm}\) shatters some set \(T \subseteq S'\). Then for every labeling of \(T\), there is a pattern in \(\mathcal{H}^{\pm}\) realizing it. By definition of \(\mathcal{H}^{\pm}\), each such pattern extends to both labels on \(x\). So for every labeling of \(T \cup \{x\}\), there is a hypothesis in \(\mathcal{H}\) realizing it. This means \(\mathcal{H}\) shatters \(T \cup \{x\}\), so \(|T| + 1 \leq d\), i.e., \(|T| \leq d - 1\).

Applying the inductive hypothesis:

• \(|\mathcal{H}_{S'}| \leq \Phi(m-1, d)\) (restriction to \(m-1\) points, VC dim at most \(d\)).
• \(|\mathcal{H}^{\pm}| \leq \Phi(m-1, d-1)\) (restriction to \(m-1\) points, VC dim at most \(d-1\)).

Finishing the induction: we need \(\Phi(m-1,d) + \Phi(m-1,d-1) = \Phi(m,d)\).

This is a "Pascal-style" identity for the function \(\Phi\). It's analogous to (and proved using) the classical Pascal's rule for binomial coefficients. Let's recall that first:

Pascal’s Rule (Reminder) For any \(n \geq 1\) and \(1 \leq k \leq n\): $$ \binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}. $$ Why: Consider \(n\) objects and count the subsets of size \(k\). Fix one object. Either it's not in the subset (choose \(k\) from the remaining \(n-1\): \(\binom{n-1}{k}\) ways) or it is (choose the other \(k-1\) from \(n-1\): \(\binom{n-1}{k-1}\) ways). These two cases are exhaustive and disjoint, so they sum to \(\binom{n}{k}\).

Now we show the identity step by step. First, expand both \(\Phi\) terms using their definitions:

$$ \Phi(m-1,d) + \Phi(m-1,d-1) = \underbrace{\sum_{i=0}^{d}\binom{m-1}{i}}_{\text{first sum}} + \underbrace{\sum_{i=0}^{d-1}\binom{m-1}{i}}_{\text{second sum}}. $$

The idea: we want to pair up terms from the two sums so that each pair collapses via Pascal's rule into a single \(\binom{m}{\cdot}\). The sums don't have the same number of terms (the first goes up to \(d\), the second up to \(d-1\)), so we'll peel off one extra term from the first sum and pair the rest.

Step 1: Peel off the \(i = 0\) term from the first sum.

$$ = \binom{m-1}{0} + \sum_{i=1}^{d}\binom{m-1}{i} + \sum_{i=0}^{d-1}\binom{m-1}{i}. $$

Step 2: Reindex the second sum. Substitute \(j = i + 1\), so when \(i\) goes from \(0\) to \(d-1\), \(j\) goes from \(1\) to \(d\), and \(\binom{m-1}{i} = \binom{m-1}{j-1}\):

$$ = \binom{m-1}{0} + \sum_{i=1}^{d}\binom{m-1}{i} + \sum_{j=1}^{d}\binom{m-1}{j-1}. $$

Now both sums run from \(1\) to \(d\). Rename \(j\) back to \(i\) in the second sum (it's just a dummy variable) and combine:

$$ = \binom{m-1}{0} + \sum_{i=1}^{d}\left[\binom{m-1}{i} + \binom{m-1}{i-1}\right]. $$

Step 3: Apply Pascal’s rule to each pair. For \(i \geq 1\): \(\binom{m-1}{i} + \binom{m-1}{i-1} = \binom{m}{i}\). So:

$$ = \underbrace{\binom{m-1}{0}}_{= 1 = \binom{m}{0}} + \sum_{i=1}^{d}\binom{m}{i} = \sum_{i=0}^{d}\binom{m}{i} = \Phi(m, d). $$

(In the first step we used \(\binom{m-1}{0} = 1 = \binom{m}{0}\).)

So \(|\mathcal{H}_S| \leq \Phi(m-1, d) + \Phi(m-1, d-1) = \Phi(m, d)\). \(\square\)

Proof

Step 1. Consider the binomial expansion \((1 + t)^m = \sum_{i=0}^{m} \binom{m}{i} t^i\) for \(t > 0\). Since all terms are positive:

$$ \sum_{i=0}^{d}\binom{m}{i} t^i \leq (1 + t)^m. $$

Step 2. For \(i \leq d\) and \(0 < t \leq 1\), we have \(t^i \geq t^d\). So:

$$ t^d \sum_{i=0}^{d}\binom{m}{i} \leq \sum_{i=0}^{d}\binom{m}{i} t^i \leq (1+t)^m. $$

Step 3. Dividing by \(t^d\):

$$ \sum_{i=0}^{d}\binom{m}{i} \leq \frac{(1+t)^m}{t^d}. $$

Step 4. Set \(t = d/m\) (which is \(\leq 1\) since \(m \geq d\)):

$$ \sum_{i=0}^{d}\binom{m}{i} \leq \frac{(1 + d/m)^m}{(d/m)^d} = \frac{(1 + d/m)^m \cdot m^d}{d^d}. $$

Step 5. The standard inequality \((1 + x/n)^n \leq e^x\) gives \((1 + d/m)^m \leq e^d\). So:

$$ \sum_{i=0}^{d}\binom{m}{i} \leq \frac{e^d \cdot m^d}{d^d} = \left(\frac{em}{d}\right)^d. \quad \square $$

The Ghost Sample Trick (Vapnik & Chervonenkis, 1971)

Imagine you had a second, independent training set \(S' = ((x'_1, y'_1), \ldots, (x'_m, y'_m))\) drawn from the same distribution \(\mathcal{D}\). You don't actually have this sample — it's a thought experiment. But since \(S'\) is drawn from \(\mathcal{D}\), its empirical risk \(L_{S'}(h)\) is an unbiased estimate of the true risk \(L_{\mathcal{D}}(h)\).

So instead of comparing \(L_S(h)\) to the unknowable \(L_{\mathcal{D}}(h)\), compare it to the concrete \(L_{S'}(h)\). If \(L_S(h)\) is far from \(L_{\mathcal{D}}(h)\), then with decent probability, \(L_S(h)\) is also far from \(L_{S'}(h)\) — because \(L_{S'}(h)\) is close to \(L_{\mathcal{D}}(h)\).

Proof

Setup. Suppose the bad event occurs: \(\sup_h (L_{\mathcal{D}}(h) - L_S(h)) > \epsilon\). This means there exists a hypothesis \(h^*\) with \(L_{\mathcal{D}}(h^*) > L_S(h^*) + \epsilon\). The true error of \(h^*\) is much bigger than its training error — \(h^*\) is overfitting.

Step 1: The ghost sample probably agrees with the truth. Draw \(S'\) independently from \(\mathcal{D}\). Since \(L_{S'}(h^*)\) is the average of \(m\) i.i.d. Bernoulli random variables with mean \(L_{\mathcal{D}}(h^*)\), Hoeffding's inequality gives:

$$ \Pr_{S'}\!\left[L_{S'}(h^*) < L_{\mathcal{D}}(h^*) - \frac{\epsilon}{2}\right] \leq e^{-2m(\epsilon/2)^2} = e^{-m\epsilon^2/2}. $$

For \(m \geq 2/\epsilon^2\), the exponent is \(\leq -1\), so this probability is \(\leq e^{-1} < 1/2\). Therefore:

$$ \Pr_{S'}\!\left[L_{S'}(h^*) \geq L_{\mathcal{D}}(h^*) - \frac{\epsilon}{2}\right] \geq \frac{1}{2}. $$

In plain English: the ghost sample's error for \(h^*\) is within \(\epsilon/2\) of the true error, with probability at least \(1/2\).

Step 2: Chain the inequalities. When the ghost concentrates (which happens with probability \(\geq 1/2\)):

$$ L_{S'}(h^*) \geq L_{\mathcal{D}}(h^*) - \frac{\epsilon}{2} > \left(L_S(h^*) + \epsilon\right) - \frac{\epsilon}{2} = L_S(h^*) + \frac{\epsilon}{2}. $$

So \(L_{S'}(h^*) - L_S(h^*) > \epsilon/2\), which means \(\sup_h (L_{S'}(h) - L_S(h)) > \epsilon/2\).

Step 3: Combine the two events into one probability.

Let's name the two events to keep things clear:

• Event \(A\) (the "bad event," depends on \(S\)): \(\sup_h (L_{\mathcal{D}}(h) - L_S(h)) > \epsilon\).
• Event \(B\) (the "ghost event," depends on \(S\) and \(S'\)): \(\sup_h (L_{S'}(h) - L_S(h)) > \epsilon/2\).

Steps 1–2 proved: whenever \(A\) happens, \(B\) happens with probability \(\geq 1/2\) over \(S'\). Written as a conditional probability:

$$ \Pr_{S'}[B \mid A] \geq \frac{1}{2}. $$

Now we use the definition of conditional probability. Recall that \(\Pr[B \mid A] = \Pr[A \text{ and } B] / \Pr[A]\), so:

$$ \Pr[A \text{ and } B] = \Pr[A] \cdot \Pr[B \mid A]. $$

Since \(A \text{ and } B\) implies \(B\) (if both happen, then certainly \(B\) happens):

$$ \Pr[B] \geq \Pr[A \text{ and } B] = \Pr[A] \cdot \Pr[B \mid A] \geq \Pr[A] \cdot \frac{1}{2}. $$

Rearranging:

$$ \Pr[A] \leq 2 \cdot \Pr[B]. $$

Substituting back the event names:

$$ \underbrace{\Pr_S\!\left[\sup_h (L_{\mathcal{D}}(h) - L_S(h)) > \epsilon\right]}_{\text{what we want to bound}} \leq 2 \cdot \underbrace{\Pr_{S,S'}\!\left[\sup_h (L_{S'}(h) - L_S(h)) > \frac{\epsilon}{2}\right]}_{\text{no longer involves } L_{\mathcal{D}}}. \quad \square $$

Analogy: The Exam Trick

Imagine a student (hypothesis \(h^*\)) who scores 95% on their practice test (\(L_S = 0.05\)) but actually knows only 70% of the material (\(L_{\mathcal{D}} = 0.30\)). They got lucky: the practice test happened to avoid their weak spots.

Now give them a second, independent practice test (\(S'\)). Since the second test is also drawn from the full material, the student will probably score around 70% again (\(L_{S'} \approx 0.30\)). The gap between their two scores (\(0.30 - 0.05 = 0.25\)) reveals the overfitting, even though we never knew the true difficulty.

That's symmetrization: replace the unknowable "true exam" with a second random exam, and the cheater is caught.

Proof Roadmap (4 Steps)

1. Symmetrize: Replace \(\Pr[\text{gap with } L_{\mathcal{D}}]\) by \(\Pr[\text{gap between two samples}]\). Cost: factor of 2 and \(\epsilon \to \epsilon/2\).
2. Fix the pool: Condition on the combined \(2m\) data points. Now the only randomness is which half goes to \(S\) vs \(S'\).
3. Count behaviors: On these \(2m\) fixed points, Sauer–Shelah says at most \(\Pi_{\mathcal{H}}(2m)\) hypotheses behave differently. So we've reduced an infinite class to a finite one.
4. Union bound + Hoeffding: For each of the \(\leq \Pi_{\mathcal{H}}(2m)\) distinct behaviors, apply Hoeffding to the random partition. Union bound over all behaviors.

Proof

Step 1: Symmetrize. By the symmetrization lemma from Section 9 (applied to both the upper and lower tails, which adds another factor of 2):

$$ \Pr_S\!\left[\sup_h |L_S(h) - L_{\mathcal{D}}(h)| > \epsilon\right] \leq 2\, \Pr_{S,S'}\!\left[\sup_h |L_S(h) - L_{S'}(h)| > \frac{\epsilon}{2}\right]. $$

We've traded the unknowable \(L_{\mathcal{D}}\) for the concrete \(L_{S'}\). Now both sides of the gap are empirical quantities computed on actual data points.

Step 2: Fix the pool and randomize over the partition. Let \(C = (z_1, \ldots, z_{2m})\) be the combined pool of all \(2m\) data points from \(S\) and \(S'\) together. We condition on \(C\) — that is, we treat these \(2m\) points as fixed and known.

What's still random? Only the split: which \(m\) of the \(2m\) points end up in \(S\) and which end up in \(S'\). This is a uniformly random partition of a fixed pool into two equal halves.

For a fixed hypothesis \(h\), once we know \(C\), we know exactly which points \(h\) gets right and which it gets wrong. Specifically, define the binary vector:

$$ v_h = (\mathbf{1}[h(x_1) \neq y_1],\ \mathbf{1}[h(x_2) \neq y_2],\ \ldots,\ \mathbf{1}[h(x_{2m}) \neq y_{2m}]) \in \{0,1\}^{2m}. $$

This vector records the right/wrong pattern of \(h\) on all \(2m\) points. The difference \(L_S(h) - L_{S'}(h)\) then depends only on \(v_h\) and on which points go to \(S\) vs \(S'\):

$$ L_S(h) - L_{S'}(h) = \frac{\text{(mistakes by } h \text{ on } S\text{)}}{m} - \frac{\text{(mistakes by } h \text{ on } S'\text{)}}{m}. $$

If the random partition sends more of \(h\)'s mistakes to \(S\) than to \(S'\), this difference is positive; if it sends more to \(S'\), it's negative. On average (over random partitions), it's zero.

Step 3: Count distinct behaviors (this is where Sauer–Shelah enters). Here's the key observation: two hypotheses \(h_1\) and \(h_2\) with the same binary vector \(v_{h_1} = v_{h_2}\) will have exactly the same value of \(L_S(h) - L_{S'}(h)\) for every partition. They are indistinguishable on these \(2m\) points.

So the number of distinct behaviors we need to worry about is not \(|\mathcal{H}|\) (which may be infinite), but the number of distinct binary vectors \(v_h\), which is \(|\mathcal{H}_{C_x}|\) (the restriction of \(\mathcal{H}\) to the input points of \(C\)). By the definition of the growth function:

$$ |\mathcal{H}_{C_x}| \leq \Pi_{\mathcal{H}}(2m). $$

By Sauer–Shelah: \(\Pi_{\mathcal{H}}(2m) \leq (2em/d)^d\). We've collapsed an infinite class into at most \((2em/d)^d\) distinct behaviors — a finite number that grows only polynomially in \(m\).

Step 4: Hoeffding for each behavior, then union bound. Fix one behavior pattern \(v \in \{0,1\}^{2m}\). The difference \(L_S(h) - L_{S'}(h)\) is now a function of the random partition only. Think of it this way: we have \(2m\) coins (the entries of \(v\)), and we randomly deal \(m\) of them to pile \(S\) and the other \(m\) to pile \(S'\). The difference in pile averages is the average of \(2m\) terms, each bounded by \(1/m\), with the randomness coming from the assignment.

By Hoeffding's inequality applied to this random partition:

$$ \Pr_{\text{partition}}\!\left[|L_S(h) - L_{S'}(h)| > \frac{\epsilon}{2}\ \Big|\ C\right] \leq 2\exp\!\left(\frac{-2(\epsilon/2)^2}{\sum_{k=1}^{2m}(1/m)^2}\right) = 2\exp\!\left(\frac{-\epsilon^2/2}{2m/m^2}\right) = 2e^{-m\epsilon^2/4}. $$

Wait, where did \(e^{-m\epsilon^2/8}\) in the theorem come from instead of \(e^{-m\epsilon^2/4}\)? The exact constant depends on how carefully you handle the partition (the \(\sigma_k\) are not fully independent due to the constraint that exactly \(m\) go to each side). A more careful analysis gives \(2e^{-m\epsilon^2/8}\). The important point is that it's exponential in \(m\).

Now union bound over all \(\leq \Pi_{\mathcal{H}}(2m)\) distinct behavior patterns:

$$ \Pr_{\text{partition}}\!\left[\sup_h |L_S(h) - L_{S'}(h)| > \frac{\epsilon}{2}\ \Big|\ C\right] \leq 2\, \Pi_{\mathcal{H}}(2m)\, e^{-m\epsilon^2/8}. $$

This holds for every fixed pool \(C\), so it also holds unconditionally (averaging over \(C\) can only preserve or tighten the bound). Combining with the factor of 2 from Step 1:

$$ \Pr_S\!\left[\sup_h |L_S(h) - L_{\mathcal{D}}(h)| > \epsilon\right] \leq 2 \times 2\, \Pi_{\mathcal{H}}(2m)\, e^{-m\epsilon^2/8} = 4\, \Pi_{\mathcal{H}}(2m)\, e^{-m\epsilon^2/8}. $$

Applying Sauer–Shelah: \(\Pi_{\mathcal{H}}(2m) \leq (2em/d)^d\). \(\square\)

$$ m = O\!\left(\frac{d \ln(m/d) + \ln(1/\delta)}{\epsilon^2}\right) $$

Absorbing the mild logarithmic dependence on \(m\): \(\displaystyle m = O\!\left(\frac{d + \ln(1/\delta)}{\epsilon^2}\right)\) suffices for uniform convergence.

Example: How Many Emails Do You Need?

You're building a spam classifier using linear classifiers in \(\mathbb{R}^{50}\) (50 features extracted from each email). VC dimension: \(d = 51\).

Scenario 1: You want the training error to be within \(\epsilon = 0.05\) (5%) of the true error, with 95% confidence (\(\delta = 0.05\)).

$$ m \approx \frac{51 + \ln(20)}{2 \times 0.0025} = \frac{51 + 3}{0.005} = \frac{54}{0.005} = 10{,}800 \text{ emails.} $$

With about 11,000 labeled emails, you can trust that every linear classifier's training error is within 5% of its true error. ERM will find one that's within 10% of optimal (the \(2\epsilon\) from the ERM argument in Section 1).

Scenario 2: You tighten to \(\epsilon = 0.01\) (1% accuracy).

$$ m \approx \frac{54}{2 \times 0.0001} = \frac{54}{0.0002} = 270{,}000 \text{ emails.} $$

5x tighter accuracy costs 25x more data (the \(1/\epsilon^2\) scaling). This is why practitioners often settle for "good enough" accuracy rather than demanding perfection.

Scenario 3: You boost confidence to \(\delta = 0.001\) (99.9%) while keeping \(\epsilon = 0.05\).

$$ m \approx \frac{51 + \ln(1000)}{0.005} = \frac{51 + 6.9}{0.005} = \frac{57.9}{0.005} = 11{,}580 \text{ emails.} $$

Going from 95% to 99.9% confidence only added ~800 emails. Confidence is cheap. Accuracy is expensive.

The Big Picture

The VC generalization bound resolves the fundamental tension in machine learning:

• Expressive classes (high VC dimension) can fit complex patterns but need lots of data to distinguish signal from noise.
• Simple classes (low VC dimension) generalize from little data but might miss real patterns.

The bound quantifies this tradeoff exactly: sample complexity scales linearly with VC dimension. And the fact that it depends on VC dimension (a finite number) rather than \(|\mathcal{H}|\) (potentially infinite) is what makes learning with infinite hypothesis classes possible at all. Linear classifiers in \(\mathbb{R}^{100}\) have VC dimension 101 — so despite there being uncountably many of them, about 10,000 samples suffice for generalization at 5% accuracy.

Proof

The proof constructs a specific adversarial distribution that defeats any learner. There are three key ideas: (1) use shattering to guarantee a perfect hypothesis exists, (2) hide the true labeling by choosing it at random, (3) show that unseen points are unpredictable.

Step 1: Choose the domain.

Since \(\operatorname{VCdim}(\mathcal{H}) = \infty\), for any number \(n\) we can find a set of size \(n\) that \(\mathcal{H}\) shatters. The learner will draw \(m\) training points, so pick \(n = 2m\) — twice the training set size. Let \(C = \{x_1, x_2, \ldots, x_{2m}\}\) be a set of \(2m\) points that \(\mathcal{H}\) shatters.

Why \(2m\)? We need enough points that, even after the learner sees \(m\) draws, a substantial fraction of \(C\) remains unseen. Choosing \(2m\) ensures (as we'll compute below) that roughly 60% of the points are never seen in the training sample.

Step 2: Choose a random labeling.

The adversary picks a labeling \(f : C \to \{0,1\}\) uniformly at random: each \(f(x_i)\) is an independent fair coin flip, with \(\Pr[f(x_i) = 0] = \Pr[f(x_i) = 1] = 1/2\). There are \(2^{2m}\) possible labelings, and we pick one uniformly.

Now define the distribution \(\mathcal{D}\) to be the uniform distribution on the labeled points \(\{(x_1, f(x_1)),\, (x_2, f(x_2)),\, \ldots,\, (x_{2m}, f(x_{2m}))\}\). Each draw from \(\mathcal{D}\) picks one of the \(2m\) labeled pairs uniformly at random.

Why does a perfect hypothesis exist? Because \(\mathcal{H}\) shatters \(C\), every possible labeling of \(C\) is realized by some \(h \in \mathcal{H}\). In particular, the random labeling \(f\) is realized by some \(h^* \in \mathcal{H}\) with \(h^*(x_i) = f(x_i)\) for all \(i\). This \(h^*\) gets every point right, so \(L_{\mathcal{D}}(h^*) = 0\).

Step 3: Count how many points the learner misses.

The learner draws a training sample \(S\) of \(m\) points, each drawn independently and uniformly from the \(2m\) points in \(C\) (with replacement, since that's how i.i.d. sampling works). Some points will appear multiple times; others won't appear at all. How many distinct points does the learner actually see?

Focus on a single point \(x_j \in C\). On each draw, the probability of picking \(x_j\) is \(1/(2m)\). The probability of not picking \(x_j\) on a single draw is \(1 - 1/(2m)\). Since the \(m\) draws are independent:

$$ \Pr[x_j \text{ never drawn}] = \left(1 - \frac{1}{2m}\right)^m. $$

This is a classic "birthday problem" style calculation. To evaluate this, recall the fundamental limit:

In our case, \(n = 2m\) and the exponent is \(m = n/2\), so:

$$ \left(1 - \frac{1}{2m}\right)^m = \left[\left(1 - \frac{1}{2m}\right)^{2m}\right]^{1/2} \approx \left[e^{-1}\right]^{1/2} = e^{-1/2} = \frac{1}{\sqrt{e}} \approx 0.6065. $$

So each individual point has about a 60.65% chance of being missed entirely!

The expected number of unseen points is (by linearity of expectation, summing over all \(2m\) points):

$$ \mathbb{E}[\text{unseen}] = 2m \cdot \left(1 - \frac{1}{2m}\right)^m \approx \frac{2m}{\sqrt{e}} \approx 1.213m. $$

And the expected number of seen (distinct) points is:

$$ \mathbb{E}[\text{seen}] = 2m - \mathbb{E}[\text{unseen}] = 2m\left[1 - \left(1 - \frac{1}{2m}\right)^m\right] \approx 2m\!\left(1 - \frac{1}{\sqrt{e}}\right) \approx 0.787m. $$

Step 4: Unseen points are unpredictable.

This is the heart of the argument. Consider a point \(x_j\) that the learner never sees in the training sample \(S\). What does the learner know about \(f(x_j)\)?

Absolutely nothing. Here's why: \(f(x_j)\) was chosen by an independent fair coin flip, and the learner's training data contains no information about this coin flip. The training sample tells the learner about \(f(x_i)\) for points that were drawn, but \(f(x_j)\) is independent of all those values (each label was an independent coin flip). So from the learner's perspective, \(f(x_j)\) is equally likely to be 0 or 1, regardless of what the learner saw in training.

This means that for any prediction the learner makes on \(x_j\) — whether it guesses 0 or 1 or flips its own coin — the probability of being wrong is exactly \(1/2\).

Step 5: Compute the expected error.

The learner's true error \(L_{\mathcal{D}}(A(S))\) is the probability of misclassifying a random point from \(\mathcal{D}\). Since \(\mathcal{D}\) is uniform on all \(2m\) points:

$$ L_{\mathcal{D}}(A(S)) = \frac{1}{2m}\sum_{i=1}^{2m} \mathbf{1}[A(S)(x_i) \neq f(x_i)]. $$

Split this into seen and unseen points:

$$ L_{\mathcal{D}}(A(S)) = \frac{1}{2m}\!\left(\sum_{x_i \in \text{seen}} \mathbf{1}[A(S)(x_i) \neq f(x_i)] \;+\; \sum_{x_j \in \text{unseen}} \mathbf{1}[A(S)(x_j) \neq f(x_j)]\right). $$

The first sum (seen points) is \(\geq 0\) — the learner might get them right, might not, but we don't need this term. The second sum is what gives us the lower bound. On each unseen point, the expected error is \(1/2\), so:

$$ \mathbb{E}[L_{\mathcal{D}}(A(S))] \;\geq\; \frac{1}{2m} \cdot \mathbb{E}[\text{unseen}] \cdot \frac{1}{2} \;=\; \frac{1}{2m} \cdot \frac{2m}{\sqrt{e}} \cdot \frac{1}{2} \;=\; \frac{1}{2\sqrt{e}} \;\approx\; 0.303. $$

Since \(\frac{1}{2\sqrt{e}} \approx 0.303 > 0.25 = \frac{1}{4}\), we conclude:

$$ \mathbb{E}_{S \sim \mathcal{D}^m}[L_{\mathcal{D}}(A(S))] \;\geq\; \frac{1}{2\sqrt{e}} \;\geq\; \frac{1}{4}. \quad \square $$

Concrete Scenario

Suppose \(\mathcal{H}\) is the class of all binary functions on \(\mathbb{R}\) (infinite VC dimension), and a learner gets \(m = 50\) training points.

• The adversary picks \(2m = 100\) points that \(\mathcal{H}\) shatters and a random labeling.
• The learner draws 50 points from these 100 (with replacement), seeing about \(100(1 - 0.95^{50}) \approx 100 \times 0.923 = 92.3\) — wait, let's compute correctly: \((1 - 1/100)^{50} = 0.99^{50} \approx 0.605\). So about \(100 \times 0.605 \approx 60.5\) points are unseen, and about 39.5 are seen.
• On the ~60.5 unseen points, the learner is guessing: expected error rate on those is 1/2.
• Overall expected error \(\geq 60.5/100 \times 1/2 \approx 0.303\), which exceeds \(1/4\).

The learner has seen less than 40% of the domain and is blind on the rest. No algorithm can beat random guessing on the unseen portion, because the labels there are independent coin flips that the training data reveals nothing about.

Why This Matters

The No-Free-Lunch theorem isn't saying "some algorithms are bad." It's saying all algorithms are bad when the hypothesis class is too expressive. The adversary's construction works against any algorithm \(A\) — neural networks, SVMs, decision trees, even algorithms that haven't been invented yet.

The reason is information-theoretic: with \(m\) samples from a domain of size \(2m\), the learner inevitably misses about 60% of the points. When the labeling is random and the unseen labels are independent of the seen ones, no amount of cleverness helps on the unseen portion.

Combined with Section 10 (finite VC dim \(\Rightarrow\) learnable), this gives us a complete characterization: a class is learnable if and only if its VC dimension is finite.

The Difference at a Glance

• PAC (realizable): "Assuming the answer is in \(\mathcal{H}\), find one that's close to perfect." The guarantee is absolute: error \(\leq \epsilon\).
• Agnostic PAC: "Find one that's close to the best in \(\mathcal{H}\), even if the best isn't perfect." The guarantee is relative: error \(\leq \operatorname{opt} + \epsilon\), where \(\operatorname{opt} = \min_h L_{\mathcal{D}}(h)\).

Agnostic PAC is strictly harder: it must work for every distribution, including ones where no \(h \in \mathcal{H}\) fits the data well. PAC learning only needs to work when the problem is "nice" (realizable). So agnostic PAC learnable \(\Rightarrow\) PAC learnable, but the converse isn't obvious at all.

Example: If you're classifying emails with linear classifiers but emails aren't linearly separable, the PAC guarantee says nothing (realizability fails). The agnostic guarantee still promises you'll get within \(\epsilon\) of the best linear classifier — even though that best classifier has nonzero error.

The Fundamental Theorem of Statistical Learning Let \(\mathcal{H}\) be a hypothesis class of functions from \(\mathcal{X}\) to \(\{0,1\}\). The following are equivalent:

1. \(\mathcal{H}\) has the uniform convergence property (Section 1: training error tracks true error for all \(h\) simultaneously).
2. \(\mathcal{H}\) is agnostically PAC learnable (by any ERM algorithm).
3. \(\mathcal{H}\) is PAC learnable (in the realizable sense).
4. \(\operatorname{VCdim}(\mathcal{H}) < \infty\).

Proof

(4) \(\Rightarrow\) (1): Finite VC dim \(\Rightarrow\) Uniform Convergence.

This is the VC generalization bound from Section 10. We proved it through the chain: finite VC dim \(\xrightarrow{\text{Sauer–Shelah (Sec. 8)}}\) polynomial growth function \(\xrightarrow{\text{symmetrization (Sec. 9) + Hoeffding (Sec. 4)}}\) uniform convergence. Specifically, Section 10 showed:

$$ \Pr\!\left[\sup_{h \in \mathcal{H}} |L_S(h) - L_{\mathcal{D}}(h)| > \epsilon\right] \leq 4\left(\frac{2em}{d}\right)^d e^{-m\epsilon^2/8}, $$

which goes to zero for any fixed \(\epsilon\) as \(m \to \infty\).

(1) \(\Rightarrow\) (2): Uniform Convergence \(\Rightarrow\) Agnostically PAC Learnable via ERM.

This is the three-step argument from Section 1. If \(|L_S(h) - L_{\mathcal{D}}(h)| \leq \epsilon\) for all \(h\), then ERM's output \(\hat{h}\) satisfies \(L_{\mathcal{D}}(\hat{h}) \leq \min_h L_{\mathcal{D}}(h) + 2\epsilon\). (Step 1: true error of ERM's pick is close to its training error. Step 2: ERM picks the lowest training error. Step 3: training error of the best \(h\) is close to its true error. Chain them.) Agnostic PAC learnability follows with the ERM algorithm.

(2) \(\Rightarrow\) (3): Agnostic PAC \(\Rightarrow\) PAC.

This is immediate from the definitions. Agnostic PAC learnability guarantees \(L_{\mathcal{D}}(A(S)) \leq \min_h L_{\mathcal{D}}(h) + \epsilon\) for every distribution. PAC learnability only requires this for distributions where \(\min_h L_{\mathcal{D}}(h) = 0\), which is a subset of all distributions. A stronger guarantee implies a weaker one.

(3) \(\Rightarrow\) (4): PAC Learnable \(\Rightarrow\) Finite VC dim.

This is the contrapositive of the No-Free-Lunch theorem (Section 11). We proved: if \(\operatorname{VCdim}(\mathcal{H}) = \infty\), then the class is not even PAC learnable (the adversary can defeat any algorithm even under realizability). Equivalently: if \(\mathcal{H}\) is PAC learnable, then \(\operatorname{VCdim}(\mathcal{H}) < \infty\).

The cycle (4) \(\Rightarrow\) (1) \(\Rightarrow\) (2) \(\Rightarrow\) (3) \(\Rightarrow\) (4) is complete. \(\square\)

Example (Two Coins)

Let \(P = \operatorname{Bernoulli}(0.6)\) and \(Q = \operatorname{Bernoulli}(0.4)\). Then:

$$ \operatorname{TV}(P, Q) = \frac{1}{2}(|0.6 - 0.4| + |0.4 - 0.6|) = \frac{1}{2}(0.2 + 0.2) = 0.2. $$

The most distinguishing event is \(A = \{1\}\) (heads): \(P(A) = 0.6\), \(Q(A) = 0.4\), gap \(= 0.2\). \(\checkmark\)

Example (Fair vs. Biased Die)

Let \(P\) = fair die (each face has probability \(1/6\)) and \(Q\) = loaded die with \(Q(6) = 1/2\) and \(Q(i) = 1/10\) for \(i = 1, \ldots, 5\). Then:

$$ \operatorname{TV}(P, Q) = \frac{1}{2}\!\left(5 \cdot |1/6 - 1/10| + |1/6 - 1/2|\right) = \frac{1}{2}\!\left(5 \cdot \frac{1}{15} + \frac{1}{3}\right) = \frac{1}{2}\!\left(\frac{1}{3} + \frac{1}{3}\right) = \frac{1}{3}. $$

A single roll gives you a 1/3 chance of noticing the difference — not great for telling the dice apart.

Proof

The algorithm is a function \(\psi : \Omega \to \{P, Q\}\) (it sees a sample \(\omega\) and guesses which distribution generated it). The error probability (averaged over the two hypotheses being equally likely) is:

$$ \Pr[\text{error}] = \frac{1}{2}P(\psi(\omega) = Q) + \frac{1}{2}Q(\psi(\omega) = P). $$

Let \(A = \{\omega : \psi(\omega) = P\}\) be the "accept \(P\)" region. Then:

$$ \Pr[\text{error}] = \frac{1}{2}(1 - P(A)) + \frac{1}{2}Q(A) = \frac{1}{2} + \frac{1}{2}(Q(A) - P(A)) \geq \frac{1}{2} - \frac{1}{2}\sup_A |P(A) - Q(A)| = \frac{1 - \operatorname{TV}(P,Q)}{2}. \;\square $$

Motivating Example: The Detective and Two Suspects

A coin is either 60% heads (suspect \(P\)) or 40% heads (suspect \(Q\)). You flip it once and see heads. How much evidence does this give you?

The natural measure is the likelihood ratio: how much more likely is heads under \(P\) than under \(Q\)?

$$ \frac{P(\text{heads})}{Q(\text{heads})} = \frac{0.6}{0.4} = 1.5. $$

Heads is 1.5× more likely under \(P\). That's some evidence for \(P\), but not overwhelming.

Now suppose you flip again and see tails. The likelihood ratio for tails is:

$$ \frac{P(\text{tails})}{Q(\text{tails})} = \frac{0.4}{0.6} \approx 0.667. $$

Tails is less likely under \(P\) — it's evidence against \(P\). The combined likelihood ratio for (heads, tails) is the product: \(1.5 \times 0.667 = 1.0\). The two flips cancelled out!

The problem with raw likelihood ratios: they multiply. After \(m\) flips, you'd have a product of \(m\) terms, which is algebraically unwieldy (products are hard to analyze, don't simplify with linearity of expectation, and can overflow or underflow numerically).

The fix: take the logarithm. The log-likelihood ratio for a single outcome \(\omega\) is:

$$ \ell(\omega) = \ln \frac{P(\omega)}{Q(\omega)}. $$

For heads: \(\ell(\text{H}) = \ln(1.5) = 0.405\). For tails: \(\ell(\text{T}) = \ln(0.667) = -0.405\).

Now the combined evidence for (heads, tails) is the sum: \(0.405 + (-0.405) = 0\). Logarithms turn products into sums — and sums are what probability theory handles best (linearity of expectation, law of large numbers, central limit theorem all work with sums).

Proof

We use the concavity of the logarithm. Since \(\ln\) is concave, Jensen's inequality gives:

$$ -\operatorname{KL}(P \| Q) = \sum_{\omega} P(\omega) \ln \frac{Q(\omega)}{P(\omega)} \leq \ln\!\left(\sum_{\omega} P(\omega) \cdot \frac{Q(\omega)}{P(\omega)}\right) = \ln\!\left(\sum_{\omega} Q(\omega)\right) = \ln(1) = 0. $$

So \(\operatorname{KL}(P \| Q) \geq 0\). Equality holds iff \(Q(\omega)/P(\omega)\) is constant for all \(\omega\) with \(P(\omega) > 0\), which forces \(P = Q\). \(\square\)

Example (Bernoulli KL Divergence — In Detail)

For \(P = \operatorname{Ber}(0.6)\) and \(Q = \operatorname{Ber}(0.4)\):

$$ \operatorname{KL}(P \| Q) = \underbrace{P(\text{H})}_{0.6} \cdot \underbrace{\ln \frac{P(\text{H})}{Q(\text{H})}}_{\ln(0.6/0.4)} + \underbrace{P(\text{T})}_{0.4} \cdot \underbrace{\ln \frac{P(\text{T})}{Q(\text{T})}}_{\ln(0.4/0.6)}. $$

Let's compute each term and understand what it means:

• Heads term: evidence from heads = \(\ln(0.6/0.4) = \ln(1.5) = +0.405\) nats (positive: heads favors \(P\)). This happens with probability 0.6 under \(P\). Contribution: \(0.6 \times 0.405 = 0.243\).
• Tails term: evidence from tails = \(\ln(0.4/0.6) = \ln(0.667) = -0.405\) nats (negative: tails favors \(Q\)). This happens with probability 0.4 under \(P\). Contribution: \(0.4 \times (-0.405) = -0.162\).

$$ \operatorname{KL}(P \| Q) = 0.243 + (-0.162) = 0.081 \text{ nats}. $$

What does 0.081 nats mean concretely? Each flip of the 60% coin gives you, on average, 0.081 nats of evidence that you're looking at the 60% coin rather than the 40% coin. This is small because the two coins almost cancel: heads gives +0.405 nats toward \(P\), but tails gives -0.405 nats toward \(Q\), and since heads only happens a bit more often (60% vs 40%), the net is a tiny +0.081.

To build up to ~1 nat of total evidence (a rough threshold where you can start to reliably distinguish the coins), you'd need about \(1/0.081 \approx 12\) flips. With only 3 or 4 flips, you have ~0.25–0.32 nats total — barely any signal through the noise.

Example (When KL is Large vs. Small)

Extreme case: \(P = \operatorname{Ber}(0.99)\), \(Q = \operatorname{Ber}(0.01)\).

$$ \operatorname{KL}(P \| Q) = 0.99 \ln\frac{0.99}{0.01} + 0.01\ln\frac{0.01}{0.99} = 0.99(4.595) + 0.01(-4.595) = 4.509 \text{ nats}. $$

One flip gives 4.5 nats of evidence! If you see heads (which happens 99% of the time under \(P\)), the log-likelihood ratio is \(\ln(99) = 4.6\), which is overwhelming evidence for \(P\). Even a single flip is enough to tell these coins apart.

Subtle case: \(P = \operatorname{Ber}(0.51)\), \(Q = \operatorname{Ber}(0.49)\). Then \(\operatorname{KL} \approx 0.0008\) nats. You'd need \(\sim 1/0.0008 = 1{,}250\) flips to accumulate 1 nat. Distinguishing a 51% coin from a 49% coin is genuinely hard.

Proof

Let \(p = 1/2 + \epsilon\) and \(q = 1/2 - \epsilon\). We need to show \(p\ln(p/q) + (1-p)\ln((1-p)/(1-q)) \leq 8\epsilon^2\).

Note that \(p/q = (1/2 + \epsilon)/(1/2 - \epsilon) = (1 + 2\epsilon)/(1 - 2\epsilon)\), and \((1-p)/(1-q) = (1/2 - \epsilon)/(1/2 + \epsilon) = (1 - 2\epsilon)/(1 + 2\epsilon)\). Let \(t = 2\epsilon\), so \(|t| < 1\). Then:

$$ \operatorname{KL} = \frac{1+t}{2}\ln\frac{1+t}{1-t} + \frac{1-t}{2}\ln\frac{1-t}{1+t}. $$

Since the second term is the negative of \(\frac{1-t}{2}\ln\frac{1+t}{1-t}\), this simplifies to:

$$ \operatorname{KL} = \frac{(1+t) - (1-t)}{2}\ln\frac{1+t}{1-t} = t \cdot \ln\frac{1+t}{1-t}. $$

Now use the Taylor series: \(\ln\frac{1+t}{1-t} = \ln(1+t) - \ln(1-t) = 2t + \frac{2t^3}{3} + \frac{2t^5}{5} + \cdots \leq 2t + 2t^3 + 2t^5 + \cdots = \frac{2t}{1-t^2}\). For \(|t| \leq 1/\sqrt{2}\) (i.e., \(|\epsilon| \leq 1/(2\sqrt{2}) \approx 0.354\)), we have \(1/(1-t^2) \leq 2\), so:

$$ \operatorname{KL} \leq t \cdot \frac{2t}{1-t^2} = \frac{2t^2}{1-t^2} \leq 4t^2 = 16\epsilon^2. $$

A tighter analysis using \(\ln\frac{1+t}{1-t} \leq 2t/(1-t^2) \leq 2t + 4t^3\) for \(|t| \leq 0.9\) gives \(\operatorname{KL} \leq 2t^2 + 4t^4 \leq 2t^2(1 + 2t^2)\). For \(|\epsilon| < 1/2\), \(t^2 = 4\epsilon^2 < 1\), so \(\operatorname{KL} \leq 2t^2 \cdot 2 = 4t^2 = 16\epsilon^2\). The constant 8 follows from the sharper bound \(\operatorname{KL} \leq \frac{2t^2}{1-t^2} \leq 8\epsilon^2\) which holds for \(|\epsilon| \leq 1/4\) (since then \(t^2 \leq 1/4\) and \(1/(1-t^2) \leq 4/3\), giving \(\operatorname{KL} \leq 2t^2 \cdot 4/3 = 8t^2/3 \leq 8\epsilon^2\) since \(t = 2\epsilon\)).

For our purposes, the key message is: \(\operatorname{KL} = \Theta(\epsilon^2)\) — the KL divergence between two coins that differ by \(\epsilon\) is proportional to \(\epsilon^2\). \(\square\)

Numerical Verification

For \(\epsilon = 0.1\): exact \(\operatorname{KL} = 0.081\), bound gives \(8 \times 0.01 = 0.08\). Very tight! (The bound is actually slightly conservative here.)

For \(\epsilon = 0.05\): exact \(\operatorname{KL} \approx 0.020\), bound gives \(8 \times 0.0025 = 0.02\). Nearly exact. \(\checkmark\)

Proof

For a product distribution, \(P^m(z_1, \ldots, z_m) = \prod_{i=1}^m P(z_i)\). So:

$$ \operatorname{KL}(P^m \| Q^m) = \mathbb{E}_{P^m}\!\left[\ln \frac{\prod P(Z_i)}{\prod Q(Z_i)}\right] = \mathbb{E}_{P^m}\!\left[\sum_{i=1}^m \ln \frac{P(Z_i)}{Q(Z_i)}\right] = \sum_{i=1}^m \mathbb{E}_P\!\left[\ln \frac{P(Z_i)}{Q(Z_i)}\right] = m \cdot \operatorname{KL}(P \| Q). $$

The key step: logarithm converts products to sums, and expectation is linear. \(\square\)

Example (Coin Flipping — Evidence Accumulation)

Returning to our 60%-vs-40% coin: \(\operatorname{KL}(P \| Q) = 0.081\) nats per flip. After \(m\) flips, the total evidence is \(0.081m\) nats.

• \(m = 3\) flips: total \(= 0.24\) nats. Still mostly noise — you'd guess wrong about 40% of the time.
• \(m = 12\) flips: total \(= 0.97\) nats. Roughly 1 nat — now you have a meaningful signal. Pinsker's inequality (next tool) will formalize this: the total variation between the two 12-sample distributions is bounded away from zero, so a good test can start to reliably distinguish them.
• \(m = 50\) flips: total \(= 4.05\) nats. Strong evidence — you'd almost never guess wrong.

For coins with bias \(1/2 \pm \epsilon\): \(\operatorname{KL} \approx 8\epsilon^2\) per flip, so accumulating 1 nat takes \(m \approx 1/(8\epsilon^2)\) flips. With \(\epsilon = 0.01\) (51% vs 49%): \(m \approx 1{,}250\) flips. With \(\epsilon = 0.001\) (50.1% vs 49.9%): \(m \approx 125{,}000\). The difficulty scales as \(1/\epsilon^2\) — a preview of the sample complexity lower bound we're building toward.

Proof

The proof has two steps: reduce to binary distributions (via data processing), then prove the binary case using calculus.

Step 1: Reduce to two outcomes. Let \(A = \{\omega : P(\omega) > Q(\omega)\}\). Define binary distributions \(\tilde{P} = (P(A), 1 - P(A))\) and \(\tilde{Q} = (Q(A), 1 - Q(A))\). Then \(\operatorname{TV}(P, Q) = P(A) - Q(A) = \operatorname{TV}(\tilde{P}, \tilde{Q})\).

The data processing inequality for KL divergence says that coarsening a distribution (grouping outcomes into sets) can only decrease KL: \(\operatorname{KL}(\tilde{P} \| \tilde{Q}) \leq \operatorname{KL}(P \| Q)\). (Intuitively: aggregating outcomes throws away information. Formally: this follows from the log-sum inequality, \(\sum a_i \ln(a_i/b_i) \geq (\sum a_i)\ln(\sum a_i / \sum b_i)\), applied to the groups \(A\) and \(A^c\).)

So if we prove Pinsker for the binary pair \((\tilde{P}, \tilde{Q})\), the general case follows:

$$ \operatorname{TV}(P, Q) = \operatorname{TV}(\tilde{P}, \tilde{Q}) \leq \sqrt{\operatorname{KL}(\tilde{P}\|\tilde{Q})/2} \leq \sqrt{\operatorname{KL}(P\|Q)/2}. $$

Step 2: Prove the binary case. We need: for \(P = \operatorname{Ber}(p)\) and \(Q = \operatorname{Ber}(q)\) with \(p, q \in (0,1)\):

$$ \operatorname{KL}(P\|Q) = p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q} \;\geq\; 2(p - q)^2. $$

Fix \(p \in (0,1)\) and define:

$$ r(q) = \operatorname{KL}(\operatorname{Ber}(p) \| \operatorname{Ber}(q)) - 2(p - q)^2 = p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q} - 2(p-q)^2. $$

We want to show \(r(q) \geq 0\) for all \(q \in (0,1)\). The strategy: find all critical points of \(r\), check that \(r \geq 0\) at each one, and use boundary behavior to conclude \(r \geq 0\) everywhere.

Critical points. Compute:

$$ r'(q) = -\frac{p}{q} + \frac{1-p}{1-q} + 4(p-q). $$

At \(q = p\): \(r'(p) = -1 + 1 + 0 = 0\). And \(r(p) = 0 - 0 = 0\). So \(q = p\) is a critical point with \(r(p) = 0\).

Is \(q = p\) a minimum? Compute:

$$ r''(q) = \frac{p}{q^2} + \frac{1-p}{(1-q)^2} - 4. $$

At \(q = p\): \(r''(p) = \frac{1}{p} + \frac{1}{1-p} - 4 = \frac{1}{p(1-p)} - 4\).

Since \(p(1-p) \leq 1/4\) for all \(p \in (0,1)\) (by AM-GM: \(p + (1-p) = 1\), so \(p(1-p) \leq (1/2)^2 = 1/4\)), we have \(1/(p(1-p)) \geq 4\), so \(r''(p) \geq 0\). The critical point \(q = p\) is a local minimum. \(\checkmark\)

Are there other critical points? Setting \(r'(q) = 0\) and clearing fractions:

$$ -\frac{p}{q} + \frac{1-p}{1-q} + 4(p-q) = 0 $$ $$ \frac{p(1-q) - (1-p)q}{q(1-q)} = 4(q - p) $$ $$ \frac{p - q}{q(1-q)} = 4(p - q). $$

If \(p \neq q\), we can divide both sides by \((p - q)\):

$$ \frac{1}{q(1-q)} = 4, \qquad \text{so } q(1-q) = \frac{1}{4}, \qquad \text{hence } q = \frac{1}{2}. $$

So the only critical points of \(r\) on \((0,1)\) are \(q = p\) and \(q = 1/2\).

Check \(r(1/2) \geq 0\).

$$ r(1/2) = p\ln(2p) + (1-p)\ln(2(1-p)) - 2\!\left(p - \tfrac{1}{2}\right)^{\!2}. $$

The first part simplifies: \(p\ln(2p) + (1-p)\ln(2(1-p)) = \ln 2 + p\ln p + (1-p)\ln(1-p) = \ln 2 - H(p)\), where \(H(p) = -p\ln p - (1-p)\ln(1-p)\) is the binary entropy. This is exactly \(\operatorname{KL}(\operatorname{Ber}(p) \| \operatorname{Ber}(1/2))\) — the divergence from the fair coin. So:

$$ r(1/2) = \operatorname{KL}(\operatorname{Ber}(p) \| \operatorname{Ber}(1/2)) - 2\!\left(p - \tfrac{1}{2}\right)^{\!2}. $$

But this is Pinsker's inequality applied to \(Q = \operatorname{Ber}(1/2)\) — is this circular? No: we can verify this specific case directly. Define \(s(p) = r(1/2)\) as a function of \(p\). Then \(s(1/2) = 0\), \(s'(p) = \ln(p/(1-p)) - 4(p - 1/2)\), and \(s'(1/2) = 0\). The second derivative is \(s''(p) = 1/(p(1-p)) - 4 \geq 0\) (same AM-GM argument). So \(p = 1/2\) is a minimum of \(s\) with \(s(1/2) = 0\). Since \(s(p) \to +\infty\) as \(p \to 0^+\) or \(p \to 1^-\), and the only other critical point would again satisfy \(p(1-p) = 1/4\), i.e., \(p = 1/2\), there are no other critical points. So \(s(p) = r(1/2) \geq 0\) for all \(p\). \(\checkmark\)

Conclusion. The function \(r(q)\) has exactly two critical points: \(q = p\) (where \(r = 0\)) and \(q = 1/2\) (where \(r \geq 0\)). Since \(r(q) \to +\infty\) as \(q \to 0^+\) or \(q \to 1^-\) (KL divergence blows up at the boundaries), and the only critical points both have \(r \geq 0\), the function cannot dip below zero anywhere. Therefore \(r(q) \geq 0\) for all \(q \in (0,1)\).

Restating: \(\operatorname{KL}(\operatorname{Ber}(p) \| \operatorname{Ber}(q)) \geq 2(p - q)^2 = 2\operatorname{TV}(P,Q)^2\). Combined with Step 1:

$$ \operatorname{TV}(P, Q) \leq \sqrt{\frac{\operatorname{KL}(P \| Q)}{2}}. \quad \square $$

Numerical Check

Let \(p = 0.7\), \(q = 0.3\):

• \(\operatorname{KL} = 0.7\ln(7/3) + 0.3\ln(3/7) = 0.7(0.847) + 0.3(-0.847) = 0.339\).
• \(2(p-q)^2 = 2(0.16) = 0.32\). Check: \(0.339 \geq 0.32\). \(\checkmark\)
• Pinsker: \(\operatorname{TV} = 0.4 \leq \sqrt{0.339/2} = \sqrt{0.170} = 0.412\). \(\checkmark\)

Verify the critical point at \(q = 1/2\): \(r'(0.5) = -0.7/0.5 + 0.3/0.5 + 4(0.2) = -1.4 + 0.6 + 0.8 = 0\). \(\checkmark\)

\(r(0.5) = 0.7\ln(1.4) + 0.3\ln(0.6) - 2(0.04) = 0.236 - 0.153 - 0.08 = 0.003 \geq 0\). \(\checkmark\)

Numerical Check

\(P = \operatorname{Ber}(0.6)\), \(Q = \operatorname{Ber}(0.4)\). We computed \(\operatorname{TV} = 0.2\) and \(\operatorname{KL} = 0.081\).

Pinsker says: \(\operatorname{TV} \leq \sqrt{0.081/2} = \sqrt{0.0405} \approx 0.201\). Actual TV = 0.2. Very tight! \(\checkmark\)

Example (The Fundamental Coin Problem)

There are two possible coins in a box. Coin A has bias \(0.6\) (heads probability). Coin B has bias \(0.4\). Someone picks a coin uniformly at random, and you see \(m\) flips from it. You must guess which coin it is.

If you see \(m = 1\) flip: even the best strategy (guess A if heads, B if tails) has error probability \(\frac{1}{2} \cdot 0.4 + \frac{1}{2} \cdot 0.4 = 0.4\). That's almost as bad as random guessing (error = 0.5).

Why 0.4? With probability 1/2, the coin is A. You see heads with probability 0.6 (correct guess) or tails with probability 0.4 (wrong guess). With probability 1/2, the coin is B. You see tails with probability 0.6 (correct guess) or heads with probability 0.4 (wrong guess). Total error = \(\frac{1}{2}(0.4) + \frac{1}{2}(0.4) = 0.4\).

We showed earlier that \(\operatorname{TV}(\operatorname{Ber}(0.6), \operatorname{Ber}(0.4)) = 0.2\), so the Testing Bound gives: error \(\geq (1 - 0.2)/2 = 0.4\). Exact match! \(\checkmark\)

Now think of this as a learning problem: under coin A, the best "classifier" (prediction rule) is "always predict heads" (\(h_A\)); under coin B, it's "always predict tails" (\(h_B\)). The learner sees data and must pick the right prediction rule. Getting it wrong means excess error of \(2 \times 0.1 = 0.2\). Le Cam formalizes this: any learner fails on at least one of the two coins with probability at least \((1 - \operatorname{TV})/2\).

Le Cam’s Two-Point Method

Suppose:

• There are two possible "worlds": distribution \(P\) (world 1) and distribution \(Q\) (world 2).
• In each world, there is a correct answer: \(h_P\) in world 1, \(h_Q\) in world 2, with \(h_P \neq h_Q\).
• A learner sees \(m\) i.i.d. samples from whichever world was chosen, and outputs a guess \(\hat{h}\).

Then:

$$ \max\!\left(\Pr_{S \sim P^m}[\hat{h}(S) \neq h_P],\; \Pr_{S \sim Q^m}[\hat{h}(S) \neq h_Q]\right) \geq \frac{1 - \operatorname{TV}(P^m, Q^m)}{2}. $$

In words: no matter what the learner does, it gets the wrong answer on at least one of the two worlds with probability at least \((1 - \operatorname{TV}(P^m, Q^m))/2\).

Proof

The proof reduces learning to testing, then applies the Testing Bound from Tool 1.

Step 1: Turn the learner into a test. The learner is a function \(\hat{h}(S)\) that takes a dataset \(S\) and outputs a classifier. Since \(h_P \neq h_Q\), the learner's output implicitly declares which world it thinks it's in:

• If \(\hat{h}(S) = h_P\), it's effectively declaring "I'm in world 1 (distribution \(P\))."
• If \(\hat{h}(S) \neq h_P\), it's effectively declaring "I'm in world 2 (distribution \(Q\))."

This turns the learner into a hypothesis test between \(P^m\) and \(Q^m\).

Step 2: Apply the Testing Bound. Suppose Nature picks world 1 or world 2 with equal probability \(1/2\). The learner's average error (averaged over which world was chosen) is:

$$ \frac{1}{2}\Pr_{P^m}[\hat{h} \neq h_P] + \frac{1}{2}\Pr_{Q^m}[\hat{h} \neq h_Q]. $$

But this is exactly the error of the induced hypothesis test. By the Testing Bound (Tool 1):

$$ \frac{1}{2}\Pr_{P^m}[\hat{h} \neq h_P] + \frac{1}{2}\Pr_{Q^m}[\hat{h} \neq h_Q] \geq \frac{1 - \operatorname{TV}(P^m, Q^m)}{2}. $$

Step 3: From average to max. For any two numbers \(a\) and \(b\): \(\max(a, b) \geq \frac{a+b}{2}\). So:

$$ \max\!\left(\Pr_{P^m}[\hat{h} \neq h_P],\; \Pr_{Q^m}[\hat{h} \neq h_Q]\right) \geq \frac{1}{2}\!\left(\Pr_{P^m}[\hat{h} \neq h_P] + \Pr_{Q^m}[\hat{h} \neq h_Q]\right) \geq \frac{1 - \operatorname{TV}(P^m, Q^m)}{2}. \;\square $$

The Complete Chain

1. Construct two hard worlds — find distributions \(P\) and \(Q\) that require different classifiers but are close together.
2. KL divergence (Tool 2) — compute how much evidence each sample provides: \(\operatorname{KL}(P \| Q)\). For coins differing by \(\epsilon\), this is \(\leq 8\epsilon^2\).
3. Tensorization (Tool 2) — after \(m\) i.i.d. samples, the total evidence is: \(\operatorname{KL}(P^m \| Q^m) = m \cdot \operatorname{KL}(P \| Q)\).
4. Pinsker (Tool 3) — convert evidence into distinguishability: \(\operatorname{TV}(P^m, Q^m) \leq \sqrt{m \cdot \operatorname{KL}(P\|Q)/2}\).
5. Le Cam (Tool 4) — convert distinguishability into learning error: any learner fails on at least one world with probability \(\geq (1 - \operatorname{TV})/2\).
6. Conclusion — if \(m\) is too small, the total evidence \(m \cdot \operatorname{KL}\) is small, so TV is small, so the error is large. No algorithm can learn.

Example: The Complete Chain in Action

Can you tell if a coin has bias \(0.5 + \epsilon\) or \(0.5 - \epsilon\) from \(m\) flips? The correct predictions differ (always guess heads vs. always guess tails), so this is a learning problem with two possible worlds.

With \(\epsilon = 0.05\) and \(m = 20\) flips:

1. Two worlds: \(P = \operatorname{Ber}(0.55)\), \(Q = \operatorname{Ber}(0.45)\).
2. KL per sample (Tool 2): \(\operatorname{KL}(P \| Q) \leq 8(0.05)^2 = 0.02\) nats.
3. Total KL (Tensorization): \(\operatorname{KL}(P^{20} \| Q^{20}) = 20 \times 0.02 = 0.4\) nats.
4. TV (Pinsker): \(\operatorname{TV}(P^{20}, Q^{20}) \leq \sqrt{0.4/2} = \sqrt{0.2} \approx 0.447\).
5. Error (Le Cam): any learner fails with probability \(\geq (1 - 0.447)/2 = 0.277\). That's a 28% failure rate — way too high for reliable learning.

How many flips do we need? For the error to drop to, say, \(\leq 0.05\), we need \((1 - \operatorname{TV})/2 \leq 0.05\), i.e., \(\operatorname{TV} \geq 0.9\). But Pinsker only gives an upper bound on TV, so this direction doesn't directly help — however, the contrapositive is what we use: if \(m\) is small enough that TV \(\leq\) some constant, then the error is bounded away from zero, proving learning is impossible with that many samples.

For TV to be at most \(1/2\): \(\sqrt{m \cdot 0.02/2} \leq 1/2\), so \(m \leq 25\). With \(m \leq 25\) flips, TV \(\leq 1/2\), so error \(\geq (1 - 1/2)/2 = 1/4\). Fewer than ~25 flips means at least 25% error rate. No algorithm can do better.

Proof — Part A: \(m \geq \Omega(d/\epsilon^2)\)

The plan in one sentence: We design a "hard exam" where the learner must figure out \(d\) unknown bits from noisy data. We show that each bit requires \(\sim 1/\epsilon^2\) samples to identify, so the total cost is \(\sim d/\epsilon^2\).

Step 1: Find \(d\) shattered points.

Recall from Section 8 what "VC dimension \(d\)" means: there exist \(d\) points that \(\mathcal{H}\) shatters — meaning for every possible labeling of these \(d\) points with 0s and 1s, there's some hypothesis in \(\mathcal{H}\) that achieves that labeling. All \(2^d\) labelings are realizable.

Call these shattered points \(x_1, x_2, \ldots, x_d\).

Step 2: Design \(2^d\) "worlds" that the learner must distinguish.

Nature is going to pick a secret binary string \(b = (b_1, b_2, \ldots, b_d)\) — think of it as a secret answer key with \(d\) entries. Each entry is 0 or 1, so there are \(2^d\) possible answer keys. The learner's job is to figure out \(b\) from noisy data.

For each possible answer key \(b\), define a distribution \(\mathcal{D}_b\) that generates labeled data as follows:

1. Pick a random point: Choose one of the \(d\) shattered points uniformly at random. Each point \(x_i\) is chosen with probability \(1/d\).
2. Generate a noisy label: At point \(x_i\), the "correct" answer is \(b_i\) (the \(i\)-th entry of the secret string). But the label is noisy: with probability \(1/2 + \epsilon\), the label matches the correct answer (\(Y = b_i\)), and with probability \(1/2 - \epsilon\), it's the wrong answer (\(Y = 1 - b_i\)).

Each draw from \(\mathcal{D}_b\) produces a pair \((x_i, Y)\): a random point and a noisy label. The learner collects \(m\) such pairs and must figure out the secret string \(b\).

Step 3: The best classifier for each world, and why getting it wrong is costly.

Under distribution \(\mathcal{D}_b\), the best possible classifier is the one that predicts the more likely label at each point: predict \(b_i\) at point \(x_i\). Call this classifier \(h_b\). Since \(\mathcal{H}\) shatters \(\{x_1, \ldots, x_d\}\), the labeling \(h_b\) (which assigns \(b_i\) to \(x_i\)) is achievable by some hypothesis in \(\mathcal{H}\) — that's exactly what shattering means.

What is the error rate of \(h_b\)? At each point \(x_i\), it predicts the correct answer \(b_i\), and the label disagrees with probability \(1/2 - \epsilon\) (the noise rate). Since each point is equally likely:

$$ L_{\mathcal{D}_b}(h_b) = \frac{1}{2} - \epsilon. $$

Now suppose the learner outputs a classifier \(\hat{h}\) that gets \(k\) of the \(d\) positions wrong (i.e., \(\hat{h}(x_i) \neq b_i\) for \(k\) of the points). At a point where \(\hat{h}\) predicts correctly, its error rate is \(1/2 - \epsilon\) (same as optimal). At a point where \(\hat{h}\) predicts incorrectly, it's guessing the less likely label, so its error rate is \(1/2 + \epsilon\). The overall error is:

$$ L_{\mathcal{D}_b}(\hat{h}) = \frac{1}{d}\Big[\underbrace{(d - k)(1/2 - \epsilon)}_{\text{correct positions}} + \underbrace{k(1/2 + \epsilon)}_{\text{wrong positions}}\Big] = \left(\frac{1}{2} - \epsilon\right) + \frac{2k\epsilon}{d}. $$

The excess error compared to the best classifier is:

$$ L_{\mathcal{D}_b}(\hat{h}) - L_{\mathcal{D}_b}(h_b) = \frac{2k\epsilon}{d}. $$

For the learner to achieve excess error at most \(\epsilon\), we need \(2k\epsilon/d \leq \epsilon\), i.e., \(k \leq d/2\). The learner must correctly identify at least half of the \(d\) secret bits.

Step 4: Why identifying each bit is a coin-flipping problem.

Focus on a single position, say position \(i\). Out of \(m\) total training samples, about \(m/d\) of them land on point \(x_i\) (since each sample picks one of the \(d\) points uniformly at random). The labels of these samples are independent coin flips:

• If \(b_i = 1\) (the secret bit is 1): each label at \(x_i\) is 1 with probability \(1/2 + \epsilon\) and 0 with probability \(1/2 - \epsilon\). This is a coin with bias \(1/2 + \epsilon\).
• If \(b_i = 0\) (the secret bit is 0): each label at \(x_i\) is 0 with probability \(1/2 + \epsilon\) and 1 with probability \(1/2 - \epsilon\). This is a coin with bias \(1/2 - \epsilon\) (for showing 1).

So to figure out bit \(i\), the learner has \(\sim m/d\) coin flips and must determine whether the coin has bias \(1/2 + \epsilon\) or \(1/2 - \epsilon\). This is exactly the coin-testing problem from the "Complete Chain in Action" example above.

Step 5: Measure how much evidence the data provides (KL divergence).

Now we apply the tools from earlier. Consider two specific worlds that differ only in position \(i\): secret strings \(b\) and \(b'\) that are identical except \(b_i \neq b'_i\). (For instance, \(b = (1,0,1)\) and \(b' = (0,0,1)\), differing only in position 1.)

When the learner sees a sample that lands on some point \(x_j\) with \(j \neq i\), both worlds produce exactly the same distribution of labels (since \(b_j = b'_j\)). That sample provides zero evidence about whether bit \(i\) is 0 or 1.

Only the samples that land on point \(x_i\) provide evidence. Each such sample is a coin flip from either \(\operatorname{Ber}(1/2 + \epsilon)\) (if \(b_i = 1\)) or \(\operatorname{Ber}(1/2 - \epsilon)\) (if \(b_i = 0\)). From Tool 2 (the Small-Bias Bernoulli KL lemma), each such flip provides at most \(8\epsilon^2\) nats of evidence.

How many samples land on \(x_i\)? About \(m/d\) (since each of the \(m\) samples picks point \(x_i\) with probability \(1/d\)). By the tensorization property of KL divergence (Tool 2: evidence from independent samples adds up), the total evidence for bit \(i\) after seeing all \(m\) samples is:

$$ \operatorname{KL}(\mathcal{D}_b^m \| \mathcal{D}_{b'}^m) \leq \frac{m}{d} \cdot 8\epsilon^2 = \frac{8m\epsilon^2}{d} \text{ nats}. $$

Step 6: Convert evidence to distinguishability (Pinsker).

From Tool 3 (Pinsker's inequality): total variation \(\leq \sqrt{\operatorname{KL}/2}\). Applying this to the full \(m\)-sample distributions for two worlds differing in bit \(i\):

$$ \operatorname{TV}(\mathcal{D}_b^m, \mathcal{D}_{b'}^m) \leq \sqrt{\frac{8m\epsilon^2/d}{2}} = \sqrt{\frac{4m\epsilon^2}{d}} = \frac{2\epsilon\sqrt{m}}{\sqrt{d}}. $$

Recall what total variation means (Tool 1): it's the largest possible difference in probability of any event between the two distributions. If TV is 0.1, then no event — no pattern in the data, no matter how cleverly chosen — has probability differing by more than 0.1 between the two worlds. The two worlds produce almost indistinguishable data.

Step 7: Convert distinguishability to error (Le Cam).

From Tool 4 (Le Cam's method): any algorithm that tries to determine bit \(i\) — i.e., to determine which of two worlds \(\mathcal{D}_b\) or \(\mathcal{D}_{b'}\) generated the data — has error probability at least \((1 - \operatorname{TV})/2\). Plugging in our TV bound:

$$ \Pr[\text{wrong about bit } i] \geq \frac{1 - \frac{2\epsilon\sqrt{m}}{\sqrt{d}}}{2}. $$

This holds for any algorithm — neural networks, decision trees, anything. It's an information-theoretic limit: the data simply doesn't contain enough evidence.

Step 8: Compute the learner's expected excess error.

Imagine Nature picks the secret string \(b\) uniformly at random from all \(2^d\) possibilities. We'll compute the learner's expected excess error, averaged over (a) Nature's random choice of \(b\) and (b) the random training data \(S\).

Let \(W\) = number of positions where the learner's classifier disagrees with the optimal classifier \(h_b\). From Step 7, for each position \(i\), the learner gets bit \(i\) wrong with probability at least \(p_0 = (1 - 2\epsilon\sqrt{m/d})/2\). By linearity of expectation (the expected value of a sum equals the sum of expected values, even when the summands are not independent):

$$ \mathbb{E}_{b,S}[W] \geq d \cdot p_0 = d \cdot \frac{1 - \frac{2\epsilon\sqrt{m}}{\sqrt{d}}}{2}. $$

From Step 3, the excess error equals \(2\epsilon W / d\). So the expected excess error is:

$$ \mathbb{E}_{b,S}[\text{excess error}] = \frac{2\epsilon}{d} \cdot \mathbb{E}[W] \geq \frac{2\epsilon}{d} \cdot d \cdot p_0 = 2\epsilon \cdot p_0 = \epsilon\!\left(1 - \frac{2\epsilon\sqrt{m}}{\sqrt{d}}\right). $$

For \(m < d/(16\epsilon^2)\): the quantity \(2\epsilon\sqrt{m/d} < 2\epsilon \cdot 1/(4\epsilon) = 1/2\), so:

$$ \mathbb{E}_{b,S}[\text{excess error}] > \epsilon \cdot (1 - 1/2) = \frac{\epsilon}{2}. $$

What does this mean? Averaged over Nature's random choice of secret and the random training data, the learner's excess error exceeds \(\epsilon/2\). No matter how clever the algorithm is, the average performance is bad.

Step 9: Find a specific hard distribution.

Step 8 showed that the average excess error over random \(b\) exceeds \(\epsilon/2\). But the learner needs to work for every distribution, not just on average. We now show there's a specific secret \(b^*\) that's hard.

The averaging argument is simple: if the average of a collection of numbers exceeds \(\epsilon/2\), then at least one of those numbers exceeds \(\epsilon/2\). (If every number were \(\leq \epsilon/2\), the average couldn't exceed \(\epsilon/2\).) So there exists a specific secret string \(b^*\) such that:

$$ \mathbb{E}_{S}[\text{excess error under } \mathcal{D}_{b^*}] > \frac{\epsilon}{2}. $$

For this specific distribution \(\mathcal{D}_{b^*}\), the learner's expected excess error exceeds \(\epsilon/2\), no matter which algorithm is used.

Step 10: Convert expected error into a failure probability.

We know: for distribution \(\mathcal{D}_{b^*}\), the learner's excess error (call it \(X\)) is a random variable (depending on the random training set \(S\)) with:

• \(\mathbb{E}[X] > \epsilon/2\) (from Step 9).
• \(X \geq 0\) (excess error is non-negative).
• \(X \leq 2\epsilon\) (the worst case is getting all \(d\) bits wrong, giving excess error \(2d\epsilon/d = 2\epsilon\)).

We want to show that \(X\) is large with noticeable probability, not just on average. The tool is a truncated expectation bound: split the expectation based on whether \(X\) is above or below a threshold \(t\).

$$ \mathbb{E}[X] = \mathbb{E}[X \cdot \mathbf{1}_{X \leq t}] + \mathbb{E}[X \cdot \mathbf{1}_{X > t}]. $$

The first term is at most \(t \cdot 1 = t\) (since \(X \leq t\) when the indicator is 1, and the indicator has probability at most 1). The second term is at most \(2\epsilon \cdot \Pr[X > t]\) (since \(X \leq 2\epsilon\) always). So:

$$ \mathbb{E}[X] \leq t + 2\epsilon \cdot \Pr[X > t]. $$

Rearranging:

$$ \Pr[X > t] \geq \frac{\mathbb{E}[X] - t}{2\epsilon}. $$

Choosing the threshold \(t\). The bound \(\Pr[X > t] \geq (\mathbb{E}[X] - t)/(2\epsilon)\) works for any \(t\), but we need \(t < \mathbb{E}[X]\) (otherwise the right side is zero or negative and the bound says nothing). Since \(\mathbb{E}[X] > \epsilon/2\), any \(t < \epsilon/2\) works. The choice of \(t\) involves a tradeoff:

• Smaller \(t\): the numerator \(\mathbb{E}[X] - t\) is larger, giving a stronger probability bound, but the accuracy guarantee ("\(X > t\)") is weaker.
• Larger \(t\) (closer to \(\epsilon/2\)): the accuracy guarantee is stronger, but the probability bound shrinks toward zero.

We pick \(t = \epsilon/4\) — the midpoint of \([0, \epsilon/2]\) — to balance these. Any choice in the range \((0, \epsilon/2)\) would give the same \(\Omega(d/\epsilon^2)\) scaling; only the constant \(C_1\) changes.

With \(t = \epsilon/4\) and \(\mathbb{E}[X] > \epsilon/2\):

$$ \Pr[\text{excess error} > \epsilon/4] \geq \frac{\epsilon/2 - \epsilon/4}{2\epsilon} = \frac{\epsilon/4}{2\epsilon} = \frac{1}{8}. $$

In words: the learner's excess error exceeds \(\epsilon/4\) with probability at least \(1/8\). An algorithm that aims for excess error at most \(\epsilon/4\) with 87.5% success cannot exist when \(m < d/(16\epsilon^2)\).

Step 11: State the lower bound (absorbing constants).

We showed: if \(m < d/(16\epsilon^2)\), then for some distribution \(\mathcal{D}_{b^*}\), any learner has excess error \(> \epsilon/4\) with probability \(\geq 1/8\).

This is a lower bound on \(m_{\mathcal{H}}(\epsilon/4, \, 7/8)\) — the sample complexity for accuracy \(\epsilon/4\) and confidence \(7/8\). To express it in terms of general \(\epsilon\), substitute \(\epsilon' = \epsilon/4\) (so \(\epsilon = 4\epsilon'\)):

$$ m_{\mathcal{H}}(\epsilon', 7/8) \geq \frac{d}{16 \cdot (4\epsilon')^2} = \frac{d}{256\,\epsilon'^2}. $$

Dropping the prime and writing \(C_1 = 1/256\):

$$ m_{\mathcal{H}}(\epsilon, \delta) \geq \frac{d}{256\,\epsilon^2} \quad \text{for } \delta \leq 7/8. $$

The constant 256 can be improved to 64 with a tighter analysis (using exact Le Cam bounds instead of Pinsker's slightly loose upper bound on TV). The key point is the scaling: the lower bound is \(\Omega(d/\epsilon^2)\), matching the upper bound from Section 10 up to constants and the \(\ln(1/\epsilon)\) factor. \(\square\) (Part A)

Proof — Part B: \(m \geq \ln(1/(2\delta))/(2\epsilon^2)\)

What Part B says: Even if the hypothesis class is trivially simple (\(d = 1\), just a single threshold), achieving high confidence (small failure probability \(\delta\)) requires \(\Omega(\ln(1/\delta)/\epsilon^2)\) samples. Part A showed that learning \(d\) bits is hard; Part B shows that learning even one bit reliably is hard.

Setup: Take a single shattered point \(x_1\) and consider just two worlds:

• World 0: the label at \(x_1\) is 0 with probability \(1/2 + \epsilon\) and 1 with probability \(1/2 - \epsilon\). The best classifier predicts \(\hat{h}(x_1) = 0\).
• World 1: the label at \(x_1\) is 1 with probability \(1/2 + \epsilon\) and 0 with probability \(1/2 - \epsilon\). The best classifier predicts \(\hat{h}(x_1) = 1\).

All \(m\) training samples are at \(x_1\) (it's the only point), so the learner sees a sequence of labels \(Y_1, Y_2, \ldots, Y_m\). In World 0, each \(Y_i\) is 0 with probability \(0.5 + \epsilon\). In World 1, each \(Y_i\) is 1 with probability \(0.5 + \epsilon\). The learner must determine which world it's in.

The natural test: Compute the fraction of 1s: \(\bar{Y} = \frac{1}{m}\sum_{i=1}^m Y_i\). In World 0, \(\mathbb{E}[\bar{Y}] = 1/2 - \epsilon\). In World 1, \(\mathbb{E}[\bar{Y}] = 1/2 + \epsilon\). So the learner should guess World 0 if \(\bar{Y} < 1/2\) and World 1 if \(\bar{Y} > 1/2\).

When does this test fail? The test fails when \(\bar{Y}\) lands on the wrong side of \(1/2\). By Hoeffding's inequality (Section 4: for bounded i.i.d. random variables with \(Y_i \in [0,1]\), \(\Pr[|\bar{Y} - \mathbb{E}[\bar{Y}]| \geq t] \leq 2e^{-2mt^2}\)):

$$ \Pr[\text{test fails}] = \Pr\!\left[|\bar{Y} - \mathbb{E}[\bar{Y}]| \geq \epsilon\right] \leq 2e^{-2m\epsilon^2}. $$

For this failure probability to be at most \(\delta\), we need:

$$ 2e^{-2m\epsilon^2} \leq \delta \quad \Longrightarrow \quad e^{-2m\epsilon^2} \leq \frac{\delta}{2} \quad \Longrightarrow \quad 2m\epsilon^2 \geq \ln\!\frac{2}{\delta} = \ln\frac{1}{(\delta/2)} \quad \Longrightarrow \quad m \geq \frac{\ln(2/\delta)}{2\epsilon^2} = \frac{\ln(1/(2\delta)) + \ln 2}{2\epsilon^2}. $$

Since \(\ln 2 > 0\), this gives \(m \geq \ln(1/(2\delta))/(2\epsilon^2)\). (We can also write it as \(m \geq \ln(2/\delta)/(2\epsilon^2)\) — the difference is just a small constant.)

Why this is a lower bound, not just an analysis of one test: The Hoeffding test (compare \(\bar{Y}\) to \(1/2\)) is actually the optimal test in this setting. Any other algorithm sees the same \(m\) coin flips and must determine the bias. The sufficient statistic is \(\sum Y_i\) (by the Neyman–Pearson lemma, the likelihood ratio test is optimal, and for Bernoulli data the likelihood ratio is a monotone function of \(\sum Y_i\)). So the \(2e^{-2m\epsilon^2}\) bound on the best test's failure rate is tight up to constants, and no algorithm can achieve failure probability \(\leq \delta\) with fewer than \(\Omega(\ln(1/\delta)/\epsilon^2)\) samples.

\(\square\) (Part B)

Combining Parts A and B

The two requirements are independent bottlenecks: Part A says you need \(\Omega(d/\epsilon^2)\) samples to handle the complexity of the hypothesis class (\(d\) noisy bits to identify), and Part B says you need \(\Omega(\ln(1/\delta)/\epsilon^2)\) samples to guarantee high confidence (even for a single bit). Both must be satisfied simultaneously, so we add them:

$$ m_{\mathcal{H}}(\epsilon, \delta) \geq C_1 \frac{d + \ln(1/\delta)}{\epsilon^2} $$

where \(C_1\) is an absolute constant (from Part A's \(1/256\) and Part B's \(1/2\), the binding constant is the smaller one). The exact value of \(C_1\) depends on the tightness of the intermediate bounds (Pinsker, the small-bias KL lemma, the truncated Markov step), but the scaling \(\Omega((d + \ln(1/\delta))/\epsilon^2)\) is what matters — it matches the upper bound from Section 10 up to constants and the mild \(\ln(1/\epsilon)\) factor. \(\square\)

Numerical Check (Full Lower Bound)

For linear classifiers in \(\mathbb{R}^{10}\) (\(d = 11\)) with \(\epsilon = 0.05\) and \(\delta = 0.05\), using the explicit constants from Parts A and B:

• Part A: \(m \geq 11/(256 \times 0.0025) = 11/0.64 \approx 17\) samples (for the 11 bits).
• Part B: \(m \geq \ln(40)/(2 \times 0.0025) = 3.69/0.005 = 738\) samples (for the 95% confidence).
• Total lower bound: \(m \geq 17 + 738 = 755\) samples.
• Upper bound (from Section 10): \(m \leq \sim 2{,}800\) samples.

The lower bound (755) and upper bound (2,800) are within a factor of ~4. Part B (confidence) dominates for small \(d\). For higher-dimensional problems (large \(d\)), Part A (complexity) dominates instead. With tighter constants (sharper Pinsker, exact Le Cam), the gap narrows further. The key point: the \(d/\epsilon^2\) and \(\ln(1/\delta)/\epsilon^2\) scaling is correct on both sides. \(\checkmark\)

What the Lower Bound Tells Us

The proof reveals why the sample complexity is \(\Theta(d/\epsilon^2)\). There are two completely different bottlenecks, both unavoidable:

• Complexity bottleneck (\(d/\epsilon^2\)): The shattered set provides \(d\) points where the correct label could go either way. Each point is a noisy coin whose bias (which side of 50%) the learner must determine. Each coin requires \(\sim 1/\epsilon^2\) flips, and the \(d\) coins share the \(m\) samples, so the total cost is \(d/\epsilon^2\).
• Confidence bottleneck (\(\ln(1/\delta)/\epsilon^2\)): Even a single coin requires \(\ln(1/\delta)/\epsilon^2\) flips to achieve failure probability \(\delta\). This cost doesn't grow with \(d\) — it's the price of being confident about any one decision.

No algorithm can cheat past either bottleneck. The upper bound from Section 10 was not wasteful — it captured the right scaling.

Reading the Formula

• \(d/\epsilon^2\): VC dimension \(d\) sets the complexity cost. Each shattered point is one "degree of freedom" that the learner must pin down, and each costs \(\sim 1/\epsilon^2\) samples because the signal is only \(\epsilon\)-strong.
• \(\ln(1/\epsilon)\) in the upper bound: A mild logarithmic overhead from converting the VC bound's polynomial-times-exponential form into a clean sample complexity. The upper and lower bounds nearly match — the gap is just this \(\ln(1/\epsilon)\) factor.
• \(\ln(1/\delta)/\epsilon^2\): Higher confidence costs only logarithmically more data. Going from 95% to 99.99% confidence barely changes the sample size (the ratio is \(\ln(1/0.0001)/\ln(1/0.05) = 9.21/3.00 \approx 3\times\)).

Sample Complexities

Hypothesis class	VC dimension \(d\)	Computation	Approximate \(m\)
Thresholds on \(\mathbb{R}\)	1	\(\frac{1 + 3.0}{2 \times 0.0025} = \frac{4.0}{0.005}\)	\(\sim 800\)
Intervals on \(\mathbb{R}\)	2	\(\frac{2 + 3.0}{0.005} = \frac{5.0}{0.005}\)	\(\sim 1{,}000\)
Linear classifiers in \(\mathbb{R}^{10}\)	11	\(\frac{11 + 3.0}{0.005} = \frac{14.0}{0.005}\)	\(\sim 2{,}800\)
Linear classifiers in \(\mathbb{R}^{100}\)	101	\(\frac{101 + 3.0}{0.005} = \frac{104}{0.005}\)	\(\sim 20{,}800\)

These are computed from the simplified VC upper bound. The exact numbers depend on which constant \(C_2\) you use — different formulations of the VC bound give slightly different constants. The key pattern is that \(m\) scales linearly with \(d\): doubling the VC dimension roughly doubles the sample requirement.

Reading the Table

Take the row for linear classifiers in \(\mathbb{R}^{100}\): VC dimension \(d = 101\) (we proved this in Section 7: halfspaces in \(\mathbb{R}^d\) have \(\operatorname{VCdim} = d + 1\)). With ~20,800 samples:

• Uniform convergence: For every linear classifier, training error is within 5% of true error.
• ERM works: The classifier with the lowest training error has true error within 10% (\(2\epsilon\)) of the best possible linear classifier.
• Agnostic guarantee: This holds even if no linear classifier fits the data well. If the best linear classifier has 20% error, ERM finds one with at most 30% error.

Note that 20,800 samples in 100 dimensions is far fewer than the number of possible linear classifiers (which is uncountably infinite). This is the power of VC theory: the sample complexity depends on VC dimension, not on the size of the class.

For \(x \in [a, b]\), the chord connecting \((a, e^{sa})\) and \((b, e^{sb})\) is:

$$ \ell(x) = e^{sa} + \frac{e^{sb} - e^{sa}}{b - a}(x - a) = \frac{b - x}{b - a}\, e^{sa} + \frac{x - a}{b - a}\, e^{sb}. $$

Since \(f(x) = e^{sx}\) is convex (\(f''(x) = s^2 e^{sx} > 0\)), we have \(f(x) \leq \ell(x)\) for all \(x \in [a,b]\). This is the definition of convexity: the function lies below any chord.

Numerical check: Let \(s = 1\), \(a = -2\), \(b = 3\), \(x = 0\).

• \(e^{sx} = e^0 = 1\).
• Chord: \(\frac{3-0}{5}e^{-2} + \frac{0-(-2)}{5}e^3 = 0.6 \cdot 0.135 + 0.4 \cdot 20.09 = 0.081 + 8.036 = 8.117\).

Indeed \(1 \leq 8.117\). \(\checkmark\)

\(\mathcal{H}\) = intervals on \(\mathbb{R}\), \(\operatorname{VCdim} = 2\). For \(m = 5\):

$$ \Phi(5, 2) = \binom{5}{0} + \binom{5}{1} + \binom{5}{2} = 1 + 5 + 10 = 16. $$

Direct count: on 5 ordered points \(x_1 < \cdots < x_5\), an interval \([a,b]\) labels a contiguous block as 1 and everything else as 0. The number of contiguous blocks (including the empty block) on 5 points is \(\binom{5}{2} + 5 + 1 = 16\) (choose two endpoints among the 5 points, or a single-point interval, or the empty interval).

Exact match: \(|\mathcal{H}_C| = 16 = \Phi(5, 2)\). The Sauer–Shelah bound is tight here. \(\checkmark\)