Critical Radii for Bounded Linear Predictors

Why Localize a Linear Predictor Class?

A linear predictor class can be large globally but much smaller near a reference predictor. Localized complexity quantifies the size of just those predictors whose predictions are close to the reference in population mean square. For bounded linear models, this calculation connects directly to the geometry of the feature distribution: the relevant dimension is the rank of its second-moment matrix, not necessarily the ambient number of coefficients.

We first bound prediction complexity, then show how the bound controls localized squared-loss complexity. The resulting fixed-point scale is a complexity calculation; turning it into an excess-risk guarantee requires the applicable fixed-point theorem and its hypotheses. For squared-error risk, a particularly direct interpretation is available when the reference predictor is the conditional mean.

Model and Localized Complexity

Let \(X\) be a random input with feature vector \(\phi(X)\in\mathbb{R}^d\). Suppose \(\|\phi(X)\|_2\le R\) almost surely. For a coefficient vector \(w\), define \(f_w(X)=w^\top\phi(X)\), and restrict coefficients to \(\|w\|_2\le B\). Thus every predictor is bounded in absolute value by \(BR\).

Fix a reference coefficient \(w_*\) in this set. The difference between \(f_w\) and \(f_{w_*}\) is \(u^\top\phi(X)\), where \(u=w-w_*\) and \(\|u\|_2\le 2B\). We localize by the population squared prediction distance.

The equality \(u^\top\Sigma u=E[(u^\top\phi(X))^2]\) shows what the radius means. The matrix is uncentered: its rank counts directions with nonzero population second moment, equivalently directions whose feature projection is not identically zero almost surely. A constant nonzero feature can therefore contribute, even though it has zero variance.

Two Bounds for Prediction Complexity

The localized term depends on the number of feature directions with nonzero second moment. The global term uses the coefficient-radius constraint and the total feature second moment. Either can be more useful, so the minimum is the informative bound.

Proof. Write \(Z=\sum_{i=1}^n\epsilon_i\phi(X_i)\). Let \(\Sigma^\dagger\) denote the Moore–Penrose pseudoinverse. If \(v\) lies in the kernel of \(\Sigma\), then \(E[(v^\top\phi(X))^2]=v^\top\Sigma v=0\). A nonnegative random variable with expectation zero is zero almost surely, so \(v^\top\phi(X)=0\) almost surely. Because the kernel is finite-dimensional, this holds simultaneously for a basis of it, and therefore \(\phi(X)\) lies in the range of \(\Sigma\) almost surely. The same is true of \(Z\).

For \(u\in T_r\), the Cauchy–Schwarz inequality applied on the range of \(\Sigma\) gives \(u^\top Z=(\Sigma^{1/2}u)^\top(\Sigma^{\dagger/2}Z)\le\sqrt{u^\top\Sigma u}\sqrt{Z^\top\Sigma^\dagger Z}\le r\sqrt{Z^\top\Sigma^\dagger Z}\). Consequently, Jensen's inequality yields \(\mathcal{R}_n(r)\le (r/n)\sqrt{E[Z^\top\Sigma^\dagger Z]}\). On expanding the quadratic form, terms with distinct sample indices have expectation zero because the signs are independent and mean zero. The diagonal terms give \(E[Z^\top\Sigma^\dagger Z]=nE[\phi(X)^\top\Sigma^\dagger\phi(X)]=n\operatorname{tr}(\Sigma^\dagger\Sigma)=nq\). Thus \(\mathcal{R}_n(r)\le r\sqrt{q/n}\).

For the global bound, \(\|u\|_2\le2B\) implies \(u^\top Z\le2B\|Z\|_2\), so \(\mathcal{R}_n(r)\le(2B/n)E\|Z\|_2\le(2B/n)\sqrt{E\|Z\|_2^2}\). Again the cross terms vanish after averaging over the signs, and \(E\|Z\|_2^2=n\operatorname{tr}(\Sigma)\). This proves the second bound. Finally, \(\operatorname{tr}(\Sigma)=E\|\phi(X)\|_2^2\le R^2\). \(\square\)

From Prediction Distance to Squared-Loss Complexity

Suppose the response satisfies \(|Y|\le M\) almost surely and use squared loss \(\ell_w(X,Y)=(f_w(X)-Y)^2\). Consider the localized loss increments \(g_u(X,Y)=\ell_{w_*+u}(X,Y)-\ell_{w_*}(X,Y)\), for \(u\in T_r\) such that \(w_*+u\) is in the coefficient ball. The coefficient restriction ensures both predictors are bounded by \(BR\).

Derivation. For fixed \((x,y)\), put \(t=u^\top\phi(x)\). The loss increment is \(h_{x,y}(t)=(f_{w_*}(x)+t-y)^2-(f_{w_*}(x)-y)^2\), which satisfies \(h_{x,y}(0)=0\). On the feasible predictors, its derivative with respect to \(t\) is \(2(f_{w_*}(x)+t-y)\). Since \(f_{w_*}(x)+t=f_{w_*+u}(x)\), the absolute derivative is at most \(2(BR+M)\). Thus \(h_{x,y}\) is Lipschitz on the feasible interval with constant \(2(BR+M)\), by the mean value theorem. The Rademacher contraction inequality, in its version with factor 2, bounds the expected supremum for these increments by twice this Lipschitz constant times the prediction complexity. Substitution gives \(4(BR+M)\mathcal{R}_n(r)\), and the theorem supplies the final inequality.

The associated fixed-point comparison is between a squared prediction radius \(r^2\) and the upper bound \(A r\sqrt{q/n}\), where \(A=4(BR+M)\). Equating these quantities for \(r>0\) gives the complexity scale \(r_{\mathrm{crit}}=A\sqrt{q/n}\), with squared scale \(r_{\mathrm{crit}}^2=A^2q/n\). This is a scale obtained from the complexity inequality, not by itself a risk theorem. It is an interior localization scale only when it is no larger than the available prediction diameter; otherwise this bound does not identify a smaller radius.

When the Radius Is an Excess-Risk Scale

A prediction radius is not automatically an excess-risk radius. One useful case is squared-error regression with \(f_{w_*}(X)=E[Y\mid X]\) almost surely and \(w_*\) in the coefficient ball. For every predictor \(f_w\), expansion of the square gives \(E[(f_w(X)-Y)^2-(f_{w_*}(X)-Y)^2]=E[(f_w(X)-f_{w_*}(X))^2]\). Indeed, the cross term is \(2E[(f_w-f_{w_*})(f_{w_*}-Y)]\), which is zero by conditioning on \(X\), since \(E[f_{w_*}-Y\mid X]=0\). In this well-specified case, squared prediction distance equals excess risk, so the critical squared scale has an excess-risk interpretation.

Without that conditional-mean condition, the cross term need not vanish. Even if \(w_*\) minimizes risk over the coefficient ball, misspecification means one must not silently identify risk excess with prediction distance. The localized complexity bound remains valid, but a risk conclusion needs the appropriate curvature or fixed-point conditions.

Common Pitfalls and Practical Interpretation

• Using covariance rank in place of second-moment rank. The matrix here is \(E[\phi\phi^\top]\), not the centered covariance matrix. A constant feature equal to one has zero variance but second moment one, and its direction contributes.
• Dropping directions merely because they do not vary. Only directions whose feature projection is identically zero almost surely are absent from the prediction process. A constant nonzero projection is not absent.
• Confusing ambient and effective dimension. The localized bound uses \(q=\operatorname{rank}(\Sigma)\); the trace bound uses total second moment. Small but nonzero eigenvalues still count in \(q\), so the localized rank bound can be conservative.
• Calling a fixed point a theorem about risk. Solving \(r^2=A r\sqrt{q/n}\) identifies a scale from the complexity upper bound. A guarantee for an estimator requires the relevant generalization result and its assumptions; an excess-risk interpretation also needs a link between prediction distance and risk.

The practical value of the calculation is that it separates three sources of scale: localization through \(r\), feature geometry through rank or trace, and loss sensitivity through \(BR+M\). When \(q\) is much smaller than \(d\), the localized bound can reflect a lower-dimensional prediction space. When the feature distribution is concentrated unevenly, the global trace bound may improve the result instead.