Excess-Loss Classes and Localization Radii

Why Localize an Excess-Loss Class?

A global comparison of predictors includes both candidates that are nearly optimal and candidates whose population risk is far worse than the best available risk. When the question concerns excess risk, those groups need not be equally informative: the empirical fluctuations of nearly optimal candidates are the ones that can affect which predictor is selected near the optimum. Localization makes this distinction explicit by restricting attention according to population excess risk.

This is a restriction on risk, not necessarily on the distance between predictors or on the pointwise size of their losses. A predictor can be close to the optimum in population risk while its loss difference varies substantially across observations. The localized class records which excess-loss functions belong to the comparison; it does not, by itself, say how large their empirical fluctuations are.

Population Risk and Excess Loss

Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$, and let $\mathcal F$ be a class of predictors. For $f\in\mathcal F$, write $\ell_f(z)$ for its loss at observation $z$. Assume each loss is measurable and integrable, so its population risk $R(f)=P\ell_f=E[\ell_f(Z)]$ is finite. Assume also that a population-risk minimizer exists, and select one such minimizer $f^*$, so $R(f^*)=\inf_{f\in\mathcal F}R(f)$.

Definition: The excess loss of $f$ relative to $f^*$ is the function $g_f(z)=\ell_f(z)-\ell_{f^*}(z)$. Its population mean, $Pg_f=E[g_f(Z)]=R(f)-R(f^*)$, is the excess risk. For a radius $r\geq 0$, the localized predictor class and its localized excess-loss class are $$ \mathcal F(r)=\{f\in\mathcal F: R(f)-R(f^*)\leq r\}, \qquad \mathcal G(r)=\{g_f:f\in\mathcal F(r)\}. $$

The radius is measured in the units of the risk: for example, squared-error units under squared-error loss or probability units under a zero-one loss. It is not a radius in a parameter norm, a prediction metric, or a sample-dependent distance. Since $f^*$ is a minimizer, $Pg_f\geq 0$ for every $f$, and $f^*\in\mathcal F(r)$ for every $r\geq 0$. If $0\leq r_1\leq r_2$, then $\mathcal F(r_1)\subseteq\mathcal F(r_2)$ and $\mathcal G(r_1)\subseteq\mathcal G(r_2)$.

The nonnegativity just noted is a statement about the mean excess loss. In general, $g_f(z)$ can be negative for particular observations: a predictor with worse average risk can outperform $f^*$ on some outcomes. Localization keeps functions according to $Pg_f$, not according to whether $g_f(z)$ is nonnegative at every $z$.

Worked Example: A Two-Predictor Classification Class

Let $Y\in\{0,1\}$, with $P(Y=1)=0.2$, and suppose $X$ is constant. The two available predictors always predict 0 or always predict 1, with zero-one loss $\ell_f(X,Y)=\mathbf 1\{f(X)\ne Y\}$. Find their risks and the localized classes.

The constant-0 predictor has risk $P(Y=1)=0.2$; the constant-1 predictor has risk $P(Y=0)=0.8$. Thus $f^*$ is the constant-0 predictor. For the constant-1 predictor $f_1$, its excess loss is $$ g_{f_1}(X,Y)=\mathbf 1\{Y=0\}-\mathbf 1\{Y=1\}=1-2Y, \qquad Pg_{f_1}=1-2(0.2)=0.6. $$

For any $0\leq r<0.6$, $\mathcal F(r)$ contains only the constant-0 predictor, and $\mathcal G(r)$ contains only the zero function. At $r=0.6$, both predictors enter the localized class, and $\mathcal G(r)$ contains both 0 and $1-2Y$. The nonzero excess-loss function takes the value 1 when $Y=0$ and $-1$ when $Y=1$, even though its expectation is the positive number 0.6.

Empirical Excess Risk and Its Fluctuation

For any integrable function $h$, define its empirical average $P_nh=n^{-1}\sum_{i=1}^n h(Z_i)$. The empirical excess risk of $f$, measured relative to the same reference predictor $f^*$, is $P_ng_f$. It can differ from the population excess risk $Pg_f$ because the observed sample need not represent the population exactly. That difference is the centered empirical fluctuation $(P_n-P)g_f=P_ng_f-Pg_f$.

Theorem: For every $f\in\mathcal F$, $$ P_n\ell_f-P_n\ell_{f^*} = R(f)-R(f^*)+(P_n-P)g_f. $$ Consequently, the empirical comparison with $f^*$ equals the population excess risk plus the fluctuation of the corresponding excess loss.

Proof. By the definition $g_f=\ell_f-\ell_{f^*}$, linearity of empirical averaging gives $P_n\ell_f-P_n\ell_{f^*}=P_ng_f$. By definition of the centered fluctuation, $P_ng_f=Pg_f+(P_n-P)g_f$. Finally, $Pg_f=R(f)-R(f^*)$. Substituting this equality proves the identity. $\square$

This identity explains why low-excess-risk candidates are a natural target: the empirical comparison for each candidate has a deterministic population component and a random fluctuation. If one is studying predictors with $Pg_f\leq r$, it is the fluctuations for $g_f\in\mathcal G(r)$ that describe the sample variation within that risk region. A global class also includes functions for candidates far from optimal, whether or not their fluctuations are relevant to that particular comparison.

Worked Example: Squared-Error Loss for Constant Predictors

Let $Y\sim N(0,1)$, let predictors be constants $a\in\mathbb R$, and use squared-error loss $\ell_a(Y)=(Y-a)^2$. Determine the localized predictor class and calculate the empirical fluctuation at $a=0.5$.

Expanding the square and using $E[Y]=0$ and $E[Y^2]=1$ gives $$ R(a)=E[(Y-a)^2]=E[Y^2]-2aE[Y]+a^2=1+a^2. $$ The minimizing constant is $a^*=0$, with risk 1. The excess loss and its mean are $$ g_a(Y)=(Y-a)^2-Y^2=a^2-2aY, \qquad Pg_a=a^2. $$ Therefore $\mathcal F(r)=\{a:a^2\leq r\}=[-\sqrt r,\sqrt r]$, and $\mathcal G(r)=\{a^2-2aY:|a|\leq\sqrt r\}$.

At $a=0.5$, $g_{0.5}(Y)=0.25-Y$, so $Pg_{0.5}=0.25$. The empirical fluctuation is $$ (P_n-P)g_{0.5} = \left(0.25-\frac{1}{n}\sum_{i=1}^nY_i\right)-0.25 = -\overline Y, $$ where $\overline Y=n^{-1}\sum_{i=1}^nY_i$. Since the observations are independent with variance 1, $\operatorname{Var}(\overline Y)=1/n$, and hence $\operatorname{Var}((P_n-P)g_{0.5})=1/n$. The predictor $a=0.5$ belongs to the localized class exactly when $r\geq 0.25$. Notice that its excess loss $0.25-Y$ can be negative even though its excess risk is positive.

A Localized Deviation Statement

The next elementary result makes the role of a localized fluctuation precise. Assume the relevant suprema below are measurable and finite; this condition avoids technical issues about taking suprema over an uncountable class. Define $$ \Delta_n(r)=\sup_{g\in\mathcal G(r)} |(P_n-P)g|. $$

Theorem: For every $f\in\mathcal F(r)$, $$ Pg_f-\Delta_n(r)\leq P_ng_f\leq Pg_f+\Delta_n(r). $$ If $\hat f_r$ minimizes empirical risk over $\mathcal F(r)$, then $$ R(\hat f_r)-R(f^*)\leq\Delta_n(r). $$

Proof. Because $f\in\mathcal F(r)$, its excess loss belongs to $\mathcal G(r)$, so $|(P_n-P)g_f|\leq\Delta_n(r)$. Writing $P_ng_f=Pg_f+(P_n-P)g_f$ and applying the two sides of this absolute-value bound gives the first pair of inequalities.

For the second claim, $f^*\in\mathcal F(r)$, and empirical minimization over that set therefore gives $P_n\ell_{\hat f_r}\leq P_n\ell_{f^*}$, or $P_ng_{\hat f_r}\leq0$. The first inequality already proved, applied to $\hat f_r$, gives $Pg_{\hat f_r}-\Delta_n(r)\leq P_ng_{\hat f_r}\leq0$. Rearranging yields $R(\hat f_r)-R(f^*)=Pg_{\hat f_r}\leq\Delta_n(r)$. $\square$

The result is deliberately conditional on minimizing over the specified localized set. It does not assert that a global empirical risk minimizer must lie in $\mathcal F(r)$, nor does it bound $\Delta_n(r)$. It identifies the quantity that controls empirical comparisons inside the risk region. Estimating or bounding that quantity is a separate task.

Worked Example: Nonunique Population Minimizers

Return to the two constant predictors under zero-one loss, but now let $P(Y=1)=P(Y=0)=0.5$. Both predictors have risk 0.5, so either can be selected as $f^*$. Describe what changes when the reference minimizer changes.

If $f^*$ is the constant-0 predictor, the constant-1 predictor has excess loss $g_1(Y)=1-2Y$, whose expectation is $1-2(0.5)=0$. If instead $f^*$ is the constant-1 predictor, the constant-0 predictor has excess loss $g_0(Y)=2Y-1=-g_1(Y)$, also with expectation zero.

Thus for every $r\geq0$, both predictors are in $\mathcal F(r)$, regardless of the selected minimizer. But the functions used to represent their loss differences depend on that choice: switching the reference reverses the sign of the nonzero difference. At a given sample, the empirical fluctuation can therefore have the opposite sign. The risk-based set of predictors is unchanged; the anchored excess-loss class need not be.

Interpreting the Radius and Avoiding Pitfalls

A radius $r$ expresses how much population risk above the minimum is allowed into the comparison. Increasing $r$ can only add predictors and excess-loss functions. A small radius focuses attention near the optimal risk value; a large radius moves toward the full class. The choice of radius does not assert that every included predictor is equally likely to be selected, and it does not guarantee that the class has small fluctuations.

A common mistake is to treat localization as restricting predictors that are close to $f^*$ in parameter space. The definition instead uses $R(f)-R(f^*)\leq r$. If a parameter distance is useful in a particular model, a separate argument must relate that distance to excess risk. Another mistake is to assume that every excess-loss function is pointwise nonnegative because its expectation is nonnegative. The squared-error and classification examples show why that conclusion is false: excess loss is a difference of losses and can change sign across observations.

Finally, the reference $f^*$ is a population minimizer, not a minimizer chosen after examining the sample. If there are several population minimizers, state which one anchors $g_f$. The set of predictors with excess risk at most $r$ is well defined using the minimum risk, while the functions in the anchored excess-loss class can depend on the chosen reference.

Key takeaway: Localization forms a nested family of excess-loss classes by retaining predictors whose population risk is within $r$ of the minimum. Empirical comparisons decompose into excess risk and centered fluctuation; localization specifies which fluctuations are relevant to a chosen risk region, without itself bounding them.

Check Your Understanding

Use the definitions and calculations in this tutorial to answer the following questions.

Why is $Pg_f\geq0$ for every predictor, even though $g_f(z)$ may be negative for some observations?
In the constant-predictor squared-error example, which values of $a$ belong to $\mathcal F(r)$ when $r=0.09$?
State the empirical excess-risk decomposition and identify its population and sample-fluctuation terms.
Does increasing the risk radius remove any predictors from the localized class? Explain.
If there are two population-risk minimizers, which part of the localization construction can depend on the selected reference minimizer?