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)
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.Sign up to join this community
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.