High-Probability KRR Bounds via Concentration

Why High-Probability Bounds Need Two Controls

An expected prediction error can be small even when a particular training sample produces an unstable fit. A high-probability guarantee addresses that distinction: it bounds the prediction error and states how often the bound can fail. For kernel ridge regression, the finite-sample argument has two separate tasks. The empirical covariance must stay close to its population counterpart, and the random noise must not produce an unusually large contribution after regularization.

We derive a bound using second moments and Markov's inequality. This gives transparent finite-sample constants, though its dependence on the confidence level is generally less sharp than bounds obtained from stronger concentration inequalities. The result is useful because it shows precisely where the kernel bound, regularization parameter, effective dimension, sample size, and noise variance enter.

Setup and Notation

Let \(\mathcal H\) be a separable reproducing kernel Hilbert space with feature map \(\Phi(x)=K(x,\cdot)\), so that \(K(x,x)=\|\Phi(x)\|_{\mathcal H}^{2}\). Suppose the observations \((X_i,Y_i)\), \(i=1,\ldots,n\), are independent and identically distributed, and satisfy \(Y_i=f_*(X_i)+\varepsilon_i\), where \(f_*\in\mathcal H\), \(E[\varepsilon_i\mid X_i]=0\), and \(E[\varepsilon_i^2\mid X_i]\leq\sigma^2\) almost surely. Assume the kernel is bounded: \(K(x,x)\leq\kappa^2\) almost surely. These conditions make the operators and expectations below well-defined.

For \(u,v\in\mathcal H\), write \(u\otimes v\) for the rank-one operator \(h\mapsto\langle v,h\rangle_{\mathcal H}u\). The population covariance operator and its empirical version are

For a regularization parameter \(\lambda>0\), define \(A_\lambda=T+\lambda I\), where \(I\) is the identity on \(\mathcal H\), and define the effective dimension

Boundedness of the kernel implies that \(T\) is positive and trace class, and \(\mathcal N(\lambda)\) is finite. The empirical kernel ridge estimator is the minimizer over \(f\in\mathcal H\) of \(\frac{1}{n}\sum_{i=1}^n(Y_i-f(X_i))^2+\lambda\|f\|_{\mathcal H}^2\). Its normal equation is \((T_n+\lambda I)\hat f_\lambda=\frac{1}{n}\sum_{i=1}^nY_i\Phi(X_i)\).

Controlling the Empirical Covariance

It is convenient to compare \(T_n\) and \(T\) after scaling both sides by \(A_\lambda^{-1/2}\). Set \(U_\lambda=A_\lambda^{-1/2}\Phi(X)\) and \(Z_\lambda=U_\lambda\otimes U_\lambda\). Then \(E[Z_\lambda]=A_\lambda^{-1/2}TA_\lambda^{-1/2}\), whose trace is \(\mathcal N(\lambda)\). Also, \(\|U_\lambda\|_{\mathcal H}^{2}\leq\kappa^2/\lambda\), since \(A_\lambda\geq\lambda I\).

Proof. Let \(Z_{\lambda,i}\) be the version of \(Z_\lambda\) formed from \(X_i\), and let \(S_\lambda=E[Z_\lambda]\). The whitened difference equals \(n^{-1}\sum_{i=1}^n(Z_{\lambda,i}-S_\lambda)\). These are independent, mean-zero random elements of the Hilbert space of Hilbert–Schmidt operators. For independent mean-zero Hilbert-space random elements, the expected squared norm of their sum is the sum of their expected squared norms: each cross inner product has expectation zero by independence and mean zero. Therefore,

The inequality follows by expanding the squared norm and using \(E\|Z_\lambda-S_\lambda\|_{\mathrm{HS}}^2 =E\|Z_\lambda\|_{\mathrm{HS}}^2-\|S_\lambda\|_{\mathrm{HS}}^2\). For a rank-one operator \(u\otimes u\), \(\|u\otimes u\|_{\mathrm{HS}}=\|u\|_{\mathcal H}^2\). Hence \(\|Z_\lambda\|_{\mathrm{HS}}^2=\|U_\lambda\|_{\mathcal H}^4 \leq(\kappa^2/\lambda)\|U_\lambda\|_{\mathcal H}^2\). Taking expectations gives \(E\|U_\lambda\|_{\mathcal H}^2=\operatorname{Tr}(A_\lambda^{-1/2}TA_\lambda^{-1/2})=\mathcal N(\lambda)\). This proves the second-moment bound. The operator norm is at most the Hilbert–Schmidt norm, so Markov's inequality applied to the squared Hilbert–Schmidt norm gives the probability statement. \(\square\)

Controlling the Noise

Define the empirical noise element \(\eta_n=n^{-1}\sum_{i=1}^n\varepsilon_i\Phi(X_i)\). The next bound controls the noise in the same whitened scale used for the covariance.

Proof. The random elements \(\varepsilon_iA_\lambda^{-1/2}\Phi(X_i)\) are independent and have mean zero, because \(E[\varepsilon_i\mid X_i]=0\). As in the preceding proof, cross inner products between different observations have expectation zero. Thus

The inequality uses \(E[\varepsilon^2\mid X]\leq\sigma^2\); the last equality is the trace identity defining \(\mathcal N(\lambda)\). Markov's inequality applied to the squared norm proves the probability bound. If \(\sigma^2\mathcal N(\lambda)=0\), the expectation on the left is zero, so \(A_\lambda^{-1/2}\eta_n=0\) almost surely. This handles the zero-threshold case directly, without applying the positive-threshold statement at \(s=0\). \(\square\)

A Finite-Sample Prediction Bound

The two propositions give simultaneous control with probability at least \(1-\delta\). Use confidence level \(\delta/2\) for each event. For the covariance event, the resulting threshold is \(\sqrt{2\kappa^2\mathcal N(\lambda)/(n\lambda\delta)}\); for the noise event, it is \(\sqrt{2\sigma^2\mathcal N(\lambda)/(n\delta)}\). The noise threshold is zero if \(\sigma^2\mathcal N(\lambda)=0\), in which case the preceding zero-expectation argument gives the event with probability one.

Proof. Put \(D_\lambda=A_\lambda^{-1/2}(T_n-T)A_\lambda^{-1/2}\) and \(C_\lambda=A_\lambda^{-1/2}(T_n+\lambda I)A_\lambda^{-1/2}\). Since \(A_\lambda=T+\lambda I\), we have \(C_\lambda=I+D_\lambda\). On the covariance event, \(\|D_\lambda\|_{\mathrm{op}}\leq1/2\), so \(\langle h,C_\lambda h\rangle_{\mathcal H}\geq\frac12\|h\|_{\mathcal H}^2\) for every \(h\in\mathcal H\). Therefore \(C_\lambda\) is invertible and \(\|C_\lambda^{-1}\|_{\mathrm{op}}\leq2\).

The regression model gives \(n^{-1}\sum_iY_i\Phi(X_i)=T_nf_*+\eta_n\). Subtracting \((T_n+\lambda I)f_*\) from the estimator's normal equation yields \((T_n+\lambda I)(\hat f_\lambda-f_*)=\eta_n-\lambda f_*\). Multiplying by the appropriate inverse factors gives

Because \(T\leq A_\lambda\), the prediction norm is no larger than the corresponding \(A_\lambda\)-scaled norm: \(\|T^{1/2}h\|_{\mathcal H}\leq\|A_\lambda^{1/2}h\|_{\mathcal H}\). On the joint covariance and noise event, the triangle inequality and \(\|C_\lambda^{-1}\|_{\mathrm{op}}\leq2\) therefore imply

Each event fails with probability at most \(\delta/2\), so the union bound gives joint probability at least \(1-\delta\). Finally \(A_\lambda^{-1}\leq\lambda^{-1}I\), which implies \(\lambda\|A_\lambda^{-1/2}f_*\|_{\mathcal H}\leq\sqrt{\lambda}\|f_*\|_{\mathcal H}\). \(\square\)

Interpretation and a Common Pitfall

The effective dimension measures how many directions of the feature space remain influential at regularization level \(\lambda\). It appears in both concentration terms because both the empirical covariance and the noise are assessed in the same regularized scale. The covariance condition is more demanding as \(\lambda\) decreases: its threshold contains \(1/\lambda\). A smaller \(\lambda\) can reduce regularization bias, but it makes the empirical inverse harder to control at a fixed sample size.

Common pitfall: mixing up whitened and unwhitened noise bounds. The theorem controls \(\|A_\lambda^{-1/2}\eta_n\|_{\mathcal H}\), whose second moment is bounded by \(\sigma^2\mathcal N(\lambda)/n\). It is incorrect to insert an extra factor \(1/\lambda\) into this bound without changing the quantity being controlled. Conversely, a bound for the unwhitened noise element \(\eta_n\) cannot be substituted into the theorem without accounting for the inverse operator. Keep the random quantity, its second-moment bound, and its threshold in the same scale.

A second useful check is to handle zero variance or zero effective dimension explicitly. Markov's inequality with a positive threshold does not by itself justify a zero-threshold event. Here a zero second moment implies that the corresponding random norm is zero almost surely, which supplies the needed conclusion. The resulting guarantee is high probability but has a \(1/\delta\) dependence inside the square roots; it should not be confused with a sharper exponential-tail bound.