Statistical performance of support vector machines

Abstract

The support vector machine (SVM) algorithm is well known to the computer learning community for its very good practical results. The goal of the present paper is to study this algorithm from a statistical perspective, using tools of concentration theory and empirical processes. Our main result builds on the observation made by other authors that the SVM can be viewed as a statistical regularization procedure. From this point of view, it can also be interpreted as a model selection principle using a penalized criterion. It is then possible to adapt general methods related to model selection in this framework to study two important points: (1) what is the minimum penalty and how does it compare to the penalty actually used in the SVM algorithm; (2) is it possible to obtain ``oracle inequalities'' in that setting, for the specific loss function used in the SVM algorithm? We show that the answer to the latter question is positive and provides relevant insight to the former. Our result shows that it is possible to obtain fast rates of convergence for SVMs.

Published in at http://dx.doi.org/10.1214/009053607000000839 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (8)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Local Rademacher complexities
• Fast rates for support vector machines using Gaussian kernels
• Risk bounds for statistical learning
• Complexity regularization via localized random penalties
• Square Root Penalty: Adaptation to the Margin in Classification and in Edge Estimation
• Simultaneous adaptation to the margin and to complexity in classification
• A new concentration result for regularized risk minimizers

Cited by in corpus (40)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Fast learning rates for plug-in classifiers
• Estimating conditional quantiles with the help of the pinball loss
• Optimal weighted nearest neighbour classifiers
• Sparsity in multiple kernel learning
• Sharp analysis of low-rank kernel matrix approximations
• Regularization in kernel learning
• Universally consistent vertex classification for latent positions graphs
• Simultaneous adaptation to the margin and to complexity in classification
• Fast learning rates for plug-in classifiers under the margin condition
• Flexible High-dimensional Classification Machines and Their Asymptotic Properties
• Distributed Inference for Linear Support Vector Machine
• Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• Performance Analysis of Support Vector Machine (SVM) on Challenging Datasets for Forest Fire Detection
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• Optimal rates of aggregation in classification under low noise assumption
• A new concentration result for regularized risk minimizers
• SLIDE: a surrogate fairness constraint to ensure fairness consistency
• Learning from dependent observations
• Classification with the nearest neighbor rule in general finite dimensional spaces: necessary and sufficient conditions
• Anisotropic oracle inequalities in noisy quantization
• Local Rademacher Complexity Bounds based on Covering Numbers
• Distance-weighted Support Vector Machine
• Asymptotic Confidence Sets for General Nonparametric Regression and Classification by Regularized Kernel Methods
• Double Sparsity Kernel Learning with Automatic Variable Selection and Data Extraction
• Comment on "Support Vector Machines with Applications"
• Bandwidth selection in kernel empirical risk minimization via the gradient
• Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
• Comment on "Support Vector Machines with Applications"
• A Critical Connectivity Radius for Segmenting Randomly-Generated, High Dimensional Data Points
• Some Theoretical Results Regarding the Polygonal Distribution
• A reproducing kernel Hilbert space framework for functional data classification
• Learning rates of $l^q$ coefficient regularization learning with Gaussian kernel
• Finding the Optimal Dynamic Treatment Regime Using Smooth Fisher Consistent Surrogate Loss
• Learning Rates for Kernel-Based Expectile Regression
• Statistical learning with indirect observations
• Cox process functional learning
• Large-Margin Classification with Multiple Decision Rules
• Asymptotic Normality of Support Vector Machine Variants and Other Regularized Kernel Methods