On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis
Authors: Zhong Li
Jiequn Han
Weinan E
Qianxiao Li
Venue: ICLR 2021 Poster (2021)
Keywords: recurrent neural network
dynamical system
universal approximation
optimization
curse of memory

Abstract: We study the approximation properties and optimization dynamics of recurrent neural networks (RNNs) when applied to learn input-output relationships in temporal data. We consider the simple but representative setting of using continuous-time linear RNNs to learn from data generated by linear relationships. Mathematically, the latter can be understood as a sequence of linear functionals.  We prove a universal approximation theorem of such linear functionals and characterize the approximation rate.  Moreover, we perform a fine-grained dynamical analysis of training linear RNNs by gradient methods.  A unifying theme uncovered is the non-trivial effect of memory, a notion that can be made precise in our framework, on both approximation and optimization: when there is long-term memory in the target, it takes a large number of neurons to approximate it. Moreover, the training process will suffer from slow downs.  In particular, both of these effects become exponentially more pronounced with increasing memory - a phenomenon we call the “curse of memory”.  These analyses represent a basic step towards a concrete mathematical understanding of new phenomenons that may arise in learning temporal relationships using recurrent architectures.

Published as a conference paper at ICLR 2021
ON THE CURSE OF MEMORY IN RECURRENT NEU- RAL NETWORKS: APPROXIMATION AND OPTIMIZA- TION ANALYSIS
Zhong Li
Jiequn Han
School of Mathematical Science Peking University 1i zhong@pku. edu.cn
Department of Mathematics
Princeton University
j jiequnhêpr inctonn edu
Weinan E
Qianxiao LiF
Department of Mathematics and PACM Princeton Univeristy we weinan@math. www.ett...iinneto.....
Department of Mathematics National University of Singapore IHPC, A*STAR, Singapore qi giaaniaa@mmnn edu. sg
ABSTRACT
We study the approximation properties and optimization dynamics of recurrent neural networks (RNNs) when applied to learn input-output relationships in tem- poral data. We consider the simple but representative setting of using continuous- time linear RNNs to learn from data generated by linear relationships. Mathemat- ically, the latter can be understood as sequence of linear functionals. We prove a universal approximation theorem of such linear functionals and characterize the approximation rate. Moreover, we perform a fine tine-grained dynamical analysis of training linear RNNs by gradient methods. A unifying theme uncovered is the non-trivial effect of memory, notion that can made precise in our framework, on both approximation and optimization: when there is long-term memory in the target, it takes large number of neurons to approximate it. Moreover, the training process will suffer from slow downs. In particular, both of these effects become exponentially more pronounced with increasing memory a phenomenon we call the "curse of memory". These analyses represent basic step towards concrete mathematical understanding of new phenomenons that may arise learning tem- poral relationships using recurrent architectures.
INTRODUCTION
Recurrent neural networks (RNNs) (Rumelhart et al.) 1986) are among the most frequently em- ployed methods to build machine learning models on temporal data. Despite its ubiquitous applica- tion (Baldi et al. 1999, Graves & Schmidhuber 2009 Graves 2013 Graves et al.) 2013) Graves &
Jaitly 2014 Gregor et al., 2015), some fundamental theoretical questions remain to be answered. These come several flavors. First, one may pose the approximation problem, which asks what kind of temporal input-output relationships can RNNs model to an arbitrary precision. Second, one may also consider the optimization problem, which concerns the dynamics of training (say, by gra- dient descent) the RNN. While such questions can be posed for any machine learning model, the crux of the problem for RNNs is how the recurrent structure of the model and the dynamical nature of the data shape the answers to these problems. For example, it is often observed that when there are tong-term dependencies in the data (Bengio al. 1994 Hochreiter et al. 200T). RNNs may encounter problems in learning, but such statements have rarely been put on precise footing.
In this paper, we make step in this direction by studying the approximation and optimization properties of RNNs. Compared with the static feed-forward setting, the key distinguishing feature
Equal contribution Corresponning author

---

Published as a conference paper at ICLR 2021
here is the presence of temporal dynamics in terms of both the recurrent architectures in the model and the dynamical structures in the data. Hence, to understand the influence of dynamics on learning is of fundamental importance. As is often the case, the key effects of dynamics can already be revealed in the simplest linear setting. For this reason, we will focus our analysis on linear RNNs, Le. those with linear activations. Further, will employ continuous-time analysis initially studied
in the context of feed-forward architectures (E) 22017] Haber & Ruthotto 2017| Li et al.] (0017)
and recently in recurrent settings (Ceni al. 2019 Chang et al. [201 Lim 2020; [Sherstinsky
2018 Niu et al., 2019; Herrera et al.) 20200, Rubanova et al.) 2019) and idealize the RNN as continuous- time dynamical system. This allows us to phrase the problems under investigation in convenient analytical settings that accentuates the effect of dynamics. In this case, the RNNs serve to approximate relationships represented by sequences of linear functionals. On first look the setting appears to be simple, but we show that it yields representative results that underlie key differences in the dynamical setting as opposed to static supervised learning problems. In fact, we show that memory, which can be made precise by the decay rates of the target linear functionals, can affect both approximation rates and optimization dynamics in a non-trivial way.
Our main results are:
1. We give systematic analysis of the approximation of linear functionals by continuous- time linear RNNs, including a precise characterization of the approximation rates in terms of regularity and memory of the target functional.
2. We give a fine-grained analysis of the optimization dynamics when training linear RNNs, and show that the training efficiency is adversely affected by the presence of long-term memory.
These results together paint comprehensive picture of the interaction of learning and dynamics, and makes concrete the heuristic observations that the presence of long-term memory affects RNN learning in a negative manner (Bengio et al. [1994 Hochreiter al. 2001). In particular, mirroring the classical curse of dimensionality (Bellman 1957). we introduce the concept of the curse of mem- ory that captures the new phenomena that arises from learning temporal relationships: when there is long-tern termt memory in the data, one requires an exponentially large number of neurons for approxi- mation, and the learning dynamics suffers from exponential slow downs. These results form basic step towards a mathematical understanding of the recurrent structure and its effects on learning from temporal data.
RELATED WORK
We will discuss related work on RNNs on three fronts concerning the central results in this paper, namely approximation theory, optimization analysis and the role of memory in learning. A num- ber of universal approximation results for RNNs have been obtained in discrete (Matthews 1993)
Doya 1993 Schäfer & Zimmermann 2006 2007) and continuous time (Funahashi & Nakamura 1993
Chow & Xiao-Dong Li| 2000 Li et al. 2005 Maass et al.] [207]] Nakamura & Nakagawa
2009 Most of these focus the case where the target relationship is generated from hidden dynamical system in the form of difference or differential equations. The formulation of functional
approximation here is more general, albeit our results are currently limited to the linear setting. Nev- ertheless, this is already sufficient to reveal new phenomena involving the interaction of learning and dynamics. This will be especially apparent when we discuss approximation rates and optimization dynamics. We also note that the functional/operator approximation using neural networks has been explored in Chen & Chen (1993): Tianping Chen Hong Chen (1955): Lu et al. (2019) for non- recurrent structures and reservoir systems for which approximation results similar to random feature models are derived (Ginnnn et al., 2020). The main difference here that we explicitly study the effect of memory in target functionals on learning using recurrent structures.
On the optimization side, there are a number of recent results concerning the training of RNNs using gradient methods, and they are mostly positive in the sense that trainability is proved under specific settings. These include recovering linear dynamics (Hardt et al. 2018) or training in over- parameterized settings (Allen-Zhu et al., 2019). Here, our result concerns the general setting of learning linear functionals that need not come from some underlying differential/diiferrnee equa- tions, and is also away from the over-parameterized regime. In our case, we discover the contrary
2

---

Published as a conference paper at ICLR 2021
that training can become very difficult even in the linear case, and this can be understood in quan- titative way, in relation to long-term memory in the target functionals.
This points to the practical literature in relation to memory and learning. The dynamical analysis here puts the ubiquitous but heuristic observations that long-term memory negatively impacts train- ing efficiency (Bengio et al. 1994 Hochreiter al., 200T) on concrete theoretical footing, least in idealized settings. This may serve to justify or improve current heuristic methods (Tseng et al.] 2016 Dieng al., 2017 Trinh et al. 2018) developed in applications deal with the difficulty in training with long-term memory. At the same time, we also complement general results on "van- ishing and explosion of gradients" (Pascanu et al., 2013; Hanin & Rolnick 2018 Hanin 2018) that are typically restricted to initialization settings with more precise characterizations in the dynamical regime during training.
The long range dependency within temporal data has been studied for long time in the time series literature, although its effect on learning input-output relationships is rarely covered. For example, the Hurst exponent (Hurst) 1951) is often used as measure of long-term memory in time series, e.g. fractional Brownian motion (Mandelbrot & Ness 1968). In contrast with the setting in this paper where memory involves the dependence of the output time series on the input, the Hurst exponent measures temporal variations and dependence within the input time series itself. Much of the time series literature investigates statistical properties and estimation methods of data with long range dependence (Samorodnitsky. 2006; Taqqu et al. 1995 Beran 1992, Doukhan et al.) 2003). One also combine these classie statistical methodologies with the RNN-like architectures to design hybrid models with various applications (Loukas & Oke 2007 Diaconescu 2008 Mohan & Gaitonde 2018: Bukhari al. 2020).
PROBLEM FORMULATION
The basic problem of supervised learning time series data is to learn mapping from an input temporal sequence to an output sequence. Formally, one can think of the output at each time as being produced from the input via an unknown function that depends the entire input sequence, or at least up to the time at which the prediction is made. In the discrete-time case, one can write the data generation process
yk
== 1,
where Tk, denote respectively the input data and output response, and {H k = 0, 1,,1,.... is
sequence of ground truth functions of increasing input dimension accounting for temporal evolution.
The goal of supervised learning is to learn an approximation of the sequence of functions { H } given observation data.
Recurrent neural networks (RNN) (Rumelhart et al. 1986) gives natural way to parameterize such a sequence of functions. In the simplest case, the one-layer RNN is given by
h&+1 oWWh, + Urk),
Ut = c
Here, } are the hidden/latent states and its evolution is governed by a recursive application of feed-forward layer with activation a, and ÿR is called the observation or readout. We omit the bias term here and only consider linear readout or output layer. For each time step kt the mapping (f0-..., + Ou parameterizes function H-g()) through adjustable parameters (c. U). Hence, for a particular choice these parameters, a sequence of functions } is constructed at the same time. To understand the working principles of RNNs, we need to characterize how {A approximates {
The model (2 is not easy to analyze due to its discrete iterative nature. Hence, here we employ continuous- time idealization that replaces the time-step index by a continuous time parameter This allows to employ large variety of continuum analysis tools to gain insights to the learning problem. Let us now introduce this framework.
Continuous-time time formulation. Consider sequence of inputs indexed by a real-valued variable t I instead of discrete variable considered previously. Concretely, we consider the input space
X = Co Co, Rd),
(3)
3

---

Published as a conference paper at ICLR 2021
which is the linear space of continuous functions from I (time) to R that vanishes at infinity. Here is the dimension of each point in the time series. We denote an element in X by a == ( E R t RJ and equip X with the supremum norm || == suP;ER || For the space of outputs will take a scalar time series, i.e. the space of bounded continuous functions from R to R:
y (I,
This is due to the fact that vector-valued outputs can be handled by considering each output sepa- rately. In continuous time, the target relationship (ground truth) to be learned is
Y/ = H,)x), EER
(5)
where for each R, H, functional H, X - TR. Correspondingly, we define continuous version of (2 as hypothesis space to model continuous-time functionals
h4 (Wh, + Un):;
Dt c h4,
whose Euler discretization corresponds discrete-time residual RNN. The dynamics then natu- rally defines a sequences of functionals {H)(()) de tt E R]. which can be used to approximate the target functionals }Hr} via adjusting (c, W, U).
Linear RNNs in continuous time. In this paper we mainly investigate the approximation and optimization property of linear RNNs, which already reveals the essential effect of dynamics. The linear RNN obeys (6) with a being the identity map. Notice that in the theoretical setup, the initial time of the system goes back to -co with lim = 0, Va E X, thus by linearity (H₂ = 0)
we specify the initial condition of the hidden state h- = for consistency. In this case, (6) has the following solution
1000 c W UWU
Ú =
Since we will investigate uniform approximations over large time intervals, we will consider stable RNNs, where W E Wm with
Wm = {W E Rm : eigenvalues of W have negative real parts}.
(8)
Owing to the representation of solutions in (7). the linear RNN defines family of functionals H Um Hm.
Hmm = { (f(())) H((x)= = 1xd c. T W Wm, U E pmxd E R
Here, m is the width of the network and controls the complexity of the hypothesis space. Clearly, the family of functionals the RNN can represent not arbitrary, and must possess some structure. Let us now introduce some definitions of functionals that makes these structures precise. Definition 3.1. Let HH L R. be sequence of functionals.
He is causal if does not depend on future values of the input: for every pair of x x' E X such that x, = for all S I, we have H.(x)) H,())..
2. H, is linear and continuous if H.(Xx + Xxx) XHa(w)) + XH(((²) for any æ, x e X and X, X' E IR and sup
(x) < 0o, in which case the induced norm can be
defined as |Helll = suPaex.||=lle (x)
3. H, is regular for any sequence (x(n) X' E N) such that x(m), 0 for Lebesgue almost every 1 E IR, lim H((x(()) = O.
4. {H, : E R} is hime-homoeenoous if Hx(x) = H (x(T)) for any t, T E R, where x(-), = xx-- for all s IR, i.e. a<(T) is whose time index shifted to the right by T.
Linear, continuous and causal functionals are common definitions. One can think of regular func- tionals as those that are not determined by values of the inputs e.g. an infinitely thin spike input. hime-homogeneous functionals, on the other hand, are those where there is special reference point in time: if the time index of both the input sequence and the functional are shifted in coordination, the output value remains the same. Given these definitions, the following observation be verified directly and its proof is immediate and hence omitted.
arbitrarily small time interval,
4

---

Published as a conference paper at ICLR 2021
Proposition 3.1. Let {He t R] be sequence of functionals in the RNN hypothesis space H. (see (.. Then for each t E RR, He is causal, continuous, linear and regular functional. Moreover, the sequence of functionals {Hle L R3 is time-homogeneous.
APPROXIMATION THEORY
The most basic approximation problem for RNN is follows: given some sequence of target func- tionals (H, 1. E }R} satisfying appropriate conditions, does there always exist a sequence of RNN functionals {He :t E } in H such that H; = He for all E IR?
We now make an important remark with respect the current problem formulation that differs from previous investigations in the RNN approximation: are not assuming that the target functionals (H+:1 E R) are themselves generated from an underlying dynamical system of the form
H₁ V/ where hy = ((h,,
V/ = g(+))
(10)
for any linear or nonlinear functions f.g. This differs from previous work where it is assumed that the sequence of target functionals are indeed generated from such system. In that casc, the approximation problem reduces to that of the functions f. g. and the obtained results often resemble those in foewwrd networks.
In our case, however, we consider general input-output relationships related by temporal sequences of functionals, with no necessary recourse to the mechanism from which these relationships are generated. This is more flexible and natural, since in applications is often not clear how one can describe the data generation process. Moreover, notice that in the linear case, if the target functionals } are generated from a linear ODE system, then the approximation question is trivial: as long as the dimension of h, in the approximating RNN is greater than or equal that which generates the data, we must have perfect approximation. However, we will see that in the more general case here, this question becomes much more interesting, even in the linear regime. In fact, we now prove precise approximation theories and characterize approximation rates that reveal intricate connections with memory effects, which may be otherwise obscured if one considers more limited settings.
Our first main result is a converse of Proposition 3.1 in the form of an universal approximation theorem for certain classes of linear functionals. The proof is found Appendix
Theorem 4.1 (Universal approximation of linear functionals). Let (H, t E R} be a family of continuous, linear, causal, regular and time-homenn time-homogeneous functionals on X. Then, for any >> 0 there exists (H, t R}= E H such that
sup H H.ll sup sup KR
[H((x) Hx(x)) Sc
(11)
ERR |=
The proof relies on the classical Tlesz-Markov-Kakeee Kakutani representation theorem, which says that each linear functional H, can be uniquely associated with signed measure 14 such that Hz( Jx x (s). Owing to the assumptions of Theorem 4.1 we can further show that the sequence of representations { are related to an integrable function (0) + Rd such that (H,) admits the common representation
Hx(x)) 1 xTT=((s)ds, LER, x EE
(12)
Comparing this representation with the solution 7 of the continuous RNN, we find that the approx- imation property of the linear RNNs is closely related to how well p(t) can approximated by the exponential sums of the form (c c T. Intuitively, (12) says that each output y1 = Hz(x) is simply a convolution between the input signal and the kernel p. Thus, the smoothness and decay of the input-output relationship is characterized by the convolution kernel Due to this observation,
we will hereafter refer to ( (H,) and p interchangeably.
Approximation rates. While the previous result establishes the universal approximation property of linear RNNs for suitable classes of linear functionals, it does not reveal to us which functionals can be efficiently approximated. In the practical literature, it is often observed that when there is
5

---

Published as a conference paper at ICLR 2021
some long-tent term memory in the inputs and outputs, the RNN becomes quite ill-behaved (Bengio ct al., 1994; Hochreiter et al.) 2001). It is the purpose of this section to establish results which will show that the rate at which linear
make these heuristies statements precise. In particular, functionals can be approximated by linear RNNs depends on the former's smoothness and memory properties. We note that this is much less explored area in the approximation theory of RNNs.
To characterize smoothness and memory of linear functionals, we may pass to investigating the properties of their actions on constant input signals. Concretely, let denote by e (i 1, I,..,,d) the standard basis vector in Rd, and e, denotes a constant signal with ei,- = e, e;1 Then, smoothness and memory is characterized by the regularity and decay rate of the maps / + (e:))), i = 1, ..... d, respectively. Our second main result shows that these two properties tied with the approximation rate, The proof is found in Appendix B
intimately
Theorem 4.2 (Approximation rates of linear RNN). Assume the same conditions as in Theorem 4.1 Consider the output of constant signals (t) == He,),,, i I....,d. Suppose there exist constants
E N4, y y > 0 such that ys (t) E C(a+1) 10 (R), i 1,...,d, d, and
(2) e.yy (1) o1) as +00, and sup 3 1lp 1e Us 120
S015
k=
a 1, (13)
where yi (²((()) denotes the hthh derivative of yt()). Then, there exists universal constant C(a) only depending on a, such that for any m E N4, there exists a sequence of width-m RNN functionals [Hett R} E Am such that
Cla)yd Bm
sup
1He Hell = sup sup [1((x) - H+(xx)] S SER
(14)
IER ||
The curse of memory in approximation. For approximation of non-linear functions using linear combinations of basis functions, one often suffers from the "curse of dimensionality" (Bellman) 1957]. in that the number of basis functions required to achieve a certain approximation accuracy increases exponentially when the dimension of input space d increases. In the case of Theorem 4.2, the bound scales linearly with d. This is because the target functional possesses linear structure, and hence each dimension can be approximated independently of others, resulting in an additive error estimate. Nevertheless, due to the presence of the temporal dimension, there enters another type of challenge, which we coin the curse of memory. Let us now discuss this point in detail.
The key observation is that the rate result requires exponential decay of derivatives of H, (et), but the density result (Theorem[4.. makes no such assumption. The natural question is thus, what happens when no exponential decay is present? We assume d = and consider example in which the target functional's 's representation satisfies p(t) E C()) (TR) and p(t) (1-www as f - +00. Here w > 0 indicates the decay rate of the memory effects in our target functional family. The smaller its value, the slower the decay and the longer the system memory. For any > 0, the system's 's memory vanishes more slowly than any exponential decay. Notice that (t) p(t) and in this case there exists no B > making
13 true, and no rate estimate can be deduced from it.
A natural way to circumvent this obstacle is to introduce a truncation in time. With T (> 1) can define p(t) (R) such that p(t) = p(t) for t S T, p(t) 0 for t 2 T 1, and p(t) is monotonically decreasing for T S t T 1. With the auxiliary linear functional H. = Jo #())ss we can have an error estimate (with technical details provided in Appendix
sup H4 H.ll < sup EER
|H H.l ER
sup || - H.ll S C (I SER
W
(15)
In order to achieve an error tolerance e, according to the first term above we require ~ e and then according the second term we have
and
O (wTT-=/e) 0 - (wee-/ww)
(16)
This estimate gives us a quantitative relationship between the degree of freedom needed and the decay speed. With p(t) ~ +-(w,) the system has long memory when w is small. Denote the minimum number of terms needed achieve an I,t emrrr as e(w,)). The above estimate shows

---

Published as a conference paper at ICLR 2021
an upper-bound of m(w, c) goes to infinity exponentially fast as w - 0t with fixed c. This is akin to the curse of dimensionality, but this time on memory, which manifests itself even in the simplest linear settings. A stronger result would be that the lower bound of m(w, e) + oo exponentially fast as w -> 0+ with fixed e, and this is a point of future work. Note that this kind of estimates differ from the previous results in the literature (Kammler 19796 Braess & Hackbusch] (2005) regarding the order of m(w,e) e) ~ log(1/e) as + with fixed w or 2 in the L or L sense. Note that the L result has not been proved.
FINE-GRAINES ANALYSIS OF OPTIMIZATION DYNAMICS
According to Section memory plays an important role in determining the approximation rates. The result therein only depends on the model architecture, and does not concern the actual training dynamics. In this section, we perform a fine- tne-ggriined analysis on the latter, which again reveals an interesting interaction between memory and learning.
The loss function (for training) is defined as
Bg Jr(;; e, W,U) = (x))) HT(1))
ee (eT pp(l) p(t) Jxr - (17)
Without loss of generality. here the input time series is assumed to be finitely off at zero, i.e. It = 0 for any t S O almost surely. Training the RNN amounts to optimizing Jr with respect to the parameters (c, W, U). The most commonly applied method is gradient descent (GD) or its stochastic variants (say SGD), which updates the parameters in the steepest descent direction.
We first show that the training dynamics of Jr exhibits very different behaviors depending on the form of target functionals. Take d = and consider learning different target functionals with white noise æ. We first investigate two choices for p: simple decaying exponential sum and scaled Airy function. The Airy function target is defined as p(t) = Ai(solt - f))) where Ai(t) is the Airy x lime- 16 cos + tu du. Note that the effective rate of decay controlled by the parameter to: for S to. the Airy function is oscillatory. Hence for large to, a large amount of memory is present in the target.
function of the first kind, given by the improper integral Ai(t) 1
Observe from Figure 0 that the training proceeds efficiently for the exponential sum case. How- ever, in the second Airy function case, there are interesting "plateauing" behaviors in the training loss. where the loss decrement slows down significantly after some time in training. The plateau sustained for long time before an eventual reduction is observed.
As further demonstration of that this behavior may be generic, we also consider a nonlinear forced dynamical system, the Lorenz 96 system (Lorenz, 1996). where the similar plateauing behavior is observed even for a non-linear RNN model trained with the Adam optimizer (Kingma & Ba 2015). All experimental details are found in Appendix C.3.I
The results in Figure hint at the fact that there are certainly some functionals that are much harder to learn than others, and it is the purpose of the remaining analyses to understand precisely when and why such difficulties occur. In particular, we will again relate this to the memory effects the target functional, which shows yet another facet of the curse of memory when it comes to optimization.
Dynamical analysis. To make analysis amenable, we will make a series of simplifications to the loss function (17), by assuming that is white noise, d = T oc, and the recurrent kernel W is diagonal. This allows us to write (see Appendix C.I for details) the optimization problem as
min eER" WER
J(a,
Σ
agE - p(t) dt.
(18)
We will subsequently see that these simplifications do not lose the key features of the training dy- namics, such as the plateauing behavior. We start with some informal discussion on a probable reason behind the plateauing. A straightforward computation shows that, for l = 1.2...., m.
0J Owk
(a, w) = 2ax 1 (-t)e- wat Σ
ase wit p(t) dt.
(19)

---

Published as a conference paper at ICLR 2021
10a
0.5
10a
0.0
10-
10:2
loss
10
loss
10
10-2
10:1
10-1
10
10
10-1
0
10000 20000 30000 40000
10000 20000
30000 40000 epoch
10000 20000
30000 40000 epoch
epoch
(a) Exponential sum target
(b) Airy function target
(c) Lorenz 96 dynamics target
Figure 1: Comparison of training dynamics on different types of functionals. (a) and (b): using the linear RNN model with the GD optimizer; (c): using the nonlinear RNN model (with tanh activation) with the Adam optimizer. The shaded region depicts the mean = the standard deviation in 10 independent runs using randomized initialization. Observe that learning complex functionals (Airy, Lorenz) suffers from slow-downs in the form of long plateaus.
A similar expression holds for AJ Write the (simplified) linear functional representation for linear daz"
RNNs as p(t: a, w) == En= a,e wet which serves to learn the target p. Observe that plateauing under the GD dynamics occurs if the gradient VJ is small but the loss J is large. A sufficient condition is that the residual p(1; a, w) - p(t) is large only for large (meaning the exponential multiplier to the residual is small). That is, the learned functional differs from the target functional only at large times. This again relates to the long-term memory in the target.
Based on this observation, build this memory effect explicitly into the target functional by con- sidering of the parametrized form
(t) = p(t) + (t),,
(20)
where p is the function which can be well-approximated by the model p. e.g. the exponential sum
p(() = ン= aze- njj=" (with w/ >> 0. 1, ..... ,..,,.)))................). On the other hand, po.- == po - 1//)
controls the target memory, with po as any bounded template function in (IR) n C (R) with sub- Gaussian tails. As w + 0+, the support of Pa.w shifts towards large times, modelling the dominance of long-ten term memories. In this case, if the initialization satisfies X = p. the sufficient condition informally discussed above is satisfied as w + 0+, which heuristically leads to the plateauing.
((-1/w)² 2.
where a", Co, a * 0 and w² are fixed constants. This corresponds to the simple case that m = and Po is the Gaussian density. Observe that as -> 0+, the memory of this sequence of functionals represented by Pw increases. It can be numerically verified that this simple target functional gives rise to the plateauing behavior, which gets worse significantly w 0+ (see Figure 2 in Appendix A.p.nd.i
A simple example of (20) can be (t) a"e--""e + Cge
Our main result on training dynamics quantifies the plateauing behavior theoretically for general functionals possessing the decomposition 20 For rigorous statements and detailed proofs, see Theorem C.I in Appendix C.2
Theorem 5.1. Define the loss function Ju as in 18 with the target p = Pw as defined in 20 Consider the gradient flow training dynamics
d -
( -VJ,((( (0( = 0o: dr
(21)
where (T) == (T) Ww (T)) 2mm for any 2 O. and Ao = (ao, wo). For any w > 0,
m E N_ and On E m x Rmm. 0 < 8 < 1, define the hitting time
To T w, m, 0g) inf (7 2 0: (O, (o) 5).
(22)
Assume that m", and the initialization is bounded and satisfies p(t: 0o): = p(t). Then
To To(6:w, w. m. 0o) 2 co/w min
In(1 + 51}
(23)
Vm
for any w > 0 sufficienlly small, where co and 2 hide universal positive constants independent of w. and 0o-
8

---

Published as a conference paper at ICLR 2021
Let us sketch the intuition behind Theorem 5.1 Suppose that we currently have a good approxima- tion و of the short-term memory part p. then we can show that the loss is large (J = (1)) since the long-term memory part P is not accounted for. However, the gradient now is small (V. o(1)), since the gradient corresponding to the long-term memory part is concentrated at large t, and thus modulated by exponentially decayed multipliers (see (T9 ). This implies slowdowns in the training dynamics in the region I ~ p. It remains to estimate a lower bound on the timescale of escaping from this region, which depends on the curvature of the loss function. In particular, we show that V is positive semi-definite when w = 0, but has (11) positive eigenvalues and multiple o(1) (can be exponentially small) eigenvalues for any 0 < w < 1. Hence, a local linearization analysis implies an exponentially increasing escape timescale, as indicated in 23
While the target form 20 may appear restrictive, we emphasize that some restrictions on the type of functionals is necessary, since plateauing does not always occur (see Figure I]. In fact, a goal of the preceding analysis is to establish family of functionals for which exponential slowdowns in training provably occurs, and this can be related to memories of target functionals in precise way.
The curse of memory in optimization. The timescale proved in Theorem 5.1 is verified numeri- cally in Figure 3 in Appendix C.3.3 where we also show that the analytical setting here is represen- tative of general cases, where plateauing occurs even for non- non-linear RNNs trained with accelerated optimizers, as long as the target functional has the memory structure imposed in (20).
Theorem 5. reveals another aspect of the curse of memory. this time in optimization. When w - 0t, the influence of target functional H, does not decay, much like the case considered in the curse of memory in approximation. However, different from the approximation case where an exponentially large number of hidden states is required to achieve approximation tolerance, here in optimization the adverse effect of memory comes with the exponentially pronounced slowdowns of the gradient flow training dynamics. While this is theoretically proved under sensible but restrictive settings, we show numerically in Appendix C.3.3 (Figure 4 that this is representative of general cases.
In the literature, number of results have been obtained pertaining to the analysis of training dy- namics of RNNs. A positive result for training by GD is established in Hardt et al. (2018), but this is in the setting of identifying hidden systems, i.e. the target functional comes from linear dynamical system, hence it must possess good decay properties provided stablity. On the other hand, conver- gence can also be ensured if the RNN sufficiently wver-parameterized (large m; Allen-ZZhu et al.) (2019). However, both of these settings may not be sufficient in reality. Here we provide an alter- native analysis of a setting that is representative of the difficulties one may encounter in practice. In particular, the curse of memory that we established here is consistent with the difficulty in RNN training often observed in applications, where heuristic attributions to memory are often alluded to Hu al. (2018); Campos al. (2017); Talathi & Vartak (2015; Li et al. (2018). The analysis here makes the connection between memories and optimization difficulti lies precise, and may form a basis for future developments overcome such difficulties in applications.
CONCLUSION
In this paper, we analyzed the basic approximation and optimization aspects of using RNNs to learn input-output relationships involving temporal sequences in the linear, continuous-time setting. In particular, we coined the concept curse of memory, and revealed two of its facets. That is, when the target relationship has the long-term memory, both approximation and optimization become exceedingly difficult. These analyses make concrete heuristic observations of the adverse effect of memory on learning RNNs. Moreover, it quantifies the interaction between the structure of the model (RNN functionals) and the structure of the data (target functionals). The latter is a much less studied topic. Here, we adopt a continuous-time approach order gain access to more quantitative tools, including classical results in approximation theory and stochastic analysis, which help us derive precise results in approximation rates and optimization dynamics. The extension of these results to discrete time may be performed via numerical analysis in subsequent work. More broadly, this approach may be a basic starting point for understanding learning from partially observed time series data in general, including gated RNN variants (Hochreiter & Schmidhuber, 1997] Cho et al. 2014) and other methods such as transformers and convolution-based approaches (Vaswani et al, 2017 Oord et al.] 2016). These are certainly worthy of future exploration.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In Advances Neural Information Processing Systems 32, 2019.
Pierre Baldi, Søren Brunak, Paolo Frasconi, Giovanni Soda, and Gianluca Pollastri. Exploiting the past and the future in protein secondary structure prediction. Bioinformaties, 15(11):937-946, 1999.
Richard Ernest Bellman. Dynamic Programming. Princeton University Press, 1957.
Yoshua. Bengio, Patrice. Simard, and Paolo. Frasconi. Learning long-term dependencies with gra- dient descent difficult. IEEE Transactions on Neural Networks, 5(2):157-166, 1994.
Beran. Statistical methods for data with long-range dependence. Statistical Science, 7:404-416, 1992.
Vladimir Bogachev. Measure theory, volume 1. Springer Science & Business Media, 2007.
Dietrich Braess. Approximation by exponential sums. In Nonlinear Approximation Theory, pp- 168-180. Springer, 1986.
Dietrich Braess and Wolfgang Hackbusch. Approximation of 1/2 by exponential sums in [1, oo). IMA journal of numerical analysis, 25(4):685-697, 2005.
Ayaz Hussain Bukhari, Muhammad Asif Zahoor Raja, M. Sulaiman, S. Islam, Muhammad Shoaib, and Kumam. Fractional neuro-sequential ARFIMA-LSTM for financial market forecasting. IEEE Access, 8:71326-71338, 2020.
Víctor Campos, Brendan Jou, Xavier Giró-i Nieto, Jordi Torres, and Shih-Fu Chang. Skip RNN: Learning to skip state updates in recurrent neural networks. arXiv preprint arXiv: 1708 06834, 2017.
Andrea Ceni, P. Ashwin, and L. Livi. Interpreting recurrent neural networks behaviour via excitable network attractors. Cognitive Computation, 12:330-356, 2019.
Bo Chang, Minmin Chen, Eldad Haber, and Ed H. Chi. AntisymmetricNNN: A dynamical system view on recurrent neural networks. In International Conference on Learning Representattonss 2019.
Tianping Chen and Hong Chen. Approximations of continuous functionals by neural networks with application to dynamical systems. IEEE Transactions on Neural Networks, 4:910-918, 1993.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. arXiv preprint
1078, 2014.
Tommy W. S. Chow and Xiao-Dong Li. Modeling of contimuous time dynamical systems with input by recurrent neural networks. IEEE Transactions on Circuits and Systems Fundamental Theory and Applications, 47(4):575-578, 2000.
Eugen Diaconeseu. The of narx neural networks to predict chaotic time series. WSEAS Trans- actions on Computers archive, 3:182-191, 2008
Adji B. Dieng, Chong Wang, Jianfeng Gao, and John W. Paisley. TopicRNN: recurrent neural network with long-range semantic dependency. In 5th International Conference on Learning Representations, ICLR 2017, 2017.
Doukhan, G. Oppenheim, and M. Taqqu. Theory and applications of long-range dependence. 2003.
Kenji Doya. Universality of fully connected recurrent neural networks. Dept of Biology, UCSD, Tech. Rep, 1993.
10

---

Published as a conference paper at ICLR 2021
Weinan E. A Proposal Machine Learning via Dynamical Systems. Communications in Mathe- matics and Statistics, 5(1):1-11, 2017. ISSN 2194-6701.
Ken-ichi Funahashi and Yuichi Nakamura. Approximation of dynamical systems by continuous time recurrent neural networks. Neural Networks, 6(6):801 806, 1993. ISSN 0893-6080.
Lukas Gonon, Lyudmila Grigoryeva, and Juan-Pablo Ortega. Approximation bounds for random
neural networks and reservoir systems. arXiv preprint arXiv:2002.05933, 2020.
Alex Graves. Generating sequences with recurrent neural networks.
arXiv preprint
1308:033000800 2013.
Alex Graves and Navdeep Jairly. Towards end-to-end speech recognition with recurrent neural networks. In International Conference on Machine Learning, pp. 1764-1772, 2014.
Alex Graves and Jürgen Schmidhuber. Offline handwriting recognition with multidimensional re- current neural networks. In Advances Neural Information Processing Systems, pp. 545-552, 2009.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 6645-6649, IEEE, 2013.
Karol Gregor, Ivo Danihelka, Alex Graves, Danilo Rezende, and Daan Wierstra. DRAW: A recurrent neural network for image generation. volume 37 of Proceedings of Machine Learning Research, pp. 1471. PMLR, 2015.
Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. Inverse Problems, 34(1):014004, 2017.
Boris Hanin. Which neural net architectures give rise to exploding and vanishing gradients? In Advances in Neural Information Processing Systems 31, pp. 582-591. Curran Associates, Inc., 2018.
Boris Hanin and David Rolnick. How to start training: The effect of initialization and architecture. In Advances in Neural Information Processing Systems 31, pp. 571-581. Curran Associates, Inc., 2018.
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19(29):1 2018
Qi-Ming He and Hanqin Zhang. On matrix exponential distributions. Advances in Applied Proba- bility, 39:271 1292,, 2007.
Calypso Herrera, Florian Krach, and Josef Teichmann. Theoretical guarantees for learning condi- tional expectation using controlled ODE-RNN. arXiv preprint arXiv:2006.04777, 2020.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Sepp Hochreiter, Yoshua Bengio, Paolo Frasconi, and Jürgen Schmidhuber. Gradient flow in re- current nets: the difficulty of learning long-term dependencies. In S. C. Kremer and J. Kolen (eds.). A Field Guide to Dynamical Recurrent Neural Networks. IEEE Press, 2001.
Yuhuang Hu, Adrian Huber, Jithendar Anumula, and Shih-Chii Liu. Overcoming the vanishing gradient problem in plain recurrent networks. arXiv preprint arXiv: 06105, 2018.
Harold Edwin Hurst. Long-term storage capacity of reservoirs. Transactions of the American Society of Civil Engineers, 116:770-799, 1951.
Dunham Jackson. The theory of approximation, volume 11. American Mathematical Soc., 1930.
David Kammler. Approximation with sums of exponentials in L,,0, oo). Journal of Approxima- fion Theory, 16(4):384-403 408, 1976.
11

---

Published as a conference paper at ICLR 2021
David W. Kammler. Least squares approximation of completely monotonic functions by sums of exponentials. SIAM Journal on Numerical Analysis, (6(5):801-818, 1979a.
David W Kammler. Li-approximation of completely monotonic functions by sums of exponentials.
SIAM Journal on Numerical Analysis, 16(1))30-45, 1979b.
Diederik Kingma and Jimmy Ba. Adam: a method for stochastic optimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2015.
Qianxiao Li, Long Chen, Cheng Tai, and Weinan E. Maximum principle based algorithms for deep learning. The Journal of Machine Learning Research, 18(1):5998 6022999996666,,,-00000 2017. ISSN 1532-4435.
Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently recurrent neural network (IndRNN): Building longer and deeper RNN. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5457-5466, 2018.
Xiao-Dong Li, John K. L. Ho, and Tommy W. S. Chow. Approximation of dynamical time-variant systems by continuous-time recurrent neural networks. IEEE Transactions on Circuits and Sys- tems Analog and Digital Signal Processing, 52:656-660, 10 2005.
Soon Hoe Lim. Understanding recurrent neural networks using nonequilibrium response theory. arXiv preprini arXiv:2006. 1052, 2020.
Edward N Lorenz. Predictability: A problem partly solved. Proc. Seminar on predictability, volume 1, 1996.
G. Loukas and Gulay Oke. Likelihood ratios and recurrent random neural networks in detection of denial of service attacks. 2007.
Lu Lu, Pengzhan Jin, and G. Karniadakis. DeepONet: Learning nonlinear operators for identifying differential equations based on the universal approximation theorem of operators. arXiv preprint arXiv:1910.03193, 2019.
Wolfgang Maass, Prashant Joshi, and Eduardo D Sontag. Computational aspects of feedback in neural circuits. PLOS Computational Biology, 3(1):e165, 2007.
B. Mandelbrot and J. V. Ness. Fractional Brownian motions, fractional noises and applications. Siam Review, 10:422-437, 1968.
Michael B. Matthews.
Approximating nonlinear fading-memory operators using neural network models. Circuits, Systems and Signal Processing, 12:279-307, 1993.
A. Mohan and D. Gaitonde. A deep learning based approach to reduced order modeling for turbulent flow control using Istm neural networks, arXiv: Computational Physics, 2018.
Ch H Müntz. Über den approximationssatz von weierstrass. In Mathematische Abhandlungen Hermann Amandus Schwarz, pp. 303-312. Springer, 1914.
Yuichi Nakamura and Masahiro Nakagawa. Approximation capability of continuous time recurrent neural networks for non-autonomous dynamical systems. In Artificial Neural Networks - ICANN 2009, pp. 593-602, 2009.
Murphy Yuezhen Niu, Lior Horesh, and Isaac Chuang. Recurrent neural networks in the eye of differential equations. arXiv preprint a904v: 12933, 2019.
C. A. O'Cinneide. Characterization of phase-type distributions. Stochastic Models, 6:1-57, 1990.
Aaron den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint arXiv: 00499.99.09999.... 2016.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. volume 28 of Proceedings of Machine Learning Research, pp. 1310-1318, 2013.
12

---

Published as a conference paper at ICLR 2021
Yulia Rubanova, Ricky T. Q. Chen, and David K Duvenaud. Latent ordinary differential equations for sregularly-sampled time series. In Advances Neural Information Processing Systems 32, pp. 5330-5330. Curran Associates, Inc., 2019.
David E Rumelhart, Geoffrey Hinton, and Ronald J Williams. Learning representations by back- propagating errors. Nature, 323(6088)5533-536, 1986.
G. Samorodnitsky. Long range dependence. Found. Trends Stoch. Syst. 1:163-22 (11663--,72 2006.
Anton Maximilian Schäfer and Hans Georg Zimmermann, Recurrent neural networks are universal approximators. Artificial Neural Networks ICANN 2006, pp. 632-640, 2006.
Anton Maximilian Schäfer and Hans-Georg Zimmermann. Recurrent neural networks are universal approximators. International journal of neural systems, 17(04):253-263, 2007.
Alex Sherstinsky. Fundamentals of recurrent neural network (RNN) and long short-term memory (LSTM) network. arXiv preprint arXiv:/808.03:: 2018.
Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling Nesterov's s accelerated gradient method: Theory and insights. In Advances Neural Information Processing Systems, pp. 2510-220022 1-18,, 2014.
Otto Szász. Über die approximation stetiger funktionen durch lineare aggregate von potenzen. Math- ematische Annalen, 77(4):482-496, 1916.
Sachin S Talathi and Aniket Vartak. Improving performance of recurrent neural network with relu nonlinearity. arXiv preprint 151.071 2015.
M. Taqqu, Vadim Teverovsky, and W. Willinger. Estimators for long-range dependence: An empir- ical study. Fractals, 03:785-798. 1995.
Tianping Chen and Hong Chen. Universal approximation to nonlinear operators by neural networks with arbitrary activation functions and its application to dynamical systems. IEEE Transactions on Neural Networks, 6(4):91 111977, 1995.
Trieu Trinh, Andrew M. Dai, Thang Luong, and Quoe Le. Learning longer-term dependencies in RNNs with auxiliary losses. In ICML, 2018.
Tzu-Hsuan Tseng. T. Yang, and Chia-Ping Chen. Verifying the long-range dependency of mnn lan- guage models. 2016 International Conference on Asian Language Processing (IALP), pp. 75-78, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
13

---

Published as a conference paper at ICLR 2021
A UNIVERSAL APPROXIMATION THEOREM OF LINEAR FUNCTIONALS BY LINEAR RNNS
A key simplification of considering linear functionals is due the classical representation result below, which allows us to pass from the approximation of functionals to the approximation func- tions. In short, this theorem says that while for each measure μ. æ Sp x du((s defines linear functional, this is in fact the only way to define a linear functional: for any linear functional H there exists unique measure μ such that (x: SR x. du(s).
Theorem A.1 Bieez-Markko-Kaakuaa linear functional. Then, there exists a unique, vector-valued, regular, countably additive signed measure μ I such that
representation theorem). Let H X - R be continuous
H(x) xg dd(ss Σ
[ xe.ddi((s.
(24)
Moreover, we have
|
sup $1
H (z)) = [ = Σ (I))...
(25)
Proof. Well-known, see e.g. Bogachev
2007). CH 7.10.4.
We will use the representation theorem to prove Theorem 4. First, prove some lemmas. The first shows that there in fact a common representation of sequence of linear functionals satisfying the assumptions of Theorem 4.]
Lemma A.1. Let {H,} be family of continuous, linear, regular, causal and time homogeneous functionals on X. Then, there exists a measurable function p [0, o0) - 12d that is integrable, i.e.
d [P]l = Σ (ax(s)lds < 80
(26)
1=1
and
H2(x) - [] 00
(s)dds
t R.
(27)
In particular, { (He) is uniformly bounded with sup, H, uous for all x E X.
|| = [Ipll=((0.co)) and t + H.(x) is contin-
Proof. By the Senn-Marrov-Kaautan representation theorem (Theorem A.1 for each / there is unique regular signed Borel measure 14 such that
H₂(x) = f xT (s),
(28)
JR
and E, [M,, ||H Since {He} is causal, we must have fe x.J due(s) for any and thus
H((x:) S x. dp))).
(29)
Now, by time homogeneity we have
[ x dpp(s) = H.((r) = Hetr
I
(30)
-00
Take T -l and set / = -40 to get
11(x)) / xT-c4((s).
(31)
14

---

Published as a conference paper at ICLR 2021
Note that have ||,] oc)) (11ool1((0,000)) ||Hlll ||Hlll and continuity follows from the fact that
H2+ - H1(xx) = 1.-0 (1246-8 x(-5) dd((s) du(ss)
(32)
/ 11046--- - - -0-
which converges to 0 as 8 + by dominated convergence theorem. Finally, we will show that each 44 is absolutely continuous with respect to À (Lebesgue measure). Take measurable E' C [0, oo) and set E' =0, oo) E. For each 2 set K2 C E, K" C E' where K K are closed and μ (E)) Kn.) S 1/n, ( E' K,) I 1/n. For fixed E {1, [L..... ... d]. define x(1) be such that _ = 0 for all j * and all For = i, we set 21-s,i = 1 if s E Kn and 0f s E K which can then be continuously extended to [0, oo). Observe that by construction, 2 + 0 for A-a.e. s, thus by dominated convergence theorem
such that x(E)
lim H+(x!")) = (x(
(33)
n-v0c
This shows that μ absolutely continuous with respect A, and by the Radon-Nikodym theorem there exists measurable function Ps : [0, oo) + I such that for any measurable A C R we have
f dps((s) f p;(s)ds,
(34)
for i = I,...,d. d. Hence, we have
H: Hx(x) = 1 00 s()sss
(35)
with ([,,0)) = =i (p:(s)lds = |Ill|i 00)) < 00.
Lemma A.2. Lel p: [0, x0) + Lebesgue integrable function, i.e. I1lll))(00,0)) < 00, Then, for any > there exists a polynomial p with p(0) such that
|| p(= )l 21
(p(t) - )(e Se.
(36)
Proof.
The approach here is similar to that of the approximation of functions using exponential 1986). Alternatively, one may also appeal to the density of phase
sums (Kammler 1976. Braess
type distributions (He & Zhang 2007 O'Cinneide 1990) in the space of positive distributions, and
generalizing them signed measures.
Fix e > 0. Define
pp log u), 0,
E (0, 1]. ==0
R(u)
(37)
Then, can check that
|R|| [ = [Iell)((0,)))) < 80.
(38)
By density of continuous functions in L there exists continuous function on [0, 1] with i?(0)
0 such that
R (o. S c/2.
(39)
By Müntz-Szász theorem (Müntz 1914 Szász 1916). there exists a polynomial p with p(0)
0
such that
l1g ((.1)((o1)) S c/2, and q(u) = p(u)/u/ is also polynomial. Therefore, we have
(40)
[-¹ [R(u)) - p(u)/uldu
||e p(e 112+0000000)
(41)
< [R(u) F((u)ddu + L. [P(()) p(u)/uldu S..
15

---

Published as a conference paper at ICLR 2021
We now ready to present the proof of Theorem 4.1
Proof of Theorem 4.7 By for each {He} H we can write
H((x) I/²0 21 10 (e c)ds.
(42)
By Lemma A.1
we can write
H((m) = 1/-0000 T (())ds,
(43)
where is integrable. Thus, we can apply Lemma P., i I....,d with (0)) such that
A.2 to conclude that there exists polynomials
Elle- - pi(e pi--pi(e)) ((0,00) S..
(44)
Notice that we can write each (u) = Ei=1 anp for some m equaling the maximal order of {pr). Taking W diag(-14 ..... -m), (1,.... .) and Uíj ajs we have
(U (UT c)2 = pi(e
d.
(45)
Consequently, we have for any æ with ||00| 1o000 1.
///0000 =TFod(s)ds - Soo "t
00
H2((x) - fx)(2)) =
$ Σ 0
/ (ma-nillpa(s) - pi(e ds S Σ llp - pa(e (120000))))00)))
(46)
Se.
B APPROXIMATION RATES AND THE CURSE OF MEMORY IN APPROXIMATION
We first give the proof of Theorem 4.2
Proof of Theorem 4.2 We fix i E (1.....d d} below until the last part of the proof. By Lemma A.1 there exists pc(l) (0, oo) such that
(1)() = He(es) = S p.(r)dr, 12 0.
(47)
By the assumption,
p (1) = ole 081- as + 00, = 0,...,a a.
(48)
Consider the transform
0
0, E (0, 1].
(s)
(49)
For A 0,..., a, can prove by induction that
&
a aa+1 1
())
((a+1) log
d 12) = (-1)* Σ
c(i k)
(50)
B
s sk+1
1=0
16

---

Published as a conference paper at ICLR 2021
where c(j, k)) are some integer constants. Together with the assumption, we have
9: (2) (e  /
Σ kii
k
+
(
k
lcl, C(a),, (51)
B
where C(a) is a universal constant only depending on a. Note that for j = ,0....,. a
(a+1) logs
(t)
1k+118 lim p
(t)
ia kil
lim 6++0+
gk+1
lim
e Dr
a+1
0,
(52)
hence (s()) C [0, 1] with (0) q,
11) (0)
9i (0) (0) 0. By Jackson's 's theorem (Jackson
1930), for m 1, ...,, there exists a polynomial Qi,m of degree m 1 such that
|1: -imml1==(10011 v C(a)r
(53)
m
Denote the polynomial Qi.m
m2-
Qim (8) =
Σ y=Ul
aiss''
(54)
and define
(t) = E -ati o Qiim (E (
(55)
Then we have
(t) c. ce WWtt
(56)
where
(1, ...1....111 1):
(57)
8
29
W
a+1
(58)
a+1
41 = (0:,0; 04.1, O..m
(59)
With a change of variable s = - we have the estimate
|lp: - & @smlll
(pi(t) - (0).m(t)cc
(.¹) Pi
-(a + 1) logs
a
(8)m(()
ds
B
Bs
(60)
+
(- 14:(s) - -s)mds)
8
< C(a)y
Bm
Finally we define U [ui,.... Ua] E Rdmxd and have
c e Wiu (é1.m(t), (t), 0d, (t)).
(61)
Recall the dynamical system 6
hr (Wh, hr, + Ux));
9r = c Th,,
(62)
which is together determined by the parameters W, U. Similar the argument in the proof of Theorem 4.1 for any æ with |= E 1 and f, we have
Cla)yd 3m
(x) H+(+)) s Σ lle - @mmmll _
(63)
17

---

Published as a conference paper at ICLR 2021
The curse of memory in approximation. Now we explain more technical details of why Theo- rem 4.2 implies the curse of memory in approximation, as pointed out in the main text. We assume d and consider example
Hx(x)) = I ((s)ss t t2 0,
(64)
in which the density satisfies p(1) (R)) and
p(t) ~ (-++w as +00.
(65)
Here w > 0 indicates the decay rate of the memory effects in our target functional family {H,}. The
smaller its value, the slower the decay and the longer the system memory. Notice that y()(t) (t) = p(t),
and in this case there exists no making the following condition (13) in the main text) true:
(k) (1) ) as +00, U
and
sup B 220
(k) l Di 5
(66)
and no rate estimate can be deduced from it.
A natural way circumvent this obstacle is to introduce truncation in time. With T (> 1) define p(t) (R) such that p(t) p(t) for t S T, p(t) 0 for t T 1, and p(t)
is monotonically decreasing for T s s T + 1. Considering the linear functional H.(a:) =
So (t-sD( we have the truncation error estimate
(f, (p(s)
H H.(x)))
| 1x
(67)
Now the conclusion of Theorem 4.2 (i.e.
63 is applicable to the truncated {Hl. } (with 1), and
we have for v/3 > 0, there is linear RNN (U, W, e) such that the associated functionals { E H... satisfy
Cr
C
(t)
Cw
ST
sup tE
|i,
H.ll
sup
(68)
3m
Bm
+20
m
B2Tw+1
It is straightforward to verify that when f = 2/T, the right-hand side of which gives us
68
achieves the minimum,
Ow T--
sup || Hell ER
(69)
m
Combining 67 and (69) gives us
sup
H₁ Aell S
T-
T
W
Tl-
(70)
tER
m
In order to achieve an error tolerance e, according to the first term above we require T ~ -__ and then according second term we have
WT 1-w
(Wwe ( (W(w=+))
m
(71)
This estimate gives us a guantitative relationship between the degree of freedom needed and the decay speed. When w is small, i.e., the system has long memory, the size of the RNN required grows exponentially.
C FINE-GRAINED ANALYSIS OF OPTIMIZATION DYNAMICS
C.1 SIMPLIFICATIONS ON THE Loss FUNCTION
Recall the loss function
Jr W,U) Ez l' WCT p(t) (dt
(72)
The simplifications Eg Jr listed follows.
18

---

Published as a conference paper at ICLR 2021
1. Take the input data to be the white noise, so that
distribution
2T ZT-
dBt.
(73)
where B, is the standard d-dimensional Wiener process. As consequence, simplifying 72 via Itô's isometry gives
= C W.U) I-" I -((t) cwe p(t) -
[c, W
(74)
2. We focus on the temporal dimension and take the spatial dimension d d= in 774 More- over, investigate the effect long- term memory, is necessary consider the training on large time horizons. Hence, we take T - 3o to get
(c W;b) = /0 (cTewb
w p(1)) dl.
(75)
where b is the sole column of U in 74 and p(t) becomes scalar-valued target. This corresponds the so-called single-inpur-singll-uuppp (SISO) system.
3. Due to the difficulty of directly analyzing V Wee and Viyew, we consider further simplified ansatz. Assume that W is a diagonal matrix with negative entries (to guarantee the stability of the model). That is, W -diag(w) w) with w E RT. Then
combine a = b o e (where a denotes the Hadamard product) and rewrite the model as
m
p(t: c, W. = TT w
age e La Te & a(t;a, w).
(76)
The optimization problem 775) becomes
min (a, w) =
1
Σ
m
age aa--iit
wit
p(t))
dt.
(77)
AER EERT
Here we omit the subseript
4. We apply a continuous-time idealization of the gradient descent dynamics by considering the gradient flow with respect to Ja, w). That is,
w'())=--o -a w(T)), - d'(r) VaJ((())) w())
(78)
with some initial value a(0) = do E R", w0) = wp E 1
As we will show later, applying the training dynamics 78 to optimize 77 is able to serve starting point in the fine-grained dynamical analysis, since still preserves the plateauing behav- ior observed in the optimization process (see Figure TT. provided additional structures related to memorics as discussed next.
C.2 CONCRETE DYNAMICAL. ANALYSIS AND THE CURSE OF MEMORY IN OPTIMIZATION
We prove Theorem 5.1 in this section. The basic insight is, by adding long-term memories in targets, one can increase the loss with little effect on the gradient and Hessian, which leads to significant slow down of the training dynamics near the short-term memory parts of the targets. Therefore, Theorem 5. proved subsequently in the following procedure.
1. We prove that J.g has a large value but small gradient when p(t; a, w) = p(t).
OOn that the spatial dimension plays little role in the previous approximation analysis (see the proof of Theorem 4.2), since each spatial dimension be handled separately.
"The time horizon is always taken as oo in the whole analysis. Note that here we also omit an index m (width of the network, relating the model capacity), since it remains unchanged in the following content if specified.
19

---

Published as a conference paper at ICLR 2021
2. We prove that when p(:: a, w) p(t). the Hessian J/ is positive semi-definite for w = 0, but for finite, small > O, V Jww has (1)) positive eigenvalues and multiple o(1) eigenvalues.
3. Based on these results, we perform a local linearization analysis on the gradient flow (1 initialized by p(t; ag, wo) = p(t), from which and by continuity the timescale of plateauing is derived.
(1) Preliminary Results
As discussed around
20 we consider the target functional with a parametrized representation
m Σ j=1
(t) = p(t) + Po
wjt aje- aje
+ po(t 1/w).
Here, aj a" (wf) * 0, wj 0 and w # w for any * j. i.j E [m=), and m < m. The former requirements are just non-degenerate conditions, and the last requirement ensures that the model can perfectly represent the well-approximated part of the target, p(t). The memory in the target controlled by Po. (t) po(t 1/w), with Po as fixed template function which satisfies the following assumptions.
Assumptions on Po. (i) pa(l) # (i) po E (2(R) (RR); (iii) po bounded on R, i.e. |PPolL== (R) < 30: (iv) lim po(() 0
Remark C.1. The above assumptions (i)ii)iii)) are rather natural, and (iv) only restricts the single side tail of Po to be zero. In the following analysis, we further focus on po with light tails, e.g. the Sab-Gaassian tail
(pu(t)) S cue cue
-212
(79)
for some fixed positive constants co, C1, lo- Obviously, Gaussian densities and continuous functions with compact supports are falb-Gassiin functions.
We begin by the following preliminary estimate that used throughout the subsequent analysis. Lemma C.1. For any N, 0 and 0, let
Anw = / l'e wt (o (1)ldl.
(80)
Then
Anw(() (w) is monotonically decreasing on (0, oo);
lim (w) = 0;
In particular, if po is sub- Gaussian, we further have
An S w "e me- n/w (02 nn + +c)), we (0, 2c1/w))
(81)
Here 02 া. C3 c0 1, and S hides universal constants only depending on n. and Po, to Co.
Proof. (i) Obviously (nw S Anww for any w1 > W2 > 0.
(ii) By the assumptions Po. get
lim (oo. (t)
lim Ipo(t 1/w)l lim w-
=
At 2 0,
and Mo = p [R) (R) < oc, which gives t" - IPo. (t) S M E L ([0, oo)) for any E N, w > and w > O. By Lebesgue's dominant convergence theorem, we have
/ ww lim (t) 0, Vn N, Vu 0. w
lim (w) -++
(82)
-++
For any n N+, [n] (1.2....,,))
20

---

Published as a conference paper at ICLR 2021
(iii) Now we estimate A (w)) under the sub-Gaussian condition 79 Suppose 0 << < 1/to, have
(00 t"e 1"e-""lPo(( 1/w)ldt
An)(())]
/l/utt
ee 1e - (/w)ldl + / /1/u Le Pe - 1/w)
1/
the f"c 1/w) dt - 11 + 12 13.
1//
Then we bound /, 1n and I3 respectively:
1/wtto
the e dt S Moe ww(1/w1o)) 1/Wtto tt
I $ Mo
1/w-to
1/w-lo
Mae e w-/ (1 + wto) ( (1 )ut (n 1)wnt
S Mye "/-w//( (lo + w),
where 102, and x hides universal constants only related and to- Let 1/c, 20 have
( -1/
(s + 1/w)" "occe"""loooo (po(s)dss S [T( +s+ 1/w)
1 = e w//w
cge =10 do,
-11/
where
f 1/w
(s+ 10 ds ds= e
ws -
(s 1/w)"e -0 201l0==]]] )² ds
-1/w
(1t) + |1/ orwl)" 202 dt
o 12
Ch ozw)n-k 2 2f6 the
12
20 dt
c w2
(1/w))) n- (V2o) k+ r
k +1+1)
2
k=0
holds for any w E (0, 201////)) Here the last inequality is due to the Mellin Transform absolute moments of the Gaussian density (see Proposition in Li al. (2005)). The argument is similar for I3, which gives the same bound as Iz.
Combining all the estimates gives the desired conclusion. The proof is completed.
The main idea to analyze plateauing behaviors is to investigate the local dynamics of the gradient flow (21) when أ P, then extend the results to the setting á p by continuity. Recall that both of them are exponential sums, we can obtain the relation of parameters hetween ý and p. according to the following lemma.
Lemma C.2. For any m N4, let (A....., Am) with X + > for any & j. 4, [m]. Then the series of functions { Ji=1 is linear independent on any interval RR
Proof. The aim is to show
Σ Ae 0,tel= 0, Vi [m].
(83)
83 holds trivially for m 1. Assume that 83
holds for m 1, then
Ge = 0, te 1
Ci -mm) + cm = 0, tel
(84)
c:(A: - Am) Am) = E.
21

---

Published as a conference paper at ICLR 2021
By induction, we get C2 Am) 0 for any 1,,.. 1. Since λ1, Am are distinct, we have G; = 0 for any = 1, m 1. Together with (84), we get Cm = 0, which completes the proof.
Definition C.I. Let m 2 m' For any partition P: [m]] = Uf with Ij, n NI = Ø for any
f1 * 12. J1.32 E {0} U im"), and To = -o.
Jor with Iu.r, n Io.r. = Ø for any T1 # r2. r1 E [to], where I + 2 for any j E [m*) and To.r # 2 for any E [io] (o 2),, define the affine space (with respect to P):
Mp = (a, w)
(
R
x R
Σ
a; = aij wi = w for any i E I, j E [m"];
TET,
0, Ea=0, W/ = Ur + w for any E Io r E [5o] and j E [m*]]
iEZo,r
Denote the collection of all such affine spaces by M == Mp.
The following lemma characterizes the relation of parameters, by showing that M is exactly the set of equívalent points to (a", w²) for the purpose of representation via exponential sums.
Lemma C.3. For any (a, w) E Rmm RT, p(l;a, w) = p(() + (a, w) E M".
Proof. (i) (+) Since (a, w) E M", there exists such that (a, E Mp. Then for any 2 O.
m
m
p(l;a, Σ
age wit
age mit
age
age -upt
i=1
i=D
r=liEfor
5=1 iEZ,
io
m
m
age -wp = =(())
ai
e
Og
iEZ
j=1
= {iE [m]: : wi = wj} for any j E [m*], and Ia = =i E [m] w; # w for any j e (ii) (+)),
[m']]. Recall that p(t) = En age "itt is non-degenerate: 03 * 0, wj > 0 and w F w for any i $j E [m*). we get [m] T , In nI,, 2 for any j1 # j2, J1. {0} [m*]. Combining Lemma C.2 and the non-degeneracy of p I, + for any j [mm]. Assume that there are ip different components in (wi)iez,> say u1. : Ulg. then 2, J wj for any r E [Po] and
j [m=). Let Io.r {i Io w; ) for any E [fo]. we get Io,r # Ø for any [fo]
(if Io + Ø), and Io = - Ju.r and Io.m n Io.ra = Ø for any r + r2, 11,72 E [fo]. Hence
[m] = In with Io = - To.r forms a P defined in Definition C.1 and
0 = p(t;a, w) p(t) =
Σ
agc
Wit
Σ j=1
Laje-us
F=1
aGe wet Σ
aje
aje-uje wie
j=0
j=l
m
m
Σ IEIo.r
0ge Wit
+
a&e Wit
Σ
age - m3e
1=1 IEI,
1=1
Σ Io
e Upt
Upt +
0j
a3
E uitt
Again by Lemma C.2 we have ΣiEr, a; 0j for any j E [m*] and ΣiEto as = 0 for any
E [áo], which gives (a, w) E Mip. The proof is completed.
22

---

Published as a conference paper at ICLR 2021
Remark C.2. Let Io
It is straightforward to check that for any partition P, the dimension 1) m m". In addition, can be verified that the cardinality of MM
2.
of Mp ([Ig) En
m
m m
where
m m
is the Stirling number of the second kind. 5
(2) Loss and Gradient
Now show that as w - 0+, the loss Ju remains lower bounded, while |VJulla converges to O. This implies that the loss will saturate at a high value when learning long-temn memories.
Proposition C.1. For any (a, w) E Rm x BT satisfying p(t: a, w) = p(t), we have
Ja(a, w) 2 C(po) > 0, Yu E (0, C" (po)),
(85)
where C(pu),
(Po) > are constants only depending on pu- That is, the loss is lower bounded
uniformly in
Proof. Recall the assumptions Pa. have po(() # 0 and Po C(R). Let 4 E R such
that Pa(11) ) F 0. By continuity, there exists bo > such that [po(t)] 2 [po(t)]l/2 for any t E
[t] 60, 1 + 50]. Hence, for any w O sufficiently small such that -1/
6g. we have
/.a0 pē(t 1/w) = [r (t(t)dt
| l 30)
pb(t)dt 2 Sulpo(ti))3 0.
11-ō0
Fix any (ā, u) E Rm RR such that p(t: 0, 1)) = ptt). Then
1
Já w) [1ă(1; wh) p(1) Po. (4) (0)1 = ll 12.0000 2 2 5000o((1)12 >0,
which completes the proof.
Proposition C.2. For any (a, w) E Rm x R satisfying p(t: a, w) = p(t), we have
lim
V (a, w)ll 0.
(86)
In particular, if po has the sub- nab-Gaussian tail 79 the estimate
Ja, w))l222)222 S Vmw e- ---iinn (c
+ Whin (1 (
(87)
holds for any E (0, min 1/to, 201 20s/Wmint). Here Wmin == minse[m] wi > 0. C2 C3 are
constants only related to C1, to. and S hides universal constants only depending on Po. to. co.
C1.
Proof. A straightforward computation shows, for k = 1,2, .., m
aJu (a. w) = 2
02
a
220
(88)
Dap
Wk
W/
Wk + w
1=1
j=1
aJu
(a, w) = -2a
a2
m
aj
+ 222a A (,)())))
(89)
Owk
(wk + w;)2
(w) + wzy
Fix any (a, wh) E Rmm RT satisfying p(1; a, vi) = p(t). By Lemma C.3 we have (ā, w) E M
Recall Definition C.I there exists partition P: [m] تf with Io _ where I, # 2 for any j E [m"] Io,r # Ø for any r E [6u] (if Ta + Ø), such that (ā, w) E MT. which gives
*That is, the non-degenerate case. Obviously, To * Ø implies an uncountable Mp. but they are all degenerate.
'The result follows from hasic knowledge of combinatorics. See details in the proof of Theorem D.1
23

---

Published as a conference paper at ICLR 2021
that ΣiEI, à; oj, dù; wj for any E Iy and j E [mn]; Σ Lie...- à; 0, 20; 24 # w for any i To.r. r E [to] and j E [m*]. Therefore, for any n E N,, we have
m
a
m
[kk + 1
c + w2)m
40
(wi + wn
(w0 + w;
(w) + wz)
5=1 s=l
10
EiETor ài
n
EiEz, àj
Σ
m
aj
0.
(90)
(1k + U2,
(20k + w3)m
(w + w3)²"
/=1
j=1
This yields
OJw (ā, ii) (( Oaz
OJu (å, u) 20x (ūkk
Owk
and hence
m
(V, 0013
A (2x)) (Z
By Lemma C.1
we get lim V u = O.
Po has the sub-uuusueee Gaussian tail 79. again by Lemma C.1 the estimate
Anw (1xk) s Dn E w mee Wrin/w (cr (o 1mi
+ C3
(91)
holds for any N, w (0, min 1/tu. 201 (min) } and & E [m]] Here Umin minge im] Wù > O, C3 > 1 are constants only related to c1, to. and S hides universal constants only depending on and Pa. to. Co, c1. Therefore
Já w)ll2 S Vmnw e- -aaal (c) + Omin (1 + [(]] w WET (0.1).
The proof is completed.
(3) Eigenvalues of Hessian
Now we show that minimal eigenvalues of J., also converges to 0 as w - 0+.
Proposition C.3. For any (a, w) IR" RT satisfying p(l; w) p(l), denote the eigenvalues Aam (w). If
of J w) by (w) dg(w)
m², have
(w(w)= > 0, 1,2, ml
(92)
lim (w(w)= 0, m' +1, + 2,... 2m --+
(93)
for w > O sufficiently small, where m' < 2m + Iol I m + m. particular, if po has the Gabb-Gassiinn tail (79). the estimate
(u(w)) S w -2 Wwnn/w /w
C2
2
+ C33
) (1 [|alloo)
k m' 1,m' + 2,. ,2m (94)
holds for any w E (0, min 20, Wmmn))) Here Wmin = minje[m] w; > 0. c2 Cg > are
constants only related to C1 lo, and S hidey universal constants only depending on Po. Co. C1-
24

---

Published as a conference paper at ICLR 2021
Proof. A straightforward computation shows, for j.j = 2, ,,
Ju (a,w)
2
(95)
0az0a;
Wi + W/
J² (a, w)
-2aj
k # J.
(96)
da.Oro
(wk + wy)2"
Jw
(a, w) 2
az
a2 2w
+ 2ux
(97)
OazOrck
[wk + w2)2
(wk + wz,
i=1
Ju (a, ()) (wis + w,y33
4aya
h # j,
(98)
of 2w
(a, () = -4a
+
2ap (w
(99)
OrogOrck
(uk w/) 3
(ik + wgs)
Fix any (a, w) E RI' x RT satisfying p(t; a, u)) = p(t). By (90). we have
0 (a, (0)
2
da
ii + وز
0 Ju (a,
((, 10)
-2ā
(k + j),
J.
(a, ())
āk
+ -22 1, (10k))
(wi 12z)
OaxOwn
20r
0 Jw
@
07
(a, w)
(k 5),
(ā, w)
2å 2, (wxx
Owr
(ux + 15
awx
200
Let
Ja. w) = llĀ(t; a, w) p(t)]]
(100)
m aje w- w
are - wil
L2(0,00)
and
O x
Diag( Al)
(a, w) = Diag( i ( (w)
Diag(a (w))
where (w) (n = 1, performed element-wisely One can verify that
V'Ia(a, v²J w) 2a, w).
(101)
Then we analyze 2 Ja, v and (á, w) respectively.
i v2J(a, w) Obviously (ā, w) is a global minimizer of Ja, w) due to J(ā, w) = 0. Hence VJ(ā, i) and V²J(ā, w)) is positive semi-definite. We further show that 4 J² w) has multi- ple zero eigenvalues when m > m=. In fact, since
J2. dagda, (ā. () we + wy Daydw,
Jº.
-20; (ιæ + +,,))²² Ow.dw,
JJJ
4āgåj
(a, w)
(a, w)
(10s + wz
it is straightforward to verify that for any i E Ip, p [mn] and any i,j E Io [to].
()) V²J wi àz v²J(a, m) = à; V²J(a, 20 m
where t denotes the i-th row of matrix A. Notice that Eieta, V²J(a, () = 0 for any r [t0]. we conclude that the Hessian v²j(ā, 2)) has at most 2m + is is S 2m + IT <
m + m² different rows, which yields rank 2 w)) S 2m + Iool S + m². Therefore,
'Here i2 Hr [1o] [Zarl > 2H. When Io the upper bound is 2m"; when Io # Ø, since Io,r # Ø for any r [io]. let á1 := Kr [io] : [To-I| |}} and is defined as before. Then il + i2.
[To| = :0 [Torl 2ig in 10++iz 82- The last inequality follows from Tol Em [, S mmmm"..
25

---

Published as a conference paper at ICLR 2021
the number of zero eigenvalues of V [a, a) 2 dim fo E R
V2J(a, -2 .z= 2m
[[a, r)) 2 2(m m²) [To| m m.. Since V²J w) is positive semi-definite, all the non-zero eigenvalues must be positive.
(ii) (á, d0). Let
G : E: 1vl S I (wx))]
c 6 = (y E : ly + سس (1ix)) - A (
By Gershgorin's circle theorem, for any eigenvalue of (a, w) say \(w), we have M(w)
U U GGG)). Combining with Lemma C.I get
[(w)] max (lâx) 2 ((ok) 1 (wx))) + 0, w +
(102)
KE [m]
If Po has the sub-Gaussian tail 79). by (T., we further have
[(()]
max kE[m)
(lãx 2, (wx)]
1 (1xx))
S 2 Whinn/
(c2
(1 + l[ālloo), w E (0, 1], + C3
(103)
where w E (0, min (1/2, 1/to 1/to, 20q [mii }), Wmin == min.e[m] W; > 0, C22 03 > are constants only related to CI, fo. and S hides universal constants only depending po. to. co. C1.
Combining (i), (ii) and applying Weyl's theorem gives the desired result.
(4) Local Lincarization Analysis
The previous analysis can now be tied directly to a quantitative dynamics via linearization argu- ments. It shown that under mild assumptions, the gradient flow (2I) can become trapped in plateaus with an exponentially large timescale. That is, the curse of memory occurs, this time in optimization dynamics instead of approximation rates.
Theorem C.1 (Restatement of Theorem 5.1p. For any w > 0, m E N+ and do (ao, wo)
1Tm X P 0 < 8 < 1, define the hitting time
To To( w. m, 0o) inf (r 2 0: (T) 0ol12 > 8},
(104)
To (ō w, m. 0o) inf {r 2 0: (O,(( - (O)) ) > 5}. Assume that m >> m,, and the initialization satisfies p(t: 0o) ~= p(t). Then we have
(105)
lim To To(6:w, w. m, 0o) = lim (6 w. m, 0g) = to0. --5
(106)
--0
In particular, if po has the sub- Gaussian tail 79). and the initialization is bounded as (ao, wo)
[a amI"m x [wf, w with constants af < a 0 < w/ < wh we further have
od(o,,,m, 0o) 2 To(o;w, m, 0o) Z w² w " min { 6 In([1 + +8}
(
(107)
for any (0, min (1/2, 1/to, 201 /w sufficiently small, where 2 hides universal constants only depending on to Co. C₁, wh, af and of.
Proof. Consider the asymptotic expansion with the form
= =
Σ (80(()) ( + 50 (0))))+)6607) (662)
(108)
for some = (0, 1) (with 8 < 1) and = 0(1 0 0, For consistency, we have @0 (0) 0g and e (0) = 0 for 1,2,.... By continuity, To and (T) Boll S å for any T [0, To]. The aim is to quantify the scale of To-
Here 0* (r) denotes the i-th term in the asymptotic expansion of (T), not the i-th power.
26

---

Published as a conference paper at ICLR 2021
Let 9u (o)( and Ho V2J The local linearization
21 shows
d
_ ml (T) 90 Ho((w 0o) 068%) E [0, ra..
+
dr
Combining with (108). have
d dr
0% (r) = 9o (r) Bo), (0) = 00:
at ((1) scale,
d
dr (T) = (H), (0) = 0,
at ( scale,
dr (T) = (T) (0) 0,
at O scale.
Therefore
(T( 0o (fe Ho 90.
(T) -HoT 0+ (0) = 0,
which gives
90 + 0 (((-)=a)(((-
(T) = 0o -0000/// Hos
TE [0, rn]-
(109)
To achieve a parameter separation gap do, ie. (T) 00ll2 = 60 with do co, c E (0, 1]. we need to take such that
I. Hos d8
50
gu
(110)
2
2
AP consisting of the eigenvalues of Ho with A 2 .... 2 A2m- Then
Let Ho ATA be the eigenvalue decomposition with P orthogonal and diag(AA, ... A2m)
[1 Hos ds
-|p0 PT (1" ds
90
=
Pgo
e
As
ds
110012
2
2
2
S I1goll2 max
max (E(2m)].Aept
[>,
le ArT - 11,
straightforward to verify that ((T;A) = le Ar 11. t 2 0 monotonically decreases on IR for any 2 Hence
[ Hos ds
(e A2m (emmm 1), Agm < 0,
go
l1golle
-Aam T,
(111)
A2m 2 0,
and the right hand side monotonically increases on 2 0. Combining (10). 111) gives
- (e A2m 1),
1
A2m < 0,
11ool12
{
(112)
A2m 2 0.
We discuss for different cases:
(i) [gol| = 0. Obviously the inequality
112) fails since
110 fails for any 7 2 0, which gives
T0 +o0;
(ii) ||gol22 * 0 and Nam 2 0. By 112). we get 2
80 Mall
(iii || * 0 and Xam
0. By
112 get
Aam
+1 80
Xam
With the convention that h)r; for any > O. and h(0; A) for any À
27

---

Published as a conference paper at ICLR 2021
If -Aam <2]1gu 12, have
In 1 d0 2Tooo
A2m
A2m
80
A2m
2|1900
60
A2m
2||so112
d0
60 -1
221..00122 ))
A2m
do
1 1 O
(1 ((6)))
2||g0 2
2|1g0|12
-X2m 22190|1a have
In(1+60) -Aam
Combining (i), (i), (iii) gives
Told;w, w. m. 0o) 2 min { In(1 + +
To
I1oolla" 122ml f
(113)
Let the initialization satisfy p(t; = p(t), and assume m > m According to Propositions C.2
and
C.3
we have
lim |llol22 = 0, lim A2m = 0 lim To W, m, 6b) = +o0.
(114)
If Po has the nau-Gausiin tail 779.. again by Propositions and C.3 we further have
To Told:w, m. 0o) 2 w wo.wn/ min
In(1 $1}
(115)
+
C3
(1 + (100l
for any E (0, (immm 20, wm..iin)) where Wpmmin == minge[m] Wo, > O, C22 C3 are
constants only related to C1, lo. and 2 hides universal constants only depending on po, la, Co. Since the initialization is bounded as (4g, wp) [ap, a.) x [wf uc] with at < a.. w/ w let cd max{[af), [a get
To(6;,, m. 0o) Z 2ze
min
In(1 + [0] Vmm"
1
(w)))
m6 (1+
+ +
2 of "f min
In(1 + 5)
(116)
v/m"
where 2 hides universal constants only related to w.. of and a..
The last task is show the dynamics of the loss is much slower than the parameter separation when there is plateauing. The argument trivial since for any T E [0, To).
Ja (0w - (06) = gd (T) 0o) + (Tw(T) 0b) Ho(Ow( - 6o) + o(82)
z -l - 0ol22 + Aam (T)(T) - 0oll3 + o(5²)
o(1)((5) + o(1)0 + o
o(5²), 0t
By continuity, the proof is completed.
Remark C.3. The estimate in Theorem C.1 shows a lower bound the escape time, hence it does not appear to preclude the situation that the plateauing lasts forever. However, in the proof above, one supposes To = +00 (04)), i.e. the hypothetical situation where the parameters are trapped
forever, and write Iu = Pgu = (90.1, -.. mm we have
[[. Ho ds
2
= = S - As ds
90
Do
(3o.s (0..)) (M(T;
A1))²
for any j such that X3- < 0. If go.s # 0, (109)
gives
[[0((T) - 00l12 2 (1 e Hos ds
+ +082)
|ãa.l ->,
ce AgT AyT - -1) + + toc, T T 00.
which is a contradiction. That is to say, the parameter separation has to achieve the gap within a finite time, even it is exponentially large.
28

---

Published as a conference paper at ICLR 2021
Remark C.A. Recall Lemina C.3
p(t: ag, we) p(t) if and only if (oo, wo) M = Up
where P is a partition over [m] as defined Definition C.I. That is, as a union of affine spaces, M is in fact an equivalent set for qualified initializations. As discussed in Remark C.2 when there
(i.e. the number of P), with each Mp an is no degeneracy, the cardinality of MM is m²! { m²
(m - m²) "mm"ddiimmiiona affine space; when there is degeneracy in some M it then becoms an uncountable set. Certainly, initializations sufficiently near M are also qualified by continuity.
Remark C.S. Motivated by the idea of weights degeneracy (see Definition C.7). can further apply similar methods to a (global) landscape analysis on the loss function Jw. The results there show that the plateaus are all over the landscape, even provided general targets (without memory structures). See details in Appendix(
C.3 NUMERICAL EXPERIMENTS
C.3.1 MOTIVATING TESTS
In this section we give details of Figure 1
(1) Learning linear functionals using linear RNNs (with GD optimizer)
The target functional is Hy (a) = -Jo p(t)ær-(dt with white noise æ, while the representation p selected as the exponential sum or the scaled Airy function:
1. Exponential sum: p(t) = [e]]T tW", where c* b' are standard normal random vectors of m dimensions, and W = -1 - z Z with Z E IR" xm" is a Gaussian random matrix with i.i.d. entries having variance 1/m*.
2. Airy function: p(t) = Ai(solt tol), where Ai(t) is the Airy function of the first kind, given by the improper integral
nn3 1 lim f cos (1² +tu du.
Ai(t)
(117)
Note that in the first example, the memory of target functional decays quickly. However, for the second example, the effective rate of decay is controlled by the parameter to. For t S to. the Airy function is oscillatory. Hence for large lo, large amount of memory is present in the target. In Figure we set m for exponential sums, and lo 3, 8g 2.25 for Airy functions.
In Figure (a) and (b), we plot the gradient descent dynamics on training the linear RNNs (dis- cretized using Euler method, hence equivalent to residual RNNs). We observe an efficient training process for the exponential sum case, while "plateauing" behaviors in the Airy function case. This causes a severe slow down of training. In addition, we also find that the plateauing effect gets worse to (or so) is increased, which corresponds to more complex Airy functions in the sense of more memory effects. That is, the long-term memory adversely affects the optimization process via gradient descent.
(2) Learning nonlinear functionals using nonlinear RNNs (with Adam optimizer)
To show that the plateauing behavior may be generic, we also consider nonlinear forced dynamical system target, the Lorenz 96 system (Lorenz) 1996):
K
1 = - + +
2k/ K,
(118)
k=1
4, = 2[zx+1 (Zt-1 - 2x+2) - 2イ v], h: k= 1, K,
with cyclic indices K = Zk. and r is an external stochastic noise. When the unresolved variables zy are unknown, the dynamics of the resolved variable y driven by æ is a nonlinear dynamical system with memory effects (but not linear functional). We use a standard nonlinear RNN (with the tanh activation) learn the sequence-tor torence-t--seqeecee mapping Zu.r Your with the Adam optimizer. Figure [ (c) shows that the training the Lorenz 96 system with the presence of memory also exhibits the plateauing phenomenon.
29

---

Published as a conference paper at ICLR 2021
1/um10
1/ue11
1/um12
19
Jn
10
10
10
10"
1o"
100
60
1/w-13
1/w-14
1/6--15
Jan
18 ln
Jn
10
Ja
10-1
10"
10
10
10 10"
1o
10
400
2000
Figure 2: The training dynamics of the target functional defined by 119 using the model (10 Here we take the width 2 in The corresponding gradient flow (21) numerically solved by the dlams-Bashforth-Mors memory becomes longer (w decreases).
method. Observe that the plateauing time increases rapidly as the
In all cases, the trained RNN model has a hidden dimension of 16 and the total length of the path is T = 6.4. The continuous-timg RNN is discretized using the Euler method with step size 0.1.
C.3.2 LONG-TERM MEMORY SIGNIFICANTLY CONTRIBUTES TO PLATEAUS
Recall the simple example of target with memory
(t-1/w)² 20
p(t) = a" ww" + cge
w > 0.
(119)
We aim learn with the exponential sum
Pm (t; a w)
03e
Rm
(120)
That is, the simplified lincar RNN model with diagonal recurrent kernel (see 76) and Ap- pendix C.I). The optimization is performed by the gradient flow (TI). i.c. continuous-time idealization of the gradient descent dynamics. The ODE (2T) is numerically solved by the Adams- Bashforth-Moulte method. The results illustrated in Figure 2 It is shown that the plateauing time increases rapidly as the memory 1/w becomes longer.
C.3.3 NUMERICAL VERIFICATIONS
(1) The timescale estimate
We first numerically verify the timescale proved in Theorem 5.1 (or Theorem C.1 That is, the
time of plateauing (and also parameter separation [[0(T) ((0) 22) is exponentially large as the
memory 1/w + +o0. The results are shown in Figure where we observe good agreement with the predicted scaling.
(2) General cases
To facilitate mathematical tractability, the analysis so far done on the restrictive cases of the di- agonal recurrent kernel W with negative entries, lincar activations and the gradient flow training dynamics. However, we show here that the plateauing behavior which we now understood as generic feature of long-term memory of the target functional and its interaction with the optimiza- tion dynamics is present even for general cases, and hence our simplified analytical setting is representative of the general situation.
In Figure 4 we still take the target functional as defined in 119). but apply more general models to learn including using full (non-diagonal) recurrent kernels of the RNN with restrictions
30

---

Published as a conference paper at ICLR 2021
Plateauing time
Parameter separation time
10
10"
Time
Time
10
10
10
14
46
18
16
18
1/w
1/w
Figure 3: The timescale of platcauing and parameter separation. Here the model and target are both selected the same as Figure 2 but with a larger width m = 10. We see the logarithm time of plateauing and parameter separation is almost linear the memory 1/w.
entries, using non-linear (tanh) activations and using the Adam optimizer. Furthermore, we do not take the Itô isometry simplification and instead use actual input sample paths of finite time horizons, just one would do in training RNNs in practice. We observe that the plateauing behavior is present in cases. Moreover, in the last case Adam (which can be thought as a momentum- based optimization method), the plateauing behavior is somewhat alleviated, although the separation of timescales is still present. This is consistent with our supplemental analysis in Appendix where show that the momentum- based methods will speed up training based our dynamical (Appendix C.2 and landscape analysis (Appendix D of plateauing.
Full Matrix (Linear, SGD)
Full Matrix (Tanh, SGD)
Full Matrix (Tanh, Adam)
10-1
10-1
10-1
10
loss
loss
loss
10-2
10-2
10-3
10-4
10000 epoch
20000
10000 epoch
20000
10000 epoch
20000
(a) White noise inputs
Full Matrix (Linear, SGD)
Full Matrix (Tanh, SGD)
Full Matrix (Tanh, Adam)
10-1
10-1
10-1
loss
lass
loss
10
10-2
10-2
10-3
epoch
epoch
epoch
(b) Cosine noise inputs
Figure 4: Numerical verifications of the plateauing behavior under general settings, with non- diagonal recurrent kernels, the non-linear activation (tanh), and the Adam (momentum-baseee op- timizer. Here we use the target functional the same as Figure 2 with the memory 1/w 20. The time horizon chosen as = 32, and 128 input samples are generated from a standard white noise. The learning rate is 1.0 for GD and 0.001 for Adam. 10 initializations are sampled and trained for each experiment. We consider two possible input distributions: a) white noise inputs; b) inputs of the form H, = Σ/=1 1 ay cos(A)!), where AÚ ~ U(0, 10) and aj ~ NN(0, 1). We observe that plateaus occur in all cases and the momentum generally improves the situation but still not resolve the difficulty.
31

---

Published as a conference paper at ICLR 2021
D LANDSCAPE ANALYSIS
As mentioned in Remark C.5 we can perform a global landscape analysis on the loss function based on the idea of weights degeneracy, which arises from Definition C.I Recall that the loss function reads
2
m
age wid a(1) _ di
min Jm (a, w)
Σ
(121)
AER" WER
The main results of the appendix summarized as follows.
In Theorem D.
we prove that the loss function has infinitely many critical points, which form factorial number of affine spaces;
we prove that such (critical) affine spaces are much more than global minimizers provided the target being an exponential sum:
In Theorem D.2
In Theorem D.3
prove that such (critical) affine spaces, the Hessian is singular in the sense of processing multiple zero eigenvalues;
In Proposition D.1 we prove that the (critical) affine spaces contain both saddles and de- generate stable points which are not global optimal.
Instead of local dynamical analysis in Appendix C.2 we generalize similar methods global landscape analysis here, and the results hold for the loss function associated with general targets. More specifically, these results complement our main results (see Theorem 5.1 or Theorem in the following aspects.
It is shown that the weights degeneracy is quite common in the whole landscape of the loss function. Unfortunately, the weights degeneracy often worsens the landscape to a large extent:
It is shown that the weights degeneracy leads to large number of stable areas (i.e. critical affine spaces), but most them contribute to non-global minimizers;
It is shown that these stable areas can also be quite flat, which often connect with local plateaus;
For the structure of these stable areas, there are both saddles and degenerate critical points (not global optimal). In certain regimes, even saddles can be rather difficult to escape from (see Theorem 5.1 or Theorem C.I..
As consequence, the optimization problem of linear RNNs is globally and essentially difficult to solve.
D. SYMMETRY ANALYSIS ON THE LANDSCAPE
This subsection consists of two parts: in Appendix D.I.I
give main results provided the
istence of weights degeneracy; in Appendix D.1.2 we give sufficient conditions to guarantee the existence. Since the key observation to utilize weights degeneracy is to notice the permutation sym- metry of coordinates of gradients, we also called "symmetry analysis".
D.1.1 GENERIC THEORY
We begin with the following definition, which describes the concept of weights degeneracy in natural and rigorous way.
Definition D.I. (coincided critical solutions and affine spaces) Let d E N.. and d m. We say (a, w) is d-coincided critical solution of Jm. if Jm,(a w) = O, and w = (w;) E RT has different components. The coincided critical affine spaces are defined as coincided critical solutions that form affine spaces.
9hhe global minimizers are distinct when the target is an exponential sum. Here we compare the number of (critical) affine spaces with the number of global minimizers (both of them are finite). When the target is not an exponential sum, the same conclusion holds if there are still finite number of global minimizers. See Remark D33 in Appendix D.I.T for details.
32

---

Published as a conference paper at ICLR 2021
To guarantee the existence of such solutions, it is necessary to have the following definition.
Definition D.2. (ā, ib) E I & R4 is called the non-degenerate global minimizer of Jm if and only if
Jm a)
inf (n, w),
(122)
aER"",
and (a, u) takes non-degenerate form
ā + 0, w; + w for i i 4 = 1,2,...,
(123)
For convenience, we also define an index set
N = {n E NN+ : Jm has non - degenerate global minimizers for any m S n): which is used frequently in the following analysis. For any f E 1,2 oo), let L[ be the Laplace transform of i.e. [s) = So ft)dt, O. We begin with the following lemma.
(124)
Lemma D.1. Assume that p is smooth and vw [w)) 0 have 1 E N and thus N + Ø.
0+ and
Then
Proof. We aim to show that there exists # and > 0, such that
(á ú)
inf aER we
J1 w1
(125)
The basic idea is to limit the unbounded domain a E R w E R4, to a compact set without effecting the minimization of Ji (1(a, w). We have
min Ja w/ = min min 0,033
a- (c[](w) a 11.112210.000
w>0
2w
min min
(a 2wl(r((we) + |10112000.00= - 220((()((())
w>0
a
2w
min w>0
{IeelB2 2w (c((((((w)) = (1(a(w),,)
where a(w) = (ww. Write h(w) = J1(a(w), w), then 1(00)) = 1((00) = -|P112210.000
Obviously h(w) II for any w hence
min h(w) w>0
min wel
h(w), wib < wab 00,
which implics
min J1 w) min JI JI(a(w), a.w20
min (1(a(w,, w).
#>0
we wE(ers (u.)
That is say, the minimization of Ji (a w) can be equivalently performed a 2-dimensional smooth curve (w, ((w))) which is certainly compact set. By continuity, J1(a, w) has global minimiz- ers, say (à, v.) Obviously á > 0 and à a(w) # (since implies (ā w) | certainly not a minimum), which completes the proof.
Remark D.1. If the target is exponential sum, i.e. p(t) = Ex=ra a3e- -33 know is smooth and v [[)) > as w 0+ and w > too; hence E N by Lemma D.1 and thus N Ø. In fact, (w) EØ= w+wy implies that [(p((w) O(1) when 0+, and (w) = O(L/w) when +00.
af
Theorem D.1. Assume that N + Ø with N defined as (124). m,d N4, 1 < d 5 min(m, 3, there exists least d! m
Let M = sup N. Then for any d-coincided critical affine spaces
of J Jm where {m] d E N4 is called the Stirling number of the second kind.
10 affine spaces degenerate to distinct points when d = For sufficient conditions to guarantee M (to avoid vacuous results), Theorem and Remark D.7 in Appendix D.1.2
33

---

Published as a conference paper at ICLR 2021
Proof. (i) Existence. The key observation is the permutation symmetry of V.m by (19 if a; aj
and ui Wj for some i # j. then 0Jm 0Jm and Da.
0Jm
8.m
3aj
Ow;
Bw:
For any m, E N4. _ I m, suppose that w = (wt) E RT has different components. Then
for any partition P: {1,-.. m) = Uر= with I n 2 = Ø for any ji + ja. J1, 1, d. define the affine space
(p..b.o)) = (a, w) ERT @ R4 ut Uy for any i E Ij
Σ aa = bj. j= 1, d KE
for some (b, v) E IR @R. where e has exactly d different components. Therefore, for any (a, w) E (p,(b,)) we have
Im(a, w)
Σ jml TET,
agc wif
p(t)
Σ b,e Ust - p(t)
= Ja(b, v),
12(0,00)
[2(00,00)
and similarly
JJm (a, w) = J e vut
d
Σ j=1
bee b, /
-d()) p(t)
de, h E s s=1,2,...,
0ak
JJm (a, w) 20k
1 0c
d Σ 0,--00 p(t) -p(t)
(-t)e-ud
di, k Ix, 8 1,2,....
Owk
jo
Notice that
x AJa (b, v) =
d
6 -vs
Σ bye 5 -p()) de, 8= 1=,,,.....
0b,
5=1
ØJa (b, v) = 2b,
{ 0
Jo
(-1)e-ns
Σ bs - pl()) dl, 8= 1,2,,....
Dvs
we have
JJm
AJa (b, v),
AJa (b, KE I,: = 1,2,.... ,, (126) aJm (a, w) = as Ov.
(a,w) = ab. dap
by Owk
Since d < min(m, M). E N. In fact, for any A N4. if k NN, there exists i < such that J(s) has no non-degenerate global minimizers, we have j & N for any j 2 i, hence M 1 k 1. Henee M implies N = N+ and M oc implies M E N. and both of them lead to E M. Therefore, Ja has non-degenerate global minimizers, i.c. there exists (b, 0) E Rd @ R4d such that
Ja(b,0) inf Ja(b, v),
(127)
heRd, and (6, 8) takes a non-degenerate form
b, + 0, 6, + úg for any + j, i.j 1.2
(128)
By 127 we get (., 6) = O. Combining with 126 and 128). we obtain V (a, w) = 0 for any (ā, w) (M.66.)). i.e. (ā, w)) belongs to d-coineided critical affine space. Note that
the affine space is with the dimension Σ (|Z,) - 1) = m d, since there are d linear equality constrains on the m-diimensional vector
By considering the gradient flow dynamic of Ja instead of Jm. model reduction (from m-dimensional to d- d-dimensional) is almost completed on M MP. (mm.)))) except for some trivial degenerate cases (e.g. as b. 0).
34

---

Published as a conference paper at ICLR 2021
(ii) Counting. By the structure of affine spaces discussed above, identify different affine spaces with respect to the partition P. For counting the number of different partitions P: f ) Z.. it can be decomposed into the following two steps. First, partitioning set of m labelled objects into d nonempty unlabelled subsets. By definition, the answer is the Stir-
m d S.
ling number of the second kind
Second, assign each partition to I,, II accordingly.
There are d! ways in total. Therefore, the number of d-coincided critical affine spaces is at least
d! m The proof is completed.
Combining Lemma D.1 Remark D.1 and Theorem D.I gives the following theorem, which states that there are much more saddles and degenerate stable points which are not global optimal than global minimizers in the landscape (provided the target being an exponential sum).
Theorem D.2. Fix any m E N relatively large. Consider the loss Jm associated with the target being a non-degenerate exponential sum, i.e. p(t) mm aze-"3', where az o O and wi o w for any i * i,j 1.... m.. Assume that m E N with N defined in 124 Then in the landscape of Jm. the number of coincided critical affine spaces is at least (oly(m) times larger than the number of global minimizers.
Proof. (i) Global minimizers. Since the target is an exponential sum, we have (m, w) 2 0 and Jm (a", w²) = O, where ä* = Pu" and wi = Pw" with P E mmx to be some permutation matrix. Next we show Jm has no other global minimizers.
Suppose Jm (a, w) O, we have
Σ 2m
age
Σ
aje C5e
t t O.
(129)
It is easy to that for any j
m, there exists i(j) such that Wa()) w.. Otherwise, 83 or Lemma C.2 we have 0j = 0, which is a contradiction. different w;'s hence the
Wi * wj. i = 1, ......... m, by Notice that w j w for any 7 j. different Wr s will correspond correspondence is one-to-one. Therefore, let wi = = (00- 112 can be rewritten as
0
Σ L0se Sa0e Σ (as (50))e S00 120.
Again by Lemma C.2 we have O; Say That is to say, Jm (a, w) = 0 implies a = Pa and Pw" with P mxm be some permutation matrix. This gives ml global minimizers.
(ii) Coincided critical affine spaces. Obviously N * Ø, and M sup N 2 m. According to m { [d}
Theorem D.1 for any N4, < d S min(m, M] = m, we have least d! d-coincided
critical afhine spaces of Jm. By (i), for any d S 1, there are global minimizers in these affine spaces. Counting the total number
m
m
(130)
(iii) Comparison. To give bound between
130
and ml, we need an elementary recurrence
{
m
= m
m
d
For d = m - 1, let Pm
=
m
then
m
Pm (m
1) m m 1 m
m
1 (m 1) + Pm- =.. m(m -
2
Although the assumption A seems strong, we will provide sufficient conditions to guarantee its validity in Appendix D.1.2 See complement in Theorem D.7
35

---

Published as a conference paper at ICLR 2021
For d = m - -2, 2 let 4m
m
then
m 2
9m (m - 2)
m
+
m 1
m 3 (m 22)mmm1 + 9m
m7
2
24 2m - 2m - 1)(2m 3) + 3(m - 2)²(m - 1)
Combining above gives
1 m!!
m
d!
m
1 [m 1)ppm + (m 2)1 (m 1)(mm 2))
d
m!!
24
which is a quadratic polynominal on m. The proof completed.
Remark D.2. We only take the last two terms of (30) for lower bound, which obviously ruther loose. In principle, Poly(m) bound with higher degrees can be similarly obtained. That is to say, on one hand, there are infinitely many critical points forming affine spaces in the landscape of Jmi on the other hand, see that even if only counting the number of affine spaces, there are still much less global minimizers (provided the width m relatively large).
Remark D.3. When the target p is not exponential sum, it is straightforward to see Theorem D.2 still holds if there is a finite number (with the scale of no more than factorial) of global minimizers.
Now get down investigate J the above coincided critical affine spaces. Is shown that 2 Jm is singular and can have multiple zero eigenvalues.
Theorem D.3. Fix any m, E N4. < d m. On the d-coincided critical affine spaces (induced by non-degent noggeeeeeee global minimizers of J. of Jm. 2 is with rank at most m + d, and hence has at least m zero eigenvalues.
Proof. A straightforward computation shows that, for k, = 1,2, ....,, m.
Jm daz
2
(a, w)
(131)
Wkk + wi
02 Jm (a, w) da,
-2at
k #
(132)
(wks + w2)2
8 Jm Oazdwk Let the induced d-coincided critical affine space be MM (m))))))m as is derived in the proof of
m
(a, w) 2wk
+ 2
[ (-t)e- wht
Σ
ae aeet p(t) dt.
(133)
Theorem
D.1 Since (b, (i) is the non-degenerate global minimizer of Jd, we have
1
(-1)e- -mue Σ age Whst - vl)) dl = [00 (-1)e- net
bi Bstt p(() di
1=1
1 OJa (6, 0) = 0,
k E I,, & = 1,2,
2b, 0y,
for any (ā, MM, (p,(6.0),(m.d) This gives
@
(ā, w)
(134)
Dag Owr
200 K
Now we show that, for any i,j E I,, + j. s = 1.2, ... ,d, 2 (â, (): = 2 (á, 2 w In
fact, for any = 1,... m, let I,r, then by (131
Jm
2
2
82 Jm
2
2
(ā, () w; 0h
(a, (0) =
0a,0az
0, 02
Da,0a
w;
+ wk
0, +
1haa is, the affine space Mp.bb.)). See details in the proof of Theorem
D.I
36

---

Published as a conference paper at ICLR 2021
For # and &o # j. (132) gives
8
2ûk
22
@
-2ū
-2ūx
(a, ()) = (w:; + x2
(a, () = (wx + 2b²)²
da,0wk
(Ús + )gr
da
(0s + 0₂² )2
By 134). for lo = i i J.
0 Jm
-ù
-ù,
8 Jm da,Own
-20;
-à,
Su,0wu
(a, (6)
200
=
26
(ā, (0) = (10 + ú;)²
26
and similarly for iii i
@m
2ūg
-ūg
8 Jm (ā, u) = - =
-ūj
(á, ú)) = (1ù; + w; 203 oa,
da,Uw;
2 20
That is to say, there at most + d different in the symmetric matrix Jm it) R2mx2m hence rank ( (m (ā, a)) I + d. Therefore, the number of zero eigenvalues of V (6) 2 dim{fr (3r R22m V ()) 0} 2m rank ui) 2 d. The proof is completed.
L
Remark D.4. The bound in Theorem D.3 is not sharp, since the estimate on rank (v²Jm) here is loose only rows with the same elements considered. In practice (numerical tests), it is often observed that there are more zero eigenvalues of rarkk(22 Jm) on the coincided critical affine space (p,..0)
Remark D.5. Theorem D.3 shows that, there are local plateaus around the d-coincided critical affine spaces Mp, (6, (6.6)) (m..d) for d S m - 1. In addition, the O-eigenspace of Jm is higher- dimensional for smaller d, which may suggest that can stuck on plateaus more easily.
D.1.2 SUFFICIENT CONDITIONS
There is still a gap when connecting Theorem D.1 and Theorem D.2 That is. it is necessary to guarantee sup N relatively large, i.e. J1, J2.
all have non-degenerate global minimizers for d as large possible. Motivated by [Kamller (1779)) we can give some sufficient conditions by limiting the target p within smaller function space, the so-called completely monotonic functions. Definition D.3. F C(0, oo] C C00 (0) is called completely monotonic, if and only if
(-1)" 0. oct< = 0,1,
and Foc))=
Remark D.6. Several examples of completely monotonic functions:
p(t) 111111111111 t) for any a > 0;
The non non-degenerate exponential sum with positive coefficients
m Σ 1=1
p(t)
aae W33
S wi < < w 0z > >0 1,2,
Since the space of exponential sums approximation to a given / E T.2(0. 0, oo) from the set
close, we turn to consider the problem of finding best
Va(R.)) = (p E Cd 00, x) : [(D + wi) ... (D + wa)lp = 0 for some w1, .......... Wa E IR+ (135)
with respect to the common L norm, i.c. inf (EV,( | pll 22). where D denotes the common differential operator. Obviously (R( c [ oo) and (R, E Va+1 for any d E N4.
Kammler (199a)) proves the following theorem.
Theorem D.4. Assume E [2, oo) to be completely monotonic. Then there exists a best approx- imation 1o to p in V (R.),, i.e.
||p0 pl12210,00)
inf peVa(R.)
|1l pll2310.00)-
(136)
37

---

Published as a conference paper at ICLR 2021
When & Va(IR+), any such best approximation admits non-degenerate form
(t) = Ebee
bje est 0 0< < <dd, by > j 1,2, dd.
(137)
and satisfies the generalized Aigrain- Wiltii-m equations (t,) L(p((;)),
1,
(138)
ds -179(()) =ūي ds ( ==ā=" j j=1,2,.. ,d.
d
(139)
Note that (366) and (37 are pretty similar to Definition D.2 except for a different choice of hy- pothesis function space. Now show connection between these two problems.
Theorem D.5. Assume E 1,2 oo) to be completely monotonic, and p Va(R+) for some
E N. Then Ja has non-degenerate global minimizers (b,0) 6) Rd R4.
Proof. According to Theorem Va (R,,, i.e.
D.4 there exists non-degenerate best approximation go to p from
11p0 p111210,00)
inf (EVa(R4)
110 - p112310,00),
(140)
(1) Σ b Ast
01 <....... Dd. by > 0, j == 112, d.
(141)
j=1
We aim to prove Ja(b, 0) = inf HERd
Ja(b, v). Define the following subsets exponential sums
Va(R+)= = p: p:)(1) = Σ
oge a wit E RR wi > 20}
1=1
(R+) = 0 E Vo(R+) w = (wi) has is different components
1 k < d,
then we have
inf bERd, DERd
Ja(b, v)
inf |lp P112210.c0)- It is straightforward to verify that (EVa(R()
Va(R+) = U (a,x(H+),, and (R+( VA & (R( for ..... d. By 140
get
1100 pll::10.00 pEVa(24)
inf || - Pllii20,00) I inf ||I - pll:zp,00) alVa)
Since 90 (R, we have
Ja(b, 6) = -1000 -1112400.00) = inf ||0 - plliat0.cc)> (EVa,a(R,)
The last task to show
inf || pl11210,00) = inf 110 pl11210,00) In fact, for any (EVa,((4+)
)
T E Vk.ks p(t) D Σi=1 are wit let ă (a),... az O),0), i = (w1, wk; maxigigs w:), we get p(t) = Etel ā,e कHtt E V4+1 which implies VA. C VA+IA+I. Therefore,
{ inf 11 e pll2310.00) isksd (REVE,)(R)
||ø pll 211 DeUL inf (EVa(R,)
inf
|lø pl12310,00)
min
(R.)
inf Igkšd (AEVeL)R
min
110 oIllaTU.0)] inf AeVa,s(R,)
-1Ø- - pl p1(2210,00)
which completes the proof.
Combining Theorem D.I
and and Theorem D.5 immediately gives the following result.
38

---

Published as a conference paper at ICLR 2021
Theorem D.6. Assume p (2) to be completely monotonic, and p (R()). Let D E : V,( Do == sup D and write m' = -mn(mm, Du}. Then the total number of coincided critical affine spaces of Jm at least E
m
Proof. We have 1 E D and thus D + 2, Do 2 1. Since Va(R+) Vd+
RR+) for any d E N Both of them gives
we have D = (1.2.... Dot if Do < oc, and D = N+ if Do (1,2. ,m'} C D, i.e. p E V (T)+) for any k m'. By Theorem D.5
00
has non-degenerate
global minimizers for any S m', ie. m' E N. According to Theorem D.1 for any d N++
1 d m' = min(m, m'} mm, M), there exists at least d! {
m
d d-coincided critical affine
spaces of Jm. Sum over d gives the total number E d! [m]
{d)-
Remark D.7. Examples:
Suppose the target is p(t) 1/(1+)) then D - and Do oc. The total num- ber of coincided critical affine spaces of the corresponding Jm is at least Ei= d! m
Suppose the target is an non-degenerate exponential sum with positive coefficients: p(t) = Σ/= 1z=aaee azj-";; where a; > and w # w for any i + J. i,j = 1, .... m. Then D = [1,2, ,m 1} and Do = m 1. The total number of coincided critical affine spaces of the corresponding Jm is at least Exn d! d
m
which is exactly ( (100).
An complement for Theorem D.2 is as follows.
Theorem D.7. Fix any m E N4 relatively large. Consider the loss Jm associated with the target being a non-degenerate exponential sum with positive coefficients, Lee. p(t) = Σj= a where a; > and / + w for any + j. i,j = -..... , ,m. Then in the landscape of Jms the number of coincided critical affine spaces is at least Poly(m) times larger than the number of global minimizers.
we only need to show is m E N. Since E I oo) is completely monotonie, and p (R for any & I 1, then by Theorem D.5 J(a) has non-degenerate global minimizers for any S m - 1, i.e. m - 1 E N. The proof is completed by noticing that Jm obviously has non-degenerate global minimizers, e.g. (a", w*).
Proof. By Theorem D.2
D.1.3 A LOW-DIMENSIONAL EXAMPLE
To further understand the structure of coincided critical affine spaces, we focus specific low- dimensional example here. That is
2 Σ
min aER? WERR?
Jz(a, w)
age wist p(1)
L2(0,00)
with the target to be a non-degenerate exponential sum p(t) = Σド aze-wie where az * 0 and w f wy for any * j. i,j = l,.... ,m" As we will show later, the coincided critical affine spaces of J2 contain both saddles and degenerate stable points which are not global optimal.
By Lemma D.I Remark D.I and Theorem D.I we know the 1-coincided critical affine space of Jn exists, and it can be constructed by taking the non-degenerate global minimizer of J1, say (ō, 1)
"In fact, Va(R+) Va+1(R+) for any d E N4 implies if Va(R+), É V&(R+) for any k < d, i.c. d E D & D for any & E d; otherwise, if p Va(R.), p E Vi(R.) for any 2 d, í.c. d E D + 1 D for any 1
39

---

Published as a conference paper at ICLR 2021
with à # 0 and ④ > 0. Then (aa.)).(2.1) = {(a1, d1, ū, u) d1 E R. E IR is line and Ja2 â a1, w, vi) for any 4 E R. Denote the Hessian of J2 on the line ()..)).12.1 by A(a.e) (a1), i.e. a(a (a1) = (21, â ai U1 d). We investigate the landscape of J2 on the line ((.1)) by analyzing the eigenvalue distribution of (aa,))()))
Proposition D.I. Suppose m = m 2, and < w wT. Let I = [0, a] and 12 = U) (á, +00
16 Then
1. If a2 < 0, the minimal eigenvalue of A(a,a) (a1) is 0 for any as E IT, and negative for any a1 Iz;
2. If aj 0 > 0 and w2/ / /w] < 2+ v3, the minimal eigenvalue of o(a is negative for any a1 IT and 0 for any on 12.
Proof. Write c(w) = Σド=ı 0z
and 02 = à - a1 A straightforward
2w(w+w3)
(wtwp))
computation shows that
2u
2
((a,))(a1)
2
2
+ 4c(w)
01
2:
216
2
2
2
0102
a2 2d
4c(w)
216
2
Considering the congruent transformation of A(a, (a1), which does not affect the index of inertia:
-01
T
2
2
A(a, =
17
o 2
+
4c (W)
2w
20
2
d2
4c(0)a2
2
2w
2
0
0
2
+
4c(10
(
4nd
see that (ai) has one positive eigenvalue 1/16 and one eigenvalue 0. What remains are the eigenvalues of A A(a,0)(0)) (a1)
af
+ 4c(
(1)
a102 110
To determine their signs,
4c(w)a22
compute
det det(Ala = a (a- a.) 4c(10)
à
+ 4c(10)
(142)
4203
i an (ā a1) ac(wi) (a² + 16 (c(())
(143)
So we need to analyze the sign of àc( and a² + 16m 16 under different assumptions on (a", w
(i) ajja < O. By the optimality condition of (á, w) for J1, we have
m
aj
à 20
4
(144)
11 + w
( + w2
j=1
and therefore
m
à
((w)
S
④ + w 3
15 Here we omit the corresponding partition since unique.
"Suppose à 0 here without loss of generality. If < 0, we let T [á, 0 and Ta (-oo, a) (), +20) and the conclusions hold.
40

---

Published as a conference paper at ICLR 2021
Write Uy == w// w0//0, j 1, we get 0 <
v1
U2 and
m
á
m
= ==1
c
Σ
1 1+ Dj
+ U3 )z
8
(1
U3 )3
j=1
Therefore
aj
810 8 ac(w)) = à²
8á
(1 U/
)
j=1
2
4j
16
16
0/)²
Uj
01)
==1
15 02)
(145)
(1 + 01 (1 + 02)
> 0,
which gives àc(()) > and a² + 16 16 > Sc)()((1))) > 0.
(ii) aa > 0, w wt + v3. By 145 àc(w))
a² 16w ac( -38²
16ā
(1 + 13)3
j=1
2
m"
a
2 m
m
aj
16
3
(1 + 02)2
1 +
(L 0g) )3
j=1
j=1
j=1
0
112 + (2 + Geuunz
20
2c
up:=y:=1 1/=
(8 + 6 + 6cs² - -css - 2cs²) (8 u2uu// > 1)
"
4 2
[62 22s(s - 38 + 1)c + 541
u2
Since (s² 38 1)a 4s = (s - 1) - 2) - 3], and < 5 = u2/u1 = (w + w
(w +
wf) < wt / < 2 + v3, we get A. < 0. This implics d² 2s(22 - 3s + 1)c + s and
à² 16w ac ()) 0.
In both (i) and (ii), â² + 16x0)a((w)) > O, which implies that there is at least one positive diag- onal element of aa) (a1) in a sufficiently small neighborhood of a 0 and 01 â. By the Rayleigh-Ritz Theorem and Weyl's Theorem, A(a,a) (01) has at least one positive eigenvalue in this neighborhood. However, by 142). det(A4 (a,)) (a1)) (a1)) only changes the sign at a₁ and 01 à. This implies another eigenvalue of A(a.an) (a1) changes the sign at a₁ 0 and a1 à accordingly. By different signs of âc(ū)) derived in (i) and (ii), and (12). the proof is completed.
that there are both saddles and degenerate stable points of J2 on the critical affine spaces (line) ((a.a))(2.1),, and each of them in fact forms affine spaces (lines) respectively, but they are certainly not global minimizers. Therefore, the gradient- based algorithums can get stuck around this affine space, except that it meets saddles with negative eigenvalues of large magnitude.
Remark D.8. From Proposition D.
E MOMENTUM HELPS TRAINING: QUADRATIC EXAMPLES
In practice, it is often the case that training is trapped in some very flat regions (plateaus), where the loss function has rather small gradients and negative eigenvalues of Hessian. Now we illustrate the escape dynamics (from plateaus) via a simple quadratic example.
41

---

Published as a conference paper at ICLR 2021
Consider the loss function f(x) = {=} e2
2 with 0 < c < 1. We check the escaping per- formance for continuous- in-time analogs of two optimization algorithms: gradient decent (GD) and momentum (heavy ball) method.
(1) Gradient decent
Consider the gradient flow of f(x) with an initial value zu (6, 1) where < 8 = O(c). Thus [ = O(c), and
< 1 and
2 =x)) (0) = = { (T( de
2 (T) (T) -1 (0) = 8
x2((7) = e f(((T) (62e-2r - -e2tr)/2 (1(T).
It is easy show that there different timescales of (1)). In fact, when T 0(1/o), l(()) ((e2)e-10(/0) - co(o()) O(c). However, when 7 continuous to increase, say
1 du In
=
(146)
2c
c
where do > 0 denotes the gap satisfying
o(o)), we get ((() S li(t)) 0(2)
ce Au /2 - 0 - 5n/2 2 < 6 for any r 2 7ं.
(2) Momentum
The momentum algorithm has the update rule
Øb+1 = 2g - f(xx) + p(xx xx-1),
(147)
where p E R. 1) > is the learning rate. The continuous-in-time analog can be derived as (similar
to the arguments in Su et al. (2014)
0=p 1k+1
2x + Fk-1 + (1 (1- Tx+1 Ik
+ (z(x))
7
Vi V1
(1 (1- x')) - vf(((t),
~ pz" (t) +
with zg == = and the step size v of the simple finite differences
Let æ zo =
we also get x (0) (()))
To facilitate comparison to GD, we take 1) 1 18 and can solve the ODE
Plugging the expression of f, we
(T( + x (T) 0, (T) - ET2(TT = 0,
3 (0)
x0) -
z((t) (z)((t) +
(2 = 1,
{
(1 = 5(coST sin T)
x2(T) L+VE eVEr 1-ve Ver
2
f(x(T)) 2
1
82 8²(COOT= sin sinT)² ( -E
(e ever + (1+
1- Ve
-ver
ver
27
2
Write (2(() = f(x(T)). It is not hard to show that there are still different timescales of (2(T). In
fact, when 7 = O(1/ (2(T) = =(E))(((1) - (e)(1))(e)0(I) +e - 10(01)2 = O(e). However, when 7 continuous to increase, say
480 2 In
(148)
2 E
we get (2(T5) = 0 e( 2
Atyeyyeee 2 /2 O(e) O(e) 80 <-00/2 hence (2(T) <
(cc) 5o 00 for any 7 2 Tz.
Combining (1) and (2), we have the following conclusions.
IIt is easy check that the emror of discretization is of order (( In the continuonsiin-iime analog of GD, i.e. the gradient flow, the step size is taken as 1. As seen later, p not only simplifies the analysis, but also helps obtain the hest acceleration.
42

---

Published as a conference paper at ICLR 2021
For both training dynamics, there are different timescales in the loss function. That is to say, relatively long time is needed to escape from the plateaus;
Comparing (146) and 148), we get different timescales of escaping: ( In(1/e)) for GD and O (1/Ve In [7+)) for momentum. Just like the convex case, where momentum improves the convergence rate by weakening the dependence on condition number, we see momentum can also help to escape rather flat saddles.
43


Reviews:
[{"review_id": "qrkAfPFiAa0", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies approximation and optimization of linear RNNs for learning linear functions, from the perspective of the memory-properties of the temporal sequence. It shows that linear functionals can be approximated by a linear RNN, with the rate of approximation depending on the long-term memory of the process.  It also shows that the training dynamics slow down for certain linear functionals with long-term memory. \n\nStrengths:\n\n1. The problem being studied in the paper is interesting and well-motivated. Capturing long-term memory is one of the major challenges for sequential models such as RNNs, and the paper makes progress towards understanding this.\n2. The functional view of the process is interesting, and seems to shed light on interesting phenomenon regarding memory. The paper also brings in rich tools from functional analysis for analyzing RNNs, which could perhaps be more broadly useful if they can be made accessible enough.\n\nWeaknesses:\n\n1. I think the paper needs to be significantly rewritten for the ML audience to extract much out of it. Most of the ML community will not be familiar with the tools and terminology here, including classical results from representation theory such as the Riesz-Markov-Kakutani theorem. Providing more intuition and context for these results will be very helpful. For instance, it would be good to provide some intuition for the \\rho(t) function. Once this is introduced, the authors use it interchangeably in place of H_t for describing all their subsequent examples, but it would be better to provide some intuition for the examples directly. The underlying phenomenon are simple and elegant, and I think they can be explained effectively to the ML community.\n2. As far as the main message of the paper regarding memory goes, I think it is interesting, but I am not sure if all the machinery is necessary for showing this result? For instance, for a linear functional which does not decay fast enough on the constant input (such as in the conditions of Thm 4.2), would it not be possible to show that it cannot be approximated using a small number of neurons even in the discrete case? The reason being that the process “remembers” inputs over exponentially long windows, and hence you need an exponential number of units to approximate it (at least with linear activations)? Can the authors shed light on the power of the continuous time view and representation theory for showing this?\n3. The optimization result seems a bit tailored to a particular functional. I think if the authors could explain more generally why the optimization is getting stuck at a plateau, even at an intuitive level, then that would be useful. I’m also curious about the same question as before, is it not possible to construct a specific worst case function even in the discrete case?\n\nOverall, I think there are some nice ideas and tools here, but am not sure if the ML community will get a lot out of this currently.\n\nSome more comments:\n\n1. Please define/describe the airy function.\n2. Typo above Eq (21), We->we.\n3. Typo above conclusion, exponentially->exponential.\n4. Theorem 4.2, y_i^(k)(t) with the superscript (k) does not appear to be defined?\n5. Please clearly define what inputs and outputs are at the beginning of Section, for example x is input, y is output, h is not observed.\n\n------Updates after response------\n\nI thank the authors for the detailed response and the revision. I am still not completely convinced regarding the suitability for ICLR and have similar concerns to reviewer 2, but am not opposed to acceptance.  In light of this, I have increased my score to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gxHDxza6sxS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides a theoretical examination of the challenge of fitting recurrent neural networks (RNNs) to fit processes with long memory (or long-range dependence). Dubbed the “curse of memory”, the author(s) restrict to the case of linear activation functions, and show that for processes with increased spatial dependence: (a) the width of the layers must increase exponentially to _guarantee_ accurate approximations under a provided bound, and (b) a gradient-based optimization algorithm will take exponentially more time to converge. Sufficient details for reproducing the experiments are provided. \n\nI like the paper and believe the contributions to be both substantive and of wide interest in the RNN community. The analysis presented here is rigorous and comprehensive, and while the discussion is limited to linear RNNs, it provides a good starting point for further studies regarding long-range dependence with RNNs. The paper is reasonably well-written, and aside from a few minor typos — see the minor comments below — I did not encounter any serious errors. I do have some criticisms, however:\n\n1. Perhaps my biggest disappointment is that while the authors do a good summary of the relevant RNN literature, they have failed to mention any analogous ideas from the time series literature. For example, any discussion regarding Hurst parameters would be welcome, since this is precisely the type of “long-range dependence” discussed here. The lack of references to this literature is disheartening, since these concepts have played a key role in time series analysis for many decades, and it would have been nice to see this acknowledged, or a connection made. \n2. The takeaway from Theorem 4.2 regarding the exponential increase in the required width for fitting a linear RNN is nice, but is undercut by the fact that Theorem 4.2 is an upper bound. I'm satisfied with the result, but a lower bound for approximating a particular functional would be more convincing.\n3. I was disappointed with the “informal” presentation here. I can appreciate the attempt to simplify the full statement, but I still had to go to the supplementary material to understand the statement, which I should hope most readers would not have to do. I think a more precise statement than “trapped in a plateau with timescale” would be better. Perhaps something involving the hitting time, or even more simply, $||\\theta'(t)|| = O(...)$ as $\\omega \\to 0^+$ for sufficiently large $t$?\n\nIt is also worth noting that there is an extraordinary amount of supplementary material here, much of which, unfortunately, does not get the attention it probably deserves in this format. There are aspects of the paper, including the precise statement of Theorem 5.1 and the definition of the Airy target, that require the reader to visit this material. The proofs of Theorems 4.1 and 4.2 seem fine to me. Unfortunately, the proof of Theorem 5.1 is especially lengthy, so I did not get the opportunity to check each step in detail. However, the general argument appears sound.\n\nOverall, I am impressed with this paper and enjoyed reading it. The missing connections to classical ideas in time series analysis are unfortunate, and I would be willing to give the paper an 8 with a wider literature review and improved presentation of Theorem 5.1. An additional lower bound for Theorem 4.2 would bring it to a 9 at least. But, even in its current form, I recommend this paper for acceptance to ICLR. \n\nOther comments:\n- I believe Theorem 4.1 also follows from the fact that matrix exponential distributions are dense (see [1]), together with the Riesz-Markov-Kakutani representation theorem used here.\n- “We first show that the training dynamics of $\\mathbb{E}_x J_m$ exhibits very interesting behaviors depending on the form of target functionals.” — This is a little too vague, maybe consider rewording?\n- In multiple places: “x being/is the white noise” -> “white noise x” or “x is white noise”.\n- Check capitalization in the statement under Theorem A.1.\n- “Airy” should be capitalized in each appearance.\n\n[1] He, Qi-Ming, and Hanqin Zhang. \"On matrix exponential distributions.\" Advances in Applied Probability 39.1 (2007): 271-292.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8xPwoWu541w", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper reports a mathematical study of approximation properties of linear RNNs. The first part  reports a universal approximation theorem, and presents an analysis of how efficient the approximation is. In particular, it is shown that approximating a slowly decaying, power-law temporal filter requires a large number of neurons, a property the authors refer to as the \"curse of memory\".\n The second part of the paper examines the dynamics of learning under gradient descent, and gives arguments related to the existence of long plateaus seen in the loss as function of training epochs.\n\nThe paper is written in a formal mathematical style (Definitions/Theorems). Not being a mathematician, I am not able to assess the formal correctness of the proofs, and I have found some parts not easily accessible. Most importantly, as currently presented the main results seem to be of limited interest to the ICLR community (see below for details). The paper as a whole is probably more appropriate for a more mathematical venue, where the novelty of the proofs may be better appreciated.\n\nStrengths:\n- attempts to put on a rigorous footing various experimental observations on RNN training\n- possibly novel mathematical derivations of approximation results\n\n\nConcerns:\n- the novelty of the results presented in the first part is limited. Previous works have reported various universal approximation theorems for RNNs. Several classical works on that topic are not mentioned, eg Doya 1993, or Maass 2007. The details of the mathematical derivation may well be novel, but I am not able to judge this aspect.\n- the fact that a diverging number of exponentials are needed to approximate a power-law function is also well known; from that perspective the \"curse of memory\" is not very surprising.\n- I found it difficult to extract key results from the second part on Optimization dynamics. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "4RAjI66dKLX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main contributions of the paper are the following ones (informal):\n 1. The approximation theorem of linear functionals with linear RNNs in continuous time settings. The main difference with the previous results is that the class of approximated functions is linear, but does not necessarily come from the same differential equation that describes the class of approximator models.\n 2. The upper bound on the approximation error for some \"exponentially decaying\" linear functionals, where the upper bound depends on the weights matrix size (i.e. memory size). The memory growth rate is polynomial with respect to approximation error. It is no longer the case when linear functional is not \"decaying exponentially\" and memory growth rate is exponential.\n 3. The optimization dynamics analysis. In particular, the authors showed that under some conditions the optimization process can be stuck if the \"memory\" of the target functional is large.\n\nOverall, it is a good paper and I enjoyed reading it. It is very well written and easy to follow. In many cases, the authors provide clarification for used assumptions. \nThe authors also emphasize the difference between their results and the previous results.\n\nPros: the authors showed that difficulties encountered in practice, where the target functional has long term dependencies, emerge even in simple linear settings and can be explained from a theoretical point of view.\n\nCons: in many settings we are interested in not just recovering some dependencies, but recovering it from the data or recovering the dependency only on some subset of the all possible input sentences. The role of input data is significantly ignored in the given analysis.\n\nSeveral questions and remarks:\n1. The condition on supremum in (14) seems purely technical (at least based on provided proof in appendix). Could the authors please clarify whether this assumption has some qualitative explanation or can be replaced with stronger but more \"meaningful\" assumptions (of course it will make the result weaker)?\n2. In the dynamic analysis x is assumed to be white noise. This assumption seems too restrictive and is used to apply Ito's isometry theorem. What else stochastic processes can be used here to make this result stronger?\n3. In (50) in  (-(alpha + 1) / beta)^{i}. i should be replaced with j.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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