Simultaneous adaptation to the margin and to complexity in classification

Abstract

We consider the problem of adaptation to the margin and to complexity in binary classification. We suggest an exponential weighting aggregation scheme. We use this aggregation procedure to construct classifiers which adapt automatically to margin and complexity. Two main examples are worked out in which adaptivity is achieved in frameworks proposed by Steinwart and Scovel [Learning Theory. Lecture Notes in Comput. Sci. 3559 (2005) 279--294. Springer, Berlin; Ann. Statist. 35 (2007) 575--607] and Tsybakov [Ann. Statist. 32 (2004) 135--166]. Adaptive schemes, like ERM or penalized ERM, usually involve a minimization step. This is not the case for our procedure.

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

References in corpus (11)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Fast learning rates for plug-in classifiers
• Fast rates for support vector machines using Gaussian kernels
• Risk bounds for statistical learning
• Aggregation for Gaussian regression
• Statistical performance of support vector machines
• Complexity regularization via localized random penalties
• Square Root Penalty: Adaptation to the Margin in Classification and in Edge Estimation
• Fast learning rates for plug-in classifiers under the margin condition
• Aggregation for Regression Learning
• Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii

Cited by in corpus (16)

• Statistical performance of support vector machines
• Fast learning rates in statistical inference through aggregation
• Sparse Estimation by Exponential Weighting
• Kullback-Leibler aggregation and misspecified generalized linear models
• Optimal rates of aggregation in classification under low noise assumption
• A universal procedure for aggregating estimators
• On the optimality of the aggregate with exponential weights for low temperatures
• Adapting to Unknown Smoothness by Aggregation of Thresholded Wavelet Estimators
• Margin-adaptive model selection in statistical learning
• Risk Bounds for CART Classifiers under a Margin Condition
• Classification with the nearest neighbor rule in general finite dimensional spaces: necessary and sufficient conditions
• Bandwidth selection in kernel empirical risk minimization via the gradient
• Aggregation of penalized empirical risk minimizers in regression
• Sharp Oracle Inequalities for Low-complexity Priors
• Ordered Smoothers With Exponential Weighting
• Suboptimality of Penalized Empirical Risk Minimization in Classification