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 (4)

• Statistical performance of support vector machines
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Moment inequalities for functions of independent random variables
• Complexities of convex combinations and bounding the generalization error in classification

Cited by in corpus (118)

• Deep Neural Networks for Estimation and Inference
• Fast learning rates for plug-in classifiers
• 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
• Empirical entropy, minimax regret and minimax risk
• On the statistical complexity of quantum circuits
• Model selection by resampling penalization
• 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
• Rates of convergence in active learning
• 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
• Minimax fast rates for discriminant analysis with errors in variables
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• A universal procedure for aggregating estimators
• Distributed inference for quantile regression processes
• Singularity, Misspecification, and the Convergence Rate of EM
• PAC-Bayesian aggregation and multi-armed bandits
• Empirical risk minimization is optimal for the convex aggregation problem
• Honest Confidence Sets in Nonparametric IV Regression and Other Ill-Posed Models
• Oracle inequalities for computationally adaptive model selection
• Early stopping for kernel boosting algorithms: A general analysis with localized complexities
• One-step ahead sequential Super Learning from short times series of many slightly dependent data, and anticipating the cost of natural disasters
• On the optimality of the aggregate with exponential weights for low temperatures
• Sharper lower bounds on the performance of the empirical risk minimization algorithm
• Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
• General nonexact oracle inequalities for classes with a subexponential envelope
• Linear regression through PAC-Bayesian truncation
• 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
• Statistical learning with Lipschitz and convex loss functions
• Bayesian fractional posteriors
• Adapting to Unknown Smoothness by Aggregation of Thresholded Wavelet Estimators
• Robustness of shape-restricted regression estimators: an envelope perspective
• Rademacher complexity of noisy quantum circuits
• Faster Rates for Policy Learning
• Risk bounds in linear regression through PAC-Bayesian truncation
• Fast Rates for Contextual Linear Optimization
• Localized Complexities for Transductive Learning
• Weighted Training for Cross-Task Learning
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• 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
• Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
• Variable selection through CART
• Fast learning rate of deep learning via a kernel perspective
• Convergence rates of least squares regression estimators with heavy-tailed errors
• Risk Bounds for CART Classifiers under a Margin Condition
• Sample Average Approximation for Stochastic Programming with Equality Constraints
• Concentration Inequalities for Two-Sample Rank Processes with Application to Bipartite Ranking
• On Empirical Risk Minimization with Dependent and Heavy-Tailed Data
• Fast rates in statistical and online learning
• Excess Risk Bounds for Exponentially Concave Losses
• Minimax-Optimal Bounds for Detectors Based on Estimated Prior Probabilities
• Quantile Processes for Semi and Nonparametric Regression
• From Stochastic Mixability to Fast Rates
• Complex sampling designs: uniform limit theorems and applications
• Optimistic bounds for multi-output prediction
• Statistical Inference after Kernel Ridge Regression Imputation under item nonresponse
• Refined Error Bounds for Several Learning Algorithms
• Minimax Analysis of Active Learning
• On the Rates of Convergence from Surrogate Risk Minimizers to the Bayes Optimal Classifier
• Improved Rademacher symmetrization through a Wasserstein based measure of asymmetry
• Optimal oracle inequalities for solving projected fixed-point equations
• Statistical Learning under Nonstationary Mixing Processes
• Bandwidth selection in kernel empirical risk minimization via the gradient
• Model Selection by Loss Rank for Classification and Unsupervised Learning
• Understanding Deep Architectures with Reasoning Layer
• Policy Transforms and Learning Optimal Policies
• An Empirical Study on Regularization of Deep Neural Networks by Local Rademacher Complexity
• Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
• High-Dimensional Semiparametric Selection Models: Estimation Theory with an Application to the Retail Gasoline Market
• Stochastic Lipschitz continuity for high dimensional Lasso with multiple linear covariate structures or hidden linear covariates
• Fast generalization error bound of deep learning without scale invariance of activation functions
• Statistical optimality conditions for compressive ensembles
• Nearly Optimal Clustering Risk Bounds for Kernel K-Means
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• Beating the Minimax Rate of Active Learning with Prior Knowledge
• An elementary analysis of ridge regression with random design
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Robust Learning under Strong Noise via SQs
• Kernel ridge vs. principal component regression: minimax bounds and adaptability of regularization operators
• Empirical Hypothesis Space Reduction
• Optimal exponential bounds on the accuracy of classification
• Early stopping and polynomial smoothing in regression with reproducing kernels
• Classes of ODE solutions: smoothness, covering numbers, implications for noisy function fitting, and the curse of smoothness phenomenon
• The two-sample problem for Poisson processes: adaptive tests with a non-asymptotic wild bootstrap approach
• Uncertainty quantification for distributed regression
• Suboptimality of Penalized Empirical Risk Minimization in Classification
• Regularized ERM on random subspaces
• Fast Learning Rate of lp-MKL and its Minimax Optimality
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Multiplier U-processes: sharp bounds and applications
• Deep Regression for Repeated Measurements
• Sharp Convergence Rate and Support Consistency of Multiple Kernel Learning with Sparse and Dense Regularization