Proof of a Kernel Ridge Rate Theorem

From a Risk Inequality to a Rate

A kernel ridge rate is not determined by regularization alone. The prediction error has two competing contributions: regularization leaves some of a smooth target unrepresented, while estimating the target from noisy observations incurs variance. A proof of a rate makes both contributions explicit, bounds each in terms of the regularization parameter, and then chooses that parameter to balance them.

This tutorial proves that calculation under a precise finite-sample risk inequality. The inequality is the statistical input: it must be justified by appropriate sampling, noise, and concentration conditions for the problem at hand. The rate proof then combines a source condition for the target with a bound on effective dimension. Keeping these roles distinct makes clear both what the rate argument proves and what must be checked before applying it.

Definition: Let $T$ be the positive covariance operator of a kernel on $L^2(P_X)$, with eigenpairs $(\mu_j,\phi_j)$, where $\mu_j\geq 0$ are listed in nonincreasing order. The effective dimension at $\lambda>0$ is $$ \mathcal{N}(\lambda)=\sum_{j:\,\mu_j>0}\frac{\mu_j}{\mu_j+\lambda}. $$ A source condition of exponent $r>0$ is $f_*=T^r g$ for some $g\in L^2(P_X)$. Here $f_*$ is the regression target and $g$ is a source element.

The effective dimension counts directions in which the operator eigenvalue is large relative to $\lambda$, with a gradual rather than a hard cutoff. The sum is finite whenever, for example, $T$ is trace class: in that case $\mathcal{N}(\lambda)\leq \operatorname{tr}(T)/\lambda$. It is not finite for every positive $\lambda$ under arbitrary eigenvalue assumptions. We will explicitly impose conditions that guarantee finiteness.

The Risk Input and the Source Bias

Write $\|h\|_{L^2(P_X)}^2=E[h(X)^2]$ for prediction risk. For the theorem below, assume the sampling and noise conditions in use provide the following oracle inequality at a fixed confidence level:

Risk inequality: For $0<\lambda\leq\lambda_0$, with probability at least $1-\delta$, $$ \|\widehat f_\lambda-f_*\|_{L^2(P_X)}^2 \leq C_b\lambda^{2r}\|g\|_{L^2(P_X)}^2+ C_v\frac{\sigma^2\mathcal{N}(\lambda)}{n}. $$ Here $f_*=T^r g$, $0<r\leq 1$, $n$ is sample size, and $C_b,C_v,\lambda_0$ are positive constants independent of $n$ and $\lambda$. The noise scale is $\sigma^2$. The inequality is an assumption of the rate theorem, not a conclusion from eigenvalue decay alone.

The first term has the expected source-condition order. To see the underlying bias calculation, consider the population-regularized target $f_\lambda=T(T+\lambda I)^{-1}f_*$. Expand $g=\sum_j g_j\phi_j$ in the eigenbasis. For positive eigenvalues, the coefficient of $f_\lambda-f_*$ in direction $\phi_j$ is $-\lambda\mu_j^r g_j/(\mu_j+\lambda)$. Thus

\begin{aligned} \|f_\lambda-f_*\|_{L^2(P_X)}^2 &=\sum_j\left(\frac{\lambda\mu_j^r}{\mu_j+\lambda}\right)^2|g_j|^2\\ &=\lambda^{2r}\sum_j \left(\frac{(\mu_j/\lambda)^r}{1+\mu_j/\lambda}\right)^2|g_j|^2\\ &\leq \lambda^{2r}\sum_j |g_j|^2 =\lambda^{2r}\|g\|_{L^2(P_X)}^2. \end{aligned}

The inequality holds because $t^r/(1+t)\leq 1$ for $t\geq0$ and $0<r\leq1$: for $t\leq1$, $t^r\leq1$; for $t\geq1$, $t^r/(1+t)\leq t^{r-1}\leq1$. A component of $g$ in the null space of $T$ contributes zero to $T^r g$ and to this bias calculation. The restriction $r\leq1$ is important: this calculation does not give the same bound for arbitrarily large source exponents.

Worked Example: Checking the Source Bias Coordinate by Coordinate

Take a single eigen-direction with eigenvalue $\mu=4$, source coefficient $g_1=3$, exponent $r=1/2$, and regularization $\lambda=1$. The target coefficient is $\mu^r g_1=2\cdot3=6$, while the population-regularized coefficient is $\mu(\mu+\lambda)^{-1}\cdot6=(4/5)\cdot6=24/5$.

The squared coefficient error is $(6-24/5)^2=(6/5)^2=36/25=1.44$. The source bound for this one direction is $\lambda^{2r}|g_1|^2=1^1\cdot9=9$, so the calculated error is indeed below the bound. More generally, the scalar multiplier in the error is $\lambda\mu^r/(\mu+\lambda)$; the preceding inequality bounds it by $\lambda^r$, independently of the eigenvalue.

Bounding Effective Dimension from Eigenvalue Decay

Assume the positive eigenvalues satisfy, for constants $C_\mu>0$ and $0<\beta<1$, $\mu_j\leq C_\mu j^{-1/\beta}$. This polynomial decay is strong enough to make the effective dimension finite and to control its growth as $\lambda$ decreases.

Lemma: If $\mu_j\leq C_\mu j^{-1/\beta}$ for $0<\beta<1$, then for $0<\lambda\leq C_\mu$, $$ \mathcal{N}(\lambda)\leq \left(2+\frac{\beta}{1-\beta}\right) \left(\frac{C_\mu}{\lambda}\right)^\beta. $$

Proof. Put $q=(C_\mu/\lambda)^\beta\geq1$ and $J=\lceil q\rceil$. For $j\leq J$, each summand $\mu_j/(\mu_j+\lambda)$ is at most one, so those terms sum to at most $J\leq2q$. For $j>J$, $\mu_j/(\mu_j+\lambda)\leq\mu_j/\lambda\leq(C_\mu/\lambda)j^{-1/\beta}$. Since $1/\beta>1$, the integral bound for the decreasing function $x^{-1/\beta}$ gives

\begin{aligned} \sum_{j>J}\frac{\mu_j}{\mu_j+\lambda} &\leq \frac{C_\mu}{\lambda}\sum_{j>J}j^{-1/\beta}\\ &\leq \frac{C_\mu}{\lambda}\int_J^\infty x^{-1/\beta}\,dx\\ &=\frac{\beta}{1-\beta}\frac{C_\mu}{\lambda}J^{1-1/\beta}\\ &\leq \frac{\beta}{1-\beta}q. \end{aligned}

The final inequality uses $J\geq q$ and $1-1/\beta<0$; hence $J^{1-1/\beta}\leq q^{1-1/\beta}$. Also $(C_\mu/\lambda)q^{1-1/\beta}=q$. Adding the first $J$ terms proves the lemma. The condition $\beta<1$ is what makes the integral finite. $\square$

Worked Example: Effective Dimension for a Polynomial Spectrum

Suppose $\mu_j=4j^{-2}$. This has $C_\mu=4$ and $\beta=1/2$, since $j^{-2}=j^{-1/\beta}$. For $0<\lambda\leq4$, the lemma gives

\mathcal{N}(\lambda)\leq \left(2+\frac{1/2}{1-1/2}\right)(4/\lambda)^{1/2} =3(4/\lambda)^{1/2} =6\lambda^{-1/2}.

For example, at $\lambda=1/4$, this upper bound is $6(1/4)^{-1/2}=12$. This is an upper bound on the sum, not a claim that the sum equals 12. In particular, the proof accounts for the infinitely many small eigenvalues through the convergent tail rather than discarding them.

Kernel Ridge Rate Theorem

The bias term decreases with $\lambda$, while the effective-dimension term increases as $\lambda$ shrinks. Combining the preceding results yields the rate.

Theorem: Suppose $0<r\leq1$, $f_*=T^r g$, and the risk inequality above holds for $0<\lambda\leq\lambda_0$. Suppose also that $\mu_j\leq C_\mu j^{-1/\beta}$ for some $0<\beta<1$. For all sufficiently large $n$, choose $\lambda_n=n^{-1/(2r+\beta)}$. Then, with probability at least $1-\delta$, $$ \|\widehat f_{\lambda_n}-f_*\|_{L^2(P_X)}^2 \leq C n^{-2r/(2r+\beta)}, $$ where $C$ may depend on $C_b,C_v,\sigma^2,\|g\|_{L^2(P_X)}^2,C_\mu,r,\beta$, but not on $n$.

Proof. Since $\lambda_n\to0$, for all sufficiently large $n$ it satisfies both $\lambda_n\leq\lambda_0$ and $\lambda_n\leq C_\mu$. Apply the risk inequality and the effective-dimension lemma:

\begin{aligned} \|\widehat f_{\lambda_n}-f_*\|_{L^2(P_X)}^2 &\leq C_b\|g\|_{L^2(P_X)}^2\lambda_n^{2r} +C_v\sigma^2\frac{\mathcal{N}(\lambda_n)}{n}\\ &\leq C_b\|g\|_{L^2(P_X)}^2 n^{-2r/(2r+\beta)} +C_v\sigma^2 \left(2+\frac{\beta}{1-\beta}\right)C_\mu^\beta \frac{n^{\beta/(2r+\beta)}}{n}. \end{aligned}

The variance power simplifies as $n^{\beta/(2r+\beta)}/n=n^{-2r/(2r+\beta)}$. Both terms therefore have the claimed order, and their fixed coefficients can be combined into $C$. The probability statement is inherited from the assumed risk inequality. $\square$

Worked Example: Balancing the Two Terms Numerically

Continue with eigenvalues $\mu_j=4j^{-2}$, so that $\beta=1/2$ and $\mathcal{N}(\lambda)\leq6\lambda^{-1/2}$. Let $r=1/2$, $\|g\|_{L^2(P_X)}^2=1$, and take $C_b=C_v=\sigma^2=1$. The resulting risk bound is $\lambda+6n^{-1}\lambda^{-1/2}$.

Differentiate with respect to $\lambda>0$: \[ \frac{d}{d\lambda}\left(\lambda+6n^{-1}\lambda^{-1/2}\right) =1-3n^{-1}\lambda^{-3/2}. \] Setting this to zero gives $\lambda^{3/2}=3/n$, hence $\lambda=(3/n)^{2/3}$. Substituting this value,

\lambda+\frac{6}{n}\lambda^{-1/2} =3^{2/3}n^{-2/3}+6\cdot3^{-1/3}n^{-2/3} =3^{5/3}n^{-2/3}.

Thus the optimized bound has order $n^{-2/3}$, matching $n^{-2r/(2r+\beta)}=n^{-1/(1+1/2)}=n^{-2/3}$. The exact constant here comes from the stated upper bound and is not asserted to be the smallest possible risk constant.

Why Finiteness Is a Necessary Check

An eigenvalue-decay condition is not a cosmetic part of this argument. It makes the variance quantity finite and controls its growth. For instance, take $\mu_j=1/j$. For any fixed $\lambda>0$, whenever $j\geq\lceil1/\lambda\rceil$, we have $\lambda j\geq1$, and

\frac{\mu_j}{\mu_j+\lambda} =\frac{1}{1+\lambda j} \geq\frac{1}{2\lambda j}.

The sum of $1/j$ diverges, so $\mathcal{N}(\lambda)=\infty$. The effective-dimension variance bound cannot then yield a finite risk rate. This sequence has decay exponent $\beta=1$, outside the lemma's condition $0<\beta<1$, and is not trace class. One must not invoke the polynomial-decay conclusion for it. A suitable stronger decay assumption, or another argument establishing finite effective dimension, is needed.

Common pitfall: It is incorrect to say that $\mathcal{N}(\lambda)$ is finite merely because $\lambda>0$. A positive denominator does not ensure that an infinite sum converges. Check trace finiteness or prove a summable eigenvalue tail before using an effective-dimension rate.

The theorem’s rate is determined by the exponents in its two terms: source smoothness contributes $\lambda^{2r}$, and polynomial eigenvalue decay contributes $n^{-1}\lambda^{-\beta}$. Equating their orders gives $\lambda\asymp n^{-1/(2r+\beta)}$ and prediction risk $n^{-2r/(2r+\beta)}$. This conclusion is conditional on the finite-sample risk inequality; verifying that inequality for a particular sampling design and noise model remains essential.

Check Your Understanding

Use the assumptions and calculations above to answer these questions.

Why does the source-bias calculation require $r\leq1$ for the stated bound?
Under $\mu_j\leq C_\mu j^{-1/\beta}$, why must $\beta<1$ for the tail integral in the effective-dimension proof to converge?
If $r=1/4$ and $\beta=1/2$, what powers of $n$ do the theorem give for $\lambda_n$ and prediction risk?
What additional statistical input, beyond eigenvalue decay, is required to apply the rate theorem to an estimator?
Why does $\mu_j=1/j$ prevent the effective-dimension argument from giving a finite variance bound at fixed positive $\lambda$?