Computational Complexity of Prediction using SVM and NN? I've seen answers discussing the complexity of training SVMs and neural nets, but how about for predicting new responses once a model has been trained?
For context, I'm working on an app that should produce predictions in near real-time given incoming pixel data and I'm looking for a machine learning algorithm that can handle complex separating planes and predict as fast as possible.
 A: In order of increasing on-line complexity:


*

*Linear SVM has prediction complexity $O(d)$ with $d$ the number of input dimensions since it is just a single inner product.

*NN complexity is related to the architecture, but will surely be above that of linear SVM.

*Prediction complexity of kernel SVM depends on the choice of kernel and is typically proportional to the number of support vectors. For most kernels, including polynomial and RBF, this is $O(n_{SV} d)$ where $n_{SV}$ is the number of support vectors. An approximation exists for SVMs with an RBF kernel that reduces the complexity to $O(d^2)$. For computer vision applications, additive kernels are often used because they yield very fast prediction speed (independent of the number of SVs).


Since you are doing a computer vision application, I recommend using either the RBF approximation or additive kernels as they are very fast in evaluation and among the state-of-the-art in terms of accuracy. Neural networks that can rival the performance of SVMs using these kernels in CV applications are typically quite large, and thus slower.
A: For any computer vision task a convolutional neural network (even a simple one) will beat any kind of SVM. This already happened in 2012 when a ConvNet cut the error rate of previous state of the art in half (see papers.nips.cc/paper/4824-imagenet-classification-w).
Furthermore, there's many efficient implementations of ConvNets. Perhaps github.com/soumith/convnet-benchmarks can serve as an overview. There's also lots of implementations focused on efficient usage on mobile phones.
