Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

**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.
I 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?

**Clarity** - The paper is clear and well written. The authors do a good job in interpreting their technical claims.
The 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.

**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].



Additional points:
1. The introduction provides background and then shifts to be related work in line 52.
2. Line 97 - why is C_s of sin z O(1) ?
3. Lemma 4.2 - if you set W*=0, doesn’t this imply you find a feed-forward NN and not an RNN?
4. Re-randomization 295-305 - what are the assumptions implied by this process? Is it equivalent to having random weights?

[1] Can SGD Learn Recurrent Neural Networks with Provable Generalization? Zeyuan Allen-Zhu, Yuanzhi Li, 2019
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.
There is no concern for negative social impact by this submission.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: Strengths

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

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

Weaknesses

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

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

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




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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Originality:
The 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.

Quality:
I have checked  details and did not find technical ﬂaws.

Clarity:
The paper is in general well-written. 
limitations_and_societal_impact: 
1. 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].

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

3. (line 142) Why is the output coefficient b_{r,s} set to |b_{r,s}|\leq 1?

4.  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.”). 

Some typos, e.g.,
Line 160: sgd  SGD
Line 162: traintrained
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

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

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

Overall, this work is a critical step in the theoretical analysis of sequential neural networks and I recommend acceptance.
limitations_and_societal_impact: I see not negative societal impact from this work.
review_title: null

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)