Empirical risk minimization is optimal for the convex aggregation problem

Abstract

Let $F$ be a finite model of cardinality $M$ and denote by $\mathrm{conv}(F)$ its convex hull. The problem of convex aggregation is to construct a procedure having a risk as close as possible to the minimal risk over $\mathrm{conv}(F)$. Consider the bounded regression model with respect to the squared risk denoted by $R(\cdot )$. If ${\hat{f}}_n^{ERM-C}$ denotes the empirical risk minimization procedure over $\mathrm{conv}(F)$, then we prove that for any $x>0$, with probability greater than $1-4\exp (-x)$, \[R({\widehat{f}}_n^{\mathit{ERM-C}})\leq\min_{f\in \operatorname {conv}(F)}R(f)+c_0\max \biggl(ψ_n^{(C)}(M),\frac{x}{n}\biggr),\] where $c_0>0$ is an absolute constant and ${\psi }_n^{(C)}(M)$ is the optimal rate of convex aggregation defined in (In Computational Learning Theory and Kernel Machines (COLT-2003) (2003) 303-313 Springer) by ${\psi }_n^{(C)}(M)=M/n$ when $M\le \sqrt{n}$ and ${\psi }_n^{(C)}(M)=\sqrt{\log (\mathrm{e}M/\sqrt{n})/n}$ when $M>\sqrt{n}$.

Published in at http://dx.doi.org/10.3150/12-BEJ447 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (5)

• Boosting Algorithms: Regularization, Prediction and Model Fitting
• Concentration around the mean for maxima of empirical processes
• Aggregation for Gaussian regression
• Fast learning rates in statistical inference through aggregation
• Sharper lower bounds on the performance of the empirical risk minimization algorithm

Cited by in corpus (5)

• Performance of empirical risk minimization in linear aggregation
• Optimal bounds for aggregation of affine estimators
• Optimal exponential bounds for aggregation of density estimators
• An adaptive multiclass nearest neighbor classifier
• Accelerated Nonnegative Tensor Completion via Integer Programming