Excess Risk Relative to a Benchmark

Why Excess Risk Needs a Benchmark

A prediction risk is an absolute measure of expected loss under a particular data distribution. Excess risk answers a different question: how much worse is this predictor than the best risk available within a specified class? The class matters. A predictor can be close to the best member of a restricted class but far from the best member of a larger one.

This makes excess risk a relative quantity, not an intrinsic score attached to a predictor by itself. To interpret it, we must identify the population distribution, the loss, and the benchmark class. We must also check whether the predictor being evaluated belongs to that class; membership determines whether nonnegativity is guaranteed.

Definition

Let \(P\) be the distribution of an observation \((X,Y)\), let \(\lambda(y,a)\) be a nonnegative loss for predicting \(a\) when the response is \(y\), and let \(g\) be a measurable prediction function. Its population risk is

R_P(g)=E_P[\lambda(Y,g(X))].

Assume the risks under discussion are finite. A benchmark class \(\mathcal H\) is a nonempty specified set of measurable prediction functions. Its benchmark risk is the infimum of population risk over that class.

R_P(\mathcal H)=\inf_{h\in\mathcal H}R_P(h).

Provided \(R_P(\mathcal H)\) is finite, the excess risk of a finite-risk predictor \(g\) relative to \(\mathcal H\) is

\mathcal E_P(g;\mathcal H) = R_P(g)-R_P(\mathcal H) = R_P(g)-\inf_{h\in\mathcal H}R_P(h).

Definition: Excess risk relative to \(\mathcal H\) is the difference between a predictor’s population risk and the infimum population risk in the specified benchmark class. It is defined only after the distribution, loss, and benchmark class have been fixed.

The benchmark is an infimum, not necessarily a minimum. There may be no \(h\in\mathcal H\) whose risk equals \(R_P(\mathcal H)\), even though members of the class can get arbitrarily close to it. The difference is still well-defined when the infimum is finite.

Worked Example: A Two-Predictor Benchmark

Suppose \(Y=1\) with probability one, \(X\) is constant, and the loss is squared error, \(\lambda(y,a)=(y-a)^2\). Consider constant predictors \(g_0(x)=0\) and \(g_1(x)=1\), and use \(\mathcal H=\{g_0,g_1\}\) as the benchmark.

For \(g_0\), the loss is always \((1-0)^2=1\), so \(R_P(g_0)=1\). For \(g_1\), the loss is always \((1-1)^2=0\), so \(R_P(g_1)=0\). Thus the benchmark risk is

R_P(\mathcal H)=\inf\{1,0\}=0.

The excess risk of \(g_0\) is \(1-0=1\), while the excess risk of \(g_1\) is \(0-0=0\). Both predictors belong to the benchmark class, and neither has negative excess risk.

When Is Excess Risk Nonnegative?

If \(g\) belongs to \(\mathcal H\), its risk is one of the values over which the infimum is taken. It therefore cannot be smaller than that infimum. This elementary observation gives the key sign property.

Theorem: Fix \(P\) and a nonnegative loss. Let \(\mathcal H\) be nonempty, with finite benchmark risk, and let \(g\) have finite risk. If \(g\in\mathcal H\), then \(\mathcal E_P(g;\mathcal H)\geq 0\). Equality holds exactly when \(R_P(g)=R_P(\mathcal H)\).

Proof. By definition, \(R_P(\mathcal H)=\inf_{h\in\mathcal H}R_P(h)\). Since \(g\in\mathcal H\), the value \(R_P(g)\) is among the risks over which this infimum is taken. Hence \(R_P(\mathcal H)\leq R_P(g)\), and subtracting the former from the latter gives \(\mathcal E_P(g;\mathcal H)\geq0\). The difference is zero exactly when the two risks are equal. \(\square\)

This result does not say that excess risk is nonnegative for every predictor. If \(g\notin\mathcal H\), its risk is not one of the values defining the benchmark. It may be lower than every risk in that class, in which case the difference is negative. That sign is mathematically valid: it says the predictor beats the chosen benchmark. It does not indicate an error in subtraction.

Worked Example: A Predictor Outside the Benchmark

Again let \(Y=1\) with probability one and use squared error. This time let the benchmark contain only the constant predictor \(h_2(x)=2\), so \(\mathcal H=\{h_2\}\). Evaluate the constant predictor \(g_1(x)=1\), which is not in \(\mathcal H\).

The candidate has risk \(R_P(g_1)=(1-1)^2=0\). The benchmark predictor has risk \(R_P(h_2)=(1-2)^2=1\), so \(R_P(\mathcal H)=1\). Therefore

\mathcal E_P(g_1;\mathcal H)=0-1=-1.

The negative value means that \(g_1\) has lower population risk than every predictor in this benchmark. The theorem does not apply because \(g_1\notin\mathcal H\).

How the Benchmark Changes the Quantity

Even when the distribution, loss, and evaluated predictor stay fixed, changing the benchmark can change the excess risk. A restricted class sets a different standard from a class that contains more candidate predictors. The following result makes this comparison precise.

Theorem: Suppose \(\mathcal H_1\subseteq\mathcal H_2\), both classes are nonempty, and their benchmark risks are finite. For any finite-risk predictor \(g\), \(\mathcal E_P(g;\mathcal H_1)\leq\mathcal E_P(g;\mathcal H_2)\).

Proof. Every risk value obtained from \(\mathcal H_1\) is also obtained from \(\mathcal H_2\), because \(\mathcal H_1\subseteq\mathcal H_2\). Taking the infimum over the larger set cannot increase the infimum, so \(R_P(\mathcal H_2)\leq R_P(\mathcal H_1)\). Subtracting these quantities from the same finite number \(R_P(g)\) reverses their order:

R_P(g)-R_P(\mathcal H_1) \leq R_P(g)-R_P(\mathcal H_2).

These are the two excess risks in the claimed inequality. \(\square\)

The result applies whether or not \(g\) belongs to either class. For a predictor that belongs to both, each excess risk is nonnegative, and the larger class provides a standard that is at least as demanding in this sense. For a predictor outside one or both classes, the values may be negative, but the ordering still holds.

Worked Example: Expanding the Benchmark

Let \(Y=1\) with probability one, use squared error, and evaluate \(g_0(x)=0\), whose risk is \(1\). First take \(\mathcal H_1=\{g_0\}\). Its benchmark risk is \(1\), so \(\mathcal E_P(g_0;\mathcal H_1)=1-1=0\).

Now enlarge the benchmark to \(\mathcal H_2=\{g_0,g_1\}\), where \(g_1(x)=1\). Its benchmark risk is \(\min\{1,0\}=0\), so \(\mathcal E_P(g_0;\mathcal H_2)=1-0=1\). The class has expanded, and the excess risk of the same predictor has increased from \(0\) to \(1\), as the nesting result predicts.

The predictor did not change, and neither did its risk. Only the benchmark changed: it now includes a predictor with lower risk.

An Infimum Need Not Be Achieved

A zero benchmark risk does not imply that some predictor in the class has risk zero. For example, a class can exclude its limiting best predictor. Excess risk is defined using the infimum, so it remains meaningful in this situation; a claim that a particular class member is “the best” would not.

Worked Example: A Benchmark With No Best Member

Let \(Y=0\) with probability one, let \(X\) be constant, and use squared error. Let \(\mathcal H\) consist of all constant predictors \(h_a(x)=a\) with \(a>0\). Each risk is

$$ R_P(h_a)=(0-a)^2=a^2. $$

Every \(a>0\) gives \(a^2>0\), so no member has risk zero. But for every \(\varepsilon>0\), choosing \(a=\sqrt{\varepsilon}/2\) gives \(a>0\) and \(R_P(h_a)=\varepsilon/4<\varepsilon\). Risks are nonnegative, so these facts imply \(\inf_{h\in\mathcal H}R_P(h)=0\), and the infimum is not attained.

For the constant predictor \(g(x)=1\), \(R_P(g)=1\). Its excess risk relative to this class is \(1-0=1\). The definition needs the infimum, not a class member that achieves it.

Common Mistakes and Interpretation

Calling every excess risk nonnegative. Nonnegativity follows when the evaluated predictor belongs to the benchmark class. Outside the class, its risk can be below the benchmark infimum.
Leaving the class unnamed. The difference \(R_P(g)-R_P(\mathcal H)\) depends on \(\mathcal H\). A reported excess risk without its benchmark is incomplete.
Assuming the benchmark is attained. An infimum need not be the risk of any member. Do not refer to a best member unless attainment has been established.
Changing the predictor and benchmark at once. To understand why an excess-risk value changed, keep track of whether the predictor, distribution, loss, or class changed. The nested-class result compares classes with \(P\), loss, and \(g\) held fixed.
Confusing population risk with observed-data loss. This definition uses expected loss under \(P\). A difference formed from observed losses is a different quantity, not this population excess risk.

Excess risk is useful because it reports performance against a stated standard rather than in isolation. Its value can be interpreted only in relation to that standard. Whenever it is reported, identify the distribution and loss being used, the evaluated predictor, and the benchmark class; then state whether the predictor belongs to that class.

Check Your Understanding

Answer each question using the definitions and results above.

What condition on \(g\) guarantees that its excess risk relative to \(\mathcal H\) is nonnegative?
Can a predictor outside \(\mathcal H\) have negative excess risk? What does that sign mean?
If \(\mathcal H_1\subseteq\mathcal H_2\), which benchmark gives the larger or equal excess risk for a fixed predictor?
Why can excess risk be defined even when no member of the benchmark class attains its infimum risk?
If the benchmark is changed but the predictor, distribution, and loss remain fixed, which part of the excess-risk definition changes?