$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\textup{GFT}_{2}(M_{f_{1},f_{2}},\textbf{U}|u_{1}=s_{i})-6\varepsilon$

where for $(a)$ we just removed $(2)$ because we are bounding from below and
increased to price to $f_{2}(\lceil v_{1}\rceil_{S})$ so we include $(3)$ and
$(4)$; and $(b),(c),(d)$ are for the same reasons as above.

Summing over all intervals $(s_{i-1},s_{i}]$ and taking the integral over
$V_{1}$, we get the desired bound for $\textup{GFT}_{2}$. Similar calculations
hold for getting the desired bound for $\textup{GFT}_{1}$. ∎

###### Proof of Lemma 7.2.

Immediate by Lemma C.4. ∎

Using the result of the lemma and the algorithm from the previous section, we
claim the following:

######  Lemma C.6.

Let $\textbf{V}=V_{s}\times V_{1}\times V_{2}$ be a product distribution over
$[0,1]^{3}$, let $S_{s},S_{1},S_{2}$ be $\varepsilon$-samples for
$V_{s},V_{1},V_{2}$, respectively. Let $\textbf{U}=U_{s}\times U_{1}\times
U_{2}$. Let $M_{U}^{*}$ be a GFT-optimal mechanism on U. For every simple
mechanism $M$:

$\displaystyle\textup{GFT}(M,\textbf{V})\leq\textup{GFT}(M_{U}^{*},\textbf{V})+24\varepsilon$

###### Proof.

Since $M$ and $M_{U}^{*}$ are simple, by Lemma 3.3 we know that each has a
pair of functions associated with it. Denote the associated pair of $M$ by
$(f_{1},f_{2})$ and the associated pair of $M_{U}^{*}$ by
$(f_{1}^{U},f_{2}^{U})$. Note that since $M_{U}^{*}$ is optimal then
$\textup{GFT}(M_{U}^{*},\textbf{V})=\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{V})$.
Then:

$\displaystyle\textup{GFT}(M,\textbf{V})-\textup{GFT}(M_{U}^{*},\textbf{V})\stackrel{{\scriptstyle(a)}}{{\leq}}\textup{GFT}(M_{f_{1},f_{2}},\textbf{V})-\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{V})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\textup{GFT}(M_{f_{1},f_{2}},\textbf{V})-\textup{GFT}(M_{f_{1},f_{2}},\textbf{U})$
$\displaystyle+\textup{GFT}(M_{f_{1},f_{2}},\textbf{U})-\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{U})$
$\displaystyle+\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{U})-\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{V})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\textup{GFT}(M_{f_{1},f_{2}},\textbf{V})-\textup{GFT}(M_{f_{1},f_{2}},\textbf{U})+\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{U})-\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{V})\stackrel{{\scriptstyle(d)}}{{\leq}}24\varepsilon$

where $(a)$ is by Lemma 3.6 and from the fact that
$\textup{GFT}(M_{U}^{*},\textbf{V})=\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{V})$,
$(b)$ we added and subtracted the same elements, $(c)$ is due to Theorem 3
that $\textup{GFT}(M_{f_{1},f_{2}},\textbf{U})$
$\leq\textup{GFT}(M_{f_{1}^{U},f_{2}^{U}},\textbf{U})$ because
$M_{f_{1}^{U},f_{2}^{U}}$ maximizes GFT on U, and $(d)$ is from using the
bound by Lemma 7.2 on $f_{1},f_{2}$ and $f_{1}^{U},f_{2}^{U}$. ∎

###### Proof of Theorem 4.

The algorithm first picks samples $S_{s},S_{1},S_{2}$, each of size
$O\left(\frac{1}{\varepsilon^{2}}\ln\frac{1}{\varepsilon\delta}\right)$ from
$V_{s},V_{1},V_{2}$, respectively. Let $M$ be a GFT-optimal mechanism for the
empirical distribution $\textbf{U}=U_{s}\times U_{1}\times U_{2}$ (computed in
poly-time using Theorem 3). By Theorem 6, with probability at least
$1-\delta$, the multisets $S_{s},S_{1},S_{2}$ are $\varepsilon$-samples of the
corresponding distributions. Thus, if $S_{s},S_{1},S_{2}$ are indeed
$\varepsilon$-samples then by Lemma C.6 the expected GFT of $M$ on V is at
most $24\varepsilon$ less than the expected GFT of any other mechanism on V –
specifically of $\textup{OPT}_{\textup{simple}}(\boldsymbol{V})$. ∎

## References

  * [Bab+18] Moshe Babaioff, Yang Cai, Yannai A. Gonczarowski and Mingfei Zhao  “The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade”  In _ACM Conference on Economics and Computation (ACM-EC)_ , 2018
  * [BD21] Liad Blumrosen and Shahar Dobzinski  “(Almost) efficient mechanisms for bilateral trading”  In _Games Econ. Behav._ 130, 2021, pp. 369–383
  * [BGG20] Moshe Babaioff, Kira Goldner and Yannai A. Gonczarowski  “Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets”  In _Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2020
  * [Bil95] P. Billingsley  “Probability and Measure”, Wiley Series in Probability and Statistics  Wiley, 1995  URL: https://books.google.co.il/books?id=z39jQgAACAAJ
  * [BNP09] Moshe Babaioff, Noam Nisan and Elan Pavlov  “Mechanisms for a Spatially Distributed Market”  In _Games and Economic Behavior (GEB)_ 66.2, 2009, pp. 660–684
  * [BSV16] Maria-Florina Balcan, Tuomas Sandholm and Ellen Vitercik  “Sample Complexity of Automated Mechanism Design”  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , NIPS’16, 2016, pp. 2091–2099
  * [Ces+21] Nicolò Cesa-Bianchi et al.  “Bilateral Trade: A Regret Minimization Perspective” Preliminary version in EC’21  In _arXiv http://arxiv.org/abs/2109.12974_ , 2021  arXiv:2109.12974 [cs.GT]
  * [Col+20] Riccardo Colini-Baldeschi et al.  “Approximately Efficient Two-Sided Combinatorial Auctions”  In _ACM Trans. Econ. Comput._ 8.1, 2020
  * [CR14] Richard Cole and Tim Roughgarden  “The Sample Complexity of Revenue Maximization”  In _Symposium on Theory of Computing (STOC)_ , 2014, pp. 243–252
  * [CW23] Yang Cai and Jinzhao Wu  “On the Optimal Fixed-Price Mechanism in Bilateral Trade”  In _Symposium on Theory of Computing (STOC)_ , 2023, pp. 737–750
  * [Den+22] Yuan Deng, Jieming Mao, Balasubramanian Sivan and Kangning Wang  “Approximately Efficient Bilateral Trade”  In _Symposium on Theory of Computing (STOC)_ , 2022, pp. 718–721
  * [DHP16] Nikhil R. Devanur, Zhiyi Huang and Christos-Alexandros Psomas  “The Sample Complexity of Auctions with Side Information”  In _Symposium on Theory of Computing (STOC)_ , 2016, pp. 426–439
  * [GHZ19] Chenghao Guo, Zhiyi Huang and Xinzhi Zhang  “Settling the Sample Complexity of Single-parameter Revenue Maximization”  In _Symposium on Theory of Computing (STOC)_ , 2019, pp. 662–673
  * [GW21] Yannai A. Gonczarowski and S. Weinberg  “The Sample Complexity of Up-to-$\varepsilon$ Multi-Dimensional Revenue Maximization”  In _J. ACM_ 68.3, 2021
  * [KPV22] Zi Yang Kang, Francisco Pernice and Jan Vondrák  “Fixed-Price Approximations in Bilateral Trade”  In _Symposium on Discrete Algorithms (SODA)_ , 2022, pp. 2964–2985
  * [McA92] R. McAfee  “A Dominant Strategy Double Auction”  In _Journal of Economic Theory_ 56.2 Elsevier, 1992, pp. 434–450
  * [MR16] Jamie Morgenstern and Tim Roughgarden  “Learning Simple Auctions”  In _Conference on Learning Theory_ , 2016, pp. 1298–1318  PMLR
  * [MS83] Roger B Myerson and Mark A Satterthwaite  “Efficient Mechanisms for Bilateral Trading”  In _Journal of Economic Theory_ 29.2, 1983, pp. 265–281
  * [MU17] Michael Mitzenmacher and Eli Upfal  “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis”  Cambridge University Press, 2017
  * [Mye81] Roger B Myerson  “Optimal Auction Design”  In _Mathematics of Operations Research_ 6.1 INFORMS, 1981, pp. 58–73
  * [Nis+07] “Algorithmic Game Theory”  Cambridge University Press, 2007  DOI: 10.1017/CBO9780511800481


then if $n-|\tau|>4$ and $\gamma_{2}<0.6$,

$\displaystyle\mathbb{P}_{\mathbf{U}}(\rho(\mathbf{U},\tau)\geq
1-\gamma_{2})=\mathbb{P}_{\mathbf{U}}(g_{\tau}(\mathbf{U})>\sqrt{\gamma_{2}})=\mathbb{P}_{\mathbf{U}}\left(\frac{\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{U}\|^{2}}{\|H_{\tau}\mathbf{U}\|^{2}}>\frac{\gamma_{2}}{1-\gamma_{2}}\right)$
$\displaystyle\quad=1-F_{n-|\tau|,|\tau|}\left(\frac{\gamma_{2}/(n-|\tau|)}{(1-\gamma_{2})/|\tau|}\right)\geq
1-\left(\frac{n-|\tau|}{2}\right)^{\frac{|\tau|}{2}}\gamma_{2}^{\frac{n-|\tau|}{2}-1}.$

The last inequality holds because when $n-|\tau|>4$ and $\gamma_{2}<0.6$,

$\displaystyle
F_{n-|\tau|,|\tau|}(\frac{\gamma_{2}/(n-|\tau|)}{(1-\gamma_{2})/|\tau|})$
$\displaystyle=\frac{{\int}_{0}^{\gamma_{2}}t^{\frac{n-|\tau|}{2}-1}(1-t)^{\frac{|\tau|}{2}-1}dt}{\mathcal{B}(\frac{n-|\tau|}{2},\frac{|\tau|}{2})}\leq\frac{\gamma_{2}^{\frac{n-|\tau|}{2}-1}}{\mathcal{B}(\frac{n-|\tau|}{2},\frac{|\tau|}{2})},$

where $\mathcal{B}(\frac{n-|\tau|}{2},\frac{|\tau|}{2})$ is the beta function
and

$\displaystyle\mathcal{B}(\frac{n-|\tau|}{2},\frac{|\tau|}{2})\geq\left(\frac{n-|\tau|}{2}\right)^{-\frac{|\tau|}{2}}.$

Therefore it follows from the above, Lemma 8 and Lemma 9 that

$\displaystyle\mathbb{P}\left(\mathbf{U}\not\in\left\\{\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U},\mathbf{X}_{0}\bm{\beta}_{0})<\tilde{\gamma}_{1}^{2},\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho(\mathbf{U},\tau)<1-\gamma_{2}\right\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U},\mathbf{X}_{0}\bm{\beta}_{0})\geq\tilde{\gamma}_{1}^{2}\right)+\mathbb{P}\left(\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho(\mathbf{U},\tau)\geq
1-\gamma_{2}\right)$
$\displaystyle\leq\sum_{|\tau|=1}^{|\tau_{0}|}\genfrac{(}{)}{0.0pt}{0}{p}{|\tau|}\Bigg{\\{}2(\arccos\tilde{\gamma}_{1})^{n-|\tau|-1}+\left(\frac{n-|\tau|}{2}\right)^{\frac{|\tau|}{2}}\gamma_{2}^{\frac{n-|\tau|}{2}-1}\Bigg{\\}}$
$\displaystyle\leq\sum_{|\tau|=1}^{|\tau_{0}|}p^{|\tau|}\Bigg{\\{}2(\arccos\tilde{\gamma}_{1})^{n-|\tau|-1}+\left(\frac{n-|\tau|}{2}\right)^{\frac{|\tau|}{2}}\gamma_{2}^{\frac{n-|\tau|}{2}-1}\Bigg{\\}}$
$\displaystyle\leq
2(\arccos\tilde{\gamma}_{1})^{n-|\tau_{0}|-1}p^{|\tau_{0}|}\sum_{k=0}^{|\tau_{0}|-1}\left(\frac{\arccos\tilde{\gamma}_{1}}{p}\right)^{k}+\gamma_{2}^{\frac{n-|\tau_{0}|}{2}-1}(\sqrt{n}p)^{|\tau_{0}|}\sum_{k=0}^{|\tau_{0}|-1}\left(\frac{\gamma_{2}}{np^{2}}\right)^{k/2}$
$\displaystyle\leq
4(\arccos\tilde{\gamma}_{1})^{n-|\tau_{0}|-1}p^{|\tau_{0}|}+2\gamma_{2}^{\frac{n-|\tau_{0}|}{2}-1}(\sqrt{n}p)^{|\tau_{0}|}.$

∎

###### Proof of Lemma 5.

For a fixed $\tau$, let

$D(\tau,\mathbf{u}^{*})=\min_{\bm{\beta}_{\tau},\sigma}\|\mathbf{Y}-\mathbf{X}_{\tau}\bm{\beta}_{\tau}-\sigma\mathbf{u}^{*}\|^{2}=\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{Y}\|^{2},$

where $\mathbf{Y}=\mathbf{X}_{0}\bm{\beta}_{0}+\sigma_{0}\mathbf{U}$ is a
random sample from the true model (2) with the error term $\mathbf{U}\sim
N(0,I_{n}),$ and $\mathbf{H}_{\tau,\mathbf{u}^{*}}$ is the projection matrix
for $(\mathbf{X}_{\tau},\mathbf{u}^{*}).$

Define

$\hat{\tau}_{\mathbf{u}^{*}}=\mathop{\rm
arg\,min\,}_{\\{\tau||\tau|\leq|\tau_{0}|\\}}D(\tau,\mathbf{u}^{*}).$

By (31) with constraint $|\tau|=\|\bm{\beta}_{\tau}\|_{0}\leq|\tau_{0}|$, if
there exists a $\tau$, $|\tau|\leq|\tau_{0}|$, such that
$\\{D(\tau,\mathbf{u}^{*})-D(\tau_{0},\mathbf{u}^{*})<0\\}$, then
$\\{\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0}\\}$. On the other hand, if
$\\{\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0}\\}$, then
$D(\hat{\tau}_{\mathbf{u}^{*}},\mathbf{u}^{*})-D(\tau_{0},\mathbf{u}^{*})<0$.
Thus,
$\bigcup_{\\{\tau||\tau|\leq|\tau_{0}|\\}}\\{D(\tau,\mathbf{u}^{*})-D(\tau_{0},\mathbf{u}^{*})<0\\}=\\{\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0}\\}$.

For each $\mathbf{Y}$,

$\displaystyle
D(\tau,\mathbf{u}^{*})-D(\tau_{0},\mathbf{u}^{*})=\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{Y}\|^{2}-\|(\mathbf{I}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})\mathbf{Y}\|^{2}$
$\displaystyle\qquad=\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})(\mathbf{X}_{0}\bm{\beta}_{0}+\sigma_{0}\mathbf{U})\|^{2}-\sigma_{0}^{2}\|(\mathbf{I}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})\mathbf{U}\|^{2}$
$\displaystyle\qquad=\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}-\sigma_{0}^{2}\mathbf{U}^{\top}(\mathbf{H}_{\tau,\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})\mathbf{U}.$
(38)

Now, define an event set

$\displaystyle
E(\gamma_{1},\gamma_{2})=\left\\{(\mathbf{u}^{*},\mathbf{u}):\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{u}^{*},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2},\rho(\mathbf{u}^{*},\mathbf{u})>1-\gamma_{2}^{2}\right\\},$
(39)

we have, for any $\delta\in(0,1)$,

$\displaystyle\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{D(\tau,\mathbf{U}^{*})-D(\tau_{0},\mathbf{U}^{*})<0,\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\right\\}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\bigg{\\{}(1-\gamma^{2}_{1})\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}-\sigma_{0}^{2}\mathbf{U}^{\top}(H_{\tau,\mathbf{U}^{*}}-H_{\tau_{0},\mathbf{U}^{*}})\mathbf{U}$
$\displaystyle\qquad+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}<0,\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\bigg{\\}}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\bigg{\\{}(1-\gamma^{2}_{1})(1-\delta)\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}$
$\displaystyle\qquad\qquad-\sigma_{0}^{2}\mathbf{U}^{\top}(\mathbf{H}_{\tau,\mathbf{U}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{U}^{*}})\mathbf{U}<0,\,(\mathbf{U},^{*}\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\bigg{\\{}(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}$
$\displaystyle\qquad\qquad+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}<0,\,(\mathbf{U},^{*}\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\bigg{\\}}$ $\displaystyle=(I_{1})+(I_{2}).$

To derive an upper bound for $(I_{1})$, we note that, by Lemma 7, for any
$(\mathbf{U},^{*}\mathbf{U})$ that satisfies
$\rho(\mathbf{U},^{*}\mathbf{U})>1-\gamma_{2}^{2},$

$\displaystyle\mathbf{U}^{\top}(\mathbf{H}_{\tau,\mathbf{U}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{U}^{*}})\mathbf{U}=\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau_{0},\mathbf{U}^{*}})\mathbf{U}-\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{U}^{*}})\mathbf{U}\leq\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau_{0},\mathbf{U}^{*}})\mathbf{U}$
$\displaystyle\qquad=\|(\mathbf{I}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{U}^{*}})\mathbf{U}\|^{2}=\|(\mathbf{I}-\mathbf{H}_{\tau_{0}})(\mathbf{I}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{U}^{*}})\mathbf{U}\|^{2}$
$\displaystyle\qquad\leq\|(\mathbf{I}-\mathbf{H}_{\tau_{0}})(\mathbf{I}-\mathbf{H}_{\mathbf{U}^{*}})\mathbf{U}\|^{2}\leq\|(\mathbf{I}-\mathbf{H}_{\mathbf{U}^{*}})\mathbf{U}\|^{2}\leq\gamma_{2}\|\mathbf{U}\|^{2},$

where $\mathbf{O}_{\tau_{0}^{\bot}\mathbf{U}^{*}}$ is the projection matrix of
$(\mathbf{I}-\mathbf{H}_{\tau_{0}})\mathbf{U}^{*}$ and the first inequality
follows from the definition of projection. It follows, from condition(C1),
that,

$\displaystyle(I_{1})$
$\displaystyle<\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{\|\mathbf{U}\|^{2}>\frac{(1-\gamma^{2}_{1})(1-\delta)}{\gamma^{2}_{2}}\frac{\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}}{\sigma_{0}^{2}},\,(\mathbf{U}^{*},\epsilon)\in
E(\gamma_{1},\gamma_{2})\right\\}$
$\displaystyle<\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{\|\mathbf{U}\|^{2}>\frac{(1-\gamma^{2}_{1})(1-\delta)}{\gamma^{2}_{2}}\frac{\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle=\mathbb{P}_{\chi^{2}_{n}}\left\\{\chi^{2}_{n}>\frac{(1-\gamma^{2}_{1})(1-\delta)}{\gamma^{2}_{2}}\frac{n|\tau_{0}\setminus\tau|C_{\min}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle<\exp\left\\{-\frac{n}{2}\log(1-2t_{1})-t_{1}\frac{(1-\gamma^{2}_{1})(1-\delta)}{\gamma^{2}_{2}}\frac{n|\tau_{0}\setminus\tau|C_{\min}}{\sigma_{0}^{2}}\right\\},$

for any $0<t_{1}<1/2$, where $\chi^{2}_{n}$ is a random variable that follows
$\chi^{2}_{n}$ distribution. The last inequality is derived from Markov
inequality and moment generating function of chi-square distribution.

For $(I_{2})$, we note that, for any $(\mathbf{U}^{*},\mathbf{U})$ such that
$\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2}$,
$\|(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}})\epsilon\|^{2}=\|(\mathbf{I}-\mathbf{H}_{\tau})(\mathbf{I}-\mathbf{O}_{\tau^{\bot}\mathbf{U}})\epsilon\|^{2}\leq\|(\mathbf{I}-\mathbf{H}_{\tau})(\mathbf{I}-\mathbf{H}_{\mathbf{U}^{*}})\mathbf{U}\|^{2}\leq\|(\mathbf{I}-\mathbf{H}_{\mathbf{U}^{*}})\mathbf{U}\|^{2}\leq\gamma_{2}^{2}\|\mathbf{U}\|^{2}.$

Thus, by Cauchy-Schwartz inequality,

$\displaystyle|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}|=|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}|$
$\displaystyle\qquad\leq\|(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{U}\|\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|\leq\gamma_{2}\|\mathbf{U}\|\,\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|.$

Therefore,

$\displaystyle(I_{2})$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}<2\sigma_{0}|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}|,$
$\displaystyle\qquad\qquad\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\big{\\}}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}<2\sigma_{0}\gamma_{2}\|\mathbf{U}\|\,\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|,$
$\displaystyle\qquad\qquad\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\big{\\}}$
$\displaystyle=\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{\|\mathbf{U}\|^{2}>\frac{(1-\gamma^{2}_{1})^{2}\delta^{2}}{4\gamma^{2}_{2}}\frac{\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}}{\sigma_{0}^{2}},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\right\\}$
$\displaystyle\leq\mathbb{P}_{\mathbf{U}}\left\\{\|\mathbf{U}\|^{2}>\frac{(1-\gamma^{2}_{1})^{2}\delta^{2}}{4\gamma^{2}_{2}}\frac{\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle=\mathbb{P}_{\chi_{n}^{2}}\left\\{\chi^{2}_{n}>\frac{(1-\gamma^{2}_{1})^{2}\delta^{2}}{4\gamma^{2}_{2}}\frac{n|\tau_{0}\setminus\tau|C_{\min}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle\leq\exp\left\\{-\frac{n}{2}\log(1-2t_{2})-t_{2}\frac{(1-\gamma^{2}_{1})^{2}\delta^{2}}{4\gamma^{2}_{2}}\frac{n|\tau_{0}\setminus\tau|C_{\min}}{\sigma_{0}^{2}}\right\\},$

for any $0<t_{2}<1/2.$

Now, by making of
$(1-\gamma^{2}_{1})(1-\delta)=(1-\gamma^{2}_{1})^{2}\delta^{2}/4$, we obtain
$\delta=\frac{2}{1-\gamma^{2}_{1}}(\sqrt{2-\gamma_{1}^{2}}-1)$. Further we
make $t_{1}=t_{2}=\frac{\gamma_{2}}{2.04}$, so we have
$-\frac{n}{2}\log(1-2t_{1})=-\frac{n}{2}\log(1-2t_{2})=-\frac{n}{2}\log(1-\frac{\gamma_{2}}{1.02})\leq
2n\gamma_{2}$. Then, intersect with the event
$\\{(\mathbf{U}^{*},\mathbf{U})\in E(\gamma_{1},\gamma_{2})\\}$, we have

$\displaystyle\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\big{\\}}$
$\displaystyle\qquad<\sum_{i=1}^{|\tau_{0}|}\sum_{j=0}^{i}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\exp\left\\{-\left(\sqrt{2-\gamma_{1}^{2}}-1\right)^{2}\frac{niC_{\min}}{2.04\gamma_{2}\sigma_{0}^{2}}+2n\gamma_{2}\right\\}$
$\displaystyle\qquad<\sum_{i=1}^{|\tau_{0}|}\sum_{j=0}^{i}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\exp\left\\{-\frac{niC_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}+2n\gamma_{2}\right\\}.$

The last inequality holds since $(\sqrt{2-\gamma_{1}^{2}}-1)^{2}\geq
1.02(1-\gamma_{1}^{2})^{2}/6$ for $\gamma_{1}^{2}\in(0,1)$. Since
$\genfrac{(}{)}{0.0pt}{0}{a}{b}\leq a^{b}$ and
$\log(p-|\tau_{0}|)+\log(|\tau_{0}|)\leq\log(p^{2}/4)=2\log(p/2)$, it follows

$\displaystyle\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\\{\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\\}$
$\displaystyle\qquad\leq\sum_{i=1}^{|\tau_{0}|}|\tau_{0}|^{i}\exp\left\\{-\frac{niC_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}+2n\gamma_{2}\right\\}\sum_{j=0}^{i}(p-|\tau_{0}|)^{j}$
$\displaystyle\qquad<2\sum_{i=1}^{|\tau_{0}|}\exp\left\\{-n\left[i\frac{C_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}-i\frac{2\log(p/2)}{n}-2\gamma_{2}\right]\right\\}$
$\displaystyle\qquad<\frac{2\exp\left\\{-n\left[\frac{C_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}-\frac{2\log(p/2)}{n}-2\gamma_{2}\right]\right\\}}{1-\exp\left\\{-n\left[\frac{C_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}-\frac{2\log(p/2)}{n}-2\gamma_{2}\right]\right\\}}$
$\displaystyle\qquad<3\exp\left\\{-\frac{n}{12\sigma_{0}^{2}}\left[\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}C_{\min}-24\left(\frac{\log(p/2)}{n}+\gamma_{2}\right)\sigma_{0}^{2}\right]\right\\}=L_{c}(\gamma_{1},\gamma_{2}),$
(40)

since
$\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}C_{\min}-24\left(\frac{\log(p/2)}{n}+\gamma_{2}\right)\sigma_{0}^{2}>0.$
The last inequality holds because

$\displaystyle\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\\{\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\\}$
$\displaystyle\qquad\leq[2+\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\\{\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\\}]$ $\displaystyle\hskip
56.9055pt\exp\left\\{-n\left[\frac{C_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}-\frac{2\log(p/2)}{n}-2\gamma_{2}\right]\right\\}$
$\displaystyle\qquad\leq
3\exp\left\\{-n\left[\frac{C_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}-\frac{2\log(p/2)}{n}-2\gamma_{2}\right]\right\\}.$

It then follows from Lemma 9 and Lemma 10 that

$\displaystyle\mathbb{P}(\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2})$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\\{\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\\}+\mathbb{P}\left(\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U},\mathbf{X}_{0}\bm{\beta}_{0})\geq\tilde{\gamma}_{1}^{2}\right)$
$\displaystyle\hskip
113.81102pt+\mathbb{P}\left(\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho(\mathbf{U},\tau)\geq
1-\gamma_{2}\right)$ $\displaystyle\leq
3\exp\left\\{-n\left[\frac{C_{\min}}{12\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}-\frac{2\log(p/2)}{n}-2\gamma_{2}\right]\right\\}+4(\arccos\tilde{\gamma}_{1})^{n-|\tau_{0}|-1}p^{|\tau_{0}|}$
$\displaystyle\hskip
113.81102pt+2\gamma_{2}^{\frac{n-|\tau_{0}|}{2}-1}(\sqrt{n}p)^{|\tau_{0}|}.$

We then make $\gamma_{1}=\sqrt{1-\gamma_{2}^{1/4}},$ from which we have
$\tilde{\gamma}_{1}=(1-\sqrt{\gamma_{2}})\sqrt{1-\gamma_{2}^{1/4}}-\sqrt{2-2\sqrt{1-\gamma^{2}_{2}}}\geq
1-1.6\gamma_{2}^{1/3}>0$ for $\gamma_{2}\in[0,0.24].$ Therefore
$\arccos\tilde{\gamma}_{1}\leq\arccos(1-1.6\gamma_{2}^{1/3})\leq
2\gamma_{2}^{1/6}<1.$ Hence the above probability bound reduces to

$\displaystyle\mathbb{P}(\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2})$
$\displaystyle\leq
3\exp\left\\{-n\left[\frac{C_{\min}}{12\sigma_{0}^{2}\sqrt{\gamma}_{2}}-\frac{2\log(p/2)}{n}-2\gamma_{2}\right]\right\\}+4(64\gamma_{2})^{\frac{n-|\tau_{0}|-1}{6}}p^{|\tau_{0}|}$
$\displaystyle\hskip
113.81102pt+2\gamma_{2}^{\frac{n-|\tau_{0}|}{2}-1}(\sqrt{n}p)^{|\tau_{0}|}.$

∎

###### Proof of Lemma 2.

By Lemma 7, we let
$D(\tau,\mathbf{u}^{*})=\frac{1}{2}\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{Y}\|^{2}+\lambda|\tau|=\frac{1}{2}\|(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{u}^{*}})\mathbf{Y}\|^{2}+\lambda|\tau|$
for any $\tau\neq\tau_{0},$ then

$\displaystyle D(\tau,\mathbf{u}^{*})-D(\tau_{0},\mathbf{u}^{*})$
$\displaystyle=\|(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}})\mathbf{Y}\|^{2}-\|(\mathbf{I}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{u}^{*}})\mathbf{Y}\|^{2}+\lambda(|\tau|-|\tau_{0}|)$
$\displaystyle=\|(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}-\mathbf{U}^{\top}(\mathbf{H}_{\tau}+\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{u}^{*}})\mathbf{U}$
$\displaystyle\quad+2\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}+2\lambda(|\tau|-|\tau_{0}|).$
(41)

Let $E(\gamma_{1},\gamma_{2})$ be the event defined in (39), then

$\displaystyle\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{D(\tau,\mathbf{U}^{*})-D(\tau_{0},\mathbf{U}^{*})<0,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\right\\}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}(1-\gamma^{2}_{1})\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}-\sigma_{0}^{2}\mathbf{U}^{\top}(\mathbf{H}_{\tau}+\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{U}^{*}})\mathbf{U}$
$\displaystyle\qquad+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}+2\lambda(|\tau|-|\tau_{0}|)<0,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\big{\\}}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}(1-\gamma^{2}_{1})(1-\delta)\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}$
$\displaystyle\qquad{}-\sigma_{0}^{2}\mathbf{U}^{\top}(\mathbf{H}_{\tau}+\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{U}^{*}})\mathbf{U}+\lambda(|\tau|-|\tau_{0}|)<0\big{\\}}$
$\displaystyle\quad+\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}$
$\displaystyle\qquad{}+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}+\lambda(|\tau|-|\tau_{0}|))<0\big{\\}}$
$\displaystyle=(I_{1})+(I_{2}),$

for any $\delta\in(0,1).$

To derive an upper bound for $I_{1}$, we have

$\displaystyle\|(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{U}\|^{2}=\|(\mathbf{I}-\mathbf{H}_{\tau})(\mathbf{I}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{U}\|^{2}$
$\displaystyle\leq\|(\mathbf{I}-\mathbf{H}_{\tau})(\mathbf{I}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{U}\|^{2}\leq\|(\mathbf{I}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{U}\|^{2}\leq\gamma_{2}^{2}\|\mathbf{U}\|^{2}.$

First,

$\displaystyle\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}$
$\displaystyle=\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}$
$\displaystyle\leq\|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\|\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|.$

Then

$\displaystyle\mathbf{U}^{\top}(\mathbf{H}_{\tau}+\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{U}^{*}})\mathbf{U}\leq
2\gamma_{2}\|\mathbf{U}\|^{2}.$

Because

$\displaystyle\|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-O_{\tau^{\bot}\mathbf{U}^{*}})\|^{2}<\gamma^{2}_{2}\|\mathbf{U}\|^{2},$

it then follows if $|\tau|\leq|\tau_{0}|$ and
$\frac{\lambda}{n}<\frac{1}{6}\min\left\\{(1-\gamma_{1}^{2})C_{\min},\frac{\sqrt{(1-\gamma_{1}^{2})C_{\min}}}{|\tau_{0}|}\right\\},$

$\displaystyle(I_{1})$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{\|\mathbf{U}\|^{2}>\frac{(1-\gamma^{2}_{1})(1-\delta)}{\gamma^{2}_{2}}\frac{\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}}{\sigma_{0}^{2}}+\frac{\lambda(|\tau|-|\tau_{0}|)}{\gamma_{2}^{2}\sigma_{0}^{2}}\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\chi^{2}_{n}>\frac{(1-\gamma^{2}_{1})(1-\delta-1/6)}{\gamma^{2}_{2}}\frac{niC_{\min}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle\leq\exp\left\\{-\frac{n}{2}\log(1-2t_{1})-t_{1}\frac{(1-\gamma^{2}_{1})(1-\delta-1/6)}{\gamma^{2}_{2}}\frac{niC_{\min}}{\sigma_{0}^{2}}\right\\},$

for any $0<t_{1}<1/2.$ Otherwise when $|\tau|>|\tau_{0}|,$ we would have

$\displaystyle(I_{1})\leq\exp\left\\{-\frac{n}{2}\log(1-2t_{1})-t_{1}\frac{\lambda(|\tau|-|\tau_{0}|)}{\gamma_{2}^{2}\sigma_{0}^{2}}\right\\}.$

The above inequalities are derived from Markov inequality and moment
generating function of chi-square distribution. For $(I_{2})$, if
$\frac{\lambda}{n}<\frac{1}{6}\min\left\\{(1-\gamma_{1}^{2})C_{\min},\frac{\sqrt{(1-\gamma_{1}^{2})C_{\min}}}{|\tau_{0}|}\right\\},$
by Cauchy-Schwartz inequality when $|\tau|\leq|\tau_{0}|$ we have

$\displaystyle(I_{2})$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}<2\sigma_{0}\|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\|\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|$
$\displaystyle\qquad\qquad\qquad{}\hskip
227.62204pt-\lambda(|\tau|-|\tau_{0}|)\big{\\}}$
$\displaystyle=\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}2\sigma_{0}\|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\|>(1-\gamma_{1}^{2})(\delta-1/6)\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|$
$\displaystyle\qquad\qquad\qquad{}\hskip
227.62204pt+\lambda(|\tau|-|\tau_{0}|)\big{\\}}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{\|\mathbf{U}\|^{2}>\frac{(1-\gamma^{2}_{1})^{2}(\delta-1/6)^{2}}{4\gamma^{2}_{2}}\frac{\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\chi^{2}_{n}>\frac{(1-\gamma^{2}_{1})^{2}(\delta-1/6)^{2}}{4\gamma^{2}_{2}}\frac{niC_{\min}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle\leq\exp\left\\{-\frac{n}{2}\log(1-2t_{2})-t_{2}\frac{(1-\gamma^{2}_{1})^{2}(\delta-1/6)^{2}}{4\gamma^{2}_{2}}\frac{niC_{\min}}{\sigma_{0}^{2}}\right\\},$

for any $0<t_{2}<1/2.$

When $|\tau|>|\tau_{0}|$, from the fact that
$(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}+2\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}\geq-\frac{\|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\|^{2}}{(1-\gamma_{1}^{2})\delta},$
we have

$\displaystyle(I_{2})$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{\|\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{U}^{*}})\|^{2}>(1-\gamma_{1}^{2})\delta\lambda(|\tau|-|\tau_{0}|)\right\\}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\left\\{\|\mathbf{U}\|^{2}/\sigma_{0}^{2}>\frac{(1-\gamma_{1}^{2})\delta\lambda(|\tau|-|\tau_{0}|)}{\gamma_{2}^{2}\sigma_{0}^{2}}\right\\}$
$\displaystyle\leq\exp\left\\{-\frac{n}{2}\log(1-2t_{2})-t_{2}\frac{(1-\gamma_{1}^{2})\delta\lambda(|\tau|-|\tau_{0}|)}{\gamma_{2}^{2}\sigma_{0}^{2}}\right\\}.$

Now, by making of
$(1-\gamma^{2}_{1})(1-\delta-1/6)=(1-\gamma^{2}_{1})^{2}(\delta-1/6)^{2}/4$,
we obtain
$\delta=\frac{2}{1-\gamma^{2}_{1}}(\sqrt{\frac{5}{3}-\frac{2}{3}\gamma_{1}^{2}}-1)+\frac{1}{6}$.
Further we make $t_{1}=t_{2}=\frac{\gamma_{2}}{2.04}$, so we have
$-\frac{n}{2}\log(1-2t_{1})=-\frac{n}{2}\log(1-2t_{2})=-\frac{n}{2}\log(1-\frac{\gamma_{2}}{1.02})\leq
2n\gamma_{2}$. Then, intersect with the event
$\\{(\mathbf{U}^{*},\mathbf{U})\in E(\gamma_{1},\gamma_{2})\\}$, we have

$\displaystyle\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\big{\\{}\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\big{\\}}$ $\displaystyle\qquad\leq
2\sum_{i=1}^{|\tau_{0}|}\sum_{j=0}^{i}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\exp\left\\{-\left(\sqrt{\frac{5}{3}-\frac{2}{3}\gamma_{1}^{2}}-1\right)^{2}\frac{niC_{\min}}{2.04\gamma_{2}\sigma_{0}^{2}}+2n\gamma_{2}\right\\}$
$\displaystyle+2\sum_{i=0}^{|\tau_{0}|}\sum_{j=i+1}^{p}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\exp\left\\{-\frac{(\sqrt{\frac{5}{3}-\frac{2}{3}\gamma_{1}^{2}}-1)\lambda(j-i)}{1.02\gamma_{2}\sigma_{0}^{2}}+2\gamma_{2}n\right\\}$
$\displaystyle\qquad\leq
2\sum_{i=1}^{|\tau_{0}|}\sum_{j=0}^{i}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\exp\left\\{-\frac{niC_{\min}}{26\sigma_{0}^{2}}\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}+2n\gamma_{2}\right\\}$
$\displaystyle+2\sum_{i=0}^{|\tau_{0}|}\sum_{j=i+1}^{p}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\exp\left\\{-\frac{(1-\gamma_{1}^{2})\lambda(j-i)}{4\gamma_{2}\sigma_{0}^{2}}+2\gamma_{2}n\right\\}.$

The last inequality holds since
$(\sqrt{\frac{5}{3}-\frac{2}{3}\gamma_{1}^{2}}-1)^{2}\geq
1.02(1-\gamma_{1}^{2})^{2}/13$ for $\gamma_{1}^{2}\in(0,1)$.

By similar calculation to that in (B.2), the first part of the above can be
bounded by

$\displaystyle
L_{p}(\gamma_{1},\gamma_{2})=3\exp\left\\{-\frac{n}{26\sigma_{0}^{2}}\left[\frac{\left(1-\gamma_{1}^{2}\right)^{2}}{\gamma_{2}}C_{\min}-52\left(\frac{\log(p/2)}{n}+\gamma_{2}\right)\sigma_{0}^{2}\right]\right\\}.$

As for the second part,

$\displaystyle
2\sum_{i=0}^{|\tau_{0}|}\sum_{j=i+1}^{p}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\exp\left\\{-\frac{(1-\gamma_{1}^{2})\lambda(j-i)}{4\gamma_{2}\sigma_{0}^{2}}+2\gamma_{2}n\right\\}$
$\displaystyle\leq
2\sum_{i=0}^{|\tau_{0}|}|\tau_{0}|^{i}\exp\left\\{\gamma_{2}n+\frac{(1-\gamma_{1}^{2})\lambda
i}{4\gamma_{2}\sigma_{0}^{2}}\right\\}\sum_{j=i+1}^{p}\exp\left[-j\left\\{\frac{(1-\gamma_{1}^{2})\lambda}{4\gamma_{2}\sigma_{0}^{2}}-\log(p-|\tau_{0}|)\right\\}\right]$
$\displaystyle\leq\frac{2\sum_{i=0}^{|\tau_{0}|}\exp\left[-\frac{(1-\gamma_{1}^{2})\lambda}{4\gamma_{2}\sigma_{0}^{2}}+\gamma_{2}n+\log(p-|\tau_{0}|)+i\\{\log(|\tau_{0}|)+\log(p-|\tau_{0}|)\\}\right]}{1-\exp\left\\{\frac{(1-\gamma_{1}^{2})\lambda}{4\gamma_{2}\sigma_{0}^{2}}-\log(p-|\tau_{0}|)\right\\}}$
$\displaystyle\leq\frac{2\exp\left[-\frac{(1-\gamma_{1}^{2})\lambda}{4\gamma_{2}\sigma_{0}^{2}}+\gamma_{2}n+(|\tau_{0}|+1)\\{\log|\tau_{0}|+\log(p-|\tau_{0}|\\}\right]}{1-\exp\left\\{\frac{(1-\gamma_{1}^{2})\lambda}{4\gamma_{2}\sigma_{0}^{2}}-\log(p-|\tau_{0}|)\right\\}}$
$\displaystyle\leq
3\exp\left(-\frac{1-\gamma_{1}^{2}}{4\gamma_{2}\sigma_{0}^{2}}nt\right),$

if
$\frac{\lambda}{n}\in\left[\frac{\lambda^{(1)}_{0}}{n}+t,\frac{1}{6}\min\left\\{(1-\gamma_{1}^{2})C_{\min},\frac{\sqrt{(1-\gamma_{1}^{2})C_{\min}}}{|\tau_{0}|}\right\\}\right),$
where

$\lambda^{(1)}_{0}=\frac{4\gamma_{2}\sigma_{0}^{2}}{1-\gamma_{1}^{2}}\left[\gamma_{2}n+(|\tau_{0}|+1)\\{\log|\tau_{0}|+\log(p-|\tau_{0}|\\}\right].$

It then follows from Lemma 9 and Lemma 10 that

$\displaystyle\mathbb{P}(\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2})$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}^{*},\mathbf{U})}\\{\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\,(\mathbf{U}^{*},\mathbf{U})\in
E(\gamma_{1},\gamma_{2})\\}+\mathbb{P}\left(\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\epsilon,\mathbf{X}_{0}\bm{\beta}_{0})\geq\tilde{\gamma}_{1}^{2}\right)$
$\displaystyle\hskip
113.81102pt+\mathbb{P}\left(\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho(\epsilon,\tau)\geq
1-\gamma_{2}\right)$ $\displaystyle\leq
L_{p}(\gamma_{1},\gamma_{2})+3\exp\left(-\frac{1-\gamma_{1}^{2}}{4\gamma_{2}\sigma_{0}^{2}}nt\right)+4(\arccos\tilde{\gamma}_{1})^{n-|\tau_{0}|-1}p^{|\tau_{0}|}$
$\displaystyle\hskip
113.81102pt+2\gamma_{2}^{\frac{n-|\tau_{0}|}{2}-1}(\sqrt{n}p)^{|\tau_{0}|}.$

We then make $\gamma_{1}=\sqrt{1-\gamma_{2}^{1/4}},$ from which we have
$\tilde{\gamma}_{1}=(1-\sqrt{\gamma_{2}})\sqrt{1-\gamma_{2}^{1/4}}-\sqrt{2-2\sqrt{1-\gamma^{2}_{2}}}\geq
1-1.6\gamma_{2}^{1/3}>0$ for $\gamma_{2}\in[0,0.24].$ Therefore
$\arccos\tilde{\gamma}_{1}\leq\arccos(1-1.6\gamma_{2}^{1/3})\leq
2\gamma_{2}^{1/6}<1.$ In addition, we make $t=\sqrt{\gamma_{2}}.$ Hence the
above probability bound reduces to

$\displaystyle\mathbb{P}(\hat{\tau}_{\mathbf{u}}\neq\tau_{0},\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2})$
$\displaystyle\leq
3\exp\left\\{-\frac{n}{26\sigma_{0}^{2}}\left[\frac{C_{\min}}{\sqrt{\gamma_{2}}}-52\left(\frac{\log(p/2)}{n}+\gamma_{2}\right)\sigma_{0}^{2}\right]\right\\}+3\exp\left(-\frac{1}{4\gamma_{2}^{3/4}\sigma_{0}^{2}}nt\right)$
$\displaystyle\hskip
113.81102pt+4(64\gamma_{2})^{\frac{n-|\tau_{0}|-1}{6}}p^{|\tau_{0}|}+2\gamma_{2}^{\frac{n-|\tau_{0}|}{2}-1}(\sqrt{n}p)^{|\tau_{0}|}$
$\displaystyle\leq
3\exp\left\\{-\frac{n}{26\sigma_{0}^{2}}\left[\frac{C_{\min}}{\sqrt{\gamma_{2}}}-52\left(\frac{\log(p/2)}{n}+\gamma_{2}\right)\sigma_{0}^{2}\right]\right\\}+3\exp\left(-\frac{n}{4\gamma_{2}^{1/4}\sigma_{0}^{2}}\right)$
$\displaystyle\hskip
113.81102pt+4(64\gamma_{2})^{\frac{n-|\tau_{0}|-1}{6}}p^{|\tau_{0}|}+2\gamma_{2}^{\frac{n-|\tau_{0}|}{2}-1}(\sqrt{n}p)^{|\tau_{0}|},$

where $\gamma_{2}<1/64$ since $\gamma_{2}^{1/4}<0.35.$

Moreover it follows from the fact $\log|\tau_{0}|+\log(p-|\tau_{0}|)\leq
2\log(p/2)$ that when
$\gamma^{1/4}_{2}<\frac{C_{\min}}{|\tau_{0}|^{2}}\wedge\frac{C_{\min}}{24\\{2+2(|\tau_{0}|+1)\log(p/2)/n\\}}$
and $t=\sqrt{\gamma_{2}},$

$\displaystyle\frac{\lambda_{0}^{(1)}}{n}+t$ $\displaystyle\leq
4\gamma_{2}^{1/2}\left\\{\gamma_{2}+1+2\gamma_{2}^{1/4}(|\tau_{0}|+1)\frac{\log(p/2)}{n}\right\\}$
$\displaystyle<4\gamma_{2}^{1/2}\left\\{2+2(|\tau_{0}|+1)\frac{\log(p/2)}{n}\right\\}$
$\displaystyle<\frac{1}{6}\gamma_{2}^{1/4}C_{\min}\leq\frac{\gamma_{2}^{1/4}\sqrt{C_{\min}}}{6|\tau_{0}|}.$

The result in Lemma 2 then follows immediately. ∎

###  B.3 Proof of Lemma 3 and Lemma 6

######  Lemma 11.

Suppose $\mathbf{U}^{*}_{1},\ldots,\mathbf{U}^{*}_{d}$ are $d$ i.i.d. copies
of $\mathbf{U}^{*}\sim N(0,\mathbf{I}),$ then

$\displaystyle\mathbb{P}\left(\bigcap_{b=1}^{d}\\{\rho(\mathbf{U}^{*}_{b},\mathbf{U})\leq
1-\gamma_{2}^{2}\\}\right)\leq\left(1-\frac{\gamma_{2}^{n-1}}{n-1}\right)^{d}.$

###### Proof of Lemma 11.

By (37), $\rho(\mathbf{U}_{b}^{*},\mathbf{U})$ and $\mathbf{U}$ are
independent. It then follows from Lemma 8 and the fact
$\arcsin(\gamma_{2})>\gamma_{2}$ that

$\displaystyle\mathbb{P}\left(\bigcap_{b=1}^{d}\\{\rho(\mathbf{U}_{b}^{*},\mathbf{U})\leq
1-\gamma_{2}^{2}\\}\right)$
$\displaystyle=E\left\\{\mathbb{P}\left(\bigcap_{b=1}^{d}\\{\rho(\mathbf{U}_{b}^{*},\mathbf{U})\leq
1-\gamma_{2}^{2}\\}\middle|\mathbf{U}\right)\right\\}$
$\displaystyle=E\left\\{\left(1-\mathbb{P}(\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2}|\mathbf{U})\right)^{d}\right\\}$
$\displaystyle=\left(1-\mathbb{P}(\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2})\right)^{d}$
$\displaystyle\leq\left(1-\frac{\gamma_{2}^{n-2}\arcsin(\gamma_{2})}{n-1}\right)^{d}\leq\left(1-\frac{\gamma_{2}^{n-1}}{n-1}\right)^{d}.$

∎

###### Proof of Lemma 6.

We can decompose the probability $\tau_{0}\notin S^{(d)}$ into

$\displaystyle\mathbb{P}(\tau_{0}\notin S^{(d)})$
$\displaystyle=\mathbb{P}\left(\tau_{0}\notin
S^{(d)},\bigcup_{b=1}^{d}\\{\rho(\mathbf{U}_{b}^{*},\mathbf{U})>1-\gamma_{2}^{2}\\}\right)+\mathbb{P}\left(\tau_{0}\notin
S^{(d)},\bigcap_{b=1}^{d}\\{\rho(\mathbf{U}_{b}^{*},\mathbf{U})\leq
1-\gamma_{2}^{2}\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\hat{\tau}_{\mathbf{U}_{b}^{*}}\neq\tau_{0},\rho(\mathbf{U}_{b}^{*},\mathbf{U})>1-\gamma_{2}^{2}\mbox{
for some
}b\right)+\mathbb{P}\left(\bigcap_{b=1}^{d}\\{\rho(\mathbf{U}_{b}^{*},\mathbf{U})\leq
1-\gamma_{2}^{2}\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0},\rho(\mathbf{U}^{*},\mathbf{U})>1-\gamma_{2}^{2}\right)+\mathbb{P}\left(\bigcap_{b=1}^{d}\\{\rho(\mathbf{U}_{b}^{*},\mathbf{U})\leq
1-\gamma_{2}^{2}\\}\right).$ (42)

Then the probability bound in (6) follows immediately from Lemma 5 and Lemma
11. ∎

###### Proof of Lemma 3.

By (B.3), the probability bound in (3) follows immediately from Lemma 2 and
Lemma 11. ∎

###  B.4 Proof of Theorem 9 and Lemma 4

In order to prove Theorem 9, we first present a technical lemma, which is a
counterpart of Lemma 4. We will first prove Lemma 12, and follow the similar
strategy to prove Lemma 4.

######  Lemma 12.

Under the constraint $|\tau|\leq|\tau_{0}|$, the finite probability bound that
the true model is not covered by the model candidate set $S^{(d)}$, obtained
by Algorithm 1 with the objective function (31), is as follows,

$\displaystyle\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}(\tau_{0}\notin
S^{(d)})\leq
L(\gamma_{1})+\left[2\\{\arccos(\gamma_{1})\\}^{n-|\tau_{0}|-1}p^{|\tau_{0}|}\right]^{d}$
(43)

where

$\displaystyle
L(\gamma_{1})=6\exp\left[-\frac{n}{18\sigma_{0}^{2}}\left\\{(1-\gamma_{1}^{2})C_{\min}-36\frac{\log
p}{n}\sigma_{0}^{2}\right\\}\right],$

and $\cos(0.3\pi)<\gamma_{1}<1$ is any real number.

###### Proof of Lemma 12.

By (B.2), for any $\delta\in(0,1)$ an any $\mathbf{u}^{*}$ such that

$\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{u}^{*},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2},$

we have

$\displaystyle\mathbb{P}_{\mathbf{U}}\left\\{D(\tau,\mathbf{u}^{*})-D(\tau_{0},\mathbf{u}^{*})<0\right\\}$
$\displaystyle\leq\mathbb{P}_{\mathbf{U}}\bigg{\\{}(1-\gamma^{2}_{1})\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}-\sigma_{0}^{2}\mathbf{U}^{\top}(\mathbf{H}_{\tau,\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})\mathbf{U}$
$\displaystyle\quad\quad\hskip
85.35826pt+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}<0\bigg{\\}}$
$\displaystyle\leq\mathbb{P}_{\mathbf{U}}\bigg{\\{}(1-\gamma^{2}_{1})(1-\delta)\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}-\sigma_{0}^{2}\mathbf{U}^{\top}(\mathbf{H}_{\tau,\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})\mathbf{U}<0\bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}_{\mathbf{U}}\bigg{\\{}(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}<0\bigg{\\}}$
$\displaystyle=(I_{1})+(I_{2}).$

By Lemma 4 of [44], we bound the log of the moment generating function $M(t)$
of
$\mathbf{U}^{\top}(\mathbf{H}_{\tau,\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})\mathbf{U}$

$\displaystyle\log\\{M(t)\\}$
$\displaystyle=\sum_{r=1}^{\infty}\frac{2^{r-1}t^{r}}{r}\mathop{\rm
tr}\\{(\mathbf{H}_{\tau,\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})^{r}\\}$
$\displaystyle\leq t(|\tau|-|\tau_{0}|)+\frac{t^{2}}{1-2t}\mathop{\rm
tr}\\{(\mathbf{H}_{\tau,\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0},\mathbf{u}^{*}})^{2}\\}\leq
2t|\tau\setminus\tau_{0}|\leq 2t|\tau_{0}\setminus\tau|,$ (44)

for any $0<t<1/2.$ Therefore by Markov Inequality

$\displaystyle(I_{1})\leq\exp\left\\{2t_{1}|\tau\setminus\tau_{0}|-\frac{t_{1}(1-\delta)(1-\gamma^{2}_{1})n|\tau_{0}\setminus\tau|C_{\min}}{\sigma_{0}^{2}}\right\\},$

for any $0<t_{1}<1/2.$ Further because
$2\sigma_{0}\epsilon^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}$
follows
$N(0,\sigma^{2}_{0}\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2})$,
then by Markov inequality and moment generating function of the normal
distribution , we have

$\displaystyle(I_{2})\leq\exp\left\\{\frac{(2t_{2}^{2}-\delta
t_{2})(1-\gamma_{1}^{2})n|\tau_{0}\setminus\tau|C_{\min}}{\sigma_{0}^{2}}\right\\}$

for any $0<t_{2}<1/2.$ It then follows that

$\displaystyle\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0})$
$\displaystyle\leq\sum_{i=0}^{|\tau_{0}|}\sum_{j=0}^{i}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\Bigg{[}\exp\left\\{2t_{1}j-\frac{t_{1}(1-\delta)(1-\gamma^{2}_{1})niC_{\min}}{\sigma_{0}^{2}}\right\\}$
$\displaystyle\qquad\qquad+\exp\left\\{\frac{(2t_{2}^{2}-\delta
t_{2})(1-\gamma_{1}^{2})niC_{\min}}{\sigma_{0}^{2}}\right\\}\Bigg{]}.$

We can make $t_{1}=t_{2}=1/3$, $\delta=5/6,$ therefore
$t_{1}(1-\delta)=-(2t_{2}^{2}-\delta t_{2})=1/18.$ Then by the fact that
$\genfrac{(}{)}{0.0pt}{0}{a}{b}\leq a^{b}$, the probability bound above can be
simplified as

$\displaystyle\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0})\leq
2\sum_{i=0}^{|\tau_{0}|}\sum_{j=0}^{i}(p-|\tau_{0}|)^{j}|\tau_{0}|^{i}\exp\left\\{-\frac{(1-\gamma_{1}^{2})nC_{\min}}{18\sigma_{0}^{2}}i+\frac{2}{3}j\right\\}$
$\displaystyle=2\sum_{i=0}^{|\tau_{0}|}\exp\left[-i\left\\{\frac{(1-\gamma_{1}^{2})nC_{\min}}{18\sigma_{0}^{2}}-\log|\tau_{0}|\right\\}\right]\sum_{j=0}^{i}\exp\left[j\left\\{\frac{2}{3}+\log(p-|\tau_{0}|)\right\\}\right].$

Then we have

$\displaystyle\sum_{j=0}^{i}\exp\left[j\left\\{\frac{2}{3}+\log(p-|\tau_{0}|)\right\\}\right]\leq\frac{\exp\left[(i+1)\left\\{\frac{2}{3}+\log(p-|\tau_{0}|)\right\\}\right]}{\exp\left\\{\frac{2}{3}+\log(p-|\tau_{0}|)\right\\}-1}$
$\displaystyle\leq\frac{\exp\left[i\left\\{\frac{2}{3}+\log(p-|\tau_{0}|)\right\\}\right]}{1-e^{-2/3}}.$

It then follows from $\log(p-|\tau_{0}|)+\log(|\tau_{0}|)\leq 2\log p-1$ that

$\displaystyle\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0})\leq\frac{2}{1-e^{-2/3}}\sum_{i=1}^{|\tau_{0}|}\exp\left[-i\left\\{\frac{(1-\gamma_{1}^{2})nC_{\min}}{18\sigma_{0}^{2}}-2\log
p\right\\}\right]$
$\displaystyle\qquad\leq\frac{2}{1-e^{-2/3}}\frac{\exp\left[-\frac{n}{18\sigma_{0}^{2}}\left\\{(1-\gamma_{1}^{2})C_{\min}-36\frac{\log
p}{n}\sigma_{0}^{2}\right\\}\right]}{1-\exp\left[-\frac{n}{18\sigma_{0}^{2}}\left\\{(1-\gamma_{1}^{2})C_{\min}-36\frac{\log
p}{n}\sigma_{0}^{2}\right\\}\right]}.$

It then follows that for any

$\mathbf{u}^{*}\in\left\\{\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{u}^{*},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\},$

we have the probability bound

$\displaystyle\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0})$
$\displaystyle\leq\left\\{\frac{2}{1-e^{-2/3}}+\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0})\right\\}\exp\left[-\frac{n}{18\sigma_{0}^{2}}\left\\{(1-\gamma_{1}^{2})C_{\min}-36\frac{\log
p}{n}\sigma_{0}^{2}\right\\}\right]$
$\displaystyle\leq\frac{3-e^{-2/3}}{1-e^{-2/3}}\exp\left[-\frac{n}{18\sigma_{0}^{2}}\left\\{(1-\gamma_{1}^{2})C_{\min}-36\frac{\log
p}{n}\sigma_{0}^{2}\right\\}\right]$ $\displaystyle\leq
6\exp\left[-\frac{n}{18\sigma_{0}^{2}}\left\\{(1-\gamma_{1}^{2})C_{\min}-36\frac{\log
p}{n}\sigma_{0}^{2}\right\\}\right]=L(\gamma_{1}).$ (45)

By Lemma 8

$\displaystyle\mathbb{P}_{\mathbf{U}^{*}}\left\\{\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad\leq\sum_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\mathbb{P}_{\mathbf{U}^{*}}\left\\{\rho_{\tau^{\bot}}(\mathbf{U}^{*},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad\leq\sum_{\\{\tau:|\tau|\leq|\tau_{0}|\\}}2\\{\arccos(\gamma_{1})\\}^{n-|\tau|-1}=\sum_{k=1}^{|\tau_{0}|}\genfrac{(}{)}{0.0pt}{0}{p}{k}2\\{\arccos(\gamma_{1})\\}^{n-k-1}$
$\displaystyle\qquad\leq
2\\{\arccos(\gamma_{1})\\}^{n-|\tau_{0}|-1}p^{|\tau_{0}|}.$ (46)

Then let $i_{\min}=\mathop{\rm arg}\min_{1\leq i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0}),$
we have

$\displaystyle\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}(\tau_{0}\notin
S^{(d)})\leq\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}\left\\{\tau_{0}\notin
S^{(d)},\min_{1\leq i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\mathbb{P}_{({\cal
U}^{d},\mathbf{Y})}\left\\{\tau_{0}\notin S^{(d)},\min_{1\leq i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq\mathbb{P}_{({\cal
U}^{d},\mathbf{Y})}\left\\{\hat{\tau}_{\mathbf{U}^{*}_{i_{\min}}}\neq\tau_{0},\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i_{\min}},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}\left\\{\min_{1\leq
i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}|{\cal
U}^{d})}\left\\{\hat{\tau}_{\mathbf{U}^{*}_{i_{\min}}}\neq\tau_{0}\middle|\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i_{\min}},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\hskip 142.26378pt\mathbb{P}_{{\cal
U}^{d}}\left\\{\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i_{\min}},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}\left\\{\min_{1\leq
i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq\max\left\\{P_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0}):\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{u}^{*},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\prod^{d}_{i=1}\mathbb{P}_{\mathbf{U}^{*}_{i}}\left\\{\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq
L(\gamma_{1})+\left[2\\{\arccos(\gamma_{1})\\}^{n-|\tau_{0}|-1}p^{|\tau_{0}|}\right]^{d}.$

∎

###### Proof of Lemma 4.

By Lemma 7, we let
$D(\tau,\mathbf{u}^{*})=\frac{1}{2}\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{Y}\|^{2}+\lambda|\tau|=\frac{1}{2}\|(\mathbf{I}-\mathbf{H}_{\tau}-O_{\tau_{0}^{\bot}\mathbf{u}})\mathbf{y}\|^{2}+\lambda|\tau|$
for any $\tau\neq\tau_{0}.$ Then By (B.2), for any $\delta\in(0,1)$ an any
$\mathbf{u}^{*}$ such that

$\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{u}^{*},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2},$

we have

$\displaystyle\mathbb{P}_{\mathbf{U}}\\{D(\tau,\mathbf{u}^{*})-D(\tau_{0},\mathbf{u}^{*})<0\\}$
$\displaystyle\leq\mathbb{P}_{\mathbf{U}}\\{(1-\gamma^{2}_{1})\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}-\sigma_{0}^{2}\mathbf{U}^{\top}(H_{\tau}+\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{u}^{*}})\mathbf{U}$
$\displaystyle\hskip
142.26378pt+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}+2\lambda(|\tau|-|\tau_{0}|)<0\\}$
$\displaystyle\leq\mathbb{P}_{\mathbf{U}}\\{(1-\gamma^{2}_{1})(1-\delta)\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}-\sigma_{0}^{2}\mathbf{U}^{\top}(H_{\tau}+\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}}-\mathbf{H}_{\tau_{0}}-\mathbf{O}_{\tau_{0}^{\bot}\mathbf{u}^{*}})\mathbf{U}$
$\displaystyle\hskip 142.26378pt+\lambda(|\tau|-|\tau_{0}|)<0\\}$
$\displaystyle\quad+\mathbb{P}_{\mathbf{U}}\\{(1-\gamma^{2}_{1})\delta\|(\mathbf{I}-\mathbf{H}_{\tau})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2}+2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau}-\mathbf{O}_{\tau^{\bot}\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}$
$\displaystyle\hskip 142.26378pt+\lambda(|\tau|-|\tau_{0}|))<0\\}$
$\displaystyle=(I_{1})+(I_{2}).$

Then it follows from (B.4) and Markov Inequality

$\displaystyle(I_{1})\leq\exp\left\\{2t_{1}|\tau\setminus\tau_{0}|-\frac{t_{1}(1-\delta)(1-\gamma^{2}_{1})n|\tau_{0}\setminus\tau|C_{\min}+t_{1}\lambda(|\tau|-|\tau_{0}|)}{\sigma_{0}^{2}}\right\\},$

for any $0<t_{1}<1/2.$ Further because
$2\sigma_{0}\mathbf{U}^{\top}(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{u}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}$
follows
$N(0,\sigma^{2}_{0}\|(\mathbf{I}-\mathbf{H}_{\tau,\mathbf{U}^{*}})\mathbf{X}_{0}\bm{\beta}_{0}\|^{2})$,
then by Markov inequality and moment generating function of the normal
distribution , we

$\displaystyle(I_{2})\leq\exp\left\\{\frac{(2t_{2}^{2}-\delta
t_{2})(1-\gamma_{1}^{2})n|\tau_{0}\setminus\tau|C_{\min}+t_{2}\lambda(|\tau|-|\tau_{0}|)}{\sigma_{0}^{2}}\right\\}$

for any $0<t_{2}<1/2.$ It then follows that

$\displaystyle\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0})$
$\displaystyle\leq\sum_{i=1}^{|\tau_{0}|}\sum_{j=0}^{i}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\Bigg{[}\exp\bigg{\\{}\frac{(2t^{2}_{1}-\delta
t_{1})(1-\gamma_{1}^{2})niC_{\min}+t_{1}\lambda(i-j)}{\sigma_{0}^{2}}\bigg{\\}}$
$\displaystyle\quad\quad\quad+\exp\bigg{\\{}\frac{-(1-\delta)t_{2}(1-\gamma^{2}_{1})niC_{\min}+t_{2}\lambda(i-j)}{\sigma_{0}^{2}}+2t_{2}j\bigg{\\}}\Bigg{]}$
$\displaystyle+\sum_{i=0}^{|\tau_{0}|}\sum_{j=i+1}^{p}\genfrac{(}{)}{0.0pt}{0}{|\tau_{0}|}{i}\genfrac{(}{)}{0.0pt}{0}{p-|\tau_{0}|}{j}\left[\exp\left\\{\frac{t_{1}\lambda(i-j)}{\sigma_{0}^{2}}\right\\}+\exp\left\\{\frac{t_{2}\lambda(i-j)}{\sigma_{0}^{2}}+2t_{2}j\right\\}\right].$

We can make $\delta=1/2,t_{1}=t_{2}=1/3,$ then by (B.4), if

$\frac{\lambda}{n}\in\left[\frac{3\sigma_{0}^{2}(|\tau_{0}|+1)\\{\log(p-|\tau_{0}|)+\log(|\tau_{0}|)+\frac{2}{3}\\}}{n}+t,\frac{(1-\gamma_{1}^{2})C_{\min}}{6},\right]$

we have

$\displaystyle\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{u}^{*}}\neq\tau_{0})$
$\displaystyle\leq
2\sum_{i=1}^{|\tau_{0}|}\sum_{j=0}^{i}(p-|\tau_{0}|)^{j}|\tau_{0}|^{i}\exp\left\\{-\frac{(1-\gamma_{1}^{2})niC_{\min}}{18\sigma_{0}^{2}}+\frac{\lambda(i-j)}{3\sigma_{0}^{2}}+\frac{2}{3}j\right\\}$
$\displaystyle\quad\quad\quad+2\sum_{i=0}^{|\tau_{0}|}\sum_{j=i+1}^{p}(p-|\tau_{0}|)^{j}|\tau_{0}|^{i}\exp\left\\{-\frac{\lambda(j-i)}{3\sigma_{0}^{2}}+\frac{2}{3}j\right\\}$
$\displaystyle\leq
L(\gamma_{1})+2\frac{\sum_{i=0}^{|\tau_{0}|}\exp\left[-\frac{\lambda}{3\sigma_{0}^{2}}+\log(p-|\tau_{0}|)+\frac{2}{3}+i\left\\{\log(|\tau_{0}|)+\log(p-|\tau_{0}|)+\frac{2}{3}\right\\}\right]}{1-\exp\left\\{-\frac{\lambda}{3\sigma_{0}^{2}}+\frac{2}{3}+\log(p-|\tau_{0}|)\right\\}}$
$\displaystyle\leq
L(\gamma_{1})+2\frac{\exp\left[-\frac{\lambda}{3\sigma_{0}^{2}}+(|\tau_{0}|+1)\\{\log(p-|\tau_{0}|)+\log(|\tau_{0}|)+\frac{2}{3}\\}\right]}{1-\exp\left\\{-\frac{\lambda}{3\sigma_{0}^{2}}+\frac{2}{3}+\log(p-|\tau_{0}|)\right\\}}$
$\displaystyle\leq
L(\gamma_{1})+3\exp\left(-\frac{nt}{3\sigma_{0}^{2}}\right).$

Then let $i_{\min}=\mathop{\rm arg}\min_{1\leq i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0}),$
by (B.4) we have

$\displaystyle\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}(\tau_{0}\notin
S^{(d)})\leq\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}\left\\{\tau_{0}\notin
S^{(d)},\min_{1\leq i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\mathbb{P}_{({\cal
U}^{d},\mathbf{Y})}\left\\{\tau_{0}\notin S^{(d)},\min_{1\leq i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq\mathbb{P}_{({\cal
U}^{d},\mathbf{Y})}\left\\{\hat{\tau}_{\mathbf{U}^{*}_{i_{\min}}}\neq\tau_{0},\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i_{\min}},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}\left\\{\min_{1\leq
i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq\mathbb{P}_{(\mathbf{U}|{\cal
U}^{d})}\left\\{\hat{\tau}_{\mathbf{U}^{*}_{i_{\min}}}\neq\tau_{0}\middle|\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i_{\min}},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\hskip 142.26378pt\mathbb{P}_{{\cal
U}^{d}}\left\\{\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i_{\min}},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\mathbb{P}_{({\cal U}^{d},\mathbf{Y})}\left\\{\min_{1\leq
i\leq
d}\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq\max\left\\{\mathbb{P}_{\mathbf{U}}(\hat{\tau}_{\mathbf{U}^{*}}\neq\tau_{0}):\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{u},\mathbf{X}_{0}\bm{\beta}_{0})<\gamma_{1}^{2}\right\\}$
$\displaystyle\qquad+\prod^{d}_{i=1}\mathbb{P}_{\mathbf{U}^{*}_{i}}\left\\{\max_{\tau\neq\tau_{0},|\tau|\leq|\tau_{0}|}\rho_{\tau^{\bot}}(\mathbf{U}^{*}_{i},\mathbf{X}_{0}\bm{\beta}_{0})\geq\gamma_{1}^{2}\right\\}$
$\displaystyle\leq
L(\gamma_{1})+3\exp\left(-\frac{nt}{3\sigma_{0}^{2}}\right)+\left[2\\{\arccos(\gamma_{1})\\}^{n-|\tau_{0}|-1}p^{|\tau_{0}|}\right]^{d}.$

∎

###### Proof of Theorem 9.

By Lemma 12, we make $\gamma^{2}_{1}=0.7$, then the probability bound (9)
follows from (43). ∎

###  B.5 Proof of Remark 2

By Theorem 4 and Theorem 6, we have
$\mathbb{P}\left\\{\tau_{0}\in{\bar{\Gamma}}^{\tau}_{\alpha_{1}}(\mathbf{Y})\right\\}\geq\alpha_{1}-\delta-o(e^{-c_{1}d})$
and
$\mathbb{P}\\{\bm{\beta}_{0,\Lambda}\in\Gamma^{\bm{\beta}_{\Lambda}}_{\alpha_{2}}(\mathbf{Y})\\}\geq\alpha-\delta-o(e^{-c_{1}d})$,
respectively, as $d\rightarrow\infty$ for some $c_{1}>0$. Here,
${\bar{\Gamma}}^{\tau}_{\alpha_{1}}(\mathbf{Y})$ is defined in (17) and
$\Gamma^{\bm{\beta}_{\Lambda}}_{\alpha_{2}}(\mathbf{Y})\\}$ is defined in
(3.1) but using $\alpha_{1}$ and $\alpha_{2}$, respectively, instead. Since
$\big{\\{}\tilde{T}(\mathbf{y}_{obs},\bm{\eta}_{\Lambda})\in
B_{\alpha_{2}}({\bm{\eta}_{\Lambda}}),\bm{\eta}_{\Lambda}=(\bm{\beta}_{\Lambda},\tau),\tau\in{\bar{\Gamma}}_{\alpha_{1}}^{\tau}(\mathbf{y}_{obs})\big{\\}}\supseteq\big{\\{}\tilde{T}(\mathbf{y}_{obs},\bm{\eta}_{\Lambda})\in
B_{\alpha_{2}}({\bm{\eta}_{\Lambda}}),\bm{\eta}_{\Lambda}=(\bm{\beta}_{\Lambda},\tau),\tau\in
S^{(d)}\big{\\}}\setminus\\{\tau\not\in{\bar{\Gamma}}_{\alpha_{1}}^{\tau}(\mathbf{y}_{obs})\\}$,
we have
$\mathbb{P}\\{\bm{\beta}_{0,\Lambda}\in{\Gamma}^{\bm{\beta}_{\Lambda},mod}_{\alpha}(\mathbf{Y}_{obs})\\}\geq\alpha_{2}-(1-\alpha_{1})-2\delta-o(e^{-c_{1}d})=\alpha-2\delta-o(e^{-c_{1}d})$.
This inequality ensures that the set
${\Gamma}^{\bm{\beta}_{\Lambda},mod}_{\alpha}(\mathbf{Y}_{obs})$ has a finite-
sample coverage for $\bm{\beta}_{0,\Lambda}$ with a finite number of sample
size $n$ and an increased number of repro samples. We can similarly prove its
asymptotic coverage (as the sample size $n\to\infty$ but with a limited number
of repro samples simulations) using Theorem 5 and Theorem 7.

## References

  * [1] [author] Athey, SusanS., Imbens, Guido W.G. W. and Wager (2018). Approximate Residual Balancing: De-Biased Inference of Average Treatment Effects in High Dimensions. arXiv:1604.07125 [econ, math, stat].
  * [2] [author] Barber, Rina FoygelR. F. and Candès, Emmanuel J.E. J. (2015). Controlling the False Discovery Rate via Knockoffs. The Annals of Statistics 43 2055–2085. 10.1214/15-AOS1337
  * [3] [author] Beaumont, Mark A.M. A., Zhang, WenyangW. and Balding, David J.D. J. (2002). Approximate Bayesian Computation in Population Genetics. Genetics 162 2025–2035.
  * [4] [author] Belloni, AlexandreA., Chernozhukov, VictorV., Chetverikov, DenisD., Hansen, ChristianC. and Kato, KengoK. (2018). High-dimensional econometrics and regularized GMM. arXiv preprint arXiv:1806.01888.
  * [5] [author] Belloni, AlexandreA., Chernozhukov, VictorV., Fernández-Val, IvanI. and Hansen, ChristianC. (2017). Program Evaluation and Causal Inference with High-Dimensional Data. Econometrica 85 233–298.
  * [6] [author] Bühlmann, PeterP. and Van De Geer, SaraS. (2011). Statistics for High-dimensional Data: Methods, Theory and Applications. Springer Science & Business Media.
  * [7] [author] Cai, TianxiT., Cai, TonyT. and Guo, ZijianZ. (2019). Individualized Treatment Selection: An Optimal Hypothesis Testing Approach In High-dimensional Models. arXiv:1904.12891 [math, stat].
  * [8] [author] Cai, TonyT. and Guo, ZijianZ. (2020). Semisupervised Inference for Explained Variance in High Dimensional Linear Regression and Its Applications. Journal of the Royal Statistical Society: Series B (Statistical Methodology).
  * [9] [author] Cai, T. TonyT. T. and Guo, ZijianZ. (2017). Confidence Intervals for High-Dimensional Linear Regression: Minimax Rates and Adaptivity. The Annals of statistics 45 615–646.
  * [10] [author] Cai, T. TonyT. T. and Guo, ZijianZ. (2018). Accuracy Assessment for High-Dimensional Linear Regression. The Annals of Statistics 46 1807–1836.
  * [11] [author] Candès, EmmanuelE., Fan, YingyingY., Janson, LucasL. and Lv, JinchiJ. (2018). Panning for Gold: ‘Model-X’ Knockoffs for High Dimensional Controlled Variable Selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 80 551–577. 10.1111/rssb.12265
  * [12] [author] Candes, EmmanuelE. and Tao, TerenceT. (2007). The Dantzig selector: Statistical estimation when p is much larger than n. The annals of Statistics 35 2313–2351.
  * [13] [author] Chatterjee, A.A. and Lahiri, S. N.S. N. (2011). Bootstrapping Lasso Estimators. Journal of the American Statistical Association 106 608–625. 10.1198/jasa.2011.tm10159
  * [14] [author] Chen, JiahuaJ. and Chen, ZehuaZ. (2008). Extended Bayesian Information Criteria for Model Selection with Large Model Spaces. Biometrika 95 759–771.
  * [15] [author] Chen, Scott ShaobingS. S., Donoho, David LD. L. and Saunders, Michael AM. A. (2001). Atomic decomposition by basis pursuit. SIAM review 43 129–159.
  * [16] [author] Chernozhukov, VictorV., Chetverikov, DenisD., Demirer, MertM., Duflo, EstherE., Hansen, ChristianC. and Newey, WhitneyW. (2017). Double/Debiased/Neyman Machine Learning of Treatment Effects. American Economic Review 107 261–65.
  * [17] [author] Chernozhukov, VictorV., Chetverikov, DenisD., Demirer, MertM., Duflo, EstherE., Hansen, ChristianC., Newey, WhitneyW. and Robins, JamesJ. (2018). Double/Debiased Machine Learning for Treatment and Structural Parameters. Oxford University Press Oxford, UK.
  * [18] [author] Chernozhukov, VictorV., Chetverikov, DenisD. and Kato, KengoK. (2017). Central Limit Theorems and Bootstrap in High Dimensions. The Annals of Probability 45 2309–2352.
  * [19] [author] Chernozhukov, VictorV., Hansen, ChristianC. and Spindler, MartinM. (2015). Post-Selection and Post-Regularization Inference in Linear Models with Many Controls and Instruments. American Economic Review 105 486–90.
  * [20] [author] Dezeure, RubenR., Bühlmann, PeterP., Meier, LukasL. and Meinshausen, NicolaiN. (2015). High-Dimensional Inference: Confidence Intervals, $p$-Values and R-Software Hdi. Statistical Science 30 533–558. 10.1214/15-STS527
  * [21] [author] Dezeure, RubenR., Bühlmann, PeterP. and Zhang, Cun-HuiC.-H. (2017). High-Dimensional Simultaneous Inference with the Bootstrap. TEST 26 685–719. 10.1007/s11749-017-0554-2
  * [22] [author] Efron, BradleyB. (1992). Bootstrap Methods: Another Look at the Jackknife. In Breakthroughs in Statistics 569–593. Springer.
  * [23] [author] Fan, JianqingJ. and Li, RunzeR. (2001). Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties. Journal of the American Statistical Association 96 1348–1360. 10.1198/016214501753382273
  * [24] [author] Fan, JianqingJ. and Lv, JinchiJ. (2008). Sure Independence Screening for Ultrahigh Dimensional Feature Space. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 70 849–911. 10.1111/j.1467-9868.2008.00674.x
  * [25] [author] Fan, JianqingJ. and Lv, JinchiJ. (2018). Sure independence screening. Wiley StatsRef: Statistics Reference Online.
  * [26] [author] Ferrari, DavideD. and Yang, YuhongY. (2015). Confidence Sets for Model Selection by F-testing. Statistica Sinica 1637–1658.
  * [27] [author] Freedman, D. A.D. A. (1981). Bootstrapping Regression Models. The Annals of Statistics 9 1218–1228. 10.1214/aos/1176345638
  * [28] [author] Guo, ZijianZ., Renaux, ClaudeC., Bühlmann, PeterP. and Cai, T. TonyT. T. (2020). Group Inference in High Dimensions with Applications to Hierarchical Testing. arXiv:1909.01503 [stat].
  * [29] [author] Guo, ZijianZ., Wang, WanjieW., Cai, T. TonyT. T. and Li, HongzheH. (2019). Optimal Estimation of Genetic Relatedness in High-Dimensional Linear Models. Journal of the American Statistical Association 114 358–369.
  * [30] [author] Hannig, JanJ., Iyer, HariH., Lai, Randy C. S.R. C. S. and Lee, Thomas C. M.T. C. M. (2016). Generalized Fiducial Inference: A Review and New Results. Journal of the American Statistical Association 111 1346–1361. 10.1080/01621459.2016.1165102
  * [31] [author] Hansen, Peter R.P. R., Lunde, AsgerA. and Nason, James M.J. M. (2011). The Model Confidence Set. Econometrica 79 453–497. 10.3982/ECTA5771
  * [32] [author] Hilafu, HaileabH. and Safo, Sandra ES. E. (2022). Sparse sliced inverse regression for high dimensional data analysis. BMC bioinformatics 23 1–19.
  * [33] [author] Janson, LucasL., Barber, Rina FoygelR. F. and Candès, EmmanuelE. (2016). EigenPrism: Inference for High-Dimensional Signal-to-Noise Ratios. arXiv:1505.02097 [stat].
  * [34] [author] Javanmard, AdelA. and Lee, Jason D.J. D. (2019). A Flexible Framework for Hypothesis Testing in High-dimensions. arXiv:1704.07971 [cs, math, stat].
  * [35] [author] Javanmard, AdelA. and Montanari, AndreaA. (2014). Confidence Intervals and Hypothesis Testing for High-Dimensional Regression. The Journal of Machine Learning Research 15 2869–2909.
  * [36] [author] Korobilis, DimitrisD. (2021). High-dimensional macroeconomic forecasting using message passing algorithms. Journal of Business & Economic Statistics 39 493–504.
  * [37] [author] Liu, WeidongW. (2013). Gaussian graphical model estimation with false discovery rate control. The Annals of Statistics 41 2948–2978.
  * [38] [author] Lv, ShaogaoS., You, MengyingM., Lin, HuazhenH., Lian, HengH. and Huang, JianJ. (2018). On the Sign Consistency of the Lasso for the High-dimensional Cox Model. Journal of Multivariate Analysis 167 79–96.
  * [39] [author] Martin, RyanR. and Liu, ChuanhaiC. (2015). Inferential Models: Reasoning with Uncertainty. Chapman & Hall/CRC.
  * [40] [author] Meinshausen, NicolaiN., Meier, LukasL. and Bühlmann, PeterP. (2009). P-Values for High-Dimensional Regression. Journal of the American Statistical Association 104 1671–1681.
  * [41] [author] Mitra, RitwikR. and Zhang, Cun-HuiC.-H. (2016). The Benefit of Group Sparsity in Group Inference with De-Biased Scaled Group Lasso. Electronic Journal of Statistics 10 1829–1873.
  * [42] [author] Nickl, RichardR. and Van De Geer, SaraS. (2013). Confidence Sets in Sparse Regression. The Annals of Statistics 41 2852–2876.
  * [43] [author] Shen, XiaotongX., Pan, WeiW. and Zhu, YunzhangY. (2012). Likelihood-Based Selection and Sharp Parameter Estimation. Journal of the American Statistical Association 107 223–232. 10.1080/01621459.2011.645783
  * [44] [author] Shen, XiaotongX., Pan, WeiW., Zhu, YunzhangY. and Zhou, HuiH. (2013). On Constrained and Regularized High-Dimensional Regression. Annals of the Institute of Statistical Mathematics 65 807–832. 10.1007/s10463-012-0396-3
  * [45] [author] Taylor, JonathanJ. and Tibshirani, Robert JR. J. (2015). Statistical learning and selective inference. Proceedings of the National Academy of Sciences 112 7629–7634.
  * [46] [author] Tibshirani, RobertR. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological) 58 267–288.
  * [47] [author] Tibshirani, Ryan JR. J., Taylor, JonathanJ., Lockhart, RichardR. and Tibshirani, RobertR. (2016). Exact post-selection inference for sequential regression procedures. Journal of the American Statistical Association 111 600–620.
  * [48] [author] Van de Geer, SaraS., Bühlmann, PeterP., Ritov, Ya’acovY. and Dezeure, RubenR. (2014). On Asymptotically Optimal Confidence Regions and Tests for High-Dimensional Models. The Annals of Statistics 42 1166–1202.
  * [49] [author] Van de Geer, SaraS. and Stucky, BenjaminB. (2016). $\chi$ 2-Confidence Sets in High-Dimensional Regression. In Statistical Analysis for High-Dimensional Data 279–306. Springer.
  * [50] [author] Verzelen, NicolasN. and Gassiat, ElisabethE. (2018). Adaptive Estimation of High-Dimensional Signal-to-Noise Ratios. Bernoulli 24 3683–3710.
  * [51] [author] Wang, HaohanH., Lengerich, Benjamin JB. J., Aragam, BryonB. and Xing, Eric PE. P. (2019). Precision Lasso: accounting for correlations and linear dependencies in high-dimensional genomic data. Bioinformatics 35 1181–1187.
  * [52] [author] Wang, XianghuiX., Benesty, JacobJ., Chen, JingdongJ. and Cohen, IsraelI. (2020). Beamforming with small-spacing microphone arrays using constrained/generalized LASSO. IEEE Signal Processing Letters 27 356–360.
  * [53] [author] Xie, Min-geM.-g. and Wang, PengP. (2022). Repro Samples Method for Finite- and Large-Sample Inferences. arXiv e-prints arXiv.2206.06421. 10.48550/arXiv.2206.06421
  * [54] [author] Zhang, Cun-HuiC.-H. (2010). Nearly Unbiased Variable Selection under Minimax Concave Penalty. The Annals of statistics 38 894–942.
  * [55] [author] Zhang, Cun-HuiC.-H. and Zhang, Stephanie S.S. S. (2014). Confidence Intervals for Low Dimensional Parameters in High Dimensional Linear Models. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 76 217–242. 10.1111/rssb.12026
  * [56] [author] Zhang, XianyangX. and Cheng, GuangG. (2017). Simultaneous Inference for High-Dimensional Linear Models. Journal of the American Statistical Association 112 757–768. 10.1080/01621459.2016.1166114
  * [57] [author] Zhang, YouweiY., d’Aspremont, AlexandreA. and Ghaoui, Laurent ElL. E. (2012). Sparse PCA: Convex Relaxations, Algorithms and Applications. In Handbook on Semidefinite, Conic and Polynomial Optimization, (Miguel F.M. F. Anjos and Jean B.J. B. Lasserre, eds.). International Series in Operations Research & Management Science 166 915–940. Springer US. 10.1007/978-1-4614-0769-0_31
  * [58] [author] Zhao, PengP. and Yu, BinB. (2006). On model selection consistency of Lasso. The Journal of Machine Learning Research 7 2541–2563.
  * [59] [author] Zhou, KunK., Li, Ker-ChauK.-C. and Zhou, QingQ. (2019). Honest Confidence Sets for High-Dimensional Regression by Projection and Shrinkage. arXiv preprint arXiv:1902.00535.
  * [60] [author] Zhu, YinchuY. and Bradic, JelenaJ. (2017). A Projection Pursuit Framework for Testing General High-Dimensional Hypothesis. arXiv:1705.01024 [math, stat].
  * [61] [author] Zhu, YinchuY. and Bradic, JelenaJ. (2018). Linear Hypothesis Testing in Dense High-Dimensional Linear Models. Journal of the American Statistical Association 113 1583–1600.
  * [62] [author] Zhu, YunzhangY., Shen, XiaotongX. and Pan, WeiW. (2020). On High-Dimensional Constrained Maximum Likelihood Inference. Journal of the American Statistical Association 115 217–230.
  * [63] [author] Zou, HuiH. (2006). The Adaptive Lasso and Its Oracle Properties. Journal of the American Statistical Association 101 1418–1429. 10.1198/016214506000000735
  * [64] [author] Zou, HuiH. and Hastie, TrevorT. (2005). Regularization and variable selection via the elastic net. Journal of the royal statistical society: series B (statistical methodology) 67 301–320.