Efficient Certifying Algorithms for Linear Classification

An efficient certifying algorithm is proposed that, given a set of $n$ points in $R^d$ with binary labels, either returns a hyperplane separating the points, or identifies of the labeled points that cannot be separated by any hyperplane. The existence of such points in the inseparable case is known to be guaranteed by Kirchberger’s theorem in combinatorial geometry; we show how to compute these points efficiently. We then propose a dimension-free and constructive extension of Kirchberger’s theorem, where for any one finds either a separating hyperplane, or $O(1/\epsilon^2)$ of the labeled points that cannot be separated with normalized margin by any hyperplane. Our algorithms are based on solving one primal-dual pair of linear programs with $d$ primal and $n$ dual variables, and at most linear equation systems with $O(d)$ equations and $O(d)$ unknowns.