<p>"Training" a naive bayes classifier, assuming you're given the feature vectors, is $O(n)$, where $n = \sum_i nnz(x_i)$, where $nnz(x_i)$ is the number of nonzero features in data point $i$.</p>

<p>For logistic regression you have to solve an optimization problem, and this depends on the optimizer. With L-BFGS an iteration takes linear time on the size of the training set and I've never needed more than 100 iterations to converge to a reasonable value (but I'm not aware of any worst-case bounds).</p>

<p>For the $k$-nearest neighbor classifier there is no training, but classifying has a high cost, and depends on the search algorithm you're using. For linear search the complexity is (for fixed k) proportional to the size of the training set for each point you want to classify. With approximate algorithms this can be <a href="http://people.csail.mit.edu/indyk/p117-andoni.pdf" rel="nofollow noreferrer">brought down</a> considerably at the expense of accuracy.</p>

<p>For svms standard quadratic-programming solvers are $n^3$, but recent approaches are <a href="http://www.cs.huji.ac.il/~shais/papers/SSSICML08.pdf" rel="nofollow noreferrer">inverse in the size of the training set</a>. More information in <a href="http://www.quora.com/What-is-the-computational-complexity-of-an-SVM" rel="nofollow noreferrer">this quora answer</a>.</p>

<p>If you really need fast learning the best approaches so far are those based on online learning, which can converge to classifiers that compete well against batch classifiers with only one pass over the training data. A very fast implementation is <a href="http://hunch.net/~vw/" rel="nofollow noreferrer">vowpal wabbit</a> and a good algorithm is <a href="http://news.google.com/research/pubs/archive/34667.pdf" rel="nofollow noreferrer">confidence-weighted learning</a>.</p>

CC BY-SA 3.0
2011-01-16T00:43:36.547Z
2018-02-08T23:09:34.247Z
2018-02-08T23:09:34.247Z
Alexandre Passos
<p>My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume anything about its distribution (it may be symmetric or very skewed). In statistics, we choose a predictive model and fit its parameters. What is the time complexity of fitting</p>

<ul>
<li>naive Bayesian classifier</li>
<li>logistic regression</li>
<li>$k$-nearest neighbor classifier</li>
<li>SVM </li>
<li>$\ldots$</li>
</ul>

<p>I understand that in some cases additional parameters or assumptions about the data (types of variables) are required. These parameters can be of course incorporated in your answer. Thank you very much!</p>

CC BY-SA 2.5
2011-01-12T16:30:18.443Z
Despite the statistical language used, this is purely a set of CS questions.  You should be asking these questions and their counterparts (http://stats.stackexchange.com/q/6199/919 ) on a programming or algorithms site.  When you migrate it (or it gets migrated for you), bear in mind that good practice is to ask one question at time, not an open-ended list of questions.
whuber
CC BY-SA 2.5
2011-01-12T20:15:38.000Z
It seems a bit broad since there are different ways of fitting those classifiers, with different complexities. For instance, one method for SVM is linear in the number of non-zero components, another one is quadratic in the number of examples, but there are dozens of others
Yaroslav Bulatov
<lg.learning><machine-learning>
Computational complexity of learning (classification) algorithms - fitting the parameters
Lan
# Computational complexity of learning (classification) algorithms - fitting the parameters

(Asked by: username_0 on 2011-01-12)

My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume anything about its distribution (it may be symmetric or very skewed). In statistics, we choose a predictive model and fit its parameters. What is the time complexity of fitting

* naive Bayesian classifier
* logistic regression
* $k$-nearest neighbor classifier
* SVM
* $\ldots$

I understand that in some cases additional parameters or assumptions about the data (types of variables) are required. These parameters can be of course incorporated in your answer. Thank you very much!

**Tags:** lg.learning, machine-learning
> **Comments:**
> **username_1**: Despite the statistical language used, this is purely a set of CS questions.  You should be asking these questions and their counterparts (http://stats.stackexchange.com/q/6199/919 ) on a programming or algorithms site.  When you migrate it (or it gets migrated for you), bear in mind that good practice is to ask one question at time, not an open-ended list of questions.  
> **username_2**: It seems a bit broad since there are different ways of fitting those classifiers, with different complexities. For instance, one method for SVM is linear in the number of non-zero components, another one is quadratic in the number of examples, but there are dozens of others  

---

## 1 answers

### Answer by username_3 on 2011-01-16. Score: 4

"Training" a naive bayes classifier, assuming you're given the feature vectors, is $O(n)$, where $n = \sum\_i nnz(x\_i)$, where $nnz(x\_i)$ is the number of nonzero features in data point $i$.

For logistic regression you have to solve an optimization problem, and this depends on the optimizer. With L-BFGS an iteration takes linear time on the size of the training set and I've never needed more than 100 iterations to converge to a reasonable value (but I'm not aware of any worst-case bounds).

For the $k$-nearest neighbor classifier there is no training, but classifying has a high cost, and depends on the search algorithm you're using. For linear search the complexity is (for fixed k) proportional to the size of the training set for each point you want to classify. With approximate algorithms this can be [brought down](http://people.csail.mit.edu/indyk/p117-andoni.pdf) considerably at the expense of accuracy.

For svms standard quadratic-programming solvers are $n^3$, but recent approaches are [inverse in the size of the training set](http://www.cs.huji.ac.il/~shais/papers/SSSICML08.pdf). More information in [this quora answer](http://www.quora.com/What-is-the-computational-complexity-of-an-SVM).

If you really need fast learning the best approaches so far are those based on online learning, which can converge to classifiers that compete well against batch classifiers with only one pass over the training data. A very fast implementation is [vowpal wabbit](http://hunch.net/~vw/) and a good algorithm is [confidence-weighted learning](http://news.google.com/research/pubs/archive/34667.pdf).


---

