Statistical and numerical limits of finite kernel solve guarantees

The Gram-perturbation and residual bounds are deterministic finite-training-vector statements. A statistical risk here would be expected loss under a data-generating probability law; these bounds contain no such law, expected loss, or generalization term, so they do not by themselves give a statistical risk guarantee.

For a test input $x_{\ast }$, the kernel prediction is $k_{\ast }^T{a}_K$, where $k_{\ast }=(k(x_{\ast },x_i){)}_{i=1}^n$. An approximation certificate for the training Gram matrix alone does not bound the test cross-kernel vector $k_{\ast }$; an out-of-sample error bound requires a separate cross-kernel certificate.

Under AC, suppose the finite real PSD kernel $k$ also has a real RKHS $\mathcal{H}$ with reproducing sections, use the zero mean $m=0$, and observe the canonical finite Gaussian process with independent noise covariance $\tau I_n$. In the GP/KRR theorem take noise standard deviation $\sigma =\sqrt{\tau }>0$. Writing $a_K(Y)=(K+\tau I_n{)}^{-1}Y$ and $u_K(Y)=K{a}_K(Y)$ for the random observation vector $Y$, the conditional-mean identity is

$\mathbb{E}[f_X\mid Y]=K(K+\tau I_n{)}^{-1}Y=u_K(Y)\text{almost surely}\mathrm{.}$

The shifted observed covariance $K+\tau I_n$ is positive definite because $\tau >0$. This optional interpretation uses the GP/KRR supplier and is separate from the choice-free deterministic matrix bounds.

For a fixed finite matrix $A\in {\mathbb{R}}^{m\times n}$ or ${\mathbb{C}}^{m\times n}$, the cited range-finder results assume iid standard real or normalized complex Gaussian sketches, integers $k,p\in \mathbb{N}$ with $k\ge 2$ and $p\ge 2$, sketch width $\mathrm{\ell }=k+p\le \min (m,n)$, exact arithmetic, and Countable Choice for the finite Gaussian probability law. They bound expected spectral error in those regimes. The theorem statements provide no per-draw bound or tail estimate for an arbitrary sketch supplied to the Nyström algorithm; a leverage-score or other sampling guarantee would require its own hypotheses and proof. The algorithm itself is specified in exact real arithmetic and includes residual statuses; no finite-precision rounding-error claim is made.

The deterministic Gram-perturbation bounds compare finite training coefficient and fitted vectors.

The residual certificate controls finite training coefficient and fitted-vector errors.

The finite-budget algorithm returns actual residuals and an explicit status.

Under AC, the finite zero-mean GP/KRR theorem identifies the training posterior mean with the kernel-ridge fitted vector.

The finite GP model defines the observation vector as latent training values plus independent centered Gaussian noise with the stated covariance.

Positive semidefinite kernels and reproducing kernel Hilbert spaces: A real RKHS with kernel $k$ contains its sections and satisfies the reproducing identity.

Inverse norm bound for a regularized Gram matrix: For $K⪰0$ and $\tau >0$, $K+\tau I_n$ is positive definite and invertible.

The real and normalized-complex Gaussian range-finder results are expectation bounds under the stated rank, oversampling, exact-arithmetic, and Countable Choice hypotheses.

Standard real and normalized complex Gaussian matrix laws: A normalized complex Gaussian entry is $(X+iY)\mathrm{/}\sqrt{2}$ for independent standard real Gaussian scalars, so its second absolute moment is one.

AC asserts that every family of nonempty sets has a choice function.

Countable Choice asserts choice for countable families of nonempty sets and is the axiom used for the finite-dimensional Gaussian-law interface.