Worked Polynomial-Spectrum Rate Calculations

From Spectral Decay to a Prediction Rate

For kernel ridge regression, the regularization parameter must control two competing effects: regularization bias and noise variance. Polynomial eigenvalue decay makes the variance increase at a predictable power of the inverse regularization level. A source condition, in turn, bounds the bias by a power of the regularization level. Putting these powers together gives an explicit rate calculation.

The purpose here is to carry out that calculation for several spectra and smoothness levels. The rates are consequences of a stated risk bound; they are not a claim that the same constants or finite-sample behavior apply to every sampling design.

Definition: Let $T$ be a positive covariance operator with positive eigenvalues $\mu_1\geq\mu_2\geq\cdots$. Polynomial eigenvalue decay with exponent $q>1$ means $\mu_j\asymp j^{-q}$. In the exact model $\mu_j=cj^{-q}$, where $c>0$, the effective dimension at regularization level $\lambda>0$ is $$ \mathcal{N}(\lambda)=\sum_{j\geq 1}\frac{\mu_j}{\mu_j+\lambda}. $$

The condition $q>1$ makes the exact polynomial spectrum summable, as is usual for a trace-class covariance operator. The effective dimension counts, with fractional weights, the eigen-directions that are appreciably represented at level $\lambda$. A source condition $f_*=T^r g$, with $\|g\|\leq R$ and $0<r\leq1$, expresses smoothness of the target relative to $T$.

We use the following common form of a prediction-risk upper bound:

\mathcal{R}(\lambda)\ \leq\ R^2\lambda^{2r} +\frac{\sigma^2}{n}\mathcal{N}(\lambda).

Here $\mathcal{R}(\lambda)$ is prediction risk, the first term bounds squared bias under the stated source condition, and the second is a variance bound under suitable noise and sampling assumptions. The calculation below assumes such a bound is available. In particular, the spectral and source exponents alone do not establish every sampling condition needed for it.

Why Polynomial Spectra Give a Power Law

For an exact spectrum $\mu_j=cj^{-q}$, substitute $h=(\lambda/c)^{1/q}$. Then $$ \mathcal{N}(\lambda)=\sum_{j\geq1}\frac{1}{1+(hj)^q}. $$ As $\lambda$ decreases, $h$ decreases, and the sum is approximated by an integral.

Result: If $q>1$ and $\mu_j=cj^{-q}$, then $$ \mathcal{N}(\lambda)\sim C_q\left(\frac{c}{\lambda}\right)^{1/q}, \qquad C_q=\int_0^\infty\frac{dx}{1+x^q}. $$ Consequently, if $\mu_j\asymp j^{-q}$, then $\mathcal{N}(\lambda)\asymp\lambda^{-1/q}$.

To prove the exact-spectrum statement, define $g(x)=(1+x^q)^{-1}$. This function is decreasing, nonnegative, and integrable on $[0,\infty)$, since $q>1$. Comparing rectangles with the area under $g$ gives $$ \int_h^\infty g(x)\,dx \leq h\sum_{j\geq1}g(hj) \leq\int_0^\infty g(x)\,dx. $$ The difference between the right-hand integral and the left-hand integral is $\int_0^h g(x)\,dx$, which is at most $h$, because $g(x)\leq1$. Thus $h\sum_{j\geq1}g(hj)$ converges to $C_q$ as $h$ tends to zero. Since $h^{-1}=(c/\lambda)^{1/q}$, the asserted asymptotic follows. If the eigenvalues are only comparable to $j^{-q}$, comparison of their summands with constant multiples of the exact-spectrum summands yields the two-sided order $\lambda^{-1/q}$. $\square$

Balancing the Two Terms

Write the effective-dimension order as $\mathcal{N}(\lambda)\asymp\lambda^{-1/q}$. Ignoring constants temporarily, the risk bound has the form $$ \lambda^{2r}+\frac{1}{n}\lambda^{-1/q}. $$ Making the terms the same order gives the regularization scale. This is an order calculation; minimizing a bound with specified constants gives a more precise expression.

Result: Suppose $r>0$, $q>1$, and a risk bound has the form $A\lambda^{2r}+(B/n)\lambda^{-1/q}$, with fixed $A,B>0$. Its minimizer over $\lambda>0$ is $$ \lambda_*=\left(\frac{B}{2rqA\,n}\right)^{q/(2rq+1)}. $$ In particular, $\lambda_*\asymp n^{-q/(2rq+1)}$, and the minimized bound is of order $n^{-2rq/(2rq+1)}$.

For the proof, differentiate the bound with respect to $\lambda$: $$ \frac{d}{d\lambda}\left(A\lambda^{2r}+\frac{B}{n}\lambda^{-1/q}\right) =2rA\lambda^{2r-1}-\frac{B}{qn}\lambda^{-1/q-1}. $$ The derivative vanishes exactly when $\lambda^{2r+1/q}=B/(2rqA n)$, which yields the displayed $\lambda_*$. The derivative is negative below this value and positive above it, so the point is the global minimizer. At this choice, $\lambda_*^{2r}$ has order $n^{-2rq/(2rq+1)}$. The variance term has the same order because the derivative equation also gives $$ \frac{B}{n}\lambda_*^{-1/q}=2rqA\lambda_*^{2r}. $$ Both terms therefore have the claimed order. $\square$

Worked Example: Quadratic Eigenvalue Decay and Half-Smooth Targets

Take $\mu_j=j^{-2}$, source exponent $r=1/2$, and the risk bound $$ R^2\lambda+\frac{\sigma^2}{n}\mathcal{N}(\lambda). $$ For $q=2$, the effective-dimension constant can be evaluated directly: $$ C_2=\int_0^\infty\frac{dx}{1+x^2} =\left[\arctan(x)\right]_0^\infty=\frac{\pi}{2}. $$ Thus $\mathcal{N}(\lambda)\sim(\pi/2)\lambda^{-1/2}$, and the leading-order bound is $R^2\lambda+(\sigma^2\pi/(2n))\lambda^{-1/2}$.

Differentiating this expression gives $R^2-(\sigma^2\pi/(4n))\lambda^{-3/2}$. Setting it to zero yields $$ \lambda_*=\left(\frac{\sigma^2\pi}{4R^2n}\right)^{2/3}. $$ The regularization order is $n^{-2/3}$. The bias has order $\lambda_* = n^{-2/3}$, and the variance has order $n^{-1}\lambda_*^{-1/2}=n^{-1}n^{1/3}=n^{-2/3}$. Hence the prediction-risk order is $n^{-2/3}$.

Changing the Smoothness and Spectral Exponents

The general calculation makes it possible to compare problems without repeating the optimization from scratch. Larger $q$ means faster eigenvalue decay, which reduces the effective dimension at a given small $\lambda$. Larger $r$ means a stronger source condition and a more rapidly decreasing bias bound. Both exponents enter the rate, but in different places.

Worked Example: Cubic Decay and a Quarter-Smooth Target

Let $\mu_j=j^{-3}$ and $r=1/4$. The effective dimension has order $\lambda^{-1/3}$, so the two terms have orders $\lambda^{1/2}$ and $n^{-1}\lambda^{-1/3}$. Equating them gives $\lambda^{1/2}=n^{-1}\lambda^{-1/3}$, or $\lambda^{5/6}=n^{-1}$. Therefore $$ \lambda_*\asymp n^{-6/5}. $$

Substituting into the bias gives $\lambda_*^{1/2}\asymp n^{-3/5}$. Substituting into the variance gives $n^{-1}\lambda_*^{-1/3}=n^{-1}n^{2/5}=n^{-3/5}$. The prediction-risk order is $n^{-3/5}$. For the exact spectrum, the effective-dimension constant is $C_3=2\pi/(3\sqrt{3})$, from integrating $(1+x^3)^{-1}$; this changes the leading constant in $\lambda_*$, not either rate exponent.

Worked Example: Slower Polynomial Decay

Let $\mu_j=j^{-3/2}$ and $r=1/4$. Now $q=3/2$, so $\mathcal{N}(\lambda)\asymp\lambda^{-2/3}$. The bias order is $\lambda^{1/2}$, and the variance order is $n^{-1}\lambda^{-2/3}$. Equating these terms gives $$ \lambda^{1/2}=n^{-1}\lambda^{-2/3}, \qquad \lambda^{7/6}=n^{-1}, \qquad \lambda_*\asymp n^{-6/7}. $$

The bias order is $\lambda_*^{1/2}\asymp n^{-3/7}$. The variance order is $n^{-1}\lambda_*^{-2/3}=n^{-1}n^{4/7}=n^{-3/7}$. Thus the prediction-risk order is $n^{-3/7}$. Compared with the cubic-decay example at the same source exponent, the slower spectral decay leads to a slower rate.

Worked Example: Stronger Smoothness with the Same Spectrum

Keep $\mu_j=j^{-2}$, but take $r=1$. Then the bias order is $\lambda^2$, while the variance order remains $n^{-1}\lambda^{-1/2}$. Balancing gives $\lambda^2=n^{-1}\lambda^{-1/2}$, so $\lambda^{5/2}=n^{-1}$ and $$ \lambda_*\asymp n^{-2/5}. $$

The bias order is $\lambda_*^2=n^{-4/5}$; the variance order is $n^{-1}\lambda_*^{-1/2}=n^{-1}n^{1/5}=n^{-4/5}$. The prediction-risk order is therefore $n^{-4/5}$. The regularization level here decays more slowly than in the first example, because the stronger smoothness already yields a smaller bias at a given $\lambda$.

Interpreting the Calculation Correctly

The rate summarizes how the selected upper bound changes with sample size. It does not say that $\lambda_*$ is a universal numerical choice: the leading constant depends on the bias and variance constants, and the bound itself depends on assumptions about the observations and noise. If the eigenvalues satisfy only $\mu_j\asymp j^{-q}$, the exponents remain valid while an exact effective-dimension constant may not be available.

A common mistake is to use $q$ instead of $1/q$ in the effective-dimension exponent. For $\mu_j\asymp j^{-q}$, the number of eigenvalues larger than $\lambda$ is roughly found by solving $j^{-q}\approx\lambda$, which gives $j\approx\lambda^{-1/q}$, not $\lambda^{-q}$. The effective-dimension calculation confirms this inverse exponent. Another mistake is to balance the two terms after substituting a candidate $\lambda$ without checking both: a valid rate calculation verifies that the bias and variance have the same order at the chosen scale.

Key takeaway: With polynomial eigenvalue decay $\mu_j\asymp j^{-q}$ and a source bias bound of order $\lambda^{2r}$, the effective-dimension variance order is $n^{-1}\lambda^{-1/q}$. Balancing gives $\lambda_*\asymp n^{-q/(2rq+1)}$ and prediction risk of order $n^{-2rq/(2rq+1)}$.

Check Your Understanding

Use the bias order $\lambda^{2r}$ and effective-dimension order $\lambda^{-1/q}$ in each calculation.

For $q=4$ and $r=1/2$, what are the regularization order and prediction-risk order?
For $q=2$ and $r=1/4$, write the two terms to balance and calculate the regularization order.
Why does $\mu_j\asymp j^{-q}$ lead to an effective-dimension order $\lambda^{-1/q}$, rather than $\lambda^{-q}$?
If the source exponent increases while $q$ stays fixed, how does the risk exponent $2rq/(2rq+1)$ change?
What additional role do the constants in the risk bound play beyond determining the rate exponents?