Title: On Concentration for (Regularized) Empirical Risk Minimization

Author(s): Sara van de Geer and Martin J. Wainwright
Issue: Volume 79 Series A Part 2 Year 2017
Pages: 159 -- 200
Rates of convergence for empirical risk minimizers have been well studied in the literature. In this paper, we aim to provide a complementary set of results, in particular by showing that after normalization, the risk of the empirical minimizer concentrates on a single point. Such results have been established by Chatterjee (The Annals of Statistics, 42(6):2340–2381 2014) for constrained estimators in the normal sequence model. We first generalize and sharpen this result to regularized least squares with convex penalties, making use of a “direct” argument based on Borell’s theorem. We then study generalizations to other loss functions, including the negative log-likelihood for exponential families combined with a strictly convex regularization penalty. The results in this general setting are based on more “indirect” arguments as well as on concentration inequalities for maxima of empirical processes.
AMS (2000) subject classification. Primary: 62E20; Secondary 60F99.
Keywords and phrases: Concentration, Density estimation, Empirical process, Empirical risk minimization, Normal sequence model, Penalized least squares.