Does Gaussian process functional regression fulfill the consistency condition?

Question

I'm learning about Gaussian process functional regression but the more I learn, the more questions arise.

So we want to estimate a function $f\left( x \right)$ from data $D = \left( {\left( {{x_1},{y_1}} \right),...,\left( {{x_n},{y_n}} \right)} \right)$ by updating a ${\text{GP}}\left( {m\left( x \right),k\left( {x,x'} \right)} \right)$ prior.

I tell to myself that GP regression should fulfill the "consistency condition" (don't know how it's called in the literature?): if we partition the data set $D$, update the ${\text{GP}}\left( {m\left( x \right),k\left( {x,x'} \right)} \right)$ prior with the first part, then update the posterior process of the previous step with the second part and so forth until the last part, we should get the same final posterior process at the end as if we directly update ${\text{GP}}\left( {m\left( x \right),k\left( {x,x'} \right)} \right)$ with whole data $D$. Otherwise, we would get different estimations/inferences, depending on said partition.

On the one hand, it is well-known that GP regression has $O\left( {{n^3}} \right)$ generic computational complexity.

On the other hand, if we successively update with each datum $\left( {{x_i},{y_i}} \right),\;i = 1,n$ one by one, the update equations are

$\left\{ \begin{gathered} {m^{i + 1}}(x) = {m^i}(x) + {k^i}\left( {x,{x_i}} \right){\left( {{k^i}\left( {{x_i},{x_i}} \right) + {\sigma ^2}} \right)^{ - 1}}\left( {{y_i} - {m^i}\left( {{x_i}} \right)} \right) \hfill \\ {k^{i + 1}}(x,x') = {k^i}(x,x') - {k^i}\left( {x,{x_i}} \right){\left( {{k^i}\left( {{x_i},{x_i}} \right) + {\sigma ^2}} \right)^{ - 1}}{k^i}\left( {{x_i},x'} \right) \hfill \\ \end{gathered} \right.$

Each recursion requires the evaluation of 4 terms.

Hence, applying the recursion again to those 4 terms requires the evaluation of 16 terms, 8 of them being different for $m(x)$: ${{m^{i-1}}\left( {{x}} \right)}$, ${{m^{i-1}}\left( {{x_{i-1}}} \right)}$ , ${{m^{i-1}}\left( {{x_{i}}} \right)}$, ${k^{i-1}}\left( {x,{x_{i-1}}} \right)$, ${k^{i-1}}\left( {x_{i-1},{x_{i-1}}} \right)$, ${k^{i-1}}\left( {x,{x_{i}}} \right)$, ${k^{i-1}}\left( {x_{i-1},{x_{i}}} \right)$ and ${k^{i-1}}\left( {x_{i},{x_{i}}} \right)$.

And so forth. It appears that updating the kernel sequentially with each datum one by one has exponential computational complexity in $n$!

Therefore, GP regression doesn't fulfill the consistency condition: it gives completely different results (or no result at all) depending on how the data is partitioned.

Correct?

Answer 1

In computer science, the idea you describe is called the divide and conquer algorithm.

While often very successful, here it fails. This is because you have to take all cross correlations between the prior $n-1$ points and the new data point into account. So nothing is gained in general by doing it sequentially or subdividing the problem in any other way.

Answer 2

Unlike parametric models that are defined by a fixed number of parameters, a Gaussian process is defined by a mean and covariance functions. While it is common to use a prior where those functions have a simple closed form (such as a squared exponential covariance function), Once you update the model with arbitrary data those functions no longer have this simple form. The updated mean and covariance functions depend in some complicated way on all the previous data points, so when you perform sequential updating, each step has an increasing complexity.

Suppose for example that the covariance function after $n$ updates is $k^{(n)}(x,x')$, and you observe the next data point $x_{n+1}$. The updated covariance $k^{(n+1)}(x,x')$, as you pointed out, is

$$k^{(n+1)}(x,x')=k^{(n)}(x,x') -k^{(n)}(x,x_{n+1})(\sigma^2 + k^{(n)}(x_{n+1},x_{n+1}))^{-1} k^{(n)}(x',x_{n+1})$$

Now evaluating this function at arbitrary points $x$ and $x'$ requires four different evaluations of $k^{(n)}(\cdot,\cdot)$, namely $k^{(n)}(x,x_{n+1})$, $k^{(n)}(x',x_{n+1})$, $k^{(n)}(x_{n+1},x_{n+1})$ and $k^{(n)}(x',x)$. But each of those function evaluations will itself require that you calculate the previous covariance $k^{(n-1)}(\cdot,\cdot)$ at another set of points, for example to evaluate $k^{(n)}(x',x_{n+1})$ you will need $k^{(n-1)}(x_n,x_{n+1})$ and so on. This naïve recursive calculation will require therefore a total of $4^n$ function evaluations, which is unlikely to be very efficient.

Of course the sequential calculation will eventually give you exactly the same result as updating once with all the data, as those are mathematically equivalent.

Answer 3

The updating equations (adapted from this answer) are:

$$K_{i+1}^{-1} = \begin{bmatrix} K_i & k_* \\ k_*^T & k_{**}\end{bmatrix}^{-1} = \begin{bmatrix}K_i^{-1} + S_i v_iv_i^T & -S_n v_i \\ -S_iv_i^T & S_i\end{bmatrix}$$

where

$$S_i := (k_{**} - k_*^Tv_i)^{-1}$$

The complexity of computing $S_i$ given $v_i$ is $\propto i$, while the cost of computing $v_i = K_i^{-1}k_*$ as well as the $v_iv_i^T$ product is $\propto i^2$.

So the cost increases quadratically per iteration.

It's easy to show that:

$$\sum_{i=1}^n i^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$$

[1] jld (https://stats.stackexchange.com/users/30005/jld), Using Gaussian Processes to learn a function online, URL (version: 2021-04-21): https://stats.stackexchange.com/q/520830