PAC Learning and Finite Hypothesis Classes

How many examples a learner needs before it can promise, for every distribution of the data, that the rule it returns is probably nearly the best one available. Defines probably approximately correct (PAC) learning in the realizable and the agnostic case; proves that every finite class is PAC learnable with ln(|H|/δ)/ε examples when some rule in it is perfect, by a union bound over the bad rules, and agnostically with 2 ln(2|H|/δ)/ε² examples, by Hoeffding's inequality and a union bound; derives the discretization trick for classes with d real parameters stored in b bits; proves Kraft's inequality and the Occam bound, in which each rule pays for its own description length; and proves the no-free-lunch theorem of learning theory, contrasting it with the no-free-lunch theorems of optimization. Worked on threshold rules for diabetes from HbA1c in 5,210 NHANES adults, a finite class of 201 rules: the realizable bound asks for 830 examples where 229 suffice, and in 30 seeded samples at each of nine sizes the agnostic bound is about three times the largest deviation observed. Worked problems on a sample size for a stricter guarantee, the guarantee at 500 examples, an Occam bound for one threshold and the no-free-lunch theorem on four points.

Of the 5,210 adults examined by NHANES in 2017 and 2018 (National Center for Health Statistics, 2020) who had an HbA1c result and answered the diabetes question, 806 said a doctor had told them they had diabetes. A rule of the form "predict diabetes when HbA1c is at least $\theta$" can be learned from a sample of these adults by choosing the $\theta$ that makes the fewest mistakes on the sample. On a small sample the chosen threshold may be poor by bad luck. How many adults must we sample before we can promise, with a stated probability, that the learned rule is nearly as good as the best rule of its kind, whatever the population looks like?

PAC learning, short for probably approximately correct learning, makes that question precise. A class of rules is PAC learnable when some algorithm, given enough examples, returns a rule whose error is within $\varepsilon$ of the best possible with probability at least $1 - \delta$. The number of examples it needs may depend on $\varepsilon$ and $\delta$ but not on the distribution that generates the data. The definition goes back to Valiant (1984), whose abstract describes learning as "knowledge acquisition in the absence of explicit programming" and asks which classes of concepts can be learned in a polynomial number of steps.

First we state the definition, in the case where some rule of the class makes no errors and in the general, agnostic case. Then we prove that every finite class is PAC learnable in both cases and measure, on the NHANES thresholds, how many examples the proofs ask for against how many suffice. Next come two ways to apply finite-class results to classes that are not finite: storing parameters in finitely many bits, and charging each rule for the length of its description. Finally the no-free-lunch theorem shows why a learner needs a restricted class at all. The article assumes Empirical Risk Minimization, which defines risk, empirical risk and the empirical risk minimizer, and Concentration Inequalities: Hoeffding and Bernstein, which proves Hoeffding's inequality.

Notation and the running data

The notation is that of the unit, set out in Empirical Risk Minimization. An example is a pair $z = (x, y)$ with $x$ in an instance space $\mathcal{X}$ and a label $y \in \{0, 1\}$. The examples come from an unknown distribution $\mathcal{D}$ on $\mathcal{X} \times \{0, 1\}$. A training sample $S = (z_1, \ldots, z_m)$ of size $m$ is drawn independently and identically distributed (i.i.d.) from $\mathcal{D}$, written $S \sim \mathcal{D}^m$. A hypothesis, or rule, is a function $h : \mathcal{X} \to \{0, 1\}$, and a hypothesis class $\mathcal{H}$ is a set of rules fixed before the data are seen. With the 0-1 loss, the risk of $h$ is its error rate on new examples and the empirical risk its error rate on the sample:

$$L_{\mathcal{D}}(h) = P_{(x, y) \sim \mathcal{D}}\big(h(x) \ne y\big), \qquad L_S(h) = \frac{1}{m}\sum_{i=1}^m \mathbf{1}\{h(x_i) \ne y_i\}.$$

An empirical risk minimizer (ERM) is any $h_S \in \mathcal{H}$ with the smallest empirical risk. The accuracy is $\varepsilon$ and the confidence $1 - \delta$. Logarithms are natural ($\ln$), as in Shalev-Shwartz and Ben-David (2014), the textbook this unit follows; $\log_2$ appears only where bits are counted.

The running data. The population is the 5,210 adults of Empirical Risk Minimization: NHANES 2017 to 2018, aged 18 or over, not pregnant, with an HbA1c result and an answer of yes, no or borderline to the diabetes question. The label is $y = 1$ for a yes; 806 adults have it. We treat the 5,210 adults as a finite population and take $\mathcal{D}$ to be the distribution of one adult drawn at random from it. Then every risk is an exact fraction with denominator 5,210, and a sample $S \sim \mathcal{D}^m$ is $m$ draws with replacement, which are exactly i.i.d. HbA1c is reported in tenths of a percent and takes 94 distinct values here, from 3.8% to 16.2%.

The class is the threshold rules $h_\theta(x) = \mathbf{1}\{x \ge \theta\}$. Because every HbA1c value is a multiple of 0.1 below 20%, the thresholds $\theta = 0.0, 0.1, \ldots, 20.0$ already give every threshold rule that can be told apart on such data. We fix this class before looking at any sample: $\mathcal{H}$ has $|\mathcal{H}| = 201$ rules. It is a finite class that arises naturally, from the resolution of a laboratory report. On the population the best of them is $\theta = 6.7\%$, with 437 errors, so $\min_{h \in \mathcal{H}} L_{\mathcal{D}}(h) = 437/5{,}210 = 0.0839$; Empirical Risk Minimization finds it and compares it with the Bayes classifier.

The definition

Here is the idea in plain words. A learner is judged on two counts. It should usually succeed, and when it succeeds its rule should be nearly as good as the target. Both "usually" and "nearly" are fixed numbers, $\delta$ and $\varepsilon$. The promise must hold for every distribution of the data, so the learner cannot rely on luck about the population.

The first version assumes that the class contains a perfect rule. The realizability assumption for $\mathcal{H}$ and $\mathcal{D}$ says that some $h^* \in \mathcal{H}$ has $L_{\mathcal{D}}(h^*) = 0$. Following Shalev-Shwartz and Ben-David (2014, Definition 3.1), a class $\mathcal{H}$ is PAC learnable if there are a function $m_{\mathcal{H}} : (0, 1)^2 \to \mathbb{N}$ and a learning algorithm $A$ with this property. For every $\varepsilon, \delta \in (0, 1)$ and every distribution $\mathcal{D}$ for which the realizability assumption holds, if $A$ is run on $m \ge m_{\mathcal{H}}(\varepsilon, \delta)$ i.i.d. examples from $\mathcal{D}$, then with probability at least $1 - \delta$ over the examples it returns a rule $h$ with $L_{\mathcal{D}}(h) \le \varepsilon$. The smallest such function is the sample complexity of $\mathcal{H}$.

The realizability assumption rarely holds. Two adults with the same HbA1c can differ in diagnosis, so no rule that sees only HbA1c is perfect, and the best threshold errs on 437 of the 5,210. The general version measures the learner against the best rule of the class instead of against zero. A class $\mathcal{H}$ is agnostic PAC learnable (Shalev-Shwartz and Ben-David, 2014, Definition 3.3) if there are $m_{\mathcal{H}}$ and $A$ such that for every $\varepsilon, \delta \in (0, 1)$ and every distribution $\mathcal{D}$ on $\mathcal{X} \times \{0, 1\}$, running $A$ on $m \ge m_{\mathcal{H}}(\varepsilon, \delta)$ i.i.d. examples returns, with probability at least $1 - \delta$, a rule $h$ with

$$L_{\mathcal{D}}(h) \le \min_{h' \in \mathcal{H}} L_{\mathcal{D}}(h') + \varepsilon.$$

When realizability holds, the minimum is zero and the agnostic promise is the realizable one. Shalev-Shwartz and Ben-David credit the agnostic formalization to Haussler (1992) and the general setting of learning with a loss function to Vapnik and Chervonenkis (1971) and Vapnik's later books.

Three features of the definition matter below.

  • The sample size is uniform over distributions. The same $m_{\mathcal{H}}(\varepsilon, \delta)$ must work for every $\mathcal{D}$. A bound that held only for well-behaved populations would not qualify.
  • The guarantee is relative to the class. The agnostic promise says nothing about how good the best rule in $\mathcal{H}$ is. That is the approximation error of Empirical Risk Minimization, and only the choice of class controls it.
  • Computation is set aside. Valiant's definition also required the learner to run in polynomial time; his abstract speaks of a "reasonable (polynomial) number of steps". Shalev-Shwartz and Ben-David (2014, §3.4) separate the statistical question from the computational one and keep the name PAC for the statistical part, as we do here. For a finite class the ERM can be computed by checking every rule, so the question does not arise.

Example (the promise is not about the typical sample). A sample complexity of 830 at $\varepsilon = 0.01$ and $\delta = 0.05$ does not mean that a learner with 830 examples typically has a risk of 0.01. It means that, for every distribution allowed, at most 5% of samples lead to a risk above 0.01; the bound is set by the worst of them. On a given population the typical risk can be far smaller, and the experiments below show by how much.

Finite classes in the realizable case

Here is the idea in one sentence. A rule with risk above $\varepsilon$ survives $m$ independent examples without a mistake with probability at most $(1 - \varepsilon)^m$, and there are at most $|\mathcal{H}|$ such rules, so the chance that any of them survives is at most $|\mathcal{H}|(1 - \varepsilon)^m$.

Two facts are used. The union bound says that $P(A_1 \cup \cdots \cup A_k) \le P(A_1) + \cdots + P(A_k)$ for any events; Multiple Comparisons and the Bonferroni Correction proves it. The other is an elementary inequality.

Lemma 1. For every real $u$, $1 - u \le e^{-u}$.

Proof. The function $g(u) = e^{-u} - (1 - u)$ has $g(0) = 0$ and $g'(u) = 1 - e^{-u}$, which is negative for $u < 0$ and positive for $u > 0$. So $g$ decreases to its minimum 0 at $u = 0$ and then increases, and $g(u) \ge 0$ everywhere. $\square$

Theorem 1 (finite classes, realizable case). Let $\mathcal{H}$ be finite, let the realizability assumption hold for $\mathcal{D}$, and let $h_S$ be any ERM. For every $\varepsilon > 0$ and every $m$,

$$P_{S \sim \mathcal{D}^m}\big(L_{\mathcal{D}}(h_S) > \varepsilon\big) \;\le\; |\mathcal{H}|\,(1 - \varepsilon)^m \;\le\; |\mathcal{H}|\,e^{-\varepsilon m}.$$

Consequently $\mathcal{H}$ is PAC learnable by ERM with sample complexity

$$m_{\mathcal{H}}(\varepsilon, \delta) \;\le\; \left\lceil \frac{\ln(|\mathcal{H}|/\delta)}{\varepsilon} \right\rceil,$$

and, equivalently, with probability at least $1 - \delta$, $L_{\mathcal{D}}(h_S) \le \ln(|\mathcal{H}|/\delta)/m$.

Proof. Call a rule bad if its risk exceeds $\varepsilon$, and let $\mathcal{H}_B = \{h \in \mathcal{H} : L_{\mathcal{D}}(h) > \varepsilon\}$. Under realizability the perfect rule $h^*$ makes no mistake on any example drawn from $\mathcal{D}$, except on an event of probability zero, so $L_S(h^*) = 0$ and every ERM also has $L_S(h_S) = 0$. If $h_S$ is bad, then some bad rule has zero empirical risk. Hence

$$\{L_{\mathcal{D}}(h_S) > \varepsilon\} \;\subseteq\; \bigcup_{h \in \mathcal{H}_B}\{L_S(h) = 0\},$$

and by the union bound

$$P\big(L_{\mathcal{D}}(h_S) > \varepsilon\big) \;\le\; \sum_{h \in \mathcal{H}_B} P\big(L_S(h) = 0\big).$$

Fix a bad rule $h$. The event $L_S(h) = 0$ says that $h$ is right on each of the $m$ examples. The examples are independent, and each is classified correctly with probability $1 - L_{\mathcal{D}}(h) < 1 - \varepsilon$, so $P(L_S(h) = 0) = (1 - L_{\mathcal{D}}(h))^m \le (1 - \varepsilon)^m$. Summing over at most $|\mathcal{H}|$ bad rules gives the first inequality, and Lemma 1 with $u = \varepsilon$ gives the second.

For the sample complexity, $|\mathcal{H}|e^{-\varepsilon m} \le \delta$ exactly when $m \ge \ln(|\mathcal{H}|/\delta)/\varepsilon$. For the last form, set $\varepsilon = \ln(|\mathcal{H}|/\delta)/m$: then $|\mathcal{H}|e^{-\varepsilon m} = \delta$. $\square$

This is Corollary 2.3 of Shalev-Shwartz and Ben-David (2014), restated as their Corollary 3.2, and Theorem 2.5 of Mohri, Rostamizadeh and Talwalkar (2018), whose version covers any algorithm that returns a rule with no training errors.

Three things about the bound deserve notice. It grows with $\ln|\mathcal{H}|$, so squaring the number of rules only doubles the logarithm. It falls like $1/m$, not $1/\sqrt{m}$, because a single mistake is enough to expose a bad rule. And it uses nothing about $\mathcal{D}$ beyond realizability, which is the price of its uniformity.

The ADA rule learned from its own labels

The NHANES diagnosis labels are not realizable by a threshold, so for a realizable example we make labels that are. The American Diabetes Association counts an HbA1c of 6.5% or more as a criterion for diabetes (American Diabetes Association Professional Practice Committee, 2025, Table 2.1). Label each adult $y = \mathbf{1}\{x \ge 6.5\}$. Then the threshold $\theta^* = 6.5$ in $\mathcal{H}$ is perfect, and a learner that sees a sample of HbA1c values with these labels must recover a cut point. In the population 746 adults meet the criterion and 4,464 do not.

The learner is ERM with ties broken toward the smallest threshold, as in Empirical Risk Minimization. A threshold has no training errors when it lies above every sampled value below 6.5 and at or below every sampled value of 6.5 or more. The smallest such threshold is one tenth above the largest sampled value below 6.5. Its risk is the share of the population strictly between that value and 6.5: those adults are labeled 0 but predicted 1.

What Theorem 1 asks for. With $|\mathcal{H}| = 201$ and $\delta = 0.05$, $\ln(|\mathcal{H}|/\delta) = \ln 4{,}020 = 8.299$. A risk of at most $\varepsilon = 0.01$ is guaranteed from $m = 830$ examples on.

What suffices on this population. Because the risk depends only on the largest sampled value below 6.5, its distribution can be computed exactly. Write $M$ for that value and $w(c)$ for the share of the population with $c < x < 6.5$. The sample's largest value below 6.5 is at most $c$ exactly when no example falls in $(c, 6.5)$, so $P(M \le c) = (1 - w(c))^m$, and the risk of the learned rule is $w(M)$. The script evaluates this for every $m$. The smallest $m$ at which the risk is at most 0.01 with probability at least 0.95 is 229, against the 830 the theorem asks for.

The distribution has a feature worth seeing. HbA1c is reported in tenths, and 68 adults have exactly 6.4%. A sample that contains one of them is followed by a threshold of exactly 6.5 and a risk of zero; a sample that misses them all has a risk of at least $68/5{,}210 = 0.0131$. This is why the exact percentiles below move in steps.

$m$ bound $\ln(\lvert\mathcal{H}\rvert/\delta)/m$ one-threshold bound $\ln(1/\delta)/m$ exact mean risk exact 95th percentile exact $P(\text{risk} > \text{bound})$ 30 runs: median (IQR)
30 0.2766 0.0999 0.0233 0.0835 0.00002 0.0131 (0.0131 to 0.0298)
100 0.0830 0.0300 0.0044 0.0131 0.0002 0 (0 to 0.0098)
300 0.0277 0.0100 0.0003 0 0.0001 0 (0 to 0)
1,000 0.0083 0.0030 below 0.0001 0 0.000002 0 (0 to 0)

The last column comes from 30 samples at each size (seeds 116,000,001 to 116,000,030) and agrees with the exact distribution. The bound holds with room to spare: where it allows a 5% chance of failure, the exact chance of exceeding it is at most 0.0002.

Left, the realizable case: the bound of Theorem 1 (blue), the one-threshold bound of Proposition 1 (dashed), and the exact 95th percentile and mean of the learned rule's risk. Notice that the one-threshold bound tracks the 95th percentile and the finite-class bound sits well above both. Right, the agnostic case on log scales: the bound of Theorem 2 against the largest deviation over the 201 rules in 30 samples (median, interquartile range and the largest of the 30). Notice that the observed curve runs parallel to the bound, about three times below it.
Left, the realizable case: the bound of Theorem 1 (blue), the one-threshold bound of Proposition 1 (dashed), and the exact 95th percentile and mean of the learned rule's risk. Notice that the one-threshold bound tracks the 95th percentile and the finite-class bound sits well above both. Right, the agnostic case on log scales: the bound of Theorem 2 against the largest deviation over the 201 rules in 30 samples (median, interquartile range and the largest of the 30). Notice that the observed curve runs parallel to the bound, about three times below it.

Where the slack comes from. The union bound in Theorem 1 treats the 200 bad thresholds as if each could survive separately. Here their survival events are nested: a threshold far below 6.5 survives only if a closer one does. A direct argument removes the factor $|\mathcal{H}|$.

Proposition 1 (one threshold suffices). Let $x$ take values on the grid of the class, let the labels be $y = \mathbf{1}\{x \ge \theta^*\}$ for a grid value $\theta^*$, let $\mathcal{D}$ be any distribution of $x$ on that grid, and let the learner return the smallest threshold with no training errors, one grid step above the largest sampled value below $\theta^*$. Then $P(L_{\mathcal{D}}(h_S) > \varepsilon) \le (1 - \varepsilon)^m \le e^{-\varepsilon m}$, so $m \ge \ln(1/\delta)/\varepsilon$ examples suffice.

Proof. Let $M$ be the largest sampled value below $\theta^*$, with $M = -\infty$ when no example falls below $\theta^*$ (the learner then returns the smallest threshold, which predicts 1 everywhere). For $c$ a grid value below $\theta^*$ or $-\infty$, let $w(c) = P(c < x < \theta^*)$, so that the learner's risk is $w(M)$, and $w$ does not increase as $c$ increases. Let $c^*$ be the smallest $c$ with $w(c) \le \varepsilon$; it exists because $w$ is zero at the grid value just below $\theta^*$. If $c^* = -\infty$, every possible risk is at most $\varepsilon$ and there is nothing to prove. Otherwise let $c'$ be the grid value just below $c^*$ (or $-\infty$). By the choice of $c^*$, $w(c') > \varepsilon$, and since no grid value lies strictly between $c'$ and $c^*$, $w(c') = P(c^* \le x < \theta^*)$. Now if the risk exceeds $\varepsilon$, then $w(M) > \varepsilon \ge w(c^*)$, so $M < c^*$, which means that no example fell in $[c^*, \theta^*)$. That set has probability $w(c') > \varepsilon$, so $m$ independent examples all miss it with probability less than $(1 - \varepsilon)^m$. Lemma 1 finishes the proof. $\square$

The proposition is the one-sided half of Lemma 6.1 of Shalev-Shwartz and Ben-David (2014), who prove $\ln(2/\delta)/\varepsilon$ for any ERM over thresholds; a general ERM can err on either side of $\theta^*$, which costs the 2. On the NHANES labels the one-threshold bound, $\ln 20/m = 2.996/m$, stays above the exact 95th percentile, as it must, and far closer to it than the finite-class bound; it asks for 300 examples at $\varepsilon = 0.01$ where 229 suffice. The finite-class bound is looser by the factor $\ln 4{,}020/\ln 20 = 2.77$. The two bounds do not promise the same thing: Theorem 1 covers every ERM, Proposition 1 one particular ERM. Against Shalev-Shwartz and Ben-David's bound, which holds for every ERM over thresholds, most of the gap, $\ln 4{,}020/\ln 40 = 2.25$, is the price of the union bound over 200 bad rules; the rest, $\ln 40/\ln 20 = 1.23$, comes from fixing the tie-break so that the learner can err on one side only.

Finite classes in the agnostic case

With real diagnoses no threshold is perfect, and the proof of Theorem 1 breaks at its first step: the best rule has training errors too, so a bad rule is no longer exposed by a single mistake. What we need instead is that every rule's training error is close to its risk at once. Then the rule with the smallest training error has nearly the smallest risk.

A sample is $\varepsilon$-representative if $\lvert L_S(h) - L_{\mathcal{D}}(h)\rvert \le \varepsilon$ for every $h \in \mathcal{H}$ (Shalev-Shwartz and Ben-David, 2014, Definition 4.1). Empirical Risk Minimization proves (Proposition 1 there) that the estimation error of any ERM is at most twice the largest deviation over the class, $L_{\mathcal{D}}(h_S) - \min_{h \in \mathcal{H}} L_{\mathcal{D}}(h) \le 2\sup_{h \in \mathcal{H}}\lvert L_{\mathcal{D}}(h) - L_S(h)\rvert$. So on an $(\varepsilon/2)$-representative sample every ERM is within $\varepsilon$ of the best rule. A class has the uniform convergence property if some function $m^{\mathrm{UC}}_{\mathcal{H}}(\varepsilon, \delta)$ makes a sample of that size $\varepsilon$-representative with probability at least $1 - \delta$, for every $\mathcal{D}$ (Definition 4.3 there). Uniform convergence with $m^{\mathrm{UC}}_{\mathcal{H}}$ therefore gives agnostic PAC learnability by ERM with $m_{\mathcal{H}}(\varepsilon, \delta) \le m^{\mathrm{UC}}_{\mathcal{H}}(\varepsilon/2, \delta)$.

For one fixed rule, $L_S(h)$ is the mean of $m$ independent indicators $\mathbf{1}\{h(x_i) \ne y_i\}$, each in $[0, 1]$ with mean $L_{\mathcal{D}}(h)$. Hoeffding's inequality, Theorem 2 of Concentration Inequalities: Hoeffding and Bernstein, says that for $m$ independent variables in $[0, 1]$ whose average is $\bar X_m$,

$$P\big(\lvert \bar X_m - E\bar X_m\rvert \ge \varepsilon\big) \le 2e^{-2m\varepsilon^2}.$$

Theorem 2 (finite classes, agnostic case). Let $\mathcal{H}$ be finite and the loss take values in $[0, 1]$. For every $\mathcal{D}$, every $\varepsilon > 0$ and every $m$,

$$P_{S \sim \mathcal{D}^m}\Big(\max_{h \in \mathcal{H}}\lvert L_S(h) - L_{\mathcal{D}}(h)\rvert \ge \varepsilon\Big) \;\le\; 2\lvert\mathcal{H}\rvert e^{-2m\varepsilon^2}.$$

Hence $\mathcal{H}$ has the uniform convergence property with $m^{\mathrm{UC}}_{\mathcal{H}}(\varepsilon, \delta) \le \lceil \ln(2|\mathcal{H}|/\delta)/(2\varepsilon^2)\rceil$, and it is agnostic PAC learnable by ERM with

$$m_{\mathcal{H}}(\varepsilon, \delta) \;\le\; \left\lceil \frac{2\ln(2|\mathcal{H}|/\delta)}{\varepsilon^2} \right\rceil.$$

Equivalently, with probability at least $1 - \delta$, every $h \in \mathcal{H}$ has $\lvert L_S(h) - L_{\mathcal{D}}(h)\rvert < \sqrt{\ln(2|\mathcal{H}|/\delta)/(2m)}$, and the ERM's risk is within twice that of the best rule.

Proof. The event that some rule deviates by $\varepsilon$ or more is the union over $h \in \mathcal{H}$ of the events $\{\lvert L_S(h) - L_{\mathcal{D}}(h)\rvert \ge \varepsilon\}$. Each rule $h$ is fixed before the sample is drawn, so the indicators $\mathbf{1}\{h(x_i) \ne y_i\}$ are i.i.d. in $[0, 1]$ and Hoeffding's inequality bounds that event's probability by $2e^{-2m\varepsilon^2}$. The union bound adds $|\mathcal{H}|$ such terms. Setting $2|\mathcal{H}|e^{-2m\varepsilon^2} = \delta$ and solving for $m$ or for $\varepsilon$ gives the two other forms, and Proposition 1 of Empirical Risk Minimization at $\varepsilon/2$ gives the learning statement. $\square$

This is Corollary 4.6 of Shalev-Shwartz and Ben-David (2014) and Theorem 2.13 of Mohri, Rostamizadeh and Talwalkar (2018), whose bound, stated for $L_{\mathcal{D}} - L_S$ only but with the two-sided constant, is $L_{\mathcal{D}}(h) \le L_S(h) + \sqrt{(\ln|\mathcal{H}| + \ln(2/\delta))/(2m)}$ for every $h$. Using one tail of Hoeffding's inequality alone, the lower tail of $L_S(h)$, $P(L_S(h) - L_{\mathcal{D}}(h) \le -\varepsilon) \le e^{-2m\varepsilon^2}$, removes the 2: with probability at least $1 - \delta$, $L_{\mathcal{D}}(h) < L_S(h) + \sqrt{\ln(|\mathcal{H}|/\delta)/(2m)}$ for every $h$, the one-sided form used in The VC Dimension.

The step "each rule is fixed before the sample is drawn" is the whole point. Hoeffding's inequality may not be applied to the ERM itself, because $h_S$ depends on the sample and its training errors are not independent draws with mean $L_{\mathcal{D}}(h_S)$. The union bound pays for that dependence by covering every rule the learner might choose.

Why $1/\varepsilon^2$ and not $1/\varepsilon$. In the realizable case a bad rule is exposed by one mistake, an event whose probability grows linearly in its risk. In the agnostic case a rule with risk 0.0839 and one with risk 0.0839 + $\varepsilon$ both make mistakes, and telling them apart requires estimating a proportion to within $\varepsilon$, which takes on the order of $1/\varepsilon^2$ examples, as the standard error $\sqrt{p(1 - p)/m}$ of a proportion already shows. Hoeffding's inequality uses the largest variance a $[0, 1]$ variable can have, $1/4$, whatever the actual risk.

Diagnosed diabetes: the guarantee against what happens

With $|\mathcal{H}| = 201$ and $\delta = 0.05$, $\ln(2|\mathcal{H}|/\delta) = \ln 8{,}040 = 8.992$. Theorem 2 then promises:

  • every one of the 201 training errors within 0.05 of its risk, with probability at least 0.95, from $m = 1{,}799$ adults;
  • a learned threshold within 0.05 of the best one, from $m = 7{,}194$ adults, more than the population holds (sampling with replacement makes larger samples possible).

To compare with what happens, the script drew 30 samples at each of nine sizes (seeds 116,000,001 to 116,000,030; each seed's generator draws the sizes in increasing order). For each sample it computed the training error of all 201 thresholds, the largest deviation $\max_h\lvert L_S(h) - L_{\mathcal{D}}(h)\rvert$, and the excess risk $L_{\mathcal{D}}(h_S) - 0.0839$ of the ERM.

$m$ bound $\sqrt{\ln(2\lvert\mathcal{H}\rvert/\delta)/(2m)}$ largest deviation: median (IQR) largest of 30 ERM excess risk: median (IQR)
100 0.2120 0.0633 (0.0537 to 0.0835) 0.1261 0.0022 (0.0010 to 0.0081)
300 0.1224 0.0414 (0.0362 to 0.0558) 0.0768 0.0021 (0 to 0.0046)
1,000 0.0671 0.0235 (0.0205 to 0.0258) 0.0568 0.0010 (0 to 0.0021)
1,799 0.0500 0.0171 (0.0148 to 0.0210) 0.0277 0.0010 (0.0002 to 0.0021)
3,000 0.0387 0.0125 (0.0102 to 0.0157) 0.0196 0 (0 to 0.0010)
10,000 0.0212 0.0071 (0.0057 to 0.0087) 0.0118 0 (0 to 0.0010)

(The script also ran $m$ = 200, 500 and 5,000; the figure shows all nine.) In every row the bound is between 2.8 and 3.3 times the median largest deviation, and in no sample did the deviation reach the bound. The excess risk is smaller still: at $m = 1{,}799$, where the bound promises an excess of at most $2 \times 0.05 = 0.1$, the median excess is 0.0010, about five adults out of 5,210.

Three things make the bound loose here, and each is a choice made in the proof.

  • The union bound. The 201 deviations are strongly dependent: neighboring thresholds differ on the few adults at one HbA1c value, so their training errors move together. The union bound treats them as if each could fail separately.
  • Hoeffding's worst-case variance. Every threshold that does at least as well as predicting no diabetes for anyone (risk $806/5{,}210 = 0.1547$) has an indicator variance $p(1 - p)$ of at most 0.131, against the $1/4$ Hoeffding allows. Bernstein's inequality, proved in Concentration Inequalities: Hoeffding and Bernstein, uses the variance and would tighten the bound for small risks.
  • The factor 2 for the ERM. The reduction to the largest deviation bounds the estimation error by twice it. The ERM's excess risk was in fact a small fraction of the largest deviation.

Example (the bound and the learning curve agree on the rate). On the log scales of the figure the observed median falls in parallel with the bound. Both decline like $1/\sqrt{m}$: from $m = 100$ to $m = 10{,}000$, a factor of 100 in $m$, the bound falls by a factor of 10 and the median deviation by a factor of 8.9. The theory gets the rate right and the constant wrong by about three.

The discretization trick

Theorem 2 needs a finite class, while most models have real-valued parameters. Shalev-Shwartz and Ben-David (2014, Remark 4.1) point out that a computer stores each parameter in finitely many bits. A class described by $d$ parameters, each stored in $b$ bits, therefore has at most $2^{bd}$ distinct rules, whatever its mathematical description. Theorem 2 then gives

$$m_{\mathcal{H}}(\varepsilon, \delta) \;\le\; \left\lceil\frac{2\big(bd\ln 2 + \ln(2/\delta)\big)}{\varepsilon^2}\right\rceil.$$

Shalev-Shwartz and Ben-David write it with $b = 64$ as $(128d + 2\ln(2/\delta))/\varepsilon^2$, using $\ln 2 < 1$.

For the thresholds the comparison is direct. Stored as one 64-bit floating-point number, a threshold has at most $2^{64}$ values, $\ln 2^{64} = 44.36$, and uniform convergence at $\varepsilon = \delta = 0.05$ needs $m = 9{,}611$. Knowing that HbA1c is reported in tenths reduces the class to 201 rules and the requirement to 1,799, a factor of 5.3. An interval rule with two 64-bit endpoints would need 18,483.

The trick is crude in two ways. Its answer depends on how numbers are stored, which has nothing to do with learning. And it counts rules that no data could tell apart: on any sample of these HbA1c values, the $2^{64}$ floating-point thresholds produce at most 95 different labelings. Counting behaviors on a sample instead of rules is the idea of The VC Dimension, which removes the dependence on the representation.

Occam's razor: paying for description length

The finite-class bound gives every rule the same share $\delta/|\mathcal{H}|$ of the failure probability. Nothing forces equal shares. If rules are ranked before the data are seen, a rule we consider likely can be given a larger share and a smaller deviation bound, and an unlikely one a smaller share. The class may then be infinite, provided the shares add up to at most $\delta$. A natural ranking is by the length of a description of each rule.

Fix a description language: a map $\sigma$ from $\mathcal{H}$ to finite strings of bits, with $|h|$ the length of the string $\sigma(h)$. The language is prefix-free if for distinct rules $h \ne h'$, $\sigma(h)$ is not the beginning of $\sigma(h')$; a string counts as its own beginning, so in particular distinct rules have distinct descriptions, and the sum of $2^{-|h|}$ over rules is a sum over a prefix-free set of strings. A prefix-free code can be read without separators: a reader who knows the code knows where each description ends.

Lemma 2 (Kraft's inequality). For a prefix-free set of bit strings, $\sum_{\sigma} 2^{-|\sigma|} \le 1$.

Proof. Take first a finite prefix-free set, and let $L$ be its longest length. A string $\sigma$ of length $\ell \le L$ is the beginning of exactly $2^{L - \ell}$ strings of length $L$. Two different strings of the set cannot both begin the same string of length $L$: the shorter of them would then be the beginning of the longer one, which prefix-freeness forbids. So these sets of extensions are disjoint subsets of the $2^L$ strings of length $L$, and $\sum_\sigma 2^{L - |\sigma|} \le 2^L$. Dividing by $2^L$ gives the claim. An infinite prefix-free set has every finite subset prefix-free, so each partial sum of the series is at most 1, and so is the sum. $\square$

Shalev-Shwartz and Ben-David (2014, Lemma 7.6) prove the same inequality with a coin-tossing argument.

Theorem 3 (the Occam bound). Let $\mathcal{H}$ be a countable class with a prefix-free description language, and let the loss take values in $[0, 1]$. For every $\mathcal{D}$, every $m$ and every $\delta \in (0, 1)$, with probability at least $1 - \delta$ over $S \sim \mathcal{D}^m$,

$$L_{\mathcal{D}}(h) \;\le\; L_S(h) + \sqrt{\frac{|h|\ln 2 + \ln(2/\delta)}{2m}} \qquad\text{for every } h \in \mathcal{H}.$$

Proof. Give rule $h$ the failure probability $\delta_h = \delta\,2^{-|h|}$, and let $\varepsilon_h = \sqrt{\ln(2/\delta_h)/(2m)}$, so that $2e^{-2m\varepsilon_h^2} = \delta_h$. For each fixed $h$, Hoeffding's inequality gives $P(\lvert L_S(h) - L_{\mathcal{D}}(h)\rvert \ge \varepsilon_h) \le \delta_h$. The union bound over the countably many rules, valid for countable unions by the same argument as for finite ones (Laws of Large Numbers states it), gives probability at most $\sum_h \delta_h = \delta\sum_h 2^{-|h|} \le \delta$ that any rule deviates, by Lemma 2. Outside that event every rule has $L_{\mathcal{D}}(h) < L_S(h) + \varepsilon_h$, and $\ln(2/\delta_h) = |h|\ln 2 + \ln(2/\delta)$. $\square$

Shalev-Shwartz and Ben-David (2014, Theorem 7.7) state the bound with $|h|$ in place of $|h|\ln 2$, a slightly weaker form, since $\ln 2 < 1$. The bound suggests the minimum description length rule: choose the $h$ that minimizes the right-hand side, trading training error against description length. Read as a statement about explanations, it says that among rules that fit the data equally well, a shorter one carries a tighter guarantee, which Shalev-Shwartz and Ben-David (2014, §7.3.1) offer as one justification of Occam's razor.

An example on HbA1c. Describe a threshold, in tenths of a percent, by its signed distance $k$ from 6.5%, chosen before any data as the ADA's cut point. Map $k$ to a positive integer, $n = 2k$ for $k > 0$ and $n = 2|k| + 1$ for $k \le 0$, and write $n$ as its binary digits, preceded by one fewer zeros than there are digits. This is a code of the kind Elias (1975) introduced for the positive integers, usually called a gamma code; we use the layout just described, whatever name the paper gives it. The code is prefix-free because the leading zeros announce the length. The description length is $|h| = 2\lfloor\log_2 n\rfloor + 1$ bits. Over the thresholds 0.0% to 100.0% the script confirms that no codeword begins another and that the Kraft sum is 0.996.

threshold codeword bits Occam term at $m = 1{,}000$
6.5% 1 1 0.0468
6.7% 00100 5 0.0598
7.0% 0001010 7 0.0653
8.0% 000011110 9 0.0705
10.0% 0000001000110 13 0.0797

The finite class of 201 thresholds charges every rule the same, $\sqrt{\ln(2 \cdot 201/0.05)/2{,}000} = 0.0671$ at $m = 1{,}000$. The Occam bound charges less for thresholds near 6.5%, where clinical knowledge said the answer was likely to be, and more for distant ones. The two charges are equal at a description length of 7.65 bits, between the codes for 7.0% and 8.0%. The class is now infinite (every multiple of 0.1 has a code) and the guarantee still holds.

Example (a short description is not better in itself). A different prefix-free language could give 10.0% a one-bit code and 6.5% a long one, and the bound would then favor 10.0%. Shalev-Shwartz and Ben-David (2014, §7.3.1) resolve the apparent paradox: what matters is that the language is chosen before the data are seen. Choosing a language is a weak form of committing to rules in advance, and the bound rewards a commitment that the data then bear out. A language chosen after looking at the data would void the guarantee, exactly as a threshold chosen after looking at the data voids Hoeffding's inequality for that threshold.

Why the class matters: the no-free-lunch theorem

Every guarantee so far depended on a class fixed in advance: $\ln|\mathcal{H}|$ in Theorems 1 and 2, the description lengths in Theorem 3. Could a learner do without one, and succeed on every distribution by learning from the data alone? The no-free-lunch theorem says no. For every learner there is a distribution on which it fails, although another learner succeeds there.

Here is the idea in plain words. Take $2m$ points and let the labels be an arbitrary function on them. A sample of $m$ examples shows at most half of the points. On the points it has not seen, the sample says nothing about the labels, and averaged over all labelings any guess is wrong half the time.

Lemma 3 (a lower tail bound). Let $Z$ take values in $[0, 1]$ with $E[Z] = \mu$. For $a \in (0, 1)$, $P(Z > a) \ge (\mu - a)/(1 - a)$.

Proof. $E[Z] \le a\,P(Z \le a) + 1 \cdot P(Z > a) = a + (1 - a)P(Z > a)$, because $Z \le a$ on the first event and $Z \le 1$ on the second. Rearranging gives the claim. $\square$

Theorem 4 (no free lunch for learning). Let $A$ be any learning algorithm for binary classification with the 0-1 loss over a domain $\mathcal{X}$, and let $m$ be a sample size with $2m \le |\mathcal{X}|$. There is a distribution $\mathcal{D}$ on $\mathcal{X} \times \{0, 1\}$ such that (1) some function $f : \mathcal{X} \to \{0, 1\}$ has $L_{\mathcal{D}}(f) = 0$, and (2) $E_{S \sim \mathcal{D}^m}[L_{\mathcal{D}}(A(S))] \ge 1/4$, hence $P_{S \sim \mathcal{D}^m}(L_{\mathcal{D}}(A(S)) \ge 1/8) \ge 1/7$. For a randomized $A$, the expectation and the probability are also over its internal randomness.

Proof. Choose a set $C \subseteq \mathcal{X}$ of $2m$ points. There are $T = 2^{2m}$ functions $f_1, \ldots, f_T$ from $C$ to $\{0, 1\}$. Let $\mathcal{D}_i$ put probability $1/(2m)$ on each pair $(x, f_i(x))$, $x \in C$. Then $L_{\mathcal{D}_i}(f_i) = 0$, so (1) holds for each $\mathcal{D}_i$. We show that $\max_i E_{S \sim \mathcal{D}_i^m}[L_{\mathcal{D}_i}(A(S))] \ge 1/4$.

There are $k = (2m)^m$ sequences of $m$ points of $C$; call them $S_1, \ldots, S_k$, and write $S_j^i$ for $S_j$ labeled by $f_i$. Under $\mathcal{D}_i$ the training sample is $S_j^i$ for $j$ drawn uniformly, so $E_{S \sim \mathcal{D}_i^m}[L_{\mathcal{D}_i}(A(S))] = \frac{1}{k}\sum_{j=1}^k L_{\mathcal{D}_i}(A(S_j^i))$. A maximum is at least an average, and an average at least a minimum, so

$$\max_i \frac{1}{k}\sum_{j=1}^k L_{\mathcal{D}_i}(A(S_j^i)) \;\ge\; \frac{1}{T}\sum_{i=1}^T\frac{1}{k}\sum_{j=1}^k L_{\mathcal{D}_i}(A(S_j^i)) \;=\; \frac{1}{k}\sum_{j=1}^k\frac{1}{T}\sum_{i=1}^T L_{\mathcal{D}_i}(A(S_j^i)) \;\ge\; \min_j \frac{1}{T}\sum_{i=1}^T L_{\mathcal{D}_i}(A(S_j^i)).$$

Fix $j$, and let $v_1, \ldots, v_p$ be the points of $C$ that do not occur in $S_j$; since $S_j$ has $m$ entries, $p \ge m$. For any $h : C \to \{0, 1\}$,

$$L_{\mathcal{D}_i}(h) = \frac{1}{2m}\sum_{x \in C}\mathbf{1}\{h(x) \ne f_i(x)\} \;\ge\; \frac{1}{2m}\sum_{r=1}^p\mathbf{1}\{h(v_r) \ne f_i(v_r)\} \;\ge\; \frac{1}{2p}\sum_{r=1}^p\mathbf{1}\{h(v_r) \ne f_i(v_r)\},$$

using $2m \le 2p$ in the last step. Therefore

$$\frac{1}{T}\sum_{i=1}^T L_{\mathcal{D}_i}(A(S_j^i)) \;\ge\; \frac{1}{2p}\sum_{r=1}^p \frac{1}{T}\sum_{i=1}^T\mathbf{1}\{A(S_j^i)(v_r) \ne f_i(v_r)\} \;\ge\; \frac{1}{2}\min_{r}\frac{1}{T}\sum_{i=1}^T\mathbf{1}\{A(S_j^i)(v_r) \ne f_i(v_r)\}.$$

Fix $r$. Pair each function $f_i$ with the function $f_{i'}$ that agrees with it everywhere except at $v_r$. The point $v_r$ is not in $S_j$, so $S_j^i = S_j^{i'}$ and the algorithm returns the same rule on both. (This step takes the learner to be deterministic. If $A$ is randomized, the same pairing holds for the probability that its rule errs at $v_r$: the two probabilities sum to 1 for each pair, and the argument goes through with expectations over $A$'s randomness.) That rule's value at $v_r$ disagrees with exactly one of $f_i(v_r)$ and $f_{i'}(v_r)$, so each pair contributes exactly 1 to the sum, and the $T/2$ pairs give $\frac{1}{T}\sum_i \mathbf{1}\{A(S_j^i)(v_r) \ne f_i(v_r)\} = 1/2$. Chaining the inequalities, $\max_i E[L_{\mathcal{D}_i}(A(S))] \ge 1/4$. Take $\mathcal{D}$ to be a $\mathcal{D}_i$ attaining the maximum, extended to $\mathcal{X}$ by giving the other points probability 0, and $f$ any extension of $f_i$.

For the probability, apply Lemma 3 to $Z = L_{\mathcal{D}}(A(S)) \in [0, 1]$ with $\mu \ge 1/4$ and $a = 1/8$: $P(Z > 1/8) \ge (1/4 - 1/8)/(7/8) = 1/7$. $\square$

This is Theorem 5.1 of Shalev-Shwartz and Ben-David (2014), with the last step, which they leave as their Exercise 5.1, written out. The failing distribution is realizable, and ERM over the class $\{f\}$ returns $f$ itself and has risk 0 from any sample (Shalev-Shwartz and Ben-David, 2014, after Theorem 5.1). So the theorem does not say that the task is unlearnable. It says that no single learner succeeds on every task, which is the sense in which there is no universal learner.

Corollary 1. If $\mathcal{X}$ is infinite, the class of all functions from $\mathcal{X}$ to $\{0, 1\}$ is not PAC learnable.

Proof. Suppose some algorithm and sample complexity $m_{\mathcal{H}}$ existed. Take $\varepsilon < 1/8$ and $\delta < 1/7$, and $m = m_{\mathcal{H}}(\varepsilon, \delta)$. The domain has more than $2m$ points, and every function is in the class, so every distribution of Theorem 4 satisfies the realizability assumption. By Theorem 4 one of them makes the algorithm's risk at least $1/8 > \varepsilon$ with probability at least $1/7 > \delta$, contradicting the definition. $\square$

This is Corollary 5.2 of Shalev-Shwartz and Ben-David (2014).

The theorem on four points, by enumeration. With $m = 2$ and $C$ of four points there are 16 labelings and 16 training sequences. The script computes $E[L_{\mathcal{D}_i}(A(S))]$ exactly for each labeling and three learners. Each learner memorizes the labels it has seen. Off the sample, one predicts 0, one predicts the majority of the seen labels (counted with repeats, 0 on a tie), and one predicts the opposite of the first seen label.

learner average over the 16 labelings worst labeling
predict 0 off the sample 9/32 9/16 (all labels 1)
predict the majority seen 9/32 3/8
predict the opposite of the first label 9/32 9/16 (all labels 0)

Every learner has the same average, 9/32. The proof explains it: on unseen points every learner is wrong for exactly half of the labelings. The expected number of unseen points among four, after two draws, is $4(3/4)^2 = 9/4$, so the average error is $(9/4)/4 \times 1/2 = 9/32$. The worst labelings differ from learner to learner, and every worst case is at least $1/4$, as Theorem 4 requires.

Example (this is not the no-free-lunch theorem of optimization). The site's No Free Lunch Theorems treats a different result, that of Wolpert and Macready (1997). There the object is a search algorithm that evaluates a fitness function at points of a finite space, and the theorem says that averaged uniformly over all fitness functions, every search algorithm performs exactly as well as every other. It is a statement about an average over problems, and about optimization performance. Theorem 4 is about prediction on points not yet seen, and it is a worst-case statement: for each learner, one distribution on which it fails. Shalev-Shwartz and Ben-David (2014, §5.4) note that Wolpert and Macready's theorems for optimization are "rather different" from theirs. The closest relative of the optimization theorem in learning is Wolpert (1996), whose abstract states, loosely, that for any two learning algorithms there are as many targets on which one has the lower expected off-training-set error as on which the other has. The equal averages of 9/32 in the table are that averaging statement on four points; Theorem 4 turns the average into a worst case. All three results make the same point about prior knowledge: an algorithm is good only on a class of problems whose structure it exploits, and for a learner that structure is the hypothesis class.

What is proved, what is cited, what the experiment shows

Proved here. The inequality $1 - u \le e^{-u}$ (Lemma 1); PAC learnability of every finite class in the realizable case, with sample complexity at most $\lceil\ln(|\mathcal{H}|/\delta)/\varepsilon\rceil$ (Theorem 1); the one-threshold bound $\ln(1/\delta)/\varepsilon$ for the smallest consistent threshold (Proposition 1); uniform convergence and agnostic PAC learnability of every finite class with a $[0, 1]$ loss (Theorem 2); the discretization bound; Kraft's inequality (Lemma 2) and the Occam bound for countable classes (Theorem 3); the prefix-freeness of the gamma code used in the example; the lower tail bound (Lemma 3), the no-free-lunch theorem (Theorem 4) and the unlearnability of all functions on an infinite domain (Corollary 1). The exact distribution of the learned threshold's risk under the ADA labels is derived on the page.

Cited. Hoeffding's inequality, from Concentration Inequalities: Hoeffding and Bernstein (Theorem 2 there); the reduction of the estimation error to twice the largest deviation, from Empirical Risk Minimization (Proposition 1 there); the union bound, from Multiple Comparisons and the Bonferroni Correction. The definitions and the theorems in the form proved here follow Shalev-Shwartz and Ben-David (2014, Chapters 2 to 5 and §7.3) and Mohri, Rostamizadeh and Talwalkar (2018, Chapter 2). Valiant's (1984) model is described from its abstract and from Shalev-Shwartz and Ben-David's bibliographic remarks; the credit of the agnostic model to Haussler (1992) is theirs; Wolpert (1996) is reported at the level of its abstract. The ADA's criteria are those of the American Diabetes Association Professional Practice Committee (2025).

Computed. The population counts, risks and sample sizes are exact computations on the 5,210 adults. The realizable risk distribution is exact; the 30 seeded runs agree with it. The agnostic deviations and excess risks are 30 seeded samples at each size, reported as medians and interquartile ranges, and they describe this population, not the worst case the theorems address. The no-free-lunch table is an exact enumeration in fractions.

Worked problems

These problems were written for this article; they use the NHANES threshold class and a four-point domain. The script tools/experiments/statistics/pac-learning.py recomputes every number.

Problem 1 (a stricter guarantee). For the ADA labels, how many examples does Theorem 1 require for a risk of at most 0.02 with probability at least 0.99?

Solution. 496 examples.

With $|\mathcal{H}| = 201$, $\delta = 0.01$ and $\varepsilon = 0.02$, the bound is $m \ge \ln(201/0.01)/0.02 = \ln(20{,}100)/0.02 = 9.908/0.02 = 495.4$, so $m = 496$. The requirement is proportional to $1/\varepsilon$, so halving $\varepsilon$ doubles it, while cutting $\delta$ from 0.05 to 0.01 raised the logarithm only from $\ln 4{,}020 = 8.299$ to 9.908: confidence is cheap, accuracy is not. Proposition 1 would ask for $\ln(100)/0.02 = 230.3$, so 231 examples.

Problem 2 (the agnostic guarantee at 500 examples). With 500 adults and the diagnosed labels, what does Theorem 2 guarantee at $\delta = 0.05$?

Solution. With probability at least 0.95, every threshold's training error is within 0.0948 of its risk, and the learned threshold's risk is within 0.1897 of the best threshold's 0.0839.

The deviation bound is $\sqrt{\ln(8{,}040)/(2 \times 500)} = \sqrt{8.992/1{,}000} = 0.0948$, and the ERM guarantee doubles it. The guarantee is weak: a risk of up to $0.0839 + 0.1897 = 0.2735$ (from unrounded terms) is worse than predicting "no diabetes" for everyone, whose risk is $806/5{,}210 = 0.1547$. In the 30 samples of size 500 the largest deviation had median 0.0319, and the learned threshold's excess risk had median 0.0015.

Problem 3 (an Occam bound for one threshold). With the gamma-code language of the article and $m = 1{,}000$, the learned threshold is 6.7% and its training error is 0.085. What risk does Theorem 3 guarantee at $\delta = 0.05$?

Solution. At most 0.1448.

The distance from 6.5% is $k = 2$ tenths, so $n = 4$, written 100 in binary and coded 00100: $|h| = 5$ bits. The Occam term is $\sqrt{(5\ln 2 + \ln 40)/2{,}000} = \sqrt{(3.466 + 3.689)/2{,}000} = 0.0598$, and the bound is $0.085 + 0.0598 = 0.1448$. The guarantee holds even though 6.7% was chosen after seeing the data, because Theorem 3 holds for every rule of the class at once.

Problem 4 (the no-free-lunch theorem on four points). On four points with $m = 2$, the learner that predicts 0 off the sample faces the labeling with every label 1. Find its expected risk, and check it against Theorem 4.

Solution. $9/16$.

All labels are 1, so the learner errs exactly on the unseen points. Two draws from four points leave 2 points unseen with probability $4 \cdot 3/16 = 3/4$ (two different points) and 3 unseen with probability $4/16 = 1/4$ (the same point twice). The expected risk is $(3/4)(2/4) + (1/4)(3/4) = 6/16 + 3/16 = 9/16$. It exceeds $1/4$, as Theorem 4 requires of the worst labeling, and every sample gives a risk of at least $2/4 \ge 1/8$. Another learner, one that predicts 1 off the sample, has zero risk on this labeling, which is why the theorem speaks of a distribution chosen against a given learner.

Summary

Result Statement
PAC (realizable) $L_{\mathcal{D}}(A(S)) \le \varepsilon$ with probability $\ge 1 - \delta$ for $m \ge m_{\mathcal{H}}(\varepsilon, \delta)$, every realizable $\mathcal{D}$
Agnostic PAC $L_{\mathcal{D}}(A(S)) \le \min_{\mathcal{H}} L_{\mathcal{D}} + \varepsilon$ with probability $\ge 1 - \delta$, every $\mathcal{D}$
Finite class, realizable $P(L_{\mathcal{D}}(h_S) > \varepsilon) \le \lvert\mathcal{H}\rvert e^{-\varepsilon m}$; $m \ge \ln(\lvert\mathcal{H}\rvert/\delta)/\varepsilon$
Finite class, agnostic $P(\max_h\lvert L_S(h) - L_{\mathcal{D}}(h)\rvert \ge \varepsilon) \le 2\lvert\mathcal{H}\rvert e^{-2m\varepsilon^2}$; $m \ge 2\ln(2\lvert\mathcal{H}\rvert/\delta)/\varepsilon^2$ for ERM
Discretization $d$ parameters of $b$ bits: $\lvert\mathcal{H}\rvert \le 2^{bd}$
Kraft prefix-free: $\sum 2^{-\lvert h\rvert} \le 1$
Occam $L_{\mathcal{D}}(h) \le L_S(h) + \sqrt{(\lvert h\rvert\ln 2 + \ln(2/\delta))/(2m)}$ for all $h$
No free lunch every learner has a realizable $\mathcal{D}$ with $E[L] \ge 1/4$ when $2m \le \lvert\mathcal{X}\rvert$
NHANES thresholds realizable: bound 830, exact 229 at $\varepsilon = 0.01$; agnostic: bound about 3 times the observed largest deviation

What we have learned

A class of rules is PAC learnable when one sample size works for every distribution. For a finite class, ERM achieves it: with $\ln(|\mathcal{H}|/\delta)/\varepsilon$ examples when a perfect rule exists, because each bad rule is exposed by one mistake, and with $2\ln(2|\mathcal{H}|/\delta)/\varepsilon^2$ examples in general, because every training error must be close to its risk at once. On the 201 HbA1c thresholds the guarantees held with room to spare: the realizable bound asked for 830 examples where 229 sufficed, and the agnostic bound stood about three times above the largest deviation observed, falling at the same $1/\sqrt{m}$ rate. Bits of storage and bits of description extend the finite-class bound to real parameters and to countable classes, and the no-free-lunch theorem shows that some restriction of this kind is needed: without a class chosen in advance, every learner has a distribution on which it fails.

The thresholds on the real line form an infinite class, and floating-point storage made the count of rules depend on the computer rather than on the problem. What a sample can actually distinguish is a far smaller number: on $m$ points, at most $m + 1$ labelings. The VC Dimension makes that count the measure of a class's capacity and shows that it, not the number of rules, decides whether a class can be learned.

Every number in this article is computed by tools/experiments/statistics/pac-learning.py in the site's repository, which downloads the NHANES files from the CDC and checks their checksums (loader tools/experiments/statistics/sltdata.py). The figure is drawn by tools/figures/pac-learning.py from the script's results.

References