Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)

DOI10.1214/009053606000001019MaRDI QIDQ2373576zbMATH OpenOpenAlexWikidataFDO

Authors Vladimir Koltchinskii

Publication date 12 July 2007

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.0083

zbMATH Keywords

model selectionclassificationconcentration inequalitiesempirical risk minimization

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Pattern recognition, speech recognition (68T10) Computational learning theory (68Q32) Probability theory on algebraic and topological structures (60B99)

Abstract: Let $mathcalF$ be a class of measurable functions $f:Smapsto[0,1]$ defined on a probability space $(S,mathcalA,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}fomin$, $finmathcalF$. 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):=Phat{f}_n-inf_{fin mathcal{F}}Pf,] expressed in terms of relevant geometric parameters of the class $mathcalF$. 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.

Recommendations

• scientific article; zbMATH DE number 1552503
• Local Rademacher complexities
• Learning Theory
• 10.1162/153244303321897690
• Risk bounds for statistical learning

Cites work

• scientific article; zbMATH DE number 2089352 (Why is no real title available?)
• scientific article; zbMATH DE number 2089354 (Why is no real title available?)
• scientific article; zbMATH DE number 5654889 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 1064642 (Why is no real title available?)
• scientific article; zbMATH DE number 2034518 (Why is no real title available?)
• scientific article; zbMATH DE number 1552503 (Why is no real title available?)
• scientific article; zbMATH DE number 3446442 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• 10.1162/1532443041424319
• A Bennett concentration inequality and its application to suprema of empirical processes
• A distribution-free theory of nonparametric regression
• A new look at independence
• A sharp concentration inequality with applications
• An empirical process approach to the uniform consistency of kernel-type function estimators
• Bounding the generalization error of convex combinations of classifiers: Balancing the dimensionality and the margins.
• Complexities of convex combinations and bounding the generalization error in classification
• Complexity regularization via localized random penalties
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Consistency of Support Vector Machines and Other Regularized Kernel Classifiers
• Convergence rate of sieve estimates
• Convexity, Classification, and Risk Bounds
• Efficient agnostic learning of neural networks with bounded fan-in
• Empirical margin distributions and bounding the generalization error of combined classifiers
• Empirical minimization
• Improving the sample complexity using global data
• Inequalities for uniform deviations of averages from expectations with applications to nonparametric regression
• Left concentration inequalities for empirical processes
• Local Rademacher complexities
• Model selection and error estimation
• Model selection for regression on a random design
• Moment inequalities for functions of independent random variables
• Neural Network Learning
• New concentration inequalities in product spaces
• On consistency of kernel density estimators for randomly censored data: Rates holding uniformly over adaptive intervals
• On the Bayes-risk consistency of regularized boosting methods.
• Optimal aggregation of classifiers in statistical learning.
• Oracle inequalities and nonparametric function estimation
• Rademacher penalties and structural risk minimization
• Risk bounds for model selection via penalization
• Sharper bounds for Gaussian and empirical processes
• Smooth discrimination analysis
• Some applications of concentration inequalities to statistics
• Some limit theorems for empirical processes (with discussion)
• Square root penalty: Adaption to the margin in classification and in edge estimation
• Statistical behavior and consistency of classification methods based on convex risk minimization.
• Statistical performance of support vector machines
• Uniform Central Limit Theorems
• Weak convergence and empirical processes. With applications to statistics

Cited in

(only showing first 100 items - show all)

• On the optimality of the aggregate with exponential weights for low temperatures
• Deep Regression for Repeated Measurements
• Inference on covariance operators via concentration inequalities: \(k\)-sample tests, classification, and clustering via Rademacher complexities
• Empirical risk minimization is optimal for the convex aggregation problem
• Empirical risk minimization for heavy-tailed losses
• Local Rademacher complexity: sharper risk bounds with and without unlabeled samples
• Adaptive kernel methods using the balancing principle
• DRM revisited: a complete error analysis
• General oracle inequalities for model selection
• Inverse statistical learning
• Discussion of ``On concentration for (regularized) empirical risk minimization by Sara van de Geer and Martin Wainwright
• Bandwidth selection in kernel empirical risk minimization via the gradient
• scientific article; zbMATH DE number 7626745 (Why is no real title available?)
• Minimax fast rates for discriminant analysis with errors in variables
• General nonexact oracle inequalities for classes with a subexponential envelope
• Solving PDEs on spheres with physics-informed convolutional neural networks
• A moment-matching approach to testable learning and a new characterization of Rademacher complexity
• Deep learning: a statistical viewpoint
• Multiplier \(U\)-processes: sharp bounds and applications
• Simultaneous adaptation to the margin and to complexity in classification
• FAST RATES FOR ESTIMATION ERROR AND ORACLE INEQUALITIES FOR MODEL SELECTION
• Optimal survey schemes for stochastic gradient descent with applications to \(M\)-estimation
• The two-sample problem for Poisson processes: adaptive tests with a nonasymptotic wild bootstrap approach
• On the optimality of the empirical risk minimization procedure for the convex aggregation problem
• Statistical performance of support vector machines
• A statistical view of clustering performance through the theory of U-processes
• Optimal upper and lower bounds for the true and empirical excess risks in heteroscedastic least-squares regression
• Optimal model selection in heteroscedastic regression using piecewise polynomial functions
• Direct importance estimation for covariate shift adaptation
• Gibbs posterior concentration rates under sub-exponential type losses
• Nonasymptotic analysis of robust regression with modified Huber's loss
• Complexities of convex combinations and bounding the generalization error in classification
• From Gauss to Kolmogorov: localized measures of complexity for ellipses
• Policy learning ``without overlap: pessimism and generalized empirical Bernstein's inequality
• On the optimality of sample-based estimates of the expectation of the empirical minimizer
• Sparsity in penalized empirical risk minimization
• Regularization in kernel learning
• Robust supervised learning with coordinate gradient descent
• Variance-based regularization with convex objectives
• 10.1162/153244303321897690
• Model selection by bootstrap penalization for classification
• Theory of Classification: a Survey of Some Recent Advances
• scientific article; zbMATH DE number 7660136 (Why is no real title available?)
• Concentration inequalities for samples without replacement
• A universal procedure for aggregating estimators
• Bayesian fractional posteriors
• Parametric or nonparametric? A parametricness index for model selection
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Learning Theory
• Rademacher penalties and structural risk minimization
• Nonparametric regression using deep neural networks with ReLU activation function
• Convergence rates for shallow neural networks learned by gradient descent
• Aggregation of estimators and stochastic optimization
• Fast learning rate of non-sparse multiple kernel learning and optimal regularization strategies
• Localized Gaussian width of \(M\)-convex hulls with applications to Lasso and convex aggregation
• Suboptimality of constrained least squares and improvements via non-linear predictors
• Local learning estimates by integral operators
• scientific article; zbMATH DE number 7370563 (Why is no real title available?)
• scientific article; zbMATH DE number 7370593 (Why is no real title available?)
• scientific article; zbMATH DE number 7306926 (Why is no real title available?)
• Forecasting the cost of drought events in France by super learning from a short time series of many slightly dependent data
• Relative deviation learning bounds and generalization with unbounded loss functions
• On least squares estimation under heteroscedastic and heavy-tailed errors
• Fast learning rates in statistical inference through aggregation
• Performance guarantees for policy learning
• Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendable geodesics
• Rho-estimators revisited: general theory and applications
• Tests and estimation strategies associated to some loss functions
• Optimal linear discriminators for the discrete choice model in growing dimensions
• Tikhonov, Ivanov and Morozov regularization for support vector machine learning
• Sampling and empirical risk minimization
• Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
• Model selection by resampling penalization
• A no-free-lunch theorem for multitask learning
• Concentration inequalities for two-sample rank processes with application to bipartite ranking
• A high-dimensional Wilks phenomenon
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Local Rademacher complexity-based learning guarantees for multi-task learning
• A new method for estimation and model selection: \(\rho\)-estimation
• Oracle inequalities for cross-validation type procedures
• Empirical minimization
• Singularity, misspecification and the convergence rate of EM
• Convergence rates of least squares regression estimators with heavy-tailed errors
• Square root penalty: Adaption to the margin in classification and in edge estimation
• scientific article; zbMATH DE number 1804106 (Why is no real title available?)
• Adaptive estimation of a distribution function and its density in sup-norm loss by wavelet and spline projections
• Measuring the capacity of sets of functions in the analysis of ERM
• Sharper lower bounds on the performance of the empirical risk minimization algorithm
• Robust multicategory support vector machines using difference convex algorithm
• Risk bounds for CART classifiers under a margin condition
• Margin-adaptive model selection in statistical learning
• Global uniform risk bounds for wavelet deconvolution estimators
• ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels
• Wild bootstrap inference for penalized quantile regression for longitudinal data
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Empirical variance minimization with applications in variance reduction and optimal control
• A local Vapnik-Chervonenkis complexity
• Honest confidence sets in nonparametric IV regression and other ill-posed models
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• Fast learning rates for plug-in classifiers

This page was built for publication: Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373576)