Does SVM classification always produces unique solution?

9
votes

Linear classifiers on separable can have more than one boundary for classifying the data. This is the reason we go for SVM to choose boundary which has maximum margin(minimum generalization error on unseen data).

Does SVM classification always produces unique solution(Wont we get two maximum margin boundary in all possible data) ?

Is answer depends on the Hard margin SVM and Soft Margin SVM?

2
machine-learningsvm
You could reframe the question a bit. Does the SMO (sequential minimal optimization) algorithm guarantee a globally optimal result? Wikipedia was not much help in that regard... – Craig Wright
SMO does not have anything to do with whether there exists a global optimum. That is a property of the optimization problem itself (e.g. whether it is convex or not). SMO is just a numerical means of obtaining some solution given an objective function and constraints. You could feed SMO a non-convex problem with many local optima and then not be assured of anything about the solution it finds. – ely

2 Answers

9
votes

Yes, both the soft and hard formulations of standard SVM are convex optimization problems, hence have unique global optima. I suppose if the problem is incredibly huge, approximation methods would be parsimonious enough that you would use them instead of exact solvers, and then your numerical solution technique might not find the global optimum purely because it's trade-off benefit is to reduce search time.

The typical approach to these is sequential minimal optimization -- hold some variables fixed and optimize over a small subset of the variables, then repeat with different variables over and over until you can't improve the objective function. Given that, I find it implausible that anyone would solve these problems in a way that won't yield the global optimum.

Of course, the global optimum you find might not actually be appropriate for your data; that depends on how well your model, noisy class labels, etc. represent the data generating process. So solving this doesn't guarantee you've found the absolute right classifier or anything.

Here are some lecture notes I found about this in a cursory search: (link)

Here is a more direct link regarding the convexity claims: (link)

2
votes

For hard margin classifiers with no regularization the SVM problem can be converted to a coercive quadratic programming problem with linear constrains (assuming a solution / positive margin exists). Coercive quadratic programming problems with linear constrains have unique global minimums and simple optimization methods (like gradient decent or the perceptron algorithm) are guaranteed to converge to the global minimum. See for example

http://optimization-online.org/DB_FILE/2007/05/1662.pdf

For soft margin SVMs and for SVMs with regularization terms, I think there are unique global minima and the usual techniques converge to the global minimum, but I am not aware of any proofs that cover all the possibilities.