Approximation, Estimation, and Penalty Error in Kernel Classification

Why Separate the Errors?

A regularized kernel classifier is selected using observed data, but its performance is measured by risk under the data-generating distribution. Comparing its population risk with an ideal benchmark requires accounting for three different costs: how well a chosen RKHS score can perform, how empirical risk differs from population risk, and the cost of controlling the score through a norm penalty. Keeping these terms distinct clarifies what a fixed regularization level does—and what a comparison bound alone does not establish.

We use binary labels $Y\in\{-1,+1\}$, an input $X$, a reproducing kernel Hilbert space $\mathcal H$, and a margin loss $\phi$. The score $f\in\mathcal H$ predicts using the sign of $f(X)$; its surrogate loss is $\phi(Yf(X))$. The statements below concern surrogate risk, not directly the zero-one classification risk.

Risks and the Regularized Empirical Score

Definition: For a measurable score $f$, define its population surrogate risk by $R(f)=E[\phi(Yf(X))]$, whenever this expectation is finite. Given an observed sample $(X_i,Y_i)_{i=1}^n$, define $P_n\phi_f=n^{-1}\sum_{i=1}^n\phi(Y_i f(X_i))$. Write $R_*=\inf_{f\in\mathcal G}R(f)$, where $\mathcal G$ is the specified class of measurable benchmark scores. For a fixed $\lambda>0$, an exact regularized empirical minimizer is any $\hat f_\lambda\in\mathcal H$ satisfying $$ P_n\phi_{\hat f_\lambda}+\lambda\|\hat f_\lambda\|_{\mathcal H}^2 = \inf_{f\in\mathcal H}\left\{P_n\phi_f+\lambda\|f\|_{\mathcal H}^2\right\}. $$

Assume the risks used below are finite and that the empirical objective attains its minimum. The comparison argument is algebraic: it does not require a particular kernel, a particular margin loss, or a uniform deviation theorem. A bounded kernel and suitable loss conditions are often useful for establishing stronger statistical bounds, but are not needed for this decomposition.

Fix any comparator $g_\lambda\in\mathcal H$ with finite risk. The subscript reminds us that the comparator may be chosen with the fixed regularization level in mind; the basic inequality holds for any such choice. Its approximation error is its excess population surrogate risk over the benchmark. Its penalty cost is its squared RKHS norm multiplied by $\lambda$.

Definition: For a fixed comparator $g_\lambda$, its comparator approximation error is $A_\lambda=R(g_\lambda)-R_*$, and its RKHS penalty cost is $P_\lambda=\lambda\|g_\lambda\|_{\mathcal H}^2$. Define the nonnegative sample error $$ S_{n,\lambda} = \left|R(\hat f_\lambda)-P_n\phi_{\hat f_\lambda}\right| + \left|P_n\phi_{g_\lambda}-R(g_\lambda)\right|. $$

The comparator approximation error depends on the benchmark class and the chosen score, not on sample fluctuation. The sample error measures the two empirical-to-population discrepancies needed to compare the fitted score with that comparator. In particular, it is evaluated at the fitted score and comparator; it is not, by itself, a uniform bound over all scores in the RKHS.

The Fixed-Comparator Decomposition

Theorem: Under the definitions above, for every fixed $g_\lambda\in\mathcal H$ with finite risk, $$ R(\hat f_\lambda)-R_* \leq A_\lambda+S_{n,\lambda}+P_\lambda. $$ More precisely, before replacing signed deviations by absolute values, $$ R(\hat f_\lambda)-R_* \leq A_\lambda+ \bigl[R(\hat f_\lambda)-P_n\phi_{\hat f_\lambda}\bigr] +\bigl[P_n\phi_{g_\lambda}-R(g_\lambda)\bigr] +\lambda\left(\|g_\lambda\|_{\mathcal H}^2-\|\hat f_\lambda\|_{\mathcal H}^2\right). $$

Proof. Add and subtract the two empirical risks and the comparator’s population risk. This gives the exact identity $$ R(\hat f_\lambda)-R_* = A_\lambda+ \bigl[R(\hat f_\lambda)-P_n\phi_{\hat f_\lambda}\bigr] +\bigl[P_n\phi_{\hat f_\lambda}-P_n\phi_{g_\lambda}\bigr] +\bigl[P_n\phi_{g_\lambda}-R(g_\lambda)\bigr]. $$ By empirical optimality, $$ P_n\phi_{\hat f_\lambda}+\lambda\|\hat f_\lambda\|_{\mathcal H}^2 \leq P_n\phi_{g_\lambda}+\lambda\|g_\lambda\|_{\mathcal H}^2. $$ Rearranging bounds the middle empirical-risk difference by $$ P_n\phi_{\hat f_\lambda}-P_n\phi_{g_\lambda} \leq \lambda\left(\|g_\lambda\|_{\mathcal H}^2-\|\hat f_\lambda\|_{\mathcal H}^2\right). $$ Substituting this into the identity proves the more precise inequality. Since $\|\hat f_\lambda\|_{\mathcal H}^2\geq0$, the penalty difference is at most $\lambda\|g_\lambda\|_{\mathcal H}^2$. Each signed deviation is at most its absolute value, so the stated bound follows. $\square$

This proof shows where each term enters. The comparator sets the approximation and penalty costs; empirical optimality controls the empirical-risk difference; and the two deviations transfer the comparison back to population risk. The sharper inequality retains the negative fitted-score penalty. Dropping it gives a simpler, possibly looser, upper bound.

Worked Comparisons with Hinge Loss

For the examples, use the hinge loss $\phi(u)=(1-u)_+$, where $a_+=\max(a,0)$, and the one-dimensional RKHS of constant scores $f_t(x)=t$, with $\|f_t\|_{\mathcal H}^2=t^2$. This is a valid simple kernel model: the kernel is $K(x,x')=1$. Take $\mathcal G$ to include all measurable scores, so the benchmark risk can be calculated directly in each example.

Worked Example: All Labels Positive and the Penalty Cost

Suppose $Y=+1$ with probability one, the observed sample contains only positive labels, and $\lambda=1$. Every score is constant. The empirical objective is $$ (1-t)_+ + t^2. $$

For $t\leq1$, the objective is $1-t+t^2$, whose derivative is $-1+2t$. Its minimum on this region is at $t=1/2$, with value $1-1/2+1/4=3/4$. For $t>1$, the objective is $t^2$, which is at least $1$. Thus $\hat f_\lambda=f_{1/2}$.

In particular, for $t<-1$ the hinge loss is $1-t$, so the objective remains $1-t+t^2$, not $1+t+t^2$. Its derivative $-1+2t$ is negative for $t<-1$; the objective decreases as $t$ increases toward $-1$, where its value is $3$. This region cannot contain a better minimizer.

The population risk is also $(1-t)_+$, so $R_*=0$, achieved at $t=1$. Choose $g_\lambda=f_1$. Then $A_\lambda=0$, $S_{n,\lambda}=0$ because the sample and population risks agree, and $P_\lambda=1$. The actual excess risk is $R(f_{1/2})-R_*=1/2$, which is at most the bound $1$. The penalty bound is valid but not tight.

Worked Example: A Balanced Sample from an Imbalanced Population

Let the input be constant and let $P(Y=+1)=0.75$, $P(Y=-1)=0.25$. Suppose the sample consists of one positive and one negative label, and let $\lambda=0.25$. For $-1\leq t\leq1$, the empirical hinge risk is $$ \frac{(1-t)+(1+t)}{2}=1. $$ The regularized objective on this interval is $1+0.25t^2$, minimized at $t=0$. For $t\geq1$, the empirical risk is $(1+t)/2$, and for $t\leq-1$ it is $(1-t)/2$; adding $0.25t^2$ gives no smaller value in either region. Hence $\hat f_\lambda=f_0$.

For $-1\leq t\leq1$, population risk is $0.75(1-t)+0.25(1+t)=1-0.5t$, minimized at $t=1$. For $t\geq1$, the risk is $0.25(1+t)$, which increases with $t$; for $t\leq-1$, it is $0.75(1-t)$, whose minimum on that region is at $-1$, with value $1.5$. Thus $R_*=0.5$. Use $g_\lambda=f_1$, for which $A_\lambda=0$ and $P_\lambda=0.25$.

The fitted score has population and empirical risks both equal to $1$, so its deviation is zero. At the comparator, empirical risk is $\{0+2\}/2=1$, while population risk is $0.5$; hence $S_{n,\lambda}=0.5$. The actual excess risk is $1-0.5=0.5$, while the bound is $0+0.5+0.25=0.75$. This sample can occur under the stated population distribution; the decomposition applies to the realized sample, without requiring it to match the population class proportions.

Worked Example: Nonzero Approximation Error

Let $P(Y=+1)=0.6$ and $P(Y=-1)=0.4$, again with constant input. The sample has four positive and one negative label, so its positive proportion is $q=0.8$. Set $\lambda=0.5$. For $-1\leq t\leq1$, empirical hinge risk is $$ 0.8(1-t)+0.2(1+t)=1-0.6t. $$ The regularized objective is $1-0.6t+0.5t^2$, minimized at $t=0.6$. For $t\geq1$, the empirical risk is $0.2(1+t)$, and the objective increases from its value at $1$. For $t\leq-1$, it is $0.8(1-t)$; the objective decreases up to the boundary $-1$, where it exceeds the value at $0.6$. Thus $\hat f_\lambda=f_{0.6}$.

The population risk on $[-1,1]$ is $0.6(1-t)+0.4(1+t)=1-0.2t$, minimized at $t=1$, with risk $0.8$. For $t\geq1$ it equals $0.4(1+t)$, which increases; for $t\leq-1$ it equals $0.6(1-t)$, whose minimum on that region is $1.2$. Therefore $R_*=0.8$. Choose the comparator $g_\lambda=f_0$. Its risk is $1$, so $A_\lambda=1-0.8=0.2$, and its penalty cost is zero.

At the fitted score, empirical risk is $0.8(0.4)+0.2(1.6)=0.64$, while population risk is $0.6(0.4)+0.4(1.6)=0.88$. The first absolute deviation is $0.24$. At $f_0$, both empirical and population risks equal $1$, so the second deviation is zero. Thus $S_{n,\lambda}=0.24$. The actual excess risk is $0.88-0.8=0.08$, and the bound is $0.2+0.24+0=0.44$. A comparator with no norm cost can still have approximation error; the terms describe different sources of error.

Approximate Empirical Minimization

In numerical work, the optimization may stop before reaching an exact minimum. The same reasoning accounts for this by adding the optimization tolerance, rather than silently treating an approximate solution as exact.

Corollary: If a score $\tilde f_\lambda\in\mathcal H$ satisfies $$ P_n\phi_{\tilde f_\lambda}+\lambda\|\tilde f_\lambda\|_{\mathcal H}^2 \leq P_n\phi_{g_\lambda}+\lambda\|g_\lambda\|_{\mathcal H}^2+\delta $$ for some $\delta\geq0$, then $$ R(\tilde f_\lambda)-R_* \leq A_\lambda+ \left|R(\tilde f_\lambda)-P_n\phi_{\tilde f_\lambda}\right| +\left|P_n\phi_{g_\lambda}-R(g_\lambda)\right| +\lambda\|g_\lambda\|_{\mathcal H}^2+\delta. $$

Proof. Rearranging the assumed objective inequality gives $P_n\phi_{\tilde f_\lambda}-P_n\phi_{g_\lambda}\leq \lambda(\|g_\lambda\|_{\mathcal H}^2-\|\tilde f_\lambda\|_{\mathcal H}^2)+\delta$. Insert this bound into the same add-and-subtract identity used in the theorem. Drop the nonpositive term $-\lambda\|\tilde f_\lambda\|_{\mathcal H}^2$ and bound the two signed deviations by their absolute values. The displayed inequality follows. $\square$

What the Bound Does—and Does Not—Say

For a fixed $\lambda$, the comparison is useful because it identifies how the choice of comparator affects the bound. A score close to the benchmark in population risk has small approximation error; a score with small RKHS norm has a small penalty cost. Those goals may conflict. The sample error records the empirical-to-population discrepancies needed for this particular comparison.

The inequality is not automatically a numerical guarantee: its sample-error terms involve population risks and may be unknown. Controlling them requires additional assumptions and arguments. In particular, a bound for one chosen score and one comparator is not a uniform deviation result over a norm-constrained class. Nor does a small surrogate excess risk by itself state a zero-one risk bound without an appropriate link between the surrogate and classification risk.

A frequent mistake is to call $\lambda\|g_\lambda\|_{\mathcal H}^2$ the entire regularization effect on the fitted classifier. In the sharper inequality the penalty contribution is $\lambda(\|g_\lambda\|_{\mathcal H}^2-\|\hat f_\lambda\|_{\mathcal H}^2)$; replacing it by $\lambda\|g_\lambda\|_{\mathcal H}^2$ is a valid upper bound because the omitted squared norm is nonnegative, but it can loosen the result. Another mistake is to treat the approximation error as a sample error: $R(g_\lambda)-R_*$ concerns population performance relative to the benchmark, regardless of which sample was observed.

Check Your Understanding

Use the fixed-comparator inequality and the definitions above to answer these questions.

In the exact decomposition, which term is controlled directly by empirical optimality?
Why is the penalty contribution bounded above by $\lambda\|g_\lambda\|_{\mathcal H}^2$, even when the sharper expression contains a negative fitted-score term?
For a fixed comparator, what two empirical-to-population discrepancies make up the sample error?
Can the comparator approximation error be nonzero when its RKHS penalty cost is zero? Explain using the definitions.
If an optimizer is known only to be within objective tolerance $\delta$, which additional term belongs in the comparison bound?