TITLE: "closure preserves homeomorphism"
QUESTION [2 upvotes]: Let me explain the title of the problem and the problem very clearly :
If $X$ and $Y$ are subsets of a topological spaces $A$ and $B$ respectively, which are homeomorphic in the respective subspace topology, does it imply that their closure $\bar{X}$ and $\bar{Y}$ are homeomorphic ?

REPLY [1 votes]: For another mode of failure....
Let $A$ and $B$ the the Euclidean plane. Let $X$ be the unit interval $(0,1)$ on the $x$-axis. Let $Y$ be the unit circle minus the point $(-1,0)$.


TITLE: About virtual displacement
QUESTION [1 upvotes]: Thornton Marion

The varied path represented by $\delta y$ can be thought of physically as a virtual displacement from the actual path consistent with all the forces and constraints (see Figure above).

The varied path $\delta y$, in fact, need not even correspond to a possible path of motion

Doesn't the second quote contradict the first. The first says the virtual path is a possible path, the second says it need not be?

REPLY [0 votes]: First of all, the first statement is wrong, the condition of being consistent with forces should be eliminated, retaining the consistency with constraints. Because if it is not eliminated, then the first statement is basically saying that the varied path is kinematically admissible, or in your phrase, possible path, which is wrong. So yes, the two statements contradict each other, but that is due to an incorrect definition of virtual displacement in the first statement. In the second statement, the reason why virtual displacements are not possible displacements, in general, is that virtual displacement is considered at a certain moment of time for a system with $dt=0$ while kinematically admissble/possible displacements have to take the change of the constraints with time into consideration. For instance, let suppose there is a particle being able to slide along a straight rigid rod rotating about a fixed point at either its ends. In this case, the virtual displacement vectors can only point along the rod, since by definition, we neglect the rotation of the rod, hence no angular velocity imposed on the particle by the rod. For possible displacements, we need to consider the rotation of the rod and add up the imposed angular velocity and any velocity of the particle on the road. Hence the possible displacement vectors will not point along the rod at the very least since rotation of the constraining rod is considered.


TITLE: Finding definite integral of a shifted function
QUESTION [0 upvotes]: Graph f(x)
Let's say I'm given a graph $f(x)$ as shown above where I know that $f(x) = x^2 + 1$ when $-2 < x < 2$,  and $f(x)=5$ everywhere else.
My question is what would I do if I am asked to find $\int_{-2}^{2} f(2x^2)\,dx$?
I apologise if the question seems badly presented (it's because I made it up myself). I was originally presented with this question. I finally managed to get the correct answer for that question (d) but the method I used there confused me when I tried applying it to the question I created above.

REPLY [0 votes]: \begin{align}
\int_{-2}^2 f(2x^2) \, dx &= 2 \int_0^2 f(2x^2) \, dx\\
&= 2 \left(\int_0^{1} f(2x^2) \, dx + \int_1^2 f(2x^2) \, dx \right) \\
&= 2 \left(\int_0^{1} ((2x^2)^2+1) \, dx + \int_1^2 5 \, dx \right) \\
\end{align}
Hopefully you can take it from here.


TITLE: Conditions for formation of an $n$ sided polygon
QUESTION [2 upvotes]: Given $n$ sides of any arbitrary length, give the necessary and sufficient conditions such that they form a $n$ sided polygon.

For a triangle, if the sides are given by $a\le b\le c$ then the necessary and sufficient condition will be $a+b > c$, that is sum of two smaller sides should be greater than the third. This result can be derived by calculating the area of this triangle by Heron's formula.
For a general $n$ sided polygon, let the sides in incresing order be $a_1 \le a_2 \le \cdots \le a_n$, then a necessary condition will be $a_n < a_1+\cdots+a_{n-1}$. Consider the distance between the endpoints of side $a_n$. There are two different paths connecting them, one path has the length $a_n$ and other one has $a_1+\cdots+a_{n-1}$, since the shortest distance between two points is a straight line between them, we get our required result. But will this also be sufficient? Maybe $n=4$ case can help us understand the general case.
$\hskip2in$

REPLY [1 votes]: We are going to prove that provided the lengths of $n$ segments ($n\ge3$) satisfy the condition:
$$
0<a_1\le a_2\le\dots\le a_n;\quad
a_n<\sum_{i=1}^{n-1} a_i
$$
it is possible to construct out of these segments a $n$-sided polygon.
I will assume that for triangles ($n=3$) the statement is established (let me know if you have troubles with this and I will provide a proof).
Assume now that the statement is valid for $n-1$ segments. We will demonstrate that this implies that it is valid for $n$ segments as well (observe that $n$ is at least $4$).
Consider the following cases:

$a_n-a_1>a_{n-1}: \max(a_n-a_1,a_{n-1},\dots,a_2)=a_n-a_1;\quad a_n-a_1< \sum_{i=2}^{n-1}a_i$;
$a_n-a_1\le a_{n-1}: \max(a_n-a_1,a_{n-1},\dots,a_2)=a_{n-1};\quad a_{n-1}< a_n-a_1+\sum_{i=2}^{n-2}a_i$.

Thus if we decrement the length of the longest segment by that of the shortest one and remove the shortest segment from the set, the longest of the remaining segments will be less than the sum of the rest $n-2$ segments.
Let $AB=a_{n}$ be the longest segment. Construct a point $F$ on the segment $AB$ such that $AF=a_1$ (see the figure below). By the induction hypothesis from the remaining $\color{red}{n-1}$ segments we can construct a polygon $BC\dots EF$. Now reflect the segments $AF$ and $FE$ about the line $AE$ to obtain the polygon $ABC\dots EF'$ with $\color{red}n$ sides.

PS. One can note that the above proof fails in the case 2. if (and only if) $n=4$ and the equalities $$a_1=a_2,\quad a_3=a_4$$ hold. In this case the explicit construction of the quadrilateral (parallelogram or kite) helps.


text:
\onecolumn
\section{Proof of Theorem \ref{Thm: major_thm_lr}}
In this section, before presenting the proof of Theorem \ref{Thm: major_thm_lr}, we start with defining some useful notations.
Recall that in \eqref{eqn:linear_regression}, the empirical risk function for linear regression problem is defined as
	\begin{equation}\label{eqn_app: linear_regression}
	\min_{\bfW}: \quad \hat{f}_{\Omega}(\bfW)=\frac{1}{2|\Omega|}\sum_{n\in \Omega}\Big| y_n - g(\bfW;\bfa_n^T\bfX) \Big|^2.
	\end{equation}
Population risk function, which is the expectation of the empirical risk function, is defined as
\begin{equation}\label{eqn_app: linear_regression_exp}
	\min_{\bfW}: \quad {f}_{\Omega}(\bfW)=\mathbb{E}_{\bfX}\frac{1}{2|\Omega|}\sum_{n\in \Omega}\Big| y_n - g(\bfW;\bfa_n^T\bfX) \Big|^2.
	\end{equation}
Then, the road-map of the proof can be summarized in the following three steps.

First, we show the Hessian matrix of the population risk function $f_{\Omega_t}$ is positive-definite at ground-truth parameters $\bfW^*$ and then characterize the local convexity region of $f_{\Omega_t}$ near $\bfW^*$, which is summarized in Lemma \ref{Lemma: local_convexity}.

Second,

$\hat{f}_{\Omega_t}$ is non-smooth because of ReLU activation, but $f_{\Omega_t}$ is smooth.
Hence, we characterize the  gradient descent term as $\nabla \hat{f}_{\Omega_t}(\bfW^{(t)}) \simeq \langle \nabla^2f_{\Omega_t}(\widehat{\bfW}^{(t)}), \bfW^{(t)}-\bfW^* \rangle + \big(\hat{f}_{\Omega_t}({\bfW}^{(t)}) - f_{\Omega_t}({\bfW}^{(t)})\big)$. During this step, we need to apply concentration theorem to bound $\nabla\hat{f}_{\Omega_t}$  to its expectation $\nabla f_{\Omega_t}$ , which is summarized in Lemma \ref{Lemma: sampling_approximation_error}.

Third, we take the momentum term of $\beta(\bfW^{(t)}-\bfW^{(t-1)})$ into consideration and obtain the following recursive rule:
\begin{equation}\label{eqn: iteeee}
\begin{bmatrix}
\W[t+1]-\bfW^*\\
\W[t]-\bfW^*
\end{bmatrix}\\
=\bfL(\beta)
\begin{bmatrix}
\W[t]-\bfW^*\\
\W[t-1]-\bfW^*
\end{bmatrix}.
\end{equation}
Then, we know iterates $\bfW^{(t)}$ converge to the ground-truth with a linear rate which is the largest singlar value of matrix $\bfL(\beta)$. Recall that  AGD reduces to GD with $\beta=0$, so our analysis applies to GD method as well. We are able to show the convergence rate of AGD is faster than GD by proving the largest singluar value of $\bfL(\beta)$ is smaller than $\bfL(0)$ for some $\beta>0$.  Lemma \ref{Thm: initialization} provides the estimation error of $\bfW^{(0)}$ and sample complexity to guarantee $\|\bfL(\beta)\|_2$ is less than $1$ for $t=0$.

\begin{lemma}\label{Lemma: local_convexity}
	Let $f_{\Omega_t}$ be the population risk function in \eqref{eqn_app: linear_regression_exp} for regression problems, then for any $\bfW$ that satisfies
	\begin{equation}\label{eqn: initial_point_lr}
	\|\bfW^* -\bfW\|_2 \le \frac{\varepsilon_0 \sigma_K}{44\kappa^2\gamma K^2},
	\end{equation}
	the second-order derivative of $f_{\Omega_t}$ is bounded as
	\begin{equation}
	\frac{(1-\varepsilon_0)\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}\bfI \preceq \nabla^2f_{\Omega_t}(\bfW)\preceq \frac{4\sigma_1^2(\bfA)}{K} \bfI.
	\end{equation}
\end{lemma}

\begin{lemma}\label{Lemma: sampling_approximation_error}
	Let $\hat{f}_{\Omega_t}$ and $f_{\Omega_t}$ be the  empirical and population risk functions in \eqref{eqn_app: linear_regression} and \eqref{eqn_app: linear_regression_exp} for regression problems, respectively.
	Then, for any fixed point $\bfW$ satisfies \eqref{eqn: initial_point_lr}, we have \footnote{We use $f(d) \gtrsim(\lesssim) g(d)$ to denote there exists some positive constant $C$ such that $f(d)\ge(\le) C\cdot g(d)$ when $d$ is sufficiently large.}
	\begin{equation}\label{eqn: lemma3}
	\left\|\nabla f_{\Omega_t}(\bfW)-\nabla \hat{f}_{\Omega_t}(\bfW)\right\|_2
	\lesssim \sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}\|\bfW-\bfW^* \|_2,
	\end{equation}
	with probability at least $1-K^2\cdot N^{-10}$.
\end{lemma}
\begin{lemma}\label{Thm: initialization}
	Assume the number of samples $|\Omega_t| \gtrsim \kappa^3(1+\delta^2)\sigma_1^4(\bfA)Kd\log^4 N$, the tensor initialization method via Subroutine 1 outputs $\bfW^{(0)}$ such that
	\begin{equation}\label{eqn: ini}
	\|\bfW^{(0)} -\bfW^* \|_2\lesssim \kappa^6 \sigma_1^2(\bfA)\sqrt{\frac{K^4(1+\delta^2)d\log N}{|\Omega_t|}}\|\bfW^*\|_2
	\end{equation}
	with probability at least $1-N^{-10}$.
\end{lemma}
The proofs of Lemmas \ref{Lemma: local_convexity} and \ref{Lemma: sampling_approximation_error} are included in Appendix \ref{sec: Local_convexity} and \ref{sec: Lemma of sample approximation}, respectively,  while the proof of Lemma \ref{Thm: initialization} can be found in Appendix \ref{Sec: Proof of initialization}. With these three preliminary lemmas on hand, the proof of Theorem \ref{Thm: major_thm_lr} is formally summarized in the following contents.
\begin{proof}[Proof of Theorem \ref{Thm: major_thm_lr}]
	The update rule of $\bfW^{(t)}$ is
	\begin{equation}
	\begin{split}
	\bfW^{(t+1)}
	=&\bfW^{(t)}-\eta\nabla \hat{f}_{\Omega_t}(\bfW^{(t)})+\beta(\W[t]-\W[t-1])\\
	=&\bfW^{(t)}-\eta\nabla {f}_{\Omega_t}(\bfW^{(t)})+\beta(\W[t]-\W[t-1])+\eta(\nabla{f}_{\Omega_t}(\bfW^{(t)})-\nabla\hat{f}_{\Omega_t}(\bfW^{(t)})).
	\end{split}
	\end{equation}
	Since $\nabla^2_{\Omega_t}$ is a smooth function, by the intermediate value theorem, we have
	\begin{equation}
	\begin{split}
	\bfW^{(t+1)}
	=\bfW^{(t)}&- \eta\nabla^2{f}_{\Omega_t}(\widehat{\bfW}^{(t)})(\bfW^{(t)}-\bfW^*)\\
	&+\beta(\W[t]-\W[t-1])\\
	&+\eta\big(\nabla{f}_{\Omega_t}(\bfW^{(t)})-\nabla\hat{f}_{\Omega_t}(\bfW^{(t)})\big),
	\end{split}
	\end{equation}
	where $\widehat{\bfW}^{(t)}$ lies in the convex hull of $\bfW^{(t)}$ and $\bfW^*$.

	Next, we have
	\begin{equation}\label{eqn: major_thm_key_eqn}
	\begin{split}
	\begin{bmatrix}
	\W[t+1]-\bfW^*\\
	\W[t]-\bfW^*
	\end{bmatrix}
	=&\begin{bmatrix}
	\bfI-\eta\nabla^2{f}_{\Omega_t}(\widehat{\bfW}^{(t)})+\beta\bfI &\beta\bfI\\
	\bfI& 0\\
	\end{bmatrix}
	\begin{bmatrix}
	\W[t]-\bfW^*\\
	\W[t-1]-\bfW^*
	\end{bmatrix}
	+\eta
	\begin{bmatrix}
	\nabla{f}_{\Omega_t}(\bfW^{(t)})-\nabla\hat{f}_{\Omega_t}(\bfW^{(t)})\\
	0
	\end{bmatrix}.
	\end{split}
	\end{equation}
	Let $\bfL(\beta)=\begin{bmatrix}
	\bfI-\eta\nabla^2{f}_{\Omega_t}(\widehat{\bfW}^{(t)})+\beta\bfI &\beta\bfI\\
	\bfI& 0\\
	\end{bmatrix}$, so we have
	\begin{equation*}
	\begin{split}
	\left\|\begin{bmatrix}
	\W[t+1]-\bfW^*\\
	\W[t]-\bfW^*
	\end{bmatrix}
	\right\|_2
	=&
	\left\|\bfL(\beta)
	\right\|_2
	\left\|
	\begin{bmatrix}
	\W[t]-\bfW^*\\
	\W[t-1]-\bfW^*
	\end{bmatrix}
	\right\|_2
	+\eta
	\left\|
	\begin{bmatrix}
	\nabla{f}_{\Omega_t}(\bfW^{(t)})-\nabla\hat{f}_{\Omega_t}(\bfW^{(t)})\\
	0
	\end{bmatrix}
	\right\|_2.
	\end{split}
	\end{equation*}
	From Lemma \ref{Lemma: sampling_approximation_error}, we know that
	\begin{equation}\label{eqn: convergence2}
	\begin{split}
	\eta\left\|\nabla{f}_{\Omega_t}(\bfW^{(t)})-\nabla\hat{f}_{\Omega_t}(\bfW^{(t)})\right\|_2
	\lesssim \eta \sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}\|\bfW-\bfW^* \|_2.
	\end{split}
	\end{equation}
	Then, we have
	\begin{equation}\label{eqn: convergence}
	\begin{split}
	\|\W[t+1]-\bfW^* \|_2
	\lesssim& \bigg(\| \bfL(\beta) \|_2+\eta\sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}\bigg)\|\W[t]-\bfW^* \|_2\\
	:\eqsim&\nu(\beta)\|\W[t]-\bfW^* \|_2.
	\end{split}
	\end{equation}

	Let $\nabla^2f(\widehat{\bfW}^{(t)})=\bfS\mathbf{\Lambda}\bfS^{T}$ be the eigen-decomposition of $\nabla^2f(\widehat{\bfW}^{(t)})$. Then, we define
	\begin{equation}\label{eqn:Heavy_ball_eigen}
	\begin{split}
	\widetilde{\bfL}(\beta)
	: =&
	\begin{bmatrix}
	\bfS^T&\bf0\\
	\bf0&\bfS^T
	\end{bmatrix}
	\bfL(\beta)
	\begin{bmatrix}
	\bfS&\bf0\\
	\bf0&\bfS
	\end{bmatrix}
	=\begin{bmatrix}
	\bfI-\eta\bf\Lambda+\beta\bfI &\beta\bfI\\
	\bfI& 0\\
	\end{bmatrix}.
	\end{split}
	\end{equation}
	Since
	$\begin{bmatrix}
	\bfS&\bf0\\
	\bf0&\bfS
	\end{bmatrix}\begin{bmatrix}
	\bfS^T&\bf0\\
	\bf0&\bfS^T
	\end{bmatrix}
	=\begin{bmatrix}
	\bfI&\bf0\\
	\bf0&\bfI
	\end{bmatrix}$, we know $\bfL(\beta)$ and $\widetilde{\bfL}(\beta)$
	share the same eigenvalues. 	Let $\lambda_i$ be the $i$-th eigenvalue of $\nabla^2f_{\Omega_t}(\widehat{\bfW}^{(t)})$, then the corresponding $i$-th eigenvalue of $\bfL(\beta)$, denoted by $\delta_i(\beta)$, satisfies
	\begin{equation}\label{eqn:Heavy_ball_quaratic}
	\delta_i^2-(1-\eta \lambda_i+\beta)\delta_i+\beta=0.
	\end{equation}
	Then, we have
	\begin{equation}\label{eqn: Heavy_ball_root}
	\delta_i(\beta)=\frac{(1-\eta \lambda_i+\beta)+\sqrt{(1-\eta \lambda_i+\beta)^2-4\beta}}{2},
	\end{equation}
	and
	\begin{equation}\label{eqn:heavy_ball_beta}
	\begin{split}
	|\delta_i(\beta)|
	=\begin{cases}
	\sqrt{\beta}, \qquad \text{if}\quad  \beta\ge \big(1-\sqrt{\eta\lambda_i}\big)^2,\\
	\frac{1}{2} \left| { (1-\eta \lambda_i+\beta)+\sqrt{(1-\eta \lambda_i+\beta)^2-4\beta}}\right| , \text{otherwise}.
	\end{cases}
	\end{split}
	\end{equation}
	Note that the other root of \eqref{eqn:Heavy_ball_quaratic} is abandoned because the root in \eqref{eqn: Heavy_ball_root} is always no less than the other root with $|1-\eta \lambda_i|<1$.
	By simple calculations, we have
	\begin{equation}\label{eqn: Heavy_ball_result}
	\delta_i(0)>\delta_i(\beta),\quad \text{for}\quad  \forall \beta\in\big(0, (1-{\eta \lambda_i})^2\big).
	\end{equation}
	Moreover, $\delta_i$ achieves the minimum $\delta_{i}^*=|1-\sqrt{\eta\lambda_i}|$ when $\beta= \big(1-\sqrt{\eta\lambda_i}\big)^2$.

	Let us first assume $\bfW^{(t)}$ satisfies \eqref{eqn: initial_point_lr}, then
	from Lemma \ref{Lemma: local_convexity}, we know that
	$$0<\frac{(1-\varepsilon_0)\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}\le\lambda_i\le\frac{4\sigma_1^2(\bfA)}{K}.$$
	Let $\gamma_1=\frac{(1-\varepsilon_0)\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}$ and $\gamma_2=\frac{4\sigma_1^2(\bfA)}{K}$.
	If we choose $\beta$ such that
	\begin{equation}
	\beta^*=\max \big\{(1-\sqrt{\eta\gamma_1})^2, (1-\sqrt{\eta\gamma_2})^2 \big\},
	\end{equation} then we have $\beta\ge (1-\sqrt{\eta \lambda_i})^2$ and $\delta_i=\max\big\{|1-\sqrt{\eta\gamma_1}|, |1-\sqrt{\eta\gamma_2}|  \big\}$ for any $i$.

	Let $\eta= \frac{1}{{2\gamma_2}}$, then $\beta^*$ equals to  $\Big(1-\sqrt{\frac{\gamma_1}{2\gamma_2}}\Big)^2$.
	Then, for any $\varepsilon_0\in (0, {1}/{2})$, we have
	\begin{equation}\label{eqn: con1}
	\begin{split}
	\|\bfL(\beta^*) \|_2
	=\max_i \delta_{i}(\beta^*)

	= 1-\sqrt{\frac{\gamma_1}{2\gamma_2}}
	=1-\sqrt{\frac{1-\varepsilon_0}{88\kappa^2 \gamma K}}
	\le 1-\frac{1-(3/4)\cdot\varepsilon_0}{\sqrt{88\kappa^2 \gamma K}}.
	\end{split}
	\end{equation}
	Then, let
	\begin{equation}\label{eqn: con2}
	\eta \sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}\lesssim \frac{\varepsilon_0}{4\sqrt{88\kappa^2 \gamma K}},
	\end{equation}
	we need $|\Omega_t|\gtrsim\varepsilon_0^{-2}\kappa^2\gamma M(1+\delta^2)\sigma_1^2(\bfA)K^3d \log N$.
	Combining \eqref{eqn: con1} and \eqref{eqn: con2}, we have
	\begin{equation}
	\nu(\beta^*)\le 1-\frac{1-\varepsilon_0}{\sqrt{88\kappa^2 \gamma K}}.
	\end{equation}
	Let $\beta = 0$, we have
	\begin{equation*}
	\begin{gathered}
	\nu(0) \ge \|\bfA(0) \|_2 = 1-\frac{1-\varepsilon_0}{{88\kappa^2 \gamma K}},	\\
	\nu(0) \lesssim \|\bfA(0) \|_2 + \eta \sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}} \le 1-\frac{1-2\varepsilon_0}{{88\kappa^2 \gamma K}}
	\end{gathered}
	\end{equation*}
	if $|\Omega_t|\gtrsim\varepsilon_0^{-2}\kappa^2\gamma M(1+\delta^2)\sigma_1^2(\bfA)K^3d \log N$.

	Hence, with $\eta =\frac{1}{2 \gamma_2}$ and $\beta = \big(1-\frac{\gamma_1}{2\gamma_2} \big)^2$, we have
	\begin{equation}\label{eqn: induction}
	\begin{split}
	\|	\W[t+1]-\bfW^*\|_2
	\le\Big(1-\frac{1-\varepsilon_0}{\sqrt{88\kappa^2 \gamma K}}\Big)\|	\W[t]-\bfW^*\|_2,
	\end{split}
	\end{equation}
	provided $\W[t]$ satisfies \eqref{eqn: initial_point_lr}, and
	\begin{equation}\label{eqn: N_3}
	|\Omega_t|\gtrsim\varepsilon_0^{-2}\kappa^2\gamma (1+\delta^2)\sigma_1^4(\bfA)K^3d \log N.
	\end{equation}
	Then, we can start mathematical induction of \eqref{eqn: induction} over $t$.

	\textbf{Base case}: According to Lemma \ref{Thm: initialization}, we know that \eqref{eqn: initial_point_lr} holds for $\bfW^{(0)}$ if
		\begin{equation}\label{eqn: N_1}
		|\Omega_t|\gtrsim \varepsilon_0^{-2}\kappa^{9}\gamma^2 (1+\delta^2)\sigma_1^4(\bfA) K^8d \log N.
		\end{equation}
		According to  Theorem \ref{Thm: major_thm_lr}, it is clear that the number of samples $|\Omega_t|$  satisfies \eqref{eqn: N_1}, then  \eqref{eqn: initial_point_lr} indeed holds for $t=0$. Since \eqref{eqn: initial_point_lr} holds for $t=0$ and $|\Omega_t|$ in Theorem \ref{Thm: major_thm_lr} satisfies \eqref{eqn: N_3} as well, we have \eqref{eqn: induction} holds for $t=0$.

	\textbf{Induction step}:
		Assuming \eqref{eqn: induction} holds for $\W[t]$, we need to show that \eqref{eqn: induction} holds for $\W[t+1]$. That is to say, we need $|\Omega_t|$ satisfies \eqref{eqn: N_3}, which holds naturally from Theorem \ref{Thm: major_thm_lr}.

		Therefore, when $|\Omega_t|\gtrsim \varepsilon_0^{-2}\kappa^{9}\gamma^2 (1+\delta^2)\sigma_1^4(\bfA)K^8 d \log N$, we know that \eqref{eqn: induction} holds for all $0\le t \le T-1$ with probability at least $1-K^2T\cdot N^{-10}$. By simple calculations, we can obtain
		\begin{equation}\label{eqn: Thm1_final}
		\begin{split}
		\|	\W[T]-\bfW^*\|_2
		\le&\Big(1-\frac{1-\varepsilon_0}{\sqrt{88\kappa^2 \gamma K}}\Big)^T\|	\W[0]-\bfW^*\|_2
		\end{split}
		\end{equation}
\end{proof}

\subsection{Proof of Lemma \ref{Lemma: local_convexity}}
\label{sec: Local_convexity}
In this section, we provide the proof of Lemma \ref{Lemma: local_convexity} which shows the local convexity of $f_{\Omega_t}$ in a small neighborhood of $\bfW^*$. The roadmap is to first bound the smallest eigenvalue of $\nabla^2 f_{\Omega_t}$ in the ground truth as shown in Lemma \ref{Lemma: lemma 5}, then show that the difference of $\nabla^2 f_{\Omega_t}$ between any fixed point $\bfW$ in this region and the ground  truth $\bfW^*$ is bounded in terms of $\|\bfW -\bfW^* \|_2$ by Lemma \ref{Lemma: lemma 6}.
\begin{lemma}\label{Lemma: lemma 5}
	The second-order derivative of $f_{\Omega_t}$ at the ground truth $\bfW^*$ satisfies
	\begin{equation}
	\frac{\sigma_1^2(\bfA)}{11 \kappa^2 \gamma K^2}   \preceq    \nabla^2 f_{\Omega_t}(\bfW^*)    \preceq \frac{3\sigma_1^2(\bfA)}{K}.
	\end{equation}
\end{lemma}

\begin{lemma}\label{Lemma: lemma 6}
	Suppose $\bfW$ satisfies \eqref{eqn: initial_point_lr}, we have
	\begin{equation}
	\left\|\nabla^2f_{\Omega_t}(\bfW) - \nabla^2f_{\Omega_t}(\bfW^*)  \right\|_2 \le  4\sigma_1^2(\bfA)\frac{\|\bfW^*-\bfW\|_2}{\sigma_K}.
	\end{equation}
\end{lemma}
The proofs of Lemmas \ref{Lemma: lemma 5} and \ref{Lemma: lemma 6} can be found in Sec. \ref{sec: sub_lr}. With these two preliminary lemmas on hand, the proof of Lemma \ref{Lemma: local_convexity} is formally summarized in the following contents.
\begin{proof}[Proof of Lemma \ref{Lemma: local_convexity}]
	By the triangle inequality, we have
	\begin{equation*}
	\Big|
	\left\| \nabla^2 f_{\Omega_t}(\bfW)\right\|_2 -\left\| \nabla^2f_{\Omega_t}(\bfW^*)\right\|_2
	\Big| \le \|\nabla^2f_{\Omega_t}(\bfW^*)-\nabla^2f_{\Omega_t}(\bfW)\|_2,
	\end{equation*}
	and
	\begin{equation*}
	\begin{split}
	&\left\| \nabla^2f_{\Omega_t}(\bfW)\right\|_2 \le \left\| \nabla^2f_{\Omega_t}(\bfW^*)\right\|_2 +\|\nabla^2f_{\Omega_t}(\bfW^*)-\nabla^2f_{\Omega_t}(\bfW)\|_2,\\
	&\left\| \nabla^2f_{\Omega_t}(\bfW)\right\|_2 \ge \left\| \nabla^2f_{\Omega_t}(\bfW^*)\right\|_2 -\|\nabla^2f_{\Omega_t}(\bfW^*)-\nabla^2f_{\Omega_t}(\bfW)\|_2.
	\end{split}
	\end{equation*}
	The error bound of $\|\nabla^2f_{\Omega_t}(\bfW^*)-\nabla^2f_{\Omega_t}(\bfW)\|_2$ can be derived from Lemma \ref{Lemma: lemma 6}, and the error bound of $\nabla^2f_{\Omega_t}(\bfW^*)$ is provided in Lemma \ref{Lemma: lemma 5}.

	Therefore, for any $\bfW$ satisfies \eqref{eqn: initial_point_lr}, we have
	\begin{equation}\label{temp_L12}
	\frac{(1-\varepsilon_0)\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}\le\left\| \nabla^2f_{\Omega_t}(\bfW)\right\|_2 \le \frac{4\sigma_1^2(\bfA)}{K}.
	\end{equation}

\end{proof}

\subsection{Proof of Lemma \ref{Lemma: sampling_approximation_error}}\label{sec: Lemma of sample approximation}
The proof of Lemma \ref{Lemma: sampling_approximation_error} is mainly to bound the concentration error of random variables $\bfz_n(j,k)$ as shown in \eqref{eqn: sub-var}. We first show that $\bfz_n(j,k)$ is a  sub-exponential random variable, and the definitions of sub-Gaussian and sub-exponential random variables are provided in Definitions \ref{Def: sub-gaussian} and \ref{Def: sub-exponential}. Though Hoeffding's inequality provides the concentration error for sum of independent random variables,  random variables $\bfz_n(j,k)$ with different $j,k$ are not independent. Hence, we introduce Lemma \ref{Lemma: partial_independent_var} to provide the upper bound for the moment generation function of the sum of partly dependent random variables and then apply standard Chernoff inequality. Lemmas \ref{Lemma: covering_set} and \ref{Lemma: spectral_norm on net} are standard tools in analyzing spectral norms of high-demensional random matrices.
\begin{definition}[Definition 5.7, \cite{V2010}]\label{Def: sub-gaussian}
	A random variable $X$ is called a sub-Gaussian random variable if it satisfies
	\begin{equation}
	(\mathbb{E}|X|^{p})^{1/p}\le c_1 \sqrt{p}
	\end{equation} for all $p\ge 1$ and some constant $c_1>0$. In addition, we have
	\begin{equation}
	\mathbb{E}e^{s(X-\mathbb{E}X)}\le e^{c_2\|X \|_{\psi_2}^2 s^2}
	\end{equation}
	for all $s\in \mathbb{R}$ and some constant $c_2>0$, where $\|X \|_{\psi_2}$ is the sub-Gaussian norm of $X$ defined as $\|X \|_{\psi_2}=\sup_{p\ge 1}p^{-1/2}(\mathbb{E}|X|^{p})^{1/p}$.

	Moreover, a random vector $\bfX\in \mathbb{R}^d$ belongs to the sub-Gaussian distribution if one-dimensional marginal $\boldsymbol{\alpha}^T\bfX$ is sub-Gaussian for any $\boldsymbol{\alpha}\in \mathbb{R}^d$, and the sub-Gaussian norm of $\bfX$ is defined as $\|\bfX \|_{\psi_2}= \sup_{\|\boldsymbol{\alpha} \|_2=1}\|\boldsymbol{\alpha}^T\bfX \|_{\psi_2}$.
\end{definition}

\begin{definition}[Definition 5.13, \cite{V2010}]\label{Def: sub-exponential}

	A random variable $X$ is called a sub-exponential random variable if it satisfies
	\begin{equation}
	(\mathbb{E}|X|^{p})^{1/p}\le c_3 {p}
	\end{equation} for all $p\ge 1$ and some constant $c_3>0$. In addition, we have
	\begin{equation}
	\mathbb{E}e^{s(X-\mathbb{E}X)}\le e^{c_4\|X \|_{\psi_1}^2 s^2}
	\end{equation}
	for $s\le 1/\|X \|_{\psi_1}$ and some constant $c_4>0$, where $\|X \|_{\psi_1}$ is the sub-exponential norm of $X$ defined as $\|X \|_{\psi_1}=\sup_{p\ge 1}p^{-1}(\mathbb{E}|X|^{p})^{1/p}$.

\end{definition}
\begin{lemma}\label{Lemma: partial_independent_var}
	Given a sampling set $\mathcal{X}=\{ x_n \}_{n=1}^N$ that contains $N$ partly dependent random variables, for each $n\in [N]$, suppose $x_n$ is dependent with at most $d_{\mathcal{X}}$ random variables  in $\mathcal{X}$ (including $x_n$ itself), and the moment generate function of $x_n$ satisfies $\mathbb{E}_{x_n} e^{sx_n}\le e^{Cs^2} $ for some constant $C$ that may depend on $x_n$. Then, the moment generation function of $\sum_{n=1}^N x_n$ is bounded as
	\begin{equation}
	\mathbb{E}_{\mathcal{X}} e^{s\sum_{n=1}^N x_n} \le e^{Cd_{\mathcal{X}}Ns^2}.
	\end{equation}
\end{lemma}

\begin{lemma}[Lemma 5.2, \cite{V2010}]\label{Lemma: covering_set}
	Let $\mathcal{B}(0, 1)\in\{ \boldsymbol{\alpha} \big| \|\boldsymbol{\alpha} \|_2=1, \boldsymbol{\alpha}\in \mathbb{R}^d  \}$ denote a unit ball in $\mathbb{R}^{d}$. Then, a subset $\mathcal{S}_\xi$ is called a $\xi$-net of $\mathcal{B}(0, 1)$ if every point $\bfz\in \mathcal{B}(0, 1)$ can be approximated to within $\xi$ by some point $\boldsymbol{\alpha}\in \mathcal{B}(0, 1)$, i.e. $\|\bfz -\boldsymbol{\alpha} \|_2\le \xi$. Then the minimal cardinality of a   $\xi$-net $\mathcal{S}_\xi$ satisfies
	\begin{equation}
	|\mathcal{S}_{\xi}|\le (1+2/\xi)^d.
	\end{equation}
\end{lemma}
\begin{lemma}[Lemma 5.3, \cite{V2010}]\label{Lemma: spectral_norm on net}
	Let $\bfA$ be an $N\times d$ matrix, and let $\mathcal{S}_{\xi}$ be a $\xi$-net of $\mathcal{B}(0, 1)$ in $\mathbb{R}^d$ for some $\xi\in (0, 1)$. Then
	\begin{equation}
	\|\bfA\|_2 \le (1-\xi)^{-1}\max_{\boldsymbol{\alpha}\in \mathcal{S}_{\xi}} |\boldsymbol{\alpha}^T\bfA\boldsymbol{\alpha}|.
	\end{equation}
\end{lemma}

The proof of Lemma \ref{Lemma: partial_independent_var} can be found in Appendex \ref{sec: sub_lr}. With these preliminary Lemmas and definition on hand, the proof of Lemma \ref{Lemma: sampling_approximation_error} is formally summarized in the following contents.
\begin{proof}[Proof of Lemma \ref{Lemma: sampling_approximation_error} ]
	We have
\begin{equation}
\begin{split}
\hat{f}_{\Omega_t}(\bfW)
=& \frac{1}{2{|\Omega_t|}} \sum_{n \in \Omega_t}\Big| y_n - g(\bfW;\bfa_n^T\bfX) \Big|^2\\
=& \frac{1}{2{|\Omega_t|}} \sum_{n \in \Omega_t}\Big| y_n - \sum_{j=1}^K \phi(\bfa_n^T \bfX\bfw_j) \Big|^2,
\end{split}
\end{equation}
and
\begin{equation}
f_{\Omega_t}(\bfW)=\mathbb{E}_{\bfX}\hat{f}_{\Omega_t}(\bfW) = \frac{1}{2{|\Omega_t|}} \sum_{n \in \Omega_t}\mathbb{E}_{\bfx}\Big| y_n - \sum_{j=1}^K \phi(\bfa_n^T \bfX\bfw_j) \Big|^2.
\end{equation}
The gradients of $\hat{f}_{\Omega_t}$ are
\begin{equation}
\begin{split}
\frac{\partial\hat{f}_{\Omega_t}}{\partial \bfw_k}(\bfW)
=&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \Big(y_n - \sum_{j=1}^{K}\phi(\bfa_n^T\bfX\bfw_j)  \Big)\bfX^T\bfa_n\phi^{\prime}(\bfa_n^T\bfX\bfw_k)\\
=&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \Big( \sum_{j=1}^{K}\phi(\bfa_n^T\bfX\bfw_j^*) - \sum_{j=1}^{K}\phi(\bfa_n^T\bfX\bfw_j)  \Big)\bfX^T\bfa_n\phi^{\prime}(\bfa_n^T\bfX\bfw_k)\\
=&\sum_{j=1}^{K}\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t}
\big( \phi(\bfa_n^T\bfX\bfw_j^*) - \phi(\bfa_n^T\bfX\bfw_j)  \big)\bfX^T\bfa_n\phi^{\prime}(\bfa_n^T\bfX\bfw_k).\\

\end{split}
\end{equation}
Let us define
\begin{equation}\label{eqn: sub-var}
\bfz_{n}(k, j) = \bfX^T\bfa_n\phi^{\prime}(\bfa_n^T\bfX\bfw_k)\big( \phi(\bfa_n^T\bfX\bfw_j^*) - \phi(\bfa_n^T\bfX\bfw_j)  \big),
\end{equation}
 then for any normalized $\boldsymbol{\alpha}\in \mathbb{R}^d$, we have
\begin{equation}
\begin{split}
&p^{-1}\Big(\mathbb{E}_{\bfX} \big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\phi^{\prime}(\bfa_n^T\bfX\bfw_k)\big( \phi(\bfa_n^T\bfX\bfw_j^*) - \phi(\bfa_n^T\bfX\bfw_j)  \big)\big|^p  \Big)^{1/p}\\
\le&p^{-1}\Big(\mathbb{E}_{\bfX} \big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^{2p}\cdot \mathbb{E}_{\bfX}\big| \phi^{\prime}(\bfa_n^T\bfX\bfw_k)\big( \phi(\bfa_n^T\bfX\bfw_j^*) - \phi(\bfa_n^T\bfX\bfw_j)  \big)\big|^{2p}  \Big)^{1/2p}\\
\le & p^{-1}\Big(\mathbb{E}_{\bfX} \big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^{2p} \Big)^{1/2p}
\cdot \Big(\mathbb{E}_{\bfX}\big| \bfa_n^T\bfX(\bfw_j^*-\bfw_j) \big|^{2p}  \Big)^{1/2p}\\

\end{split}
\end{equation}
where the first inequality comes from the Cauchy-Schwarz inequality. Furthermore, $\bfa_n^T\bfX$ belongs to the Gaussian distribution and thus is a sub-Gaussian random vector as well. Then, from Definition \ref{Def: sub-gaussian}, we have
\begin{equation}
\begin{gathered}
    \Big(\mathbb{E}_{\bfX} \big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^{2p} \Big)^{1/2p}  \le (2p)^{1/2}\|\bfX^T\bfa_n\|_{\psi_2}
    \le (2p)^{1/2}\|\bfa_n \|_2,\\
    \text{and}\quad
    \Big(\mathbb{E}_{\bfX}\big| \bfa_n^T\bfX(\bfw_j^*-\bfw_j) \big|^{2p}  \Big)^{1/2p}
    \le (2p)^{1/2}\|\bfa_n \|_2\cdot \|\bfw_j^*-\bfw_j \|_2.
    \end{gathered}
\end{equation}
Then, we have
\begin{equation}
\begin{split}
&p^{-1}\Big(\mathbb{E}_{\bfX} \big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\phi^{\prime}(\bfa_n^T\bfX\bfw_k)\big( \phi(\bfa_n^T\bfX\bfw_j^*) - \phi(\bfa_n^T\bfX\bfw_j)  \big)\big|^p  \Big)^{1/p}\\
    \le& p^{-1}\cdot 2p\|\bfa_n\|_2^2\cdot \|\bfw_j^*-\bfw_j \|_2\\
\le& 2\sigma_1^2(\bfA)\cdot \|\bfw_j^*-\bfw_j \|_2.
\end{split}
\end{equation}

Therefore, from Definition \ref{Def: sub-exponential}, $\bfz_n(k,j)$ belongs to the sub-exponential distribution with
\begin{equation}
    \|\bfz_n \|_{\phi_1} \le 2\sigma^2_1(\bfA)\cdot \|\bfw_j^*-\bfw_j\|_2.
\end{equation}

Recall that each node is connected with at most $\delta$ other nodes. Hence, for any fixed $\bfz_n$, there are at most $(1+\delta^2)$ (including $\bfz_n$ itself) elements in $\big\{ \bfz_l\big| l\in\Omega_t \big\}$ are dependant with $\bfz_n$. From Lemma \ref{Lemma: partial_independent_var},   the moment generation function of $\sum_{n\in\Omega_t} (\bfz_n-\mathbb{E}_{\bfX}\bfz_n)$ satisfies
\begin{equation}
    \mathbb{E}_{\bfX} e^{s\sum_{n\in\Omega_t} (\bfz_n-\mathbb{E}_{\bfX}\bfz_n)}\le e^{C(1+\delta^2)|\Omega_t|s^2}.
\end{equation}

By Chernoff inequality, we have
\begin{equation}
    \text{Prob}
    \bigg\{  \Big\|\frac{1}{|\Omega_t|} \sum_{n \in \Omega_t} \big(\bfz_n(k,j) - \mathbb{E}_{\bfX}\bfz_n(k,j)\big) \Big\|_2>t
    \bigg
    \}\le \frac{e^{C(1+\delta^2)|\Omega_t|s^2}}{e^{|\Omega_t|ts}}
\end{equation}
for any $s>0$.

Let $s = t/\big(C(1+\delta^2)\|\bfz_n \|_{\phi_1}^2\big)$ and $t = \sqrt{ \frac{(1+\delta^2)d\log N}{|\Omega_t|}} \|\bfz_n \|_{\phi_1}$, we have
\begin{equation}
\begin{split}
\Big\|\frac{1}{|\Omega_t|} \sum_{n \in \Omega_t} \big(\bfz_n(k,j) - \mathbb{E}_{\bfX}\bfz_n(k,j)\big) \Big\|_2
\le& C\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}\sigma_1^2(\bfA)\cdot \|\bfw_{j}^*-\bfw_{j}\|_2\\

\le&C\sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}\cdot \|\bfW^*-\bfW\|_2
\end{split}
\end{equation}
with probability at least $1- N^{-d}$.

In conclusion, by selecting $\xi=\frac{1}{2}$ in Lemmas \ref{Lemma: covering_set} and \ref{Lemma: spectral_norm on net}, we have
\begin{equation}
\begin{split}
\Big\|\frac{\partial\hat{f}_{\Omega_t}}{\partial \bfw_k}(\bfW) - \frac{\partial{f}_{\Omega_t}}{\partial \bfw_k}(\bfW)\Big\|_2
\le& \sum_{k=1}^{K}\sum_{j=1}^{K}\frac{1}{K^2}\Big\|\frac{1}{|\Omega_t|} \sum_{n \in \Omega_t}\bfz_n(k,j) - \mathbb{E}_{\bfX}\bfz_n(k,j)\Big\|_2\\
\le& C\sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}\cdot \|\bfW^*-\bfW \|_2
\end{split}
\end{equation}
with probability at least $1-\big(\frac{5}{N} \big)^d$.
\end{proof}

\subsection{Proof of auxiliary lemmas for regression problems}\label{sec: sub_lr}
\subsubsection{Proof of Lemma \ref{Lemma: lemma 5}}\label{Sec: lemma5}
\begin{proof}[Proof of Lemma \ref{Lemma: lemma 5}  ]
	For any normalized $\boldsymbol{\alpha}\in \mathbb{R}^{Kd}$, the lower bound of $\nabla^2f_{\Omega_t}(\bfW^*)$ is derived from
	\begin{equation}
	\begin{split}
	\boldsymbol{\alpha}^T {\nabla^2 f(\bfW^*)} \boldsymbol{\alpha}
	=&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \mathbb{E}_{\bfX}\bigg[ \Big( \sum_{j=1}^{K} \boldsymbol{\alpha}_j^T\bfX^T \bfa_n \phi^{\prime}(\bfa_n^T\bfX
	\bfw_j^*)  \Big)^2  \bigg]\\
	\ge & \frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t}\frac{\|\bfa_n\|_2^2}{11 \kappa^2 \gamma}\|\boldsymbol{\alpha}\|_2^2
	=  \frac{\sigma_1^2(\bfA)}{11 \kappa^2 \gamma K^2},
	\end{split}
	\end{equation}
	where the last inequality comes from Lemma D.6 in \cite{ZSJB17_v2}.

	Next,  the upper bound of $\nabla^2f_{\Omega_t}(\bfW^*)$ is derived from
	\begin{equation}
	\begin{split}
	&\boldsymbol{\alpha}^T {\nabla^2 f(\bfW^*)} \boldsymbol{\alpha}\\
	=&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \mathbb{E}_{\bfX}\bigg[ \Big( \sum_{j=1}^{K} \boldsymbol{\alpha}_j^T\bfX^T \bfa_n \phi^{\prime}(\bfa_n^T\bfX\bfw_j^*)  \Big)^2  \bigg]\\
	=&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \sum_{j_1=1}^{K} \sum_{j_2=1}^{K} \mathbb{E}_{\bfX}\bigg[  \boldsymbol{\alpha}_{j_1}^T\bfX^T\bfa_n \phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)
	\boldsymbol{\alpha}_{j_2}^T\bfX^T\bfa_n \phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2}^*)  \bigg]\\
	\le&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \sum_{j_1=1}^{K} \sum_{j_2=1}^{K} \Big[\mathbb{E}_{\bfX}|\boldsymbol{\alpha}_{j_1}^T\bfX^T\bfa_n|^4 \cdot\mathbb{E}_{\bfX}|\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)|^4
	\cdot\mathbb{E}_{\bfX}|\boldsymbol{\alpha}_{j_2}^T\bfX^T\bfa_n|^4
	\cdot\mathbb{E}_{\bfX}|\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2}^*)|^4\Big]^{\frac{1}{4}}\\
	\le& \frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \sum_{j_1=1}^{K} \sum_{j_2=1}^{K} 3\sigma_1^2(\bfA)\|\boldsymbol{\alpha}_{j_1} \|_2\|\boldsymbol{\alpha}_{j_2} \|_2\\
	\le& 3\sigma_1^2(\bfA) \frac{\|\boldsymbol{\alpha}\|_2^2}{K},
	\end{split}
	\end{equation}
	which completes the proof.
\end{proof}
\subsubsection{Proof of Lemma \ref{Lemma: lemma 6}}\label{Sec: lemma6}
\begin{proof}[Proof of Lemma \ref{Lemma: lemma 6} ]
	The second-order derivative of $f_{\Omega_t}$ is written as
	\begin{equation}
	\begin{split}
	&\frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW) - \frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW^*)\\
	=&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \mathbb{E}_{\bfX}(\bfX^T \bfa_n)(\bfX^T\bfa_n)^T \Big[\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2})
	-\phi^{\prime}(\bfa_n^T\bfX\bfw^*_{j_1})\phi^{\prime}(\bfa_n^T\bfX\bfw^*_{j_2})\Big] \\
	=&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t}  \mathbb{E}_{\bfX}(\bfX^T \bfa_n)(\bfX^T\bfa_n)^T \big(\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)\big)\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2})\\
	&-\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \mathbb{E}_{\bfX}(\bfX^T \bfa_n)(\bfX^T\bfa_n)^T\phi^{\prime}(\bfa_n^T\bfX\bfw^*_{j_1})\big(\phi^{\prime}(\bfa_n^T\bfX\bfw^*_{j_2})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2})\big).
	\end{split}
	\end{equation}
	For any normalized $\boldsymbol{\alpha}\in \mathbb{R}^d$, we have
	\begin{equation}
	\begin{split}
	&\Big|\boldsymbol{\alpha}^T\Big[\frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW) - \frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW^*)\Big]\boldsymbol{\alpha}\Big|\\
	\le&\Big|\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t}  \mathbb{E}_{\bfX}(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2 \big(\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)\big)\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2})\Big|\\
	&+\Big|\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \mathbb{E}_{\bfX}(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2\phi^{\prime}(\bfa_n^T\bfX\bfw^*_{j_1})\big(\phi^{\prime}(\bfa_n^T\bfX\bfw^*_{j_2})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2})\big)\Big| \\
	\le&\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t}  \mathbb{E}_{\bfX}\big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^2\cdot \Big|\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)\Big|\\
	&+\frac{1}{K^2|\Omega_t|} \sum_{n \in \Omega_t} \mathbb{E}_{\bfX}\big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^2\cdot \Big|\phi^{\prime}(\bfa_n^T\bfX\bfw^*_{j_2})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_2})\Big|.
	\end{split}
	\end{equation}

	{ It is easy to verify there exists a basis such that $\mathcal{B}=\{\boldsymbol{\alpha},\boldsymbol{\beta}, \boldsymbol{\gamma}, \boldsymbol{\alpha}_4^{\perp}, \cdots, \boldsymbol{\alpha}_d^{\perp}\}$ with $\{\boldsymbol{\alpha}, \boldsymbol{\beta}, \boldsymbol{\gamma} \}$ spanning a subspace that contains $\boldsymbol{\alpha}, \bfw_{j_1}$ and $\bfw_{j_1}^*$. Then, for any $\bfX^T\bfa_n\in \mathbb{R}^d$, we have a unique $\bfz=\begin{bmatrix}
		z_1&z_2&\cdots & z_d
		\end{bmatrix}^T$ such that
		\begin{equation*}
		\bfX^T\bfa_n = z_1\boldsymbol{\alpha} + z_2 \boldsymbol{\beta} +z_3\boldsymbol{\gamma} + \cdots + z_d\boldsymbol{\alpha}^{\perp}_d.
		\end{equation*}
		Also, since $\bfX^T\bfa_n \sim \mathcal{N}(\boldsymbol{0}, \|\bfa_n \|_2^2\bfI_d)$, we have $\bfz \sim \mathcal{N}(\boldsymbol{0}, \|\bfa_n \|_2^2\bfI_d)$. Then, we have
		\begin{equation*}
		\begin{split}
		& \mathbb{E}_{\bfX}\big|\boldsymbol{\alpha}^T\bfX^T \bfa_n\big|^2\cdot \Big|\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)\Big| \\
		=& \mathbb{E}_{z_1, z_2, z_3}|\phi^{\prime}\big(\bfw_{j_1}^T\widetilde{\bfx}\big)-\phi^{\prime}\big({\bfw_{j_1}^*}^T\widetilde{\bfx}\big)|\cdot
		|\bfa^T\widetilde{\bfx}|^2\\
		=&\int|\phi^{\prime}\big(\bfw_{j_1}^T\widetilde{\bfx}\big)-\phi^{\prime}\big({\bfw_{j_1}^*}^T\widetilde{\bfx}\big)|\cdot
		|\bfa^T\widetilde{\bfx}|^2\cdot f_Z(z_1, z_2,z_3)dz_1 dz_2 dz_3,
		\end{split}
		\end{equation*}
		where $\widetilde{\bfx}= z_1\boldsymbol{\alpha} + z_2\boldsymbol{\beta} + z_3\boldsymbol{\gamma}$ and $f_Z(z_1, z_2,z_3)$ is the probability density function of $(z_1, z_2, z_3)$. Next, we consider spherical coordinates with $z_1= r\cos\phi_1 , z_2 = r\sin\phi_1\sin\phi_2, z_3=z_2 = r\sin\phi_1\cos\phi_2$. Hence,
		\begin{equation}
		\begin{split}
		& \mathbb{E}_{\bfX}\big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^2\cdot \Big|\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)\Big| \\
		=&\int\int\int|\phi^{\prime}\big(\bfw_{j_1}^T\widetilde{\bfx}\big)-\phi^{\prime}\big({\bfw_{j_1}^*}^T\widetilde{\bfx}\big)|\cdot |r\cos\phi_1|^2
		\cdot f_Z(r, \phi_1, \phi_2)r^2\sin \phi_1 drd\phi_1d\phi_2.
		\end{split}
		\end{equation}
		It is easy to verify that $\phi^{\prime}\big(\bfw_{j_1}^T\widetilde{\bfx}\big)$ only depends on the direction of $\widetilde{\bfx}$ and
		\begin{equation*}
		f_Z(r, \phi_1, \phi_2) = \frac{1}{(2\pi\|\bfa_n \|_2^2)^{\frac{3}{2}}}e^{-\frac{x_1^2+x_2^2+x_3^2}{2\|\bfa_n \|_2^2}}=\frac{1}{(2\pi\|\bfa_n \|_2^2)^{\frac{3}{2}}}e^{-\frac{r^2}{2\|\bfa_n \|_2^2}}
		\end{equation*}
		only depends on $r$. Then, we have
		\begin{equation}\label{eqn: ean111}
		\begin{split}
		&\mathbb{E}_{\bfX}\big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^2\cdot \Big|\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)\Big| \\
		=&\int \int\int|\phi^{\prime}\big(\bfw_{j_1}^T(\widetilde{\bfx}/r)\big)-\phi^{\prime}\big({\bfw_{j_1}^*}^T(\widetilde{\bfx}/r)\big)|\cdot |r\cos\phi_1|^2
		\cdot f_Z(r)r^2\sin \phi_1 drd\phi_1d\phi_2\\
		=& \int_0^{\infty} r^4f_z(r)dr\int_{0}^{\pi}\int_{0}^{2\pi}|\cos \phi_1|^2\cdot \sin\phi_1\cdot|\phi^{\prime}\big(\bfw_{j_2}^T(\widetilde{\bfx}/r)\big)-\phi^{\prime}\big({\bfw_{j_2}^*}^T(\widetilde{\bfx}/r)\big)|d\phi_1d\phi_2\\
		\le& 3\|\bfa_n\|^2_2 \cdot \int_0^{\infty} r^2f_z(r)dr\int_{0}^{\pi}\int_{0}^{2\pi} \sin\phi_1\cdot|\phi^{\prime}\big(\bfw_{j_2}^T(\widetilde{\bfx}/r)\big)-\phi^{\prime}\big({\bfw_{j_2}^*}^T(\widetilde{\bfx}/r)\big)|d\phi_1d\phi_2\\
		=&3\|\bfa_n\|^2_2\cdot\mathbb{E}_{z_1, z_2, z_3}\big|\phi^{\prime}\big(\bfw_{j_1}^T\widetilde{\bfx}\big)-\phi^{\prime}\big({\bfw_{j_1}^*}^T\widetilde{\bfx}\big)|\\
		=&3\|\bfa_n\|^2_2\cdot\mathbb{E}_{\bfX}\big|\phi^{\prime}\big(\bfa_n^T\bfX\bfw_{j_1}\big)-\phi^{\prime}\big(\bfa_n^T\bfX{\bfw_{j_1}^*}\big)\big|\\

		\end{split}
		\end{equation}

				Define a set $\mathcal{A}_1=\{\bfx| ({\bfw_{j_1}^*}^T\bfx)({\bfw_{j_1}}^T\bfx)<0 \}$. If $\bfx\in\mathcal{A}_1$, then ${\bfw_{j_1}^*}^T\bfx$ and ${\bfw_{j_1}}^T\bfx$ have different signs, which means the value of $\phi^{\prime}(\bfw_{j_1}^T\bfx)$ and $\phi^{\prime}({\bfw_{j_1}^*}^T\bfx)$ are different. This is equivalent to say that
	\begin{equation}\label{eqn:I_1_sub1}
	|\phi^{\prime}(\bfw_{j_1}^T\bfx)-\phi^{\prime}({\bfw_{j_1}^*}^T\bfx)|=
	\begin{cases}
	&1, \text{ if $\bfx\in\mathcal{A}_1$}\\
	&0, \text{ if $\bfx\in\mathcal{A}_1^c$}
	\end{cases}.
	\end{equation}
	Moreover, if $\bfx\in\mathcal{A}_1$, then we have
	\begin{equation}
	\begin{split}
	|{\bfw_{j_1}^*}^T\bfx|
	\le&|{\bfw_{j_1}^*}^T\bfx-{\bfw_{j_1}}^T\bfx|
	\le\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|\cdot\|\bfx\|.
	\end{split}
	\end{equation}
			Define a set $\mathcal{A}_2$ such that
	\begin{equation}
	\begin{split}
	\mathcal{A}_2
	=&\Big\{\bfx\Big|\frac{|{\bfw_{j_1}^*}^T\bfx|}{\|\bfw_{j_1}^*\|\|\bfx\|}\le\frac{\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|}{\|\bfw_{j_1}^*\|}   \Big\}
	=\Big\{\theta_{\bfx,\bfw_{j_1}^*}\Big||\cos\theta_{\bfx,\bfw_{j_1}^*}|\le\frac{\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|}{\|\bfw_{j_1}^*\|}   \Big\}.
	\end{split}
	\end{equation}
	Hence, we have that
	\begin{equation}\label{eqn:I_1_sub2}
	\begin{split}
	& \mathbb{E}_{\bfx}
	|\phi^{\prime}(\bfw_{j_1}^T\bfx)-\phi^{\prime}({\bfw_{j_1}^*}^T\bfx_{i_2})|
	= \text{Prob}(\bfx\in\mathcal{A}_1)
	\le\text{Prob}(\bfx\in\mathcal{A}_2).
	\end{split}
	\end{equation}
	Since $\bfx\sim \mathcal{N}({\bf0}, \bfI)$, $\theta_{\bfx,\bfw_{j_1}^*}$ belongs to the uniform distribution on $[-\pi, \pi]$, we have
	\begin{equation}\label{eqn:I_1_sub3}
	\begin{split}
	\text{Prob}(\bfx\in\mathcal{A}_2)
	=&\frac{\pi- \arccos\frac{\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|}{\|\bfw_{j_1}^*\|} }{\pi}\\
	\le&\frac{1}{\pi}\tan(\pi- \arccos\frac{\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|}{\|\bfw_{j_1}^*\|})\\
	=&\frac{1}{\pi}\cot(\arccos\frac{\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|}{\|\bfw_{j_1}^*\|})\\
	\le&\frac{2}{\pi}\frac{\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|}{\|\bfw_{j_1}^*\|}.
	\end{split}
	\end{equation}

	Hence,  \eqref{eqn: ean111} and \eqref{eqn:I_1_sub3} suggest that
	\begin{equation}\label{eqn:I_1_bound}
	\mathbb{E}_{\bfX}\big|\phi^{\prime}\big(\bfa_n^T\bfX\bfw_{j_1}\big)-\phi^{\prime}\big(\bfa_n^T\bfX{\bfw_{j_1}^*}\big)\big|\le\frac{6}{\pi}\frac{\|{\bfw_{j_1}^*}-{\bfw_{j_1}}\|}{\|\bfw_{j_1}^*\|}.
	\end{equation}
	}

	Then, we have
		\begin{equation}\label{eqn: ean111}
		\begin{split}
		&\mathbb{E}_{\bfX}\big|\boldsymbol{\alpha}^T\bfX^T\bfa_n\big|^2\cdot \Big|\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1})-\phi^{\prime}(\bfa_n^T\bfX\bfw_{j_1}^*)\Big| \\
		=&3\|\bfa_n\|^2_2\cdot\mathbb{E}_{\bfX}\big|\phi^{\prime}\big(\bfa_n^T\bfX\bfw_{j_1}\big)-\phi^{\prime}\big(\bfa_n^T\bfX{\bfw_{j_1}^*}\big)\big|\\
		\le & \frac{6\|\bfa_n \|_2^2}{\pi}\cdot \frac{\|\bfw_{j_1} - \bfw_{j_1}^* \|_2}{\|\bfw_{j_1}^*\|_2},
		\end{split}
		\end{equation}

	All in all, we have
	\begin{equation}
	\begin{split}
	\left\|\nabla^2f_{\Omega_t}(\bfW) - \nabla^2f_{\Omega_t}(\bfW^*)  \right\|_2
	\le&\sum_{j_1}^{K}\sum_{j_2}^{K}\Big\|\frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW) - \frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW^*)\Big\|_2\\
	\le& K^2\max_{j_1, j_2}\Big\|\frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW) - \frac{\partial^2 f_{\Omega_t}}{\partial \bfw_{j_1}\partial \bfw_{j_2}}(\bfW^*)\Big\|_2\\
	\le& K^2\cdot \frac{12\|\bfa_n \|_2^2}{\pi}\max_{j}\frac{\|\bfw_{j} - \bfw_{j}^* \|_2}{\|\bfw_{j}^*\|_2}\\
	\le & 4\sigma_1^2(\bfA)\frac{\|\bfW^*-\bfW\|_2}{\sigma_K}.
	\end{split}
	\end{equation}

\end{proof}

\subsubsection{Proof of Lemma \ref{Lemma: partial_independent_var}}
\begin{proof}[Proof of Lemma \ref{Lemma: partial_independent_var} ]
	According to the Definitions in \cite{J04}, there exists a family of $\{ (\mathcal{X}_j, w_j) \}_j$, where $\mathcal{X}_j \subseteq \mathcal{X} $ and $w_j \in [0,1]$, such that $\sum_{j}w_j \sum_{x_{n_j}\in\mathcal{X}_j}x_{n_j}=\sum_{n=1}^{N}x_n$, and $\sum_{j}w_j \le d_{\mathcal{X}}$ by equations (2.1) and (2.2) in \cite{J04}. Then, let $p_j$ be any positive numbers with $\sum_{j}p_j=1$. By Jensen's inequality, for any $s\in\mathbb{R}$, we have
	\begin{equation}
	e^{s\sum_{n=1}^Nx_n}=e^{\sum_{j}p_j\frac{s w_j}{p_j}X_j}\le \sum_{j}p_je^{\frac{sw_j}{p_j}X_j},
	\end{equation}
	where $X_j = \sum_{x_{n_j}\in\mathcal{X}_j}x_{n_j}$.

	Then, we have
	\begin{equation}
	\begin{split}
	\mathbb{E}_{\mathcal{X}}e^{s\sum_{n=1}^Nx_n}
	\le& \mathbb{E}_{\mathcal{X}}\sum_{j}p_je^{\frac{sw_j}{p_j}X_j}
	= \sum_{j} p_j \prod_{\mathcal{X}_j}\mathbb{E}_{\mathcal{X}}e^{\frac{sw_j}{p_j}x_{n_j}}\\
	\le& \sum_{j} p_j \prod_{\mathcal{X}_j}e^{\frac{Cw_j^2}{p_j^2}s^2}\\
	\le & \sum_{j} p_j e^{\frac{C|\mathcal{X}_j|w_j^2}{p_j^2}s^2}.\\
	\end{split}
	\end{equation}

	Let $p_j = \frac{w_j|\mathcal{X}_j|^{1/2}}{\sum_{j}w_j|\mathcal{X}_j|^{1/2}}$, then we have
	\begin{equation}
	\mathbb{E}_{\mathcal{X}}e^{s\sum_{n=1}^Nx_n}
	\le \sum_{j} p_j e^{C\big(\sum_{j}w_j|\mathcal{X}_j|^{1/2}\big)^2s^2}
	=e^{C\big(\sum_{j}w_j|\mathcal{X}_j|^{1/2}\big)^2s^2}.
	\end{equation}

	By Cauchy-Schwarz inequality, we have
	\begin{equation}
	\big(\sum_{j}w_j|\mathcal{X}_j|^{1/2}\big)^2\le \sum_{j}w_j \sum_{j}w_j |\mathcal{X}_j|\le d_{\mathcal{X}}N.
	\end{equation}

	Hence, we have
	\begin{equation}
	\mathbb{E}_{\mathcal{X}}e^{s\sum_{n=1}^Nx_n}\le 	e^{Cd_{\mathcal{X}}Ns^2}.
	\end{equation}
\end{proof}

\section{Proof of Theorem \ref{Thm: major_thm_cl}}
Recall that the empirical risk function in \eqref{eqn: classification} is defined as
	\begin{equation}\label{eqn_app: cl}
		\begin{split}
		\min_{\bfW}: \quad \hat{f}_{\Omega}(\bfW)
		=&\frac{1}{|\Omega|}\sum_{n\in \Omega} -y_n \log \big(g(\bfW;\bfa_n^T\bfX)\big)
		-(1-y_n) \log \big(1-g(\bfW;\bfa_n^T\bfX)\big).
		\end{split}
	\end{equation}
	The population risk function is defined as
\begin{equation}\label{eqn_app: cl_exp}
	\begin{split}
	f_{\Omega}(\bfW):=& \mathbb{E}_{\bfX,y_n}\hat{f}_{\Omega}(\bfW)\\
	=&\mathbb{E}_{\bfX}\mathbb{E}_{y_n|\bfX}\Big[\frac{1}{|\Omega|}\sum_{n\in \Omega}
	- y_n \log \big(g(\bfW;\bfa_n^T\bfX)\big)
	-(1-y_n) \log \big(1-g(\bfW;\bfa_n^T\bfX)\big)\Big]\\
	=&\mathbb{E}_{\bfX}\frac{1}{|\Omega|}\sum_{n\in \Omega} - g(\bfW^*;\bfa_n^T\bfX) \log \big(g(\bfW;\bfa_n^T\bfX)\big)
	-(1-g(\bfW^*;\bfa_n^T\bfX)) \log \big(1-g(\bfW;\bfa_n^T\bfX)\big).
	\end{split}
\end{equation}
The road-map of proof for Theorem \ref{Thm: major_thm_cl} follows the similar three steps as those for Theorem \ref{Thm: major_thm_lr}. The major differences lie  in three aspects: (i) in the second step,
the objective function $\hat{f}_{\Omega_t}$ is smooth since the activation function $\phi(\cdot)$ is sigmoid. Hence, we can directly apply the mean value theorem as $\nabla \hat{f}_{\Omega_t}(\bfW^{(t)}) \simeq \langle \nabla^2\hat{f}_{\Omega_t}(\widehat{\bfW}^{(t)}), \bfW^{(t)}-\bfW^* \rangle$ to characterize the effects of the gradient descent term in each iteration, and the error bound of $\nabla^2\hat{f}_{\Omega_t}$ is provided in Lemma \ref{lemma: local_convex_cl};
(ii) the objective function is the sum of cross-entry loss functions, which have more complex structure of derivatives than those of square loss functions;
(iii) as the convergent point may not be the critical point of empirical loss function,
we need to provide  the distance from the convergent point to the ground-truth parameters additionally, where Lemma \ref{lemma: first_order_cl} is used.

Lemmas \ref{lemma: local_convex_cl} and \ref{lemma: first_order_cl} are summarized in the following contents. Also, the notations $\lesssim$ and $\gtrsim$ follow the same definitions as in \eqref{eqn: lemma3}.
The proofs of Lemmas \ref{lemma: local_convex_cl} and \ref{lemma: first_order_cl} can be found in Appendix \ref{sec: local_cl} and \ref{sec: sub_cl}, respectively.
\begin{lemma}\label{lemma: local_convex_cl}
	For any $\bfW$ that satisfies
	\begin{equation}\label{eqn: initial_point_cl}
	\|\bfW-\bfW^*\| \le \frac{2\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}
	\end{equation}
	then the second-order derivative of the empirical risk function in \eqref{eqn_app: cl} for binary classification problems is bounded as
	\begin{equation}
			\frac{2(1-\varepsilon_0)}{11\kappa^2 \gamma K^2}\sigma_1^2(\bfA)
			\preceq \nabla^2\hat{f}_{\Omega_t}(\bfW)
			\preceq \sigma_1^2(\bfA).
	\end{equation}
	provided the number of samples satisfies
	\begin{equation}\label{eqn: sample_cl}
	|\Omega_t|\gtrsim \varepsilon_0^{-2}(1+\delta^2)\kappa^2\gamma \sigma_1^4(\bfA)K^6d\log N.
	\end{equation}
\end{lemma}

\begin{lemma}\label{lemma: first_order_cl}
	Let $\hat{f}_{\Omega_t}$ and ${f}_{\Omega_t}$ be the empirical and population risk function in \eqref{eqn_app: cl} and \eqref{eqn_app: cl_exp} for binary classification problems, respectively, then the first-order derivative of $\hat{f}_{\Omega_t}$ is close to its expectation ${f}_{\Omega_t}$ with an upper bound as
	\begin{equation}
	\begin{split}
	\|\nabla f_{\Omega_t}(\bfW) - \nabla \hat{f}_{\Omega_t}(\bfW) \|_2
	\lesssim K^2\sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log d}{|\Omega_t|}}
	\end{split}
	\end{equation}
	with probability at least $1-K^2N^{-10}$.
\end{lemma}
 With these preliminary lemmas, the proof of Theorem \ref{Thm: major_thm_cl} is formally summarized in the following contents.
\begin{proof}[Proof of Theorem \ref{Thm: major_thm_cl}]
	The update rule of $\bfW^{(t)}$ is
	\begin{equation}
	\begin{split}
	\bfW^{(t+1)}
	=&\bfW^{(t)}-\eta\nabla \hat{f}_{\Omega_t}(\bfW^{(t)})+\beta(\W[t]-\W[t-1])\\

	\end{split}
	\end{equation}
	Since $\widehat{\bfW}$ is a critical point, then we have  $\nabla \hat{f}_{\Omega_t}(\widehat{\bfW})=0$. By the intermediate value theorem, we have
	\begin{equation}
	\begin{split}
	\bfW^{(t+1)}
	=\bfW^{(t)}&- \eta\nabla^2\hat{f}_{\Omega_t}(\widehat{\bfW}^{(t)})(\bfW^{(t)}-\widehat{\bfW})\\
	&+\beta(\W[t]-\W[t-1])\\

	\end{split}
	\end{equation}
	where $\widehat{\bfW}^{(t)}$ lies in the convex hull of $\bfW^{(t)}$ and $\widehat{\bfW}$.

	Next, we have
	\begin{equation}\label{eqn: major_thm_key_eqn_cl}
	\begin{split}
	\begin{bmatrix}
	\W[t+1]-\bfW^*\\
	\W[t]-\bfW^*
	\end{bmatrix}
	=&\begin{bmatrix}
	\bfI-\eta\nabla^2{\hat{f}}_{\Omega_t}(\widehat{\bfW}^{(t)})+\beta\bfI &\beta\bfI\\
	\bfI& 0\\
	\end{bmatrix}
	\begin{bmatrix}
	\W[t]-\bfW^*\\
	\W[t-1]-\bfW^*
	\end{bmatrix}
	.
	\end{split}
	\end{equation}
	Let $\bfP(\beta)=\begin{bmatrix}
	\bfI-\eta\nabla^2{\hat{f}}_{\Omega_t}(\widehat{\bfW}^{(t)})+\beta\bfI &\beta\bfI\\
	\bfI& 0\\
	\end{bmatrix}$, so we have
	\begin{equation*}
	\begin{split}
	\left\|\begin{bmatrix}
	\W[t+1]-\bfW^*\\
	\W[t]-\bfW^*
	\end{bmatrix}
	\right\|_2
	=&
	\left\|\bfP(\beta)
	\right\|_2
	\left\|
	\begin{bmatrix}
	\W[t]-\bfW^*\\
	\W[t-1]-\bfW^*
	\end{bmatrix}
	\right\|_2.
	\end{split}
	\end{equation*}

	Then, we have
	\begin{equation}\label{eqn: convergence_cl}
	\begin{split}
	\|\W[t+1]-\bfW^* \|_2
	\lesssim& \| \bfP(\beta) \|_2 \|\W[t]-\bfW^* \|_2\\

	\end{split}
	\end{equation}

Let $\lambda_i$ be the $i$-th eigenvalue of $\nabla^2\hat{f}_{\Omega_t}(\widehat{\bfW}^{(t)})$, and $\delta_{i}$ be the $i$-th eigenvalue of matrix $\bfP(\beta)$. Following the similar analysis in proof of Theorem \ref{Thm: major_thm_lr}, we have
	\begin{equation}\label{eqn: Heavy_ball_result_cl}
	\delta_i(0)>\delta_i(\beta),\quad \text{for}\quad  \forall \beta\in\big(0, (1-{\eta \lambda_i})^2\big).
	\end{equation}
	Moreover, $\delta_i$ achieves the minimum $\delta_{i}^*=|1-\sqrt{\eta\lambda_i}|$ when $\beta= \big(1-\sqrt{\eta\lambda_i}\big)^2$.

	Let us first assume $\bfW^{(t)}$ satisfies \eqref{eqn: initial_point_cl} and the number of samples satisfies \eqref{eqn: sample_cl}, then
	from Lemma \ref{lemma: local_convex_cl}, we know that
	$$0<\frac{2(1-\varepsilon_0)\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}\le\lambda_i\le {\sigma_1^2(\bfA)}.$$
	We define $\gamma_1=\frac{2(1-\varepsilon_0)\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}$ and $\gamma_2={\sigma_1^2(\bfA)}$.

	Also, for any $\varepsilon_0\in (0, 1)$, we have
	\begin{equation}\label{eqn: con1_cl}
	\begin{split}
	\nu(\beta^*)= \|\bfP(\beta^*) \|_2

	= 1-\sqrt{\frac{\gamma_1}{2\gamma_2}}
	=1-\sqrt{\frac{1-\varepsilon_0}{11\kappa^2 \gamma K}}

	\end{split}
	\end{equation}

	Let $\beta = 0$, we have
	\begin{equation*}
	\begin{gathered}
	\nu(0) = \|\bfA(0) \|_2 = 1-\frac{1-\varepsilon_0}{{11\kappa^2 \gamma K}}.	\\
	\end{gathered}
	\end{equation*}

	Hence, with probability at least $1- K^2\cdot N^{-10}$, we have
	\begin{equation}\label{eqn: induction_cl}
	\begin{split}
	\|	\W[t+1]-\bfW^*\|_2
	\le\Big(1-\sqrt{\frac{1-\varepsilon_0}{11\kappa^2 \gamma K}}\Big)\|	\W[t]-\bfW^*\|_2,
	\end{split}
	\end{equation}
	provided that $\W[t]$ satisfies \eqref{eqn: initial_point_lr}, and
	\begin{equation}\label{eqn: N_3_cl}
	|\Omega_t|\gtrsim\varepsilon_0^{-2}\kappa^2\gamma (1+\delta^2)\sigma_1^4(\bfA)K^6d \log N.
	\end{equation}
	According to Lemma \ref{Thm: initialization}, we know that \eqref{eqn: initial_point_cl} holds for $\bfW^{(0)}$ if
	\begin{equation}\label{eqn: N_1_cl}
	|\Omega_t|\gtrsim \varepsilon_0^{-2}\kappa^{8}\gamma^2 (1+\delta^2) K^8d \log N.
	\end{equation}
	Combining \eqref{eqn: N_3_cl} and \eqref{eqn: N_1_cl}, we need $|\Omega_t|\gtrsim \varepsilon_0^{-2}\kappa^{8}\gamma^2 (1+\delta^2)\sigma_1^4(\bfA) K^8d \log N$.

	Finally,  by the mean value theorem, we have
	\begin{equation}
	\hat{f}_{\Omega_t}(\widehat{\bfW}) \le \hat{f}_{\Omega_t}(\bfW^*) + {\nabla\hat{f}_{\Omega_t}(\bfW^*)}^T(\widehat{\bfW}-\bfW^*) +
	\frac{1}{2} (\widehat{\bfW}-\bfW^*)^T\nabla^2\hat{f}_{\Omega_t}(\widetilde{\bfW})(\widehat{\bfW}-\bfW^*)
	\end{equation}
	for some $\widetilde{\bfW}$ between $\widehat{\bfW}$ and $\bfW^*$.
	Since $\widehat{\bfW}$ is the local minima, we have $\hat{f}_{\Omega_t}(\widehat{\bfW})\le \hat{f}_{\Omega_t}(\bfW^*)$. That is to say
	\begin{equation}
	{\nabla\hat{f}_{\Omega_t}(\bfW^*)}^T(\widehat{\bfW}-\bfW^*) +
	\frac{1}{2} (\widehat{\bfW}-\bfW^*)^T\nabla^2\hat{f}_{\Omega_t}(\widetilde{\bfW})(\widehat{\bfW}-\bfW^*)\le 0
	\end{equation}
	which implies
	\begin{equation}\label{eqn: cccccc3}
	\frac{1}{2} \|\nabla^2\hat{f}_{\Omega_t}(\widetilde{\bfW})\|_2\|\widehat{\bfW}-\bfW^*\|_2^2\le \|{\nabla\hat{f}_{\Omega_t}(\bfW^*)}\|_2\|\widehat{\bfW}-\bfW^*\|_2.
	\end{equation}
	From Lemma \ref{lemma: local_convex_cl}, we know that
	\begin{equation}\label{eqn: cccccc1}
	\|\nabla^2\hat{f}_{\Omega_t}(\widetilde{\bfW})\|_2\ge \frac{2(1-\varepsilon_0)}{11\kappa^2\gamma K^2}\sigma^2(\bfA).
	\end{equation}
	From Lemma \ref{lemma: first_order_cl}, we know that
	\begin{equation}\label{eqn: cccccc2}
	\|{\nabla\hat{f}_{\Omega_t}(\bfW^*)} \|_2 = \| {\nabla\hat{f}_{\Omega_t}(\bfW^*)} - {\nabla{f}_{\Omega_t}(\bfW^*)}\|_2 \lesssim K^2 \sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}.
	\end{equation}
	Plugging inequalities \eqref{eqn: cccccc1} and \eqref{eqn: cccccc2} back into \eqref{eqn: cccccc3}, we have
	\begin{equation}
	\|\widehat{\bfW} -\bfW^* \|_2 \lesssim (1-\varepsilon_0)^{-1}\kappa^2 \gamma K^4\sqrt{\frac{(1+\delta^2)d\log d}{|\Omega_t|}}.
	\end{equation}

\end{proof}

\subsection{Proof of Lemma \ref{lemma: local_convex_cl}}\label{sec: local_cl}
The roadmap of proof for Lemma \ref{lemma: local_convex_cl} follows the similar steps as those  of Lemma \ref{Lemma: local_convexity} for regression problems. Lemmas \ref{Lemma: CL_ground_truth}, \ref{Lemma: CL_W} and \ref{Lemma: CL_sample} are the preliminary lemmas, and
their proofs can be found in Appendix \ref{sec: sub_cl}. The proof of Lemma \ref{lemma: local_convex_cl} is summarized after these preliminary lemmas.
\begin{lemma}\label{Lemma: CL_ground_truth}
The second-order derivative of $f_{\Omega_t}$ at the ground truth $\bfW^*$ satisfies
	\begin{equation}
	\frac{4\sigma_1^2(\bfA)}{11\kappa^2 \gamma K^2}\bfI
	\preceq \nabla^2f_{\Omega_t}(\bfW^*)
	\preceq \frac{\sigma_1^2(\bfA)}{4}\bfI.
	\end{equation}
\end{lemma}

\begin{lemma}\label{Lemma: CL_W}
	Suppose $f_{\Omega_t}$ is the population loss function with respect to binary classification problems, then we have
	\begin{equation}
	\|\nabla^2f_{\Omega_t}(\bfW) - \nabla^2f_{\Omega_t}(\bfW^*) \|_2 \lesssim \|\bfW -\bfW^* \|_2.
	\end{equation}
\end{lemma}
\begin{lemma}\label{Lemma: CL_sample}
	Suppose $\hat{f}_{\Omega_t}$ is the empirical loss function with respect to binary classification problems, then the second-order derivative of $\widehat{f}_{\Omega_t}$ is close to its expectation with an upper bound as
	\begin{equation}
	\begin{split}
	\|\nabla^2f_{\Omega_t}(\bfW) - \nabla^2\hat{f}_{\Omega_t}(\bfW) \|_2
	\lesssim K^2\sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log d}{|\Omega_t|}}
	\end{split}
	\end{equation}
	with probability at least $1-K^2N^{-10}$.
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lemma: local_convex_cl} ]
For any $\bfW$, we have
\begin{equation}
\Big|\| \nabla^2 f_{\Omega_t}(\bfW)\|_2 -\|\nabla^2 f_{\Omega_t}(\bfW^*)  \|_2\Big|
\le\| \nabla^2 f_{\Omega_t}(\bfW) -\nabla^2 f_{\Omega_t}(\bfW^*)  \|_2 .
\end{equation}
That is
\begin{equation}
\begin{split}
&\| \nabla^2 f_{\Omega_t}(\bfW)\|_2 \le \|\nabla^2 f_{\Omega_t}(\bfW^*)  \|_2 + \| \nabla^2 f_{\Omega_t}(\bfW) -\nabla^2 f_{\Omega_t}(\bfW^*)  \|_2 \\
\text{and \quad} &\| \nabla^2 f_{\Omega_t}(\bfW)\|_2 \ge \|\nabla^2 f_{\Omega_t}(\bfW^*)  \|_2 - \| \nabla^2 f_{\Omega_t}(\bfW) -\nabla^2 f_{\Omega_t}(\bfW^*)  \|_2 \\
\end{split}
\end{equation}
Then, for any $\bfW$ that satisfies $\|\bfW-\bfW^*\| \le \frac{2\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}$, from Lemmas \ref{Lemma: CL_ground_truth} and \ref{Lemma: CL_W}, we have
\begin{equation}\label{eqn: CL_theorem_1}
\frac{2}{11\kappa^2 \gamma K^2}\sigma_1^2(\bfA)
\preceq \nabla^2f_{\Omega_t}(\bfW)
\preceq \frac{1}{2}\sigma_1^2(\bfA).
\end{equation}
Next, we have
\begin{equation}
\begin{split}
&\| \nabla^2 \hat{f}_{\Omega_t}(\bfW)\|_2 \le \|\nabla^2 f_{\Omega_t}(\bfW)\|_2+ \|\nabla^2\hat{f}_{\Omega_t}(\bfW) -\nabla^2 f_{\Omega_t}(\bfW) \|_2  \\
\text{and \quad} &\| \nabla^2 \hat{f}_{\Omega_t}(\bfW)\|_2 \ge \| \nabla^2 f_{\Omega_t}(\bfW)\|_2- \|\nabla^2 \hat{f}_{\Omega_t}(\bfW) -\nabla^2 f_{\Omega_t}(\bfW) \|_2  \\
\end{split}
\end{equation}
Then, from \eqref{eqn: CL_theorem_1} and Lemma \ref{Lemma: CL_sample}, we have
\begin{equation}
\frac{2(1-\varepsilon_0)}{11\kappa^2 \gamma K^2}\sigma_1^2(\bfA)
\preceq \nabla^2\hat{f}_{\Omega_t}(\bfW)
\preceq \sigma_1^2(\bfA)
\end{equation}
provided that  the sample size $|\Omega_t|\gtrsim \varepsilon_0^{-2}(1+\delta^2)\kappa^2\gamma \sigma_1^4(\bfA)K^6d\log N$.
\end{proof}

\subsection{Proof of auxiliary lemmas for binary classification problems}\label{sec: sub_cl}
\subsubsection{Proof of Lemma \ref{Lemma: CL_ground_truth}}
\begin{proof}[Proof of Lemma \ref{Lemma: CL_ground_truth} ]
	Since $\mathbb{E}_{\bfX}y_n = g_n(\bfW^*;\bfa_n)$, then  we have
	\begin{equation}
	\begin{split}
	\frac{\partial^2 f_{{\Omega_t}}(\bfW^*)}{\partial \bfw_j^* \partial \bfw_k^*}
	=&\mathbb{E}_{\bfX} \frac{\partial^2 \hat{f}_{\Omega_t}(\bfW^*)}{\partial \bfw_j^* \partial \bfw_k^*}\\
	=&\mathbb{E}_{\bfX}\frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\frac{1}{g(\bfW;\bfa_n)\big(1-g(\bfW;\bfa_n)\big)}\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T,
	\end{split}
	\end{equation}
	for any $j, k\in [K]$.

	Then, for any $\boldsymbol{\alpha} = \begin{bmatrix}
	\boldsymbol{\alpha}_1^T ,& \boldsymbol{\alpha}_2^T, &\cdots,&\boldsymbol{\alpha}_K^T
	\end{bmatrix}^T\in\mathbb{R}^{dk}$ with $\boldsymbol{\alpha}_j \in \mathbb{R}^d$, the lower bound can be obtained from
	\begin{equation}
	\begin{split}
	\boldsymbol{\alpha}^T \nabla^2 f_{\Omega_t}(\bfW^*) \boldsymbol{\alpha}
	=&\mathbb{E}_{\bfX}\frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\frac{\Big(\sum_{j=1}^{K}\boldsymbol{\alpha}_j^T\bfX^T\bfa_n\phi^{\prime}({\bfw_j^*}^T\bfX^T\bfa_n)\Big)^2}{g(\bfW^*;\bfa_n)\big(1-g(\bfW^*;\bfa_n)\big)}\\
	\ge&\mathbb{E}_{\bfX}\frac{4}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\Big(\sum_{j=1}^{K}\boldsymbol{\alpha}_j^T\bfX^T\bfa_n\phi^{\prime}({\bfw_j^*}^T\bfX^T\bfa_n)\Big)^2\\
	\ge& \frac{4\sigma_1^2(\bfA)}{11\kappa^2\gamma K^2}.
	\end{split}
	\end{equation}

	Also, for the upper bound, we have
	\begin{equation}
	\begin{split}
	\boldsymbol{\alpha}^T \nabla^2 f_{\Omega_t}(\bfW^*) \boldsymbol{\alpha}
	=&\mathbb{E}_{\bfX}\frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\frac{\Big(\sum_{j=1}^{K}\boldsymbol{\alpha}_j^T\bfX^T\bfa_n\phi^{\prime}({\bfw_j^*}^T\bfX^T\bfa_n)\Big)^2}{g(\bfW^*;\bfa_n)\big(1-g(\bfW^*;\bfa_n)\big)}\\
	=&\mathbb{E}_{\bfX}\frac{1}{|\Omega_t|}\sum_{n\in\Omega_t}\frac{\Big(\sum_{j=1}^{K}\boldsymbol{\alpha}_j^T\bfX^T\bfa_n\phi^{\prime}({\bfw_j^*}^T\bfX^T\bfa_n)\Big)^2}{\sum_{j_1=1}^{K}\phi({\bfw_{j_1}^*}^T\bfX^T\bfa_n)\sum_{j_2=1}^{K}\big(1-\phi({\bfw_{j_2}^*}^T\bfX^T\bfa_n)\big)}\\
	\le& \mathbb{E}_{\bfX}\frac{1}{|\Omega_t|}\sum_{n\in\Omega_t}\frac{\sum_{j=1}^{K}\big(\boldsymbol{\alpha}_j^T\bfX^T\bfa_n\big)^2 \sum_{j=1}^{K}\big( \phi^{\prime}({\bfw_j^*}^T\bfX^T\bfa_n)\big)^2}{\sum_{j_1=1}^{K}\phi({\bfw_{j_1}^*}^T\bfX^T\bfa_n)\sum_{j_2=1}^{K}\big(1-\phi({\bfw_{j_2}^*}^T\bfX^T\bfa_n)\big)}.\\
	\end{split}
	\end{equation}
	For the denominator item, we have
	\begin{equation}
	\begin{split}
	\sum_{j_1=1}^{K}\phi({\bfw_{j_1}^*}^T\bfX^T\bfa_n)\sum_{j_2=1}^{K}\big(1-\phi({\bfw_{j_2}^*}^T\bfX^T\bfa_n)\big)
	\ge&\sum_{j=1}^{K}\phi({\bfw_{j}^*}^T\bfX^T\bfa_n)\big(1-\phi({\bfw_{j}^*}^T\bfX^T\bfa_n)\big)\\
	=&\sum_{j=1}^{K}\phi^{\prime}({\bfw_{j}^*}^T\bfX^T\bfa_n)\\
	\ge&4 \sum_{j=1}^{K}\phi^{\prime}({\bfw_{j}^*}^T\bfX^T\bfa_n)^2.\\
	\end{split}
	\end{equation}
	Hence, we have
	\begin{equation}
	\begin{split}
	\boldsymbol{\alpha}^T \nabla^2 f_{\Omega_t}(\bfW^*) \boldsymbol{\alpha}
	\le \mathbb{E}_{\bfX}\frac{1}{4|\Omega_t|}\sum_{n\in \Omega_t}\sum_{j=1}^{K}(\boldsymbol{\alpha}_j^T \bfX^T\bfa_n)^2
	\le \frac{1}{4}\sigma_1^2(\bfA).
	\end{split}
	\end{equation}
\end{proof}
\subsubsection{Proof of Lemma \ref{Lemma: CL_W}}
\begin{proof}[Proof of Lemma \ref{Lemma: CL_W}  ]
	Recall that
	\begin{equation}
	\begin{split}
	&\frac{\partial^2 {f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k} \\
	=&\mathbb{E}_{\bfX} \frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\bigg(\frac{g(\bfW^*;\bfa_n)}{g^2(\bfW;\bfa_n)} + \frac{1 - g(\bfW^*;\bfa_n)}{(1-g(\bfW;\bfa_n))^2} \bigg)\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T,
	\end{split}
	\end{equation}
	and
	\begin{equation}
	\begin{split}
	\frac{\partial^2 {f}_{\Omega_t}(\bfW)}{\partial \bfw_j^2 }
	=&\mathbb{E}_{\bfX} \frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\bigg(\frac{g(\bfW^*;\bfa_n)}{g^2(\bfW;\bfa_n)} + \frac{1 - g(\bfW^*;\bfa_n)}{(1-g(\bfW;\bfa_n))^2} \bigg)\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)^2(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T\\
	&-\mathbb{E}_{\bfX}\frac{1}{K|\Omega_t|}\sum_{n\in\Omega_t}\bigg(-\frac{g(\bfW^*;\bfa_n)}{g(\bfW;\bfa_n)} + \frac{1 - g(\bfW^*;\bfa_n)}{1-g(\bfW;\bfa_n)} \bigg)\phi^{\prime\prime}(\bfw_j^T\bfX^T\bfa_n)(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T.
	\end{split}
	\end{equation}
	Let us denote $A_{j,k}(\bfW;\bfa_n)$ as
	\begin{equation}
	A_{j,k}(\bfW;\bfa_n) = \begin{cases}
	\frac{1}{K^2}\big(\frac{g(\bfW^*;\bfa_n)}{g^2(\bfW;\bfa_n)} + \frac{1 - g(\bfW^*;\bfa_n)}{(1-g(\bfW;\bfa_n))^2} \big)\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)\\
	~~~~~~~~~~~~~-\frac{1}{K}\big(-\frac{g(\bfW^*;\bfa_n)}{g(\bfW;\bfa_n)} + \frac{1 - g(\bfW^*;\bfa_n)}{1-g(\bfW;\bfa_n)} \big)\phi^{\prime\prime}(\bfw_j^T\bfX^T\bfa_n),\text{\quad when \quad} j=k;\\
	~\\
	\frac{1}{K^2}\big(\frac{g(\bfW^*;\bfa_n)}{g^2(\bfW;\bfa_n)} + \frac{1 - g(\bfW^*;\bfa_n)}{(1-g(\bfW;\bfa_n))^2} \big)\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n), \text{\quad  when \quad} j\neq k.
	\end{cases}
	\end{equation}
	Further, let us define $M(\bfW;\bfa_n) = \max \Big\{\frac{2}{K^3}\frac{1}{g^3(\bfW;\bfa_n)}, \frac{2}{K^3}\frac{1}{(1-g(\bfW;\bfa_n))^3}, \frac{1}{K^2}\frac{1}{g^2(\bfW;\bfa_n)},\frac{1}{K^2} \frac{1}{ ((1-g(\bfW;\bfa_n))^2 } \Big\}$.

	Then, by the mean value theorem, we have
	\begin{equation}
	A_{j,k}(\bfW;\bfa_n) - A_{j,k}(\bfW;\bfa_n) = \sum_{l=1}^{K}\langle\frac{\partial A_{j,k}}{\partial \bfw_{l}}(\widetilde{\bfW};\bfa_n), \bfw_l-\bfw_l^* \rangle.
	\end{equation}
	For $\frac{\partial A_{j,k}}{\partial \bfw_{l}}$, we have
	\begin{equation}
	\frac{\partial A_{j,k}}{\partial \bfw_{l}}(\widetilde{\bfW};\bfa_n) = B_{j,k,l}(\widetilde{\bfW};\bfa_n) \bfX^T\bfa_n
	\end{equation}
	with
	\begin{equation}
	\begin{split}
	|B_{j,k,l}(\widetilde{\bfW};\bfa_n)|
	\le& \frac{2}{K^3}\frac{1}{g^3(\widetilde{\bfW};\bfa_n)} +  \frac{2}{K^3}\frac{1}{(1-g(\widetilde{\bfW};\bfa_n))^3} + \frac{1}{K^2}\frac{1}{g(\widetilde{\bfW};\bfa_n)} + \frac{1}{K^2} \frac{1}{ (1-g(\widetilde{\bfW};\bfa_n))^2}\\
	\le & 4 M(\widetilde{\bfW};\bfa_n).
	\end{split}
	\end{equation}
	for all $j\in[K],k\in[K],l\in[K]$.

	Therefore, for any $\boldsymbol{\alpha}\in \mathbb{R}^{Kd}$, we have
	\begin{equation}
	\begin{split}
	&\boldsymbol{\alpha}^T \nabla^2f_{\Omega_t}(\bfW)\boldsymbol{\alpha}\\
	\le& \frac{1}{|\Omega_t|}\sum_{n\in |\Omega_t|} \sum_{j=1}^{K}\sum_{k=1}^{K}\mathbb{E}_{\bfX}\Big|\boldsymbol{\alpha}_j^T \frac{\partial f_{\Omega_t}}{\partial \bfw_j \partial \bfw_k}(\bfW) \boldsymbol{\alpha}_k \Big|\\
	=& \frac{1}{|\Omega_t|}\sum_{n\in |\Omega_t|} \sum_{j=1}^{K}\sum_{k=1}^{K}\mathbb{E}_{\bfX}\Big|\sum_{l=1}^{K}|B_{j,k,l}(\widetilde{\bfW};\bfa_n)| \langle \bfw_l-\bfw_l^*, \bfX^T\bfa_n \rangle \langle \boldsymbol{\alpha}_j, \bfX^T\bfa_n \rangle\langle \boldsymbol{\alpha}_k, \bfX^T\bfa_n \rangle \Big|\\
	=& \frac{1}{|\Omega_t|}\sum_{n\in |\Omega_t|} \sum_{j=1}^{K}\sum_{k=1}^{K}\bigg(\sum_{l=1}^{K}\mathbb{E}_{\bfX}|B_{j,k,l}(\widetilde{\bfW};\bfa_n)|^2\bigg)^{\frac{1}{2}}
	\bigg(\sum_{l=1}^{K}\mathbb{E}_{\bfX}\big|\langle \bfw_l-\bfw_l^*, \bfX^T\bfa_n \rangle \langle \boldsymbol{\alpha}_j, \bfX^T\bfa_n \rangle\langle \boldsymbol{\alpha}_k, \bfX^T\bfa_n \rangle\big|^2\bigg)^{\frac{1}{2}}\\
	\le&\frac{1}{|\Omega_t|}\sum_{n\in |\Omega_t|} \sum_{j=1}^{K}\sum_{k=1}^{K} 36K^{\frac{1}{2}} \Big(\mathbb{E}_\bfX M^2(\widehat{\bfW};\bfa_n) \Big)^\frac{1}{2} \cdot
	\Big(\sum_{l=1}^{K}\|\bfw_l -\bfw_l^*\|_2^2\Big)^{\frac{1}{2}} \|\bfa_j\|_2 \|\bfa_k\|_2\\
	\le &\frac{1}{|\Omega_t|}\sum_{n\in |\Omega_t|}  36K^{3} \Big(\mathbb{E}_\bfX M^2(\widehat{\bfW};\bfa_n) \Big)^\frac{1}{2}
	\|\bfW -\bfW^*\|_2\\
	\stackrel{(a)}{\lesssim} & e^{\sigma_1^2(\bfA)} \|\bfW -\bfW^*\|_2\\
	\lesssim & \|\bfW -\bfW^*\|_2,
	\end{split}
	\end{equation}
	where ($a$) comes from Lemma 5 in \cite{FCL19}.
\end{proof}

\subsubsection{Proof of Lemma \ref{Lemma: CL_sample}}
\begin{proof}[Proof of Lemma \ref{Lemma: CL_sample} ]
	Recall that
	\begin{equation}
	\begin{split}
	&\frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k} \\
	=&\frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\bigg(\frac{y_n}{g^2(\bfW;\bfa_n)} + \frac{1 - y_n}{(1-g(\bfW;\bfa_n))^2} \bigg)\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T,
	\end{split}
	\end{equation}
	and
	\begin{equation}
	\begin{split}
	\frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j^2 }
	=&\frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\bigg(\frac{y_n}{g^2(\bfW;\bfa_n)} + \frac{1 - y_n}{(1-g(\bfW;\bfa_n))^2} \bigg)\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)^2(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T\\
	&-\frac{1}{K|\Omega_t|}\sum_{n\in\Omega_t}\bigg(-\frac{y_n}{g(\bfW;\bfa_n)} + \frac{1 - y_n}{1-g(\bfW;\bfa_n)} \bigg)\phi^{\prime\prime}(\bfw_j^T\bfX^T\bfa_n)(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T.
	\end{split}
	\end{equation}

	When $y_n=1$ and $j\neq k$, we have
	\begin{equation}
	\begin{split}
	\frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k}
	=\frac{1}{K^2|\Omega_t|}\sum_{n\in\Omega_t}\frac{\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)}{g^2(\bfW;\bfa_n)}(\bfX^T\bfa_n)(\bfX^T\bfa_n)^T,
	\end{split}
	\end{equation}
	and
	\begin{equation}\label{eqn: sths_1}
	\begin{split}
	\frac{\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)}{g^2(\bfW;\bfa_n)}
	=& \frac{\phi(\bfw_j^T\bfX^T\bfa_n)(1-\phi(\bfw_j^T\bfX^T\bfa_n))\phi(\bfw_k^T\bfX^T\bfa_n)(1-\phi(\bfw_k^T\bfX^T\bfa_n))}{\big(\frac{1}{K}\sum_{l=1}^{K}\phi(\bfw_l^T\bfX^T\bfa_n)\big)^2}\\
	\le&K^2\frac{\phi(\bfw_j^T\bfX^T\bfa_n)(1-\phi(\bfw_j^T\bfX^T\bfa_n))\phi(\bfw_k^T\bfX^T\bfa_n)(1-\phi(\bfw_k^T\bfX^T\bfa_n))}{\phi(\bfw_j^T\bfX^T\bfa_n)\phi(\bfw_k^T\bfX^T\bfa_n)}\\
	=&K^2(1-\phi(\bfw_j^T\bfX^T\bfa_n))(1-\phi(\bfw_k^T\bfX^T\bfa_n))\le K^2.
	\end{split}
	\end{equation}
	When $y_n=1$ and $j= k$, we have
	\begin{equation}
	\begin{split}
	\frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k}
	=\frac{1}{|\Omega_t|}\sum_{n\in\Omega_t}\Big[\frac{1}{K^2}\frac{\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)}{g^2(\bfW;\bfa_n)}
	+\frac{1}{K}\frac{\phi^{\prime\prime}(\bfw_j^T\bfX^T\bfa_n)}{g(\bfW;\bfa_n)} \Big](\bfX^T\bfa_n)(\bfX^T\bfa_n)^T,
	\end{split}
	\end{equation}
	and
	\begin{equation}\label{eqn:sths_2}
	\begin{split}
	\Big|\frac{\phi^{\prime\prime}(\bfw_j^T\bfX^T\bfa_n)}{g(\bfW;\bfa_n)}\Big|
	= \frac{\phi(\bfw_k^T\bfX^T\bfa_n)(1-\phi(\bfw_k^T\bfX^T\bfa_n))\cdot \big|1-2\phi(\bfw_k^T\bfX^T\bfa_n)\big|}{\frac{1}{K}\sum_{l=1}^{K}\phi(\bfw_l^T\bfX^T\bfa_n)}
	\le K.
	\end{split}
	\end{equation}
	Similar to \eqref{eqn: sths_1} and \eqref{eqn:sths_2}, we can obtain the following inequality for $y_n=0$.
	\begin{equation}
	\begin{gathered}
	\frac{\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)}{\big(1-g(\bfW;\bfa_n)\big)^2}
	\le K^2, \text{\quad and \quad}
	\Big|\frac{\phi^{\prime\prime}(\bfw_j^T\bfX^T\bfa_n)}{1-g(\bfW;\bfa_n)}\Big|
	\le K.
	\end{gathered}
	\end{equation}

	Then, for any $\boldsymbol{\alpha}\in \mathbb{R}^d$, we have
	\begin{equation}
	\begin{split}
	\boldsymbol{\alpha}^T \frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k} \boldsymbol{\alpha}
	=& \frac{1}{|\Omega_t|}\sum_{n\in\Omega_t}\bigg[\frac{1}{K^2}\bigg(\frac{y_n}{g^2(\bfW;\bfa_n)} + \frac{1 - y_n}{(1-g(\bfW;\bfa_n))^2} \bigg)\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\phi^{\prime}(\bfw_k^T\bfX^T\bfa_n)\\
	&-\frac{\mathds{1}_{\{j=k\}}}{K}\bigg(-\frac{y_n}{g(\bfW;\bfa_n)} + \frac{1 - y_n}{1-g(\bfW;\bfa_n)} \bigg)\phi^{\prime\prime}(\bfw_j^T\bfX^T\bfa_n) \bigg](\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2\\
	:=&\frac{1}{|\Omega_t|}\sum_{n\in\Omega_t} H_{j,k}(\bfa_n)\cdot(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2.
	\end{split}
	\end{equation}

	Next, we show that $H_{j,k}(\bfa_n)\cdot(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2$ belongs to the sub-exponential distribution.
	For any $p\in\mathbb{N}^+$, we have
	\begin{equation}\label{eqn: second_h_cl}
	\begin{split}
	\Big(\mathbb{E}_{\bfX,\bfy_n} \Big[ \big|H_{j,k}(\bfa_n)\cdot(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2\big|^p \Big]\Big)^{1/p}
	\le&\Big(\mathbb{E}_{\bfX} \Big[ \big|4(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2\big|^p \Big]\Big)^{1/p}\\
	\le& 8\|\bfa_n \|_2^2 p\le  8\sigma_1^2(\bfA) p
	\end{split}
	\end{equation}
	Hence, $H_{j,k}(\bfa_n)\cdot(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2$ belongs to the sub-exponential distribution with $\| H_{j,k}(\bfa_n)(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2 \|_{\psi_1} = 8\sigma_1^2(\bfA)$. Then, the moment generation function of $H_{j,k}(\bfa_n)\cdot(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2$ can be bounded as
	\begin{equation}
	\mathbb{E}e^{sH_{j,k}(\bfa_n)\cdot(\boldsymbol{\alpha}^T\bfX^T\bfa_n)^2}\le e^{C\sigma_1^2(\bfA)s^2}
	\end{equation}
	for some positive constant $C$ and any $s\in\mathbb{R}$. From Lemma \ref{Lemma: partial_independent_var} and Chernoff bound, we have
	\begin{equation}
	\boldsymbol{\alpha}^T \Big(\frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k} - \frac{\partial^2{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k}\Big)\boldsymbol{\alpha} \le C\sigma_1^2(\bfA) \sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}
	\end{equation}
	with probability at least $1-N^{-d}$. By selecting $\xi=\frac{1}{2}$ in Lemmas \ref{Lemma: covering_set} and \ref{Lemma: spectral_norm on net}, we have
	\begin{equation}
	\left\| \frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k} - \frac{\partial^2{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k} \right\|_2
	\le  C\sigma_1^2(\bfA) \sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}
	\end{equation}
	with probability at least $1-\big(\frac{5}{N}\big)^{d}$.

	In conclusion, we have
	\begin{equation}
	\begin{split}
	\|\nabla^2f_{\Omega_t}(\bfW) - \nabla^2\hat{f}_{\Omega_t}(\bfW) \|_2
	\le& \sum_{j=1}^{K} \sum_{k=1}^{K}\left\| \frac{\partial^2 \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k}
	- \frac{\partial^2{f}_{\Omega_t}(\bfW)}{\partial \bfw_j \partial \bfw_k} \right\|_2\\
	\le& CK^2\sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log d}{|\Omega_t|}}
	\end{split}
	\end{equation}
	with probability at least $1-\big(\frac{5}{d}\big)^{d}$.
\end{proof}

\subsubsection{Proof of Lemma \ref{lemma: first_order_cl}}
\begin{proof}[Proof of Lemma \ref{lemma: first_order_cl}]
	Recall that the first-order derivative of $\hat{f}_{\Omega_t}(\bfW)$ is calculated from
	\begin{equation}
	\frac{\partial \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j} = -\frac{1}{K|\Omega_t|}\sum_{n\in\Omega}\frac{y_n-g(\bfW;\bfa_n)}{g(\bfW;\bfa_n)\big(1-g(\bfW;\bfa_n)\big)}\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)\bfX^T\bfa_n.
	\end{equation}
	Similar to  \eqref{eqn:sths_2}, we have
	\begin{equation}
	\begin{split}
	\Big|\frac{\phi^{\prime}(\bfw_j^T\bfX^T\bfa_n)}{g(\bfW;\bfa_n)}\Big|
	= \frac{\phi(\bfw_k^T\bfX^T\bfa_n)(1-\phi(\bfw_k^T\bfX^T\bfa_n))}{\frac{1}{K}\sum_{l=1}^{K}\phi(\bfw_l^T\bfX^T\bfa_n)}
	\le K.
	\end{split}
	\end{equation}
	Similar to \eqref{eqn: second_h_cl}, for any fixed $\boldsymbol{\alpha}\in \mathbb{R}^{dK}$, we can show that random variable $\boldsymbol{\alpha}^T\frac{\partial \hat{f}_{\Omega_t}(\bfW)}{\partial \bfw_j}$ belongs to sub-exponential distribution with the same bounded norm up to a constant.
	 Hence, by applying Lemma \ref{Lemma: partial_independent_var} and the Chernoff bound, we have
	 \begin{equation}
	 \left\| \nabla f_{\Omega_t}(\bfW) - \nabla\hat{f}_{\Omega_t}(\bfW) \right\|_2
	 \lesssim K^2\sigma_1^2(\bfA) \sqrt{\frac{(1+\delta^2)d\log N}{|\Omega_t|}}
	 \end{equation}
	 with probability at least $1-\big(\frac{5}{N}\big)^{d}$.
\end{proof}
\section{Proof of Lemma \ref{Lemma: sigma_1}}
\begin{proof}[Proof of Lemma \ref{Lemma: sigma_1}]
Let $\widetilde{\bfA}$  denote the adjacency matrix, then we have
    \begin{equation}
        \sigma_1(\widetilde{\bfA}) = \max_{\bfz} \frac{\bfz^T \widetilde{\bfA} \bfz}{\bfz^T \bfz} \ge \frac{\boldsymbol{1}^T\widetilde{\bfA}\boldsymbol{1}}{\boldsymbol{1}^T\boldsymbol{1}}= 1 + \frac{\sum_{n=1}^N \delta_{n} }{N},
    \end{equation}
    where $\delta_n$ denotes the degree of node $v_n$.
    Let $\bfz$ be the eigenvetor of the maximum eigenvalue $\sigma_1(\bfA)$. Since $\sigma_1(\bfA)= \bfD^{-1/2}\widetilde{\bfA}\bfD^{-1/2}$ and $\bfD$ is diagonal matrix, then $\bfz$ is the eigenvector to $\sigma_1(\widetilde{\bfA})$ as well. Then, let $n\in [N]$ be the index of the largest value of vector $\bfz_n$ as $z_n  = \|\bfz\|_{\infty}$, we have
    \begin{equation}
        \sigma_1({\widetilde{\bfA}}) = \frac{(\widetilde{\bfA} \bfz)_n}{z_n}
        = \frac{\widetilde{\bfa}_n^T \bfz}{z_n}
        \le \frac{\|\bfa_n\|_1 \|\bfz\|_{\infty}}{z_n}
        = 1 + \delta.
    \end{equation}
    where $\widetilde{\bfa}_n$ is the $n$-th row of $\widetilde{\bfA}$.

    Since $\bfD$ is a diagonal matrix with $\|\bfD \|_2 \le 1+\delta$, then we can conclude the inequality in this lemma.
\end{proof}

\section{Proof of Lemma \ref{Thm: initialization}}\label{Sec: Proof of initialization}
{The proof of Lemma \ref{Thm: initialization} is divided into three major  parts to bound $I_1$, $I_2$ and $I_3$ in \eqref{eqn: temppppp}. Lemmas \ref{Lemma: M_2}, \ref{Lemma: M_3} and \ref{Lemma: M_1} provide the error bounds for  $I_1$, $I_2$ and $I_3$, respectively. The proofs of these preliminary lemmas are similar to those of Theorem 5.6 in \cite{ZSJB17}, the difference is to apply Lemma \ref{Lemma: partial_independent_var} plus Chernoff inequality  instead of standard Hoeffding inequality, and we skip the details of the proofs of Lemmas \ref{Lemma: M_2}, \ref{Lemma: M_3} and \ref{Lemma: M_1} here.
\begin{lemma}\label{Lemma: M_2}
	Suppose $\bfM_{2}$ is defined as in \eqref{eqn: M_2} and $\widehat{\bfM}_{2}$ is the estimation of $\bfM_{2}$ by samples. Then, with probability
	$1-N^{-10}$, we have
	\begin{equation}
	\|\widehat{\bfM}_{2}-\bfM_{2}\| \lesssim \sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)d\log N}{|\Omega|}},
	\end{equation}
	provided that $|\Omega|\gtrsim(1+\delta^2) d\log^4 N$.
\end{lemma}

\begin{lemma}\label{Lemma: M_3}
	Let $\widehat{\bfV}$ be generated by step 4 in Subroutine 1. Suppose $\bfM_{3}(\widehat{\bfV},\widehat{\bfV},\widehat{\bfV})$ is defined as in \eqref{eqn: M_3_v1} and $\widehat{\bfM}_{3}(\widehat{\bfV},\widehat{\bfV},\widehat{\bfV})$ is the estimation of $\bfM_{3}(\widehat{\bfV},\widehat{\bfV},\widehat{\bfV})$ by samples.
	Further, we assume $\bfV\in\mathbb{R}^{d \times K}$ is an orthogonal basis of $\bfW^*$ and satisfies $\| \bfV\bfV^T - \widehat{\bfV}\widehat{\bfV}^T \|\le 1/4$.
	Then, provided that $N \gtrsim K^5 \log^6d$, with probability at least
	$1-N^{-10}$,  we have
	\begin{equation}
	\begin{split}
	\|\widehat{\bfM}_{3}(\widehat{\bfV},\widehat{\bfV},\widehat{\bfV})-\bfM_{3}(\widehat{\bfV},\widehat{\bfV},\widehat{\bfV})\|
	\lesssim \sigma_1^2(\bfA)\sqrt{\frac{(1+\delta^2)K^3\log N}{|\Omega|}}.
	\end{split}
	\end{equation}
\end{lemma}
\begin{lemma}\label{Lemma: M_1}
	Suppose $\bfM_{1}$ is defined as in \eqref{eqn: M_1} and $\widehat{\bfM}_{1}$ is the estimation of $\bfM_{1}$ by samples. Then, with probability
	$1-N^{-10}$, we have
	\begin{equation}
	\|\widehat{\bfM}_{1}-\bfM_{1}\| \lesssim  \sigma_{1}^2(\bfA) \sqrt{\frac{(1+\delta^2)d\log N}{|\Omega|}}
	\end{equation}
	provided that $|\Omega| \gtrsim (1+\delta^2) d \log^4 N$.
\end{lemma}

\begin{lemma}[\cite{ZSJB17}, Lemma E.6]\label{Lemma: subspace_error}
	Let $\bfV\in\mathbb{R}^{d \times K}$ be an orthogonal basis of $\bfW^*$ and $\widehat{\bfV}$ be generated by step 4 in Subroutine 1. Assume $\|\widehat{\bfM}_{2}-\bfM_{2} \|_2 \le \sigma_{K}(\bfM_{2})/10$. Then, for some small $\varepsilon_0$, we have
	\begin{equation}
	\|\bfV\bfV^T -\widehat{\bfV}\widehat{\bfV}^T \|_2 \le \frac{\|\bfM_{2} -\widehat{\bfM}_{2} \|}{\sigma_{K}(\bfM_{2})}.
	\end{equation}
\end{lemma}
\begin{lemma}[\cite{ZSJB17}, Lemma E.13]\label{Lemma: first_order_solution}
	Let $\bfV\in\mathbb{R}^{d \times K}$ be an orthogonal basis of $\bfW^*$ and $\widehat{\bfV}$ be generated by step 4 in Subroutine 1. Assume $\bfM_{1}$ can be written in the form of \eqref{eqn: M_1} with some homogeneous function $\phi_1$, and let $\widehat{\bfM}_{1}$ be the estimation of $\bfM_{1}$ by samples. Let $\widehat{\bf \alpha}$ be the optimal solution of \eqref{eqn: int_op} with $\widehat{\overline{\bfw}}_j =\widehat{\bfV}\widehat{\bfu}_{j}$. Then, for each $j\in[K]$, if
	\begin{equation}\label{eqn: condition_Lemma_first_order}
	\begin{gathered}
	T_1:=\|\bfV\bfV^T -\widehat{\bfV}\widehat{\bfV}^T \|_2\le \frac{1}{\kappa^2\sqrt{K}},\\
	T_2:=\|\widehat{\bfu}_j -\widehat{\bfV}^T\overline{\bfw}_j \|_2 \le \frac{1}{\kappa^2\sqrt{K}},\\
	T_3:=\|\widehat{\bfM}_{1}-\bfM_{1} \|_2\le \frac{1}{4}\|\bfM_{1} \|_2,
	\end{gathered}
	\end{equation}
	then we have
	\begin{equation}
	\Big| \|\bfw_j\|_2 - \widehat{\alpha}_j \Big|\le \Big(\kappa^4K^{\frac{3}{2}}\big(T_1+T_2\big)+\kappa^2  K^{\frac{1}{2}}T_3\Big)\|\bfW^* \|_2.
	\end{equation}
\end{lemma}
\begin{proof}[Proof of Lemma \ref{Thm: initialization}]
	we have
	\begin{equation}\label{eqn: temppppp}
	\begin{split}
	\|\bfw_j^* -\widehat{\alpha}_j\widehat{\bfV}\widehat{\bfu}_j \|_2
	\le& \Big\| \bfw_j^* -\|\bfw_j \|_2\widehat{\bfV}\widehat{\bfu}_j +\|\bfw_j \|_2\widehat{\bfV}\widehat{\bfu}_j - \widehat{\alpha}_j\widehat{\bfV}\widehat{\bfu}_j\Big\|_2\\
	\le&\Big\| \bfw_j^* -\|\bfw_j \|_2\widehat{\bfV}\widehat{\bfu}_j\|_2 \Big\|_2 \Big\|  \|\bfw_j \|_2\widehat{\bfV}\widehat{\bfu}_j - \widehat{\alpha}_j\widehat{\bfV}\widehat{\bfu}_j\Big\|_2\\
	\le& \|\bfw_j^* \|_2 \| \overline{\bfw}_j^* - \widehat{\bfV}\widehat{\bfu}_j \|_2 +
	\Big| \|\bfw_j\|_2 - \widehat{\alpha}_j \Big\|_2  \|\widehat{\bfV}\widehat{\bfu}_j \|_2\\
	\le &\sigma_{1} \big(\|\overline{\bfw}^*_j - \widehat{\bfV}\widehat{\bfV}^T\overline{\bfw}^*_j \|_2 +  \|\widehat{\bfV}^T\overline{\bfw}^*_j-\widehat{\bfu}_j \|_2 \big)
	+\Big| \|\bfw_j\|_2 - \widehat{\alpha}_j \Big|\\
	:=&\sigma_{1} \big(I_1 +  I_2 \big)
	+I_3.
	\end{split}
	\end{equation}
	From Lemma \ref{Lemma: subspace_error}, we have
	\begin{equation}
	\begin{split}
	I_1
	= \|\overline{\bfw}^*_j - \widehat{\bfV}\widehat{\bfV}^T\overline{\bfw}^*_j \|_2
	\le \|\bfV\bfV^T - \widehat{\bfV}\widehat{\bfV}^T \|_2
	\le \frac{\|\widehat{\bfM}_{2} -\bfM_{2}  \|_2}{\sigma_{K}(\bfM_{2})} ,
	\end{split}
	\end{equation}
	where the last inequality comes from Lemma \ref{Lemma: M_2}.
	Then, from \eqref{eqn: M_2}, we know that
	\begin{equation}
	\sigma_{K}(\bfM_{2})\lesssim  \min_{1\le j \le K} \|\bfw^*_{j} \|_2\lesssim \sigma_{K}(\bfW^*).
	\end{equation}
	From Theorem 3 in \cite{KCL15}, we have
	\begin{equation}
	\begin{split}
	I_2
	=\|\widehat{\bfV}^T\overline{\bfw}^*_j-\widehat{\bfu}_j \|_2
	\lesssim \frac{\kappa}{\sigma_{K}(\bfW^*)}\| \widehat{\bfM}_{3}(\widehat{\bfV}, \widehat{\bfV} , \widehat{\bfV}) - {\bfM}_{3}(\widehat{\bfV}, \widehat{\bfV} , \widehat{\bfV}) \|_2.
	\end{split}
	\end{equation}
	To guarantee the condition \eqref{eqn: condition_Lemma_first_order} in Lemma \ref{Lemma: first_order_solution} hold, according to Lemmas \ref{Lemma: M_2} and \ref{Lemma: M_3}, we need $|\Omega|\gtrsim \kappa^3(1+\delta^2)Kd\log N$.
	Then, from Lemma \ref{Lemma: first_order_solution}, we have
	\begin{equation}
	I_3 = \Big(\kappa^4 K^{3/2}(I_1 + I_2) + \kappa^2 K^{1/2}\|\widehat{\bfM}_{1}-\bfM_{1} \|\Big)\|\bfW^* \|_2.
	\end{equation}
	Since $d\gg K$, according to Lemmas \ref{Lemma: M_2}, \ref{Lemma: M_3} and \ref{Lemma: M_1}, we have
	\begin{equation}
	\|\bfw_j^* -\widehat{\alpha}_j\widehat{\bfV}\widehat{\bfu}_j \|_2\lesssim  \kappa^6 \sigma_{1}^2(\bfA)\sqrt{\frac{K^3(1+\delta^2)d\log N}{|\Omega|}}\|\bfW^* \|_2
	\end{equation}
	provided $|\Omega|\gtrsim (1+\delta^2)d\log^4 N $.
\end{proof}

config: arxiv


TITLE: Complex Analysis Limits
QUESTION [1 upvotes]: Hi there. I am struggling to understand how the this equation is obtained in the working:

How do you approach along a line when working out a limit?
Thanks

REPLY [0 votes]: $\require{cancel}$
We note that functions being differentiable means a certain limit exists. Limits, by their nature, must be the same along every path going through the point if they are to exist at all, so they opt to check the path $y=x$ as one possibility. You work it out by using the facts about the line in question.
On this line they choose $y=x$ so we can replace $y$ with $x$ everywhere in the limit we see it and the limit becomes
$$\lim_{x\to 0}{1\over x+ix}{(1+i)x^3-(1-i)x^3\over x^2+x^2}=\lim_{x\to 0}{1\over x+ix}{x^{\cancel{3}}((1+i)-(1-i))\over 2\cancel{x^2}}$$
$$=\lim_{x\to 0}{2i\cancel{x}\over \cancel{x}(1+i)}=1+i$$
The last equality being easily observed as $(1+i)^2=1^2+2i+i^2=2i$


TITLE: Ordinal multiplication
QUESTION [0 upvotes]: I understand why $(\omega+1)\cdot2 = \omega\cdot2+1$ and why $(\omega+1)\cdot\omega = \omega^2$
What I am struggling with is something along the lines of:
$(\omega\cdot3+4)\cdot3$ which I think is = $\omega\cdot9+4$
And:
$(\omega\cdot3+4)(\omega\cdot3)$ which I think is = $\omega^2\cdot9$
Am I correct?

REPLY [0 votes]: You have evaluated $(\omega\cdot 3+4)\cdot 3$ correctly. However, $(\omega\cdot 3+4)\cdot(\omega\cdot 3)$ is not correctly evaluated. I do not know which step of your evaluation is incorrect, but I guess you think $(\omega\cdot 3)^2$ is $\omega^2\cdot 9$.
This is not true, however, as
$$(\omega\cdot 3)\cdot (\omega\cdot 3) = \omega\cdot (3\cdot\omega)\cdot 3 = \omega^2\cdot 3.$$
The core part of the evaluation is $3\cdot\omega=\omega$ that can be proven in the way of proving $3+\omega =\omega$ (and the linked question in your comment.)
We would think evaluating $(\omega\cdot 3+4)\cdot(\omega\cdot 3)$ is not too different from that of $(\omega\cdot 3)\cdot (\omega\cdot 3)$. The problem is, we have extra $+4$ and we cannot apply the distribution law in the case.
However, the addition in the middle of the expression would disappear when adding $(\omega\cdot 3+4)$ many times, so we can guess the answer is $\omega^2\cdot 3$.
You can make our discussion concretely by following the steps of the proof you have linked; that is, use the transfinite induction for $\beta\le \omega\cdot 3$ to prove
$$(\omega\cdot 3+4)\cdot\beta = \begin{cases}
\omega\cdot (3\cdot\beta) &\text{if $\beta$ is a limit ordinal,} \\ \omega\cdot (3\cdot\beta) + 4 & \text{if $\beta$ is a successor ordinal.}\end{cases}$$


TITLE: Why was $\vec{A}\cdot\vec{B}$ defined as $|\vec{A}||\vec{B}|\cos \theta$?
QUESTION [3 upvotes]: Why was $\vec{A}\cdot\vec{B}$ defined as $|\vec{A}||\vec{B}|\cos \theta$? Historically what is the underlying idea?

REPLY [0 votes]: Because it is fundamentally linked to the solution of practical problems in mathematics and physics.  In physics we often find ourselves needing to decompose a vector into components.  For example when we think about acceleration as a vector, we are often concerned with its components in the tangential and normal directions.  The dot product helps us do that.  The dot product also shows up in the definition of work and flux.  In mathematics it is prevalent in linear algebra as well as vector algebra and vector calculus (Divergence Theorem, Stokes Theorem).  Because the idea of projection appears in so many places, it warranted its own definition and notation.


TITLE: Something Being True in the Limit as Something Else Goes to Zero
QUESTION [1 upvotes]: In general, my question is: what do we mean when we say that a mathematical statement is true only in the limit as $x$ goes to $0$?

For example, if the velocity $v$ of a particle is a function of time $t$, then the particle has different velocities at different instants of time. But, we say that $\Delta s=v\Delta t$, where is $\Delta s$ is the distance traveled, is true only if the velocity is not changing during that time interval, and this condition is only true in the limit as $\Delta t$ goes to zero.
How can the condition that the velocity is not changing in the interval $\Delta t$ be true when the velocity is different at different instants of time? Since I am not able to understand how the velocity can be constant (maybe it is approximately constant) for an interval $\Delta t$ as it goes to zero, therefore I think I don't really understand generally what we mean when we say that something is true only in the limit as something else goes to zero.

REPLY [3 votes]: This phrasing is not completely rigorous. In general when someone says that $f(x)=g(x)$ in the limit $x\to 0$, they mean something like
$$ \lim_{x\to 0}\frac{f(x)}{g(x)}=1 \qquad\text{or}\qquad
\lim_{x\to 0}(f(x)-g(x))=0 $$
but these conditions are different, and it is possible for two functions $f$ and $g$ to satisfy one of them but not the other (or vice versa).
In general the meaning is that $f(x)$ and $g(x)$ may not be exactly equal, but they can be made to be as "close to each other" (in some appropriate sense) as you want to by selecting $x$ sufficiently small.

Judging from your choice of example, I think what you need might be a good introductory calculus textbook ...


text:
{\bf Problem.} Find
\[\sum_{N = 1}^{1024} \lfloor \log_2 N \rfloor.\]
{\bf Level.} Level 4
{\bf Type.} Intermediate Algebra
{\bf Solution.} For $1 \le N \le 1024,$ the possible values of $\lfloor \log_2 N \rfloor$ are 0, 1, 2, $\dots,$ 10.  For a given value of $k,$ $0 \le k \le 10,$
\[\lfloor \log_2 N \rfloor = k\]for $N = 2^k,$ $2^{k + 1},$ $\dots,$ $2^{k + 1} - 1,$ for $2^k$ possible values.  The only exception is $k = 10$: $\lfloor \log_2 N \rfloor = 10$ only for $N = 1024.$

Hence, the sum we seek is
\[S = 1 \cdot 0 + 2 \cdot 1 + 2^2 \cdot 2 + 2^3 \cdot 3 + \dots + 2^8 \cdot 8 + 2^9 \cdot 9 + 10.\]Then
\[2S = 2 \cdot 0 + 2^2 \cdot 1 + 2^3 \cdot 2 + 2^4 \cdot 3 + \dots + 2^9 \cdot 8 + 2^{10} \cdot 9 + 20.\]Subtracting these equations, we get
\begin{align*}
S &= 10 + 2^{10} \cdot 9 - 2^9 - 2^8 - \dots - 2^2 - 2 \\
&= 10 + 2^{10} \cdot 9 - 2(2^8 + 2^7 + \dots + 2 + 1) \\
&= 10 + 2^{10} \cdot 9 - 2(2^9 - 1) \\
&= \boxed{8204}.
\end{align*}

set_name: MATH


TITLE: Why is there a negative sign in the (non-relativistic) bivector formulation of the Lorentz force?
QUESTION [2 upvotes]: I'm currently trying to update my understanding of basic (Newtonian, non-relativistic) physics to use bivectors and Clifford products instead of pseudovectors and cross products. And I've come up against that most famous use of cross products, magnetic fields.
In the cross product formulation, the B-field is a pseudovector, and the force it exerts on a moving charged particle is $\vec{F}_{mag} = q \vec{v} \times \vec{B}$ .
In the bivector formulation, the B-field is a bivector, and the force it exerts on a moving charged particle is $\vec{F}_{mag} = -q\vec{v} \vee \mathbf{B}$ (where $\vee$ is the inner product).
Where does this extra negative sign come from? Why doesn't it show up in the cross product formulation?

REPLY [3 votes]: This is something I'm personally also trying to understand better, but here is something that might help. I was able to derive the minus sign by starting with the bivector and then deriving the usual $\vec{B}$ pseudovector field from that. Since I start by assuming the bivector is positive, I get the result that the pseudovector points in the "opposite sense", leading to a negative sign. If you turn my derivation backwards, assuming that the pseudovector is the positive one instead, you should get the formula you have.
First, I assume that there is a magnetic bivector $\textbf{B}$ which is written out with a right-handed bivector basis with scalar components $B^i$ (not to be confused with the pseudovector's components $\vec{B}^i$):
$\textbf{B} = B^1e_{23} + B^2e_{31} + B^3e_{12}$
This bivector is chosen to create a Lorentz force law which does not have a minus sign in it.
$\vec{F}_{mag}=q\vec{v}\vee\textbf{B}$
What will be shown is that this assumption leads to the cross-product-pseudovector version acquiring a minus sign,
$\vec{F}_{mag}=-q\vec{v}\times\vec{B}$
Which means that if you take $\vec{B}$ as the "starting point" instead, then the signs on both equations will flip and we'll get your version of the bivector force law that has a minus sign in it. I apologize for the "backwards" nature of this proof, but it helped me get a better handle on it because pseudovectors are imho less intuitive to work with than bivectors.
The key equation is this:
$\omega\textbf{B}=-B^ie_i=\vec{B}^ie_i=\vec{B}$
where $\omega=e_1e_2e_3$ is the pseudoscalar of 3-space. Let's work out the algebra to see how this is true.
$$
\omega\textbf{B}=e_1e_2e_3(B^1e_{23} + B^2e_{31} + B^3e_{12})
\\
= e_1e_2e_3(B^1e_{23}) + e_1e_2e_3(B^2e_{31}) + e_1e_2e_3(B^3e_{12})
\\
= B^1e_1e_2e_3(e_{23}) + B^2e_1e_2e_3(e_{31}) + B^3e_1e_2e_3(e_{12})
$$
We are free to permute the vectors making up $\omega$ as long as they stay in the same $1\rightarrow2\rightarrow3$ order, so
$$
B^1e_1e_2e_3(e_{23}) + B^2e_1e_2e_3(e_{31}) + B^3e_1e_2e_3(e_{12})
\\=B^1e_1e_2e_3(e_{23}) + B^2e_2e_3e_1(e_{31}) + B^3e_3e_1e_2(e_{12})
$$
$e_ie_j(e_ie_j)=-e_ie_je_je_i=-e_ie_i=-1$, so
$$
B^1e_1e_2e_3(e_{23}) + B^2e_2e_3e_1(e_{31}) + B^3e_3e_1e_2(e_{12})\\=-B^1e_1 - B^2e_2 - B^3e_3
$$
This expression is a vector, "$-B^ie_i$", whose vector-components (coefficients tacked onto basis vectors $e_i$) are expressed in terms of the bivector's components ($B^i$, which are just scalars). You'll note the minus sign in front. You have two options on how you interpret this. For now, we will define the "usual" pseudovector field $\vec{B}$ to include this minus sign (relative to the original bivector components).
$$
\vec{B}\equiv\vec{B}^ie_i\equiv-B^ie_i
$$
To be totally explicit, we're saying that the (scalar) components of the geometrical object "pseudovector $\vec{B}$", which we label $\vec{B}^i$, are each defined to have the numerical value found by evaluating the scalar expression "$-1\cdot B^i$". Where $B^i$ is, as always, "the coefficients of the $e_{23}$, $e_{31}$, and $e_{12}$ that add up to make up the geometrical object that is the bivector $\textbf{B}$".
So, now we've seen that $\omega\textbf{B}=\vec{B}$ ... in essence we can "convert" from $\textbf{B}$ to $\vec{B}$ with this formula. If we have a bivector, we can find its corresponding pseudovector. What about the other way around? Well, let's do the algebra.
$$
\omega\vec{B}=e_1e_2e_3(\vec{B}^1e_{1} + \vec{B}^2e_{2} + \vec{B}^3e_{3})
\\=e_1e_2e_3(\vec{B}^1e_{1}) + e_1e_2e_3(\vec{B}^2e_{2}) + e_1e_2e_3(\vec{B}^3e_{3})
\\=\vec{B}^1e_1e_2e_3(e_{1}) + \vec{B}^2e_1e_2e_3(e_{2}) + \vec{B}^3e_1e_2e_3(e_{3})
\\=\vec{B}^1e_2e_3e_1(e_{1}) + \vec{B}^2e_3e_1e_2(e_{2}) + \vec{B}^3e_1e_2e_3(e_{3})
\\=\vec{B}^1e_2e_3 + \vec{B}^2e_3e_1 + \vec{B}^3e_1e_2
\\
(\vec{B}^i\equiv-B^i)
\\
=-B^1e_2e_3 - B^2e_3e_1 - B^3e_1e_2
\\=-\textbf{B}
$$
In summary,
$$
\omega\vec{B}=-\textbf{B}
\\
\omega\textbf{B}=\vec{B}
$$
This relationship is the source of the "opposite sense" between the bivector field and the pseudovector one. Now that we have this fact, we are almost ready to recover your equation in the form you have it.
Continuing to stick with the assumption that $\textbf{B}$ is the "default" which leads to the following force law
$\vec{F}_{mag}=q\vec{v}\vee\textbf{B}$
Using the equation we found above, $\omega\vec{B}=-\textbf{B}$, we find that $-\omega\vec{B}=\textbf{B}$, so let's substitute that into our force law:
$\vec{F}_{mag}=q\vec{v}\vee(-\omega\vec{B})$
We can move that minus sign out front:
$\vec{F}_{mag}=-q\vec{v}\vee(\omega\vec{B})$
And re-use our definitions for "converting":
$$
\omega\vec{B}=-\textbf{B}
\\
\vec{F}_{mag}=-q\vec{v}\vee(-\textbf{B})
$$
Seems redundant? Well, now we can finally make our conclusion. Remember how I did this all "backwards", starting by assuming the bivector $\textbf{B}$ is positive. However, by the definition of $\vec{B}$, you can see it's just as valid to assume that $\vec{B}$'s components are positive, and $\textbf{B}$ is the negative one:
$$
\vec{B}\equiv\vec{B}^ie_i=-B^ie_i
\\
\therefore B^ie_i=-\vec{B}^ie_i
$$
So if we apply that to our "redundant" force law we get
$$
\vec{F}_{mag}=-q\vec{v}\vee(\textbf{B})
$$
instead, which was the result to be shown. In short, the reason this "extra minus sign" shows up is because assuming that the cross-product is the "default" law with a positive sign entails that the bivector formula must have a minus sign to "make up for" the minus sign that appears when you "convert" between the axial vector/pseudovector $\vec{B}$ and the corresponding bivector $\textbf{B}$.
I worry that my notation and especially the sign-flipping might end up confusing more than it clears up, but all the same, at the very least I've shown you some of the reason why there is always a minus sign difference between the bivector and pseudovector versions of the magnetic force law. Hope it helps!