What's the time complexity of training a Gaussian process and its Expectation Propagation approximation?

(Before studying them, I'd like to understand if they are even feasible for my application)


I stumbled onto this passage in Gaussian Processes for Machine Learning, p. 24:

For the GP models it is computationally expensive to make use of all 44,484 training cases due to the $O(n^3)$ scaling of the basic algorithm. In chapter 8 we present several different approximate GP methods for large datasets.

P. 58 has some detail on the complexity of the EP algorithm, also $O(n^3)$, and chapter 8 offers several approximation methods for use with large datasets. A table of complexities for storage, initialization, and calculating predictive mean using those methods is found on p. 183.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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