Surrogate-to-Task Excess-Risk Transfer

Why Excess Risk Needs a Transfer Argument

A predictor can have small risk under a surrogate loss without that statement, by itself, saying how well it performs under the task loss. The bridge is a calibration condition: it quantifies how much surrogate excess risk is required whenever the prediction incurs nonzero task regret. A population transfer bound then converts that pointwise relationship into a guarantee about expected task performance.

The distinction between a conditional and a population guarantee matters. Calibration is most naturally stated separately at each input value. To obtain a population statement, we average over inputs and use the convexity of the calibration function. We also need to respect the range of that function: its inverse is defined only on that range. Since task regret is bounded, the final bound can be written so its inverse is always evaluated in its domain.

Conditional Risks and the Calibration Condition

Let \(X\) be an input, \(Y\) a structured output taking values in a finite set \(\mathcal Y\), and \(\mathcal A\) a finite set of actions or predicted outputs. Let \(\Delta:\mathcal A\times\mathcal Y\to[0,M]\) be the task loss, where \(0<M<\infty\). Assume a regular conditional distribution \(P(Y\mid X=x)\) is available; for example, it is enough to take the input space to be standard Borel. A score predictor \(g\) takes values in a measurable score space \(\mathcal U\), and a measurable decoder \(d:\mathcal U\to\mathcal A\) turns scores into actions.

For a fixed input \(x\), define the conditional task risk of action \(a\) and its Bayes value by

The conditional task regret of a score \(u\) is \(t(u,x)=r_\Delta(d(u)\mid x)-r_\Delta^*(x)\). It lies in \([0,M]\): each conditional task risk lies in \([0,M]\), and the Bayes risk is the minimum of those risks.

Let \(\ell:\mathcal U\times\mathcal Y\to[0,\infty]\) be a measurable surrogate loss. Its conditional risk and conditional optimum are

Assume \(r_s^*(X)\) is measurable, the expectations below are well-defined, and the predictor \(g\) has finite surrogate risk. If the infimum over \(v\) is not attained, we still use the pointwise infimum. To identify the population surrogate benchmark with \(E[r_s^*(X)]\), assume measurable predictors can approximate these conditional infima arbitrarily closely in expectation. In particular, this holds when there are measurable conditional minimizers, or under the usual measurable-selection conditions that provide measurable approximate minimizers.

The condition is a lower bound on surrogate excess in terms of task regret. It does not say surrogate excess is at most \(\psi(M)\). That distinction is essential when applying the inverse calibration function.

The Population Transfer Bound

Write \(R_\Delta(d\circ g)=E[\Delta(d(g(X)),Y)]\), and let \(R_\Delta^*=E[r_\Delta^*(X)]\). Define \(R_s(g)=E[\ell(g(X),Y)]\) and \(R_s^*=E[r_s^*(X)]\), under the benchmark assumption just stated. The excesses are \(T=R_\Delta(d\circ g)-R_\Delta^*\) and \(S=R_s(g)-R_s^*\).

Proof. Put \(t(X)=t(g(X),X)\) and \(s(X)=r_s(g(X)\mid X)-r_s^*(X)\). By definition, both are measurable under the stated assumptions, \(0\le t(X)\le M\), and \(s(X)\ge0\). The calibration condition gives \(\psi(t(X))\le s(X)\) almost surely. Taking expectations yields \(E[\psi(t(X))]\le E[s(X)]=S\). Also \(T=E[t(X)]\), by conditioning the task loss on \(X\) and subtracting \(E[r_\Delta^*(X)]\). Since \(\psi\) is convex and \(t(X)\in[0,M]\), Jensen’s inequality gives

The bound \(0\le T\le M\) follows from \(t(X)\in[0,M]\). Because \(\psi\) is increasing, this also gives \(\psi(T)\le\psi(M)\). Thus \(\psi(T)\le\min\{S,\psi(M)\}\). The minimum belongs to \([0,\psi(M)]\), the domain of \(\psi^{-1}\); applying the increasing inverse proves the claimed result. \(\square\)

The cap by \(\psi(M)\) is not optional if \(S\) can exceed \(\psi(M)\). It both preserves the bound and ensures that the inverse is applied only within its range.

Worked Example: Binary Classification with Squared Loss

Worked Example: A Finite Structured Output Space

Worked Example: Using the Transfer Bound and Its Cap

Assumptions, Interpretation, and a Common Pitfall

The transfer theorem separates three ingredients. First, the task loss is bounded, so task regret lies in a known interval. Second, the surrogate excess is measured relative to the pointwise conditional optimum, with the population benchmark matching its expectation. Third, calibration holds for the chosen score-to-action decoder. Changing the decoder can invalidate the calibration condition even when the surrogate loss is unchanged.

The convexity assumption is used specifically to pass from conditional regrets to their average: Jensen’s inequality gives \(\psi(E[t])\le E[\psi(t)]\). Without convexity, that step is not justified in general. Strict increase and continuity make the ordinary inverse on the stated range available. For functions that are not strictly increasing, a generalized inverse can be used, but it must be defined explicitly.

• Wrong reasoning: “Calibration gives \(\psi(T)\le S\), so the bound is \(T\le\psi^{-1}(S)\) for every \(S\).” This overlooks that \(\psi^{-1}\) is defined here only up to \(\psi(M)\).
• Correction: Since \(T\le M\), the proof also gives \(\psi(T)\le\psi(M)\). Combine the two inequalities to obtain \(\psi(T)\le\min\{S,\psi(M)\}\), then invert.
• Another common mistake: Treating a small surrogate risk as automatically sufficient. The theorem uses surrogate excess over its benchmark, and the calibration inequality must connect it to the task regret for the decoder actually used.