Noise Conditions Behind KRR Variance Rates

Why the Noise Assumption Matters

Kernel ridge regression (KRR) shrinks fitted directions according to their empirical covariance and the regularization parameter. The variance of its prediction error also depends on how much noise enters those directions. A constant conditional noise variance gives an exact spectral formula; a uniform variance bound gives an upper bound; and a conditional sub-Gaussian assumption is a stronger distributional condition that, in particular, supplies such a variance bound.

The distinction is useful because these assumptions do different jobs. The fixed-design variance calculations below need only conditional second moments and independence across observations. Stronger tail assumptions are useful for probability bounds, but they do not by themselves control how the observed design represents the population. The results here concern the noise contribution to prediction error, not the regularization bias or the additional effects of random design.

Setup and Noise Conditions

Let \(\mathcal H\) be a reproducing kernel Hilbert space with kernel \(k\), and write \(k_x=k(x,\cdot)\in\mathcal H\). Conditional on observed inputs \(X_1,\ldots,X_n\), suppose the responses satisfy \(Y_i=f_*(X_i)+\varepsilon_i\), where \(E[\varepsilon_i\mid X_1,\ldots,X_n]=0\). Assume the errors are conditionally independent across \(i\), with finite conditional variances \(\sigma_i^2=\operatorname{Var}(\varepsilon_i\mid X_1,\ldots,X_n)\). The KRR estimator minimizes the average squared error plus a squared-norm penalty.

Define the empirical covariance operator \(T_n:\mathcal H\to\mathcal H\) and the noise-weighted covariance operator \(T_{n,\sigma}\) by

where \((u\otimes v)h=\langle v,h\rangle_{\mathcal H}u\). The empirical prediction norm is \(\|h\|_{T_n}^2=\langle h,T_nh\rangle_{\mathcal H}\). It measures squared prediction error averaged over the observed inputs.

A common way to obtain a variance bound is bounded centered noise: if \(|\varepsilon_i|\le M\) almost surely and its conditional mean is zero, then \(\sigma_i^2\le M^2\). A centered conditionally sub-Gaussian error has conditional variance at most \(\tau^2\), so it also satisfies a uniform variance bound. Neither condition requires the errors to have a common distribution across inputs.

The Fixed-Design Variance Formula

For fixed inputs, the KRR solution is linear in the responses. Its component due solely to the errors is \(\hat f_{\lambda,\varepsilon}=(T_n+\lambda I)^{-1}n^{-1}\sum_i\varepsilon_i k_{X_i}\). This is the random part whose conditional prediction variance we calculate. The formula makes clear that the noise level and the regularized directions both matter.

Proof. Set \(A=(T_n+\lambda I)^{-1}\) and \(g=n^{-1}\sum_i\varepsilon_i k_{X_i}\), so that \(\hat f_{\lambda,\varepsilon}=Ag\). Conditional independence and zero conditional means make every cross term in the covariance of \(g\) vanish. Thus

For any square-integrable Hilbert-space-valued random variable \(Z\) and positive finite-rank operator \(T_n\), \(E[\langle Z,T_nZ\rangle]=\operatorname{tr}(T_nE[Z\otimes Z])\); here this follows by expanding in an orthonormal basis of the finite-dimensional span of the observed feature vectors. Apply this identity to \(Z=Ag\). Since \(A\) is self-adjoint, \(E[(Ag)\otimes(Ag)\mid X_1,\ldots,X_n] =A\,E[g\otimes g\mid X_1,\ldots,X_n]\,A\). Substituting the covariance of \(g\) and using cyclic invariance of the finite-rank trace gives the stated formula. \(\square\)

From Noise Assumptions to Effective Dimension

In the homoscedastic case, \(T_{n,\sigma}=\sigma^2T_n\). If \(t_1,\ldots,t_r\) are the positive eigenvalues of \(T_n\), the theorem therefore gives an exact spectral sum. The effective dimension at \(\lambda\) is \(N_n(\lambda)=\operatorname{tr}[T_n(T_n+\lambda I)^{-1}]\). Each term in the exact variance sum is no larger than its corresponding effective-dimension term.

To verify the inequality, \(t_j\ge0\) and \(\lambda>0\) imply \(0\le t_j/(t_j+\lambda)\le1\), and hence \((t_j/(t_j+\lambda))^2\le t_j/(t_j+\lambda)\). Summing and multiplying by \(\sigma^2/n\) proves the claim.

The same effective-dimension bound holds when noise is heteroscedastic but uniformly bounded in variance. In operator order, \(T_{n,\sigma}\preceq vT_n\), because for every \(h\in\mathcal H\),

Consequently the trace formula is bounded by the same expression with \(T_{n,\sigma}\) replaced by \(vT_n\). This replacement is valid because, for positive operators \(B\preceq C\) and positive \(A,T_n\), \(\operatorname{tr}(T_nABA)\le\operatorname{tr}(T_nACA)\): the difference is the trace of a product of positive operators, equivalently \(\operatorname{tr}(A T_n A(C-B))\ge0\). Applying the spectral inequality above gives the result.

Worked Examples

What These Bounds Do—and Do Not—Say

The factor \(N_n(\lambda)/n\) describes the variance cost of fitting the observed inputs after regularization. Homoscedasticity identifies that cost precisely through a spectral sum. A uniform conditional variance bound controls it even when noise levels vary across inputs. A conditional sub-Gaussian assumption implies such a bound and also supplies tail information that can support stronger probability statements.

These are conditional, empirical prediction bounds. They do not automatically bound integrated prediction error under the population distribution of \(X\): the empirical norm weights observed inputs, whereas population risk weights inputs according to their distribution. Relating the two requires control of how the empirical covariance represents the population covariance, in addition to assumptions on the noise. A noise tail condition alone does not supply that design control.

Common Mistake

A common mistake is to treat “sub-Gaussian noise” as if it automatically proved a high-probability population-risk bound. The condition controls the conditional tails of the errors; it does not ensure that the observed inputs cover the directions important under the population distribution. Another mistake is to use a constant-variance formula when the variance changes with \(X_i\). In that case the exact expression involves \(T_{n,\sigma}\), and the simple effective-dimension bound follows only after establishing a uniform variance bound (or another suitable operator comparison).