Sharper lower bounds on the performance of the empirical risk minimization algorithm

DOI10.3150/09-BEJ225zbMATH Open1220.62007arXiv1102.4983OpenAlexW3098804594MaRDI QIDQ637070FDOQ637070

Authors: Guillaume Lecué, Shahar Mendelson 

Publication date: 2 September 2011

Published in: Bernoulli (Search for Journal in Brave)

Abstract: We present an argument based on the multidimensional and the uniform central limit theorems, proving that, under some geometrical assumptions between the target function $T$ and the learning class $F$, the excess risk of the empirical risk minimization algorithm is lower bounded by [frac{mathbb{E}sup_{qin Q}G_q}{sqrt{n}}delta,] where $(G_q{)}_{qinQ}$ is a canonical Gaussian process associated with $Q$ (a well chosen subset of $F$) and $delta$ is a parameter governing the oscillations of the empirical excess risk function over a small ball in $F$.

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

Recommendations

• Lower Bounds for the Empirical Minimization Algorithm
• Learning Theory
• Risk bounds for statistical learning
• Empirical minimization
• Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)

zbMATH Keywords

learning theorylower bounduniform central limit theoremmultidimensional central limit theorem

Mathematics Subject Classification ID

Inference from stochastic processes (62M99) Gaussian processes (60G15) Central limit and other weak theorems (60F05) Statistical decision theory (62C99)

Cites Work

• Weak convergence and empirical processes. With applications to statistics
• Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
• Uniform Central Limit Theorems
• The Generic Chaining
• The importance of convexity in learning with squared loss
• Risk bounds for statistical learning
• Empirical minimization
• Lower Bounds for the Empirical Minimization Algorithm
• Suboptimality of Penalized Empirical Risk Minimization in Classification

Cited In (11)

• Learning Theory
• Lower Bounds for the Empirical Minimization Algorithm
• On the Stability of Empirical Risk Minimization in the Presence of Multiple Risk Minimizers
• Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model
• Optimal learning with \textit{Q}-aggregation
• Performance of empirical risk minimization in linear aggregation
• On the optimality of the aggregate with exponential weights for low temperatures
• Empirical risk minimization is optimal for the convex aggregation problem
• General oracle inequalities for model selection
• General nonexact oracle inequalities for classes with a subexponential envelope
• On the optimality of sample-based estimates of the expectation of the empirical minimizer

This page was built for publication: Sharper lower bounds on the performance of the empirical risk minimization algorithm

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