Boundary-Localized Bump Lower Bounds

Why Localize a Perturbation at the Boundary?

In binary classification, changing a regression function far from the decision boundary may change its numerical values without changing the optimal classifier. A more consequential perturbation is one that changes the sign of \(\eta(x)-1/2\) close to the boundary. There, a small change in the regression function can reverse the preferred label, while smoothness limits how large and how sharply localized that change can be.

The construction below isolates three scales. A bump of width \(h\) occupies design probability of order \(h^d\). Smoothness of order \(\beta\) permits amplitude of order \(h^\beta\). When the bump changes the classifier, the affected strip has normal width of order \(h^\beta\) and tangential size of order \(h^{d-1}\). These scales combine to produce a lower bound.

Definition: For a binary response \(Y\in\{0,1\}\), write \(\eta(x)=P(Y=1\mid X=x)\). A classifier \(g\) maps covariates \(x\) to labels 0 or 1. Its excess risk is \(R(g)-R^*\), where \(R(g)=P(g(X)\ne Y)\) and \(R^*=\inf_g R(g)\). The Bayes classifier is \(g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}\), with either label permissible at a tie.

Conditionally on \(X=x\), predicting the non-Bayes label increases the error probability by \(|2\eta(x)-1|\). Consequently,

R(g)-R^*=\int |2\eta(x)-1|\, \mathbf{1}\{g(x)\ne g^*(x)\}\,dP_X(x).

This identity explains why the useful region is not merely where two regression functions differ. It is where their Bayes labels differ and both models assign non-negligible weight to a classification error.

A Smooth Boundary Bump

Let \(X\) be uniform on \([0,1]^d\), with \(d\ge 1\). Use coordinates \(x=(x_1,x')\), where \(x'\in[0,1]^{d-1}\); when \(d=1\), there are no tangential coordinates. Take an integer smoothness order \(\beta\ge1\). Let \(\psi_0\) and \(\psi_1\) be fixed, nonnegative, infinitely differentiable functions supported on \([-1,1]\), with \(\psi_0(s)=1\) for \(|s|\le1/2\) and \(\psi_1(u)\ge c_0>0\) for \(|u|\le1/2\). For \(d=1\), omit \(\psi_1\).

For a small width \(h>0\), define a boundary-localized bump

b_h(x)=a h^\beta \psi_0\!\left(\frac{x_1-1/2}{h}\right) \prod_{j=2}^{d}\psi_1\!\left(\frac{x_j-1/2}{h}\right),

where \(a>0\) is a fixed, sufficiently small constant. Its support lies in a box of side order \(h\) centered on the plane \(x_1=1/2\). Compare the regression functions

\eta_0(x)=\frac12+\kappa(x_1-1/2), \qquad \eta_1(x)=\eta_0(x)-b_h(x),

for a fixed \(0<\kappa\le1/4\). The first model has a flat decision boundary at \(x_1=1/2\). The second lowers \(\eta\) locally, moving the boundary in the bump’s tangential patch. Choose \(a\) small enough that both functions stay in \([1/4,3/4]\).

Scaling fact: For any multi-index \(\nu\) of order \(|\nu|\le\beta\), differentiating the rescaled bump gives a factor \(h^{-|\nu|}\). Thus \[ \|D^\nu b_h\|_\infty\le C_\nu a h^{\beta-|\nu|}\le C_\nu a \quad\text{when }0<h\le1. \] The perturbations therefore have uniformly bounded derivatives through order \(\beta\). The amplitude \(h^\beta\) is what allows localization to width \(h\) without violating this smoothness bound.

Worked Example: Checking the Smoothness Scaling

Take \(\beta=2\). The bump amplitude is \(a h^2\). One derivative in a coordinate where the bump varies contributes a factor \(h^{-1}\), so its first derivative has size at most \(C a h\). Two derivatives contribute \(h^{-2}\), so its second derivatives have size at most \(C a\). In particular, shrinking \(h\) does not make the second derivatives diverge.

If instead the amplitude were \(a h\), the second derivatives could be of order \(a/h\), which grows without bound as \(h\) shrinks. That scaling would not give a uniformly bounded second-derivative class. This is why a smoothness order \(\beta\) pairs with amplitude \(h^\beta\).

Worked Example: The Design Probability of the Bump

For \(d=3\), the support is contained in a box of side length \(2h\) in each of the three coordinates. Under the uniform design, its probability is at most \((2h)^3=8h^3\). More precisely, a change of variables \(s_1=(x_1-1/2)/h\), \(s_j=(x_j-1/2)/h\) for \(j=2,3\) gives \[ \int b_h(x)^2\,dx =a^2h^{2\beta+3} \left(\int\psi_0(s)^2\,ds\right) \left(\int\psi_1(u)^2\,du\right)^2. \] The probability of encountering the support is of order \(h^3\), while the squared perturbation integrated over the design is of order \(h^{2\beta+3}\). These are distinct quantities: the latter includes the squared amplitude.

The Disagreement Region and the Margin Condition

On a tangential patch of side order \(h\), the bump is bounded below by a constant times \(a h^\beta\). For positive \(t=x_1-1/2\) of order \(h^\beta\), \(\eta_0(x)-1/2=\kappa t\) is positive, but \(\eta_1(x)-1/2=\kappa t-b_h(x)\) is negative. The Bayes labels therefore differ in a strip whose normal width is order \(h^\beta\). Its design probability is order \(h^{d-1}h^\beta\).

On a smaller strip, both models’ classification margins are order \(h^\beta\). Integrating the excess-risk weight over that strip gives order \(h^\beta\cdot h^{d-1+\beta}=h^{2\beta+d-1}\).

The pair can also satisfy a uniform margin condition with exponent one. For \(\eta_0\), the derivative in the \(x_1\) direction is \(\kappa\). For \(\eta_1\), it is \[ \frac{\partial\eta_1}{\partial x_1} =\kappa-a h^{\beta-1}\psi_0'\!\left(\frac{x_1-1/2}{h}\right) \prod_{j=2}^d\psi_1\!\left(\frac{x_j-1/2}{h}\right). \] Choose \(a\) small enough (for \(\beta=1\)) or \(h\) small enough (for \(\beta>1\)) that this derivative is at least \(\kappa/2\). For fixed \(x'\), monotonicity and the mean value theorem then imply that the set of \(x_1\) with \(|\eta_j(x)-1/2|\le u\) has length at most \(4u/\kappa\). Integrating over \(x'\) yields \[ P\bigl(|2\eta_j(X)-1|\le s\bigr)\le \frac{2s}{\kappa}, \qquad j=0,1. \] Thus both models obey a linear small-margin bound with a constant independent of \(h\).

Worked Example: Locating a Region of Opposite Bayes Labels

Suppose \(d=2\), and consider \(x_2\) in the interval \([1/2-h/2,1/2+h/2]\). There the tangential bump factor is at least \(c_0\). For small enough \(h\), take \[ \frac{a c_0 h^\beta}{8\kappa} \le t=x_1-\frac12 \le \frac{a c_0 h^\beta}{4\kappa}. \] This interval has width \(a c_0h^\beta/(8\kappa)\). Its points satisfy \(t/h\le1/2\) if \(a c_0h^{\beta-1}/(4\kappa)\le1/2\), so the normal bump factor equals one. Hence \(b_h(x)\ge a c_0h^\beta\).

Here \(\eta_0-1/2=\kappa t>0\), while \[ \eta_1-\frac12 \le \frac{a c_0h^\beta}{4}-a c_0h^\beta =-\frac{3a c_0h^\beta}{4}<0. \] The labels disagree throughout this region. Its area is at least \[ \frac{a c_0h^\beta}{8\kappa}\,h =\frac{a c_0}{8\kappa}h^{\beta+1}, \] and the smaller of the two margins \(|2\eta_j-1|\) is at least \(a c_0h^\beta/4\). Their product, integrated over the region, is therefore at least a positive constant times \(h^{2\beta+1}\).

From Indistinguishability to a Lower Bound

Let \(P_j\) denote the joint distribution of one observation \((X,Y)\) under regression function \(\eta_j\). The design distribution is the same under both models, and conditional on \(X=x\), \(Y\) is Bernoulli with success probability \(\eta_j(x)\). The next result quantifies what a single localized bump can imply for minimax excess risk.

Theorem: Fix \(d\ge1\) and integer \(\beta\ge1\). For suitable fixed \(\kappa,a>0\), the two regression functions above belong to a common bounded smoothness class and satisfy a uniform linear margin condition. For all sufficiently large \(n\), any classifier \(\hat g\) constructed from \(n\) independent observations has, for at least one of the two models, expected excess risk at least \[ C n^{-(2\beta+d-1)/(2\beta+d)}, \] where \(C>0\) does not depend on \(n\). In particular, this is a minimax lower bound for any class containing these models at the chosen width.

Proof. First bound the divergence between the sample distributions. For Bernoulli probabilities \(p,q\in[1/4,3/4]\), \[ p\log\frac pq+(1-p)\log\frac{1-p}{1-q} \le \frac{(p-q)^2}{q(1-q)}. \] This follows by applying \(\log z\le z-1\) to both logarithms and simplifying. Since \(q(1-q)\ge3/16\), the conditional divergence is at most \((16/3)(p-q)^2\). The design is uniform, and \(\eta_0-\eta_1=b_h\), so \[ \operatorname{KL}(P_0,P_1) \le C a^2 h^{2\beta+d}. \] Independence makes the divergence of the \(n\)-observation distributions \(P_0^n,P_1^n\) at most \(C n a^2h^{2\beta+d}\).

Choose \(h=c n^{-1/(2\beta+d)}\), where the fixed \(c>0\) is small enough that this last bound is at most \(1/2\). Pinsker’s inequality, \(\operatorname{TV}(P_0^n,P_1^n)\le\sqrt{\operatorname{KL}(P_0^n,P_1^n)/2}\), then gives total variation at most \(1/2\).

Let \(A_h\) be the disagreement strip constructed above, and write \(m(x)=\min\{|2\eta_0(x)-1|,|2\eta_1(x)-1|\}\). The strip argument gives \[ \int_{A_h}m(x)\,dx\ge C_1 h^{2\beta+d-1}. \] For each fixed \(x\in A_h\), the decision \(\hat g(\cdot,x)\) based on the data acts as a test between the two models: output 1 is an error relative to the Bayes label under model 0, and output 0 is an error under model 1. For any such test, the sum of its two error probabilities is at least \(1-\operatorname{TV}(P_0^n,P_1^n)\). This follows directly from the definition of total variation: if \(B\) is the event that the test outputs 1, then \[ P_0^n(B)+P_1^n(B^c) =1-\{P_1^n(B)-P_0^n(B)\} \ge1-\operatorname{TV}(P_0^n,P_1^n). \] Using the excess-risk identity and integrating this inequality over \(A_h\) gives \[ E_0[R(\hat g)-R_0^*]+E_1[R(\hat g)-R_1^*] \ge \bigl(1-\operatorname{TV}(P_0^n,P_1^n)\bigr) \int_{A_h}m(x)\,dx \ge \frac{C_1}{2}h^{2\beta+d-1}. \] At least one of the two expected excess risks is at least half this sum. Substituting \(h=c n^{-1/(2\beta+d)}\) proves the claimed rate. \(\square\)

Worked Example: Reading the Rate in Two Dimensions

For \(d=2\) and \(\beta=2\), the bump amplitude is \(h^2\), the support probability is order \(h^2\), and the integrated squared perturbation is order \(h^6\). Thus the sample divergence is order \(nh^6\), which stays bounded when \(h\) is chosen proportional to \(n^{-1/6}\).

The disagreement strip has tangential length order \(h\) and normal width order \(h^2\), so its area is order \(h^3\). The margin weight there is order \(h^2\). The excess-risk contribution is therefore order \(h^5\), or \(n^{-5/6}\) after substituting \(h\asymp n^{-1/6}\). Each exponent comes from a different part of the construction: \(2\beta+d\) in the divergence and \(2\beta+d-1\) in the weighted disagreement region.

What the Construction Does—and Does Not—Show

The lower bound is a balance between statistical visibility and classification impact. Making \(h\) smaller reduces the divergence, making the two models harder to distinguish from data. But it also shrinks the region where their Bayes decisions differ. The width \(h\) is chosen so that the sample divergence remains bounded; the resulting weighted disagreement determines the lower bound.

A single bump proves a valid lower bound for a class containing the constructed pair, but it need not give the sharp minimax rate. It uses just one tangential patch. A richer lower-bound construction can place perturbations in many patches and use the accumulated difficulty; the geometry and the number of patches then matter. The single-bump calculation is useful because it makes the role of each scale explicit.

Common Mistake

Counting the bump’s support as the excess-risk region. The support has probability order \(h^d\), but much of it need not have opposite Bayes labels. The relevant disagreement strip has tangential size order \(h^{d-1}\) and normal width order \(h^\beta\); excess risk also weights that strip by a margin of order \(h^\beta\).
Using amplitude \(h^\beta\) without checking derivatives. The derivative scaling is \(h^{\beta-|\nu|}\), not simply \(h^\beta\). Smoothness is verified by checking the largest derivative order in the class.
Calling bounded divergence a classification lower bound by itself. Indistinguishability matters only where the Bayes labels disagree. The weighted disagreement integral is what converts the testing difficulty into excess risk.

Key takeaway: A boundary bump of width \(h\) and smoothness-limited amplitude \(h^\beta\) has integrated squared size of order \(h^{2\beta+d}\). It can create a weighted disagreement region of order \(h^{2\beta+d-1}\). Balancing \(nh^{2\beta+d}\) at a constant yields the single-bump minimax lower bound.

Check Your Understanding

Check whether you can track each scale in the construction.

Why does a derivative of order \(|\nu|\) of the bump have size of order \(h^{\beta-|\nu|}\)?
Under a uniform design in dimension \(d\), what is the order of the bump’s support probability?
Why is the normal width of the disagreement strip of order \(h^\beta\), rather than \(h\), when \(\beta>1\)?
What is the order of the integrated squared perturbation, and how does it enter the sample divergence?
Explain why the weighted disagreement integral has order \(h^{2\beta+d-1}\).