Empirical entropy, minimax regret and minimax risk

Abstract

We consider the random design regression model 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 sharp oracle inequalities for its risk. We show that, under the ${\epsilon }^{-p}$ growth of the empirical $\epsilon$-entropy, the excess risk of the proposed method attains the rate $n^{-2/(2+p)}$ for $p\in (0,2)$ and $n^{-1/p}$ for $p>2$ where $n$ is the sample size. Furthermore, for $p\in (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 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\in (0,2)$. In other words, for $p\in (0,2)$ the problem of statistical learning enjoys the same minimax rate as the problem of statistical estimation. On the contrary, for $p>2$ we show that the rates of the minimax regret are, in general, slower than for the minimax risk. Our oracle inequalities also imply the $v\log (n/v)/n$ rates for Vapnik-Chervonenkis type classes of dimension $v$ without the usual 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 [Math. Methods Statist. 16 (2007) 246-259] and providing the optimal rate.

Published at http://dx.doi.org/10.3150/14-BEJ679 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 (2)

• Deviation optimal learning using greedy Q-aggregation
• Empirical risk minimization is optimal for the convex aggregation problem

Cited by in corpus (25)

• Loss minimization and parameter estimation with heavy tails
• Does data interpolation contradict statistical optimality?
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• On Bayes Risk Lower Bounds
• Learning with Square Loss: Localization through Offset Rademacher Complexity
• Minimax Estimation of Conditional Moment Models
• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Distribution-Free Robust Linear Regression
• Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions
• Sharp oracle bounds for monotone and convex regression through aggregation
• Generative Modeling with Denoising Auto-Encoders and Langevin Sampling
• A Chaining Algorithm for Online Nonparametric Regression
• Online Nonparametric Regression with General Loss Functions
• Bayesian fractional posteriors
• A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Optimal learning via local entropies and sample compression
• Minimax Rates for Conditional Density Estimation via Empirical Entropy
• An optimal unrestricted learning procedure
• Efficient online learning with kernels for adversarial large scale problems
• On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
• Semi-Parametric Efficient Policy Learning with Continuous Actions
• Optimal oracle inequalities for solving projected fixed-point equations
• Localization, Convexity, and Star Aggregation
• On the Minimal Error of Empirical Risk Minimization