Calibration Bounds for Kernel Classification Scores

Why Calibration Bounds Matter

A kernel score \(f\) is often fitted by minimizing a surrogate loss rather than the discontinuous zero-one loss. To use that fitting objective as a guarantee about classification, one needs a link between the two kinds of risk: if the score has small excess surrogate risk, how large can its excess classification risk still be? A calibration bound answers this by bounding the latter in terms of the former.

The bound is a population statement. It applies to any measurable real-valued score, so it applies in particular to a measurable score in a reproducing kernel Hilbert space (RKHS). The RKHS structure determines which scores an estimation procedure can produce; it is not, by itself, needed for the calibration argument.

Risks and Conditional Regret

Let \(X\) take values in a standard Borel feature space and let \(Y\in\{-1,+1\}\). Write \(\eta(x)=P(Y=+1\mid X=x)\) for a measurable version of the conditional class probability. For a measurable score \(f\), use the classifier \(g_f(x)=+1\) when \(f(x)\geq 0\) and \(g_f(x)=-1\) otherwise. This convention fixes how ties at zero are classified.

Conditionally on \(X=x\), the classification regret of \(f\) is zero if its predicted class is a Bayes class, and is \(|2\eta(x)-1|\) if it predicts the other class. When \(\eta(x)=1/2\), both classes are Bayes classes and the regret is zero. Thus, writing \(d_f(x)\) for this conditional regret,

This conditional quantity is the bridge to surrogate risk. For each loss, we first show how much conditional surrogate regret is forced when the score predicts the wrong class.

Hinge-Loss Calibration

The hinge loss is \(\phi_{\mathrm{hinge}}(u)=(1-u)_+\), where \(a_+=\max(a,0)\). Its conditional risk at class probability \(\eta\) and score \(t\) is \(A_\eta(t)=\eta(1-t)_+ +(1-\eta)(1+t)_+\). The minimum over real \(t\) is \(2\min(\eta,1-\eta)\): for \(\eta>1/2\), it is attained by any \(t\geq1\); for \(\eta<1/2\), by any \(t\leq-1\); and for \(\eta=1/2\), by any \(t\in[-1,1]\).

Proof. Fix \(x\), set \(\eta=\eta(x)\), and write \(t=f(x)\). If \(\eta>1/2\) but \(t<0\), the classifier is wrong. When \(-1\leq t<0\), \(A_\eta(t)=1-(2\eta-1)t\geq1\). When \(t<-1\), \(A_\eta(t)=\eta(1-t)\geq2\eta\geq1\). Since the conditional minimum is \(2(1-\eta)=1-(2\eta-1)\), the conditional surrogate regret is at least \(2\eta-1\), exactly the conditional classification regret. If \(\eta<1/2\) and \(t\geq0\), symmetry gives conditional surrogate regret at least \(1-2\eta\), again the classification regret. In every other case, the classifier has zero conditional classification regret, while conditional surrogate regret is nonnegative. Therefore the conditional surrogate regret is at least \(d_f(x)\) for every \(x\).

The conditional minima above integrate to \(R_{\mathrm{hinge}}^*\). Indeed, their minimizing scores can be selected measurably from \(\eta(x)\) (choose \(1\) when \(\eta>1/2\), \(-1\) when \(\eta<1/2\), and \(0\) at equality). Integrating the pointwise inequality therefore gives \(R_{\mathrm{hinge}}(f)-R_{\mathrm{hinge}}^*\geq E[d_f(X)]=R_{01}(f)-R_{01}^*\). The last bound follows because an excess zero-one risk cannot exceed \(1\). \(\square\)

Logistic-Loss Calibration

Use the logistic loss \(\phi_{\mathrm{log}}(u)=\log(1+e^{-u})\), with natural logarithms. At conditional probability \(\eta\), its conditional risk is \(A_\eta(t)=\eta\log(1+e^{-t})+(1-\eta)\log(1+e^t)\). If \(q=(1+e^{-t})^{-1}\), this is the Bernoulli cross-entropy \(-\eta\log q-(1-\eta)\log(1-q)\). Its infimum is the binary entropy \(H(\eta)=-\eta\log\eta-(1-\eta)\log(1-\eta)\), with \(0\log0=0\). For \(0<\eta<1\), the infimum is attained at \(q=\eta\), equivalently \(t=\log(\eta/(1-\eta))\); at \(\eta=0\) or \(1\), it is an infimum approached as \(t\) tends to the corresponding infinity.

Proof. At a fixed \(x\), with conditional probability \(\eta\), the conditional logistic excess is \(A_\eta(t)-H(\eta)=\eta\log(\eta/q)+(1-\eta)\log((1-\eta)/(1-q))\), the Kullback–Leibler divergence between Bernoulli probabilities \(\eta\) and \(q\). Suppose first that \(\eta>1/2\) and the classifier is wrong. Then \(t<0\), so \(q<1/2\). As a function of \(q\), the divergence has derivative \((q-\eta)/(q(1-q))<0\) on \(0<q\leq1/2\); hence its infimum over that range is at \(q=1/2\). For \(\eta<1/2\) and a wrong prediction, the tie convention allows \(t=0\), and wrong predictions have \(q\geq1/2\). The derivative is positive there, so again the minimum is at \(q=1/2\). Thus whenever the conditional classification regret is \(u=|2\eta-1|\), a wrong prediction forces logistic excess at least \(\log2-H(\eta)=\psi_{\mathrm{log}}(u)\). If the prediction is Bayes, \(u=0\) and the same lower bound is zero.

The pointwise conditional infimum integrates to \(R_{\mathrm{log}}^*\). To see this without assuming a finite optimal score, restrict scores temporarily to \([-M,M]\). The conditional minimizing score is the log odds clipped to that interval, with endpoint values chosen at \(\eta=0,1\); it is measurable. The resulting conditional minimum decreases to \(H(\eta)\) as \(M\) increases. It lies between \(0\) and \(\log2\), since score \(0\) is available, so dominated convergence shows that the infimum population risk is \(E[H(\eta(X))]\). It follows that the conditional inequality just proved integrates to \(R_{\mathrm{log}}(f)-R_{\mathrm{log}}^*\geq E[\psi_{\mathrm{log}}(d_f(X))]\). Finally, \(\psi_{\mathrm{log}}\) is convex: on \(0<u<1\), its second derivative is \(1/(1-u^2)>0\), and it extends continuously to the endpoints. Jensen’s inequality gives \(E[\psi_{\mathrm{log}}(d_f(X))]\geq\psi_{\mathrm{log}}(E[d_f(X)])\). Using \(E[d_f(X)]=R_{01}(f)-R_{01}^*\) proves the result. Monotonicity and the definition of the capped inverse give the equivalent bound. \(\square\)

Using and Interpreting the Bounds

The two losses give different conversions. Hinge excess risk controls classification excess risk linearly. Logistic excess risk is converted through \(\psi_{\mathrm{log}}^{-1}\), which is nonlinear and capped at one. A useful simpler logistic consequence follows from \(\psi_{\mathrm{log}}''(u)\geq1\), together with \(\psi_{\mathrm{log}}(0)=\psi_{\mathrm{log}}'(0)=0\): integrating twice gives \(\psi_{\mathrm{log}}(u)\geq u^2/2\). Therefore \(R_{01}(f)-R_{01}^*\leq\min\{1,\sqrt{2(R_{\mathrm{log}}(f)-R_{\mathrm{log}}^*)}\}\).

Neither theorem requires a special kernel, a bounded RKHS norm, or a particular way of choosing the score. Those conditions may matter when proving that a fitted score has small excess surrogate risk, but that is a separate step. Calibration begins once such an excess-risk bound is available, and turns it into a guarantee relative to the Bayes classification risk.

Common Pitfall

A common mistake is to treat the logistic conversion as linear, for example claiming that excess zero-one risk is at most excess logistic risk. The conditional calculation shows why this reasoning fails: at class probability \(\eta=0.75\), a wrong score can have classification regret \(0.5\), while its smallest logistic regret is only about \(0.131\). The correction is to use \(\psi_{\mathrm{log}}^{-1}\), or a valid looser consequence such as the square-root bound. The hinge loss has a linear bound, but that fact does not transfer to every surrogate loss.