2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
Author:
- Vladimir KoltchinskiiVKVladimir Koltchinskii
Preprint
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_nf\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.
Keywords
All Related Versions
- Version 1, 2007-08-01, ArXiv
- Published version: The Annals of Statistics, 34 (6), 2593.
This publication has 32 references indexed in Scilit:
- Model selection for regression on a random designESAIM: Probability and Statistics, 2002
- A Distribution-Free Theory of Nonparametric Regression2002
- Une inégalité de concentration à gauche pour les processus empiriquesComptes Rendus Mathematique, 2002
- A Bennett concentration inequality and its application to suprema of empirical processesComptes Rendus Mathématique, 2002
- Inequalities for uniform deviations of averages from expectations with applications to nonparametric regressionJournal of Statistical Planning and Inference, 2000
- An Empirical Process Approach to the Uniform Consistency of Kernel-Type Function EstimatorsJournal of Theoretical Probability, 2000
- Risk bounds for model selection via penalizationProbability Theory and Related Fields, 1999
- New concentration inequalities in product spacesInventiones Mathematicae, 1996
- A Probabilistic Theory of Pattern Recognition1996
- Efficient agnostic learning of neural networks with bounded fan-inIEEE Transactions on Information Theory, 1996