Misspecification with a Fixed Classification Kernel

Why a Fixed Kernel Can Leave Persistent Error

Increasing the sample size does not necessarily remove every source of classification error. If the kernel and its RKHS are held fixed, the fitted scores remain restricted to that function space. Even with perfect optimization and arbitrarily many observations, that restriction can prevent the classifier from matching the Bayes decision rule. This is kernel approximation error, not sampling noise.

To separate these effects, we will use hinge-loss regularization as a concrete learning procedure. The main conclusion is an oracle bound: under suitable sampling and regularization conditions, the procedure approaches the best hinge risk available in the fixed RKHS. Its classification risk is then bounded by the unrestricted Bayes risk plus a fixed approximation term. The bound does not assert that every fitted sequence converges to a unique classifier.

Classification Risk and Fixed-RKHS Approximation

Let $(X,Y)$ be a random pair with $Y\in\{-1,+1\}$, and let $(X_i,Y_i)_{i=1}^n$ be independent observations with this distribution. A score $f$ predicts $+1$ when $f(X)\geq 0$, and predicts $-1$ otherwise. This convention makes a zero score a positive prediction.

Definition: The classification risk of a measurable score $f$ is $$ R(f)=P\bigl(Yf(X)<0\bigr)+P\bigl(Y=-1,\ f(X)=0\bigr). $$ The Bayes risk is $R^*=\inf_g R(g)$, where the infimum is over all measurable real-valued scores $g$. For a fixed RKHS $\mathcal H$, its classification approximation error is $$ A_{\mathcal H}=\inf_{f\in\mathcal H}R(f)-R^*. $$

The tie term in the risk definition matters: when $Y=-1$ and $f(X)=0$, the prediction is $+1$, so that observation is an error. Conversely, a positive-label observation tied at zero is correctly classified. The quantity $A_{\mathcal H}$ is nonnegative. It is strictly positive when no sequence of scores in $\mathcal H$ can approach Bayes risk; merely saying that the Bayes score is not an element of $\mathcal H$ does not, by itself, prove strict positivity.

For hinge-loss learning, define $\phi(u)=(1-u)_+$, where $a_+=\max(a,0)$, and write $$ R_\phi(f)=E\bigl[\phi(Yf(X))\bigr]. $$ Let $R_\phi^*=\inf_g R_\phi(g)$, with the infimum again over all measurable scores. The hinge approximation error is $$ \Delta_{\mathcal H}=\inf_{f\in\mathcal H}R_\phi(f)-R_\phi^*. $$ It is a surrogate-risk approximation quantity, not the same quantity as $A_{\mathcal H}$. The hinge loss is classification-calibrated: small excess hinge risk controls excess classification risk. But when the score space is restricted, the hinge-risk minimizer within that space need not be the best classifier in the space. Thus $\Delta_{\mathcal H}$ gives a useful upper bound, not generally an exact description of the limiting classification risk.

Worked Examples of Approximation Error

Worked Example: A Constant Kernel Cannot Separate Two Regions

Suppose $X$ takes values $a$ and $b$ with probability $1/2$ each, and $P(Y=+1\mid X=a)=0.9$, while $P(Y=+1\mid X=b)=0.2$. Let the fixed RKHS contain only constant scores, as happens for a suitable constant kernel.

At $a$, the Bayes classifier predicts $+1$ and has conditional error $0.1$. At $b$, it predicts $-1$ and has conditional error $0.2$. Therefore $$ R^*=\tfrac12(0.1)+\tfrac12(0.2)=0.15. $$ A positive constant score predicts $+1$ everywhere, with risk $\tfrac12(0.1)+\tfrac12(0.8)=0.45$. A negative constant score predicts $-1$ everywhere, with risk $\tfrac12(0.9)+\tfrac12(0.2)=0.55$. A zero score predicts $+1$ everywhere and also has risk $0.45$. Hence $\inf_{f\in\mathcal H}R(f)=0.45$ and $A_{\mathcal H}=0.45-0.15=0.30$. No increase in sample size can remove this restriction while the RKHS remains the constants.

The hinge risks show why the surrogate approximation term can differ. For a constant score $t$, the marginal positive-label probability is $0.5(0.9)+0.5(0.2)=0.55$. For $0\leq t\leq1$, $$ R_\phi(t)=0.55(1-t)+0.45(1+t)=1-0.10t, $$ so its minimum over this interval is $0.9$ at $t=1$; for $t\geq1$, the risk is $0.45(1+t)$, which increases from $0.9$. For $-1\leq t\leq0$, the risk is $1-0.10t$, which is at least $0.9$, and for $t\leq-1$, it is $0.55(1-t)$, also at least $1.1$. Thus the best constant hinge risk is $0.9$. Pointwise, the unrestricted hinge-risk minimum is $2\min(\eta,1-\eta)$, giving $0.2$ at $a$ and $0.4$ at $b$; consequently $R_\phi^*=0.3$ and $\Delta_{\mathcal H}=0.6$. This surrogate bound is valid but looser than the actual classification approximation error $0.30$.

Worked Example: Regularization Changes Scores Before It Changes Decisions

Let $X$ be constant, $P(Y=+1)=0.8$, and let the RKHS consist of constant scores $f_t(x)=t$ with norm $\lVert f_t\rVert_{\mathcal H}=|t|$. The population hinge risk is $$ R_\phi(f_t)=0.8(1-t)_++0.2(1+t)_+. $$ For $-1\leq t\leq1$, this equals $1-0.6t$. The regularized population objective on this interval is $1-0.6t+\lambda t^2$, whose derivative is $-0.6+2\lambda t$.

If $\lambda=0.5$, the minimizer is $t=0.6$, since the derivative vanishes there and the second derivative is $2\lambda=1>0$. Its classification risk is $0.2$, the Bayes risk. The regularization has changed the score magnitude but not its sign. If $\lambda=0.1$, the unconstrained stationary point is $t=3$, outside this interval; for $t\geq1$ the objective is $0.2(1+t)+0.1t^2$, which is increasing, so the minimizer is $t=1$. As $\lambda$ decreases, the score changes, while the classification decision remains positive. This example distinguishes score-level regularization bias from classification approximation error.

An Oracle Bound for a Fixed RKHS

Assume $\mathcal H$ is a measurable, separable RKHS with kernel $k$ satisfying $k(x,x)\leq\kappa^2$ for every $x$, where $\kappa<\infty$. For $\lambda_n>0$, define a regularized empirical hinge-risk minimizer by $$ \hat f_n\in\arg\min_{f\in\mathcal H}\left\{\frac1n\sum_{i=1}^n\phi(Y_i f(X_i))+\lambda_n\lVert f\rVert_{\mathcal H}^2\right\}. $$ Write $P_n\phi_f=n^{-1}\sum_{i=1}^n\phi(Y_i f(X_i))$, and $P\phi_f=R_\phi(f)$.

Theorem: Suppose $\lambda_n>0$, $\lambda_n\to0$, and $n\lambda_n\to\infty$. Under the bounded-kernel and measurability assumptions above, $$ R_\phi(\hat f_n)\leq \inf_{f\in\mathcal H}R_\phi(f)+o_p(1), $$ and therefore $$ R(\hat f_n)-R^*\leq \Delta_{\mathcal H}+o_p(1). $$ In particular, if $A_{\mathcal H}>0$, every $\mathcal H$-valued fitted score has classification risk at least $R^*+A_{\mathcal H}$, regardless of the sample size.

Proof. Since the objective at $f=0$ is $1$, optimality and nonnegativity of hinge loss imply $$ \lambda_n\lVert\hat f_n\rVert_{\mathcal H}^2\leq1, \qquad \lVert\hat f_n\rVert_{\mathcal H}\leq\frac1{\sqrt{\lambda_n}}. $$ The positivity condition on $\lambda_n$ is essential for this division. Set $B_n=1/\sqrt{\lambda_n}$, and let $$ D_n=\sup_{\lVert f\rVert_{\mathcal H}\leq B_n}|P_n\phi_f-P\phi_f|. $$ For any fixed $g\in\mathcal H$, optimality gives $P_n\phi_{\hat f_n}+\lambda_n\lVert\hat f_n\rVert_{\mathcal H}^2\leq P_n\phi_g+\lambda_n\lVert g\rVert_{\mathcal H}^2$. Dropping the nonnegative penalty on the left and applying the definition of $D_n$ to $\hat f_n$ yields $$ R_\phi(\hat f_n)\leq P_n\phi_g+\lambda_n\lVert g\rVert_{\mathcal H}^2+D_n \leq R_\phi(g)+\lambda_n\lVert g\rVert_{\mathcal H}^2+2D_n. $$ The second use of $D_n$ is valid because $g$ need not belong to the ball: if $g$ lies outside it, first compare with any fixed $g$ inside the ball. More generally, for the oracle conclusion, it suffices to fix an arbitrary candidate $g$ and use the deviation bound on a ball containing both $g$ and $\hat f_n$; for each fixed $g$, $B_n$ eventually exceeds $\lVert g\rVert_{\mathcal H}$, since $\lambda_n\to0$. Thus the displayed inequality applies for all sufficiently large $n$ for that candidate.

For completeness, symmetrization and the contraction inequality for the one-Lipschitz hinge loss give $E[D_n]\leq4\kappa B_n/\sqrt n=4\kappa/\sqrt{n\lambda_n}$. Hence $D_n=o_p(1)$ by Markov's inequality and $n\lambda_n\to\infty$. For any $\epsilon>0$, choose a fixed $g_\epsilon\in\mathcal H$ with $R_\phi(g_\epsilon)\leq\inf_{f\in\mathcal H}R_\phi(f)+\epsilon$. Its norm is fixed, so $\lambda_n\lVert g_\epsilon\rVert_{\mathcal H}^2\to0$. The comparison inequality gives the first assertion by letting $\epsilon$ be arbitrarily small.

To obtain the classification assertion, condition on $X=x$ and set $\eta=P(Y=+1\mid X=x)$. The conditional hinge risk at score $t$ is $C_\eta(t)=\eta(1-t)_++(1-\eta)(1+t)_+$, whose infimum over $t\in\mathbb R$ is $2\min(\eta,1-\eta)$. The conditional classification excess is $|2\eta-1|$ if the score predicts the less probable label, and zero otherwise. Directly from the piecewise-linear formula for $C_\eta$, this excess is at most $C_\eta(t)-2\min(\eta,1-\eta)$; the same inequality holds at $t=0$ under the stated tie convention. Integrating over $X$ gives $R(f)-R^*\leq R_\phi(f)-R_\phi^*$. Apply this inequality to $\hat f_n$, then use the first assertion and $R_\phi^*\leq R_\phi(f)$ for every measurable $f$, to obtain $$ R(\hat f_n)-R^*\leq \inf_{f\in\mathcal H}R_\phi(f)-R_\phi^*+o_p(1) =\Delta_{\mathcal H}+o_p(1). $$ Finally, the definition of $A_{\mathcal H}$ gives $R(\hat f_n)\geq R^*+A_{\mathcal H}$ for each $n$. $\square$

Reading the Error Terms

The theorem separates two errors that the choice of a decreasing regularization sequence cannot eliminate in the same way. The uniform deviation $D_n$ is a sampling term; its bound vanishes when $n\lambda_n\to\infty$. The penalty on any fixed comparison function $g$ is $\lambda_n\lVert g\rVert_{\mathcal H}^2$, which vanishes when $\lambda_n\to0$. What remains in the stated classification guarantee is $\Delta_{\mathcal H}$, determined by the fixed RKHS and the distribution. A positive $A_{\mathcal H}$ gives an unavoidable classification-risk floor, even if sampling and penalty errors vanish.

Worked Example: Tracking Sampling and Penalty Terms

Suppose the kernel is bounded with $\kappa=1$, and choose $\lambda_n=n^{-1/2}$. Then $\lambda_n\to0$ and $n\lambda_n=n^{1/2}\to\infty$, so both conditions in the theorem hold. The expected deviation bound becomes $$ E[D_n]\leq\frac{4}{\sqrt{n\lambda_n}}=4n^{-1/4}. $$ For $n=10{,}000$, $\lambda_n=0.01$, and this bound is $4(10{,}000)^{-1/4}=0.4$. If a fixed comparison score has RKHS norm $2$, its penalty term is $\lambda_n\lVert g\rVert_{\mathcal H}^2=0.01(4)=0.04$. The comparison inequality includes two deviation terms, so these numerical upper bounds contribute $2(0.4)+0.04=0.84$ beyond that score's hinge risk. The bound is conservative, but its terms have distinct roles: increasing $n$ shrinks the deviation bound, decreasing $\lambda_n$ shrinks the fixed-score penalty, and neither operation changes the fixed-kernel approximation term.

Common Pitfall

Incorrect: “The estimator is consistent because the sample size grows and the regularization parameter shrinks.” This ignores the class in which the estimator is constrained. A fixed RKHS may not approximate the Bayes decision rule, and a nonzero approximation floor remains.
Correction: State which error is being controlled. The conditions $n\lambda_n\to\infty$ and $\lambda_n\to0$ control sampling deviation and the penalty on fixed comparison functions. They do not make a fixed RKHS richer. Also, the bound involving $1/\sqrt{\lambda_n}$ requires $\lambda_n>0$; it cannot be stated or derived when the regularization parameter is zero.

A second useful caution is that the oracle inequality is an upper bound, not an exact limit formula. It does not prove convergence of the scores, uniqueness of a population minimizer, or equality between the limiting risk and $R^*+\Delta_{\mathcal H}$. The actual limiting classification risk can depend on the distribution, the geometry of the RKHS, and how scores behave near zero.

Key takeaway: With a fixed classification kernel, vanishing sampling and regularization errors leave the RKHS approximation error untouched. Report the attainable class risk and the surrogate approximation term separately; do not call a fixed-kernel risk floor a finite-sample effect.

Check Your Understanding

Answer each question by identifying the relevant risk or error term.

Under the convention that a zero score predicts $+1$, which tied observations contribute to classification risk?
Why does $\lambda_n>0$ matter for the norm bound on the empirical minimizer?
In the two-region example, calculate the classification approximation error for the constant-score RKHS.
What conditions on $\lambda_n$ control the sampling deviation and the penalty on a fixed comparison score?
Why does a small hinge approximation error provide a risk guarantee without proving that the fitted scores converge to a unique limit?