Bump Hypercubes for Function Estimation

Why Localized Bumps Create Hard Function Families

A useful lower-bound construction should have many alternatives that are separated as functions, yet statistically difficult to distinguish when one small part of the function changes. A bump hypercube achieves both goals: place a scaled copy of one localized function on each of many disjoint cells, then independently switch each copy on or off. The resulting family is indexed by binary vectors, and changing one bit alters the function only on one cell.

The construction is particularly useful for applying Assouad’s lemma to function estimation. The geometry is controlled by the bump’s norm and the cell width; the statistical difficulty is controlled by the divergence between distributions corresponding to neighboring binary vectors. These two calculations are separate and should be checked separately.

Definition of a Bump Hypercube

Let the domain be \([0,1]^d\), let \(m\) be a positive integer, and set \(h=1/m\). Partition the domain into \(J=m^d\) cubes of side length \(h\), ignoring shared boundaries, which have Lebesgue measure zero. Index the cubes by \(k\in\{0,\ldots,m-1\}^d\), and let \(x_k=hk\) be the lower corner of cube \(k\). Choose a nonzero function \(\psi\) supported inside \((0,1)^d\). For a scale \(a>0\), define the localized bump

Because the support of \(\psi\) lies strictly inside the unit cube, the supports of distinct \(\psi_k\) are disjoint and do not cross cell boundaries. Thus \(f_\theta\) switches a local feature on or off on each cell, without overlap between features.

For integer smoothness \(s\), a sufficient regularity condition is \(\psi\in C_c^s((0,1)^d)\), meaning that \(\psi\) has continuous derivatives through order \(s\) and compact support inside the open unit cube. For a multi-index \(\nu\) of order \(|\nu|\le s\), the chain rule gives

Since \(h\le1\), these derivatives are bounded by \(a\|D^\nu\psi\|_\infty\). Disjoint supports ensure that the same bound applies to the sum \(f_\theta\), rather than growing with the number of cells. To place every vertex in a specified smoothness ball, choose \(a\) small enough for the ball’s derivative bounds. Merely requiring \(\psi\) to be nonzero and supported inside the unit cube does not guarantee any derivative regularity; the smoothness assumption must be imposed when the target function class requires it.

Metric Separation: A General Calculation

To prove the formula, write the difference as a sum over the cells on which the bits disagree. On each such cell, the difference is either \(\psi_k\) or \(-\psi_k\). Since the supports are disjoint, the \(p\)th power of the absolute value of the sum equals the sum of the \(p\)th powers pointwise, apart from boundaries of measure zero. A change of variables \(u=(x-x_k)/h\), with \(dx=h^d\,du\), gives

There are exactly \(H(\theta,\theta')\) disagreeing cells, proving the displayed equality. For \(p=2\), write \(\delta=a h^{s+d/2}\|\psi\|_2\). Then \(\|f_\theta-f_{\theta'}\|_2^2=\delta^2 H(\theta,\theta')\). This exact linear relation between squared distance and Hamming distance is what makes squared \(L^2\) loss especially convenient.

Neighboring Divergence in Gaussian Regression

Consider \(n\) independent observations \((X_i,Y_i)\), with \(X_i\) uniform on \([0,1]^d\) and \(Y_i\mid X_i=x\sim N(f_\theta(x),\sigma^2)\), where \(\sigma^2>0\) is fixed. Denote the joint data distribution by \(P_\theta^n\). For neighboring vertices, the two regression functions differ by one bump. The Kullback–Leibler divergence is

For completeness, two normal distributions with the same variance and respective means \(\mu,\mu'\) have divergence \((\mu-\mu')^2/(2\sigma^2)\), as follows by taking the expectation under the first distribution of the log density ratio. Conditioning on \(X=x\) therefore gives divergence \((f_\theta(x)-f_{\theta'}(x))^2/(2\sigma^2)\). The covariate distribution is the same under both models, so averaging over the uniform covariate integrates this expression over \([0,1]^d\). Independence makes the divergence of \(n\) observations \(n\) times the one-observation divergence. Finally, a neighboring pair differs by one scaled bump, whose squared integral is \(a^2h^{2s+d}\|\psi\|_2^2\) by the change-of-variables calculation above. Combining these steps proves the result.

From Edge Difficulty to a Function-Risk Bound

The preceding calculations supply the two ingredients for an Assouad argument: each edge of the hypercube has function separation \(\delta\), and the distributions at its endpoints have small total variation distance. The following direct derivation makes the squared \(L^2\) consequence explicit. Assume the vertices belong to the function class under study, and let \(\widehat f\) be any measurable estimator taking values in \(L^2([0,1]^d)\). For each cell define a bit estimate by projecting \(\widehat f\) onto \(\psi_k\):

If \(\widehat\theta_k\ne\theta_k\), the projected coefficient differs from the true coefficient \(\theta_k\in\{0,1\}\) by at least \(1/2\). By Cauchy–Schwarz, the squared estimation error on that cell is at least \(\|\psi_k\|_2^2/4=\delta^2/4\). Summing over disjoint cells gives

For any neighboring pair \(\theta,\theta'\) differing in coordinate \(k\), the average error probability for testing that bit under equal prior probabilities is at least \((1-\operatorname{TV}(P_\theta^n,P_{\theta'}^n))/2\). This testing inequality follows because the sum of the two error probabilities for any test is at least \(1-\operatorname{TV}\). Average the risk uniformly over all \(2^J\) vertices, pair vertices along each of the \(J\) coordinates, and apply the inequality to each pair. If every edge has total variation at most \(\tau\), the average number of bit errors is at least \(J(1-\tau)/2\). Therefore

The first inequality holds because the maximum is at least the average. Since this bound applies to every estimator, it also lower-bounds the minimax squared \(L^2\) risk over any function class containing the hypercube. In Gaussian regression, Pinsker’s inequality gives \(\operatorname{TV}(P,Q)\le\sqrt{D_{\mathrm{KL}}(P\|Q)/2}\). Thus, if every neighboring KL divergence is at most \(1/8\), then \(\tau\le1/4\), and the risk is at least \(3J\delta^2/32\). \(\square\)

A Bernoulli Regression Divergence Check

The same bump geometry can be used with a different observation model, provided the regression probabilities stay away from zero and one. For example, let \(X_i\) again be uniform, and let \(Y_i\mid X_i=x\) be Bernoulli with success probability \(p_\theta(x)=1/2+f_\theta(x)\). Suppose every vertex satisfies \(|f_\theta(x)|\le1/4\), so all probabilities lie in \([1/4,3/4]\).

Common Pitfalls and Practical Checks

• Assuming support implies smoothness. A nonzero function supported inside a cube need not have even one derivative. For integer smoothness \(s\), require bounded derivatives through order \(s\), for example by taking \(\psi\in C_c^s((0,1)^d)\).
• Forgetting the volume factor. Scaling the argument by \(1/h\) changes the integral by \(h^d\). Thus the \(L^2\) norm scales as \(h^{s+d/2}\), not merely \(h^s\).
• Multiplying neighboring divergence by the number of cells. An edge changes exactly one bit, so its divergence contains one bump’s squared integral. The factor \(J\) enters later when summing testing errors across coordinates.
• Ignoring model constraints. A Bernoulli regression probability must remain in \([0,1]\), and a smoothness class imposes derivative bounds. Check the amplitude \(a\) against both conditions before claiming that the hypercube lies in the model class.

The construction’s value is its modularity. The cell width and smoothness exponent determine the signal size on one edge; the observation model determines the edge divergence. Once the vertices are valid and the edge distributions are sufficiently close, the many binary decisions force a nontrivial estimation risk.