Minimax Lower Bounds — Examples

The finite parameter set defines a measurable experiment by [F7]. The target gap is $\mathrm{\Delta }={\theta }_1-{\theta }_0=\sigma \mathrm{/}(2\sqrt{n})$. By [F2] and [F3], $D(P_{{\theta }_1}\mathrm{\parallel }{P}_{{\theta }_0})=n\frac{{\mathrm{\Delta }}^2}{2{\sigma }^2}=\frac{1}{8}\mathrm{.}$ Pinsker [F4] therefore gives $\mathrm{\parallel }{P}_{{\theta }_0}-P_{{\theta }_1}{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}\le \sqrt{(1\mathrm{/}8)\mathrm{/}2}=1\mathrm{/}4$.

Apply [F5] with this gap and total-variation bound: ${\inf }_K{\max }_{j=0,1}{R}_{{\theta }_j}(K)\ge \frac{{\mathrm{\Delta }}^2}{8}(1-\frac{1}{4})=\frac{{\sigma }^2}{4n}\cdot \frac{3}{32}=\frac{3{\sigma }^2}{128n}\mathrm{.}$ This is the claimed minimax risk bound under [F6].

By [F2], choose a code $\mathcal{C}$ of size $M$ with associated $u^{\omega }\in \{0,1{\}}^d$, each having exactly $k$ ones and pairwise squared distance greater than $k\mathrm{/}2$. Its logarithmic size is positive because $ed\mathrm{/}k\ge 2e>1$ by [F8], so $M\ge 2$.

Suppose $M=2$. The size bound in [F2] implies $k\log (ed\mathrm{/}k)\le 1024\log 2<1024$ by [F8]. The two means ${\mu }^0=0$ and ${\mu }^1=b{e}_1$, where $b=\sigma \mathrm{/}(2\sqrt{n})$, both belong to ${\mathrm{\Theta }}_{k,d}$ because $k\ge 1$. Let ${\pi }_1:{\mathbb{R}}^d\to \mathbb{R}$ be first-coordinate projection and define the scalar action kernel $K_1(y,B):=K(y,{\pi }_1^{-1}(B))$ for every Borel $B\subseteq \mathbb{R}$. Since ${\pi }_1$ is Borel, each $K_1(y,\cdot )$ is the pushforward probability under ${\pi }_1$ and $y\mapsto K_1(y,B)$ is measurable, so [F5] applies to $K_1$. For $j=0,1$, define $R_j^{(1)}(K_1):={\int }_{{\mathbb{R}}^d}{\int }_{\mathbb{R}}(x-{\mu }_1^j{)}^2{K}_1(y,dx)P_{{\mu }^j}(dy)$. The pushforward integral identity here follows from the definition of $K_1$ for indicators and then for nonnegative functions by simple approximation; together with $\mathrm{\parallel }z-{\mu }^j{\mathrm{\parallel }}_2^2\ge (z_1-{\mu }_1^j{)}^2$, it gives $R_{{\mu }^j}(K)\ge R_j^{(1)}(K_1)$. The scalar target gap is $b$. The KL divergence of the two full observation laws is $n{b}^2\mathrm{/}(2{\sigma }^2)=1\mathrm{/}8$ by [F3], so [F6] gives $\mathrm{\parallel }{P}_{{\mu }^0}-P_{{\mu }^1}{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}\le 1\mathrm{/}4$. Applying [F5] to the scalar kernel and these two laws yields ${\max }_j{R}_j^{(1)}(K_1)\ge b^2(1-1\mathrm{/}4)\mathrm{/}8=3b^2\mathrm{/}32=3{\sigma }^2\mathrm{/}(128n)$, and therefore ${\max }_j{R}_{{\mu }^j}(K)\ge 3{\sigma }^2\mathrm{/}(128n)$. Since $1024\mathrm{/}200000<3\mathrm{/}128$, this exceeds ${\sigma }^{2}k\log (ed\mathrm{/}k)\mathrm{/}(200000n)$.

Suppose $M\ge 3$. Put $a^2={\sigma }^2\log M\mathrm{/}(4nk)$ and ${\mu }^{\omega }=a{u}^{\omega }$. These means belong to ${\mathrm{\Theta }}_{k,d}$, and their pairwise squared distances exceed $a^{2}k\mathrm{/}2$ by step 1.1.

Take $Q=P_0$, the zero-mean Gaussian law. By [F3], for every $\omega \in \mathcal{C}$, $D(P_{{\mu }^{\omega }}\mathrm{\parallel }{P}_0)=\frac{n}{2{\sigma }^2}\mathrm{\parallel }a{u}^{\omega }{\mathrm{\parallel }}_2^2=\frac{n{a}^{2}k}{2{\sigma }^2}=\frac{\log M}{8}\mathrm{.}$ Thus the average reference divergence equals $\log M\mathrm{/}8$.

Since $M\ge 3$, $\log 2\mathrm{/}\log M\le \log 2\mathrm{/}\log 3<2\mathrm{/}3$: the strict inequality follows from $3\log 2=\log 8<\log 9=2\log 3$, using $8<9$, monotonicity, and the product law in [F8]. Thus $1-((\log M)\mathrm{/}8+\log 2)\mathrm{/}\log M\ge 7\mathrm{/}8-2\mathrm{/}3=5\mathrm{/}24>1\mathrm{/}5$. Apply [F4] with separation $\mathrm{\Delta }=a\sqrt{k\mathrm{/}2}$ and reference $P_0$. Every estimator's average risk on the code is at least $\frac{{\mathrm{\Delta }}^2}{4}\cdot \frac{1}{5}=\frac{a^{2}k}{40}=\frac{{\sigma }^2\log M}{160n}\ge \frac{{\sigma }^{2}k\log (ed\mathrm{/}k)}{163840n}\mathrm{.}$ The supremum over ${\mathrm{\Theta }}_{k,d}$ dominates this finite-code average.

In the $M\ge 3$ case, $1\mathrm{/}163840>1\mathrm{/}200000$, so step 4.1 implies the claimed bound. In the $M=2$ case it follows from step 2.1. For every estimator, the supremum risk over ${\mathrm{\Theta }}_{k,d}$ is at least the finite submodel average or two-point maximum just proved; taking the infimum over estimators in the defined minimax value preserves the bound.

Let $a=\sigma \mathrm{/}\sqrt{n}$, so the parameter set is $\{0,a{\}}^d$; this finite parameter set makes the model a measurable kernel by [F6]. Neighboring vertices differ in one coordinate. By [F2], their KL divergence is $\frac{n{a}^2}{2{\sigma }^2}=\frac{1}{2}\mathrm{.}$ Pinsker [F3] therefore bounds every neighboring total-variation distance by $\sqrt{(1\mathrm{/}2)\mathrm{/}2}=1\mathrm{/}2$.

Apply [F4] with this spacing and $v\le 1\mathrm{/}2$: ${\inf }_K{\sup }_{\theta \in \{0,a{\}}^d}{R}_{\theta }(K)\ge \frac{a^{2}d}{8}(1-\frac{1}{2})=\frac{{\sigma }^{2}d}{16n}\mathrm{.}$ The action and loss are those specified in [F5], which proves the example.