A Linearly Convergent Linear-Time First-Order Algorithm for Support Vector Classification with a Core Set Result

We present a simple, first-order approximation algorithm for the support vector classification problem. Given a pair of linearly separable data sets and $\epsilon \in (0,1)$, the proposed algorithm computes a separating hyperplane whose margin is within a factor of $(1-\epsilon)$ of that of the maximum-margin separating hyperplane. We discuss how our algorithm can be extended … Read more