text:
\section{Introduction}
Consider a standard decision-theoretic  setting where $\Theta$  and $\mathcal{A}$ are the parameter and action spaces respectively and $L(\theta, a): \Theta \times \mathcal{A} \mapsto [0, \infty)$  is a non-negative loss function. We observe data $X$ taking values in a sample space ${\mathcal{X}}$. The distribution of $X$ depends on the unknown parameter $\theta$ and is denoted by $P_{\theta}$ ($P_{\theta}$ is a probability measure on ${\mathcal{X}}$). The class of probability measures $\{P_{\theta} : \theta \in \Theta\}$ is denoted by ${\mathcal{P}}$.  A decision rule is a measurable mapping from ${\mathcal{X}}$ to ${\mathcal{A}}$. The risk of a decision rule ${\mathfrak{d}}$ is defined by ${\mathbb E}_{\theta} L(\theta, {\mathfrak{d}}(X))$, where ${\mathbb E}_{\theta}$ denotes expectation taken under the assumption that $X$ is distributed according to $P_{\theta}$. For a given proper prior $w$ (i.e., $w$ is a probability  measure on $\Theta$), the Bayes risk with respect to $w$ is  defined by
\begin{equation}
  R_{\rm Bayes}(w, L; \Theta) := \inf_{{\mathfrak{d}}} \int_{\Theta} {\mathbb E}_{\theta} L(\theta, {\mathfrak{d}}(X)) w(\mathrm{d}\theta)
 \label{eq:R_Bayes}
\end{equation}
where the infimum is over all decision rules ${\mathfrak{d}}$. When $L$ and $\Theta$ are clear from the context, we simply denote the Bayes risk by $R_{\rm Bayes}(w)$. When the prior $w$ is also clear, the notation is further simplified to $R$.

The goal of this paper is to prove new lower bounds for $R_{\rm Bayes}(w, L; \Theta)$ for any given prior $w$ and loss function $L$. Bayes risk lower bounds are useful for three main reasons: (a) they provide an idea of the difficulty of the decision theoretic problem under a specific prior $w$, (b) they automatically provide lower bounds for the minimax risk:
\begin{eqnarray}
  R_{\rm minimax}(L; \Theta):= \inf_{{\mathfrak{d}}} \sup_{\theta \in \Theta} {\mathbb E}_{\theta} L(\theta, {\mathfrak{d}}(X)),
  \label{eq:R_minimax}
\end{eqnarray}
which is an important quantity in statistical decision theory, and (c) they are useful in proving admissibility results.

In order to give the reader a flavor of the kind of results proved in this paper, let us consider Fano's classical inequality \citep{Han:94,Cover:IT:06, yu1997assouad}  which is one of the most widely used Bayes risk lower bounds in statistics and  information theory. The standard version of Fano's inequality applies to the case when $\Theta = {\mathcal{A}} = \{1, \dots, N\}$ for some positive integer $N$ with the indicator loss  $L(\theta, a) := \mathbb{I}\{\theta \neq a\}$ ($\mathbb{I}$ stands for the zero-one valued indicator function) and the prior $w$ being the discrete uniform distribution on $\Theta$. In this setting, Fano's inequality states that
\begin{equation}\label{eq:classcial_Fano}
  R_{\rm Bayes}(w) \geq 1 - \frac{I(w, \mathcal{P}) + \log 2}{\log N}
\end{equation}
where $I(w, \mathcal{P})$ is the mutual information between the random variables $\theta \sim w$ and $X$ with $X \vert \theta \sim P_{\theta}$ (note that this mutual information only depends on $w$ and ${\mathcal{P}}=\{P_{\theta} : \theta \in \Theta\}$ which is why we denote it by $I(w, {\mathcal{P}})$). Fano's inequality implies  that when $I(w; \mathcal{P})$ is large i.e., when the information that $X$ has about $\theta$ is large, then the risk of estimation is small and vice versa.

A natural question regarding Fano's inequality, which does not seem to have been asked until very recently, is the following: does there exist an analogue of \eqref{eq:classcial_Fano} when $w$ is not necessarily the uniform prior and/or when $\Theta$ and ${\mathcal{A}}$ are arbitrary sets, and/or when the loss function is not necessarily $\mathbb{I}\{\theta \neq a\}$? An interesting result in this direction is the following inequality which has been recently proved by \cite{Duchi:Fano} who termed it the continuum Fano inequality. This inequality applies to the case when $\Theta = {\mathcal{A}}$ is a subset of Euclidean space with finite strictly positive Lebesgue measure, $L(\theta, a) = \mathbb{I}\{\|\theta - a\|_2 \geq \epsilon\}$ for a fixed $\epsilon > 0$ ($\|\cdot\|_2$ is the  usual Euclidean metric) and the prior $w$ being the uniform probability measure (i.e., normalized Lebesgue measure) on $\Theta$. In this setting, \cite{Duchi:Fano} proved that
\begin{equation}\label{cf}
  R_{\rm Bayes}(w) \geq 1 + \frac{I(w, \mathcal{P}) + \log 2}{\log \left( \sup_{a \in {\mathcal{A}}}
      w\{\theta \in \Theta : \|\theta - a\|_2 < \epsilon\}  \right)}.
\end{equation}

It turns out that there is a very clean connection between inequalities \eqref{eq:classcial_Fano} and \eqref{cf}. Indeed, both these inequalities are special instances of the  following inequality:
\begin{equation}\label{intro_gf}
  R_{\rm Bayes}(w) \geq 1 + \frac{I(w, \mathcal{P}) + \log 2}{\log \left( \sup_{a \in {\mathcal{A}}}
      w\{\theta \in \Theta : L(\theta, a) = 0\} \right)}
\end{equation}
Indeed, the term $w\{\theta \in \Theta : L(\theta, a) = 0\}$ equal to  $1/N$  in the setting of \eqref{eq:classcial_Fano} and it is equal to $w\{\theta \in \Theta: \|\theta - a\|_2 < \epsilon\}$ in the setting of \eqref{cf}.

Since both \eqref{eq:classcial_Fano} and \eqref{cf} are special instances of \eqref{intro_gf}, one might reasonably conjecture that inequality \eqref{intro_gf} might hold more generally. In Section \ref{sec:Bayes_01}, we give an affirmative answer by proving that inequality \eqref{intro_gf} holds for any zero-one valued loss function $L$ and any prior $w$. No assumptions on $\Theta$, ${\mathcal{A}}$ and $w$ are needed. We refer to this result as \emph{generalized Fano's inequality}.  Our proof of \eqref{intro_gf} is quite succinct and is based on the data processing inequality \citep{Cover:IT:06,Liese12} for Kullback-Leibler (KL) divergence.

The data processing inequality is not only available for the KL divergence. It can be generalized to any divergence belonging to a general family known as $f$-divergences \citep{Csiszar:63, AliSilvey:66}. This family includes the KL divergence, chi-squared divergence, squared Hellinger distance, total variation distance and power divergences as special cases. For every $f$-divergence, one can define a quantity called $f$-informativity \citep{Csiszar:72} which plays the same role as the mutual information for KL divergence. The precise definitions of $f$-divergences and $f$-informativities are given in Section \ref{sec:pre}. Utilizing the data processing inequality for $f$-divergence, we prove  general Bayes  risk lower bounds which hold for every zero-one valued loss $L$ and for arbitrary $\Theta$, ${\mathcal{A}}$ and $w$ (Theorem \ref{man}). The generalized Fano's inequality~\eqref{intro_gf} is a special case by choosing the $f$-divergence to be KL. The proposed Bayes risk lower bounds  can also be specialized to other $f$-divergences and have a variety of interesting connections to existing lower bounds in the literature such as Le Cam's inequality,  Assouad's lemma (see Theorem 2.12 in \cite{Tsybakov:nonpara}), Birg\'{e}-Gushchin inequality \citep{Gushchin:03, Birge:ineq}, and many minimax lower bounds in \cite{Tsybakov:nonpara} (specifically, Theorem 2.4,   2.5,  2.6 and   2.15 in \cite{Tsybakov:nonpara}). These results are provided in Section \ref{sec:Bayes_01}.  In Section \ref{sec:compare}, we also provide some qualitative comparisons among the derived Bayes risk lower bounds for different choices of $f$-divergence. We argue that Hellinger distance leads to inequalities that are qualitatively quite different (and less useful in certain applications) from the inequalities corresponding to KL and chi-squared  divergences. We also reason that our lower bounds involving KL/chi-squared are useful even in situations where all pairwise  KL/chi-squared divergences are infinite.

In Section \ref{sec:Bayes_general}, we deal with arbitrary nonnegative valued loss functions $L$ which are not necessarily zero-one valued. Basically, we use the standard method of lower bounding the general loss function $L$ by a zero-one valued function and then use our results from Section \ref{sec:Bayes_01} for lower bounding the Bayes risk.
This technique, in conjunction with the generalized Fano's inequality, gives the following lower bound (proved in Corollary \ref{cor:bwl})
\begin{equation}\label{eq:intro_I_bayes_KL}
R_{\rm Bayes}(w, L; \Theta)  \geq \frac{1}{2} \sup \left\{t> 0 : \sup_{a \in {\mathcal{A}}} w \{\theta : L(\theta, a) <t \} \leq \frac{1}{4} e^{-2 I(w, \mathcal{P})} \right\}.
\end{equation}
This inequality is very general in that it is true for any $\Theta$, ${\mathcal{A}}$, any given nonnegative  loss $L$ and prior $w$. In fact, using our $f$-divergence inequalities from Section \ref{sec:Bayes_01}, we prove, in Theorem \ref{bwl}, the following general lower bound for $R_{\rm Bayes}(w, L; \Theta)$ which holds for any $f$-divergence:
\begin{equation}\label{ggfe}
\frac{1}{2} \sup \left\{t > 0 : \sup_{a \in {\mathcal{A}}} w \{\theta : L(\theta, a) < t\} < 1 - u_f(I_f(w, \mathcal{P}))\right\}
\end{equation}
where $I_f(w, \mathcal{P})$ represents the $f$-informativity and $u_f(\cdot)$ is a non-decreasing $[0, 1]$-valued function that depends only on $f$. This function $u_f(\cdot)$ (see its definition from \eqref{ufi}) can be explicitly computed for many $f$-divergences of interest, which gives useful lower bounds in terms of $f$-informativity. For example, for the case of KL divergence and chi-squared divergence, inequality \eqref{ggfe} gives the lower bound in \eqref{eq:intro_I_bayes_KL} and the following inequality respectively,
\begin{equation}\label{eq:intro_I_bayes_chi}
R_{\rm Bayes}(w, L; \Theta)  \geq \frac{1}{2} \sup \left\{t> 0 : \sup_{a \in {\mathcal{A}}} w \{\theta : L(\theta, a) < t\} \leq \frac{1}{4(1 + I_{\chi^2}(w, \mathcal{P}))} \right\}.
\end{equation}
where $I_{\chi^2}(w, \mathcal{P})$ is the chi-squared informativity.

Intuitively, inequality \eqref{ggfe} shows that the Bayes risk is lower bounded by half of the largest possible $t$ such that the maximum prior mass of any $t$-radius ``ball" ($w \{\theta : L(\theta, a) < t \}$) is less than some function of $f$-informativity. To apply \eqref{ggfe},  one needs to obtain upper bounds on the following two quantities:
 \begin{enumerate}
\item The ``small ball probability" $\sup_{a \in {\mathcal{A}}} w \{\theta : L(\theta, a) < t \}$, which does not depend  of the family of probability measures ${\mathcal{P}}$.
\item The $f$-informativity $I_f(w, \mathcal{P})$, which does not depend on the loss function $L$.
\end{enumerate}
We note that a nice feature of \eqref{ggfe} is that $L$ and ${\mathcal{P}}$ play separately roles. One may first obtain an upper bound $I_f^{\rm up}$ for the $f$-informativity $I_f(w, \mathcal{P})$, then choose $t$ so that the small ball probability $w \{\theta : L(\theta, a) < t \}$ can be bounded from above by $1 - u_f(I_f^{\rm up})$. The Bayes risk will be bounded from below by $t/2$.

We do not have a general guideline for bounding the small ball probability. It needs to be dealt with case by case based on the prior and the loss function.  But for upper bounding the $f$-informativity, we offer a general recipe in Section \ref{sec:upper_f_informativity} for a  subclass of divergences of interest (power divergences for $\alpha \notin [0, 1)$), which covers the chi-squared divergence as one of the most important divergences in our applications.  These bounds generalize results of \cite{haussler1997} and \cite{Yang:Barron:99} for mutual information to $f$-informativities involving power divergences. As an illustration of our techniques (inequality \eqref{ggfe} combined with the $f$-informativity upper bounds), we apply them to a concrete estimation problem in Section \ref{sec:upper_f_informativity} with more examples in the appendix.

A nontrivial application of our Bayes risk lower bounds to a recent admissibility result of  \cite{Sourav14LS} is presented in Section \ref{sec:admis}. The result deals with convex-constrained least squares estimators in the Gaussian sequence model.  Consider the problem of estimating a vector $\theta \in {\mathbb R}^n$ in squared Euclidean loss $L(\theta, a)=\|\theta-a\|_2^2$ from a single $n$-dimensional observation $X \sim N(\theta, I_n)$, i.e., $X$ is Gaussian with mean $\theta$ and identity covariance. The true parameter  $\theta$ is assumed to be in a known closed  convex set $\Theta \subseteq {\mathbb R}^n$. This estimation problem includes many standard problems such as isotonic regression, convex regression, constrained Lasso  etc. as special cases.

The most commonly used estimator in this setting is the Least Squares Estimator (LSE) defined as $\widehat{\theta}(X) := \mathop{\rm argmin}_{t \in \Theta} \|X - t\|_2^2$. \citet{Sourav14LS} posed the following fundamental question about the LSE: does $\widehat{\theta}(X)$ satisfy a general optimality property that holds for \textit{every} closed convex set $\Theta$? This is a non-trivial question; the obvious guesses might be admissibility and minimaxity; but the LSE does not satisfy either of these for every $\Theta$. \citet{Sourav14LS}  answered this question in the affirmative by proving that $\widehat{\theta}(X)$ is \textit{approximately admissible} for every $\Theta$. The precise statement of Chatterjee's theorem is described below. Let us say that, for a constant $C > 0$, an estimator ${\mathfrak{d}}(X)$ is \emph{$C$-admissible} if for every other estimator $\widetilde{{\mathfrak{d}}}(X)$, there exists $\theta' \in \Theta$ such that
\begin{equation}\label{cad}
  C {\mathbb E}_{\theta'} \|{\mathfrak{d}}(X) - \theta' \|_2^2 \leq {\mathbb E}_{\theta'} \|\widetilde{{\mathfrak{d}}}(X) - \theta'\|_2^2.
\end{equation}
Essentially this definition means that it is impossible for any estimator to dominate ${\mathfrak{d}}(X)$ uniformly over $\Theta$ by more than a constant. \cite{Sourav14LS} proved that there exists a universal constant $0 < C \leq 1$ such that for every $n \geq 1$ and  closed  convex subset $\Theta \subseteq {\mathbb R}^n$, the LSE $\widehat{\theta}(X)$ is  $C$-admissible.
Remarkable features of this result are that it is true for every $\Theta$ and that the constant $C$  does not depend on $n$ or $\Theta$.

This is a rather difficult result (in \citeauthor{Sourav14LS}'s own words, ``from a purely mathematical point of view, this is the deepest result of this paper'') and the original proof in \citet{Sourav14LS} is quite complex. In Section \ref{sec:admis}, we show how this proof can be considerably simplified with the use of inequality \eqref{eq:intro_I_bayes_chi}. An outline of our idea is as follows. Analogous to the notion of $C$-admissibility, we can define a notion of $C$-Bayes as follows. For $C > 0$ and a proper prior $w$ over $\Theta$, we say that an estimator ${\mathfrak{d}}(X)$ is $C$-Bayes with respect to $w$ if
\begin{equation}\label{eq:C_Bayes}
  C \int_{\Theta} {\mathbb E}_{\theta} \|{\mathfrak{d}}(X) - \theta \|_2^2 w(\mathrm{d}\theta) \leq R_{\rm Bayes}(w):=  \inf_{\tilde{{\mathfrak{d}}}} \int_{\Theta} {\mathbb E}_{\theta} \|\tilde{{\mathfrak{d}}}(X) - \theta \|_2^2  w(\mathrm{d}\theta)
\end{equation}
Based on the simple observation that $C$-Bayes for any  prior $w$ implies $C$-admissibility, it is enough to construct a prior $w$ such that the LSE  $\widehat{\theta}(X)$ is $C$-Bayes with respect to $w$ (for some universal constant $C$). In order to prove that $\widehat{\theta}(X)$ is $C$-Bayes with respect to $w$, it is clear that we need to:
\begin{enumerate}
\item bound $\int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2w(\mathrm{d}\theta)$ from  above,
\item bound $R_{\rm Bayes}(w)$ from below
\end{enumerate}
and make sure that the two bounds differ only by the multiplicative factor $C$. Bayes risk lower bounds established in this paper (specifically \eqref{eq:intro_I_bayes_chi}) are directly applicable for carrying out the second step above. In contrast, \citet{Sourav14LS} used a bare hands approach for the second step via ``a sequence of relatively complicated technical steps involving concentration inequalities and second moment lower bounds''.
As we shall demonstrate in Section \ref{sec:admis}, the prior $w$ proposed by \citet{Sourav14LS} is a continuous non-uniform prior on $\Theta$, so that existing Bayes risk lower bounds cannot be directly applied.

Before finishing this introduction section, we briefly describe related work on Bayes risk lower bounds. There are a few results dealing with special cases of finite dimensional estimation problems under (weighted/truncated) quadratic losses. The first results of this kind were established by \cite{VanTree:68}, and ~\cite{Borovkov:80} with extensions by~\cite{Brown:90, Brown:93, gill95,Sato:96, Takada:99}. A few additional papers dealt with even more specialized problems e.g., Gaussian white noise model \citep{BrownLiu:93}, scale models \citep{Gajek:94} and estimating Gaussian variance \citep{Vidakovic:95}. Most of these results are based on the van Trees inequality (see \cite{gill95} and Theorem 2.13 in \cite{Tsybakov:nonpara}). Although the van Trees inequality usually leads to sharp constant in the Bayes risk lower bounds, it only applies to weighted quadratic loss functions (as its proof relies on Cauchy-Schwarz inequality) and requires the underlying Fisher information to be easily computable, which limits its applicability. There is also a vast body of literature on minimax lower bounds (see, e.g., \cite{Tsybakov:nonpara}) which can be viewed as Bayes risk lower bounds for certain priors. These priors are usually discrete and specially constructed so that the lower bounds do not apply to more general (continuous) priors. Another related area of work involves finding lower bounds on posterior contraction rates (see, e.g., \citet{Castillo08Lower}).

The rest of the paper is organized in the following way. In Section \ref{sec:pre}, we describe notations and review preliminaries such as $f$-divergences, $f$-informativity, data processing inequality, etc. Section \ref{sec:Bayes_01} deals with inequalities for zero-one valued loss functions. These inequalities have many connections to existing lower bound techniques. Section \ref{sec:Bayes_general} deals with arbitrary loss functions and we provide inequality \eqref{ggfe} and its special cases. Section \ref{sec:upper_f_informativity} presents upper bounds on the $f$-informativity for power divergences for $\alpha \notin [0, 1)$. Some examples are also given in this section. Finally, Section \ref{sec:admis} presents our simplified proof of Theorem \ref{jee}. Due to space constraints, we have relegated all the proofs and some additional examples and results to the .

\section{Preliminaries and notations}
\label{sec:pre}
We first review the notions of $f$-divergence~\citep{Csiszar:63,AliSilvey:66} and $f$-informativity~\citep{Csiszar:72}. Let ${\mathcal{C}}$ denote the class of all convex functions $f: (0, \infty) \rightarrow {\mathbb R}$ which satisfy $f(1) = 0$. Because of convexity, the limits $f(0) := \lim_{x \downarrow 0} f(x)$ and $f'(\infty) := \lim_{x \uparrow \infty} f(x)/x$  exist (even though they may be $+\infty$) for each $f \in {\mathcal{C}}$. Each function $f \in {\mathcal{C}}$  defines a divergence between probability measures which is referred to as $f$-divergence. For two probability measures $P$ and $Q$ on a sample space having densities  $p$ and $q$ with respect to a common measure $\mu$, the $f$-divergence $D_f(P||Q)$ between $P$ and $Q$ is defined as follows:
\begin{equation}\label{eq:df}
  D_f(P||Q) := \int f \left(\frac{p}{q} \right)q  \mathrm{d} \mu  + f'(\infty) P\{q = 0\}.
\end{equation}
We note that the convention $0\cdot \infty= 0$ is adopted here so that $f'(\infty) P\{q = 0\}=0$ when $f'(\infty)=\infty$ and $P\{q=0\}=0$. Note that $D_f(P\|Q) = +\infty$ when $f'(\infty) = +\infty$ and $P\{q = 0\} > 0$.  Also note that $f(1) =  0$ implies that $D_f(P \|Q) = 0$ when $P = Q$.

Certain divergences are commonly used because they can  be easily computed or bounded when $P$ and $Q$ are product measures. These divergences are the power divergences  corresponding to the functions $f_{\alpha}$ defined by
\begin{eqnarray*}
  f_\alpha(x) =\begin{cases}
    x^{\alpha}-1 & \text{for}  \quad \alpha \not \in [0,1];\\
    1- x^{\alpha} & \text{for}  \quad \alpha \in (0,1);\\
    x\log x & \text{for}  \quad \alpha=1; \\
    -\log x & \text{for}  \quad \alpha=0.\\
  \end{cases}
\end{eqnarray*}
Popular examples of power divergences include:

\textbf{1)} Kullback-Leibler (KL) divergence: $\alpha=1$, $D_{f_1}(P||Q)=\bigintssss p \log (p/q) \mathrm{d} \mu$ if $P$ is absolutely continuous with respect to $Q$ (and it is infinite if $P$ is not absolutely continuous with respect to $Q$).  Following the conventional notation, we denote the KL divergence by $D(P||Q)$ (instead of $D_{f_1}(P||Q)$).

\textbf{2)} Chi-squared divergence: $\alpha=2$, $D_{f_2}(P||Q)= \bigintssss (p^2/q)  \mathrm{d} \mu - 1$ if $P$ is absolutely continuous with respect to $Q$ (and it is infinite if $P$ is not absolutely continuous with respect to $Q$). We denote the chi-squared divergence by $\chi^2(P||Q)$ following the conventional notation.

\textbf{3)} When $\alpha=1/2$, one has $D_{f_{1/2}}(P||Q)=  1- \bigintssss \sqrt{p q}  \mathrm{d} \mu$ which is a half of the squared Hellinger distance. That is, $D_{f_{1/2}}(P||Q)=H^2(P ||Q)/2$, where $H^2(P||Q)= \bigintssss  (\sqrt{p}-\sqrt{q})^2  \mathrm{d} \mu$ is the squared Hellinger distance between $P$ and $Q$.

The total variation distance $\|P-Q\|_{TV}$ is another $f$-divergence (with $f(x) = |x - 1|/2$) but not a power divergence.

One of the most important properties of $f$-divergences is the ``data processing inequality" (\cite{Csiszar:72} and \citet[Theorem 3.1]{Liese12}) which states the   following: let ${\mathcal{X}}$ and $\mathcal{Y}$ be two measurable spaces and let $\Gamma: {\mathcal{X}} \rightarrow \mathcal{Y}$ be a measurable function. For every $f \in {\mathcal{C}}$ and every pair of probability measures $P$ and $Q$ on ${\mathcal{X}}$, we have
\begin{equation}
  \label{dpi}
D_f(P\Gamma^{-1} || Q \Gamma^{-1}) \leq D_f(P||Q),
\end{equation}
where $P\Gamma^{-1}$ and $Q \Gamma^{-1}$ denote the \emph{induced measures} of $\Gamma$ on $\mathcal{Y}$, i.e., for any measurable set $B$ on the space $\mathcal{Y}$, $P\Gamma^{-1}(B):=P(\Gamma^{-1}(B))$, $Q\Gamma^{-1}(B):=Q(\Gamma^{-1}(B))$ (see the definition of induced measure from Definition 2.2.1. in \cite{Athreya:06}).

Next, we introduce the notion of $f$-informativity~\citep{Csiszar:72}. Let $\mathcal{P}= \{P_{\theta}: \theta \in \Theta\}$ be a family of probability measures on a space $\mathcal{X}$ and $w$ be a probability measure on $\Theta$. For each $f \in {\mathcal{C}}$, the $f$-informativity, $I_f(w, {\mathcal{P}})$, is defined as
\begin{eqnarray}\label{eq:def_f_info}
  I_f(w, {\mathcal{P}})= \inf_{Q} \int D_f(P_{\theta}||Q) w(\mathrm{d} \theta),
\end{eqnarray}
where the infimum is taken over all possible probability measures $Q$ on $\mathcal{X}$. When $f(x)=x\log x$ (so that the corresponding $f$-divergence is the KL divergence), the $f$-informativity is equal to the mutual information and is denoted by $I(w, \mathcal{P})$. We denote the informativity corresponding to the power divergence $D_{f_\alpha}$ by $I_{f_{\alpha}}(w, {\mathcal{P}})$. For the special case $\alpha = 2$, we use the more suggestive notation $I_{\chi^2}(w, {\mathcal{P}})$. The informativity corresponding to the total variation distance will be denoted by $I_{TV}(w, {\mathcal{P}})$.

Additional notations and definitions are described as follows.
Recall the Bayes risk~\eqref{eq:R_Bayes} and the minimax risk~\eqref{eq:R_minimax}. When the loss function $L$ and parameter space $\Theta$ are clear from the context, we drop the dependence on $L$ and $\Theta$. When the prior $w$ is also clear from the context, we denote the Bayes risk by $R$ and the minimax risk by $R_{\rm minimax}$.
We need certain notation for covering numbers. For a given $f$-divergence  and a subset $S \subset \Theta$, let $M_f(\epsilon, S)$ denote any upper bound on the smallest number $M$ for which there exist probability measures $Q_1, \dots, Q_M$ that form an $\epsilon^2$-cover of $\{P_{\theta}, \theta \in S \}$ under the $f$-divergence i.e.,
\begin{equation}\label{redf}
  \sup_{\theta \in S} \min_{1 \leq j \leq M} D_f(P_{\theta} || Q_j) \leq \epsilon^2.
\end{equation}
We write the covering number as $M_{KL}(\epsilon, S)$ when $f(x) = x \log x$ and $M_{\chi^2}(\epsilon, S)$ when $f(x) = x^2 - 1$. We write $M_{\alpha}(\epsilon, S)$ when $f = f_{\alpha}$ for other $\alpha \in {\mathbb R}$. We note that $\log M_f(\epsilon, S)$ is an upper bound on the metric entropy. The quantity $M_f(\epsilon, S)$ can be infinite if $S$ is arbitrary.
For a vector $x=(x_1, \ldots, x_d)$ and a real number $p \geq 1$, denote by $\|x\|_p$ the $\ell_p$-norm of $x$. In particular, $\|x\|_2$ denotes the Euclidean norm of $x$.
$\mathbb{I}(A)$ denotes the indicator function which takes value 1 when $A$ is true and 0 otherwise.
We use $C$, $c$, etc. to denote generic constants whose values might change from place to place.

\section{Bayes risk lower bounds for zero-one valued loss functions and their applications}
\label{sec:Bayes_01}

In this section, we consider zero-one loss functions $L$ and present a principled approach to derive Bayes risk lower bounds involving $f$-informativity for every $f \in {\mathcal{C}}$. Our results hold for any given prior $w$ and zero-one loss $L$. By specializing the $f$-divergence to KL   divergence, we obtain the generalized Fano's inequality~\eqref{intro_gf}. When specializing to other $f$-divergences, our bounds lead to some classical minimax bounds of Le Cam and Assouad \citep{Assouad:83}, more recent minimax results of \citet{Gushchin:03, Birge:ineq} and also results in \citet[Chapter 2]{Tsybakov:nonpara}. Bayes risk lower bounds for general nonnegative loss functions will be presented in the next section.

We need additional notations to state the main results of this section. For  each $f \in {\mathcal{C}}$, let $\phi_f: [0, 1]^2 \rightarrow {\mathbb R}$ be the function defined in the following way: for $a, b \in [0, 1]^2$, $\phi_f(a, b)$ is the $f$-divergence between the two probability measures $P$ and $Q$ on $\{0, 1\}$ given by $P\{1\} = a$ and $Q\{1\} = b$. By the definition \eqref{eq:df}, it is easy to see that $\phi_f(a, b)$ has the following  expression (recall that $f'(\infty) := \lim_{x \uparrow \infty} f(x)/x$):
\begin{eqnarray}\label{eq:phi}
  \phi_f(a, b) =\begin{cases}
    b f \left(\frac{a}{b} \right) + (1 - b) f \left(\frac{1-a}{1-b}
    \right)    & \text{for}  \quad 0 < b < 1;\\
  f(1-a) + a f'(\infty) & \text{for}  \quad b = 0;\\
  f(a) + (1 - a) f'(\infty) & \text{for}  \quad b = 1.  \\
  \end{cases}
\end{eqnarray}
The convexity of $f$ implies monotonicity and convexity properties of $\phi_f$, which is stated in the following lemma.
\begin{lemma}\label{lem:lower_property}
For each $f \in \mathcal{C}$, for every fixed $b$, the map $g(a): a \mapsto \phi_f(a,b)$ is non-increasing for $a \in [0,b]$ and $g(a)$ is convex and continuous in $a$. Further, for every fixed $a$, the map $h(b): b \mapsto \phi_f(a,b)$ is non-decreasing for $b \in  [a, 1]$.
\end{lemma}

We also define the quantity
\begin{equation}\label{R0def}
  R_0 := \inf_{a \in {\mathcal{A}}} \int_{\Theta} L(\theta, a) w(\mathrm{d}\theta),
\end{equation}
where the decision $a$ does not depend on data $X$. Note that $R_0$ represents the Bayes risk with respect to $w$ in the ``no data'' problem i.e., when one only has information on $\Theta$, ${\mathcal{A}}$, $L$ and the prior $w$ but not the data $X$. For simplicity, our notation for $R_0$ suppresses its dependence  on $w$. Because the loss function is zero-one valued so that $L(\theta,a)=1-\mathbb{I}(L(\theta,a)=0)$, the quantity $R_0$ has the following alternative expression:
\begin{equation}
  \label{alte}
  R_0 = 1 - \sup_{a \in {\mathcal{A}}} w(B(a)),
\end{equation}
where
\begin{equation}\label{ba}
B(a) := \left\{\theta \in \Theta: L(\theta, a) = 0 \right\},
\end{equation}
and $w(B(a))$ is the prior mass of the ``ball" $B(a)$.
It will be important in the sequel to observe that the Bayes risk, $R_{\rm Bayes}(w)$ is bounded from above by $R_0$. This is obvious because the risk with some data cannot be greater than the risk in the no data problem. Formally, if $\mathcal{D}=\{{\mathfrak{d}}:  \exists a \in {\mathcal{A}} ~~ \text{such that} ~~ {\mathfrak{d}}(x) = a~ \forall x \in \mathcal{X}\}$ is the class of the constant decision rules, then $R_0=\inf_{{\mathfrak{d}} \in \mathcal{D}} \int_{\Theta} {\mathbb E}_{\theta}L(\theta, {\mathfrak{d}}(X)) w(\mathrm{d}\theta) \geq R_{\rm Bayes}(w)$. Because $0 \leq R_{\rm Bayes}(w) \leq R_0$, we have $R_{\rm Bayes}(w) = 0$ when $R_0 = 0$. We shall therefore assume throughout this section that $R_0 > 0$.

The main result of this section is presented next. It provides an implicit lower bound for the Bayes risk in terms of $R_0$ and the $f$-informativity $I_f(w, {\mathcal{P}})$ for every $f \in {\mathcal{C}}$. The only assumption is that $L$ is zero-one valued and we do not assume the existence of the Bayes decision rule.
\begin{theorem}\label{man}
  Suppose that the loss function $L$ is zero-one valued. For any $f \in {\mathcal{C}}$, we have
  \begin{equation}
    \label{man.eq}
    I_f(w, {\mathcal{P}}) \geq \phi_f(R_{\rm Bayes}(w), R_0)
  \end{equation}
   where $\phi_f$ and $R_0$ are defined \eqref{eq:phi} and \eqref{R0def} respectively.
\end{theorem}

\begin{figure}[!t]
\centering
  \includegraphics[width=0.6\textwidth]{illu_main.png}
\caption{Illustration on why \eqref{man.eq} leads to a lower bound on $R_{\rm Bayes}(w)$. Recall that $R \leq R_0$ and $r \mapsto \phi_f(r, R_0)$ is non-increasing in $r$ for $r \in [0, R_0]$.  Given $I_f(w, \mathcal{P})$ as an upper bound of $\phi_f(R_{\rm Bayes}(w), R_0)$, we  have $R_{\rm Bayes}(w) >R_L$ and thus $R_L$ serves as a Bayes risk lower bound.
}
  \label{fig:phi_r}
\end{figure}

Inequality \eqref{man.eq} provides an implicit lower bound for the Bayes risk $R := R_{\rm Bayes}(w)$ since  $R \leq R_0$  and $r \mapsto \phi_f(r, R_0)$ is non-increasing in $r$ for $r \in [0, R_0]$ (Lemma \ref{lem:lower_property}).
As an illustration, we plot $\phi_f(r, R_0)$ for $f(x)=x \log x$ and $r \in [0, R_0]$ in Figure~\ref{fig:phi_r}. The implicit Bayes risk lower bound in \eqref{man.eq} can be easily converted into an  explicit bound in the following way. This technique will be used to establish the generalized Fano's inequality (see Corollary \ref{cor:Fano}). In particular, since $r \mapsto \phi_f(r, R_0)$ is convex (see Lemma \ref{lem:lower_property}),
\begin{equation*}
  \phi_f(R, R_0) \geq \phi_f(r, R_0) + \phi'_f(r-, R_0) (R - r) \qt{for every $0 < r \leq R_0$}
\end{equation*}
where $\phi_f'(r-, R_0)$ denotes the left derivative of $x \mapsto \phi_f(x, R_0)$ at $x = r$. The monotonicity of $\phi_f(r, R_0)$ in $r$ (Lemma \ref{lem:lower_property}) gives $\phi_f'(r-, R_0) \leq 0$ and we thus have,
\begin{equation*}
  R \geq r + \frac{\phi_f(R, R_0) - \phi_f(r, R_0)}{\phi_f'(r-, R_0)} \qt{for every $0 < r \leq R_0$}.
\end{equation*}
Inequality \eqref{man.eq}  $I_f(w, {\mathcal{P}}) \geq \phi_f(R, R_0)$ can now be used  to deduce that (note that  $\phi_f'(r-, R_0) \leq 0$)
\begin{equation}
  \label{expb}
  R \geq r + \frac{I_f(w, {\mathcal{P}}) - \phi_f(r, R_0)}{\phi_f'(r-, R_0)} \qt{for every $0 < r \leq R_0$}.
\end{equation}
The above inequality provides a general approach to convert \eqref{man.eq} to an  explicit lower bound on $R$.

Theorem~\ref{man} is new, but its special case $\Theta = {\mathcal{A}} =  \{1, \dots, N\}$, $L(\theta, a) := \mathbbm{I}\{\theta \neq a\}$ and the uniform prior $w$ is known (see \cite{Gushchin:03}  and \cite{Aditya:fdiv}). In such a discrete setting, $w(B(a))=1/N$ for any $a \in {\mathcal{A}}$ and thus $R_0=1-1/N$. The proof of Theorem \ref{man} (see Section \ref{sec:proof_man} in the appendix) heavily relies on the following lemma, which is a consequence of the data processing inequality for $f$-divergences (see \eqref{dpi} in Section \ref{sec:pre}).

\begin{lemma}\label{lem.dpi}
Suppose that the loss function $L$ is zero-one valued. For every $f \in {\mathcal{C}}$, every  probability measure $Q$ on ${\mathcal{X}}$ and every decision rule ${\mathfrak{d}}$, we have
\begin{equation}\label{main.eq1}
  \int_{\Theta} D_f(P_{\theta}||Q) w(\mathrm{d}\theta) \geq \phi_f(R^{{\mathfrak{d}}}, R_Q^{{\mathfrak{d}}})
\end{equation}
where
\begin{equation}\label{eq:def_R_Q}
   R^{{\mathfrak{d}}} := \int_{\Theta} {\mathbb E}_{\theta} L(\theta, {\mathfrak{d}}(X)) w(\mathrm{d}\theta) ~~, ~~   R_Q^{{\mathfrak{d}}} := \int_{{\mathcal{X}}} \int_{\Theta} L(\theta, {\mathfrak{d}}(x)) w(\mathrm{d}\theta) Q(\mathrm{d}x).
\end{equation}
\end{lemma}

We note that Lemma \ref{lem.dpi} is of independent interest, which can be applied to establish minimax lower bound as shown in the following remark.

\begin{remark}\label{rem:minimax}
  Lemma \ref{lem.dpi} can also be used to derive minimax lower bounds in a different  way.  For example, when the minimax decision rule ${\mathfrak{d}}$ exists (e.g., for finite space  $\Theta$ and ${\mathcal{A}}$ \citep{Ferguson76decision}), we have $R^{{\mathfrak{d}}} \leq R_{\rm minimax}$. If the probability measure $Q$ is chosen so that $R_{\rm minimax} \leq R_Q^{{\mathfrak{d}}}$, then, by Lemma~\ref{lem:lower_property}, the right hand side of~\eqref{man.eq} can be lower bounded by replacing $R^{{\mathfrak{d}}}$ with $R_{\rm minimax}$  which yields
\begin{equation}\label{eq:ext_main.eq_1}
  \int_{\Theta} D_f(P_{\theta}||Q) w(\mathrm{d}\theta) \geq \phi_f(R_{\rm minimax}, R_Q^{{\mathfrak{d}}}).
\end{equation}
Similarly, this inequality can be converted to an explicit lower bound on  minimax risk. We will show an application of this inequality in deriving Birg\'{e}-Gushchin inequality \citep{Gushchin:03, Birge:ineq}  in Section \ref{beig}.
\end{remark}

\subsection{Generalized Fano's inequality}
In the next result, we derive the generalized Fano's ienquality  \eqref{intro_gf} using Theorem \ref{man}. The inequality proved here is in fact slightly stronger than \eqref{intro_gf}; see Remark \ref{pach} for the clarification.

\begin{corollary}[Generalized Fano's inequality]\label{cor:Fano}
For any given prior $w$ and zero-one loss $L$, we have
\begin{equation}\label{gf}
  R_{\rm Bayes}(w, L; \Theta) \geq 1 + \frac{I(w, \mathcal{P}) + \log (1 + R_0)}{\log \left(\sup_{a \in {\mathcal{A}}} w(B(a))\right)},
\end{equation}
where $B(a)$ is defined in \eqref{ba}.
\end{corollary}

To prove this corollary, we simply  apply \eqref{expb} to $f(x) = x \log x$ and $r = R_0/(1 + R_0)$ and detailed calculations are provided in Section \ref{sec:proof_fano} in the appendix.

\begin{remark}\label{pach}
This inequality is slightly stronger than \eqref{intro_gf} because $R_0 \leq 1$ (thus $\log(1+R_0) \leq \log 2$). For example, when $\Theta = {\mathcal{A}} = \{0, 1\}$, $L(\theta, a) := \mathbbm{I}\{\theta \neq a\}$ and $w\{0\} = w\{1\} = 1/2$, the inequality \eqref{intro_gf} leads to a trivial bound since the right hand side of \eqref{intro_gf} is negative. However, since $R_0=1/2$, the inequality \eqref{gf} still provides a useful lower bound when $I(w, {\mathcal{P}})$ is strictly  smaller than $\log 2 -\log(3/2)$.
\end{remark}

As mentioned in the introduction, the classical Fano inequality \eqref{eq:classcial_Fano} and the recent continuum Fano inequality \eqref{cf} are both special cases (restricted to uniform priors) of Corollary \ref{cor:Fano}. The proof of \eqref{cf} given in \cite{Duchi:Fano} is rather complicated
with a stronger assumption and a discretization-approximation argument. Our proof based on Theorem \ref{man} is much simpler. Lemma \ref{lem.dpi} also has its independent interest. Using Lemma \ref{lem.dpi}, we are able to recover another recently proposed variant of Fano's inequality in \citet[Proposition 2.2]{BraunPokutta}. Details of this argument are provided in Section  \ref{sec:supp_Fano} in the appendix.

\subsection{Specialization of Theorem \ref{man} to different $f$-divergences and their applications}
In addition to the generalized Fano's inequality, Theorem \ref{man} allows us to derive a class of lower bounds on Bayes risk for zero-one losses by plugging other $f$-divergences. In the next corollary, we consider some widely used $f$-divergences  and provide the corresponding Bayes risk lower bounds by inverting \eqref{man.eq} in Theorem \ref{man}.
\begin{corollary}\label{cor:lb_01_f}
  Let $L$ be zero-one valued, $w$ be any arbitrary prior on $\Theta$ and $R = R_{\rm Bayes}(w, L, \Theta)$. We then have the following inequalities
  \begin{enumerate}[(i)]
    \item Chi-squared divergence:
      \begin{equation}
        \label{eq:chi}
        R \geq R_0 - \sqrt{R_0(1 - R_0) I_{\chi^2}(w, {\mathcal{P}})} .
      \end{equation}
    \item Total variation distance:
      \begin{equation}
    R \geq R_0 - I_{TV}(w, {\mathcal{P}}).
      \label{eq:total}
    \end{equation}
    \item Hellinger distance:
      \begin{equation}
        \label{eq:hellinger_3}
        R \geq R_0 - (2 R_0 - 1) \frac{h^2}{2} - \sqrt{R_0(1 - R_0) h^2 (2 - h^2)}
      \end{equation}
      provided $h^2 \leq 2 R_0$. Here $
        h^2=\int_{\Theta} \int_{\Theta}  H^2(P_{\theta}\| P_{\theta'})  w(\mathrm{d} \theta)w(\mathrm{d} \theta').
     $
\end{enumerate}
\end{corollary}

The inequalities in Corollary \ref{cor:lb_01_f} can be proved from Theorem \ref{man}; these proofs are provided in Section \ref{colr} of the appendix. The special case of Corollary \ref{cor:lb_01_f} for $\Theta = {\mathcal{A}} = \{1, \dots, N\}$, $L(\theta, a) = \mathbbm{I}\{\theta \neq a\}$ and $w$ being the uniform prior has been discovered previously in \cite{Aditya:fdiv}. Corollary \ref{cor:lb_01_f} can be used to recover classical inequalities of Le Cam (for two point hypotheses) and Assouad (Theorem 2.12 in \cite{Tsybakov:nonpara} with both total variation distance and Hellinger distance) and Theorem 2.15 in \cite{Tsybakov:nonpara} that involves fuzzy hypotheses. The details are presented in Section \ref{sec:supp_LeCam} of the appendix.

\subsection{Comparison of the bounds for different divergences}
\label{sec:compare}
We provide some qualitative comparisons of Bayes risk lower bounds given by Theorem \ref{man} for different power divergences.
In particular, let us consider the discrete setting where $\Theta = {\mathcal{A}} = \{\theta_1, \dots, \theta_N\}$, $L(\theta, a) = \mathbbm{I}\{\theta \neq a\}$, and $w$ is the discrete uniform. Note that in such a ``multiple testing problem" setup, $R_0$ is equal to $1 - (1/N)$. We take $N$ sufficiently large so that $R_0$ is close to 1. To establish minimax lower bounds, a typical approach is to reduce the estimation problem to a multiple hypotheses testing problem in the aforementioned setup, then try to prove that the Bayes risk $R \geq c>0$ (see Section 2.2. in \cite{Tsybakov:nonpara}). Without loss of generality, we take $c = 1/2$ and we shall see how the three  inequalities  \eqref{gf}, \eqref{eq:chi} and \eqref{eq:hellinger_3} work to establish $R \geq 1/2$.

Let us start with \eqref{gf} corresponding to KL divergence, which is equivalent to the classical Fano's  inequality \eqref{eq:classcial_Fano} in the discrete setting. To establish $R \geq 1/2$, the following condition should hold:
\begin{equation}\label{nef}
  I(w, {\mathcal{P}}) \leq \frac{1}{2} \log \left(\frac{N}{4} \right).
\end{equation}
We remark that $I(w, {\mathcal{P}})$ is at most $\log N$ even if every the pairwise KL divergence $D(P_{\theta_i} \| P_{\theta_j})$ equals $\infty$ for $i \neq j$.  This fact will be clear from the inequality \eqref{ybp} from Section \ref{sec:upper_f_informativity} (let $M=N$ and $Q_j=P_{\theta_j}$ for $1 \leq j \leq M$). The upper bound on $I(w, \mathcal{P})$ in  \eqref{ybp} further provides a sufficient condition to verify \eqref{nef}.

Now we turn to \eqref{eq:chi} corresponding to the chi-squared divergence. Since $R_0 = 1-(1/N)$, inequality \eqref{eq:chi} implies a sufficient condition for $R \geq 1/2$:
\begin{equation}\label{nec}
  I_{\chi^2}(w,{\mathcal{P}}) \leq \frac{N^2}{N-1} \left(\frac{1}{2} - \frac{1}{N} \right)^2.
\end{equation}
When $N$ is large, the above condition is equivalent to $I_{\chi^2}(w, {\mathcal{P}}) \leq N/4$.  Note that the maximum possible value of $I_{\chi^2}(w, {\mathcal{P}})$ in this discrete setting is $N - 1$ (even when $\chi^2(P_{\theta_i} \| P_{\theta_j})  = \infty$ for every $i \neq j$) and this follows from our upper bounds on $f$-informativity for a class of power divergences in \eqref{eq:upper_f_power} (see Section \ref{sec:upper_f_informativity}).

The conditions \eqref{nef} and \eqref{nec} don't imply each other. The chi-squared divergence is always greater than the KL divergence (see Lemma 2.7 in \cite{Tsybakov:nonpara}), but the upper bound required by~\eqref{nec} is also weaker than that required by~\eqref{nef}. For both divergences, constructing more hypotheses (i.e., choosing $N>2$) is often helpful for showing $R \geq 1/2$.

For the Hellinger distance (inequality \eqref{eq:hellinger_3}), we claim that it gives no more useful bounds than those obtained by a simple two point argument. To see this, since $R_0 = 1 - (1/N)$,  inequality \eqref{eq:hellinger_3} implies
\begin{equation*}
  R \geq 1 - \frac{1}{N} - \frac{N-2}{N} \frac{h^2}{2} - \frac{\sqrt{N-1}}{N} \sqrt{h^2(2 - h^2)}
\end{equation*}
where $h^2 = \sum_{i, j} H^2(P_{\theta_i} || P_{\theta_j})/N^2$. When $N$ is large, the above inequality reduces to effectively $R \geq 1 - (h^2/2)$. Therefore a sufficient condition for $R \geq 1/2$ is $h^2 \leq 1$, which is equivalent to,
\begin{equation*}
  \frac{1}{N(N-1)/2} \sum_{i < j} H^2(P_{\theta_i}|| P_{\theta_j}) \leq \frac{N}{N-1}.
\end{equation*}
When $N$ is large, the above displayed condition implies the existence of $i < j$ for which $H^2(P_{\theta_i}|| P_{\theta_j}) \leq 1$. Let $\tilde{w}$ denote the prior $\tilde{w}\{i\} = \tilde{w}\{j\} = 1/2$. It is easy to see that the Bayes risk for $\tilde{w}$ equals
$
  R_{\rm Bayes}(\tilde{w}) = \frac{1}{2} \left(1 - \|P_{\theta_i} - P_{\theta_j}\|_{TV} \right).
$
By Le Cam's inequality (see Lemma 2.3 in \cite{Tsybakov:nonpara}), we have,
\begin{equation*}
  R_{\rm Bayes}(\tilde{w}) \geq \frac{1}{2} \left( 1 - H(P_{\theta_i} || P_{\theta_j}) \sqrt{1 - \frac{H^2(P_{\theta_i}|| P_{\theta_j})}{4}} \right)
\end{equation*}
Since $H(P_{\theta_i} || P_{\theta_j}) \leq 1$, it is easy to verify from the above that $R_{\rm Bayes}(\tilde{w}) \geq 1/8$. Therefore in this discrete setting, if inequality \eqref{eq:hellinger_3} implies $R_{\rm Bayes}(w) \geq 1/2$, then there is a much simpler two point prior $\tilde{w}$ for which $R_{\rm Bayes}(\tilde{w}) \geq 1/8$. It shows that for Hellinger distance, considering $N>2$ hypotheses is not more useful than using a pair of hypotheses. The reason is that the Hellinger informativity can be written as an expression involving pairwise Hellinger distances. In particular, it can be seen from the proof of inequality \eqref{eq:hellinger_3} that
\[
  I_{f_{1/2}}(w, {\mathcal{P}}) = 1 - \Bigl(1 - \frac{1}{2N^2} \sum_{i, j} H^2(P_{\theta_i} || P_{\theta_j})\Bigr)^{1/2}.
\]
In contrast, the mutual information, $I(w, {\mathcal{P}})$, cannot be written in terms of $D(P_{\theta_i} \| P_{\theta_j})$ for $i \neq j$ (recall that $I(w, {\mathcal{P}})$ is always at most $\log N$ even when $D(P_{\theta_i} \| P_{\theta_j}) = \infty$ for all $i \neq j$). The same holds for $I_{\chi^2}(w, {\mathcal{P}})$ as well (which is always at most $N - 1$ even if $\chi^2(P_{\theta_i} \| P_{\theta_j}) = \infty$ for all $i \neq j$).

If the eventual goal of obtaining Bayes risk lower bounds is to obtain lower bounds upto multiplicative constants on the minimax risk, then the bound in \eqref{eq:hellinger_3} gives no more useful bounds than those obtained by the simple two point argument. In this sense, inequality \eqref{eq:hellinger_3} induced by Hellinger distance is not as useful as inequalities \eqref{gf} and \eqref{eq:chi}. In fact, the Hellinger distance is seldom used in lower bounding minimax risk involving many hypotheses (for example, none of the minimax rates in the examples of  \cite{Tsybakov:nonpara} involving multiple hypotheses testing are established via Hellinger distance).

Therefore, in most applications in this paper in Section \ref{sec:upper_f_informativity} and \ref{sec:admis}, we shall only use the bounds involving KL   and chi-squared divergence. Also, in Section \ref{sec:upper_f_informativity} on bounding $f$-informativities, we will focus on the bounds involving KL  and chi-squared divergences (and more generally for power divergences with $\alpha \geq 1$) as opposed to the Hellinger distance (and more generally for power divergences with $\alpha \in (0, 1)$).

\subsection{Birg\'e-Gushchin's inequality and an application}\label{beig}

In this section, we expand \eqref{eq:ext_main.eq_1} in Remark \ref{rem:minimax} to obtain a minimax risk lower bound due to \cite{Gushchin:03} and \cite{Birge:ineq}, which presents an improvement of the classical Fano's inequality when specializing to KL divergence.
\begin{proposition}\citep{Gushchin:03, Birge:ineq}\label{prop:Birge}
  Consider the finite parameter and action space $\Theta={\mathcal{A}}=\{\theta_0, \theta_1, \ldots, \theta_{N} \}$  and the zero-one valued indicator loss $L(\theta, a) = \mathbbm{I}\{\theta \neq a\}$,  for any $f$-divergence,
\begin{equation}
  \psi_{N,f}(R_{\rm minimax}) \leq \min_{0 \leq j \leq N} \frac{1}{N} \sum_{i: i\neq j} D_f\left(P_{\theta_i} || P_{\theta_j}  \right),
  \label{eq:Birge}
\end{equation}
where $\psi_{N,f}(x):= \frac{N-x}{N} f\left(\frac{Nx}{N-x} \right) + \frac{x}{N} f\left(\frac{N(1-x)}{x}\right).
$
\end{proposition}

Proposition \ref{prop:Birge} applied to specific $f$-divergences has interesting connections to several existing risk lower bounds in the literature. In particular, it is possible to derive, via Proposition \ref{prop:Birge}, many inequalities in \cite{Tsybakov:nonpara} including Theorem 2.4 (referred to as ``main theorem on lower bounds for the risk" by \cite{Tsybakov:nonpara}) and its corollaries (Proposition 2.3, Theorem 2.5, Proposition 2.4 Theorem 2.6). In order to derive Theorem 2.4 in   \cite{Tsybakov:nonpara}, we use Proposition \ref{prop:Birge} with a carefully designed $f$-divergence $D_f(\cdot||\cdot)$ induced by the following convex function for fixed $s \in {\mathbb R}$,
\[
f(x)=\min(1,s)-\min(x, s)
\]
The resulting divergence will then involve the likelihood ratio term in Eq. (2.41) in  Theorem 2.4 in \cite{Tsybakov:nonpara}. This also serves as an interesting application of a specially constructed $f$-divergence other than the commonly used power divergences. Details are provided in Section \ref{sec:likelihood} of the  appendix.

\section{Bayes risk lower bounds for nonnegative loss functions}
\label{sec:Bayes_general}

\begin{figure}[!t]
\centering
  \begin{subfigure}{.45\textwidth}
  \centering
  \includegraphics[width=\textwidth]{Phi_f}
  \caption{$\phi_f(1/2, b)$}
  \label{fig:phi}
\end{subfigure}\hspace{0.1cm}
\begin{subfigure}{.45\textwidth}
  \centering
  \includegraphics[width=\textwidth]{u_f}
  \caption{$u_f(x)$}
  \label{fig:u}
\end{subfigure}
\caption{Illustration of $\phi_f(1/2,b)$ and $u_f(x)$ for $f(x)=x\log x$.}
\label{fig:phi_u}
\end{figure}
In the previous section, we discussed Bayes risk lower bounds for zero-one valued loss functions. We deal with general nonnegative loss functions in this section. The main result of this section, Theorem \ref{bwl}, provides lower bounds for $R_{\rm Bayes}(w, L; \Theta)$ for any given loss $L$ and prior $w$. To state this result, we need the following notion.
Fix $f \in {\mathcal{C}}$ and recall the definition of $\phi_f$ in \eqref{eq:phi}. We define   $u_f: [0, \infty) \mapsto [1/2,1]$ by
\begin{equation}\label{ufi}
  u_f(x) := \inf \left\{1/2 \leq b \leq 1 : \phi_f(1/2, b) > x \right\}
\end{equation}
and if $\phi_f(1/2, b) \leq x$ for every $b \in [1/2, 1]$, then we take $u_f(x)$
to be 1. By Lemma \ref{lem:lower_property}, it is easy to see that $u_f(x)$ is a non-decreasing function of $x$. For example, for KL-divergence with $f(x)= x \log x$, we have $\phi_f(1/2, b)=\frac{1}{2} \log \frac{1}{4b(1-b)}$ and $u_f(x) = \frac{1}{2}+ \frac{1}{2} \sqrt{1-e^{-2x}}$ (see Figure \ref{fig:phi_u}). We are now ready to state the main theorem of this paper.
\begin{theorem}\label{bwl}
For every $\Theta, {\mathcal{A}}, L, w$ and $f \in {\mathcal{C}}$, we have
\begin{equation}
  R_{\rm Bayes}(w, L; \Theta)  \geq \frac{1}{2} \sup\left\{t > 0 :  \sup_{a \in \mathcal{A}}  w(B_t(a,L))  < 1- u_f(I_f(w, {\mathcal{P}})) \right\},
  \label{eq:main_bwl}
\end{equation}
where
\begin{equation}  \label{bta}
B_t(a, L) := \{\theta \in \Theta: L(\theta, a) < t\} \qt{for $a \in {\mathcal{A}}$ and $t > 0$}.
\end{equation}
\end{theorem}

Because $u_f(x)$ is non-decreasing in $x$, one can replace $I_f(w, {\mathcal{P}})$ in \eqref{eq:main_bwl} by any upper bound $I_f^{\rm up}$ i.e., for any $I_f^{\rm up} \geq I_f(w, {\mathcal{P}})$, we have
\begin{equation}\label{upbo}
  R_{\rm Bayes}(w, L; \Theta)  \geq \frac{1}{2} \sup\left\{t > 0 :  \sup_{a \in \mathcal{A}}  w(B_t(a,L))  < 1- u_f(I_f^{\rm up}) \right\}.
\end{equation}
This is useful since $I_f(w, {\mathcal{P}})$ is often difficult to calculate exactly. When $f(x)=x\log x$, \cite{haussler1997} provided a useful upper bound on the mutual information $I(w, {\mathcal{P}})$. We describe this result in Section \ref{sec:upper_f_informativity} where we also extend it to power divergences $f_\alpha$ for  $\alpha \not \in [0,1]$ (which covers the case of chi-squared divergence).

\begin{remark}
From the proof of Theorem \ref{bwl} (see Section \ref{sec:proof_bwl} in the appendix), it can be observed that the constant $1/2$ in the right hand side of \eqref{eq:main_bwl} and in the definition of $u_f(\cdot)$ can be replaced by any $c \in (0,1]$. This gives the sharper lower bound:
\small
\begin{eqnarray*}
     R_{\rm Bayes}(w, L; \Theta) \geq \sup_{c \in (0,1]} \left( c \sup \left\{t > 0 : \sup_{a
      \in {\mathcal{A}}} w \left(B_t(a,L) \right) < 1- u_{f,c}(I_f(w, {\mathcal{P}})) \right\} \right),
\end{eqnarray*}
\normalsize
where $u_{f,c}(x)=\inf\{c\leq b \leq 1: \phi_f(c, b) \geq x \}$. Since obtaining exact constants is not our main concern, the inequality \eqref{eq:main_bwl} is usually sufficient to provide Bayes risk lower bounds with correct dependence on the model and prior.
\end{remark}

\begin{remark}\label{rem:Bayes_decomp}

 We note that the lower bound presented in Theorem \ref{bwl} might not be tight for some specially constructed priors, e.g., when the prior $w$ has a spike.  As a concrete example, let $\Theta = {\mathcal{A}}$ be a subset of a  finite dimensional Euclidean space containing the origin with $L$ being the Euclidean distance and let $w$ denote the mixture of the uniform priors over the balls $B_1(0, L)$ and $B_\epsilon(0, L)$ for some very small $0 < \epsilon \ll 1$. In such case, the term $\sup_{a \in \mathcal{A}} w(B_t(a,L))$ will be too large to establish a tight Bayes risk lower bound (consider $a = 0$).

 For such situations, the tight lower bound can often be salvaged by partitioning the parameter space $\Theta$ into finite or countably many disjoint subsets $\Theta_i, i \geq 0$ and to apply Theorem \ref{bwl} to $w$ restricted to each $\Theta_i$. To illustrate this technique, suppose that $w$ has a  Lebesgue density  $f$ that is bounded from above. Let $f_{\max}$ denote the supremum of $f$. We partition the parameter space $\Theta$ into disjoint subsets $\Theta_0,\Theta_1,\dots$ with
 \begin{equation}\label{eq:space_part}
	\Theta_i := \{\theta\in\Theta: 2^{-(i+1)} f_{\max} < f(\theta) \leq 2^{-i} f_{\max} \}.
 \end{equation}
 Then, we apply Theorem \ref{bwl} to $w$ restricted to each $\Theta_i$. More specifically, let $w_i$ denote the probability measure $w$ restricted to $\Theta_i$ i.e., $w_i(S) := w(S \cap \Theta_i)/w(\Theta_i)$ for any measurable set $S \subseteq  \Theta_i$.  we have
\begin{equation}\label{eq:prior_decomp}
  R_{\rm Bayes}(w, L; \Theta) \geq \sum_{i} w(\Theta_i) R_{\rm Bayes}(w_i, L; \Theta_i),
\end{equation}
where $R_{\rm Bayes}(w_i, L; \Theta_i)=\inf_{{\mathfrak{d}}} \int_{\Theta_i} {\mathbb E}_{\theta} L(\theta, {\mathfrak{d}}(X)) w_i(\mathrm{d}\theta)$.
To see this, for any decision rule ${\mathfrak{d}}$, we have
$
    	R^{\mathfrak{d}}(w, L; \Theta) = \sum_{i=1}^\infty w(\Theta_i)R^{{\mathfrak{d}}} (w_i, L; \Theta_i);
$
then take infimum over all possible ${\mathfrak{d}}$ on both sides,
\begin{multline*}
 R_{\rm Bayes}(w, L;\Theta) = \inf_{{\mathfrak{d}}} R^{\mathfrak{d}}(w, L; \Theta) \\ \geq \sum_{i=1}^\infty w(\Theta_i) \inf_{{\mathfrak{d}}}  R^{{\mathfrak{d}}} (w_i, L; \Theta_i)=\sum_{i=1}^\infty w(\Theta_i) R_{\rm Bayes}(w_i, L; \Theta_i)
\end{multline*}
One can lower bound each Bayes risk $R_{\rm Bayes}(w_i, L; \Theta_i)$ for all $i$ using Theorem \ref{bwl}. Since the density of $w_i$ differs by a factor at most $2$, the spiking prior problem will no longer exist while applying Theorem \ref{bwl} for $w_i$. We also note that another useful application of such a partitioning technique is presented in Corollary \ref{nd}.

Now take the concrete example of the mixture of the uniform priors over  $B_1:=B_1(0, L)$ and $B_\epsilon:= B_\epsilon(0, L)$.  It is clear from \eqref{eq:space_part} that $\Theta_0=B_\epsilon$ and $\Theta_k=B_1\backslash B_\epsilon$ for some $k>0$ and the rest of $\Theta_i$'s are empty sets.
Applying \eqref{eq:prior_decomp},  we have
    \begin{align*}
      R_{\rm Bayes}(w, L; \Theta) \geq & w(B_{\epsilon}) R_{\rm Bayes}(w_1, L; B_{\epsilon})  + w(B_1 \backslash B_{\epsilon}) R_{\rm Bayes}(w_2, L; B_1  \backslash B_{\epsilon})  \\
      \geq & w(B_1 \backslash B_{\epsilon}) R_{\rm Bayes}(w_2, L; B_1  \backslash B_{\epsilon})
    \end{align*}
Note that $w(B_1 \backslash B_{\epsilon})$ is lower bounded by a universal constant. Then we can lower bound $R_{\rm Bayes}(w_2, L; B_1  \backslash B_{\epsilon})$ using Theorem \ref{bwl} and obtain a tight lower bound up to a constant factor that is independent of $\epsilon$ (see an example of deriving Bayes risk lower bound for estimating the mean of a Gaussian model with uniform prior on a ball in Section~\ref{sec:upper_f_informativity}).

\end{remark}

For specific $f \in {\mathcal{C}}$, the right hand side of \eqref{upbo} can be explicitly evaluated. This is the next corollary whose proof is given in Section \ref{sec:supp_bwl} of the appendix.

\begin{corollary}\label{cor:bwl}
Fix $\Theta, {\mathcal{A}}, L, w$ and ${\mathcal{P}}$. The Bayes risk $R_{\rm Bayes}(w, L; \Theta)$ satisfies each of the following inequalities (the quantity $I_f^{\rm up}$ represents an upper bound on the corresponding $f$-informativity):
  \begin{enumerate}[(i)]
    \item KL divergence:
    \small
       \begin{equation}
  R_{\rm Bayes}(w,L;\Theta) \geq \frac{1}{2} \sup \left\{t > 0 : \sup_{a
      \in {\mathcal{A}}} w\left(B_t(a,L)\right)< \frac{1}{4} e^{-2 I_f^{\rm up}} \right\}.
    \label{eq:I_bayes_KL}
\end{equation}
\normalsize
    \item Chi-squared divergence:
    \small
      \begin{equation}
    R_{\rm Bayes}(w, L;\Theta) \geq \frac{1}{2} \sup \left\{t > 0 :
      \sup_{a \in {\mathcal{A}}} w \left( B_t(a,L) \right) < \frac{1}{4\left(1+ I_f^{\rm up}\right)} \right\}.
        \label{eq:I_bayes_chi}
  \end{equation}
  \normalsize
    \item Total variation distance:
    \small
      \begin{equation}
    R_{\rm Bayes}(w, L;\Theta) \geq \frac{1}{2} \sup \left\{t> 0 :
      \sup_{a \in {\mathcal{A}}} w \left(B_t(a,L) \right)  < \frac{1}{2} - I_f^{\rm up} \right\}.
      \label{eq:I_bayes_TV}
  \end{equation}
  \normalsize
    \item Hellinger distance:
    If $I_f^{\rm up} < 1-1/\sqrt{2}$, then we have
    \small
  \begin{equation}
    R_{\rm Bayes}(w,L;\Theta) \geq \frac{1}{2} \sup \left\{t > 0 :
      \sup_{a \in {\mathcal{A}}} w \left(B_t(a,L) \right) < \frac{1}{2} - \left(1- I_f^{\rm up}\right)\sqrt{ I_f^{\rm up}\left(2- I_f^{\rm up}\right)} \right\}.
      \label{eq:I_bayes_Hellinger}
  \end{equation}
  \normalsize
  \end{enumerate}
\end{corollary}

\section{Upper bounds on $f$-informativity and examples}
\label{sec:upper_f_informativity}
To apply Theorem~\ref{bwl}, we need upper bounds on the $f$-informativity $I_f(w; {\mathcal{P}})$. In this section, we focus on the power divergence $f_{\alpha}$ for some $\alpha \geq 1$. Recall that in Section \ref{sec:compare}, we provided motivation for restricting our attention to such divergences.  We assume that there is a measure $\mu$ on ${\mathcal{X}}$ that dominates $P_{\theta}$ for every $\theta \in \Theta$. We will also  implicitly make the assumption that any other probability measure on ${\mathcal{X}}$ is also dominated by $\mu$. None of our results depend on the choice of the dominating measure $\mu$.

When the $f$-informativity is the mutual information,~\cite{haussler1997} have proved useful upper bounds which we briefly review here. Let $P$ and $\{Q_{\vartheta}, \vartheta \in \Xi\}$ be probability measures on ${\mathcal{X}}$
having densities $p$ and $\{q_{\vartheta}, \vartheta \in \Xi\}$ respectively. Let $\nu$ be an arbitrary probability measure on $\Xi$ and $\bar{Q}$ be the probability measure on ${\mathcal{X}}$ having density $\bar{q}=\int_{\Xi} q_{\vartheta} \nu(\mathrm{d}\vartheta)$. \cite{haussler1997} proved the following inequality
\begin{eqnarray}
  D\left(P||\bar{Q} \right) \leq - \log\left(\int_{\Xi} \exp\left(-D(P||Q_{\vartheta}) \right) \nu(\mathrm{d}\vartheta) \right).
  \label{eq:upper_KL_0}
\end{eqnarray}
Now given a class of probability measures $\{P_{\theta}, \theta \in \Theta\}$, applying the above inequality for each $P_{\theta}$ and integrating the resulting inequalities with respect to a probability measure $w$ on $\Theta$,~\citet[Theorem 2]{haussler1997} obtained the following mutual information upper bound:
\begin{equation}\label{eq:upper_KL_1}
I(w, {\mathcal{P}}) \leq  - \int_{\Theta} w(\mathrm{d} \theta) \log \left(\int_{\Xi} \exp\left(-D(P_{\theta}||Q_{\vartheta}) \right) \nu(\mathrm{d}\vartheta) \right).
\end{equation}

In the special case when $\Xi=\{1,\ldots, M\}$ and $\nu$ is the uniform probability measure on $\Xi$, we have $\bar{Q}=\left(Q_1 + \ldots + Q_M\right)/M$ and inequality  \eqref{eq:upper_KL_0} then becomes
$
    D(P||\bar{Q}) \leq -\log \left(\frac{1}{M} \sum_{j=1}^M \exp
      \left(-D(P||Q_j) \right) \right).
$
Because $\sum_{j=1}^M \exp(-D(P\|Q_j)) \geq \exp \left(-\min_{j} D(P\|Q_j) \right)$, we obtain
\begin{equation*}
  D(P \| \bar{Q}) \leq \log M + \min_{1 \leq j \leq M} D(P\|Q_j).
\end{equation*}
Inequality~\eqref{eq:upper_KL_1} can be further simplified to
  \begin{equation}\label{ybp}
   I(w, {\mathcal{P}}) \leq \log M +
    \int_{\Theta} \min_{1 \leq j \leq M} D(P_{\theta}||Q_j)
    w(\mathrm{d}\theta).
  \end{equation}
This inequality can be used to give an upper bound for $f$-informativity in terms of the KL covering numbers. Recall the definition of $M_{KL}(\epsilon, \Theta)$ from~\eqref{redf}. Applying~\eqref{ybp} to any fixed $\epsilon>0$  and
choosing $\{Q_1, \dots, Q_M\}$ to be an $\epsilon^2$-covering, we have
  \begin{equation}\label{yb}
   I(w, {\mathcal{P}})\leq
    \inf_{\epsilon > 0} \left(\log M_{KL}(\epsilon, \Theta) + \epsilon^2
    \right).
  \end{equation}
  When $w$ is the uniform prior on a finite
  subset of $\Theta$, the above inequality has been proved by~\citet[Page 1571]{Yang:Barron:99}. If $M_{KL}(\epsilon, \Theta)$ is infinity for all $\epsilon$, then \eqref{yb} gives $\infty$ as the upper bound on $I(w, {\mathcal{P}})$ and thus \eqref{eq:I_bayes_KL} will lead to a trivial lower bound $0$ for $R_{\rm Bayes}$.
   In such a case, one may find a subset $\tilde{\Theta} \subset \Theta$ for which $M_{KL}(\epsilon, \tilde{\Theta})$ is bounded and contains most prior mass. If $\tilde{w}$ denotes the prior $w$ restricted in $\tilde{\Theta}$, then it is easy to see that $R_{\rm Bayes}(w, L; \Theta) \geq  w(\tilde{\Theta}) R_{\rm Bayes}(\tilde{w}, L; \tilde{\Theta})$. Then we can use~\eqref{eq:I_bayes_KL} and~\eqref{yb} to lower bound $R_{\rm Bayes}(\tilde{w}, L; \tilde{\Theta})$ .

In the next theorem, we extend inequalities \eqref{eq:upper_KL_0} and \eqref{eq:upper_KL_1} to power divergences corresponding to $f_{\alpha}$ for $\alpha  \notin [0, 1]$. We also note that in Subsection \ref{effb} of the appendix, we demonstrate the tightness of  the bound~\eqref{co1} in Theorem \ref{cd} by a simple example.

\begin{theorem}\label{cd}
Fix $\alpha \notin [0, 1]$ and let $f_{\alpha} \in {\mathcal{C}}$ be as defined in Section~\ref{sec:pre}. Under the setting of inequalities~\eqref{eq:upper_KL_0} and~\eqref{eq:upper_KL_1}, we have
  \begin{equation}\label{co1}
    D_{f_{\alpha}}(P||\bar{Q}) \leq  \left[\int_{\Xi} \left( D_{f_{\alpha}} (P||Q_{\vartheta}) +1 \right)^{1/(1-\alpha)} \nu(\mathrm{d}\vartheta) \right]^{1-\alpha} - 1.
  \end{equation}
and
  \begin{equation}\label{eq:upper_f_power}
    I_{f_\alpha}(w, \mathcal{P}) \leq \int_{\Theta} \left[\int_{\Xi} \left( D_{f_{\alpha}} (P_\theta||Q_{\vartheta}) +1 \right)^{1/(1-\alpha)} \nu(\mathrm{d}\vartheta) \right]^{1-\alpha} w(\mathrm{d}\theta) - 1.
  \end{equation}
\end{theorem}

For $\alpha > 1$, one can deduce an upper bound analogous to~\eqref{yb} for the $f_{\alpha}$-informativity which is described in the next corollary. Recall the notion of the covering numbers $M_{\alpha}(\epsilon, \Theta)$ from Section \ref{sec:pre}.

\begin{corollary}\label{cor:chi_dist_upper}
  For every $\alpha > 1$, we have
  \begin{equation}\label{eq:chi_dist_upper}
    I_{f_\alpha}(w, \mathcal{P})  \leq \inf_{\epsilon> 0} (1 + \epsilon^2) M_{\alpha}(\epsilon, \Theta)^{\alpha - 1} - 1.
  \end{equation}
\end{corollary}
In particular, when $D_{f_{\alpha}}$ is the chi-square divergence, Corollary~\ref{cor:chi_dist_upper} implies
\begin{equation}\label{eq:chi_dist_upper_1}
I_{\chi^2}(w, \mathcal{P}) \leq \inf_{\epsilon> 0} (1 + \epsilon^2) M_{\chi^2}(\epsilon, \Theta) - 1.
\end{equation}
Note that Corollary~\ref{cor:chi_dist_upper} gives trivial bound when $M_{\alpha}(\epsilon, \Theta)$ equals $\infty$ for all $\epsilon > 0$. This can be handled in a way similar to that outlined in the discussion after \eqref{yb}.

We now turn to applications of the Bayes risk lower bounds in Corollary \ref{cor:bwl} and the informativity upper bounds in this section. We present a toy example here and postpone more complicated examples (e.g., generalized linear model, spiked covariance model, Gaussian model with general prior and loss) to Section \ref{sec:Bayes_Example} of the appendix.

\begin{example}[Gaussian model with uniform priors on large balls]\label{tutu}
Fix $d \geq 1$. Suppose $\Theta = {\mathcal{A}} \subseteq {\mathbb R}^d$ and let $L(\theta, a) := \|\theta - a\|_2^2$. For each $\theta \in {\mathbb R}^d$, let $P_{\theta}$ denote the Gaussian distribution with mean $\theta$ and covariance matrix $\sigma^2 I_{d\times d}$  ($\sigma^2 > 0$ is a constant). Let $w$ be the uniform distribution on the closed ball of  radius $\Gamma$ centered at the origin. Let $\Gamma \geq \sigma \sqrt{d}$. We will show below how to obtain  the tight Bayes risk lower bound using Corollary \ref{cor:bwl} along with the $f$-informativity upper bound in Corollary~\ref{cor:chi_dist_upper}.

We can assume that $\Theta$ (and ${\mathcal{A}}$) is the closed ball of radius $\Gamma$ centered at the origin as $w$ puts zero probability outside this ball. We use the inequality~\eqref{eq:I_bayes_chi} induced by the chi-squared divergence. To establish the lower bound, we need to upper bound $\sup_{a \in {\mathcal{A}}} w(B_t(a, L))$ and the chi-squared informativity. The former can be easily controlled because $\sup_{a \in {\mathcal{A}}} w(B_t(a, L)) \leq \left(\sqrt{t}/\Gamma \right)^d.$ For the latter, we use \eqref{eq:chi_dist_upper_1}, which requires an upper bound on $M_{\chi^2}(\epsilon, \Theta)$. Note that $\chi^2(P_{\theta} \| P_{\theta'}) = \exp \left(\|\theta-\theta'\|_2/\sigma^2 \right) - 1$ for $\theta, \theta' \in \Theta$. As a consequence, $\chi^2(P_{\theta} \| P_{\theta'}) \leq \epsilon^2$ if and only if $\|\theta - \theta\|_2 \leq \epsilon' := \sigma\sqrt{\log (1 + \epsilon^2)}$. Therefore, by a standard volumetric argument, we have
  \begin{eqnarray*}
    M_{\chi^2}(\epsilon, \Theta) \leq \left(\frac{\Gamma+\epsilon'/2}{\epsilon'/2}\right)^d \leq \left(\frac{3\Gamma}{\epsilon'}\right)^d = \left( \frac{3 \Gamma }{ \sigma \sqrt{\log(1+\epsilon^2)}}\right)^d
  \end{eqnarray*}
provided $\epsilon' \leq \Gamma$. In particular, if we take $\epsilon := \sqrt{e^d - 1}$, then $\epsilon' = \sigma \sqrt{d} \leq \Gamma$, we will obtain $M_{\chi^2}(\epsilon, \Theta) \leq (3 \Gamma/(\sigma \sqrt{d}))^d$. Inequality~\eqref{eq:chi_dist_upper_1} then gives
$
  I_{\chi^2}(w, {\mathcal{P}}) \leq \left( \frac{3 e \Gamma }{ \sigma \sqrt{d}}\right)^d-1.
$
Let $I_f^{\rm up}$ be the right hand side. If we choose $t = c d \sigma^2$ for a sufficiently small constant $c > 0$, then we have $ \sup_{a \in {\mathcal{A}}} w(B_t(a, L)) < \frac{1}{4} (1 + I_f^{\rm up})^{-1}$. Inequality~\eqref{eq:I_bayes_chi} then gives
\begin{equation}\label{kolo}
R_{\rm Bayes}(w, L; \Theta) \geq c d \sigma^2.
\end{equation}
This lower bound is tight due to the trivial upper bound $R_{\rm Bayes}(w, L; \Theta) \leq d \min(\sigma^2, \Gamma^2)$ since $R_{\rm Bayes}(w, L; \Theta)$  is smaller than the risk of the constant estimator 0 as well as the trivial estimator of the observation itself.

This example allows us to compare the bound given by Theorem \ref{bwl} for different $f \in {\mathcal{C}}$.  We argue below that using KL divergence and applying \eqref{eq:I_bayes_KL}  along with inequality~\eqref{yb} for controlling the mutual information will not yield a tight lower bound for this example.
In other words, the same strategy that works for $f(x) = x^2 - 1$ does not work for $f(x) = x \log x$. To see this, notice that $D(P_{\theta}\|P_{\theta'}) = \|\theta - \theta'\|^2/\sigma^2$ for $\theta, \theta' \in \Theta$. As a result, $D(P_{\theta} \| P_{\theta'}) \leq \epsilon^2$ if and only if $\|\theta - \theta'\| \leq \sqrt{2} \epsilon \sigma$. The same volumetric argument again gives
$
  M_{KL}(\epsilon, \Theta) \leq \left(\frac{3 \Gamma}{\sqrt{2} \epsilon \sigma} \right)^d
$ provided  $\sqrt{2} \epsilon \sigma \leq \Gamma$.
The bound~\eqref{yb} implies that the mutual information $I(w, {\mathcal{P}})$ is bounded by
\begin{equation*}
  I(w, {\mathcal{P}}) \leq \inf_{0 < \epsilon \leq \Gamma/(\sqrt{2} \epsilon \sigma)} \left(d \log \left(\frac{3  \Gamma}{\sqrt{2} \epsilon \sigma}  \right) + \epsilon^2 \right) = d \log \left(\frac{3 \Gamma}{\sigma \sqrt{d}} \right) + \frac{d}{2}.
\end{equation*}
Let $I_f^{\rm up}$ be the right hand side above. The maximum $t > 0$ for which $(\sqrt{t}/\Gamma)^d < \frac{1}{4} \exp \left(-2I_f^{\rm up} \right)$ is on the order of $d^2 \sigma^4/\Gamma^2$. This means that inequality~\eqref{eq:I_bayes_KL} implies a weaker lower bound $\Omega(d^2 \sigma^4/\Gamma^2)$, which is suboptimal when $d \sigma^2$ is small or when $\Gamma$ is large. This is in contrast with the optimal bound~\eqref{kolo}.
\end{example}
In the above example, a direct application of Theorem~\ref{bwl} with $f(x) = x \log x$ does not produce a tight lower bound. This is mainly because, when the prior is over a large parameter space (e.g., a ball of a constant radius), the upper bound of mutual information over the entire parameter space $\Theta$ in \eqref{yb} could be too loose.
This can be corrected by partitioning the parameter space $\Theta$ into small hypercubes, and applying our bounds for the prior restricted to each hypercube separately  so that the mutual information inside the partition can be appropriately upper bounded using \eqref{yb}. This is another illustration of the idea described in Remark \ref{rem:Bayes_decomp}. We first describe this method in a more general setting in the following corollary and then apply it to the setting of Example \ref{tutu}. We use the  following notation. For measurable subsets $S$ of a Euclidean space, $\text{Vol}(S)$ denotes the volume (Lebesgue measure) of $S$.

\begin{corollary}\label{nd}
Let $\Theta=\mathcal{A} \subseteq \mathbb{R}^d$. Suppose that the prior $w$ has a Lebesgue density $f_w$ that is positive over $\Theta$. For each $\theta \in \Theta$ and $\delta>0$, let
\begin{equation*}
  r_{\delta}(\theta) := \sup \left\{ \frac{f_w(\theta_1)}{f_w(\theta_2)} : \theta_i \in \Theta \text{ and } \|\theta_i - \theta\|_2 \leq \sqrt{d} \delta \text{ for } i = 1, 2 \right\}.
\end{equation*}
Suppose also the existence of $A > 0$ such that $D(P_{\theta_1} \| P_{\theta_2}) \leq A  \|\theta_1 - \theta_2\|_2^2$  for all $\theta_1, \theta_2 \in\Theta$ and the existence of $V > 0$ (which may depend on $d$) and $p > 0$ such that $\sup_{a \in {\mathcal{A}}} \mathrm{Vol} (B_t(a, L)) \leq V t^{d/p}$ for every $t > 0$. Then
     \begin{equation}
           R_{\rm Bayes}(w, L; \Theta)  \geq \frac{1}{2} \sup_{0 < \delta \leq A^{-1/2}} \left[e^{-2p}  \delta^p  (8V)^{-p/d} \int_{\Theta} \left(\frac{1}{r_{\delta}(\theta)}\right)^{p/d}  w(\mathrm{d}\theta) \right].
           \label{eq:R_bayes_fano}
     \end{equation}
     \label{cor:KL_bayes_lower}
\end{corollary}

We demonstrate below that this corollary yields the correct rate in Example~\ref{tutu}. More examples are given in Section \ref{sec:Bayes_Example} of the appendix.

\begin{example}[Gaussian model with uniform priors on large balls (continued)] \label{tutug}
  Consider the same setting as in Example~\ref{tutu}. Because $D(P_{\theta}\|P_{\theta'}) = \|\theta - \theta'\|_2^2/(2 \sigma^2)$, we can take $A = (2 \sigma^2)^{-1}$ in Corollary~\ref{nd}. Moreover, because $L(\theta, a) = \|\theta - a\|_2^2$, it is easy to see that $\sup_{a \in {\mathcal{A}}} \mathrm{Vol}(B_t(a, L)) \leq t^{d/2} \mathrm{Vol} (B)$ which means that we can take $p = 2$ and $V = \mathrm{Vol}(B)$ in Corollary~\ref{nd} where $B$ is the unit ball in ${\mathbb R}^d$. Finally, because $w$ is the uniform prior, we have  $r_{\delta}(\theta) = 1$ for all $\theta \in \Theta$. Corollary~\ref{nd} therefore gives
  \begin{equation*}
    R_{\rm Bayes}(w, L; \Theta) \geq \frac{1}{2} \sup_{0 < \delta \leq \sqrt{2} \sigma} \left(e^{-4} 8^{-2/d} \delta^2 \mathrm{Vol}(B)^{-2/d} \right).
  \end{equation*}
This matches the tight lower bound~\eqref{kolo} by noting that $\mathrm{Vol}(B)^{1/d} \asymp d^{-1/2}$.
\end{example}

\section{Admissibility of Least Squares Estimators under Convex Constraint} \label{sec:admis}
In this section, we shall use the results developed in this paper (specifically inequality \eqref{eq:I_bayes_chi} induced by chi-squared divergence in Corollary \ref{cor:bwl} and Theorem \ref{cd}) to yield a  simpler proof of an important  admissibility result due to \citet{Sourav14LS}. Let us briefly review the problem here.

Consider the problem of estimating a vector $\theta \in {\mathbb R}^n$ in squared Euclidean loss $L(\theta, a)=\|\theta-a\|_2^2$ from a single observation $X \sim N(\theta, I_n)$ under the constraint that $\theta \in \Theta \subseteq {\mathbb R}^n$. In our setting, we take $\Theta = {\mathcal{A}}$, $P_{\theta} := N(\theta, I_n)$ and ${\mathcal{P}} := \{P_{\theta} : \theta \in \Theta\}$. For different choices of $\Theta$, one gets special cases including (a) Isotonic regression where $\Theta := \{\theta \in R^n : \theta_1 \leq \dots \le \theta_n\}$, (b) convex regression where $\Theta := \{\theta \in {\mathbb R}^n : 2 \theta_i \leq \theta_{i-1} + \theta_{i+1}\}$ and (c)  constrained Lasso where $\Theta := \{X \beta : \beta \in \mathbb{R}^p, |\beta_1| + \dots + |\beta_p| \leq L\}$. Most shape constrained regression problems can also be viewed as special cases of this problem~\citep{meyer2000degrees}.

The most commonly used estimator in this setting is the Least Squares Estimator (LSE) defined as $\widehat{\theta}(X) := \mathop{\rm argmin}_{t \in \Theta} \|X - t\|_2^2$. As mentioned in the introduction, \citet{Sourav14LS} proved an optimality property for the LSE which holds for every $n \geq 1$ and every closed convex $\Theta \subseteq {\mathbb R}^n$. Before describing his result, let us first remark that $\widehat{\theta}(X)$ is neither minimax (even up to a universal multiplicative constant) nor admissible for all closed convex $\Theta$. A counterexample for minimaxity is $\Theta := \{\theta : \sum_{i=1}^{n-1} \theta_i^2 + n^{-1/2} \theta_n^2 \leq 1\}$ as  noted by \citet{zhang2013nearly}; a more elaborate counterexample is given in \citet{Sourav14LS}. A  counterexample for admissibility is $\Theta = {\mathbb R}^n$ where the James-Stein estimator dominates $\widehat{\theta}(X) = X$; see \citet{james1961estimation}. Chatterjee's theorem is described next. Recall the definition of $C$-admissability from  \eqref{cad}.
\begin{theorem}\citep{Sourav14LS}\label{jee}
There exists a universal constant $0 < C \leq 1$ (independent of $n$ and $\Theta$) such that for every $n \geq 1$ and closed  convex subset $\Theta \subseteq {\mathbb R}^n$, the least squares estimator $\widehat{\theta}(X)$ is  $C$-admissible.
\end{theorem}
The high-level idea of the proof of this theorem was sketched in the introduction.  Basically,  $C$-admissibility is implied by $C$-Bayes (see the definition in \eqref{eq:C_Bayes}) for every prior $w$ (which is allowed to depend on $n$ and $\Theta$); and to prove that $\widehat{\theta}(X)$ is $C$-Bayes with respect to $w$,  we only need to:
\begin{enumerate}
\item bound $\int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2w(\mathrm{d}\theta)$ from  above,
\item bound $R_{\rm Bayes}(w)$ from below
\end{enumerate}
and make sure that the two bounds differ only by the multiplicative factor $C$. Bayes risk lower bounds established in this paper (such as \eqref{eq:I_bayes_chi} in Corollary \ref{cor:bwl}) are directly applicable for carrying out the second step  above.
In the following, we shall simplify and shorten \citeauthor{Sourav14LS}'s proof by replacing his complicated bare hands approach for the second step with an argument involving Corollary \ref{cor:bwl}. Our proof of Theorem  \ref{jee} provides the explicit lower bound $10^{-8}$ for the constant $C$. On the other hand, the constant obtained from the proof in \cite{Sourav14LS} is smaller than $10^{-12}$ (though this is not explicitly stated in \cite{Sourav14LS}). We do not believe however that $10^{-8}$ is close to being an optimal value for $C$; finding the optimal constant probably requires  other techniques and we leave it to future work.

We describe our proof of Theorem \ref{jee} in Subsection \ref{pjee}. Prior to that, we  recall some relevant results from \cite{Sourav14LS} in Subsection \ref{prim}. These results are useful mainly for handling the first step above, i.e., bounding $\int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2w(\mathrm{d}\theta)$ from above.

\subsection{Preliminary results from \cite{Sourav14LS}} \label{prim}
We shall use the following results from \cite{Sourav14LS}:

\textbf{1)} The quantity $\|\widehat{\theta}(X) - \theta\|_2$ is concentrated around a deterministic quantity $t_{\theta}$ which is defined as follows:
  \begin{equation}\label{mde}
    t_{\theta} := \mathop{\rm argmax}_{t \geq 0} \left(m_{\theta}(t) - \frac{t^2}{2} \right),  \qquad m_{\theta}(t) := {\mathbb E}_{\theta} \sup_{\alpha \in \Theta: \|\alpha - \theta\|_2 \leq t} \left<X - \theta,  \alpha - \theta \right>.
  \end{equation}
The existence and uniqueness of $t_{\theta}$ and the precise form of the  concentration of $\|\widehat{\theta}(X) - \theta\|_2$ around $t_{\theta}$ can be found in \citet[Theorem 1.1]{Sourav14LS}. For our purposes, the following consequence of the concentration is adequate, which can be easily proved from \citet[Theorem 1.1]{Sourav14LS}:
\begin{equation}\label{1co}
  {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2 \leq 150 \max \left(1, t_{\theta}^2 \right).
\end{equation}

\textbf{2)} The risk function $\theta \mapsto {\mathbb E}_{\theta} \|\widehat{\theta}(X) \theta\|^2_2$ is smooth in the following sense:
  \begin{equation}\label{smor}
    {\mathbb E}_{\theta_1} \|\widehat{\theta}(X) - \theta_1\|_2^2 \leq 2 {\mathbb E}_{\theta_2} \|\widehat{\theta}(X) - \theta_2\|_2^2 + 8 \|\theta_1 - \theta_2\|_2^2
  \end{equation}
for all $\theta_1, \theta_2 \in \Theta$. This is a simple consequence of the triangle  inequality. Further, the quantity $t_{\theta}$ is  smooth in $\theta$ in the following sense:    if $\theta_1, \theta_2 \in \Theta$ are such  that  $\|\theta_1 -  \theta_2\|_2  \leq   t_{\theta_1}/24$, then
  \begin{equation}\label{smoo}
    \frac{11 t_{\theta_1}}{24} \leq t_{\theta_2} \leq \frac{50 t_{\theta_1}}{24}.
  \end{equation}
This is proved in \citet[Lemma 4.8]{Sourav14LS}.

\textbf{3)} Recall the definition of $m_{\theta}(t)$ in \eqref{mde}. For each fixed $\theta$, the map $t \mapsto m_{\theta}(t)$ is non-decreasing and concave. Further, for all $t \geq 0$  and  $\theta \in \Theta$, we have
  \begin{equation}\label{inc}
    m_{\theta}(t) \leq m_{\theta}(t_{\theta}) + t_{\theta}(t -
    t_{\theta}).
  \end{equation}
   This inequality follows almost directly from the definition \eqref{mde} of $m_{\theta}(t)$. A proof of this inequality can be found in \citet[inequality (12)]{Sourav14LS}.

The proof of Theorem \ref{jee} is given next. Due to space constraints, we provide a  sketch of the proof here and the full proof is given in Section \ref{sec:supp_admis}  the appendix.

\subsection{Proof Sketch of Theorem \ref{jee}}\label{pjee}
As mentioned earlier, the main step is the construction of an appropriate $w$ on $\Theta$. The idea here is to fix a specific $\theta^* \in \Theta$ and to choose $w$ to be a specific prior that is supported on the set
\begin{equation}\label{uri}
U(\theta^*): = \Theta \cap \{\theta \in {\mathbb R}^n : \|\theta - \theta^*\|_2 \leq \rho  t_{\theta^*}\}
\end{equation}
for a small enough constant $\rho$, where $t_{\theta^*}$ is defined in \eqref{mde}. Because of inequalities \eqref{1co}, \eqref{smor}  and \eqref{smoo}, it can then be shown that
\begin{equation}\label{alla}
  \int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2 w(d\theta) \leq C t_{\theta^*}^2
\end{equation}
for some universal constant $C$ (provided $\rho$ is chosen to be sufficiently small). To  complete the proof, we would only need to show the Bayes risk lower bound:
\begin{equation}\label{tosh}
  R_{\rm Bayes}(w) \geq c t^2_{\theta^*}
\end{equation}
for some universal positive constant $c$. We shall prove this for every closed convex set $\Theta$ provided $\theta^*$ and $w$ are properly chosen.

It makes sense here to work with two separate cases: the case when $\inf_{\theta \in \Theta}  t_{\theta} $ is strictly smaller than some constant (we will take this constant to be 85 for technical reasons) and the case when $\inf_{\theta \in \Theta} t_{\theta}$ is larger than $85$. The first case is the easier case. Here we will take $\theta^* \in \Theta$ to be such that $t_{\theta^*} \leq 85$. The required bound \eqref{tosh} will then be a parametric lower bound which we will prove by the simple Le Cam's two point lower bound ($w$ will be taken to be a uniform prior on $\{\theta^*, \theta_1\}$ for some suitably chosen $\theta_1 \in \Theta$). Please refer to Section \ref{sec:supp_admis} of the appendix for more details. We would like to remark that our proof of this easy case has been already much simpler than the original proof in \cite{Sourav14LS}.

Here we will provide the argument in the harder case when $\inf_{\theta \in \Theta} t_{\theta} \geq 85$ (in this case, the LSE $\widehat{\theta}(X)$ may not attain the parametric rate anywhere on $\Theta$). Suppose $\inf_{\theta \in \Theta} t_{\theta} \geq b := 85$ and let $\rho := 0.03$. We shall first specify the choices for $\theta^* \in \Theta$ and the prior $w$ supported on the set $U(\theta^*)$ in \eqref{uri}.  Let $\theta^*$ be chosen so that
\begin{equation}\label{cho}
  m_{\theta^*}(\rho t_{\theta^*}) \geq \sup_{\theta \in \Theta} m_{\theta}(\rho t_{\theta}) - 0.01
\end{equation}
where $m_{\theta}(\cdot)$ is defined in \eqref{mde}. Let $\Psi : {\mathbb R}^n \mapsto \Theta$ be any measurable mapping such that $\Psi(z)$ is a maximizer of $\left< z, \theta - \theta^* \right>$  as $\theta$ varies in $U(\theta^*)$. As in \cite{Sourav14LS}, the prior $w$ is set to be the   distribution of $\Psi(Z)$ for a standard Gaussian vector $Z$ in ${\mathbb R}^n$. Because of inequalities \eqref{1co} and \eqref{smor},
\begin{equation}\label{les}
  {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2 \leq 2 {\mathbb E}_{\theta^*} \|\widehat{\theta}(X) - \theta^*\|_2^2 + 8 \|\theta - \theta^*\|^2_2  \leq \left( 300 + 8 \rho^2 \right) t^2_{\theta^*}
\end{equation}
for all $\theta \in U(\theta^*)$. This implies \eqref{alla} with $C = 300 + 8 \rho^2$. To complete the proof, it remains therefore to prove the Bayes risk lower bound \eqref{tosh}.  This is the main part of the proof. We will use inequality \eqref{eq:I_bayes_chi} in Corollary \ref{cor:bwl} induced by chi-squared divergence.
Note that the prior $w$ is concentrated on the convex set $U(\theta^*)$, we can replace the supremum over $a \in \Theta$ in \eqref{eq:I_bayes_chi} by the supremum over $a \in U(\theta^*)$, which gives the lower bound
\begin{equation}\label{wf}
\frac{1}{2} \sup \left\{t > 0 : \sup_{a \in U(\theta^*)} w \{\theta \in \Theta:  \|\theta - a\|_2^2  \leq t\} < \frac{1}{4(1 + I_f^{\rm up})} \right\},
\end{equation}
where $I_f^{\rm up}$ is any upper bound on the chi-squared informativity $I_{\chi^2}(w, \mathcal{P})$.
To obtain  $I_f^{\rm up}$, we use the bound given by inequality \eqref{eq:upper_f_power} in Theorem \ref{cd} with $\alpha = 2$, $\Xi := \{0\}$ and $Q_0 := P_{\theta^*}$. This gives
\begin{equation*}
  I_{\chi^2}(w, \mathcal{P}) \leq \int_{\Theta} \chi^2(P_{\theta} \| P_{\theta^*}) dw(\theta) \leq \sup_{\theta \in U(\theta^*)} \chi^2(P_{\theta} \| P_{\theta^*}) \leq \exp \left(\rho^2 t^2_{\theta^*} \right) - 1.
\end{equation*}
The last inequality above follows from the expression $\chi^2(P_{\theta} \| P_{\theta^*}) = \exp(\|\theta - \theta^*\|_2^2)-1$ and the fact that $\|\theta - \theta^*\|_2 \leq \rho t_{\theta^*}$ for all $\theta \in U(\theta^*)$. We can therefore take $1 + I_f^{\rm up}$ to be $\exp(\rho^2 t^2_{\theta^*})$ in \eqref{wf} which gives the lower bound
\begin{equation}\label{neal}
\frac{1}{2} \sup \left\{t > 0 : \sup_{a \in U(\theta^*)} w \{\theta \in \Theta:  \|\theta - a\|_2^2 \leq t\} < \frac{1}{4} \exp(- \rho^2 t^2_{\theta^*}) \right\}.
\end{equation}
for $R_{\rm Bayes}(w)$. The main step now is to argue that the inequality
\begin{equation}\label{sta}
  \sup_{a \in U(\theta^*)} w \{\theta \in \Theta:  \|\theta - a\|_2^2 \leq t\} < \frac{1}{4} \exp(- \rho^2 t^2_{\theta^*})
\end{equation}
holds for $t := 0.01 \rho^2 t^2_{\theta^*}$. This will then imply \eqref{tosh} and complete the proof. The argument for \eqref{sta} is similar to that in the proof of \citet[Theorem 1.4]{Sourav14LS} but the constants involved are different. Please refer to the full proof in Section \ref{sec:supp_admis} of appendix for the details.

Inequalities \eqref{sta} and \eqref{neal} together imply that
\begin{equation}\label{sa1}
  R_{\rm Bayes}(w) \geq  \frac{0.01 \rho^2}{2}  t^2_{\theta^*}
\end{equation}
On the other hand, for the LSE $\widehat{\theta}(X)$, inequality \eqref{les} gives
\begin{equation}\label{sa2}
  \int {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta \|_2^2 dw(\theta) \leq (300 + 8 \rho^2) t^2_{\theta^*}.
\end{equation}
Putting together \eqref{sa1} and \eqref{sa2}, we obtain
\[
\frac{0.01 \rho^2}{600 + 16 \rho^2} \int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) -  \theta\|_2^2 dw(\theta) \leq R_{\rm Bayes}(w).
\]
The constant above is at least $10^{-8}$ which proves that $\widehat{\theta}(X)$ is $C$-Bayes for some $C \geq 10^{-8}$. This completes the proof of Theorem \ref{jee}.

\section*{Acknowledgements}
The authors are very grateful to the anonymous referees and the associate editor for their detailed
and constructive comments. The authors would like to thank Michael I. Jordan and Sivaraman Balakrishnan for helpful discussions.

\section{Appendix}

\subsection{Proofs and Additional Results for for Section \ref{sec:Bayes_01} on Bayes Risk Lower Bound for Zero-one Loss}

\subsubsection{Proof of Lemma~\ref{lem:lower_property}}
Recall the expression \eqref{eq:phi} of $\phi_f(a, b)$. We first fix
$b$ and show that $g(a): a \mapsto \phi_f(a,b)$ is a
non-increasing for $a \in  [0, b]$. There is nothing to prove if $b =
0$ so let us assume that $b > 0$. We will consider the cases $0 < b <
1$ and $b = 1$ separately. For $0 < b < 1$, note that for every $a \in (0, b]$, we
have,
\begin{equation*}
  g_L'(a) = f_L' \left(\frac{a}{b} \right) - f_R' \left(\frac{1 -
      a}{1 -b} \right),
\end{equation*}
where $g_L'$ and $f_L'$ represent left derivatives and $f_R'$
represents right derivative (note that $f_L'$ and $f_R'$ exist because
of the convexity of $f$). Because $\frac{a}{b} \leq \frac{1-a}{1-b}$ for
every $0 \leq a \leq b$ and $f$ is convex, we see that
$$ g_L'(a) \leq  f_R' \left(\frac{a}{b} \right) -f_R' \left(\frac{1 -
      a}{1 - b} \right) \leq 0$$ for every $a \in (0, b]$ which
  implies that $g(a)$ is non-increasing on $[0, b]$.

When $b = 1$, we have $g_{L}'(a) = f_L'(a) - f'(\infty)$ which is
always $\leq 0$ because $f$ is convex (note that $f'(\infty) = \lim_{x
\uparrow \infty} f(x)/x = \lim_{x \uparrow \infty} (f(x) - f(1))/(x -
1)$).

The convexity and continuity of $g$ follow from the convexity of
$f$ and the expression for $\phi_f$.

Next, we fix $a$ and show that $h(b): b \mapsto \phi_f(a,b)$ is
non-decreasing for $b \in  [a, 1]$. For every $b \in [a, 1)$, we have,
\begin{equation}
  h_R'(b) = f\left( \frac{a}{b} \right) - \frac{a}{b} f'_L\left(\frac{a}{b} \right)-f\left(\frac{1-a}{1-b} \right) + \frac{1-a}{1-b} f'_R\left(\frac{1-a}{1-b} \right),
  \label{eq:h_R}
\end{equation}
where $h_R'$ represents the right derivative of $h$. By the convexity of $f$,
\begin{equation}
  \label{eq:h_R_1}
  f\left( \frac{a}{b} \right) -f\left(\frac{1-a}{1-b} \right) \geq f_R' \left(\frac{1-a}{1-b} \right)  \left(\frac{a}{b} - \frac{1-a}{1-b} \right).
\end{equation}
Combining \eqref{eq:h_R} with \eqref{eq:h_R_1}, we obtain that,
\begin{equation*}
h_R'(b) \geq \frac{a}{b} \left(f_R' \left(\frac{1-a}{1-b} \right)- f'_L\left(\frac{a}{b} \right) \right) \geq \frac{a}{b} \left(f_L' \left(\frac{1-a}{1-b} \right)- f'_L\left(\frac{a}{b} \right) \right) \geq 0,
\end{equation*}
where the last inequality is because that $\frac{a}{b} \leq \frac{1-a}{1-b}$ for every $0 \leq a \leq b$ and $f$ is convex. The non-negativity of $h_R'(b)$ implies that $h(b)$ is non-decreasing on $[a, 1]$.

\subsubsection{Proof of Lemma \ref{lem.dpi}}

\begin{proof}[Proof of Lemma \ref{lem.dpi}]
Let $\P$ denote the joint distribution of $\theta$ and $X$ under the prior $w$ i.e.,
$\theta \sim w$ and $X|\theta \sim P_{\theta}$. For any decision rule ${\mathfrak{d}}$, $R^{{\mathfrak{d}}}$ in \eqref{eq:def_R_Q} can be written as $R^{{\mathfrak{d}}} = {\mathbb E}_{\P} L(\theta,{\mathfrak{d}}(X))$. Let ${\mathbb Q}$ denote the joint distribution of $\theta$ and $X$ under which they are independently distributed according to $\theta \sim w$ and $X \sim Q$ respectively. The quantity $R_Q^{{\mathfrak{d}}}$ in \eqref{eq:def_R_Q} can then be written as $R_Q^{{\mathfrak{d}}}={\mathbb E}_{\mathbb Q} L\left(\theta,  {\mathfrak{d}}(X)\right)$.

Because the loss function is zero-one valued, the function $\Gamma
(\theta, x) :=  L(\theta, {\mathfrak{d}}(x))$ maps $\Theta \times {\mathcal{X}}$
into $\{0, 1\}$. Our strategy is to fix $f \in {\mathcal{C}}$ and apply the data processing inequality~\eqref{dpi} to the probability measures $\P, {\mathbb Q}$ and the mapping $\Gamma$. This gives
\begin{equation}\label{dp}
  D_f(\P||{\mathbb Q}) \geq D_f(\P\Gamma^{-1}||{\mathbb Q} \Gamma^{-1}),
\end{equation}
where $\P\Gamma^{-1}$ and ${\mathbb Q} \Gamma^{-1}$ are induced measures on the space $\{0,1\}$ of $\Gamma$. In other words, since $L$ is zero-one valued, both $\P\Gamma^{-1}$ and ${\mathbb Q} \Gamma^{-1}$ are two-point distributions on $\{0,1\}$ with
\begin{equation*}
  \P \Gamma^{-1} \{1\} = \int \Gamma d\P = {\mathbb E}_{\P} L(\theta,
  {\mathfrak{d}}(X)) = R^{{\mathfrak{d}}}, \qquad {\mathbb Q}\Gamma^{-1}\{1\}= \int \Gamma d{\mathbb Q}= R_Q^{{\mathfrak{d}}}.
\end{equation*}
By the definition of the function $\phi_f(\cdot, \cdot)$, it follows that $D_f(\P\Gamma^{-1}||{\mathbb Q} \Gamma^{-1}) = \phi_f (R^{{\mathfrak{d}}}, R_Q^{{\mathfrak{d}}})$. It is also easy to see  $D_f(\P||{\mathbb Q}) = \int_{\Theta} D_f(P_{\theta}||Q) w(\mathrm{d}\theta)$. Combining this equation with inequality~\eqref{dp} establishes inequality~\eqref{main.eq1}.
\end{proof}

\subsubsection{Proof of Theorem \ref{man}}
\label{sec:proof_man}

\begin{proof}[Proof of Theorem \ref{man}]
We write $R$ as a shorthand notation of $R_{\rm Bayes}(w)$. By the definition \eqref{eq:def_f_info} of $I_f(w, {\mathcal{P}})$, it suffices to prove that
\begin{equation}\label{jia}
  \int D_f(P_{\theta} \| Q) w(d\theta) \geq \phi_f(R, R_0)
\end{equation}
for every probability measure $Q$.

Notice that $R \leq  R_0$. If $R = R_0$, then the right hand side of \eqref{man.eq} is zero and hence the inequality immediately holds. Assume that $R < R_0$. Let $\epsilon > 0$ be small enough so that $R + \epsilon < R_0$. Let ${\mathfrak{d}}$ denote any decision rule for which  $R \leq R^{{\mathfrak{d}}} < R+\epsilon$ and note that such a rule exists since $R=\inf_{{\mathfrak{d}}} R^{{\mathfrak{d}}}$. It is easy to see that
  \begin{equation*}
    R_Q^{{\mathfrak{d}}} = \int_{{\mathcal{X}}} \int_{\Theta} L(\theta, {\mathfrak{d}}(x))
    w(\mathrm{d}\theta) Q(dx) \geq \int_{{\mathcal{X}}}\left( \inf_{a \in {\mathcal{A}}} \int_{\Theta }L(\theta, a)
    w(\mathrm{d}\theta) \right) Q(dx) = R_0.
  \end{equation*}
  We thus have $R \leq R^{{\mathfrak{d}}} < R + \epsilon < R_0 \leq R_Q^{{\mathfrak{d}}}$. By Lemma  \ref{lem.dpi}, we have
  \begin{equation*}
    \int_{\Theta} D_f(P_{\theta} \| Q) w(\mathrm{d}\theta) \geq \phi_f(R^{{\mathfrak{d}}},
    R_Q^{{\mathfrak{d}}}).
  \end{equation*}
Because $x \mapsto \phi_f(x, R_{Q}^{{\mathfrak{d}}})$ is non-increasing on $x \in
[0, R_Q^{{\mathfrak{d}}}]$, we have
\begin{equation*}
  \phi_f(R^{{\mathfrak{d}}}, R_Q^{{\mathfrak{d}}}) \geq \phi_f(R + \epsilon, R_Q^{{\mathfrak{d}}}).
\end{equation*}
Because $x \mapsto \phi_f(R + \epsilon, x)$ is non-decreasing
on $x \in [R + \epsilon, 1]$, we have
\begin{equation*}
  \phi_f(R + \epsilon, R_Q^{{\mathfrak{d}}}) \geq \phi_f(R + \epsilon, R_0).
\end{equation*}
Combining the above three inequalities, we have
\begin{equation*}
  \int_{\Theta} D_f(P_{\theta} \| Q) w(d\theta) \geq \phi_f(R^{{\mathfrak{d}}},
    R_Q^{{\mathfrak{d}}}) \geq \phi_f(R + \epsilon, R_Q^{{\mathfrak{d}}}) \geq \phi_f(R + \epsilon, R_0).
\end{equation*}
The proof of \eqref{jia} completes by letting $\epsilon \downarrow 0$ and  using the continuity of $\phi_f(\cdot, R_0)$ (continuity was noted in Lemma  \ref{lem:lower_property}). This completes the proof of Theorem \ref{man}.
\end{proof}

\subsubsection{Proof of Corollary \ref{cor:Fano}}
\label{sec:proof_fano}

\begin{proof}[Proof of Corollary \ref{cor:Fano}]
We simply apply \eqref{expb} to $f(x) = x \log x$ and $r = R_0/(1 + R_0)$, it can then be checked that
\[
\phi_f(r, R_0)= - \log (1+R_0) - \frac{1}{1+R_0} \log(1-R_0), \quad \phi_f'(r-, R_0)= \log (1-R_0),
\]
Inequality \eqref{expb} then gives
\begin{equation*}\label{eq:Fano1}
  R \geq 1 + \frac{I(w, {\mathcal{P}}) + \log (1 + R_0)}{\log (1 - R_0)}
\end{equation*}
which proves \eqref{gf}.
\end{proof}

\subsubsection{A variant of Fano's inequality from \cite{BraunPokutta}}
\label{sec:supp_Fano}
One of the main results in \cite{BraunPokutta} (Proposition 2.2)
establishes the following variant of Fano's inequality. Consider the
setting of Lemma \ref{lem.dpi}. In particular, recall the quantities
$R^{{\mathfrak{d}}}$ and $R_Q^{{\mathfrak{d}}}$ from \eqref{eq:def_R_Q} and also the sets
$B(a), a \in {\mathcal{A}}$ from \eqref{ba}. \cite[Proposition
2.2]{BraunPokutta} proved the following: for any decision rule ${\mathfrak{d}}$,
\begin{equation}\label{bp}
  R^{{\mathfrak{d}}} \geq \frac{-I(w, \mathcal{P}) - H(R^{{\mathfrak{d}}}) - \log w_{\max}}{\log \left[ (1 - w_{\min})/w_{\max} \right]},
\end{equation}
where $H(x) := -x \log x - (1-x) \log(1-x)$, $w_{\min} := \inf_{a \in
  {\mathcal{A}}} w(B(a))$ and $w_{\max} := \sup_{a \in  {\mathcal{A}}} w(B(a))$.

Below we provide a proof of this inequality using Lemma
\ref{lem.dpi}. The proof given in \cite{BraunPokutta} is quite
different proof. Using \eqref{main.eq1} from Lemma \ref{lem.dpi} with
$f(x)= x \log x$, we have for any decision rule
\begin{equation*}
  \int_{\Theta} D_f(P_{\theta} \| Q) w(d\theta) \geq R^{{\mathfrak{d}}} \log
  \frac{R^{{\mathfrak{d}}}}{R_Q^{{\mathfrak{d}}}} + (1 - R^{{\mathfrak{d}}}) \log \frac{1 - R^{{\mathfrak{d}}}}{1
    - R_Q^{{\mathfrak{d}}}}.
\end{equation*}
We can rewrite this as
\begin{equation}\label{eq:Braun}
  \int_{\Theta} D_f(P_{\theta} \| Q) w(d\theta) \geq -H(R^{{\mathfrak{d}}}) -
  R^{{\mathfrak{d}}} \log R_Q^{{\mathfrak{d}}} - (1 - R^{{\mathfrak{d}}}) \log(1 - R_Q^{{\mathfrak{d}}})
\end{equation}
where $H(x) := -x \log x - (1-x) \log(1-x)$. Since $L$ in Lemma
\ref{lem.dpi} is zero-one valued.
\begin{equation}
  R_Q^{{\mathfrak{d}}} =1- {\mathbb E}_{Q} w(B({\mathfrak{d}}(X)))
  \label{eq:R_Q}
\end{equation}
where ${\mathbb E}_Q$ denotes expectation taken under $X \sim Q$ and and
$B({\mathfrak{d}}(X))$ is defined in \eqref{ba}.
As a result, we have
\begin{equation}\label{qb}
 1- \max_{a \in {\mathcal{A}}} w(B(a)) \leq R_Q^{{\mathfrak{d}}} \leq 1- \min_{a \in {\mathcal{A}}} w(B(a)).
\end{equation}
Using the bounds in~\eqref{qb} on the right hand side of \eqref{eq:Braun}, we deduce
\begin{equation*}
  \int_{\Theta} D_f(P_{\theta} \| Q) w(d\theta) \geq -H(R^{{\mathfrak{d}}}) - R^{{\mathfrak{d}}} \log \left(1 - w_{\min} \right) - (1 - R^{{\mathfrak{d}}})  \log w_{\max}.
\end{equation*}
where $w_{\min} := \inf_{a \in {\mathcal{A}}} w(B(a))$ and $w_{\max} := \sup_{a \in  {\mathcal{A}}} w(B(a))$ for notational simplicity.
Taking the infimum on the left hand side above over all probability measures $Q$, we obtain
\begin{equation*}
 I(w, \mathcal{P}) \geq -H(R^{{\mathfrak{d}}}) - R^{{\mathfrak{d}}} \log \left(1 - w_{\min} \right) - (1 - R^{{\mathfrak{d}}})  \log \left( w_{\max} \right).
\end{equation*}
Provided $w_{\min} + w_{\max} < 1$, one can rewrite the above
inequality as \eqref{bp}. This completes the proof of \eqref{bp}.

\subsubsection{Proof of Corollary \ref{cor:lb_01_f}}\label{colr}
\label{sec:cor_lb_01_f}

\begin{enumerate}
    \item \textbf{Proof of inequality \eqref{eq:chi}}: Applying
      Theorem \ref{man} with $f(x) = x^2 - 1$, we obtain
    \begin{equation*}
    I_{\chi^2}(w, {\mathcal{P}}) \geq \frac{(R_0-R)^2}{R_0(1-R_0)}
    \end{equation*}
    Because $R \leq R_0$, we can invert the above to obtain
    \eqref{eq:chi}.

  \item \textbf{Proof of inequality \eqref{eq:total}}:
    Theorem~\ref{man} with $f(x) = |x - 1|/2$ gives
    \begin{equation*}
     I_{TV}(w, {\mathcal{P}}) \geq  \frac{R_0}{2} \left|\frac{R}{R_0} -1 \right|  + \frac{1-R_0}{2} \left|\frac{1-R}{1-R_0} -1 \right| =R_0-R,
    \end{equation*}
    where the last equality uses the fact that $R \leq R_0$. Inverting
    the above inequality, we obtain \eqref{eq:total}.

  \item \textbf{Proof of inequality \eqref{eq:hellinger_3}}:
   Theorem \ref{man} with $f(x) = f_{1/2}(x) = 1 - \sqrt{x}$ gives
   \begin{equation}\label{enim}
     I_{f_{1/2}}(w, {\mathcal{P}}) \geq 1 - \sqrt{R R_0} - \sqrt{(1 - R)(1 -
       R_0)}.
   \end{equation}
  Assume that $P_{\theta}$ has density $p_{\theta}$ with respect to a
  common dominating measure $\mu$. We shall show below that
  \begin{equation}\label{exha}
    I_{f_{1/2}}(w, {\mathcal{P}}) = 1 - \sqrt{\int_{{\mathcal{X}}} u^2 d\mu} \qt{where
      $u := \int_{\Theta} \sqrt{p_{\theta}} w(d\theta)$. }
  \end{equation}
  To see this, fix a probability measure $Q$ that has a density $q$
  with respect to $\mu$. We can then write
  \begin{equation*}
    \int_{\Theta} D_{f_{1/2}} (P_{\theta} \| Q) w(d\theta) = 1 -
    \int_{{\mathcal{X}}} \sqrt{q} \left( \int_{\Theta} \sqrt{p_{\theta}}
      w(d\theta) \right) d\mu = 1 - \int_{{\mathcal{X}}} \sqrt{q u^2} d\mu
  \end{equation*}
  It follows then from the Cauchy-Schwarz inequality that
\begin{equation*}
  \int_{\Theta} D_{f_{1/2}}(P_{\theta}||Q) w(\mathrm{d}\theta)=1-\int_{{\mathcal{X}}} \sqrt{q u^2}\;\mathrm{d}\mu \geq 1- \sqrt{\int_{{\mathcal{X}}} u^2 \; \mathrm{d} \mu},
\end{equation*}
with equality holding when $q$ is proportional to $u^2$. This proves
\eqref{exha}. We now see that
\begin{align}
\label{eq:hellinger_2}
 \int_{{\mathcal{X}}} u^2 \; \mathrm{d} \mu & =\int_{\Theta} \int_{\Theta} \int_{{\mathcal{X}}} \sqrt{p_{\theta}} \sqrt{p_{\theta'}} \; \mathrm{d}\mu~ w(\mathrm{d} \theta) w(\mathrm{d} \theta')  = 1- \frac{1}{2} h^2
\end{align}
where $h^2$ is defined as
      \begin{equation}\label{eq:h_square}
        h^2=\int_{\Theta} \int_{\Theta}  H^2(P_{\theta}\| P_{\theta'})  w(\mathrm{d} \theta)w(\mathrm{d} \theta').
        \end{equation}
This, together with
\eqref{enim} and \eqref{exha}, gives the inequality
\begin{equation}\label{eq:hellinger_1}
  \sqrt{R R_0} + \sqrt{(1 - R) (1 - R_0)} \geq \sqrt{1 - \frac{h^2}{2}}
\end{equation}
Now under the assumption $h^2 \leq 2 R_0$, the right hand side of the
inequality \eqref{eq:hellinger_1} lies between $\sqrt{1-R_0}$ and
$1$. On the other hand, it can be checked that, as a function in $R$,
the left hand side of \eqref{eq:hellinger_1} is strictly increasing
from $\sqrt{1-R_0}$ (at $R=0$) to 1 at ($R=R_0$).  Therefore, from
\eqref{eq:hellinger_1}, we know that $R \geq \widehat{R}$ where
$\widehat{R} \in [0, R_0]$ is the solution to the equation
obtained by replacing the inequality \eqref{eq:hellinger_1} with an
equality. One can solve this equation and obtain two solutions. One of
two solutions can be discarded by the fact that $R \leq R_0$.
The other solution is given by:
\begin{equation*}
  \widehat{R} = R_0-(2R_0-1) \frac{h^2}{2} - \sqrt{R_0(1-R_0)} \sqrt{h^2(2-h^2)}
\end{equation*}
and thus we have $R \geq \widehat{R}$ which proves inequality
\eqref{eq:hellinger_3}.

We note that the lower bound on $R$ in \eqref{eq:hellinger_3} only
holds under the condition $h^2  \leq 2 R_0$.  When $h^2 > 2 R_0$,
inequality \eqref{eq:hellinger_3} holds for every $R \in [0, R_{Q^*}]$
and thus cannot provide a non-trivial lower bound on $R$. As an
example, when $\Theta = {\mathcal{A}} = \{1, \dots, N\}$, $L(\theta, a) =
\mathbbm{I}\{\theta \neq a\}$ and $w$ is the uniform prior on
$\Theta$, it is easy to see that $R_0 = 1 - (1/N)$ and
\begin{equation}
  h^2= \frac{1}{N^2} \sum_{\theta \neq \theta'} H^2(P_{\theta}\|
  P_{\theta'}) \leq 2 \frac{N(N-1)}{N^2} =2 R_{Q^*}.
\end{equation}
Inequality~\eqref{eq:hellinger_3} therefore is equivalent to
\begin{equation*}
    R \geq 1- \frac{1}{N} -\frac{N-2}{N} \frac{h^2}{2}-
    \frac{\sqrt{N-1}}{N} \sqrt{h^2(2-h^2)}.
\end{equation*}
This recovers the result in Example \RNum{2}.6 in \cite{Aditya:fdiv}.
\end{enumerate}

\subsubsection{Derivations of Le Cam's inequality (two hypotheses) and Assouad's lemma and other results from Corollary \ref{cor:lb_01_f}}
\label{sec:supp_LeCam}

To demonstrate the application of Corollary \ref{cor:lb_01_f}, we apply it to derive the two hypotheses version of Le Cam's inequality (with total variation distance) and Assouad's lemma (see Theorem 2.12 in \citep{Tsybakov:nonpara}).

The simplest version of the Le Cam's inequality, the so-called two-point argument, is an easy corollary of~\eqref{eq:total}. Indeed, applying~\eqref{eq:total} with $\Theta = {\mathcal{A}} = \{\theta_0, \theta_1\}$, $L(\theta, a) = \mathbbm{I}\{\theta \neq a\}$ and $w\{0\} = w\{1\} = 1/2$ (and note that $R_0=1/2$), we obtain that for any distribution $Q$ on $\mathcal{X}$,
\begin{equation*}
  \frac{1}{2} \left(\|P_{\theta_0} - Q\|_{TV} + \|P_{\theta_1} - Q\|_{TV} \right) \geq I_{TV}(w, \mathcal{P}) \geq 1/2 - R
\end{equation*}
Taking $Q = (P_{\theta_0} + P_{\theta_1})/2$, we obtain Le Cam's inequality:
\begin{equation}\label{eq:LeCam}
  R_{\rm minimax} \geq \frac{1}{2} \left(1 - \|P_{\theta_0} - P_{\theta_1}\|_{TV} \right).
\end{equation}
The more involved Le Cam's inequality considers $\Theta = {\mathcal{A}} = \Theta_0 \cup \Theta_1$ for two disjoint subsets $\Theta_0$ and $\Theta_1$ and loss function $L(\theta, a) = \mathbbm{I} \{\theta \in \Theta_1, a \in \Theta_2\} + \mathbbm{I}\{\theta \in \Theta_2, a \in \Theta_1\}$. The inequality states that for every pair of probability measures $w_0$ and $w_1$ concentrated on $\Theta_0$ and $\Theta_1$ respectively,
\begin{equation}\label{eq:LeCam_set}
  R_{\rm minimax} \geq \frac{1}{2} \left(1 - \|m_0 - m_1\|_{TV} \right)
\end{equation}
where $m_{0}$ and $m_1$ are marginal densities given by $m_{\tau}(x) = \int p_{\theta}(x) w_{\tau}(\mathrm{d}\theta)$ for $\tau = 0, 1$. To prove~\eqref{eq:LeCam_set}, consider the prior $w = (w_0 + w_1)/2$. Under this prior, the problem is easily converted to the previous binary testing problem.  In particular, the data generating process under the prior $w$ can be viewed as first sampling $\tau \sim \mathrm{Uniform}\;\{0,1\}$ and then $X \sim m_{\tau}$. The decision $a \in \mathcal{A}$ can be converted into the binary decision $\hat{\tau}=\mathbbm{I}(a \in \Theta_1)$. The loss function is $L(\tau, \hat{\tau}) = \mathbbm{I}(\tau \neq \hat{\tau}) $. The Bayes risk under the prior $w$ can be re-written as,
\begin{equation}
  R_{\rm Bayes}(w, L; \Theta)  = \frac{1}{2} \inf_{\hat{\tau}} \sum_{\tau=0,1}  \int_{\mathcal{X}}   \mathbbm{I}(\tau \neq \hat{\tau}(x))  m_{\tau}(x)  \mu(\mathrm{d} x),
  \label{eq:LeCam_set_1}
\end{equation}
which has the same form as the Bayes risk in the earlier binary testing problem. Applying the same argument as for proving \eqref{eq:LeCam}, we obtain the lower bound on the Bayes risk in \eqref{eq:LeCam_set_1}, $R_{\rm Bayes}(w, L; \Theta) \geq \frac{1}{2} \left(1 - \|m_0 - m_1\|_{TV} \right)$, which further implies \eqref{eq:LeCam_set}.

Another classical minimax inequality involving the total variation distance is Assouad's inequality~\citep{Assouad:83} which states that if $\Theta = \mathcal{A} = \{0,1\}^d$ and the loss function $L$ is defined by the Hamming distance, i.e., $L(\theta, a) = \sum_{i=1}^d \mathbbm{I}(\theta_i \neq a_i)$, then
\begin{eqnarray}
  R_{\rm minimax} \geq \frac{d}{2} \min_{L(\theta, \theta')=1} \left(1-\|P_{\theta} - P_{\theta'}\|_{TV} \right).
  \label{eq:assouad}
\end{eqnarray}
This inequality is also a consequence of~\eqref{eq:total}: let $w$ be the uniform probability measure on $\Theta$ and $L_1(\theta, a)= \mathbbm{I}(\theta_1 \neq a_1)$. Under $w$, the marginal distribution of the first coordinate is $w_1\{0\} = w_1\{1\} = 1/2$. Let $m_\tau(x) :=\sum_{\theta: \theta_1=\tau} p_{\theta}(x)/2^{d-1}$  for $\tau \in \{0,1\}$ be the corresponding marginal density of $X$ and let $Q(x)= \frac{1}{2} \left( m_0(x)+m_1(x) \right)$. Applying the same argument as for proving \eqref{eq:LeCam}, we obtain that the minimax risk for the zero-one valued loss function $L_1(\theta, a)$ is bounded below by $\frac{1}{2} \left( 1- \|m_0 - m_1\|_{TV} \right) \geq \frac{1}{2} \min_{L(\theta, \theta')=1} \left(1-\|P_{\theta} - P_{\theta'}\|_{TV} \right)$. Repeating this argument for $L_i(\theta, a) := \mathbbm{I}\{\theta_i \neq a_i\}$ for $i = 2, \dots, d$ and adding up the resulting bounds, we obtain~\eqref{eq:assouad}.

By using Le Cam's inequality (see, e.g., Lemma 2.3 in \citep{Tsybakov:nonpara}) which states that:
\begin{equation*}
  \|P_{\theta} - P_{\theta'}\|_{TV} \leq \sqrt{H^2(P_{\theta} \| P_{\theta'}) \left(1 - \frac{1}{4} H^2(P_{\theta} \| P_{\theta'}) \right)},
\end{equation*}
the inequality in \eqref{eq:assouad} further implies the Hellinger distance version of Assouad's inequality in the book \citet[Theorem 2.12]{Tsybakov:nonpara}, i.e.,
\begin{equation}\label{eq:hell_assouad}
  R_{\rm minimax} \geq \frac{d}{2} \min_{L(\theta, \theta') = 1} \left\{1 - \sqrt{H^2(P_{\theta} \| P_{\theta'}) \left(1 - \frac{1}{4} H^2(P_{\theta} \| P_{\theta'}) \right)} \right\} .
\end{equation}

Finally, we also note that Corollary \ref{cor:Fano} (generalized Fano's inequality) and Corollary \ref{cor:lb_01_f} can also lead to Theorem 2.15 (slightly weaker version) in \cite{Tsybakov:nonpara} which involves two fuzzy hypotheses. Here, we only show the KL divergence version. The cases for other divergences are similar and quite straightforward. In particular, let $\mathbb{P}_{\theta_0}$ and $\mathbb{P}_{\theta_1}$ be  two fuzzy hypotheses. the key step of Theorem 2.15 in \cite{Tsybakov:nonpara} is to show that if $D(\mathbb{P}_{\theta_1} || \mathbb{P}_{\theta_0}) \leq \alpha$ for some $\alpha>0$, then
  \[
    \inf_{{\mathfrak{d}}} \frac{1}{2} \left( \mathbb{P}_{\theta_0}({\mathfrak{d}}=1) + \mathbb{P}_{\theta_1} ({\mathfrak{d}}=0) \right) \geq c(\alpha)>0,
  \]
  where ${\mathfrak{d}}$ is the decision rule maps from $\mathcal{X}$ to $\Theta={\mathcal{A}}=\{0,1\}$  and $c(\alpha)$ is some positive constant. Considering the uniform prior $w$ over $\Theta=\{0,1\}$ and using Corollary \ref{cor:Fano} (note that $R_0=1/2$ and $I(w, \mathcal{P}) \leq D(\mathbb{P}_{\theta_1} || \mathbb{P}_{\theta_0}) \leq \alpha$), we have the Bayes risk lower bound
  \[
  \inf_{{\mathfrak{d}}} \frac{1}{2} \left( \mathbb{P}_{\theta_0}({\mathfrak{d}}=1) + \mathbb{P}_{\theta_1} ({\mathfrak{d}}=0) \right) \geq \frac{\log(4/3)-\alpha/2}{\log(2)},
  \]
  which is a positive constant for any $\alpha < 2 \log(4/3)$. This result is spiritually similar to that of \cite{Tsybakov:nonpara}.

\subsubsection{Proof of Proposition  \ref{prop:Birge}}
\label{sec:supp_Birge}
We will provide a proof of Proposition \ref{prop:Birge} based on Lemma
\ref{lem.dpi}. For this, it is enought to prove that
$\frac{1}{N}\sum_{i:i \neq j} D_f(P_{\theta_i}||P_{\theta_j}) \geq
\psi_{N, f}(R_{\rm minimax})$ for every $j \in \{0, \dots,
N\}$. Without loss of generality, we assume that $j = 0$. We
apply~\eqref{main.eq1} with the uniform distribution on $\Theta
\setminus \{\theta_0\} = \{\theta_1, \dots, \theta_N\}$ as $w$, $Q =
P_{\theta_0}$ and the minimax rule for the problem as ${\mathfrak{d}}$. Because
${\mathfrak{d}}$ is the minimax rule, $R^{{\mathfrak{d}}} \leq R_{\rm minimax}$. Also
\begin{equation*}
  R_Q^{{\mathfrak{d}}} = \frac{1}{N} \sum_{i=1}^N {\mathbb E}_{\theta_0} L(\theta_i, {\mathfrak{d}}(X)) = \frac{1}{N}{\mathbb E}_{\theta_0}  \sum_{i=1}^N \mathbbm{I} \{\theta_i \neq {\mathfrak{d}}(X)\}.
\end{equation*}
It is easy to verify that $\sum_{i=1}^N \mathbbm{I} \{\theta_i \neq {\mathfrak{d}}(X)\} = N -\mathbbm{I} \{\theta_0 \neq {\mathfrak{d}}(X)\}$. We thus have $R_Q^{{\mathfrak{d}}} = 1 - {\mathbb E}_{\theta_0} L(\theta_0, {\mathfrak{d}}(X))/N$. Because ${\mathfrak{d}}$ is minimax, ${\mathbb E}_{\theta_0} L(\theta_0, {\mathfrak{d}}(X)) \leq R_{\rm minimax}$  and thus
\begin{equation}\label{dan}
R_Q^{{\mathfrak{d}}} \geq 1 - R_{\rm minimax}/N.
\end{equation}

On the other hand, we have $R_{\rm minimax} \leq N/(N+1)$. To see
this, note that the minimax risk is upper bounded by the maximum risk
of a random decision rule, which chooses among the $N+1$ hypotheses
uniformly  at random. For this random decision rule, its risk is
$\frac{N}{N+1}$ no matter what the true hypothesis is. Thus,
$\frac{N}{N+1}$ is an upper bound on the minimax risk. We thus have,
from~\eqref{dan}, that $R_Q^{{\mathfrak{d}}} \geq 1 -R_{\rm minimax}/N \geq
R_{\rm minimax}$. We can thus apply~\eqref{eq:ext_main.eq_1} to
obtain
\begin{equation*}
  \frac{1}{N} \sum_{i=1}^N D_f(P_{\theta_i}||P_{\theta_0}) \geq
  \phi_f(R_{\rm minimax}, 1 - R_{\rm minimax}/N).
\end{equation*}
The right hand side above equals $\psi_{N, f}(R_{\rm minimax})$,
completing the proof Proposition \ref{prop:Birge}.

\subsubsection{Reproduce Theorem 2.4. in \cite{Tsybakov:nonpara}}
\label{sec:likelihood}
In this subsection, we apply Proposition \ref{prop:Birge} to specific
choices of $f$ and derive many lower bounds in
\cite{Tsybakov:nonpara}. In particular, we derive Theorem 2.4 and its
corollaries (Proposition 2.3, Theorem 2.5, Theorem 2.6) in
\cite{Tsybakov:nonpara}.

Let us start with the derivation of Theorem 2.4 in
\cite{Tsybakov:nonpara}. First note that by the standard
reduction of minimax risk lower bound to the multiple hypothesis
testing problem (Eq. (2.9) in \cite{Tsybakov:nonpara}), Theorem 2.4 in
\cite{Tsybakov:nonpara} is equivalent to the following statement.
Suppose the parameter space $\Theta=\{\theta_0, \ldots, \theta_N\}$
with $N\geq 2$ and consider the indicator loss function
$L(\theta,a)=\mathbb{I}(\theta \neq a)$, if there exists $s \geq 1$
and $\alpha<1$ such that (assuming that $P_{\theta_0} \ll
P_{\theta_j}$)
  \begin{equation}\label{eq:like_assump}
     \frac{1}{N} \sum_{j=1}^N P_{\theta_j} \left( \frac{\mathrm{d} P_{\theta_0}}{\mathrm{d} P_{\theta_j}} \geq \frac{1}{s} \right) \geq 1-\alpha,
  \end{equation}
  then
  \begin{equation}\label{eq:Thm24_Tsy}
    R_{\rm minimax} \geq \frac{N}{s+N} (1-\alpha).
  \end{equation}
  Here, we note that we let $s=1/\tau$ where the $\tau$ is defined in Theorem 2.4 in \cite{Tsybakov:nonpara} for notational simplicity. We prove Theorem 2.4 in \cite{Tsybakov:nonpara} under a slightly different condition  (assuming that $P_{\theta_0} \ll P_{\theta_j}$ and $P_{\theta_j} \ll P_{\theta_0}$),
   \begin{equation}\label{eq:like_assump_2}
   \frac{1}{N} \sum_{j=1}^N
  P_{\theta_j} \left\{\frac{\mathrm{d} P_{\theta_0}}{\mathrm{d} P_{\theta_j}} \geq \frac{1}{s} \right\} +   \frac{s}{N} \sum_{j=1}^N
  P_{\theta_0} \left\{ \frac{\mathrm{d} P_{\theta_j}}{\mathrm{d}  P_{\theta_0}} > s\right\} \geq 1-\alpha,
   \end{equation}
   for some $s \geq 1-\alpha$. On one hand, \eqref{eq:like_assump_2} is weaker than \eqref{eq:like_assump} since there is an extra positive term $\frac{s}{N} \sum_{j=1}^N
  P_{\theta_0} \left\{ \frac{\mathrm{d} P_{\theta_j}}{\mathrm{d}  P_{\theta_0}} > s\right\}$ on the left hand side of \eqref{eq:like_assump_2}. On the other hand, the condition in \eqref{eq:like_assump_2} requires $s \geq 1$.
   Nevertheless, in all applications of Theorem 2.4 in \cite{Tsybakov:nonpara} (e.g., Proposition 2.3, Theorem 2.5, Theorem 2.6), they always have $s>1$ (see the proof of Proposition 2.3 in \cite{Tsybakov:nonpara}). Now, let us derive \eqref{eq:Thm24_Tsy} under the condition in \eqref{eq:like_assump_2}.  According to Proposition \ref{prop:Birge}, for every $f$ divergence, we have
    \begin{equation}\label{gush}
      \psi_{N,f}(R_{\rm minimax}) \leq \frac{1}{N} \sum_{j=1}^N D_f(P_{\theta_j} \| P_{\theta_0})
    \end{equation}
    where
    \begin{equation*}
      \psi_{N,f}(x) := \frac{N-x}{N} f \left(\frac{Nx}{N-x} \right) +
      \frac{x}{N} f \left(\frac{N(1 - x)}{x} \right).
    \end{equation*}
   To deduce Theorem 2.4 in \cite{Tsybakov:nonpara}, we would like to apply Proposition \ref{prop:Birge} with the $f$-divergence from the following $f$ function:
   \[
   f_s(x) := \min(1, s) -  \min(x, s)
   \]
   for a fixed $s > 0$. This corresponds to the $f$-divergence:
\begin{equation*}
  D_{f_s}(P\|Q) := \min(1, s) - \int \min(p, qs) \mathrm{d} \mu  = \min(1, s) - P
  \left\{\frac{\mathrm{d} Q}{\mathrm{d} P}
    \geq \frac{1}{s} \right\} - s Q \left\{\frac{\mathrm{d} P}{\mathrm{d} Q} > s \right\}.
\end{equation*}
With this choice of divergence and the definition of $\psi_{N,f}$, inequality \eqref{gush} becomes
\begin{multline*}
  \min(1, s) - \min \left(R_{\rm minimax}, s\;\frac{N-R_{\rm minimax}}{N} \right) - \min \left(1 -
    R_{\rm minimax}, \frac{R_{\rm minimax} s}{N} \right) \\
    \leq \min(1, s) - \frac{s}{N} \sum_{j=1}^N
  P_{\theta_0} \left\{ \frac{\mathrm{d} P_{\theta_j}}{\mathrm{d}  P_{\theta_0}} > s\right\}- \frac{1}{N} \sum_{j=1}^N
  P_{\theta_j} \left\{\frac{\mathrm{d} P_{\theta_0}}{\mathrm{d} P_{\theta_j}} \geq \frac{1}{s} \right\},
\end{multline*}
which is equivalent to
\begin{multline}\label{gut}
  \min \left(R_{\rm minimax}, s\;\frac{N-R_{\rm minimax}}{N} \right) + \min \left(1 -
    R_{\rm minimax}, \frac{R_{\rm minimax} s}{N} \right) \\
    \geq \underbrace{\frac{s}{N} \sum_{j=1}^N
  P_{\theta_0} \left\{ \frac{\mathrm{d} P_{\theta_j}}{\mathrm{d}  P_{\theta_0}} > s\right\} + \frac{1}{N} \sum_{j=1}^N
  P_{\theta_j} \left\{\frac{\mathrm{d} P_{\theta_0}}{\mathrm{d} P_{\theta_j}} \geq \frac{1}{s} \right\}}_{T}.
\end{multline}
Let us, for convenience, denote the right hand side above by
$T$ and from \eqref{eq:like_assump_2}, we have
\begin{equation}\label{eq:T_lower}
T \geq 1-\alpha.
\end{equation}
From the inequality \eqref{gut}, we shall now deduce that
\begin{equation}\label{ogu}
  R_{\rm minimax} \geq \frac{N}{N + s} \min (1, s, T).
\end{equation}
To prove this, we may assume that $R_{\rm minimax} <  N/(N+s) \min(1, s)$ for
otherwise \eqref{ogu} automatically holds. This assumption implies that $R_{\rm minimax} <
N/(N+s)$ and $R_{\rm minimax} < Ns/(N+s)$. It can now be checked that inequality
\eqref{gut} is the same as
\begin{equation*}
  R_{\rm minimax} + \frac{R_{\rm minimax}\;s}{N} \geq T
\end{equation*}
which is equivalent to $R_{\rm minimax} \geq \frac{N}{N+s} T$ that proves \eqref{ogu}.

It is easy to see now that inequality \eqref{ogu} implies \eqref{eq:Thm24_Tsy}. Indeed, when $s \geq 1-\alpha$,
\eqref{ogu} and \eqref{eq:T_lower} imply that
\[
    R_{\rm minimax} \geq \frac{N}{N+s} (1-\alpha),
\]
which is exactly \eqref{eq:Thm24_Tsy}.

\subsection{Proofs of Results for Section \ref{sec:Bayes_general} on Bayes Risk Lower Bound for General Loss}

\subsubsection{Proof of Theorem \ref{bwl}}
\label{sec:proof_bwl}
\begin{proof}[Proof of Theorem \ref{bwl}]
Fix $\Theta, {\mathcal{A}}, L, w$ and $f$. Let $I := I_f(w, {\mathcal{P}})$ be a shorthand notation. Suppose $t > 0$ is such that
  \begin{eqnarray}
  \label{eq:cond_t}
  \sup_{a \in {\mathcal{A}}} w \left(B_t(a,L)\right) < 1-u_f(I).
  \end{eqnarray}
We prove below that $R_{\rm Bayes}(w, L; \Theta) \geq t/2$ and this would complete the proof. Let $L_{t}$ denote the zero-one valued loss function $L_{t}(\theta, a) :=  \mathbbm{I} \left\{L(\theta, a) \geq t \right\}$. It is obvious that $L \geq t L_{t}$ and hence the proof will be complete if we establish that $R_{\rm Bayes}(w, L_{t}; \Theta) \geq 1/2$.  Let $R := R_{\rm Bayes}(w, L_{t}; \Theta)$ for a shorthand notation.

Because $L_t$ is a zero-one valued loss function, Theorem \ref{man} gives
\begin{equation}\label{sb}
  I \geq \phi_f(R, R_0) \qt{where $R_0 = 1 - \sup_{a \in {\mathcal{A}}} w \left( B_t(a, L) \right)$}.
\end{equation}
By \eqref{eq:cond_t}, it then follows that $R_0 > u_f(I)$. By definition of $u_f(\cdot)$, it is clear that there exists $b^* \in [1/2, R_0)$ such that $\phi(1/2, b^*) > I$ (this in particular implies that $R_0 \geq 1/2$).  Lemma \ref{lem:lower_property} implies that $b \mapsto \phi_f(1/2, b)$ is non-decreasing for $b\in[1/2, 1]$, which yields $\phi_f(1/2, b^*) \leq \phi_f(1/2, R_0)$. The above two inequalities imply $I <  \phi_f(1/2, R_0)$. Combining this inequality with~\eqref{sb}, we have
\begin{equation*}
  \phi_f(1/2, R_0) > I \geq \phi_f(R, R_0).
\end{equation*}
Lemma \ref{lem:lower_property} shows that  $a \mapsto \phi_f(a, R_0)$ is non-increasing for $a \in [0, R_0]$. Thus, we have $R \geq 1/2$.
\end{proof}

\subsubsection{Proof of Corollary \ref{cor:bwl}}

\label{sec:supp_bwl}
\begin{enumerate}
  \item Inequality \eqref{eq:I_bayes_KL} involving KL divergence:  Suppose $f(x) = x\log x$ so that $D_f(P||Q) = D(P||Q)$ equals the KL divergence. Then the function $u_f(x)$ in~\eqref{ufi}
has the expression for all $x>0$,
\begin{equation*}
  u_f(x) = \inf \left\{1/2 \leq b \leq 1: b(1-b) < e^{-2x}/4 \right\}
  = \frac{1}{2} + \frac{1}{2} \sqrt{1 - e^{-2x}}.
\end{equation*}
The elementary inequality $\sqrt{1 - a} \leq 1 - a/2$ gives for all $x>0$,
\begin{equation*}
  u_f(x) \leq 1 - \frac{1}{4} e^{-2x}.
\end{equation*}
Inequality~\eqref{eq:main_bwl} reduces to the desired inequality \eqref{eq:I_bayes_KL}:
\begin{equation*}
  R_{\rm Bayes}(w,L; \Theta) \geq \frac{1}{2} \sup \left\{t > 0 : \sup_{a
      \in {\mathcal{A}}} w\left(B_t(a,L)\right)< \frac{1}{4} e^{-2 I_f^{\rm up}} \right\}.
\end{equation*}
  \item Inequality \eqref{eq:I_bayes_chi} involving chi-squared divergence: Suppose $f(x) = x^2 - 1$ so that $D_f(P||Q) = \chi^2(P||Q)$. Then it
  is straightforward to see that
  \begin{equation*}
    u_f(x) = \inf \left\{1/2 \leq b \leq 1 : \frac{(1 -
        2b)^2}{4b(1-b)} > x \right\} = \frac{1}{2} + \frac{1}{2}
    \sqrt{\frac{x}{1+x}}.
  \end{equation*}
  Using the elementary inequality for all $x>0$,
  \begin{equation*}
    \sqrt{\frac{x}{1+x}} \leq 1 - \frac{1}{2(1+x)}.
  \end{equation*}
  We obtain \eqref{eq:I_bayes_chi} from Theorem~\ref{bwl}, i.e.,
  \begin{equation*}
    R_{\rm Bayes}(w, L; \Theta) \geq \frac{1}{2} \sup \left\{t > 0 :
      \sup_{a \in {\mathcal{A}}} w \left( B_t(a,L) \right) < \frac{1}{4\left(1+ I_f^{\rm up}\right)} \right\}.
  \end{equation*}
  \item Inequality \eqref{eq:I_bayes_TV} involving total variation distance:   Suppose $f(x) = |x-1|/2$ so that $D_f(P||Q) = \|P-Q\|_{TV}$ is the total
  variation distance between $P$ and $Q$. Then
  \begin{equation*}
    u_f(x) = \inf \left\{1/2 \leq b \leq 1 : |1 - 2b| > 2x \right\} =
    \frac{1}{2} + x
  \end{equation*}
  which gives \eqref{eq:I_bayes_TV} as below
  \begin{equation*}
    R_{\rm Bayes}(w, L; \Theta) \geq \frac{1}{2} \sup \left\{t> 0 :
      \sup_{a \in {\mathcal{A}}} w \left(B_t(a,L) \right)  < \frac{1}{2} - I_f^{\rm up} \right\}.
  \end{equation*}
  \item Inequality \eqref{eq:I_bayes_Hellinger} involving Hellinger divergence:  Suppose $f(x)=1-\sqrt{x}$ so that $D_f(P||Q)=H^2(P || Q)/2$. Then,
\begin{equation*}
  u_f(x)= \inf \left\{1/2 \leq b \leq 1: 1-\sqrt{b/2} -\sqrt{(1-b)/2}  >x \right\}.
\end{equation*}
Since $0 \leq 1-\sqrt{b/2} -\sqrt{(1-b)/2} \leq 1-1/\sqrt{2} $   for
$1/2 \leq b \leq 1$, we have $u_f(x) =1$ when $x\geq
1-1/\sqrt{2}$. On the other hand, when $x<1-1/\sqrt{2}$, we have
\begin{eqnarray*}
  u_f(x)=\frac{1}{2} + (1-x) \sqrt{x(2-x)}.
\end{eqnarray*}
Thus, if $I_f^{\rm up} < 1-1/\sqrt{2}$, we obtain inequality
\eqref{eq:I_bayes_Hellinger}.
\end{enumerate}

\subsection{Proofs and Additional Results for Section
  \ref{sec:upper_f_informativity} on Upper Bounds on
  $f$-informativity} \label{ange}

\subsubsection{Proof of Theorem \ref{cd}}

To prove Theorem \ref{cd}, the following lemma is critical.

\begin{lemma}\label{lem:concavity}
Fix $r < 1$. Let $\mu$ be a probability measure on the space $T$ and let $S := \{u: T \rightarrow {\mathbb R}_+: u \in L_{\mu}^r(T)\}$. Then the map $f : S \rightarrow {\mathbb R}$ defined by $f(u) := \left( \int_{T} u(t)^r  \mu(\mathrm{d}t)\right)^{1/r}$ is concave in $u$.
\end{lemma}
Note that the discrete version of Lemma \ref{lem:concavity}  states that $f(u)=\left(  \sum_{i=1}^M u_i^r/M\right)^{1/r}$ is a concave function of $u \in \mathbb{R}_{+}^M$ when $r<1$.

\begin{proof}[Proof of Lemma \ref{lem:concavity}]
 Let $\phi(t) \equiv t^r$ with $\phi'(t)=r t^{r-1}$ and
  $\phi''(t)=r(r-1) t^{r-2}$  and $\varphi(t)=t^{1/r}$ with
  $\varphi'(t)=\frac{1}{r}t^{(1-r)/r}$. Then
  $$f(u)=\varphi\left(\int_{T}  \phi(u(t)) \mu(\mathrm{d}t) \right).$$
  To prove the concavity of $f(u)$, considering the scalar function
  \begin{eqnarray}
    h(s) = \varphi\left(\int_{T}  \phi(u(t)+s v(t) ) \mu(\mathrm{d}t) \right),
  \end{eqnarray}
  for arbitrary $u, v \in  L^{r}_{\mu}(T)$. We notice that concavity
  of $f$ is equivalent to concavity at zero for all functions of the
  form $h$, and we therefore only have to show that $h''(0) \leq
  0$. Let $g(s)= \int_{T}  \phi(u(t)+s v(t) ) \mu(\mathrm{d}t)$,
  \begin{align*}
    h'(s) = & \varphi'(g(s)) \int_T \phi'(u(t)+sv(t))v(t) \mu(\mathrm{d} t) \\
    h''(s)  = &\varphi''(g(s))\left( \int_T \phi'(u(t)+sv(t))v(t) \mu(\mathrm{d} t) \right)^2  \\
               & + \varphi'(g(s)) \int_T \phi''(u(t)+sv(t))v^2(t) \mu(\mathrm{d} t)
  \end{align*}
  By plugging in the definitions of $\phi(t)$, $\varphi(t)$, $g(s)$ and setting $s=0$, we have
  \begin{eqnarray*}
    h''(0)=\frac{1-r}{f(u)}\left( \left(f(u)^{1-r} \int_T u(t)^{r-1} v(t) \mu(\mathrm{d}t) \right)^2- f(u)^{2-r} \int_T u(t)^{r-2} v^2(t) \mu(\mathrm{d}t)\right)
  \end{eqnarray*}
  Applying the Cauchy-Schwarz inequality $$\left(\int_T a(t)b(t)
    \mu(\mathrm{d}t)\right)^2  \leq  \left(\int_T a(t)^2
    \mu(\mathrm{d}t)\right) \left(\int_T b(t)^2
    \mu(\mathrm{d}t)\right) $$ with
  $a(t)=\left(\frac{f(u)}{u(t)}\right)^{-r/2}$ and $b(t) = v(t)
  \left(\frac{f(u)}{u(t)}\right)^{1-r/2}$ and noticing that $r<1$, we
  have $h''(0)\leq 0$, which completes the proof.
\end{proof}

In fact, since we will apply this lemma to prove Theorem \ref{cd} with $r=\frac{1}{1-\alpha}$,  the condition $r<1$ in Lemma \ref{lem:concavity} translates into $\alpha \not \in [0,1]$ in Theorem \ref{cd}.  We are now ready to prove Theorem~\ref{cd}.

\begin{proof}[Proof of Theorem \ref{cd}]
  By the identity that $D_{f_\alpha}(P||Q)=D_{f_{1-\alpha}}(Q||P)$, we have
  \begin{align*}
    D_{f_{\alpha}}(P||\bar{Q})  = D_{f_{1-\alpha}}(\bar{Q}||P)  &=\int_{\mathcal{X}} p \left( \int_{\Xi}\frac{q_{\vartheta}}{p} \nu(\mathrm{d}\vartheta) \mathrm{d} \lambda \right)^{1-\alpha}    -1 \\
&=\int_{\mathcal{X}} p \left( \int_{\Xi}\left[\left(\frac{q_{\vartheta}}{p} \right)^{1-\alpha} \right]^{1/(1-\alpha)}\nu(\mathrm{d}\vartheta) \mathrm{d} \lambda \right)^{1-\alpha} -1
  \end{align*}
  Let $u(\vartheta, x) = \left(\frac{q_{\vartheta}}{p} \right)^{1-\alpha}$. Since $\frac{1}{1-\alpha}<1$ when $\alpha \not \in [0,1]$, Lemma \ref{lem:concavity} implies that
  $u(\vartheta, x) \mapsto \left( \int_{\Xi} u(\vartheta, x)^{1/(1-\alpha)} \nu(\mathrm{d}\vartheta)\right)^{1-\alpha} $ is concave in $u$. Applying Jensen's inequality,
  \begin{align*}
     D_{f_{\alpha}}(P||\bar{Q})   & \leq  \left( \int_{\Xi}\left[\int_{\mathcal{X}} p \left(\frac{q_{\vartheta}}{p} \right)^{1-\alpha} \mathrm{d} \lambda \right]^{1/(1-\alpha)}\nu(\mathrm{d}\vartheta)  \right)^{1-\alpha} -1 \\
     & =  \left( \int_{\Xi}\left[D_{f_{1-\alpha}}(Q_{\vartheta} || P) \right]^{1/(1-\alpha)}\nu(\mathrm{d}\vartheta)  \right)^{1-\alpha} -1.

  \end{align*}
This completes the proof of~\eqref{co1} because $D_{f_{1-\alpha}}(Q_{\vartheta} || P)= D_{f_{\alpha}}(P || Q_{\vartheta}) $. The proof of~\eqref{eq:upper_f_power} follows by applying~\eqref{co1} for $P = P_{\theta}$ and then integrating the resulting bound with respect to $w(\mathrm{d}\theta)$.
\end{proof}

\subsubsection{Example demonstrating the effectiveness of Theorem~\ref{cd}}\label{effb}
In this example, we show the tightness of the upper bound in \eqref{co1} in terms of chi-squared divergence ($\alpha = 2$). In particular, let the distribution $P$ be the $n$-fold product of $N(0,1)$ and $Q_{\vartheta}$ be the $n$-fold product of $N(\vartheta,1)$ where $\vartheta \sim N(0,1)$. It is straightforward to show that the marginal distribution $\bar{Q}$ is a $n$-dimensional Gaussian distribution with mean $\mathbf{0}$ and covariance matrix $I_n+ \mathbf{1}_n \mathbf{1}_n ^T$, where $\mathbf{1}_n$ denotes the $n$-dimensional all one vector and $I_n$ the $n\times n$ identity matrix.

  Since $\chi^2(P||Q_{\vartheta})=\exp(n \vartheta^2)-1$, the right hand side of \eqref{co1} equals to $\sqrt{2n+1}-1$. The term   $\chi^2(P||\bar{Q})$ on the left hand side of \eqref{co1}  is difficult to evaluate. However, we can lower bound $\chi^2(P||\bar{Q})$ using the following standard inequality $\exp\left( D(P||\bar{Q}) \right) -1 \leq \chi^2(P||\bar{Q})$ (see Lemma 2.7 in \citet{Tsybakov:nonpara}).
  By the closed-form expression for KL divergence between two multivariate Gaussian distributions, we have $D(P||\bar{Q})=\frac{1}{2} \left( \log(n+1) - n/(n+1) \right)$ and thus
  \begin{eqnarray*}
    e^{-1/2} \sqrt{n+1}-1 \leq \exp\left( D(P||\bar{Q}) \right) -1  \leq \chi^2(P||\bar{Q})
  \end{eqnarray*}
  As we can see, the upper bound $\sqrt{2n+1}-1$ in \eqref{co1} is quite tight and $\chi^2(P||\bar{Q})$ is on the order of $\sqrt{n}$.

\subsubsection{Proof of Corollary \ref{cor:chi_dist_upper}}
Let $Q_1, \dots, Q_M$ be probability measures on ${\mathcal{X}}$ and fix $\theta \in \Theta$. Inequality~\eqref{co1} applied to $P = P_{\theta}$, $\Xi := \{1, \dots, M\}$ and the uniform probability measure on $\Xi$ as $\nu$ gives
\begin{equation*}
  D_{f_{\alpha}}(P_{\theta} \| \bar{Q}) \leq  M^{\alpha-1} \left[ \sum_{j=1}^M  (1+D_{f_{\alpha}}(P_{\theta}\| Q_j))^{1/(1-\alpha)} \right]^{1-\alpha} - 1
\end{equation*}
We now use (note that $\alpha > 1$)
\begin{eqnarray*}
  \sum_{j=1}^M  (1+D_{f_{\alpha}}(P_{\theta}\| Q_j))^{1/(1-\alpha)}  \geq  & \max_{1 \leq j \leq M}  (1+D_{f_{\alpha}}(P_{\theta}\| Q_j))^{1/(1-\alpha)} \\
                          = & \left(1 + \min_{1 \leq j \leq M} D_{f_{\alpha}}(P_{\theta}\|Q_j) \right)^{1/(1-\alpha)}.
\end{eqnarray*}
This gives $$D_{f_{\alpha}}(P_{\theta}\|\bar{Q}) \leq M^{\alpha - 1} \left(1 + \min_{1 \leq j \leq M} D_{f_{\alpha}}(P_{\theta}\|Q_j) \right) - 1.$$

We now fix $\epsilon > 0$ and apply the above with $\{Q_1, \dots, Q_M\}$ taken to be an $\epsilon^2$-cover of $\Theta$ under the $f_\alpha$-divergence. We then obtain
\begin{equation*}
  D_{f_{\alpha}}(P_{\theta}\|\bar{Q}) \leq \inf_{\epsilon>0} (1 + \epsilon^2) M_{\alpha}(\epsilon, \Theta)^{\alpha - 1} - 1.
\end{equation*}
The proof is complete by integrating the above inequality with respect to $w(\mathrm{d}\theta)$.

  \subsubsection{Proof of Corollary~\ref{nd}}\label{sec:cor_nd}
Fix $0 < \delta \leq A^{-1/2}$. Partition the entire parameter space $\Theta$ into small hypercubes each with side length $\delta$. For each such hypercube $S$ and let $\pi_S$ denote the probability measure $w$ conditioned to be in $S$ i.e., $\pi_S(C) := w(C)/w(S)$ for measurable set $C \subseteq S$.

For every decision rule ${\mathfrak{d}}(X)$, clearly
\begin{equation*}
  \int_{\Theta} {\mathbb E}_{\Theta} L(\theta, {\mathfrak{d}}(X)) w(\mathrm{d}\theta) = \sum_{S} w(S) \int_S {\mathbb E}_{\theta} L(\theta, {\mathfrak{d}}(X)) d\pi_S(\theta)
\end{equation*}
where the sum above is over all hypercubes $S$ in the partition. This implies therefore that
\begin{equation*}
  R_{\rm Bayes}(w, L; \Theta) \geq \sum_{S} w(S) R_{\rm Bayes}(\pi_S, L; S).
\end{equation*}
The proof will therefore be completed if we show that
\begin{equation}\label{rsp}
  R_{\rm Bayes}(\pi_S, L; S) \geq \frac{1}{2} e^{-2p} 8^{-p/d} \delta^p V^{-p/d} \int_S \left(\frac{1}{r_{\delta}(\theta)}  \right)^{p/d} \pi_S(d\theta)
\end{equation}
for every fixed hypercube $S$. So let us fix $S$ and, for notational simplicity, let $\pi := \pi_S$. We will
use~\eqref{eq:I_bayes_KL} to prove a lower bound on $R_{\rm Bayes}(\pi_S, L; S)$. Note first that
\begin{multline} \label{eq:fano_mutual}
  \inf_{Q} \int_S D(P_{\theta} || Q) \pi(\mathrm{d}\theta)  \leq   \int_S  \int_S D(P_{\theta} || P_{\theta'}) \pi(\mathrm{d}\theta) \pi(\mathrm{d}\theta')   \\
   \leq   A \max_{\theta \in S, \theta' \in S} \|\theta-\theta'\|_2^2      \leq   A d \delta^2 =: I_f^{\rm up} .
\end{multline}
Also, letting $f_w^{\max}$ and $f_w^{\min}$ be the maximum and minimum values of $f_w$ in $S$, we have
\begin{eqnarray*}
  \sup_{a \in S } \pi(B_t(a, L)) \leq \frac{f_w^{\max}}{w(S)} \text{Vol}(B_t(a, L ))   \leq \frac{f_w^{\max} V t^{d/p}}{f_w^{\min} \delta^d} .
\end{eqnarray*}
Let $\widetilde \theta$ be an arbitrary point in the set $S$. Since $S$ has diameter $\sqrt{d} \delta$, the set $\{\theta: \|\theta-\widetilde \theta\|_2 \leq \sqrt{d} \delta \}$
contains $S$.  We obtain from the definition of $r_\delta(\theta)$
that $f_w^{max}/f_w^{min} \leq r_{\delta}(\tilde{\theta})$ so that
\begin{equation*}
  \sup_{a \in S } \pi(B_t(a, L)) \leq r_{\delta}(\tilde{\theta}) V \delta^{-d} t^{d/p}.
\end{equation*}
Thus, by~\eqref{eq:fano_mutual}, the choice
\begin{eqnarray*}
  t= e^{-2p A \delta^2} \delta^p \left( \frac{1}{8 V r_{\delta}(\widetilde \theta)}\right)^{p/d},
\end{eqnarray*}
leads to $\sup_{a \in S} \pi(B_t(a, L)) < \frac{1}{4} e^{-2I_f^{\rm up}}$. Employing \eqref{eq:I_bayes_KL}, we deduce
\begin{equation*}
  R_{\rm Bayes}(\pi, L; S) \geq \frac{1}{2} e^{-2p A \delta^2} \delta^p \left( \frac{1}{8 V r_{\delta}(\widetilde \theta)}\right)^{p/d} \geq \frac{1}{2}e^{-2p} \delta^p \left( \frac{1}{8 V  r_{\delta}(\widetilde \theta)}\right)^{p/d}
\end{equation*}
where we used the fact that $\delta^2 \leq 1/A$. Because $\tilde{\theta} \in S$ is arbitrary, we can write
\begin{eqnarray*}
    R_{\rm Bayes}(\pi, L; S) & \geq &  \frac{1}{2} e^{-2p} \delta^p (8V)^{-p/d} \sup_{\tilde \theta\in S} \left( \frac{1}{r_{\delta}(\tilde \theta)}\right)^{p/d} \\
    & \geq & \frac{1}{2} e^{-2p} \delta^p (8V)^{-p/d} \int_{S} \left(\frac{1}{r_{\delta}(\theta)}\right)^{p/d} \pi(\mathrm{d}\theta).
\end{eqnarray*}
This proves~\eqref{rsp}.

\subsection{More Examples on Bayes Risk Lower Bounds}
\label{sec:Bayes_Example}

In this subsection, we provide more examples on the applications of derived Bayes risk lower bound in Theorem \ref{bwl} and Corollary \ref{cor:bwl}. For the clarity of the presentation, in each example, we will first present the Bayes risk lower bound and then provide the proof.

\subsubsection{Generalized Linear Model}

Fix $d \geq 1$ and let $\Theta = {\mathcal{A}} = {\mathbb R}^d$ with $L(\theta, a) = \|\theta - a\|_2^p$ for a fixed $p > 0$. Also fix $n \geq 1$ and an $n \times d$ matrix $X$ whose rows are written as $x_1^T, \dots, x_n^T$. As in the last example, $\lambda_{\max}$ denotes the maximum eigenvalue of $X^T X/n$.

For $\theta \in \Theta$, let $P_{\theta}$ denote the joint distribution of independent random variables $Y_1, \dots, Y_n$ where $Y_i$ has the density
\begin{equation}\label{eq:glm_density}
  \exp \left[\frac{y \beta_i - b(\beta_i)}{a(\phi)}  + c(y, \phi) \right] \qt{for $y \in {\mathbb R}$}
\end{equation}
with $\beta_i = x_i^T \theta$ for $i = 1, \dots, n$. The parameter $\phi$ is taken to be a constant and the functions $a(\cdot), c(\cdot, \cdot)$ and $b(\cdot)$ are assumed to be known. We assume the existence of a constant $K > 0$ such that $b''(\beta) \leq K$ for all $\beta$ where $b''(\cdot)$ is the second derivative of $b(\cdot)$. This assumption indeed holds for many generalized linear models (e.g., binomial, Gaussian) and we will discuss the case (i.e., Poisson) where this assumption fails at the end of this example.

Let $w$ denote the Gaussian prior with mean zero and covariance matrix $\tau^2 I_d$. Using Corollary~\ref{nd}, we can prove that that
\begin{equation}\label{mee}
  R_{\rm Bayes}(w, L; \Theta) \geq C \left[ d \min \left(\frac{a(\phi)}{n K }, \tau^2  \right) \right]^{p/2}
\end{equation}
for a constant $C$ that depends only on $p$. Let us illustrate this lower bound by considering a simple case of $p=2$. We note that the term $ \frac{d a(\phi)}{n K}$ is the well-known minimax risk of generalized linear model under  the squared loss. The parameter $\tau$ characterizes the strength of the prior information. In fact, since $\tau^2 I$ is the variance of the Gaussian prior distribution, a small value of $\tau$ provides strong prior information that each $\theta_j$ should be concentrated around $0$. When $\tau$ is large, i.e., with less prior information, the lower bound of the Bayes risk in~\eqref{mee} is the same as the minimax risk up to a constant factor. On the other hand, when $\tau$ is small, i.e., with strong prior information, the lower bound of the Bayes risk becomes $d \tau^2$, which is smaller than the minimax risk.

The proof of~\eqref{mee} will involve Corollary~\ref{nd} for which we need to determine $A, V$ and $r_{\delta}(\theta)$. As before, it is easy to check that $V = \mathrm{Vol}(B)$. To determine $A$, fix a pair $\theta_1, \theta_2$ and, letting $\beta_i^{(j)} = x_i^T \theta_j$ for $j = 1, 2$ and $i=1, \ldots, n$, observe that
\begin{equation*}
   D(P_{\theta_1} || P_{\theta_2}) =   \frac{1}{a(\phi)} \sum_{i=1}^n \left(b'(\beta^{(1)}_{i}) \left( \beta^{(1)}_{i} -\beta^{(2)}_{i} \right) -\left(b(\beta^{(1)}_{i})- b(\beta^{(2)}_{i}) \right)  \right)
\end{equation*}
By the second order Taylor expansion of $b(\beta^{(2)}_{i})$ at the point $\beta^{(1)}_{i}$, we  obtain
\begin{equation*}
  D(P_{\theta_1} || P_{\theta_2})  =  \frac{1}{a(\phi)} \sum_{i=1}^n \frac{b''(\tilde{\beta}_i)}{2} ( \beta^{(1)}_{i} -\beta^{(2)}_{i})^2
\end{equation*}
where $\tilde{\beta}_i$ lies between $\min(\beta^{(1)}_{i}, \beta^{(2)}_{i})$ and $\max(\beta^{(1)}_{i},  \beta^{(2)}_{i})$. Now because of our assumption that $b''(\cdot) $ is bounded from above by $K$, we get
\begin{align*}
  D(P_{\theta_1} \| P_{\theta_2}) & \leq \frac{K}{2 a(\phi)} \|\beta^{(1)} - \beta^{(2)} \|_2^2 = \frac{K}{2 a(\phi)} (\theta_1 - \theta_2)^T X^T X (\theta_1 - \theta_2) \\ & \leq \frac{n K \lambda_{\max}}{2 a(\phi)} \|\theta_1 - \theta_2\|^2.
\end{align*}
We can thus take $A = n K \lambda_{\max}/(2 a(\phi))$ in Corollary~\ref{nd}. Next we control $r_{\delta}(\theta)$. For given $\theta$ and $\delta$,
\begin{eqnarray*}
  r_{\delta}(\theta)= \sup \left\{ \exp\left(-\frac{1}{2 \tau^2} \left( \|\theta_1\|_2^2 - \|\theta_2\|_2^2 \right) \right) : \|\theta_i - \theta\|_2 \leq \sqrt{d} \delta \right\}.
\end{eqnarray*}
For $\theta_1, \theta_2$ with $\|\theta_i - \theta\|_2 \leq \sqrt{d} \delta,\; i = 1, 2$, we have
\begin{eqnarray*}
  \left|  \|\theta_1\|_2^2 - \|\theta_2\|_2^2  \right|  & = & \left|  \|\theta_1-\theta\|_2^2 +2 \theta^T(\theta_1-\theta) - \|\theta_2-\theta\|_2^2- 2 \theta^T(\theta_2-\theta)  \right| \\
  & \leq & \left|  \|\theta_1-\theta\|_2^2  - \|\theta_2-\theta\|_2^2 \right| + 2\| \theta\|_2 \left(\|\theta_1-\theta\|_2+\|\theta_2-\theta\|_2  \right) \\
  & \leq &  d \delta^2 + 4 \sqrt{d} \delta \|\theta\|_2.
\end{eqnarray*}
As a result $r_{\delta}(\theta)^{-p/d} \geq \exp(-p\delta^2/(2 \tau^2)) \exp(-2p\delta \|\theta\|_2/(\tau^2 \sqrt{d}))$ and hence
\begin{eqnarray*}
  \int_{\Theta} \left(\frac{1}{r_{\delta}(\theta)}\right)^{p/d} w(\mathrm{d}\theta) &\geq & \exp \left(  -\frac{p \delta^2}{2 \tau^2} \right) \int_{\Theta} \exp\left(-\frac{2p\delta }{\tau} \frac{\|\theta\|_2}{\tau \sqrt{d}} \right) w(\mathrm{d}\theta)\\
& \geq & \exp \left(  -\frac{p \delta^2}{2 \tau^2} - \frac{4 p \delta}{\tau} \right)  \int_{\Theta} \mathbb{I} \left\{\|\theta\|_2 < 2 \tau \sqrt{d} \right\} w(\mathrm{d}\theta).
\end{eqnarray*}
By Chebyshev's inequality, we have
\begin{equation}\label{eq:Gauss_con}
  \int_{\Theta}\mathbb{I} \left\{\|\theta\|_2 \geq 2 \tau \sqrt{d} \right\} w(\mathrm{d}\theta) \leq \frac{1}{4 \tau^2 d} \int_{\Theta} \|\theta\|_2^2 w(\mathrm{d}\theta) = \frac{1}{4}.
\end{equation}
Consequently,
\begin{eqnarray}
\int_{\Theta} \left(\frac{1}{r_{\delta}(\theta)}\right)^{p/d} w(\mathrm{d}\theta)\geq \frac{3}{4}\exp \left(  -\left( \frac{p \delta^2}{2 \tau^2} +\frac{ 4p \delta}{\tau} \right)\right).
\label{eq:Bayes_log_1}
\end{eqnarray}
Corollary~\ref{nd} therefore gives
\begin{equation*}
  R_{\rm Bayes}(w, L; \Theta) \geq \frac{3}{8} e^{-2p} (8 V)^{-p/d} \delta^p \exp \left(-\frac{p\delta^2}{2 \tau^2} - \frac{4 p \delta}{\tau} \right)  \qt{whenever $\delta^2 \leq 1/A$}.
\end{equation*}
We make the choice
\begin{equation*}
  \delta^2 := \min \left(1/A, \tau^2 \right) = \min \left(\frac{2 a(\phi)}{n K \lambda_{\max}}, \tau^2 \right)
\end{equation*}
which implies that the exponential term in the right hand side of~\eqref{eq:Bayes_log_1} is bounded from below by $\exp(-9p/2)$. We thus have
\begin{equation*}
  R_{\rm Bayes}(w, L; \Theta) \geq \frac{3}{8} e^{-13p/2} (8 V)^{-p/d} \left[\min \left(\frac{2 a(\phi)}{n K \lambda_{\max}}, \tau^2 \right)  \right]^{p/2}.
\end{equation*}
The inequality~\eqref{mee} now follows because $V^{1/d} \asymp d^{-1/2}$.

The assumption that $b''(\beta) \leq K$ which was used for the proof of~\eqref{mee} holds  under some widely used densities of $Y_i$ in \eqref{eq:glm_density}. For Gaussian distribution in \eqref{eq:glm_density}, we have $b(\beta)=\frac{\beta^2}{2}$ so that $b''(\beta)=1$ for $\beta \in \mathbb{R}$. For binomial distribution, $b(\beta)= \log(1+\exp(\beta))$ and $b''(\beta)=\frac{\exp(\beta)}{(1+\exp(\beta))^2} \leq \frac{1}{4}$ for all $\beta \in \mathbb{R}$. However, for Poisson distribution, $b(\beta)=\exp(\beta)$ and thus $b''(\beta) =\exp(\beta)$ is unbounded on $\mathbb{R}$. To address this issue, we restrict the prior to the subset $\widetilde{\Theta}=\{ \theta \in \Theta: \|\theta\|_2 \leq 2 \tau \sqrt{d} \}$ and define the re-scaled prior distribution $\pi$ on $\widetilde{\Theta}$ as $\pi(S)=w(S)/w(\widetilde{\Theta})$ for any measurable set $S \subseteq  \widetilde{\Theta}$. Let $B= \max_{i=1,\ldots, n} \|x_i\|_2$. For any $\beta=x_i^T \theta$ for some $i=1, \ldots, n$ and $\theta \in \widetilde{\Theta}$, we have $b''(\beta) \leq \exp(2 \tau \sqrt{d}  B):=K$. We note that such a restriction of the parameter space will not affect the order of the Bayes risk lower bound. In particular, since now $b''(\beta) \leq K$ when $\theta \in \widetilde{\Theta}$, applying the same argument, we obtain the lower bound on $R_{\rm Bayes}(\pi, L; \widetilde{\Theta})$.  By \eqref{eq:Gauss_con}, we have $w(\widetilde{\Theta})\geq 3/4$ and the lower bound on $R_{\rm Bayes}( w, L ; \Theta)$ can be easily established by noticing that $R_{\rm Bayes}( w, L ; \Theta)  \geq  w(\widetilde{\Theta})R_{\rm Bayes}( \pi, L ; \widetilde{\Theta}) \geq \frac{3}{4} R_{\rm Bayes}( \pi, L ; \widetilde{\Theta}).$

\subsubsection{Spiked covariance model}\label{sec:vee}

Fix $\Theta = {\mathcal{A}} = B$ where $B$ is the unit Euclidean closed ball of radius one and let $L(\theta, a) := \|\theta - a\|_2^p$ for a fixed $p > 0$. Also fix $n \geq d/2$. For $\theta \in \Theta$, let $P_{\theta}$ denote the joint distribution of independent and identically distributed observations $X_1, \dots, X_n$ satisfying the Gaussian distribution with zero mean and covariance matrix $\Sigma_{\theta} := I_d + \theta \theta^T$. This is the problem of estimating the principal component for a rank-one spiked covariance model. Let $w$ denote the uniform distribution on $B$. We shall prove that
\begin{equation}\label{vee}
  R_{\rm Bayes}(w, L; \Theta) \geq C \left[\min \left(\frac{1}{2}, \frac{d}{n} \right) \right]^{p/2}
\end{equation}
where $C$ only depends on $p$.

The proof is based on the application of~\eqref{eq:main_bwl}  with $f(x) = x^2 - 1$, i.e., on inequality~\eqref{eq:I_bayes_chi}.

For this, we need to bound the term $\sup_{a \in {\mathcal{A}}} w(B_t(a, L))$ and the $f$-informativity corresponding to the chi-squared divergence. It is easy to see that $\sup_{a \in {\mathcal{A}}} w(B_t(a, L)) \leq t^{d/p}$.

For the $f$-informativity, we will use the bound~\eqref{eq:chi_dist_upper} with $\alpha = 2$ which requires bounding $M_{\chi^2}(\epsilon, \Theta)$. According to \cite[Theorem 4.6.1]{Aditya:PhDThesis}, for two Gaussian distributions with mean zero and covariance matrices $\Sigma_1$ and $\Sigma_2$ such that $2 \Sigma_1^{-1}  - \Sigma_2^{-1}$ is positive definite and $\|\Sigma_1 - \Sigma_2\|_F^2 \leq \frac{1}{2} \lambda^2_{\min}(\Sigma_2)$,  we have
  \begin{eqnarray}
    \chi^2\left(N_d(0, \Sigma_1) || N_d(0, \Sigma_2) \right) \leq \exp\left(\frac{\|\Sigma_1 - \Sigma_2\|^2_F}{\lambda_{\min}(\Sigma_2)^2}\right) -1.
    \label{eq:Gaussian_Chi_0}
  \end{eqnarray}
Here $\|\cdot\|_F$ denotes the Frobenius norm defined as $\|A\|_F^2 := \sum_{i, j} a_{ij}^2$ where $A = (a_{ij})$ and $\lambda_{\min}$ denotes the smallest eigenvalue

Using this result, we get that for $\theta_1, \theta_2 \in \Theta$ (note that $\lambda_{\min}(\Sigma_{\theta}) = 1$ for all $\theta$),
   \begin{eqnarray}
     \chi^2\left(P_{\theta_1} || P_{\theta_2} \right) \leq\exp\left(n\|\Sigma_{\theta_1} - \Sigma_{\theta_2}\|^2_F\right) -1,
     \label{eq:Gaussian_Chi}
   \end{eqnarray}
provided
   \begin{equation}\label{acon}
2 \Sigma_{\theta_1}^{-1} - \Sigma_{\theta_2}^{-1} \text{ is positive definite and }  \|\Sigma_{\theta_1} - \Sigma_{\theta_2}\|_F^2 \leq 1/2.
   \end{equation}
In the sequel, whenever we employ~\eqref{eq:Gaussian_Chi}, the conditions~\eqref{acon} hold. But, for ease of presentation, instead of verifying~\eqref{acon} for every application of~\eqref{eq:Gaussian_Chi}, we will simply assume~\eqref{eq:Gaussian_Chi} and verify the necessary conditions at the end of the proof.  Assuming~\eqref{eq:Gaussian_Chi}, we see that $\chi^2(P_{\theta_1}\|P_{\theta_2}) \leq \epsilon^2$ provided $\|\Sigma_{\theta_1} - \Sigma_{\theta_2}\|_F^2 \leq \log(1 + \epsilon^2)/n$. Now for $\theta_1, \theta_2 \in \Theta$
\begin{multline*}
  \|\Sigma_{\theta_1} - \Sigma_{\theta_2}\|_F^2  = \|\theta_1 \theta_1^T - \theta_2 \theta_2^T\|_F^2 = \|\theta_1 \theta_1^T - \theta_1 \theta_2^T + \theta_1 \theta_2^T - \theta_2 \theta_2^T\|_F^2 \\
\leq 2 \left(\|\theta_1\|_2^2 + \|\theta_2\|_2^2 \right) \|\theta_1 - \theta_2\|_2^2 \leq 4 \|\theta_1 - \theta_2\|_2^2.
\end{multline*}
It follows therefore that the $\epsilon^2$-covering number in the chi-squared divergence can be bounded from above by the $\sqrt{\log(1 + \epsilon^2)}/(2\sqrt{n})$-covering number of $B$ under the usual Euclidean norm. Consequently
\begin{equation*}
  M_{\chi^2}(\epsilon, \Theta) \leq \left(\frac{36 n}{\log (1 + \epsilon^2)}\right)^{d/2} \qt{provided \; $\log(1 + \epsilon^2) \leq 4n$}.
\end{equation*}
We now set $\epsilon$ to satisfy $\log(1+\epsilon^2)=\min \left(n/2, d\right)$ so that Corollary~\ref{cor:chi_dist_upper} gives
\begin{eqnarray*}
   I_{\chi^2}(w, {\mathcal{P}}) &\leq & M_{\chi^2}(\epsilon)(1+\epsilon^2) - 1\\
               & \leq & \exp \left(\min\left(\frac{n}{2}, d\right) \right)  \left[36 \max\left(2, \frac{n}{d} \right) \right]^{d/2} -1 =: I_f^{\rm up}.
\end{eqnarray*}
It follows that $ \sup_{a \in {\mathcal{A}}} w(B_t(a, L)) < \frac{1}{4} (1 + I_f^{\rm up})^{-1}$ provided $t = (4(1 + I_f^{\rm up}))^{-p/d}$. Inequality~\eqref{eq:I_bayes_chi} then proves
\begin{equation*}
  R_{\rm Bayes}(w, L; \Theta) \geq \frac{1}{2} \left(4(1 + I_f^{\rm up}) \right)^{-p/d} \geq \frac{1}{2} (24 e)^{-p} \left[\min \left(\frac{1}{2}, \frac{d}{n} \right) \right]^{p/2}
\end{equation*}
which implies~\eqref{vee}.

It remains to justify the conditions~\eqref{acon} when we used~\eqref{eq:Gaussian_Chi}.  It should be clear that for this, we only need to verify~\eqref{acon} when
\begin{equation}\label{didi}
  \|\Sigma_{\theta_1} - \Sigma_{\theta_2}\|_F^2 \leq \frac{\log(1+\epsilon^2)}{n} = \min \left( \frac{1}{2}, \frac{d}{n} \right).
\end{equation}
We only need to check that $2 \Sigma_{\theta_1}^{-1} - \Sigma_{\theta_2}^{-1}$ is positive definite under the above condition. For this, observe that by Weyl's inequality,
 \begin{eqnarray*}
     \lambda_{\min}\left(2 \Sigma_{\theta_1}^{-1} -\Sigma_{\theta_2}^{-1}\right) \geq \lambda_{\min}\left( 2 \Sigma_{\theta_1}^{-1}\right) - \lambda_{\max}\left(\Sigma_{\theta_2}^{-1}\right) = \frac{2}{1+\|\theta_1\|_2^2} - 1 \geq 0.
 \end{eqnarray*}
This implies that $2 \Sigma_{\theta_1}^{-1} - \Sigma_{\theta_2}^{-1}$ is positive semi-definite
and $\|\theta_1\|_2=1$ is a necessary condition for $\lambda_{\min}\left(2 \Sigma_{\theta_1}^{-1} -\Sigma{\theta_2}^{-1}\right)=0$. Under the condition that $\|\theta_1\|_2=1$, by Sherman-Morrison formula,
 \begin{eqnarray*}
    2\Sigma_{\theta_2}^{-1} - \Sigma_{\theta_1}^{-1}=I_d - \theta_1 \theta_1^T+\frac{\theta_2 \theta_2^T}{1+\theta_2^T \theta_2}.
 \end{eqnarray*}
 It is then easy to check that  $\lambda_{\min}\left(2 \Sigma_{\theta_1}^{-1} -\Sigma_{\theta_2}^{-1}\right)=0$ only if $\theta_2$ is orthogonal to $\theta_1$. However, when $\|\theta_1\|_2=1$ and $\theta_2$ is orthogonal to $\theta_1$,  $\|\Sigma_{\theta_1} - \Sigma_{\theta_2}\|^2_F= \|\theta_1\|_2^2+ \|\theta_2\|_2^2 > 1$,
 which contradicts \eqref{didi}. Therefore $2 \Sigma_{\theta_1}^{-1} - \Sigma_{\theta_2}^{-1}$ is positive definite and this completes the proof of~\eqref{vee}.

\subsubsection{Gaussian model with general prior and loss}
\label{sec:Gaussian}
In this example, we consider Gaussian location model with continuous
prior with a bounded Lebesgue density and general loss
functions. Here, we do not specify the form of the prior and loss. We
only present this example to illustrate applications of Theorem
\ref{bwl} and Corollary \ref{cor:bwl}. Our main bound is inequality
\eqref{hok}. This bound however might be suboptimal for specific
priors $w$ because we do not use knowledge about the specific form of
$w$. However, when the specific form of $w$ is available, the argument
can often be easily modified to improve inequality \eqref{hok}. We
provide examples of this at the end of this subsubsection.

\subsubsection{Gaussian model with squared loss}

Fix $d \geq 1$. Suppose $\Theta = {\mathcal{A}} = {\mathbb R}^d$ and let $L(\theta, a) := \|\theta - a\|_2^2$ where $\|\cdot\|_2$ is the usual Euclidean norm on ${\mathbb R}^d$. For each $\theta \in {\mathbb R}^d$, let $P_{\theta}$ denote the Gaussian distribution with mean $\theta$ and covariance matrix $\sigma^2 I_d$  ($\sigma^2 > 0$ is a constant). For every prior $w$ on ${\mathbb R}^d$ with a Lebesgue density bounded by $W > 0$, we have
\begin{equation}\label{hok}
  R_{\rm Bayes}(w, L; \Theta) \gtrsim \frac{d \sigma^4 W^{-2/d}}{(\sigma^2 + V)^2}
\end{equation}
where
\begin{equation}\label{eq:V}
    V := \min_{s \in {\mathbb R}^d} \int_{\Theta} \frac{1}{d} \sum_{i=1}^d (\theta_i- s_i)^2 w(\mathrm{d} \theta).
\end{equation}

To prove~\eqref{hok}, we shall apply~\eqref{eq:main_bwl} with $f(x) = x \log x$, i.e., we apply~\eqref{eq:I_bayes_KL}. The resulting $f$-informativity (a.k.a mutual information) can be bounded in the following way. Because $I(w, {\mathcal{P}}) \leq \int D(P_{\theta}\|Q) w(\mathrm{d}\theta)$ for every $Q$. In particular, we take $Q$ to be the Gaussian  distribution with mean $t$ and covariance matrix                                                                                $(\sigma^2 + V) I_d$, where $t= \mathop{\rm argmin}_{s \in {\mathbb R}^d} \int_{\Theta} \frac{1}{d} \sum_{i=1}^d (\theta_i- s_i)^2 w(\mathrm{d} \theta)$, i.e., $t_i =\int_{\Theta} \theta_i w(\mathrm{d} \theta)$ is ``center" of the prior.
Then, we obtain
\begin{equation*}
  I(w, {\mathcal{P}})  \leq \int_\Theta D\left( N\left( \theta, \sigma^2 I_d \right)  || N\left(t, \left(\sigma^2+V\right) I_d \right)  \right) w(\mathrm{d}\theta).
\end{equation*}
Using the standard formula for the KL divergence between two Gaussians, we deduce that
\begin{equation*}
  I(w, {\mathcal{P}}) \leq \frac{1}{2} \int_{\Theta} \left[\frac{\sum_{i=1}^d ((\theta_i-t_i)^2 - V)}{\sigma^2 + V} + d \log \frac{\sigma^2 + V}{\sigma^2} \right] w(\mathrm{d}\theta)
\end{equation*}
which by \eqref{eq:V} implies that
\begin{equation}\label{ibi}
  I(w, {\mathcal{P}}) \leq \frac{d}{2} \log \frac{\sigma^2 + V}{\sigma^2}.
\end{equation}
Let $I_f^{\rm up}$ denote the right hand side above. To apply~\eqref{eq:I_bayes_KL}, we also need an  upper bound on $\sup_{a \in A} w\left(B_t(a,L)\right)$. Because of the assumption that the Lebesgue density of $w$ is bounded from above by $W$, we get
\begin{equation}\label{psu1}
   \sup_{a \in A} w\left(B_t(a,L) \right) \leq  W t^{d/2} \mathrm{Vol}(B)
\end{equation}
where $B$ is the Euclidean ball with unit radius. Thus the choice
\begin{equation*}
  t = c W^{-2/d} \mathrm{Vol}(B)^{-2/d} \frac{\sigma^4 }{(\sigma^2 + V)^2},
\end{equation*}
for a small enough universal positive constant $c$, ensures $\sup_{a \in A} w\{B_t(a)\} < \frac{1}{4} e^{-2 I_f^{\rm up}}$ (recall that $I_f^{\rm up}$ is the right hand side of\eqref{ibi}).  Consequently, inequality~\eqref{eq:I_bayes_KL} implies that $R_{\rm Bayes} \geq t/2$. The proof of~\eqref{hok} is now completed using the standard fact: $\mathrm{Vol}(B)^{1/d} \asymp d^{-1/2}$.

However, since the form of the prior $w$ is unspecified in this
example, the simple upper bound on $ \sup_{a \in A} w\left(B_t(a,L)
\right) $ in \eqref{psu1} could be loose. But this can be easily fixed
when the concrete form of the prior is available. For example,  for a
spiked model with a large $W$ (see an example of mixture prior in
Remark \ref{rem:Bayes_decomp} in the main text), the lower bound in
\eqref{hok} could be sub-optimal but can be easily tightened using the
proposed chaining technique in Remark \ref{rem:Bayes_decomp} in the
main text. For another example, let $w$  be the uniform
prior on the hyper-rectangle $H = [-\epsilon,\epsilon]\times
[-1,1]^{d-1}$ for some very small $\epsilon$. Here
inequality~\eqref{psu1} is equivalent to
  \[
   \sup_{a \in A} w\left(B_t(a,L) \right) \leq  W t^{d/2} \mathrm{Vol}(B).
\]
When $\epsilon\to 0$, we have $W\to \infty$ so that the upper bound is fairly loose. However, since $H$ is the support of $w$, we can also use the following upper bound:
\[
   \sup_{a \in A} w\left(B_t(a,L) \right) \leq  W t^{d/2} \mathrm{Vol}(B\cap H).
\]
When $\epsilon\to 0$, we have $W\to \infty$ but $\mathrm{Vol}(B\cap
H)\to 0$. In particular, the product limit $\lim_{\epsilon\to 0}
W\mathrm{Vol}(B\cap H)\to 0$ is finite. It converges to the maximum
value of $w\left(B_t(a,L) \right)$ where $w$ is restricted in a
$(d-1)$-dimensional subspace of ${\mathbb R}^d$. Once we replace
inequality~\eqref{psu1} by the above upper bound, the associated Bayes
risk lower bound will be tight.

\subsubsection{Gaussian model with general loss}

Consider the same setup as in the previous example but now allow the loss function to be $L(\theta, a) = \|\theta - a\|^2$ for an arbitrary norm $\|\cdot\|$ (not necessarily the Euclidean norm) on ${\mathbb R}^d$. In this case, we obtain the following Bayes risk lower bound:
 \begin{eqnarray}
   R_{\rm Bayes}(w, L; \Theta) \gtrsim \frac{\sigma^4 W^{-2/d}}{(\sigma^2 + V)^2} \frac{d^2}{({\mathbb E} \|Z\|_* )^2}.
   \label{eq:Gaussian_location_norm}
 \end{eqnarray}
where $Z$ is a standard Gaussian vector and $\|\cdot\|_*$ is the dual norm corresponding to $\|\cdot\|$ defined by $\|x\|_* := \sup \{\left<x, y \right> : \|y\| \leq 1\}$. The quantities $W$ and $V$ are as defined in  the previous example.

The proof of~\eqref{eq:Gaussian_location_norm} is largely similar to that of~\eqref{hok}. We use~\eqref{eq:I_bayes_KL} along with~\eqref{ibi} for controlling $I(w, {\mathcal{P}})$. To control $\sup_{a \in {\mathcal{A}}} w(B_t(a, L))$, we again use the fact that the Lebesgue density of $w$ is bounded from above by $W$ to obtain
\begin{equation}\label{psu3}
   \sup_{a \in A} w\left(B_t(a,L) \right)  \leq  W \mathrm{Vol} \left\{\theta \in {\mathbb R}^d : \|\theta\| < \sqrt{t} \right\}.
\end{equation}
To deal with the volume term above, we use Urysohn's inequality to obtain an upper bound in terms of the volume of the unit Euclidean unit ball $B$. The  original reference for Urysohn's inequality is~\cite{Urysohn:24} but it has been recently  used in a statistical context by~\cite{MaWu:13}. Urysohn's inequality gives
 \begin{equation}\label{psu2}
  \left(\frac{\mathrm{Vol} \left\{\theta \in {\mathbb R}^d : \|\theta\| < \sqrt{t} \right\}}{\mathrm{Vol}(B) } \right)^\frac{1}{d} \leq \frac{\sqrt{t}}{\sqrt{d}} {\mathbb E}\|Z\|_* \qt{with $Z \sim N(0, I_d)$}.
\end{equation}
Inequalities~\eqref{psu3} and~\eqref{psu2} together give
 \begin{equation*}
   \sup_{a \in A} w\left(B_t(a,L) \right) \leq W t^{d/2} \mathrm{Vol}(B) \left(\frac{{\mathbb E} \|Z\|_*}{\sqrt{d}} \right)^d.
 \end{equation*}
The choice
\begin{equation*}
  t = c \mathrm{Vol}(B)^{-2/d} \frac{W^{-2/d} \sigma^4}{(\sigma^2 + V)^2} \frac{d}{({\mathbb E}\|Z\|_*)^2}
\end{equation*}
for a small enough universal positive constant $c$ ensures $\sup_{a \in A} w\{B_t(a)\} < \frac{1}{4} e^{-2 I_f^{\rm up}} $ ($I_f^{\rm up}$ is the right hand side of~\eqref{ibi}). The proof of~\eqref{eq:Gaussian_location_norm} is then completed by noting that $\mathrm{Vol}(B)^{1/d} \asymp d^{-1/2}$.

\subsection{Proof of Theorem \ref{jee}}
\label{sec:supp_admis}
We provide a complete proof of Theorem \ref{jee} in this
section. Because of space constraints, only an overview of the proof
was given in the main text. The preliminary results described in
Subsection \ref{prim} will be used here.

The main step is the construction of the prior $w$ on $\Theta$. The
idea here is to fix a specific $\theta^* \in \Theta$ and to choose $w$
to be a specific prior that is supported on the set
\begin{equation}\label{uri}
U(\theta^*): = \Theta \cap \{\theta \in {\mathbb R}^n : \|\theta - \theta^*\|_2 \leq \rho  t_{\theta^*}\}
\end{equation}
for a small enough constant $\rho$. Because of inequalities
\eqref{1co}, \eqref{smor}  and \eqref{smoo}, it can then be shown that
\begin{equation}\label{alla}
  \int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2 w(d\theta) \leq C t_{\theta^*}^2
\end{equation}
for some universal constant $C$ (provided $\rho$ is chosen to be
sufficiently small). To  complete the proof, we would only need to show the Bayes risk lower bound:
\begin{equation}\label{tosh}
  R_{\rm Bayes}(w) \geq c t^2_{\theta^*}
\end{equation}
for some universal positive constant $c$. We shall prove this for every closed convex set $\Theta$ provided $\theta^*$ and $w$ are properly chosen.

It makes sense here to work with two separate cases: the case when
$\inf_{\theta \in \Theta}  t_{\theta} $ is strictly smaller than some
constant (we will take this constant to be 85 for technical reasons)
and the case when $\inf_{\theta \in \Theta} t_{\theta}$ is larger than
$85$. The first case is the easy case. Here we will take $\theta^* \in
\Theta$ to be such that $t_{\theta^*} \leq 85$. The required bound
\eqref{tosh} will then be a parametric lower bound which we will prove
by the simple Le Cam's two point inequality ($w$ will be taken to be a
prior on $\{\theta^*, \theta_1\}$ for some suitably chosen $\theta_1
\in \Theta$). We would like to remark here that our proof of this easy
case is already simpler than the proof of this case in
\cite{Sourav14LS}. The second case (where the
LSE $\widehat{\theta}(X)$ may not attain the parametric rate anywhere
on $\Theta$) is the hard case. We will start with the proof of the
easy case first.

\textbf{Easy Case:} For the easy case $\inf_{\theta \in \Theta} t_{\theta} < b := 85$.
Choose $\theta^* \in  \Theta$ such that $t_{\theta^*} \leq b$. Let $\theta_1 \in \Theta$ be any maximizer of $\|\theta^* - \theta\|_2$ as $\theta$ varies over $\{\theta \in \Theta: \|\theta - \theta^*\|_2 \leq 1\}$. Let $w$ be the uniform prior over the two-point set $\{\theta^*, \theta_1\}$. The Bayes risk with respect to $w$ can be easily bounded by below by Le Cam's inequality which gives
\begin{equation*}
  R_{\rm Bayes}(w) \geq \frac{1}{4} \|\theta^* - \theta_1\|_2^2 \left(1 - \|P_{\theta^*} - P_{\theta_1}\|_{TV} \right).
\end{equation*}
Pinsker's inequality (see Lemma 2.5. in \cite{Tsybakov:nonpara}) now
implies
\begin{equation*}
  2 \|P_{\theta^*} - P_{\theta_1} \|^2_{TV} \leq D(P_{\theta^*} \|
  P_{\theta_1}) = \frac{1}{2} \|\theta^* - \theta_1\|_2^2 \leq
  \frac{1}{2}
\end{equation*}
and hence
\begin{equation}\label{rba}
  R_{\rm Bayes}(w) \geq \frac{1}{8} \|\theta^* - \theta_1\|_2^2.
\end{equation}
By the definition of $\theta_1$, we have $\|\theta_1-\theta^*\|_2 \leq 1$. We consider the following two cases by the value of  $\|\theta_1-\theta^*\|_2$.
\begin{enumerate}
\item $\|\theta^* - \theta_1\|_2 = 1$: Here inequality \eqref{rba} gives
  $R_{\rm Bayes}(w) \geq 1/8$. Further, by the assumption $t_{\theta^*}
  \leq b$ and inequality \eqref{1co}, we have ${\mathbb E}_{\theta^*} \|\widehat{\theta}(X) - \theta^*\|_2^2 \leq 150 b^2$. Moreover, by inequality \eqref{smor},
  we have
  \begin{equation*}
{\mathbb E}_{\theta_1} \|\widehat{\theta}(X) - \theta_1\|_2^2 \leq 2 {\mathbb E}_{\theta^*} \|\widehat{\theta}(X)   - \theta^*\|_2^2 + 8 \|\theta^* - \theta_1\|_2^2 \leq 300 b^2 + 8.
  \end{equation*}
We thus have
  \begin{equation*}
\int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2 dw(\theta) \leq 225 b^2 + 4.
  \end{equation*}
This inequality together with $R_{\rm Bayes}(w) \geq 1/8$ allow us to deduce:
  \begin{equation*}
    \frac{1}{1800 b^2 + 32} \int_{\Theta} {\mathbb E}_{\theta}
    \|\widehat{\theta}(X) - \theta\|_2^2 dw(\theta) \leq R_{\rm Bayes}(w).
  \end{equation*}
  This means that $\widehat{\theta}(X)$ is $C$-Bayes with respect to $w$
  with $C = 1/(1800b^2 + 32) \geq 10^{-8}$.
\item $\|\theta^* - \theta_1\|_2 < 1$. Then $\gamma :=
  diam(K) \leq 2$ and $\|\theta^* - \theta_1\|_2 \geq
  \gamma/2$. Inequality \eqref{rba} then gives $R_{\rm Bayes}(w) \geq
  \gamma^2/32$. Also  for every $\theta \in \Theta$, we have
  ${\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2  \leq
  \gamma^2$. These two inequalities imply that
  \begin{equation*}
    \frac{1}{32} \int_{\Theta} {\mathbb E}_{\theta} \|\widehat{\theta}(X) -
    \theta\|_2^2 dw(\theta) \leq  R_{\rm Bayes}(w)
  \end{equation*}
  which means that $\widehat{\theta}(X)$ is $C$-Bayes with respect to $w$ with $C = 1/32$.
\end{enumerate}
Therefore in this easy case, we have proved that $\widehat{\theta}(X)$ is $C$-Bayes for some $C \geq 10^{-8}$.

\textbf{Hard Case:} Here $\inf_{\theta \in \Theta} t_{\theta} \geq b
:= 85$ and let $\rho := 0.03$. We shall first specify the choices for
$\theta^* \in \Theta$ and the prior $w$ supported on the set
$U(\theta^*)$ in \eqref{uri}.  Let $\theta^*$ be chosen so that
\begin{equation}\label{cho}
  m_{\theta^*}(\rho t_{\theta^*}) \geq \sup_{\theta \in \Theta} m_{\theta}(\rho t_{\theta}) - 0.01
\end{equation}
where $m_{\theta}(\cdot)$ is defined in \eqref{mde}. Let $\Psi : {\mathbb R}^n
\mapsto \Theta$ be any measurable mapping such that $\Psi(z)$ is a
maximizer of $\left< z, \theta - \theta^* \right>$  as $\theta$ varies
in $U(\theta^*)$. As in \cite{Sourav14LS}, the prior $w$ is set to be
the   distribution of $\Psi(Z)$ for a standard Gaussian vector $Z$ in
${\mathbb R}^n$. Because of inequalities \eqref{1co} and \eqref{smor},
\begin{equation}\label{les}
  {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta\|_2^2 \leq 2
  {\mathbb E}_{\theta^*} \|\widehat{\theta}(X) - \theta^*\|_2^2 + 8 \|\theta -
  \theta^*\|^2_2  \leq \left( 300 + 8 \rho^2 \right) t^2_{\theta^*}
\end{equation}
for all $\theta \in U(\theta^*)$. This implies \eqref{alla} with $C =
300 + 8 \rho^2$. To complete the proof, it remains therefore to prove
the Bayes risk lower bound \eqref{tosh}.  This is the main part of the
proof. We will use inequality \eqref{eq:I_bayes_chi} which gives the
following lower bound on $R_{\rm Bayes}(w)$:
\begin{equation*}
\frac{1}{2} \sup \left\{t > 0 : \sup_{a \in \Theta} w \{\theta \in
  \Theta:  \|\theta - a\|_2^2 \leq t\} <
  \frac{1}{4(1 + I_f^{\rm up})} \right\},
\end{equation*}
 where $I_f^{\rm up}$ is any upper bound on the chi-squared informativity:
 $I_{\chi^2}(w, \mathcal{P}) := \inf_{Q}  \int_{\Theta}
 \chi^2(P_{\theta} \| Q) dw(\theta)$. Because the prior $w$ is concentrated on the convex set $U(\theta^*)$, we can replace the supremum over $a \in \Theta$ in \eqref{wf} by the supremum over $a \in U(\theta^*)$. This gives the bound
\begin{equation}\label{wf}
\frac{1}{2} \sup \left\{t > 0 : \sup_{a \in U(\theta^*)} w \{\theta
  \in \Theta:  \|\theta - a\|_2^2  \leq t\} < \frac{1}{4(1 + I_f^{\rm up})}
\right\}.
\end{equation}
To obtain $I_f^{\rm up}$, we use the bound given by inequality
\eqref{eq:upper_f_power} with $\alpha = 2$,
 $\Xi := \{0\}$ and $Q_0 := P_{\theta^*}$. This gives
\begin{equation*}
  I_{\chi^2}(w, \mathcal{P}) \leq \int_{\Theta} \chi^2(P_{\theta} \|
  P_{\theta^*}) dw(\theta) \leq \sup_{\theta \in U(\theta^*)}
  \chi^2(P_{\theta} \| P_{\theta^*}) \leq \exp \left(\rho^2
    t^2_{\theta^*} \right) - 1.
\end{equation*}
The last inequality above follows from the expression
$\chi^2(P_{\theta} \| P_{\theta^*}) = \exp(\|\theta -
\theta^*\|_2^2)-1$ and the fact that $\|\theta - \theta^*\|_2 \leq
\rho t_{\theta^*}$ for all $\theta \in U(\theta^*)$. We can therefore
take $1 + I_f^{\rm up}$ to be $\exp(\rho^2 t^2_{\theta^*})$ in \eqref{wf} which
gives the lower bound
\begin{equation}\label{neal}
\frac{1}{2} \sup \left\{t > 0 : \sup_{a \in U(\theta^*)} w \{\theta \in \Theta:  \|\theta - a\|_2^2 \leq t\} < \frac{1}{4} \exp(- \rho^2 t^2_{\theta^*}) \right\}
\end{equation}
for $R_{\rm Bayes}(w)$.
We shall argue below that
\begin{equation}\label{sta}
  \sup_{a \in U(\theta^*)} w \{\theta \in \Theta:  \|\theta - a\|_2^2 \leq t\} < \frac{1}{4} \exp(- \rho^2 t^2_{\theta^*})
\end{equation}
holds for $t := 0.01 \rho^2 t^2_{\theta^*}$. This, together with
\eqref{neal}, will imply \eqref{tosh} and complete the proof. The
argument for \eqref{sta} is similar to that in \cite[Proof of Theorem
1.4]{Sourav14LS} but the constants involved are different and hence we
outline the argument below for the convenience of the reader.

Because $w$ is defined as the distribution of $\Psi(Z)$ which is a
maximizer of $\left<Z, \theta - \theta^* \right>$ over $\theta \in
U(\theta^*)$, we have
\begin{equation*}
  w(A) \leq \P \left\{\sup_{\theta \in A} \left<Z, \theta - \theta^*
    \right> \geq \sup_{\theta \in U(\theta^*)} \left<Z, \theta -
      \theta^* \right> \right\}.
\end{equation*}
Therefore for every $a \in U(\theta^*)$, the prior probability $w \{\theta \in \Theta : \|\theta - a\|^2_2 \leq t\}$ is bounded from above by
\begin{equation*}
  \P \left\{\sup_{\theta \in \Theta : \|\theta - a\|^2_2 \leq t} \left<Z, \theta - \theta^* \right>  \geq \sup_{\theta \in \Theta : \|\theta - \theta^*\| \leq \rho t_{\theta^*}} \left<Z, \theta - \theta^* \right> \right\} .
\end{equation*}
The above probability can be written as $\P \{M_2 + M_3 \geq M_1\}$ where
\begin{equation*}
  M_1 := \sup_{\theta \in \Theta : \|\theta - \theta^*\| \leq \rho t_{\theta^*}} \left<Z, \theta - \theta^* \right>, ~~~ M_2 :=  \sup_{\theta \in \Theta : \|\theta - a\|^2_2 \leq t} \left<Z, \theta - a  \right>
\end{equation*}
and $M_3 := \left<Z, a - \theta^* \right>$. To control the above probability, we first argue that ${\mathbb E} M_1$ is much larger than ${\mathbb E} M_2$. To see this observe first that ${\mathbb E} M_1 = m_{\theta^*}(\rho t_{\theta^*})$ where the function $m$ is defined in \eqref{mde}. Because $\theta^*$ is chosen so that inequality \eqref{cho} is satisfied, we have ${\mathbb E} M_1 =  m_{\theta^*}(\rho t_{\theta^*}) \geq m_a(\rho t_a) - 0.01$. Since $a \in U(\theta^*)$, it  follows that $\|a - \theta^*\|_2 \leq \rho t_{\theta^*} \leq t_{\theta^*}/24$ (remember that $\rho = 0.03$) and consequently, inequality \eqref{smoo} implies that
\begin{equation}\label{ny}
  t_a \geq \frac{11 t_{\theta^*}}{24}.
\end{equation}
The above inequality will be used repeatedly in the sequel. Because ${\mathbb E} M_1 \geq m_a(\rho t_a) - 0.01$ and $t \mapsto m_a(t)$ is non-decreasing, we obtain from \eqref{ny} that
\begin{equation*}
  {\mathbb E} M_1 \geq m_a \left(\frac{11 \rho t_{\theta^*}}{24} \right) - 0.01.
\end{equation*}
On the other hand, ${\mathbb E} M_2 = m_a(\sqrt{t}) = m_a(0.1 \rho t_{\theta^*})$ because $t = 0.01  \rho^2 t^2_{\theta^*}$. We thus have
\begin{equation*}
  {\mathbb E} M_1 - {\mathbb E} M_2 \geq m_a \left(\frac{11 \rho t_{\theta^*}}{24}
  \right) - m_a(0.1 \rho t_{\theta^*}) - 0.01.
\end{equation*}
Now because $s \mapsto m_a(s)$ is concave and $11 \rho t_{\theta^*}/24
\leq \rho t_a \leq t_a$, we get
\begin{equation*}
  m_a \left(\frac{11 \rho t_{\theta^*}}{24} \right) - m_a(0.1 \rho
  t_{\theta^*}) \geq m_a(t_a) - m_a \left(t_a - \frac{11 \rho
      t_{\theta^*}}{24} + 0.1 \rho t_{\theta^*} \right).
\end{equation*}
The right hand side above can be bounded from below via inequality \eqref{inc} (and \eqref{ny} as well as $\rho = 0.03$) which gives
\begin{equation*}
  m_a(t_a) - m_a \left(t_a - \frac{11 \rho
      t_{\theta^*}}{24} + 0.1 \rho t_{\theta^*} \right) \geq \rho t_a t_{\theta^*} \left(\frac{11}{24} - 0.1 \right) \geq \frac{2.838}{576} t^2_{\theta^*}.
\end{equation*}
Putting the above three displayed inequalities together, we obtain ${\mathbb E} M_1 - {\mathbb E} M_2 \geq 2.838 t^2_{\theta^*}/576 - 0.01$. Because $t_{\theta^*} \geq 85$, we deduce
\begin{equation}\label{vam}
  {\mathbb E} M_1 - {\mathbb E} M_2 \geq \left(\frac{2.838}{576} - \frac{0.01}{85^2} \right) t^2_{\theta^*} \geq 5 \rho^2 t^2_{\theta^*}.
\end{equation}
We now bound the probability $\P \{M_2 + M_3 \geq M_1 \}$ in the following way. Because  of \eqref{vam},  it follows that if the event $M_2 +
M_3 \geq M_1$ is satisfied, then at least one of the three events $M_1
- {\mathbb E} M_1 > -5\rho^2t^2_{\theta^*}/3$, $M_2 - {\mathbb E} M_2 \leq 5 \rho^2 t^2_{\theta^*}/3$ and  $M_3 \leq 5 \rho^2t^2_{\theta^*}/3$ must be violated. As a result, the probability $\P \{M_2 + M_3 \geq M_1\}$ is bounded from above by
\begin{equation*}
\P \left\{M_1 - {\mathbb E} M_1 \leq - 5 \rho^2 t^2_{\theta^*}/3 \right\} + \P \left\{M_2 - {\mathbb E} M_2 > 5 \rho^2t^2_{\theta^*}/3 \right\} + \P \left\{M_3 > 5 \rho^2 t^2_{\theta^*}/3 \right\}.
\end{equation*}
Each of the probabilities above can be easily bounded by gaussian concentration. Indeed, it is easy to check that (a) $M_1$, as a function of $Z$, is Lipschitz with constant $\rho t_{\theta^*}$, (b) $M_2$, as a function of $Z$, is Lipschitz with constant $\sqrt{t} = 0.1 \rho t_{\theta^*}$ and (c) $M_3$, as a function of $Z$,  is Lipschitz with constant $\|a - \theta^*\| \leq \rho t_{\theta^*}$. As a result, each of the above probabilities is bounded from above by $\exp (-25 \rho^2 t^2_{\theta^*}/18)$. Hence $\P \{M_2 + M_3 \geq M_1\}$ is bounded from above by $3 \exp (-25 \rho^2 t^2_{\theta^*}/18)$ which means that
\begin{equation*}
  \sup_{a \in U(\theta^*)} w \{\theta \in \Theta:  \|\theta - a\|_2^2 \leq t\} \leq 3 \exp \left(-\frac{25 \rho^2 t^2_{\theta^*}}{18} \right).
\end{equation*}
Because $\rho = 0.03$ and $t_{\theta^*} \geq 85$, it is elementary to
check that the right hand side above is strictly smaller than
$\exp(-\rho^2 t^2_{\theta^*})/4$. We have therefore proved
\eqref{sta}. Because $t = 0.01 \rho^2 t_{\theta^*}^2$, inequality
\eqref{neal} implies that
\begin{equation}\label{sa1}
  R_{\rm Bayes}(w) \geq  \frac{0.01 \rho^2}{2}  t^2_{\theta^*}
\end{equation}
On the other hand, for the LSE $\widehat{\theta}(X)$, inequality \eqref{les} gives
\begin{equation}\label{sa2}
  \int {\mathbb E}_{\theta} \|\widehat{\theta}(X) - \theta \|_2^2 dw(\theta) \leq (300 + 8 \rho^2) t^2_{\theta^*}.
\end{equation}
Putting together \eqref{sa1} and \eqref{sa2}, we obtain
\begin{equation*}
\frac{0.01 \rho^2}{600 + 16 \rho^2} \int_{\Theta} {\mathbb E}_{\theta}
\|\widehat{\theta}(X) -  \theta\|_2^2 dw(\theta) \leq R_{\rm Bayes}(w).
\end{equation*}
The constant above is at least $10^{-8}$ which proves that $\widehat{\theta}(X)$ is $C$-Bayes for some $C \geq 10^{-8}$. This completes the proof of Theorem \ref{jee}.

\newpage

\bibliographystyle{abbrvnat}

redpajama_set_name: RedPajamaArXiv