Agnostic ERM Over Finite Hypothesis Classes

Why Agnostic Classification Needs a Different Guarantee

In classification, a hypothesis may make errors even when it is the best choice available. The labels may be noisy, or the hypothesis class may not contain a classifier that predicts well for every possible input. In this agnostic setting, a useful guarantee should not promise zero risk. It should compare the risk of the selected classifier with the smallest risk achievable within the class.

The key issue is estimation: an empirical risk minimizer chooses a classifier using a finite sample, while the goal is to control its population risk. For a finite class, concentration of each empirical risk, followed by a union bound, controls all candidate classifiers simultaneously. This gives a bound with two conceptually distinct parts: the best-in-class risk and a sampling error term.

Population and Empirical Classification Risk

Let $(X,Y)$ be a random pair with values in $\mathcal{X}\times\{0,1\}$, and let $(X_1,Y_1),\ldots,(X_n,Y_n)$ be independent observations with the same distribution as $(X,Y)$. Let $\mathcal{H}$ be a nonempty finite set of measurable classifiers $h:\mathcal{X}\to\{0,1\}$, with $M=|\mathcal{H}|$. The zero-one loss is one when a prediction is wrong and zero otherwise.

Definition: The population risk of $h\in\mathcal{H}$ is $R(h)=P(h(X)\ne Y)$. Its empirical risk on the sample is $\widehat{R}_n(h)=\frac{1}{n}\sum_{i=1}^n \mathbf{1}\{h(X_i)\ne Y_i\}$. The best-in-class risk is $R_{\mathcal{H}}^*=\min_{h\in\mathcal{H}}R(h)$. An empirical risk minimizer, or ERM, is any $\widehat{h}\in\mathcal{H}$ satisfying $\widehat{R}_n(\widehat{h})=\min_{h\in\mathcal{H}}\widehat{R}_n(h)$.

Because the class is finite, a minimizer $h^*$ of $R(h)$ over $\mathcal{H}$ exists. There may be more than one such minimizer, just as there may be more than one empirical minimizer. The guarantee below holds for any choice of $h^*$ and any ERM $\widehat{h}$.

Worked Example: Finding the Best Risk in a Finite Class

Suppose $X\in\{a,b\}$, with $P(X=a)=0.6$ and $P(X=b)=0.4$. The conditional label probabilities are $P(Y=1\mid X=a)=0.8$ and $P(Y=1\mid X=b)=0.25$. Consider three classifiers: $h_0$ predicts 0 at both inputs, $h_1$ predicts 1 at both inputs, and $h_s$ predicts 1 at $a$ and 0 at $b$.

For $h_0$, an error occurs when $Y=1$. Therefore $R(h_0)=0.6(0.8)+0.4(0.25)=0.48+0.10=0.58$.

For $h_1$, an error occurs when $Y=0$. Thus $R(h_1)=0.6(0.2)+0.4(0.75)=0.12+0.30=0.42$.

For $h_s$, the error probabilities are $0.2$ at $a$ and $0.25$ at $b$. Hence $R(h_s)=0.6(0.2)+0.4(0.25)=0.12+0.10=0.22$. The best-in-class risk is $R_{\mathcal{H}}^*=0.22$, attained by $h_s$. This calculation concerns population risks; an ERM based on a sample may select a different classifier.

Uniform Control of Empirical Risks

For each fixed $h$, the observed losses $\mathbf{1}\{h(X_i)\ne Y_i\}$ are independent Bernoulli random variables with mean $R(h)$. Hoeffding’s inequality states that for independent random variables $Z_1,\ldots,Z_n$ taking values in $[0,1]$, with common mean $\mu$, their average satisfies $P(|n^{-1}\sum_i Z_i-\mu|>t)\le 2\exp(-2nt^2)$ for $t>0$. Apply this to the losses for a fixed $h$, then take a union bound across the $M$ hypotheses.

Theorem: For every $t>0$, $$ P\left(\sup_{h\in\mathcal{H}}|\widehat{R}_n(h)-R(h)|>t\right) \le 2M\exp(-2nt^2). $$ In particular, for $0<\delta<1$, with probability at least $1-\delta$, $$ \sup_{h\in\mathcal{H}}|\widehat{R}_n(h)-R(h)| \le \sqrt{\frac{\log(2M/\delta)}{2n}}. $$

To see the first inequality, for each $h$ let $A_h$ be the event that its empirical risk differs from its population risk by more than $t$. Hoeffding’s inequality gives $P(A_h)\le 2\exp(-2nt^2)$. Since the event that the supremum exceeds $t$ is the union of the $A_h$, the union bound gives $P(\bigcup_{h\in\mathcal{H}} A_h)\le \sum_{h\in\mathcal{H}}P(A_h)\le 2M\exp(-2nt^2)$. For the second inequality, choose $t$ so that the right-hand side equals $\delta$: solving $2M\exp(-2nt^2)=\delta$ gives $t=\sqrt{\log(2M/\delta)/(2n)}$.

The Agnostic ERM Bound

Write $h^*$ for any population-risk minimizer in $\mathcal{H}$, and $\widehat{h}$ for any ERM. On the event of uniform deviation at most $t$, the difference between their population risks can be bounded by adding and subtracting empirical risks. The ERM property makes the empirical-risk difference nonpositive.

Theorem: Under the assumptions above, for $0<\delta<1$, every ERM $\widehat{h}$ satisfies, with probability at least $1-\delta$, $$ R(\widehat{h}) \le R_{\mathcal{H}}^* +2\sqrt{\frac{\log(2M/\delta)}{2n}} =R_{\mathcal{H}}^*+\sqrt{\frac{2\log(2M/\delta)}{n}}. $$ Equivalently, the excess risk over the best classifier in the class is at most $\sqrt{2\log(2M/\delta)/n}$.

Proof. By finiteness, choose $h^*\in\mathcal{H}$ with $R(h^*)=R_{\mathcal{H}}^*$. On the event $\sup_{h\in\mathcal{H}}|\widehat{R}_n(h)-R(h)|\le t$, write

\begin{aligned} R(\widehat{h})-R(h^*) &=\bigl(R(\widehat{h})-\widehat{R}_n(\widehat{h})\bigr) +\bigl(\widehat{R}_n(\widehat{h})-\widehat{R}_n(h^*)\bigr)\\ &\quad+\bigl(\widehat{R}_n(h^*)-R(h^*)\bigr)\\ &\le t+0+t=2t. \end{aligned}

The first and third terms are at most $t$ by the event under consideration. The middle term is at most zero because $\widehat{h}$ minimizes empirical risk over $\mathcal{H}$. Set $t=\sqrt{\log(2M/\delta)/(2n)}$. The uniform-deviation theorem says that the event has probability at least $1-\delta$, which proves the result. $\square$

The bound separates the benchmark from the cost of learning from data. The term $R_{\mathcal{H}}^*$ is a property of the distribution and the chosen class; the term $\sqrt{2\log(2M/\delta)/n}$ is the finite-sample estimation allowance. The theorem does not claim the benchmark is zero, nor does it claim that the ERM is the best possible learning procedure.

Worked Example: A Noisy Label Distribution

Let $X$ have any distribution and let $Y$ be independent of $X$, with $P(Y=1)=0.7$. Take $\mathcal{H}$ to contain the two constant classifiers $h_0(x)=0$ and $h_1(x)=1$. Their risks are $R(h_0)=0.7$ and $R(h_1)=0.3$, so $R_{\mathcal{H}}^*=0.3$. Neither classifier has zero risk.

For $n=50$ and $\delta=0.1$, the theorem gives an excess-risk allowance of $\sqrt{2\log(2\cdot2/0.1)/50}=\sqrt{2\log(40)/50}$. Since $\log(40)\approx3.6889$, this is $\sqrt{7.3778/50}=\sqrt{0.14756}\approx0.3841$. Thus, with probability at least $0.9$, every ERM has risk at most $0.3+0.3841=0.6841$. The guarantee is valid even though the class cannot achieve zero error; its benchmark remains $0.3$.

Worked Example: Choosing a Sample Size

Suppose $\mathcal{X}=\{1,2,3\}$, $X$ is uniform on these three values, and $P(Y=1\mid X=1,2,3)=(0.2,0.5,0.8)$. Let $\mathcal{H}$ contain all $2^3=8$ binary classifiers on these inputs. At input 1 the smaller error probability is $0.2$, at input 2 either prediction has error probability $0.5$, and at input 3 the smaller error probability is $0.2$. Therefore $R_{\mathcal{H}}^*=(0.2+0.5+0.2)/3=0.3$.

To guarantee excess risk at most $\epsilon=0.15$ with confidence at least $0.95$, it is enough to choose $n$ so that $\sqrt{2\log(2M/\delta)/n}\le0.15$. Squaring both sides and rearranging gives $n\ge2\log(2M/\delta)/(0.15)^2$.

Here $2M/\delta=16/0.05=320$, and $\log(320)\approx5.7683$. Thus $n\ge 2(5.7683)/0.0225=512.74$, so $n=513$ suffices. With that sample size, the guarantee is $R(\widehat{h})\le0.3+0.15=0.45$ with probability at least $0.95$.

Reading the Guarantee Carefully

The finite-class bound becomes more informative as $n$ increases and less informative as the class size $M$ increases. Its dependence on class size enters through $\log M$, rather than $M$ itself. The confidence level also appears inside the logarithm: asking for a smaller failure probability $\delta$ increases the required sample size.

A common mistake is to use the realizable argument and treat the absence of training errors as the relevant target in every classification problem. That reasoning assumes a hypothesis in the class can achieve zero population risk and that the observed labels are compatible with such a hypothesis. In the agnostic setting, these assumptions need not hold. Even an ERM with empirical risk zero can have positive population risk. The correction is to compare its population risk with $R_{\mathcal{H}}^*$, and to control the difference using uniform empirical-to-population deviations.

The result is specific to a finite class and bounded zero-one loss. Its role here is to show how agnostic ERM can be controlled without assuming a perfect classifier: the empirical minimizer performs nearly as well as the best available member of the class, up to a sample-dependent estimation term.

Check Your Understanding

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

Why does the best-in-class risk exist when $\mathcal{H}$ is finite and nonempty?
In the proof of the ERM bound, which term is nonpositive, and what property makes it so?
If $M$ increases while $n$ and $\delta$ stay fixed, what happens to the estimation allowance?
For $M=4$, $n=100$, and $\delta=0.05$, write the numerical expression for the excess-risk allowance.
Why does the agnostic bound compare with $R_{\mathcal{H}}^*$ rather than necessarily with zero?