Calibration Functions for Multiclass Surrogates

Why Calibration Is a Quantitative Requirement

A surrogate loss replaces a task loss with an objective that may be easier to optimize. But optimization is useful only if a low surrogate risk forces the decoded prediction to have low task risk. Calibration expresses that link at a fixed covariate value: whenever a score leads to a decision with substantial task regret, its conditional surrogate risk must be separated from the best possible conditional surrogate risk.

This is more informative than saying that a surrogate is “consistent.” A calibration function gives a numerical lower bound on the surrogate regret required to incur a specified amount of task regret. That pointwise bound can then be integrated to relate population risks.

Conditional Risks and the Calibration Function

Let the label set be \(\mathcal Y=\{1,\ldots,K\}\), let \(\mathcal A\) be a finite set of task actions, and let \(L(a,y)\) be the task loss for action \(a\) when the label is \(y\). A conditional label distribution is a vector \(\eta\) in the probability simplex \(\Delta_K\), with coordinates \(\eta_y=P(Y=y\mid X=x)\). The conditional task risk of action \(a\) and its Bayes risk are

R_\eta(a)=\sum_{y=1}^K \eta_y L(a,y), \qquad R_\eta^*=\min_{a\in\mathcal A} R_\eta(a).

A surrogate predictor reports a score \(z\) from a set \(\mathcal Z\). The decoder \(d:\mathcal Z\to\mathcal A\) turns that score into a task action. For surrogate loss \(\phi(z,y)\), define the conditional surrogate risk and its infimum by

C_\eta(z)=\sum_{y=1}^K \eta_y\phi(z,y), \qquad C_\eta^*=\inf_{z\in\mathcal Z} C_\eta(z).

Assume the surrogate losses are measurable and the conditional risks and infima are well-defined and finite. The task regret of the decoded action is \(\Delta_\eta(z)=R_\eta(d(z))-R_\eta^*\). The surrogate regret is \(e_\eta(z)=C_\eta(z)-C_\eta^*\). Both are nonnegative. The calibration function below is a worst-case lower envelope over all conditional label distributions and scores.

Definition: Let \(T=\sup_{\eta\in\Delta_K,\ a\in\mathcal A}\{R_\eta(a)-R_\eta^*\}\), the largest possible task regret. For \(0\le t\le T\), define the calibration function

\delta(t)=\inf_{\substack{\eta\in\Delta_K,\ z\in\mathcal Z\\ \Delta_\eta(z)\ge t}} e_\eta(z).

The infimum of an empty set is \(+\infty\). The surrogate is calibrated for the task if \(\delta(t)>0\) for every attainable \(t>0\). Thus a fixed positive task error cannot be approached with surrogate regret tending to zero.

The constraint in this definition is “task regret at least \(t\),” not “task regret exactly \(t\).” As \(t\) increases, the constrained set can only shrink, so \(\delta\) is nondecreasing. The function need not be convex. This distinction matters when converting a conditional bound into a bound on expected regret.

Worked Examples

Worked Example: An Exact Calibration Function

Take multiclass zero-one loss, \(L(a,y)=\mathbf 1\{a\ne y\}\), with reports \(z\in\mathcal A=\{1,\ldots,K\}\), identity decoder \(d(z)=z\), and surrogate loss \(\phi(z,y)=\mathbf 1\{z\ne y\}\). Here the surrogate is the task loss itself.

For any \(\eta\), \(C_\eta(z)=R_\eta(z)=1-\eta_z\), and \(C_\eta^*=R_\eta^*=1-\max_y\eta_y\). Therefore \(e_\eta(z)=\Delta_\eta(z)\). Every score satisfying \(\Delta_\eta(z)\ge t\) has surrogate regret at least \(t\), so \(\delta(t)\ge t\).

For \(0\le t\le1\), choose \(\eta_1=(1+t)/2\), \(\eta_2=(1-t)/2\), and all other coordinates zero; predict class 2. The Bayes class is class 1 (or tied when \(t=0\)), and the task regret is \(\eta_1-\eta_2=t\). Its surrogate regret is also \(t\). Hence \(\delta(t)\le t\), and together the inequalities give \(\delta(t)=t\). This verifies calibration directly, although in this example it offers no computational advantage over the task loss.

Worked Example: A Three-Class Surrogate Bound

Consider three classes, zero-one task loss, reports \(p=(p_1,p_2,p_3)\) in the probability simplex, and decoder \(d(p)=\arg\max_j p_j\), with a fixed rule for ties. Use the surrogate loss \(\phi(p,y)=1-p_y\). Its conditional risk is \(C_\eta(p)=1-\sum_j\eta_jp_j\), and its infimum is \(C_\eta^*=1-\max_j\eta_j\): a unit mass on a class with largest \(\eta_j\) attains the infimum.

Suppose the decoder outputs \(j\), and let \(k\) be a class with largest probability \(\eta_k\). Since \(p_j\) is a largest report coordinate, \(p_j\ge1/3\). The task regret is \(\Delta_\eta(p)=\eta_k-\eta_j\). The surrogate regret satisfies

e_\eta(p) =\sum_{\ell=1}^3 p_\ell(\eta_k-\eta_\ell) \ge p_j(\eta_k-\eta_j) \ge \frac{\Delta_\eta(p)}{3}.

The first inequality holds because every term is nonnegative and the \(j\)th term is \(p_j(\eta_k-\eta_j)\). Consequently, \(\delta(t)\ge t/3\) for this task and surrogate: a positive task regret requires positive surrogate regret.

For a numerical check, take \(\eta=(0.6,0.3,0.1)\) and \(p=(0.2,0.5,0.3)\). The decoder chooses class 2, so the task regret is \(0.6-0.3=0.3\). The surrogate risk is \(1-(0.6(0.2)+0.3(0.5)+0.1(0.3))=1-0.30=0.70\). Its optimum is \(1-0.6=0.40\), giving surrogate regret \(0.30\), which is at least \(0.30/3=0.10\), as required.

Worked Example: A Binary Report With a Linear Calibration Function

For a binary label \(Y\in\{0,1\}\), write \(\eta=P(Y=1)\). Let the report be \(p\in[0,1]\), decode to 1 when \(p\ge1/2\) and to 0 otherwise, and use absolute loss \(\phi(p,y)=|p-y|\) with zero-one task loss. The conditional surrogate risk is

C_\eta(p)=\eta(1-p)+(1-\eta)p =\eta+p(1-2\eta), \qquad C_\eta^*=\min(\eta,1-\eta).

If \(\eta>1/2\), the Bayes task action is 1. A report decoded as 0 has \(p<1/2\). Its task regret is \(2\eta-1\), while its surrogate regret is \(C_\eta(p)-C_\eta^*=(1-2\eta)(p-1)\). The infimum over \(p<1/2\) is the limit as \(p\) approaches \(1/2\) from below, namely \((2\eta-1)/2\). If \(\eta<1/2\), a report decoded as 1 has \(p\ge1/2\); its task regret is \(1-2\eta\), and its surrogate regret is \(p(1-2\eta)\), minimized at \(p=1/2\) to give \((1-2\eta)/2\).

Thus, for either wrong decision, the infimum surrogate regret is half the task regret. Choosing \(\eta=(1+t)/2\) and \(p\) tending to \(1/2\) from below shows the bound is attained as an infimum for every \(0\le t\le1\). Therefore \(\delta(t)=t/2\). The strict tie rule matters: at \(p=1/2\), this decoder selects class 1.

From Conditional Calibration to Risk Bounds

The definition immediately gives a pointwise inequality. A second step shows what can be concluded after averaging over covariates. Let \(\eta(x)\) be the conditional distribution of \(Y\) given \(X=x\), and let \(g(x)\) be a measurable score predictor. Define its conditional task and surrogate regrets by \(\Delta_{\eta(x)}(g(x))\) and \(e_{\eta(x)}(g(x))\). Assume these quantities are measurable and integrable.

Theorem: For every \(\eta\) and score \(z\), \(e_\eta(z)\ge\delta(\Delta_\eta(z))\). Consequently, for any predictor \(g\),

E[e_{\eta(X)}(g(X))] \ge E[\delta(\Delta_{\eta(X)}(g(X)))]. $$ If \(\psi:[0,T]\to[0,\infty)\) is convex and nondecreasing, satisfies \(\psi(0)=0\), and obeys \(\psi(t)\le\delta(t)\) for every \(t\), then $$ E[e_{\eta(X)}(g(X))] \ge \psi\!\left(E[\Delta_{\eta(X)}(g(X))]\right).

Proof. Fix \(\eta\) and \(z\), and put \(t=\Delta_\eta(z)\). The pair \((\eta,z)\) is in the set over which \(\delta(t)\) takes its infimum, because its task regret equals \(t\) and therefore is at least \(t\). The infimum cannot exceed the surrogate regret at that pair, so \(\delta(t)\le e_\eta(z)\). Substituting \(\eta=\eta(x)\) and \(z=g(x)\) gives the pointwise inequality for each \(x\), and integrating gives the first expected-risk inequality.

Since \(\psi\le\delta\), the same pointwise argument gives \(e_{\eta(X)}(g(X))\ge\psi(\Delta_{\eta(X)}(g(X)))\). Taking expectations preserves the inequality. Jensen’s inequality applies because \(\psi\) is convex and the task regret is bounded between 0 and \(T\). It yields \(E[\psi(\Delta)]\ge\psi(E[\Delta])\), proving the final claim. \(\square\)

The first expected bound uses the calibration function itself and requires no convexity, but it retains the expectation of a transformed, pointwise regret. The last bound is often easier to interpret: a small expected surrogate regret forces the expected task regret to be small whenever \(\psi\) is positive away from zero and can be inverted on the relevant range. It requires a convex lower bound \(\psi\); one must not assume that the lower-envelope function \(\delta\) is automatically convex.

Worked Example: Turning a Calibration Bound Into a Population Bound

Suppose the conditional inequality is \(e_\eta(z)\ge\Delta_\eta(z)/3\), as in the three-class example. Set \(\psi(t)=t/3\), which is convex, nondecreasing, and zero at zero. The theorem gives

E[e_{\eta(X)}(g(X))] \ge \frac{1}{3}E[\Delta_{\eta(X)}(g(X))].

If the expected conditional surrogate regret is at most \(0.06\), then \(E[\Delta_{\eta(X)}(g(X))]\le 3(0.06)=0.18\). This conclusion is about expected task regret, not a guarantee that every covariate value has task regret at most \(0.18\). The argument requires the conditional risks and regrets to be measurable and the expectations to exist.

What Calibration Does—and Does Not—Guarantee

Calibration concerns the relationship between conditional risks and the decoder. It is not merely a property of the surrogate loss considered in isolation: changing the task loss or the decoder changes the task regrets in the constraint defining \(\delta\). A useful analysis therefore specifies all three ingredients—task loss, surrogate loss, and decoder—before making a calibration claim.

Calibration also does not say how quickly a learning algorithm finds low surrogate risk, or how accurately an estimated predictor performs with finite data. Those questions require additional statistical and optimization arguments. Calibration supplies the link needed after a surrogate-risk guarantee has been obtained.

Common Mistake

Wrong reasoning: “The surrogate regret is small on average, so the task regret must be small at every covariate value.” A population bound is an average and does not rule out a few points with large task regret.
Correction: First use the conditional inequality \(e_\eta(z)\ge\delta(\Delta_\eta(z))\), then integrate. To turn the result into a bound involving only expected task regret, use a convex, nondecreasing lower bound \(\psi\) and Jensen’s inequality. Even then, the conclusion is about expected regret, not a pointwise guarantee.

A related error is to check only that one surrogate-risk minimizer decodes to a Bayes action. Calibration is stronger: it rules out sequences of scores whose surrogate regrets approach zero while their task regrets remain bounded away from zero. The function \(\delta\) makes that separation explicit.

Key takeaway: Calibration is a conditional-risk separation property. The calibration function lower-bounds surrogate regret whenever decoded task regret is at least a specified amount; integration gives a population bound, and convexity is needed for the familiar Jensen-based bound in terms of expected task regret.

Check Your Understanding

Try these questions before moving on.

Why does the definition constrain task regret to be at least \(t\), rather than exactly \(t\)?
For the three-class surrogate, identify the inequality that uses the fact that the decoded class has the largest report coordinate.
In the binary absolute-loss example, why is the infimum over wrong reports only approached, rather than attained, when \(\eta>1/2\)?
What additional property of a lower bound \(\psi\) permits Jensen’s inequality to yield a bound involving expected task regret?
Explain why calibration alone does not guarantee that a learning algorithm will achieve small finite-sample task risk.