Paired Risk Comparisons with Paired Losses

Why Compare Losses in Pairs?

When two predictors are evaluated on the same observations, each observation supplies a pair of losses. The natural quantity for comparing their performance is the difference within that pair. Keeping the losses paired preserves how they vary together; analyzing each predictor’s empirical risk separately can discard that information.

The aim here is a sampling-error bound for the risk difference of two fixed predictors. The word fixed matters: the predictors must be specified independently of the sample used for evaluation, or the guarantee below does not apply automatically. The comparison is pointwise for this pair, not a guarantee simultaneous over a collection of pairs.

Paired Loss Differences

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations with distribution $F$. Let $h$ and $g$ be two fixed predictors, and let $\ell(h,z)$ denote the loss of predictor $h$ on observation $z$. Assume the losses are measurable and bounded. Define the population risk and empirical risk by

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

For each observation, form the paired loss difference $D_i=\ell(h,Z_i)-\ell(g,Z_i)$. A positive value means $h$ incurs more loss on that observation; a negative value means $h$ incurs less. The same observation is used for both terms.

Definition: The paired loss difference for observation $Z_i$ is $D_i=\ell(h,Z_i)-\ell(g,Z_i)$. Its population mean is $E[D_i]=R(h)-R(g)$, and its empirical mean is $\overline D_n=n^{-1}\sum_{i=1}^n D_i=\widehat R_n(h)-\widehat R_n(g)$. Thus the sampling error in the empirical risk difference is $\overline D_n-E[D_i]$.

This identity follows by subtracting the two empirical averages term by term. It is the key feature of the paired comparison: we can apply a concentration bound directly to the $n$ paired differences. Suppose, more specifically, that $D_i$ lies in a known interval $[c,d]$ with $c<d$. The width $d-c$, rather than the bounds on each loss considered separately, determines the Hoeffding radius.

A Concentration Bound for a Fixed Pair

Hoeffding’s inequality states that for independent random variables $X_i$, each lying almost surely in an interval of width $w_i$, $P(|\sum_i(X_i-E[X_i])|\ge t)\le 2\exp(-2t^2/\sum_i w_i^2)$. Apply it to the paired differences: they are independent because the observations are independent, and each has the same range $[c,d]$.

Theorem: Suppose $h$ and $g$ are fixed independently of the evaluation sample, the $Z_i$ are independent and identically distributed, and $D_i=\ell(h,Z_i)-\ell(g,Z_i)$ lies almost surely in $[c,d]$, where $c<d$. Then, for every $\varepsilon>0$, $$ P\left(\left|\widehat R_n(h)-\widehat R_n(g)-\{R(h)-R(g)\}\right|\ge \varepsilon\right) \le 2\exp\left(-\frac{2n\varepsilon^2}{(d-c)^2}\right). $$

Derivation. By the paired-mean identity, the expression inside the absolute value is $n^{-1}\sum_{i=1}^n(D_i-E[D_i])$. Apply Hoeffding’s inequality with $X_i=D_i$, $w_i=d-c$, and $t=n\varepsilon$. The sum of squared widths is $n(d-c)^2$, so the probability is at most $2\exp\{-2(n\varepsilon)^2/[n(d-c)^2]\}=2\exp\{-2n\varepsilon^2/(d-c)^2\}$, as claimed. $\square$

Equivalently, for any $0<\delta<1$, the sampling error is at most $(d-c)\sqrt{\log(2/\delta)/(2n)}$ with probability at least $1-\delta$. If each loss lies in $[0,M]$, then $D_i\in[-M,M]$, so $d-c=2M$. For losses in $[0,1]$, the resulting two-sided radius is $\sqrt{2\log(2/\delta)/n}$. If a sharper, valid range for the difference is known, use its width instead.

Worked Example: A Binary Classifier Comparison

Suppose two fixed classifiers are evaluated on $n=1000$ independent cases using zero-one loss, which is 1 for an error and 0 for a correct prediction. Let $h$ make errors on 80 cases where $g$ is correct, and be correct on 180 cases where $g$ errs. On the remaining 740 cases, their losses agree.

For the 80 cases, $D_i=1$; for the 180 cases, $D_i=-1$; and for the other cases, $D_i=0$. Therefore, $\overline D_n=(80-180)/1000=-0.10$. This is $\widehat R_n(h)-\widehat R_n(g)$, so the observed empirical error rate for $h$ is 0.10 lower.

Since both losses are in $[0,1]$, the difference lies in $[-1,1]$, an interval of width 2. At confidence level 95%, take $\delta=0.05$. The radius is $\sqrt{2\log(2/0.05)/1000}=\sqrt{2\log(40)/1000}\approx\sqrt{0.007378}\approx0.0859$.

Thus, with probability at least 0.95, the population risk difference lies between $-0.10-0.0859=-0.1859$ and $-0.10+0.0859=-0.0141$. For this fixed pair, the bound places the entire interval below zero, supporting lower population risk for $h$.

Worked Example: Using a Narrower Difference Range

Suppose two fixed predictors have losses in $[0,1]$, but their construction ensures that the difference in their losses always lies in $[-0.2,0.2]$. On $n=200$ observations, suppose 40 paired differences equal $0.2$ and 160 equal $-0.05$. These values can arise, for example, from loss pairs $(0.6,0.4)$ and $(0.35,0.4)$, respectively.

The empirical mean difference is $(40(0.2)+160(-0.05))/200=(8-8)/200=0$. The known interval for each difference has width $0.4$, not 2. At 95% confidence, the paired Hoeffding radius is $0.4\sqrt{\log(40)/(2(200))}=\sqrt{0.16\log(40)/400}\approx\sqrt{0.001476}\approx0.0384$.

The resulting bound is $|R(h)-R(g)|\le 0.0384$ with probability at least 0.95. Using only the separate loss range $[0,1]$ would give a radius of $\sqrt{2\log(40)/200}\approx0.1921$. The narrower paired-difference range is what sharpens the bound; one may use it only when it is guaranteed for every observation, not merely suggested by the sample.

Why Dependence Between the Losses Matters

The two losses on a given observation need not be independent. In fact, their dependence can make their difference much less variable than either loss alone. If the losses have finite variance, the variance identity is

\operatorname{Var}(\ell(h,Z)-\ell(g,Z)) =\operatorname{Var}(\ell(h,Z))+\operatorname{Var}(\ell(g,Z)) -2\operatorname{Cov}(\ell(h,Z),\ell(g,Z)).

To derive it, let $A=\ell(h,Z)$ and $B=\ell(g,Z)$. Expanding the definition of variance gives $\operatorname{Var}(A-B)=E[((A-E[A])-(B-E[B]))^2]$. Expanding the square yields $\operatorname{Var}(A)+\operatorname{Var}(B)-2E[(A-E[A])(B-E[B])]$. The last expectation is $\operatorname{Cov}(A,B)$, proving the identity. $\square$

Positive covariance reduces the variance of the paired difference; negative covariance increases it. This identity explains why comparing losses on the same observations can be informative. It does not replace the bounded-range Hoeffding guarantee above, but it shows what is obscured when the losses are treated as unrelated quantities.

Worked Example: Identical Losses Cancel Exactly

Suppose $h$ and $g$ produce exactly the same loss on every possible observation: $\ell(h,z)=\ell(g,z)$ for all $z$. The common loss may be random and may vary substantially across observations. Nevertheless, every paired difference is $D_i=0$.

Consequently $\widehat R_n(h)-\widehat R_n(g)=0$ and $R(h)-R(g)=0$ for every sample. The difference has the degenerate range $[0,0]$, and its sampling error is exactly zero.

For contrast, separately applying Hoeffding to losses in $[0,1]$ gives a nonzero, conservative uncertainty radius for each risk. To see the consequence, use a union bound with error probability $0.025$ for each risk. Each empirical risk is within $\sqrt{\log(2/0.025)/(2n)}=\sqrt{\log(80)/(2n)}$ of its population risk with probability at least 0.975. Together, the two separate statements imply an error bound for their difference of twice that radius, even though the actual paired difference is identically zero. Pairing retains the exact cancellation.

Common Mistakes and Scope

Ignoring the shared observations. The empirical comparison is the average of $D_i=\ell(h,Z_i)-\ell(g,Z_i)$, not a comparison of two independent samples. Pairing is what preserves the within-observation relationship.
Using an unjustified narrow range. A range such as $[-0.2,0.2]$ must hold for every possible observation under consideration. Observing no larger differences in a finite sample does not prove that range.
Reversing the sign. With the convention $D_i=\ell(h,Z_i)-\ell(g,Z_i)$, a negative empirical difference favors $h$, because lower loss is better.
Applying a fixed-pair bound after data-driven selection. If the same data were used to choose $h$ and $g$, they are not automatically fixed independently of the evaluation sample. The pointwise guarantee cannot simply be asserted for that selected pair.
Claiming a guaranteed improvement from a negative estimate alone. The population difference remains uncertain; compare the full confidence interval with zero. In the binary example, the interval is below zero, while the narrower-range example includes zero.

Key takeaway: For a fixed pair of predictors evaluated on the same independent observations, concentrate the single paired difference $D_i$, not the two loss sequences separately. The Hoeffding radius depends on the range width of $D_i$, and pairing preserves any cancellation between the losses.

Check Your Understanding

Work through these questions using the paired-difference convention in this tutorial.

If $D_i=\ell(h,Z_i)-\ell(g,Z_i)$ has range $[-0.5,0.5]$, what is the interval width used in the Hoeffding bound?
For $n=400$, differences of range width 2, and $\delta=0.05$, write the paired two-sided confidence radius.
Why does a negative empirical difference indicate lower observed risk for $h$?
How does positive covariance between the two losses affect the variance of their difference?
What assumption is needed before applying the fixed-pair bound to two predictors evaluated on a sample?