5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Are you looking for guidance on $n$ for Gaussian processes in particular or more general guidelines/information on complexity and scalability? $\endgroup$
    – jcken
    Commented Aug 10, 2021 at 9:12
  • $\begingroup$ @jcken, more general guidelines please but would also appreciate info on n for Gaussian processes ! $\endgroup$
    – stochasticmrfox
    Commented Aug 10, 2021 at 9:18

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

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.