existing in a single probability space.

We note that Lemma D.1 establishes that
$\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})$ and
$\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})$ coincide almost
surely in the high-dimensional limit. As such, the squared error loss of these
two estimates coincide almost surely in the limit, and we may write

$\displaystyle\lim_{D\rightarrow\infty}D^{-1}\mathrm{R}^{D}_{\pi}(\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D}))$
$\displaystyle=\lim_{D\rightarrow\infty}D^{-1}\mathbb{E}\left[\mathbb{E}[\|\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})-\beta\|_{F}^{2}\mid\beta]\right]$
$\displaystyle=\lim_{D\rightarrow\infty}D^{-1}\mathbb{E}\big{[}\mathbb{E}[\|\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})-\beta\|_{F}^{2}+\|\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})-\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})\|_{F}^{2}+$
$\displaystyle
2\mathrm{tr}((\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})-\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D}))^{\top}(\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})-\beta))\mid\beta]\big{]}$
$\displaystyle=\lim_{D\rightarrow\infty}\mathbb{E}\left[D^{-1}\mathbb{E}[\|\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})-\beta\|_{F}^{2}\mid\beta]\right]$
$\displaystyle=\lim_{D\rightarrow\infty}\mathbb{E}\left[\sigma^{2}Q-\sigma^{4}(D-2Q-2)\mathbb{E}[\|\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\dagger}\|_{F}^{2}|\beta]\right]$
$\displaystyle=\sigma^{2}Q-\sigma^{4}\lim_{D\rightarrow\infty}\mathbb{E}[(D-2Q-2)\|\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\dagger}\|_{F}^{2}]$
$\displaystyle=\sigma^{2}Q-\sigma^{4}\lim_{D\rightarrow\infty}\mathbb{E}[\mathrm{tr}[(\tilde{\Sigma}+\sigma^{2}I_{Q})^{-1}]+o(1)]$
$\displaystyle=\sigma^{2}Q-\sigma^{4}\mathrm{tr}[(\tilde{\Sigma}+\sigma^{2}I_{Q})^{-1}].$

The third line comes from linearity of expectation and that
$\|\hat{\beta}_{\mathrm{ECov}}-\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}\|\overset{a.s.}{\rightarrow}0.$
The fourth line comes from Lemma 4.2. The second to last line comes from Lemma
D.2.

We next recognize that
$\mathrm{tr}[(\tilde{\Sigma}+\sigma^{2}I_{Q})^{-1}]=\sum_{q=1}^{Q}(\lambda_{q}+\sigma^{2})^{-1},$
where $\lambda_{1},\dots,\lambda_{Q}$ are the eigenvalues of $\tilde{\Sigma}.$
Accordingly we may write,

$\displaystyle\lim_{D\rightarrow\infty}D^{-1}\mathrm{R}^{D}_{\pi}(\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D}))$
$\displaystyle=\sigma^{2}Q-\sigma^{4}\sum_{q=1}^{Q}(\lambda_{q}+\sigma^{2})^{-1}.$

Furthermore since we obtain $\hat{\beta}_{\mathrm{ID}}(\mathcal{D}_{D})$ by
applying $\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})$ independently to each
dataset, we analogously obtain

$\displaystyle\lim_{D\rightarrow\infty}D^{-1}\mathrm{R}^{D}_{\pi}(\hat{\beta}_{\mathrm{ID}}(\mathcal{D}_{D}))=\sigma^{2}Q-\sigma^{4}\sum_{q=1}^{Q}(\tilde{\Sigma}_{q,q}+\sigma^{2})^{-1}.$

Putting these expressions together, we obtain

$\displaystyle\lim_{D\rightarrow\infty}D^{-1}\left[\mathrm{R}^{D}_{\pi}(\hat{\beta}_{\mathrm{ID}}(\mathcal{D}_{D}))-\mathrm{R}^{D}_{\pi}(\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D}))\right]$
$\displaystyle=\sigma^{4}\left[\sum_{q=1}^{Q}(\lambda_{q}+\sigma^{2})^{-1}-\sum_{q=1}^{Q}(\tilde{\Sigma}_{q,q}+\sigma^{2})^{-1}\right].$

Finally, including the additional scaling by $\sigma^{-2}Q^{-1}$ we obtain

$\displaystyle\mathrm{Gain}(\pi,\sigma^{2})=\sigma^{2}Q^{-1}\left[\sum_{q=1}^{Q}(\lambda_{q}+\sigma^{2})^{-1}-\sum_{q=1}^{Q}(\tilde{\Sigma}_{q,q}+\sigma^{2})^{-1}\right]$

as desired.

######  Lemma D.1.

Under the conditions of Lemma 5.2,
$\lim_{D\rightarrow\infty}\|\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})-\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})\|_{F}=0$
almost surely.

###### Proof.

Note that under the conditions of Lemma 5.2, Lemma 4.4 provides that
$\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})$ and
$\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})$ differ only when
$\hat{\Sigma}^{\mathrm{MM}}$ is not positive definite; otherwise
$\hat{\Sigma}^{\mathrm{MM}}=\hat{\Sigma}.$ Since
$\hat{\Sigma}^{\mathrm{MM}}=D^{-1}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\top}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})-\sigma^{2}I_{Q},$
by Lemma D.3 $\hat{\Sigma}^{\mathrm{MM}}$ will be positive definite for all
$D$ above some $D^{\prime}$ almost surely, and so
$\hat{\beta}_{\mathrm{ECov}}(\mathcal{D}_{D})$ and
$\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}(\mathcal{D}_{D})$ become equal for
all $D$ large enough, implying strong convergence. ∎

######  Lemma D.2.

Under the conditions of Lemma 5.2,
$\lim_{D\rightarrow\infty}D\|\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\dagger}\|_{F}^{2}=\mathrm{tr}[(\tilde{\Sigma}+\sigma^{2}I_{Q})^{-1}]$
almost surely.

###### Proof.

Recall that
$\|\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\dagger}\|_{F}^{2}=\mathrm{tr}[(\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\top}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D}))^{-1}].$
As such, we may write
$D\|\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\dagger}\|_{F}^{2}=\mathrm{tr}[(D^{-1}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\top}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D}))^{-1}].$
By Lemma D.3
$D^{-1}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\top}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})\overset{a.s.}{\rightarrow}\tilde{\Sigma}+\sigma^{2}I_{Q},$
and so we can see that
$D\|\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\dagger}\|_{F}^{2}\overset{a.s.}{\rightarrow}\mathrm{tr}[(\tilde{\Sigma}+\sigma^{2}I_{Q})^{-1}]$
as desired. ∎

######  Lemma D.3.

Under the conditions of Lemma 5.2
$\lim_{D\rightarrow\infty}D^{-1}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\top}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})=\tilde{\Sigma}+\sigma^{2}I_{Q}$
almost surely.

###### Proof.

It suffices to show strong convergence element wise, as this implies strong
convergence in all other relevant norms. For convenience, let
$C^{(D)}\mathrel{\mathop{\mathchar
58\relax}}=D^{-1}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\top}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D}).$
Note that we may write each entry
$C_{q,q^{\prime}}^{(D)}=\sum_{d=1}^{D}D^{-1}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{q}_{d}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})_{d}^{q^{\prime}}$
as a sum of $D$ i.i.d. terms. Notably, each term
$\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{q}_{d}\cdot\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})_{d}^{q^{\prime}}$
is a product of two Gaussian random variables and is therefore sub-exponential
with some non-negative parameters $(\nu,\alpha)$ (see e.g. Wainwright [61,
Definition 2.7]). As a result, $C^{(D)}$ is then sub-exponential with
parameters $(D^{-\frac{1}{2}}\nu,D^{-1}\alpha).$ Therefore, for any constant
$b$ satisfying $0<b<\nu^{2}/\alpha,$ by Wainwright [61, Proposition 2.9] we
have that

$\mathbb{P}\left[\left|C^{(D)}_{q,q^{\prime}}-\mathbb{E}[C^{(D)}_{q,q^{\prime}}]\right|\geq
b\right]\leq 2\exp\\{-\frac{D}{2}b^{2}/\nu^{2}\\}.$

This rapid, exponential decay in tail probability with $D$ implies that for
small $b,$

$\sum_{D=1}^{\infty}\mathbb{P}\left[\left|C^{(D)}_{q,q^{\prime}}-\mathbb{E}[C^{(D)}_{q,q^{\prime}}]\right|\geq
b\right]\leq\infty.$

Therefore, by the Borel-Cantelli lemma we see that
$|C^{(D)}_{q,q^{\prime}}-\mathbb{E}[C^{(D)}_{q,q^{\prime}}]|\overset{a.s.}{\rightarrow}0.$
Since $\mathbb{E}[C^{(D)}]=\tilde{\Sigma}+\sigma^{2}I_{Q}$ for each $D,$ this
implies that
$\lim_{D\rightarrow\infty}D^{-1}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})^{\top}\hat{\beta}_{\mathrm{LS}}(\mathcal{D}_{D})=\tilde{\Sigma}+\sigma^{2}I_{Q}$
almost surely. ∎

###  D.2 Further discussion of Theorem 5.3

We here give further detail related to the proof of Theorem 5.3 and introduce
additional notation used in the remainder of the section. Recall from Lemma
5.2 that
$\mathrm{Gain}(\pi,\sigma^{2})=\sigma^{2}Q^{-1}[\sum_{q=1}^{Q}(\lambda_{q}+\sigma^{2})^{-1}-\sum_{q=1}^{Q}(\tilde{\Sigma}_{q,q}+\sigma^{2})^{-1}].$
For convenience, we will use $\ell\mathrel{\mathop{\mathchar
58\relax}}=\mathrm{diag}(\tilde{\Sigma})^{\downarrow}$ to denote the
$Q$-vector of diagonal entries of $\tilde{\Sigma}$ sorted in descending order.
Similarly, we take $\lambda$ to be the $Q$-vector of eigenvalues of
$\tilde{\Sigma},$ again sorted in descending order. Next, it is useful to
rewrite

$\mathrm{Gain}(\pi,\sigma^{2})=\sigma^{2}Q^{-1}\left[\vec{f}(\lambda)-\vec{f}(\ell)\right]$

where $\vec{f}(x)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{q=1}^{Q}f(x_{q})=\sum_{q=1}^{Q}(\sigma^{2}+x_{q})^{-1}$
(where $f(x)\mathrel{\mathop{\mathchar 58\relax}}=(\sigma^{2}+x)^{-1}$).

The key theoretical tool used in establishing Theorem 5.3 is the Schur-Horn
theorem. We state this result below, adapted from Horn [32, Theorem 5]. The
Schur-Horn theorem guarantees that $\lambda$ majorizes $\ell$. In particular,
an $N$-vector $a$ is said to majorize a second $N$-vector $b$ if
$\sum_{n=1}^{N}a_{n}=\sum_{n=1}^{N}b_{n}$ and for all $N^{\prime}\leq N,$

$\sum_{n=1}^{N^{\prime}}a_{n}^{\downarrow}\geq\sum_{n=1}^{N^{\prime}}b^{\downarrow}_{n},$

where for a vector $v,$ we use $v^{\downarrow}$ to denote the vector with the
same components as $v,$ sorted in descending order. As captured by Theorem
5.3, we can therefore see that $\mathrm{Gain}(\pi,\sigma^{2})$ is non-negative
for any $\tilde{\Sigma}$ by observing that $\vec{f}$ is Schur-convex (since
$f$ is convex).

######  Theorem D.4 (Schur-Horn).

A vector $\ell$ can be the diagonal of a Hermitian matrix with (repeated)
eigenvalues $\lambda$ if and only if $\lambda$ majorizes $\ell.$

###  D.3 Proof of Theorem 5.4

We here show that $\mathrm{Gain}(\pi,\sigma^{2})$ is upper bounded as

$\displaystyle\mathrm{Gain}(\pi,\sigma^{2})$
$\displaystyle\leq\sigma^{2}Q^{-1}f^{\prime\prime}(\lambda_{\mathrm{min}})\|\lambda\|_{2}\|\lambda-\ell\|_{2}$
$\displaystyle=2\sigma^{2}Q^{-1}\|\lambda\|_{2}\|\lambda-\ell\|_{2}/(\sigma^{2}+\lambda_{\mathrm{min}})^{3},$

and lower bounded as

$\displaystyle\mathrm{Gain}(\pi,\sigma^{2})$
$\displaystyle\geq\frac{1}{2}\sigma^{2}Q^{-1}f^{\prime\prime}(\lambda_{\mathrm{max}})\|\lambda-\ell\|^{2}$
$\displaystyle=\sigma^{2}Q^{-1}\|\lambda-\ell\|^{2}/(\sigma^{2}+\lambda_{\mathrm{max}})^{3},$

where $f^{\prime\prime}(x)\mathrel{\mathop{\mathchar
58\relax}}=\frac{d^{2}}{dx^{2}}f(x)$ where $f$ is as defined in Section D.2.

We obtain both bounds with quadratic approximations to $f$. In particular, we
define $g_{\alpha}$ as the $2^{\text{nd}}$ order Taylor approximation of $f$
expanded at $\alpha$,

$g_{\alpha}(x)\mathrel{\mathop{\mathchar
58\relax}}=f(\alpha)+f^{\prime}(\alpha)(x-\alpha)+\frac{1}{2}f^{\prime\prime}(\alpha)(x-\alpha)^{2},$

and note that by Lemma D.5

$\displaystyle\vec{g}_{\lambda_{\mathrm{max}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{max}}}(\ell)\leq\vec{f}(\lambda)-\vec{f}(\ell)\leq\vec{g}_{\lambda_{\mathrm{min}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{min}}}(\ell),$
(8)

where $\vec{g}_{\alpha}(x)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{q=1}^{Q}g_{\alpha}(x_{q})$.

#### Proof of upper bound.

We obtain the desired upper bound as follows.

Equation 8 and Lemma D.6 allow us to see

$\displaystyle\begin{split}\mathrm{Gain}(\pi,\sigma^{2})&\leq\sigma^{2}Q^{-1}\left[\vec{g}_{\lambda_{\mathrm{min}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{min}}}(\ell)\right]\\\
&=\frac{1}{2}\sigma^{2}Q^{-1}f^{\prime\prime}(\lambda_{\mathrm{min}})(\|\lambda\|^{2}-\|\ell\|^{2}).\end{split}$
(9)

Since $f^{\prime\prime}$ is positive on $\mathbb{R}_{+},$ the problem reduces
to upper bounding $\|\lambda\|^{2}-\|\ell\|^{2}$.

In particular, we find

$\displaystyle\|\lambda\|^{2}-\|\ell\|^{2}$
$\displaystyle=\langle\lambda+\ell,\lambda-\ell\rangle$ (10)
$\displaystyle\leq\|\lambda+\ell\|\|\lambda-\ell\|$ // by Cauchy-Schwarz (11)
$\displaystyle=\sqrt{\|\lambda\|^{2}+2\langle\lambda,\ell\rangle+\|\ell\|^{2}}\,\|\lambda-\ell\|$
(12)
$\displaystyle\leq\sqrt{\|\lambda\|^{2}+2\|\lambda\|\|\ell\|+\|\ell\|^{2}}\,\|\lambda-\ell\|\,\,\,\,$
// by Cauchy-Schwarz (13) $\displaystyle\leq 2\|\lambda\|\|\lambda-\ell\|$
$\displaystyle\text{// Since }\|\lambda\|\geq\|\ell\|,$ (14)

where we can see that $\|\lambda\|\geq\|\ell\|$ by noting that $\|\cdot\|^{2}$
is Schur convex, and again appealing to the Schur-Horn Theorem. The desired
upper bound obtains by combining Equations 9 and 10.

#### Proof of lower bound.

We begin as we did for the upper bound. Equation 8 and Lemma D.6 allow us to
see

$\displaystyle\begin{split}\mathrm{Gain}(\pi,\sigma^{2})&\geq\sigma^{2}Q^{-1}\left[\vec{g}_{\lambda_{\mathrm{max}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{max}}}(\ell)\right]\\\
&=\frac{1}{2}\sigma^{2}Q^{-1}f^{\prime\prime}(\lambda_{\mathrm{max}})(\|\lambda\|^{2}-\|\ell\|^{2}).\end{split}$
(15)

Since, again, $f^{\prime\prime}$ is positive on $\mathbb{R}_{+},$ the problem
reduces to lower bounding $\|\lambda\|^{2}-\|\ell\|^{2}$.

In particular, we would like to show
$\|\lambda\|^{2}-\|\ell\|^{2}\geq\|\lambda-\ell\|^{2}$. We can arrive at this
bound with a particular expansion of $\|\lambda-\ell\|^{2}$ and using Lemma
D.7, which again leverages the fact that $\lambda$ majorizes $\ell$.
Specifically, we write

$\displaystyle\begin{split}\|\lambda-\ell\|^{2}&=\langle\lambda-\ell,\lambda\rangle-\langle\lambda-\ell,\ell\rangle\\\
&=\|\lambda\|^{2}-\left[\langle\lambda,\ell\rangle+\langle\lambda-\ell,\ell\rangle\right]\\\
&=\|\lambda\|^{2}-\|\ell\|^{2}-\left[\langle\lambda,\ell\rangle-\langle\ell,\ell\rangle+\langle\lambda-\ell,\ell\rangle\right]\\\
&=\|\lambda\|^{2}-\|\ell\|^{2}-2\langle\lambda-\ell,\ell\rangle\\\
&\leq\|\lambda\|^{2}-\|\ell\|^{2}\end{split}$ (16)

where the last line follows from Lemma D.7, which provides that
$\langle\lambda-\ell,\ell\rangle\geq 0$ since, from the Schur-Horn theorem for
any $Q^{\prime}\leq Q\ \sum_{q=1}^{Q^{\prime}}\lambda_{q}-\ell_{q}\geq 0,$ and
$\ell$ has non-negative, non-increasing entries. We obtain the desired lower
bound by combining Equations 15 and 16.

######  Lemma D.5.

Let $\lambda$ and $\ell$ be $Q$-vectors of non-negative reals with non-
increasing entries, and let $\lambda$ majorize $\ell.$ Consider
$\vec{f}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{Q}\rightarrow\mathbb{R},x\mapsto\sum_{q=1}^{Q}f(x_{q})=\sum_{q=1}^{Q}(\sigma^{2}+x_{q})^{-1}$
(where $f(v)\mathrel{\mathop{\mathchar 58\relax}}=(\sigma^{2}+v)^{-1}$) for
any $\sigma^{2}>0,$ and define $g_{\alpha}$ to be the $2^{\text{nd}}$ order
Taylor approximation of $f$ expanded at $\alpha$,

$g_{\alpha}(x)\mathrel{\mathop{\mathchar
58\relax}}=f(\alpha)+f^{\prime}(\alpha)(x-\alpha)+\frac{1}{2}f^{\prime\prime}(\alpha)(x-\alpha)^{2}.$

Then

$\vec{g}_{\lambda_{\mathrm{max}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{max}}}(\ell)\leq\vec{f}(\lambda)-\vec{f}(\ell)\leq\vec{g}_{\lambda_{\mathrm{min}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{min}}}(\ell),$

where $\vec{g}_{\alpha}(x)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{q=1}^{Q}g_{\alpha}(x_{q})$ and
$\lambda_{\mathrm{max}}=\lambda_{1}$ and $\lambda_{\mathrm{min}}=\lambda_{Q}$
are the largest and smallest entries of $\lambda,$ respectively.

###### Proof.

If there are indices $q$ for which $\lambda_{q}=\ell_{q}$, remove them (they
do not affect $\vec{f}(\ell)-\vec{f}(\lambda)$). If all are equal, $\lambda=d$
and so the result is trivial, otherwise we have $Q\geq 2$ entries with
$\lambda_{q}\neq\ell_{q}$.

We begin with the lower bound; the upper bound follows similarly. For this, it
suffices to show
$\vec{f}(\lambda)-\vec{f}(\ell)-\left(\vec{g}_{\lambda_{\mathrm{max}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{max}}}(\ell)\right)\geq
0$.

We first express this difference as an inner product

$\displaystyle\vec{f}(\lambda)-\vec{f}(\ell)-\left(\vec{g}_{\lambda_{\mathrm{max}}}(\lambda)-\vec{g}_{\lambda_{\mathrm{max}}}(\ell)\right)$
$\displaystyle=\sum_{q=1}^{Q}\left[(f-g_{\lambda_{\mathrm{max}}})(\lambda_{q})-(f-g_{\lambda_{\mathrm{max}}})(\ell_{q})\right]$
$\displaystyle=\sum_{q=1}^{Q}(\lambda_{q}-\ell_{q})\left[\frac{(f-g_{\lambda_{\mathrm{max}}})(\lambda_{q})-(f-g_{\lambda_{\mathrm{max}}})(\ell_{q})}{\lambda_{q}-\ell_{q}}\right]$
$\displaystyle\text{ // defining each }\,h_{q}\mathrel{\mathop{\mathchar
58\relax}}=\frac{(f-g_{\lambda_{\mathrm{max}}})(\lambda_{q})-(f-g_{\lambda_{\mathrm{max}}})(\ell_{q})}{\lambda_{q}-\ell_{q}}$
$\displaystyle=\sum_{q=1}^{Q}(\lambda_{q}-\ell_{q})h_{q}$
$\displaystyle=\langle\lambda-\ell,h\rangle$

where $h=[h_{1},h_{2},\dots,h_{Q}]^{\top}.$

We will complete our proof by leveraging Lemma D.7, which provides that
$\langle a,b\rangle\geq 0$ for any $Q$-vector $a$ satisfying
$\sum_{q=1}^{Q}a_{q}=0$ and $\sum_{q=1}^{Q^{\prime}}a_{q}\geq 0$ for every
$Q^{\prime}\leq Q,$ and $Q$-vector $b$ with non-increasing entries.

It therefore remains only to show that $\lambda-\ell$ and $h$ satisfy the
conditions of Lemma D.7. Since the entries of $\lambda$ and $\ell$ are taken
to be in descending order, the condition that
$\sum_{q=1}^{Q^{\prime}}(\lambda-\ell)_{q}\geq 0$ for any $Q^{\prime}\leq Q,$
follows from the Schur-Horn theorem. Likewise, this theorem provides that
$\sum_{q=1}^{Q}\lambda_{q}=\sum_{q=1}^{Q}\ell_{q},$ and therefore that
$\sum_{q=1}^{Q}(\lambda-\ell)_{q}=0,$ so that $\lambda-\ell$ meets condition
(2) of the lemma.

We next confirm that $h$ has non-increasing entries by considering an
expansion of the expressions for each $h_{q}$. In particular, observe that

$\displaystyle h_{q}$
$\displaystyle=\frac{(f-g_{\lambda_{\mathrm{max}}})(\lambda_{q})-(f-g_{\lambda_{\mathrm{max}}})(\ell_{q})}{\lambda_{q}-\ell_{q}}$
$\displaystyle=(\lambda_{q}-\ell_{q})^{-1}\left\\{f(\lambda_{q})-f(\ell_{q})-\left[g_{\lambda_{\mathrm{max}}}(\lambda_{q})-g_{\lambda_{\mathrm{max}}}(\ell_{q})\right]\right\\}$
$\displaystyle=(\lambda_{q}-\ell_{q})^{-1}\big{\\{}\frac{(\sigma^{2}+\ell_{q})-(\sigma^{2}+\lambda_{q})}{(\sigma^{2}+\ell_{q})(\sigma^{2}+\lambda_{q})}-$
$\displaystyle\left[(\lambda_{q}-\ell_{q})f^{\prime}(\lambda_{\mathrm{max}})+\frac{1}{2}((\lambda_{q}-\lambda_{\mathrm{max}})^{2}-(\ell_{q}-\lambda_{\mathrm{max}})^{2})f^{\prime\prime}(\lambda_{\mathrm{max}})\right]\big{\\}}$
$\displaystyle=(\sigma^{2}+\lambda_{\mathrm{max}})^{-2}-(\sigma^{2}+\ell_{q})^{-1}(\sigma^{2}+\lambda_{q})^{-1}-\frac{1}{2}(\lambda_{q}-\ell_{q})^{-1}(\sigma^{2}+\lambda_{\mathrm{max}})^{-3}\left[\lambda_{q}^{2}-\ell_{q}^{2}-2\lambda_{\mathrm{max}}(\lambda_{q}-\ell_{q})\right]$
$\displaystyle=(\sigma^{2}+\lambda_{\mathrm{max}})^{-2}-(\sigma^{2}+\ell_{q})^{-1}(\sigma^{2}+\lambda_{q})^{-1}-\frac{1}{2}(\sigma^{2}+\lambda_{\mathrm{max}})^{-3}\left[\lambda_{q}+\ell_{q}-2\lambda_{\mathrm{max}}\right].$

Next define
$\phi(a,b)=(\sigma^{2}+\lambda_{\mathrm{max}})^{-2}-(\sigma^{2}+a)^{-1}(\sigma^{2}+b)^{-1}-\frac{1}{2}(\sigma^{2}+\lambda_{\mathrm{max}})^{-3}\left[b+a-2\lambda_{\mathrm{max}}\right],$
so that for each $q,h_{q}=\phi(\ell_{q},\lambda_{q}).$ Now, for
$q^{\prime}>q,$ we may write

$\displaystyle\begin{split}h_{q^{\prime}}-h_{q}&=\phi(\ell_{q^{\prime}},\lambda_{q^{\prime}})-\phi(\ell_{q},\lambda_{q})\\\
&=\int_{\ell_{q}}^{\ell_{q^{\prime}}}\frac{\partial}{\partial
a}\phi(a,\lambda_{q})da+\int_{\lambda_{q}}^{\lambda_{q^{\prime}}}\frac{\partial}{\partial
b}\phi(\ell_{q^{\prime}},b)db.\end{split}$ (17)

Next note that

$\frac{\partial}{\partial
a}\phi(a,b)=(\sigma^{2}+a)^{-2}(\sigma^{2}+b)^{-1}-\frac{1}{2}(\sigma^{2}+\lambda_{\mathrm{max}})^{-3}$

and

$\frac{\partial}{\partial
b}\phi(a,b)=(\sigma^{2}+a)^{-1}(\sigma^{2}+b)^{-2}-\frac{1}{2}(\sigma^{2}+\lambda_{\mathrm{max}})^{-3}$

from which we can see that $\frac{\partial}{\partial a}\phi(a,b)$ and
$\frac{\partial}{\partial b}\phi(a,b)$ are positive for
$a,b\in[\lambda_{\mathrm{min}},\lambda_{\mathrm{max}}].$ Accordingly, Equation
17 provides that $h_{q^{\prime}}-h_{q}\leq 0,$ since
$\ell_{q^{\prime}}\leq\ell_{q}$ and $\lambda_{q^{\prime}}\leq\lambda_{q}$ for
$q^{\prime}>q,$ because the entries of $\ell$ and $\lambda$ are non-
increasing. Therefore $h_{q^{\prime}}\leq h_{q},$ completing the proof. ∎

######  Lemma D.6.

Consider the quadratic function
$\vec{h}(x)=\sum_{q=1}^{Q}(ax_{q}^{2}+bx_{q}+c)$. Let
$\lambda,\ell\in\mathbb{R}^{Q}$ satisfy
$\sum_{q=1}^{Q}\lambda_{q}=\sum_{q=1}^{Q}\ell_{q}$. Then

$\vec{h}(\ell)-\vec{h}(\lambda)=a(\|\ell\|^{2}-\|\lambda\|^{2}).$

###### Proof.

The result follows from the simple algebraic rearrangement below,

$\displaystyle\vec{h}(\ell)-\vec{h}(\lambda)$
$\displaystyle=\sum_{q=1}^{Q}(a\ell_{q}^{2}+b\ell_{q}+c)-(a\lambda_{q}^{2}+b\lambda_{q}+c)$
$\displaystyle=\sum_{q=1}^{Q}a\ell_{q}^{2}-a\lambda_{q}^{2}$
$\displaystyle=a(\|\ell\|^{2}-\|\lambda\|^{2}).$

∎

######  Lemma D.7.

Let $x$ be a $Q$-vector satisfying for each $Q^{\prime}\leq
Q,\,\sum_{q=1}^{Q^{\prime}}x_{q}\geq 0$, and let $y$ be a $Q$-vector with non-
increasing entries. If additionally either (1) $y$ has non-negative entries or
(2) $\sum_{q=1}^{Q}x_{q}=0$ then $\langle x,y\rangle\geq
y_{Q}\sum_{q=1}^{Q}x_{q}\geq 0.$

###### Proof.

We first prove the lemma under condition (1) by induction. The base case of
$Q=1$ is trivial; $\langle x,y\rangle=x_{1}y_{1}$ and under (1) $x_{1}$ and
$y_{1}$ are non-negative and under (2) $x_{1}=0.$

Assume the result holds for $Q-1$. Then

$\displaystyle\langle x,y\rangle$ $\displaystyle=y_{Q}x_{Q}+\langle
x_{1\mathrel{\mathop{\mathchar 58\relax}}Q-1},y_{1\mathrel{\mathop{\mathchar
58\relax}}Q-1}\rangle$ (18) $\displaystyle\geq
y_{Q}x_{Q}+y_{Q-1}\sum_{q=1}^{Q-1}x_{q}$ // by the inductive hypothesis (19)
$\displaystyle\geq y_{Q}x_{Q}+y_{Q}\sum_{q=1}^{Q-1}x_{q}\,\,\,\,$
$\displaystyle\text{// since }y_{Q-1}\geq y_{Q}\text{ and
}\sum_{q=1}^{Q-1}x_{q}\geq 0$ (20) $\displaystyle=y_{Q}\sum_{q=1}^{Q}x_{q}\geq
0$ $\displaystyle\text{// since }y_{Q}\text{ and }\sum_{q=1}^{Q}x_{q}\text{
are non-negative.}$ (21)

This provides the desired inductive step, completing the proof under condition
(1).

Under condition (2), consider $y^{\prime}=y-\min_{q}y_{q}\mathbf{1}_{Q}.$ Then

$\displaystyle\langle x,y\rangle$ $\displaystyle=\langle
x,y^{\prime}\rangle+\min_{q}y_{q}\langle x,\mathbf{1}_{Q}\rangle$
$\displaystyle=\langle x,y^{\prime}\rangle.$

Since $y^{\prime}$ now has non-negative entries, condition (1) is satisfied
and the result follows. ∎

###  D.4 Proof of Corollary 5.5

We establish the corollary with a brief sequence of upper bounds following
from our initial upper bound in Theorem 5.3. In particular, the theorem
provides

$\mathrm{Gain}(\pi,\sigma^{2})\leq
2\sigma^{2}Q^{-1}\|\lambda^{\downarrow}\|\|\ell^{\downarrow}-\lambda^{\downarrow}\|/(\sigma^{2}+\lambda_{\mathrm{min}})^{3}.$

We begin by simplifying this upper bound. As a first step, note that

$\displaystyle\|\ell^{\downarrow}-\lambda^{\downarrow}\|^{2}$
$\displaystyle=\|\ell\|^{2}+\|\lambda\|^{2}-\langle\ell^{\downarrow},\lambda^{\downarrow}\rangle$
$\displaystyle\leq 2\|\lambda\|^{2}.$

As such, we can simplify our upper bound as

$\displaystyle\begin{split}\mathrm{Gain}(\pi,\sigma^{2})&\leq
2\sigma^{2}Q^{-1}\|\lambda\|\|\ell^{\downarrow}-\lambda^{\downarrow}\|/(\sigma^{2}+\lambda_{\mathrm{min}})^{3}\\\
&\leq
4\sigma^{2}Q^{-1}\|\lambda\|^{2}/(\sigma^{2}+\lambda_{\mathrm{min}})^{3}\\\
&\leq
4\kappa^{2}\lambda_{\mathrm{min}}^{2}\sigma^{2}/(\sigma^{2}+\lambda_{\mathrm{min}})^{3}\end{split}$
(22)

where $\kappa\mathrel{\mathop{\mathchar
58\relax}}=\lambda_{\mathrm{max}}/\lambda_{\mathrm{min}}$ is the condition
number of $\tilde{\Sigma}.$

We then obtain the first bound by noting that

$\displaystyle\lambda_{\mathrm{min}}^{2}\sigma^{2}/(\sigma^{2}+\lambda_{\mathrm{min}})^{3}$
$\displaystyle\leq\lambda_{\mathrm{min}}^{2}\sigma^{2}/(\sigma^{2})^{2}/\lambda_{\mathrm{min}}$
$\displaystyle\leq\lambda_{\mathrm{min}}/\sigma^{2}$

and the second by noting that

$\displaystyle\lambda_{\mathrm{min}}^{2}\sigma^{2}/(\sigma^{2}+\lambda_{\mathrm{min}})^{3}$
$\displaystyle\leq\lambda_{\mathrm{min}}^{2}\sigma^{2}/(\lambda_{\mathrm{min}})^{3}$
$\displaystyle\leq\sigma^{2}/\lambda_{\mathrm{min}}.$

Substituting these expressions into Equation 22 provides the desired
expressions in Corollary 5.5.

##  Appendix E Experiments Supplementary Results and Details

###  E.1 Simulations additional details

We here describe the details of the simulated datasets discussed in Section 6.
For each of the dimensions $D$ and each of the 20 replicates we first
generated covariate effects for all $Q=10$ datasets. To do this, we began by
setting $\Sigma;$ for the correlated covariate effects experiments (Figure 1
Left) we generating a random $Q\times Q$ matrix of orthonormal vectors $U$ and
set $\Sigma=U\mathrm{diag}([2^{0},2^{-1},\dots,2^{Q-1}]^{\top})U^{\top},$ and
for independent effects (Figure 1 Right) we set $\Sigma=I_{Q}.$ We then
simulated covariate effects as
$\beta_{d}\overset{i.i.d.}{\sim}\mathcal{N}(0,\Sigma).$

We next simulated the design matrices. For each dataset $q,$ we chose a random
number of data points $N^{q}\sim\text{Pois}(\lambda=1000)$, and for each data
point $n=1,\dots,N^{q}$ sampled $X^{q}_{n}\sim\mathcal{N}(0,(1/1000)I_{D})$ so
that for each dataset $\mathbb{E}[X^{q\top}X^{q}]=I_{D}.$ Finally, we
generated each response as
$Y^{q}_{n}\overset{indep}{\sim}\mathcal{N}(X^{q\top}_{n}\beta^{q},1).$

For $\hat{\beta}_{\mathrm{EData}},$ we estimated the $D\times D$ covariance
$\Gamma$ by maximum marginal likelihood. We did this with an EM algorithm
closely related to Algorithm 1. See e.g. Gelman et al. [24, Chapter 15
sections 4-5] for an explanation of the relevant conjugacy calculations in a
more general case that includes a hyper-prior on $\Gamma.$

###  E.2 Practical moment estimation for poorly conditioned problems

The moment based estimator (using $\hat{\Sigma}^{\mathrm{MM}}$ in Section 4)
is unstable in the two real data applications discussed in Section 6 due to
poor conditioning of the design matrices leading $\hat{\beta}_{\mathrm{LS}}$
to have high variance. To overcome this limitation, we instead used an adapted
moment estimation procedure which is less sensitive to this poor conditioning.
While, in agreement with Theorem 4.5, this approach performs worse than
$\hat{\beta}_{\mathrm{ECov}}$ (see Figure 3) we report it nonetheless because
it has lower computational cost and may be appealing for larger scale
applications. We describe this approach here. We note however that moment
based estimates of the sort we consider here do not naturally extend to
logistic regression and so are not reported for our application to CIFAR10.

We first introduce some additional notation. For each dataset $q$ consider the
reduced singular value decomposition
$X^{q}=S^{q}\mathrm{diag}(\omega^{q})R^{q\top},$ where $S^{q}$ and $R^{q}$ are
$N^{q}\times D$ and $D\times D$ matrices with orthonormal columns and
$\omega^{q}$ is a $D$-vector of non-negative singular values. Next define for
each dataset $W^{q}\mathrel{\mathop{\mathchar 58\relax}}=S^{q\top}X^{q}$ and
$Z^{q}\mathrel{\mathop{\mathchar 58\relax}}=S^{q\top}Y^{q},$ which we may
interpret as a $D\times D$ matrix of pseudo-covariates and $D$-vector of
pseudo-responses, respectively. Next define $\Omega$ to be the $Q\times Q$
matrix with entries $\Omega_{q,q^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}=\mathrm{tr}(W^{q\top}W^{q^{\prime}})^{-1}$ and
$\vec{\sigma}^{2}\mathrel{\mathop{\mathchar
58\relax}}=[\sigma_{1}^{2},\sigma_{2}^{2},\dots,\sigma_{Q}^{2}]^{\top}.$
Lastly, let $Z=[Z^{1},Z^{2},\dots,Z^{Q}]$ be the $D\times Q$ matrix of all
pseudo-responses. Our new moment estimator is

$\hat{\Sigma}^{\mathrm{MM}}\mathrel{\mathop{\mathchar
58\relax}}=[Z^{\top}Z-D\mathrm{diag}(\vec{\sigma}^{2})]\odot\Omega.$

We next show hat $\mathbb{E}[\hat{\Sigma}^{\mathrm{MM}}]=\Sigma$ under correct
prior and likelihood specification. Note first that if $\delta$ is a $D\times
Q$ matrix with i.i.d. standard normal entries we may write

$Z\overset{d}{=}[W^{1}\beta^{1},W^{2}\beta^{2},\dots,W^{Q}\beta^{Q}]+\delta\mathrm{diag}(\vec{\sigma}^{2}).$

As such, for each $q$ and $q^{\prime},$ we have that

$\displaystyle\mathbb{E}[(Z^{\top}Z)_{q,q^{\prime}}]$
$\displaystyle=\mathbb{E}[Z^{q\top}Z^{q}]$
$\displaystyle=\mathbb{E}[\beta^{q\top}W^{q\top}W^{q^{\prime}}\beta^{q^{\prime}}]+\mathbb{I}[q=q^{\prime}]\sigma_{q}^{2}D$
$\displaystyle=\mathrm{tr}(W^{q\top}W^{q^{\prime}}\mathbb{E}[\beta^{q^{\prime}}\beta^{q\top}])+\mathbb{I}[q=q^{\prime}]\sigma_{q}^{2}D$
$\displaystyle=\Omega_{q,q^{\prime}}^{-1}\Sigma_{q,q^{\prime}}+\mathbb{I}[q=q^{\prime}]\sigma_{q}^{2}D.$

Accordingly, we can see that each entry of $\hat{\Sigma}^{\mathrm{MM}}$ has
expectation
$\mathbb{E}[\hat{\Sigma}^{\mathrm{MM}}_{q,q^{\prime}}]=\Sigma_{q,q^{\prime}},$
which establishes unbiasedness.

However, this moment estimate still has the limitation that it evaluates to a
non positive semidefinite matrix with positive probability. Under the
expectation that, in line with Theorem 4.3 the very small and negative
eigenvalues of $\hat{\Sigma}^{\mathrm{MM}}$ might lead to over-shrinking, we
performed an additional step of clipping these eigenvalues to force the
resulting estimate to be reasonably well conditioned. In particular, if our
initial estimate had eigendecomposition
$\hat{\Sigma}^{\mathrm{MM}}=U\mathrm{diag}(\lambda)U^{\top},$ we instead used
$\hat{\Sigma}^{\mathrm{MM}}=U\mathrm{diag}(\tilde{\lambda})U^{\top},$ where
for each $q,$ we have
$\tilde{\lambda}_{q}=\max(\lambda_{q},\lambda_{\mathrm{max}}/100)$ so that the
condition number of the modified estimate was at most 100. Though we did not
find the performance of the resulting estimates to be very sensitive to this
cutoff, we view requirement for these partly subjective implementation choices
required to make the $\hat{\beta}_{\mathrm{ECov}}^{\mathrm{MM}}$ effective in
practice to be a downside of the approach as compared to
$\hat{\beta}_{\mathrm{ECov}},$ which avoids such choices by estimating
$\Sigma$ by maximum marginal likelihood.

Compared to the iterative EM algorithms, which rely on matrix inversions at
each iteration, computation of $\hat{\Sigma}^{\mathrm{MM}}$ is much faster. In
each of our experiments, computing it requires less than one second.

Figure 3: Performances of additional methods on the law enforcement and blog
datasets. Uncertainty intervals are $\pm 1\texttt{SEM}.$

###  E.3 Allowing for non-zero means a priori in hierarchical Bayesian
estimates

In the development of our approach in Section 2 we imposed the restriction
that $\mathbb{E}[\beta_{d}]=0$ a priori. Though in general one might prefer to
let $\beta$ have some nontrivial mean (as Lindley and Smith [43] do in the
context of exchangeability of effects across datasets) this assumption
simplifies the resulting estimators, theory, and notation. When $\beta$ is
permitted to have a non-zero mean, conjugacy maintains and the methodology
presented in Section 3 may be updated to accommodate the change. While we omit
a full explanation of the tedious details of this variation, we include its
implementation in our code and the performance of the resulting empirical
Bayesian estimators in Figures 3, 4 and 5. From these empirical results we see
that removing this restriction has little impact on the performance of the
resulting estimators. Notably, our results in these figures reveal that the
same is true for choosing to include or exclude a prior mean for the
exchangeability of effects across datasets prior.

Figure 4: Performances of methods on the blog dataset, segmented by post type.
Uncertainty intervals are $\pm 1\texttt{SEM}.$ Figure 5: Performances of
methods on the law enforcement dataset, segmented by region and recorded
offense categorization. Uncertainty intervals are $\pm 1\texttt{SEM}.$

###  E.4 Additional details on datasets

In each of the two regression applications, for each component dataset, we
mean centered and variance-normalized the responses. Additionally, we
Winsorized the responses by dataset; in particular, we clipped values more
than 2 standard deviations from the mean.

#### BlogFeedback Data Set details

Given the nature of the features included in the blog dataset used in the main
text (which are summarizing characteristics rather than readable text), we
believe it may be possible to find the blog post that corresponds to a
particular data point. But we believe it is unlikely that the dataset directly
contains any personally identifiable information. The blog information was
obtained by web-crawling on publicly posted pages, so it is unlikely that
consent for inclusion of the content into this dataset was obtained.

#### Communities and Crime Dataset details

All data in this dataset was obtained through official channels. This dataset
is composed of statistics aggregated at the community level, so it is less
likely (though not impossible) to contain personally identifiable information.
Since it contains demographic, census, and crime data, it is unlikely to
contain offensive content.

#### CIFAR10 details.

For the tasks car vs. cat, car vs. dog, truck vs. cat, and truck vs. dog we
used $N^{q}=100$ data points. For the tasks car vs. deer, car vs. horse, truck
vs. deer, and truck vs. horse we used $N^{q}=1000$ data points.

We generated the pre-trained neural network embeddings using a variational
auto-encoder (VAE) [36]. We adapted our VAE implementation from ALIBI DETECT
[58], here. See also notebooks/2021_05_12_CIFAR10_VAE_embeddings.ipynb for
details.

CIFAR10 is composed from a subset of the 80 million tiny images dataset. As is
currently acknowledged on the 80 million tiny images website, this larger
dataset is known to contain offensive images and images obtained without
consent (https://groups.csail.mit.edu/vision/TinyImages/). However, given the
benign nature of the 10 image classes in CIFAR10, we expect it does not
contain offensive or personally identifiable content. These data were also
obtained by web-crawling, so it is unlikely that consent for inclusion of the
content into this dataset was obtained.

Figure 6: Performances of methods on CIFAR10 segmented by binary
classification task. Uncertainty intervals are $\pm 1\texttt{SEM}.$

###  E.5 Software Licenses

We here report the software used to generate our results and their associated
licenses.

All of our experiments were implemented in python, which is licensed under the
PSF license. For ease of reproducibility, ran our experiments and generated
our plots IPython in Jupyter notebooks; this software is covered by a modified
BSD license.

For our application to transfer learning using CIFAR10, we used a variational
auto-encoder implementation adapted from ALIBI DETECT [58], which uses the
Apache licence. Our implementation of our EM algorithm uses TensorFlow [1],
which is licensed under the MIT license.

We made frequent use of python packages numpy and scipy and matplotlib. These
are large libraries with components covered different licenses. See
github.com/scipy/scipy/blob/master/LICENSES_bundled.txt for scipy,
github.com/numpy/numpy/blob/main/LICENSES_bundled.txt for numpy, and
github.com/matplotlib/matplotlib/tree/master/LICENSE for matplotlib.