Bayes Consistency with Universal Kernels

Why Universality Can Give Bayes Consistency

A kernel classifier restricts its scores to a reproducing kernel Hilbert space (RKHS). That restriction can seem problematic: the Bayes decision rule may have a discontinuous boundary, while an RKHS associated with a continuous kernel contains continuous functions. The key point is that classification risk depends on how a score behaves under the feature distribution, not on whether it matches the Bayes rule at every point. On a compact domain, density of a universal RKHS in the continuous functions lets us approximate a measurable Bayes score in the distribution’s \(L^1\) norm. For hinge loss, that is enough to make the approximation error vanish.

This approximation property is only one part of a consistency argument. A fitted classifier must also estimate its risk from a finite sample, and regularization must not prevent it from approaching good approximating scores. We will make both requirements explicit.

Consider a binary outcome \(Y\in\{-1,+1\}\), a feature \(X\in\mathcal X\), and the regression function \(\eta(x)=P(Y=+1\mid X=x)\). For a measurable score \(f\), predict \(+1\) when \(f(x)\geq 0\), and predict \(-1\) when \(f(x)<0\). The classification risk is \(R_{01}(f)=P(Y\ne h_f(X))\), where \(h_f\) is this thresholded prediction. Its minimum over measurable classifiers is the Bayes risk \(R^*=E[\min\{\eta(X),1-\eta(X)\}]\).

We use the hinge loss \(\phi(t)=\max\{0,1-t\}\) and write \(R_\phi(f)=E[\phi(Yf(X))]\). The hinge loss is a convex surrogate: it penalizes scores that are on the wrong side of zero and also scores that are correctly signed but too close to zero.

Conditional Hinge Risk and Classification Risk

At a feature value \(x\), the conditional hinge risk of score \(t\) is \(H_{\eta(x)}(t)=\eta(x)\phi(t)+(1-\eta(x))\phi(-t)\). The smallest possible value is \(2\min\{\eta(x),1-\eta(x)\}\). Indeed, if \(\eta(x)\geq 1/2\), choosing \(t=1\) gives \(2(1-\eta(x))\); if \(\eta(x)<1/2\), choosing \(t=-1\) gives \(2\eta(x)\). The conditional risk is piecewise linear, and these values are its minima. Consequently the minimum measurable hinge risk is \(R_\phi^*=2R^*\).

Proof. It is enough to compare the conditional excess risks at each \(x\). Write \(\eta=\eta(x)\) and \(t=f(x)\). If \(\eta\geq 1/2\), the Bayes prediction is \(+1\). A wrong prediction occurs exactly when \(t<0\), and its conditional classification excess is \(2\eta-1\). For \(-1<t<0\), \(H_\eta(t)=1+(1-2\eta)t\geq 1\), since \(1-2\eta\leq 0\) and \(t<0\). For \(t\leq-1\), \(H_\eta(t)=\eta(1-t)\geq2\eta\geq1\). Thus when the prediction is wrong, its conditional hinge excess over \(2(1-\eta)\) is at least \(1-2(1-\eta)=2\eta-1\). If \(t\geq0\), the prediction is correct, so its classification excess is zero; its hinge excess is nonnegative because \(2(1-\eta)\) is the minimum conditional hinge risk.

If \(\eta<1/2\), the Bayes prediction is \(-1\). A wrong prediction occurs when \(t\geq0\), including \(t=0\). For \(0\leq t<1\), \(H_\eta(t)=1+(1-2\eta)t\geq1\); for \(t\geq1\), \(H_\eta(t)=(1-\eta)(1+t)\geq2(1-\eta)\geq1\). The hinge excess is therefore at least \(1-2\eta\), the classification excess. When \(t<0\), the prediction is correct, and hinge excess is nonnegative. At \(\eta=1/2\), classification excess is zero for either prediction and hinge excess remains nonnegative. Integrating these pointwise inequalities over \(X\) proves the result. \(\square\)

Universality Removes Approximation Error

The Bayes score need not be continuous. Define the measurable score \(g(x)=+1\) when \(\eta(x)\geq1/2\), and \(g(x)=-1\) otherwise. Its conditional hinge risk is \(2\min\{\eta(x),1-\eta(x)\}\), so \(R_\phi(g)=2R^*\). The following approximation argument explains why universality still suffices.

Proof. Continuous functions are dense in \(L^1(P_X)\) for a finite Borel measure on a compact metric space. To see why, first approximate a bounded measurable function by a simple function. For each measurable set \(A\) appearing in that simple function, regularity gives a compact \(K\subset A\) and an open \(U\supset A\) such that \(P_X(U\setminus K)\) is arbitrarily small. There is a continuous function between zero and one that equals one on \(K\) and zero outside \(U\); for example, when \(K\) and \(\mathcal X\setminus U\) are nonempty, use \(u(x)=d(x,\mathcal X\setminus U)/(d(x,\mathcal X\setminus U)+d(x,K))\). It differs from the indicator of \(A\) only on \(U\setminus K\). Applying this construction to the finitely many sets in the simple function gives a continuous approximation to \(g\) in \(L^1(P_X)\).

Choose \(u\in C(\mathcal X)\) with \(E|u(X)-g(X)|<\varepsilon/2\). By universality choose \(f\in\mathcal H\) with \(\sup_x|f(x)-u(x)|<\varepsilon/2\). Then \(E|f(X)-g(X)|<\varepsilon\). Finally, \(\phi\) is 1-Lipschitz, so for every \(y\in\{-1,+1\}\), \(|\phi(yf(x))-\phi(yg(x))|\leq|f(x)-g(x)|\). Taking expectations shows \(R_\phi(f)\leq R_\phi(g)+\varepsilon=2R^*+\varepsilon\). No score can have hinge risk below \(2R^*\), by the conditional minimum already established. Hence the infimum over \(\mathcal H\) equals \(2R^*\). \(\square\)

From Approximation to a Consistent Fitted Classifier

Universality is a population approximation property; it does not by itself control estimation from data. Here is a sufficient set of conditions for the regularized empirical hinge minimizer. Assume \((X_i,Y_i)_{i=1}^n\) are independent and identically distributed, \(X_i\in\mathcal X\), \(Y_i\in\{-1,+1\}\), and \(k\) is continuous, bounded, and universal. Let \(\kappa^2=\sup_x k(x,x)<\infty\). For a deterministic penalty \(\lambda_n>0\), let \(\hat f_n\) minimize $$ \frac{1}{n}\sum_{i=1}^n\phi(Y_i f(X_i))+\lambda_n\|f\|_{\mathcal H}^2 $$ over \(f\in\mathcal H\). We assume a minimizer is used; the standard finite-sample convex objective with a strictly positive norm penalty admits one.

Proof. Write \(P\phi_f=E[\phi(Yf(X))]\) and \(P_n\phi_f=n^{-1}\sum_{i=1}^n\phi(Y_i f(X_i))\). Since the objective at \(f=0\) is \(1\), optimality and nonnegativity of hinge loss imply \(\lambda_n\|\hat f_n\|_{\mathcal H}^2\leq1\), so \(\|\hat f_n\|_{\mathcal H}\leq\lambda_n^{-1/2}\).

For \(R>0\), the reproducing property gives \(|f(x)|\leq\|f\|_{\mathcal H}\sqrt{k(x,x)}\leq\kappa R\) whenever \(\|f\|_{\mathcal H}\leq R\). The hinge loss is 1-Lipschitz in its score. Symmetrization and the contraction inequality for Rademacher averages therefore give, for a numerical constant \(C\), \(E[\sup_{\|f\|_{\mathcal H}\leq R}|P_n\phi_f-P\phi_f|]\leq C\kappa R/\sqrt n\). This bound applies because the loss class is measurable and bounded on each such ball by \(1+\kappa R\). With \(R=\lambda_n^{-1/2}\), the expected uniform deviation is at most \(C\kappa/\sqrt{n\lambda_n}\), which tends to zero. Markov's inequality then implies that \(D_n=\sup_{\|f\|_{\mathcal H}\leq\lambda_n^{-1/2}}|P_n\phi_f-P\phi_f|\xrightarrow{p}0\).

For any fixed \(f\in\mathcal H\), optimality of \(\hat f_n\), followed by the deviation bound on the ball containing \(\hat f_n\), gives $$ P\phi_{\hat f_n} \leq P_n\phi_{\hat f_n}+D_n \leq P_n\phi_f+\lambda_n\|f\|_{\mathcal H}^2+D_n \leq P\phi_f+\lambda_n\|f\|_{\mathcal H}^2+2D_n. $$ Because \(\lambda_n\to0\) and \(D_n\xrightarrow{p}0\), this inequality holds asymptotically with an arbitrarily small excess over the risk of any fixed \(f\in\mathcal H\). The universal-kernel approximation theorem gives \(\inf_{f\in\mathcal H}P\phi_f=2R^*\). More explicitly, for any \(\varepsilon>0\), choose a fixed \(f_\varepsilon\in\mathcal H\) with \(P\phi_{f_\varepsilon}<2R^*+\varepsilon\); its norm is fixed, so \(\lambda_n\|f_\varepsilon\|^2\to0\). The displayed inequality yields \(P\phi_{\hat f_n}-2R^*\xrightarrow{p}0\), since this difference is nonnegative and its upper bound can be made arbitrarily small in probability. The conditional-risk inequality then gives \(0\leq R_{01}(\hat f_n)-R^*\leq P\phi_{\hat f_n}-2R^*\xrightarrow{p}0\). \(\square\)

What the Conditions Do—and Do Not—Say

The theorem is a sufficient consistency result for a fixed universal kernel and a specific regularized empirical objective. It does not say universality makes every fitted classifier consistent regardless of the penalty, nor that every finite sample can represent the Bayes boundary exactly. The proof balances three quantities: approximation by a fixed RKHS score, the penalty paid for that score, and the empirical-to-population deviation over the norm ball containing the fitted score.

A common mistake is to infer consistency from density alone: “the RKHS approximates continuous functions, so the fitted classifier must approach Bayes risk.” The missing step is estimation. The norms of scores needed for increasingly accurate approximation may grow, and empirical risk is harder to control over larger norm balls. In this argument, \(n\lambda_n\to\infty\) makes the deviation vanish for the ball of radius \(\lambda_n^{-1/2}\), while \(\lambda_n\to0\) ensures each fixed approximating score eventually pays negligible penalty. A separate later analysis may seek sharper or different schedules, but neither condition can be omitted from this proof.