I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity.

I have noticed this is very uncommon. However, I believe it would help us compare these algorithms and decide which one to use for a given scenario.

I am also aware that the running time of most machine learning algorithms is highly dependent on the data. For example, gradient descent algorithm can iterate significantly more times on certain data sets than others.

Considering this, what would be a nice complexity measure for comparing machine learning algorithms?

  • $\begingroup$ pros: indeed they have not been explored! Cons: ML algorithms are probabilistic, which makes them highly unlikely to have a good way to compute accurate enough lower or upper bounds to make those numbers look interesting. Good luck! $\endgroup$ – Apoorv Feb 10 '20 at 3:34
  • 1
    $\begingroup$ @ApoorvIngle I'm afraid both of those statements are simply wrong. First, not all "ML algorithms" are probabilistic. Second, already if you look at the documentation for say scikit-learn (which is a popular Python library), you'll see that the scaling of many algorithms is stated often with references to the literature. $\endgroup$ – Juho Feb 10 '20 at 15:45
  • $\begingroup$ @Juho My first statement was supposed to mean "ML algorithms can be probabilistic". My second statement still stands correct as it is difficult to compute traditional $\Theta$/$\Omega$ complexity functions for such algorithms. $\endgroup$ – Apoorv Feb 10 '20 at 18:33
  • $\begingroup$ @ApoorvIngle OK. Even if it's difficult, it doesn't mean that nobody wouldn't have tried. In fact, people succesfully have, meaning it is not true that "... they have not been explored" (see e.g., scikit-learn docs). $\endgroup$ – Juho Feb 10 '20 at 18:39

Well, first let's clarify the following. Asymptotic Complexity and real life situations are different. Please take a look at this Question.

Now, machine learning is a very hard topic to explore precisely the asymptotic complexity of your algorithms. If we think machine learning as linear algebra, then the asymptotic complexity is the complexity of multiplying matrices. In the area of machine learning, the most important thing is not so much the complexity, but the efficient use of GPUs and TPUs. Let's say you need to train a model for Natural Language Understanding and you use LSTM, GRU and CNN (CNN ?!). Each algorithm has its own complexity because each one does easier or harder calculations. Unfortunately there is no metric such as Model's Accuracy / # of computations. But we all can agree that two LSTM can vastly vary on their speed depending on how good use of GPUs and TPUs they make.


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.