Empirical Entropy, Minimax Regret and Minimax Risk

We consider the random design regression with square loss. We propose a method that aggregates empirical minimizers (ERM) over appropriately chosen random subsets and reduces to ERM in the extreme case, and we establish exact oracle inequalities for its risk. We show that, under the ∈−p growth of the empirical ∈-entropy, the excess risk of the proposed method attains the rate n−2/2+p for p ∈ (0, 2] and n−1/p for p > 2. We provide lower bounds to show that these rates are optimal. Furthermore, for p ∈ (0, 2], the excess risk rate matches the behavior of the minimax risk of function estimation in regression problems under the well-specified model. This yields a surprising conclusion that the rates of statistical estimation in well-specified models (minimax risk) and in misspecified models (minimax regret) are equivalent in the regime p ∈ (0, 2]. In other words, for p ∈ (0, 2] the problem of statistical learning enjoys the same minim! ax rate as the problem of statistical estimation. Our oracle inequalities also imply the log(n)/n rates for Vapnik-Chervonenkis type classes without the typical convexity assumption on the class; we show that these rates are optimal. Finally, for a slightly modified method, we derive a bound on the excess risk of s-sparse convex aggregation improving that of Lounici and we show that it yields the optimal rate.