Three Sources of Risk, One Decomposition
An empirical risk minimizer can have high risk for two different reasons. The hypothesis class may not contain a rule with risk as low as the best possible rule, or the data may lead ERM to select a rule that is worse than the best member of the class. These contributions are distinct: the first is a property of the class and the data distribution, while the second also depends on the training sample.
We make that distinction concrete for binary classification. Let \((X,Y)\) have a fixed distribution, with \(Y\in\{0,1\}\). A classifier \(h\) is a measurable function from the feature space to \(\{0,1\}\). Under zero-one loss, its risk is its probability of misclassification. Write \(R^*\) for the smallest risk attainable by any measurable classifier, and \(R_{\mathcal H}^*\) for the smallest risk among classifiers in a specified class \(\mathcal H\).
For a training sample \(S=((X_1,Y_1),\ldots,(X_n,Y_n))\), the empirical risk is \(\widehat R_S(h)=n^{-1}\sum_{i=1}^n \mathbf 1\{h(X_i)\ne Y_i\}\). An ERM is any \(\hat h\in\mathcal H\) minimizing this empirical risk. When the class is finite, an ERM exists; if several classifiers minimize empirical risk, a tie-breaking rule specifies which one is selected. The selected classifier and its estimation contribution are random because they depend on \(S\).
The target risk has a useful conditional-probability description. Let \(\eta(x)=P(Y=1\mid X=x)\). Predicting 0 at \(x\) has conditional error \(\eta(x)\), while predicting 1 has conditional error \(1-\eta(x)\). Choosing the smaller of these two errors at each \(x\) gives $$ R^*=E\bigl[\min\{\eta(X),1-\eta(X)\}\bigr]. $$ A Bayes classifier predicts 1 where \(\eta(x)>1/2\), predicts 0 where \(\eta(x)<1/2\), and may choose either label where they are equal.
What the Decomposition Says
Proof. Add and subtract \(R_{\mathcal H}^*\) on the left: $$ R(\hat h)-R^* = \bigl(R_{\mathcal H}^*-R^*\bigr) + \bigl(R(\hat h)-R_{\mathcal H}^*\bigr). $$ Because the class is a subset of the measurable classifiers, \(R_{\mathcal H}^*\ge R^*\). Also, because \(\hat h\in\mathcal H\), its risk is at least the infimum over \(\mathcal H\), so \(R(\hat h)\ge R_{\mathcal H}^*\). These inequalities establish nonnegativity of both terms. \(\square\)
This identity applies to every realized training sample, not just to an expectation or a large-sample limit. It also prevents a common ambiguity: “excess risk” must be measured relative to a stated benchmark. Excess over \(R^*\) includes approximation error; excess over \(R_{\mathcal H}^*\) is the estimation contribution alone.
Worked Examples
Worked Example: Realizable ERM Can Still Have Estimation Error
Let \(X\in\{a,b\}\), with \(P(X=b)=0.2\) and \(P(X=a)=0.8\). The label is deterministic: \(Y=0\) at \(a\) and \(Y=1\) at \(b\). Consider the two classifiers \(h^*(a)=0,\ h^*(b)=1\), and \(h_0(a)=h_0(b)=0\). The class is \(\mathcal H=\{h^*,h_0\}\). For ERM, break empirical-risk ties in favor of \(h_0\).
Target and best-in-class risks. The classifier \(h^*\) always predicts the observed label, so \(R(h^*)=0\). No risk can be negative, hence \(R^*=0\); since \(h^*\in\mathcal H\), \(R_{\mathcal H}^*=0\). This is a realizable setting: a member of the class labels every possible observation correctly.
Risk of the other class member. The classifier \(h_0\) errs exactly when \(X=b\), so \(R(h_0)=P(X=b)=0.2\).
Estimation contribution of ERM. If the sample contains at least one observation with \(X=b\), then \(h_0\) makes at least one training error while \(h^*\) makes none. ERM selects \(h^*\), with estimation contribution 0. If every training feature is \(a\), both classifiers have empirical risk 0 and the tie rule selects \(h_0\), whose estimation contribution is 0.2. Independence gives $$ P(X_1=\cdots=X_n=a)=0.8^n. $$ Therefore the expected estimation contribution is \(0.2(0.8)^n\). For \(n=1\), it is \(0.16\). The target and best-in-class risks are both zero, yet finite-sample ERM can have positive risk because the sample may not reveal the feature value \(b\).
Worked Example: Noisy Labels With No Approximation Error
Let \(X\) be constant and \(Y\sim\operatorname{Bernoulli}(0.7)\). Take \(\mathcal H=\{h_0,h_1\}\), where \(h_j\) always predicts \(j\). Use a training sample of size \(n=1\); ERM predicts the observed label.
Target and best-in-class risks. Predicting 1 errs with probability \(0.3\), while predicting 0 errs with probability \(0.7\). Thus \(R^*=0.3\). The best class member is \(h_1\), so \(R_{\mathcal H}^*=0.3\) and the approximation error is zero. Labels are not deterministic given \(X\), so the setting is not realizable. Here the class nevertheless contains a Bayes classifier.
Expected risk of one-observation ERM. With probability \(0.7\), the observed label is 1 and ERM selects \(h_1\), whose risk is \(0.3\). With probability \(0.3\), it selects \(h_0\), whose risk is \(0.7\). Consequently, $$ E[R(\hat h)] =0.7(0.3)+0.3(0.7) =0.21+0.21 =0.42. $$ Subtracting the best-in-class risk gives expected estimation contribution \(0.42-0.3=0.12\). Because approximation error is zero, the expected excess over the target risk is also \(0.12\).
Derivation. The better constant classifier is \(h_1\), with risk \(1-p\). The one-observation ERM selects \(h_1\) with probability \(p\), giving estimation contribution 0, and selects \(h_0\) with probability \(1-p\), giving contribution \(p-(1-p)=2p-1\). Taking the expectation yields $$ p(0)+(1-p)(2p-1)=(1-p)(2p-1). $$ For \(p=0.7\), this is \(0.3(0.4)=0.12\), as calculated above. \(\square\)
Worked Example: Misspecification Adds Approximation Error
Let \(P(X=0)=0.75\) and \(P(X=1)=0.25\), with \(P(Y=1\mid X=0)=0.1\) and \(P(Y=1\mid X=1)=0.8\). Let \(\mathcal H\) contain only the two constant classifiers \(h_0\) and \(h_1\). As in the previous example, use \(n=1\), so ERM selects the constant classifier that matches the observed label.
Target risk. A Bayes classifier predicts 0 at \(X=0\) and 1 at \(X=1\). Its conditional error probabilities are \(0.1\) and \(0.2\), respectively. Therefore $$ R^*=0.75(0.1)+0.25(0.2)=0.075+0.05=0.125. $$
Best-in-class risk. The marginal probability of label 1 is $$ P(Y=1)=0.75(0.1)+0.25(0.8)=0.075+0.2=0.275. $$ Thus \(R(h_0)=0.275\) and \(R(h_1)=P(Y=0)=0.725\). The best class member is \(h_0\), giving \(R_{\mathcal H}^*=0.275\) and approximation error \(0.275-0.125=0.15\). The class is misspecified because neither constant classifier agrees with the Bayes rule at both feature values.
Expected estimation contribution. ERM selects \(h_1\) with probability \(0.275\), in which case the contribution over the best-in-class risk is \(0.725-0.275=0.45\). It selects \(h_0\) with probability \(0.725\), in which case the contribution is zero. Hence $$ E[R(\hat h)-R_{\mathcal H}^*] =0.275(0.45)+0.725(0) =0.12375. $$ The expected selected risk is \(0.275+0.12375=0.39875\). Its excess over target risk is \(0.39875-0.125=0.27375\), which equals the sum \(0.15+0.12375\) of approximation error and expected estimation contribution.
Comparing the Three Settings
| Setting and example | Target risk \(R^*\) | Best-in-class risk \(R_{\mathcal H}^*\) | Expected estimation contribution |
|---|---|---|---|
| Realizable, rare feature value; sample size \(n\) | 0 | 0 | \(0.2(0.8)^n\) |
| Noisy labels; constant class; \(n=1\) | 0.3 | 0.3 | 0.12 |
| Misspecified constant class; \(n=1\) | 0.125 | 0.275 | 0.12375 |
The values illustrate three different questions. Is a zero-error classifier in the class? That is the realizability question. Does the class attain the best possible risk even when labels are noisy? That is what happens in the agnostic example. Does the restriction to the class force a risk above the target? That is the positive approximation error in the misspecified example. In every case, the estimation contribution measures the additional risk from selecting a nonoptimal member of the class.
Common Pitfall: Calling All Excess Risk “Estimation Error”
A tempting but incorrect calculation in the misspecified example is to call \(R(\hat h)-R^*=0.27375\) the estimation contribution. That quantity is the total expected excess risk over the target. It includes the \(0.15\) approximation error that remains even if one always selects the best class member. The estimation contribution alone is \(0.12375\), measured relative to \(R_{\mathcal H}^*\).
A second pitfall is to treat “agnostic” and “misspecified” as synonyms. The agnostic example has nondeterministic labels, but its class still contains a Bayes classifier, so approximation error is zero. In the misspecified example, the class cannot represent the Bayes decision rule and its best risk is strictly larger than the target. Label noise and class misspecification are separate features of a problem; either can occur without the other.
Check Your Understanding
For each question, distinguish the target, best-in-class, and sample-dependent quantities.
- In the realizable example, why can ERM have positive risk even though the class contains a classifier with zero risk?
- In the noisy-label example, which fact makes the target risk positive, and which fact makes the approximation error zero?
- For the misspecified example, calculate the risk of the constant-one classifier and explain why it is not best in class.
- If a selected classifier has risk \(0.4\), the target risk is \(0.1\), and the best-in-class risk is \(0.25\), find its approximation error and estimation contribution.
- Can labels be noisy while approximation error is zero? Can approximation error be positive when a classifier has been selected perfectly within its class? Explain briefly.