Converting Hamming Error to Estimation Loss

From Coordinate Errors to Estimation Loss

Assouad’s method studies a finite family indexed by binary vectors. Its testing step bounds how often a procedure must get individual coordinates wrong. To turn that conclusion into a lower bound for estimating a parameter, one more link is needed: many wrong coordinates must force the estimate to be far from the true parameter. That link is geometric, and it must be stated as an assumption on the family of parameters.

We make the link using a decoder. Given an estimator that may take any value in the parameter space, choose the nearest member of the finite hypercube family. If the family is sufficiently separated in the metric, a decoder that makes many coordinate errors can only have been produced by an estimator with substantial metric loss.

Definition: For \(v,w\in\{0,1\}^m\), their Hamming distance is \(H(v,w)=\sum_{j=1}^m \mathbf{1}\{v_j\ne w_j\}\), the number of coordinates on which they differ. A family \(\{\theta_v:v\in\{0,1\}^m\}\) in a metric space \((\Theta,d)\) has Hamming separation at scale \(\Delta>0\) if \(d(\theta_v,\theta_w)\geq \Delta H(v,w)\) for every \(v,w\).

The separation requirement concerns every pair of vertices, not just pairs that differ in one coordinate. It is what allows a bound on the total number of wrong decoded coordinates to imply a bound on distance.

The Nearest-Point Decoder

Let \(\hat\theta\) be a measurable estimator taking values in a metric space containing the finite family \(\{\theta_v\}\). Define its decoded index by selecting a closest family member:

\hat v(\hat\theta)\in\arg\min_{w\in\{0,1\}^m}d(\hat\theta,\theta_w).

Fix an ordering of the vertices and use it to break ties. Since the candidate set is finite, this defines a measurable decoder whenever the distances from \(\hat\theta\) to the fixed candidates are measurable.

Proposition: If the family has Hamming separation at scale \(\Delta\), then for every true index \(v\) and every estimate \(\hat\theta\), \(d(\hat\theta,\theta_v)\geq (\Delta/2)H(\hat v,v)\).

Proof. The triangle inequality and Hamming separation give \( \Delta H(\hat v,v)\leq d(\theta_{\hat v},\theta_v)\leq d(\theta_{\hat v},\hat\theta)+d(\hat\theta,\theta_v)\). By the nearest-point choice, \(d(\theta_{\hat v},\hat\theta)\leq d(\theta_v,\hat\theta)\). Thus \(\Delta H(\hat v,v)\leq 2d(\hat\theta,\theta_v)\), which is the claimed inequality. \(\square\)

Worked Example: An Exact Hamming Embedding

Take \(m=3\), \(\Theta=\mathbb{R}^3\) with the \(\ell_1\) metric \(d(x,y)=\sum_{j=1}^3|x_j-y_j|\), and set \(\theta_v=2v\). For any two indices, \(d(\theta_v,\theta_w)=\sum_{j=1}^3|2v_j-2w_j|=2H(v,w)\). Thus the separation condition holds with \(\Delta=2\).

For any estimator, decode by choosing the closest of the eight vertices. If the decoded vector differs from the true index in two coordinates, the proposition says its estimation error is at least \((2/2)\times2=2\) in \(\ell_1\) distance. If it differs in all three coordinates, the error is at least \(3\). These bounds apply even when the estimator itself is not one of the eight vertices.

A Risk Bound from Neighboring Experiments

For each index \(v\), let \(P_v\) be the distribution of the observed data when the parameter is \(\theta_v\). Write \(\mathbb{E}_v\) for expectation under \(P_v\), and let \(\hat v\) be the decoded index. For coordinate \(j\), write \(v^{(j,b)}\) for the vector formed by deleting coordinate \(j\) from \(v\) and inserting \(b\in\{0,1\}\). Thus \(u\in\{0,1\}^{m-1}\) indexes a pair of vertices that differ only in coordinate \(j\), denoted \(u^{(j,0)}\) and \(u^{(j,1)}\).

Theorem: Suppose the family has Hamming separation at scale \(\Delta\). For each \(j\), define the average total variation distance between neighboring data distributions by \[ \overline{\mathrm{TV}}_j =2^{-(m-1)}\sum_{u\in\{0,1\}^{m-1}} \mathrm{TV}\bigl(P_{u^{(j,0)}},P_{u^{(j,1)}}\bigr). \] Then every measurable estimator satisfies \[ \sup_{v\in\{0,1\}^m}\mathbb{E}_v[d(\hat\theta,\theta_v)] \geq \frac{\Delta}{4}\sum_{j=1}^m(1-\overline{\mathrm{TV}}_j). \]

Proof. Average the risk over the \(2^m\) vertices. The nearest-point proposition gives \(\mathbb{E}_v[d(\hat\theta,\theta_v)]\geq(\Delta/2)\mathbb{E}_v[H(\hat v,v)]\). Averaging this inequality over \(v\), and writing the Hamming distance as a sum of coordinate errors, yields \[ 2^{-m}\sum_v\mathbb{E}_v[d(\hat\theta,\theta_v)] \geq \frac{\Delta}{2}\sum_{j=1}^m e_j, \qquad e_j=2^{-m}\sum_v P_v(\hat v_j\ne v_j). \] Group the terms defining \(e_j\) into pairs with the same \(m-1\) other coordinates. This gives \[ e_j=2^{-(m-1)}\sum_u\frac{P_{u^{(j,0)}}(\hat v_j=1)+P_{u^{(j,1)}}(\hat v_j=0)}{2}. \] For any two probability distributions \(P,Q\) and any event \(A\), \(P(A)+Q(A^c)\geq 1-\mathrm{TV}(P,Q)\). Indeed, the left side is \(1-(Q(A)-P(A))\), and \(Q(A)-P(A)\leq\mathrm{TV}(P,Q)\). Apply this inequality to each pair with \(A=\{\hat v_j=1\}\). It follows that \(e_j\geq(1-\overline{\mathrm{TV}}_j)/2\). Substitution gives the asserted bound on average risk. The supremum risk is at least the average risk, so the same lower bound holds for the supremum. \(\square\)

In particular, if every neighboring pair in coordinate \(j\) has total variation distance at most \(\tau_j\), then \[ \sup_v\mathbb{E}_v[d(\hat\theta,\theta_v)] \geq \frac{\Delta}{4}\sum_{j=1}^m(1-\tau_j). \] If a larger parameter space contains this finite family, its supremum risk is also at least this large. The testing step here is the coordinate-wise binary testing argument used in Assouad’s lemma; the geometric step above explains how its Hamming errors become estimation loss.

Worked Example: Identical Data Laws on a Three-Dimensional Cube

Use the \(\ell_1\) family \(\theta_v=2v\) from the first example. Suppose the observation space contains just one possible observation, and \(P_v\) assigns probability one to it for every \(v\). Every neighboring pair has total variation distance zero. The theorem therefore gives \(\sup_v\mathbb{E}_v[d(\hat\theta,\theta_v)]\geq (2/4)\times3=1.5\).

The bound is consistent with the data being completely uninformative: the observed value cannot reveal which vertex is true. More directly, any decoded vertex has average Hamming distance \(3/2\) from a uniformly chosen true vertex, so the proposition forces average \(\ell_1\) error of at least \((2/2)(3/2)=1.5\).

Examples of the Separation Condition

Worked Example: Euclidean Distance Gives a Weaker Hamming Scale

Let \(m=4\), use Euclidean distance on \(\mathbb{R}^4\), and set \(\theta_v=3v\). If \(H(v,w)=k\), then \(d(\theta_v,\theta_w)=3\sqrt{k}\). For \(k\in\{1,2,3,4\}\), \(\sqrt{k}\geq k/2\), since squaring both nonnegative sides reduces this to \(k\geq k^2/4\), which holds for \(k\leq4\). Therefore \(d(\theta_v,\theta_w)\geq(3/2)H(v,w)\), so \(\Delta=3/2\) is valid.

Suppose the data laws are identical at all vertices. All neighboring total variation distances are zero, and the theorem gives a Euclidean risk lower bound of \((3/2)\times4/4=1.5\). The scale \(\Delta=3/2\) is exact for the opposite vertices, whose Hamming distance is four and whose Euclidean distance is six. Thus the condition accounts for how Euclidean distance grows across the whole cube, not just along one edge.

Worked Example: A Partially Informative Experiment

Let \(m=2\), \(\theta_v=v\in\mathbb{R}^2\), and use \(\ell_1\) distance. Then \(d(\theta_v,\theta_w)=H(v,w)\), so \(\Delta=1\). Take the observation space \(\{\ast,00,01,10,11\}\), and define \(P_v(\ast)=1/2\), \(P_v(v)=1/2\), with probability zero on the other outcomes. The observation reveals the true index when it is not \(\ast\), and reveals nothing when it is \(\ast\).

For two neighboring indices \(v,w\), the distributions have common mass \(1/2\) at \(\ast\), and their remaining mass \(1/2\) is on distinct outcomes. Their total variation distance is therefore \(1/2\). Hence each \(\overline{\mathrm{TV}}_j=1/2\), and the theorem gives \(\sup_v\mathbb{E}_v[d(\hat\theta,\theta_v)]\geq(1/4)[(1-1/2)+(1-1/2)]=1/4\). The factor \(1/2\) in the bound reflects the chance that the observation carries no information; the other half of the time the index can be learned exactly.

Why the Condition Matters

A common mistake is to check only that parameters at neighboring vertices are separated by at least \(\Delta\), and then to claim \(d(\theta_v,\theta_w)\geq\Delta H(v,w)\) for all pairs. The conclusion does not follow: the triangle inequality gives an upper bound on distance along a path, not the required lower bound. For example, in the Euclidean construction \(\theta_v=3v\) with \(m=4\), neighboring vertices are distance \(3\) apart, but opposite vertices are distance \(6\), not \(3\times4=12\). A valid Hamming-separation scale for the whole family is \(3/2\), not \(3\).

The theorem is a lower bound for expected metric loss \(d\). If the loss is instead \(d^p\) for \(p\geq1\), the same pointwise argument gives \(d(\hat\theta,\theta_v)^p\geq(\Delta/2)^p H(\hat v,v)^p\geq(\Delta/2)^p H(\hat v,v)\), because Hamming distance is a nonnegative integer. Thus the testing bound can also yield a lower bound for powered metric loss, with the factor \(\Delta/2\) raised to \(p\).

In applications, the work is therefore split into two checks: establish a valid global separation scale for the parameter family, then control the total variation distances between neighboring data laws. A strong testing bound cannot compensate for an invalid geometric separation claim.

Check Your Understanding

Use the decoder and risk bound to answer the following.

Why does the nearest-point property contribute a factor of two in the conversion from metric error to Hamming error?
If \(\Delta=2\) and every neighboring total variation distance is at most \(1/3\), what lower bound does the theorem give for the supremum expected metric risk when \(m=6\)?
For the family \(\theta_v=a v\) under Euclidean distance, derive a valid Hamming-separation scale in terms of \(a\) and \(m\).
Why is separation of neighboring parameter points alone insufficient to establish the theorem’s separation condition?
In the partially informative experiment, what happens to the risk bound if the probability of observing \(\ast\) is increased while the remaining probability still reveals the index exactly?