Candidate Risk Gaps And Selection Diagnostics

Why Compare Candidates Pairwise?

A finite selection rule chooses among candidate predictors using their empirical risks. Its decision depends not on whether each empirical risk is individually close to its population value, but on whether the difference between two empirical risks has the correct sign. A candidate with larger population risk can still look better on a particular sample. Concentration of the paired risk difference quantifies how likely that reversal is.

The population risk gap matters: a candidate whose risk is only slightly worse than the best risk is harder to distinguish than one with a large disadvantage. The bounds below make this relationship explicit. They concern the probability of selecting a suboptimal candidate, rather than an expected excess-risk guarantee.

Paired Risks and Population Gaps

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$. There are $M$ fixed candidate predictors $f_1,\ldots,f_M$, and a measurable loss $\ell(f,Z)$ taking values in $[0,1]$. The candidates are fixed independently of the observations used for selection. Define the population and empirical risks by

R_j=E[\ell(f_j,Z)],\qquad \widehat R_j=\frac{1}{n}\sum_{i=1}^n \ell(f_j,Z_i).

Choose an index $j_0$ with minimum population risk, so $R_{j_0}=\min_{1\leq j\leq M}R_j$. For another candidate $j$, its population risk gap relative to this comparator is $\Delta_j=R_j-R_{j_0}$. It is suboptimal when $\Delta_j>0$. The paired loss difference on observation $Z_i$ is

D_{j,i}=\ell(f_j,Z_i)-\ell(f_{j_0},Z_i).

Then $D_{j,i}\in[-1,1]$, $E[D_{j,i}]=\Delta_j$, and $\widehat R_j-\widehat R_{j_0}=n^{-1}\sum_{i=1}^n D_{j,i}$. The two losses in a difference are evaluated on the same observation. This pairing is important: it preserves any dependence between the candidates’ losses rather than treating them as independent measurements.

Definition: The population risk gap of candidate $j$ relative to a population-risk minimizer $j_0$ is $\Delta_j=R_j-R_{j_0}$. The paired empirical risk difference is $\widehat R_j-\widehat R_{j_0}$. A suboptimal candidate appears to beat $j_0$ on the sample when this difference is nonpositive.

Worked Example: An Exact Paired-Comparison Probability

Suppose two candidates, A and B, have losses that are opposite on every observation: with probability $0.6$, candidate A has loss 0 and B has loss 1; with probability $0.4$, A has loss 1 and B has loss 0. The loss is bounded in $[0,1]$, as required.

The risks are $R_A=0(0.6)+1(0.4)=0.4$ and $R_B=1(0.6)+0(0.4)=0.6$. Thus A is the population-risk minimizer and the gap for B is $\Delta_B=0.2$. The paired difference $D_i=\ell(B,Z_i)-\ell(A,Z_i)$ is $1$ with probability $0.6$ and $-1$ with probability $0.4$, so $E[D_i]=0.6-0.4=0.2$.

For $n=5$, let $K$ be the number of observations on which $D_i=1$. Then $K\sim\operatorname{Binomial}(5,0.6)$, and B’s empirical risk is no greater than A’s exactly when $2K-5\leq0$, or $K\leq2$. Therefore

P(\widehat R_B\leq\widehat R_A) =\binom50(0.6)^0(0.4)^5 +\binom51(0.6)(0.4)^4 +\binom52(0.6)^2(0.4)^3 =0.01024+0.0768+0.2304=0.31744.

The probability of this mistaken empirical ordering is about $0.317$. The general Hoeffding bound derived below is $e^{-5(0.2)^2/2}=e^{-0.1}\approx0.90484$, which is valid but conservative. This example also shows why a positive population gap does not make empirical reversal impossible.

A Pairwise Concentration Bound

The central step is to control a single suboptimal candidate’s chance of appearing at least as good as $j_0$. We use Hoeffding’s lemma: if $Y$ is a bounded random variable in an interval $[a,b]$, then for every real $t$,

E\!\left[e^{t(Y-E[Y])}\right]\leq \exp\!\left(\frac{t^2(b-a)^2}{8}\right).

For completeness, this inequality follows by writing $\psi(t)=\log E[e^{t(Y-E[Y])}]$. Boundedness permits differentiation under the expectation, and $\psi''(t)$ is the variance under the exponentially tilted distribution. Any random variable $V\in[a,b]$ has variance at most $(b-a)^2/4$: since $(V-a)(b-V)\geq0$, $E[V^2]\leq(a+b)E[V]-ab$, so $\operatorname{Var}(V)\leq(E[V]-a)(b-E[V])\leq(b-a)^2/4$. The tilted distribution is still supported on $[a,b]$, so $\psi''(t)\leq(b-a)^2/4$. Since $\psi(0)=\psi'(0)=0$, the integral form of Taylor’s formula gives $\psi(t)=t^2\int_0^1(1-s)\psi''(st)\,ds\leq t^2(b-a)^2/8$, as claimed.

Theorem: Under the fixed-candidate, iid, bounded-loss setup above, every candidate $j$ with $\Delta_j>0$ satisfies $$ P(\widehat R_j\leq\widehat R_{j_0})\leq \exp\!\left(-\frac{n\Delta_j^2}{2}\right). $$

Proof. Let $D_i=D_{j,i}$, so the $D_i$ are iid, have mean $\Delta_j$, and lie in an interval of length 2. The event of interest is

\sum_{i=1}^n(D_i-\Delta_j)\leq -n\Delta_j.

Apply the exponential Markov inequality to the negative of this sum. For any $t>0$, independence and Hoeffding’s lemma give

P\!\left(\sum_{i=1}^n(D_i-\Delta_j)\leq-n\Delta_j\right) \leq e^{-tn\Delta_j} \prod_{i=1}^n E[e^{-t(D_i-\Delta_j)}] \leq \exp\!\left(-tn\Delta_j+\frac{nt^2}{2}\right).

The final inequality uses $(b-a)^2/8=4/8=1/2$. Choosing $t=\Delta_j$, which is positive by assumption, makes the exponent $-n\Delta_j^2/2$. This proves the bound. $\square$

Worked Example: A Pairwise Bound at a Specified Gap

Suppose two candidates have risks $R_A=0.25$ and $R_B=0.25+\sqrt{7.554/42}$, with bounded losses and $n=42$ iid observations. The gap is $\Delta_B=\sqrt{7.554/42}\approx0.4241$, so B is suboptimal. If a selection rule chooses B over A, then $\widehat R_B\leq\widehat R_A$. The theorem gives

P(\widehat R_B\leq\widehat R_A) \leq \exp\!\left(-\frac{42}{2}\frac{7.554}{42}\right) =e^{-3.777}\approx0.02289.

Thus the pairwise probability of this empirical reversal is at most about $2.29\%$. The bound is not the probability itself: it is a guaranteed upper limit, and the actual probability may be smaller.

From One Comparison to Finite Selection

Let $\hat j$ be an empirical risk minimizer, meaning that $\widehat R_{\hat j}=\min_{1\leq j\leq M}\widehat R_j$. Any fixed tie-breaking rule is allowed. If $\hat j$ is suboptimal, then $\Delta_{\hat j}>0$ and $\widehat R_{\hat j}\leq\widehat R_{j_0}$. Consequently, selecting any suboptimal candidate requires at least one pairwise reversal against $j_0$.

Theorem: Under the same assumptions, $$ P(\Delta_{\hat j}>0) \leq \sum_{j:\,\Delta_j>0}\exp\!\left(-\frac{n\Delta_j^2}{2}\right). $$ In particular, if every suboptimal candidate has gap at least $\delta>0$, then $$ P(\Delta_{\hat j}>0)\leq \min\!\left\{1,(M-1)\exp\!\left(-\frac{n\delta^2}{2}\right)\right\}. $$

Proof. If $\Delta_{\hat j}>0$, the selected candidate $j=\hat j$ belongs to the set of suboptimal indices and satisfies $\widehat R_j\leq\widehat R_{j_0}$. Hence the event $\{\Delta_{\hat j}>0\}$ is contained in the union of events $\{\widehat R_j\leq\widehat R_{j_0}\}$ over suboptimal $j$. The union bound and the pairwise theorem give the first inequality. If every such gap is at least $\delta$, each summand is at most $e^{-n\delta^2/2}$, and there are at most $M-1$ suboptimal candidates. A probability is also at most 1, yielding the displayed minimum. The comparisons may be dependent; the union bound does not require their independence. $\square$

The gap-specific sum is often more informative than the uniform-gap version. Candidates with large gaps contribute exponentially little, while candidates near the minimum risk can dominate the bound. This is a diagnostic interpretation: it identifies which competitors make selection difficult, rather than assigning the same penalty to every candidate.

Worked Example: Which Risk Gaps Dominate?

Suppose there are three candidates, with one population minimizer and two suboptimal candidates. Let $n=100$, and suppose their gaps are $\Delta_1=0.1$ and $\Delta_2=0.3$. The pairwise exponents are

\frac{n\Delta_1^2}{2}=\frac{100(0.01)}{2}=0.5,\qquad \frac{n\Delta_2^2}{2}=\frac{100(0.09)}{2}=4.5.

The finite-selection bound is therefore

P(\text{suboptimal selection}) \leq e^{-0.5}+e^{-4.5} \approx0.60653+0.01111=0.61764.

The candidate with gap $0.1$ supplies nearly all of this bound. The larger-gap candidate contributes only about $0.01111$. This bound is loose overall, but it correctly signals which candidate is the more plausible source of empirical misselection.

Interpretation and Common Pitfalls

For a fixed positive gap, the pairwise upper bound decreases exponentially in $n$, with exponent proportional to the squared gap. For fixed $n$, a larger gap is easier to distinguish. The finite-class bound also reflects the number of suboptimal candidates: adding more candidates adds more possible pairwise reversals. This is a union-bound cost, not a claim that all comparisons are independent.

A common mistake is to interpret $P(\Delta_{\hat j}>0)$ as an expected risk excess. They are different quantities. The first asks whether the selected index has strictly larger population risk than the minimum; the second would average a numerical risk difference. A small probability of a wrong choice does not by itself specify how costly that choice would be. Conversely, a wrong choice can have a very small gap. This tutorial’s bounds address the former question.

Another pitfall is to compare each candidate’s empirical risk to its population risk as if the two candidate losses were independent. The relevant random variable is their paired difference on the same observation. Its mean is the population gap, and its range is $[-1,1]$. The proof uses the observations’ independence across $i$, not independence between candidates’ losses. Finally, when a suboptimal candidate ties the comparator empirically, it is included in the event $\widehat R_j\leq\widehat R_{j_0}$; this makes the bound valid regardless of how empirical ties are broken.

Key takeaway: For bounded losses and fixed candidates, a suboptimal candidate with risk gap $\Delta_j$ beats a population minimizer empirically with probability at most $e^{-n\Delta_j^2/2}$. A union bound turns these pairwise diagnostics into a bound for finite empirical risk minimization.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

Why is the paired difference $D_{j,i}$ in an interval of length 2 when each loss lies in $[0,1]$?
If a candidate has gap $\Delta>0$, what event must occur for its empirical risk to be no greater than the empirical risk of a population minimizer?
For fixed $n$, how does the pairwise Hoeffding bound change when the gap is doubled?
Why does the finite-class union bound not require independence among the pairwise comparison events?
Explain why the probability of selecting a suboptimal candidate is not the same quantity as expected excess risk.