Deriving the Effective-Dimension Variance Bound

Why Effective Dimension Controls Variance

Kernel ridge regression fits a function using noisy responses while penalizing its RKHS norm. Its variance depends not just on the noise level and sample size, but also on how many directions the kernel can use at the chosen regularization level. Effective dimension summarizes that regularized number of directions. This tutorial derives an expected variance bound in the empirical prediction norm.

The distinction in that last phrase matters. The bound below concerns the fitted noise evaluated at the training inputs. It is not, without additional arguments, a bound on prediction error at a fresh input. We make the norm explicit so the result states exactly what has been proved.

Assumptions and notation: Let \(\mathcal H\) be a separable RKHS with measurable kernel \(k\), and suppose \(k(x,x)\leq \kappa^2\) for every \(x\). The inputs \(X_1,\ldots,X_n\) are independent and identically distributed from \(P\). Write \(K_x=k(x,\cdot)\), and define the population and empirical covariance operators by

T=E[K_X\otimes K_X], \qquad T_n=\frac{1}{n}\sum_{i=1}^n K_{X_i}\otimes K_{X_i}.

Here \((u\otimes v)h=\langle v,h\rangle_{\mathcal H}u\). Assume the errors are conditionally independent given the inputs, with \(E[\varepsilon_i\mid X_1,\ldots,X_n]=0\) and \(E[\varepsilon_i^2\mid X_1,\ldots,X_n]\leq \sigma^2\). For \(\lambda>0\), define the population effective dimension \(N(\lambda)=\operatorname{Tr}\{T(T+\lambda I)^{-1}\}\).

The kernel bound implies \(E\|K_X\|_{\mathcal H}^2=E[k(X,X)]\leq\kappa^2\), so \(T\) is a positive trace-class operator. Thus \(N(\lambda)\) is finite, and \(N(\lambda)\leq \operatorname{Tr}(T)/\lambda\leq\kappa^2/\lambda\). The trace is the sum of eigenvalues, counted with multiplicity; equivalently, if \(T\) has eigenvalues \(\mu_j\), then \(N(\lambda)=\sum_j\mu_j/(\mu_j+\lambda)\).

The Noise-Only Fit and the Main Bound

For squared-loss kernel ridge regression, the part of the fitted function that is linear in the errors is

\widehat f_{\varepsilon} =(T_n+\lambda I)^{-1}\frac{1}{n}\sum_{i=1}^n\varepsilon_i K_{X_i}.

This follows from the regularized normal equation: replacing every response by its noise contribution leaves the empirical covariance on the left and the noise-feature average on the right. Define the empirical prediction norm by \(\|h\|_{T_n}^2=\langle h,T_nh\rangle_{\mathcal H}=n^{-1}\sum_{i=1}^n h(X_i)^2\). The next result bounds the conditional variance in this norm.

Theorem: Under the assumptions above, for every fixed \(\lambda>0\),

E\!\left[\|\widehat f_{\varepsilon}\|_{T_n}^2\right] \leq \frac{\sigma^2}{n}N(\lambda).

The expectation is over both the inputs and the errors. More precisely, conditional on the inputs, the variance is at most \(\frac{\sigma^2}{n}\operatorname{Tr}\{[T_n(T_n+\lambda I)^{-1}]^2\}\), which is at most \(\frac{\sigma^2}{n}\operatorname{Tr}\{T_n(T_n+\lambda I)^{-1}\}\).

Proof of the conditional bound. Fix the inputs and let \(b=n^{-1}\sum_i\varepsilon_iK_{X_i}\). Conditional independence and zero conditional means make the cross-covariances vanish. Therefore, in positive-semidefinite operator order,

\operatorname{Cov}(b\mid X_1,\ldots,X_n) =\frac{1}{n^2}\sum_{i=1}^n \operatorname{Var}(\varepsilon_i\mid X_1,\ldots,X_n) (K_{X_i}\otimes K_{X_i}) \preceq \frac{\sigma^2}{n}T_n.

Set \(R=(T_n+\lambda I)^{-1}\), so that \(\widehat f_\varepsilon=Rb\). For a centered random vector with covariance \(C\), the expected squared norm after applying an operator \(A\) is \(\operatorname{Tr}(ACA^*)\); this identity follows by expanding in an orthonormal basis. Applying it with the empirical norm gives

E[\|\widehat f_\varepsilon\|_{T_n}^2\mid X_1,\ldots,X_n] =\operatorname{Tr}\{T_nR\operatorname{Cov}(b\mid X_1,\ldots,X_n)R\} \leq \frac{\sigma^2}{n}\operatorname{Tr}(RT_nRT_n).

The inequality uses the covariance bound and the fact that taking the trace against a positive operator preserves positive-semidefinite order. Since \(R\) is a function of \(T_n\), these operators commute. If \(t\geq0\) is an eigenvalue of \(T_n\), its contribution to the last trace is \(t^2/(t+\lambda)^2\), and

\frac{t^2}{(t+\lambda)^2}\leq\frac{t}{t+\lambda}.

Summing over the eigenvalues proves the stated conditional bound. The empirical covariance has finite rank, so these traces are finite. \(\square\)

Why the Expected Empirical Dimension Is Bounded

It remains to compare the empirical effective dimension with \(N(\lambda)\). The key fact is that \(A\mapsto A(A+\lambda I)^{-1}\) is operator concave for positive operators. Here is the needed Jensen inequality and its justification.

Operator Jensen inequality used here: For positive random operators \(A\) with finite expected trace, and \(g(A)=A(A+\lambda I)^{-1}\),

E[g(A)]\preceq g(E[A]).

In particular, if \(E[A]=T\), then \(E\operatorname{Tr}\{A(A+\lambda I)^{-1}\}\leq \operatorname{Tr}\{T(T+\lambda I)^{-1}\}\).

Justification. For a positive definite operator \(B\), the quadratic form of its inverse has the variational expression

\langle u,B^{-1}u\rangle =\sup_v\{2\langle u,v\rangle-\langle v,Bv\rangle\}.

Indeed, subtracting the expression inside the supremum from the left side gives \(\langle v-B^{-1}u,B(v-B^{-1}u)\rangle\geq0\), with equality at \(v=B^{-1}u\). A supremum of affine functions of \(B\) is convex. Applying scalar Jensen to this quadratic-form representation gives

E[(A+\lambda I)^{-1}]\succeq(E[A]+\lambda I)^{-1}.

Since \(g(A)=I-\lambda(A+\lambda I)^{-1}\), this is the asserted operator concavity inequality. For finite-dimensional operators, taking traces gives the trace inequality directly. In the trace-class setting here, apply that result on increasing finite-dimensional projections and pass to the limit: \(A(A+\lambda I)^{-1}\) has trace at most \(\operatorname{Tr}(A)/\lambda\), so the projected traces converge to the full trace. This establishes the stated inequality in the setting used below. \(\square\)

Apply this result to \(A=T_n\). Because the inputs are identically distributed, \(E[T_n]=T\). Consequently,

E\operatorname{Tr}\{T_n(T_n+\lambda I)^{-1}\} \leq \operatorname{Tr}\{T(T+\lambda I)^{-1}\}=N(\lambda).

Taking expectations in the conditional variance bound and using \(\operatorname{Tr}\{[T_n(T_n+\lambda I)^{-1}]^2\}\leq\operatorname{Tr}\{T_n(T_n+\lambda I)^{-1}\}\) proves the theorem. \(\square\)

Worked Examples

Worked Example: A Constant Kernel

Suppose \(k(x,x')=1\) for all inputs, and use the noise-only fit with conditional error variance exactly \(\sigma^2\). The RKHS is one-dimensional, consisting of constant functions. The feature vector has norm one, so \(T=T_n=1\) on that dimension, regardless of the observed inputs.

Thus \(N(\lambda)=1/(1+\lambda)\). The fitted noise function is the constant \(\bar\varepsilon/(1+\lambda)\), where \(\bar\varepsilon=n^{-1}\sum_i\varepsilon_i\). Its empirical squared norm has expectation

E\!\left[\|\widehat f_\varepsilon\|_{T_n}^2\right] =\frac{E[\bar\varepsilon^2]}{(1+\lambda)^2} =\frac{\sigma^2}{n(1+\lambda)^2} \leq\frac{\sigma^2}{n(1+\lambda)} =\frac{\sigma^2}{n}N(\lambda).

The inequality holds because \(1+\lambda\geq1\). This example displays both the \(1/n\) noise averaging and the regularization’s reduction of variance.

Worked Example: A Uniform Distribution on Four Points

Let the input take values \(1,2,3,4\), each with probability \(1/4\), and use the kernel \(k(i,j)=1\) if \(i=j\) and \(0\) otherwise. Its feature vectors are the four coordinate vectors, so \(T\) is diagonal with each diagonal entry \(1/4\). At \(\lambda=1/4\), each eigenvalue contributes

\frac{1/4}{1/4+1/4}=\frac12

to effective dimension. Therefore \(N(1/4)=4(1/2)=2\), and the theorem gives \(E\|\widehat f_\varepsilon\|_{T_n}^2\leq2\sigma^2/n\). The sample covariance has diagonal entries equal to the four observed proportions, which can vary substantially across samples; the result controls their expected regularized dimension without requiring them to equal their population values.

Worked Example: Comparing the Squared and Unsquared Trace Terms

Consider a fixed empirical covariance with eigenvalues \(2\) and \(1/2\), and take \(\lambda=1/2\). The trace term from the conditional covariance calculation is

\left(\frac{2}{2+1/2}\right)^2+ \left(\frac{1/2}{1/2+1/2}\right)^2 =(0.8)^2+(0.5)^2=0.89.

The empirical effective dimension is instead

\frac{2}{2+1/2}+\frac{1/2}{1/2+1/2} =0.8+0.5=1.3.

Thus the conditional variance is bounded by \(0.89\sigma^2/n\), and hence also by the looser but simpler \(1.3\sigma^2/n\). This numerical comparison illustrates the eigenvalue inequality used in the proof; it does not require the sample covariance to have these particular eigenvalues in every application.

Interpretation and a Common Pitfall

The bound has the familiar form “noise variance times effective dimension divided by sample size.” Each regularized eigen-direction contributes \(\mu_j/(\mu_j+\lambda)\) to \(N(\lambda)\): directions with eigenvalues much smaller than \(\lambda\) contribute little, while directions much larger than \(\lambda\) contribute nearly one. Increasing \(\lambda\) therefore reduces this variance bound by suppressing more directions. This result is a variance statement; it does not quantify the bias caused by regularization.

Pitfall: silently changing the prediction norm. The proof controls \(n^{-1}\sum_i\widehat f_\varepsilon(X_i)^2\). It does not establish the same bound for \(E_X[\widehat f_\varepsilon(X)^2]\), where \(X\) is a fresh input. Those quantities use different covariance operators, and the fitted function depends on the training inputs.
Correction: State the norm in the claim. A population prediction bound requires additional control that connects the sample-dependent fit and the population covariance; it does not follow just by renaming \(\|\cdot\|_{T_n}\) as \(\|\cdot\|_T\).
Pitfall: assuming only an unconditional mean-zero error is enough. The conditional covariance calculation uses zero conditional means and conditional independence given the inputs.
Correction: Check the noise assumptions at the design level. A uniform conditional variance upper bound is sufficient here; the errors need not have identical conditional variances.

Key takeaway: For bounded kernels, independent random inputs, and conditionally independent mean-zero errors with variance at most \(\sigma^2\), kernel ridge regression’s expected empirical prediction variance is at most \(\sigma^2N(\lambda)/n\). The proof first bounds conditional noise variance by empirical effective dimension, then uses operator concavity to compare its expectation with population effective dimension.

Check Your Understanding

Try these questions before moving on.

Why does the bounded-kernel assumption imply that \(T\) has finite trace?
In the conditional covariance calculation, where are conditional independence and the zero conditional means used?
For an eigenvalue \(t\geq0\), verify that \(t^2/(t+\lambda)^2\leq t/(t+\lambda)\).
What does the factor \(\mu_j/(\mu_j+\lambda)\) contribute when \(\mu_j\) is much smaller than \(\lambda\)?
Why does the theorem not by itself bound prediction variance at a fresh input?