Introduction
Risk calculations are easiest to audit when the outcome space is finite: list the possible outcomes, write down their probabilities, evaluate each predictor's loss at each outcome, and add. The arithmetic is elementary, but the choice of benchmark is not merely bookkeeping. A number called “excess risk” is meaningful only after its reference risk has been stated, and comparator-relative regret answers a different question from excess risk relative to the best predictor in a class.
This tutorial carries out those calculations for classification, squared-error prediction, and a finite decision problem. In each case, the population distribution and the observed sample are kept separate. This distinction matters because a predictor can perform best on the observed sample without having the smallest population risk.
Finite-Support Risk Calculations
Let \(Z=(X,Y)\) denote a feature-response pair, and let a predictor \(h\) incur loss \(\ell(h(X),Y)\). Suppose \(Z\) has finite support \(z_1,\ldots,z_m\), where \(z_j=(x_j,y_j)\), with probabilities \(p_j=P(Z=z_j)\). The probabilities satisfy \(p_j\geq 0\) and \(\sum_{j=1}^m p_j=1\). Assume the loss is defined and finite at each support point for the predictors being considered.
The population calculation weights losses by the probabilities in the data-generating distribution. The empirical calculation instead weights them by observed proportions. The two formulas look alike, but their weights need not be the same. A finite support makes the sum explicit; it does not make the sample proportions equal to the population probabilities.
When the class is finite, each infimum above is a minimum. Excess risk relative to the class minimum is nonnegative. Regret relative to a particular comparator can be positive, zero, or negative: a negative value means \(h\) has lower risk than that comparator. The comparator does not have to be optimal.
Two Useful Identities
Proof. Write \(L=\ell(h(X),Y)\). Since \(Z\) takes values only in \(z_1,\ldots,z_m\), the loss \(L\) takes the corresponding values \(\ell(h(x_j),y_j)\). Partitioning the expectation according to the disjoint events \(\{Z=z_j\}\) gives
For the sample, group the \(n\) summands in \(n^{-1}\sum_{i=1}^n\ell(h(X_i),Y_i)\) according to which support point was observed. The loss at \(z_j\) appears exactly \(N_j\) times, so the sum is \(n^{-1}\sum_{j=1}^mN_j\ell(h(x_j),y_j)=\sum_{j=1}^m(N_j/n)\ell(h(x_j),y_j)\). This proves both formulas. \(\square\)
Proof. Expand the right-hand side and cancel the common benchmark:
Replacing \(R\) and \(R^*_{\mathcal H}\) throughout by \(\widehat R_n\) and \(\widehat R^*_{\mathcal H,n}\) gives the empirical identity by the same cancellation. Thus comparator regret is the difference between two excess risks measured against the same benchmark; it is not itself necessarily an excess risk. \(\square\)
Worked Calculations
Worked Example: Classification With Population and Sample Weights
Let \(X\in\{a,b\}\), \(Y\in\{0,1\}\), and use zero-one loss, which is \(1\) for an incorrect label and \(0\) for a correct one. The population probabilities and sample counts are:
| Outcome \((X,Y)\) | Population probability | Observed count |
|---|---|---|
| \((a,0)\) | 0.4 | 4 |
| \((a,1)\) | 0.1 | 1 |
| \((b,0)\) | 0.1 | 2 |
| \((b,1)\) | 0.4 | 3 |
There are \(n=4+1+2+3=10\) observations. Consider \(h_0\), which always predicts 0; \(h_1\), which always predicts 1; and \(h_X\), which predicts 0 at \(a\) and 1 at \(b\). The loss vectors in the table's outcome order are \(h_0:(0,1,0,1)\), \(h_1:(1,0,1,0)\), and \(h_X:(0,1,1,0)\).
For \(h_0\), the population risk is \(0.4(0)+0.1(1)+0.1(0)+0.4(1)=0.5\). For \(h_1\), it is \(0.4(1)+0.1(0)+0.1(1)+0.4(0)=0.5\). For \(h_X\), it is \(0.4(0)+0.1(1)+0.1(1)+0.4(0)=0.2\).
Now use the observed frequencies \(4/10,1/10,2/10,3/10\). The empirical risks are
Take \(\mathcal H=\{h_0,h_1,h_X\}\). Its population benchmark is \(0.2\), attained by \(h_X\), so the population excess risks in the order \(h_0,h_1,h_X\) are \(0.3,0.3,0\). Its empirical benchmark is \(0.3\), also attained by \(h_X\), so empirical excess risks are \(0.1,0.3,0\). If the specified comparator is \(h_0\), population regrets for \(h_0,h_1,h_X\) are \(0,0,-0.3\); empirical regrets are \(0,0.2,-0.1\). The negative regret for \(h_X\) says it improves on \(h_0\), not that it has negative risk.
Worked Example: Squared Loss and a Sample-Selected Predictor
Let the response \(Y\) take values \(0,2,4\) with probabilities \(1/4,1/2,1/4\). Use squared loss \(\ell(c,y)=(c-y)^2\) and consider constant predictors \(h_c(x)=c\) for \(c\in\{1,2,3\}\). Suppose the observed sample contains one 0, three 2s, and two 4s, so \(n=6\).
For \(c=1\), the squared losses at \(0,2,4\) are \(1,1,9\), respectively. Thus \(R(h_1)=(1/4)(1)+(1/2)(1)+(1/4)(9)=3\). For \(c=2\), the losses are \(4,0,4\), so \(R(h_2)=(1/4)(4)+(1/2)(0)+(1/4)(4)=2\). For \(c=3\), the losses are \(9,1,1\), so \(R(h_3)=(1/4)(9)+(1/2)(1)+(1/4)(1)=3\).
The population benchmark over these three predictors is \(R^*_{\mathcal H}=2\), attained by \(h_2\). The population excess risks for \(h_1,h_2,h_3\) are therefore \(1,0,1\).
For the sample, the frequencies of \(0,2,4\) are \(1/6,3/6,2/6\). Substituting the losses gives
The empirical benchmark is \(2\), attained by \(h_2\), so empirical excess risks are \(5/3,0,1/3\). Relative to the fixed comparator \(h_2\), the empirical regrets are also \(5/3,0,1/3\), since the comparator happens to attain the empirical benchmark. If instead \(h_3\) were chosen as comparator, empirical regret for \(h_2\) would be \(2-7/3=-1/3\). The observed sample has not changed the definition of population risk: it has only supplied different weights for empirical risk.
Worked Example: Regret in a Finite Decision Problem
There is no feature in this decision problem; a decision is one of two actions, \(a\) or \(b\), and the outcome is one of three states \(A,B,C\). The population probabilities are \(P(A)=0.5\), \(P(B)=0.3\), and \(P(C)=0.2\). The loss table is:
| Action | State A | State B | State C |
|---|---|---|---|
| \(a\) | 0 | 2 | 1 |
| \(b\) | 1 | 0 | 2 |
Suppose the sample has four outcomes: two \(A\)'s, one \(B\), and one \(C\). The population risk of \(a\) is \(0.5(0)+0.3(2)+0.2(1)=0.8\); the population risk of \(b\) is \(0.5(1)+0.3(0)+0.2(2)=0.9\). Over the class \(\{a,b\}\), the population benchmark is \(0.8\). The excess risks are 0 for \(a\) and \(0.1\) for \(b\).
The sample frequencies are \(2/4,1/4,1/4\). Hence the empirical risks are \(\widehat R_4(a)=[2(0)+1(2)+1(1)]/4=3/4\) and \(\widehat R_4(b)=[2(1)+1(0)+1(2)]/4=4/4=1\). The empirical benchmark is \(3/4\), so the empirical excess risks are 0 for \(a\) and \(1/4\) for \(b\).
For a comparator-relative calculation, specify \(b\) as the comparator. Population regret for \(a\) relative to \(b\) is \(0.8-0.9=-0.1\), while empirical regret is \(3/4-1=-1/4\). The negative signs record that \(a\) has lower risk than this particular comparator. They do not conflict with nonnegative excess risk relative to the best action in the class.
How to Keep the Benchmarks Straight
A reliable calculation follows a fixed order: write the support and its weights, list the loss of every predictor at every support point, sum using population probabilities, and only then repeat the calculation using sample frequencies. Afterward, state the benchmark before subtracting it. This prevents a numerical result from being detached from the question it answers.
- Population excess risk compares a predictor's population risk with the best population risk in the specified class.
- Empirical excess risk compares observed empirical risks with the best empirical risk in the specified class.
- Comparator regret compares one predictor with a named alternative, whether or not that alternative is optimal.
In a finite class, finding either benchmark requires calculating the risk of each member and taking the smallest. If the benchmark is an explicitly named comparator rather than the class minimum, do not silently replace it with the minimum. The resulting regret may be negative, as in the decision example.
Common Mistake
A frequent error is to compute \(R(h)-R(g)\) and call it “excess risk” without saying what \(g\) is. That subtraction is comparator-relative regret. It equals excess risk only in the special case where \(g\) attains the population benchmark for the class under discussion. Similarly, subtracting the empirical minimum from a population risk mixes two different weight systems. Keep the risk type and benchmark aligned: population with population, empirical with empirical, unless a different comparison is deliberately defined and clearly named.
Check Your Understanding
For each question, write down the weights and the benchmark before doing the subtraction.
- A predictor has losses \(0,2,4\) on three outcomes with probabilities \(1/2,1/3,1/6\). Calculate its population risk.
- In a sample of eight observations, an outcome occurs three times and has loss 5. What is its contribution to empirical risk?
- A class has population risks \(0.4,0.6,0.9\). Find the excess risk of the predictor with risk \(0.6\).
- A predictor has risk \(0.7\), and its stated comparator has risk \(0.5\). Calculate comparator-relative regret and interpret its sign.
- Why can empirical excess risk be zero for a predictor whose population excess risk is positive?