Note that conditions $i)$ and $ii)$ are satisfied for any $n>0$ and $k\leq
D\leq
2(\sqrt{2}-1)\min\left\\{\frac{(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}}{n\|{\bm{\beta}}\|_{\infty}^{4}},n\right\\}$.
∎

##  Appendix C Proofs of Polynomial-Time Reductions

Consider signed support recovery in the $\mathtt{MSLR}$ problem, where we seek
to recover the support of ${\bm{\beta}}_{1}$ and ${\bm{\beta}}_{2}$, along
with the along with the signs of their entries. Take
$({\bm{\beta}}_{1},{\bm{\beta}}_{2})\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$, and let
$\mathcal{S}_{1}:={\rm
supp}({\bm{\beta}}_{1})=\\{j\in[p]:{\bm{\beta}}_{1,j}\neq 0\\}$, and
$\mathcal{S}_{2}$ defined similarly for ${\bm{\beta}}_{2}$. We study the
computational hardness of the problem as we vary two parameters of our joint
signal distribution, the overlap $\xi$ and the signed overlap $\tau$
respectively:

$\xi=\frac{|\mathcal{S}_{1}\cap\mathcal{S}_{2}|}{k},\qquad\tau=\frac{\langle{\bm{\beta}}_{1},{\bm{\beta}}_{2}\rangle}{|\mathcal{S}_{1}\cap\mathcal{S}_{2}|},$

that are of constant order, i.e., do not scale with respect to $n,p,k$.
Previous work (Gamarnik and Zadik, 2022) studies exact support recovery in
sparse linear regression and the computational hardness that arises from the
overlap distribution of two identical copies of the signal. We extend the
analysis by considering exact signed support recovery by varying the parameter
$\tau$, which measures the relative frequency of $+1$ and $-1$ entries with
the same index. Note that for $\xi=1,\tau=1$ we have the usual $\mathtt{SLR}$
problem, for $\xi=1,\tau=-1$ we have the $\mathtt{SB}$-$\mathtt{MSLR}$ regime,
and importantly for $\phi=1/2,\tau\in(-1,1),\xi>0$ we have the
$\mathtt{PSB}$-$\mathtt{MSLR}$ regime. We denote $\mathtt{MSLR}_{\xi,\tau}$
and $\mathtt{MSLR-D}_{\xi,\tau}$ as the $\mathtt{MSLR}$ and $\mathtt{MSLR-D}$
problems with the joint signal prior $\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$
constrained to signals $({\bm{\beta}}_{1},{\bm{\beta}}_{2})$ with overlap and
signed overlap $\xi$ and $\tau$ respectively.

Using these definitions, we first form in Lemma C.1 a polynomial-time
reduction from $\mathtt{SB}$-$\mathtt{MSLR-D}$ to exact signed support
recovery in $\mathtt{SB}$-$\mathtt{MSLR}$ within the scaling regime of Theorem
2.2. Notice that $\mathtt{MSLR-D}_{1,-1}$ is equivalent to the
$\mathtt{SB}$-$\mathtt{MSLR-D}$ problem. Next, we prove a polynomial-time
reduction from exact signed support recovery in $\mathtt{SB}$-$\mathtt{MSLR}$
to exact signed support recovery in $\mathtt{MSLR}_{\xi,\tau}$ for
$\tau\in(-1,1),\xi>0$ ($\mathtt{PSB}$-$\mathtt{MSLR}$ ) within the scaling
regime of Theorem 2.2, proving that if exact signed support recovery can be
achieved in $\mathtt{PSB}$-$\mathtt{MSLR}$ , then it can also be achieved in
$\mathtt{SB}$-$\mathtt{MSLR}$.

Combining the two arguments above, we have that solving exact signed support
recovery in $\mathtt{PSB}$-$\mathtt{MSLR}$ implies solving strong detection in
$\mathtt{SB}$-$\mathtt{MSLR-D}$, which would contradict the implication in
Theorem 2.2 that $\mathtt{SB}$-$\mathtt{MSLR-D}$ cannot be solved in
polynomial time, resulting in Theorem C.3. For more background on the logic of
average-case reductions, we refer to (Brennan and Bresler, 2020b).

The reduction from $\mathtt{SLR-D}$ to $\mathtt{SLR}$ is nearly identical to
that in Lemma C.1 with the midly less restrictive condition that
$\texttt{SNR}\geq 1$, and hence the proof is omitted.

Throughout the proofs, we use the following measure of recovery error for
mixtures of linear regressions (Chen et al., 2014):

$\rho((\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2}),({\bm{\beta}}_{1},{\bm{\beta}}_{2})):=\min\left\\{\left\|\hat{\bm{{\bm{\beta}}}}_{1}-\bm{{\bm{\beta}}}_{1}\right\|_{2}+\left\|\hat{\bm{{\bm{\beta}}}}_{2}-\bm{{\bm{\beta}}}_{2}\right\|_{2},\,\left\|\hat{\bm{{\bm{\beta}}}}_{1}-\bm{{\bm{\beta}}}_{2}\right\|_{2}+\left\|\hat{\bm{{\bm{\beta}}}}_{2}-\bm{{\bm{\beta}}}_{1}\right\|_{2}\right\\}.$

This error measure takes into account recovery of the two signals up to
relabelling. For vectors $a$, $b$, $\hat{a}$, $\hat{b}\in{\mathbb{R}}^{p}$,
define

$\displaystyle\|(\hat{a},\hat{b})-(a,b)\|_{\infty}:=\min\left\\{\|\hat{a}-a\|_{\infty}+\|\hat{b}-b\|_{\infty},\|\hat{b}-a\|_{\infty}+\|\hat{a}-b\|_{\infty}\right\\}.$

Notice that for $\epsilon\in[0,1)$ and signals
$({\bm{\beta}}_{1},{\bm{\beta}}_{2})\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|{\bm{\beta}}\|_{2}}(\\{-1,1\\})$ we have that

$\displaystyle{\mathbb{P}}\left[\rho((\hat{{\bm{\beta}}_{1}},\,\hat{{\bm{\beta}}}_{2}),({\bm{\beta}}_{1},{\bm{\beta}}_{2}))>\epsilon\right]\to
0\iff{\mathbb{P}}\left[\|(\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\|_{\infty}>\epsilon\right]\to
0,$

#### Main Statements

We begin by defining the parameter regimes of interest:

$\displaystyle\mathcal{C}_{1}=\left\\{(p_{i},n_{i},k_{i},\sigma_{i})_{i=1}^{\infty}\subset\mathbb{N}^{4}:\,p_{i}=\omega_{i}(1),k_{i}=o(\sqrt{p_{i}}),n_{i}=\omega(\max\\{k_{i},\log{p_{i}}\\})\,,\right.$
$\displaystyle\hskip
40.00006pt\left.n_{i}=o\left((k_{i}+\sigma_{i}^{2})^{2}\cdot\frac{1}{\log{p_{i}}}\right)\right\\}.$
(7)
$\displaystyle\mathcal{C}_{2}=\left\\{(p_{i},n_{i},k_{i},\sigma_{i})_{i=1}^{\infty}\subset\mathbb{N}^{4}:\,p_{i}=\omega_{i}(1),k_{i}=o(\sqrt{p_{i}}),n_{i}=\omega(\max\\{k_{i},\log{p_{i}}\\})\,,\right.$
$\displaystyle\hskip
40.00006pt\left.n_{i}\gtrsim\frac{k_{i}\log{p_{i}}}{\log(1+\frac{k_{i}}{\sigma_{i}^{2}})}\right\\}.$
(8)

Notice that $\mathcal{C}_{1},\mathcal{C}_{2}$ are both contained within the
parameter regime where $\mathtt{SB}$-$\mathtt{MSLR-D}$ encounters a
computational barrier, as per Theorem 2.2. The following lemmas consist of two
sub-reductions which together give the reduction argument from
$\mathtt{SB}$-$\mathtt{MSLR-D}$ to exact recovery in
$\mathtt{PSB}$-$\mathtt{MSLR}$ .

######  Lemma C.1.

Let $({\bm{\beta}}_{1},{\bm{\beta}}_{2})\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\}),\texttt{SNR}=\omega(1)$.
Given a sequence of parameters
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}$ in $\mathcal{C}_{2}$ for
$\mathtt{SB}$-$\mathtt{MSLR-D}$ and $\mathtt{SB}$-$\mathtt{MSLR}$, if for any
$\epsilon>0$ there exists a randomized polynomial-time algorithm $\mathcal{A}$
for $\mathtt{SB}$-$\mathtt{MSLR}$ producing
$(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})$ with
$\mathbb{P}\left[\|(\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\|_{\infty}<\epsilon\right]\underset{(i\to\infty)}{\to}1$,
then there exists a randomized polynomial-time detection algorithm
$\mathcal{A^{\prime}}$ for $\mathtt{SB}$-$\mathtt{MSLR-D}$ with vanishing Type
I+II errors as $i\to\infty$.

The proof of Lemma C.1 is given in Section C.1.

######  Lemma C.2.

Fix signal priors to be $\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$. For any
sequence of parameters
$\\{(p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},\sigma^{\prime}_{i})\\}_{i=1}^{\infty}$
in $\mathcal{C}_{1}$ for $\mathtt{PSB}$-$\mathtt{MSLR}$ with solution
${\bm{\beta}}^{\prime}_{1},{\bm{\beta}}^{\prime}_{2}$ and problem instances
$({\bm{X}}^{\prime},{\bm{y}}^{\prime})$, there exists a sequence of parameters
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}$ in $\mathcal{C}_{1}$ for
$\mathtt{SB}$-$\mathtt{MSLR}$ with solution
${\bm{\beta}}_{1},{\bm{\beta}}_{2}$ and problem instances
$({\bm{X}},{\bm{y}})$ such that, for any randomized polynomial time algorithm
$\mathcal{A^{\prime}}$ for $\mathtt{PSB}$-$\mathtt{MSLR}$ outputting
$(\hat{{\bm{\beta}}^{\prime}}_{1},\hat{{\bm{\beta}}^{\prime}}_{2})$ with

${\mathbb{P}}\left[\|(\hat{{\bm{\beta}}^{\prime}}_{1},\hat{{\bm{\beta}}^{\prime}}_{2})-({\bm{\beta}}^{\prime}_{1},{\bm{\beta}}^{\prime}_{2})\|_{\infty}>0\right]\to
0,$

we can construct a second randomized polynomial time algorithm $\mathcal{A}$
for $\mathtt{PSB}$-$\mathtt{MSLR}$ outputting
$(\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2})$ such that

${\mathbb{P}}\left[\|(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\|_{\infty}>0\right]\to
0.$

The proof of Lemma C.2 is given in Section C.2.

######  Theorem C.3 (Reduction from $\mathtt{SB}$-$\mathtt{MSLR-D}$ to exact
recovery in $\mathtt{PSB}$-$\mathtt{MSLR}$ ).

Consider the setting of $\mathtt{PSB}$-$\mathtt{MSLR}$ (2) with joint signal
prior $\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$. Any randomized polynomial-
time algorithm $\mathcal{A}$ solving $\mathtt{PSB}$-$\mathtt{MSLR}$ within
parameter regimes $\mathcal{C}_{1}\cap\mathcal{C}_{2}$ and with
$\texttt{SNR}=\omega(1)$ would contradict Theorem 2.2.

###### Proof.

Suppose there exists a randomized polynomial-time algorithm $\mathcal{A}$
solving exact recovery in $\mathtt{PSB}$-$\mathtt{MSLR}$ with signals in
$\\{-1,0,1\\}^{p}$ and parameter regime contained in $\mathcal{C}_{1}$ defined
in (7). Then by Lemma C.2 we would have a randomized polynomial time algorithm
$\mathcal{A}^{\prime}$ solving exact recovery in $\mathtt{SB}$-$\mathtt{MSLR}$
within this regime. By Lemma C.1, we would then consequently have a
polynomial-time algorithm solving $\mathtt{SB}$-$\mathtt{MSLR-D}$ in the
scaling regime $\mathcal{C}_{1}\cap\mathcal{C}_{2}$, which is contained in the
scaling regime of Theorem 2.2 and hence contradicts Theorem 2.2. ∎

######  Remark C.4.

Note that the lower bounds $\frac{k\log{p}}{\log(1+\texttt{SNR})}$ in
constraint $\mathcal{C}_{1}$ in (7) used in Theorem C.3 are not restrictive as
this is the information-theoretic minimal sample complexity for support
recovery in $\mathtt{SLR}$ (Reeves et al., 2019; Gamarnik and Zadik, 2022;
Wang et al., 2010).

###  C.1 Reduction from $\mathtt{SB}$-$\mathtt{MSLR-D}$ to
$\mathtt{SB}$-$\mathtt{MSLR}$

We utilize a variant of a theorem in Gamarnik and Zadik (2017) to construct
our reduction, Lemma C.5. Consider the following optimization problem for
$\sigma>0$:

$\displaystyle\psi:=\min\quad$ $\displaystyle
n^{-\frac{1}{2}}\lVert\sigma{\bm{w}}-{\bm{X}}{\bm{\beta}}_{1}\odot{\bm{z}}-{\bm{X}}{\bm{\beta}}_{2}\odot(1-{\bm{z}})\rVert_{2}$
s.t. $\displaystyle{\bm{\beta}}_{1},{\bm{\beta}}_{2}\in\\{-1,0,1\\}^{p},\
{\bm{z}}\in\\{0,1\\}^{n}$ (9)
$\displaystyle\|{\bm{\beta}}_{1}\|_{0}=\lVert{\bm{\beta}}_{2}\rVert_{0}=k,$

where ${\bm{X}}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$, independent from
$w_{i}\mathbin{\overset{\text{i.i.d.}}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$.

######  Lemma C.5.

Let $\psi$ be as defined in (9). For $\delta>0$ we have:

$\mathbb{P}\left[\psi\geq
e^{-(1+\delta)/2}\exp\left(-\frac{2k(\log{p}+1)}{n}\right)\sqrt{k+\sigma^{2}}\right]\geq
1-e^{-\frac{\delta}{2}n}.$

The proof follows by nearly identical arguments as that of Theorem 3.1 in
(Gamarnik and Zadik, 2017) and is hence omitted.

###### Proof of Lemma C.1.

Throughout the proof, we drop the $i$ subscript in the parameters
$(p_{i},n_{i},k_{i},\sigma_{i})$ for convenience. We refer to
$\mathtt{SB}$-$\mathtt{MSLR}$ and $\mathtt{SB}$-$\mathtt{MSLR-D}$ as
$\mathtt{MSLR}_{\xi,\tau}$ and $\mathtt{MSLR-D}_{\xi,\tau}$ respectively, with
$\xi=1,\tau=-1$. We take ${\rm P}:={\mathbb{P}}({\bm{X}},{\bm{y}})$ to
represent the planted measure in the formulation of $\mathtt{SLR-D}$, and
${\rm Q}:={\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})$ to represent
the null measure. We emphasize that, since
${\bm{\beta}}\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$,
$\|{\bm{\beta}}\|^{2}_{2}$ and $k$ are interchangeable. As prescribed in the
statement of the lemma, suppose that
${\mathbb{P}}\left[\rho((\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2}),({\bm{\beta}}_{1},{\bm{\beta}}_{2}))<\epsilon\right]\underset{(i\to\infty)}{\to}1$
for any $\epsilon>0$.

Define the two following events under the planted hypothesis ${\rm P}$:

$\tilde{\Omega}_{1}:=\left\\{\\{\hat{{\bm{\beta}}}_{1}={\bm{\beta}}_{1},\hat{{\bm{\beta}}}_{2}={\bm{\beta}}_{2}\\}\cup\\{\hat{{\bm{\beta}}}_{2}={\bm{\beta}}_{1},\hat{{\bm{\beta}}}_{1}={\bm{\beta}}_{2}\\}\right\\},$

and

$\tilde{\Omega}_{2}:=\\{|w_{q}|<|\sigma^{-1}\langle{\bm{X}}_{q},{\bm{\beta}}_{2}-{\bm{\beta}}_{1}\rangle+w_{q}|,\>\>\forall
q\in[n]\\}.$

Note that by assumption, $\tilde{\Omega}_{1}$ occurs with probability $1-o(1)$
under ${\rm P}$. Indeed, we can choose $\epsilon<1$ in the definition of our
given algorithm $\mathcal{A}$ and since
$\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2},{\bm{\beta}}_{1},{\bm{\beta}}_{2}\in\\{-1,0,1\\}^{p}$
we obtain that ${\mathbb{P}}\left[\tilde{\Omega}_{1}\right]\to 1$. We first
consider the planted hypothesis ${\rm P}$. Let
$\nu_{q}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,(1-\xi\tau)\frac{k}{\sigma^{2}})$, and
$g_{q}\mathbin{\overset{}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$, independent from
each other and from $w_{q}$, for $q\in[n]$. In this case we have by symmetry
that

$\displaystyle{\rm
P}\left[\tilde{\Omega}_{2}^{\complement}\middle|\tilde{\Omega}_{1}\right]$
$\displaystyle={\rm
P}\left[\\{|w_{q}|\geq|\sigma^{-1}\langle{\bm{X}}_{q},{\bm{\beta}}_{2}-{\bm{\beta}}_{1}\rangle+w_{q}|,\>\>\forall
q\in[n]\\}\right]$ $\displaystyle=\int{\rm
P}\left[\\{|w_{q}|\geq|\nu_{q}+w_{q}|,\>\>\forall
q\in[n]\\}\middle|w_{q}\right]{\rm P}[dw_{q}]$
$\displaystyle=2\int_{0}^{\infty}{\rm
P}\left[\nu_{q}\in[-2w_{q},0],\>\>\forall q\in[n]\\}\middle|w_{q}\right]{\rm
P}[dw_{q}]$ $\displaystyle=2\int_{0}^{\infty}{\rm
P}\left[\\{g_{q}\in[-2w_{q}/((1-\xi\tau)k/\sigma^{2}),0],\>\>\forall
q\in[n]\\}\middle|w_{q}\right]{\rm P}[dw_{q}],$

where we have

${\rm P}\left[\\{g_{q}\in[-2w_{q}/((1-\xi\tau)k/\sigma^{2}),0],\>\>\forall
q\in[n]\\}\middle|w_{q}\right]\to 0\;\;\text{ as }{k/\sigma^{2}\to\infty},$

and ${\rm P}\left[\\{g\in[-2w_{q}/((1-\xi\tau)k/\sigma^{2}),0],\>\>\forall
q\in[n]\\}\middle|w_{q}\right]\leq 1$, so we can apply the Dominated
Convergence Theorem to obtain that

$\displaystyle{\rm
P}\left[\tilde{\Omega}_{2}^{\complement}\middle|\tilde{\Omega}_{1}\right]$
$\displaystyle=2\int_{0}^{\infty}{\rm
P}\left[\\{g_{q}\in[-2w_{q}/((1-\xi\tau)k/\sigma^{2}),0],\>\>\forall
q\in[n]\\}\middle|w_{q}\right]{\rm P}[dw_{q}]\to 0\text{ as
}k/\sigma^{2}\to\infty.$

We therefore have that ${\rm
P}\left[\tilde{\Omega}_{2}\middle|\tilde{\Omega}_{1}\right]=1-o(1)$, and hence
${\rm
P}\left[\left(\tilde{\Omega}_{1},\tilde{\Omega}_{2}\right)\right]=1-o(1)$.

Next, note that under the planted hypothesis ${\rm P}$ and in the joint event
$(\tilde{\Omega}_{1},\tilde{\Omega}_{2})$ we have for indices $q$ such that
$z_{q}=1$:

$\displaystyle|y_{q}-\frac{1}{\sigma}\langle{\bm{X}}_{q},\hat{{\bm{\beta}}}_{1}\rangle|$
$\displaystyle=|y_{q}-\frac{1}{\sigma}\langle{\bm{X}}_{q},{\bm{\beta}}_{1}\rangle|$
$\displaystyle=|w_{q}|$
$\displaystyle<|\frac{1}{\sigma}\langle{\bm{X}}_{q},{\bm{\beta}}_{1}-{\bm{\beta}}_{2}\rangle+w_{q}|$
$\displaystyle=|y_{q}-\frac{1}{\sigma}\langle{\bm{X}}_{q},{\bm{\beta}}_{2}\rangle|$
$\displaystyle=|y_{q}-\frac{1}{\sigma}\langle{\bm{X}}_{q},\hat{{\bm{\beta}}}_{2}\rangle|.$

An analogous statement with $\hat{{\bm{\beta}}}_{1}$ and
$\hat{{\bm{\beta}}}_{2}$ swapped holds for indices $q$ such that $z_{q}=0$. We
therefore have that under $(\tilde{\Omega}_{1},\tilde{\Omega}_{2})$ we can
exactly estimate ${\bm{z}}$ using the above thresholding procedure, and we
call this exact estimate $\hat{{\bm{z}}}$. We then define our detection
algorithm in this case:

$\mathcal{A^{\prime}}\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right)=\begin{cases}\mathtt{p},&n^{-1/2}\|{\bm{y}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{1}\odot\hat{{\bm{z}}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{2}\odot(1-\hat{{\bm{z}}})\|\leq\sqrt{5}\\\
\mathtt{q},&n^{-1/2}\|{\bm{y}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{1}\odot\hat{{\bm{z}}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{2}\odot(1-\hat{{\bm{z}}})\|>\sqrt{5}\end{cases}.$

We will proceed to prove that $\mathcal{A^{\prime}}$ has vanishing Type II
error. Indeed, under ${\rm P}$ and under the high-probability event
$(\tilde{\Omega}_{1},\tilde{\Omega}_{2})$ we have:

$\displaystyle\|{\bm{y}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{1}\odot\hat{{\bm{z}}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{2}\odot(1-\hat{{\bm{z}}})\|_{2}$
$\displaystyle=\|\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{1}\odot{\bm{z}}+\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{2}\odot(1-{\bm{z}})+{\bm{w}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{1}\odot\hat{{\bm{z}}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{2}\odot(1-\hat{{\bm{z}}})\|_{2}$
$\displaystyle\leq\|{\bm{w}}\|_{2}+\|\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{1}\odot{\bm{z}}+\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{2}\odot(1-{\bm{z}})-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{1}\odot\hat{{\bm{z}}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{2}\odot(1-\hat{{\bm{z}}})\|_{2}$
$\displaystyle=\|{\bm{w}}\|_{2}.$

We therefore have

$\displaystyle{\rm
P}\left[\mathcal{A^{\prime}}\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right)=\mathtt{q}\right]$ $\displaystyle={\rm
P}\left[\mathcal{A^{\prime}}\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right)=\mathtt{q}\middle|(\tilde{\Omega}_{1},\tilde{\Omega}_{2})^{\complement}\right]\cdot{\rm
P}\left[(\tilde{\Omega}_{1},\tilde{\Omega}_{2})^{\complement}\right]+{\rm
P}\left[\left\\{\mathcal{A^{\prime}}\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right)=\mathtt{q}\right\\}\cap(\tilde{\Omega}_{1},\tilde{\Omega}_{2})\right]$
$\displaystyle\leq{\rm
P}\left[\mathcal{A^{\prime}}\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right)=\mathtt{q}\middle|(\tilde{\Omega}_{1},\tilde{\Omega}_{2})^{\complement}\right]\cdot{\rm
P}\left[(\tilde{\Omega}_{1},\tilde{\Omega}_{2})^{\complement}\right]+{\rm
P}\left[\left\\{\|{\bm{w}}\|_{2}>\sqrt{5n}\right\\}\cap(\tilde{\Omega}_{1},\tilde{\Omega}_{2})\right]$
$\displaystyle\leq 1\cdot o(1)+{\rm
P}\left[\left\\{\|{\bm{w}}\|_{2}>\sqrt{5n}\right\\}\right]$ $\displaystyle\leq
1\cdot o(1)+e^{-n}=o(1),$

where the last inequality is obtained using a standard chi-square large
deviation tail bounds (Example 2.11 of Wainwright (2019)):

$\displaystyle{\rm P}\left[\|{\bm{w}}\|_{2}<\sqrt{n+2\sqrt{nt}+2t}\right]\geq
1-e^{-t},$

and taking $t=\sqrt{n}$.

We now turn to showing that $\mathcal{A^{\prime}}$ has vanishing Type I error.
Under the null hypothesis ${\rm Q}$ we have by definition of $\psi$ in
Definition 9 that

$\|{\bm{y}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{1}\odot\hat{{\bm{z}}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{2}\odot(1-\hat{{\bm{z}}})\|_{2}\geq\psi,$

where we recall from Lemma C.5 that

${\rm Q}\left[\psi\geq
e^{-3/2}\exp\left(-\frac{2k(\log{p}+1)}{n}\right)\sqrt{k+\sigma^{2}}\right]\geq
1-e^{-n},$

hence it would suffice to show that

$e^{-3/2}\exp\left(-\frac{2k(\log{p}+1)}{n}\right)\sqrt{k+\sigma^{2}}>\sqrt{5}.$

In order to do so, choose
$n^{*}=\frac{4k(\log{p}+1)}{\log{(1+\frac{k}{\sigma^{2}})}-\log{5}-3}=\Theta(\frac{4k\log{p}}{\log(1+\frac{k}{\sigma^{2}})})$
and notice that if the inequality holds for $n^{*}$, it must hold for all
$n\geq n^{*}$ since the left hand side is increasing with $n$. We plug in
$n^{*}$ to obtain

$e^{-3/2}\exp\left(-1/2\log(1+\frac{k}{\sigma^{2}})+\log{\sqrt{5}}+3/2\right)\sqrt{1+2\frac{k}{\sigma^{2}}}=\frac{\sqrt{1+2\frac{k}{\sigma^{2}}}}{\sqrt{1+\frac{k}{\sigma^{2}}}}\sqrt{5}>\sqrt{5},$

and therefore we have that

$\displaystyle{\rm
Q}\left[\mathcal{A^{\prime}}\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right)=\mathtt{q}\right]$ $\displaystyle={\rm
Q}\left[\|{\bm{y}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{1}\odot\hat{{\bm{z}}}-\frac{1}{\sigma}{\bm{X}}\hat{{\bm{\beta}}}_{2}\odot(1-\hat{{\bm{z}}})\|_{2}>\sqrt{5}\right]$
$\displaystyle\geq{\rm Q}\left[\psi>\sqrt{5}\right]$ $\displaystyle\geq{\rm
Q}\left[\psi\geq
e^{-3/2}\exp\left(-\frac{2k(\log{p}+1)}{n}\right)\sqrt{k+\sigma^{2}}\right]$
$\displaystyle\geq 1-e^{-n}.$

Importantly, note that $n$ satisfies the constraints of $\mathcal{C}_{2}$.

∎

###  C.2 Reduction from $\mathtt{SB}$-$\mathtt{MSLR}$ to
$\mathtt{PSB}$-$\mathtt{MSLR}$

###### Proof of Lemma C.2.

First, recall that the $\mathtt{PSB}$-$\mathtt{MSLR}$ regime implies,

$\phi=1/2\text{ and }{\bm{\beta}}_{1,j}=-{\bm{\beta}}_{2,j}\text{ for }j\in
J\subseteq{\rm supp}({\bm{\beta}}_{1})\cap{\rm supp}({\bm{\beta}}_{2})\text{
with }C_{1}k\leq|J|\leq C_{2}k,$

for some constants $1\geq C_{1},C_{2}>0$. Without loss of generality, we can
take $|J|=Ck$ for some constant $0<C\leq 1$, and all constants that follow can
be lower bounded or upper bounded accordingly. In light of this,
$\mathtt{PSB}$-$\mathtt{MSLR}$ corresponds to $\mathtt{MSLR}_{\xi,\tau}$ for
some $\tau\in(-1,1)$ and some $\xi>0$, where we recall that $\xi,\tau$ are of
constant order, i.e., do not scale with respect to $n,p,k$.

For brevity, we denote
${\mathfrak{P}}^{\prime}:=\text{$\mathtt{PSB}$-$\mathtt{MSLR}$}$ and
${\mathfrak{P}}:=\text{$\mathtt{SB}$-$\mathtt{MSLR}$}$. Let
$c=1-\frac{\tau\cdot\xi+1}{2}\in(0,1)$ denote the proportion of matching non-
zero entries with opposite sign between ${\bm{\beta}}_{1}$ and
${\bm{\beta}}_{2}$ (intuitively, this corresponds to the “hard” portion of the
signal), and note that it is fixed. Note that this follows since
$\tau\cdot\xi=\frac{\langle{\bm{\beta}}_{1},{\bm{\beta}}_{2}\rangle}{k}$ for
$\xi>0$.

Given a sequence of parameters
$\\{p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},\sigma^{\prime}_{i}\\}_{i=1}^{\infty}\subseteq\mathcal{C}_{1}$
for ${\mathfrak{P}}^{\prime}$, consider the sequence of parameters
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}=\\{(cp^{\prime}_{i},n^{\prime}_{i},ck^{\prime}_{i},\sigma^{\prime}_{i})\\}_{i=1}^{\infty}$
for ${\mathfrak{P}}$. Notice that
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}\subseteq\mathcal{C}_{1}$
since (dropping the subscript $i$ notation for convenience):

  * •

$k=ck^{\prime}=o(cC\sqrt{p^{\prime}})=o(c^{3/2}C\sqrt{p})=o(\sqrt{p})$

  * •

$n=n^{\prime}=o\left((k^{\prime}+(\sigma^{\prime})^{2})^{2}\cdot\frac{1}{\log{p^{\prime}}}\right)=o\left((k+\sigma^{2})^{2}\cdot\frac{1}{\log{p}}\right)$,

  * •

$n=n^{\prime}=\omega(\max\\{k^{\prime},\log{p^{\prime}}\\})=\omega(\max\\{k,\log{p}\\})$,

and hence the parameter regimes of ${\mathfrak{P}}$ are also contained in
$\mathcal{C}_{1}$. For $i\in\mathbb{N}$, let $J=({\bm{X}},{\bm{y}})$ denote an
instance of ${\mathfrak{P}}$ with parameters $(p_{i},n_{i},k_{i},\sigma_{i})$,
where we recall:

$\displaystyle\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}=\begin{bmatrix}{\bm{X}}\\\
\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{1}\odot{\bm{z}}+\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{2}\odot(1-{\bm{z}})+{\bm{w}}\end{bmatrix}.$

We now want to show that, given a sequence of parameters
$\\{p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i}\\}_{i=1}^{\infty}\subseteq\mathcal{C}_{1}$
for ${\mathfrak{P}}^{\prime}$ and a randomized polynomial-time algorithm
$\mathcal{A^{\prime}}$ solving it, we can construct a randomized polynomial-
time algorithm $\mathcal{A}$ solving ${\mathfrak{P}}$ along the above
parameter sequence
$\\{p_{i},n_{i},k_{i}\\}_{i=1}^{\infty}\subseteq\mathcal{C}_{1}$. We will
construct our desired algorithm $\mathcal{A}$ by composing
$\mathcal{A^{\prime}}$ with a pre- and post-processing step. Indeed, we let
$\mathcal{A}=\mathcal{B}\circ\mathcal{A^{\prime}}\circ\mathcal{D}$, where we
define $\mathcal{B}$ and $\mathcal{D}$ below.

First, let $\mathtt{RS}$ denote the random variable that reshuffles entries of
a given size $p$ vector or the columns of a given $p$-column matrix according
to a uniform shuffling of the index set $[p]$. Let $\mathtt{IRS}$ denote the
random variable which inverts this reshuffling process on a vector or matrix,
such that $\mathtt{IRS}\circ\mathtt{RS}$ is the identity operation. Let
$\mathbbm{1}$ denote the all-ones vector of any size (to be inferred from
context). Let $\bar{\mathbbm{1}}_{1}$ and $\bar{\mathbbm{1}}_{2}$ denote two
independent copies of a $(1-c)k^{\prime}$ sparse vector in
$\\{0,1,-1\\}^{(1-c)p^{\prime}}$. We now define our pre- and post-processing
procedures Algorithms 1, 2, which can be seen to run in randomized polynomial
time with respect to $p$.

;

Data: ${\bm{V}}\in\mathbb{R}^{n\times(1-c)/c\>p}\text{ with
columns}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,{\bm{I}}_{n})$

;

$\tilde{{\bm{y}}}\leftarrow{\bm{y}}+\frac{1}{\sigma}{\bm{V}}\mathbbm{1}$ ;

$\tilde{{\bm{X}}}\leftarrow\mathtt{RS}{\begin{bmatrix}{\bm{V}}&{\bm{X}}\end{bmatrix}}$
;

return $(\tilde{{\bm{X}}},\tilde{{\bm{y}}})$

Algorithm 1 $\mathcal{D}({\bm{X}},{\bm{y}})$, where $({\bm{X}},{\bm{y}})$ is
an instance of ${\mathfrak{P}}(p,n,k,\sigma)$

${\begin{bmatrix}\bar{\mathbbm{1}}_{1}\\\
{\bm{\beta}}_{1}\end{bmatrix}}\leftarrow\mathtt{IRS}(\tilde{{\bm{\beta}}}_{1})$
;

${\begin{bmatrix}\bar{\mathbbm{1}}_{2}\\\
{\bm{\beta}}_{2}\end{bmatrix}}\leftarrow\mathtt{IRS}(\tilde{{\bm{\beta}}}_{2})$
;

return $({\bm{\beta}}_{1},{\bm{\beta}}_{2})$

Algorithm 2 $\mathcal{B}(\tilde{{\bm{\beta}}}_{1},\tilde{{\bm{\beta}}}_{2})$,
where $(\tilde{{\bm{\beta}}}_{1},\tilde{{\bm{\beta}}}_{2})$ are both in
$\\{0,1,-1\\}^{p^{\prime}}$

######  Proposition C.6.

For $i\in\mathbb{N}$, $({\bm{X}},{\bm{y}})$ an instance of
${\mathfrak{P}}(p_{i},n_{i},k_{i},\sigma_{i})$, and
$({\bm{X}}^{\prime},{\bm{y}}^{\prime})$ an instance of
${\mathfrak{P}}^{\prime}(p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i})$, we
have that
$\mathcal{D}({\bm{X}},{\bm{y}})\overset{d}{=}({\bm{X}}^{\prime},{\bm{y}}^{\prime})$.

###### Proof.

Let $(\tilde{{\bm{X}}},\tilde{{\bm{y}}}):=\mathcal{D}({\bm{X}},{\bm{y}})$.
First note that $\tilde{{\bm{X}}}\overset{d}{=}{\bm{X}}^{\prime}$ since
${\begin{bmatrix}{\bm{V}}&{\bm{X}}\end{bmatrix}}$ has dimensions
$n\times(p+\frac{1-c}{c}p)=n^{\prime}\times(cp^{\prime}+(1-c)p^{\prime})=n^{\prime}\times
p^{\prime}$. Next, note that we can decompose $\tilde{{\bm{y}}}$ as follows:

$\displaystyle\tilde{{\bm{y}}}$
$\displaystyle={\bm{y}}+\frac{1}{\sigma}{\bm{V}}\mathbbm{1}$
$\displaystyle=\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{1}\odot{\bm{z}}+\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{2}\odot(1-{\bm{z}})+\frac{1}{\sigma}{\bm{V}}\mathbbm{1}+w$
$\displaystyle=\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{1}\odot{\bm{z}}+\frac{1}{\sigma}{\bm{X}}{\bm{\beta}}_{2}\odot(1-{\bm{z}})+\frac{1}{\sigma}{\bm{V}}\mathbbm{1}\odot{\bm{z}}+\frac{1}{\sigma}{\bm{V}}\mathbbm{1}\odot(1-{\bm{z}})+w$
$\displaystyle=\frac{1}{\sigma}(\mathtt{RS}{\begin{bmatrix}{\bm{V}}&{\bm{X}}\end{bmatrix}})\left(\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{1}\\\
{\bm{\beta}}_{1}\end{bmatrix}}\right)\odot{\bm{z}}+\frac{1}{\sigma}\left(\mathtt{RS}{\begin{bmatrix}{\bm{V}}&{\bm{X}}\end{bmatrix}}\right)\left(\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{2}\\\
{\bm{\beta}}_{2}\end{bmatrix}}\right)\odot(1-{\bm{z}})+w$

and hence $\tilde{{\bm{y}}}$ is the output of a $\mathtt{MSLR}$ model with
size $cp^{\prime}+(1-c)p^{\prime}=p^{\prime}$ signals
$\left(\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{1}\\\
{\bm{\beta}}_{1}\end{bmatrix}},\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{2}\\\
{\bm{\beta}}_{2}\end{bmatrix}}\right)$ containing $ck^{\prime}$ non-zero
opposing sign entries from $({\bm{\beta}}_{1},{\bm{\beta}}_{2})$ and
$(1-c)k^{\prime}$ remaining non-zero entries from appending
$\bar{\mathbbm{1}}$, for a total support of size $k^{\prime}$. Additionally,
these signals are linearly transformed by a design matrix that is i.i.d
Gaussian and $n^{\prime}\times p^{\prime}$ as mentioned above. The first and
second point together imply that $\tilde{{\bm{y}}}$ is the output of a
$\mathtt{MSLR}_{\xi,\tau}$ model and
$\mathcal{D}({\bm{X}},{\bm{y}})=(\tilde{{\bm{X}}},\tilde{{\bm{y}}})\overset{d}{=}({\bm{X}}^{\prime},{\bm{y}}^{\prime})$.
∎

Following Proposition C.6, all that is left to show is that
${\mathbb{P}}[\|\mathcal{B}\circ\mathcal{A^{\prime}}\circ\mathcal{D}({\bm{X}},{\bm{y}})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\|_{\infty}>0]\to
0$. Indeed, the following steps hold due to Proposition C.6 and the definition
of $\mathcal{B}$:

$\displaystyle\|\mathcal{A^{\prime}}({\bm{X}}^{\prime},{\bm{y}}^{\prime})-({\bm{\beta}}^{\prime}_{1},{\bm{\beta}}^{\prime}_{2})\|_{\infty}$
$\displaystyle\overset{d}{=}$
$\displaystyle\left\|\mathcal{A^{\prime}}(\mathtt{RS}({\begin{bmatrix}{\bm{V}}&{\bm{X}}\end{bmatrix}}),{\bm{y}}+\frac{1}{\sigma}{\bm{V}}\mathbbm{1})-\left(\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{1}\\\
{\bm{\beta}}_{1}\end{bmatrix}},\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{2}\\\
{\bm{\beta}}_{2}\end{bmatrix}}\right)\right\|_{\infty}$ $\displaystyle=$
$\displaystyle\left\|\mathcal{A^{\prime}}\circ\mathcal{D}({\bm{X}},{\bm{y}})-\left(\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{1}\\\
{\bm{\beta}}_{1}\end{bmatrix}},\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{2}\\\
{\bm{\beta}}_{2}\end{bmatrix}}\right)\right\|_{\infty}$ $\displaystyle\geq$
$\displaystyle\left\|\mathcal{B}\circ\mathcal{A^{\prime}}\circ\mathcal{D}({\bm{X}},{\bm{y}})-\mathcal{B}\left(\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{1}\\\
{\bm{\beta}}_{1}\end{bmatrix}},\mathtt{RS}{\begin{bmatrix}\bar{\mathbbm{1}}_{2}\\\
{\bm{\beta}}_{2}\end{bmatrix}}\right)\right\|_{\infty}$ $\displaystyle=$
$\displaystyle\left\|\mathcal{A}({\bm{X}},{\bm{y}})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\right\|_{\infty},$

and hence:

$\displaystyle{\mathbb{P}}\left[\|\mathcal{A^{\prime}}({\bm{X}}^{\prime},{\bm{y}}^{\prime})-({\bm{\beta}}^{\prime}_{1},{\bm{\beta}}^{\prime}_{2})\|_{\infty}>0\right]\to
0\implies{\mathbb{P}}\left[\left\|\mathcal{A}({\bm{X}},{\bm{y}})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\right\|_{\infty}>0\right]\to
0,$

where $\mathcal{A}$ runs in randomized polynomial time with respect to the
input size $p$ since it is a composition of randomized polynomial time
procedures with respect to $p$. ∎

###  C.3 Reduction from $\mathtt{SB}$-$\mathtt{MSLR-D}$ to $\mathtt{SPR}$

In this section, we present a polynomial-time reduction from strong detection
in noiseless $\mathtt{SB}$-$\mathtt{MSLR-D}$ to exact support recovery in
$\mathtt{SPR}$ , for signals with non-zero entries in $\\{-1,0,1\\}^{p}$. More
specifically, we consider the following symmetric $\mathtt{SLR}$ problem.

######  Definition C.7 ($\mathtt{S-SLR}$).

For ${\bm{X}}\in\mathbb{R}^{n\times p}$, ${\bm{w}}\in\mathbb{R}^{n}$, and
${\bm{z}}\in\mathbb{R}^{n}$, consider the model:

${\bm{y}}=g\left({\bm{X}}{\bm{\beta}}\right)+{\bm{w}},$

where $\odot$ denotes element-wise product between vectors,
$X_{i,j}\mathbin{\overset{\text{i.i.d.}}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$,
$w_{i}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,\sigma^{2})$, ${\bm{\beta}}\in{\mathbb{R}}^{p}$ each
$k$-sparse, and $g:{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ a separable entry-wise
even function ($g_{i}(x)=g_{i}(-x)$ for $i\in[n]$ and $x\in{\mathbb{R}}$).
Given $({\bm{X}},{\bm{y}})$ the objective is to estimate ${\bm{\beta}}$.

We note that setting $g_{i}(x)=|x|$ and $g_{i}(x)=x^{2}$ yields two standard
formulations of the phase retrieval problem with sparse signals
($\mathtt{SPR}$) (Candès et al., 2015; Liu et al., 2021). We seek to show
hardness within the parameter scaling regime of Theorem 2.2 in the noiseless
case ($\frac{\texttt{SNR}+1}{\texttt{SNR}}=1$) , and hence we prove a
reduction within the constraint set $\mathcal{C}_{3}$:

$\displaystyle\mathcal{C}_{3}=\left\\{(p_{i},n_{i},k_{i},\sigma_{i})_{i=1}^{\infty}\subset\mathbb{N}^{4}:\exists
C\in\mathbb{R}_{+}\,\text{ s.t.
}\,p_{i}=\omega_{i}(1),k_{i}=o(\sqrt{p_{i}}),,\right.$ $\displaystyle\hskip
40.00006pt\left.n_{i}=\omega(\max\\{k_{i},\log{p_{i}}\\})\,n_{i}=o\left(k_{i}^{2}\cdot\frac{1}{\log{p_{i}}}\right)\right\\}.$
(10)

We note that $\mathcal{C}_{3}$ is just $\mathcal{C}_{1}$ in (7), but with the
stricter constraint $n_{i}=o\left(k_{i}^{2}\cdot\frac{1}{\log{p_{i}}}\right)$.
We begin with a lemma, which we use to initiate our reduction in Theorem C.9.

######  Lemma C.8.

Fix signal priors to be $\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$. For any
sequence of parameters
$\\{(p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},\sigma^{\prime}_{i})\\}_{i=1}^{\infty}$
in $\mathcal{C}_{3}$ for $\mathtt{S-SLR}$ with solution
${\bm{\beta}}^{\prime}$ and problem instances
$({\bm{X}}^{\prime},{\bm{y}}^{\prime})$, there exists a sequence of parameters
$\\{(p_{i},n_{i},k_{i},\sigma_{i}=0)\\}_{i=1}^{\infty}$ in $\mathcal{C}_{3}$
for $\mathtt{SB}$-$\mathtt{MSLR}$ (noiseless) with solution
${\bm{\beta}}_{1},{\bm{\beta}}_{2}$ and problem instances
$({\bm{X}},{\bm{y}})$ such that, for any randomized polynomial time algorithm
$\mathcal{A^{\prime}}$ for $\mathtt{S-SLR}$ producing
$\hat{{\bm{\beta}}^{\prime}}$ with

${\mathbb{P}}\left[\|\hat{{\bm{\beta}}^{\prime}}-{\bm{\beta}}\|_{\infty}>0\right]\to
0,$

we can construct a second randomized polynomial time algorithm $\mathcal{A}$
for $\mathtt{SB}$-$\mathtt{MSLR}$ outputting
$(\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2})$ such that

${\mathbb{P}}\left[\|(\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\|_{\infty}>0\right]\to
0.$

###### Proof.

We drop the subscript $i$ notation for convenience. For brevity, let
${\mathfrak{P}}^{\prime}:=\mathtt{S-SLR}$, and
${\mathfrak{P}}:=\text{$\mathtt{SB}$-$\mathtt{MSLR}$}$. Given a sequence of
parameters
$\\{p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},\sigma^{\prime}_{i}\\}_{i=1}^{\infty}$
in $\mathcal{C}_{3}$ for ${\mathfrak{P}}^{\prime}$, consider the sequence of
parameters
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}=\\{(p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},0)\\}_{i=1}^{\infty}$
for ${\mathfrak{P}}$. Notice that
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}$ in $\mathcal{C}_{3}$.
Let $({\bm{X}},{\bm{y}})$ be a problem instance of ${\mathfrak{P}}$ with
parameters $\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}$, and recall
that for noiseless $\mathtt{SB}$-$\mathtt{MSLR}$ the observation is of the
form $({\bm{X}},{\bm{y}}={\bm{X}}{\bm{\beta}}\odot(2{\bm{z}}-1))$. We apply a
preprocessing step to construct
$\tilde{{\bm{y}}}:=g({\bm{y}})+{\bm{w}}\in{\mathbb{R}}^{n}$ were
${\bm{w}}\mathbin{\overset{\text{i.i.d.}}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$,
done in randomized polynomial time. Notice that $({\bm{X}},\tilde{{\bm{y}}})$
is now an instance of ${\mathfrak{P}}^{\prime}$, by virtue of $g$ being
symmetric with respect to sign flips. We then run algorithm
$\mathcal{A}^{\prime}$ on $({\bm{X}},\tilde{{\bm{y}}})$ to obtain
$\hat{{\bm{\beta}}}^{\prime}$ with
${\mathbb{P}}\left[\|\hat{{\bm{\beta}}^{\prime}}-{\bm{\beta}}\|_{\infty}>0\right]\to
0$ as per the problem statement. Without loss of generality setting
$(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})=(\hat{{\bm{\beta}}},-\hat{{\bm{\beta}}})$,
we have an algorithm $\mathcal{A}$ which yields
${\mathbb{P}}\left[\|(\hat{{\bm{\beta}}_{1}},\hat{{\bm{\beta}}}_{2})-({\bm{\beta}}_{1},{\bm{\beta}}_{2})\|_{\infty}>0\right]\to
0$. ∎

######  Theorem C.9 (Reduction from $\mathtt{SB}$-$\mathtt{MSLR-D}$ to exact
recovery in $\mathtt{SPR}$ ).

Consider the setting of $\mathtt{SPR}$ with joint signal prior
$\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$. Any randomized polynomial-time
algorithm $\mathcal{A}$ solving $\mathtt{SPR}$ in parameter regime
$\mathcal{C}_{2}\cap\mathcal{C}_{3}$ and $\texttt{SNR}=\omega(1)$ would
contradict Theorem 2.2.

###### Proof.

We first reduce $\mathtt{SB}$-$\mathtt{MSLR-D}$ to
$\mathtt{SB}$-$\mathtt{MSLR}$ within the constraint set $\mathcal{C}_{2}$ (8),
using Lemma C.1. We then reduce noiseless $\mathtt{SB}$-$\mathtt{MSLR}$ to
$\mathtt{SPR}$ using Lemma C.8 within the constraint set $\mathcal{C}_{3}$
(10) by choosing $g(x)=|x|$ or $g(x)=x^{2}$ depending on the precise
definition of $\mathtt{SPR}$ . Throughout, we have let
$\texttt{SNR}=\omega(1)$ to satisfy Lemma C.1. Suppose there exists a
randomized polynomial-time algorithm $\mathcal{A}$ solving exact recovery in
$\mathtt{SPR}$ with signals with non-zero entries in $\\{-1,0,1\\}^{p}$, i.e.
${\mathbb{P}}\left[\|\hat{{\bm{\beta}}^{\prime}}-{\bm{\beta}}\|_{\infty}>0\right]\to
0$. Then by the aforementioned chain of reductions we would have a randomized
polynomial time algorithm $\mathcal{A}^{\prime}$ solving strong detection in
$\mathtt{SB}$-$\mathtt{MSLR-D}$ with signals with non-zero entries in
$\\{-1,0,1\\}^{p}$ in the scaling regime $\mathcal{C}_{2}\cap\mathcal{C}_{3}$,
which is included in the parameter regime stated in Theorem 2.2 and would
hence contradict Theorem 2.2. ∎

For completeness, we also include a reduction from
$\mathtt{SB}$-$\mathtt{MSLR-D}$ to a detection variant of $\mathtt{SPR}$ in
Theorem C.11.

######  Definition C.10 (Detection Variant $\mathtt{SPR-D}$ ).

For ${\bm{X}}\in\mathbb{R}^{n\times p}$, $\sigma>0$, and
${\bm{w}}^{(1)},{\bm{w}}^{(2)}\in\mathbb{R}^{n}$, consider the following
hypothesis testing problem:

$\displaystyle{{\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})}:\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}=\begin{bmatrix}{\bm{X}}\\\
\sqrt{\frac{\|{\bm{\beta}}\|^{2}_{2}}{\sigma^{2}}}|{\bm{w}}_{1}|+{\bm{w}}_{2}\\\
\end{bmatrix}$
$\displaystyle{{\mathbb{P}}({\bm{X}},{\bm{y}})}:\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}=\begin{bmatrix}{\bm{X}}\\\
\frac{1}{\sigma}|{\bm{X}}{\bm{\beta}}|+{\bm{w}}\end{bmatrix}$

where
$({\bm{\beta}}_{1},{\bm{\beta}}_{2})\sim\mathcal{P}_{\|{\bm{\beta}}\|_{2}}(\mathcal{D})$,
and $X_{i,j}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$, $w_{i}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$, $z_{i}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\text{Bernoulli}(\phi)$. The task is to construct a function $f$
which strongly distinguishes
${\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})$ from
${\mathbb{P}}({\bm{X}},{\bm{y}})$.

######  Theorem C.11.

Fix signal priors to be $\mathcal{P}_{\|\beta\|_{2}}(\\{-1,1\\})$. For any
sequence of parameters
$\\{(p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},\sigma^{\prime}_{i})\\}_{i=1}^{\infty}$
in $\mathcal{C}_{3}$ for $\mathtt{SPR-D}$ with signal ${\bm{\beta}}^{\prime}$
and problem instances $({\bm{X}}^{\prime},{\bm{y}}^{\prime})$, there exists a
sequence of parameters
$\\{(p_{i},n_{i},k_{i},\sigma_{i}=0)\\}_{i=1}^{\infty}\subseteq\mathcal{C}_{3}$
for $\mathtt{SB}$-$\mathtt{MSLR-D}$ (noiseless) with signals
${\bm{\beta}}_{1},{\bm{\beta}}_{2}$ and problem instances
$({\bm{X}},{\bm{y}})$ such that, for any randomized polynomial time algorithm
$\mathcal{A^{\prime}}$ solving strong detection in ${\mathfrak{P}}^{\prime}$,
we can construct a second randomized polynomial time algorithm $\mathcal{A}$
for solving strong detection in ${\mathfrak{P}}$.

###### Proof.

We drop the subscript $i$ notation for convenience. For brevity, let
${\mathfrak{P}}^{\prime}:=\mathtt{SPR-D}$, and
${\mathfrak{P}}:=\text{$\mathtt{SB}$-$\mathtt{MSLR-D}$}$. Given a sequence of
parameters
$\\{p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},\sigma^{\prime}_{i}\\}_{i=1}^{\infty}$
in $\mathcal{C}_{3}$ for ${\mathfrak{P}}^{\prime}$, consider the sequence of
parameters
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}=\\{(p^{\prime}_{i},n^{\prime}_{i},k^{\prime}_{i},0)\\}_{i=1}^{\infty}$
for ${\mathfrak{P}}$. Notice that
$\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}$ is in $\mathcal{C}_{3}$.
Let $({\bm{X}},{\bm{y}})$ be a problem instance of ${\mathfrak{P}}$ with
parameters $\\{(p_{i},n_{i},k_{i},\sigma_{i})\\}_{i=1}^{\infty}$, and recall
that in noiseless $\mathtt{SB}$-$\mathtt{MSLR-D}$ the observation in the
alternative hypothesis is of the form
$({\bm{X}},{\bm{y}}={\bm{X}}{\bm{\beta}}\odot(2{\bm{z}}-1))$. We apply a
preprocessing step to construct
$\tilde{{\bm{y}}}:=|{\bm{y}}|+{\bm{w}}\in{\mathbb{R}}^{n}$ were
${\bm{w}}\mathbin{\overset{\text{i.i.d.}}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$,
done in randomized polynomial time. Notice that under both hypotheses,
$({\bm{X}},\tilde{{\bm{y}}})$ is an instance of ${\mathfrak{P}}^{\prime}$, by
virtue of $g$ being symmetric with respect to sign flips (even). We can then
run algorithm $\mathcal{A}^{\prime}$ on $({\bm{X}},\tilde{{\bm{y}}})$ to solve
the hypothesis testing problem of ${\mathfrak{P}}$ on $({\bm{X}},{\bm{y}})$. ∎

##  Appendix D Proofs for efficient algorithms

###  D.1 $\mathtt{CORR}$ for support recovery in $\mathtt{MSLR}$

######  Theorem D.1 ($\mathtt{CORR}$ achieves joint support recovery in
$\mathtt{MSLR}$).

Consider the general setting of $\mathtt{MSLR}$,
$({\bm{\beta}}_{1},{\bm{\beta}}_{2})\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|{\bm{\beta}}\|_{2}}(\mathcal{D})$. Let
$\epsilon\in(0,1)$ be the one used in $\mathtt{CORR}$. Then provided

$n\geq\frac{32(1+\epsilon)}{\min\\{\phi^{2}{\bm{\beta}}^{2}_{\texttt{min}},(1-\phi)^{2}{\bm{\beta}}^{2}_{\texttt{min}},\langle{\bm{\beta}}\rangle^{2}_{\texttt{min}}\\}}\frac{k(\texttt{SNR}+1)}{\texttt{SNR}}\log{2p},$

we have that $\mathtt{CORR}$ outputs the exact joint support of signals
${\bm{\beta}}_{1}$ and ${\bm{\beta}}_{2}$ with probability at least
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$ for
constants $c_{1},c_{2}>0$.

###### Proof.

Let $\delta>0$ to be chosen later, and for two sets $A$ and $B$ denote the
symmetric difference $A\Delta B:=(A\setminus B)\cup(B\setminus A)$. Let
$\tau:=\sqrt{2(1+\epsilon/2)\log{2p}}$ and define the error event

$\mathcal{E}:=\cup_{j\in\mathcal{S}_{1}\cup\mathcal{S}_{2}}\left\\{\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\tau\right\\}\cup\left\\{\max_{q\in(\mathcal{S}_{1}\cup\mathcal{S}_{2})^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\tau\right\\}.$

From here we partition the set of indices
$j\in\mathcal{S}_{1}\cup\mathcal{S}_{2}$ into two sets,

$J_{a}:=\\{j\in[p]:j\in\mathcal{S}_{1}\cap\mathcal{S}_{2}\\},\qquad
J_{b}:=\\{j\in[p]:j\in\mathcal{S}_{1}\Delta\mathcal{S}_{2}\\},$

with respect to which we perform a union bound:

$\displaystyle\mathbb{P}\left[\mathcal{E}\right]\leq\mathbb{P}\left[\cup_{j\in\mathcal{S}_{1}\cup\mathcal{S}_{2}}\left\\{\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\tau\right\\}\right]+\mathbb{P}\left[\max_{q\in(\mathcal{S}_{1}\cup\mathcal{S}_{2})^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\tau\right]$
$\displaystyle\leq\mathbb{P}\left[\cup_{j_{a}\in
J_{a}}\left\\{\left|\frac{\langle{\bm{X}}_{j_{a}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\tau\right\\}\right]+\mathbb{P}\left[\cup_{j_{b}\in
J_{b}}\left\\{\left|\frac{\langle{\bm{X}}_{j_{b}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\tau\right\\}\right]+\mathbb{P}\left[\max_{q\in(\mathcal{S}_{1}\cup\mathcal{S}_{2})^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\tau\right]$
$\displaystyle\leq
2k\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j_{a}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\tau\right]+2k\mathbb{P}\left[\left\\{\left|\frac{\langle{\bm{X}}_{j_{b}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\tau\right\\}\right]+\mathbb{P}\left[\max_{q\in(\mathcal{S}_{1}\cup\mathcal{S}_{2})^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\tau\right],$
(11)

where $j_{a}\in J_{a}$, $j_{b}\in J_{b}$, and
$q\in\left(\mathcal{S}_{1}\cup\mathcal{S}_{2}\right)^{\complement}$. Analyzing
the last term, we note that for $q\notin\mathcal{S}_{1}\cap\mathcal{S}_{2}$ we
have
$\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$. We therefore have,

$\displaystyle\mathbb{P}\left[\max_{q\in(\mathcal{S}_{1}\cup\mathcal{S}_{2})^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle\stackrel{{\scriptstyle
i)}}{{\leq}}\mathbb{P}\left[\max_{q\in(\mathcal{S}_{1}\cup\mathcal{S}_{2})^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2\log{2p}}+\frac{\epsilon}{2\sqrt{8}}\sqrt{\log{2p}}\right]\stackrel{{\scriptstyle
ii)}}{{\leq}}(2p)^{-\frac{1}{16}\left(\frac{\epsilon}{2}\right)^{2}},$

where $i)$ follows from
$\sqrt{2(1+\epsilon/2)}\geq\sqrt{2}+\frac{\epsilon}{2\sqrt{8}}$, and $ii)$
from a tail bound on the maximum of standard Gaussians (see
$\mathbb{P}\big{[}\Omega^{\complement}_{2}(t)\big{]}$ in Lemma D.9). Applying
Lemmas D.3 and D.2 respectively (and choosing $\delta>0$ small enough to
satisfy these) to the first two terms in (11) we obtain that, for some
constants $c_{1},c_{2}>0$,

$\displaystyle\mathbb{P}\left[\mathcal{E}\right]$ $\displaystyle\leq
c_{1}\left(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}}\right).$

∎

#### The principal concentration lemmas.

######  Lemma D.2 (General Bound for
$j\in\mathcal{S}_{1}\Delta\mathcal{S}_{2}$).

Consider the setting of $\mathtt{MSLR}$. Let
$j^{*}\in\mathcal{S}_{1}\Delta\mathcal{S}_{2}$. Then if
$n\geq\frac{32(1+\epsilon)}{\min\\{\phi^{2},(1-\phi)^{2}\\}{\bm{\beta}}^{2}_{\texttt{min}}}(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$
for any $\epsilon\in(0,1)$ we obtain that

$\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right]\leq\frac{1}{p}+4e^{-\frac{\delta^{2}n}{8}}+\frac{39}{\delta^{2}n}.$

###### Proof.

Let $g_{i}\mathbin{\overset{\text{i.i.d.}}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$
(independent from ${\bm{y}},{\bm{z}},{\bm{\beta}}_{1},{\bm{\beta}}_{2}$) for
$i\in[n]$ and $\delta>0$ to be chosen later. Without loss of generality, we
can assume $j^{*}\in\mathcal{S}_{1}\setminus\mathcal{S}_{2}$. We begin by
considering fixed ${\bm{\beta}}_{1}$, ${\bm{\beta}}_{2}$, ${\bm{y}}$ and
${\bm{z}}$ vectors, and hence the initial randomness of interest lies in the
design matrix ${\bm{X}}$. Define

  * •

$\sigma^{(1)}_{i}:=\frac{y_{i}}{\|{\bm{y}}\|_{2}}\sqrt{1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}$,

  * •

$\sigma^{(2)}_{i}:=\frac{y_{i}}{\|{\bm{y}}\|_{2}}$,

  * •

$\mu^{(1)}_{i}:=\frac{y^{2}_{i}}{\|{\bm{y}}\|_{2}}\frac{{\bm{\beta}}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}$,

  * •

$\mu^{(2)}_{i}:=0$,

and notice that for $\tau\in\mathbb{R}$,

$\displaystyle\mathbb{P}\left[X_{j^{*},i}\leq\tau|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]=\mathbb{P}\left[z_{i}\left(\frac{y_{i}\cdot{\bm{\beta}}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}+\sqrt{1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}g_{i}\right)+(1-z_{i})g_{i}\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},y_{i},z_{i}\right],$

which follows from Lemma D.4. We then have that

$\mathbb{P}\left[X_{j^{*},i}\frac{y_{i}}{\|{\bm{y}}\|_{2}}\leq\tau\middle|{\bm{y}},{\bm{z}}\right]=\mathbb{P}\left[z_{i}(\mu^{(1)}_{i}+\sigma^{(1)}_{i}g_{i})+(1-z_{i})(\mu^{(2)}_{i}+\sigma^{(2)}_{i}g_{i})\leq\tau\middle|{\bm{y}},{\bm{z}}\right],$

from which it follows that for $\tau>0$,

$\displaystyle\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[\left|\sum_{i=1}^{n}z_{i}(\mu^{(1)}_{i}+\sigma^{(1)}_{i}g_{i})+(1-z_{i})(\mu^{(2)}_{i}+\sigma^{(2)}_{i}g_{i})\right|\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[\left|\sum_{i=1}^{n}(z_{i}\mu^{(1)}+(1-z_{i})\mu^{(2)})+(z_{i}\sigma^{(1)}+(1-z_{i})\sigma^{(2)})g_{i}\right|\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\overset{i)}{=}\mathbb{P}\left[\left|\sum_{i=1}^{n}(z_{i}\mu^{(1)}+(1-z_{i})\mu^{(2)})+g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\right|\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[\left\\{\sum_{i=1}^{n}(z_{i}\mu^{(1)}+(1-z_{i})\mu^{(2)})+g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\tau\right\\}\right.$
$\displaystyle\left.\quad\cap\left\\{-\tau\leq\sum_{i=1}^{n}(z_{i}\mu^{(1)}+(1-z_{i})\mu^{(2)})+g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\right\\}\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\overset{ii)}{\leq}\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\tau-\left|\sum_{i=1}^{n}(z_{i}\mu^{(1)}+(1-z_{i})\mu^{(2)})\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\tau-\left|\sum_{i=1}^{n}\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\cdot
z_{i}{\bm{\beta}}_{1,j^{*}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=:\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right],$
(12)

where $i)$ holds by the closure of Gaussian random variables under finite sum,
and $ii)$ holds by symmetry of the Gaussian $g_{1}$ and since
$\mathbb{P}\left[B_{1}\cap
B_{2}\right]\leq\min_{i\in\\{1,2\\}}\mathbb{P}\left[B_{i}\right]$.

Using the high probability events $\Omega_{1}(\delta),\Omega_{4}(\delta)$
defined in Lemma D.9, we have

$\displaystyle\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\tau\right]=\int_{{\bm{\beta}}_{1},{\bm{\beta}}_{2}}\int_{y,z}\mathbb{P}\left[\left|\frac{\langle
X_{j^{*},i},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]d\mathbb{P}[{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},z]$
$\displaystyle\leq\int_{{\bm{\beta}}_{1},{\bm{\beta}}_{2}}\int_{\Omega_{1}(\delta)\cap\Omega_{4}(\delta)}\mathbb{P}\left[\left|\frac{\langle
X_{j^{*},i},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\tau\middle|{\bm{y}},{\bm{z}}\right]d\mathbb{P}[{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},z]$
$\displaystyle\quad+\int_{{\bm{\beta}}_{1},{\bm{\beta}}_{2}}\mathbb{P}\left[\left(\Omega_{1}(\delta)\cap\Omega_{4}(\delta)\right)^{\complement}\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2}\right]d\mathbb{P}[{\bm{\beta}}_{1},{\bm{\beta}}_{2}]$
$\displaystyle=\int_{{\bm{\beta}}_{1},{\bm{\beta}}_{2}}\int_{\Omega_{1}(\delta)\cap\Omega_{4}(\delta)}\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]d\mathbb{P}[{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},z]+\mathbb{P}\left[\left(\Omega_{1}(\delta)\cap\Omega_{4}(\delta)\right)^{\complement}\right]$
$\displaystyle\leq\int_{{\bm{\beta}}_{1},{\bm{\beta}}_{2}}\int_{\Omega_{1}(\delta)\cap\Omega_{4}(\delta)}\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]d\mathbb{P}[{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},z]+\mathbb{P}\left[\Omega^{\complement}_{1}(\delta)\right]+\mathbb{P}\left[\Omega_{4}^{\complement}(\delta)\right].$
(13)

Now setting $\tau=\sqrt{2(1+\epsilon/2)\log{2p}}$ and
$n\geq\frac{32(1+\epsilon)}{\phi^{2}{\bm{\beta}}^{2}_{\texttt{min}}}(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{p}$
we obtain that for $(y,z)\in\Omega_{1}(\delta)\cap\Omega_{4}(\delta)$:

$\displaystyle\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\tau-\left|\sum_{i=1}^{n}\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\cdot
z_{i}{\bm{\beta}}_{1,j^{*}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right.$
$\displaystyle\left.\hskip
100.00015pt-\left|\frac{\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\phi{\bm{\beta}}_{1,j^{*}}-\sqrt{\frac{2(3+\delta)\log{2p}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right.$
$\displaystyle\left.\hskip
100.00015pt-\left|\sqrt{\frac{n(1-\delta)}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}\phi{\bm{\beta}}_{1,j^{*}}-\sqrt{\frac{2(3+\delta)\log{2p}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right.$
$\displaystyle\left.\hskip
100.00015pt-\left|\sqrt{32(1+\epsilon)(1-\delta)\log{2p}}-\sqrt{\frac{2(3+\delta)\log{2p}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right],$
(14)

where for small enough $\delta>0$, we have

$\displaystyle\sqrt{2(1+\epsilon/2)}-\left|\sqrt{32(1+\epsilon)(1-\delta)}-\sqrt{2(3+\delta)/(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}\right|\leq-\sqrt{2}.$
(15)

Hence we obtain that the right hand side of the inequality in (14) is
negative, leading us to the following inequality for
$(y,z)\in\Omega_{1}(\delta)\cap\Omega_{4}(\delta)$,

$\displaystyle\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{1/2}\leq-\sqrt{2\log{2p}}\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\exp\left(-\frac{2\log{2p}}{2\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}}\right)$
$\displaystyle\overset{i)}{\leq}\exp\left(-\frac{2\log{2p}}{2\sum_{i=1}^{n}\frac{y_{i}^{2}}{\|{\bm{y}}\|^{2}_{2}}}\right)\leq\frac{1}{2p},$
(16)

where $i)$ follows almost surely from the fact that $z_{i}\in\\{0,1\\}$ and
$\left(1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}}\right)\leq
1$. We generalize to the case where
$j\in\mathcal{S}_{2}\setminus\mathcal{S}_{1}$, and hence consider the
analogous result with $\phi$ and ${\bm{\beta}}_{1}$ replaced with $(1-\phi)$
and ${\bm{\beta}}_{2}$. Putting it all together in (13) using Lemma D.9 and
choosing $\delta>0$ small enough to satisfy (15), we obtain that for
$n\geq\frac{32}{\min\\{\phi^{2},(1-\phi)^{2}\\}{\bm{\beta}}^{2}_{\texttt{min}}}(1+\epsilon)(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$,

$\displaystyle\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle\leq\frac{1}{p}+4e^{-\frac{\delta^{2}n}{8}}+\frac{39}{\delta^{2}n}.$
(17)

∎

######  Lemma D.3 (General Bound for
$j\in\mathcal{S}_{1}\cap\mathcal{S}_{2}$).

Consider the setting of $\mathtt{MSLR}$. Let
$j^{*}\in\mathcal{S}_{1}\cap\mathcal{S}_{2}$. Then if
$n\geq\frac{32(1+\epsilon)}{(\phi\beta_{1,j^{*}}+(1-\phi)\beta_{2,j^{*}})^{2}}(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$
for any $\epsilon\in(0,1)$ we obtain that

$\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right]\leq\frac{1}{p}+4e^{-\frac{\delta^{2}n}{8}}+\frac{39}{\delta^{2}n}.$

###### Proof.

The proof is along the same lines as that of Lemma D.2, with the main
difference being in the conditional means and variances of $X_{j^{*},i}$, for
$i\in[n]$. As before, let $g_{i}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$ (independent from
$y,z,{\bm{\beta}}_{1},{\bm{\beta}}_{2}$) for $i\in[n]$ and $\delta>0$ to be
chosen later. Define

  * •

$\sigma^{(1)}_{i}:=\frac{y_{i}}{\|{\bm{y}}\|_{2}}\sqrt{1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}$,

  * •

$\sigma^{(2)}_{i}:=\frac{y_{i}}{\|{\bm{y}}\|_{2}}\sqrt{1-\frac{{\bm{\beta}}^{2}_{2,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}$,

  * •

$\mu^{(1)}_{i}:=\frac{y^{2}_{i}}{\|{\bm{y}}\|_{2}}\frac{{\bm{\beta}}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}$,

  * •

$\mu^{(2)}_{i}:=\frac{y^{2}_{i}}{\|{\bm{y}}\|_{2}}\frac{{\bm{\beta}}_{2,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}$,

and notice that for $\tau\in\mathbb{R}$,

$\displaystyle\mathbb{P}\left[X_{j^{*},i}\leq\tau|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[z_{i}\left(\frac{y_{i}\cdot{\bm{\beta}}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}+\sqrt{1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}g_{i}\right)\right.$
$\displaystyle\qquad\quad\left.+(1-z_{i})\left(\frac{y_{i}\cdot{\bm{\beta}}_{2,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}+\sqrt{1-\frac{{\bm{\beta}}^{2}_{2,j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}g_{i}\right)\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},y_{i},z_{i}\right],$

which follows from Lemma D.4. We then have that

$\mathbb{P}\left[X_{j^{*},i}\frac{y_{i}}{\|{\bm{y}}\|_{2}}\leq\tau\middle|{\bm{y}},{\bm{z}}\right]=\mathbb{P}\left[z_{i}(\mu^{(1)}_{i}+\sigma^{(1)}_{i}g_{i})+(1-z_{i})(\mu^{(2)}_{i}+\sigma^{(2)}_{i}g_{i})\leq\tau\middle|{\bm{y}},{\bm{z}}\right].$

Then, using the same steps as in (12), we obtain that for for $\tau>0$:

$\displaystyle\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\tau\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\tau-\left|\sum_{i=1}^{n}\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\cdot(z_{i}{\bm{\beta}}_{1,j^{*}}+(1-z_{i}){\bm{\beta}}_{2,j^{*}})\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=:\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right].$
(18)

Using the high probability events $\Omega_{1}(\delta),\Omega_{3}(\delta)$
defined in Lemma D.9, by the same arguments as in (13) we have

$\displaystyle\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\tau\right]$
$\displaystyle\leq\int_{{\bm{\beta}}_{1},{\bm{\beta}}_{2}}\int_{\Omega_{1}(\delta)\cap\Omega_{3}(\delta)}\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]d\mathbb{P}[{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},z]+\mathbb{P}\left[\Omega^{\complement}_{1}(\delta)\right]+\mathbb{P}\left[\Omega_{3}^{\complement}(\delta)\right],$
(19)

Now setting $\tau=\sqrt{2(1+\epsilon/2)\log{2p}}$ and
$n\geq\frac{32}{\langle{\bm{\beta}}\rangle^{2}_{\texttt{min}}}(1+\epsilon)(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$
we obtain that for $(y,z)\in\Omega_{1}(\delta)\cap\Omega_{3}(\delta)$,

$\displaystyle\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle=\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\tau-\left|\sum_{i=1}^{n}\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\cdot(z_{i}{\bm{\beta}}_{1,j^{*}}+(1-z_{i}){\bm{\beta}}_{2,j^{*}})\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right.$
$\displaystyle\left.\hskip
100.00015pt-\left|\frac{\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}(\phi{\bm{\beta}}_{1,j^{*}}+(1-\phi){\bm{\beta}}_{2,j^{*}})-\sqrt{\frac{2(3+\delta)\log{2p}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right.$
$\displaystyle\left.\hskip
100.00015pt-\left|\sqrt{\frac{n(1-\delta)}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}(\phi{\bm{\beta}}_{1,j^{*}}+(1-\phi){\bm{\beta}}_{2,j^{*}})-\sqrt{\frac{2(3+\delta)\log{2p}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\left(\sum_{i=1}^{n}(z_{i}\sigma^{(1)}_{i}+(1-z_{i})\sigma^{(2)}_{i})^{2}\right)^{\frac{1}{2}}\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right.$
$\displaystyle\left.\hskip
100.00015pt-\left|\sqrt{32(1+\epsilon)(1-\delta)\log{2p}}-\sqrt{\frac{2(3+\delta)\log{2p}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right|\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right],$
(20)

where

$\displaystyle\sqrt{2(1+\epsilon/2)}-\left|\sqrt{32(1+\epsilon)(1-\delta)}-\sqrt{2(3+\delta)/(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}\right|\leq-\sqrt{2},$
(21)

for small enough $\delta>0$. Hence we obtain that the right hand side of (20)
is negative, leading us to the following inequality for
$(y,z)\in\Omega_{1}(\delta)\cap\Omega_{3}(\delta)$, obtained via the same
steps as (16):

$\displaystyle\mathbb{P}\left[A\middle|{\bm{\beta}}_{1},{\bm{\beta}}_{2},{\bm{y}},{\bm{z}}\right]\leq\frac{1}{2p}.$

Putting it all together in (19) using Lemma D.9 and choosing $\delta>0$ small
enough to satisfy (20) we obtain that for
$n\geq\frac{32}{\langle{\bm{\beta}}\rangle^{2}_{\texttt{min}}}(1+\epsilon)(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$,

$\displaystyle\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle\leq\frac{1}{p}+4e^{-\frac{\delta^{2}n}{8}}+\frac{39}{\delta^{2}n}.$

∎

#### The conditioning lemmas.

######  Lemma D.4 (General conditioning lemma).

Consider the setting of $\mathtt{MSLR}$.

For $j^{*}\in\mathcal{S}_{1}\cap\mathcal{S}_{2}$ and $i\in[n]$ it holds that:

$\displaystyle\left.X_{j^{*},i}\middle|(y_{i},{\bm{\beta}}_{1},z_{i}=1)\right.$
$\displaystyle\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(\frac{y_{i}\cdot{\bm{\beta}}_{1,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}},\left(1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}}\right)\right),$
(22)
$\displaystyle\left.X_{j^{*},i}\middle|(y_{i},{\bm{\beta}}_{2},z_{i}=0)\right.$
$\displaystyle\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(\frac{y_{i}\cdot{\bm{\beta}}_{2,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}},\left(1-\frac{{\bm{\beta}}^{2}_{2,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}}\right)\right).$
(23)

For $j^{*}\in\mathcal{S}_{1}\Delta\mathcal{S}_{2}$ (without loss of generality
$j^{*}\in\mathcal{S}_{1}\setminus\mathcal{S}_{2}$) and $i\in[n]$ it holds that

$\displaystyle\left.X_{j^{*},i}\middle|(y_{i},{\bm{\beta}}_{1},z_{i}=1)\right.$
$\displaystyle\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(\frac{y_{i}\cdot{\bm{\beta}}_{1,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}},\left(1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}}\right)\right),$
(24) $\displaystyle\left.X_{j^{*},i}\middle|(y_{i},z_{i}=0)\right.$
$\displaystyle\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(0,1\right)$ (25)

###### Proof.

To prove (22) and (24), recall that

$y_{i}=z_{i}({\bm{X}}{\bm{\beta}}_{1})_{i}+(1-z_{i})({\bm{X}}{\bm{\beta}}_{2})_{i}+w_{i},$

and hence given $z_{i}=1$ we have

$y_{i}=\sum_{j\neq
j^{*}\in\mathcal{S}_{1}}{\bm{\beta}}_{1,j}X_{j,i}+{\bm{\beta}}_{1,j^{*}}X_{j^{*},i}+w_{i},$

implying that

$\displaystyle\left.X_{j^{*},i}\,\middle|\,(y_{i},{\bm{\beta}}_{1},z_{i}=1)\right.$
$\displaystyle=\left.X_{j^{*},i}\,\middle|\,\left({\bm{\beta}}_{1},y_{i}=\sum_{j\neq
j^{*}\in\mathcal{S}_{1}}{\bm{\beta}}_{1,j}X_{j,i}+{\bm{\beta}}_{1,j^{*}}X_{j^{*},i}+w_{i}\right)\right..$

Therefore, applying Corollary D.7, we obtain that
$\left.X_{j^{*},i}\middle|(y_{i},{\bm{\beta}}_{1},z_{i}=1)\right.\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(\frac{y_{i}{\bm{\beta}}_{1,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}},\left(1-\frac{{\bm{\beta}}^{2}_{1,j^{*}}}{\|{\bm{\beta}}_{1}\|^{2}_{2}+\sigma^{2}}\right)\right)$.
The result in (23) is proved in the same way, but replacing ${\bm{\beta}}_{1}$
with ${\bm{\beta}}_{2}$.

For (25), notice that given $z_{i}=0$ we have

$y_{i}=\sum_{j\in\mathcal{S}_{2}}{\bm{\beta}}_{2,j}X_{j,i}+w_{i},$

which is independent of $X_{j^{*},i}$ by definition, and hence
$X_{j^{*},i}|(y_{i},z_{i}=0)$ has the same distribution as
$X_{j^{*},i}\mathbin{\overset{}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$. ∎

######  Lemma D.5 (General conditioning lemma).

Let $a\mathbin{\overset{}{\kern 0.0pt\sim}}\mathcal{N}\left(0,\Sigma_{k\times
k}\right)$, and $b\in\mathbb{R}^{k}$ a fixed vector. Then:

$\left.a\middle|\right.\left(\sum_{j=1}^{k}b_{j}a_{j}=\eta\right)\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(\eta v,B\Sigma_{k\times k}B^{T}\right)$

where, letting $\mathbbm{1}$ denote the all-ones vector,

$v=\frac{1}{b^{T}\tilde{\Sigma}\mathbbm{1}}\tilde{\Sigma}\mathbbm{1},\quad
B=I_{k\times k}-vb^{T},\quad\tilde{\Sigma}=\mathbb{E}\left[a(a\odot
b)^{T}\right].$

###### Proof.

Let $B$ be a deterministic matrix, and $\eta:=\sum_{j=1}^{k}b_{j}a_{j}$. Then
$(Ba,\eta)$ is jointly normal. We will construct a fixed matrix $B$ and fixed
vector $v$ such that

  * •

$Ba$ is independent from $\eta$

  * •

$a=Ba+\eta v$.

If the above holds, then by independence we have the required result that
$a|\eta\mathbin{\overset{}{\kern 0.0pt\sim}}\mathcal{N}\left(\eta v,B\Sigma
B^{T}\right)$. In order for the first point to hold, their covariances must be
zero, implying

$\mathbb{E}\left[Ba\eta\right]=\mathbb{E}\left[Ba(a\odot
b)^{T}\mathbbm{1}\right]=B\tilde{\Sigma}\mathbbm{1}=0.$

Meanwhile, the second point is satisfied by choosing $B=I-vb^{T}$. Combining
these two facts, we obtain the result. ∎

######  Corollary D.6.

Consider the setting of $\mathtt{SLR}$, let $j^{*}\in\mathcal{S}$, and
$i\in[n]$. Then it holds that

$\left.X_{j^{*},i}\middle|\left(\sum_{j\in\mathcal{S}}X_{j,i}+w_{i}=\eta\right)\right.\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(\frac{\eta}{k+\sigma^{2}},\left(1-\frac{1}{k+\sigma^{2}}\right)\right)$

###### Proof.

Apply Lemma D.5 conditioning on the sum
$\sum_{j\in\mathcal{S}}X_{j,i}+w_{i}=:\eta$, where we recall
$\begin{bmatrix}{\bm{X}}_{\mathcal{S}}\;w_{i}\end{bmatrix}\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(0,\Sigma\right)$ with

$\Sigma=\begin{bmatrix}1&0&\cdots&0\\\ 0&1&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\sigma^{2}\end{bmatrix}\in\mathbb{R}^{(k+1)\times(k+1)}$

yielding

$v=\frac{1}{k+\sigma^{2}}\begin{bmatrix}1\\\ 1\\\ \vdots\\\
\sigma^{2}\end{bmatrix}$

and

$B=\begin{bmatrix}(1-\frac{1}{k+\sigma^{2}})&-\frac{1}{k+\sigma^{2}}&\cdots&-\frac{1}{k+\sigma^{2}}\\\
-\frac{1}{k+\sigma^{2}}&(1-\frac{1}{k+\sigma^{2}})&\cdots&-\frac{1}{k+\sigma^{2}}\\\
\vdots&\vdots&\ddots&\vdots\\\
-\frac{1}{k+\sigma^{2}}&-\frac{1}{k+\sigma^{2}}&\cdots&(1-\frac{1}{k+\sigma^{2}})\\\
\end{bmatrix}.$

Noticing that $(B\Sigma B^{T})_{j^{*},j^{*}}=1-\frac{1}{k+\sigma^{2}}$, we
obtain the result. ∎

######  Corollary D.7.

Consider the setting of $\mathtt{SLR}$, and let $b\in\mathbb{R}^{p}$ be fixed.
Let $j^{*}\in\mathcal{S}$, and $i\in[n]$. Then it holds that

$\left.X_{j^{*},i}\middle|\left(\sum_{j\in\mathcal{S}}b_{j}X_{j,i}+w_{i}=\eta\right)\right.\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{N}\left(\frac{\eta\cdot
b_{j^{*}}}{\|b\|^{2}_{2}+\sigma^{2}},\left(1-\frac{b^{2}_{j^{*}}}{\|b\|^{2}_{2}+\sigma^{2}}\right)\right)$

###### Proof.

The result is obtained by applying Lemma D.5 conditioning on the sum
$\sum_{j\in\mathcal{S}}b_{j}X_{j,i}+w_{i}=\eta$. We then have that

$\tilde{\Sigma}=\mathbb{E}\left[{\begin{bmatrix}X_{1,i}\\\ X_{2,i}\\\
\vdots\\\ w_{i}\end{bmatrix}}{\begin{bmatrix}b_{1}X_{1,i}\\\ b_{2}X_{2,i}\\\
\vdots\\\ w_{i}\end{bmatrix}}^{T}\right]=\begin{bmatrix}b_{1}&0&\cdots&0\\\
0&b_{2}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\sigma^{2}\end{bmatrix}\in\mathbb{R}^{(k+1)\times(k+1)}$

yielding

$v=\frac{1}{\|b\|^{2}_{2}+\sigma^{2}}\begin{bmatrix}b_{1}\\\ b_{2}\\\
\vdots\\\ \sigma^{2}\end{bmatrix}$

and

$B=\begin{bmatrix}(1-\frac{b^{2}_{1}}{\|b\|^{2}_{2}+\sigma^{2}})&-\frac{b_{1}b_{2}}{\|b\|^{2}_{2}+\sigma^{2}}&\cdots&-\frac{b_{1}}{\|b\|^{2}_{2}+\sigma^{2}}\\\
-\frac{b_{2}b_{1}}{\|b\|^{2}_{2}+\sigma^{2}}&(1-\frac{b^{2}_{2}}{\|b\|^{2}_{2}+\sigma^{2}})&\cdots&-\frac{b_{2}}{\|b\|^{2}_{2}+\sigma^{2}}\\\
\vdots&\vdots&\ddots&\vdots\\\
-\frac{\sigma^{2}b_{1}}{\|b\|^{2}_{2}+\sigma^{2}}&-\frac{\sigma^{2}b_{2}}{\|b\|^{2}_{2}+\sigma^{2}}&\cdots&(1-\frac{\sigma^{2}}{\|b\|^{2}_{2}+\sigma^{2}})\\\
\end{bmatrix}.$

Noticing that $(B\Sigma
B^{T})_{j^{*},j^{*}}=1-\frac{b^{2}_{j^{*}}}{\|b\|^{2}_{2}+\sigma^{2}}$, we
obtain the result. ∎

######  Lemma D.8.

Consider the setting of $\mathtt{MSLR}$ as in Definition 1.1. Then $y$ and $z$
are independent.

###### Proof.

Let $g\mathbin{\overset{}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$, and $A$ an event
in the sigma algebra. By Bayes rule, for every $i\in[n]$ it holds that

$\displaystyle\mathbb{P}\left[z_{i}=1\middle|y_{i}\in A\right]$
$\displaystyle=\frac{\mathbb{P}\left[y_{i}\in
A\middle|z_{i}=1\right]\mathbb{P}[z_{i}=1]}{\mathbb{P}[y]}$
$\displaystyle=\frac{\mathbb{P}\left[y_{i}\in
A\middle|z_{i}=1\right]\mathbb{P}[z_{i}=1]}{\mathbb{P}\left[y_{i}\in
A\middle|z_{i}=1\right]\mathbb{P}[z_{i}=1]+\mathbb{P}\left[y_{i}\in
A\middle|z_{i}=0\right]\mathbb{P}[z_{i}=0]}$
$\displaystyle=\frac{\mathbb{P}[\sqrt{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}g\in
A]\phi}{\mathbb{P}[\sqrt{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}g\in
A]\phi+\mathbb{P}[\sqrt{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}g\in A](1-\phi)}$
$\displaystyle=\phi$ $\displaystyle=\mathbb{P}[z_{i}=1],$

and the analogous result holds for the case $z_{i}=0$. The result then follows
by recalling that $y_{i}$ and $z_{i}$ are i.i.d. across the $i$ indices. ∎

#### High-probability events and Concentration inequalities

######  Lemma D.9 (High-probability events).

Consider the setting of $\mathtt{MSLR}$. Let
$g_{q}\mathbin{\overset{\text{i.i.d.}}{\kern 0.0pt\sim}}\mathcal{N}(0,1)$ for
$q\in[p]$ and $\delta\in(0,1)$, $t>0,j^{*}\in[p]$. Define the following events
that will be necessary for the analysis of $\mathtt{CORR}$ on $\mathtt{MSLR}$:

$\Omega_{1}(\delta):=\left\\{(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})n(1-\delta)\leq\|{\bm{y}}\|^{2}\leq(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})n(1+\delta)\right\\},$
$\Omega_{2}(t):=\left\\{\max_{q\in[p]}|g_{q}|\leq\sqrt{2\log{2p}}+\sqrt{2t\log{2p}}\right\\},$
$\displaystyle\Omega_{3}(\delta):=\left\\{\left|\sum_{i=1}^{n}(z_{i}{\bm{\beta}}_{1,j^{*}}+(1-z_{i}){\bm{\beta}}_{2,j^{*}})\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right.\right.$
$\displaystyle\qquad\qquad\left.\left.-(\phi{\bm{\beta}}_{1,j^{*}}+(1-\phi){\bm{\beta}}_{2,j^{*}})\frac{\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|<\sqrt{\frac{2(3+\delta)\log{(2p)}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right\\},$
$\Omega_{4}(\delta):=\left\\{\left|\sum_{i=1}^{n}z_{i}{\bm{\beta}}_{1,j^{*}}\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}-\phi{\bm{\beta}}_{1,j^{*}}\frac{\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|<\sqrt{\frac{2(3+\delta)\log{(2p)}}{(1-\delta)(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})}}\right\\},$
$\Omega_{5}(\delta):=\left\\{\left|\|{\bm{y}}\|^{4}_{4}-3n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}\right|<\delta
n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}\right\\}.$

Then, the above events all occur with high probability. Specifically,

  * •

$\mathbb{P}\left[\Omega^{\complement}_{1}(\delta)\right]\leq
2e^{-\frac{\delta^{2}n}{8}}$ as per Example 2.11 in Wainwright (2019) noting
that $y_{i}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})$ both marginally
and conditionally on z (similarly for the setting of $\mathtt{SLR}$).

  * •

$\mathbb{P}\left[\Omega^{\complement}_{2}(t)\right]\leq\frac{1}{(2p)^{t}}$ as
per Lemma 5.2 in van Handel (2014).

  * •

$\mathbb{P}\left[\Omega^{\complement}_{3}(\delta)\middle|\Omega_{1}(\delta),\Omega_{5}(\delta)\right]\leq\frac{1}{2p}$
as per Lemma D.11 and consequently
$\mathbb{P}\left[\Omega^{\complement}_{3}(\delta)\right]\leq\frac{1}{2p}+2e^{-\frac{\delta^{2}n}{8}}+\frac{39}{\delta^{2}n}$.

  * •

$\mathbb{P}\left[\Omega^{\complement}_{4}(\delta)\middle|\Omega_{1}(\delta),\Omega_{5}(\delta)\right]\leq\frac{1}{2p}$
as per Lemma D.11 with ${\bm{\beta}}_{2,j^{*}}=0$ and consequently
$\mathbb{P}\left[\Omega^{\complement}_{4}(\delta)\right]\leq\frac{1}{2p}+2e^{-\frac{\delta^{2}n}{8}}+\frac{39}{\delta^{2}n}$.

  * •

$\mathbb{P}\left[\Omega^{\complement}_{5}(\delta)\right]\leq\frac{39}{\delta^{2}n}$
as per Lemma D.10.

######  Lemma D.10 (Fast $\ell_{4}$ norm concentration).

Let ${\bm{y}}\in{\mathbb{R}}^{n}$ with
$y_{i}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,\sigma^{2})$ for $i\in[n]$. Then for $\delta>0$ we
have,

$\mathbb{P}\left[\left|\|{\bm{y}}\|_{4}-3n(\sigma^{2})^{2}\right|\geq\delta
n(\sigma^{2})^{2}\right]\leq\frac{39}{\delta^{2}n}.$

###### Proof.

The proof follows from a standard application of Chebyshev’s inequality. We
first recall that the $p^{\text{th}}$ centered Gaussian moment is given by
$(\text{variance})^{\frac{p}{2}}(p-1)!!$, and consequently by independence we
have that $\mathbb{E}\left[\|{\bm{y}}\|^{4}_{4}\right]=3n(\sigma^{2})^{2}$. We
then proceed with Chebyshev’s inequality (see Boucheron et al. (2013)) for
$t>0$:

$\displaystyle\mathbb{P}\left[\left|\|{\bm{y}}\|^{4}_{4}-\mathbb{E}\left[\|{\bm{y}}\|^{4}_{4}\right]\right|\geq
t\right]$ $\displaystyle\leq\frac{n\text{Var}(y^{4}_{1})}{t^{2}}$
$\displaystyle=\frac{n\left(\mathbb{E}y^{8}_{1}-\left(\mathbb{E}y^{4}_{1}\right)^{2}\right)}{t^{2}}$
$\displaystyle=\frac{n(\sigma^{2})^{4}((7-1)!!-9)}{t^{2}}=\frac{39n(\sigma^{2})^{4}}{t^{2}}.$

We set $t=n(\sigma^{2})^{2}$ to obtain

$\displaystyle\mathbb{P}\left[\left|\|{\bm{y}}\|^{4}_{4}-\mathbb{E}\left[\|{\bm{y}}\|^{4}_{4}\right]\right|\geq
n(\sigma^{2})^{2}\right]$
$\displaystyle\leq\frac{39n(k+\sigma^{2})^{4}}{n^{2}(\sigma^{2})^{4}}=\frac{39}{n}.$

∎

######  Lemma D.11.

Consider the setting of $\mathtt{MSLR}$. For $t>0,\delta>0,j^{*}\in[p]$ we
have that

$\displaystyle\mathbb{P}\left[\left|\sum_{i=1}^{n}(z_{i}{\bm{\beta}}_{1,j^{*}}+(1-z_{i}){\bm{\beta}}_{2,j^{*}})\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}-(\phi{\bm{\beta}}_{1,j^{*}}+(1-\phi){\bm{\beta}}_{2,j^{*}})\frac{\|{\bm{y}}\|^{2}_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|\geq
t\middle|\Omega_{1}(\delta),\Omega_{5}(\delta)\right]$
$\displaystyle\leq\exp\left(-\frac{(1-\delta)}{2(3+\delta)}(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})t^{2}\right)$

###### Proof.

Consider $y\in\Omega_{1}(\delta)\cap\Omega_{5}(\delta)$ in Lemma D.9. We first
apply Hoeffding’s inequality (see Boucheron et al. (2013)), then the
definitions of $\Omega_{1}(\delta)$ and $\Omega_{5}(\delta)$ to obtain,

$\displaystyle\mathbb{P}\left[\left|\sum_{i=1}^{n}(z_{i}{\bm{\beta}}_{1,j^{*}}+(1-z_{i}){\bm{\beta}}_{2,j^{*}})\frac{y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}-(\phi{\bm{\beta}}_{1,j^{*}}+(1-\phi){\bm{\beta}}_{2,j^{*}})\frac{\|{\bm{y}}\|^{2}_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|\geq
t\middle|{\bm{y}}\right]$
$\displaystyle\leq\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}({\bm{\beta}}_{1,j^{*}}-{\bm{\beta}}_{2,j^{*}})^{2}\frac{y^{4}_{i}/\|{\bm{y}}\|^{2}_{2}}{(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}}}\right)$
$\displaystyle=\exp\left(-\frac{2t^{2}}{({\bm{\beta}}_{1,j^{*}}-{\bm{\beta}}_{2,j^{*}})^{2}\frac{\|{\bm{y}}\|^{4}_{4}}{\|{\bm{y}}\|^{2}_{2}}\frac{1}{(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}}}\right)$
$\displaystyle\leq\exp\left(-\frac{2t^{2}}{({\bm{\beta}}_{1,j^{*}}-{\bm{\beta}}_{2,j^{*}})^{2}\frac{3n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}+\delta
n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}}{\|{\bm{y}}\|^{2}_{2}}\frac{1}{(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}}}\right)$
$\displaystyle\leq\exp\left(-\frac{2t^{2}}{({\bm{\beta}}_{1,j^{*}}-{\bm{\beta}}_{2,j^{*}})^{2}\frac{3n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}+\delta
n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}}{n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})(1-\delta)}\frac{1}{(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})^{2}}}\right)$
$\displaystyle=\exp\left(-\frac{2(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})t^{2}}{({\bm{\beta}}_{1,j^{*}}-{\bm{\beta}}_{2,j^{*}})^{2}\frac{3+\delta}{1-\delta}}\right)$
$\displaystyle\overset{i)}{\leq}\exp\left(-\frac{2(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})t^{2}}{4\|{\bm{\beta}}\|^{2}_{2}\frac{3+\delta}{1-\delta}}\right)$
$\displaystyle=\exp\left(-\frac{(1-\delta)}{2(3+\delta)}(1+\sigma^{2}/\|{\bm{\beta}}\|^{2}_{2})t^{2}\right),$

where $i)$ follows from
$({\bm{\beta}}_{1,j^{*}}-{\bm{\beta}}_{2,j^{*}})^{2}\leq\|{\bm{\beta}}_{1}-{\bm{\beta}}_{2}\|^{2}_{2}$
and the triangle inequality. Applying the law of total probability to the
above, we obtain the result. ∎

###  D.2 $\mathtt{CORR}$ for $\mathtt{MSLR-D}$

###### Proof of Theorem 2.5.

We first note that, since
$({\bm{\beta}}_{1},{\bm{\beta}}_{2})\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|{\bm{\beta}}\|_{2}}(\mathcal{D})$, the two signals
have equal norm. Hence, the complement of the $\mathtt{SB}$-$\mathtt{MSLR}$
regime can be equivalently expressed through the condition
$\phi{\bm{\beta}}_{1}+(1-\phi){\bm{\beta}}_{2}\neq 0$.

Let $\mathtt{CORR}({\bm{X}},{\bm{y}})$ denote the output of running
$\mathtt{CORR}$ on inputs ${\bm{X}},{\bm{y}}$. Consider the test function

$g\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right):=\begin{cases}\mathtt{p}&\mathtt{CORR}({\bm{X}},{\bm{y}})\neq\emptyset\\\
\mathtt{q}&\mathtt{CORR}({\bm{X}},{\bm{y}})=\emptyset\end{cases}.$

Let ${\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\mathbin{\overset{}{\kern
0.0pt\sim}}{{\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})}$. Recall that
$\mathtt{CORR}$ outputs the following set

$\mathtt{CORR}({\bm{X}},{\bm{y}})=\left\\{j\in[p]:\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right\\}.$

As in the proof of Theorem D.1, we note that

$\displaystyle\mathbb{P}\left[\max_{q\in[p]}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle\leq\mathbb{P}\left[\max_{q\in[p]}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2\log{2p}}+\frac{\epsilon}{2\sqrt{8}}\sqrt{\log{2p}}\right].$
(26)

Noting that for ${\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\mathbin{\overset{}{\kern
0.0pt\sim}}{{\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})}$ we have that
$\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$, we apply Lemma D.9 to (26) and obtain that

$\displaystyle\mathbb{P}\left[\max_{q\in[p]}\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right]\leq(2p)^{-\frac{1}{8}\left(\frac{\epsilon}{2}\right)^{2}},$

and hence we have that, under
${{\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})}$,
$g\left({\begin{bmatrix}{\bm{X}}\\\ {\bm{y}}\end{bmatrix}}\right)=\mathtt{q}$
with probability $1-o(1)$.

Conversely, let ${\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\mathbin{\overset{}{\kern
0.0pt\sim}}{{\mathbb{P}}({\bm{X}},{\bm{y}})}$. Let $J\subseteq{\rm
supp}({\bm{\beta}}_{1})\cup{\rm supp}({\bm{\beta}}_{2})$ such that
$\phi{\bm{\beta}}_{1,j}+(1-\phi){\bm{\beta}}_{2,j}\neq 0$ for $j\in J$. From
Lemma D.3, we then have that,

$\displaystyle\mathbb{P}\left[|\mathtt{CORR}({\bm{X}},{\bm{y}})|=0\right]$
$\displaystyle=\mathbb{P}\left[\cap_{j\in[p]}\left\\{\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right\\}\right]$
$\displaystyle\leq\mathbb{P}\left[\cap_{j\in
J}\left\\{\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right\\}\right]$
$\displaystyle\leq\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{J_{1}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle\leq\left(\frac{1}{p}+6e^{\frac{\delta^{2}n}{w}}+\frac{39}{\delta^{2}n}\right)=o(1),$

and hence we have that, under ${{\mathbb{P}}({\bm{X}},{\bm{y}})}$,
$g\left({\begin{bmatrix}{\bm{X}}\\\ {\bm{y}}\end{bmatrix}}\right)=\mathtt{p}$
with probability $1-o(1)$. ∎

###  D.3 Recovery algorithms for $\mathtt{MSLR}$

#### General recovery algorithm for $\mathtt{MSLR}$

A recovery algorithm for $\mathtt{MSLR}$ in the noiseless and balanced regimes
is given in Theorem 2.6. We measure the recovery error in $\mathtt{MSLR}$ as
in Chen et al. (2014),

$\rho(\hat{\bm{\theta}},\bm{\theta}):=\min\left\\{\left\|\hat{\bm{{\bm{\beta}}}}_{1}-\bm{{\bm{\beta}}}_{1}\right\|_{2}+\left\|\hat{\bm{{\bm{\beta}}}}_{2}-\bm{{\bm{\beta}}}_{2}\right\|_{2},\left\|\hat{\bm{{\bm{\beta}}}}_{1}-\bm{{\bm{\beta}}}_{2}\right\|_{2}+\left\|\hat{\bm{{\bm{\beta}}}}_{2}-\bm{{\bm{\beta}}}_{1}\right\|_{2}\right\\},$

where $\hat{\bm{\theta}}=(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})$ and
$\bm{\theta}=({\bm{\beta}}_{1},{\bm{\beta}}_{2})$.

###### Proof of Theorem 2.6.

In the case of $\sigma=0,\phi\neq 1/2$ (noiseless), we first apply
$\mathtt{CORR}$ and then the Alternating Minimization (AM) algorithm of Yi et
al. (2014). Theorem D.12 shows that this succeeds in the regime of interest.

In the case of $\phi=1/2$ (balanced), $\texttt{SNR}=\Omega(k)$, we first apply
$\mathtt{CORR}$ and then the algorithm of Chen et al. (2014). Theorem D.20
proves that in the high SNR regime $\texttt{SNR}=\Omega(1)$, we have that
$\rho(\hat{\theta},\theta)=\Theta\left(\sigma\sqrt{\frac{k}{n}}\right)$. In
order for exact recovery to be achieved for all allowable finite $n$, we would
require
$\sqrt{\frac{\sigma^{2}k}{(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{p}}}\to
0$, which is satisfied for
$\texttt{SNR}=\|{\bm{\beta}}\|^{2}_{2}/\sigma^{2}=\Omega(k)$, implying a non-
vanishing signal-to-noise ratio with respect to the support set. This is
satisfied by hypothesis, and hence $\mathtt{CORR}$ together with Algorithm 6
succeeds in solving asymptotically exact recovery (up to relabeling of
${\bm{\beta}}_{1}$ and ${\bm{\beta}}_{2}$) in the regime of interest. ∎

#### Recovery algorithm for noiseless, unbalanced $\mathtt{MSLR}$

In this section we will show that the $\mathtt{CORR}$ algorithm can be used to
reduce the $\mathtt{MSLR}$ problem to a dense problem where $n,k=\Theta(p)$
and the signal is not assumed to be sublinearly sparse, where state-of-the-art
algorithms for this dense mixed linear regression case can then infer
${\bm{\beta}}_{1}$ from ${\bm{\beta}}_{2}$. In the noiseless case with
$\phi\neq 1/2$, we can apply $\mathtt{CORR}$ together with the existing
polynomial-time Alternating Minimization (AM) algorithm from Yi et al. (2014)
to fully solve $\mathtt{MSLR}$ in what is a constant number of steps. We
recall that Theorem D.1 only provided guarantees on the support recovery of
the joint signal, whereas now with the execution of the AM algorithm on the
reduced joint support set one can fully infer ${\bm{\beta}}_{1}$ from
${\bm{\beta}}_{2}$. Define the mixture proportions,

$\displaystyle\frac{n_{1}}{n}:=\frac{\sum_{i=1}^{n}z_{i}}{n}$
$\displaystyle\frac{n_{2}}{n}:=\frac{\sum_{i=1}^{n}(1-z_{i})}{n}.$

We begin by stating the theorem.

######  Theorem D.12 (Success of $\mathtt{CORR}+$ AM on noiseless
$\mathtt{MSLR}$).

Consider the general setting of $\mathtt{MSLR}$ with parameters
$p,n,k,\sigma=0$, $\phi\neq 1/2$,
$({\bm{\beta}}_{1},{\bm{\beta}}_{2})\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|{\bm{\beta}}\|_{2}}(\mathcal{D})$. Suppose

$n\geq\frac{32}{\min\\{\phi^{2}{\bm{\beta}}^{2}_{\texttt{min}},(1-\phi)^{2}{\bm{\beta}}^{2}_{\texttt{min}},\langle{\bm{\beta}}\rangle^{2}_{\texttt{min}}\\}}(1+\epsilon)\|{\bm{\beta}}\|^{2}_{2}\log{2p}$

for $\epsilon\in(0,1)$ used in $\mathtt{CORR}$. Then with probability at least
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$ for
constants $c_{1},c_{2}>0$, the output
$\hat{\theta}=(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})$ of
$\mathtt{CORR}+$ Algorithm 3 $+$ Algorithm 5 satisfies

$\rho(\hat{\theta},\theta)=0.$

###### Proof of Theorem D.12.

By Theorem D.1, we can recover the joint support set (at most of size $2k$) of
signals $({\bm{\beta}}_{1},{\bm{\beta}}_{2})$ with probability at least
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$ by running
$\mathtt{CORR}$.

After running $\mathtt{CORR}$ and identifying the $<2k$ joint support set
indices, we restrict the regression problem to these indices by removing all
other columns from the design matrix ${\bm{X}}$ (as these do not influence the
output $y$ since they do not correspond to support indices of
${\bm{\beta}}_{1}$ or ${\bm{\beta}}_{2}$). We are then tasked with solving a
two-component mixtures of regressions problem with $n$ samples and signals of
dimension between $k$ and $2k$ (importantly, the dimension is no longer $p$).

From this point, the idea is to spectrally initialize
$({\bm{\beta}}_{1}^{(0)},{\bm{\beta}}^{(0)}_{2})$ using Algorithm 3 for which
Proposition D.14 provides guarantees, pass
$({\bm{\beta}}_{1}^{(0)},{\bm{\beta}}^{(0)}_{2})$ into Algorithm 5 for which
Theorem D.15 provides guarantees on geometric error decay given this
initialization, and run Algorithm 5 for a finite number of iterations
guaranteed by Proposition D.16.

The condition on sample size $n$ of Proposition D.14 is met, since it is
assumed that
$n\gtrsim\|{\bm{\beta}}\|^{2}_{2}\log{2p}\geq{\bm{\beta}}_{\texttt{min}}^{2}k\log{2p}$
and $k\log{2p}=\omega(k\log^{2}{k})$. The condition of Theorem D.15 is met by
the result of Proposition D.14. The condition of Proposition D.16 is met by
running Algorithm 5 (resampling) with $O(k\log^{2}{k})$ samples (see Remark
D.17).

What remains to show is that $n_{1}\neq n_{2}$, as this is required by Remark
D.13. Recall $n_{1}=\sum_{i=1}^{n}z_{i}$ and $n_{2}=\sum_{i=1}^{n}(1-z_{i})$
and $z_{i}$ are independent $\text{Bernoulli}(\phi)$. Without loss of
generality assuming $\phi<1/2$, there exists a $\delta\in(0,1)$ such that,

$\displaystyle{\mathbb{P}}\left[\frac{1}{n}\sum_{i=1}^{n}z_{i}\geq
1/2\right]\leq{\mathbb{P}}\left[\frac{1}{n}\sum_{i=1}^{n}z_{i}\geq(1+\delta)\phi\right]\leq
e^{-\Theta{(n)}},$

after applying a standard Chernoff bound. This high probability statement can
be absorbed into the
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$ high
probability statement provided by $\mathtt{CORR}$ , choosing adjusted
constants $c_{1},c_{2}>0$.

We hence conclude that running $\mathtt{CORR}$ followed by Algorithm 3
followed by Algorithm 5 we obtain
$\rho(\mathbf{\theta}^{(t)},\mathbf{\theta})=0$ in finite $t$ with probability
at least $1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$.
∎

Their initialization algorithm is based on the positive semidefinite matrix:

$\displaystyle
M:=\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}{\bm{x}}_{i}\otimes{\bm{x}}_{i}$

which serves as an unbiased estimator of a matrix whose two largest
eigenvectors span the space spanned by ${\bm{\beta}}_{1},{\bm{\beta}}_{2}$.

######  Remark D.13.

It is stated in Fan et al. (2018) that, when the mixture frequencies are equal
to each other ($n_{1}=n_{2}$), the top two eigenvectors of
${\mathop{\mathbb{E}}}M$ will not be ${\bm{\beta}}_{1},{\bm{\beta}}_{2}$.
Hence, their algorithms only work for the case $\phi\neq 1/2$ and $\sigma=0$
(noiseless).

Outside of the case $\phi=1/2$, when the mixture proportions are known, an
approximation of ${\bm{\beta}}_{1},{\bm{\beta}}_{2}$ can be computed in closed
form through Algorithm 3, where

$sign(b)=\begin{cases}1,\;b=1\\\ -1,\;b=2.\end{cases}$

;

Data: Input: $n_{1},n_{2}$, samples $\\{(y_{i},{\bm{x}}_{i}),i=1,2,...,n\\}$

;

$M\leftarrow\frac{1}{N}\sum_{i=1}^{N}y_{i}^{2}{\bm{x}}_{i}\otimes{\bm{x}}_{i}$
;

Compute top 2 eigenvectors and eigenvalues $(v_{b},\lambda_{b}),b=1,2$ of
$(M-I)/2$ ;

Compute
${\bm{\beta}}_{b}^{(0)}=\sqrt{\frac{1-\Delta_{b}}{2}}v_{b}+sign(b)\sqrt{\frac{1+\Delta_{b}}{2}}v_{-b}$,
where
$\Delta_{b}=\frac{(\lambda_{b}-\lambda_{-b})^{2}+n_{b}^{2}-n_{-b}^{2}}{2(\lambda_{-b}-\lambda_{b})n_{b}},\;b=1,2$

return ${\bm{\beta}}_{1}^{(0)},{\bm{\beta}}_{2}^{(0)}$

Algorithm 3 Initialization with proportion information

In what follows, we state the iterative algorithms proposed in Fan et al.
(2018) and their guarantees.

Data: Initial ${\bm{\beta}}_{1}^{(0)},{\bm{\beta}}_{2}^{(0)}$, # iterations
$t_{0}$, samples $\\{(y_{i},{\bm{x}}_{i}),i=1,2,...,N\\}$

for  _$t=0,\cdots,t_{0}-1$_ do

$J_{1},J_{2}\leftarrow\emptyset$;

for  _$i=1,2,\cdots,N$_ do

if  _$\left|y_{i}-\langle{{\bm{x}}_{i}},{{\bm{\beta}}}_{1}^{(t)}\rangle\right|
<\left|y_{i}-\langle{{\bm{x}}_{i}},{{\bm{\beta}}_{2}^{(t)}}\rangle\right|$_
then

$J_{1}\leftarrow J_{1}\cup\\{i\\}$;

else

$J_{2}\leftarrow J_{2}\cup\\{i\\}$;

end if

end for

;

${\bm{\beta}}_{1}^{(t+1)}\leftarrow\operatorname*{arg\,min}_{{\bm{\beta}}\in{\mathbb{R}}^{k}}\|{{\bm{y}}_{J_{1}}-{\bm{X}}_{J_{1}}{\bm{\beta}}}\|_{2}$

${\bm{\beta}}_{2}^{(t+1)}\leftarrow\operatorname*{arg\,min}_{{\bm{\beta}}\in{\mathbb{R}}^{k}}\|{\bm{y}}_{J_{2}}-{\bm{X}}_{J_{2}}{\bm{\beta}}\|_{2}$
;

end for

return ${\bm{\beta}}_{1}^{(t_{0})},{\bm{\beta}}_{2}^{(t_{0})}$

Algorithm 4 AM

######  Proposition D.14.

(Yi et al., 2014) Consider the initialization method in Algorithm 3. Given any
constant $\widehat{c}<1/2$, with probablity at least $1-\frac{1}{p^{2}}$, the
approach produces an initialization
$({\bm{\beta}}_{1}^{(0)},{\bm{\beta}}_{2}^{(0)})$ satisfying

$\displaystyle\rho({\mathbf{\theta}}^{(0)},\mathbf{\theta})~{}\leq~{}\widehat{c}\,\min\\{n_{1}/n,n_{2}/n\\}\,\|{\bm{\beta}}_{1}-{\bm{\beta}}_{2}\|_{2},$

if

$n\geq c_{1}\left(\frac{1}{\widetilde{\delta}}\right)^{2}\,p\,\log^{2}p.$

Here $c_{1}$ is a constant that depends on $\widehat{c}$. And

$\sqrt{\widetilde{\delta}}=\widehat{c}\sqrt{\min\\{n_{1}/n,n_{2}/n\\}}^{3}\|{\bm{\beta}}_{1}-{\bm{\beta}}_{2}\|_{2}(\sqrt{1-\kappa})\kappa,$

where
$\kappa=\sqrt{1-4(1-\langle{{\bm{\beta}}_{1}},{{\bm{\beta}}_{2}}\rangle^{2})\frac{n_{1}}{n}\frac{n_{2}}{n}}$.

Data: Initial ${\bm{\beta}}_{1}^{(0)},{\bm{\beta}}_{2}^{(0)}$, # iterations
$t_{0}$, samples $\\{(y_{i},{\bm{x}}_{i}),i=1,2,...,N\\}$

Partition the samples $\\{(y_{i},{\bm{x}}_{i})\\}$ into $t_{0}$ disjoint sets:
$\mathcal{S}_{1},...,\mathcal{S}_{t_{0}}$

for  _$t=1,\cdots,t_{0}$_ do

Use $\mathcal{S}_{t}$ to run Algorithm 4 initialized with
$({\bm{\beta}}_{1}^{(t-1)},{\bm{\beta}}_{2}^{(t-1)})$ and returning
$({\bm{\beta}}_{1}^{t},{\bm{\beta}}_{2}^{t})$

end for

return ${\bm{\beta}}_{1}^{(t_{0})},{\bm{\beta}}_{2}^{(t_{0})}$

Algorithm 5 AM with resampling

######  Theorem D.15.

Yi et al. (2014) Consider one iteration in Algorithm 5. For fixed
$({\bm{\beta}}_{1}^{(t-1)},{\bm{\beta}}_{2}^{(t-1)})$, there exist absolute
constants $\widetilde{c},c_{1},c_{2}$ such that if

$\rho({\mathbf{\theta}}^{(t-1)},\mathbf{\theta})~{}\leq~{}\widetilde{c}\,\min\\{n_{1}/n,n_{2}/n\\}\,\|\mathbf{{\bm{\beta}}}_{1}^{*}-\mathbf{{\bm{\beta}}}_{2}^{*}\|_{2},$

and if the number of samples in that iteration satisfies

$|\mathcal{S}_{t}|~{}\geq~{}\left(\frac{c_{1}}{\min\\{n_{1}/n,n_{2}/n\\}}\right)\,p,$

then with probability greater than $1-\exp(-c_{2}p)$ we have a geometric
decrease in the error at the next stage, i.e.

$\rho({\mathbf{\theta}}^{(t)},\mathbf{\theta})\leq\frac{1}{2}\rho({\mathbf{\theta}}^{(t-1)},\mathbf{\theta})$

######  Proposition D.16.

(Exact Recovery) Yi et al. (2014) There exist absolute constants $c_{1},c_{2}$
such that if

$\rho({\mathbf{\theta}}^{(t-1)},\mathbf{\theta})\leq\frac{c_{1}}{p^{2}}\|{\bm{\beta}}_{1}-{\bm{\beta}}_{2}\|_{2}$

and

$\frac{1}{\min\\{n_{1}/n,n_{2}/n\\}}p<|\mathcal{S}_{t}|<c_{2}p,$

then with probability greater than $1-\frac{1}{p}$,

$\rho({\mathbf{\theta}}^{(t)},\mathbf{\theta})=0.$

######  Remark D.17.

It is easy to see, and remarked in Fan et al. (2018) (pp. 11-12, above and
below Proposition 4) that, running Algorithm 5 with guarantees given in
Theorem D.15, one would require $O(p\log^{2}{p})$ samples to obtain
$\rho({\mathbf{\theta}}^{(t-1)},\mathbf{\theta})\leq\frac{c_{1}}{p^{2}}\|\mathbf{{\bm{\beta}}}_{1}^{*}-\mathbf{{\bm{\beta}}}_{2}^{*}\|_{2}$
for the constant $c_{1}>0$ suitable for Proposition D.16.

#### Algorithm for $\mathtt{MSLR}$ in the balanced case

Consider the case of Mixtures of Linear Regressions ($\mathtt{MLR}$) as in
Chen et al. (2014), where $n,k=\Theta(p)$, and $\sigma^{2}$ is known. Further,
consider the balanced regime where $\phi=1/2$, but
${\bm{\beta}}_{1,j}\neq-{\bm{\beta}}_{2,j}$ for any
$j\in\mathcal{S}_{1}\cap\mathcal{S}_{2}$
($\langle{\bm{\beta}}\rangle^{2}_{\texttt{min}}\neq 0$). We claim that we can
solve the aforementioned $\mathtt{MSLR}$ problem in this regime by recovering
the joint support of ${\bm{\beta}}_{1},{\bm{\beta}}_{2}$ using $\mathtt{CORR}$
, and then running the algorithm in Chen et al. (2014) for general mixed
linear regression. This latter Algorithm 6 is outlined below.

;

Data: $({\bm{X}},{\bm{y}})\in\mathbb{R}^{n\times p}\times\mathbb{R}^{n}$

;

Let
$(\hat{\bm{K}},\hat{\bm{g}}):=\operatorname*{arg\,min}_{\bm{K},\bm{g}}\;\sum_{i=1}^{n}\left(-\left\langle\bm{x}_{i}\bm{x}_{i}^{\top},\bm{K}\right\rangle+2y_{i}\left\langle\bm{x}_{i},\bm{g}\right\rangle-
y_{i}^{2}+\sigma^{2}\right)^{2}+\lambda\left\|\bm{K}\right\|_{*}$ ;

Compute the matrix
$\hat{\bm{J}}=\hat{\bm{g}}\hat{\bm{g}}^{\top}-\hat{\bm{K}}$, and its first
eigenvalue-eigenvector pair $\hat{\lambda}$ and $\hat{\bm{v}}$ ;

Compute
$\hat{\bm{{\bm{\beta}}}}_{1},\hat{\bm{{\bm{\beta}}}}_{2}=\hat{\bm{g}}\pm\sqrt{\hat{\lambda}}\hat{\bm{v}}$
;

return $(\hat{\bm{{\bm{\beta}}}}_{1},\hat{\bm{{\bm{\beta}}}}_{2})$

Algorithm 6 Estimate ${\bm{\beta}}$’s (Chen et al., 2014)

As motivated in (Chen et al., 2014), the algorithm performs a convex penalized
least squares optimization to determine matrix and vector
$(\hat{\bm{K}},\hat{\bm{g}})$, $\hat{\bm{g}}$ being a naive estimate of
${\bm{\beta}}_{1},{\bm{\beta}}_{2}$ and the leading eigenvector-eigenvalue of
$\hat{\bm{J}}$ a necessary correction. We define the value
$\alpha:=\frac{\left\|\bm{{\bm{\beta}}}_{1}-\bm{{\bm{\beta}}}_{2}\right\|_{2}^{2}}{\left\|\bm{{\bm{\beta}}}_{1}\right\|_{2}^{2}+\left\|\bm{{\bm{\beta}}}_{2}\right\|_{2}^{2}}$.

######  Definition D.18.

(Chen et al., 2014) Let $n_{1}=\left\\{i\in[n]:z_{i}=1\right\\}$ denote the
number of samples obtained from ${\bm{\beta}}_{1}$, and $n_{2}$ the analogous
for ${\bm{\beta}}_{2}$. We define the following regularity conditions,
required for our further proofs:

  1. 1.

${\bm{X}}$ is an i.i.d. standard Gaussian matrix,

  2. 2.

$\alpha\geq c_{3}$,

  3. 3.

$\min\\{n_{1},n_{2}\\}\geq c_{4}p$,

  4. 4.

$\lambda=\Theta(\sigma(\|{\bm{\beta}}_{1}\|_{2}+\|{\bm{\beta}}_{2}\|_{2}+\sigma)\sqrt{np}\log^{3}{n})$,

  5. 5.

$n\geq c_{3}p\log^{8}{n}$,

  6. 6.

$|n_{1}-n_{2}|=O\left(\sqrt{n\log{n}}\right)$,

for some constants $0<c_{3}<2$ and $c_{4}$.

######  Theorem D.19.

Chen et al. (2014) Suppose the conditions in Definition D.18 hold. There exist
constants $c_{1},c_{2},c_{4}>0$ such that with probability at least
$1-c_{1}n^{-c_{2}}$, the output
$\hat{\theta}=(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})$ of
$\mathtt{Algorithm\;3}$ satisfies

$\rho(\hat{\theta},\theta)\leq
c_{4}\sigma\sqrt{\frac{p}{n}}\log^{4}{n}+c_{4}\min\left\\{\frac{\sigma^{2}}{\|{\bm{\beta}}_{1}\|_{2}+\|{\bm{\beta}}_{2}\|_{2}},\sigma\left(\frac{p}{n}\right)^{1/4}\right\\}\log^{4}{n}.$

The result in Theorem D.19 implies that, in the high-snr regime
$\|{\bm{\beta}}\|^{2}_{2}/\sigma^{2}=\Omega(1)$, we have that
$\rho(\hat{\theta},\theta)=\Theta(\sigma\sqrt{\frac{p}{n}})$. This holds since
$\|{\bm{\beta}}_{1}\|_{2}+\|{\bm{\beta}}_{2}\|_{2}=2\sqrt{k}$.

######  Theorem D.20 (Success of
$\mathtt{CORR}+\mathtt{Algorithm\;\ref{algo:balanced}}$ on $\mathtt{MSLR}$).

Consider the general setting of $\mathtt{MSLR}$ with parameters
$p,n,k,\phi=1/2$,
$({\bm{\beta}}_{1},{\bm{\beta}}_{2})\mathbin{\overset{}{\kern
0.0pt\sim}}\mathcal{P}_{\|{\bm{\beta}}\|_{2}}(\mathcal{D})$. Suppose the
conditions of Definition D.18 hold. There exist constants
$c_{1},c_{2},c_{4}>0$ such that, provided

$n\geq\frac{32}{\min\\{\phi^{2}{\bm{\beta}}^{2}_{\texttt{min}},(1-\phi)^{2}{\bm{\beta}}^{2}_{\texttt{min}},\langle{\bm{\beta}}\rangle^{2}_{\texttt{min}}\\}}(1+\epsilon)(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$

for $\epsilon\in(0,1)$ used in $\mathtt{CORR}$ , with probability at least
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$, the
output $\hat{\theta}=(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})$ of
$\mathtt{CORR}+\mathtt{Algorithm\;\ref{algo:balanced}}$ satisfies

$\rho(\hat{\theta},\theta)\leq
c_{4}\sigma\sqrt{\frac{2k}{n}}\log^{4}{n}+c_{4}\min\left\\{\frac{\sigma^{2}}{\|{\bm{\beta}}_{1}\|_{2}+\|{\bm{\beta}}_{2}\|_{2}},\sigma\left(\frac{2k}{n}\right)^{1/4}\right\\}\log^{4}{n}.$

###### Proof of Theorem D.20.

By Theorem D.1, we can recover the joint support set (at most of size $2k$) of
signals $({\bm{\beta}}_{1},{\bm{\beta}}_{2})$ with probability at least
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$ by running
$\mathtt{CORR}$.

After running $\mathtt{CORR}$ and identifying the $<2k$ joint support set
indices, we restrict the regression problem to these indices by removing all
other columns from the design matrix ${\bm{X}}$ (as these do not influence the
output $y$ since they do not correspond to support indices of
${\bm{\beta}}_{1}$ or ${\bm{\beta}}_{2}$). We are then tasked with solving a
two-component mixtures of regressions problem with $n$ samples and signals of
dimension between $k$ and $2k$. We run $\mathtt{Algorithm\;3}$ on this
simplified regression problem, to obtain
$(\hat{{\bm{\beta}}}_{1},\hat{{\bm{\beta}}}_{2})$.

What remains is to show that the assumptions of Theorem D.19 hold with $p$
replaced by $2k$. Indeed, condition $1.$ holds since without loss of
generality we can assume ${\bm{\beta}}_{1}\neq{\bm{\beta}}_{2}$, otherwise the
problem setting would be that of $\mathtt{SLR}$. Condition $3.,4.,5.$ hold by
the definition of the $\mathtt{MSLR}$ problem, and by freedom with respect to
$\lambda$ and $c_{3}$.

Condition $2.$ holds with probability at least
$1-\exp\left(-\Theta(n)\right)$, indeed by Hoeffding’s inequality (Boucheron
et al., 2013) we have that

$\displaystyle\mathbb{P}\left[n_{1}<2c_{4}k\right]$
$\displaystyle=\mathbb{P}\left[\sum_{i=1}^{n}z_{i}<2c_{4}k\right]$
$\displaystyle=\mathbb{P}\left[\sum_{i=1}^{n}(z_{i}-\phi)<2c_{4}k-\phi
n\right]$ $\displaystyle=\mathbb{P}\left[\sum_{i=1}^{n}(-z_{i}+\phi)\geq\phi
n-2c_{4}k\right]$ $\displaystyle\leq\exp\left(-\Theta(n)\right),$

where $\phi n-2c_{4}k$ is positive for some $c_{4}>0$ since by assumption
$n\geq\frac{32(1+\epsilon)}{\min\\{(2\phi-1)^{2},\phi^{2},(1-\phi)^{2}\\}}(1+\epsilon)(k+\sigma^{2})\log{p}$
and $(k+\sigma^{2})\log{p}=\omega(k)$, analogously for $n_{2}$.

In the case $\phi=1/2$ (so that $2\phi-1=0$), we have that condition $6.$
holds with probability $\exp(-\Theta(\log{n}))$ by Hoeffding’s inequality,

$\displaystyle\mathbb{P}\left[\left|\sum_{i=1}^{n}z_{i}-\sum_{i=1}^{n}(1-z_{i})\right|\geq\Theta(\sqrt{n\log{n}})\right]$
$\displaystyle\leq\mathbb{P}\left[\sum_{i=1}^{n}(2z_{i}-1)\geq\Theta(\sqrt{n\log{n}})\right]+\mathbb{P}\left[\sum_{i=1}^{n}(-2z_{i}+1)\geq\Theta(\sqrt{n\log{n}})\right]$
$\displaystyle\leq
2\exp\left(-\frac{2\Theta(n\log{n})}{2n}\right)=\exp\left(-\Theta(\log{n})\right).$

The above events occur with probability at least $1-\exp(-\Theta(\log{n}))$,
and the event that $\mathtt{CORR}$ succeeds occurs with probability
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$. These two
events occur together with probability at least
$1-c_{1}(\frac{k}{p}+ke^{-c_{2}n}+\frac{k}{n}+\frac{1}{p^{c_{2}}})$ for
adjusted constants $c_{1},c_{2}>0$. Applying Theorem D.19, we obtain the
result. ∎

###  D.4 $\mathtt{CORR}$ for signed support recovery in $\mathtt{SLR}$

###### Proof of Theorem 2.9.

The proof proceeds similarly as that of Theorem 2.5. Let
$\mathtt{CORR}({\bm{X}},{\bm{y}})$ denote the output of running
$\mathtt{CORR}$ on inputs ${\bm{X}},{\bm{y}}$. Consider the test function

$g\left({\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\right):=\begin{cases}\mathtt{p}&\mathtt{CORR}({\bm{X}},{\bm{y}})\neq\emptyset\\\
\mathtt{q}&\mathtt{CORR}({\bm{X}},{\bm{y}})=\emptyset\end{cases}.$

Let ${\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\mathbin{\overset{}{\kern
0.0pt\sim}}{{\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})}$. Recall that
$\mathtt{CORR}$ outputs the following set

$\mathtt{CORR}({\bm{X}},{\bm{y}})=\left\\{j\in[p]:\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right\\}.$

As in the proof of Theorem 2.10, we note that for ${\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\mathbin{\overset{}{\kern
0.0pt\sim}}{{\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})}$ we have
$\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$. Applying Lemma D.9 to (27) we obtain,

$\displaystyle\mathbb{P}\left[\max_{q\in[p]}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle\leq\mathbb{P}\left[\max_{q\in[p]}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2\log{2p}}+\frac{\epsilon}{2\sqrt{8}}\sqrt{\log{2p}}\right],$
(27) $\displaystyle\leq{p^{-\frac{1}{16}(\frac{\epsilon}{2})^{2}}}=o(1),$

and hence we have that, under
${{\mathbb{P}}({\bm{X}})\otimes{\mathbb{P}}({\bm{y}})}$,
$g\left({\begin{bmatrix}{\bm{X}}\\\ {\bm{y}}\end{bmatrix}}\right)=\mathtt{q}$
with probability $1-o(1)$.

Conversely, let ${\begin{bmatrix}{\bm{X}}\\\
{\bm{y}}\end{bmatrix}}\mathbin{\overset{}{\kern
0.0pt\sim}}{{\mathbb{P}}({\bm{X}},{\bm{y}})}$. We then apply Theorem 2.10 to
deduce that $\mathtt{CORR}({\bm{X}},{\bm{y}})={\rm
supp}({\bm{\beta}})\neq\emptyset$ with probability at least
$1-\left(\frac{k}{p}+2ke^{-c_{2}n}+\frac{1}{p^{c_{2}}}\right)$ for some
constant $c_{2}>0$. Hence, under ${\mathbb{P}}({\bm{X}},{\bm{y}})$,
$g\left({\begin{bmatrix}{\bm{X}}\\\ {\bm{y}}\end{bmatrix}}\right)=\mathtt{p}$
with probability $1-o(1)$. ∎

In what follows, we consider the modified $\mathtt{CORR}$ algorithm in (3) for
estimating the signed support of ${\bm{\beta}}$.

###### Proof of Theorem 2.10.

Let $\mathcal{S}$ denote the support set of ${\bm{\beta}}$. Define the error
event

$\mathcal{E}=\cup_{j\in\mathcal{S}}\left\\{\left|\frac{\langle{\bm{X}}_{j},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\sqrt{2(1+\epsilon/2)\log{2p}}\right\\}\cup\left\\{\max_{q\in\mathcal{S}^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right\\}.$

The theorem claim follows by demonstrating that
$\mathbb{P}\left[\mathcal{E}\right]=o(1)$. With this in mind, we perform a
union bound

$\displaystyle\mathbb{P}\left[\mathcal{E}\right]$ $\displaystyle\leq
k\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|<\sqrt{2(1+\epsilon/2)\log{2p}}\right]+\mathbb{P}\left[\max_{q\in\mathcal{S}^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle:=k\nu_{1}+\nu_{2}$

where $j^{*}\in\mathcal{S}$. We first focus on $\nu_{2}$, where we notice
$\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$ for $q\in\mathcal{S}^{\complement}$. Applying
Lemma D.9, we deduce that

$\displaystyle\nu_{2}$
$\displaystyle=\mathbb{P}\left[\max_{q\in\mathcal{S}^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
$\displaystyle\leq\mathbb{P}\left[\max_{q\in\mathcal{S}^{\complement}}\left|\frac{\langle{\bm{X}}_{q},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\geq\sqrt{2\log{2p}}+\frac{\epsilon}{2\sqrt{8}}\sqrt{\log{2p}}\right]$
$\displaystyle\leq(2p)^{-\frac{1}{16}\left(\frac{\epsilon}{2}\right)^{2}},$

since $\sqrt{2(1+\epsilon/2)}\geq\sqrt{2}+\frac{\epsilon}{2\sqrt{8}}$. Setting
$n\geq\frac{8(1+\epsilon)}{{\bm{\beta}}^{2}_{\min}}(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$
for some $\epsilon\in(0,1)$, the bound for $\nu_{1}$ follows from applying
Lemma D.21 below:

$\nu_{1}\leq\frac{1}{2p}+2e^{-\frac{\delta^{2}n}{8}}.$

Putting it all together, we obtain that
$\mathbb{P}\left[\mathcal{E}\right]\leq\frac{k}{2p}+2ke^{-c_{2}n}+\frac{1}{p^{c_{2}}}$,
for some constant $c_{2}>0$. ∎

######  Lemma D.21 (Concentration bound for $\mathtt{SLR}$).

Consider the setting of $\mathtt{SLR}$ for $j^{*}\in\mathcal{S}$. Then for
$n\geq\frac{8(1+\epsilon)}{{\bm{\beta}}^{2}_{\min}}(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$
we have

$\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right]\leq\frac{1}{p}+2e^{-\frac{\delta^{2}n}{8}}$

###### Proof.

Let
$\nu:=\mathbb{P}\left[\left|\frac{\langle{\bm{X}}_{j^{*}},{\bm{y}}\rangle}{\|{\bm{y}}\|_{2}}\right|\leq\sqrt{2(1+\epsilon/2)\log{2p}}\right]$
and $\delta>0$ to be chosen later. We begin by conditioning on the event
$\Omega_{1}:=\Omega_{1}(\delta)$ from Lemma D.9, and apply Lemma D.5 (for the
case $z_{i}=1$) denoting $g_{i}\mathbin{\overset{\text{i.i.d.}}{\kern
0.0pt\sim}}\mathcal{N}(0,1)$ for $i\in[n]$ as independent (also from $y$, $z$)
unit normal Gaussians, obtaining

$\displaystyle\nu$
$\displaystyle=\int\mathbb{P}\left[\left|\frac{{\bm{X}}_{j^{*}}^{T}\xi}{\|\xi\|_{2}}\right|<\sqrt{2(1+\epsilon/2)\log{2p}}\;\middle|\;{\bm{y}}\right]d\mathbb{P}\left[y\right]$
$\displaystyle=\int\mathbb{P}\left[\left|\sum_{i=1}^{n}g_{i}\frac{y_{i}}{\|{\bm{y}}\|_{2}}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}+\frac{{\bm{\beta}}_{j^{*}}\cdot
y^{2}_{i}/\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|<\sqrt{2(1+\epsilon/2)\log{2p}}\;\middle|\;{\bm{y}}\right]d\mathbb{P}\left[y\right]$
$\displaystyle=\int\mathbb{P}\left[\left|g_{1}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}+\frac{{\bm{\beta}}_{j^{*}}\cdot\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|<\sqrt{2(1+\epsilon/2)\log{2p}}\;\middle|\;{\bm{y}}\right]d\mathbb{P}\left[y\right]$
$\displaystyle\leq\mathbb{P}\left[\left|g_{1}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}+\frac{{\bm{\beta}}_{j^{*}}\cdot\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|<\sqrt{2(1+\epsilon/2)\log{2p}}\;\middle|\;\Omega_{1}\right]+\mathbb{P}\left[\Omega^{\complement}_{1}\right]$
$\displaystyle=\mathbb{P}\left[\left\\{g_{1}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}+\frac{{\bm{\beta}}_{j^{*}}\cdot\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}<\sqrt{2(1+\epsilon/2)\log{2p}}\right\\}\right.$
$\displaystyle\hskip
50.00008pt\left.\cap\left\\{-\sqrt{2(1+\epsilon/2)\log{2p}}\leq
g_{1}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}+\frac{{\bm{\beta}}_{j^{*}}\cdot\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right\\}\;\middle|\;\Omega_{1}\right]+\mathbb{P}\left[\Omega^{\complement}_{1}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}<\sqrt{2(1+\epsilon/2)\log{2p}}-\left|\frac{{\bm{\beta}}_{j^{*}}\cdot\|{\bm{y}}\|_{2}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|\;\middle|\;\Omega_{1}\right]+\mathbb{P}\left[\Omega^{\complement}_{1}\right]$
$\displaystyle\leq\mathbb{P}\left[g_{1}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}<\sqrt{2(1+\epsilon/2)\log{2p}}-\left|\frac{{\bm{\beta}}_{j^{*}}\cdot\sqrt{n(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})(1-\delta)}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right|\;\middle|\;\Omega_{1}\right]+\mathbb{P}\left[\Omega^{\complement}_{1}\right]$
$\displaystyle=\mathbb{P}\left[g_{1}\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}<\sqrt{2(1+\epsilon/2)\log{2p}}-\left|{\bm{\beta}}_{j^{*}}\sqrt{\frac{n(1-\delta)}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}\right|\;\middle|\;\Omega_{1}\right]+\mathbb{P}\left[\Omega^{\complement}_{1}\right].$

Now setting
$n\geq\frac{8(1+\epsilon)}{{\bm{\beta}}^{2}_{\min}}(\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2})\log{2p}$
and applying standard sub-Gaussian bounds (see Wainwright (2019)) we obtain

$\displaystyle\nu$
$\displaystyle\leq\mathbb{P}\left[g\sqrt{1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}}<(\sqrt{2(1+\epsilon/2)}-\sqrt{8(1+\epsilon)(1-\delta)})\sqrt{\log{2p}}\right]+\mathbb{P}\left[\Omega_{1}^{\complement}\right]$
$\displaystyle\leq\exp\left(-\frac{(\sqrt{2(1+\epsilon/2)}-\sqrt{8(1+\epsilon)(1-\delta)})^{2}\log{2p}}{2\left(1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right)}\right)+2e^{-\frac{\delta^{2}n}{8}},$

where

$\displaystyle\sqrt{2(1+\epsilon/2)}-\sqrt{8(1+\epsilon)(1-\delta)}<-\sqrt{2}$
(28)

for $\delta>0$ small enough. Hence, choosing $\delta$ to satisfy (28) above,
we obtain that for $k$ large enough,

$\displaystyle\nu$
$\displaystyle\leq\exp\left(-\frac{2\log{2p}}{2\left(1-\frac{{\bm{\beta}}^{2}_{j^{*}}}{\|{\bm{\beta}}\|^{2}_{2}+\sigma^{2}}\right)}\right)+2e^{-\frac{\delta^{2}n}{8}}$
$\displaystyle\leq\exp\left(-\frac{2\log{2p}}{2}\right)+2e^{-\frac{\delta^{2}n}{8}}$
$\displaystyle\leq\frac{1}{2p}+2e^{-\frac{\delta^{2}n}{8}}.$

∎