text:
\section{Proofs of Lemmas in Section~\ref{section:algorithm}}\label{section:appendix_proof_1}

\subsection{Proof of Lemma~\ref{lemma:psidefinition}}
We first present the following lemma. The proof is given in Appendix~\ref{section:appendix_proof_3}.
\begin{lemma}\label{lemma:monotonecovineq}
Let $f(z)$ and $g(z)$ be two non-trivial increasing functions. Let $Z_1$ and $Z_2$ be zero-mean jointly Gaussian random variables. If $\Var(Z_1) = \Var(Z_2) = 1$ and $\theta = \Cov (Z_1,Z_2)  > 0$, then $\Cov[f(Z_1),g(Z_2)]$ is an increasing function of $\theta$, and we have $\Cov[f(z_1),g(z_2)] > 0$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lemma:psidefinition}]
Since $\Cov(\wb^\top \bZ, \wb'^{\top} \bZ) = \wb^\top \wb'$, by Lemma~\ref{lemma:monotonecovineq} we know there exists an increasing function $\psi(\tau)$ such that $\psi(\wb^\top \wb') = \phi(\wb , \wb')$ and $\psi(\tau) >0$ for $\tau>0$. $\psi(\tau) \leq \Delta$ follows directly by Cauchy-Schwarz inequality.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:boundedconstant}}
\begin{proof}[Proof of Lemma~\ref{lemma:boundedconstant}]
For $M$, if $\kappa=0$ it is obvious that $M=0$. If $\kappa \neq 0$, we have
\begin{align*}
    \frac{|\kappa| (2L|\mathbf{1}^\top \vb^*| + \sqrt{k})}{\Delta + \kappa^2k} \leq \frac{|\kappa| (2L|\mathbf{1}^\top \vb^*| + \sqrt{k})}{\kappa^2k} \leq \frac{ (2L|\mathbf{1}^\top \vb^*| + 1)}{|\kappa|}.
\end{align*}
This upper bound if $M$ does not depend on $k$.

For $D$, since we assume that $\alpha \leq 1/(8\Delta)$, it suffices to show that $\kappa^2 M^2 k$ is bounded. Similar to the bound of $M$, if $\kappa = 0$ clearly $\kappa^2 M^2 k$. If $\kappa \neq 0$, we have
\begin{align*}
    \kappa^2 k \cdot \bigg[\frac{|\kappa| (2L|\mathbf{1}^\top \vb^*| + \sqrt{k})}{\Delta + \kappa^2k}\bigg]^2 \leq \kappa^2 k \cdot \bigg[\frac{|\kappa|\sqrt{k} (2L|\mathbf{1}^\top \vb^*| + 1)}{\kappa^2k}\bigg]^2 = (2L|\mathbf{1}^\top \vb^*| + 1)^2.
\end{align*}
Therefore $D$ has an upper bound that only depends on the choice of activation function $\sigma(\cdot)$, the ground-truth parameters $(\wb^*,\vb^*)$ and the initialization $(\wb^0,\vb^0)$. The results for $D_0$ and $\rho$ are obvious.
\end{proof}

\section{Proofs of Results in Section~\ref{section:proofmain}}\label{section:appendix_proof_2}
In this section we give the proofs of the claims and lemmas used in Section~\ref{section:proofmain}.
\subsection{Proof of Claim~\ref{claim:expectationcalculation}}
\begin{proof}[Proof of Claim~\ref{claim:expectationcalculation}]
Note that for any $i=1,\ldots, n$, $\Pb_j \xb_i$, $j=1,\ldots,k$ are independent standard Gaussian random vectors. Therefore we have
$ v_j \sigma(\wb^{\top} \Pb_j \xb_i) \cdot \xi^{-1} v_{j'} \Pb_{j'} \xb_i =0$ for $j'\neq j$. Moreover, suppose that $\zb$ is a standard Gaussian random vector. Let $\tilde\wb_1,\ldots, \tilde\wb_{r-1}$ be a set of orthonormal vectors orthogonal to $\wb$, then we have
\begin{align*}
    \EE_{\zb} [ \sigma(\wb^{\top} \zb) \zb ] &= \EE_{\zb} [ \sigma(\wb^{\top} \zb) \cdot (\wb^{\top} \zb) ] \cdot \wb + \sum_{j=1}^{r-1}\EE_{\zb} [ \sigma(\wb^{\top} \zb) \cdot (\wb_j^{\top} \zb) ] \cdot \wb_j\\
    &= \EE_{\zb} [ \sigma(\wb^{\top} \zb) \cdot (\wb^{\top} \zb) ] \cdot \wb\\
    &= \xi\cdot \wb,
\end{align*}
where the second equality follows by the fact that $\wb_j^{\top} \zb$, $j=1,\ldots, r-1$ are independent of $\wb^{\top} \zb$ and have mean $0$. Note that this argument for $\wb$ also works for $\wb^*$. Therefore, we have
\begin{align*}
    \EE[\gb_w(\wb,\vb) ]&= - \frac{1}{n} \sum_{i=1}^n \EE\Bigg\{  \Bigg[y_i -
\sum_{j=1}^k v_j \sigma(\wb^{\top} \Pb_j \xb_i)\Bigg]\cdot \sum_{j'=1}^k \xi^{-1} v_{j'} \Pb_{j'} \xb_i \Bigg\}\\
& = - \frac{1}{n} \sum_{i=1}^n \EE\Bigg\{  \Bigg[\sum_{j=1}^k v_j^* \sigma(\wb^{*\top} \Pb_j \xb_i) -
\sum_{j=1}^k v_j \sigma(\wb^{\top} \Pb_j \xb_i)\Bigg]\cdot \sum_{j'=1}^k \xi^{-1} v_{j'} \Pb_{j'} \xb_i \Bigg\}\\
&= - \Bigg( \sum_{j=1}^k v_j^* v_j \wb^* - \sum_{j=1}^k v_j^2 \wb \Bigg)\\
&=\overline{\gb}_w(\wb,\vb).
\end{align*}
This proves the first result. The second identity $\EE[\gb_v(\wb,\vb)] = \overline{\gb}_v(\wb,\vb)$ directly follows by the definition.
\end{proof}
\subsection{Proof of Lemma~\ref{lemma:smoothness_all}}
\begin{proof}[Proof of Lemma~\ref{lemma:smoothness_all}]
Define
\begin{align*}
    &H_{ww}:=\sup_{\substack{ \wb,\wb'\in \cW_0 \\ \vb\in\cV_0}} \frac{\| \gb_w(\wb,\vb) - \gb_w(\wb',\vb) \|_2  }{\| \wb - \wb' \|_2}, &
    &H_{wv} : = \sup_{ \substack{ \vb,\vb'\in \cV_0\\ \wb \in \cW_0}} \frac{\|\gb_w(\wb,\vb) - \gb_w(\wb,\vb')\|_2 }{\| \vb - \vb' \|_2},\\
    &H_{vw} : = \sup_{ \substack{\wb,\wb' \in \cW_0\\ \vb
    \in \cV_0}} \frac{\|\gb_v(\wb,\vb) - \gb_v(\wb',\vb)\|_2 }{\| \wb - \wb' \|_2},&
    &H_{vv} : = \sup_{ \substack{ \vb, \vb'
    \in \cV_0 \\ \wb \in \cW_0}} \frac{\|\gb_v(\wb,\vb) - \gb_v(\wb,\vb')\|_2 }{\| \vb - \vb' \|_2}.
\end{align*}
For any $\delta_1,\ldots,\delta_5>0$, we first give the following lemmas.
\begin{lemma}\label{lemma:uniformbound1}
If $n \geq (r+k)\log(34/\delta_1)$, then with probability at least $1-\delta_1$, we have
\begin{align*}
    \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} \frac{1}{n}\sum_{i=1}^n  \sum_{j=1}^k  |b_j\ab^\top \Pb_j\xb_i|  \cdot  \Bigg| \sum_{j'=1}^k b_{j'}'\ab'^\top \Pb_{j'}\xb_i \Bigg|  \leq C \sqrt{k},
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

\begin{lemma}\label{lemma:uniformbound2}
If $n \geq (r+k)\log(68/\delta_2)$, then with probability at least $1-\delta_2$, we have
\begin{align*}
    \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} \frac{1}{n}\sum_{i=1}^n  \sum_{j=1}^k  b_j \sigma(\ab^\top \Pb_j\xb_i)  \cdot   \sum_{j'=1}^k b_{j'}'\ab'^\top \Pb_{j'}\xb_i   \leq C L \sqrt{k} ,
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

\begin{lemma}\label{lemma:uniformbound2.5}
If $n \geq (r+k)\log(34/\delta_3)$, then with probability at least $1-\delta_3$, we have
\begin{align*}
    \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} \frac{1}{n}\sum_{i=1}^n  \sum_{j=1}^k | b_j \ab^\top \Pb_j\xb_i |  \cdot   \sum_{j'=1}^k | b_{j'}' \ab'^\top \Pb_{j'}\xb_i |   \leq C k,
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

\begin{lemma}\label{lemma:uniformbound3}
If $n \geq (r+k)\log(68/\delta_4)$, then with probability at least $1-\delta_4$, we have
\begin{align*}
    \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} \frac{1}{n}\sum_{i=1}^n  \sum_{j=1}^k | b_j \ab^\top \Pb_j\xb_i |  \cdot   \sum_{j'=1}^k | b_{j'}' \sigma(\ab'^\top \Pb_{j'}\xb_i) |   \leq C L k,
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

\begin{lemma}\label{lemma:uniformbound4}
If $n \geq (r+k)\log(102/\delta_5)$, then with probability at least $1-\delta_5$, we have
\begin{align*}
    \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} \frac{1}{n}\sum_{i=1}^n  \sum_{j=1}^k  b_j \sigma(\ab^\top \Pb_j\xb_i)  \cdot   \sum_{j'=1}^k b_{j'}' \sigma(\ab'^\top \Pb_{j'}\xb_i)   \leq C L^2  k,
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

\begin{lemma}\label{lemma:uniformbound5}
If $n \geq (r+k)\log(18/\delta_6)$, then with probability at least $1-\delta_6$, we have
\begin{align*}
    \sup_{\substack{\ab \in S^{r-1}\\ \mathbf{b} \in S^{k-1}}} \frac{1}{n}\sum_{i=1}^n  \epsilon_i  \cdot \sum_{j=1}^k b_{j}\ab^\top \Pb_{j}\xb_i  \leq C\nu,
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

\begin{lemma}\label{lemma:uniformbound6}
If $n \geq (r+k)\log(18/\delta_7)$, then with probability at least $1-\delta_7$, we have
\begin{align*}
    \sup_{\substack{\ab \in S^{r-1}\\ \mathbf{b} \in S^{k-1}}} \frac{1}{n}\sum_{i=1}^n  |\epsilon_i|  \cdot \sum_{j=1}^k |b_{j}\ab^\top \Pb_{j}\xb_i|  \leq C\nu\sqrt{k},
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

Let $\delta_1 = \delta/9$, $\delta_2 = \delta_4 = 2\delta/9$, $\delta_5 = \delta/3$ and $\delta_6 = \delta_7 = \delta/18$. Then we have $\delta_1 + \delta_2 + \delta_4 + \delta_5 + \delta_6 + \delta_7 = \delta$. By union bound and the assumption that $n \geq (r+k)\log(324/\delta)$, with probability at least $1-\delta$, the results of Lemmas~\ref{lemma:uniformbound1}, \ref{lemma:uniformbound2}, \ref{lemma:uniformbound3}, \ref{lemma:uniformbound4}, \ref{lemma:uniformbound5}, and \ref{lemma:uniformbound6} all hold.
We are now ready to prove \eqref{eq:smoothness_ww}-\eqref{eq:smoothness_vv}.

\noindent\textbf{Proof of \eqref{eq:smoothness_ww}}.
By Assumption~\ref{assump:1Lipschitz} and Lemma~\ref{lemma:uniformbound1} we have
\begin{align*}
    H_{ww} &= \sup_{\ab\in S^{r-1},\vb\in\cV_0}\frac{|\ab^\top[\gb_w(\wb,\vb) - \gb_w(\wb',\vb)]|}{\|\wb - \wb^*\|_2}\\
    &\leq\sup_{\ab\in S^{r-1},\vb\in\cV_0} \xi^{-1}\|\vb\|_2^2\cdot\frac{1}{n}\sum_{i=1}^{n} \sum_{j=1}^k \bigg| \frac{v_j}{\|\vb\|_2} \frac{(\wb - \wb')^\top}{\|\wb - \wb'\|_2} \Pb_j \xb_i \bigg| \cdot \Bigg| \sum_{j'=1}^k \frac{v_{j'}}{\|\vb\|_2}\ab^\top \Pb_j \xb_i\Bigg|\\
    &\leq C_1 \xi^{-1} D_0^2 \sqrt{k},
\end{align*}
where $C_1$ is an absolute constant.

\noindent\textbf{Proof of \eqref{eq:smoothness_wv}}
For any $\ab \in S^{r-1},$ by definition we have
\begin{align*}
    \ab^\top [\gb_w(\wb,\vb) - \gb_w(\wb,\vb')] = I_1  + I_2 + I_3 + I_4,
\end{align*}
where
\begin{align*}
&I_1 = -\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k v_j^* \sigma(\wb^{*\top} \Pb_j \xb_i)
 \sum_{j'=1}^k \xi^{-1} (v_{j'} - v'_{j'}) \ab^\top \Pb_{j'} \xb_i,\\
 &I_2 = \frac{1}{n} \sum_{i=1}^n
\sum_{j=1}^k (v_j - v'_j) \sigma(\wb^{\top} \Pb_j \xb_i)\cdot \sum_{j'=1}^k \xi^{-1} v_{j'} \ab^\top \Pb_{j'} \xb_i,\\
&I_3 = \frac{1}{n} \sum_{i=1}^n
\sum_{j=1}^k v'_j \sigma(\wb^{\top} \Pb_j \xb_i)\cdot \sum_{j'=1}^k \xi^{-1} ( v_{j'} - v'_{j'}) \ab^\top \Pb_{j'} \xb_i,\\
&I_4 = -\frac{1}{n} \sum_{i=1}^n \epsilon_i
 \sum_{j'=1}^k \xi^{-1} (v_{j'} - v'_{j'}) \ab^\top \Pb_{j'} \xb_i.
\end{align*}
By Lemma~\ref{lemma:uniformbound2} and Lemma~\ref{lemma:uniformbound5} we have
\begin{align*}
    &I_1 \leq C_2 \xi^{-1} L\sqrt{k}  \|\vb^*\|_2 \| \vb - \vb' \|_2,\\
    &I_2,I_3\leq C_2D_0 \xi^{-1}L\sqrt{k} \| \vb - \vb' \|_2,\\
    &I_4 \leq C_2 \nu \xi^{-1} \| \vb - \vb' \|_2
\end{align*}
for all $\ab\in S^{r-1}$, $\wb \in \cW_0$ and $\vb,\vb'\in \cV_0$, where $C_2$ is an absolute constant. Since $2\|\vb^*\|_2 + D_0 \leq 3D_0$, we have
\begin{align*}
    H_{wv} = \sup_{ \substack{\ab \in S^{r-1}, \wb\in \cW_0\\ \vb,\vb'\in \cV_0}} \frac{\ab^\top [\gb_w(\wb,\vb) - \gb_w(\wb,\vb')]}{\| \vb - \vb' \|_2} \leq C_3\xi^{-1}(\nu + D_0L\sqrt{k}),
\end{align*}
where $C_3$ is an absolute constant.

\noindent\textbf{Proof of \eqref{eq:smoothness_vw}}
By definition we have
\begin{align*}
    H_{vw} &= \sup_{ \substack{ \ab \in S^{k-1}, \vb
    \in \cV_0\\ \wb,\wb' \in \cW_0}} \frac{\ab^\top [\gb_v(\wb,\vb) - \gb_v(\wb',\vb)] }{\| \wb - \wb' \|_2}\\
    &= \sup_{ \substack{ \ab \in S^{k-1}, \vb
    \in \cV_0\\ \wb,\wb' \in \cW_0}} -\frac{\ab^\top \{ [\bSigma (\wb) - \bSigma (\wb')]^\top \yb + [\bSigma^\top (\wb)\bSigma (\wb) - \bSigma^\top (\wb')\bSigma (\wb')]\vb \}}{n \| \wb - \wb'\|_2}\\
    &\leq   I'_1 +  I'_2 + I'_3,
\end{align*}
where
\begin{align*}
    &I'_1 = \sup_{ \substack{ \ab \in S^{k-1}, \\ \wb,\wb' \in \cW_0}} -\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k \frac{a_j [\sigma(\wb^\top \Pb_j\xb_i) - \sigma(\wb'^\top \Pb_j\xb_i)]}{\| \wb - \wb'\|_2}\cdot \sum_{j'=1}^k v_{j'}^* \sigma(\wb^{*\top} \Pb_{j'}\xb_i),\\
    &I'_2 = \sup_{ \substack{ \ab \in S^{k-1}, \vb
    \in \cV_0 \\ \wb,\wb' \in \cW_0}} -\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k a_j \sigma(\wb^\top \Pb_j\xb_i)\cdot \sum_{j'=1}^k \frac{v_{j'} [\sigma(\wb^{\top} \Pb_{j'}\xb_i) - \sigma(\wb'^{\top} \Pb_{j'}\xb_i)]}{\| \wb - \wb' \|_2},\\
    &I'_3 = \sup_{ \substack{ \ab \in S^{k-1}, \vb
    \in \cV_0 \\ \wb,\wb' \in \cW_0}} -\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k \frac{a_j [\sigma(\wb^\top \Pb_j\xb_i) - \sigma(\wb'^\top \Pb_j\xb_i)]}{\|  \wb - \wb' \|_2}\cdot \sum_{j'=1}^k v_{j'} \sigma(\wb'^{\top} \Pb_{j'}\xb_i),\\
    &I'_4 = \sup_{ \substack{ \ab \in S^{k-1}, \\ \wb,\wb' \in \cW_0}} -\frac{1}{n} \sum_{i=1}^n \epsilon_i\cdot \sum_{j=1}^k \frac{a_j [\sigma(\wb^\top \Pb_j\xb_i) - \sigma(\wb'^\top \Pb_j\xb_i)]}{\| \wb - \wb'\|_2}.
\end{align*}
Therefore by the Lipschitz continuity of $\sigma(\cdot)$, Lemma~\ref{lemma:uniformbound3} and Lemma~\ref{lemma:uniformbound6}, we have
\begin{align*}
    &I'_1 \leq \sup_{ \substack{ \ab \in S^{k-1}, \\ \wb,\wb' \in \cW_0}} \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k \bigg|a_j \frac{(\wb - \wb')^\top}{\|\wb-\wb'\|_2} \Pb_j\xb_i\bigg|\cdot \sum_{j'=1}^k |v_{j'}^* \sigma(\wb^{*\top} \Pb_{j'}\xb_i)| \leq C_4  L k \| \vb^*\|_2  ,\\
    &I'_2 \leq \sup_{ \substack{ \ab \in S^{k-1}, \vb
    \in \cV_0 \\ \wb,\wb' \in \cW_0}} \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k |a_j \sigma(\wb^\top \Pb_j\xb_i)|\cdot \sum_{j'=1}^k \bigg|v_{j'} \frac{(\wb - \wb')^\top}{\|\wb-\wb'\|_2} \Pb_{j'}\xb_i\bigg| \leq  C_4  L D_0 k,\\
    &I'_3 \leq \sup_{ \substack{ \ab \in S^{k-1}, \vb
    \in \cV_0 \\ \wb,\wb' \in \cW_0}} \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k \bigg|a_j \frac{(\wb - \wb')^\top}{\|\wb-\wb'\|_2} \Pb_j\xb_i\bigg|\cdot \sum_{j'=1}^k |v_{j'} \sigma(\wb'^{\top} \Pb_{j'}\xb_i)|\leq C_4  L D_0 k,\\
    &I'_4 \leq \sup_{ \substack{ \ab \in S^{k-1}, \\ \wb,\wb' \in \cW_0}} \frac{1}{n} \sum_{i=1}^n |\epsilon_i|\cdot \sum_{j=1}^k \bigg|a_j \frac{(\wb - \wb')^\top}{\|\wb-\wb'\|_2} \Pb_j\xb_i\bigg| \leq C_4 \nu \sqrt{k} ,
\end{align*}
where $C_4$ is an absolute constant. Since $\| \vb^* \|_2 \leq D_0$, we have
\begin{align*}
    H_{vw} \leq C_5 ( \nu +  D_0 L \sqrt{k})\sqrt{k},
\end{align*}
where $C_5$ is an absolute constant.

\noindent\textbf{Proof of \eqref{eq:smoothness_vv}}
By Lemma~\ref{lemma:uniformbound4} we have
\begin{align*}
    H_{vv} &= \sup_{ \substack{ \ab \in S^{k-1}, \wb \in \cW_0\\ \vb, \vb'
    \in \cV_0}} \frac{\ab^\top [\gb_v(\wb,\vb) - \gb_v(\wb,\vb')] }{\| \vb - \vb' \|_2}\\
    &= \sup_{ \substack{ \ab \in S^{k-1}, \wb \in \cW_0\\ \vb, \vb'
    \in \cV_0}} -\frac{\ab^\top \bSigma^\top(\wb)\bSigma(\wb)(\vb -\vb') }{n\| \vb - \vb' \|_2}\\
    &=\sup_{ \substack{ \ab \in S^{k-1}, \wb \in \cW_0\\ \vb, \vb'
    \in \cV_0}} -\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^k a_j \sigma(\wb^\top \Pb_j \xb_i) \cdot \sum_{j'=1}^k \frac{v_{j'} - v'_{j'}}{\|\vb - \vb'\|_2} \sigma(\wb^\top \Pb_{j'} \xb_i)\\
    &\leq C_6 L^2 k,
\end{align*}
where $C_6$ is an absolute constant. This completes the proof of Lemma~\ref{lemma:smoothness_all}.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:gradientuniformconcentration}}
We first introduce the following lemma.
\begin{lemma}\label{lemma:sigma(x)subgaussian} Let $z$ be a standard Gaussian random variable. Then under Assumption~\ref{assump:1Lipschitz}, $\sigma(z)$ is sub-Gaussian with
\begin{align*}
    \|\sigma(z)\|_{\psi_2} \leq CL \text{ and }\|\sigma(z) - \kappa \|_{\psi_2} \leq C\Gamma,
\end{align*}
where $C$ is an absolute constant, $L = 1+|\sigma(0)|$ and $\Gamma = 1 + |\sigma(0) - \kappa|$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lemma:gradientuniformconcentration}]
By assumption, with probability at least $1-\delta/3$, the bounds given in Lemma~\ref{lemma:smoothness_all} all hold.
let $\cN_1 = \cN[\cW_0, (kn)^{-1}]$, $\cN_2 = \cN[\cV_0, (kn)^{-1}]$ be $(kn)^{-1}$-nets covering $\cW_0$ and $\cV_0$ respectively. Then by the proof of Lemma~5.2 in \cite{vershynin2010introduction}, we have
\begin{align*}
    |\cN_1|\leq (3kn)^r,~|\cN_2|\leq (3kn)^k.
\end{align*}
For any $\wb\in \cW_0$ and $\vb\in \cV_0$, there exists $\hat{\wb}\in \cN_1$ and $\hat{\vb}\in \cN_2$ such that
\begin{align*}
    \|\wb - \hat{\wb}\|_2 \leq (kn)^{-1},~ \|\vb - \hat{\vb}\|_2 \leq (kn)^{-1}.
\end{align*}

\noindent\textbf{Proof of \eqref{eq:gradientuniformconcentration_w}}. By triangle inequality we have
\begin{align*}
    \|\gb_w(\wb,\vb) - \overline{\gb}_w(\wb,\vb) \|_2 \leq A_1 + A_2 + A_3,
\end{align*}
where
\begin{align*}
    &A_1 = \|\gb_w(\wb,\vb) - \gb_w(\hat{\wb},\hat{\vb}) \|_2,\\
    &A_2 = \|\gb_w(\hat{\wb},\hat{\vb}) -  \overline{\gb}_w(\hat{\wb},\hat{\vb}) \|_2,\\
    &A_3 = \|\overline{\gb}_w(\hat{\wb},\hat{\vb}) -  \overline{\gb}_w(\wb,\vb) \|_2.
\end{align*}
For $A_1$, we have
\begin{align}
A_1 &\leq \|\gb_w(\wb,\vb) - \gb_w(\hat{\wb},\vb) \|_2 + \|\gb_w(\hat{\wb},\vb) - \gb_w(\hat{\wb},\hat{\vb}) \|_2 \nonumber \\
&\leq C_1\xi^{-1} D_0^2\sqrt{k} \| \wb - \hat{\wb} \|_2 + C_2 \xi^{-1}(\nu + D_0L\sqrt{k}) \| \vb - \hat{\vb} \|_2\nonumber \\
&\leq C_3 \xi^{-1} (\nu + D_0^2 +  D_0L)\frac{1}{n\sqrt{k}},\label{eq:gradientuniformconcentrationproof1}
\end{align}
where $C_1$, $C_2$ and $C_3$ are absolute constants. For $A_2$, by direct calculation we have
\begin{align*}
    \overline{\gb}_w(\hat{\wb},\hat{\vb}) = \EE [\gb_w(\hat{\wb},\hat{\vb})].
\end{align*}
Let $\cN_3 = \cN(S^{r-1}, 1/2)$ be a $1/2$-net covering $S^{r-1}$. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_3|\leq 5^r$. By definition, for any $\ab \in \cN_3$ we have
\begin{align*}
    \ab^\top \gb_w(\hat{\wb},\hat{\vb}) = -\frac{1}{n\xi} \sum_{i=1}^n [U_i^* - U_i  + \epsilon_i + \kappa \mathbf{1}^\top(\vb^*-\hat{\vb}) ] V_i,
\end{align*}
where
\begin{align*}
    U_i^* = \sum_{j=1}^k v_j^*[\sigma(\wb^{*\top}\Pb_j\xb_{i})- \kappa],~U_i = \sum_{j=1}^k \hat{v}_j[\sigma(\hat{\wb}^{\top} \Pb_j \xb_{i}) - \kappa],~ V_i = \sum_{j=1}^k \hat{v}_{j}\ab^\top \Pb_j\xb_{i}.
\end{align*}
By Lemma~\ref{lemma:sigma(x)subgaussian}, $\sigma(\wb^{*\top} \Pb_j\xb_{i}) -\kappa$ and $\sigma(\hat{\wb}^{\top} \Pb_j\xb_{i}) -\kappa$ are centered sub-Gaussian random variables with $\|\sigma(\wb^{*\top} \Pb_j\xb_{i}) -\kappa \|_{\psi_2}, \|\sigma(\hat{\wb}^{\top} \Pb_j\xb_{i})-\kappa\|_{\psi_2} \leq C_4\Gamma$ for some absolute constant $C_4$. Therefore by Lemma~5.9 in \cite{vershynin2010introduction}, we have $\| U_i^* \|_{\psi_2} \leq C_5 \| \vb^*\|_2 \Gamma$ and $\| U_i \|_{\psi_2} \leq C_5 D_0 \Gamma$, where $C_5$ is an absolute constant. Similarly, we have $\| V_i \|_{\psi_2} \leq C_6 D_0$ for some absolute constant $C_6$. Therefore, by Lemma~\ref{lemma:subgaussianproduct} we have
\begin{align*}
    \| [U_i^* - U_i  + \epsilon_i + \kappa \mathbf{1}^\top(\vb^*-\hat{\vb}) ] V_i \|_{\psi_1} &\leq C_7 D_0[(D_0 + \| \vb^*\|_2) \Gamma + M + \nu]\\
    &\leq C_8 D_0(D_0 \Gamma + M + \nu),
\end{align*}
where $C_7$ and $C_8$ are absolute constants. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/3$, we have
\begin{align*}
    |\ab^\top [\gb_w(\hat{\wb},\hat{\vb}) -  \overline{\gb}_w(\hat{\wb},\hat{\vb})]| \leq C_9 \xi^{-1} D_0(D_0 \Gamma + M + \nu) \sqrt{\frac{(r+k)\log(90nk/\delta)}{n}}
\end{align*}
for all $\hat{\wb} \in \cN_1$, $\hat{\vb} \in \cN_2$ and $\ab \in \cN_3$, where $C_9$ is an absolute constant. Therefore by Lemma~5.3 in \cite{vershynin2010introduction},  we have
\begin{align}\label{eq:gradientuniformconcentrationproof2}
    A_2 \leq  C_{10} \xi^{-1} D_0(D_0 \Gamma + M + \nu) \sqrt{\frac{(r+k)\log(90nk/\delta)}{n}}
\end{align}
for all $\hat{\wb} \in \cN_1$, $\hat{\vb} \in \cN_2$, where $C_{10}$ is an absolute constant. For $A_3$, by triangle inequality we have
\begin{align}
    A_3 &\leq \|\overline{\gb}_w(\hat{\wb},\hat{\vb}) -  \overline{\gb}_w(\wb,\hat{\vb}) \|_2 + \|\overline{\gb}_w(\wb,\hat{\vb}) -  \overline{\gb}_w(\wb,\vb) \|_2\nonumber \\
    &\leq \| \hat{\vb} \|_2^2 \| \wb - \hat{\wb} \|_2 + \big[\big|\| \vb \|_2^2 - \| \hat{\vb} \|_2^2\big| + \big|\vb^{*\top} (\vb - \hat{\vb})\big| \big]\nonumber \\
    &\leq D_0^2 \| \wb - \hat{\wb} \|_2 + 3D_0 \| \vb - \hat{\vb} \|_2\nonumber \\
    &\leq 4D_0(D_0+1) (nk)^{-1}.\label{eq:gradientuniformconcentrationproof3}
\end{align}
By \eqref{eq:gradientuniformconcentrationproof1}, \eqref{eq:gradientuniformconcentrationproof2}, \eqref{eq:gradientuniformconcentrationproof3}, and the assumptions on sample size $n$, we have
\begin{align*}
    \|\gb_w(\wb,\vb) - \overline{\gb}_w(\wb,\vb) \|_2 \leq  C_{11} \xi^{-1} D_0(D_0 \Gamma + M + \nu) \sqrt{\frac{(r+k)\log(90nk/\delta)}{n}},
\end{align*}
where $C_{11}$ is an absolute constant.

\noindent\textbf{Proof of \eqref{eq:gradientuniformconcentration_v}}. By triangle inequality we have
\begin{align*}
    \|\gb_v(\wb,\vb) - \overline{\gb}_v(\wb,\vb) \|_2 \leq B_1 + B_2 + B_3,
\end{align*}
where
\begin{align*}
    &B_1 = \|\gb_v(\wb,\vb) - \gb_v(\hat{\wb},\hat{\vb}) \|_2,\\
    &B_2 = \|\gb_v(\hat{\wb},\hat{\vb}) -  \overline{\gb}_v(\hat{\wb},\hat{\vb}) \|_2,\\
    &B_3 = \|\overline{\gb}_v(\hat{\wb},\hat{\vb}) -  \overline{\gb}_v(\wb,\vb) \|_2.
\end{align*}
For $B_1$, by Lemma~\ref{lemma:smoothness_all} we have
\begin{align}
    B_1 &\leq  \|\gb_v(\wb,\vb) - \gb_v(\hat{\wb},\vb) \|_2 + \|\gb_v(\hat{\wb},\vb) - \gb_v(\hat{\wb},\hat{\vb}) \|_2 \nonumber \\
    &\leq C_{12} ( \nu +  D_0 L \sqrt{k})\sqrt{k} \| \wb - \hat{\wb} \|_2 + C_{13} L^2 k \| \vb - \hat{\vb} \|_2 \nonumber \\
    &\leq C_{14} (\nu \sqrt{k} + D_0 L k + L^2 k)/(nk),\label{eq:gradientuniformconcentrationproof4}
\end{align}
where $C_{12}$, $C_{13}$ and $C_{14}$ are absolute constants. For $B_2$, by direct calculation we have
\begin{align*}
    \overline{\gb}_v(\hat{\wb},\hat{\vb})  =  \EE[\gb_v(\hat{\wb},\hat{\vb})].
\end{align*}
Let $\cN_4 = \cN(S^{k-1}, 1/2)$ be a $1/2$-net covering $S^{k-1}$. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_4|\leq 5^k$. By definition, for any $\mathbf{b} \in \cN_4$ we have
\begin{align*}
    \mathbf{b}^\top \gb_v(\hat{\wb},\hat{\vb}) = - \frac{1}{n} \sum_{i=1}^n [U_i^* - U_i + \epsilon_i +  \kappa \mathbf{1}^\top(\vb^*-\hat{\vb}) ] (U_i' + \kappa \mathbf{1}^\top \mathbf{b}),
\end{align*}
where
\begin{align*}
    U_i^* = \sum_{j=1}^k v_j^*[\sigma(\wb^{*\top} \Pb_j \xb_i)- \kappa],~U_i = \sum_{j=1}^k \hat{v}_j^t[\sigma(\hat{\wb}^{\top}  \Pb_j \xb_i)- \kappa],~U_i' = \sum_{j=1}^k b_j[\sigma(\hat{\wb}^{\top} \Pb_j \xb_i)-\kappa].
\end{align*}
Similar to the proof of \eqref{eq:gradientuniformconcentration_w}, we have $\| U_i^* \|_{\psi_2} \leq C_{15} \| \vb^*\|_2 \Gamma$, $\| U_i \|_{\psi_2} \leq C_{15} D_0 \Gamma$, and $\| U_i' \|_{\psi_2} \leq C_{15} \Gamma$, where $C_{15}$ is an absolute constant.
Therefore by Lemma~\ref{lemma:subgaussianproduct}, we have
\begin{align*}
    \| [U_i^* - U_i + \epsilon_i +  \kappa \mathbf{1}^\top(\vb^*-\hat{\vb}) ] &(U_i' + \kappa \mathbf{1}^\top \mathbf{b}) \|_{\psi_2} \leq C_{16} (\Gamma + \kappa \sqrt{k}) [D_0 \Gamma + M + \nu],
\end{align*}
where $C_{16}$ is an absolute constant. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/4$ we have
\begin{align*}
    | \mathbf{b}^\top [\gb_v(\hat{\wb},\hat{\vb}) - \overline{\gb}_v(\hat{\wb},\hat{\vb}) ] | \leq C_{17} (\Gamma + \kappa \sqrt{k}) [D_0 \Gamma + M + \nu]\sqrt{\frac{(r+k)\log(90nk/\delta)}{n}}
\end{align*}
for all $\hat{\wb}\in \cN_1$, $\hat{\vb}\in \cN_2$ and $\mathbf{b}\in \cN_4$, where $C_{17}$ is an absolute constant. By Lemma~5.3 in \cite{vershynin2010introduction}, we have
\begin{align}
    \| \gb_v(\hat{\wb},\hat{\vb}) - \overline{\gb}_v(\hat{\wb},\hat{\vb}) \|_2 \leq C_{18}(\Gamma + \kappa \sqrt{k}) [D_0 \Gamma + M + \nu]\sqrt{\frac{(r+k)\log(90nk/\delta)}{n}}\label{eq:gradientuniformconcentrationproof5}
\end{align}
for all $\hat{\wb}\in \cN_1$, $\hat{\vb}\in \cN_2$, where $C_{18}$ is an absolute constant. For $B_3$, by definition and Lemma~\ref{lemma:philipschitz} we have
\begin{align}
    B_3 &\leq (\Delta + \kappa k) \| \vb - \hat{\vb} \|_2 + \| \vb^* \|_2 |\phi(\wb,\wb^*) - \phi(\hat{\wb},\wb^*)| \nonumber \\
    &\leq (\Delta + \kappa k) \| \vb - \hat{\vb} \|_2 + L\| \vb^* \|_2 \| \wb - \hat{\wb} \|_2 \nonumber \\
    &\leq (\Delta + \kappa k + D_0L) (nk)^{-1}. \label{eq:gradientuniformconcentrationproof6}
\end{align}
By \eqref{eq:gradientuniformconcentrationproof4}, \eqref{eq:gradientuniformconcentrationproof5}, \eqref{eq:gradientuniformconcentrationproof6} and the assumptions on the sample size $n$, we have
\begin{align*}
    \|\gb_v(\wb,\vb) - \overline{\gb}_v(\wb,\vb) \|_2 \leq C_{19}(\Gamma + \kappa \sqrt{k}) [D_0 \Gamma + M + \nu]\sqrt{\frac{(r+k)\log(90nk/\delta)}{n}},
\end{align*}
where $C_{19}$ is an absolute constant. This completes the proof of \eqref{eq:gradientuniformconcentration_v}.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:recursiveproperty}}
We remind the readers that $L = 1+|\sigma(0)|$ and $\Gamma = 1 + |\sigma(0) - \kappa|$ are constants that only depends on the activation function. We introduce the following notations. Let
\begin{align*}
\begin{array}{ll}
    \overline{\gb}_w^t = \overline{\gb}_w(\wb^t,\vb^t), &\overline{\gb}_v^t = \overline{\gb}_v(\wb^t,\vb^t),\\
    \overline{\ub}^{t+1} = \wb^{t} - \alpha \overline{\gb}_w^t, & \overline{\vb}^{t+1} = \vb^{t} - \alpha \overline{\gb}_v^t.
\end{array}
\end{align*}
Then it is easy to see that for any fixed $\wb^t,\vb^t$, the vectors $\overline{\gb}_w^t,\overline{\gb}_v^t,\overline{\ub}^{t+1},\overline{\vb}^{t+1}$ defined above are expectations of $\gb_w^t,\gb_v^t,\ub^{t+1},\vb^{t+1}$ respectively.
We will also use the result of the following lemma.
\begin{lemma}\label{lemma:philipschitz}
Under Assumption~\ref{assump:1Lipschitz}, for any fixed unit vector $\wb$, $\phi(\wb,\cdot)$ is Lipschitz continuous with Lipschitz constant $L = 1+|\sigma(0)|$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lemma:recursiveproperty}]
We now list the proof of \eqref{eq:recursiveproperty1}-\eqref{eq:recursiveproperty4} as follows.

\noindent\textbf{Proof of \eqref{eq:recursiveproperty1}}. By the definition of $\overline{\ub}^{t+1}$ and $\overline{\gb}^{t}$ we have
\begin{align*}
    \overline{\ub}^{t+1} =  \wb^t - \alpha \overline{\gb}_w^{t} = (1-\alpha \|\vb^t\|_2^2) \wb^t + \alpha (\vb^{*\top} \vb^t) \wb^*.
\end{align*}
The equation above implies that when $1-\alpha \|\vb^t\|_2^2 \geq 0$, $\overline{\ub}^{t+1}$ is in the cone spanned by $\wb^t$ and $\wb^*$. To simplify notation, we define $\hat{\ub} = \overline{\ub}^{t+1} / \| \overline{\ub}^{t+1} \|_2$. By $1-\alpha \|\vb^t\|_2^2 < 1$ and $\alpha (\vb^{*\top} \vb^t) \geq \alpha\rho$, we have
\begin{align}\label{eq:recursivepropertyproof1}
    \wb^{*\top}\hat{\ub} \geq \wb^{*\top} \frac{ \alpha\rho \wb^* + \wb^t }{ \| \alpha\rho \wb^* + \wb^t \|_2 }
    = \frac{ \alpha\rho + \wb^{*\top}\wb^t }{ \| \alpha\rho \wb^* + \wb^t \|_2 }
    \geq \frac{ \alpha\rho + \wb^{*\top}\wb^t }{ 1 + \alpha\rho }.
\end{align}
The first inequality in \eqref{eq:recursivepropertyproof1} is further explained in Figure~\ref{fig:wboundexplanation}.
\begin{figure}[t]
	\begin{center}
		\includegraphics[width=.6\textwidth,angle=0]{wboundexplanationcomplete}
	\end{center}
	\vskip-15pt
	\caption{Explanation of \eqref{eq:recursivepropertyproof1}. The two arrows denotes $\wb^*$ and $\wb^t$. The gray area shows all possible positions of $a \wb^* + b \wb^t$ with $a\geq \alpha\rho$ and $0 \leq b \leq 1$. We use blue and green dots to represent the worst case of $\overline{\ub}^{t+1}$ and $\hat{\ub}$ respectively. The first inequality in \eqref{eq:recursivepropertyproof1} is then easily obtained by replacing $\hat{\ub}$ with its worst case value, which is $\frac{ \alpha\rho \wb^* + \wb^t }{ \| \alpha\rho \wb^* + \wb^t \|_2}$.}
	\label{fig:wboundexplanation}
	\vspace{-10pt}
\end{figure}
Moreover, by Lemma~\ref{lemma:gradientuniformconcentration} we have
\begin{align*}
    \| \ub^{t+1} - \overline{\ub}^{t+1} \|_2 = \alpha \| \gb_w^{t} - \overline{\gb}_w^{t} \|_2 \leq \alpha \eta_w.
\end{align*}
By Lemma~\ref{lemma:distance2innerproduct}, we have
\begin{align*}
    \| \wb^{t+1} - \hat{\ub} \|_2 \leq \frac{2\alpha \eta_w}{ \| \overline{\ub}^{t+1}\|_2 }.
\end{align*}
By $\wb^{*\top}\wb^t>0$, we have
\begin{align*}
    \| \overline{\ub}^{t+1} \|_2 = \big\|  (1-\alpha \|\vb^t\|_2^2) \wb^t + \alpha \vb^{t\top} \vb^*\wb^* \big\|_2 \geq 1-\alpha \|\vb^t\|_2^2 \geq 1 - \alpha D_0^2 \geq \frac{1}{2}.
\end{align*}
Therefore,
\begin{align}\label{eq:recursivepropertyproof2}
    \| \wb^{t+1} - \hat{\ub} \|_2 \leq 4\alpha \eta_w.
\end{align}
Since $\wb^*$, $\wb^t$ and $\hat{u}$ are all unit vectors, by \eqref{eq:recursivepropertyproof1} we have
\begin{align*}
    1 -\frac{1}{2} \|\wb^{*} - \hat{\ub}\|_2^2 \geq  \frac{ \alpha\rho }{ 1 + \alpha\rho  }  +  \frac{ 1}{ 1 + \alpha\rho } \bigg( 1 - \frac{1}{2} \|\wb^{*\top } - \wb^t\|_2^2 \bigg).
\end{align*}
Rearranging terms gives
\begin{align*}
    \| \hat{\ub} - \wb^* \|_2 \leq \frac{1}{\sqrt{1+\alpha \rho }} \| \wb^t -\wb^* \|_2.
\end{align*}
By \eqref{eq:recursivepropertyproof2} we have
\begin{align*}
    \| \wb^{t+1} - \wb^* \|_2 \leq \frac{1}{\sqrt{1+\alpha \rho }} \| \wb^t -\wb^* \|_2 + 4\alpha \eta_w \leq \frac{1}{\sqrt{1+\alpha \rho }} \| \wb^t -\wb^* \|_2 + \frac{8\alpha\sqrt{1+\alpha\rho}}{1 + \sqrt{1+\alpha\rho}} \eta_w.
\end{align*}
Rearranging terms again, we obtain
\begin{align*}
    \| \wb^{t+1} - \wb^* \|_2 - 8\rho^{-1}(1+\alpha\rho)\eta_w \leq \frac{1}{\sqrt{1+\alpha \rho }} [\| \wb^t -\wb^* \|_2 - 8\rho^{-1}(1+\alpha\rho)\eta_w].
\end{align*}
This completes the proof of \eqref{eq:recursiveproperty1}.

\noindent \textbf{Proof of \eqref{eq:recursiveproperty2}}. By the definition of $\overline{\gb}_v^{t}$ we have
\begin{align*}
    \mathbf{1}^\top \overline{\gb}_v^{t} &= \mathbf{1}^\top \{(\Delta \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top )\vb^t - [\phi(\wb^t,\wb^*) \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top ]\vb^*\} \\
    & = (\Delta + \kappa^2k) \mathbf{1}^\top\vb^t - [\phi(\wb^t,\wb^*)  + \kappa^2 k  ] \mathbf{1}^\top\vb^*\\
    & = (\Delta + \kappa^2k) \mathbf{1}^\top(\vb^t - \vb^*) + [\Delta - \phi(\wb^t,\wb^*)]\mathbf{1}^\top\vb^*.
\end{align*}
Therefore,
\begin{align*}
    \mathbf{1}^\top (\overline{\vb}^{t+1} - \vb^*) = [1 - \alpha (\Delta + \kappa^2k)]\mathbf{1}^\top (\vb^{t} - \vb^*) - \alpha [\Delta - \phi(\wb^t,\wb^*)]\mathbf{1}^\top\vb^*.
\end{align*}
By Lemma~\ref{lemma:gradientuniformconcentration},
$
|\mathbf{1}^\top (\vb^{t+1} - \vb^t)| \leq \alpha |\mathbf{1}^\top (\gb^{t} - \overline{\gb}^t)| \leq \alpha \sqrt{k} \| \gb^{t} - \overline{\gb}^t \|_2 \leq \alpha \sqrt{k} \eta_v
$.
Therefore by triangle inequality we have
\begin{align*}
    |\mathbf{1}^\top (\vb^{t+1} - \vb^*)| \leq [1 - \alpha (\Delta + \kappa^2k)]|\mathbf{1}^\top (\vb^{t} - \vb^*)| + \alpha |\Delta - \phi(\wb^t,\wb^*)|\cdot |\mathbf{1}^\top\vb^*| + \alpha \sqrt{k} \eta_v.
\end{align*}
By lemma~\ref{lemma:philipschitz}, we have
\begin{align*}
    |\Delta - \phi(\wb^t,\wb^*)| = |\phi(\wb^*,\wb^*) - \phi(\wb^t,\wb^*)| \leq L\| \wb^t - \wb^* \|_2.
\end{align*}
Therefore,
\begin{align}\label{eq:recursivepropertyproof3}
    |\mathbf{1}^\top (\vb^{t+1} - \vb^*)| \leq [1 - \alpha (\Delta + \kappa^2k)]|\mathbf{1}^\top (\vb^{t} - \vb^*)| + \alpha L\| \wb^t - \wb^* \|_2 |\mathbf{1}^\top\vb^*| + \alpha \sqrt{k} \eta_v.
\end{align}
This completes the proof of \eqref{eq:recursiveproperty2}.

\noindent\textbf{Proof of \eqref{eq:recursiveproperty3}}.
By the definition of $\overline{\gb}_v^{t}$, we have
\begin{align}
    \overline{\gb}_v^{t} &= (\Delta \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top )\vb^t - [\phi(\wb^t,\wb^*) \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top ]\vb^*\nonumber \\
    & = \Delta \vb^t - \phi(\wb^t,\wb^*) \vb^*  + \kappa^2 \mathbf{1} \mathbf{1}^\top (\vb^t - \vb^* ) \nonumber \\
    & = \Delta (\vb^t - \vb^*) + [\Delta -  \phi(\wb^t,\wb^*)] \vb^*  + \kappa^2 \mathbf{1} \mathbf{1}^\top (\vb^t - \vb^* ).\label{eq:recursivepropertyproof4}
\end{align}
Therefore
\begin{align*}
    (\vb^t - \vb^* )^\top \overline{\gb}_v^{t} & \geq \Delta \| \vb^t - \vb^* \|_2^2 +  [\Delta -  \phi(\wb^t,\wb^*)] (\vb^t - \vb^* )^\top \vb^* \\
    & \geq \Delta \| \vb^t - \vb^* \|_2^2  -  |\Delta -  \phi(\wb^t,\wb^*)|\cdot \|\vb^t - \vb^* \|_2 \|\vb^*\|_2.
\end{align*}
By Lemma~\ref{lemma:philipschitz}, we have
\begin{align*}
    |\Delta -  \phi(\wb^t,\wb^*)| = |\phi(\wb^*,\wb^*) - \phi(\wb^t,\wb^*)| \leq L \|\wb^* - \wb^t\|_2.
\end{align*}
Therefore,
\begin{align*}
    (\vb^t - \vb^* )^\top \overline{\gb}_v^{t} & \geq \Delta \| \vb^t - \vb^* \|_2^2  -  L\|\wb^{*} - \wb^t\|_2 \|\vb^t - \vb^* \|_2 \|\vb^*\|_2 \\
    &\geq \Delta \| \vb^t - \vb^* \|_2^2 - \frac{1}{2} \bigg( \frac{L^2}{\Delta}\|\vb^*\|_2^2 \|\wb^{*} - \wb^t\|_2^2 + \Delta  \|\vb^t - \vb^* \|_2^2 \bigg) \\
    &\geq \frac{\Delta}{2} \| \vb^t - \vb^* \|_2^2 - \frac{L^2}{2\Delta} \|\vb^*\|_2^2 \|\wb^{*} - \wb^t\|_2^2.
\end{align*}
By Lemma~\ref{lemma:gradientuniformconcentration}, we have
\begin{align*}
    (\vb^t - \vb^* )^\top \gb_v^t &\geq \frac{\Delta}{2} \| \vb^t - \vb^* \|_2^2 - \frac{L^2}{2\Delta} \|\vb^*\|_2^2 \|\wb^{*} - \wb^t\|_2^2 - \|\vb^t - \vb^* \|_2 \eta_v\\
    &\geq \frac{\Delta}{4} \| \vb^t - \vb^* \|_2^2 - \frac{L^2}{2\Delta} \|\vb^*\|_2^2 \|\wb^{*} - \wb^t\|_2^2 - \frac{1}{\Delta}\eta_v^2
\end{align*}
Moreover, by \eqref{eq:recursivepropertyproof4} we have
\begin{align*}
    \| \overline{\gb}_v^{t} \|_2 \leq \Delta \|\vb^t - \vb^*\|_2 + L  \|\vb^* \|_2 \|\wb^t -\wb^* \|_2 + \kappa^2 \sqrt{k} | \mathbf{1}^\top (\vb^t - \vb^*) |.
\end{align*}
By Lemma~\ref{lemma:gradientuniformconcentration}, we have
\begin{align*}
    \| \gb_v^t \|_2 \leq \Delta \|\vb^t - \vb^*\|_2 + L \|\vb^* \|_2 \|\wb^t -\wb^* \|_2 + \kappa^2 \sqrt{k} | \mathbf{1}^\top (\vb^t - \vb^*) | + \eta_v,
\end{align*}
Therefore,
\begin{align*}
    \| \vb^{t+1} -\vb^* \|_2^2 &= \| \vb^{t} - \alpha \gb_v^t -\vb^* \|_2^2\\
    & = \| \vb^{t} -\vb^* \|_2^2 - 2\alpha (\vb^t - \vb^* )^\top \gb_v^t +\alpha^2 \| \gb_v^t \|_2^2.
\end{align*}
Plugging in the previous inequalities gives
\begin{align*}
    \| \vb^{t+1} -\vb^* \|_2^2 \leq & ( 1 - \alpha \Delta + 4\alpha^2\Delta^2 ) \| \vb^{t} -\vb^* \|_2^2 + \bigg(\frac{\alpha L^2}{\Delta} + 4\alpha^2L^2 \bigg)  \|\vb^*\|_2^2 \|\wb^{*} - \wb^t\|_2^2\\
    & + 4\alpha^2\kappa^4 k [ \mathbf{1}^\top (\vb^t - \vb^*) ]^2 + \bigg( \frac{2\alpha}{\Delta} + 4 \alpha^2 \bigg) \eta_v^2.
\end{align*}
This completes the proof of \eqref{eq:recursiveproperty3}.

\noindent \textbf{Proof of \eqref{eq:recursiveproperty4}}. We first check $\wb^{t+1}\in \cW$. By \eqref{eq:recursivepropertyproof1} and \eqref{eq:recursivepropertyproof2} we have
\begin{align*}
    \wb^{*\top}\wb^{t+1} \geq  \frac{\alpha \rho + \wb^{*\top}\wb^t }{ 1 + \alpha\rho  } -  4\alpha \eta_w.
\end{align*}
Since $\wb^t\in \cW$, we have $\wb^{*\top} \wb^0 \leq 2\wb^{*\top} \wb^t$. Moreover, by $ \wb^{*\top} \wb^0 \leq 1$, we have
\begin{align*}
\wb^{*\top}\wb^{t+1}\geq  \frac{\alpha \rho }{ 1 + \alpha\rho  }\wb^{*\top} \wb^0 + \frac{1}{2}\frac{ 1 }{ 1 + \alpha\rho }\wb^{*\top}\wb^0 -  4\alpha \eta_w \geq \frac{1}{2}\wb^{*\top}\wb^0.
\end{align*}
where the last inequality follows by the assumption that
\begin{align*}
    4\alpha \eta_w \leq \frac{1}{2} \frac{\alpha \rho }{ 1 + \alpha\rho  }\wb^{*\top} \wb^0.
\end{align*}
Since $\|\wb^{t+1}\|_2 = 1$, we have $\wb^{t+1}\in \cW$. For $\vb^{t+1}$, since $\vb^t\in \cV$, by \eqref{eq:recursiveproperty3} and the definition of $M$ and $D$ we have
\begin{align*}
    \|\vb^{t+1} - \vb^*\|_2^2 &\leq (1-\alpha\Delta + 4\alpha^2 \Delta^2) \|\vb^{t} - \vb^*\|_2^2 + \alpha(\Delta^{-1} + 4\alpha) L^2 \|\vb^*\|_2^2\cdot 4\\
    &\qquad + 4\alpha^2 \kappa^2 M^2 k  + 2\alpha (\Delta^{-1} + 2\alpha)\\
    &\leq  (1-\alpha\Delta + 4\alpha^2 \Delta^2) D^2 + \alpha\Delta(1 - 4\alpha \Delta)D^2\\
    & = D^2.
\end{align*}
Therefore we have $\|\vb^{t+1} - \vb^*\|_2 \leq D$. Since $\vb^t \in \cV$, by \eqref{eq:recursivepropertyproof3} and the definition of $M$ we have
\begin{align*}
    |\kappa\mathbf{1}^\top (\vb^{t+1} - \vb^*)| &\leq [1 - \alpha (\Delta + \kappa^2k)]|\kappa\mathbf{1}^\top (\vb^{t} - \vb^*)| + \alpha|\kappa| L \| \wb^t - \wb^* \|_2 |\mathbf{1}^\top\vb^*| + \alpha|\kappa| \sqrt{k} \eta_v\\
    & \leq [1 - \alpha (\Delta + \kappa^2k)] M + 2\alpha |\kappa| L |\mathbf{1}^\top\vb^*| + \alpha|\kappa| \sqrt{k}\\
    & \leq [1 - \alpha (\Delta + \kappa^2k)] M  + \alpha (\Delta + \kappa^2k)  M\\
    & = M.
\end{align*}
We now check $\vb^{*\top}\vb^{t+1}\geq \rho$. By assumption we have $\kappa^2 (\mathbf{1}^\top \vb^*)\mathbf{1}^\top(\vb^t - \vb^*) \leq \rho$. Therefore by definition we have
\begin{align*}
    \vb^{*\top}\overline{\gb}_v^{t} &= \Delta \vb^{*\top} \vb^t + \kappa^2 (\mathbf{1}^\top \vb^*) (\mathbf{1}^\top \vb^t) - \psi(\wb^{*\top}\wb^t) \|\vb^{*}\|_2^2  - \kappa^2 (\mathbf{1}^\top \vb^*)^2\\
    &\leq \Delta \vb^{*\top} \vb^t - \psi(\wb^{*\top}\wb^t ) \|\vb^{*}\|_2^2 + \rho.
\end{align*}
By Lemma~\ref{lemma:psidefinition}, $\psi(\tau)$ is an increasing function. Therefore,
\begin{align*}
    \vb^{*\top}\overline{\vb}^{t+1} &= \vb^{*\top} ( \vb^t - \alpha \overline{\gb}_v^{t}) \\
    &\geq  \vb^{*\top}\vb^t -\alpha [\Delta \vb^{*\top} \vb^t - \psi(\wb^{*\top}\wb^t ) \|\vb^{*}\|_2^2 + \rho ] \\
    &\geq (1-\alpha\Delta) \vb^{*\top}\vb^t + \alpha \psi(\wb^{*\top}\wb^0/2 ) \|\vb^{*}\|_2^2 -\alpha\rho\\
    &\geq (1-\alpha\Delta) \rho + \alpha \psi(\wb^{*\top}\wb^0/2 ) \|\vb^{*}\|_2^2 -\alpha\rho.
\end{align*}
By the definition of $\rho$, we have
\begin{align*}
    \psi(\wb^{*\top}\wb^0/2 ) \|\vb^{*}\|_2^2 \geq (2 + \Delta) \rho.
\end{align*}
Therefore we have
\begin{align*}
    \vb^{*\top}\overline{\vb}^{t+1} \geq (1-\alpha\Delta) \rho + \alpha (2+\Delta) \rho - \alpha\rho = (1+\alpha)\rho.
\end{align*}
Moreover,
\begin{align*}
    | \vb^{*\top}\vb^{t+1} - \vb^{*\top}\overline{\vb}^{t+1} | \leq \alpha\|\vb^*\|_2\eta_v.
\end{align*}
By the assumptions on $n$ we have $\|\vb^*\|_2\eta_v \leq \rho$. Therefore
\begin{align*}
    \vb^{*\top}\vb^{t+1} \geq (1+\alpha)\rho - \alpha \|\vb^*\|_2 \eta_v \geq \rho.
\end{align*}
Finally, we check $\kappa^2 (\mathbf{1}^\top \vb^*)\mathbf{1}^\top(\vb^{t+1} - \vb^*) \leq \rho$. By definition we have
\begin{align*}
    \mathbf{1}^\top \overline{\gb}_v^{t} &= \mathbf{1}^\top \{(\Delta \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top )\vb^t - [\phi(\wb^t,\wb^*) \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top ]\vb^*\} \\
    & = (\Delta + \kappa^2k) \mathbf{1}^\top\vb^t - [\phi(\wb^t,\wb^*)  + \kappa^2 k  ] \mathbf{1}^\top\vb^*.
\end{align*}
By Lemma~\ref{lemma:psidefinition}, we have $\phi(\wb^t,\wb^*) \leq \Delta$. Therefore,
\begin{align*}
    (\mathbf{1}^\top\vb^*)(\mathbf{1}^\top \overline{\gb}_v^{t})
    & = (\Delta + \kappa^2k) (\mathbf{1}^\top\vb^*) (\mathbf{1}^\top\vb^t) - [\phi(\wb^t,\wb^*)  + \kappa^2 k  ] (\mathbf{1}^\top\vb^*)^2\\
    &\geq  (\Delta + \kappa^2k) (\mathbf{1}^\top \vb^{*})\mathbf{1}^\top (\vb^{t} - \vb^{*}),
\end{align*}
and
\begin{align*}
    (\mathbf{1}^\top \vb^{*})\mathbf{1}^\top(\overline{\vb}^{t+1} - \vb^*) &\leq (\mathbf{1}^\top \vb^{*})\mathbf{1}^\top(\vb^{t} - \vb^*) - \alpha (\Delta + \kappa^2k) (\mathbf{1}^\top \vb^{*})\mathbf{1}^\top (\vb^{t} - \vb^{*})\\
    & = [1 - \alpha (\Delta + \kappa^2k)](\mathbf{1}^\top \vb^{*})\mathbf{1}^\top (\vb^{t} - \vb^{*}).
\end{align*}
Since $\vb^t \in \cV$, by Lemma~\ref{lemma:gradientuniformconcentration}, when $1- \alpha  (\Delta + \kappa^2k) \geq 0$ we have
\begin{align*}
    \kappa^2(\mathbf{1}^\top \vb^{*})\mathbf{1}^\top (\vb^{t+1} - \vb^{*}) &\leq [1 - \alpha (\Delta + \kappa^2k)][\kappa^2(\mathbf{1}^\top \vb^{*})\mathbf{1}^\top (\vb^{t} - \vb^{*})] + \alpha \kappa^2|\mathbf{1}^\top \vb^{*}|\sqrt{k}\eta_v\\
    &\leq  [1 - \alpha (\Delta + \kappa^2k)]\rho  + \alpha \kappa^2|\mathbf{1}^\top \vb^{*}|\sqrt{k}\eta_v\\
    &\leq [1 - \alpha (\Delta + \kappa^2k)]\rho +\alpha (\Delta + \kappa^2k)\cdot \frac{\kappa^2|\mathbf{1}^\top \vb^{*}|\sqrt{k}}{\Delta + \kappa^2k}\cdot \eta_v\\
    &\leq [1 - \alpha (\Delta + \kappa^2k)]\rho +\alpha (\Delta + \kappa^2k) \cdot \frac{|\mathbf{1}^\top \vb^{*}|}{\sqrt{k}}\cdot \eta_v.
\end{align*}
By the assumption on $n$ we have $|\mathbf{1}^\top \vb^{*}| k^{-1/2} \eta_v \leq \rho$. Plugging it into the inequality above gives
\begin{align*}
    \kappa^2(\mathbf{1}^\top \vb^{*})\mathbf{1}^\top (\vb^{t+1} - \vb^{*}) \leq \rho.
\end{align*}
Therefore we have $(\wb^{t+1},\vb^{t+1}) \in \cW \times \cV$.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:recursive_to_explicit}}
The following auxiliary lemma plays a key role in converting the recursive bounds to explicit bounds.
\begin{lemma}\label{lemma:recursivebound1}
Let $a,b \in (0,1)$, $c_1,c_2 >0$ be constants. If sequences $\{u_t \}_{t\geq 0}$, $\{v_t \}_{t\geq 0}$ satisfies
\begin{align*}
    u_{t+1} \leq au_t + c_1 b^{t} + c_2,~v_{t+1} \leq av_t + c_1 t^2 b^{t} + c_2
\end{align*}
then it holds that
\begin{align*}
    u_t \leq a^t u_0 + c_1 t(a\lor b)^{t-1} + c_2\frac{1}{1-a}, ~v_t \leq a^t v_0 +  \frac{c_1}{3}t^3 (a\lor b)^{t-1} + c_2\frac{1}{1-a}.
\end{align*}
\end{lemma}
The proof of Lemma~\ref{lemma:recursivebound1}
is given in Section~\ref{section:auxiliarylemmas} in appendix. We can now apply Lemma~\ref{lemma:recursivebound1} to the recursive bounds \eqref{eq:recursiveproperty1}, \eqref{eq:recursiveproperty2} and \eqref{eq:recursiveproperty3}.

\begin{proof}[Proof of Lemma~\ref{lemma:recursive_to_explicit}]
The first convergence result for $\wb^t$ directly follows by Lemma~\ref{lemma:recursiveproperty} and \eqref{eq:recursiveproperty1}. To prove \eqref{eq:convergence_vt}, we first derive the convergence rate of $|\mathbf{1}^\top (\vb^{t} - \vb^*)|$. By \eqref{eq:convergence_wt} and Lemma~\ref{lemma:recursiveproperty}, we have
\begin{align*}
    |\mathbf{1}^\top (\vb^{t+1} - \vb^*)| &\leq \gamma_3|\mathbf{1}^\top (\vb^{t} - \vb^*)| + \alpha L |\mathbf{1}^\top\vb^*| \gamma_1^t \| \wb^0 -\wb^* \|_2  + 8\alpha L |\mathbf{1}^\top\vb^*|\rho^{-1}\gamma_1\eta_w \\
    &\quad + \alpha \sqrt{k} \eta_v.
\end{align*}
By Lemma~\ref{lemma:recursivebound1}, we have
\begin{align*}
    |\mathbf{1}^\top (\vb^{t} - \vb^*)| &\leq \gamma_3^t |\mathbf{1}^\top (\vb^{0} - \vb^*)| + t(\gamma_1\lor \gamma_3)^{t} \alpha L |\mathbf{1}^\top\vb^*|  \| \wb^0 -\wb^* \|_2 \\
    &\quad + \frac{8 L |\mathbf{1}^\top\vb^*|\rho^{-1}\gamma_1\eta_w  +  \sqrt{k} \eta_v}{\Delta + \kappa^2k}.
\end{align*}
Therefore, by Lemma~\ref{lemma:recursiveproperty} we have
\begin{align*}
    \| \vb^{t+1} -\vb^* \|_2^2 &\leq \gamma_2^2 \| \vb^{t} -\vb^* \|_2^2 + 2(\Delta^{-1} + 4\alpha )\alpha L^2  \|\vb^*\|_2^2 (\gamma_1^{2t} \| \wb^0 -\wb^* \|_2^2  + 64\rho^{-2}\gamma_1^{-4}\eta_w^2) \nonumber \\
    &\quad  + 12\alpha^2 \kappa^4 k \Bigg\{
    \gamma_3^{2t} |\mathbf{1}^\top (\vb^{0} - \vb^*)|^2 + t^2(\gamma_1\lor \gamma_3)^{2t} \alpha^2 L^2 |\mathbf{1}^\top\vb^*|^2  \| \wb^0 -\wb^* \|_2^2 \\
    & \quad + \bigg(\frac{8 L |\mathbf{1}^\top\vb^*|\rho^{-1}\gamma_1\eta_w +  \sqrt{k} \eta_v}{\Delta + \kappa^2k} \bigg)^2
    \Bigg\}\\
    &\quad+ \bigg( \frac{2\alpha}{\Delta} + 4 \alpha^2 \bigg) \eta_v^2\\
    &\leq \gamma_2^2 \| \vb^{t} -\vb^* \|_2^2 + R_1' t^2(\gamma_1\lor \gamma_3)^{2t}    + R_2'.
\end{align*}
where
\begin{align*}
    R_1' &= 2(\Delta^{-1} + 4\alpha )\alpha L^2  \|\vb^*\|_2^2 \| \wb^0 -\wb^* \|_2^2 + 12\alpha^2 \kappa^4 k [|\mathbf{1}^\top (\vb^{0} - \vb^*)|^2 \\
    &\quad+ \alpha^2 L^2 |\mathbf{1}^\top\vb^*|^2  \| \wb^0 -\wb^* \|_2^2],\\
    R_2' &= 128(\Delta^{-1} + 4\alpha )\alpha L^2  \|\vb^*\|_2^2 \rho^{-2}\gamma_1^{-4}\eta_w^2 + 12\alpha^2 \kappa^4 k \bigg(\frac{8 L |\mathbf{1}^\top\vb^*|\rho^{-1}\gamma_1\eta_w +  \sqrt{k} \eta_v}{\Delta + \kappa^2k} \bigg)^2 \\
    &\quad+ \bigg( \frac{2\alpha}{\Delta} + 4 \alpha^2 \bigg) \eta_v^2.
\end{align*}
We can then further apply the second bound in Lemma~\ref{lemma:recursivebound1} to the above inequality and obtain
\begin{align*}
    \| \vb^{t} -\vb^* \|_2 &\leq R_1 t^{3/2} (\gamma_1 \lor \gamma_2 \lor \gamma_3)^{t} + (R_2 + R_3 |\kappa|\sqrt{k}) (\eta_w + \eta_v),
\end{align*}
where
\begin{align*}
    R_1 &= \sqrt{2(\Delta^{-1} + 4\alpha )\alpha L^2}  \|\vb^*\|_2 \| \wb^0 -\wb^* \|_2 + 4\alpha \kappa^2 \sqrt{k} [|\mathbf{1}^\top (\vb^{0} - \vb^*)| + \| \vb^0 - \vb^* \|_2  \\
    &\quad + \alpha L |\mathbf{1}^\top\vb^*|  \| \wb^0 -\wb^* \|_2],\\
    R_2 &= \frac{1}{\Delta \sqrt{1 - 4\alpha \Delta}}\big[16 \sqrt{(1 + 4\alpha\Delta ) L^2 } \|\vb^*\|_2 \rho^{-1}\gamma_1^{-2} + 32\sqrt{\alpha\Delta} \kappa L |\mathbf{1}^\top \vb^*|\rho^{-1}\gamma_1 + \sqrt{2 + 4 \alpha \Delta}\big],\\
    R_3 &= \sqrt{\frac{12 \alpha}{\Delta(1 - 4\alpha \Delta)}}.
\end{align*}
This completes the proof of convergence of $v^t$.
\end{proof}

\section{Proofs of Lemmas in Appendix~\ref{section:appendix_proof_1}}\label{section:appendix_proof_3}

\subsection{Proof of Lemma~\ref{lemma:monotonecovineq}}
The following lemma gives a generalized version of Hoeffding's Covariance Identity \citep{hoeffding1940masstabinvariante}. This result is mentioned in \cite{sen1994impact}, and a version for bounded random variables is proved by \cite{cuadras2002covariance}. We give the proof of the version we present in Appendix~\ref{section:auxiliarylemmas}.
\begin{lemma}\label{lemma:hoeffdingidentity}
Let $X_1$, $X_2$ be two continuous random variables. For right-continuous monotonic functions $f$ and $g$ we have
\begin{align*}
    \Cov[f(X_1),g(X_2)] = \int_{\RR^2} \Cov[\ind(X_1 \leq x_1),\ind(X_2 \leq x_2)] \mathrm{d}f(x_1) \mathrm{d}f(x_2).
\end{align*}
\end{lemma}
We also need the following lemma, which is a Gaussian comparison inequality given by \cite{slepian1962one}.
\begin{lemma}[\cite{slepian1962one}]\label{lemma:slepian}
Let $\bX, \bY \in \RR^d$ be two centered Gaussian random vectors. If
$\EE (X_i^2) = \EE(Y_i^2)$ and $\EE(X_i X_j) \leq \EE(Y_i Y_j)$
for all $i,j=1,\ldots,d$,
then for any real numbers $\tau_1,\ldots, \tau_d$, we have
\begin{align*}
    \PP(X_1\leq \tau_1,\ldots, X_d\leq \tau_d) \leq \PP(Y_1\leq \tau_1,\ldots, Y_d\leq \tau_d).
\end{align*}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lemma:monotonecovineq}]
It directly follows by Lemma~\ref{lemma:hoeffdingidentity} and Lemma~\ref{lemma:slepian} that $\Cov[f(Z_1),g(Z_2)]$ is an increasing function of $\theta$. Moreover, let $U_1$ and $U_2$ be independent standard Gaussian random variables. Then it is easy to check that
$$
\frac{\mathrm{d}}{\mathrm{d} \theta} \PP(U_1 \leq x_1, \theta U_1 + \sqrt{1-\theta^2} U_2 \leq x_2) \bigg|_{\theta = 0} > 0
$$
for all $x_1,x_2\in \RR$. Therefore for non-trivial increasing functions $f$ and $g$, by Lemma~\ref{lemma:hoeffdingidentity} and the definition of Lebesgue-Stieltjes integration, we have $\Cov[f(Z_1),g(Z_2)] > 0$.
\end{proof}

\section{Proofs of Lemmas in Appendix~\ref{section:appendix_proof_2}}\label{section:appendix_proof_4}

\subsection{Proof of Lemma~\ref{lemma:uniformbound1}}
\begin{proof}[Proof of Lemma~\ref{lemma:uniformbound1}]
Let $\cN_1 = \cN(S^{r-1},1/8)$, $\cN_2 = \cN(S^{k-1},1/8)$ be $1/8$-nets covering $S^{r-1}$ and $S^{k-1}$ respectively. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_1| \leq 17^r$ and $|\cN_2| \leq 17^k$.
Denote
$$
A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')= \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  |\hat{b}_j\hat{\ab}^\top \Pb_j\xb_i| \cdot \Bigg| \sum_{j'=1}^k \hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i \Bigg|.
$$
It is easy to see that $\sum_{j'=1}^k  \hat{b}'_{j'}\hat{\ab}'^\top \Pb_{j'}\xb_i$, $i=1,\ldots,n$ are independent standard normal random variables. Moreover, for each $i=1,\ldots,n$, $\hat{\ab}^\top \Pb_j\xb_i$, $j=1,\ldots,k$ are independent standard Gaussian random vectors. By triangle inequality we have
\begin{align*}
   \Bigg\| \sum_{j=1}^k  |\hat{b}_j\hat{\ab}^\top \Pb_j\xb_i| \Bigg\|_{\psi_2} \leq C_1 \| \hat{\mathbf{b}} \|_1 \leq C_1 \sqrt{k},
\end{align*}
where $C_1$ is an absolute constant. Therefore, by Lemma~\ref{lemma:subgaussianproduct} we have
\begin{align*}
    \Bigg\| \sum_{j=1}^k  |\hat{b}_j\hat{\ab}^\top \Pb_j\xb_i| \cdot \Bigg| \sum_{j'=1}^k \hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i \Bigg| \Bigg\|_{\psi_1} \leq C_2 \sqrt{k},
\end{align*}
where $C_2$ is an absolute constant. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta_1$ we have
\begin{align*}
    | A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - \EE[A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')] | \leq C_3 \sqrt{k}
    \sqrt{\frac{(r+k)\log(34/\delta_1)}{n}}
\end{align*}
for all $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, where $C_3$ is an absolute constant. By the assumptions on $n$ we have
\begin{align*}
    | A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - \EE[A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')] | \leq C_3 \sqrt{k}.
\end{align*}
Moreover, by the definition of $\psi_1$-norm we have
\begin{align*}
    \EE[A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')] &\leq \| A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') \|_{\psi_1} \leq C_2\sqrt{k}.
\end{align*}
Therefore
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_4 \sqrt{k}
\end{align*}
for all $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, where $C_4$ is an absolute constant.

For any $\ab,\ab' \in S^{r-1}$ and $\mathbf{b},\mathbf{b}'\in S^{k-1}$, there exists $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$ such that
\begin{align*}
    \|\ab - \hat{\ab}\|_2, \|\ab' - \hat{\ab}'\|_2, \| \mathbf{b} - \hat{\mathbf{b}} \|_2, \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \leq 1/8.
\end{align*}
Therefore
\begin{align}\label{eq:uniformbound1eq1}
    A(\ab,\ab',\mathbf{b},\mathbf{b}') \leq  C_4\sqrt{k} +  I_1 + I_2 + I_3 + I_4,
\end{align}
where
\begin{align*}
    &I_1 = |A(\ab,\ab', \mathbf{b},\mathbf{b}') - A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}')|,\\
    &I_2 = |A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}') - A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_3 = |A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_4 = |A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|.
\end{align*}
Let
\begin{align*}
    \overline{A} = \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} A(\ab,\ab', \mathbf{b},\mathbf{b}').
\end{align*}
Then we have
\begin{align*}
    I_1 &\leq A(\ab,\ab', \mathbf{b},\mathbf{b}' - \hat{\mathbf{b}}')\\
    &= \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 A\bigg(\ab,\ab', \mathbf{b},\frac{\mathbf{b}' - \hat{\mathbf{b}}'}{\| \mathbf{b}' - \hat{\mathbf{b}}' \|_2}\bigg)\\
    &\leq \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \overline{A}.
\end{align*}
Similarly, we have
\begin{align*}
    &I_2 \leq \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \overline{A},\\
    &I_3 \leq \| \ab' - \hat{\ab}' \|_2 \overline{A},\\
    &I_4 \leq \| \ab - \hat{\ab} \|_2 \overline{A}.
\end{align*}
Plugging the inequalities above into \eqref{eq:uniformbound1eq1} gives
\begin{align*}
    \overline{A} \leq C_4\sqrt{k} + \frac{1}{2} \overline{A}.
\end{align*}
Therefore we have $\overline{A} \leq 2C_4\sqrt{k}$. This completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:uniformbound2}}
\begin{proof}[Proof of Lemma~\ref{lemma:uniformbound2}]
Let $\cN_1 = \cN(S^{r-1},1/8)$, $\cN_2 = \cN(S^{k-1},1/8)$ be $1/8$-nets covering $S^{r-1}$ and $S^{k-1}$ respectively. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_1| \leq 17^r$ and $|\cN_2| \leq 17^k$. Denote
$$
A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')= \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  \hat{b}_j\sigma(\hat{\ab}^\top \Pb_j\xb_i) \cdot \sum_{j'=1}^k \hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i.
$$
For any $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, by Lemma~\ref{lemma:sigma(x)subgaussian}, $\sigma(\hat{\ab}^\top \Pb_j\xb_i)$, $j=1,\ldots, r$ are independent sub-Gaussian random variables with $\| \sigma(\hat{\ab}^\top \Pb_j\xb_i)\|_{\psi_2} \leq C_1 L$ for some absolute constant $C_1$. Therefore by triangle inequality, we have
\begin{align*}
    \Bigg\| \sum_{j=1}^k  \hat{b}_j \sigma(\hat{\ab}^\top \Pb_j\xb_i) \Bigg\|_{\psi_2} \leq C_2 L\sqrt{k},
\end{align*}
where $C_2$ is an absolute constant. Moreover, since $\Pb_{j'} \xb_i$, $j'=1,\ldots,k$ are independent Gaussian random vectors, we have
\begin{align*}
    \Bigg\| \sum_{j'=1}^k \hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i \Bigg\|_{\psi_2} \leq C_3
\end{align*}
for some absolute constant $C_3$. Therefore, by Lemma~\ref{lemma:subgaussianproduct} we have $\|A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')\|_{\psi_1} \leq C_4 L \sqrt{k}$, where $C_4$ is an absolute constant. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta_2/2$, we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - \EE A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') | \leq C_5L \sqrt{k} \sqrt{\frac{(r+k)\log(68/\delta_2)}{n}}
\end{align*}
for all $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, where $C_5$ is an absolute constant. Therefore by the assumptions on $n$ we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_6L \sqrt{k} + |\EE A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,
\end{align*}
where $C_6$ is an absolute constant. Moreover, by the definition of $\psi_1$-norm we have
\begin{align*}
    \EE A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') \leq \| A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') \|_{\psi_1} \leq C_4L \sqrt{k}.
\end{align*}
Therefore we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_7 L \sqrt{k}
\end{align*}
for some absolute constant $C_7$.
Now for any  $\ab,\ab' \in S^{r-1}$ and $\mathbf{b},\mathbf{b}'\in S^{k-1}$, there exists $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$ such that
\begin{align*}
    \|\ab - \hat{\ab}\|_2, \|\ab' - \hat{\ab}'\|_2, \| \mathbf{b} - \hat{\mathbf{b}} \|_2, \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \leq 1/8.
\end{align*}
Therefore
\begin{align*}
    A(\ab,\ab',\mathbf{b},\mathbf{b}') \leq  C_7 L \sqrt{k} +  I_1 + I_2 + I_3 + I_4,
\end{align*}
where
\begin{align*}
    &I_1 = |A(\ab,\ab', \mathbf{b},\mathbf{b}') - A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}')|,\\
    &I_2 = |A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}') - A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_3 = |A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_4 = |A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|.
\end{align*}
Let
\begin{align*}
    \overline{A} = \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} A(\ab,\ab', \mathbf{b},\mathbf{b}').
\end{align*}
Since $A(\ab,\ab',\mathbf{b},\mathbf{b}')$ is linear in $\ab'$, $\mathbf{b}$ and $\mathbf{b}'$, we have
\begin{align*}
    I_1 \leq \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \overline{A},~ I_2 \leq \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \overline{A},~ I_3 \leq \| \ab' - \hat{\ab}' \|_2 \overline{A}
\end{align*}
Moreover, by the Lipschitz continuity of $\sigma(\cdot)$, we have
\begin{align*}
    I_4 \leq \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  |\hat{b}_j (\ab - \hat{\ab})^\top \Pb_j\xb_i| \cdot \Bigg|\sum_{j'=1}^k \hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i\Bigg|.
\end{align*}
Therefore by Lemma~\ref{lemma:uniformbound1} with $\delta_1 = \delta_2/2$ we have
\begin{align*}
    I_4 \leq C_8 \sqrt{k} \| \ab - \ab' \|_2
\end{align*}
for some absolute constant $C_8$. Summing the bounds on $I_1,\ldots,I_4$ gives
\begin{align*}
    \overline{A} \leq C_{9}L \sqrt{k} + \overline{A}/2,
\end{align*}
where $C_9$ is an absolute constant. Therefore we have $\overline{A} \leq 2C_{9} L \sqrt{k} $. This completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:uniformbound2.5}}
\begin{proof}[Proof of Lemma~\ref{lemma:uniformbound2.5}]
Let $\cN_1 = \cN(S^{r-1},1/8)$, $\cN_2 = \cN(S^{k-1},1/8)$ be $1/8$-nets covering $S^{r-1}$ and $S^{k-1}$ respectively. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_1| \leq 17^r$ and $|\cN_2| \leq 17^k$. Denote
$$
A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')= \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  |\hat{b}_j\hat{\ab}^\top \Pb_j\xb_i| \cdot \sum_{j'=1}^k |\hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i|.
$$
For any $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, by triangle inequality, we have
\begin{align*}
    \Bigg\| \sum_{j=1}^k \hat{b}_{j'}\hat{\ab}^\top \Pb_{j}\xb_i \Bigg\|_{\psi_2}, \Bigg\| \sum_{j'=1}^k \hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i \Bigg\|_{\psi_2} \leq C_1 \sqrt{k}
\end{align*}
for some absolute constant $C_1$. Therefore, by Lemma~\ref{lemma:subgaussianproduct} we have $\|A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')\|_{\psi_1} \leq C_2 k$, where $C_2$ is an absolute constant. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta_3$, we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - \EE[A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')]| \leq C_3 k \sqrt{\frac{(r+k)\log(34/\delta_3)}{n}}
\end{align*}
for all $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, where $C_3$ is an absolute constant. Therefore by the assumptions on $n$ we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_3 k + |\EE [A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')]|.
\end{align*}
By the definition of $\psi_1$-norm we have
\begin{align*}
    \EE [A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')] \leq \| A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') \|_{\psi_1} \leq C_2 k.
\end{align*}
Therefore we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_4k,
\end{align*}
where $C_4$ is an absolute constant. Now for any  $\ab,\ab' \in S^{r-1}$ and $\mathbf{b},\mathbf{b}'\in S^{k-1}$, there exists $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$ such that
\begin{align*}
    \|\ab - \hat{\ab}\|_2, \|\ab' - \hat{\ab}'\|_2, \| \mathbf{b} - \hat{\mathbf{b}} \|_2, \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \leq 1/8.
\end{align*}
Therefore
\begin{align*}
    A(\ab,\ab',\mathbf{b},\mathbf{b}') \leq  C_4 k +  I_1 + I_2 + I_3 + I_4,
\end{align*}
where
\begin{align*}
    &I_1 = |A(\ab,\ab', \mathbf{b},\mathbf{b}') - A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}')|,\\
    &I_2 = |A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}') - A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_3 = |A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_4 = |A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|.
\end{align*}
Let
\begin{align*}
    \overline{A} = \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} A(\ab,\ab', \mathbf{b},\mathbf{b}').
\end{align*}
Since $A(\ab,\ab',\mathbf{b},\mathbf{b}')$ is Lipschitz continuous in $\ab$, $\ab'$, $\mathbf{b}$ and $\mathbf{b}'$, we have
\begin{align*}
    I_1 \leq \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \overline{A},~ I_2 \leq \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \overline{A},~ I_3 \leq \| \ab' - \hat{\ab}' \|_2 \overline{A},~I_4 \leq \| \ab - \hat{\ab} \|_2 \overline{A}.
\end{align*}
Therefore,
\begin{align*}
    \overline{A} \leq C_4 k + \overline{A}/2,
\end{align*}
Therefore we have $\overline{A} \leq 2C_{4}k$. This completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:uniformbound3}}
\begin{proof}[Proof of Lemma~\ref{lemma:uniformbound3}]
Let $\cN_1 = \cN(S^{r-1},1/8)$, $\cN_2 = \cN(S^{k-1},1/8)$ be $1/8$-nets covering $S^{r-1}$ and $S^{k-1}$ respectively. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_1| \leq 17^r$ and $|\cN_2| \leq 17^k$. Denote
$$
A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')= \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  |\hat{b}_j\hat{\ab}^\top \Pb_j\xb_i| \cdot \sum_{j'=1}^k |\hat{b}_{j'}'\sigma('\hat{\ab}'^\top \Pb_{j'}\xb_i)|.
$$
For any $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, by Lemma~\ref{lemma:sigma(x)subgaussian}, $\sigma(\hat{\ab}'^\top \Pb_{j'}\xb_i)$, $j'=1,\ldots, r$ are independent sub-Gaussian random variables with $\| \sigma(\hat{\ab}'^\top \Pb_j\xb_i)\|_{\psi_2} \leq C_1 L$ for some absolute constant $C_1$. Therefore by triangle inequality, we have
\begin{align*}
    \Bigg\| \sum_{j=1}^k  |\hat{b}_j \sigma(\hat{\ab}^\top \Pb_j\xb_i)| \Bigg\|_{\psi_2} \leq C_2 L \sqrt{k},
\end{align*}
where $C_2$ is an absolute constant. Similarly, we have
\begin{align*}
    \Bigg\| \sum_{j'=1}^k |\hat{b}_{j'}'\hat{\ab}'^\top \Pb_{j'}\xb_i| \Bigg\|_{\psi_2} \leq C_3 \sqrt{k}
\end{align*}
for some absolute constant $C_3$. Therefore, by Lemma~\ref{lemma:subgaussianproduct} we have $\|A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')\|_{\psi_1} \leq C_4 L k$, where $C_4$ is an absolute constant. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta_4/2$, we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - \EE[A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')]| \leq C_5L k \sqrt{\frac{(r+k)\log(68/\delta_4)}{n}}
\end{align*}
for all $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, where $C_5$ is an absolute constant. Therefore by the assumptions on $n$ we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_5 L k + |\EE [A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')]|.
\end{align*}
By the definition of $\psi_1$-norm we have
\begin{align*}
    \EE [A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')] \leq \| A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') \|_{\psi_1} \leq C_4 L k.
\end{align*}
Therefore we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_6 L k
\end{align*}
for some absolute constant $C_6$.
Now for any  $\ab,\ab' \in S^{r-1}$ and $\mathbf{b},\mathbf{b}'\in S^{k-1}$, there exists $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$ such that
\begin{align*}
    \|\ab - \hat{\ab}\|_2, \|\ab' - \hat{\ab}'\|_2, \| \mathbf{b} - \hat{\mathbf{b}} \|_2, \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \leq 1/8.
\end{align*}
Therefore
\begin{align*}
    A(\ab,\ab',\mathbf{b},\mathbf{b}') \leq  C_6 L k +  I_1 + I_2 + I_3 + I_4,
\end{align*}
where
\begin{align*}
    &I_1 = |A(\ab,\ab', \mathbf{b},\mathbf{b}') - A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}')|,\\
    &I_2 = |A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}') - A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_3 = |A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_4 = |A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|.
\end{align*}
Let
\begin{align*}
    \overline{A} = \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} A(\ab,\ab', \mathbf{b},\mathbf{b}').
\end{align*}
Since $A(\ab,\ab',\mathbf{b},\mathbf{b}')$ is Lipschitz continuous in $\ab$, $\mathbf{b}$ and $\mathbf{b}'$, we have
\begin{align*}
    I_1 \leq \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \overline{A},~ I_2 \leq \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \overline{A},~ I_4 \leq \| \ab - \hat{\ab} \|_2 \overline{A}.
\end{align*}
Moreover, by the Lipschitz continuity of $\sigma(\cdot)$, we have
\begin{align*}
    I_3 \leq \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  |\hat{b}_j \ab^\top \Pb_j\xb_i| \cdot \sum_{j'=1}^k |\hat{b}_{j'}'( \ab' - \hat{\ab}')^\top \Pb_{j'}\xb_i|.
\end{align*}
Therefore by Lemma~\ref{lemma:uniformbound2.5} with $\delta_3 = \delta_4/2$ we have
\begin{align*}
    I_3 \leq C_7 k \| \ab' - \hat{\ab}' \|_2
\end{align*}
for some absolute constant $C_7$. Since $L \geq 1$, summing the bounds on $I_1,\ldots,I_4$ gives
\begin{align*}
    \overline{A} \leq C_{8} L k + \overline{A}/2,
\end{align*}
where $C_8$ is an absolute constant. Therefore we have $\overline{A} \leq 2C_{8} L k$. This completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:uniformbound4}}
\begin{proof}[Proof of Lemma~\ref{lemma:uniformbound4}]
Let $\cN_1 = \cN(S^{r-1},1/8)$, $\cN_2 = \cN(S^{k-1},1/8)$ be $1/8$-nets covering $S^{r-1}$ and $S^{k-1}$ respectively. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_1| \leq 17^r$ and $|\cN_2| \leq 17^k$. Denote
$$
A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')= \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  \hat{b}_j \sigma( \hat{\ab}^\top \Pb_j\xb_i) \cdot \sum_{j'=1}^k \hat{b}_{j'}'\sigma('\hat{\ab}'^\top \Pb_{j'}\xb_i).
$$
For any $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, similar to the proof of Lemma~\ref{lemma:uniformbound3}, we have
\begin{align*}
    \Bigg\| \sum_{j=1}^k  \hat{b}_j \sigma(\hat{\ab}^\top \Pb_j\xb_i) \Bigg\|_{\psi_2}, \Bigg\| \sum_{j'=1}^k  \hat{b}_{j'}' \sigma(\hat{\ab}'^\top \Pb_{j'}\xb_i) \Bigg\|_{\psi_2} \leq C_1 L \sqrt{k},
\end{align*}
where $C_1$ is an absolute constant. Therefore, by Lemma~\ref{lemma:subgaussianproduct} we have $\|A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')\|_{\psi_1} \leq C_2L^2 k$, where $C_2$ is an absolute constant. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta_5/3$, we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - \EE[A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')]| \leq C_3L^2 k \sqrt{\frac{(r+k)\log(102/\delta_5)}{n}}
\end{align*}
for all $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$, where $C_3$ is an absolute constant. Therefore by the assumptions on $n$ we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_3 L^2 k + |\EE [A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')]|.
\end{align*}
Similar to the proofs of Lemma~\ref{lemma:uniformbound1}-\ref{lemma:uniformbound3}, by the definition of $\psi_1$-norm we have
\begin{align*}
    \EE [A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')] \leq \| A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') \|_{\psi_1} \leq C_2L^2k.
\end{align*}
Therefore we have
\begin{align*}
    |A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')| \leq C_4L^2k
\end{align*}
for some absolute constant $C_4$.
Now for any  $\ab,\ab' \in S^{r-1}$ and $\mathbf{b},\mathbf{b}'\in S^{k-1}$, there exists $\hat{\ab},\hat{\ab}'\in \cN_1$ and $\hat{\mathbf{b}},\hat{\mathbf{b}}'\in \cN_2$ such that
\begin{align*}
    \|\ab - \hat{\ab}\|_2, \|\ab' - \hat{\ab}'\|_2, \| \mathbf{b} - \hat{\mathbf{b}} \|_2, \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \leq 1/8.
\end{align*}
Therefore
\begin{align*}
    A(\ab,\ab',\mathbf{b},\mathbf{b}') \leq  C_4 L^2 k +  I_1 + I_2 + I_3 + I_4,
\end{align*}
where
\begin{align*}
    &I_1 = |A(\ab,\ab', \mathbf{b},\mathbf{b}') - A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}')|,\\
    &I_2 = |A(\ab,\ab', \mathbf{b},\hat{\mathbf{b}}') - A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_3 = |A(\ab,\ab', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|,\\
    &I_4 = |A(\ab,\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}') - A(\hat{\ab},\hat{\ab}', \hat{\mathbf{b}},\hat{\mathbf{b}}')|.
\end{align*}
Let
\begin{align*}
    \overline{A} = \sup_{\substack{\ab,\ab' \in S^{r-1}\\ \mathbf{b},\mathbf{b}'\in S^{k-1}}} A(\ab,\ab', \mathbf{b},\mathbf{b}').
\end{align*}
Since $A(\ab,\ab',\mathbf{b},\mathbf{b}')$ is linear in $\mathbf{b}$ and $\mathbf{b}'$, we have
\begin{align*}
    I_1 \leq \| \mathbf{b}' - \hat{\mathbf{b}}' \|_2 \overline{A},~ I_2 \leq \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \overline{A}.
\end{align*}
Moreover, by the Lipschitz continuity of $\sigma(\cdot)$, we have
\begin{align*}
    &I_3 \leq \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  |\hat{b}_j \sigma(\ab^\top \Pb_j\xb_i)| \cdot \sum_{j'=1}^k |\hat{b}_{j'}'( \ab' - \hat{\ab}')^\top \Pb_{j'}\xb_i|,\\
    &I_4 \leq \frac{1}{n}\sum_{i=1}^n \sum_{j=1}^k  |\hat{b}_j (\ab - \hat{\ab})^\top \Pb_j\xb_i)| \cdot \sum_{j'=1}^k |\hat{b}_{j'}' \sigma( \hat{\ab}'^\top \Pb_{j'}\xb_i)|,
\end{align*}
Therefore by Lemma~\ref{lemma:uniformbound3} with $\delta_4 = 2\delta_5/3$ we have
\begin{align*}
    I_3 \leq C_5 k \| \ab' - \hat{\ab}' \|_2,~I_4 \leq C_5 k \| \ab - \hat{\ab} \|_2
\end{align*}
for some absolute constant $C_5$. Since we have $ L \geq 1$, summing the bounds on $I_1,\ldots,I_4$ gives
\begin{align*}
    \overline{A} \leq C_{6} L^2 k + \overline{A}/2,
\end{align*}
where $C_6$ is an absolute constant. Therefore we have $\overline{A} \leq 2C_{6} L^2 k$. This completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:uniformbound5}}
\begin{proof}[Proof of Lemma~\ref{lemma:uniformbound5}]
Let $\cN_1 = \cN(S^{r-1},1/4)$, $\cN_2 = \cN(S^{k-1},1/4)$ be $1/4$-nets covering $S^{r-1}$ and $S^{k-1}$ respectively. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_1| \leq 9^r$ and $|\cN_2| \leq 9^k$. Denote
$$
A(\hat{\ab}, \hat{\mathbf{b}})= \frac{1}{n}\sum_{i=1}^n \epsilon_i \cdot \sum_{j=1}^k  \hat{b}_j \hat{\ab}^\top \Pb_j\xb_i.
$$
For any $\hat{\ab} \in \cN_1$ and $\hat{\mathbf{b}} \in \cN_2$, since $\Pb_{j} \xb_i$, $j=1,\ldots,k$ are independent Gaussian random vectors, we have
\begin{align*}
    \Bigg\| \sum_{j=1}^k \hat{b}_{j}\hat{\ab}^\top \Pb_{j}\xb_i \Bigg\|_{\psi_2} \leq C_1
\end{align*}
for some absolute constant $C_1$. Therefore by Lemma~\ref{lemma:subgaussianproduct} we have $\|A(\hat{\ab}, \hat{\mathbf{b}})\|_{\psi_1} \leq C_2 \nu$, where $C_2$ is an absolute constant. Since $\EE A(\hat{\ab}, \hat{\mathbf{b}}) = 0$, by Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta_6$, we have
\begin{align*}
    |A(\hat{\ab}, \hat{\mathbf{b}})| \leq C_3 \nu \sqrt{\frac{(r+k)\log(18/\delta_6)}{n}}
\end{align*}
for all $\hat{\ab}\in \cN_1$ and $\hat{\mathbf{b}}\in \cN_2$, where $C_3$ is an absolute constant. Therefore by the assumptions on $n$ we have
\begin{align*}
    |A(\hat{\ab}, \hat{\mathbf{b}})| \leq C_3 \nu.
\end{align*}
Now for any  $\ab \in S^{r-1}$ and $\mathbf{b} \in S^{k-1}$, there exists $\hat{\ab}\in \cN_1$ and $\hat{\mathbf{b}}\in \cN_2$ such that
\begin{align*}
    \|\ab - \hat{\ab}\|_2, \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \leq 1/4.
\end{align*}
Therefore
\begin{align}\label{eq:lemmauniformbound5proof1}
    A(\ab,\mathbf{b}) \leq  C_3 \nu +  I_1 + I_2,
\end{align}
where
\begin{align*}
    I_1 = |A(\ab, \mathbf{b}) - A(\ab, \hat{\mathbf{b}})|,~I_2 = |A(\ab, \hat{\mathbf{b}}) - A(\hat{\ab}, \hat{\mathbf{b}})|.
\end{align*}
Let
\begin{align*}
    \overline{A} = \sup_{\substack{\ab \in S^{r-1}\\ \mathbf{b}\in S^{k-1}}} A(\ab, \mathbf{b}).
\end{align*}
Since $A(\ab, \mathbf{b})$ is linear in $\ab$ and $\mathbf{b}$, we have
\begin{align*}
    I_1 \leq \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \overline{A},~ I_2 \leq \| \ab - \hat{\ab} \|_2 \overline{A}.
\end{align*}
Plugging the two inequalities above into \eqref{eq:lemmauniformbound5proof1} gives
\begin{align*}
    \overline{A} \leq C_3\nu + \overline{A}/2.
\end{align*}
Therefore we have $\overline{A} \leq 2C_{3}\nu $. This completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:uniformbound6}}
\begin{proof}[Proof of Lemma~\ref{lemma:uniformbound6}]
Let $\cN_1 = \cN(S^{r-1},1/4)$, $\cN_2 = \cN(S^{k-1},1/4)$ be $1/4$-nets covering $S^{r-1}$ and $S^{k-1}$ respectively. Then by Lemma~5.2 in \cite{vershynin2010introduction} we have $|\cN_1| \leq 9^r$ and $|\cN_2| \leq 9^k$. Denote
$$
A(\hat{\ab}, \hat{\mathbf{b}})= \frac{1}{n}\sum_{i=1}^n |\epsilon_i| \cdot \sum_{j=1}^k  |\hat{b}_j \hat{\ab}^\top \Pb_j\xb_i|.
$$
For any $\hat{\ab} \in \cN_1$ and $\hat{\mathbf{b}} \in \cN_2$, since $\Pb_{j} \xb_i$, $j=1,\ldots,k$ are independent Gaussian random vectors, by triangle inequality we have
\begin{align*}
    \Bigg\| \sum_{j=1}^k |\hat{b}_{j}\hat{\ab}^\top \Pb_{j}\xb_i| \Bigg\|_{\psi_2} \leq C_1 \sqrt{k}
\end{align*}
for some absolute constant $C_1$. Therefore by Lemma~\ref{lemma:subgaussianproduct} we have $\|A(\hat{\ab}, \hat{\mathbf{b}})\|_{\psi_1} \leq C_2 \nu \sqrt{k}$, where $C_2$ is an absolute constant. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta_7$, we have
\begin{align*}
    |A(\hat{\ab}, \hat{\mathbf{b}}) - \EE [A(\hat{\ab}, \hat{\mathbf{b}})]| \leq C_3 \nu \sqrt{k} \sqrt{\frac{(r+k)\log(18/\delta_7)}{n}}
\end{align*}
for all $\hat{\ab}\in \cN_1$ and $\hat{\mathbf{b}}\in \cN_2$, where $C_3$ is an absolute constant. Therefore by the assumptions on $n$ we have
\begin{align*}
    |A(\hat{\ab}, \hat{\mathbf{b}})| \leq C_3 \nu \sqrt{k} + |\EE [A(\hat{\ab}, \hat{\mathbf{b}})]|.
\end{align*}
By the definition of $\psi_1$-norm, we have
\begin{align*}
    \EE [A(\hat{\ab}, \hat{\mathbf{b}})] \leq \| A(\hat{\ab}, \hat{\mathbf{b}}) \|_{\psi_1} \leq C_2 \nu \sqrt{k}.
\end{align*}
Therefore we have
\begin{align*}
    |A(\hat{\ab}, \hat{\mathbf{b}})| \leq C_4 \nu \sqrt{k}
\end{align*}
for some absolute constant $C_4$.
Now for any  $\ab \in S^{r-1}$ and $\mathbf{b} \in S^{k-1}$, there exists $\hat{\ab}\in \cN_1$ and $\hat{\mathbf{b}}\in \cN_2$ such that
\begin{align*}
    \|\ab - \hat{\ab}\|_2, \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \leq 1/4.
\end{align*}
Therefore
\begin{align}\label{eq:lemmauniformbound6proof1}
    A(\ab,\mathbf{b}) \leq  C_4 \nu \sqrt{k} +  I_1 + I_2,
\end{align}
where
\begin{align*}
    I_1 = |A(\ab, \mathbf{b}) - A(\ab, \hat{\mathbf{b}})|,~I_2 = |A(\ab, \hat{\mathbf{b}}) - A(\hat{\ab}, \hat{\mathbf{b}})|.
\end{align*}
Let
\begin{align*}
    \overline{A} = \sup_{\substack{\ab \in S^{r-1}\\ \mathbf{b}\in S^{k-1}}} A(\ab, \mathbf{b}).
\end{align*}
Since $A(\ab, \mathbf{b})$ is Lipschitz continuous in $\ab$ and $\mathbf{b}$, we have
\begin{align*}
    I_1 \leq \| \mathbf{b} - \hat{\mathbf{b}} \|_2 \overline{A},~ I_2 \leq \| \ab - \hat{\ab} \|_2 \overline{A}.
\end{align*}
Plugging the two inequalities above into \eqref{eq:lemmauniformbound6proof1} gives
\begin{align*}
    \overline{A} \leq C_4\nu\sqrt{k} + \overline{A}/2.
\end{align*}
Therefore we have $\overline{A} \leq 2C_{4}\nu\sqrt{k} $. This completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:sigma(x)subgaussian}}
\begin{proof}[Proof of Lemma~\ref{lemma:sigma(x)subgaussian}]
By triangle inequality we have
\begin{align*}
    |\sigma(z)| \leq |\sigma(z) - \sigma(0)| + |\sigma(0) | \leq |z| + |\sigma(0) |.
\end{align*}
Since $\| z \|_{\psi_2} \leq 1$, by the definition of $\psi_2$-norm we have
\begin{align*}
    \|\sigma(z)\|_{\psi_2} = \sup_{p\geq 1} p^{-1/2} \{ \EE[|\sigma(z)|^p] \}^{1/p} \leq \sup_{p\geq 1} p^{-1/2} \{ \EE[(|z| + |\sigma(0)|)^p] \}^{1/p}\leq 2[1+|\sigma(0)|].
\end{align*}
Similarly, we have
\begin{align*}
    |\sigma(z) - \kappa| \leq |\sigma(z) - \sigma(0)| + |\sigma(0) - \kappa| \leq |z| + |\sigma(0) - \kappa|.
\end{align*}
By the definition of $\psi_2$-norm, we have
\begin{align*}
    \|\sigma(z) - \kappa \|_{\psi_2} \leq 2[1 + |\sigma(0) - \kappa|].
\end{align*}
\end{proof}

\subsection{Proof of Lemma~\ref{lemma:philipschitz}}
\begin{proof}[Proof of Lemma~\ref{lemma:philipschitz}]
Let $\wb_1,\wb_2$ be two distinct unit vectors, and $U_1$, $U_2$ be jointly Gaussian random variables with $\EE(U_1) = \EE(U_2) = 0$, $\EE(U_1^2) = \EE(U_2^2) = 1$ and $\EE(U_1 U_2) = \frac{\wb^{\top}(\wb_1- \wb_2)}{\|\wb_1 - \wb_2\|_2}\in [-1,1]$. Then by the definition of $\phi$, we have
\begin{align*}
    |\phi(\wb,\wb_1) - \phi(\wb,\wb_2)| &= \big|\EE_{\zb\sim N(\mathbf{0},\Ib)} \big[\sigma\big(\wb^{\top}\zb\big) \sigma\big(\wb_1^{\top}\zb\big)\big] - \EE_{\zb\sim N(\mathbf{0},\Ib)}\big[\sigma\big(\wb^{\top}\zb\big) \sigma\big(\wb_2^{t\top}\zb\big)\big]\big| \\
    & \leq \EE_{\zb\sim N(\mathbf{0},\Ib)} [ |\sigma(\wb^{\top}\zb)|\cdot  | (\wb_1 - \wb_2)^\top \zb | ]\\
    & \leq |\sigma(0)| \|\wb_1 - \wb_2\|_2 \EE(|U_2|) + \|\wb_1 - \wb_2\|_2\EE(|U_1|\cdot |U_2| )\\
    & \leq [1 + |\sigma(0)|] \|\wb^* - \wb^t\|_2\\
    & = L \|\wb^* - \wb^t\|_2.
\end{align*}
This completes the proof.
\end{proof}

\section{Conclusions and Future Work}\label{sec:conclusions}

We propose a new algorithm namely approximate gradient descent for training CNNs, and show that, with high probability, the proposed algorithm with random initialization can recover the ground-truth parameters up to statistical precision at a linear convergence rate .
Compared with previous results, our result applies to a class of monotonic and Lipschitz continuous activation functions including ReLU, Leaky ReLU, Sigmod and Softplus etc. Moreover, our algorithm achieves better sample complexity in the dependency of the number of hidden nodes and filter size. In particular, our result matches the information-theoretic lower bound for learning one-hidden-layer CNNs with linear activation functions, suggesting that our sample complexity is tight. Numerical experiments on synthetic data corroborate our theory. Our algorithms and theory can be extended to learn one-hidden-layer CNNs with overlapping filters. We leave it as a future work. It is also of great importance to extend the current result to deeper CNNs with multiple convolution filters
\section{Introduction}

Deep learning is one of the key research areas in modern artificial intelligence.
Deep neural networks have been successfully applied to various fields including image processing \citep{krizhevsky2012imagenet}, speech recognition \citep{hinton2012deep} and reinforcement learning \citep{silver2016mastering}. Despite the remarkable success in a broad range of applications, theoretical understandings of neural network models remain largely incomplete: the high non-convexity of neural networks makes convergence analysis of learning algorithms very difficult; numerous practically successful choices of the activation function, twists of the training process and variants of the network structure make neural networks even more mysterious.

One of the fundamental problems in learning neural networks  is parameter recovery, where we assume the data are generated from a ``teacher'' network, and the task is to estimate the ground-truth parameters of the teacher network based on the generated data.
Recently, a line of research \citep{zhong2017recovery, fu2018local,zhang2018learning} gives parameter recovery guarantees for gradient descent based on the analysis of local convexity and smoothness properties of the square loss function. The results of \citet{zhong2017recovery} and \citet{fu2018local} hold for various activation functions except ReLU activation function, while \citet{zhang2018learning} prove the corresponding result for ReLU. Their results are for fully connected neural networks and their analysis requires accurate knowledge of second-layer parameters. For instance, \citet{fu2018local} and \citet{zhang2018learning} directly assume that the second-layer parameters are known, while  \citet{zhong2017recovery} reduce the second-layer parameters to be $\pm 1$'s with the homogeneity assumption, and then exactly recovers them with a tensor initialization algorithm. Moreover, it may not be easy to generalize the local convexity and smoothness argument to other algorithms that are not based on the exact gradient of the loss function. Another line of research \citep{brutzkus2017globally, du2017gradient, goel2018learning, du2018improved} focuses on convolutional neural networks with ReLU activation functions. \citet{brutzkus2017globally, du2017gradient} provide convergence analysis for gradient descent on parameters of both layers, while \citet{goel2018learning, du2018improved} proposed new algorithms to learn single-hidden-layer CNNs. However, these results heavily rely on the exact calculation of the population gradient for ReLU networks, and do not provide tight sample complexity guarantees.

In this paper, we study the parameter recovery problem for non-overlapping convolutional neural networks. We aim to develop a new convergence analysis framework for neural networks that: (i) works for a class of general activation functions, (ii) does not rely on ad hoc initialization, (iii) can be potentially applied to different variants of the gradient descent algorithm.
The main contributions of this paper is as follows:
\begin{itemize}[leftmargin = *]
	\item We propose an approximate gradient descent algorithm that learns the parameters of both layers in a non-overlapping convolutional neural network. With weak requirements on initialization that can be easily satisfied, the proposed algorithm converges to the ground-truth parameters linearly up to statistical precision.
	\item Our convergence result holds for all non-trivial, monotonic and Lipschitz continuous activation functions. Compared with the results in \citet{brutzkus2017globally, du2017gradient, goel2018learning, du2018improved}, our analysis does not rely on any analytic calculation related to the activation function. We also do not require the activation function to be smooth, which is assumed in the work of \citet{zhong2017recovery} and \citet{fu2018local}.
	\item We consider the empirical version of the problem where the estimation of parameters is based on $n$ independent samples. We avoid the usual analysis with sample splitting by proving uniform concentration results. Our method outperforms the state-of-the-art results in terms of sample complexity. In fact, our result for general non-trivial, monotonic and Lipschitz continuous activation functions matches the lower bound given for linear activation functions in \citet{du2018many}, which implies the statistical optimality of our algorithm.
\end{itemize}
\iffalse
We establish the theoretical foundation for convergence analysis of one-hidden-layer neural networks with general activation functions. Under the mild assumption that the activation function is non-trivial, monotonic and Lipschitz continuous, we establish various properties of the neural network which prove useful in convergence analysis.
\fi

\begin{table}[t]

	\centering
	\caption {Comparison with related work \citep{du2017gradient,du2018many,goel2018learning,du2018improved}. Note that \citet{du2018many} did not study any specific learning algorithms. All sample complexity results are calculated for standard Gaussian inputs and non-overlapping filters. Here Approximate GD stands for approximate gradient descent, which is given in Algorithm~\ref{alg:approximategradient}
	\label{table:comparison}}
 	\vskip 0.05in
\begin{tabular}{ccccccc}
    \toprule
    \hspace{-1mm}&\hspace{-4mm}Conv. rate& \hspace{-3.5mm}Sample comp.  &\hspace{-3.2mm}Act. fun. &\hspace{-2.5mm}Data input&\hspace{-3.1mm}Overlap&\hspace{-3mm}Sec. layer
     \\
	\midrule
    \hspace{-1mm}\citet{du2017gradient}&\hspace{-4mm}linear&\hspace{-4.8mm}-&\hspace{-3.2mm}ReLU&\hspace{-2.5mm}Gaussian&\hspace{-3.1mm}no&\hspace{-3mm}yes\\
    \midrule
    \hspace{-1mm}\citet{du2018many} &\hspace{-4mm}-&\hspace{-4.8mm}$\tilde O ( (k+r)\cdot \epsilon^{-2} )$&\hspace{-3.2mm}Linear&\hspace{-2.5mm}sub-Gaussian&\hspace{-3.1mm}yes&\hspace{-3mm}-\\
    \midrule
    \hspace{-1mm}Convotron &\hspace{-4mm}\multirow{2}{*}{(sub)linear\footnotemark} &\hspace{-4.8mm}\multirow{2}{*}{$\tilde O(k^2r\cdot \epsilon^{-2})$}&\hspace{-3.2mm}\multirow{2}{*}{(leaky) ReLU}& \hspace{-2.5mm}\multirow{2}{*}{symmetric}&\hspace{-3.1mm}\multirow{2}{*}{yes}&\hspace{-3mm}\multirow{2}{*}{no}\\
    \hspace{-1mm}\citep{goel2018learning}& & & & & &\\
    \midrule
    \hspace{-1mm}Double Convotron &\hspace{-4mm}\multirow{2}{*}{sublinear}&\hspace{-4.8mm}\multirow{2}{*}{$\tilde O(\mathrm{poly}(k,r,\epsilon^{-1}))$}&\hspace{-3.2mm}\multirow{2}{*}{(leaky) ReLU}& \hspace{-2.5mm}\multirow{2}{*}{symmetric}&\hspace{-3.1mm}\multirow{2}{*}{yes}&\hspace{-3mm}\multirow{2}{*}{yes}\\
    \hspace{-1mm}\citep{du2018improved}& & & & & &\\
    \midrule
    \hspace{-1mm}\textbf{Approximate GD}& \hspace{-4mm}\multirow{2}{*}{linear}&\hspace{-4.8mm}\multirow{2}{*}{$\tilde O ( (k+r)\cdot \epsilon^{-2} )$}&\hspace{-3.2mm}\multirow{2}{*}{general}& \hspace{-2.5mm}\multirow{2}{*}{Gaussian}&\hspace{-3.1mm}\multirow{2}{*}{no}&\hspace{-3mm}\multirow{2}{*}{yes}\\
    \hspace{-1mm}\textbf{(This paper)}& & & & & &\\
	\bottomrule
\end{tabular
\end{table}
\footnotetext{\citet{goel2018learning} provided a general sublinear convergence result as well as a linear convergence rate for the noiseless case. We only list their sample complexity result of the noisy case in the table for proper comparison. }

Detailed comparison between our results and the state-of-the-art on learning one-hidden-layer CNNs is given in Table~\ref{table:comparison}. We compare the convergence rates and sample complexities obtained by recent work with our result. We also summarize the applicable activation functions and data input distributions, and whether overlapping/non-overlapping filters and second layer training are considered in each of the work.

\noindent\textbf{Notation:}  Let $\Ab = [A_{ij}] \in \RR^{d\times d}$ be a matrix and $\xb = (x_1,...,x_d)^{\top} \in \RR^{d}$ be a vector. We use $\|\xb\|_{q} = (\sum_{i=1}^{d}|x_{i}|^{q})^{1/q}$ to denote $\ell_{q}$ vector norm for $0 < q < +\infty$. The spectral and Frobenius norms of $\Ab$ are denoted by $\|\Ab\|_{2}$ and $\|\Ab\|_{F}$. For a symmetric matrix $\Ab$, we denote by $\lambda_{\max}(\Ab)$, $\lambda_{\min}(\Ab)$ and $\lambda_{i}(\Ab)$ the maximum, minimum and $i$-th largest eigenvalues of $\Ab$. We denote by $\Ab \succeq 0$ that $\Ab$ is positive semidefinite (PSD).
Given two sequences $\{a_n\}$ and $\{b_n\}$, we write $a_n = O(b_n)$ if there exists a constant $0 < C < +\infty$ such that $a_n \leq C\, b_n$, and $a_n = \Omega(b_n)$ if $a_n \geq C\, b_n$ for some constant $C$. We use notations $\tilde{O}(\cdot), \tilde{\Omega}(\cdot)$ to hide the logarithmic factors.
Finally, we denote $a \land b = \min\{a,b\}$, $a \lor b = \max\{a,b\}$.
\section{The One-hidden-layer Convolutional Neural Network}\label{section:cnndef}
In this section we formalize the one-hidden-layer convolutional neural network model.
In a convolutional network with neuron number $k$ and filter size $r$, a filter $\wb\in \RR^r$ interacts with the input $\xb$ at $k$ different locations $\cI_1,\ldots,\cI_k$, where $\cI_1,\ldots,\cI_k\subseteq \{1,2,\ldots,d\}$ are index sets of cardinality $r$. Let $\cI_j = \{p_{j1},\ldots, p_{jr}\},j=1,\ldots, k$, then the corresponding selection matrices $\Pb_1,\ldots,\Pb_k$ are defined as
$\Pb_j = (\eb_{p_{j1}},\ldots, \eb_{p_{jr}})^\top$, $j=1,\ldots, k$.

We consider a convolutional neural network of the form
\begin{align*}
    y = \sum_{j=1}^k  v_j\sigma(\wb^{\top} \Pb_{j} \xb_{i}),
\end{align*}
where $\sigma(\cdot)$ is the activation function, and $\wb\in \RR^r$, $\vb\in \RR^k$ are the first and second layer parameters respectively.
Suppose that we have $n$ samples $\{(\xb_i, y_i)\}_{i=1}^n$, where $\xb_1,\ldots,\xb_n \in \RR^d$ are generated independently from standard Gaussian distribution, and the corresponding output $y_1,\ldots,y_n\in\RR$ are generated from the teacher network with true parameters $\wb^*$ and $\vb^*$ as follows.
\begin{align*}
    y_{i} = \sum_{j=1}^k  v^*_j\sigma(\wb^{*\top} \Pb_{j} \xb_{i}) + \epsilon_{i},
\end{align*}
where $k$ is the number of hidden neurons, and $\epsilon_1,\ldots,\epsilon_n$ are independent sub-Gaussian white noises with $\psi_2$ norm $\nu$. Through out this paper, we assume that $\|\wb^*\|_2=1$.

The choice of activation function $\sigma(\cdot)$ determines the landscape of the neural network. In this paper, we assume that $\sigma(\cdot)$ is a non-trivial, Lipschitz continuous increasing function.
\begin{assumption}\label{assump:1Lipschitz}
$\sigma$ is $1$-Lipschitz continuous:
$|\sigma(z_1)-\sigma(z_2)|\leq |z_1-z_2|$ for all $z_1,z_2\in\RR$.
\end{assumption}
\begin{assumption}\label{assump:nontrivialincreasing}
$\sigma$ is a non-trivial (not a constant) increasing function.
\end{assumption}
\begin{remark}
Assumptions~\ref{assump:1Lipschitz} and~\ref{assump:nontrivialincreasing} are fairly weak assumptions satisfied by most practically used activation functions including the rectified linear unit (ReLU) function $\sigma(z) = \max(z,0)$, the sigmoid function $\sigma(z) = 1/(1+e^z)$, the hyperbolic tangent function $\sigma(z) = (e^z - e^{-z})/(e^z + e^{-z})$, and the erf function $\sigma(z) = \int_0^z e^{-t^2/2}\mathrm{d} t$. Since we do not make any assumptions on the second layer true parameter $\vb^*$, our assumptions can be easily relaxed to any non-trivial, $L$-Lipschitz continuous and monotonic functions for arbitrary fixed positive constant $L$.
\end{remark}

\section{Approximate Gradient Descent}\label{section:algorithm}
In this section we present a new algorithm for the estimation of $\wb^*$ and $\vb^*$.

\subsection{Algorithm Description}
Let $\yb = (y_1,\ldots,y_n)^\top$, $\Sigma(\wb) = [\sigma(\wb^\top \Pb_j \xb_i)]_{n\times k}$ and $\xi = \EE_{z\sim N(0,1)}[\sigma(z)z]$. The algorithm is given in Algorithm~\ref{alg:approximategradient}. We call it approximate gradient descent because it is derived by simply replacing the $\sigma'(\cdot)$ terms in the gradient of the empirical square loss function by the constant $\xi^{-1}$.
It is easy to see that under Assumption~\ref{assump:1Lipschitz} and \ref{assump:nontrivialincreasing}, we have $\xi > 0$. Therefore, replacing $\sigma'(\cdot) > 0$ with $\xi^{-1}$ will not drastically change the gradient direction, and gives us an approximate gradient.

Algorithm~\ref{alg:approximategradient} is also related to, but different from the Convotron algorithm proposed by \citet{goel2018learning} and the Double Convotron algorithm proposed by \citet{du2018improved}.
The Approximate Gradient Descent algorithm can be seen a generalized version of the Convotron algorithm, which only considers optimizing over the first layer parameters of the convolutional neural network. Compared to the Double Convotron, Algorithm~\ref{alg:approximategradient} implements a simpler update rule based on iterative weight normalization for the first layer parameters, and uses a different update rule for the second layer parameters.

\begin{algorithm}[h]
\caption{Approximate Gradient Descent for Non-overlapping CNN} \label{alg:approximategradient}
\begin{algorithmic}
\REQUIRE Training data $\{(\xb_i,y_i)\}_{i=1}^n$, number of iterations $T$, step size $\alpha$, initialization $\wb^{0} \in S^{r-1} $, $\vb^0$.
\FOR{$t=0,1,2,\ldots, T-1$}
\STATE $\gb_w^t = - \frac{1}{n} \sum_{i=1}^n \big[y_i -
\sum_{j=1}^k v_j^t \sigma(\wb^{t\top} \Pb_j \xb_i)\big]\cdot \sum_{j'=1}^k \xi^{-1} v_{j'}^t \Pb_{j'} \xb_i$
\STATE $\gb^t_v = - \frac{1}{n} \bSigma^{\top}(\wb^t) [\yb - \bSigma(\wb^t) \vb^t]$
\STATE $\ub^{t+1} = \wb^{t} - \alpha \gb_w^{t}$, $\wb^{t+1} = \ub^{t+1}/\|\ub^{t+1}\|_2$, $\vb^{t+1} = \vb^t - \alpha \gb_v^t$
\ENDFOR
\ENSURE $\wb^T$, $\vb^T$
\end{algorithmic}
\end{algorithm}

\subsection{Convergence Analysis of Algorithm~\ref{alg:approximategradient}}
In this section we give the main convergence result of Algorithm~\ref{alg:approximategradient}. We first introduce some notations. The following quantities are determined purely by the activation function:
\begin{align*}
    &\kappa := \EE_{z\sim N(0,1)}[\sigma(z)],~\Delta := \mathrm{Var}_{z\sim N(0,1)}[\sigma(z)],~ L := 1+|\sigma(0)|,~\Gamma := 1 + |\sigma(0) - \kappa|, \\
    &\phi(\wb, \wb') := \mathrm{Cov}_{\zb\sim N(\mathbf{0},\Ib)}[\sigma(\wb^\top \zb), \sigma(\wb'^\top \zb)].
\end{align*}
The following lemma shows that the function $\phi(\wb,\wb')$ can in fact be written as a function of $\wb^\top \wb'$, which we denote as $\psi(\wb^\top \wb')$. The lemma also reveals that $\psi(\cdot)$ is an increasing function.
\begin{lemma}\label{lemma:psidefinition}
Under Assumption~\ref{assump:nontrivialincreasing}, there exists an increasing function $\psi(\tau)$ such that $\psi(\wb^\top \wb') = \phi(\wb , \wb')$, and $\Delta \geq \psi(\tau)>0$ for all $\tau >0$.
\end{lemma}
We further define the following quantities.
\begin{align*}
    &M = \max\bigg\{ \frac{|\kappa| (2L|\mathbf{1}^\top \vb^*| + \sqrt{k})}{\Delta + \kappa^2k}, |\kappa\mathbf{1}^\top (\vb^0 - \vb^*)|\bigg\},\\
    &D = \max\Bigg\{\| \vb^0 - \vb^* \|_2, \sqrt{\frac{4(1 + 4\alpha\Delta) L^2 \|\vb^*\|_2^2 + 4\alpha\Delta (\kappa^2 M^2 k + 1) + 2}{\Delta^2(1 - 4\alpha \Delta)}}
    \Bigg\},\\
    &\rho = \min\bigg\{\frac{1}{2+\Delta}\psi\bigg(\frac{1}{2}\wb^{*\top}\wb^0\bigg)\|\vb^{*}\|_2^2, \vb^{*\top} \vb^0 \bigg\}.
\end{align*}
Let $D_0 = D + \|\vb^*\|_2$. Note that in our problem setting the number of filters $k$ can scale with $n$. However, although $k$ is used in the definition of $M$, $D$, $\rho$ and $D_0$, it is not difficult to check that all these quantities can be upper bounded, as is stated in the following lemma.

\begin{lemma}\label{lemma:boundedconstant}
If $\alpha \leq 1/(8\Delta)$, then
$M$, $D$, $D_0$ have upper bounds, and $\rho$ has a lower bound, that only depend on the activation function $\sigma(\cdot)$, the ground-truth $(\wb^*,\vb^*)$ and the initialization $(\wb^0,\vb^0)$.
\end{lemma}

We now present our main result, which states that the iterates $\wb^t$ and $\vb^t$ in Algorithm~\ref{alg:approximategradient} converge linearly towards $\wb^*$ and $\vb^*$ respectively up to statistical accuracy.

\begin{theorem}\label{thm:mainthm_convergence} Let $\delta \in (0,1)$, $\gamma_1 = (1+\alpha \rho)^{-1/2}$, $\gamma_2 = \sqrt{1 - \alpha \Delta + 4\alpha^2\Delta^2}$, and $\gamma_3 = 1 - \alpha(\Delta + \kappa^2k)$. Suppose that the initialization $(\wb^0,\vb^0)$ satisfies
\begin{align}\label{eq:initializationcondition}
    \wb^{*\top} \wb^0>0,~ \vb^{*\top} \vb^0>0, ~\kappa^2(\mathbf{1}^\top \vb^*)\mathbf{1}^\top(\vb^0 - \vb^*)\leq \rho,
\end{align}
and the step size $\alpha$ is chosen such that
\begin{align*}
    \alpha &\leq  \frac{1}{2(\Delta + \kappa^2 k)} \land \frac{1}{8\Delta} \land  \frac{\Delta^2}{(24 L^2 + 2\Delta^2) \|\vb^*\|_2^2 + 2 M^2 k + 10} \land \frac{1}{2(\| \vb^0 - \vb^* \|_2^2 + \| \vb^* \|_2^2) }.
\end{align*}
If
\begin{align}
    c_1\sqrt{\frac{(r+k)\log(c_2 nk /\delta )}{n}} &\leq 1 \land \frac{\rho \sqrt{k}}{|\mathbf{1}^\top \vb^*|} \land \frac{  \Gamma \sqrt{k(r+k)} }{  1 + L + \xi} \land  \frac{ (\Gamma + |\kappa| \sqrt{k}) \Gamma \sqrt{r+k} }{ L^2 + |\kappa| + \Delta + L  }\nonumber \\
    &\quad\land \frac{\xi}{ D_0(D_0 \Gamma + M + \nu)} \bigg(1\land \frac{\rho}{1+\alpha \rho} \wb^{*\top}\wb^0 \bigg)\nonumber \\
    &\quad\land \frac{1}{(\Gamma + \kappa \sqrt{k}) (D_0 \Gamma + M + \nu)} \bigg(1 \land \frac{\rho}{\| \vb^* \|_2}\bigg)\label{eq:samplecomplexityassumption}
\end{align}
for some large enough absolute constants $c_1$ and $c_2$, then there exists absolute constants $C$ and $C'$ such that, with probability at least $1-\delta$ we have
\begin{align}
     &\| \wb^{t} - \wb^* \|_2  \leq \gamma_1^{t} \| \wb^0 -\wb^* \|_2  + 8\rho^{-1}\gamma_1^{-2}\eta_w, \label{eq:convergence_wt} \\
     &\| \vb^{t} -\vb^* \|_2 \leq R_1 t^{3/2} (\gamma_1 \lor \gamma_2 \lor \gamma_3)^{t} + (R_2 + R_3 |\kappa|\sqrt{k}) (\eta_w + \eta_v), \label{eq:convergence_vt}
\end{align}
for all $t=0,\ldots,T$, where
\begin{align}
    &\eta_w = C\xi^{-1} D_0(D_0 \Gamma + M + \nu)\cdot  \sqrt{\frac{(r+k)\log(120nk/\delta)}{n}}, \label{eq:def_eta_w}\\
    &\eta_v = C'(\Gamma + \kappa \sqrt{k}) (D_0 \Gamma + M + \nu)\cdot \sqrt{\frac{(r+k)\log(120nk/\delta)}{n}},\label{eq:def_eta_v}
\end{align}
and $R_1$, $R_2$, $R_3$ are constants that only depend on the choice of activation function $\sigma(\cdot)$, the ground-truth parameters $(\wb^*,\vb^*)$ and the initialization $(\wb^0,\vb^0)$.
\end{theorem}

Equation \eqref{eq:samplecomplexityassumption} is an assumption on the sample size $n$. Although this assumption looks complicated, essentially except $k$ and $r$, all quantities in this condition can be treated as constants, and \eqref{eq:samplecomplexityassumption} can be interpreted as an assumption that $n \geq \tilde\Omega((1 + \kappa \sqrt{k}) \sqrt{r+k})$, which is by no means a strong assumption. The second and third lines of \eqref{eq:samplecomplexityassumption} are to guarantee $\eta_w \leq 1\land [\rho/(1+\alpha \rho) \wb^{*\top}\wb^0]$ and $\eta_v \leq 1\land ( \rho/\| \vb^* \|_2 )$ respectively, while the first line is for technical purposes to ensure convergence.

\begin{remark}
Theorem~\ref{thm:mainthm_convergence} shows that with initialization satisfying \eqref{eq:initializationcondition}, Algorithm~\ref{alg:approximategradient} linearly converges to true parameters up to statistical error. This condition for initialization can be easily satisfied with random initialization. In Section~\ref{sec:initialization}, we will give a detailed initialization algorithm inspired by a random initialization method proposed in \citet{du2017gradient}.
\end{remark}

\begin{remark}
Compared with the most relevant convergence results in literature given by \citet{du2017gradient}, our result is based on optimizing the empirical loss function instead of the population loss function. In particular, when $\kappa=0$, Theorem~\ref{thm:mainthm_convergence} proves that Algorithm~\ref{alg:approximategradient} eventually gives estimation of parameters with statistical error of order $O\Big(\sqrt{\frac{(r+k)\log(120nk/\delta)}{n}}\Big)$. This rate matches the information-theoretic lower bound for one-hidden-layer convolutional neural networks with linear activation functions. Note that our result holds for general activation functions. Matching the lower bound of the linear case implies the optimality of our algorithm.
Compared with two recent results, namely the Convotron algorithm proposed by \citet{goel2018learning} and the Double Convotron algorithm proposed by \citet{du2018improved}, which work for ReLU activation and generic symmetric input distributions, our theoretical guarantee for Algorithm~\ref{alg:approximategradient} gives a tighter sample complexity for more general activation functions, but requires the data inputs to be Gaussian. We remark that if restricting to ReLU activation function, our analysis can be extended to generic symmetric input distributions as well, and can still provide tight sample complexity.
\end{remark}

\begin{remark}\label{remark:convergence_speedup}
A recent result by \citet{du2017gradient} discussed a speed-up in convergence when training non-overlapping CNNs with ReLU activation function. This phenomenon also exists in Algorithm~\ref{alg:approximategradient}. To show it, we first note that in Theorem~\ref{thm:mainthm_convergence}, the convergence rate of $\wb^t$ and $\vb^t$ are essentially determined by $\gamma_1= (1+\alpha \rho)^{-1/2}$. For appropriately chosen $\alpha$, $\rho$ being too small (i.e. $\wb^{*\top} \wb^0 $ or $\vb^{*\top} \vb^0 $ being too small, by Lemma~\ref{lemma:psidefinition}) is the only possible reason of slow convergence.
Now by the iterative nature of Algorithm~\ref{alg:approximategradient}, for any $T_1>0$, we can analyze the convergence behavior after $T_1$ by treating $\wb^{T_1}$ and $\vb^{T_1}$ as new initialization and applying Theorem~\ref{thm:mainthm_convergence} again. By Theorem~\ref{thm:mainthm_convergence}, even if the initialization gives small $\wb^{*\top}\wb^0$ and $\vb^{*\top}\vb^0$, after certain number of iterations, $\wb^{*\top}\wb^t$ and $\vb^{*\top}\vb^t$ become much larger and therefore the convergence afterwards gets much faster. This phenomenon is comparable with the two-phase convergence result of \citet{du2017gradient}. However, while \citet{du2017gradient} only show the convergence of second layer parameters for phase II of their algorithm, our result shows that linear convergence of Algorithm~\ref{alg:approximategradient} starts at the first iteration.
\end{remark}

\subsection{Initialization}\label{sec:initialization}
To complete the theoretical analysis of Algorithm~\ref{alg:approximategradient}, it remains to show that initialization condition \eqref{eq:initializationcondition} can be achieved with practical algorithms.
The following theorem is inspired by a similar method proposed by \citet{du2017gradient}. It gives a simple random initialization method that satisfy \eqref{eq:initializationcondition}.

\begin{theorem}\label{thm:initialization}
Let $\wb\in \RR^r$ and $\vb\in \RR^k$ be vectors generated by $\PP_w$ and $\PP_v$ with support $S^{r-1}$ and $B(\mathbf{0},k^{-1/2}|\mathbf{1}^\top \vb^*|)$ respectively. Then there exists $(\wb^0,\vb^0) \in \{ (\wb,\vb),(-\wb,\vb),(\wb,-\vb),(-\wb,-\vb)\}$
that satisfies \eqref{eq:initializationcondition}.
\end{theorem}

\begin{remark}
The proof of Theorem~\ref{thm:initialization} is fairly straightforward--the vector $\vb$ generated by proposed initialization method in fact satisfies that $\kappa^2(\mathbf{1}^\top \vb^*)\mathbf{1}^\top(\vb - \vb^*)\leq 0$.
Moreover, it is worth noting that for activation functions with $\kappa = \EE_{z\sim N(0,1)}[\sigma(z)] = 0$, the initialization condition $\kappa^2(\mathbf{1}^\top \vb^*)\mathbf{1}^\top(\vb^0 - \vb^*)\leq \rho$ is automatically satisfied. Therefore for any vector $\wb\in S^{r-1}$ and $\vb\in \RR^k$, one of $(\wb,\vb),(-\wb,\vb),(\wb,-\vb),(-\wb,-\vb)$ satisfies the initialization condition, making initialization for Algorithm~\ref{alg:approximategradient} extremely easy.
\end{remark}

\section{Proof of the Main Theory}\label{section:proofmain}
In this section we give the proof of Theorem~\ref{thm:mainthm_convergence}. The proof consists of three steps: (i) prove uniform concentration inequalities for approximate gradients, (ii) give recursive upper bounds for $\|\wb^t - \wb^*\|_2$ and $\|\vb^t - \vb^*\|_2$, (iii) derive the final convergence result \eqref{eq:convergence_wt} and \eqref{eq:convergence_vt}.

We first analyze how well the approximate gradients $\gb_w^t$ and $\gb_v^t$ concentrate around their expectations. Instead of using the classic analysis on $\gb_w^t$ and $\gb_v^t$ conditioning on all previous iterations $\{\wb^{s},\vb^{s}\}_{s = 1}^t$, we consider uniform concentration  over a parameter set $\cW_0\times \cV_0$ defined as follows.
\begin{align*}
\cW_0:= S^{r-1} = \{\wb:\|\wb\|_2=1\}, ~ \cV_0:= \{\vb:  \|\vb - \vb^*\|_2 \leq D,~ |\kappa \mathbf{1}^\top (\vb - \vb^*)| \leq M\}.
\end{align*}
Define
\begin{align*}
\gb_w(\wb,\vb) &= - \frac{1}{n} \sum_{i=1}^n \Bigg[y_i -
\sum_{j=1}^k v_j \sigma(\wb^{\top} \Pb_j \xb_i)\Bigg]\cdot \sum_{j'=1}^k \xi^{-1} v_{j'} \Pb_{j'} \xb_i,\\
\gb_v(\wb,\vb) &= - \frac{1}{n} \bSigma^\top(\wb) [\yb - \bSigma(\wb) \vb],\\
\overline{\gb}_w(\wb,\vb) &= \|\vb\|_2^2 \wb - (\vb^{*\top}\vb) \wb^*,\\
\overline{\gb}_v(\wb,\vb) &= (\Delta \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top )\vb - [\phi(\wb,\wb^*) \Ib  + \kappa^2 \mathbf{1} \mathbf{1}^\top ]\vb^*.
\end{align*}
The following claim follows by direct calculation.
\begin{claim}\label{claim:expectationcalculation}
For any fixed $\wb,\vb$, it holds that $\EE[\gb_w(\wb,\vb)] = \overline{\gb}_w(\wb,\vb)$ and $\EE[\gb_v(\wb,\vb)] = \overline{\gb}_v(\wb,\vb)$, where the expectation is taken over the randomness of data.
\end{claim}
Our goal is to bound $\sup_{(\wb,\vb)\in \cW_0\times \cV_0} \|\gb_w(\wb,\vb) - \overline{\gb}_w(\wb,\vb) \|_2$ and $\sup_{(\wb,\vb)\in \cW_0\times \cV_0} \|\gb_v(\wb,\vb) - \overline{\gb}_v(\wb,\vb) \|_2$. A key step for proving such uniform bounds is to show thee uniform Lipschitz continuity of $\gb_w(\wb,\vb)$ and $\gb_v(\wb,\vb)$, which is given in the following lemma.

\begin{lemma}\label{lemma:smoothness_all}
For any $\delta>0$, if $n \geq (r+k)\log(324/\delta)$, then with probability at least $1-\delta$, the following inequalities hold uniformly over all $\wb,\wb'\in \cW_0$ and $\vb, \vb' \in \cV_0$:
\begin{align}
    &\| \gb_w(\wb,\vb) - \gb_w(\wb',\vb) \|_2 \leq C\xi^{-1}D_0^2\sqrt{k}\cdot \| \wb - \wb' \|_2, \label{eq:smoothness_ww} \\
    &\|\gb_w(\wb,\vb) - \gb_w(\wb,\vb')\|_2 \leq C\xi^{-1}(\nu + D_0L\sqrt{k})\cdot \| \vb - \vb' \|_2,\label{eq:smoothness_wv}\\
    &\|\gb_v(\wb,\vb) - \gb_v(\wb',\vb)\|_2 \leq C ( \nu +  D_0 L \sqrt{k})\sqrt{k}\cdot \| \wb - \wb' \|_2,\label{eq:smoothness_vw}\\
    &\|\gb_v(\wb,\vb) - \gb_v(\wb,\vb')\|_2 \leq C L^2 k \cdot \| \vb - \vb' \|_2 ,\label{eq:smoothness_vv}
\end{align}
where $C$ is an absolute constant.
\end{lemma}
If $\gb_w$ and $\gb_v$ are gradients of some objective function $f$, then Lemma~\ref{lemma:smoothness_all} essentially proves the uniform smoothness of $f$. However, in our algorithm, $\gb_w$ is not the exact gradient, and therefore the results are stated in the form of Lipschitz continuity of $\gb_w$.
Lemma~\ref{lemma:smoothness_all} enables us to use a covering number argument together with point-wise concentration inequalities to prove uniform concentration, which is given as Lemma~\ref{lemma:gradientuniformconcentration}.
\begin{lemma}\label{lemma:gradientuniformconcentration}
Assume that $n \geq (r+k)\log(972/\delta)$, and
\begin{align*}
    & \xi^{-1} D_0(D_0 \Gamma + M + \nu)\sqrt{n(r+k)\log(90nk/\delta)} \geq D_0(D_0 + 1) \lor \xi^{-1}(\nu + D_0^2 + D_0L),\\
    & (\Gamma + \kappa \sqrt{k})[D_0 \Gamma + M + \nu] \sqrt{n(r+k)\log(90nk/\delta)} \geq (\Delta + \kappa + D_0L) \lor (\nu + D_0 L + L^2).
\end{align*}
Then with probability at least $1-\delta$ we have
\begin{align}
    &\sup_{(\wb,\vb)\in \cW_0\times \cV_0} \|\gb_w(\wb,\vb) - \overline{\gb}_w(\wb,\vb) \|_2 \leq \eta_w, \label{eq:gradientuniformconcentration_w}\\
    &\sup_{(\wb,\vb)\in \cW_0\times \cV_0} \|\gb_v(\wb,\vb) - \overline{\gb}_v(\wb,\vb) \|_2 \leq \eta_v, \label{eq:gradientuniformconcentration_v}
\end{align}
where $\eta_w$ and $\eta_v$ are defined in \eqref{eq:def_eta_w} and \eqref{eq:def_eta_v} respectively with large enough constants $C$ and $C'$.
\end{lemma}

We now proceed to study the recursive properties of $\{ \wb^t \}$ and $\{ \vb^t \}$.
Define
\begin{align*}
&\cW := \{\wb: \|\wb\|_2= 1,~ \wb^{*\top} \wb \geq \wb^{*\top}\wb^0/2 \},\\
&\cV := \{\vb:  \|\vb - \vb^*\|_2 \leq D,~ |\kappa \mathbf{1}^\top (\vb - \vb^*)| \leq M, \vb^{*\top} \vb \geq \rho ,~\kappa^2 (\mathbf{1}^\top \vb^*)\mathbf{1}^\top(\vb - \vb^*) \leq \rho \}.
\end{align*}
Then clearly $\cW\times \cV \subseteq \cW_0\times \cV_0$, and therefore the results of Lemma~\ref{lemma:gradientuniformconcentration} hold for $(\wb,\vb)\in \cW\times \cV $.
\begin{lemma}\label{lemma:recursiveproperty}
Suppose that \eqref{eq:gradientuniformconcentration_w} and \eqref{eq:gradientuniformconcentration_v} hold. Under the assumptions of Theorem~\ref{thm:mainthm_convergence},
in Algorithm~\ref{alg:approximategradient}, if $(\wb^t,\vb^t)\in \cW \times \cV $, then
\begin{align}
    &\| \wb^{t+1} - \wb^* \|_2 - 8\rho^{-1}(1+\alpha\rho)\eta_w \leq \frac{1}{\sqrt{1+\alpha \rho }} [\| \wb^t -\wb^* \|_2 - 8\rho^{-1}(1+\alpha\rho)\eta_w], \label{eq:recursiveproperty1} \\
    &|\mathbf{1}^\top (\vb^{t+1} - \vb^*)| \leq [1 - \alpha (\Delta + \kappa^2k)]|\mathbf{1}^\top (\vb^{t} - \vb^*)| + \alpha L\| \wb^t - \wb^* \|_2 |\mathbf{1}^\top\vb^*|
    + \alpha \sqrt{k} \eta_v, \label{eq:recursiveproperty2}\\
    &\| \vb^{t+1} -\vb^* \|_2^2 \leq ( 1 - \alpha \Delta + 4\alpha^2\Delta^2  ) \| \vb^{t} -\vb^* \|_2^2 + \bigg(\frac{\alpha L^2}{\Delta} + 4\alpha^2 L^2 \bigg)  \|\vb^*\|_2^2 \|\wb^t - \wb^{*} \|_2^2 \nonumber \\
    &\quad\quad\quad\quad\quad\quad\quad + 4\alpha^2 \kappa^4 k[\mathbf{1}^\top (\vb^{t} - \vb^*)]^2 + \bigg( \frac{2\alpha}{\Delta} + 4 \alpha^2 \bigg) \eta_v^2 ,\label{eq:recursiveproperty3}\\
    &(\wb^{t+1},\vb^{t+1}) \in \cW\times \cV.\label{eq:recursiveproperty4}
\end{align}
\end{lemma}

It is not difficult to see that the results of Lemma~\ref{lemma:recursiveproperty} imply convergence of $\wb^t$ and $\vb^t$ up to statistical error. To obtain the final convergence result of Theorem~\ref{thm:mainthm_convergence}, it suffices to rewrite the recursive bounds into explicit bounds, which is mainly tedious calculation. We therefore summarize the result as the following lemma, and defer the detailed calculation to appendix.

\begin{lemma}\label{lemma:recursive_to_explicit}
Suppose that \eqref{eq:recursiveproperty1}, \eqref{eq:recursiveproperty2} and \eqref{eq:recursiveproperty3} hold for all $t=0,\ldots,T$. Then
\begin{align*}
     &\| \wb^{t} - \wb^* \|_2 \leq \gamma_1^{t} \| \wb^0 -\wb^* \|_2  + 8\rho^{-1}\gamma_1^{-2}\eta_w, \\
     &\| \vb^{t} -\vb^* \|_2 \leq R_1 t^3 (\gamma_1 \lor \gamma_2 \lor \gamma_3)^{t} + (R_2 + R_3 |\kappa|\sqrt{k}) (\eta_w + \eta_v)
\end{align*}
for all $t=0,\ldots,T$, where $\gamma_1 = (1+\alpha \rho)^{-1/2}$, $\gamma_2 = \sqrt{1 - \alpha \Delta + 4\alpha^2\Delta^2}$, and $\gamma_3 = 1 - \alpha(\Delta + \kappa^2k)$, and $R_1$, $R_2$, $R_3$ are constants that only depend on the choice of activation function $\sigma(\cdot)$, the ground-truth parameters $(\wb^*,\vb^*)$ and the initialization $(\wb^0,\vb^0)$.
\end{lemma}

We are now ready to present the final proof of Theorem~\ref{thm:mainthm_convergence}, which is a  straightforward combination of the results of Lemma~\ref{lemma:recursiveproperty} and Lemma~\ref{lemma:recursive_to_explicit}.

\begin{proof}[Proof of Theorem~\ref{thm:mainthm_convergence}]
By Lemma~\ref{lemma:recursiveproperty}, as long as $(\wb^0,\vb^0)\in \cW \times \cV $, \eqref{eq:recursiveproperty1}, \eqref{eq:recursiveproperty2} and \eqref{eq:recursiveproperty3} hold for all $t=0,\ldots,T$. Therefore by Lemma~\ref{lemma:recursive_to_explicit}, we have
\begin{align*}
     &\| \wb^{t} - \wb^* \|_2 \leq \gamma_1^{t} \| \wb^0 -\wb^* \|_2  + 8\rho^{-1}\gamma_1^{-2}\eta_w, \\
     &\| \vb^{t} -\vb^* \|_2 \leq R_1 t^3 (\gamma_1 \lor \gamma_2 \lor \gamma_3)^{t} + (R_2 + R_3 |\kappa|\sqrt{k}) (\eta_w + \eta_v)
\end{align*}
for all $t=0,\ldots,T$. This completes the proof of Theorem~\ref{thm:mainthm_convergence}.
\end{proof}

\section{Experiments}\label{sec:experiments}
We perform numerical experiments to backup our theoretical analysis. We test Algorithm~\ref{alg:approximategradient} together with the initialization method given in Theorem~\ref{thm:initialization} for ReLU, sigmoid and hyperbolic tangent networks, and compare its performance with the Double Convotron algorithm proposed by \citet{du2018improved}. To give a reasonable comparison, we use a batch version of Double Convotron without the additional noises on unit sphere, which gives the best performance for Double Convotron, and makes it directly comparable with our algorithm.
The detailed parameter choices are given as follows:
\begin{itemize}[leftmargin = *]
    \item For all experiments, we set the number of iterations $T = 100$, sample size $n = 1000$.
    \item We tune the step size $\alpha$ to maximize performance. Specifically, we set $\alpha = 0.04$ for ReLU, $\alpha = 0.25$ for sigmoid, and $\alpha = 0.1$ for hyperbolic tangent networks. Note that for sigmoid and hyperbolic tangent networks, an inappropriate step size can easily lead to blown up errors for Double Convotron.
    \item We uniformly generate $\wb^*$ from unit sphere, and generate $\vb^*$ as a standard Gaussian vector.
    \item We consider two settings: (i) $k = 15$, $r = 5$, $\tilde\nu=0.08$, (ii) $k = 30$, $r=9$, $\tilde\nu=0.04$, where $\tilde\nu$ is the standard deviation of white Gaussian noises.
\end{itemize}

\begin{figure*}[h]
	\begin{center}
		\begin{tabular}{ccc}
			\includegraphics[width=0.30\linewidth,angle=0]{errorplot_ReLU_k15r5_log.pdf}
			&
			\includegraphics[width=0.30\linewidth,angle=0]{errorplot_sigmoid_k15r5_log.pdf}
			&
			\includegraphics[width=0.30\linewidth,angle=0]{errorplot_tanh_k15r5_log.pdf}
			\\
			(a) ReLU & (b) Sigmod & (c) Hyperbolic tangent
			\\
			\includegraphics[width=0.30\linewidth,angle=0]{errorplot_ReLU_k30r9_log.pdf}
			&
			\includegraphics[width=0.30\linewidth,angle=0]{errorplot_sigmoid_k30r9_log.pdf}
			&
			\includegraphics[width=0.30\linewidth,angle=0]{errorplot_tanh_k30r9_log.pdf}
			\\
		    (d) ReLU & (e) Sigmod & (f) Hyperbolic tangent
		    \end{tabular}
	\end{center}
	\vskip-10pt
	\caption{Numerical simulation for Algorithm~\ref{alg:approximategradient} and the Double Convotron algorithm proposed by \citet{du2018improved} with different activation functions, number of hidden nodes and filter sizes. The results for the case $k = 15$, $r = 5$ and $k = 30$, $r=9$ are shown in (a)-(c) and (d)-(f) respectively. (a), (d) show the results for ReLU networks; (b), (e) give the results for sigmoid networks; and finally the results for hyperbolic tangent activation function are in (c) and (f).
    All plots are semi-log plots.
    }
	\label{fig:convergence}

\end{figure*}

The random initialization is performed as follows: we generate $\wb$ uniformly over the unit sphere. We then generate a standard Gaussian vector $\vb$. If $\| \vb \|_2 \geq  k^{-1/2}|\mathbf{1}^\top \vb^*| / 2$, then $\vb$ is projected onto the ball $\cB(0, k^{-1/2}|\mathbf{1}^\top \vb^*| / 2)$. We then run the approximate gradient descent algorithm and Double Convotron algorithm starting with each of $(\wb,\vb),(-\wb,\vb),(\wb,-\vb), (-\wb,-\vb)$, and present the results corresponding to the starting point that gives the smallest $\| \wb^T - \wb^* \|_2$.

Figure~\ref{fig:convergence} gives the experimental results in semi-log plots. We summarize the results as follows.
\begin{enumerate}[leftmargin = *]
    \item For all the six cases, the approximate gradient descent algorithm eventually reaches a stable state of linear convergence, until reaching very small error.
    \item For ReLU networks, both algorithms converges. The convergence of approximated gradient descent algorithm is slower compared with Double Convotron, but it eventually reaches smaller statistical error, indicating a better sample complexity.
    \item For sigmoid and hyperbolic tangent networks, not surprisingly, Double Convotron does not converge. In contrast, approximated gradient descent still converges in a linear rate.
\end{enumerate}
The experimental results discussed above clearly demonstrates the validity of our theoretical analysis. In Appendix~\ref{appendix:additional_experiments}, we also present some additional experiments on non-Gaussian inputs, and demonstrate that although this setting is not the focus of our theoretical results, approximate gradient descent still has promising performance on symmetric data distributions.

\input{conclusions}

\section*{Acknowledgement}

We thank the anonymous reviewers and area chair for their helpful comments. This research was sponsored in part by the National Science Foundation CAREER Award IIS-1906169, IIS-1903202, and Salesforce Deep Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

\subsection{Direction estimation}
In this section we consider a simple algorithm to estimate the direction of parameter vectors $\wb_*$ and $\vb_*$.

\begin{algorithm}[h]
\caption{Direction Estimation for Non-overlapping CNN} \label{alg:NOCNN}
\begin{algorithmic}
\REQUIRE Training data $\{(\xb_i,y_i)\}_{i=1}^n$.
\FOR{$j=1,2,3,\ldots, r$}
\STATE $\hat{\ub}_j = \frac{1}{n} \sum _{i=1}^n y_i \Pb_j \xb_i$
\ENDFOR
\STATE $\hat{\wb} = \frac{1}{r}\sum_{j=1}^r \hat{\ub}_j $
\ENSURE $\hat{\wb}$.
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[h]
\caption{Direction Estimation for Non-overlapping CNN, 2 layers} \label{alg:NOCNN2layer}
\begin{algorithmic}
\REQUIRE Training data $\{(\xb_i,y_i)\}_{i=1}^n$.
\STATE $\hat{\ub}_1 = \frac{1}{n} \sum _{i=1}^n y_i \Pb_1 \xb_i$
\FOR{$j=1,2,3,\ldots, r$}
\STATE $\hat{\ub}_j = \frac{1}{n} \sum _{i=1}^n y_i \Pb_j \xb_i$
\ENDFOR
\STATE Set $l = \argmax_j \|\hat{\ub}_j\|_2$
\FOR{$j=1,2,3,\ldots, r$}
\STATE $a_j = \mathrm{sign}(\hat{\ub}_l^\top \hat{\ub}_j) $
\ENDFOR
\STATE $\tilde{\wb} = \hat{\ub}_l $, $\tilde{\vb} = (a_1\|\hat{\ub}_1\|_2,\ldots, a_r\|\hat{\ub}_r\|_2)^\top$
\ENSURE $\tilde{\wb}$, $\tilde{\vb}$
\end{algorithmic}
\end{algorithm}
\textcolor{red}{use $\tilde v_j$ instead of $\tilde \vb_j$ because it's a scalar}

\begin{algorithm}[h]
\caption{Direction Estimation for Overlapping CNN} \label{alg:OCNN}
\begin{algorithmic}
\REQUIRE Training data $\{(\xb_i,y_i)\}_{i=1}^n$.
\STATE $\tilde{\wb} =  \frac{1}{n} \sum _{i=1}^n y_i \Pb_1 \xb_i$
\STATE $\hat{w}_1 = \tilde{w}_1$
\FOR{$l=2,3,\ldots, k$}
\STATE $\hat{w}_l = \tilde{w}_{l} -\tilde{w}_{l-1}$
\ENDFOR
\ENSURE $\hat{\wb} = (\hat{w}_1,\ldots, \hat{w}_k)^\top$.
\end{algorithmic}
\end{algorithm}

\iffalse

\begin{algorithm}[h]
\caption{Direction Estimation for Non-overlapping CNN} \label{alg:NOCNN}
\begin{algorithmic}
\REQUIRE Training data $\{(\xb_i,y_i)\}_{i=1}^n$.
\FOR{$j=1,2,3,\ldots, r$}
\STATE $\hat{\ub}_j = \frac{1}{n} \sum _{i=1}^n y_i \Pb_j \xb_i$
\ENDFOR
\STATE $\hat{\wb} = \frac{1}{r}\sum_{j=1}^r \hat{\ub}_j $, $\hat{\vb} = (\|\hat{\ub}_1\|, \|\hat{\ub}_2\|, \ldots, \|\hat{\ub}_r\|)$
\ENSURE $\hat{\wb}$, $\hat{\vb}$.
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[h]
\caption{Direction Estimation for overlapping CNN} \label{alg:NOCNN}
\begin{algorithmic}
\REQUIRE Training data $\{(\xb_i,y_i)\}_{i=1}^n$.
\FOR{$j=1,2,3,\ldots, r$}
\STATE $\hat{\ub}_j = \frac{1}{n} \sum _{i=1}^n y_i \Pb_j \xb_i$
\ENDFOR
\STATE $\hat{\wb} = \frac{1}{r}\sum_{j=1}^r \hat{\ub}_j $, $\hat{\vb} = (\|\hat{\ub}_1\|, \|\hat{\ub}_2\|, \ldots, \|\hat{\ub}_r\|)$
\ENSURE $\hat{\wb}$, $\hat{\vb}$.
\end{algorithmic}
\end{algorithm}

\fi

\iffalse
\begin{algorithm}[h]
\caption{Direction Estimation for Non-overlapping CNN} \label{alg:NOCNN}
\begin{algorithmic}
\REQUIRE Training data $\{(\xb_i,y_i)\}_{i=1}^n$.
\STATE Randomly split the training data into $T$ subsets, each with size $n/T$.
\FOR{$t=1,2,3,\ldots, T$}
\STATE $\wb_{t} = \wb_{t-1} - \eta\nabla\hcL_{S_t}(\wb_{t-1})$
\ENDFOR
\ENSURE $\wb_T$.
	\end{algorithmic}
\end{algorithm}

It is worth noting that the key difference between the resampling version and vanilla gradient descent is that we split the whole sample $\{(\xb_i,y_i)\}_{i=1}^n$ into $T$ subsets, where $T$ is the total number of iterations in gradient descent,  and we use one fresh subset for each iteration. This resampling procedure ensures the independence between $\wb_{t-1}$ and the subsample  $\{(\xb_i,y_i), i\in S_t\}$ used for updating $\wb_{t-1}$, which is essential for later analysis. More specifically, we first randomly split the training sample $\{(\xb_i,y_i)\}_{i=1}^n$ into $T$ different subsets: $\{(\xb_i,y_i), i\in S_1\},\{(\xb_i,y_i),i\in S_2\}, \ldots \{(\xb_i,y_i),i\in S_T\}$, where the cardinality of $S_t$ is $|S_t|=n/T$, and we only use the subset $\{(\xb_i,y_i), i\in S_t\}$ for the
update in the $t$-th iteration. Furthermore, we write $\hcL_{S_t}(\wb)$ as the empirical loss function with respect to the subsample used in the $t$-th iteration, and give the formal definition of $\hcL_{S_t}(\wb)$ as follows
\begin{align*}
\hcL_{S_t}(\wb) = \frac{1}{2|S_t|} \sum_{i\in S_t} \big(\sigma(\wb^\top\xb_i) - y_i\big)^2.
\end{align*}
\fi

\section{Main Theory}

\begin{definition}
We define the function $\gamma(h) :=  \EE_{z\sim N(0,1)}[\sigma(hz)z]$ for any $h\in\RR$.
\end{definition}

\textcolor{red}{add assumptions}
\begin{assumption}\label{assump:Lipschitz}
The activation function $\sigma$ is $L$-Lipschitz for some constant $L>0$ such that
\begin{align*}
    |\sigma(z_1)-\sigma(z_2)|\leq L|z_1-z_2|, \text{ for all }z_1,z_2\in\RR.
\end{align*}
\end{assumption}

The following lemma is given by \cite{zhong2017recovery}.

\begin{lemma}[\cite{zhong2017recovery}]\label{lemma:momentcalculation}
For any $(\xb,y)$ generated by the model in \eqref{eq:cnndef}, we have
\begin{align*}
    \EE_{(\xb,y)\sim \cD}[y\cdot \xb] = \frac{\gamma(\|\wb^*\|_2)}{\|\wb^*\|_2}\sum_{i=1}^r \Pb_i^\top \wb^*,
\end{align*}
\end{lemma}

The following lemma characterizes an important property of Algorithm \ref{alg:NOCNN}, which estimates the direction of $\wb^*$.
\begin{lemma}
For the estimator $\hat \wb$ output by Algorithm \ref{alg:NOCNN}, we have
\begin{align*}
    \EE[\hat\wb] = \frac{\gamma(\|\wb^*\|_2)}{\|\wb^*\|_2}\wb^*.
\end{align*}
where $\gamma(h) :=  \EE_{z\sim N(0,1)}[\sigma(hz)z]$.
\end{lemma}

\subsection{Non-overlapped CNN}

\begin{theorem}\label{lemma:directionconcentrationNO}
If the activation function $\sigma$ is $L$- Lipschitz with $L>0$, with probability at least $1-\delta$, the output of Algorithm~\ref{alg:NOCNN} satisfies
\begin{align*}
    \bigg\| \hat{\wb} - \frac{\gamma(\|\wb^*\|_2)}{\|\wb^*\|_2} \wb^* \bigg\|_2 \leq  C\Bigg\{ M   \sqrt{\frac{2rk\log(2n^2r)\log(60r/\delta)}{n}}
    + [r\sigma(0)
    + \nu]\sqrt{\frac{k\log(30/\delta)}{nr}} \Bigg\},
\end{align*}
where $M = \max\{ L\|\wb^*\|_2,\|\wb^*\|_2^2\} $ and $C$ is an absolute constant. Moreover, we have
\begin{align*}
    \bigg\langle \frac{\hat{\wb}}{\|\hat{\wb}\|_2}, \frac{\wb^*}{\|\wb^*\|_2} \bigg\rangle \geq 1- \frac{C'}{\gamma^2(\|\wb^*\|_2)}\Bigg\{ M   \sqrt{\frac{2rk\log(2n^2r)\log(60r/\delta)}{n}}
    + [r\sigma(0)
    + \nu]\sqrt{\frac{k\log(30/\delta)}{nr}} \Bigg\}^2,
\end{align*}
where $C'$ is an absolute constant.
\end{theorem}

\textcolor{red}{add a remark on the assumption}
\begin{remark}

\end{remark}
\begin{proof}[Proof of Theorem~\ref{lemma:directionconcentrationNO}]
Let $\cN_{1/2}$ be a $1/2$-net covering the unit Euclidean sphere $S^{k-1}$, then by Lemma~5.2 in \cite{vershynin2010introduction}, we have
$
|\cN_{1/2}| \leq 5^k.
$
For any vector $\zb\in \cN_{1/2}$, we have
\begin{align*}
    \zb^\top \hat{\wb} = \frac{1}{nr}  \sum_{j=1}^r\sum_{i=1}^n y_i \cdot \zb^\top\Pb_j\xb_i.
\end{align*}
Plugging \eqref{eq:cnndef} into the equation above gives
\begin{align*}
    \zb^\top \hat{\wb} =  \frac{1}{n} \sum_{j=1}^r  \sum_{i=1}^n  \Bigg[\sum_{j'=1}^r \sigma(\wb^{*\top} \Pb_{j'} \xb_{i}) + \epsilon_{i}\Bigg]\cdot\zb^\top\Pb_j\xb_i =  I_1 + I_2 + I_3 ,
\end{align*}
where
\begin{align*}
   &I_1  = \frac{1}{nr} \sum_{j=1}^r \sum_{j'=1}^r \sum_{i=1}^n [\sigma(\wb^{*\top}  \Pb_{j'} \xb_{i})-\sigma(0)]\cdot\zb^\top\Pb_j\xb_i,\\
   &I_2 = \frac{1}{nr} \sum_{j=1}^r \sum_{i=1}^n r\sigma(0)\cdot\zb^\top\Pb_j\xb_i,\\
   &I_3 = \frac{1}{nr} \sum_{j=1}^r\sum_{i=1}^n \epsilon_{i}\cdot\zb^\top\Pb_j\xb_i.
\end{align*}

It is easy to see that $\EE(I_1) = \EE(\zb^\top \hat{\wb}) $ and $\EE(I_2) = \EE(I_3) =0$. We now analyze the concentration of the three terms.

\noindent \textbf{Concentration of $I_1$}. We reorganize the sum as follows.
\begin{align*}
    I_1 =  \frac{1}{n\sqrt{r}} \sum_{j'=1}^r \sum_{i=1}^n    [\sigma(\wb^{*\top}  \Pb_{j'} \xb_{i})-\sigma(0)]\cdot \frac{1}{\sqrt{r}} \sum_{j=1}^r \zb^\top\Pb_j\xb_i.
\end{align*}
Let
\begin{align}\label{eq:def_Vi}
    U_{ij'} = \sigma(\wb^{*\top}  \Pb_{j'} \xb_{i})-\sigma(0),~ V_i = \frac{1}{\sqrt{r}} \sum_{j=1}^r \zb^\top\Pb_j\xb_i,~ i=1,\ldots,n.
\end{align}
By Lipschitz condition, for $i=1,\ldots, n$ we have $|U_{ij'}| \leq   L|\wb^{*\top} \Pb_{j'} \xb_{i}|$. Therefore by Lemma~\ref{lemma:Gaussiantail} and union bound, with probability at least $1-\eta$, $|U_{ij'}| \leq R$
for all $i=1,\ldots, n$ and $j'=1,\ldots, r$, where $ R = L\|\wb^*\|_2  \sqrt{2\log(2nr/\eta)}$.
Moreover, $V_1,\ldots, V_n$ are i.i.d. standard normal random variables.
Let $\hat{U}_{ij'} = U_{ij'}\ind (|U_{ij'}| \leq R) $, then we have
\begin{align}\label{eq:decomp_I1}
    \Bigg| \frac{1}{n} \sum_{i=1}^n U_{ij'} V_i - \EE(U_{1j'} V_1) \Bigg| \leq & \Bigg| \frac{1}{n} \sum_{i=1}^n (U_{ij'} - \hat{U}_{ij'}) V_i \Bigg| + \Bigg| \frac{1}{n} \sum_{i=1}^n \hat{U}_{ij'} V_i - \EE(\hat{U}_{1j'} V_1)\Bigg| \notag\\
    &\qquad+ \big| \EE(U_{1j'} V_1) - \EE(\hat{U}_{1j'} V_1)  \big|.
\end{align}
We now proceed to bound the three terms on the right-hand side above. By definition of $R$, with probability at least $1-\eta$ the first term on the right hand side of \eqref{eq:decomp_I1} vanishes for all $j'=1,\ldots,r$ and $\zb\in \cN_{1/2}$. For the second term, by Lemma~\ref{lemma:subgaussianproduct} we have
\begin{align*}
    \| \hat{U}_{ij'} V_i \|_{\psi_1} \leq C_1R
\end{align*}
for some absolute constant $C_1$. Therefore by Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/6$, we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n (U_{ij'} - \hat{U}_{ij'}) V_i \Bigg| \leq C_2 R\sqrt{\frac{k\log(60r/\delta)}{n}}
\end{align*}
\textcolor{red}{should the left hand side be the second term?}for all $j'=1,\ldots, r$ and $\zb\in \cN_{1/2}$, where $C_2$ is an absolute constant.
For the third term, we have
\begin{align*}
    \big| \EE(U_{1j'} V_1) - \EE(\hat{U}_{1j'} V_1)  \big| \leq \EE \big(\big| U_{1j'} - \hat{U}_{1j'}\big|\cdot V_1 \big) = \EE (| U_{1j'}|\cdot \ind (U_{1j'} > R)\cdot V_1 ).
\end{align*}
Applying Cauchy-Schwarz inequality gives
\begin{align*}
    \big| \EE(U_{1j'} V_1) - \EE(\hat{U}_{1j'} V_1)  \big| \leq C_3\sqrt{\eta}\|\wb^*\|_2^2,
\end{align*}
where $C_3$ is an absolute constant. Therefore, with probability at least $1-\eta - \delta/6$, we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n U_{ij'} V_i - \EE(U_{1j'} V_1) \Bigg| \leq C_2 L\|\wb^*\|_2  \sqrt{\frac{2k\log(2nr/\eta)\log(60r/\delta)}{n}} + C_3\sqrt{\eta}\|\wb^*\|_2^2
\end{align*}
for all $j'=1,\ldots, r$. Setting $\eta = \min\{\delta/6, 1/n\}$ and plugging the inequality above into the definition of $I_1$, we have that with probability at least $1-\delta/3$,
\begin{align}\label{eq:directionconcentrationNO1}
    |I_1 - \EE[\zb^\top \hat{\wb}] | \leq C_2 L\|\wb^*\|_2  \sqrt{\frac{2rk\log(2n^2r)\log(60r/\delta)}{n}} + C_3\|\wb^*\|_2^2\sqrt{\frac{r}{n}}
\end{align}
for all $\zb \in \cN_{1/2}$.

\iffalse
\begin{align*}
    U^{(j)}_{ij'} &= [\sigma(\wb^{*\top}  \Pb_{j'} \xb_{i}) - \sigma(0)] \cdot \zb^\top\Pb_j\xb_i,\\
    V^{(j)}_{ij'} &= \sigma(0) \cdot \zb^\top\Pb_j\xb_i.
\end{align*}

By Lemma~\ref{lemma:subgaussianproduct} and (5.15) in \cite{vershynin2010introduction} as an equivalent definition of $\psi_1$-norm, we have
$$
\|U^{(j)}_{ij'}\|_{\psi_1} \leq L\|\wb^{*\top} \Pb_{j'} \xb_{i} \cdot  \zb^\top\Pb_j\xb_i \|_{\psi_1} \leq  C_1L\|\wb^{*}\|,
$$
where $C_1$ is an absolute constant. Applying Proposition~5.16 in \cite{vershynin2010introduction} to $\{U^{(j)}_{ij'}\}$, we have that with probability at least $1-\delta/3$, we have
\begin{align*}
    \Bigg|\frac{1}{n} \sum_{i=1}^n U^{(j)}_{ij'} - \delta_{j,j'}\EE(\zb^\top \hat{\wb})\Bigg| \leq C_2L\|\wb^*\| \sqrt{\frac{k\log[30r^2/\delta]}{n}}
\end{align*}
for all $j,j'\in [r]$ and all $\zb \in \cN_{1/2}$,
where $C_2$ is an absolute constant. Therefore with probability at least $1-\delta/3$, we have
\begin{align}\label{eq:directionconcentrationNO2}
    \Big|I_1^{(j)} - \EE(\zb^\top \hat{\wb})\Big| \leq C_2Lr\|\wb^*\| \sqrt{\frac{k\log[30r^2/\delta]}{n}}
\end{align}
for all $j\in [r]$ and all $\zb \in \cN_{1/2}$.
\fi

\noindent \textbf{Concentration of $I_2$}. Since $\cI_{1},\ldots,\cI_{r}$ do not overlap, $I_2$ is an average of $nr$ independent Gaussian random variables. For any $\zb \in\cN_{1/2}$, the $\psi_2$-norm of $\zb^\top\Pb_j\xb_i$ is the $\psi_2$-norm of standard normal random variables. Therefore by Proposition~5.10 in \cite{vershynin2010introduction}, with probability at least $1-\delta/3$, we have
\begin{align}\label{eq:directionconcentrationNO2}
    |I_2|\leq C_4\sigma(0)\sqrt{\frac{rk\log(15e/\delta)}{n}},
\end{align}
where $C_4$ is an absolute constant.

\noindent \textbf{Concentration of $I_3$}.
We have
\begin{align*}
    I_3= \frac{1}{rn} \sum_{j=1}^r \sum_{i=1}^n \epsilon_{i}\cdot\zb^\top\Pb_j\xb_i.
\end{align*}
Since $\cI_{1},\ldots,\cI_{r}$ do not overlap, for $j'\neq j$, $\Pb_{j'} \xb_{i}$ and $\Pb_{j} \xb_{i}$ contains different entries of $\xb_i$. Therefore, let $v_1,\ldots, v_n \sim N(0,1)$ be i.i.d. standard normal random variables, then we have \textcolor{red}{$v_i$ are the same as $V_i$ defined in \eqref{eq:def_Vi}}
\begin{align*}
    I_3 = \frac{1}{n\sqrt{r}}  \sum_{i=1}^n \epsilon_{i}\cdot \sum_{j=1}^r\frac{1}{\sqrt{r}}\zb^\top\Pb_j\xb_i \overset{d}{=} \frac{1}{n\sqrt{r}}  \sum_{i=1}^n \epsilon_{i}\cdot v_i.
\end{align*}
Moreover we have $\|\epsilon_{i}\cdot v_i\|_{\psi_1} \leq C_4 \nu$ for some absolute constant $C_5$. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/3$, we have
\begin{align}\label{eq:directionconcentrationNO3}
    |I_3|  \leq C_6\nu \sqrt{\frac{k\log(30/\delta)}{nr}}
\end{align}
for all $\zb\in \cN_{1/2}$, where $C_6$ is an absolute constant.
By \eqref{eq:directionconcentrationNO1}, \eqref{eq:directionconcentrationNO2},\eqref{eq:directionconcentrationNO3} and the definition of $\hat{\wb}$, we have
\begin{align*}
    |\zb^\top (\hat{\wb} - \EE[\hat{\wb}])| \leq &  C_2 L\|\wb^*\|_2  \sqrt{\frac{2rk\log(2n^2r)\log(60r/\delta)}{n}} + C_3\|\wb^*\|_2^2\sqrt{\frac{r}{n}} \\
    &\qquad+ C_4\sigma(0)\sqrt{\frac{k\log(15e/\delta)}{nr}}
    + C_6 \nu\sqrt{\frac{k\log(30/\delta)}{nr}}
\end{align*}
for all $\zb\in \cN_{1/2}$. Now by Lemma~5.3 in \cite{vershynin2010introduction} and Lemma~\ref{lemma:momentcalculation}, we have that with probability at least $1-\delta$,
\begin{align*}
    \bigg\| \hat{\wb} - \frac{\gamma(\|\wb^*\|)}{\|\wb^*\|} \wb^* \bigg\|_2 \leq & C\Bigg[ L\|\wb^*\|_2  \sqrt{\frac{2rk\log(2n^2r)\log(60r/\delta)}{n}} + \|\wb^*\|_2^2\sqrt{\frac{r}{n}} \\
    &\qquad+ \sigma(0)\sqrt{\frac{rk\log(15e/\delta)}{n}}
    + \nu\sqrt{\frac{k\log(30/\delta)}{nr}} \Bigg],
\end{align*}
where $C$ is an absolute constant. The first result of Lemma~\ref{lemma:directionconcentrationNO} directly follows the inequality above.
The second result of Lemma~\ref{lemma:directionconcentrationNO} follows by Lemma~\ref{lemma:distance2innerproduct}.
\end{proof}

\subsection{Non-overlapped CNN, 2 layer}
In this section we consider the convolutional neural network with unknown second layer parameters $\vb^*$.
\textcolor{red}{use $v_j^*$ instead of $\vb_j^*$ because it's a scalar}
\begin{align}\label{eq:cnndef2layer}
    y_{i} = \sum_{j=1}^r  v^*_j\sigma(\wb^{*\top} \Pb_{j} \xb_{i}) + \epsilon_{i},
\end{align}

\textcolor{red}{how about the estimation error bound of $\wb$?}

\textcolor{red}{The following bound is a bound on the bias?}

\begin{lemma}\label{lemma:uhatexpectationNO2layer}
For any $(\xb,y)$ generated by the model in \eqref{eq:cnndef2layer}, we have
\begin{align*}
    \EE (\hat{\ub}_j) = \frac{\gamma(\|\wb^*\|_2)}{\|\wb^*\|_2} v^*_j \wb^*,~j=1,\ldots,r.
\end{align*}
\end{lemma}

\begin{lemma}\label{lemma:uhatconcentrationNO2layer}
In Algorithm~\ref{alg:NOCNN2layer}, with probability at least $1-\delta$ we have
\begin{align*}
   \|\hat{\ub}_j - \EE[\hat{\ub}_j] \|_2 \leq C \Bigg\{ M\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} +  [ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}} \Bigg\},
\end{align*}
for all $j=1,\ldots,r$, where $M = \max\{ L\|\wb^*\|_2,\|\wb^*\|_2^2\} $ and $C$ is an absolute constant.
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lemma:uhatconcentrationNO2layer}]
Let $\cN_{1/2}$ be a $1/2$-net covering the unit Euclidean sphere $S^{k-1}$, then by Lemma~5.2 in \cite{vershynin2010introduction}, we have
$
|\cN_{1/2}| \leq 5^k.
$
For any vector $\zb\in \cN_{1/2}$, we have
\begin{align*}
    \zb^\top \hat{\ub}_j = \frac{1}{n} \sum_{i=1}^n y_i \cdot \zb^\top\Pb_j\xb_i,~j=1,\ldots,r.
\end{align*}
We next proof the concentration result for $\hat{\ub}_1$, and the proofs for $\hat{\ub}_2,\ldots, \hat{\ub}_r$ are exactly the same. Plugging \eqref{eq:cnndef2layer} into the equation above gives
\begin{align*}
    \zb^\top \hat{\ub}_1 =  \frac{1}{n}  \sum_{i=1}^n  \Bigg[\sum_{j'=1}^r v^*_{j'}\sigma(\wb^{*\top} \Pb_{j'} \xb_{i}) + \epsilon_{i}\Bigg]\cdot\zb^\top\Pb_1\xb_i =  I_1 + I_2 ,
\end{align*}
where
\begin{align*}
   &I_1  = \frac{1}{n} \sum_{j'=1}^r \sum_{i=1}^n [v^*_{j'}\sigma(\wb^{*\top}  \Pb_{j'} \xb_{i})-\sigma(0)]\cdot\zb^\top\Pb_1\xb_i,\\
   &I_2 = \frac{1}{n} \sum_{i=1}^n \Bigg[\sigma(0)\cdot\sum_{j'=1}^r v^*_{j'} + \epsilon_{i} \Bigg] \cdot\zb^\top\Pb_1\xb_i,\\
\end{align*}
It is easy to see that $\EE(I_1) = \EE(\zb^\top \hat{\wb}) $ and $\EE(I_2) =0$. We now analyze the concentration of the two terms.

\noindent \textbf{Concentration of $I_1$}.
Let
$$
U_{ij'} = \sigma(\wb^{*\top}  \Pb_{j'} \xb_{i})-\sigma(0),~ V_i = \zb^\top\Pb_j\xb_i,~ i=1,\ldots,n.
$$
By Lipschitz condition, for $i=1,\ldots, n$ we have $|U_{ij'}| \leq   L|\wb^{*\top} \Pb_{j'} \xb_{i}|$. Therefore by Lemma~\ref{lemma:Gaussiantail} and union bound, with probability at least $1-\eta$, $|U_{ij'}| \leq R$
for all $i=1,\ldots, n$ and $j'=1,\ldots, r$, where $ R = L\|\wb^*\|_2  \sqrt{2\log(2nr/\eta)}$.
Moreover, $V_1,\ldots, V_n$ are i.i.d. standard normal random variables.
Let $\hat{U}_{ij'} = U_{ij'}\ind (|U_{ij'}| \leq R) $, then we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n U_{ij'} V_i - \EE(U_{1j'} V_1) \Bigg| \leq & \Bigg| \frac{1}{n} \sum_{i=1}^n (U_{ij'} - \hat{U}_{ij'}) V_i \Bigg| + \Bigg| \frac{1}{n} \sum_{i=1}^n \hat{U}_{ij'} V_i - \EE(\hat{U}_{1j'} V_1)\Bigg| \\
    &\qquad+ \big| \EE(U_{1j'} V_1) - \EE(\hat{U}_{1j'} V_1)  \big|.
\end{align*}
We now proceed to bound the three terms on the right-hand side above. By definition of $R$, with probability at least $1-\eta$ the first term vanishes for all $j'=1,\ldots,r$ and $\zb\in \cN_{1/2}$. For the second term, by Lemma~\ref{lemma:subgaussianproduct} we have
\begin{align*}
    \| \hat{U}_{ij'} V_i \|_{\psi_1} \leq C_1R
\end{align*}
for some absolute constant $C_1$. Therefore by Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/(4r)$, we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n (U_{ij'} - \hat{U}_{ij'}) V_i \Bigg| \leq C_2 R\sqrt{\frac{k\log(40r^2/\delta)}{n}}
\end{align*}
for all $j'=1,\ldots, r$ and $\zb\in \cN_{1/2}$, where $C_2$ is an absolute constant.
For the third term, we have
\begin{align*}
    \big| \EE(U_{1j'} V_1) - \EE(\hat{U}_{1j'} V_1)  \big| \leq \EE \big(\big| U_{1j'} - \hat{U}_{1j'}\big|\cdot V_1 \big) = \EE (| U_{1j'}|\cdot \ind (U_{1j'} > R)\cdot V_1 ).
\end{align*}
Applying Cauchy-Schwarz inequality gives
\begin{align*}
    \big| \EE(U_{1j'} V_1) - \EE(\hat{U}_{1j'} V_1)  \big| \leq C_3\sqrt{\eta}\|\wb^*\|_2^2,
\end{align*}
where $C_3$ is an absolute constant. Therefore, with probability at least $1-\eta - \delta/(4r)$, we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n U_{ij'} V_i - \EE(U_{1j'} V_1) \Bigg| \leq C_2 L\|\wb^*\|_2  \sqrt{\frac{2k\log(2nr/\eta)\log(40r^2/\delta)}{n}} + C_3\sqrt{\eta}\|\wb^*\|_2^2
\end{align*}
for all $j'=1,\ldots, r$. Setting $\eta = \min\{\delta/(4r), 1/n\}$ and plugging the inequality above into the definition of $I_1$, we have that with probability at least $1-\delta/(2r)$,
\begin{align}\label{eq:directionconcentrationNO2layer1}
    |I_1 - \EE[\zb^\top \hat{\wb}] | \leq C_2 Lr\|\wb^*\|_2 \|\vb^*\|_1  \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} + C_3\|\wb^*\|_2^2\|\vb^*\|_1 \frac{1}{\sqrt{n}}
\end{align}
for all $\zb \in \cN_{1/2}$.

\noindent \textbf{Concentration of $I_2$}.
By Lemma~\ref{lemma:subgaussianproduct} we have $\|[\sigma(0)+\epsilon_{i}]\cdot \zb^\top\Pb_1\xb_i\|_{\psi_1} \leq C_4 [ \|\vb^*\|_1 \sigma(0) + \nu ]$ for some absolute constant $C_4$. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/(2r)$, we have
\begin{align}\label{eq:directionconcentrationNO2layer2}
    |I_3|  \leq C_5[ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}}
\end{align}
for all $\zb\in \cN_{1/2}$, where $C_5$ is an absolute constant.
By \eqref{eq:directionconcentrationNO2layer1}, \eqref{eq:directionconcentrationNO2layer2}, and the definition of $\hat{\ub}_1$, with probability at least $1 - \delta/r$, we have
\begin{align*}
    |\zb^\top (\hat{\ub}_1 - \EE[\hat{\ub}_1])| \leq & C_2 L\|\wb^*\|_2\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} + C_3\|\wb^*\|_2^2\|\vb^*\|_1 \frac{1}{\sqrt{n}} \\
    &+ C_5[ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}}
\end{align*}
for all $\zb\in \cN_{1/2}$. Now by Lemma~5.3 in \cite{vershynin2010introduction}, we have
\begin{align*}
    \|\hat{\ub}_1 - \EE[\hat{\ub}_1] \|_2 \leq C \Bigg\{ M\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} +  [ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}} \Bigg\},
\end{align*}
where $M = \max\{ L\|\wb^*\|_2,\|\wb^*\|_2^2\} $.
By the same proof, we have that with probability at least $1-\delta$,
\begin{align*}
   \|\hat{\ub}_j - \EE[\hat{\ub}_j] \|_2 \leq C \Bigg\{ M\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} +  [ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}} \Bigg\},
\end{align*}
for all $j=1,\ldots,r$. This completes the proof.
\end{proof}

\begin{lemma}\label{lemma:recoversignNO2layer}
There exists an absolute constant $C$ such that with probability at least $1-\delta$, for any $j=1,\ldots,r$, if
\begin{align*}
    |v^*_j| \gamma(\|\wb^*\|_2)> C\Bigg\{ M\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} +  [ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}} \Bigg\},
\end{align*}
where $M = \max\{ L\|\wb^*\|_2,\|\wb^*\|_2^2\} $, then $a_j = \sign(v^*_l v^*_j)$.
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lemma:recoversignNO2layer}]
Let $\zeta = \gamma(\|\wb^*\|_2)$ and
\begin{align*}
    \eta = C'\Bigg\{ M\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} +  [ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}} \Bigg\},
\end{align*}
where $C'$ is the absolute constant given by Lemma~\ref{lemma:uhatconcentrationNO2layer}. We set $C = 5C'$. Then by Lemma~\ref{lemma:uhatexpectationNO2layer} and Lemma~\ref{lemma:uhatconcentrationNO2layer}, with probability at least $1-\delta$ we have
\begin{align*}
   \big|\|\hat{\ub}_j \|_2 - \zeta v^*_j| \big| \leq \eta,~j=1,\ldots,r.
\end{align*}
By the definition of $l$, we have
\begin{align*}
    \zeta|v^*_j|\leq \big| \zeta v^*_j - \|\hat{\ub}_j \|_2\big| + \|\hat{\ub}_l \|_2 \leq \eta + \big| \zeta v^*_l - \|\hat{\ub}_l \|_2\big| + \zeta|v^*_l| \leq 2\eta + \zeta |v^*_l|.
\end{align*}
By the inequality above and the assumption that $\zeta |v^*_j| >5\eta$, we have $\zeta |v^*_l| > \eta$. Plugging this into the inequality above again to cancel $eta$ gives $|v^*_j| \leq 3 |v^*_l|$.
Moreover, we have
\begin{align*}
    \big|\hat{\ub}_l^\top \hat{\ub}_j - \EE(\hat{\ub}_l^\top) \EE(\hat{\ub}_j) \big| &\leq \big|\hat{\ub}_l^\top \hat{\ub}_j - \hat{\ub}_l^\top \EE(\hat{\ub}_j) \big| + \big| \hat{\ub}_l^\top \EE(\hat{\ub}_j) - \EE(\hat{\ub}_l^\top) \EE(\hat{\ub}_j) \big|\\
    &\leq \eta \big[\|\hat{\ub}_l\|_2 + \|\EE(\hat{\ub}_1)\|_2\big] \\
    &\leq   \eta \big[\zeta (| v^*_l| + | v^*_j|) + \eta \big]\\
    &< 5\zeta \eta |v^*_l|
\end{align*}
On the other hand, we have
$\EE(\hat{\ub}_1^\top) \EE(\hat{\ub}_j) = \zeta^2v^*_1v^*_j$, and
\begin{align*}
    \big|\hat{\ub}_l^\top \hat{\ub}_j - \EE(\hat{\ub}_l^\top) \EE(\hat{\ub}_j) \big| <5\zeta \eta |v^*_l| < \zeta^2|v^*_l||v^*_j| = \big|\EE(\hat{\ub}_1^\top) \EE(\hat{\ub}_j)\big|.
\end{align*}
The inequality above implies that $a_j = \sign(\hat{\ub}_l^\top \hat{\ub}_j) = \sign[\EE(\hat{\ub}_1^\top) \EE(\hat{\ub}_j)] = \sign(v^*_l v^*_j)$.
\end{proof}

\begin{lemma}\label{lemma:vtildeNO2layer}
In Algorithm~\ref{alg:NOCNN2layer}, with probability at least $1-\delta$ we have
\begin{align*}
    \big| \tilde{v}_j - &\sign( v^*_l)\gamma(\|\wb^*\|)  v^*_j \big| \\
    &\leq C \Bigg\{ M\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} +  [ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}} \Bigg\},
\end{align*}
where $M = \max\{ L\|\wb^*\|_2,\|\wb^*\|_2^2\} $ and $C$ is the absolute constant.
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lemma:vtildeNO2layer}]
Let $$
\eta = C' \Bigg\{ M\|\vb^*\|_1   \sqrt{\frac{2k\log(2n^2r)\log(40r^2/\delta)}{n}} +  [ \|\vb^*\|_1 \sigma(0) + \nu ] \sqrt{\frac{k\log(20r/\delta)}{n}} \Bigg\},
$$
where $C'$ is the absolute constant given by Lemma~\ref{lemma:uhatconcentrationNO2layer}. Denote $\zeta = \gamma(\|\wb^*\|_2)$. Then by Lemma~\ref{lemma:uhatexpectationNO2layer} and Lemma~\ref{lemma:uhatconcentrationNO2layer}, with probability at least $1-\delta$ we have
\begin{align}\label{eq:vtildeNO2layer1}
   \big|\|\hat{\ub}_j \|_2 - \zeta v^*_j| \big| \leq \eta,~j=1,\ldots,r.
\end{align}
Let $C''$ be the absolute constant introduced by Lemma~\ref{lemma:recoversignNO2layer} and $c = C''/C'$. For each $v^*_j$, $j=1,\ldots,r$,
we consider two cases.

\noindent (i) If $|v^*_j| \leq c\zeta$, then by \eqref{eq:vtildeNO2layer1} we have
\begin{align*}
    |\tilde{v}_j| = \|\hat{\ub}_j \|_2 \leq (c+1)\eta,
\end{align*}
and therefore
\begin{align*}
    \big| \tilde{v}_j - \sign( v^*_l)\zeta  v^*_j \big| \leq |\tilde{v}_j| + \zeta | v^*_j| \leq (2c+1) \eta.
\end{align*}

\noindent (ii) If $|v^*_j| > C\eta /\zeta$, by Lemma~\ref{lemma:recoversignNO2layer}, with probability at least $1-\delta$ we have $a_j = \sign(v^*_l v^*_j)$.
Therefore by \eqref{eq:vtildeNO2layer1} we have
\begin{align*}
    \big| \tilde{v}_j - \sign( v^*_l)\zeta  v^*_j \big| = \big| \sign(v^*_l v^*_j) \|\hat{\ub}_j\|_2 - \sign( v^*_l)\zeta  v^*_j \big| = \big|  \|\hat{\ub}_j\|_2 - \zeta  |v^*_j| \big| \leq \eta.
\end{align*}
This completes the proof.
\end{proof}

\subsection{Overlapped CNN}

\begin{lemma}\label{lemma:directionconcentrationOwtildeexpectation}
In Algorithm~\ref{alg:OCNN}, we have
\textcolor{red}{change $l'$ to something else, for example, $j$ or $s$}
\begin{align*}
    \tilde{\wb}_l = \frac{\gamma(\|\wb^*\|_2)}{\|\wb^*\|_2} \sum_{s=1}^l \wb^*_{s},~l=1,\ldots,k
\end{align*}
\end{lemma}
\begin{proof}

\end{proof}

\begin{lemma}\label{lemma:directionconcentrationOwtilde}
With probability at least $1-\delta$, we ahve
\begin{align*}
    \| \tilde{\wb} - \EE(\tilde{\wb}) \|_2 \leq & C\Bigg[M' r  \sqrt{\frac{2k\log(2n^2r)\log(40r/\delta)}{n}} +  \nu \sqrt{\frac{k\log(20/\delta)}{n}} \Bigg],
\end{align*}
where $M' = \max\{ L[\|\wb^*\|_2 + |\sigma(0)|], \|\wb^*\|_2^2 + \sigma^2(0) \}$, and $C$ is an absolute constant.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lemma:directionconcentrationOwtilde}]
Let $\cN_{1/2}$ be a $1/2$-net covering the unit Euclidean sphere $S^{k-1}$, then by Lemma~5.2 in \cite{vershynin2010introduction}, we have
$
|\cN_{1/2}| \leq 5^k.
$
For any vector $\zb\in \cN_{1/2}$, we have
\begin{align*}
    \zb^\top \tilde{\wb} = \frac{1}{n} \sum_{i=1}^n y_i \cdot \zb^\top\Pb_1\xb_i.
\end{align*}
Plugging \eqref{eq:cnndef} into the equation above gives
\begin{align*}
    \zb^\top \tilde{\wb} =  \frac{1}{n}  \sum_{i=1}^n  \Bigg[\sum_{j=1}^r \sigma(\wb^{*\top} \Pb_{j} \xb_{i}) + \epsilon_{i}\Bigg]\cdot\zb^\top\Pb_1\xb_i =  I_1 + I_2 + I_3 ,
\end{align*}
where
\begin{align*}
   &I_1  = \frac{1}{n} \sum_{j=1}^r \sum_{i=1}^n \sigma(\wb^{*\top}  \Pb_{j} \xb_{i})\cdot\zb^\top\Pb_1\xb_i,\\
   &I_2 = \frac{1}{n} \sum_{i=1}^n \epsilon_{i}\cdot\zb^\top\Pb_j\xb_i.
\end{align*}

It is easy to see that $\EE(I_1) = \EE[\zb^\top \tilde{\wb}] $ and $\EE(I_2) =0$. We now analyze the concentration of the two terms.

\noindent \textbf{Concentration of $I_1$}.
Let
$$
U_{ij} = \sigma(\wb^{*\top}  \Pb_{j} \xb_{i}),~ V_i = \zb^\top\Pb_1\xb_i,~ i=1,\ldots,n.
$$
By Lipschitz condition, for $i=1,\ldots, n$ we have $|U_{ij}| \leq   L|\wb^{*\top} \Pb_{j} \xb_{i}| + |\sigma(0)|$. Therefore by Lemma~\ref{lemma:Gaussiantail} and union bound, with probability at least $1-\eta$, $|U_{ij'}| \leq R$
for all $i=1,\ldots, n$ and $j=1,\ldots, r$, where $ R = L\|\wb^*\|_2  \sqrt{2\log(2nr/\eta)} + |\sigma(0)|$.
Moreover, $V_1,\ldots, V_n$ are i.i.d. standard normal random variables.
Let $\hat{U}_{ij} = U_{ij}\ind (|U_{ij}| \leq R) $, then we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n U_{ij} V_i - \EE(U_{1j} V_1) \Bigg| \leq & \Bigg| \frac{1}{n} \sum_{i=1}^n (U_{ij} - \hat{U}_{ij}) V_i \Bigg| + \Bigg| \frac{1}{n} \sum_{i=1}^n \hat{U}_{ij} V_i - \EE(\hat{U}_{1j} V_1)\Bigg| \\
    &\qquad+ \big| \EE(U_{1j} V_1) - \EE(\hat{U}_{1j} V_1)  \big|.
\end{align*}
We now proceed to bound the three terms on the right-hand side above. By definition of $R$, with probability at least $1-\eta$ the first term vanishes for all $j=1,\ldots,r$ and $\zb\in \cN_{1/2}$. For the second term, by Lemma~\ref{lemma:subgaussianproduct} we have
\begin{align*}
    \| \hat{U}_{ij} V_i \|_{\psi_1} \leq C_1R
\end{align*}
for some absolute constant $C_1$. Therefore by Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/4$, we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n (U_{ij} - \hat{U}_{ij'}) V_i \Bigg| \leq C_2 R\sqrt{\frac{k\log(40r/\delta)}{n}}
\end{align*}
for all $j=1,\ldots, r$ and $\zb\in \cN_{1/2}$, where $C_2$ is an absolute constant.
For the third term, we have
\begin{align*}
    \big| \EE(U_{1j} V_1) - \EE(\hat{U}_{1j} V_1)  \big| \leq \EE \big(\big| U_{1j} - \hat{U}_{1j}\big|\cdot V_1 \big) = \EE (| U_{1j}|\cdot \ind (U_{1j} > R)\cdot V_1 ).
\end{align*}
Applying Cauchy-Schwarz inequality gives
\begin{align*}
    \big| \EE(U_{1j} V_1) - \EE(\hat{U}_{1j} V_1)  \big| \leq C_3\sqrt{\eta}[\|\wb^*\|_2^2 + \sigma^2(0)],
\end{align*}
where $C_3$ is an absolute constant. Therefore, with probability at least $1-\eta - \delta/4$, we have
\begin{align*}
    \Bigg| \frac{1}{n} \sum_{i=1}^n U_{ij} V_i - \EE(U_{1j} V_1) \Bigg| \leq C_2 R  \sqrt{\frac{k\log(40r/\delta)}{n}} + C_3\sqrt{\eta}\cdot \big(\|\wb^*\|_2^2 + \sigma^2(0)\big)
\end{align*}
for all $j=1,\ldots, r$. Setting $\eta = \min\{\delta/4, 1/n\}$ and plugging the inequality above into the definition of $I_1$, we have that with probability at least $1-\delta/2$,
\begin{align}\label{eq:directionconcentrationOwtilde1}
    |I_1 - \EE[\zb^\top \tilde{\wb}] | \leq C_4 M' r  \sqrt{\frac{2k\log(2n^2r)\log(40r/\delta)}{n}}
\end{align}
for all $\zb \in \cN_{1/2}$, where $M' = \max\{ L[\|\wb^*\|_2 + |\sigma(0)|], \|\wb^*\|_2^2 + \sigma^2(0) \}$ and $C_4$ is an absolute constant.

\iffalse
\begin{align*}
    U^{(j)}_{ij'} &= [\sigma(\wb^{*\top}  \Pb_{j'} \xb_{i}) - \sigma(0)] \cdot \zb^\top\Pb_j\xb_i,\\
    V^{(j)}_{ij'} &= \sigma(0) \cdot \zb^\top\Pb_j\xb_i.
\end{align*}

By Lemma~\ref{lemma:subgaussianproduct} and (5.15) in \cite{vershynin2010introduction} as an equivalent definition of $\psi_1$-norm, we have
$$
\|U^{(j)}_{ij'}\|_{\psi_1} \leq L\|\wb^{*\top} \Pb_{j'} \xb_{i} \cdot  \zb^\top\Pb_j\xb_i \|_{\psi_1} \leq  C_1L\|\wb^{*}\|,
$$
where $C_1$ is an absolute constant. Applying Proposition~5.16 in \cite{vershynin2010introduction} to $\{U^{(j)}_{ij'}\}$, we have that with probability at least $1-\delta/3$, we have
\begin{align*}
    \Bigg|\frac{1}{n} \sum_{i=1}^n U^{(j)}_{ij'} - \delta_{j,j'}\EE(\zb^\top \hat{\wb})\Bigg| \leq C_2L\|\wb^*\| \sqrt{\frac{k\log[30r^2/\delta]}{n}}
\end{align*}
for all $j,j'\in [r]$ and all $\zb \in \cN_{1/2}$,
where $C_2$ is an absolute constant. Therefore with probability at least $1-\delta/3$, we have
\begin{align}\label{eq:directionconcentrationOwtilde1}
    \Big|I_1^{(j)} - \EE(\zb^\top \hat{\wb})\Big| \leq C_2Lr\|\wb^*\| \sqrt{\frac{k\log[30r^2/\delta]}{n}}
\end{align}
for all $j\in [r]$ and all $\zb \in \cN_{1/2}$.
\fi

\noindent \textbf{Concentration of $I_2$}.
We have
\begin{align*}
    I_2= \frac{1}{n} \sum_{i=1}^n \epsilon_{i}\cdot\zb^\top\Pb_1\xb_i.
\end{align*}
By Lemma~\ref{lemma:subgaussianproduct}, we have
$\|\epsilon_{i}\cdot \zb^\top\Pb_1\xb_i\|_{\psi_1} \leq C_5 \nu$ for some absolute constant $C_5$. By Proposition~5.16 in \cite{vershynin2010introduction}, with probability at least $1-\delta/2$, we have
\begin{align}\label{eq:directionconcentrationOwtilde2}
    |I_2|  \leq C_6\nu \sqrt{\frac{k\log(20/\delta)}{n}}
\end{align}
for all $\zb\in \cN_{1/2}$, where $C_6$ is an absolute constant.
By \eqref{eq:directionconcentrationOwtilde1}, \eqref{eq:directionconcentrationOwtilde2}, and the definition of $\tilde{\wb}$, we have
\begin{align*}
    \big|\zb^\top \big(\tilde{\wb} - \EE[\tilde{\wb}]\big)\big| \leq &  C_4 M' r  \sqrt{\frac{2k\log(2n^2r)\log(40r/\delta)}{n}} +  C_6\nu \sqrt{\frac{k\log(20/\delta)}{n}}
\end{align*}
for all $\zb\in \cN_{1/2}$. Now by Lemma~5.3 in \cite{vershynin2010introduction} and Lemma~\ref{lemma:momentcalculation}, we have that with probability at least $1-\delta$,
\begin{align*}
    \| \tilde{\wb} - \EE[\tilde{\wb}] \|_2 \leq & C\Bigg[M' r  \sqrt{\frac{2k\log(2n^2r)\log(40r/\delta)}{n}} +  \nu \sqrt{\frac{k\log(20/\delta)}{n}} \Bigg],
\end{align*}
where $C$ is an absolute constant. This completes the proof.

\iffalse
note that
\begin{align*}
    \|\hat\wb-\EE[\hat\wb]\|_2^2\geq 2\|\hat\wb\|_2\cdot\|\EE[\hat\wb]\|_2-2\langle\hat\wb,\EE[\hat\wb]\rangle.
\end{align*}
It immediately implies that
\begin{align*}
    \bigg\langle\frac{\hat\wb}{\|\hat\wb\|_2},\frac{\EE[\hat\wb]}{\|\EE[\hat\wb]\|_2}\bigg\rangle\geq 1-\frac{1}{2\|\EE[\hat\wb]\|}\|\hat\wb-\EE[\hat\wb]\|_2^2
\end{align*}
\fi
\end{proof}

\begin{lemma}\label{lemma:directionconcentrationO}
In Algorithm~\ref{alg:OCNN}, we have
\begin{align*}
    \bigg\| \hat{\wb} - \frac{\gamma(\|\wb^*\|)}{\|\wb^*\|} \wb^* \bigg\|_2 &\leq C\Bigg[M' r  \sqrt{\frac{2k\log(2n^2r)\log(40r/\delta)}{n}} +  \nu \sqrt{\frac{k\log(20/\delta)}{n}} \Bigg], \text{ and}\\
    \bigg\langle \frac{\hat{\wb}}{\|\hat{\wb}\|_2}, \frac{\wb^*}{\|\wb^*\|_2} \bigg\rangle &\geq 1- \frac{C'}{\gamma^2(\|\wb^*\|_2)}  \Bigg[M' r  \sqrt{\frac{2k\log(2n^2r)\log(40r/\delta)}{n}} +  \nu \sqrt{\frac{k\log(20/\delta)}{n}} \Bigg]^2,
\end{align*}
where $M' = \max\{ L(\|\wb^*\|_2 + |\sigma(0)|), \|\wb^*\|_2^2 + \sigma^2(0) \}$, and $C, C'$ are absolute constants.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lemma:directionconcentrationO}]
Let
\begin{align*}
    \Ab = \begin{bmatrix}
    1       & 0 & 0 &  \dots & 0  & 0 \\
    -1       & 1 & 0 &  \dots & 0  & 0 \\
    0       & -1 & 1 &  \dots & 0  & 0 \\
    \hdotsfor{6}\\
    0       & 0 & 0 & \dots & 1  & 0 \\
    0       & 0 & 0 & \dots & -1  & 1
\end{bmatrix} \in \RR^{k\times k}.
\end{align*}
Then in Algorithm~\ref{alg:OCNN} we have $\hat{\wb} = \Ab\tilde{\wb}$. Moreover by Lemma~\ref{lemma:directionconcentrationOwtildeexpectation}, we have
\begin{align*}
    \EE[\Ab\tilde{\wb}] = \frac{\gamma(\|\wb^*\|_2)}{\|\wb^*\|_2} \wb^*.
\end{align*}
Therefore,
\begin{align}\label{eq:directionconcentrationO1}
    \bigg\| \hat{\wb} - \frac{\gamma(\|\wb^*\|_2)}{\|\wb^*\|_2} \wb^* \bigg\|_2 \leq \| \Ab \|_2 \| \tilde{\wb} - \EE[\tilde{\wb}] \|_2
\end{align}
Note that we have
\begin{align*}
    \Ab^\top \Ab= \begin{bmatrix}
    2       & -1 & 0 &  \dots & 0  & 0 \\
    -1       & 2 & -1 &  \dots & 0  & 0 \\
    0       & -1 & 2 &  \dots & 0  & 0 \\
    \hdotsfor{6}\\
    0       & 0 & 0 & \dots & 2  & -1 \\
    0       & 0 & 0 & \dots & -1  & 1
\end{bmatrix}.
\end{align*}
Therefore $\|\Ab\|_2$ is bounded by an absolute constant. The result of Lemma~\ref{lemma:directionconcentrationO} follows by \eqref{eq:directionconcentrationO1}, Lemma~\ref{lemma:directionconcentrationOwtilde} and Lemma~\ref{lemma:distance2innerproduct}.
\end{proof}

\section{Proof of Lemmas in Appendix~\ref{section:proof1} and \ref{section:proof2}}\label{section:prooflemmasinappendix}

\section{Additional Auxiliary Lemmas}\label{section:auxiliarylemmas}
The following lemma is given by \cite{yi2015regularized}
\begin{lemma}[\cite{yi2015regularized}]\label{lemma:subgaussianproduct}
For two sub-Gaussian random variables $Z_1$ and $Z_2$, $Z_1\cdot Z_2$ is a sub-exponential random variable with
\begin{align*}
    \|Z_1\cdot Z_2\|_{\psi_1} \leq C\|Z_1\|_{\psi_2}\cdot\|Z_2\|_{\psi_2},
\end{align*}
where $C$ is an absolute constant.
\end{lemma}

\begin{lemma}\label{lemma:distance2innerproduct}
For any non-zero vectors $\ub, \vb\in \RR^k$, if
    $\| \ub - \vb \|_2 \leq \rho$, then we have
\begin{align*}
    \bigg\| \frac{\ub}{\|\ub\|_2} - \frac{\vb}{\|\vb\|_2} \bigg\|_2 \leq \frac{2\rho}{\|\vb\|_2}, \text{ and } \bigg\langle \frac{\ub}{\|\ub\|_2}, \frac{\vb}{\|\vb\|_2} \bigg\rangle \geq 1-\frac{2\rho^2}{\|\vb\|_2^2}.
\end{align*}
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lemma:distance2innerproduct}]
By triangle inequality, we have $\big|\|\vb\|_2 - \|\ub\|_2 \big| \leq \| \ub - \vb \|_2 \leq \rho$. Therefore,
\begin{align*}
    \bigg\| \frac{\ub}{\|\ub\|_2} - \frac{\vb}{\|\vb\|_2} \bigg\|_2 & \leq \bigg\| \frac{\ub}{\|\ub\|_2} - \frac{\ub}{\|\vb\|_2} \bigg\|_2 + \bigg\| \frac{\ub}{\|\vb\|_2} - \frac{\vb}{\|\vb\|_2} \bigg\|_2\\
    &= \|\ub\|_2\cdot \frac{\big|\|\vb\|_2 - \|\ub\|_2 \big|}{\|\ub\|_2\|\vb\|_2} + \frac{\|\ub - \vb\|_2}{\|\vb\|_2} \\
    &\leq \frac{2\rho}{\|\vb\|_2}.
\end{align*}
Moreover, we have
\begin{align*}
    -2\bigg\langle \frac{\ub}{\|\ub\|_2}, \frac{\vb}{\|\vb\|_2} \bigg\rangle + 2 = \bigg\| \frac{\ub}{\|\ub\|_2} - \frac{\vb}{\|\vb\|_2} \bigg\|_2^2  \leq  \frac{4\rho^2}{\|\vb\|_2^2}.
\end{align*}
Therefore we have
\begin{align*}
    \bigg\langle \frac{\ub}{\|\ub\|_2}, \frac{\vb}{\|\vb\|_2} \bigg\rangle \geq 1-\frac{2\rho^2}{\|\vb\|_2^2}.
\end{align*}
This completes the proof.
\end{proof}

The following lemma follows directly from the standard Gaussian tail bound. A similar result is given as Fact B.1 in \cite{zhong2017recovery}.
\begin{lemma}(\cite{zhong2017recovery})\label{lemma:Gaussiantail}
    Let $\wb\in \RR^k$ be a fixed vector. For any $t\geq 0$, we have
    \begin{align*}
        \PP_{\xb\sim N(\mathbf{0},\Ib_k)} \big(|\wb^\top \xb | \leq \|\wb\|_2\cdot t\big) \geq 1 - 2\exp(-t^2/2).
    \end{align*}
\end{lemma}

\iffalse
\begin{lemma}[\cite{gordon1985some}] Let $X_{ij}$ and $Y_{ij}$, $i=1,\ldots,m$, $j=1,\ldots,n$ be $m\times n$ jointly Gaussian random variables with equal means. Assume that
\begin{align*}
    &\Cov(X_{ij},X_{il}) \leq \Cov(Y_{ij},Y_{il}),\\
    &\Cov(X_{ij},X_{kl}) \geq \Cov(Y_{ij},Y_{kl}), \text{ if } i\neq k,\\
    &\Var(X_{ij}) = \Var(Y_{ij}).
\end{align*}
Then for any $\tau_{ij}$, $i=1,\ldots,m$, $j=1,\ldots,n$, we have
\begin{align*}
    \PP\Bigg( \bigcap_{i=1}^m \bigcup_{j=1}^n \{X_{ij} \leq \tau_{ij}\} \Bigg) \leq \PP\Bigg( \bigcap_{i=1}^m \bigcup_{j=1}^n \{Y_{ij} \leq \tau_{ij}\} \Bigg)
\end{align*}
\end{lemma}
\fi

\subsection{Proof of Lemma~\ref{lemma:hoeffdingidentity}}
\begin{proof}[Proof of Lemma~\ref{lemma:hoeffdingidentity}]
Let $(\tilde{X_1},\tilde{X_2})$ be an independent copy of $(X_1,X_2)$. Then by definition we have
\begin{align*}
    &\Cov[f(X_1),g(X_2)] = \EE \{ [f(X_1) - f(\tilde{X}_1)]\cdot [g(X_2) - g(\tilde{X}_2)]\},\\
    &\Cov[[\ind(X_1 \leq x_1),\ind(X_2 \leq x_2)] = \EE \{ [\ind(X_1 \leq x_1)  - \ind(\tilde{X}_1 \leq x_1)]\cdot [\ind(X_2 \leq x_2)  - \ind(\tilde{X}_2 \leq x_2)]  \}.
\end{align*}
For $f(X_1) - f(\tilde{X}_1)$, by the definition of Lebesgue-Stieltjes integration,
\begin{align*}
    f(X_1) - f(\tilde{X}_1) &= \int_\RR \{ \ind[x_1\leq f(X_1)] - \ind[x_1\leq f(\tilde{X}_1)] \} \mathrm{d} x_1\\
    &= \int_\RR [ \ind(x_1\leq X_1) - \ind(x_1\leq \tilde{X}_1)] \mathrm{d} f(x_1).
\end{align*}
Similarly, we have
\begin{align*}
    g(X_2) - g(\tilde{X}_2) = \int_\RR [ \ind(x_2\leq X_2) - \ind(x_2\leq \tilde{X}_2)] \mathrm{d} g(x_2).
\end{align*}
Therefore by Fubini's Theorem we have
\begin{align*}
    \Cov[f(X_1),g(X_2)] = \int_{\RR^2} \Cov[\ind(X_1 \leq x_1),\ind(X_2 \leq x_2)] \mathrm{d}f(x_1) \mathrm{d}g(x_2).
\end{align*}
\end{proof}

\begin{proof}[Proof fo Lemma~\ref{lemma:recursivebound1}]
For $\{u_t\}_{t\geq 0}$ We have
\begin{align*}
    u_{t} &\leq au_{t-1} + c_1 b^{t-1} + c_2\\
    &\leq a (au_{t-2} + c_1 b^{t-2} + c_2) + c_1 b^{t-1} + c_2\\
    &= a^2 u_{t-2} + c_1 (a b^{t-2} + b^{t-1}) + c_2 (1+a)\\
    &\leq \cdots\\
    &\leq a^t u_0 + c_1(a^{t-1} + a^{t-2}b + \cdots + a b^{t-2} + b^{t-1}) + c_2 \frac{1}{1 - a}\\
    &\leq a^t u_0 + c_1 t (a\lor b)^{t-1} + c_2\frac{1}{1-a}.
\end{align*}
This gives the first bound. Similarly, $\{u_t\}_{t\geq 0}$ for We have
\begin{align*}
    v_{t} &\leq av_{t-1} + c_1(t-1)^2 b^{t-1} + c_2\\
    &\leq a (av_{t-2} + c_1(t-2)^2 b^{t-2} + c_2) + c_1(t-1)^2 b^{t-1} + c_2\\
    &= a^2 v_{t-2} + c_1 [(t-2)^2a b^{t-2} + (t-1)^2b^{t-1}] + c_2 (1+a)\\
    &\leq \cdots\\
    &\leq a^t v_0 + c_1[0^2\cdot a^{t-1} + 1^2\cdot a^{t-2}b + \cdots + (t-2)^2\cdot a b^{t-2} +(t-1)^2\cdot b^{t-1}] + c_2 \frac{1}{1 - a}\\
    &\leq a^t v_0 + c_1 \frac{t(t-1)(2t-1)}{6} (a\lor b)^{t-1} + c_2\frac{1}{1-a}\\
    &\leq a^t v_0 +  \frac{c_1}{3}t^3 (a\lor b)^{t-1} + c_2\frac{1}{1-a}.
\end{align*}
This completes the proof.
\end{proof}

\section{Additional Experiments}\label{appendix:additional_experiments}
In this section we present some additional experimental results on non-Gaussian inputs. Here we consider two types of input distributions: uniform distribution over unit sphere and a transelliptical distribution (the distribution of a Gaussian random vector after an entry-wise monotonic transform $y = x^3$). The experiments are conducted in the setting $k=15$, $r = 5$ for ReLU and hyperbolic tangent activation functions, where $\wb^*$ and $\vb^*$ are generated in the same way as described in Section~\ref{sec:experiments}. Specifically, Figures \ref{subfig:1}, \ref{subfig:2} show the results for uniform distribution over unit sphere, while Figures \ref{subfig:3}, \ref{subfig:4} are for the transelliptical distribution. Moreover, Figures \ref{subfig:1}, \ref{subfig:3} are for ReLU networks, and the results for hyperbolic tangent networks are given in Figures \ref{subfig:2}, \ref{subfig:4}. From these figures, we can see that although it is not directly covered in our theoretical results, the approximate gradient descent algorithm proposed in our paper is still capable of handling non-Gaussian distributions. In specific, from Figures \ref{subfig:1}, \ref{subfig:3}, we can see that our proposed algorithm is competitive with Double Convotron for symmetric distributions and ReLU activation, which is the specific setting Double Convotron is designed for. Moreover, Figures \ref{subfig:2}, \ref{subfig:4} clearly show that for hyperbolic tangent activation function, Double Convotron fails to converge, while our approximated gradient descent still converges linearly.
\begin{figure}[h]
	\begin{center}
		\begin{tabular}{cc}
 		\hspace{-0.2in}
			\subfigure[ReLU+Unif. Sphere]{\includegraphics[width=0.4\linewidth,angle=0]{errorplot_ReLU_k15r5_log_uniformsphere.pdf}\label{subfig:1}}
			&
			\subfigure[tanh+Unif. Sphere]{\includegraphics[width=0.4\linewidth,angle=0]{errorplot_tanh_k15r5_log_uniformsphere.pdf}\label{subfig:2}}
			\\
			\subfigure[ReLU+Transelliptical]{\includegraphics[width=0.4\linewidth,angle=0]{errorplot_ReLU_k15r5_log_gaussiancopula.pdf}\label{subfig:3}}
			&
			\subfigure[tanh+Transelliptical]{\includegraphics[width=0.4\linewidth,angle=0]{errorplot_tanh_k15r5_log_gaussiancopula.pdf}\label{subfig:4}}
		    \end{tabular}
	\end{center}
	\vskip -12pt
	\caption{Experimental results for different non-Gaussian input distributions. (a) and (b) are for uniform distribution over unit sphere, while (c) and (d) give the results for  transelliptical distribiton.}
	\label{fig:boundevaluation}
\end{figure}
\section{Related Work}\label{section:relatedwork}
There has been a vast body of literature on the theory of deep learning. We will review in this section the most relevant work to ours.

It is well known that neural networks have remarkable expressive power due to the universal approximation theorem \cite{hornik1991approximation}. However, even learning a one-hidden-layer neural network with a sign activation can be NP-hard \citep{blum1989training} in the realizable case. In order to explain the success of deep learning in various applications, additional assumptions on the data generating distribution have been explored such as symmetric distributions \citep{baum1990polynomial} and log-concave distributions \citep{klivans2009baum}. More recently, a line of research has focused on Gaussian distributed input for one-hidden-layer or two-layer networks with different structures \citep{janzamin2015beating,tian2016symmetry,brutzkus2017globally,li2017convergence,zhong2017recovery,zhong2017learning,ge2017learning,zhang2018learning,fu2018local}. Compared with these results, our work aims at providing tighter sample complexity for more general activation functions.

A recent line of work \citep{mei2016landscape,shamir2016distribution,mei2018mean,li2018learning,du2018gradient, allen2018convergence,du2018gradientdeep,zou2018stochastic,allen2018generalization,arora2019fine,cao2019generalization,arora2019exact,cao2019generalizationsgd,zou2019improved} studies the training of neural networks in the over-parameterized regime. \citet{mei2016landscape,shamir2016distribution} studied the optimization landscape of over-parameterized neural networks. \citet{li2018learning,du2018gradient, allen2018convergence,du2018gradientdeep,zou2018stochastic,zou2019improved} proved that gradient descent can find the global minima of over-parameterized neural networks. Generalization bounds under the same setting are studied in \citet{allen2018generalization,arora2019fine,cao2019generalization,cao2019generalizationsgd}. Compared with these results in the over-parameterized setting, the parameter recovery problem studied in this paper is in the classical setting, and therefore different approaches need to be taken for the theoretical analysis.

This paper studies convolutional neural networks (CNNs). There are not much theoretical literature specifically for CNNs. The expressive power of CNNs is shown in \citet{cohen2016convolutional}. \citet{nguyen2017bloss} study the loss landscape in CNNs and \citet{brutzkus2017globally} show the global convergence of gradient descent on one-hidden-layer CNNs. \citet{du2017convolutional} extend the result to non-Gaussian input distributions with ReLU activation. \citet{zhang2016convexified} relax the class of CNN filters to a reproducing kernel Hilbert space and prove the generalization error bound for the relaxation. \citet{gunasekar2018implicit} show that there is an implicit bias in gradient descent on training linear CNNs.

redpajama_set_name: RedPajamaArXiv