Model Class Reliance for Linear and RKHS Model Classes

Summary

Under squared-error loss, linear and additive models allow a closed form. Proposition 15: $MR(f_{\beta })=1+\frac{2}{e_{\text{orig}}(f_{\beta })}\{\mathrm{Cov}(Y,X_1){\beta }_1-{\beta }_2^{\prime }\mathrm{Cov}(X_2,X_1){\beta }_1\}$, and ${\hat{e}}_{\text{switch}}(f_{\beta })$ costs $O(n)$. Any linear combination ${\xi }_{\text{orig}}{\hat{e}}_{\text{orig}}+{\xi }_{\text{switch}}{\hat{e}}_{\text{switch}}$ is a (possibly non-convex) quadratic in $\beta$ (Remark 16). With a quadratic norm constraint (ridge-type, Eq 7.4) or an RKHS norm constraint (Eq 7.6), each binary-search step is a QP1QC: one quadratic objective, one quadratic constraint, a trust-region-type problem that is solvable globally. Lemmas 17-18 give the loss bound $B_{\text{ind}}$ needed by the theory.

Overview

Throughout §7: $\mathcal{X}\subset {\mathbb{R}}^p$, $\mathcal{Y}\subset \mathbb{R}$, $L(f,(y,x_1,x_2))=(y-f(x_1,x_2){)}^2$, and $0<{\min }_{f\in \mathcal{F}}{\hat{e}}_{\text{orig}}(f)$. The section serves two purposes. It makes MR interpretable for linear models, and it makes empirical MCR exactly computable (global minima, despite non-convexity) for three classes: unconstrained linear, quadratically constrained linear, and kernel regression.

Main Content

Interpreting and computing MR for linear models (§7.1)

Proposition 15: MR for linear models (p. 26, Eqs 7.1-7.2)

Use squared-error loss, $y\in \mathbb{R}$, $x_1\in {\mathbb{R}}^{p_1}$ and $x_2\in {\mathbb{R}}^{p_2}$. Let $\beta =({\beta }_1,{\beta }_2)$ and $f_{\beta }(x)=x^{\prime }\beta =x_1^{\prime }{\beta }_1+x_2^{\prime }{\beta }_2$. Then

$$MR(f_{\beta })=1+\frac{2}{e_{\text{orig}}(f_{\beta })}\{\mathrm{Cov}(Y,X_1){\beta }_1-{\beta }_2^{\prime }\mathrm{Cov}(X_2,X_1){\beta }_1\},(7.1)$$

and for finite samples

$${\hat{e}}_{\text{switch}}(f_{\beta })=\frac{1}{n}\left\{{\mathbf{y}}^{\prime }\mathbf{y}-2{\left[\begin{array}{c}{\mathbf{X}}_1^{\prime }\mathbf{Wy}\\ {\mathbf{X}}_2^{\prime }\mathbf{y}\end{array}\right]}^{\prime }\beta +{\beta }^{\prime }\left[\begin{array}{cc}{\mathbf{X}}_1^{\prime }{\mathbf{X}}_1& {\mathbf{X}}_1^{\prime }\mathbf{W}{\mathbf{X}}_2\\ {\mathbf{X}}_2^{\prime }\mathbf{W}{\mathbf{X}}_1& {\mathbf{X}}_2^{\prime }{\mathbf{X}}_2\end{array}\right]\beta \right\},(7.2)$$

where $\mathbf{W}:=\frac{1}{n-1}(1_n{1}_n^{\prime }-{\mathbf{I}}_n)$.

Linear cost. ${\mathbf{X}}_1^{\prime }\mathbf{Wy}=\frac{1}{n-1}\{({\mathbf{X}}_1^{\prime }{1}_n)(1_n^{\prime }\mathbf{y})-{\mathbf{X}}_1^{\prime }\mathbf{y}\}$ and ${\mathbf{X}}_1^{\prime }\mathbf{W}{\mathbf{X}}_2=\frac{1}{n-1}\{({\mathbf{X}}_1^{\prime }{1}_n)(1_n^{\prime }{\mathbf{X}}_2)-{\mathbf{X}}_1^{\prime }{\mathbf{X}}_2\}$. Each needs $O(n)$ work, although (3.3) has $n(n-1)$ terms.

Additive models. Both results extend to $f_{g_1,g_2}(X_1,X_2)=g_1(X_1)+g_2(X_2)$, since permuting $X_1$ is the same as permuting $g_1(X_1)$ (as in Gregorutti et al. 2017, who derived the equivalent of (7.1) assuming $f_{\beta }=E(Y\mid X)$ and centered covariates).

Proof of Proposition 15 (App B.8, pp. 64-65)

Write $e_{\text{orig}}=\mathbb{E}[(Y-X_2^{\prime }{\beta }_2{)}^2]-2\mathbb{E}[(Y-X_2^{\prime }{\beta }_2)X_1^{\prime }]{\beta }_1+{\beta }_1^{\prime }\mathbb{E}[X_1{X}_1^{\prime }]{\beta }_1$. In $e_{\text{switch}}$, $X_1^{(a)}$ is independent of $(Y^{(b)},X_2^{(b)})$, so the cross term factorizes: $e_{\text{switch}}=\mathbb{E}[(Y-X_2^{\prime }{\beta }_2{)}^2]-2\mathbb{E}[Y-X_2^{\prime }{\beta }_2]\mathbb{E}[X_1^{\prime }]{\beta }_1+{\beta }_1^{\prime }\mathbb{E}[X_1{X}_1^{\prime }]{\beta }_1$. Subtracting,

$$e_{\text{switch}}(f_{\beta })=e_{\text{orig}}(f_{\beta })+2\mathrm{Cov}(Y-X_2^{\prime }{\beta }_2,X_1){\beta }_1=e_{\text{orig}}+2\mathrm{Cov}(Y,X_1){\beta }_1-2{\beta }_2^{\prime }\mathrm{Cov}(X_2,X_1){\beta }_1.$$

Divide by $e_{\text{orig}}$ to get (7.1).

Finite-sample half, Eq 7.2 (Eqs B.48-B.49, pp. 64-65). Start from the U-statistic form ${\hat{e}}_{\text{switch}}(f_{\beta })=\frac{1}{n(n-1)}{\sum }_{i=1}^n{\sum }_{j\ne i}(y_{[j]}-{\mathbf{X}}_{2[j,\cdot ]}{\beta }_2-{\mathbf{X}}_{1[i,\cdot ]}{\beta }_1{)}^2$. Here row $j$ supplies $(y,x_2)$ and row $i$ supplies $x_1$.

1. Expand the square inside the double sum. Each term is $(y_{[j]}-{\mathbf{X}}_{2[j,\cdot ]}{\beta }_2{)}^2-2(y_{[j]}-{\mathbf{X}}_{2[j,\cdot ]}{\beta }_2)({\mathbf{X}}_{1[i,\cdot ]}{\beta }_1)+({\mathbf{X}}_{1[i,\cdot ]}{\beta }_1{)}^2$.
2. Count the pure terms (B.48). Each of the two squared pieces depends on one index only, and each index value appears in $n-1$ ordered pairs. So

$$n(n-1){\hat{e}}_{\text{switch}}=(n-1)\sum _i(y_{[i]}-{\mathbf{X}}_{2[i,\cdot ]}{\beta }_2{)}^2-2\{\sum _i\sum _{j\ne i}({\mathbf{X}}_{1[i,\cdot ]}{\beta }_1)(y_{[j]}-{\mathbf{X}}_{2[j,\cdot ]}{\beta }_2)\}+(n-1)\sum _i({\mathbf{X}}_{1[i,\cdot ]}{\beta }_1{)}^2.(\text{B.48})$$

3. Simplify the braces term (B.49). Add and subtract the diagonal $j=i$: ${\sum }_i{\sum }_{j\ne i}={\sum }_i{\sum }_{j=1}^n-{\sum }_{i=j}$. The full double sum factorizes as $\left({\sum }_i{\mathbf{X}}_{1[i,\cdot ]}{\beta }_1\right)({\sum }_j(y_{[j]}-{\mathbf{X}}_{2[j,\cdot ]}{\beta }_2))=({\mathbf{X}}_1{\beta }_1{)}^{\prime }{1}_n{1}_n^{\prime }(\mathbf{y}-{\mathbf{X}}_2{\beta }_2)$. The diagonal is $({\mathbf{X}}_1{\beta }_1{)}^{\prime }(\mathbf{y}-{\mathbf{X}}_2{\beta }_2)$. Hence

$$\{\cdot \}=({\mathbf{X}}_1{\beta }_1{)}^{\prime }(1_n{1}_n^{\prime }-{\mathbf{I}}_n)(\mathbf{y}-{\mathbf{X}}_2{\beta }_2).(\text{B.49})$$

4. Plug back in and write in matrix form. $n(n-1){\hat{e}}_{\text{switch}}=(n-1)\Vert \mathbf{y}-{\mathbf{X}}_2{\beta }_2{\Vert }_2^2-2({\mathbf{X}}_1{\beta }_1{)}^{\prime }(1_n{1}_n^{\prime }-{\mathbf{I}}_n)(\mathbf{y}-{\mathbf{X}}_2{\beta }_2)+(n-1)\Vert {\mathbf{X}}_1{\beta }_1{\Vert }_2^2$. Divide by $n-1$. The matrix $\frac{1}{n-1}(1_n{1}_n^{\prime }-{\mathbf{I}}_n)$ is exactly $\mathbf{W}$:

$$n{\hat{e}}_{\text{switch}}=\Vert \mathbf{y}-{\mathbf{X}}_2{\beta }_2{\Vert }_2^2-2({\mathbf{X}}_1{\beta }_1{)}^{\prime }\mathbf{W}(\mathbf{y}-{\mathbf{X}}_2{\beta }_2)+\Vert {\mathbf{X}}_1{\beta }_1{\Vert }_2^2.$$

5. Collect terms in $\beta$. Expanding gives ${\mathbf{y}}^{\prime }\mathbf{y}-2{\mathbf{y}}^{\prime }{\mathbf{X}}_2{\beta }_2+{\beta }_2^{\prime }{\mathbf{X}}_2^{\prime }{\mathbf{X}}_2{\beta }_2-2{\beta }_1^{\prime }{\mathbf{X}}_1^{\prime }\mathbf{Wy}+2{\beta }_1^{\prime }{\mathbf{X}}_1^{\prime }\mathbf{W}{\mathbf{X}}_2{\beta }_2+{\beta }_1^{\prime }{\mathbf{X}}_1^{\prime }{\mathbf{X}}_1{\beta }_1$. In block form this is ${\mathbf{y}}^{\prime }\mathbf{y}-2[{\mathbf{X}}_1^{\prime }\mathbf{Wy};{\mathbf{X}}_2^{\prime }\mathbf{y}{]}^{\prime }\beta +{\beta }^{\prime }\left[\begin{array}{cc}{\mathbf{X}}_1^{\prime }{\mathbf{X}}_1& {\mathbf{X}}_1^{\prime }\mathbf{W}{\mathbf{X}}_2\\ {\mathbf{X}}_2^{\prime }\mathbf{W}{\mathbf{X}}_1& {\mathbf{X}}_2^{\prime }{\mathbf{X}}_2\end{array}\right]\beta$, which is (7.2). $\mathbf{W}$ is symmetric, so the cross term $2{\beta }_1^{\prime }{\mathbf{X}}_1^{\prime }\mathbf{W}{\mathbf{X}}_2{\beta }_2$ splits evenly across the two off-diagonal blocks.

Intuition. $\mathbf{W}$ has zeros on the diagonal and $\frac{1}{n-1}$ off it. It is the “average over all other rows” operator. The $\mathbf{W}$ appears only where $X_1$ meets $(y,X_2)$, because those are the only pairs the permutation separates.

Reading (7.1). MR exceeds 1 to the extent that the $X_1$ term $X_1^{\prime }{\beta }_1$ covaries with the part of $Y$ not already explained by $X_2^{\prime }{\beta }_2$, scaled by model accuracy. Two linear models with equal loss can split a shared signal between correlated $X_1$ and $X_2$ in different proportions, and so have very different MR. This is the Rashomon effect in its simplest form.

Linear model classes (§7.2)

${\mathcal{F}}_{\text{lm}}:=\{f_{\beta }:f_{\beta }(x)=x^{\prime }\beta ,\beta \in {\mathbb{R}}^p\}$.

Remark 16: Tractability of empirical MCR for linear model classes (p. 27, Eq 7.3)

For any $f_{\beta }\in {\mathcal{F}}_{\text{lm}}$ and fixed ${\xi }_{\text{orig}},{\xi }_{\text{switch}}\in \mathbb{R}$, the combination

$${\xi }_{\text{orig}}{\hat{e}}_{\text{orig}}(f_{\beta })+{\xi }_{\text{switch}}{\hat{e}}_{\text{switch}}(f_{\beta })(7.3)$$

is proportional in $\beta$ to $-2{\mathbf{q}}^{\prime }\beta +{\beta }^{\prime }\mathbf{Q}\beta$, with

$$\mathbf{Q}:={\xi }_{\text{orig}}{\mathbf{X}}^{\prime }\mathbf{X}+{\xi }_{\text{switch}}\left[\begin{array}{cc}{\mathbf{X}}_1^{\prime }{\mathbf{X}}_1& {\mathbf{X}}_1^{\prime }\mathbf{W}{\mathbf{X}}_2\\ {\mathbf{X}}_2^{\prime }\mathbf{W}{\mathbf{X}}_1& {\mathbf{X}}_2^{\prime }{\mathbf{X}}_2\end{array}\right],\mathbf{q}:={\xi }_{\text{orig}}{\mathbf{X}}^{\prime }\mathbf{y}+{\xi }_{\text{switch}}\left[\begin{array}{c}{\mathbf{X}}_1^{\prime }\mathbf{Wy}\\ {\mathbf{X}}_2^{\prime }\mathbf{y}\end{array}\right].$$

So each search step is an unconstrained, possibly non-convex QP. $\mathbf{Q}$ can be indefinite when $\xi$ has mixed signs, as in ${\hat{h}}_{+,\gamma }$ with $\gamma <0$.

Proof (App C.6). Apply Proposition 15 to ${\hat{e}}_{\text{switch}}$, use ${\hat{e}}_{\text{orig}}=\frac{1}{n}({\mathbf{y}}^{\prime }\mathbf{y}-2{\mathbf{y}}^{\prime }\mathbf{X}\beta +{\beta }^{\prime }{\mathbf{X}}^{\prime }\mathbf{X}\beta )$, and drop the constant ${\mathbf{y}}^{\prime }\mathbf{y}$ terms.

Regularized linear models (§7.3)

Definition: Quadratically constrained linear class (Eq 7.4, p. 27)

$${\mathcal{F}}_{\text{lm},r_{\text{lm}}}:=\{f_{\beta }:f_{\beta }(x)=x^{\prime }\beta ,\beta \in {\mathbb{R}}^p,{\beta }^{\prime }{\mathbf{M}}_{\text{lm}}\beta \le r_{\text{lm}}\},$$

with ${\mathbf{M}}_{\text{lm}}$ and $r_{\text{lm}}$ prespecified. This is the constrained form of ridge regression.

Search subproblem as QP1QC (§7.3.1, Eq 7.5, p. 28)

$$\underset{\beta }{\min }-2{\mathbf{q}}^{\prime }\beta +{\beta }^{\prime }\mathbf{Q}\beta \text{s.t.}{\beta }^{\prime }{\mathbf{M}}_{\text{lm}}\beta \le r_{\text{lm}}.(7.5)$$

This is a possibly non-convex quadratic program with one quadratic constraint (QP1QC). It is well studied and related to the trust-region problem (Boyd & Vandenberghe 2004; Pólik & Terlaky 2007; Park & Boyd 2017), so the §6 bounds are computationally tractable for this class. (Background, not stated in the paper: the S-lemma gives zero duality gap for a QP1QC, which is why global solutions are available despite non-convexity.)

Lemma 17: Loss upper bound for linear models (§7.3.2, p. 28)

Suppose ${\mathbf{M}}_{\text{lm}}$ is positive definite, $Y$ is bounded within a known range, and there is a known $r_X$ with $x^{\prime }{\mathbf{M}}_{\text{lm}}^{-1}x\le r_X$ for all $x\in {\mathcal{X}}_1\times {\mathcal{X}}_2$. Then Assumption 1 holds for ${\mathcal{F}}_{\text{lm},r_{\text{lm}}}$ under squared error with

$$B_{\text{ind}}=\max [\{\underset{y\in \mathcal{Y}}{\min }(y)-\sqrt{r_X{r}_{\text{lm}}}{\}}^2,\{\underset{y\in \mathcal{Y}}{\max }(y)+\sqrt{r_X{r}_{\text{lm}}}{\}}^2].$$

In practice $r_X$ can be approximated from the empirical distribution of $X$ and $Y$. The constraints on $X$ and $\beta$ are complementary: if ${\mathbf{M}}_{\text{lm}}$ is diagonal, its smallest entries are the directions in which $\beta$ is least restricted and $x$ is most restricted.

Proof (App C.7). Bound the loss by maximizing or minimizing $x^{\prime }\beta$ subject to $x^{\prime }{\mathbf{M}}_{\text{lm}}^{-1}x\le r_X$ and ${\beta }^{\prime }{\mathbf{M}}_{\text{lm}}\beta \le r_{\text{lm}}$ (C.17). The paper notes (p. 75) that both constraints hold with equality at the solution (our gloss: the objective is bilinear, so scaling either $x$ or $\beta$ up to its constraint boundary can only increase a positive optimum). This is why it is valid to replace the inequality constraints with the equality (unit-norm) constraints after the change of variables. With the eigendecomposition $\mathbf{UD}{\mathbf{U}}^{\prime }={\mathbf{M}}_{\text{lm}}$, the change of variables $\tilde{x}=r_X^{-1/2}{\mathbf{D}}^{-1/2}{\mathbf{U}}^{\prime }x$, $\tilde{\beta }=r_{\text{lm}}^{-1/2}{\mathbf{D}}^{1/2}{\mathbf{U}}^{\prime }\beta$ turns this into $\max {\tilde{x}}^{\prime }\tilde{\beta }\sqrt{r_X{r}_{\text{lm}}}$ over unit vectors, with optimum $\sqrt{r_X{r}_{\text{lm}}}$. The minimum is $-\sqrt{r_X{r}_{\text{lm}}}$. The squared error is largest at an extreme $y$ paired with an extreme prediction.

Regression in a reproducing kernel Hilbert space (§7.4)

Definition: Kernel regression class ${\mathcal{F}}_{\mathbf{D},r_k}$ (Eqs 7.6-7.7, pp. 28-29)

Let $\mathbf{D}$ be an $R\times p$ dictionary of reference points (rows in $\mathcal{X}={\mathbb{R}}^p$), $k$ a prespecified positive-definite kernel, $\mu$ a prespecified estimate of $\mathbb{E}Y$, and ${\mathbf{K}}_{\mathbf{D}}$ the $R\times R$ matrix with ${\mathbf{K}}_{\mathbf{D}[i,j]}=k({\mathbf{D}}_{[i,\cdot ]},{\mathbf{D}}_{[j,\cdot ]})$. Then

$${\mathcal{F}}_{\mathbf{D},r_k}=\{f_{\alpha }:f_{\alpha }(x)=\mu +\sum _{i=1}^{R}k(x,{\mathbf{D}}_{[i,\cdot ]}){\alpha }_{[i]},\Vert f_{\alpha }{\Vert }_k\le r_k,\alpha \in {\mathbb{R}}^R\},(7.6)$$ $$\Vert f_{\alpha }{\Vert }_k:=\sum _{i=1}^R\sum _{j=1}^R{\alpha }_{[i]}{\alpha }_{[j]}k({\mathbf{D}}_{[i,\cdot ]},{\mathbf{D}}_{[j,\cdot ]})={\alpha }^{\prime }{\mathbf{K}}_{\mathbf{D}}\alpha .(7.7)$$

The similarity to each reference point is a regression feature. This allows nonlinear and non-additive structure.

Search subproblem for RKHS class as QP1QC (§7.4.1, Eqs 7.8-7.11, pp. 29-30)

Given a test sample $\mathbf{Z}=[\mathbf{y}\mathbf{X}]$:

• let ${\mathbf{K}}_{\text{orig}}$ be $n\times R$ with ${\mathbf{K}}_{\text{orig}[i,j]}=k({\mathbf{X}}_{[i,\cdot ]},{\mathbf{D}}_{[j,\cdot ]})$;
• let ${\mathbf{Z}}_{\text{switch}}=[{\mathbf{y}}_{\text{switch}}{\mathbf{X}}_{\text{switch}}]$ be the $n(n-1)\times (1+p)$ matrix with rows $\{({\mathbf{y}}_{[i]},{\mathbf{X}}_{1[j,\cdot ]},{\mathbf{X}}_{2[i,\cdot ]}):i\ne j\}$;
• let ${\mathbf{K}}_{\text{switch}}$ be $n(n-1)\times R$ with ${\mathbf{K}}_{\text{switch}[i,j]}=k({\mathbf{X}}_{\text{switch}[i,\cdot ]},{\mathbf{D}}_{[j,\cdot ]})$.

Then minimizing ${\xi }_{\text{orig}}{\hat{e}}_{\text{orig}}(f_{\alpha })+{\xi }_{\text{switch}}{\hat{e}}_{\text{switch}}(f_{\alpha })$ over ${\mathcal{F}}_{\mathbf{D},r_k}$ is

$$\underset{\alpha }{\min }\frac{{\xi }_{\text{orig}}}{n}\Vert \mathbf{y}-\mu -{\mathbf{K}}_{\text{orig}}\alpha {\Vert }_2^2+\frac{{\xi }_{\text{switch}}}{n(n-1)}\Vert {\mathbf{y}}_{\text{switch}}-\mu -{\mathbf{K}}_{\text{switch}}\alpha {\Vert }_2^2\text{s.t.}{\alpha }^{\prime }{\mathbf{K}}_{\mathbf{D}}\alpha <r_k,(7.8\text{-}7.9)$$

again a QP1QC. Derivation: ${\hat{e}}_{\text{orig}}(f_{\alpha })=\frac{1}{n}{\sum }_i\{{\mathbf{y}}_{[i]}-\mu -{\sum }_{j}k({\mathbf{X}}_{[i,\cdot ]},{\mathbf{D}}_{[j,\cdot ]}){\alpha }_{[j]}{\}}^2=\frac{1}{n}\Vert \mathbf{y}-\mu -{\mathbf{K}}_{\text{orig}}\alpha {\Vert }_2^2$ (7.10-7.11), and likewise ${\hat{e}}_{\text{switch}}(f_{\alpha })=\frac{1}{n(n-1)}\Vert {\mathbf{y}}_{\text{switch}}-\mu -{\mathbf{K}}_{\text{switch}}\alpha {\Vert }_2^2$.

Lemma 18: Loss upper bound for RKHS regression (§7.4.2, p. 30)

Suppose $Y$ is bounded within a known range and there is a known $r_{\mathbf{D}}$ with $v(x{)}^{\prime }{\mathbf{K}}_{\mathbf{D}}^{-1}v(x)\le r_{\mathbf{D}}$ for all $x\in {\mathcal{X}}_1\times {\mathcal{X}}_2$, where $v:{\mathbb{R}}^p\to {\mathbb{R}}^R$ and $v(x{)}_{[i]}=k(x,{\mathbf{D}}_{[i,\cdot ]})$. Then Assumption 1 holds for ${\mathcal{F}}_{\mathbf{D},r_k}$ under squared error with

$$B_{\text{ind}}=\max [\{\underset{y\in \mathcal{Y}}{\min }(y)-(\mu +\sqrt{r_{\mathbf{D}}{r}_k}){\}}^2,\{\underset{y\in \mathcal{Y}}{\max }(y)+(\mu +\sqrt{r_{\mathbf{D}}{r}_k}){\}}^2].$$

Proof as given in the paper (App C.8, pp. 75-76). The proof follows the structure of C.7. From (7.7), the largest possible output of $f_{\alpha }\in {\mathcal{F}}_{\mathbf{D},r_k}$ is

$$\mu +\underset{x\in {\mathbb{R}}^p,\alpha \in {\mathbb{R}}^R}{\max }\sum _{i=1}^{R}k(x,{\mathbf{D}}_{[i,\cdot ]}){\alpha }_{[i]}=\mu +\underset{x,\alpha }{\max }v(x{)}^{\prime }\alpha \text{s.t.}v(x{)}^{\prime }{\mathbf{K}}_{\mathbf{D}}^{-1}v(x)\le r_{\mathbf{D}},{\alpha }^{\prime }{\mathbf{K}}_{\mathbf{D}}\alpha \le r_k.$$

1. Relax. Replace $v(x)$, which ranges over the image of the feature map, by an arbitrary vector $z\in {\mathbb{R}}^R$ with $z^{\prime }{\mathbf{K}}_{\mathbf{D}}^{-1}z\le r_{\mathbf{D}}$. The feasible set gets larger, so the maximum can only grow: $\le \mu +{\max }_{z,\alpha \in {\mathbb{R}}^R}{z}^{\prime }\alpha$ s.t. $z^{\prime }{\mathbf{K}}_{\mathbf{D}}^{-1}z\le r_{\mathbf{D}}$, ${\alpha }^{\prime }{\mathbf{K}}_{\mathbf{D}}\alpha \le r_k$.
2. Reuse C.17. This is the same problem as (C.17), with $({\mathbf{K}}_{\mathbf{D}},r_k)$ in place of $({\mathbf{M}}_{\text{lm}},r_{\text{lm}})$ and $(z,r_{\mathbf{D}})$ in place of $(x,r_X)$. Its optimum is $\sqrt{r_{\mathbf{D}}{r}_k}$. So the largest output is at most $\mu +\sqrt{r_{\mathbf{D}}{r}_k}$.
3. Lower side and conclusion. The paper states that the smallest output is “similarly” lower bounded by $-(\mu +\sqrt{r_{\mathbf{D}}{r}_k})$, and concludes that $B_{\text{ind}}$ is at most the displayed expression.

Equivalent shortcut (not the paper’s wording). Cauchy-Schwarz in the ${\mathbf{K}}_{\mathbf{D}}$ metric gives the same bound in one line: $|v(x{)}^{\prime }\alpha |\le \sqrt{v(x{)}^{\prime }{\mathbf{K}}_{\mathbf{D}}^{-1}v(x)}\sqrt{{\alpha }^{\prime }{\mathbf{K}}_{\mathbf{D}}\alpha }\le \sqrt{r_{\mathbf{D}}{r}_k}$.

Caveat on the lower output bound (our check, not flagged in the paper). The symmetric argument actually gives a minimum output of $\mu -\sqrt{r_{\mathbf{D}}{r}_k}$, not $-(\mu +\sqrt{r_{\mathbf{D}}{r}_k})$. The two agree only when $\mu =0$. For $\mu \ge 0$, $-(\mu +\sqrt{r_{\mathbf{D}}{r}_k})\le \mu -\sqrt{r_{\mathbf{D}}{r}_k}$, so the stated value is still a valid but loose lower bound. In that case the stated $B_{\text{ind}}$ is conservative, provided also $\max y+\sqrt{r_{\mathbf{D}}{r}_k}\ge 0$ (true for any nonnegative outcome): its second term $\{\max y+\mu +\sqrt{r_{\mathbf{D}}{r}_k}{\}}^2$ is then at least the tight $\{\max y-\mu +\sqrt{r_{\mathbf{D}}{r}_k}{\}}^2$. For $\mu <0$ the stated lower output bound is not valid, and the stated $B_{\text{ind}}$ can understate the worst-case loss. The safe general form is

$$B_{\text{ind}}=\max [\{\underset{y}{\min }(y)-(\mu +\sqrt{r_{\mathbf{D}}{r}_k}){\}}^2,\{\underset{y}{\max }(y)-(\mu -\sqrt{r_{\mathbf{D}}{r}_k}){\}}^2].$$

In practice, centering $Y$ so that $\mu \approx 0$ makes the two forms coincide.

Examples

MR of a two-variable linear model (illustrative use of Eq 7.1)

Let $X_1,X_2$ have unit variance with correlation $\rho$, $Y=X_1+X_2+\epsilon$ and $\mathrm{Var}(\epsilon )=1$. The model $f_{\beta }$ with $\beta =(1,1)$ has $e_{\text{orig}}=1$, $\mathrm{Cov}(Y,X_1)=1+\rho$ and $\mathrm{Cov}(X_2,X_1)=\rho$. So $MR=1+2\{(1+\rho )-\rho \}=3$, whatever $\rho$ is. Now take $\rho =0.9$ and the alternative $\beta =(0,1.95)$. Its $e_{\text{orig}}=\mathrm{Var}(X_1+X_2-1.95X_2)+1=\mathrm{Var}(X_1-0.95X_2)+1=1+0.9025-1.71+1=1.19$, only 19% worse, yet $MR(f_{(0,1.95)})=1$. With $ϵ\approx 0.2$, the Rashomon set contains models with MR from 1 to above 3 on $X_1$. MCR exposes this; a single fit hides it.

Marketing use

For a ridge-constrained linear response model on adstocked channel spends, Remark 16 and (7.5) make MCR for any channel exactly computable with a trust-region solver in a few dozen solves. Swapping ${\mathbf{M}}_{\text{lm}}$ for a prior-precision matrix links this to a MAP or ridge Bayesian MMM (Bayesian Estimation and Priors for MMM).

Connections

• The RKHS class is the finite-dictionary form of kernel ridge regression, closely related to the Gaussian Process Regression posterior mean. The norm bound $r_k$ is the frequentist counterpart of the GP prior scale.
• Equation (7.1) shows MR depends on the residualized covariance of $Y$ with $X_1$ given the model’s own use of $X_2$. That is why MR can be large for a variable with zero marginal correlation, and vice versa.
• Regularization Bias and the Partially Linear Model: ridge-type constraints that make MCR computable also bias individual coefficients.

See Also

• Model Class Reliance - Binary Search Computation: the outer loop these subproblems plug into
• Model Class Reliance - Recidivism Case Study: RKHS class applied with an RBF kernel
• Fisher Rudin Dominici 2019 - Model Class Reliance - Overview