Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a single-input single-output (SISO) linear system that has a similar sequential input-output structure as the recurrent neural network (RNN). The ground-truth labels are generated by a teacher which is assumed to be a similar linear system. The authors model gradient descent (GD) with small step size by gradient flow (GF), and prove that the convergence of GF to a zero loss solution leads the student to extrapolate (i.e., learn the ground truth completely even beyond the training horizon) when the training sequence length is greater than two times of the teacher's state space dimension, regardless of how large the student state space dimension is.
strength_and_weaknesses: Strength: The topic is interesting. The result seems convincing. The presentation is relatively clear.
Weaknesses: Some places in the setup need more justification. See comments below.

It is reasonable to investigate SISO linear systems as an initial step to understanding the performance of actual RNNs. Most of the parts are clearly stated and well-written. I have some details questions as follows.

1. In Eq. (3.1), why does the transition matrix $A$ need to be symmetric (i.e., $A^T=A$)?

2. In Eq. (3.2) and Eq. (3.3), the loss uses the output only at the last time step. I wonder why not use the output of all time steps to calculate the loss.

3. The authors mention some existing studies of implicit extrapolation in linear RNNs suggesting that GD is biased toward solutions with short-term memory. Does this contradict the result in this paper that low dimensional state space does not coincide the short-term memory? If so, how to explain such a contraction?
clarity,_quality,_novelty_and_reproducibility: This paper is novel and clear. The overall quality is relatively high.
summary_of_the_review: The paper is well-written and provides some novel results, yet some places need more clarification.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors study from a theoretical point of view the extrapolation capabilities of linear RNNs in the teacher-student framework. They show that under certain conditions, students with 0 error may not extrapolate to longer time horizons than the ones they were trained on. They also show, that under the right parameterization of the teacher, if Gradient Flow converges to a zero loss in the training, the student will be able to extrapolate perfectly. They also prove that under some more conditions, the student $\epsilon$-extrapolates.
strength_and_weaknesses: The mathematical arguments seem solid. However, there results only apply to linear RNNs in the teacher-student framework. Even there, conditions on the teacher are necessary to proof the authors statements. I feel the studied setup is too restrictive and it would need to tackle at least non-linear RNNs or more complex learning scenarios. Also, the insights don't lead to any new algorithm/model.
clarity,_quality,_novelty_and_reproducibility: The paper is clear, although the math feels a bit too convoluted at times. I am not familiar enough with this particular area to judge the novelty of this approach.
summary_of_the_review: It's a well-written paper that does a thorough analysis of linear RNNs in the teacher-student framework. However, I feel the scope of the paper is too narrow to justify acceptance at ICLR. If the authors would either study a more general RNN setup or build some new training algorithm based on the insights, this could be a strong publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work provides some theoretical results for the phenomenon of RNNs “extrapolation” i.e., the ability of RNNs to provide correct predictions on test sequences longer than the sequences available at training time.

The theory is built with a simple teacher-student setup with the following properties:

- Teacher and student are represented as linear RNNs.

- The teacher and student RNNs have states spaces of dimension $\hat{d}$ and $d$  respectively.

- The length of the sequences available at training time is $k$.

- The student RNN is in the overparametrised regime ($d > k$).

- No correlation exists between the elements of the input sequences.

- The student RNN is initialised in a “balanced” condition, implying that the linear operators defining the RNN are connected in a specific way that also helps in the calculations.

Under the assumptions and the notation specified above, the authors prove the following main result:

If $k > 2d $ (the training sequences are greater than 2 times the teacher state space dimension) and if a gradient flow loss minimisation reaches zero quadratic loss, then the parameters obtained necessarily generalise.

The authors then enhance this result by relaxing the zero loss condition provided that the teacher is “stable”, and finally prove that the balancedness condition is approximately implied by a near zero initialisation of the RNNs weights, thus justifying one of their assumptions.

After the above theorems are stated/proved, several numerical results are presented. 

These consist in set of curves showing the extrapolation error as a function of the sequence length ($k$) for fixed teacher dimension ($d$) and for several teacher-student settings, specifically: 

(1) the theoretical settings used to prove the theorems 

(2) a simplified settings where certain assumptions from (1) are relaxed (such as the balancedness of the teacher)

(3) a nonlinear RNN setting where essentially none of the simplifying assumptions used hold exactly

For all settings (and remarkably also for the nonlinear setting (3)), the curves resemble a phase transition where the generalisation error decreases sharply around a specific "critical" value of $k$. The critical $k$ value found numerically is around $2d$, in agreement with the theory, trivially for setting (1) and notably also for setting (2) where some theory assumptions have been relaxed. For setting (3) instead, the critical $k$ does not fall around $2d$ but around $4d$.
strength_and_weaknesses: **Strengths:**

The paper is very well written, and relatively easy to follow in spite of the highly technical nature of the results presented. 

The main result is remarkably simple to state, and yet rather nontrivial to prove.

I appreciate a lot the addition of numerical results to supplement, strengthen and extend the theoretical findings. I think nowadays this should be a mandatory practice, while too often it is overlooked or ignored by theoretical studies.


**Weaknesses:**

The results presented are very technical and limited in their scope. In particular, although probably the assumptions used here are less strong than those used in previous theoretical works on the same topic, the main theorems proven are still based on quite strong and unrealistic assumptions such as the linearity of the investigated RNNs and the complete independence of the terms in the sequences.

However, I am aware of the fact that deriving rigorous theoretical results for state of the art (nonlinear) neural networks is a remarkably difficult task, and, moreover, the numerical tests seem to show that the key findings of the work could extend beyond the restricted theoretical setting analysed.



clarity,_quality,_novelty_and_reproducibility: The paper is very clear and seems reproducible, the results are novel to the best of my knowledge.
summary_of_the_review: I appreciate the elegance of the results obtained, the clarity of the writing, the robustness of the results. I also appreciate the presence of several numerical experiments to support and extend the key findings to broader and more realistic settings.

I highlight the somewhat obvious limitations of this work in terms of its strong and unrealistic assumptions, but I recognise the difficulty of theoretical analysis in more realistic settings, and further recognise that the numerical experiments provided seem to suggest that the key findings of this work could extend beyond the restricted setting where they have been proven.

I believe this is a good publication for ICLR. It is not a breakthrough publication, but it is a technically very solid paper which can have good impact in specific research communities.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The manuscript studies extrapolation properties when learning the parameters of a linear dynamical system when predicting outputs on time horizons longer than present in the training data in a student teacher setup. 
For balanced parameters the population loss over a time horizon $k$ is re-interpreted as the summed quadratic distance between the first $k$-th moments of two random variables associated to the students and teachers parameters. 
This allows the application of results from moment matching theory, which guarantee that all moments of the random variables match, when the first $k$ moments do, where $k$ needs to be sufficiently large in dependency of the teachers state space dimension. Noting that balancedness is preserved under gradient flow (GF) implies that zero loss solutions found by GF starting from balanced parameters exhibits perfect interpolation. An approximate version of the result on perfect extrapolation is also provided. 
The theoretical findings are supported by experiments on different models are conducted in order to show the phase transition between perfect and non perfect extrapolation.
strength_and_weaknesses: Strengths:
* The manuscript provides a nice connection of the population loss for parameter estimation in linear RNNs as a moment matching objective. This could be a useful tool for future theoretical works. 
* The theoretical analysis is strong, well supported and clearly laid out.

Weaknesses: 
* *Convergence of training:* A study of convergence properties of training dynamics is not provided. The main contribution of the manuscript is an extrapolation result for balanced students and teachers rather than a result for solutions obtained by gradient descent training. When comparing this to the study of overparametrized networks in the context of supervised learning the manuscript can not explain why overparametrized students are superior. One argument could be improved convergence for these models. 
* *Experiments:* The experimental evaluation of the results could be strengthened in several aspects. Currently, the results shown and discussed in Section 5 are only for a single student size. I think the experiments can easily be strengthened by including more student sizes, more random trials and more sequence lengths. More importantly, I think the relation to the theoretical findings is not discussed in great detail, i.e., whether the transition to perfect extrapolation occurs at the predicted sequence length is not discussed sufficiently. Finally, it could be interesting to add experiments with fixed sequence length and increasing student size since in practice one will have data of a fixed length and will need to set the student size. 
clarity,_quality,_novelty_and_reproducibility: **Clarity.**
The manuscript is written very well and is a smooth read overall. Both the introduced concepts as well as the mathematical proofs are clearly presented and easy to follow. Occasionally, some things could be improved, some concrete thoughts are in the review down below. 

**Quality.**
The proofs are clearly writte, well supported and follow a nice line of thoughts. The experiments are well designed, but results are only presented for a relatively small number of trials and problem sizes. 

**Novelty.** 
The central conceptional contribution is the connection of the population loss of linear RNNs to a moment matching objective, which I appreciate a lot. That being said, the idea is very fundamental and I originally thought it could have been studied in the literature on parameter identification for linear dynamical systems. That being said, I am not an expert in this area and a quick search did not reveal a work giving this intepretation directly.

**Reproducibility.** 
The experiments are well described in the appendix, however, no code is provided. 

summary_of_the_review: The manuscript  provides a valuable contribution in studying the extrapolation properties of linear RNNs through a connection of the population loss of linear RNNs to a moment matching problem. 
My main criticism is presented under **weaknesses**, which concerns the absence of a study of the convergence properties of GF dynamics as well as the realm of the experiments. Where my thoughts regarding additional experiments are outlined above, I want to share a few thoughts on the main message of the paper here:

I believe that the main theorem of the paper is Lemma 7 and Theorem 5 is a corollary of this. Hence, I wonder, whether it might be better to present the results as extrapolation results for balanced students. The same applies to Theorem 8. 

Some other things that caught my eye:
* In Theorem 5, Lemma 7 etc: Do you require $d>k$? Probably this is included since for these regimes Proposition 3 implies that the problem of extrapolation is hard. Nevertheless, putting this as an assumption can convey the message that the result is not true for $d\le k$. 
* In the experiments in Subsectino 5.1: Your empirical results indicate perfect interpolation is reached somewhere between $k = 16$ and $k = 20$, where your theoretical analysis suggest perfect extrapolation for $k>2\hat d = 10$. Is my reading of this correct? If not, what is the correct interpretation of your empirical results? If so, what is your interpretation of the results?
* The second to last paragraph in the conclusion section should be in the discussion of related works or introduction. No new things should be discussed in the conclusion.
* No actual content should be in footnotes or brackets, e.g., footnote 2 should be in the main text. Also in „Figure 1(a) reports the extrapolation error (quantified by the $\ell^\infty$ distance between
the impulse response of the learned student and that of the teacher) as a function of $k$.“ I would simply delete the brackets.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In this paper, the authors analyze the extrapolation properties of gradient descent (GD) when applied to overparameterized linear recurrent neural networks (RNNs). They provide theoretical evidence for learning low-dimensional state spaces that can model long-term memory, in contrast to recent arguments suggesting an implicit bias towards short-term memory. Their results rely on a dynamical characterization of GD and tools developed in the context of the moment problem from statistics. Experiments corroborate their theory, demonstrating extrapolation via learning low-dimensional state spaces with both linear and non-linear RNNs. 

The reviewers thought the problem is interesting, paper is well written for the most part and that investigating SISO linear systems is a good step towards understanding RNNs. Some reviewers thought the scope of the paper is too narrow and focusing only on the linear case is too restrictive and that the authors make "strong and unrealistic assumptions". I read the paper carefully myself. I agree that the assumptions of the paper are restrictive. However, I think the paper is a step in the right direction with an interesting analysis. Therefore, I recommend acceptance.
justification_for_why_not_higher_score: The paper has a restrictive setup which does not merit a higher score.
justification_for_why_not_lower_score: The paper is an interesting step in the right direction. Clearly borderline with some flaws but I think the text of the reviews are a bit lower than the written statements.
Decision: Accept: poster