Fast rates for support vector machines using Gaussian kernels

Abstract

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.

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

References in corpus (1)

• Local Rademacher complexities

Cited by in corpus (44)

• Fast learning rates for plug-in classifiers
• Statistical performance of support vector machines
• Regularization in kernel learning
• Nonlinear Approximation Using Gaussian Kernels
• Optimistic Rates for Learning with a Smooth Loss
• Simultaneous adaptation to the margin and to complexity in classification
• Flexible High-dimensional Classification Machines and Their Asymptotic Properties
• Fast Cross-Validation via Sequential Testing
• Asymptotic distribution and sparsistency for l1-penalized parametric M-estimators with applications to linear SVM and logistic regression
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Optimal rates of aggregation in classification under low noise assumption
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Fast Polynomial Kernel Classification for Massive Data
• Adapting to Unknown Smoothness by Aggregation of Thresholded Wavelet Estimators
• A new concentration result for regularized risk minimizers
• A Statistical Learning Assessment of Huber Regression
• Tree based weighted learning for estimating individualized treatment rules with censored data
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• Minimax-Optimal Bounds for Detectors Based on Estimated Prior Probabilities
• Learning from dependent observations
• Tight Sample Complexity of Large-Margin Learning
• Improved Classification Rates for Localized SVMs
• Asymptotic Confidence Sets for General Nonparametric Regression and Classification by Regularized Kernel Methods
• Near-optimal Individualized Treatment Recommendations
• A semiparametric instrumental variable approach to optimal treatment regimes under endogeneity
• Double Sparsity Kernel Learning with Automatic Variable Selection and Data Extraction
• Residual Weighted Learning for Estimating Individualized Treatment Rules
• Aggregation of penalized empirical risk minimizers in regression
• Doubly Robust Direct Learning for Estimating Conditional Average Treatment Effect
• Sparse Feature Selection in Kernel Discriminant Analysis via Optimal Scoring
• Feature Elimination in Kernel Machines in moderately high dimensions
• Best-scored Random Forest Classification
• Learning rates of $l^q$ coefficient regularization learning with Gaussian kernel
• A General Framework of Nonparametric Feature Selection in High-Dimensional Data
• Large-Margin Classification with Multiple Decision Rules
• Learning Optimal Distributionally Robust Individualized Treatment Rules
• Distribution-Dependent Sample Complexity of Large Margin Learning
• Anisotropic Gaussian approximation in $L_2({\mathbb{R}}^2)$
• Finding the Optimal Dynamic Treatment Regime Using Smooth Fisher Consistent Surrogate Loss
• Asymptotic Normality of Support Vector Machine Variants and Other Regularized Kernel Methods
• Learning rates for the risk of kernel based quantile regression estimators in additive models
• Learning From Non-iid Data: Fast Rates for the One-vs-All Multiclass Plug-in Classifiers
• Learning rates for classification with Gaussian kernels
• Model selection of polynomial kernel regression