Common Confusions About Risk and Regret

Three Questions Before Comparing Risks

A numerical risk is not meaningful in isolation. To interpret it, ask which distribution produced it, which loss was used, and what benchmark it is compared with. Confusing any of these can turn a correct calculation into an incorrect conclusion: a low training error is not automatically a low population error, and a lower surrogate loss is not automatically better performance on the target task.

Let \(Z=(X,Y)\) have population distribution \(P\), let \(g\) be a prediction rule, and let \(\ell(g,Z)\) be its loss on one observation. The loss may be squared error, zero-one loss, or another specified loss. For a sample \(Z_1,\ldots,Z_n\), write \(\ell(g,Z_i)\) for the loss on observation \(i\).

Definition: The population risk of a fixed prediction rule \(g\), under loss \(\ell\) and distribution \(P\), is \(R_{\ell,P}(g)=E_P[\ell(g,Z)]\), when this expectation is defined. Given observations \(Z_1,\ldots,Z_n\), its empirical risk is \(\widehat R_{\ell,n}(g)=\frac{1}{n}\sum_{i=1}^n \ell(g,Z_i)\). Population risk averages over the stated population distribution; empirical risk averages over the observed sample.

These quantities use the same loss but generally differ on a particular sample. Empirical risk is a statistic computed from data; population risk is an expectation under \(P\). The distinction is not “training data versus test data”: either data set can be used to compute an empirical average, while population risk remains an expectation over the distribution of interest.

Worked Comparisons

Worked Example: The Sample Ranking Reverses the Population Ranking

Let \(X\) take values \(x_1,x_2,x_3,x_4\), each with probability \(1/4\), and let the label be \(Y=0\) at every value. Use zero-one loss for classifiers that predict either 0 or 1. Classifier \(g_A\) predicts \((0,0,0,1)\) at \((x_1,x_2,x_3,x_4)\); classifier \(g_B\) predicts \((1,1,0,0)\).

The population risk of \(g_A\) is its probability of predicting incorrectly. It is wrong only at \(x_4\), so \(R(g_A)=1/4\). Classifier \(g_B\) is wrong at \(x_1\) and \(x_2\), so \(R(g_B)=2/4=1/2\). Thus \(g_A\) has the lower population risk.

Now suppose the observed sample contains \(x_1\) and \(x_2\), each once. On both observations \(g_A\) is correct and \(g_B\) is wrong. Therefore \(\widehat R_2(g_A)=0/2=0\) and \(\widehat R_2(g_B)=2/2=1\). In this sample the empirical ranking agrees with the population ranking, but it gives a much larger gap: 1 rather than the population gap \(1/2-1/4=1/4\).

If instead the sample contains \(x_4\) twice, the empirical risks are \(\widehat R_2(g_A)=1\) and \(\widehat R_2(g_B)=0\), reversing the population ranking. Such a sample has positive probability under the stated distribution. A sample ranking is evidence about population performance, not its definition.

Excess Risk and Regret Need a Benchmark

Both excess risk and regret are differences in performance, but the comparison object must be stated. In statistical learning, excess risk commonly means the population-risk gap between a rule and the best rule in a specified class. Regret is used more broadly for a gap against a stated benchmark; depending on the setting, that benchmark might be a class optimum, an external rule, or an oracle. Some texts use “regret” for a population excess-risk gap as well. The terms are not distinguished by subtraction alone: the reference point determines what the number means.

Definition: For a class \(\mathcal G\), suppose a minimizer \(g^*_{\mathcal G}\in\mathcal G\) of population risk exists. The excess risk within \(\mathcal G\) of \(g\in\mathcal G\) is \(R(g)-R(g^*_{\mathcal G})\). For a specified benchmark rule \(b\), define the risk regret relative to \(b\) of \(g\) to be \(R(g)-R(b)\). These gaps need not be equal if \(b\) is not the best member of \(\mathcal G\).

Worked Example: One Rule, Two Benchmarks

Let \(Y=0\) with probability 1 and use squared-error loss for constant predictions \(a\), so the loss is \((a-Y)^2\). Take \(\mathcal G=\{a=1,a=2\}\), and consider the external benchmark \(b=0\).

The risks are \(R(1)=(1-0)^2=1\), \(R(2)=(2-0)^2=4\), and \(R(0)=(0-0)^2=0\). The best rule within \(\mathcal G\) is \(a=1\). For \(a=2\), excess risk within \(\mathcal G\) is \(4-1=3\), whereas regret relative to \(b=0\) is \(4-0=4\). For \(a=1\), the within-class excess risk is \(1-1=0\), but regret relative to \(b=0\) is \(1-0=1\).

Neither calculation is wrong. They answer different questions because they use different benchmarks. A claim such as “the regret is 3” is incomplete unless its comparator is identified.

Empirical excess risk uses a different risk function and benchmark: for example, \(\widehat R_n(g)-\inf_{h\in\mathcal G}\widehat R_n(h)\). It is not the same quantity as population excess risk. The empirical minimizer may have zero empirical excess risk and still have positive population excess risk. Nor is an empirical risk itself a regret: regret is a difference from a benchmark.

Two Useful Risk Comparisons

The first fact explains why empirical risk can estimate population risk without being identical to it. Assume \(Z_1,\ldots,Z_n\) are independent and identically distributed with distribution \(P\), \(g\) is fixed independently of this sample, and \(E_P[|\ell(g,Z)|]<\infty\).

Result: Under these assumptions, empirical risk is unbiased for population risk: \(E[\widehat R_n(g)]=R(g)\).

Proof. By linearity of expectation and identical distribution,

E[\widehat R_n(g)] = E\left[\frac{1}{n}\sum_{i=1}^n \ell(g,Z_i)\right] = \frac{1}{n}\sum_{i=1}^n E[\ell(g,Z_i)] = \frac{1}{n}\sum_{i=1}^n R(g) = R(g).

The finite-expectation assumption makes these expectations well-defined. The result concerns a fixed rule. If \(g\) is selected using the same observations, the expectation of its empirical risk need not equal the population risk of that selected rule; the rule and the sample are then dependent. Unbiasedness also does not say that a particular empirical risk equals its population counterpart. \(\square\)

A second comparison gives a deterministic guarantee when every rule in a class has a sufficiently accurate empirical risk. It does not say that such accuracy always holds; it shows what follows if it does.

Result: Suppose \(\widehat g\) minimizes empirical risk over \(\mathcal G\), a population-risk minimizer \(g^*_{\mathcal G}\) exists in \(\mathcal G\), and \(\sup_{g\in\mathcal G}|\widehat R_n(g)-R(g)|\leq\varepsilon\). Then \(R(\widehat g)-R(g^*_{\mathcal G})\leq 2\varepsilon\).

Proof. Add and subtract the empirical risks of both rules. Since \(\widehat g\) minimizes empirical risk, \(\widehat R_n(\widehat g)-\widehat R_n(g^*_{\mathcal G})\leq 0\). The uniform deviation assumption bounds each of the other two differences by \(\varepsilon\):

\begin{aligned} R(\widehat g)-R(g^*_{\mathcal G}) ={}&[R(\widehat g)-\widehat R_n(\widehat g)]\\ &+[\widehat R_n(\widehat g)-\widehat R_n(g^*_{\mathcal G})]\\ &+[\widehat R_n(g^*_{\mathcal G})-R(g^*_{\mathcal G})]\\ \leq{}&\varepsilon+0+\varepsilon =2\varepsilon. \end{aligned}

The conclusion is a bound on population excess risk relative to the best rule in the class. The middle term is nonpositive because of empirical minimization; the other terms control the difference between empirical and population risk. \(\square\)

Surrogate Risk Is Not Target Risk

A surrogate loss is chosen in place of a target loss, often because it has useful mathematical or computational properties. Each loss defines its own risk. Comparing surrogate risks answers which rule performs better under the surrogate; a conclusion about target performance requires an additional relationship between the two risks. In particular, simply minimizing a surrogate over a class does not, by definition, minimize the target risk over that class.

Worked Example: Lower Logistic Risk, Higher Classification Error

Let \(X\) have two values, \(u\) and \(v\), each with probability \(1/2\), and let \(Y=+1\) at both values. A score \(s(X)\) predicts \(+1\) when its score is positive and \(-1\) when its score is negative. Compare target zero-one loss with logistic loss \(\ell_{\mathrm{log}}(s,Y)=\log(1+\exp(-Ys))\).

Rule \(g_A\) gives scores \(s(u)=100\) and \(s(v)=-0.01\). It misclassifies \(v\) only, so its target risk is \(R_{01}(g_A)=1/2\). Its logistic risk is \(R_{\mathrm{log}}(g_A)=\frac12[\log(1+\exp(-100))+\log(1+\exp(0.01))]\).

The first term is approximately \(3.72\times10^{-44}\), and the second is approximately \(0.69816\), giving \(R_{\mathrm{log}}(g_A)\approx0.34908\). Rule \(g_B\) gives score \(0.1\) at both values. It makes no classification errors, so \(R_{01}(g_B)=0\), while \(R_{\mathrm{log}}(g_B)=\log(1+\exp(-0.1))\approx0.64440\).

Thus \(g_A\) has lower logistic risk but higher target risk: \(0.34908<0.64440\), while \(1/2>0\). This comparison of two rules does not establish what happens for every class or every distribution. It demonstrates why a surrogate-risk ranking alone cannot be reported as a target-risk ranking.

Common Mistakes

Calling training risk “the risk.” The reasoning is that the observed average is the quantity calculated, so it must be the population performance. The correction is to label it empirical risk and state the distribution that defines the population risk you care about.
Reporting regret without a comparator. A difference from the best member of a restricted class can differ from a difference against an external benchmark. Name the benchmark and, when relevant, whether the risks are empirical or population risks.
Treating excess risk and regret as universally distinct terms. Their usage overlaps across settings. Define the comparator rather than relying on the label alone.
Equating lower surrogate risk with lower target risk. The surrogate and target use different losses, and their rankings can differ. A transfer claim needs a stated result that connects those particular risks.

Whenever a risk comparison appears, write down the loss, distribution or sample, and benchmark before interpreting the difference. Those details determine whether a statement is about estimation, performance relative to a class, or performance relative to another decision rule.

Check Your Understanding

For each question, identify the relevant risk and benchmark rather than giving an unqualified comparison.

Under what assumptions is empirical risk unbiased for the population risk of a fixed rule?
A rule has zero empirical excess risk within a class. Does this imply zero population excess risk? Explain.
In the squared-error example, why does the rule \(a=1\) have zero within-class excess risk but positive regret relative to \(b=0\)?
What additional condition was used to derive the \(2\varepsilon\) population excess-risk bound for an empirical minimizer?
In the logistic-loss example, which rule has lower target risk, and which has lower surrogate risk?