6
$\begingroup$

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!

$\endgroup$

migrated from stats.stackexchange.com Jan 12 '11 at 16:41

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Jan 12 '11 at 16:30
  • $\begingroup$ 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 $\endgroup$ – Yaroslav Bulatov Jan 12 '11 at 20:15
4
$\begingroup$

"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.

$\endgroup$

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.