Sharp regret bounds for empirical Bayes and compound decision problems

Yury Polyanskiy, Yihong Wu

Title: Sharp Regret Bounds for Empirical Bayes and Compound Decision Problems
Authors: Yury Polyanskiy and Yihong Wu

Abstract: This paper addresses the fundamental limits of "borrowing strength" in statistical estimation, a core concept in Empirical Bayes (EB) and compound decision problems. By establishing the first sharp asymptotic bounds for regret in nonparametric EB settings for Gaussian and Poisson models, the authors resolve a long-standing conjecture from 1979. The study proves that a data-driven estimator cannot perfectly match a Bayesian oracle, identifying a fundamental logarithmic "price" for unknown priors.

Introduction

Empirical Bayes (EB), introduced by Herbert Robbins in 1956, provides a framework for improving group-level estimation by leveraging data across multiple groups to "learn" an underlying prior distribution. While widely used in fields ranging from genomics to sports statistics, the exact theoretical limits of EB—specifically the rate at which the "regret" (excess risk over a Bayesian oracle) vanishes—remained an open question for decades.

This research by Yury Polyanskiy and Yihong Wu provides a definitive answer to this question. They bridge a significant gap in theoretical statistics by determining the optimal rates of regret for two of the most fundamental probabilistic frameworks: the Normal (Gaussian) mean model and the Poisson model.

Problem Formulation: The Cost of Learning

The central metric in this study is regret. In a Bayesian setting, an "oracle" knows the true prior distribution of parameters and can achieve minimum risk. In the EB setting, the prior is unknown and must be estimated from the data. Regret measures the performance gap between a data-driven estimator and this Bayesian oracle.

A key focus of the paper is Singh’s Conjecture (1979), which posited that for exponential families, it is impossible to achieve "bounded regret" (regret that remains constant as the sample size $n$ increases) even with well-behaved, compactly supported priors. This paper provides the formal proof for this conjecture, establishing that there is always a non-vanishing cost to not knowing the prior.

Methodology: A General Program for Lower Bounds

The authors developed a sophisticated mathematical framework to prove lower bounds on regret, utilizing several advanced tools:

  • Operator Theory: The problem of estimating the Bayes rule is reframed as estimating specific integral operators ($K$ and $K_1$) derived from posterior densities.
  • Assouad’s Lemma: To establish minimax lower bounds, the authors constructed large sets of "nearby" prior distributions. These distributions are designed to be statistically indistinguishable to any algorithm while leading to significantly different optimal estimation rules.
  • Orthogonal Bases: The construction of these difficult priors relied on specific mathematical functions, such as Hermite functions for Gaussian models and generalized Laguerre polynomials for Poisson models. These functions allow for perturbations in the prior that are "invisible" to the observer but impactful on the regret.

Key Results and Insights

The paper establishes "sharp" bounds, where the theoretical lower limit matches the performance of the best known estimators.

Poisson Model

The results for the Poisson model are particularly striking. The authors found that the optimal regret scales as:

  • $\Theta\left(\left( \frac{\log n}{\log \log n} \right)^2\right)$ for compactly supported priors.
  • $\Theta(\log^3 n)$ for subexponential priors.

Notably, they discovered that the original estimator proposed by Robbins in 1956 is rate-optimal for the Poisson model, achieving the best possible scaling.

Gaussian Model

For the Gaussian mean model, the authors established a lower bound of:

  • $\Omega\left(\left( \frac{\log n}{\log \log n} \right)^2\right)$ for compact support.
  • $\Omega(\log^2 n)$ for subgaussian priors.

High-Order Information

A core insight is that minimizing regret is fundamentally more difficult than simple density estimation. Regret minimization requires "high-order" information, such as derivatives of the mixture density. Since derivatives are highly sensitive to noise, this requirement imposes a strict physical limit on the speed at which regret can decrease.

Conclusion and Future Directions

This work provides a rigorous foundation for understanding the limits of empirical Bayes methods. While it resolves Singh's conjecture and provides sharp bounds for the Poisson model, some gaps remain. For the Gaussian model, a small discrepancy exists between the new lower bound ($\Omega(\log^2 n)$) and the best known upper bound ($O(\log^5 n)$). Future research will likely focus on closing this gap and extending the "general program" to more complex exponential families beyond the Gaussian and Poisson cases.

Summary updated

Abstract

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 $Θ((\frac{\log n}{\log\log n})^2)$ and $Θ(\log^3 n)$, respectively, both attained by the original estimator of Robbins. For the normal mean model, the regret is shown to be at least $Ω((\frac{\log n}{\log\log n})^2)$ and $Ω(\log^2 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 $Ω(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.
BibTeX
@misc{polyanskiy2021sharp,
  author = {Yury Polyanskiy and Yihong Wu},
  title = {{Sharp regret bounds for empirical Bayes and compound decision problems}},
  year = {2021},
  eprint = {2109.03943},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.03943},
}
Figure