Model Class Reliance - Appendix C Proofs of the Binary Search Lemmas

Summary

Appendix C proves the computational results of §6: the bound lemmas (Lemma 9 for the lower search, Lemma 13 for the upper search), the monotonicity lemmas that justify bisection (Lemma 10, Lemma 14), and Proposition 11 (nonnegative weights suffice). Every proof uses the same three tools. (i) An elementary inequality (C.1): from $a\ge c$ and $a+b\le c+d$, conclude $b\le d$. (ii) Optimality of each minimizer, ${\hat{h}}_{\pm ,{\gamma }_1}({\hat{g}}_{\pm ,{\gamma }_1})\le {\hat{h}}_{\pm ,{\gamma }_1}({\hat{g}}_{\pm ,{\gamma }_2})$ (C.2). (iii) The linear “shift” identities C.3-C.4 between objectives at two values of $\gamma$. All statements and the algorithm are in Model Class Reliance - Binary Search Computation; this note holds the full derivations.

Overview

Notation follows Model Class Reliance - Binary Search Computation:

• ${\hat{h}}_{-,\gamma }(f)=\gamma {\hat{e}}_{\text{orig}}(f)+{\hat{e}}_{\text{switch}}(f)$, with minimizer ${\hat{g}}_{-,\gamma }$;
• ${\hat{h}}_{+,\gamma }(f)={\hat{e}}_{\text{orig}}(f)+\gamma {\hat{e}}_{\text{switch}}(f)$, with minimizer ${\hat{g}}_{+,\gamma }$;
• ${ϵ}_{\text{abs}}>0$ is the absolute loss threshold;
• throughout, $0<{\hat{e}}_{\text{orig}}(f)$ for every $f\in \mathcal{F}$.

Scope with ${\hat{e}}_{\text{divide}}$ (App C preamble, p. 67). Almost every proof in App C is unchanged if ${\hat{e}}_{\text{switch}}$ is replaced by ${\hat{e}}_{\text{divide}}$ in the definitions of ${\hat{h}}_{\pm ,\gamma }$, ${\hat{g}}_{\pm ,\gamma }$ and $\widehat{MR}$. The only exception is C.3 (Proposition 11). See ^proof-prop11.

Main Content

Preamble identities (pp. 67-68)

Identities C.1-C.4 used in every App C proof

(C.1) For constants $a,b,c,d\in \mathbb{R}$ with $a\ge c$:

$$a+b\le c+d\Rightarrow a-c\le d-b\Rightarrow 0\le d-b(\text{since }0\le a-c)\Rightarrow b\le d.$$

(C.2) For any ${\gamma }_1,{\gamma }_2\in \mathbb{R}$, the definitions of the minimizers give

$${\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_1})\le {\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_2}),{\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})\le {\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_2}).$$

(C.3) For any ${\gamma }_1,{\gamma }_2$ and any $f$:

$${\hat{h}}_{+,{\gamma }_1}(f)={\hat{e}}_{\text{orig}}(f)+{\gamma }_2{\hat{e}}_{\text{switch}}(f)+\{{\gamma }_1{\hat{e}}_{\text{switch}}(f)-{\gamma }_2{\hat{e}}_{\text{switch}}(f)\}={\hat{h}}_{+,{\gamma }_2}(f)+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{switch}}(f).$$

(C.4) By the same steps,

$${\hat{h}}_{-,{\gamma }_1}(f)={\hat{h}}_{-,{\gamma }_2}(f)+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}(f).$$

C.1 Proof of Lemma 9 (lower bound for $\widehat{MR}$), pp. 68-69

Proof of Lemma 9, Part 1 (C.1.1): Eq 6.1 holds for all $f$ with ${\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}$

If ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })\ge 0$ and ${\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}$, then $1/{ϵ}_{\text{abs}}\le 1/{\hat{e}}_{\text{orig}}(f)$. Multiplying by the nonnegative $\hat{h}$ gives

$$\frac{{\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })}{{ϵ}_{\text{abs}}}\le \frac{{\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })}{{\hat{e}}_{\text{orig}}(f)}.(C.5)$$

By the definition of ${\hat{g}}_{-,\gamma }$:

$${\hat{h}}_{-,\gamma }(f)\ge {\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })\Rightarrow \gamma +\frac{{\hat{e}}_{\text{switch}}(f)}{{\hat{e}}_{\text{orig}}(f)}\ge \frac{{\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })}{{\hat{e}}_{\text{orig}}(f)}\stackrel{(C.5)}{\ge }\frac{{\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })}{{ϵ}_{\text{abs}}},$$

so $\widehat{MR}(f)\ge {\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })/{ϵ}_{\text{abs}}-\gamma$.

Proof of Lemma 9, Part 2 (C.1.2): equality cases

Take $f={\hat{g}}_{-,\gamma }$.

• If ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })=0$: then $0=\gamma {\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })+{\hat{e}}_{\text{switch}}({\hat{g}}_{-,\gamma })$, so $\gamma =-{\hat{e}}_{\text{switch}}({\hat{g}}_{-,\gamma })/{\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })$. Hence $\frac{0}{{ϵ}_{\text{abs}}}-\gamma =\widehat{MR}({\hat{g}}_{-,\gamma })$.
• If ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })={ϵ}_{\text{abs}}$: then $\frac{{\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })}{{ϵ}_{\text{abs}}}-\gamma =\frac{\gamma {\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })+{\hat{e}}_{\text{switch}}({\hat{g}}_{-,\gamma })}{{\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })}-\gamma =\widehat{MR}({\hat{g}}_{-,\gamma })$.

C.2 Proof of Lemma 10 (monotonicity, lower search), pp. 69-70

Proof of Lemma 10, Part 1 (C.2.1): ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })$ increases in $\gamma$

Let ${\gamma }_1<{\gamma }_2$. Since ${\hat{e}}_{\text{orig}}(f)>0$ for all $f$,

$${\gamma }_1{\hat{e}}_{\text{orig}}(f)+{\hat{e}}_{\text{switch}}(f)<{\gamma }_2{\hat{e}}_{\text{orig}}(f)+{\hat{e}}_{\text{switch}}(f),\text{i.e. }{\hat{h}}_{-,{\gamma }_1}(f)<{\hat{h}}_{-,{\gamma }_2}(f).(C.6)$$

Then ${\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})\stackrel{(C.2)}{\le }{\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_2})\stackrel{(C.6)}{\le }{\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})$. This is analogous to Lemma 3 of Dinkelbach (1967).

Proof of Lemma 10, Part 2 (C.2.2): ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })$ decreases in $\gamma$

Let ${\gamma }_1<{\gamma }_2$. Start from C.2 and rewrite both sides with C.4 (shifting from ${\gamma }_1$ to ${\gamma }_2$):

$${\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_1})+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})\le {\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2}).$$

By C.2 at ${\gamma }_2$, $a:={\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_1})\ge c:={\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})$. So C.1 gives $({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})\le ({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})$. Dividing by the negative ${\gamma }_1-{\gamma }_2$ gives ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})\ge {\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})$.

Proof of Lemma 10, Part 3 (C.2.3): sign-dependent monotonicity of the lower bound

Claim: ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })/{ϵ}_{\text{abs}}-\gamma$ decreases in $\gamma$ where ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })\le {ϵ}_{\text{abs}}$ and increases otherwise.

Case ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1}),{\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})\le {ϵ}_{\text{abs}}$, with ${\gamma }_1<{\gamma }_2$:

$${\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})\stackrel{(C.2)}{\le }{\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_1})\stackrel{(C.4)}{=}{\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})+({\gamma }_2-{\gamma }_1){\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})\le {\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})+({\gamma }_2-{\gamma }_1){ϵ}_{\text{abs}}.$$

Dividing by ${ϵ}_{\text{abs}}$: ${\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})/{ϵ}_{\text{abs}}-{\gamma }_2\le {\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})/{ϵ}_{\text{abs}}-{\gamma }_1$ (decreasing).

Case both $\ge {ϵ}_{\text{abs}}$, with ${\gamma }_1<{\gamma }_2$:

$${\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})\le {\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_2})={\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})\le {\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})+({\gamma }_1-{\gamma }_2){ϵ}_{\text{abs}},$$

where the last step uses ${\gamma }_1-{\gamma }_2<0$ and ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})\ge {ϵ}_{\text{abs}}$. (The source labels this step “from ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})\ge {ϵ}_{\text{abs}}$”, but the term that is bounded is ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})$, which the case assumption also covers.) Dividing by ${ϵ}_{\text{abs}}$: ${\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})/{ϵ}_{\text{abs}}-{\gamma }_1\le {\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})/{ϵ}_{\text{abs}}-{\gamma }_2$ (increasing).

C.3 Proof of Proposition 11 (nonnegative weights), pp. 70-71

Proof of Proposition 11 (C.3, Eqs C.7-C.10)

1. Equal weights at ${\gamma }_1=1/(n-1)$. Let $D_s$ be the sample distribution and $D_m$ the product of the sample $(Y,X_2)$ marginal and the sample $X_1$ marginal:

$${\mathbb{P}}_{D_m}\{(Y,X_1,X_2)=(y,x_1,x_2)\}=\frac{1}{n^2}\sum _{i=1}^{n}1(y_{[i]}=y,{\mathbf{X}}_{2[i]}=x_2)\sum _{j=1}^{n}1({\mathbf{X}}_{1[j]}=x_1).$$

With ${\gamma }_1=1/(n-1)$, every weight in Eq 6.2 equals $1/\{n(n-1)\}$, so ${\hat{h}}_{-,{\gamma }_1}(f)\propto {\mathbb{E}}_{D_m}L\{f,(Y,X_1,X_2)\}$. 2. A minimizer ignores $X_1$. In $D_m$, $X_1$ is independent of $(Y,X_2)$. Condition 2 of Prop 11 then gives a minimizer ${\hat{g}}_{-,{\gamma }_1}$ with ${\hat{g}}_{-,{\gamma }_1}(x_1^{(a)},x_2)={\hat{g}}_{-,{\gamma }_1}(x_1^{(b)},x_2)$. Condition 1 makes its loss invariant to $x_1$. 3. So its $\widehat{MR}$ is 1 (C.7). ${\hat{e}}_{\text{switch}}({\hat{g}}_{-,{\gamma }_1})=\frac{1}{n}{\sum }_i\frac{1}{n-1}{\sum }_{j\ne i}L\{{\hat{g}}_{-,{\gamma }_1},(y_{[i]},{\mathbf{X}}_{1[j]},{\mathbf{X}}_{2[i]})\}=\frac{1}{n}{\sum }_{i}L\{{\hat{g}}_{-,{\gamma }_1},(y_{[i]},{\mathbf{X}}_{1[i]},{\mathbf{X}}_{2[i]})\}={\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})$. 4. Move to ${\gamma }_2=0$. By the definition of ${\hat{g}}_{-,0}$: $0+{\hat{e}}_{\text{switch}}({\hat{g}}_{-,0})\le 0+{\hat{e}}_{\text{switch}}({\hat{g}}_{-,{\gamma }_1})$ (C.8). By Lemma 10 Part 2 (since $0\le {\gamma }_1$): ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,0})\ge {\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})$ (C.9). 5. Combine (C.10). $\widehat{MR}({\hat{g}}_{-,0})={\hat{e}}_{\text{switch}}({\hat{g}}_{-,0})/{\hat{e}}_{\text{orig}}({\hat{g}}_{-,0})\le {\hat{e}}_{\text{switch}}({\hat{g}}_{-,{\gamma }_1})/{\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})=1$. 6. Since ${\hat{h}}_{-,0}({\hat{g}}_{-,0})={\hat{e}}_{\text{switch}}({\hat{g}}_{-,0})\ge 0$ automatically, Condition 8 holds at $\gamma =0$ iff ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,0})\le {ϵ}_{\text{abs}}$. Together with C.10 this is the dichotomy in Proposition 11.

Why it fails for ${\hat{e}}_{\text{divide}}$ (p. 71). ${\hat{e}}_{\text{divide}}$ is not an expectation over a distribution in which $X_1$ is independent of $(X_2,Y)$, because of its fixed pairing. So Condition 2 of Prop 11 does not apply.

C.4 Proof of Lemma 13 (upper bound for $\widehat{MR}$), pp. 71-72

Proof of Lemma 13, Part 1 (C.4.1): Eq 6.4 holds for all $f$ with ${\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}$

If ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })\ge 0$, then as in C.5, ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })/{ϵ}_{\text{abs}}\le {\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })/{\hat{e}}_{\text{orig}}(f)$ (C.11). For $\gamma \le 0$:

$${\hat{e}}_{\text{orig}}(f)+\gamma {\hat{e}}_{\text{switch}}(f)\ge {\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })\Rightarrow 1+\gamma \widehat{MR}(f)\ge \frac{{\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })}{{\hat{e}}_{\text{orig}}(f)}\stackrel{(C.11)}{\ge }\frac{{\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })}{{ϵ}_{\text{abs}}}.$$

Subtracting 1 and multiplying by ${\gamma }^{-1}<0$ flips the inequality: $\widehat{MR}(f)\le \{{\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })/{ϵ}_{\text{abs}}-1\}{\gamma }^{-1}$.

Proof of Lemma 13, Part 2 (C.4.2): equality cases

Take $f={\hat{g}}_{+,\gamma }$.

• If ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })=0$: $0={\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })+\gamma {\hat{e}}_{\text{switch}}({\hat{g}}_{+,\gamma })$, so $-{\hat{e}}_{\text{switch}}({\hat{g}}_{+,\gamma })/{\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })=1/\gamma$. Then $\{0/{ϵ}_{\text{abs}}-1\}{\gamma }^{-1}=-{\gamma }^{-1}=\widehat{MR}({\hat{g}}_{+,\gamma })$.
• If ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })={ϵ}_{\text{abs}}$: $\{\frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })+\gamma {\hat{e}}_{\text{switch}}({\hat{g}}_{+,\gamma })}{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })}-1\}{\gamma }^{-1}=\{1+\gamma \widehat{MR}({\hat{g}}_{+,\gamma })-1\}{\gamma }^{-1}=\widehat{MR}({\hat{g}}_{+,\gamma })$.

C.5 Proof of Lemma 14 (monotonicity, upper search), pp. 72-74

Proof of Lemma 14, Part 1 (C.5.1): ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })$ increases in $\gamma$

Let ${\gamma }_1<{\gamma }_2$. Using nonnegativity of ${\hat{e}}_{\text{switch}}$,

$${\hat{e}}_{\text{orig}}(f)+{\gamma }_1{\hat{e}}_{\text{switch}}(f)<{\hat{e}}_{\text{orig}}(f)+{\gamma }_2{\hat{e}}_{\text{switch}}(f),\text{i.e. }{\hat{h}}_{+,{\gamma }_1}(f)<{\hat{h}}_{+,{\gamma }_2}(f).(C.12)$$

Then ${\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_1})\stackrel{(C.2)}{\le }{\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_2})\stackrel{(C.12)}{<}{\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_2})$.

Caveat. The source cites the assumption $0\le {\hat{e}}_{\text{switch}}(f)$ but writes the strict inequality in C.12. Strictness needs ${\hat{e}}_{\text{switch}}(f)>0$; with only $\ge$, C.12 and the conclusion hold as weak inequalities, which is all the binary search needs.

Proof of Lemma 14, Part 2 (C.5.2): ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })$ decreases for $\gamma \le 0$, and Condition 12 holds at $\gamma =0$

Let ${\gamma }_1<{\gamma }_2\le 0$.

Step A (C.13): ${\hat{e}}_{\text{switch}}$ falls as $\gamma$ rises. From C.2 rewritten with C.3:

$${\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_1})+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})\le {\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_2})+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2}).$$

C.1 (with C.2 at ${\gamma }_2$) gives $({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})\le ({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})$, so ${\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})\ge {\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})$. Multiplying by ${\gamma }_2\le 0$ gives ${\gamma }_2{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})\le {\gamma }_2{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})$.

Step B (C.14): ${\hat{e}}_{\text{orig}}$ falls as $\gamma$ rises. From C.2 at ${\gamma }_2$:

$${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})+{\gamma }_2{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})\le {\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})+{\gamma }_2{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1}).$$

By C.13 the ${\gamma }_2{\hat{e}}_{\text{switch}}$ term on the left is at least the one on the right. C.1 then gives ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})\le {\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})$.

Step C: Condition 12 at $\gamma =0$ when ${ϵ}_{\text{abs}}\ge {\min }_f{\hat{e}}_{\text{orig}}(f)$. At $\gamma =0$, ${\hat{h}}_{+,0}({\hat{g}}_{+,0})={\hat{e}}_{\text{orig}}({\hat{g}}_{+,0})$, which is positive by assumption, so the first inequality of Condition 12 holds. Also

$${\hat{e}}_{\text{orig}}({\hat{g}}_{+,0})={\hat{h}}_{+,0}({\hat{g}}_{+,0})=\underset{f\in \mathcal{F}}{\min }{\hat{h}}_{+,0}(f)=\underset{f\in \mathcal{F}}{\min }{\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}},$$

so the second holds too. This is why the upper search can always start at $\gamma =0$.

Proof of Lemma 14, Part 3 (C.5.3): increasing and decreasing ranges of the upper bound

Claim: $\{{\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })/{ϵ}_{\text{abs}}-1\}{\gamma }^{-1}$ increases in $\gamma$ where ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })\le {ϵ}_{\text{abs}}$ and $\gamma <0$, and decreases where ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })>{ϵ}_{\text{abs}}$ and $\gamma <0$.

Increasing range. Let ${\gamma }_1<{\gamma }_2<0$ with both ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_i})\le {ϵ}_{\text{abs}}$. Then $1/{\gamma }_2<1/{\gamma }_1$, and multiplying by ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})-{ϵ}_{\text{abs}}\le 0$:

$$\frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})-{ϵ}_{\text{abs}}}{{\gamma }_2}\ge \frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})-{ϵ}_{\text{abs}}}{{\gamma }_1}.(C.15)$$

(The source prints C.15 with a strict ”>”, which needs ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})<{ϵ}_{\text{abs}}$.) From C.2, ${\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_2})\le {\gamma }_2{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})+{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})$. Subtract ${ϵ}_{\text{abs}}$ and divide by ${\gamma }_2<0$:

$$\frac{{\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}}{{\gamma }_2}\ge {\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})+\frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})-{ϵ}_{\text{abs}}}{{\gamma }_2}\stackrel{(C.15)}{\ge }{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})+\frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})-{ϵ}_{\text{abs}}}{{\gamma }_1}=\frac{{\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_1})-{ϵ}_{\text{abs}}}{{\gamma }_1}.$$

Dividing by ${ϵ}_{\text{abs}}$ shows the bound at ${\gamma }_2$ is at least the bound at ${\gamma }_1$.

Decreasing range. Let ${\gamma }_1<{\gamma }_2<0$ with both ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_i})\ge {ϵ}_{\text{abs}}$. Now ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}\ge 0$, so

$$\frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}}{{\gamma }_2}\le \frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}}{{\gamma }_1}.(C.16)$$

From C.2, ${\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_1})\le {\gamma }_1{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})+{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})$. Subtract ${ϵ}_{\text{abs}}$ and divide by ${\gamma }_1<0$:

$$\frac{{\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_1})-{ϵ}_{\text{abs}}}{{\gamma }_1}\ge {\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})+\frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}}{{\gamma }_1}\stackrel{(C.16)}{\ge }{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})+\frac{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}}{{\gamma }_2}=\frac{{\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}}{{\gamma }_2}.$$

Dividing by ${ϵ}_{\text{abs}}$ shows the bound at ${\gamma }_1$ is at least the bound at ${\gamma }_2$, i.e. decreasing.

Typo in source (p. 74). The last line of this chain is printed as $({\hat{h}}_{+,{\gamma }_1}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}})/{\gamma }_2$. It should read ${\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_2})$, since ${\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})+\{{\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}\}/{\gamma }_2=\{{\hat{h}}_{+,{\gamma }_2}({\hat{g}}_{+,{\gamma }_2})-{ϵ}_{\text{abs}}\}/{\gamma }_2$.

Examples

Why the two monotonicity facts license bisection (illustrative)

Fix ${ϵ}_{\text{abs}}=1$ and suppose that at $\gamma =-0.2$ the upper-search minimizer has ${\hat{e}}_{\text{orig}}=0.95\le 1$ and ${\hat{h}}_{+}=0.95-0.2\times 1.6=0.63\ge 0$, so Condition 12 holds and Lemma 13 gives $\widehat{MR}\le (0.63-1)/(-0.2)=1.85$. Part 2 says that moving to a more negative $\gamma$ can only raise ${\hat{e}}_{\text{orig}}$ of the minimizer, so once a $\gamma$ breaks the loss constraint, every smaller $\gamma$ does too. Part 3 says that inside the feasible range the bound falls as $\gamma$ falls. So the tightest feasible bound sits at the feasibility boundary, and bisection finds it.

Connections

• The structure (parametric linear subproblems plus monotonicity of the optimal value in the parameter) is Dinkelbach’s (1967) method for fractional programs. The constraint on the denominator, ${\hat{e}}_{\text{orig}}\le {ϵ}_{\text{abs}}$, is what makes Part 3 of Lemmas 10 and 14 necessary.
• The same “fit-versus-reliance” trade-off curve appears when screening alternative model fits by in-sample loss: see Model Selection and Overfitting.

See Also

• Model Class Reliance - Binary Search Computation: statements, figures and the algorithm
• Model Class Reliance - Appendix B Proofs of the Finite-Sample Bounds: the statistical proofs
• Fisher Rudin Dominici 2019 - Model Class Reliance - Overview