2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization

Abstract

Let $\mathcal{F}$ be a class of measurable functions $f:S\mapsto [0,1]$ defined on a probability space $(S,\mathcal{A},P)$. Given a sample (X_1,...,X_n) of i.i.d. random variables taking values in S with common distribution P, let P_n denote the empirical measure based on (X_1,...,X_n). We study an empirical risk minimization problem $P_{n}f\to \min$, $f\in \mathcal{F}$. Given a solution ${\hat{f}}_n$ of this problem, the goal is to obtain very general upper bounds on its excess risk \[\mathcal{E}_P(\hat{f}_n):=P\hat{f}_n-\inf_{f\in \mathcal{F}}Pf,\] expressed in terms of relevant geometric parameters of the class $\mathcal{F}$. Using concentration inequalities and other empirical processes tools, we obtain both distribution-dependent and data-dependent upper bounds on the excess risk that are of asymptotically correct order in many examples. The bounds involve localized sup-norms of empirical and Rademacher processes indexed by functions from the class. We use these bounds to develop model selection techniques in abstract risk minimization problems that can be applied to more specialized frameworks of regression and classification.

This paper discussed in: [arXiv:0708.0089], [arXiv:0708.0094], [arXiv:0708.0098], [arXiv:0708.0121], [arXiv:0708.0124], [arXiv:0708.0132]. Rejoinder in [arXiv:0708.0135]. Published at http://dx.doi.org/10.1214/009053606000001019 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (7)

• Local Rademacher complexities
• Statistical performance of support vector machines
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Moment inequalities for functions of independent random variables
• Complexity regularization via localized random penalties
• Complexities of convex combinations and bounding the generalization error in classification
• Square Root Penalty: Adaptation to the Margin in Classification and in Edge Estimation

Cited by in corpus (121)

• Fast learning rates for plug-in classifiers
• Deep Neural Networks for Estimation and Inference
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Nonparametric regression using deep neural networks with ReLU activation function
• Aggregation for Gaussian regression
• Statistical performance of support vector machines
• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• Data-driven calibration of penalties for least-squares regression
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Rademacher Complexity for Adversarially Robust Generalization
• Global uniform risk bounds for wavelet deconvolution estimators
• Fast learning rates in statistical inference through aggregation
• Learning Theory Approach to Minimum Error Entropy Criterion
• Empirical risk minimization for heavy-tailed losses
• On the statistical complexity of quantum circuits
• 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
• Asymptotic behavior of ${\ell }_p$-based Laplacian regularization in semi-supervised learning
• Activized Learning: Transforming Passive to Active with Improved Label Complexity
• Parametric or nonparametric? A parametricness index for model selection
• A new method for estimation and model selection: $\rho$-estimation
• Square Root Penalty: Adaptation to the Margin in Classification and in Edge Estimation
• Simultaneous adaptation to the margin and to complexity in classification
• Rates of convergence in active learning
• Fast learning rates for plug-in classifiers under the margin condition
• The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning
• On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces
• Adaptive estimation of a distribution function and its density in sup-norm loss by wavelet and spline projections
• Sparse recovery in convex hulls via entropy penalization
• Concentration Inequalities and Confidence Bands for Needlet Density Estimators on Compact Homogeneous Manifolds
• Minimal penalties and the slope heuristics: a survey
• Constrained Classification and Policy Learning
• Gibbs posterior concentration rates under sub-exponential type losses
• Learning nonlinear dynamical systems from a single trajectory
• Surrogate Losses in Passive and Active Learning
• Randomized sketches for kernels: Fast and optimal non-parametric regression
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• Minimax fast rates for discriminant analysis with errors in variables
• A universal procedure for aggregating estimators
• Distributed inference for quantile regression processes
• Singularity, Misspecification, and the Convergence Rate of EM
• Honest Confidence Sets in Nonparametric IV Regression and Other Ill-Posed Models
• Oracle inequalities for computationally adaptive model selection
• Empirical risk minimization is optimal for the convex aggregation problem
• PAC-Bayesian aggregation and multi-armed bandits
• One-step ahead sequential Super Learning from short times series of many slightly dependent data, and anticipating the cost of natural disasters
• Early stopping for kernel boosting algorithms: A general analysis with localized complexities
• On the optimality of the aggregate with exponential weights for low temperatures
• Sharper lower bounds on the performance of the empirical risk minimization algorithm
• General nonexact oracle inequalities for classes with a subexponential envelope
• Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
• Linear regression through PAC-Bayesian truncation
• Statistical learning with Lipschitz and convex loss functions
• Inference on covariance operators via concentration inequalities: k-sample tests, classification, and clustering via Rademacher complexities
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Adapting to Unknown Smoothness by Aggregation of Thresholded Wavelet Estimators
• Bayesian fractional posteriors
• Rademacher complexity of noisy quantum circuits
• Risk bounds in linear regression through PAC-Bayesian truncation
• Robustness of shape-restricted regression estimators: an envelope perspective
• Faster Rates for Policy Learning
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Fast Rates for Contextual Linear Optimization
• Localized Complexities for Transductive Learning
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Weighted Training for Cross-Task Learning
• Margin-adaptive model selection in statistical learning
• Convergence rates of least squares regression estimators with heavy-tailed errors
• Risk Bounds for CART Classifiers under a Margin Condition
• Variable selection through CART
• Fast learning rate of deep learning via a kernel perspective
• Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
• Sample Average Approximation for Stochastic Programming with Equality Constraints
• Concentration Inequalities for Two-Sample Rank Processes with Application to Bipartite Ranking
• Fast rates in statistical and online learning
• Minimax-Optimal Bounds for Detectors Based on Estimated Prior Probabilities
• On Empirical Risk Minimization with Dependent and Heavy-Tailed Data
• Excess Risk Bounds for Exponentially Concave Losses
• Refined Error Bounds for Several Learning Algorithms
• Optimistic bounds for multi-output prediction
• From Stochastic Mixability to Fast Rates
• Statistical Inference after Kernel Ridge Regression Imputation under item nonresponse
• Quantile Processes for Semi and Nonparametric Regression
• Complex sampling designs: uniform limit theorems and applications
• Improved Rademacher symmetrization through a Wasserstein based measure of asymmetry
• Understanding Deep Architectures with Reasoning Layer
• Optimal oracle inequalities for solving projected fixed-point equations
• On the Rates of Convergence from Surrogate Risk Minimizers to the Bayes Optimal Classifier
• Statistical Learning under Nonstationary Mixing Processes
• Bandwidth selection in kernel empirical risk minimization via the gradient
• Minimax Analysis of Active Learning
• Model Selection by Loss Rank for Classification and Unsupervised Learning
• Stochastic Lipschitz continuity for high dimensional Lasso with multiple linear covariate structures or hidden linear covariates
• Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
• Statistical optimality conditions for compressive ensembles
• Fast generalization error bound of deep learning without scale invariance of activation functions
• Policy Transforms and Learning Optimal Policies
• High-Dimensional Semiparametric Selection Models: Estimation Theory with an Application to the Retail Gasoline Market
• Nearly Optimal Clustering Risk Bounds for Kernel K-Means
• An Empirical Study on Regularization of Deep Neural Networks by Local Rademacher Complexity
• Fast Learning Rate of lp-MKL and its Minimax Optimality
• Empirical Hypothesis Space Reduction
• Suboptimality of Penalized Empirical Risk Minimization in Classification
• The two-sample problem for Poisson processes: adaptive tests with a non-asymptotic wild bootstrap approach
• Early stopping and polynomial smoothing in regression with reproducing kernels
• Deep Regression for Repeated Measurements
• Robust Learning under Strong Noise via SQs
• Kernel ridge vs. principal component regression: minimax bounds and adaptability of regularization operators
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• Regularized ERM on random subspaces
• Multiplier U-processes: sharp bounds and applications
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Classes of ODE solutions: smoothness, covering numbers, implications for noisy function fitting, and the curse of smoothness phenomenon
• Sharp Convergence Rate and Support Consistency of Multiple Kernel Learning with Sparse and Dense Regularization
• Beating the Minimax Rate of Active Learning with Prior Knowledge
• Uncertainty quantification for distributed regression
• An elementary analysis of ridge regression with random design
• Optimal exponential bounds on the accuracy of classification