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

DOI10.3150/09-BEJ225MaRDI QIDQ637070zbMATH OpenOpenAlexFDO

Authors Guillaume Lecué, Shahar Mendelson

Publication date 2 September 2011

Published in Bernoulli (Search for Journal in Brave)

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

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)

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$.

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)

Cites work

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

Cited in

(11)

• Learning Theory
• Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model
• Lower Bounds for the Empirical Minimization Algorithm
• On the Stability of Empirical Risk Minimization in the Presence of Multiple Risk Minimizers
• Performance of empirical risk minimization in linear aggregation
• Optimal learning with \textit{Q}-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)