Finite-Rank Kernels and Parametric Prediction Rates

Why Finite Rank Changes the Rate Calculation

For an infinite-rank kernel, the effective dimension can grow as regularization decreases. For a finite-rank kernel, there are only finitely many directions in which predictions can vary. This caps effective dimension and makes a parametric prediction rate possible: for fixed rank, prediction error can decrease at order \(1/n\). The rank alone does not guarantee that rate, however. The design must provide information about all relevant directions, and the noise must be controlled.

We will first calculate the spectral effective dimension and its variance bound. We will then give a finite-dimensional kernel ridge result with explicit assumptions. The distinction matters: a spectral variance expression is informative, but a rate for a fitted estimator also depends on how the observed design represents the population directions.

Finite Rank and Effective Dimension

Each direction contributes a number between zero and one. Directions with \(\mu_j\) much larger than \(\lambda\) contribute nearly one; directions much smaller than \(\lambda\) contribute little. Thus \(0\leq\mathcal{N}(\lambda)\leq r\), and as \(\lambda\) decreases to zero, \(\mathcal{N}(\lambda)\) increases to \(r\). Unlike an infinite-rank setting, the effective dimension cannot keep growing without bound.

Suppose the regression target lies in the range of \(T\), and write its expansion in orthonormal eigenfunctions as \(f_*=\sum_{j=1}^r a_j e_j\). The population ridge solution is \(f_\lambda=(T+\lambda I)^{-1}Tf_*\). Its coefficient in direction \(e_j\) is \(\mu_j a_j/(\mu_j+\lambda)\). Consequently its squared \(L_2(P_X)\) approximation error is

This is the regularization bias: ridge shrinks each direction, and the shrinkage is stronger relative to signal in directions with smaller eigenvalues. In a finite-rank model, the sum has only \(r\) terms.

Effective Dimension Bounds the Empirical Variance

A direct variance calculation is available for a fixed design. Let \(K\) be the \(n\times n\) Gram matrix, with eigenvalues \(s_1,\ldots,s_n\geq0\), and define the scaled eigenvalues \(q_j=s_j/n\). With the objective \(n^{-1}\|y-f\|^2+\lambda\|f\|_{\mathcal H}^2\), the fitted-value smoother has eigenvalues \(q_j/(q_j+\lambda)\) on the nonzero eigenspaces. The empirical effective dimension is \(\mathcal{N}_n(\lambda)=\sum_j q_j/(q_j+\lambda)\).

To verify the expression, write the fitted-value smoother as \(H=K(K+n\lambda I)^{-1}\). If the response noise vector is \(\varepsilon\), the noise part of the fitted values is \(H\varepsilon\). The empirical squared prediction error is \(n^{-1}\|H\varepsilon\|^2\). Since \(E[\varepsilon\varepsilon^\top]=\sigma^2 I\), its expectation is \(\sigma^2 n^{-1}\operatorname{Tr}(H^2)\). The eigenvalues of \(H\) are \(q_j/(q_j+\lambda)\), giving the stated sum. Each such eigenvalue \(u\) satisfies \(0\leq u\leq1\), so \(u^2\leq u\). Summing this inequality gives the effective-dimension bound. At most \(r\) terms are nonzero, each at most one, proving the rank bound. \(\square\)

This calculation is exact for empirical prediction error under the stated noise assumptions. It is not, by itself, an exact formula for population prediction error: the observed design and the population distribution need not measure prediction errors in the same way. The next result makes the needed connection explicit in a finite-dimensional representation.

A Finite-Dimensional Prediction-Rate Result

Represent a rank-\(r\) kernel through a feature vector \(\phi(X)\in\mathbb{R}^r\), so that prediction functions have the form \(f_\beta(X)=\phi(X)^\top\beta\). Let \(\Sigma=E[\phi(X)\phi(X)^\top]\). For observations \((X_i,Y_i)\), define the empirical feature covariance \(G=n^{-1}\sum_{i=1}^n\phi(X_i)\phi(X_i)^\top\). Kernel ridge regression in these coordinates minimizes the empirical squared error plus \(\lambda\|\beta\|^2\).

To prove the result, write \(\Phi\) for the matrix whose \(i\)th row is \(\phi(X_i)^\top\). Then $$ \hat{\beta}_\lambda-\beta_* =-\lambda(G+\lambda I)^{-1}\beta_* +(G+\lambda I)^{-1}\frac{\Phi^\top\varepsilon}{n}. $$ The first term is the regularization bias and the second is the noise contribution. Conditional on the design, the noise has mean zero, so the expected cross term in squared prediction error is zero.

For the bias, the smallest eigenvalue of \(G\) is at least \(c\). Therefore $$ \left\|\lambda(G+\lambda I)^{-1}\beta_*\right\| \leq \frac{\lambda R}{c+\lambda} \leq \frac{\lambda R}{c}. $$ Using \(\Sigma\preceq aG\) and \(G\preceq CI\), its squared population prediction error is at most $$ a\,\lambda^2\beta_*^\top(G+\lambda I)^{-1}G(G+\lambda I)^{-1}\beta_* \leq aC\frac{\lambda^2R^2}{c^2}. $$

For the noise term, its conditional covariance matrix is $$ \frac{\sigma^2}{n}(G+\lambda I)^{-1}G(G+\lambda I)^{-1}, $$ because \(E[\varepsilon\varepsilon^\top\mid X_1,\ldots,X_n]=\sigma^2I\) and \(\Phi^\top\Phi/n=G\). Domination by \(aG\) bounds its population prediction error by $$ \frac{a\sigma^2}{n}\operatorname{Tr}\!\left(G^2(G+\lambda I)^{-2}\right) =\frac{a\sigma^2}{n}\sum_{j=1}^r\left(\frac{g_j}{g_j+\lambda}\right)^2 \leq\frac{a\sigma^2r}{n}, $$ where \(g_1,\ldots,g_r\) are the eigenvalues of \(G\). The final inequality holds because each fraction is at most one. Adding the bias and variance bounds proves the theorem. \(\square\)

For fixed \(r\), choose \(\lambda=1/n\). The theorem gives a bias term of order \(n^{-2}\) and a variance term of order \(r/n\), hence a prediction error of order \(r/n\) when the constants and \(R\) are fixed. This is the parametric prediction rate. For random designs with fixed \(r\), positive-definite \(\Sigma\), and suitable moment conditions, empirical covariance converges to \(\Sigma\); the required covariance comparisons then hold with probability tending to one. The theorem is conditional on those comparisons, rather than a claim that they hold for every finite sample.

What Finite Rank Does—and Does Not—Guarantee

Finite rank limits the number of estimable prediction directions. This is why the variance can be bounded by a rank factor divided by sample size, rather than by an effective dimension that grows as \(\lambda\) shrinks. With fixed rank and adequate design information, prediction behaves like estimation in a finite-dimensional parametric model.

The qualification about design is essential. If observations provide almost no information in one direction, the empirical covariance can be nearly singular even when the population kernel has finite rank. In that case, a small regularization level can amplify estimation error in that direction. The theorem's lower eigenvalue condition excludes this failure; the comparison \(\Sigma\preceq aG\) ensures that population prediction loss is controlled by directions represented in the sample.

• Common mistake: “finite rank automatically gives error \(r/n\).” Rank caps the effective-dimension variance term, but a population prediction-rate claim also needs a suitable design and a noise condition. Poorly observed directions can invalidate the comparison between empirical and population loss.
• Common mistake: treating effective dimension as exactly the rank for every \(\lambda\). At positive \(\lambda\), each direction contributes \(\mu_j/(\mu_j+\lambda)\), usually less than one. The effective dimension approaches rank only as \(\lambda\) decreases to zero.
• Common mistake: ignoring regularization bias because the model has finite rank. Ridge shrinks coefficients even when the target is exactly representable. The bias vanishes as \(\lambda\) decreases, but the balance with variance still matters.