Nonparametric Least Squares and Rates of Convergence
Least squares chooses a function that fits the observations, but the fitted function also responds to the noise. The basic inequality compares its error with a noise inner product. Bounding that inner product over functions near the truth leads to localized Gaussian complexity and a critical radius. We derive this connection for fixed design and use it to calculate prediction rates for several classes.
Fix design points \(x_1,\ldots,x_n\), and suppose \(Y_i=f^*(x_i)+\sigma g_i\), where \(g_i\) are independent standard normals and \(\sigma>0\). Write \(\|h\|_n^2=n^{-1}\sum_i h(x_i)^2\). Assume \(f^*\in\mathcal F\) and that a measurable least-squares minimizer exists. It is enough to work with the evaluation vectors in \(\mathbb R^n\); closed prediction sets attain the minimum. For convex closed prediction sets the fitted vector is unique. The bounds concern prediction at the given design, not automatically the population \(L^2(P)\) error.
Example 1 (Linear regression). For \(f_\beta(x)=\langle\beta,x\rangle\) and a compact coefficient set \(C\), minimizing empirical loss is exactly minimizing \(n^{-1}\|Y-X\beta\|_2^2\) over \(C\). Compactness guarantees attainment; convexity of \(C\), when assumed, makes \(\mathcal F-f^*\) star-shaped. Unrestricted linear regression instead works on the closed subspace \(\operatorname{range}(X)\), whether or not the coefficient representation is unique.
Example 2 (Kernel ridge regression). In an RKHS \(\mathcal H\) with kernel \(K\), minimize
Decompose \(f=f_0+f_\perp\) with \(f_0\) in the span of \(K(x_i,\cdot)\). The reproducing identity gives \(f_\perp(x_i)=0\), whereas \(\|f\|_{\mathcal H}^2=\|f_0\|_{\mathcal H}^2+\|f_\perp\|_{\mathcal H}^2\). Therefore the unique minimizer lies in this finite span. If \(K_n=(K(x_i,x_j))\), one representation is \(\widehat f=\sum_i\alpha_iK(x_i,\cdot)\), with \(\alpha=(K_n+n\lambda I)^{-1}Y\). Substitution verifies the normal equation \(K_n(K_n+n\lambda I)\alpha=K_nY\), including singular \(K_n\). This is a penalized estimator; Theorem 5 below concerns the constrained estimator with the displayed basic inequality.
Example 3 (Cubic smoothing splines). On \([0,1]\), take the Sobolev space \(W^{2,2}\) and minimize
Assume at least two distinct design points. Values at those points together with \(\|f''\|_2\) control the \(W^{2,2}\) norm: integrate \(f''\) twice and solve for the two affine coefficients. A bounded minimizing sequence thus has a weakly convergent subsequence; evaluations are continuous linear functionals and the squared derivative norm is weakly lower semicontinuous. This proves existence. A direction with zero quadratic curvature must be affine and vanish at two distinct points, hence zero, proving uniqueness.
For every variation \(h\in W^{2,2}\), the first-order equation is
On an interval containing no observation, compactly supported variations give \(f^{(4)}=0\) in the distributional sense, so \(f\) is cubic there. The Sobolev representative has continuous \(f,f'\). Integrating by parts on adjacent intervals, the arbitrary values of \(h'\) at a knot force continuity of \(f''\); the coefficients of \(h\) permit jumps in \(f^{(3)}\). Endpoint variations impose \(f''(0)=f''(1)=0\); on any exterior interval with no observations they also force \(f^{(3)}=0\), giving linear tails. Thus the solution is a natural cubic spline, whose third derivative may jump at the distinct observations.
The constrained version \(\int(f'')^2\le R\) approaches affine least squares as \(R\downarrow0\); the penalized version does so as \(\lambda\to\infty\). To see the latter, compare with the best affine fit: its objective is bounded independently of \(\lambda\), so \(\int(\widehat f'')^2\to0\), and the same two-point control identifies the affine least-squares limit. These are two different tuning parameters.
Example 4 (Convex regression). For a finite convex function on an open convex domain \(D\), each design point \(x_i\in D\) has a supporting subgradient \(z_i\). Its values \(a_i=f(x_i)\) therefore satisfy
Conversely, any feasible values and subgradients define \(f(x)=\max_i\{a_i+\langle z_i,x-x_i\rangle\}\). This function is convex and satisfies \(f(x_j)=a_j\): every plane is at most \(a_j\), and the \(j\)th plane attains it. Thus minimizing \(n^{-1}\sum_i(Y_i-a_i)^2\) under these linear constraints is exactly the original problem on the observed points. This is a finite-dimensional representation, rather than a claim that the function away from the observations is uniquely determined. The feasible value set is a nonempty closed convex polyhedron (a linear projection of this finite system of inequalities), so its least-squares projection exists.
Set \(\mathcal F^*=\mathcal F-f^*\), and define the normalized empirical local complexity by
Both the factor \(1/n\) and the empirical norm are required. For random design, a population-localized complexity could instead restrict \(\|h\|_{P,2}\) and average over the design; it is a different quantity. We retain fixed design throughout. The critical inequality is
Expanding the least-squares comparison with the feasible truth gives the pathwise basic inequality
The error radius is random and depends on these same Gaussian variables. Replacing the right side by an expectation at that random radius is not justified. The next uniform event resolves that dependence.
Theorem 5. Suppose \(\mathcal F^*\) is star-shaped about zero and \(\delta_n>0\) solves the critical inequality. For every \(t\ge\delta_n\),
Remark 6. For \(0<r<s\), star-shapedness implies \((r/s)(\mathcal F^*\cap B_s)\subset\mathcal F^*\cap B_r\); hence \(\mathcal G_n(s)/s\le\mathcal G_n(r)/r\). Also Cauchy–Schwarz gives \(\mathcal G_n(r)\le r\mathbb E\|g\|_2/\sqrt n\le r\), so \(r=2\sigma\) is always an admissible radius. Existence does not require an attained smallest positive radius; any admissible positive one suffices.
Proof of Theorem 5. For fixed \(s\ge\delta_n\), put
It is \(\sigma s/\sqrt n\)-Lipschitz, and \(\mathbb EA_s=\sigma\mathcal G_n(s)\le s\delta_n/2\le s^2/2\). Gaussian concentration implies
If any \(h\in\mathcal F^*\) with \(\|h\|_n\ge s\) satisfies \(|\sigma\langle g,h\rangle/n|\ge2s\|h\|_n\), the rescaled function \(sh/\|h\|_n\) belongs to the radius-\(s\) class and forces \(A_s\ge2s^2\). On the complement of this event every such \(h\), including the data-dependent error, obeys the strict reverse inequality. If \(\|\widehat\Delta\|_n<s\), the desired bound already holds. Otherwise the basic inequality gives \(\|\widehat\Delta\|_n^2/2<2s\|\widehat\Delta\|_n\), hence \(\|\widehat\Delta\|_n<4s\). Set \(s=\sqrt{t\delta_n}\). This proves the tail bound, including the zero-error case. All local suprema are continuous Lipschitz functions of \(g\), since the local evaluation vectors are bounded subsets of \(\mathbb R^n\).
Integrating the tail also gives \(\mathbb E\|\widehat\Delta\|_n^2\le16\delta_n^2+32\sigma^2/n\). Indeed, above \(16\delta_n^2\) the tail is bounded by \(\exp\{-nu/(32\sigma^2)\}\). The constants and possible \(\sigma^2/n\) remainder cannot be dropped merely by the heuristic preceding the theorem. ◻
Proposition 7 (Truncated entropy bound). Let \(B_\delta=\{h\in\mathcal F^*:\|h\|_n\le\delta\}\), and let \(C\) be a universal constant. For \(0<a<\delta/2\),
Consequently, if \(0<\delta\le\sigma\), take \(a=\delta^2/(8\sigma)\). An upper bound \(\delta^2/(4\sigma)\) on the integral term is sufficient for the critical inequality. The universal constant and cutoff replace the unsupported exact constant in the source.
Proof. Use internal nets at radii \(r_j=\delta2^{-j}\), with \(\pi_0h=0\), and stop at the first \(K\) for which \(r_K\le2a\). Then \(a<r_K\le2a\). In normalized Gaussian inner products, an increment between two net points at level \(j\) has standard deviation at most \(3r_j/\sqrt n\), and there are at most \(N(r_j)N(r_{j-1})\) possibilities. The finite Gaussian maximum bound therefore bounds its expected absolute maximum by \(Cr_j\sqrt{\log(2N(r_j))}/\sqrt n\). Because entropy is nonincreasing,
The intervals are disjoint and lie in \([a/2,\delta]\). The remaining approximation error is bounded by \(r_K\|g\|_2/\sqrt n\), whose expectation is at most \(2a\). Summing proves the claim. Letting \(a\downarrow0\) also gives the full entropy-integral bound when finite. The covariance metric is \(\|h-k\|_n/\sqrt n\) for the normalized sums; its square is not the unsquared norm. ◻
Remark 8. The bound \(\mathcal G_n(\delta)\le\delta\) gives the admissible radius \(2\sigma\). Conversely, if the star-shaped error class contains the constant function one, then for \(0<\delta\le1\) it contains the constant function \(\delta\), and
An admissible radius in this range must satisfy \(\delta^2\ge8\sigma^2/(\pi n)\). Every admissible positive radius therefore obeys \(\delta^2\ge\min\{1,8\sigma^2/(\pi n)\}\). Convexity beyond star-shapedness is unnecessary for this particular argument.
1. Application: Rates of Convergence
We apply the same normalized complexity throughout the examples below.
1.1. Parametric problem: linear regressions
For linear regression put \(S=\operatorname{range}(X)\), \(r=\dim S\). Euclidean volume comparison gives \(\log N(u,S\cap B_\delta,\|\cdot\|_n)\le r\log(1+2\delta/u)\). The entropy integral becomes \(\delta\sqrt{r/n}\int_0^1\sqrt{\log(1+2/v)}\,dv\), which is finite. More directly,
Thus \(\delta_n=2\sigma\sqrt{r/n}\) works for \(r>0\). The fitted vector is \(\Pi_SY\), giving exact mean squared prediction error \(\sigma^2r/n\); no inverse of \(X^\top X\) is needed. This risk is minimax over the full subspace: a centered Gaussian prior with covariance \(\tau^2I_r\) on orthonormal subspace coordinates has Bayes risk \(r\sigma^2\tau^2/[n(\sigma^2+\tau^2)]\). Letting \(\tau\to\infty\) proves the matching lower bound. If \(r=0\), prediction is exact.
Remark 9 (Polynomial regression). Fix design points \(x_1,\ldots,x_n\), let \(\phi(x)=(1,x,\ldots,x^{d-1})\), and form the design matrix \(\Phi\in\mathbb R^{n\times d}\) with rows \(\phi(x_i)^\top\). The vectors of polynomial evaluations form the linear subspace \(S=\operatorname{range}(\Phi)\), of dimension \(r=\operatorname{rank}(\Phi)\le\min(n,d)\). They are generally an uncountable set. The Sauer–Shelah lemma counts Boolean traces and cannot bound the cardinality of these real-valued vectors.
Projection onto \(S\) gives the local Gaussian complexity exactly. For a standard Gaussian vector \(g\in\mathbb R^n\),
Thus \(\delta_n=2\sigma\sqrt{r/n}\) satisfies the critical inequality for this normalized complexity \(\sigma\mathcal C_n(\delta_n)\le\delta_n^2/2\) when \(r>0\). This calculation needs no logarithmic factor and remains valid when the design matrix has dependent columns.
For unrestricted least squares in the well-specified Gaussian model \(Y=\Phi\beta^*+\sigma g\), the fitted vector is \(\Pi_SY\), regardless of whether the coefficient vector is unique. Hence
The squared projected norm has the chi-square law with \(r\) degrees of freedom. For every \(u>0\),
To verify the tail bound, for \(0<t<1/2\) its centered log moment generating function is \(-r\log(1-2t)/2-rt\le rt^2/(1-2t)\); Chernoff optimization gives the displayed threshold. Taking \(u=d\log(n+1)\) recovers a bound of order \(\sigma^2d\log(n+1)/n\) with probability at least \(1-(n+1)^{-d}\). The logarithm here records the chosen confidence level, rather than a combinatorial count of polynomial evaluation vectors. If \(r=0\), the prediction error is identically zero.
1.2. Nonparametric Least Squares: Twice-Differentiable Functions
For a fixed constant \(C\), consider functions with \(\|f\|_\infty,\|f'\|_\infty\le C\) and \(f'\) Lipschitz with constant at most \(C\). This closed \(C^{1,1}\) class contains the source's twice continuously differentiable class with these bounds. It is convex and compact in \(C^1\) by Arzelà–Ascoli, so its prediction set is compact and least squares exists. Alternatively one may retain the original \(C^2\) class if existence of its minimizer is assumed. In either case assume the truth belongs to the fitted class.
The uniform entropy bound is \(\log N(u,\mathcal F_C,\|\cdot\|_\infty)\le C_Cu^{-1/2}\) for \(0<u\le1\). Here is a constructive proof. Take a regular mesh of spacing \(h\asymp\sqrt u\). At each mesh point round \(f\) to a multiple of \(h^2\) and \(f'\) to a multiple of \(h\). The initial pair has only polynomially many possibilities in \(1/h\). Given one rounded pair, the next derivative differs by at most \(Ch\), up to rounding, and Taylor's remainder gives
Thus there are only a bounded number, depending on \(C\), of next rounded pairs. Over \(O(1/h)\) intervals the logarithm of the number of codes is \(O_C(1/h)+O_C(\log(1/h))\). Piecewise affine reconstruction from the code has uniform error \(O_C(h^2)\). Choosing \(h\) by a sufficiently small constant multiple of \(\sqrt u\) gives the stated bound; selecting a function from each nonempty coding cell gives internal centers at twice the radius.
The difference class has the same bound with \(2C\). Restricting a cover to a local ball costs at most a factor two in radius. Since \(\|\cdot\|_n\le\|\cdot\|_\infty\), Proposition 7 gives, for \(0<\delta\le1\),
Solving \(\sigma C_C'\delta^{3/4}/\sqrt n\le\delta^2/2\) yields \(\delta_n=A_C(\sigma^2/n)^{2/5}\). In the regime where this radius is at most one, Theorem 5 with \(t=\delta_n\) proves
The squared-error exponent is \(4/5\); \(2/5\) is the exponent for the unsquared radius. For larger noise levels the general radius \(2\sigma\) and the bounded diameter remain available. The entropy exponent depends on smoothness two, not on the envelope constant \(C\).
1.3. Nonparametric Problem: Orthogonal Series Expansions
Let \(\phi_j\) be orthonormal in population \(L^2(P)\), and fit \(f_\beta=\sum_{j=1}^T\beta_j\phi_j\) under \(\|\beta\|_2\le1\). With \(\Phi_{ij}=\phi_j(x_i)\), empirical orthonormality is the additional condition \(\Phi^\top\Phi/n=I_T\), not a consequence of population orthonormality. In this special case, setting \(z=\Phi^\top Y/n\) gives
The penalized objective with penalty \(\lambda\|\beta\|_2^2\) has solution \(z/(1+\lambda)\); the matching nonnegative parameter is \(\lambda=(\|z\|_2-1)_+\). For a general design, convex optimality gives
These conditions are sufficient by convexity and necessary since the unit ball has an interior feasible point. If the unconstrained minimum-norm least-squares coefficient lies in the ball, choose \(\lambda=0\); otherwise \(\lambda>0\) and the norm of the ridge solution decreases continuously and crosses one as \(\lambda\) increases. Thus singular designs cause no difficulty.
For \(f^*=\sum_{j\ge1}\beta_j^*\phi_j\in L^2(P)\), Parseval gives
Consequently the best approximation under the coefficient ball is
The first term vanishes only if the truncated truth is feasible. This is a population approximation identity; a misspecified empirical-risk bound needs a separate approximation argument, since Theorem 5 assumes a feasible truth.
1.4. Nonparametric Problem: Additive Models
For each coordinate let \(\mathcal H_j\) be a convex symmetric class containing zero, such as the unit ball of a normed function space. These are properties of the class, not assertions that each univariate function is convex and even. Fit sums \(f(x)=\sum_{j=1}^d h_j(x_j)\), with a feasible decomposition \(f^*=\sum_jh_j^*\). Then \(\Delta_j=\widehat h_j-h_j^*\in2\mathcal H_j\), and \(\Delta=\sum_j\Delta_j\). Define
Choose any positive \(\delta_j\) satisfying \(\sigma\mathcal G_{n,j}(\delta_j)\le\delta_j^2/2\), and put \(\delta_{\max}=\max_j\delta_j\). For fixed \(t\ge\delta_{\max}\), let \(Z_{j,t}\) be the corresponding random supremum at radius \(t\), including the factor \(\sigma\). Its mean is at most \(t\delta_j/2\le t^2/2\), since \(\mathcal G_{n,j}(r)/r\) is nonincreasing, and its Lipschitz constant is \(\sigma t/\sqrt n\). Therefore
On the simultaneous event for all coordinates, star-shaped rescaling gives, for every \(h\in2\mathcal H_j\),
For \(\|h\|_n\le t\) use the local bound; otherwise scale to radius \(t\). This event is uniform in \(h\), so it applies to the random fitted components. A union bound and the basic inequality imply, with probability at least \(1-de^{-nt^2/(8\sigma^2)}\),
To express the right side in terms of the total prediction error, impose the empirical compatibility condition
This is an assumption on the design and component classes. It cannot be deduced from convexity: two components equal to constants \(1\) and \(-1\) already contradict it. Empirically orthogonal component spaces satisfy it with \(K=1\); centering alone does not establish empirical orthogonality.
Under this condition, Cauchy–Schwarz gives \(\sum_j\|\Delta_j\|_n\le\sqrt{dK}\|\Delta\|_n\). Using \(t\sqrt{dK}\|\Delta\|_n\le\|\Delta\|_n^2/4+dKt^2\) then yields
For a specified failure probability \(\eta\), take \(t=\max\{\delta_{\max},\sigma\sqrt{8\log(d/\eta)/n}\}\). The same inequality then holds with probability at least \(1-\eta\). No independence between the coordinatewise noise suprema was assumed.