Assouad Hypercubes For Hölder Risk

Why Use a Hypercube?

A two-point lower bound compares just two possible regression functions. That can show that estimation cannot be perfect, but it does not always capture the full difficulty of estimating a function with many independently varying local features. An Assouad hypercube packages many such features into a family indexed by binary vectors. If neighboring members of the family are hard to distinguish, then many coordinates must be estimated with nontrivial error.

We derive this argument for random-design regression on the unit cube. The resulting lower bound has the familiar dependence on sample size \(n\), dimension \(d\), and Hölder smoothness \(\alpha\). The construction uses a smooth bump function, as in the earlier material on smooth bump functions for lower bounds.

Model, Risk, and Hölder Class

Suppose the observations \((X_i,Y_i)\), \(i=1,\ldots,n\), are independent and identically distributed, with \(X_i\) uniform on \([0,1]^d\) and \(Y_i=f(X_i)+\varepsilon_i\), where the errors are independent of the design and satisfy \(\varepsilon_i\sim N(0,\sigma^2)\). For an estimator \(\hat f\), its integrated squared-error risk at \(f\) is

Fix a noninteger smoothness level \(\alpha>0\), and write \(\alpha=r+s\), where \(r\) is a nonnegative integer and \(0<s<1\). For definiteness, a Hölder norm can be taken to bound the suprema of all partial derivatives through order \(r\), together with the \(s\)-Hölder seminorms of the order-\(r\) derivatives. The Hölder ball \(\mathcal H^\alpha(L)\) consists of functions whose norm is at most \(L\). The precise equivalent choice of norm changes constants, not the rate derived below.

Building the Localized Family

Choose a nonzero smooth function \(\psi\) supported in the interior of \([0,1]^d\). Let \(h\leq 1/4\) be a scale, let \(q=\lfloor 1/(2h)\rfloor\), and place one bump in each of \(M=q^d\) blocks of side \(2h\). For an index \(k=(k_1,\ldots,k_d)\) with \(0\leq k_\ell<q\), put \(z_k=2hk\) and define

Each bump is supported within its own block, and distinct supports are separated by gaps. A fixed smooth bump and this spacing give a constant \(C_{\psi,\alpha,d}\) such that the Hölder norm of every \(f_\theta\) is at most \(C_{\psi,\alpha,d}a\), uniformly over \(0<h\leq1/4\). To see why the scaling works, a derivative of order \(|\nu|\leq r\) has size bounded by a constant times \(a h^{\alpha-|\nu|}\), which is at most a constant times \(a\). The order-\(r\) derivatives have size of order \(a h^s\); within a bump their \(s\)-Hölder quotient is bounded by a constant times \(a\). Across distinct supports, their separation is proportional to \(h\), giving the same bound. Thus choosing \(a\leq L/C_{\psi,\alpha,d}\) puts the entire family in \(\mathcal H^\alpha(L)\).

A single coordinate change has a particularly simple squared distance. Define \(B=a^2h^{2\alpha+d}\|\psi\|_2^2\), where \(\|\psi\|_2^2=\int_{[0,1]^d}\psi(u)^2\,du\). A change in coordinate \(j\) changes the function by \(a h^\alpha\psi_j\). Changing variables \(u=(x-z_j)/h\) gives

where \(\theta^{(j)}\) is \(\theta\) with its \(j\)th bit flipped. For the Gaussian regression model, the Kullback–Leibler divergence between the joint data distributions \(P_\theta\) and \(P_{\theta^{(j)}}\) is

Indeed, conditional on the design points, the log-density ratio for one observation has expectation \((f_\theta(X_i)-f_{\theta^{(j)}}(X_i))^2/(2\sigma^2)\) under \(P_\theta\). Averaging over the uniform design integrates this squared difference over the cube; independence adds the \(n\) contributions.

From Function Estimation to Bit Testing

To use the hypercube, convert an arbitrary function estimator into a decision about each bit. Given \(\hat f\), project it onto the \(j\)th bump and define

Here \(\langle g_1,g_2\rangle=\int g_1(x)g_2(x)\,dx\). The true coefficient along \(\psi_j\) is \(a h^\alpha\theta_j\), because the bump supports are disjoint. If \(\hat\theta_j\ne\theta_j\), the coefficient error is at least \(a h^\alpha/2\). Orthogonality of the bumps implies that the squared estimation error is at least the sum of its squared projections onto their span. Consequently,

Proof. Pair each vector with \(\theta_j=0\) with its neighbor \(\theta^{(j)}\) having bit \(j\) equal to \(1\). For any such pair, let \(A\) be the event that the decision is \(1\). The sum of the two error probabilities is \(P_\theta(A)+P_{\theta^{(j)}}(A^c)=1+P_\theta(A)-P_{\theta^{(j)}}(A)\). By the definition of total variation distance, the absolute difference between the probabilities of any event is at most that distance. The displayed sum is therefore at least \(1-\tau\). There are \(2^{M-1}\) pairs; averaging their error sums over all \(2^M\) vectors gives the asserted bound. \(\square\)

Assouad Lower Bound for Hölder Risk

Proof. Choose a nonzero smooth bump \(\psi\) as above and a fixed \(a>0\) small enough that \(C_{\psi,\alpha,d}a\leq L\). Choose a constant \(\gamma>0\) with \(\gamma\leq1/4\) and \(a^2\|\psi\|_2^2\gamma^{2\alpha+d}/(2\sigma^2)\leq1/8\), and set \(h=\gamma n^{-1/(2\alpha+d)}\). Then \(h\leq1/4\), and every \(f_\theta\) belongs to the Hölder ball. For every neighboring pair, \[ \operatorname{KL}(P_\theta,P_{\theta^{(j)}}) =\frac{n a^2 h^{2\alpha+d}\|\psi\|_2^2}{2\sigma^2} =\frac{a^2\|\psi\|_2^2\gamma^{2\alpha+d}}{2\sigma^2} \leq\frac18. \] Pinsker’s inequality, \(\operatorname{TV}(P,Q)\leq\sqrt{\operatorname{KL}(P,Q)/2}\), thus gives neighboring total variation at most \(1/4\). By the lemma, each coordinate’s average bit-error probability is at least \((1-1/4)/2=3/8\).

For any estimator, the projection inequality gives its average risk over the hypercube at least \((B/4)M(3/8)=3MB/32\). Since \(h\leq1/4\), \(q=\lfloor1/(2h)\rfloor\geq1/(4h)\), so \(M=q^d\geq(4h)^{-d}\). Substituting \(B=a^2h^{2\alpha+d}\|\psi\|_2^2\) yields \[ 2^{-M}\sum_\theta R_{f_\theta}(\hat f) \geq \frac{3a^2\|\psi\|_2^2}{32\cdot4^d}h^{2\alpha} =\frac{3a^2\|\psi\|_2^2\gamma^{2\alpha}}{32\cdot4^d} n^{-2\alpha/(2\alpha+d)}. \] The supremum risk over the Hölder ball is at least this average risk over a finite subset of the ball. Taking the infimum over estimators proves the claim, with the displayed positive coefficient as one possible constant. \(\square\)

Interpreting the Rate and Avoiding a Pitfall

The lower bound matches the characteristic exponent \(2\alpha/(2\alpha+d)\) for integrated squared-error estimation: increasing smoothness makes the risk decrease faster, while increasing dimension slows that decrease. The dimension appears in the number of independently testable locations, \(M\), as well as in the bump’s volume \(h^d\). This argument is a lower bound: it rules out uniformly better rates over the stated class, but does not by itself construct an estimator attaining the bound.

• Pitfall: use only one pair of functions. A two-point comparison can establish a lower bound from one difficult perturbation, but it does not automatically collect the errors from many local features. The correction is to index the functions by all \(M\) bits and sum the coordinatewise testing errors.
• Pitfall: count bumps but ignore their volume. There are order \(h^{-d}\) locations, but each coordinate’s squared separation is only order \(a^2h^{2\alpha+d}\). Their product is order \(a^2h^{2\alpha}\), not order \(a^2h^{2\alpha+d}\).
• Pitfall: make neighboring distributions too easy to distinguish. The coordinate argument needs controlled total variation between neighbors. Here the choice \(h\) proportional to \(n^{-1/(2\alpha+d)}\) keeps the neighboring Kullback–Leibler divergence bounded while retaining enough separated locations.