Diagnosing Slow Excess Risk in a Kernel Classifier

What a Slow Guarantee Is Diagnosing

A kernel classifier can fit its observed labels very accurately and still have a weak guarantee for population performance. A useful diagnosis asks which part of the argument is responsible: perhaps the chosen function class cannot approximate the target well, the sample does not control population loss uniformly, the empirical objective is not optimized accurately, or the distribution does not satisfy a favorable margin condition. These are distinct issues, and a slow bound should not be blamed on “the kernel” without identifying which assumption or term is limiting it.

We use binary labels $Y\in\{-1,+1\}$, a feature vector $X$, and a score $f(X)$. The corresponding classifier must assign a label even when its score is zero. Throughout, define $g_f(x)=+1$ when $f(x)\geq 0$, and $g_f(x)=-1$ when $f(x)<0$. This tie rule matters: the classification regret identity below is stated for a label-valued classifier, not for a sign function that might return zero.

Definition: Let $\eta(x)=P(Y=+1\mid X=x)$, and let $R(g)=P(g(X)\ne Y)$ be the population classification risk of a label-valued rule $g$. A Bayes classifier chooses a label with the larger conditional probability; write its risk as $R^*$. The excess risk, or classification regret, of $g_f$ is $R(g_f)-R^*$. Define $\delta(x)=|2\eta(x)-1|$. At each $x$, the conditional excess risk is $\delta(x)$ if $g_f(x)$ chooses the less probable label, and zero otherwise.

For logistic loss, $\ell(yf)=\log(1+\exp(-yf))$, the population surrogate risk is $L(f)=E[\ell(Yf(X))]$. The conditional minimizing score, when $0<\eta(x)<1$, is $\log\{\eta(x)/(1-\eta(x))\}$. Its conditional minimum is the binary entropy. At $\eta=0$ or $1$, the minimum is an infimum, approached by scores tending to the appropriate infinity. Write $L^*=\inf_f L(f)$, with the infimum over measurable scores, and define the logistic excess $Z(f)=L(f)-L^*$.

A common way to diagnose the guarantee for a regularized kernel fit is to bound $Z(\hat f)$ first, and then translate that bound into classification regret. The first bound separates three contributions. A margin condition enters in the second translation; it is not a fourth additive term in the surrogate-risk decomposition.

Three Contributions to Logistic Excess

Definition: Let $\mathcal H$ be a reproducing kernel Hilbert space with norm $\|\cdot\|_{\mathcal H}$, and let $\lambda>0$. Define the penalized approximation term $$ A_\lambda=\inf_{f\in\mathcal H}\left\{L(f)-L^*+\lambda\|f\|_{\mathcal H}^2\right\}. $$ For data $(X_i,Y_i)_{i=1}^n$, let $P_n$ denote the empirical average and $P$ the population expectation. Suppose a fitted score $\hat f$ satisfies $P_n\ell_{\hat f}+\lambda\|\hat f\|_{\mathcal H}^2\leq\inf_{f\in\mathcal H}\{P_n\ell_f+\lambda\|f\|_{\mathcal H}^2\}+\varepsilon$, where $\ell_f=\ell(Yf(X))$ and $\varepsilon\geq0$. Let $D$ be a finite uniform deviation bound satisfying $\sup_{f\in\mathcal H}|P_n\ell_f-P\ell_f|\leq D$.

The deviation condition is an assumption about the class over which the comparison is made. In applications, a finite bound may require a norm restriction, bounded scores, or a suitable localized argument; it should not be presumed for an unrestricted class merely because the fit is a kernel method. The optimization tolerance $\varepsilon$ is also explicit: it measures how far the returned score may be from minimizing the empirical penalized objective.

Theorem: Under the preceding conditions, $$ Z(\hat f)\leq A_\lambda+2D+\varepsilon. $$ The three terms are penalized approximation, uniform estimation error, and optimization error, respectively.

Proof. For any $g\in\mathcal H$, the uniform deviation bound and the assumed empirical optimization inequality give

\begin{aligned} P\ell_{\hat f}+\lambda\|\hat f\|_{\mathcal H}^2 &\leq P_n\ell_{\hat f}+\lambda\|\hat f\|_{\mathcal H}^2+D\\ &\leq \inf_{f\in\mathcal H}\{P_n\ell_f+\lambda\|f\|_{\mathcal H}^2\}+\varepsilon+D\\ &\leq P_n\ell_g+\lambda\|g\|_{\mathcal H}^2+\varepsilon+D\\ &\leq P\ell_g+\lambda\|g\|_{\mathcal H}^2+\varepsilon+2D. \end{aligned}

Since $\lambda\|\hat f\|_{\mathcal H}^2\geq0$, dropping this term from the left side preserves the inequality. Subtract $L^*$, then take the infimum over $g\in\mathcal H$. The result is $Z(\hat f)\leq A_\lambda+\varepsilon+2D$, as claimed. $\square$

A small $A_\lambda$ says that some score in the RKHS can achieve small logistic excess without paying too much regularization. A small $D$ says the observed loss is a reliable proxy for population loss over the comparison class. A small $\varepsilon$ says the optimization procedure solved its empirical task accurately enough. Reducing one term cannot compensate automatically for another term that remains large.

Margin Conditions and the Regret Conversion

Logistic excess is not itself classification regret. A margin condition controls how much probability lies near the decision boundary, where even a small score error can change a label. We use the following version, with $\alpha\geq0$ and $C>0$.

Definition: The distribution satisfies the margin condition with parameters $(C,\alpha)$ if, for every $t>0$, $$ P\{\delta(X)\leq t\}\leq Ct^\alpha,\qquad \delta(X)=|2\eta(X)-1|. $$

When $\alpha$ is larger, the condition restricts the probability near $\eta(X)=1/2$ more strongly. The constant $C$ matters too: a large $C$ weakens the resulting guarantee. A margin condition is a property of the distribution, not a consequence of high training accuracy.

Theorem: If the margin condition holds and $Z(f)$ is the logistic excess of a measurable score $f$, then the classifier $g_f(x)=+1$ for $f(x)\geq0$ and $g_f(x)=-1$ otherwise satisfies $$ R(g_f)-R^*\leq 3C^{1/(\alpha+2)}Z(f)^{(\alpha+1)/(\alpha+2)}. $$ The tie at zero is assigned to $+1$, as specified; the result applies to this label-valued rule.

Proof. Set $q(x)=1/(1+\exp(-f(x)))$. At a fixed $x$, the conditional logistic excess is $$ \eta(x)\log\frac{\eta(x)}{q(x)}+(1-\eta(x))\log\frac{1-\eta(x)}{1-q(x)}, $$ with the usual limiting interpretation at $\eta(x)=0$ or $1$. This is the Kullback–Leibler divergence between Bernoulli distributions with success probabilities $\eta(x)$ and $q(x)$. Pinsker’s inequality for Bernoulli distributions lower-bounds it by $2(q(x)-\eta(x))^2$.

If $g_f(x)$ chooses the less probable label, then $|q(x)-\eta(x)|\geq\delta(x)/2$. This includes a tie $f(x)=0$: then $q(x)=1/2$, and if the tie rule chooses the less probable $+1$ label, the same inequality holds. Thus, on a misclassified point with $\delta(x)>t$, the conditional logistic excess is at least $\delta(x)^2/2$. The conditional classification excess is $\delta(x)$. Consequently, on that event it is at most $2/t$ times the conditional logistic excess, since $\delta(x)>t$.

Split the population regret into $\{\delta(X)\leq t\}$ and $\{\delta(X)>t\}$. On the first event its conditional value is at most $t$, and on the second event the preceding inequality applies wherever the classifier is wrong. Integrating and using the margin condition gives, for every $t>0$,

R(g_f)-R^* \leq tP\{\delta(X)\leq t\}+\frac{2Z(f)}{t} \leq Ct^{\alpha+1}+\frac{2Z(f)}{t}.

If $Z(f)>0$, choose $t=(Z(f)/C)^{1/(\alpha+2)}$. The first term becomes $C^{1/(\alpha+2)}Z(f)^{(\alpha+1)/(\alpha+2)}$, and the second becomes twice that quantity. If $Z(f)=0$, let $t$ decrease to zero in the displayed inequality; because $\alpha+1>0$, the regret is zero. This proves the result. $\square$

Combining the two results gives a useful diagnostic guarantee:

R(g_{\hat f})-R^* \leq 3C^{1/(\alpha+2)} \left(A_\lambda+2D+\varepsilon\right)^{(\alpha+1)/(\alpha+2)}.

This conversion explains why a regret guarantee can be slow even when the surrogate excess bound looks respectable. A weak margin condition, a large margin constant, or a substantial approximation, estimation, or optimization term can each limit the final statement. The exponent is a guarantee under the stated assumptions; it does not claim the classifier’s actual regret equals the bound.

Worked Diagnoses

Worked Example: Locating the Largest Bound Contribution

Suppose a regularized fit has $A_\lambda=0.012$, $D=0.008$, and $\varepsilon=0.004$. Suppose also that the distribution satisfies a margin condition with $C=2$ and $\alpha=1$. Calculate the resulting regret guarantee and identify its principal bottleneck.

The logistic excess bound is $$ Z(\hat f)\leq0.012+2(0.008)+0.004=0.032. $$ The estimation contribution is $2D=0.016$, which is larger than the approximation contribution $0.012$ and the optimization contribution $0.004$. In this numerical decomposition, estimation is the largest of the three.

For $C=2$ and $\alpha=1$, the regret exponent is $2/3$, so $$ R(g_{\hat f})-R^*\leq3(2)^{1/3}(0.032)^{2/3}\approx3(1.2599)(0.1007)\approx0.381. $$ This is a valid but loose upper bound. It does not establish that regret is near $0.381$; it says the assumptions and terms used here do not certify a smaller value.

Worked Example: A Zero Score and Its Tie Rule

Let $X$ be constant, let $\eta(X)=0.49$, and take the score $f(X)=0$. Under the stated tie rule, $g_f(X)=+1$. The Bayes label is $-1$, so the regret is $$ R(g_f)-R^*=0.51-0.49=0.02. $$

The logistic probability assigned by this score is $q=1/2$. Its logistic excess is $$ Z(f)=0.49\log(0.98)+0.51\log(1.02)\approx0.000200. $$ Here $\delta(X)=|2(0.49)-1|=0.02$. The margin condition holds with $\alpha=1$, $C=50$: for $t<0.02$ its left side is zero, and for $t\geq0.02$ its left side is one while $50t\geq1$.

The theorem therefore gives $$ R(g_f)-R^*\leq3(50)^{1/3}(0.000200)^{2/3}\approx0.038. $$ The bound exceeds the actual regret $0.02$, as an upper bound may. Most importantly, the zero score predicts a valid label under the stated convention, and the pointwise regret calculation uses that same prediction.

Worked Example: Perfect Training Accuracy, Positive Population Regret

Let $X$ take values $0$ and $1$, with $P(X=1)=0.05$ and $P(X=0)=0.95$. Let $Y=+1$ whenever $X=0$, and $Y=-1$ whenever $X=1$. The Bayes risk is zero. Consider a sample of $n=10$, and suppose the fitted rule predicts $+1$ everywhere whenever all ten observed feature values equal zero.

The event that all ten observations have $X=0$ has probability $$ P(X_1=\cdots=X_{10}=0)=0.95^{10}\approx0.599. $$ On this event every observed label is $+1$, so the rule has 100% training accuracy. But in the population it misclassifies every point with $X=1$. Its population risk, and hence its excess risk, is $0.05$.

The example does not say that a particular kernel procedure must produce this rule. It shows why training accuracy by itself cannot rule out unobserved regions or establish a population guarantee. The empirical observations may contain no information about a feature region that still has positive population probability.

How to Read a Slow Bound

When a kernel classification guarantee is slow, inspect the assumptions and terms in order rather than treating the rate as one indivisible expression.

Check approximation.
If $A_\lambda$ is large, the available RKHS scores cannot achieve small logistic excess at an acceptable penalty level. More accurate empirical optimization does not remove this limitation.

Check estimation.
If $D$ is large, the sample does not uniformly control population loss over the relevant class. Consider the complexity or localization assumptions behind the deviation bound.

Check optimization.
If $\varepsilon$ is large, the returned fit has not been shown to minimize the empirical penalized objective closely enough. This is distinct from sampling uncertainty.

Check the margin assumption.
Even with small logistic excess, the regret conversion depends on $C$ and $\alpha$. If that condition is unavailable or weak, this particular fast conversion is unavailable or weak too.

A common mistake is to see near-perfect training accuracy and infer that population regret is small. Training accuracy concerns the observed sample; regret compares population risk with the population Bayes risk. The two quantities answer different questions. Another mistake is to call every slow final rate an estimation problem. The decomposition shows that approximation or optimization may dominate instead, while the margin condition affects the conversion from surrogate excess to regret.

Key takeaway: Diagnose the guarantee in two stages: first identify whether approximation, estimation, or optimization controls the logistic excess; then assess whether the distribution’s margin condition supports a strong conversion to classification regret. High empirical accuracy alone establishes neither stage.

Check Your Understanding

Use the definitions and bounds in this tutorial to answer the following questions.

If $A_\lambda$ is small but $D$ is large, which part of the guarantee is limiting the logistic excess bound, and what does $D$ measure?
Why is optimization tolerance $\varepsilon$ not interchangeable with estimation error $D$?
For a zero score, what label does the classifier predict under the convention used here, and why must the regret calculation respect that convention?
What role does the margin condition play in the regret guarantee, and which two quantities from that condition affect the bound?
In the two-point feature example, why can perfect training accuracy coexist with positive population regret?