= Assouad's lemma
{c}
{title2=$R^*\geq k(1-\eta)/2$}
{wiki}
Assouad's lemma turns many neighbouring testing problems into a lower bound for <minimax risk>. One direct form estimates an unknown bit vector $\omega\in\{0,1\}^k$ from data with law $P_\omega$, using <Hamming distance> as loss. If every neighbouring pair satisfies $\operatorname{TV}(P_\omega,P_{\omega'})\leq\eta$, where $\omega,\omega'$ differ in one bit, then
$$
\inf_{\widehat\omega}\sup_\omega\mathbb E_\omega d_H(\widehat\omega,\omega)\geq\frac{k}{2}(1-\eta).
$$
To prove it, average the risk over all vertices. For a fixed coordinate, pair vertices differing only in that bit. The sum of the two bit-error probabilities of any <hypothesis test> is at least $1-\operatorname{TV}$, so the averaged error in that coordinate is at least $(1-\eta)/2$. Sum over coordinates and use that a maximum dominates an average.
An <Assouad hypercube> embeds this construction in a larger estimation problem. The embedding must also relate the original loss to bit errors; it is that geometric separation which transfers the testing difficulty into a numerical estimation lower bound.
Back to article page
