Local Rademacher complexities

Abstract

We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical version of Rademacher averages, in the sense that the Rademacher averages are computed from the data, on a subset of functions with small empirical error. We present some applications to classification and prediction with convex function classes, and with kernel classes in particular.

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

References in corpus (1)

• Complexity regularization via localized random penalties

Cited by in corpus (41)

• Classification with Noisy Labels by Importance Reweighting
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Deep Neural Networks for Estimation and Inference
• On Mean Absolute Error for Deep Neural Network Based Vector-to-Vector Regression
• Boosting with early stopping: Convergence and consistency
• Fast rates for support vector machines using Gaussian kernels
• Estimating conditional quantiles with the help of the pinball loss
• Statistical performance of support vector machines
• Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations
• On the Existence of Simpler Machine Learning Models
• Model selection by resampling penalization
• Empirical entropy, minimax regret and minimax risk
• Regularization in kernel learning
• Complexities of convex combinations and bounding the generalization error in classification
• Fast Rates by Transferring from Auxiliary Hypotheses
• Full error analysis for the training of deep neural networks
• On the optimal estimation of probability measures in weak and strong topologies
• Low-Rank Covariance Function Estimation for Multidimensional Functional Data
• Optimizing Two-way Partial AUC with an End-to-end Framework
• Surrogate Losses in Passive and Active Learning
• Minimax fast rates for discriminant analysis with errors in variables
• LocalDrop: A Hybrid Regularization for Deep Neural Networks
• Tight Risk Bounds for Multi-Class Margin Classifiers
• Bayesian Cramér-Rao Bound Estimation with Score-Based Models
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Margin-adaptive model selection in statistical learning
• Recovering Structured Data From Superimposed Non-Linear Measurements
• The shattering dimension of sets of linear functionals
• Minimax Rates for Conditional Density Estimation via Empirical Entropy
• Robust 1-Bit Compressed Sensing via Hinge Loss Minimization
• A Distribution Dependent and Independent Complexity Analysis of Manifold Regularization
• Convolutional neural networks for valid and efficient causal inference
• Semi-supervised Vector-valued Learning: Improved Bounds and Algorithms
• Comment on "Support Vector Machines with Applications"
• Data-Adaptive Discriminative Feature Localization with Statistically Guaranteed Interpretation
• Fitted value iteration methods for bicausal optimal transport
• Strong overall error analysis for the training of artificial neural networks via random initializations
• When are epsilon-nets small?
• Distributionally robust risk evaluation with a causality constraint and structural information
• Deep Regression for Repeated Measurements
• Generalization bounds and sample complexity for remaining useful life prediction from complete degradation trajectories