Boundary-Fragment Classification Models

Why Describe a Classifier by Its Boundary?

In binary classification, the Bayes rule changes its label where the conditional class probability crosses one half. In some problems, that boundary has structure: it can be represented as a smooth surface rather than an arbitrary subset of the covariate space. A boundary-fragment model makes that structure explicit. Its key consequence is that a boundary can be approximated using fewer local pieces than a general classifier, while the probability mass near the boundary determines how costly a small location error is.

We develop two complementary calculations. First, if a graph is approximated to a given vertical accuracy, a near-boundary probability condition converts that accuracy into a bound on excess classification risk. Second, an explicit noisy-label model gives a lower bound: many small, smooth boundary perturbations are hard to distinguish from data, and their aggregate classification cost determines a minimax rate.

Boundary-Fragment Model

Write a covariate as \(X=(U,V)\), where \(U\in[0,1]^p\), \(V\in[0,1]\), and \(p=d-1\). A boundary fragment is described by a function \(b:[0,1]^p\to[1/4,3/4]\). The associated threshold classifier labels points below and above its graph differently.

For a noninteger \(\beta>0\), a Hölder class \(C^\beta(L)\) bounds the derivatives through order \(\lfloor\beta\rfloor\) and requires the derivatives of that highest order to be Hölder continuous with exponent \(\beta-\lfloor\beta\rfloor\), with norm at most \(L\). The precise convention at integer smoothness does not affect the rate calculations below. The central approximation property is that local polynomial approximation on cells of side length \(w\) can achieve vertical error at most \(Cw^\beta\), for a constant \(C\) depending on the smoothness bound and dimension.

Let \(\eta(x)=P(Y=1\mid X=x)\), and let \(g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}\) be the Bayes classifier. For any classifier \(g\), its excess risk is \(R(g)-R(g^*)\), where \(R(g)=P(g(X)\ne Y)\). The identity

shows why geometric error alone is not enough: its classification cost depends on both the probability of the region where the rules disagree and the conditional label gap there.

From Boundary Approximation to Excess Risk

A useful way to express near-boundary probability is through a tube around the graph. Suppose there are constants \(C_0>0\), \(\alpha>0\), and \(r_0>0\) such that

The exponent \(\alpha\) describes how quickly probability accumulates in a narrow tube. For example, a density that is bounded and positive at a flat boundary typically gives \(\alpha=1\). A density that vanishes near the boundary can give a larger exponent.

Proof. If \(g_{\tilde b}(u,v)\ne g_b(u,v)\), then \(v\) lies between \(b(u)\) and \(\tilde b(u)\). Consequently, \(|v-b(u)|\le|\tilde b(u)-b(u)|\le\delta\). The disagreement event is therefore contained in the tube \(\{|V-b(U)|\le\delta\}\). Applying the excess-risk identity, bounding the label gap by \(M\), and then applying the tube condition gives

This proves the proposition. In particular, a boundary approximation with error of order \(w^\beta\) has excess risk at most order \(w^{\alpha\beta}\), under these assumptions. This is an approximation statement: by itself it does not show that data can estimate the graph to that accuracy.

A Model for a Minimax Lower Bound

To see how data difficulty depends on smoothness and near-boundary mass, consider the following explicit family. Let \(U\) be uniform on \([0,1]^p\), independent of a vertical coordinate \(V\) with density

This is a probability density: integrating on each side of \(1/2\) gives total integral \(1\). In particular, for \(0<r\le1/2\),

For a boundary function \(b\), let the conditional label probability be \(\varepsilon\) below the graph and \(1-\varepsilon\) above it, with fixed \(0<\varepsilon<1/2\). Thus \(g_b\) is Bayes-optimal and the label gap away from the graph is \(s=1-2\varepsilon>0\). The covariate distribution is fixed across the boundary functions; only the conditional label law changes.

We use smooth, nonnegative bumps on disjoint horizontal cells. Take a fixed smooth function \(\psi\), supported inside the unit cube, with \(0\le\psi\le1\) and positive on a set of positive volume. For cells of side \(w\), place scaled copies \(\psi_j\) on \(m\) disjoint cells, where \(m\ge c w^{-p}\) for a constant \(c>0\). For \(\theta=(\theta_1,\ldots,\theta_m)\in\{0,1\}^m\), define

where \(a>0\) is fixed and sufficiently small. The supports are disjoint, so these functions remain in a fixed Hölder ball of smoothness \(\beta\), and their values remain in \([1/4,3/4]\) for small enough \(w\).

The infimum is over classifiers based on \(n\) independent observations, and \(E_\theta\) averages over the training data under parameter \(\theta\). The bound applies to any estimator, not just graph estimators.

Proof. First compare two parameters that differ only in coordinate \(j\). Their conditional label distributions differ only in the vertical strip between \(1/2\) and \(1/2+aw^\beta\psi_j(u)\). On this strip, one distribution has label probability \(\varepsilon\) and the other \(1-\varepsilon\). The Kullback–Leibler divergence between these two Bernoulli distributions is the finite positive constant

Outside the strip the conditional laws agree. Integrating the divergence over the fixed covariate density gives, for one observation, a divergence at most \(C_2w^p(aw^\beta)^\alpha\). Indeed, at a horizontal location \(u\) in the cell the strip has probability mass

and integrating over a cell of volume \(w^p\) gives the claimed bound. For \(n\) independent observations, the divergence is at most \(C_2 n w^{p+\alpha\beta}\).

Choose \(w\) proportional to \(n^{-1/(p+\alpha\beta)}\), with a sufficiently small proportionality constant. Then every neighboring pair has divergence at most a fixed small constant. Pinsker’s inequality, \(\operatorname{TV}(P,Q)\le\sqrt{\operatorname{KL}(P,Q)/2}\), makes the total variation distance of each such pair at most \(1/2\).

It remains to connect difficulty in testing the bits to classification loss. In cell \(j\), the two boundary choices disagree on a strip whose covariate probability is

where \(C_3>0\) because \(\psi\) is positive on a set of positive volume. Decode the \(j\)th bit by deciding which of the two Bayes labels the fitted classifier predicts on at least half of this strip, measured by covariate probability. If the decoded bit is wrong, the classifier mislabels at least half the strip under the true boundary choice. Its excess risk there is at least \(sA_j/2\).

For each pair of parameters differing in bit \(j\), the sum of the two testing error probabilities is at least \(1-\operatorname{TV}\), hence at least \(1/2\). Averaging over all \(2^m\) parameter vectors therefore gives expected bit-error count at least \(m/4\). The average excess risk is consequently at least

because \(m\ge c w^{-p}\). Substituting \(w\) proportional to \(n^{-1/(p+\alpha\beta)}\) yields the stated lower bound. A supremum risk is at least the average risk over this finite family, so the result follows. \(\square\)

Interpreting the Exponents

The lower-bound construction balances the information in one local perturbation against the number of places it can occur. A bump has height of order \(w^\beta\), so its disagreement strip has probability of order \(w^p(w^\beta)^\alpha=w^{p+\alpha\beta}\). Its data distinguishability is proportional to \(n\) times that probability. Setting this quantity to a constant gives \(w\) of order \(n^{-1/(p+\alpha\beta)}\). Across order \(w^{-p}\) possible cells, a constant fraction of the bits remain difficult to recover; the resulting total excess risk is order \(w^{\alpha\beta}\).

This calculation depends on the specified model. It is a lower bound, not a proof of a matching upper bound for every boundary-fragment problem. An upper bound would additionally require an estimator and assumptions ensuring it can use the observations efficiently. The earlier material on margin exponents describes probability near small conditional label gaps; here the exponent \(\alpha\) has been given a concrete geometric interpretation through probability mass near a graph.

Common Pitfall

• Wrong reasoning: “A graph approximation error of \(\delta\) always gives excess risk of order \(\delta\).” This assumes, without checking, that probability accumulates linearly around the boundary and that the label gap is controlled.
• Correction: Use the excess-risk identity and state the relevant assumptions. Under a tube bound \(P(|V-b(U)|\le r)\le C_0r^\alpha\) and label-gap bound \(M\), the direct bound is \(MC_0\delta^\alpha\). In the explicit lower-bound model, the same exponent \(\alpha\) enters the probability of a local disagreement strip and therefore changes the testing balance.