On the Provable Generalization of Recurrent Neural Networks
Year: 2022

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 = (X1, X2, ..., XL), previous works study to learn functions that are summation of f(β l Xl) and require normalized conditions that ||Xl|| ≤ εwith some very small ε 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(β [Xl1 , ..., XlN ]), which do not belong to the “additive” concept class, i,e., the summation of function f(Xl). And we show that when either N or l0 = max(l1, .., lN ) − min(l1, .., lN ) is small, f(β [Xl1 , ..., XlN ]) will be learnable with the number iterations and samples scaling almost-polynomially in the input length L.

text: 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 = (X1, X2, ..., XL), previous works study to learn functions that are summation of f(βTl Xl) and require normalized conditions that ||Xl|| ≤ ϵwith some very small ϵ 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(βT [Xl1 , ..., XlN ]), which do not belong to the “additive” concept class, i,e., the summation of function f(Xl). And we show that when either N or l0 = max(l1, .., lN ) − min(l1, .., lN ) is small, f(βT [Xl1 , ..., XlN ]) will be learnable with the number iterations and samples scaling almost-polynomially in the input length L.

heading: 1 Introduction
text: 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 = (X1, X2, ..., XL). A RNN with the form
hl(x) = ϕ(Whl−1 +AXl), (1)
∗Corresponding Author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
is trying to learn functions fl(X1, X2, ...Xl) as
h1(x) = f1(X1)
h2(x) = f2(X1, X2)
... hL(x) = fL(X1, X2, ...XL)
(2)
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:
• 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.
• For multi-layer feed-forward networks, functions with the form F ∗(x) =∑C r=1 ϕr(β T r X), X ∈ Rd, βr ∈ Rd, ||βr|| = 1 are learnable i.e. fitting the train-
ing data with a provably small generalization error, if ϕ is analytic and the “complexity” is low enough Allen-Zhu et al. (2019a); Arora et al. (2019); Cao and Gu (2019).
• The “complexity” of function ϕ can be measured by a matrix derived from the NTK (Neural Tangent Kernel) of the network Arora et al. (2019); Cao and Gu (2019).
• For recurrent neural networks Allen-Zhu and Li (2019a), if the input sequence is normalized, i.e., x = (X1, X2, ..., XL), ||X1|| = 1, ||Xl|| = ϵ with ϵ very small, functions with the form F ∗(x) = ∑L l=1 ∑Cl r=1 ϕl,r(β T l,rXl) are learnable, where m is the size of matrix W , and
C = ∑∞
i=0 aiR 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.
• Firstly, for RNNs, the method in Allen-Zhu and Li (2019a) requires a normalized condition for A andXl in (1) that ||AXl|| ≤ ϵx for all l ≤ L and shows that for a function F ∗(x) with the complexity C , it is learnable with error O(ϵ1/3x C ). Thus ||Xl|| (or equally, ||A||) should be very small and the scale is dependent on the complexity of functions. The dependence of ||AXl|| on C 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 ψ(βTl Xl). 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 hL(x) is a function of {X1, X2, ...XL}, 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 xi, the label (+1 or −1) of xi can be expressed by the sign of a target function F ∗(xi). We consider Elman recurrent neural networks with ReLU activation
hl(x) = ϕ(Whl−1 +AXl)
f(W , x) = BThL(x) ∈ R. x = (X1, X2, ..., XL), Xl ∈ Rd,W ∈ Rm×m, A ∈ Rm×d,B ∈ Rm, ϕ(x) = max(x, 0)
(3)
to learn two types of target functions:
• Additive Concept Class:
F ∗(x) = L∑ l=1 ∑ r=1 ψl,r(β T l,rXl/||Xl||),
ψl,r(x) = ∞∑ i=0 cix i,
(4)
• N-variables Concept Class: F ∗(x) = ∑ r ψr(⟨βr, [Xl1 , ..., XlN ]⟩),
ψr(x) = ∞∑ i=0 cix i.
(5)
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 of f(Xl) 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 ∗(X1, X2, ..., XL) with the form as in (4) or (5), there is a power series named the complexity C (F ∗) dependent on the Taylor expansion coefficient in (4) and (5). For (4), C (F ∗) is almost-polynomial in L. For (5), when N or l0 = max(l1, .., lN ) − min(l1, .., lN ) is small, C (F ∗) is almost-polynomial in L. Under this definition of complexity C (F ∗), F ∗ is learnable using RNN with m hidden nodes and ReLU activation in (3) in O(C (F ∗)2) steps with O(C (F ∗)2) samples if m ≥ poly(L,C (F ∗)).
Contribution. We summarize the contributions as follows:
• 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.
• 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(βT [Xl, Xl+l0 ]) ) are learnable with complexity scaling almost polynomially in the input length L and correlation distance l0.
• 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” 1m ⟨Backl(xi),Backl(xj)⟩ 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 ∈ Rm×n, we define ⟨A,B⟩ = Tr(ATB). We define the asymptotic notations O(·),Ω(·), poly(·) as follows. an, bn are two sequences. an = O(bn) if lim supn→∞ |an/bn| < ∞, an = Ω(bn) if lim infn→∞ |an/bn| > 0, an = poly(bn) if there is k ∈ N that an = O((bn)k). Õ(·), Ω̃(·), p̃oly(·) are notions which hide the logarithmic factors in O(·),Ω(·), poly(·). || · || and || · ||2 denote the 2-norm of matrices. || · ||1 denote the 1-norm. || · ||F is the Frobenius-norm. || · ||0 is the number of non-zero entries. For elements Ai.j , Bi,j of symmetric matrix A,B. We abuse the notion Ai.j ⪰ Bi.j to denote A ⪰ B, i.e. A−B is a positive semidefinite matrix.

heading: 2 Preliminaries

heading: 2.1 Function Complexity
text: For a analytic function ψ(z), we can write it as ψ(z) = c0 + ∑∞ i=1 ciz i. We define the following notion to measure the complexity to learn such functions.
C (ψ,R) = 1 + ∞∑ i=1 i · |ci|Ri. (6)
CN (ψ,R) = 1 + ∞∑ i=1 L1.5NCN1 · √ CN,i · (i/N)N · |ci|Ri (7)
where C1 > 100 is an large absolute constant and CN,i is the largest combination number i!n1!n2!...nN ! for n1, n2...nN > 0, n1 + n2 + ...nN = i,
Example 2.1 Arora et al. (2019) Consider ψ(z) = arctan(z/2). Then ψ(z) = ∑ i=1 (−1)i−121−2i 2i− 1 z2i−1 (8)
In this case,
C (ψ, 1) = 1 + ∞∑ i=1 i · |ci| ≤ 1 + ∞∑ i=1 21−2i ≤ O(1).
Example 2.2 In the case N = 2, C2,i = i, (i/2)2 ≤ i2. ψ(z) = exp(z)
C2(ψ, 1) ≤ 1 + ∞∑ i=1 L3C21πi 2.5/i! ≤ O(1)

heading: 2.2 Concept Class
text: For the input sequence {Xl}, we assume Cmin ≤ ||Xl|| ≤ Cmax, for all 1 ≤ l ≤ L and Cmax/Cmin ∼ C0. Under this condition, we consider two types of target functions with the following form: Additive Concept Class.
F ∗(x) = L∑ l=1 Cl∑ r=1 ψl,r(β T l,rXl/||Xl||). (9)
Here for all l, r, ψl,r is analytic and ||βl,r||2 ≤ 1. We define
C (F ∗) = L3.5 L∑
l=1 Cl∑ r=1 C (ψl,r, C0 √ L), (10)
to be the complexity of the target function.
Remark 2.1 If we consider function ψ(βTXl) and ||Xl|| = 1 for all l, the above complexity will become C (ψ,O( √ 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) = ∑ r ψr(⟨βr, [Xl1 , ..., XlN ]⟩/ √ N max ||Xln ||). (11)
For all r, ψl,a,r(x, y) is an analytic function ψr(x) = c0 + ∑∞ i=1 cix i. βr ∈ RdN , ||βr||2 ≤ 1. Let l0 = max(l1, .., lN )−min(l1, .., lN ). We define
C (F ∗) = min(L2CN (ψr, C0 √ L), L3.5C (ψr, 2 l0C0 √ L)). (12)
Remark 2.2 The complexity ∑ r CN (ψr, C0 √ L) and ∑ r C (ψr, 2 l0C0 √ L) are exponential in N and l0 respectively. And C (F ∗) is less or equal than both. Thus if either l0 or N is small, C (F ∗) will be polynomial in L. Especially when N is small(e.g. N=2), even if l0 = L− 1, functions with the form f(βT [Xl, Xl+l0 ]) are still learnable with a low complexity.

heading: 2.3 Results on Positive Definite Matrices and Functions
text: We say a function ϕ(·, ·) : Rd × Rd → R is positive definite if for all n ∈ N, any {x1, ..., xn} ⊆ Rd, {c1, ..., cn} ⊆ R, ∑
i,j
cicjϕ(xi, xj) ≥ 0. (13)
The following basic properties in chapter 3 of BergJens et al. (1984) are very useful in our proof.
Proposition 2.1 If ϕ(·, ·) is positive definite function, let matrix M ∈ Rn×n, {x1, ..., xn} ⊆ Rd, and Mi,j = ϕ(xi, xj). Then M is a semi-positive definite matrix.
Proposition 2.2 If ϕ1(·, ·) and ϕ1(·, ·) are positive definite, ϕ(xi, xj) = ϕ1(xi, xj) · ϕ2(xi, xj) is also a positive definite function.
Proposition 2.3 Let ϕ(·, ·) be a positive definite function, and ψ(x) = ∑∞
i=0 cix i, ci ≥ 0. Then
ψ(ϕ(·, ·)) is also a positive definite function.
For a positive definite matrix M ∈ Rn×n, there is a result in Arora et al. (2019),
Proposition 2.4 (Section E of Arora et al. (2019).) Let X = (x1, ...xn) ∈ Rd×n and Kp ∈ Rn×n is a matrix with (Kp)i,j = (xTi xj)
p. Suppose there is α > 0, such that M ⪰ α2Kp. Let y = ((βTx1) p, ..., (βTxn) p) ∈ Rn. We have √ yT (M)−1y ≤ ||β||p2/α.

heading: 3 Main Results
text: Assume there is an unknown data set D = {x, y}. The inputs have the form x = (X1, X2, ...XL) ∈ (Rd)L. ||Xl|| ≤ O(1) for all 1 ≤ l ≤ L. For every input xi, there is a label yi = ±1. The neural network with input x is
h0(x) = ϕ(M0),
hl(x) = ϕ(Whl−1 +AXl),
f(W , x) = BThL(x).
(14)
Here W ∈ Rm×m,A ∈ Rm×d,B,M0 ∈ Rm. The entries of M0, W and A are respectively i.i.d. generated from N(0, 2m ), N(0, 2 m ) and N(0, 2 L3·m ). The entries of B are i.i.d. generated from N(0, 1m ).
The goal of learning RNN is to minimize the population loss:
LD(W ) = E(x,y)∼Dℓ(y · f(W , x)), (15)
by optimizing the empirical loss
LS(W ) = 1
n n∑ i=1 ℓ(yi · f(W , xi)), (16)
using SGD. Here ℓ(x) = log(1 + exp(−x)) is the cross-entropy loss. Consider the SGD algorithm on this RNN. Let the complexity C ∗ of F ∗(·) be defined in (10) and (12). The 0-1 error for D is L0−1D (W ) = E(x,y)∼D1{y · f(W , x) < 0}. We have:
Theorem 2 Assume there is δ ∈ (0, e−1]. Supposing for D = {xi, yi}, there is a function F ∗ belonging to the concept class (9) or (11) such that yi ·F ∗(xi) ≥ 1 for all i. Let W k be the output of
Algorithm 1: Training RNN with SGD Input: Data set D, learning rate η. The entries of W 0,A are i.i.d. generated from N(0, 2m ). The entries of B are i.i.d. generated
from N(0, 1m ). for t = 1, 2, 3...n do
Randomly sample (xt, yt) from the data set D. W t = W t−1 − η∇W t−1ℓ(yt · f(W t−1, xt)).
end
Algorithm 1. There is a parameterm∗(n, δ, L,C ∗) = poly(n, δ−1, L,C ∗) such that, with probability at least 1− δ, if m > m∗(n, δ, L), there exits parameter η = O(1/m) that satisfies
1
n n∑ k=1 L0−1D (W k) ≤ Õ[ (C ∗)2 n ] +O( log(1/δ) n ). (17)
Remark 3.1 This theorem induces that, to achieve population 0− 1 error(rather than empirical loss) being less than ϵ, it is enough to train the network using Algorithm 1 with Ω̃((L · C ∗)2/ϵ) steps. As defined in section 2.1 and 2.2, when N is small, for the two types of concept class, (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 1 n ∑n i=1 ∑L l=1 ℓ(yi · fl(W , xi)) with fl(W , x) = BThl(x). This is because the matrix
H li,j = 1
m ⟨∇fl(W , xi),∇fl(W , xj)⟩
with different l are almost “orthogonal” by a similar argument to (26) in Theorem 6. Then RNN can learn a function fl = sign(F ∗l (x)) with F ∗ l (x) belonging to functions in section 2.2. See Remark G.1 in the supplementary materials.

heading: 4 Sketch Proof of the Main Theorem
text: 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 {xi, yi}ni=1. ỹ = [F ∗(x1), F ∗(x2), ...F ∗(xn)]
T . Let H be a matrix with Hi,j = 1m ⟨∇W̃ f(W̃ , xi),∇W̃ f(W̃ , xj)⟩. The entries of W̃ are i.i.d. generated from N(0, 2m ). If there is a matrix H ∞ ∈ Rn×n satisfying
H + ϵT ϵ ⪰ H∞ with ||ϵ||F ≤ 0.01/O(C ∗), (18) and √ ỹT (H∞)−1ỹ ≤ O(C ∗), there exits m∗(n, δ−1, L,C ∗) = poly(n, δ−1, L,C ∗) such that, with probability at least 1− δ, if m > m∗, 1
n n∑ k=1 L0−1D (W k) ≤ Õ[ ỹ T (H∞)−1ỹ n ] +O( log(1/δ) 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, √ ỹT (H∞)−1ỹ) ≥ poly(n,L, √ ỹT (H∞)−1ỹ) is enough. √ ỹT (H∞)−1ỹ 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 √ ỹT (H∞)−1ỹ be. We can show that:
Theorem 4 Under the condition of Theorem 3, with probability at least 1 − δ, there exits matrix H∞ satisfying (18) and √
ỹT (H∞)−1ỹ ≤ O(C ∗). (20)
Theorem 2 is a direct corollary of the above two theorems.

heading: 4.1 Calculation on Kernel Matrix
text: The proof of (20) relies on a direct calculation to construct a kernel matrix H∞. We consider two input xi and xj . LetXi,l andXj,l be the l−th input of xi and xj . LetDl ∈ Rm×m andD′l ∈ Rm×m be diagonal matrices that,
(Dl)k,k = 1{Whl−1(xi) +AXi,l > 0} (D′l)k,k = 1{Whl−1(xj) +AXj,l > 0}
(21)
Backl = BDLW · · ·Dl+1W,Back′l = BD′LW · · ·D′l+1W (22)
Then
1 m ⟨∇ W̃ f(W̃ , xi),∇W̃ f(W̃ , xj)⟩ = 1 m ∑ l,l′ ⟨Backl(xi) ·Dl,Backl′(xj) ·D′l′⟩ · ⟨hl(xi), hl′(xj)⟩
(23) Generally Hi,j = 1m ⟨∇W̃ f(W̃ , xi),∇W̃ f(W̃ , xj)⟩ is hard to deal with. However, in the m→ ∞ limit, we can use some techniques to do the calculation.

heading: 4.1.1 Forward Correlation
text: Theorem 5 For fixed i, j, under the condition in Theorem 3, with probability at least 1 − exp(−Ω(log2m)),
|⟨hl(xi), hl(xj)⟩ −Kli,j | ≤ O(l16 · log 2m/
√ m) (24)
And let Ql = √ (1 + 1L3 ∑l k=1 ||Xi,k||2) · (1 + 1 L3 ∑l k=1 ||Xj,k||2),
K1i,j = Q1 · ∞∑ r=0 µ2r[(1 + 1 L3 XTi,1Xj,1)/Q1] r
Kli,j = Ql · ∞∑ r=0 µ2r({ 1 L3 XTi,lXj,l +K l−1 i,j }/Ql) r
(25)
In the above equations, µr = 1√2π ∫∞ 0 √ 2xhr(x)e − x22 dx, hr(x) = 1√r! (−1) re x2 2 dr dxr e − x22 .

heading: 4.1.2 Backward Correlation
text: Theorem 6 For l ̸= l′, with probability at least 1− exp(−Ω(log2m)),
| 1 m ⟨Backl(xi) ·Dl,Backl′(xj) ·D′l′⟩| ≤ O(
L4 log4m
m1/4 ). (26)
For l = l′, there is F li,j that, with probability at least 1− exp(−Ω(log 2m)),
| 1 m ⟨Backl(xi) ·Dl,Backl(xj) ·D′l′⟩ − F li,j | ≤ O(
L4 log4m
m1/4 ). (27)
where
Σ(x) = 1 2 + arcsin(x) π , (28)
F li,j ⪰ 1 K Σ({ 1 L3 ⟨Xi,l, Xj,l⟩+Kl−1i,j }/Ql). (29)
and 0 < K ≤ O(1/L4).
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 1m ⟨Backl(xi),Backl(xj)⟩ −K is still positive definite. However, is K large enough thus 1/K ≥ poly(L) rather than 1/K ≤ exp(−Ω(L)) ? This is not a trivial question. One can only get K ≥ 1
2L using naive estimation. In Allen-Zhu and Li (2019a), ||AXl|| ≤ ϵx is required to make
sure Back′l = Backl(xi) − Backl(xj) samll. However after k steps of training, we can show the approximation error is roughly O(||Back′||·||W k−W 0||) and ||W k−W 0||F ∼ √ ỹT (H∞)−1ỹ ∼ C (F ∗). Thus the dependence of ϵx on 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 liml→∞ hl(xi)Thl(xj)/(||hl(xi)|| · ||hl(xj ||) will degenerate to a constant function.

heading: 4.1.3 Sketch Proof of Theorem 4
text: 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 √ ỹT (H∞)−1ỹ, we need to show
H∞ ⪰ ξp · (XTl Xl)◦p (30)
with ξp > 0 for all p ∈ N, 1 ≤ l ≤ L. Here Xl ∈ Rn×d = [X1,l, X2,l...Xn,l] and
[(XTl Xl) ◦p]i,j = {XTi,lXj,l}p. (31)
We will show that, there is a matrix H∞. With probability at least 1− δ, Hij = H∞ij ±O( L4 log4 m m1/4 ) for all i, j ∈ [n], and,
H∞i,j ⪰ 1
O(L4) ·QlΣ({
1
L3 ⟨Xi,l, Xj,l⟩+Kl−1i,j }/Ql). (32)
for all l.
Based on (32), we can show the following results:
For all 1 ≤ l ≤ L and all k
H∞i,j ⪰ 1
O(L4) Σ({Kli,j+
1
L3 XTi,lXj,l}/Ql) ⪰ Ω(
1 L7 )·( 1 O(L) )k · 1 k2 (XTi,lXj,l) k/(||Xi,l||·Xj,l||)k.
(33) This deduces the complexity for the Additive Concept Class in section 2.1,√
ỹT (H∞)−1ỹ ≤ O(C ∗). (34)
As for N-Variables Concept Class,
H∞i,j ⪰ 1
CN1 L 4 · L2N · CN,p · (p/N)N
· (XTi,r1Xj,r1 +X T i,r2Xj,r2 ...+X T i,rNXj,rN ) p/(N ·max n (||Xi,rn ||) ·max n (||Xj,rn ||))p
(35) with some large constant C1 > 0. Meanwhile, for any l ≤ L, a < l, let Zi,l,a = [Xi,l, Xi,l−1, ...Xi,l−a]. We have:
H∞i,j ⪰ Ω( 1 L7 ) · ( 1 O(L) )k · 1 k2 (ZTi,l,aZj,l,a) k/(||Zi,l,a|| · Zj,l,a|| · 2a)k (36)
Then from definition of complexity in section 2.2 and Proposition 2.4, we can prove√ ỹT (H∞)−1ỹ ≤ O(C ∗). (37)
Therefore (20) follows.

heading: 5 Dissicusion
text: In this paper, we use a new method to avoid the normalized conditions. The main idea is to provide an esitmation for √ ỹT (H∞)−1ỹ in the RNN case directly. However, the value of √ ỹT (H∞)−1ỹ 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 fL ≈ ∑ l Back(0) · 1⟨W,hl−1⟩+AXl≥0W ∗ · hl−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) 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 x(0). 4) Explicitly construct the approximation.
These steps strongly rely on the normalized condition ||Xl|| ≪ 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 fL ≈ ∑ l Back(0) · 1⟨W,hl−1⟩+AXl≥0W ∗ · hl−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 Back ≈ 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√ ỹT (H∞)−1ỹ ≤ O(C ∗) with C ∗ polynomial in L. Our methods rely on a detailed estimation on the degeneracy of long RNN based on Theorem 5.

heading: 6 Related Work
text: 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 overparameterization 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 VCdimension 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).

heading: 7 Conclusion and Future Work
text: 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 ψ(⟨β, [Xl1 , ..., XlN ]⟩). The complexity of learning such functions grows exponentially with either N or l0 = max(l1, ...lN )−min(l1, ...lN ), 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.

heading: Acknowledgement
text: 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).

Review summaries:
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$.  The 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].  Organization 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.

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.

 In 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.