Assouad’s Lemma on the Hypercube

Why a Hypercube Gives a Lower Bound

A lower bound for estimation can be built by choosing a finite collection of parameter values that are difficult to distinguish. A binary hypercube is useful because each parameter has $d$ separate signs, and changing just one sign gives a natural pair of nearby alternatives. If the data do not reliably reveal that sign, an estimator must make errors in that coordinate on at least some members of the pair.

Assouad’s lemma formalizes this idea. It counts the contribution of every coordinate by pairing vertices that differ only there, then uses binary testing difficulty to bound the estimation risk averaged over the entire hypercube. The result gives a minimax lower bound, since the largest risk over the parameter set cannot be smaller than its average.

Hypercube Experiments and Hamming Risk

Definition: Let $d$ be a positive integer, let $\Omega=\{-1,+1\}^d$, and let $(\mathcal X,\mathcal A)$ be a measurable sample space. A statistical experiment on the hypercube is a collection of probability distributions $\{P_\omega:\omega\in\Omega\}$ on that space. An estimator is a measurable function $\hat\omega:\mathcal X\to\Omega$. Its Hamming loss at $\omega$ is $$ H(\hat\omega,\omega)=\sum_{j=1}^d \mathbf{1}\{\hat\omega_j\ne\omega_j\}. $$ The minimax Hamming risk is $$ R^*=\inf_{\hat\omega}\sup_{\omega\in\Omega}E_\omega[H(\hat\omega,\omega)]. $$

The Hamming loss simply counts the number of incorrectly estimated signs. For a coordinate $j$, write $u\in\{-1,+1\}^{d-1}$ for the values of all the other coordinates. Denote by $\omega(u,+)$ and $\omega(u,-)$ the two vertices with those fixed other coordinates and with coordinate $j$ set to $+1$ and $-1$, respectively. These are neighboring vertices.

For two probability distributions $P$ and $Q$, their total variation distance is $ \operatorname{TV}(P,Q)=\sup_{A\in\mathcal A}|P(A)-Q(A)| $. It ranges from zero for identical distributions to one for mutually singular distributions. It measures how well a test can distinguish the distributions.

Lemma (binary testing bound): Suppose a test $\phi$ takes values in $\{+,-\}$, with $P_+$ the distribution under the $+$ alternative and $P_-$ under the $-$ alternative. Then $$ P_+(\phi=-)+P_-(\phi=+)\ \ge\ 1-\operatorname{TV}(P_+,P_-). $$

Proof. Let $A=\{x:\phi(x)=+\}$. The sum of the two error probabilities is $$ P_+(A^c)+P_-(A) =1-\bigl(P_+(A)-P_-(A)\bigr). $$ By the definition of total variation, $P_+(A)-P_-(A)\le \operatorname{TV}(P_+,P_-)$. Substitution proves the inequality. $\square$

Assouad’s Lemma

Theorem (Assouad’s lemma, Hamming-risk form): For each coordinate $j$ and each fixed configuration $u$ of the other $d-1$ coordinates, let $$ \Delta_{j,u}=\operatorname{TV}\bigl(P_{\omega(u,+)},P_{\omega(u,-)}\bigr). $$ Then $$ R^*\ \ge\ \frac12\sum_{j=1}^d \left[ 1-\frac{1}{2^{d-1}}\sum_{u\in\{-1,+1\}^{d-1}}\Delta_{j,u} \right]. $$ In particular, if every pair of neighboring distributions has total variation distance at most $\alpha$, then $$ R^*\ \ge\ \frac d2(1-\alpha). $$

Proof. Fix any estimator $\hat\omega$. For a given coordinate $j$, use its $j$th output as a test between the two distributions in each neighboring pair: decide $+$ when $\hat\omega_j=+1$, and decide $-$ otherwise. The binary testing bound gives, for each $u$, $$ P_{\omega(u,+)}(\hat\omega_j=-1)+P_{\omega(u,-)}(\hat\omega_j=+1) \ \ge\ 1-\Delta_{j,u}. $$ Sum this inequality over all $2^{d-1}$ choices of $u$. Every vertex in $\Omega$ appears exactly once in these pairs, so the result is $$ \sum_{\omega\in\Omega}P_\omega(\hat\omega_j\ne\omega_j) \ \ge\ \sum_{u\in\{-1,+1\}^{d-1}}(1-\Delta_{j,u}). $$ Now sum over $j$, divide by $2^d$, and use the definition of Hamming loss: $$ \frac{1}{2^d}\sum_{\omega\in\Omega}E_\omega[H(\hat\omega,\omega)] \ \ge\ \frac12\sum_{j=1}^d \left[ 1-\frac{1}{2^{d-1}}\sum_u\Delta_{j,u} \right]. $$ The maximum risk of $\hat\omega$ over $\Omega$ is at least its average risk over $\Omega$. Thus its maximum risk is at least the displayed lower bound. Taking the infimum over all estimators proves the first claim. If $\Delta_{j,u}\le\alpha$ for all $j,u$, each bracket is at least $1-\alpha$, which proves the final claim. $\square$

The average-pair version can be sharper than the uniform bound: some coordinates or some parts of the hypercube may be much easier to distinguish than others. The proof keeps these differences visible until the final averaging step.

Worked Examples

Worked Example: No Information About Any Coordinate

Let $d=4$, and suppose $P_\omega=N(0,1)$ for every $\omega\in\{-1,+1\}^4$. The observation has the same distribution at every vertex. Therefore, for every coordinate and every configuration $u$, $$ \Delta_{j,u}=\operatorname{TV}(N(0,1),N(0,1))=0. $$ Assouad’s bound gives $$ R^*\ge \frac12\sum_{j=1}^4(1-0)=2. $$ Thus no estimator can have worst-case expected Hamming error below two. The conclusion follows from indistinguishability, not from a particular choice of estimator.

Worked Example: A Gaussian Hypercube

Observe one vector $X=(X_1,\ldots,X_d)$, with independent coordinates $X_j\sim N(a\omega_j,1)$, where $a>0$ is fixed. Neighboring vertices differ in just one coordinate, so their distributions differ only in one normal mean: $a$ versus $-a$. The Kullback–Leibler divergence between $N(a,1)$ and $N(-a,1)$ is $$ E_{X\sim N(a,1)} \left[\log\frac{f_a(X)}{f_{-a}(X)}\right] =\frac{(a-(-a))^2}{2} =2a^2. $$ The other coordinates have identical distributions under the pair, so they do not change this divergence. By Pinsker’s inequality, $\operatorname{TV}(P,Q)\le\sqrt{\operatorname{KL}(P\|Q)/2}$, every neighboring pair satisfies $\Delta_{j,u}\le a$. For $a=1/4$, this gives $$ R^*\ge \frac d2\left(1-\frac14\right)=\frac{3d}{8}. $$ The bound applies to every dimension $d$; the uncertainty in each coordinate contributes to the total Hamming risk.

Worked Example: Only One Sign Is Observed

Let $d=4$, and suppose the data are the single value $W=\omega_1$. If two vertices differ in coordinate 1, their observations are different with probability one, so their distributions have total variation distance 1. If they differ only in coordinate 2, 3, or 4, their observations are identical, so their total variation distance is 0.

For coordinate 1, the bracket in Assouad’s bound is $1-1=0$. For each of the other three coordinates, it is $1-0=1$. Hence $$ R^*\ge \frac12(0+1+1+1)=\frac32. $$ The data reveal the first sign but contain no information about the other three. The bound records that the latter coordinates alone force an average of at least $3/2$ errors in the worst case.

What the Bound Says—and What It Does Not

Assouad’s lemma is especially effective when a large parameter set can be organized into many one-coordinate comparisons. Its central quantity is not the total variation between distant vertices, but the average total variation between neighbors. If these neighboring distributions are close, each coordinate is hard to recover, and the contributions add under Hamming loss.

The statement proved here concerns estimation of a hypercube label under Hamming loss. In applications, the hypercube may encode parameters of a different kind, but an additional argument is needed to relate Hamming errors to that application’s loss. The lemma itself does not supply that conversion.

Common Mistake

A common error is to compare only one pair of neighboring vertices and multiply its testing lower bound by $d$. That multiplication is justified only when the same bound applies to every coordinate and every setting of the remaining signs. In a nonuniform experiment, some neighboring pairs may be easy to distinguish. The correction is to retain the pair-specific quantities $\Delta_{j,u}$, average them over the other coordinates, and sum the resulting coordinate-wise bounds as in the theorem.

Key takeaway: Pair the hypercube vertices along each coordinate, lower-bound the two testing errors in every pair by one minus their total variation distance, and average. The result is a minimax Hamming-risk lower bound that adds the unresolved coordinate contributions.

Check Your Understanding

Work through these questions using the pairwise form of the lemma.

For a fixed coordinate and fixed values of the other signs, identify the two distributions used in the binary testing argument.
Why is the sum of the two testing errors at least one minus the total variation distance?
If every neighboring pair has total variation distance at most $0.2$, what lower bound does Assouad’s lemma give for dimension $d$?
In the partially observed example, which coordinates contribute zero to the bound, and why?
Why does a lower bound on risk averaged uniformly over the hypercube imply a lower bound on the maximum risk?