VC Bounds for Agnostic ERM

From Uniform Deviation to Excess Risk

In binary classification, empirical risk minimization chooses a classifier with the smallest observed error on the training sample. The central question is how much worse its true error can be than the best true error available in the chosen hypothesis class. A VC uniform-deviation bound answers this by controlling, simultaneously over the whole class, the difference between empirical and population error.

This distinction matters when no classifier in the class predicts perfectly. The ERM procedure can select a classifier whose risk is close to the class optimum while that optimum itself is still positive. The bound below concerns the first gap: the excess risk over the best-in-class risk. It does not claim that the best classifier in the class has small risk.

We assume that an ERM exists and is measurable, and that the relevant suprema over the class are measurable. These conditions hold, for example, for a finite or countable class; standard measurable-separability conditions are another way to make the probability statements below well-defined. The observations are independent and identically distributed, and the loss is the zero-one loss shown in the definition.

The VC Uniform-Deviation Bound

For a class of binary-valued functions, its growth function counts how many distinct patterns it can produce on a fixed finite set. For classification, the relevant functions are the losses \((x,y)\mapsto\mathbf 1\{h(x)\ne y\}\). Write \(S_{\mathcal H}(m)\) for the largest number of distinct loss patterns this class can produce on any \(m\) points in \(\mathcal X\times\{0,1\}\). If \(\mathcal H\) has finite VC dimension \(d\), this loss class has VC dimension at most \(d\): on any fixed labelled points, each loss pattern is obtained from the classifier’s prediction pattern by flipping coordinates according to the labels. Consequently, it has at most as many patterns as the prediction class on the corresponding inputs.

Here is a proof with constants included. Introduce an independent sample \(Z'_1,\ldots,Z'_n\), and let \(\widehat R'_n(h)\) be its empirical risk. If the original sample has a classifier whose deviation exceeds \(\varepsilon\), then, conditional on that sample, the ghost-sample estimate for that classifier is within \(\varepsilon/2\) of its population risk with probability at least \(1-1/(n\varepsilon^2)\). Indeed, its variance is at most \(1/(4n)\), so Chebyshev’s inequality bounds the probability of a deviation of at least \(\varepsilon/2\) by \(1/(n\varepsilon^2)\le 1/2\). On the event that the ghost estimate is within \(\varepsilon/2\), the two empirical risks differ by more than \(\varepsilon/2\). Thus

To bound the probability on the right, condition on the \(n\) pairs \((Z_i,Z'_i)\) and independently swap the members of each pair with probability one half. This leaves their joint distribution unchanged. For any fixed loss pattern on the \(2n\) observations, the difference of empirical risks after the swaps has the form \(n^{-1}\sum_{i=1}^n \sigma_i c_i\), where the \(\sigma_i\) are independent random signs and \(c_i\in\{-1,0,1\}\). Since \(\sum_i c_i^2\le n\), Hoeffding’s inequality gives a two-sided tail bound of at most \(2\exp(-n\varepsilon^2/8)\) at threshold \(\varepsilon/2\). There are at most \(S_{\mathcal H}(2n)\) loss patterns on the pooled observations. A union bound therefore gives at most \(2S_{\mathcal H}(2n)\exp(-n\varepsilon^2/8)\) for the ghost-sample event. Combining this with the factor 2 above proves the displayed inequality (with the stated, slightly looser exponent). \(\square\)

The growth function can be bounded using Sauer’s lemma. When the VC dimension \(d\ge1\) and \(2n\ge d\),

The first inequality is the VC growth-function bound; the second is the standard binomial-sum estimate. Together, these inequalities turn a bound in terms of the number of patterns into one in terms of the VC dimension.

Why the Excess-Risk Bound Has a Factor of Two

Define the uniform deviation \(D_n=\sup_{h\in\mathcal H}|\widehat R_n(h)-R(h)|\). ERM compares classifiers using empirical risks, but the target is population risk. The discrepancy between those two criteria can enter once for the classifier ERM selected and once for the best-in-class benchmark.

To prove it, fix any \(h\in\mathcal H\). Add and subtract the empirical risks:

The middle term is nonpositive because \(\hat h\) minimizes empirical risk. Taking the infimum over \(h\in\mathcal H\) gives the result. In detail, since \(R(\hat h)\le R(h)+2D_n\) for every \(h\), it follows that \(R(\hat h)\le\inf_h R(h)+2D_n\). \(\square\)

Combining this inequality with the VC deviation bound gives a direct high-probability result. For \(d\ge1\), \(n\ge d\), and \(0<\delta<1\), choose

This choice satisfies \(n\varepsilon_{n,\delta}^2\ge2\). Applying Sauer’s lemma in the VC bound makes its right-hand side at most \(\delta\): the exponential factor cancels \((2en/d)^d\) and leaves \(\delta/4\), multiplied by 4. The ERM inequality then yields

This is a finite-sample upper bound; its right-hand side can exceed 1, in which case it is valid but uninformative because a binary classification risk is at most 1. For fixed \(d\) and \(\delta\), it gives an excess-risk rate of order \(\sqrt{d\log(n/d)/n}\) with this growth-function argument. The displayed rate includes a logarithmic factor and is not a claim that this particular bound is sharp in every setting.

Reading the Result Correctly

The excess risk \(R(\hat h)-R^*_{\mathcal H}\) measures the cost of using a data-selected classifier rather than the best classifier in the specified class. It is nonnegative because \(R^*_{\mathcal H}\) is an infimum. The VC argument controls this cost through estimation error: if empirical risks are uniformly close to population risks, empirical minimization cannot select a classifier whose population risk is much worse than the class benchmark.

A common mistake is to read the bound as saying that ERM’s risk is small. The theorem instead says that ERM’s risk is close to \(R^*_{\mathcal H}\). If every classifier in the class performs poorly, then \(R^*_{\mathcal H}\) can itself be large, and the excess-risk bound does not remove that baseline risk. Another mistake is to use a pointwise deviation bound for a single fixed classifier: ERM is selected after looking at the data, so the deviation control must hold uniformly over the class.

The practical message is to keep the two quantities separate: \(R^*_{\mathcal H}\) is the best achievable risk within the class, while \(R(\hat h)-R^*_{\mathcal H}\) is the sample-dependent excess risk. VC dimension controls the latter through the number of label patterns the class can realize, not the absolute predictive quality of the class.