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

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_{q\in Q}G_q}{\sqrt{n}}δ,\] where $(G_q{)}_{q\in Q}$ 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$.

arXiv commentPublished in at http://dx.doi.org/10.3150/09-BEJ225 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (2)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Risk bounds for statistical learning

Cited by in corpus (9)

• Deviation optimal learning using greedy Q-aggregation
• Sharp Oracle Inequalities for Aggregation of Affine Estimators
• Mirror averaging with sparsity priors
• Performance of empirical risk minimization in linear aggregation
• Optimal learning with $Q$-aggregation
• Empirical risk minimization is optimal for the convex aggregation problem
• On the optimality of the aggregate with exponential weights for low temperatures
• General nonexact oracle inequalities for classes with a subexponential envelope
• Optimal exponential bounds for aggregation of density estimators