That’s a sequel to my previous question Does Gaussian process functional regression fulfill the consistency condition?

The conclusion was that:

  • Gaussian process regression with i.i.d. Gaussian noise returns the same posterior Gaussian process for any partition of the data;
  • ... but with completely different calculations/algorithms. In particular, GP regression with full $n-$update (i.e. the trivial partition) has $O\left( {{n^3}} \right)$ generic computational complexity but GP regression with $n$ sequential $1-$updates (i.e. the atomic partition) has exponential computational complexity in $n$. That’s the reason why we never do $n$ sequential $1-$updates but a $(n-1)-$update followed by a $1-$ update in sequential/online learning, see e.g. Using Gaussian Processes to learn a function online.

Now, consider a Bayesian problem with data $D = \left( {{d_1},...,{d_n}} \right)$ and parameters $\Theta $:

$p\left( {\left. \Theta \right|D} \right) \propto p\left( {\left. D \right|\Theta } \right)p\left( \Theta \right)$

Proposition $1$: if the likelihood factorizes $p\left( {\left. D \right|\Theta } \right) = \prod\limits_{i = 1}^n {p\left( {\left. {{d_i}} \right|\Theta } \right)} $ and $\Theta$ is fixed once and for all

then the posterior calculations are exactly the same for any partition $D = \bigcup\limits_{j = 1}^p {{D_j}} $ of the data and any of its $p!$ permutations.

Proof: we have

$p\left( {\left. \Theta \right|D} \right) \propto p\left( {\left. D \right|\Theta } \right)p\left( \Theta \right) = \left( {p\left( {\left. {{D_p}} \right|\Theta } \right)...\underbrace {\left( {p\left( {\left. {{D_2}} \right|\Theta } \right)\underbrace {\left( {p\left( {\left. {{D_1}} \right|\Theta } \right)p\left( \Theta \right)} \right)}_{ \propto p\left( {\left. \Theta \right|{D_1}} \right)}} \right)}_{ \propto p\left( {\left. \Theta \right|{D_1},{D_2}} \right)}...} \right)$

Therefore, the only difference from one partition to another and from one permutation to another are the parentheses and the order of the products that are totally useless by the associative and commutative properties of the product. QED.

Proposition 1 just says that the likelihood $\prod\limits_{i = 1}^n {p\left( {\left. {{d_i}} \right|\Theta } \right)} $ and the full posterior remain the same regardless of how the data are grouped together and of their order of arrival.

Corollary $1$: GP regression with i.i.d. Gaussian noise is not a Bayesian method.

Proof: We have ${d_i} = \left( {{x_i},{y_i}} \right)$ and for i.i.d. Gaussian noise the likelihood factorizes

$p\left( {\left. D \right|\Theta } \right) = \prod\limits_{i = 1}^n {p\left( {\left. {{x_i},{y_i}} \right|f,\sigma } \right) = } \prod\limits_{i = 1}^n {p\left( {\left. {{y_i}} \right|{x_i},f,\sigma } \right)p\left( {\left. {{x_i}} \right|f,\sigma } \right)} \propto \prod\limits_{i = 1}^n {p\left( {\left. {{y_i}} \right|{x_i},f,\sigma } \right)} \propto {\sigma ^{ - n}}\prod\limits_{i = 1}^n {{e^{ - \frac{{{{\left( {{y_i} - f\left( {{x_i}} \right)} \right)}^2}}}{{2{\sigma ^2}}}}}} $

Moreover, $\Theta$ is fixed once and for all: $\Theta = \left( {f,\sigma ,m,k,{\rm M},{\rm K}} \right)$, see Is Gaussian process functional regression a truly Bayesian method (again)?

But the posterior calculations are not exactly the same from one partition/update scheme to another. QED.

In the same way, we have

Proposition $2$: if the likelihood factorizes and $\Theta$ is fixed once and for all, then Bayesian inference has $O(n)$ computational complexity.

Proof: Computing the prior $p\left( \Theta \right)$ has $O(1)$ computational complexity because it does not depend on $n$. Computing the likelihood $p\left( {\left. D \right|\Theta } \right) = \prod\limits_{i = 1}^n {p\left( {\left. {{d_i}} \right|\Theta } \right)} $ has $O(n)$ computational complexity. Computing the normalization constant $p\left( D \right) = \int {p\left( {\left. D \right|\Theta } \right)p\left( \Theta \right){\text{d}}\Theta } $ has $O(1)$ complexity because that's a $|\Theta|-$ dimensional integral that has nothing to do with $n$ (moreover, we don't need to compute it, it cancels out by Leibniz rule/Feynman trick). Therefore, computing the full posterior $p\left( {\left. \Theta \right|D} \right)$ has $O(n)$ computation complexity. Finally, drawing posterior inferences, taking Bayes estimators and computing credible intervals has $O(1)$ computational complexity because it involves $\left| \Theta \right|-$dimensional integrals whose complexity basically does not depend on $n$ (we just integrate different functions that depend on $n$ but the complexity of those integrals basically does not depend on $n$). All in all, Bayesian inference has $O(n)$ computational complexity. QED.

For one example of such truly Bayesian $O(n)$ functional regression algorithm, see Bayesian interpolation and deconvolution.

Corollary $2$: again, GP regression with i.i.d. Gaussian noise is not a Bayesian method.

Proof: GP regression does not have $O(n)$ computational complexity.

Is that correct please?

  • 3
    $\begingroup$ You already asked this question (twice) and got it answered. Computational complexity has nothing to do with being Bayesian or not. $\endgroup$
    – Tim
    Apr 18, 2023 at 8:40
  • $\begingroup$ @Tim But Proposition 2 just says the opposite: if the likelihood factorizes, Bayesian inference has $O(n)$ computational complexity. Anything wrong with that? $\endgroup$
    – Student
    Apr 18, 2023 at 8:52
  • $\begingroup$ @Tim Let's go step by step please. Do you agree that computing the prior is $O(1)$ or not? Do you agree that computing the likehood is $O(n)$ or not? Do you agree that drawing inference requires evaluating $|\Theta|-$dimensional integrals that have nothing to do with $n$ or not? $\endgroup$
    – Student
    Apr 18, 2023 at 8:59
  • 4
    $\begingroup$ I give up. You are cherry-picking arbitrary computations and calculating big-$O$ complexity for them while ignoring other computations to "prove" your point. It doesn't work like this. $\endgroup$
    – Tim
    Apr 18, 2023 at 9:43
  • 3
    $\begingroup$ It is an unusual computing model indeed that supposes the cost of evaluating an integral (in arbitrarily many dimensions) is $O(1)$! If you have such a machine and can get the implicit constant small enough, scientists and engineers everywhere will beat a path to your door. I believe such a machine would be superior to a quantum computer. $\endgroup$
    – whuber
    Apr 18, 2023 at 18:27

2 Answers 2


Computational complexity has nothing to do with being a Bayesian model. Bayes theorem is a mathematical concept, it has no computational complexity whatsoever. There are different Bayesian models, where some have closed-form solutions so can be solved "instantly", some would need you to take complicated integrals. For the latter, we have many algorithms for finding the, usually approximate, solutions, where each of the algorithms has different computational complexity.

As you can learn from Who Are The Bayesians? there is no clear definition of "Bayesianism" but one of the key concepts is the subjectivist interpretation of probability. The Bayesian model is the one defined in terms of priors and likelihood and using Bayes theorem, which is clearly the case of Gaussian processes. Notice however that there are generalizations of the Bayesian approach that would be considered by many still as Bayesian approaches, e.g. ABC (see ) that do not even try to directly calculate the Bayes theorem and consider scenarios where this is not possible.

Finally, you seem to be sticking to the idea of Bayesian updating but notice that for some Bayesian models, it would not be possible in practice to do such an update at all. For example, if you are using Markov Chain Monte Carlo for sampling from the posterior distribution to get an approximation of it, there is no simple way of using those samples as a prior for another model.

  • $\begingroup$ Please, see my comments above and just disprove Proposition 2: if the likelihood factorizes, then Bayesian inference has $O(n)$ computational complexity. $\endgroup$
    – Student
    Apr 18, 2023 at 9:01
  • $\begingroup$ I believe you agree that computing the full posterior has $O(n)$ computional complexity. Therefore, you need to prove that taking Bayes estimator from the full posterior does depend on $n$. But it does NOT because we just need to evaluate $|\Theta|-$ dimensional integrals (e.g. for computing the marginal posterior moments) that have nothing to do with $n$. $\endgroup$
    – Student
    Apr 18, 2023 at 9:05
  • $\begingroup$ What about Proposition 1 please? This one is even more difficult to disprove, isn't it? $\endgroup$
    – Student
    Apr 18, 2023 at 9:41
  • $\begingroup$ Please provide your feedback about Proposition 1 and Corollary 1. If you can't disprove them, then you'll agree that GP regression is not Bayesian and you'll be in a better position to appreciate Proposition 2 and Corollary 2. $\endgroup$
    – Student
    Apr 18, 2023 at 9:50
  • 2
    $\begingroup$ @Student I'm backing off the discussion as it leads nowhere. I already answered your question. $\endgroup$
    – Tim
    Apr 18, 2023 at 10:41

Your Proposition 1 is wrong, because calculating the posterior can require an increasing number of computations for every additional data point.

A simple example that demonstrates it is a mixture distribution: suppose that $$ x \sim pf_1(x|\theta) + (1-p)f_2(x|\varphi).$$

Namely, $x$ comes from a mixture distribution with two components that are parametrized by $\theta$ and $\varphi$, on which you have some prior $\pi(\theta,\varphi)$. The posterior distribution after observing the first sample $x_1$ will become also a mixture distribution with two components:

$$P(\theta,\varphi|x_1) \propto pf_1(x_1|\theta)\pi(\theta,\varphi) + (1-p)f_2(x_1|\varphi)\pi(\theta,\varphi)$$

The posterior distribution after observing the second sample $x_2$ will then become a mixture distribution with four components :

$$P(\theta,\varphi|x_1,x_2) \propto (pf_1(x_1|\theta)\pi(\theta,\varphi) + (1-p)f_2(x_1|\varphi)) \times (pf_1(x_1|\theta)\pi(\theta,\varphi) + (1-p)f_2(x_1|\varphi)\pi(\theta,\varphi))$$

And so on. After observing $n$ samples the posterior will be a mixture of $2^n$ components, so the amount of calculations requires grows exponentioaly.

Since this proposition is wrong, everything else that follows from it is clearly also wrong.

  • $\begingroup$ How such a straigthforward, immediate consequence of the associative property of the product as Proposition 1 could ever be wrong is well beyond my understanding??? Short answer: don't forget the UNKNOWN mixture allocation variables/parameters ${a_i} = \left\{ \begin{gathered} {\text{1 if }}{x_i} \sim {f_1}\left( {\left. x \right|\theta } \right) \hfill \\ {\text{2 if }}{x_i} \sim {f_2}\left( {\left. x \right|\varphi } \right) \hfill \\ \end{gathered} \right.$ in your likelihood $p\left( {\left. {{x_1},...,{x_n}} \right|\theta ,\varphi ,p,{a_1},...,{a_n}} \right)$... $\endgroup$
    – Student
    Apr 18, 2023 at 18:48
  • $\begingroup$ And don't forget that $\Theta = \left( {\theta ,\varphi ,{a_1},...,{a_n}} \right)$. Rewrites Bayes rule accordingly and check that Proposition 1 holds.... $\endgroup$
    – Student
    Apr 18, 2023 at 18:50
  • $\begingroup$ Latent but mandatory allocation variables. $\endgroup$
    – Student
    Apr 18, 2023 at 19:04
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Cross Validated Meta, or in Cross Validated Chat. Comments continuing discussion may be removed. $\endgroup$
    – Tim
    Apr 18, 2023 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.