I keep seeing complexities for machine learning algorithms e.g. Gaussian process implementation requires inversion of an nxn matrix so complexity is $O(n^3)$.
When does complexity actually become an issue? Is there a way to work out when it becomes prohibitive?
Best Answer
I use least-squares support vector machines a fair bit, which are $\mathcal{O}(n^3)$ for the most obvious implementation, and problems with up to a ten thousand or so examples are just about practical on my machine, but memory usage is not insignificant either, and 8192*8192 matrix in double precision format is 0.5Gb of memory.
Gaussian processes are not dissimilar to LS-SVMs (bit more expensive).
However as well as fitting the model, you will need to perform model selection as well (tuning the hyper-parameters) and that is where things get expensive as you have to refit the model many times (not so bad if you can perform the calculations in parallel).
If you have more data than that, you will probably want to look into sparse approximation.