Turning Empirical Surrogate Bounds Into Regret Guarantees

From a Surrogate Bound to a Classification Guarantee

A finite-sample analysis may control how far a fitted score is from optimal under a surrogate loss. The practical question is what this says about its classification decisions. Calibration supplies the link: small population surrogate excess risk forces small classification regret. The conversion is made by applying the inverse of a calibration function to a bound that is already on the population surrogate excess risk.

This step does not itself establish a generalization bound. If the available result controls empirical risk, one first needs a valid argument that converts that result into a population bound. Once such a bound is supplied, calibration gives a direct regret guarantee, with the same confidence level.

Risks and the Calibration Inequality

Let \((X,Y)\) be a random pair, with \(Y\in\{-1,+1\}\), and define \(\eta(x)=P(Y=+1\mid X=x)\). A measurable score \(f\) predicts \(g_f(x)=+1\) when \(f(x)\geq 0\), and \(g_f(x)=-1\) otherwise. The Bayes classifier predicts a label with the larger conditional probability; when \(\eta(x)=1/2\), either label is Bayes-optimal.

Write \(R_{01}(g)=P(g(X)\ne Y)\) for classification risk. For a margin loss \(\phi\), define \(R_\phi(f)=E[\phi(Yf(X))]\). The conditional surrogate risk at \(x\) and score \(s\) is \(C_\phi(\eta(x),s)=\eta(x)\phi(s)+(1-\eta(x))\phi(-s)\). The pointwise optimal surrogate risk is \(C_\phi^*(\eta(x))=\inf_{s\in\mathbb R}C_\phi(\eta(x),s)\), and the population surrogate optimum is \(R_\phi^*=E[C_\phi^*(\eta(X))]\). These definitions allow an infimum that is not attained.

Define the classification regret of \(f\) by \(\mathcal E_{01}(f)=R_{01}(g_f)-\inf_g R_{01}(g)\), where the infimum ranges over measurable classifiers. If \(g_f(x)\) is not Bayes-optimal, its conditional classification excess is \(|2\eta(x)-1|\); otherwise it is zero. Thus, with \(\Delta_f(X)=|2\eta(X)-1|\,\mathbf 1\{g_f(X)\text{ is not Bayes-optimal}\}\), we have \(\mathcal E_{01}(f)=E[\Delta_f(X)]\).

The Population Conversion

To see the connection, at a point where the score decision is correct, \(\Delta_f=0\) and \(\psi(\Delta_f)=0\). Where it is wrong, the calibration inequality gives conditional surrogate excess at least \(\psi(\Delta_f)\). Taking expectations therefore gives \(R_\phi(f)-R_\phi^*\geq E[\psi(\Delta_f)]\). The equality between expected conditional excess and population excess follows by conditioning on \(X\), since \(R_\phi(f)=E[C_\phi(\eta(X),f(X))]\) and \(R_\phi^*=E[C_\phi^*(\eta(X))]\). The latter subtraction is valid, for example, when the risks are finite; if the surrogate excess is infinite, the claimed inequality is immediate. Jensen’s inequality applies because \(\Delta_f\in[0,1]\) and \(\psi\) is convex: \[ E[\psi(\Delta_f)]\geq\psi(E[\Delta_f])=\psi(\mathcal E_{01}(f)). \] Combining the inequalities proves the result. \(\square\)

For inversion, define the upper generalized inverse \[ \psi^{\leftarrow}(u)=\sup\{t\in[0,1]:\psi(t)\leq u\},\qquad u\geq 0. \] The set is nonempty because \(\psi(0)=0\). If \(\psi(\mathcal E_{01}(f))\leq u\), then \(\mathcal E_{01}(f)\) belongs to this set and is no larger than its supremum. Consequently, \[ R_\phi(f)-R_\phi^*\leq u \quad\Longrightarrow\quad \mathcal E_{01}(f)\leq\psi^{\leftarrow}(u). \] When \(\psi\) is continuous and strictly increasing, this is its ordinary inverse for \(u\leq\psi(1)\); for larger \(u\), the regret bound is at most \(1\). The generalized inverse also handles flat portions without pretending that an ordinary inverse exists.

On every data set where the assumed surrogate bound holds, the population conversion applies to the realized score \(\hat f\), giving \(\mathcal E_{01}(\hat f)\leq\psi^{\leftarrow}(B_n)\). The event for the regret guarantee therefore contains the event for the surrogate bound, so its probability is at least \(1-\delta\). No new probability calculation or confidence penalty is introduced in this conversion. \(\square\)

Worked Conversions

Interpreting the Bound and Avoiding a Common Error

The inverse function determines how much classification regret is compatible with a given surrogate excess. For example, if \(\psi(t)=ct^q\) with \(c>0\) and \(q\geq1\), then \(\psi^{\leftarrow}(u)=\min\{1,(u/c)^{1/q}\}\). A quadratic calibration bound therefore turns a surrogate excess rate of order \(n^{-1/2}\) into a regret bound of order \(n^{-1/4}\), unless other structure supplies a sharper route. The inversion is a mathematical consequence of the particular calibration bound; it is not an empirical-process calculation.

A common mistake is to take a bound on \(\widehat R_\phi(\hat f)\), or on empirical excess risk, and apply \(\psi^{\leftarrow}\) directly. Calibration concerns population excess \(R_\phi(\hat f)-R_\phi^*\). An empirical quantity cannot replace it without a justified generalization and optimization argument, and a restricted score class may also incur an approximation gap. The correction is to identify exactly what the supplied result bounds, add any required terms to obtain a population excess bound, and only then apply the generalized inverse.