3
$\begingroup$

For example, suppose you train a linear regression model using the Normal Equation, on a training set $\mathbf{X}$ containing $m$ instances and $n$ features. The Normal Equation requires computing $(\mathbf{X}^t \cdot \mathbf{X})^{-1}$, which is the inverse of an $n \times n$ matrix. According to the Wikipedia, inverting a matrix has a computational complexity of about $O(n^{2.4})$ using the best algorithms. On the other hand, the algorithm is linear with regards to the number of training examples $m$. So overall, it should be possible to train a linear regression model in $O(m \cdot n^{2.4})$.

Is there a table providing similar information for other Machine Learning algorithms, such as SVMs, Neural Networks (with $u$ layers and $v$ neurons per layer), Random Forests, KNN, Naive Bayes, etc.?

$\endgroup$
0
$\begingroup$

I was looking for the same table, which I never found. I ended up writing this blog post about time complexity of machine learning algorithms, where I focused on the most common algorithms (random forests, regressions, SVMs, kNN...).

It turns out that theoretical arguments such as yours and complexity evaluated on some implementations of some models can be quite different (sometimes due to default parameters, or to the different solvers that are being used).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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