If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the data is linearly separable if and only if such a hyperplane exists.

If the data consists of $m$ pairs $(x_1, y_1), \ldots, (x_m,y_m)$, with $x_i \in \{0,1\}^n$ and $y_i \in \{0,1\}$, do we know what the worst case running time is for finding whether or not a maximum margin hyperlane exists?

I can't seem to find a straightforward answer to this. Section 1.4.2 of this says something about complexity and the number of support vectors, but the section also begins by mentioning a lower bound.

Also, this seems to cite a running time of $O(max(m, n) \times min(m, n)^2)$, at least for the running time of the optimization part of the problem.

These texts are not clear to me. Can someone break down the running time for this algorithm? Is the worst case running time known? Can SVMs detect if the $m$ points are linearly separable in polynomial time?

p.s. I am aware that linear programming can solve this in polynomial time ($\text{poly}(mn)$ I think?), but I would like to know how support vector machines behave here.

Edit: The Bottou, Lin chapter seems to come from this book.

  • $\begingroup$ A curiosity : Is this chapter written by L´eon Bottou and Chih-Jen Lin part of some book/review that is available online? I tried following the back-links but I couldn't find anything. What is the source? $\endgroup$ – Anirbit Aug 2 '15 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.