Assouad lower bound for a squared-error hypercube

For each coordinate $i$, define ${\varphi }_i(x)=K(x,\{z\in {\mathbb{R}}^d:z_i\ge a\mathrm{/}2\})$. This is a measurable $[0,1]$-valued function by [F2]. If the true bit is $0$, an action counted by ${\varphi }_i$ has coordinate squared error at least $a^2\mathrm{/}4$; if the true bit is $1$, an action outside that event has coordinate squared error at least $a^2\mathrm{/}4$. Thus $R_{\omega }(K)\ge \frac{a^2}{4}{\sum }_{i=1}^d[(1-{\omega }_i)P_{\omega }{\varphi }_i+{\omega }_i{P}_{\omega }(1-{\varphi }_i)],$ where $Pf:=\int fdP$.

For any two probability laws $P,Q$ and measurable $\varphi :\mathcal{X}\to [0,1]$, the finite approximants ${\varphi }_N=N^{-1}{\sum }_{r=1}^N{\mathbf{1}}_{\{\varphi \ge r\mathrm{/}N\}}$ satisfy $0\le \varphi -{\varphi }_N\le 1\mathrm{/}N$. By [F4], $\int {\varphi }_{N}dP-\int {\varphi }_{N}dQ\le \mathrm{\parallel }P-Q{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$, and the replacement error is at most $2\mathrm{/}N$. Letting $N\to \mathrm{\infty }$ gives $\int \varphi dP-\int \varphi dQ\le \mathrm{\parallel }P-Q{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}$. Applying the same result to $1-\varphi$ gives $P\varphi +Q(1-\varphi )\ge 1-\mathrm{\parallel }P-Q{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}\mathrm{.}$ For each coordinate, pair every hypercube vertex with bit $i=0$ to the unique neighbor with bit $i=1$. There are $2^{d-1}$ such pairs, and each pair's two testing errors in step 1.1 sum to at least $1-v$. Averaging over all $2^d$ vertices therefore gives average coordinate error at least $(1-v)\mathrm{/}2$. This establishes the coordinate error bound.

Average the risk bound in step 1.1 over the $2^d$ vertices. Step 2.1 shows that the average risk is at least $a^{2}d(1-v)\mathrm{/}8$. The supremum of finitely many risks is at least their arithmetic mean, so every $K$ has maximum risk at least this amount. Taking the infimum over procedures using [F5] proves the minimax bound.