# What is the complexity of classification with SVMs?

I'm interested in how fast SVMs can classify new data with $c \in \mathbb{N}_{\geq 2}$ classes and $n \in \mathbb{N}_{\geq 1}$ features.

## Example for Neural Networks

For neural networks, this depends very much on the architecture. For supposing you only have one hidden layer with $3n$ neurons, you would have a $n:3n:c$ topology and hence

• one multiplication of a $n$-dimensional vector with a matrix in $\mathbb{R}^{n \times 3n}$,
• then a multiplication of a vector in $\mathbb{R}^{3n}$ with a matrix in $\mathbb{R}^{3n \times c}$
• and of course $3n+c$ applications of the activation functions.
• Adding the biases is dominated by the matrix multiplications.

This results in an overall complexity of $\mathcal{O}(n^2 \cdot c)$.

## Question

I would be interested in a similar analysis of the classification complexity (NOT the training!) of SVMs, preferably with a reference to literature.

• Interesting question, but difficult to answer for SVMs without relying on kernel and implementation details. Linear SVMs will, of course, simply compute a dot-product + a bias and report the sign; That is O(n) in the number of features. Non-linear SVMs are totally dependent on their definition of the kernel that performs a dot-product in some O(huge)-dimensional space. If this kernel is efficient (because they're chosen to avoid requiring the explicit formation of the expanded vector), then they can be of low complexity. SVMs based on polynomial and RBF kernels are O(n) for classification. – Iwillnotexist Idonotexist Dec 26 '15 at 9:43
• So the best for SVMs which should distinguish $c$ classes is $\mathcal{O}(n c^2)$ (applying the one-vs-one strategy which seems to be better than the one-vs-all strategy). – Martin Thoma Dec 26 '15 at 9:57
• I don't think the question is answerable as posed. To answer the question you must provide us additional information: (1) are you using a kernel, or is this a linear SVM? (2) what variety of multi-class SVM are you using? Standard SVMs support only two classes. There are multiple different ways to build a multi-class classifier based on SVMs, but you'll need to tell us which you have in mind for us to give you an answer. – D.W. Dec 29 '15 at 6:18