1
$\begingroup$

I am interested in collecting the list of the classifiers that (depending on their setting) can have linear time complexity (both in training and testing step) with respect to the number of samples $n$, the number of features of each sample $m$, and the number of classes $c$.

In other words, I am seeking for a list of the well-known classifiers that can have the complexity of $\mathcal{O}(mnc)$ or lower.

1- I know that Naive Bayes classifiers are so; given that the parameters of the utilized probability distributions can be estimated in linear time (e.g. Poisson Naive Bayes and Multinomial Naive Bayes)

2- I also know that when K-NN is utilized as classifier (counting the K-nearest neighbors and choosing the most-voted class), it is also included in this list.

Although this list, in theory, can be extended infinitively, I am interested in completing the list by the well-known classifiers by the CS community.

I searched the web, a lot, but seemingly, there is no page even speaking about such subject or such list. The only thing that I found was a lot of info about "linear classifiers" whose scope is much more general than my question (even their list includes SVM and etc.).

$\endgroup$

closed as too broad by Juho, Evil, David Richerby, vonbrand, Kyle Jones Jul 25 '18 at 3:08

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Define 'trained in linear time'. $\endgroup$ – orlp Jul 7 '18 at 17:10
  • 2
    $\begingroup$ Linear in what parameter? $\endgroup$ – D.W. Jul 7 '18 at 17:17
  • 1
    $\begingroup$ We discourage list questions. There are many many classifiers, so asking for a complete list of all classifiers with this property seems like it is asking a bit much. We seek questions that can be answered in a paragraph or a few paragraphs. Why do you want such a list? What will you do with it? Perhaps you can think of a more focused question that will be a better fit for this site's format. $\endgroup$ – D.W. Jul 7 '18 at 17:18
  • $\begingroup$ @D.W. Of course, a complete list is not expected by me. It was very strange for me that I could find no web articles or papers that review the "well-known" classifiers from the Big-O point of view. There are a lot of web articles and papers that have reviewed classifiers from different points of view. But, I am interested to know which classifiers "theoretically guarantee" very fast performance that is appropriate for being trained and tested in real-time. The accepted answer is not still this, but I am used to accepting the almost-good answers until they are the best existing one. $\endgroup$ – hossayni Jul 8 '18 at 8:10
  • $\begingroup$ @orlp If the classifier performance is dependent to $\{x_1, x_2, ... , x_n\}$ variables, then the training and the testing complexity are less than $\mathcal{O} (x_1 x_2 ... x_n)$. $\endgroup$ – hossayni Jul 8 '18 at 8:13
1
$\begingroup$

You might want to read my blog post Comparing Classifiers, especially the MNIST summary.

Time Complexity of Training

By Training Samples

Let $n$ be the number of training samples.

The following classifiers can perform at least on training / fitting step in $\mathcal{O}(n)$:

  • Neural Networks: You can take a fixed batch size. Then increasing $n$ is simply having more mini-batches to train on.
  • $k$-nearest-neighbors: All "training steps"

The following classifiers cannot perform at least one training / fitting step in $\mathcal{O}(n)$:

  • ???

I am unsure about the following:

  • SVMs
  • Decision Trees: I'm relatively sure it is linear, but I would need to go through one of the training algorithms

By classes

If $n$ is the number of classes, then the training of $k$-NN is in $\mathcal{O}(1)$. If you keep the number of samples and k constant, then it doesn't matter if you have 2 classes or $10^{100}$.

I'm unsure about:

  • Neural Networks: The size of the last layer grows. My intuition is that this is in $\mathcal{O}(n)$, but I need to put more thought into it. I am, however, not sure if the Big-O Time Complexity makes a lot of sense for this classifier. If you look at the tables in Appendix D, you see that in real problems the FLOPs are dominant in the beginning. Given a problem, you usually you can't influence the number of classes. And the wall-clock time complexity of training for two classes is vastly different for different classifiers. So much, that up to a reasonable amount of classes you will likely not see the asymptotic behavior.
  • Decision trees might even be in $\mathcal{O}(1)$. I have to give impurity measures a closer thought.
$\endgroup$
  • $\begingroup$ I guess you're thinking about batch training. But I'm talking about a single mini-batch training run. that single one is constant in time complexity. And then you can train n times which is linear in n. $\endgroup$ – Martin Thoma Jul 8 '18 at 10:01
  • $\begingroup$ Sure you can change what you're looking at. But if you change the architecture you're changing the model. I was clear that I'm only looking at the training samples / classes. $\endgroup$ – Martin Thoma Jul 8 '18 at 10:12
  • $\begingroup$ Somebody edited my answer, while it should be another answer. I don't want this to be lost: gist.github.com/MartinThoma/85080a53f73661f971a7ef4dba48364b $\endgroup$ – Martin Thoma Jul 8 '18 at 15:52
  • 1
    $\begingroup$ It was my answer after setting the utilized list in your weblog as the basis and exhaustively searching the web for finding the complexities. I saw it more polite not to make it a separate one. Now, that it is your suggestion, I submit it as a separate one. $\endgroup$ – hossayni Jul 9 '18 at 2:39
  • $\begingroup$ Thank you, @hossayni :-) Giving credit in you answer is enough. It is better than adding it to my answer, as you get credit for what you wrote. $\endgroup$ – Martin Thoma Jul 9 '18 at 5:07
0
$\begingroup$

Time Complexity of Training and Testing

Linear with respect to training samples ($n$) and samples features ($m$) and number of classes ($c$).

Letting the list provided in the weblog of @Martin_Thoma as the basis, I exhaustively searched the web and reached the following list.

The following classifiers potentially have computational complexities less than or equal with $\mathcal{O}(mnc)$ complexity) in both of the training and testing phases.

The following classifiers are nonlinear either in the training or in the testing phase:

$\endgroup$
  • $\begingroup$ As you have three variables you're interested in (n, m, c), you should not write "k-nearest neighbors is linear", but rather something like $\mathcal{O}(n+m+c)$ $\endgroup$ – Martin Thoma Jul 9 '18 at 5:16

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