# Sharp regret bounds for empirical Bayes and compound decision problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 65 references that are in the map.
- First posted on arXiv 8 Sep 2021.

## Builds on (most cited first, 1 of 1)

- [Two Modeling Strategies for Empirical Bayes Estimation](https://mlsanity.com/paper/1409.2677/) (2014)

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

- [Optimal score estimation via empirical Bayes smoothing](https://mlsanity.com/paper/2402.07747/) (2024)
- [From optimal score matching to optimal sampling](https://mlsanity.com/paper/2409.07032/) (2024)
- [Solving Empirical Bayes via Transformers](https://mlsanity.com/paper/2502.09844/) (2025)
- [A Mean Field Approach to Empirical Bayes Estimation in High-dimensional Linear Regression](https://mlsanity.com/paper/2309.16843/) (2023)
- [On the best approximation by finite Gaussian mixtures](https://mlsanity.com/paper/2404.08913/) (2024)
- [Sharp Inequalities between Total Variation and Hellinger Distances for Gaussian Mixtures](https://mlsanity.com/paper/2602.03202/) (2026)
- [Universal priors: solving empirical Bayes via Bayesian inference and pretraining](https://mlsanity.com/paper/2602.15136/) (2026)
- [Quasi-Bayes empirical Bayes: a sequential approach to the Poisson compound decision problem](https://mlsanity.com/paper/2411.07651/) (2024)
- [Poisson empirical Bayes estimation of sums of random variables via minimum-distance methods](https://mlsanity.com/paper/2610.07190/) (2026)

## Abstract (arXiv)

We consider the classical problems of estimating the mean of an n-dimensional normally (with identity covariance matrix) or Poisson distributed vector under the squared loss. In a Bayesian setting the optimal estimator is given by the prior-dependent conditional mean. In a frequentist setting various shrinkage methods were developed over the last century. The framework of empirical Bayes, put forth by Robbins (1956), combines Bayesian and frequentist mindsets by postulating that the parameters are independent but with an unknown prior and aims to use a fully data-driven estimator to compete with the Bayesian oracle that knows the true prior. The central figure of merit is the regret, namely, the total excess risk over the Bayes risk in the worst case (over the priors). Although this paradigm was introduced more than 60 years ago, little is known about the asymptotic scaling of the optimal regret in the nonparametric setting. We show that for the Poisson model with compactly supported and subexponential priors, the optimal regret scales as Theta((fraclog nloglog n)2) and Theta(log3 n), respectively, both attained by the original estimator of Robbins. For the normal mean model, the regret is shown to be at least Omega((fraclog nloglog n)2) and Omega(log2 n) for compactly supported and subgaussian priors, respectively, the former of which resolves the conjecture of Singh (1979) on the impossibility of achieving bounded regret; before this work, the best regret lower bound was Omega(1). In addition to the empirical Bayes setting, these results are shown to hold in the compound setting where the parameters are deterministic. As a side application, the construction in this paper also leads to improved or new lower bounds for density estimation of Gaussian and Poisson mixtures.