Sample Complexity for VC Classes

From a Deviation Bound to a Sample Size

A uniform-convergence statement is useful when it answers a practical question: how large must the sample be to make every hypothesis' empirical performance close to its population performance, with a specified confidence? For a VC class, the growth function gives a direct route from a probability bound to such a sample-size guarantee. The resulting classical formula is explicit, but it contains an extra logarithmic dependence on accuracy. Entropy-based arguments sharpen that rate.

Definition: Let $\mathcal A$ be a class of measurable subsets of a sample space, and let $X_1,\ldots,X_n$ be independent observations with common distribution $P$. Write $P_n(A)=n^{-1}\sum_{i=1}^n \mathbf 1\{X_i\in A\}$. The class has VC dimension $d$ if $d$ is the largest size of a finite set on which $\mathcal A$ realizes every possible subset. Its growth function $\Pi_{\mathcal A}(m)$ is the largest number of distinct subsets of $m$ points that members of $\mathcal A$ can realize.

We assume $d\geq 1$, and that the supremum in the deviation event below is measurable (or that the probability is interpreted as outer probability). For $0<\varepsilon\leq 1$, a uniform-convergence guarantee at accuracy $\varepsilon$ and confidence $1-\delta$ means

P\left(\sup_{A\in\mathcal A}|P_n(A)-P(A)|>\varepsilon\right)\leq\delta.

The growth-function inequality established in uniform convergence from growth functions states that, for $n\geq 1$,

P\left(\sup_{A\in\mathcal A}|P_n(A)-P(A)|>\varepsilon\right) \leq 8\Pi_{\mathcal A}(2n)\exp\left(-\frac{n\varepsilon^2}{32}\right).

The Sauer–Shelah lemma gives $\Pi_{\mathcal A}(m)\leq (em/d)^d$ when $m\geq d$. In particular, for $n\geq d$, these two inequalities imply

P\left(\sup_{A\in\mathcal A}|P_n(A)-P(A)|>\varepsilon\right) \leq 8\left(\frac{2en}{d}\right)^d \exp\left(-\frac{n\varepsilon^2}{32}\right).

An Explicit Classical Sample-Size Bound

Because $n$ appears both in a power and in the exponential, the last inequality is not solved for $n$ simply by taking one logarithm. The following slightly conservative formula gives a convenient explicit solution. All logarithms in this tutorial are natural logarithms.

Theorem: Let $\mathcal A$ have VC dimension $d\geq1$, and suppose $0<\varepsilon\leq1$ and $0<\delta<1$. Under the measurability condition above, it is sufficient to take $$ n\geq \frac{128}{\varepsilon^2}\left[d\log\left(\frac{128e}{\varepsilon^2}\right)+\log\left(\frac{8}{\delta}\right)\right] $$ to ensure $P(\sup_{A\in\mathcal A}|P_n(A)-P(A)|>\varepsilon)\leq\delta$. The smallest integer meeting this displayed sufficient condition is its right-hand side rounded up.

Proof. Set $L=\log(128e/\varepsilon^2)$, $q=\log(8/\delta)$, and $N=128(dL+q)/\varepsilon^2$. We first check the growth-function bound at every real $n\geq N$; such $n$ also satisfies $n\geq d$. Indeed, $L>1$ and $N\geq128dL/\varepsilon^2>d$.

It suffices for the probability bound to have

\frac{n\varepsilon^2}{32}\geq d\log\left(\frac{2en}{d}\right)+q.

At $n=N$, the logarithm on the right is

\log\left(\frac{2eN}{d}\right) =\log\left(\frac{256e}{\varepsilon^2}\left(L+\frac{q}{d}\right)\right) =L+\log 2+\log\left(L+\frac{q}{d}\right) \leq 2L+\log 2+\frac{q}{d},

where $\log y\leq y$ for $y>0$ was used in the final inequality. Consequently,

d\log\left(\frac{2eN}{d}\right)+q \leq 2dL+d\log 2+2q \leq 4dL+4q =\frac{N\varepsilon^2}{32}.

The second inequality holds because $2dL-d\log 2+2q>0$. To extend the result from $N$ to all $n\geq N$, define $g(n)=n\varepsilon^2/32-d\log(2en/d)$. Its derivative is $g'(n)=\varepsilon^2/32-d/n$, which is positive for $n\geq N$, since $N\varepsilon^2/32=4(dL+q)>d$. Thus $g(n)+(-q)\geq0$ for all $n\geq N$. Substitution into the probability bound gives at most $8\exp(-q)=\delta$. $\square$

Worked Example: A Numerical VC Guarantee

Suppose the VC dimension is $d=10$, the desired uniform accuracy is $\varepsilon=0.1$, and the failure probability is at most $\delta=0.05$. The sufficient real-valued sample size is

$128/(0.1)^2=12{,}800$, $\log(128e/(0.1)^2)=\log(12800e)\approx10.45720045$, and $\log(8/0.05)=\log(160)\approx5.07517382$. Therefore the term in square brackets is $10(10.45720045)+5.07517382\approx109.6471783$.

Multiplying gives $12{,}800(109.6471783)\approx1{,}403{,}483.9$. Rounding up, the displayed sufficient condition is met by $n=1{,}403{,}484$. This is a conservative guarantee from the stated inequality, not a claim that this many observations are necessary.

The formula separates the main sources of difficulty: larger dimension increases the required sample size, smaller accuracy makes it grow as $\varepsilon^{-2}$ times a logarithmic factor, and higher confidence contributes through $\log(1/\delta)$. These are sufficient bounds; a guarantee is not generally an exact minimum sample size.

Using Uniform Convergence for Risk

A common application is a class of binary classifiers, represented by measurable sets $A$, with zero-one loss $\mathbf 1\{x\in A\}$ for a fixed labeling convention. Its empirical and population risks are $P_n(A)$ and $P(A)$. If a uniform deviation bound holds with accuracy $\varepsilon$, it also controls the gap between empirical and population risk for any data-dependent choice from the class.

Worked Example: Converting Risk Accuracy to Uniform Accuracy

Suppose an empirical risk minimizer $\hat A$ is chosen from $\mathcal A$, and suppose a population risk minimizer $A^*$ exists in $\mathcal A$. On the event that $\sup_{A\in\mathcal A}|P_n(A)-P(A)|\leq\varepsilon$, empirical minimality gives $P_n(\hat A)\leq P_n(A^*)$. Adding and subtracting the empirical risks yields

$P(\hat A)-P(A^*)=[P(\hat A)-P_n(\hat A)]+[P_n(\hat A)-P_n(A^*)]+[P_n(A^*)-P(A^*)]\leq\varepsilon+0+\varepsilon=2\varepsilon.$

Thus to guarantee excess risk at most $\rho$, it is sufficient to use the uniform-deviation formula with $\varepsilon=\rho/2$ (for $0<\rho\leq2$). The resulting classical sufficient condition is

n\geq \frac{512}{\rho^2} \left[d\log\left(\frac{512e}{\rho^2}\right)+\log\left(\frac{8}{\delta}\right)\right].

The factor $512$ includes the substitution $(\rho/2)^{-2}=4/\rho^2$. The confidence remains $1-\delta$, because the risk comparison holds on the same uniform-deviation event.

Classical Growth Rates and Sharper Entropy Rates

Ignoring constants, the explicit growth-function calculation has the form

n=O\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon^2}\right).

The $\log(1/\varepsilon)$ factor arises when the Sauer–Shelah bound is evaluated at $2n$, after which the sample size must control a logarithm containing $n$. This is the classical growth-function rate. It is valid and often convenient, but its accuracy dependence is not the sharpest general VC rate.

Entropy-based comparison: For a measurable class of sets with finite VC dimension $d\geq1$, the standard VC entropy uniform-deviation theorem gives universal constants $C,c>0$ such that a sufficient sample size has order $$ n\geq \frac{C}{\varepsilon^2}\left(d+\log\left(\frac{c}{\delta}\right)\right). $$ Equivalently, at fixed confidence, the rate is $O(d/\varepsilon^2)$, without the additional $\log(1/\varepsilon)$ factor. The constants in this order statement are universal but are not the explicit constants of the growth-function formula.

This sharper rate comes from controlling the class at multiple scales through metric entropy, rather than bounding all patterns on a single sample of size $2n$. The entropy argument and its technical conditions are developed in the later study of covering numbers and uniform deviations; the comparison here is about the consequence for sample size. The two displayed rates should not be conflated: the explicit numerical bound proved above is the classical one, whereas the entropy rate asserts a sharper order with unspecified constants.

Worked Example: Reading the Two Rates at Fixed Confidence

Take $d=10$ and $\delta=0.05$. As $\varepsilon$ decreases, the classical guarantee has order $\varepsilon^{-2}[10\log(1/\varepsilon)+\log(20)]$, up to constants. The entropy-based guarantee has order $\varepsilon^{-2}[10+\log(1/0.05)]$, again up to universal constants.

For example, changing accuracy from $0.1$ to $0.05$ multiplies the $\varepsilon^{-2}$ factor by $4$ in both expressions. In the classical expression, the dimension term also changes from $10\log(10)$ to $10\log(20)$; in the entropy expression, the bracket $10+\log(20)$ does not depend on accuracy. This comparison identifies the logarithmic improvement without pretending that the two formulas have matching constants.

Common Pitfalls

Calling a sufficient bound the exact minimum. A theorem that guarantees convergence above a threshold does not show that smaller samples fail. Lower bounds are needed to establish necessity.
Dropping the logarithm's argument or changing its base silently. The formula uses natural logarithms and $\log(128e/\varepsilon^2)$, not $\log(128e/\varepsilon)$. Changing logarithm base changes constants.
Forgetting that accuracy conventions can differ. A bound on uniform deviation by $\varepsilon$ gives an excess-risk bound of $2\varepsilon$ for empirical risk minimization. To target excess risk $\rho$, substitute $\varepsilon=\rho/2$.
Confusing the two rates. The explicit growth-function inequality yields the extra $\log(1/\varepsilon)$ factor. The sharper order comes from entropy methods and does not follow merely by algebraically rearranging that inequality.

Key takeaway: The growth-function inequality gives a concrete, conservative VC sample-size bound of order $\varepsilon^{-2}[d\log(1/\varepsilon)+\log(1/\delta)]$. Entropy-based uniform-deviation results improve the order to $\varepsilon^{-2}[d+\log(1/\delta)]$, with different constants and proof machinery.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

In the classical sufficient sample-size formula, which terms depend on VC dimension, accuracy, and confidence?
Why does the growth-function calculation produce a logarithmic factor involving accuracy?
If an empirical risk minimizer is to have excess risk at most $\rho$, what uniform-deviation accuracy should be used?
Does satisfying a sufficient sample-size bound prove that every smaller sample size fails? Explain.
State the difference in accuracy dependence between the classical growth-function rate and the sharper entropy-based rate.