1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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
    Commented Feb 10, 2020 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
    Commented Feb 10, 2020 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
    Commented Feb 10, 2020 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
    Commented Feb 10, 2020 at 18:39

2 Answers 2

Reset to default
1
$\begingroup$

Usually, when considering machine learning algorithms from a theoretical perspective, we are interested in PAC learnability, or some other learnability definition (most of those are very similar to PAC, since everything in the machine learning region is stochastic).

Under those definitions, there are a few possible "metrics" that measure something similar to complexity. However, there is no "standard metric", as to different algorithms for different problems can behave totally differently in structure.

An example of that would be the sample complexity when considering supervised learning tasks: How many input samples do we need in order to guarantee an error of up to $\epsilon$ with probability $1-\delta$ (as a function of $\epsilon$ and $\delta$)?

Or, in the reinforcement learning world, a "metric" could be considered the convergence rate of an algorithm to the wanted output: How much does the error "shrink" each iteration of the algorithm?

That being said, there is no standard way to compare the algorithms theoretically, but practically you can run each of them and see who is performing better and faster.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

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.