Sketched kernel learning and certified approximate solves

Let $\mathcal{X}$ be a set, $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ a real positive-semidefinite kernel, and $\mathcal{H}$ a real reproducing-kernel Hilbert space with kernel $k$. Let $X=(x_i{)}_{i=1}^n$ be a nonempty finite ordered training list in $\mathcal{X}$, let $K=(k(x_i,x_j){)}_{i,j=1}^n$, let $y\in {\mathbb{R}}^n$, and let $\lambda >0$. Set $\tau =n\lambda$ and define the mean-square empirical objective

$J(f)=\frac{1}{n}{\sum }_{i=1}^n(y_i-f(x_i){)}^2+\lambda \parallel f{\parallel }_{\mathcal{H}}^2\mathrm{.}$

For any finite real symmetric positive-semidefinite matrix $G\in {\mathbb{R}}^{n\times n}$, define its regularized kernel prediction system by $a_G=(G+\tau I_n{)}^{-1}y$ and $u_G=G{a}_G$, where $I_n$ is the $n\times n$ identity matrix. The original training system uses $G=K$. The same definition applies to any positive-semidefinite matrix approximation $\tilde{K}$ of $K$, with $a_{\tilde{K}}=(\tilde{K}+\tau I_n{)}^{-1}y$ and $u_{\tilde{K}}=\tilde{K}{a}_{\tilde{K}}$. In either case $u_G=y-\tau a_G$. The scalar $\tau =n\lambda$ fixes the normalization between mean-square loss and the unnormalized finite linear system.

A real positive-semidefinite kernel has nonnegative finite Gram quadratic forms, and its RKHS reproduces the kernel sections.

The definitions allow $K$ to be singular or zero. More generally, for every finite real symmetric positive-semidefinite $G$ and $\tau >0$, each nonzero $x$ satisfies $x^T(G+\tau I_n)x=x^{T}Gx+\tau \parallel x{\parallel }_2^2\ge \tau \parallel x{\parallel }_2^2>0$. Thus each shifted matrix in the definition is positive definite and invertible, including when $G=K$ or $G=\tilde{K}$; no full-rank assumption is placed on the kernel Gram matrix or on a sketch.

Let $M,N\in {\mathbb{R}}^{n\times n}$ be symmetric matrices such that $x^{T}Mx\ge 0$ and $x^{T}Nx\ge 0$ for every $x\in {\mathbb{R}}^n$, where $n\ge 1$, and let $\tau >0$. Write $I_n$ for the identity matrix, $A=M+\tau I_n$, and $B=N+\tau I_n$. For vectors use $\parallel x{\parallel }_2=({\sum }_i{x}_i^2{)}^{1\mathrm{/}2}$, and for a matrix $T$ use the induced Euclidean norm $\parallel T{\parallel }_2={\sup }_{\parallel x{\parallel }_2=1}\parallel Tx{\parallel }_2$. Positive definite means $x^{T}Ax>0$ for every nonzero $x$, and analogously for $B$. Then $A$ and $B$ are positive definite and invertible, $\parallel A^{-1}{\parallel }_2,\parallel B^{-1}{\parallel }_2\le 1\mathrm{/}\tau$, and

$A^{-1}-B^{-1}=A^{-1}(N-M)B^{-1},\parallel A^{-1}-B^{-1}{\parallel }_2\le \frac{\parallel M-N{\parallel }_2}{{\tau }^2}\mathrm{.}$

A finite-dimensional real symmetric positive-semidefinite operator has an orthonormal eigenbasis with nonnegative eigenvalues.

Let $\mathcal{X}$ be a set, let $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ be a real positive-semidefinite kernel, and let $\mathcal{H}$ be a real reproducing-kernel Hilbert space with kernel $k$. Take a finite ordered list $X=(x_i{)}_{i=1}^n$ with $n\ge 1$, a response vector $y\in {\mathbb{R}}^n$, and $\lambda >0$. Put $K=(k(x_i,x_j){)}_{i,j=1}^n$ and $\tau =n\lambda$. Define $a=(K+\tau I_n{)}^{-1}y$, $f_0={\sum }_{i=1}^n{a}_{i}k(\cdot ,x_i)$, and $u=Ka$. Then $f_0$ is the unique minimizer over $f\in \mathcal{H}$ of

$J(f)=\frac{1}{n}{\sum }_{i=1}^n(y_i-f(x_i){)}^2+\lambda \parallel f{\parallel }_{\mathcal{H}}^2,$

and its training evaluation vector is $u=y-\tau a$.

Positive semidefinite kernels and reproducing kernel Hilbert spaces: A real RKHS contains each kernel section and satisfies $⟨f,k(\cdot ,x){⟩}_{\mathcal{H}}=f(x)$.

Regularized kernel prediction system: The coefficient and fitted vectors are defined by $a=(K+\tau I{)}^{-1}y$ and $u=Ka=y-\tau a$.

Let $K,\tilde{K}\in {\mathbb{R}}^{n\times n}$ be symmetric matrices such that $x^{T}Kx\ge 0$ and $x^T\tilde{K}x\ge 0$ for every $x\in {\mathbb{R}}^n$, with $n\ge 1$, let $y\in {\mathbb{R}}^n$, and let $\tau >0$. Write $I_n$ for the identity matrix. For $G\in \{K,\tilde{K}\}$ define $a_G=(G+\tau I_n{)}^{-1}y$ and $u_G=G{a}_G$. Define $\parallel x{\parallel }_2=({\sum }_i{x}_i^2{)}^{1\mathrm{/}2}$ for vectors and $\parallel M{\parallel }_2={\sup }_{\parallel x{\parallel }_2=1}\parallel Mx{\parallel }_2$ for matrices. If $\parallel K-\tilde{K}{\parallel }_2\le \delta$ for some $\delta \ge 0$, then

$\parallel a_K-a_{\tilde{K}}{\parallel }_2\le \frac{\delta \parallel y{\parallel }_2}{{\tau }^2},\parallel u_K-u_{\tilde{K}}{\parallel }_2\le \frac{\delta \parallel y{\parallel }_2}{\tau }\mathrm{.}$

In particular, let $S\in {\mathbb{R}}^{n\times s}$ with $s\ge 0$ and $\tilde{K}=KS(S^{T}KS{)}^{†}{S}^{T}K$, where $M^{†}$ denotes the unique matrix satisfying the four Moore–Penrose equations. Choose $0\le r\le n$ and an orthogonal eigenbasis $K=U\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)U^T$ with $U^{T}U=I_n$ and ${\lambda }_1\ge \cdots \ge {\lambda }_n\ge 0$. Write $U=(U_1{U}_2)$ with the first $r$ eigenvectors in $U_1$, let ${\mathrm{\Lambda }}_2=\mathrm{diag}({\lambda }_{r+1},\dots ,{\lambda }_n)$ and ${\mathrm{\Lambda }}_2^{1\mathrm{/}2}=\mathrm{diag}(\sqrt{{\lambda }_{r+1}},\dots ,\sqrt{{\lambda }_n})$, and set ${\mathrm{\Omega }}_1=U_1^{T}S$ and ${\mathrm{\Omega }}_2=U_2^{T}S$. If ${\mathrm{\Omega }}_1$ has full row rank, meaning $\mathrm{rank}({\mathrm{\Omega }}_1)=r$, with the empty-row convention when $r=0$, then the same bounds hold with $\delta ={\lambda }_{r+1}+\parallel {\mathrm{\Lambda }}_2^{1\mathrm{/}2}{\mathrm{\Omega }}_2{\mathrm{\Omega }}_1^{†}{\parallel }_2^2$, using ${\lambda }_{n+1}=0$ and zero norm for empty blocks.

Regularized kernel prediction system: The systems use $a_G=(G+\tau I{)}^{-1}y$ and $u_G=G{a}_G=y-\tau a_G$.

The positive-semidefinite Nyström approximation: The Nyström approximation is $KS(S^{T}KS{)}^{†}{S}^{T}K$.

The Nyström approximation is positive semidefinite.

Under the full-row-rank leading-sketch hypothesis, the displayed deterministic spectral residual bound holds.

The Moore–Penrose inverse is the unique matrix satisfying the four Penrose equations.

Let $K\in {\mathbb{R}}^{n\times n}$ be symmetric with $x^{T}Kx\ge 0$ for every $x\in {\mathbb{R}}^n$ and $n\ge 1$, let $y\in {\mathbb{R}}^n$, and let $\tau >0$. Write $I_n$ for the identity matrix. Define $a=(K+\tau I_n{)}^{-1}y$ and $u=Ka$. For any vector $b\in {\mathbb{R}}^n$, define the actual residual $r=y-(K+\tau I_n)b$. Define $\parallel x{\parallel }_2=({\sum }_i{x}_i^2{)}^{1\mathrm{/}2}$ and $\parallel M{\parallel }_2={\sup }_{\parallel x{\parallel }_2=1}\parallel Mx{\parallel }_2$; then

$\parallel b-a{\parallel }_2\le \frac{\parallel r{\parallel }_2}{\tau },\parallel Kb-u{\parallel }_2\le \frac{\parallel K{\parallel }_2\parallel r{\parallel }_2}{\tau }\mathrm{.}$

Regularized kernel prediction system: The exact coefficient and fitted vectors solve $(K+\tau I)a=y$ and $u=Ka$.

Inverse norm bound for a regularized Gram matrix: The shifted Gram inverse has induced norm at most $1\mathrm{/}\tau$.

All matrix-vector operations below use exact real arithmetic. The inputs are a finite real symmetric matrix $K\in {\mathbb{R}}^{n\times n}$ with $n\ge 1$ and $x^{T}Kx\ge 0$ for every $x\in {\mathbb{R}}^n$, a vector $y\in {\mathbb{R}}^n$, a scalar $\tau >0$, a finite sketch $S\in {\mathbb{R}}^{n\times s}$ with $s\ge 0$, a residual tolerance $\eta \ge 0$, and a finite nonnegative integer iteration budget $T$. Write $I_n$ for the identity matrix and $\parallel x{\parallel }_2=({\sum }_i{x}_i^2{)}^{1\mathrm{/}2}$ for the Euclidean norm. The Moore–Penrose inverse $M^{†}$ is the unique matrix satisfying $M{M}^{†}M=M$, $M^{†}M{M}^{†}=M^{†}$, $(M{M}^{†}{)}^T=M{M}^{†}$, and $(M^{†}M{)}^T=M^{†}M$.

1. Form the Nyström matrix $\tilde{K}=KS(S^{T}KS{)}^{†}{S}^{T}K$. The formula is defined even when $S^{T}KS$ is singular or $s=0$.

2. Set $B=\tilde{K}+\tau I_n$. Initialize $b_0=0$, ${\tilde{r}}_0=y-B{b}_0=y$, and $p_0={\tilde{r}}_0$.

3. For $j=0,1,\dots ,T$, recompute the actual residuals ${\tilde{r}}_j=y-B{b}_j$ and $r_j=y-(K+\tau I_n)b_j$. If both norms are at most $\eta$, return status certified, coefficient vector $b_j$, fitted vector $\tilde{K}{b}_j$, and both residuals. If ${\tilde{r}}_j=0$ but $\parallel r_j{\parallel }_2>\eta$, return status uncertified with the same outputs. If $j=T$ and neither return condition holds, return status budget-exhausted with the same outputs.

4. Otherwise compute $q_j=B{p}_j$. If $p_j^T{q}_j=0$, return status uncertified with the current outputs. If $p_j^T{q}_j>0$, set ${\alpha }_j=({\tilde{r}}_j^T{\tilde{r}}_j)\mathrm{/}(p_j^T{q}_j)$, $b_{j+1}=b_j+{\alpha }_j{p}_j$, and ${\tilde{r}}_{j+1}={\tilde{r}}_j-{\alpha }_j{q}_j$. If ${\tilde{r}}_{j+1}=0$, recompute $r_{j+1}$ and return certified when $\parallel r_{j+1}{\parallel }_2\le \eta$, and otherwise return uncertified, together with the resulting outputs. If ${\tilde{r}}_{j+1}\mathrm{\ne }0$, set ${\beta }_j=({\tilde{r}}_{j+1}^T{\tilde{r}}_{j+1})\mathrm{/}({\tilde{r}}_j^T{\tilde{r}}_j)$ and $p_{j+1}={\tilde{r}}_{j+1}+{\beta }_j{p}_j$, then continue at the next iteration.

The output always includes the actual residuals for both the Nyström system and the original system. certified asserts that both residuals meet the requested tolerance; uncertified and budget-exhausted make no solve-accuracy claim. In particular, exhausting the budget does not certify a solve. If $K$ is a Gram matrix and $\tau =n\lambda$, the original-system residual is the one used in the residual prediction certificate.

The positive-semidefinite Nyström approximation: For a PSD matrix $K$, the Nyström matrix is $KS(S^{T}KS{)}^{†}{S}^{T}K$.

Nyström is positive semidefinite, dominated by A, and exact when it captures the range: Every such Nyström matrix is positive semidefinite and is bounded above by $K$.

Inverse norm bound for a regularized Gram matrix: Adding $\tau I$ with $\tau >0$ makes the Nyström system positive definite.

The four equations stated above define a Moore–Penrose inverse.

Every finite real matrix has a unique Moore–Penrose inverse, including singular and zero-sized matrices.

The original-system residual bounds coefficient and training fitted-vector errors.

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.