On the Variance, Admissibility, and Stability of Empirical Risk
  Minimization
Gil Kur Eli Putterman Alexander Rakhlin
It is well known that Empirical Risk Minimization (ERM) with squared loss may
attain minimax suboptimal error rates (Birg\'e and Massart, 1993). The key
message of this paper is that, under mild assumptions, the suboptimality of ERM
must be due to large bias rather than variance. More precisely, in the
bias-variance decomposition of the squared error of the ERM, the variance term
necessarily enjoys the minimax rate. In the case of fixed design, we provide an
elementary proof of this fact using the probabilistic method. Then, we prove
this result for various models in the random design setting. In addition, we
provide a simple proof of Chatterjee's admissibility theorem (Chatterjee, 2014,
Theorem 1.4), which states that ERM cannot be ruled out as an optimal method,
in the fixed design setting, and extend this result to the random design
setting. We also show that our estimates imply stability of ERM, complementing
the main result of Caponnetto and Rakhlin (2006) for non-Donsker classes.
Finally, we show that for non-Donsker classes, there are functions close to the
ERM, yet far from being almost-minimizers of the empirical loss, highlighting
the somewhat irregular nature of the loss landscape.