# On the Provable Generalization of Recurrent Neural Networks

Lifu Wang, Bo Shen, Bo Hu, Xing Cao
Beijing Jiaotong University
{Lifu_Wang, bshen<EMAIL_ADDRESS>
###### Abstract

Recurrent Neural Network (RNN) is a fundamental structure in deep learning.
Recently, some works study the training process of over-parameterized neural
networks, and show that over-parameterized networks can learn functions in
some notable concept classes with a provable generalization error bound. In
this paper, we analyze the training and generalization for RNNs with random
initialization, and provide the following improvements over recent works:

  1. (1)

For a RNN with input sequence $x=(X_{1},X_{2},...,X_{L})$, previous works
study to learn functions that are summation of $f(\beta^{T}_{l}X_{l})$ and
require normalized conditions that $||X_{l}||\leq\epsilon$ with some very
small $\epsilon$ depending on the complexity of $f$. In this paper, using
detailed analysis about the neural tangent kernel matrix, we prove a
generalization error bound to learn such functions without normalized
conditions and show that some notable concept classes are learnable with the
numbers of iterations and samples scaling almost-polynomially in the input
length $L$.

  2. (2)

Moreover, we prove a novel result to learn N-variables functions of input
sequence with the form $f(\beta^{T}[X_{l_{1}},...,X_{l_{N}}])$, which do not
belong to the “additive” concept class, i,e., the summation of function
$f(X_{l})$. And we show that when either $N$ or
$l_{0}=\max(l_{1},..,l_{N})-\min(l_{1},..,l_{N})$ is small,
$f(\beta^{T}[X_{l_{1}},...,X_{l_{N}}])$ will be learnable with the number
iterations and samples scaling almost-polynomially in the input length $L$.

##  1 Introduction

In Deep Learning, the recurrent neural network (RNN) is well-known as one of
the most popular models to model sequential data and is widely used in
practice for tasks in natural language processing (NLP). One of the characters
of RNN is that it performs the same operation for all the input of the
sequence.

Consider a input sequence $x=(X_{1},X_{2},...,X_{L})$. A RNN with the form

$h_{l}(x)=\phi(\bm{W}h_{l-1}+\bm{A}X_{l}),$ (1)

is trying to learn functions $f_{l}(X_{1},X_{2},...X_{l})$ as

$\displaystyle h_{1}(x)=f_{1}(X_{1})$ (2) $\displaystyle
h_{2}(x)=f_{2}(X_{1},X_{2})$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots$
$\displaystyle h_{L}(x)=f_{L}(X_{1},X_{2},...X_{L})$

Due to the complex nonlinearity, the loss is generally non-convex, and it is
very difficult to give a theoretical guarantee. Recently, there are some works
[Allen-Zhu et al., 2019b, Cao and Gu, 2019, Allen-Zhu et al., 2019a, Du et
al., 2019, Arora et al., 2019, Allen-Zhu et al., 2019c] trying to give a
theoretical explanation that why gradient descent can allow an
overparametrized network to attain arbitrarily low training error and ample
generalization ability. These papers show that, under some assumptions, we
have:

  * $\bullet$

_Multi-layer feed-forward networks[Allen-Zhu et al., 2019b, Du et al., 2019]
and recurrent neural networks [Allen-Zhu et al., 2019c] with large hidden size
can attain zero training error, regardless of whether the data is properly
labeled or randomly labeled._

  * $\bullet$

_For multi-layer feed-forward networks, functions with the form
$F^{*}(x)=\sum_{r=1}^{C}\phi_{r}(\beta^{T}_{r}X),X\in\mathbb{R}^{d},\beta_{r}\in\mathbb{R}^{d},||\beta_{r}||=1$
are learnable i.e. fitting the training data with a provably small
generalization error, if $\phi$ is analytic and the “complexity” is low enough
[Allen-Zhu et al., 2019a, Arora et al., 2019, Cao and Gu, 2019]._

  * $\bullet$

_The “complexity” of function $\phi$ can be measured by a matrix derived from
the NTK (Neural Tangent Kernel) of the network [Arora et al., 2019, Cao and
Gu, 2019]._

  * $\bullet$

_For recurrent neural networks[Allen-Zhu and Li, 2019a], if the input sequence
is normalized, i.e., $x=(X_{1},X_{2},...,X_{L})$, $||X_{1}||=1$,
$||X_{l}||=\epsilon$ with $\epsilon$ very small, functions with the form
$F^{*}(x)=\sum_{l=1}^{L}\sum_{r=1}^{C_{l}}\phi_{l,r}(\beta^{T}_{l,r}X_{l})$
are learnable, where $m$ is the size of matrix $\bm{W}$, and
$\mathscr{C}=\sum_{i=0}^{\infty}a_{i}R^{i}$ is a series representing the
complexity of learnable functions._

These works show the provable learning ability of deep learning. But there are
still some important issues that were not addressed.

  * $\bullet$

Firstly, for RNNs, the method in [Allen-Zhu and Li, 2019a] requires a
normalized condition for $\bm{A}$ and $X_{l}$ in (1) that
$||\bm{A}X_{l}||\leq\epsilon_{x}$ for all $l\leq L$ and shows that for a
function $F^{*}(x)$ with the complexity $\mathscr{C}$, it is learnable with
error $O(\epsilon^{1/3}_{x}\mathscr{C})$. Thus $||X_{l}||$ (or equally,
$||\bm{A}||$) should be very small and the scale is dependent on the
complexity of functions. The dependence of $||\bm{A}X_{l}||$ on $\mathscr{C}$
makes the results unrealistic in practice since generally the norm of input
will not be so small.

  * $\bullet$

Secondly, the result in [Allen-Zhu and Li, 2019a] shows that RNNs can learn
functions which are the summation of functions like
$\psi(\beta^{T}_{l}X_{l})$. But this is only a linear combination of the
functions of the input at different positions and does not consider the
nonlinear interaction of the inputs. One may ask, since $h_{L}(x)$ is a
function of $\\{X_{1},X_{2},...X_{L}\\}$, is it possible to go beyond and
learn more complex functions?

In order to study these problems, we consider the binary classification
problem: for every input $x_{i}$, the label ($+1$ or $-1$) of $x_{i}$ can be
expressed by the sign of a target function $F^{*}(x_{i})$. We consider Elman
recurrent neural networks with ReLU activation

$\displaystyle h_{l}(x)=\phi(\bm{W}h_{l-1}+\bm{A}X_{l})$ (3) $\displaystyle
f(\bm{W},x)=\bm{B}^{T}h_{L}(x)\in\mathbb{R}.$ $\displaystyle
x=(X_{1},X_{2},...,X_{L}),X_{l}\in\mathbb{R}^{d},\bm{W}\in\mathbb{R}^{m\times
m},$ $\displaystyle\bm{A}\in\mathbb{R}^{m\times
d},\bm{B}\in\mathbb{R}^{m},\phi(x)=\max(x,0)$

to learn two types of target functions:

  * $\bullet$

Additive Concept Class:

$\displaystyle
F^{*}(x)=\sum_{l=1}^{L}\sum_{r=1}\psi_{l,r}(\beta^{T}_{l,r}X_{l}/||X_{l}||),$
(4) $\displaystyle\psi_{l,r}(x)=\sum_{i=0}^{\infty}c_{i}x^{i},$

  * $\bullet$

N-variables Concept Class:

$\displaystyle
F^{*}(x)=\sum_{r}\psi_{r}(\langle\beta_{r},[X_{l_{1}},...,X_{l_{N}}]\rangle),$
(5) $\displaystyle\psi_{r}(x)=\sum_{i=0}^{\infty}c_{i}x^{i}.$

For these two types of function, we study the following questions:

  * $\bullet$

Can RNN learn additive concept class functions (4) without the normalized
condition with reasonable complexity on the sequence size $L$?

  * $\bullet$

Can RNN learn functions in N-variables Concept Class (5) which can not be
written as the summation of $f(X_{l})$ with reasonable complexity on $N$ and
$L$?

Our Result.  We answer the two questions and give a provable generalization
error bound. Our results are stated as follows:

###### Theorem 1

(Informal) For a function $F^{*}(X_{1},X_{2},...,X_{L})$ with the form as in
(4) or (5), there is a power series named the complexity $\mathscr{C}(F^{*})$
dependent on the Taylor expansion coefficient in (4) and (5). For (4),
$\mathscr{C}(F^{*})$ is almost-polynomial in $L$. For (5), when $N$ or
$l_{0}=\max(l_{1},..,l_{N})-\min(l_{1},..,l_{N})$ is small,
$\mathscr{C}(F^{*})$ is almost-polynomial in $L$. Under this definition of
complexity $\mathscr{C}(F^{*})$, $F^{*}$ is learnable using RNN with $m$
hidden nodes and ReLU activation in (3) in
$\mathcal{O}(\mathscr{C}(F^{*})^{2})$ steps with
$\mathcal{O}(\mathscr{C}(F^{*})^{2})$ samples if $m\geq
poly(L,\mathscr{C}(F^{*}))$.

Contribution. We summarize the contributions as follows:

  * $\bullet$

_In this paper, we prove that RNN without normalized condition can efficiently
learn some notable concept classes with both time and sample complexity
scaling almost polynomially in the input length $L$._

  * $\bullet$

_Our results go beyond the “additive” concept class. We prove a novel result
that RNN can learn more complex function of the input such as N-variables
concept class functions. And “long range correlation functions” with small $N$
(e.g. $N=2$, $f(\beta^{T}[X_{l},X_{l+l_{0}}])$ ) are learnable with complexity
scaling almost polynomially in the input length $L$ and correlation distance
$l_{0}$._

  * $\bullet$

_Technically, we study the “backward correlation” of RNN network. In RNN case,
using a crucial observation on the degeneracy of deep network, we show that
the “backward correlation”
$\frac{1}{m}\langle\text{Back}_{l}(x_{i}),\text{Back}_{l}(x_{j})\rangle$ will
decay polynomially rather than exponentially in input length $L$. This shows
the complexity of learning RNN with ReLU activation function is polynomial in
the size of input sequence $L$._

Notions. For two matrices $\bm{A},\bm{B}\in\mathbb{R}^{m\times n}$, we define
$\langle\bm{A},\bm{B}\rangle=\text{Tr}(A^{T}B)$. We define the asymptotic
notations $\mathcal{O}(\cdot),\Omega(\cdot),poly(\cdot)$ as follows.
$a_{n},b_{n}$ are two sequences. $a_{n}=\mathcal{O}(b_{n})$ if
$\lim\sup_{n\to\infty}|a_{n}/b_{n}|<\infty$, $a_{n}=\Omega(b_{n})$ if
$\lim\inf_{n\to\infty}|a_{n}/b_{n}|>0$, $a_{n}=poly(b_{n})$ if there is
$k\in\mathbb{N}$ that $a_{n}=O((b_{n})^{k})$.
$\widetilde{\mathcal{O}}(\cdot),\widetilde{\Omega}(\cdot),\widetilde{poly}(\cdot)$
are notions which hide the logarithmic factors in
$\mathcal{O}(\cdot),\Omega(\cdot),poly(\cdot)$. $||\cdot||$ and
$||\cdot||_{2}$ denote the 2-norm of matrices. $||\cdot||_{1}$ denote the
1-norm. $||\cdot||_{F}$ is the Frobenius-norm. $||\cdot||_{0}$ is the number
of non-zero entries.

For elements $A_{i.j},B_{i,j}$ of symmetric matrix $\bm{A},\bm{B}$. We abuse
the notion $A_{i.j}\succeq B_{i.j}$ to denote $\bm{A}\succeq\bm{B}$, i.e.
$\bm{A}-\bm{B}$ is a positive semidefinite matrix.

##  2 Preliminaries

###  2.1 Function Complexity

For a analytic function $\psi(z)$, we can write it as
$\psi(z)=c_{0}+\sum_{i=1}^{\infty}c_{i}z^{i}$. We define the following notion
to measure the complexity to learn such functions.

$\mathscr{C}(\psi,R)=1+\sum_{i=1}^{\infty}i\cdot|c_{i}|R^{i}.$ (6)
$\mathscr{C}_{N}(\psi,R)=1+\sum_{i=1}^{\infty}L^{1.5N}C_{1}^{N}\cdot\sqrt{C_{N,i}}\cdot(i/N)^{N}\cdot|c_{i}|R^{i}$
(7)

where $C_{1}>100$ is an large absolute constant and $C_{N,i}$ is the largest
combination number $\frac{i!}{n_{1}!n_{2}!...n_{N}!}$ for
$n_{1},n_{2}...n_{N}>0,n_{1}+n_{2}+...n_{N}=i$,

###### Example 2.1

[Arora et al., 2019] Consider $\psi(z)=arctan(z/2)$. Then

$\psi(z)=\sum_{i=1}\frac{(-1)^{i-1}2^{1-2i}}{2i-1}z^{2i-1}$ (8)

In this case,

$\mathscr{C}(\psi,1)=1+\sum_{i=1}^{\infty}i\cdot|c_{i}|\leq
1+\sum_{i=1}^{\infty}2^{1-2i}\leq\mathcal{O}(1).$

###### Example 2.2

In the case $N=2$, $C_{2,i}=i$, $(i/2)^{2}\leq i^{2}$. $\psi(z)=exp(z)$

$\mathscr{C}_{2}(\psi,1)\leq 1+\sum_{i=1}^{\infty}L^{3}C_{1}^{2}\pi
i^{2.5}/i!\leq\mathcal{O}(1)$

###  2.2 Concept Class

For the input sequence $\\{X_{l}\\}$, we assume $C_{min}\leq||X_{l}||\leq
C_{max}$, for all $1\leq l\leq L$ and $C_{max}/C_{min}\sim C_{0}$. Under this
condition, we consider two types of target functions with the following form:
Additive Concept Class.

$F^{*}(x)=\sum_{l=1}^{L}\sum_{r=1}^{C_{l}}\psi_{l,r}(\beta^{T}_{l,r}X_{l}/||X_{l}||).$
(9)

Here for all $l,r$, $\psi_{l,r}$ is analytic and $||\beta_{l,r}||_{2}\leq 1$.

We define

$\mathscr{C}(F^{*})=L^{3.5}\sum_{l=1}^{L}\sum_{r=1}^{C_{l}}\mathscr{C}(\psi_{l,r},C_{0}\sqrt{L}),$
(10)

to be the complexity of the target function.

###### Remark 2.1

If we consider function $\psi(\beta^{T}X_{l})$ and $||X_{l}||=1$ for all $l$,
the above complexity will become $\mathscr{C}(\psi,\mathcal{O}(\sqrt{L}))$.
This is similar with that in [Allen-Zhu and Li, 2019a] but this complexity
requirement is much weaker than that in [Allen-Zhu and Li, 2019a]. For
example, the complexity of $arctan(z/2)$ in [Allen-Zhu and Li, 2019a] is not
finite, as shown in [Arora et al., 2019].

N-variables Concept Class.

$F^{*}(x)=\sum_{r}\psi_{r}(\langle\beta_{r},[X_{l_{1}},...,X_{l_{N}}]\rangle/\sqrt{N}\max||X_{l_{n}}||).$
(11)

For all $r$, $\psi_{l,a,r}(x,y)$ is an analytic function
$\psi_{r}(x)=c_{0}+\sum_{i=1}^{\infty}c_{i}x^{i}$.
$\beta_{r}\in\mathbb{R}^{dN}$, $||\beta_{r}||_{2}\leq 1$. Let
$l_{0}=\max(l_{1},..,l_{N})-\min(l_{1},..,l_{N})$. We define

$\mathscr{C}(F^{*})=\min(L^{2}\mathscr{C}_{N}(\psi_{r},C_{0}\sqrt{L}),L^{3.5}\mathscr{C}(\psi_{r},2^{l_{0}}C_{0}\sqrt{L})).$
(12)

###### Remark 2.2

The complexity $\sum_{r}\mathscr{C}_{N}(\psi_{r},C_{0}\sqrt{L})$ and
$\sum_{r}\mathscr{C}(\psi_{r},2^{l_{0}}C_{0}\sqrt{L})$ are exponential in $N$
and $l_{0}$ respectively. And $\mathscr{C}(F^{*})$ is less or equal than both.
Thus if either $l_{0}$ or $N$ is small, $\mathscr{C}(F^{*})$ will be
polynomial in $L$. Especially when $N$ is small(e.g. N=2), even if
$l_{0}=L-1$, functions with the form $f(\beta^{T}[X_{l},X_{l+l_{0}}])$ are
still learnable with a low complexity.

###  2.3 Results on Positive Definite Matrices and Functions

We say a function
$\phi(\cdot,\cdot):\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ is
positive definite if for all $n\in\mathbb{N}$, any
$\\{x_{1},...,x_{n}\\}\subseteq\mathbb{R}^{d},\\{c_{1},...,c_{n}\\}\subseteq\mathbb{R}$,

$\sum_{i,j}c_{i}c_{j}\phi(x_{i},x_{j})\geq 0.$ (13)

The following basic properties in chapter 3 of [BergJens et al., 1984] are
very useful in our proof.

###### Proposition 2.1

If $\phi(\cdot,\cdot)$ is positive definite function, let matrix
$\bm{M}\in\mathbb{R}^{n\times n}$,
$\\{x_{1},...,x_{n}\\}\subseteq\mathbb{R}^{d}$, and
$M_{i,j}=\phi(x_{i},x_{j})$. Then $\bm{M}$ is a semi-positive definite matrix.

###### Proposition 2.2

If $\phi_{1}(\cdot,\cdot)$ and $\phi_{1}(\cdot,\cdot)$ are positive definite,
$\phi(x_{i},x_{j})=\phi_{1}(x_{i},x_{j})\cdot\phi_{2}(x_{i},x_{j})$ is also a
positive definite function.

###### Proposition 2.3

Let $\phi(\cdot,\cdot)$ be a positive definite function, and
$\psi(x)=\sum_{i=0}^{\infty}c_{i}x^{i}$, $c_{i}\geq 0$. Then
$\psi(\phi(\cdot,\cdot))$ is also a positive definite function.

For a positive definite matrix $\bm{M}\in\mathbb{R}^{n\times n}$, there is a
result in [Arora et al., 2019],

###### Proposition 2.4

(Section E of [Arora et al., 2019].) Let
$\bm{X}=(x_{1},...x_{n})\in\mathbb{R}^{d\times n}$ and
$\bm{K}_{p}\in\mathbb{R}^{n\times n}$ is a matrix with
$(K_{p})_{i,j}=(x_{i}^{T}x_{j})^{p}$. Suppose there is $\alpha>0$, such that
$\bm{M}\succeq\alpha^{2}\bm{K}_{p}$. Let
$y=((\beta^{T}x_{1})^{p},...,(\beta^{T}x_{n})^{p})\in\mathbb{R}^{n}$. We have
$\sqrt{y^{T}(\bm{M})^{-1}y}\leq||\beta||_{2}^{p}/\alpha$.

##  3 Main Results

Assume there is an unknown data set ${\cal D}=\\{x,y\\}$. The inputs have the
form $x=(X_{1},X_{2},...X_{L})\in(\mathbb{R}^{d})^{L}$.
$||X_{l}||\leq\mathcal{O}(1)$ for all $1\leq l\leq L$. For every input
$x_{i}$, there is a label $y_{i}=\pm 1$.

The neural network with input $x$ is

$\displaystyle h_{0}(x)=\phi(\bm{M}_{0}),$ (14) $\displaystyle
h_{l}(x)=\phi(\bm{W}h_{l-1}+\bm{A}X_{l}),$ $\displaystyle
f(\bm{W},x)=\bm{B}^{T}h_{L}(x).$

Here $\bm{W}\in\mathbb{R}^{m\times m},\bm{A}\in\mathbb{R}^{m\times
d},\bm{B},\bm{M}_{0}\in\mathbb{R}^{m}$. The entries of $\bm{M}_{0}$, $\bm{W}$
and $\bm{A}$ are respectively i.i.d. generated from $N(0,\frac{2}{m})$,
$N(0,\frac{2}{m})$ and $N(0,\frac{2}{L^{3}\cdot m})$. The entries of $\bm{B}$
are i.i.d. generated from $N(0,\frac{1}{m})$.

The goal of learning RNN is to minimize the population loss:

$L_{{\cal D}}(\bm{W})=\mathbb{E}_{(x,y)\sim{\cal D}}\ell(y\cdot f(\bm{W},x)),$
(15)

by optimizing the empirical loss

$L_{S}(\bm{W})=\frac{1}{n}\sum_{i=1}^{n}\ell(y_{i}\cdot f(\bm{W},x_{i})),$
(16)

using SGD. Here $\ell(x)=\log(1+exp(-x))$ is the cross-entropy loss. Consider
the SGD algorithm on this RNN.

Input: Data set ${\cal D}$, learning rate $\eta$.

The entries of $\bm{W}^{0},\bm{A}$ are i.i.d. generated from
$N(0,\frac{2}{m})$. The entries of $\bm{B}$ are i.i.d. generated from
$N(0,\frac{1}{m})$.

for  _$t=1,2,3...n$_ do

Randomly sample $(x_{t},y_{t})$ from the data set ${\cal D}$.

$\bm{W}^{t}=\bm{W}^{t-1}-\eta\nabla_{\bm{W}^{t-1}}\ell(y_{t}\cdot
f(\bm{W}^{t-1},x_{t}))$.

end for

Algorithm 1 Training RNN with SGD

Let the complexity $\mathscr{C}^{*}$ of $F^{*}(\cdot)$ be defined in (10) and
(12). The 0-1 error for ${\cal D}$ is $L^{0-1}_{{\cal
D}}(\bm{W})=\mathbb{E}_{(x,y)\sim{\cal D}}\mathbbm{1}\\{y\cdot
f(\bm{W},x)<0\\}$. We have:

###### Theorem 2

Assume there is $\delta\in(0,e^{-1}]$. Supposing for ${\cal
D}=\\{x_{i},y_{i}\\}$, there is a function $F^{*}$ belonging to the concept
class (9) or (11) such that $y_{i}\cdot F^{*}(x_{i})\geq 1$ for all $i$. Let
$\bm{W}^{k}$ be the output of Algorithm 1. There is a parameter
$m^{*}(n,\delta,L,\mathscr{C}^{*})=poly(n,\delta^{-1},L,\mathscr{C}^{*})$ such
that, with probability at least $1-\delta$, if $m>m^{*}(n,\delta,L)$, there
exits parameter $\eta=\mathcal{O}(1/m)$ that satisfies

$\frac{1}{n}\sum_{k=1}^{n}L^{0-1}_{{\cal
D}}(\bm{W}^{k})\leq\widetilde{\mathcal{O}}[\frac{(\mathscr{C}^{*})^{2}}{n}]+\mathcal{O}(\frac{\log(1/\delta)}{n}).$
(17)

###### Remark 3.1

This theorem induces that, to achieve population $0-1$ error(rather than
empirical loss) being less than $\epsilon$, it is enough to train the network
using Algorithm 1 with
$\widetilde{\Omega}((L\cdot\mathscr{C}^{*})^{2}/\epsilon)$ steps. As defined
in section 2.1 and 2.2, when $N$ is small, for the two types of concept class,
$(\mathscr{C}^{*})^{2}$ is almost-polynomial in input length $L$. Thus they
can be learned effectively.

###### Remark 3.2

This theorem can also be generalized to “sequence labeling” loss such as
$\frac{1}{n}\sum_{i=1}^{n}\sum_{l=1}^{L}\ell(y_{i}\cdot f_{l}(\bm{W},x_{i}))$
with $f_{l}(\bm{W},x)=\bm{B}^{T}h_{l}(x)$. This is because the matrix

$H^{l}_{i,j}=\frac{1}{m}\langle\nabla f_{l}(\bm{W},x_{i}),\nabla
f_{l}(\bm{W},x_{j})\rangle$

with different $l$ are almost “orthogonal” by a similar argument to (26) in
Theorem 6. Then RNN can learn a function $f_{l}=sign(F^{*}_{l}(x))$ with
$F^{*}_{l}(x)$ belonging to functions in section 2.2. See Remark G.1 in the
supplementary materials.

##  4 Sketch Proof of the Main Theorem

The first step to prove the main theorem 2 is the following generalization of
Corollary 3.10 in [Cao and Gu, 2019].

###### Theorem 3

Under the condition of Theorem 2, let $n$ samples in the training set be
$\\{x_{i},y_{i}\\}_{i=1}^{n}$.
$\widetilde{y}=[F^{*}(x_{1}),F^{*}(x_{2}),...F^{*}(x_{n})]^{T}$. Let $\bm{H}$
be a matrix with
$H_{i,j}=\frac{1}{m}\langle\nabla_{\widetilde{W}}f(\widetilde{\bm{W}},x_{i}),\nabla_{\widetilde{W}}f(\widetilde{\bm{W}},x_{j})\rangle$.
The entries of $\widetilde{\bm{W}}$ are i.i.d. generated from
$N(0,\frac{2}{m})$. If there is a matrix
$\bm{H}^{\infty}\in\mathbb{R}^{n\times n}$ satisfying

$\bm{H}+\bm{\epsilon}^{T}\bm{\epsilon}\succeq\bm{H}^{\infty}\text{ with
}||\bm{\epsilon}||_{F}\leq 0.01/\mathcal{O}(\mathscr{C}^{*}),$ (18)

and
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(\mathscr{C}^{*})$,
there exits
$m^{*}(n,\delta^{-1},L,\mathscr{C}^{*})=poly(n,\delta^{-1},L,\mathscr{C}^{*})$
such that, with probability at least $1-\delta$, if $m>m^{*}$,

$\frac{1}{n}\sum_{k=1}^{n}L^{0-1}_{{\cal
D}}(\bm{W}^{k})\leq\widetilde{\mathcal{O}}[\frac{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}{n}]+\mathcal{O}(\frac{\log(1/\delta)}{n}).$
(19)

###### Remark 4.1

In order to show Theorem 2 using this theorem, we need to carefully pick out
the exponential parts of $L$. Using the methods in [Allen-Zhu et al., 2019c]
and [Cao and Gu, 2019], we can show that
$m^{*}(L,n,\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}})\geq
poly(n,L,\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}})$ is
enough. $\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}$ is dealt
with by calculating the forward and backward correlation in section 4.1.1 and
4.1.2.

The proof of theorem 3 is in fact a combination of the results in [Cao and Gu,
2019] and [Allen-Zhu et al., 2019c]. The really matter thing is how large can
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\ $ be. We can
show that:

###### Theorem 4

Under the condition of Theorem 3, with probability at least $1-\delta$, there
exits matrix $\bm{H}^{\infty}$ satisfying (18) and

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(\mathscr{C}^{*}).$
(20)

Theorem 2 is a direct corollary of the above two theorems.

###  4.1 Calculation on Kernel Matrix

The proof of (20) relies on a direct calculation to construct a kernel matrix
$\bm{H}^{\infty}$. We consider two input $x_{i}$ and $x_{j}$. Let $X_{i,l}$
and $X_{j,l}$ be the $l-th$ input of $x_{i}$ and $x_{j}$. Let
$D_{l}\in\mathbb{R}^{m\times m}$ and $D_{l}^{\prime}\in\mathbb{R}^{m\times m}$
be diagonal matrices that,

$\displaystyle(D_{l})_{k,k}=\mathbbm{1}\\{\bm{W}h_{l-1}(x_{i})+\bm{A}X_{i,l}>0\\}$
(21)
$\displaystyle(D^{\prime}_{l})_{k,k}=\mathbbm{1}\\{\bm{W}h_{l-1}(x_{j})+\bm{A}X_{j,l}>0\\}$

$\displaystyle\text{Back}_{l}=BD_{L}W\cdots
D_{l+1}W,\text{Back}^{\prime}_{l}=BD^{\prime}_{L}W\cdots D^{\prime}_{l+1}W$
(22)

Then

$\frac{1}{m}\langle\nabla_{\widetilde{W}}f(\widetilde{\bm{W}},x_{i}),\nabla_{\widetilde{W}}f(\widetilde{\bm{W}},x_{j})\rangle=\frac{1}{m}\sum_{l,l^{\prime}}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l^{\prime}}(x_{j})\cdot
D_{l^{\prime}}^{\prime}\rangle\cdot\langle
h_{l}(x_{i}),h_{l^{\prime}}(x_{j})\rangle$ (23)

Generally
$H_{i,j}=\frac{1}{m}\langle\nabla_{\widetilde{W}}f(\widetilde{\bm{W}},x_{i}),\nabla_{\widetilde{W}}f(\widetilde{\bm{W}},x_{j})\rangle$
is hard to deal with. However, in the $m\to\infty$ limit, we can use some
techniques to do the calculation.

####  4.1.1 Forward Correlation

###### Theorem 5

For fixed $i,j$, under the condition in Theorem 3, with probability at least
$1-exp(-\Omega(\log^{2}m))$,

$|\langle
h_{l}(x_{i}),h_{l}(x_{j})\rangle-K^{l}_{i,j}|\leq\mathcal{O}(l^{16}\cdot\log^{2}m/\sqrt{m})$
(24)

And let
$Q_{l}=\sqrt{(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X_{i,k}||^{2})\cdot(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X_{j,k}||^{2})}$,

$\displaystyle
K^{1}_{i,j}=Q_{1}\cdot\sum_{r=0}^{\infty}\mu^{2}_{r}[(1+\frac{1}{L^{3}}X_{i,1}^{T}X_{j,1})/Q_{1}]^{r}$
(25) $\displaystyle
K^{l}_{i,j}=Q_{l}\cdot\sum_{r=0}^{\infty}\mu^{2}_{r}(\\{\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}+K^{l-1}_{i,j}\\}/Q_{l})^{r}$

In the above equations,
$\mu_{r}=\frac{1}{\sqrt{2\pi}}\int_{0}^{\infty}\sqrt{2}xh_{r}(x)e^{-\frac{x^{2}}{2}}dx$,
$h_{r}(x)=\frac{1}{\sqrt{r!}}(-1)^{r}e^{\frac{x^{2}}{2}}\frac{d^{r}}{dx^{r}}e^{-\frac{x^{2}}{2}}.$

####  4.1.2 Backward Correlation

###### Theorem 6

For $l\neq l^{\prime}$, with probability at least $1-exp(-\Omega(\log^{2}m))$,

$|\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l^{\prime}}(x_{j})\cdot
D_{l^{\prime}}^{\prime}\rangle|\leq\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}}).$
(26)

For $l=l^{\prime}$, there is $F^{l}_{i,j}$ that, with probability at least
$1-exp(-\Omega(\log^{2}m))$,

$|\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l}(x_{j})\cdot
D_{l^{\prime}}^{\prime}\rangle-F^{l}_{i,j}|\leq\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}}).$
(27)

where

$\Sigma(x)=\frac{1}{2}+\frac{arcsin(x)}{\pi},$ (28)
$F^{l}_{i,j}\succeq\frac{1}{K}\Sigma(\\{\frac{1}{L^{3}}\langle
X_{i,l},X_{j,l}\rangle+K^{l-1}_{i,j}\\}/Q_{l}).$ (29)

and $0<K\leq\mathcal{O}(1/L^{4}).$

###### Remark 4.2

We should note that this theorem is one of the key differences between this
work and the methods in [Allen-Zhu and Li, 2019a]. In fact, we must show that
there is a constant $K>0$ such that
$\frac{1}{m}\langle\text{Back}_{l}(x_{i}),\text{Back}_{l}(x_{j})\rangle-K$ is
still positive definite. However, is $K$ large enough thus $1/K\geq poly(L)$
rather than $1/K\leq exp(-\Omega(L))$ ? This is not a trivial question. One
can only get $K\geq\frac{1}{2^{L}}$ using naive estimation. In [Allen-Zhu and
Li, 2019a], $||\bm{A}X_{l}||\leq\epsilon_{x}$ is required to make sure
$\text{Back}^{\prime}_{l}=\text{Back}_{l}(x_{i})-\text{Back}_{l}(x_{j})$
samll. However after $k$ steps of training, we can show the approximation
error is roughly
$\mathcal{O}(||\text{Back}^{\prime}||\cdot||\bm{W}^{k}-\bm{W}^{0}||)$ and
$||\bm{W}^{k}-\bm{W}^{0}||_{F}\sim\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\sim\mathscr{C}(F^{*})$.
Thus the dependence of $\epsilon_{x}$ on $\mathscr{C}(F^{*})$ is hard to be
dealt with using this method. In this paper, we do not need the normalized
condition. Our methods rely on a crucial observation that the function
$\lim_{l\to\infty}h_{l}(x_{i})^{T}h_{l}(x_{j})/(||h_{l}(x_{i})||\cdot||h_{l}(x_{j}||)$
will degenerate to a constant function.

####  4.1.3 Sketch Proof of Theorem 4

In order to estimate the complexity, we use the results in the last subsection
and Proposition 2.4,2.2 and 2.3.

Proposition 2.4 shows that, in order to estimate
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}$, we need to show

$\bm{H}^{\infty}\succeq\xi_{p}\cdot(\bm{X}_{l}^{T}\bm{X}_{l})^{\circ p}$ (30)

with $\xi_{p}>0$ for all $p\in\mathbb{N},1\leq l\leq L$. Here
$\bm{X}_{l}\in\mathbb{R}^{n\times d}=[X_{1,l},X_{2,l}...X_{n,l}]$ and

$[(\bm{X}_{l}^{T}\bm{X}_{l})^{\circ p}]_{i,j}=\\{X_{i,l}^{T}X_{j,l}\\}^{p}.$
(31)

We will show that, there is a matrix $H^{\infty}$. With probability at least
$1-\delta$,
$H_{ij}=H^{\infty}_{ij}\pm\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}})$ for all
$i,j\in[n]$, and,

$H^{\infty}_{i,j}\succeq\frac{1}{\mathcal{O}(L^{4})}\cdot
Q_{l}\Sigma(\\{\frac{1}{L^{3}}\langle
X_{i,l},X_{j,l}\rangle+K^{l-1}_{i,j}\\}/Q_{l}).$ (32)

for all $l$.

Based on (32), we can show the following results:

For all $1\leq l\leq L$ and all $k$

$H^{\infty}_{i,j}\succeq\frac{1}{\mathcal{O}(L^{4})}\Sigma(\\{K^{l}_{i,j}+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}\\}/Q_{l})\succeq\Omega(\frac{1}{L^{7}})\cdot(\frac{1}{\mathcal{O}(L)})^{k}\cdot\frac{1}{k^{2}}(X_{i,l}^{T}X_{j,l})^{k}/(||X_{i,l}||\cdot
X_{j,l}||)^{k}.$ (33)

This deduces the complexity for the Additive Concept Class in section 2.1,

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(\mathscr{C}^{*}).$
(34)

As for N-Variables Concept Class,

$\displaystyle H^{\infty}_{i,j}\succeq$
$\displaystyle\frac{1}{C_{1}^{N}L^{4}\cdot L^{2N}\cdot C_{N,p}\cdot(p/N)^{N}}$
(35)
$\displaystyle\cdot(X_{i,r_{1}}^{T}X_{j,r_{1}}+X_{i,r_{2}}^{T}X_{j,r_{2}}...+X_{i,r_{N}}^{T}X_{j,r_{N}})^{p}/(N\cdot\max_{n}(||X_{i,r_{n}}||)\cdot\max_{n}(||X_{j,r_{n}}||))^{p}$

with some large constant $C_{1}>0$. Meanwhile, for any $l\leq L,a<l$, let
$Z_{i,l,a}=[X_{i,l},X_{i,l-1},...X_{i,l-a}]$. We have:

$H^{\infty}_{i,j}\succeq\Omega(\frac{1}{L^{7}})\cdot(\frac{1}{\mathcal{O}(L)})^{k}\cdot\frac{1}{k^{2}}(Z_{i,l,a}^{T}Z_{j,l,a})^{k}/(||Z_{i,l,a}||\cdot
Z_{j,l,a}||\cdot 2^{a})^{k}$ (36)

Then from definition of complexity in section 2.2 and Proposition 2.4, we can
prove

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(\mathscr{C}^{*}).$
(37)

Therefore (20) follows.

##  5 Dissicusion

In this paper, we use a new method to avoid the normalized conditions. The
main idea is to provide an esitmation for
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}$ in the RNN case
directly. However, the value of
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}$ is only
explicitly calculated for the two-layer case in [Arora et al., 2019]. In the
RNN cases, the neural tangent kernel matrix involves the depth and the weight
sharing in the network and difficult to deal with.

In [Allen-Zhu and Li, 2019a], their method is to reduce the RNN case to

$f_{L}\approx\sum_{l}Back^{(0)}\cdot\mathbbm{1}_{\langle
W,h_{l-1}\rangle+AX_{l}\geq 0}W^{*}\cdot h_{l-1},$

which is similar to a summation of $L$ two-layer networks. And this reduction
requires the following operations in [Allen-Zhu and Li, 2019a]:

  1. 1)

Introduce new randomness to keep the independence of rows in the random
initialization matrices W and A at different depths. Then estimate the
perturbation.

  2. 2)

Show the "off-target" Backward Correlation is zero.

  3. 3)

Estimate the "on target" Backward Correlation by introducing a normalized
input sequence $x^{(0)}$.

  4. 4)

Explicitly construct the approximation.

These steps strongly rely on the normalized condition $||X_{l}||\ll 1$ and
this is apparently unrealistic. Instead, we calculate the kernel matrix and we
introduce many new estimation to avoid this condition.

We should note that this expression

$f_{L}\approx\sum_{l}Back^{(0)}\cdot\mathbbm{1}_{\langle
W,h_{l-1}\rangle+AX_{l}\geq 0}W^{*}\cdot h_{l-1}$

is additive in itself. Thus the nonlinear interaction between different
positions considered in this paper, especially N-variable target functions,
cannot be deduced using the from this method. In the previous proof, [Allen-
Zhu and Li, 2019a] is to use these steps to reduce the RNN function to a
summation of two-layer networks and ignore the correlation between inputs from
different locations and this heavily relies on the normalized condition. In
our method, we need to consider the information in Back to show the non-linear
correlation between the inputs at different positions and prove N-variable
target functions are learnable, while [Allen-Zhu and Li, 2019a]. requires the
normalized condition to make sure $\text{Back}\approx\text{Back}^{(0)}$ to be
roughly a constant. This is one of the most different parts between this work
and [Allen-Zhu and Li, 2019a].

In our case, since we do no use the normalized condition, we must show the
polynomial decay of the constant part in $Back$. As mentioned in Remark 4.2,
in our case, it is generally non-trivial to show
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq
O(\mathscr{C}^{*})$ with $\mathscr{C}^{*}$ polynomial in $L$. Our methods rely
on a detailed estimation on the degeneracy of long RNN based on Theorem 5.

##  6 Related Work

Overparameterized neural network. In [Tian, 2017] and [Du et al., 2018], it is
shown that, for a single-hidden-node ReLU network, under mild assumptions, the
loss function is one point convex in a very large area. However, in [Safran
and Shamir, 2018], the authors pointed out that such good properties are rare
for networks with multi-hidden nodes, and indicated that an over-
parameterization assumption is necessary. Similarly, [Hardt et al., 2016]
showed that over-parameterization can help in the training process of a linear
dynamic system i.e., linear RNN. A different way to show over-parameterization
is important as in [Freeman and Bruna, 2016], this work proved that in the
two-layer case if the number of the hidden nodes is large enough, the sub-
level sets of the loss will be nearly connected. Their method can also be
applied to deep networks with a skip connection in [Wang et al., 2020] to
study the properties of loss surfaces.

Recent breakthroughs were made in understanding the neural tangent kernel(NTK)
[Jacot et al., 2018, Alemohammad et al., 2021] of the neural network near the
area of the random initialization. In [Li and Liang, 2018], [Du et al., 2019],
[Allen-Zhu et al., 2019b] and [Allen-Zhu et al., 2019c], it is shown that deep
networks with a large hidden size can attain zero training error, under some
assumptions of input non-degeneracy. This explains the empirical results
[Zhang et al., 2017] that DNN can fit training data with even random labels.

There are also some provable convergence results with over-parameterization
going beyond NTK. The loss surface of the two-layer over-parameterized network
with quadratic activation function was studied in [Du and Lee, 2018] and
[Mahdi et al., 2018]. They showed that all the bad local minima are eliminated
by over-parameterization. For ReLU activation function, in [Allen-Zhu and Li,
2019b], it is shown that there exits some functions can not be learned by any
kernel functions but learnable with less error by a network with a skip
connection. [Li et al., 2020] provided a convergence result for learning a
specific two-layer neural network which can not be learned by any kernel
method, including Neural Tangent Kernel.

Generalization Ability of Deep Learning

Classical VC theory cannot explain the generalization ability of deep learning
because the VC-dimension of neural networks is at least linear in the number
of parameters [Bartlett et al., 2019]. Recently, [Allen-Zhu et al., 2019a]
showed that overparameterized neural networks can learn some notable concept
classes of target functions with rich types. Moreover, their work goes beyond
the NTK linearization and provides new results on the non-convex interactions
of the three-layer network. Meanwhile, [Arora et al., 2019] provided a fine-
grained analysis on the generalization error and showed the connections to the
matrix of the neural tangent kernel. The results were generalized to the
multi-layer case in [Cao and Gu, 2019]. Similar results were also studied in
[Ji and Telgarsky, 2020] and [Chen et al., 2020b].

Ref. [Allen-Zhu et al., 2019a] also considered the generalization error bounds
beyond the first-order NTK. It has been shown in [Allen-Zhu et al., 2019a]
that a three-layer ReLU network can provable learn some notable composite
functions and dropout can help to reduce the Rademacher Complexity of the
network thus reduce the generalization error bounds. The proof is based on the
second-order NTK expansion and saddle points escaping arguments. Higher-order
NTK are also studied in [Bai and Lee, 2020] with provable generalization error
bounds. Moreover, it is shown in [Chen et al., 2020a] that comparing with the
general NTK, deep networks with neural representation can achieve improved
sample complexities, while for the first-order NTK, depth may not provide
benefits for the learning ability [Bietti and Bach, 2021].

##  7 Conclusion and Future Work

In this paper, we studied the problem of what type of function can be learned
by RNN. In this work, we showed that RNNs can provably learn the two types of
functions, the additive concept class and the N-variables concept class in
_almost-polynomial in input length many iterations and samples_ starting from
random initialization. For the additive concept class, we proved the result
without the normalized condition and showed the almost-polynomial complexity
in input length $L$. For the N-variable concept class, we showed that RNN with
ReLU activation function can provably learn functions like
$\psi(\langle\beta,[X_{l_{1}},...,X_{l_{N}}]\rangle)$. The complexity of
learning such functions grows exponentially with either $N$ or
$l_{0}=\max(l_{1},...l_{N})-\min(l_{1},...l_{N})$, but when one of them is
small, the complexity is almost-polynomial in the input length $L$.

One of the limitations is that this work relies on the NTK linearization of
RNN. One probably direction is to consider the non-convex interactions in RNN
and learn more complex functions using the method in [Allen-Zhu et al.,
2019a]. Meanwhile, this work studied RNN with ReLU activation function. This
did not consider the “gate” structure in RNN. We believe that a study on GRU,
LSTM, and MGU may lead to learning more complex functions with long-term
memory.

## Acknowledgement

We would like to thank Professor Wenyu Zhang for his valuable discussion, and
Shuai Wang for the great help in writing. We also thank the anonymous
reviewers and area chair for their helpful comments. This research was funded
by the Fundamental Research Funds for the Central Universities (Grant number
2020YJS012).

## References

  * [Alemohammad et al., 2021] Alemohammad, S., Wang, Z., Balestriero, R., and Baraniuk, R. (2021).  The recurrent neural tangent kernel.  In International Conference on Learning Representations.
  * [Allen-Zhu and Li, 2019a] Allen-Zhu, Z. and Li, Y. (2019a).  Can sgd learn recurrent neural networks with provable generalization?  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * [Allen-Zhu and Li, 2019b] Allen-Zhu, Z. and Li, Y. (2019b).  What can resnet learn efficiently, going beyond kernels?  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * [Allen-Zhu et al., 2019a] Allen-Zhu, Z., Li, Y., and Liang, Y. (2019a).  Learning and generalization in overparameterized neural networks, going beyond two layers.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * [Allen-Zhu et al., 2019b] Allen-Zhu, Z., Li, Y., and Song, Z. (2019b).  A convergence theory for deep learning via over-parameterization.  In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 242–252. PMLR.
  * [Allen-Zhu et al., 2019c] Allen-Zhu, Z., Li, Y., and Song, Z. (2019c).  On the convergence rate of training recurrent neural networks.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * [Arora et al., 2019] Arora, S., Du, S. S., Hu, W., Li, Z., and Wang, R. (2019).  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 322–332. PMLR.
  * [Bai and Lee, 2020] Bai, Y. and Lee, J. D. (2020).  Beyond linearization: On quadratic and higher-order approximation of wide neural networks.  In International Conference on Learning Representations.
  * [Bartlett et al., 2019] Bartlett, P. L., Harvey, N., Liaw, C., and Mehrabian, A. (2019).  Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks.  J. Mach. Learn. Res., 20:63:1–63:17.
  * [BergJens et al., 1984] BergJens, C., Reus, P., and Ressel, C. (1984).  Harmonic Analysis on Semigroups Theory of Positive Definite and Related Functions.  Springer Netherlands.
  * [Bietti and Bach, 2021] Bietti, A. and Bach, F. (2021).  Deep equals shallow for relu networks in kernel regimes.
  * [Boucheron et al., 2013] Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration inequalities : a non asymptotic theory of independence.  Oxford University Press.
  * [Cao and Gu, 2019] Cao, Y. and Gu, Q. (2019).  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * [Chen et al., 2020a] Chen, M., Bai, Y., Lee, J. D., Zhao, T., Wang, H., Xiong, C., and Socher, R. (2020a).  Towards understanding hierarchical learning: Benefits of neural representations.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 22134–22145. Curran Associates, Inc.
  * [Chen et al., 2020b] Chen, Z., Cao, Y., Zou, D., and Gu, Q. (2020b).  How much over-parameterization is sufficient to learn deep relu networks?
  * [Daniely et al., 2016] Daniely, A., Frostig, R., and Singer, Y. (2016).  Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity.  In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc.
  * [Du and Lee, 2018] Du, S. S. and Lee, J. D. (2018).  On the power of over-parametrization in neural networks with quadratic activation.  International conference on machine learning, pages 1328–1337.
  * [Du et al., 2018] Du, S. S., Lee, J. D., and Tian, Y. (2018).  When is a convolutional filter easy to learn.  International conference on machine learning.
  * [Du et al., 2019] Du, S. S., Zhai, X., Poczos, B., and Singh, A. (2019).  Gradient descent provably optimizes over-parameterized neural networks.  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net.
  * [Freeman and Bruna, 2016] Freeman, C. D. and Bruna, J. (2016).  Topology and geometry of half-rectified network optimization.  International conference on machine learning.
  * [Ge et al., 2017] Ge, R., Lee, J. D., and Ma, T. (2017).  Learning one-hidden-layer neural networks with landscape design.  CoRR, abs/1711.00501.
  * [Hardt et al., 2016] Hardt, M., Ma, T., and Recht, B. (2016).  Gradient descent learns linear dynamical systems.  Journal of Machine Learning Research, 19.
  * [Huang et al., 2020] Huang, K., Wang, Y., Tao, M., and Zhao, T. (2020).  Why do deep residual networks generalize better than deep feedforward networks? - A neural tangent kernel perspective.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual.
  * [Jacot et al., 2018] Jacot, A., Gabriel, F., and Hongler, C. (2018).  Neural tangent kernel: Convergence and generalization in neural networks.  In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
  * [Ji and Telgarsky, 2020] Ji, Z. and Telgarsky, M. (2020).  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.
  * [Li and Liang, 2018] Li, Y. and Liang, Y. (2018).  Learning overparameterized neural networks via stochastic gradient descent on structured data.  In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
  * [Li et al., 2020] Li, Y., Ma, T., and Zhang, H. R. (2020).  Learning over-parametrized two-layer relu neural networks beyond ntk.
  * [Mahdi et al., 2018] Mahdi, S., Adel, J., and D., L. J. (2018).  Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.  IEEE Transactions on Information Theory.
  * [Safran and Shamir, 2018] Safran, I. and Shamir, O. (2018).  Spurious local minima are common in two-layer relu neural networks.  International conference on machine learning, pages 4430–4438.
  * [Tian, 2017] Tian, Y. (2017).  Symmetry-breaking convergence analysis of certain two-layered neural networks with relu nonlinearity.  International conference on learning representations.
  * [Wang et al., 2020] Wang, L., Shen, B., Zhao, N., and Zhang, Z. (2020).  Is the skip connection provable to reform the neural network loss landscape?  In Bessiere, C., editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 2792–2798. International Joint Conferences on Artificial Intelligence Organization.  Main track.
  * [Zhang et al., 2017] Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2017).  Understanding deep learning requires rethinking generalization.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net.

Supplementary Materials

##  Appendix A Flowchart of the Proofs

Theorem 5Theorem 16Theorem 4Theorem 6Theorem 19Theorem 3Main Result: Theorem
2Lemma 14Lemma 15Theorem 13Theorem 23Re-RandomizationptKey Estimation
onBackward CorrelationNeural Tangent KernelForwardBackward
ComplexityGeneralization Error Figure 1: Flowchart of the Proof.

The Flowchart of the proof is shown in Figure 1. There are two parts. The
first part is to prove Theorem 3. This is easy by using techniques in [Allen-
Zhu et al., 2019c] and [Cao and Gu, 2019]. The more important part is to prove
Theorem 4. We study the forward and backward correlation in Theorem 5 and 6.
In Theorem 19, we show the polynomial degeneration of backward correlation
which is crucial to show the complexity is polynomial in $L$.

##  Appendix B Some Probability Theory Lemmas

###### Definition 1

A random variable $X$ is said to be sub-Gaussian with variance proxy
$\sigma^{2}$ if $\mathbb{E}[X]=0$ and for all $s\in\mathbb{R}$,

$\mathbb{E}[e^{sX}]\leq e^{\frac{\sigma^{2}s^{2}}{\sigma^{2}}}.$ (38)

A random variable X is said to be $\lambda$-sub-exponential if
$\mathbb{E}[X]=0$, and for all $s$ that $|s|\leq\frac{1}{\lambda}$,

$\mathbb{E}[e^{sX}]\leq e^{\frac{s^{2}\lambda^{2}}{2}}$ (39)

For $\lambda$-sub-exponential random variable, we have the following standard
concentration inequality from Chernoff bound estimation(c.f. [Boucheron et
al., 2013]):

###### Theorem 7

Let $X_{1},X_{2},...X_{m}$ be i.i.d $\lambda$-sub-exponential random variable
with $\lambda<\mathcal{O}(1)$. Let $0<\epsilon\leq 1$. With probability at
least $1-exp[\Omega(m\epsilon^{2})]$,

$|\frac{1}{m}\sum_{i=1}^{m}X_{i}|\leq\epsilon$ (40)

Let $\phi$ be a function with either $|\phi(x)|\leq|Bx|$ or $|\phi(x)|\leq B$
for some $B>0$. Assuming $w$ is a Gaussian random vector, we can show
$\phi(w^{T}X_{1})\phi(w^{T}X_{2})-\mathbb{E}\phi(w^{T}X_{1})\phi(w^{T}X_{2})$
is $\lambda$-sub-exponential for some $\lambda$ by estimating the moments. For
$\mathbb{E}\phi(w^{T}X_{1})\phi(w^{T}X_{2})$, there is an equation which is a
direct corollary of Claim 4.3 in [Ge et al., 2017]:

###### Theorem 8

Consider $M\in\mathbb{R}^{d}$, all the entries of $M$ are i.i.d. generated
from $N(0,\frac{1}{d})$, and $X_{1},X_{2}\in\mathbb{R}^{d}$ with
$||X_{1}||=||X_{2}||=1$. Let $\mu_{i}(\phi)$ denote the $i-$th Hermite
coefficient of function $\phi$, i.e.
$\mu_{r}(\phi)=\frac{1}{\sqrt{2\pi}}\int_{0}^{\infty}\phi(x)h_{r}(x)e^{-\frac{x^{2}}{2}}dx$,
$h_{r}(x)=\frac{1}{\sqrt{r!}}(-1)^{r}e^{\frac{x^{2}}{2}}\frac{d^{r}}{dx^{r}}e^{-\frac{x^{2}}{2}}.$

We have

$\underset{M}{\mathbb{E}}\phi_{1}(M^{T}X_{2})\phi_{2}(M^{T}X_{1})=\sum_{r}\mu_{r}(\phi_{1})\mu_{r}(\phi_{2})(X_{1}^{T}X_{2})^{r}.$
(41)

$\underset{M}{\mathbb{E}}\phi(M^{T}X_{2})\phi(M^{T}X_{1})=\sum_{r}\mu^{2}_{r}(\phi)(X_{1}^{T}X_{2})^{r}.$
(42)

Combine the above two theorems and set $\epsilon=\frac{\log m}{\sqrt{m}}$. We
have:

###### Theorem 9

Let $\bm{W}\in\mathbb{R}^{m\times d}$. All the entries of $M$ are i.i.d.
generated from $N(0,\frac{2}{m})$, and $X_{1},X_{2}\in\mathbb{R}^{d}$ with
$||X_{1}||=||X_{2}||=1$. $\phi(x)=\max(0,x)$ denotes the ReLU activation
function. $\mu_{i}(\phi)$ denotes the $i-$th Hermite coefficient of function
$\phi$. $W_{i}$ denotes the $i$-th row of $\bm{W}$. With probability at least
$1-exp(-\Omega(\log^{2}m))$,

$\displaystyle\phi^{T}(\bm{W}X_{1})\phi(\bm{W}X_{2})$
$\displaystyle=\sum_{i}\phi^{T}(W_{i}X_{1})\phi(W_{i}X_{2})$ (43)
$\displaystyle=\mathbb{E}_{w\sim
N(0,I_{d})}\phi(w^{T}X_{1})\phi(w^{T}X_{2})\pm\mathcal{O}(\frac{\log
m}{\sqrt{m}})$
$\displaystyle=\sum_{r}\mu_{r}(\phi)\mu_{r}(\phi)(X_{1}^{T}X_{2})^{r}\pm\mathcal{O}(\frac{\log
m}{\sqrt{m}}).$

This theorem is a direct corollary of the concentration inequality for the
sub-exponential random variable $\phi(w^{T}X_{1})\phi(w^{T}X_{2})$.

In the case of ReLU function and its derivative, we can obtain analytical
expressions which have been proved in [Daniely et al., 2016, Huang et al.,
2020]:

###### Theorem 10

Consider functions $\phi_{1}(x)=\sqrt{2}\max(0,x)$ and
$\phi_{2}(x)=\sqrt{2}\mathbbm{1}\\{x>0\\}$. Let
$X_{1},X_{2}\in\mathbb{R}^{d},||X_{1}||=||X_{2}||=1$, $z=X_{1}^{T}X_{2}$.

$\mathbb{E}_{w\sim
N(0,I_{d})}\phi_{1}(w^{T}X_{1})\phi_{1}(w^{T}X_{2})=\frac{\sqrt{1-z^{2}}+(\pi-
arccos(z))z}{\pi},$ (44)

and

$\mathbb{E}_{w\sim
N(0,I_{d})}\phi_{2}(w^{T}X_{1})\phi_{2}(w^{T}X_{2})=\frac{\pi-
arccos(z)}{\pi}.$ (45)

For such functions $f(z)=\mathbb{E}_{w\sim
N(0,I_{d})}\phi(w^{T}X_{1})\phi(w^{T}X_{2})$, we can see
$f(0)=\mu^{2}_{0}(\phi)$ and $f^{\prime}(0)=\mu^{2}_{1}(\phi)$.

##  Appendix C Technical Lemmas for RNN

Consider equations

$\displaystyle h_{l}(\bm{W},x)=\phi(\bm{W}h_{l-1}+\bm{A}X_{l}),$ (46)
$\displaystyle f(\bm{W}),x)=\bm{B}^{T}h_{L}(x),$ $\displaystyle\nabla
f(\bm{W},x_{i})=\sum_{l=1}^{L}\text{Back}^{T}_{l}D_{l}\cdot h_{l}^{T}(x_{i}),$
$\displaystyle\text{Back}_{l}(\bm{W},x_{i})=\bm{B}^{T}D_{L}\bm{W}\cdots
D_{l+1}\bm{W}.$

The properties of $\nabla f(\bm{W},x_{i})$ and $h_{l}$ have been already
appeared in [Allen-Zhu et al., 2019c]. We list the results we used in this
section.

Let $\bm{W}_{0}$ be the point of Randomly Initialization and
$B(\bm{W}_{0},\omega)=\\{\bm{W}|\ ||\bm{W}-\bm{W}_{0}||_{F}\leq\omega\\}$. We
have:

###### Lemma 11

For fixed vector $x\in\mathbb{R}^{d}$, $y,z\in\mathbb{R}^{m}$. With
probability at least $1-exp(-\Omega(m/L^{2}))$

$||\mathbbm{1}_{\bm{W}_{0}y+\bm{A}x>0}\cdot\bm{W}_{0}z||_{2}\leq||z||_{2}(1+1/100L).$
(47)

For fixed $x\in\mathbb{R}^{d}$ and all $y,z$:

$||\mathbbm{1}_{\bm{W}_{0}y+\bm{A}x>0}\cdot\bm{W}_{0}z||_{2}\leq||z||_{2}(1+1/50L).$
(48)

The first equation is from Claim B.13 in [Allen-Zhu et al., 2019c]. The second
one can be easily deduced from a $\epsilon$-net argument.

###### Lemma 12

(Section B and Section C in [Allen-Zhu et al., 2019c]) Let $\tau_{0}\leq
poly(n,L),\omega\leq\tau_{0}\cdot m^{-1/2}$ , $m\geq poly(L,n,\delta^{-1})$.
With probability at least $1-\delta$, for all $i\in[n]$, all $l$, and
$\bm{W}\in B(\bm{W}_{0},\omega)$

  1. (a)

$||h_{l}(\bm{W},x_{i})||\leq\mathcal{O}(l)$,

  2. (b)

$||\text{Back}_{l}(\bm{W},x_{i})D_{l}(\bm{W},x_{i})||_{2}\leq\mathcal{O}(L^{7}\sqrt{m})$,

  3. (c)

$||\bm{W}D_{l_{1}-1}...\bm{W}(D_{l+1})||\leq\mathcal{O}(L^{7})$,

  4. (d)

For any vector $v$ with
$||v||_{0}\leq\mathcal{O}(L^{10/3}\tau_{0}^{2/3}m^{2/3})$,
$||B^{T}(D^{0}_{L})\bm{W}^{0}...\bm{W}^{0}v||\leq\sqrt{m}L^{5/3}\tau_{0}^{1/3}\log
m\cdot m^{-1/6}$,

  5. (e)

$||D_{l}^{\prime}||_{0}\leq\mathcal{O}(L^{10/3}\tau_{0}^{2/3}m^{2/3}).$

The (a) is from the proof of Lemma B.3 and Lemma C.2a in [Allen-Zhu et al.,
2019c], and the (b) is from Lemma C.9 and Lemma B.11 in [Allen-Zhu et al.,
2019c]. (c) is from Lemma C.7 in [Allen-Zhu et al., 2019c]. From Corollary
B.18, Lemma C.11 and Claim G.2 in [Allen-Zhu et al., 2019c] we have (d) and
(e).

In our case, $||\bm{A}X_{l}||\leq\frac{1}{L^{3/2}}$, rather than
$||\bm{A}X_{l}||\leq\mathcal{O}(1)$. These bounds can be improved, but since
we mainly care about the exponential dependence on $L$, we do not use it.

These equations deduce the following linearization theorem which is an
analogue of Lemma 4.1 in [Cao and Gu, 2019]:

###### Theorem 13

With probability at least $1-\mathcal{O}(n)\cdot exp(-\Omega(\log m))$, for
all $i\in[n]$ and $\bm{W},\bm{W}^{\prime}\in B(\bm{W}_{0},\omega)$,

$|f(\bm{W}^{\prime},x_{i})-f(\bm{W},x_{i})-\langle\nabla
f(\bm{W},x_{i}),\bm{W}^{\prime}-\bm{W}\rangle|\leq\mathcal{O}(\omega^{1/3}L^{10}\log
m\sqrt{m})||\bm{W}^{\prime}-\bm{W}||_{2}.$ (49)

Proof: Let

$\displaystyle h_{L}(x)=h_{L}(\bm{W},x),\
h_{L}(\bm{W^{\prime}},x)=h_{L}(x)+h^{\prime}_{L}(x),$ (50) $\displaystyle
D_{l}=D_{l}(\bm{W},x),\ D_{l}^{\prime}=D_{l}(\bm{W}^{\prime},x),\
D^{0}_{l}=D_{l}(\bm{W}_{0},x).$

By Claim G.2 in [Allen-Zhu et al., 2019c], there exits diagonal matrices
$D^{\prime\prime}_{l}$, $\\{D^{\prime\prime}_{l}\\}_{ii}\neq 0$ if and only if
$\\{D^{\prime}_{l}\\}_{ii}\neq 0$,
$||D^{\prime\prime}_{l}||_{0}\leq||D_{l}^{\prime}||_{0}\leq\mathcal{O}(L^{10/3}\tau_{0}^{2/3}m^{2/3})$,
and

$\displaystyle B^{T}(h_{L}(x)+h^{\prime}_{L}(x))-B^{T}h_{L}(x)=$
$\displaystyle\sum_{l=1}^{L-1}B^{T}(D_{L}+D^{\prime\prime}_{L})\bm{W}^{\prime}...(D_{l+1}+D^{\prime\prime}_{l+1})$
(51) $\displaystyle\cdot(\bm{W}^{\prime}-\bm{W})h_{l}(x).$

Then,

$\displaystyle f(\bm{W}^{\prime},x_{i})-f(\bm{W},x_{i})-\langle\nabla
f(\bm{W},x_{i}),\bm{W}^{\prime}-\bm{W}\rangle$ (52)
$\displaystyle=\sum_{l=1}^{L-1}B^{T}(D_{L}+D^{\prime\prime}_{L})\bm{W}^{\prime}...(D_{l+1}+D^{\prime\prime}_{l+1})\cdot(\bm{W}^{\prime}-\bm{W})h_{l}(x)$
$\displaystyle-B^{T}D_{L}\bm{W}...\bm{W}D_{l+1}\cdot(\bm{W}^{\prime}-\bm{W})h_{l}(x).$

To prove the theorem, same as Lemma 5.7 in [Allen-Zhu et al., 2019b], we have
the following result: Let $D^{0/1}_{l}$ be diagonal matrix and
$(D^{0/1}_{l})_{ii}=0$ if $(D_{l}+D^{\prime\prime}_{l}-D^{0}_{l})_{ii}=0$,
$(D^{0/1}_{l})_{ii}=1$ if $(D_{l}+D^{\prime\prime}_{l}-D^{0}_{l})_{ii}\neq 0$.
With probability at least $1-\delta$,

$\displaystyle||B^{T}(D_{L}+D^{\prime\prime}_{L})\bm{W}^{\prime}...(D_{l+1}+D^{\prime\prime}_{l+1})\cdot\bm{W}^{\prime})-B^{T}D_{L}\bm{W}...\bm{W}D_{l+1}\cdot\bm{W}||$
(53)
$\displaystyle\leq\mathcal{O}(\sum_{l_{1}=l+1}^{L}\underbrace{||B^{T}(D^{0}_{L})\bm{W}^{0}...\bm{W}^{0}(D^{0/1}_{l_{1}})||}_{T_{1}}\cdot||D^{\prime\prime}_{l_{1}}||\cdot\underbrace{||(D^{0/1}_{l_{1}})\bm{W}^{\prime}D^{\prime}_{l_{1}-1}...\bm{W}^{\prime}(D^{\prime}_{l+1})||}_{T_{2}})$
$\displaystyle\overset{(a)}{\leq}\mathcal{O}(\sqrt{m}L^{5/3+8}\tau_{0}^{1/3}\log
m\cdot m^{-1/6})\leq\mathcal{O}(\sqrt{m}L^{10}\omega^{1/3}\log m).$

In (a), $T_{2}\leq O(L^{7})$ is from (c) in Lemma 12. From (d) in Lemma 12 and
$||D^{\prime\prime}_{l}||_{0}\leq\mathcal{O}(L^{10/3}\tau_{0}^{2/3}m^{2/3})$,
$T_{1}\leq\sqrt{m}L^{5/3}\tau_{0}^{1/3}\log m\cdot m^{-1/6}$. $\blacksquare$

###### Remark C.1

In this theorem,

$|f(\bm{W}^{\prime},x_{i})-f(\bm{W},x_{i})-\langle\nabla
f(\bm{W},x_{i}),\bm{W}^{\prime}-\bm{W}\rangle|\leq\mathcal{O}(\omega^{1/3}L^{10}\log
m\sqrt{m})||\bm{W}^{\prime}-\bm{W}||_{2}.$ (54)

And in [Cao and Gu, 2019], there is a similar result that

$|f(\bm{W}^{\prime},x_{i})-f(\bm{W},x_{i})-\langle\nabla
f(\bm{W},x_{i}),\bm{W}^{\prime}-\bm{W}\rangle|\leq\mathcal{O}(\omega^{1/3}L^{2}\sqrt{\log
m}\sqrt{m})||\bm{W}^{\prime}-\bm{W}||_{2}.$ (55)

The differences on $\log m$ are from that Lemma 4.4 in [Allen-Zhu et al.,
2019b] says if $||u||_{0}\leq s$,
$|B^{T}(D_{L}+D^{\prime\prime}_{L})\bm{W}^{\prime}_{L}...(D_{l+1}+D^{\prime\prime}_{l+1})\cdot\bm{W}^{\prime}_{l+1}u|\leq\mathcal{O}(\sqrt{s\log
m}$ and Corollary B.18 in [Allen-Zhu et al., 2019c] says
$|B^{T}(D_{L}+D^{\prime\prime}_{L})\bm{W}^{\prime}...(D_{l+1}+D^{\prime\prime}_{l+1})\cdot\bm{W}^{\prime}u|\leq\mathcal{O}(\sqrt{s}\log
m)$ for RNN case.

##  Appendix D Generalization properties: Proof of Theorem 3

###### Lemma 14

Denote $L_{i}(\bm{W})=\ell(y_{i}\cdot f(\bm{W},x_{i}))$. Suppose there exits
$\bm{W}^{*}\in B(\bm{W}_{0},R/\sqrt{m})$ with $R\leq poly(n,L)$,
$L_{i}(\bm{W}^{*})\leq\frac{1+R^{2}}{n}$. For any $\delta$, there exists

$m^{*}(n,\delta,R,L)=poly(n,R,L,\delta^{-1})$ (56)

such that if $m>m^{*}$, with probability at least $1-\delta$, SGD with
$\eta=1/m$ for some small enough $\nu$ will output:

$\frac{1}{n}\sum_{i=1}^{n}L^{0-1}_{\emph{D}}(\bm{W}^{i})\leq\mathcal{O}(\frac{1}{n})+\mathcal{O}(\frac{R^{2}}{n})+\mathcal{O}(\frac{\log(1/\delta)}{n}).$
(57)

Proof of Lemma 14:

Firstly, for all $i$, $\bm{W}\in B(\bm{W}_{0},\omega),\omega\leq R/m^{1/2}$,
from Lemma 12, $||\nabla f(\bm{W},x_{i})||_{F}\leq\mathcal{O}(L^{8}\sqrt{m})$.

$||\bm{W}^{i+1}-\bm{W}^{0}||_{F}\leq\sum_{k=1}^{i}||\bm{W}^{k+1}-\bm{W}^{k}||_{F}\leq\mathcal{O}(n\eta
L^{8}\sqrt{m})\leq\frac{L^{8}R}{\sqrt{m}}\leq\mathcal{O}(\tau_{0}/m^{1/2})$
(58)

with $\tau_{0}\leq poly(n,L)$. Thus we can use Theorem 13. We have,

$\displaystyle L_{i}(\bm{W}^{i})-L_{i}(\bm{W}^{*})$
$\displaystyle\leq\langle\nabla_{\bm{W}}L_{i}(\bm{W}^{i}),\bm{W}^{i}-\bm{W}^{*}\rangle$
(59) $\displaystyle+|\ell^{\prime}(y_{i}f(\bm{W},x_{i}))\cdot
y_{i}|\cdot\mathcal{O}(\omega^{1/3}L^{10}\log
m\sqrt{m})||\bm{W}^{i}-\bm{W}^{*}||_{2}$
$\displaystyle=\frac{\langle\bm{W}^{i}-\bm{W}^{i+1},\bm{W}^{i}-\bm{W}^{*}\rangle}{\eta}+\mathcal{O}(\omega^{1/3}L^{10}\log
m\sqrt{m})||\bm{W}^{i}-\bm{W}^{*}||_{2}$

Therefore,

$\displaystyle\sum_{i=1}^{n}L_{i}(\bm{W}^{i})$
$\displaystyle\leq\sum_{i=1}^{n}\\{L_{i}(\bm{W}^{*})+\frac{R^{2}}{2\eta
m}+\mathcal{O}(\omega^{1/3}L^{10}\log
m\sqrt{m})\sum_{i=1}^{n}||\bm{W}^{i}-\bm{W}^{*}||_{2}\\},$ (60)
$\displaystyle\leq\sum_{i=1}^{n}\\{L_{i}(\bm{W}^{*})+\frac{R^{2}}{2\eta
m}+\mathcal{O}(L^{10}\log m\cdot n\cdot R^{4/3}\cdot m^{-1/6})\\},$
$\displaystyle\overset{(a)}{\leq}\sum_{i=1}^{n}L_{i}(\bm{W}^{*})+R^{2}.$

In (a), we use $m>m^{*}\sim poly(n,L)$.

Therefore,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}L_{i}(\bm{W}^{i})\leq\frac{1+R^{2}}{n}+\frac{R^{2}}{n}.$
(61)

The cross-entropy function $\ell(x)$ satisfies that
$L^{\prime}_{i}(\bm{W}^{i})\leq L_{i}(\bm{W}^{i})$ and
$L^{0-1}_{i}(\bm{W}^{i})\leq L^{\prime}_{i}(\bm{W}^{i})$, where

$L^{\prime}_{i}(\bm{W}^{i})=-\ell^{\prime}(y_{i}f(\bm{W},x_{i})).$ (62)

And $-\ell^{\prime}(x)$ is bounded. Using the boundedness and a martingale
Bernstein bound argument as Lemma 4.3 in [Ji and Telgarsky, 2020], we have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}L^{0-1}_{D}(\bm{W}^{i})\leq\mathcal{O}(\frac{1}{n})+\mathcal{O}(\frac{R^{2}}{n})+\mathcal{O}(\frac{\log(1/\delta)}{n}).$
(63)

$\blacksquare$

###### Remark D.1

The result of generalization error $1/n$ is this better than that in [Cao and
Gu, 2019] $1/\sqrt{n}$, which shows

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}L^{0-1}_{D}(\bm{W}^{i})\leq\frac{4}{n}\sum_{i=1}^{n}L_{i}(\bm{W}^{*})+\mathcal{O}(\frac{R}{\sqrt{n}})+\mathcal{O}(\sqrt{\frac{\log(1/\delta)}{n}}).$
(64)

This is because Lemma 4.3 in [Ji and Telgarsky, 2020] makes use of the
boundedness of $L_{i}(\bm{W})$. Thus it is applicable in this theorem. There
is also a similar argument in Lemma 5.6 of [Chen et al., 2020b].

###### Lemma 15

Under the condition of Theorem 3, with probability at least $1-\delta$, there
exits $\bm{W}^{*}\in B(\bm{W}_{0},R/\sqrt{m})$, such that
$L_{i}(\bm{W}^{*})\leq\frac{1+R^{2}}{n}$,
$R\leq\widetilde{\mathcal{O}}(L\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}})$.

Proof of Lemma 15:
Let $\bm{\epsilon}$ be the matrix in (18),

$\bm{G}=m^{-1/2}\cdot(vec[\nabla f(\bm{W}^{0},x_{1})],vec[\nabla
f(\bm{W}^{0},x_{2})],...vec[\nabla
f(\bm{W}^{0},x_{n})])\in\mathbb{R}^{m^{2}\times n}.$
$\bm{G}+\bm{\epsilon}=\bm{P}\bm{\Lambda}\bm{Q}^{T}.$ (65)

is the singular value decomposition. Note that $m^{2}\gg n$. We can set
$\bm{\epsilon}^{T}\bm{G}=0$ without changing $\bm{\epsilon^{T}\epsilon}$.

With probability at least $1-\delta$, for all $i\in[n]$,
$|f(\bm{W}^{0},x_{i})|\leq\mathcal{O}(L\log(n/\delta))$. We assume
$w^{*}=\bm{P}\bm{\Lambda}^{-1}\bm{Q}^{T}(B\cdot\widetilde{y})$, with
$0<|f(\bm{W}^{0},x_{i})|+\log\\{1/[exp(n^{-1})-1]\\}+0.01<B\leq\mathcal{O}(L\log(n/\delta))$
for all $i\in[n]$, then $||w^{*}||^{2}_{2}\leq
B^{2}\widetilde{y}^{T}(\bm{H}+\bm{\epsilon}^{T}\bm{\epsilon})^{-1}\widetilde{y}.$
and $\bm{G}^{T}w^{*}=B\cdot\widetilde{y}-\bm{\epsilon}^{T}w^{*}$. Meanwhile,
reshape $w^{*}$ as $\bm{W}^{*}\in\mathbb{R}^{m\times m}$, then we have

$\langle\nabla
f(\bm{W}^{0},x_{i}),\bm{W}^{*}-\bm{W}^{0}\rangle=B\cdot\widetilde{y}_{i}\pm||\bm{\epsilon}||_{F}\cdot\sqrt{\widetilde{y}^{T}(\bm{H}+\bm{\epsilon})^{-1}\widetilde{y}}=B\cdot\widetilde{y}_{i}\pm
0.01.$ (66)

Therefore $\bm{W}^{*}\in
B(\bm{W}_{0},\widetilde{O}(L\mathscr{C}^{*}/\sqrt{m}))$, and

$\displaystyle\ell(y_{i}\cdot(f(\bm{W}^{*},x_{i})))$
$\displaystyle\leq\ell(y_{i}\cdot\\{f(\bm{W}^{0},x_{i})+\langle\nabla
f(\bm{W}^{0},x_{i}),\bm{W}^{*}-\bm{W}^{0}\rangle\\})$ (67)
$\displaystyle+|\ell^{\prime}(y_{i}f(\bm{W},x_{i}))\cdot
y_{i}|\cdot\mathcal{O}(L^{10}\log m\cdot n\cdot R^{4/3}\cdot m^{-1/6})$
$\displaystyle\leq\ell(y_{i}\cdot\\{f(\bm{W}^{0},x_{i})+\langle\nabla
f(\bm{W}^{0},x_{i}),\bm{W}^{*}-\bm{W}^{0}\rangle\\})$ $\displaystyle+R^{2}/n$
$\displaystyle\leq\ell(\log(1/[exp(n^{-1})-1]))+R^{2}/n,$ $\displaystyle\leq
n^{-1}+R^{2}/n.$

Thus $L_{i}(\bm{W}^{*})\leq\frac{1+R^{2}}{n}$. $\blacksquare$

Then Theorem 3 follows from Lemma 14 and 15.

##  Appendix E Forward Correlation: Proof of Theorem 5

###### Theorem 16

Consider equation
$h^{\prime}_{l}(x_{1})=\phi(\bm{W}_{l}h^{\prime}_{l-1}(x_{l})+\bm{A}_{l}X_{l})$,
where the entries of $\bm{W}^{l}$ and $\bm{A}^{l}$ are i.i.d. generated from
$N(0,\frac{2}{m})$ and $N(0,\frac{2}{L^{3}m})$. $\bm{W}^{l}$, $\bm{A}^{l}$ and
$\bm{W}^{l^{\prime}}$, $\bm{A}^{l^{\prime}}$ are independent when $l\neq
l^{\prime}$. With probability at lesat $1-L^{2}exp(-\Omega(\log^{2}m))$. For
all $1<l\leq L$, we have

$|h_{l}^{T}(x)h_{l}(x^{\prime})-{h^{\prime}_{l}}^{T}(x)h^{\prime}_{l}(x^{\prime})|\leq\mathcal{O}(L^{2}\log^{2}m/\sqrt{m})$
(68)

for $x,x^{\prime}=x_{1},x_{2}$.

In order to prove the theorem, firstly we claim that

###### Lemma 17

Let $h_{l}(x)=\phi(\bm{W}h_{l-1}(x)+\bm{A}X_{l})$.
$\widetilde{h}_{l}(x)=\phi(\widetilde{\bm{W}}\widetilde{h}_{l-1}(x)+\widetilde{\bm{A}}X_{l})$
is defined by $\widetilde{\bm{W}},\widetilde{\bm{A}}$.
$\widetilde{\bm{W}},\widetilde{\bm{A}}$ and $\bm{W},\bm{A}$ are i.i.d. Then
for any $0<l,l^{\prime}<L$, with probability at least
$1-L^{2}exp(-\Omega(\log^{2}m))$,

$|h_{l}^{T}(x)h_{l^{\prime}}(x^{\prime})-{\overline{h}_{l}}^{T}(x)\overline{h}_{l^{\prime}}(x^{\prime})|\leq\mathcal{O}(l^{2}\log^{2}m/\sqrt{m})$
(69)

where

$\overline{h}_{l}(x)=\phi(\bm{W}\widetilde{h}_{l-1}(x)+\bm{A}X_{l})$
$\overline{h}_{l^{\prime}}(x^{\prime})=\phi(\bm{W}\widetilde{h}_{l^{\prime}-1}(x^{\prime})+\bm{A}X^{\prime}_{l})$

Proof of Theorem 16:
In the case $l=1$, $h_{1}(x)=\phi(\bm{W}h_{0}+\bm{A}X_{1})$.

From Theorem 9 we have, with probability at least $1-exp(-\Omega(\log^{2}m))$

$h_{1}^{T}(x)h_{1}(x^{\prime})=\mathbb{E}h_{1}^{T}(x)h_{1}(x^{\prime})\pm\mathcal{O}(\log^{2}m/m)={h^{\prime}_{1}}^{T}(x)h^{\prime}_{1}(x^{\prime})\pm\mathcal{O}(\log^{2}m/\sqrt{m})$
(70)

The theorem is true.

Supposing the theorem is true for $l$, for $l+1$, using Lemma 17

$h_{l+1}^{T}(x)h_{1+1}(x^{\prime})=\mathbb{E}\phi(\bm{W}\widetilde{h}_{l}(x^{\prime})+\bm{A}X^{\prime}_{l+1})\phi(\bm{W}\widetilde{h}_{l}(x)+\bm{A}X_{l+1})\pm\mathcal{O}(l^{2}\log^{2}m/\sqrt{m})$
(71)

$\bm{W}\widetilde{h}_{l}(x)+\bm{A}X_{l+1}=\begin{bmatrix}\bm{W}&L^{3/2}\bm{A}\end{bmatrix}\cdot\begin{bmatrix}\widetilde{h}_{l}(x)\\\
\frac{1}{L^{3/2}}X_{l+1}\end{bmatrix}=\bm{M}\cdot z$ (72)

Thus

$\displaystyle\mathbb{E}\phi(\bm{W}\widetilde{h}_{l}(x^{\prime})+\bm{A}X^{\prime}_{l+1})\phi(\bm{W}\widetilde{h}_{l}(x)+\bm{A}X_{l+1})$
(73) $\displaystyle=\mathbb{E}_{w\sim
N(0,\sqrt{2}\bm{I}_{m+d})}\phi(\bm{w}^{T}z)\phi(\bm{w}^{T}z^{\prime})$
$\displaystyle={h^{\prime}_{l+1}}^{T}(x)h^{\prime}_{l+1}(x^{\prime})\pm\mathcal{O}(l^{16}\log^{2}m/\sqrt{m})$
$h_{l+1}^{T}(x)h_{1+1}(x^{\prime})={h^{\prime}_{1+1}}^{T}(x)h^{\prime}_{1+1}(x^{\prime})\pm\mathcal{O}((l+1)^{16}\log^{2}m/\sqrt{m}).$

$\blacksquare$

Proof of Lemma 17:
In the case $l=1$, this is true from Theorem 9.

For $l>1$, We use the Gram-Schmidt orthonormal matrix as Claim B.4 in [Allen-
Zhu et al., 2019c]. let $\bm{U}_{l}\in\mathbb{R}^{m\times 2l}$ denote column
orthonormal matrix using Gram-Schmidt as

$\displaystyle\bm{U}_{l}=GS(h_{1}(x_{1}),h_{1}(x_{2}),...h_{l}(x_{1}),h_{l}(x_{2})).$
(74)

We can write

$\displaystyle
Wh_{l}=WU_{l-1}U_{l-1}^{T}h_{l-1}+W(I-U_{l-1}U_{l-1}^{T})h_{l},$ (75)

and

$\displaystyle h_{l+1}(x)$
$\displaystyle=\phi(WU_{l-1}U_{l-1}^{T}h_{l}+W(I-U_{l-1}U_{l-1}^{T})h_{l}+AX_{l+1})$
(76)

Consider

$\displaystyle h_{l+1}(x_{2})^{T}h_{l+1}(x_{1})=$
$\displaystyle\phi(WU_{l-1}U_{l-1}^{T}h_{l}(x_{2})+W(I-U_{l-1}U_{l-2}^{T})h_{l}(x_{2})+Ax_{2,l+1})^{T}$
(77)
$\displaystyle\cdot\phi(WU_{l-1}U_{l-1}^{T}h_{l}(x_{1})+W(I-U_{l-1}U_{l-1}^{T})h_{l}(x_{1})+Ax_{1,l+1})$

We write $z_{1}=(I-U_{l-1}U_{l-1}^{T})h_{l}(x_{1})$,
$z_{2}=(I-U_{l-1}U_{l-1}^{T})h_{l}(x_{2}).$
$q_{1}=U_{l-1}^{T}h_{l}(x_{1}),q_{2}=U_{l-1}^{T}h_{l}(x_{2})$.

$\displaystyle z_{2}=\frac{\langle z_{1},z_{2}\rangle
z_{1}}{||z_{1}||^{2}}+(I-z_{1}z_{1}^{T}/||z_{1}||^{2})z_{2}$ (78)

Then

$\displaystyle h_{l+1}(x_{2})^{T}h_{l+1}(x_{1})=$
$\displaystyle\phi(WU_{l-1}q_{2}+W\frac{\langle z_{1},z_{2}\rangle
z_{1}}{||z_{1}||^{2}}+W(I-z_{1}z_{1}^{T}/||z_{1}||^{2})z_{2}+Ax_{2,l+1})^{T}$
(79) $\displaystyle\cdot\phi(WU_{l-1}q_{1}+Wz_{1}+Ax_{1,l+1})$

Thus

$\displaystyle h_{l+1}(x_{2})^{T}h_{l+1}(x_{1})=$
$\displaystyle\phi(\begin{bmatrix}M_{1}&M_{2}&M_{3}&M_{4}\end{bmatrix}\cdot\begin{bmatrix}q_{2}\\\
\frac{\langle z_{1},z_{2}\rangle}{||z_{1}||}\\\
||(I-z_{1}z_{1}^{T}/||z_{1}||^{2})z_{2}||\\\ x_{2,l+1}\end{bmatrix})^{T}$ (80)
$\displaystyle\cdot\phi(\begin{bmatrix}M_{1}&M_{2}&M_{3}&M_{4}\end{bmatrix}\cdot\begin{bmatrix}q_{1}\\\
||z_{1}||\\\ 0\\\ x_{1,l+1}\end{bmatrix})$

where

$\begin{bmatrix}M_{1}&M_{2}&M_{3}&M_{4}\end{bmatrix}=\begin{bmatrix}WU_{l-1}&Wz_{1}/||z_{1}||&W(I-z_{1}z_{1}^{T}/||z_{1}||^{2})z_{2}/||(I-z_{1}z_{1}^{T}/||z_{1}||^{2})z_{2}||&A\end{bmatrix}$
(81)

Let

$\displaystyle E_{2}=\begin{bmatrix}q_{2}\\\ \frac{\langle
z_{1},z_{2}\rangle}{||z_{1}||}\\\ ||(I-z_{1}z_{1}^{T}/||z_{1}||^{2})z_{2}||\\\
x_{2,l+1}\end{bmatrix})$ (82) $\displaystyle E_{1}=\begin{bmatrix}q_{1}\\\
||z_{1}||\\\ 0\\\ x_{1,l+1}\end{bmatrix})$

We have $E_{2}^{T}E_{1}=h_{l}(x_{2})^{T}h_{l}(x_{1})+x_{2,l+1}^{T}x_{1,l+1}$.

Using a similar proof as Claim B.4 and Claim B.4 in [Allen-Zhu et al., 2019c],
we have for any $E_{1},E_{2}$, with probability at least
$1-exp(-\Omega(\log^{2}m))$,

$\displaystyle\phi(\begin{bmatrix}M_{1}&M_{2}&M_{3}&M_{4}\end{bmatrix}\cdot
E_{2})^{T}\cdot\phi(\begin{bmatrix}M_{1}&M_{2}&M_{3}&M_{4}\end{bmatrix}\cdot
E_{1})$ (83)
$\displaystyle=\mathbb{E}_{M\sim\mathcal{N}(0,I)}\phi(ME_{2})\phi(ME_{1})\pm\mathcal{O}({l+1})^{2}\frac{\log^{2}m}{\sqrt{m}})$

Thus

$\displaystyle h_{l^{\prime}+1}(x^{\prime})^{T}h_{l+1}(x)$ (84)
$\displaystyle=$
$\displaystyle\overline{h}_{l^{\prime}+1}(x^{\prime})^{T}\overline{h}_{l+1}(x)\pm\mathcal{O}((l+1)^{2}\log^{2}m/\sqrt{m}).$

The theorem follows. $\blacksquare$

Combing above theorems, Theorem 8,9 and 10, we have

###### Lemma 18

Let

$Q_{l}=\sqrt{(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X_{i,k}||^{2})\cdot(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X_{j,k}||^{2})}$
$\Gamma(z)=\frac{\sqrt{1-z^{2}}+(\pi-arccos(z))z}{\pi}$

There exits $K^{l}_{i,j}$ such that with probability at least
$1-L^{2}exp(-\Omega(\log^{2}m))$,

$|h_{l}^{T}(x_{i})h_{l}(x_{j})-K^{l}_{i,j}|\leq\mathcal{O}(\frac{l^{2}\log^{2}m}{\sqrt{m}}).$
(85)

And

$\displaystyle
K^{1}_{i,j}=Q_{1}\cdot\Gamma([1+\frac{1}{L^{3}}X_{i,1}^{T}X_{j,1}]/Q_{1})$
(86) $\displaystyle
K^{l}_{i,j}=Q_{l}\cdot\Gamma(\\{\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}+K^{l-1}_{i,j}\\}/Q_{l})^{r}$

Thus Theorem 5 follows.

##  Appendix F Backward Correlation: Proof of Theorem 6

###### Theorem 19

For $l\neq l^{\prime}$, with probability at least
$1-L^{2}exp(-\Omega(\log^{2}m))$,

$|\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l^{\prime}}(x_{j})\cdot
D_{l^{\prime}}^{\prime}\rangle|\leq\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}}).$
(87)

For $l=l^{\prime}$, with probability at least
$1-L^{2}exp(-\Omega(\log^{2}m))$,

$\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l}(x_{j})\cdot
D_{l}^{\prime}\rangle\succeq\Omega(1/L^{4})\cdot\Sigma(\\{\frac{1}{L^{3}}\langle
X_{i,l},X_{j,l}\rangle+K^{l-1}_{i,j}\\}/Q_{l})\pm\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}}).$
(88)

Proof of (87):

The proof of (87) is almost a line-by-line copy of the proof in section C of
[Allen-Zhu and Li, 2019a], but there are some minor differences.

Let $\zeta_{1},...,\zeta_{m}$ be a random orthonormal basis of
$\mathbb{R}^{m}$. Then divide all the $m$ coordinates into $\sqrt{m}$ chunks
$N_{1},N_{2},...N_{m^{1/2}}$ of the size $N=\sqrt{m}$.

Define

$z_{1,0}=D_{l}\zeta_{1},z^{\prime}_{1,0}=D^{\prime}_{l}\zeta_{1},\ ...\
z_{N,0}=D_{l}\zeta_{N},z^{\prime}_{N,0}=D^{\prime}_{l}\zeta_{N}$ (89)

and

$\displaystyle z_{i,a}=D_{l+a}W\cdots D_{l+1}WD_{l}z_{i,1}$ (90)
$\displaystyle z^{\prime}_{i,a}=D^{\prime}_{l^{\prime}+a}W\cdots
D^{\prime}_{l+1}WD^{\prime}_{l^{\prime}}z^{\prime}_{i,1}$

$Z_{p,a}=GS(h_{1},...,h_{\max(l,l^{\prime})},z_{1,1},...,z_{N,1},z^{\prime}_{1,1},...,z^{\prime}_{N,1},...,z_{1,a},...,z_{p,a},z^{\prime}_{1,a},...,z^{\prime}_{p,a})$
(91)

We claim that, with probability at least $1-L^{2}exp(-\Omega(\log^{2}m))$, for
all $a$,

$||Z_{p,a}^{T}z_{p,a}||\leq\mathcal{O}(\frac{L^{3}\sqrt{N}\log^{3}m}{\sqrt{m}}).$
(92)

When $a=0$,

$Z_{p,0}^{T}z_{p,0}=Z_{p,0}^{T}D_{l}\zeta_{1}$ (93)

With probability at least $1-exp(-\Omega(\log^{2}m))$,

$||Z_{p,0}^{T}z_{p,0}||\leq\mathcal{O}(l\log m/\sqrt{m}).$ (94)

For $a>1$,

$Z_{p,a+1}^{T}z_{p,a+1}=Z_{p,a+1}^{T}D_{l+a+1}(W(I-Z_{p,a+1}Z_{p,a+1}^{T})z_{p,a}+WZ_{p,a+1}Z_{p,a+1}^{T}z_{p,a}),$
(95)
$\displaystyle||Z_{p,a+1}^{T}D_{l+a+1}WZ_{p,a+1}Z_{p,a+1}^{T}z_{p,a})||\leq||D_{l+a+1}WZ_{p,a+1}Z_{p,a+1}^{T}z_{p,a})||$
(96) $\displaystyle\leq||Z_{p,a+1}^{T}z_{p,a})||(1+\frac{1}{50L}),$

The last step is from Lemma 11.

And

$||Z_{p,a+1}^{T}D_{l+a+1}W(I-Z_{p,a+1}Z_{p,a+1}^{T})z_{p,a}||\leq\mathcal{O}(\frac{(l+a)^{3}\sqrt{N}\log^{2}m}{\sqrt{m}}).$
(97)

is because $W(I-Z_{p,a+1}Z_{p,a+1}^{T})z_{p,a}\sim
N(0,(2\bm{I}/m)\cdot||(I-Z_{p,a+1}Z_{p,a+1}^{T})z_{p,a}||^{2})$.

This claim follows that,

$\sum_{p\in[N]}\Xi_{p}=\sum_{p}B^{T}(I-Z_{p,a}Z_{p,a}^{T})z_{p,a}\cdot
B^{T}(I-Z_{p,a^{\prime}}Z_{p,a^{\prime}}^{T})z^{\prime}_{p,a^{\prime}}\pm\mathcal{O}(m^{1/4}L^{3}\log^{4}{m})$
(98)

In the case $a\neq a^{\prime}$, $(I-Z_{p,a}Z_{p,a}^{T})z_{p,a}$ and
$(I-Z_{p,a^{\prime}}Z_{p,a^{\prime}}^{T})z^{\prime}_{p,a^{\prime}}$ are
mutually orthogonal. With probability at least $1-exp(-\Omega(\log^{2}m))$,

$|\sum_{p}B^{T}(I-Z_{p,a}Z_{p,a}^{T})z_{p,a}\cdot
B^{T}(I-Z_{p,a^{\prime}}Z_{p,a^{\prime}}^{T})z^{\prime}_{p,a^{\prime}}|\leq\mathcal{O}(log^{4}m)$
(99)

Thus

$|\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l^{\prime}}(x_{j})\cdot
D_{l^{\prime}}^{\prime}\rangle|\leq\mathcal{O}(\frac{L^{3}\log^{4}m}{m^{1/4}}).$
(100)

There are $\sqrt{m}$ chunks, thus with probability at least
$1-\sqrt{m}L^{2}exp(-\Omega(\log^{2}m))=1-L^{2}exp(-\Omega(\log^{2}m))$. (87)
follows. $\blacksquare$

Proof of (88):

For any $a$, we have,

$z_{p,a+1}=D_{l+a+1}(W(I-Z_{p,a+1}Z_{p,a+1}^{T})z_{p,a}+WZ_{p,a+1}Z_{p,a+1}^{T}z_{p,a})$
(101)

Thus,

$||z_{p,a+1}-D_{l+a+1}W(I-Z_{p,a+1}Z_{p,a+1}^{T})z_{p,a}||\leq\mathcal{O}(\frac{L^{3}\sqrt{N}\log^{3}m}{\sqrt{m}})$
(102)

We know that $\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l}(x_{j})\cdot
D_{l}^{\prime}\rangle=\sum_{i=1}^{m^{1/2}}\Theta_{i}$, where

$\displaystyle\Theta_{i}=\sum_{p\in[N_{i}]}\Xi_{p}=$
$\displaystyle\sum_{p}B^{T}(I-Z_{p,a}Z_{p,a}^{T})D_{l+a}W(I-Z_{p,a}Z_{p,a}^{T})...D_{l+1}W(I-Z_{p,1}Z_{p,1}^{T})z_{p,0}$
(103) $\displaystyle\cdot
B^{T}(I-Z_{p,a}Z_{p,a}^{T})D^{\prime}_{l+a}W(I-Z_{p,a}Z_{p,a}^{T})...D^{\prime}_{l+1}W(I-Z_{p,1}Z_{p,1}^{T})z^{\prime}_{p,0}$
$\displaystyle\pm\mathcal{O}(m^{1/4}L^{3}\log^{4}{m})$

Combine the facts :

  * •

With probability at least $1-exp(-\Omega(\log^{2}m))$,

$\sum_{p}B^{T}z_{p,a}\cdot B^{T}z^{\prime}_{p,a}=\langle
z_{p,a},z^{\prime}_{p,a}\rangle\pm\mathcal{O}(\frac{\sqrt{N}L^{2}\log^{2}m}{\sqrt{m}}).$
(104)

  * •

Let

$\displaystyle D_{l}=\phi(\bm{W}h_{l-1}(x_{l})+\bm{A}X_{l})$ (105)
$\displaystyle\widetilde{D_{l}}=\phi(\bm{W}\widetilde{h}_{l-1}(x_{l})+\bm{A}X_{l})$

where $\widetilde{h}$ is $h_{l}$ define by re-randomization in Lemma 17. Then
$|\langle
D^{\prime}_{l},D_{l}\rangle-\langle\widetilde{D^{\prime}_{l}},\widetilde{D_{l}}\rangle|\leq\mathcal{O}(\frac{L^{2}\log^{2}m}{m})$

  * •

$||Z_{p,a}^{T}z_{p,a}||\leq\mathcal{O}(\frac{L^{3}\sqrt{N}\log^{3}m}{\sqrt{m}}).$
(106)

and Claim F.1. Let
$Q_{l}=\sqrt{(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X_{k}||^{2})\cdot(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X^{\prime}_{k}||^{2})}$.
With probability at least $1-exp(-\Omega(\log^{2}m))$, we have

$\displaystyle\langle z_{p,a},z^{\prime}_{p,a}\rangle=$
$\displaystyle\langle(I-Z_{p,a-1}Z_{p,a-1}^{T})z_{p,a-1},(I-Z_{p,a-1}Z_{p,a-1}^{T})z^{\prime}_{p,a-1}\rangle$
(107)
$\displaystyle\cdot\Sigma(\\{h_{l+a-1}^{T}h^{\prime}_{l+a-1}+\frac{1}{L^{3}}X^{T}_{l+a}X_{l+a}\\}/Q_{l+a})\pm\mathcal{O}(\frac{L^{3}\sqrt{N}\log^{3}m}{\sqrt{m}}),$
$\displaystyle=$
$\displaystyle\langle(z_{p,a-1},z^{\prime}_{p,a-1}\rangle\cdot\Sigma(\langle
h_{l+a-1},h^{\prime}_{l+a-1}\rangle/Q_{l+a}$
$\displaystyle+\frac{1}{L^{3}}\langle
X_{l+a},X^{\prime}_{l+a}\rangle/Q_{l+a})\pm\mathcal{O}(\frac{L^{3}\sqrt{N}\log^{3}m}{\sqrt{m}}),$

where

$\Sigma(x)=\frac{1}{2}+\frac{arcsin(x)}{\pi}=\frac{\pi-arccos(x)}{\pi}.$ (108)

In order to study the constant term in

$\Sigma(\langle
h_{l+a-1},h^{\prime}_{l+a-1}\rangle/Q_{l+a}+\frac{1}{L^{3}}\langle
X_{l+a},X^{\prime}_{l+a}\rangle/Q_{l+a}),$

we need to study$\langle h_{l+a-1},h^{\prime}_{l+a-1}\rangle.$

The constant term in $\langle h_{l+a-1},h^{\prime}_{l+a-1}\rangle/Q_{l+a}$ is
the sequence (Lemma 18):

$\displaystyle K_{l}=\Gamma(K_{l-1}\cdot Q_{l-1}/Q_{l}),$ (109)
$\displaystyle\Gamma(x)=x+\frac{\sqrt{1-x^{2}}-arccos(x)x}{\pi}.$

Note that $K_{l}>0$ is convergent. Meanwhile, the sequence $K^{\prime}_{l}$,

$\displaystyle 0<K^{\prime}_{1}<1,$ (110) $\displaystyle
K^{\prime}_{l}=\Gamma(K^{\prime}_{l-1}),$

is also convergent [Huang et al., 2020]. We have
$\lim_{l\to\infty}K^{\prime}_{l}=\lim_{l\to\infty}K_{l}=1$. The aim of us is
to show $\sum_{l=1}^{L}\sqrt{(1-K_{l})}\leq\mathcal{O}(\log L)$.

Let $e_{l}=1-K_{l}$. Claim F.3 and F.2 below show that
$e_{l}\sim\frac{1}{l^{2}}$ and

The constant term in $\displaystyle\\{\prod_{l=1}^{L}\Sigma(\langle
h_{l-1},h^{\prime}_{l-1}\rangle/Q_{l}+\frac{1}{L^{3}}\langle
X_{l},X^{\prime}_{l}\rangle/Q_{l})\\}\geq\Omega(1/L^{b}).$ (111)

and in this case, $b=3+\frac{\log^{2}L}{L}\leq 4$. Then (88) follows.
$\blacksquare$

###### Claim F.1

Let $D$ and $D^{\prime}$ be diagonal matrix satisfying

$\displaystyle(D)_{k,k}=\mathbbm{1}\\{\bm{W}Y+\bm{A}X>0\\},$ (112)
$\displaystyle(D^{\prime})_{k,k}=\mathbbm{1}\\{\bm{W}Y^{\prime}+\bm{A}X^{\prime}>0\\}.$

If $\langle Y,Z\rangle,\langle Y,Z^{\prime}\rangle=0$,

$\displaystyle\mathbb{E}_{\bm{W},\bm{A}}\langle
D\bm{W}Z,D^{\prime}\bm{W}Z^{\prime}\rangle=$ $\displaystyle
Z^{T}Z^{\prime}\cdot\mathbb{E}_{w\sim N(0,I_{m}),a\sim
N(0,\frac{1}{L^{3}}I_{d})}\langle\phi^{\prime}([w,a]^{T}[Y,X]),\phi^{\prime}([w,a]^{T}[Y^{\prime},X^{\prime}])$
(113) $\displaystyle=$ $\displaystyle
Z^{T}Z^{\prime}\cdot\Sigma(\\{Y^{T}Y^{\prime}+X^{T}X^{\prime}\\}/(||Y||\cdot||Y^{\prime}||+||X||\cdot||X^{\prime}||))$

with $\phi^{\prime}(x)=\sqrt{2}\mathbbm{1}\\{x>0\\}.$

Proof of Claim F.1:
In fact,

$\displaystyle\mathbb{E}_{\bm{W},\bm{A}}\langle
D\bm{W}Z,D^{\prime}\bm{W}Z^{\prime}\rangle=$ $\displaystyle\langle
Z^{\prime},\nabla_{Y^{\prime}}\langle Z,\nabla_{Y}\mathbb{E}_{w\sim
N(0,I_{m}),a\sim N(0,\frac{1}{L^{3}}I_{d})}$ (114)
$\displaystyle\langle\phi([w,a]^{T}[Y,X]),\phi([w,a]^{T}[Y^{\prime},X^{\prime}])\rangle\rangle.$

with $\phi(x)=\sqrt{2}\max(0,x)$. Then (113) is clearly a corollary of (114)
and $\langle Y,Z\rangle,\langle Y,Z^{\prime}\rangle=0$.

###### Claim F.2

Supposing $K_{l}\sim cos[\pi(1-(\frac{l}{l+1})^{b})]+\xi_{l}$,
$\sum_{l=l_{1}}^{L}\sqrt{\xi_{l}}\leq\mathcal{O}(1)$, $b>0$,

$\prod_{l=1}^{L}\frac{\pi-arccos(K_{l})}{\pi}\geq\Omega(exp(-b\log
L))\geq\Omega(L^{-b})$ (115)

Proof:We use the inequality,

$\prod_{l=1}^{L}(1-\frac{b}{l}-\Omega(\sqrt{\xi_{l}}))\geq\Omega(exp(-\sum_{l=1}^{L}\frac{b}{l}-\Omega(\sqrt{\xi_{l}}))).$
(116)

Meanwhile, for harmonic series,

$\sum_{l=1}^{L}\frac{b}{l}=b\log L+b\gamma+O(1/L^{2})$ (117)

where $\gamma\approx 0.57721$ is the Euler- Mascheroni constant. Thus the
claim follows. $\blacksquare$

###### Claim F.3

Let $e_{l}$ satisfy

$\displaystyle e_{l}=\frac{Q_{l-1}}{Q_{l}}e_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}}$
(118)
$\displaystyle-\frac{\sqrt{1-(1-\frac{Q_{l-1}}{Q_{l}}e_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})^{2}}-arccos(\frac{Q_{l-1}}{Q_{l}}e_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}})(1-\frac{Q_{l-1}}{Q_{l}}e_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})}{\pi}.$

For $l,L$ large enough , we have $e_{l}\leq
1-cos[\pi(1-(\frac{l}{l+1})^{3+\frac{\log^{2}L}{L}})]+\xi_{l}$ and
$\sum_{l=l_{1}}^{L}\sqrt{\xi_{l}}\leq\mathcal{O}(1)$.

Before proving this claim, we cite the following lemma in the proof of Lemma
15 in [Huang et al., 2020]:

###### Lemma 20

Let

$z_{l}=1-cos[\pi(1-(\frac{l}{l+1})^{3+\frac{\log^{2}L}{L}})].$ (119)
$z_{l}\geq
z_{l-1}-\frac{\sqrt{1-(1-z_{l-1})^{2}}-arccos(z_{l-1})(1-z_{l-1})}{\pi}+\frac{3\pi^{2}\log^{2}L}{l^{3}L}+\frac{20\pi^{2}}{2l^{4}}$
(120)

Proof of Claim F.3: Firstly, note that from the assumption of $||X_{l}||$, we
have

$\frac{Q_{l}-Q_{l-1}}{Q_{l}}\leq\mathcal{O}(\frac{1}{L^{3}}).$

We will show there exits $q_{l}=z_{l}+\xi_{l}$ such that

$\displaystyle q_{l}\geq$
$\displaystyle\frac{Q_{l-1}}{Q_{l}}q_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}}$ (121)
$\displaystyle-\frac{\sqrt{1-(1-\frac{Q_{l-1}}{Q_{l}}q_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})^{2}}-arccos(\frac{Q_{l-1}}{Q_{l}}q_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}})(1-\frac{Q_{l-1}}{Q_{l}}q_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})}{\pi}.$

Then $e_{l}\leq q_{l}$. The theorem follows.

Let

$\displaystyle\frac{Q_{l}-Q_{l-1}}{Q_{l}}=\epsilon_{l}z_{l-1},$ (122)
$\displaystyle q_{l-1}=(1+\theta_{l})z_{l-1},$
$\displaystyle(1+\theta_{l+1})=\frac{Q_{l}-Q_{l-1}}{Q_{l}}(1+\theta_{l})+\epsilon_{l},$
$\displaystyle\theta_{l_{0}+1}=0.$

Since $z_{l}<1$, $\theta_{l}>0$. And

$\frac{Q_{l-1}}{Q_{l}}q_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}}=(\frac{Q_{l}-Q_{l-1}}{Q_{l}}(1+\theta_{l})+\epsilon_{l})z_{l-1}=(1+\theta_{l+1})z_{l-1}.$

Using Lemma 20, since $\frac{\sqrt{1-z^{2}}-arccos(z)(1-z)}{\pi}\sim
O(z^{3/2}),$ we claim that

$\displaystyle(1+\theta_{l+1})z_{l}\geq$
$\displaystyle(1+\theta_{l+1})z_{l-1}$ (123)
$\displaystyle-\frac{\sqrt{1-(1-(1+\theta_{l})z_{l-1})^{2}}-arccos((1+\theta_{l})z_{l-1})(1-(1+\theta_{l})z_{l-1})}{\pi}$

This is because $\theta_{l}>0$, $(1+\theta_{l})^{3/2}\geq(1+\theta_{l+1})$.
Then we have

$\displaystyle-$
$\displaystyle\frac{\sqrt{1-(1-\frac{Q_{l-1}}{Q_{l}}q_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})^{2}}-arccos(\frac{Q_{l-1}}{Q_{l}}q_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}})(1-\frac{Q_{l-1}}{Q_{l}}q_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})}{\pi}$
(124) $\displaystyle\leq(1+\theta_{l+1})(z_{l}-z_{l-1}).$

Therefore,

$\displaystyle\frac{Q_{l-1}}{Q_{l}}q_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}}-$ (125)
$\displaystyle\frac{\sqrt{1-(1-\frac{Q_{l-1}}{Q_{l}}q_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})^{2}}-arccos(\frac{Q_{l-1}}{Q_{l}}q_{l-1}+\frac{Q_{l}-Q_{l-1}}{Q_{l}})(1-\frac{Q_{l-1}}{Q_{l}}q_{l-1}-\frac{Q_{l}-Q_{l-1}}{Q_{l}})}{\pi}$
$\displaystyle\leq[\frac{Q_{l}-Q_{l-1}}{Q_{l}}](1+\theta_{l})z_{l-1}+\epsilon_{l}z_{l-1}+(1+\theta_{l+1})z_{l}-(1+\theta_{l+1})z_{l-1}$
$\displaystyle=[\frac{Q_{l}-Q_{l-1}}{Q_{l}}(1+\theta_{l})+\epsilon_{l}-(1+\theta_{l+1})]z_{l-1}+[1+\theta_{l+1}]z_{l}$
$\displaystyle=[1+\theta_{l+1}]z_{l}$ $\displaystyle=q_{l}.$

Since

$(1+\theta_{l+1})=\frac{Q_{l}-Q_{l-1}}{Q_{l}}(1+\theta_{l})+\epsilon_{l},$
(126)

we can write

$(1+\theta_{l+1})=1+\sum_{l^{\prime}=l_{0}}^{l}\prod_{j=l^{\prime}}^{l}\frac{Q_{j}-Q_{j-1}}{Q_{j}}\epsilon_{l^{\prime}}.$
(127)

Then

$\displaystyle(1+\theta_{l+1})\leq
1+\mathcal{O}(\sum_{l^{\prime}=l_{0}}^{l}\epsilon_{l^{\prime}})$ (128)

$\displaystyle q_{l}$ $\displaystyle=(1+\theta_{l+1})z_{l}\leq
z_{l}+\mathcal{O}(\sum_{l^{\prime}=l_{0}}^{l}\epsilon_{l^{\prime}}z_{l})$
(129) $\displaystyle\leq
z_{l}+\mathcal{O}(\sum_{l^{\prime}=l_{0}}^{l}\frac{Q_{l^{\prime}}-Q_{l^{\prime}-1}}{Q_{l^{\prime}}}\frac{(l^{\prime})^{2}}{l^{2}})$
$\displaystyle\leq z_{l}+\mathcal{O}(\frac{l}{L^{3}})$

Since

$\sum_{l=1}^{L}\sqrt{\frac{l}{L^{3}}}\leq\mathcal{O}(1),$ (130)

the theorem follows. $\blacksquare$

##  Appendix G Complexity of Functions: Proof of Theorem 4.

In this section, we give the detailed proof of Theorem 4.

###### Lemma 21

Let

$\Sigma(x)=\frac{1}{2}+\frac{arcsin(x)}{\pi}.$ (131)

If $||Z_{i}||,||Z_{j}||\leq\mathcal{O}(1)$, $\mu>1$,

$\Sigma(\\{\mu+\frac{1}{L^{3}}Z_{i}^{T}Z_{j}\\}/Q_{l})\succeq\Omega(\frac{1}{L^{3}})\cdot(\frac{1}{\mathcal{O}(L)})^{k}\cdot\frac{1}{k^{2}}(Z_{i}^{T}Z_{j})^{k}/(||Z_{i}||\cdot
Z_{j}||)^{k}$ (132)

Proof: From the Taylor formula, for all $p\in\mathbb{N}$,

$\displaystyle\Sigma(Z_{i}^{T}Z_{j})\succeq\sum_{p=1}^{\infty}\frac{(Z_{i}^{T}Z_{j})^{2p-1}}{2\pi(2p-1)^{2}}.$
(133)

And

$\displaystyle\Sigma([\mu+\frac{1}{L^{3}}Z_{i}^{T}Z_{j}]/Q_{l})\succeq\sum_{p=1}^{\infty}\frac{(\mu+\frac{1}{L^{3}}Z_{i}^{T}Z_{j})^{2p-1}}{2\pi(2p-1)^{2}\cdot
Q_{l}^{2p-1}}.$ (134)

For any $k\in\mathbb{N}$, the coefficient of $[Z_{i}^{T}Z_{j}/L^{3}]^{k}/$ in
$\Sigma([\mu_{0}+\frac{1}{L^{3}}Z_{i}^{T}Z_{j}]/Q_{l})$ will be larger than
$\frac{a_{k}}{Q_{l}^{k}}$ with

$a_{k}=\sum_{2p-1>k}^{\infty}\frac{1}{2\pi(2p-1)^{2}}\cdot(\frac{\mu}{Q_{l}})^{2p-1-k}\cdot\frac{2p-1\cdot(2p-2)\cdot...\cdot(2p-k)}{k!}$
(135)

Consider

$b_{k}=\sum_{2p-1>k}^{\infty}(\frac{\mu}{Q_{l}})^{(2p-1-k-2)}\cdot\frac{2p-1\cdot(2p-2)\cdot...\cdot(2p-k+2))}{k!}$
(136)

$b_{k}=\Omega((\frac{\mu}{Q_{l}})^{2})\cdot a_{k}$. Let

$f(x)=\frac{1}{1-x^{2}}.$ (137)

Then

$\displaystyle
b_{k}\geq\Omega(|f^{(k-2)}(\frac{\mu}{Q_{l}})|\cdot\frac{1}{k!}$ (138)
$\displaystyle=\frac{(k-2)!}{2\cdot
k!}[\frac{1}{(1-\frac{\mu}{Q_{l}})^{k-1}}+\frac{(-1)^{k-2}}{(1+\frac{\mu}{Q_{l}})^{k-1}}$
$\displaystyle\geq\Omega(\frac{1}{(k-2)\cdot(k-3)}\cdot\frac{Q_{l}^{k-1}}{(Q_{l}-\mu)^{k-1}})$

Thus the coefficient of $(Z_{i}^{T}Z_{j}/L^{3})^{k}$ in
$\Sigma([\mu_{0}+Z_{i}^{T}Z_{j}]/Q_{l})$ will be larger than

$\Omega(\frac{1}{(k-2)\cdot(k-3)}\cdot\frac{Q_{l}^{-1}}{(Q_{l}-\mu)^{k-1}}\frac{Q_{l}^{2}}{\mu^{2}})\geq\Omega(Q_{l}-\mu)\cdot\frac{1}{(Q_{l}-\mu)^{k}\cdot
k^{2}}.$

Since

$\displaystyle 0<C_{1}\leq||X_{l,i}||^{2},||X_{l,j}||^{2}\leq C_{2},$ (139)
$\displaystyle||Z_{i}||^{2}/\sum_{l=1}^{L}||X_{i,l}||^{2}\sim\frac{1}{L},$
$\displaystyle||Z_{j}||^{2}/\sum_{l=1}^{L}||X_{j,l}||^{2}\sim\frac{1}{L}$

and

$Q_{l}=\sqrt{(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X_{i,k}||^{2})\cdot(1+\frac{1}{L^{3}}\sum_{k=1}^{l}||X_{j,k}||^{2})}.$
(140)

We have

$\Sigma(\\{\mu+\frac{1}{L^{3}}Z_{i}^{T}Z_{j}\\}/Q_{l})\succeq\Omega(\frac{1}{L^{3}})\cdot(\frac{1}{\mathcal{O}(L)})^{k}\cdot\frac{1}{k^{2}}(Z_{i}^{T}Z_{j})^{k}/(||Z_{i}||\cdot||Z_{j}||)^{k}.$
(141)

The claim follows. $\blacksquare$

Using this lemma, note that we can write
$[K^{l-1}_{i,j}+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}]/Q_{l}=\frac{\mu+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}+T_{i,j}}{Q_{l}}$
with $T_{i,j}\succeq 0$ where $\mu=1$ is the constant term in $K^{l-1}_{i,j}$
and

$[K^{l-1}_{i,j}+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}+T_{i,j}]/Q_{l}\succeq\frac{\mu+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}}{Q_{l}}.$

We have the following lemma:

###### Lemma 22

Under the condition of Lemma 18, for any $k\in\mathbb{N}$,

$\Sigma(\\{K^{l}_{i,j}+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}\\}/Q_{l})\succeq\Omega(\frac{1}{L^{3}})\cdot(\frac{1}{\mathcal{O}(L)})^{k}\cdot\frac{1}{k^{2}}(X_{i,l}^{T}X_{j,l})^{k}/(||X_{i,l}||\cdot
X_{j,l}||)^{k}.$ (142)

Now we can prove Theorem 4.

###### Theorem 23

Assume there is $\delta\in[0,e^{-1}]$. Let $n$ samples in ${\cal D}$ be
$\\{x_{i},y_{i}\\}_{i=1}^{n}$.
$\widetilde{y}=[F^{*}(x_{1}),F^{*}(x_{2}),...F^{*}(x_{n})]^{T}$. $F^{*}$ is a
function belonging to the concept class (9) or (11) such that $y_{i}\cdot
F^{*}(x_{i})\geq 1$ for all $i$. There exits matrix $\bm{H}^{\infty}$
satisfying:

$\bm{H}+\bm{\epsilon}^{T}\bm{\epsilon}\succeq\bm{H}^{\infty}\text{ with
}||\bm{\epsilon}||_{F}\leq 0.01/\mathcal{O}(\mathscr{C}^{*})$ (143)

and

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(\mathscr{C}^{*}).$
(144)

Proof:

Firstly, using the forward and backward correlation Theorem 5 and Theorem 6,

$\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l}(x_{j})\cdot
D_{l}^{\prime}\rangle\succeq\frac{1}{\mathcal{O}(L^{4})}\Sigma(\\{\frac{1}{L^{3}}\langle
X_{i,l},X_{j,l}\rangle+K^{l-1}_{i,j}\\}/Q_{l})\pm\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}})$
(145)

and

$|\frac{1}{m}\langle\text{Back}_{l}(x_{i})\cdot
D_{l},\text{Back}_{l^{\prime}}(x_{j})\cdot
D_{l^{\prime}}^{\prime}\rangle|\leq\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}}).$
(146)

for $l\neq l^{\prime}$.

Thus

$\displaystyle H_{i,j}=\frac{1}{m}\langle\nabla f(\bm{W},x_{i}),\nabla
f(\bm{W},x_{j})\rangle=$
$\displaystyle\sum_{l=1}^{L}\frac{1}{m}\langle,\text{Back}^{T}_{l}D_{l}\cdot
h_{l}^{T}(x_{i}),\text{Back}^{T}_{l}D_{l}\cdot h_{l}^{T}(x_{j})\rangle$ (147)
$\displaystyle\pm\mathcal{O}(\frac{L^{6}\log^{4}m}{m^{1/4}})$

The closure of multiplication Proposition 2.2 for positive definite function
concludes there exits semi-positive define matrix $\bm{M}$

$H_{i,j}+M_{i,j}\succeq\frac{1}{\mathcal{O}(L^{4})}\Sigma(\\{\frac{1}{L^{3}}\langle
X_{i,l},X_{j,l}\rangle+K^{l-1}_{i,j}\\}/Q_{l}).$ (148)

with $M_{i,j}\leq\mathcal{O}(\frac{L^{6}\log^{2}m}{m^{1/4}})$. Then
$||\bm{M}||_{F}\leq n^{2}\frac{L^{6}\log^{2}m}{m^{1/4}}$. $\bm{M}$ is semi-
positive define, therefore there exits
$\bm{\epsilon}^{T}\bm{\epsilon}=\bm{M}$, $||\bm{\epsilon}||_{F}\leq
0.01/\mathscr{C}^{*}$ by SVD and reshaping since $m>poly(n,\mathscr{C}^{*})$.
Meanwhile let

$\bm{G}=m^{-1/2}\cdot(vec[\nabla f(\bm{W}^{0},x_{1})],vec[\nabla
f(\bm{W}^{0},x_{2})],...vec[\nabla
f(\bm{W}^{0},x_{n})])\in\mathbb{R}^{m^{2}\times n}.$

Since $m^{2}\gg n$, we can set $\bm{\epsilon}$ satisfying
$\bm{\epsilon}^{T}\bm{G}=0$ without changing $\bm{\epsilon^{T}\epsilon}$.

For a function
$\psi(\beta^{T}_{l,r}X_{l}/||X_{l}||)=\sum_{p=1}^{\infty}c_{p}(\beta^{T}_{l,r}X_{l}/||X_{l}||)^{p}$
with $||\beta_{l,r}||\leq 1$, let

$y_{p}=[c_{p}(\beta^{T}_{l,r}X_{1,l}/||X_{1,l}|)^{p},...c_{p}(\beta^{T}_{l,r}X_{n,l}/||X_{n,l}||)^{p}]\in\mathbb{R}^{n}.$
(149)

Using Proposition 2.4, if
$H^{\infty}_{i,j}\succeq\xi_{p}(X_{l,i}^{T}X_{l,j}/(||X_{l,i}||\cdot||X_{l,j}||))^{p}$,

$y_{p}^{T}(\bm{H}^{\infty})^{-1}y_{p}\leq\frac{c^{2}_{p}||\beta^{T}_{l,r}||^{2p}}{\xi_{p}}.$

In our case, from Lemma 22,

$\xi_{p}=\Omega(\frac{1}{L^{4}})\cdot\Omega(\frac{1}{L^{3}})\cdot(\frac{1}{\mathcal{O}(L)})^{p}\cdot\frac{1}{p^{2}}$
(150)

Note that

$y\overset{\text{d}ef}{=}\sum_{p=1}^{\infty}y_{p}=[\psi(\beta^{T}_{l,r}X_{1,l}/||X_{1,l}||),...\psi(\beta^{T}_{l,r}X_{n,l}/||X_{n,l}||)]\in\mathbb{R}^{n}.$

We have

$\sqrt{y^{T}(\bm{H}^{\infty})^{-1}y}\leq\sum_{p}\sqrt{y^{T}_{p}(\bm{H}^{\infty})^{-1}y_{p}}\leq\sum_{p=1}^{\infty}\frac{c_{p}||\beta^{T}_{l,r}||^{p}}{\xi_{p}}.$
(151)

In our case ,

$\frac{1}{\sqrt{\xi_{p}}}\leq O(L^{3.5})\cdot(\mathcal{O}(\sqrt{L}))^{p}\cdot
p.$ (152)

We have

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(\mathscr{C}^{*})$
(153)

for Additive Concept Class (9).

For N-variables Concept Class (11)

$F^{*}(x)=\sum_{r}\psi_{r}(\langle\beta_{r},[X_{l_{1}},...,X_{l_{N}}]\rangle/\sqrt{N}\max||X_{l_{n}}||).$

We rewrite it as

$F^{*}(x)=\sum_{r}\psi_{r}(\langle\beta_{r},[X_{l_{max}},...,X_{l_{max}-N^{\prime}}]\rangle/\sqrt{N}\max||X_{l_{n}}||$
$l_{max}=\max(l_{1},..,l_{N}),N^{\prime}=\max(l_{1},..,l_{N})-\min(l_{1},..,l_{N}).$

Finally we prove that
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(L^{4}\sum_{r}\mathscr{C}_{N}(\psi_{r},\mathcal{O}(\sqrt{L}))$.

Based on the structure of $H^{\infty}$, we have

$H^{\infty}_{i,j}\succeq\frac{1}{\mathcal{O}(L^{4})}\cdot\Sigma(\\{K^{l_{1}}_{i,j}+\frac{1}{L^{3}}X_{i,l_{1}}^{T}X_{j,l_{1}}\\}/Q_{l_{1}})\cdot...\cdot\Sigma(\\{K^{l_{N}}_{i,j}+\frac{1}{L^{3}}X_{i,l_{N}}^{T}X_{j,l_{N}}\\}/Q_{l_{N}}).$

Then we have the follow claim

###### Claim G.1

For any N terms
$X_{i,r_{1}}^{T}X_{j,r_{1}},X_{i,r_{2}}^{T}X_{j,r_{2}}...,X_{i,r_{N}}^{T}X_{j,r_{N}}$,
$r_{max}=\max(r_{1},...r_{N})$, we have

$\displaystyle H^{\infty}_{i,j}$
$\displaystyle\succeq\frac{1}{C_{1}^{N}L^{4}\cdot L^{2N}\cdot
C_{N,p}\cdot(p/N)^{2N}}$ (154)
$\displaystyle\cdot(X_{i,r_{1}}^{T}X_{j,r_{1}}/||X_{i,r_{1}}||\cdot||X_{j,r_{1}}||+X_{i,r_{2}}^{T}X_{j,r_{2}}/||X_{i,r_{2}}||\cdot||X_{j,r_{2}}||...$
$\displaystyle+X_{i,r_{N}}^{T}X_{j,r_{N}}/||X_{i,r_{N}}||\cdot||X_{j,r_{N}}||)^{p}$
$\displaystyle\succeq\frac{1}{C_{1}^{N}L^{4}\cdot L^{2N}\cdot
C_{N,p}\cdot(p/N)^{2N}}$
$\displaystyle\cdot(X_{i,r_{1}}^{T}X_{j,r_{1}}+X_{i,r_{2}}^{T}X_{j,r_{2}}...+X_{i,r_{N}}^{T}X_{j,r_{N}})^{p}/(N\cdot\max_{n}(||X_{i,r_{n}}||)\cdot\max_{n}(||X_{j,r_{n}}||))^{p}$

where $C_{1}$ is a large constant.

which can be deduced from the following facts:

  1. (a)

For $k\in\mathbb{N}$,
$\Sigma(\\{K^{l}_{i,j}+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}\\}/Q_{l})\succeq\Omega(\frac{1}{L^{3}})\cdot(\frac{1}{\mathcal{O}(L)})^{k}\cdot\frac{1}{k^{2}}(X_{i,l}^{T}X_{j,l})^{k}/(||X_{i,l}||\cdot
X_{j,l}||)^{k}.$

  2. (b)

For any $n$ integers $n_{1},n_{2},...n_{N}$, with $n_{1}+n_{2}+..+n_{N}=p$,
$C_{N,p}\geq\frac{p!}{n_{1}!n_{2}!...n_{N}!}$ and the largest coefficient of
monomial in $(x_{1}+x_{2}+,..+x_{N})^{2p-1}$ is less than $C_{N,p}$.

  3. (c)

For any $n$ integers $n_{1},n_{2},...n_{N}$, with $n_{1}+n_{2}+..+n_{N}=p$,
$(p/N)^{2N}\geq n^{2}_{1}\cdot...\cdot n^{2}_{N})$.

(b) and (c) are trivial. (a) is from Lemma 22.

Combing these results, polynomial theorem and using a similar argument as
(153), we have

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq
L^{2}\mathcal{O}(1+\sum_{p=1}^{\infty}L^{1.5N}C_{1}^{N}\cdot\sqrt{C_{N,p}}\cdot(p/N)^{N}(\mathcal{O}(\sqrt{L}))^{p}\cdot|c_{p}|.$

Thus
$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(L^{2}\sum_{r}\mathscr{C}_{N}(\psi_{r},1))$.

Finally we prove

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(L^{3}\sum_{r}\mathscr{C}(\psi_{r},2^{l_{0}}\mathcal{O}(\sqrt{L}))).$

Consider

$\displaystyle
K^{1}_{i,j}=Q_{l}\cdot\sum_{r=0}^{\infty}\mu^{2}_{r}(1+\frac{1}{L^{3}}X_{i,1}^{T}X_{j,1}/Q_{l})^{r},$
(155) $\displaystyle
K^{l}_{i,j}=Q_{l}\sum_{r=0}^{\infty}\mu^{2}_{r}(\\{\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}+K^{l-1}_{i,j}\\}/Q_{l})^{r}.$

with
$\mu_{r}=\frac{1}{\sqrt{2\pi}}\int_{0}^{\infty}\sqrt{2}xh_{r}(x)e^{-\frac{x^{2}}{2}}dx$,
$h_{r}(x)=\frac{1}{\sqrt{r!}}(-1)^{r}e^{\frac{x^{2}}{2}}\frac{d^{r}}{dx^{r}}e^{-\frac{x^{2}}{2}}.$
We can rewrite this equation as:

$\displaystyle\overline{K}_{1}=\sum_{r=0}^{\infty}\mu^{2}_{r}(1+\frac{1}{L^{3}}X_{i,1}^{T}X_{j,1}/Q_{1})^{r}=\Gamma([1+\frac{1}{L^{3}}X_{i,1}^{T}X_{j,1}]/Q_{1}),$
(156) $\displaystyle\overline{K}_{l}=\Gamma(\overline{K}_{l-1}\cdot
Q_{l-1}/Q_{l}),$
$\displaystyle\Gamma(x)=x+\frac{\sqrt{1-x^{2}}-arccos(x)x}{\pi}.$

and

$\displaystyle K^{l}_{i,j}=$ $\displaystyle\overline{K}_{l}\cdot Q_{l}$ (157)
$\displaystyle=$ $\displaystyle
Q_{l}\cdot\underbrace{\Gamma\frac{Q_{l-1}}{Q_{l}}\circ...\circ\Gamma\\{\frac{1}{Q_{1}}\cdot(1+\frac{1}{L^{3}}X_{i,1}^{T}X_{j,1})\\}}_{l\
times}.$

Using the fact

$Q_{l}\cdot\prod_{k=k_{0}}^{l}\frac{Q_{l-1}}{Q_{l}}=Q_{k_{0}-1},$ (158)

and

$\nabla_{x}f_{l}\circ f_{l-1}...\circ f_{1}(x)=f_{l}^{\prime}\circ
f^{\prime}_{l-1}...\circ f^{\prime}_{1}(x),$

The linear part in $K^{l}_{i,j}$ is
$\sum_{r=0}^{l-1}\mu_{1}^{2l-2r}\frac{1}{L^{3}}X_{i,r}^{T}X_{j,r}$. Thus

$\displaystyle K^{l}_{i,j}+\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}$ (159)
$\displaystyle\succeq\frac{1}{L^{3}}X_{i,l}^{T}X_{j,l}+\sum_{r=0}^{l-1}\mu_{1}^{2l-2r}\frac{1}{L^{3}}X_{i,r}^{T}X_{j,r}$
$\displaystyle\succeq\mu_{1}^{2l}\sum_{r=1}^{l}\frac{1}{L^{3}}X_{i,r}^{T}X_{j,r}$

with $\mu_{1}^{2}=\frac{1}{2}$.

$||\mu_{1}^{2l}\sum_{r=1}^{l}X_{i,r}^{T}X_{j,r}||\leq\mu_{1}^{2l}\cdot
l\leq\mathcal{O}(1)$. Then from Lemma 21, we have

$H^{\infty}_{i,j}\succeq\Omega(\frac{1}{L^{7}})\cdot(\frac{1}{\mathcal{O}(L)})^{k}\cdot\frac{1}{k^{2}}(Z_{i}^{T}Z_{j})^{k}/(||Z_{i}||\cdot||Z_{j}||\cdot
2^{l})^{k}$ (160)

with $Z_{i}^{T}Z_{j}=\sum_{r=1}^{l}\mu_{1}^{2r}X_{i,r}^{T}X_{j,r}$ and
$||Z_{i}||^{2}=\sum_{r}\mu_{1}^{2r}||X_{i,r}||^{2}$

Therefore

$\sqrt{\widetilde{y}^{T}(\bm{H}^{\infty})^{-1}\widetilde{y}}\leq\mathcal{O}(L^{3.5}\sum_{r}\mathscr{C}(\psi_{r},2^{l_{0}}\mathcal{O}(\sqrt{L})))$

The theorem follows. $\blacksquare$

###### Remark G.1

Based on the previous results, we can generalize the results to the loss with
the form:

$\frac{1}{n}\sum_{i=1}^{n}\sum_{l=1}^{L}\ell(y_{i}\cdot f_{l}(\bm{W},x_{i}))$

with $f_{l}(\bm{W},x)=\bm{B}^{T}h_{l}(x)$ to show for
$\bm{H}^{l}_{i,j}=\langle\nabla f_{l}(\bm{W},x_{i}),\nabla
f_{l}(\bm{W},x_{j})\rangle$, there exits

$\bm{H}^{l}+\bm{\epsilon}^{T}\bm{\epsilon}\succeq(\bm{H}^{l})^{\infty}\text{
with }||\bm{\epsilon}||_{F}\leq
0.01/\sqrt{\widetilde{y}^{T}((\bm{H}^{l})^{\infty})^{-1}\widetilde{y}}$ (161)

In fact we have following two generalization results of previous results which
are in fact already contained in the proof.

Generalization of Lemma 17:

Let
$g_{l}=\phi_{1}(\bm{W}g_{l-1}),h_{l}(x_{1})=\phi_{2}(\bm{W}h_{l-1}(x_{l})+\bm{A}X_{l})$.
$\widetilde{g}_{l}=\phi_{1}(\widetilde{\bm{W}}\widetilde{g}_{l-1})$ and
$\widetilde{h}_{l}(x_{1})=\phi_{1}(\widetilde{\bm{W}}\widetilde{h}_{l-1}(x_{l})+\widetilde{\bm{A}}X_{l})$
are defined by $\widetilde{\bm{W}},\widetilde{\bm{A}}$.
$\widetilde{\bm{W}},\widetilde{\bm{A}}$ and $\bm{W},\bm{A}$ are i.i.d. Then
for any $0<l,l^{\prime}<L$, with probability at least
$1-L^{2}exp(-\Omega(\log^{2}m))$,

$|g_{l}^{T}h_{l^{\prime}}(x^{\prime})-{\overline{g}_{l}}^{T}\overline{h}_{l^{\prime}}(x^{\prime})|\leq\mathcal{O}(L^{2}\log^{2}m/m)$
(162)

where

$\overline{g}_{l}=\phi_{1}(\bm{W}\widetilde{g}_{l-1})$
$\overline{h}_{l^{\prime}}(x_{1})=\phi_{2}(\bm{W}\widetilde{h}_{l^{\prime}-1}(x_{l})+\bm{A}X_{l})$

Let $\phi_{1}(x)=x,\phi_{2}(x)=max(x,0)$. One corollary of this result is that
from (4.2) in [Allen-Zhu et al., 2019c], there exits $g_{l}$, such that
$\langle g_{l},h_{l^{\prime}}\rangle\geq 1/poly(L)$ when $l=l^{\prime}$. Else
$\langle g_{l},h_{l^{\prime}}\rangle=0$.

Generalization of Theorem 19:

With probabiluty at least $1-L^{2}exp(-\Omega(\log^{2}m))$,

$|\frac{1}{m}\langle BD_{l_{1}}W\cdots
D_{l+1}WD_{l},BD^{\prime}_{l_{2}}W\cdots
D^{\prime}_{l+1}WD^{\prime}_{l}\rangle|\leq\mathcal{O}(\frac{L^{4}\log^{4}m}{m^{1/4}}).$
(163)

if $l_{1}\neq l_{2}$.

Then we can show there exits $w^{*}_{a}$ with
$||w^{*}_{a}||\leq\mathscr{C}(F_{a}^{*})$. for $a=1,2...L$ with

$\frac{1}{\sqrt{m}}\langle\nabla_{\widetilde{W}}f_{a}(\widetilde{\bm{W}},x_{i}),w^{*}_{a}\rangle=\frac{1}{m}\sum_{l}\langle
BD_{a}W\cdots D_{l+1}WD_{l},w^{*}_{a,back}\rangle\cdot\langle
h_{l}(x_{i}),g_{a}\rangle=F^{*}_{a}(x_{i})+\epsilon$ (164)

and

$|\frac{1}{\sqrt{m}}\langle\nabla_{\widetilde{W}}f_{a^{\prime}}(\widetilde{\bm{W}},x_{i}),w^{*}_{a}\rangle=|\frac{1}{m}\sum_{l}\langle
BD_{a^{\prime}}W\cdots D_{l+1}WD_{l},w^{*}_{a,back}\rangle\cdot\langle
h_{l}(x_{i}),g_{a}\rangle|\leq\epsilon$ (165)

when $a\neq a^{\prime}$.

Here $w^{*}_{a,back}$ is from the SVD of matrix

$\frac{1}{m}\langle BD_{l_{1}}W\cdots D_{l+1}WD_{l},BD^{\prime}_{l_{2}}W\cdots
D^{\prime}_{l+1}WD^{\prime}_{l}\rangle.$

as (65) in the proof of Lemma 15.