Statistical performance of support vector machines

By Gilles Blanchard, Olivier Bousquet, Pascal Massart. 2008

175 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Optimal Rates for Regularized Least Squares Regression (2009, methodology): “Recall that the eigenvalue assumption (6) was first used in [5] to establish an oracle inequality for SVMs using the hinge loss, while [6] considers (6) for SVMs using the least squares loss and f∗ P ∈ H .”
Finite-Dimensional Projection for Classification and Statistical Learning (2008, unknown): “…K 1 ,n and its eigenvectors V 1 , . . . , V n together with its eigenvalues in decreasing order Next, put 3) The last step is the model selection problem consisting in choosing the dimension D ; for this step, we use the penalized trimmed hinge loss as studied earlier: where f D = clip( f D ) .”
Regularization in kernel learning (2010, background): “It should be noted that in the classification setting (to be more precise, in the example of support vector machines), Blanchard, Bousquet and Massart [5] showed that a regularization term of the form ηn‖f‖H was possible.”
Estimating conditional quantiles with the help of the pinball loss (2011, methodology): “Recall that (5) was first used in [6] to establish an oracle inequality for SVMs using the hinge loss, while [7, 18, 25] consider (5) for SVMs using the least-squares loss.”
Rejoinder: Local Rademacher complexities and oracle inequalities in risk minimization (2006, background): “tt, Jordan and McAuliﬀe [6] and Blanchard, Lugosi and Vayatis [10] obtained convergence rates of boosting-type classiﬁcation methods based on convex risk minimization. Blanchard, Bousquet and Massart [9] obtained interesting oracle inequalities for penalized empirical risk minimization in kernel mac”
Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning (2014, methodology): “It has been first proposed for classification by [5], and for regression by [17].”
Estimating Individualized Treatment Rules Using Outcome Weighted Learning (2012, methodology): “We can then use Theorem 4.3 in the article by Blanchard, Bousquet, and Massart (2008) after we verify the following conditions (H1)–(H4): We have ψ S ,S ∈ S , is a sequence of subroot functions, that is, ψ S is nonnegative, nondecreasing, and ψ S ( r ) / √ r is nonincreasing for r > 0 .”
New Statistical Learning Methods for Estimating Optimal Dynamic Treatment Regimes (2015, background): “The fast rate of convergence to the best achievable error for SVMs is anticipated provided certain conditions hold on the data-generating distribution (Tsybakov 2004; Steinwart and Scovel 2007; Blanchard, Bousquet, and Massart 2008).”
How to Compare Different Loss Functions and Their Risks (2007, background): “[1, 4] in order to derive variance bounds for margin-based losses, but of course it also works for distancebased losses.”
Classification with a Reject Option using a Hinge Loss (2008, methodology): “Specialized to the case (δ, d) = (0, 1/2), we note that Lemma 7 removes unnecessary technical restrictions on η(X) near 0 and 1, imposed in [5] and [12].”