Model Class Reliance - Binary Search Computation

Summary

Empirical MCR means minimizing and maximizing a ratio ${\hat{e}}_{\text{switch}}/{\hat{e}}_{\text{orig}}$ over $\{f:{\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}\}$. The paper reduces this to repeatedly minimizing linear combinations: ${\hat{h}}_{-,\gamma }=\gamma {\hat{e}}_{\text{orig}}+{\hat{e}}_{\text{switch}}$ for the lower bound and ${\hat{h}}_{+,\gamma }={\hat{e}}_{\text{orig}}+\gamma {\hat{e}}_{\text{switch}}$ ($\gamma \le 0$) for the upper bound. This is a Dinkelbach-style fractional-programming search. Each minimum gives a valid bound function holding for every loss level at once (the “bowl” envelope of Figs 2 and 8). Monotonicity lemmas justify a binary search over $\gamma$. When irrelevant information cannot help (Prop 11), the lower-bound search needs only $\gamma \ge 0$, i.e. a reweighted empirical-risk minimization on an $n^2$-row expanded sample.

Overview

The bound is stated on the absolute loss scale ${ϵ}_{\text{abs}}$; set ${ϵ}_{\text{abs}}={\hat{e}}_{\text{orig}}(f_{\text{ref}})+ϵ$. The output is a pair of functions $b_{-},b_{+}$ with

$$b_{-}({ϵ}_{\text{abs}})\le \widehat{MR}(f)\le b_{+}({ϵ}_{\text{abs}})\text{for all }\{f,{ϵ}_{\text{abs}}:{\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}},f\in \mathcal{F},{ϵ}_{\text{abs}}>0\}.$$

The binary search tightens them at the ${ϵ}_{\text{abs}}$ of interest. Throughout, $0<{\min }_{f\in \mathcal{F}}{\hat{e}}_{\text{orig}}(f)$, so MR is finite. Almost everything holds with ${\hat{e}}_{\text{divide}}$ in place of ${\hat{e}}_{\text{switch}}$. The App C preamble (p. 67) states this explicitly: every App C proof is unchanged with ${\hat{e}}_{\text{divide}}$ in the definitions of ${\hat{h}}_{\pm ,\gamma }$, ${\hat{g}}_{\pm ,\gamma }$ and $\widehat{MR}$, except C.3 (Proposition 11).

Preamble identities (App C, pp. 67-68) used by all proofs below:

• (C.1) for $a\ge c$, $a+b\le c+d$ implies $b\le d$;
• (C.2) ${\hat{h}}_{\pm ,{\gamma }_1}({\hat{g}}_{\pm ,{\gamma }_1})\le {\hat{h}}_{\pm ,{\gamma }_1}({\hat{g}}_{\pm ,{\gamma }_2})$;
• (C.3) ${\hat{h}}_{+,{\gamma }_1}(f)={\hat{h}}_{+,{\gamma }_2}(f)+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{switch}}(f)$;
• (C.4) ${\hat{h}}_{-,{\gamma }_1}(f)={\hat{h}}_{-,{\gamma }_2}(f)+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}(f)$.

Full App C derivations are in Model Class Reliance - Appendix C Proofs of the Binary Search Lemmas.

Heuristic alternatives (p. 19). Any model in $\hat{\mathcal{R}}(ϵ)$ gives a lower bound on ${\widehat{MCR}}_{+}$ and an upper bound on ${\widehat{MCR}}_{-}$. So heuristic search, e.g. simulated annealing, tightens the bounds from inside, while the binary search bounds them from outside.

Table 1 (p. 19): Tractability of empirical MCR computation

Model class and loss	Computing ${\widehat{MCR}}_{-}$	Computing ${\widehat{MCR}}_{+}$
(L2-regularized) linear models, squared error	Highly tractable (QP1QC; §§7.2-7.3)	Highly tractable (QP1QC; §§7.2-7.3)
Linear models in an RKHS, squared error	Moderately tractable (QP1QC; §7.4.1)	Moderately tractable (QP1QC; §7.4.1)
Cases where irrelevant covariates do not improve predictions	Moderately tractable (convex problems; Prop 11)	Potentially intractable
Cases where minimizing empirical loss is convex	Potentially intractable (DC programs; §6.3)	Potentially intractable (DC programs; §6.3)

Main Content

Lower bound (§6.1)

Definition: Lower-search objective and Condition 8 (p. 20)

For $\gamma \in \mathbb{R}$: ${\hat{h}}_{-,\gamma }(f):=\gamma {\hat{e}}_{\text{orig}}(f)+{\hat{e}}_{\text{switch}}(f)$ and ${\hat{g}}_{-,\gamma }\in \arg {\min }_{f\in \mathcal{F}}{\hat{h}}_{-,\gamma }(f)$. The minimizer need not be unique. Condition 8 (criteria to continue the search for the MR lower bound): ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })\ge 0$ and ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })\le {ϵ}_{\text{abs}}$.

Lemma 9: Lower bound for $\widehat{MR}$ (p. 20, Eq 6.1)

If $\gamma \in \mathbb{R}$ satisfies ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })\ge 0$, then

$$\frac{{\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })}{{ϵ}_{\text{abs}}}-\gamma \le \widehat{MR}(f)(6.1)$$

for all $f\in \mathcal{F}$ with ${\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}$. Also $-\gamma \le \widehat{MR}(f)$ for all $f\in \mathcal{F}$. If $f={\hat{g}}_{-,\gamma }$ and at least one inequality in Condition 8 holds with equality, then (6.1) holds with equality.

Proof (App C.1). Since $\hat{h}\ge 0$ and ${\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}$: $\hat{h}(\hat{g})/{ϵ}_{\text{abs}}\le \hat{h}(\hat{g})/{\hat{e}}_{\text{orig}}(f)$. Optimality gives $\gamma {\hat{e}}_{\text{orig}}(f)+{\hat{e}}_{\text{switch}}(f)\ge \hat{h}(\hat{g})$. Dividing by ${\hat{e}}_{\text{orig}}(f)$ gives $\gamma +\widehat{MR}(f)\ge \hat{h}(\hat{g})/{\hat{e}}_{\text{orig}}(f)\ge \hat{h}(\hat{g})/{ϵ}_{\text{abs}}$. Equality: if $\hat{h}(\hat{g})=0$ then $\gamma =-\widehat{MR}(\hat{g})$; if ${\hat{e}}_{\text{orig}}(\hat{g})={ϵ}_{\text{abs}}$ the two sides coincide algebraically.

Boundary-function reading (p. 20). Lemma 9 reduces lower-bounding $\widehat{MR}(f)$ to minimizing the linear combination ${\hat{h}}_{-,\gamma }(f)$. For a fixed $\gamma$, the result is not a single bound at one ${ϵ}_{\text{abs}}$ but a boundary function that holds for all ${ϵ}_{\text{abs}}>0$. Lower values of ${ϵ}_{\text{abs}}$ give more restrictive (higher) lower bounds on $\widehat{MR}(f)$, because the left side of (6.1) is decreasing in ${ϵ}_{\text{abs}}$ when ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })\ge 0$. One minimization per $\gamma$ therefore yields a whole curve, which is how the “bowls” in Figure 8 are drawn.

Figure 4 (p. 21): Geometry of Lemma 9

Plot each $f\in \mathcal{F}$ as the point $({\hat{e}}_{\text{orig}}(f),{\hat{e}}_{\text{switch}}(f))$. The slope from the origin to $f$ is $\widehat{MR}(f)$.

• (A) The class is a region bounded away from the vertical axis.
• (B) For $\gamma =1$, contour lines of ${\hat{h}}_{-,\gamma }$ are lines of slope $-\gamma$. The tangent line at the minimum excludes the half-plane below it. If $\min \hat{h}\ge 0$, the origin is excluded or on the boundary.
• (C) Intersecting with ${\hat{e}}_{\text{orig}}\le {ϵ}_{\text{abs}}$ leaves an unshaded region. Every ray from the origin into it has slope at least that of the black line through the origin and the point where the tangent meets ${ϵ}_{\text{abs}}$. That slope is the left side of (6.1).

Lemma 10: Monotonicity for the lower-bound binary search (p. 22)

1. ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })$ is monotonically increasing in $\gamma$ (analogous to Lemma 3 of Dinkelbach 1967).
2. ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })$ is monotonically decreasing in $\gamma$.
3. Given ${ϵ}_{\text{abs}}$, the bound ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })/{ϵ}_{\text{abs}}-\gamma$ is monotonically decreasing in $\gamma$ where ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })\le {ϵ}_{\text{abs}}$, and increasing otherwise.

Implication (p. 22). By point 3, the tightest lower bound from (6.1) uses the smallest $\gamma$ still satisfying Condition 8. The paper states the monotonicity claim with a qualifier: by points 1-2, if ${\gamma }_0$ satisfies Condition 8 and one of the inequalities in Condition 8 holds with equality, then Condition 8 holds for all $\gamma \ge {\gamma }_0$. Together these justify a binary search that lowers $\gamma$ until Condition 8 is no longer met. Figure 5 illustrates the result. (Our reading of the qualifier: point 1 alone makes ${\hat{h}}_{-,\gamma }({\hat{g}}_{-,\gamma })\ge 0$ persist as $\gamma$ grows, and point 2 alone makes ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,\gamma })\le {ϵ}_{\text{abs}}$ persist. The paper attaches the equality qualifier as written, so it is recorded here rather than dropped.)

Proof (App C.2). Uses ${\hat{h}}_{-,{\gamma }_1}(f)={\hat{h}}_{-,{\gamma }_2}(f)+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{orig}}(f)$ (C.4), optimality of each $\hat{g}$ (C.2), the elementary rule C.1 ($a\ge c$ and $a+b\le c+d$ imply $b\le d$), and ${\hat{e}}_{\text{orig}}>0$.

• Part 1: ${\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})$.
• Part 2: rewrite C.2 with C.4 and apply C.1, giving $({\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 ${\gamma }_1-{\gamma }_2<0$ gives ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})\ge {\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})$.
• Part 3: if both minimizers have ${\hat{e}}_{\text{orig}}\le {ϵ}_{\text{abs}}$, then ${\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})\le {\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})+({\gamma }_2-{\gamma }_1){ϵ}_{\text{abs}}$, so the bound falls; if both are $\ge {ϵ}_{\text{abs}}$ the mirror-image chain shows it rises.

Full derivations: ^proof-lemma10-p2 and ^proof-lemma10-p3.

Figure 5 (p. 23): Monotonicity illustrated

Two values ${\gamma }_1<{\gamma }_2$ on Fig. 4-C. A larger $\gamma$ means a flatter tangent line.

1. Intercepts satisfy ${\hat{h}}_{-,{\gamma }_1}({\hat{g}}_{-,{\gamma }_1})\le {\hat{h}}_{-,{\gamma }_2}({\hat{g}}_{-,{\gamma }_2})$.
2. The tangent points move left: ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})\ge {\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_2})$.
3. The implied lower-bound slope falls as $\gamma$ rises in the feasible range.

Reweighting identity (Eq 6.2, p. 22). For $\gamma \ge 0$, minimizing ${\hat{h}}_{-,\gamma }$ is a weighted empirical risk minimization over the $n^2$ “expanded” rows:

$${\hat{h}}_{-,\gamma }(f)=\sum _{i=1}^n\sum _{j=1}^n{w}_{\gamma }(i,j)L\{f,({\mathbf{y}}_{[i]},{\mathbf{X}}_{1[j,\cdot ]},{\mathbf{X}}_{2[i,\cdot ]})\},w_{\gamma }(i,j)=\frac{\gamma 1(i=j)}{n}+\frac{1(i\ne j)}{n(n-1)}\ge 0.$$

Proposition 11: Nonnegative weights suffice for the lower-bound search (pp. 22-23)

Assume:

1. Predictions are sufficient for computing the loss. $L\{f,(y,x_1^{(a)},x_2^{(a)})\}=L\{f,(y,x_1^{(b)},x_2^{(b)})\}$ whenever $f(x_1^{(a)},x_2^{(a)})=f(x_1^{(b)},x_2^{(b)})$.
2. Irrelevant information does not improve predictions. For any distribution $D$ with $X_1{\perp }_D(X_2,Y)$, there is $f_D$ attaining ${\min }_{f\in \mathcal{F}}{\mathbb{E}}_{D}L\{f,(Y,X_1,X_2)\}$ with $f_D(x_1^{(a)},x_2)=f_D(x_1^{(b)},x_2)$ for all $x_1^{(a)},x_1^{(b)},x_2$ (6.3).

Let $\gamma =0$. Then either (i) some minimizer ${\hat{g}}_{-,0}$ of ${\hat{h}}_{-,0}$ violates Condition 8, or (ii) ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,0})\le {ϵ}_{\text{abs}}$ and $\widehat{MR}({\hat{g}}_{-,0})\le 1$ for every minimizer.

Implication. In case (i), the search for $\gamma$ can be restricted to $\gamma \ge 0$, so every subproblem is a nonnegatively weighted ERM, which is convex whenever ordinary ERM is. In case (ii), a well-performing model with $\widehat{MR}\le 1$ exists, so ${\widehat{MCR}}_{-}(ϵ)\le 1$. That is “sufficiently precise … for most interpretational purposes” (p. 23).

Proof (App C.3). At ${\gamma }_1=1/(n-1)$ all $n^2$ weights are equal, so ${\hat{h}}_{-,{\gamma }_1}\propto {\mathbb{E}}_{D_m}L$ under the product distribution $D_m$ of the sample’s $(Y,X_2)$ and $X_1$ marginals. Condition 2 gives a minimizer ignoring $x_1$. Condition 1 makes its loss invariant to permuting $X_1$, so $\widehat{MR}({\hat{g}}_{-,{\gamma }_1})=1$. For ${\gamma }_2=0\le {\gamma }_1$: ${\hat{e}}_{\text{switch}}({\hat{g}}_{-,0})\le {\hat{e}}_{\text{switch}}({\hat{g}}_{-,{\gamma }_1})$ and, by Lemma 10.2, ${\hat{e}}_{\text{orig}}({\hat{g}}_{-,0})\ge {\hat{e}}_{\text{orig}}({\hat{g}}_{-,{\gamma }_1})$. Hence $\widehat{MR}({\hat{g}}_{-,0})\le 1$.

Does not transfer to ${\hat{e}}_{\text{divide}}$. The fixed pairing is not the expectation under a distribution with $X_1$ independent of $(X_2,Y)$. It holds approximately, and (6.1) remains a valid but possibly looser bound with $\gamma \ge 0$.

Upper bound (§6.2)

Definition: Upper-search objective and Condition 12 (p. 24)

${\hat{h}}_{+,\gamma }(f):={\hat{e}}_{\text{orig}}(f)+\gamma {\hat{e}}_{\text{switch}}(f)$, ${\hat{g}}_{+,\gamma }\in \arg {\min }_{f\in \mathcal{F}}{\hat{h}}_{+,\gamma }(f)$. Condition 12 (criteria to continue the search for the MR upper bound), for $(\gamma ,{ϵ}_{\text{abs}})\in {\mathbb{R}}_{\le 0}\times {\mathbb{R}}_{>0}$: ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })\ge 0$ and ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })\le {ϵ}_{\text{abs}}$.

Lemma 13: Upper bound for $\widehat{MR}$ (p. 24, Eqs 6.4-6.5)

If $\gamma \le 0$ and ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })\ge 0$, then for all $f\in \mathcal{F}$ with ${\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}$:

$$\widehat{MR}(f)\le \{\frac{{\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })}{{ϵ}_{\text{abs}}}-1\}{\gamma }^{-1},(6.4)$$

and globally $\widehat{MR}(f)\le |{\gamma }^{-1}|$ for all $f\in \mathcal{F}$ (6.5). Equality in (6.4) holds at $f={\hat{g}}_{+,\gamma }$ if at least one inequality of Condition 12 is tight.

Proof idea (App C.4). As for Lemma 9: ${\hat{e}}_{\text{orig}}(f)+\gamma {\hat{e}}_{\text{switch}}(f)\ge \hat{h}(\hat{g})\ge \hat{h}(\hat{g}){\hat{e}}_{\text{orig}}(f)/{ϵ}_{\text{abs}}$. Divide by $\gamma {\hat{e}}_{\text{orig}}(f)<0$, which flips the inequality. Equality (C.4.2): if ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })=0$ then $-{\gamma }^{-1}=\widehat{MR}({\hat{g}}_{+,\gamma })$, which is the right side of (6.4); if ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })={ϵ}_{\text{abs}}$ the right side reduces to $\{1+\gamma \widehat{MR}({\hat{g}}_{+,\gamma })-1\}{\gamma }^{-1}$. Details: ^proof-lemma13-p2.

Lemma 14: Monotonicity for the upper-bound binary search (pp. 24-25)

1. ${\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })$ is monotonically increasing in $\gamma$.
2. ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })$ is monotonically decreasing in $\gamma$ for $\gamma \le 0$, and Condition 12 holds at $\gamma =0$ whenever ${ϵ}_{\text{abs}}\ge {\min }_f{\hat{e}}_{\text{orig}}(f)$.
3. Given ${ϵ}_{\text{abs}}$, the bound $\{{\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })/{ϵ}_{\text{abs}}-1\}{\gamma }^{-1}$ is monotonically increasing in $\gamma$ where ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })\le {ϵ}_{\text{abs}}$ and $\gamma <0$, and decreasing where ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,\gamma })>{ϵ}_{\text{abs}}$ and $\gamma <0$.

Implication. The tightest upper bound uses the smallest $\gamma$ (most negative) still satisfying Condition 12. Binary-search over $\gamma \le 0$, starting from $\gamma =0$, which is always feasible.

Proof sketch (App C.5, pp. 72-74).

• Part 1 (C.5.1, Eq C.12). Since ${\hat{e}}_{\text{switch}}\ge 0$, ${\hat{h}}_{+,{\gamma }_1}(f)\le {\hat{h}}_{+,{\gamma }_2}(f)$ for ${\gamma }_1<{\gamma }_2$; combine with optimality C.2.
• Part 2 (C.5.2, Eqs C.13-C.14). For ${\gamma }_1<{\gamma }_2\le 0$, C.2 plus the shift identity C.3 (${\hat{h}}_{+,{\gamma }_1}={\hat{h}}_{+,{\gamma }_2}+({\gamma }_1-{\gamma }_2){\hat{e}}_{\text{switch}}$) and C.1 give ${\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})\ge {\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})$, hence ${\gamma }_2{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_1})\le {\gamma }_2{\hat{e}}_{\text{switch}}({\hat{g}}_{+,{\gamma }_2})$ (C.13). Feeding that into C.2 at ${\gamma }_2$ with C.1 gives ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_2})\le {\hat{e}}_{\text{orig}}({\hat{g}}_{+,{\gamma }_1})$ (C.14). Condition 12 holds at $\gamma =0$ because ${\hat{h}}_{+,0}({\hat{g}}_{+,0})={\hat{e}}_{\text{orig}}({\hat{g}}_{+,0})>0$ and ${\hat{e}}_{\text{orig}}({\hat{g}}_{+,0})={\min }_f{\hat{e}}_{\text{orig}}(f)\le {ϵ}_{\text{abs}}$.
• Part 3 (C.5.3, Eqs C.15-C.16). For ${\gamma }_1<{\gamma }_2<0$, $1/{\gamma }_2<1/{\gamma }_1$. Multiplying by ${\hat{e}}_{\text{orig}}-{ϵ}_{\text{abs}}$ ($\le 0$ in the feasible range, C.15; $\ge 0$ outside it, C.16) and combining with C.2 (subtract ${ϵ}_{\text{abs}}$, divide by the negative $\gamma$) shows the bound rises with $\gamma$ in the feasible range and falls outside it.

Full derivations, plus a typo in the source’s last line of C.5.3: ^proof-lemma14-p1, ^proof-lemma14-p2, ^proof-lemma14-p3.

The algorithm

Algorithm: Binary search for empirical MCR (assembled from §6.1-6.2, Lemmas 9-14)

Input: data; class $\mathcal{F}$; loss $L$; target ${ϵ}_{\text{abs}}={\hat{e}}_{\text{orig}}(f_{\text{ref}})+ϵ$; an oracle that minimizes ${\xi }_{\text{orig}}{\hat{e}}_{\text{orig}}+{\xi }_{\text{switch}}{\hat{e}}_{\text{switch}}$ over $\mathcal{F}$.

Lower end ${\widehat{MCR}}_{-}$:

1. Set ${\gamma }_{hi}$ to a value satisfying Condition 8. Lemma 10 implies large $\gamma$ works. Under Prop 11, first try $\gamma =0$: if ${\hat{g}}_{-,0}$ meets Condition 8, stop and report ${\widehat{MCR}}_{-}\le 1$.
2. Set ${\gamma }_{lo}$ to a value violating Condition 8 (under Prop 11, ${\gamma }_{lo}=0$).
3. Repeat: $\gamma \leftarrow ({\gamma }_{lo}+{\gamma }_{hi})/2$; compute ${\hat{g}}_{-,\gamma }$. If Condition 8 holds, set ${\gamma }_{hi}\leftarrow \gamma$, otherwise ${\gamma }_{lo}\leftarrow \gamma$.
4. Report $b_{-}({ϵ}_{\text{abs}})={\hat{h}}_{-,{\gamma }_{hi}}({\hat{g}}_{-,{\gamma }_{hi}})/{ϵ}_{\text{abs}}-{\gamma }_{hi}$ (Lemma 9). The model ${\hat{g}}_{-,{\gamma }_{hi}}$ gives an attained value $\widehat{MR}({\hat{g}}_{-,{\gamma }_{hi}})\ge b_{-}$, so the gap shows how tight the bound is.

Upper end ${\widehat{MCR}}_{+}$: 5. Set ${\gamma }_{hi}=0$ (feasible by Lemma 14.2) and choose ${\gamma }_{lo}<0$ violating Condition 12. 6. Bisect in the same way, keeping the smallest feasible $\gamma$. 7. Report $b_{+}({ϵ}_{\text{abs}})=\{{\hat{h}}_{+,\gamma }({\hat{g}}_{+,\gamma })/{ϵ}_{\text{abs}}-1\}{\gamma }^{-1}$ (Lemma 13).

Envelope: every evaluated $\gamma$ gives a bound valid at all ${ϵ}_{\text{abs}}$. Taking the pointwise best over the evaluated $\gamma$s gives the closed-form convex “bowl” of Fig. 2, which is tightest near the target $ϵ$.

Figure 2 (p. 7): Output of the computation

The axes are $\widehat{MR}(f)$ (x) and in-sample loss (y). A purple convex envelope contains every model in $\mathcal{F}$, and its intersection with the horizontal line at ${\hat{e}}_{\text{orig}}(f_{\text{ref}})+ϵ$ brackets $[{\widehat{MCR}}_{-}(ϵ),{\widehat{MCR}}_{+}(ϵ)]$. The procedure works sequentially, tightening the envelope near the $ϵ$ of interest. Fig. 8 (COMPAS) uses the same format.

Convex model classes: DC programming (§6.3, p. 25)

For $f_{\theta }$ with $\theta \in \Theta \subseteq {\mathbb{R}}^d$ and $L$ convex in $\theta$, the lemmas need only a lower bound on $\min {\hat{h}}_{\pm ,\gamma }$, not the exact minimum. The subproblems are either convex or difference-of-convex (DC) programs:

$$\underset{\{\theta :c_{DC}(\theta )\le k,\theta \in \Theta \}}{\min }{g}_{DC}(\theta )-h_{DC}(\theta ),g_{DC},h_{DC},c_{DC}\text{ convex}.$$

Algorithm: Simplex branch-and-bound lower bound for a DC program (§6.3; Horst & Thoai 1999)

1. Partition $\Theta$ into simplexes.
2. On simplex $j$, replace $h_{DC}$ by the affine $h_j$ interpolating $h_{DC}$ at the vertices. Since $h_{DC}$ is convex, $h_j\ge h_{DC}$ on the simplex, so $l_j:={\min }_{\theta }{g}_{DC}(\theta )-h_j(\theta )$ is a convex problem and a valid lower bound.
3. Discard partitions whose $l_j$ is too high.
4. Subdivide the partition with the lowest $l_j$ and recompute the bounds.
5. Stop when the lower bound is tight enough, then plug it into (6.1) or (6.4) in place of $\hat{h}(\hat{g})$.

The bounds are always valid, but convergence can be slow in high dimension, giving very conservative results.

Examples

One step of the lower search (illustrative)

Suppose ${ϵ}_{\text{abs}}=1.0$. At $\gamma =0.5$ the minimizer has ${\hat{e}}_{\text{orig}}=0.9$ and ${\hat{e}}_{\text{switch}}=1.2$, so $\hat{h}=0.45+1.2=1.65\ge 0$ and Condition 8 holds. Lemma 9 gives $\widehat{MR}\ge 1.65/1.0-0.5=1.15$ for every model with loss at most 1.0. The minimizer itself has $\widehat{MR}=1.2/0.9=1.33$. So ${\widehat{MCR}}_{-}\in [1.15,1.33]$, and lowering $\gamma$ while Condition 8 holds narrows the gap.

Connections

• Dinkelbach (1967) fractional programming minimizes a ratio by a sequence of parametric linear problems. The novelty here is the constraint on the denominator ${\hat{e}}_{\text{orig}}\le {ϵ}_{\text{abs}}$.
• Using the reweighted $n^2$-row sample is like augmenting data with “permuted” copies. A similar trick is used to build knockoff or null features.
• In MMM practice the “oracle” is just a weighted regression solver, so MCR for a ridge-type response model costs a few dozen solves; see Model Class Reliance for Linear and RKHS Model Classes.

See Also

• Model Class Reliance - Appendix C Proofs of the Binary Search Lemmas: every App C proof in full
• Model Class Reliance for Linear and RKHS Model Classes: exact subproblem solvers
• Model Class Reliance - Recidivism Case Study: Fig. 8 envelopes in practice
• Fisher Rudin Dominici 2019 - Model Class Reliance - Overview