Zero-One Risk Bounds For Finite Classifiers

Why Realizability Changes the Guarantee

A classifier chosen to make few errors on a training sample need not make few errors on new observations. For a finite class, probability bounds quantify this gap. Under zero-one loss, a crucial distinction is whether the class contains a classifier with no population errors. When it does, an empirical risk minimizer that makes no training errors has a faster guarantee than the general guarantee available without that assumption.

The faster conclusion is not a property of zero-one loss alone: it depends on realizability. Without realizability, a classifier may make unavoidable errors even with unlimited data, and finite-class selection generally has a slower, square-root sample-size rate unless additional structure is available.

Setup and Definitions

Let \((X,Y)\) have a fixed distribution \(P\), where \(Y\in\{0,1\}\), and let \((X_1,Y_1),\ldots,(X_n,Y_n)\) be independent observations with this distribution. Let \(\mathcal H\) be a nonempty finite class of measurable classifiers \(h:\mathcal X\to\{0,1\}\), and write \(M=|\mathcal H|\). The zero-one loss is one for an incorrect prediction and zero otherwise.

The minimum population risk \(R^*_{\mathcal H}=\min_{h\in\mathcal H}R(h)\) is the best risk available within the class. It need not be zero. In the agnostic setting, a useful guarantee compares the selected classifier with this in-class oracle, rather than with an unattainable error-free classifier.

The Realizable Case: A \(1/n\)-Scale Bound

When some candidate has zero population risk, it makes no errors on any individual drawn from \(P\), with probability one. Thus the minimum empirical risk is zero for every sample, except on a probability-zero event. Every empirical risk minimizer is then consistent: it also has zero training errors. The question is how large its population risk could still be.

Proof. Choose \(h_0\in\mathcal H\) with \(R(h_0)=0\). Each training observation is classified correctly by \(h_0\) with probability one, so \(\widehat R_n(h_0)=0\) with probability one. Since empirical risks are nonnegative, every empirical risk minimizer has empirical risk zero with probability one.

Fix \(\varepsilon>0\). If \(R(\hat h)>\varepsilon\), then some \(h\in\mathcal H\) has \(R(h)>\varepsilon\) and makes no errors on the sample. For any fixed \(h\), independence gives $$ P\{\widehat R_n(h)=0\}=(1-R(h))^n\le e^{-nR(h)}. $$ For every \(h\) with \(R(h)>\varepsilon\), this probability is at most \(e^{-n\varepsilon}\). Taking a union bound over at most \(M\) classifiers yields $$ P\{R(\hat h)>\varepsilon\}\le M e^{-n\varepsilon}. $$ Set \(\varepsilon=\log(M/\delta)/n\). Then \(M e^{-n\varepsilon}=\delta\), proving the claim. \(\square\)

The Agnostic Case: A Slow-Rate Oracle Bound

Without realizability, there may be no zero-risk classifier, and the empirical minimizer need not be consistent. A general finite-class guarantee instead controls how far each candidate's empirical risk can deviate from its population risk. It then compares the selected classifier with the best population-risk candidate.

Proof. For each fixed \(h\), the \(n\) loss values \(\mathbf 1\{h(X_i)\ne Y_i\}\) are independent, lie in \([0,1]\), and have mean \(R(h)\). Hoeffding's inequality therefore gives $$ P\{|\widehat R_n(h)-R(h)|>t\}\le 2e^{-2nt^2}. $$ A union bound over \(\mathcal H\) shows that the probability of any candidate violating this deviation bound is at most \(2M e^{-2nt^2}=\delta\). On the complementary event, \(|\widehat R_n(h)-R(h)|\le t\) for every \(h\in\mathcal H\).

Choose \(h^*\in\mathcal H\) minimizing \(R(h)\), which exists because the class is finite. On that same event, use the deviation inequality first for \(\hat h\), then empirical minimization, and then for \(h^*\): $$ R(\hat h) \le \widehat R_n(\hat h)+t \le \widehat R_n(h^*)+t \le R(h^*)+2t. $$ This is the stated bound. \(\square\)

Interpreting the Difference

The realizable bound decreases on the scale \(\log(M/\delta)/n\), whereas the general agnostic excess-risk bound decreases on the scale \(\sqrt{\log(M/\delta)/n}\). The difference arises in the proof: in the realizable case, a classifier with risk \(r\) must make zero errors for the empirical minimizer to select it, an event whose probability is at most \(e^{-nr}\). In the agnostic case, the argument must control deviations of empirical risks around their means, leading to a square-root term.

These guarantees are uniform over the finite class and can be used without knowing the particular distribution \(P\), provided the stated assumptions hold. The bounds may be conservative: they depend on the size of the whole class and do not exploit additional structure that might make selection easier. In particular, do not read the agnostic result as saying that every problem needs a square-root rate; stronger rates require further conditions.

Common Mistake

A common error is to use the realizable bound just because an empirical minimizer makes no training errors. That observation only says the selected classifier fits this sample. It does not imply that any classifier in the class has zero population risk. Without that population-level assumption, the union-bound argument for the faster rate does not apply. Use the agnostic oracle bound unless realizability is justified. Conversely, the realizable theorem guarantees small risk for a consistent empirical minimizer; it does not say every classifier in the class is accurate.