From Conditional Bounds to Population Regret

From a Conditional Bound to a Population Guarantee

A calibration inequality is first a statement at a fixed feature value: if a score makes a classification decision that is conditionally worse than the Bayes decision, its conditional surrogate risk must pay a corresponding cost. A learning procedure, however, is judged across the distribution of \(X\). To transfer the conditional statement to that population scale, we average over \(X\) and use convexity.

This passage has two parts. First, the conditional classification regret and conditional surrogate excess must be defined using the same conditional distribution of \(Y\) given \(X\). Second, Jensen’s inequality converts the average of a convex function of the conditional regret into a function of the average regret. The result is a bound on population classification regret in terms of population surrogate excess.

Conditional and Population Regrets

Consider binary classification with \(Y\in\{-1,+1\}\), feature vector \(X\), and a measurable real-valued score \(f(X)\). The classifier predicts \(+1\) when \(f(X)\geq 0\), and predicts \(-1\) otherwise. Write \(\eta(x)=P(Y=+1\mid X=x)\). At a fixed \(x\), the two possible classification errors have probabilities \(\eta(x)\) and \(1-\eta(x)\); the smaller of these is the conditional Bayes error.

Definition: The conditional classification regret of a score value \(t\) at \(x\) is \(r(x,t)=P(Y\ne h_t\mid X=x)-\min\{\eta(x),1-\eta(x)\}\), where \(h_t=+1\) if \(t\geq0\) and \(h_t=-1\) otherwise. Equivalently, with \(m(x)=2\eta(x)-1\), it is \(|m(x)|\) if \(h_t\) disagrees with the Bayes label and \(0\) otherwise. At \(\eta(x)=1/2\), it is \(0\) for either prediction.

Thus \(0\leq r(x,t)\leq1\). The population classification regret of \(f\), denoted \(R_{01}(f)-R_{01}^*\), is the expected conditional regret \(E[r(X,f(X))]\). Here \(R_{01}(f)=P(Y\ne h_{f(X)})\), and \(R_{01}^*\) is the risk of a Bayes classifier.

For a margin loss \(\phi:\mathbb{R}\to[0,\infty)\), the loss on an observation is \(\phi(Yf(X))\). Conditional on \(X=x\), the surrogate risk at score \(t\) is

C_{\eta(x)}(t)=\eta(x)\phi(t)+(1-\eta(x))\phi(-t).

Definition: The conditional surrogate excess is \(\delta(x,t)=C_{\eta(x)}(t)-C_{\eta(x)}^*\), where \(C_{\eta(x)}^*=\inf_{u\in\mathbb{R}} C_{\eta(x)}(u)\). The population surrogate excess is \(R_\phi(f)-R_\phi^*\), where \(R_\phi(f)=E[\phi(Yf(X))]\) and \(R_\phi^*=\inf_g R_\phi(g)\), with the infimum over measurable score functions \(g\).

For the population argument, assume \(X\) takes values in a standard Borel space, \(\phi\) is finite, continuous, and nonnegative, and the risks under discussion are finite. These conditions ensure that the conditional risks are measurable and that \(R_\phi^*=E[C_{\eta(X)}^*]\). To see the latter equality, continuity gives \(\inf_{u\in\mathbb{R}}C_{\eta(x)}(u)=\inf_{q\in\mathbb{Q}}C_{\eta(x)}(q)\). The countable infimum is measurable, and for each \(\epsilon>0\) one can measurably choose a rational score whose conditional risk is within \(\epsilon\) of that infimum. Integrating and letting \(\epsilon\) decrease to zero gives the equality. Consequently, \(R_\phi(f)-R_\phi^*=E[\delta(X,f(X))]\).

The Conditional Bound and the Population Theorem

A calibration function supplies a lower bound on conditional surrogate excess in terms of conditional classification regret. For the transfer below, the function must be convex as well as nondecreasing; a constrained-infimum definition alone does not guarantee that the function used in Jensen’s inequality has these properties.

Assumption: Let \(\psi:[0,1]\to[0,\infty)\) be finite, convex, and nondecreasing, with \(\psi(0)=0\). Suppose that for almost every \(x\), and every score \(t\) with finite conditional risk, \(\psi(r(x,t))\leq\delta(x,t)\).

Theorem (population calibration inequality): Under the preceding conditions, every measurable score function \(f\) with finite surrogate risk satisfies \[ \psi\!\left(R_{01}(f)-R_{01}^*\right) \leq R_\phi(f)-R_\phi^*. \]

The pointwise premise applies with \(t=f(x)\) for almost every \(x\). Since \(r(X,f(X))\) lies in \([0,1]\), it is integrable; the assumed finite surrogate excess also makes the right side integrable. Taking expectations in the conditional inequality gives

E\!\left[\psi(r(X,f(X)))\right] \leq E[\delta(X,f(X))] =R_\phi(f)-R_\phi^*.

Jensen’s inequality for the convex function \(\psi\) gives \(\psi(E[r(X,f(X))])\leq E[\psi(r(X,f(X)))]\). Substituting \(E[r(X,f(X))]=R_{01}(f)-R_{01}^*\) proves the claim.

\psi\!\left(R_{01}(f)-R_{01}^*\right) \leq E\!\left[\psi(r(X,f(X)))\right] \leq R_\phi(f)-R_\phi^*.

The first inequality is precisely where convexity enters. Monotonicity is useful when interpreting or inverting the resulting guarantee, but it does not replace convexity in this proof.

Worked Examples

Worked Example: A Two-Stratum Population

Let \(X\) take two values, each with probability \(1/2\). Use squared margin loss \(\phi(u)=(1-u)^2\). In the first stratum, let \(\eta=0.8\) and score \(t=-0.2\); in the second, let \(\eta=0.6\) and score \(t=0.4\). We calculate both population regrets.

For squared margin loss, put \(m=2\eta-1\). Expanding the conditional risk gives \(C_\eta(t)=\eta(1-t)^2+(1-\eta)(1+t)^2=1-2mt+t^2\). Completing the square gives \(C_\eta(t)=1-m^2+(t-m)^2\), so \(C_\eta^*=1-m^2\) and \(\delta=(t-m)^2\).

In the first stratum, \(m=0.6\). The negative score predicts the wrong class, so \(r=0.6\). Its conditional surrogate excess is \((-0.2-0.6)^2=0.64\), which is at least \(r^2=0.36\). In the second stratum, \(m=0.2\). The positive score is correct, so \(r=0\), while the conditional excess is \((0.4-0.2)^2=0.04\).

Therefore, the population classification regret is \((0.6+0)/2=0.3\), and the population surrogate excess is \((0.64+0.04)/2=0.34\). The population inequality with \(\psi(u)=u^2\) reads \(0.3^2=0.09\leq0.34\), as claimed.

Result for squared margin loss: For every \(\eta\in[0,1]\) and score \(t\), the conditional excess satisfies \(\delta\geq r^2\). Indeed, if the prediction is correct then \(r=0\). If it is wrong, \(t\) lies on the opposite side of zero from \(m=2\eta-1\), so \(|t-m|\geq|m|=r\); the identity \(\delta=(t-m)^2\) then proves the bound. At \(m=0\), the regret is zero, so the same inequality holds. Thus \(\psi(u)=u^2\), which is convex and nondecreasing on \([0,1]\), gives \((R_{01}(f)-R_{01}^*)^2\leq R_\phi(f)-R_\phi^*\). \(\square\)

Worked Example: One Stratum With a Wrong Score

Suppose \(X\) is constant, \(\eta=0.75\), and the score is \(t=-0.1\), again with \(\phi(u)=(1-u)^2\). Here \(m=2(0.75)-1=0.5\), so the Bayes label is positive, while the score predicts negative. The conditional classification regret is \(r=0.5\).

The conditional surrogate minimizer is \(m=0.5\), and \(C_\eta^*=1-m^2=0.75\). The score’s excess is \(\delta=(t-m)^2=(-0.1-0.5)^2=0.36\), so \(\psi(r)=r^2=0.25\leq0.36\). Since there is only one stratum, the population quantities equal their conditional counterparts: \(R_{01}(f)-R_{01}^*=0.5\) and \(R_\phi(f)-R_\phi^*=0.36\). This verifies \(0.5^2\leq0.36\).

Worked Example: Unequal Stratum Probabilities

Let \(X\) have three strata with probabilities \(0.2,0.3,0.5\). Their respective \(\eta\) values are \(0.9,0.3,0.6\), and their scores are \(-0.2,-0.1,-0.3\). For squared margin loss, calculate each conditional regret and excess.

The corresponding \(m=2\eta-1\) values are \(0.8,-0.4,0.2\). In the first stratum, the score predicts negative although the Bayes label is positive, so \(r=0.8\) and \(\delta=(-0.2-0.8)^2=1\). In the second, the score predicts the Bayes label, so \(r=0\) and \(\delta=(-0.1-(-0.4))^2=0.09\). In the third, the score predicts negative although the Bayes label is positive, so \(r=0.2\) and \(\delta=(-0.3-0.2)^2=0.25\).

Weighting by the stratum probabilities gives population classification regret \(0.2(0.8)+0.3(0)+0.5(0.2)=0.26\), and population surrogate excess \(0.2(1)+0.3(0.09)+0.5(0.25)=0.352\). Jensen’s intermediate quantity is \(E[r^2]=0.2(0.64)+0.3(0)+0.5(0.04)=0.148\). Thus \(0.26^2=0.0676\leq0.148\leq0.352\), displaying both inequalities in the population proof.

Why the Averaging Step Matters

The conditional bound allows different feature values to have different degrees of difficulty. Some points may be classified correctly and contribute no classification regret, while others near or across the decision boundary contribute more. The population theorem does not require the conditional regrets to be constant. It says that their average cannot escape the surrogate cost when the conditional calibration function is convex.

The direction of Jensen’s inequality is essential: for convex \(\psi\), \(\psi(E[r])\leq E[\psi(r)]\). Reversing this direction would not justify a population guarantee. Nor can one generally substitute a nonconvex constrained-infimum curve into this step; first one needs a convex calibration lower bound that still satisfies the conditional inequality.

Common Mistake

Wrong reasoning: “The conditional inequality holds at every \(x\), so averaging gives \(\psi(E[r])\leq E[\delta]\) directly.” This skips the step connecting the average conditional calibration cost to the calibration cost at the average regret.
Correction: First average the pointwise inequality to obtain \(E[\psi(r)]\leq E[\delta]\). Then apply Jensen’s inequality, using convexity, to obtain \(\psi(E[r])\leq E[\psi(r)]\). Without convexity, that second step is not established.

Key takeaway: A conditional calibration bound becomes a population regret bound by integrating the conditional regrets and excesses, then applying Jensen’s inequality to a convex calibration function. The population guarantee inherits the exact hypotheses that make those steps valid.

Check Your Understanding

Use the definitions and inequalities above to answer these questions.

Why is the conditional classification regret zero when \(\eta(x)=1/2\), regardless of the score?
State the two inequalities that turn a conditional calibration bound into the population calibration inequality.
For squared margin loss, why does a score that predicts the wrong label satisfy \(|t-m|\geq|m|\)?
In the three-stratum example, compute the population classification regret if the first stratum’s probability were changed from \(0.2\) to \(0.4\), with the other probabilities adjusted to keep their relative proportions unchanged.
What role does convexity play in the proof, and why is a pointwise inequality alone insufficient to skip Jensen’s step?