0

By drawing analogy, I believe that Bayesian linear regression has a time complexity same to standard linear regression $(^2+^3)$ which is dominated by the number of features $p$ (What is the Time Complexity of Linear Regression?). To be more specific, the $O(p^3)$ term arises because we need to invert $X^TX$. On the other hand, in Gaussian process regression we need to invert a $n$ x $n$ covariance matrix (with noise), which results in $O(n^3)$. But Bayesian linear regression can be interpreted as Gaussian process at the same time. So why is there such an inconsistency or am I missing something?

Sam
  • 111
  • 1
  • Why do you think Bayesian linear regression has a time complexity of $O(np^{2}+p^{3})$. This might be true for the conjugate case but not for MCMC. – bayes2021 Dec 02 '22 at 09:57
  • what do you mean by 'MCMC' in this context? the complexity I mentioned here is from another post (to which I've provided the link) and I think it makes sense because it captures the complexity of the matrix operation for each term (see the original post for the details) – Sam Dec 03 '22 at 06:35
  • MCMC=Markov Chain Monte Carlo. Unless you have a conjugate model (f.e. with Normal Inverse Gamma priors), there is no closed form solution for the posterior. In this case one uses MCMC to simulate samples from the posterior to answer questions regarding the posterior. Therefore the time complexity is dominated by the number of MCMC steps. https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo – bayes2021 Dec 03 '22 at 17:24
  • @bayes2021 yes I am assuming the case where it can be solved analytically (with closed form solution of the posterior), otherwise I think it doesn't make sense to compare it with GP with a closed form solution https://martenlienen.com/blog/gaussian-processes-are-bayesian-linear-regression/. – Sam Dec 04 '22 at 14:31
  • That's true. But how do you interpret Bayesian linear regression as GP? – bayes2021 Dec 05 '22 at 11:47
  • @bayes2021 please refer to the accepted answer in this post: https://stats.stackexchange.com/questions/444049/equivalence-of-gaussian-process-and-bayesian-linear-regression-by-inspecting-the – Sam Dec 05 '22 at 14:07

0 Answers0