Common Errors in Kernel Classification Guarantees

Why Guarantee Audits Need More Than a Rate Formula

A kernel classification guarantee is a chain of statements: an objective is minimized, the resulting score is turned into a classifier, and the classifier's population risk is bounded. Errors arise when one link is silently replaced by another. A small surrogate loss is not itself a zero-one risk; a score of zero needs a prediction rule; separability is not a generalization bound; and a penalty parameter has meaning only relative to the objective's normalization.

The earlier material on margin conditions, fast rates, and regularization scaling supplies the ingredients for many such bounds. Here the task is to audit how those ingredients are used. We use binary labels \(Y\in\{-1,+1\}\), an input \(X\), and a measurable real-valued score \(f\). Unless stated otherwise, define its classifier by \(g_f(x)=+1\) when \(f(x)\geq 0\), and \(g_f(x)=-1\) when \(f(x)<0\). This convention matters when the score is tied at zero.

Error 1: Calling Surrogate Risk Zero-One Risk

A surrogate loss replaces the discontinuous error indicator with a loss on the signed score \(Yf(X)\). For example, the hinge loss is \(\phi_{\mathrm{hinge}}(u)=(1-u)_+\), where \(a_+=\max(a,0)\). The logistic loss is \(\phi_{\mathrm{log}}(u)=\log(1+e^{-u})\). Their values and scales are not those of the zero-one loss. A numerical surrogate-risk bound must not be reported as though it were a bound of the same numerical size on classification error unless a valid comparison has been established.

Proof. For each outcome \((X,Y)\), if \(g_f(X)\ne Y\), then \(Yf(X)\leq 0\). Indeed, an error with \(Y=+1\) requires \(f(X)<0\), while an error with \(Y=-1\) under the chosen convention requires \(f(X)\geq 0\); in both cases the signed margin is at most zero. Therefore \((1-Yf(X))_+\geq 1\). If there is no error, the indicator of error is zero and the hinge loss is nonnegative. Thus, pointwise,

Taking expectations gives the asserted risk inequality. If the hinge risk is zero, the nonnegative zero-one risk is bounded above by zero and hence is zero. \(\square\)

The reverse shortcut is also unsafe: a small surrogate risk does not, by itself, identify a particular zero-one risk. The hinge inequality above is a valid one-sided comparison for the raw hinge risk. To reason about excess risk, one must compare the appropriate excess quantities and use a valid surrogate-to-classification-risk result under its hypotheses. In general, subtracting a surrogate-risk infimum does not turn the difference into zero-one excess risk.

Error 2: Leaving Score Ties Unspecified

The notation \(\operatorname{sign}(f(x))\) can conceal a genuine decision rule. At \(f(x)=0\), a convention is needed: predict \(+1\), predict \(-1\), or randomize. These choices can have different risks whenever \(P(f(X)=0)>0\). A tie convention that is irrelevant for a continuous score distribution need not be irrelevant for a fitted classifier that produces exact zeros.

Derivation. On \(T\), a \(+1\) prediction is wrong exactly when \(Y=-1\), so the error event restricted to \(T\) is \(T\cap\{Y=-1\}\). A \(-1\) prediction is wrong exactly when \(Y=+1\), giving \(T\cap\{Y=+1\}\). Taking probabilities yields the two contributions. If a randomized rule predicts \(+1\) with probability \(q\) at a tie, independently of the label conditional on the score, the contribution is \(qP(T,Y=-1)+(1-q)P(T,Y=+1)\). \(\square\)

When reading a margin or classification guarantee, check what classifier is covered and how ties are treated. A condition controlling the probability of scores near zero may help bound the effect of near-ties, but it does not license silently changing the prediction at an exact tie.

Error 3: Treating Separability as a Fast-Rate Assumption

Separability says that some rule can classify the relevant observations without error. It does not, on its own, control how many rules fit those observations, how complex the selected rule is, how close population points lie to a decision boundary, or how well empirical performance predicts population performance. Fast-rate conclusions use additional conditions, such as suitable noise or Bernstein conditions together with control of the estimator's complexity and approximation error. The exact hypotheses depend on the bound; separability is not a substitute for them.

This example does not show that every separable kernel problem has slow rates. It shows why separability alone cannot establish a rate. In a kernel analysis, the relevant guarantee may depend on the RKHS norm of the fitted score, the kernel's effective complexity, approximation error, a margin or noise condition, and the regularization schedule. Each assumption does a distinct job. A small empirical hinge loss, for example, is not a replacement for the population conditions in a fast-rate theorem.

Error 4: Comparing Penalties Without Comparing Objectives

Regularization parameters are not portable numbers independent of the objective's scale. A common pair of objectives is a sum of losses with a squared-norm penalty and an average loss with the same type of penalty. Since the average loss is \(1/n\) times the sum, matching the two objectives requires rescaling the penalty parameter as well.

Proof. Multiplying the average-loss objective by \(n>0\) leaves its minimizers unchanged. The result is

This equals \(J_{\mathrm{sum}}(f)\) for every \(f\) exactly when \(\lambda_{\mathrm{sum}}=n\lambda_{\mathrm{avg}}\). Since multiplication by a positive constant preserves the set of minimizers, the objectives then have the same minimizers. \(\square\)

This conversion assumes the loss and penalty are otherwise written identically. A factor such as \(1/2\) on the penalty must also be accounted for if it differs between formulations.

A Practical Audit and Common Pitfalls

Before interpreting a kernel classification guarantee, check each of the following:

• Risk target: Is the bound for surrogate risk, zero-one risk, or an excess-risk quantity? What comparison justifies moving between them?
• Decision rule: How is the score converted to a label at zero, and can ties occur with positive probability?
• Rate assumptions: Does the argument use a noise or margin condition, a complexity or norm bound, and a specified approximation term? Is separability being used only as a feasibility statement?
• Objective scale: Is the empirical loss summed or averaged? Are the penalty and any constants written with the same normalization as the theorem?

A common mistake is to read “the surrogate objective is small, the sample is separable, and the fitted score has a penalty of \(0.01\)” as enough information to infer a small classification error and a fast rate. The correction is to identify the exact population risk being bounded, fix the tie rule, verify every noise and complexity hypothesis, and translate the penalty to the theorem's objective normalization. Each step prevents a different kind of invalid comparison.