Approximating Bayes Decision Boundaries in an RKHS

Bayes Decisions and Score Approximation

An RKHS classifier makes decisions by taking the sign of a score function. The challenge in approximating a Bayes classifier is that its decision rule is a sign pattern, while many approximation tools control numerical errors in the score itself. The connection is sensitive to where those errors occur: a score error far from the Bayes boundary may not change a decision, whereas a small error near the boundary can do so. The amount of probability near that boundary determines how much such disagreements matter for risk.

Let $X$ be an input and $Y\in\{-1,+1\}$ its label. Write $\eta(x)=P(Y=+1\mid X=x)$ and $g(x)=2\eta(x)-1=E[Y\mid X=x]$. Use the decision convention $\operatorname{sign}(u)=+1$ for $u\geq 0$ and $-1$ for $u<0$. The Bayes classifier is $f^*(x)=\operatorname{sign}(g(x))$. When $g(x)=0$, either decision has the same conditional classification risk.

Definition: The Bayes boundary is the set where $g(x)=0$; the Bayes decision changes across locations where $g$ changes sign. For a score $f$, its classification rule is $\operatorname{sign}(f(x))$. Its excess classification risk is $R(\operatorname{sign}f)-R(f^*)$, where $R(a)=P(a(X)\ne Y)$.

The conditional excess risk at $x$ is $|g(x)|$ if the classifier disagrees with the Bayes decision, and zero otherwise. Therefore

R(\operatorname{sign}f)-R(f^*) = E\!\left[|g(X)|\,\mathbf{1}\{\operatorname{sign}f(X)\ne\operatorname{sign}g(X)\}\right].

This identity makes the role of the boundary explicit. A disagreement where $|g(X)|$ is small contributes little; a disagreement where $|g(X)|$ is large is more costly.

Squared-Loss Approximation and Classification Risk

A useful way to quantify score approximation is squared loss against the observed label. Its conditional mean target is $g$, since $E[Y\mid X]=g(X)$. The following identity shows exactly what its approximation error measures.

Theorem: For any measurable score $f$ with finite second moment, $$ E[(f(X)-Y)^2]-E[(g(X)-Y)^2]=E[(f(X)-g(X))^2]. $$ Thus excess squared-loss risk is precisely the mean squared error in approximating the conditional mean score.

Proof. Given $X$, write $f-Y=(f-g)+(g-Y)$. Expanding the square and taking the conditional expectation gives

E[(f-Y)^2\mid X] =(f-g)^2+2(f-g)E[g-Y\mid X]+E[(g-Y)^2\mid X].

Because $E[Y\mid X]=g$, the middle term is zero. The last term is $E[(g-Y)^2\mid X]$, so subtracting it and then taking expectation over $X$ proves the identity. Finite second moments ensure the displayed expectations exist. $\square$

For an RKHS $\mathcal H$, define the best squared-loss approximation available within a norm budget $B$:

A(B)=\inf_{\substack{h\in\mathcal H\\ \|h\|_{\mathcal H}\leq B}} E[(h(X)-g(X))^2].

The theorem says $A(B)$ is also the smallest excess squared-loss risk attainable by an RKHS score with norm at most $B$. It is an approximation profile: increasing $B$ allows more complex scores, but does not guarantee that approximation error decreases at any particular rate. That depends on the kernel, the distribution of $X$, and the structure of $g$.

Worked Example: A Linear RKHS Represents a Simple Bayes Score

Let $X$ be uniform on $[-1,1]$, and specify $P(Y=+1\mid X=x)=(1+x)/2$. This is a valid probability because it lies in $[0,1]$. Then $g(x)=2P(Y=+1\mid X=x)-1=x$, so the Bayes boundary is at zero.

Use the linear kernel $K(x,x')=xx'$, whose RKHS consists of scores $h(x)=wx$ with norm $\|h\|_{\mathcal H}=|w|$. Taking $h(x)=x$ gives $E[(h(X)-g(X))^2]=0$, with norm $1$. By the squared-loss identity, its excess squared-loss risk is zero; its sign also agrees with the Bayes decision except at $x=0$, a probability-zero point.

This case has no approximation difficulty once the norm budget reaches $1$. The conclusion depends on the match between the target and the RKHS; a different kernel or target need not have this property.

A Boundary-Mass Bound

Define the probability of a $t$-wide score margin around the Bayes boundary by $m(t)=P(|g(X)|\leq t)$, for $t>0$. This quantity includes the probability of points on the boundary as well as points where the Bayes decision is weakly separated. It depends on both the conditional label probabilities and the distribution of inputs.

Theorem: For any measurable score $f$ with $E[(f(X)-g(X))^2]<\infty$, and any $t>0$, $$ R(\operatorname{sign}f)-R(f^*) \leq t\,m(t)+\frac{E[(f(X)-g(X))^2]}{t}. $$

Proof. Split the excess-risk identity into inputs with $|g(X)|\leq t$ and those with $|g(X)|>t$. The first part is at most $tP(|g(X)|\leq t)=tm(t)$, since the risk weight $|g(X)|$ is at most $t$ there. On the remaining inputs, a disagreement of signs implies $|f(X)-g(X)|\geq |g(X)|>t$: two numbers on opposite sides of zero must differ by at least the magnitude of either one. In particular, on this disagreement event, \[ |g(X)|\leq \frac{(f(X)-g(X))^2}{|g(X)|} \leq \frac{(f(X)-g(X))^2}{t}. \] Integrating bounds the second part by $E[(f(X)-g(X))^2]/t$. Adding the two bounds proves the result. $\square$

Applying the theorem to a norm-constrained RKHS score gives, for any $B$ and $t>0$,

\inf_{\substack{h\in\mathcal H\\\|h\|_{\mathcal H}\leq B}} \bigl(R(\operatorname{sign}h)-R(f^*)\bigr) \leq t\,m(t)+\frac{A(B)}{t}.

This follows by applying the bound to each admissible $h$ and taking the infimum; if the infimum defining $A(B)$ is not attained, scores with squared error arbitrarily close to it give the same inequality by a limit. The two terms have distinct meanings. The first is the classification cost of uncertainty near the boundary. The second is the score approximation error away from that region, amplified by $1/t$. Choosing $t$ balances them; a small squared error alone does not determine classification performance without information about boundary mass.

Worked Example: Uniform Inputs and a Shifted Linear Score

Continue with $X$ uniform on $[-1,1]$ and $g(x)=x$, but use $f(x)=x+0.2$. The score is positive when $x\geq-0.2$, while the Bayes score is negative for $x<0$. They disagree on $[-0.2,0)$, up to endpoints of probability zero.

The exact excess classification risk is $$ \frac12\int_{-0.2}^{0}|x|\,dx =\frac12\left(\frac{0.2^2}{2}\right)=0.01. $$ The squared score approximation error is $E[(f(X)-g(X))^2]=0.2^2=0.04$. For $0<t\leq1$, uniformity gives $m(t)=P(|X|\leq t)=t$. Taking $t=0.2$ in the theorem yields the valid bound $$ 0.2(0.2)+\frac{0.04}{0.2}=0.04+0.2=0.24. $$ This bound is not sharp for this particular score, but it correctly separates boundary mass from score error. It guarantees an upper bound without needing to locate every disagreement.

Why Boundary Geometry Can Require Large Norm

Boundary mass describes how much probability lies near a weak decision. Geometry describes how rapidly a score must change in space to produce the desired sign pattern. These are different issues: a narrow region can contain little probability, yet still require a steep score if the classifier must assign robustly opposite signs on nearby inputs.

Here is a general norm lower bound. Let $\Phi(x)=K(x,\cdot)$ be the RKHS feature map, and suppose that for the two locations of interest, $\|\Phi(x_+)-\Phi(x_-)\|_{\mathcal H}\leq L\|x_+-x_-\|$. If a score $h$ satisfies $h(x_-)\leq-a$ and $h(x_+)\geq a$ for some $a>0$, then

2a \leq h(x_+)-h(x_-) =\langle h,\Phi(x_+)-\Phi(x_-)\rangle_{\mathcal H} \leq \|h\|_{\mathcal H}L\|x_+-x_-\|.

The last inequality is Cauchy–Schwarz. Consequently,

\|h\|_{\mathcal H}\geq \frac{2a}{L\|x_+-x_-\|}.

As the separation shrinks while the required score magnitudes remain fixed, the required norm grows. The bound requires the stated feature-map regularity for the pair of locations; it is not a universal norm-rate claim for every kernel.

Worked Example: Nearby Opposite Signs Under a Gaussian Kernel

Consider the Gaussian kernel $K(x,x')=\exp(-(x-x')^2/(2\sigma^2))$ on the real line, with $\sigma>0$. At $x_-=-a$ and $x_+=a$, where $a>0$, require interpolated scores $h(x_-)=-1$ and $h(x_+)=1$. The Gram matrix and target vector are $$ G=\begin{pmatrix}1&\rho\\\rho&1\end{pmatrix}, \qquad y=\begin{pmatrix}-1\\1\end{pmatrix}, \qquad \rho=\exp(-2a^2/\sigma^2). $$ $$ $$

The two kernel sections are linearly independent because $0<\rho<1$. The minimum-norm interpolant has squared RKHS norm $y^\mathsf{T}G^{-1}y$. Direct inversion gives $$ G^{-1}=\frac{1}{1-\rho^2} \begin{pmatrix}1&-\rho\\-\rho&1\end{pmatrix}, \qquad G^{-1}y=\frac{1}{1-\rho} \begin{pmatrix}-1\\1\end{pmatrix}. $$ Therefore $$ \|h\|_{\mathcal H}^2=y^\mathsf{T}G^{-1}y=\frac{2}{1-\rho} =\frac{2}{1-\exp(-2a^2/\sigma^2)}. $$ For $a/\sigma$ small, $1-\exp(-2a^2/\sigma^2)$ is approximately $2a^2/\sigma^2$, so the squared norm is approximately $\sigma^2/a^2$. The divergence as $a$ decreases quantifies the cost of forcing opposite unit scores onto increasingly nearby points.

Interpreting the Approximation Trade-Off

The squared-loss approximation profile and the boundary-mass function together give a practical conceptual guide. If $A(B)$ decreases rapidly as the allowed norm grows, the RKHS can represent the conditional mean score economically. If reducing $A(B)$ requires a very large norm, estimation and regularization may become difficult even when the desired sign pattern looks simple. Meanwhile, if much of the input distribution lies where $|g|$ is small, some sign disagreements can have limited risk cost. Conversely, errors in regions with large $|g|$ are costly.

A common mistake is to equate small score error with small classification error without specifying where the error occurs or how much probability lies near the boundary. The bound shows why that reasoning is incomplete: a score error must be compared with boundary mass, through a choice of $t$. Another mistake is to claim that a geometrically complicated boundary always requires a large RKHS norm. That conclusion needs assumptions about the kernel, the required score magnitudes, and the spatial separation over which the score changes. The Gaussian example verifies such growth under explicit interpolation constraints; it does not establish it for every target or kernel.

The central distinction is between approximating the score and reproducing the Bayes sign pattern. Score approximation is controlled by surrogate error such as squared-loss excess. Its translation into classification performance depends on how the conditional mean behaves near zero and where the input distribution places its mass. RKHS norm controls which approximations are available, while boundary geometry can make some sign patterns expensive to realize.

Check Your Understanding

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

Why is the conditional mean score $g(x)=E[Y\mid X=x]$ the target that minimizes conditional squared loss?
In the boundary-mass inequality, what do the two terms represent, and why is $t$ a free threshold?
If a score has uniformly small error relative to $g$, which inputs can still have their signs changed, and how does their probability matter?
Under what feature-map condition does forcing scores of at least $a$ and at most $-a$ at two locations imply a norm lower bound?
In the Gaussian-kernel example, what happens to the minimum interpolation norm as the two oppositely scored points approach each other, with $\sigma$ fixed?