$\displaystyle\leq\frac{\left|\tau_{1}^{2}-{\tau^{\star}_{1}}^{2}\right|}{\eta}+2\tau_{\max}^{\star}L_{\tau}\sum_{s=1}^{[t/2]}\frac{\left|{\lambda_{s}}-{\lambda_{s+1}}\right|}{\eta^{s}}+2\tau_{\max}^{\star}L_{\tau}\sum_{s=1+[t/2]}^{t}\frac{\left|{\lambda_{s}}-{\lambda_{s+1}}\right|}{\eta^{s}}$
$\displaystyle\leq\frac{\left|\tau_{1}^{2}-{\tau^{\star}_{1}}^{2}\right|}{\eta}+2\tau_{\max}^{\star}L_{\tau}\frac{1}{\eta^{[t/2]}}\sum_{s=1}^{[t/2]}[\lambda_{s}-\lambda_{s+1}]+2\tau_{\max}^{\star}L_{\tau}\frac{[\lambda_{[t/2]}-\lambda_{[t/2]+1}]}{1-\eta}\eta^{-t}$
$\displaystyle\leq\frac{\left|\tau_{1}^{2}-{\tau^{\star}_{1}}^{2}\right|}{\eta}+2\tau_{\max}^{\star}L_{\tau}\lambda_{1}\frac{1}{\eta^{[t/2]}}+2\tau_{\max}^{\star}L_{\tau}\frac{[\lambda_{[t/2]}-\lambda_{[t/2]+1}]}{1-\eta}\eta^{-t}.$

Re-arranging the above expression, we are left with

$\displaystyle\left|\tau_{t}^{2}-{\tau^{\star}_{t}}^{2}\right|\leq\frac{\left|\tau_{1}^{2}-{\tau^{\star}_{1}}^{2}\right|}{\eta}\eta^{t}+2\tau_{\max}^{\star}L_{\tau}\lambda_{1}\eta^{[t/2]}+\frac{2\tau_{\max}^{\star}L_{\tau}}{1-\eta}[\lambda_{[t/2]}-\lambda_{[t/2]+1}]\rightarrow
0,\quad t\rightarrow\infty.$

This completes the proof of Proposition B.3.

##  Appendix C Proofs about the AMP updates

The goal of this section is to prove Theorem 3. In Section C.1, we state a key
lemma (cf. Lemma C.1), which characterizes the convergence of the AMP updates
(as $t\rightarrow\infty$) to the minimum $\ell_{1}$-norm interpolator
$\widehat{\bm{\theta}}^{\mathsf{Int}}$. The proof of Theorem 3 is then built
upon this lemma. Section C.2 is then devoted to the main proof of Lemma C.1
with auxiliary lemmas established in Section C.3 and Section C.4.

The main structure of the proof is similar to that of Bayati and Montanari,
2011b ; in the following text, we often refer to the paper as BM for
simplification. The major difference between the min $\ell_{1}$ scenario and a
fixed $\lambda$ scenario (considered in Bayati and Montanari, 2011b  and other
references) lies in the lack of restricted strong convexity around the
solution point, which prevents us from translating the closeness in the loss
function values to the proximity of the minimizers. We shall overcome this
challenge by carefully investigating the AMP updates for decaying choices of
the regularization parameter. Throughout this section, we make use of the
properties for the state evolution parameters repeatedly (we refer the readers
to Section B for more details).

###  C.1 Proof of Theorem 3

The key enabler for obtaining Theorem 3 from Proposition 2 is the following
result, which connects the minimum $\ell_{1}$-norm interpolator with the AMP
iterations in expression (21) (with the parameters selected according to
(27)).

######  Lemma C.1.

The sequence produced by the AMP updates satisfies

$\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{1}{p}\|\bm{\theta}^{t}-\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}^{2}~{}\overset{\mathrm{a.s.}}{=}0.$
(59)

Let us first provide the proof of Theorem 3 and defer the proof of Lemma C.1
to Section C.2. To begin with, given any $t\geq 0$, in view of the pseudo-
Lipschitz property of $\psi$ (cf. (6)), one has

$\displaystyle\left|\frac{1}{p}\sum_{i=1}^{p}\psi(\widehat{\theta}^{\mathsf{Int}}_{i},\theta^{\star}_{i})-\frac{1}{p}\sum_{i=1}^{p}\psi(\theta_{i}^{t+1},\theta^{\star}_{i})\right|$
$\displaystyle\leq\frac{L}{p}\sum_{i=1}^{p}|\theta_{i}^{t+1}-\widehat{\theta}^{\mathsf{Int}}_{i}|\left(1+\sqrt{(\widehat{\theta}^{\mathsf{Int}}_{i})^{2}+(\theta^{\star}_{i})^{2}}+\sqrt{(\theta_{i}^{t+1})^{2}+(\theta^{\star}_{i})^{2}}\right)$
$\displaystyle\leq\frac{L}{p}\|\bm{\theta}^{t+1}-\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}\sqrt{\sum_{i=1}^{p}\left(1+|\widehat{\theta}^{\mathsf{Int}}_{i}|+|\theta_{i}^{t+1}|+2|\theta^{\star}_{i}|\right)^{2}}$
$\displaystyle\leq
L\frac{\|\bm{\theta}^{t+1}-\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}}{\sqrt{p}}\cdot\sqrt{4+\frac{16\|\bm{\theta}^{\star}\|_{2}^{2}}{p}+\frac{4\|\bm{\theta}^{t+1}\|_{2}^{2}}{p}+\frac{4\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}^{2}}{p}}.$

Regarding the right-hand side of the above relation, Lemma C.1 guarantees that
$\lim_{p\rightarrow\infty}\|\bm{\theta}^{t+1}-\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}/\sqrt{p}\rightarrow
0$ almost surely as $t\rightarrow\infty$; our assumptions about
$\bm{\theta}^{\star}$ ensure that $\|\bm{\theta}^{\star}\|_{2}^{2}/p$ is
bounded. By virtue of Lemma C.3, the other two terms involving state evolution
$\bm{\theta}^{t}$ and the $\ell_{1}$-minimization solution
$\widehat{\bm{\theta}}^{\mathsf{Int}}$ are also bounded. Putting these
together, one can readily conclude that

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p}\sum_{i=1}^{p}\psi(\widehat{\theta}^{\mathsf{Int}}_{i},\theta^{\star}_{i})$
$\displaystyle=\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{1}{p}\sum_{i=1}^{p}\psi(\theta_{i}^{t},\theta^{\star}_{i})\quad(\text{Lemma~{}\ref{thm:distance-
limit}, Lemma~{}\ref{lem:l2-upper-bound}})$
$\displaystyle=\lim_{t\rightarrow\infty}\mathbb{E}\left\\{\psi(\eta(\Theta+\tau_{t}Z;\zeta_{t}),\Theta)\right\\}\quad\text{(Proposition~{}\ref{prop:amp-
fixed-t})}$
$\displaystyle=\mathbb{E}\left\\{\psi(\eta(\Theta+{\tau^{\star}}Z;{\alpha^{\star}}{\tau^{\star}}),\Theta)\right\\}.$

Here, the last step makes use of Proposition B.3 and Proposition B.2 which
demonstrates that $\tau_{t}\rightarrow{\tau^{\star}}$ and
${\alpha^{\star}_{t}}\rightarrow{\alpha^{\star}}$ as $t\rightarrow\infty$. The
proof of Theorem 3 is thus complete.

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

This section is devoted to the proof of Lemma C.1. To this end, we first
introduce a key result in Lemma C.2 which characterizes the conditions under
which, the $\ell_{2}$-norm of the perturbation $\|\bm{r}\|_{2}$ can be
controlled whenever the difference between
$\mathcal{C}_{\lambda_{t}}(\bm{\theta}+\bm{r})$ and
$\mathcal{C}_{\lambda_{t}}(\bm{\theta})$ (cf. (60)) is small. The proof of
this lemma can be found in Section C.3.1. With Lemma C.2 in place, proving
Lemma C.1 boils down to verifying each required condition. To accomplish this
goal, we make use of a series of results in Lemmas C.3-C.6, followed by the
complete proof of Lemma C.1. The proofs of these auxiliary results are
deferred to Section C.3.

We define the Lasso problem associated with the regularization parameter
$\lambda_{t}$ as follows

$\displaystyle\widehat{\bm{\theta}}_{t}=\widehat{\bm{\theta}}(\lambda_{t};\bm{X},\bm{y})=\arg\\!\min_{\bm{\theta}}\mathcal{C}_{\lambda_{t}}(\bm{\theta}),\quad\text{where}\quad\mathcal{C}_{\lambda_{t}}(\bm{\theta})\coloneqq\frac{1}{2}\|\bm{y}-\bm{X}\bm{\theta}\|_{2}^{2}+\lambda_{t}\|\bm{\theta}\|_{1}.$
(60)

As we shall make clear momentarily, each iterate of our AMP updates aims to
take a step closer to the minimizer of
$\mathcal{C}_{\lambda_{t}}(\bm{\theta})$. More connections with these Lasso
estimators shall be pointed out in the sequel.

######  Lemma C.2.

There exists a function $\xi(\varepsilon,c_{1},\dots,c_{6})$ such that, if
$\bm{\theta},\bm{r}\in\mathbb{R}^{p}$ satisfy the following conditions:

  1. 1.

$\|\bm{r}\|_{2}\leq c_{1}\sqrt{p}$;

  2. 2.

$\mathcal{C}_{\lambda_{t}}(\bm{\theta}+\bm{r})\leq\mathcal{C}_{\lambda_{t}}(\bm{\theta})+c_{2}\lambda_{t}p\varepsilon$;

  3. 3.

There exists
$\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta})\in\partial\mathcal{C}_{\lambda_{t}}(\bm{\theta})$,
such that
$\|\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta})\|_{2}\leq\sqrt{p}\lambda_{t}\varepsilon$;

  4. 4.

Let
$\bm{s}=(1/\lambda_{t})[\bm{X}^{\top}(\bm{y}-\bm{X}\bm{\theta})+sg(\mathcal{C}_{\lambda_{t}},\bm{\theta})]\in\partial\|\bm{\theta}\|_{1}$,
and $S(c_{3})=\left\\{i\in[p]:|s_{i}|\geq 1-c_{3}\right\\}$. Then for any
$S^{\prime}\subseteq[p]$, $|S^{\prime}|\leq c_{4}p$, we have
$\sigma_{\min}(\bm{X}_{S(c_{3})\cup S^{\prime}})\geq c_{5}$;

  5. 5.

$\sigma_{\max}(\bm{X})\leq c_{6}$,

then $\|\bm{r}\|_{2}\leq\sqrt{p}\xi(\varepsilon,c_{1},\dots,c_{6})$, and for
any $c_{1},\dots,c_{6}>0$, one has
$\xi(\varepsilon,c_{1},\dots,c_{6})\rightarrow 0$ as $\varepsilon\rightarrow
0$.

A few remarks are in order. First, we write
$\xi(\varepsilon,c_{1},\dots,c_{6})$ to emphasize that the function does not
depend on $\bm{X}$, $\mathcal{C}_{\lambda_{t}}$ or the constructions of
$\bm{\theta},\bm{r}$. Secondly, Lemma C.2 is a generalization of BM-Lemma 3.1.
Since BM is concerned with the Lasso estimator with a single positive
$\lambda$, the corresponding lemma only requires
$\mathcal{C}_{\lambda}(\bm{\theta}+\bm{r})\leq\mathcal{C}_{\lambda}(\bm{\theta})$,
and is employed for the Lasso loss function with $\bm{\theta}+\bm{r}$ being
the Lasso solution. In this case,
$\mathcal{C}_{\lambda}(\bm{\theta}+\bm{r})\leq\mathcal{C}_{\lambda}(\bm{\theta})$
holds true for every $\bm{\theta}$ by definition. In our setting, however, the
minimum $\ell_{1}$-norm solution $\widehat{\bm{\theta}}^{\mathsf{Int}}$ is not
the minimizer of $\mathcal{C}_{\lambda_{t}}$ — recognizing the fact that we
aim to apply Lemma C.2 with
$\bm{\theta}+\bm{r}=\widehat{\bm{\theta}}^{\mathsf{Int}}$. BM-Lemma 3.1
therefore does not apply directly. Hence, it requires us to generalize their
lemma in a way suitable to our setting.

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

Now suppose that one can find constants $(c_{1},\dots,c_{6})$ and a sequence
$\left\\{\varepsilon_{t}\right\\}$ satisfying
$\lim_{t\rightarrow\infty}\varepsilon_{t}=0$, such that the five conditions in
Lemma C.2 hold almost surely with the choice of $\varepsilon=\varepsilon_{t}$,
$\bm{\theta}=\bm{\theta}^{t}$ and
$\bm{\theta}+\bm{r}=\widehat{\bm{\theta}}^{\mathsf{Int}}$. As a result, we
know that for each $t$, it holds that

$\displaystyle\|\bm{\theta}^{t}-\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}\leq\sqrt{p}\xi(\varepsilon_{t},c_{1},\dots,c_{6})$

almost surely. Further taking $t\rightarrow\infty$ yields

$\displaystyle\lim_{t\rightarrow\infty}\frac{\|\bm{\theta}^{t}-\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}}{\sqrt{p}}\leq\lim_{t\rightarrow\infty}\xi(\varepsilon_{t},c_{1},\dots,c_{6})=0,$

where the last equality follows from
$\lim_{t\rightarrow\infty}\varepsilon_{t}=0$ and the conclusion in Lemma C.2
that $\xi(\varepsilon,c_{1},\dots,c_{6})\rightarrow 0$ as
$\varepsilon\rightarrow 0$. Thus we complete the proof of Lemma C.1. It
remains to construct these $(c_{1},\dots,c_{6})$ and a converging sequence of
$\varepsilon_{t}$, such that the five conditions in Lemma C.2 hold almost
surely as $p\rightarrow\infty$.

To begin with, we make the observation that the last condition of Lemma C.2
follows directly from the classical random matrix theory where
$\sigma_{\max}(\bm{X})\rightarrow 1+\frac{1}{\sqrt{\delta}}$ almost surely
(see, e.g., Bai and Silverstein, (2010)). Thus it suffices to verify the other
four conditions.

  * •

_Condition 1 of Lemma C.2._ We introduce the following lemma, which develops
upper bounds on the $\ell_{2}$-norm of both the $\ell_{1}$-interpolation
solution and the AMP iterations. The proof of this result is deferred to
Section C.3.2.

######  Lemma C.3.

There exists a constant $C$ that only depends on $\Theta$, $\sigma$ and
$\delta$, such that, almost surely

$\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{1}{p}\|\bm{\theta}^{t}\|_{2}^{2}<C;\\\
$ (61a)
$\lim_{p\rightarrow\infty}\frac{1}{p}\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}^{2}<C.$
(61b)

By virtue of this lemma, there exists a constant $c_{1}>0$ such that
$\|\bm{r}\|_{2}=\|\widehat{\bm{\theta}}^{\mathsf{Int}}-\bm{\theta}^{t}\|_{2}\leq
c_{1}\sqrt{p}$, which validates Condition 1 of Lemma C.2.

  * •

_Condition 3 of Lemma C.2._ Similar to the constructions in BM (pg. 25), let
us denote

$\displaystyle
s_{i}^{t}\coloneqq\left\\{\begin{matrix}\text{sign}(\theta_{i}^{t}),&\text{if
}\theta_{i}^{t}\neq 0;\\\
\frac{1}{\zeta_{t-1}}\left\\{[\bm{X}^{\top}\bm{z}^{t-1}]_{i}+\theta_{i}^{t-1}\right\\},&\text{otherwise},\end{matrix}\right.\quad\text{or}\quad\bm{s}^{t}\coloneqq\frac{1}{\zeta_{t-1}}\left(\bm{\theta}^{t-1}+\bm{X}^{\top}\bm{z}^{t-1}-\bm{\theta}^{t}\right).$
(62)

In view of the AMP updates (21a), we can verify the equivalence of these two
expressions above, and that vector

$\displaystyle\text{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})\coloneqq\lambda_{t}\bm{s}^{t}-\bm{X}^{\top}(\bm{y}-\bm{X}\bm{\theta}^{t})$
(63)

is a valid sub-gradient of $\mathcal{C}_{\lambda_{t}}$ at $\bm{\theta}^{t}$.
With these notation in place, we introduce the following lemma which controls
the $\ell_{2}$-norm of
$\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})$. The proof of this
result can be found in Section C.3.3.

######  Lemma C.4.

Under our choices of $\left\\{\lambda_{t}\right\\}$ and
$\left\\{\zeta_{t}\right\\}$, the sub-gradient of $\mathcal{C}_{\lambda_{t}}$
at point $\bm{\theta}^{t}$ defined in (63) satisfy

$\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{1}{\sqrt{p}\lambda_{t}}\|\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})\|_{2}~{}\overset{\mathrm{a.s.}}{=}~{}0.$
(64)

In other words, there exists a sequence of $\\{\varepsilon_{t}\\}$ approaching
zero such that: for each $t$, it holds almost surely that
$\|\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})\|_{2}\leq\sqrt{p}\lambda_{t}\varepsilon_{t}$.

  * •

_Condition 4 in Lemma C.2._ As defined above, the vector $\bm{s}^{t}$ in the
expression (62) satisfies

$\displaystyle\bm{s}^{t}=\lambda_{t}^{-1}\left[\bm{X}^{\top}(\bm{y}-\bm{X}\bm{\theta}^{t})+\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})\right]\in\partial\|\bm{\theta}^{t}\|_{1},$

where
$\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})\in\partial\mathcal{C}_{\lambda_{t}}(\bm{\theta}^{t})$
(cf. (63)) is a valid sub-gradient of $\mathcal{C}_{\lambda_{t}}$. It turns
out that the approximate support set of $\bm{\theta}^{t}$ does not vary too
much across iterations of the AMP algorithm. This is a high-level reason why
$\sigma_{\min}(\bm{X}_{S(c_{3})\cup S^{\prime}})$ can be bounded away from
zero, despite the fact that the loss function is not strongly convex. This
observation is rigorized in the lemma below.

######  Lemma C.5.

Given every $\gamma\in(0,1)$and $t\geq 1$, define the set

$\displaystyle S_{t}(\gamma)=\left\\{i\in[p]:|s_{i}^{t}|\geq
1-\gamma\right\\},$ (65)

with $\bm{s}^{t}$ defined in (62). Then for any $\xi>0$ there exists
$t_{\star}=t_{\star}(\xi,\gamma)<\infty$ such that, for all $t_{2}\geq
t_{1}\geq t_{\star}$, one has

$\displaystyle|S_{t_{2}}(\gamma)/S_{t_{1}}(\gamma)|<p\xi,$

almost surely as $p\rightarrow\infty$.

The proof of Lemma C.5 is provided in Section C.4. Recall that BM-Lemma C.5
establishes similar results for the AMP iterates corresponding to a fixed
$\lambda.$ Here, we aim to approximate the Lasso solution for different
parameter $\lambda_{t}$ at each step of the AMP iteration. Therefore it
requires us to consider auxiliary state-evolution formulas for each $t$
separately in order to establish Lemma C.5.

Based on Lemma C.5, one can derive the following result concerning the
constrained singular value of $\bm{X}$.

######  Lemma C.6.

There exists constraints $\gamma_{1}\in(0,1)$, $\gamma_{2},\gamma_{3}>0$ and
$t_{\min}<\infty$ such that for any $t\geq t_{\min}$,

$\min_{S^{\prime}}\left\\{\sigma_{\min}(\bm{X}_{S_{t}(\gamma_{1})\cup
S^{\prime}}):S^{\prime}\subseteq[p],|S^{\prime}|\leq\gamma_{2}p\right\\}\geq\gamma_{3},$
(66)

almost surely as $p\rightarrow\infty$.

Based on the conclusion of Lemma C.3, the proof of Lemma C.6 follows verbatim
as of BM-Proposition 3.6, and is thus omitted here. Note that apart from Lemma
C.3, the proof requires BM-Lemma 3.4, which holds for AMP iterations with
general choices of $\left\\{\zeta_{t}\right\\}$, which can be directly adapted
to accommodate our setting.

As a direct consequence of Lemma C.6, Condition 4 in Lemma C.2 follows
immediately with the choice of $\bm{s}=\bm{s}^{t}$.

  * •

_Condition 2 in Lemma C.2._ To verify this condition, we only need to find a
vanishing sequence $\\{\varepsilon_{t}\\}$ such that
$\mathcal{C}_{\lambda_{t}}(\bm{\theta}^{t})-\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}^{\mathsf{Int}})\geq-
c_{2}\lambda_{t}p\varepsilon_{t}$. Towards this end, we shall control
$\mathcal{C}_{\lambda_{t}}(\bm{\theta}^{t})-\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}^{\mathsf{Int}})$
as follows. First, recalling that $\widehat{\bm{\theta}}_{t}$ is the minimizer
of $\mathcal{C}_{\lambda_{t}}(\cdot)$ (cf. (60)). Hence,

$\displaystyle\frac{\mathcal{C}_{\lambda_{t}}(\bm{\theta}^{t})-\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}^{\mathsf{Int}})}{p}\geq\frac{\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}_{t})-\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}^{\mathsf{Int}})}{p}$
$\displaystyle=\frac{1}{2p}\|\bm{y}-\bm{X}\widehat{\bm{\theta}}_{t}\|_{2}^{2}+\frac{\lambda_{t}}{p}\left[\|\widehat{\bm{\theta}}_{t}\|_{1}-\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}\right]$
$\displaystyle\geq\frac{\lambda_{t}}{p}\left[\|\widehat{\bm{\theta}}_{t}\|_{1}-\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}\right].$
(67)

In the following, we aim to show that
$\|\widehat{\bm{\theta}}_{t}\|_{1}-\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}\geq-
c_{2}\varepsilon_{t}$ for some vanishing sequence $\\{\varepsilon_{t}\\}.$
From the definition of $\mathcal{C}_{\lambda_{t}}$ in the expression (60), for
every $\bm{\theta}$ we can express

$\displaystyle\mathcal{C}_{\lambda_{t}}(\bm{\theta})=\mathcal{C}_{\lambda_{t+1}}(\bm{\theta})+(\lambda_{t}-\lambda_{t+1})\|\bm{\theta}\|_{1};$

both of the right-hand side terms $\mathcal{C}_{\lambda_{t+1}}(\bm{\theta})$
and $(\lambda_{t}-\lambda_{t+1})\|\bm{\theta}\|_{1}$ are convex and non-
negative functions of $\bm{\theta}$, and are minimized at
$\widehat{\bm{\theta}}_{t+1}$ and $\bm{0}_{p}$, respectively. For any
$\bm{\theta}\in\mathbb{R}^{p}$ with
$\|\bm{\theta}\|_{1}>\|\widehat{\bm{\theta}}_{t+1}\|_{1}\geq 0$, it is easily
seen that
$\mathcal{C}_{\lambda_{t+1}}(\bm{\theta})\geq\mathcal{C}_{\lambda_{t+1}}(\widehat{\bm{\theta}}_{t+1})$
and
$(\lambda_{t}-\lambda_{t+1})\|\bm{\theta}\|_{1}>(\lambda_{t}-\lambda_{t+1})\|\widehat{\bm{\theta}}_{t+1}\|_{1}$;
it follows that
$\mathcal{C}_{\lambda_{t}}(\bm{\theta})>\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}_{t+1})\geq\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}_{t})$.
Thus we reach the conclusion that
$\|\widehat{\bm{\theta}}_{t}\|_{1}\leq\|\widehat{\bm{\theta}}_{t+1}\|_{1}$.
Additionally, by virtue of Lemma C.3, we obtain that

$\displaystyle\lim_{p\rightarrow\infty}\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}}{p}\leq\lim_{p\rightarrow\infty}\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}}{\sqrt{p}}\leq\sqrt{C}$

is bounded almost surely. As a summery, the sequence
$\|\widehat{\bm{\theta}}_{t}\|_{1}/p$ enjoys the following two properties

    * –

$\|\widehat{\bm{\theta}}_{t}\|_{1}/p\leq\|\widehat{\bm{\theta}}_{t+1}\|_{1}/p\leq\dots\leq\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}/p$,
and almost surely as $p\rightarrow\infty$,
$\lim_{t\rightarrow\infty}\widehat{\bm{\theta}}_{t}=\widehat{\bm{\theta}}^{\mathsf{Int}}$;

    * –

$\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}/p$ is bounded almost surely.

In view of the monotone convergence theorem, we reach the conclusion that

$\displaystyle\lim_{t\rightarrow\infty}\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}-\|\widehat{\bm{\theta}}_{t}\|_{1}}{p}=0\quad\Longrightarrow\quad\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}-\|\widehat{\bm{\theta}}_{t}\|_{1}}{p}\leq\varepsilon_{t},$

for a vanishing sequence $\left\\{\varepsilon_{t}\right\\}$. Combining with
expression (• ‣ C.2), we arrive at
$\mathcal{C}_{\lambda_{t}}(\bm{\theta}^{t})-\mathcal{C}_{\lambda_{t}}(\widehat{\bm{\theta}}^{\mathsf{Int}})\geq-
c_{2}\lambda_{t}p\varepsilon_{t}.$ Thus we verify the condition 2 in Lemma
C.2.

Taking the above results collectively, we complete the proof of Lemma C.1.

###  C.3 Proof of supporting lemmas to Lemma C.1

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

As experienced readers might have already noticed, the statement of Lemma C.2
is very similar to that of BM-Lemma 3.1; the only difference lies in the
Condition 2 and Condition 3. A closer inspection at the proof of BM-Lemma 3.1
reveals that these two conditions are only used to establish BM-(3.4) and
BM-(3.5). Therefore, as long as we can show BM-(3.4) and BM-(3.5) for our
setting, the proof of our lemma will be completed, with the rest part
following verbatim from the proof of BM-Lemma 3.1.

Let us first adapt BM-(3.4) and BM-(3.5) to our setting. Throughout, we shall
use $\xi(\varepsilon)$ to denote a function of constants $c_{1},\dots,c_{6}>0$
and of $\varepsilon$ such that $\xi(\varepsilon)\rightarrow 0$ as
$\varepsilon\rightarrow 0$. Additionally, we shall use
$S=\text{supp}(\bm{\theta})\subseteq[p]$. Formally, it suffices for us to show
that, one can find such $\xi(\varepsilon)$ where

$\frac{\|\bm{r}_{\bar{S}}\|_{1}-\langle\bm{s}_{\bar{S}},\,\bm{r}_{\bar{S}}\rangle}{p}\leq\xi(\varepsilon);$
(68a) $\|\bm{X}\bm{r}\|_{2}^{2}\leq p\xi(\varepsilon).$ (68b)

Given these two inequalities, the proof of Lemma C.2 follows directly from BM-
Lemma 3.1. For the sake of brevity, we only establish the aforementioned two
inequalities, and refer readers to Bayati and Montanari, 2011b  for the rest
of the proof.

##### Verifying the expressions (68a) and (68b).

With $\bm{s}$ defined in condition 4, we obtain

$\displaystyle c_{2}\varepsilon\geq$
$\displaystyle\frac{\mathcal{C}_{\lambda_{t}}(\bm{\theta}+\bm{r})-\mathcal{C}_{\lambda_{t}}(\bm{\theta})}{p\lambda_{t}}\quad\text{(Condition
2)}$ $\displaystyle=$
$\displaystyle\frac{\|\bm{\theta}_{S}+\bm{r}_{S}\|_{1}-\|\bm{\theta}_{S}\|_{1}}{p}+\frac{\|\bm{r}_{\bar{S}}\|_{1}}{p}+\frac{\|\bm{y}-\bm{X}\bm{\theta}-\bm{Xr}\|_{2}^{2}-\|\bm{y}-\bm{X}\bm{\theta}\|_{2}^{2}}{2p\lambda_{t}}$
$\displaystyle\overset{(\mathrm{i})}{=}$
$\displaystyle\frac{\|\bm{\theta}_{S}+\bm{r}_{S}\|_{1}-\|\bm{\theta}_{S}\|_{1}-\langle\text{sign}(\bm{\theta}_{S}),\,\bm{r}_{S}\rangle}{p}+\frac{\|\bm{r}_{\bar{S}}\|-\langle\bm{s}_{\bar{S}},\,\bm{r}_{\bar{S}}\rangle}{p}+\frac{\lambda_{t}\langle\bm{s},\,\bm{r}\rangle-\langle\bm{y}-\bm{X}\bm{\theta},\,\bm{Xr}\rangle+\frac{1}{2}\|\bm{Xr}\|_{2}^{2}}{p\lambda_{t}}$
$\displaystyle\overset{(\mathrm{ii})}{=}$
$\displaystyle\frac{\|\bm{\theta}_{S}+\bm{r}_{S}\|_{1}-\|\bm{\theta}_{S}\|_{1}-\langle\text{sign}(\bm{\theta}_{S}),\,\bm{r}_{S}\rangle}{p}+\frac{\|\bm{r}_{\bar{S}}\|-\langle\bm{s}_{\bar{S}},\,\bm{r}_{\bar{S}}\rangle}{p}+\frac{\langle\text{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}),\,\bm{r}\rangle}{p\lambda_{t}}+\frac{\|\bm{Xr}\|_{2}^{2}}{2p\lambda_{t}}.\quad\text{(Condition
4)}.$

Here, $(\mathrm{i})$ follows from the fact that
$\bm{s}\in\partial\|\bm{\theta}\|_{1}$, and thus
$\text{sign}(\bm{\theta}_{S})=\bm{s}_{S}$. The equality $(\mathrm{ii})$ comes
from the definition (63).

Invoking the Cauchy-Schwarz inequality and Condition 3 yields
$\left|\langle\text{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}),\,\bm{r}\rangle/(p\lambda_{t})\right|\leq
c_{1}\varepsilon$. Substitution into the above inequality with a little
algebra leads to

$\frac{\|\bm{\theta}_{S}+\bm{r}_{S}\|_{1}-\|\bm{\theta}_{S}\|_{1}-\langle\text{sign}(\bm{\theta}_{S}),\,\bm{r}_{S}\rangle}{p}+\frac{\|\bm{r}_{\bar{S}}\|-\langle\bm{s}_{\bar{S}},\,\bm{r}_{\bar{S}}\rangle}{p}+\frac{\|\bm{Xr}\|_{2}^{2}}{2p\lambda_{t}}\leq(c_{1}+c_{2})\varepsilon.$
(69)

It can be easily seen that these three terms on the left-hand side above are
all non-negative. Therefore, the inequalities (68a) and (68b) follow directly.

####  C.3.2 Proof of Lemma C.3

The proof of this lemma is adapted from BM-Lemma 3.2 with modifications
tailored to the minimum $\ell_{1}$-norm solution. As mentioned previously,
Proposition 2 holds for general choices of $\\{\zeta_{t}\\}$, and is therefore
directly applicable to our setting. Hence, the AMP iterates satisfy

$\displaystyle\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{1}{p}\|\bm{\theta}^{t}\|_{2}^{2}=\lim_{t\rightarrow\infty}\mathbb{E}\left[\eta^{2}(\Theta+\tau_{t}Z;\zeta_{t})\right]\leq\mathbb{E}[\Theta^{2}]+{{\tau^{\star}}}^{2}.$

In other words, asymptotically $\frac{1}{p}\|\bm{\theta}^{t}\|_{2}^{2}$ is
bounded by some constant that depends only on $\mathbb{E}[\Theta^{2}]$ and
${\tau^{\star}}$.

Consequently, to prove Lemma C.3, it suffices to establish the relation (61b).
Let us first decompose the minimum $\ell_{1}$-norm interpolator
$\widehat{\bm{\theta}}^{\mathsf{Int}}$ into the projection onto the row space
of $\bm{X}$, and the residual. Formally, we write

$\displaystyle\widehat{\bm{\theta}}^{\mathsf{Int}}=\widehat{\bm{\theta}}^{\mathsf{Int}}_{\perp}+\widehat{\bm{\theta}}^{\mathsf{Int}}_{||},$

where
$\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}=\bm{X}^{\top}(\bm{XX}^{\top})^{-1}\bm{X}\widehat{\bm{\theta}}^{\mathsf{Int}}$.
It is straightforward to verify that
$\bm{X}\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}=\bm{X}\widehat{\bm{\theta}}^{\mathsf{Int}}=\bm{y}$.
We can view $\widehat{\bm{\theta}}^{\mathsf{Int}}_{\perp}$ as the projection
of $\widehat{\bm{\theta}}^{\mathsf{Int}}$ onto the orthogonal space of
$\text{row}(\bm{X})$, which is a uniformly random $(p-n)$-dimensional subspace
of $\mathbb{R}^{p}$. By Kashin Theorem (BM-Lemma F.1), there exists a
universal constant $c_{1}>0$ depending on $\delta$ such that
$\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{\perp}\|_{2}^{2}\leq
c_{1}\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{\perp}\|_{1}^{2}/p$, almost
surely as $p\rightarrow\infty$. In addition, regarding the limiting value for
the eigenvalues of Wishart matrices, it is known that there exists a constant
$c_{2}$ depending only on $\delta$ such that
$\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}\|_{2}^{2}\leq
c_{2}\|\bm{X}\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}\|_{2}^{2}$ almost
surely as $p\rightarrow\infty$ (see BM-Lemma F.2). Therefore, we arrive at

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p}\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}^{2}$
$\displaystyle=\lim_{p\rightarrow\infty}\left[\frac{1}{p}\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{\perp}\|_{2}^{2}+\frac{1}{p}\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}\|_{2}^{2}\right]$
$\displaystyle\leq\lim_{p\rightarrow\infty}\left[c_{1}\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{\perp}\|_{1}^{2}}{p^{2}}+\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}\|_{2}^{2}}{p}\right]$
$\displaystyle(\text{by Cauchy-Schwarz})$
$\displaystyle\leq\lim_{p\rightarrow\infty}\left[2c_{1}\left(\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}^{2}}{p^{2}}+\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}\|_{2}^{2}}{p}\right)+\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}\|_{2}^{2}}{p}\right]$
$\displaystyle\leq\lim_{p\rightarrow\infty}\left[2c_{1}\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}^{2}}{p^{2}}+(2c_{1}+1)c_{2}\frac{\|\bm{y}\|_{2}^{2}}{p}\right],$
(70)

where the last step uses
$\bm{X}\widehat{\bm{\theta}}^{\mathsf{Int}}_{||}=\bm{X}\widehat{\bm{\theta}}^{\mathsf{Int}}=\bm{y}$.

As a consequence, it suffices to upper bound the quantities
$\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}/p$ and $\|\bm{y}\|_{2}^{2}/p$.
First, by our model assumption,
$y_{i}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\|\bm{\theta}^{\star}\|_{2}^{2}/n+\sigma^{2})$;
it immediately follows that $\lim_{p\rightarrow\infty}\|\bm{y}\|_{2}^{2}/p$ is
bounded. In addition, we note that
$\bm{a}=\bm{X}^{\top}(\bm{XX}^{\top})^{-1}\bm{y}$ satisfies the condition
$\bm{Xa}=\bm{y}$. Since $\widehat{\bm{\theta}}^{\mathsf{Int}}$ has the minimum
$\ell_{1}$-norm over all linear interpolators, we can guarantee that

$\displaystyle\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}\leq\|\bm{X}^{\top}(\bm{XX}^{\top})^{-1}\bm{y}\|_{1}.$

Finally, by virtue of BM-Lemma F.2, we obtain
$\sigma_{\max}((\bm{XX}^{\top})^{-1})\leq c_{3}$ for some $c_{3}>0$ depending
on $\delta$, almost surely as $p\rightarrow\infty$. Collecting these
components together yields

$\displaystyle\left(\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}}{p}\right)^{2}\leq\frac{1}{p}\|\bm{X}^{\top}(\bm{XX}^{\top})^{-1}\bm{y}\|_{2}^{2}\leq\frac{\bm{y}^{\top}(\bm{XX}^{\top})^{-1}\bm{y}}{p}\leq
2\frac{\|\bm{\theta}^{\star}\|_{2}^{2}}{p}+2c_{3}\frac{\|\bm{z}\|_{2}^{2}}{p}.$

Therefore,
$\lim_{p\to\infty}(\frac{\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{1}}{p})^{2}\leq
2\mathbb{E}[\Theta^{2}]+2c_{3}\sigma^{2}$ holds almost surely. Combining this
with the expression (70), we see that
$\lim_{p\rightarrow\infty}\frac{1}{p}\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{2}^{2}$
is upper bounded by a universal constant that depends only on $\delta$.

Putting these two parts together finishes the proof of Lemma C.3.

####  C.3.3 Proof of Lemma C.4

To prove Lemma C.4, we aim to upper bound the target quantity
$\|\mathrm{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})\|_{2}$ by three
terms, and look at each term separately. For ease of exposition, let us define

$\displaystyle\omega_{t}=\frac{1}{\delta}\left\langle\eta^{\prime}(\bm{X}^{\top}\bm{z}^{t-1}+\bm{\theta}^{t-1};\zeta_{t-1})\right\rangle.$

The AMP iterate (21b) then translates into
$\bm{y}-\bm{X}\bm{\theta}^{t}=\bm{z}^{t}-\omega_{t}\bm{z}^{t-1}$. With this
piece of notation in mind, we can rewrite the sub-gradient (cf. (63)) as

$\displaystyle\text{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})$
$\displaystyle=\lambda_{t}\bm{s}^{t}-\bm{X}^{\top}(\bm{z}^{t}-\bm{z}^{t-1})-(1-\omega_{t})\bm{X}^{\top}\bm{z}^{t-1}$
$\displaystyle=\frac{\lambda_{t}}{\zeta_{t-1}}\left[\zeta_{t-1}\bm{s}^{t}-\bm{X}^{\top}\bm{z}^{t-1}\right]-\bm{X}^{\top}(\bm{z}^{t}-\bm{z}^{t-1})+\frac{\left[\lambda_{t}-\zeta_{t-1}(1-\omega_{t})\right]}{\zeta_{t-1}}\bm{X}^{\top}\bm{z}^{t-1}$
$\displaystyle=\frac{\lambda_{t}}{\zeta_{t-1}}(\bm{\theta}^{t-1}-\bm{\theta}^{t})-\bm{X}^{\top}(\bm{z}^{t}-\bm{z}^{t-1})+\frac{\left[\lambda_{t}-\zeta_{t-1}(1-\omega_{t})\right]}{\zeta_{t-1}}\bm{X}^{\top}\bm{z}^{t-1}.$

Applying the triangle inequality leads to

$\displaystyle\frac{1}{\sqrt{p}\lambda_{t}}\|\text{sg}(\mathcal{C}_{\lambda_{t}},\bm{\theta}^{t})\|_{2}\leq\frac{1}{\zeta_{t-1}}\frac{\|\bm{\theta}^{t-1}-\bm{\theta}^{t}\|_{2}}{\sqrt{p}}+\sigma_{\max}({\bm{X}})\frac{\|\bm{z}^{t}-\bm{z}^{t-1}\|_{2}}{\sqrt{p}\lambda_{t}}+\sigma_{\max}({\bm{X}})\frac{\|\bm{z}^{t-1}\|_{2}}{\sqrt{p}}\frac{\left[\lambda_{t}-\zeta_{t-1}(1-\omega_{t})\right]}{\zeta_{t-1}\lambda_{t}}.$
(71)

The proof of Lemma C.4 then boils down to analyzing the three terms on the
right-hand side of (71). We first invoke the following lemma describing the
convergence of the AMP updates, which will be proved in Section C.4.3.

######  Lemma C.7.

The AMP iterates obey the following convergence guarantees

$\displaystyle\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{1}{p\lambda_{t}^{2}}\|\bm{\theta}^{t}-\bm{\theta}^{t-1}\|_{2}^{2}=0,\qquad\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{1}{p\lambda_{t}^{2}}\|\bm{z}^{t}-\bm{z}^{t-1}\|_{2}^{2}=0.$

Note that, in the limit, Proposition B.2 ensures that
$\zeta_{t}\rightarrow\zeta^{\star}$, and is thus bounded away from $0$.
Combining Lemma C.7 and the choice of $\lambda_{t}$ ensures
$\frac{1}{\zeta_{t-1}}\frac{\|\bm{\theta}^{t-1}-\bm{\theta}^{t}\|_{2}}{\sqrt{p}}$
converges to zero as $t\rightarrow\infty$. In addition, since
$\sigma_{\max}(\bm{X})$ is almost surely bounded in the limit, the second term
on the right-hand side of the expression (71) also converges to $0$.

It remains to consider the third term on the right-hand side of the expression
(71). To this end, one can first characterize the large-system limit of
$\|\bm{z}^{t}\|_{2}$ as follows

$\displaystyle\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{\|\bm{z}^{t}\|_{2}}{\sqrt{p}}=\lim_{t\rightarrow\infty}\tau_{t}={\tau^{\star}},\quad\text{almost
surely},$ (72)

as shown in BM-Lemma 4.1. In addition, the result in BM-Lemma F.3 demonstrates
that $\forall t\geq 1$,

$\lim_{p\rightarrow\infty}\left[1-\omega_{t}\right]\overset{\text{a.s.}}{=}1-\frac{1}{\delta}\mathbb{E}\left[\eta^{\prime}(\Theta+\tau_{t}Z;\zeta_{t})\right].$

By construction, we know
$\lambda_{t}={\tau^{\star}_{t}}{\alpha^{\star}_{t}}\left(1-\frac{1}{\delta}\mathbb{E}\left[\eta^{\prime}(\Theta+{\tau^{\star}_{t}}Z;{\tau^{\star}_{t}}{\alpha^{\star}_{t}})\right]\right)$.
Hence,

$\displaystyle\left|\frac{1}{{\alpha^{\star}_{t}}{\tau^{\star}_{t}}}-\frac{1-\omega_{t}}{\lambda_{t}}\right|$
$\displaystyle\overset{\mathrm{a.s.}}{\rightarrow}\frac{1}{\lambda_{t}}\left|\frac{\lambda_{t}}{{\alpha^{\star}_{t}}{\tau^{\star}_{t}}}-\left(1-\frac{1}{\delta}\mathbb{E}\left[\eta^{\prime}(\Theta+\tau_{t}Z;\tau_{t}{\alpha^{\star}_{t}})\right]\right)\right|$
$\displaystyle=\frac{1}{\delta\lambda_{t}}\left|\mathbb{E}\left[\eta^{\prime}(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]-\mathbb{E}\left[\eta^{\prime}(\Theta+\tau_{t}Z;\tau_{t}{\alpha^{\star}_{t}})\right]\right|$
$\displaystyle\leq\frac{1}{\delta\lambda_{t}}\mathbb{E}\left[\left|\Phi\left({\alpha^{\star}_{t}}-\frac{\Theta}{{\tau^{\star}_{t}}}\right)-\Phi\left({\alpha^{\star}_{t}}-\frac{\Theta}{\tau_{t}}\right)\right|\right]+\frac{1}{\delta\lambda_{t}}\mathbb{E}\left[\left|\Phi\left({\alpha^{\star}_{t}}+\frac{\Theta}{{\tau^{\star}_{t}}}\right)-\Phi\left({\alpha^{\star}_{t}}+\frac{\Theta}{\tau_{t}}\right)\right|\right]$
$\displaystyle\leq\frac{2\mathbb{E}[|\Theta|]}{\delta{\tau^{\star}_{t}}\tau_{t}}\frac{|\tau_{t}-{\tau^{\star}_{t}}|}{\lambda_{t}},$

where the second inequality comes from the Lipschitz property of
$\Phi(\cdot)$. If we take $t\rightarrow\infty$, then the limiting values of
${\tau^{\star}_{t}}\rightarrow{\tau^{\star}}$ and
$\tau_{t}\rightarrow{\tau^{\star}}$ and Lemma C.9 immediately indicate that

$\displaystyle\frac{2\mathbb{E}[|\Theta|]}{\delta{\tau^{\star}_{t}}\tau_{t}}\overset{\mathrm{a.s.}}{\rightarrow}\frac{2\mathbb{E}[|\Theta|]}{\delta{\tau^{\star}}^{2}};\quad\frac{\left|\tau_{t}-{\tau^{\star}_{t}}\right|}{\lambda_{t}}\overset{\mathrm{a.s.}}{\rightarrow}0.$

Combining this with the model construction that
$\mathbb{E}[|\Theta|]<+\infty$, we obtain

$(1-\omega_{t})/\lambda_{t}\overset{\mathrm{a.s.}}{\rightarrow}1/({\alpha^{\star}}{\tau^{\star}}),$

and it follows that

$\displaystyle\lim_{t\rightarrow\infty}\lim_{p\rightarrow\infty}\frac{\left[\lambda_{t}-\zeta_{t-1}(1-\omega_{t})\right]}{\zeta_{t-1}\lambda_{t}}\overset{\mathrm{a.s.}}{=}\lim_{t\rightarrow\infty}\left[\frac{1}{\zeta_{t-1}}-\frac{1}{{\alpha^{\star}}{\tau^{\star}}}\right]=0.$

Taken collectively with the expression (72), the third term of the inequality
(71) converges to zero. This concludes the proof.

###  C.4 Proof of Lemma C.5 and Lemma C.7

The goal of this section is to prove Lemma C.5 and Lemma C.7, which requires
us to characterize the changes between two AMP iterates $\bm{\theta}^{s}$ and
$\bm{\theta}^{t}$ in different iterations $s\neq t$. Towards this end, in
Section C.4.1, we define the covariance between AMP iterates, and state two
auxiliary lemmas about the convergence rate of these covariances (cf. Lemma
C.9 and Lemma C.10). In Section C.4.2 and Section C.4.3, we invoke these two
lemmas to derive Lemma C.5 and Lemma C.7 respectively, which is then followed
by the proofs of these two lemmas.

####  C.4.1 Auxiliary definitions and lemmas

By virtue of Proposition 2, the state evolution sequence
$\\{\tau_{t}^{2}\\}_{t=0}^{\infty}$ can be viewed as the large $n$ “variance”
of the AMP recursions. We generalize this notion to consider the correlations
between $\bm{\theta}^{s}$ and $\bm{\theta}^{t}$ when $s\neq t$. Formally,
define a sequence of scalars $\left\\{\mathsf{R}_{s,t}\right\\}_{s,t\geq 0}$
recursively as in BM-(4.13):

$\displaystyle\mathsf{R}_{s+1,t+1}\coloneqq\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{s};\zeta_{s})-\Theta\right]\left[\eta(\Theta+Z_{t};\zeta_{t})-\Theta\right]\right\\}.$
(73)

Here $(Z_{s},Z_{t})\in{}^{2}$ are jointly Gaussian, independent of $\Theta$,
with zero mean and

$\displaystyle\mathbb{E}[Z_{s}^{2}]=\mathsf{R}_{s,s},\quad\mathbb{E}[Z_{t}^{2}]=\mathsf{R}_{t,t},\quad\mathbb{E}[Z_{s}Z_{t}]=\mathsf{R}_{s,t}.$
(74)

The boundary conditions are given by
$\mathsf{R}_{0,0}=\sigma^{2}+\mathbb{E}[\Theta^{2}]/\delta$, and

$\displaystyle\mathsf{R}_{0,t+1}=\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{t};\zeta_{t})-\Theta\right](-\Theta)\right\\},$
(75)

where $Z_{t}\sim\mathcal{N}(0,\mathsf{R}_{t,t})$ is independent of $\Theta$.
Comparing these with the definition of state evolution formula in expressions
(24a) and (24b), we can immediately see that $\mathsf{R}_{t,t}=\tau_{t}^{2}$
for $t\geq 0$. We record the following result from Bayati and Montanari, 2011b
.

######  Lemma C.8 (Theorem 4.2 in Bayati and Montanari, 2011b ).

Under the setting of Proposition 2, given any pseudo-Lipschitz function
$\psi:{}^{3}\to\real$, it holds that

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p}\sum_{i=1}^{p}\psi(\theta_{i}^{s}+(\bm{X}^{\top}\bm{z}^{s})_{i},\theta_{i}^{t}+(\bm{X}^{\top}\bm{z}^{t})_{i},\theta^{\star}_{i})\overset{\mathrm{a.s.}}{=}\mathbb{E}\left\\{\psi(\Theta+Z_{s},\Theta+Z_{t},\theta^{\star}_{i})\right\\},$

where $(Z_{s},Z_{t})$ are jointly Gaussian, independent from $\Theta$, mean-
zero and satisfy (74).

Before embarking on the proofs of Lemma C.5 and Lemma C.7, let us first
introduce two crucial lemmas concerning the convergence rate of
$\mathsf{R}_{s,t}$ for both the cases of $s=t$ and $s\neq t$ (note that the
$s=t$ case represents the convergence rate of $\tau_{t}^{2}$). Their proofs
can be found in Section C.4.5 and Section C.4.4, respectively.

######  Lemma C.9 (Convergence rate of the variance and $1$-step covariance).

Define $\mathsf{R}_{s,t}$ as in then expression (73). We have

$\displaystyle\max\left\\{|\mathsf{R}_{t,t}-{\tau^{\star}_{t}}^{2}|,|\mathsf{R}_{t+1,t+1}-{\tau^{\star}_{t}}^{2}|,\left|\mathsf{R}_{t,t}-2\mathsf{R}_{t,t+1}+\mathsf{R}_{t+1,t+1}\right|\right\\}\leq
c_{0}\exp\left\\{-c\Lambda_{t}\right\\}+4L_{\tau}\tau^{\star}_{\max}l_{t},$
(76)

where
$l_{t}\coloneqq\sum_{s=1}^{t}|\lambda_{s}-\lambda_{s+1}|\exp\left\\{-c[\Lambda_{t}-\Lambda_{s}]\right\\}$
as in Assumption 1. Here ${\tau^{\star}_{t}}$ is the solution to the system of
equations (15), $c=(2\alpha^{\star}_{\max}\tau^{\star}_{\max})^{-1}$,
$L_{\tau}$ is defined in Proposition B.2, and $c_{0}>0$ is some constant that
depends on $\Theta$, $\sigma$ and $\delta$.

With Lemma C.9 in place, for general $t_{1}$ and $t_{2}$, one can easily
decompose $\mathsf{R}_{t_{1},t_{2}}$ into multiple consecutive differences and
obtain the respective convergence rates as follows.

######  Lemma C.10 (Convergence rate of general covariances).

For any $t_{0}\geq 0$ and $t_{1},t_{2}\geq t_{0}$, with the same $c_{0}$ and
$c$ defined in Lemma C.9, the covariance $\mathsf{R}_{t_{1},t_{2}}$ satisfies

$\displaystyle\left|\mathsf{R}_{t_{1},t_{1}}-2\mathsf{R}_{t_{1},t_{2}}+\mathsf{R}_{t_{2},t_{2}}\right|\leq
4\left[\sum_{i=t_{1}}^{\infty}\sqrt{c_{0}\exp\left\\{-c\Lambda_{i}\right\\}+4L_{\tau}\tau^{\star}_{\max}l_{i}}\right]^{2}.$

Proposition B.3 ensures that
$\mathsf{R}_{t_{i},t_{i}}=\tau_{t_{i}}^{2}\to{\tau^{\star}}^{2}$ as
$t_{0}\to\infty.$ Under Assumption 1 (so that
$\sum_{t=1}^{\infty}\sqrt{l_{t}}<+\infty$ and
$\sum_{t=1}^{\infty}\exp\left\\{-c\Lambda_{t}\right\\}<\infty$), Lemma C.10
immediately implies that
$\left|\mathsf{R}_{t_{1},t_{2}}-{\tau^{\star}}^{2}\right|\rightarrow 0$ as
$t_{1},t_{2}\geq t_{0}$ and $t_{0}\rightarrow\infty$. With the assistance of
the aforementioned two lemmas, we are ready to proceed to the proofs of Lemma
C.5 and Lemma C.7.

####  C.4.2 Proof of Lemma C.5

Now we are ready to prove Lemma C.5. It suffices to show that
$\lim_{p\rightarrow\infty}|S_{t_{2}}(\gamma)\setminus
S_{t_{1}}(\gamma)|/p\leq\xi$ almost surely. As argued in the proof of BM-Lemma
3.5, it is guaranteed that

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p}\left|S_{t_{2}}(\gamma)\setminus
S_{t_{1}}(\gamma)\right|=\lim_{p\rightarrow\infty}\mathbb{P}\left\\{|\Theta+Z_{t_{2}-1}|\geq(1-\gamma)\zeta_{t_{2}-1},|\Theta+Z_{t_{1}-1}|<(1-\gamma)\zeta_{t_{1}-1}\right\\}=:P_{t_{1},t_{2}},$

where $(Z_{t_{1}},Z_{t_{2}})$ are jointly Gaussian with
$\mathbb{E}[Z_{t_{1}}^{2}]=\mathsf{R}_{t_{1},t_{1}}$,
$\mathbb{E}[Z_{t_{2}}^{2}]=\mathsf{R}_{t_{2},t_{2}}$ and
$\mathbb{E}[Z_{t_{1}}Z_{t_{2}}]=\mathsf{R}_{t_{1},t_{2}}$. If we denote
$a\coloneqq(1-\gamma){\alpha^{\star}}{\tau^{\star}}$, in view of Lemma B.3, we
know that $\forall\varepsilon>0$ and large enough $t_{\star}$, it holds that
$|(1-\gamma)\zeta_{t_{i}-1}-a|\leq\varepsilon$ for $i\in\left\\{1,2\right\\}$.
Then with the same argument as BM-Lemma 3.5, we reach

$\displaystyle P_{t_{1},t_{2}}$
$\displaystyle\leq\frac{1}{4\varepsilon^{2}}\left[\mathsf{R}_{t_{1}-1,t_{1}-1}-2\mathsf{R}_{t_{1}-1,t_{2}-1}+\mathsf{R}_{t_{2}-1,t_{2}-1}\right]+\frac{4\varepsilon}{\sqrt{2\pi\mathsf{R}_{t_{1}-1,t_{1}-1}}}$
$\displaystyle\leq\frac{\left[\sum_{i=t_{\star}}^{\infty}\sqrt{c_{0}\exp\left\\{-c\Lambda_{i}\right\\}}+\sum_{i=t_{\star}}^{\infty}\sqrt{4L_{\tau}\tau^{\star}_{\max}l_{i}}\right]^{2}}{\varepsilon^{2}}+\frac{2\varepsilon}{\sigma},$

as a consequence of Lemma C.10 and $\tau_{t}\geq\sigma$, $\forall t\geq 1$.

Under Assumption 1, $\sum_{i=t_{\star}}^{\infty}\sqrt{l_{i}}\to 0$ and
$\sum_{i=t_{\star}}^{\infty}\exp\left\\{-c/2\Lambda_{i}\right\\}\to 0$ as
$t_{\star}$ increases. Taking
$\varepsilon=\left[\sum_{i=t_{\star}}^{\infty}\sqrt{c_{0}\exp\left\\{-c\Lambda_{i}\right\\}}+\sum_{i=t_{\star}}^{\infty}\sqrt{4L_{\tau}\tau^{\star}_{\max}l_{i}}\right]^{2/3}$
gives

$P_{t_{1},t_{2}}\leq
C^{\prime}\left[\sum_{i=t_{\star}}^{\infty}\sqrt{c_{0}\exp\left\\{-c\Lambda_{i}\right\\}}+\sum_{i=t_{\star}}^{\infty}\sqrt{4L_{\tau}\tau^{\star}_{\max}l_{i}}\right]^{2/3}.$

The conclusion of Lemma C.5 thus follows immediately.

####  C.4.3 Proof of Lemma C.7

In view of the proof for BM-Lemma 4.3 — a general result proved for any
positive thresholding sequence $\left\\{\zeta_{t}\right\\}$), we obtain

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p\lambda_{t}^{2}}\|\bm{z}^{t}-\bm{z}^{t-1}\|_{2}^{2}~{}\overset{\mathrm{a.s.}}{=}~{}\lim_{p\rightarrow\infty}\frac{1}{p\lambda_{t}^{2}}\|\bm{\theta}^{t}-\bm{\theta}^{t-1}\|_{2}^{2}.$

It is thus sufficient to prove Lemma C.7 for the $\bm{\theta}^{t}$ sequence
only. As a consequence of the generalized state evolution formula (cf. Lemma
C.8), we can guarantee that

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p\lambda_{t}^{2}}\|\bm{\theta}^{t}-\bm{\theta}^{t-1}\|_{2}^{2}$
$\displaystyle=\frac{1}{\lambda_{t}^{2}}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{t};\zeta_{t})-\eta(\Theta+Z_{t-1};\zeta_{t-1})\right]^{2}\right\\}$
$\displaystyle\leq\frac{2(\zeta_{t}-\zeta_{t-1})^{2}}{\lambda_{t}^{2}}+\frac{2\mathbb{E}[(Z_{t}-Z_{t-1})^{2}]}{\lambda_{t}^{2}}.$

  * •

The term $\mathbb{E}[(Z_{t}-Z_{t-1})^{2}]$ can be controlled via Lemma C.9,
where

$\displaystyle\mathbb{E}[(Z_{t}-Z_{t-1})^{2}]=\mathsf{R}_{t,t}-2\mathsf{R}_{t-1,t}+\mathsf{R}_{t-1,t-1}\leq
c_{0}\exp\left\\{-c\Lambda_{t}\right\\}+4L\tau^{\star}_{\max}l_{t}.$ (77)

To control the right-hand side, we first obtain from Assumption 1 that
$\sum_{s=t}^{\infty}\sqrt{l_{s}}$ is a converging sequence. In addition,
Assumption 1 ensures that $\sum_{s=t}^{\infty}\lambda_{s}$ is a diverging
sequence. Then we conclude that $l_{t-1}/\lambda_{t}^{2}\rightarrow 0$ as
$t\rightarrow\infty$. Additionally, by Assumption 1, we know that
$\sum_{s=1}^{\infty}\exp\left\\{-\Lambda_{t}\right\\}$ has a finite limit,
while $\sum_{i=1}^{\infty}\lambda_{i}$ diverges, thus
$\exp\left\\{-c\Lambda_{t}\right\\}/\lambda_{t}^{2}\rightarrow 0$. Taking
these collectively ensures that

$\displaystyle\frac{2\mathbb{E}[(Z_{t}-Z_{t-1})^{2}]}{\lambda_{t}^{2}}\rightarrow
0.$

  * •

It remains to show that the term
$2(\zeta_{t}-\zeta_{t-1})^{2}/\lambda_{t}^{2}$ vanishes as
$t\rightarrow\infty$. We obtain from Lemma B.2 that
$0\leq{{\alpha^{\star}}}^{\prime}(0)\leq C$. It then immediately follows that

$\displaystyle\left|\frac{\zeta_{t}-\zeta_{t-1}}{\lambda_{t}}\right|\leq{\alpha^{\star}_{t}}\left|\frac{\tau_{t}-\tau_{t-1}}{\lambda_{t}}\right|+\tau_{t-1}\left|\frac{{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}}{\lambda_{t}-\lambda_{t-1}}\right|\frac{\lambda_{t}-\lambda_{t-1}}{\lambda_{t}}\rightarrow{\alpha^{\star}}\left|\frac{\tau_{t}-\tau_{t-1}}{\lambda_{t}}\right|+{\tau^{\star}}{{\alpha^{\star}}}^{\prime}(0)\frac{\lambda_{t}-\lambda_{t-1}}{\lambda_{t}}\rightarrow
0,$

where the limit value
$|\tau_{t}-\tau_{t-1}|/\lambda_{t}\overset{\mathrm{a.s.}}{\to}0$ follows from
Lemma C.9, and $(\lambda_{t}-\lambda_{t-1})/\lambda_{t}\to 0$ holds by virtue
of Assumption 1.

Putting all this together completes the proof.

####  C.4.4 Proof of Lemma C.10

The main idea of this proof is to decompose
$\mathsf{R}_{t_{1},t_{2}}-{\tau^{\star}}^{2}$ into terms of the form
$\mathsf{R}_{t,t+1}-{\tau^{\star}}^{2}$ or
$\mathsf{R}_{t,t}-{\tau^{\star}}^{2}$. Without loss of generality, we assume
$t_{2}>t_{1}$. The proof of BM-Theorem 4.2 (which is a general result for any
positive $\left\\{\zeta_{t}\right\\}$ sequence, so we can safely use the
arguments there) ensures that: if we define

$\displaystyle\bm{h}^{t+1}=\bm{\theta}^{\star}-(\bm{X}^{\top}\bm{z}^{t}+\bm{\theta}^{t}),$

then the empirical distribution of $\left\\{\bm{h}^{i+1}\right\\}_{T\geq i\geq
0}$ converges weakly to a sequence of Gaussian random variables
$\left\\{Z_{i}\right\\}_{T\geq i\geq 0}$ as $p\rightarrow\infty$. Here,
$Z_{0},Z_{1},Z_{2},\dots$ are Gaussian random variables, defined on the same
probability space with $\mathbb{E}[Z_{t}]=0$ and
$\mathbb{E}[Z_{t}Z_{s}]=\mathsf{R}_{t,s}$. In addition, one has

$\displaystyle\mathsf{R}_{t_{1},t_{2}}=\lim_{p\to\infty}\frac{1}{p}\langle\bm{h}^{t_{1}+1},\,\bm{h}^{t_{2}+1}\rangle.$

With these results in place, direct calculations yield

$\displaystyle\left|\mathsf{R}_{t_{1},t_{1}}-2\mathsf{R}_{t_{1},t_{2}}+\mathsf{R}_{t_{2},t_{2}}\right|=\mathbb{E}[(Z_{t_{1}}-Z_{t_{2}})^{2}]$
$\displaystyle=\sum_{i,j=t_{1}}^{t_{2}-1}\mathbb{E}[(Z_{i+1}-Z_{i})(Z_{j+1}-Z_{j})]$
$\displaystyle\leq\left[\sum_{i=t_{1}}^{t_{2}-1}\left\\{\mathbb{E}(Z_{i+1}-Z_{i})^{2}\right\\}^{1/2}\right]^{2}$
$\displaystyle\leq
4\left[\sum_{i=t_{1}}^{\infty}\sqrt{c_{0}\exp\left\\{-c\Lambda_{i}\right\\}+4L_{\tau}\tau^{\star}_{\max}l_{i}}\right]^{2},$

where the last inequality follows from inequality (77). The proof of Lemma
C.10 is thus completed.

####  C.4.5 Proof of Lemma C.9

Similar to the proof of BM-Lemma 5.7, we find it convenient to change
coordinates and define

$\displaystyle
y_{t,1}\coloneqq\mathsf{R}_{t-1,t-1}=\tau_{t-1}^{2},~{}~{}y_{t,2}\coloneqq\mathsf{R}_{t,t}=\tau_{t}^{2},~{}~{}y_{t,3}\coloneqq\mathsf{R}_{t-1,t-1}-2\mathsf{R}_{t-1,t}+\mathsf{R}_{t,t}.$

To capture the updating rule (73), we introduce the following recursive
formula via the mapping $\bm{y}_{t+1}=\mathsf{G}^{t}(\bm{y}_{t})$:

$\displaystyle y_{t+1,1}=\mathsf{G}^{t}_{1}(\bm{y}_{t})\coloneqq y_{t,2},$
(78a) $\displaystyle
y_{t+1,2}=\mathsf{G}^{t}_{2}(\bm{y}_{t})\coloneqq\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{t};{\alpha^{\star}_{t}}\sqrt{y_{t,2}})-\Theta\right]^{2}\right\\}=\mathsf{F}(y_{t,2},{\alpha^{\star}_{t}}\sqrt{y_{t,2}}),$
(78b) $\displaystyle
y_{t+1,3}=\mathsf{G}^{t}_{3}(\bm{y}_{t})\coloneqq\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{t};{\alpha^{\star}_{t}}\sqrt{y_{t,2}})-\eta(\Theta+Z_{t-1};\alpha_{t-1}^{\star}\sqrt{y_{t,1}})\right]^{2}\right\\},$
(78c)

where $(Z_{t},Z_{t-1})$ are jointly mean-zero Gaussian random variables with
$\mathbb{E}[Z_{t}^{2}]=y_{t,2}$, $\mathbb{E}[Z_{t-1}^{2}]=y_{t,1}$ and
$\mathbb{E}[(Z_{t}-Z_{t-1})^{2}]=y_{t,3}$. In contrast to BM-Lemma 5.7, the
mapping $\mathsf{G}^{t}$ is different for each step $t$ since at different
$t$, ${\alpha^{\star}_{t}}$ is chosen as the unique solution to the equation
set (26), which varies across iterations. (As such, the mapping
$\mathsf{G}^{t}$ is well-defined for $y_{t,3}\leq 2(y_{t,1}+y_{t,2})$.) In
addition, the recursive updates are initialized to $Z_{0}\sim\mathcal{N}(0,1)$
and

$\displaystyle y_{1,1}$
$\displaystyle\coloneqq\sigma^{2}+\frac{1}{\delta}\mathbb{E}[\Theta^{2}];$
$\displaystyle y_{1,2}$
$\displaystyle\coloneqq\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{0};\zeta_{0})-\Theta\right]^{2}\right\\};$
$\displaystyle y_{1,3}$
$\displaystyle\coloneqq\frac{1}{\delta}\mathbb{E}\left\\{\eta(\Theta+Z_{0};\zeta_{0})^{2}\right\\}.$

We first make note of the following fact: if
$y_{t,1}=y_{t,2}={{\tau^{\star}_{t}}}^{2}$, then one has
$y_{t+1,1}=y_{t+1,2}={{\tau^{\star}_{t}}}^{2}$ since ${\alpha^{\star}_{t}}$
satisfies the equation set (26) where

$\displaystyle{{\tau^{\star}_{t}}}^{2}=\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+{\tau^{\star}_{t}}Z_{t};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta\right]^{2}\right\\}.$

In other words, $\bm{y}^{\star}_{t}$ is a fixed point of the mapping
$\mathsf{G}^{t}$, namely,
$\bm{y}^{\star}_{t}=\mathsf{G}^{t}(\bm{y}^{\star}_{t}).$ In addition, one has
$\lim_{t\rightarrow\infty}{\tau^{\star}_{t}}={\tau^{\star}}$ by Proposition
B.3.

We claim that the following three properties hold true.

  1. 1.

As $t\rightarrow\infty$, the update sequence satisfies
$y_{t,1}\rightarrow{{\tau^{\star}_{t}}}^{2}$ and
$y_{t,2}\rightarrow{{\tau^{\star}_{t}}}^{2}$, with
$y_{t,3}<y_{t,1}+y_{t,2}-\sigma^{2}$.

  2. 2.

Define another recursive updating rule
$\widetilde{y}_{t+1,3}\coloneqq\mathsf{G}_{3}^{t}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3})$.
If we can find some $t_{0}\geq T_{\min}$ such that
$\widetilde{y}_{t_{0},3}<2{\tau^{\star}_{t_{0}}}^{2}$, then the following two
properties are satisfied

    1. (a)

for all $t\geq t_{0}$, it holds that
$\widetilde{y}_{t,3}<2{\tau^{\star}_{t}}^{2}$;

    2. (b)

it follows that $\widetilde{y}_{t,3}\rightarrow 0$ as $t\rightarrow\infty$.

Here $T_{\min}$ is some constant that is pre-determined by $\Theta$ and
$\sigma$.

  3. 3.

When $t\geq t_{0}$, the Jacobian $J_{t}\coloneqq
J_{G^{t}}(\bm{y}^{\star}_{t})$ of $G^{t}$ at
$\bm{y}^{\star}_{t}\coloneqq({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},0)$
has spectral radius

$\displaystyle\sigma(J_{t})\leq
1-\frac{\lambda_{t}}{2\alpha^{\star}_{\max}\tau^{\star}_{\max}}.$ (79)

Let us take these claims as given for the moment and proceed to the proof of
Lemma C.9. In light of the first claim, we obtain that for all large enough
$t$, one has $y_{t,3}\leq 2{\tau^{\star}_{t}}^{2}-\sigma^{2}$. Then the second
claim further guarantees that $y_{t,3}\rightarrow 0$. Taking the first two
claims collectively implies that
$\bm{y}_{t}\rightarrow\bm{y}^{\star}_{t}=({\tau^{\star}_{t}}^{2},{\tau^{\star}_{t}}^{2},0)$
as $t\rightarrow\infty$. In addition, by virtue of the third property, for
appropriately large $t$, we obtain

$\displaystyle\|\bm{y}_{t+1}-\bm{y}^{\star}_{t+1}\|_{2}=\|\bm{y}_{t+1}-\bm{y}^{\star}_{t}\|_{2}+\|\bm{y}^{\star}_{t+1}-\bm{y}^{\star}_{t}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle(\mathrm{i})}}{{\leq}}\sigma(J_{t})\|\bm{y}_{t}-\bm{y}^{\star}_{t}\|_{2}+\|\bm{y}^{\star}_{t+1}-\bm{y}^{\star}_{t}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle(\mathrm{ii})}}{{\leq}}\exp\left\\{-c\lambda_{t}\right\\}\|\bm{y}_{t}-\bm{y}^{\star}_{t}\|_{2}+4\tau^{\star}_{\max}|{\tau^{\star}_{t}}-\tau^{\star}_{t+1}|,$
(80)

where we define $c=(2\alpha^{\star}_{\max}\tau^{\star}_{\max})^{-1}$. Here,
the inequality $(\mathrm{i})$ uses the relations

$\displaystyle\bm{y}_{t+1}=\mathsf{G}^{t}(\bm{y}_{t})~{}\text{ and
}~{}\bm{y}^{\star}_{t}=\mathsf{G}^{t}(\bm{y}^{\star}_{t}),$

and $(\mathrm{ii})$ uses the property (79). Recalling that we define
$\Lambda_{t}\coloneqq\sum_{i\leq t}\lambda_{i}$, we can apply the inequality
(C.4.5) recursively to yield

$\displaystyle\frac{\|\bm{y}_{t+1}-\bm{y}^{\star}_{t+1}\|_{2}}{\exp\left\\{-c\Lambda_{t}\right\\}}$
$\displaystyle\
\leq\frac{\|\bm{y}_{t}-\bm{y}^{\star}_{t}\|_{2}}{\exp\left\\{-c\Lambda_{t-1}\right\\}}+4\tau^{\star}_{\max}\frac{|{\tau^{\star}_{t}}-\tau^{\star}_{t+1}|}{\exp\left\\{-c\Lambda_{t}\right\\}}$
$\displaystyle\
\leq\frac{\|\bm{y}_{t_{0}}-\bm{y}^{\star}_{t_{0}}\|_{2}}{\exp\left\\{-c\Lambda_{t_{0}-1}\right\\}}+4\tau^{\star}_{\max}\sum_{s=t_{0}}^{t}\frac{|{\tau^{\star}_{t}}-\tau^{\star}_{s+1}|}{\exp\left\\{-c\Lambda_{s}\right\\}}$
$\displaystyle\leq\
\frac{\|\bm{y}_{t_{0}}-\bm{y}^{\star}_{t_{0}}\|_{2}}{\exp\left\\{-c\Lambda_{t_{0}-1}\right\\}}+4L_{\tau}\tau^{\star}_{\max}\sum_{s=1}^{t}\frac{|\lambda_{s}-\lambda_{s+1}|}{\exp\left\\{-c\Lambda_{s}\right\\}}.$

Then we can conclude that, with
$c_{0}\coloneqq\|\bm{y}_{t_{0}}-\bm{y}^{\star}_{t_{0}}\|_{2}\exp\left\\{c\Lambda_{t_{0}-1}\right\\}$,

$\displaystyle\|\bm{y}_{t+1}-\bm{y}^{\star}_{t+1}\|_{2}\leq
c_{0}\exp\left\\{-c\Lambda_{t}\right\\}+4L\tau^{\star}_{\max}\sum_{s=1}^{t}|\lambda_{s}-\lambda_{s+1}|\exp\left\\{-c[\Lambda_{t}-\Lambda_{s}]\right\\}.$

Finally, recalling the definition

$\displaystyle
y_{t,1}=\mathsf{R}_{t-1,t-1}=\tau_{t-1}^{2},~{}~{}y_{t,2}=\mathsf{R}_{t,t}=\tau_{t}^{2},~{}~{}y_{t,3}=\mathsf{R}_{t-1,t-1}-2\mathsf{R}_{t-1,t}+\mathsf{R}_{t,t},$

we can show that

$\displaystyle\max\left\\{|\mathsf{R}_{t,t}-{\tau^{\star}_{t}}^{2}|,\left|\mathsf{R}_{t,t}-2\mathsf{R}_{t,t+1}+\mathsf{R}_{t+1,t+1}\right|\right\\}\leq
c_{0}\exp\left\\{-c\Lambda_{t}\right\\}+4L\tau^{\star}_{\max}\sum_{s=1}^{t}|\lambda_{s}-\lambda_{s+1}|\exp\left\\{-c[\Lambda_{t}-\Lambda_{s}]\right\\},$

which establishes the advertised result in Lemma C.9. It remains to prove the
three claims above.

####  C.4.6 Proof of the three claims

In the sequel, we look at these three claims separately.

#### Proof of Claim 1

The iteration updates (78a) and (78b), along with the initial condition, yield
that $y_{t+1,1}=y_{t,2}=\tau_{t}$, $\forall t\geq 1$. Taking the results in
Proposition B.3 collectively with
$\lim_{t\rightarrow\infty}\tau_{t}={\tau^{\star}}$ and
$\lim_{t\rightarrow\infty}{\tau^{\star}_{t}}={\tau^{\star}}$, we obtain

$y_{t,1}-{{\tau^{\star}_{t}}}^{2}\to 0\qquad\text{and}\qquad
y_{t,2}-{{\tau^{\star}_{t}}}^{2}\to 0.$

The second part of the claim is proved by induction; for the proof to go
through, let us verify the initial condition and the induction step
respectively.

  * •

For the initial condition, we can write

$\displaystyle
y_{1,1}+y_{1,2}-y_{1,3}=2\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\Theta\left(\Theta-\eta(\Theta+Z_{0};\zeta_{0})\right)\right\\}.$

It is easy to check that the function
$\theta\mapsto\theta-\eta(\theta+Z_{0};\zeta_{0})$ is monotonically increasing
for any $Z_{0}$ and $\zeta_{0}$; therefore, the random variables $\Theta$ and
$\Theta-\eta(\Theta+Z_{0};\zeta_{0})$ are positively correlated. In other
words,

$\displaystyle\frac{1}{\delta}\mathbb{E}\left\\{\Theta\left(\Theta-\eta(\Theta+Z_{0};\zeta_{0})\right)\right\\}\geq
0\quad\Longrightarrow\quad y_{1,1}+y_{1,2}-y_{1,3}\geq 2\sigma^{2}.$

  * •

Suppose $y_{t,3}<y_{t,1}+y_{t,2}-\sigma^{2}$ holds for all steps up to $t$. At
step $t+1$, the iteration formula (78) directly leads to

$\displaystyle
y_{t+1,1}+y_{t+1,2}-y_{t+1,3}=2\sigma^{2}+\frac{2}{\delta}\mathbb{E}\left[\left(\eta(\Theta+Z_{t};{\alpha^{\star}_{t}}\sqrt{y_{t,2}})-\Theta\right)\left(\eta(\Theta+Z_{t-1};\alpha_{t-1}^{\star}\sqrt{y_{t,1}})-\Theta\right)\right],$

where $(Z_{t},Z_{t-1})$ are jointly Gaussian with
$\mathbb{E}[Z_{t}^{2}]=y_{t,2}$, $\mathbb{E}[Z_{t-1}^{2}]=y_{t,1}$ and
$\mathbb{E}[(Z_{t}-Z_{t-1})^{2}]=y_{t,3}$. By definition of $Z_{t}$ and
$Z_{t-1}$, one has $\mathbb{E}[Z_{t}Z_{t-1}]=(y_{t,1}+y_{t,2}-y_{t,3})/2$
which stays positive given the induction assumption.

Now since the mapping $x\mapsto\eta(x+\theta;\zeta)-\theta$ is monotone in
$x$, we can readily conclude that

$\displaystyle\mathbb{E}\left[\left(\eta(\Theta+Z_{t};{\alpha^{\star}_{t}}\sqrt{y_{t,2}})-\Theta\right)\left(\eta(\Theta+Z_{t-1};\alpha_{t-1}^{\star}\sqrt{y_{t,1}})-\Theta\right)\right]\geq
0,$

which further leads to $y_{t+1,1}+y_{t+1,2}-y_{t+1,3}>2\sigma^{2}$. We have
thus proved that $y_{t+1,3}<y_{t+1,1}+y_{t+1,2}-\sigma^{2}$ at $t+1$.

Combining the initial condition with the induction argument, we conclude that
$y_{t,3}<y_{t,1}+y_{t,2}-\sigma^{2}$ for all $t$.

#### Proof of Claim 2(a)

To establish the second claim, with a slight abuse of notation, we define

$\displaystyle
G_{3}(y_{1},y_{2},y_{3};\alpha_{1},\alpha_{2})\coloneqq\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{1};\alpha_{1}\sqrt{y_{1}})-\eta(\Theta+Z_{2};\alpha_{2}\sqrt{y_{2}})\right]^{2}\right\\},$
(81)

where $(Z_{1},Z_{2})$ are jointly Gaussian with zero mean and
$\mathbb{E}[Z_{1}^{2}]=y_{1}$, $\mathbb{E}[Z_{2}^{2}]=y_{2}$ and
$\mathbb{E}[(Z_{1}-Z_{2})^{2}]=y_{3}$. We remark that the dependence on
$y_{3}$ is only through the covariance between $Z_{1}$ and $Z_{2}$. From the
definition of $\widetilde{y}_{t+1,3}$, we immediately have

$\displaystyle\widetilde{y}_{t+1,3}=G_{3}({\tau^{\star}_{t}}^{2},{\tau^{\star}_{t}}^{2},\widetilde{y}_{t,3},{\alpha^{\star}_{t}},\alpha^{\star}_{t-1}).$

It is straightforward to verify that $G_{3}$ is continuous in all the
parameters under our assumption that $\mathbb{E}[\Theta^{2}]<\infty$. The
continuity of $G_{3}$, together with the fact that
${{\alpha^{\star}_{t}}}^{2}$ converges, implies that
$\widetilde{y}_{t+1,3}-G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})\rightarrow
0$, for any fixed $t\geq 0$.

With this notation in mind, we are ready to prove that
$\widetilde{y}_{t+1,3}<2(\tau_{t+1}^{\star})^{2}$ for all sufficiently large
$t$ via an inductive argument. First, suppose
$\widetilde{y}_{i,3}<2(\tau_{i}^{\star})^{2}$ holds for all steps between
$t_{0}$ up to $t$. In view of relation
${{\tau^{\star}_{t}}}^{2}=\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{t};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta\right]^{2}\right\\}$,
we arrive at

$\displaystyle
2{{\tau^{\star}_{t}}}^{2}-G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})=2\sigma^{2}+\frac{2}{\delta}\mathbb{E}\left\\{\left(\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta\right)\left(\eta(\Theta+Z_{2};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta\right)\right\\},$

where again $(Z_{1},Z_{2})$ are jointly Gaussian with zero mean and
$\mathbb{E}[Z_{1}^{2}]={\tau^{\star}_{t}}^{2}$,
$\mathbb{E}[Z_{2}^{2}]={\tau^{\star}_{t}}^{2}$ and
$\mathbb{E}[Z_{1}Z_{2}]=2{{\tau^{\star}_{t}}}^{2}-\widetilde{y}_{t,3}$. Under
the induction assumption $\widetilde{y}_{t,3}\leq 2{{\tau^{\star}_{t}}}^{2}$,
the two random variables
$\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta$ and
$\eta(\Theta+Z_{2};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta$ are
positively or zero correlated. Then it is guaranteed that

$\displaystyle\frac{2}{\delta}\mathbb{E}\left\\{\left(\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta\right)\left(\eta(\Theta+Z_{2};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\Theta\right)\right\\}\geq
0\quad\Longrightarrow\quad
2{{\tau^{\star}_{t}}}^{2}-G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})\geq
2\sigma^{2}.$ (82)

Now to prove the upper bound for $\widetilde{y}_{t+1,3}$, it is sufficient for
us to control the difference between
$G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})$
and $\widetilde{y}_{t+1,3}$. Towards this end, let us invoke the Lipschitz
property for soft-thresholding function

$\displaystyle\left|\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\eta(\Theta+Z_{1};\alpha^{\star}_{t-1}{\tau^{\star}_{t}})\right|\leq{\tau^{\star}_{t}}|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|,$

which leads to

$\displaystyle|G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})-\widetilde{y}_{t+1,3}|$
(83) $\displaystyle=$
$\displaystyle|G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})-G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};\alpha_{t-1}^{\star},{\alpha^{\star}_{t}})|$
$\displaystyle=$ $\displaystyle\
\frac{1}{\delta}\mathbb{E}\left|\left[\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\eta(\Theta+Z_{1};\alpha^{\star}_{t-1}{\tau^{\star}_{t}})\right]\left[\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})+\eta(\Theta+Z_{1};\alpha^{\star}_{t-1}{\tau^{\star}_{t}})-2\eta(\Theta+Z_{2};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]\right|$
$\displaystyle\leq$ $\displaystyle\
\frac{{\tau^{\star}_{t}}|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|}{\delta}\mathbb{E}\left|\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})+\eta(\Theta+Z_{1};\alpha^{\star}_{t-1}{\tau^{\star}_{t}})-2\eta(\Theta+Z_{2};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right|$
$\displaystyle\stackrel{{\scriptstyle(\mathrm{i})}}{{\leq}}$ $\displaystyle\
\frac{{\tau^{\star}_{t}}|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|}{\delta}\cdot
4(\mathbb{E}[|\Theta|]+\tau^{\star}_{\max})\leq\frac{4(\mathbb{E}[|\Theta|]+\tau^{\star}_{\max})\tau^{\star}_{\max}}{\delta}|{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}|.$

Here, the inequality $(\mathrm{i})$ follows since
$\mathbb{E}\left[\left|\eta(\Theta+Z_{i};{\alpha^{\star}_{t}}\tau^{\star}_{s})\right|\right]\leq\mathbb{E}\left[|\Theta+Z_{1}|\right]\leq\mathbb{E}[|\Theta|]+\tau^{\star}_{\max}$
with $i\in\left\\{1,2\right\\}$ and $s\in\left\\{t,t-1\right\\}$.

Combining the inequalities (82) and (83) yields

$\displaystyle\widetilde{y}_{t+1,3}\leq
2{{\tau_{t+1}^{\star}}}^{2}+\frac{4(\mathbb{E}[|\Theta|]+\tau^{\star}_{\max})\tau^{\star}_{\max}}{\delta}|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|+2({\tau^{\star}_{t}}^{2}-{\tau^{\star}_{t+1}}^{2})-2\sigma^{2}.$

As $t\rightarrow\infty$, we know from Proposition B.3 that
$|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|\rightarrow 0$, as well as
$|{\tau^{\star}_{t}}^{2}-{\tau^{\star}_{t+1}}^{2}|\rightarrow 0$; as such, we
can always find some $T_{\min}$ determined by $\Theta$ and $\sigma^{2}$, such
that the
$\frac{4(\mathbb{E}[|\Theta|]+\tau^{\star}_{\max})\tau^{\star}_{\max}}{\delta}|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|+2|{\tau^{\star}_{t}}^{2}-{\tau^{\star}_{t+1}}^{2}|-2\sigma^{2}<0$.
In this case, we conclude that
$\widetilde{y}_{t+1,3}<2{{\tau_{t+1}^{\star}}}^{2}$, and then by induction,
$\widetilde{y}_{t,3}<2{{\tau_{t+1}^{\star}}}^{2}$, $\forall t\geq t_{0}$. This
completes the proof of Claim 2(a).

#### Proof of Claim 2(b)

It turns out that the function
$G_{3}({{\tau^{\star}_{t}}}^{2},{\tau_{t}^{\star}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})$
is the same as the $\mathsf{G}_{*}$ function defined in BM-Pg 36. We record
here two key observations from BM-Pg 36 regarding this function.

  * •

The derivative of function $G_{3}$ with respect to its third argument
satisfies

$\displaystyle\left.\frac{\partial}{\partial
x}G_{3}({{\tau^{\star}_{t}}}^{2},{\tau_{t}^{\star}}^{2},x;{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})\right|_{x=0}=\frac{1}{\delta}\mathbb{E}\left\\{\eta^{\prime}(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right\\}=1-\frac{\lambda_{t}}{{\alpha^{\star}_{t}}{\tau^{\star}_{t}}};$
(84)

  * •

The mapping $x\mapsto\frac{\partial}{\partial
x}G_{3}({{\tau^{\star}_{t}}}^{2},{\tau_{t}^{\star}}^{2},x;{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})$
is decreasing in $[0,2{\tau^{\star}_{t}}^{2})$.

In addition, we claim that
$G_{3}({{\tau^{\star}_{t}}}^{2},{\tau_{t}^{\star}}^{2},0;{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})=0$.
In order to see this, by construction in (81), we have

$\displaystyle
G_{3}({{\tau^{\star}_{t}}}^{2},{\tau^{\star}_{t}}^{2},0;{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})=\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+Z_{1};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\eta(\Theta+Z_{2};{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]^{2}\right\\},$

where $\mathbb{E}[Z_{1}^{2}]=\mathbb{E}[Z_{2}^{2}]={\tau^{\star}_{t}}^{2}$ and
$\mathbb{E}[(Z_{1}-Z_{2})^{2}]=0$. From this construction, we know
$Z_{1}=Z_{2}$, almost surely; it follows that
$\eta(\Theta+Z_{1};\alpha_{1}{\tau^{\star}_{t}})=\eta(\Theta+Z_{1};\alpha_{1}{\tau^{\star}_{t}})$,
almost surely. We therefore obtain
$G_{3}({{\tau^{\star}_{t}}}^{2},{\tau_{t}^{\star}}^{2},0;{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})=0$.

Taking these observations collectively guarantees that: under the condition
$\widetilde{y}_{t,3}<2{\tau_{t}^{\star}}^{2}$, one has

$\displaystyle
G_{3}({{\tau^{\star}_{t}}}^{2},{\tau_{t}^{\star}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})\leq(1-\lambda_{t}/{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\widetilde{y}_{t,3}\leq(1-(\alpha_{\max}^{\star}\tau_{\max}^{\star})^{-1}\lambda_{t})\widetilde{y}_{t,3}.$

In view of the inequality (83), we have

$|G_{3}({{\tau^{\star}_{t}}}^{2},{{\tau^{\star}_{t}}}^{2},\widetilde{y}_{t,3};{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})-\widetilde{y}_{t+1,3}|\leq
C|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|,$

where $C$ is determined by $\Theta$ and $\sigma^{2}$. Putting these pieces
together leads to

$\displaystyle\widetilde{y}_{t+1,3}\leq(1-(\alpha_{\max}^{\star}\tau_{\max}^{\star})^{-1}\lambda_{t})\widetilde{y}_{t,3}+C|\alpha_{t+1}^{\star}-{\alpha^{\star}_{t}}|.$
(85)

Invoking the above relation recursively, we obtain, for
$c_{1}\coloneqq(\alpha_{\max}^{\star}\tau_{\max}^{\star})^{-1}$, that

$\displaystyle\widetilde{y}_{t+1,3}$
$\displaystyle\leq\prod_{i=0}^{t-t_{0}}(1-c_{1}\lambda_{t-i})\widetilde{y}_{t_{0}}+C\sum_{i=0}^{t-t_{0}}\prod_{j=1}^{i}(1-c_{1}\lambda_{t+1-j})|\alpha^{\star}_{t+1-i}-\alpha^{\star}_{t-i}|$
$\displaystyle\leq
e^{-c_{1}\sum_{i=t_{0}}^{t}\lambda_{i}}\widetilde{y}_{t_{0}}+C\sum_{i=t_{0}}^{t}e^{-c_{1}\sum_{j=i+1}^{t}\lambda_{j}}|\alpha^{\star}_{i+1}-\alpha^{\star}_{i}|$
$\displaystyle=e^{-c_{1}\sum_{i=t_{0}}^{t}\lambda_{i}}\widetilde{y}_{t_{0}}+C\sum_{i=t_{0}}^{t/2}e^{-c_{1}\sum_{j=i+1}^{t}\lambda_{j}}|\alpha^{\star}_{i+1}-\alpha^{\star}_{i}|+C\sum_{i=t/2}^{t}e^{-c_{1}\sum_{j=i+1}^{t}\lambda_{j}}|\alpha^{\star}_{i+1}-\alpha^{\star}_{i}|.$
(86)

Observing that $\widetilde{y}_{t_{0},3}<2{\tau^{\star}_{t_{0}}}^{2}$ and the
sequence $\sum_{i=t_{0}}^{t}\lambda_{i}$ diverges to infinity, we know that
the first term on the right-hand side of (86) converges to zero as $t$
increases. Moreover, as proved in Proposition B.2, the sequence
$\left\\{{\alpha^{\star}_{t}}\right\\}$ is monotone when $t$ is sufficiently
large, and we then see that
$\sum_{t=t/2}^{+\infty}|\alpha_{t+1}^{\star}-{\alpha^{\star}_{t}}|$ converges
to zero. In the meantime, $e^{-c_{1}\sum_{j=i+1}^{t}\lambda_{j}}\leq
e^{-c_{1}\lambda_{t}}\leq e^{-c_{1}\max_{t}\lambda_{t}}$ is always controlled
by some constant. As a result, the third term on the right-hand side of (86)
also vanishes. It remains to control the second term on the right-hand side of
(86). To this end, we make the observation that
$|\alpha^{\star}_{i+1}-\alpha^{\star}_{i}|\leq 2\alpha_{\max}^{\star}$ and

$\displaystyle\sum_{i=t_{0}}^{t/2}e^{-c_{1}\sum_{j=i+1}^{t}\lambda_{j}}\leq
te^{-c_{1}\sum_{j=t/2}^{t}\lambda_{j}}=e^{(\log
t-c_{1}\sum_{j=t/2}^{t}\lambda_{j})}\to 0,$

where the last inequality follows from Assumption 1. Thus, the second term on
the right-hand side of (86) also has a zero limit. Taking these collectively,
we establish the advertised result in Claim 2(b).

#### Proof of Claim 3.

To begin with, by some direct algebra, we can express the Jacobian matrix of
mapping $\mathsf{G}^{t}$ at
$\bm{y}_{\star}=({\tau_{t}^{\star}}^{2},{\tau_{t}^{\star}}^{2},0)$ by

$\displaystyle J_{\mathsf{G}^{t}}(\bm{y}_{\star})=\begin{pmatrix}0&1&0\\\
0&\left.\frac{\mathrm{d}}{\mathrm{d}\tau^{2}}\mathsf{F}(\tau^{2},{\alpha^{\star}_{t}}\tau)\right|_{{\tau_{t}^{\star}}^{2}}&0\\\
\cdots&\cdots&\left.\frac{\mathrm{d}}{\mathrm{d}y_{3}}\mathsf{G}_{3}^{t}({\tau_{t}^{\star}}^{2},{\tau_{t}^{\star}}^{2},y_{3})\right|_{y_{3}=0}\end{pmatrix}.$

It is easily seen that the maximal eigenvalues of the above matrix satisfies
the following relation

$\displaystyle\sigma(J_{\mathsf{G}^{t}}(\bm{y}_{\star}))=\max\left\\{\left.\frac{\mathrm{d}}{\mathrm{d}\tau^{2}}\mathsf{F}(\tau^{2},{\alpha^{\star}_{t}}\tau)\right|_{{\tau_{t}^{\star}}^{2}},\left.\frac{\mathrm{d}}{\mathrm{d}y_{3}}\mathsf{G}_{3}^{t}({\tau_{t}^{\star}}^{2},{\tau_{t}^{\star}}^{2},y_{3})\right|_{y_{3}=0}\right\\}.$
(87)

To control $\sigma(J_{\mathsf{G}^{t}}(\bm{y}_{\star}))$, it is sufficient for
us to bound each term respectively. For the first term, from the proof of BM-
Proposition 1.3, we know that the function
$\tau^{2}\mapsto\mathsf{F}(\tau^{2},\alpha\tau)$ is concave, for any
$\alpha>0$ and $\Theta$ that is not identically $0$; therefore, we obtain

$\displaystyle\left.\frac{\mathrm{d}}{\mathrm{d}\tau^{2}}\mathsf{F}(\tau^{2},{\alpha^{\star}_{t}}\tau)\right|_{{\tau_{t}^{\star}}^{2}}\leq\frac{\mathsf{F}({\tau^{\star}_{t}}^{2},{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\mathsf{F}(0,0)}{{\tau^{\star}_{t}}^{2}-0}=\frac{{\tau^{\star}_{t}}^{2}-\sigma^{2}}{{\tau^{\star}_{t}}^{2}}\leq
1-\frac{\sigma^{2}}{{\tau^{\star}_{\max}}^{2}}\coloneqq\eta.$

For the second term, with the function $G_{3}$ defined in expression (81), we
write

$\displaystyle\left.\frac{\mathrm{d}}{\mathrm{d}y_{3}}\mathsf{G}_{3}^{t}({\tau_{t}^{\star}}^{2},{\tau_{t}^{\star}}^{2},y_{3})\right|_{y_{3}=0}$
$\displaystyle=\left.\frac{\mathrm{d}}{\mathrm{d}x}G_{3}({\tau_{t}^{\star}}^{2},{\tau_{t}^{\star}}^{2},x;\alpha_{t-1}^{\star},{\alpha^{\star}_{t}})\right|_{x=0}$
$\displaystyle=\left.\frac{\mathrm{d}}{\mathrm{d}x}\mathbb{E}\left[\eta(\Theta+a(x)Z+b(x)W;{\alpha^{\star}_{t}}{\tau_{t}^{\star}})\eta(\Theta+{\tau_{t}^{\star}}Z;\alpha_{t-1}^{\star}{\tau_{t}^{\star}})\right]\right|_{x=0}.$

Here $Z$ and $W$ are independent standard Gaussian random variables and we
denote

$\displaystyle
a(x)\coloneqq{\tau_{t}^{\star}}-x/(2{\tau_{t}^{\star}})\qquad\text{and
}~{}b(x)\coloneqq\sqrt{x-x^{2}/(4{\tau_{t}^{\star}}^{2})}.$ (88)

Further define

$\displaystyle
g(\Theta,Z,W;x)\coloneqq\eta(\Theta+a(x)Z+b(x)W;{\alpha^{\star}_{t}}{\tau_{t}^{\star}})\Big{[}\eta(\Theta+{\tau_{t}^{\star}}Z;\alpha_{t-1}^{\star}{\tau^{\star}})-\eta(\Theta+{\tau^{\star}}Z;{\alpha^{\star}_{t}}\tau^{\star}_{t})\Big{]}.$
(89)

With this notation in place, we can write

$\displaystyle\left.\frac{\mathrm{d}}{\mathrm{d}y_{3}}\mathsf{G}_{3}^{t}({\tau^{\star}_{t}}^{2},{\tau^{\star}_{t}}^{2},y_{3})\right|_{y_{3}=0}$
$\displaystyle\
=\left.\frac{\mathrm{d}}{\mathrm{d}y_{3}}G_{3}({\tau^{\star}_{t}}^{2},{\tau^{\star}_{t}}^{2},x;{\alpha^{\star}_{t}},{\alpha^{\star}_{t}})\right|_{x=0}+\left.\frac{\mathrm{d}}{\mathrm{d}x}\mathbb{E}\left\\{g(\Theta,Z,W;x)\right\\}\right|_{x=0}$
(90) $\displaystyle\
=1-\frac{\lambda_{t}}{{\tau^{\star}_{t}}{\alpha^{\star}_{t}}}+\left.\frac{\mathrm{d}}{\mathrm{d}x}\mathbb{E}\left\\{g(\Theta,Z,W;x)\right\\}\right|_{x=0},$

where the last equality follows from the expression (84). To control the
spectral radius of the Jacobian, it suffices to control the last term on the
right-hand side above. We claim that it satisfies the following property:

$\displaystyle\left.\frac{\mathrm{d}}{\mathrm{d}x}\mathbb{E}\left\\{g(\Theta,Z,W;x)\right\\}\right|_{x=0}\leq
2|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|.$ (91)

Taking this claim as given for the moment, we can translate the expression
(90) into

$\displaystyle\left.\frac{\mathrm{d}}{\mathrm{d}y_{3}}\mathsf{G}_{3}^{t}({\tau^{\star}_{t}}^{2},{\tau^{\star}_{t}}^{2},y_{3})\right|_{y_{3}=0}\leq
1-\frac{\lambda_{t}}{\alpha^{\star}_{\max}\tau^{\star}_{\max}}+2|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|.$

Combining the results of Proposition B.2 and Assumption 1 gives

$\displaystyle|{\alpha^{\star}_{t}}-\alpha_{t-1}^{\star}|\leq
L_{\alpha}|\lambda_{t}-\lambda_{t-1}|\leq\frac{\lambda_{t}}{4\alpha^{\star}_{\max}\tau^{\star}_{\max}}$

for sufficiently large $t$. Thus we complete the proof of expression (79). The
only thing that is left is to establish the inequality (91), which shall be
done as follows.

##### Proof of the inequality (91).

Throughout this part, we denote $a=a(x)$ and $b=b(x)$ for simplicity if there
is no confusion. Direct calculation of the derivative for the expression (89)
gives

$\displaystyle\left.\frac{\mathrm{d}}{\mathrm{d}x}\mathbb{E}\left\\{g(\Theta,Z,W;x)\right\\}\right|_{x=0}=(\mathrm{I})+(\mathrm{II}),$

where

$\displaystyle(\mathrm{I})\coloneqq\left.\mathbb{E}\left\\{-\frac{Z}{2{\tau^{\star}_{t}}}\left[\eta(\Theta+{\tau^{\star}_{t}}Z;\alpha_{t-1}^{\star}{\tau^{\star}_{t}})-\eta(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]\eta^{\prime}(\Theta+aZ+bW;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right\\}\right|_{x=0};$
$\displaystyle(\mathrm{II})\coloneqq\left.\mathbb{E}\left\\{-\frac{W}{2b}\left[\eta(\Theta+{\tau^{\star}_{t}}Z;\alpha_{t-1}^{\star}{\tau^{\star}_{t}})-\eta(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]\eta^{\prime}(\Theta+aZ+bW;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right\\}\right|_{x=0}.$

Next we shall control each term respectively. For the first term, invoking the
Lipschitz property yields $|\eta^{\prime}(x;\zeta)|\leq 1$
and$|\eta(x;\zeta_{1})-\eta(x;\zeta_{2})|\leq|\zeta_{1}-\zeta_{2}|$, which
further give

$\displaystyle(\mathrm{I})\leq\mathbb{E}\left[\left|\frac{Z}{2}\right|\cdot|\alpha_{t-1}^{\star}-{\alpha^{\star}_{t}}|\right]\leq|\alpha_{t-1}^{\star}-{\alpha^{\star}_{t}}|.$
(93)

It remains to study the second term (II), for which the main difficulty lies
in the fact that $b(x)\rightarrow 0$ as $x\rightarrow 0$. It is easy to see
that the limit value of $(\mathrm{II})$ is equal to the limiting value of
$(\mathrm{IIa})+(\mathrm{IIb})$, where

$\displaystyle(\mathrm{IIa})$
$\displaystyle\coloneqq-\frac{1}{2b}\mathbb{E}\left\\{W\left[\eta(\Theta+{\tau^{\star}_{t}}Z;\alpha_{t-1}^{\star}{\tau^{\star}_{t}})-\eta(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]\textbf{1}(\Theta+aZ+bW\geq{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right\\};$
$\displaystyle(\mathrm{IIb})$
$\displaystyle\coloneqq-\frac{1}{2b}\mathbb{E}\left\\{W\left[\eta(\Theta+{\tau^{\star}_{t}}Z;\alpha_{t-1}^{\star}{\tau^{\star}_{t}})-\eta(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]\textbf{1}(\Theta+aZ+bW\leq-{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right\\}.$

The analysis of the two parts are quite similar, so we only only discuss the
first part. Denote

$\displaystyle\mu(x;Z,\Theta,W)\coloneqq\left[\eta(\Theta+{\tau^{\star}_{t}}Z;\alpha_{t-1}^{\star}{\tau^{\star}_{t}})-\eta(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\right]\textbf{1}(\Theta+a(x)Z+b(x)W\geq{\alpha^{\star}_{t}}{\tau^{\star}_{t}}),$
(94)

To establish expression (91), it suffices to show that

$\displaystyle\lim_{x\rightarrow
0}\left|\frac{1}{2b(x)}\mathbb{E}[W\mu(x;Z,\Theta,W)]\right|\leq\left|{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}\right|.$
(95)

The remaining part of the current section is then devoted to the proof of
(95). Towards this, we make the key observation that
$\mathbb{E}[\mu(x;Z,\Theta,W)\mid W=w]$ is a Lipschitz function in $w.$ In
order to see this, first notice that the convoluted density of
$p_{aZ}*p_{\Theta}$ is bounded over all
$a\in[{\tau^{\star}_{t}}/2,{\tau^{\star}_{t}}]$. Indeed, we can calculate the
convolution density by

$\displaystyle(p_{aZ}*p_{\Theta})(z)=\int_{-\infty}^{\infty}\frac{1}{a\sqrt{2\pi}}\exp\left\\{-\frac{(\Theta-z)^{2}}{2a^{2}}\right\\}\mathrm{d}P_{\Theta}\leq\frac{1}{a\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{d}P_{\Theta}=\frac{1}{a\sqrt{2\pi}}\leq\frac{1}{{\tau^{\star}_{t}}},\quad\forall
z\in\mathbb{R}.$ (96)

Next, for any $x\in(0,{\tau^{\star}_{t}}^{2})$ and $w_{1}<w_{2}$, direct
calculations yield

$\displaystyle\
\Big{|}\mathbb{E}[\mu(x;Z,\Theta,w_{1})]-\mathbb{E}[\mu(x;Z,\Theta,w_{2})]\Big{|}$
$\displaystyle=$ $\displaystyle\
\Big{|}\mathbb{E}\big{[}(\eta(\Theta+{\tau^{\star}_{t}}Z;\alpha_{t-1}^{\star}{\tau^{\star}_{t}})-\eta(\Theta+{\tau^{\star}_{t}}Z;{\alpha^{\star}_{t}}{\tau^{\star}_{t}}))\cdot(\textbf{1}(\Theta+a(x)Z+b(x)w_{1}\geq{\alpha^{\star}_{t}}{\tau^{\star}_{t}})-\textbf{1}(\Theta+a(x)Z+b(x)w_{2}\geq{\alpha^{\star}_{t}}{\tau^{\star}_{t}})\big{]}\Big{|}$
$\displaystyle\leq$ $\displaystyle\
{\tau^{\star}_{t}}|{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}|\cdot\mathbb{P}\left\\{{\alpha^{\star}_{t}}{\tau^{\star}_{t}}-b(x)w_{2}\leq\Theta+a(x)Z\leq{\alpha^{\star}_{t}}{\tau^{\star}_{t}}-b(x)w_{1}\right\\}$
$\displaystyle\leq$ $\displaystyle\
b(x)|{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}||w_{1}-w_{2}|,$

where the last inequality follows from the expression (96) and the fact that
$a(x)\in[{\tau^{\star}_{t}}/2,{\tau^{\star}}]$ when
$0<x<{\tau^{\star}_{t}}^{2}$.

Now we proceed to control $\mathbb{E}[W\mu(x;Z,\Theta,W)].$ First we can write

$\displaystyle\left|\mathbb{E}\left[W\mu(x;Z,\Theta,W)-W\mu(x;Z,\Theta,0)\right]\right|=$
$\displaystyle\
\mathbb{E}\left\\{W\mathbb{E}\left[\mu(x;Z,\Theta,W)-\mu(x;Z,\Theta,0)|W\right]\right\\}$
$\displaystyle\leq$ $\displaystyle\
b(x)|{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}|\mathbb{E}[W^{2}]$
$\displaystyle=$ $\displaystyle\
b(x)|{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}|.$

Additionally, by symmetry, we know that

$\displaystyle\mathbb{E}\left[W\mu(x;Z,\Theta,0)\right]=0,$

since $W\sim\mathcal{N}(0,1)$ is independent from $\mu(x;Z,\Theta,0)$. Putting
everything together, we conclude that

$\displaystyle\left|\frac{1}{2b(x)}\mathbb{E}[W\mu(x;Z,\Theta,W)]\right|\leq\frac{1}{2}|{\alpha^{\star}_{t}}-\alpha^{\star}_{t-1}|,$

thus concluding the proof of the inequality (95). Similarly, one can control
$(\mathrm{IIb})$. Taking these collectively with (93), we validated the
inequality (91).

##  Appendix D Proofs about the risk curve

###  D.1 Proof of Lemma 1 and Lemma 2

In this section, we present the proofs of Lemma 1 and Lemma 2 by analyzing
each term inside the derivative (3.2.2). The proofs are divided into several
parts: first in Section D.1.1, we derive the explicit expressions of
$F_{1}(\nu,\delta,\alpha)$, $F_{2}(\nu,\delta,\alpha)$ and their partial
derivatives, which serve as the basis for subsequent analyses. Their limiting
values are computed in Section D.1.2 for the case when $\delta\rightarrow
1^{-}$, which in turn establishes Lemma 2.

When it comes to the case $\delta\rightarrow 0^{+}$, we start by stating two
crucial lemmas concerning the growth of ${\alpha^{\star}}$ and
${\nu^{\star}}$, and some partial derivatives, as in Lemma D.1 and D.2.
Properties (38b) and (39) are direct consequences of these two lemmas. For
property (38a), it turns out that the first-order approximations of both the
minuend and subtrahend cancel out. Therefore, we need to resort to the second-
order computation of these two terms, which is postponed to Section D.1.3.
Putting these together completes the proof of Lemma 1. Finally, the proofs of
auxiliary Lemma D.1 and D.2 are deferred to the end of this section.

For notational simplicity, throughout this section, we denote
$F_{1}(\nu,\delta,\alpha)$ as $F_{1}$, and similarly for $F_{2}$ and all other
partial derivative functions when the values of $(\nu,\delta,\alpha)$ are
clear from the context.

####  D.1.1 Expressions of $F_{1}$ and $F_{2}$

Let us first express $F_{1}$ and $F_{2}$ as functions of the density and
cumulative density functions of the standard Gaussian distribution (denoted as
$\phi(\cdot)$ and $\Phi(\cdot)$ respectively). For $F_{1}$, it is easily seen
that

$F_{1}(\nu,\delta,\alpha)=\epsilon\left[\Phi(-\alpha+\sqrt{\delta}\nu)+\Phi(-\alpha-\sqrt{\delta}\nu)\right]+2(1-\epsilon)\Phi(-\alpha)-\delta.$
(97)

When it comes to $F_{2}$, invoking the equality (124a) in Lemma E.1, we arrive
at the following decomposition

$\displaystyle
F_{2}=F_{21}+\epsilon\delta^{-1}F_{22}+(1-\epsilon)\delta^{-1}F_{23},$ (98)

where

$\displaystyle F_{21}(\nu,\delta,\alpha)\coloneqq$
$\displaystyle\frac{\nu^{2}}{M^{2}}-1;$ (99) $\displaystyle
F_{22}(\nu,\delta,\alpha)\coloneqq$
$\displaystyle\int_{-\infty}^{\infty}(\eta(\sqrt{\delta}\nu+z,\alpha)-\sqrt{\delta}\nu)^{2}\phi(z)\mathrm{d}z$
$\displaystyle=$ $\displaystyle\
(\sqrt{\delta}\nu-\alpha)\phi(\alpha+\sqrt{\delta}\nu)+(-\sqrt{\delta}\nu-\alpha)\phi(\alpha-\sqrt{\delta}\nu)$
$\displaystyle+(\alpha^{2}+1-\delta\nu^{2})\left[\Phi(-\alpha-\sqrt{\delta}\nu)+\Phi(-\alpha+\sqrt{\delta}\nu)\right]+\delta\nu^{2};$
$\displaystyle F_{23}(\nu,\delta,\alpha)\coloneqq$
$\displaystyle\int_{-\infty}^{\infty}\eta^{2}(z,\alpha)\phi(z)\mathrm{d}z=2\left[-\alpha\phi(\alpha)+(\alpha^{2}+1)\Phi(-\alpha)\right].$

Direct computation of the partial derivatives yield the following expressions.

##### Partial derivatives of $F_{1}$.

For $F_{1}$, we have the following three partial derivatives with respect to
$\alpha,\delta$ and $\nu$ respectively, where

$\displaystyle\nabla_{\alpha}F_{1}(\nu,\delta,\alpha)$
$\displaystyle=-\epsilon\left[\phi(\alpha-\sqrt{\delta}\nu)+\phi(\alpha+\sqrt{\delta}\nu)\right]-2(1-\epsilon)\phi(\alpha);$
(100) $\displaystyle\nabla_{\delta}F_{1}(\nu,\delta,\alpha)$
$\displaystyle=\epsilon\frac{\nu}{2\sqrt{\delta}}\left[\phi(\alpha-\sqrt{\delta}\nu)-\phi(\alpha+\sqrt{\delta}\nu)\right]-1;$
$\displaystyle\nabla_{\nu}F_{1}(\nu,\delta,\alpha)$
$\displaystyle=\epsilon\sqrt{\delta}\left[\phi(\alpha-\sqrt{\delta}\nu)-\phi(\alpha+\sqrt{\delta}\nu)\right].$

##### Partial derivatives of $F_{2}$.

With respect to $\alpha$, from the decomposition (98), one obtains

$\displaystyle\nabla_{\alpha}F_{2}=\epsilon\delta^{-1}\nabla_{\alpha}F_{22}+(1-\epsilon)\delta^{-1}\nabla_{\alpha}F_{23},$
(101)

where

$\displaystyle\nabla_{\alpha}F_{22}(\nu,\delta,\alpha)=$
$\displaystyle-2\left[\phi(\alpha+\sqrt{\delta}\nu)+\phi(\alpha-\sqrt{\delta}\nu)\right]+2\alpha\left[\Phi(-\alpha-\sqrt{\delta}\nu)+\Phi(-\alpha+\sqrt{\delta}\nu)\right];$
$\displaystyle\nabla_{\alpha}F_{23}(\nu,\delta,\alpha)=$
$\displaystyle-4\left[\phi(\alpha)-\alpha\Phi(-\alpha)\right].$

With respect to $\delta$, a little algebra leads to

$\displaystyle\nabla_{\delta}F_{2}(\nu,\delta,\alpha)$
$\displaystyle=-\delta^{-2}\left[\epsilon
F_{22}+(1-\epsilon)F_{23}\right]+\epsilon\delta^{-1}\nabla_{\delta}F_{22}$
$\displaystyle=-\epsilon\delta^{-2}\left[F_{22}-\delta\nabla_{\delta}F_{22}\right]-(1-\epsilon)\delta^{-2}F_{23}.$
(102)

We then further evaluate the right-hand side of the above equation.
Recognizing that

$\nabla_{\delta}F_{22}(\nu,\delta,\alpha)=\nu^{2}\left[\Phi(\alpha-\sqrt{\delta}\nu)-\Phi(-\alpha-\sqrt{\delta}\nu)\right],$

we can guarantee that

$\displaystyle
F_{22}-\delta\nabla_{\delta}F_{22}=-(\alpha-\sqrt{\delta}\nu)\phi(\alpha+\sqrt{\delta}\nu)-(\alpha+\sqrt{\delta}\nu)\phi(\alpha-\sqrt{\delta}\nu)+(\alpha^{2}+1)\left[\Phi(-\alpha-\sqrt{\delta}\nu)+\Phi(-\alpha+\sqrt{\delta}\nu)\right].$

Plugging this into the expression (D.1.1) yields the final expression of
$\nabla_{\delta}F_{2}.$ Finally, with respect to $\nu$, it is straightforward
to verify that

$\displaystyle\nabla_{\nu}F_{2}(\nu,\delta,\alpha)=2M^{-2}\nu+\epsilon\delta^{-1}\nabla_{\nu}F_{22},$

where

$\displaystyle\nabla_{\nu}F_{22}(\nu,\delta,\alpha)=2\nu\delta\left[\Phi(\alpha-\sqrt{\delta}\nu)-\Phi(-\alpha-\sqrt{\delta}\nu)\right].$

####  D.1.2 The limit of $\delta\rightarrow 1^{-}$: proof of Lemma 2

Equipped with these close-form expressions, we are ready to study the the
behaviors of ${\alpha^{\star}}$ and ${\nu^{\star}}$ when $\delta\rightarrow
1^{-}$, and check the limiting orders of all terms in the expression (3.2.2).

##### Limiting orders of ${\alpha^{\star}}$ and ${\nu^{\star}}$.

We first make the observation that for any given $\nu,\alpha>0$,
$F_{1}(\nu,\delta,\alpha)$ is strictly decreasing in $\alpha$ and increasing
in $\nu$. Also we note that ${\nu^{\star}}<M$ as
$M/{\nu^{\star}}={\tau^{\star}}>1.$ Then it is easy to check that

$\displaystyle
0=F_{1}({\nu^{\star}},\delta,{\alpha^{\star}})<F_{1}(M,\delta,{\alpha^{\star}})<F_{1}(M,\delta,0)=1-\delta.$

Taking $\delta\rightarrow 1^{-}$, one can deduce that
$F_{1}(M,\delta,{\alpha^{\star}})\rightarrow 0$, which further indicates that
${\alpha^{\star}}\rightarrow 0$. Now putting ${\alpha^{\star}}\rightarrow 0$
together with the expression (99), we reach

$\displaystyle F_{22}({\nu^{\star}},\delta,{\alpha^{\star}})\rightarrow
1;\quad F_{23}({\nu^{\star}},\delta,{\alpha^{\star}})\rightarrow
1\quad\Longrightarrow\quad
F_{2}({\nu^{\star}},\delta,{\alpha^{\star}})\rightarrow\frac{{\nu^{\star}}^{2}}{M^{2}}.$

Combining this with the fact that
$F_{2}({\nu^{\star}},\delta,{\alpha^{\star}})=0$ ensures
${\nu^{\star}}\rightarrow 0$.

##### Limiting order of ${\nu^{\star}}^{\prime}(\delta)$.

With the limiting values of ${\alpha^{\star}}$ and ${\nu^{\star}}$ in place,
we are ready to check the limiting orders of all the terms in expression
(3.2.2). First, taking the expressions of $F_{1}$, $F_{2}$ and their
derivatives in Section D.1.1 collectively with some algebra, we can guarantee
that

$\displaystyle\nabla_{\alpha}F_{1}\sim-2\phi(0);\quad\nabla_{\delta}F_{1}\sim-1;\quad\nabla_{\nu}F_{1}\sim
2\epsilon\delta{\nu^{\star}}{\alpha^{\star}}\phi(0);$
$\displaystyle\nabla_{\alpha}F_{2}\sim(-4+2\epsilon)\phi(0);\quad\nabla_{\delta}F_{2}\sim-1;\quad\nabla_{\nu}F_{2}\sim
2M^{-2}{\nu^{\star}},$

when $\delta\rightarrow 1^{-}$ and all the partial derivatives are evaluated
at the point $({\nu^{\star}},\delta,{\alpha^{\star}})$. Substituting these
relations into (3.2.2) yields

$\displaystyle\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}\sim-2(1-\epsilon)\phi(0);$
$\displaystyle\nabla_{\nu}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\nu}F_{1}\sim-4M^{-2}\phi(0){\nu^{\star}}.$

When $\epsilon$ is bounded away from $1$ and when $M$ bounded away from
$\infty$, one can easily see that
${\nu^{\star}}^{\prime}(\delta)\rightarrow-\infty$ as $\delta\rightarrow
1^{-}$ (since $0<{\nu^{\star}}\rightarrow 0$). We thus conclude the proof of
Lemma 2.

####  D.1.3 The limit of $\delta\rightarrow 0^{+}$: proof of Lemma 1

Before embarking on the main proof, we make note of the following two lemmas
concerned with the growth of ${\alpha^{\star}}$ and ${\nu^{\star}}$ and the
derivatives of $F_{1}$ and $F_{2}$ when $\delta\rightarrow 0^{+}$ which shall
be used multiple times. Their proofs of these lemmas can be found in Section
D.2 and D.3 respectively.

######  Lemma D.1.

When $\delta\rightarrow 0^{+}$, the following properties are satisfied

$\lim_{\delta\rightarrow
0^{+}}{\alpha^{\star}}=+\infty;\quad\lim_{\delta\rightarrow
0^{+}}\sqrt{\delta}{\alpha^{\star}}=0;\quad\lim_{\delta\rightarrow
0^{+}}\frac{\delta{\alpha^{\star}}}{\phi({\alpha^{\star}})}=2;\quad\lim_{\delta\rightarrow
0^{+}}{\nu^{\star}}=\nu_{0}.$ (103)

######  Lemma D.2.

When $\delta\rightarrow 0^{+}$, the limiting order of the partial derivatives
of $F_{1}$ and $F_{2}$ are characterized as following:

$\displaystyle\lim_{\delta\rightarrow
0^{+}}\frac{\nabla_{\alpha}F_{1}}{\phi({\alpha^{\star}})}=-2;\quad\lim_{\delta\rightarrow
0^{+}}\nabla_{\delta}F_{1}=-1;\quad\lim_{\delta\rightarrow
0^{+}}\frac{\nabla_{\nu}F_{1}}{\phi^{2}({\alpha^{\star}})}=4\epsilon\nu_{0};$
(104) $\displaystyle\lim_{\delta\rightarrow
0^{+}}{\alpha^{\star}}\nabla_{\alpha}F_{2}=-2;\quad\lim_{\delta\rightarrow
0^{+}}{\alpha^{\star}}\phi({\alpha^{\star}})\nabla_{\delta}F_{2}=-1;\quad\lim_{\delta\rightarrow
0^{+}}\nabla_{\nu}F_{2}=\frac{2}{\nu_{0}},$ (105)

where all the partial derivatives of $F_{1}$ and $F_{2}$ are evaluated at the
point $({\nu^{\star}},\delta,{\alpha^{\star}})$.

First note that relation (39) in Lemma 1 directly comes from Lemma D.1; Lemma
D.2 combined with a little algebra leads to relation (38b). Therefore, to
prove Lemma 1, it is only left for us to establish the limiting order of
(38a), which shall be done as follows.

##### Proof of relation (38a).

By virtue of Lemma D.2, one immediately notices that the leading terms in
$\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}$ and
$\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}$ cancel out with each other.
Therefore, to characterize the limiting order of
$\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}$,
it requires us to investigate the second-order terms. Throughout this part,
all the partial derivatives of $F_{1}$ and $F_{2}$ are calculated at the point
$({\nu^{\star}},\delta,{\alpha^{\star}})$ unless otherwise noted.

#### Second-order terms of $\nabla_{\alpha}F_{1}$ and $\nabla_{\delta}F_{1}$.

Let us consider $\nabla_{\alpha}F_{1}$ and $\nabla_{\delta}F_{1}$. We first
make the observation that

$\displaystyle\frac{\nabla_{\alpha}F_{1}+2\phi({\alpha^{\star}})}{\phi({\alpha^{\star}})}$
$\displaystyle=-\epsilon\left[e^{-\delta{\nu^{\star}}^{2}/2}\left(e^{{\alpha^{\star}}{\sqrt{\delta}\nu^{\star}}}+e^{-{\alpha^{\star}}{\sqrt{\delta}\nu^{\star}}}\right)-2\right]$
$\displaystyle\stackrel{{\scriptstyle(\mathrm{i})}}{{\sim}}-\epsilon{\alpha^{\star}}^{2}\delta{\nu^{\star}}^{2}\stackrel{{\scriptstyle(\mathrm{ii})}}{{\sim}}-2\epsilon\nu_{0}^{2}{\alpha^{\star}}\phi({\alpha^{\star}}),$
(106)

where $(\mathrm{ii})$ follows as a direct consequence of (103). Regarding the
relation $(\mathrm{i})$, by virtue of the Taylor expansion, we obtain

$\displaystyle
e^{{\alpha^{\star}}{\sqrt{\delta}\nu^{\star}}}+e^{-{\alpha^{\star}}{\sqrt{\delta}\nu^{\star}}}=2+\delta{\nu^{\star}}^{2}{\alpha^{\star}}^{2}+o(\delta{\nu^{\star}}^{2}{\alpha^{\star}}^{2}),\quad
e^{-\delta{\nu^{\star}}^{2}/2}=1-\delta{\nu^{\star}}^{2}/2+o(\delta{\nu^{\star}}^{2}).$

As already shown in Lemma D.1, ${\alpha^{\star}}\rightarrow\infty$, and
therefore, the $\delta{\nu^{\star}}^{2}/2$ term is of smaller order compared
with $\delta{\nu^{\star}}^{2}{\alpha^{\star}}^{2}$, which in turn justifies
step $(\mathrm{i})$. Here, recall that these limits are taken with respect to
$\delta\rightarrow 0^{+}$.

Moreover, direct computation gives

$\displaystyle\frac{\phi({\alpha^{\star}}-\sqrt{\delta}{\nu^{\star}})-\phi({\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})}{\sqrt{\delta}{\alpha^{\star}}{\nu^{\star}}\phi({\alpha^{\star}})}=\exp\left\\{-\delta{\nu^{\star}}^{2}/2\right\\}\frac{\exp\\{\sqrt{\delta}{\alpha^{\star}}{\nu^{\star}}\\}-\exp\\{-\sqrt{\delta}{\alpha^{\star}}{\nu^{\star}}\\}}{\sqrt{\delta}{\alpha^{\star}}{\nu^{\star}}}\sim
2,\quad\delta\rightarrow 0^{+},$ (107)

where the the last relation is given by L’Hôpital’s rule, combined with the
facts $\sqrt{\delta}{\alpha^{\star}}\rightarrow 0$ and
${\nu^{\star}}\rightarrow\nu_{0}$ as $\delta\rightarrow 0^{+}$. Taking this
collective with Lemma D.1, one arrives at

$\displaystyle\nabla_{\delta}F_{1}+1=\epsilon\frac{{\nu^{\star}}}{2\sqrt{\delta}}\left[\phi({\alpha^{\star}}-\sqrt{\delta}{\nu^{\star}})-\phi({\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})\right]\sim\epsilon\nu_{0}^{2}{\alpha^{\star}}\phi({\alpha^{\star}}).$
(108)

#### Second-order term of $\nabla_{\delta}F_{2}$.

Moving on to the quantity $\nabla_{\delta}F_{2}$, we can rearrange terms to
derive the following decomposition

$\frac{\nabla_{\delta}F_{2}+({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}{({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}=\underbrace{\frac{\nabla_{\delta}F_{2}+\delta^{-2}F_{23}}{({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}}_{=:\Delta_{1}}-\underbrace{\frac{\delta^{-2}F_{23}-({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}{({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}}_{=:\Delta_{2}}.$
(109)

With this decomposition in mind, we proceed to control the two terms above
separately.

  * •

Step 1: Bounding the term $\Delta_{1}$. Armed with the expressions of
$\nabla_{\delta}F_{2}$ and $F_{23}$ in closed-form, one can re-arrange terms
and obtain

$\displaystyle\nabla_{\delta}F_{2}+\delta^{-2}F_{23}=-\epsilon\delta^{-2}\left[f(s)+f(-s)-2f(0)\right],$
(110)

where
$f(s)\coloneqq-({\alpha^{\star}}+s)\phi({\alpha^{\star}}-s)+({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}}+s)$,
for $s={\sqrt{\delta}\nu^{\star}}$. To facilitate analysis of the expression
(110), we make note of the following two facts:

    * –

For every $k\geq 1$, the rescaled derivative
$f^{(k)}(s)/\phi({\alpha^{\star}}-s)$ is a polynomial of $s$ and
${\alpha^{\star}}$;

    * –

Since ${\alpha^{\star}}\rightarrow\infty$ and
${\nu^{\star}}\rightarrow\nu_{0}$ as $\delta\rightarrow 0^{+}$,
$s={\sqrt{\delta}\nu^{\star}}$ is therefore negligible compared to any
polynomial of ${\alpha^{\star}}$.

Leveraging the aforementioned results, one can see that in the Taylor
expansion of $f$ around $s=0$, the non-zero term with the lowest order of $s$
is the dominant term. By further calculating $f^{(2)}(0)=0$ and
$f^{(4)}(0)=6{\alpha^{\star}}\phi({\alpha^{\star}})$, we see that

$\displaystyle\nabla_{\delta}F_{2}+\delta^{-2}F_{23}\sim-\epsilon\delta^{-2}\frac{2}{4!}6{\alpha^{\star}}\phi({\alpha^{\star}})({\sqrt{\delta}\nu^{\star}})^{4}\sim-\frac{\epsilon\nu_{0}^{4}}{2}{\alpha^{\star}}\phi({\alpha^{\star}}).$

  * •

Step 2: Bounding the term $\Delta_{2}$. Recalling our definition for function
$F_{23}$ (cf. (99)), we can express $\Delta_{2}$ as follows

$\displaystyle\frac{\delta^{-2}F_{23}-({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}{({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}=(1+R_{1})(1+R_{2})-1,$
(111)

where

$\displaystyle
R_{1}\coloneqq\frac{{\alpha^{\star}}^{3}\left[-{\alpha^{\star}}\phi({\alpha^{\star}})+({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}})\right]}{2\phi({\alpha^{\star}})}-1;\quad
R_{2}\coloneqq\left(\frac{2\phi({\alpha^{\star}})}{{\alpha^{\star}}\delta}\right)^{2}-1.$

Let us consider each term separately. Firstly, directly invoking expression
(124d) from Lemma E.1 suggests $R_{1}=o(1)$, as $\delta\rightarrow 0^{+}$. To
further study the limiting order of $R_{1}$, we obtain

$\displaystyle\lim_{{\alpha^{\star}}\rightarrow\infty}{\alpha^{\star}}^{2}R_{1}$
$\displaystyle=\lim_{{\alpha^{\star}}\rightarrow\infty}\frac{{\alpha^{\star}}^{5}\left[-{\alpha^{\star}}\phi({\alpha^{\star}})+({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}})\right]-2{\alpha^{\star}}^{2}\phi({\alpha^{\star}})}{2\phi({\alpha^{\star}})}$
(L’Hôpital’s rule)
$\displaystyle=\lim_{{\alpha^{\star}}\rightarrow\infty}\frac{(2{\alpha^{\star}}^{2}-7{\alpha^{\star}}^{4})\phi({\alpha^{\star}})+(7{\alpha^{\star}}^{5}+5{\alpha^{\star}}^{3})\Phi(-{\alpha^{\star}})}{-2\phi({\alpha^{\star}})}+2$
$\displaystyle=\frac{7}{2}\lim_{{\alpha^{\star}}\rightarrow\infty}\frac{{\alpha^{\star}}^{3}\left[{\alpha^{\star}}\phi({\alpha^{\star}})-({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}})\right]}{\phi({\alpha^{\star}})}-\lim_{{\alpha^{\star}}\rightarrow\infty}\frac{{\alpha^{\star}}^{2}\left[\phi({\alpha^{\star}})-{\alpha^{\star}}\Phi(-{\alpha^{\star}})\right]}{\phi({\alpha^{\star}})}+2$
$\displaystyle=-6,$

where the last step uses relations (124c) and (124d) from Lemma E.1. This
establishes the limiting order $R_{1}\sim-6{\alpha^{\star}}^{-2}$ as
$\delta\rightarrow 0^{+}$.

Turning to the term $R_{2}$, one can easily conclude from Lemma D.1 that
$R_{2}=o(1)$ as $\delta\rightarrow 0^{+}$. To further pin down the limiting
order of $R_{2}$, we recall that

$\displaystyle\epsilon\left[\Phi(-{\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})+\Phi(-{\alpha^{\star}}-\sqrt{\delta}{\nu^{\star}})\right]+2(1-\epsilon)\Phi(-{\alpha^{\star}})-\delta=0$

as $F_{1}({\nu^{\star}},\delta,{\alpha^{\star}})=0$. These allow us to
decompose

$\displaystyle{\alpha^{\star}}^{2}\left[\frac{\delta{\alpha^{\star}}}{2\phi({\alpha^{\star}})}-1\right]=\frac{\epsilon{\alpha^{\star}}^{3}[\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})+\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})-2\Phi(-{\alpha^{\star}})]}{2\phi({\alpha^{\star}})}+\frac{{\alpha^{\star}}^{2}\left[{\alpha^{\star}}\Phi(-{\alpha^{\star}})-\phi({\alpha^{\star}})\right]}{\phi({\alpha^{\star}})}.$
(112)

By virtue of the Taylor expansion, we can use similar reasoning as for the
expression (110) to arrive at

$\displaystyle\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})+\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})-2\Phi(-{\alpha^{\star}})\sim{\alpha^{\star}}\delta\nu_{0}^{2}\phi({\alpha^{\star}}),$

as $\delta\rightarrow 0^{+}$. Taking this together with the fact that
$\delta{\alpha^{\star}}\sim 2\phi({\alpha^{\star}})$ (cf. (103)) reveals that:
the first term in the decomposition (112) scales as
$\epsilon\nu_{0}^{2}{\alpha^{\star}}^{2}\phi({\alpha^{\star}})$. In addition,
from the equation (124c), the second term in the decomposition (112) scales as
$-1$ — which is therefore the dominant term as
${\alpha^{\star}}\rightarrow\infty.$ We can therefore conclude that

$\displaystyle{\alpha^{\star}}^{2}\left[\frac{\delta{\alpha^{\star}}}{2\phi({\alpha^{\star}})}-1\right]\sim-1\quad\Longrightarrow\quad\frac{2\phi({\alpha^{\star}})}{{\alpha^{\star}}\delta}=1+{\alpha^{\star}}^{-2}+o({\alpha^{\star}}^{-2}).$

As a consequence, we obtain $R_{2}\sim 2{\alpha^{\star}}^{-2}$.

Substituting the limit scalings of $R_{1}$ and $R_{2}$ into the decomposition
(111) yields

$\displaystyle\frac{\delta^{-2}F_{23}-({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}{({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}}\sim-4{\alpha^{\star}}^{-2}.$
(113)

Consequently, the above results on $\Delta_{1}$ and $\Delta_{2}$ taken
collectively with the expression (109) lead to

$\displaystyle\nabla_{\delta}F_{2}=-({\alpha^{\star}}\phi({\alpha^{\star}}))^{-1}\left[1-4{\alpha^{\star}}^{-2}+o({\alpha^{\star}}^{-2})\right].$
(114)

#### Second-order term of $\nabla_{\alpha}F_{2}$.

We are only left to establish the order of $\nabla_{\alpha}F_{2}$. To this
end, re-arranging terms in the expression of $\nabla_{\alpha}F_{2}$ leads to

$\displaystyle\frac{\nabla_{\alpha}F_{2}+2\alpha^{-1}}{\alpha^{-1}}=\underbrace{\frac{\nabla_{\alpha}F_{2}-\delta^{-1}\nabla_{\alpha}F_{23}}{\alpha^{-1}}}_{=:T_{1}}+\underbrace{\frac{\delta^{-1}\nabla_{\alpha}F_{23}+2\alpha^{-1}}{\alpha^{-1}}}_{=:T_{2}}.$

Therefore, it suffices to analyze the limiting order of the two terms $T_{1}$
and $T_{2}$ separately, which shall be done as follows.

  * •

Step 1: Bounding the term $T_{1}$. We characterize the leading term of $T_{1}$
by examining its Taylor expansion with similar argument as in (110).
Specifically, setting $s\coloneqq{\sqrt{\delta}\nu^{\star}}$, we have

$\displaystyle\nabla_{\alpha}F_{2}-\delta^{-1}\nabla_{\alpha}F_{23}=\epsilon\delta^{-1}[f_{2}(s)+f_{2}(-s)-2f_{2}(0)],$

where
$f_{2}(s):=-2\phi({\alpha^{\star}}+s)+2{\alpha^{\star}}\Phi(-{\alpha^{\star}}-s).$
It is straightforward to verify that $f_{2}^{(2)}(0)=2\phi({\alpha^{\star}})$,
and it follows that

$\displaystyle\nabla_{\alpha}F_{2}-\delta^{-1}\nabla_{\alpha}F_{23}\sim\epsilon\delta^{-1}2\phi({\alpha^{\star}})({\sqrt{\delta}\nu^{\star}})^{2}\sim
2\epsilon\nu_{0}^{2}\phi({\alpha^{\star}}).$

  * •

Step 2: Bounding the term $T_{2}$. To calculate the limiting order of $T_{2}$,
we establish the decomposition

$\displaystyle\frac{\delta^{-1}\nabla_{\alpha}F_{23}+2{\alpha^{\star}}^{-1}}{{\alpha^{\star}}^{-1}}=2\frac{2\phi({\alpha^{\star}})}{\delta{\alpha^{\star}}}\left[-\frac{{\alpha^{\star}}\left[{\alpha^{\star}}\phi({\alpha^{\star}})-({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}})\right]}{\phi({\alpha^{\star}})}+\frac{\phi({\alpha^{\star}})-{\alpha^{\star}}\Phi(-{\alpha^{\star}})}{\phi({\alpha^{\star}})}\right].$

As direct consequences of the expressions (124c), (124d) and (103), one can
easily see that

$\displaystyle\frac{{\alpha^{\star}}\left[{\alpha^{\star}}\phi({\alpha^{\star}})-({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}})\right]}{\phi({\alpha^{\star}})}\sim-2{\alpha^{\star}}^{-2};\quad\frac{\phi({\alpha^{\star}})-{\alpha^{\star}}\Phi(-{\alpha^{\star}})}{\phi({\alpha^{\star}})}\sim{\alpha^{\star}}^{-2};\quad\frac{2\phi({\alpha^{\star}})}{\delta{\alpha^{\star}}}\sim
1,$

as $\delta\rightarrow 0^{+}$. Plugging the above relations into the
decomposition of $T_{2}$ yields $T_{2}\sim 6{\alpha^{\star}}^{-2}$.

In view of the results above on $T_{1}$ and $T_{2}$, we can conclude that

$\displaystyle\frac{\nabla_{\alpha}F_{2}+2{\alpha^{\star}}^{-1}}{{\alpha^{\star}}^{-1}}\sim
6{\alpha^{\star}}^{-2}.$ (115)

##### Putting all this together.

Thus far, we have established the limiting order of $\nabla_{\alpha}F_{1}$,
$\nabla_{\delta}F_{1}$, $\nabla_{\delta}F_{2}$ and $\nabla_{\alpha}F_{2}$.
Combining all the above pieces together, it is easy to justify that

$\displaystyle\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}=2{\alpha^{\star}}^{-1}\left[1-4{\alpha^{\star}}^{-2}+o({\alpha^{\star}}^{-2})\right];$
$\displaystyle\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}=2{\alpha^{\star}}^{-1}\left[1-3{\alpha^{\star}}^{-2}+o({\alpha^{\star}}^{-2})\right].$

It immediately suggests that
$\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}=-2{\alpha^{\star}}^{-3}+o({\alpha^{\star}}^{-3})$,
which proves the relation (38a), thus completing the proof of Lemma 1.

###  D.2 Limiting orders of ${\alpha^{\star}}$ and ${\nu^{\star}}$ when
$\delta\rightarrow 0^{+}$: proof of Lemma D.1

In this section, we present the proofs of the four relations in Lemma D.1 in
the sequel.

##### First claim in (103).

Recall that $F_{1}$ is defined as

$\displaystyle F_{1}(\nu,\delta,\alpha)$
$\displaystyle\coloneqq\epsilon\mathbb{P}\left(\big{|}\nu\sqrt{\delta}+Z\big{|}>\alpha\right)+(1-\epsilon)\mathbb{P}\left(\left|Z\right|>\alpha\right)-\delta.$

Since the first two terms are non-negative, when $\delta\rightarrow 0^{+}$,
setting $F_{1}({\nu^{\star}},\delta,{\alpha^{\star}})=0$ leads to

$\displaystyle\mathbb{P}\left(\big{|}{\sqrt{\delta}\nu^{\star}}+Z\big{|}>{\alpha^{\star}}\right)\rightarrow
0;\quad\mathbb{P}\left(\left|Z\right|>{\alpha^{\star}}\right)\rightarrow 0.$

From the second expression, it can be immediately concluded that
$\lim_{\delta\rightarrow 0^{+}}{\alpha^{\star}}=\infty$.

##### Second claim in (103).

In order to study the limiting behavior of $\sqrt{\delta}{\alpha^{\star}}$, we
first make the observations that $0<{\nu^{\star}}\leq M$ as
$M/{\nu^{\star}}={\tau^{\star}}\geq 1$ (see (15a)) and $\Phi$ is a
monotonically increasing function such that

$\displaystyle\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})<\Phi(-{\alpha^{\star}})<\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}}).$

Consequently, $F_{1}({\nu^{\star}},\delta,{\alpha^{\star}})$ can be upper
bounded as

$\displaystyle 0=F_{1}({\nu^{\star}},\delta,{\alpha^{\star}})$
$\displaystyle=\epsilon\left[\Phi(-{\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})+\Phi(-{\alpha^{\star}}-\sqrt{\delta}{\nu^{\star}})\right]+2(1-\epsilon)\Phi(-{\alpha^{\star}})-\delta$
$\displaystyle\leq
2\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})-\delta,$

which in turn suggests

$\displaystyle\Phi(-{\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})\geq\delta/2.$

Apply Lemma E.1 with a little algebra to yield

$\displaystyle
2\geq\frac{\delta}{\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})}\overset{(\mathrm{i})}{\sim}\frac{({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\delta}{\phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})}\overset{(\mathrm{ii})}{\sim}\frac{1}{\sqrt{2\pi}}{\alpha^{\star}}\delta
e^{{\alpha^{\star}}^{2}/2},$

where $(\mathrm{i})$ is a direct consequence of the expression (124b), and
$(\mathrm{ii})$ follows from the observations that
${\alpha^{\star}}\rightarrow\infty$ and ${\sqrt{\delta}\nu^{\star}}\leq
M\sqrt{\delta}\rightarrow 0$ as $\delta\rightarrow 0^{+}$. It therefore
reveals that ${\alpha^{\star}}^{2}\delta=o(1)$, due to the fact that
${\alpha^{\star}}\rightarrow\infty$. Thus, we complete the proof of the second
claim.

##### Third claim in (103).

With the limiting values of ${\alpha^{\star}}$ and
${\alpha^{\star}}\sqrt{\delta}$ in place, we are now ready to characterize the
limiting orders of $\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})$ and
$\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})$. To this end, we first
recognize the following relation

$\displaystyle\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\sim\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})\sim\Phi(-{\alpha^{\star}})\sim\frac{\phi({\alpha^{\star}})}{{\alpha^{\star}}},$
(116)

when $\delta\to 0^{+}$, followed by the property
${\alpha^{\star}}{\sqrt{\delta}\nu^{\star}}\leq
M{\alpha^{\star}}\sqrt{\delta}=o(1)$. It immediately follows that

$\displaystyle\lim_{\delta\rightarrow
0^{+}}\frac{\delta{\alpha^{\star}}}{\phi({\alpha^{\star}})}$
$\displaystyle=\lim_{\delta\rightarrow
0^{+}}\frac{\left[\epsilon\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})+\epsilon\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})+2(1-\epsilon)\Phi(-{\alpha^{\star}})\right]{\alpha^{\star}}}{\phi({\alpha^{\star}})}$
$\displaystyle=\epsilon+\epsilon+2(1-\epsilon)=2,$

where the first equality comes from property
$F_{1}({\nu^{\star}},\delta,{\alpha^{\star}})=0$. We thus finish the proof of
the third claim.

##### Fourth claim in (103).

In order to understand the limit of ${\nu^{\star}}$ as $\delta\rightarrow
0^{+}$, we resort to the decomposition (98) of $F_{2}$, where

$\displaystyle
F_{2}=\frac{\nu^{2}}{M^{2}}-1+\epsilon\delta^{-1}F_{22}+(1-\epsilon)\delta^{-1}F_{23}.$
(117)

We claim that it satisfies

$\displaystyle
0=F_{2}({\nu^{\star}},\delta,{\alpha^{\star}})=\frac{{\nu^{\star}}^{2}}{M^{2}}-1+\epsilon{\nu^{\star}}^{2}+o(1),\quad\text{as
}~{}\delta\rightarrow 0^{+}.$ (118)

Taking the above result as given for the moment, one can conclude that
$\lim_{\delta\rightarrow 0^{+}}{\nu^{\star}}=\nu_{0}$ as desired, where
$\nu_{0}$ is defined as $\nu_{0}\coloneqq M/\tau_{0}$ and
$\tau_{0}^{2}=1+\epsilon M^{2}$ (cf. the expression (35)).

Now it remains to establish the crucial relation (118). To this end, the idea
is to characterize the limiting order of each term in the expression (117) in
terms of ${\nu^{\star}}$, as $\delta\rightarrow 0^{+}$. Let us start with the
quantity $\delta^{-1}F_{23}$. Firstly, invoking the equation (124d) from Lemma
E.1, we know that $F_{23}\sim 4{\alpha^{\star}}^{-3}\phi({\alpha^{\star}})$.
As a result, one can write

$\displaystyle\delta^{-1}F_{23}\sim
4\delta^{-1}{\alpha^{\star}}^{-3}\phi({\alpha^{\star}})\sim
2{\alpha^{\star}}^{-2},$

where the last relation uses the third claim in (103) that we just proved,
namely, $\lim_{\delta\rightarrow
0^{+}}\frac{\delta{\alpha^{\star}}}{\phi({\alpha^{\star}})}=2$. Since
${\alpha^{\star}}\rightarrow+\infty$ as $\delta\rightarrow 0^{+}$, we can
ensure that $\delta^{-1}F_{23}=o(1)$ as $\delta\rightarrow 0^{+}$.

When it comes to the terms in $\delta^{-1}F_{22}$, we find it useful to define
the following function

$g(x)\coloneqq\phi(x)-x\Phi(-x).$ (119)

One shall then conclude from the expression (124c) that $g(x)\sim
x^{-2}\phi(x)$ when $x\rightarrow\infty$. With this piece of notation, we can
rewrite $F_{22}$ as

$\displaystyle
F_{22}(\nu,\delta,\alpha)=-(\alpha-\sqrt{\delta}\nu)g(\alpha+\sqrt{\delta}\nu)-(\alpha+\sqrt{\delta}\nu)g(\alpha-\sqrt{\delta}\nu)+\left[\Phi(-\alpha-\sqrt{\delta}\nu)+\Phi(-\alpha+\sqrt{\delta}\nu)\right]+\delta\nu^{2}.$

Let us examine each term on the right-hand side above respectively. For the
terms involving $g$, again applying $\lim_{\delta\rightarrow
0^{+}}\frac{\delta{\alpha^{\star}}}{\phi({\alpha^{\star}})}=2$ gives

$\displaystyle\frac{({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})g({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})}{\delta}\sim\frac{{\alpha^{\star}}^{-1}\phi({\alpha^{\star}})}{\delta}\sim\frac{1}{2};\quad\frac{({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})g({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})}{\delta}\sim\frac{{\alpha^{\star}}^{-1}\phi({\alpha^{\star}})}{\delta}\sim\frac{1}{2}.$

In addition, for the terms involving the function $\Phi$, by the sandwich
relation (116), we arrive at

$\displaystyle\Phi(-\alpha-\sqrt{\delta}\nu)+\Phi(-\alpha+\sqrt{\delta}\nu)\sim\delta.$

Plugging the above relations into $F_{22}$ leads to
$\delta^{-1}F_{22}({\nu^{\star}},\delta,{\alpha^{\star}})=o(1)+{\nu^{\star}}^{2}$,
as $\delta\rightarrow 0^{+}$.

Combining the conclusions about $\delta^{-1}F_{22}$ and $\delta^{-1}F_{23}$,
we successfully establish the equation (118), thus finishing the proof of the
fourth claim.

###  D.3 Limiting orders of the partial derivatives: proof of Lemma D.2

We are now positioned to study the limiting orders of the partial derivatives
of $F_{1}$ and $F_{2}$ stated in Section D.1.1. This will be accomplished by
taking advantage of Lemma D.1.

##### Properties concerning $F_{1}$ in (104).

Recognizing the fact that $\sqrt{\delta}{\alpha^{\star}}\rightarrow 0$ and
${\nu^{\star}}\rightarrow\nu_{0}$ as $\delta\rightarrow 0^{+}$ (as in Lemma
D.1), we obtain that
$\phi({\alpha^{\star}}-\sqrt{\delta}{\nu^{\star}})\sim\phi({\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})\sim\phi({\alpha^{\star}})$.
Combining this with the explicit expressions of derivatives of $F_{1}$ (cf.
(100)), we immediately obtain
$\nabla_{\alpha}F_{1}\sim-2\phi({\alpha^{\star}})$.

Further, taking Lemma D.1 collectively with the relation (107) where

$\displaystyle\frac{\phi({\alpha^{\star}}-\sqrt{\delta}{\nu^{\star}})-\phi({\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})}{\sqrt{\delta}{\alpha^{\star}}\phi({\alpha^{\star}}){\nu^{\star}}}\sim
2,\quad\delta\rightarrow 0^{+},$

we can directly see that

$\displaystyle\nabla_{\nu}F_{1}\sim
2\epsilon{\nu^{\star}}\delta{\alpha^{\star}}\phi({\alpha^{\star}})\sim
4\epsilon\nu_{0}\phi^{2}({\alpha^{\star}})$
$\displaystyle\frac{\epsilon{\nu^{\star}}}{2\sqrt{\delta}}\left[\phi({\alpha^{\star}}-\sqrt{\delta}{\nu^{\star}})-\phi({\alpha^{\star}}+\sqrt{\delta}{\nu^{\star}})\right]\sim\epsilon\nu_{0}^{2}{\alpha^{\star}}\phi({\alpha^{\star}})=o(1)$

as $\delta\rightarrow 0^{+}$. From the second relation, one can conclude that
$\nabla_{\delta}F_{1}\sim-1$, and thus complete the proof of expression (104).

##### Properties concerning $F_{2}$ in (105).

Let us turn to the analysis of the partial derivatives related to $F_{2}$. In
what follows, we shall check the limiting orders of $\nabla_{\alpha}F_{2}$,
$\nabla_{\delta}F_{2}$ and $\nabla_{\nu}F_{2}$ respectively, with the
assistance of Lemma E.1 and Lemma D.1.

  * •

Limiting order of $\nabla_{\alpha}F_{2}$. It is useful to recall the
decomposition as in expression (101), where

$\displaystyle\nabla_{\alpha}F_{2}=\epsilon\delta^{-1}\nabla_{\alpha}F_{22}+(1-\epsilon)\delta^{-1}\nabla_{\alpha}F_{23}.$

Now we are only left to analyze each term on the right-hand side of the above
relation separately. Firstly, the relation (124c) directly yields
$\nabla_{\alpha}F_{23}\sim-4{\alpha^{\star}}^{-2}\phi({\alpha^{\star}})$;
further recognizing that $\delta\sim
2{\alpha^{\star}}^{-1}\phi({\alpha^{\star}})$ (cf. (124b)), we have
$\delta^{-1}\nabla_{\alpha}F_{23}\sim-2{\alpha^{\star}}^{-1}$.

To analyze the quantity $\delta^{-1}\nabla_{\alpha}F_{22}$, we again invoke
the definition of function $g$ in (119) to obtain the decomposition

$\displaystyle\nabla_{\alpha}F_{22}(\nu,\delta,\alpha)=-2g(\alpha+\sqrt{\delta}\nu)-2g(\alpha-\sqrt{\delta}\nu)+2\sqrt{\delta}\nu\left[\Phi(-\alpha-\sqrt{\delta}\nu)-\Phi(-\alpha+\sqrt{\delta}\nu)\right].$

Taking this together with the facts that $g(x)\sim x^{-2}\phi(x)$ when
$x\rightarrow\infty$, and
$\phi({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})\sim\phi({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\sim\phi({\alpha^{\star}})$,
leads to

$\displaystyle g({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})\sim
g({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\sim{\alpha^{\star}}^{-2}\phi({\alpha^{\star}})\qquad\text{
as }~{}\delta\rightarrow 0^{+}.$

Finally, we claim that the terms involving $\Phi$ are negligible. This can be
shown by combining the results in Lemma E.1 with the equality (107).
Specifically, one has

$\displaystyle
2{\sqrt{\delta}\nu^{\star}}\left[\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})-\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\right]\sim
4\phi({\alpha^{\star}})=o(1),$

where the last step uses $\phi({\alpha^{\star}})=o(1)$ as $\delta\rightarrow
0^{+}$. Putting these pieces together gives

$\displaystyle\delta^{-1}\nabla_{\alpha}F_{22}\sim-4\delta^{-1}{\alpha^{\star}}^{-2}\phi({\alpha^{\star}})\sim-2{\alpha^{\star}}^{-1}.$

As a result, one immediately realizes that
$\nabla_{\alpha}F_{2}\sim-2{\alpha^{\star}}^{-1}$.

  * •

Limiting order of $\nabla_{\delta}F_{2}$. First recall that
$\nabla_{\delta}F_{2}=-\epsilon\delta^{-2}\left[F_{22}-\delta\nabla_{\delta}F_{22}\right]-(1-\epsilon)\delta^{-2}F_{23}.$
As a direct consequence of the relation (124d), one has $F_{23}\sim
4{\alpha^{\star}}^{-3}\phi({\alpha^{\star}})$. When it comes to the first
term, re-arranging terms in the expression of $F_{22}$ leads to

$\displaystyle F_{22}-\delta\nabla_{\delta}F_{22}=$
$\displaystyle-({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\phi({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})-({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})\phi({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})$
$\displaystyle+({\alpha^{\star}}^{2}+1)\left[\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})+\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})\right].$

Applying (124d) again at ${\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}}$ and
${\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}}$ gives

$\displaystyle({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\phi({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})+({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\sim-2{\alpha^{\star}}^{-3}\phi({\alpha^{\star}}),$
$\displaystyle({\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})\phi({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})+({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}}+{\sqrt{\delta}\nu^{\star}})\sim-2{\alpha^{\star}}^{-3}\phi({\alpha^{\star}}),$

which together with $\delta\sim 2{\alpha^{\star}}^{-1}\phi({\alpha^{\star}})$
(cf. (124b)) directly validate $\lim_{\delta\rightarrow
0^{+}}{\alpha^{\star}}\phi({\alpha^{\star}})\nabla_{\delta}F_{2}=-1.$

  * •

Limiting order of $\nabla_{\nu}F_{2}$. It is helpful to recall the expression
$\nabla_{\nu}F_{2}=2M^{-2}{\nu^{\star}}+\epsilon\delta^{-1}\nabla_{\nu}F_{22}$.
With Lemma D.1 in place, one has

$\displaystyle\delta^{-1}\nabla_{\nu}F_{22}=2{\nu^{\star}}\left[\Phi({\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})-\Phi(-{\alpha^{\star}}-{\sqrt{\delta}\nu^{\star}})\right]\sim
2\nu_{0}.$

As a result, we have $\nabla_{\nu}F_{2}\sim
2(M^{-2}+\epsilon)\nu_{0}=2/\nu_{0}$, where the last equality follows from the
definition of $\nu_{0}$ as $\nu_{0}\coloneqq M/\tau_{0}$ with
$\tau_{0}^{2}=1+\epsilon M^{2}$ according to the expression (35).

Thus, we complete the proof of Lemma D.2.

###  D.4 Proof of Lemma 3

We divide this proof into two parts. In the first part, we characterize the
limiting values of ${\alpha^{\star}}$ and ${\nu^{\star}}/M$ as
$\epsilon\rightarrow 0$ to establish (42); in the second part, we proceed by
calculating the limiting orders of each quantity in the expression (3.2.2) for
${\nu^{\star}}^{\prime}(\delta_{0})/M$.

##### Step 1: limit of ${\alpha^{\star}}$ and ${\nu^{\star}}/M$ as
$\epsilon\rightarrow 0$.

  * •

To establish the first statement of the expression (42), we make the
observation that: having $F_{1}({\nu^{\star}},\delta_{0},{\alpha^{\star}})=0$
yields

$\displaystyle\epsilon\left[\Phi(-{\alpha^{\star}}+\sqrt{\delta_{0}}{\nu^{\star}})+\Phi(-{\alpha^{\star}}-\sqrt{\delta_{0}}{\nu^{\star}})-2\Phi(-{\alpha^{\star}})\right]=\delta_{0}-2\Phi(-{\alpha^{\star}}),$

by recalling the expression of $F_{1}$ in (97). It then immediately follows
that

$\displaystyle\left|\delta_{0}-2\Phi(-{\alpha^{\star}})\right|\leq 4\epsilon.$

When $\epsilon\rightarrow 0$, we know that
$2\Phi(-{\alpha^{\star}})\rightarrow\delta_{0}$, or equivalently,
${\alpha^{\star}}\rightarrow-\Phi^{-1}(\delta_{0}/2)=:\alpha_{0}$.

  * •

In the hope of proving the second statement of the expression (42), we find it
helpful to recall the decomposition
$F_{2}=F_{21}+\epsilon\delta^{-1}F_{22}+(1-\epsilon)\delta^{-1}F_{23}.$ From
$F_{2}({\nu^{\star}},\delta_{0},{\alpha^{\star}})=0$, the following relation
holds true

$\displaystyle\left|\frac{{\nu^{\star}}^{2}}{M^{2}}-1+\delta_{0}^{-1}F_{23}\right|\leq\epsilon\delta_{0}^{-1}\left|F_{22}-F_{23}\right|.$
(120)

Below we shall demonstrate the fact that $|F_{22}-F_{23}|$ is upper bounded by
some constant that only depends on $\delta_{0}$, which means when
$\epsilon\rightarrow 0$, the right-hand side of the inequality (120) vanishes
to zero. In other words, one can conclude

$\displaystyle\frac{{\nu^{\star}}}{M}\rightarrow\sqrt{1-\delta_{0}^{-1}F_{23}}\rightarrow\sqrt{1-2\delta_{0}^{-1}[-\alpha_{0}\phi(\alpha_{0})+(\alpha_{0}^{2}+1)\Phi(-\alpha_{0})]},$

where the last step follows since
$F_{23}({\nu^{\star}},\delta,{\alpha^{\star}})=2[-{\alpha^{\star}}\phi({\alpha^{\star}})+({\alpha^{\star}}^{2}+1)\Phi(-{\alpha^{\star}})].$

Therefore, it boils down to controlling $|F_{22}-F_{23}|$. From now on, let us
consider the scenario when ${\alpha^{\star}}<2\alpha_{0}$. Recognizing that
${\alpha^{\star}}\rightarrow\alpha_{0}>0$ as $\epsilon\rightarrow 0$, one sees
that ${\alpha^{\star}}<2\alpha_{0}$ holds as long as $\epsilon$ is
sufficiently small. By virtual of the expression (99), we know that
$F_{22}(0,\delta_{0},{\alpha^{\star}})=F_{23}({\nu^{\star}},\delta_{0},{\alpha^{\star}})$,
and

$\displaystyle\nabla_{\nu}F_{22}(\nu,\delta_{0},{\alpha^{\star}})=2\nu\delta_{0}\left[\Phi({\alpha^{\star}}-\sqrt{\delta_{0}}\nu)-\Phi(-{\alpha^{\star}}-\sqrt{\delta_{0}}\nu)\right],$

which combined with direct calculation gives

$\displaystyle
0<\nabla_{\nu}F_{22}(\nu,\delta_{0},{\alpha^{\star}})<2\nu\delta_{0}\Phi(2\alpha_{0}-\sqrt{\delta_{0}}\nu).$
(121)

With the help of the above relation, we can further obtain

$\displaystyle 0\leq
F_{22}-F_{23}=\int_{0}^{{\nu^{\star}}}\nabla_{\nu}F_{22}(\nu,\delta_{0},{\alpha^{\star}})\mathrm{d}\nu$
$\displaystyle\leq\int_{0}^{{\nu^{\star}}}2\nu\delta_{0}\Phi(2\alpha_{0}-\sqrt{\delta_{0}}\nu)\mathrm{d}\nu$
$\displaystyle=2\int_{0}^{{\nu^{\star}}\sqrt{\delta_{0}}}\nu\Phi(2\alpha_{0}-\nu)\mathrm{d}\nu\leq
2\int_{0}^{+\infty}\nu\Phi(2\alpha_{0}-\nu)\mathrm{d}\nu\leq C_{\delta_{0}},$

where $C_{\delta_{0}}$ is a constant that only depends on $\delta_{0}$.
Therefore, we complete the proof of the second statement in (42).

##### Step 2: analysis of quantities in (3.2.2).

Equipped with the limiting values ${\nu^{\star}}$ and ${\alpha^{\star}}$, we
are ready to analyze those terms that appear in the expression (3.2.2). Akin
to the previous part, we also assume without loss of generality that
${\alpha^{\star}}<2\alpha_{0}$ throughout this part.

  * •

Limiting order of the numerator. Let us first consider the numerator
$\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}$,
where the partial derivatives are evaluated at
$({\nu^{\star}},\delta,{\alpha^{\star}}).$ With $|\phi(x)|\leq 1$ and
${\nu^{\star}}\leq M$ in mind, by virtue of the equations (100), we can easily
verify that

$\displaystyle\left|\nabla_{\delta}F_{1}(\nu,\delta_{0},\alpha)+1\right|\leq\frac{M}{\sqrt{\delta_{0}}}\epsilon=\sqrt{\frac{\text{SNR}\cdot\epsilon}{\delta_{0}}};\quad\left|\nabla_{\alpha}F_{1}(\nu,\delta_{0},\alpha)+2\phi(\alpha)\right|\leq
4\epsilon$

with SNR defined in equation (12), which reveals that
$\nabla_{\delta}F_{1}\sim-1$ and
$\nabla_{\alpha}F_{1}\sim-2\phi({\alpha^{\star}})$ as $\epsilon\to 0.$

We now turn to the $F_{2}$-related quantities. Invoking their explicit
expressions as derived in Section D.1.1 yields

$\displaystyle\left|\nabla_{\alpha}F_{2}-\delta_{0}^{-1}\nabla_{\alpha}F_{23}\right|$
$\displaystyle=\epsilon\delta_{0}^{-1}\left|\nabla_{\alpha}F_{22}-\nabla_{\alpha}F_{23}\right|;$
(122a) $\displaystyle\left|\nabla_{\delta}F_{2}+\delta_{0}^{-2}F_{23}\right|$
$\displaystyle=\epsilon\delta_{0}^{-2}\left|F_{23}-F_{22}+\delta_{0}\nabla_{\delta}F_{22}\right|.$
(122b)

We claim that the right-hand sides of both of the above equations vanish as
$\epsilon\to 0.$ Taking these as given for the moment, we have
$\nabla_{\alpha}F_{2}\sim\delta_{0}^{-1}\nabla_{\alpha}F_{23}$ and
$\nabla_{\delta}F_{2}\sim-\delta_{0}^{-2}F_{23}$ which further ensure that

$\displaystyle\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}$
$\displaystyle~{}\rightarrow~{}2\delta_{0}^{-2}\phi(\alpha_{0})F_{23}+\delta_{0}^{-1}\nabla_{\alpha}F_{23}$
$\displaystyle~{}\rightarrow~{}2\delta_{0}^{-2}{\phi(\alpha_{0})}\left[-2\alpha_{0}\phi(\alpha_{0})+(\alpha_{0}^{2}+1)\delta_{0}\right]-2\delta_{0}^{-1}\left[2\phi(\alpha_{0})-\alpha_{0}\delta_{0}\right],$

as claimed in the expression (43a). Here, the last step uses
$\alpha_{0}\coloneqq-\Phi^{-1}(\delta_{0}/2)$. For any $0<\delta_{0}<1$, the
limiting value is a negative number, due to the basic relation

$\displaystyle\Phi(-\alpha_{0})\in\left[\phi(\alpha_{0})\bigg{(}\frac{1}{\alpha_{0}}-\frac{1}{\alpha_{0}^{3}}\bigg{)},~{}\phi(\alpha_{0})\bigg{(}\frac{1}{\alpha_{0}}-\frac{1}{\alpha_{0}^{3}}+\frac{1}{\alpha_{0}^{5}}\bigg{)}\right].$

##### Analysis of the expressions (122a) and (122b).

Combining $|\phi(x)|\leq 1$, $|\Phi(x)|\leq 1$ with the expressions of
$\nabla_{\alpha}F_{22}$ and $\nabla_{\alpha}F_{23}$ in Section D.1.1, one can
easily see that

$\displaystyle\left|\nabla_{\alpha}F_{22}\right|\leq 4(1+{\alpha^{\star}})\leq
8(1+\alpha_{0})\qquad\text{and }~{}\left|\nabla_{\alpha}F_{23}\right|\leq
4(1+{\alpha^{\star}})\leq 8(1+\alpha_{0}),$

given ${\alpha^{\star}}<2\alpha_{0}$. It is thus clear that (122a) is
negligible when $\epsilon\to 0$.

As for the relation (122b), note that we have shown in the previous part that
$|F_{23}-F_{22}|\leq C_{\delta_{0}}$, where $C_{\delta_{0}}$ only depends on
$\delta_{0}$. Additionally, it is clear that

$\displaystyle 0\leq\nabla_{\delta}F_{22}$
$\displaystyle={\nu^{\star}}^{2}\left[\Phi({\alpha^{\star}}-{\nu^{\star}})-\Phi(-{\alpha^{\star}}-{\nu^{\star}})\right]$
$\displaystyle\leq{\nu^{\star}}^{2}\Phi(2\alpha_{0}-\sqrt{\delta_{0}}{\nu^{\star}})\leq\max_{\nu\geq
0}\left\\{\nu^{2}\Phi(2\alpha_{0}-\sqrt{\delta_{0}}\nu)\right\\}=:C_{\delta_{0}}^{\prime}.$

Thus we conclude that $|\nabla_{\delta}F_{22}|\leq C_{\delta_{0}}^{\prime}$.
Putting the above arguments together leads to the fact that
$\left|F_{23}-F_{22}+\delta_{0}\nabla_{\delta}F_{22}\right|$ is bounded by a
universal constant determined by $\delta_{0}$ and is thus negligible when
$\epsilon\to 0$.

  * •

Limiting order of the denominator. It remains to study the denominator
$M(\nabla_{\nu}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\nu}F_{1})$.
To begin with, from the previous analysis, it is seen that
$\nabla_{\alpha}F_{2}$ scales as
$-2\delta_{0}^{-1}\left[2\phi(\alpha_{0})-\alpha_{0}\delta_{0}\right]$ and
$\nabla_{\alpha}F_{1}$ as $-2\phi(\alpha_{0})$ when taking
$\epsilon\rightarrow 0$. In what follows, we shall analyze
$M\nabla_{\nu}F_{2}$ and $M\nabla_{\nu}F_{1}$ separately. For these two
quantities, the following inequalities hold true

$\displaystyle\left|M\nabla_{\nu}F_{1}\right|$
$\displaystyle=\sqrt{\text{SNR}\cdot\delta_{0}\epsilon}\left|\phi({\alpha^{\star}}-\sqrt{\delta_{0}}{\nu^{\star}})-\phi({\alpha^{\star}}+\sqrt{\delta_{0}}{\nu^{\star}})\right|\leq
2\sqrt{\text{SNR}\cdot\delta_{0}\epsilon}$

and

$\displaystyle\left|M\nabla_{\nu}F_{2}-2\frac{{\nu^{\star}}}{M}\right|=\sqrt{\text{SNR}\cdot\delta_{0}^{-2}\epsilon}\left|\nabla_{\nu}F_{22}\right|$
$\displaystyle=2\sqrt{\text{SNR}\cdot\epsilon}{\nu^{\star}}\left[\Phi({\alpha^{\star}}-\sqrt{\delta_{0}}{\nu^{\star}})-\Phi(-{\alpha^{\star}}-\sqrt{\delta_{0}}{\nu^{\star}})\right]$
$\displaystyle\leq
2\sqrt{\text{SNR}\cdot\epsilon}{\nu^{\star}}\Phi(2\alpha_{0}-\sqrt{\delta_{0}}{\nu^{\star}})\leq
2\sqrt{\text{SNR}\cdot\epsilon}C_{\delta_{0}}^{\prime\prime},$

with $C_{\delta_{0}}^{\prime\prime}\coloneqq\\{\max_{\nu\geq
0}\nu\Phi(2\alpha_{0}-\sqrt{\delta_{0}}\nu)\\}$. Taken these collectively, as
$\epsilon\rightarrow 0$, we achieve

$\displaystyle
M(\nabla_{\nu}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\nu}F_{1})$
$\displaystyle\rightarrow-4\phi(\alpha_{0})\frac{{\nu^{\star}}}{M}\rightarrow-4\phi(\alpha_{0})\sqrt{1-2\delta_{0}^{-1}[-\alpha_{0}\phi(\alpha_{0})+(\alpha_{0}^{2}+1)\Phi(-\alpha_{0})]},$

where the last step relies on the relation (42).

##### Summary.

Substituting the above parts on the numerator and the denominator into the
expression (3.2.2), we conclude that when $\epsilon\rightarrow 0$, one has

$\displaystyle\lim_{\epsilon\rightarrow
0}\frac{{\nu^{\star}}^{\prime}(\delta_{0})}{M}<0,$

which further indicates that the solution of ${\nu^{\star}}/M$ decreases with
$\delta$ near $\forall\delta_{0}\in(0,1)$, as long as $\epsilon$ is below a
certain threshold.

##  Appendix E Auxiliary lemmas and details

###  E.1 An example satisfying Assumption 1

######  Example 1.

Let $\\{\lambda_{t}\\}$ be a piece-wise constant sequence with

$\displaystyle\lambda_{t}=\mu_{k},\qquad\text{for }S_{k-1}+1\leq t\leq S_{k},$
(123)

where the length of each piece $s_{k}\coloneqq S_{k}-S_{k-1}$ and $S_{0}$ is
set to be $0.$ Further choose $\mu_{k}=1/\max\left\\{\log k,1\right\\}$ and
$\Lambda_{S_{k}}=\sum_{i=1}^{S_{k}}\lambda_{i}=k^{3}$, $k\geq 1$.

###### Proof.

Let us now verify that this sequence satisfies Assumption 1. It is
straightforward to validate the other inequalities, so we only present the
proof for the second relation of (25). In this case, when $S_{k}\leq t\leq
S_{k+1}-1$, direct calculations yield

$\displaystyle
l_{t}=\sum_{s=1}^{t}|\lambda_{s}-\lambda_{s+1}|\exp\left\\{-c[\Lambda_{t}-\Lambda_{s}]\right\\}$
$\displaystyle=\sum_{j=1}^{k}|\mu_{j}-\mu_{j+1}|\exp\left\\{-c[\Lambda_{t}-\Lambda_{S_{j}}]\right\\}$
$\displaystyle\leq\sum_{j=1}^{k}|\mu_{j}-\mu_{j+1}|\exp\left\\{-ck^{3}+cj^{3}\right\\}\exp\left\\{-c(t-S_{k})\mu_{k}\right\\}.$

Further, it is easy to verify that $|\mu_{j}-\mu_{j+1}|\sim 1/(j\log^{2}j)$,
and as a result,

$\displaystyle\sqrt{l_{t}}\lesssim\exp\left\\{-\frac{c\mu_{k}(t-S_{k})}{2}\right\\}\exp\left\\{-\frac{ck^{3}}{2}\right\\}\sqrt{\sum_{j=1}^{k}\frac{1}{j\log^{2}j}\exp\left\\{cj^{3}\right\\}}\overset{\text{(}*)}{\lesssim}\exp\left\\{-\frac{c\mu_{k}(t-S_{k})}{2}\right\\}\frac{1}{k^{3/2}\log
k},$

where $\text{(}*)$ follows from the fact that

$\displaystyle\int_{1}^{k}\frac{1}{x\log^{2}x}\exp(cx^{3})\mathrm{d}x\lesssim\frac{1}{k^{3}\log^{2}k}\exp(ck^{3}).$

Finally, we arrive at

$\displaystyle\sum_{t=1}^{+\infty}\sqrt{l_{t}}$
$\displaystyle\leq\sum_{k=1}^{+\infty}\left[\sum_{t=S_{k}}^{S_{k+1}-1}\exp\left\\{-\frac{c\mu_{k}(t-S_{k})}{2}\right\\}\right]\frac{1}{k^{3/2}\log
k}\lesssim\sum_{k=1}^{+\infty}\frac{1}{1-\exp(-c/2\mu_{k})}\frac{1}{k^{3/2}\log
k}\lesssim\sum_{k=1}^{+\infty}\frac{1}{k^{3/2}}<\infty.$

∎

###  E.2 Auxiliary lemma for Gaussian distributions

We collect some useful expressions about the standard Gaussian distribution,
which shall be used multiple times in the proof of Section D.

######  Lemma E.1.

The density function and cumulative density function $\phi(\cdot)$ and
$\Phi(\cdot)$ of the standard Gaussian distribution obey the following
relations:

$\displaystyle\int_{b}^{\infty}(z-a)^{2}\phi(z)\mathrm{d}z=(b-2a)\phi(b)+(a^{2}+1)[1-\Phi(b)];$
(124a)
$\displaystyle\lim_{\alpha\rightarrow+\infty}\frac{\alpha\Phi(-\alpha)}{\phi(\alpha)}=1;$
(124b)
$\displaystyle\lim_{\alpha\rightarrow+\infty}\frac{\alpha^{2}\left[\phi(\alpha)-\alpha\Phi(-\alpha)\right]}{\phi(\alpha)}=1;$
(124c)
$\displaystyle\lim_{\alpha\rightarrow+\infty}\frac{\alpha^{3}\left[\alpha\phi(\alpha)-(\alpha^{2}+1)\Phi(-\alpha)\right]}{\phi(\alpha)}=-2.$
(124d)

###### Proof of Lemma E.1..

To verify the first expression, direct calculations yield

$\displaystyle\int_{b}^{\infty}(z-a)^{2}\phi(z)\mathrm{d}z$
$\displaystyle=\int_{b}^{\infty}z^{2}\phi(z)\mathrm{d}z-2a\int_{b}^{\infty}z\phi(z)\mathrm{d}z+a^{2}\int_{b}^{\infty}\phi(z)\mathrm{d}z$
$\displaystyle=-\int_{b}^{\infty}z\mathrm{d}\phi(z)+2a\int_{b}^{\infty}\mathrm{d}\phi(z)+a^{2}\int_{b}^{\infty}\mathrm{d}\Phi(z)$
$\displaystyle=-\left[-b\phi(b)-\int_{b}^{\infty}\phi(z)\mathrm{d}z\right]-2a\phi(b)+a^{2}\left[1-\Phi(b)\right]$
$\displaystyle=(b-2a)\phi(b)+(a^{2}+1)[1-\Phi(b)].$

The last three equations can be verified similarly by use of L’Hôpital’s rule;
as an illustration, we provide the proof of the last equation here. By taking