Abstract:

The use of (Euclidean) distance minimization to find ``best'' separating hyperplanes runs from proofs of the Separating Hyperplane Theorem for convex sets through current software for machine learning. Although separation is not a metric property, a metric approach seems to follow naturally from trying to find a best separator. In this talk I discuss generalizing this duality relationship to an arbitrary Minkowski metric and to the inseparable case, where it is still useful to find a ``best classifying'' hyperplane. It turns out separability of the input implies a convex (and hence efficiently solvable) relaxation of the distance minimization yields the correct answer, while the general non-convex minimization problem is able to solve polytope width, and hence is NP-hard.