Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem
Zohar Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz and Omri Weinstein JMLR W&CP 23: 2.1 - 2.17, 2012
Abstract
This paper introduces the Furthest Hyperplane Problem (FHP), which is an unsupervised counterpart
of Support Vector Machines. Given a set of n points in Rd, the objective is to produce
the hyperplane (passing through the origin) which maximizes the separation margin, that is, the
minimal distance between the hyperplane and any input point.
To the best of our knowledge, this is the first paper achieving provable results regarding FHP.
We provide both lower and upper bounds to this NP-hard problem. First, we give a simple randomized
algorithm whose running time is nO(1/θ2) where θ is the optimal separation margin. We
show that its exponential dependency on 1/θ2 is tight, up to sub-polynomial factors, assuming SAT
cannot be solved in sub-exponential time. Next, we give an efficient approximation algorithm. For
any α ∈ [0, 1], the algorithm produces a hyperplane whose distance from at least 1 - 3α fraction
of the points is at least α times the optimal separation margin. Finally, we show that FHP does
not admit a PTAS by presenting a gap preserving reduction from a particular version of the PCP
theorem.
