Model Class Reliance - Appendix B Proofs of the Finite-Sample Bounds

Summary

Full derivations behind the statistical results in Model Class Reliance - Outer and Inner Finite-Sample Bounds. Lemma 24 turns bounds on two losses into bounds on their ratio or difference. Theorem 4 (outer bound) follows in four steps: Lemma 23 (Hoeffding) puts the population optimizer into the enlarged empirical Rashomon set; then Lemma 24 plus Hoeffding’s bound for U-statistics controls the MR estimation error at that one model; a $\delta /3+2\delta /3$ union bound finishes. Theorem 25 gives uniform deviations over $\mathcal{F}$ through a cover chosen against a data-dependent mixture distribution, which is why the covering number must hold for any distribution. Theorem 6 (inner bound) combines Theorem 25 twice at level $\delta /2$. The difference-based variants drop Assumption 3 throughout.

Overview

Notation: $\tilde{L}(f,z)=L(f,z)-L(f_{\text{ref}},z)$; $\hat{\mathbb{E}}$ is the sample average; ${\mathcal{G}}_r$ is an $r$-margin-expectation-cover of size $\mathcal{N}(\mathcal{F},r)$ (Eq 4.4); $f_{\pm ,ϵ}$ are the population maximizer/minimizer of MR over $\mathcal{R}(ϵ)$. The functions

$$q_{\text{difference}}(k_Z,k_X)=k_Z+k_X,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}$$

are from Lemma 24. Two concentration tools recur:

• Hoeffding’s inequality (Hoeffding 1963, Thm 2) for the iid average ${\hat{e}}_{\text{orig}}$: exponent $-2n{t}^2/(\text{range}{)}^2$.
• Hoeffding’s bound for U-statistics (Hoeffding 1963, Eq 5.7; Serfling 1980, Thm A p. 201) for the order-2 U-statistic ${\hat{e}}_{\text{switch}}$ (and ${\hat{e}}_{\text{divide}}$): exponent $-n{t}^2/(\text{range}{)}^2$, half as strong, which is why every ${\hat{e}}_{\text{switch}}$ term has $\log (\cdot )/n$ where the ${\hat{e}}_{\text{orig}}$ term has $\log (\cdot )/2n$.

Main Content

B.2 Proof of Lemma 24 (pp. 49-51)

Proof of Lemma 24: from loss bounds to ratio and difference bounds

Difference (B.5-B.6). $|(Z-X)-({\mu }_Z-{\mu }_X)|\le |Z-{\mu }_Z|+|{\mu }_X-X|\le k_Z+k_X$.

Ratio (B.7-B.9). Let $A_Z=\max (Z,{\mu }_Z)$, $a_X=\min (X,{\mu }_X)$, $d_Z=|Z-{\mu }_Z|$, $d_X=|X-{\mu }_X|$. Then $\max (X,{\mu }_X)=a_X+d_X$ and $\min (Z,{\mu }_Z)=A_Z-d_Z$, so both $Z/X$ and ${\mu }_Z/{\mu }_X$ lie in

$$[\frac{\min (Z,{\mu }_Z)}{\max (X,{\mu }_X)},\frac{\max (Z,{\mu }_Z)}{\min (X,{\mu }_X)}]=[\frac{A_Z-d_Z}{a_X+d_X},\frac{A_Z}{a_X}],\text{hence}|\frac{Z}{X}-\frac{{\mu }_Z}{{\mu }_X}|\le \frac{A_Z}{a_X}-\frac{A_Z-d_Z}{a_X+d_X}.(B.9)$$

Partial derivatives of the right side of B.9:

$$\frac{\partial }{\partial a_X}=-\frac{A_Z}{a_X^2}+\frac{A_Z-d_Z}{(a_X+d_X{)}^2}\le 0,\frac{\partial }{\partial A_Z}=\frac{1}{a_X}-\frac{1}{a_X+d_X}\ge 0,\frac{\partial }{\partial d_X}=\frac{A_Z-d_Z}{(a_X+d_X{)}^2}>0,\frac{\partial }{\partial d_Z}=\frac{1}{a_X+d_X}>0.$$

So the bound is largest when $d_Z,d_X,A_Z$ are as large as possible and $a_X$ as small as possible. Under $d_Z\le k_Z$, $d_X\le k_X$, $a_X\ge b_{\text{orig}}>0$ and $A_Z\le B_{\text{switch}}$, this gives $q_{\text{ratio}}(k_Z,k_X)$.

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

Step 1 (B.3.1, Eqs B.10-B.12): $\mathbb{P}[\widehat{MR}(f_{+,ϵ})\le {\widehat{MCR}}_{+}({ϵ}_{\text{out}})]\ge 1-\delta /3$

The event $\widehat{MR}(f_{+,ϵ})\le {\widehat{MCR}}_{+}({ϵ}_{\text{out}})$ (B.10) always holds if $f_{+,ϵ}\in \hat{\mathcal{R}}({ϵ}_{\text{out}})$, because ${\widehat{MCR}}_{+}({ϵ}_{\text{out}})$ is the maximum empirical MR over that set. So

$$\mathbb{P}[\widehat{MR}(f_{+,ϵ})>{\widehat{MCR}}_{+}({ϵ}_{\text{out}})]\le \mathbb{P}[f_{+,ϵ}\notin \hat{\mathcal{R}}({ϵ}_{\text{out}})]\le \delta /3,(B.11\text{-}B.12)$$

by Lemma 23 at level $\delta /3$ (that is where $\log (3{\delta }^{-1})$ in ${ϵ}_{\text{out}}$ comes from).

Step 2 (B.3.2, Eq B.13): deterministic decomposition

When B.10 holds, adding and subtracting $MR(f_{+,ϵ})$:

$$MR(f_{+,ϵ})\le {\widehat{MCR}}_{+}({ϵ}_{\text{out}})+[MR(f_{+,ϵ})-\widehat{MR}(f_{+,ϵ})].(B.13)$$

Step 3 (B.3.3, Eqs B.14-B.16): the bracketed error exceeds ${\mathcal{Q}}_{\text{out}}$ with probability at most $2\delta /3$

Define $q(k):=q_{\text{ratio}}(k,k/\sqrt{2})$. Then

$${\mathcal{Q}}_{\text{out}}=q_{\text{ratio}}(B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{n}},B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{2n}})=q\left(B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{n}}\right).$$

The chain (B.14-B.16):

$$\mathbb{P}[MR(f_{+,ϵ})-\widehat{MR}(f_{+,ϵ})>{\mathcal{Q}}_{\text{out}}]$$ $$\le \mathbb{P}\left[\right\{|{\hat{e}}_{\text{orig}}-e_{\text{orig}}|>B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{2n}}\}\cup \{|{\hat{e}}_{\text{switch}}-e_{\text{switch}}|>B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{n}}\left\}\right]\text{(Lemma 24)}$$ $$\le 2\exp \{-\frac{2n}{B_{\text{ind}}^2}{B}_{\text{ind}}^2\frac{\log (6{\delta }^{-1})}{2n}\}+2\exp \{-\frac{n}{B_{\text{ind}}^2}{B}_{\text{ind}}^2\frac{\log (6{\delta }^{-1})}{n}\}=\frac{2\delta }{6}+\frac{2\delta }{6}=\frac{2\delta }{3},$$

using a union bound and Hoeffding’s bound for U-statistics (all evaluated at the fixed model $f_{+,ϵ}$). Both ${\hat{e}}_{\text{orig}}(f_{+,ϵ})$ and ${\hat{e}}_{\text{switch}}(f_{+,ϵ})$ are U-statistics whose terms each have expectation $e_{\text{orig}}$ or $e_{\text{switch}}$, so they are unbiased and the bound applies (p. 52).

Difference version (p. 53). With $M{R}_{\text{difference}}$, set $q(k)=q_{\text{difference}}(k,k/\sqrt{2})$ and

$${\mathcal{Q}}_{\text{out,difference}}:=(1+\frac{1}{\sqrt{2}})B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{n}}=q_{\text{difference}}(B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{n}},B_{\text{ind}}\sqrt{\frac{\log (6{\delta }^{-1})}{2n}}).$$

The same proof then holds without Assumption 3. ${\hat{e}}_{\text{divide}}$: B.14-B.16 also hold with ${\hat{e}}_{\text{divide}}$ in place of ${\hat{e}}_{\text{switch}}$ throughout (including in Assumption 3), since the same U-statistic bound covers both.

Step 4 (B.3.4, Eqs B.17-B.19): combine

$$\mathbb{P}(MC{R}_{+}(ϵ)>{\widehat{MCR}}_{+}({ϵ}_{\text{out}})+{\mathcal{Q}}_{\text{out}})=\mathbb{P}(MR(f_{+,ϵ})>{\widehat{MCR}}_{+}({ϵ}_{\text{out}})+{\mathcal{Q}}_{\text{out}})$$ $$\le \mathbb{P}[\widehat{MR}(f_{+,ϵ})>{\widehat{MCR}}_{+}({ϵ}_{\text{out}})]+\mathbb{P}[MR(f_{+,ϵ})-\widehat{MR}(f_{+,ϵ})>{\mathcal{Q}}_{\text{out}}]\le \frac{\delta }{3}+\frac{2\delta }{3}=\delta .(B.17)$$

Eq 4.3 (lower side). Analogously, $\mathbb{P}[\widehat{MR}(f_{-,ϵ})<{\widehat{MCR}}_{-}({ϵ}_{\text{out}})]\le \delta /3$; on the complement, $MR(f_{-,ϵ})\ge {\widehat{MCR}}_{-}({ϵ}_{\text{out}})-[\widehat{MR}(f_{-,ϵ})-MR(f_{-,ϵ})]$; $\mathbb{P}[\widehat{MR}(f_{-,ϵ})-MR(f_{-,ϵ})>q(B_{\text{ind}}\sqrt{\log (6{\delta }^{-1})/n})]\le 2\delta /3$ (B.18); and the union bound gives $\delta$ (B.19). The difference version again holds without Assumption 3, with $q=q_{\text{difference}}(k,k/\sqrt{2})$ in B.18-B.19.

B.4 Proof of Corollary 22 (p. 54)

Proof of Corollary 22 (Eqs B.20-B.21)

By definition $MR(f_{-,ϵ})\le MR(f^{\star })\le MR(f_{+,ϵ})$ (with $ϵ=0$, since $f^{\star }\in \mathcal{R}(0)$). So

$$\mathbb{P}\{MR(f^{\star })\in [{\widehat{MCR}}_{-}({ϵ}_{\text{best}})-{\mathcal{Q}}_{\text{best}},{\widehat{MCR}}_{+}({ϵ}_{\text{best}})+{\mathcal{Q}}_{\text{best}}]\}\ge 1-\mathbb{P}\{MR(f_{-,ϵ})<{\widehat{MCR}}_{-}({ϵ}_{\text{best}})-{\mathcal{Q}}_{\text{best}}\}-\mathbb{P}\{MR(f_{+,ϵ})>{\widehat{MCR}}_{+}({ϵ}_{\text{best}})+{\mathcal{Q}}_{\text{best}}\}(B.20)$$ $$\ge 1-\delta /2-\delta /2\text{(Theorem 4)},(B.21)$$

because ${ϵ}_{\text{best}}$ and ${\mathcal{Q}}_{\text{best}}$ are ${ϵ}_{\text{out}}$ and ${\mathcal{Q}}_{\text{out}}$ with $ϵ=0$ and $\delta$ replaced by $\delta /2$. With ${\mathcal{Q}}_{\text{best,difference}}=(1+1/\sqrt{2})B_{\text{ind}}\sqrt{\log (12{\delta }^{-1})/n}$ (= ${\mathcal{Q}}_{\text{out,difference}}$ at $\delta /2$), the corollary holds without Assumption 3. (The source calls it “Theorem 22” in this sentence; it is Corollary 22.)

B.5 Proofs of Theorems 5, 25 and 6 (pp. 55-62)

Theorem 5 “follows directly” from Eq B.25 of Theorem 25 (statement in ^thm-25).

Proof of Eq B.22 (B.5.2, Eqs B.29-B.33): uniform deviation of ${\hat{e}}_{\text{orig}}$

Let ${\mathcal{G}}_r$ be a minimal $r$-margin-expectation-cover, $D_p$ the population, $D_s$ the sample distribution, and $D^{\star }$ their uniform mixture: ${\mathbb{P}}_{D^{\star }}(Z\le z)=\frac{1}{2}{\mathbb{P}}_{D_p}(Z\le z)+\frac{1}{2}{\mathbb{P}}_{D_s}(Z\le z)$ (B.29). For any $f$ pick $g\in {\mathcal{G}}_r$ with ${\mathbb{E}}_{D^{\star }}|L(g,Z)-L(f,Z)|\le r$. Then (B.30)

$$|\hat{\mathbb{E}}L(f)-\mathbb{E}L(f)|\le |\hat{\mathbb{E}}L(g)-\mathbb{E}L(g)|+{\mathbb{E}}_{D_p}|L(g)-L(f)|+{\mathbb{E}}_{D_s}|L(f)-L(g)|=|\hat{\mathbb{E}}L(g)-\mathbb{E}L(g)|+2{\mathbb{E}}_{D^{\star }}|L(g)-L(f)|\le |\hat{\mathbb{E}}L(g)-\mathbb{E}L(g)|+2r.$$

Hence (B.31-B.33)

$$\mathbb{P}(\underset{f}{\sup }|\hat{\mathbb{E}}L(f)-\mathbb{E}L(f)|>B_{\text{ind}}\sqrt{\frac{\log (2{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r)\le \sum _{g\in {\mathcal{G}}_r}\mathbb{P}(|\hat{\mathbb{E}}L(g)-\mathbb{E}L(g)|>B_{\text{ind}}\sqrt{\frac{\log (2{\delta }^{-1}\mathcal{N})}{2n}})\le \mathcal{N}(\mathcal{F},r)\cdot 2\exp \{-\log (2{\delta }^{-1}\mathcal{N})\}=\delta ,$$

by the union bound and Hoeffding’s inequality ($L(g,Z)$ lies in an interval of length $B_{\text{ind}}$). Because $D_s$ depends on the data, the cover has to be valid for any distribution; this is why Eq 4.4 quantifies over all $D$.

Proof of Eq B.23 (B.5.3)

“Nearly identical” to B.22: replace $L$ by $\tilde{L}$ and $B_{\text{ind}}$ by $2B_{\text{ref}}$ (the range of $\tilde{L}$ under Assumption 2) in B.30-B.33.

Proof of Eq B.24 (B.5.4, Eq B.34): uniform deviation of ${\hat{e}}_{\text{switch}}$

Replace the distributions by “switched” ones:

• ${\tilde{D}}_p$: product of the population $(Y,X_2)$ marginal and the population $X_1$ marginal, $F_{{\tilde{D}}_p}(y,x_1,x_2)=F_{D_p}(Y=y,X_2=x_2)F_{D_p}(X_1=x_1)$, so $e_{\text{switch}}(f)={\mathbb{E}}_{{\tilde{D}}_p}L(f,Z)$;
• ${\tilde{D}}_s$: the empirical distribution of the $n(n-1)$ off-diagonal pairs, ${\mathbb{P}}_{{\tilde{D}}_s}(y,x_1,x_2)=\frac{1}{n(n-1)}{\sum }_i{\sum }_{j\ne i}1(y_{[j]}=y,{\mathbf{X}}_{1[i,\cdot ]}=x_1,{\mathbf{X}}_{2[j,\cdot ]}=x_2)$, so ${\hat{e}}_{\text{switch}}(f)={\mathbb{E}}_{{\tilde{D}}_s}L(f,Z)$;
• ${\tilde{D}}^{\star }$: their uniform mixture, as in B.29.

With $g\in {\mathcal{G}}_r$ chosen so ${\mathbb{E}}_{{\tilde{D}}^{\star }}|L(g)-L(f)|\le r$, the same argument gives $|{\hat{e}}_{\text{switch}}(f)-e_{\text{switch}}(f)|\le |{\hat{e}}_{\text{switch}}(g)-e_{\text{switch}}(g)|+2r$. A union bound over ${\mathcal{G}}_r$ and Hoeffding’s bound for U-statistics (Eq 5.7 of Hoeffding 1963, as in B.15) give

$$\mathbb{P}(\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 \mathcal{N}(\mathcal{F},r)2\exp \{-\frac{n}{B_{\text{ind}}^2}{B}_{\text{ind}}^2\frac{\log (2{\delta }^{-1}\mathcal{N})}{n}\}=\delta .(B.34)$$

Note that B.24 is stated with $\mathcal{N}(\mathcal{F},r)$; there is no $\sqrt{2}$ in it.

Proof of Eq B.25 (B.5.5, Eqs B.35-B.37): uniform ratio bound

By Lemma 24 and the definition of ${\mathcal{Q}}_4$ (B.27), a ratio error above ${\mathcal{Q}}_4$ requires one of two deviations:

$$\mathbb{P}[\underset{f}{\sup }|\text{ratio error}|>{\mathcal{Q}}_4]\le \mathbb{P}[\underset{f}{\sup }|{\hat{e}}_{\text{orig}}-e_{\text{orig}}|>B_{\text{ind}}\sqrt{\frac{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r]+\mathbb{P}[\underset{f}{\sup }|{\hat{e}}_{\text{switch}}-e_{\text{switch}}|>B_{\text{ind}}\sqrt{\frac{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))}{n}}+2r\sqrt{2}]\le \frac{\delta }{2}+\frac{\delta }{2}.(B.36\text{-}B.37)$$

The first term is B.22 at level $\delta /2$. The second is B.24 applied at level $\delta /2$ with cover radius $r\sqrt{2}$ in place of $r$: substituting gives exactly $B_{\text{ind}}\sqrt{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))/n}+2r\sqrt{2}$. That is the only place the $\sqrt{2}$ enters. The source gives no reason for using radius $r\sqrt{2}$ rather than $r$ for the switched term. Since B.24 holds for any $r>0$, the choice is valid, but it is not derived from any property of the pairs distribution.

Printing inconsistency. B.25 is printed with the ratio ${\hat{e}}_{\text{orig}}/{\hat{e}}_{\text{switch}}$ against $e_{\text{orig}}/e_{\text{switch}}$, but the first argument of $q_{\text{ratio}}$ in ${\mathcal{Q}}_4$ ($k_Z$, the numerator’s deviation) is the ${\hat{e}}_{\text{switch}}$ term, and Lemma 24’s conditions ($0<b_{\text{orig}}\le X$, $Z\le B_{\text{switch}}$) only make sense with ${\hat{e}}_{\text{switch}}$ in the numerator. The intended statement is the MR ratio ${\hat{e}}_{\text{switch}}/{\hat{e}}_{\text{orig}}$, matching Theorem 5.

Proof of Eq B.26 (B.5.6): uniform difference bound

Same steps as B.35-B.37, with B.28 and the difference part of Lemma 24:

$$\mathbb{P}[\underset{f}{\sup }|\{{\hat{e}}_{\text{switch}}-{\hat{e}}_{\text{orig}}\}-\{e_{\text{switch}}-e_{\text{orig}}\}|>{\mathcal{Q}}_{4,\text{difference}}]\le \frac{\delta }{2}+\frac{\delta }{2}.$$

No ratio is formed, so Assumption 3 is not needed. This is the uniform bound for $M{R}_{\text{difference}}$, i.e. the difference analogue of Theorem 5.

Proof of Theorem 6, Eq 4.6 (B.5.7, Eqs B.38-B.43)

Bad event (B.38). $E$: some ${\hat{f}}_{+,{ϵ}_{\text{in}}}\in \arg {\max }_{f\in \hat{\mathcal{R}}({ϵ}_{\text{in}})}\widehat{MR}(f)$ has $MC{R}_{+}(ϵ)<MR({\hat{f}}_{+,{ϵ}_{\text{in}}})$. Because ${ϵ}_{\text{in}}<ϵ$, $E$ should be unlikely.

$E$ is unlikely (B.39-B.40).

$$\mathbb{P}(E)\le \mathbb{P}\{\exists f\in \hat{\mathcal{R}}({ϵ}_{\text{in}}):MC{R}_{+}(ϵ)<MR(f)\}=\mathbb{P}\{\exists f\in \hat{\mathcal{R}}({ϵ}_{\text{in}})\setminus f_{\text{ref}}:MC{R}_{+}(ϵ)<MR(f)\}$$

(since $MC{R}_{+}(ϵ)\ge MR(f_{\text{ref}})$)

$$\le \mathbb{P}\{\exists f\in \hat{\mathcal{R}}({ϵ}_{\text{in}})\setminus f_{\text{ref}}:\mathbb{E}\tilde{L}(f,Z)>ϵ\}$$

(a model with MR above $MC{R}_{+}(ϵ)$ cannot be in $\mathcal{R}(ϵ)$)

$$=\mathbb{P}\{\exists f\in \mathcal{F},\mathbb{E}\tilde{L}(f,Z)>ϵ:\hat{\mathbb{E}}\tilde{L}(f,Z)\le {ϵ}_{\text{in}}\}$$ $$=\mathbb{P}\{\exists f,\mathbb{E}\tilde{L}>ϵ:\hat{\mathbb{E}}\tilde{L}-ϵ\le -2B_{\text{ref}}\sqrt{\frac{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}-2r\}\text{(definition of }{ϵ}_{\text{in}})$$ $$\le \mathbb{P}\{\underset{f}{\sup }|\hat{\mathbb{E}}\tilde{L}-\mathbb{E}\tilde{L}|\ge 2B_{\text{ref}}\sqrt{\frac{\log (4{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r\}=\frac{\delta }{2}\text{(B.23 at }\delta /2).$$

Off $E$ (B.41). For every ${\hat{f}}_{+,{ϵ}_{\text{in}}}$ in the argmax:

$$MC{R}_{+}(ϵ)\ge MR({\hat{f}}_{+,{ϵ}_{\text{in}}})=\widehat{MR}({\hat{f}}_{+,{ϵ}_{\text{in}}})-\{\widehat{MR}({\hat{f}}_{+,{ϵ}_{\text{in}}})-MR({\hat{f}}_{+,{ϵ}_{\text{in}}})\}={\widehat{MCR}}_{+}({ϵ}_{\text{in}})-\{\cdots \}\ge {\widehat{MCR}}_{+}({ϵ}_{\text{in}})-\underset{f\in \mathcal{F}}{\sup }|\widehat{MR}(f)-MR(f)|.$$

The $\delta /2$-level error term (B.42).

$${\mathcal{Q}}_{\text{in}}=\frac{B_{\text{switch}}}{b_{\text{orig}}}-\frac{B_{\text{switch}}-\{B_{\text{ind}}\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))}{n}}+2r\sqrt{2}\}}{b_{\text{orig}}+\{B_{\text{ind}}\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r\}}=q_{\text{ratio}}(B_{\text{ind}}\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))}{n}}+2r\sqrt{2},B_{\text{ind}}\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r),$$

i.e. ${\mathcal{Q}}_4$ (equivalently $q(\delta ,r,n)$ of Eq 4.5) at level $\delta /2$. By Theorem 25 the sup in B.41 is below ${\mathcal{Q}}_{\text{in}}$ with probability at least $1-\delta /2$.

Union bound (B.43).

$$\mathbb{P}\{MC{R}_{+}(ϵ)<{\widehat{MCR}}_{+}({ϵ}_{\text{in}})-{\mathcal{Q}}_{\text{in}}\}\le \mathbb{P}(E)+\mathbb{P}\{\underset{f}{\sup }|\widehat{MR}-MR|>{\mathcal{Q}}_{\text{in}}\}\le \frac{\delta }{2}+\frac{\delta }{2}.$$

Theorem 6 without Assumption 3, and Eq 4.7 (pp. 60-62, Eqs B.44-B.45)

Difference version of 4.6. With $MR=e_{\text{switch}}-e_{\text{orig}}$ and

$${\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)=q_{\text{difference}}(B_{\text{ind}}\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r\sqrt{2}))}{n}}+2r\sqrt{2},B_{\text{ind}}\sqrt{\frac{\log (8{\delta }^{-1}\mathcal{N}(\mathcal{F},r))}{2n}}+2r),$$

the proof of 4.6 holds without Assumption 3, using B.26 in B.43.

Eq 4.7. Bad event (B.44): some ${\hat{f}}_{-,{ϵ}_{\text{in}}}\in \arg {\min }_{\hat{\mathcal{R}}({ϵ}_{\text{in}})}\widehat{MR}$ has $MC{R}_{-}(ϵ)>MR({\hat{f}}_{-,{ϵ}_{\text{in}}})$. As in B.40, $\mathbb{P}(\text{B.44})\le \mathbb{P}\{\exists f,\mathbb{E}\tilde{L}>ϵ:\hat{\mathbb{E}}\tilde{L}\le {ϵ}_{\text{in}}\}\le \delta /2$. Off B.44, $MC{R}_{-}(ϵ)\le {\widehat{MCR}}_{-}({ϵ}_{\text{in}})+{\sup }_f|\widehat{MR}(f)-MR(f)|$. The union bound gives $\delta /2+\delta /2$ (B.45). The difference version again uses ${\mathcal{Q}}_{\text{in,difference}}$ and B.26.

Examples

Where the constants $3$, $6$, $4$ and $8$ inside the logs come from

• ${ϵ}_{\text{out}}$ uses $\log (3{\delta }^{-1})$: Lemma 23 is spent at $\delta /3$.
• ${\mathcal{Q}}_{\text{out}}$ uses $\log (6{\delta }^{-1})$: the remaining $2\delta /3$ is split over two two-sided Hoeffding bounds, each $2\exp (\cdot )=2\delta /6$.
• ${ϵ}_{\text{in}}$ uses $\log (4{\delta }^{-1}\mathcal{N})$: B.23 at level $\delta /2$, where B.23 itself has $\log (2{\delta }^{-1}\mathcal{N})$.
• ${\mathcal{Q}}_{\text{in}}$ uses $\log (8{\delta }^{-1}\mathcal{N})$: B.25 at level $\delta /2$, where B.25 already spends $\delta /2$ on each of B.22 and B.24.
• ${ϵ}_{\text{best}},{\mathcal{Q}}_{\text{best}}$ use $\log (6{\delta }^{-1}),\log (12{\delta }^{-1})$: Theorem 4 at $\delta /2$.

Connections

• The B.5.2 trick (choose the cover against a mixture of population and sample distributions, so the same $g$ approximates $f$ in both) is a standard route to uniform laws of large numbers; it is the formal reason the in-sample $ϵ$-band does not overfit when $\mathcal{N}(\mathcal{F},r)$ is controlled. See Model Selection and Overfitting.
• Treating ${\hat{e}}_{\text{switch}}$ as a U-statistic, rather than as a single random permutation, is what makes Hoeffding’s U-statistic bound available: Model Reliance - Permutation Importance as a U-Statistic.

See Also

• Model Class Reliance - Outer and Inner Finite-Sample Bounds: the statements these proofs support
• Model Class Reliance - Appendix C Proofs of the Binary Search Lemmas: the computational proofs
• Fisher Rudin Dominici 2019 - Model Class Reliance - Overview