When Kernel Ridge Attains Minimax Rates

What It Means for Kernel Ridge to Attain a Minimax Rate

A kernel ridge regression (KRR) upper bound says that a particular estimator performs at most a certain prediction risk over a specified class of regression functions. A minimax lower bound says that no estimator can do better, up to constants, over a specified statistical model and function class. If the two bounds have the same dependence on sample size, KRR attains the minimax rate for that comparison.

This conclusion depends on matching the assumptions. The eigenvalue decay determines how many directions contribute appreciably to variance; the source condition determines how rapidly regularization bias can shrink; and the noise must be sufficiently present for a positive lower bound. A rate match is informative only when both bounds describe the same smoothness class and compatible noise regimes.

We use the covariance-scale source convention \(f_* = T^r g\), where \(T\) is the population covariance operator, \(g\) is a function with bounded \(L^2(P_X)\) norm, and \(0<r\leq 1\). The restriction here keeps the bias bound in its standard, nonsaturated range. Write \(\mu_j\) for the positive eigenvalues of \(T\), in decreasing order. The effective dimension is \(N(\lambda)=\sum_j \mu_j/(\mu_j+\lambda)\), where \(\lambda>0\) is the regularization parameter.

Under the usual conditions for the KRR prediction-risk bound—for example, a bounded kernel, independent observations, conditionally mean-zero errors with conditional variance bounded above, and the sample-operator conditions needed for the bound—we use the following form:

Here \(C\) does not depend on \(n\) or \(\lambda\) in the range under consideration, and \(\sigma^2\) is an upper bound on the conditional noise variance. The first term is the source-condition bias bound; the second is the effective-dimension variance bound. We will compare this upper bound with a lower bound in a specified diagonal Gaussian sequence model.

Polynomial Eigenvalue Decay: The Rate Balance

Suppose the eigenvalues satisfy \(\mu_j\asymp j^{-1/p}\) for some \(0<p<1\), where \(\asymp\) means bounded above and below by positive constant multiples. In this regime, the effective dimension has order \(\lambda^{-p}\). Thus, ignoring constants that do not depend on \(n\), the KRR risk bound is \(R^2\lambda^{2r}+\sigma^2 n^{-1}\lambda^{-p}\).

To verify the balance, set \(\lambda^{2r}\) of the same order as \(n^{-1}\lambda^{-p}\). Multiplication by \(\lambda^p\) gives \(\lambda^{2r+p}\asymp n^{-1}\), hence \(\lambda\asymp n^{-1/(2r+p)}\). Substitution into the bias term gives \(\lambda^{2r}\asymp n^{-2r/(2r+p)}\); substitution into the variance term gives the same order. This establishes the claimed upper-bound rate. \(\square\)

A Diagonal Lower Bound

For a precise comparison, consider the Gaussian sequence experiment \(Z_j=f_j+\sigma n^{-1/2}\xi_j\), independently over \(j\), where the \(\xi_j\) are independent \(N(0,1)\) variables and \(\sigma>0\) is fixed. Prediction loss is \(\sum_j(\widehat f_j-f_j)^2\). The source class is the ellipsoid \(\mathcal F_r(R)=\{f:\sum_j f_j^2/\mu_j^{2r}\leq R^2\}\). This is the diagonal counterpart of \(f_*=T^r g\) with \(\|g\|_{L^2(P_X)}\leq R\).

Here is a proof. Choose an integer \(m\) of order \(n^{p/(2r+p)}\), and consider a hypercube of signals supported on coordinates \(m+1,\ldots,2m\), with each such coordinate equal to either \(a\) or \(-a\), where \(a=c_0\sigma n^{-1/2}\) and \(c_0=1/4\). The lower eigenvalue bound implies that for these coordinates, \(\mu_j^{-2r}\leq c_1^{-2r}(2m)^{2r/p}\). Every vertex of the hypercube therefore has ellipsoid sum at most \(m a^2 c_1^{-2r}(2m)^{2r/p}\). Since \(m\) is of order \(n^{p/(2r+p)}\), this expression is at most a constant times \(c_0^2\sigma^2\). Choosing the constant in \(m\) sufficiently small makes it no larger than \(R^2\); all vertices belong to \(\mathcal F_r(R)\).

Two vertices differing only in coordinate \(j\) have Gaussian observation distributions whose Kullback–Leibler divergence is \((2a)^2/(2\sigma^2/n)=2na^2/\sigma^2=2c_0^2\). Pinsker's inequality, in the form \(\operatorname{TV}(P,Q)\leq\sqrt{\operatorname{KL}(P,Q)/2}\), bounds their total variation distance by \(c_0=1/4\). For any estimator, deciding whether its \(j\)th estimate is nearer \(a\) or \(-a\) defines a test of these two vertices. When that decision is wrong, the squared coordinate error is at least \(a^2\). The sum of the two testing error probabilities is at least one minus the total variation distance, so their average is at least \(3/8\).

Average the risk over all \(2^m\) vertices. For each of the \(m\) coordinates, pair vertices that differ only in that coordinate. The testing bound implies an average squared error of at least \(3a^2/8\) on that coordinate. Summing gives average risk at least \(3ma^2/8\), and the worst-case risk is no smaller. Since \(m\asymp n^{p/(2r+p)}\) and \(a^2=c_0^2\sigma^2/n\), this lower bound has order \(m/n\asymp n^{p/(2r+p)-1}=n^{-2r/(2r+p)}\). The constants are positive because \(R\) and \(\sigma\) are positive. This proves the result. \(\square\)

The upper and lower exponents agree. Consequently, when the diagonal experiment is a submodel of the regression problem under comparison and the KRR upper bound holds uniformly over the same source ball, KRR is minimax-rate optimal there. The lower bound by itself applies to the diagonal experiment; it does not automatically establish a lower bound for a different regression model.

Other Spectra and What Must Match

The same comparison can be made using the effective dimension directly, without forcing a polynomial exponent. For example, with exponentially decaying eigenvalues \(\mu_j\asymp e^{-aj}\), \(a>0\), the number of eigenvalues appreciably larger than \(\lambda\) is of order \(\log(1/\lambda)\). Thus \(N(\lambda)\asymp\log(1/\lambda)\). Balancing \(\lambda^{2r}\) with \(n^{-1}\log(1/\lambda)\) yields a risk of order \((\log n)/n\). A matching diagonal ellipsoid lower bound has the same order: roughly \(\log n\) coordinates can carry signals at the noise scale, giving cumulative risk of order \((\log n)/n\). The polynomial formula should not be used for this spectrum; the effective-dimension growth is different.

Noise assumptions matter just as much. The KRR variance bound uses an upper bound on conditional variance. A lower bound of the displayed Gaussian form needs positive noise variance: if \(\sigma=0\), the testing distributions used in the proof are distinguishable without noise, and that proof gives no positive noisy minimax rate. If noise variance changes with \(n\), it must appear in the balance rather than being treated as a fixed constant.

Common Mistakes and Practical Interpretation

• Comparing different source classes. The exponent \(r\) defines the ellipsoid used in the lower bound as well as the bias bound used in the upper bound. A lower bound for one value of \(r\) cannot certify optimality for a different smoothness class.
• Calling an upper bound a minimax result. An estimator's risk guarantee does not rule out a better estimator. A matching lower bound is needed, and it must apply to the same statistical model or to a submodel of it.
• Using the wrong spectral summary. Polynomial and exponential eigenvalue decay give different effective-dimension growth. The balancing step must use the actual behavior of \(N(\lambda)\).
• Ignoring noise in the lower bound. A positive noisy lower bound requires nondegenerate noise. If the noise level varies with sample size, the rate balance and lower-bound construction must account for that variation.

The useful comparison is therefore a sequence of checks: specify the prediction norm and source ball, determine the effective-dimension order from the eigenvalues, balance the KRR bias and variance, and verify that a lower-bound construction fits the same source ball and noise regime. When these checks agree, the rate match is evidence of genuine minimax-rate attainment, not just a convenient algebraic coincidence.