result, $n_{1}\widehat{\Delta}_{1}/\Delta_{1}\sim\chi_{n_{1}}^{2}$ and
$\mathds{P}[n_{1}\widehat{\Delta}_{1}\leqslant{n_{1}\Delta_{1}}/{2}]\leqslant\exp(-cn_{1}),$
cf. (53b). Thus,
$\mathds{P}_{\mathcal{H}_{0}}[\widehat{S}>0]\leqslant\exp(-cn_{1})+2\exp\left(-cn_{1}\Delta_{1}\right)+2\exp\left(-{cn_{1}^{2}\Delta_{1}^{2}}/{\bar{r}}\right)$
as claimed. ∎

###  A.3 Proof of Corollary 1

For simplicity we assume $\Delta_{0}=\Delta_{1}=\Delta$; the general case is
similar. Recall that $\Delta^{2}\leqslant 1$. Recall also that
$r:=\max\\{r_{0},r_{1}\\}$ and $\bar{r}:=\min\\{r,n\\}$.

$\boldsymbol{{1}^{o}}$. We first look at the reverse direction: assume that

$cn\Delta\min\left\\{1,\frac{n\Delta}{\bar{r}}\right\\}\geqslant\log(1/\delta)$
(54)

which, by (15), corresponds to
$\max\\{\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1],\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0]\\}\leqslant
2C\delta=O(\delta)$. Choosing the second term in the minimum in (54), we get

$n\Delta\geqslant\sqrt{\log(1/\delta)\bar{r}/c}=\sqrt{\log(1/\delta)\min\\{r,n\\}/c},$

whence

$n=\Omega\left(\min\left\\{\frac{\log(1/\delta)}{\Delta^{2}},\frac{\sqrt{r\log(1/\delta)}}{\Delta}\right\\}\right).$
(55)

On the other hand, choosing the first term in the minimum in (54) yields
$n=\Omega(\log(1/\delta)/\Delta)$, which corresponds to the missing (so far)
term in the sample complexity bound (17) (recall that $\Delta\leqslant 1$).
Thus, (17) is indeed necessary to guarantee that
$\max\\{\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1],\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0]\\}=O(\delta)$
as per (15).

$\boldsymbol{{2}^{o}}$. Conversely, assume that

$cn\Delta\geqslant\min\left\\{\frac{\log(1/\delta)}{\Delta},\sqrt{r\log(1/\delta)}+\log(1/\delta)\right\\},$
(56)

which corresponds to the sufficient sample size as per (17). Meanwhile, (54)
can be rewritten as

$\displaystyle
cn\Delta\geqslant\max\left\\{1,\frac{\bar{r}}{n\Delta}\right\\}\log(1/\delta)$
$\displaystyle=\max\left\\{1,\min\left\\{\frac{1}{\Delta},\frac{r}{n\Delta}\right\\}\right\\}\log(1/\delta)$
(57)
$\displaystyle=\min\left\\{\frac{1}{\Delta},\max\left\\{1,\frac{r}{n\Delta}\right\\}\right\\}\log(1/\delta),$

where in the last step we used that $\Delta\leqslant 1$. Clearly, the first
case for the minimum in (56) is identical to the first case for the minimum in
(57). On the other hand, the second case for the minimum in (56) implies that
$n\Delta\geqslant\log(1/\delta)$ and $n^{2}\Delta^{2}\geqslant
r\log(1/\delta)$, i.e., the second case in (57). ∎

###  A.4 Proof of Proposition 2

Recall the decomposition of the type I error (all probabilities are
conditional on $X^{(0)},X^{(1)}$):

$\displaystyle\;\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X^{(0)},X^{(1)}]$
$\displaystyle=\mathds{P}\bigg{[}\frac{1}{\widehat{\tau}_{0}}\|\xi^{(0)}\|^{2}_{X^{(0)}}-\widehat{r}_{0}+\widehat{r}_{1}-\frac{1}{\widehat{\tau}_{1}}\|\xi^{(1)}\|^{2}_{X^{(1)}}+\frac{2}{\widehat{\tau}_{1}\sigma_{1}}\langle
X^{(1)}(\theta_{1}-\theta_{0}),\xi^{(1)}\rangle\geqslant\frac{n\widehat{\Delta}_{1}}{\widehat{\tau}_{1}\sigma_{1}^{2}}\bigg{]}$
$\displaystyle=\mathds{P}\bigg{[}\frac{\widehat{\tau}_{1}}{\widehat{\tau}_{0}}\|\xi^{(0)}\|^{2}_{X^{(0)}}-\widehat{\tau}_{1}\widehat{r}_{0}+\widehat{\tau}_{1}\widehat{r}_{1}-\|\xi^{(1)}\|^{2}_{X^{(1)}}+\frac{2}{\sigma_{1}}\langle
X^{(1)}(\theta_{1}-\theta_{0}),\xi^{(1)}\rangle\geqslant\frac{n\widehat{\Delta}_{1}}{\sigma_{1}^{2}}\bigg{]}$
$\displaystyle\leqslant\mathds{P}\bigg{[}\widehat{r}_{1}-\|\xi^{(1)}\|^{2}_{X^{(1)}}\geqslant\frac{n\widehat{\Delta}_{1}}{5\sigma_{1}^{2}}\bigg{]}+\mathds{P}\bigg{[}\frac{1}{\sigma_{1}}\langle
X^{(1)}(\theta_{1}-\theta_{0}),\xi^{(1)}\rangle\geqslant\frac{n\widehat{\Delta}_{1}}{10\sigma_{1}^{2}}\bigg{]}$
$\displaystyle\quad+\mathds{P}\bigg{[}\frac{\widehat{\tau}_{1}}{\widehat{\tau}_{0}}\left(\|\xi^{(0)}\|^{2}_{X^{(0)}}-\widehat{r}_{0}\right)\geqslant\frac{n\widehat{\Delta}_{1}}{5\sigma_{1}^{2}}\bigg{]}+\mathds{P}\bigg{[}(\widehat{\tau}_{1}-1)\widehat{r}_{1}\geqslant\frac{n\widehat{\Delta}_{1}}{5\sigma_{1}^{2}}\bigg{]}+\mathds{P}\bigg{[}\widehat{\tau}_{1}\bigg{(}\frac{1}{\widehat{\tau}_{0}}-1\bigg{)}\widehat{r}_{0}\geqslant\frac{n\widehat{\Delta}_{1}}{5\sigma_{1}^{2}}\bigg{]}.$
(58)

As in the proof of Proposition 1, the sum of the terms in the penultimate line
of (58) is bounded by

$2\exp\bigg{(}-\frac{cn\widehat{\Delta}_{1}}{\sigma_{1}^{2}}\min\bigg{\\{}1,\frac{n\widehat{\Delta}_{1}}{\widehat{r}_{1}\sigma_{1}^{2}}\bigg{\\}}\bigg{)}.$

Using that $\widehat{\tau}_{0},$ $\widehat{\tau}_{1}$ and
$\|\xi^{(0)}\|^{2}_{X^{(0)}}-\widehat{r}_{0}$ are conditionally independent
and $\mathds{P}[\widehat{\tau}_{k}\notin[\tfrac{1}{2},2]]\leqslant C\exp(-cn)$
for $k\in\\{0,1\\}$ due to (28), applying (53) and the union bound, we bound
the first term in the last line of (58) by

$\displaystyle\mathds{P}\bigg{[}\|\xi^{(0)}\|^{2}_{X^{(0)}}-\widehat{r}_{0}\geqslant\frac{n\widehat{\Delta}_{1}}{5\sigma_{1}^{2}}\bigg{]}+C\exp(-cn)\leqslant\exp\bigg{(}-\frac{cn\widehat{\Delta}_{1}}{\sigma_{1}^{2}}\min\bigg{\\{}1,\frac{n\widehat{\Delta}_{1}}{\widehat{r}_{0}\sigma_{1}^{2}}\bigg{\\}}\bigg{)}+C\exp(-cn).$

Moreover, applying (28) to $\widehat{\tau}_{1}$ and noting that
$\widehat{r}_{1}\leqslant n$ a.s., we bound the next term as

$\mathds{P}\bigg{[}(\widehat{\tau}_{1}-1)\geqslant\frac{n\widehat{\Delta}_{1}}{5\widehat{r}_{1}\sigma_{1}^{2}}\bigg{]}\leqslant
2\exp\bigg{(}-\frac{c_{3}n^{2}\widehat{\Delta}_{1}}{\widehat{r}_{1}\sigma_{1}^{2}}\min\bigg{\\{}1,\frac{n\widehat{\Delta}_{1}}{\widehat{r}_{1}\sigma_{1}^{2}}\bigg{\\}}\bigg{)}\leqslant
2\exp\bigg{(}-\frac{c_{3}n\widehat{\Delta}_{1}}{\sigma_{1}^{2}}\min\bigg{\\{}1,\frac{n\widehat{\Delta}_{1}}{\widehat{r}_{1}\sigma_{1}^{2}}\bigg{\\}}\bigg{)}.$

In order to estimate the last term in the right-hand side of (58), we use that
$\mathds{P}[\widehat{\tau}_{1}\geqslant 2]\leqslant 2\exp(-cn)$ by (28) and
that $\widehat{\tau}_{0}$ and $\widehat{\tau}_{1}$ are conditionally
independent. We then have

$\displaystyle\mathds{P}\bigg{[}\widehat{\tau}_{1}\bigg{(}\frac{1}{\widehat{\tau}_{0}}-1\bigg{)}\geqslant\frac{n\widehat{\Delta}_{1}}{5\widehat{r}_{0}\sigma_{1}^{2}}\bigg{]}$
$\displaystyle\leqslant
2\exp(-cn)+\mathds{P}\bigg{[}\bigg{(}\frac{1}{\widehat{\tau}_{0}}-1\bigg{)}\geqslant\frac{n\widehat{\Delta}_{1}}{10\widehat{r}_{0}\sigma_{1}^{2}}\bigg{]}$
$\displaystyle\leqslant
2\exp(-cn)+\mathds{P}\bigg{[}\widehat{\tau}_{0}\leqslant
1-\frac{1}{2}\min\bigg{\\{}\frac{n\widehat{\Delta}_{1}}{10\widehat{r}_{0}\sigma_{1}^{2}},1\bigg{\\}}\bigg{]}$
$\displaystyle\leqslant
4\exp(-c_{4}n)+2\exp\bigg{(}-\frac{c_{4}n\widehat{\Delta}_{1}}{\sigma_{1}^{2}}\min\bigg{\\{}1,\frac{n\widehat{\Delta}_{1}}{\widehat{r}_{0}\sigma_{1}^{2}}\bigg{\\}}\bigg{)}$

where in the second step we used that $\tfrac{1}{1+t}\leqslant
1-\tfrac{1}{2}\min[t,1]$ for $t\geqslant 0$, and in the end we used (28). ∎

##  Appendix B Proof of Theorem 2

Our goal in this section is to prove Theorem 2. We proceed in four steps
correspondingly implemented in Sections B.1–B.4. For simplicity, we introduce
the following concise notation for the samples:

$(X,Y)=(X^{(0)},Y^{(0)}),\quad(X^{\prime},Y^{\prime})=(X^{(1)},Y^{(1)}).$

Similarly, we denote $\xi:=\xi^{(0)}[=Y-X\theta_{0}]$ and
$\xi^{\prime}:=\xi^{(1)}[=Y^{\prime}-X^{\prime}\theta_{1}]$.

###  B.1 Reduction to fixed-design setup

We first show that one can pass to the fixed-design setup – namely, focus on
proving the bound

$\underset{\widehat{T}}{\inf}\underset{(\theta_{0},\theta_{1})\in\widehat{\Theta}}{\sup}\left\\{\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right\\}\geqslant
C\exp\left(-cn\Delta\min\left\\{1,\frac{n\Delta}{\texttt{r}}\right\\}\right).$
(59)

Here the infimum is over all measurable maps
$(\theta^{*},X,Y,X^{\prime},Y^{\prime})\to\\{0,1\\}$ as in (31), the supremum
over the set

$\widehat{\Theta}=\widehat{\Theta}(32\Delta):=\\{(\theta_{0},\theta_{1}):\max\\{\widehat{\Delta}_{0},\widehat{\Delta}_{1}\\}\geqslant
32\Delta\\}$ (60)

with $\widehat{\Delta}_{0},\widehat{\Delta}_{1}$ defined in (11); finally,
$\widehat{\texttt{r}}:=\min\\{\textup{rank}(\widehat{\boldsymbol{\Sigma}}_{0}),\textup{rank}(\widehat{\boldsymbol{\Sigma}}_{1})\\}$
with $\widehat{\boldsymbol{\Sigma}}_{k}=\frac{1}{n}X^{(k)\top}X^{(k)}$.
Moreover, when proving (59), we shall assume w.l.o.g. that $r_{0}\leqslant
r_{1}$, and recall that $\texttt{r}\geqslant 28$. Finally, from now on we
assume that

$\lambda_{\min}(\widehat{\boldsymbol{\Sigma}}_{0,\mathsf{\Gamma}}),\lambda_{\max}(\widehat{\boldsymbol{\Sigma}}_{1,\mathsf{\Gamma}})\in\left[\frac{1}{16},\frac{49}{16}\right],$
(61)

where $\widehat{\boldsymbol{\Sigma}}_{k,\mathsf{\Gamma}}$ is the top left
submatrix of $\widehat{\boldsymbol{\Sigma}}_{k}$ (for $k\in\\{0,1\\}$) at the
intersection of the first $\lfloor\texttt{r}/4\rfloor$ rows and columns; this
implies, in particular, that

$\textup{rank}(\widehat{\boldsymbol{\Sigma}}_{0,\mathsf{\Gamma}})=\left\lfloor{\texttt{r}}/{4}\right\rfloor.$

This is a non-restrictive assumption: indeed, in Section B.4 we shall prove
that

$\mathds{P}\left\\{\lambda_{\min}(\widehat{\boldsymbol{\Sigma}}_{0,\mathsf{\Gamma}}),\lambda_{\max}(\widehat{\boldsymbol{\Sigma}}_{1,\mathsf{\Gamma}})\in\left[\frac{1}{16},\frac{49}{16}\right]\right\\}\geqslant\frac{1}{8}.$
(62)

When combined with (59), (61) will readily yield (31). Indeed, by Markov’s
inequality

$\widehat{\Delta}_{0}\leqslant
32\Delta_{0}\;\;\text{and}\;\;\widehat{\Delta}_{1}\leqslant 32\Delta_{1}$

simultaneously with prob. $\geqslant 15/16$ over $X,X^{\prime}$. Under the
joint event (and so w.p. $\geqslant 1-7/8-1/16=1/16$) one has that
$\widehat{\Theta}(32\Delta)\subseteq\Theta(\Delta)$, i.e., the supremum in
(31) is over a larger set than in (59); thus,

$\displaystyle\underset{\widehat{T}}{\inf}\underset{(\theta_{0},\theta_{1})\in\Theta(\Delta)}{\sup}\left\\{\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0]\right\\}$
$\displaystyle\geqslant$
$\displaystyle\frac{1}{16}\underset{\widehat{T}}{\inf}\underset{(\theta_{0},\theta_{1})\in\widehat{\Theta}(32\Delta)}{\sup}\left\\{\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right\\}$
$\displaystyle\geqslant$
$\displaystyle\frac{C}{16}\exp\left(-cn\Delta\min\left\\{1,\frac{n\Delta}{\texttt{r}}\right\\}\right),$

which is (31). Thus, we can indeed focus on proving (59) with fixed design
matrices $X,X^{\prime}$ obeying (61). This is our next goal; Secs. B.2–B.3 are
dedicated to reaching it, and in Sec. B.4 we shall verify (62).

#### What is ahead.

Note that (59) comprises two bounds simultaneously: the rank-independent bound
$\exp(-cn\Delta)$ and the second bound which depends on r. These two bounds
shall be proved correspondingly in Sections B.2 and B.3. It turns out that for
the first bound it suffices to consider a further simplified testing problem,
where one observes both models $\\{\theta^{*},\bar{\theta}\\}$ rather than
just $\theta^{*}$, where

$\bar{\theta}:=\theta_{0}+\theta_{1}-\theta^{*}$

is the complementary to $\theta^{*}$ model in $\\{\theta_{0},\theta_{1}\\}$.
The problem then reduces to discriminating between the two simple hypotheses
$(\theta_{0},\theta_{1})=(\theta^{*},\bar{\theta})$ and
$(\theta_{0},\theta_{1})=(\bar{\theta},\theta^{*})$. Intuitively, the absence
of the rank in the corresponding sample complexity bound can be explained by
the fact that the testing problem reduces to a one-dimensional one since
$\theta_{1}-\theta_{0}$ is known. On the other hand, capturing the dependency
on r requires to take into account that the complementary model $\bar{\theta}$
actually is not observed. We capture this by putting a Gaussian prior on
$\bar{\theta}$ and carefully bounding the Bayes risk.

###  B.2 Rank-independent bound

Let $\bar{\theta}:=\theta_{0}+\theta_{1}-\theta^{*}$, so that
$\\{\theta^{*},\bar{\theta}\\}=\\{\theta_{0},\theta_{1}\\}$ as the two sets
regardless of the hypothesis. Now, observe that the two hypotheses
$\mathcal{H}_{0}:\theta_{0}=\theta^{*}$ and
$\mathcal{H}_{1}:\theta_{1}=\theta^{*}$ can be reformulated as the hypotheses
$(\theta_{0},\theta_{1})=(\theta^{*},\bar{\theta})$ and
$(\theta_{0},\theta_{1})=(\bar{\theta},\theta^{*})$ about the aggregated
parameter $(\theta_{0},\theta_{1})$. Since $\bar{\theta}$ is unknown, we are
dealing with a composite testing problem, and thus cannot apply the Neyman-
Pearson lemma. To put us in the two-point hypothesis testing situation, we can
simply fix a value of $\bar{\theta}$, and assume that it is also known – in
other words, consider the following testing problem:

$\boxed{\begin{aligned} \textit{Given the
data}\;n,\widehat{r}_{0},\widehat{r}_{1},(\theta^{*},\bar{\theta})\in\widehat{\Theta},\;(X,Y)\in\mathds{P}_{0}^{\otimes
n},\;(X^{\prime},Y^{\prime})\sim\mathds{P}_{1}^{\otimes n},\\\
\textit{test}\;\;\bar{\mathcal{H}}_{0}:\;(\theta^{*},\bar{\theta})=(\theta_{0},\theta_{1})\;\text{\em
against}\;\;\bar{\mathcal{H}}_{1}:(\theta^{*},\bar{\theta})=(\theta_{1},\theta_{0}).\end{aligned}}$
(2-point)

Clearly, (2-point) is a problem of testing between two simple hypotheses about
the unknown parameter $(\theta_{0},\theta_{1})\in\widehat{\Theta}$. By the
Neyman-Pearson lemma, the sum of type I and II error probabilities for any
test in (2-point) is lower-bounded by that for the likelihood-ratio test, and
this test writes

$\widehat{T}_{\textsf{LR}}=\mathds{1}\left\\{\|Y-X\theta^{*}\|^{2}+\|Y^{\prime}-X^{\prime}\bar{\theta}\|^{2}\geqslant\|Y-X\bar{\theta}\|^{2}+\|Y^{\prime}-X^{\prime}\theta^{*}\|^{2}\right\\}.$
(63)

On the other hand, (2-point) cannot be harder than the initial testing problem
considered in (59). Indeed, any test admissible in (59) is a mapping
$(\theta^{*},\bar{\theta},X,Y,X^{\prime},Y^{\prime})\to\\{0,1\\}$ that does
not depend on $\bar{\theta}$, whereas in (2-point) one is also allowed to use
the tests that do depend on $\bar{\theta}$ and thus are not
$(\theta^{*},X,Y,X^{\prime},Y^{\prime})$-measurable. As such, the left-hand
side of (59) admits the bound

$\displaystyle\underset{\widehat{T}:(\theta^{*},X,Y,X^{\prime},Y^{\prime})\to\\{0,1\\}}{\inf}$
$\displaystyle\underset{(\theta_{0},\theta_{1})\in\widehat{\Theta}}{\sup}\left\\{\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right\\}$
$\displaystyle\geqslant$
$\displaystyle\underset{(\theta^{*},\bar{\theta})\in\widehat{\Theta}}{\sup}\left\\{\mathds{P}_{\bar{\mathcal{H}}_{0}}[\widehat{T}_{\textsf{LR}}=1|X,X^{\prime}]+\mathds{P}_{\bar{\mathcal{H}}_{1}}[\widehat{T}_{\textsf{LR}}=0|X,X^{\prime}]\right\\},$

with $\widehat{T}_{\textsf{LR}}$ being the test given by (63). Fixing
$(\theta^{*},\bar{\theta})\in\widehat{\Theta}=\widehat{\Theta}(32\Delta)$,
under $\bar{\mathcal{H}}_{0}$ we get

$\displaystyle\mathds{P}_{\bar{\mathcal{H}}_{0}}[\widehat{T}_{\textsf{LR}}=1|X,X^{\prime}]$
$\displaystyle\geqslant\mathds{P}\left\\{\|Y-X\theta_{0}\|^{2}+\|Y^{\prime}-X^{\prime}\theta_{1}\|^{2}\geqslant\|Y-X\theta_{1}\|^{2}+\|Y^{\prime}-X^{\prime}\theta_{0}\|^{2}\;\middle|\;X,X^{\prime}\right\\}$
$\displaystyle=\mathds{P}\left\\{2\langle\xi,X(\theta_{0}-\theta_{1})\rangle+2\langle\xi^{\prime},X^{\prime}(\theta_{0}-\theta_{1})\rangle\geqslant\|X(\theta_{0}-\theta_{1})\|^{2}+\|X^{\prime}(\theta_{0}-\theta_{1})\|^{2}\middle|X,X^{\prime}\right\\}$
$\displaystyle\geqslant
C\exp\big{(}-c\max\\{\|X(\theta_{0}-\theta_{1})\|^{2},\|X^{\prime}(\theta_{0}-\theta_{1})\|^{2}\\}\big{)}=C\exp\big{(}-cn\max\\{\widehat{\Delta}_{0},\widehat{\Delta}_{1}\\}\big{)}.$

Here we first used that
$\langle\xi^{(k)},X^{(k)}(\theta_{0}-\theta_{1})\rangle\sim\mathcal{N}(0,\|X^{(k)}(\theta_{0}-\theta_{1})\|^{2})$
for $k\in\\{0,1\\}$ conditionally on $(X,X^{\prime})$, and then applied the
lower bound for the Gaussian tails (see [41, Eq. 7.1.13]):

$\mathds{P}[\mathcal{N}(0,1)\geqslant t]\geqslant C\exp(-ct^{2}),\quad\forall
t\geqslant 0.$

By symmetry, we also have the same bound for
$\mathds{P}_{\bar{\mathcal{H}}_{1}}[\widehat{T}_{\textsf{LR}}=0|X,X^{\prime}]$.
Now, taking $(\theta_{*},\bar{\theta})$ on the boundary of
$\widehat{\Theta}(32\Delta)$, i.e., such that
$\max[\widehat{\Delta}_{0},\widehat{\Delta}_{1}]=32\Delta$, we arrive at

$\displaystyle\underset{\widehat{T}:(\theta^{*},X,Y,X^{\prime},Y^{\prime})\to\\{0,1\\}}{\inf}\;\underset{(\theta_{0},\theta_{1})\in\widehat{\Theta}}{\sup}\left\\{\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right\\}\geqslant
C\exp(-c^{\prime}n\Delta).$ (64)

This is precisely the rank-independent part of (59). Next we deal with the
rank-dependent part.

###  B.3 Rank-dependent bound

We first observe that in the cases $n\Delta\leqslant 1$ and
$n\Delta\geqslant\texttt{r}/4$, the bound (59) follows from (64) up to a
change in constants. Hence, it suffices to focus on the range

$1\leqslant n\Delta\leqslant{\texttt{r}/4}.$ (65)

Instead of fixing the pair $(\theta^{*},\bar{\theta})$, we now only fix
$\theta^{*}$ and put on $\bar{\theta}$ a Gaussian prior centered at
$\theta^{*}$ with covariance corresponding to the constraint
$(\theta^{*},\bar{\theta})\in\widehat{\Theta}$ (cf. (68)). Note that, by
symmetry, this is equivalent to putting the same prior on
$(\theta_{0},\theta_{1})$, or the centered prior with the same covariance on
$\theta_{1}-\theta_{0}$ (cf. (69), but the exact expression is not important
for what follows in step $\boldsymbol{{1}^{o}}$ below). Technically, such
prior violates the constraint $(\theta_{0},\theta_{1})\in\widehat{\Theta}$, so
we have to verify that the event

$\mathcal{C}:=\\{(\theta_{0},\theta_{1})\in\widehat{\Theta}\\}$ (66)

has sufficient mass under this prior. (Note that this concentration step is
common in the literature on Bayesian lower bounds, see, e.g., [42, Sec. 5.4].)
To that end, we further proceed in three steps.

$\boldsymbol{{1}^{o}}$: Reduction to the unconstrained Bayes risk. We let
$\pi$ be any prior on $(\theta_{0},\theta_{1})\in\mathds{R}^{d}$, and let
$\pi_{\mathcal{C}}$ be the conditioning of $\pi$ to the event $\mathcal{C}$ in
(66):

$\pi_{\mathcal{C}}(\mathcal{E})=\frac{\pi(\mathcal{\mathcal{E}}\cap\mathcal{C})}{\pi(\mathcal{C})},\quad\forall\mathcal{E}\subseteq\mathds{R}^{2d}.$

In what follows, we identify events over $(\theta_{0},\theta_{1})$ with
subsets of $\mathds{R}^{2d}$; in particular, $\mathcal{C}$ is identified with
$\widehat{\Theta}=\widehat{\Theta}(32\Delta)$. Now, since $\pi_{\mathcal{C}}$
is supported on $\mathcal{C}$, we can bound the left-hand side of (59) as

$\displaystyle\underset{\widehat{T}}{\inf}\underset{(\theta_{0},\theta_{1})\in\widehat{\Theta}}{\sup}\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\geqslant\underset{\widehat{T}}{\inf}\;\mathds{E}_{\pi_{\mathcal{C}}}\Big{[}\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\Big{]}$

where $\mathds{E}_{\pi_{\mathcal{C}}}$ is the expectation over
$(\theta_{0},\theta_{1})\sim\pi_{\mathcal{C}}$, and the infimum on the right
is over the same set of admissible tests
$(\theta^{*},X,Y,X^{\prime},Y^{\prime})\to\\{0,1\\}$ as on the left. Now, let
$\widehat{T}_{\pi_{\mathcal{C}}}$ be the corresponding Bayes test (i.e., the
one on which the Bayes risk is attained):

$\displaystyle\underset{\widehat{T}}{\inf}\;\mathds{E}_{\pi_{\mathcal{C}}}\Big{[}\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\Big{]}=\mathds{E}_{\pi_{\mathcal{C}}}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\pi_{\mathcal{C}}}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}_{\pi_{\mathcal{C}}}=0|X,X^{\prime}]\right].$

On the other hand,

$\displaystyle\mathds{E}_{\pi}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\pi_{\mathcal{C}}}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}_{\pi_{\mathcal{C}}}=0|X,X^{\prime}]\right]$
$\displaystyle\leqslant\mathds{E}_{\pi_{\mathcal{C}}}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\pi_{\mathcal{C}}}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}_{\pi_{\mathcal{C}}}=0|X,X^{\prime}]\right]$
$\displaystyle\quad+2\pi(\mathds{R}^{2d}\setminus\mathcal{C}).$

Finally, since $\widehat{T}_{\pi_{\mathcal{C}}}$ is generally not the Bayes
test for $\pi$, we have

$\displaystyle\underset{\widehat{T}}{\inf}\;\mathds{E}_{\pi}\Big{[}\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\Big{]}\leqslant\mathds{E}_{\pi}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\pi_{\mathcal{C}}}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}_{\pi_{\mathcal{C}}}=0|X,X^{\prime}]\right].$

We conclude that

$\displaystyle\underset{\widehat{T}}{\inf}\underset{(\theta_{0},\theta_{1})\in\widehat{\Theta}}{\sup}\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]$
$\displaystyle\geqslant\underset{\widehat{T}}{\inf}\,\mathds{E}_{\pi}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right]$
(67) $\displaystyle\quad-2\pi(\mathds{R}^{2d}\setminus\mathcal{C});$

thus, it suffices to bound the Bayes risk associated with $\pi$ from below and
$\pi(\mathds{R}^{2d}\setminus\mathcal{C})$ from above.

$\boldsymbol{{2}^{o}}$: Choosing a prior and showing concentration. Let us
choose $\pi$ as follows: $\theta^{*}$ is fixed at an arbitrary value, and
$\theta_{1}-\theta_{0}$ is a vector supported on ${\mathcal{I}}:=\\{1,\lfloor
r/4\rfloor\\}$ and such that

$(\theta_{1}-\theta_{0})_{{\mathcal{I}}}\sim\mathcal{N}(0,\rho(\widehat{\boldsymbol{\Sigma}}_{0,\mathsf{\Gamma}})^{-1})\;\;\text{with}\;\;\rho:=\frac{64\Delta}{\lfloor\texttt{r}/4\rfloor},$
(68)

where $(u)_{{\mathcal{I}}}=[u_{1};...;u_{\lfloor r/4\rfloor}]$. By writing
$\mathcal{C}=\widehat{\Theta}(32\Delta)$, cf. (60), as
$\mathcal{C}=\mathcal{C}_{0}\cup\mathcal{C}_{1}$ with
$\mathcal{C}_{k}=\\{\widehat{\Delta}_{k}\geqslant 32\Delta\\}$ for
$k\in\\{0,1\\}$, and recalling that
$\widehat{\Delta}_{0}=\|\widehat{\boldsymbol{\Sigma}}_{0}^{1/2}(\theta_{1}-\theta_{0})\|^{2}=\frac{1}{n}\|X(\theta_{1}-\theta_{0})\|^{2}$,
we observe that

$\pi(\mathds{R}^{2d}\setminus\mathcal{C})\leqslant\pi(\mathds{R}^{2d}\setminus\mathcal{C}_{0})=\pi(\\{\widehat{\Delta}_{0}\leqslant
32\Delta\\}).$

Clearly,

$\tfrac{1}{\sqrt{n}}X(\theta_{1}-\theta_{0})\sim\mathcal{N}\left(0,\rho\boldsymbol{\Pi}_{X_{\mathcal{I}}}\right),$
(69)

where

$\boldsymbol{\Pi}_{X_{\mathcal{I}}}=X_{\mathcal{I}}^{\vphantom{\top}}(X_{\mathcal{I}}^{\top}X_{\mathcal{I}}^{\vphantom{\top}})^{-1}X_{\mathcal{I}}^{\top}=\frac{1}{n}X_{\mathcal{I}}^{\vphantom{\top}}\widehat{\boldsymbol{\Sigma}}_{0,\mathsf{\Gamma}}^{-1}X_{\mathcal{I}}^{\top},$
(70)

$X_{\mathcal{I}}$ being the submatrix of $X$ collecting the columns indexed by
${\mathcal{I}}$. Therefore, we have
$\widehat{\Delta}_{0}\sim\rho\chi^{2}_{\lfloor\texttt{r}/4\rfloor}$ and
$\widehat{\Delta}_{0}/(32\Delta)\sim\tfrac{2}{\lfloor\texttt{r}/4\rfloor}\chi^{2}_{\lfloor\texttt{r}/4\rfloor}$.
In combination with the bound (53b) for the left tail of $\chi^{2}_{s}$ this
gives

$\pi(\mathds{R}^{2d}\setminus\mathcal{C})\leqslant\exp\left(-c\texttt{r}\right)$

for some $c>0$. Now, recall that we are in the regime
$n\Delta\leqslant\texttt{r}/4$, cf. (65), and thus

$\exp(-c\texttt{r})\leqslant\exp\left(-\frac{c^{\prime}n^{2}\Delta^{2}}{\texttt{r}}\right).$

Recalling the result of $\boldsymbol{{1}^{o}}$ (namely (67)) we conclude that,
in order to establish the r-dependent part of (59), it suffices to lower-bound
the largest of the two Bayes risks associated with $\pi$ and $\widetilde{\pi}$
as

$\displaystyle\max\Big{\\{}$
$\displaystyle\underset{\widehat{T}}{\inf}\left\\{\mathds{E}_{\pi}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right]\right\\},$
$\displaystyle\underset{\widehat{T}}{\inf}\left\\{\mathds{E}_{\widetilde{\pi}}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right]\right\\}\Big{\\}}\geqslant
3\exp\left(-\frac{c^{\prime}n^{2}\Delta^{2}}{\texttt{r}}\right).$ (71)

In the next step we prove (71); it is in this step that we use condition (61)
on the design matrices.

$\boldsymbol{{3}^{o}}$: Lower-bounding the Bayes risk. For $\pi$ chosen in
$\boldsymbol{{2}^{o}}$, the Neyman-Pearson lemma gives

$\displaystyle\underset{\widehat{T}}{\inf}\mathds{E}_{\pi}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0|X,X^{\prime}]\right]\geqslant\mathds{E}_{\pi}\left[\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{MLR}}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}_{\textsf{MLR}}=0|X,X^{\prime}]\right]$

where $\widehat{T}_{\textsf{MLR}}$ is the marginal likelihood ratio test
associated with $\pi$ and given by

$\widehat{T}_{\textsf{MLR}}=\mathds{1}\left\\{Q_{\mathcal{H}_{0}}(Y,Y^{\prime}|X,X^{\prime})\leqslant
Q_{\mathcal{H}_{1}}(Y,Y^{\prime}|X,X^{\prime})\right\\};$

here $Q_{\mathcal{H}_{0}}(Y,Y^{\prime}|X,X^{\prime})$ (resp.,
$Q_{\mathcal{H}_{1}}(Y,Y^{\prime}|X,X^{\prime})$) is the marginal (over
$\bar{\theta}\sim\pi$) likelihood of $(Y,Y^{\prime})$ under $\mathcal{H}_{0}$
(resp., $\mathcal{H}_{1}$) conditionally on $(X,X^{\prime})$. Now, recalling
that $\mathcal{H}_{1}$ reads
$(\theta^{*},\bar{\theta})=(\theta_{1},\theta_{0})$ we get

$\displaystyle
Q_{\mathcal{H}_{1}}^{2}(Y,Y^{\prime}|X,X^{\prime})=\frac{\exp\big{(}-\|Y^{\prime}-X^{\prime}\theta^{*}\|^{2}-(Y-X\theta^{*})^{\top}\left(\boldsymbol{I}+n\rho\boldsymbol{\Pi}_{X_{\mathcal{I}}}\right)^{-1}(Y-X\theta^{*})\big{)}}{C_{n}\det\left(\boldsymbol{I}+n\rho\boldsymbol{\Pi}_{X_{\mathcal{I}}}\right)},$

where $\boldsymbol{\Pi}_{X_{\mathcal{I}}}$ is given in (70), and $C_{n}$ is
the normalization constant depending solely on $n$. Indeed, conditionally on
$(X,X^{\prime})$ under $\mathcal{H}_{1}$ we have that
$Y^{\prime}\sim\mathcal{N}(X\bar{\theta},\boldsymbol{I})$,
$X\bar{\theta}\sim\mathcal{N}(X\theta^{*},n\rho\boldsymbol{\Pi}_{X_{\mathcal{I}}})$
by (69), and $Y-X\bar{\theta}\sim\mathcal{N}(0,\boldsymbol{I})$ independently;
hence,
$Y\sim\mathcal{N}(X\theta^{*},\boldsymbol{I}+n\rho\boldsymbol{\Pi}_{X_{\mathcal{I}}})$
marginally over $\bar{\theta}$. Similarly,

$Q_{\mathcal{H}_{0}}^{2}(Y,Y^{\prime}|X,X^{\prime})=\frac{\exp\big{(}-\|Y-X\theta^{*}\|^{2}-(Y^{\prime}-X^{\prime}\theta^{*})^{\top}(\boldsymbol{I}+n\rho\boldsymbol{\Omega}_{X,X^{\prime}})^{-1}(Y^{\prime}-X^{\prime}\theta^{*})\big{)}}{C_{n}\det(\boldsymbol{I}+n\rho\boldsymbol{\Omega}_{X,X^{\prime}})},$

where

$\boldsymbol{\Omega}_{X,X^{\prime}}:=X^{\prime}_{{\mathcal{I}}}(X_{{\mathcal{I}}}^{\top}X_{{\mathcal{I}}}^{\vphantom{\top}})^{-1}(X^{\prime}_{\mathcal{I}})^{\top}=\frac{1}{n}X^{\prime}_{{\mathcal{I}}}\widehat{\boldsymbol{\Sigma}}_{0,\mathsf{\Gamma}}^{-1}(X^{\prime}_{\mathcal{I}})^{\top}.$

Hence, $\widehat{T}_{\textsf{MLR}}$ writes

$\widehat{T}_{\textsf{MLR}}=\mathds{1}\\{\|\boldsymbol{A}^{1/2}(Y-X\theta^{*})\|^{2}-\log\det(\boldsymbol{I}-\boldsymbol{A})\geqslant\|\boldsymbol{B}^{1/2}(Y^{\prime}-X^{\prime}\theta^{*})\|^{2}-\log\det(\boldsymbol{I}-\boldsymbol{B})\\},$

where

$\boldsymbol{A}:=\boldsymbol{I}-(\boldsymbol{I}+n\rho\boldsymbol{\Pi}_{X_{I}})^{-1}\quad\text{and}\quad\boldsymbol{B}:=\boldsymbol{I}-(\boldsymbol{I}+n\rho\boldsymbol{\Omega}_{X,X^{\prime}})^{-1}.$

Let us now lower-bound the marginal over $\pi$ type I error
$\mathds{E}_{\pi}\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{MLR}}=1|X,X^{\prime}]$
(clearly this would also give a lower bound for the expected sum of errors).
To this end, observe that

$\boldsymbol{A}=\frac{n\rho}{1+n\rho}\boldsymbol{\Pi}_{X_{\mathcal{I}}}$

and, under $\mathcal{H}_{0}$ and conditionally on $(X,X^{\prime})$, we have

$\|\boldsymbol{A}^{1/2}(Y-X\theta^{*})\|^{2}\sim\frac{n\rho}{1+n\rho}\|\boldsymbol{\Pi}_{X_{\mathcal{I}}}\xi\|^{2}\quad\text{and}\quad\|\boldsymbol{B}^{1/2}(Y^{\prime}-X^{\prime}\theta^{*})\|^{2}\sim
n\rho\|\boldsymbol{\Omega}_{X,X^{\prime}}^{1/2}\zeta\|^{2},$

where $\xi:=Y-X\theta_{0}\sim\mathcal{N}(0,\boldsymbol{I})$, and $\zeta$ is
the whitening of
$Y^{\prime}-X^{\prime}\theta_{0}=\xi^{\prime}+X^{\prime}(\theta_{1}-\theta_{0})$;
thus, $\zeta,\xi$ are independent and have the same distribution. By
rotational invariance, we may assume w.l.o.g. that

$n\rho\boldsymbol{\Omega}_{X,X^{\prime}}=\sum_{j=1}^{\lfloor\texttt{r}/4\rfloor}\mu_{j}\boldsymbol{e}_{j}^{\vphantom{\top}}\boldsymbol{e}_{j}^{\top},$

where $\boldsymbol{e}_{j}$ is the $j$-th canonical vector of $\mathds{R}^{n}$;
here we used that
$\textup{rank}(\boldsymbol{\Omega}_{X,X^{\prime}})\leqslant\lfloor\texttt{r}/4\rfloor$.
As a result,

$\mathds{E}_{\pi}\mathds{P}_{\mathcal{H}_{0}}\left[\widehat{T}_{\textsf{MLR}}=1|X,X^{\prime}\right]=\mathds{P}\left[\|\boldsymbol{\Pi}_{X_{{\mathcal{I}}}}{\xi}\|^{2}\geqslant\frac{1+n\rho}{n\rho}\left(\texttt{r}\log(1+n\rho)/4+\sum_{j=1}^{\lfloor\texttt{r}/4\rfloor}\mu_{j}\zeta_{j}^{2}-\log(1+\mu_{j})\right)\right].$

Now, by the standard deviation bound for the generalized chi-squared
distribution ([29, Lemma 1])

$\sum_{j=1}^{\lfloor\texttt{r}/4\rfloor}\mu_{j}\zeta_{j}^{2}\leqslant\sum_{j=1}^{\lfloor\texttt{r}/4\rfloor}\mu_{j}+2\sqrt{\sum_{j=1}^{\lfloor\texttt{r}/4\rfloor}\mu_{j}^{2}}$

with probability $c>0$. Moreover,
$\mu_{j}-\log(1+\mu_{j})\leqslant\mu_{j}^{2}$. Hence

$\mathds{E}_{\pi}\mathds{P}_{\mathcal{H}_{0}}\left[\widehat{T}_{\textsf{MLR}}=1|X,X^{\prime}\right]\geqslant
c\mathds{P}\left[\|\boldsymbol{\Pi}_{X_{\mathcal{I}}}\xi\|^{2}\geqslant\frac{1+n\rho}{n\rho}\left(\texttt{r}\log(1+n\rho)/4+\sum_{j=1}^{\texttt{r}/4}\mu_{j}^{2}+2\sqrt{\sum_{j=1}^{\texttt{r}/4}\mu_{j}^{2}}\right)\right].$

Moreover, $\log(1+n\rho)-\frac{n\rho}{1+n\rho}\leqslant(n\rho)^{2}$ and
$n\rho\leqslant 1$ (cf. (65)), so we arrive at

$\mathds{E}_{\pi}\mathds{P}_{\mathcal{H}_{0}}\left[\widehat{T}_{\textsf{MLR}}=1|X,X^{\prime}\right]\geqslant
c\mathds{P}\left[\|\boldsymbol{\Pi}_{X_{\mathcal{I}}}\xi\|^{2}-\texttt{r}/4\geqslant\frac{2}{n\rho}\left(\sum_{j=1}^{\texttt{r}/4}\mu_{j}^{2}+2\sqrt{\sum_{j=1}^{\texttt{r}/4}\mu_{j}^{2}}\right)+\texttt{r}n\rho/2\right].$
(72)

Now, observe that that $\|\boldsymbol{\Omega}_{X,X^{\prime}}\|\leqslant 49$.
Indeed, due to (61) we have that

$\|\boldsymbol{\Omega}_{X,X^{\prime}}\|\leqslant\frac{\lambda_{\max}(\widehat{\Sigma}_{1,\mathsf{\Gamma}})}{\lambda_{\min}(\widehat{\Sigma}_{0,\mathsf{\Gamma}})}\leqslant
49,$

and thus $\mu_{j}\leqslant 49n\rho$ for all $j$. Returning to (72), and
recalling the definition of $\rho$ (cf. (68)) we get

$\displaystyle\mathds{E}_{\pi}\mathds{P}_{\mathcal{H}_{0}}\left[\widehat{T}_{\textsf{MLR}}=1|X,X^{\prime}\right]$
$\displaystyle\geqslant
c\mathds{P}\left[\|\boldsymbol{\Pi}_{X_{\mathcal{I}}}\xi\|^{2}-\texttt{r}/4\geqslant
100\sqrt{\texttt{r}}+1250\texttt{r}n\rho\right]$
$\displaystyle=c\mathds{P}\left[\|\boldsymbol{\Pi}_{X_{\mathcal{I}}}\xi\|^{2}-\texttt{r}/4\geqslant
100\sqrt{\texttt{r}}+33\cdot 10^{4}n\Delta\right].$

We are now in the position to apply a lower bound for the right tail of the
$\chi^{2}_{s}$ distribution with $s\geqslant 2$ degrees of freedom ([43,
Prop.3.1]):999One can verify that this bound is tight (matching (53a)) when
$u=O(k)$, which is our case; however, it proves to be loose for larger
deviations. Meanwhile, recent work [44, Corollary 3] establishes the sharpness
of (53) in all regimes.

$\mathds{P}\left[\chi_{s}^{2}-s\geqslant
u\right]\geqslant\frac{c(u+s)}{\sqrt{s}(u+\sqrt{s})}\exp\left(-\frac{Cu^{2}}{s}\right),$

This bound, when applied with $s=\texttt{r}/4$ and
$u=100\sqrt{\texttt{r}}+33\cdot 10^{4}n\Delta$, suffices for our purposes.
Indeed, recall that we are in the regime $n\rho\leqslant 1$, i.e.,
$n\Delta=O(\texttt{r})$. Thus, we need to apply the bound in the range
$c_{1}\sqrt{s}\leqslant u\leqslant c_{2}s$ where it becomes

$\displaystyle\mathds{P}\left[\chi_{s}^{2}-s\geqslant
u\right]\geqslant\frac{c\sqrt{s}}{u}\exp\left(-\frac{Cu^{2}}{s}\right)\geqslant
c\exp\left(-\frac{2Cu^{2}}{s}\right)$ $\displaystyle\geqslant
c\exp\left(-\frac{C^{\prime}(\sqrt{\texttt{r}}+n\Delta)^{2}}{\texttt{r}}\right)$
(73) $\displaystyle\geqslant
c^{\prime}\exp\left(-\frac{C^{\prime\prime}n^{2}\Delta^{2}}{\texttt{r}}\right).$

This proves the r-dependent part of (59). Recalling the discussion in Sec. B.1
we see that, in order to conclude the proof of Theorem 2, it only remains to
show (62); this is our goal in the next section.

###  B.4 Proof of (62)

We shall rely on a classical result about random Gaussian matrices. For
integer $p<n$, let $X\in\mathds{R}^{n\times p}$ have i.i.d. $\mathcal{N}(0,1)$
entries. Then it is known ([45, Theorem II.13]) that, for any $t>0$,

$\max\Big{\\{}\,\mathds{P}\left\\{\lambda_{\min}(X)\leqslant(1-t)\sqrt{n}-\sqrt{p}\right\\},\;\;\mathds{P}\left\\{\lambda_{\max}(X)\geqslant(1+t)\sqrt{n}+\sqrt{p}\right\\}\Big{\\}}\leqslant\exp\left(-nt^{2}/2\right).$

Noting that $|{\mathcal{I}}|=\lfloor\texttt{r}/4\rfloor\leqslant n/4$ and
taking $t=1/4$, we conclude that

$\frac{1}{16}\leqslant\lambda_{\min}(\widehat{\boldsymbol{\Sigma}}_{0,\mathsf{\Gamma}}),\lambda_{\max}(\widehat{\boldsymbol{\Sigma}}_{1,\mathsf{\Gamma}})\leqslant\frac{49}{16}$

with probability at least $1-2e^{-n/32}\geqslant 1/8$ as we are assuming
$n\geqslant\texttt{r}\geqslant 28$.

##  Appendix C Proofs for asymptotic results

###  C.1 Proof of Proposition 3

For convenience we define
$\boldsymbol{J}^{\boldsymbol{\star}}_{k}:=\boldsymbol{J}_{k}(\theta_{k})$ for
$k\in\\{0,1\\}$. As in the proof of Theorem 1, we decompose the statistic
whose sign is examined in (Asymp) as
$\widehat{S}=\widehat{S}_{0}-\widehat{S}_{1}$. W.l.o.g., we analyze the type
II error probability $\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0];$ thus,
$\theta^{*}=\theta_{1}$.

$\boldsymbol{{1}^{o}}$. Recall that
$\boldsymbol{J}^{\boldsymbol{\star}}_{1}:=\boldsymbol{J}_{1}(\theta_{1})$. We
first study

$\displaystyle\widehat{S}_{1}:=n_{1}\|\widehat{\boldsymbol{H}}_{1}(\theta_{1})^{\dagger/2}\nabla\widehat{L}_{1}(\theta_{1})\|^{2}-\textup{Tr}[\boldsymbol{J}^{\boldsymbol{\star}}_{1}]$

and the complementary to it term within $\widehat{S}_{0}$. Let us first define
random variables

$Z(\theta):=\nabla\widehat{L}_{0}(\theta)-\nabla L_{0}(\theta),\quad
Z^{\prime}(\theta):=\nabla\widehat{L}_{1}(\theta)-\nabla L_{1}(\theta);$

note also that $\nabla L_{0}(\theta_{0})=\nabla L_{1}(\theta_{1})=0$. By the
central limit theorem (CLT) we have the following convergence in distribution
as $n_{0},n_{1}\to\infty$:

$\sqrt{n_{0}}Z(\theta)\rightsquigarrow\mathcal{N}(0,\boldsymbol{G}_{0}(\theta)),\quad\sqrt{n_{1}}Z^{\prime}(\theta)\rightsquigarrow\mathcal{N}(0,\boldsymbol{G}_{1}(\theta)),$

with $\boldsymbol{G}_{0}(\theta),\boldsymbol{G}_{1}(\theta)$ defined in (33).
Define $\chi^{2}_{\boldsymbol{J}}$ as the generalized chi-square law –
precisely, the law of $\|\xi\|^{2}$ with
$\xi\sim\mathcal{N}(0,\boldsymbol{J})$ for PSD matrix $\boldsymbol{J}$. Recall
that $\mathds{E}[\chi^{2}_{\boldsymbol{J}}]=\textup{Tr}[\boldsymbol{J}]$, and
[29, Lemma 1] gives

$\displaystyle\mathds{P}[\chi^{2}_{\boldsymbol{J}}-\textup{Tr}[\boldsymbol{J}]\geqslant
t]$
$\displaystyle\leqslant\exp\left(-c\min\left\\{\frac{t}{\|\boldsymbol{J}\|},\frac{t^{2}}{\textup{Tr}[\boldsymbol{J}^{2}]}\right\\}\right),$
(74a)
$\displaystyle\mathds{P}[\chi^{2}_{\boldsymbol{J}}-\textup{Tr}[\boldsymbol{J}]\leqslant-t]$
$\displaystyle\leqslant\exp\left(-\frac{ct^{2}}{\textup{Tr}[\boldsymbol{J}^{2}]}\right).$
(74b)

At fixed $\theta$ we have
$n_{0}\|\boldsymbol{H}_{0}(\theta)^{\dagger/2}Z(\theta)\|^{2}\rightsquigarrow\chi^{2}_{\boldsymbol{J}_{0}(\theta)}$
and
$n_{1}\|\boldsymbol{H}_{1}(\theta)^{\dagger/2}Z(\theta)\|^{2}\rightsquigarrow\chi^{2}_{\boldsymbol{J}_{1}(\theta)},$
that is,

$n_{1}\|\boldsymbol{H}_{1}(\theta_{1})^{\dagger/2}\nabla\widehat{L}_{1}(\theta_{1})\|^{2}\rightsquigarrow\chi^{2}_{\boldsymbol{J}^{\boldsymbol{\star}}_{1}}$

since $\nabla L_{1}(\theta_{1})=0$. Clearly, the fully empirical counterpart
of this quantity
$n_{1}\|\widehat{\boldsymbol{H}}_{1}(\theta_{1})^{\dagger/2}\nabla\widehat{L}_{1}(\theta_{1})\|^{2}$
has the same asymptotic distribution. Indeed, at any fixed $\theta$ one has
$\widehat{\boldsymbol{H}}_{k}(\theta)\to\boldsymbol{H}_{k}(\theta)$ in
probability as $n_{k}\to\infty$ by the law of large numbers; in particular,
$\widehat{\boldsymbol{H}}_{1}(\theta_{1})\to\boldsymbol{H}_{1}(\theta_{1})$.
Thus, by the matrix version of Slutsky’s theorem ([46]) we have that
$\widehat{\boldsymbol{H}}_{1}(\theta_{1})^{\dagger/2}\nabla\widehat{L}_{1}(\theta_{1})\rightsquigarrow\mathcal{N}(0,\boldsymbol{J}^{\boldsymbol{\star}}_{1})$;
as a result, indeed,

$n_{1}\|\widehat{\boldsymbol{H}}_{1}(\theta_{1})^{\dagger/2}\nabla\widehat{L}_{1}(\theta_{1})\|^{2}\rightsquigarrow\chi^{2}_{\boldsymbol{J}^{\boldsymbol{\star}}_{1}}.$

Using tail bounds (74a)–(74b), for any fixed $t>0$ we have
$\mathds{P}[\widehat{S}_{1}\geqslant
t]\to\mathds{P}[\chi^{2}_{\boldsymbol{J}^{\boldsymbol{\star}}_{1}}-\textup{Tr}[\boldsymbol{J}^{\boldsymbol{\star}}_{1}]\geqslant
t]$ as $n_{1}\to\infty$. Now, recall that we are in the regime (in particular,
$n_{k}\bar{\Delta}_{k}\to\lambda_{k}$ for $k\in\\{0,1\\}$. Thus, choosing
$t=\lambda_{0}/3,$ and applying (74a), we arrive at

$\lim_{[...]}\mathds{P}\left[\widehat{S}_{1}\geqslant\frac{n_{0}\bar{\Delta}_{0}}{3}\right]\leqslant\exp\left(-{c\lambda_{0}}\min\left\\{\frac{1}{\|\boldsymbol{J}^{\boldsymbol{\star}}_{1}\|},\frac{\lambda_{0}}{\textup{Tr}[(\boldsymbol{J}^{\boldsymbol{\star}}_{1})^{2}]}\right\\}\right),$
(75)

where the limit is in the regime specified in the premise of the theorem (we
will keep this notation).

$\boldsymbol{{2}^{o}}$. We now consider $\widehat{S}_{0}$ which we decompose
as

$\displaystyle\widehat{S}_{0}$
$\displaystyle:=n_{0}\|\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}\nabla\widehat{L}_{0}(\theta_{1})\|^{2}-\textup{Tr}[\boldsymbol{J}_{0}(\theta_{1})]$
$\displaystyle=n_{0}\|\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}Z(\theta_{1})\|^{2}-\textup{Tr}[\boldsymbol{J}_{0}(\theta_{1})]+n_{0}\bar{\Delta}_{0}+2n_{0}\langle\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}Z(\theta_{1}),\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}\nabla
L_{0}(\theta_{1})\rangle.$

We have
$n_{0}\|\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}Z(\theta_{1})\|^{2}-\textup{Tr}[\boldsymbol{J}_{0}(\theta_{1})]\rightsquigarrow\chi^{2}_{\boldsymbol{J}_{0}(\theta_{1})}$
by CLT combined with Slutsky’s theorem (cf. $\boldsymbol{{1}^{o}}$). Hence,
using (74b), we have

$\displaystyle\lim_{[...]}\mathds{P}\left[n_{0}\|\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}Z(\theta_{1})\|^{2}-\textup{Tr}[\boldsymbol{J}_{0}(\theta_{1})]\leqslant-\frac{n_{0}\bar{\Delta}_{0}}{3}\right]$
$\displaystyle\leqslant\exp\left(-\frac{c\lambda_{0}^{2}}{\textup{Tr}[\boldsymbol{J}_{0}^{2}(\theta_{1})]}\right).$
(76)

Now, by CLT combined with Slutsky’s theorem,
$\sqrt{n_{0}}\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}Z(\theta_{1})\rightsquigarrow\mathcal{N}(0,\boldsymbol{J}_{0}(\theta_{1}))$.
Due to that, and since
$\|\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}\nabla
L_{0}(\theta_{1})\|^{2}/\bar{\Delta}_{0}\to 1$ in probability, we have that

$\sqrt{n_{0}}\langle\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}Z(\theta_{1}),\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}\nabla
L_{0}(\theta_{1})\rangle\rightsquigarrow\mathcal{N}(0,v_{0})\;\;\text{with}\;\;v_{0}\leqslant\|\boldsymbol{J}_{0}(\theta_{1})\|\bar{\Delta}_{0}.$

Therefore by (53c),

$\lim_{[...]}\mathds{P}\left[2n_{0}\langle\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}Z(\theta_{1}),\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{\dagger/2}\nabla
L_{0}(\theta_{1})\rangle\leqslant-\frac{n_{0}\bar{\Delta}_{0}}{3}\right]=\exp\left(\frac{-\lambda_{0}}{36\|\boldsymbol{J}_{0}(\theta_{1})\|}\right).$
(77)

Finally, combining (75)–(77) through the union bound, and observing that
$\textup{Tr}[\boldsymbol{J}_{0}(\theta_{1})]/\textup{Tr}[\boldsymbol{J}^{\boldsymbol{\star}}_{0}]\to
1$ and
$\|\boldsymbol{J}_{0}(\theta_{1})\|/\|\boldsymbol{J}^{\boldsymbol{\star}}_{0}\|\to
1$ since $\boldsymbol{J}_{0}(\cdot)$ is continuous at $\theta_{0}$ and
$\bar{\Delta}_{0}\to 0$, we arrive at the claimed bound:

$\lim_{[...]}\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0]\leqslant
C\exp\bigg{(}-c\lambda_{0}\min\bigg{\\{}\frac{1}{\|\boldsymbol{J}^{\boldsymbol{\star}}_{0}\|},\;\frac{1}{\|\boldsymbol{J}^{\boldsymbol{\star}}_{1}\|},\;\frac{\lambda_{0}}{\textup{Tr}[(\boldsymbol{J}^{\boldsymbol{\star}}_{0})^{2}]},\;\frac{\lambda_{0}}{\textup{Tr}[(\boldsymbol{J}^{\boldsymbol{\star}}_{1})^{2}]}\bigg{\\}}\bigg{)}.$
(78)

The type I error bound follows by symmetry. ∎

###  C.2 Proof of Theorem 3

W.l.o.g., we again focus on the type II error. Following the argument in the
main text after the theorem statement (modulo the switch of indices due to the
different hypothesis), it remains to verify that

$\widehat{\textsf{T}}_{1}\rightsquigarrow\chi_{\boldsymbol{J}_{1}(\theta_{1})}^{2},\quad\widehat{\textsf{T}}_{0}\rightsquigarrow\chi_{\boldsymbol{J}_{0}(\theta_{1})}^{2}.$

Then the result will follow by applying the generalized chi-squared bounds
(74) with $t=\lambda_{0}/3$ and replacing $\boldsymbol{J}_{0}(\theta_{1})$
with $\boldsymbol{J}_{0}(\theta_{0})$ by continuity. To verify the weak
convergence, by using (40) we write

$\widehat{\textsf{T}}_{0}:=\frac{n_{0}}{2}\big{\|}\widehat{\boldsymbol{H}}_{0}(\theta_{1})^{{\dagger}/{2}}\big{[}Z(\theta_{1})-\widetilde{Z}(\theta_{1})\big{]}\big{\|}^{2},\quad(k\in\\{0,1\\}),$

where $\widetilde{Z}(\theta)$ is an independent copy of $Z(\theta)$ from the
previous proof. As before,
$\widehat{\boldsymbol{H}}_{0}(\theta_{1})\to\boldsymbol{H}_{0}(\theta_{1})$ in
probability by the law of large numbers, whereas
$\sqrt{n_{0}}Z(\theta)\rightsquigarrow\mathcal{N}(0,\boldsymbol{G}_{0}(\theta))$
by CLT, thus

$Z(\theta)-\widetilde{Z}(\theta)\rightsquigarrow\mathcal{N}(0,2\boldsymbol{G}_{0}(\theta))$

by independence. By Slutsky’s theorem, this results in
$\widehat{\textsf{T}}_{0}\rightsquigarrow\chi_{\boldsymbol{J}_{0}(\theta_{1})}^{2}$.
The case of $\widehat{\textsf{T}}_{1}$ is similar, and the result follows. ∎

##  Appendix D Proofs for generalized linear models

###  D.1 Proof of Theorem 4

W.l.o.g. we analyze the type II error
$\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0]$ (so that
$\theta^{*}=\theta_{1}$) and use the abridged notation:

$\displaystyle(x_{i},y_{i}):=(x_{i}^{(0)},y_{i}^{(0)}),\quad(x_{i}^{\prime},y_{i}^{\prime}):=(x_{i}^{(1)},y_{i}^{(1)}),$
$\displaystyle\widehat{\Delta}:=\widehat{\Delta}_{0}(x),\quad\Delta:=\Delta_{0},\quad\nu:=\nu_{0},\quad\kappa:=\kappa_{0}.$

$\boldsymbol{{0}^{o}}$. We first focus on the “shifted” term in (GLM),

$\widehat{S}_{0}:=\sum_{i=1}^{n}\frac{(a^{\prime}(\eta_{i}(\theta_{1}))-y_{i})^{2}}{a^{\prime\prime}(\eta_{i}(\theta_{1}))}-n\nu(\theta_{1}),$

where $\eta_{i}(\theta):=\eta_{x_{i}}(\theta)$. By adding and subtracting
$\mathds{E}[y_{i}|x_{i}]$ under the square, we get

$\displaystyle\widehat{S}_{0}$
$\displaystyle=\sum_{i=1}^{n}\frac{(y_{i}-\mathds{E}[y_{i}|x_{i}])^{2}}{a^{\prime\prime}(\eta_{i}(\theta_{1}))}-\nu(\theta_{1})+\frac{(a^{\prime}(\eta_{i}(\theta_{1}))-\mathds{E}[y_{i}|x_{i}])^{2}}{a^{\prime\prime}(\eta_{i}(\theta_{1}))}-\frac{2(a^{\prime}(\eta_{i}(\theta_{1}))-\mathds{E}[y_{i}|x_{i}])(y_{i}-\mathds{E}[y_{i}|x_{i}])}{a^{\prime\prime}(\eta_{i}(\theta_{1}))}$
$\displaystyle=\widehat{Q}_{0}+\widehat{R}_{0}+\widehat{U}_{0}.$ (79)

The term $\widehat{Q}_{0}$ corresponds to the centered $\chi^{2}$-type
statistic. The term $\widehat{R}_{0}$ is non-random when conditioned on
$X=[x_{1};...;x_{n}],$ and incorporates the offset of the statistic due to
$\Delta$. The cross-term $\widehat{U}_{0}$ gives smaller-order fluctuations.
Representing the “unshifted” term
$\widehat{S}_{1}=\widehat{S}_{0}-\widehat{S}$ in a similar manner, where
$\widehat{S}$ is the whole statistic whose sign is examined in (GLM), we
decompose $\widehat{S}$ as follows:

$\widehat{S}=\widehat{S}_{0}-\widehat{S}_{1}=[\widehat{Q}_{0}-\widehat{Q}_{1}]+[\widehat{R}_{0}-\widehat{R}_{1}]+[\widehat{U}_{1}-\widehat{U}_{0}].$

Here $\widehat{Q}_{1},\widehat{R}_{1},\widehat{U}_{1}$ are the counterparts of
$\widehat{Q}_{0},\widehat{R}_{0},\widehat{U}_{0}$ which we do not write down
explicitly here.

$\boldsymbol{{1}^{o}}$. Let us define

$\omega_{i}:=\frac{y_{i}-\mathds{E}[y_{i}|x_{i}]}{\sqrt{a^{\prime\prime}(\eta_{i}(\theta_{1}))}}.$

For $\widehat{Q}_{0}=\sum_{i=1}^{n}\omega_{i}^{2}-n\nu(\theta_{1})$, we have
$\mathds{E}[\widehat{Q}_{0}]=0$ and
$\textup{Var}[\widehat{Q}_{0}]=\sum_{i=1}^{n}\textup{Var}[\omega_{i}^{2}]=n[\kappa(\theta_{1})-\nu^{2}(\theta_{1})],$
where we used independence of $\omega_{i}$’s. Hence, by Chebyshev’s inequality

$\displaystyle\mathds{P}\left[|\widehat{Q}_{0}|\leqslant\frac{n\Delta}{c}\right]$
$\displaystyle\geqslant
1-\frac{c^{2}[\kappa(\theta_{1})-\nu^{2}(\theta_{1})]}{n\Delta^{2}},$

where $c>0$ will be chosen later. In particular, the right-hand side is
$\geqslant 39/40$ whenever

$n\Delta^{2}\geqslant{40c^{2}\kappa(\theta_{1})}.$

As a result, repeating the same analysis for $\widehat{Q}_{1}$, we get

$\mathds{P}\left[|\widehat{Q}_{0}-\widehat{Q}_{1}|\leqslant\frac{2n\Delta}{c}\right]\geqslant\frac{19}{20}$

whenever

$n\geqslant\frac{40c^{2}\max\left\\{\kappa_{1}(\theta_{1}),\kappa_{0}(\theta_{1})\right\\}}{\Delta^{2}}.$
(80)

On the other hand, we verify by simple calculations that (80) with $c=120$ is
indeed implied by (49).

$\boldsymbol{{2}^{o}}$. Our next goal is to similarly bound
$\widehat{R}_{0}-\widehat{R}_{1}$ from below by $\Omega(n\Delta^{2})$. To this
end, we have

$\displaystyle\widehat{R}_{0}$
$\displaystyle=\sum_{i=1}^{n}\widehat{\Delta}(x_{i})+\frac{(a^{\prime}(\eta_{i}(\theta_{0}))-\mathds{E}[y_{i}|x_{i}])^{2}}{a^{\prime\prime}(\eta_{i}(\theta_{1}))}+2\cdot\frac{a^{\prime}(\eta_{i}(\theta_{1}))-a^{\prime}(\eta_{i}(\theta_{0}))}{\sqrt{a^{\prime\prime}(\eta_{i}(\theta_{1}))}}\cdot\frac{a^{\prime}(\eta_{i}(\theta_{0}))-\mathds{E}[y_{i}|x_{i}]}{\sqrt{a^{\prime\prime}(\eta_{i}(\theta_{1}))}}$
$\displaystyle\geqslant\sum_{i=1}^{n}\frac{\widehat{\Delta}(x_{i})}{2}-\frac{(a^{\prime}(\eta_{i}(\theta_{0}))-\mathds{E}[y_{i}|x_{i}])^{2}}{a^{\prime\prime}(\eta_{i}(\theta_{1}))}=\sum_{i=1}^{n}\frac{\widehat{\Delta}(x_{i})}{2}-\beta_{0}(\theta_{1}|x_{i}),$

where we used the expressions (47) and (46):

$\widehat{\Delta}(x):=\frac{[a^{\prime}(\eta_{x}(\theta_{0}))-a^{\prime}(\eta_{x}(\theta_{1}))]^{2}}{a^{\prime\prime}(\eta_{x}(\theta_{1}))},\quad\beta_{0}(\theta|x):=\frac{(a^{\prime}(\eta_{x}(\theta_{0})-\mathds{E}[y|x])^{2}}{a^{\prime\prime}(\eta_{x}(\theta))}$

and in the second line we used that $-2ab\leqslant a^{2}/2+2b^{2}$. Repeating
the analysis for $\widehat{R}_{1}$, we arrive at

$\widehat{R}_{0}-\widehat{R}_{1}\geqslant\sum_{i=1}^{n}\frac{\widehat{\Delta}(x_{i})}{2}-\beta_{0}(\theta_{1}|x_{i})-\beta_{1}(\theta_{1}|x_{i}^{\prime}).$

Now observe that, due to the small misspecification bias assumption (48b),

$\mathds{E}\left[\sum_{i=1}^{n}\beta_{0}^{2}(\theta_{1}|x_{i})+\beta_{1}(\theta_{1}|x_{i}^{\prime})\right]\leqslant
n[\beta_{0}(\theta_{1})+\beta_{1}(\theta_{1})]\leqslant\frac{n\Delta}{400}.$

Hence, by Markov’s inequality,

$\mathds{P}\left[\sum_{i=1}^{n}\beta_{0}(\theta_{1}|x_{i})+\beta_{1}(\theta_{1}|x_{i}^{\prime})\leqslant\frac{n\Delta}{40}\right]\geqslant\frac{9}{10}.$

On the other hand, by the Paley-Zygmund inequality ([40]), for arbitrary
$t\in[0,1]$ we have

$\mathds{P}\left[\sum_{i=1}^{n}\widehat{\Delta}(x_{i})\geqslant
t{n\Delta}\right]\geqslant(1-t)^{2}\frac{n^{2}\Delta^{2}}{\mathds{E}\Big{[}\big{(}\sum_{i=1}^{n}{\widehat{\Delta}(x_{i})}\big{)}^{2}\Big{]}}.$

The denominator satisfies

$\mathds{E}\left[\left(\sum_{i=1}^{n}{\widehat{\Delta}(x_{i})}\right)^{2}\right]=n\mathds{E}[\widehat{\Delta}^{2}]+n(n-1)\Delta^{2}=n^{2}\Delta^{2}+n\textup{Var}[\widehat{\Delta}]\leqslant\frac{81}{80}n^{2}\Delta^{2}.$

where in the end we used that $n\Delta^{2}\geqslant
80\textup{Var}[\widehat{\Delta}]$, cf. (49). Thus, by choosing $t=1/10$ we
arrive at

$\mathds{P}\left[\sum_{i=1}^{n}\widehat{\Delta}(x_{i})\geqslant\frac{n\Delta}{10}\right]\geqslant\frac{8}{10}.$

Combining this with the previous result through the union bound, we finally
arrive at the bound

$\mathds{P}\left[\widehat{R}_{0}-\widehat{R}_{1}\geqslant\frac{n\Delta}{40}\right]\geqslant\frac{7}{10}.$

$\boldsymbol{{3}^{o}}$. It remains to upper-bound the cross-term
$\widehat{U}_{0}-\widehat{U}_{1}$. First, note that condition (49) implies

$\displaystyle\sqrt{n}\Delta$ $\displaystyle\geqslant
40c\sqrt{20\max\left\\{\kappa_{0}(\theta_{1}),\kappa_{1}(\theta_{1}),4\mathds{E}[\widehat{\Delta}^{2}]\right\\}}$
(81)

with $c=120$ – i.e., with the same constant as in step $\boldsymbol{{1}^{o}}$.
Now, let us consider the following event:

$\mathcal{E}=\left\\{\sum_{i=1}^{n}\widehat{\Delta}^{2}(x_{i})+\beta_{0}^{2}(\theta_{1}|x_{i})+\beta_{1}^{2}(\theta_{1}|x_{i}^{\prime})\leqslant{10n\mathds{E}[\widehat{\Delta}^{2}]}\right\\}.$

Using Markov’s inequality and (48b), one can verify that
$\mathds{P}\left[\mathcal{E}\right]\geqslant 49/50$. Moreover, introducing

$\alpha^{2}_{0}(\theta_{1}|x):=\frac{(a^{\prime}(\eta(\theta_{1}))-\mathds{E}[y|x])^{4}}{a^{\prime\prime}(\eta(\theta_{1}))^{2}}\leqslant
4\widehat{\Delta}^{2}(x)+4\beta_{0}^{2}(\theta_{1}|x),$

we have that

$\displaystyle\mathds{P}\left[|\widehat{U}_{0}-\widehat{U}_{1}|\leqslant\frac{n\Delta}{c}\right]$
$\displaystyle\geqslant\mathds{P}\left[|\widehat{U}_{0}|+|\widehat{U}_{1}|\leqslant\frac{n\Delta}{c}\right]$
$\displaystyle\geqslant\mathds{P}\left[|\widehat{U}_{0}|\leqslant\frac{n\Delta}{2c}\right]\mathds{P}\left[|\widehat{U}_{1}|\leqslant\frac{n\Delta}{2c}\right]$
$\displaystyle\geqslant\left(\frac{49}{50}-\mathds{P}\left[|\widehat{U}_{0}|\mathds{1}_{\mathcal{E}}\geqslant\frac{n\Delta}{2c}\right]\right)\left(\frac{49}{50}-\mathds{P}\left[|\widehat{U}_{1}|\mathds{1}_{\mathcal{E}}\geqslant\frac{n\Delta}{2c}\right]\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\geqslant}}\left(\frac{49}{50}-\frac{16c^{2}\mathds{E}\left[\mathds{1}_{\mathcal{E}}\sum_{i=1}^{n}\alpha_{0}(\theta_{1}|x_{i})\nu_{0}(\theta_{1}|x_{i})\right]}{n^{2}\Delta^{2}}\right)\cdot\left(\frac{49}{50}-\frac{16c^{2}\mathds{E}\left[\mathds{1}_{\mathcal{E}}\sum_{i=1}^{n}\beta_{1}(\theta_{1}|x_{i}^{\prime})\nu_{1}(\theta_{1}|x_{i}^{\prime})\right]}{n^{2}\Delta^{2}}\right)$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\geqslant}}\left(\frac{49}{50}-\frac{16c^{2}\sqrt{\kappa_{0}(\theta_{1})\mathds{E}\left[\mathds{1}_{\mathcal{E}}\sum_{i=1}^{n}\alpha^{2}_{0}(\theta_{1}|x_{i})\right]}}{n^{3/2}\Delta^{2}}\right)\cdot\left(\frac{49}{50}-\frac{16c^{2}\sqrt{\kappa_{1}(\theta_{1})\mathds{E}\left[\mathds{1}_{\mathcal{E}}\sum_{i=1}^{n}\beta^{2}_{1}(\theta_{1}|x_{i}^{\prime})\right]}}{n^{3/2}\Delta^{2}}\right)$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\geqslant}}\left(\frac{49}{50}-\frac{64c^{2}\sqrt{10\kappa_{1}(\theta_{1})\mathds{E}[\widehat{\Delta}^{2}]})}{n\Delta^{2}}\right)\cdot\left(\frac{49}{50}-\frac{16c^{2}\sqrt{10\kappa_{0}(\theta_{1})\mathds{E}[\widehat{\Delta}^{2}]}}{n\Delta^{2}}\right)\stackrel{{\scriptstyle(iv)}}{{\geqslant}}\frac{19}{20}.$

Here we proceeded as follows:

  * •

in $(i)$ we recognized $\alpha^{2}_{0}(\theta_{1}|x)$ and
$\beta_{1}^{2}(\theta_{1}|x^{\prime})$ and then used Markov’s inequality in
the form

$\mathds{P}[|X|\geqslant\varepsilon]\leqslant\mathds{E}[X^{2}]/\varepsilon^{2};$

  * •

in $(ii)$ we used the Cauchy-Schwarz inequality twice: first on the sum under
the expectation to obtain the product of two random variables, and then on the
expectation of the product;

  * •

in (iii) we used the definition of the event $\mathcal{E}$;

  * •

in (iv) we used (49) and performed a direct calculation.

By putting $c=120$ and combining the results of
$\boldsymbol{{1}^{o}}$–$\boldsymbol{{3}^{o}}$ via the union bound, we bound
the probability of type II error by $2/5$ as required. The bound for the type
II error follows by symmetry. ∎

###  D.2 Proof of Corollary 3

By Theorem 4, we have that
$\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{j}=1]\leqslant 2/5$ for all
$j\in[b]$. Hence

$\displaystyle\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}=1]$
$\displaystyle=\mathds{P}_{\mathcal{H}_{0}}\left[\sum_{j\in[b]}\widehat{T}_{j}\geqslant\frac{b}{2}\right]\leqslant\mathds{P}_{\mathcal{H}_{0}}\left[\sum_{j\in[b]}\widehat{T}_{j}-\mathds{E}_{0}[\widehat{T}_{j}]\geqslant\frac{b}{10}\right]\leqslant
e^{-cb},$

for some constant $c>0$, where the final step is by Hoeffding’s inequality.
Plugging in the bound (51) for $m=\lceil n/b\rceil$, we verify the claim. The
matching inequality for $\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}=0]$ follows
by symmetry. ∎

###  D.3 Proof of Proposition 4

When analyzing the error probabilities for test (GLM+), we can decompose the
statistic almost in the same way as for (GLM), with two additional terms
corresponding to the fluctuations of $\widehat{\nu}_{0}(\theta^{*})$ and
$\widehat{\nu}_{1}(\theta^{*})$ around their expectations. More precisely,
representing as $\widehat{S}=\widehat{S}_{0}-\widehat{S}_{1}$ the statistic
whose sign is examined in (GLM+) (in the same way as in the proof of Theorem
4), we decompose $\widehat{S}_{0}$ as

$\widehat{S}_{0}=\widehat{Q}_{0}+\widehat{R}_{0}-\widehat{U}_{0}-\widehat{V}_{0}\;\;\text{with}\;\;\widehat{V}_{0}:=n_{0}[\widehat{\nu}_{0}(\theta^{*})-\nu_{0}(\theta^{*})],$

where the first three terms are the same as in (79). Thus, defining
$\widehat{V}_{1}:=n_{1}[\widehat{\nu}_{1}(\theta^{*})-\nu_{1}(\theta^{*})]$,
we have

$\widehat{S}=[\widehat{Q}_{0}-\widehat{Q}_{1}]+[\widehat{R}_{0}-\widehat{R}_{1}]+[\widehat{U}_{1}-\widehat{U}_{0}]+[\widehat{V}_{1}-\widehat{V}_{0}].$

We now show that the additional fluctuation term
$|\widehat{V}_{1}-\widehat{V}_{0}|$ admits essentially the same bound as
$|\widehat{U}_{1}-\widehat{U}_{0}|$. Indeed, in the notation of the proof of
Theorem 4, by Chebyshev’s inequality we have

$\displaystyle\mathds{P}\left[|\widehat{V}_{0}|\geqslant\frac{n\Delta}{c}\right]\leqslant\frac{c^{2}\textup{Var}[n\widehat{\nu}_{0}(\theta^{*})]}{n^{2}\Delta^{2}}=\frac{c^{2}}{n\Delta^{2}}\textup{Var}\left[\frac{(y-\widetilde{y})^{2}}{2a^{\prime\prime}(\eta_{x}(\theta^{*}))}\right]=\frac{c^{2}}{n\Delta^{2}}\left(\mathds{E}\left[\frac{(y-\widetilde{y})^{4}}{4a^{\prime\prime}(\eta_{x}(\theta^{*}))^{2}}\right]-\nu_{0}(\theta^{*})\right);$

here $(x,y)\sim\mathds{P}_{0}$ and $\widetilde{y}$ is independent of $y$ (with
the same distribution) conditionally on $x$, cf. Assumption 1. Furthermore,

$\mathds{E}\left[\frac{(y-\widetilde{y})^{4}}{4a^{\prime\prime}(\eta_{x}(\theta^{*}))^{2}}\right]=\mathds{E}\left[\frac{(y-\mathds{E}[y|x]-(\widetilde{y}-\mathds{E}[\widetilde{y}|x]))^{4}}{4a^{\prime\prime}(\eta_{x}(\theta^{*}))^{2}}\right].$

Thus, for independent $\xi:=y-\mathds{E}[y|x]$ and
$\widetilde{\xi}:=\widetilde{y}-\mathds{E}[y|x]$ (so that
$\mathds{E}[\xi|x]=\mathds{E}[\widetilde{\xi}|x]=0$) we have

$\mathds{E}\left[\frac{(y-\widetilde{y})^{4}}{4a^{\prime\prime}(\eta_{x}(\theta^{*}))^{2}}\right]=\mathds{E}\left[\frac{\mathds{E}[(\xi-\widetilde{\xi})^{4}|x]}{4a^{\prime\prime}(\eta_{x}(\theta^{*}))^{2}}\right]=\mathds{E}\left[\frac{2\mathds{E}[\xi^{4}|x]+6\mathds{E}[\xi^{2}|x]^{2}}{4a^{\prime\prime}(\eta_{x}(\theta^{*}))^{2}}\right]=\frac{\kappa_{0}(\theta^{*})}{2}+\frac{3\nu_{0}^{2}(\theta^{*})}{2}.$

As a result,

$\mathds{P}\left[|\widehat{V}_{0}|\geqslant\frac{n\Delta}{c}\right]\leqslant\frac{c^{2}[\kappa_{0}(\theta^{*})+\nu_{0}^{2}(\theta^{*})]}{2n\Delta^{2}}\leqslant\frac{c^{2}\kappa_{0}(\theta^{*})}{n\Delta^{2}}.$

Proceeding for $\widehat{V}_{1}$ in a similar manner, we arrive at

$\mathds{P}\left[|\widehat{V}_{0}-\widehat{V}_{1}|\geqslant\frac{2n\Delta}{c}\right]\leqslant\frac{c^{2}[\kappa_{0}(\theta^{*})+\kappa_{1}(\theta^{*})]}{n\Delta^{2}},$

that is,

$\mathds{P}_{\mathcal{H}_{1}}\left[|\widehat{V}_{0}-\widehat{V}_{1}|\geqslant\frac{2n\Delta}{c}\right]\leqslant\frac{c^{2}[\kappa_{1}(\theta_{1})+\kappa_{0}(\theta_{1})]}{n\Delta^{2}},$

As a result, under (80) (assuming hypothesis $\mathcal{H}_{1}$ w.l.o.g.) the
bound $|\widehat{V}_{0}-\widehat{V}_{1}|\leqslant 2n\Delta/c$ holds with fixed
probability. Thus, we can combine this result with steps
$\boldsymbol{{1}^{o}}$-$\boldsymbol{{3}^{o}}$ in the proof of Theorem 4,
(slightly increasing the constants), and arrive at a fixed type II error
probability bound for (GLM+). ∎

##  Appendix E Suboptimality of test (Grad)

For simplicity, we let $n_{0}=n_{1}=n$ and consider the setup of a well-
specified linear model with fixed design (cf. Sec. 2); the example can easily
be extended for random design. We use the abridged notation
$(X,Y)=(X^{(0)},Y^{(0)})$ and $(X^{\prime},Y^{\prime})=(X^{(1)},Y^{(1)})$ for
the two samples, and we also let $\xi=Y-X\theta_{0}$ and
$\xi^{\prime}=Y^{\prime}-X^{\prime}\theta_{1}$. Recall that, by Proposition 1,
our proposed test in (Lin) has type I error probability

$\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Lin}}}=1|X,X^{\prime}]\leqslant
C\exp\left(-cn_{1}\widehat{\Delta}_{1}\min\left\\{1,\frac{n_{1}\widehat{\Delta}_{1}}{\widehat{r}}\right\\}\right)$

and the complementary bound for type II error (with the replacement $1\mapsto
0$ of the subscript). Here the (empirical) separation measures
$\widehat{\Delta}_{0},\widehat{\Delta}_{1}$ are given by

$\widehat{\Delta}_{0}=\|\widehat{\boldsymbol{\Sigma}}_{0}^{1/2}(\theta_{1}-\theta_{0})\|^{2},\quad\widehat{\Delta}_{1}=\|\widehat{\boldsymbol{\Sigma}}_{1}^{1/2}(\theta_{1}-\theta_{0})\|^{2},$

and $\widehat{r}=\max\\{\widehat{r}_{0},\widehat{r}_{1}\\}$, where
$\widehat{r}_{k}=\textup{rank}(\widehat{\boldsymbol{\Sigma}}_{k})$. We now
construct a problem instance in which the gradient test
$\widehat{T}_{\textsf{{Grad}}}$, given by (Grad), is suboptimal. To this end,
let $\widehat{\boldsymbol{\Sigma}}_{0}$ and
$\widehat{\boldsymbol{\Sigma}}_{1}$ have the same rank $\widehat{r}$, smallest
non-zero eigenvalue $1/\kappa$ and other eigenvalues equal to $1$, for
$\kappa>0$ to be fixed later. Now, let us take $\theta_{1}-\theta_{0}$ as the
unit vector in the direction corresponding to the smallest eigenvalue of
$\widehat{\boldsymbol{\Sigma}}_{1}$. Then
$\widehat{\Delta}_{1}={1}/{\kappa}\leqslant\widehat{\Delta}_{0}.$ On the other
hand, the quantities
$\widehat{\delta}_{k}:=\|\widehat{\boldsymbol{\Sigma}}_{k}(\theta_{1}-\theta_{0})\|^{2}$,
$k\in\\{0,1\\}$, satisfy

$\widehat{\delta}_{1}=\frac{\widehat{\Delta}_{1}}{\kappa}=\frac{1}{\kappa^{2}}\leqslant\widehat{\delta}_{0}.$

Now, observe that $\widehat{\delta}_{1}$ controls the sum of errors of the
gradient norm test (Grad) in a similar manner as $\widehat{\Delta}_{1}$
controls that for test (Lin). Indeed, proceeding as in the proof of
Proposition 1, we have

$\displaystyle\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Grad}}}=1|X,X^{\prime}]$
$\displaystyle=\mathds{P}\Big{[}\underbrace{\tfrac{1}{n}\|X^{\top}\xi\|^{2}-\mathds{E}[\tfrac{1}{n}\|X^{\top}\xi\|^{2}|X]}_{U}+\underbrace{\mathds{E}[\tfrac{1}{n}\|(X^{\prime})^{\top}\xi^{\prime}\|^{2}|X^{\prime}]-\tfrac{1}{n}\|(X^{\prime})^{\top}\xi^{\prime}\|^{2}}_{V}+\underbrace{2\langle\widehat{\boldsymbol{\Sigma}}_{1}(\theta_{1}-\theta_{0}),(X^{\prime})^{\top}\xi^{\prime}\rangle}_{W}$
$\displaystyle\quad\quad\geqslant n\widehat{\delta}_{1}\Big{]}.$

As our goal is to show suboptimality, let us bound
$\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Grad}}}=1|X,X^{\prime}]$
from below. Since $\tfrac{1}{n}XX^{\top}$ has the same eigenvalues as
$\widehat{\boldsymbol{\Sigma}}_{0}=\frac{1}{n}X^{\top}X$, and similarly for
$\frac{1}{n}X^{\prime}(X^{\prime})^{\top}$, we have that
$\tfrac{1}{n}\|X^{\top}\xi\|^{2}$ is distributed as
$\frac{1}{\kappa}\zeta^{2}+\chi_{\widehat{r}-1}^{2}$, where
$\chi_{\widehat{r}-1}^{2}$ is chi-squared with $\widehat{r}-1$ degrees of
freedom, and $\zeta\sim\mathcal{N}(0,1)$ is independent from
$\chi_{\widehat{r}-1}^{2}.$ Thus, we estimate the (conditional to $X$)
variance of $U$ above as

$\textup{Var}[U|X]\leqslant\widehat{r}(\widehat{r}-1)+3\widehat{r}-(\widehat{r}-1)^{2}\leqslant
4\widehat{r},$

where we used that $\mathds{E}[\zeta^{4}]=3$. Similarly,
$\textup{Var}[V|X^{\prime}]\leqslant 4\widehat{r}$. Finally, by the definition
of $\theta_{1}-\theta_{0}$ we find

$\textup{Var}[W|X^{\prime}]=4\big{\|}X^{\prime}\widehat{\boldsymbol{\Sigma}}_{1}(\theta_{1}-\theta_{0})\big{\|}^{2}=\frac{4}{\kappa^{2}}\|X^{\prime}(\theta_{1}-\theta_{0})\|^{2}=\frac{4n\widehat{\Delta}_{1}}{\kappa^{2}}=\frac{4n\widehat{\delta}_{1}}{\kappa}.$

Thus,

$\textup{Var}[\tfrac{1}{\kappa}\zeta^{2}-\tfrac{1}{\kappa}+V+W]\leqslant\textup{Var}[U+V+W]\leqslant
3\left(8\widehat{r}+\frac{4n\widehat{\delta}_{1}}{\kappa}\right).$

By Chebyshev’s inequality, any centered random variable $Z$ satisfies
$\mathds{P}[Z\leqslant 2\sqrt{\textup{Var}[Z]}]\geqslant 1/2.$ Applying this
to $Z=\tfrac{1}{\kappa}\zeta^{2}-\tfrac{1}{\kappa}+V+W$, we arrive at

$\displaystyle\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Grad}}}=1|X,X^{\prime}]$
$\displaystyle\geqslant\frac{1}{2}\mathds{P}\left[\chi_{\widehat{r}-1}^{2}-(\widehat{r}-1)\geqslant
n\widehat{\delta}_{1}-10\left(\sqrt{\widehat{r}+\frac{n\widehat{\delta}_{1}}{\kappa}}\right)\right]$
$\displaystyle\geqslant\frac{1}{2}\mathds{P}\left[\chi_{\widehat{r}-1}^{2}-(\widehat{r}-1)\geqslant\frac{1}{\kappa}\left(n\widehat{\Delta}_{1}-10\sqrt{\kappa^{2}\widehat{r}+n\widehat{\Delta}_{1}}\right)\right]$

Now, for $\widehat{r}$ large enough, consider the regime

$40\sqrt{\widehat{r}}\leqslant\frac{n\widehat{\Delta}_{1}}{\kappa}\leqslant
3\widehat{r}\quad\iff\quad
40\sqrt{\widehat{r}}\leqslant\frac{n}{\kappa^{2}}\leqslant 3\widehat{r}.$ (82)

By simple algebra, in this regime we have that
$10\sqrt{\kappa^{2}\widehat{r}+n\widehat{\Delta}_{1}}\leqslant
n\widehat{\Delta}_{1}/2$, thus

$\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Grad}}}=1|X,X^{\prime}]\geqslant\frac{1}{2}\mathds{P}\left[\chi_{\widehat{r}-1}^{2}-(\widehat{r}-1)\geqslant\frac{n\widehat{\Delta}_{1}}{2\kappa}\right].$

On the other hand, in this regime we can apply the lower bound for the right
tail probability of the chi-squared distribution (cf. (73)), which gives

$\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Grad}}}=1|X,X^{\prime}]\geqslant
c\exp\left(-\frac{C}{\kappa^{2}}\frac{n^{2}\widehat{\Delta}_{1}^{2}}{\widehat{r}}\right).$

Now, allowing $\widehat{r}$ to grow, let us put $\kappa=\sqrt{\widehat{r}}$
and $n=40\widehat{r}^{3/2}$ (this is on the “left edge” of (82)). Then

$\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Grad}}}=1|X,X^{\prime}]\geqslant
c.$

On the other hand, in this regime we have
$n\widehat{\Delta}_{1}\asymp\widehat{r}$ up to a constant, whence, returning
to test (Lin),

$\mathds{P}_{\mathcal{H}_{0}}[\widehat{T}_{\textsf{{Lin}}}=1|X,X^{\prime}]+\mathds{P}_{\mathcal{H}_{1}}[\widehat{T}_{\textsf{{Lin}}}=0|X,X^{\prime}]\leqslant
C\exp\bigg{(}-\frac{cn^{2}\widehat{\Delta}_{1}^{2}}{\widehat{r}}\bigg{)}\leqslant
C\exp(-c\widehat{r}).$

Thus, we see that there is a widening gap – as $\widehat{r}$ grows – between
the error bounds for the tests $\widehat{T}_{\textsf{{Lin}}}$ and
$\widehat{T}_{\textsf{{Grad}}}$ (and moreover, $\widehat{T}_{\textsf{{Grad}}}$
is not even consistent in this regime, whereas $\widehat{T}_{\textsf{{Lin}}}$
still is). ∎

##  Appendix F Why empirical prediction scores do not violate non-disclosure

Recall that, when discussing the non-disclosure mechanism behind our proposed
testing protocol in Section 1.1, we replaced the data
$\big{(}Z^{(0)},Z^{(1)},\ell,\widehat{S}_{0}(\theta^{*}),\widehat{S}_{1}(\theta^{*})\big{)}$
with $\left(Z^{(0)},Z^{(1)},\ell\right)$, thus neglecting the additional
statistical information about $\mathds{P}_{0},\mathds{P}_{1}$ contained in the
prediction scores. We justify this step by comparing the traces of Fisher
information matrices corresponding to the samples and prediction scores. For
the sake of concreteness we focus on the well-specified linear model setup as
in Section 2 with $\ell$ being the squared loss. For simplicity, we assume
$n_{0}=n_{1}=n$, and the design is non-random and the same in both
samples,101010One can also let $X^{(0)}$ and $X^{(1)}$ be different: the
interested reader may verify that, modulo a few adjustments. The argument we
are about to present will essentially remain the same. so that
$Y^{(k)}\sim\mathcal{N}(X\theta_{k},\boldsymbol{I}_{n})$ fully specifies the
distributions of the samples. We also define
$\xi^{(k)}:=Y^{(k)}-X\theta_{k}\sim\mathcal{N}(0,\boldsymbol{I}_{n})$. Given
our focus on prediction rather than estimation, we shall pass to the
“prediction parameters” $\mu_{k}:=X\theta_{k}\in\mathds{R}^{n}$ living in the
subset $\textup{col}(X)\subseteq\mathds{R}^{n}$ of dimension $\widehat{r}$.
Finally, w.l.o.g. we grant the null hypothesis, so that, $\mu^{*}=\mu_{0}$ is
the mean parameter corresponding to $\theta^{*}=\theta_{0}$.

We shall now focus on the Fisher information about $\mu^{*}=\mu_{0}$ in
$\widehat{S}_{0}(\theta_{0})$ and $\widehat{S}_{1}(\theta_{0})$. Let us first
observe that
$\widehat{S}_{k}(\theta)=\|\boldsymbol{\Pi}_{X}[Y^{(k)}-X\theta]\|^{2}$ can be
reparametrized in terms of $\mu:=X\theta$ as follows:

$\widehat{S}_{k}(\theta)=\|\boldsymbol{\Pi}_{X}[\xi^{(k)}]+X(\theta_{k}-\theta)\|^{2}=\|\zeta^{(k)}+\mu_{k}-\mu\|^{2}=:\widehat{T}_{k}(\mu),$

where
$\zeta^{(k)}:=\boldsymbol{\Pi}_{X}\xi^{(k)}\sim\mathcal{N}(0,\boldsymbol{\Pi}_{X})$.
Now, consider the corresponding Fisher information matrices:

$\mathfrak{I}_{\widehat{T}_{k}(\mu_{0})}(\mu):=\mathds{E}\left[\nabla\mathcal{L}_{\widehat{T}_{k}(\mu_{0})}(\mu)\otimes\nabla\mathcal{L}_{\widehat{T}_{k}(\mu_{0})}(\mu)\right],$

where $v\otimes u=vu^{{\sf T}}$ and $\mathcal{L}_{\widehat{T}_{k}(\mu_{0})}$
is the log-likelihood of $\widehat{T}_{k}(\mu_{0})$. The functional

$\textup{Tr}[\mathfrak{I}_{\widehat{T}_{k}(\mu_{0})}(\mu)]=\mathds{E}\left[\Big{\|}\nabla\mathcal{L}_{\widehat{T}_{k}(\mu_{0})}(\mu)\Big{\|}^{2}\right]$

evaluated at $\mu=\mu_{0}$ quantifies the amount of information about
$\mu^{*}=\mu_{0}$ contained in $\widehat{T}_{k}(\mu_{0})$, and can be compared
with $\textup{Tr}[\mathfrak{I}_{\widehat{Z}_{k}}(\mu_{0})]$, where
$\mathfrak{I}_{\widehat{Z}_{k}}(\mu)$ corresponds to the likelihood of
$\widehat{Z}_{k}$. In addition, by rotational invariance of Gaussian
distribution we have

${\widehat{T}_{k}}(\mu)=\|\omega^{(k)}+\|\mu-\mu_{k}\|\boldsymbol{e}_{1}\|^{2},$

where $\boldsymbol{e}_{1}$ is the first canonical vector in
$\mathds{R}^{\widehat{r}}$, and
$\omega^{(k)}\sim\mathcal{N}(0,\boldsymbol{I}_{\widehat{r}})$. Now, by the
monotonicity property of Fisher information matrices (see, e.g., [47, Theorem
2.86]) we have that

$\mathfrak{I}_{\widehat{T}_{k}(\mu_{0})}(\mu)\preccurlyeq\mathfrak{I}_{\omega^{(k)}+\|\mu_{0}-\mu_{k}\|\boldsymbol{e}_{1}}(\mu).$

Furthermore, $\omega^{(k)}+\|\mu-\mu_{k}\|\boldsymbol{e}_{1}$ has independent
entries, of which only the first one depends on $\mu$, so

$\mathfrak{I}_{\omega^{(k)}+\|\mu_{0}-\mu_{k}\|\boldsymbol{e}_{1}}(\mu)=\mathfrak{I}_{\omega_{1}^{(k)}+\|\mu_{0}-\mu_{k}\|}(\mu).$

Thus,
$\textup{Tr}[\mathfrak{I}_{\widehat{T}_{k}(\mu_{0})}(\mu)]\leqslant\textup{Tr}[\mathfrak{I}_{\omega_{1}+\|\mu_{0}-\mu_{k}\|}(\mu)]$,
where $\omega_{1}\sim\mathcal{N}(0,1)$. Finally, the latter trace can be
computed explicitly. Indeed, the log-likelihood of the observation
$\omega_{1}+\|\mu_{0}-\mu_{k}\|\sim\mathcal{N}(\|\mu_{0}-\mu_{k}\|,1)$ at
arbitrary $\mu$ (i.e., with the actual data-generating distribution
corresponding to $\mu=\mu_{0}$) is given by

$\mathcal{L}_{\omega_{1}+\|\mu_{0}-\mu_{k}\|}(\mu)=-\tfrac{1}{2}(\omega_{1}+\|\mu_{0}-\mu_{k}\|-\|\mu-\mu_{k}\|)^{2}.$

Taking the gradient (in $\mu$) through the composition formula, we get

$\displaystyle\nabla\mathcal{L}_{\omega_{1}+\|\mu_{0}-\mu_{k}\|}(\mu)$
$\displaystyle=(\omega_{1}+\|\mu_{0}-\mu_{k}\|-\|\mu-\mu_{k}\|)\,\nabla(\|\mu-\mu_{k}\|)$
$\displaystyle=\frac{\omega_{1}+\|\mu_{0}-\mu_{k}\|-\|\mu-\mu_{k}\|}{\|\mu-\mu_{k}\|}(\mu-\mu_{k})=(\omega_{1}+\|\mu_{0}-\mu_{k}\|-\|\mu-\mu_{k}\|)\,\boldsymbol{e}_{\mu-\mu_{k}},$

where $\boldsymbol{e}_{\mu-\mu_{k}}$ is the unit-norm vector in the direction
of $\mu-\mu_{k}$. In particular, at $\mu=\mu_{0}$ we get
$\nabla\mathcal{L}_{\omega_{1}+\|\mu_{0}-\mu_{k}\|}(\mu_{0})=\omega_{1}\boldsymbol{e}_{\mu_{0}-\mu_{k}}$,
thus
$\|\nabla\mathcal{L}_{\omega_{1}+\|\mu_{0}-\mu_{k}\|}(\mu_{0})\|^{2}=\omega_{1}^{2}$
and $\textup{Tr}[\mathfrak{I}_{\omega_{1}+\|\mu_{0}-\mu_{k}\|}(\mu_{0})]=1$.
We conclude that

$\textup{Tr}[\mathfrak{I}_{\widehat{T}_{k}(\mu_{0})}(\mu_{0})]\leqslant
1,\quad k\in\\{0,1\\}.$

Let us now contrast this with the amount of information about $\mu_{0}$ that
is already contained in the samples themselves. On one hand, $Y^{(1)}$ does
not reveal any information about $\mu_{0}$ as it only depends on $\mu_{1}$;
hence, $\textup{Tr}[\mathfrak{I}_{Y^{(1)}}(\mu_{0})]=0$. On the other hand,
$\textup{Tr}[\mathfrak{I}_{Y^{(0)}}(\mu_{0})]=n$ by a straightforward
calculation in the Gaussian sequence model. Thus, we conclude that each
prediction scores contains information about $\mu^{*}$ roughly corresponding
to a single additional data point – just as we claimed. ∎