Lower bounds for the minimax risk using $f$-divergences and applications

I Introduction

where the infimum is over all measurable functions $\hat{\theta}:{\mathcal{X}}\rightarrow{\mathcal{A}}$ and the expectation is taken under the assumption that $X$ is distributed according to $P_{\theta}$.

the infimum being over all estimators $T$ taking values in $F$. The proof of this inequality relies on the triangle inequality satisfied by the metric $\rho$ and can be found, for example, in [1, Page 1570, Proof of Theorem 1] (Let us note, for the convenience of the reader, that the notation employed by Yang and Barron differs from ours in that they use $d$ for the metric $\rho$, $\epsilon_{n,d}$ for our $\eta$ and $N_{\epsilon_{n},d}$ for the finite set $F$. Also the proof in involves a positive constant $A$ which can be taken to be 1 for our purposes. The constant $A$ arises because Yang and Barron do not require that $d$ is a metric but rather require it to satisfy a weaker local triangle inequality which involves the constant $A$.)

The next step is to note that $r$ is bounded from below by Bayes risks. Let $w$ be a probability measure on $F$. The Bayes risk $\bar{r}_{w}$ corresponding to the prior $w$ is defined by

where $w_{\theta}:=w\left\{\theta\right\}$ and the infimum is over all estimators $T$ taking values in $F$. When $w$ is the discrete uniform probability measure on $F$, we simply write $\bar{r}$ for $\bar{r}_{w}$. The trivial inequality $r\geq\bar{r}_{w}$ implies that lower bounds for $\bar{r}_{w}$ are automatically lower bounds for $r$.

if $P$ is absolutely continuous with respect to $Q$ and $\infty$ otherwise.

Our proof of Theorem II.1 presented in section II is extremely simple. It just relies on the convexity of the function $f$ and the standard result that $\bar{r}_{w}$ has the following exact expression:

where $p_{\theta}$ denotes the density of $P_{\theta}$ with respect to a common dominating measure $\mu$ (for example, one can take $\mu:=\sum_{\theta\in F}P_{\theta}$).

We show that Fano’s inequality is a special case (see Example II.4) of Theorem II.1, obtained by taking $f(x)=x\log x$. Fano’s inequality is used extensively in the nonparametric statistics literature for obtaining minimax lower bounds, important works being . In the special case when $F$ has only two points, Theorem II.1 gives a sharp inequality relating the total variation distance between two probability measures to $f$-divergences (see Corollary II.3). When $f(x)=x\log x$, Corollary II.3 implies an inequality due to Topsøe from which Pinsker’s inequality can be derived. Thus Theorem II.1 can be viewed as a generalization of both Fano’s inequality and Pinsker’s inequality.

The bound given by Theorem II.1 involves the quantity $J_{f}:=\inf_{Q}\sum_{\theta\in F}D_{f}(P_{\theta}||Q)/|F|$, where the infimum is over all probability measures $Q$ and $|F|$ denotes the cardinality of the finite set $F$. It is usually not possible to calculate $J_{f}$ exactly and in section III, we provide upper bounds for $J_{f}$. The main result of this section, Theorem III.1, provides an upper bound for $J_{f}$ based on approximating the set of $|F|$ probability measures $\left\{P_{\theta},\theta\in F\right\}$ by a smaller set of probability measures. This result is motivated by and a generalization to $f$-divergences of a result of Yang and Barron for the Kullback-Leibler divergence.

In section IV, we use the inequalities proved in sections II and III to obtain minimax lower bounds involving only global metric entropy attributes. Of all the lower bounds presented in this paper, Theorem IV.1, the main result of section IV, is the most application-ready method. In order to apply this in a particular situation, one only needs to determine suitable bounds on global covering and packing numbers of the parameter space $\Theta$ and the space of probability measures $\left\{P_{\theta},\theta\in\Theta\right\}$ (see section V for an application).

Although the main results of sections II and III hold true for all $f$-divergences, Theorem IV.1 is stated only for the Kullback-Leibler divergence, chi-squared divergence and the divergences based on $f(x)=x^{l}-1$ for $l>1$. The reason behind this is that Theorem IV.1 is intended for applications where it is usually the case that the underlying probability measures $P_{\theta}$ are product measures and divergences such as the Kullback-Leibler divergence and chi-squared divergence can be computed for product probability measures.

The inequalities given by Theorem IV.1 for the chi-squared divergence and divergences based on $f(x)=x^{l}-1$ for $l>1$ are new while the inequality for the Kullback-Leibler divergence is due to Yang and Barron . There turn out to be qualitative differences between these inequalities in the case of estimation problems involving finite dimensional parameters where the inequality based on chi-squared divergence gives minimax lower bounds having the optimal rate while the one based on the Kullback-Leibler divergence only results in sub-optimal lower bounds. We shall explain this happening in section IV by means of elementary examples.

We shall present two applications of our bounds. In section V, we shall prove a new lower bound for the minimax risk in the problem of estimation/reconstruction of a $d$-dimensional convex body from noisy measurements of its support function in $n$ directions. In section VI, we shall provide a different proof of a recent result by Cai, Zhang and Zhou on covariance matrix estimation.

We shall prove a lower bound for $\bar{r}_{w}$ defined in (2) in terms of $f$-divergences. We shall assume that the $N:=|F|$ probability measures $P_{\theta},\theta\in F$ are all dominated by a sigma finite measure $\mu$ with densities $p_{\theta},\theta\in F$. In terms of these densities, $\bar{r}_{w}$ has the exact expression given in (3). A trivial consequence of (3) that we shall often use in the sequel is that $\bar{r}\leq 1-1/N$ (recall that $\bar{r}$ is $\bar{r}_{w}$ in the case when $w$ is the uniform probability measure on $F$).

where $W:=\int_{{\mathcal{X}}}w_{T(x)}dQ(x)$. In particular, taking $w$ to be the uniform probability measure, we get that

The proof of this theorem relies on a simple application of the convexity of $f$ and it is presented below.

We may assume that all the weights $w_{\theta}$ are strictly positive and that the probability measure $Q$ has a density $q$ with respect to $\mu$. We start with a simple inequality for nonnegative numbers $a_{\theta},\theta\in F$ with $\tau:=\arg\max_{\theta\in F}\left\{w_{\theta}a_{\theta}\right\}$. We first write

and then use the convexity of $f$ to obtain that the quantity $\sum_{\theta}w_{\theta}f(a_{\theta})$ is bounded from below by

We now fix $x\in{\mathcal{X}}$ such that $q(x)>0$ and apply the inequality just derived to $a_{\theta}:=p_{\theta}(x)/q(x)$. Note that in this case $\tau=T(x)$. We get that

Integrating inequality (6) with respect to the probability measure $Q$, we get that the term $\sum_{\theta\in F}w_{\theta}D_{f}(P_{\theta}||Q)$ is bounded from below by

Let $Q^{\prime}$ be the probability measure on ${\mathcal{X}}$ having the density $q^{\prime}(x):=w_{T(x)}q(x)/W$ with respect to $\mu$. Clearly

which, by Jensen’s inequality, is larger than or equal to $Wf((1-\bar{r}_{w})/W)$. It follows similarly that

This completes the proof of inequality (4). When $w$ is the uniform probability measure on the finite set $F$, it is obvious that $W$ equals $1/N$ and this leads to inequality (5). ∎

Let us denote the function of $\bar{r}$ on the right hand side of (5) by $g$:

Inequality (5) provides an implicit lower bound for $\bar{r}$. This is because $\bar{r}\in[0,1-1/N]$ and $g$ is non-increasing on $[0,1-1/N]$ (as can be seen in the proof of the next corollary in the case when $f$ is differentiable; if $f$ is not differentiable, one needs to work with right and left derivatives which exist for convex functions).

The convexity of $f$ also implies trivially that $g$ is convex, which can be used to convert the implicit bound (5) into an explicit lower bound. This is the content of the following corollary. We assume differentiability for convenience; to avoid working with one-sided derivatives.

Suppose that $f:[0,\infty)$ is a differentiable convex function and that $g$ is defined as in (7). Then, for every $a\in[0,1-1/N]$, we have

where the infimum is over all probability measures $Q$.

Fix a probability measure $Q$. Inequality (5) says that $\sum_{\theta\in F}D_{f}(P_{\theta}||Q)\geq g(\bar{r})$. The convexity of $f$ implies that $g$ is also convex and hence, for every $a\in[0,1-1/N]$, we can write

Because $g$ is convex, we have $g^{\prime}(a)\leq g^{\prime}(1-1/N)=0$ for $a\leq 1-1/N$ (this proves that $g$ is non-increasing on $[0,1-1/N]$). Therefore, by rearranging (9), we obtain (8). ∎

Let us now provide an intuitive understanding of inequality (5). When the probability measures $P_{\theta},\theta\in F$ are tightly packed i.e., when they are close to one another, it is hard to distinguish between them (based on the observation $X$) and hence, the testing Bayes risk $\bar{r}$ will be large. On the other hand, when the probability measures are well spread out, it is easy to distiguish between them and therefore, $\bar{r}$ will be small. Indeed, $\bar{r}$ takes on its maximum value of $1-1/N$ when the probability measures $P_{\theta},\theta\in F$ are all equal to one another and it takes on its smallest value of 0 when $\max p_{\theta}=\sum p_{\theta}$ i.e., when $P_{\theta},\theta\in F$ are all mutually singular.

Now, one way of measuring how packed/spread out the probability measures $P_{\theta},\theta\in F$ are is to consider the quantity $\inf_{Q}\sum_{\theta\in F}D_{f}(P_{\theta}||Q)$, which is small when the probabilities are tightly packed and large when they are spread out. It is therefore reasonable to expect a connection between this quantity and $\bar{r}$. Inequality (5) makes this connection explicit and precise. The fact that the function $g$ in (7) is non-increasing means that when $\inf_{Q}\sum_{\theta\in F}D_{f}(P_{\theta}||Q)$ is small, the lower bound on $\bar{r}$ implied by (5) is large and when $\inf_{Q}\sum_{\theta\in F}D_{f}(P_{\theta}||Q)$ is large, the lower bound on $\bar{r}$ is small.

Theorem II.1 implies the following corollary which provides sharp inequalities between total variation distance and $f$-divergences. The total variation distance between two probability measures is defined as half the $L^{1}$ distance between their densities.

where the infimum is over all probability measures $Q$. Moreover this inequality is sharp in the sense that for every $V\in$, the infimum of the left hand side of (10) over all probability measures $P_{1}$ and $P_{2}$ with total variation distance $V$ equals the right hand side of (10).

In the setting of Theorem II.1, suppose that $F=\left\{1,2\right\}$ and that the two probability measures are $P_{1}$ and $P_{2}$ with densities $p_{1}$ and $p_{2}$ respectively. Since $2\max(p_{1},p_{2})$ equals $p_{1}+p_{2}+|p_{1}-p_{2}|$, it follows that $2\bar{r}$ equal $1-V$. Inequality (10) is then a direct consequence of inequality (5).

The following example shows that (10) is sharp. Fix $V\in$. Consider the space ${\mathcal{X}}=\left\{1,2\right\}$ and define the probabilities $P_{1}$ and $P_{2}$ by $P_{1}\left\{1\right\}=P_{2}\left\{2\right\}=(1+V)/2$ and of course $P_{1}\left\{2\right\}=P_{2}\left\{1\right\}=(1-V)/2$. Then the total variation distance between $P_{1}$ and $P_{2}$ equals $V$. Also if we take $Q$ to be the uniform probability measure $Q\left\{1\right\}=Q\left\{2\right\}=1/2$, then one sees that $D_{f}(P_{1}||Q)+D_{f}(P_{2}||Q)$ equals $f(1+V)+f(1-V)$ which is same as the right hand side in (10). ∎

What we have actually shown in the above proof is that inequality (10) is sharp for the space ${\mathcal{X}}=\left\{1,2\right\}$. However, the result holds in more general spaces as well. For example, if the space is such that there exist two disjoint nonempty subsets $A_{1}$ and $A_{2}$ and two probability measures $\nu_{1}$ and $\nu_{2}$ concentrated on $A_{1}$ and $A_{2}$ respectively, then we can define $P_{1}:=\nu_{1}(1+V)/2+\nu_{2}(1-V)/2$ and $P_{2}:=\nu_{1}(1-V)/2+\nu_{2}(1+V)/2$ so that $V(P_{1},P_{2})=V$ and (10) becomes an equality (with $Q=\nu_{1}/2+\nu_{2}/2$).

There exist many inequalities in the literature relating the $f$-divergence of two probability measures to their total variation distance. We refer the reader to for the sharpest results in this direction and for earlier references. Inequality (10), which is new, can be trivially converted into an inequality between $D_{f}(P_{1}||P_{2})$ and $V$ by taking $Q=P_{2}$. The resulting inequality will not be sharp however and hence will be inferior to the inequalities in . As stated, inequality (10) is a sharp inequality relating not $D_{f}(P_{1}||P_{2})$ but a symmetrized form of $f$-divergence between $P_{1}$ and $P_{2}$ to their total variation distance.

In the remainder of this section, we shall apply Theorem II.1 and Corollary II.3 to specific $f$-divergences.

Let $f(x):=x\log x$. Then $D_{f}(P||Q)$ becomes the Kullback-Leibler divergence $D(P||Q)$ between $P$ and $Q$. The quantity $\sum_{\theta\in F}D(P_{\theta}||Q)$ is minimized when $Q=\bar{P}:=(\sum_{\theta\in F}P_{\theta})/N$. This is a consequence of the following identity which is sometimes referred to as the compensation identity, see for example [12, Page 1603]:

Using inequality (5) with $Q=\bar{P}=(\sum_{\theta\in F}P_{\theta})/N$, we obtain

The quantity on the left hand side is known as the Jensen-Shannon divergence. It is also Shannon’s mutual information [16, Page 19] between the random parameter $\theta$ distributed according to the uniform distribution on $F$ and the observation $X$ whose conditional distribution given $\theta$ equals $P_{\theta}$. The above inequality is stronger than the version of Fano’s inequality commonly used in nonparametric statistics. It is implicit in [17, Proof of Theorem 1] and is explicitly stated in a slightly different form in [18, Theorem 3]. The proof in is based on the Fano’s inequality from information theory [16, Theorem 2.10.1]. To obtain the usual form of Fano’s inequality as used in statistics, we turn to inequality (8). For $a_{0}:=(N-1)/(2N-1)\leq 1-1/N$ and the function $g$ in (7), it can be checked that

and $g^{\prime}(a_{0})=-N\log N$. Using inequality (8) with $a=a_{0}$, we get that

Since $\log((2N-1)/N)\leq\log 2$, we have obtained

which is the commonly used version of Fano’s inequality.

By taking $f(x)=x\log x$ in Corollary II.3, we get that

This inequality relating the Jensen-Shannon divergence between two probability measures (also known as capacitory discrimination) to their total variation distance is due to Topsøe [12, Equation (24)]. Our proof is slightly simpler than Topsøe’s. Topsøe also explains how to use this inequality to deduce Pinsker’s inequality with sharp constant: $D(P_{1}||P_{2})\geq 2V^{2}$. Thus, Theorem II.1 can be considered as a generalization of both Fano’s inequality and Pinsker’s inequality to $f$-divergences.

Let $f(x)=x^{2}-1$. Then $D_{f}(P||Q)$ becomes the chi-squared divergence $\chi^{2}(P||Q):=\int p^{2}/q-1$. The function $g$ can be easily seen to satisfy

Because $\bar{r}\leq 1-1/N$, we can invert the inequality $\inf_{Q}\sum_{\theta\in F}\chi^{2}(P_{\theta}||Q)\geq g(\bar{r})$ to obtain

Also it follows from Corollary II.3 that for every two probability measures $P_{1}$ and $P_{2}$,

The weaker inequality $\chi^{2}(P_{1}||\bar{P})+\chi^{2}(P_{2}||\bar{P})\geq 2V^{2}$ can be found in [12, Equation (11)].

Let $f(x)=1-\sqrt{x}$. Then $D_{f}(P||Q)=1-\int\sqrt{pq}d\mu=H^{2}(P,Q)/2$, where $H^{2}(P,Q)=\int(\sqrt{p}-\sqrt{q})^{2}d\mu$ is the square of the Hellinger distance between $P$ and $Q$. It can be shown, using the Cauchy-Schwarz inequality, that $\sum_{\theta\in F}D_{f}(P_{\theta}||Q)$ is minimized when $Q$ has a density with respect to $\mu$ that is proportional to $(\sum_{\theta\in F}\sqrt{p_{\theta}})^{2}$. Indeed if $u:=\sum_{\theta\in F}\sqrt{p_{\theta}}$, then

by the Cauchy-Schwarz inequality with equality when $q$ is proportional to $u^{2}$. The inequality (5) can then be simplified to

We let $h^{2}:=\sum_{\theta,\theta^{\prime}}H^{2}(P_{\theta},P_{\theta^{\prime}})/N^{2}$ so that $\int u^{2}d\mu=N^{2}(1-h^{2}/2)$. As a consequence, we have $\int u^{2}d\mu\leq N^{2}$. Also note that $\int u^{2}d\mu\geq\int(\sum_{\theta}p_{\theta})d\mu=N$. Therefore, the right hand side of the inequality (14) lies between 1 and $\sqrt{N}$. On the other hand, it can be checked that, as a function of $\bar{r}$, the left hand side of (14) is strictly increasing from $1$ at $\bar{r}=0$ to $\sqrt{N}$ at $\bar{r}=1-1/N$. It therefore follows that inequality (14) is equivalent to $\bar{r}\geq\breve{r}$ where $\breve{r}\in[0,1-1/N]$ is the solution to the equation obtained by replacing the inequality in (14) with an equality.

This equation can be solved in the usual way by squaring etc., until we get a quadratic equation in $\bar{r}$ which can be solved resulting in two solutions. One of the two solutions can be discarded by continuity considerations (the solution has to be continuous in $\int u^{2}d\mu/N$) and the fact that $\bar{r}\leq 1-1/N$. The other solution equals $\breve{r}$ and is given by

In the case when $N=2$ and $F=\left\{1,2\right\}$, it is clear that $h^{2}=(H^{2}(P_{1},P_{2})+H^{2}(P_{2},P_{1}))/4=H^{2}(P_{1},P_{2})/2$. Also since $2\bar{r}$ equals $1-V$, where $V$ denotes the total variation distance between $P_{1}$ and $P_{2}$, the above inequality implies that for every pair of probability measures $P_{1}$ and $P_{2}$, we have

This inequality is usually attributed to Le Cam .

Let $f(x)=|x-1|/2$. Then $D_{f}(P||Q)$ becomes the total variation distance between $P$ and $Q$. The function $g$ satisfies

Since $\bar{r}\leq 1-1/N$, we have $N(1-\bar{r})\geq 1$ and $N\bar{r}/(N-1)\leq 1$ so that the above expression for $g(\bar{r})$ simplifies to $N-1-N\bar{r}$. Inequality (5), therefore, results in

where $V_{\theta}$ denotes the total variation distance between $P_{\theta}$ and $Q$.

Let $f(x)=x^{l}-1$ where $l>1$. The case $l=2$ has already been considered in Example II.5. The function $g$ has the expression

It therefore follows that $\inf_{Q}\sum_{\theta\in F}D_{f}(P_{\theta}||Q)\geq g(\bar{r})\geq N^{l}(1-\bar{r})^{l}-N$ which results in the inequality

When $l=2$, inequality (15) results in a bound that is weaker than inequality (12) although for large $N$, the two bounds are almost the same.

Let $f(x)=-\log x$ so that $D_{f}(P||Q)=D(Q||P)$. Then from Corollary II.3, we get that for every two probability measures $P_{1}$ and $P_{2}$,

Unlike Example II.4, it is not true that $D(Q||P_{1})+D(Q||P_{2})$ is minimized when $Q=\bar{P}$. This is easy to see because $D(\bar{P},P_{1})+D(\bar{P},P_{2})$ is finite only when $P_{1}<<P_{2}$ and $P_{2}<<P_{1}$. By taking $Q=P_{1}$ and $Q=P_{2}$, we get that

The above inequality, which is clearly weaker than inequality (16), can also be found in [20, Proof of Lemma 2.6].

In order to apply the minimax lower bounds of the previous section in practical situations, we must be able to bound the quantity $J_{f}:=\inf_{Q}\sum_{\theta\in F}D_{f}(P_{\theta}||Q)/N$ from above. We shall provide such bounds in this section. It should be noted that for some functions $f$, it may be possible to calculate $J_{f}$ directly. For example, the quantity $\inf_{Q}\sum_{\theta\in F}H^{2}(P_{\theta},Q)$ can be written in terms of pairwise Hellinger distances (Example II.6) and may be calculated exactly for certain probability measures $P_{\theta}$. This is not the case for most functions $f$ however.

The following is a simple upper bound for $J_{f}$ which, in the case when $f(x)=x\log x$ or Kullback-Leibler divergence, has been frequently used in the literature (see for example and ).

We observed in section II that $J_{f}$ measures the spread of the probability measures $P_{\theta},\theta\in F$ i.e., how tightly packed/spread out they are. It should be clear that the simple bound $\max_{\theta,\theta^{\prime}}D_{f}(P_{\theta}||P_{\theta^{\prime}})$ does not adequately describe this aspect of $P_{\theta},\theta\in F$ and it is therefore desirable to look for alternative upper bounds for $J_{f}$ that capture the notion of spread in a better way.

In the case of the Kullback-Leibler divergence, Yang and Barron [1, Page 1571] provided such an upper bound for $J_{f}$. They showed that for any finite set $\left\{Q_{\alpha}:\alpha\in G\right\}$ of probability measures,

Let us now take a closer look at this beautiful inequality of Yang and Barron . The $|G|$ probability measures $Q_{\alpha},\alpha\in G$ can be viewed as an approximation of the $N$ probability measures $P_{\theta},\theta\in F$. The term $\max_{\theta}\min_{\alpha}D(P_{\theta}||Q_{\alpha})$ then denotes the approximation error, measured via the Kullback-Leibler divergence. The right hand side of inequality (17) can therefore be made small if it is possible to choose not too many probability measures $Q_{\alpha}$ which well approximate the given set of probability measures $P_{\theta}$.

It should be clear how the upper bound (17) measures the spread of the probability measures $P_{\theta},\theta\in F$. If the probabilities are tightly packed, it is possible to approximate them well with a smaller set of probabilities and then the bound will be small. On the other hand, if $P_{\theta},\theta\in F$ are well spread out, we need more probability measures for approximation and consequently the bound will be large.

Another important aspect of inequality (17) is that it can be used to obtain lower bounds for $R$ depending only on global metric entropy properties of the parameter space $\Theta$ and the space of probability measures $\left\{P_{\theta},\theta\in\Theta\right\}$ (see section IV). On the other hand, the evaluation of inequalities resulting from the use of $J_{f}\leq\max_{\theta,\theta^{\prime}}D(P_{\theta}||P_{\theta^{\prime}})$ requires knowledge of both metric entropy and the existence of certain special localized subsets. We refer the reader to for a detailed discussion of these issues.

The goal of this section is to generalize inequality (17) to $f$-divergences. The main result is given below. In section IV, we shall use this theorem along with the results of the previous section to come up with minimax lower bounds involving global entropy properties.

Let $\bar{Q}:=\sum_{\alpha\in G}Q_{\alpha}/M$ and $\bar{q}:=\sum_{\alpha\in G}q_{\alpha}/M$. Clearly for each $\theta\in F$, we have

The convexity of $f$ implies that the map $y\mapsto y[f(a/y)-f(0)]$ is non-increasing for every nonnegative $a$. Using this and the fact that $\bar{q}\geq q_{j(\theta)}/M$, we get that for every $\theta\in F$,

Inequality (18) now follows as a consequence of the inequality $J_{f}\leq\sum_{\theta\in F}D_{f}(P_{\theta}||\bar{Q})/N$. ∎

In the following examples, we shall demonstrate that Theorem III.1 is indeed a generalization of the bound (17) to $f$-divergences. We shall also see that Theorem III.1 results in inequalities that have the same qualitative structure as (17), at least for the convex functions $f$ of interest such as $x^{l}-1,l>1$ and $(\sqrt{x}-1)^{2}$.

Let $f(x)=x\log x$. In this case, $J_{f}$ equals $\sum_{\theta\in F}D(P_{\theta}||\bar{P})/N$ and invoking inequality (18), we get that

Inequality (17) now follows if we choose $j(\theta):=\arg\min_{\alpha\in G}D(P_{\theta}||Q_{\alpha})$. Hence Theorem III.1 is indeed a generalization of (17).

Let $f(x)=x^{l}-1$ for $l>1$. Applying inequality (18), we get that

By choosing $j(\theta)=\arg\min_{\alpha\in G}D_{f}(P_{\theta}||Q_{\alpha})$, we get that

In particular, in the case of the chi-squared divergence i.e., when $l=2$, the quantity $J_{f}=\inf_{Q}\sum_{\theta\in F}\chi^{2}(P_{\theta}||Q)/N$ is bounded from above by

Just like (17), each of the above two inequalities is also a function of the number of probability measures $Q_{\alpha}$ and the approximation error which is now measured in terms of the chi-squared divergence.

Let $f(x)=(\sqrt{x}-1)^{2}$ so that $D_{f}(P||Q)=H^{2}(P,Q)$, the square of the Hellinger distance between $P$ and $Q$. Using inequality (18), we get that

If we now choose $j(\theta):=\arg\min_{\alpha\in G}H^{2}(P_{\theta},Q_{\alpha})$, then we get

Notice, once again, the trade-off between $M$ and the approximation error which is measured in terms of the Hellinger distance.

IV Bounds involving global entropy

In this section, we shall apply the results of the previous two sections to obtain lower bounds for the minimax risk $R$ depending only on global metric entropy properties of the parameter space. The theorem is stated below, but we shall need to establish some notation first.

For $\eta>0$, let $N(\eta)\geq 1$ be a real number for which there exists a finite subset $F\subseteq\Theta$ with cardinality $\geq N(\eta)$ satisfying $\rho(\theta,\theta^{\prime})\geq\eta$ whenever $\theta,\theta^{\prime}\in F$ and $\theta\neq\theta^{\prime}$. In other words, $N(\eta)$ is a lower bound on the $\eta$-packing number of the metric space $(\Theta,\rho)$.

We note here that the probability measures $Q_{\alpha},\alpha\in G$ in the definition of $M_{f}(\epsilon,S)$ do not need to be included in the set $\left\{P_{\theta},\theta\in\Theta\right\}$ and the set $G$ just denotes the index set and need not have any relation to $S$ or $\Theta$.

We now fix $\epsilon>0$ and use the definition of $M_{C}(\epsilon,F)$ to get a finite set $G$ with cardinality $\leq M_{C}(\epsilon,F)$ and probability measures $Q_{\alpha},\alpha\in G$ such that $\sup_{\theta\in S}\min_{\alpha\in G}\chi^{2}(P_{\theta}||Q_{\alpha})\leq\epsilon^{2}$. We then use inequality (20) to get that

The proof is complete by the trivial observation $M_{C}(\epsilon,F)\leq M_{C}(\epsilon,\Theta)$. ∎

The inequality (21) is due to Yang and Barron [1, Proof of Theorem 1]. In their paper, Yang and Barron mainly considered the problem of estimation from $n$ independent and identically distributed observations. However their method results in inequality (21) which applies to every estimation problem. Inequalities (22) and (23) are new.

Note that the lower bounds for $R$ given in Theorem IV.1 all depend only on the quantities $N(\eta)$ and $M_{f}(\epsilon,\Theta)$, which describe packing/covering properties of the entire parameter space $\Theta$. Consequently, these inequalities only involve global metric entropy properties. This is made possible by the use of inequalities in Theorem III.1. In applications of Fano’s inequality (11) with the standard bound $J_{f}\leq\max_{\theta,\theta^{\prime}\in F}D(P_{\theta}||P_{\theta^{\prime}})$ as well as in the application of other popular methods for obtaining minimax lower bounds like Le Cam’s method or Assouad’s lemma, one needs to construct the finite subset $F$ of the parameter space in a very special way: the parameter values in $F$ should be reasonably separated in the metric $\rho$ and also, the probability measures $P_{\theta},\theta\in F$ should be close in some probability metric. In contrast, the application of Theorem IV.1 does not require the construction of such a special subset $F$.

Yang and Barron have successfully applied inequality (21) to achieve minimax lower bounds of the optimal rate for many nonparametric density estimation and regression problems where $N(\eta)$ and $M_{KL}(\epsilon,\Theta)$ can be deduced from standard results in approximation theory for function classes. We refer the reader to for examples. In some of these examples, inequality (22) can also be applied to get optimal lower bounds. In section V, we shall employ inequality (22) to obtain a new minimax lower bound in the problem of reconstructing convex bodies from noisy support function measurements.

But prior to that, let us assess the performance of inequality (22) in certain standard parametric estimation problems. In these problems, an interesting contrast arises between the two minimax lower bounds (21) and (22): the inequality (21) only results in a sub-optimal lower bound on the minimax risk (this observation, due to Yang and Barron [1, Page 1574], is also explained in Example IV.2 below) while (22) produces rate-optimal lower bounds.

Our intention here is to demonstrate, with the help of the subsequent three examples, that inequality (22) works even for finite dimensional parametric estimation problems, a scenario in which it is already known [1, Page 1574] that inequality (21) fails. Of course, obtaining optimal minimax rates in such problems is facile in most situations. For example, a two-points argument based on Hellinger distance gives the optimal rate, as is widely recognized since Le Cam . But the point here is that even in finite dimensional situations, global metric entropy features are adequate for obtaining rate-optimal minimax lower bounds. This is contrary to the usual claim that in order to establish rate-optimal lower bounds in parametric settings, one needs more information than global entropy characteristics [1, Page 1574].

Suppose that $m_{\theta}$ equals the normal distribution with mean $\theta$ and variance 1. It can be readily verified that, for $\theta,\theta^{\prime}\in\Theta$, one has

It follows directly that $D(P_{\theta}||P_{\theta^{\prime}})\leq\epsilon^{2}$ if and only if $|\theta-\theta^{\prime}|\leq\sqrt{2}\epsilon/\sqrt{n}$ and $\chi^{2}(P_{\theta}||P_{\theta^{\prime}})\leq\epsilon^{2}$ if and only if $|\theta-\theta^{\prime}|\leq\sqrt{\log(1+\epsilon^{2})}/\sqrt{n}$. As a result, we can take

for $\epsilon\leq\epsilon_{0}$. Now, inequality (21) says that the minimax risk $R_{n}$ satisfies

The function $\epsilon\mapsto\epsilon^{2}-\log\epsilon$ is minimized on $[0,\epsilon_{0}]$ at, say, $\epsilon=\epsilon_{1}$ and we then get

where $c_{3}$ is a function of $c_{2}$ and $\epsilon_{1}$. We now note that when $\eta=c/\sqrt{n}$ for a constant $c$, the quantity inside the parantheses on the right hand side of (25) converges to 0 as $n$ goes to $\infty$. This means that inequality (21) only gives lower bounds of inferior order for $R_{n}$, the optimal order being, of course, $1/n$.

On the other hand, we shall show below that inequality (22) gives $R_{n}\geq c/n$ for a positive constant $c$. Indeed, inequality (22) says that

Taking $\epsilon=\epsilon_{0}$ and $\eta=c_{3}/\sqrt{n}$, we get

where $c_{4}$ depends only on $c_{1},c_{2}$ and $\epsilon_{0}$. Hence by choosing $c_{3}$ small, we get that $R_{n}\geq c/n$ for all large $n$.

Suppose that $\Theta$ is a compact interval of the positive real line that is bounded away from zero and suppose that $m_{\theta}$ denotes the uniform distribution on $[0,\theta]$. It is then elementary to check that the chi-squared divergence between $P_{\theta}$ and $P_{\theta^{\prime}}$ equals $(\theta^{\prime}/\theta)^{n}-1$ if $\theta\leq\theta^{\prime}$ and $\infty$ otherwise. It follows accordingly that $\chi^{2}(P_{\theta}||P_{\theta^{\prime}})\leq\epsilon^{2}$ provided

Because the parameter space is a compact interval bounded away from zero, in order to ensure (27), it is enough to require that $0\leq\theta^{\prime}-\theta\leq c_{2}\log(1+\epsilon^{2})/n$. Therefore, we can take

for $\epsilon\leq\epsilon_{0}$. Inequality (22) now implies that

Taking $\epsilon=\epsilon_{0}$ and $\eta=c_{4}/n$, we get that

where $c_{5}$ depends only on $c_{1},c_{3}$ and $\epsilon_{0}$. Hence by choosing $c_{4}$ sufficiently small, we get that $R_{n}\geq c/n^{2}$ for all large $n$. This is the optimal minimax rate for this problem as can be seen by estimating $\theta$ by the maximum of the observations.

Suppose that $m_{\theta}$ denotes the uniform distribution on the interval $[\theta,\theta+1]$. We shall argue that $M_{C}(\epsilon,\Theta)$ can be chosen to be

for a positive constant $c_{2}$ at least for large $n$. To see this, let us define $\epsilon^{\prime}$ so that $2\epsilon^{\prime}:=(1+\epsilon^{2})^{1/n}-1$ and let $G$ denote an $\epsilon^{\prime}$-grid of points in the interval $\Theta$; $G$ would contain at most $c_{2}/\epsilon^{\prime}$ points when $\epsilon\leq\epsilon_{0}$. For a point $\alpha$ in the grid, let $Q_{\alpha}$ denote the $n$-fold product of the uniform distribution on the interval $[\alpha,\alpha+1+2\epsilon^{\prime}]$. Now, for a fixed $\theta\in\Theta$, let $\alpha$ denote the point in the grid such that $\alpha\leq\theta\leq\alpha+\epsilon^{\prime}$. It can then be checked that the chi-squared divergence between $P_{\theta}$ and $Q_{\alpha}$ is equal to $(1+2\epsilon^{\prime})^{n}-1=\epsilon^{2}$. Hence $M_{C}(\epsilon,\Theta)$ can be taken to be the number of probability measures $Q_{\alpha}$, which is the same as the number of points in $G$. We thus have (28). It can be checked by elementary calculus (Taylor expansion, for example) that the inequality

holds for $\epsilon\leq\sqrt{2}$ (in fact for all $\epsilon$, but for $\epsilon>\sqrt{2}$, the right hand side above may be negative). Therefore for $\epsilon\leq\min(\epsilon_{0},\sqrt{2})$, we get that

From inequality (22), we get that for every $\eta\leq\eta_{0}$ and $\epsilon\leq\min(\epsilon_{0},\sqrt{2})$,

If we now take $\epsilon=\min(\epsilon_{0},1)$ and $\eta=c_{3}/n$, we see that the quantity inside the parantheses converges to $1-\sqrt{c_{3}}c_{4}$ where $c_{4}$ depends only on $c_{1},c_{2}$ and $\epsilon_{0}$. Therefore by choosing $c_{3}$ sufficiently small, we get that $R_{n}\geq c/n^{2}$. This is the optimal minimax rate for this problem as can be seen by estimating $\theta$ by the minimum of the observations.

The fact that inequality (22) produced optimal lower bounds for the minimax risk in each of the above three examples is reassuring but not really exciting because, as we mentioned before, there are other simpler methods of obtaining such bounds in these examples. We presented them as simple toy examples to evaluate the performance of (22), to present a difference between (21) and (22) (which provides a justification for using divergences other than the Kullback-Leibler divergence for lower bounds) and also to stress the fact that global packing and covering characteristics are enough to obtain optimal minimax lower bounds. In order to convince the reader of the effectiveness of (22) in more involved situations, we now apply it to obtain the optimal minimax rate in a $d$-dimensional normal mean estimation problem. We are grateful to an anonymous referee for communicating this example to us. Another non-trivial application of (22) is presented in the next section.

We shall use inequality (22) to show that the minimax risk $R$ for this problem is larger than or equal to a constant multiple of $d\sigma^{2}$ when $\Gamma\geq\sigma\sqrt{d}$. We begin by arguing that we can take

whenever $\sigma\sqrt{\log(1+\epsilon^{2})}\leq\Gamma$.

For $N(\eta)$, we first note that the $\eta$-packing number of the metric space $(\Theta,\rho)$ is bounded from below by its $\eta$-covering number. Now, for any $\eta$-covering set, the space $\Theta$ is contained in the union of the balls of radius $\eta$ with centers in the covering set and hence the volume of $\Theta$ must be smaller than the sum of the volumes of these balls. Therefore, the number of points in the $\eta$-covering set must be at least $(\Gamma/\eta)^{d}$. Since this is true for every $\eta$-covering set, it follows that the $\eta$-covering number and hence the $\eta$-packing number is not smaller than $(\Gamma/\eta)^{d}$.

For $M_{C}(\epsilon,\Theta)$, we first observe that for $\theta,\theta^{\prime}\in\Theta$, the chi-squared divergence between $P_{\theta}$ and $P_{\theta^{\prime}}$ can be easily computed (because they are normal distributions with the same covariance matrix) to be $\chi^{2}(P_{\theta}||P_{\theta^{\prime}})=\exp\left(\rho^{2}(\theta,\theta^{\prime})/\sigma^{2}\right)-1$. Therefore $\chi^{2}(P_{\theta}||P_{\theta^{\prime}})\leq\epsilon^{2}$ if and only if $\rho(\theta,\theta^{\prime})\leq\epsilon^{\prime}:=\sigma\sqrt{\log(1+\epsilon^{2})}$. As a result, $M_{C}(\epsilon,\Theta)$ can be taken to be any upper bound on the $\epsilon^{\prime}$-covering number of $(\Theta,\rho)$. The $\epsilon^{\prime}$-covering number, as noted previously, is bounded from above by the $\epsilon^{\prime}$-packing number. Now, for any $\epsilon^{\prime}$-packing set, the balls of radius $\epsilon^{\prime}/2$ with centers in the packing set are all disjoint and their union is contained in the ball of radius $\Gamma+(\epsilon^{\prime}/2)$ centered at the origin. Consequently, the sum of the volumes of these balls is smaller than the volume of the ball of radius $\Gamma+(\epsilon^{\prime}/2)$ centered at the origin. Therefore, the number of points in the $\epsilon^{\prime}$-packing set is at most $(1+(2\Gamma/\epsilon^{\prime}))^{d}\leq(3\Gamma/\epsilon^{\prime})^{d}$ provided $\epsilon^{\prime}\leq\Gamma$. Since this is true for every $\epsilon^{\prime}$-packing set, it follows that the $\epsilon^{\prime}$-packing number and hence the $\epsilon^{\prime}$-covering number is not larger than $(3\Gamma/\epsilon^{\prime})^{d}$.

We can thus apply inequality (22) with (29) to get that, for every $\eta>0$ and $\epsilon>0$ such that $\sigma\sqrt{\log(1+\epsilon^{2})}\leq\Gamma$, we have

Now by elementary calculus, it can be checked that the function $\epsilon\mapsto\sqrt{1+\epsilon^{2}}/(\log(1+\epsilon^{2}))^{d/4}$ is minimized (subject to $\sigma\sqrt{\log(1+\epsilon^{2})}\leq\Gamma$) when $1+\epsilon^{2}=e^{d/2}$. We then get that

We now take $\eta=c_{1}\sigma\sqrt{d}$ and since $\Gamma\geq\sigma\sqrt{d}$, we obtain

V Reconstruction of convex bodies from noisy support function measurements

Let $\left\{u_{i},i\geq 1\right\}$ be a sequence of $d$-dimensional unit vectors. Gardner, Kiderlen and Milanfar (see their paper for earlier references) considered the problem of reconstructing an unknown convex body $K$ from noisy measurements of $h_{K}$ in the directions $u_{1},\dots,u_{n}$. More precisely, their problem was to estimate $K$ from observations $Y_{1},\dots,Y_{n}$ drawn according to the model $Y_{i}=h_{K}(u_{i})+\xi_{i},i=1,\dots,n$ where $\xi_{1},\dots,\xi_{n}$ are independent and identically distributed mean zero gaussian random variables. They constructed a convex body (estimator) $\hat{K}_{n}=\hat{K}_{n}(Y_{1},\dots,Y_{n})$ having the property that, for nice sequences $\left\{u_{i},i\geq 1\right\}$, the $L^{2}$ norm $||h_{K}-h_{\hat{K}_{n}}||_{2}$ (see (30) below) converges to zero at the rate $n^{-2/(d+3)}$ for dimensions $d=2,3,4$ and at a slower rate for dimensions $d\geq 5$ (see [25, Theorem 6.2]).

We shall show here that in the same setting, it is impossible in the minimax sense to construct estimators for $K$ converging at a rate faster than $n^{-2/(d+3)}$. This implies that the least squares estimator in is rate optimal for dimensions $d=2,3,4$. We shall need some notation to describe our result.

An estimator for $h_{K}$ is allowed to be a bounded function on $S^{d-1}$ that depends on the data $Y_{1},\dots,Y_{n}$. The loss functions that we shall use are the $L^{p}$ norms for $p\in[1,\infty]$ defined by

for $p\in[1,\infty)$ and $||h_{K}-\hat{h}||_{\infty}:=\sup_{u\in S^{d-1}}|h_{K}(u)-\hat{h}(u)|$. For convex bodies $K$ and $L$ and $p\in[1,\infty]$, we shall also write $\delta_{p}(K,L)$ for $||h_{K}-h_{L}||_{p}$ and refer to $\delta_{p}$ as the $L^{p}$ distance between $K$ and $L$.

We shall consider the minimax risk of the problem of estimating $h_{K}$ from $Y_{1},\dots,Y_{n}$ when $K$ is assumed to belong to ${\mathcal{K}}^{d}(\Gamma)$ i.e., we are interested in the quantity

The following is the main theorem of this section.

Fix $p\in[1,\infty)$ and $\Gamma>0$. Suppose the errors $\xi_{1},\dots,\xi_{n}$ are independent normal random variables with mean zero and variance $\sigma^{2}$. Then the minimax risk $r_{n}(p,\Gamma)$ satisfies

for a constant $c$ that is independent of $n$.

In the case when $p=2$, Gardner, Kiderlen and Milanfar showed that the least squares estimator converges at the rate given by the right hand side of (31) for dimensions $d=2,3,4$. Thus, at least for $p=2$, the lower bound given by (31) is optimal for dimensions $d=2,3,4$.

In order to apply inequality (22), we need to determine $N(\eta)$ and $M_{C}(\epsilon,\Theta)$. The quantity $N(\eta)$ is a lower bound on the $\eta$-packing number of the set ${\mathcal{K}}^{d}(\Gamma)$ under the $L^{p}$ norm. When $p=\infty$, Bronshtein [26, Theorem 4 and Remark 1] proved that there exist positive constants $c^{\prime}$ and $\eta_{0}$ depending only on $d$ such that $\exp\left(c^{\prime}(\eta/\Gamma)^{(1-d)/2}\right)$ is a lower bound for the $\eta$-packing number of $\Theta$ for $\eta\leq\eta_{0}$. It is a standard fact that $p=\infty$ corresponds to the Hausdorff metric on ${\mathcal{K}}^{d}(\Gamma)$.

It turns out that Bronshtein’s result is actually true for every $p\in[1,\infty]$ and not just for $p=\infty$. However, to the best of our knowledge, this has not been proved anywhere in the literature. By modifying Bronshtein’s proof appropriately and using the Varshamov-Gilbert lemma (see for example [27, Lemma 4.7]), we provide, in Theorem VII.1, a proof of this fact. Therefore from Theorem VII.1, we can take

where $c^{\prime}$ and $\eta_{0}$ are constants depending only on $d$ and $p$.

Now let us turn to $M_{C}(\epsilon,\Theta)$. For $f,g\in\Theta$, $P_{f}$ and $P_{g}$ are normal distributions with the same covariance matrix and hence the chi-squared divergence between $P_{f}$ and $P_{g}$ can be seen to be

where $\epsilon^{\prime}:=\sigma\sqrt{\log(1+\epsilon^{2})}/\sqrt{n}$. Let $W_{\epsilon^{\prime}}$ be the smallest $W$ for which there exist sets $K_{1},\dots,K_{W}$ in ${\mathcal{K}}^{d}(\Gamma)$ having the property that for every set $K\in{\mathcal{K}}^{d}(\Gamma)$, there exists a $K_{j}$ such that the Hausdorff distance between $K$ and $K_{j}$ is less than or equal to $\epsilon^{\prime}$. It must be clear from (33) that $M_{C}(\epsilon,\Theta)$ can be taken to be a number larger than $W_{\epsilon^{\prime}}$. Bronshtein [26, Theorem 3 and Remark 1] showed that there exist positive constants $c^{\prime\prime}$ and $\epsilon_{0}$ depending only on $d$ such that

Hence for all $\epsilon$ such that $\log(1+\epsilon^{2})\leq n\epsilon_{0}^{2}/\sigma^{2}$, we can take

We are now ready to prove inequality (31). We shall define two quantities

where $c=c(d,p)$ will be specified shortly. Also let $\epsilon(n)$ be such that $\log(1+\epsilon^{2}(n))=u^{2}(n)$. Clearly as $n\rightarrow\infty$, we have $\eta(n)\rightarrow 0$, $u(n)\rightarrow\infty$ and $u(n)/\sqrt{n}\rightarrow 0$. As a result $\eta(n)\leq\eta_{0}$ and $u^{2}(n)\leq n\epsilon_{0}^{2}/\sigma^{2}$ for large $n$ and therefore from (32) and (34), we get that