VC-Dimension Rates Under Low Noise

From Low Noise to Faster Learning

A classifier can make errors for two rather different reasons: the data may be inherently ambiguous, or the learning procedure may choose the wrong decision on covariate values where the Bayes decision is actually clear. The classification margin distinguishes these cases. If little probability mass lies near the decision boundary, disagreement with the Bayes classifier is comparatively costly in risk. That relationship can make empirical risk minimization converge faster than the usual square-root rate.

This tutorial derives the relevant rate for a class of binary classifiers with finite VC dimension. The argument has two ingredients: a noise condition converts excess risk into a bound on the variance of a loss difference, and a relative VC inequality controls empirical deviations in terms of that variance.

Setup and the Tsybakov Condition

Let $(X,Y)$ be a random pair with $Y\in\{0,1\}$, and let $(X_i,Y_i)$, $i=1,\ldots,n$, be independent observations with the same distribution. Write $\eta(x)=P(Y=1\mid X=x)$ for a version of the conditional probability, and define the classification margin by $\Delta(x)=|2\eta(x)-1|$. A classifier $h$ is a measurable function from the covariate space into $\{0,1\}$. Its risk is $\mathcal R(h)=P(h(X)\ne Y)$. A Bayes classifier $h^*$ chooses the more probable label given $X$, with either label allowed when $\eta(X)=1/2$.

Definition: The distribution satisfies the Tsybakov margin condition with exponent $\alpha\ge 0$ and constant $C\ge 1$ if, for every $0<t\le 1$, $$ P\bigl(\Delta(X)\le t\bigr)\le C t^\alpha. $$ The excess risk of $h$ is $\mathcal E(h)=\mathcal R(h)-\mathcal R(h^*)$.

The condition limits the probability mass close to the decision boundary; it does not require every covariate value to have a large margin. Larger $\alpha$ means a stronger restriction on the mass of small margins. The case $\alpha=0$ gives no useful decay with $t$, and therefore does not imply a faster-than-square-root rate.

Worked Example: Reading a Margin Condition

Suppose a distribution obeys $P(\Delta(X)\le t)\le 3t^2$ for all $0<t\le1$. Here the margin exponent is $\alpha=2$, and $C=3$. At $t=0.1$, the probability of margin at most $0.1$ is bounded by $3(0.1)^2=0.03$. At $t=0.5$, the corresponding bound is $3(0.5)^2=0.75$.

The condition is an upper bound, not an assertion that either probability equals its bound. In particular, the first calculation says that at most three percent of the covariate distribution has margin at most $0.1$; it does not say that the remaining covariates are noise-free.

Excess Risk Controls Disagreement

For binary classification, the excess risk has a direct expression in terms of the margin. Conditional on $X=x$, choosing the less probable label instead of the Bayes label increases error probability by $|2\eta(x)-1|$. Integrating over $X$ gives

\mathcal E(h)=E\!\left[\Delta(X)\mathbf 1\{h(X)\ne h^*(X)\}\right].

This identity remains valid when ties occur: if $\Delta(X)=0$, choosing either label has zero excess conditional risk. The margin condition now bounds the probability that a classifier disagrees with $h^*$.

Result: If the Tsybakov condition holds with $\alpha\ge0$ and $C\ge1$, then, for every classifier $h$, $$ P\bigl(h(X)\ne h^*(X)\bigr) \le 2C^{1/(\alpha+1)}\mathcal E(h)^{\alpha/(\alpha+1)}. $$

To prove the result, fix $0<t\le1$ and split the disagreement event according to whether $\Delta(X)\le t$. The first part has probability at most $Ct^\alpha$. On the second part, the excess-risk identity implies $$ \mathcal E(h)\ge t\,P\bigl(h(X)\ne h^*(X),\ \Delta(X)>t\bigr). $$ Therefore, $$ P\bigl(h(X)\ne h^*(X)\bigr) \le Ct^\alpha+\frac{\mathcal E(h)}{t}. $$ If $\mathcal E(h)>0$, choose $t=(\mathcal E(h)/C)^{1/(\alpha+1)}$. Since $\mathcal E(h)\le1$ and $C\ge1$, this choice lies in $(0,1]$. Both terms then equal $C^{1/(\alpha+1)}\mathcal E(h)^{\alpha/(\alpha+1)}$, proving the bound. If $\mathcal E(h)=0$, the same split inequality holds for every $t>0$; letting $t$ decrease to zero shows that the disagreement probability is zero when $\alpha>0$. When $\alpha=0$, the displayed result follows directly from the probability being at most one. $\square$

The Bernstein Exponent

For a classifier $h$, define the loss difference $Z_h=\mathbf 1\{h(X)\ne Y\}-\mathbf 1\{h^*(X)\ne Y\}$. It takes values in $\{-1,0,1\}$, has expectation $\mathcal E(h)$, and satisfies $Z_h^2=\mathbf 1\{h(X)\ne h^*(X)\}$. Consequently, the preceding disagreement bound also controls its variance.

Result: Under the same margin condition, with $\beta=\alpha/(\alpha+1)$, $$ \operatorname{Var}(Z_h)\le E[Z_h^2] \le 2C^{1/(\alpha+1)}\mathcal E(h)^\beta. $$

The first inequality follows from $\operatorname{Var}(Z_h)=E[Z_h^2]-(E[Z_h])^2\le E[Z_h^2]$. The second follows from $Z_h^2=\mathbf 1\{h(X)\ne h^*(X)\}$ and the disagreement result. This is a Bernstein-type variance condition: smaller excess risk forces smaller variance of the loss difference. Its exponent $\beta$, rather than the margin exponent $\alpha$ itself, enters the learning-rate calculation.

Worked Example: A Distribution with a Quadratic Margin Condition

Let $X$ take values in $(0,1)$ with distribution function $P(X\le t)=t^2$, and set $P(Y=1\mid X=x)=(1+x)/2$. The Bayes classifier is $h^*(x)=1$, and $\Delta(x)=x$. Thus $P(\Delta(X)\le t)=t^2$, so the margin condition holds with $\alpha=2$ and $C=1$.

For $0<s<1$, define $h_s(x)=0$ when $x\le s$ and $h_s(x)=1$ when $x>s$. Its disagreement probability is $P(X\le s)=s^2$. The density of $X$ on $(0,1)$ is $2x$, so its excess risk is $$ \mathcal E(h_s)=\int_0^s x(2x)\,dx=\frac{2s^3}{3}. $$ Therefore $P(h_s(X)\ne h^*(X))=s^2=(3\mathcal E(h_s)/2)^{2/3}$. The power $2/3$ agrees with $\beta=\alpha/(\alpha+1)=2/3$: disagreement shrinks as excess risk shrinks, in the precise way predicted by the margin condition.

Combining VC Complexity with Low Noise

Let $\mathcal H$ be a measurable class of classifiers with VC dimension $d\ge1$. Assume a Bayes classifier $h^*$ belongs to $\mathcal H$, and suppose an empirical risk minimizer $\hat h\in\mathcal H$ exists. For a confidence level $1-\delta$, define

q=\frac{d\log(en/d)+\log(1/\delta)}{n},\qquad 1\le d\le n.

A relative VC deviation inequality states that, with probability at least $1-\delta$, the empirical and population means of all the loss differences $Z_h$, $h\in\mathcal H$, differ by at most $$ K\left(\sqrt{E[Z_h^2]\,q}+q\right) $$ for every $h\in\mathcal H$, where $K$ is a universal constant. This form uses the variance scale $E[Z_h^2]$, rather than a uniform constant scale. Its complexity term comes from the VC growth bound: on $n$ observations, the number of distinct prediction patterns is at most $\sum_{j=0}^d {n\choose j}$, which is at most $(en/d)^d$ when $d\le n$. Relative concentration, applied with this growth control and a confidence term $\log(1/\delta)$, yields the stated bound.

Theorem: Under the stated assumptions and the Tsybakov condition with exponent $\alpha\ge0$, there is a constant $A$, depending only on $C$ and universal constants, such that, with probability at least $1-\delta$, $$ \mathcal E(\hat h)\le A\min\left\{1,\ q^{\,(\alpha+1)/(\alpha+2)}\right\}. $$

Here the empirical risk is $n^{-1}\sum_{i=1}^n\mathbf 1\{h(X_i)\ne Y_i\}$. To derive the theorem, use that $h^*\in\mathcal H$ and $\hat h$ minimizes empirical risk, so the empirical mean of $Z_{\hat h}$ is nonpositive. On the relative VC event, this gives $$ \mathcal E(\hat h)\le K\left(\sqrt{E[Z_{\hat h}^2]\,q}+q\right) \le K\left(\sqrt{2C^{1/(\alpha+1)}\mathcal E(\hat h)^\beta q}+q\right). $$ Put $r=\mathcal E(\hat h)$. The last inequality has the form $r\le a\sqrt{r^\beta q}+bq$, for constants $a,b$ depending only on $C$ and $K$. If $q\le1$, set $u=r/q^{1/(2-\beta)}$. Dividing by $q^{1/(2-\beta)}$ gives $$ u\le a u^{\beta/2}+bq^{1-1/(2-\beta)} \le a u^{\beta/2}+b, $$ because $1/(2-\beta)\le1$. Since $0\le\beta<1$, this inequality bounds $u$ by a constant: once $u$ is sufficiently large, $a u^{\beta/2}\le u/2$, so $u\le2b$; below that threshold it is already bounded. Finally, $1/(2-\beta)=(\alpha+1)/(\alpha+2)$. If $q>1$, the excess risk is at most one, which accounts for the minimum in the theorem. $\square$

The exponent interpolates between the ordinary $n^{-1/2}$ scale when $\alpha=0$ and rates approaching $n^{-1}$, up to complexity factors, as the margin condition becomes stronger. For every finite $\alpha$, the exponent is $(\alpha+1)/(\alpha+2)$. The displayed VC complexity includes a logarithmic factor; this is a high-probability upper bound, not a claim that every problem has a matching lower bound.

Worked Example: Computing a VC Rate

Suppose $\alpha=1$, $d=10$, $n=10{,}000$, and $\delta=0.05$. The exponent is $(1+1)/(1+2)=2/3$. The complexity term is $$ q=\frac{10\log(e\cdot1000)+\log(20)}{10{,}000} \approx\frac{10(7.908)+2.996}{10{,}000} \approx0.00821. $$ Thus $q^{2/3}\approx0.0407$, and the theorem bounds excess risk by a constant times approximately $0.041$, with probability at least $0.95$. The unknown constant matters: this calculation gives the rate scale, not a precise numerical guarantee.

Worked Example: Stronger Margin, Faster Rate

Suppose $\alpha=2$, $d=4$, $n=4{,}000$, and $\delta=0.1$. Then the rate exponent is $3/4$, and $$ q=\frac{4\log(e\cdot1000)+\log(10)}{4{,}000} \approx\frac{4(7.908)+2.303}{4{,}000} \approx0.00848. $$ Taking the fourth root gives $q^{1/4}\approx0.3035$; hence $q^{3/4}\approx0.0280$. The excess-risk upper bound is a constant times $0.0280$, with probability at least $0.9$. The comparison with the preceding example illustrates that the exponent changes with the noise condition; the numerical values also depend on the sample size, dimension, confidence level, and unspecified constant.

Common Pitfalls and Interpretation

A frequent mistake is to use the margin exponent $\alpha$ directly as the variance exponent. The variance exponent is instead $\beta=\alpha/(\alpha+1)$, because the small-margin probability bound must first be converted into a disagreement bound. Substituting $\alpha$ in place of $\beta$ changes the rate and can even suggest an impossible exponent.

Another important assumption is that the Bayes classifier lies in $\mathcal H$. The theorem compares the empirical risk minimizer with that classifier. If $\mathcal H$ cannot represent a Bayes decision rule, empirical minimization must also contend with approximation error; the displayed conclusion does not by itself bound excess risk relative to the unrestricted Bayes risk in that setting. Finally, $d$ measures the richness of the classifier class, while $\alpha$ describes the distribution near its decision boundary. They play different roles and cannot be substituted for one another.

Key takeaway: A Tsybakov margin condition yields a Bernstein exponent $\beta=\alpha/(\alpha+1)$. Combining the resulting variance control with relative VC deviations gives an excess-risk scale of $\left([d\log(en/d)+\log(1/\delta)]/n\right)^{1/(2-\beta)}$, provided the Bayes classifier belongs to the class.

Check Your Understanding

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

For margin exponent $\alpha=3$, what is the Bernstein exponent $\beta$, and what is the excess-risk rate exponent?
Why does the excess-risk identity remain valid at covariate values where $\eta(X)=1/2$?
Explain why $E[Z_h^2]$ equals the probability that $h$ disagrees with the Bayes classifier.
Which assumption allows empirical risk minimization to compare directly with Bayes risk in the theorem?
For fixed $d$, confidence level, and finite $\alpha$, how does the rate exponent compare with $1/2$, and what happens as $\alpha$ increases?