Multiclass Surrogate Regret Bounds

From Conditional Guarantees to Population Risk

A surrogate loss is optimized through a numerical objective, but the prediction of interest is judged by a task loss. A calibration inequality links these two quantities at a fixed covariate value: it says that a prediction with substantial task regret must also have substantial surrogate regret. The practical question is how to turn that pointwise statement into a guarantee averaged over the population.

The key is to average the conditional excess risks, not the raw losses. When the conditional calibration function is convex, Jensen’s inequality ensures that the population task excess risk is controlled by the population surrogate excess risk. This tutorial states the conditions precisely and works through the transfer for multiclass classification.

Conditional Risks and Calibration

Let $Y$ take values in $\mathcal{Y}=\{1,\ldots,K\}$, and let $X$ be a covariate. At a covariate value $x$, write $p_j(x)=P(Y=j\mid X=x)$. For a predicted label $a$, use the zero-one task loss, which is zero when $a=Y$ and one otherwise. Its conditional risk is $1-p_a(x)$; the smallest possible conditional risk is $1-\max_j p_j(x)$.

A score vector $u$ is converted to a label by a fixed decoder $d(u)\in\mathcal{Y}$. A surrogate loss $\phi(y,u)$ has conditional risk $C_\phi(u;p)=\sum_{j=1}^K p_j\phi(j,u)$. The difference between a risk and its best achievable conditional value is its conditional excess risk.

Definition: For a probability vector $p$ and score vector $u$, the conditional task regret and conditional surrogate regret are $$ \Delta(d(u);p)=\max_{j}p_j-p_{d(u)},\qquad \mathcal{E}_\phi(u;p)=C_\phi(u;p)-\inf_v C_\phi(v;p). $$ A calibration function $\psi:[0,1]\to[0,\infty)$ gives a conditional regret bound if it is convex and nondecreasing, $\psi(0)=0$, and $$ \psi\bigl(\Delta(d(u);p)\bigr)\leq \mathcal{E}_\phi(u;p) $$ for every probability vector $p$ and every allowed score vector $u$.

The task regret lies in $[0,1]$, which is why the calibration function is defined on that interval. The infimum in $\mathcal{E}_\phi$ need not be attained. Subtracting it matters: the minimum surrogate risk may be positive even for an ideal score, so raw surrogate risk generally includes a component that says nothing about the predictor’s regret.

The Conditional-to-Population Bound

Let $g(X)=d(u(X))$ be a measurable prediction rule. Define its population task excess risk by $R(g)-R^*$, where $R(g)=P(g(X)\ne Y)$ and $R^*=\inf_h P(h(X)\ne Y)$, with the infimum over measurable label-valued rules. Define its population surrogate excess risk by $$ S_\phi=E\!\left[C_\phi(u(X);p_X)-\inf_v C_\phi(v;p_X)\right], $$ where $p_X=(P(Y=j\mid X))_{j=1}^K$. Assume the conditional distributions and risks are measurable, the conditional calibration inequality holds almost surely, and the displayed nonnegative surrogate excess is measurable with finite expectation.

Theorem: Under these conditions, if $\psi$ is a convex, nondecreasing calibration function as defined above, then $$ \psi\bigl(R(g)-R^*\bigr)\leq S_\phi. $$ Consequently, $$ R(g)-R^*\leq \psi^{-1}_{+}(S_\phi),\qquad \psi^{-1}_{+}(s)=\sup\{t\in[0,1]:\psi(t)\leq s\}. $$

The generalized inverse is defined on $[0,1]$; it is a valid bound even when $\psi$ has flat portions. In the common case $\psi(t)=c t^\alpha$, for $c>0$ and $\alpha>0$, the theorem gives $R(g)-R^*\leq \min\{1,(S_\phi/c)^{1/\alpha}\}$.

Proof. For each $x$, let $\Delta_x=\max_j p_j(x)-p_{g(x)}(x)$. Choosing a label with maximal conditional probability minimizes the zero-one conditional risk, so the difference between the conditional risk of $g(x)$ and that minimum is exactly $\Delta_x$. Taking expectations gives $E[\Delta_X]=R(g)-R^*$. The pointwise calibration inequality gives $\psi(\Delta_X)\leq C_\phi(u(X);p_X)-\inf_v C_\phi(v;p_X)$ almost surely. Taking expectations and applying Jensen’s inequality to the convex function $\psi$ yields $$ \psi(R(g)-R^*)=\psi(E[\Delta_X]) \leq E[\psi(\Delta_X)] \leq S_\phi. $$ By the definition of $\psi^{-1}_{+}$, this implies $R(g)-R^*\leq\psi^{-1}_{+}(S_\phi)$. $\square$

Convexity is used in the direction $ \psi(E[\Delta_X])\leq E[\psi(\Delta_X)]$. Without a suitable convex calibration function, the conditional inequality alone does not justify this particular population bound.

Quadratic Calibration for the Brier Score

For multiclass probability prediction, a score can itself be a probability vector $q$ in the simplex. The Brier loss for outcome $y$ is $\sum_{j=1}^K(q_j-\mathbf{1}\{y=j\})^2$, and the decoder selects a label with largest $q_j$, using any fixed rule to break ties. Its conditional risk has an especially useful exact decomposition.

Result: For the multiclass Brier loss, the conditional surrogate excess at $q$ is $\|q-p\|_2^2$. Under the largest-probability decoder, $$ \frac{\Delta(d(q);p)^2}{2}\leq \|q-p\|_2^2. $$ Thus $\psi(t)=t^2/2$ is a calibration function, and the population bound is $$ R(g)-R^*\leq \sqrt{2S_\phi}. $$

Derivation. For an outcome $Y$ with probabilities $p$, expand the conditional Brier risk: $$ C_\phi(q;p)=\sum_{j=1}^K q_j^2-2\sum_{j=1}^Kp_jq_j+1. $$ Completing the square gives $C_\phi(q;p)=\|q-p\|_2^2+1-\|p\|_2^2$. Since $p$ belongs to the simplex, the minimum over $q$ is attained at $q=p$, and the excess is $\|q-p\|_2^2$.

To prove the regret inequality, choose $a$ with $p_a=\max_j p_j$, and let $b=d(q)$. Then $q_b\geq q_a$, including when the decoder breaks a tie. Therefore $$ \Delta(b;p)=p_a-p_b =(p_a-q_a)+(q_a-q_b)+(q_b-p_b) \leq |p_a-q_a|+|q_b-p_b|. $$ By Cauchy–Schwarz, the right side is at most $\sqrt{2}\sqrt{(p_a-q_a)^2+(p_b-q_b)^2}$, which is at most $\sqrt{2}\|p-q\|_2$. Squaring proves $\Delta(b;p)^2/2\leq\|p-q\|_2^2$, as claimed. Applying the population theorem with $\psi(t)=t^2/2$ gives the stated bound. $\square$

Worked Example: A Conditional Brier Regret Bound

Suppose the conditional label probabilities are $p=(0.60,0.30,0.10)$, and a model predicts $q=(0.35,0.40,0.25)$. The most probable true label is 1, while the model predicts label 2. Its task regret is $0.60-0.30=0.30$.

The probability-vector difference is $q-p=(-0.25,0.10,0.15)$, so the Brier surrogate excess is $$ \|q-p\|_2^2=(-0.25)^2+(0.10)^2+(0.15)^2 =0.0625+0.0100+0.0225=0.095. $$ The calibration-function value is $\psi(0.30)=0.30^2/2=0.045$. Thus the conditional inequality holds numerically: $0.045\leq0.095$. This is a bound, not an equality requirement; surrogate regret can be larger than the calibration function evaluated at task regret.

Worked Example: Aggregating Regret Across Two Covariate Strata

Let $X$ take values $A$ and $B$, with probabilities $P(X=A)=0.4$ and $P(X=B)=0.6$. At $A$, let $p_A=(0.70,0.20,0.10)$ and $q_A=(0.50,0.40,0.10)$. The decoder predicts label 1, which is also the most probable label, so $\Delta_A=0$. The conditional Brier excess is $$ \|q_A-p_A\|_2^2=(-0.20)^2+(0.20)^2+0^2=0.08. $$

At $B$, let $p_B=(0.20,0.50,0.30)$ and $q_B=(0.40,0.35,0.25)$. The model predicts label 1 instead of the most probable label 2, so $\Delta_B=0.50-0.20=0.30$. The conditional Brier excess is $$ \|q_B-p_B\|_2^2=(0.20)^2+(-0.15)^2+(-0.05)^2=0.065. $$ The population task excess is $0.4(0)+0.6(0.30)=0.18$. The population surrogate excess is $S_\phi=0.4(0.08)+0.6(0.065)=0.071$. The theorem gives $$ R(g)-R^*\leq\sqrt{2(0.071)}=\sqrt{0.142}\approx0.377. $$ The actual excess, $0.18$, is below this valid but conservative upper bound.

The intermediate Jensen calculation can also be checked directly: $E[\Delta_X^2/2]=0.4(0)+0.6(0.045)=0.027$, while $(E[\Delta_X])^2/2=0.18^2/2=0.0162$. The inequality $0.0162\leq0.027\leq0.071$ shows both steps in the population argument.

Worked Example: A Tie at the Decision Boundary

Consider two labels with conditional probabilities $p=(0.60,0.40)$, and predicted probabilities $q=(0.50,0.50)$. Suppose the fixed tie-breaking rule selects label 2. The Bayes label is 1, so the task regret is $0.60-0.40=0.20$. The Brier excess is $$ \|q-p\|_2^2=(-0.10)^2+(0.10)^2=0.02. $$ Here $\psi(0.20)=0.20^2/2=0.02$, so the conditional calibration bound holds with equality. The example also shows why the decoder’s tie rule should be specified: it determines the prediction at a tie, while the bound remains valid for either choice.

How to Read and Use the Bound

A population guarantee is useful because it separates a property of the loss from the distribution of covariates. Once the pointwise calibration inequality is established, the theorem applies to any measurable score rule with finite population surrogate excess. It does not require the conditional distribution $p_X$ to be constant across covariate values. The expectation incorporates those differences automatically.

For the Brier score, the square-root dependence is important: a surrogate excess of $S_\phi=0.02$ guarantees task excess at most $\sqrt{0.04}=0.20$. Smaller surrogate excess therefore forces smaller task excess, but the numerical guarantee need not be tight. A sharper calibration function, when available under the relevant conditions, can yield a sharper transfer.

Common mistake: use raw surrogate risk. Raw Brier risk includes the irreducible conditional term $1-\|p\|_2^2$. The theorem compares against the best conditional surrogate risk, so the relevant quantity is the surrogate excess.
Common mistake: average the conditional regrets and skip Jensen’s inequality. A pointwise statement $\psi(\Delta_X)\leq\mathcal{E}_\phi(X)$ does not by itself say $\psi(E[\Delta_X])\leq E[\mathcal{E}_\phi(X)]$ unless the needed convexity and integrability conditions hold.
Common mistake: treat a small surrogate loss as zero task regret. A finite upper bound controls task excess; it does not generally establish that the decoded predictions are Bayes-optimal at every covariate value.

Key takeaway: Establish a pointwise inequality between the calibration function of conditional task regret and conditional surrogate excess. If that calibration function is convex, averaging and Jensen’s inequality yield a population excess-risk guarantee.

Check Your Understanding

Use the definitions and bounds above to answer the following.

Why is conditional surrogate excess, rather than conditional surrogate risk, the quantity used in a calibration inequality?
Which step in the conditional-to-population proof requires convexity of $\psi$?
For the Brier score, what is the conditional surrogate excess when $p=(0.5,0.3,0.2)$ and $q=(0.4,0.4,0.2)$?
If a calibrated surrogate has $\psi(t)=t^2/2$ and population surrogate excess $S_\phi=0.08$, what upper bound does the theorem give on task excess risk?
Why must a decoder’s tie-breaking rule be fixed when defining the prediction rule, even though the Brier calibration inequality allows ties?