Worked VC Sample-Size Calculations

From Uniform Accuracy to a Sample-Size Calculation

A VC bound is useful in practice when it can answer a concrete question: how many independent observations are enough to make every classifier’s empirical risk close to its population risk, with a specified confidence? The answer is a sufficient sample size, not generally the smallest sample size the problem truly requires. Its value is that the calculation applies uniformly over the entire class rather than only to one classifier selected in advance.

Let $(X_i,Y_i)$, $i=1,\ldots,n$, be independent observations from a common distribution $P$, with binary labels and classifiers $h$ taking values in $\{0,1\}$. Write $R(h)=P(h(X)\ne Y)$ for population risk and $\widehat R_n(h)=n^{-1}\sum_{i=1}^n \mathbf 1\{h(X_i)\ne Y_i\}$ for empirical risk. We seek $P(\sup_{h\in\mathcal H}|R(h)-\widehat R_n(h)|>\varepsilon)\le\delta$, where $\varepsilon>0$ is the allowed error and $0<\delta<1$ is the allowed failure probability.

Assume the supremum is measurable; for example, this holds for a pointwise measurable class. The same statements can be formulated with outer probability when needed. Let $d$ be the VC dimension of the classifier class $\mathcal H$. On any fixed sample of labeled observations, the possible loss patterns have no greater cardinality than the prediction patterns: the labels are fixed, and each loss bit is the prediction bit with that label flipped when appropriate. Thus the loss class has VC dimension at most $d$.

Theorem: For a binary classifier class with VC dimension $d$, the standard VC deviation inequality gives $$ P\left(\sup_{h\in\mathcal H}|R(h)-\widehat R_n(h)|>\varepsilon\right) \le 8 S_{\mathcal H}(2n)\exp\left(-\frac{n\varepsilon^2}{32}\right), $$ where $S_{\mathcal H}(m)$ is the largest number of distinct prediction patterns the class can produce on $m$ points. Consequently, it is sufficient for uniform accuracy $\varepsilon$ with confidence at least $1-\delta$ that $$ \ln\left(\frac{8S_{\mathcal H}(2n)}{\delta}\right)\le\frac{n\varepsilon^2}{32}. $$

The first inequality is the VC deviation bound; the sample-size work is to control its growth factor and verify the resulting numerical inequality. For $1\le d\le 2n$, the Sauer bound gives $S_{\mathcal H}(2n)\le\sum_{j=0}^{d}\binom{2n}{j}\le(2en/d)^d$. Substitution yields an implicit but directly checkable condition:

\frac{n\varepsilon^2}{32} \ge \ln\left(\frac{8}{\delta}\right) +d\ln\left(\frac{2en}{d}\right), \qquad 1\le d\le 2n.

The condition is implicit because $n$ appears both outside and inside the logarithm. A proposed integer sample size can nevertheless be checked by evaluating both sides. Moreover, the left side minus the right side is increasing once $n>32d/\varepsilon^2$: its derivative, treating $n$ as a real variable, is $\varepsilon^2/32-d/n>0$. So after verifying the condition at a proposed $n$ in that range, every larger sample size also satisfies it.

Dimension-zero case: If $d=0$ and the class is nonempty, it produces only one pattern on every finite set, so $S_{\mathcal H}(2n)=1$. The sufficient condition is then $$ \ln\left(\frac{8}{\delta}\right)\le\frac{n\varepsilon^2}{32}, \qquad\text{or equivalently}\qquad n\ge\frac{32}{\varepsilon^2}\ln\left(\frac{8}{\delta}\right). $$ The Sauer expression involving division by $d$ is not used in this case.

Worked Calculations for Three Class Families

For the examples below, the domain is $\mathbb R$ for thresholds and intervals, and $\mathbb R^3$ for affine halfspaces. Thresholds on the line have VC dimension 1; intervals on the line have VC dimension 2; affine halfspaces in $\mathbb R^p$ have VC dimension $p+1$, hence dimension 4 when $p=3$. These dimensions determine which growth bound enters the sample-size calculation.

Worked Example: Thresholds With Ten-Percent Accuracy

Consider thresholds $h_t(x)=\mathbf 1\{x\le t\}$ on the real line. Ask for uniform risk error at most $\varepsilon=0.10$ with confidence at least $0.95$, so $\delta=0.05$. Here $d=1$, and the sufficient condition is $\frac{n}{3200}\ge\ln(160)+\ln(2en)$.

Take $n=57{,}000$. The left side is $57{,}000/3{,}200=17.8125$. On the right, $\ln(160)=5.075174$, and $\ln(2e\cdot57{,}000)=\ln(57{,}000)+\ln(2e)=10.950807+1.693147=12.643954$. Thus the right side is approximately $17.719128$, which is less than $17.8125$. Also, $57{,}000>32d/\varepsilon^2=3{,}200$, so the condition continues to hold for every larger $n$. Therefore 57,000 observations are sufficient under this bound.

This is a conservative guarantee from the stated inequality, not a claim that 57,000 is the exact minimum required by the threshold problem.

Worked Example: Intervals With Five-Percent Accuracy

Let the classifiers be indicators of intervals on the real line, and require $\varepsilon=0.05$ and confidence $0.99$, so $\delta=0.01$. Their VC dimension is $d=2$, giving $\frac{n}{12{,}800}\ge\ln(800)+2\ln(en)$.

Test $n=450{,}000$. The left side is $450{,}000/12{,}800=35.15625$. For the right side, $\ln(800)=6.684612$, while $\ln(e\cdot450{,}000)=1+\ln(450{,}000)=1+13.017003=14.017003$. The right side is therefore approximately $34.718617$ (using unrounded logarithms), which is smaller than $35.15625$. The monotonicity threshold is $32d/\varepsilon^2=25{,}600$, well below the proposed sample size. Hence $450{,}000$ is sufficient.

The logarithm is doubled because the Sauer term is $(en)^2$ for this dimension. Omitting that factor would understate the right side and could produce an invalid guarantee.

Worked Example: Affine Halfspaces in Three Dimensions

Consider affine halfspaces in $\mathbb R^3$, with VC dimension $d=4$. For $\varepsilon=0.05$ and confidence $0.95$, the condition becomes $\frac{n}{12{,}800}\ge\ln(160)+4\ln(en/2)$.

At $n=800{,}000$, the left side is $62.5$. On the right, $\ln(160)=5.075174$, and $\ln(e\cdot800{,}000/2)=1+\ln(400{,}000)=1+12.899220=13.899220$. Thus the right side is approximately $60.672053$ (using unrounded logarithms). Since $62.5>60.672053$, the sample size satisfies the sufficient condition. It also exceeds the monotonicity threshold $32d/\varepsilon^2=51{,}200$, so all larger sample sizes satisfy it as well.

The calculation uses the ambient dimension through $d=4$, not through the number of coefficients alone without an intercept. Affine halfspaces include an intercept; that is why their VC dimension in $\mathbb R^3$ is 4.

Why the Calculation Matters—and Where It Can Go Wrong

Uniform accuracy controls all classifiers in the class simultaneously. This is valuable when a classifier is selected using the same data on which its empirical risk is evaluated: a uniform deviation guarantee applies to the selected member as well as to every other member. The guarantee does not say that each classifier has exactly the same risk, nor does it establish that the best classifier in the class has low population risk. It bounds the discrepancy between empirical and population risk.

A common mistake is to read the displayed condition as an exact sample-size formula or to keep only the confidence term $\ln(8/\delta)$. The complexity term $d\ln(2en/d)$ is essential in the Sauer-based calculation. Another mistake is to apply the expression $(2en/d)^d$ at $d=0$; its division by zero makes that expression invalid there. The dimension-zero case must instead use $S_{\mathcal H}(2n)=1$ and its separate condition.

A practical calculation therefore has three checks: identify the correct VC dimension, choose an integer $n$ and evaluate both sides of the appropriate inequality, and confirm that the requested guarantee is uniform over the intended class. A larger class, tighter error tolerance, or higher confidence generally demands a larger sufficient sample size. The bound is informative as a transparent guarantee, while its conservatism should be kept distinct from the unknown or problem-specific minimum sample size.

Set the target.
Specify $\varepsilon$ and $\delta$ for the desired uniform-risk guarantee.

Identify the dimension.
Use the VC dimension of the classifier family; for dimension zero, use the separate growth calculation.

Check a candidate sample size.
Evaluate the Sauer-based inequality when $d\ge1$, or the dimension-zero inequality when $d=0$.

State the conclusion precisely.
Report the checked integer as sufficient under the bound, not as an exact minimum.

Key takeaway: For positive VC dimension, a convenient sufficient condition is $$ \frac{n\varepsilon^2}{32}\ge\ln\left(\frac{8}{\delta}\right)+d\ln\left(\frac{2en}{d}\right). $$ Check the inequality numerically at the proposed sample size, and handle $d=0$ separately.

Check Your Understanding

Use the stated VC deviation and growth bounds to answer these questions.

For thresholds with VC dimension 1, write the Sauer-based sample-size condition for general $\varepsilon$ and $\delta$.
Why does the sample-size expression involving $(2en/d)^d$ require a separate treatment when $d=0$?
For intervals on the real line, what VC dimension enters the bound, and what is the resulting logarithmic growth term?
In the affine halfspace example, why is the VC dimension 4 rather than 3?
What does a verified sufficient sample size guarantee, and what does it not claim about the exact minimum sample size?

Worked VC Sample-Size Calculations

What You'll Learn