Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies approximation and optimization of linear RNNs for learning linear functions, from the perspective of the memory-properties of the temporal sequence. It shows that linear functionals can be approximated by a linear RNN, with the rate of approximation depending on the long-term memory of the process.  It also shows that the training dynamics slow down for certain linear functionals with long-term memory. 

Strengths:

1. The problem being studied in the paper is interesting and well-motivated. Capturing long-term memory is one of the major challenges for sequential models such as RNNs, and the paper makes progress towards understanding this.
2. The functional view of the process is interesting, and seems to shed light on interesting phenomenon regarding memory. The paper also brings in rich tools from functional analysis for analyzing RNNs, which could perhaps be more broadly useful if they can be made accessible enough.

Weaknesses:

1. I think the paper needs to be significantly rewritten for the ML audience to extract much out of it. Most of the ML community will not be familiar with the tools and terminology here, including classical results from representation theory such as the Riesz-Markov-Kakutani theorem. Providing more intuition and context for these results will be very helpful. For instance, it would be good to provide some intuition for the \rho(t) function. Once this is introduced, the authors use it interchangeably in place of H_t for describing all their subsequent examples, but it would be better to provide some intuition for the examples directly. The underlying phenomenon are simple and elegant, and I think they can be explained effectively to the ML community.
2. As far as the main message of the paper regarding memory goes, I think it is interesting, but I am not sure if all the machinery is necessary for showing this result? For instance, for a linear functional which does not decay fast enough on the constant input (such as in the conditions of Thm 4.2), would it not be possible to show that it cannot be approximated using a small number of neurons even in the discrete case? The reason being that the process “remembers” inputs over exponentially long windows, and hence you need an exponential number of units to approximate it (at least with linear activations)? Can the authors shed light on the power of the continuous time view and representation theory for showing this?
3. The optimization result seems a bit tailored to a particular functional. I think if the authors could explain more generally why the optimization is getting stuck at a plateau, even at an intuitive level, then that would be useful. I’m also curious about the same question as before, is it not possible to construct a specific worst case function even in the discrete case?

Overall, I think there are some nice ideas and tools here, but am not sure if the ML community will get a lot out of this currently.

Some more comments:

1. Please define/describe the airy function.
2. Typo above Eq (21), We->we.
3. Typo above conclusion, exponentially->exponential.
4. Theorem 4.2, y_i^(k)(t) with the superscript (k) does not appear to be defined?
5. Please clearly define what inputs and outputs are at the beginning of Section, for example x is input, y is output, h is not observed.

------Updates after response------

I thank the authors for the detailed response and the revision. I am still not completely convinced regarding the suitability for ICLR and have similar concerns to reviewer 2, but am not opposed to acceptance.  In light of this, I have increased my score to 6.
review_title: Mathematically elegant paper, but not clear if suitable for ICLR in current form

final_score: rating: 3: Clear rejection
review_content: This paper reports a mathematical study of approximation properties of linear RNNs. The first part  reports a universal approximation theorem, and presents an analysis of how efficient the approximation is. In particular, it is shown that approximating a slowly decaying, power-law temporal filter requires a large number of neurons, a property the authors refer to as the "curse of memory".
 The second part of the paper examines the dynamics of learning under gradient descent, and gives arguments related to the existence of long plateaus seen in the loss as function of training epochs.

The paper is written in a formal mathematical style (Definitions/Theorems). Not being a mathematician, I am not able to assess the formal correctness of the proofs, and I have found some parts not easily accessible. Most importantly, as currently presented the main results seem to be of limited interest to the ICLR community (see below for details). The paper as a whole is probably more appropriate for a more mathematical venue, where the novelty of the proofs may be better appreciated.

Strengths:
- attempts to put on a rigorous footing various experimental observations on RNN training
- possibly novel mathematical derivations of approximation results


Concerns:
- the novelty of the results presented in the first part is limited. Previous works have reported various universal approximation theorems for RNNs. Several classical works on that topic are not mentioned, eg Doya 1993, or Maass 2007. The details of the mathematical derivation may well be novel, but I am not able to judge this aspect.
- the fact that a diverging number of exponentials are needed to approximate a power-law function is also well known; from that perspective the "curse of memory" is not very surprising.
- I found it difficult to extract key results from the second part on Optimization dynamics. 
review_title: A mathematical study of approximation properties of linear RNNs

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The main contributions of the paper are the following ones (informal):
 1. The approximation theorem of linear functionals with linear RNNs in continuous time settings. The main difference with the previous results is that the class of approximated functions is linear, but does not necessarily come from the same differential equation that describes the class of approximator models.
 2. The upper bound on the approximation error for some "exponentially decaying" linear functionals, where the upper bound depends on the weights matrix size (i.e. memory size). The memory growth rate is polynomial with respect to approximation error. It is no longer the case when linear functional is not "decaying exponentially" and memory growth rate is exponential.
 3. The optimization dynamics analysis. In particular, the authors showed that under some conditions the optimization process can be stuck if the "memory" of the target functional is large.

Overall, it is a good paper and I enjoyed reading it. It is very well written and easy to follow. In many cases, the authors provide clarification for used assumptions. 
The authors also emphasize the difference between their results and the previous results.

Pros: the authors showed that difficulties encountered in practice, where the target functional has long term dependencies, emerge even in simple linear settings and can be explained from a theoretical point of view.

Cons: in many settings we are interested in not just recovering some dependencies, but recovering it from the data or recovering the dependency only on some subset of the all possible input sentences. The role of input data is significantly ignored in the given analysis.

Several questions and remarks:
1. The condition on supremum in (14) seems purely technical (at least based on provided proof in appendix). Could the authors please clarify whether this assumption has some qualitative explanation or can be replaced with stronger but more "meaningful" assumptions (of course it will make the result weaker)?
2. In the dynamic analysis x is assumed to be white noise. This assumption seems too restrictive and is used to apply Ito's isometry theorem. What else stochastic processes can be used here to make this result stronger?
3. In (50) in  (-(alpha + 1) / beta)^{i}. i should be replaced with j.

review_title: Official Blind Review #1

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper provides a theoretical examination of the challenge of fitting recurrent neural networks (RNNs) to fit processes with long memory (or long-range dependence). Dubbed the “curse of memory”, the author(s) restrict to the case of linear activation functions, and show that for processes with increased spatial dependence: (a) the width of the layers must increase exponentially to _guarantee_ accurate approximations under a provided bound, and (b) a gradient-based optimization algorithm will take exponentially more time to converge. Sufficient details for reproducing the experiments are provided. 

I like the paper and believe the contributions to be both substantive and of wide interest in the RNN community. The analysis presented here is rigorous and comprehensive, and while the discussion is limited to linear RNNs, it provides a good starting point for further studies regarding long-range dependence with RNNs. The paper is reasonably well-written, and aside from a few minor typos — see the minor comments below — I did not encounter any serious errors. I do have some criticisms, however:

1. Perhaps my biggest disappointment is that while the authors do a good summary of the relevant RNN literature, they have failed to mention any analogous ideas from the time series literature. For example, any discussion regarding Hurst parameters would be welcome, since this is precisely the type of “long-range dependence” discussed here. The lack of references to this literature is disheartening, since these concepts have played a key role in time series analysis for many decades, and it would have been nice to see this acknowledged, or a connection made. 
2. The takeaway from Theorem 4.2 regarding the exponential increase in the required width for fitting a linear RNN is nice, but is undercut by the fact that Theorem 4.2 is an upper bound. I'm satisfied with the result, but a lower bound for approximating a particular functional would be more convincing.
3. I was disappointed with the “informal” presentation here. I can appreciate the attempt to simplify the full statement, but I still had to go to the supplementary material to understand the statement, which I should hope most readers would not have to do. I think a more precise statement than “trapped in a plateau with timescale” would be better. Perhaps something involving the hitting time, or even more simply, $||\theta'(t)|| = O(...)$ as $\omega \to 0^+$ for sufficiently large $t$?

It is also worth noting that there is an extraordinary amount of supplementary material here, much of which, unfortunately, does not get the attention it probably deserves in this format. There are aspects of the paper, including the precise statement of Theorem 5.1 and the definition of the Airy target, that require the reader to visit this material. The proofs of Theorems 4.1 and 4.2 seem fine to me. Unfortunately, the proof of Theorem 5.1 is especially lengthy, so I did not get the opportunity to check each step in detail. However, the general argument appears sound.

Overall, I am impressed with this paper and enjoyed reading it. The missing connections to classical ideas in time series analysis are unfortunate, and I would be willing to give the paper an 8 with a wider literature review and improved presentation of Theorem 5.1. An additional lower bound for Theorem 4.2 would bring it to a 9 at least. But, even in its current form, I recommend this paper for acceptance to ICLR. 

Other comments:
- I believe Theorem 4.1 also follows from the fact that matrix exponential distributions are dense (see [1]), together with the Riesz-Markov-Kakutani representation theorem used here.
- “We first show that the training dynamics of $\mathbb{E}_x J_m$ exhibits very interesting behaviors depending on the form of target functionals.” — This is a little too vague, maybe consider rewording?
- In multiple places: “x being/is the white noise” -> “white noise x” or “x is white noise”.
- Check capitalization in the statement under Theorem A.1.
- “Airy” should be capitalized in each appearance.

[1] He, Qi-Ming, and Hanqin Zhang. "On matrix exponential distributions." Advances in Applied Probability 39.1 (2007): 271-292.
review_title: Official Blind Review #4

Meta-review: This paper provides a theoretically rigorous treatment of approximation properties and convergence analysis of LINEAR RNNs. The reviewers were divided in their evaluation. On the positive side, the presented relation between approximation error and required memory size is not obvious and interesting. On the less positive side, two of the reviewers raised the necessity of mathematical machinery that were invoked. Furthermore, its applicability is unclear in ML, since they aren't applicable to the usual nonlinear RNNs. However, given that the theoretical contributions are clear, the final decision was to accept.
Decision: Accept (Poster)