# Empirical entropy, minimax regret and minimax risk

arXiv: https://arxiv.org/abs/1308.1147 · HTML: https://mlsanity.com/paper/1308.1147/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2013.

## Built on by (most cited first, 21 of 21)

- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior](https://mlsanity.com/paper/2307.14619/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits](https://mlsanity.com/paper/2602.09456/) (2026)
- [On the Minimal Error of Empirical Risk Minimization](https://mlsanity.com/paper/2102.12066/) (2021)
- [On the Variance, Admissibility, and Stability of Empirical Risk Minimization](https://mlsanity.com/paper/2305.18508/) (2023)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [An Efficient Minimax Optimal Estimator For Multivariate Convex Regression](https://mlsanity.com/paper/2205.03368/) (2022)
- [Star algorithm for NN ensembling](https://mlsanity.com/paper/2206.00255/) (2022)
- [Active Learning via Regression Beyond Realizability](https://mlsanity.com/paper/2506.00316/) (2025)
- [Latent Variable Modeling for Robust Causal Effect Estimation](https://mlsanity.com/paper/2508.20259/) (2025)
- [Fast Best-in-Class Regret for Contextual Bandits](https://mlsanity.com/paper/2510.15483/) (2025)
- [High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch](https://mlsanity.com/paper/2602.11747/) (2026)

## Abstract (arXiv)

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 varepsilon-p growth of the empirical varepsilon-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 where n is the sample size. 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 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 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 vlog(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.