Assouad Constructions for Classification Minimaxity

Why a Hypercube Gives a Classification Lower Bound

A minimax lower bound asks how well any classifier can perform in the hardest distribution in a specified class. For classification, one way to make the problem hard is to create many small regions where the Bayes label can independently be either 0 or 1. A classifier must then recover many unknown binary choices from the sample. If neighboring choices produce nearly indistinguishable data, some choices will be wrong, and those errors incur excess risk.

Assouad’s method formalizes this argument. Its useful feature is that it separates the construction into local pieces: the mass and margin of each piece determine its contribution to risk, while the distance between neighboring distributions determines how hard its bit is to learn.

Definition: In binary classification, write $\eta(x)=P(Y=1\mid X=x)$ and $\Delta(x)=|2\eta(x)-1|$. For a classifier $g$, its excess risk over the Bayes classifier is $$ \mathcal{E}(g)=R(g)-R^*=E\!\left[\Delta(X)\mathbf{1}\{g(X)\ne g^*(X)\}\right], $$ where $g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}$; ties do not affect the displayed excess-risk formula. The minimax excess risk over a class $\mathcal{P}$ is $\inf_{\widehat g}\sup_{P\in\mathcal{P}} E_P[\mathcal{E}(\widehat g)]$, where $\widehat g$ is constructed from $n$ independent observations.

A hypercube has one sign $\sigma_j\in\{-1,+1\}$ for each of $m$ cells. The conditional probability on cell $j$ is $1/2+\sigma_j a$, where $a>0$ is small. Thus the Bayes label in that cell is exactly the sign $\sigma_j$. Let the cells $A_1,\ldots,A_m$ be disjoint, each with design probability $q=P_X(A_j)$. The total active mass is $M=mq$. Outside those cells, take a common distribution and regression function for every sign vector, so that observations there reveal nothing about the signs.

From Classification to Bit Recovery

To use a testing argument, convert any classifier into an estimate of each sign. On $A_j$, set $\widehat\sigma_j=+1$ if the classifier predicts 1 on at least half the design mass of that cell, and set $\widehat\sigma_j=-1$ otherwise. If this bit estimate is wrong, the classifier misclassifies at least half of $A_j$. Since $\Delta=2a$ on the cell, that bit error contributes at least $a q$ to excess risk.

The next result states the resulting lower bound. The assumptions make the link between the statistical experiment and the margin constraint explicit; localized smooth functions can be used to realize the cellwise alternatives when the design and cell geometry permit them.

Theorem (Assouad lower bound for a classification hypercube): Suppose the alternatives are indexed by $\sigma\in\{-1,+1\}^m$. The cells are disjoint, have common design mass $q$, and satisfy $\eta_\sigma=1/2+\sigma_j a$ on $A_j$, with $0<a\le 1/4$. Suppose all alternatives agree outside the cells. If, for every pair $\sigma,\sigma'$ differing in one coordinate, the total variation distance between their $n$-observation laws is at most $1/2$, then every classifier estimator satisfies $$ \sup_{\sigma} E_\sigma[\mathcal{E}(\widehat g)]\ge \frac{a m q}{4}. $$

Here total variation distance is $\|P-Q\|_{\mathrm{TV}}=\sup_B|P(B)-Q(B)|$. To prove the theorem, first fix a coordinate $j$, and pair each sign vector with the vector that reverses only its $j$th sign. For any test between two distributions $P,Q$, the sum of its two error probabilities is at least $1-\|P-Q\|_{\mathrm{TV}}$. This follows because, for the event $B$ on which the test chooses $P$, the sum is $P(B^c)+Q(B)=1-(P(B)-Q(B))\ge1-\|P-Q\|_{\mathrm{TV}}$. Thus the average error probability over a neighboring pair is at least $1/4$. Averaging over all sign vectors preserves this bound for each bit. Summing the bit errors and using the risk contribution $a q$ per wrong bit gives $$ 2^{-m}\sum_\sigma E_\sigma[\mathcal{E}(\widehat g)] \ge a q\sum_{j=1}^m 2^{-m}\sum_\sigma P_\sigma(\widehat\sigma_j\ne\sigma_j) \ge \frac{a m q}{4}. $$ The supremum is at least this average, proving the claim. $\square$

Worked Example: Four Cells and One Observation

Take $m=4$, cell mass $q=1/16$, and amplitude $a=1/8$. Conditional on $X$ being in cell $j$, let $Y$ be Bernoulli with probability $5/8$ or $3/8$, according to $\sigma_j=+1$ or $-1$. Let the remaining design mass $3/4$ be outside the cells and have the same distribution under every alternative. Check that the neighboring alternatives are hard to distinguish when $n=1$, then compute the theorem’s lower bound.

For Bernoulli probabilities $p$ and $r$, the inequality $\log u\le u-1$ gives $\mathrm{KL}(\mathrm{Bern}(p),\mathrm{Bern}(r))\le(p-r)^2/[r(1-r)]$. For the two cell probabilities, $p-r=1/4$ and $r(1-r)=(5/8)(3/8)=15/64$, so the divergence conditional on the cell is at most $(1/16)/(15/64)=4/15$. A single observation falls in the changed cell with probability $1/16$; hence the joint divergence is at most $1/60$. Pinsker’s inequality, $\|P-Q\|_{\mathrm{TV}}\le\sqrt{\mathrm{KL}(P,Q)/2}$, bounds the total variation distance by $\sqrt{1/120}<1/2$, as required.

The total active mass is $mq=4/16=1/4$. The theorem gives $\sup_\sigma E_\sigma[\mathcal{E}(\widehat g)]\ge a m q/4=(1/8)(1/4)/4=1/128$. This is a lower bound for every classifier estimator, not the risk of a particular fitting procedure.

Neighboring Samples and the Smoothness Scale

For $n$ independent observations, neighboring alternatives differ only when $X$ falls in their one changed cell. The one-observation divergence is $q$ times the conditional Bernoulli divergence, and divergences add over independent observations. When the cell probabilities are $1/2+a$ and $1/2-a$, with $a\le1/4$, the same Bernoulli inequality gives $$ \mathrm{KL}(\mathrm{Bern}(1/2+a),\mathrm{Bern}(1/2-a)) \le \frac{(2a)^2}{(1/2-a)(1/2+a)} \le 32a^2. $$ Consequently, the $n$-sample divergence is at most $32nqa^2$. Pinsker’s inequality then gives total variation at most $4a\sqrt{nq}$. In particular, $nqa^2\le1/64$ suffices for the theorem’s total-variation condition.

This calculation explains the local testing scale: each cell must have small enough mass, amplitude, or both that its signal is difficult to detect. In a $\beta$-smooth construction, a bump supported on a region of width $h$ can have height proportional to $h^\beta$, so take $a\asymp h^\beta$. Under a regular $d$-dimensional design, a cell of width $h$ has mass of order $h^d$. The neighbor-divergence condition then has order $n h^{2\beta+d}$.

Worked Example: Checking the Smoothness and Testing Scales

Suppose $d=2$, $\beta=1$, and there are cells of width $h=0.1$. Take amplitude $a=h^\beta=0.1$ and cell mass $q=h^d=0.01$. For $n=10$, the divergence bound for neighboring samples is $32nqa^2=32(10)(0.01)(0.01)=0.032$. Pinsker’s inequality therefore bounds total variation by $\sqrt{0.032/2}=\sqrt{0.016}$, approximately $0.126$, below $1/2$.

The calculation is a sufficient check, not an exact divergence calculation: it deliberately uses an upper bound. It also shows why the exponent contains both $2\beta$, from the squared signal height, and $d$, from the probability of landing in the changed cell.

Imposing a Margin Constraint

A margin condition restricts the amount of design probability near the classification boundary. In the convention used here, an exponent $\alpha\ge0$ and constant $C$ impose $P_X(\Delta(X)\le t)\le C t^\alpha$ for every $t>0$. On each active cell, $\Delta=2a$, so the active mass must obey $M=mq\le C(2a)^\alpha$. The lower bound $aM/4$ is then of order at most $a^{1+\alpha}$; to make it a valid construction, choose the active mass of that order, rather than putting fixed probability mass near the boundary as $a$ shrinks.

For a concrete smoothness scaling, suppose $q\asymp h^d$, $a\asymp h^\beta$, and choose $m\asymp h^{\alpha\beta-d}$, so $M=mq\asymp h^{\alpha\beta}$. This choice is feasible as a growing collection of cells when $\alpha\beta<d$; at equality, a bounded number of cells gives the same scaling. If cells can be placed with localized smooth bumps and the remaining design mass is supported where the margin is bounded away from zero, the margin condition holds: below $2a$ the active cells contribute no mass, and at or above $2a$ their total mass is of order $a^\alpha$. The background must also be checked against the condition, but a fixed positive margin there causes no small-margin mass for $t$ below that gap.

Now take $h$ so that $n h^{2\beta+d}$ is a sufficiently small constant. The neighboring alternatives remain hard to distinguish, while the Assouad risk bound has order $$ aM\asymp h^{\beta(1+\alpha)} \asymp n^{-\beta(1+\alpha)/(2\beta+d)}. $$ This is a lower bound for classes containing the stated alternatives and satisfying the stated design, smoothness, and margin requirements. It is not a claim that the same construction applies unchanged to every design or every parameter regime.

Worked Example: A Margin-Constrained Rate in Two Dimensions

Let $d=2$, $\beta=1$, and $\alpha=1/2$. Set $h=n^{-1/4}$, which makes $n h^{2\beta+d}=n h^4=1$. Take cells with mass $q\asymp h^2$, amplitude $a\asymp h$, and number $m\asymp h^{\alpha\beta-d}=h^{-3/2}$. Integer rounding changes only constants for small $h$.

The active mass is $mq\asymp h^{-3/2}h^2=h^{1/2}=a^\alpha$, so it has the required margin scale. The testing quantity for a neighboring bit is $nqa^2\asymp n h^2h^2=1$; choosing the proportionality constant in $h$ sufficiently small makes it satisfy the required small-divergence bound. The excess-risk lower bound is $a m q\asymp h\cdot h^{1/2}=h^{3/2}=n^{-3/8}$.

The exponent agrees with the general expression: $\beta(1+\alpha)/(2\beta+d)=1(1+1/2)/(2+2)=3/8$. The active mass calculation is essential: using a fixed total active mass would not satisfy this positive margin exponent as the cell amplitude tends to zero.

Common Pitfall and Interpretation

Common mistake: keep the number of cells at order $h^{-d}$, assign them total probability of order one, and then claim a lower bound of order $h^\beta$ while also imposing a positive margin exponent. That construction puts order-one probability at margin $2a\asymp h^\beta$. At $t=2a$, the margin condition would require order-one mass to be at most $C h^{\alpha\beta}$, which tends to zero when $\alpha>0$. The construction therefore violates the condition.

Correction: reduce the total probability near the boundary to order $a^\alpha$, and account for that reduction in the risk: the lower bound is amplitude times active mass, $aM$, not just amplitude. The number of cells and the probability per cell also both enter the testing calculation $nqa^2$. Keeping these three quantities distinct—amplitude, cell mass, and number of cells—is the main bookkeeping discipline in an Assouad argument.

Assouad constructions are useful because they turn a many-parameter estimation problem into $m$ related binary tests while preserving a direct interpretation in classification risk. Their conclusion is only as strong as the family of alternatives: smoothness must hold for every alternative, the margin condition must be verified under its design distribution, and neighboring sample laws must actually be close. Checking those conditions is part of the lower-bound proof, not a technical afterthought.

Check Your Understanding

Use the definitions and derivations above to answer the following questions.

Why does a wrong estimated sign on a cell of mass $q$ contribute at least $a q$, rather than $2a q$, to excess risk under the majority-decoding rule?
If neighboring $n$-sample laws have total variation at most $1/2$, what lower bound does the testing argument give on the average error probability for one bit?
For a smoothness scale $a\asymp h^\beta$ and cell mass $q\asymp h^d$, derive the order of the neighboring-sample divergence.
Why must the total active mass shrink when a positive margin exponent is imposed and $a$ tends to zero?
In the two-dimensional worked example, verify both the active-mass order and the excess-risk exponent from the chosen $m$, $q$, and $a$.