Computational costs and limits of finite Gaussian-process regression

Cholesky factorization costs $n^3\mathrm{/}3+O(n^2)$ by [F5]. For one test point, the posterior variance formula requires solving $A_{X}u=k_{X\ast }$ and forming $k_{\ast \ast }-k_{\ast X}u$. Factoring $A_X=L{L}^T$ reduces this to two triangular solves, each with $O(n^2)$ cost by [F5], followed by an $O(n)$ inner product. Therefore the variance calculation after factorization is $O(n^2)$.

The spectral norm of $A_{ϵ}=\mathrm{diag}(1,ϵ)$ is $1$, its smallest singular value is $ϵ$, and therefore its spectral condition number is $1\mathrm{/}ϵ$. The perturbation $E=\mathrm{diag}(0,-ϵ)$ has norm $ϵ$, so $\parallel E{\parallel }_2\mathrm{/}\parallel A_{ϵ}{\parallel }_2=ϵ$, while $A_{ϵ}+E=\mathrm{diag}(1,0)$ is singular. Thus operation counts alone do not control sensitivity to finite-precision perturbations near singularity.

The scalar kernel $k_{\theta }(t,t)=\theta$ is positive semidefinite for $\theta \ge 0$, and the observed covariance is $A_{\theta }=1+\theta >0$. Apply [F1] with $m=0$ and $y=0$ to get $L(\theta )=\frac{1}{2}\log (1+\theta )+\frac{1}{2}\log (2\pi )$. Differentiating twice gives $L^{\mathrm{\prime }\mathrm{\prime }}(\theta )=-1\mathrm{/}(2(1+\theta {)}^2)<0$ for every $\theta >0$, so this negative log marginal likelihood is not convex on its parameter domain.

Write $\sigma (z)=(1+e^{-z}{)}^{-1}$; then $0<\sigma (z)<1$ for all $z$, so ${\int }_{\mathbb{R}}\varphi (z)\sigma (z)dz$ is finite and positive. The logistic posterior is therefore a positive density whose log, up to an additive constant, is $q(z)=-z^2\mathrm{/}2-\log (1+e^{-z})$. Differentiation gives $q^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}(z)=-\sigma (z)(1-\sigma (z))(1-2\sigma (z))$. At $z=\log 3$ this equals $3\mathrm{/}32\mathrm{\ne }0$. A positive density on all of $\mathbb{R}$ cannot be a degenerate Gaussian; every nondegenerate univariate Gaussian log density is quadratic and has third derivative zero, so this posterior is not Gaussian.

Since $0<\mathrm{\Phi }(z)<1$ for all $z$, the probit posterior normalizer ${\int }_{\mathbb{R}}\varphi (z)\mathrm{\Phi }(z)dz$ is finite and positive. Its positive log density, up to an additive constant, is $q(z)=-z^2\mathrm{/}2+\log \mathrm{\Phi }(z)$. Put $h=\varphi \mathrm{/}\mathrm{\Phi }$ and $c=h(0)=\sqrt{2\mathrm{/}\pi }$. Since $(\log \mathrm{\Phi }{)}^{\mathrm{\prime }}=h$ and $h^{\mathrm{\prime }}=-zh-h^2$, differentiation yields $(\log \mathrm{\Phi }{)}^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}(0)=h^{\mathrm{\prime }\mathrm{\prime }}(0)=-c+2c^3=c(4\mathrm{/}\pi -1)\mathrm{\ne }0$; the last inequality uses $\pi <4$. A positive density on all of $\mathbb{R}$ cannot be a degenerate Gaussian; every nondegenerate univariate Gaussian log density is quadratic and has third derivative zero, so this posterior is not Gaussian.

Let $D=\{t_i:1\le i\le r\}$ for any finite list $t_1,\dots ,t_r\in [0,1]$. The equality kernel has Gram form ${\sum }_{t\in D}({\sum }_{i:t_i=t}{a}_i{)}^2\ge 0$. Therefore it is positive semidefinite, and by [A1, F2] it defines a cylinder-space Gaussian process with standard normal coordinates and covariance $1_{s=t}$.

For any finite list of distinct inputs in $[0,1]$, [F3] gives a centered Gaussian vector with covariance identity. By [F4] its characteristic function is $\exp (-\frac{1}{2}{\sum }_i{u}_i^2)$, which factors into the univariate standard-normal characteristic functions; uniqueness therefore gives independent standard-normal coordinates.

Let $q_j=1\mathrm{/}(j+2)$. If a continuous modification $G$ existed, the equalities $G_{q_j}=f_{q_j}$ for all $j$ and $G_0=f_0$ would hold simultaneously almost surely, since there are countably many coordinates. Let $E_0=\{\mathrm{\mid }{f}_0\mathrm{\mid }<1\}$, which has positive probability, and $E_j=\{\mathrm{\mid }{f}_{q_j}\mathrm{\mid }>2\}$, each of probability $p>0$ by [F2]. The finite-coordinate independence from step 2.1 gives $\mathrm{Pr}(E_0\cap {\bigcap }_{j=N}^M{E}_j^c)=\mathrm{Pr}(E_0)(1-p{)}^{M-N+1}$. By [F7], letting $M\to \mathrm{\infty }$ gives $\mathrm{Pr}(E_0\cap {\bigcap }_{j=N}^{\mathrm{\infty }}{E}_j^c)=0$ for each $N$; the countable union over $N$ then shows $E_0$ and infinitely many $E_j$ occur together with probability $\mathrm{Pr}(E_0)>0$. On that event $\mathrm{\mid }{G}_0\mathrm{\mid }<1$ while $\mathrm{\mid }{G}_{q_j}\mathrm{\mid }>2$ infinitely often, contradicting continuity at $0$. No continuous modification exists.

The scope distinction in [F6] concerns a Gaussian observation likelihood; the explicit logistic and probit posterior calculations in steps 1.4 and 1.5 have nonzero third derivatives and are not Gaussian. Thus the exact finite Gaussian regression formula does not give an exact Gaussian posterior for those classification models.