\section{Introduction}
Community detection \cite{abbe2017community, girvan2002community, zhao2011community} is a central problem in network science. It is to recover hidden community structures from network data and has wide applications in social science, neuroscience, computer science, and physics.   Among various approaches for community detection,
spectral clustering \cite{rohe2011spectral, von2008consistency, jin2022mixed, jin2015fast, lei2020consistency, paul2020spectral, gulikers2017spectral, zhang2020detecting, ghoshdastidar2017consistency} is a particularly popular one and has achieved tremendous success.   It  first reduces the dimensionality of data by  a spectral decomposition and performs clustering in a reduced-dimension space.
 It  is computationally appealing, easy to implement, and has surprisingly good performance. 

 Driven by its popularity and success, there has been growing interest in theoretical and statistical analysis for the performance of spectral clustering. In most literature \cite{lei2015consistency, rohe2011spectral, qin2013regularized, zhou2019analysis, gao2017sbm_algo}, spectral clustering is shown to attain polynomially small errors. As a result, it is often used as a warm start to initialize  \cite{gao2017sbm_algo, lu2016statistical, xu2020optimal, han2020exact, gao2022community} delicate procedures in order to provably achieve exponentially small errors and even optimal statistical accuracy. However, spectral clustering performs exceptionally well numerically, indicating a gap between theory and practice. This raises important questions such as whether spectral clustering achieves exponentially small errors and how small it can be.
 
 
 
 
In this paper, we carry out a sharp statistics analysis on the performance of  spectral clustering for community detection 
to precisely characterize its statistical accuracy with matching upper and lower bounds.
We consider the Stochastic Block Model (SBM) \cite{holland1983stochastic}, which is the most studied model for community detection.
Consider an $n$-node network with $k$ communities. For every two nodes, we observe an edge with probability $p$ if they belong to the same community and $q$ otherwise. The goal is to recover the hidden community structure $z^*$ given the network.
We study a popular spectral clustering procedure \cite{lei2015consistency, gao2017sbm_algo, zhou2019analysis, pensky2019spectral} $\hat z$
that is based on the eigendecomposition of the adjacency matrix. It first regularizes \cite{joseph2016impact} the network by removing high-degree nodes, a step that is necessary   for the concentration of sparse networks \cite{le2017concentration, chin2015stochastic}.  It then weights leading eigenvectors of the regularized adjacency matrix by corresponding eigenvalues, followed by the $k$-means clustering. Its clustering error can be measured by a loss $\ell(\hat z,z^*)$. See Sections \ref{sec:SBM}-\ref{sec:sc} for more details about the model and the algorithm.
 The main result of this paper is summarized below in Theorem \ref{thm:introduction}.
 
\begin{theorem}\label{thm:introduction}
Assume $k$ is a constant and all community sizes $n_1,n_2,\ldots,n_k$ are of the same order. Assume $p,q$ satisfy $0<q<p \leq 1/10$ and are of the same order. We further assume $\frac{n(p-q)^2}{p}\rightarrow\infty$. Then
\begin{align*}
&\mathbb{E} \ell(\hat z,z^*)\leq \ebr{-\br{1-o(1)}J_{\min}}+2n^{-3},\\
\text{and }\quad& \mathbb{E} \ell(\hat z,z^*)\geq \ebr{-\br{1+o(1)} J_{\min}}-2n^{-3},
\end{align*}
where
\begin{align}\label{eqn:J_min}
J_{\min}:= \min_{1\leq a\neq b\leq k}\max_{t} \br{(n_a-n_b)t \frac{p+q}{2} - n_a \log\br{q e^t + 1-q} - n_b\log \br{pe^{-t}+1-p}}.
\end{align}

\end{theorem}

Theorem \ref{thm:introduction} gives both upper and lower bounds for the partial recovery of spectral clustering $\hat z$. We note that the additive term $2n^{-3}$ in the error bounds can be replaced by $n^{-C}$ for an arbitrarily large constant $C>0$, and in general should be ignored. Then the upper and lower bounds are both in an exponential form with a matching asymptotic exponent $J_{\min}$. In this way, Theorem \ref{thm:introduction} gives an exact characterization of the error exponent of the spectral clustering, even including the sharp leading constant. Theorem \ref{thm:introduction} holds under mild conditions, allowing networks to have multiple imbalanced communities and to be sparse with $p,q\ll (\log n)/n$. The assumption ${n(p-q)^2}/{p}\rightarrow\infty$ is known to be the necessary and sufficient condition to have consistent community detection \cite{zhang2016minimax}.
 It is also worth mentioning that Theorem \ref{thm:introduction} characterizes precisely the performance of the spectral clustering for each instance of $z^*$, which is beyond the minimax framework that only focuses on the worst case of a large parameter space.


The asymptotic exponent $J_{\min}$ in Theorem \ref{thm:introduction} has a
complicated dependence on $p,q$ and the community sizes. Despite  no explicit expression,
the quantity $J_{\min}$ is closely related to tail probabilities of Bernoulli random variables. Let $\{X_i\}$ and $\{Y_j\}$ be independent Bernoulli random variables with probabilities $q,p$ respectively.  By Chernoff bound (see Lemma \ref{lem:binomial_diff}), 
\begin{align*}
 \min_{1\leq a\neq b\leq k} -\log\pbr{\sum_{i\in[n_a]} X_i - \sum_{j\in[n_b]} Y_j \geq (n_a-n_b)\frac{p+q}{2}} =(1+o(1))J_{\min}.
\end{align*}
To further explain why $J_{\min}$ appears in Theorem \ref{thm:introduction} and is fundamental for the performance of the spectral clustering, we study an oracle estimator that is inspired by $\hat z$ but utilizes the unobserved population eigenstructure instead of the sample one. Its corresponding statistical accuracy turns out to be determined by the aforementioned tail probabilities (see Section \ref{sec:oracel}). 

Under the setting of Theorem \ref{thm:introduction}, $J_{\min}$ and  $n(p-q)^2/p$ can be shown to be of the same order (see Lemma \ref{lem:J}). Hence, the assumption $n(p-q)^2/p\rightarrow\infty$ in Theorem \ref{thm:introduction} can  be replaced by $J_{\min}\rightarrow\infty$ and   is the sufficient and necessary condition for $\hat z$ to have a vanishing error.
Theorem \ref{thm:introduction} also immediately indicates a sharp threshold of the exact recovery. When $J_{\min}\geq (1+\epsilon) \log n$ for any constant $\epsilon>0$,  $\hat z$ achieves the exact recovery (i.e., $\ell(\hat z,z^*)=0$) with high probability. When $J_{\min}\leq (1+\epsilon) \log n$ for any constant $\epsilon>0$, $\hat z$ fails to achieve the exact recovery with  constant probability, i.e., $\pbr{\ell(\hat z,z^*)\neq 0}\geq c$ for some constant $c>0$.   







The most related work in literature is  \cite{abbe2020entrywise} that considers a very special setting where the network has two equal-sized communities and $p=a(\log n)/n, q=b(\log n)/n$ with fixed constants $a,b$. The spectral clustering procedure studied in  \cite{abbe2020entrywise} has a simple form: it only utilizes  the second leading eigenvector of the adjacency matrix and partitions the network using signs of coordinates. Under this setting, \cite{abbe2020entrywise} proves the spectral clustering achieves an optimal exponential rate.
However, the procedure, result, and proof technique of \cite{abbe2020entrywise} are limited to this special setting and cannot  be extended to even slightly more general cases such as that  the network has two imbalanced communities or $p,q$ are of a smaller order of $(\log n)/n$. On the contrary, our results hold for general SBMs  and cover the setting of \cite{abbe2020entrywise} as a special case. Other closely related papers including \cite{loffler2019optimality, abbe2022lp, zhang2022leaveone} obtain exponential error bounds for  spectral clustering under Gaussian and sub-Gaussian mixture models. However, they rely heavily on Gaussianity and sub-Gaussianity of data. Direct application of their results to networks or other binary data can only lead to trivial upper bounds. 

The key  to Theorem \ref{thm:introduction} is a novel truncated $\ell_2$ perturbation analysis for eigenvectors and a proof idea of  eigenvectors truncation. Let $u$ be one of the leading $k$ eigenvectors of the regularized adjacency matrix.  
Analysis of the spectral clustering shows that tail probabilities of quantities in the form of $\sum_{i\in[n]}u_i(X_i -\mathbb{E} X_i)$ play a crucial role, where $\{X_i\}_{i\in[n]}$ are some Bernoulli random variables such as edges of a node. Direction applications of classical concentration inequalities for Bernoulli random variables often involve $\norm{u}_{\infty}$  that has some inevitable $\log n$ factor. To deal with this $\log n$ factor and to derive meaningful tail probabilities, $p$ has to be at least of an order $(\log n)/n$ as seen in literature \cite{chen2022partial, abbe2020entrywise, chen2019spectral}. However, in this paper, we consider sparse networks with the connectivity probability allowed to be far smaller than $(\log n)/n$ and the aforementioned analysis breaks down.
Instead, we truncate coordinates of $u$ by some carefully selected threshold $t_0$. The truncated eigenvector has an $\ell_\infty$ norm bounded by $t_0$  and  its inner product with $\{X_i-\mathbb{E} X_i\}$ is well-controlled with desired tail probabilities. The approximation error of replacing $u$ by its truncated counterpart turns out to be related to $\sum_{i\in[n]} \norm{u_i}^2\indic{\abs{u_i}\geq t_0}$, which we refer to as a truncated $\ell_2$ norm of $u$. We establish an upper bound for the  truncated $\ell_2$ norm in Theorem \ref{thm:truncated_l2} and further show such approximation error is negligible. The idea of eigenvector truncation and Theorem \ref{thm:truncated_l2} are critical to establishing sharp upper and lower bounds in Theorem \ref{thm:introduction}, and might be useful for fine-grained spectral perturbation analysis of other binary random matrices. To establish Theorem \ref{thm:introduction}, we also use a leave-one-out technique \cite{chen2021spectral, abbe2020entrywise} to decouple dependence between the eigenvectors and the regularized adjacency matrix.







\paragraph{Organization. }
In Sections \ref{sec:SBM}-\ref{sec:sc}, we provide more details about  SBMs and give a detailed implementation of the spectral clustering. In Section \ref{sec:polynomial}, we give a preliminary polynomial upper bound for the performance of the spectral clustering. In Section \ref{sec:oracel}, we carry out an oracle analysis to provide intuition on the fundamental limits of the spectral clustering. 
We establish the upper bound part of Theorem \ref{thm:introduction} in Section \ref{sec:upper} and the lower bound part in Section \ref{sec:lower}.  The truncated $\ell_2$ perturbation analysis of eigenvectors is presented in  Section \ref{sec:truncated}. The proofs of the upper bound and the truncated $\ell_2$ perturbation analysis are given in Section \ref{sec:proof_upper} and Section \ref{sec:proof_truncated}, respectively. We include the proof of the lower bound in the appendix, along with proofs of the results of Section \ref{sec:pre} and all auxiliary lemmas.



\paragraph{Notation. } For any positive integer $r$, let $[r]:=\{1,2,\ldots, r\}$. For any vector $x$, we denote $\norm{x}_\infty:=\max_{i}\abs{x_i}$ to be its $\ell_{\infty}$ norm and $\norm{x}_1 = \sum_i \abs{x_i}$ to be its $\ell_1$ norm.
For a matrix $A$, denote $A_{i\cdot}$ and $A_{\cdot i}$ to be its $i$th row and column, receptively. We further denote $\norm{A}$ to be its operator norm, $\fnorm{A}$ to be its Frobenius norm, and $\norm{A}_{2,\infty}:= \max_i \norm{A_{i\cdot}}$ to be its maximum $\ell_2$ norms of rows. For any two numbers $a,b\in\mathbb{R}$, we denote $a\wedge b:= \min\{a,b\}$ and $a\vee b:= \max\{a,b\}$. We denote $\indic{\cdot}$ as the indicator function. 
For any two positive integers $a,b$, we denote $I_a$ to be the $a\times a$ identity matrix and $\mathcal{O}(a,b)$  to be the set of all $a\times b$ matrices with orthogonal columns. For any random vectors $X,Y$, and $Z$, we use $X\perp Y|Z$ to mean $X$ and $Y$ are independent conditioned on $Z$. For any event $\mathcal{G}$, we denote $\mathcal{G}^\complement$ to be its complement.
 
\section{Preliminaries}\label{sec:pre}
\subsection{Community Detection and Stochastic Block Models}\label{sec:SBM}
Consider an $n$-node network with its adjacency matrix denoted by $A\in\{0,1\}^{n\times n}$ such that $A=A^T$ and $A_{ii}=0$ for all $i\in[n]$. Under the SBM, all edges $\{A_{ij}\}_{1\leq i<j\leq n}$ are independent Bernoulli random variables with probabilities depending on the underlying community structure.
Let $z^*\in[k]^n$ be a community assignment vector such that each coordinate indicates which community the corresponding node belongs to. 
We assume
\begin{align*}
\mathbb{E} A_{ij} = \begin{cases}
p,\text{ if }z^*_i=z^*_j,\\
q,\text { o.w.,}
\end{cases}
\end{align*}
for all $1\leq i<j\leq n$, where $0<q<p<1$. That is, nodes are more likely to be connected if they are from the same community: the probability for two nodes to be connected is $p$ if they belong to the same community and is $q$ otherwise. The goal of community detection is to estimate $z^*$ given the network $A$. Throughout the paper, we assume $k$, the number of communities, is known.

We denote $n_1,\ldots,n_k$ to be community sizes such that $n_a:= \sum_{i\in[n]}\indic{z^*_i =a}$ for all $a\in[k]$. Define $\beta := ({\min_{a\in[k]}n_a})/{(n/k)}$ such that $\beta n/k$ is the smallest community size. 
For any $z\in [k]^n$, its performance for community detection  can be measured by the following loss function \cite{gao2017sbm_algo}:
\begin{align*}
\ell(z,z^*) := \frac{1}{n} \min_{\phi\in\Phi} \sum_{i\in[n]} \indic{z_i= \phi(z^*_i)},
\end{align*}
where $\Phi:=\{\phi:\phi \text{ is a bijection from $[k]$ to $[k]$}\}$. It is a value between 0 and 1, giving the proportions of nodes mis-clustered in $z$ compared to $z^*$.

\subsection{Spectral Clustering}\label{sec:sc}
Spectral clustering refers to clustering procedures built upon the eigendecomposition or the singular value decomposition of matrices constructed from data. There exist different variants of spectral clustering for community detection \cite{newman2006modularity, priebe2019two, sarkar2015role, cape2019spectral, jin2015fast}. They  differ in the matrix on
which the spectral decomposition is applied and in what spectral components are used for the
subsequent clustering. The spectral clustering considered in this paper is a popular one and has been widely studied  in literature. It contains three steps summarized below with the detailed implementation given in Algorithm \ref{alg:1}.

 

\begin{algorithm}[ht]
\SetAlgoLined
\KwIn{Adjacency matrix $A\in\{0,1\}^{n\times n}$,  number of communities $k$}
\KwOut{Community assignment $\hat z$}
 \nl Define  $d_i := \sum_{j\neq i} A_{ij}$ for all $i\in[n]$ to be degrees of $A$. Let $\tilde A$  be a trimmed version of $A$ by replacing its $i$th row and column by 0 whenever $d_i\geq \tau$ where $\tau:=20np$, for all $i\in[n]$. That is,  for all $i,j\in[n]$, 
\begin{align*}
\tilde A_{ij} :=\begin{cases}
A_{ij},\text{ if }d_i,d_j<\tau,\\
0,\text{ o.w.}
\end{cases}
\end{align*} \\
 \nl Let the eigendecomposition of $\tilde A$ be $\tilde A = \sum_{i\in[n]} \lambda_i u_iu_i^T$ with eigenvalues $\lambda_1\geq\ldots\geq \lambda_n$ and eigenvectors $u_1,\ldots, u_n\in\mathbb{R}^n$. Define $U:=(u_1,\ldots,u_k)\in\mathbb{R}^{n\times k}$ to be the leading  eigensapce and $\Lambda:=\text{diag}(\lambda_1,\ldots,\lambda_k)\in\mathbb{R}^{k\times k}$ to be the diagonal matrix with the leading $k$ eigenvalues. Denote $U_{1\cdot},\ldots,U_{n\cdot}\in\mathbb{R}^{1\times n}$ to be rows of $U$.\\
 \nl Apply $k$-means on the rows of $U\Lambda\in\mathbb{R}^{n\times k}$ and let $\hat z$ be the clustering output. That is, 
 \begin{align}
(\hat z,\{\hat \theta_1,\ldots,\hat \theta_k\}):= \mathop{\rm argmin}_{z\in[k]^n, \theta_1,\ldots,\theta_k\in\mathbb{R}^{1\times k}} \sum_{i\in[n]}\norm{U_{i\cdot}\Lambda - \theta_{z_i}}^2.\label{eqni:1}
 \end{align}
\caption{Spectral Clustering for Community Detection in Stochastic Block Models \label{alg:1}}
\end{algorithm}

In the first step, we regularize the adjacency matrix by removing high-degree nodes, i.e., nodes with degrees greater or equal to $20np$. This step is necessary for sparse networks as the adjacency matrix $A$  is known to be away from its expectation $\mathbb{E} A$ when $p\ll (\log n)/n$. On the contrary, by zeroing out rows and columns of $A$ that correspond to the high-degree nodes, we have a trimmed adjacency matrix $\tilde A$ that is highly concentrated around $\mathbb{E} A$ (see Lemma \ref{lem:tilde_A_concentration}). The threshold $20np$ is selected for the convenience of theoretical analysis and can be replaced by other values such as $Cnp$ for some large constant $C$.

 In the second step, we obtain two matrices $U,\Lambda$ through the eigendecomposition of  $\tilde A$, where $U$ is a matrix including the leading $k$ eigenvectors and $\Lambda$ is a diagonal matrix with the leading $k$ eigenvalues. Throughout the paper, we refer to $U$ as the leading eigenspace of $\tilde A$. Since eigenvectors are not of equal importance, they are weighted with their corresponding eigenvalues and $U\Lambda$ is used for the subsequent clustering.
 
 In the third step, we perform the $k$-means clustering on rows of $U\Lambda$ which are of dimension $k$.
 Compared to the adjacency matrix $A$, we greatly reduce the dimensionality of data from $n$ to $k$ as usually $k\ll n$ and perform clustering in a low-dimensional space. The $k$-means clustering returns a partition of the data and cluster centers, which are denoted as $\hat z$ and $\{\hat \theta_a\}_{a\in[k]}$ respectively.


\subsection{A Polynomial Upper Bound}\label{sec:polynomial}
In this section, we provide preliminary analysis for the spectral clustering and show it achieves a polynomial error rate. We first introduce a matrix $P\in\mathbb{R}^{n\times n}$ defined as
\begin{align*}
P_{ij}:=p\indic{z^*_i=z^*_j} + q\indic{z^*_i\neq z^*_j},\forall i,j\in[n].
\end{align*}
It can be viewed as a population matrix with $\tilde A$ being its sample counterpart.
Note that $P$ is different from the expectation matrix $\mathbb{E} A$ as the latter has all diagonal entries being zero due to the fact that the network has no self-loops. 

The matrix $P$ is rank-$k$. Let the eigendecomposition of $P$ be $P=\sum_{i\in[k]}\lambda^*_i u^*_i u^{*T}_i$ with eigenvalues $\lambda_1^*\geq\ldots\geq \lambda_k^*$ and eigenvectors $u_1^*,\ldots, u_n^*\in\mathbb{R}^n$. Define $U^*:=(u_1^*,\ldots,u_k^*)\in\mathbb{R}^{n\times k}$ to be the leading  eigenspace and $\Lambda^*:=\text{diag}(\lambda_1^*,\ldots,\lambda_k^*)\in\mathbb{R}^{k\times k}$ to be the diagonal matrix with the leading $k$ eigenvalues. Then we have $P=U^*\Lambda^* U^{*T}$
and
the matrix $U^*\Lambda^*$ satisfies the following property.







\begin{lemma}\label{lem:population}
The matrix $U^*\Lambda^*\in\mathbb{R}^{n\times k}$ has $k$ unique rows. To be more specific, there exist $\theta^*_1,\ldots,\theta^*_k\in\mathbb{R}^{1\times k}$ such that $(U^*\Lambda^*)_{i\cdot} = \theta^*_{z^*_i}$ for all $i\in[n]$. In addition, 
\begin{align*}
\norm{\theta^*_a - \theta^*_b} = \sqrt{n_a+n_b}(p-q),
\end{align*}
and $\normt{\theta^*_a}^2 = (p^2-q^2)n_a + q^2 n$, for all $a,b\in[k]$ such that $a\neq b$.
\end{lemma}

Lemma \ref{lem:population} reveals that rows of $U^*\Lambda^*$ are equal to each other if their corresponding nodes belong to the same community and the $k$ unique rows $\{\theta^*_a\}$ are separated from each other.
As a result, if the $k$-means clustering (\ref{eqni:1}) was performed on rows of $U^*\Lambda^*$ instead of $U\Lambda$, we would have a perfect partition of the network with clustering centers being $\{\theta^*_a\}$. But this is unrealistic as  $U^*\Lambda^*$ is unobserved and $U\Lambda$ is used in (\ref{eqni:1}). Nevertheless, since $\tilde A$ can be viewed as a perturbation of $P$, $U\Lambda$ can be seen as a perturbation of $U^*\Lambda^*$. Intuitively, if $\tilde A$ is close to $P$, then  $U\Lambda$ is expected to be close to $U^*\Lambda^*$, and the clustering centers $\{\hat \theta_a\}$ should also be close to $\{\theta^*_a\}$ and $\hat z$ is expected to have a small clustering error.

The distance between $\tilde A$ and $P$ is essentially all about the distance between $\tilde A$ and $\mathbb{E} A$, as the two matrices $P$ and $\mathbb{E} A$ only differ in diagonal entries. The concentration of a random graph has been extensively studied in recent literature. We use the following result from
Lemma 12 of  \cite{chin2015stochastic}. Despite that the lemma in \cite{chin2015stochastic} only states  that the upper bound holds with probability $1-o(1)$, its proof gives an explicit expression for  the probability that is at least $1-\ebr{-(3-\log 2)n}-n^{-3}$. By scrutinizing its proof, $1-2n^{-3}$ in Lemma \ref{lem:tilde_A_concentration} can be replaced by $1-n^{-C}$ for any constant $C>0$.
\begin{lemma}[Lemma 12 of \cite{chin2015stochastic}]\label{lem:tilde_A_concentration}
There exists a constant $C_0>0$ such that
\begin{align*}
\norm{\tilde A - \mathbb{E} A} \leq C_0\sqrt{np}
\end{align*}
with probability at least $1-2n^{-3}$.
\end{lemma}


In the remaining part of the paper, we will analyze the performance of the spectral clustering under the with-high-probability event that $\tilde A$ is well-concentrated around $\mathbb{E} A$.
Denote an event
\begin{align}\label{eqn:event_f_def}
\mathcal{F}:=\mathbb{I}\{\normt{\tilde A - \mathbb{E} A}\leq C_0\sqrt{np}\},
\end{align}
where $C_0$ is the constant from the statement of Lemma \ref{lem:tilde_A_concentration}. 
  Then $\pbr{\mathcal{F}}\geq 1-2n^{-3}$. Under $\mathcal{F}$, by classical spectral perturbation theory, we immediately have the following preliminary result. 


\begin{proposition}\label{prop:prelim}
Assume the event $\mathcal{F}$ holds.
There exist constants $C_1,C_2>0$ and some $\phi\in\Phi$ such that if $\frac{n(p-q)^2}{\beta^{-2}k^3 p}\geq C_1$, we have
\begin{align}
&\frac{1}{n}\sum_{i\in[n]}\indic{\hat z_i \neq \phi(z^*_i)} \leq C_2 \frac{k^2\beta^{-1}p}{n(p-q)^2},\label{eqn:prop_prelim_1}\\
\text{and }\quad & \min_{a\in[k]} \norm{\hat \theta_{\phi(a)} U^T - \theta^*_a U^{*T}}\leq C_2 \beta^{-0.5} k\sqrt{p}.\label{eqn:prop_prelim_2}
\end{align}
\end{proposition}

The upper bound in (\ref{eqn:prop_prelim_1}) is essentially equal to the reciprocal of ${n(p-q)^2}/{p}$, a quantity regarded as the signal-to-noise ratio in the community detection literature \cite{zhang2016minimax}. Hence,  (\ref{eqn:prop_prelim_1}) decreases polynomially as ${n(p-q)^2}/{p}$ grows and we refer to it as a polynomial upper bound. Proposition \ref{prop:prelim} also gives an upper bound for the deviation between cluster centers $\{\hat \theta_a\}$ and their population counterpart $\{\theta^*_a\}$.
Results similar to Proposition \ref{prop:prelim} for spectral clustering can be found in \cite{lei2015consistency, loffler2019optimality, zhang2022leaveone}. Proposition \ref{prop:prelim} serves as the starting point for our further analysis toward Theorem \ref{thm:introduction}.


\subsection{Oracle Analysis and Exponents}\label{sec:oracel}
In this section, we provide heuristic arguments to explain why the spectral clustering has exponential error bounds and to derive the exponent $J_{\min}$. For any two positive integers $m_1,m_2$, define
\begin{align}\label{eqn:J_def}
J_{m_1,m_2,p,q}:= \max_{t} \br{(m_1-m_2)t \frac{p+q}{2} - m_1 \log\br{q e^t + 1-q} - m_2\log \br{pe^{-t}+1-p}}.
\end{align}
Then $J_{\min} = \min_{1\leq a\neq b \leq k} J_{n_a,n_b,p,q}$. For simplicity, we consider a two-community SBM.
In addition, instead of analyzing $\hat z$, we study a simplified procedure $\check z\in\{1,2\}^{n}$ defined as follows:
\begin{align*}
\check z_i: = \begin{cases}
1,\text{ if }\norm{A_{i\cdot}U^* - \theta^*_1}\leq \norm{A_{i\cdot} U^*- \theta^*_2},\\
2,\text{ o.w..}
\end{cases}
\end{align*}
We refer to $\check z$ as an oracle estimator since it involves  the unknown $U^*$ and $\theta^*_1,\theta^*_2$ and is not practical.
Nevertheless, $\check z$ is closely related to $\hat z$ as we elaborate below. Note that $\hat z$ performs clustering on rows of $\tilde A U$ as $\tilde A U = U\Lambda$. The $k$-means clustering (\ref{eqni:1}) implies $\hat z_i$ is equal to 1 if $\normt{\tilde A_{i\cdot} U - \hat \theta_1}\leq \normt{\tilde A_{i\cdot} U - \hat \theta_2}$ and is equal to 2 otherwise for each $i\in[n]$. As a comparison, $\check z$ has a similar form but with $\tilde A U$  replaced by $AU^*$ and $\hat \theta_1,\hat \theta_2$ replaced by $\theta^*_1,\theta^*_2$. Since $\theta^*_1,\theta^*_2$ are provided, $\check z$ is more of a classification procedure than a clustering method. Despite all these discrepancies, $\check z$ captures the key ingredient of $\hat z$ and analyzing $\check z$ reveals  fundamentally important properties of the spectral clustering.





The following proposition 
characterizes the statistical accuracy of the oracle estimator with both upper and lower bounds. 
From Proposition \ref{prop:exponent}, the oracle estimator has an exponential classification error with $J_{\min}$ being the exact asymptotic exponent. Though it only considers $k=2$ case, it can be generalized to multi-community cases with $J_{\min}$ appearing in the exponent.
\begin{proposition}\label{prop:exponent}
Consider a two-community SBM with community sizes $n_1,n_2$ both of the order  $n$.
In addition, assume $0<q<p\leq 1/2$, $p,q$ are of the same order, and $\frac{n(p-q)^2}{p}\rightarrow\infty$, we have
\begin{align*}
&\mathbb{E} \br{ \frac{1}{n}\sum_{i\in[n]}\indic{\check z_i \neq z^*_i} }\leq \ebr{- (1-o(1))\br{J_{n_1,n_2,p,q}\wedge J_{n_2,n_1,p,q}}}\\
\text{and }\quad &\mathbb{E} \br{ \frac{1}{n}\sum_{i\in[n]}\indic{\check z_i \neq z^*_i} }\geq \ebr{- (1+o(1))\br{J_{n_1,n_2,p,q}\wedge J_{n_2,n_1,p,q}}}.
\end{align*}
\end{proposition}

To explain why $J_{n_1,n_2,p,q}\wedge J_{n_2,n_1,p,q}$ appears in  Proposition \ref{prop:exponent}, let us consider any $i\in[n]$  such that $z^*_i = 2$. By simple algebra (see proof of Proposition \ref{prop:exponent}), the event $\indic{\check z_i \neq z^*_i}$ can be written equivalently as
\begin{align}
 \indic{{\sum_{j:z^*_j=1} A_{ij} - \sum_{j\neq i:z^*_j=2}A_{ij} }\geq (n_1-n_2)\frac{p+q}{2} }.\label{eqni:2}
\end{align}
Note that for any $j\in[n]$, $A_{ij}$ is a Bernoulli random variable with probability $q$ if $z^*_j=1$ and $p$ if $z^*_j=2$ and $j\neq i$. In addition, $|\{j:z^*_j=1\}|=n_1$ and $|\{j\neq i:z^*_j=2\}|=n_2-1$. Let $\{X_i\}$ and $\{Y_j\}$ be independent Bernoulli random variables with probabilities $q,p$ respectively. 
 Then $\mathbb{E} \indic{\check z_i \neq z^*_i}$ is essentially equal to
\begin{align*}
\pbr{\sum_{l\in[n_1]} X_l - \sum_{j\in[n_2]} Y_j \geq \br{n_1 - n_2}\frac{p+q}{2}},
\end{align*}
where we ignore a minor difference between $n_2$ and $n_2-1$ which is negligible. For this tail probability, a direct application of Chernoff bound leads to an upper bound $\ebr{-J_{n_1,n_2,p,q}}$, and its lower bound $\ebr{-(1+o(1)) J_{n_1,n_2,p,q}}$ can be established using the Cram\'{e}r-Chernoff argument. Similarly, $J_{n_2,n_1,p,q}$ appears in the analysis for any $i\in[n]$ such that $z^*_i=1$. Between these two exponents, the smaller one of $J_{n_1,n_2,p,q}$ and $J_{n_2,n_1,p,q}$ dominates and leads to Proposition \ref{prop:exponent}.







\section{Main Results}




\subsection{Upper Bound}\label{sec:upper}
In this section, we present one main result of the paper: a sharp upper bound for the performance of the spectral clustering. Theorem \ref{thm:upper} is essentially the upper bound part of Theorem \ref{thm:introduction} but with an explicit formula  for the $o(1)$ term in the exponent.
\begin{theorem}\label{thm:upper}
Under the assumption that $\beta^{-1}$, $k=O(1)$, $0<q< p\leq 1/10$,  $\frac{p}{q}=O(1)$, and $\frac{n(p-q)^2}{p}\rightarrow\infty$, there exists some constant $C>0$ such that 
\begin{align*}
\mathbb{E} \ell(\hat z,z^*)\leq \ebr{-\br{1-C\br{\log\br{\frac{n(p-q)^2}{p}}}^{-\frac{1}{2}}} J_{\min}}+2n^{-3}.
\end{align*}
\end{theorem}
The upper bound in Theorem \ref{thm:upper}  involves two terms, the exponential term is essentially from $\mathbb{E}  \ell(\hat z,z^*)\indic{\mathcal{F}}$ where we study $\ell(\hat z,z^*)$ under the event $\mathcal{F}$ and the term $2n^{-3}$ comes from $\pbr{\mathcal{F}^\complement}\leq 2n^{-3}$ (see Lemma \ref{lem:tilde_A_concentration}).
Since $2n^{-3}$ can be improved into $n^{-C}$ for any constant $C>0$ by scrutinizing the proof of Lemma  \ref{lem:tilde_A_concentration}, it should be generally ignored. By Lemma \ref{lem:J}, $J_{\min}$ can be shown to be of the order $n(p-q)^2/p $. Hence, $n(p-q)^2/p\rightarrow\infty$ is the sufficient condition for $\hat z$ to have a vanishing error. When $J_{\min}\geq (1+\epsilon) \log n$ for any constant $\epsilon>0$, Theorem \ref{thm:upper} immediately implies that $\hat z$ achieves the exact recovery with high probability.

The proof of Theorem \ref{thm:upper} is quite involved. Below we give an overview of the proof and highlight challenges we face and new ideas and techniques we use to address them. Since $\tilde A U=U\Lambda$, the $k$-means clustering is performed on rows of $\tilde A U$ and $\hat z_i$ satisfies $\hat z_i = \mathop{\rm argmin}_{a\in[k]}\normt{\tilde A_{i\cdot} U - \hat \theta_a}$ for each $i\in[n]$.
Consider any node $i\in[n]$ and any $a\neq z^*_i$. The node will be incorrectly clustered if $\normt{\tilde A_{i\cdot} U - \hat \theta_a} \leq \normt{\tilde A_{i\cdot} U - \hat \theta_{z^*_i}}$ happens, an event that is about $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})U$. To analyze it, we further decompose it into two terms: one is essentially in a form of $( A_{i\cdot}-\mathbb{E} A_{i\cdot}) U^*$ and the other one is $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})U$.

The analysis for the term $( A_{i\cdot}-\mathbb{E} A_{i\cdot}) U^*$ is relatively straightforward. It eventually leads to the following event
\begin{align}
\mathbb{I}\Bigg\{{\sum_{j:z^*_j=a}  A_{ij} - \sum_{j:z^*_j=z^*_i,j\neq i} A_{ij}}  \geq (n_a -n_{z^*_i})\frac{p+q}{2} -o(1) (n_a + n_{z^*_i})\frac{p-q}{2}\Bigg\}, \label{eqni:3}
\end{align}
which mimics the event (\ref{eqni:2}) of the oracle estimator. 
The existence of $o(1)(n_a + n_{z^*_i})(p-q)/2$ is due to the discrepancy between the spectral clustering and the oracle estimator. The probability of the event (\ref{eqni:3}) leads to an upper bound $\ebr{-(1-o(1))J_{n_a,n_{z^*},p,q}}$. Going through all $i\in[n]$ and $a\in[k]$, the largest one  is $\ebr{-(1-o(1))J_{\min}}$ and appears in the upper bound of Theorem \ref{thm:upper}.

The proof of  Theorem \ref{thm:upper} mostly focuses on analyzing tail probabilities of  $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})U$ which is the most difficult and technical part toward establishing Theorem \ref{thm:upper}. There are two main challenges. The first challenge is that $\tilde A_{i\cdot}$ and $U$ are heavily dependent on each other. This challenge can be addressed by a refined leave-one-out technique to decouple the dependence. The second challenge is more critical and is the reason why we need to develop new techniques. For the purpose of illustration, let us consider a simplified setting: we want to study tail probabilities of $(X-\mathbb{E} X)u$ where $X\in\{0,1\}^{1\times n}$ with $X_i\stackrel{iid}{\sim} \text{Bernoulli}(p)$ and is independent of $u$, a column of $(I-U^*U^{*T})U$. Existing literature \cite{chen2022partial, abbe2020entrywise, chen2019spectral} typically applies classical tail probabilities of Bernoulli random variables (e.g., Bernstein inequality) which involve both $\normt{u}$ and $\normt{u}_\infty$. Between these two norms, the former one is well-controlled but the latter one is essentially $\normt{U}_{2,\infty}$ that has some  inevitable $\log n$ factor. To deal with this $\log n$ factor and to derive meaningful tail probabilities, $p$ has to be much bigger than $(\log n)/n$. However, in this paper, we consider sparse networks with the connectivity probability allowed to be far smaller than $(\log n)/n$ and the aforementioned analysis breaks down.



To analyze $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})U$, we develop a new technical tool that avoids the use of $\norm{u}_{\infty}$ by truncating its coordinates. More accurately, 
to avoid dealing with $\norm{U}_{2,\infty}$, we truncate rows of $U$ if their $\ell_2$ norms are above a certain threshold. 
Let $t>0$ and define a mapping $f_t:\mathbb{R}^{1\times k}\rightarrow \mathbb{R}^{1\times k}$ such that 
\begin{align}\label{eqn:ft_def}
f_t(x) =\begin{cases}
x,\text{ if }\norm{x}\leq t,\\
tx/\norm{x},\text{ if }\norm{x}>t.
\end{cases}
\end{align}
That is, $f_t(x)$ truncates $x$ if $\norm{x}> t$ so that $\norm{f_t(x)}\leq t$ is always satisfied. If $k=1$, $f_t$ is a truncation operator such that $f_t(x)= x\indic{\abs{x}\leq t} + t\indic{x>t} -t\indic{x<-t}$ for any scalar $x$.
Apply $f_t$ to rows of $U$ and we get a matrix $\bar U\in\mathbb{R}^{n\times k}$ defined as
\begin{align}\label{eqn:proof_11}
\bar U_{i\cdot} := f_t(U_{i\cdot}),\forall i\in[n].
\end{align}
The definition of $\bar U$ ensures $\normt{\bar U}_{2,\infty}\leq t$.
Note that $\bar U$ depends on the value of $t$. In the proof of Theorem \ref{thm:upper}, we set  $t=t_0$ where $t_0$ is defined later in (\ref{eqn:t_0}).
With $\bar U$, we decompose $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})U$ into 
\begin{align}
\hspace*{-.2cm}(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})U &= (\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})\bar U + (\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})(U-\bar U).\label{eqni:4}
\end{align}
We now use classical concentration inequalities to analyze $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})\bar U$ (after decoupling the dependence between $\tilde A_{i\cdot}$ and $\bar U$ by the leave-one-out technique) thanks to that the controlled $\normt{\bar U}_{2,\infty}$. It leads to negligible tail probabilities that can be absorbed into $\ebr{-(1-o(1))J_{\min}}$. Aggregating all $i\in[n]$, the impact of $ (\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})(U-\bar U)$, the second term in (\ref{eqni:4}), turns out to be related to a truncated $\ell_2$ norm $\sum_{i\in[n]}\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}} \geq t_0}$. According to Theorem \ref{thm:truncated_l2} below, this truncated $\ell_2$ norm is exponentially small. With the help of Theorem \ref{thm:truncated_l2}, the contribution of $ \{(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})(U-\bar U)\}$ toward $\ell(\hat z,z^*)$ is also negligible and can be absorbed into $\ebr{-(1-o(1))J_{\min}}$ as well. In this way, we derive the exponential term $\ebr{-(1-o(1))J_{\min}}$ in Theorem \ref{thm:upper}.



\subsection{Truncated $\ell_2$ Perturbation Analysis for Eigenspaces}\label{sec:truncated}
\begin{theorem}\label{thm:truncated_l2}
Define
\begin{align}\label{eqn:t_0}
t_0 :=  
\frac{160k^2}{\beta}\sqrt{\frac{k}{\beta n}}.
\end{align}
 Under the assumption that $\beta^{-1},k=O(1),0<q<p\leq 1/2$, and $\frac{n(p-q)^2}{p}\rightarrow\infty$, we have
\begin{align*}
\mathbb{E} \br{\sum_{i\in[n]}\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}} \geq t_0}} \indic{\mathcal{F}}\leq t_0^2n\ebr{  -\frac{3n(p-q)^2}{2p}}.
\end{align*}
\end{theorem}

Theorem \ref{thm:truncated_l2} provides a truncated $\ell_2$ norm for $U$ and is crucial to establishing  Theorem \ref{thm:upper}. The choice of $t_0$ in (\ref{eqn:t_0}) is carefully chosen. Note that $\normt{U^*}_{2,\infty}=  \sqrt{k/(\beta n)}$ according to Lemma \ref{lem:U_star}. When $\beta, k$ are both constants, $t_0$ is equal to $\normt{U^*}_{2,\infty}$ multiplied by a large constant. Since $U$ can be seen as a perturbation of $U^*$,  the truncated $\ell_2$ norm can also be interpreted as a perturbation bound for $U$ and $U^*$. Particularly, it focuses on rows of $U$ with norms that far exceed the baseline $\normt{U^*}_{2,\infty}$.
Theorem \ref{thm:truncated_l2} immediately implies the number of such rows is exponentially small.

\begin{corollary}\label{cor:truncated_hamming}
Under the same assumption as in Theorem \ref{thm:truncated_l2},  we have
\begin{align*}
\mathbb{E}  \br{\sum_{i\in[n]}\indic{\norm{U_{i\cdot}}\geq  t_0}} \indic{\mathcal{F}} \leq n\ebr{  -\frac{3n(p-q)^2}{2p}}.
\end{align*}
\end{corollary}

Theorem \ref{thm:truncated_l2} and Corollary \ref{cor:truncated_hamming} together provide insights on why the eigenvector truncation idea works in analyzing $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})U$ in the proof of Theorem \ref{thm:upper}.  Let us revisit the simplified setting $(X-\mathbb{E} X)u$ discussed above. The magnitude of $\norm{u}_\infty$ does break down classical concentration inequalities. However, these concentration inequalities are usually sharp for the worst case: their upper bounds hold for all weight vectors $u$ with given $\norm{u}$ and $\norm{u}_\infty$. 
On the contrary, the particular $u$ appearing in our analysis is very special: it has a small number of high magnitude coordinates (Corollary \ref{cor:truncated_hamming}) which have an exponentially small aggregated $\ell_2$ norm (Theorem \ref{thm:truncated_l2}), an important property completely ignored if classical concentration inequalities are applied. Instead, in our analysis, we fully exploit this structure by singling out high-magnitude coordinates of $u$ using the eigenvector truncation and eliminate the use of $\norm{u}_\infty$. This is the intuition behind (\ref{eqni:4}) which is crucial to proving Theorem \ref{thm:upper}. The idea of eigenvector truncation, the decomposition (\ref{eqni:4}), and Theorem \ref{thm:truncated_l2} might be useful for spectral perturbation analysis of other random matrix problems and models.

The proof of Theorem \ref{thm:truncated_l2} is also complicated. Since $U=\tilde AU \Lambda^{-1}$, for each $i\in[n]$, the event $\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}} \geq t_0}$ is essentially also about $(\tilde A_{i\cdot}-\mathbb{E} A_{i\cdot}) U$, the same as in the proof of Theorem \ref{thm:upper}.  As a result, 
we face the same challenges that appear in the analysis of Theorem \ref{thm:upper}, and we address them with the same eigenvector truncation arguments and techniques. Similar to how we establish Theorem \ref{thm:upper}, we decompose $(\tilde A_{i\cdot}-\mathbb{E} A_{i\cdot}) U$ into two parts: one eventually leads to a well-controlled tail probability of  $(A_{i\cdot}-\mathbb{E} A_{i\cdot}) U^*$, and the other one involves $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})U$. For the latter one, we use (\ref{eqni:4}) again, handle the quantity $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})\bar U $ with the help of the leave-one-out technique, and aggregate   $(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})\bar U$ across all $i\in[n]$ which leads to $\sum_{i\in[n]}\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}} \geq t_0}$. The remaining part of the proof is different from that of Theorem \ref{thm:upper}.
So far, we obtain an inequality:
 its left-hand side is our target of Theorem \ref{thm:truncated_l2}, the truncated $\ell_2$ norm $\sum_{i\in[n]}\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}}\geq t_0}$; its right-hand side involves various terms with one being the truncated $\ell_2$ norm as well. The one appearing on the right-hand side (from the aggregation of $\{(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})(I-U^*U^{*T})\bar U\}$) can be shown to have a small constant factor and consequently can be absorbed into the one on the left-hand side. The inequality then becomes an upper bound for the truncated $\ell_2$ norm and leads to Theorem \ref{thm:truncated_l2}.


\subsection{Lower Bound}\label{sec:lower}

Following the proof of Theorem \ref{thm:upper} with some modifications, we are able the obtain a matching lower bound presented below in Theorem \ref{thm:lower}. It corresponds to the lower bound part of Theorem \ref{thm:introduction}. 
\begin{theorem}\label{thm:lower}
Under the same assumption as in Theorem \ref{thm:upper}, there exists some constant $C'>0$ such that 
\begin{align*}
\mathbb{E} \ell(\hat z,z^*)\geq \ebr{-\br{1+C' \br{\log\br{\frac{n(p-q)^2}{p}}}^{-\frac{1}{4}}} J_{\min}}- 2n^{-3}.
\end{align*}
\end{theorem}

By Lemma \ref{lem:J}, $J_{\min}$ is of the order $n(p-q)^2/p $. Theorem \ref{thm:lower} indicates $n(p-q)^2/p\rightarrow\infty$ is the necessary condition for $\hat z$ to have a vanishing error. When $J_{\min}\leq  (1+\epsilon) \log n$ for any constant $\epsilon>0$, Theorem \ref{thm:upper} immediately implies that $\hat z$ has a constant probability of not achieving the exact recovery. Theorem \ref{thm:lower} complements Theorem \ref{thm:upper} and together they provide a precise characterization of the performance of the spectral clustering.



\section{Proofs of Theorem \ref{thm:upper} and Theorem \ref{thm:truncated_l2}}

In this section, we give detailed proofs of Theorem \ref{thm:upper} and Theorem \ref{thm:truncated_l2}. 
Before giving the proofs,
 we first introduce some useful concepts and tools and state some important properties.


~\\
\emph{Preliminary results from Proposition \ref{prop:prelim}.}
Recall the definition of the event $\mathcal{F}$ in (\ref{eqn:event_f_def}).  
Under this event, Proposition \ref{prop:prelim} gives a preliminary analysis for the performance of the spectral clustering, showing that there exists some constant $C_2>0$ and some $\phi\in\Phi$ such that (\ref{eqn:prop_prelim_1}) and (\ref{eqn:prop_prelim_2}) hold as   $\frac{n(p-q)^2}{\beta ^{-2}k^3p}\rightarrow\infty$. Without loss of generality, we can assume $\phi=\text{Id}$. Then (\ref{eqn:prop_prelim_2}) leads to
\begin{align}\label{eqnp:upper_2}
 \min_{a\in[k]} \norm{\hat \theta_{a} U^T - \theta^*_a U^{*T}}&\leq C_2 \beta^{-0.5} k\sqrt{p}.
\end{align}
In addition, we have
\begin{align}\label{eqnpn:33}
\mathbb{E} \ell(\hat z,z^*)\indic{\mathcal{F}}=\mathbb{E}\frac{1}{n}\sum_{i\in[n]} \indic{\hat z_i \neq z^*_i}\indic{\mathcal{F}}.
\end{align}

~\\
\emph{Facts about $U$.}
Define 
\begin{align*}
S:=\cbr{i\in[n]: d_i\geq \tau},
\end{align*}
to be the set that includes all indexes of rows and columns zeroed out in the spectral clustering where the value of $\tau$ is given in Algorithm \ref{alg:1}.
Then $\tilde A$ can be written equivalently as
\begin{align*}
\tilde A_{ij}=A_{ij}\indic{i\notin S\text{ and }j\notin S},\forall i,j\in[n].
\end{align*}
Since $U$ is the leading eigenspace of $\tilde A$, we have
\begin{align}\label{eqn:UH_1}
U_{i\cdot}=0,\forall i\in S,
\end{align}
and consequently $\norm{U_{i\cdot}}=0,\forall i\in S$. In addition, we have
\begin{align}\label{eqn:UH_3}
(\tilde A_{i\cdot} - \mathbb{E} A_{i\cdot})U  =  (A_{i\cdot}- \mathbb{E} A_{i\cdot}) U,\forall i\notin S.
\end{align}
This is because due to (\ref{eqn:UH_1}), the left-hand side of (\ref{eqn:UH_3}) is equal to $\sum_{j\notin S} (\tilde A_{ij}-\mathbb{E} A_{ij}) U_{j\cdot}=\sum_{j\notin S}  (A_{ij}-\mathbb{E} A_{ij}) U_{j\cdot}$ which is equal to the right-hand side of (\ref{eqn:UH_3}).

~\\
\emph{Row-wise truncation of $U$.} In the proofs of the main theorems, we need to study quantities that involve rows of $A$ and $U$. To avoid dealing with $\norm{U}_{2,\infty}$, we  truncate rows of $U$ if their $\ell_2$ norms are above a certain threshold. 
Recall the definitions of $f_t$ and $\bar U$ in (\ref{eqn:ft_def}) and (\ref{eqn:proof_11}).
Since $\norm{f_t(x) - x}\leq \norm{x}\indic{\norm{x}\geq t}$, we have
\begin{align}\label{eqnpn:1}
\normf{U - \bar U}^2 &= \sum_{i\in[n]} \norm{U_{i\cdot} - \bar U_{i\cdot}}^2 \leq \sum_{i\in[n]} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t}.
\end{align}
Note that $\bar U$ depends on the value of $t$. In the proofs of the main theorems, we will first consider any $t>0$ and then set $t=t_0$.

~\\
\emph{Leave-one-out counterparts of $U$ and $\bar U$.} One challenge is that rows of $\tilde A$ and $U$ are not independent of each other. To decouple the dependence,
we  introduce leave-one-out counterparts of $U$ and $\bar U$. For any $i\in[n]$,  define $\tilde A^{(i)}\in \{0,1\}^{n\times n}$ to be the leave-one-out counterpart of $\tilde A$ such that
\begin{align}\label{eqn:proof_15}
\tilde A_{jl}^{(i)} := \tilde A_{jl}\indic{j\neq i\text{ and }l\neq i},\forall j,l\in[n].
\end{align}
That is, $\tilde A^{(i)}$ is obtained from $\tilde A$ by zeroing out its $i$th row and column. Let $U^{(i)}\in\mathbb{R}^{n\times k}$ be the leading  eigenspace of $\tilde A^{(i)}$. Under the event $\mathcal{F}$ and $\frac{n(p-q)^2}{\beta ^{-2}k^4p}\rightarrow\infty$,  conditions in Lemma \ref{lem:UU_difference} are satisfied, which leads to
\begin{align}\label{eqn:proof_6}
\fnorm{U -U^{(i)}W^{(i)}}\leq 6k^{1.5}\norm{U_{i\cdot}},
\end{align}
for some orthogonal matrix $W^{(i)}\in\mathcal{O}(k,k)$. Apply $f_t$ to rows of $U^{(i)}$ and we have $\bar U^{(i)}\in\mathbb{R}^{n\times k}$:
\begin{align}\label{eqn:proof_26}
\bar U_{j\cdot}^{(i)} := f_t( U_{j\cdot}^{(i)}),\forall j\in[n].
\end{align}
Since $W^{(i)}$ is an orthogonal matrix, for any $j\in[n]$, we have $\normt{U_{j\cdot}^{(i)}W^{(i)}} = \normt{U_{j\cdot}^{(i)}}$ and consequently,
$\bar U_{j\cdot}^{(i)} W^{(i)} = f_t(U_{j\cdot}^{(i)}W^{(i)})$. By Lemma \ref{lem:ft}, we have $\normt{\bar U_{j\cdot}   - \bar U_{j\cdot}^{(i)}W^{(i)}} = \normt{f_t(U_{j\cdot}) - f_t(U_{j\cdot}^{(i)}W^{(i)})} \leq \normt{U_{j\cdot} - U_{j\cdot}^{(i)}W^{(i)}}$. Then (\ref{eqn:proof_6}) gives
\begin{align}\label{eqnpn:2}
\fnorm{\bar U  -\bar U^{(i)}W^{(i)}} \leq \fnorm{U -U^{(i)}W^{(i)}} \leq 6k^{1.5}\norm{U_{i\cdot}}.
\end{align}
Similar to $\bar U$, $\bar U^{(i)}$ depends on the value of $t$. In the proofs of the main theorems, we will first consider any $t>0$ and then set $t=t_0$.

~\\
\emph{Decomposition of rows of $\tilde A$.} For each $i\in[n]$, $\tilde A_{i\cdot}$ and the leave-one-out eigenspace $\bar U^{(i)}$ still depend on each other, mainly due to the removal of high-degree  nodes and $S$.
To further decouple the dependence,
we need to have a decomposition for $\tilde A_{i\cdot}$.
Define a set 
\begin{align}\label{eqnpn:4}
 S_i:=\cbr{j\in[n]:j\neq i\text{ and }\sum_{l\neq i,j}A_{jl}\geq \tau-1}.
\end{align}
By its definition, $ S_i$ is independent of $A_{i\cdot}$. We also have 
\begin{align}\label{eqnpn:3}
S\cup\{i\} \subset S_i\cup \{i\} .
\end{align}
 This is because  for each $j\notin i$, we have $d_j - (\sum_{l\neq i,j}A_{jl})=A_{ji} =A_{ij}\in\{0,1\}$.  As a result, if $j\in S$, it must be in $S_i$ as well; if $j\in S_i$, it is in $S$ if and only if $A_{ij}=1$.   This leads to the independence between $S\cup\{i\}$ and coordinates in $A_{i\cdot}$ with indexes not in $S_i\cup\{i\}$, conditioned on the set $S_i\cup\{i\}$.  Define $\check A_{i\cdot},\check P_{i\cdot}$ such that
\begin{align}\label{eqnpn:7}
\check A_{ij} := A_{ij}\indic{j\neq i \text{ and }j\in S_i^\complement} \text{ and }\check P_{ij} := P_{ij}\indic{j\neq i \text{ and }j\in S_i^\complement},\forall j\in[n].
\end{align}
Then the aforementioned independence can be stated equivalently as
\begin{align*}
(\check A_{i\cdot} - \check P_{i\cdot}) \perp  S\cup\{i\} | S_i\cup \{i\}.
\end{align*}
By its definition in (\ref{eqn:proof_15}), $\tilde A^{(i)}$ is obtained from $A$ by zeroing out rows and columns in $S\cup\{i\}$. In addition, $\bar U^{(i)}$ is a function of $\tilde A^{(i)}$. Hence, 
\begin{align}\label{eqn:independence}
(\check A_{i\cdot} - \check P_{i\cdot}) \perp \tilde A^{(i)} | S_i\cup\{i\} \text{ and }(\check A_{i\cdot} - \check P_{i\cdot}) \perp \bar U^{(i)} | S_i\cup\{i\},
\end{align}
for all $i\in[n]$.

~\\
\emph{Decouple dependence between rows of $\tilde A$ and $\mathcal{F}$.} For each $i\in[n]$, $\check A_{i\cdot} - \check P_{i\cdot}$ introduced above and the event $\mathcal{F}$ are dependent on each other. To decouple this dependence, we introduce 
\begin{align}\label{eqnpn:5}
\mathcal{F}_i := \indic{\normt{\tilde A^{(i)} -\mathbb{E} A} \leq (C_0+2)\sqrt{np}}.
\end{align}
 Denote $[\mathbb{E} A]^{(i)}\in[0,1]^{n\times n}$ to be a matrix that is equal to $\mathbb{E} A$ but with its $i$th row and column zeroed out. Then $\tilde A^{(i)} - [\mathbb{E} A]^{(i)}$ is equal to $\tilde A -\mathbb{E} A$   but with its $i$th row and column zeroed out. Then we have $\normt{\tilde A^{(i)} - [\mathbb{E} A]^{(i)}}\leq \normt{\tilde A -\mathbb{E} A}$ and consequently $\normt{\tilde A^{(i)} -\mathbb{E} A}\leq \normt{\tilde A -\mathbb{E} A} + \norm{\mathbb{E} A - [\mathbb{E} A]^{(i)}}\leq \normt{\tilde A -\mathbb{E} A} + 2 \norm{\mathbb{E} A_{i\cdot}}\leq \normt{\tilde A -\mathbb{E} A} + 2\sqrt{n}p $.  Hence
\begin{align*}
\indic{\mathcal{F}}\leq \indic{\mathcal{F}_i},\forall i\in[n].
\end{align*}
Since $\mathcal{F}_i$ is a function of $\tilde A^{(i)}$, from (\ref{eqn:independence}) we have
\begin{align}\label{eqnpn:6}
(\check A_{i\cdot} - \check P_{i\cdot}) \perp \mathcal{F}_i | S_i\cup\{i\} ,
\end{align}
for all $i\in[n]$. By Lemma \ref{lem:bar_U_i_U_star_diff}, we have
\begin{align}\label{eqnpn:8}
\norm{\br{I_n - U^*U^{*T}}\bar U^{(i)}}_{2,\infty}\leq t + \sqrt{\frac{k}{\beta n}}
\end{align}
for all $i\in[n]$.
In addition, under the event $\mathcal{F}_i$,  by Lemma \ref{lem:bar_U_i_U_star_diff},  as $\frac{n(p-q)^2}{\beta^{-2}k^2p}\rightarrow\infty$, we have
\begin{align}
\fnorm{\br{I_n - U^*U^{*T}} \bar U^{(i)}} \leq   \frac{2\sqrt{2}(C_0+3)k\sqrt{knp}}{\beta n(p-q)}\label{eqn:proof_22}
\end{align}
for all $i\in[n]$ when $t>\sqrt{k/(\beta n)}$.







\subsection{Proof of Theorem \ref{thm:upper}}\label{sec:proof_upper}
Note that
\begin{align}
\mathbb{E} \ell(\hat z,z^*)&\leq \mathbb{E} \ell(\hat z,z^*)\indic{\mathcal{F}} + \pbr{\mathcal{F}^\complement} \nonumber\\
&\leq  \mathbb{E}  \frac{1}{n}\sum_{i\in[n]}\indic{\hat z_i\neq z^*_i}\indic{\mathcal{F}}  + 2n^{-3} \nonumber\\
&=\mathbb{E}  \frac{1}{n}\sum_{i\notin S}\indic{\hat z_i\neq z^*_i}\indic{\mathcal{F}} +  \frac{1}{n}\mathbb{E} \abs{S} + 2n^{-3} \nonumber\\
&\leq  \frac{1}{n}  \mathbb{E} \sum_{i\notin S}\indic{\hat z_i\neq z^*_i}\indic{\mathcal{F}} +   \ebr{-128np} + 2n^{-3},\label{eqnpn:27}
\end{align}
where the second inequality is by (\ref{eqnpn:33}) and 
the last inequality is by Lemma \ref{lem:S_size}. In the following proof, we are going to establish an upper bound for $ \mathbb{E} \sum_{i \notin S}\indic{\hat z_i\neq z^*_i}\indic{\mathcal{F}}$.

Now consider a fixed $i\notin S$. According to the objective function of the $k$-means, we have the following inequality
\begin{align}
\indic{\hat z_i \neq z_i^*} \indic{\mathcal{F}} &\leq  \indic{\min_{a\neq z^*_i}\norm{U_{i\cdot}\Lambda - \hat \theta_a} \leq \norm{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}}\indic{\mathcal{F}}\nonumber\\
&\leq \sum_{a\neq z^*_i}\indic{\norm{U_{i\cdot}\Lambda - \hat \theta_a}\leq \norm{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}}\indic{\mathcal{F}}. \label{eqnpn:24}
\end{align}

Further consider a fixed $a\in[k]\setminus\{z^*_i\}$.
 We are going to study the event that $U_{i\cdot}\Lambda $ is closer to  an incorrect center $\hat \theta_a$ than the correct center $\hat \theta_{z^*_i}$.  We have
 \begin{align}\label{eqnp:upper_1}
&\indic{\norm{U_{i\cdot}\Lambda - \hat \theta_a}\leq \norm{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}} \indic{\mathcal{F}}  =  \indic{\iprod{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}{ \hat \theta_a - \hat \theta_{z^*_i}} \geq \frac{1}{2} \norm{ \hat \theta_a - \hat \theta_{z^*_i}}^2}\indic{\mathcal{F}}.
 \end{align}
 We are going to have a decomposition of $\langle U_{i\cdot}\Lambda - \hat \theta_{z^*_i}, \hat \theta_a - \hat \theta_{z^*_i}\rangle$.
Due to $U\Lambda = \tilde AU$, we have $U_{i\cdot}\Lambda = \tilde A_{i\cdot} U =  (\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot}) U +  (\mathbb{E} A_{i\cdot}) U$. We have
\begin{align}
\iprod{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}{ \hat \theta_a - \hat \theta_{z^*_i}} &= \iprod{(\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot}) U}{ \hat \theta_a - \hat \theta_{z^*_i}} + \iprod{ (\mathbb{E} A_{i\cdot}) U- \hat \theta_{z^*_i}}{ \hat \theta_a - \hat \theta_{z^*_i}} \nonumber\\
&=(\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot}) U \br{ \hat \theta_a - \hat \theta_{z^*_i}}^T + \iprod{ (\mathbb{E} A_{i\cdot}) U- \hat \theta_{z^*_i}}{ \hat \theta_a - \hat \theta_{z^*_i}} \nonumber\\
&=( A_{i\cdot}- \mathbb{E} A_{i\cdot}) U \br{ \hat \theta_a - \hat \theta_{z^*_i}}^T + \iprod{ (\mathbb{E} A_{i\cdot}) U- \hat \theta_{z^*_i}}{ \hat \theta_a - \hat \theta_{z^*_i}} \nonumber\\
&=( A_{i\cdot}- \mathbb{E} A_{i\cdot}) U^* \br{\theta^*_a - \theta^*_{z^*_i}}^T  + ( A_{i\cdot}- \mathbb{E} A_{i\cdot}) \br{U\hat \theta_a^T - U^* \theta_a^{*T} - U\hat \theta_{z^*_i}^T + U^* \theta^{*T}_{z^*_i}} \nonumber \\
&\quad + \iprod{ (\mathbb{E} A_{i\cdot}) U- \hat \theta_{z^*_i}}{ \hat \theta_a - \hat \theta_{z^*_i}},\label{eqnp:upper_4}
\end{align}
where the third equation is by (\ref{eqn:UH_3}). 
Using Lemma \ref{lem:P_line_diff},  the first term in (\ref{eqnp:upper_4}) can be simplified
\begin{align*}
( A_{i\cdot}- \mathbb{E} A_{i\cdot}) U^* \br{\theta^*_a - \theta^*_{z^*_i}}^T 
&= (p-q)\br{\sum_{j:z^*_j=a} ( A_{ij} -\mathbb{E} A_{ij}) - \sum_{j:z^*_j=z^*_i,j\neq i} ( A_{ij} -\mathbb{E} A_{ij}) }.
\end{align*}
Together with (\ref{eqnp:upper_1}) and (\ref{eqnp:upper_4}), we have
\begin{align}
&\indic{\norm{U_{i\cdot}\Lambda - \hat \theta_a}\leq \norm{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}} \indic{\mathcal{F}} \nonumber \\
&=\mathbb{I}\bigg\{(p-q)\br{\sum_{j:z^*_j=a} ( A_{ij} -\mathbb{E} A_{ij}) - \sum_{j:z^*_j=z^*_i,j\neq i} ( A_{ij} -\mathbb{E} A_{ij}) } \nonumber \\
&\quad + ( A_{i\cdot}- \mathbb{E} A_{i\cdot}) \br{U\hat \theta_a^T - U^* \theta_a^{*T} - U\hat \theta_{z^*_i}^T + U^* \theta^{*T}_{z^*_i}} \nonumber \\
&\quad + \iprod{ (\mathbb{E} A_{i\cdot}) U- \hat \theta_{z^*_i}}{ \hat \theta_a - \hat \theta_{z^*_i}}\geq \frac{1}{2} \norm{ \hat \theta_a - \hat \theta_{z^*_i}}^2\bigg\}\indic{\mathcal{F}}.\label{eqnp:upper_5}
\end{align}

Next, we are going to give an upper bound for (\ref{eqnp:upper_5}). Since $\mathbb{E} A_{i\cdot} $ and $P_{i\cdot}$ only differ in their $i$th coordinates with $A_{ii}=0$ and $P_{ii}=p$, we have 
\begin{align*}
 \norm{ (\mathbb{E} A_{i\cdot}) U- \hat \theta_{z^*_i}} &=   \norm{ P_{i\cdot}U - P_{ii}U_{i\cdot}- \hat \theta_{z^*_i}} \leq \norm{ P_{i\cdot}U - \hat \theta_{z^*_i}}  + p\norm{U_{i\cdot}}  =  \norm{ \theta^*_{z^*_i}U^{*T}U- \hat \theta_{z^*_i}}+ p\norm{U_{i\cdot}} \\
 & =   \norm{ \theta^*_{z^*_i}U^{*T}U- \hat \theta_{z^*_i}U^TU}+ p\norm{U_{i\cdot}}  = \norm{ \theta^*_{z^*_i}U^{*T}- \hat \theta_{z^*_i}U^T}+ p\norm{U_{i\cdot}} \\
 &\leq \max_{b\in[k]}\norm{U\hat \theta_b^T - U^* \theta_b^{*T}} + p\leq C_2 \beta^{-0.5} k\sqrt{p} + p \leq 2C_2 \beta^{-0.5} k\sqrt{p},
\end{align*}
where the second to last inequality is due to (\ref{eqnp:upper_2}).
We also have
\begin{align*}
&\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot}) \br{U\hat \theta_a^T - U^* \theta_a^{*T} - U\hat \theta_{z^*_i}^T + U^* \theta^{*T}_{z^*_i}}}\\
&\leq  \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*U^{*T} \br{U\hat \theta_a^T - U^* \theta_a^{*T} - U\hat \theta_{z^*_i}^T + U^* \theta^{*T}_{z^*_i}}} \\
&\quad + \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) \br{U\hat \theta_a^T - U^* \theta_a^{*T} - U\hat \theta_{z^*_i}^T + U^* \theta^{*T}_{z^*_i}}}\\
&\leq  2 \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*}\max_{b\in[k]}\norm{U\hat \theta_b^T - U^* \theta_b^{*T}} +   \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) \br{U\hat \theta_a^T - U\hat \theta_{z^*_i}^T }} \\
&\leq  2C_2 \beta^{-0.5} k\sqrt{p} \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*} +   \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U} \norm{\hat \theta_a - \hat \theta_{z^*_i}},
\end{align*}
where in the last inequality we use (\ref{eqnp:upper_2}) again.
Then (\ref{eqnp:upper_5}) leads to
\begin{align}
&\indic{\norm{U_{i\cdot}\Lambda - \hat \theta_a}\leq \norm{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}} \indic{\mathcal{F}} \nonumber \\
&\leq \mathbb{I}\Bigg\{(p-q)\br{\sum_{j:z^*_j=a} ( A_{ij} -\mathbb{E} A_{ij}) - \sum_{j:z^*_j=z^*_i,j\neq i} ( A_{ij} -\mathbb{E} A_{ij}) }  + 2C_2 \beta^{-0.5} k\sqrt{p}\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*}  \nonumber\\
&\quad +\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U} \norm{\hat \theta_a - \hat \theta_{z^*_i}} + 2C_2 \beta^{-0.5} k\sqrt{p}\norm{ \hat \theta_a - \hat \theta_{z^*_i}}\nonumber\\
& \quad \geq \frac{1}{2} \norm{ \hat \theta_a - \hat \theta_{z^*_i}}^2\Bigg\}\indic{\mathcal{F}}.\label{eqnp:upper_3}
\end{align}
To further simplify the above display, we need to study $\normt{ \hat \theta_a - \hat \theta_{z^*_i}}$. From Lemma \ref{lem:population}, we have $\normt{\theta^*_a -\theta^*_{z^*_i}} =\sqrt{n_a+n_{z^*_i}}(p-q) \geq \sqrt{2\beta n/k}(p-q)$.
Under the event $\mathcal{F}$, from  (\ref{eqnp:upper_2}), we have
\begin{align}
 \norm{ \hat \theta_a - \hat \theta_{z^*_i}} &= \norm{ \hat \theta_a U^T- \hat \theta_{z^*_i}U^T }  \nonumber\\
 &=  \norm{ \hat \theta_a U^T - \theta^*_aU^{*T} +  \theta^*_aU^{*T} -  \theta^*_{z^*_i}U^{*T} +  \theta^*_{z^*_i}U^{*T}- \hat \theta_{z^*_i}U^T }  \nonumber\\
 &\geq  \norm{ \theta^*_aU^{*T} -  \theta^*_{z^*_i}U^{*T}} - 2\max_{b\in[k]} \norm{\theta^*_bU^{*T}- \hat \theta_{b}U^T }  \nonumber\\
 & = \norm{ \theta^*_a -  \theta^*_{z^*_i}} - 2\max_{b\in[k]} \norm{\theta^*_bU^{*T}- \hat \theta_{b}U^T }  \nonumber\\
 &\geq \sqrt{n_a + n_{z^*_i}}(p-q) -2C_2 \beta^{-0.5} k\sqrt{p}, \label{eqnp:upper_8}

\end{align}
which can be further lower bounded by $\frac{1}{2} \sqrt{\frac{2\beta n}{k}} (p-q)$ as $\frac{n(p-q)^2}{\beta^{-2}k^3p}\rightarrow\infty$. 
Then,
\begin{align*}
&\frac{1}{2} \norm{ \hat \theta_a - \hat \theta_{z^*_i}}^2 - 2C_2 \beta^{-0.5} k\sqrt{p}\norm{ \hat \theta_a - \hat \theta_{z^*_i}} \\
& = \frac{1}{2}\br{1- \frac{2C_2 \beta^{-0.5} k\sqrt{p}}{\norm{ \hat \theta_a - \hat \theta_{z^*_i}}}}\norm{ \hat \theta_a - \hat \theta_{z^*_i}}^2\\
&\geq \frac{1}{2} \br{1- \frac{2C_2 \beta^{-0.5} k\sqrt{p}}{\frac{1}{2} \sqrt{\frac{2\beta n}{k}} (p-q)}}\br{\sqrt{n_a + n_{z^*_i}}(p-q) -2C_2 \beta^{-0.5} k\sqrt{p}}^2\\
&\geq \frac{1}{2}\br{1-C_3\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}} (n_a + n_{z^*_i})(p-q)^2,
\end{align*}
for some constant $C_3>0$, where the last inequality holds as  $\frac{n(p-q)^2}{\beta^{-2}k^3p}\rightarrow\infty$.  Similar to (\ref{eqnp:upper_8}), we also have
\begin{align*}
 \norm{ \hat \theta_a - \hat \theta_{z^*_i}}  &\leq   \norm{ \theta^*_a -  \theta^*_{z^*_i}} + 2\max_{b\in[k]} \norm{\theta^*_bU^{*T}- \hat \theta_{b}U^T } \\
 &\leq \sqrt{n_a + n_{z^*_i}}(p-q) +2C_2 \beta^{-0.5} k\sqrt{p}\\
 &\leq 1.1 \sqrt{n_a + n_{z^*_i}}(p-q) ,
\end{align*}
where the last inequality is under the assumption $\frac{n(p-q)^2}{\beta^{-2}k^3p}\rightarrow\infty$. Then (\ref{eqnp:upper_3}) becomes
\begin{align}
&\indic{\norm{U_{i\cdot}\Lambda - \hat \theta_a}\leq \norm{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}} \indic{\mathcal{F}} \nonumber \\
&\leq \mathbb{I}\Bigg\{(p-q)\br{\sum_{j:z^*_j=a} ( A_{ij} -\mathbb{E} A_{ij}) - \sum_{j:z^*_j=z^*_i,j\neq i} ( A_{ij} -\mathbb{E} A_{ij}) }  + 2C_2 \beta^{-0.5} k\sqrt{p}\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*}  \nonumber\\
&\quad + 1.1 \sqrt{n_a + n_{z^*_i}}(p-q)\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U}\nonumber\\
& \quad \geq \frac{1}{2}\br{1-C_3\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}} (n_a + n_{z^*_i})(p-q)^2\Bigg\}\indic{\mathcal{F}}.\label{eqnp:upper_10}
\end{align}

We are going to split the indication function in (\ref{eqnp:upper_10}) into several ones using the following fact: $\indic{x_1 + x_2\geq x_3+x_4}\leq \indic{x_1\geq x_3} + \indic{x_2\geq x_4}$ for all $x_1,x_2,x_3,x_4\in\mathbb{R}$.
 Consider a positive sequence $\rho=o(1)$  whose value will be determined later. We have
\begin{align}
&\indic{\norm{U_{i\cdot}\Lambda - \hat \theta_a}\leq \norm{U_{i\cdot}\Lambda - \hat \theta_{z^*_i}}} \indic{\mathcal{F}} \nonumber \\
&\leq \mathbb{I}\Bigg\{{\sum_{j:z^*_j=a} ( A_{ij} -\mathbb{E} A_{ij}) - \sum_{j:z^*_j=z^*_i,j\neq i} ( A_{ij} -\mathbb{E} A_{ij}) }  \geq \frac{1}{2}\br{1-4\rho-C_3\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}} (n_a + n_{z^*_i})(p-q)\Bigg\}\indic{\mathcal{F}}    \nonumber\\
&\quad +  \indic{\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*}  \geq \frac{\rho  (n_a + n_{z^*_i})(p-q)^2}{2C_2 \beta^{-0.5} k\sqrt{p}}} \indic{\mathcal{F}}  \nonumber\\
&\quad +  \indic{1.1 \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U} \geq \rho  \sqrt{n_a + n_{z^*_i}}(p-q)  } \indic{\mathcal{F}}  \nonumber\\
&\leq \mathbb{I}\Bigg\{{\sum_{j:z^*_j=a} ( A_{ij} -\mathbb{E} A_{ij}) - \sum_{j:z^*_j=z^*_i,j\neq i} ( A_{ij} -\mathbb{E} A_{ij}) }  \geq \frac{1}{2}\br{1-4\rho-C_3\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}} (n_a + n_{z^*_i})(p-q)\Bigg\}   \nonumber\\
&\quad +  \indic{\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*}  \geq \frac{\rho n (p-q)^2}{C_2 \beta^{-1.5} k^2\sqrt{p}}}  \nonumber\\
&\quad +  \indic{ \norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U} \geq \rho\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}  \nonumber\\
& =: G_{1,i,a} + G_{2,i} + G_{3,i} \label{eqnpn:25}
\end{align}
where $G_{2,i}$ and $G_{3,i}$ do not depend on $a$. 

To further  decompose $G_{3,i}$, first we replace $A_{i\cdot}$ by $\tilde A_{i\cdot}$ as
\begin{align*}
 ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U &= ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U  +  ( A_{i\cdot}- \tilde A_{i\cdot})(I_n-U^*U^{*T}) U  \\
 &= ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U  -  ( A_{i\cdot}- \tilde A_{i\cdot})U^*U^{*T} U,
\end{align*}
where we use (\ref{eqn:UH_3}) in the last inequality. Since $A_{ij} =\tilde A_{ij}$ for all $j\notin S$ and $ \tilde A_{ij}=0$ for all $j\in S$, we have
 $( A_{i\cdot}- \tilde A_{i\cdot})U^*U^{*T} U = \sum_{j\in S} A_{ij} U^*_{j\cdot} U^{*T} U$. As a result, $\normt{( A_{i\cdot}- \tilde A_{i\cdot})U^*U^{*T} U}= \normt{ \sum_{j\in S} A_{ij} U^*_{j\cdot} U^{*T} U} \leq \normt{ \sum_{j\in S} A_{ij} U^*_{j\cdot} } \leq ( \sum_{j\in S} A_{ij})\norm{U^*}_{2,\infty} \leq \sqrt{\frac{k}{\beta n}}  \sum_{j\in S} A_{ij} $ where the last inequality is due to (\ref{lem:U_star}). Hence,
\begin{align*}
\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U} &\leq \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U } + \sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}.
\end{align*}
Recall that $\bar U$ and $\bar U^{(i)}$ are defined in (\ref{eqnpn:1}) and (\ref{eqn:proof_26}) by applying $f_t(\cdot)$ to rows of $U$ and $U^{(i)}$ where $t>0$.
For now, let us consider any $t>0$. We will set $t=t_0$ later in the proof.
Using $U = \br{U- \bar U} + \br{\bar U -\bar U^{(i)}  W^{(i)}} + \bar U^{(i)}  W^{(i)}$,  we have
\begin{align*}
\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U} &\leq  \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) } \\
&\quad +   \norm{ (\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (\bar U -\bar U^{(i)}  W^{(i)})}\\
&\quad +  \norm{ ( \tilde  A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  W^{(i)}}+\sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}.
\end{align*}
The third term in the above display can be further simplified:
\begin{align*}
&\norm{ ( \tilde  A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  W^{(i)}} = \norm{ ( \tilde  A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  } \\
& \leq  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  } +  \norm{\br{ ( \tilde  A_{i\cdot}- \mathbb{E} A_{i\cdot})- ( \check  A_{i\cdot}- \check P_{i\cdot})}(I_n-U^*U^{*T})  \bar U^{(i)}  }\\
& \leq  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  } + \norm{ ( \tilde  A_{i\cdot}- \mathbb{E} A_{i\cdot})- ( \check  A_{i\cdot}- \check P_{i\cdot})}_1 \norm{(I_n-U^*U^{*T})  \bar U^{(i)} }_{2,\infty},
\end{align*}
where the last inequality is by H\"{o}lder's inequality.
Note that $(\tilde A_{ij}-\mathbb{E} A_{ij})-(\check A_{ij}-\check P_{ij}) =( A_{ij}-\mathbb{E} A_{ij})\indic{j\in S^\complement \cap S_i}$ for each $j\in[n]$. Together with (\ref{eqnpn:8}), we have
\begin{align*}
&\norm{ ( \tilde  A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  W^{(i)}} \\
&\quad \leq  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  + \sum_{j\in S^C\cap S_i} \abs{A_{ij}-\mathbb{E} A_{ij}} \br{t+\sqrt{\frac{k}{\beta n}}}\\
&\quad \leq  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  + \sum_{j\in S_i} \abs{A_{ij}-\mathbb{E} A_{ij}} \br{t+\sqrt{\frac{k}{\beta n}}}.
\end{align*}
Hence, the above displays lead to
\begin{align}
&\norm{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) U} \nonumber\\
&\leq  \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }  +   \norm{ (\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (\bar U -\bar U^{(i)}  W^{(i)})}\nonumber\\
&\quad + \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  +\sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}+ \br{t+\sqrt{\frac{k}{\beta n}}}  \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}}. \label{eqnpn:10}
\end{align}
Then
\begin{align}
G_{3,i} &\leq  \indic{ \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U-\bar U)} \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}  \nonumber\\
&\quad +  \indic{ \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (\bar U -\bar U^{(i)}  W^{(i)})} \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}  \nonumber\\
&\quad +  \indic{ \norm{ ( \check A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)} } \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}  \nonumber\\
&\quad +  \indic{\sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}  \geq \frac{\rho}{8}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}  \nonumber\\
&\quad +  \indic{ \br{t+\sqrt{\frac{k}{\beta n}}}  \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}} \geq \frac{\rho}{8}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}  \nonumber\\
&=: H_{1,i} + H_{2,i} + H_{3,i} + H_{4,i} + H_{5,i}. \label{eqnpn:28}
\end{align}

So far, by (\ref{eqnpn:24}), (\ref{eqnpn:25}), and (\ref{eqnpn:28}), we have
\begin{align}
  &\frac{1}{n}  \mathbb{E} \sum_{i\notin S}\indic{\hat z_i\neq z^*_i}\indic{\mathcal{F}} \nonumber\\
   &\leq \frac{1}{n} \mathbb{E}\sum_{i\notin S} \sum_{a\neq z^*_i}   \br{G_{1,i,a} + G_{2,i} + G_{3,i}}\nonumber\\
  &\leq  \frac{1}{n} \sum_{i\in [n]}  \sum_{a\neq z^*_i} \mathbb{E} G_{1,i,a} + \frac{k}{n}\sum_{i\in [n]} \mathbb{E} G_{2,i} +  \frac{k}{n}\sum_{i\in [n]}\mathbb{E} H_{1,i} + \frac{k}{n}\sum_{i\in [n]}\mathbb{E} H_{2,i} \nonumber\\
 & \quad + \frac{k}{n}\sum_{i\in [n]}\br{\mathbb{E} H_{3,i} + \mathbb{E} H_{4,i} + \mathbb{E} H_{5,i}}. \label{eqnpn:26}
  \end{align}
We are going to analyze terms in (\ref{eqnpn:26}) one by one. Consider any $i\in[n]$ and any $a\neq z^*_i$.

For $G_{1,i,a}$, we have
\begin{align*}
\mathbb{E} G_{1,i,a} &\leq \pbr{{\sum_{j:z^*_j=a} ( A_{ij} -\mathbb{E} A_{ij}) - \sum_{j:z^*_j=z^*_i,j\neq i} ( A_{ij} -\mathbb{E} A_{ij}) }  \geq \frac{1}{2}\br{1-4\rho-C_3\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}} (n_a + n_{z^*_i}-1)(p-q)}\\
&\leq \ebr{-J_{n_a,n_{z^*_i}-1,p,q} + \br{2\rho+\frac{C_3}{2}\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}}(n_a+n_{z^*_i}-1) \frac{(p-q)^2}{q}}\\
&\leq  \ebr{-J_{n_a,n_{z^*_i},p,q} + \frac{(p-q)^2}{4q}  + \br{2\rho+\frac{C_3}{2}\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}}(n_a+n_{z^*_i}-1) \frac{(p-q)^2}{q}}\\
&\leq \ebr{ - \br{1- \frac{\br{2\rho+\frac{C_3}{2}\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}}}(n_a+n_{z^*_i}-1)\frac{(p-q)^2}{q}+ \frac{(p-q)^2}{4q} }{n_{z^*_i}  \frac{(p-q)^2}{8p}}}J_{n_a,n_{z^*_i},p,q} }\\
&\leq \ebr{-\br{1- \br{2\rho+\frac{C_3}{2}\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}} + \frac{1}{n}} \frac{16kp}{\beta q} }J_{n_a,n_{z^*_i},p,q} }
\end{align*}
where the first inequity  is due to  Lemma \ref{lem:binomial_diff} and the second and third inequalities are due to Lemma \ref{lem:J}.

For $G_{2,i}$, we have  $\normt{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*} \leq \sum_{j\in[k]}  |( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*_{\cdot j}|$. Note that $U^*_{\cdot j}$ is a unit vector with $\normt{U^*_{\cdot j}}_\infty \leq \sqrt{k/(\beta n)}$ for each $j\in[k]$ according to Lemma \ref{lem:U_star}. By the union bound and Bernstein inequality, we  have
\begin{align*}
\mathbb{E} G_{2,i} &\leq \sum_{j\in[k]} \pbr{\abs{ ( A_{i\cdot}- \mathbb{E} A_{i\cdot})U^*_{\cdot j}}  \geq \frac{\rho n(p-q)^2}{C_2 \beta^{-1.5} k^3\sqrt{p}}}\leq \sum_{j\in[k]} \ebr{- \frac{\frac{1}{2}\br{\frac{\rho n(p-q)^2}{C_2 \beta^{-1.5} k^3\sqrt{p}}}^2}{p\norm{U^*_{j\cdot}}^2 + \frac{1}{3}\norm{U^*_{j\cdot}}_\infty \frac{\rho n(p-q)^2}{C_2 \beta^{-1.5} k^3\sqrt{p}} }}\\
&\leq k\ebr{- \frac{\frac{1}{2}\br{\frac{\rho n(p-q)^2}{C_2 \beta^{-1.5} k^3\sqrt{p}}}^2}{p + \frac{1}{3} \sqrt{\frac{k}{\beta n}} \frac{\rho n(p-q)^2}{C_2 \beta^{-1.5} k^3\sqrt{p}} }}
\leq k \ebr{-\br{\frac{1}{4} \frac{\rho^2 n^2(p-q)^4}{C_2^2 \beta^{-3} k^6 p^2}}\wedge \br{\frac{3}{4}\frac{\sqrt{np}\rho n(p-q)^2}{C_2 \beta^{-2} k^{3.5} p}}}\\
&\leq k\ebr{-\frac{10n(p-q)^2}{p}},
\end{align*}
where the last inequality holds as long as $\frac{\rho^2n(p-q)^2}{\beta^{-3} k^6 p}\rightarrow\infty$ and $\frac{\rho\sqrt{np}}{\beta^{-2}k^{3.5}}\rightarrow\infty$.


In the remaining part of the proof, we set $t=t_0$ whose value is given (\ref{eqn:t_0}). 
We are going to analyze $H_{1,i}, H_{2,i}, H_{3,i}, H_{4,i},$ and $H_{5,i}$ term by term. For $H_{1,i}$, we have
\begin{align}
&\sum_{i\in[n]}H_{1,i} \nonumber\\
&\leq \sum_{i\in[n]} \frac{16k }{\rho^2 \beta n(p-q)^2}  \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U-\bar U)}^2\indic{\mathcal{F}} \nonumber\\
&= \sum_{i\in[n]}\frac{16k }{\rho^2 \beta n(p-q)^2} \text{tr}\br{(U-\bar U)^T (I_n-U^*U^{*T})^T  ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})^T ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U-\bar U)}\indic{\mathcal{F}} \nonumber\\
&=\frac{16k }{\rho^2 \beta n(p-q)^2}\text{tr}\br{(U-\bar U)^T (I_n-U^*U^{*T})^T \br{\sum_{i\in[n]}  ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})^T ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})}(I_n-U^*U^{*T}) (U-\bar U)}\indic{\mathcal{F}}\nonumber\\
&= \frac{16k }{\rho^2 \beta n(p-q)^2}\text{tr}\br{(U-\bar U)^T (I_n-U^*U^{*T})^T (\tilde A -A)^T(\tilde A - A)(I_n-U^*U^{*T}) (U-\bar U)}\indic{\mathcal{F}}\nonumber\\
&= \frac{16k }{\rho^2 \beta n(p-q)^2}\fnorm{(\tilde A - A)(I_n-U^*U^{*T}) (U-\bar U)}^2\indic{\mathcal{F}}\nonumber\\
&\leq  \frac{16k }{\rho^2 \beta n(p-q)^2} \norm{\tilde A - A}^2 \fnorm{(I_n-U^*U^{*T}) (U-\bar U)}^2\indic{\mathcal{F}} \nonumber\\
&\leq  \frac{16C_0^2kp }{\rho^2 \beta (p-q)^2} \fnorm{U-\bar U}^2\indic{\mathcal{F}}, \label{eqnpn:12}
\end{align}
where in the last inequality, we use $\normt{\tilde A - A}\leq C_0\sqrt{np}$ under the event $\mathcal{F}$. By (\ref{eqnpn:1}) and Theorem \ref{thm:truncated_l2}, we have
\begin{align*}
\mathbb{E} \sum_{i\in[n]}H_{1,i}  &\leq  \frac{16C_0^2kp }{\rho^2 \beta (p-q)^2} \mathbb{E}  \sum_{i\in[n]} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}}\indic{\mathcal{F}} \geq t_0} \leq  \frac{16C_0^2kp }{\rho^2 \beta (p-q)^2} t_0^2n\ebr{  -\frac{3n(p-q)^2}{2p}}\\
&\leq nk\ebr{  -\frac{3n(p-q)^2}{2p}},
\end{align*}
where the second and the third inequalities hold under the assumption $\beta^{-1},k=O(1),p\leq 1/2$, and $\frac{\rho^2n(p-q)^2}{p}\rightarrow\infty$.

For $H_{2,i}$, using (\ref{eqnpn:2}), we have
\begin{align}
 \norm{ (\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (\bar U -\bar U^{(i)}  W^{(i)})} &\leq  \norm{  \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot}}\norm{\bar U -\bar U^{(i)}  W^{(i)}} \nonumber\\
 &\leq  \norm{  \tilde A- \mathbb{E} A} 6k^{1.5}\norm{U_{i\cdot}}.  \label{eqnpn:11}

\end{align}
Then
\begin{align*}
H_{2,i} &\leq   \indic{ \norm{  \tilde A- \mathbb{E} A} 6k^{1.5}\norm{U_{i\cdot}}\geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}\\
&\leq  \indic{6C_0k^{1.5}\sqrt{np}\norm{U_{i\cdot}} \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}}\\
&\leq \indic{\norm{U_{i\cdot}} \geq t_0} \indic{\mathcal{F}},
\end{align*}
where the last inequality holds under the assumption that $\beta^{-1},k=O(1),p\leq 1/2$, and $\frac{\rho^2n(p-q)^2}{p}\rightarrow\infty$. Then by Corollary \ref{cor:truncated_hamming}, we have
\begin{align*}
\mathbb{E} \sum_{i\in[n]} H_{2,i}\leq \mathbb{E} \sum_{i\in[n]} \indic{\norm{U_{i\cdot}} \geq t_0} \indic{\mathcal{F}}  \leq n\ebr{  -\frac{3n(p-q)^2}{2p}}.
\end{align*}

For $H_{3,i}$, using  (\ref{eqnpn:5}), we have
\begin{align*}
H_{3,i}&\leq  \indic{ \norm{ ( \check A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)} } \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}_i} 
\end{align*}
and then
\begin{align*}
\mathbb{E} H_{3,i} &\leq \mathbb{E} \br{\mathbb{E}  \br{\indic{ \norm{ ( \check A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)} } \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}_i}  \Bigg| S_i \cup\{i\}}}.
\end{align*}
Note that according to (\ref{eqn:independence}) and (\ref{eqnpn:6}), we have independence between $ \check A_{i\cdot}- \check P_{i\cdot}$ and $ \bar U^{(i)}$, $\mathcal{F}_i$ when conditioned on $S_i\cup\{i\}$. On the other hand, we have (\ref{eqn:proof_22}) holds under the event $\mathcal{F}_i$ and the assumption $\frac{n(p-q)^2}{\beta^{-2}k^2p}\rightarrow\infty$. Together with (\ref{eqnpn:8}), we have 
\begin{align*}
&\mathbb{E} H_{3,i} \\
&\leq \mathbb{E} \br{ \sup_{\Delta\in\mathbb{R}^{n\times k}:\fnorm{\Delta}\leq \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)},\norm{\Delta}_{2,\infty}\leq 2t_0}\mathbb{E}  \br{\indic{ \norm{ ( \check A_{i\cdot}- \check P_{i\cdot})\Delta } \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \indic{\mathcal{F}_i}  \Bigg| S_i \cup\{i\}}}\\
&\leq \mathbb{E} \br{ \sup_{\Delta\in\mathbb{R}^{n\times k}:\fnorm{\Delta}\leq \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)},\norm{\Delta}_{2,\infty}\leq 2t_0}\mathbb{E}  \br{\indic{ \norm{ ( \check A_{i\cdot}- \check P_{i\cdot})\Delta } \geq \frac{\rho}{4}\sqrt{\frac{\beta n}{k}}(p-q)  } \Bigg| S_i \cup\{i\}}}\\
&\leq \mathbb{E} \br{ \sup_{\Delta\in\mathbb{R}^{n\times k}:\fnorm{\Delta}\leq \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)},\norm{\Delta}_{2,\infty}\leq 2t_0}\mathbb{E}  \sum_{l\in[k]}\sum_{\alpha\in\{-1,1\}}  \br{\indic{ \alpha ( \check A_{i\cdot}- \check P_{i\cdot})\Delta_{\cdot l} \geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)  } \Bigg| S_i \cup\{i\}}}\\
&\leq   \sum_{l\in[k]}\sum_{\alpha\in\{-1,1\}} \mathbb{E} \br{ \sup_{\Delta\in\mathbb{R}^{n\times k}:\fnorm{\Delta}\leq \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)},\norm{\Delta}_{2,\infty}\leq 2t_0}\mathbb{E}  \br{\indic{ \alpha ( \check A_{i\cdot}- \check P_{i\cdot})\Delta_{\cdot l} \geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)  } \Bigg| S_i \cup\{i\}}}.
\end{align*}
Define 
\begin{align}\label{eqnpn:16}
\mathcal{W}:=\{w\in\mathbb{R}^n:\norm{w}\leq \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)},\norm{w}_\infty \leq 2t_0\}.
\end{align}
Then,
\begin{align}
\mathbb{E} H_{3,i} &\leq \sum_{l\in[k]}\sum_{\alpha\in\{-1,1\}} \mathbb{E} \br{\sup_{w\in\mathcal{W}} \mathbb{E}  \br{\indic{ \alpha ( \check A_{i\cdot}- \check P_{i\cdot})w\geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)  } \Bigg| S_i \cup\{i\}}}\nonumber\\
& = k \sum_{\alpha\in\{-1,1\}} \mathbb{E} \br{\sup_{w\in\mathcal{W}} \mathbb{E}  \br{\indic{ \alpha ( \check A_{i\cdot}- \check P_{i\cdot})w\geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)  } \Bigg| S_i \cup\{i\}}} \nonumber\\
&=k\sum_{\alpha\in\{-1,1\}} \mathbb{E} \br{\sup_{w\in \mathcal{W}} \pbr{ \alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j\geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   \Bigg| S_i \cup\{i\}}}, \label{eqnpn:15}
\end{align}
where the last equation is due to the definition of $\check A_{i\cdot}$ and $\check P_{i\cdot}$ in (\ref{eqnpn:7}). Now consider any $\alpha\in\{-1,1\}$ and any $w\in\mathcal{W}$. Then by Chernoff bound, the  conditional probability in the above display can be upper bounded by
\begin{align}
&\log \pbr{ \alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j\geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   \Bigg| S_i \cup\{i\}} \nonumber\\
&\leq -s\frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   +  \log \mathbb{E} \ebr{ s\alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j  \Bigg| S_i \cup\{i\} } \nonumber\\
&=  -s\frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   +  \log \prod_{j\in S_i^\complement} \mathbb{E} \ebr{ s\alpha  (A_{ij}-\mathbb{E} A_{ij})w_j } \nonumber\\
&=  -s\frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   +  \sum_{j\in S_i^\complement}\log\mathbb{E} \ebr{ s\alpha  (A_{ij}-\mathbb{E} A_{ij})w_j } \nonumber\\
&\leq    -s\frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   + ps^2\norm{w}^2 \ebr{{s} \norm{w}_\infty} \nonumber\\
&\leq   -s\frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   + ps^2 \br{ \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)}}^2 \ebr{2{s}t_0}, \label{eqnpn:17}
\end{align}
for any $s>0$,
where the second to last inequality is due to Lemma \ref{lem:weighted_bernoulli_simplified} under the assumption $p\leq 1/2$. Choose $s= \frac{8k}{\rho} \sqrt{\frac{k}{\beta n}} \frac{4n(p-q)}{p}$ so that the first term in the above display is equal to $-\frac{4n(p-q)^2}{p}$. Then, we have
\begin{align*}
&\log \pbr{ \alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j\geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   \Bigg| S_i \cup\{i\}} \\
&\leq -\frac{4n(p-q)^2}{p} + p \br{  \frac{8k}{\rho} \sqrt{\frac{k}{\beta n}} \frac{4n(p-q)}{p} \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)}}^2 \ebr{ \frac{8k}{\rho} \sqrt{\frac{k}{\beta n}} \frac{4n(p-q)}{p}2t_0} \\
& = -\frac{4n(p-q)^2}{p} + \frac{128^2(C_0+3)^2 k^6}{\rho^2 \beta^3} \ebr{ \frac{64\times 160 k^4(p-q)}{\rho \beta^2 p}},
\end{align*}
where in the last equation we use the definition of $t_0$ in (\ref{eqn:t_0}). When $\beta^{-1},k=O(1)$ and $\frac{n(p-q)^2}{p}\rightarrow\infty$, a sufficient condition for the second term in the above display to be dominated by the first term is that $\rho$ satisfies 
$\rho^{-1}=o\br{\log\br{\frac{n(p-q)^2}{p}}}$. Then
\begin{align*}
&\log \pbr{ \alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j\geq \frac{\rho}{8k}\sqrt{\frac{\beta n}{k}}(p-q)   \Bigg| S_i \cup\{i\}} \leq -\frac{2n(p-q)^2}{p}.
\end{align*}
Hence,
\begin{align*}
\mathbb{E} H_{3,i}&\leq k\sum_{\alpha\in\{-1,1\}} \mathbb{E} \ebr{ -\frac{2n(p-q)^2}{p}}\leq 2k \ebr{ -\frac{2n(p-q)^2}{p}}.
\end{align*}





For $H_{4,i}$, we first have $\sum_{j\in S}A_{ij}\leq \sum_{j\in S_i} A_{ij}$ due to (\ref{eqnpn:3}) and the fact $A_{ii}=0$. Note that conditioned on $S_i$,  $\sum_{j\in S_i} A_{ij}\sim \text{Binom}(\abs{S_i},p)$. This leads to $\mathbb{E} \sum_{j\in S_i} A_{ij} = p \mathbb{E} \abs{S_i}\leq np\ebr{-128np}$ where the last inequality is by Lemma \ref{lem:S_size}. Then
\begin{align*}
\mathbb{E} H_{4,i} & \leq \mathbb{E} \indic{\sum_{j\in S_i} A_{ij} \geq \frac{\rho \beta n(p-q)}{8k}} \leq 
\frac{8k}{\rho \beta n(p-q)} \mathbb{E}  \sum_{j\in S_i} A_{ij} \leq   \frac{8kp}{\rho \beta (p-q)}\ebr{-128np}\\
&=8\sqrt{\frac{p}{\rho^2 \beta^2 n(p-q)^2}} k\sqrt{np}\ebr{-128np} \leq  k\ebr{-64 np},
\end{align*}
where the last inequality holds under the assumption that $\frac{\rho^2n(p-q)^2}{\beta^{-2}p}\rightarrow\infty$.
Similarly, for $H_{5,i}$, we have
\begin{align*}
\mathbb{E} H_{5,i} & \leq \mathbb{E}  \indic{2t_0  \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}} \geq \frac{\rho}{8}\sqrt{\frac{\beta n}{k}}(p-q)  } \leq  \frac{2t_0}{\frac{\rho}{8}\sqrt{\frac{\beta n}{k}}(p-q)}\mathbb{E}  \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}}\\
&\leq \frac{2t_0}{\frac{\rho}{8}\sqrt{\frac{\beta n}{k}}(p-q)} 2p\mathbb{E} \abs{S_i}\leq \frac{2t_0}{\frac{\rho}{8}\sqrt{\frac{\beta n}{k}}(p-q)} 2np\ebr{-128np}\leq  k\ebr{-64 np},
\end{align*}
where the last inequality holds under the assumption that $\beta^{-1},k=O(1)$,  and $\frac{\rho^2n(p-q)^2}{p}\rightarrow\infty$. 

Now we can combine the above results together to derive the final conclusion. From (\ref{eqnpn:26}), we have
\begin{align*}
 & \frac{1}{n}  \mathbb{E} \sum_{i\notin S}\indic{\hat z_i\neq z^*_i}\indic{\mathcal{F}}  \\
  &\leq  \frac{1}{n} \sum_{i\in S}  \sum_{a\neq z^*_i} \ebr{-\br{1- \br{2\rho+\frac{C_3}{2}\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}} + \frac{1}{n}} \frac{16kp}{\beta q} }J_{n_a,n_{z^*_i},p,q} } \\
  &\quad + \frac{k}{n}\sum_{i\in[n]} k\ebr{-\frac{10n(p-q)^2}{p}} +  \frac{k}{n}n\ebr{  -\frac{3n(p-q)^2}{2p}}\\
  &\quad + \frac{k}{n}\sum_{i\in[n]} \br{2k \ebr{ -\frac{2n(p-q)^2}{p}} + 2k\ebr{-64 np}}\\
  &\leq k\ebr{-\br{1- \br{2\rho+\frac{C_3}{2}\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}} + \frac{1}{n}} \frac{16kp}{\beta q} }\min_{1\leq a\neq b\leq k}J_{n_a,n_{b},p,q} }\\
  &\quad + 4k^2\ebr{  -\frac{3n(p-q)^2}{2p}}.
\end{align*}
So far, we require $\beta^{-1},k=O(1)$, $0<q<p\leq 1/2$,  $\frac{n(p-q)^2}{p}\rightarrow\infty$, and $\rho^{-1}=o\br{\log\br{\frac{n(p-q)^2}{p}}}$.
Then using (\ref{eqnpn:27}), we have
\begin{align}
&\mathbb{E} \ell(\hat z,z^*) \nonumber\\
 &\leq k\ebr{-\br{1- \br{2\rho+\frac{C_3}{2}\sqrt{\frac{\beta^{-2}k^3p}{n(p-q)^2}} + \frac{1}{n}} \frac{16kp}{\beta q} }\min_{1\leq a\neq b\leq k}J_{n_a,n_{b},p,q} } \nonumber\\
  &\quad + 4k^2\ebr{  -\frac{3n(p-q)^2}{2p}} +   \ebr{-128np} + 2n^{-3}. \label{eqnpn:29}
\end{align}
When $p\leq 1/10$ is further assumed, by Lemma \ref{lem:J}, we have $J_{\min}=\min_{1\leq a\neq b\leq k}J_{n_a,n_{b},p,q} \leq \max_{a\in[k]} n_a 4(p-q)^2/(3p)\leq 4n(p-q)^2/(3p)$. As a result, the exponents $128np $ and $\frac{3n(p-q)^2}{2p} $  in (\ref{eqnpn:29}) are bigger than $J_{\min}$. We can let $\rho^{-1}=\br{\log\br{\frac{n(p-q)^2}{p}}}^\frac{1}{2}$.
With $\frac{p}{q}=O(1)$ further assumed, 
there exists some constant $C_4$ such that
\begin{align*}
&\mathbb{E} \ell(\hat z,z^*)\indic{\mathcal{F}} \leq \ebr{-\br{1-C_4 \br{\log\br{\frac{n(p-q)^2}{p}}}^{-\frac{1}{2}}}J_{\min} }+ 2n^{-3}.
\end{align*}


\subsection{Proof of Theorem \ref{thm:truncated_l2}}\label{sec:proof_truncated}


We first have a decomposition of rows of $U$. Consider any $i\in[n]$.
Due to $U\Lambda = \tilde AU$, we have  $U = \tilde AU\Lambda^{-1}$ and its $i$th row satisfies $U_{i\cdot} = \tilde A_{i\cdot}U\Lambda^{-1}$. Then
we have
\begin{align*}
U_{i\cdot} &=  \tilde A_{i\cdot}U\Lambda^{-1} = (\mathbb{E} A_{i\cdot})U\Lambda^{-1}  + (\tilde A_{i\cdot}-\mathbb{E} A_{i\cdot})U\Lambda^{-1}.
\end{align*}
This gives us
\begin{align}\label{eqn:proof_1}
\norm{U_{i\cdot}} \indic{\mathcal{F}} &\leq  \norm{(\mathbb{E} A_{i\cdot})U\Lambda^{-1}} \indic{\mathcal{F}} + \norm{ (\tilde A_{i\cdot}-\mathbb{E} A_{i\cdot})U}\norm{\Lambda^{-1}} \indic{\mathcal{F}}.
\end{align}
For the  term $ \normt{(\mathbb{E} A_{i\cdot})U\Lambda^{-1}} $ in (\ref{eqn:proof_1}), we have
\begin{align*}
(\mathbb{E} A_{i\cdot})U\Lambda^{-1} & = P_{i\cdot}U\Lambda^{-1} - p U_{i\cdot}\Lambda^{-1} \\
&= U^*_{i\cdot} \Lambda^* U^{*T} U\Lambda^{-1} - p U_{i\cdot}\Lambda^{-1}\\
& =U^*_{i\cdot} U^{*T} U + U^*_{i\cdot} \br{\Lambda^* U^{*T} U - U^{*T} U\Lambda}\Lambda^{-1}-  p U_{i\cdot}\Lambda^{-1}.
\end{align*}
Hence,
\begin{align*}
\norm{(\mathbb{E} A_{i\cdot})U\Lambda^{-1}}&\leq  \norm{ U^*_{i\cdot} }  +  \norm{ U^*_{i\cdot} } \norm{\Lambda^* U^{*T} U - U^{*T} U\Lambda} \norm{\Lambda^{-1}}  +  p\norm{ U_{i\cdot}}\norm{\Lambda^{-1}}.
\end{align*}
Note that $\norm{ U_{i\cdot}}\leq \norm{U}=1$. 
From Lemma \ref{lem:U_star}, we have $\norm{ U^*_{i\cdot} }  \leq 1/\sqrt{{\beta n/k}}$. 
Note that  $ \Lambda^* U^{*T} = U^{*T}  P$ and $U \Lambda  = \tilde AU^T$. We have $\Lambda^* U^{*T} U - U^{*T} U \Lambda =U^{*T}  PU - U^{*T}\tilde AU^T=U^{*T}  (P-\tilde A)U$ and thus $\normt{\Lambda^* U^{*T} U - U^{*T} U\Lambda}\leq \normt{\tilde A - P}$. 
By Lemma \ref{lem:Lambda_star}, we have
 $\normt{\Lambda^{-1}}\leq 2k/(\beta n(p-q))$. As a result,
\begin{align*}
\norm{(\mathbb{E} A_{i\cdot})U\Lambda^{-1}}\indic{\mathcal{F}}&\leq \sqrt{\frac{k}{\beta n}} + \sqrt{\frac{k}{\beta n}}C_0\sqrt{np} \frac{2k}{\beta n(p-q)} + p  \frac{2k}{\beta n(p-q)}\leq 2\sqrt{\frac{k}{\beta n}},
\end{align*}
where the last inequality holds under the assumption  that $\frac{n(p-q)^2}{\beta ^{-2}k^2p}\rightarrow\infty$.
Then (\ref{eqn:proof_1}) leads to
\begin{align}\label{eqn:proof_2}
\norm{U_{i\cdot}}\indic{\mathcal{F}} \leq  2\sqrt{\frac{k}{\beta n}} + \frac{4k}{\beta n(p-q)} \norm{ (\tilde A_{i\cdot}-\mathbb{E} A_{i\cdot})U} \indic{\mathcal{F}}.
\end{align}

From (\ref{eqn:UH_1}), we have
\begin{align}\label{eqn:proof_14}
\sum_{i\in[n]}\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}} \geq t} = \sum_{i\notin S}\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}} \geq t}.
\end{align}
Hence, we only need to consider indexes not in $S$.  From now on, consider any $i\notin S$. Then together with (\ref{eqn:UH_3}), (\ref{eqn:proof_2}) leads to
\begin{align}\label{eqnpn:9}
\norm{U_{i\cdot}}\indic{\mathcal{F}} \leq  2\sqrt{\frac{k}{\beta n}} + \frac{4k}{\beta n(p-q)} \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U} \indic{\mathcal{F}}.
\end{align}
We are going to decompose $ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U$ in a similar way as in the proof of Theorem \ref{thm:upper}. 
Recall that $\bar U$ and $\bar U^{(i)}$ are defined in (\ref{eqnpn:1}) and (\ref{eqn:proof_26}) by applying $f_t(\cdot)$ to rows of $U$ and $U^{(i)}$ where $t>0$.
For any $t>0$,
we have
\begin{align*}
& \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U}  \\
 &\leq  \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*U^{*T} U} +  \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})(I-U^*U^{*T})U}\\
 &\leq \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*} +  \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})(I-U^*U^{*T})U}\\
 &\leq \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*} + \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }  +   \norm{ (\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (\bar U -\bar U^{(i)}  W^{(i)})}\\
&\quad + \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  +\sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}+\br{t+\sqrt{\frac{k}{\beta n}}}  \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}},
\end{align*}
where the last inequality is by (\ref{eqnpn:10}).
From (\ref{eqnpn:11}), we have $ \normt{ (\tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (\bar U -\bar U^{(i)}  W^{(i)})}\leq 6C_0k^{1.5}\sqrt{np}\norm{U_{i\cdot}}$ under the event $\mathcal{F}$. Then (\ref{eqnpn:9}) gives
\begin{align*}
\norm{U_{i\cdot}}\indic{\mathcal{F}} &\leq \Bigg( 2\sqrt{\frac{k}{\beta n}} + \frac{4k}{\beta n(p-q)}   \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*}  \\
&\quad +  \frac{4k}{\beta n(p-q)}   \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }  \\
&\quad + \frac{24C_0k^{2.5}\sqrt{np}}{\beta n(p-q)}\norm{U_{i\cdot}}  + \frac{4k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }   + \frac{4k}{\beta n(p-q)} \sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}   \\
&\quad  +\frac{4k}{\beta n(p-q)} \br{t+\sqrt{\frac{k}{\beta n}}}   \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}} \Bigg)\indic{\mathcal{F}} .
\end{align*}
Under the assumption that $\frac{n(p-q^2)}{\beta^{-2}k^5p}\rightarrow\infty$, we have $\br{1- \frac{24C_0k^{2.5}\sqrt{p}}{\beta \sqrt{n}(p-q)}} >\frac{1}{2}$. After arrangement, we have 
\begin{align*}
\norm{U_{i\cdot}}\indic{\mathcal{F}} &\leq  \Bigg(4\sqrt{\frac{k}{\beta n}} + \frac{8k}{\beta n(p-q)}   \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*}  \\
&\quad +  \frac{8k}{\beta n(p-q)}   \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }  \\
&\quad +  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \\
&\quad + \frac{8k}{\beta n(p-q)} \sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}  +\frac{8k}{\beta n(p-q)} \br{t+\sqrt{\frac{k}{\beta n}}}    \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}} \Bigg)\indic{\mathcal{F}} .
\end{align*}
By Lemma \ref{lem:indicator}, we have
\begin{align*}
&\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}}\geq t}\indic{\mathcal{F}} \\
&\leq 25\Bigg( \br{4\sqrt{\frac{k}{\beta n}} }^2\indic{4\sqrt{\frac{k}{\beta n}}  \geq \frac{t}{5}} + \br{\frac{8k}{\beta n(p-q)}  \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*}}^2 \indic{ \frac{8k}{\beta n(p-q)}   \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*} \geq \frac{t}{5}}  \\
&\quad + \br{ \frac{8k \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }}{\beta n(p-q)}   }^2\indic{ \frac{8k \norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }}{\beta n(p-q)}   \geq \frac{t}{5}} \\
&\quad + \br{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  } }^2 \indic{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \geq \frac{t}{5}}\\
&\quad + \br{ \frac{8k}{\beta n(p-q)} \sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij}}^2\indic{ \frac{8k}{\beta n(p-q)} \sqrt{\frac{k}{\beta n}} \sum_{j\in S} A_{ij} \geq \frac{t}{5}} \\
&\quad + \br{\frac{8k}{\beta n(p-q)} \br{t+\sqrt{\frac{k}{\beta n}}}   \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}}}^2\indic{\frac{8k}{\beta n(p-q)} \br{t+\sqrt{\frac{k}{\beta n}}}   \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}}\geq \frac{t}{5}}   \Bigg)\indic{\mathcal{F}}.
\end{align*}
For any $t>20\sqrt{\frac{k}{\beta n}}$, we have $\br{4\sqrt{\frac{k}{\beta n}} }^2\indic{4\sqrt{\frac{k}{\beta n}}  \geq \frac{t}{5}}=0$. With this and the fact that an indication function is always smaller or equal to 1,  the above display can be simplified into
\begin{align*}
&\norm{U_{i\cdot}}^2\indic{\norm{U_{i\cdot}}\geq t}\indic{\mathcal{F}} \\
&\leq 25 \br{\frac{8k}{\beta n(p-q)}  \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*}}^2 \indic{ \frac{8k}{\beta n(p-q)}   \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*} \geq \frac{t}{5}}  \\
&\quad + 25\br{\frac{8k}{\beta n(p-q)}}^2\norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }^2\indic{\mathcal{F}}\\
&\quad + 25\br{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  } }^2 \indic{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \geq \frac{t}{5}}\indic{\mathcal{F}}\\
&\quad + 25\br{\frac{8k}{\beta n(p-q)}}^2 \frac{k}{\beta n } \br{ \sum_{j\in S} A_{ij}}^2 +  25\br{\frac{16k}{\beta n(p-q)}}^2t^2\br{  \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}}}^2\\
&=: H_{0,i}' + H_{1,i}' + H_{3,i}' + H_{4,i}' + H_{5,i}'.
\end{align*}
Note the similarity between $H_{1,i}'$, $H_{3,i}' $, $H_{4,i}' $, $H_{5,i}' $ and $H_{1,i}$, $H_{3,i} $, $H_{4,i} $, $H_{5,i} $ defined in the proof of Theorem \ref{thm:upper}. Summing over all $i\notin S$, we have
\begin{align}
 \sum_{i \notin S} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t} &\leq \sum_{i\in[n]}H_{0,i}' + \sum_{i\in[n]}H_{1,i}' +\sum_{i\in[n]}H_{3,i}' +\sum_{i\in[n]}H_{4,i}' +\sum_{i\in[n]}H_{5,i}'. \label{eqnpn:13}
\end{align}

For $\sum_{i\in[n]}H_{1,i}'$, following the analysis to establish (\ref{eqnpn:12}) for $\sum_{i\in[n]}H_{1,i}$ in the proof of Theorem \ref{thm:upper}, we have
\begin{align*}
\sum_{i\in[n]} H_{1,i}'&\leq 25\br{\frac{8k}{\beta n(p-q)}}^2 \sum_{i\in[n]}\norm{ ( \tilde A_{i\cdot}- \mathbb{E} A_{i\cdot})(I_n-U^*U^{*T}) (U -\bar U) }^2\indic{\mathcal{F}}\\
&\leq  25\br{\frac{8k}{\beta n(p-q)}}^2  \br{C_0\sqrt{np}}^2 \fnorm{U - \bar U}^2 \indic{\mathcal{F}}\\
&\leq \frac{40^2 C_0^2 k^2 p}{\beta^2n(p-q)^2} \fnorm{U - \bar U}^2 \indic{\mathcal{F}}.
\end{align*}
Using (\ref{eqnpn:1}) and (\ref{eqn:UH_1}), we have
\begin{align*}
\sum_{i\in[n]} H_{1,i}'&\leq  \frac{40^2 C_0^2 k^2 p}{\beta^2n(p-q)^2} \sum_{i\in[n]} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t} =   \frac{40^2 C_0^2 k^2 p}{\beta^2n(p-q)^2} \sum_{i \notin S} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t}.
\end{align*}
Under the assumption $\frac{n(p-q)^2}{\beta^{-2} k^2p}\rightarrow\infty$, we have $\br{1-  \frac{40^2 C_0^2 k^2 p}{\beta^2n(p-q)^2}  }\geq \frac{1}{2}$. Rearranging  (\ref{eqnpn:13}), we have
\begin{align*}
 \sum_{i \notin S} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t} &\leq 2\sum_{i\in[n]}H_{0,i}' + 2\sum_{i\in[n]}H_{3,i}' + 2\sum_{i\in[n]}H_{4,i}' +2\sum_{i\in[n]}H_{5,i}'.
\end{align*}
Using (\ref{eqn:proof_14}), we have
\begin{align}\label{eqnpn:14}
\mathbb{E}  \sum_{i \in [n]} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t} &\leq 2 \mathbb{E} \sum_{i\in[n]}H_{0,i}' + 2\mathbb{E} \sum_{i\in[n]}H_{3,i}' + 2\mathbb{E} \sum_{i\in[n]}H_{4,i}' +2\mathbb{E} \sum_{i\in[n]}H_{5,i}'.
\end{align}

In the following, we are going to consider any $i\in[n]$ and
analyze $\mathbb{E} H_{0,i}'$, $\mathbb{E} H_{3,i}' $, $\mathbb{E} H_{4,i}' $, and $\mathbb{E} H_{5,i}' $, term by term. We first analyze the latter two as their analysis is more straightforward. 
Similar to the analysis for $H_{4,i}$ in the proof of Theorem \ref{thm:upper}, we have
\begin{align*}
\mathbb{E} \br{ \sum_{j\in S} A_{ij}}^2 &\leq \mathbb{E} \br{ \sum_{j\in S_i} A_{ij}}^2 = \mathbb{E} \br{ \mathbb{E}  \br{\br{ \sum_{j\in S_i} A_{ij}}^2 \Bigg| S_i}} \leq  \mathbb{E} \br{ (\abs{S_i} p)^2 + \abs{S_i} p } \\
& \leq \br{np + 1} \mathbb{E} \abs{S_i}p\leq 2(np)^2\ebr{-128np},
\end{align*}
where the last inequality is by Lemma \ref{lem:S_size}. Then,
\begin{align*}
\mathbb{E} H_{4,i}'&= 25\br{\frac{8k}{\beta n(p-q)}}^2 \frac{k}{\beta n } \mathbb{E}  \br{ \sum_{j\in S} A_{ij}}^2 \leq  2\frac{40^2 k^3p^2}{\beta^3 n(p-q)^2} \ebr{-128np}.
\end{align*}
Similarly, we have
\begin{align*}
\mathbb{E}  H_{5,i}'&\leq 25\br{\frac{16k}{\beta n(p-q)}}^2t^2   \mathbb{E} \br{  \sum_{j\in  S_i} \abs{A_{ij}-\mathbb{E} A_{ij}}}^2 \\
&\leq 25\br{\frac{16k}{\beta n(p-q)}}^2t^2   \mathbb{E} \br{\br{2p\abs{S_i}}^2 + 2p\abs{S_i}} \\
&\leq  6\frac{160k^2t^2 n p^2}{\beta^2 n(p-q)^2} \ebr{-128np}.
\end{align*}

For $\mathbb{E} H_{0,i}'$, note that for any positive random variable $X$ and any $s\geq 0$, we have $\mathbb{E} X^2\indic{X\geq s} =\sum_{j=1}^{\infty}$ $\mathbb{E} X^2 \indic{(j+1)s >X\geq j s} \leq \sum_{j=1}^{\infty} (j+1)^2s^2\mathbb{E} \indic{X\geq js}$. Then
\begin{align*}
\mathbb{E} H_{0,i}' &\leq   25 \mathbb{E} \br{\frac{8k}{\beta n(p-q)}  \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*}}^2 \indic{ \frac{8k}{\beta n(p-q)}   \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*} \geq \frac{t}{5}} \\
&\leq t^2  \sum_{j=1}^{\infty} (j+1)^2 \pbr{ \frac{8k}{\beta n(p-q)}   \norm{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*} \geq \frac{t}{5}j}\\
&\leq  t^2   \sum_{l\in[k]}  \sum_{j=1}^{\infty} (j+1)^2\pbr{  \abs{ ( A_{i\cdot}-\mathbb{E} A_{i\cdot})U^*_{\cdot l}} \geq  \frac{\beta n(p-q)}{8k}\frac{t}{5k}j} \\
&\leq  t^2   \sum_{l\in[k]}  \sum_{j=1}^{\infty} (j+1)^2 \ebr{- \frac{\frac{1}{2}j^2 \br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}^2}{p +  \frac{1}{3} j \frac{\beta n(p-q)}{8k}\frac{t}{5k} \sqrt{\frac{k}{\beta n}}}},
\end{align*}
where in the last inequality, we use Bernstein inequality and the fact that $\norm{U^*_{\cdot l}}=1$ and $\norm{U^*_{\cdot l}}_\infty \leq \sqrt{\frac{k}{\beta n}}$ from Lemma \ref{lem:U_star}. For any $t>\sqrt{\frac{k}{\beta n}}$, we have $\frac{1}{p} \br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}^2 \rightarrow\infty $ and also $ \br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}  \sqrt{\frac{\beta n}{k}}\rightarrow\infty$, under the assumption that $\frac{n(p-q)^2}{\beta^{-1}k^3p}\rightarrow\infty$. By  Lemma  \ref{lem:summation}, we have
\begin{align*}
\mathbb{E} H_{0,i}' &\leq  t^2   \sum_{l\in[k]}  \sum_{j=1}^{\infty} (j+1)^2 \ebr{-  \frac{\frac{1}{2}j^2}{\br{\frac{1}{p}{\br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}^2}}^{-1} + \frac{1}{3}{j}\br{\br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}  \sqrt{\frac{\beta n}{k}}}^{-1} }} \\
&\leq 8t^2 k   \ebr{-  \frac{\frac{1}{2}}{\br{\frac{1}{p}{\br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}^2}}^{-1} + \frac{1}{3}\br{\br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}  \sqrt{\frac{\beta n}{k}}}^{-1} }} \\
& = 8t^2 k  \ebr{- \frac{\frac{1}{2} \br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}^2}{p +  \frac{1}{3} \frac{\beta n(p-q)}{8k}\frac{t}{5k} \sqrt{\frac{k}{\beta n}}}}.
\end{align*}

The analysis for $\mathbb{E} H_{3,i}'$ is similar to that of $\mathbb{E} H_{0,i}'$ but is more involved. By the same argument as in the analysis of $\mathbb{E} H_{0,i}'$, we have
\begin{align*}
\mathbb{E} H_{3,i}'&\leq 25 \mathbb{E} \br{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  } }^2 \\
&\quad \times \indic{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \geq \frac{t}{5}}\indic{\mathcal{F}} \\
&\leq t^2 \sum_{j=1}^{\infty}(j+1)^2 \mathbb{E}  \indic{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \geq \frac{t}{5} j}\indic{\mathcal{F}}.
\end{align*}
Consider a fixed $j\geq 1$ and any $t>\sqrt{\frac{k}{\beta n}}$. 
Follow the analysis of $\mathbb{E} H_{3,i}$ in the proof of Theorem \ref{thm:upper}, we have
\begin{align*}
&\mathbb{E}  \indic{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \geq \frac{t}{5} j}\indic{\mathcal{F}}\\
& =  \mathbb{E}  \indic{    \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \geq \frac{\beta n(p-q)tj}{40k}}\indic{\mathcal{F}}\\
&\leq k\sum_{\alpha\in\{-1,1\}} \mathbb{E} \br{\sup_{w\in \mathcal{W'}} \pbr{ \alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j\geq \frac{\beta n(p-q)tj}{80k^2}   \Bigg| S_i \cup\{i\}}}
\end{align*}
which is analogous to (\ref{eqnpn:15}). Here $\mathcal{W'}:=\{w\in\mathbb{R}^n:\norm{w}\leq \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)},\norm{w}_\infty \leq 2t\}$, analogous to the definition of  $\mathcal{W}$  in (\ref{eqnpn:16}). Consider any $\alpha \in\{-1,1\}$ and any $w\in\mathcal{W'}$. Analogous to (\ref{eqnpn:17}), we can obtain
\begin{align*}
&\log \pbr{ \alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j\geq \frac{\beta n(p-q)tj}{80k^2}   \Bigg| S_i \cup\{i\}} \\
&\leq -\frac{\beta n(p-q)tj}{80k^2}  s +   ps^2 \br{ \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)}}^2 \ebr{2{s}t},
\end{align*}
for any $s>0$. To derive the above display, we use Lemma \ref{lem:weighted_bernoulli_simplified} and assume $p\leq 1/2$.
Choose $s =\frac{160k^2}{\beta t}\frac{(p-q)}{p}$ such that $\frac{\beta n(p-q)t}{80k^2}  s  =  \frac{2n(p-q)^2}{p}$. Then we have
\begin{align*}
&\log \pbr{ \alpha\sum_{j\in S_i^\complement} (A_{ij}-\mathbb{E} A_{ij})w_j\geq \frac{\beta n(p-q)tj}{80k^2}   \Bigg| S_i \cup\{i\}} \\
&\leq - \frac{2n(p-q)^2}{p}j  + p  \br{\frac{160k^2}{\beta t}\frac{(p-q)}{p}}^2\br{ \frac{4(C_0+3)k\sqrt{knp}}{\beta n(p-q)}}^2 \ebr{\frac{320k^2(p-q)}{p}}\\
& =  - \frac{2n(p-q)^2}{p}j  + \br{\frac{640(C_0+3)k^{3.5}}{\beta^2 \sqrt{n}t}}^2\ebr{\frac{320k^2(p-q)}{p}}.
\end{align*}
Then
\begin{align*}
&\mathbb{E}  \indic{  \frac{8k}{\beta n(p-q)}  \norm{ ( \check  A_{i\cdot}- \check P_{i\cdot})(I_n-U^*U^{*T})  \bar U^{(i)}  }  \geq \frac{t}{5} j}\indic{\mathcal{F}}\\
&\leq 2k \ebr{ - \frac{2n(p-q)^2}{p}j  + \br{\frac{640(C_0+3)k^{3.5}}{\beta^2 \sqrt{n}t}}^2\ebr{\frac{320k^2(p-q)}{p}}},
\end{align*}
and consequently,
\begin{align*}
\mathbb{E} H_{3,i}' &\leq 2k^2t^2  \sum_{j=1}^{\infty} (j+1)^2\ebr{ - \frac{2n(p-q)^2}{p}j  + \br{\frac{640(C_0+3)k^{3.5}}{\beta^2 \sqrt{n}t}}^2\ebr{\frac{320k^2(p-q)}{p}}}\\
&\leq 16k^2t^2 \ebr{ - \frac{2n(p-q)^2}{p} + \br{\frac{640(C_0+3)k^{3.5}}{\beta^2 \sqrt{n}t}}^2\ebr{\frac{320k^2(p-q)}{p}}},
\end{align*}
where the last inequality is due to that $\frac{n(p-q)^2}{p}\rightarrow\infty$.

Combining all the above expressions together, (\ref{eqnpn:14}) leads to
\begin{align*}
\mathbb{E}  \sum_{i \in [n]} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t} &\leq 4\frac{40^2 k^3p^2}{\beta^3 n(p-q)^2} n\ebr{-128np} + 12\frac{160k^2t^2 n p^2}{\beta^2 n(p-q)^2} n\ebr{-128np} \\
&\quad +16t^2 k n  \ebr{- \frac{\frac{1}{2} \br{ \frac{\beta n(p-q)}{8k}\frac{t}{5k}}^2}{p +  \frac{1}{3} \frac{\beta n(p-q)}{8k}\frac{t}{5k} \sqrt{\frac{k}{\beta n}}}} \\
&\quad + 32k^2t^2n \ebr{ - \frac{2n(p-q)^2}{p} + \br{\frac{640(C_0+3)k^{3.5}}{\beta^2 \sqrt{n}t}}^2\ebr{\frac{320k^2(p-q)}{p}}},
\end{align*}
for any $t>20\sqrt{\frac{k}{\beta n}}$. Taking $t=t_0$ where $t_0$ is defined in (\ref{eqn:t_0}), we have
\begin{align*}
\mathbb{E}  \sum_{i \in [n]} \norm{U_{i\cdot}}^2 \indic{\norm{U_{i\cdot}} \geq t_0} &\leq 4\frac{40^2 p}{k^2 n(p-q)^2} nt_0^2(np)\ebr{-128np} + 12\frac{160k^2 p}{\beta^2 n(p-q)^2} nt^2_0 (np)\ebr{-128np} \\
&\quad +16t_0^2 kn\ebr{-\frac{2n(p-q)^2}{p}}\\
&\quad + 32k^2t_0^2n \ebr{ - \frac{2n(p-q)^2}{p} +72k^2(C_0+3)^2 \beta^{-1}\ebr{\frac{320k^2(p-q)}{p}}}\\
&\leq t_0^2 n \ebr{-\frac{3n(p-q)^2}{2p}},
\end{align*}
where the last inequality holds under the assumption that $\beta^{-1},k=O(1)$, $0<q<p\leq 1/2$, and $\frac{n(p-q)^2}{p}\rightarrow\infty$.







