Empirical Risk Minimization Under Massart Noise

Why a Uniform Gap Speeds Up Empirical Risk Minimization

In binary classification, a predictor can have small excess risk because it makes errors only on a small part of the feature distribution. A low-noise condition makes that relationship quantitative. Under Massart’s uniform margin gap, every feature value has a conditional class probability bounded away from one half. Consequently, a classifier that disagrees with the Bayes rule on a given amount of probability mass pays a definite amount of excess risk. This converts the usual square-root behavior of uniform estimation into a faster rate for empirical risk minimization.

The result below concerns zero-one loss and a classifier class of finite VC dimension. Its central assumptions are important: the Bayes classifier must belong to the class being minimized over, and the gap must hold uniformly almost surely. The resulting rate has the characteristic scale of VC complexity divided by the sample size and the gap.

Setup and Massart’s Uniform Gap

Let $(X,Y)$ be a random pair, where $X$ takes values in a measurable feature space and $Y\in\{-1,+1\}$. Write $\eta(x)=P(Y=+1\mid X=x)$, and define the zero-one risk of a measurable classifier $g$ by $R(g)=P(g(X)\ne Y)$. A Bayes classifier $g^*$ predicts the more probable label: $g^*(x)=+1$ when $\eta(x)\ge 1/2$, and $g^*(x)=-1$ otherwise. When there are no ties, this minimizes risk over all measurable classifiers.

Definition: The distribution satisfies Massart’s uniform margin gap with parameter $h\in(0,1]$ if $$ |2\eta(X)-1|\ge h \quad\text{almost surely.} $$ The quantity $|2\eta(x)-1|$ is the conditional difference between the probabilities of the more likely and less likely labels. The condition requires that difference to be at least $h$, except on a set of feature values of probability zero.

Let $\mathcal G$ be a class of measurable binary classifiers with VC dimension $d$, and suppose $g^*\in\mathcal G$. Given independent observations $(X_i,Y_i)_{i=1}^n$ from the distribution, an empirical risk minimizer $\hat g$ satisfies $$ \hat R_n(\hat g)=\inf_{g\in\mathcal G}\hat R_n(g), \qquad \hat R_n(g)=\frac1n\sum_{i=1}^n \mathbf 1\{g(X_i)\ne Y_i\}. $$ Assume a measurable minimizer exists; standard measurability or separability conditions on the class suffice for the uniform probability statements below.

Worked Example: Computing the Gap and Excess Risk

Suppose $X$ takes values $a$ and $b$, with probabilities $P(X=a)=0.6$ and $P(X=b)=0.4$. Let $\eta(a)=0.9$ and $\eta(b)=0.65$. At both feature values the Bayes prediction is $+1$. The conditional gaps are $|2(0.9)-1|=0.8$ and $|2(0.65)-1|=0.3$, so the distribution satisfies the condition with $h=0.3$.

Consider the classifier $g$ that predicts $+1$ at $a$ and $-1$ at $b$. The Bayes risk is $R(g^*)=0.6(0.1)+0.4(0.35)=0.06+0.14=0.20$. For $g$, the error probability at $a$ is $0.1$, while at $b$ it is $0.65$. Thus $R(g)=0.6(0.1)+0.4(0.65)=0.06+0.26=0.32$, and the excess risk is $0.32-0.20=0.12$.

The classifiers disagree only at $b$, a set of probability $0.4$. Multiplying this disagreement probability by the gap there gives $0.4(0.3)=0.12$, exactly the excess risk in this example.

Excess Risk Measures Weighted Disagreement

For any classifier $g$, the excess risk over the Bayes rule has an exact conditional expression. It shows why the uniform gap is useful rather than merely a technical condition.

Result: For every measurable binary classifier $g$, $$ R(g)-R(g^*)= E\!\left[|2\eta(X)-1|\,\mathbf 1\{g(X)\ne g^*(X)\}\right]. $$ Consequently, under Massart’s uniform gap, $$ P(g(X)\ne g^*(X))\le \frac{R(g)-R(g^*)}{h}. $$

Derivation. Condition on $X=x$. If $g(x)=g^*(x)$, the conditional difference in error probabilities is zero. If they disagree, one predicts the more likely label and the other predicts the less likely label. The conditional error probability of the latter exceeds that of the former by $|\eta(x)-(1-\eta(x))|=|2\eta(x)-1|$. Therefore the conditional excess risk is $|2\eta(x)-1|\mathbf 1\{g(x)\ne g^*(x)\}$. Taking expectations proves the identity. Since $|2\eta(X)-1|\ge h$ almost surely, the identity also gives $R(g)-R(g^*)\ge hP(g(X)\ne g^*(X))$, proving the inequality. $\square$

This identity also explains the statistical mechanism. The variance of the empirical comparison with $g^*$ is controlled by disagreement probability; Massart’s gap bounds that probability by excess risk divided by $h$. Thus a classifier with small excess risk has a comparison with relatively small variance.

A Fast Excess-Risk Bound for VC Classes

We use the standard relative-deviation inequality for VC classes. In the form needed here, there is a universal constant $C_0$ such that, for $n\ge d\ge1$, a fixed measurable comparator $g^*$, and a measurable VC class of dimension $d$, with probability at least $1-\delta$, simultaneously for every $g\in\mathcal G$, $$ \left|(\hat R_n(g)-\hat R_n(g^*))-(R(g)-R(g^*))\right| \le C_0\left[ \sqrt{P Z_g^2\,q}+q \right], \qquad q=\frac{d\log(en/d)+\log(2/\delta)}{n}, $$ where $$ Z_g(X,Y)=\mathbf 1\{g(X)\ne Y\}-\mathbf 1\{g^*(X)\ne Y\}. $$ This is a uniform VC Bernstein inequality for zero-one loss differences. The square-root term depends on the second moment $PZ_g^2$, which is what allows the Massart condition to yield a fast rate. As usual, the inequality is understood under conditions ensuring the stated uniform event is measurable.

Theorem: Suppose $n\ge d\ge1$, $g^*\in\mathcal G$, and the distribution satisfies Massart’s uniform gap with parameter $h\in(0,1]$. There is a universal constant $K$ such that, with probability at least $1-\delta$, $$ R(\hat g)-R(g^*) \le K\,\frac{d\log(en/d)+\log(2/\delta)}{h n}. $$

Proof. Set $r=R(\hat g)-R(g^*)$, which is nonnegative because $g^*$ is Bayes optimal. For each $g$, $Z_g^2$ is one exactly when $g(X)\ne g^*(X)$, and is zero otherwise: if the predictions agree, their losses agree for either label; if they differ, one loss is zero and the other is one. Hence $$ PZ_g^2=P(g(X)\ne g^*(X)) \le \frac{R(g)-R(g^*)}{h}. $$ On the event in the relative-deviation inequality, apply it to $\hat g$. Since $g^*\in\mathcal G$ and $\hat g$ minimizes empirical risk, $\hat R_n(\hat g)-\hat R_n(g^*)\le0$. Therefore $$ r \le |(\hat R_n(\hat g)-\hat R_n(g^*))-r| \le C_0\left(\sqrt{\frac{r q}{h}}+q\right). $$ For nonnegative $r,q$, the inequality $C_0\sqrt{rq/h}\le r/2+C_0^2q/(2h)$ follows by expanding the square $(\sqrt r-C_0\sqrt{q/h})^2\ge0$. Substitution yields $$ r\le \frac r2+\frac{C_0^2q}{2h}+C_0q, \qquad r\le \left(\frac{C_0^2}{h}+2C_0\right)q \le \frac{C_0^2+2C_0}{h}\,q, $$ where the final inequality uses $h\le1$. Taking $K=C_0^2+2C_0$ proves the claimed bound. $\square$

The dependence on $h$ is inverse-linear: a smaller gap weakens the conversion from disagreement to excess risk. For fixed confidence and dimension, the bound scales as $1/(hn)$, up to the VC logarithmic factor. If $d=0$, all classifiers in the class agree on every singleton feature set, so a class containing $g^*$ has zero excess risk; the theorem treats the nontrivial case $d\ge1$.

Worked Example: A Finite-Class Bound With Explicit Constants

A finite subclass with $M=20$ classifiers also has a direct union-bound calculation. Suppose it contains $g^*$, the gap is $h=0.25$, the sample size is $n=1000$, and the desired failure probability is $\delta=0.05$. For each fixed $g$, Bernstein’s inequality for $Z_g$, which is bounded in absolute value by one, gives a deviation at most $\sqrt{2PZ_g^2 L/n}+2L/(3n)$, where $L=\log(2M/\delta)$. A union bound makes this hold for all $M$ comparisons with probability at least $1-\delta$.

Here $L=\log(800)\approx6.685$, so $a=L/n\approx0.006685$. For an empirical risk minimizer, the same comparison as in the theorem gives $r\le\sqrt{2ra/h}+2a/3$. Since $\sqrt{2ra/h}\le r/2+a/h$, it follows that $r\le 2a/h+4a/3$. Numerically, $2a/h=2(0.006685)/0.25\approx0.05348$, and $4a/3\approx0.00891$. Thus the bound is $r\le0.06239$, or approximately $0.0624$, with probability at least $0.95$. This explicit finite-class calculation illustrates the same inverse-gap dependence; the VC theorem replaces the finite-class logarithm by a dimension-dependent complexity.

Worked Example: Comparing Two Gap Values

Suppose the dimension and sample size give $d\log(en/d)=30$, and take $\delta=0.05$ and $n=600$. The complexity numerator is $30+\log(40)\approx33.689$, so its ratio to $n$ is approximately $0.05615$.

For $h=0.5$, the theorem’s rate scale, before multiplication by the universal constant $K$, is $0.05615/0.5\approx0.1123$. For $h=0.25$, it is $0.05615/0.25\approx0.2246$. Halving the gap doubles this rate scale. These are bound scales, not exact prediction errors: the theorem guarantees a bound multiplied by $K$, and the actual excess risk may be much smaller.

Assumptions, Interpretation, and a Common Pitfall

The inclusion $g^*\in\mathcal G$ ensures that empirical minimization is compared with a classifier of zero excess risk. Without it, the same argument does not directly give the displayed bound relative to Bayes risk: the empirical minimizer may be unable to attain that benchmark. The result is therefore an estimation guarantee under a realizability-of-the-Bayes-rule assumption, not a general approximation guarantee.

A common mistake is to say, “The gap is positive, so the excess risk is $O(1/n)$,” without tracking how large the gap is. The correction is visible in the proof: Massart’s condition gives $P(g\ne g^*)\le [R(g)-R(g^*)]/h$. The variance term therefore involves $r/h$, and solving the resulting inequality leaves a factor $1/h$ in the rate. A tiny positive gap can make the bound much weaker. Also, the gap condition is uniform almost surely; a condition that holds only on average cannot be substituted into this proof without a different argument.

Key takeaway: Under a uniform Massart gap and inclusion of the Bayes classifier in the VC class, disagreement is controlled by excess risk. That variance control yields a high-probability ERM excess-risk rate of order $[d\log(en/d)+\log(1/\delta)]/(hn)$.

Check Your Understanding

Check that you can identify the role of each assumption and each term in the rate.

For a classifier that disagrees with the Bayes rule on a set of probability $p$, what lower bound does Massart’s gap give for its excess risk?
Why does $PZ_g^2=P(g(X)\ne g^*(X))$ for the zero-one loss difference used in the proof?
Where does the inverse factor $1/h$ enter the ERM argument?
Why is it necessary to assume $g^*\in\mathcal G$ for the stated comparison with Bayes risk?
If the gap is halved while all other quantities stay fixed, how does the theorem’s rate scale change?