Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
In this paper, the authors study the type of functions that can be learned with RNNs. They show 2 types of concept classes (additive and N-variables) that can be learned with time and sample complexity almost polynomial in L (input length). For the additive concept class, using the analysis about the NTK of the model they prove the generalization error bound for learnability of such functions without using the normalization condition. Going beyond the additive concept class, they show learnability for N-variable functions with similar guarantees.

main_review: 
The paper considers the problem of providing provable guarantees for the generalization of recurrent neural networks. The result for the additive concept class adds to the earlier work by proving the case without the normalized condition. They also go beyond the additive case and the result for N-variables functions is novel. They clearly state the differences with earlier work. I haven’t gone through every proof in the appendix but I appreciate the flow chart in the beginning. I understand that this is a theoretical paper, however, I believe adding a few numerical experiments would improve the work.

Other comments:
- Could you clarify if the result holds true for input sequences of arbitrary length?
- Line 43-46: it is not clear where the terms m and complexity are used.
- The reference links to different sections and theorems do not work.



limitations_and_societal_impact: The authors discussed limitations and there is no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers when the training data are separable by certain concept class, the generalization of overparameterized RNN trained by SGD. The generalization error depends on a function complexity measure and converges at the rate $1/n$.

The treatment and results in the paper share the flavor of [Cao and Gu, 2019, Arora et al., 2019, Allen-Zhu et al., 2019]. Several comparisons are made in the paper to justify the contribution: 1) Compared to [Cao and Gu, 2019, Arora et al., 2019], no data distribution assumption is made in the current manuscript; 2) No normalized condition is needed compared to [Allen-Zhu and Li, 2019a].

Organization of the paper is clear and easy to follow, despite the proof sketch in Section 4.1 reads a bit dense. I appreciate the authors provided a proof road map in supplementary. No experiments are provided, yet the focus is purely on theory.
main_review: The following comments may help improve the clarity and significance of the paper:

1) A practical motivation on considering the concept class in the paper is missing. For example, does autoregressive models belong to the concept class. (I feel like they can be described by the N-variables concept class.) These examples may be helpful in explaining the data separation assumption in Theorem 2, as it is rather not a restrictive condition.

2) It is unclear how Theorem 5 and Theorem 6 are applied to deriving Equation (32). Meanwhile, Theorem 5 and 6 themselves may need some high-level explanations and intuitions on why it is true.

3) Technical novelty of the paper should be made more clear. The major contribution is establishing inequality (20). From the current presentation, it is hard to evaluate its difficulty and understand the tools used here.

---------------------- Post Author Response ----------------------------

The author response clarified most of my concerns. I would like to keep my score.
limitations_and_societal_impact: Limitations of the work is discussed in Section 6. There is no directly foreseeable negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper investigates the learnability of certain types of concept classes via recurrent neural networks. In particular, the authors consider two concept classes: 1) functions that are sums of power series of a linear function of each temporal input and 2) functions that are sums of power series of a linear transformation of the entire temporal sequence. Under suitable conditions, it is proved that these functions can be learned by RNN in polynomial time and sample complexity, and almost polynomial in input sequence length.
main_review: While the topic of learnability of function(al)s by RNN is a highly relevant topic, I am not sure if the results in this paper contributes to a substantial advancement in this understanding. The biggest issue I see is the lack of motivation of why one would want to consider concept classes introduced in Eq (4) and (5), and in particular why they are interesting generalizations of those considered in earlier works (e.g. [Allen-Zhu and Li, 2019a]). Moreover, the proof techniques appears to be adapted from earlier works. In this sense, I feel that the novelty of the results presented here is quite limited. Below, I list some additional questions/issues:

1. As far as I am aware, ReLU activation is rarely used in RNNs as a recurrent activation, since it only outputs non-negative values. Usually, activations such as $tanh$ is used. How crucially do the current results depend on this assumption? 
2. What is the intuition of the complexity measures in (6) and (7), and what is the relationship between usual Hardy/Bergman spaces and their associated associated norms? It appears to me to be a measure of (generalized) regularity, since it concerns the decay rate of certain series coefficients. The paper would benefit from a discussion of the meaning of the complexity measure introduced.
3. Algorithm 1: As stated, the matrices $A$ and $B$ appears to be fixed during training. This is different from practical RNN training where these are also weights to be trained. 

## Minor Issues

The paper would benefit from more careful proofreading, as there are many typos and grammatical errors. I list some I have identified below.

1. Page 5 Line 155: the parameters of $m^*$ does not agree with previous line.
2. Page 5 Line 155: “there exits”
3. Page 6 Line Remark 3.3: “do not dependent”
4. Page 6 Line 180: “The really matter thing” - revise sentence
5. Eq (4): and Eq (5): the RHS should depend on $l,r$ and $r$ respectively

---

After rebuttal: I thank the authors for addressing some of the questions. It appears that some of the limitations I pointed out (not training A,B, using ReLU activations) are also assumed in some prior works. While still unrealistic, it is acceptable for the purpose of simplifying analysis to obtain insights. 
I think the paper's novelty can be much better emphasized by building some of the discussion in the authors' reply in the paper itself. In the present form I have reservations to recommend acceptance due to unclear new contributions.
limitations_and_societal_impact: Not applicable
review_title: null

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