Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Nets
Authors: Edo Cohen-Karlik
Itamar Menuhin-Gruman
Raja Giryes
Nadav Cohen
Amir Globerson
Venue: ICLR 2023 poster (2023)
Keywords: RNN
gradient descent
implicit bias
extrapolation

Abstract: Overparameterization in deep learning refers to settings where a trained Neural Network (NN) has representational capacity to fit the training data in many ways, some of which generalize well, while others do not. In the case of Recurrent Neural Networks (RNNs) there exists an additional layer of overparameterization, in the sense that a model may exhibit many solutions that generalize well for sequence lengths seen in training, some of which \emph{extrapolate} to longer sequences, while others do not. Numerous works studied the tendency of Gradient Descent (GD) to fit overparameterized NNs with solutions that generalize well. On the other hand, its tendency to fit overparameterized RNNs with solutions that extrapolate has been discovered only lately, and is far less understood. In this paper, we analyze the extrapolation properties of GD when applied to overparameterized linear RNNs. In contrast to recent arguments suggesting an implicit bias towards short-term memory, we provide theoretical evidence for learning low dimensional state spaces, which can also model long-term memory. Our result relies on a dynamical characterization showing that GD (with small step size and near zero initialization) strives to maintain a certain form of balancedness, as well as tools developed in the context of the \emph{moment problem} from statistics (recovery of discrete probability distribution from its moments). Experiments corroborate our theory, demonstrating extrapolation via learning low dimensional state spaces with both linear and non-linear RNNs.

Published as a conference paper at ICLR 2023
LEARNING Low DIMENSIONAL STATE SPACES WITH OVERPARAMETERIZED RECURRENT NEURAL NETS
Edo Cohen-Karlik' Itamar Menuhin-Gruman' Raja Giryes', Naday Cohen' & Amir Globerson 1.2 Tel Aviv University "Google Research
(edocohen, menuhin| J @mail. aau. ac. i1 (raja, cchennadav, gamir ) auex. tau. ac.il
ABSTRACT
Overparameterization in deep learning typically refers to settings where trained neural network (NN) has representational capacity to fit the training data in many ways, some of which generalize well, while others do not. In the case of Recurrent Neural Networks (RNNs), there exists an additional layer of overparameterizaaton, in the sense that a model may exhibit many solutions that generalize well for sequence lengths seen in training, some of which extrapolate to longer sequences, while others do not. Numerous works have studied the tendency of Gradient Descent (GD) to fit overparameterized NNs with solutions that generalize well. On the other hand, its tendency to fit overparameterized RNNs with solutions that extrapolate has been discovered only recently and is far less understood. In this paper, we analyze the extrapolation properties of GD when applied overparameterized linear RNNs. In contrast to recent arguments suggesting an implicit bias towards short-term memory, we provide theoretical evidence for learning low-dimensional state spaces, which can also model long-term memory. Our result relies on a dynamical characterization which shows that GD (with small step size and near-zero initialization) strives maintain certain form balancedness, as well as on tools developed in the context of the moment problem from statistics (recovery of a probability distribution from its moments). Experiments corroborate our theory, demonstrating extrapolation via learning low-dimensional state spaces with both linear and non-linear RNNs.
INTRODUCTION
Neural Networks (NNs) are often overparameterized. in the sense that their representational capacity far exceeds what is necessary for fitting training data. Surprisingly, training overparameterized NNs via (variants of) Gradient Descent (GD) tends to produce solutions that generalize well, despite exis- tence of many solutions that do not. This implicil generalization phenomenon attracted considerable scientific interest, resulting in various theoretical explanations (see, e.g., Woodworth et al. (2020);
: Yun et al. 2020): Zhang et al. (0017) Li et al. (2000) Ji & Telgarsky (2118) Lyu & Li 20 11)).
Recent studies have surfaced new form of implicit bias that arises in Recurrent Neural Networks (RNNs) and their variants (c.g.. Long Short-Term Memory Hochreiter & Schmidhuber (1977) and Gated Recurrent Units Chung al. (2014). For such models, the length of sequences in training is often shorter than in testing, and it is not clear to what extent a learned solution will be able to extrapolate beyond the sequence lengths seen in training. In the overparameterized regime, where the representational capacity of the learned model exceeds what is necessary for fitting short sequences, there may exist solutions that generalize but do not extrapolate, meaning that their accuracy is high over short sequences but arbitrarily poor over long ones (see Cohen-Karlik et al. (2022)). In practice however, when training RNNs using GD, accurate extrapolation is often observed. We refer to this phenomenon as the implicit extrapolation of GD.
As opposed to the implicit generalization of GD, little is formally known about its implicit extrap- olation. Existing theoretical analyses of the latter focus on linear RNNs also known Linear Dynamical Systems (LDS)- - and either treat infinitely wide models (Emami et al., 202T). or models of finite width that learn from memoryless teacher (Cohen-Karlit Karlik al. 2022). In these regimes,

---

Published as a conference paper at ICLR 2023
GD has been argued to exhibit implicit bias towards short-term memory. While such results are informative, their generality remains in question, particularly since infinitely wide NNs are known to substantially differ from their finite-width counterparts, and since memoryless teacher essentially neglects the main characteristic of RNNs (memory).
In this paper, we theoretically investigate the implicit extrapolation of GD when applied to overpa- rameterized finite-width linear RNNs learning from a teacher with memory. We consider models with symmetric transition matrices, in the case where a student (learned model) with state space dimension d is trained on sequences of length k generated by a teacher with state space dimension d. Our interest lies in the overparameterized regime, where d is greater than both and d. meaning that the student has state space dimensions large enough to fully agree with the teacher on sequences of length k while potentially disagreeing with it on longer sequences. As a necessary assumption on initialization, we follow prior work and focus on certain balancedness condition, which is known (see experiments in Johen-Karlik et al.) (2022). as well as our theoretical analysis) to capture near-zero initialization as commonly employed in practice.
Our main theoretical result states that GD originating from a balanced initialization leads the student to extrapolate, irrespective of how large its state space dimension is. Key to the result is a surprising connection to a moment matching theorem from Cohen & Yeredor (201T), whose proof relies on ideas from compressed sensing (Elad) 2010 Eldar & Kutymiok] (012) and neighborly polytopes (Gaee 1963). This connection may be of independent interest, and in particular may prove useful in deriving other results concerning the implicit properties of GI.. We corroborate theory with
experiments, which demonstrate extrapolation via learning low-dimensional state spaces in both the
analyzed setting and ones involving non-linear RNNs.
The implicit extrapolation of GD is an emerging and exciting area of inquiry. Our results suggest that short-term memory not enough for explaining it as previously believed. We hope the techniques developed in this paper will contribute to a further understanding of this phenomenon.
2 RELATED WORK
The study of linear RNNs, or LDS, has a rich history dating back to at least the early works of Kalman (Kalman 1960; [963). An extensively studied question relevant to extrapolation is that of system identification, which explores when the parameters of a teacher LDS can be recovered (see) Ljung (1999). ). Another related topic concerns finding compact realizations of systems, i.e. realizations of the same input-output mapping as a given LDS, with a state space dimension that is lower (see Antoulas (2005)) Despite the relation, our focus is fundamentally different from the above - we ask what happens when one learns an LDS using GD. Since GD is not explicitly designed to find low-dimensional state space, it is not clear that the application of GD to an overparameterized student allows system identification through a compact realization. The fact that it does relate to the implicit properties of GD, and to our knowledge has not been investigated in the classic LDS literature.
The implicit generalization of GD in training RNNs has been a subject of theoretical study for at least several years (see, e.g., Hardt et al.] (016)); Allen-Zhu et al.] (2019); Lim et al. (202T)) In contrast, works analyzing the implicit extrapolation aatiooooaioonnooo of GD have surfaced only recently, specifically in Emami et al.] (021)) and CChhen-Kariii et al. (2022) Emami et al. (2021) analyzes linear RNNs in the infinite width regime, suggesting that in this case GD is implicitly biased towards impulse responses corresponding to short-term memory. Cohen-
et al. (2022) studies finite-width linear RNNs (as we do), showing that when the teacher is memoryless (has state space dimension zero), GD emanating from balanced initialization successfully extrapolates. Our work tackles an arguably more realistic and challenging setting - we analyze the regime in which the teacher has memory. Our results suggest that the implicit extrapolation of GD does not originate from a bias towards short-term memory, but rather tendency to learn fow-dimensional state spaces [ We note that there have been works studying extrapolation in the context of non-recurrent NNs, e.g. Xu et al. (2020).
'There is no formal contradiction between our results and those of (Emami et al. 2021 and (Cohen-Karlik ct al. 2022). These works make restrictive assumptions (namely, the former assumes that the teacher is stable and its impulse response decays exponentially fast, and the latter assumes that the teacher is memoryless) under which implicit extrapolation via learning low- dimeennnsio state spaces leads to solutions with short-term memory. Our work on the other hand is not limited by these assumptions, and we show that in cases where they are violated, learning yields solutions with diw-iiienioonal state spaces that do not result in short-term memory.
2

---

Published as a conference paper at ICLR 2023
This type of extrapolation deals with the behavior of learned functions outside the support of the training distribution, and thus fundamentally different from the type of extrapolation we consider, which deals with the behavior of learned functions over sequences longer than those seen in training.
Linear RNNs fundamentally differ from the commonly studied model of linear (ooed-forward) NNs (see, e.g.. Arora et al. (2018): : Ji & Telgarsky (2018); : |Aroa et al.) (2019a b): Razin & Cohen (2020))
One of the key differences is that a linear RNN entails different powers of a parameter (transition)
matrix, leading a loss function which roughly corresponds to sum of losses for multiple linear NNs having different architectures and shared weights. This precludes the use of a vast array of theoretical tools tailored for linear NNs, rendering the analysis of linear RNNs technically challenging.
On the empirical side, extrapolation of NNs to sequence lengths beyond those seen in training has been experimentally demonstrated in numerous recent works, covering both modern language
and attention models (Press et al. 2022 Anil et al. 2022 Zhang et al. 2022), and RNNs with
transition matrices of particular forms (Gu al. 2022
2021
2020; Guptal 2022). The current paper
is motivated by these findings, and takes a step towards theoretically explaining them.
3 LINEAR RECURRENT NEURAL NETWORKS
Our theoretical analysis applies to single-input single-output (SISO) linear RNNs with symmetric transition matrices. Given state space dimension d E N, this model is defined by the update rule:
s1+1 As; + BrG, Yt = Cs.. t 0, 2.......
(3.1)
where A E Rddd Be Rdx1 and C E Rixd are configurable parameters, the transition matrix A satisfies A AT; To, .I.... R form an input sequence; yo- y/,.... R form the corresponding output sequence; and 8, E Rdx1 represents the internal state at time I, assumed to be equal to zero at the outset (i.e. it is assumed that 80 0). As with any linear time-invariant system (Porat 1996). the input-output mapping realized by the RNN is determined by its impulse response.
Definition 1.
The impulse response of the RNN is the output sequence corresponding to the input sequence (ro, I1, .). = (1,0,
Namely, it is the sequence (CB, BAB, CA
For brevity, we employ the shorthand θ = (,, The d x d symmetric transition matrix A is parameterized through a d(d + 1)/2-dimensional vector holding its upper triangular elements, and with slight overloading of notation, the symbol A is also used to refer this parameterization.
We note that our theory readily extends to multiple-inpul multiple-output (MIMO) networks, and the focus the SISO case is merely for simplicity of presentation. Note also that the restriction to symmetric transition matrices is customary in both theory (Hazan et al. 2018) and practice (Gupta 2022), and represents a generalization of the canonical modal form, which under mild non-degeneracy conditions does not limit generality (Boyd & Lessard 2006).
Given length A input sequence, x (Jo,... ..to..... Fk-1) RR consider the output the last time step, i.e. y : Sk é R. and denote it by RNN (x)). Using this output as a label, we define an empirical loss induced by a training set S = (x(1) (1)
(xl()) y( c I* x R:
(s(A,
1 N
Σ e (RNN (a12)..91))
..))).
(3.2)
where Ely. 0) = (yy 2) is the square loss, By the update rule of the RNN (Equation 3.1. we have:
Cs(A, 1 N Σ Σ CA
Br ( y
(3.3)
Suppose that ground truth labels are generated by RNN defined in Equation 3.1 and denote the state space dimension and parameters of this teacher network by d and è = (A, B, C') respectively. We employ the common assumption (e.g., see Hardt et al. (2016) by which input sequences are drawn from a whitened distribution, i.e. distribution where E [ equals 1 if = j' and 0 otherwise. The population loss over length & sequences can then be written as (see Lemma E.
k-1
C(A. (AA,BC)=
Σ (CA'B-CA')" -
(3.4)
3

---

Published as a conference paper at ICLR 2023
implies that solution ④ (A.B.C) achieves zero population loss over length A: sequences if and only if CAA = ČÁ' for O...., k 1. To what extent does such a solution imply that the student (i.c., the learned RNN) extrapolates to longer sequences? This depends how close CAA is to C.A for j > k.
Equation| 3.4
Definition 2. For e 2 0 and y E N, we say that the student e-extrapolates with horizon q with respect to (w.r..) the teacher if:
-C C VjE (0.1,....9-1}}
(3.5)
If the above holds for all q E N then the student is said to e-extrapolate w.r.t the teacher, and if it holds for all q e N with c = 0 then the student is simply said to extrapolate w.r.f the teacher.
Per Definition 2 e-cxtrapolation with horizon q is equivalent to the first g elements of the student's impulse response being c-close to those of the teacher's, whereas extrapolation means that the student's impulse response fully coincides with the teacher's. s. The latter condition implies that the student realizes the same input-output mapping as the teacher, for any sequence length (this corresponds to the notion of system identification; see Section 2
Notice that when the student is overparameterized, in the sense that d is greater than k: and d, it may perfectly generalize, i.e. lead the population loss over length & sequences (Equation 3.4) to equal zero, and yet fail to extrapolate, as stated in the following proposition.
Proposition 3. Assume d k; and let O and q E {k + 1, + 2....). Then, for any teacher parameters Ô there exist student parameters & with which the population loss in Equation 3.4 equals zero, and yet the student does not e-extrapolate with horizon q.
Proof sketch (for complete proof see Appendix E.1.2 The result follows from the fact that the first d
elements of the student's impulse response can be assigned freely via a proper choice of O.
We are interested in the extent to which student parameters learned by GD extrapolate in the overparameterized regime. Proposition Bjimplie that, regardless of how many (length k) sequences are used training, if GD leads to any form of extrapolation, must be a result of some implicit bias induced by the algorithm. Note that in our setting, extrapolation cannot be explained via classic tools from statistical learning theory, as evaluation over sequences longer than those seen in training violates the standard assumption of train and test data originating from the same distribution.
To decouple the question of extrapolation from that of generalization, we consider the case where the training set S' is large, more formally, where the empirical loss Ls(-) (Equation 3.3) is well represented by the population loss C(-) (Equation 3.4). We model GD with small step size via Gradient Flow (GF), customary in the theory of NNs see Saxe et al. (2013); Gunasckar et al. (2017); Arora et al.] (2018) 2019b); Lyu & Li (2019h Li et al. (2020); Azulay et al. (2021) for examples where is used and Elkabetz & Cohen (221)) for theoretical justification of its usage. Using the GF formulation, we analyze the following dynamics:
à a(7) = a - C(AG), (()))))))_ B(T) C(T)) T 0,
(3.6)
where [A. C}. If no assumption on initialization is made, no form of extrapolation can be established (indeed, the initial point may be a global minimizer of C(-) that fails to extrapolate, and GF will stay there). Following prior work (see Cohen- et al. (2022)), we assume that the initialization adheres to the following balancedness condition:
Definition 4. An RNN with parameters O (A, B, C") is said to be balanced if B CT
was shown empirically in (Cohen-Karli, et al. (2022) that the balancedness condition captures near-zer zero initialization as commonly employed in practice. We support this finding theoretically in Section 4.3 Aside from the initialization of the student, we will also assume that the teacher adheres to the balancedness condition.
4 THEORETICAL ANALYSIS
We turn to our theoretical analysis. Section 4.1 proves that in the setting of Section 3 convergence of GF to zero loss solution leads the student extrapolate, irrespective of how large its state space
4

---

Published as a conference paper at ICLR 2023
extends this result by establishing that, under mild conditions, approximate convergence leads to approximate extrapolation. The results of sections 4.1 and 4.2 assume that GF emanates from balanced initialization, which empirically is known to capture near-zero initialization as commonly employed in practice (see Section B) Section 4.3 theoretically supports this empirical premise, by showing that with high probability, random near-zero initialization leads balancedness.
dimension is. Section 4.2
We introduce notations that will be used throughout the analysis. For a matrix Q Rmxx, we let [|Q] F. Q) and |[Q]] 2/ denote the Frobenius, &o and &2 (spectral) norms, respectively. For a vector t E R" we use 0 to denote the Euclidean norm and U; to denote its jth entry.
4.1 CONVERGENCE LEADS TO EXTRAPOLATION
Theoretical analyses of implicit generalization often assume convergence solution attaining zero loss (see, e.g., Azulay et al. (22II); Gunasckar et al. (0177; Lyu & Li (019); Woodworth et al. (2020)). Under such an assumption, Theorem 5 below establishes implicit extrapolation, i.e. that the solution to which GF converges extrapolates, irrespective how large the student's state space dimension d is. A condition posed by the theorem is that the training sequence length is greater than two times the teacher's 's state space dimension d. This condition is necessary see Appendix A for theoretical justification and Section for empirical demonstration.
Theorem 5. Assume that d > k 2d, the teacher parameters Ô are balanced (Definition 4. and the student parameters & are learned by applying GF to the loss L(.) (Equation 3.4) starting from balanced initialization. Then, if GF converges to point O* satisfying L(O 0, this point
extrapolates (Definition
In order to prove Theorem
introduce two lemmas: Lemma 6 which shows that balancedness is preserved under GF; and Lemma 7 which (through surprising connection to a moment problem from statistics) establishes that balanced solution attaining zero loss necessarily extrapolates. With Lemmas and 7 in place, the proof of Theorem B readily follows.
Lemma 6. Let ((T), with t > O, be curve brought forth by applying GF to the loss L()) starting from a balanced initialization. Then, @(T) is balanced for every 2 0.
Proof sketch (for complete proof see Appendix E.1.5). The result follows from the symmetric role of B and C in the loss f(-).
Lemma 7. Suppose that d > k > 2d, the teacher is balanced, and that the student parameters θ are balanced and satisfy L(O) O. Then O extrapolates.
Proof sketch (for complete proof see Appendix E.2 The proof is based on surprising connection that we draw to the moment problem from statistics (recovery of a probability distribution from its moments), which has been studied for decades (see, e.g.. .g.,Scchüdgeen (2017)).
Without loss generality, we may assume that Á diagonal (if this is not the case then we apply an orthogonal eigendecomppositinn to A and subsequently absorb eigenvectors into B and C). We may also assume that ČВ (otherwise we absorb a scaling factor into B and/or C). Since ČT = B (teacher is balanced), summing up to one) f e Rdd via PÚ = C,B., 1,..., d. We let denote the random variable supported on (A1,1,-.. A A,aā which assumes the value A.S with probability Pi. i 1,...,d d. Notice that for every E N:
may define probability vector (i.c. vector with non-negative entries
ČÁB Σ P.A. = B[
meaning that the elements of the teacher's impulse response are precisely the moments of 2.
Similarly to above we may assume A is diagonal, and since (()) = 0 it holds that CB ČB - We may thus define a probability vector p E IRd via p; C,B. i 1,..., d, and random variable Z which assumes the value A, with probability pt, L,.., d. For every j N:
CA'B Ex, M E[
and the elements of the student's impulse response are precisely the moments of Z.
5

---

Published as a conference paper at ICLR 2023
The probabilistic formulation we set forth admits interpretation of extrapolation a moment problem. Namely, since [()) = (i.e. CA ČÁ' B for = O,..., k- 1) the random variables Z and 2 agree their first l-- moments, and the question is whether they agree all higher moments as well. We note that this question is somewhat more challenging than that tackled in classic instances of the moment problem, since the support of the random variable whose moments we match (2) is not known to coincide with the support of the random variable we seek to recover (2). Luckily, recent powerful result allows addressing the question we face -Cohen & Yeredor (201T)
showed that the first 2n moments of a discrete random variable X taking at most E N values uniquely define X, in the sense that any discrete random variable agreeing with these 2n moments must be identical to X. Translating this result to our setting, we have that if Z agrees with 2 on its first 2d moments, it must be identical to Z, and particular it must agree with 2 on higher moments as well. The fact that k - > 2d then concludes the proof.
To attain some intuition for the result we imported from Cohen & Yeredor (201T) consider the simple case where d = 1. The transition matrix A is then scalar à E R. the random variable 2 is deterministically equal to à and the teacher's impulse response is given by the moments B[2"] a², j 0, 1,..... ..... Since we assume k 2d, the fact that L()) 0 means the random variable corresponding to the student, Z, agrees with the first two moments of 2. That is, Z satisfies B[z]= à and [=] a². This implies that Var [2] R[ - E[ 0, and therefore Z is
deterministically equal to â, i.e. it is identical to 2. The two random variables thus agree on all of their moments, meaning the impulse responses of the student and teacher are the same.
Proof of Theorem 5 By Lemma
6 (as well continuity considerations) O+ is balanced. Therefore, Lemma 7 limplis that it extrapolates.
4.2 APPROXIMATE CONVERGENCE LEADS TO APPROXIMATE EXTRAPOLATION
Theorem in Section 4.1 proves extrapolation in the case where GF converges to a zero loss solution.
Theorem below extends this result by establishing that, under mild conditions, approximate convergence leads to approximate extrapolation or more formally - for any e >> 0 and q E N, when GF leads the loss to be sufficiently small, the student e-extrapolates with horizon q.
Theorem 8. Assume the conditions of Theorem 5 and that the teacher parameters é are stable, i.e. the eigenvalues of A are in [-1,1]. Assume also that Q are -egeeeeeee,,te, in the sense that the input-outuut mapping they realize is not identically zero. Finally, assume that the student parameters @ learned by GF are confined to some bounded domain in parameter space, Then, for any > 0 and q N, there exists ò(e, q) > O such that whenever ((O) & ö(e, q), the student e-extrapolates with horizon q.
Proof sketch (for complete proof see Appendix E.3 Let 5 > be a constant whose value will be chosen later, and suppose GF reached point ② satisfying ((O) < 8.
Following the proof of Lemma Ô is identified with a distribution supported on the eigenvalues of Å. whose jth moment is mi CA' BA'B(C BCCB) for every j E N. Similarly, O is identified with dis- tribution supported on the eigenvalues of A, whose jth moment is m, == CA B(CB) for every j N. The fact that (()) & 8 implies ICB CB & v8, and in addition |n myl & ((v8)
for every j = 1...., ......, lo 1. To conclude the proof suffices to show that
|m myl & O(c) Vj (1....,9-1 1}
(4.1)
given a small enough choice for 8 (this choice then serves as 5(c, q) in the theorem statement).
We establish Equation 4.1 by employing the theory of Wasserstein distances (Vaserstein 1969).
For p E N. denote by Wp the p-Wasserstein distance between the distributions identified with e
and @ Since k: 2d, it holds that jmj myl & O(vō) for every j 1,... 2d. Proposition 2 in
Wu & Yang (020)) then implies Wi & ( For any P E N. W & O(W)/P) (see Section 2.3
in Panaretos & Zemel (2019)) and |mp mpl & O(W,) (see Section 1.2 in Biswas & Mackey
(2021)) Combining the latter three inequalities, we have that pmp m,l & O (ppp for any E N. (E (d(())))) therefore establishes Equation 4.
Choosing 8

---

Published as a conference paper at ICLR 2023
4.3 BALANCEDNESS CAPTURES HERR-ZERO INITIALIZATION
Theorems and assume that GF emanates from a balanced initialization. i.e. from a point (A, B C' satisfying B C It was shown in Cohen-Karlik al. (0022) that theoreti- cal predictions derived assuming balanced initialization faithfully match experiments conducted with near-zero initialization (an initialization commonly used in practice). Proposition y below theoreti- cally supports this finding, establishing that with high probability, random near-zero initialization leads GF arrive at an approximately balanced point, i.e. a point @ (A, C) for which the difference between B and C is negligible compared to their size.
Proposition 9. Suppose that: (i) d > 20; (ii) the teacher parameters é are balanced and are non-degenerate, in the sense that the input-outpin mapping they realize is not identically zero; and (iii) the student parameters are learned by applying GF the loss [(-). Let θ be random point in parameter space, with entries drawn independently from the standard normal distribution. For >> O, consider the case where GF emanates from the initialization c and denote the resulting curve by (r( (A) (e(T,,C(TT) with T > O. Then, w.p. least 0.75, for every > O there exists e 0 such that:
(T,) C. (Te)lL= 0.
lim 0+ (T( + C. (Te)]lF
(4.2)
Proof sketch (for complete proof see Appendix[E.4 The idea behind the proof is as follows. Assume e is sufficiently small. Then, when the entries of = (A, B, C) are on the order of e, we have
0 AB (()) -2CB. CT and
8C [(e) -CCB B This implies that during the first part of
the curve (T) it holds that (B.(r) C. (T) -2CB (B) C. (T) and similarly de (B.(T) + CT(T)) x 2CB (B.(T) (T)).. Since ČB > 0 (follows from the teacher parameters being balanced and non-degenerate), the entries of Bz( C. (r) shrink exponentially fast while those of (T) + (T) grow the same rate. This exponential shrinkage/growth leads (T) - (T)l (T) + C. (T) to become extremely small, more so the smaller c is.
5 EXPERIMENTS
In this section we present experiments corroborating our theoretical analysis (Section 4 The latter establishes that, under certain conditions, linear RNN with state space dimension d extrapolates when learning from teacher network with state space dimension d via training sequences of length irrespective of how large d is compared to d and k. A key condition underlying the result is that k is larger than 2d. Section 5.1 5.11 below considers the theoretically analyzed setting, and empirically evaluates extrapolation as & varies. Its results demonstrate phase transition, in the sense that extrapolation takes place when k > 2d, in compliance with theory, but fails when & falls below 2d, in which case the theory indeed does not guarantee extrapolation. Section 5..2 displays the same phenomenon with linear RNNs that do not adhere to some of the assumptions made by the theory (in particular the assumption of symmetric transition matrices, and those concerning balancedness). Finally, Section [5.3 considers non-linear RNNs (specifically, Gated Recurrent Unit networks Chung et al. ())14)), and shows that they too exhibit phase transition in extrapolation as the training sequence length varies. For brevity, we defer some of the details behind our implementation, as well as additional experiments, to Appendix B
5.1 THFORETICALLY ANALYZED SETTING
Our first experiment considers the setting described in Section ald theoretically analyzed in Sec- tion 4 As representative values for the state space dimensions of the teacher and (overparameterized) student, we choose d 5 and 40 respectively (higher state space dimensions for the student, namely d = 100 and d = 200, yield qualitatively identical results). For given training sequence length k. the student is learned via GD applied directly to the population loss defined in Equation [3.4] (applying GD to the empirical loss defined in Equation 3.3 with N 10, 000 training examples, led to similar results). Figure [a) reports the extrapolation error (quantified by the Exx distance between the impulse response of the learned student and that of the teacher) extrapolation exhibits a phase transition that accords with our theory: when l > 2d extrapolation error is low, whereas when & falls below 2d extrapolation error is high.
function of k. As can be seen,
7

---

Published as a conference paper at ICLR 2023
5.2 OTHER SETTINGS WITH LINEAR RECURRENT NEURAL NETWORKS
To assess the generality of our findings, we experiment with linear RNNs in settings that do not adhere to some of the assumptions made by our theory. Specifically, we evaluate settings in which: (i) the teacher is unbalanced, meaning B * C and its transition matrix Á non-symmetrie; (ūi) the student's s transition matrix A is not restricted to be symmetrie; (iii) learning is implemented by optimizing the empirical loss defined in Equation 3.3 (rather than the population loss defined in Equation 3.4); and (iv) optimization is based on Adam Kingma & Ba (2014) (rather than GD), emanating from standard near-zero initialization which is generally unbalanced (namely, B * C' Figure (bb reports the results of experiment where the state space dimensions of the teacher and (overparameterized) student are d = 10 and d = 50 respectively (higher state space dimensions for the student, namely d = 100 and d 200, yield qualitatively identical results), and where the teacher implements a delay line of d time steps (for details see Appendix C.2.2). Similar results obtained with randomly generated teachers are reported in Appendix [ As can be seen, despite the fact that our theory does not apply to the evaluated settings, its conclusions still hold extrapolation errr is low when the training sequence length & greater than 2d, and high when & falls below 2d.
0.4
0.2
00
22 24
20
12
14
16
10
26 20
(a) Theoretically analyzed setting
(b) Other setting with linear RNN
Figure 1: Demonstration of implicit extrapolation with linear RNNs. Plots show extrapolation error (average over three random seeds, with shaded region marking standard deviation) as a function of training sequence length k., for student with state space dimension d learning from teacher with state space dimension d, where d >> d. (a) Models adhere to the setting described in Section 3
and theoretically analyzed in Section 4 with d 5, d 40. (b) Models do not adhere to some of the assumptions made by the theory, and d = 10, d = 50. Notice that extrapolation exhibits a phase transition that accords with theory when k > 2d extrapolation error is low, and when k falls below 2d extrapolation error is high. The gradual transition exhibited is due to numerical errors introduced by the optimization not reaching exact global minimum. For further details see Sections and Appendix B
5.1 and 5.2
5.3 NON-LINEAR RECURRENT NEURAL NETWORKS
As a final experiment, we explore implicit extrapolation with non-linear RNNs, namely GRU networks. Specifically, evaluate the extent to which student GRU with state space dimension dy 100 extrapolates when learning from a teacher GRU with state space dimension dy 10 (higher state space dimensions for the student, namely d, 200 and dy 500, yield qualitatively identical results). The student is learned by optimizing an empirical loss comprising training sequences of length kg. where kg is predetermined. Optimization is based on Adam emanating from standard near- zero initialization. Figure 2 a) reports the extrapolation error (quantified by the Eor distance between the response of the learned student and that of the teacher, averaged across randomly generated input sequences) for different choices of kg. As can be seen, similarly to the case with linear RNNs (see Sections 5. and 5.2). there exists a critical threshold for the training sequence length ky above which extrapolation error is low and below which extrapolation error is high (note that this critical threshold is around four times the teacher's s state space dimension, whereas with linear RNNs the critical threshold was around two times the teacher's state space dimension; theoretically explaining this difference is an interesting direction for future work). Figure (bb displays the average output response over different inputs of the teacher alongside those of two students one trained with
8

---

Published as a conference paper at ICLR 2023
1.00
Teacher
0.75
Student (k=30)
0.50
60)
-050
-0.75
100
(a) Extrapolation training sequence length
(b) Average output over several inputs
Demonstration of implicit extrapolation with non-linear RNNs, namely GRU networks. Plots show results for student with state space dimension dg = 100 learning from a teacher with state space dimension dy 10 using training sequences of length kig where Kg varies. (a) Extrapolation error (average over ten random seeds, with shaded region marking standard deviation) as a function of kgg. (b) Average output over several imputs of teacher and student for different choices of kg. Notice that, similarly to the case with linear RNNs, there exists critical threshold for kg above which extrapolation error low and below which extrapolation error high. See details in Appendix
Figure 2:
sequences of length k, = 30, and the other with sequences of length Kg 60 As expected, the impulse response of each student tracks that of the teacher for the first Kg time steps (where K, is dedddentdeeendent)... However, while the student for which kg = 30 fails to track the teacher beyond kg time steps, the student for which hg 60 succeeds, thereby exemplifying implicit extrapolation.
CONCLUSION
This paper studies the question of extrapolation in RNNs, and more specifically, of whether student RNN trained on data generated by a teacher RNN can capture the behavior of the teacher over sequences longer than those seen in training. We focus overparameterized students that can perfectly fit training sequences while producing a wide range of behaviors over longer sequences. Such student will fail to extrapolate, unless the teacher possesses certain structure, and the learning algorithm is biased towards solutions adhering to that structure. We show - theoretically for linear RNNs and empirically for both linear and non-linear RNNs that such implicit extrapolation takes place when the teacher has low dimensional state space and the learning algorithm is GD.
Existing studies of implicit extrapolation in (linear) RNNs (Emami al. 2022) suggest that GD is biased towards solutions with short-term memory. While low dimensional state space and short-term memory may coincide in some cases, in general they do not, and solution with low dimensional state space may entail long-term memory. Our theory and experiments show that in settings where low dimensional state space and short-term memory contradict each other, the implicit extrapolation chooses the former over the latter.
2021 1
Cohen- Karlik et al.
An important direction future work is extending our theory to non-linear RNNs. We believe possible, in the same way that theories for linear (feed-forward) NNs were extended to account for non-linear NNs (see, c.g., Razin et al. (2021 2022): Lyu & Li (2019)). An additional direction to explore is the applicability of our results to the recently introduced S4 model (Gu et al. 2022).
ACKNOWLEDGEMENN
This work was supported by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant ERC HOLI 819080), the Tel-Aviv University Data-Science and AI Center (TAD), a Google Research Scholar Award, Google Research Gift, the Yandex Initiative in Machine Learning, the Israel Science Foundation (grant 1780/21), Len Blavatnik and the Blavatnik Family Foundation, and Amnon and Anat Shashua.
Note that with GRU networks, in contrast to linear RNNs, the impulse response does not identify the input-output mapping realized by network. It presented in Figure b) for demonstrative purposes.

---

Published as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. Advances in neural information processing systems, 32, 2019.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur, Exploring length generalization in large language models. arXiv preprint 0rXiv:2207.04901, 2022.
Athanasios Antoulas. Approximation of large-scale dynamical systems. SIAM, 2005.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pp. 244 253. PMLR, 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. International Conference on Learning Representations (ICLR), 2019a.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems (NeurlPS), pp. 7413-7424, 2019b.
Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. International Conference on Machine Learning, pp. 468-477. PMLR, 2021.
Niloy Biswas and Lester Mackey. Bounding wasserstein distance with couplings. arXiv preprint 1r..v:2/12.03/522 2021.
S Boyd and I. Lessard. Ee263:
Introduction to linear dynamical systems. Online Lecture Notes, Stanford University, Spring Quarter, 2007, 2006.
Junyoung Chung. Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint 141.:555 2014.
Anna Cohen and Arie Yeredor. On the use of sparsity for recovering discrete probability distributions from their moments. In 2011 IEEE Statistical Signal Processing Workshop (SSP), pp. 753-756. IEEE, 2011.
Edo Cohen-Karlin Avichai Ben David, Nadav Cohen, and Amir Globerson. On the implicit bias of gradient descent for temporal extrapolation. International Conference on Artificial Intelligence and Statistics, 2022.
Michael Elad.
Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer Publishing Company, Incorporated, 2010.
Yonina C. Eldar and Gitta Kutyniok. Compressed Sensing: Theory and Applications. Cambridge University Press, 2012.
Omer Elkabetz and Nadav Cohen. Continuous vs. discrete optimization of deep neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Melikasadat Emami, Mojtaba Sahraee- Ardaake,, Parthe Pandit, Sundeep Rangan, and Alyson K. Fletcher. Implicit bias of linear rnns, 2021.
David Gale. Neighborly and cyclic polytopes. In Proc. Sympos. Pure Math, volume 7, pp. 225-232, 1963.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. Advances Neural Information Processing Systems, 33: 1474-1487, 2020.
10

---

Published as a conference paper at ICLR 2023
Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Combining recurrent, convolutional, and continuous-time models with linear state space layers. Advances in Neural Information Processing Systems, 34, 2021.
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Ankit Gupta. Diagonal state spaces are as effective structured state spaces. arXiv preprint arXiv:2203.14343, 2022.
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. arXiv preprint arXiv: 1609.0519,, 2016.
Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Spectral filtering for general linear dynamical systems, Advances Neural Information Procexsing Systems, 31, 2018.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8):
1780, 1997. doi: 10.1162/neco.1997.1 1997.9.8.1735.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2018.
Rudolf E Kalman. On the general theory of control systems. In Proceedings First International Conference on Automatic Control, Moscow, USSR, pp. 481-492, 1960.
Rudolf Emil Kalman. Mathematical description of linear dynamical systems. Journal of the Society for Industrial and Applied Mathematics, Series A: Control, 1(2):152-122, 1963.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1rXiv:1412.6988. 2014.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pp.
2000.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint ar arXiv:20/2.09889, 2020.
Soon Hoe Lim, N Benjamin Erichson, Liam Hodgkinson, and Michael W Mahoney. Noisy recurrent neural networks. Advances in Neural Information Processing Systems, 34:5124-5137, 2021.
Lennart Ljung. System identification. Wiley encyclopedia of electrical and electronics engineering, pp. 1-19, 1999.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2019.
Victor M Panaretos and Yoav Zemel. Statistical aspects of wasserstein distances. Annual review of statistics and its application, 4310,-431, 2019.
Boaz Porat, course in digital signal processing. John Wiley & Sons, Inc., 1996.
Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022.
Noam Razin and Naday Cohen. Implicit regularization in deep learning may not be explainable by norms. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. International Conference Machine Learning (ICMI.), 2021.

---

Published as a conference paper at ICLR 2023
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factor- ization and deep convolutional neural networks. International Conference on Machine Learning (ICML), 2022.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprini urXiv: 2013.
Konrad Schmüddeen. The moment problem, volume 9. Springer, 2017.
Leonid Nisonovich Vaserstein. Markov processes over denumerable products of spaces, describing large systems of automata. Problemy Peredachi Informatsii, 5(3):64-72, 1969.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pp. 3635-3673. PMLR, 2020.
Yihong Wu and Pengkun Yang. Optimal estimation of gaussian mixtures via denoised method of moments, The Annals of Statistics, 48(4):1981-207) 2020.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint 1rXiv:2009.11844 2020.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. wtwp://wwwwetttonmommeme/emeam http://forrmmmmddyyyyeee Sy 9xx
OpenReview.net, 2017. URL
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: a synthetic reasoning task. arXiv preprint arXiv:2206.04300) 2022.
12

---

Published as a conference paper at ICLR 2023
A NECESSITY OF LOWER BOUND ON TRAINING SEQUENCE LENGTH
Our theoretical guarantees of implicit extrapolation (Theorems 5 and assumed that the training sequence length & is greater than two times the teacher's state space dimension d. Below we show that this assumption is necessary (up to a small additive constant). More precisely, we prove that if & 2d- - 1, implicit extrapolation cannot be guaranteed.
Lemma A.1. For any d N, there exist two configurations of teacker parameters θ - (A,, Bi, Cj) and θ₂ = (A,, B2, C2), both balanced (Deffnitionn)) stable (meaning the eigenvalues of A and A in [-1, 1]) and non-degenerate (meaning the input-oupuut mappings realized by Q and O₂ not identically zero), such that:
B B1A,Ci=B2AA3 1.:0i=B2AA
BB2A/02 for all j = 0, 1..... .2....dd 2d
and yet:
BIACCI BrAjCs for j 2d 1.
Proof. A derivation as in the proof sketch of Lemma shows that any d-atomic distribution (i.e. any distribution supported on a set of d real numbers) can be associated with a balanced configuration of such that the values to which the distribution
teacher parameters θ (Á, B, C') satisfying ČB assigns non-zero probability are the eigenvalues of Á, and the jth moment of the distribution is equal to CÁ. for every j N. light of this, and of the fact that any configuration of teacher parameters θ = (A, B, C) satisfying C'B is non-degenerate (the first element of its impulse response is non-zero), it suffices to prove that there exist two d-atomic distributions supported on [-1, 1] which agree on their first 2d 2 moments yet disagree their (2d th moment. This follows from Lemmas 4 and 30 in Wu & Yang (2020).
Corollary A.2. Assume the conditions of Theorem 5 but with > 2d replaced by k & 2d Then, the stated result does hold, i.e. GF may converge to a point O* satisfying L()*)
0 which does not extrapolate (Definition 2}. Similarly, replacing k > 2d by k & 2d - in the conditions of Theorem 8 renders the stated result false, meaning there exist e > and q E N such that for every 0, there is some & satisfying ((H) & 5 which does not e-extrapolate with horizon (Definition
Proof. In the context of either Theorem or Theorem 8 if 2d-1 then by Lemma A.1 there exist two configurations of teacher parameters both satisfying the conditions of the theorem which lead different impulse response (Definition] [ yet induce the same loss 2(-) (Equation (3.4p. If the result stated in the theorem were true, it would mean extrapolation, or e-extrapolation with horizon for arbitrarily small e > and arbitrarily large q E N (see Definition 2, simultaneously with respect to both teachers, and this leads to contradiction.
B FURTHER EXPERIMENTS
In this section we provide additional experiments that are not included in the main manuscript due to space constraints.
B. BALANCED TEACHER
In Section 5.1
we have experimented with our proposed thcoretical setup. In this section we provide additional figures and experiments.
B.1.1 UNBALANCED STUDENT
In this experiment we use the same balanced teacher with d= as done in Section 5.1 Instead the diagonal student with balanced initialization, sampled from Gaussian with scale 10 and = 40. Results are depicted Figure a). similar phase transition phenomenon to the one in Figure T found also here.
use general (non-diagonal) student with weights
13

---

Published as a conference paper at ICLR 2023
1.-
025
023
0.4
043
010
093
002
10
14
16
16
30
26
10
15
16
Segaones tangth
Sengare gmch
(a) Balanced teacher and general (unbalanced) student (h) Random (unbalanced) teacher and general (unbal- anced) student
function of the training sequence length k. (a) balanced teacher with state dimensions d 5 and general (unbalanced and non diagonal) student with d 40. (b) random unbalanced teacher (see Section B.2) with dimension d 5, and student that has non-diagonal transition matrix and is trained with standard (small) initialization, with state dimension 50. In both plots results are averaged over 3 seeds.
Figure 3: Extrapolation
0.8
Extrapolation
0.6
Initialization Scale
0.2
6.01
0.001
10
12
14
16
10
20
22
24
25
k
Figure 4: Extrapolation error as a function training sequence length k for different initialization scales. Extrapolation error increases along with the scale of initialization.
B.1.2 EFFECT OF THE INITIALIZATION SCALE
Proposition 9 provides theoretical support for the fact that under near-zero initialization, the learned RNN tends to balancedness, which according theorems and guarantees extrapolation. Below we empirically explore the impact of varying the initialization scale. We use the same setting as in Section B.I.I and repeat the experiment with different initialization scales for the students' weights.
As can be seen in Figure the extrapolation deteriorates for larger initialization scale, in the sense that it requires longer training sequences for getting good extrapolation error. This suggests that the condition of small initialization required by our theory is not an artifact of our proof technique, but rather necessary condition for extrapolation occur.
B.2 UNBALANCED TEACHER
In Section 5.2 have tested the extrapolation with respect to specific unbalanced teacher and have observed a similar phase transition as predicted by the theory of Section and empirical evaluation of Section 5.1 Here show that the phase transition not limited to the specific teacher discussed by
14

---

Published as a conference paper at ICLR 2023
0.8
Teacher
0.7
Student (k=10)
0.6
Student (k=20)
0.4
0.3
0.2
0.1
0.0
10 20 30
50
Figure 5: Balanced teacher and student impulse response. Students trained with: A = 10, 20 with respect to the balanced teacher described in Section C.2.I As can be seen, both students track the teacher up to the & used in training, for k = 10 there is no extrapolation for larger values of k whereas 20 tracks the teacher well beyond the sequence length used in training.
testing with respect to randomly generated unbalanced (non nonndiagonall) teacher (see Section C.2.2) The teacher is set to = 5 and student to d = 50. Results are presented in Figure (b). Here too we can observe the phase transition phenomena.
B.3 IMPULSE RESPONSE FIGURES
In Section 5 we have presented the extrapolation performance in different settings. In order better convey the meaning of extrapolating vs non-extrapolating solutions we present here figures of the impulse response of different models.
We start with the impulse response corresponding to the experiment described in Section 5.1 depicts the balanced teacher with d = and two selected students (with d = 40), one trained with 10 and the other with 20.
Figure
We can see that the student trained with k = 10 tracks the teacher several steps beyond the 10th time step and then decays to zero. For 20 we can see near perfect extrapolation for the horizon evaluated.
Next we turn to Section and depict the average impulse responses (Figure 6 of the "delay teacher" and the students trained with respect to the mentioned teacher.
Since the teacher here has d 10, model trained with k 8 is trained with respect to the impulse response (see Section C.2.2 for details on delay teacher), and as expected results with the that for k 18 the student diverges from the teacher shortly after the 18th time step. For l = 20 we can see near perfect extrapolation up to the horizon considered.
'zero' solution.
C IMPLEMENTATION DETAILS
All the experiments are implemented using Py PyToch.
C.I OPTIMIZATION
In Section 5.
we optimize the population loss, which entails minimizing Equation 3.4 with respect to the parameters of the learned model. We use 15K optimization steps with Adam optimizer and learning rate of 10-3. In this experiment, the results were not sensitive to the initialization scale of the (balanced) student. In Section 5.2 and Section (5.3) in the experiments that involve minimizing the empirical loss, we use 50K optimization steps with early stopping (most experiments required less than 10K steps). The batch size is set to 100, data is sampled from Gaussian with zero mean
15

---

Published as a conference paper at ICLR 2023
1.00
0.75
0.50
0.25
0.00
00.5
Teacher
Student (k=8)
-0.50
Student (k= 18)
-0.75
Student (k=20)
-1.00
20
40
60 80 100
Figure 6: Unbalanced teacher (delay) and student impulse response. Students trained with:
k 8, 18, 20 with respect the unbalanced delay teacher described in Section S.22ion[C...2 We can that for k = 18 the student diverges for longer sequences while k 20 which is trained for merely two additional time steps extrapolates and tracks the teacher almost perfectly.
and scale of 1. Experiments were not sensitive to most hhper--ypramaee parameters other than learning rate and initialization scale. The examination of the effect of initialization scale presented in Section B..12 done with learning rate scheduler tor torch. opt im. r__sheddulee SerauleerMMr Mu Mtt...ulitttttet.e. tistepLR using milestones [5000, 10000, 15000, 15000,30000) and decaying factor of 0.1.
C.2 TEACHER GENERATION
One of the main challenges in empirically evaluating extrapolation is that randomly sampling weights from a Gaussian distribution may result with RNN of lower effective rank (i.e. the resulting RNN may be accurately approximated with another RNN with smaller hidden dimension). We will now describe the teacher generation scheme for the different experiments.
C.2.1 BALANCED TEACHER GENERATION
balanced teacher consists of d entries corresponding to the diagonal teacher and d entries repre- senting B ČT In order avoid cases of rapid decay the impulse response on the one hand, and exponential growth on the other, we set the eigenvalues to distribute uniformly between 0.6 and 1.05. The values of B and Ó' are randomly sampled from Gaussian around 0.5 and scale I and then normalized such that ČB 1.
C.2.2 UNBALANCED TEACHER GENERATION
In this experiment, the teacher has a general (non-symmetrid) matrix Á and B * ÔT, We set the weights described next.
Delay Teacher 'delay' teacher has an impulse response at time step = d 1, that is, the teacher has impulse response of (O....,0, 0, ...... ). In order to generate the mentioned impulse response we set the weights as follows,
0
1
0
and C
(C.I)
0
0
0
Note that B, C above set extract the last entry of the first row of A' and A is Nilpotent shift matrix. It is straightforward verify that C.A.B B 1 for i d- 1 and 0 otherwise.
16

---

Published as a conference paper at ICLR 2023
Random Unbalanced Teacher The second unbalanced teacher is randomly generated. In order to avoid the caveats mentioned in Section B.1 we randomly sample the diagonal (from a Gaussian with zero mean and scale 0.1) and super diagonal (from Gaussian with mean 0.7 and scale 0.1) of A. We set B, C' as in equation C.T. The structure A ensures similar properties to that the delayed teacher, specifically, that the first entries of the impulse response is zero and the teacher is 'revealed' only after time steps.
C.2.3 NON-LINEAR TEACHER GENERATION
As opposed to the linear teacher discussed in previous sections, when the teacher is Gated Recurrent Units (GRU), it is unclear how to generate non-trivial teacher. When randomly generating a teacher GRU the result is either trivial model that quickly decays to zero or teacher with an exploding impulse response (depending on the scale of the initialization). In order to produce a teacher with interesting extrapolation behaviour, we initialize a model with an initialization scale of 10-6 and train for 1000 step the model to mimic an arbitrarily chosen impulse response. The result of the mentioned procedure is a teacher GRU with non-trivits behaviour. Figure (2]b shows that we get with this non-trivial teacher the phase transition phenomena described in Section 5.3
C.3 EXTRAPOLATION ERROR
The concept of extrapolation is very intuitive, and yet it does not admit any standard error measure. proper extrapolation error measure should: (a) capture fine differences between two models with good extrapolation behaviour; and on the other hand, (b) be insensitive to the scale in which two non-extrapolating model explode. natural approach which we take here is report the loo norm difference on the tail of the impulse response. A model is considered non non-exxrapolating if the extrapolation error is worse than the extrapolation error of trivial solution which has an impulse response of zeros.
D ACCUMULATING LOSS
In the main paper the analysis is performed for the loss function defined in Section 3 which corresponds to a regression problem over sequences. Another important and common loss function is an accumulating loss defined over the full output sequence. Specifically, the empirical loss of Equation 3.3 is replaced with,
N 1-1
(s(A,B,C) =
ΣΣ
RRNN .)).
(D.1)
=1
In this section we discuss the adaptations required to accommodate our theory with the loss defined
in Equation D.I
D.1 POPULATION LOSS
A similar derivation of the population loss described in Appendix E.I.] can be applied to Equation D.I The difference that an additional summation introduced and is preserved throughout the analysis to result with.
k-1 = ΣΣ (CA'B- - ww:)²
E E CRNN (1z) 95)
(D.2)
j= i=
The loss above can be viewed as a different weighting of the original population loss, i.c. Equation D.2 can be written as
Σ (k - ()CAA w.:?
(D.3)
is clear that the minimizers of Equation D.2 are the same minimizers of Equation (ic. CA
wi for i O,.--; k 1). Thus Lemma holds with additional modifications.
17

---

Published as a conference paper at ICLR 2023
D.2 APPROXIMATE EXTRAPOLATION
For Theorem the analysis in the proof makes use of the fact that the difference in the moments defined by the student and teacher bounded by ((vō). The same true for the case of the weighted loss, specifically, the loss & 6, then for all 0, O.......
/ [k: (C w;) & vo. Since k - i > for 0 O,...,k k - we have (CA' - ws) & v (k: C w:) & v and the remainder of the proof the same.
D.3 IMPLICIT BIAS FOR BALANCEDNESS
The proof of the implicit bias for balancedness involve the gradients of the population loss defined in Equation 3.4 For the weighted population loss the gradients differ, but the symmetries are all preserved (the gradient computation boils down to adding external summation to the terms computed in Section
The same steps described in Section E.4 apply for the weighted loss.
E DEFERRED PROOFS
Here provide complete proofs for the results in the paper.
E. AUXILARY PROOFS
In this section we provide missing proofs from the main paper and additional lemmas to be used in the main proofs.
E.I.1 POPULATION LOSS
Lemma E.1 (Proof of Equation 3.4
Assume D such that Em=D[ 0, Ea xx 1 I& Biikk where In the identity matrix. y is given by (NN(w) where RNN(-) denotes the output of teacher RNN, = (Á, Õ). Denote w; CA' B, the loss for the student RNN satisfies:
Ez-D IE (RNN
Σ (CA'B - -w;))²
(E.1)
Proof of Lemma
E.1
The population loss for training with sequences of length k is
R-
Ex- D [ERNN (x) = EEID Σ CA
CAR-1- Ba,
Σ
Wk - -1
(E.2)
1=0
Reversing the order of summation, expanding the terms,
18

---

Published as a conference paper at ICLR 2023
BEWD [eRNNN (2) EOOD
Ba Σ
wytk-1-1
(E.3)
B -CCCCAABBCCABBBB. w/ Ex (26-1-106-111
(E.4)
C W:W,] 1x-1-ink--
(E.5)
BABBCA'B2CCA + Zin
(E.6)
2 w³] Σ (CA'B--))
(E.7)
where the transition from the second to third rows is by our assumption that E [2,0]]] Therefore we have,
1i-j-
ELDD [E (RNN (x)
(CA'--ut) -
(E.8)
concluding the proof.
E.1.2 PERFECT GENERALIZATION AND FAILED EXTRAPOLATION
Proposition E.2 (Proposition in main paper). Assume > k, and let e 0 and q {k + 1, + .). Then, for any teacher parameters θ, there exist student parameters O with which the population loss Equation 3.4 equals zero, and yet the student does not c-extrapolate with horizon q.
Proof. Consider a student, θ, such that A is symmetric (and therefore has an orthogonal eigen- decomposition). Denote A TAUT. The impulse response at time step be expressed as C'A'B CUA'U" B. The latter can be written compactly in matrix form as Vg where V is the Vandermonde matrix with (Aag(A) as its values.
1
A
Ag
Ad
2
X
X
dd11
X d-11
and g is defined as g = (CU) OUT B they are invertible if and only if A; # Xy. vi # j. Given fixed set of distinct values (A1...., Aa) and an arbitrary impulse response r IR in order for the student to generate the impulse response (i.e. Vg r), one can set the coefficient vector, g V- and end up with symmetric student with r as its impulse response of length d.
A known result on square Vandermonde matrices is that
Consider teacher RNN, é (,,, we can set and the first entries of r to ČÁ-IBB Vi (1....,4 ,K,. We are therefore left with d & degrees of freedom which yields many different students that correspond to the first entries of the teacher while fitting arbitrary values beyond the & considered.
Here O denotes the Hadamard (elementwise) product.
19

---

Published as a conference paper at ICLR 2023
E.1.3 EQUIVALENCE BETWEEN BALANCED RNNS WITH SYMMETRIC AND DIAGONAL TRANSITION MATRICES
Lemma E.3. A balanced RNN, e = (A, C), with a symmetric transition matrix (i.e. B C. and A A has an equivalent (i.e. generating the same impulse response) RNN, e' (A' "",'",),, which is balanced and its transition matrix is diagonal.
C"),
Lemma E.3 alloow alternating between systems with symmetric and diagonal matrices. This is useful simplify the analysis in Section 4
Proof of Lemma E.3 Any symmetric matrix admits an orthogonal eigendecomposition with real
(non-imm non-immginnay) eigenvalues. Denote
UAUT. We can define
A B' = U and =
The tth index of the impulse response is given by
CA'B CUNU B C' C
concluding that O and O' have the same impulse response of any length.
E.1.4 GRADIENT DERIVATION
For completeness and Section E.4 compute the gradients for the general setting.
Lemma E.4. Given the population loss
[(ABB,)) = Σ (CAB-CAB))
3.4
revisited)
J-0
Denote Vl, CA'B B Wi the derivatives of the loss with respect B, and C satisfy:
ac
VR(AA)TTT.
(E.9)
²B
ēc Oc = Σ V (A')
(E.10)
Proof of Lemma E.4 Here, will compute the gradient of the population loss.
Note that for j > 0, the derivative of CA3B B with respect to to is given by
(CAB CA.
(E.11)
²B
Similarly, the derivative of CA'B B with respect to C is given by
(CA
B
(E.
2C
Using these derivatives, can calculate the derivative of the population loss, (assigning w; BÁ'O).
C(A. B,C) EAND (<(RNN(()) (x)
(CA'B w:)2
(F.13)
Denoting V4, (B
CA'B Wis and noting that wy is constant (depends Q). have for X
θ (CA'B w;)
(CA'B ws).
K-1
(CA'B)
Vl.
Σ
Vl
(E.14)
2x
2x
2X
ax
1-0
1-0
1
20

---

Published as a conference paper at ICLR 2023
Plugging in Equation
E.1
and Equation E.12
have:
Oc
k-1
(CA'B)
a
V4
(E.15)
A
(CAB)
Σ
44
VLB VI,B"(A'),,
(E.16)
àC
1-0
E.1.5 LEMMA 6 (CONSERVATION OF BALANCEDNESS)
Lemma E.S. [Lemma 6 in main paper] When optimizing equation 3.4 with GF emenating from balanced initialization (0), the parameters ((T) are balanced for all E Rt.
We prove the above result by first showing for GD and then translating the result to GF. The GD result is stated below, and generalizes result that was shown in "Cohhn-Kaatti et al. (2022) for the memoryless case.
Lemma E.6. When optimizing equation 3.4 with GD with balanced initial conditions, then VI E N, C has balanced weight configuration, i.e. B, CTT
Proof of Lemma E.6 We prove by induction. By assumption, the condition holds for / 0. Assume B, C our goal is to show the conditions hold for (Bi+1, Cz+1). In order to show that
B++1 C we only need to show that 2B, have
(C,,)
Writing the gradients (Lemma E,4 we
Qc aC,
- =
T
k-1 Σ VA(AT)C Oc
VLA,B,
(E.
2B.'
where the inequality follows from the induction assumption and the symmetric structure of A,. To conclude, the gradients at time are the same and B; = C, by the induction assumption, arriving at
dL
(
OC ac, = C
B B. 1 ²
C.
(E.18)
The proof of Lemma 6o follows from Lemma E.6 and the fact that for sufficiently small step size GD approximates GF with arbitrary precision (see Theorem 3 in Elkabetz & Cohen 2021)
E. CONSERVATION OF DIFFERENCE OF NORMS
Appendix E.I.5 shows that if weights initialized to be balanced. this property is conserved throughout optimization. Here we show under standard initialization schemes, the difference between the norms B and C' also conserved.
Lemma E.7. When optimizing equation 3.4 with GF the difference between the norms of B, C is conserved throughout GF, i.e.,
d
( |[C
(E.19)
Proof of Lemma E.7
We wish to prove that the difference between the norms is conserved over time. Consider the following expression
a
B - C Tr(B B) -T((CCT) BJB CC
(F.20)
'The last equality follows since in the SISO setup, B B and CCT scalars and therefore the trace operator be omitted.
21

---

Published as a conference paper at ICLR 2023
With this notation, we just need prove that à 0. The derivative of B, C' with respect to time is given by,
k-1 Σ
VE(ATTCTT
(E.21)
Č= Σ VA,
(E.22)
Using the interchangeability of derivative and transpose, have:
B
B- ČC
CČT = =2 B-2C
(E.23)
Plugging equation
E.2
and equation
E.22
we get
à 2B
VE((AT)CCT)
-2 Σ (ATB
CT
(E.24)
2m0
1-0
2 B
Σ
VEL(AT) CT -T-
Σ (e,(AT) CT
0.
(E.25)
1-0
establishing that d de
(IB) - [[[|]] O.
E.2 LEMMA (EXACT EXTRAPOLATION)
Lemma E.8. [Lemma]] 7 main paper] Suppose that d > k > 2d, the teacher is balanced, and that the student parameters è are balanced and satisfy ((0) 0. Then O extrupolates.
balanced RNN with symmetric transition matrix has equivalent (generating the same impulse response) balanced RNN with a diagonal transition matrix. We will continue under the assumption of diagonal transition matrices.
Proof of Lemma E.8
By Lemma
Without loss of generality assume ČB Otherwise, the problem can be rescaled by ČB, which is equivalent to rescaling the initial conditions, and providing no additional information 5
From the balanced assumption, we have Č = B. Denote P C B C B, and we get P. 3 and Σ, p. 1, and therefore p may be interpreted a distribution over random variable with possible values. We shall assume that these values are Â A and denote the corresponding random variable by 2.
Furthermore, we can also interpret elements of the impulse response of θ as moments of this distribution. Let write the nh element of the impulse response
B = EzL2nJ.
(E.26)
where Ep[2] is the expected value of a random variable Z under the distribution p. In the same way, we can define for the learned model Ô distribution p: C,B,, and write the learned impulse response as:
CA"B Σ p.ay -E EplZ"].
(E.27)
This view provides us with moment matching interpretation of the learning problem. Namely, the fact that θ matches the first & elements of the teacher impulse response, is the same as saying they agree on the first & moments Ep1 ZP] for j E f1....,k k 1) The question of extrapolation is whether equality in the first k moments implies an equality in all other moments.
"The case for which Ć = is handled separately. 'Equality of the tt moment ensures the student induces valid probability, i.e. Σ, C,C.B,=,, Č,
22

---

Published as a conference paper at ICLR 2023
In (Cohen & Yeredor 201 Theorem 1) and in (Wu & Yang 2020 Lemma 4) it is shown that the first 2d moments of discrete random variable taking most d different values uniquely define this random variable. Therefore, any other discrete random variable identifying with the teacher on 2d moments must be the same random variable and therefore identifies on higher moments as well. Since we assumed k > 2d, this result immediately implies that equality in the first k - 1 moments implies equality in all other moments.
For the case ČB 0, from our assumption that the teacher balanced, we have that the condition met only if C; = B; = for = I...., d. Such a teacher has an impulse response of zeros, for k 1, student minimizing the loss must also satisfy CB 0 and therefore has the zeros as its impulse response (recall the student balanced) thus extrapolating with respect to the said teacher.
E.3 THEOREM 8 (APPROXIMATE EXTRAPOLATION)
This section devoted to the proof of Theorem which ties the approximation error of optimization to that of extrapolation.
Theorem F.9. [Theorem Øin main paper] Consider the minimization of Equation 3.4 and assume:
(i) d=> > 2d: (ii) the teacher is balanced and stable (i.e. the eigenvalues of Á are in |-1, , 1D: (iii) the teacher is non-degenerate, i.e. the input output mapping they realize is not identically zero; (iv) the student parameters are learned by applying GF to the loss f()), starting from a balanced initialization: (v) the student parameters & are bounded.
Then, for any E >> O and q N, there exists 8(e, q) > such that whenever ((O) < 8(e, q). the student c-extrapolates with horizon q.
Proof of Theorem
E.9
Let 5 0 be a constant whose value will be chosen later, and suppose GF
reached point θ satisfying (()) & 8. Following the proof of Lemma 7 θ is identified with distribution supported on the eigenvalues
Á, whose j j'th moment is my == (CC)) for every j N. Similarly, θ is identified with distribution supported the eigenvalues of A, whose j'th moment is my == (EABB(CB)) for every e N. From our assumption that (()) & 5,
((0)
Σ j=0
CAAB CAAB-CAB) CAB))= &
(E.28)
-CA'B-CAE CÁC)2 < 8 for 0,... k - 1. In particular, ČB CB, then 3 e [-Vō, voj. Note that ČB is (positive) constant, multiplying the loss by (CB)-2 we have that each term & 8(CB) -2 We can write for each j k-.,
and specifically, each term satisfies
(CB CB)² & d. Denote
CAAB ČÁBY
CA'B
CA'
CA
ČÁB 2
(E.29)
ČB ČB
ČB
CB
CB
ČB
1
CA.B
ČAB
CABB
+
(E.30)
ČB
CB
CB
ČB
my-my
We can further expand the term on the left,
1 1
1
- CB-
ČB
B
(E.31)
CB
CB
ČB
ČB
ČB - B)
CB CB)
23

---

Published as a conference paper at ICLR 2023
Plugging back to the above, we have
CA'B
CAB
BCABB
8(CB)
+ (m, mmn))
(B.32)
CB
CB
CB - CB)
BR 23k(m; mm)) ) (my mm)²
(E.33)
23x(m, myj + (m, m2j²
(B.34)
2) m,)l ) + (my m2)²
(E.35)
CB CB) From assumption (ii), the teacher is stable and therefore my & CB for all j O....,. 1. Similarly, from assumption (v) the student parameters bounded and therefore
where K
CAAB
CA is bounded by 7J+2 (where = max 1, v/ and is bound on the Frobenous norm of A, B, C). mj is bounded in similar fashion by r².
Combining the above, for 5 < Č we have,
8
2 +1
(my m,,²
(E.36)
CCB)
2(CB)²
Setting 8'
B By
if L()) 8' then my myy-hi mmyl
/ for 1, 1,...,k k- Proposition
1+-k++
in Wu & Yang (0200) then implies (i & O
= (UL_) An) U ( (the union of the supports of and Q), from Sec- tion 2.3 in Panaretos & Zemel (2019). for q > p the 9th and pth Wasserstein distances sat- isfy ( Q) & W 0) where
Denote
maxz.yen ja yl- In particular, for p = 1,
O,, & (0,,))))~1 1/9 Note that can is bounded by + & 2r (recall the student bounded and teacher is stable).
Finally, Ing- mgl & Wy(O, θ) (see Section 1.2 Biswas Mackey (2021) p). Combining the steps above, for all q N
1/4 mg mgl W2 & (1270)) & (1)5))(22))-1)
(E.37)
where p constant satisfying Wi@e, 3) & pol/id To achieve |my- myyl for any >> we
4d
can set 8(c,g) < (
concluding the proof.
E.4 PROPOSITION O 9 (IMPLICIT BIAS FOR BALANCEDNESS)
The proof of Proposition 9 consists of several steps. First, we bound with high probability the norms of B and C initialization (Lemma E.10 We then derive bounds the differential equations of de (B()) + (!)) and L (B()) C (Z) (Lemma F. 14). We show that when the initialization
scale tends zero, the ratio between the differential equations tends zero. (Lemma E.13).
Before we turn to prove Proposition 9 initialized with (0, =)
we first need to bound the initial values for vector v IR"
Lemma E. Assume vector E Ra with A(O, S per coordinate, Then:
3c
Pr
|
> 2 2-e-eeex99n666
(E.38)
2
'Here overload notations and denote the distributions of the teacher and student by θ and Ô respectively
24

---

Published as a conference paper at ICLR 2023
Proof of Lemma E.10 The proof of E.10 uses known results the Chi-square distribution Laurent & Massart (2000) applied to our specific setting to achieve the desired bounds. We will begin by
changing variables, é; V; y The entries Ü, are standard Gaussian variables. The squared norm of e distributes according to the X-squared distribution.
By (Laurent& & Massart 2000 Lemma 1), in our case (assigning 9n/64) the following inequalities hold:
Pr [|ol² > (1.75 + 9/32)m) & exp(-9n//66
(B.39)
Pr (1 & n/4)
(E.40)
In particular,
Pr (r 2.25m) exp(-9n/664) = Pr (1 1.5m)) & exp(-9n/64).
(E.41)
Changing variables back to
Pr Pr[[ > 1.5c) exp(-9m/644)
(E.42)
Similarly, for the second bound:
Pr (|ह) < vn/2) < exp((9n/66)) = Pr (1le) < < < (ep(-9n/64).
(E.43)
Taking the complementary probability, we have the desired result of
3e 2 1 -2exp(-9n/64).
Pr 2
|o|| <
(B.44)
Note that for matrix X E RRx Lemma E. bounds its Frobenius norm, Pr < X < 2)
1 2eap (-9mp/64) The result is straight forward by applying the lemma X's vectorized form.
Proposition E.11. [Proposition 9in main paper] Suppose that: (i) 4; (ii) the teacher parame- ters θ are balanced and non-degenerate, in the sense that the input-output mapping they realize is not identically zero; and (iii) the student parameters are learned by applying GF to the loss C(.). Let θ be random point in parameter space, with entries drawn independently from the standard normal distribution. For e > O, consider the case where GF emanates from the initialization e and denote the resulting curve by (.(T) (T) B.(T), Cc(T)), with O. Then, w.p. least 0.75, for every >> O there exists > 0 such that:
[.(eT) C.T (Te)lLe 0.
lim +0++
(E.45)
B.(T.) + C. (T.)
The consequence of Proposition 9 is that converges to zero, B and C converge towards each other.
For convenience, we refer the mentioned initialization scheme (where every coordinate in a vector is initialized as /V (1, { c-normal initialization. In order to prove the proposition we define few relevant terms,
Y B-T-
W Wp ČB.
(E.46)
We will fact prove the stronger, following lemma, for any matrix A, not necessarily symmetric. Lemma E. Assume wo > 0, and A, B, C are e-normally initialized. Then 3t such that
A((t) W(1]2
lim W (t) = 0,
lim
0.
(E.47)
25

---

Published as a conference paper at ICLR 2023
The proof of Lemma E.12 follows three steps: (1) establish time in the optimization for which the norms of all parameters are bounded (Lemma 1 (2) derive upper (and lower) bounds for the differential equations describing the evolvement of Y. W and A. Our approximations are limited to the initial phase of training. Concretely, we show that for & &
In ( ), all norms are 20to
bounded. Thus, it is possible to obtain meaningful bounds on the ODEs of Y and W while A remains in the magnitude of initialization (Lemma E.14); (3) using the relevant bounds, show that as the initialization scale tends to zero, so do the limits in Equation [..7
As it turns out, there is critical time i O (In (x))), up until which the considered bounds valid (see details in the proof of Lemma E.13
Lemma E.13. Assume d 20, student parameters are e-normally initialized, assume also a balanced teacher. Then w.p. at least 0. 7,75,fo for all 0 & 1 & I, there exist M1, M2 such that:
[[C(t),, |B))ll
(E.48)
and
A F M2c
(E.49)
To prove this, we note that at initialization, A, B and satisfy these bounds. From continuity, there exists maximal time for which they satisfied. We bound the rate of their growth, and thus show that for all as described, we are within this region.
Lemma E.14. Assume wo (see Lemma E.1 for definition of wi) and assume A, B, C are c-normally initialized, we have the following bounds hold for all 0 & & E w.p. at least 0.75,
Y Y() 6G em2ott + C2t 2.5
2wot
c2t2
(E.50)
and
W(1) TOOTWIO W(1) Ezt 2 222ot 2.3
(E.51)
Lemma E.14 shows that the growth rate of W(t) (t)) and the decay rate of Y both depend on the sign of Wp- In our analysis we assume the teacher is balanced and therefore un > the same analysis applies for < O with opposite roles for Y and W. The proof of Lemma E. follows from writing the leading terms of the ODE and bounding the remaining terms by their upper bounds in the time considered. Using these lemmas, we proceed to prove Lemma E.12
C'n (2dx). By Lemma E.14 w.p. at Proof of Lemma 12 Consider the dynamics at time least 0.75, we have,
Y()) Y()) (()) & c 2n pis
c2e2.5 (2we-2wo6 +2)e
(B.52)
and
((t) T W(t) b 2 2woC ,os.
c
2.5 ege
2wp
C.CCee.. 1.5
2.5
(E.53)
We can calculate the limit (where 2 and F account for the relevant constant factors),
(t) lim
(ē) + c2)
lim
(E.54)
W(D
2.5 2.52.5
From Lemma E.13
A((T) P < M2e, so we can calculate the limit,
ADD w(D
2ac
lim
lim
(E.55)
Eze 1.
2.5
which concludes the proof.
Proof of Lemma E.13 Applying Lemma E.10 with d 20 results with the bounds holding
at initialization with probabilities > 1 2erp( -9 20 /64) for A, and > 1 2exp(-9-
20/64) for and C. The probability for A, B, C satisfying the inequalities simultaneously
> (1 - 1--2eer((-- 9. 20/ 20/64))3 x 0.83 > 0.75.
Suppose that the norm bounds of Equation E.38 that
satisfied at 0. In particular, 3M,, M2 such
[B())) ((O) 2e M,
(E.56)
26

---

Published as a conference paper at ICLR 2023
and
|A(O)) < 2e M2e.
(E.57)
Where M2 e. and M1 4.25
Denote by t the minimal time for which A(ta)] = Mye. Similarly, tp. are the times for which [B((B)] [C(tc)] Mi Denote also min (LA,4B, Proving the lemma amounts to showing there exists C' e I& such that / = Cn ( Next, we turn to develop the differential inequalities of the norms, which will later be used lower bound the time until violation of the mentioned bounds.
Recall derivative of B with respect to time (see Section E.1.4
k-1 B Σ
VA(AT)CT
(F.58)
Using Cauchy-Schwar inequality, we have that for all [0, the norm of B is upper bounded by
k-1
B VA(ATTCC
V4l A I
(E.59)
We now bound the norms of V4, A and C in order to transfer the inequality to a differential one.
Denote M = max([w:]) + Mf 2.5
then we have
M max( (u;x((:;)>> M 1.5 max([w:)) + |C B > max( (1: + CC
(E.60)
max([w) [. + max CAABB > max(|u; [c + (CA'B) max V&J).
(E.61)
For the norm of C, recall the conservation law from Lemma E.7 for the norms of and C:
d dt -B(01--|C(()) 0.
vI,
(E.62)
From the assumption that the initial conditions are met,
[B(O)), < = (1) B(0) - [C(O)))) < 4e.
(E.63)
Therefore, we get
vI, |C((|]] < || [B(]] + 4e.
(E.64)
Note also that by assuming M2 < 3, we have M2e < 1 and
Σ (M2c)* < k.
(F.65)
Plugging the above steps into equation E.59
we have:
k-1
B
[ C < M(I 4e)
Σ ((AT)]
(E.66)
B| 4c).
(E.67)
Denoting 7 =B B B, then
B
B
2B B
(F.68)
Taking absolute value and then plugging equation E.66 results with
Hi = 2
B
< B
B
B M B| + 4e).
(E.69)
Using the definition of 7, we get that
|R| < 2kM
(17l + de devlrl)
(E.70)
27

---

Published as a conference paper at ICLR 2023
Next show that i = O (In (2.5)) Suppose this is not the case, then there exists & < In (103) such that one of the bounds are violated: (i) B Mic0.75 4e; (ii |C()]] 0150. de;
or (iii) |A(t) > M2c 2c.
Consider case (i) from continuity there exists t' such that [ = 4e, and t" e R such that for any t e [t', t"], de < B(t) & M,c0.75 In such case, also have
K & 2kM (hl + 4evh7l & 4kMhl
(E.71)
Integrating the inequality [4] < 4kMhi by for & [t',t].
Filt [" 4kMMd,
(E.72)
substituting integration variables and using
E t" In (5..E).
(()) 1 dr & 4kM (s (s-t) f) < 4kM In 20. 0)
(E.73)
The above evaluates to,
In (1())) (((t))
4kM In
(E.74)
c0.5
which may be further manipulated to reach,
[n())] < e 4kas (1t))) (4c)2 aaks in (stts)
(E.75)
where we have used [Bt())] 4e. The final bound on the norm of ((s) is therefore,
16e²
hns)]
0.. e LMM
16e 1.5 ( 4RM
(F.76)
Denoting M2 = 16-
e 4KM and taking the square root of the above,
B(s) M.
(F.77)
We have shown that for all 0 < & In (2os). there exists M1 s.t B(t) < 0.75 (the same proof applies for case (ii)).
Consider case (ii), we need to show that the bound over | F| applies for te [0, f]. Notice that for matrix, ||] Tr( A A), and
Tr Tr(ATA)
Tr d
(ATA))
(E.78)
di
=Tr [ÄT A) +Tr (ATA)
(B.79)
2Tr A A
(E.80)
where we have used the linearity of trace and its invariance transpose. The derivative of A with
respect to time (see Section E.1.4.
Á Σ VL, C (-
(E.81)
Multiplying it from the left by AT and then taking trace provides us with
Tr(ATA A)
Σ
V4 Tr
B (A))
(E.82)
*The of [C(+) 0.70 handled similarly.
28

---

Published as a conference paper at ICLR 2023
Taking transpose and then using the eyclic property of trace and, for each summand,
((AT)++I (A (A)) Tr (B (AT) Tr
(F.83)
-Tr(CA'))
(E.84)
CA'B.
(E.85)
Equation
E.82
evaluates
Tr A) =
Σ V4
CAB = Σ PQ-i-AA
(E.86)
Bounding Tr(ATA) A),
Tr(A A) &
Vel-i-ICA'B
(E.87)
Using the Cauchy-Schward inequality and then plugging M > [4, and the bounds found for ||C], B < Mic..ra leads to
V4I . i. CA'B & M 1. |C|
A
B & i. Mi 15 A|
(E.88)
Putting the bound of Equation E.88 into Equation E.87 results with,
k-1 M Mf 2.5 |A M M
Tr(A A)
i A|ll
(E.89)
Noting that |A|r r < and denoting M2
MM M M?
12 2
leads to
k-1
< A k(k 1)
1.2
i
A
Al|l
(E.90)
2
2
Therefore, we get that
Tr(ATAr < <Mae" 1.51..51AA A
(E.91)
Notice that
d
(1A = 0.5 d
AA|F dt
(1A1?))= -TrAAT
(E.92)
dt
d
||A||F dt
(|||]])) <Mge' 1 |A
(E.93)
di (|All)) M.6 1.5
(E.94)
Therefore, for any 0 < & F,
|A(s)] |A(0)) p= S d
dt (IA(t)) M2
(E.95)
= >|[(ss]| < Mae 1. In
+ |A())]
(E.96)
0..
We make use the fact that Vx > 0, In(x)) < x to bound,
Mge 1.5 In
Mge 15 0.5
Mre.
(E.97)
0.5
From our assumption on initialization, |A(0)) 2e. Putting back together,
IA(s) F Mae 2e.
(E.98)
Taking M2 M2 have for all 0 & f & that
|| AA([] < M2e,
(E.99)
concluding the proof.
29

---

Published as a conference paper at ICLR 2023
E.4.1 BOUNDING THE DIFFERENTIAL EQUATIONS
Proof of Lemma E. 14
Denote
Y=C-
W = C + B.
(E.100)
Recall that
àc
Oc
VE(ATTCT
B T Σ (l,(
(E.
²B
1=0
We write the change in Y.
Y = -
B Σ VLA'B C
(E.102)
V4 ((A ( C A'B)
1=0
Denote (A')s = A'+(ATy and (A') = A A'
the symmetric and anti-symmetric parts of A'.
We write
(A J'CT A'B [(A's )s (A')s] C - + {A))s B = (A') -B) (A')s(C) + +B)
(E.103)
S - s W
Note also that for i O, have A I and its anti-symmetric part is the zero matrix, writing i 0
separately and assigning equation E. 103 into equation E.
+ Σ V4 ((A))SY - (
(E.1
Let us look at d (YTY) YTY + 2 at
Multiplying equation
E. 1.4 from the left with T evaluates to
K-1
YT = V4 TY
Σ
Va (
(E. 105)
We now turn to bound the terms the sum.
YT VlY Y
(LY (AA)ss
(E.106)
We bound each term using Sauuch-Schwarz... We first need bound Y and W|| which trivially bounded by
|YI. W|
|C|| + B < 2. 0.75
(E.107)
As for the symmetric and symmetrii parts of A.
A' + T
1 1
(IA
(|A + [I(A))
AAA' |A]]
(E.)
where the last inequality follows again from Cauchy- Cauchy-Schwarz (the considerations apply for (A') a))s
From Cauchy-Schward
bound Y (AA)ss W
Y (III W|
||]||||
[
denote M3 mar M1, M2) and derive,
Y (A W 2M
0.73 (M2c))
0.75
(E.
30

---

Published as a conference paper at ICLR 2023
which is maximized when 1.
We again bound: M max([w;s) + -M 55
Vlgl. We can
bound the terms in equation b.
V4 Y (A')sY| + (A')sWi)
<--M M .3
(E.110)
Plugging back into equation E.106
k- 1
Y & V + Σ
8 M 2
(E.111)
We can also bound Vl (CB wp) ww + CC & wi + | & wp + M Note also that we multiply by Y
Y so we can bound
Vlo Y
M 1.5 (M22l
21 0.752
(E.112)
-MMfe²
putting back together, we get
Y w we Y 4M (k. - 1)( + 1)8 M. 2
(E.113)
In particular, there exists M4 such that
+ 2.5
(E.114)
Recall that we were interested in bounding
d de Y = +
Y
& 200 + 2 2.5
(E.115)
dt
Denoting =(t) ((t) Y(t) (t))) and (t) W (t) W(t,, and using Lemma E.15 bounds
have the desired
=(t)
(33wgdee)) e 2wot M4
(E.116)
2w0
In particular, we can write
(t)) & c-
2wat + C2t 2.5
(E.117)
and
x(t) > C3E² 2wot 2wot CGf 2.5
(E.118)
where c; ss are positive constants.
Note that the derivation of (t)) is exactly the same as z(t) with opposite signs and bounding from below instead.
E.4.2 INTEGRAL BOUND OF DIFTERENTIAL EQUATIONS
Lemma E.15. Assume & < -2wp2 + 2.5 < 0, > 2woz M4 0, where wn > 0. Then, under the assumptions of Lemmal E.10
2(t1)
(exp(-2wptt1) (75w)de?) 2.)5
(E.119)
2wo
1
Win
x(t2)
exp((wwot))
2.
(E.120)
2wo
25d
Proof of Lemma E.15 Assume ~2wpp + 2,5 assume i > 2wox - 2.5
where wo 0,2 245 Similarly,
Then:
1/2 2w02
2,5 -1
(E.
31

---

Published as a conference paper at ICLR 2023
(E.122)
Zwn M4 2.5
Integrating both sides by dt, and using integration by substitution, we get:
11
11
1
dz di
-=(t)) 1
1
M4 2. dl ==(0) 2wpz M45 dz
(E.123)
2wnz
22
dr dt
co(tz)
12
2w - 2 dr
(E.124)
2 dt 2wox 00
J0
22)))
We note:
((4)
1
1
de
[In (2wp2(t1) M4 - 1n(2 - Mcc2.501 (E.125)
20))
2wpz M
2wo
(t1)
1
2wwzz(1)
2 2.5
dz
In
(E.126)
=()
2wiz M4e2.5
2wo
20)=(0)
24
xz(1z)
1
(200)r(t2) M
2wg M4e2.5 dx
In
(E.127)
(x)
2w0
2wox(()) M4e
Combining equations, we have:
(w)2(11) 243
In
< <h
(E.128)
2wo
(0)
M4e..5
(t))
In
2wot
(E. 129)
210= Mae2.5
2woz((1)
M
exp(-2wott)
(E.130)
2wnz(0)
M4e2.5
2w)
2.5
(2wr²(0) M2(2
(E.131)
1
=(tt) <
[exp(-2usp) -2wgth) (2wp²(0) MM42.55 + M4
(E.132)
2w0
x((2) >
[exp(2wol2) (O) M4 + M4e 2.57
(E.133)
2uo
Note that =(0) = (0) By linearity of sum of variances, Y(O)'s 's entries are distributed
according to N(0, v2. c), by Lemma E.10
v2
3
|YO)
1E.134)
2
From Cauchy-Schwartz z(0) < 362 with high probability. W distributed as Y, therefore,
<<()) je². Assuming 2.5 2 have:
wae²
1
z((1) < (exp(-2wot) (6wne?) + 2.0)
(E.135)
2wn
x(t2) > (exp(2wont2) (wee?) + 2.5
(E.136)
2wo
Concluding the proof.
32


Reviews:
[{"review_id": "tk2mgtXSMqM", "reviewer": "Reviewer_3zQj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \nFor 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. \nThis 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. \nThe theoretical findings are supported by experiments on different models are conducted in order to show the phase transition between perfect and non perfect extrapolation.", "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. \nMy 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:\n\nI 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. \n\nSome other things that caught my eye:\n* 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$. \n* 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?\n* 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.\n* 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\nthe impulse response of the learned student and that of the teacher) as a function of $k$.“ I would simply delete the brackets. \n\n\n", "strength_and_weaknesses": "Strengths:\n* 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. \n* The theoretical analysis is strong, well supported and clearly laid out.\n\nWeaknesses: \n* *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. \n* *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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "fZmSSyk5LET", "reviewer": "Reviewer_C8pz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "L91lxcp1Vo", "reviewer": "Reviewer_n2fU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n\nThe theory is built with a simple teacher-student setup with the following properties:\n\n- Teacher and student are represented as linear RNNs.\n\n- The teacher and student RNNs have states spaces of dimension $\\hat{d}$ and $d$  respectively.\n\n- The length of the sequences available at training time is $k$.\n\n- The student RNN is in the overparametrised regime ($d > k$).\n\n- No correlation exists between the elements of the input sequences.\n\n- 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.\n\nUnder the assumptions and the notation specified above, the authors prove the following main result:\n\nIf $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.\n\nThe 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.\n\nAfter the above theorems are stated/proved, several numerical results are presented. \n\nThese 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: \n\n(1) the theoretical settings used to prove the theorems \n\n(2) a simplified settings where certain assumptions from (1) are relaxed (such as the balancedness of the teacher)\n\n(3) a nonlinear RNN setting where essentially none of the simplifying assumptions used hold exactly\n\nFor 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$.", "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.\n\nI 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.\n\nI 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.", "strength_and_weaknesses": "**Strengths:**\n\nThe paper is very well written, and relatively easy to follow in spite of the highly technical nature of the results presented. \n\nThe main result is remarkably simple to state, and yet rather nontrivial to prove.\n\nI 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.\n\n\n**Weaknesses:**\n\nThe 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.\n\nHowever, 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.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8OZq0yn50a", "reviewer": "Reviewer_8yoF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "The paper is well-written and provides some novel results, yet some places need more clarification.", "strength_and_weaknesses": "Strength: The topic is interesting. The result seems convincing. The presentation is relatively clear.\nWeaknesses: Some places in the setup need more justification. See comments below.\n\nIt 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.\n\n1. In Eq. (3.1), why does the transition matrix $A$ need to be symmetric (i.e., $A^T=A$)?\n\n2. 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.\n\n3. 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?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster