  


A Linearly Convergent LinearTime FirstOrder Algorithm for Support Vector Classification with a Core Set Result
Piyush Kumar(piyushcs.fsu.edu) Abstract: We present a simple, firstorder 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 maximummargin separating hyperplane. We discuss how our algorithm can be extended to nonlinearly separable and inseparable data sets. The running time of our algorithm is linear in the number of data points and in $1/\epsilon$. In particular, the number of support vectors computed by the algorithm is bounded above by $O(\zeta/\epsilon)$ for all sufficiently small $\epsilon > 0$, where $\zeta$ is the square of the ratio of the distances between the farthest and closest points in the two data sets. Furthermore, we establish that our algorithm exhibits linear convergence. We adopt the real number model of computation in our analysis. Keywords: Support vector machines, support vector classification, FrankWolfe algorithm, approximation algorithms, core sets, linear convergence. Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Bilkent University, Department of Industrial Engineering, Technical Report, April 2008. Download: [PDF] Entry Submitted: 04/10/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  