On the Provable Generalization of Recurrent Neural Networks
Authors: Lifu Wang
Bo Shen
Bo Hu
Xing Cao
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning Theory
Deep Learning Theory
Over-parametrized Neural Network
Neural Tangent Kernel

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) 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_lX_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) 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$.


On the Provable Generalization of Recurrent Neural Networks
Lifu Wang
Bo Shen" Beijing Jiaotong University bshen tu. edu. en
Bo Hu
Beijing Jiaotong University Lifu Lifu_ Wangebj tu. edu. en
Beijing Jiaotong University hubo2018@bj tu. edu,
Xing Cao
Beijing Jiaotong University caoxingobjtu edu.
Abstract
Recurrent Neural Network (RNN) is a fundamental structure in deep learning. Recently, some works study the training process of over perrpaaamtterized neural networks, and show that over-parameterized networks can learn functions in some notable concept classes with 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) For RNN with input sequence (X1, X2, XL), previous works study to Iearn functions that are summation of f(3) Xt) and require normalized conditions that ||x||| I with some very small depending on the complexity of f- In this paper, using detailed analysis about the neural tangent kernel matrix, prove generalization error bound to learn such functions without normalized conditions and show that some notable concept classes are learn- able with the numbers of iterations and samples scaling cimoss--olynommilly in the input length L.
(2) Moreover, we prove a novel result to learn N-variables functions of input sequence with the form f(3 .X.,...., J). which do not belong to the "additive" concept class, i.e., the summation of function f(X)). And we show that when either N or lo max(11.... (x) min(11.... (N) is small, [Xi, Xly]) will be learnable with the number iterations and samples scaling almost-polynomially in the input length I..
1 Introduction
In Deep Learning. the recurrent neural network (RNN) is well- known as one of the most popular models 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 input sequence x (X1, X,....,Xx.). RNN with the form
hx(x) = 6WWhhWWhh1 + AX)),
(I)
"Corresponding Author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is trying to learn functions fi(X1, X2....XS as
h1(2) = f1(11) h2(2) = f2(
hr(2) fT.(XI, X2,
Due to the complex nonlinearity, the loss is generally non-convex, and it is very difficult to give theoretical guarantee. Recently, there are some works Allen-Zhu et al. | (2019b); Cao and Gu (2019); Allen-Zhu et al. (2019a); Du et al. (019)); 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:
Multi-layer feed-forward networks Allen-Zhu et al. (2019b); Du el al. (2019) and recurrent neural networks Allen-Zhu al. (2019c) with large hidden size can allain zero training error, regardless of whether the data is properly labeled or randomly labeled.
For multi-layer feed-forward networks, functions with the form F*(x) Een (3. X).X E TR B, E ERd, ing data with provably small generalization error, if ④ is analytic and the "complexity" low enough Allen-Zhu al. (2019a); Arora et al. (2019): Cao and Gu (2019).
&R,,113,1 ||3,11 = 1 are learnable i.e. fitting the train-
The "complexity" " of function de can be measured by matrix derived from the NTK (Neural Tangent Kernel) of the network Arora et al.) (2019) Cao and Gu (2019).
For recurrent neural networks Allen -Zu and Li (0199)) if the imput sequence is normalized, i.e., x = (X1, 12,....... X2),, || ||xi|| = with very small, functions with the form F*(x) = Et- E (B, are learnable, where is the size of matrix W, and = Ei= a,l' 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.
Firstly, for RNNs. the method in Allen-Zhu and Li (2119)) requires a normalized condition for A and X, in I that ||AX||| S c₂ for all < and shows that for a function F* (I)) with the complexity 6,, is learnable with error /36) Thus ||x (or equally, ||A|]) should be very small and the scale is dependent on the complexity of functions. The dependence of |X||| l on E makes the results unrealistic in practice since generally the norm of input will not be so small.
Secondly, the result in Allen-Zhu and Li (2019a) shows that RNNs can learn functions which are the summation of functions like (03 Xi). 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 (xx) is a function of {X1, X2, [.),, J.K. is possible to
go beyond and learn more complex functions?
In order to study these problems, we consider the binary classification problem: for every input 2,, the label (+1 or 1) of z, can be expressed by the sign of a target function F* (xz). We consider Elman recurrent neural networks with ReLU activation
h₂(a) <(Wh AXi)
f(W,z) = BT hz(2)) R.
(3)
x = (X1, X2, X1), X1 E Rdd W E mm
Ae A B TM Φ(z) max
to learn two types of target functions:

---

Additive Concept Class:
(x
thr (8,
1=1
(4)
80
v1rr caat,
N-variables Concept Class:
F (x) = Σ 2 (.,, Xinl)),
(5)
(x)
For these two types of function, we study the following questions:
Can RNN learn additive concept class functions 4 without the normalized condition with reasonable complexity on the sequence size L,?
Can RNN learn functions in N-variables Concept Class (5) which can not be written as the summation f(X)) 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 (Informal) For a function F (X1, X2,..., with the form as in or (). there is
power series named the complexity 6 (FF))
) dependent on the Taylor expansion coefficient in 4
and (5) For (4). '6 (FF)) is almost-polyye cimnost-polynooee polynomial in L. For (5, when N or lo
ma IN).
min( (1y.., IN) small, 6 (FF)) ) admosi-pplynonee
in L. Under this definition of complexity E (F*),
F is learnable using RNN with m hidden nodes and ReLU activation in (3) in ((((FF)))) (2) steps
with ((6(F*)2 samples 2 poly(L, ((F))).
Contribution. We summarize the contributions as follows:
In this paper, prove that RNN without normalized condition can efficiently learn some table concept classes with both time and sample complexity scaling almost polynomially in the input length L.
Our results go beyond the "additive" " concept class. We prove 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, X(to)) are learnable with complexity scaling almost polynomially in the input length T. and correlation distance lo-
Technically, we study the "backward correlation" of RNN network. In RNN case, using crucial observation on the degeneracy of deep network, we show that the "backward corre- lation" I (Back((;)) Back, (x,)) 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 A, B E Rmxn we define (A, = T)(A We define the asymptotic notations O(-), R(-), poly(-) follows. an, bn two sequences. an Obb.)) if lim sup [an/bal < 00, On = ((bb)) ) if lim (an/br. > 0, a, poly(b,,) there is A N that a, O(b,,)) )²) (O), poly(-) are notions which hide the logarithmic factors in (())))))))) 1| and 2l2 denote the 2-norm of matrices. 1|1 denote the 1-norm. || Ilo is the number of non-zero entries.
the Frobenius-norme
For elements Ar.j, Bj,j of symmetric matrix A, B. We abuse the notion Ar, 2 Brg to denote A > B.... A
B is positive semidefinite matrix.

---

2 Preliminaries
2.1 Function Complexity
For a analytic function (x), we can write it as (122) = co + Ei=1 G22.. We define the following notion measure the complexity learn such functions.
(v, - 1+ Σ i- Ja|R'.
(6)
(v, 1+ Σ
L 155 OF
VONs (I/N)) 14//
i=1
where C > 100 is an large absolute constant and CN2, is the largest combination number Ing!..... for ni, ReN > 0, n1 + 122 + N.. = i,
8
Example 2.1 Arora et al. (2019) Consider (b2) = arclan(z/2). Then
121
(b2)
21-1
(8)
2i
i=1
In this case,
(vb1))
Σ i. |a| S 11 Σ 21-21 0(1)
2, C2 Example 2.2 In the case N 2
= (1/2)3 (b2) exp(z)
(10,1) + Σ
2 25 / 5 0(1)
2.2 Concept Class
For the input sequence } we assume Cuann I || S Cmaz. for all S S L and Cman/Cme ~ Co. Under this condition, we consider two types of target functions with the following form: Additive Concept Class.
4
C₁ Wt.
(x)
ΣV
(9)
1=1
Here for all L,,, whr,, analytic and ||3t,1122 1.
We define
L
((F') 3.5
C(vir, CoVL).
(10)
to be the complexity of the target function.
Remark 2.1 If we consider function 33 Xi) and | for all 1, the above complexity will become '6 (τb O(VL)). This is similar with that in Allen-Zhu and Li 2019a) but this complexity requirement is much weaker than that Allen Zhu and L (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)= Σ ((B,,, Xixl)/V max II).
(11)
For all r, (2t, y) is an analytic function ()(xx) cu Dee Gar. Br RAN 1|8,11 1. Let lo = max(11,... .., IN) min(11..... In). We define
((F') min(I.26N (vhr, Co CoVT), 2h CovCo.))))
(12)

---

Remark 2.2 The complexity E. (x(2r, CovL) and E. C( Cov () are exponential in N and lo respectively. And 6 (F") is less or equal than both. Thus if either to N is small, (((") will be polynomial in L.. Especially when N is small(e.g. N=2), even if = I. 1, functions with the form f(3 (Xt, X(+tol) are still learnable with a low complexity.
2.3 Results on Positive Definite Matrices and Functions
We say function .b:.-) IEd x Rd + R is positive definite if for all n E N, any (I1,,.., Ln) C
Rd {cl...., Cn J [ R.
Σ Cecdd(ar 20.
(13)
The following basic properties in chapter 3 of BergJens et al. 1984) are very useful in our proof.
Proposition 2.1 If ((.,)) positive definite function, matrix M E TRux,, fai1, Fn) C TRd,
and Maj Φ(I;, 2z). Then M is a semi-positive definite matrix.
Proposition 2.2 If (1(-:) and Φn (-,-) are positive definite, ((x;, = (11; 02(111 25) is
also positive definite function.
Proposition 2.3 Let ():-)) be positive definite function, and (p(x) Ei=o Gar,, c 2 0. Then
((((;,)) 1) is also positive definite function.
For positive definite matrix M Raxx there is result in Arora et al. 2019).
Proposition 2.4 (Section of Arora et al. (2019).) Let X (I1)...En)) E Raxn and Kp. E Raxn
a matrix with b. = x,). Suppose there is a > 0, such that M 2 a Kp Let
11)",,)".... (8" pn E R". We have v (M) -y S 1181//a.
3 Main Results
Assume there is an unknown data set D fz, y]. The inputs have the form x X2,, e ( ||x||| & O(1) for all < 1 < For every input I,, there a label y/: = =1.
The neural network with input x is
ho(x) = (MM)),
hz(x) = 6WWhy-1- AXI),
(14)
f(W x) BT -B)hz(r).
Here W E mm A E R B, B.Mo E R The entries of Mo. W and A are respectively i.d. generated from N(0,, 2 N(0, 2 and N(0 (.)) The entries of i.id, generated from (0, 1)
The goal of learning RNN is to minimize the population loss:
Ld(W)= = E -Eee))-lly S(W, x));
(15)
by optimizing the empirical loss
1 n E(y f(W, xx)),
Ls(W)
n1 Σ
(16)
using SGD. Here {(x) log(1 + exp( -x)) is the cross-entropy loss. Consider the SGD algorithm on this RNN. Let the complexity 8* of F (.) be defined in (10) and (12). The O-1 error for D is
I.g- (W) = B( ff f(W x)) < 0}. We have:
Theorem 2 Assume there is 8 (0, e ". Supposing for D {z,, ye,. there is function F
belonging to the concept class 111 such that y: F (2x) for all Let W be the output of
5

---

Algorithm 1: Training RNN with SGD
Input: Data set D. learning rate 7)-
The entries of W A are i.i.d. generated from N (0, m) The entries of B are i.i.d. generated from (0. .H).
for / 1,2.3...m do
Randomly sample (I,, we) from the data set D. W' W ww f(W*-1 xz))).
z2)).
end
Algorithm at least
There is parameter m" (n, ö, L, 6")) )- poly(n, 8-1 1 L, 6) such that, with probability
6, if m > m² (n, 6, L). there exits parameter - (1/mm) that satisfies
1
n
D. (w*) S 50 )
+ 0 1og(1/0)
(17)
T2
Remark 3.1 This theorem induces that, to achieve population 0 error( than empirical loss) being less than e, it is enough to train the network using Algorithm with ([[L-66') steps. As defined in section 2./ and 2.2 when N is small, for the two types of concept class, (6*)² is almost-pe poolosstppl 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 DE Ets Elye .x)) with ft(W, B hx(x). This is becuuse the matrix
H WWW 24), VW(W xz))
with different are almost "orthogonal" by similar argument to (6) in Theorem 6 Then RNN can
learn a function Ji = sign( (F((() (x)) with FJ (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 is the following generalization of Corollary 3.10 in Cao and Gu (209)).
Theorem Under the condition of Theorem let n samples in the training be {xi Di 7 (x1), F" (x2),...F* (xa))". (z.))" Let H be a matrix with H = 1h (V w JWW x.), V W J(W, xz))) The entries of W are i.i.d. generated from N0,, 2.. If there is a matrix H R satisfying
H H+e H with |/ellæ I 0.01/0(E"),
(18)
and (H < O there exits m (n, 8-1, L,,,6 = poly(n, 8-1 L, 8*) such that, with probability at least 1 5, if m > m
H (H))
o log(1/))
(w
(19)
Remark 4.1 order show Theorem using this theorem, we need carefully pick out the exponential parts of L. Using the methods in Allen- The et al. al. (209cc) and Cao and Gu (209)) we can
show that m (L. ()T((=>* 2 poly(n, L, Vi" (H v is enough. Vy"
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 (H be. We can show that:
Theorem Under the condition of Theorem with probability at least 1 8, there exits matrix H satisfying (88 and
(20)

---

Theorem Dis a direct corollary of the above two theorems.
4.1
Calculation on Kernel Matrix
The proof of (20) relies direct calculation to construct kernel matrix H We consider two input 2i and J.. Let X,, and X3, be the / th input x, and vy. Let Dr E Rmxm and Dj mm be diagonal matrices that,
(Di)&, 1 (Whh + AX., 0}
(21)
(Df) 1(Wh;-1 AX3, > 0}
Back: = BDtW ... D441,, BD W ... -141 W
(22)
Then
(V (W,,;) W JW (W,)))
(Back)(x;) Di, Backy D/y (11(2;), by (1;))
(23)
Generally Hi, = - ( W (( ;:)): w S(W, rz)) is hard to deal with. However, in the m - oo
limit, we can use some techniques do the calculation.
4.1.1 Forward Correlation
Theorem For fixed i,j. under the condition in Theorem with probability at least 1 exp(-S((log' m)).
[hu(2ss) h((=;) Kig S O log* m/ m/vm)
(24)
And let Qi = (1+ + 1. Ei [x.)) (1+ 1s Ek [1
K3 Q1
13 X1ii,,)\/111'
(25)
KI = Q1
(1
X X1 + K 1/2
3
r=0
In the above equations, H4
1 Jo (2)e 3 dr, (x) = J (-1 c- de
Vaa
4.1.2 Backward Correlation
Theorem For 1 + V. with probability at least - exp(=S2(log> m)),
L log m 1/4
(Back) Di, (ack)((x)) D/,) O
(26)
For 1 = 1', there is Flg that, with probability at least - e.r((- -(log* m)).
L log m m²/4
(Back( Di, Back( Db. Fl, S O
(27)
m
where
arcsin(x)
Σ(x)
(28)
1
Flg 2
Σ({ (X X + 1/Q1)
(29)
K 33
and 0 < <K O(1/LA)

---

We should note that this theorem is one of the key differences between this work and the methods in Allen-Zhaa and Li (219a)) In fact, we must show that there is a constant K K is still positive definite. However, is K large enough thus 1/K poly(T) rather than 1/K S exp( ? This is not trivial question. One can only get K 2 2r using naive estimation. In Allen-Zhu and Li (2019a), ||AXi|| S Ez is required to make sure Back' (a;k)(x;) (x,)) samll. However after k steps of training, we show the approximation error is roughly BackkI [| II) and W |
Remark 4.2
such that ((Back((z)) Back
( ~ (FF)). Thus the dependence of c. on ((FF) 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 (z, ha(2z)/
[[4( will degenerate to 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
2.2
and 2.3
Proposition
2.4 shows that, in order to estimate
(H we need to show
H Ep (X/ X
(30)
with &, > 0 for all P
L. Here X E Raxd [11t X2,1...n..Il and
[x] Xi) Pb, = {
(31)
We will show that, there is matrix 1000 With probability at least - 6, Hig for i,j E [n], and,
H + 0
log" m
m1/4
MR = O(LA) Q 1 7 (Xu, k(5))/11)
(32)
for all I.
Based on 322 we can show the following results:
For all < 1 < L and all k
1 E([K)
1 1 XTx.//1)) = 2( - ) L3
)d_ (x),,,,)))((XXXX,,
((L4)
OLL) 12
(33)
This deduces the complexity for the Additive Concept Class in section
2.1
1H 0(8)).
(34)
As for N-Variables Concept Class,
H z CN LNN CNP (p/N)N
(XT, sr Xim + XT Xj + X Xarx) max([]X max([1X;,) jo. "'
n
n
(35)
with some large constant C > 0. K1,,,X,11 X.t-a). We have:
Meanwhile, for any S L,a < 1, let Zi,a
1 (DiaaZzio /(| Zit,al- 22)*
"
(36)
Then from definition of complexity in section 2.2 and Proposition 2.4 we can prove
(37)
Therefore 20 follows.

---

Dissicusion
In this paper, we use new method to avoid the normalized conditions. The main idea is provide an esitmation for ( in the RNN case directly. However, the value of v ( is only explicitly calculated for the two-layer case in Arora et al. (2199) 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 reduce the RNN case
fL Σ Back 1 (W,,, Ax22X h1-1,
which is similar to summation of I. two-layer networks. And this reduction requires the following operations in Allen-Zhu and Li (2019a):
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) Show the "off-target" Backward Correlation is zero.
3) Estimate the "on target" Backward Correlation by introducing a normalized input sequence x0())
4) Explicitly construct the approximation.
These steps strongly rely on the normalized condition ||x||| <
and this is apparently unrealistic. Instead, we calculate the kernel matrix and we introduce many estimation to avoid this condition.
We should note that this expression
fL Pc Σ Back 1ww 2 h4-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-Zhuu and Li (2019a) is 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 while/Allen and prove N-variable target functions are learnable, while [Allen -hu and Li] (2019a). requires the normalized condition make sure Back Ro Back be roughly constant. This is one the most different parts between this work and Allen-Zhu and Li (2019)).
In our case, since we do no use the normalized condition, we must show the polynomial decay the constant part in Back. As mentioned in Remark 4.2, in our case, it is generally non-trivial to show V -H*) S O(6*) with E polynomial in L. Our methods rely on detailed estimation on degeneracy of long RNN based on Theorem
Related Work
Overparameterized neural network. In Tian (017 and Du et al. (2018). it is shown that, for single-hidden-node ReLU network, under mild assumptions, the loss function is one point convex in very large area. However, in (Sfaran and Shamir (2018), the authors pointed out that such good propertics are rare for networks with multi-hidden nodes, and indicated that an over- paramcterization assumption is necessary. Similarly, Hardt et al. (016)) showed that paramctrrizziiionn can help in the training process of a linear dynamic system i.c., linear RNN. A different way to show over- parameterization important 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 skip connection in Wang et al. (2020) to study the properties loss surfaces.
Recent breakthroughs were made in understanding the neural tangent kernel(NTK) Jacot et al. (2018) Alemohammad al. (20T)) of the neural network near the area of the random initialization. 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 imput 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 veerparrameterizzatoonn 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 Re 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 network with a skip connection. [i et al. (2020) provided 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 [Brtlett 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 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 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-pont poonos--olynomial 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 moonos-polynomilll complexity in input length L. For the N-variable concept class, showed that RNN with ReLU activation function can provably learn functions like (b3 [Xi,.... x)) The complexity of learning such functions grows exponentially with either N or to max(h ... min(I,,...d ....), but when one of them is small, the complexity is plmoss-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 RNN and learn more complex functions using the method in Allen et al. (2019a). Mcanwhile, 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).
10

---

References
Alemohammad, S., Wang. 7., Balestriero, R., and Baraniuk, (2021). The recurrent neural tangent kernel. In International Conference on Learning Representations.
Allen-Zhu, Z. and Li, Y. (2019a). Can sgd learn recurrent neural networks with provable general- ization? Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc.
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, 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, Z.. Li, Y., and Song. (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, Cali- formia, USA, volume 97 of Proceedings of Machine Learning Research, pages
PMLR.
Allen-Zhie 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, 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, Y. and Lee, J. D. (2020). Beyond linearization:
On quadratic and higher-order approximation of wide neural networks. International Conference on Learning Representations.
Bartlett, P. L., Harvey, N., Liaw, C., and Mchrabian, (2019). Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. J. Mach. Learn. Res., 10:63:1- 63:17.
BergJens, C., Reus, P., and Ressel, C. (1984). Harmonic Analysis on Semigroups Theory of Positive Definite and Related Functions. Springer Netherlands.
Bietti, A. and Bach, F. (2021). Deep equals shallow for relu networks in kernel regimes.
Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration inequalities: a non asymptotic theory of independence. Oxford University Press.
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, 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-22144 Curran Associates, Inc.
Chen, Z., Cao, Y., Zou, D., and Gu, Q. (2020b). How much over-paramettrrizaton is sufficient to learn deep relu networks?
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 Gamett, R., editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc.
Du, and Lee, J. D. (2018). On the power of over-parametrization in neural networks with quadratic activation. International conference machine learning, pages 1328-1337.
11

---

Du, S. S.. Lee, J. D., and Tian, Y. (2018). When is convolutional filter easy to learn. International conference on machine learning.
Du, S. S., Zhai, X., Poczos, B., and Singh, A. (2019). Gradient descent provably optimizes over- parameterized neural networks. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net.
Freeman, C. D. and Bruna, J. (2016). Topology and geometry of half-rectified network optimization. International conference machine learning.
Ge, R., Lee, J. D., and Ma. T. (2017). Learning one-hidden-laye layer neural networks with landscape design. CoRR, abs/ 202//711.0000 1.00501.
Hardt, M., Ma, T., and Recht, B. (2016). Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19.
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: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12. 2020, virtual.
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, Z. and Telgarsky. M. (2020). Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.
Li, Y. and Liang, Y. (2018). Learning overparameterized neural networks via stochastic gradient descent 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, Y., Ma, T., and Zhang, H. R. (2020). Learning vver-parametrized two-layer relu neural networks beyond ntk.
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, I. and Shamir, O. (2018). Spurious local minima are common in two-layer relu neural networks. International conference machine learning, pages 4430-4438.
Tian, Y. (2017). Symmetry-breaking convergence analysis of certain two-layered neural networks with relu nonlinearity. International conference on learning representations.
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 the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 2792-2798. International Joint Conferences on Artificial Intelligence Organization. Main track.
Weber, N. C. (1980). A martingale approach central limit theorems for exchangeable random variables. Journal of Applied Probability, 17(3).
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net.
12


Reviews:
[{"review_id": "gj1igX8_oSZ", "reviewer": "Reviewer_Quiy", "summary": "This paper considers when the training data are separable by certain concept class, the generalization of overparameterized RNN trained by SGD. The generalization error depends on a function complexity measure and converges at the rate $1/n$.\n\nThe treatment and results in the paper share the flavor of [Cao and Gu, 2019, Arora et al., 2019, Allen-Zhu et al., 2019]. Several comparisons are made in the paper to justify the contribution: 1) Compared to [Cao and Gu, 2019, Arora et al., 2019], no data distribution assumption is made in the current manuscript; 2) No normalized condition is needed compared to [Allen-Zhu and Li, 2019a].\n\nOrganization of the paper is clear and easy to follow, despite the proof sketch in Section 4.1 reads a bit dense. I appreciate the authors provided a proof road map in supplementary. No experiments are provided, yet the focus is purely on theory.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The following comments may help improve the clarity and significance of the paper:\n\n1) A practical motivation on considering the concept class in the paper is missing. For example, does autoregressive models belong to the concept class. (I feel like they can be described by the N-variables concept class.) These examples may be helpful in explaining the data separation assumption in Theorem 2, as it is rather not a restrictive condition.\n\n2) It is unclear how Theorem 5 and Theorem 6 are applied to deriving Equation (32). Meanwhile, Theorem 5 and 6 themselves may need some high-level explanations and intuitions on why it is true.\n\n3) Technical novelty of the paper should be made more clear. The major contribution is establishing inequality (20). From the current presentation, it is hard to evaluate its difficulty and understand the tools used here.\n\n---------------------- Post Author Response ----------------------------\n\nThe author response clarified most of my concerns. I would like to keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the work is discussed in Section 6. There is no directly foreseeable negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "GlykxOJaFRA", "reviewer": "Reviewer_kie7", "summary": "\nIn this paper, the authors study the type of functions that can be learned with RNNs. They show 2 types of concept classes (additive and N-variables) that can be learned with time and sample complexity almost polynomial in L (input length). For the additive concept class, using the analysis about the NTK of the model they prove the generalization error bound for learnability of such functions without using the normalization condition. Going beyond the additive concept class, they show learnability for N-variable functions with similar guarantees.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe paper considers the problem of providing provable guarantees for the generalization of recurrent neural networks. The result for the additive concept class adds to the earlier work by proving the case without the normalized condition. They also go beyond the additive case and the result for N-variables functions is novel. They clearly state the differences with earlier work. I haven’t gone through every proof in the appendix but I appreciate the flow chart in the beginning. I understand that this is a theoretical paper, however, I believe adding a few numerical experiments would improve the work.\n\nOther comments:\n- Could you clarify if the result holds true for input sequences of arbitrary length?\n- Line 43-46: it is not clear where the terms m and complexity are used.\n- The reference links to different sections and theorems do not work.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed limitations and there is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1yRkc6Z1LmB", "reviewer": "Reviewer_yR1a", "summary": "This paper investigates the learnability of certain types of concept classes via recurrent neural networks. In particular, the authors consider two concept classes: 1) functions that are sums of power series of a linear function of each temporal input and 2) functions that are sums of power series of a linear transformation of the entire temporal sequence. Under suitable conditions, it is proved that these functions can be learned by RNN in polynomial time and sample complexity, and almost polynomial in input sequence length.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the topic of learnability of function(al)s by RNN is a highly relevant topic, I am not sure if the results in this paper contributes to a substantial advancement in this understanding. The biggest issue I see is the lack of motivation of why one would want to consider concept classes introduced in Eq (4) and (5), and in particular why they are interesting generalizations of those considered in earlier works (e.g. [Allen-Zhu and Li, 2019a]). Moreover, the proof techniques appears to be adapted from earlier works. In this sense, I feel that the novelty of the results presented here is quite limited. Below, I list some additional questions/issues:\n\n1. As far as I am aware, ReLU activation is rarely used in RNNs as a recurrent activation, since it only outputs non-negative values. Usually, activations such as $tanh$ is used. How crucially do the current results depend on this assumption? \n2. What is the intuition of the complexity measures in (6) and (7), and what is the relationship between usual Hardy/Bergman spaces and their associated associated norms? It appears to me to be a measure of (generalized) regularity, since it concerns the decay rate of certain series coefficients. The paper would benefit from a discussion of the meaning of the complexity measure introduced.\n3. Algorithm 1: As stated, the matrices $A$ and $B$ appears to be fixed during training. This is different from practical RNN training where these are also weights to be trained. \n\n## Minor Issues\n\nThe paper would benefit from more careful proofreading, as there are many typos and grammatical errors. I list some I have identified below.\n\n1. Page 5 Line 155: the parameters of $m^*$ does not agree with previous line.\n2. Page 5 Line 155: “there exits”\n3. Page 6 Line Remark 3.3: “do not dependent”\n4. Page 6 Line 180: “The really matter thing” - revise sentence\n5. Eq (4): and Eq (5): the RHS should depend on $l,r$ and $r$ respectively\n\n---\n\nAfter rebuttal: I thank the authors for addressing some of the questions. It appears that some of the limitations I pointed out (not training A,B, using ReLU activations) are also assumed in some prior works. While still unrealistic, it is acceptable for the purpose of simplifying analysis to obtain insights. \nI think the paper's novelty can be much better emphasized by building some of the discussion in the authors' reply in the paper itself. In the present form I have reservations to recommend acceptance due to unclear new contributions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents new generalization bounds for RNN. While this paper follows the line of NTK theory, to deal with RNN, this paper proposes new and non-trivial techniques. 
Decision: Accept (Poster)