← Back to papers
2013 ICML ICML 2013

Learning Optimally Sparse Support Vector Machines

Abstract

We show how to train SVMs with an optimal guarantee on the number of support vectors (up to constants), and with sample complexity and training runtime bounds matching the best known for kernel SVM optimization (i.e. without any additional asymptotic cost beyond standard SVM training). Our method is simple to implement and works well in practice.

🚀 Conference Pioneer — ICML 2013
🌉 Interdisciplinary Bridge — Machine Learning and Mathematics & Optimization
🧭 Keyword Pioneer — generalization guarantee
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio

Authors

Andrew Cotter , Shai Shalev-shwartz , Nati Srebro

Topics

Machine Learning > Core Methods > Classification Machine Learning > Optimization & Theory > Optimization Mathematics & Optimization > Optimization > Sparse Optimization Machine Learning > Core Methods > Support Vector Machine

Keywords

feature selection sparse optimization support vector machine generalization guarantee sparse classification kernel methods
Download PDF

Related papers

Convex Adversarial Collective Classification 2013
Gaussian Process Vine Copulas for Multivariate Dependence 2013
Stochastic Simultaneous Optimistic Optimization 2013
Generic Exploration and K-armed Voting Bandits 2013
Robust Structural Metric Learning 2013