Performance of empirical risk minimization in linear aggregation

Abstract

We study conditions under which, given a dictionary $F=\{f_1,\dots ,f_M\}$ and an i.i.d. sample $(X_i,Y_i{)}_{i=1}^N$, the empirical minimizer in $\mathrm{span}(F)$ relative to the squared loss, satisfies that with high probability \[R\bigl(\tilde{f}^{\mathrm{ERM}}\bigr)\leq\inf_{f\in\operatorname {span}(F)}R(f)+r_N(M),\] where $R(\cdot )$ is the squared risk and $r_N(M)$ is of the order of $M/N$. Among other results, we prove that a uniform small-ball estimate for functions in $\mathrm{span}(F)$ is enough to achieve that goal when the noise is independent of the design.

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

References in corpus (4)

• Aggregation for Gaussian regression
• Empirical risk minimization is optimal for the convex aggregation problem
• On the optimality of the aggregate with exponential weights for low temperatures
• Sharper lower bounds on the performance of the empirical risk minimization algorithm

Cited by in corpus (3)

• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• Performance of Empirical Risk Minimization for Linear Regression with Dependent Data
• An elementary analysis of ridge regression with random design