Learning and Generalization in RNNs
Authors: Abhishek Panigrahi
Navin Goyal
Venue: NeurIPS 2021 Poster (2021)
Keywords: Recurrent Neural Networks
Generalization
Overparametrized Neural Networks
Optimization

Abstract: Simple recurrent neural networks (RNNs) and their more advanced cousins LSTMs etc. have been very successful in sequence modeling. Their theoretical understanding, however, is lacking and has not kept pace with the progress for feedforward networks, where a reasonably complete understanding in the special case of highly overparametrized one-hidden-layer networks has emerged. In this paper, we make progress towards remedying this situation by proving that RNNs can learn functions of sequences. In contrast to the previous work that could only deal with functions of sequences that are sums of functions of individual tokens in the sequence, we allow general functions. Conceptually and technically, we introduce new ideas which enable us to extract information from the hidden state of the RNN in our proofs---addressing a crucial weakness in previous work. We illustrate our results on some regular language recognition problems.

Learning and Generalization in RNNs
Abhishek Panigrahi Department Computer Science
Navin Goyal Microsoft Research India navingo@micrros crosoft. com
Princeton University ap34@princeton.er edu
Abstract
Simple recurrent neural networks (RNNs) and their more advanced cousins LSTMs etc. have been very successful sequence modeling. Their theoretical understand- ing, however, is lacking and has not kept pace with the progress for feedforward networks, where reasonably complete understanding in the special case of highly overparameterized nee-hidden-layer networks has emerged. In this paper, progress towards remedying this situation by proving that RNNs can learn functions of sequences. In contrast to the previous work that could only deal with functions of sequences that are sums of functions of individual tokens in the sequence, we allow general functions. Conceptually and technically, which enable us to extract information from the hidden state of the RNN in our proofs-addrese addressing a crucial weakness in previous work. We illustrate our results on some regular language recognition problems.
make
introduce new ideas
Introduction
Simple Recurrent Neural Networks [ also known as Elman RNNs or vanilla RNNs (just RNNs henceforth) along with their more advanced versions such as LSTMs 2 and GRU 3 are among the most successful models for processing sequential data, finding wide-ranging applications including natural language processing, audio processing 4 and time series classification
[5). Feedforward
networks (FFNs) model functions inputs of fixed length, such vectors in Rd. In contrast, RNNs model functions whose input consists of sequences of tokens (1), x²)) ..... where x(1) < Rd for each RNNs have a notion of memory; formally
given by the hidden state vector which is denoted by (() after processing the t-th token. RNNs apply fixed function to (() and (+++1 to compute ((+1) and the output. This fixed function is modeled by neural networks with hidden-layer.
Compared to FFNs, new challenges arise in the analysis of RNNs: for example, the use of memory and the same function each step introduces dependencies across time and RNN training suffers from vanishing and exploding gradients 66].
Studies aimed at understanding the effectiveness of RNNs have been conducted since their intro- duction; for some of the carly work, see, e.g., 7 S. These works take the form of experimental probing of the inner workings of these models as well as theoretical studies. The theoretical studies are often focused on expressibility, training and generalization questions in isolation rather than all together- the latter needs to be addressed approach full understanding of RNNs and appears to be far more challenging. While experimental probing has continued apace, e.g., g 10], progress on theoretical front has been slow. It is only recently that training and generalization addressed in the wake of progress on the relatively easier case of FFNs as discussed next.
starting be
9 well to dynamical systems. With finite precision and ReLU activation, they are equivalent to finite automata [I1] in computational power. In the last few years progress made on theoretical analysis of overparameterized FFNs
RNNs closely related to deterministic finite automata
Work done as a research fellow in Microsoft Research India
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Building upon these techniques, 19 proved that RNNs trained with SGD (stochastic gradient descent) achieve small training loss if the number of neurons is sufficiently large polynomial in the number of training datapoints and the maximum sequence length.
with one-hidden- e.g., 13 IS 16
18
But the gap between our understanding of RNNs and FFNs remains large. 20 21 provide general- ization bounds on RNNs terms of certain norms of the parameters. While interesting, these bounds shed light on only a part of the picture as they do not consider the training of the networks nor do not preclude the possibility that the norms of the parameters for the trained networks are large leading to poor generalization guarantees. RNNs can be viewed as dynamical systems and many works have used this viewpoint to study RNNs, e.g., [22 23 24 25). Other related work includes relation to kernel methods, e.g., [26] [7 28 linear RNNs 29 saturated RNNs [3) BT [2], and echo state
27
networks 33 34
Several other works talk about the expressive power the novel sequence to
sequence models Transformers 36 Due to large number of works in this area it is not possible
to be exhaustive: apart from the references directly relevant to our work we have only been able to include small subset.
37 gave the first "end-to-end" result for RNNs. Very informally, their result is: if the concept class consists of functions that are sums of functions of tokens then overparameterized RNNs trained using SGD with sufficiently small learning rate can learn such a concept class. They introduce new technical ideas, most notably what they call re-radomization which allows one to tackle the dependencies that arise because the same weights are used in RNN across time. However, an important shortcoming of their result is limited expressive power of their concept class: while this class can be surprisingly useful as noted there, cannot capture problems where the RNN needs to make use of the information in the past tokens when processing token (in their terminolgy. their concept class can adapt to time but not to tokens). Indeed, a key step in their proof shows that RNNs can learn to ignore the hidden state (t). (The above concept class comes up because can be learnt even if ((() is ignored.) But the hidden state (1) is the hallmark of RNNs and is the source of information about the past tokens in general, not something to be ignored. Thus, it is an important question to theoretically analyze RNNs' performance on general concept classes and it was also raised in (37). This question is addressed in the present paper. As in previous work, we work with sequences of bounded length L.
Without loss of generality, we work with token sequences x(!) ,.,, (1,) of fixed length as opposed sequences of length up to L. Informally, our result is:
Overparameterized RNNs can efficiently learn concept classes consisting of one-hidden-layer neural networks that take the entire sequence of tokens as input. The training algorithm used is SGD with sufficiently small step size.
By the universality theorem for one-hidden-layee layer networks, such RNNs can approximate all continu- ous functions of (1)),..., ...., thoghthough naturally the more complex the functions in the class the larger the network size required. We note that the above result applies to all three aspects mentioned above: expressive power, training and generalization. We illustrate the power of our result by showing that some regular languages such as PARITY can be recognized efficiently by RNNs.
In concurrent work (38), the authors also study related problems. The results there are not directly comparable: On the one hand, they do not normalize the input unlike our work. On the other hand, the concept classes treated in their work appear to be weak. The authors show that RNNs can learn concept classes that include functions of the form f(x((1) (fx) ..... xx (fxx)), where ei...., Lx e [L]. However, the number of SGD iterations and training samples necessary depend exponentially on the minimum of the two parameters, N and to max(f,..... [N) min(!.....,.. LN).
2 Preliminaries
Let gd-1 == {x E Rdd ||x||2 = 1} be the unit sphere in Rdd For positive integer n define [n] == f1.2...... .n.. Given vector v, by e; we denote its i-th component. Given two vectors E Rdi and b E Rdz, la, b) E Rdd++da denotes the concatenation of the two vectors. (.-) denotes the standard dot product. Given a matrix M, we will denote its i-th row as m, and the element in row i and column j as myj. Given two matrices A ga1x02
X02 and B E B Xba with 0₁ bj let

---

[A, B), E Rai (12+ denote the matrix whose rows are obtained by concatenating the respective rows of A and B. Similarly, [A, B]. E Re +b)]x02 (assuming columns are obtained by concatenating the columns of A and B.
by) denotes the matrix whose
(() and (2(-) hide absolute constants. Similarly, poly(-) denotes a polynomial in its arguments with degree and coefficients bounded by absolute constants; different instances of poly(-) may refer to different polynomials. Writing out explicit constants would lead to unwieldy formulas without any new insights.
Let a: IR - R, given by σ(z) := max (z, 0} = x L.20 be ReLU activation function. ReLU can be extended to act vectors by coordinate-ve application: ((TI1,.... .(a)) == (a( ..... a (za)). Note that ReLU U is a positive homogenous function of degree L, that is to say (Ax)) = A )o(x) for all and all À 0.
To be learnable efficiently, the functions in the concept class need to be not too complex. We will quantify this with the following two complexity measures which are weighted norms of the Taylor expansion and intuitively can be thought of as quantifying network size and sample complexities, resp., needed to learn & up to error E.
Definition 2.1 (Function complexity (15). Suppose that function Φ: b:R.. I has Taylor expansion <(=) =
Di- azz For R, >> 0, define
(C*B))+ (llggteee 0oR) Jea,
Co(o, R) = Ein
C, R) = C' Ee (i 1)1. lal.
where C 10². As an example, if 6(2) 2a for positive integer d. then Co, R) O(R")
and (o, R) = O(RR (R log 1 Co, R) (oly(1/E). We have C, R) S Co R) C, O(R) x (1/y(1/E) for all e and
(2)). For d(2) = sin 2, cos 2, we have Cá R) = O(1) and
for 6(2) = sin 2, ex or constant degree polynomials, they only differ by (11/)). See [5] for details.
Note that @ itself is not member of our concept class but functions like it will be used construct members of our concept class.
Problem Formulation
The data are generated from an unknown distribution D over ((x(2) ..... x((-1)), ),))")))))))))))))) E ((8d-2)L- )), for some label set Y C Rdoot for some positive integer dont- We call x == (x(2) x((-1)) the true sequence and y* the true label. Denote by 2 the training dataset containing N i.i.d. samples from D. We preprocess the true sequence to normalize it:
In our set-up, RNNs output a label after processing the whole input sequence
Definition 3.1 (Normalized Input sequence). Let = (x(2) ..... x( 11-1)) be given true input
sequence of length L 2, s.t.
x()) E g and (1)
1.4 for all i [2, L 1). The normalized
input sequence x = (x) (() is given by
(1) (0d-1 1), x (E (0.0)
VE [2, 1), x(4 -0d-1,10 1).
where we set E. 0 later Theorem
3.1
We use normalized sequence in place of the true sequence as input to RNNs, as helps in proofs, e.g.. with bounds on the changes in the activation patterns at each RNN cell, when the input sequences change and also with inversion of RNNs (defined later). Our method can be applied without normalization too, but in that case our error bound has exponential dependence on the length of the input sequence. The extra dimension the normalized sequence serves as bias which we do not use explicitly to simplify notation.
3.1 RNNs
Definition 3.2 (Recurrent Neural Networks). We assume that the input sequences are of length L for some given L 0 and of the form ()) ....,.(()) with (!) E Rd for all é E [L]. An RNN is
While set-up has similarity previous work 37 there are also important differences.
3

---

specified by three matrices Wen E I Ara E Raxd and Byn R XM, where m is the dimension of the hidden state and dou the dimension of the output. The hidden states of the RNN are given by bean 0 E R and
(0) == (Amma + W Wrnnh/nn for l E [T]. h ron
(1)
The output at each step & E [L] is given by yrnu = Brnn brnn. By RNN cell we mean the underlying FEN in (T. The m rows of W run and Arun correspond to the m neurons in the RNN.
(2)
Pick the matrices W E R and A E Rm by sampling entries i..d. from (0, 2. When W.m = W and Aran A, the RNN is said to be at random initialization. We will denote the parameters of an RNN at initialization by dropping the subscript "rnn", thus the hidden states are (h(") be[[)] In the following theorems, we will keep Bra at initialization B and train only Aran and W rna-
xd by sampling entries i.i.d. from (0, )), and pick B
We write Frum (x; W rmn Arn)) = y rin Bhaa (2) for the output of the ε-th step. Our goal is to use Yrun E Rod to fit the true label y E y using some loss function G RRdo x y - R. We assume that for every y" E y, G (0%, y²)) [-1, 1] is bounded, and G (-,y") is convex and I-Lipschitz continuous in its first variable, This includes, for instance, the cross-entropy loss and l -regression
(8)
loss (for bounded arguments).
3.2 Concept Class
We now define our target concept class, which we will show to be learnable by RNNs using SGD.
Definition 3.3 (Concept Class). Our concept class consists of functions F : (4--))((d-1) - dout detined follows. Let denote set of smooth functions with Taylor expansions with finite complexity as in Def. 2.1 To define a function F, we choose a subset {Ø, : R + Reje[pi from +, (wi,- a set of output coefficients with [6/.ol S 1. Then, we define F -R(L-2)(dd1) - Rdont where for each output dimension s E [dout] we define the s-th coordinate F, of F == (F1,..., Fdom) by
)r(p))eee(douu) a set of weight vectors, and (bf.- E (E))
F,(x)
Σ bt. Pri ((w/,.. (x(22,
(1 (1-1))))
rE(p]
To simplify formulas, assume (0,+(0) for all and s. We denote the complexity of the concept class by
C. ( = max (o, R)), +
= (a RR) Φc
Let F be a function in the concept class with smallest possible population loss which we denote by OPT. Hence, we in agnostic learning setting where aim is to learn function with population objective OPT + E. As one can observe, functions in the concept class are given by one hidden layer network with p neurons and smooth activations. We will show that the complexity of the functions r, determines the number of neurons and the number of training samples necessary to train the recurrent neural network that has OPT E population loss.
While we have defined F* as a function of x, since there's 's one-to-one correspondence between X and x, it will occasionally be convenient to talk about F* being function of x and this should cause no confusion. And similarly for other functions like F(f (x; W, A).
3.3 Objective Function and the Learning Algorithm
We assume that there exists function F* in the concept class that can achieve population loss G(F (x), & OPT. The following loss function is used for gradient descent: (x
OPT, i.e.
Obj(W', A') = E Obj(x, y"; W "')',, where
Obj(x,y; W A') = G(AF(L) Tmn (x: W + W. AA)))"))

---

Parameter À whose value is set in the main Theorem 3.1 is scaling factor needed for technical reasons discussed later. We consider vanilla stochastic gradient updates with W,, A, denoting the matrices after 1-steps of sgd. W, and A, are given by
W, = W 7/ V V. Obj(x, y"; W A, = A - 7 VA., y";; A(-1;
where (x. y*) is random sample from 2 and x is its normalized form. It should be noted that train only W.
Remark. We made two assumptions in our set-up: (1) input sequences of fixed length, and (2) the output is only considered at the last step. These assumptions are without loss generality and allow us keep already quite complex formulas manageable without affecting the essential ideas. The main change needed to drop these assumptions is a change in the objective function, which will now include terms not just for how well the output fits the target step L but also for the earlier steps. The objective function for each step behaves in the same way as that for step L, and so the sum can be analyzed similarly. Intuitively speaking, considering the output at the end is the "hardest" training regime for RNNs as it uses the "minimal" amount of label information.
3.4 RNNs learn the concept class
We are now ready state our main theorem. We use p 100 log m in the following. Recall that a set & of smooth functions induces a concept class as in Def. 3.3
Theorem 3.1 (Main, restated in the appendix as Theorem D.5). Let & a set of smooth functions. For Ez
polyiot and (o, C (1,0 define complexity (D, ((,E and 10Lp' Assume that the number of neurons m poly (C.p, L, dout, E and the number of samples N 2 poly (C.p, L, d Then with parameter choices 1) == θ Ep and
T O poly(p)==3) with probability least 1 - -Q(p)) over the random initialization, SGD satisfies
Σ
W,, Obj Obj(x x,y;; W., W., A.)] OPT + + 1/ poly(p)- t=0 j-D
E
(3)
sgd
Informally, the above theorem states that by SGD training of overparameterized RNNs with suffi- ciently small learning rate and appropriate preprocessing of the input sequence, we can efficiently find an RNN that has population objective nearly as small as OPT as E + 1/ poly(p) small. The required number of neurons and the number of training samples have polynomial dependence on the function complexity of the concept class, the length of the input sequence, the output dimension, and the additional prediction eтror E.
4
Proof Sketch
While the full proof is highly technical, in this section we will sketch the proof focusing on the conceptual aspects while minimizing the technical aspects to the essentials; full proofs are in the appendix. The high-level outline of our proof is as follows.
Overparameterization simplifies the neural network behavior: The function F(L) (x: W W', A + A') computed by the RNN is function of the parameters W', A' well of the input x. It a highly non-linear and non-convex function both the parameters and in the input. The objective function inherits these properties and its direct analysis is difficult. However, it has been realized in the last few years-preddmmen predommnnnii for the FFN setting- that when the network is overparameterized (i.e., as the number of neurons becomes large compared other paramters of the problem such as the complexity of the concept class), the network behavior simplifies in certain sense. The general idea carries over to RNNs well: in (4) below we write the first-order Taylor approximation of F(LL) (x; W + W', + A') at W and A as a linear function of W' and A'; ; it is still non-lincar function of the input
5

---

sequence. As in [3]] we call this function pseudo-network, though our notion is more general as we vary both the parameters W' and A'. Pseudo-network good approximation of the target network as function of x for all x.
2. Existence of good RNN. In order to show that the RNN training successfully learns, we first show that there are parameters values for RNN so that function of x it is good approximation of F*. Instead of doing this directly, we show that the pseudo-network can approximate F*; this suffices as know that the RNN and the pseudo-network remain close. This is done by constructing paramters W and A so that the resulting pseudo-network approximates the target function in the concept class (Section 4.2) for all X.
3. Optimization. SGD makes progress because the loss function is convex in terms of the pseudo-network which stays close to the RNN as a function x. Thus, SGD finds parame- ters with training loss close to that achieved by W A'.
4. Generalization. Apply Rademacher complexity-basee argument to show that SGD has low population loss.
Step 2 is the main novel contribution of our paper and we will give more details of this step in the rest of this section
4.1 Pseudo-network
We define the yseudo-netword here. Suppose W, A, B are at random initialization. The linear term in the first-order Taylor approximation is given by the pseudo-network
F (x: W A')
Back,_, (w'h + AA'(())
(4)
FILL W + W A+'+AA) F(L) (x; W. A). (using Lemma G.3
This function approximates the change in the output of the RNN, when (W, A) changes to (W W', A + A'). The parameter X, that we defined in the objective function, will be used to make the contribution of F(Lt) at initialization small thus making pseudo-network good approximation of RNN. Hence, can observe that the pseudo network is good approximation of the RNN, provided the weights stay close to the initialization.
To complete the above definition of -seudo-network we define the two new notations in the above formula. For each l E [4], define ( E pmxm as a diagonal matrix, with diagonal entries
I[ [[w, (6-1) + a, x 2 0]. Vr [m].
(5)
In words, the diagonal of matrix D represents the activation pattern for the RNN cell at step é at initialization.
Define Back I dout Xm for each 1 isisis by
Backi := BD .......DD
with Back == for each i E [7.]. Matrices Back;- in Eq. (4 arise naturally in the computation of the first-order Taylor approximation (equivalently, gradients w.r.t. the parameters) using standard
matrix calculus. Very roughly, one can think of Back, as related to the backpropagation signal from the output step j to the parameters at step i.
4.2 Existence of good pseudo-network
Our goal is construct W and A such that for any true input sequence (x(22) define the normalized sequence x (x(1) ..... x(()), then with high probability we have
((4-1)), if
F W
'The above outline is similar to prior work, e.g., 37 Details can be quite different though, e.g., they only train W and keep A fixed to its initial value. Their contribution was also mainly in Step 2 and the other steps were similar prior work.

---

To simplify the presentation, in this sketch we will assume that p, the number of neurons in the concept class, and the output dimension dout are both equal 1. Also, let the output weight b := 1. These assumptions retain the main proof ideas while simplifying equations. Overall, we assume that (d-1) (d-11)
the target function F* (2(-2)
+
R on a given sequence is given by
F x
((w),
[x(2),
x()))))),
where 4" IR R is a smooth function and w E 3(
First, we state Lemma 6.2 in 15 which is useful for our construction of the matrices W and A Consider smooth function @: 1,
can be approximated as linear combination of step functions (derivatives of ReLU) for all u E (-,, there exists a "weight function" H IR² - IR such that Φ (u) x Ea, ,1, .ug [ (a1, bu) I fo ( where 01 31 N (0,1) and by N (0, 1) are independent random variables (we omitted some technical details).
The above statement can be straightforwardly extended to the following slightly more general version:
Lemma 4.1. For every smooth function 6, any w E s and any E (0, c. there exists a H R + (-c, (0, 1), (,,1)), which is C. (ő, 1) Lipschhit continuous and for all u E S we have
(o(wTn - W ((w w, bo) WTu+b020]
S.
Very informally, this lemma states that the activation pattern of one-layer ReLU network (given by Tuuo) at initialization can be used to express a smooth function of the dot product the input vector with fixed vector. While the above statement involves expectation, one can easily replace it by an empirical average with slight increase in error. This statement formed the basis for FFN and RNN results in [5 37). Can
it for RNNs for general concept class? An attempt to do so is the following lemma showing that the pseudo-network can express any smooth function of the hidden state h (L-1) and (L).
Lemma 4.2 (Informal). For a given smooth function é, vector w E g(m+d-1), and any e (0, (, there exist matrices W and A such that for every normalized input sequence (x(1) ....,,(()) formed from a sequence x, we have with high probability.
(X W", A") - s((w, (WW,h!/-a) (1 (2.1))) Se.
(L)
provided m = poly(?, L, Co, O()))) Vector (L) x is (L) without the last coordinate, the bias term appended to each input.
The reason (L-1) and (L) come up is because they serve as inputs to the RNN cell when processing the L-th input. The proof sketched below uses the fact that RNNs one-layer FFNs unrolled over time. Hence, we could try to apply the result of Lemma 4.1 to the RNN cell at step L. However, a difficulty arises in carrying out this plan because the contributions of previous times steps also come up (as seen in the equations below) and it can be difficult to disentangle the contribution of step L. This is addressed in the proof:
Proof. Recall that W, A ~ NO, 1). Also, recall that we have assumed for simplicity dout = 1. Hence, B and Back,-,, are row and column vectors respectively. For typographical simplicty, denote by b, and Back;-L.r the respective r-th components of these vectors.
We set W = 0 and for every E [m], at == H, (n/2(([wa 1,,d-1), w)), / /m/ (n/2and)eed for a function H that we will describe below. With these choices we have
FLL) (x; W" A*) =
Back
1=1
b, Back H (V ar, w)), /m am//ardd) Tw, h((-)) (a. +aTx(220
i=1 [m]m]

---

In the last step, we have simplified the formula using sum over neurons. The first L summands in the outer sum above nearly vanish due small correlation between B and Back, - for < (see Lemma F.TTD. Recall that Back = B and thus the correlation is not small for i = L. This gives
p(b) x:
A7)
Σ re(m]
w)), V m/2ar.a) (a]Thh00+aaaxa
m7
Now, this resembles discretized version of Lemma 4.1 Lemma 4.1 and use concentration bounds with respect to the randomness of weights W and A to complete the proof.
We can substitute u as [h (T-1)), x(1) in
More generally, with much more technical work, it might be possible to prove an extension of the above lemma asserting the existence of pseudo- network approximating sum of functions of type
EsE( Φ5 (W.,, ( x)) However, even so it is not at all clear what class of functions of this represents because of the presence of the hidden state vectors.
Thus, the major challenge in constructing W and A to express the functions from the desired concept class is to use the information contained (e), The construction W in [37 is not able to use this information and ignores it by treating it as noise (which is also non-trivial). The idea underlying our construction is that h0) in fact contains information about all the inputs
x()
up until step f. Furthermore and crucially, this information can be recovered approximately by a linear transformation (Theorem 4.5 below). This enables to show:
Theorem 4.3 (Existence of pseudo-network approximation for target function; abridged statement of Theorem D.2 in the appendix). For every target function F* of the form Eq. 7 there exist matrices W and A such that with probability at least 1 - c =Q((p²) over W, A, B. we have for every normalized input sequence x= =xx(", ...., formed from a true sequence x,
[x W A*) x- ((w) [x(2 (...,x(4-3)) x(1 x
1
Set poly(p)
provided m 2 poly(p, L, CD O0= ((==1))) 1)) and c S paty(o)
Proof sketch. By Theorem 4.5 there exists matrix w such that WTL h(6-1) = [x(1),.. ,...,, x(1]
for all input sequences [x(",, ,...,, ((1]. We can modify will) to get [x(2) , ,..,,,((-1)) (11-1)). Hence, by using W/ wi, O] as w and 4- as ò in Lemma 4.2 we can have Fx)) W A") s x ('w(t, WILT (((-)))) Re (x),, implying F(L) and F are close. Accounting for all the er- rors inversion and approximation of function, we get the final bound.
Re-rundomization. In the proof sketches of Lemmas and Theorem above we swept a technical but critical consideration under the rug: the random variables {w,,, Jr]mmm] W(L) [Back;-1.hejp and concentration inequalities w.r.t. the randomness of W and A-this application is required in the proofs. Here our new variation of the re-randomization technique from (37] comes in handy. The basic idea is the following: whenever we want to apply concentration bounds w.r.t. the randomness of W and A, we divide the set of rows into disjoint sets of equal sizes. For each set, we will
are not independent. This invalidates application of standard
re-randomize the rows of the matrix [W, A]r, show that the matrices ! [Back,-z) and (h()) [e] don't 't change lot and then apply concentration bounds w.r.t the new weights in the set. Finally, we account for the error from each set.
4.3 The rest of the proof
Having shown that there exists a psewdo-network approximation of the RNN that can also approx- imate the concept class, we will complete the proof by showing that SGD can find matrices with performance similar to W and A on the population objective Obj(.). Lemma D.3 shows that the training loss decreases with time. The basic idea is to use the fact that within small radius of perturbation, overparameterizee RNNs behave linear network and hence the training can be
8

---

analyzed via convex optimization. Then, we show using Lemma th4t the Rademacher complex- ity for overparameterized RNNs is bounded. Again, the main idea here is that overparameterizee RNNs behave as pseudo-networks in our overparameterized regime and hence their Rademacher complexity can be approximated by the Rademacher complexity of pseudo-networks. Finally, using generalization bounds on the Rademacher complexity, we get the final population-level objective in Theorem D.5
4.4 Invertibility of RNNs at initialization
In this section, we describe how to get back x(1) ,..,, x(L) from the hidden state h(4) The following lemma states that any linear function can be represented by one-hidden layer FFN with activation function Weth, small approximation error of the order
vm
Lemma 4.4. [a simpler continuous version can be found in Lemma C.1 in the appendix] For any Rd, the linear function taking x to v xforx Rd, can be represented
|||||
T x x To- (TX)
(8)
vm
with p 2Tv, where T Rmxd a matrix with elements i.i.d. sampled from N 1).
Using the above lemma we will show that the hidden state (L) can be inverted using matrix will to get back the input sequence x(1)
(())
Theorem 4.5. [informal version of Theorem D.I There exists a set of matrices (w! heety which can possibly depend on W and A, such that for any Ex < t and any given normalized sequence x(1), (L), with probability at least e -Dp(p we have
[|(x(0) _...,,(111___ - IT h S po eea)
Very roughly, the above result is obtained by repeated application of Lemma 4.4 to go from h (c) to (h( x(0) starting with = L. This uses the fact that the RNN cell is a one-hidden layer neural network and hence Lemma 4.4 is applicable. Several difficulties need be overcome carry out this plan.
One difficulty is that naive application of Lemma results in exponential blowup of error with L. The reason is as follows: Lemma 4.4] the factor in the linear transformation p appears because of the activation function ReLU. naive application will result in defining W inductively 2 w A], for 2 < & < L, with Will A. This will lead the approximation error exploding exponentially with L in induction, since the approximation error at each step will depend on the norm of w 1--1
However, one can observe from the proof of Lemma 4.4 that it suffices to use the following linear transformation: p(w) w Il x>0- which helps in removing the factor of 2. However, this requires knowing the indicator function Iw Tx20- This implies for RNNs, we need to know the
indicator matrix ( at each step.
To do so, we define base sequence X(0)- whose indicator matrices {D (8) (0) hEE()) will be used to
approximate the indicator matrix ( at each step E for any sequence x. That is, w will be defined
inductively as [D) ww D (c) A], for 2 < f s L, with Will- D()) A. We then show that the approximation error of the indicator matrix builds up to give an error with polynomial dependence
(0)
on Eg and L. We defer the technical details of this resolution the full proof in the appendix.
Secondly, we apply re-randomization tackle the dependence between W, A, {h(*) Jeelz) and {w Jee[z]. We performed few toy experiments on the ability of invertibility for RNNs at initializa-
*This lemma is from a companion paper (forthcoming) where it used to invert feedforward networks; apart from the above lemma, this work is very different from the present paper. We have reproduced the proof in full in the appendix.

---

tion (Sec. D. We observed, as predicted by our theorem above, that the error involved in inversion decreases with the number of neurons and increases with the length of the sequence (Fig. 4
On concept classes
It is apparent that our concept class very general as allows arbitrary dependencies across tokens. To concretely illustrate the generality of our concept class, and to compare with previous work, we show that our result implies that RNNs can recognize a simple formal language Dz, Here we are working in the discrete setting where each input token comes from {0. 1} possibly represented as vector when fed to the RNN. For a sequence E {0, 1)4, we define Dr, (z) to be if the number of I's in z is exactly 1 and define it to be 0 otherwise. We can show that Dr, is not representable in the concept class of [37] (see Theorem H.T in the appendix). However, we can show that the language DL, can be recognized with one-layer FFN with one neuron and quadratic activation. The idea is that we can simply calculate the number of I's in the input string, which is doable using a single neuron. This implies that our concept class can represent language DL, with low complexity.
More generally, we can show that our concept class can efficiently represent pattern matching problems, where strings belong to language only if they contain given strings as substrings. In general, we can show that our concept class can express general regular languages. However, the complexity of the concept class may depend super-polynomiag depending on the regular language (more discussion in sec. HH.. Some regular languages allow special treatment though. For example, consider the language PARITY. PARITY is the language over alphabet {0. with a string w = (W1,..... wyy) E PARITY iff wi + wy = 1 mod 2, for 2 1. We can show in sec. H that PARITY is easily expressible by our concept class with small complexity. RNNs perform well on regular language recognition task in our experiments in Sec. [] Figuring out which regular languages can be efficiently expressed by concept class remains interesting open problem.
on the length of the input sequence,
Limitations and Conclusions
We proved the first result on the training and generalization of RNNs when the functions in the concept class are allowed to be essentially arbitrary continuous functions of the token sequence. Conceptually the main new idea was to show that the hidden state of the RNN contains information about the whole input sequence and this can be recovered via linear transformation. We believe our techniques can be used to prove similar results for echo state networks.
Two main limitations of the present work are: (1) Our overparameterized setting requires the number of neurons to be large in terms of the problem parameters including the sequence length-and is often qualitatively different from the practical setting. Thcoretical analysis of practical parameter setting remains an outstanding challenge-eve generalization to sequences longer than those in the training data. Such result would be very interesting but it appears that would require stronger assumptions than our very general assumptions about the data distribution. Our techniques might be a useful starting point to that end: for example, we knew that the distributions of the hidden states are similar at different times steps and the output the same the hidden state (i.e. B is the identity) then results might easily generalize higher lengths. We note that to our knowledge the limitation noted here holds for all works dealing with generalization for RNNs. (3) Understanding LSTMs remains open.
for one-hidden layer FFNs. (2) We did not consider
Our work addresses theoretical analysis of RNNs and is not directly concerned with applications. We do not anticipate any immediate societal impact of our work. In the long run, it may help improve RNNs and translate to impact on the applications.
Acknowledgements
We thank Sanjeev Arora, Raghav Somani and Abhishek Shetty for their valuable suggestions on improving the presentation of the paper. We also thank the reviewers, the area chair and the senior area chair for their valuable suggestions regarding this work.
10

---

References
[1] Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):19- 221, 1990.
[2] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 18): 1997.
[3] Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1724-1734, Doha, Qatar, October 2014. Association for Computational Linguistics.
[4] Dan Jurafsky and James H. Martin. Speech and Language Processing, 3rd draft edition, 2020.
[5] Bryan Lim and Stefan Zohren. Time series forecasting with deep learning: A survey, 2020.
[6] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1310-1318, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[7] Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. J. Comput. Syst. Sci.,
1995.
[8] John F Kolen and Stefan Kremer. A field guide to dynamical recurrent networks. John Wiley & Sons, 2001.
[9] Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision mnss for language recognition. In Iryna Gurevych and Yusuke Miyao, editors, Proceed- ings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL. 2018, Melbourne, Australia, July 15-20, 2018, Volume 2: Short Papers, pages 740-745. Association for Computational Linguistics, 2018
[10] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of trans- formers recognize formal languages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing. EMNLP 2020, Online, November 16-20, 2020, pages 7096-7116 Association for Computational Linguistics, 2020.
[11] Samuel A Korsky and Robert C Berwick. On the computational power of rnns. arXiv preprint arXiv:/906.00 06349, 2019.
[12] Arthur Jacot, Clément Hongler, and Franck Gabricl. Neural tangent kernel: Convergence and generalization in neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages 1580, 2018.
[13] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances Neural Information Processing Systems 31, pages 8157-88 077-8666, 1666 2018.
[14] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. Proceedings of the 35th International Conference on Learning Representations, 2018.
[15] Zeyuan Allen -hu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. In Advances in neural information processing systems, pages 6155-6166, 2019.
[16] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109:1-20 03 2020.

---

[17] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-graine grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pages 322-332. PMLR, 2019.
[18] Behrooz Ghorbani, Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-1054 2021.
[19] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In Advances in newral information processing systems, pages 6676-6688, 2019.
[20] Zhuozhuo Tu, Fengxiang He, and Dacheng Tao. Understanding generalization in recurrent neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[21] Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds of family of recur- rent neural networks. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1233-1243. PMLR, 26-28 Aug 2020.
[22] Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. CoRR, (assl/60900191 2016.
[23] John Miller and Moritz Hardt. Stable recurrent models. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019.
[24] Samet Oymak. Stochastic gradient descent learns state equations with nonlinear activations. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2551-2579, Phoenix, USA, 25-28 Jun 2019, PMLR.
[25] Niru Maheswaranathan, Alex H Williams, Matthew D Golub, Surya Ganguli, and David Sussillo. Reverse engineering recurrent networks for sentiment classification reveals line attractor dynamics. Advances in neural information processing systems, 32:15696, 2019.
[26] Greg Yang. Wide feedforward or recurrent neural networks of any architecture are gaussian processes. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9947-9960, 2019.
[27] Sina Alemohammad, Zichao Wang, Randall Balestriero, and Richard Baraniuk. The recurrent neural tangent kernel. In 9th International Conference on Learning Representations, ICLR 2021, 2021.
[28] Sina Alemohammad, Randall Balestriero, Zichao Wang, and Richard Baraniuk. Scalable neural tangent kernel of recurrent architectures. arXiv preprint arXiv:2012.04852 2020.
[29] Melikasadat Emami, Mojtaba Sahrace-Ardakan, Parthe Pandit, Sundeep Rangan, and Alyson K. Fletcher. Implicit bias of linear rnns, 2021.
[30] William Merrill. Sequential neural networks as automata. arXiv preprint arXiv:1906.01613
2019.
[31] William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah Smith, and Eran Yahav. formal hierarchy of mn architectures. arXiv preprint 200.020000008000. 2020.
[32] William Merrill. Formal language theory meets modern nlp. arXiv preprint arXiv:2100 10094,
2021.
12

---

[33] Lyudmila Grigoryeva and Juan-Pablo Ortega. Echo state networks are universal. Neural Networks, 108:495-508 2018.
[34] Mustafa C Ozturk, Dongming Xu, and Jose C Principe. Analysis and design of echo state networks. Neural computation, 19(1): 2007.
[35] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiy Kumar. Are transformers universal approximators of gequence-to-eqqunne functions? arXiv preprint WxXi: 2019.
[36] Chulhee Yun, Yin- Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. o(n) connections are expressive enough: Universal approximability of sparse transformers. arXiv preprint urXiv:2006. 04866, 2020.
[37] Zeyuan Allen-Zhu and Yuanzhi Li. Can sgd learn recurrent neural networks with provable generalization? In Advances in Neural Information Processing Systems, pages 10331-10341, 2019.
[38] Lifu Wang, Bo Shen, Bo Hu, and Xing Cao. On the provable generalization of recurrent neural networks. arXiv preprint arXiv:2109.14142, 2021.
[39] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 101 1011v:1011.3027
2010.
[40] Roman Vershynin. Spectral norm of products of random and deterministic matrices. Probubility theory and related fields, 150(3-45 (0: 2011.
[41] Martin J. Wainwright. High- Digee-Dimesiooal Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[42] S Boucheron, L Gabor, and P Massart. Concentration inequalities oxford university press, 2013.
[43] Roman Vershynin. High- High--Dimessioal Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[44] Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithmss Cambridge university press, 2014.
[45] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-paramettrizztion.. arXiv, pages arXiv-1811, 2018
[46] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):29-681, 2017.
[47] G.G. Lorentz. Approximation of Functions. Holt, Rinehart and Winston, New York, 1966.
[48] Ryan O'Donnell. Analysis of boolean fooleannfunctions Cambridge University Press, 2014.
[49] M. Tomita. Dynamic construction of finite automata from examples using hill-climbing. In Proceedings of the Fourth Annual Conference of the Cognitive Science Society, pages 105-108, Ann Arbor, Michigan, 1982.
[50] Hinton, N Srivastava, and K Swersky. Coursera: Neural networks for machine learning: Lecture 6 (v)-vver of mini-batch gradient descent, 2014.
13


Reviews:
[{"review_id": "oAjR6RD4Zdm", "reviewer": "Reviewer_Gmdk", "summary": "In this paper, the authors try to prove that overparametrized RNNs can efﬁciently learn concept classes consisting of one-hidden-layer neural networks that take the entire sequence of tokens as input. The training algorithm used is SGD with sufﬁciently small step size. Conceptually and technically, the introduced new ideas enable us to extract information from the hidden state of the RNN, which addresses a crucial weakness in previous work. In the end, the authors illustrate their results on some regular language recognition problems.", "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": "Originality:\nThe motivation of this paper comes from the fact that, compared to the previous work [37], this paper investigates the learnability of RNN for more general concept class. The motivation is ok and the proofs seem non-trivial.\n\nQuality:\nI have checked  details and did not find technical ﬂaws.\n\nClarity:\nThe paper is in general well-written. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\n1. The concept class (definition 3.1), as the main difference from related work [37], should be discussed in more detail. It would be better to add a remark (e.g., below Definition 3.3) to illustrate the relation between the concept classes in this paper and [37].\n\n2. There’s some notational confusion here and there, e.g.,  Back_{i->j} (line 217, Equation 4) is used before being introduced,  parameter p (Equation 2) is not formally introduced, etc.\n\n3. (line 142) Why is the output coefficient b_{r,s} set to |b_{r,s}|\\leq 1?\n\n4.  In Theorem 3.1, we see that the step size \\eta=\\frac{1}{\\epsilon \\rho^2 m}. If I am not wrong, the step size \\eta tends to be large when \\epsilon moves towards 0, which seems to contradict the statement in line 69  (“The training algorithm used is SGD with sufﬁciently small step size.”). \n\nSome typos, e.g.,\nLine 160: sgd  SGD\nLine 162: traintrained", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "Yy1aA-lQOlk", "reviewer": "Reviewer_N1qr", "summary": "Reference [37] demonstrated that that SGD learns the recurrent weight matrix of an RNN with provable generalization if the number of training sequences is at least polynomial in the logarithm of the number of hidden nodes, and if the target function computes, at each time step, a sum of differentiable functions of linear transforms of previous  time steps.  This paper uses the same notation, and many of the same methods, but significantly extends the previous work  in the following way: the function class that can be computed is significantly expanded, to include sums of differentiable functions of linear transforms of the __concatenated sequence__ of inputs, not just transforms of individual inputs. In order to do so, this paper cosiders bounds on the input matrix (A) and recurrent matrix (W) sufficient to encode the entire sequence of inputs into the state vector.", "questions": "", "limitations": "", "rating": 8, "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": "Strengths\n\nIn the spirit of many recent papers, the generalization error bound considered here is not a monotonically increasing function of the number of hidden nodes.  Instead, as in  reference [37], the generalization bound is actually a monotonically decreasing function of the number of hidden nodes, for any fixed dataset size.  \n\nAn interesting  and surprising result in this derivation is that the number of hidden nodes is required to be very large: at least polynomial in the sequence length, function class complexity, and output dimension.  This result is fundamental to the proof method, because the proof method encodes the entire input sequence into the state vector.  I'm actually not sure if this is a strength or a weakness of the paper: it obviously limits the applicability of this result  in practical settings, but the purpose of that limitation (the state vector needs to encode the input) is quite interesting, and might cause practitioners to think about the designs of their architectures.\n\nWeaknesses\n\nThe convergence proof depends on similarity between the pseudo-network and the learned network.  The pseudo-network and learned network differ if many of the ReLUs have switched on or off during  training.  Although each step of SGD might switch very few  ReLUs, the optimum weights (the end of SGD) might  have a completely  different set of ReLU activations than the initial set, and in that case, the pseudo-network will be an arbitrarily poor approximation of the true network.  In that case, I believe, the convergence proof fails.\n\nThe requirement that the length is fixed at L is proposed in the text as being \"w.l.o.g.\"  It is more accurate to say, as the conclusion says, that because of this requirement, the results in this article are ony proven for test sequences that are shorter than the longest training sequence.\n\n\"parameterization\" is sometimes spelled \"parameterization\", sometimes \"paramterization\", sometimes \"paramtrization\".  OK, we know what you mean, but this  seems sloppy.  There are  other places where spelling or grammar are sloppy.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The key contribution of the paper is a result demonstrating generalization error bounds for very wide recurrent neural networks trained with SGD.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "R0yyvheU8c", "reviewer": "Reviewer_pm6R", "summary": "The authors provide a proof that sufficiently wide recurrent neural networks can accurately learn functions of sequences of data, providing a much needed extension of known results about standard feed-forward neural network to recurrent neural networks.", "questions": "", "limitations": "", "rating": 7, "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 authors first extend the result shown in (https://arxiv.org/pdf/1811.04918.pdf) to recurrent neural networks, showing that a wide enough RNN can learn *any* function from sequence input space (i.e. R^(d*L), where d is the input dimension and L is the sequence length) to output space, so long as it can parametrized by a neural network with one hidden layer and smooth activation, which is a very large concept class. \n\nThis is not trivial, as RNNs are 'limited' to a constant function between input space and hidden layer, hidden layer at one time-point and the next, and the hidden layer to output, and they authors showed SGD is in fact able to learn any function from the concept class described above. \n\nWhile the proof is obviously very long, the authors do provide a straight forward 'sketch' of the proof, which makes it clear what are the key innovations and ideas that went into it. The further make note of their contributions beyond other works such as https://arxiv.org/pdf/1902.01028.pdf and https://papers.nips.cc/paper/2019/file/62dad6e273d32235ae02b7d321578ee8-Paper.pdf, which follow a similar formalism.\n\nOverall, this work is a critical step in the theoretical analysis of sequential neural networks and I recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I see not negative societal impact from this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "FwPbB6Sf1pi", "reviewer": "Reviewer_vs66", "summary": "This paper shows that overparamterized RNNs trained with SGD can learn a concept class defined over the entire input sequence. The paper provides convergence and generalization guarantees.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "**Originality** - The work is a natural extension of previous work, the main difference between this work and prior work [1] is the the analysis under a more general concept class and instead of fixing A and B at initialization only B is fixed in this work. The contribution seems marginal as the majority of technical tools were introduced in prior work.\n\n**Quality** - The submission seems technically sound and well supported although verifying correctness of all claims will require hundreds of hours to do rigorously and is beyond the capacity of a standard review.\nI would appreciate a discussion on the practical bounds achieved, i.e. are the bounds meaningful in practice or do they require huge widths that practically make this result no different than those obtained via NTK?\n\n**Clarity** - The paper is clear and well written. The authors do a good job in interpreting their technical claims.\nThe implications of theorem 3.1 are not clear enough, an example would be very informative, for example in lemma D.4 the bound contains $\\rho^7$ where in theorem 3.1 $\\rho$ is defined to be $\\rho=100Ld_{out}$, for sequence length $10$ and output dimension $1$, the value is huge: $\\rho^7=10^{21}$. It seems a bit misleading to present this as analysis in the finite case.\n\n**Significance** - I think this paper’s significance is incremental as it is mostly technical changes to prior work and the technical tools that constitute a significant contribution were mostly established in [1].\n\n\n\nAdditional points:\n1. The introduction provides background and then shifts to be related work in line 52.\n2. Line 97 - why is C_s of sin z O(1) ?\n3. Lemma 4.2 - if you set W*=0, doesn’t this imply you find a feed-forward NN and not an RNN?\n4. Re-randomization 295-305 - what are the assumptions implied by this process? Is it equivalent to having random weights?\n\n[1] Can SGD Learn Recurrent Neural Networks with Provable Generalization? Zeyuan Allen-Zhu, Yuanzhi Li, 2019", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation is the practicality of the obtained guarantees, it is not clear if the sample complexity and network width obtained by theorem 3.1 are meaningful.\nThere is no concern for negative social impact by this submission. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns arise from this submission", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves that sufficiently overparameterized RNNs can learn functions of their input that can be computed by a hidden single layer MLP operating on the entire sequence concatenated together (the size of which is related to the size of the required RNN). If I understand correctly, the main idea is to show that a carefully initialized RNN basically encodes the entire sequence up to the current time step within its hidden state vector, similar to an echo-state network. From there, an NTK-style argument is given that this information can be decoded by the output layer through gradient descent training.

While probably still an oversimplification of how RNNs actually work in practice, this paper represents an improvement on our state of formal understanding compared to previous theoretical works. The reviewers and myself found the paper to be well written and relatively easy to read, despite the difficult subject matter. The reviewers weren't able to find any serious technical issues with the proofs or problems with the plausibility of the claims, although they weren't able to carefully check the proofs thoroughly due to the very long length of the appendix. (I suppose it is questionable whether a paper of this kind of suitable for NeurIPS.) Thus, while I cannot 100% certify the correctness of this paper, I think it's most likely to be correct, and thus a solid contribution to the theory of overparameterized neural networks. 
Decision: Accept (Poster)