Complexity regularization via localized random penalties

Abstract

In this article, model selection via penalized empirical loss minimization in nonparametric classification problems is studied. Data-dependent penalties are constructed, which are based on estimates of the complexity of a small subclass of each model class, containing only those functions with small empirical loss. The penalties are novel since those considered in the literature are typically based on the entire model class. Oracle inequalities using these penalties are established, and the advantage of the new penalties over those based on the complexity of the whole model class is demonstrated.

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

Cited by in corpus (13)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Local Rademacher complexities
• Boosting for high-dimensional linear models
• Boosting with early stopping: Convergence and consistency
• Statistical performance of support vector machines
• Learning by mirror averaging
• On the Existence of Simpler Machine Learning Models
• Sparse Estimation by Exponential Weighting
• Model selection by resampling penalization
• Complexities of convex combinations and bounding the generalization error in classification
• Simultaneous adaptation to the margin and to complexity in classification
• Square Root Penalty: Adaptation to the Margin in Classification and in Edge Estimation
• Margin-adaptive model selection in statistical learning