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