Model Class Reliance - Outer and Inner Finite-Sample Bounds

Summary

Under three loss-boundedness assumptions, the paper gives two-sided guarantees that empirical MCR estimates population MCR. Theorem 4 (outer): with probability at least $1-\delta$, $MC{R}_{+}(ϵ)\le {\widehat{MCR}}_{+}({ϵ}_{\text{out}})+{\mathcal{Q}}_{\text{out}}$, with ${ϵ}_{\text{out}}=ϵ+2B_{\text{ref}}\sqrt{\log (3{\delta }^{-1})/2n}$. It needs no complexity limit, because complexity enters through the size of $\hat{\mathcal{R}}$. Theorem 5: a covering number $\mathcal{N}(\mathcal{F},r)$ bounds ${\sup }_f|\widehat{MR}-MR|$ uniformly. Theorem 6 (inner): $MC{R}_{+}(ϵ)\ge {\widehat{MCR}}_{+}({ϵ}_{\text{in}})-{\mathcal{Q}}_{\text{in}}$, with a shrunken threshold ${ϵ}_{\text{in}}<ϵ$. If ${\widehat{MCR}}_{\pm }({ϵ}_{\text{in}})\approx {\widehat{MCR}}_{\pm }({ϵ}_{\text{out}})$, then ${\widehat{MCR}}_{\pm }(ϵ)$ is close to its target. The bounds are too wide for practical CIs, so the paper uses the bootstrap in practice.

Overview

These results justify the point estimator $[{\widehat{MCR}}_{-}(ϵ),{\widehat{MCR}}_{+}(ϵ)]$ (§4.1, p. 12). The authors are explicit that the weak assumptions, “typical for statistical-learning-theoretic analysis”, make the implied CIs “impractically large”. They therefore serve to show when empirical MCR is sensible. Sampling variability in §9.1 and §10 is handled with the bootstrap.

Main Content

Assumptions (§4.1, p. 12)

Let $b_{\text{orig}},B_{\text{ind}},B_{\text{ref}},B_{\text{switch}}\in \mathbb{R}$ be known constants. Each assumption is a property of a given $f\in \mathcal{F}$.

Assumptions 1-3: Bounded losses (p. 12)

• Assumption 1 (bounded individual loss): $0\le L(f,(y,x_1,x_2))\le B_{\text{ind}}$ for all $(y,x_1,x_2)\in \mathcal{Y}\times {\mathcal{X}}_1\times {\mathcal{X}}_2$.
• Assumption 2 (bounded relative loss): $|L(f,(y,x_1,x_2))-L(f_{\text{ref}},(y,x_1,x_2))|\le B_{\text{ref}}$ for all $(y,x_1,x_2)\in \mathcal{Z}$.
• Assumption 3 (bounded aggregate loss): $\mathbb{P}\{0<b_{\text{orig}}\le {\hat{e}}_{\text{orig}}(f)\}=\mathbb{P}\{{\hat{e}}_{\text{switch}}(f)\le B_{\text{switch}}\}=1$.

Setting the constants in practice. An unbounded loss such as squared error is allowed if $Y$ and the predictions lie in a known range; see Lemmas 17-18 in Model Class Reliance for Linear and RKHS Model Classes.

• $b_{\text{orig}}$: fit a highly flexible model and take half (or any positive fraction) of its cross-validated loss.
• $B_{\text{switch}}$: set it to $B_{\text{ind}}$, which is conservative. For non-separable binary classification no linear classifier can misclassify every point, so $B_{\text{ind}}>B_{\text{switch}}$.
• $B_{\text{ref}}$: may be set to $B_{\text{ind}}$ if $f_{\text{ref}}$ satisfies Assumption 1.

With difference-based MR, Assumption 3 is not needed.

Theorem 4: outer bounds

Theorem 4: "Outer" MCR bounds (pp. 12-13, Eqs 4.2-4.3)

Given $ϵ\ge 0$, let $f_{+,ϵ}\in \arg {\max }_{\mathcal{R}(ϵ)}MR(f)$ and $f_{-,ϵ}\in \arg {\min }_{\mathcal{R}(ϵ)}MR(f)$. If $f_{+,ϵ}$ and $f_{-,ϵ}$ satisfy Assumptions 1, 2 and 3, then

$$\mathbb{P}(MC{R}_{+}(ϵ)>{\widehat{MCR}}_{+}({ϵ}_{\text{out}})+{\mathcal{Q}}_{\text{out}})\le \delta ,(4.2)$$ $$\mathbb{P}(MC{R}_{-}(ϵ)<{\widehat{MCR}}_{-}({ϵ}_{\text{out}})-{\mathcal{Q}}_{\text{out}})\le \delta ,(4.3)$$

where

$${ϵ}_{\text{out}}:=ϵ+2B_{\text{ref}}\sqrt{\frac{\log (3{\delta }^{-1})}{2n}},{\mathcal{Q}}_{\text{out}}:=\frac{B_{\text{switch}}}{b_{\text{orig}}}-\frac{B_{\text{switch}}-B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{n}}}{b_{\text{orig}}+B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{2n}}}.$$

As $n\to \infty$, ${ϵ}_{\text{out}}\to ϵ$ and ${\mathcal{Q}}_{\text{out}}\to 0$.

Practical reading. If ${\widehat{MCR}}_{+}(ϵ)\approx {\widehat{MCR}}_{+}({ϵ}_{\text{out}})$, the empirical ${\widehat{MCR}}_{+}(ϵ)$ is unlikely to substantially underestimate $MC{R}_{+}(ϵ)$. Symmetrically, ${\widehat{MCR}}_{-}(ϵ)$ is unlikely to substantially overestimate $MC{R}_{-}(ϵ)$.

Implicit complexity control. The bound needs no covering number, Rademacher complexity or VC dimension. A more flexible $\mathcal{F}$ enlarges $\hat{\mathcal{R}}({ϵ}_{\text{out}})$, so the optimized bound widens automatically. This is why it “naturally account[s] for potential overfitting” (p. 13).

Proof of Theorem 4, 4 steps (App B.3, pp. 51-54)

1. Step 1. $\widehat{MR}(f_{+,ϵ})\le {\widehat{MCR}}_{+}({ϵ}_{\text{out}})$ whenever $f_{+,ϵ}\in \hat{\mathcal{R}}({ϵ}_{\text{out}})$. By Lemma 23 with $\delta /3$, that membership fails with probability at most $\delta /3$ (Eqs B.10-B.12).
2. Step 2. On that event, $MR(f_{+,ϵ})\le {\widehat{MCR}}_{+}({ϵ}_{\text{out}})+[MR(f_{+,ϵ})-\widehat{MR}(f_{+,ϵ})]$ (Eq B.13).
3. Step 3. Write ${\mathcal{Q}}_{\text{out}}=q_{\text{ratio}}(B_{\text{ind}}\sqrt{\log (6{\delta }^{-1})/n},B_{\text{ind}}\sqrt{\log (6{\delta }^{-1})/2n})$. By Lemma 24, the error exceeds ${\mathcal{Q}}_{\text{out}}$ only if $|{\hat{e}}_{\text{orig}}-e_{\text{orig}}|$ or $|{\hat{e}}_{\text{switch}}-e_{\text{switch}}|$ exceeds its share. Hoeffding’s bound for U-statistics (Hoeffding 1963, Eq 5.7; Serfling 1980, Thm A p. 201) plus a union bound gives probability at most $2\delta /6+2\delta /6=2\delta /3$ (Eqs B.14-B.16). The same holds with ${\hat{e}}_{\text{divide}}$ in place of ${\hat{e}}_{\text{switch}}$.
4. Step 4. A union bound over Steps 1 and 3 gives $\delta /3+2\delta /3=\delta$. Eq 4.3 follows symmetrically.

The transcribed equations (B.10-B.19, incl. $q(k)=q_{\text{ratio}}(k,k/\sqrt{2})$, the Hoeffding exponents and the difference version without Assumption 3, B.3.3-B.3.4) are in ^proof-thm4-step3.

Supporting lemmas (App B.1-B.2)

Lemma 23: Good population models are in the enlarged empirical Rashomon set (App B.1, p. 49)

For $ϵ\in \mathbb{R}$ and $\delta \in (0,1)$ let ${ϵ}_1^{\prime }:=ϵ+2B_{\text{ref}}\sqrt{\log ({\delta }^{-1})/2n}$, and let $f_1\in \mathcal{R}(ϵ)$ be a specific, possibly unknown model. If $f_1$ satisfies Assumption 2, then $\mathbb{P}\{f_1\in \hat{\mathcal{R}}({ϵ}_1^{\prime })\}\ge 1-\delta$.

Proof. $\tilde{L}(f_1)$ lies in an interval of length $2B_{\text{ref}}$ and $\mathbb{E}\tilde{L}(f_1,Z)\le ϵ$. Hoeffding’s inequality bounds $\mathbb{P}[\hat{\mathbb{E}}\tilde{L}-\mathbb{E}\tilde{L}>2B_{\text{ref}}\sqrt{\log ({\delta }^{-1})/2n}]$ by $\exp \{-2n(\cdot {)}^2/(2B_{\text{ref}}{)}^2\}=\delta$.

Lemma 24: Transforming bounds on losses into bounds on ratios and differences (App B.2, pp. 49-51)

Let $X,Z,{\mu }_X,{\mu }_Z,k_X,k_Z\in \mathbb{R}$ satisfy $|Z-{\mu }_Z|\le k_Z$ and $|X-{\mu }_X|\le k_X$. Then $|(Z-X)-({\mu }_Z-{\mu }_X)|\le q_{\text{difference}}(k_Z,k_X):=k_Z+k_X$ (B.5-B.6). If moreover $0<b_{\text{orig}}\le X,{\mu }_X$ and $Z,{\mu }_Z\le B_{\text{switch}}<\infty$, then

$$|\frac{Z}{X}-\frac{{\mu }_Z}{{\mu }_X}|\le q_{\text{ratio}}(k_Z,k_X):=\frac{B_{\text{switch}}}{b_{\text{orig}}}-\frac{B_{\text{switch}}-k_Z}{b_{\text{orig}}+k_X}.(B.7\text{-}B.8)$$

Proof idea (full derivation with B.9 and all four partial derivatives: ^proof-lem-24). Both ratios lie in $[(A_Z-d_Z)/(a_X+d_X),A_Z/a_X]$, where $A_Z=\max (Z,{\mu }_Z)$, $a_X=\min (X,{\mu }_X)$, $d_Z=|Z-{\mu }_Z|$ and $d_X=|X-{\mu }_X|$. The width of this interval increases in $A_Z$, $d_Z$ and $d_X$ and decreases in $a_X$ (sign of partial derivatives), so it is maximized at the extreme constants.

Covering number and Theorem 5

Definition: $r$-margin-expectation-cover and covering number (Eq 4.4, p. 14)

A set of functions ${\mathcal{G}}_r$ is an $r$-margin-expectation-cover if for any $f\in \mathcal{F}$ and any distribution $D$ there is $g\in {\mathcal{G}}_r$ with

$${\mathbb{E}}_{Z\sim D}|L(f,Z)-L(g,Z)|\le r.(4.4)$$

The covering number $\mathcal{N}(\mathcal{F},r)$ is the size of the smallest such cover. Probabilities and expectations are with respect to the population unless subscripted, e.g. ${\mathbb{P}}_D$, ${\mathbb{E}}_{V\sim D}$.

Theorem 5: Uniform bound for $\widehat{MR}$ (p. 14, Eq 4.5)

Given $r>0$, if Assumptions 1 and 3 hold for all $f\in \mathcal{F}$, then

$$\mathbb{P}\left[\underset{f\in \mathcal{F}}{\sup }\right|\widehat{MR}(f)-MR(f)|>q(\delta ,r,n)]\le \delta ,$$ $$q(\delta ,r,n):=\frac{B_{\text{switch}}}{b_{\text{orig}}}-\frac{B_{\text{switch}}-\{B_{\text{ind}}\sqrt{\frac{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))}{n}}+2r\sqrt{2}\}}{b_{\text{orig}}+\{B_{\text{ind}}\sqrt{\frac{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r\}}.(4.5)$$

The bound can be made arbitrarily small by increasing $n$ and decreasing $r$. So a model can be trained and have its reliance estimated on the same data, without sample splitting.

Theorem 25: Uniform deviation bounds via covering number (App B.5.1, p. 55)

If Assumptions 1, 2 and 3 hold for all $f\in \mathcal{F}$, then for any $r>0$:

$${\mathbb{P}}_D[\underset{f}{\sup }|{\hat{e}}_{\text{orig}}(f)-e_{\text{orig}}(f)|>B_{\text{ind}}\sqrt{\frac{\log (2{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r]\le \delta (B.22)$$ $${\mathbb{P}}_D[\underset{f}{\sup }|\hat{\mathbb{E}}\tilde{L}(f,Z)-\mathbb{E}\tilde{L}(f,Z)|>2B_{\text{ref}}\sqrt{\frac{\log (2{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r]\le \delta (B.23)$$ $${\mathbb{P}}_D[\underset{f}{\sup }|{\hat{e}}_{\text{switch}}(f)-e_{\text{switch}}(f)|>B_{\text{ind}}\sqrt{\frac{\log (2{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{n}}+2r]\le \delta (B.24)$$ $$\mathbb{P}[\underset{f}{\sup }\text{|ratio error|}>{\mathcal{Q}}_4]\le \delta ,{\mathbb{P}}_D[\underset{f}{\sup }|\{{\hat{e}}_{\text{switch}}-{\hat{e}}_{\text{orig}}\}-\{e_{\text{switch}}-e_{\text{orig}}\}|>{\mathcal{Q}}_{4,\text{difference}}]\le \delta (B.25\text{-}B.26)$$

with ${\mathcal{Q}}_4:=q_{\text{ratio}}(B_{\text{ind}}\sqrt{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))/n}+2r\sqrt{2},B_{\text{ind}}\sqrt{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r))/2n}+2r)$, and ${\mathcal{Q}}_{4,\text{difference}}$ the same with $q_{\text{difference}}$ (B.27-B.28). B.26 does not need Assumption 3. (Eq B.25 is printed with the ratio ${\hat{e}}_{\text{orig}}/{\hat{e}}_{\text{switch}}$. Theorem 5, the ratio ${\hat{e}}_{\text{switch}}/{\hat{e}}_{\text{orig}}$, “follows directly” from it.)

Proof idea for B.22 (App B.5.2). Let $D^{\star }$ be the uniform mixture of the population $D_p$ and the sample distribution $D_s$. For any $f$ pick $g\in {\mathcal{G}}_r$ with ${\mathbb{E}}_{D^{\star }}|L(g)-L(f)|\le r$. Then $|\hat{\mathbb{E}}L(f)-\mathbb{E}L(f)|\le |\hat{\mathbb{E}}L(g)-\mathbb{E}L(g)|+2r$. A union bound over the $\mathcal{N}(\mathcal{F},r)$ cover elements and Hoeffding’s inequality finish the proof. This is why the cover must work for any distribution: the cover is chosen against a data-dependent mixture.

Where $r\sqrt{2}$ comes from. B.24 itself is stated with $\mathcal{N}(\mathcal{F},r)$ and $+2r$. The $r\sqrt{2}$ appears only when B.24 is plugged into the ratio bound (Eq B.36) at level $\delta /2$ with radius $r\sqrt{2}$. The source gives no further justification for that radius. Full proofs of B.22-B.26 (incl. the switched distributions ${\tilde{D}}_p$, ${\tilde{D}}_s$, ${\tilde{D}}^{\star }$ and Hoeffding’s U-statistic bound in B.34): ^proof-b24.

Theorem 6: inner bounds

Theorem 6: "Inner" MCR bounds (p. 15, Eqs 4.6-4.7)

Given $ϵ\ge 0$ and $r>0$, if Assumptions 1, 2 and 3 hold for all $f\in \mathcal{F}$, then

$$\mathbb{P}(MC{R}_{+}(ϵ)<{\widehat{MCR}}_{+}({ϵ}_{\text{in}})-{\mathcal{Q}}_{\text{in}})\le \delta ,(4.6)$$ $$\mathbb{P}(MC{R}_{-}(ϵ)>{\widehat{MCR}}_{-}({ϵ}_{\text{in}})+{\mathcal{Q}}_{\text{in}})\le \delta ,(4.7)$$ $${ϵ}_{\text{in}}:=ϵ-2B_{\text{ref}}\sqrt{\frac{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}-2r,{\mathcal{Q}}_{\text{in}}:=q\left(\frac{\delta }{2},r,n\right)\text{(Eq 4.5)}.$$

This gives an interval inside $[MC{R}_{-}(ϵ),MC{R}_{+}(ϵ)]$ with high probability. The source (p. 15) says: if ${\widehat{MCR}}_{+}({ϵ}_{\text{in}})\approx {\widehat{MCR}}_{+}(ϵ)$, the estimator is “unlikely … to substantially underestimate” $MC{R}_{+}(ϵ)$.

Likely typo in the source: "underestimate" should be "overestimate" lower bound on $MC{R}_{+}(ϵ)$: with high probability $MC{R}_{+}(ϵ)\ge {\widehat{MCR}}_{+}({ϵ}_{\text{in}})-{\mathcal{Q}}_{\text{in}}\approx {\widehat{MCR}}_{+}(ϵ)-{\mathcal{Q}}_{\text{in}}$. What follows logically is that ${\widehat{MCR}}_{+}(ϵ)$ is unlikely to substantially overestimate $MC{R}_{+}(ϵ)$. Underestimation is ruled out by Theorem 4 (Eq 4.2), not Theorem 6. The source's very next sentence, which combines the two theorems to rule out both errors, is consistent with this reading. The theorem statement also contains a stray "and then" before the displayed equations.

Eq 4.6 is a

Combined with Theorem 4: if ${\widehat{MCR}}_{+}({ϵ}_{\text{in}})\approx {\widehat{MCR}}_{+}({ϵ}_{\text{out}})$, then ${\widehat{MCR}}_{+}(ϵ)$ neither over- nor underestimates by much. This is plausible in large samples, since ${ϵ}_{\text{in}},{ϵ}_{\text{out}}\to ϵ$.

Why the inner bound needs complexity control (pp. 13-14). Theorem 4 does not say whether the outer bounds are attained or whether the estimated range is needlessly wide. The models that drive ${\widehat{MCR}}_{+}(ϵ)$ might fit well in-sample only through overfitting, so they are not truly in $\mathcal{R}(ϵ)$. Or they might be truly good but have the largest MR estimation error. A covering number controls both worst cases.

Proof sketch of Theorem 6 (App B.5.7, pp. 59-61)

Compressed here; every intermediate inequality (B.38-B.45, incl. the $\delta /2$-level rewrite ${\mathcal{Q}}_{\text{in}}=q_{\text{ratio}}(\cdots \log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))\cdots )$ in B.42, Eq 4.7 and the difference version) is in ^proof-thm6-46. Let $E$ be the event that some ${\hat{f}}_{+,{ϵ}_{\text{in}}}\in \arg {\max }_{\hat{\mathcal{R}}({ϵ}_{\text{in}})}\widehat{MR}$ has $MR>MC{R}_{+}(ϵ)$. That requires some $f\in \hat{\mathcal{R}}({ϵ}_{\text{in}})\setminus \{f_{\text{ref}}\}$ with $\mathbb{E}\tilde{L}>ϵ$ but $\hat{\mathbb{E}}\tilde{L}\le {ϵ}_{\text{in}}$, i.e. a uniform deviation of at least $2B_{\text{ref}}\sqrt{\log (4{\delta }^{-1}\mathcal{N})/2n}+2r$. By Theorem 25 (B.23 at $\delta /2$) this has probability at most $\delta /2$ (Eqs B.38-B.40). Off $E$, $MC{R}_{+}(ϵ)<{\widehat{MCR}}_{+}({ϵ}_{\text{in}})-{\mathcal{Q}}_{\text{in}}$ requires ${\sup }_f|\widehat{MR}-MR|>{\mathcal{Q}}_{\text{in}}$, which has probability at most $\delta /2$ by Theorem 5 at $\delta /2$. The union bound gives $\delta$ (Eq B.43).

Figure 3 (p. 16): Terms in Theorems 4 and 6

The axes are empirical MR (x) and empirical loss (y). A dashed curve traces, for each MR value, the lowest empirical loss attainable in $\mathcal{F}$, and $f_{\text{ref}}$ is a black point. Horizontal lines mark ${\hat{e}}_{\text{orig}}(f_{\text{ref}})+{ϵ}_{\text{in}}$, $+ϵ$ and $+{ϵ}_{\text{out}}$.

• Blue (Thm 4): expand to ${ϵ}_{\text{out}}$ so that $f_{\pm ,ϵ}$ is captured, then widen by ${\mathcal{Q}}_{\text{out}}$.
• Purple (Thm 6): shrink to ${ϵ}_{\text{in}}$ so that bad models are excluded, then narrow by ${\mathcal{Q}}_{\text{in}}$.

A secondary x-axis shows that ${\widehat{MCR}}_{-}(ϵ)$ and ${\widehat{MCR}}_{+}(ϵ)$ always lie between the inner and outer brackets.

Best-in-class corollary (App A.4)

Corollary 22: Bound on best-in-class MR (App A.4, p. 45)

Let $f^{\star }\in \arg {\min }_{f\in \mathcal{F}}{e}_{\text{orig}}(f)$, with $f_{\pm ,ϵ}$ as in Theorem 4. If $f_{+,ϵ}$ and $f_{-,ϵ}$ satisfy Assumptions 1, 2 and 3, then

$$\mathbb{P}\{MR(f^{\star })\in [{\widehat{MCR}}_{-}({ϵ}_{\text{best}})-{\mathcal{Q}}_{\text{best}},{\widehat{MCR}}_{+}({ϵ}_{\text{best}})+{\mathcal{Q}}_{\text{best}}\left]\right\}\ge 1-\delta ,$$ $${ϵ}_{\text{best}}:=2B_{\text{ref}}\sqrt{\frac{\log (6{\delta }^{-1})}{2n}},{\mathcal{Q}}_{\text{best}}:=\frac{B_{\text{switch}}}{b_{\text{orig}}}-\frac{B_{\text{switch}}-B_{\text{ind}}\sqrt{\frac{\log (12{\delta }^{-1})}{n}}}{b_{\text{orig}}+B_{\text{ind}}\sqrt{\frac{\log (12{\delta }^{-1})}{2n}}}.$$

Uniqueness of $f^{\star }$ is not required; the bounds hold simultaneously for all minimizers. If $E(Y\mid X_1,X_2)=f^{\star }$, this bounds the reliance of the true regression function, which Proposition 19 turns into a causal statement (^thm-prop19).

Proof (App B.4, p. 54). Apply Theorem 4 with $ϵ=0$ and $\delta /2$ to each side, since $MR(f^{\star })\in [MC{R}_{-}(0),MC{R}_{+}(0)]$, and take a union bound.

Difference-based versions (App A.5)

Error terms for $M{R}_{\text{difference}}$ (App A.5, p. 46)

With $M{R}_{\text{difference}}=e_{\text{switch}}-e_{\text{orig}}$, Theorems 4 and 6 and Corollary 22 hold without Assumption 3, using

$${\mathcal{Q}}_{\text{out,difference}}:=(1+\frac{1}{\sqrt{2}})\sqrt{\frac{\log (6{\delta }^{-1})}{n}}{B}_{\text{ind}},{\mathcal{Q}}_{\text{best,difference}}:=(1+\frac{1}{\sqrt{2}})\sqrt{\frac{\log (12{\delta }^{-1})}{n}}{B}_{\text{ind}},$$ $${\mathcal{Q}}_{\text{in,difference}}:=B_{\text{ind}}\{\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))}{n}}+\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}\}+2r(\sqrt{2}+1).$$

$b_{\text{orig}}$ and $B_{\text{switch}}$ disappear.

Uniform bound for $M{R}_{\text{difference}}$ (Theorem 5 analogue). Proved as Eq B.26 of Theorem 25 (App B.5.1, B.5.6): ${\mathbb{P}}_D[{\sup }_f|\{{\hat{e}}_{\text{switch}}-{\hat{e}}_{\text{orig}}\}-\{e_{\text{switch}}-e_{\text{orig}}\}|>{\mathcal{Q}}_{4,\text{difference}}]\le \delta$, with ${\mathcal{Q}}_{4,\text{difference}}=q_{\text{difference}}(B_{\text{ind}}\sqrt{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))/n}+2r\sqrt{2},B_{\text{ind}}\sqrt{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r))/2n}+2r)$, again without Assumption 3.

Why the difference is easier (App A.5, p. 45). The mean, variance and asymptotic distribution of ${\widehat{MR}}_{\text{difference}}$ follow directly from U-statistic results, without the delta method (citing Dorfman 1938 and Lehmann & Casella 2006 for the delta method; see also Ver Hoef 2012). Difference estimates are also more stable when ${\min }_f{e}_{\text{orig}}(f)$ is small, and can be normalized by $\mathrm{Var}(Y)$ (as in Williamson et al. 2017) for interpretability.

Examples

How large are the terms? (illustrative arithmetic, not from the paper)

Take squared error with $Y\in [0,1]$ and predictions in $[0,1]$, so $B_{\text{ind}}=B_{\text{ref}}=B_{\text{switch}}=1$. Take $b_{\text{orig}}=0.05$, $\delta =0.05$ and $n=10,000$. Then ${ϵ}_{\text{out}}-ϵ=2\sqrt{\log (60)/20000}\approx 0.029$, a loss buffer of about 0.03 on a 0-1 scale. ${\mathcal{Q}}_{\text{out}}=20-(1-0.022)/(0.05+0.015)\approx 20-14.9\approx 5.1$, an MR error of about 5. That is useless as a CI, which is why the authors present these as consistency arguments and bootstrap in practice. The ratio form with a small $b_{\text{orig}}$ is especially loose, one motivation for the difference version.

Connections

• The structure (enlarge the empirical set to catch the population optimizer, shrink it to exclude bad models) is the same logic as profile-likelihood and Rashomon-set CIs (Rashomon-Set Confidence Intervals and Profile Likelihood).
• The covering-number argument is a uniform law of large numbers. Overfitting control of this kind is the theory behind Model Selection and Overfitting and Overfitting and Information Criteria.
• Finite-sample, distribution-free guarantees with a similar flavor (Hoeffding, union bounds) underpin split conformal prediction (Split Conformal Prediction and the Coverage Guarantee). There, though, the guarantee is tight rather than conservative.

See Also

• Model Class Reliance - Appendix B Proofs of the Finite-Sample Bounds: full proofs of Lemma 24, Theorems 4, 25, 6 and Corollary 22
• Rashomon Sets and Model Class Reliance - Definitions
• Model Class Reliance - Toy Example and Bootstrap Coverage Simulations: bootstrap used in place of these bounds
• Fisher Rudin Dominici 2019 - Model Class Reliance - Overview