On Bayes Risk Lower Bounds

By X. Chen, Adityanand Guntuboyina, Yuchen Zhang. 2014

51 citations recorded by the source corpus.

This paper provides a general technique for lower bounding the Bayes risk of statistical estimation, applicable to arbitrary loss functions and arbitrary prior distributions. A lower bound on the Bayes risk not only serves as a lower bound on the minimax risk, but also characterizes the fundamental limit of any estimator given the prior knowledge. Our bounds are based on the notion of $f$-informativity, which is a function of the underlying class of probability measures and the prior. Application of our bounds requires upper bounds on the $f$-informativity, thus we derive new upper bounds on $f$-informativity which often lead to tight Bayes risk lower bounds. Our technique leads to generalizations of a variety of classical minimax bounds (e.g., generalized Fano's inequality). Our Bayes risk lower bounds can be directly applied to several concrete estimation problems, including Gaussian location models, generalized linear models, and principal component analysis for spiked covariance models. To further demonstrate the applications of our Bayes risk lower bounds to machine learning problems, we present two new theoretical results: (1) a precise characterization of the minimax risk of learning spherical Gaussian mixture models under the smoothed analysis framework, and (2) lower bounds for the Bayes risk under a natural prior for both the prediction and estimation errors for high-dimensional sparse linear regression under an improper learning setting.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Information-Theoretic Lower Bounds on Bayes Risk in Decentralized Estimation (2016, background): “[8], and generalizes the result of Duchi and Wainwright [15].”
Reward-Free Exploration for Reinforcement Learning (2020, methodology): “Equation (11) in Chen et al. [2016]. We will apply Fano’s inequality of each a ∈ [A].”
$f$ -Divergence Inequalities (2015, background): “(6)] (see also [16]), which in turn generalizes the special case for α = (1)2 obtained simultaneously and independently by Birgé and Massart [11, eq.”
Provable Meta-Learning of Linear Representations (2020, background): “Even in this setting, a gap remains with respect to condition number/eigenvalue factors of the data design matrix X, between existing upper and lower bounds (see Chen et al. (2016, Section 7), Raskutti et al. (2011, Theorem 1, Theorem 2) and Zhang et al. (2014) for example).”