Bayes Risk and Excess-Risk Decomposition

From Population Risk to Conditional Regret

A prediction rule can have risk above the best risk achievable from the available information. To understand that difference, it helps to examine each feature value separately. At a given value of the features, the conditional risk measures the rule’s expected loss; the minimum conditional risk is the best such value any available action can attain there. Their difference is the rule’s conditional regret.

Averaging those pointwise differences gives the excess-risk decomposition. It identifies exactly how much risk a fixed prediction rule incurs beyond the best rule based on the same features. The decomposition does not, by itself, say why the predictor is suboptimal: the gap might arise from the rule being deliberately poor, from a restricted class of rules, or from a learning procedure. The minimum risk is a separate quantity, determined by the prediction problem itself.

Conditional Risk and Bayes Risk

Let \(X\) be the observed features, \(Y\) the outcome, and \(\mathcal{A}\) the action space. A prediction rule \(g\) maps the observed features to an action, so its prediction is \(g(X)\). Write \(L(Y,a)\) for the loss incurred when the outcome is \(Y\) and the chosen action is \(a\). The population risk of a fixed rule is \(R(g)=E[L(Y,g(X))]\).

Assume a conditional distribution of \(Y\) given \(X=x\) is available, and define \(r(x,a)=E[L(Y,a)\mid X=x]\), a version of the conditional risk. The pointwise minimum of this risk over actions is \(m(x)=\inf_{a\in\mathcal{A}}r(x,a)\). When a measurable rule \(g^*\) attains that minimum, it is a Bayes rule: \(r(x,g^*(x))=m(x)\) for almost every feature value under the distribution of \(X\).

The terms in this definition are well behaved under standard measurability and integrability conditions. For example, suppose the feature and outcome spaces are standard Borel, the loss is measurable and nonnegative, and the conditional risk and its pointwise infimum are measurable. Assume also that a measurable Bayes rule exists and has finite risk. For the decomposition below, take \(g\) to be a measurable rule with finite risk. These conditions ensure the conditional expectations are defined and avoid subtracting infinite risks.

The Excess-Risk Decomposition

Proof. First, conditional expectation gives

For any measurable rule \(h\), the definition of the pointwise infimum gives \(r(X,h(X))\geq m(X)\) almost surely. Taking expectations yields \(R(h)\geq E[m(X)]\). For the measurable Bayes rule \(g^*\), equality holds almost surely, so \(R(g^*)=E[m(X)]\). Thus the infimum population risk is \(R^*=E[m(X)]\). Applying the same conditional-expectation identity to \(g\), and subtracting the finite quantity \(E[m(X)]\), gives

The integrand is nonnegative by the definition of \(m\), proving the final claim. \(\square\)

This result is a population identity: it concerns the risk of a fixed rule under the joint distribution of \(X\) and \(Y\). If a rule is produced by a random training sample, the identity can be applied conditional on that training sample when the sample is independent of a fresh test pair and the required risks are finite. It should not be confused with a decomposition of empirical error or with a guarantee about how a learning algorithm finds a good rule.

When Is Excess Risk Zero?

The decomposition also characterizes optimality. Since conditional regret is nonnegative, its expectation is zero exactly when it is zero almost surely. Thus an optimal rule must choose a conditionally minimizing action for almost every feature value. If the minimizing action is unique almost surely, this further implies that any optimal rule agrees with the Bayes rule almost surely. If there are multiple minimizing actions, different rules may attain the same risk.

Proof. By the decomposition, \(R(g)-R^*=E[D]\), where \(D=r(X,g(X))-m(X)\geq 0\) almost surely. If \(D=0\) almost surely, then \(E[D]=0\), so \(R(g)=R^*\). Conversely, if \(R(g)=R^*\), then \(E[D]=0\). A nonnegative random variable with expectation zero equals zero almost surely: for every positive integer \(k\), \(P(D\geq 1/k)\leq kE[D]=0\); and \(\{D>0\}=\bigcup_{k=1}^{\infty}\{D\geq 1/k\}\). Hence \(P(D>0)=0\). When the minimizing action is unique, choosing an action with conditional risk \(m(X)\) requires choosing that unique action, which proves the final statement. \(\square\)

When Bayes Risk Is Irreducible

Bayes risk is often called irreducible prediction error, but the phrase needs a reference point. Given a specified outcome distribution, loss, and set of observed features, \(R^*\) is the smallest population risk any rule based on those features can attain. No improvement in the rule alone can push risk below it. In this precise sense, the Bayes risk is irreducible relative to that prediction problem.

It is not necessarily an unavoidable error under every possible information set or every loss. More informative features can change the conditional outcome distribution and lower the minimum risk. A different loss changes the conditional risks and may change the minimum, too. Moreover, Bayes risk can be zero when the outcome is perfectly predictable under the chosen loss. The decomposition identifies a floor for a specified problem; it does not assert that the floor is positive or universal.

Common Pitfall

A common mistake is to interpret the decomposition as saying that all excess risk is “noise,” or that the Bayes risk is always positive and impossible to affect. The identity says something narrower: for a fixed rule, its excess risk is the expectation of its conditional regret under a specified distribution, loss, and information set. Conditional regret is zero for a Bayes rule; Bayes risk is the minimum risk attainable using the specified information.

To use the identity correctly, keep the two quantities separate. The excess risk measures how far a particular rule is from conditional minimization. The Bayes risk measures the minimum risk itself. Changing the rule can reduce the first quantity, while changing the loss or the information available can change the second.