S}e^{\theta_{j}^{*}}}\\!\Big{)}\\!\\!\\!\Bigg{\\}}\\!\boldsymbol{e}_{i}\Bigg{\\}}^{2}\leq
C_{0}\epsilon_{0}\Bigg{\\}},$

where the constant $C_{0}$ is chosen properly such that
$\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\left((E_{\mathcal{E}})^{C}\right)\leq
n^{-10}$. By maximal inequality we have that under the event
$E_{\mathcal{E}}$, there exists a large enough constant $C>0$ such that

$\displaystyle\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(W-W_{0}\geq
C\sqrt{\epsilon_{0}\log n}\,|\,\bm{x},\mathcal{E}\right)$
$\displaystyle\leq\mathbb{P}_{\boldsymbol{\theta}^{*}}\Bigg{(}\max_{k\in[n]}\sum_{\ell=1}^{L}\sum_{S\in\mathcal{I}}\mathcal{E}_{S}\sum_{i\in
S}\Bigg{\\{}\frac{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}})^{\dagger}}{\sqrt{L\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}})^{\dagger}\widehat{\mathbf{v}}_{k}}}\left(x_{S}^{(i,\ell)}-\frac{e^{\widehat{\theta}_{i}}}{\sum_{j\in
S}e^{\widehat{\theta}_{j}}}\right)$
$\displaystyle\quad-\frac{\mathbf{v}_{k}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*})^{\dagger}}{\sqrt{L\mathbf{v}_{k}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*})^{\dagger}\mathbf{v}_{k}}}\left(x_{S}^{(i,\ell)}-\frac{e^{\theta_{i}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)\Bigg{\\}}\boldsymbol{e}_{i}z_{\ell}\geq
C\sqrt{\epsilon_{0}\log n}\,|\,\bm{x},\mathcal{E}\Bigg{)}\leq n^{-10}/2.$

Very similarly, under the event ${\mathbb{E}}_{\mathcal{E}}$ we can also show
that

$\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(W_{0}-W\geq C\sqrt{\epsilon_{0}\log
n}\,|\,\bm{x},\mathcal{E}\right)\leq n^{-10}/2,$

and in turn

$\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(|W-W_{0}|\geq
C\sqrt{\epsilon_{0}\log n}\,|\,\bm{x},\mathcal{E}\right)\leq n^{-10}.$

Combining the above results we have

$\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(|W-W_{0}|\geq
C\sqrt{\epsilon_{0}\log
n}\,|\,\bm{x},\mathcal{E}\right)>n^{-10}\right)\leq\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\left((E_{\mathcal{E}})^{C}\right)\leq
n^{-10}.$

Now we consider $|T-T_{0}|$. Under the condition that
$\kappa_{r}\lesssim\sqrt{n}$, with probability at least $1-O(n^{-10})$ we have
that

$\displaystyle|T-T_{0}|$
$\displaystyle\lesssim\max_{k\in[n]}\bigg{\\{}\\!\bigg{\lvert}\frac{\sqrt{L}(\widehat{\Delta}_{k}\\!-\\!\Delta_{k})}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}})^{\dagger}\widehat{\mathbf{v}}_{k}}}\\!-\\!\frac{\sqrt{L}(\widehat{\Delta}_{k}\\!-\\!\Delta_{k})}{\sqrt{\mathbf{v}_{k}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*})^{\dagger}\mathbf{v}_{k}}}\bigg{\rvert}\\!+\\!\frac{\|{\mathbf{P}}_{\mathbf{1}}^{\perp}\mathbf{v}_{k}\|_{2}\|\mathbf{R}_{0}\|_{2}+\|\mathbf{v}_{k}\|_{\infty}\|\widehat{\boldsymbol{\theta}}^{d}\\!-\\!\boldsymbol{\theta}^{*}\|_{2}^{2}}{\sqrt{\mathbf{v}_{k}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*})^{\dagger}\mathbf{v}_{k}/L}}\bigg{\\}}$
$\displaystyle\lesssim\max_{k\in[n]}\bigg{\\{}\|{\mathbf{P}}_{\mathbf{1}}^{\perp}\mathbf{v}_{k}\|_{2}\|\widehat{\boldsymbol{\theta}}^{d}-\boldsymbol{\theta}^{*}\|_{2}\bigg{\lvert}\frac{\sqrt{L}}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}})^{\dagger}\widehat{\mathbf{v}}_{k}}}-\frac{\sqrt{L}}{\sqrt{\mathbf{v}_{k}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*})^{\dagger}\mathbf{v}_{k}}}\bigg{\rvert}$
$\displaystyle\quad+\frac{\|{\mathbf{P}}_{\mathbf{1}}^{\perp}\mathbf{v}_{k}\|_{2}\|\mathbf{R}_{0}\|_{2}+\|\mathbf{v}_{k}\|_{\infty}\|\widehat{\boldsymbol{\theta}}^{d}-\boldsymbol{\theta}^{*}\|_{2}^{2}}{\sqrt{\mathbf{v}_{k}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*})^{\dagger}\mathbf{v}_{k}/L}}\bigg{\\}}$
$\displaystyle\leq{\max_{k\in[n]}\frac{\sqrt{n}\log
n}{\sqrt{L}}\left(\sqrt{\frac{n}{M_{n}p}}+\frac{\|\mathbf{v}_{k}\|_{\infty}}{\|{\mathbf{P}}_{\mathbf{1}}^{\perp}\mathbf{v}_{k}\|_{2}}{\frac{1}{\sqrt{M_{n}p}}}\right)}\lesssim\frac{n\log
n}{\sqrt{M_{n}pL}}.$

Thus if we take $\zeta_{1}=C_{1}\frac{n\log n}{\sqrt{M_{n}pL}}$ and
$\zeta_{2}=C_{2}n^{-10}$ with large enough constants $C_{1}$ and $C_{2}$
independent of $\boldsymbol{\theta}^{*}$, under the condition that $\sqrt{\log
n}\frac{n\log n}{\sqrt{M_{n}pL}}\asymp\frac{n^{2}(\log
n)^{3/2}}{\sqrt{2^{n}pL}}=o(1)$, condition (1) also holds, and by Corollary
3.1 in Chernozhukov et al., (2013) we have that with high probability with
respect to $\boldsymbol{\mathcal{E}}$ the event (D.1) holds.

Then by Jensen’s inequality and the dominated convergence theorem we have

$\displaystyle\lim_{n,L\rightarrow\infty}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T\\!>\\!c_{W}(\alpha,\boldsymbol{\mathcal{E}})\right)\\!-\\!\alpha\right|\\!=\\!\\!\lim_{n,L\rightarrow\infty}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\int\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T\\!>\\!c_{W}(\alpha,\boldsymbol{\mathcal{E}})\,|\,\boldsymbol{\mathcal{E}}\right){\rm
d}\mu(\boldsymbol{\mathcal{E}})\\!-\\!\alpha\right|$
$\displaystyle=\lim_{n,L\rightarrow\infty}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\int\left(\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T>c_{W}(\alpha,\boldsymbol{\mathcal{E}})\,|\,\boldsymbol{\mathcal{E}}\right)-\alpha\right){\rm
d}\mu(\boldsymbol{\mathcal{E}})\right|$
$\displaystyle\leq\lim_{n,L\rightarrow\infty}\int\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T>c_{W}(\alpha,\boldsymbol{\mathcal{E}})\,|\,\boldsymbol{\mathcal{E}}\right)-\alpha\right|{\rm
d}\mu(\boldsymbol{\mathcal{E}})$
$\displaystyle=\lim_{n,L\rightarrow\infty}\int_{{\boldsymbol{\mathcal{A}}}_{\boldsymbol{\mathcal{E}}}}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T>c_{W}(\alpha,\boldsymbol{\mathcal{E}})\,|\,\boldsymbol{\mathcal{E}}\right)-\alpha\right|{\rm
d}\mu(\boldsymbol{\mathcal{E}})$
$\displaystyle\quad+\lim_{n,L\rightarrow\infty}\int_{{\boldsymbol{\mathcal{A}}}_{\boldsymbol{\mathcal{E}}}^{c}}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T>c_{W}(\alpha,\boldsymbol{\mathcal{E}})\,|\,\boldsymbol{\mathcal{E}}\right)-\alpha\right|{\rm
d}\mu(\boldsymbol{\mathcal{E}})$
$\displaystyle\leq\int_{{\boldsymbol{\mathcal{A}}}_{\boldsymbol{\mathcal{E}}}}\lim_{n,L\rightarrow\infty}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T>c_{W}(\alpha,\boldsymbol{\mathcal{E}})\,|\,\boldsymbol{\mathcal{E}}\right)-\alpha\right|{\rm
d}\mu(\boldsymbol{\mathcal{E}})+\lim_{n,L\rightarrow\infty}\int_{{\boldsymbol{\mathcal{A}}}_{\boldsymbol{\mathcal{E}}}^{c}}{\rm
d}\mu(\boldsymbol{\mathcal{E}})=0.$

Thus
$\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\sup_{\alpha\in(0,1)}\left|\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(T>c_{W}(\alpha,\boldsymbol{\mathcal{E}})\right)-\alpha\right|=o(1)$
as $n,L\rightarrow\infty$.

##  E Proof of Theorem 3.4

We will first show that $[\widehat{K}_{L},\widehat{K}_{U}]$ is a valid
confidence interval for $K^{*}$ based on Lemma 3.5. Note that by definition,
if $\widehat{K}_{U}<n$, we have that
$\widehat{\Delta}_{\widehat{K}_{U}+1}>c_{W}(\alpha/2,\boldsymbol{\mathcal{E}})\sqrt{{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}}/{L}}$.
Then we have

$\displaystyle\mathbb{P}_{\boldsymbol{\theta}^{*}}(\widehat{K}_{L}\\!\\!\leq\\!\\!K^{*}\\!\\!\leq\\!\\!\widehat{K}_{U})\geq
1\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}(\widehat{K}_{L}\\!>\\!K^{*})\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}(\widehat{K}_{U}\\!<\\!K^{*})=1\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}(\widehat{K}_{L}\\!>\\!K^{*})\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}(\widehat{K}_{U}\\!+\\!1\\!\leq\\!K^{*})$
$\displaystyle=1\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}(\Delta_{\widehat{K}_{L}}\\!\geq\\!0)-\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(\left\\{\Delta_{\widehat{K}_{U}+1}\\!<\\!0\right\\}\cap\\{\widehat{K}_{U}<n\\}\right)$
$\displaystyle=1\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(\\!\\{\Delta_{\widehat{K}_{L}}\\!\geq\\!0\\}\\!\cap\\!\left\\{\widehat{\Delta}_{\widehat{K}_{L}}\\!\\!<\\!-c_{W}(\alpha/2,\boldsymbol{\mathcal{E}})\sqrt{{\widehat{\mathbf{v}}_{\widehat{K}_{L}}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{\widehat{K}_{L}}}/{L}}\right\\}\\!\right)$
$\displaystyle\quad\quad-\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(\\!\\{\Delta_{\widehat{K}_{U}+1}\\!<\\!0\\}\\!\cap\\!\left\\{\widehat{K}_{U}<n,\,\widehat{\Delta}_{\widehat{K}_{U}+1}\\!\\!>\\!c_{W}(\alpha/2,\boldsymbol{\mathcal{E}})\sqrt{{\widehat{\mathbf{v}}_{\widehat{K}_{U}+1}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{\widehat{K}_{U}+1}}/{L}}\right\\}\\!\right)$
$\displaystyle\geq
1\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}\Bigg{(}\\!\min_{k>K^{*}}\frac{\sqrt{L}(\widehat{\Delta}_{k}-\Delta_{k})}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}}}\\!\leq\\!-c_{W}(\frac{\alpha}{2},\boldsymbol{\mathcal{E}})\\!\\!\Bigg{)}\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}\Bigg{(}\\!\max_{k\leq
K^{*}}\frac{\sqrt{L}(\widehat{\Delta}_{k}-\Delta_{k})}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}}}\geq
c_{W}(\frac{\alpha}{2},\boldsymbol{\mathcal{E}})\\!\\!\Bigg{)}$
$\displaystyle\geq
1\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}\Bigg{(}\\!\min_{k\in[n]}\frac{\sqrt{L}(\widehat{\Delta}_{k}-\Delta_{k})}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}}}\\!\leq\\!-c_{W}(\frac{\alpha}{2},\boldsymbol{\mathcal{E}})\\!\\!\Bigg{)}\\!-\\!\mathbb{P}_{\boldsymbol{\theta}^{*}}\Bigg{(}\\!\max_{k\in[n]}\frac{\sqrt{L}(\widehat{\Delta}_{k}-\Delta_{k})}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}}}\geq
c_{W}(\frac{\alpha}{2},\boldsymbol{\mathcal{E}})\\!\\!\Bigg{)}.$

By Lemma 3.5, we know that

$\\!\lim_{n,L\rightarrow\infty}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(\max_{k\in[n]}\frac{\widehat{\Delta}_{k}-\Delta_{k}}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}/L}}\geq
c_{W}(\alpha/2,\boldsymbol{\mathcal{E}})\right)=\frac{\alpha}{2}.$

Also, following similar proof and the symmetry of Gaussian distribution we
have

$\displaystyle\lim_{n,L\rightarrow\infty}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(\min_{k\in[n]}\frac{\widehat{\Delta}_{k}-\Delta_{k}}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}/L}}\leq-
c_{W}(\alpha/2,\boldsymbol{\mathcal{E}})\right)$
$\displaystyle=\lim_{n,L\rightarrow\infty}\sup_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\left(\max_{k\in[n]}-\frac{\widehat{\Delta}_{k}-\Delta_{k}}{\sqrt{\widehat{\mathbf{v}}_{k}^{\top}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\widehat{\mathbf{v}}_{k}/L}}\geq
c_{W}(\alpha/2,\boldsymbol{\mathcal{E}})\right)=\frac{\alpha}{2}.$

and thus by taking limits and supreme on both sides of the inequality, we have
that (3.13) follows.

Now we move on to show (3.14). By the equivalence of (1.1) and (2.4), we have
that

$\displaystyle\sup_{{\mathcal{S}}^{*}\in{\boldsymbol{\mathcal{S}}}_{0}}\mathbb{P}_{\boldsymbol{\theta}^{*}}(\text{Reject
}H_{0})=\sup_{\boldsymbol{\theta}^{*}:K^{*}\in\mathcal{K}_{0}}\mathbb{P}_{\boldsymbol{\theta}^{*}}(\text{Reject
}H_{0})=\sup_{\boldsymbol{\theta}^{*}:K^{*}\in\mathcal{K}_{0}}\mathbb{P}_{\boldsymbol{\theta}^{*}}([\widehat{K}_{L},\widehat{K}_{U}]\cap\mathcal{K}_{0}=\varnothing)$
$\displaystyle=\sup_{\boldsymbol{\theta}^{*}:K^{*}\in\mathcal{K}_{0}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\Big{(}\\{K^{*}\in\mathcal{K}_{0}\\}\cap\big{\\{}[\widehat{K}_{L},\widehat{K}_{U}]\cap\mathcal{K}_{0}=\varnothing\big{\\}}\Big{)}$
$\displaystyle\leq\sup_{\boldsymbol{\theta}^{*}:K^{*}\in\mathcal{K}_{0}}\mathbb{P}_{\boldsymbol{\theta}^{*}}\Big{(}\\{K^{*}\in\mathcal{K}_{0}\\}\cap\\{K^{*}\notin[\widehat{K}_{L},\widehat{K}_{U}]\\}\Big{)}$
$\displaystyle\leq
1-\inf_{\boldsymbol{\theta}^{*}:K^{*}\in\mathcal{K}_{0}}\mathbb{P}_{\boldsymbol{\theta}^{*}}(K^{*}\in[\widehat{K}_{L},\widehat{K}_{U}])\leq
1-\inf_{\boldsymbol{\theta}^{*}\in\mathbf{\Theta}}\mathbb{P}_{\boldsymbol{\theta}^{*}}(K^{*}\in[\widehat{K}_{L},\widehat{K}_{U}]).$

Then from (3.13), by taking limits on both sides we have that (3.14) holds.

##  F Proof of Technical Lemmas

###  F.1 Proof of Lemma A.1

Let
${\mathbf{A}}_{S}=\mathcal{E}_{S}\cdot\frac{1}{|S|^{2}}\sum_{\begin{subarray}{c}i,j\in
S\\\
i<j\end{subarray}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{j})(\boldsymbol{e}_{i}-\boldsymbol{e}_{j})^{\top}$,
then
$\mathbf{L}_{\boldsymbol{\mathcal{E}}}=\sum_{S\in\mathcal{I}}{\mathbf{A}}_{S}$.
We have that

$\displaystyle\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})$
$\displaystyle=p\sum_{k=2}^{n+1}\sum_{S\in\mathcal{I}_{k}}\frac{1}{k^{2}}\sum_{\begin{subarray}{c}i,j\in
S\\\
i<j\end{subarray}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{j})(\boldsymbol{e}_{i}-\boldsymbol{e}_{j})^{\top}=p\begin{pmatrix}nN_{n}&\quad-
N_{n}\mathbf{1}_{n}^{\top}\\\
-N_{n}\mathbf{1}_{n}&\quad(nM_{n}\\!+\\!N_{n})\mathbf{I}_{n}\\!-\\!M_{n}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\end{pmatrix}$
$\displaystyle=p\left((n+1)M_{n}\mathbf{I}_{n+1}-M_{n}\mathbf{1}_{n+1}\mathbf{1}_{n+1}^{\top}+(N_{n}-M_{n})\begin{pmatrix}n&-\mathbf{1}_{n}^{\top}\\\
-\mathbf{1}_{n}&\mathbf{I}_{n}\end{pmatrix}\right)$
$\displaystyle=p\left((n+1)M_{n}\mathbf{I}_{n+1}-M_{n}\mathbf{1}_{n+1}\mathbf{1}_{n+1}^{\top}+(N_{n}-M_{n})\left(\mathbf{I}_{n+1}+{\rm
diag}(n,\mathbf{1}_{n}\mathbf{1}_{n}^{\top})-\mathbf{1}_{n+1}\mathbf{1}_{n+1}^{\top}\right)\right)$
$\displaystyle=p\left((nM_{n}+N_{n})\mathbf{I}_{n+1}+(N_{n}-M_{n}){\rm
diag}(n,\mathbf{1}_{n}\mathbf{1}_{n}^{\top})-N_{n}\mathbf{1}_{n+1}\mathbf{1}_{n+1}^{\top}\right).$

Consider the matrix $(N_{n}-M_{n}){\rm
diag}(n,\mathbf{1}_{n}\mathbf{1}_{n}^{\top})-N_{n}\mathbf{1}_{n+1}\mathbf{1}_{n+1}^{\top}$.
Define $\mathbf{w}_{1}=(1,\mathbf{0}^{\top})^{\top}$,
$\mathbf{w}_{2}=(0,\mathbf{1}_{n}^{\top}/\sqrt{n})^{\top}$ and
$\mathbf{W}=(\mathbf{w}_{1},\mathbf{w}_{2})$. Then it can be seen that
$\mathbf{1}_{n+1}=\mathbf{w}_{1}+\sqrt{n}\mathbf{w}_{2}$ and we have that

$\displaystyle(N_{n}-M_{n}){\rm
diag}(n,\mathbf{1}_{n}\mathbf{1}_{n}^{\top})-N_{n}\mathbf{1}_{n+1}\mathbf{1}_{n+1}^{\top}=n(N_{n}-M_{n})\mathbf{W}\mathbf{W}^{\top}-\mathbf{W}\begin{pmatrix}N_{n}&\sqrt{n}N_{n}\\\
\sqrt{n}N_{n}&N_{n}\end{pmatrix}\mathbf{W}^{\top}$
$\displaystyle=\mathbf{W}\begin{pmatrix}(n-1)N_{n}-nM_{n}&-\sqrt{n}N_{n}\\\
-\sqrt{n}N_{n}&-nM_{n}\end{pmatrix}\mathbf{W}^{\top}=\mathbf{W}\mathbf{G}{\rm
diag}\left(n(N_{n}-M_{n}),-nM_{n}-N_{n}\right)\mathbf{G}^{\top}\mathbf{W}^{\top},$

where $\mathbf{G}=\frac{1}{\sqrt{n+1}}\begin{pmatrix}\sqrt{n}&1\\\
-1&\sqrt{n}\end{pmatrix}$ and the last equality follows from the following
eigen-decomposition:

$\begin{pmatrix}(n-1)N_{n}-nM_{n}&-\sqrt{n}N_{n}\\\
-\sqrt{n}N_{n}&-nM_{n}\end{pmatrix}=\mathbf{G}{\rm
diag}\left(n(N_{n}-M_{n}),-nM_{n}-N_{n}\right)\mathbf{G}^{\top}.$

Then combining the above results we have that

$\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})=p\left((nM_{n}+N_{n})\mathbf{I}_{n+1}+\mathbf{W}\mathbf{G}{\rm
diag}\left(n(N_{n}-M_{n}),-nM_{n}-N_{n}\right)\mathbf{G}^{\top}\mathbf{W}^{\top}\right),$
(F.1)

which indicates that $\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})$
follows a spiked structure with
$\lambda_{1}\big{(}\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\big{)}=(n+1)N_{n}$,
$\lambda_{n}\big{(}\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\big{)}=nM_{n}+N_{n}$
and
$\lambda_{n+1}\big{(}\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\big{)}=0$.
Also since
$\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\mathbf{1}_{n+1}=\mathbf{0}$,
we have that $\mathbf{1}_{n+1}$ corresponds to the $(n+1)$-th eigenvalue of
$\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})$. Let
$\mathbf{R}_{\boldsymbol{\mathcal{E}}}\in\mathbb{R}^{(n+1)\times n}$ denote
the stacking of the top $n$ normalized eigenvectors of
$\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})$, which is unique up to
rotation, and we have
$\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}\mathbf{R}_{\boldsymbol{\mathcal{E}}}=\mathbf{I}_{n}$
and $\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}\mathbf{1}_{n+1}=\mathbf{0}$.
Then from (F.1), it can be seen that

$\mathbb{E}(\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}\mathbf{L}_{\boldsymbol{\mathcal{E}}}\mathbf{R}_{\boldsymbol{\mathcal{E}}})=\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\mathbf{R}_{\boldsymbol{\mathcal{E}}}={\rm
diag}\big{(}(n+1)N_{n}p,(nM_{n}+N_{n})p\mathbf{I}_{n-1}\big{)}.$

We have that

$\lambda_{\min}({\mathbf{A}}_{S})\geq
0,\quad\lambda_{\max}({\mathbf{A}}_{S})\leq|S|/|S|^{2}=1/|S|\leq 1.$

and

$\lambda_{\min}(\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}{\mathbf{A}}_{S}\mathbf{R}_{\boldsymbol{\mathcal{E}}})\geq
0,\quad\lambda_{\max}(\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}{\mathbf{A}}_{S}\mathbf{R}_{\boldsymbol{\mathcal{E}}})\leq\lambda_{\max}({\mathbf{A}}_{S})\leq
1.$

Then by Theorem 5.1.1 in Tropp, (2015), under the condition that $2^{n}p\geq
Cn\log n$ for some large enough constant $C>0$, there exists a constant $c>0$
such that for large enough $n$ we have

$\displaystyle\mathbb{P}\left(\lambda_{\min,\perp}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\leq(nM_{n}+N_{n})p/2\right)=\mathbb{P}\left(\lambda_{\min}(\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}\mathbf{L}_{\boldsymbol{\mathcal{E}}}\mathbf{R}_{\boldsymbol{\mathcal{E}}})\leq\lambda_{\min}\left(\mathbb{E}(\mathbf{R}_{\boldsymbol{\mathcal{E}}}^{\top}\mathbf{L}_{\boldsymbol{\mathcal{E}}}\mathbf{R}_{\boldsymbol{\mathcal{E}}})\right)/2\right)$
$\displaystyle\quad\leq n\exp(-cnM_{n}p)\leq n^{-10},$

and

$\displaystyle\mathbb{P}\left(\lambda_{\max}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\geq
3(n+1)N_{n}p/2\right)=\mathbb{P}\left(\lambda_{\max}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\geq
3\lambda_{\max}\left(\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\right)/2\right)$
$\displaystyle\quad\leq(n+1)\exp(-cnM_{n}p)\leq n^{-10}.$

###  F.2 Proof of Lemma A.2

First, we can rewrite

$\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})=\sum_{S\in\boldsymbol{\mathcal{E}}}\left\\{\sum_{\begin{subarray}{c}i,l\in
S\\\ i<l\end{subarray}}\frac{e^{\theta_{i}}e^{\theta_{l}}}{\left(\sum_{j\in
S}e^{\theta_{j}}\right)^{2}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\right\\}.$

Then we have

$\frac{e^{\theta_{i}}}{\sum_{j\in S}e^{\theta_{j}}}=\frac{1}{\sum_{j\in
S}e^{\theta_{j}-\theta_{i}}}=\frac{1}{\sum_{j\in
S}e^{(\theta_{j}-\theta_{j}^{*})+(\theta_{j}^{*}-\theta_{i}^{*})+(\theta_{i}^{*}-\theta_{i})}}\geq\frac{1}{\sum_{j\in
S}e^{\log\kappa_{\boldsymbol{\theta}}+2\|\boldsymbol{\theta}^{*}-\boldsymbol{\theta}\|_{\infty}}}=\frac{1}{|S|\kappa_{\boldsymbol{\theta}}e^{2C}}.$

Similarly, we also have

$\frac{e^{\theta_{i}}}{\sum_{j\in S}e^{\theta_{j}}}=\frac{1}{\sum_{j\in
S}e^{(\theta_{j}-\theta_{j}^{*})+(\theta_{j}^{*}-\theta_{i}^{*})+(\theta_{i}^{*}-\theta_{i})}}\leq\frac{1}{\sum_{j\in
S}e^{-\log\kappa_{\boldsymbol{\theta}}-2\|\boldsymbol{\theta}^{*}-\boldsymbol{\theta}\|_{\infty}}}=\frac{\kappa_{\boldsymbol{\theta}}e^{2C}}{|S|}.$

Since
$(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\succeq\mathbf{0}$
for any $i<l$, we have that

$\left(\frac{e^{\theta_{i}}e^{\theta_{l}}}{\left(\sum_{j\in
S}e^{\theta_{j}}\right)^{2}}-\frac{1}{|S|^{2}(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}}\right)(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\succeq\mathbf{0},$
$\text{and}\quad\left(\frac{e^{\theta_{i}}e^{\theta_{l}}}{\left(\sum_{j\in
S}e^{\theta_{j}}\right)^{2}}-\frac{(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}}{|S|^{2}}\right)(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\preceq\mathbf{0}.$

Hence,

$\displaystyle\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})$
$\displaystyle=\sum_{S\in\boldsymbol{\mathcal{E}}}\bigg{\\{}\sum_{\begin{subarray}{c}i,l\in
S\\\ i<l\end{subarray}}\frac{e^{\theta_{i}}e^{\theta_{l}}}{\left(\sum_{j\in
S}e^{\theta_{j}}\right)^{2}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\bigg{\\}}$
$\displaystyle\succeq\sum_{S\in\boldsymbol{\mathcal{E}}}\bigg{\\{}\sum_{\begin{subarray}{c}i,l\in
S\\\
i<l\end{subarray}}\frac{1}{|S|^{2}(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\bigg{\\}}$
$\displaystyle=\frac{1}{(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}}\sum_{S\in\boldsymbol{\mathcal{E}}}\bigg{\\{}\sum_{\begin{subarray}{c}i,l\in
S\\\
i<l\end{subarray}}\frac{1}{|S|^{2}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\bigg{\\}}=\frac{1}{(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}}\mathbf{L}_{\boldsymbol{\mathcal{E}}},$

and similarly
$\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})\preceq(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}\mathbf{L}_{\boldsymbol{\mathcal{E}}}$.
Then by Lemma A.1, the inequalities in (A.4) follow.

###  F.3 Proof of Lemma A.3

We know that

$\displaystyle\nabla_{\lambda}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})$
$\displaystyle=\lambda\boldsymbol{\theta}^{*}-\sum_{S\in\boldsymbol{\mathcal{E}}}\left\\{\sum_{i\in
S}\left(x_{S}^{(i)}-\frac{e^{\theta^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\boldsymbol{e}_{i}\right\\}$
$\displaystyle=\lambda\boldsymbol{\theta}^{*}-\frac{1}{L}\sum_{S\in\boldsymbol{\mathcal{E}}}\sum_{\ell=1}^{L}\underbrace{\left\\{\sum_{i\in
S}\left(x_{S}^{(i,\ell)}-\frac{e^{\theta^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\boldsymbol{e}_{i}\right\\}}_{:=\bm{z}_{S}^{(\ell)}},$

and we have $\mathbb{E}\left(\bm{z}_{S}^{(\ell)}\right)=\mathbf{0}$ and

$\left\|\bm{z}_{S}^{(\ell)}\right\|_{2}^{2}=\sum_{i\in
S}\left(x_{S}^{(i,\ell)}-\frac{e^{\theta^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)^{2}\leq\sum_{i\in
S}(x_{S}^{(i,\ell)})^{2}+\sum_{i\in
S}\frac{(e^{\theta^{*}_{i}})^{2}}{\left(\sum_{j\in
S}e^{\theta^{*}_{j}}\right)^{2}}\leq 1+\sum_{i\in
S}\frac{e^{\theta^{*}_{i}}}{\sum_{j\in S}e^{\theta^{*}_{j}}}=2,$
$\displaystyle\mathbb{E}\left(\bm{z}_{S}^{(\ell)}\bm{z}_{S}^{(\ell)\top}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}i,l\in S\\\
i<l\end{subarray}}\frac{e^{\theta_{i}}e^{\theta_{l}}}{\left(\sum_{j\in
S}e^{\theta_{j}}\right)^{2}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\preceq\kappa_{\boldsymbol{\theta}}^{2}\sum_{\begin{subarray}{c}i,l\in
S\\\
i<l\end{subarray}}\frac{1}{|S|^{2}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top};$
$\displaystyle\mathbb{E}\left(\bm{z}_{S}^{(\ell)\top}\bm{z}_{S}^{(\ell)}\right)$
$\displaystyle=\sum_{i\in S}\frac{e^{\theta^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}-\sum_{i\in S}\left(\frac{e^{\theta^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)^{2}\leq 1,$

and thus with probability at least $1-O(n^{-10})$ (with randomness coming from
$\boldsymbol{\mathcal{E}}$) we have

$\displaystyle\left\|\frac{1}{L^{2}}\sum_{S\in\boldsymbol{\mathcal{E}}}\sum_{\ell=1}^{L}\mathbb{E}\left(\bm{z}_{S}^{(\ell)}\bm{z}_{S}^{(\ell)\top}\right)\right\|_{2}\lesssim\frac{\kappa_{\boldsymbol{\theta}}^{2}}{L}\bigg{\|}\sum_{S\in\boldsymbol{\mathcal{E}}}\Big{\\{}\frac{1}{|S|^{2}}\sum_{\begin{subarray}{c}i,l\in
S\\\
i<l\end{subarray}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{j})(\boldsymbol{e}_{i}-\boldsymbol{e}_{j})^{\top}\Big{\\}}\bigg{\|}_{2}\lesssim\frac{1}{L}\|\bm{L}_{\boldsymbol{\mathcal{E}}}\|_{2}\lesssim\frac{nM_{n}p}{L};$
$\displaystyle\Big{|}\frac{1}{L^{2}}\sum_{S\in\boldsymbol{\mathcal{E}}}\sum_{\ell=1}^{L}\mathbb{E}\left(\bm{z}_{S}^{(\ell)\top}\bm{z}_{S}^{(\ell)}\right)\Big{|}=\Big{|}\frac{1}{L^{2}}\sum_{S\in\boldsymbol{\mathcal{E}}}\sum_{\ell=1}^{L}\operatorname{Tr}\left\\{\mathbb{E}\left(\bm{z}_{S}^{(\ell)}\bm{z}_{S}^{(\ell)\top}\right)\right\\}\Big{|}\lesssim\frac{(n+1)}{L}\|\bm{L}_{\boldsymbol{\mathcal{E}}}\|_{2}\lesssim\frac{n^{2}M_{n}p}{L}.$

Thus we can take $V=\frac{n^{2}M_{n}p}{L}$ and $B=1/L$, then by the matrix
Bernstein inequality (Tropp,, 2012), with probability at least $1-O(n^{-10})$
we have that

$\|\nabla_{\lambda}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})-\lambda\boldsymbol{\theta}^{*}\|_{2}\lesssim\sqrt{V\log
n}+B\log n\lesssim n\sqrt{\frac{M_{n}p\log n}{L}}+\frac{\log n}{L}.$

Thus when $\lambda\asymp\sqrt{\frac{nM_{n}p\log n}{L}}$, since we know that
$\|\boldsymbol{\theta}^{*}\|_{2}\leq\sqrt{n+1}\log\kappa_{\boldsymbol{\theta}}$,
with probability at least $1-O(n^{-10})$ we have

$\|\nabla_{\lambda}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\|_{2}\leq\lambda\boldsymbol{\theta}^{*}+\|\nabla_{\lambda}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})-\lambda\boldsymbol{\theta}^{*}\|_{2}\lesssim
n\sqrt{\frac{M_{n}p\log n}{L}}.$

###  F.4 Proof of Lemma A.4

The proof is similar to the proof of Lemma A.1. First note that for any
$\boldsymbol{\theta}\in\mathbb{R}^{n+1}$ and any $S\in\mathcal{I}$, we have
that

$e^{\theta_{i}}e^{\theta_{l}}/(\sum_{j\in S}e^{\theta_{j}})^{2}\leq
e^{\theta_{i}}/(\sum_{j\in
S}e^{\theta_{j}})\Big{(}1-e^{\theta_{i}}/(\sum_{j\in
S}e^{\theta_{j}})\Big{)}\leq 1/4,\quad\forall i,l\in S,$

and thus

$\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})=\sum_{S\in\boldsymbol{\mathcal{E}}}\left\\{\sum_{\begin{subarray}{c}i,l\in
S\\\ i<l\end{subarray}}\frac{e^{\theta_{i}}e^{\theta_{l}}}{\left(\sum_{j\in
S}e^{\theta_{j}}\right)^{2}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\right\\}\preceq\underbrace{\frac{1}{4}\sum_{S\in\boldsymbol{\mathcal{E}}}\left\\{\sum_{\begin{subarray}{c}i,l\in
S\\\
i<l\end{subarray}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\right\\}}_{\mathbf{L}^{\prime}_{\boldsymbol{\mathcal{E}}}}.$

We let $\mathbf{B}_{S}=\mathcal{E}_{S}\cdot\sum_{\begin{subarray}{c}i,l\in
S\\\
i<l\end{subarray}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}$,
then $\lambda_{\min}(\mathbf{B}_{S})\geq 0$ and
$\lambda_{\max}(\mathbf{B}_{S})\leq|S|\leq n+1$. We have

$\displaystyle\mathbb{E}(\mathbf{L}_{\boldsymbol{\mathcal{E}}}^{\prime})$
$\displaystyle=p\sum_{S\in\mathcal{I}}\left\\{\sum_{\begin{subarray}{c}i,l\in
S\\\
i<l\end{subarray}}(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})(\boldsymbol{e}_{i}-\boldsymbol{e}_{l})^{\top}\right\\}=p2^{n-2}\left((n+2)\mathbf{I}_{n+1}+{\rm
diag}(n,\mathbf{1}_{n}\mathbf{1}_{n}^{\top})-2\mathbf{1}_{n+1}\mathbf{1}_{n+1}^{\top}\right)$
$\displaystyle=p2^{n-2}\left((n+2)\mathbf{I}_{n+1}+{\rm
diag}(1,\mathbf{1}_{n}/\sqrt{n})\mathbf{G}{\rm
diag}\left(n,-(n+2)\right)\mathbf{G}^{\top}{\rm
diag}(1,\mathbf{1}_{n}^{\top}/\sqrt{n})\right),$

where $\mathbf{G}=\frac{1}{\sqrt{n+1}}\begin{pmatrix}\sqrt{n}&1\\\
-1&\sqrt{n}\end{pmatrix}$. By Theorem 5.1.1 in Tropp, (2015), under the
condition that $2^{n}p\geq C\log n$ for some large enough constant $C>0$, for
large enough $n$ we have that there exist constants $c,c^{\prime}>0$ such that

$\displaystyle\mathbb{P}\left(\lambda_{\max}(\mathbf{L}^{\prime}_{\boldsymbol{\mathcal{E}}})\geq
3(n+1)2^{n-1}p/2\right)=\mathbb{P}\left(\lambda_{\max}(\mathbf{L}^{\prime}_{\boldsymbol{\mathcal{E}}})\geq
3\lambda_{\max}\left(\mathbb{E}(\mathbf{L}^{\prime}_{\boldsymbol{\mathcal{E}}})\right)/2\right)$
$\displaystyle\quad\leq(n+1)\exp(-c2^{n}p)\leq n^{-10}.$

Thus with probability at least $1-n^{-10}$, we have that

$\|\nabla^{2}\mathcal{L}_{\lambda}(\boldsymbol{\theta};\bm{x})\|_{2}\lesssim\lambda+\lambda_{\max}(\mathbf{L}_{\boldsymbol{\mathcal{E}}}^{\prime})/4\leq\lambda+3(n+1)2^{n}p/16.$

###  F.5 Proof of Lemma A.5

By the optimality of $\widehat{\boldsymbol{\theta}}$ and Taylor’s expansion,
we have

$\displaystyle\mathcal{L}_{\lambda}(\widehat{\boldsymbol{\theta}};\bm{x})$
$\displaystyle=\mathcal{L}_{\lambda}(\boldsymbol{\theta}^{*};\bm{x})+(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})^{\top}\nabla\mathcal{L}_{\lambda}(\boldsymbol{\theta}^{*};\bm{x})+\frac{1}{2}(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})^{\top}\nabla^{2}\mathcal{L}_{\lambda}(\widetilde{\boldsymbol{\theta}};\bm{x})(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})\leq\mathcal{L}_{\lambda}(\boldsymbol{\theta}^{*};\bm{x}),$

where $\widetilde{\boldsymbol{\theta}}$ lies between
$\widehat{\boldsymbol{\theta}}$ and $\boldsymbol{\theta}^{*}$. Thus

$\displaystyle\frac{1}{2}\lambda_{\min}\left(\nabla^{2}\mathcal{L}_{\lambda}(\widetilde{\boldsymbol{\theta}};\bm{x})\right)\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{2}^{2}\leq\frac{1}{2}(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})^{\top}\nabla^{2}\mathcal{L}_{\lambda}(\widetilde{\boldsymbol{\theta}};\bm{x})(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})$
$\displaystyle\quad\leq-(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})^{\top}\nabla\mathcal{L}_{\lambda}(\boldsymbol{\theta}^{*};\bm{x})\leq\|\nabla\mathcal{L}_{\lambda}(\boldsymbol{\theta}^{*};\bm{x})\|_{2}\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{2},$

and thus by Lemma A.3

$\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{2}\leq\frac{2\|\nabla\mathcal{L}_{\lambda}(\boldsymbol{\theta}^{*};\bm{x})\|_{2}}{\lambda_{\min}\left(\nabla^{2}\mathcal{L}_{\lambda}(\widetilde{\boldsymbol{\theta}};\bm{x})\right)}\lesssim\frac{2\|\nabla\mathcal{L}_{\lambda}(\boldsymbol{\theta}^{*};\bm{x})\|_{2}}{\lambda}\lesssim\sqrt{n}.$

###  F.6 Proof of Lemma B.1

In this section, we provide the proof for the upper bounds given in Lemma B.1.

####  F.6.1 Proof of B.1

For each $i\in[n]_{+}$ and $k=2,\ldots,n+1$, define
$n_{i,k}=\sum_{S\in\mathcal{I}_{k}:i\in S}\mathcal{E}_{S}$. Since
$\left|x_{S}^{(i,\ell)}-\frac{e^{\theta_{i}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right|\leq 1$ and
$\operatorname{Var}(x_{S}^{(i,\ell)})\leq{e^{\theta_{i}^{*}}}/\left({\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)\lesssim 1/|S|$, by Bernstein’s inequality,
conditional on $\boldsymbol{\mathcal{E}}$, with probability at least
$1-O(n^{-11})$ we have

$\displaystyle\left|\frac{1}{L}\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k}:i\in
S}\sum_{\ell=1}^{L}\left(x_{S}^{(i,\ell)}-\frac{e^{\theta_{i}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)\right|\lesssim\sqrt{\frac{\sum_{k=2}^{n+1}k^{-1}n_{i,k}\log
n}{L}}+\frac{\log n}{L}.$

Also by Bernstein’s inequality, under the condition that $nM_{n}p\geq C\log n$
for some large enough constant $C>0$, with probability at least $1-O(n^{-11})$
we have that

$\displaystyle\left|\sum_{k=2}^{n+1}k^{-1}n_{i,k}-p\sum_{k=2}^{n+1}k^{-1}\left(\mathbb{I}(i=0){n\choose
k-1}+\mathbb{I}(i\in[n]){n-1\choose
k-2}\right)\right|=\Big{|}\sum_{k=2}^{n+1}\sum_{S\in\mathcal{I}_{k}:i\in
S}k^{-1}\left(\mathcal{E}_{S}-p\right)\Big{|}$
$\displaystyle\lesssim\sqrt{\left(p\sum_{k=2}^{n+1}k^{-2}\left(\mathbb{I}(i=0){n\choose
k-1}+\mathbb{I}(i\in[n]){n-1\choose k-2}\right)\right)\log
n}\lesssim\sqrt{nM_{n}p\log n}\lesssim nM_{n}p,$

and thus with probability at least $1-O(n^{-10})$, we have

$\displaystyle\max_{i\in[n]_{+}}\bigg{|}\sum_{k=2}^{n+1}k^{-1}n_{i,k}-p\sum_{k=2}^{n+1}k^{-1}$
$\displaystyle\left(\mathbb{I}(i=0){n\choose
k-1}+\mathbb{I}(i\in[n]){n-1\choose k-2}\right)\bigg{|}\lesssim nM_{n}p,$
(F.2) $\displaystyle\max_{i\in[n]_{+}}\sum_{k=2}^{n+1}k^{-1}n_{i,k}\lesssim
nM_{n}p,$

and in turn we have that

$\displaystyle\|\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\|_{\infty}$
$\displaystyle=\max_{i\in[n]_{+}}\left|\frac{1}{L}\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}:i\in
S}\sum_{\ell=1}^{L}\left(x_{S}^{(i,\ell)}-\frac{e^{\theta_{i}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)\right|\lesssim\sqrt{\frac{nM_{n}p\log n}{L}}.$

####  F.6.2 Proof of B.2

We first consider
$\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})$.
For $i\in[n]_{+}$, by the mean value theorem we have

$\displaystyle\left[\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\right]_{i}=\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k}:i\in
S}\left(\frac{e^{\widehat{\theta}_{i}}}{\sum_{j\in
S}e^{\widehat{\theta}_{j}}}-\frac{e^{\theta^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)$
$\displaystyle=\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k}:i\in
S}\left\\{\frac{e^{\widetilde{\theta}_{i}}\left(\sum_{j\in
S\backslash\\{i\\}}e^{\widetilde{\theta}_{j}}\right)}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{i}-\sum_{l\in
S\backslash\\{i\\}}\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{l}\right\\}^{\top}(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}),$

where $\widetilde{\boldsymbol{\theta}}$ lies on the line between
$\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}$. Then we have

$\displaystyle\left|\left[\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})-\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})\right]_{i}\right|$
$\displaystyle\leq\left\|\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k}:i\in
S}\left\\{\frac{e^{\widetilde{\theta}_{i}}\left(\sum_{l\in
S\backslash\\{i\\}}e^{\widetilde{\theta}_{l}}\right)}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{i}-\sum_{l\in
S\backslash\\{i\\}}\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{l}\right\\}-[\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})]_{i}\right\|_{1}\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}.$

Now consider any $S\in\boldsymbol{\mathcal{E}}$ such that $i\in S$. Under the
condition that $n\sqrt{\log n/(2^{n}pL)}\leq c$ for some small enough constant
$c>0$, by Theorem 3.1 there exists a small enough constant $\epsilon>0$ such
that
$\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}\leq\epsilon$
with probability at least $1-O(n^{-10})$. Then for any
$\widetilde{\boldsymbol{\theta}}$ lies between $\widehat{\boldsymbol{\theta}}$
and $\boldsymbol{\theta}^{*}$ and any $l\in S$, with probability at least
$1-O(n^{-10})$ we have

$\displaystyle\frac{e^{\widetilde{\theta}_{l}}}{\sum_{j\in
S}e^{\widetilde{\theta}_{j}}}$
$\displaystyle=\frac{e^{\theta_{l}^{*}+(\widetilde{\theta}_{l}-\theta_{l}^{*})}}{\sum_{j\in
S}e^{\theta_{j}^{*}+(\widetilde{\theta}_{j}-\theta_{j}^{*})}}\leq
e^{2\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}}\left(\frac{e^{\theta_{l}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)\leq
e^{2\epsilon}\left(\frac{e^{\theta_{l}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)\lesssim\frac{e^{\theta_{l}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}.$

Then for any $l\in S$, by the mean value theorem one has

$\displaystyle\left|\frac{e^{\widetilde{\theta}_{l}}}{\sum_{j\in
S}e^{\widetilde{\theta}_{j}}}\\!-\\!\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right|\\!\\!\lesssim\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\left(\\!\\!1-\\!\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\\!|\widetilde{\theta}_{l}-\theta_{l}^{*}|\\!+\\!\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\\!\\!\sum_{j\in
S\backslash\\{l\\}}\\!\\!\frac{e^{{\theta}^{*}_{j}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}|\widetilde{\theta}_{j}-\theta_{j}^{*}|$
$\displaystyle\quad\lesssim\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\|\widetilde{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}\leq\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}.$

In turn for any $l\in S\backslash\\{i\\}$, by we have

$\displaystyle\left|\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}-\frac{e^{{\theta}^{*}_{i}}e^{{\theta}^{*}_{l}}}{\left(\sum_{j\in
S}e^{{\theta}^{*}_{j}}\right)^{2}}\right|\leq\left|\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}-\left(\frac{e^{\widetilde{\theta}_{i}}}{\sum_{j\in
S}e^{\widetilde{\theta}_{j}}}\right)\left(\frac{e^{\theta_{i}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)\right|$
$\displaystyle\quad+\left|\left(\frac{e^{\widetilde{\theta}_{i}}}{\sum_{j\in
S}e^{\widetilde{\theta}_{j}}}\right)\left(\frac{e^{\theta_{i}^{*}}}{\sum_{j\in
S}e^{\theta_{j}^{*}}}\right)-\frac{e^{{\theta}^{*}_{i}}e^{{\theta}^{*}_{l}}}{\left(\sum_{j\in
S}e^{{\theta}^{*}_{j}}\right)^{2}}\right|$
$\displaystyle\lesssim\left(\frac{e^{{\theta}^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\left(\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}.$

Thus with probability at least $1-O(n^{-10})$ we have that

$\displaystyle\left\|\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k},i\in
S}\left\\{\frac{e^{\widetilde{\theta}_{i}}\left(\sum_{l\in
S\backslash\\{i\\}}e^{\widetilde{\theta}_{l}}\right)}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{i}-\sum_{l\in
S\backslash\\{i\\}}\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{l}\right\\}-[\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})]_{i}\right\|_{1}$
$\displaystyle\lesssim\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k},i\in
S}\sum_{l\in
S\backslash\\{i\\}}\left|\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}-\frac{e^{{\theta}^{*}_{i}}e^{{\theta}^{*}_{l}}}{\left(\sum_{j\in
S}e^{{\theta}^{*}_{j}}\right)^{2}}\right|$
$\displaystyle\lesssim\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k},i\in
S}\sum_{l\in S\backslash\\{i\\}}\left(\frac{e^{{\theta}^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\left(\frac{e^{{\theta}^{*}_{l}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}$
$\displaystyle\lesssim\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}\sum_{k=2}^{n+1}\sum_{S\in\mathcal{I}_{k},i\in
S}\left(\frac{e^{{\theta}^{*}_{i}}}{\sum_{j\in
S}e^{\theta^{*}_{j}}}\right)\mathcal{E}_{S}\lesssim
nM_{n}p\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty},$

where the last inequality follows from (F.2). Putting the above analysis
together, with probability at least $1-O(n^{-10})$, we have that for any
$i\in[n]_{+}$

$\displaystyle\left|\left[\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})-\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})\right]_{i}\right|\lesssim
nM_{n}p\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}^{2}\lesssim\frac{n\log
n}{L},$

and hence (B.2) holds.

######  Remark F.1.

Recall that

$\left[\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\\!-\\!\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\right]_{i}\\!\\!=\\!\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k},i\in
S}\\!\left\\{\frac{e^{\widetilde{\theta}_{i}}\left(\sum_{j\in
S\backslash\\{i\\}}e^{\widetilde{\theta}_{j}}\right)}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{i}-\\!\\!\sum_{l\in
S\backslash\\{i\\}}\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{l}\right\\}^{\top}\\!\\!\\!\\!(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}),$

where $\widetilde{\boldsymbol{\theta}}$ lies on the line between
$\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}$. Thus with probability
at least $1-O(n^{-11})$, under the condition that $2^{n}p\geq Cn\log n$ for
some large enough constant $C>0$ we have that

$\displaystyle\left|\left[\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\right]_{i}\right|$
$\displaystyle\leq\left\|\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k},i\in
S}\left\\{\frac{e^{\widetilde{\theta}_{i}}\left(\sum_{j\in
S\backslash\\{i\\}}e^{\widetilde{\theta}_{j}}\right)}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{i}-\sum_{l\in
S\backslash\\{i\\}}\frac{e^{\widetilde{\theta}_{i}}e^{\widetilde{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{l}\right\\}\right\|_{1}\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}$
$\displaystyle\lesssim\left\\{\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k},i\in
S}\frac{e^{\widetilde{\theta}_{i}}\left(\sum_{j\in
S\backslash\\{i\\}}e^{\widetilde{\theta}_{j}}\right)}{\left(\sum_{j\in
S}e^{\widetilde{\theta}_{j}}\right)^{2}}\right\\}\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}\lesssim\left(\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k}:i\in
S}k^{-1}\right)\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}$
$\displaystyle\lesssim
nM_{n}p\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty},$

where the last inequality follows from Bernstein’s inequality. Then with
probability at least $1-O(n^{-10})$ we have

$\left\|\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\right\|_{\infty}\lesssim
nM_{n}p\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty}\lesssim
n\sqrt{\frac{M_{n}p\log n}{L}}.$ (F.3)

####  F.6.3 Proof of B.3

For any $i\in[n]_{+}$, very similar to the proof in Section F.6.2, with
probability at least $1-O(n^{-10})$ we have

$\displaystyle\|[\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})]_{i}-[\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})]_{i}\|_{1}$
$\displaystyle=\left\|\sum_{k=2}^{n+1}\sum_{S\in\boldsymbol{\mathcal{E}}_{k},i\in
S}\left\\{\frac{e^{\widehat{\theta}_{i}}\left(\sum_{l\in
S\backslash\\{i\\}}e^{\widehat{\theta}_{l}}\right)}{\left(\sum_{j\in
S}e^{\widehat{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{i}-\sum_{l\in
S\backslash\\{i\\}}\frac{e^{\widehat{\theta}_{i}}e^{\widehat{\theta}_{l}}}{\left(\sum_{j\in
S}e^{\widehat{\theta}_{j}}\right)^{2}}\boldsymbol{e}_{l}\right\\}-[\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})]_{i}\right\|_{1}$
$\displaystyle\lesssim
nM_{n}p\|\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{\infty},$

and hence by Theorem 3.1 with probability at least $1-O(n^{-10})$ we have

$\|\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\|_{\infty}=\max_{i\in[n+1]}\|[\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})]_{i}-[\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})]_{i}\|_{1}\lesssim
n\sqrt{\frac{M_{n}p\log n}{L}}.$

####  F.6.4 Proof of B.4

For the simplicity of notation, we let
$\widetilde{\lambda}_{1}\geq\ldots\geq\widetilde{\lambda}_{n}\geq\widetilde{\lambda}_{n+1}=0$
be the eigenvalues of $\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})$ in
descending order, and let $\bm{v}_{1},\ldots,\bm{v}_{n}$ and
$\frac{1}{\sqrt{n+1}}\mathbf{1}$ be the normalized eigenvectors corresponding
to $\widetilde{\lambda}_{1},\ldots,\widetilde{\lambda}_{n+1}$. From the proof
of Lemma A.2, we know that for any $\boldsymbol{\theta}\in\mathbb{R}^{n+1}$
such that $\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\|_{\infty}\leq C$ for
some constant $C>0$, we have
$\frac{1}{(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}}\mathbf{L}_{\boldsymbol{\mathcal{E}}}\preceq\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})\preceq(\kappa_{\boldsymbol{\theta}}e^{2C})^{2}\mathbf{L}_{\boldsymbol{\mathcal{E}}}$.
Besides, by Lemma A.1, with probability at least $1-O(n^{-10})$, we have

$\lambda_{\min,\perp}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\geq\frac{1}{2}(nM_{n}+N_{n})p,\lambda_{\max}(\mathbf{L}_{\boldsymbol{\mathcal{E}}})\leq\frac{3}{2}(n+1)N_{n}p.$

Thus we have that $\widetilde{\lambda}_{1}\asymp\widetilde{\lambda}_{n}\asymp
nM_{n}p$ with probability at least $1-O(n^{-10})$. Also recall that
$\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})\mathbf{1}=\mathbf{0}$, and
hence for any constant $C>0$, we have the eigen-decomposition

$\displaystyle\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&C\mathbf{1}\\\
C\mathbf{1}^{\top}&0\end{pmatrix}=\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&\mathbf{0}\\\
\mathbf{0}&0\end{pmatrix}+C\begin{pmatrix}\mathbf{0}&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}=\sum_{i=1}^{n}\widetilde{\lambda}_{i}\begin{pmatrix}\bm{v}_{i}\\\
0\end{pmatrix}\begin{pmatrix}\bm{v}_{i}\\\ 0\end{pmatrix}^{\top}$
$\displaystyle\quad+C\sqrt{n+1}\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
\frac{1}{\sqrt{2}}\end{pmatrix}\\!\\!\\!\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
\frac{1}{\sqrt{2}}\end{pmatrix}^{\top}\\!\\!\\!\\!\\!-C\sqrt{n+1}\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
-\frac{1}{\sqrt{2}}\end{pmatrix}\\!\\!\\!\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
-\frac{1}{\sqrt{2}}\end{pmatrix}^{\top}.$

It is not hard to verify by the relationship between $\bm{v}_{i}$’s and
$\mathbf{1}$ that the above representation is a valid eigen-decomposition of
$\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&C\mathbf{1}\\\
C\mathbf{1}^{\top}&0\end{pmatrix}$. Thus we can see that the $n+2$ eigenvalues
of
$\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&C\mathbf{1}\\\
C\mathbf{1}^{\top}&0\end{pmatrix}$ are
$\widetilde{\lambda}_{1},\ldots,\widetilde{\lambda}_{n}$ and $\pm
C\sqrt{n+1}$, and
$\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&C\mathbf{1}\\\
C\mathbf{1}^{\top}&0\end{pmatrix}^{-1}$ would take the following form

$\displaystyle\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&C\mathbf{1}\\\
C\mathbf{1}^{\top}&0\end{pmatrix}^{-1}=\sum_{i=1}^{n}\widetilde{\lambda}_{i}^{-1}\begin{pmatrix}\bm{v}_{i}\\\
0\end{pmatrix}\\!\\!\begin{pmatrix}\bm{v}_{i}\\\
0\end{pmatrix}^{\top}\\!\\!\\!\\!+C^{-1}(n+1)^{-1/2}\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
\frac{1}{\sqrt{2}}\end{pmatrix}\\!\\!\\!\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
\frac{1}{\sqrt{2}}\end{pmatrix}^{\top}\\!\\!\\!\\!\\!$
$\displaystyle\quad-C^{-1}(n+1)^{-1/2}\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
-\frac{1}{\sqrt{2}}\end{pmatrix}\\!\\!\\!\begin{pmatrix}\frac{1}{\sqrt{2(n+1)}}\mathbf{1}\\\
-\frac{1}{\sqrt{2}}\end{pmatrix}^{\top}=\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}&\frac{1}{C(n+1)}\mathbf{1}\\\
\frac{1}{C(n+1)}\mathbf{1}^{\top}&0\end{pmatrix},$

where
$\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}=\sum_{i=1}^{n}\widetilde{\lambda}_{i}^{-1}\bm{v}_{i}\bm{v}_{i}^{\top}$.
Then for any $\boldsymbol{\theta}\in\mathbb{R}^{n+1}$ such that
$\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\|_{\infty}=O(1)$ and a constant
$C_{n}>0$ (dependent of $n$) such that $nM_{n}p\lesssim C_{n}\sqrt{n}$, we
have

$\left\|\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&C_{n}\mathbf{1}\\\
C_{n}\mathbf{1}^{\top}&0\end{pmatrix}^{-1}\right\|_{2}=\max(\frac{1}{\lambda_{n}(\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x}))},\frac{1}{C_{n}\sqrt{n+1}})\lesssim\frac{1}{nM_{n}p}.$

Thus by B.3, with probability at least $1-O(n^{-10})$ we have

$\displaystyle\left\|\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{-1}-\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{-1}\right\|_{2}=\left\|\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}-\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})^{\dagger}\right\|_{2}$
$\displaystyle=\left\|\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&C_{n}\mathbf{1}\\\
C_{n}\mathbf{1}^{\top}&0\end{pmatrix}^{-1}-\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})&C_{n}\mathbf{1}\\\
C_{n}\mathbf{1}^{\top}&0\end{pmatrix}^{-1}\right\|_{2}$
$\displaystyle\leq\\!\left\|\\!\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\\!\\!C_{n}\mathbf{1}\\\
C_{n}\mathbf{1}^{\top}&\\!\\!0\end{pmatrix}^{\\!\\!-1}\\!\right\|_{2}\\!\left\|\\!\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})&\\!\\!C_{n}\mathbf{1}\\\
C_{n}\mathbf{1}^{\top}&\\!\\!0\end{pmatrix}^{\\!\\!-1}\\!\right\|_{2}\\!\left\|\\!\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\\!\\!C_{n}\mathbf{1}\\\
\\!\\!C_{n}\mathbf{1}^{\top}&0\end{pmatrix}\\!-\\!\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})&\\!\\!C_{n}\mathbf{1}\\\
\\!\\!C_{n}\mathbf{1}^{\top}&0\end{pmatrix}\\!\right\|_{2}$
$\displaystyle\lesssim\frac{\sqrt{n}}{(nM_{n}p)^{2}}\|\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})\|_{\infty}\lesssim\frac{1}{\sqrt{n}M_{n}p}\sqrt{\frac{\log
n}{M_{n}pL}}.$

###  F.7 Proof of Corollary B.2

From the proof of Lemma B.1 it can be seen that

$\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{-1}=\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}&\frac{1}{n+1}\mathbf{1}\\\
\frac{1}{n+1}\mathbf{1}^{\top}&0\end{pmatrix}$

holds true for any $\boldsymbol{\theta}\in\mathbb{R}^{n+1}$, where
$\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}$ is the Moore-
Penrose inverse of $\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})$. Now
define
$\mathbf{\Gamma}=(\bm{v}_{1},\bm{v}_{2},\ldots,\bm{v}_{n},\frac{1}{\sqrt{n+1}}\mathbf{1})$,
and denote by
$\boldsymbol{\gamma}_{j}=(\gamma_{j1},\ldots,\gamma_{jn},\frac{1}{\sqrt{n+1}})$
the $j$-th row of $\mathbf{\Gamma}$, $j\in[n+1]$. Then since $\mathbf{\Gamma}$
is orthonormal, it can be seen that
$\|\boldsymbol{\gamma}_{j}\|_{2}^{2}=\sum_{k=1}^{n}\gamma_{jk}^{2}+\frac{1}{n+1}=1$
and $\sum_{k=1}^{n}\gamma_{jk}^{2}\asymp 1$. Thus for any
$\boldsymbol{\theta}\in\mathbb{R}^{n+1}$ such that
$\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\|_{\infty}<C$ for some constant
$C>0$, for $j,k\in[n+1],j\neq k$, with probability at least $1-O(n^{-10})$ we
have

$\displaystyle[\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}]_{jj}$
$\displaystyle=\boldsymbol{e}_{j}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}\boldsymbol{e}_{j}=\boldsymbol{\gamma}_{j}^{\top}\begin{pmatrix}\widetilde{\lambda}_{1}^{-1}&\ldots&&0\\\
\vdots&\ddots&&\\\ &&\widetilde{\lambda}_{n}^{-1}&\\\
0&&&0\end{pmatrix}\boldsymbol{\gamma}_{j}=\sum_{i=1}^{n}\gamma_{ji}^{2}\widetilde{\lambda}_{i}^{-1}\asymp\frac{1}{nM_{n}p},$
$\displaystyle\big{|}[\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}]_{jk}\big{|}$
$\displaystyle=\big{|}\boldsymbol{e}_{j}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}\boldsymbol{e}_{k}\big{|}\leq\|\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})^{\dagger}\|_{2}\lesssim\frac{1}{nM_{n}p}.$

###  F.8 Proof of Lemma B.3

By Corollary B.2 and the definition of $\widehat{\boldsymbol{\theta}}^{d}$, we
have that

$\displaystyle\widehat{\boldsymbol{\theta}}^{d}$
$\displaystyle=\widehat{\boldsymbol{\theta}}^{\prime}-\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})^{\dagger}\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})=\widehat{\boldsymbol{\theta}}^{\prime}-\left(\mathbf{I}_{n+1},\mathbf{0}\right)\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{-1}\begin{pmatrix}\mathbf{I}_{n+1}\\\
\mathbf{0}\end{pmatrix}\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})$
$\displaystyle=\left(\mathbf{I}_{n+1},\mathbf{0}\right)\begin{pmatrix}\widehat{\boldsymbol{\theta}}^{\prime}\\\
0\end{pmatrix}-\left(\mathbf{I}_{n+1},\mathbf{0}\right)\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{-1}\begin{pmatrix}\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\\\
0\end{pmatrix},$

then left-multiply both sides by $\left(\mathbf{I}_{n+1},\mathbf{0}\right)$ we
have

$\displaystyle\begin{pmatrix}\widehat{\boldsymbol{\theta}}^{d}\\\
0\end{pmatrix}$ $\displaystyle={\rm
diag}(\mathbf{I}_{n+1},0)\begin{pmatrix}\widehat{\boldsymbol{\theta}}^{\prime}\\\
0\end{pmatrix}-{\rm
diag}(\mathbf{I}_{n+1},0)\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{-1}\begin{pmatrix}\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\\\
0\end{pmatrix}$
$\displaystyle\quad=\begin{pmatrix}\widehat{\boldsymbol{\theta}}^{\prime}\\\
0\end{pmatrix}-\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{-1}\begin{pmatrix}\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\\\
0\end{pmatrix},$

where the second equality is due to the fact that
$\mathbf{1}_{n+1}^{\top}\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})=0$.
Hence we can see that $\widehat{\boldsymbol{\theta}}^{d}$ can be treated as
the sub-vector for the first $n+1$ coordinates of an augmented Newton-debiased
estimator. Recall that we state in the proof of Theorem 3.1, we will abuse the
notation and let $\widehat{\boldsymbol{\theta}}$ denote
$\widehat{\boldsymbol{\theta}}^{\prime}={\mathbf{P}}_{\mathbf{1}}^{\perp}\widehat{\boldsymbol{\theta}}$
and let $\boldsymbol{\theta}^{*}$ denote
$\boldsymbol{\theta}^{*\prime}={\mathbf{P}}_{\mathbf{1}}^{\perp}\boldsymbol{\theta}^{*}$.
Then we have the following decomposition

$\displaystyle\left(\begin{array}[]{c}\\!\\!\widehat{\boldsymbol{\theta}}^{d}-\boldsymbol{\theta}^{*}\\!\\!\\\
0\end{array}\right)\\!\\!=$
$\displaystyle\underbrace{\left(\\!\\!\\!\left(\begin{array}[]{cc}\\!\\!\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{array}\right)^{\\!\\!-1}\\!\\!\\!\\!\\!\\!-\left(\begin{array}[]{cc}\\!\\!\nabla^{2}\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{array}\right)^{\\!\\!-1}\\!\right)\\!\\!\left(\begin{array}[]{c}\\!\\!\\!-\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\\!+\\!\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\\!\\!\left(\widehat{\boldsymbol{\theta}}\\!-\\!\boldsymbol{\theta}^{*}\right)\\!\\!\\!\\!\\!\\\
0\end{array}\right)}_{I_{1}}$
$\displaystyle+\underbrace{\left(\begin{array}[]{cc}\nabla^{2}\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{array}\right)^{-1}\left(\begin{array}[]{c}\nabla\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)-\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})+\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\left(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\right)\\\
0\end{array}\right)}_{I_{2}}$
$\displaystyle+\left(\begin{array}[]{cc}\nabla^{2}\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{array}\right)^{-1}\left(\begin{array}[]{c}-\nabla\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)\\\
0\end{array}\right).$

By Lemma B.1, we can bound the term $I_{1}$ and $I_{2}$ accordingly,

$\displaystyle\|I_{1}\|_{2}$
$\displaystyle\leq\left\|\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{\\!\\!-1}\\!\\!-\\!\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{\\!\\!-1}\right\|_{2}\left\|-\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})+\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})\right\|_{2}$
$\displaystyle\lesssim\sqrt{n}\left\|\begin{pmatrix}\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{\\!\\!-1}\\!\\!-\\!\begin{pmatrix}\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})&\mathbf{1}\\\
\mathbf{1}^{\top}&0\end{pmatrix}^{\\!\\!-1}\right\|_{2}\left\|-\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})+\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})\right\|_{\infty}$
$\displaystyle\lesssim\sqrt{n}\times\frac{1}{\sqrt{n}M_{n}p}\sqrt{\frac{\log
n}{M_{n}pL}}\left(\frac{n\log n}{L}+\sqrt{\frac{nM_{n}p\log
n}{L}}\right)\lesssim\frac{\sqrt{n}\log n}{M_{n}pL}\left(\sqrt{\frac{n\log
n}{M_{n}pL}}+1\right),$

and

$\displaystyle\|I_{2}\|_{2}$
$\displaystyle=\left\|\left(\begin{array}[]{cc}\nabla^{2}\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)^{\dagger}&\frac{1}{n+1}\mathbf{1}\\\
\frac{1}{n+1}\mathbf{1}^{\top}&0\end{array}\right)\\!\\!\left(\begin{array}[]{c}\\!\\!\nabla\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)-\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})+\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\left(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\right)\\\
\\!\\!0\end{array}\\!\\!\\!\right)\right\|_{2}$
$\displaystyle=\left\|\nabla^{2}\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)^{\dagger}\left(\nabla\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)-\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})+\nabla^{2}\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})\left(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\right)\right)\right\|_{2}$
$\displaystyle\lesssim\sqrt{n}\left\|\nabla^{2}\mathcal{L}\left(\boldsymbol{\theta}^{*};\bm{x}\right)^{\dagger}\right\|_{2}\|\nabla\mathcal{L}(\widehat{\boldsymbol{\theta}};\bm{x})-\nabla\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})-\nabla^{2}\mathcal{L}(\boldsymbol{\theta}^{*};\bm{x})(\widehat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*})\|_{\infty}$
$\displaystyle\lesssim\frac{n\log
n}{L}\times\frac{\sqrt{n}}{nM_{n}p}=\frac{\sqrt{n}\log n}{M_{n}pL},$

where the second equality is due to the fact that
$\mathbf{1}_{n+1}^{\top}\nabla\mathcal{L}(\boldsymbol{\theta};\bm{x})=0$ and
$\mathbf{1}_{n+1}^{\top}\nabla^{2}\mathcal{L}(\boldsymbol{\theta};\bm{x})=\mathbf{0}$
for any $\boldsymbol{\theta}\in\mathbb{R}^{n+1}$. Thus in turn we have that

$\|\mathbf{R}_{0}\|_{2}\leq\|I_{1}\|_{2}+\|I_{2}\|_{2}\lesssim\frac{\sqrt{n}\log
n}{M_{n}pL}\left(\sqrt{\frac{n\log
n}{M_{n}pL}}+1\right)\lesssim\frac{n^{5/2}\log
n}{2^{n}pL}\left(\sqrt{\frac{n^{3}\log n}{2^{n}pL}}+1\right).$