Fast Rates for Finite Predictor Classes

Why Finite Classes Can Learn Faster Under Low Noise

For a finite predictor class, a basic uniform-convergence argument gives an excess-risk rate of order \(\sqrt{\log M/n}\), where \(M\) is the number of predictors. That rate treats every empirical comparison as if its variability remained large even when two predictors have nearly the same risk. Under a low-noise condition, this is unnecessarily pessimistic: predictors with small excess risk disagree with the optimal classifier on relatively little probability mass, so their empirical risk differences fluctuate less.

This tutorial turns that idea into a high-probability guarantee for empirical risk minimization (ERM). The central steps are to bound the variance of each excess-loss difference by a power of its mean, then apply Bernstein’s inequality and a union bound over the finite class. Under Tsybakov’s margin condition, the resulting rate is faster than the general square-root rate when the margin exponent is positive.

Setup and the Tsybakov Margin Condition

Let \((X,Y)\) be a random pair with \(Y\in\{-1,+1\}\), and let \((X_1,Y_1),\ldots,(X_n,Y_n)\) be independent observations with the same distribution. A classifier \(h\) maps the feature space to \(\{-1,+1\}\). Its zero-one risk is \(R(h)=P(h(X)\ne Y)\), and its empirical risk is \(R_n(h)=n^{-1}\sum_{i=1}^n\mathbf{1}\{h(X_i)\ne Y_i\}\). Write \(\eta(x)=P(Y=+1\mid X=x)\) and \(\Delta(x)=|2\eta(x)-1|\). A Bayes classifier \(h_B\) predicts the more probable label given \(X\); ties may be resolved by either label.

For a classifier \(h\), define its Bayes excess risk \(r(h)=R(h)-R(h_B)\). Conditioning on \(X\) gives the useful identity \(r(h)=E[\Delta(X)\mathbf{1}\{h(X)\ne h_B(X)\}]\). It says that a disagreement in a region with a large conditional class-probability gap costs more risk than one near the boundary.

From Margin Mass to a Bernstein Condition

For a fixed classifier \(h\), let \(Z_h=\mathbf{1}\{h(X)\ne Y\}-\mathbf{1}\{h_B(X)\ne Y\}\) be its single-observation loss difference from the Bayes classifier. It takes values in \(\{-1,0,+1\}\). Its expectation is \(r(h)\), and its square is one exactly when \(h(X)\ne h_B(X)\). Consequently, \(\operatorname{Var}(Z_h)\le E[Z_h^2]=P(h(X)\ne h_B(X))\). The margin condition controls this last probability as follows.

To verify the bound, write \(r=r(h)>0\). For every \(t>0\), the margin condition and the excess-risk identity give \[ P(h(X)\ne h_B(X)) \le Ct^q+\frac{r}{t}. \] Taking \(t=(r/C)^{1/(q+1)}\) makes both terms equal to \(C^{1/(q+1)}r^{q/(q+1)}\). Thus disagreement probability is at most \(2C^{1/(q+1)}r^\beta\), which also bounds the variance. If \(r=0\), then \(\Delta(X)\mathbf{1}\{h(X)\ne h_B(X)\}=0\) almost surely. The margin condition with \(q>0\) implies \(P(\Delta(X)=0)=0\), by taking \(t\) down to zero, so disagreement has probability zero and the variance bound holds in this case too. \(\square\)

More generally, the finite-class argument below only needs the Bernstein condition \(\operatorname{Var}(Z_h)\le B r(h)^\beta\) for every \(h\) in the class, with \(0\le\beta\le1\). The margin calculation is one way to obtain it; the condition itself is what drives the concentration step.

A High-Probability Bound for Finite-Class ERM

Let \(\mathcal{H}\) be a nonempty finite class of size \(M\), containing a Bayes classifier, and define \(\hat h\) to minimize \(R_n(h)\) over \(h\in\mathcal{H}\). If there are ties, choose any empirical minimizer. For each \(h\), write \(r(h)=R(h)-R(h_B)\) and let \(Z_h\) be its loss difference from \(h_B\) as above. Assume \(\operatorname{Var}(Z_h)\le B r(h)^\beta\) for all \(h\in\mathcal{H}\), where \(B>0\) and \(0\le\beta\le1\).

The bound is a high-probability guarantee for the excess risk of ERM. Its proof compares each class member to the Bayes classifier, controls the probability that a worse classifier achieves no greater empirical risk, and then takes a union bound.

All concentration here is for bounded zero-one loss differences, and the only class-size cost is the union bound’s \(\log M\). No independence among the different classifiers’ empirical risks is needed.

Interpretation and a Common Pitfall

Under the margin condition, \(\beta=q/(q+1)\), so the sample-size exponent in the finite-class rate is \((q+1)/(q+2)\). When \(q\) is close to zero, this approaches the general square-root rate. As \(q\) grows, the exponent approaches one, giving a rate closer to \(\log(M/\delta)/n\). The logarithm records the cost of searching among \(M\) candidates; the noise condition controls how effectively their empirical risks can be distinguished.

Common mistake: applying this conclusion to any finite class without checking the comparator. The proof uses that the Bayes classifier belongs to \(\mathcal{H}\), so ERM can be compared directly with it and its excess-loss variance is controlled by the Bayes margin condition. If the Bayes classifier is outside the class, the best-in-class predictor may disagree with it even when the class predictor is optimal within \(\mathcal{H}\). Tsybakov’s condition alone does not then establish the same Bernstein bound in terms of excess risk over the best-in-class predictor. The correction is to verify a Bernstein condition for that comparator, or to use an analysis that explicitly accounts for approximation error; do not silently substitute the best-in-class risk into the theorem.