support vector classification – Optimization Online

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

Published: 2009/04/10

Convex Optimization approximation algorithms, core sets, frank-wolfe, linear convergence, support vector classification, support vector machines

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