Localized Complexity for Squared-Error Regression

Regression Error and Excess Loss

In squared-error regression, the prediction error has a useful structure: averaging over the response removes a term that remains present in each individual observation. This separates the population risk, which measures average prediction quality, from the random fluctuations of the observed excess loss. The distinction is central when studying localized complexity: a function can be close to the regression function on average even though its observed losses still fluctuate.

Let \((X,Y)\) be a random pair, with \(Y\) bounded, and define the regression function \(\eta(x)=E[Y\mid X=x]\). We compare predictors \(f\) with \(\eta\), the population squared-error risk minimizer. For the finite-class complexity bound below, assume \(|Y|\le B\) almost surely and \(|f(X)|\le B\) almost surely for every candidate predictor \(f\), where \(B>0\). Conditional expectation then gives \(|\eta(X)|\le B\) almost surely.

Write \(h_f(x)=f(x)-\eta(x)\) for the prediction error and \(\varepsilon=Y-\eta(X)\) for the regression residual. These definitions give an exact pointwise representation of excess loss, not merely an approximation.

Indeed, \(f(X)-Y=h_f(X)-\varepsilon\) and \(\eta(X)-Y=-\varepsilon\). Subtracting their squared losses gives \((h_f-\varepsilon)^2-\varepsilon^2=h_f^2-2\varepsilon h_f\). The first term is nonnegative prediction error; the second is a residual fluctuation whose conditional mean is zero.

Population Excess Risk Is Squared Regression Error

The key population identity follows by conditioning on \(X\). Since \(h_f(X)\) is determined by \(X\) and \(E[\varepsilon\mid X]=0\), the cross-term vanishes in expectation.

Proof. Square-integrability makes the risks finite. The pointwise identity above and conditional expectation give \(E[\varepsilon h_f(X)]=E[h_f(X)E[\varepsilon\mid X]]=0\). Consequently, \(R(f)-R(\eta)=E[g_f(X,Y)]=E[h_f(X)^2]\), as claimed. \(\square\)

This identity also shows why \(\eta\) is a population minimizer: the right-hand side is nonnegative for every \(f\). It does not require \(\eta\) to belong to a proposed candidate class \(\mathcal F\). If the best available predictor is restricted to \(\mathcal F\), its risk need not equal \(R(\eta)\); the identity still measures each candidate's excess risk relative to the unrestricted regression function.

Localized Empirical Complexity

For a sample \((X_i,Y_i)_{i=1}^n\), write \(P_n a=n^{-1}\sum_{i=1}^n a(X_i,Y_i)\) for an empirical average. Localization restricts attention to predictors whose squared prediction error on this sample is small. For radius \(r\ge 0\), define \(\mathcal F_r=\{f\in\mathcal F:P_n h_f^2\le r\}\). The corresponding localized excess-loss class consists of the vectors of observed values \(g_f(X_i,Y_i)\) for \(f\in\mathcal F_r\).

The next bound uses only boundedness, finite class size, and the local empirical squared-error radius. In particular, it does not assert that population localization automatically implies empirical localization; that would require a separate deviation argument.

Proof. Set \(h_i=f(X_i)-\eta(X_i)\) and \(\varepsilon_i=Y_i-\eta(X_i)\). The bounds on \(Y\), \(f(X)\), and \(\eta(X)\) imply \(|h_i|\le 2B\) and \(|\varepsilon_i|\le 2B\). Using the pointwise excess-loss identity, \(|g_f(X_i,Y_i)|=|h_i^2-2\varepsilon_i h_i|\le |h_i|(|h_i|+2|\varepsilon_i|)\le6B|h_i|\). For \(f\in\mathcal F_r\), it follows that \(\sum_{i=1}^n g_f(X_i,Y_i)^2\le36B^2\sum_{i=1}^n h_i^2\le36B^2nr\). Thus every vector in \(\mathcal G_r\) has Euclidean norm at most \(6B\sqrt{nr}\).

For completeness, if a finite set has \(K\) vectors with norms at most \(A\), then \(E_\sigma\max_a n^{-1}\sum_i\sigma_i a_i\le A\sqrt{2\log K}/n\). To see this, for any \(\lambda>0\), the sign moment-generating function satisfies \(E_\sigma\exp(\lambda\sum_i\sigma_i a_i)=\prod_i\cosh(\lambda a_i)\le\exp(\lambda^2\|a\|_2^2/2)\). Applying the log-sum-exp bound to the \(K\) vectors gives an upper bound \(\log(K)/\lambda+\lambda A^2/2\) for the expected unnormalized maximum. Minimizing over \(\lambda\) yields \(A\sqrt{2\log K}\). Include both signs of every vector to control the supremum in the Rademacher definition by an absolute maximum; there are at most \(2M\) such vectors. Substituting \(A=6B\sqrt{nr}\) and dividing by \(n\) proves the stated bound. \(\square\)

The result makes the localization effect explicit: at fixed class size and sample size, the bound decreases proportionally to \(\sqrt r\). It is a bound for the empirical complexity on the observed sample. For a class indexed by infinitely many predictors, one needs additional control of its size or geometry; finiteness cannot simply be dropped from this argument.

What the Bound Does—and Does Not—Say

The excess-loss identity is useful because it identifies the population scale for localization: \(R(f)-R(\eta)=E[h_f(X)^2]\). The finite-class bound then controls the random-sign fluctuations of observed excess-loss vectors when their empirical prediction errors are small. Both pieces are needed to reason about generalization: population curvature describes the target quantity, while empirical complexity describes a sample-dependent fluctuation.

A common mistake is to replace the observed excess loss by squared prediction error pointwise, writing \(g_f(X,Y)=h_f(X)^2\). The omitted term is \(-2\varepsilon h_f(X)\). It has conditional mean zero, but is generally not zero on an observation. The correction is to retain the residual term in empirical calculations and use conditional expectation only when deriving the population identity. A second caution is that the theorem localizes with \(P_n h_f^2\); a bound for predictors selected by \(E[h_f(X)^2]\le r\) requires a separate argument connecting population and empirical averages.