<p>SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration * #iterations (where #iterations is assumed to be constant)</p>

CC BY-SA 3.0
2013-09-01T05:17:24.320Z
2013-09-01T05:17:24.320Z
Suresh Venkat
<p>Relevance Vector Machines need a $O(n^3)$ time too, but the main overhead there is in the learning phase, it needs to repeatedly compute the inverse of a Hessian Matrix (that requires $O(n^3)$ computations. </p>

<p>Although tipping in his paper suggest a maximum of 5000 features vectors, I had a hard time to train a dataset of 2000 examples!</p>

<p>The k-nearest neighbor algorithm does not require any training time, and it can easily achieve near linear time complexity using approximation algorithms. </p>

<p>However, a preprocessing step is often useful and it also costs you $O(nd)$, specially if you want faster classification speeds. <a href="http://people.csail.mit.edu/indyk/p117-andoni.pdf" rel="nofollow">This is a good paper</a> to read if you want to know more.</p>

CC BY-SA 3.0
2013-09-01T14:16:17.223Z
2013-09-01T14:16:17.223Z
Subhayan
<p>I would like to know what is the asymptotic time complexity analysis for general models of Back-propagation Neural Network, SVM and Maximum Entropy. Does it just depend on number of features included and training time complexity is the only stuff that really matters. </p>

<p>And does it real matter when applying on large chunk of text classification like twitter data or blog data</p>

CC BY-SA 3.0
2013-08-25T17:50:33.973Z
SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration * #iterations (where #iterations is assumed to be constant)
Suresh Venkat
CC BY-SA 3.0
2013-08-31T18:14:29.517Z
@SureshVenkat: That should be an answer, not a comment.
Jeffε
CC BY-SA 3.0
2013-09-01T05:17:53.167Z
@JɛﬀE it is done.
Suresh Venkat
<machine-learning><time-complexity>
Compute Time Complexity of Neural network, SVM and other classification algorithms
MalTec
# Compute Time Complexity of Neural network, SVM and other classification algorithms

(Asked by: username_0 on 2013-08-25)

I would like to know what is the asymptotic time complexity analysis for general models of Back-propagation Neural Network, SVM and Maximum Entropy. Does it just depend on number of features included and training time complexity is the only stuff that really matters.

And does it real matter when applying on large chunk of text classification like twitter data or blog data

**Tags:** machine-learning, time-complexity
> **Comments:**
> **username_1**: SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration * #iterations (where #iterations is assumed to be constant)  
> **username_2**: @SureshVenkat: That should be an answer, not a comment.  
> **username_1**: @JɛﬀE it is done.  

---

## 2 answers

### Answer by username_1 on 2013-09-01. Score: 4

SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration \* #iterations (where #iterations is assumed to be constant)


---

### Answer by username_3 on 2013-09-01. Score: 0

Relevance Vector Machines need a $O(n^3)$ time too, but the main overhead there is in the learning phase, it needs to repeatedly compute the inverse of a Hessian Matrix (that requires $O(n^3)$ computations.

Although tipping in his paper suggest a maximum of 5000 features vectors, I had a hard time to train a dataset of 2000 examples!

The k-nearest neighbor algorithm does not require any training time, and it can easily achieve near linear time complexity using approximation algorithms.

However, a preprocessing step is often useful and it also costs you $O(nd)$, specially if you want faster classification speeds. [This is a good paper](http://people.csail.mit.edu/indyk/p117-andoni.pdf) to read if you want to know more.


---

