# Computational complexity of learning (classification) algorithms - fitting the parameters

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!

• Despite the statistical language used, this is purely a set of CS questions. You should be asking these questions and their counterparts (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. Jan 12, 2011 at 16:30
• 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 Jan 12, 2011 at 20:15

## 1 Answer

"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 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. More information in this quora answer.

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 and a good algorithm is confidence-weighted learning.