Fast rates for support vector machines using Gaussian kernels

By Ingo Steinwart, Clint Scovel. 2007

293 citations recorded by the source corpus.

For binary classification we establish learning rates up to the order of n −1 for support vector machines (SVMs) with hinge loss and Gaussian RBF kernels. These rates are in terms of two assumptions on the considered distributions: Tsybakov’s noise assumption to establish a small estimation error, and a new geometric noise condition which is used to bound the approximation error. Unlike previously proposed concepts for bounding the approximation error, the geometric noise assumption does not employ any smoothness assumption. 1. Introduction. In recent years support vector machines (SVMs) have been the subject of many theoretical considerations. Despite this effort, their learning performance on restricted classes of distributions is still widely unknown. In particular, it is unknown under which nontrivial circumstances SVMs can guarantee fast learning rates. The aim of this work is to use concepts like Tsybakov’s noise assumption and local Rademacher averages to establish learning rates up to the order of n −1 for nontrivial distributions. In addition to these concepts that are used to deal with the stochastic part of the analysis we also introduce a geometric assumption for distributions that allows us to estimate the approximation properties of Gaussian RBF kernels. Unlike many other concepts introduced for bounding the approximation error, our geometric assumption is not in terms of smoothness but describes the concentration and the noisiness of the data-generating distribution near the decision boundary. Let us formally introduce the statistical classification problem. To this end let us fix a subset X ⊂ R d . We write Y := {−1,1}. Given a finite training set

Subfields: Artificial Intelligence, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

Smoothness, Low Noise and Fast Rates (2010, methodology): “For example, Steinwart [27] used Local Rademacher Complexity to provide fast rate on the 0/1 loss of Support Vector Machines (SVMs) (`2-regularized hinge-loss minimization) based on the so called “geometric margin condition” and Tsybakov’s margin condition.”
Residual Weighted Learning for Estimating Individualized Treatment Rules (2015, methodology): “By Theorem 3.1, the Bayes rule ∈H { } That is, d ∗ needs to be approximated by functions in the space H K + { 1 } .”
Learning Kernel-Based Halfspaces with the 0-1 Loss (2011, background): “For example, in the statistical learning literature, there are several definitions of “noise” conditions, some of them are related to margin, which lead to faster decrease of the error rate as a function of the number of examples (see for example [10, 26, 25]).”
QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines (2006, background): “Applying (Lemma 14, Equation (19)) with q = p and ¯ σ = σ(α|Wp) on the left, and (Lemma 14, Equation ( 18 )) with q = n on the right gives”
Fast cross-validation via sequential testing (2012, background): “Approximation errors have been studied for example in the papers by Smale and Zhou (2003) and Steinwart and Scovel (2007), but the papers only prove upper bounds, and the rates are also worst-case rates which are likely not close enough to the true errors.”
Support Vector Machine Solvers (2007, background): “Well designed compromises lead to estimation and approximation errors that scale between the inverse and the inverse square root of the number of examples (Steinwart and Scovel, 2004).”
Optimal regression rates for SVMs using Gaussian kernels (2013, background): “To be more concrete, the currently best learning rates have been established in [33, 40].”
Generalization bounds for learning the kernel (2009, background): “Firstly, it would be interesting to get fast error rates with respect to the sample number as those in [4, 26, 27, 29].”
Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance (2019, unknown): “Rates faster than O(1/ √ n) can be obtained with a variety of added assumptions, such as some form of strong convexity [33, 7], noise conditions for classification [34], or extra conditions on the loss, such as self-concordance [2] or exp-concavity [19, 24], whose partial goal is to avoid exponentia”
A Classification Framework for Anomaly Detection (2005, background): “In recent years Tsybakov’s noise exponent has played a crucial role for establishing learning rates faster than n− 1 2 for certain algorithms (see e.g. Mammen and Tsybakov, 1999; Tsybakov, 2004; Steinwart and Scovel, 2004).”
On Early Stopping in Gradient Descent Learning (2007, methodology): “Our results can be extended to incorporate the geometric noise condition introduced by [Steinwart and Scovel 2005], which is however not pursued in this paper.”
Statistical performance of support vector machines (2008, result): “In [33], convergence properties of the standard SVM is studied in the case of the Gaussian kernel.”
Estimating Individualized Treatment Rules Using Outcome Weighted Learning (2012, methodology): “The proof is modiﬁed based on the literature by Vert and Vert (2006) and Steinwart and Scovel (2007), where the weights in the loss function are taken into consideration.”
Classification with a Reject Option using a Hinge Loss (2008, methodology): “…error term ε n approaches zero at a faster rate when the conditional probability η(X) is unlikely to be close to the critical value of 1/2 (Audibert and Tsybakov, 2007; Bartlett et al., 2006; Blanchard et al., 2008; Steinwart and Scovel, 2007; Tarigan and van de Geer, 2006; Tsybakov, 2004).”
Rademacher Chaos Complexities for Learning the Kernel Problem (2010, background): “Other assumptions on the distribution ρ such as the geometric noise condition introduced by Steinwart and Scovel (2005) are possible to achieve polynomial decays of the regularization error.”
Sufficient Dimension Reduction via Squared-Loss Mutual Information Estimation (2010, background): “The Gaussian RKHS satisfies this condition for arbitrarily small γ [27].”
Finite-Dimensional Projection for Classification and Statistical Learning (2008, unknown): “…if γ is an integer, the RKHS with this kernel is the Sobolev space of order γ with periodic boundary conditions It is known (see e.g. k | | (cid:16)R (cid:17) In this situation, the non-continuity of f ∗ prevents normal convergence of its Fourier series, so that necessarily α ≤ 1 . irregular .”