Why the Center of Localization Matters
Localized complexity studies a learning procedure near predictors with small excess risk. Under misspecification, the right center is not necessarily a predictor that matches the data-generating mechanism. It is a predictor that minimizes population risk within the model being considered. Loss differences from this center have nonnegative expectation, but they need not be nonnegative for every observation. That distinction determines both how the excess-loss class is defined and what conclusions can be drawn from it.
There are two distinct sources of risk relative to an ideal benchmark. The model may be unable to attain the benchmark at all; this is approximation error. Even within the model, a predictor selected from finite data may perform worse than the model’s population-risk minimizer; this is within-model excess risk. Localization addresses the second quantity, not the first.
Population Risk, Misspecification, and Excess Loss
Let \(Z\) denote one observation, let \(P\) be its distribution, and let \(\mathcal{M}\) be a nonempty class of predictors. For a measurable loss \(\ell_f(Z)\), assume \(P|\ell_f|<\infty\) for every \(f\in\mathcal{M}\). Write \(R(f)=P\ell_f=E[\ell_f(Z)]\) for population risk. A population-risk minimizer in the model is a fixed \(f_*\in\mathcal{M}\) such that \(R(f_*)=\inf_{f\in\mathcal{M}}R(f)\). We assume this minimum is attained.
The nonnegativity here concerns the expectation \(Pg_f\), not the value \(g_f(z)\) at each observation. A candidate can incur less loss than \(f_*\) on some observations and more loss on others. Under misspecification, there is generally no reason for the differences to have one sign pointwise.
To define approximation error, let \(\mathcal{F}\) be a larger benchmark class containing \(\mathcal{M}\), and suppose the risks in question are finite. The benchmark infimum \(R_{\mathcal{F}}^*=\inf_{f\in\mathcal{F}}R(f)\) need not be attained. The model’s approximation error relative to \(\mathcal{F}\) is \(A_{\mathcal{M}}=R(f_*)-R_{\mathcal{F}}^*\), which is nonnegative when \(\mathcal{M}\subseteq\mathcal{F}\).
Proof. Add and subtract \(R(f_*)\): \(R(f)-R_{\mathcal{F}}^*=[R(f)-R(f_*)]+[R(f_*)-R_{\mathcal{F}}^*]\). The first bracket is \(Pg_f\), and the second is \(A_{\mathcal{M}}\), giving the identity. Both terms are nonnegative. In particular, for a data-dependent \(\hat f\in\mathcal{M}\), the identity holds for each realized value of \(\hat f\); its first term is the within-model excess risk and its second is the fixed approximation error. \(\square\)
Worked Example: Squared-Error Regression With a Restricted Model
Let \(X\) be equally likely to be \(-1\) or \(1\), let \(Y=X+2+\varepsilon\), where \(\varepsilon\) is independent of \(X\), has mean zero, and has variance \(1\). Use squared-error loss \(\ell_f(X,Y)=(Y-f(X))^2\). The model \(\mathcal{M}\) consists only of constant predictors \(f_c(X)=c\), while the benchmark class contains all measurable predictors.
For a constant \(c\), the conditional mean of \(Y\) given \(X\) is \(X+2\). Expanding the squared error and using \(E[\varepsilon\mid X]=0\) gives \(R(f_c)=E[(X+2-c)^2]+1\). Since \(E[X]=0\) and \(E[X^2]=1\), \(E[(X+2-c)^2]=1+(2-c)^2\), so \(R(f_c)=2+(2-c)^2\). The model minimizer is therefore \(c_*=2\), with risk \(R(f_*)=2\).
The benchmark predictor \(f_0(X)=X+2\) has risk \(E[\varepsilon^2]=1\). No predictor can have smaller squared-error risk, since for any \(f\), \(E[(Y-f(X))^2]=E[\varepsilon^2]+E[(X+2-f(X))^2]\geq1\). Thus \(R_{\mathcal{F}}^*=1\) and \(A_{\mathcal{M}}=2-1=1\). For the model predictor \(f_{2.5}\), the within-model excess is \(R(f_{2.5})-R(f_*)=(2.5-2)^2=0.25\). Its total excess over the benchmark is \(2.25-1=1.25=1+0.25\), as the decomposition requires.
More generally, the excess-loss function for \(f_c\) is \(g_{f_c}=(Y-c)^2-(Y-2)^2\), which can be negative for individual observations even though \(Pg_{f_c}=(c-2)^2\geq0\).
Risk-Based Localization
Localization restricts attention to predictors whose population excess risk is small. For \(r\geq0\), define \(\mathcal{G}(r)=\{g_f\in\mathcal{G}:Pg_f\leq r\}\). The class always contains the zero function \(g_{f_*}\). Increasing \(r\) enlarges the class, and \(\mathcal{G}(r)\) is defined by expected risk, not by pointwise closeness of predictors or losses.
For independent observations \(Z_1,\ldots,Z_n\) from \(P\), write \(P_n g=n^{-1}\sum_{i=1}^n g(Z_i)\). The empirical excess loss satisfies \(P_n g_f=P_n\ell_f-P_n\ell_{f_*}\). Thus an empirical risk minimizer over \(\mathcal{M}\) has \(P_n g_{\hat f}\leq0\), provided it attains the empirical minimum. This simple inequality connects localization to empirical-process deviations.
Proof. By population optimality, \(Pg_{\hat f}\geq0\). By empirical optimality, \(P_n g_{\hat f}\leq0\). Therefore \(Pg_{\hat f}=P_n g_{\hat f}+(P-P_n)g_{\hat f}\leq(P-P_n)g_{\hat f}\leq |(P-P_n)g_{\hat f}|\). The condition \(Pg_{\hat f}\leq r\) puts \(g_{\hat f}\) in \(\mathcal{G}(r)\), so its absolute deviation is at most the displayed supremum. \(\square\)
This is a deterministic comparison on the stated event; by itself it does not establish that the supremum is small or that the event \(Pg_{\hat f}\leq r\) holds. Those require additional control of empirical fluctuations. The theorem identifies exactly which fluctuations matter once the selected predictor is known to be in a localized class.
A complementary version gives a sufficient condition for localization. If, for some \(r\geq0\), every \(g\in\mathcal{G}\) with \(Pg>r\) satisfies \(|(P_n-P)g|<Pg\), then every empirical risk minimizer has excess risk at most \(r\). Indeed, such a \(g\) would satisfy \(P_n g=Pg+(P_n-P)g>0\). But an empirical minimizer has \(P_n g_{\hat f}\leq0\), because \(f_*\) is in the model. Hence the minimizer cannot have excess greater than \(r\).
Worked Example: Log Loss and Negative Pointwise Differences
Let \(Y\) be Bernoulli with \(P(Y=1)=0.8\), and consider constant probability predictions \(q\in[0.4,0.6]\) with log loss \(\ell_q(Y)=-Y\log q-(1-Y)\log(1-q)\). The true conditional probability \(0.8\) is outside the model. The risk is \(R(q)=-0.8\log q-0.2\log(1-q)\). Its derivative is \((q-0.8)/(q(1-q))\), which is negative throughout \([0.4,0.6]\); hence the model minimizer is \(q_*=0.6\).
Compare \(q=0.4\) with \(q_*=0.6\). When \(Y=1\), the excess loss is \(-\log(0.4)+\log(0.6)=\log(1.5)\). When \(Y=0\), it is \(-\log(0.6)+\log(0.4)=-\log(1.5)\). Thus the excess loss is negative when \(Y=0\), an event with probability \(0.2\). Its expectation is \(Pg_{q}=0.8\log(1.5)-0.2\log(1.5)=0.6\log(1.5)\), approximately \(0.2433>0\). The model minimizer is better in expectation even though it is worse on some individual observations.
The unrestricted benchmark predicts probability \(0.8\), whose risk is the binary entropy \(-0.8\log(0.8)-0.2\log(0.2)\). The model minimizer’s risk exceeds this by \(0.8\log(0.8/0.6)+0.2\log(0.2/0.4)\), approximately \(0.0915\). This is approximation error; the \(0.2433\) above is instead the excess risk of \(q=0.4\) relative to the model minimizer.
Reading the Localized Empirical Process
A common measure of the fluctuations of a localized class is its empirical Rademacher complexity. Conditional on the observed sample, let \(\sigma_1,\ldots,\sigma_n\) be independent random signs, each equally likely to be \(1\) or \(-1\). Define \(\widehat{\mathfrak{R}}_n(\mathcal{G}(r))=E_\sigma[\sup_{g\in\mathcal{G}(r)} n^{-1}\sum_{i=1}^n\sigma_i g(Z_i)]\). This quantity concerns variation among the loss differences around \(f_*\), not the absolute size of the individual losses. It is one tool for bounding the localized supremum in the theorem; any such bound must also meet the hypotheses of the empirical-process result being applied.
The centering is consequential. If one instead compares every predictor to an ideal predictor outside \(\mathcal{M}\), the resulting differences need not have nonnegative expectation over the model, and the empirical minimizer need not have nonpositive empirical difference relative to that ideal predictor. Centering at \(f_*\) gives both properties directly. Approximation error remains in the overall risk decomposition but is not part of the localized estimation term.
Worked Example: A Finite Class and a One-Observation Selection
Suppose the model contains \(f_*\) and \(f_1\). For every observation, \(f_*\) has loss \(2\). Let \(Z\) take values \(a\) and \(b\) with probability \(1/2\) each; \(f_1\) has loss \(1\) at \(a\) and \(5\) at \(b\). The excess loss \(g_{f_1}\) is therefore \(-1\) at \(a\) and \(3\) at \(b\), with \(Pg_{f_1}=\tfrac12(-1)+\tfrac12(3)=1\). Thus \(f_*\) is the unique population minimizer and \(\mathcal{G}(r)=\{0\}\) for \(0\leq r<1\).
With one observation, if \(Z_1=a\), then \(P_1g_{f_1}=-1<0\), so empirical risk minimization selects \(f_1\), whose population excess risk is \(1\). If \(Z_1=b\), then \(P_1g_{f_1}=3>0\), so it selects \(f_*\). The selection error occurs with probability \(1/2\). For the selected \(f_1\) in the first case, the empirical deviation is \((P-P_1)g_{f_1}=1-(-1)=2\), which is large enough to offset its positive population excess. This illustrates why it is not enough to inspect only a small localized class: one must also control fluctuations that could let a higher-risk candidate enter the empirical minimizer.
Common Pitfall and Practical Interpretation
Wrong reasoning: “Because \(f_*\) minimizes population risk, \(g_f(Z)\geq0\) for every observation. Therefore localized excess losses are nonnegative pointwise.” The minimization only says \(E[g_f(Z)]\geq0\). The log-loss example gives an explicit negative value, and the finite-class example shows that negative observations can make empirical risk favor a population-inferior candidate.
Correction: Keep the pointwise loss difference, its population expectation, and its empirical average distinct. It is \(Pg_f\) that defines the localized class and is nonnegative by population optimality. It is \(P_ng_f\) that is nonpositive at an empirical minimizer. Their gap, \((P-P_n)g_f\), is what must be controlled.
The decomposition also clarifies interpretation. If a model has large approximation error, even perfect estimation of its population minimizer cannot achieve the benchmark risk. Conversely, a small approximation error does not guarantee a good fitted predictor if within-model excess risk remains large. Localized excess-loss analysis isolates that estimation question around the correct model-specific population center, without pretending that misspecification has disappeared.
Check Your Understanding
Answer using the distinction between model risk, benchmark risk, and empirical risk.
- Why must \(Pg_f\geq0\) hold for every \(f\in\mathcal{M}\), and why need not \(g_f(Z)\geq0\) hold for every observation?
- State the exact decomposition of \(R(f)-R_{\mathcal{F}}^*\) into approximation error and within-model excess risk.
- For an empirical risk minimizer, what sign does \(P_ng_{\hat f}\) have, and how does this yield a bound involving \((P-P_n)g_{\hat f}\)?
- In the log-loss example, calculate the probability and value of the outcome on which \(g_{0.4}\) is negative.
- Why does controlling fluctuations only over \(\mathcal{G}(r)\) not automatically prove that the empirical minimizer has excess risk at most \(r\)?