A Linear-Kernel Classification Bound Worked from First Principles

From a Linear Norm Constraint to a Risk Guarantee

A classification guarantee for a kernel method can be made concrete by considering the linear kernel first. In this setting, the reproducing-kernel Hilbert space (RKHS) consists of linear score functions, and its norm constraint directly limits how much the score can change over the covariate space. If covariates are bounded, that constraint controls the estimation error of hinge risk. Hinge calibration then translates the risk bound into a bound on classification error.

The result has two distinct sources of error. The estimation term decreases with sample size and depends on the allowed score norm and covariate bound. The approximation term records whether the norm-constrained class can achieve hinge risk close to the best possible hinge risk. Keeping these terms separate is useful: a small estimation error alone does not guarantee a good classifier if the constrained class is too restrictive.

Setup and Definitions

Let \((X_i,Y_i)_{i=1}^n\) be independent and identically distributed observations, where \(X_i\in\mathbb{R}^d\) and \(Y_i\in\{-1,+1\}\). Assume \(X\) is measurable and \(\|X\|_2\leq\kappa\) almost surely, for a finite constant \(\kappa\). For the linear kernel \(k(x,x')=x^\mathsf{T}x'\), a score function has the form \(f_w(x)=w^\mathsf{T}x\); its RKHS norm is \(\|w\|_2\). We use the norm-constrained class \(\mathcal{F}_{\Lambda}=\{f_w:\|w\|_2\leq\Lambda\}\), where \(\Lambda\geq0\). There is no separate unpenalized intercept in this definition; an intercept can be included by augmenting the covariate vector.

Since \(|f_w(X)|\leq\|w\|_2\|X\|_2\leq\Lambda\kappa\), every loss in the class lies between zero and \(B=1+\Lambda\kappa\). This boundedness will be used for concentration; the norm constraint will control the size of the class.

A Uniform Hinge-Risk Bound

The next result gives a finite-sample deviation bound. Its probability statement requires no assumption that the data distribution has a density. In finite dimension, the parameter ball is compact and the hinge loss is continuous in \(w\); with measurable covariates, the suprema below are measurable.

Proof. Subtract the constant value \(\ell(y,0)=1\) and write \(g_f(x,y)=\ell(y,f(x))-1\). This centering does not change the difference between population and empirical risks. For any fixed sample, the Rademacher average of this centered class is

where the \(\varepsilon_i\) are independent random signs, each equally likely to be \(+1\) or \(-1\). The first inequality is the Rademacher contraction inequality: \(t\mapsto\ell(y,t)-1\) is 1-Lipschitz and equals zero at \(t=0\). The inequality applies because multiplying the score by \(y\in\{-1,+1\}\) preserves its Lipschitz constant. For the second inequality, the supremum of the linear form over the radius-\(\Lambda\) ball is \(\Lambda\|\sum_i\varepsilon_iY_iX_i\|_2/n\). Jensen's inequality and independence of the signs give

For either one-sided deviation, symmetrization bounds the expected supremum by twice this Rademacher average, hence by \(2\Lambda\kappa/\sqrt n\). The same bound holds for the other one-sided deviation. Changing one observation changes either supremum by at most \(B/n\), because the loss lies in \([0,B]\). McDiarmid's inequality therefore bounds the probability that either supremum exceeds its expectation by \(B\sqrt{\log(2/\delta)/(2n)}\) by at most \(\delta/2\). A union bound for the two one-sided deviations proves the stated absolute-deviation bound. \(\square\)

Empirical Minimization and the Constrained Oracle

Let \(\widehat f\in\mathcal{F}_{\Lambda}\) be an empirical hinge-risk minimizer. More generally, suppose it is an approximate minimizer satisfying \(\widehat R_{\mathrm h}(\widehat f)\leq\inf_{f\in\mathcal{F}_{\Lambda}}\widehat R_{\mathrm h}(f)+\varepsilon\), where \(\varepsilon\geq0\) is the optimization tolerance. Define the best constrained risk gap by \(A_{\Lambda}=\inf_{f\in\mathcal{F}_{\Lambda}}R_{\mathrm h}(f)-R_{\mathrm h}^*\), where \(R_{\mathrm h}^*=\inf_f R_{\mathrm h}(f)\) is the smallest hinge risk over measurable real-valued score functions.

Derivation. For any \(f\in\mathcal{F}_{\Lambda}\), the uniform deviation event and the approximate-minimization property imply

Taking the infimum over \(f\in\mathcal{F}_{\Lambda}\) and subtracting \(R_{\mathrm h}^*\) gives the result. This argument does not require an optimizer of the population risk to exist. \(\square\)

Why Hinge Regret Controls Classification Risk

A hinge-risk bound is useful for classification because hinge loss is calibrated to zero-one loss. The key point is a pointwise statement about the conditional risks; it does not require a margin or low-noise assumption.

where \(R_{01}^*=\inf_g R_{01}(g)\) is the Bayes classification risk.

Proof. Let \(\eta(x)=P(Y=+1\mid X=x)\). At a fixed \(x\), the conditional hinge risk of score \(t\) is \(C_{\eta}(t)=\eta(1-t)_+ +(1-\eta)(1+t)_+\). For \(-1\leq t\leq1\), this equals \(1+(1-2\eta)t\). For \(t\geq1\), it equals \((1-\eta)(1+t)\); for \(t\leq-1\), it equals \(\eta(1-t)\). Consequently,

For \(1/2\leq\eta<1\), the minimum is attained at \(t=1\); when \(\eta=1\), it is attained at every \(t\geq1\). For \(0<\eta<1/2\), the minimum is attained at \(t=-1\); when \(\eta=0\), it is attained at every \(t\leq-1\). At \(\eta=1/2\), every \(t\in[-1,1]\) minimizes the conditional risk.

If \(\eta>1/2\), the Bayes decision is \(+1\), and a wrong decision under our threshold convention requires \(t<0\). On \([-1,0]\), \(C_{\eta}(t)\geq C_{\eta}(0)=1\), while for \(t\leq-1\), \(C_{\eta}(t)=\eta(1-t)\geq2\eta\). In either region, the hinge-risk excess is at least \(2\eta-1\), the conditional zero-one excess. If \(\eta<1/2\), the Bayes decision is \(-1\), and a wrong decision requires \(t\geq0\). For \(0\leq t\leq1\), \(C_{\eta}(t)\geq1\); for \(t\geq1\), \(C_{\eta}(t)\geq2(1-\eta)\). The hinge-risk excess is therefore at least \(1-2\eta\), again the conditional zero-one excess. When \(\eta=1/2\), the conditional zero-one excess is zero. Integrating these inequalities over \(X\) proves the result. \(\square\)

The Classification Guarantee and a Common Pitfall

Combining the empirical-minimization result with hinge calibration gives the promised classification guarantee. With probability at least \(1-\delta\),

The norm and covariate bound enter through the estimation terms, while \(A_{\Lambda}\) captures the limitations of the constrained linear class. Increasing \(\Lambda\) can reduce approximation error, but it also increases the estimation bound. Choosing the norm constraint is therefore a balance, not a reason to make the allowed norm as large as possible.

Common pitfall: confusing the minimum value with all its minimizers. For example, when \(\eta=0.75\), the conditional minimum is \(0.5\), but the score \(t=2\) has risk \(0.25(1+2)=0.75\), not \(0.5\). The minimum is attained at \(t=1\) for \(1/2\leq\eta<1\); only when \(\eta=1\) are all \(t\geq1\) minimizers. Similarly, for \(0<\eta<1/2\), the minimum is attained at \(t=-1\), not at every \(t\leq-1\). The endpoint families of minimizers occur only at \(\eta=0\) and \(\eta=1\). This distinction matters when proving calibration pointwise.