Sufficient Conditions for Kernel Classifier Consistency

From Regularized Scores to Classification Consistency

A regularized kernel classifier balances two demands. Its score should approximate a good classification rule, but its RKHS norm must not grow so quickly that the data cannot estimate its performance. Consistency follows when approximation improves, estimation error vanishes over the relevant norm range, and the penalty still controls that range. This tutorial makes that balance precise for the hinge loss.

Let \((X,Y)\) have a fixed distribution, with \(Y\in\{-1,+1\}\), and let \((X_i,Y_i)_{i=1}^n\) be independent observations from that distribution. Let \(\mathcal H\) be a separable RKHS with measurable kernel \(K\), satisfying \(K(x,x)\leq \kappa^2\) for all \(x\), where \(0<\kappa<\infty\). For a score \(f\in\mathcal H\), define its hinge loss by \(\phi(Yf(X))=(1-Yf(X))_+\), where \(u_+=\max(u,0)\). 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))\).

The regularized empirical hinge classifier is any minimizer

where \(\lambda_n>0\). We assume a measurable minimizer is selected. The squared norm penalty both favors smaller scores and supplies a deterministic bound on the norm of the selected fit.

Hinge Risk Controls Classification Risk

The first step is a pointwise comparison. Let \(\eta(x)=P(Y=+1\mid X=x)\), using any measurable version of this conditional probability. Given \(X=x\), the conditional hinge risk of a score value \(t\) is

Its infimum over real \(t\) is \(2\min(\eta,1-\eta)\): if \(\eta\geq 1/2\), a value \(t\geq1\) attains \(2(1-\eta)\); if \(\eta\leq1/2\), a value \(t\leq-1\) attains \(2\eta\). Integrating this conditional infimum gives \(2R^*\).

Proof. Fix \(x\) and put \(\eta=\eta(x)\). If \(\eta>1/2\), the Bayes label is \(+1\). A classification error occurs only when \(t<0\), and the conditional classification regret is \(2\eta-1\). For \(-1\leq t<0\), \(C_\eta(t)=1+(1-2\eta)t\geq1\), so \(C_\eta(t)-2(1-\eta)\geq2\eta-1\). For \(t<-1\), \(C_\eta(t)=\eta(1-t)\geq2\eta\), which gives at least the same bound. If \(\eta<1/2\), the Bayes label is \(-1\), and an error occurs when \(t\geq0\), including the specified tie at zero. For \(0\leq t\leq1\), \(C_\eta(t)=1+(1-2\eta)t\geq1\), so \(C_\eta(t)-2\eta\geq1-2\eta\). For \(t>1\), \(C_\eta(t)=(1-\eta)(1+t)\geq2(1-\eta)\), again giving at least \(1-2\eta\). At \(\eta=1/2\), the classification regret is zero. Thus, in every case, conditional classification regret is at most conditional hinge risk minus its infimum. Taking expectations proves the inequality. \(\square\)

A Sufficient-Condition Consistency Theorem

Approximation is measured against the best possible hinge risk, \(2R^*\). Let \(r_n>0\) be a sequence of comparator norm bounds, and choose \(g_n\in\mathcal H\) with \(\lVert g_n\rVert_{\mathcal H}\leq r_n\). Define its approximation error by \(A_n=P\phi_{g_n}-2R^*\), which is nonnegative by the conditional hinge-risk calculation above. For \(R>0\), define the uniform estimation error on the RKHS ball of radius \(R\) as

Proof. Since the zero function has empirical hinge risk \(P_n\phi_0=1\), optimality gives

The hinge risk is nonnegative, so \(\lVert\hat f_n\rVert_{\mathcal H}\leq\lambda_n^{-1/2}\). The assumed comparator bound places \(g_n\) in the same ball. Apply the definition of \(\Delta_n\), then compare the empirical objectives of \(\hat f_n\) and \(g_n\):

Subtract \(2R^*\) and apply the lemma to \(\hat f_n\). This proves the displayed finite-sample inequality.

To verify the convergence claim, the RKHS evaluation inequality gives \(|f(x)|\leq\kappa\lVert f\rVert_{\mathcal H}\). The hinge loss is 1-Lipschitz, and \(\phi(0)=1\). Symmetrization and the Rademacher contraction inequality therefore give

Here the bound follows by centering the loss at \(\phi(0)\), applying contraction to the centered 1-Lipschitz loss, and using \(E\sup_{\lVert f\rVert\leq R}|n^{-1}\sum_{i=1}^n\epsilon_iY_i f(X_i)|\leq\kappa R/\sqrt n\), where the \(\epsilon_i\) are independent random signs. At \(R=\lambda_n^{-1/2}\), the expectation is at most \(4\kappa/\sqrt{n\lambda_n}\), which tends to zero. Markov's inequality implies \(\Delta_n(\lambda_n^{-1/2})\xrightarrow{p}0\). The finite-sample inequality and the other two assumptions now imply \(R(\hat f_n)-R^*\xrightarrow{p}0\). \(\square\)

Checking the Conditions in Practice

The theorem separates three requirements rather than hiding them in a single statement of consistency. The approximation error asks whether some sequence of RKHS scores approaches the Bayes hinge risk. The penalty term \(\lambda_n r_n^2\) asks whether the norms needed for that approximation remain affordable. Finally, \(n\lambda_n\to\infty\) ensures that the estimation error on the ball forced by the penalty vanishes. These are sufficient conditions; failing one does not by itself prove inconsistency.

Common Pitfall

A common mistake is to argue that \(\lambda_n\to0\) makes the penalty harmless, so increasingly complex scores can be used without a further condition. The penalty has two roles. It must not overwhelm the improving comparator, which is why \(\lambda_n r_n^2\to0\); but it must also restrict the fitted norm enough for estimation, which here requires \(n\lambda_n\to\infty\). These conditions can hold together, as in the first example, but neither follows merely from \(\lambda_n\to0\).