d_{0}}$ $\displaystyle\leq C_{k}\left(2\delta+\mathds{1}_{d<X\leq
d_{0}}+\mathds{1}_{d_{0}<X\leq d}\right)$ $\displaystyle\leq
2C_{k}\left(2\delta\vee\mathds{1}_{d<X\leq d_{0}}+\mathds{1}_{d_{0}<X\leq
d}\right):=F_{\delta}(X,\xi)$

Hence the $L_{2}(P)$ norm of the envelope function:

$\sqrt{PF_{\delta}^{2}}\leq
2C_{k}\left(2\delta\vee\sqrt{\mathbb{P}\left(d_{0}<X<d\right)+\mathbb{P}\left(d<X<d_{0}\right)}\right)\leq
4C_{k}\delta:=\phi_{n}(\delta)\,.$

Hence an application of Theorem 3.2.5 of [29] yields $\sqrt{n}\
d\left(\hat{\theta},\theta_{0}\right)=O_{p}(1)$, which completes the proof.

##### Asymptotic distribution:

In the final paragraph we establish the asymptotic distribution of
$\sqrt{n}\left(\hat{\alpha}-\alpha_{0}\right),\sqrt{n}\left(\hat{\beta}-\beta_{0}\right)$
and $n\left(\hat{d}-d_{0}\right)$. Towards that end, we largely follow the
approach of Subsection 14.5.1 of [17]. For any
$\mathbf{h}:=(h_{1},h_{2},h_{3})\in\mathbb{R}^{3}$ define a paramter vector
$\theta_{n,\mathbf{h}}=\alpha_{0}+\frac{h_{1}}{\sqrt{n}},\beta_{0}+\frac{h_{2}}{\sqrt{n}},d_{0}+\frac{h_{3}}{n}$.
Define a stochastic process $\mathbb{Q}_{n}$ on $\mathbb{R}^{3}$ as:

$\displaystyle\mathbb{Q}_{n}(h_{1},h_{2},h_{3})$
$\displaystyle=n\times\mathbb{P}_{n}\left(f_{\theta_{n,\mathbf{h}}}-f_{\theta_{0}}\right)$
$\displaystyle=\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{X_{i}\leq
d_{0}\wedge d}$
$\displaystyle\qquad+\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+\alpha_{0}-\beta_{0}-\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{d_{0}+\frac{h_{3}}{n}<X_{i}\leq
d_{0}}$
$\displaystyle\qquad\qquad+\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+\beta_{0}-\alpha_{0}-\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad\qquad+\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{X_{i}>d\vee
d_{0}}$
$\displaystyle:=\mathbb{Q}_{n,1}(\mathbf{h})+\mathbb{Q}_{n,2}(\mathbf{h})+\mathbb{Q}_{n,3}(\mathbf{h})+\mathbb{Q}_{n,4}(\mathbf{h})\,.$

It is immediate from the definition of $\mathbb{Q}_{n}(\mathbf{h})$ that:

$\widehat{\mathbf{h}}_{n}:=\left(\sqrt{n}\left(\hat{\alpha}-\alpha_{0}\right),\sqrt{n}\left(\hat{\beta}-\beta_{0}\right),n\left(\hat{d}-d_{0}\right)\right)=\text{mid
argmin}_{\mathbf{h}\in\mathbb{R}^{3}}\mathbb{Q}_{n}(\mathbf{h})\,.$

We next show that there exist a stochastic process $\mathbb{Q}$ on
$\mathbb{R}^{3}$ such that for any compact rectangle $\mathbb{I}=I_{1}\times
I_{2}\times I_{3}\subset\mathbb{R}^{3}$:

$\mathbb{Q}_{n}|_{\mathbb{I}}\overset{\mathscr{L}}{\implies}\mathbb{Q}|_{\mathbb{I}}\,.$

where the process $\mathbb{Q}$ is defined as:

$\displaystyle\mathbb{Q}(\mathbf{h})$
$\displaystyle=\left(h_{1}\sigma_{k}\sqrt{F_{X}(d_{0})}\times
Z_{1}+\frac{h_{1}^{2}}{2}\mu_{k}F_{X}(d_{0})\right)$ $\displaystyle\hskip
50.00008pt+\left(h_{2}\sigma_{k}\sqrt{\bar{F}_{X}(d_{0})}\times
Z_{2}+\frac{h_{2}^{2}}{2}\mu_{k}\bar{F}_{X}(d_{0})\right)$
$\displaystyle\hskip
100.00015pt+\text{CPP}\left(\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i}),f_{X}(\theta_{0})\right)\,.$

with $Z_{1},Z_{2}\overset{i.i.d}{\sim}\mathcal{N}(0,1)$ and CPP is (as defined
in the main paper) compound Poisson process. Note that the stochastic process
$\mathbb{Q}_{n}$ is continuous with respect to its first two co-ordinates and
cadlag (right continuous with left limit) with respect to its third co-
ordinate. Hence to establish the convergence of
$\left\\{\mathbb{Q}_{n}|_{\mathbb{I}}\right\\}_{n\in\mathbb{N}}$ we need to
use Skorohod topology. We mainly use Theorem 13.5 of [7] to establish the
convergence result. Towards that end, define:

$\displaystyle\tilde{\xi}_{i,h_{1}}$
$\displaystyle=\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)-\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\right]$
$\displaystyle\tilde{\xi}_{i,h_{2}}$
$\displaystyle=\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)-\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\right]$

and another stochastic process $\tilde{\mathbb{Q}}_{n}(\mathbf{h})$ as:

$\displaystyle\tilde{\mathbb{Q}}_{n}(\mathbf{h})$
$\displaystyle=\sum_{i=1}^{n}\tilde{\xi}_{i,h_{1}}\mathds{1}_{X_{i}\leq
d_{0}\wedge d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad+\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{d_{0}+\frac{h_{3}}{n}<X_{i}\leq
d_{0}}$
$\displaystyle\qquad\qquad+\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+(\beta_{0}-\alpha_{0})\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad\qquad+\sum_{i=1}^{n}\tilde{\xi}_{i,h_{2}}\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle:=\tilde{\mathbb{Q}}_{n,+}(\mathbf{h})\mathds{1}_{h_{3}\geq
0}+\tilde{\mathbb{Q}}_{n,-}(\mathbf{h})\mathds{1}_{h_{3}<0}\,.$

Hence we have the following decomposition:

$\mathbb{Q}_{n}(\mathbf{h})=\tilde{\mathbb{Q}}_{n}(\mathbf{h})+\mathfrak{E}_{n}(\mathbf{h})+\mathfrak{R}_{n}(\mathbf{h})$
(A.16)

where:

$\displaystyle\mathfrak{R}_{n}(\mathbf{h})$
$\displaystyle=\sum_{i=1}^{n}\left(\tilde{H}_{k}\left({\epsilon}_{i}+(\alpha_{0}-\beta_{0})-\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}\left({\epsilon}_{i}+(\alpha_{0}-\beta_{0})\right)\right)\mathds{1}_{d_{0}+\frac{h_{3}}{n}<X_{i}\leq
d_{0}}$
$\displaystyle\qquad\qquad+\sum_{i=1}^{n}\left(\tilde{H}_{k}\left({\epsilon}_{i}+(\beta_{0}-\alpha_{0})-\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}\left({\epsilon}_{i}+(\beta_{0}-\alpha_{0})\right)\right)\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}$

and

$\displaystyle\mathfrak{E}_{n}(\mathbf{h})$
$\displaystyle=\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}\right)\right)\right]\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}\wedge d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad+\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}\right)\right)\right]\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}$

We next show $\mathfrak{R}_{n}(\mathbf{h})$ is $o_{p}(1)$ uniformly over a
compact set:

$\displaystyle\left|\mathfrak{R}_{n}(\mathbf{h})\right|$
$\displaystyle=\left|\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})-\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)\right)\mathds{1}_{d_{0}+\frac{h_{3}}{n}<X_{i}\leq
d_{0}}\right.$
$\displaystyle\qquad\qquad+\left.\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+(\beta_{0}-\alpha_{0})-\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}+(\beta_{0}-\alpha_{0})\right)\right)\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}\right|$
$\displaystyle\leq\sum_{i=1}^{n}\left|\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})-\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)\right|\mathds{1}_{d_{0}+\frac{h_{3}}{n}<X_{i}\leq
d_{0}}$
$\displaystyle\qquad\qquad+\sum_{i=1}^{n}\left|\tilde{H}_{k}\left(\xi_{i}+(\beta_{0}-\alpha_{0})-\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}+(\beta_{0}-\alpha_{0})\right)\right|\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\leq\frac{(k+1)h_{2}}{\sqrt{n}}\sum_{i=1}^{n}\mathds{1}_{d_{0}+\frac{h_{3}}{n}<X_{i}\leq
d_{0}}+\frac{(k+1)h_{1}}{\sqrt{n}}\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}$

Now suppose $\mathbf{h}\in\mathbb{I}$. There
$|h_{1}|\vee|h_{2}|\vee|h_{3}|\leq K$ for some $K>0$. Hence we have:

$\displaystyle\sup_{\mathbf{h}\in\mathbb{I}}\left|\mathfrak{R}_{n}(\mathbf{h})\right|$
$\displaystyle\leq\frac{(k+1)K}{\sqrt{n}}\left[\sum_{i=1}^{n}\mathds{1}_{d_{0}-\frac{K}{n}<X_{i}\leq
d_{0}}+\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq d_{0}+\frac{K}{n}}\right]$
$\displaystyle=\frac{(k+1)K}{\sqrt{n}}\sum_{i=1}^{n}\mathds{1}_{d_{0}-\frac{K}{n}<X_{i}\leq
d_{0}+\frac{K}{n}}$

as we know:

$\sum_{i=1}^{n}\mathds{1}_{d_{0}-\frac{K}{n}<X_{i}\leq
d_{0}+\frac{K}{n}}\overset{\mathscr{L}}{\implies}\text{Pois}\left(Kf_{X}(d_{0})\right)$

we conclude that:

$\sup_{\mathbf{h}\in\mathbb{I}}\left|\mathfrak{R}_{n}(\mathbf{h})\right|=O_{p}(n^{-1/2})=o_{p}(1)\,.$
(A.17)

We now establish the convergence of $\mathfrak{E}(\mathbf{h})$:

$\displaystyle\mathfrak{E}_{n}(\mathbf{h})$
$\displaystyle=\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\right]\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}\wedge d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad+\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{2}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)\right]\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle=\frac{k+1}{k}\left\\{\frac{h_{1}^{2}}{2n}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{1}}{\sqrt{n}}\right)+\mathbb{E}\left[\left(\frac{h_{1}}{\sqrt{n}}k-\frac{h_{1}}{\sqrt{n}}\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq
k}\right]\right.$
$\displaystyle\qquad\qquad\qquad\qquad+\left.\mathbb{E}\left[\frac{1}{2}\left(\xi+\frac{h_{1}}{\sqrt{n}}+k\right)^{2}\mathds{1}_{-k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq-k}\right]\right\\}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}\wedge d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad+\frac{k+1}{k}\left\\{\frac{h_{2}^{2}}{2n}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{2}}{\sqrt{n}}\right)+\mathbb{E}\left[\left(\frac{h_{2}}{\sqrt{n}}k-\frac{h_{2}}{\sqrt{n}}\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq
k}\right]\right.$
$\displaystyle\qquad\qquad\qquad\qquad+\left.\mathbb{E}\left[\frac{1}{2}\left(\xi+\frac{h_{2}}{\sqrt{n}}+k\right)^{2}\mathds{1}_{-k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq-k}\right]\right\\}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle=n\frac{k+1}{k}\left\\{\frac{h_{1}^{2}}{2n}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{1}}{\sqrt{n}}\right)+\mathbb{E}\left[\left(\frac{h_{1}}{\sqrt{n}}k-\frac{h_{1}}{\sqrt{n}}\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq
k}\right]\right.$
$\displaystyle\qquad\qquad\qquad\qquad+\left.\mathbb{E}\left[\frac{1}{2}\left(\xi+\frac{h_{1}}{\sqrt{n}}+k\right)^{2}\mathds{1}_{-k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq-k}\right]\right\\}\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}\wedge d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad+n\frac{k+1}{k}\left\\{\frac{h_{2}^{2}}{2n}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{2}}{\sqrt{n}}\right)+\mathbb{E}\left[\left(\frac{h_{2}}{\sqrt{n}}k-\frac{h_{2}}{\sqrt{n}}\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq
k}\right]\right.$
$\displaystyle\qquad\qquad\qquad\qquad+\left.\mathbb{E}\left[\frac{1}{2}\left(\xi+\frac{h_{2}}{\sqrt{n}}+k\right)^{2}\mathds{1}_{-k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq-k}\right]\right\\}\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle=\frac{k+1}{k}\left\\{\frac{h_{1}^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{1}}{\sqrt{n}}\right)+n\mathbb{E}\left[\left(\frac{h_{1}}{\sqrt{n}}k-\frac{h_{1}}{\sqrt{n}}\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq
k}\right]\right.$
$\displaystyle\qquad\qquad\qquad\qquad+\left.n\mathbb{E}\left[\frac{1}{2}\left(\xi+\frac{h_{1}}{\sqrt{n}}+k\right)^{2}\mathds{1}_{-k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq-k}\right]\right\\}\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}\wedge d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad+\frac{k+1}{k}\left\\{\frac{h_{2}^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{2}}{\sqrt{n}}\right)+n\mathbb{E}\left[\left(\frac{h_{2}}{\sqrt{n}}k-\frac{h_{2}}{\sqrt{n}}\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq
k}\right]\right.$
$\displaystyle\qquad\qquad\qquad\qquad+\left.n\mathbb{E}\left[\frac{1}{2}\left(\xi+\frac{h_{2}}{\sqrt{n}}+k\right)^{2}\mathds{1}_{-k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq-k}\right]\right\\}\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}$

From strong law of large numbers we have:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq d_{0}\wedge
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\overset{p}{\longrightarrow}\mathbb{P}(X\leq d_{0})\,,$ (A.18)
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\overset{p}{\longrightarrow}\mathbb{P}(X>d_{0})\,,$ (A.19)

For the other terms in the expectation:

$\displaystyle\frac{h_{1}^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{1}}{\sqrt{n}}\right)$
$\displaystyle\overset{}{\longrightarrow}\frac{h_{1}^{2}}{2}\mathbb{P}\left(-k\leq{\epsilon}\leq
k\right)\,,$ (A.20)
$\displaystyle\frac{h_{2}^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\frac{h_{2}}{\sqrt{n}}\right)$
$\displaystyle\overset{}{\longrightarrow}\frac{h_{2}^{2}}{2}\mathbb{P}\left(-k\leq{\epsilon}\leq
k\right)\,.$ (A.21)

For the other terms:

$\displaystyle
n\mathbb{E}\left[\left(\frac{h_{2}}{\sqrt{n}}k-\frac{h_{2}}{\sqrt{n}}\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq
k}\right]$
$\displaystyle=n\int_{k-\frac{h_{2}}{\sqrt{n}}}^{k}\left(\frac{h_{2}}{\sqrt{n}}k-\frac{h_{2}}{\sqrt{n}}x-\frac{1}{2}\left(x-k\right)^{2}\right)f_{\xi}(x)\
dx$
$\displaystyle=n\left[\frac{h_{2}}{\sqrt{n}}\int_{k-\frac{h_{2}}{\sqrt{n}}}^{k}(k-x)f_{\xi}(x)\
dx-\frac{1}{2}\int_{k-\frac{h_{2}}{\sqrt{n}}}^{k}\left(x-k\right)^{2}\
f_{\xi}(x)\ dx\right]$
$\displaystyle=n\left[\frac{h_{2}}{\sqrt{n}}\int_{0}^{\frac{h_{2}}{\sqrt{n}}}zf_{\xi}(z-k)\
dx-\frac{1}{2}\int_{-\frac{h_{2}}{\sqrt{n}}}^{0}z^{2}\ f_{\xi}(z+k)\
dx\right]$ $\displaystyle\leq
Cn\left[\frac{h_{2}}{\sqrt{n}}\int_{0}^{\frac{h_{2}}{\sqrt{n}}}z\
dz+\frac{1}{2}\int_{-\frac{h_{2}}{\sqrt{n}}}^{0}z^{2}\ dz\right]\hskip
14.45377pt[C=\max_{x}f_{\xi}(x)]$ $\displaystyle=n\times O(n^{-3/2})=o(1)\,.$
(A.22)

and

$\displaystyle
n\mathbb{E}\left[\frac{1}{2}\left(\xi+\frac{h_{2}}{\sqrt{n}}+k\right)^{2}\mathds{1}_{-k-\frac{h_{2}}{\sqrt{n}}\leq\xi\leq-k}\right]$
$\displaystyle=n\int_{-k-\frac{h_{2}}{\sqrt{n}}}^{-k}\frac{1}{2}\left(x+\frac{h_{2}}{\sqrt{n}}+k\right)^{2}\
f_{\xi}(x)\ dx$
$\displaystyle=\frac{h_{2}^{3}}{6n^{1/2}}f_{\xi}(k)+o(1)=o(1)\,.$ (A.23)

Similar calculation holds for the terms involving $h_{1}$. Hence we conclude
combining equations (A.18) - (A.23) we conclude:

$\displaystyle\mathfrak{E}_{n}(\mathbf{h})$
$\displaystyle\overset{P}{\longrightarrow}\frac{k+1}{k}\left[\frac{h_{1}^{2}}{2}\mathbb{P}\left(-k\leq{\epsilon}\leq
k\right)F_{X}(d_{0})+\frac{h_{2}^{2}}{2}\mathbb{P}\left(-k\leq{\epsilon}\leq
k\right)\bar{F}_{X}(d_{0})\right]\,.$ (A.24)

Finally we show the weak convergence of $\tilde{\mathbb{Q}}_{n}(\mathbf{h})$
to $\mathbb{Q}(\mathbf{h})$, for which we need to show that the collection
$\\{\tilde{\mathbb{Q}}_{n}(\mathbf{h})\\}_{n\in\mathbb{N}}$ is tight with
respect to appropriate topology and every finite dimensional projection of
$\tilde{\mathbb{Q}}_{n}(\mathbf{h})$ converges to that of
$\mathbb{Q}(\mathbf{h})$. We embark on by showing that for any fixed
$\mathbf{h}$, $\tilde{\mathbb{Q}}_{n}(\mathbf{h})$ converges to
$\mathbb{Q}(\mathbf{h})$ in distribution. Towards that direction, fix
$h_{3}>0$:

$\displaystyle\mathbb{E}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\mid
X_{1},\dots,X_{n}\right]\right]$
$\displaystyle:=\mathbb{E}\left[\mathbb{E}_{\mathbf{X}}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\right]\right]$

We start with analyzing the inner expectation
$\mathbb{E}_{\mathbf{X}}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\right]$:

$\displaystyle\mathbb{E}_{\mathbf{X}}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\right]$
$\displaystyle=\mathbb{E}_{\mathbf{X}}\left[{\sf
exp}\left\\{\left(it\sum_{i=1}^{n}\tilde{\xi}_{i,h_{1}}\mathds{1}_{X_{i}\leq
d_{0}}\right.\right.\right.$
$\displaystyle\qquad\qquad\qquad\qquad\left.\left.\left.+\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}\right.\right.\right.$ $\displaystyle\hskip
200.0003pt\left.\left.\left.+\sum_{i=1}^{n}\tilde{\xi}_{i,h_{2}}\mathds{1}_{X_{i}>d_{0}+\frac{h_{3}}{n}}\right)\right\\}\right]$
$\displaystyle=\left(\phi_{\tilde{\xi}_{h_{1}}}(t)\right)^{\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}}}\times\left(\phi_{\tilde{\xi}_{h_{2}}}(t)\right)^{\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}+\frac{h_{3}}{n}}}$
$\displaystyle\qquad\qquad\qquad\qquad\times\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}}$
$\displaystyle=\left(\phi_{\tilde{\xi}_{h_{1}}}(t)\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}}}\times\left(\phi_{\tilde{\xi}_{h_{2}}}(t)\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}+\frac{h_{3}}{n}}}$
$\displaystyle\qquad\qquad\qquad\qquad\times\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}}$ (A.25)

To show the convergence of the characteristic function of
$\tilde{\xi}_{h_{1}}$ (and similarly for $\tilde{\xi}_{h_{2}}$) we first note
that the variance of $\tilde{\xi}_{h_{1}}$ for $h_{1}>0$ is:

$\displaystyle{\sf var}\left(\tilde{\xi}\right)$ $\displaystyle={\sf
var}\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)$
$\displaystyle=\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}(\xi_{i})\right)^{2}\right]+O(n^{-2})\hskip
14.45377pt[O(n^{-2})\text{ follows from the analysis of
}\mathfrak{E}_{n}(\mathbf{h})]$
$\displaystyle=\left(\frac{k+1}{k}\right)^{2}\left\\{\mathbb{E}\left[\left(\frac{h_{1}}{\sqrt{n}}\xi+\frac{h_{1}^{2}}{2n}\right)^{2}\mathds{1}_{-k\leq\xi\leq
k-\frac{h_{1}}{\sqrt{n}}}\right]\right.$
$\displaystyle\qquad+\left.\mathbb{E}\left[\left(\frac{1}{2}\left(\xi+\frac{h_{1}}{\sqrt{n}}+k\right)^{2}-\frac{h_{1}}{\sqrt{n}}k\right)^{2}\mathds{1}_{-k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq-k}\right]\right.$
$\displaystyle\qquad\qquad+\left.\mathbb{E}\left[\left(-\frac{1}{2}\left(\xi-k\right)^{2}+k\frac{h_{1}}{\sqrt{n}}\right)^{2}\mathds{1}_{k-\frac{h_{1}}{\sqrt{n}}\leq\xi\leq
k}\right]\right.$
$\displaystyle\qquad\qquad\qquad+\left.\frac{k^{2}h_{1}^{2}}{n}\left\\{\mathbb{P}\left(\xi>k\right)+\mathbb{P}\left(\xi<-k-\frac{h_{1}}{\sqrt{n}}\right)\right\\}+O(n^{-2})\right\\}$
$\displaystyle=\left(\frac{k+1}{k}\right)^{2}\left(\frac{h_{1}^{2}}{n}\mathbb{E}\left[\xi^{2}\mathds{1}_{-k\leq\xi\leq
k}\right]+\frac{k^{2}h_{1}^{2}}{n}\left\\{\mathbb{P}\left(\xi>k\right)+\mathbb{P}\left(\xi<-k\right)\right\\}\right)+o(n^{-1})$
$\displaystyle=\left(\frac{k+1}{k}\right)^{2}\left(\frac{h_{1}^{2}}{n}\mathbb{E}\left[\xi^{2}\mathds{1}_{-k\leq\xi\leq
k}\right]+\frac{2k^{2}h_{1}^{2}}{n}\mathbb{P}\left(\xi>k\right)\right)+o(n^{-1})$
$\displaystyle:=\frac{h_{1}^{2}\sigma_{k}^{2}}{n}+o(n^{-1})\,.$

where the variance parameter $\sigma_{k}^{2}$ is defined as:

$\left(\frac{k+1}{k}\right)^{2}\left(\mathbb{E}\left[\xi^{2}\mathds{1}_{-k\leq\xi\leq
k}\right]+2k^{2}\mathbb{P}\left(\xi>k\right)\right)\,.$

Similar calculation holds for $h_{1}<0$ and for $h_{2}$. Hence going back to
equation (A.5) we have:

$\displaystyle\mathbb{E}_{\mathbf{X}}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\right]$
$\displaystyle=\left(1-\frac{t^{2}}{2}\frac{h_{1}^{2}\sigma_{k}^{2}}{n}+o(n^{-1})\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}}}$
$\displaystyle\qquad\qquad\times\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}}$
$\displaystyle\qquad\qquad\qquad\qquad\times\left(1-\frac{t^{2}}{2}\frac{h_{2}^{2}\sigma_{k}^{2}}{n}+o(n^{-1})\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}+\frac{h_{3}}{n}}}$

As

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq d_{0}}$
$\displaystyle\overset{a.s.}{\longrightarrow}F_{X}(d_{0})$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\overset{a.s.}{\longrightarrow}\bar{F}_{X}(d_{0})$

we conclude:

$\displaystyle\left(1-\frac{t^{2}}{2}\frac{h_{1}^{2}\sigma_{k}^{2}}{n}+o(n^{-1})\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}}}$
$\displaystyle\overset{a.s.}{\longrightarrow}e^{-\frac{t^{2}h_{1}^{2}\sigma_{k}^{2}}{2}F_{X}(d_{0})}$
$\displaystyle\left(1-\frac{t^{2}}{2}\frac{h_{2}^{2}\sigma_{k}^{2}}{n}+o(n^{-1})\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}+\frac{h_{3}}{n}}}$
$\displaystyle\overset{a.s.}{\longrightarrow}e^{-\frac{t^{2}h_{2}^{2}\sigma_{k}^{2}}{2}\bar{F}_{X}(d_{0})}$

Also we know:

$\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}\overset{\mathscr{L}}{\implies}\text{Pois}\left(f_{X}(d_{0})h_{3}\right)$

which further implies:

$\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}}\overset{\mathscr{L}}{\implies}\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\text{Pois}\left(f_{X}(\theta_{0})h_{3}\right)}$

Hence combining these we conclude:

$\displaystyle\mathbb{E}_{\mathbf{X}}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\right]$
$\displaystyle=\left(\phi_{\tilde{\xi}_{h_{1}}}(t)\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}\leq
d_{0}}}\times\left(\phi_{\tilde{\xi}_{h_{2}}}(t)\right)^{n\times\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{X_{i}>d_{0}+\frac{h_{3}}{n}}}$
$\displaystyle\qquad\qquad\qquad\qquad\times\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\sum_{i=1}^{n}\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}}$
$\displaystyle\overset{\mathscr{L}}{\implies}e^{-\frac{t^{2}h_{1}^{2}\sigma_{k}^{2}}{2}F_{X}(d_{0})}\times
e^{-\frac{t^{2}h_{2}^{2}\sigma_{k}^{2}}{2}\bar{F}_{X}(d_{0})}$
$\displaystyle\qquad\qquad\qquad\qquad\times\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\text{Pois}\left(f_{X}(d_{0})h_{3}\right)}$

Applying DCT and taking expectation on the both side we conclude:

$\displaystyle\mathbb{E}\left[{\sf
exp}{\left(it\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right)}\right]$
$\displaystyle\longrightarrow
e^{-\frac{t^{2}h_{1}^{2}\sigma_{k}^{2}}{2}F_{X}(d_{0})}\times
e^{-\frac{t^{2}h_{2}^{2}\sigma_{k}^{2}}{2}\bar{F}_{X}(d_{0})}$
$\displaystyle\qquad\qquad\qquad\qquad\times\mathbb{E}\left[\left(\phi_{\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})}(t)\right)^{\text{Pois}\left(f_{X}(d_{0})h_{3}\right)}\right]\,.$

This concludes that
$\tilde{\mathbb{Q}}_{n}(\mathbf{h})\overset{\mathscr{L}}{\implies}\mathbb{Q}(\mathbf{h})$.
The proof of the fact that for any finite collection
$(\mathbf{h}_{1},\dots,\mathbf{h}_{l})$:

$\left(\tilde{\mathbb{Q}}_{n}(\mathbf{h}_{1}),\dots,\tilde{\mathbb{Q}}_{n}(\mathbf{h}_{l})\right)\overset{\mathscr{L}}{\implies}\left(\mathbb{Q}(\mathbf{h}_{1}),\dots,\mathbb{Q}(\mathbf{h}_{l})\right)$
(A.26)

is similar (same analysis of characteristic function) and hence skipped for
brevity. Interested readers can take a look at the proof of Lemma 3.2 of [20]
or the proof of Theorem 5 of [18] for more details of this type of
calculations. We next establish the tightness of the process. Define another
process $\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h})$ as:

$\displaystyle\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h})$
$\displaystyle=\sum_{i=1}^{n}\tilde{\xi}_{i,h_{1}}\mathds{1}_{X_{i}\leq
d_{0}}$
$\displaystyle\qquad+\sum_{i=1}^{n}\left(H_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{d_{0}+\frac{h_{3}}{n}<X_{i}\leq
d_{0}}$
$\displaystyle\qquad\qquad+\sum_{i=1}^{n}\left(H_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right)\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{h_{3}}{n}}$
$\displaystyle\qquad\qquad\qquad+\sum_{i=1}^{n}\tilde{\xi}_{i,h_{2}}\mathds{1}_{X_{i}>d_{0}}$
$\displaystyle:=\accentset{\approx}{\mathbb{Q}}_{n,1}(\mathbf{h})+\accentset{\approx}{\mathbb{Q}}_{n,2}(\mathbf{h})+\accentset{\approx}{\mathbb{Q}}_{n,3}(\mathbf{h})+\accentset{\approx}{\mathbb{Q}}_{n,4}(\mathbf{h})$
(A.27)

We now show that $\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h})$ uniformly
approximate $\tilde{\mathbb{Q}}_{n}(\mathbf{h})$ over compact sets:

$\displaystyle\mathbb{E}\left[\sup_{\mathbf{h}\in\mathbb{I}}\left|\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h})-\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right|\right]$
$\displaystyle\leq\mathbb{E}\left[\sup_{\mathbf{h}\in\mathbb{I}}\left\\{\left|\sum_{i=1}^{n}\tilde{\xi}_{i,h_{1}}\left[\mathds{1}_{X_{i}\leq
d_{0}}-\mathds{1}_{X_{i}\leq d_{0}\wedge
d_{0}+\frac{h_{3}}{n}}\right]\right|+\left|\sum_{i=1}^{n}\tilde{\xi}_{i,h_{2}}\left[\mathds{1}_{X_{i}>d_{0}}-\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}\right]\right|\right\\}\right]$ $\displaystyle\leq
2\mathbb{E}\left[\sup_{\mathbf{h}\in\mathbb{I}}\left|\sum_{i=1}^{n}\tilde{\xi}_{i,h_{1}}\left[\mathds{1}_{X_{i}\leq
d_{0}}-\mathds{1}_{X_{i}\leq d_{0}\wedge
d_{0}+\frac{h_{3}}{n}}\right]\right|\right]$ $\displaystyle\hskip
100.00015pt+2\mathbb{E}\left[\sup_{\mathbf{h}\in\mathbb{I}}\left|\sum_{i=1}^{n}\tilde{\xi}_{i,h_{2}}\left[\mathds{1}_{X_{i}\leq
d_{0}}-\mathds{1}_{X_{i}>d_{0}\vee
d_{0}+\frac{h_{3}}{n}}\right]\right|\right]$ $\displaystyle\leq
2\mathbb{E}\left[\sum_{i=1}^{n}|\tilde{\xi}_{i,h_{1}}|\mathds{1}_{d_{0}-\frac{K}{n}<X_{i}\leq
d_{0}}\right]+2\mathbb{E}\left[\sum_{i=1}^{n}|\tilde{\xi}_{i,h_{2}}|\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{K}{n}}\right]$ $\displaystyle\leq
2n\mathbb{E}\left[|\tilde{\xi}_{h_{1}}|\right]\mathbb{P}\left(d_{0}-\frac{K}{n}<X\leq
d_{0}\right)+2n\mathbb{E}\left[|\tilde{\xi}_{h_{2}}|\right]\mathbb{P}\left(d_{0}<X\leq
d_{0}+\frac{K}{n}\right)$ $\displaystyle\leq 2n\times\left[\sqrt{{\sf
var}\left(\tilde{\xi}_{h_{1}}\right)}\times\left(\frac{K}{n}f_{X}(d_{0})+o(n^{-1})\right)+\sqrt{{\sf
var}\left(\tilde{\xi}_{h_{2}}\right)}\times\left(\frac{K}{n}f_{X}(d_{0})+o(n^{-1})\right)\right]$
$\displaystyle=2n\times\left[\left(\frac{h_{1}\sigma_{k}}{\sqrt{n}}+o(n^{-1/2})\right)\times\left(\frac{K}{n}f_{X}(d_{0})+o(n^{-1})\right)\right.$
$\displaystyle\qquad\qquad\qquad\left.+\left(\frac{h_{2}\sigma_{k}}{\sqrt{n}}+o(n^{-1/2})\right)\times\left(\frac{K}{n}f_{X}(d_{0})+o(n^{-1})\right)\right]$
$\displaystyle=O(n^{-1/2})=o(1)\,.$ (A.28)

Hence from equation (A.28) we conclude:

$\sup_{\mathbf{h}\in\mathbb{I}}\left|\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h})-\tilde{\mathbb{Q}}_{n}(\mathbf{h})\right|=o_{p}(1)\,.$
(A.29)

Therefore it is immediate from equation (A.26) that:

$\left(\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h}_{1}),\dots,\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h}_{l})\right)\overset{\mathscr{L}}{\implies}\left(\mathbb{Q}(\mathbf{h}_{1}),\dots,\mathbb{Q}(\mathbf{h}_{l})\right)\,.$
(A.30)

Next, we show that tightness
$\left\\{\accentset{\approx}{\mathbb{Q}}_{n}(\mathbf{h})\right\\}_{n\in\mathbb{N}}\,.$
As evident from equation (A.27), it is enough to show tightness of
$\left\\{\accentset{\approx}{\mathbb{Q}}_{n,i}(\mathbf{h})\right\\}_{n\in\mathbb{N}}$
for $i=1,2,3,4$. For $i=1$, the process
$\accentset{\approx}{\mathbb{Q}}_{n,1}(\mathbf{h})$ only depends on $h_{1}$
and hence have continuous paths. Therefore to establish tightness, it is
enough to show:

$\lim_{\delta\downarrow
0}\limsup_{n\to\infty}\mathbb{E}\left[\sup_{\begin{subarray}{c}|h_{1,1}|\vee|h_{1,2}|\leq
K\\\
|h_{1,1}-h_{1,2}|\leq\delta\end{subarray}}\sum_{i=1}^{n}\left|\tilde{\xi}_{i,h_{1,1}}-\tilde{\xi}_{i,h_{1,2}}\right|\mathds{1}_{X_{i}\leq
d_{0}}\right]=0$

Towards that end, define a collection of functions:

$\mathcal{F}_{1,\delta}=\left\\{f_{h_{1,1},h_{1,2}}:\left|h_{1,1}\right|\vee\left|h_{1,2}\right|\leq
K,|h_{1,1}-h_{1,2}|\leq\delta\right\\}\,,$

where the individual functions $f_{h_{1,1},h_{1,2}}$ is defined as:

$\displaystyle f_{h_{1,1},h_{1,2}}(X,{\epsilon})$
$\displaystyle=\left\\{\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}+\frac{h_{2}}{\sqrt{n}}\right)\right)\right.$
$\displaystyle\qquad\qquad\qquad\left.-\mathbb{E}\left[\left(\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}+\frac{h_{2}}{\sqrt{n}}\right)\right)\right]\right\\}\mathds{1}_{X\leq
d_{0}}\,.$

Clearly $\mathcal{F}_{1,\delta}$ has finite VC dimension. Also from equation
(A.15) we have:

$\displaystyle\left|\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1,1}}{\sqrt{n}}\right)-\tilde{H}_{k}\left(\xi_{i}+\frac{h_{1,2}}{\sqrt{n}}\right)\right|$
$\displaystyle\qquad\leq\frac{k+1}{k}\left[4k\frac{\left|h_{1,1}-h_{1,2}\right|}{\sqrt{n}}+\frac{1}{2}\frac{\left(h_{1,1}-h_{1,2}\right)^{2}}{n}+\left(\frac{|h_{1,1}-h_{1,2}|}{\sqrt{n}}\wedge
2k\right)^{2}\right]\leq C_{k}\frac{\delta}{\sqrt{n}}\,.$

Therefore, the envelope function can be taken as:

$F_{1,\delta}(X,{\epsilon})=\frac{2C_{k}\delta}{\sqrt{n}}\,.$

Hence using Lemma 2.14.1 of [29] we conclude:

$\limsup_{n\to\infty}\mathbb{E}\left[\sup_{\begin{subarray}{c}|h_{1,1}|\vee|h_{1,2}|\leq
K\\\
|h_{1,1}-h_{1,2}|\leq\delta\end{subarray}}\sum_{i=1}^{n}\left|\tilde{\xi}_{i,h_{1,1}}-\tilde{\xi}_{i,h_{1,2}}\right|\mathds{1}_{X_{i}\leq
d_{0}}\right]\lesssim\delta$

which established tightness of
$\accentset{\approx}{\mathbb{Q}}_{n,1}(\mathbf{h})$. The proof of tightness of
$\accentset{\approx}{\mathbb{Q}}_{n,4}(\mathbf{h})$ is similar and hence
skipped. Finally we show the tightness of
$\accentset{\approx}{\mathbb{Q}}_{n,23}(\mathbf{h})=\accentset{\approx}{\mathbb{Q}}_{n,2}(\mathbf{h})+\accentset{\approx}{\mathbb{Q}}_{n,3}(\mathbf{h})$.
As these terms only depend on $h_{3}$ which has cadlag paths, we use equation
(13.14) of Theorem 13.5 from [7] with $\beta=1/2$, $\alpha=1$ and $F(x)=Cx$
for some constant $C$. Fix $h_{3,1}<0<h_{3,2}<h_{3,3}$. The other cases (i.e.
say $0<h_{3,1}<h_{3,2}<h_{3,3}$) are similar and hence skipped.

$\displaystyle\mathbb{E}\left[\left|\accentset{\approx}{\mathbb{Q}}_{n,23}(h_{3,1})-\accentset{\approx}{\mathbb{Q}}_{n,23}(h_{3,2})\right|\left|\accentset{\approx}{\mathbb{Q}}_{n,23}(h_{3,2})-\accentset{\approx}{\mathbb{Q}}_{n,23}(h_{3,3})\right|\right]$
$\displaystyle=\mathbb{E}\left[\left|\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right)\left[\mathds{1}_{d_{0}+\frac{h_{3,1}}{n}\leq
X_{i}<d_{0}}-\mathds{1}_{d_{0}\leq
X_{i}<d_{0}+\frac{h_{3,2}}{n}}\right]\right|\right.$
$\displaystyle\qquad\qquad\qquad\left.\times\left|\sum_{i=1}^{n}\left(\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right)\left[\mathds{1}_{d_{0}\leq
X_{i}<d_{0}+\frac{h_{3,2}}{n}}-\mathds{1}_{d_{0}\leq
X_{i}<d_{0}+\frac{h_{3,3}}{n}}\right]\right|\right]$
$\displaystyle=\mathbb{E}\left[\sum_{i=1}^{n}\left|\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right|\left[\mathds{1}_{d_{0}+\frac{h_{3,1}}{n}\leq
X_{i}<d_{0}}+\mathds{1}_{d_{0}\leq
X_{i}<d_{0}+\frac{h_{3,2}}{n}}\right]\right.$
$\displaystyle\qquad\qquad\qquad\left.\times\sum_{i=1}^{n}\left|\tilde{H}_{k}\left(\xi_{i}+(\alpha_{0}-\beta_{0})\right)-\tilde{H}_{k}(\xi_{i})\right|\left[\mathds{1}_{d_{0}\leq
X_{i}<d_{0}+\frac{h_{3,2}}{n}}+\mathds{1}_{d_{0}\leq
X_{i}<d_{0}+\frac{h_{3,3}}{n}}\right]\right]$
$\displaystyle\leq\frac{k+1}{k}\left(4(\alpha_{0}-\beta_{0})k+\frac{1}{2}(\alpha_{0}-\beta_{0})^{2}+\left((\alpha_{0}-\beta_{0})\wedge
2k\right)^{2}\right)\times$
$\displaystyle\qquad\qquad\qquad\mathbb{E}\left[\left(\sum_{i=1}^{n}\mathds{1}_{d_{0}+\frac{h_{3,1}}{\sqrt{n}}\leq
X_{i}<d_{0}+\frac{h_{3,2}}{n}}\right)\times\left(\sum_{i=1}^{n}\mathds{1}_{d_{0}+\frac{h_{3,2}}{n}\leq
X_{i}<d_{0}+\frac{h_{3,3}}{n}}\right)\right]$
$\displaystyle=C_{k,\theta_{0}}\sum_{i\neq
j}\mathbb{E}\left[\mathds{1}_{d_{0}+\frac{h_{3,1}}{n}\leq
X_{i}<d_{0}+\frac{h_{3,2}}{n}}\times\mathds{1}_{d_{0}+\frac{h_{3,2}}{n}\leq
X_{j}<d_{0}+\frac{h_{3,3}}{n}}\right]$ $\displaystyle\leq
C_{k,\theta_{0}}\times n^{2}\times\mathbb{P}\left(d_{0}+\frac{h_{3,1}}{n}\leq
X<d_{0}+\frac{h_{3,2}}{n}\right)\times\mathbb{P}\left(d_{0}+\frac{h_{3,2}}{n}\leq
X<d_{0}+\frac{h_{3,3}}{n}\right)$ $\displaystyle\leq
C_{k,\theta_{0}}C^{2}\times(h_{3,2}-h_{3,1})\times(h_{3,3}-h_{3,2})\hskip
14.45377pt[C=\max_{x}f_{X}(x)]$ $\displaystyle\leq
C_{k,\theta_{0}}C^{2}\times(h_{3,3}-h_{3,1})^{2}$

This completes the proof of tightness of
$\accentset{\approx}{\mathbb{Q}}_{n}$. Hence using equation (A.30) we
conclude:

$\accentset{\approx}{\mathbb{Q}}_{n}|_{\mathbb{I}}\overset{\mathscr{L}}{\implies}\mathbb{Q}|_{\mathbb{I}}\,.$

which, along with equation (A.29) implies:

$\tilde{\mathbb{Q}}_{n}|_{\mathbb{I}}\overset{\mathscr{L}}{\implies}\mathbb{Q}|_{\mathbb{I}}\,.$
(A.31)

Finally, from the decomposition in equation (A.16) and combining our
conclusions from equation (A.17), (A.24) and equation (A.31) we have:

$\mathbb{Q}_{n}|_{\mathbb{I}}\overset{\mathscr{L}}{\implies}\mathbb{Q}|_{\mathbb{I}}\,.$
(A.32)

Next and last step is to invoke argmin continuity mapping theorem to say that:

$\widehat{\mathbf{h}}_{n}=\left(\sqrt{n}\left(\hat{\alpha}-\alpha_{0}\right),\sqrt{n}\left(\hat{\beta}-\beta_{0}\right),n\left(\hat{d}-d_{0}\right)\right)\overset{\mathscr{L}}{\implies}\text{mid
argmin}_{\mathbf{h}\in\mathbb{R}^{3}}\mathbb{Q}(\mathbf{h})\,.$

This will complete the proof. Following the proof of Lemma 3.2 of [20], all we
need to establish the joint asymptotic tightness of
$\left\\{\left(\mathbb{Q}_{n}(\mathbf{h}),\mathbb{J}_{n}(\mathbf{h})\right)\right\\}_{n\in\mathbb{N}}$
where $\mathbb{J}_{n}(\mathbf{h})$ is the jump process corresponding to
$\mathbb{Q}_{n}(\mathbf{h})$, i.e.

$\mathbb{J}_{n}(\mathbf{h})=\text{sign}(h_{3})\sum_{i=1}^{n}\left[\mathds{1}_{X_{i}\leq
d_{0}+\frac{h_{3}}{n}}-\mathds{1}_{X_{i}\leq d_{0}}\right]\,.$

As we have already established the tightness of
$\\{\mathbb{Q}_{n}(\mathbf{h})\\}$, we only need to establish the tightness of
$\\{\mathbb{J}_{n}(\mathbf{h})\\}$. The proof is very similar to the proof of
Lemma 3.2 of [20] and skipped here for the brevity.

###  A.6 Proofs of Theorem 2.2 and 2.3

The proofs of Theorem 2.2 and 2.3 are similar to that of Theorem 2.1 by
replacing $\tilde{H}_{k}$ with $\ell_{1}$ loss function and $\ell_{2}$ loss
function respectively and hence skipped.

###  A.7 Proof of Theorem 3.7

Here we assume $\alpha_{0}=0,\beta_{0}=1$ is known and derive the bound on the
$\hat{d}$. When $\alpha_{0},\beta_{0}$ is not known, then the problem becomes
harder and rate of convergence obviously can not be faster. Our proof is based
on the proof of Theorem 5 of [23]. Consider $\mathscr{A}$ to be the set of all
half-spaces, i.e.

$\mathscr{A}=\left\\{x^{\top}d>0\right\\}_{d\in S^{p-1}}\,.$

Our model is $X\sim P$ and:

$Y=\mathds{1}_{X^{\top}d>0}+\xi$

where $\xi\sim\mathcal{N}(0,1)$. Now the class of hyperplanes $\mathscr{A}$
has VC dimension $p$. From the properties of the hyperplane we know that,
given any $N>p$ (not to be confused with sample size $n$) there exist
$x_{1},\dots,x_{N}\in\mathbb{R}^{p}$ such that $\mathscr{A}$ shatters all
subsets of $\left\\{x_{1},\dots,x_{N}\right\\}$ with cardinality $k\leq\lfloor
p/2\rfloor:=V$ (e.g. see [12]). Define $\Theta_{N,V}$ to be the collection of
all such $d\in S^{p-1}$ which shatters all subsets of length $V$ of
$\left\\{x_{1},\dots,x_{N}\right\\}$. Hence we have:

$\left\\{\left(\mathds{1}_{x_{1}^{\top}d>0},\dots,\mathds{1}_{x_{N}^{\top}d>0}\right)\right\\}_{d\in\Theta_{N,V}}:=B$

where:

$B=\left\\{0,1\right\\}_{N,V}=\left\\{b\in\\{0,1\\}^{N}:\sum_{i=1}^{N}b_{i}=V\right\\}\,.$

Henceforth for any $d\in\Theta_{N,V}$ we denote by $b_{d}$ to be the
corresponding unique $b\in B$. Define $\mu$ to be the uniform measure on
$\\{x_{1},\dots,x_{N}\\}$ and for any $d\in\Theta_{N,V}$ define:

$Y=\mathds{1}_{X^{\top}d>0}+\xi\,.$

The loss function we use here is the squared error loss defined as:

$\displaystyle\ell\left(d,d_{0}\right)$
$\displaystyle=\mathbb{E}\left[(Y-\mathds{1}_{X^{\top}d>0})^{2}-(Y-\mathds{1}_{X^{\top}d_{0}>0})^{2}\right]$
$\displaystyle=\mathbb{E}_{X}\left[\left|\mathds{1}_{X^{\top}d>0}-\mathds{1}_{X^{\top}d_{0}>0}\right|\right]$
$\displaystyle=\left\|\mathds{1}_{X^{\top}d>0}-\mathds{1}_{X^{\top}d_{0}>0}\right\|_{L_{1}(P)}\,.$

The minimax risk is defined as:

$\displaystyle\mathcal{R}_{n}$ $\displaystyle=\inf_{\hat{d}}\sup_{d\in
S^{p-1}}\mathbb{E}_{d}\left[\ell(\hat{d},d)\right]$
$\displaystyle\geq\inf_{\hat{d}}\sup_{d\in\Theta_{N,V}}\mathbb{E}_{d}\left[\ell(\hat{d},d)\right]$
$\displaystyle=\inf_{\hat{d}}\sup_{d\in\Theta_{N,V}}\mathbb{E}_{d}\left[\left\|\mathds{1}_{X^{\top}\hat{d}>0}-\mathds{1}_{X^{\top}d>0}\right\|_{L_{1}(\mu)}\right]$
$\displaystyle=\frac{1}{N}\inf_{\hat{d}}\sup_{d\in\Theta_{N,V}}\mathbb{E}_{d}\left[\sum_{i=1}^{N}\left|\mathds{1}_{x_{i}^{\top}\hat{d}>0}-\mathds{1}_{x_{i}^{\top}d>0}\right|_{L_{1}(\mu)}\right]$
(A.33)

Now for any $\hat{d}\in S^{p-1}$, define $\hat{d}_{\text{new}}$ as:

$\hat{d}_{\text{new}}={\arg\min}_{d_{*}\in\Theta_{N,V}}\left\|\mathds{1}_{X^{\top}\hat{d}>0}-\mathds{1}_{X^{\top}d_{*}>0}\right\|_{L_{1}(\mu)}\,.$

Then we have for any $d\in\Theta_{N,V}$:

$\displaystyle\left\|\mathds{1}_{X^{\top}\hat{d}_{\text{new}}>0}-\mathds{1}_{X^{\top}d>0}\right\|_{L_{1}(\mu)}$
$\displaystyle=\left\|\mathds{1}_{X^{\top}\hat{d}_{\text{new}}>0}-\mathds{1}_{X^{\top}\hat{d}>0}+\mathds{1}_{X^{\top}\hat{d}>0}-\mathds{1}_{X^{\top}d>0}\right\|_{L_{1}(\mu)}$
$\displaystyle\leq\left\|\mathds{1}_{X^{\top}\hat{d}_{\text{new}}>0}-\mathds{1}_{X^{\top}\hat{d}>0}\right\|_{L_{1}(\mu)}+\left\|\mathds{1}_{X^{\top}\hat{d}>0}-\mathds{1}_{X^{\top}d>0}\right\|_{L_{1}(\mu)}$
$\displaystyle\leq
2\left\|\mathds{1}_{X^{\top}\hat{d}>0}-\mathds{1}_{X^{\top}d>0}\right\|_{L_{1}(\mu)}\,.$

Putting this bound in equation (A.33) we obtain:

$\displaystyle\mathcal{R}_{n}$
$\displaystyle\geq\frac{1}{N}\inf_{\hat{d}}\sup_{d\in\Theta_{N,V}}\mathbb{E}_{d}\left[\sum_{i=1}^{N}\left|\mathds{1}_{x_{i}^{\top}\hat{d}>0}-\mathds{1}_{x_{i}^{\top}d>0}\right|_{L_{1}(\mu)}\right]$
$\displaystyle\geq\frac{1}{2N}\inf_{\hat{d}}\sup_{d\in\Theta_{N,V}}\mathbb{E}_{d}\left[\sum_{i=1}^{N}\left|\mathds{1}_{x_{i}^{\top}\hat{d}_{\text{new}}>0}-\mathds{1}_{x_{i}^{\top}d>0}\right|_{L_{1}(\mu)}\right]$
$\displaystyle=\frac{1}{2N}\inf_{\hat{d}\in\Theta_{N,V}}\sup_{d\in\Theta_{N,V}}\mathbb{E}_{d}\left[\sum_{i=1}^{N}\left|\mathds{1}_{x_{i}^{\top}\hat{d}>0}-\mathds{1}_{x_{i}^{\top}d>0}\right|_{L_{1}(\mu)}\right]$
(A.34)

Next note that:

$\sum_{i=1}^{N}\left|\mathds{1}_{x_{i}^{\top}\hat{d}>0}-\mathds{1}_{x_{i}^{\top}d>0}\right|=d_{H}\left(b_{\hat{d}},b_{d}\right)$

where $d_{H}$ is the Hamming distance. As $\Theta_{N,V}$ has a bijection with
$B$ we can write equation (A.34) as:

$\mathcal{R}_{n}\geq\frac{1}{2N}\inf_{\hat{b}}\sup_{b\in
B}\mathbb{E}_{b}\left[d_{H}\left(\hat{b},b\right)\right]\geq\frac{1}{2N}\inf_{\hat{b}\in\mathcal{D}}\sup_{b\in\mathcal{D}}\mathbb{E}_{b}\left[d_{H}\left(\hat{b},b\right)\right]$
(A.35)

for any subset $\mathcal{D}\subseteq B$. We now choose $\mathcal{D}$
carefully. Note that for any $N\geq 4V$ (i.e. $N\geq 2p$), we can choose
$\mathcal{D}$ such that (Lemma 8 of [25]):

  1. 1.

$d_{H}\left(b,b^{\prime}\right)>\frac{V}{2}$ for all $b\neq
b^{\prime}\in\mathcal{D}$.

  2. 2.

$\log{|\mathcal{D}|}\geq\rho V\log{\left(\frac{N}{V}\right)}$ with
$\rho=0.233$.

Using this we modify equation (A.35) as follows:

$\displaystyle\mathcal{R}_{n}$
$\displaystyle\geq\frac{1}{2N}\inf_{\hat{b}\in\mathcal{D}}\sup_{b\in\mathcal{D}}\mathbb{E}_{b}\left[d_{H}\left(\hat{b},b\right)\right]$
$\displaystyle=\frac{1}{2N}\inf_{\hat{b}\in\mathcal{D}}\sup_{b\in\mathcal{D}}\mathbb{E}_{b}\left[d_{H}\left(\hat{b},b\right)\mathds{1}_{\hat{b}\neq
b}\right]$
$\displaystyle\geq\frac{V}{4N}\inf_{\hat{b}\in\mathcal{D}}\sup_{b\in\mathcal{D}}\mathbb{P}_{b}\left(\hat{b}\neq
b\right)\hskip 14.45377pt[\text{From point 1. above}]$
$\displaystyle=\frac{V}{4N}\inf_{\hat{b}\in\mathcal{D}}\sup_{b\in\mathcal{D}}\left(1-\mathbb{P}_{b}\left(\hat{b}=b\right)\right)$
$\displaystyle=\frac{V}{4N}\inf_{\hat{b}\in\mathcal{D}}\left(1-\min_{b\in\mathcal{D}}\mathbb{P}_{b}\left(\hat{b}=b\right)\right)$
(A.36)

Now to further bound the above equation, we use the following lemma (see [8]):

######  Lemma A.9.

Let $m\geq 1$, $(P_{i})_{0\leq i\leq m}$ be a family of probability
distributions and $(A_{i})_{0\leq i\leq m}$ be a family of disjoint events.
Let $a=\min_{0\leq i\leq m}P_{i}(A_{i})$. Then setting:

$\bar{\mathscr{K}}=\frac{1}{m}\sum_{i=1}^{m}\mathscr{K}(P_{i},P_{0})$

where $\mathscr{K}$ is the Kullback-Liebler divergence, we have:

$a\leq\alpha\vee\left(\frac{\bar{\mathscr{K}}}{\log{(1+m)}}\right)\,.$

where $\alpha=0.71$.

We now use this bound in equation (A.36). Fix any $b_{0}\in\mathcal{D}$.
Define $A_{i}=\left\\{\hat{b}=b_{i}\right\\}$ for all $b_{i}\in\mathcal{D}$
which are disjoint events. Hence using Lemma A.9 we obtain:

$\min_{b\in\mathcal{D}}\mathbb{P}_{b}\left(\hat{b}=b\right)\leq\alpha\vee\left(\frac{\bar{\mathscr{K}}}{\log{|\mathcal{D}|}}\right)$
(A.37)

where:

$\bar{\mathscr{K}}=\frac{1}{|\mathcal{D}|-1}\sum_{b\in\mathcal{D},b\neq
b_{0}}\mathscr{K}\left(P_{b}^{\otimes n},P_{b_{0}}^{\otimes
n}\right)=\frac{n}{|\mathcal{D}|-1}\sum_{b\in\mathcal{D},b\neq
b_{0}}\mathscr{K}\left(P_{b},P_{b_{0}}\right)\,.$

Now note that for any $d_{1},d_{2}$ we have:

$\displaystyle\mathscr{K}\left(P_{d_{1}},P_{d_{2}}\right)$
$\displaystyle=\mathbb{E}_{X}\left[\mathscr{K}\left(P_{d_{1}}(Y\mid
X),P_{d_{2}}(Y\mid X)\right)\right]$
$\displaystyle=\mathbb{E}_{X}\left[\left(\mathds{1}_{X^{\top}d_{1}>0}-\mathds{1}_{X^{\top}d_{2}>0}\right)^{2}\right]$
$\displaystyle=\mathbb{E}_{X}\left[\left|\mathds{1}_{X^{\top}d_{1}>0}-\mathds{1}_{X^{\top}d_{2}>0}\right|\right]$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left|\mathds{1}_{x_{i}^{\top}d_{1}>0}-\mathds{1}_{x_{i}^{\top}d_{2}>0}\right|$
$\displaystyle=\frac{1}{N}d_{H}(b_{d_{1}},b_{d_{2}})\,.$

Also by definition for any two $b,b^{\prime}\in\mathcal{D}$ we have
$d_{H}(b,b^{\prime})\leq 2V$. Hence we have:

$\bar{\mathscr{K}}\leq\frac{2Vn}{N}\,.$

This bound along with equation (A.37) modifies the bound of equation (A.36)
as:

$\displaystyle\mathcal{R}_{n}$
$\displaystyle\geq\frac{V}{4N}\inf_{\hat{b}\in\mathcal{D}}\left(1-\min_{b\in\mathcal{D}}\mathbb{P}_{b}\left(\hat{b}=b\right)\right)$
$\displaystyle\geq\frac{V}{4N}\left(1-\left(\alpha\vee\frac{2Vn}{N\log{|\mathcal{D}|}}\right)\right)$
$\displaystyle=\frac{V(1-\alpha)}{4N}$ (A.38)

when,

$\displaystyle\alpha\geq\frac{2Vn}{N\log{|\mathcal{D}|}}\,.$

which holds if:

$\displaystyle\alpha>\frac{2Vn}{N\rho V\log{(N/V)}}$

i.e. if:

$N\log{\left(\frac{N}{V}\right)}\geq\frac{2n}{\alpha\rho}\,.$ (A.39)

which is satisfied, if for example:

$N=\left\lfloor\frac{4n}{\rho\alpha\left(1+\log{\left(\frac{n}{V}\right)}\right)}\right\rfloor.$

Using this in equation (A.38) we conclude:

$\mathcal{R}_{n}\gtrsim\frac{V}{n}\left(1+\log{\left(\frac{n}{V}\right)}\right)\asymp\frac{p}{n}\left(1+\log{\left(\frac{n}{p}\right)}\right)\,.$

as $V=\lfloor p/2\rfloor$. We finally need to verify $N>4V$ and that it
satisfies equation (A.39). The first one is obviously true for all large $n$
as $n/p\to\infty$. For the second one, lets forget the $\lfloor\cdot\rfloor$
in the definition of $N$ for the time being as it will not affect
asymptotically. Then:

$\displaystyle N\log{\left(\frac{N}{V}\right)}\geq\frac{2n}{\alpha\rho}$
$\displaystyle\iff$
$\displaystyle\frac{4n}{\rho\alpha\left(1+\log{\left(\frac{n}{V}\right)}\right)}\log{\left(\frac{4n}{V\rho\alpha\left(1+\log{\left(\frac{n}{V}\right)}\right)}\right)}\geq\frac{2n}{\alpha\rho}$
$\displaystyle\iff$
$\displaystyle\frac{1}{\left(1+\log{\left(\frac{n}{V}\right)}\right)}\log{\left(\frac{4n}{V\rho\alpha\left(1+\log{\left(\frac{n}{V}\right)}\right)}\right)}\geq\frac{1}{2}$
$\displaystyle\iff$
$\displaystyle\frac{1}{\left(1+\log{\left(\frac{n}{V}\right)}\right)}\left[\log{\left(\frac{n}{V}\right)}+\log{\left(\frac{4}{\rho\alpha}\right)}-\log{\left(1+\log{\left(\frac{n}{V}\right)}\right)}\right]\geq\frac{1}{2}$

As $n/V\to\infty$, LHS converges to 1 and eventually $>1/2$. Therefore the
choice of $N$ is valid for all large $n$.

###  A.8 Proof of Theorem 3.10

We first assume that Assumption 3.5 holds globally and our parameter space
$\Omega=\Omega_{\alpha}\times\Omega_{\beta}$ for $(\alpha_{0},\beta_{0})$ is
such that:

$\min_{\alpha\in\Omega_{\alpha}}|\alpha-\beta_{0}|\wedge\min_{\beta\in\Omega_{\beta}}|\beta-\alpha_{0}|\geq\delta>0\,.$

This is just to avoid the issue of consistency. One can relax this assumption
with an additionally showing that the estimators are consistent. To prove
Theorem 3.10 we use Theorem A.3 of [24]. To match our notation with that
theorem, here our loss function $\gamma(\theta,\cdot)$ is:

$\displaystyle\gamma(\theta,(X,\xi))$
$\displaystyle=\tilde{H}_{k}\left(\xi+\alpha_{0}\mathds{1}_{X^{\top}d_{0}\leq
0}+\beta_{0}\mathds{1}_{X^{\top}d_{0}>0}-\alpha\mathds{1}_{X^{\top}d\leq
0}-\beta\mathds{1}_{X^{\top}d>0}\right)-\tilde{H}_{k}(\xi)$
$\displaystyle=\left(\tilde{H}_{k}\left(\xi+\alpha_{0}-\alpha\right)-\tilde{H}_{k}(\xi)\right)\mathds{1}_{X^{\top}d\vee
X^{\top}d_{0}\leq 0}$
$\displaystyle\qquad\left(\tilde{H}_{k}\left(\xi+\alpha_{0}-\beta\right)-\tilde{H}_{k}(\xi)\right)\mathds{1}_{X^{\top}d_{0}\leq
0<X^{\top}d}$
$\displaystyle\qquad\qquad+\left(\tilde{H}_{k}\left(\xi+\beta_{0}-\alpha\right)-\tilde{H}_{k}(\xi)\right)\mathds{1}_{X^{\top}d\leq
0<X^{\top}d_{0}}$
$\displaystyle\qquad\qquad\qquad+\left(\tilde{H}_{k}\left(\xi+\beta_{0}-\beta\right)-\tilde{H}_{k}(\xi)\right)\mathds{1}_{X^{\top}d\wedge
X^{\top}d_{0}>0}$

It is immediate from the definition that $\gamma(\theta_{0},(X,\xi))=0$. Also
from equation (A.15) we know $\gamma(\theta,\cdot)$ is uniform bounded by some
constant only depending on $k$ and the width of $\Omega$. Following similar
arguments used in the proof of Theorem 3.6, we obtain:

$\displaystyle\ell(\theta,\theta_{0})$
$\displaystyle=\mathbb{E}[\gamma(\theta,(X,\xi))]\geq c_{k}\ {\sf
dist}^{2}(\theta,\theta_{0})\,,$ (A.40)

for some constant $c_{k}$ (independent of $n$), where the ${\sf dist}$
function is:

${\sf
dist}(\theta,\theta_{0})=\sqrt{(\alpha-\alpha_{0})^{2}+(\beta-\beta_{0})^{2}+\mathbb{P}\left(\text{sign}(X^{\top}d)\neq\text{sign}(X^{\top}d_{0})\right)}\,.$

Moreover, from equation (A.15) we have:

$\displaystyle{\sf var}\left(\gamma(\theta,(X,\xi))\right)$
$\displaystyle\leq\mathbb{E}[\gamma^{2}(\theta,(X,\xi))]\leq C_{k}\ {\sf
dist}^{2}(\theta,\theta_{0})\,.$

Hence this semi-metric ${\sf dist}$ satisfies conditions of Theorem A.3 of
[24] with $\omega(x)=x$. Next we need to bound the modulus of continuity:

$\displaystyle\sqrt{n}\mathbb{E}\left[\sup_{\begin{subarray}{c}\theta:f_{\theta}\in\mathcal{F}_{m}\\\
{\sf
dist}(\theta,\theta_{m})\leq{\epsilon}\end{subarray}}\left|\left(\mathbb{P}_{n}-P\right)\left(\gamma(\theta,(X,\xi))-\gamma(\theta_{m},(X,\xi))\right)\right|\right]$

Note that another application of equation (A.15) yields:

$\sup_{\begin{subarray}{c}\theta:f_{\theta}\in\mathcal{F}_{m}\\\ {\sf
dist}(\theta,\theta_{m})\leq{\epsilon}\end{subarray}}\mathbb{E}\left[\left(\gamma(\theta,(X,\xi))-\gamma(\theta_{m},(X,\xi))\right)^{2}\right]\lesssim{\epsilon}^{2}\,.$

Hence applying Theorem 8.7 of [26] we have:

$\displaystyle\sqrt{n}\mathbb{E}\left[\sup_{\begin{subarray}{c}\theta:f_{\theta}\in\mathcal{F}_{m}\\\
{\sf
dist}(\theta,\theta_{m})\leq{\epsilon}\end{subarray}}\left\|\left(\mathbb{P}_{n}-P\right)\left(\gamma(\theta,(X,\xi))-\gamma(\theta_{m},(X,\xi))\right)\right\|\right]$
$\displaystyle\lesssim{\epsilon}\sqrt{V_{m}\log{\frac{1}{{\epsilon}}}}\vee\frac{V_{m}}{\sqrt{n}}\log{\frac{1}{{\epsilon}}}$
$\displaystyle:=\psi_{m}({\epsilon})\,.$ (A.41)

So a value of ${\epsilon}_{m}$ that satisfies
$\sqrt{n}{\epsilon}_{m}^{2}\geq\phi_{m}({\epsilon}_{m})$ is:

${\epsilon}_{m}=\frac{V_{m}}{n}\log{\frac{n}{V_{m}}}\,.$

Therefore we can take $x_{m}=V_{m}\log{(n/V_{m})}$ and as $\omega(x)=x$ we
have $b(n)=1$ (see Theorem A.3 of [24] for the exact expression of
$\omega(x),b(n)$). Note that, as we are assuming $(s\log{p})/n\to 0$
(Assumption 3.9), it is sufficient to search among the models with $1\leq
m\leq C\lfloor(n/\log{p})\rfloor$ for any constant $C$. We take $C=1/4$ here.
With these choices, the value of $\Sigma$ (as defined in Theorem A.3 of [24])
is:

$\displaystyle\Sigma$
$\displaystyle=\sum_{i=1}^{\frac{1}{4}\lfloor\frac{n}{\log{p}}\rfloor}e^{-V_{i}\log{\frac{n}{V_{i}}}}$
$\displaystyle\leq\lim_{n\to\infty}\sum_{i=1}^{\frac{1}{4}\lfloor\frac{n}{\log{p}}\rfloor}e^{-V_{i}\log{\frac{n}{V_{i}}}}<\infty\,.$

Hence, an application Theorem A.3 of [24] yields:

$\mathbb{P}\left(\ell(\hat{\theta},\theta_{0})>C\text{pen}(s)+t\frac{C_{1}}{n}\right)\leq\Sigma
e^{-t}\,.$

This along with the value of $\text{pen}(s)$ from equation (3.4) of the main
paper and the lower bound equation (A.40) completes the first part of the
proof, i.e.

${\sf
dist}^{2}\left((\hat{\alpha}_{\text{init}},\hat{\beta}_{\text{init}},\hat{d}),(\alpha_{0},\beta_{0},d_{0})\right)=O_{p}\left(\frac{V_{s}}{n}\log{\frac{n}{V_{s}}}\right)\,.$

The acceleration of the rate of $\hat{\alpha},\hat{\beta}$ via replacing
$d_{0}$ by $\hat{d}$ in the model equation is exactly same as that of Theorem
3.6 and hence skipped.

###  A.9 Proof of Theorem 3.14

Here again we assume for technical simplicity that the wedge assumption
(Assumption 3.5) is valid on entire $S^{p-1}$, although all our arguments can
be extended to the case where the assumption is valid only locally along with
a separate argument for the consistency of the estimator. We use the same
notations as of Theorem 3.10 through out the proof. Define

$y^{2}_{m}=2\kappa\frac{V_{m}\|\xi\|_{n,2}}{n}\log{\frac{n}{V_{m}}}$

for all $m\in\mathcal{M}$, where $V_{m}$ is the VC dimension of model $m$. For
any such model $m$ we obtain $\hat{\theta}_{m}$ as:

$\displaystyle\hat{\theta}_{m}$
$\displaystyle={\arg\min}_{\theta\in\Omega\times
S^{p-1}_{m}}\mathbb{P}_{n}\left\\{(Y-\alpha\mathds{1}_{X^{\top}d\leq
0}-\beta\mathds{1}_{X^{\top}d>0})^{2}-\xi^{2}\right\\}$
$\displaystyle={\arg\min}_{\theta\in\Omega\times
S^{p-1}_{m}}\mathbb{P}_{n}\left\\{\xi\left(\alpha_{0}\mathds{1}_{X^{\top}d_{0}\leq
0}+\beta_{0}\mathds{1}_{X^{\top}d_{0}>0}-\alpha\mathds{1}_{X^{\top}d\leq
0}-\beta\mathds{1}_{X^{\top}d>0}\right)\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\left.+\frac{1}{2}\left(\alpha_{0}\mathds{1}_{X^{\top}d_{0}\leq
0}+\beta_{0}\mathds{1}_{X^{\top}d_{0}>0}-\alpha\mathds{1}_{X^{\top}d\leq
0}-\beta\mathds{1}_{X^{\top}d>0}\right)^{2}\right\\}$
$\displaystyle:={\arg\min}_{\theta\in\Omega\times
S^{p-1}_{m}}\mathbb{P}_{n}f_{\theta}$
$\displaystyle:={\arg\min}_{\theta\in\Omega\times
S^{p-1}_{m}}\mathbb{P}_{n}\left(f_{\theta,1}+f_{\theta,2}\right)$

where the functions $f_{d,1},f_{d,2}$ are defined as:

$\displaystyle f_{\theta,1}$
$\displaystyle=\xi\left(\alpha_{0}\mathds{1}_{X^{\top}d_{0}\leq
0}+\beta_{0}\mathds{1}_{X^{\top}d_{0}>0}-\alpha\mathds{1}_{X^{\top}d\leq
0}-\beta\mathds{1}_{X^{\top}d>0}\right)\,,$ $\displaystyle f_{\theta,2}$
$\displaystyle=\frac{1}{2}\left(\alpha_{0}\mathds{1}_{X^{\top}d_{0}\leq
0}+\beta_{0}\mathds{1}_{X^{\top}d_{0}>0}-\alpha\mathds{1}_{X^{\top}d\leq
0}-\beta\mathds{1}_{X^{\top}d>0}\right)^{2}\,.$

The loss function used here is:

$\ell(\theta,\theta_{0})=\mathbb{P}f_{\theta}\gtrsim{\sf
dist}^{2}(\theta,\theta_{0})\,,$

for all $\theta\in\Omega\in S^{p-1}$ via the global version of Assumption 3.5.
From the definition of $\hat{m}$ we have:

$\displaystyle\mathbb{P}_{n}f_{\hat{\theta}_{\hat{m}}}+\text{pen}(\hat{m})$
$\displaystyle\leq\mathbb{P}_{n}f_{\hat{\theta}_{s_{0}}}+\text{pen}(s_{0})$
$\displaystyle\leq\mathbb{P}_{n}f_{\theta_{s_{0}}}+\text{pen}(s_{0}):=\text{pen}(s_{0})\,.$

Using this we can bound the loss function:

$\displaystyle\ell(\hat{\theta}_{\hat{m}},\theta_{0})$
$\displaystyle=\mathbb{P}f_{\hat{\theta}_{\hat{m}}}$
$\displaystyle=\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\hat{\theta}_{\hat{m}}}+\mathbb{P}_{n}f_{\hat{\theta}_{\hat{m}}}$
$\displaystyle=\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\hat{\theta}_{\hat{m}}}+\mathbb{P}_{n}f_{\hat{\theta}_{\hat{m}}}+\text{pen}(\hat{m})-\text{pen}(\hat{m})$
$\displaystyle\leq\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\hat{\theta}_{\hat{m}}}+\text{pen}(s_{0})-\text{pen}(\hat{m})$
$\displaystyle=\frac{\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\hat{\theta}_{\hat{m}}}}{\ell(\hat{\theta}_{\hat{m}},\theta_{0})+y_{\hat{m}}^{2}}\left(\ell(\hat{\theta}_{\hat{m}},\theta_{0})+y_{\hat{m}}^{2}\right)+\text{pen}(s_{0})-\text{pen}(\hat{m})$
$\displaystyle\leq\sup_{\theta\in\Omega\times
S^{p-1}_{\hat{m}}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\theta}\right|}{\ell(\theta,\theta_{0})+y_{\hat{m}}^{2}}\left(\ell(\hat{\theta}_{\hat{m}},d_{0})+y_{\hat{m}}^{2}\right)+\text{pen}(s_{0})-\text{pen}(\hat{m})$

For the rest of the calculation, define:

$\displaystyle\Gamma_{m}$ $\displaystyle=\sup_{\theta\in\Omega\times
S^{p-1}_{m}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\theta}\right|}{\ell(\theta,\theta_{0})+y_{m}^{2}}$
$\displaystyle=\sup_{\theta\in\Omega\times
S^{p-1}_{m}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)(f_{\theta,1}+f_{\theta,2})\right|}{\ell(\theta,\theta_{0})+y_{m}^{2}}$
$\displaystyle\leq\sup_{\theta\in\Omega\times
S^{p-1}_{m}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\theta,1}\right|}{\ell(\theta,\theta_{0})+y_{m}^{2}}+\sup_{\theta\in\Omega\times
S^{p-1}_{m}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\theta,2}\right|}{\ell(\theta,\theta_{0})+y_{m}^{2}}$
$\displaystyle:=\Gamma_{m,1}+\Gamma_{m,2}\,.$

Next we try to bound $\Gamma_{\hat{m}}$. More specifically, we bound
$\Gamma_{m}$ for all $m$ and then use a union bound to bound
$\Gamma_{\hat{m}}$. Note that, as the function class under the consideration
of $\Gamma_{m,2}$ is bounded we can use similar as of the proof of Theorem A.3
of [24] (i.e. applying Talagrand’s inequality and then bound the expectation
and variance) to conclude:

$\mathbb{P}\left(\Gamma_{\hat{m},2}\geq 1/4\right)=o(1)\,.$ (A.42)

For $\Gamma_{m,1}$, we first decompose it as follows:

$\displaystyle\Gamma_{m,1}$ $\displaystyle\leq\sup_{d\in
S^{p-1}_{m}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)\left(f_{\theta,1}-f_{\theta_{m},1}\right)\right|}{\ell(\theta,\theta_{0})+y_{m}^{2}}+\sup_{\theta\in\Omega\times
S^{p-1}_{m}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\theta_{m},1}\right|}{\ell(\theta,\theta_{0})+y_{m}^{2}}$
$\displaystyle\leq\sup_{\theta\in\Omega\times
S^{p-1}_{m}}\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)\left(f_{\theta,1}-f_{\theta_{m},1}\right)\right|}{\ell(\theta,\theta_{0})+y_{m}^{2}}+\frac{\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)f_{\theta_{m},1}\right|}{\ell(\theta_{m},\theta_{0})+y_{m}^{2}}$
$\displaystyle=\Gamma_{m,11}+\Gamma_{m,12}\,.$

Bounding $\mathbb{E}[\Gamma_{m,12}]$ is straight-forward:

$\displaystyle\mathbb{E}[\Gamma_{m,12}]$ $\displaystyle\leq\frac{\sqrt{{\sf
var}\left(f_{\theta_{m},1}\right)}}{\sqrt{n}\left(\ell(\theta_{m},\theta_{0})+y_{m}^{2}\right)}$
$\displaystyle\leq\frac{\|\xi\|_{2}{\sf
dist}(\theta_{m},\theta_{0})}{\sqrt{n}\left({\sf
dist}^{2}(\theta_{m},\theta_{0})+y_{m}^{2}\right)}$
$\displaystyle\leq\frac{\|\xi\|_{2}}{\sqrt{n}}\ \sup_{x\geq
0}\frac{x}{x^{2}+y_{m}^{2}}\leq\frac{\|\xi\|_{2}}{2}\frac{1}{\sqrt{n}y_{m}}\,.$

To bound $\mathbb{E}[\Gamma_{m,1}]$ we use the maximal inequality of the
weighted empirical process (see Lemma A.5 of [23]), which is a variant of
peeling argument. First of all note that, by symmetrization and applying
Theorem 8.7 of [26], we have for any $1\leq k\leq n$:

$\displaystyle\mathbb{E}\left[\sup_{\begin{subarray}{c}\theta\in\Omega\times
S^{p-1}_{m}\\\ {\sf
dist}(\theta,\theta_{m})\leq{\epsilon}\end{subarray}}\left|\sum_{i=1}^{k}\xi_{i}\left(\alpha_{m}\mathds{1}_{X_{i}^{\top}d_{m}\leq
0}+\beta_{m}\mathds{1}_{X_{i}^{\top}d_{m}>0}-\alpha\mathds{1}_{X_{i}^{\top}d\leq
0}-\beta\mathds{1}_{X_{i}^{\top}d>0}\right)\right|\right]$
$\displaystyle\qquad\qquad\qquad\lesssim\left(\sigma_{{\epsilon}}\sqrt{kV_{m}\log{\frac{1}{\sigma_{{\epsilon}}}}}\vee
V_{m}\log{\frac{1}{\sigma_{\epsilon}}}\right)\,.$

where the _wimpy variance_ $\sigma_{\epsilon}^{2}$ is defined as:

$\displaystyle\sigma_{\epsilon}^{2}=\sup_{\begin{subarray}{c}\theta:f_{\theta}\in\mathcal{F}_{m}\\\
{\sf dist}(\theta,\theta_{m})\leq{\epsilon}\end{subarray}}\sigma_{\xi}^{2}\
\mathbb{E}\left[\left(\alpha_{m}\mathds{1}_{X_{i}^{\top}d_{m}\leq
0}+\beta_{m}\mathds{1}_{X_{i}^{\top}d_{m}>0}-\alpha\mathds{1}_{X_{i}^{\top}d\leq
0}-\beta\mathds{1}_{X_{i}^{\top}d>0}\right)^{2}\right]\lesssim{\epsilon}^{2}\,.$

This, along with Proposition A.7 implies:

$\displaystyle\mathbb{E}\left[\sup_{\begin{subarray}{c}\theta:f_{\theta}\in\mathcal{F}_{m}\\\
{\sf
dist}(\theta,\theta_{m})\leq{\epsilon}\end{subarray}}\left|\left(\mathbb{P}-\mathbb{P}_{n}\right)\left(f_{\theta,1}-f_{\theta_{m},1}\right)\right|\right]$
$\displaystyle=\mathbb{E}\left[\sup_{\begin{subarray}{c}\theta:f_{\theta}\in\mathcal{F}_{m}\\\
{\sf
dist}(\theta,\theta_{m})\leq{\epsilon}\end{subarray}}\left|\sum_{i=1}^{k}\xi_{i}\left(\alpha_{m}\mathds{1}_{X_{i}^{\top}d_{m}\leq
0}+\beta_{m}\mathds{1}_{X_{i}^{\top}d_{m}>0}-\alpha\mathds{1}_{X_{i}^{\top}d\leq
0}-\beta\mathds{1}_{X_{i}^{\top}d>0}\right)\right|\right]$
$\displaystyle\qquad\lesssim\left\|\xi\right\|_{2,1}{\epsilon}\sqrt{\frac{V_{m}}{n}\log{\left(\frac{1}{{\epsilon}}\right)}}+2\frac{V_{m}}{n}\log{\left(\frac{1}{{\epsilon}}\right)}\mathbb{E}\left[\max_{1\leq
i\leq n}\left|\xi_{i}\right|\right]:=\frac{\psi_{m}({\epsilon})}{\sqrt{n}}\,.$

An application of Lemma A.5 of [23] yields:

$\mathbb{E}[\Gamma_{m,1}]\lesssim\frac{\psi_{m}(2\sqrt{2}y_{m})}{\sqrt{n}y_{m}^{2}}$

which, in turn, yields:

$\displaystyle E(\Gamma_{m,1})$
$\displaystyle\leq\frac{4\phi_{m}(2\sqrt{2}y_{m})}{\sqrt{n}y^{2}_{m}}+\frac{\|\xi\|_{2}}{2\sqrt{n}y_{m}}$
$\displaystyle\leq\frac{4\phi_{m}(2\sqrt{2}\epsilon_{m})}{\sqrt{n}y_{m}\epsilon_{m}}+\frac{\|\xi\|_{2}}{2\sqrt{n}y_{m}}\sqrt{\frac{y_{m}^{2}}{y^{2}_{m}}}$
$\displaystyle\leq\frac{8\sqrt{2}\phi_{m}(\epsilon_{m})}{\sqrt{n}y_{m}\epsilon_{m}}+\frac{\|\xi\|_{2}}{2\sqrt{n}y_{m}}\sqrt{\frac{\phi^{2}_{m}\left(y_{m}\right)}{y^{2}_{m}}}$
$\displaystyle\leq\frac{8\sqrt{2}\epsilon_{m}}{y_{m}}+\frac{2}{\sqrt{n}y_{m}}\sqrt{\frac{\phi^{2}_{m}\left(\epsilon_{m}\right)}{\epsilon^{2}_{m}}}$
$\displaystyle\leq\frac{8}{\sqrt{\kappa}}+\frac{\|\xi\|_{2}}{2\sqrt{n}y_{m}}\frac{\phi_{m}\left(\epsilon_{m}\right)}{\epsilon_{m}}$
$\displaystyle\leq\frac{8}{\sqrt{\kappa}}+\frac{\|\xi\|_{2}\epsilon_{m}}{2y_{m}}\leq\frac{8+\sqrt{2}}{\sqrt{\kappa}}$
(A.43)

which can be made arbitrarily small by making $\kappa$ arbitrarily large.
Next, we bound the fluctuation of $V_{m,1}$ around its mean using Chebychev
inequality:

$\mathbb{P}\left(\left|\Gamma_{m,1}-\mathbb{E}[\Gamma_{m,1}]\right|\geq
t\right)\leq\frac{{\sf var}(\Gamma_{m,1})}{t^{2}}\,.$

To bound the variance we use Theorem 11.17 along with Theorem 11.1 of [9]. To
match with their notation for the ease of the readers, we have:

$\displaystyle X_{i,\theta}$
$\displaystyle=\frac{1}{n}\left[\frac{\xi_{i}\left(\alpha_{m}\mathds{1}_{X_{i}^{\top}d_{m}\leq
0}+\beta_{m}\mathds{1}_{X_{i}^{\top}d_{m}>0}-\alpha\mathds{1}_{X_{i}^{\top}d\leq
0}-\beta\mathds{1}_{X_{i}^{\top}d>0}\right)}{\ell(\theta,\theta_{0})+y_{m}^{2}}\right.$
$\displaystyle\qquad\qquad\qquad\left.-\mathbb{E}\left(\frac{\xi_{i}\left(\alpha_{m}\mathds{1}_{X_{i}^{\top}d_{m}\leq
0}+\beta_{m}\mathds{1}_{X_{i}^{\top}d_{m}>0}-\alpha\mathds{1}_{X_{i}^{\top}d\leq
0}-\beta\mathds{1}_{X_{i}^{\top}d>0}\right)}{\ell(\theta,\theta_{0})+y_{m}^{2}}\right)\right]$
$\displaystyle=\frac{1}{n}\left[\frac{\xi_{i}\left(\alpha_{m}\mathds{1}_{X_{i}^{\top}d_{m}\leq
0}+\beta_{m}\mathds{1}_{X_{i}^{\top}d_{m}>0}-\alpha\mathds{1}_{X_{i}^{\top}d\leq
0}-\beta\mathds{1}_{X_{i}^{\top}d>0}\right)}{\ell(\theta,\theta_{0})+y_{m}^{2}}\right]\hskip
14.45377pt[\text{As }\mathbb{E}(\xi)=0]$

That $X_{i,\theta}$ is symmetric follows from the symmetry of $\xi$. We define
$M$ as:

$\max_{1\leq i\leq n}\sup_{\theta\in\Omega\times
S^{p-1}_{m}}X_{i,\theta}^{2}\lesssim\frac{\max_{1\leq i\leq
n}\xi_{i}^{2}}{n^{2}y_{m}^{4}}:=M$

and the wimpy variance:

$\displaystyle\sup_{\theta\in\Omega\times
S^{p-1}_{m}}\sum_{i=1}^{n}\mathbb{E}(X_{i,\theta}^{2})$
$\displaystyle\leq\frac{2\sigma_{\xi}^{2}}{n}\frac{\ell(\theta_{m},\theta_{0})}{(\ell(\theta_{m},\theta_{0})+y_{m}^{2})^{2}}$
$\displaystyle\leq\frac{2\sigma_{\xi}^{2}}{n}\sup_{x\geq
0}\frac{x}{(x+y_{m}^{2})^{2}}$
$\displaystyle\leq\frac{2\sigma_{\xi}^{2}}{4ny_{m}^{2}}:=\sigma_{m}^{2}\,.$

An application of Theorem 11.17 and Theorem 11.1 of [9] yields:

$\displaystyle{\sf
var}(\Gamma_{m,1})\leq\sigma_{m}^{2}+64\sqrt{\mathbb{E}[M_{m}]}\mathbb{E}[\Gamma_{m,1}]+18^{2}\mathbb{E}[M_{m}]\,.$
(A.44)

Note that we set $V_{m}=m(\log p)^{1+\delta}$ (which is slightly larger than
the VC dimension) and choose $y_{m}^{2}$ as:

$y_{m}^{2}=2\frac{V_{m}\|\xi\|_{2,n}}{n}\log{\frac{n}{V_{m}}}=2\text{pen}(m)\,.$

As per Assumption 3.13, we confine the model selection in $1\leq
m\leq(1/4)\lfloor n/(\log{p})^{2}\rfloor$. To facilitate the union, we next
show that $\sum_{i=1}^{\mathcal{M}}{\sf var}(V_{m,1})\to 0$ as $n\to\infty$.
We bound each terms on RHS of equation (A.44):

$\displaystyle\sum_{i=1}^{\mathcal{M}}\sigma_{m}^{2}$
$\displaystyle=\frac{\sigma_{\xi}^{2}}{4}\sum_{i=1}^{\mathcal{M}}\frac{1}{ny_{m}^{2}}$
$\displaystyle=\frac{\sigma_{\xi}^{2}}{4\|\xi\|_{n,2}}\sum_{i=1}^{n/(4(\log
p)^{2})}\frac{1}{V_{m}\log{\frac{n}{V_{m}}}}$
$\displaystyle\leq\frac{\sigma_{\xi}^{2}}{4\log{4}\|\xi\|_{n,2}}\sum_{i=1}^{n/4(\log
p)^{2}}\frac{1}{V_{m}}$
$\displaystyle\leq\frac{\sigma_{\xi}^{2}}{4\log{4}(\log{p})^{\delta/2}\|\xi\|_{n,2}}\sum_{i=1}^{n/(4(\log
p)^{2})}\frac{1}{m(\log{m})^{1+\delta/2}}$
$\displaystyle\leq\frac{\sigma_{\xi}^{2}}{4\log{4}(\log{p})^{\delta/2}\|\xi\|_{n,2}}\sum_{i=1}^{\infty}\frac{1}{m(\log{m})^{1+\delta/2}}$
$\displaystyle\longrightarrow 0\text{ as }n\to\infty.$

Now for the second summand:

$\displaystyle
64\sum_{i=1}^{\mathcal{M}}\sqrt{\mathbb{E}[M_{m}]}\mathbb{E}[\Gamma_{m,1}]$
$\displaystyle\leq 16\sqrt{\mathbb{E}[M_{m}]}$ $\displaystyle\lesssim
8\sum_{i=1}^{\mathcal{M}}\sqrt{\frac{\mathbb{E}[\max_{1\leq i\leq
n}\xi_{i}^{2}]}{n^{2}y_{m}^{4}}}$
$\displaystyle=8\sum_{i=1}^{\mathcal{M}}\frac{\|\xi\|_{n,2}}{ny_{m}^{2}}$
$\displaystyle\leq\frac{8}{4\log{4}(\log{p})^{\delta/2}}\sum_{i=1}^{\infty}\frac{1}{m(\log{m})^{1+\delta/2}}$
$\displaystyle\longrightarrow 0\text{ as }n\to\infty.$

And similarly for the third summand:

$\displaystyle 18^{2}\sum_{i=1}^{\mathcal{M}}\mathbb{E}[M_{m}]$
$\displaystyle=18^{2}\sum_{i=1}^{\mathcal{M}}\frac{\mathbb{E}[\max_{1\leq
i\leq n}\xi_{i}^{2}]}{n^{2}y_{m}^{4}}$
$\displaystyle\leq\frac{18^{2}}{4\log{4}(\log{p})^{\delta}}\sum_{i=1}^{\infty}\frac{1}{m^{2}(\log{m})^{2+\delta}}$
$\displaystyle\longrightarrow 0\text{ as }n\to\infty.$

Hence taking $t=1/8$ and using the fact that $\mathbb{E}[\Gamma_{m,1}]\leq
1/8$ for all $m$ for our choice of $\kappa$, we have:

$\mathbb{P}\left(\Gamma_{\hat{m},1}>\frac{1}{4}\right)\longrightarrow 0\,.$
(A.45)

Therefore, combining equation (A.42) and (A.45) we conclude:

$\mathbb{P}\left(\Gamma_{\hat{m}}>\frac{1}{2}\right)\longrightarrow 0$

Hence, on its complement event, we have

$\displaystyle\ell(\hat{\theta}_{\hat{m}},\theta_{0})$
$\displaystyle\leq\frac{1}{2}\left(\ell(\hat{\theta}_{\hat{m}},d_{0})+y_{\hat{m}}^{2}\right)+\text{pen}(s_{0})-\text{pen}(\hat{m})$
$\displaystyle=\frac{1}{2}\ell(\hat{\theta}_{\hat{m}},d_{0})+\text{pen}(s_{0})\,,$

which further implies,

$\ell(\hat{\theta}_{\hat{m}},\theta_{0})\leq 2\text{pen}(s_{0})\,.$

This, along with equation (A.40) indicates:

${\sf
dist}^{2}\left((\hat{\alpha}_{\text{init}},\hat{\beta}_{\text{init}},\hat{d}),(\alpha_{0},\beta_{0},d_{0})\right)=O_{p}\left(\frac{s_{0}(\log{p})^{(1+\delta)}\|\xi\|_{n,2}}{n}\left(\log{\frac{n}{s_{0}\log{p}}}\right)\right)\,.$

The boosting of the rate of $\hat{\alpha},\hat{\beta}$ by replacing $d_{0}$ by
$\hat{d}$ in the model equation is exactly same as that of Theorem 3.6 and
hence skipped.

###  A.10 Proof of Theorem 3.12

For the proof of this theorem we follow the techniques of proof of Theorem
2.18 of [24]. Recall Fano’s inequality: if $\Theta\subseteq S^{p-1}$ is a
finite $2{\epsilon}$ packing set, i.e. for any two $d_{i},d_{j}\in\Theta$, we
have $\|d_{i}-d_{j}\|\geq 2{\epsilon}$ with $|\Theta|<\infty$, then based on n
i.i.d. observations $z_{1},\dots,z_{n}$ we have the following minimax lower
bound in estimating $d_{0}$:

$\inf_{\hat{d}}\sup_{\mathcal{P}_{d}}\mathbb{E}\left[\left\|\hat{d}-d\right\|^{2}\right]\geq{\epsilon}^{2}\left(1-\frac{\frac{n}{M^{2}}\sum_{i,j:d_{i},d_{j}\in\Theta}KL(P_{d_{i}}||P_{d_{j}})+\log{2}}{\log{(|\Theta|-1)}}\right)$

Next recall Gilbert-Varshamov Lemma: if $d_{H}$ is the Hamming distance, i.e.
$d_{H}(x,y)=\sum_{i=1}^{d}\mathds{1}(x_{i}\neq y_{i})$ with $d$ being the
ambient dimension. Then given any $v$ with $1\leq v\leq p/8$, we can find
$\omega_{1},\dots,\omega_{M}\in\\{0,1\\}^{p}$ which satisfy the following:

  1. a)

$d_{H}(\omega_{i},\omega_{j})\geq\frac{v}{2}\ \ \forall\ i\neq j\ \
\in\\{1,\dots,m\\}$.

  2. b)

$\log{M}\geq\frac{v}{8}\log{\left(1+\frac{d}{2v}\right)}$.

  3. c)

$\|\omega_{j}\|_{0}=v\ \ \forall\ j\ \in\\{1,\dots,M\\}$.

We choose the appropriate ${\epsilon}$ later. First, for a fixed
$0<{\epsilon}<1$, we construct the set $\Theta$ as follows: applying Gilbert-
Varshamov Lemma in dimension $p-1$ with sparsity $v=s-1$, we choose
$\Omega=\left\\{\omega_{1},\dots,\omega_{M}\right\\}\in\\{0,1\\}^{p-1}$ which
satisfies the above conditions (a) - (c). Then, for each $\omega_{j}\in\Omega$
set $d_{j}$ as:

$d_{j}=\frac{\left(1,\frac{{\epsilon}}{\sqrt{s-1}}\omega_{j}\right)}{\sqrt{1+{\epsilon}^{2}}}$

It is immediate that $\|d_{j}\|_{2}=1$ and $\|d_{j}\|_{0}=s$. Set
$\Theta=\\{d_{j}:\omega_{j}\in\Omega\\}$. From condition (c) above we have:

$\left|\Theta\right|:=M\geq\frac{s-1}{8}\log{\left(1+\frac{p-1}{s-1}\right)}\,.$

Further note that for any $d_{i}\neq d_{j}\in\Theta$:

$\|d_{i}-d_{j}\|^{2}_{2}=\frac{{\epsilon}^{2}}{(s-1)(1+{\epsilon}^{2})}\|\omega_{i}-\omega_{j}\|^{2}=\frac{{\epsilon}^{2}}{(s-1)(1+{\epsilon}^{2})}d_{H}(\omega_{i},\omega_{j})=\frac{{\epsilon}^{2}}{2(1+{\epsilon}^{2})}\geq\frac{{\epsilon}^{2}}{4}\,.$

which proves that $\Theta$ is a ${\epsilon}/2$ packing set of $S^{p-1}$. On
the other hand, from condition (c) above it is immediate that, for any
$\omega_{i}\neq\omega_{j}\in\Omega$, we have $d_{H}(\omega_{i},\omega_{j})\leq
2s$. This implies that for any $d_{i},d_{j}\in\Theta$:

$\|d_{i}-d_{j}\|_{2}^{2}=\frac{{\epsilon}^{2}}{(s-1)(1+{\epsilon}^{2})}d_{H}(\omega_{i},\omega_{j})\leq
2{\epsilon}^{2}\,.$

Now for each $d_{i}\in\Theta$ define the distribution $P_{d_{i}}$ of $(X,Y)$
as: $X\sim\mathcal{N}(0,I_{p}),\xi\sim\mathcal{N}(0,1)$, $X$ is independent of
$\xi$ and:

$Y\overset{d}{=}\mathds{1}_{X^{\top}d_{i}>0}+\xi\,.$

Hence for any $d_{i}\neq d_{j}\in\Theta$, the Kullback-Liebler divergence
between $P_{d_{i}}$ and $P_{d_{j}}$ is:

$\displaystyle KL(P_{d_{i}}||P_{d_{j}})$
$\displaystyle=\frac{1}{2}\mathbb{E}_{X}\left[\left(\mathds{1}_{X^{\top}d_{i}>0}-\mathds{1}_{X^{\top}d_{j}>0}\right)^{2}\right]$
$\displaystyle=\mathbb{P}\left(\text{sign}(X^{\top}d_{i})\neq\text{sign}(X^{\top}d_{j})\right)$
$\displaystyle\leq C\|d_{i}-d_{j}\|_{2}\leq{\epsilon}\ \sqrt{2C^{2}}\,.$

for some universal constant $C$. Hence applying Fano’s inequality we obtain:

$\displaystyle\inf_{\hat{d}}\sup_{\mathcal{P}_{d}}\mathbb{E}\left[\left\|\hat{d}-d\right\|^{2}\right]$
$\displaystyle\geq\frac{{\epsilon}^{2}}{16}\left(1-\frac{\frac{n}{M^{2}}\sum_{i,j:d_{i},d_{j}\in\Theta}KL(P_{d_{i}}||P_{d_{j}})+\log{2}}{\log{(|\Theta|-1)}}\right)$
$\displaystyle\geq\frac{{\epsilon}^{2}}{16}\left(1-\frac{n{\epsilon}\
\sqrt{2C^{2}}+\log{2}}{\log{\left(\frac{s-1}{8}\log{\left(1+\frac{p-1}{s-1}\right)}-1\right)}}\right)\,.$

Taking ${\epsilon}=(s\log{(1+p/s)})/n$ we conclude the proof.

##  Appendix B Proof of supplementary lemmas

###  B.1 Proof of Lemma A.8

As $\xi$ has symmetric distribution around origin, without loss of generality
we can assume $\mu>0$. Hence we have to establish the result for $0<\mu k$.
Note that difference $H_{k}(\xi+\mu)-H_{k}(\xi)$ can be decomposed into five
terms, depending where $\xi$ lies:

$H_{k}(\xi+\mu)-H_{k}(\xi)=\begin{cases}\frac{1}{2}\left[(\xi+\mu)^{2}-\xi^{2}\right]\,,&\text{
if }-k\leq\xi\leq k-\mu\\\
\frac{1}{2}(\xi+\mu)^{2}-k\left(|\xi|-\frac{k}{2}\right)\,,&\text{ if
}-k-\mu\leq\xi\leq-k\\\
k\left(|\xi+\mu|-\frac{k}{2}\right)-\frac{\xi^{2}}{2}\,,&\text{ if
}k-\mu\leq\xi\leq k\\\ K\left(|\xi+\mu|-|\xi|\right)\,,&\text{ if }\xi>k\text{
or }\xi<-k-\mu\end{cases}$ (B.1)

Now we inspect the regions individually. Note that when $-k-\mu\leq\xi\leq-k$,
we have:

$\displaystyle H_{k}(\xi+\mu)-H_{k}(\xi)$
$\displaystyle=\frac{1}{2}(\xi+\mu)^{2}-k\left(|\xi|-\frac{k}{2}\right)$
$\displaystyle=\frac{1}{2}(\xi+\mu)^{2}+k\left(\xi+\frac{k}{2}\right)\hskip
14.45377pt[\because|\xi|=-\xi]$
$\displaystyle=\frac{\xi^{2}}{2}+(\mu+k)\xi+\frac{\mu^{2}+k^{2}}{2}$
$\displaystyle=\frac{1}{2}\left(\xi+\mu+k\right)^{2}-\mu k$

When $k-\mu\leq\xi\leq k$:

$\displaystyle H_{k}(\xi+\mu)-H_{k}(\xi)$
$\displaystyle=k\left(|\xi+\mu|-\frac{k}{2}\right)-\frac{\xi^{2}}{2}$
$\displaystyle=k\left((\xi+\mu)-\frac{k}{2}\right)-\frac{\xi^{2}}{2}$
$\displaystyle=-\frac{\xi^{2}}{2}+k\xi-\frac{k^{2}}{2}+k\mu$
$\displaystyle=-\frac{1}{2}\left(\xi-k\right)^{2}+k\mu$

Also, we have:

$k\left(|\xi+\mu|-|\xi|\right)=\begin{cases}k\mu\,,&\text{ if }\xi>k\\\
-k\mu\,,&\text{ if }\xi<-k-\mu\,.\end{cases}$

Hence we can modify equation (B.1) as:

$H_{k}(\xi+\mu)-H_{k}(\xi)=\begin{cases}\mu\xi+\frac{\mu^{2}}{2}\,,&\text{ if
}-k\leq\xi\leq k-\mu\\\ \frac{1}{2}\left(\xi+\mu+k\right)^{2}-\mu k\,,&\text{
if }-k-\mu\leq\xi\leq-k\\\ -\frac{1}{2}\left(\xi-k\right)^{2}+k\mu\,,&\text{
if }k-\mu\leq\xi\leq k\\\ k\mu\,,&\text{ if }\xi>k\\\ -k\mu\,,&\text{ if
}\xi<-k-\mu\,.\end{cases}$ (B.2)

Note that the term $-\mu k$ is active on the region $\xi\leq-k$ and $\mu k$ is
active on the region $\xi\geq k-\mu$. From the symmetry of the distribution of
$\xi$, this effect of $-\mu k$ and $\mu k$ on the region $(-\infty,-k)$ and
$(k,\infty)$ will cancel each other upon taking expectation and the effect of
$\mu k$ on $(k-\mu,k)$ will remain. Hence we have:

$\displaystyle\mathbb{E}\left[H_{k}(\xi+\mu)-H_{k}(\xi)\right]$
$\displaystyle=\frac{\mu^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\mu\right)+\mu\mathbb{E}\left[\xi\mathds{1}_{-k\leq\xi\leq k-\mu}\right]$
$\displaystyle\qquad+\mathbb{E}\left[\frac{1}{2}\left(\xi+\mu+k\right)^{2}\mathds{1}_{-k-\mu\leq\xi\leq-k}\right]+\mathbb{E}\left[-\frac{1}{2}\left(\xi-k\right)^{2}\mathds{1}_{k-\mu\leq\xi\leq
k}\right]$ $\displaystyle=\frac{\mu^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\mu\right)-\mu\mathbb{E}\left[\xi\mathds{1}_{k-\mu\leq\xi\leq k}\right]$
$\displaystyle\qquad+\mathbb{E}\left[\frac{1}{2}\left(\xi+\mu+k\right)^{2}\mathds{1}_{-k-\mu\leq\xi\leq-k}\right]+\mathbb{E}\left[\left(\mu
k-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\mu\leq\xi\leq
k}\right]$ $\displaystyle=\frac{\mu^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\mu\right)+\mathbb{E}\left[\left(\mu
k-\mu\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\mu\leq\xi\leq
k}\right]$
$\displaystyle\qquad\qquad\qquad\qquad+\mathbb{E}\left[\frac{1}{2}\left(\xi+\mu+k\right)^{2}\mathds{1}_{-k-\mu\leq\xi\leq-k}\right]$
$\displaystyle\geq\frac{\mu^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\mu\right)+\mathbb{E}\left[\left(\mu
k-\mu\xi-\frac{1}{2}\left(\xi-k\right)^{2}\right)\mathds{1}_{k-\mu\leq\xi\leq
k}\right]$ $\displaystyle\geq\frac{\mu^{2}}{2}\mathbb{P}\left(-k\leq\xi\leq
k-\mu\right)$

where the last inequality follows from the fact:

$f(\xi)=\mu k-\mu\xi-\frac{1}{2}\left(\xi-k\right)^{2}\geq 0\ \ \ \forall\ \ \
\xi\in\left[k-\mu,k\right]\,.$

observing the fact that:

$\mathbb{E}\left[\tilde{H}_{k}(\xi+\mu)-\tilde{H}_{k}(\xi)\right]=\frac{k+1}{k}\mathbb{E}\left[H_{k}(\xi+\mu)-H_{k}(\xi)\right]\geq\mathbb{E}\left[H_{k}(\xi+\mu)-H_{k}(\xi)\right]$

we complete the proof for all $k>0$. Now for $k=0$ for $0<\mu<\delta$,

$\displaystyle\mathbb{E}\left[|\xi+\mu|-|\xi|\right]$
$\displaystyle=-\mu\mathbb{P}(\xi\leq-\mu)+\mu\mathbb{P}(\xi>0)+\mathbb{E}\left[(2\xi+\mu)\mathds{1}_{-\mu\leq\xi\leq
0}\right]$
$\displaystyle=\mu\mathbb{P}(0\leq\xi\leq\mu)+\mathbb{E}\left[(-2\xi+\mu)\mathds{1}_{0\leq\xi\leq\mu}\right]$
$\displaystyle=\mathbb{E}\left[(-2\xi+2\mu)\mathds{1}_{0\leq\xi\leq\mu}\right]$
$\displaystyle=2\int_{0}^{\mu}(\mu-x)f_{\xi}(x)\ dx$ $\displaystyle\geq
f_{\xi}(0)\int_{0}^{\mu}(\mu-x)\ dx$
$\displaystyle=\frac{\mu^{2}}{2}f_{\xi}(0)\,.$

This completes the proof.

###  B.2 Proof of Lemma A.1

###### Proof.

Although we assume continuous steps, our proof can be certainly extended to
the case when $S_{n}$ takes value $0$ with positive probability. The proof
critically uses Theorem 4 of Chapter 12 of Volume 2 of [14]. To keep the
notational similarity with the book, define:

$q_{n}=\mathbb{P}\left(\max_{1\leq i\leq n}S_{i}<0\right)$

and the corresponding generating function $q(s)$ as:

$q(s)=1+\sum_{n=1}^{\infty}s^{n}q_{n}\,.$

Then from equation (7.22) of Theorem 4, Chapter 12, Vol. 2 of [14] we have:

$\log{q(s)}=\sum_{n=1}^{\infty}\frac{s^{n}}{n}\mathbb{P}\left(S_{n}<0\right):=f(s)\iff
q(s)=e^{f(s)}\,.$ (B.3)

Now we need a lower bound on $q_{n}$. Note that from the property of the
generating function we have:

$q_{n}=n!q^{(n)}(0)\,.$

On the other hand from Faa di Bruno’s formula:

$\displaystyle q^{(n)}(0)=\left.\frac{d^{n}}{ds^{n}}e^{f(s)}\right|_{s=0}$
$\displaystyle=\left.\left[e^{f(s)}\sum\frac{n!}{m_{1}!1!^{m_{2}}m_{1}!2!^{m_{2}}\cdots
m_{n}!n!^{m_{n}}}\Pi_{j=1}^{n}\left(f^{(j)}(s)\right)^{m_{j}}\right]\right|_{s=0}$
$\displaystyle=\left.\left[e^{f(s)}\sum\frac{n!}{m_{1}!m_{2}!\cdots
m_{n}!}\Pi_{j=1}^{n}\left(\frac{f^{(j)}(s)}{j!}\right)^{m_{j}}\right]\right|_{s=0}$
$\displaystyle=\sum\frac{n!}{m_{1}!m_{2}!\cdots
m_{n}!}\Pi_{j=1}^{n}\left(\frac{f^{(j)}(0)}{j!}\right)^{m_{j}}$ (B.4)

where the sum runs over all the sequences $\\{m_{j}\\}_{j=1}^{n}$ such that:

$\sum_{i=1}^{n}im_{i}=n\,.$

Note that $f^{(j)}(0)$ is non-negative for $j$. Hence using only one sequence
with $m_{1}=\dots=m_{n-1}=0$ and $m_{n}=1$, equation (B.4) can lower bounded
as:

$\displaystyle\left.\frac{d^{n}}{ds^{n}}e^{f(s)}\right|_{s=0}\geq
f^{(n)}(0)\,.$

On the from the expression of $f(s)$ from equation (B.3) it is immediate that:

$f^{(n)}(0)=n!\frac{1}{n}\mathbb{P}\left(S_{n}<0\right)\,.$

Combining our findings we have:

$\displaystyle n!q_{n}=q^{(n)}(0)$
$\displaystyle=\left.\frac{d^{n}}{ds^{n}}e^{f(s)}\right|_{s=0}$
$\displaystyle\geq f^{(n)}(0)$
$\displaystyle=n!\frac{1}{n}\mathbb{P}\left(S_{n}<0\right)\,.$

This immediately implies $q_{n}\geq\mathbb{P}\left(S_{n}>0\right)/n$ which
completes our proof. ∎

###  B.3 Proof of Lemma A.2

From the definition of distribution of $\xi$ we have:

$F_{\xi}(t)=\frac{\frac{1}{2}+t^{\gamma}}{1+t^{\gamma}}\ \ \ \ t\geq 0\,.$

and

$F_{\xi}(-t)=1-F_{\xi}(t)=\frac{1}{2(1+t^{\gamma})}\,.$

Hence it is immediate that for any $t_{0}>0$:

$\frac{1}{2(1+t_{0}^{-\gamma})}\leq\sup_{t\geq
t_{0}}t^{\gamma}\bar{F}_{\xi}(t)=\sup_{t\geq
t_{0}}\frac{t^{\gamma}}{2(1+t^{\gamma})}\leq\frac{1}{2}$ (B.5)

For any fixed $k\geq 1$:

$\displaystyle\mathbb{P}\left(M\geq k\right)$ $\displaystyle=\sum_{j\geq
k}\mathbb{P}\left(M=j\right)$ $\displaystyle=\sum_{j\geq
k}\mathbb{P}\left(S_{i}>S_{j}\ \forall\ 0\leq i\leq j-1,S_{i}>S_{j}\ \forall\
i\geq j+1\right)$
$\displaystyle=\mathbb{P}\left(S_{1}>0,S_{2}>0,\dots\right)\sum_{j\geq
k}\mathbb{P}\left(\max_{1\leq i\leq j}S_{i}<0\right)$
$\displaystyle=p^{*}\sum_{j\geq k}\mathbb{P}\left(\max_{1\leq i\leq
j}S_{j}<0\right)\hskip 14.45377pt[p^{*}=P\left(S_{1}>0,S_{2}>0,\dots\right)]$
$\displaystyle\geq p^{*}\sum_{j\geq k}\frac{1}{j}P\left(S_{j}\leq 0\right)$
(B.6)

where the last inequality uses Lemma A.1. From the symmetry of the
distribution of $\xi$ we have:

$\displaystyle\mathbb{P}\left(S_{j}\leq 0\right)$
$\displaystyle=\mathbb{P}\left(\sum_{i=1}^{j}\xi_{j}\leq-j\mu\right)=\mathbb{P}\left(\sum_{i=1}^{j}\xi_{j}>j\mu\right)\,.$

Set $a_{j}=j^{1/\gamma}$. Define the event $A_{i}$ as:

$A_{i}=\left\\{\xi_{i}>j\mu+(j-1)a_{j},\ \xi_{l}\in[-a_{j},j\mu)\ \forall\
1\leq l\neq i\leq j\right\\}$

Clearly $\\{A_{i}\\}^{\prime}s$ are disjoint events and

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{j}\xi_{j}>j\mu\right)$
$\displaystyle\geq\mathbb{P}\left(\cup_{i=1}^{j}A_{i}\right)$
$\displaystyle=\sum_{i=1}^{j}\mathbb{P}(A_{i})$
$\displaystyle=j\bar{F}\left(j\mu+(j-1)a_{j}\right)\left(F[-a_{j},j\mu)\right)^{j-1}$
$\displaystyle=j\bar{F}\left(j\mu+(j-1)a_{j}\right)\left(1-\bar{F}(a_{j})-\bar{F}(j\mu)\right)^{j-1}$
(B.7)

Next note that, $j\mu+(j-1)a_{j}\geq\mu$ for all $j\geq 1$. Therefore from
equation (B.5) we have for all $j\geq 1$:

$\bar{F}\left(j\mu+(j-1)a_{j}\right)\geq\frac{\left(j\mu+(j-1)a_{j}\right)^{-\gamma}}{2(1+\mu^{-\gamma})}\,,$

which further implies:

$\displaystyle j\times\bar{F}\left(j\mu+(j-1)a_{j}\right)$
$\displaystyle\geq\frac{1}{{2(1+\mu^{-\alpha})}}\frac{j}{\left(j\mu+(j-1)a_{j}\right)^{\gamma}}$
$\displaystyle=\frac{1}{{2(1+\mu^{-\gamma})}}\frac{j}{\left(j\mu+(j-1)j^{1/\alpha}\right)^{\gamma}}$
$\displaystyle=\frac{1}{{2(1+\mu^{-\gamma})}}\frac{j}{j^{\gamma+1}\left(j^{-1/\gamma}\mu+\left(1-\frac{1}{j}\right)\right)^{\gamma}}$
$\displaystyle=\frac{1}{j^{\gamma}}\ \frac{1}{{2(1+\mu^{-\gamma})}}\
\frac{1}{\left(j^{-1/\gamma}\mu+\left(1-\frac{1}{j}\right)\right)^{\gamma}}$
$\displaystyle\geq\frac{1}{j^{\gamma}}\ \frac{1}{{2(1+\mu^{-\gamma})}}\
\frac{1}{(\mu+1)^{\gamma}}:=\frac{c_{1}}{j^{\gamma}}\,.$

Next observe that $(j\mu)^{\gamma}\geq j$ for all $j\geq 1$ if $\mu>1$ or for
all $j\geq\mu^{-\gamma/(\gamma-1)}$ if $\mu\leq 1$. Using this in equation
(B.7) we have for all $j\geq 1\vee\lceil\mu^{-\gamma/(\gamma-1)}\rceil$:

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{j}\xi_{j}>j\mu\right)$
$\displaystyle\geq\frac{c_{1}}{j^{\gamma}}\left[\left(1-\bar{F}(a_{j})-\bar{F}(j\mu)\right)^{j-1}\right]$
$\displaystyle\geq\frac{c_{1}}{j^{\gamma}}\times\left(1-\frac{1}{2(1+a_{j}^{\alpha})}-\frac{1}{2(1+(j\mu)^{\alpha})}\right)^{j-1}$
$\displaystyle=\frac{c_{1}}{j^{\gamma}}\times\left(1-\frac{1}{2(1+j)}-\frac{1}{2(1+(j\mu)^{\alpha})}\right)^{j-1}$
$\displaystyle\geq\frac{c_{1}}{j^{\gamma}}\times\left(1-\frac{1}{(1+j)}\right)^{j-1}$
$\displaystyle\geq\frac{c_{1}}{j^{\gamma}}\times\inf_{x\geq
1}\left(1-\frac{1}{(1+x)}\right)^{x-1}$
$\displaystyle:=\frac{c_{1}c_{2}}{j^{\gamma}}$ (B.8)

Using this in equation (B.6) we obtain:

$\displaystyle P\left(M\geq k\right)$ $\displaystyle\geq p^{*}\sum_{j\geq
k}\frac{1}{j}P\left(S_{j}\leq 0\right)$ $\displaystyle=p^{*}\sum_{j\geq
k}\frac{1}{j}\left(\sum_{i=1}^{j}\xi_{j}>j\mu\right)$ $\displaystyle\geq
c_{1}c_{2}\times p^{*}\times\sum_{j\geq k}j^{-(\gamma+1)}$ $\displaystyle\geq
c_{1}c_{2}\times p^{*}\times\int_{k}^{\infty}x^{-(\gamma+1)}\ dx$
$\displaystyle\geq c_{1}c_{2}\times p^{*}\times\frac{1}{\gamma k^{\gamma}}\,.$

This completes the proof of lower bound.

###  B.4 Proof of Lemma A.3

We have, by symmetry:

$\mathbb{P}\left(|M_{ts}|>k\right)=\mathbb{P}\left(M_{ts}>k\right)+\mathbb{P}\left(M_{ts}<-k\right)=2\mathbb{P}\left(M_{ts}>k\right)\,.$

Hence, by virtue of Lemma A.2, all we need to show is:

$P(M_{ts}=k)\geq p^{*}\mathbb{P}(M_{os}=k)\,.$

Towards that end:

$\displaystyle\mathbb{P}\left(M_{ts}=k\right)$
$\displaystyle=\mathbb{P}\left(S_{K}\leq S_{i}\ \forall\ 0\leq i\leq
k-1,S_{k}\leq S_{i}\ \forall\ i\geq k+1,S_{k}\leq\inf_{j\geq 1}S_{-j}\right)$
$\displaystyle=\mathbb{P}\left(S_{K}\leq S_{i}\ \forall\ 0\leq i\leq
k-1,S_{k}\leq\inf_{j\geq 1}S_{-j}\right)\mathbb{P}\left(S_{i}\geq 0\ \forall\
i\geq 1\right)$ $\displaystyle=p^{*}\mathbb{P}\left(S_{K}\leq S_{i}\ \forall\
0\leq i\leq k-1,S_{k}\leq\inf_{j\geq 1}S_{-j}\right)$ $\displaystyle\geq
p^{*}\mathbb{P}\left(S_{K}\leq S_{i}\ \forall\ 0\leq i\leq
k-1,S_{k}\leq\inf_{j\geq 1}S_{-j}\mid\inf_{j\geq
1}S_{-j}>0\right)\mathbb{P}\left(\inf_{j\geq 1}S_{-j}>0\right)$
$\displaystyle=p^{*}\mathbb{P}\left(\inf_{j\geq
1}S_{-j}>0\right)\mathbb{P}\left(S_{K}\leq S_{i}\ \forall\ 0\leq i\leq
k-1\right)$ $\displaystyle=\mathbb{P}\left(\inf_{j\geq
1}S_{-j}>0\right)\mathbb{P}\left(M_{os}=k\right)$
$\displaystyle=p^{*}\mathbb{P}\left(M_{os}=k\right)\,.$

where the last equality follows from the fact:

$\mathbb{P}\left(M_{os}=k\right)=p^{*}\mathbb{P}\left(S_{K}\leq S_{i}\
\forall\ 0\leq i\leq k-1\right)$

This completes the proof.

###  B.5 Proof of Lemma A.4

Using same line of arguments as in Corollary 1:

$\displaystyle\mathbb{P}\left(M_{ts,CPP}=x\right)$
$\displaystyle=\sum_{k=0}^{\infty}\mathbb{P}\left(M_{ts,CPP}=x\mid
N_{1}(x)=k\right)\mathbb{P}(N_{1}(x)=k)$
$\displaystyle=\sum_{k=0}^{\infty}\mathbb{P}\left(M_{ts}=k\right)\mathbb{P}(N_{1}(x)=k)$
$\displaystyle\geq
p^{*}\sum_{k=0}^{\infty}\mathbb{P}\left(M_{os}=k\right)\mathbb{P}(N_{1}(x)=k)$
$\displaystyle=\mathbb{P}\left(M_{os,CPP}=x\right)$

Hence to establish Corollary A.4, all we need show:

$\mathbb{P}\left(M_{os,CPP}>x\right)\geq\frac{c_{0}}{2f_{X}^{\gamma}(d_{0})}x^{-\gamma}$

for all large $x$, where $M$ is the argmin of one sided compound Poisson
process, namely the minimizer of the following:

$X_{+}(t)=\sum_{i=1}^{N_{1}(t)}X_{i}\,,\ \ \ t\in\mathbb{R}^{+}\,.$

Now we have:

$\displaystyle P(M_{os,CPP}>x)$
$\displaystyle=\sum_{k=0}^{\infty}\mathbb{P}\left(M_{os,CPP}>x\mid
N_{1}(x)=k\right)\mathbb{P}\left(N_{1}(x)=k\right)$
$\displaystyle=\sum_{k=0}^{\infty}\mathbb{P}\left({\arg\min}_{i\geq
0}S_{i}>k\right)\mathbb{P}\left(N_{1}(x)=k\right)$
$\displaystyle\geq\sum_{k=k_{0}}^{\infty}\mathbb{P}\left({\arg\min}_{i\geq
0}S_{i}>k\right)\mathbb{P}\left(N_{1}(x)=k\right)$ $\displaystyle\geq
c_{0}\sum_{k=k_{0}}^{\infty}k^{-\gamma}\mathbb{P}\left(N_{1}(x)=k\right)$
$\displaystyle=c_{0}\sum_{k=k_{0}}^{\infty}\frac{e^{-\Lambda(x)}\Lambda(x)^{k}}{k!k^{\gamma}}$
$\displaystyle\geq
c_{0}\sum_{k=k_{0}}^{\infty}\frac{e^{-\Lambda(x)}\Lambda(x)^{k}}{k!(k+1)(k+2)\dots(k+\gamma)}$
$\displaystyle=c_{0}\sum_{k=k_{0}}^{\infty}\frac{e^{-\Lambda(x)}\Lambda(x)^{k}}{(k+\gamma)!}$
$\displaystyle=c_{0}\Lambda(x)^{-\gamma}\sum_{k=k_{0}+\alpha}^{\infty}\frac{e^{-\Lambda(x)}\Lambda(x)^{k}}{k!}$
$\displaystyle=c_{0}\Lambda(x)^{-\gamma}\mathbb{P}\left(N_{1}(x)\geq
k_{0}+\alpha\right)$
$\displaystyle\geq\frac{c_{0}}{2}\Lambda(x)^{-\gamma}=\frac{c_{0}}{2f_{X}^{\gamma}(d_{0})}x^{-\gamma}$

where the last inequality is valid as long as ${\sf
med}\left(N_{1}(X)\right)\geq k_{0}+\gamma$. From [2], we know as
$N_{1}(x)\sim Poisson(xf_{X}(d_{0}))$, we have ${\sf
med}\left(N_{1}(x)\right)\geq xf_{X}(d_{0})-\log{2}$. Hence the inequality is
valid as long as $x\geq(k_{0}+\gamma+\log{2})/f_{X}(d_{0})$. From This
completes the proof.

###  B.6 Proof of Lemma A.5

###### Proof.

As per our model description, all the parallel change point processes are
i.i.d. Therefore $n(\hat{d}_{i}-d_{0,i})$ has same distribution across $1\leq
i\leq m$. Therefore, we henceforth define $F_{n}$ to be the distribution of
$n(\hat{d}-d_{0})$ and drop $i$ from subscript. From the definition of change
point estimator, we have:

$\displaystyle n(\hat{d}-d_{0})$ $\displaystyle=\text{mid
argmin}_{t}\sum_{i=1}^{n}\left(\xi_{i}+\frac{1}{2}\right)\left\\{\mathds{1}_{d_{0}<X_{i}\leq
d_{0}+\frac{t}{n}}\right\\}$ $\displaystyle\qquad\qquad\qquad+\text{mid
argmin}_{t}\sum_{i=1}^{n}\left(-\xi_{i}+\frac{1}{2}\right)\left\\{\mathds{1}_{d_{0}+\frac{t}{n}<X_{i}\leq
d_{0}}\right\\}$ $\displaystyle=\text{mid
argmin}_{t}\sum_{i=1}^{N_{n,+}(t)}\left(\xi_{i}+\frac{1}{2}\right)\mathds{1}_{t\geq
0}+\sum_{i=1}^{N_{n,-}(t)}\left(-\xi_{i}+\frac{1}{2}\right)\mathds{1}_{t<0}\,.$

Here the count processes $N_{n,+}(t)$ and $N_{n,-}(t)$ are defined as follows:
For $t\geq 0$,

$N_{n,+}(t)=\sum_{i=0}^{n}\mathds{1}_{d_{0}\leq X_{i}\leq
d_{0}+\frac{t}{n}}\sim\text{Bin}\left(n,F_{X}\left(d_{0}+\frac{t}{n}\right)-F_{X}(t)\right)$

and for $t<0$,

$N_{n,-}(t)=\sum_{i=0}^{n}\mathds{1}_{d_{0}+\frac{t}{n}\leq X_{i}\leq
d_{0}}\sim\text{Bin}\left(n,F_{X}(t)-F_{X}\left(d_{0}+\frac{t}{n}\right)\right)\,.$

These processes can be though as finite sample approximation of Compound
Poisson Process, where we have approximated the Poisson random variables by
Binomial random variables. It is immediate that:

$\displaystyle N_{n,+}(t)$
$\displaystyle\overset{\mathscr{L}}{\implies}\text{Pois}\left(tf(d_{0})\right)\,,$
$\displaystyle N_{n,-}(t)$
$\displaystyle\overset{\mathscr{L}}{\implies}\text{Pois}\left(-tf(d_{0})\right)\,.$

We name the process as _compound Binomial process_ and henceforth denote by
CBP:

$CBP(t)=\sum_{i=1}^{N_{n,+}(t)}\left(\xi_{i}+\frac{1}{2}\right)\mathds{1}_{t\geq
0}+\sum_{i=1}^{N_{n,-}(t)}\left(-\xi_{i}+\frac{1}{2}\right)\mathds{1}_{t<0}$
(B.9)

Hence we work with the smallest argmin instead of mid-argmin just for some
technical simplicity, but all of the following analysis is valid for mid-
argmin also. As will be evident later, the thickness of the tail of the
distribution $F_{n}$ (the distribution of $n(\hat{d}-d_{0})$) is closely
related to the tail of the minimizer of a random walk with finitely many
steps. Therefore, we start by establishing a lower bound on the tail of a
n-step random walk $\\{S_{i}\\}_{i=0}^{n}$ with the usual convention $S_{0}=0$
and step distribution $X_{i}\overset{d}{=}\xi_{i}+1/2$. Let $Z_{n}$ be the
minimizer of this random walk. The random variable $Z_{n}$ is supported on
$\\{0,1,\dots,n\\}$. Then for any $0\leq k\leq n-1$:

$\displaystyle\mathbb{P}\left(Z_{n}>k\right)$
$\displaystyle=\sum_{j=k+1}^{n}\mathbb{P}\left(Z_{n}=j\right)$
$\displaystyle=\sum_{j=k+1}^{n}\mathbb{P}\left(S_{i}>S_{j}\ \forall\ 0\leq
i\leq j-1,S_{i}>S_{j}\ \forall\ j+1\leq i\leq n\right)$
$\displaystyle=\sum_{j=k+1}^{n}P\left(S_{i}<0\ \forall\ 1\leq i\leq
j\right)\mathbb{P}\left(S_{i}>0\ \forall\ 1\leq i\leq n-j\right)$
$\displaystyle\geq\mathbb{P}\left(S_{i}>0\ \forall\ 1\leq
i<\infty\right)\sum_{j=k+1}^{n}\mathbb{P}\left(\max_{1\leq i\leq
j}S_{i}<0\right)$
$\displaystyle=p^{*}\sum_{j=k+1}^{n}\mathbb{P}\left(\max_{1\leq i\leq
j}S_{j}<0\right)\hskip 14.45377pt\left[p^{*}=\mathbb{P}\left(\min_{1\leq
i<\infty}S_{i}>0\right)\right]$ $\displaystyle\geq
p^{*}\sum_{j=k+1}^{n}\frac{1}{j}\mathbb{P}\left(S_{j}\leq 0\right)$ (B.10)

From equation (B.8) in the proof of Lemma A.2 we conclude for $j\geq
2^{\gamma/(\gamma-1)}:=k_{0}$:

$\mathbb{P}\left(S_{j}\leq 0\right)\geq\frac{c_{1}c_{2}}{j^{\gamma}}\,.$

Using the above bound in equation (B.10) we conclude:

$\displaystyle\mathbb{P}\left(Z_{n}>k\right)$ $\displaystyle\geq
p^{*}\sum_{j=k+1}^{n}\frac{1}{j}\mathbb{P}\left(S_{j}\leq 0\right)$
$\displaystyle\geq
p^{*}\sum_{j=k+1}^{n}\frac{1}{j}\frac{c_{1}c_{2}}{j^{\gamma}}$
$\displaystyle=c_{1}c_{2}p^{*}\sum_{j=k+1}^{n}\frac{1}{j^{\gamma+1}}$
$\displaystyle\geq c_{1}c_{2}p^{*}\int_{k+1}^{n+1}x^{-(\gamma+1)}\ dx\hskip
14.45377pt[\text{Riemann integral lower bound}]$
$\displaystyle=\frac{c_{1}c_{2}p^{*}}{\gamma}\left[\frac{1}{(k+1)^{\gamma}}-\frac{1}{(n+1)^{\gamma}}\right]$
(B.11)

Now we go back to the random variable of interest $n(\hat{d}-d_{0})$. Let
$X_{(i)}$ denotes the $i^{th}$ order statistics of $\\{X_{i}\\}_{i\leq n}$. If
$X_{(i)}<d_{0}<X_{(i+1)}$, then from the definition of $n(\hat{d}-d_{0})$, we
have a random walk with $i$ steps on the negative axis and a random walk with
$n-i$ steps on the positive axis. Therefore the number of steps of random walk
on either side of origin is equal to the number of $X_{i}^{\prime}s$ on the
corresponding side of $d_{0}$. Denote by $R_{n}$ (and respectively $L_{n}$),
the number of $X_{i}^{\prime}s$ greater than $d_{0}$ (respectively less than
$d_{0}$). Hence $R_{n}\sim\text{Bin}(n,\bar{F}_{X}(d_{0}))$ and
$L_{n}\sim\text{Bin}(n,F_{X}(d_{0}))$ with $R_{n}+L_{n}=n$. Then we have for
any $x>0$:

$\displaystyle\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)$
$\displaystyle=\sum_{r=0}^{n}\sum_{k=0}^{r}\mathbb{P}\left(n(\hat{d}-d_{0})>x\mid
R_{n}=r,N_{n,+}(x)=k\right)\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)$

Given $R_{n}=r$, we have a two sided random walk, with $r$ steps on the
positive real line $n-r$ steps on the negative real line. Therefore, the event
$n(\hat{d}-d_{0})>x$ given $N_{n,+}(x)=k$ and $R_{n}=r$ is equivalent to the
event that in a two sided random walks with $r$ steps on the right and $n-r$
steps on the left, the argmin is on the right and it happens after $k$ steps.
More precisely, if we denote by $S_{0}\equiv 0,S_{1},\dots,S_{r}$ to be the
random walk on the right side with step distribution $(\xi+1/2)$ and
$S^{\prime}_{0}\equiv 0,S^{\prime}_{1},\dots,S^{\prime}_{n-r}$ to be random
walk on the left with step distribution $(-\xi+1/2)$, then the above event
corresponds that this two sided random walk is minimized at $S_{j}$ for some
$k+1\leq j\leq r$. Therefore we write:

$\displaystyle\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)$
$\displaystyle=\sum_{r=0}^{n}\sum_{k=0}^{r}\mathbb{P}\left(n(\hat{d}-d_{0})>x\mid
R_{n}=r,N_{n,+}(x)=k\right)\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)$
$\displaystyle=\sum_{r=0}^{n}\sum_{k=0}^{r}\left[\mathbb{P}\left({\arg\min}\text{
of twosided RW }>k\right)\times\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right]$ (B.12)

Next, we obtain a lower bound on the tail of the minimizer of the two sided
random walk. Note that, we have already established a lower bound on the tail
of the minimizer of a one sided random walk in equation (B.11), which we
exploit here to get a lower bound on the tail of the minimizer of this two-
sided incarnation:

$\displaystyle\mathbb{P}\left({\arg\min}\text{ twosided RW }>k\right)$
$\displaystyle=\sum_{j=k+1}^{r}\mathbb{P}\left({\arg\min}\text{ twosided RW
}=j\right)$
$\displaystyle=\sum_{j=k+1}^{r}\mathbb{P}\left(S_{j}<S_{0},\dots,S_{j}<S_{j-1},S_{j}<S_{j+1},\dots,S_{j}<S_{r},S_{j}<\min_{1\leq
i\leq n-r}S^{\prime}_{i}\right)$
$\displaystyle=\sum_{j=k+1}^{r}\mathbb{P}\left(S_{j}<S_{0},\dots,S_{j}<S_{j-1},S_{j}<\min_{1\leq
i\leq n-r}S^{\prime}_{i}\right)\mathbb{P}(S_{1}>0,\dots,S_{r-j}>0)$
$\displaystyle\geq\sum_{j=k+1}^{r}\mathbb{P}\left(S_{j}<S_{0},\dots,S_{j}<S_{j-1},S_{j}<\min_{1\leq
i\leq n-r}S^{\prime}_{i}\mid\min_{1\leq i\leq
n-r}S^{\prime}_{i}>0\right)\times$ $\displaystyle\hskip
150.00023pt\mathbb{P}\left(\min_{1\leq i\leq
n-r}S^{\prime}_{i}>0\right)\mathbb{P}(S_{1}>0,\dots,S_{r-j}>0)$
$\displaystyle\geq
p^{*}\sum_{j=k+1}^{r}\mathbb{P}\left(S_{j}<S_{0},\dots,S_{j}<S_{j-1},S_{j}<\min_{1\leq
i\leq n-r}S^{\prime}_{i}\mid\min_{1\leq i\leq
n-r}S^{\prime}_{i}>0\right)\times$ $\displaystyle\hskip
250.00038pt\mathbb{P}(S_{1}>0,\dots,S_{r-j}>0)$
$\displaystyle=p^{*}\sum_{j=k+1}^{r}\mathbb{P}\left(S_{j}<S_{0},\dots,S_{j}<S_{j-1}\right)\mathbb{P}(S_{1}>0,\dots,S_{r-j}>0)$
$\displaystyle=p^{*}\mathbb{P}\left({\arg\min}\text{ one-sided RW with length
}r>k\right)$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}\left[\frac{1}{(k+1)^{\gamma}}-\frac{1}{(r+1)^{\gamma}}\right]\hskip
14.45377pt[\text{From equation }\eqref{eq:finite_sample_rw_lower_bound}]\,.$

For the rest of the calculation we assume $\gamma$ (the number of finite
moments of the error distribution $\xi$) is an integer, as all our calculation
is valid by replacing $\gamma$ by $\lfloor\gamma\rfloor$. Define a success
probability $p_{x,n}$ as:

$p_{x,n}=\mathbb{P}\left(X\in\left(d_{0}+\frac{x}{n},d_{0}\right)\mid
X>d_{0}\right)=\frac{F_{X}\left(d_{0}+\frac{x}{n},d_{0}\right)-F_{X}(d_{0})}{1-F_{X}(d_{0})}\,.$

Therefore it is immediate that:

$N_{n,+}(x)\mid R_{n}=r\sim\text{Bin}\left(r,p_{x,n}\right)\,.$

As per our assumption $F_{X}$ has continuous density $f_{X}$ with
$f_{X}(d_{0})>0$. Therefore, there exists $\delta_{1}>0$ such that
$f_{X}(t)>f_{X}(d_{0})/2$ for $|t-d_{0}|\leq\delta_{1}$. Hence, for any $0\leq
x\leq n\delta_{1}$, we have:

$p_{x,n}\geq\frac{x}{n}\times\frac{f_{X}(d_{0})}{2(1-F_{X}(d_{0}))}\,.$ (B.13)

On the other, let $f_{\max}$ be the upper bound on $f_{X}$ on the entire
$\mathbb{R}$. Then, again from the mean value theorem, we have:

$p_{x,n}\leq\frac{x}{n}\times\frac{f_{\max}}{2(1-F_{X}(d_{0}))}\,.$ (B.14)

Therefore combining equations (B.13) and (B.14), we have:

$\frac{x}{n}\times\frac{f_{X}(d_{0})}{2(1-F_{X}(d_{0}))}\leq
p_{x,n}\leq\frac{x}{n}\times\frac{f_{\max}}{2(1-F_{X}(d_{0}))}\,.$ (B.15)

We will use the above relations in our rest of the calculation. Going back to
equation (B.12) we have:

$\displaystyle\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)$
$\displaystyle=\sum_{r=1}^{n}\sum_{k=0}^{r}\left[\mathbb{P}\left({\arg\min}\text{
twosided RW }>k\right)\times\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right]$
$\displaystyle=\sum_{r=k_{0}}^{n}\sum_{k=k_{0}}^{r}\left[\mathbb{P}\left({\arg\min}\text{
twosided RW }>k\right)\times\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}\sum_{r=1}^{n}\sum_{k=0}^{r}\left[\frac{1}{(k+1)^{\gamma}}-\frac{1}{(r+1)^{\gamma}}\right]\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)$
$\displaystyle=\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}\left[\sum_{r=k_{0}}^{n}\sum_{k=k_{0}}^{r}\frac{1}{(k+1)^{\gamma}}\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right.$ $\displaystyle\hskip
150.00023pt\left.-\sum_{r=k_{0}}^{n}\frac{1}{(r+1)^{\gamma}}\mathbb{P}(k_{0}\leq
N_{n,+}(x)<r\mid R_{n}=r)\mathbb{P}(R_{n}=r)\right]$
$\displaystyle=\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}\left[\sum_{r=k_{0}}^{n}\sum_{k=k_{0}}^{r}\frac{1}{(k+1)^{\gamma}}\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right.$ $\displaystyle\hskip
150.00023pt\left.-\sum_{r=1}^{n}\frac{1}{(r+1)^{\gamma}}\mathbb{P}(R_{n}=r)\right]$
$\displaystyle=\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}\left[\sum_{r=k_{0}}^{n}\sum_{k=k_{0}}^{r}\frac{1}{(k+1)^{\gamma}}\dbinom{r}{k}p_{x,n}^{k}(1-p_{x,n})^{r-k}\mathbb{P}(R_{n}=r)\right.$
$\displaystyle\hskip
150.00023pt\left.-\sum_{r=1}^{n}\frac{1}{(r+1)^{\gamma}}\mathbb{P}(R_{n}=r)\right]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}\left[\sum_{r=k_{0}}^{n}\left\\{\sum_{k=k_{0}}^{r}\frac{1}{(k+1)^{\gamma}}\dbinom{r}{k}p_{x,n}^{k}(1-p_{x,n})^{r-k}\right\\}\mathbb{P}(R_{n}=r)-\sum_{r=1}^{n}\frac{1}{(r+1)^{\gamma}}\mathbb{P}(R_{n}=r)\right]$
(B.16)

where the last inequality is obtained by replacing $1-p_{x,n}$ by its upper
bound 1. The inner sum of the above equation can be analyzed as follows:

$\displaystyle\sum_{k=k_{0}}^{r}\frac{1}{(k+1)^{\gamma}}\dbinom{r}{k}p_{x,n}^{k}(1-p_{x,n})^{r-k}$
$\displaystyle=\sum_{k=k_{0}}^{r}\frac{1}{(k+1)^{\gamma}}\frac{r!}{k!(r-k)!}p_{x,n}^{k}(1-p_{x,n})^{r-k}$
$\displaystyle\geq\sum_{k=k_{0}}^{r}\frac{1}{(k+1)(k+2)\dots(k+\gamma)}\frac{r!}{k!(r-k)!}p_{x,n}^{k}(1-p_{x,n})^{r-k}$
$\displaystyle\geq\frac{p_{x,n}^{-\gamma}}{(r+1)(r+2)\dots(r+\gamma)}\sum_{k=k_{0}}^{r}\frac{(r+\gamma)!}{(k+\gamma)!(r-k)!}p_{x,n}^{k+\gamma}(1-p_{x,n})^{r-k}$
$\displaystyle=\frac{p_{x,n}^{-\gamma}}{(r+1)(r+2)\dots(r+\gamma)}\mathbb{P}\left(\text{Bin}(r+\gamma,p_{x,n})\geq
k_{0}+\gamma\right)\,.$

Putting this back into equation (B.16) we obtain:

$\displaystyle\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}p_{x,n}^{-\gamma}\left[\sum_{r=k_{0}}^{n}\frac{\mathbb{P}\left(\text{Bin}(r+\gamma,p_{x,n})\geq
k_{0}+\gamma\right)}{(r+1)(r+2)\dots(r+\gamma)}\mathbb{P}(R_{n}=r)-p_{x,n}^{\gamma}\sum_{r=1}^{n}\frac{1}{(r+1)^{\gamma}}\mathbb{P}(R_{n}=r)\right]$
(B.17)

Now from the properties of the inverse moments of the binomial distribution
(see e.g. [11]) we have:

$\sum_{r=1}^{n}\frac{1}{(r+1)^{\gamma}}\mathbb{P}(R_{n}=r)\leq
C\left(n\bar{F}_{X}(d_{0})\right)^{-\gamma}\hskip 14.45377pt[\text{Recall
}R_{n}\sim\text{Bin}(n,\bar{F}_{X}(d_{0}))]\,.$

On the other hand we have for all $r\geq n\bar{F}_{X}(d_{0})$:

$\displaystyle(r+\gamma)p_{x,n}$
$\displaystyle\geq(n\bar{F}_{X}(d_{0})+\gamma)\times\frac{x}{n}\times\frac{f_{X}(d_{0})}{2(1-F_{X}(d_{0}))}\hskip
14.45377pt[\text{Equation }\eqref{eq:pxn_lb}]$
$\displaystyle\geq\left(\bar{F}_{X}(d_{0})+\frac{\gamma}{n}\right)\times
x\times\frac{f_{X}(d_{0})}{2(1-F_{X}(d_{0}))}$
$\displaystyle\geq\bar{F}_{X}(d_{0})\times
x\times\frac{f_{X}(d_{0})}{2(1-F_{X}(d_{0}))}>\gamma+k_{0}$

for all $x>2(\gamma+k_{0})/f_{X}(d_{0})$. Now we know that the median of
$Bin(n,p)$ is $\lfloor np\rfloor$ or $\lceil np\rceil$. For simplicity, we
will use the bound here $\mathbb{P}(Bin(n,p)\geq np)\geq 1/2$ as it will be
valid simply replacing $np$ by $\lfloor np\rfloor$ and this will not alter any
of our subsequent analysis. Therefore we have:

$\displaystyle\sum_{r=k_{0}}^{n}\frac{\mathbb{P}\left(\text{Bin}(r+\gamma,p_{x,n})\geq\gamma+k_{0}\right)}{(r+1)(r+2)\dots(r+\gamma)}\mathbb{P}(R_{n}=r)$
$\displaystyle\geq\sum_{r=n\bar{F}(d_{0})}^{n}\frac{\mathbb{P}\left(\text{Bin}(r+\gamma,p_{x,n})\geq\gamma+k_{0}\right)}{(r+1)(r+2)\dots(r+\gamma)}\mathbb{P}(R_{n}=r)$
$\displaystyle\geq\sum_{r=n\bar{F}(d_{0})}^{n}\frac{1}{2(r+1)(r+2)\dots(r+\gamma)}\mathbb{P}(R_{n}=r)$
$\displaystyle\geq\frac{1}{2(n+1)(n+2)\dots(n+\gamma)}\sum_{r=n\bar{F}(d_{0})}^{n}\mathbb{P}(R_{n}=r)$
$\displaystyle\geq\frac{1}{4(n+1)(n+2)\dots(n+\gamma)}\,.$

Going back to equation (B.17) we have:

$\displaystyle\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}p_{x,n}^{-\gamma}\left[\sum_{r=k_{0}}^{n}\frac{\mathbb{P}\left(\text{Bin}(r+\gamma,p_{x,n})\geq\gamma\right)}{(r+1)(r+2)\dots(r+\gamma)}\mathbb{P}(R_{n}=r)-p_{x,n}^{\gamma}\sum_{r=1}^{n}\frac{1}{(r+1)^{\gamma}}\mathbb{P}(R_{n}=r)\right]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}p_{x,n}^{-\gamma}\left[\frac{1}{4(n+1)(n+2)\dots(n+\gamma)}-p_{x,n}^{\gamma}\frac{C(\bar{F}(d_{0}))^{-\gamma}}{n^{\gamma}}\right]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}x^{\gamma}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\left[\frac{n^{\gamma}}{4(n+1)(n+2)\dots(n+\gamma)}-(np_{x,n})^{\gamma}\frac{C(\bar{F}(d_{0}))^{-\gamma}}{n^{\gamma}}\right]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}x^{\gamma}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\left[\frac{1}{4(2^{\gamma})}-(np_{x,n})^{\gamma}\frac{C(\bar{F}(d_{0}))^{-\gamma}}{n^{\gamma}}\right]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}x^{\gamma}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\left[\frac{1}{4(2^{\gamma})}-\left(x\times\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{\gamma}\frac{C(\bar{F}(d_{0}))^{-\gamma}}{n^{\gamma}}\right]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}x^{\gamma}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\left[\frac{1}{4(2^{\gamma})}-\left(\frac{\delta_{2}f_{X,\max}}{C(1-F_{X}(d_{0}))^{2}}\right)^{\gamma}\right]\hskip
14.45377pt[\forall\ x\leq\delta_{2}n]$
$\displaystyle\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\times\frac{1}{2^{\gamma+3}}\times
x^{-\gamma}$ $\displaystyle=\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma
2^{\gamma+3}}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\times
x^{-\gamma}\,.$

where the last inequality is valid for small enough $\delta_{2}$, i.e. we
choose $\delta_{2}$ which satisfies:

$\frac{1}{2^{\gamma+2}}-\left(\frac{\delta_{2}f_{X,\max}}{C(1-F_{X}(d_{0}))^{2}}\right)^{\gamma}\geq\frac{1}{2^{\gamma+3}}\,.$

Therefore we have established that for any $2\gamma/f_{X}(d_{0})\leq
x\leq(\delta_{1}\wedge\delta_{2})n$:

$\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)\leq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma
2^{\gamma+3}}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\times
x^{-\gamma}\,.$ (B.18)

The calculation for the negative $x$ is similar. As introduced before, $L_{n}$
denotes the number of $X_{i}^{\prime}s$ on the left of $d_{0}$ and
$L_{n}\sim\text{Bin}(n,F(d_{0}))$. Given $L_{n}=l$, define $S_{0}\equiv
0,S^{\prime}_{1},\dots,S^{\prime}_{l}$ to be random walk on the left of origin
and $S_{0}=0,S_{1},S_{2},\dots,S_{n-l}$ on the right of origin. Given
$L_{n}=l,N_{n,-}(x)=k^{\prime}$, the event $n(\hat{d}-d_{0})<-x$ is equivalent
to the event that in a two sided random walk with $l$ steps on the left and
$n-l$ steps on the right, the minima occurs on the left and it occurs at one
of the steps among
$\left\\{S^{\prime}_{k^{\prime}+1},S^{\prime}_{k^{\prime}+2},\dots,S^{\prime}_{l}\right\\}$.
Using the similar logic as above we obtain for any $2\gamma/f_{X}(d_{0})\leq
x\leq(\delta_{1}\wedge\delta_{2})n$:

$\mathbb{P}\left(n(\hat{d}-d_{0})<-x\right)\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma
2^{\gamma+3}}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\times
x^{-\gamma}\,.$ (B.19)

Finally, from equation (B.18) and (B.19) we conclude for any
$2\gamma/f_{X}(d_{0})\leq x\leq(\delta_{1}\wedge\delta_{2})n$:

$\mathbb{P}\left(\left|n(\hat{d}-d_{0})\right|>x\right)\geq\frac{c_{1}c_{2}(p^{*})^{2}}{\gamma
2^{\gamma+2}}\times\left(\frac{f_{X,\max}}{1-F_{X}(d_{0})}\right)^{-\gamma}\times
x^{-\gamma}\,.$

This completes the proof. ∎

###  B.7 Proof of Lemma A.6

We use the same notations as used in the proof of Lemma A.5. As $\xi_{i}$’s
are bounded by $b$ with mean $\mu>0$, by applying Hoeffding’s inequality, we
have for any $j\in\mathbb{N}$:

$\mathbb{P}\left(\bar{\xi}_{j}<-\mu\right)\leq
e^{-\frac{j\mu^{2}}{4b^{2}}}:=e^{-cj}\,,$

with $c=\mu^{2}/4b^{2}$. As in Lemma A.5, we start with establishing an upper
bound on the tail on the minimizer of random walk. Let
$\\{S_{j}\\}_{j=0,\dots,n}$ denotes a $n$-step random walk and let $Z_{n}$
denotes its minimizer supported on $\\{0,1,\dots,n\\}$. We then have:

$\displaystyle\mathbb{P}\left(Z_{n}>k\right)$
$\displaystyle=\sum_{j=k+1}^{n}\mathbb{P}\left(Z_{n}=j\right)$
$\displaystyle=\sum_{j=k+1}^{n}\mathbb{P}\left(S_{j}<0,\dots,S_{j}<S_{j-1},S_{j}<S_{j+1},\dots,S_{j}<S_{n}\right)$
$\displaystyle\leq\sum_{j=k+1}^{n}\mathbb{P}\left(S_{j}<0\right)$
$\displaystyle=\sum_{j=k+1}^{n}\mathbb{P}\left(\bar{\xi}_{j}<-\mu\right)$
$\displaystyle\leq\sum_{j=k+1}^{n}e^{-cj}=\frac{e^{-c(k+1)}}{1-e^{-c}}\,.$

Going back to distribution of $n(\hat{d}-d_{0})$, as in the proof of Lemma A.5
we have:

$\displaystyle\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)$
$\displaystyle=\sum_{r=0}^{n}\sum_{k=0}^{r}\mathbb{P}\left(n(\hat{d}-d_{0})>x\mid
R_{n}=r,N_{n,+}(x)=k\right)\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)$
$\displaystyle=\sum_{r=0}^{n}\sum_{k=0}^{r}\left[\mathbb{P}\left({\arg\min}\text{
twosided RW }>k\mid R_{n}=r,N_{n,+}(x)=k\right)\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\times\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right]$
$\displaystyle=\sum_{r=0}^{n}\sum_{k=0}^{r}\left[\mathbb{P}\left({\arg\min}\text{
twosided RW }>k\mid R_{n}=r\right)\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\times\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right]$ (B.20)

Upper bounding the argmin of two-sided random walk is relatively easier:

$\displaystyle\mathbb{P}\left({\arg\min}\text{ twosided RW }>k\mid
R_{n}=r\right)$
$\displaystyle=\sum_{j=k+1}^{r}\mathbb{P}\left({\arg\min}\text{ twosided RW
}=j\mid R_{n}=r\right)$
$\displaystyle=\sum_{j=k+1}^{r}\mathbb{P}\left(S_{j}<\min_{0\leq i\leq
j-1}S_{i},S_{j}<\min_{j+1\leq i\leq r}S_{i},S_{j}<\min_{1\leq i\leq
n-r}S^{\prime}_{i}\right)$
$\displaystyle\leq\sum_{j=k+1}^{r}\mathbb{P}\left(S_{j}<0\right)\leq\frac{e^{-c(k+1)}}{1-e^{-c}}\,.$

Using this bound in equation (B.20) we obtain for any $0\leq x\leq
n\delta_{1}$ (where $\delta_{1}$ is same as defined in the proof of Lemma A.5,
i.e. we choose $\delta_{1}>0$ such that $f_{X}(t)\geq f_{X}(d_{0})/2$ for all
$|t-d_{0}|\leq\delta_{1}$):

$\displaystyle\mathbb{P}\left(n(\hat{d}-d_{0})>x\right)$
$\displaystyle=\sum_{r=0}^{n}\sum_{k=0}^{r}\left[\mathbb{P}\left({\arg\min}\text{
twosided RW }>k\mid R_{n}=r\right)\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\times\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)\right]$
$\displaystyle\leq\sum_{r=0}^{n}\sum_{k=0}^{r}\frac{e^{-c(k+1)}}{1-e^{-c}}\mathbb{P}(N_{n,+}(x)=k\mid
R_{n}=r)\mathbb{P}(R_{n}=r)$
$\displaystyle\leq\frac{e^{-c}}{1-e^{-c}}\sum_{r=0}^{n}\sum_{k=0}^{r}e^{-ck}\
\mathbb{P}(N_{n,+}(x)=k\mid R_{n}=r)\mathbb{P}(R_{n}=r)$
$\displaystyle=\frac{e^{-c}}{1-e^{-c}}\sum_{r=0}^{n}\left(1-p_{n,x}+p_{n,x}e^{-c}\right)^{r}\mathbb{P}(R_{n}=r)$
$\displaystyle=\frac{e^{-c}}{1-e^{-c}}\left(1-\bar{F}(d_{0})+\bar{F}(d_{0})\left(1-p_{n,x}+p_{n,x}e^{-c}\right)\right)^{n}$
$\displaystyle=\frac{e^{-c}}{1-e^{-c}}\left(1-\bar{F}(d_{0})p_{n,x}(1-e^{-c})\right)^{n}$
$\displaystyle\leq\frac{e^{-c}}{1-e^{-c}}\left(1-(1-e^{-c})\frac{xf_{X}(d_{0})}{2n}\right)^{n}$
$\displaystyle\leq\frac{e^{-c}}{1-e^{-c}}e^{-x\frac{f_{X}(d_{0})}{2}(1-e^{-c})}\,.$

The calculation for $\mathbb{P}(n(\hat{d}-d_{0})<-x)$ for $x>0$ is similar and
hence skipped for brevity. Therefore we obtain for $0\leq|x|\leq n\delta_{1}$:

$\mathbb{P}\left(\left|n(\hat{d}-d_{0})\right|>x\right)\leq\frac{2e^{-c}}{1-e^{-c}}e^{-x\frac{f_{X}(d_{0})}{2}(1-e^{-c})}\,.$

This completes the proof.

###  B.8 Proof of Proposition A.7

From proposition 5 of [15] we have:

$\mathbb{E}\left\|\sum_{i=1}^{n}\xi
f(X_{i})\right\|_{\mathcal{F}}\leq\mathbb{E}\left[\sum_{k=1}^{n}\left(\left|\eta_{(k)}\right|-\left|\eta_{(k+1)}\right|\right)\mathbb{E}\left\|\sum_{i=1}^{k}{\epsilon}_{i}f(X_{i})\right\|_{\mathcal{F}}\right]$

where
$\left|\eta_{(1)}\right|\geq\left|\eta_{(2)}\right|\geq\dots\left|\eta_{(n)}\right|\geq\left|\eta_{(n+1)}\right|=0$
are the decreasing order statistics of
$\left\\{\left|\xi_{i}-\xi_{i}^{\prime}\right|\right\\}_{i=1}^{n}$ where
$\left\\{\xi_{i}^{\prime}\right\\}_{1\leq i\leq n}$ are i.i.d copy of
$\left\\{\xi_{i}\right\\}_{1\leq i\leq n}$. Hence we have:

$\displaystyle\mathbb{E}\left\|\sum_{i=1}^{n}\xi
f(X_{i})\right\|_{\mathcal{F}}$
$\displaystyle\leq\mathbb{E}\left[\sum_{k=1}^{n}\left(\left|\eta_{(k)}\right|-\left|\eta_{(k+1)}\right|\right)\mathbb{E}\left\|\sum_{i=1}^{k}{\epsilon}_{i}f(X_{i})\right\|_{\mathcal{F}}\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{k=1}^{n}\left(\left|\eta_{(k)}\right|-\left|\eta_{(k+1)}\right|\right)\left(\varphi_{n}(k)+b_{n}\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{i=1}^{n}\int_{\left|\eta_{(k+1)}\right|}^{\left|\eta_{(k)}\right|}\varphi_{n}(k)\
dt\right]+b_{n}\mathbb{E}\left[\left|\eta_{(1)}\right|\right]$
$\displaystyle\leq\mathbb{E}\left[\int_{0}^{\infty}\varphi_{n}\left(\left|\left\\{i:\left|\eta_{i}\right|\geq
t\right\\}\right|\right)\ dt\right]+b_{n}\mathbb{E}\left[\max_{1\leq i\leq
n}\left|\xi_{i}-\xi_{i}^{\prime}\right|\right]$
$\displaystyle\leq\int_{0}^{\infty}\varphi_{n}\left(\sum_{i=1}^{n}\mathbb{P}\left(|\xi_{i}-\xi_{i}^{\prime}|>t\right)\right)+2b_{n}\mathbb{E}\left[\max_{1\leq
i\leq n}\left|\xi_{i}\right|\right]\hskip 14.45377pt[\text{By Jensen's
inequality}]$
$\displaystyle\leq\int_{0}^{\infty}\varphi_{n}\left(\sum_{i=1}^{n}\left(\mathbb{P}\left(|\xi_{i}|>t/2\right)+\mathbb{P}\left(|\xi^{\prime}_{i}|>t/2\right)\right)\right)+2b_{n}\mathbb{E}\left[\max_{1\leq
i\leq n}\left|\xi_{i}\right|\right]$
$\displaystyle=\int_{0}^{\infty}\varphi_{n}\left(2\sum_{i=1}^{n}\mathbb{P}\left(|\xi_{i}|>t/2\right)\right)+2b_{n}\mathbb{E}\left[\max_{1\leq
i\leq n}\left|\xi_{i}\right|\right]$
$\displaystyle=2\int_{0}^{\infty}\varphi_{n}\left(2\sum_{i=1}^{n}\mathbb{P}\left(|\xi_{i}|>t\right)\right)+2b_{n}\mathbb{E}\left[\max_{1\leq
i\leq n}\left|\xi_{i}\right|\right]$ $\displaystyle\leq
4\int_{0}^{\infty}\varphi_{n}\left(\sum_{i=1}^{n}\mathbb{P}\left(|\xi_{i}|>t\right)\right)+2b_{n}\mathbb{E}\left[\max_{1\leq
i\leq n}\left|\xi_{i}\right|\right]$

where the last inequality follows from the fact that $\varphi_{n}(0)=0$ and
$\varphi_{n}$ concave which leads to $\varphi_{n}(2x)\leq 2\varphi_{n}(x)$.

## References

  * [1] Felix Abramovich and Vadim Grinshtein.  High-dimensional classification by sparse logistic regression.  arXiv preprint arXiv:1706.08344, 2017.
  * [2] José A Adell and P Jodrá.  The median of the poisson distribution.  Metrika, 61(3):337–346, 2005.
  * [3] Andrew Barron, Lucien Birgé, and Pascal Massart.  Risk bounds for model selection via penalization.  Probability theory and related fields, 113(3):301–413, 1999.
  * [4] Peter L Bartlett, Stéphane Boucheron, and Gábor Lugosi.  Model selection and error estimation.  Machine Learning, 48(1):85–113, 2002.
  * [5] S Basso, M Schirmer, and G Botter.  On the emergence of heavy-tailed streamflow distributions.  Advances in Water Resources, 82:98–105, 2015.
  * [6] Peter J Bickel, Ya’acov Ritov, Alexandre B Tsybakov, et al.  Simultaneous analysis of lasso and dantzig selector.  The Annals of Statistics, 37(4):1705–1732, 2009.
  * [7] Patrick Billingsley.  Convergence of probability measures.  John Wiley & Sons, 2013.
  * [8] Lucien Birgé.  A new lower bound for multiple hypothesis testing.  IEEE transactions on information theory, 51(4):1611–1615, 2005\.
  * [9] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration inequalities: A nonasymptotic theory of independence.  OUP Oxford, 2013.
  * [10] Brendan O Bradley and Murad S Taqqu.  Financial risk and heavy tails.  In Handbook of heavy tailed distributions in finance, pages 35–103. Elsevier, 2003.
  * [11] Francisco Cribari-Neto, Nancy Lopes Garcia, and Klaus LP Vasconcellos.  A note on inverse moments of binomial variates.  Brazilian Review of Econometrics, 20(2):269–277, 2000.
  * [12] Herbert Edelsbrunner.  Algorithms in combinatorial geometry, volume 10.  Springer Science & Business Media, 2012.
  * [13] Ailin Fan, Rui Song, and Wenbin Lu.  Change-plane analysis for subgroup detection and sample size calculation.  Journal of the American Statistical Association, 112(518):769–778, 2017.
  * [14] William Feller.  An introduction to probability theory and its applications.  1957.
  * [15] Qiyang Han, Jon A Wellner, et al.  Convergence rates of least squares regression estimators with heavy-tailed errors.  Annals of Statistics, 47(4):2286–2319, 2019.
  * [16] Felix Hernandez-Campos, JS Marron, Gennady Samorodnitsky, and F Donelson Smith.  Variable heavy tails in internet traffic.  Performance Evaluation, 58(2-3):261–284, 2004.
  * [17] Michael R Kosorok.  Introduction to empirical processes and semiparametric inference.  Springer Science & Business Media, 2007.
  * [18] Michael R Kosorok and Rui Song.  Inference under right censoring for transformation models with a change-point based on a covariate threshold.  The Annals of Statistics, 35(3):957–989, 2007.
  * [19] M.R. Kosorok.  Introduction to Empirical Processes and Semiparametric Inference.  Springer, New York, 2008.
  * [20] Yan Lan, Moulinath Banerjee, and George Michailidis.  Change-point estimation under adaptive sampling.  The Annals of Statistics, 37(4):1752–1791, 2009.
  * [21] Jialiang Li, Yaguang Li, and Baisuo Jin.  Multi-threshold change plane model: Estimation theory and applications in subgroup identification.  arXiv preprint arXiv:1808.00647, 2018.
  * [22] Pascal Massart.  Concentration inequalities and model selection.
  * [23] Pascal Massart and Élodie Nédélec.  Risk bounds for statistical learning.  The Annals of Statistics, 34(5):2326–2366, 2006.
  * [24] Debarghya Mukherjee, Moulinath Banerjee, and Ya’acov Ritov.  Optimal linear discriminators for the discrete choice model in growing dimensions.  arXiv preprint arXiv:1903.10063, 2019.
  * [25] Patricia Reynaud-Bouret.  Adaptive estimation of the intensity of inhomogeneous poisson processes via concentration inequalities.  Probability Theory and Related Fields, 126(1):103–153, 2003.
  * [26] Bodhisattva Sen.  A gentle introduction to empirical process theory and applications.  2018\.
  * [27] M.H. Seo and O. Linton.  A smoothed least squares estimator for threshold regression models.  Journal of Econometrics, 141(2):704–735, 2007.
  * [28] Noa Slater, Yoram Louzoun, Loren Gragert, Martin Maiers, Ansu Chatterjee, and Mark Albrecht.  Power laws for heavy-tailed distributions: Modeling allele and haplotype diversity for the national marrow donor program.  PLoS Comput Biol, 11(4):e1004204, 2015.
  * [29] Aad W Van Der Vaart and Jon A Wellner.  Weak convergence.  In Weak convergence and empirical processes, pages 16–28. Springer, 1996.
  * [30] Vladimir Vapnik and Alexey Chervonenkis.  Theory of pattern recognition, 1974.
  * [31] Susan Wei and M.R. Kosorok.  The Cox proportional hazards model with change plane.  Submitted, 2015.
  * [32] Martin L Weitzman.  Fat-tailed uncertainty in the economics of catastrophic climate change.  Review of Environmental Economics and Policy, 5(2):275–292, 2011\.
  * [33] Bin Yu.  Assouad, fano, and le cam.  In Festschrift for Lucien Le Cam, pages 423–435. Springer, 1997\.