Learning and Generalization in RNNs
Year: 2021

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

heading: 1 Introduction
text: Simple Recurrent Neural Networks [1] 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 on inputs of fixed length, such as vectors in Rd. In contrast, RNNs model functions whose input consists of sequences of tokens x(1),x(2), . . ., where x(i) ∈ Rd for each i. RNNs have a notion of memory; formally it is given by the hidden state vector which is denoted by h(t) after processing the t-th token. RNNs apply a fixed function to h(t) and x(t+1) to compute h(t+1) and the output. This fixed function is modeled by a neural networks with one hidden-layer. Compared to FFNs, new challenges arise in the analysis of RNNs: for example, the use of memory and the same function at each step introduces dependencies across time and RNN training suffers from vanishing and exploding gradients [6].
Studies aimed at understanding the effectiveness of RNNs have been conducted since their introduction; for some of the early work, see, e.g., [7, 8]. 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 to approach full understanding of RNNs and appears to be far more challenging. While experimental probing has continued apace, e.g., [9, 10], progress on theoretical front has been slow. It is only recently that training and generalization are starting to be addressed in the wake of progress on the relatively easier case of FFNs as discussed next.
RNNs are closely related to deterministic finite automata [11, 9] as well as to dynamical systems. With finite precision and ReLU activation, they are equivalent to finite automata [11] in computational power. In the last few years progress was made on theoretical analysis of overparameterized FFNs
∗Work done as a research fellow in Microsoft Research India
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
with one-hidden-layer, e.g., [12, 13, 14, 15, 16, 17, 18]. 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.
But the gap between our understanding of RNNs and FFNs remains large. [20, 21] provide generalization bounds on RNNs in 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, 27, 28], linear RNNs [29], saturated RNNs [30, 31, 32], and echo state networks [33, 34]. Several other works talk about the expressive power of the novel sequence to sequence models Transformers [35, 36]. Due to a 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 a 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-randomization 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, it cannot capture problems where the RNN needs to make use of the information in the past tokens when processing a 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 h(t). (The above concept class comes up because it can be learnt even if h(t) is ignored.) But the hidden state h(t) 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), . . . ,x(L) of fixed length as opposed to 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-layer networks, such RNNs can approximate all continuous functions of x(1), . . . ,x(L)—though 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 a 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),x(`2), . . . ,x(`N )), where `1, . . . , `N ∈ [L]. However, the number of SGD iterations and training samples necessary depend exponentially on the minimum of the two parameters, N and `0 = max(`1, . . . , `N )−min(`1, . . . , `N ).

heading: 2 Preliminaries
text: Let Sd−1 := {x ∈ Rd | ‖x‖2 = 1} be the unit sphere in Rd. For positive integer n define [n] := {1, 2, . . . , n}. Given a vector v, by vi we denote its i-th component. Given two vectors a ∈ Rd1 and b ∈ Rd2 , [a,b] ∈ Rd1+d2 denotes the concatenation of the two vectors. 〈·, ·〉 denotes the standard dot product. Given a matrix M, we will denote its i-th row as mi and the element in row i and column j as mij . Given two matrices A ∈ Ra1×a2 and B ∈ Rb1×b2 with a1 = b1 let
[A,B]r ∈ Ra1×(a2+b2) denote the matrix whose rows are obtained by concatenating the respective rows of A and B. Similarly, [A,B]c ∈ R(a1+b1)×a2 (assuming a2 = b2) denotes the matrix whose columns are obtained by concatenating the columns of A and B.
O(·) and Ω(·) 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 σ : R→ R, given by σ(x) := max{x, 0} = x Ix≥0, be ReLU activation function. ReLU can be extended to act on vectors by coordinate-wise application: σ((x1, . . . , xd)) := (σ(x1), . . . , σ(xd)). Note that ReLU is a positive homogenous function of degree 1, that is to say σ(λx) = λσ(x) for all x 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 . Definition 2.1 (Function complexity [15]). Suppose that function φ : R→ R has Taylor expansion φ(z) = ∑∞ i=0 ciz i. For R, > 0, define
Cε(φ,R) := ∑∞ i=0 ( (C∗R) i + (√ log(1/ε)√ i C∗R )i) |ci| ,
Cs(φ,R) := C ∗∑∞ i=0(i+ 1) 1.75Ri |ci| ,
where C∗ = 104. As an example, if φ(z) = zd for positive integer d, then Cs(φ,R) = O(Rd) and Cε(φ,R) = O(Rd logd/2( 1ε )). For φ(z) = sin z, cos z, e
z , we have Cs(φ,R) = O(1) and Cε(φ,R) = poly(1/ε). We have Cs(φ,R) ≤ Cε(φ,R) ≤ Cs(φ,O(R)) × poly(1/ε) for all φ and for φ(z) = sin z, ez or constant degree polynomials, they only differ by o(1/ε). See [15] for details. Note that φ itself is not a member of our concept class but functions like it will be used to construct members of our concept class.

heading: 3 Problem Formulation
text: In our set-up, RNNs output a label after processing the whole input sequence.2 The data are generated from an unknown distribution D over ((x(2), . . . ,x(L−1)),y∗) ∈ ((Sd−2)L−2,Y), for some label set Y ⊂ Rdout for some positive integer dout. We call x := (x(2), . . . ,x(L−1)) the true sequence and y∗ the true label. Denote by Z the training dataset containing N i.i.d. samples from D. We preprocess the true sequence to normalize it:
Definition 3.1 (Normalized Input sequence). Let x = (x(2), . . . ,x(L−1)) be a given true input sequence of length L − 2, s.t. x(i) ∈ Sd−2 and x(i)d−1 = 1 2 , for all i ∈ [2, L − 1]. The normalized input sequence x := (x(1), . . . ,x(L)) is given by
x(1) := (0d−1, 1), x(`) := (εxx (`), 0), ∀` ∈ [2, L− 1], x(L) := (0d−1, 1),
where we set εx > 0 later in Theorem 3.1.
We use normalized sequence in place of the true sequence as input to RNNs, as it 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 in the normalized sequence serves as bias which we do not use explicitly to simplify notation.

heading: 3.1 RNNs
text: Definition 3.2 (Recurrent Neural Networks). We assume that the input sequences are of length L for some given L > 0 and are of the form x(1), . . . ,x(L) with x(`) ∈ Rd for all ` ∈ [L]. An RNN is
2While our set-up has similarity to previous work [37], there are also important differences.
specified by three matrices Wrnn ∈ Rm×m, Arnn ∈ Rm×d and Brnn ∈ Rdout×m, where m is the dimension of the hidden state and dout is the dimension of the output. The hidden states of the RNN are given by h(0)rnn = 0 ∈ Rm and
h(`)rnn := σ(Arnnx (`) + Wrnnh (`−1) rnn ) for ` ∈ [L]. (1)
The output at each step ` ∈ [L] is given by y(`)rnn = Brnnh(`)rnn. By RNN cell we mean the underlying FFN in (1). The m rows of Wrnn and Arnn correspond to the m neurons in the RNN.
Pick the matrices W ∈ Rm×m and A ∈ Rm×d by sampling entries i.i.d. from N(0, 2m ), and pick B by sampling entries i.i.d. from N(0, 2dout ). When Wrnn = W and Arnn = 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(`)}`∈[L]. In the following theorems, we will keep Brnn at initialization B and train only Arnn and Wrnn.
We write F (`)rnn(x;Wrnn,Arnn) = y (`) rnn = Bh (`) rnn for the output of the `-th step. Our goal is to use y (L) rnn ∈ Rdout to fit the true label y∗ ∈ Y using some loss function G : Rdout × Y → R. We assume
that for every y∗ ∈ Y, G ( 0k,y∗ ) ∈ [−1, 1] is bounded, and G (·,y∗) is convex and 1-Lipschitz continuous in its first variable. This includes, for instance, the cross-entropy loss and `2 -regression loss (for bounded arguments).

heading: 3.2 Concept Class
text: 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 : R(L−2)·(d−1) → Rdout defined as follows. Let Φ denote a 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,s : R→ R}r∈[p],s∈[dout] from Φ, {w†r,s ∈ S(L−2)(d−1)−1}r∈[p],s∈[dout], a set of weight vectors, and {b†r,s ∈ R}r∈[p],s∈[dout], a set of output coefficients with |b†r,s| ≤ 1. Then, we define F : R(L−2)·(d−1) → Rdout , where for each output dimension s ∈ [dout] we define the s-th coordinate Fs of F = (F1, . . . , Fdout) by
Fs(x) := ∑ r∈[p] b†r,sΦr,s ( 〈w†r,s, [x(2), . . . ,x(L−1)]〉 ) . (2)
To simplify formulas, we assume Φr,s(0) = 0 for all r and s. We denote the complexity of the concept class by
Cε(Φ, R) := max φ∈Φ {Cε(φ,R)}, Cs(Φ, R) := max φ∈Φ {Cs(φ,R)}.
Let F ∗ be a function in the concept class with smallest possible population loss which we denote by OPT. Hence, we are in an agnostic learning setting where our aim is to learn a function with population objective OPT + ε. As one can observe, functions in the concept class are given by a one hidden layer network with p neurons and smooth activations. We will show that the complexity of the functions Φr,s determines the number of neurons and the number of training samples necessary to train the recurrent neural network that has OPT + ε population loss.
While we have defined F ∗ as a function of x, since there’s a one-to-one correspondence between x and x, it will occasionally be convenient to talk about F ∗ as being a function of x—and this should cause no confusion. And similarly for other functions like F (`)rnn(x;W,A).

heading: 3.3 Objective Function and the Learning Algorithm
text: We assume that there exists a function F ∗ in the concept class that can achieve a population loss OPT, i.e. E
(x,y∗)∼D G(F ∗(x),y∗) ≤ OPT. The following loss function is used for gradient descent:
Obj(W′,A′) = E (x,y∗)∼Z Obj(x,y∗;W′,A′), where
Obj(x,y∗;W′,A′) = G(λF (L)rnn (x;W + W ′,A + A′),y∗).
Parameter λ whose value is set in the main Theorem 3.1 is a scaling factor needed for technical reasons discussed later. We consider vanilla stochastic gradient updates with Wt,At denoting the matrices after t-steps of sgd. Wt and At are given by
Wt = Wt−1 − η∇Wt−1Obj(x,y∗;Wt−1,At−1), At = At−1 − η∇At−1Obj(x,y∗;Wt−1,At−1),
where (x,y∗) is a random sample from Z and x is its normalized form. It should be noted that [37] train only W.
Remark. We made two assumptions in our set-up: (1) input sequences are of fixed length, and (2) the output is only considered at the last step. These assumptions are without loss of generality and allow us to 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 at 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.

heading: 3.4 RNNs learn the concept class
text: We are now ready to state our main theorem. We use ρ := 100Ldout logm 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 Φ be a set of smooth functions. For x := 1poly(ρ) and ε ∈ ( 0, 1
p·poly(ρ)·Cs(Φ,O( −1x ))
) , define complexity C := Cε(Φ,O( −1x )) and
λ := ε10Lρ . Assume that the number of neurons m ≥ poly ( C, p, L, dout, ε −1) and the number of samples N ≥ poly ( C, p, L, dout, ε
−1). Then with parameter choices η := Θ( 1ερ2m) and

heading: T := Θ(p2C2 poly(ρ)ε−2) with probability at least 1−e−Ω(ρ
text: 2) over the random initialization, SGD satisfies
E sgd [ 1 T T−1∑ t=0 E (x,y∗)∼D Obj ( x,y∗;Wt,At )] ≤ OPT + ε+ 1/poly(ρ). (3)
Informally, the above theorem states that by SGD training of overparameterized RNNs with sufficiently 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 ε+ 1/poly(ρ) is 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 error ε.

heading: 4 Proof Sketch
text: 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.
1. Overparameterization simplifies the neural network behavior. The function F (L)rnn (x;W + W′,A + A′) computed by the RNN is a function of the parameters W′,A′ as well as of the input x. It is a highly non-linear and non-convex function in 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—predominantly for the FFN setting—that when the network is overparameterized (i.e., as the number of neurons m becomes large compared to other paramters of the problem such as the complexity of the concept class), the network behavior simplifies in a certain sense. The general idea carries over to RNNs as well: in (4) below we write the first-order Taylor approximation of F (L)rnn (x;W + W′,A + A′) at W and A as a linear function of W′ and A′; it is still a non-linear function of the input
sequence. As in [37] we call this function pseudo-network, though our notion is more general as we vary both the parameters W′ and A′. Pseudo-network is a good approximation of the target network as a function of x for all x.
2. Existence of a good RNN. In order to show that the RNN training successfully learns, we first show that there are parameters values for RNN so that as a function of x it is a good approximation of F ∗. Instead of doing this directly, we show that the pseudo-network can approximate F ∗; this suffices as we 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 of x. Thus, SGD finds parameters with training loss close to that achieved by W∗,A∗.
4. Generalization. Apply a Rademacher complexity-based 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.3

heading: 4.1 Pseudo-network
text: We define the pseudo-network 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 (L)(x;W′,A′) := L∑ i=1 Backi→LD (i) ( W′h(i−1) + A′x(i) ) (4)
≈ F (L)rnn (x;W + W′,A + A′)− F (L)rnn (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 λ, that we defined in the objective function, will be used to make the contribution of F (L)rnn at initialization small thus making pseudo-network a good approximation of RNN. Hence, we can observe that the pseudo network is a good approximation of the RNN, provided the weights stay close to the initialization.
To complete the above definition of pseudo-network we define the two new notations in the above formula. For each ` ∈ [L], define D(`) ∈ Rm×m as a diagonal matrix, with diagonal entries
d(`)rr := I[w>r h(`−1) + a>r x(`) ≥ 0], ∀r ∈ [m]. (5)
In words, the diagonal of matrix D(`) represents the activation pattern for the RNN cell at step ` at initialization.
Define Backi→j ∈ Rdout×m for each 1 ≤ i ≤ j ≤ L by
Backi→j := BD (j)W . . .D(i+1)W,
with Backi→i := B for each i ∈ [L]. Matrices Backi→j 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 Backi→j as related to the backpropagation signal from the output at step j to the parameters at step i.

heading: 4.2 Existence of good pseudo-network
text: Our goal is to construct W∗ and A∗ such that for any true input sequence x = (x(2), . . . ,x(L−1)), if we define the normalized sequence x = (x(1), . . . ,x(L)), then with high probability we have
F (L)(x;W∗,A∗) ≈ F ∗(x). (6) 3The 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 to 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 to 1. Also, let the output weight b† := 1. These assumptions retain the main proof ideas while simplifying equations. Overall, we assume that the target function F ∗ : R(L−2)·(d−1) → R on a given sequence is given by
F ∗(x) = Φ∗(〈w†, [x(2), · · · ,x(L−1)]〉), (7)
where Φ∗ : R→ R is a smooth function and w† ∈ S(L−2)·(d−1)−1. First, we state Lemma 6.2 in [15], which is useful for our construction of the matrices W∗ and A∗. Consider a smooth function φ : [−1, 1]→ R. It can be approximated as a linear combination of step functions (derivatives of ReLU) for all u ∈ (−1, 1), i.e., there exists a “weight function”H : R2 → R such that φ (u) ≈ Eα1,β1,b0 [H (α1, b0) Iα1u+β1√1−u2+b0≥0] where α1, β1 ∼ N (0, 1) and b0 ∼ 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 φ, any w ∈ Sd−1, and any ε ∈ (
0, 1Cs(φ,1)
) there exists a
H : R2 → ( −Cε (φ, 1) ,Cε (φ, 1) ) , which is Cε (φ, 1)-Lipschitz continuous and for all u ∈ Sd−1, we
have ∣∣∣φ(w>u)− Ew∼N (0,I),b0∼N (0,1)[H(w>w, b0) Iw>u+b0≥0]∣∣∣ ≤ ε. Very informally, this lemma states that the activation pattern of a one-layer ReLU network (given by Iw>u≥0) at initialization can be used to express a smooth function of the dot product of the input vector with a fixed vector. While the above statement involves an 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 [15, 37]. Can we use it for RNNs for our 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 x(L). Lemma 4.2 (Informal). For a given smooth function φ, a vector w ∈ S(m+d−1), and any ε ∈(
0, 1Cs(φ,1)
) , there exist matrices W∗ and A∗ such that for every normalized input sequence x =
(x(1), . . . ,x(L)) formed from a sequence x, we have with high probability,∣∣∣F (L)(x;W∗,A∗)− φ(〈w, [h(L−1),x(L):d−1]〉)∣∣∣ ≤ ε, provided m = poly( 1ε , L,C (φ,O(1))). Vector x (L) :d−1 is x
(L) without the last coordinate, the bias term appended to each input.
The reason h(L−1) and x(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 are 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 ∼ N (0, 2mI). Also, recall that we have assumed for simplicity dout = 1. Hence, B and Backi→L are row and column vectors respectively. For typographical simplicty, denote by br and Backi→L,r the respective r-th components of these vectors.
We set W∗ := 0 and for every r ∈ [m], a∗r := 1mbrH( √ m/2(〈[wr,ar,:d−1],w〉), √ m/2ar,d)ed, for a function H that we will describe below. With these choices we have
F (L)(x;W∗,A∗) = L∑ i=1 Backi→LD (i) ( W∗h(i−1) + A∗x(i) ) = 1
m L∑ i=1 ∑ r∈[m] brBacki→L,rH( √ m/2(〈[wr,ar,:d−1],w〉), √ m/2ar,d) · Iw>r h(i−1)+a>r x(i)≥0.
In the last step, we have simplified the formula using sum over neurons. The first L− 1 summands in the outer sum above nearly vanish due to small correlation between B and Backi→L for i < L (see Lemma F.11). Recall that BackL→L = B and thus the correlation is not small for i = L. This gives
F (L)(x;W∗,A∗) ≈ 1 m ∑ r∈[m] b2rH( √ m/2(〈[wr,ar,:d−1],w〉), √ m/2ar,d) · Iw>r h(i−1)+a>r x(i)≥0,
Now, this resembles a discretized version of Lemma 4.1. We can substitute u as [h(L−1),x(L)] in Lemma 4.1 and use concentration bounds with respect to the randomness of weights W and A to complete the proof.
More generally, with much more technical work, it might be possible to prove an extension of the above lemma asserting the existence of a pseudo-network approximating a sum of functions of type∑ i∈[L] φi(〈wi, [h(i−1),x(i)]〉). However, even so it is not at all clear what class of functions of x 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 in h(`). The construction of 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 h(`) in fact contains information about all the inputs x(1), . . . ,x(`) up until step `. Furthermore and crucially, this information can be recovered approximately by a linear transformation (Theorem 4.5 below). This enables us 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 − e−Ω(ρ
2) over W,A,B, we have for every normalized input sequence x = (x(1), . . . ,x(L)) formed from a true sequence x,∣∣∣∣F (L)(x;W∗,A∗)− Φ∗ (〈w†, [x(2), . . . ,x(L−2)]〉)∣∣∣∣ ≤ ε+ 1poly(ρ) , provided m ≥ poly(ρ, L, ε−1,Cε(Φ,O(ε−1x ))) and x ≤ 1poly(ρ) .
Proof sketch. By Theorem 4.5 there exists a matrix W [L] such that W [L]>
h(L−1) ≈ [x(1), . . . ,x(L)] for all input sequences [x(1), . . . ,x(L)]. We can modify W [L] to get [x(2), . . . ,x(L−1)]. Hence, by using [W [L]
w†,0] as w and Φ∗ as φ in Lemma 4.2, we can have F (L)(x;W∗,A∗) ≈ Φ∗(〈w†,W[L]>h(L−1)〉) ≈ F ∗(x), implying F (L) and F ∗ are close. Accounting for all the errors in inversion and approximation of function, we get the final bound.
Re-randomization. In the proof sketches of Lemmas 4.2 and Theorem 4.3 above we swept a technical but critical consideration under the rug: the random variables {wr,ar}r∈[m], W (L) , {Backi→L}i∈[L] and {h(i)}i∈[L] are not independent. This invalidates application of standard 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 re-randomize the rows of the matrix [W,A]r, show that the matrices W [L] , {Backi→L}i∈[L] and {h(i)}i∈[L] don’t change a lot and then apply concentration bounds w.r.t. the new weights in the set. Finally, we account for the error from each set.

heading: 4.3 The rest of the proof
text: Having shown that there exists a pseudo-network approximation of the RNN that can also approximate 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, overparameterized RNNs behave as a linear network and hence the training can be
analyzed via convex optimization. Then, we show using Lemma D.4 that the Rademacher complexity for overparameterized RNNs is bounded. Again, the main idea here is that overparameterized 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.

heading: 4.4 Invertibility of RNNs at initialization
text: In this section, we describe how to get back x(1), . . . ,x(L) from the hidden state h(L). The following lemma states that any linear function can be represented by a one-hidden layer FFN with activation function ReLU,with a small approximation error of the order 1√
m :
Lemma 4.4. [a simpler continuous version can be found in Lemma C.1 in the appendix] For any v ∈ Rd, the linear function taking x to v>x for x ∈ Rd, can be represented as∣∣∣v>x− p>σ(Tx)∣∣∣ ≤ ‖v‖ ·‖x‖√
m , (8)
with p = 2Tv, where T ∈ Rm×d is a matrix with elements i.i.d. sampled from N (0, 1).
Using the above lemma,4 we will show that the hidden state h(L) can be inverted using a matrix W [L] to get back the input sequence x(1), . . . ,x(L).
Theorem 4.5. [informal version of Theorem D.1] There exists a set of matrices {W[`]}`∈[L], which can possibly depend on W and A, such that for any εx < 1L and any given normalized sequence x(1), . . . ,x(L), with probability at least 1− e−Ω(ρ2) we have∥∥[x(1), . . . ,x(L)]−W[L]>h(L)∥∥∞ ≤ poly(L, ρ,m−1, εx). Very roughly, the above result is obtained by repeated application of Lemma 4.4 to go from h(`) to (h(`−1),x(`)) 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 to be overcome to carry out this plan.
One difficulty is that a naive application of Lemma 4.4 results in exponential blowup of error with L. The reason is as follows: in Lemma 4.4, the factor 2 in the linear transformation p appears because of the activation function ReLU. A naive application will result in defining W [`] inductively as 2[WW [`−1]
,A]r for 2 ≤ ` ≤ L, with W[1] = A. This will lead to the approximation error exploding exponentially with L in induction, since the approximation error at each step will depend on the norm of W [`−1] .
However, one can observe from the proof of Lemma 4.4 that it suffices to use the following linear transformation: p(w) = w>v Iw>x≥0, which helps in removing the factor of 2. However, this requires knowing the indicator function Iw>x≥0. This implies for RNNs, we need to know the indicator matrix D(`) at each step.
To do so, we define a base sequence x(0), whose indicator matrices {D (`) (0)}`∈[L] will be used to approximate the indicator matrix D(`) at each step ` for any sequence x. That is, W [`]
will be defined inductively as [D(`)(0)WW [`−1] ,D (`) (0)A]r for 2 ≤ ` ≤ L, with W [1] = D (1) (0)A. We then show that the approximation error of the indicator matrix builds up to give an error with polynomial dependence on εx and L. We defer the technical details of this resolution to the full proof in the appendix.
Secondly, we apply re-randomization to tackle the dependence between W, A, {h(`)}`∈[L] and {W[`]}`∈[L]. We performed few toy experiments on the ability of invertibility for RNNs at initializa-
4This lemma is from a companion paper (forthcoming) where it is 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. I). 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).

heading: 5 On concept classes
text: It is apparent that our concept class is very general as it 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 DL1 . Here we are working in the discrete setting where each input token comes from {0, 1} possibly represented as a vector when fed to the RNN. For a sequence z ∈ {0, 1}L, we define DL1(z) to be 1 if the number of 1’s in z is exactly 1 and define it to be 0 otherwise. We can show that DL1 is not representable in the concept class of [37] (see Theorem H.1 in the appendix). However, we can show that the language DL1 can be recognized with a one-layer FFN with one neuron and quadratic activation. The idea is that we can simply calculate the number of 1’s in the input string, which is doable using a single neuron. This implies that our concept class can represent language DL1 with low complexity.
More generally, we can show that our concept class can efficiently represent pattern matching problems, where strings belong to a 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-polynomially on the length of the input sequence, depending on the regular language (more discussion in sec. H). Some regular languages allow special treatment though. For example, consider the language PARITY. PARITY is the language over alphabet {0, 1} with a string w = (w1, . . . , wj) ∈ PARITY iff w1 + . . .+ wj = 1 mod 2, for j ≥ 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. I. Figuring out which regular languages can be efficiently expressed by our concept class remains an interesting open problem.

heading: 6 Limitations and Conclusions
text: 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 a 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 it is often qualitatively different from the practical setting. Theoretical analysis of practical parameter setting remains an outstanding challenge—even for one-hidden layer FFNs. (2) We did not consider generalization to sequences longer than those in the training data. Such a result would be very interesting but it appears that it 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, if we knew that the distributions of the hidden states are similar at different times steps and the output is the same as the hidden state (i.e. B is the identity) then our results might easily generalize to 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.
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.

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

Review summaries:
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.

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.