Inverse Approximation Theory for Nonlinear Recurrent Neural Networks
Authors: Shida Wang
Zhong Li
Qianxiao Li
Venue: ICLR 2024 spotlight (2024)
Keywords: Recurrent neural networks
sequence modelling
approximation theory
Primary area: learning theory

Abstract: We prove an inverse approximation theorem for the approximation of nonlinear sequence-to-sequence relationships using recurrent neural networks (RNNs). This is a so-called Bernstein-type result in approximation theory, which deduces properties of a target function under the assumption that it can be effectively approximated by a hypothesis space. In particular, we show that nonlinear sequence relationships that can be stably approximated by nonlinear RNNs must have an exponential decaying memory structure - a notion that can be made precise. This extends the previously identified curse of memory in linear RNNs into the general nonlinear setting, and quantifies the essential limitations of the RNN architecture for learning sequential relationships with long-term memory. Based on the analysis, we propose a principled reparameterization method to overcome the limitations. Our theoretical results are confirmed by numerical experiments.

Published as a conference paper at ICLR 2024
INVERSE APPROXIMATION THEORY FOR NONLINEAR RECURRENT NEURAL NETWORKS
Shida Wang
Zhong Li
Department of Mathematics National University of Singapore e0622338Qu. nus edu
Microsoft Research Asia zzongêmi crosoft.e.
Qianxiao Li
Department of Mathematics Institute for Functional Intelligent Materials National University of Singapore edu..sddu.... sg
ABSTRACT
We prove an inverse approximation theorem for the approximation of nonlinear relationships using recurrent neural networks (RNNs). This is so-called Bernstein-typp result in approximation theory, which deduces prop- erties of a target function under the assumption that it can be effectively approx- imated by hypothesis space. In particular, relationships that can be stably approximated by nonlinear RNNs must have an exponential decaying memory structure notion that can be made precise. This extends the previously identified curse of memory in linear RNNs into the gen- eral nonlinear setting, and quantifies the essential limitations of the RNN archi- tecture for learning sequential relationships with long-term memory. Based on the analysis, we propose a principled reparameterization method to overcome the limitations. Our theoretical results are confirmed by numerical experiments.
show that nonlinear sequence
INTRODUCTION
of the most basic machine learning models to learn the relationship between sequential or temporal data. They have wide applications from time series prediction (Connor et al., 1994), text generation (Sutskever et al., 2011], speech recognition (Graves & Jaitly] 2014) to sentiment classification (Tang et al., 2015) 1994)
Recurrent neural networks (RNNs) (Rumelhart al. 1986)
However, when there long-term dependeneies in the data, empirical results (Bengio
show that RNN may encounter difficulties in learning. In this paper, we investigate this problem from the view of approximation theory.
From approximation perspective, there are various types of theorems characterizing the connections between target relationships and model architectures for learning them. Universal approximation (Achieser) 2013, 32) and Jackson-type theorem (Achieser 2013 p. 187) provide basic guarantees of approximation and error estimates sufficiently regular target functions by particular hypoth- esis space. A number of such results available for sequence modeling, including the RNN LLi ctt al. 2020 2022). On the other hand, relatively under-investigated domain in the machine learn- ing literature are Bernstein-type theorems (Bernstein 1914 Li Li al. 2022), which are also known as inverse approximation theorems. These results aims to characterize the regularity of target relation- ships, assuming that they can be approximated efficiently with hypothesis space. These regularity notions intimately depends on, thus gives important insights into, the structure of the hypothesis space under study.
"Corresponding author

---

Published as a conference paper at ICLR 2024
This paper establishes inverse approximation result for the approximation of nonlinear function- als via RNNs. Previous works ( et al., 2020; (022) indicate that linear functionals that can be universally approximated by linear RNNs must have exponential decaying memory. This phenom- ena was coined the curse of memory for linear RNNs. A natural question is whether the nonlinear recurrent activation used in practical RNNs changes the situation. This is important since bigger hypothesis space may lift restrictions on the target functions, Moreover, it is known that nonlinear activation is crucial for feed-forward networks to achieve universality (Cybenko 1989). Thus, is worthwhile to investigate whether the linear Bernstein result generalizes to the case of approximat- ing nonlinear sequence relationships with nonlinear RNNs. In this paper, we prove that nonlinear RNNs still suffer from curse of memory in approximation nonlinear functionals that can be sta- bly approximated by RNNs with nonlinear activations must have an exponential decaying memory function. The notions of stable approximation and memory function can be concretely defined. Our results make precise the empirical observation that the RNN architecture has inherent limitations when modeling long-time dependencies.
In summary, our main contributions are:
1. We extends the concept of memory function in the linear settings (Li et al. 2020 2022) to the nonlinear setting. This memory function can be numerically quantified in sequence modeling applications.
2. We introduce a notion of stable approximation, which ensures that an approximant has the possibility be found by gradient- based optimization algorithm.
3. We prove, to the best of our knowledge, the first Bernstein-type approximation theorem for nonlinear functional sequences through nonlinear RNNs. Our results characterize the essential limit of nonlinear RNNs in learning long-term relationship. Our analysis also suggests that appropriate parameterization can alleviate the 'curse of memory' phenomenon in learning targets with long memory. The theoretical result is corroborated with numerical experiments.
Notation. For sequence of d-dimensional vectors indexed by IR, x {x, RRd E R). we denote the supremum norm by ||x]| == suPtER [2 Here |x == max, |za |a/e := : E, |x;| are the usual max (Toa) norm, L-2 represents sequence while the normal letters are scalars, vectors or functions. Throughout this paper use || to denote norms over sequences of vectors, or function(al)s, while (with subscripts) represents the norm of number, vector or weights tuple. The hat notation in this paper refers to the hypothesis space (functional) while the original symbol is referring to the target space (functional).
VE, " |c/1
and L, norm. The bold face
PROBLEM FORMULATION AND PRIOR RESULTS ON LINEAR RNNS
In this section, we introduce the problem formulation of sequence modeling as functional sequence approximation problem (Tang et al. 2023). We pay particular attention to distinguish two types of results: forward (Jackson-type) and inverse (Bernstein-typp approximation theorems. For approx- imation theory in machine learning, most existing results focus on forward theorems. However, inverse approximation theorems are of significant importance in revealing the fundamental limita- tions of an approximation approach. This paper focuses on establishing such results in the general, non-linear setting. We conclude this section with a review of known Bernstein-type estimates, which is currently restricted to the linear case. In so doing, we highlight the definition of memory in the linear case, which motivates our general definition of memory for nonlinear functional sequences in Section 3.1 The relationship between memory and approximation is central to our results.
2.1 THE APPROXIMATION PROBLEM FOR SEQUENCE MODELING
The goal of sequential modeling is to learn a relationship between an input sequence x = { and a corresponding output sequence time setting in (Li et al. 2020). where E IR. This is also a natural setting for irregularly sampled time series (eechner & Hasani 2020). The input sequence space is X' Co, R"), the space of continuous functions vanishing at infinity. We assume the input and output sequences are related
{ J. For ease of analysis, we adopt the continuous-
by sequence of functionals H (H, X + RR; E R) via y1- Hx)x,, t R. The sequential
2

---

Published as a conference paper at ICLR 2024
approximation problem can be formulated as the approximation of the target functional sequence H by functional sequence H from model hypothesis space such RNNs.
Forward and inverse approximation theorems. Given a hypothesis space H(m) of complexity (e.g. width-m RNNs), forward approximation theorems, also called Jackson-type theorems, bound the optimal approximation error inf H H| C(H, m).
(cR(m)
Inverse approximation (Bernstein-type) results are "converse" statements to Jackson-type results. From the starting assumption that an efficient approximation exists for a specific target H. Bernstein- type results deduce the approximation spaces that H ought to belong to, i.e. it identifies a com- plexity or regularity measure C(-) and show that ((H) is necessarily finite. Take the trigono- metric polynomial approximation
an example, Bernstein (Achieser 2013 p. 187) proved that if for all m 2 1 and some g > 0, c > 0, then C(H) - |H(a) < co, i.e.
inf || - M|| S m
C
HEH(m)
H must be a-times differentiable with 6-Hölder continuous derivatives.
Bernstein-type inverse approximation results are important in characterizing the approximation ca- pabilities for hypothesis spaces. For trigonometric polynomial example, it says that only smooth functions be efficiently approximated, thereby placing concrete limitation the approxima- tion capabilities of these models. Our goal in this paper is to deduce analogues of this result, but for the approximation of general nonlinear functional sequences by RNNs. Unlike the classical case where the notion of regularity enters in the form of smoothness, here we shall investigate the concept of memory as a quantifier of regularity notion that we will make precise subsequently.
2.2 THE RNN ARCHITECTURE AND PRIOR RESULTS
The continuous-time RNN architecture parameterizes functional sequences by the introduction of hidden dynamical system
dhg (Wh, Uni + b) h-x = 0, E R.
(I)
ú. = c hes
Here, d: IR the predicted output sequence value, and he R denotes the hidden state The well-definedness of the comtinuous-time RNN will be discussed in Appendix A The hyper- parameter m is also known as the hidden dimension, or width, of recurrent neural networks. For different hidden dimensions m, the RNN is parameterized by trainable weights (W, b, c). where W E mm is the recurrent kernel, U E Rm is the input kernel, b R is the bias and e E IK" the readout. The complexity of the RNN hypothesis space is characterized by the hidden dimension m. The nonlinearity arises from the activation function or-), which a scalar function performed element-wise such tanh, hardtanh, sigmoid or ReLU. The hypothesis space of RNNs is thus the following functional sequence space
kmmm) = (x + via Equation
W mmmm SU mxd E R. e RR.
(2)
Before presenting our main results, we review known Jackson and Bernstein-yy type results established for linear RNNs, corresponding to setting (2) = z and b = 0 in equation [ the definition of memory for target functional sequence, and how relates approximation properties under the RNN hypothesis space.
We shall pay attention
We begin with some definitions on (sequences of) functionals as introduced in (Li et al. 2020).
Definition 2.1. Let H {Hi, X + R; R} be sequence of functionals, Without loss of generality, we assume (2 = 0 (Otherwise we can consider the adjusted relationship H adjustedd (x) := (x) (O)))).
1. (Linear) H, is linear if for any X, X' E IR and x, E X. H2(Ax + Xx') XH,(x) + (x')..).
'The boundary condition h- = O is consistent with practical implementations such TensorFlow and PyTorch, where the initial value of hidden is set he by default.
3

---

Published as a conference paper at ICLR 2024
2. (Continuous) H₃ is continuous if for any x. X, limx' [H((')) H+(x)) 0.
3. (Bounded) H, is bounded if xx7
(x) x < co.
4. (Time-homogeneous)) H = [H, it E R] is time- hom-goooggsssuss (or shift-equivariant) if the input-output relationship commutes with time shift: let [S, (x)] It-r be a shift operator, then (S,,x) = (x)
5. (Causal) H, is causal if it does not depend on future values of the input. That is, x, satisfy xy = x/ for any 1 S lo. then H+(x) = (x'x)) for any S lo-
6. (Regular) H, is regular if for any sequence (x(x) n E NJ such that w!"") - for almost every 8 IR, then lim Hr (x(m)) 0.
The works in Li et al. (2020) 2022) study the approximation of functional sequences satisfying Definition 2.1 by linear RNNs. A key idea showing that any such functional sequence H admits Riesz representation (see Appendix A.2 and Appendix A.3)
1. p(s) Tz- -s-
Hx(x)=
VER.
In this sense, p completely determines H. and its approximation using linear RNNs can be reduced to the study of the approximation of E 1 ([0, x)), IR4) by exponential sums of the form (c (cTeWsU) UU) An important observation here is that p captures the memory pattern of the target linear functional sequence: if p decays rapidly, then the target has short memory, and vice versa.
By assuming that a target functional sequence H can be approximated uniformly by stable RNNs, then the memory of the target functional sequence must satisfy e ((()] o(1) as t oo for some Bg > O. This was coined the "curse of memory" (Li al. 2020 2022) and reveals fundamental
limitations of the RNN architecture to capture long-term memory structures.
The focus of this paper is to investigate whether the addition of nonlinear activation changes this result. In other words, would the curse of memory hold for nonlinear RNNs in the approximation of suitably general nonlinear functionals? This is a meaningful question, since Bernstein-type results essentially constrain approximation spaces, and so larger hypothesis space may relax such con- straints. We expand on this in Appendix A.4, A sigmificant challenge in the nonlinear setting is the lack of a Riesz representation result, and thus one needs carefully define a notion of memory that is consistent with p in the linear case, but can still be used in the nonlinear setting to prove inverse approximation theorems. Moreover, we will need to introduce general notion of approximation stability, which together with the generalized memory definition allows us to derive a Bernstein-type result that holds beyond the linear case.
MAIN RESULTS
In this section, we establish Bernstein-type approximation result for nonlinear functional quences using nonlinear RNNs. We first give a definition of memory function for nonlinear function- als. It is compatible with the memory definition in the linear functionals and it can be queried and verified in applications. Next, we propose the framework of stable approximation. It is a mild re- quirement from the perspective approximation, but desirable one from the view of optimization. Moreover, we show that any linear functional with an exponential decaying memory can be sta- bly approximated. Based on the memory function definition and stable approximation framework, we prove Bernstein-type theorem. The theorem shows that any nonlinear functionals that can be stably approximated by general nonlinear RNNs must have an exponentially decaying memory, which confirms that the curse-of-memon phenomenon is not limited to the linear case. Numerical verifications are included to demonstrate the result.
3.1 MEMORY FUNCTION FOR NONLINEAR FUNCTIONALS
Recall that the memory for linear functional sequence is defined by its Riesz representation in Equation B3). While there are no known general analogues of Riesz representation for nonlinear functionals, may consider other means extract effective memory function from H.
4

---

Published as a conference paper at ICLR 2024
fx 12 0,
Let x E R$ and consider the following Heaviside input sequence -p = z-
=0 (0,00))t)
(0 < 0.
In the linear case, notice that according to Equation
3
H,((²))
x
p(t)
sup 1r
sup
lp(t))1-
(4)
u 10
270
Hence, conditions on |p(t)]1 may be replaced by conditions on the left hand side, which well- defined also for nonlinear functionals. This motivates the following definition of memory function for nonlinear functional sequences.
Definition 3.1 (Memory function of nonlinear functional sequences). For continuous, causal, regu- lar and hume-hooogeneous functional sequences H (x) :t E R} X, define the following function as the memory fimction of H over bounded Heaviside input u":
(t) == sup x
Hc(u*) di
(5)
In partieular, in this paper we consider nonlinear functionals whose memory function finite for all Unlike traditional methods that evaluate memory through heuristic tasks, approach offers precise, task-independent characterization of model memories. If the oracle of the target functional available, the memory function be evaluated and the result is named queried memory. In Appendix [ and Appendix G we discuss the memory function evaluated over different test inputs and show the numerical equivalence in Appendix H Without target functional oracle, we may ap- proximate the target with the learned model and still evaluate the memory function. If the queried memory are decaying for all Heaviside inputs, then we say the corresponding nonlinear functional sequence has a decaying memory. We demonstrate in Appendix B that the memory querying shows the memory pattern of LSTM and bidirectional LSTM seueenceet--squenee models in sentiment analysis on IMDB movie reviews.
Definition 3.2 (Decaying memory). For continuous, causal, regular and time-homogeneous func- tional sequences H (H:(x) E RR on X, we say it has decaying memory if:
lim M(H) = O.
t+
We say that H has exponential decaying memory if for some B > O.
lim et (H)((( O.
Furthermore, the family } has uniformly decaying memory if
lim sup ((H,)(t))== =
(8)
t00
Remark 3.3. The requirement of decaying memory on homoeeooogessuus functionals is mild since it is satisfied if dH, is continuous Heaviside input, under the topology of point-wise convergence (see Appendix A.5 We show that dH dt are point-wise continuous over Heaviside inputs for all RNNs, thus RNNs have decaying memory (see Appendix A.6). Another related notion of fading memory is discussed in the Appendix A.7
3.2 STABLE APPROXIMATION
We now introduce the stable approximation framework. Let write the hypothesis space 7m) as a parametric space (m)) (H(:::m) Om E Om} where for each m, Om is subset of Euclidean space with dimension depending on m, representing the parameter space defining the hypothesis and H is parametric model. For example, in the case of RNNs, the parameter 0m is (Wm, Um, Um Cm)) E O,, == (Rmxmm Rexxd R x R and is the hidden dimension the RNN.
Let us consider a collection of functional sequences (Ā, f((:0m)) m 2 1} that approximates target functional sequence H. Stable approximation requires that, if one were to perturb each parameter fm by small amount, the resulting approximant sequence should still have a continuous perturbation error. For the gradient- massed optimization, this condition is necessary for to find such an approximant sequence, as small perturbations of parameters should keep perturbation error continuous for gradients to be computed. We now define this notion of stability precisely.
5

---

Published as a conference paper at ICLR 2024
301
10a
Perturbation Em.())
Perturbation error (m(
307
30a
10:4
10-4
10-2
10-2
8
0
Perturbation P
Perturbation P
(a) Target with exponential decay memory
(b) Target with polynomial decay memory
Perturbation errors for linear functionals with different decaying memory. The antici- pated limiting curve E(3) is marked with a black dashed line. (a) For linear functional sequences with exponential decaying memory, there exists a perturbation radius Bo such that the perturbation error F(3) for 0 S 3 < So is continuous. (b) Approximation of linear functional sequences with polynomial decaying memory. As hidden dimension m increases, the perturbation radius where the error remains small decreases, suggesting that there may not exist Bo achieving the stable approx- imation condition. The intersections of lines are shifting left as the hidden dimension m increases. The anticipated limiting curve E(3) is not continous for the polynomial decaying memory target.
Figure I:
Definition 3.4. For target H and parameterized model ((,)),), we define the perturbation error for hidden dimension m to be:
Em (B)
sup
Moreover, E(3) = lim supm Em (3) is the (asymptotic) perturbation error. Here [0|2 := max([W] 2, 1, 2//2/cl2))
Definition 3.5 (Stable approximation via parameterized models). Let 130 > 0. We say a target functional sequence H admits a ft-stable approximation under (7[("))) }. if there exists a sequence of parameterized approximants Hm, = H((, (m,) 6m. E 6m such that
lim H m00000
Hm +00, 0,
(10)
and for all 0 S 3 S Bo the perturbation error satisfies that E(B) is continuous in 3 for 0 S B S Bo- Remark 3.6. It can be seen that approximation only requires E(0) = 0. Therefore the stable approx- imation condition generalizes the approximation by requiring the continuity of E around / 0. If an approximation is unstable (O) = O, lim3_o E(3) > 0), it is difficult to be found by gradient- based optimizations. Since our notion of stability depends on the size of weight perturbations, one may wonder whether rescaling the norm of weights separately for each m achieves stability. There are two issues with this approach. First, the rescaled version is no-longer the usual RNN hypoth- esis space. Second, to achieve stability the rescaling rule may depend on information of the target functional sequence, which we have no access to in practice. We discuss this in detail in Appendix C
Next, we demonstrate that the stable approximation condition not too stringent in the sense that,
for linear functional sequence with exponential decaying memory (Equation (7) admits a stable
approximation. We show the numerical verification this result in Figure | The approximation
of linear functional with exponential decay can be seen in the left panel at 3 = 0 since increasing
the hidden dimension m will make the estimated error decrease to over B E [0, Ro]. Stable approximation be verified that for positive perturbation 8, adding the hidden dimension does
not increase the perturbation error E(3). In contrast, for linear functional with polynomial decaying memory, the perturbation error E(B) is not continuous at B 0.
3.3 BERNSTEIN-TYED A APPROXIMATION RESULT FOR NONLINEAR RNNS
We now present the main result of this paper, which is a Bernstein-type approximation result for nonlinear functional sequences using nonlinear RNNs. The key question is whether the addition

---

Published as a conference paper at ICLR 2024
of nonlinearity alleviates the curse of memory limitation and allows efficient approximation of functionals with slow memory decay. In the following, we show that the answer is negative, and a similar Bernstein-type approximation result holds for nonlinear functionals and RNNs with class of recurrent activations, including the most often used hardtanh/tanh activations.
Definition 3.7. We consider the Sobolev-type norm:
dHg dife
W1 = sup
| Helloc +
(11)
dt
dt
The nonlinear functional norm is given by || == supxy0 (x) + [H,( = supxy00 ||
[x)(
||*||>
Definition 3.8. We consider the following family of bounded monotone Lipschitz continuous activations which are locally- -tnh around O: For some Zo 0,
Ao (z))) c, > 0,|21 < Zo},
(12)
A (0) 0: differentiable, o' d'(2)
(0) a, 0.12| Zo}.
(13)
Notice Ao U Ag includes the commonly used activations such as hardtanh and tanh. In particular, tanh corresponds to the case a = 1 for A1 with Zo = =00
Theorem 3.9. Assume H is a sequence of bounded continuous, causal, regular and time- homogeneous functionals X with decaying memory. Let the activation be in Au U A1. Sup- pose H is Be-stably upproximated by a sequence of RNNs (H(-, (m))m== in the norm defined in Equation 11 If the perturbed models' memory functions are uniformly decaying (as defined in Definition 3.2 and the weight norms are uniformly bounded in m:
sup 1mll2 3c.
(14)
Then the memory function (t) of the target decays exponentially:
lim e ((H)(()= = 0, B <<< Bo. 6000
(15)
The proofs are included in the Appendix A.8 Given that approximations are required to be stable, the decaying memory property ensures that the derivative of the hidden states for the perturbed model approaches 0 as time t - oo. Using the Hartman-Grobmi Grobman theorem, can obtain bounds on the eigenvalues of the matrices Wn. In Appendix J we demonstrate that our methods can be generalized analyze the dynamies of GRU and L.TT.. The framework is similar while the final hidden dynamics GRU and LSTM require more techniques to analyze.
Our main result (Theorem 3.9 extends the previous linear result from Li et al. (2022). Instead of smoothness (measured by the Sobolev norm) as a regularity mea- sure, the RNN Bernstein-type result identifies exponential decaying memory (e (H) - 0) as the right regularity measure. If RNN, then that target must have exponential decaying memory. Previously this was only known for linear case, but for nonlinear case, even addition of nonlinearity substantially increases model complexity, it does not fix the essential memory limitation of RNNs.
Interpretation of Theorem 3.9
approximate some target funetionals stably using nonlinear
From the numerical perspective, the theorem implies the following two statements, and we provide numerical verification for each of them. First, if the memory function of target functional sequence decays slower than exponential (e.g. M{H((t) = (..r).)). ). the optimization difficult and the approximation in Figure is achieved at 1000 epochs while typically exponential decaying memory achieves the approximation Figure 2 that, for larger perturbation scale 3, there is no perturbation stability. Second, if a target functional sequence can be well-approximated and the approximation's stability radius 30 can be shown to be positive, then the target functional sequence should have exponential decaying memory. See Figure 3 for the approximation filtered with perturbation stability requirement. (See Figure 5 Appendix B For the validation of memory over general sentiment classification task.)
10 epochs. When the approximation is achieved, it can be seen in
7

---

Published as a conference paper at ICLR 2024
10a
m=4
Porturattin crar E(g)
m-8
101
m=
mm64
100
10-4
10
10
10
10.3
10
16
10
perturbation
Figure 2: Target with polynomial decaying memory + approximation (achieved at 1000 epochs) -> no stability. Similar to the linear functional case, when approximating nonlinear functionals with polynomial decaying memory by tanh RNN, the intersections of curves are shifting left as the hidden dimension m increases.
stabllity the approximation
memory function the target functional
m=4
Memory function M(H(())
Perturbed etter Ex((8
10-
m-16
109
m=32
10-1
10-4
10-²
10
10 10
10
10
109
20
40
60
80
100
Perturbation
Time
Figure 3: Stable approximation via RNNs implies exponential decaying memory. We construct sev- eral randomly-initialin RNN models teacher models with large hidden dimension (m 256). When approximating the teacher model with series of student RNN models, we can numerically verify the approximation's stability (left panel). We can apply a filtering: we only select those teacher models which both can be approximated, and the approximations tion error Em (3) having positive stability radius). We found that the only teachers that remain are those with exponential decaying memory functions. An example is shown in the right panel.
stable (with perturba-
3.4 SUITABLE PARAMETRIZATION ENABLES STABLE APPROXIMATION
The key insight of Theorem 3.9 can be summarized follow: in order to approximate targets with non-exponential decaying memory, the recurrent weights of RNNs must have eigenvalues' real part approaching on the negative side. However, if the largest eigenvalue real parts are approaching zero, then its stability under perturbation will decrease. This is why the approximation and stability cannot be achieved at the same time if the target's memory does not decay exponentially. The stability problem can be resolved via reparameterization even when the eigenvalues are approaching O. If we reparameterize the recurrent weights so that it approach zero and remain stable (i.e., eigenvalue real part being negative) under perturbations, then this architecture will maintain stability while having the possibility of approximation. We can accomplish this by substituting the recurrent weight with a continuous matrix function, which will refer to as "stable reparameterization"
the stability radius is not decreasing
R M g(M) = W.
(16)
This reparameterized RNN is stable as the eigenvalues' real part are always negative. We show there are several methods to achieve this reparameterization: The exponential function g(M) = - and the softplus function g(M
log(1 + e.ad) maps the eigenvalues of M to negative range (see Figure 4 and Figure 8 for the stable approximation
linear functional with polynomial decay memory). LRU (Orvicto et al. 2023) proposed to parameterizes the real part of eigenvalues by exp(-exp(A)) which corresponds to the discrete case for (MM = M
8

---

Published as a conference paper at ICLR 2024
Perturbation E
Porturbation cmor Eall)
107
R-11
205
13-1
20-
12"
10"
10-1
10-3
30t
10'
12-1
12-3
10
12*
201
Perturbation
Perturbation
(a) Exp reparameterization + Linear RNN
(b) Softplus reparameterization Linear RNN
Figure 4: Stable approximation of linear functionals with polynomial decay memory by linear RNN with exp and softplus reparameterization. The limiting dashed curve E(B) shall be continuous.
4 RELATED WORK
Various results have been established in RNNs approximation theory, see Sontag (998); Hanson et al. (202T) and references therein. For unbounded input index sets, Lp approximation is estab- lished by Gonon & Ortega (2020). In Gonon & Ortega (202I). the universal approximation theorem constructed for functionals with fading memory in the discrete time setting. In et al.] (2020), the universal approximation theorem and Jackson-type approximation theorem characterize the density and speed of linear RNNs applied to linear functionals, Most existing results are forward (Jackson- type) approximation theorems, which upper bound the optimal approximation error. Of most rele- vance is the Bernstein- -ype result proved in Li et al. (022). where it has been proved that the linear functional sequences that can be efficiently approximated by linear RNNs must have an exponential decaying memory. However, the main limitation of the above result is the linear setting for both models and targets.
The notion of approximation stability is one of the central concepts exploit in this paper. We note that in classical approximation theory, stable approximation has numerous definitions depending on the setting Vore et al., (02II. For example, in nonlinear approximation (De Vore 1998), stably approximating sequence { of H is one that satisfies |/m,| S C'H( for some absolute constant C> 0 and all This approach is taken to show the non-existence of stable procedure to approx- imating functions from equally-spaced samples with exponential convergence on analytic functions (llatee et al., 2011). This notion of stability is the conditioning of the approximation problem. In contrast, our notion of stability introduced in Section 3.2 is more similar to a uniform continuity requirement. Pertaining to sequence modeling, a related but different notion of dynamic stability (Hanson & Raginsky, (2200) was used to prove a Jackson-type results for universal simulation of dynamical systems. There, the stability is akin requiring the uniform (in inputs) continuity of the flow-map of the RNN hidden dynamics. In practice, some specific forms of the stable reparameter- ization we defined in Equation (T6) has been adopted in state-space models optimization (Gu al.)
2020 2021 Smith et al.
2023
Wang & Xue 2023 Wang & Li 2023).
5
CONCLUSION
In summary, we derive an inverse approximation result in the setting of sequence modeling using nonlinear RNNs. We show that, assuming that a given target sequence relationship (mathemati- cally understood as a nonlinear functional sequence) can be stably approximated by RNNs with nonlinear activations, then the target functional sequence's 's memory structure must exponentially decreasing. This places priori limitations on the ability of RNNs to learn long-term memory in sequence modeling, and makes precise the empirical observation that RNNs do not perform well for such problems. From the approximation viewpoint, our results show that this failure is not only due to learning algorithms (e.g. explosion of gradients), but also due to fundamental limitations of princi-
the RNN hypothesis space. At the same time, analysis points to reparameterization pled methodology to remedy the limitations of RNN when it comes to long-tern memory and we demonstrate its effectiveness in by learning linear functionals with polynomial memory.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This research supported by the National Research Foundation, Singapore, under the NRF fellow- ship (project No. NRF-NREFF13-222--0005) Shida Wang is supported by NUS-RMI Scholarship.
REFERENCES
N. I. Achieser. Theory of Approximation. Courier Corporation, June 2013. ISBN 978-0-486-15313-
1.
Y. Bengio, Simard, and Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157-166, March 1994. ISSN 1941-0093. doi: 109/77.2.....11.....
Serge Bernstein. Sur la meilleure approximation de |x] par des polynomes degrés donnés. Acta Mathematica, 37(1):1-57, December 1914. ISSN 1871-2509. doi: 10. 100000FF22400822
Stephen Boyd, L. O. Chua, and C. A. Desoer. Analytical Foundations of Volterra Series. IMA Journal of Mathematical Control and Information, 1(3):243-22 January 1984. ISSN 0265-
0754. doi: 10.1093/mmamc//1..222
Jerome T. Connor, R. Douglas Martin, and Les E. Atlas. Recurrent neural networks and robust time series prediction. IEEE transactions on neural networks, 5(2):240 254, 1994.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Con- trol, Signals and Systems, 2(4):303-314, December 1989. ISSN 1435-568X. doi: 10.1007/ BF02551274.
Ronald Vorere, Boris Hanin, and Guergana Petrova. Neural network approximation. Acta Numer- ica, 30:327-444, 2021.
Ronald De Vore. Nonlinear approximation. Acta numerica, 7:51-150, 1998. ISSN 1474-0508.
Lukas Gonon and Juan-Pablo Ortega. Reservoir Computing Universality With Stochastic Inputs. IEEE Transactions on Neural Networks and Learning Systems, 31(1):100-112, January 2020. ISSN 2162-2388. doi: 1.1100//NNLSS2019.225200
Lukas Gonon and Juan-Pablo Ortega. Fading memory echo state networks are universal. Neural Networks, 138:10-13, 2021.
Alex Graves and Navdeep Jaitly. Towards End-To-End Speech Recognition with Recurrent Neural Networks. Proceedings of the 31st International Conference on Machine Learning, pp. 1764- 1772. PMLR, June 2014.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. HÎPPO: Recurrent Memory with Optimal Polynomial Projections. Advances in Neural Information Processing Systems, volume 33, pp. 1474-1487. Curran Associates, Inc., 2020.
Albert Gu, Karan Goel, and Christopher Re. Efficiently Modeling Long Sequences with Structured State Spaces. In International Conference on Learning Representations, October 2021.
Joshua Hanson and Maxim Raginsky. Universal Simulation of Stable Dynamical Systems by Recur- rent Neural Nets. Proceedings of the 2nd Conference on Learning for Dynamics and Control, pp. 384-392, PMLR, July 2020.
Joshua Hanson, Maxim Raginsky, and Eduardo Sontag. Learning Recurrent Neural Net Models of Nonlinear Systems. In Proceedings of the 3rd Conference on Learning for Dynamics and Control, pp. 425-435. PMLR, May 2021.
Haotian Jiang, Qianxiao Li, Zhong Li. and Shida Wang. A Brief Survey the Approximation Theory for Sequence Modelling. Journal of Machine Learning, 2(1):1-30, June 2023. ISSN 2790-203X, 2790-2048. doi: 10.4208/jm1.221221.
H.K. Khalil. Nonlinear Systems. Pearson Education. Prentice Hall, 2002. ISBN 9780130673893.
10

---

Published as a conference paper at ICLR 2024
Mathias Lechner and Ramin Hasani. Learning long-tenn dependencies in iregularly-samplee time series. arXiv preprint arXiv:2006.044/ 2020.
Zhong Li, Jiequn Han, Weinan E, and Qianxiao Li. On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis. In International Conference on Learning Representations, October 2020.
Zhong Li, Jiequn Han, Weinan E, and Qianxiao Li. Approximation and Optimization Theory for
Linear Continuous- Time Recurrent Neural Networks. Journal of Machine Learning Research, 23 (42):1-85, 2022. ISSN 1533-7928.
Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pas- canu, and Soham De. Resurrecting recurrent neural networks for long sequences. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of ICML '2, pp. 26670- 26698. JoLR.org, July 2023.
Rodrigo B. Platte, Lloyd N. Trefethen, and Arno B. J. Kuijlaars. Impossibility of Fast Stable Ap- proximation of Analytic Functions from Equispaced Samples. SIAM Review, 53(2):308-315 January 2011. ISSN 0036-1445. doi: 10.1 10.1137/090774777.
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back-propagating errors. Nature, 323(6088):533-556 October 1986. ISSN 1476-4687. doi: 10.1038/32353aa..
Jimmy T. H. Smith, Andrew Warrington, and Scott Linderman. Simplified State Space Layers for Sequence Modeling. In International Conference on Learning Representations, February 2023.
Eduardo D. Sontag. A learning result for continuous-time time recurrent neural networks. Systems & Control Letters, 34(3)1151-188 June 1998. ISSN 01676911. doi: 10.1016/50167-6111999 00006-1.
Ilya Sutskever, James Martens, and Geoffrey Hinton. Generating Text with Recurrent Neural Net- works. In International Conference on Machine Learning, pp. 1017-1024, January 2011.
Duyu Tang, Bing Qin, and Ting Liu. Document Modeling with Gated Recurrent Neural Network for Sentiment Classification. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 1422- 1432,1432, Lisbon, Portugal, September 2015. Association for Computational Linguistics. doi: 10. (0.18633/1/DD15-1166)
Shida Wang and Qianxiao Li. Stablessm: Alleviating the curse of memory state-space models through stable reparameterization. arXiv preprint arXiv:2311.14498 2023.
Shida Wang and Beichen Xue. State-space models with layer-wise nonlineariy universal approx- imators with exponential decaying memory. In Thirty-Sevntth Conference on Neural Information Processing Systems, November 2023.

---

Published as a conference paper at ICLR 2024
A THEORETICAL RESULTS AND PROOFS
In this section, we first attach the famous Riesz representation theorem and the previous results for linear RNNs in Section A.2 A.2 and Section A.3
A.1 WELL-DEFINEDNESS OF CONTINUOUS-TIME RNN
Here we discuss the well-definedness of continuous time nonlinear RNNs. The -oo boundary con- dition is chosen to make the tmmehomogeneity well-defined, representing more general scenario than the boundary at O. Regarding issues on the input continuity, Heaviside inputs are point-wise limit of smooth inputs 1Tdh limg-+o coontt Therefore the outputs of continuous targets function- als are well-defined: H, (limkoooo comt)) limg-+oo Hg (u,
A.2 RIESZ REPRESENTATION THEOREM
Theorem A.1 (Riesz-Markov-Kakee)
representation theorem). Assume H linear and continuous functional. Then there exists unique, vector-valued, regular, countably additive signed measure on R such that
Co - R is
H())
[
J. dp(s)( Σ ==1 JR
xx,ddu((s).
(17)
In addition, we have ||||| == supp [xxx] ||ll| (R) Es [R:(
Based on the representation theorem, can further obtain that the functionals {H t E R} satisfying properties Definition 2.1 can be represented by the following convolutional form
H2(x) I00 x(-sp(8)ds, L R
(18)
and the representation function p 10, o0) - RRd is a measurable and integrable function with ||ellx> ((0,cc)) suPteR ||He]]- The details can be found in Appendix A.3 or Li et al. (2020), where the causality and homeeenett play a key role.
A.3 THREE TYPES OF APPROXIMATION FOR LINEAR FUNCTIONALS AND LINEAR RNNS
We include the statements of the universal approximation theorem and approximation rate for linear functionals by linear RNNs from Li et al. (2020).
Theorem A.2 (Universal approximation for linear functionals by linear RNNs (Li et al. 2020
Let HHe t E R} be a sequence of linear, continuous, causal, regular and tone-hooogeneous functionals defined on X. Then, for any 0, there exists {H, t R. Hlinear such that
sup H H.ll sup sup [H, - H, S..
(19)
RE
tER ||x]_=
Theorem A.3 (Jackson-type approximation rate for linear functionals by linear RNNs (Li et al. 2020 Assume the same conditions as Theorem [12 Consider the output of constant signals
(t()) = H,(e:),
i= 1=1,...,. .d.
where e; a constant signal with t,,t = e, e, (1203. and {es) denote the standard basis vectors in Rdd Suppose there exist constants & E N4. 7 > 0 such that for = 1, 1..... d. = 1,.... & + 1, (t) E C(++1)(R) and
Bt (1) (t) o(1), as t t +00,
y
3 (k) (1)
sup E20
Then, there exists a universal constant C(a) only depending on a, such that for any m E N4, there exists sequence of width-m RNN functionals (H, :t R) Hlinear such that
sup sup [H(()) - Hx(x)) Clayyd
R(m) sup
|He
Hell
(20)
tER
tER |1
8m
12

---

Published as a conference paper at ICLR 2024
Theorem A.4 (Bernstein-tyee) type approximation for linear functionals by linear RNNs (Li al. 2022 Let {H, t E R) be a sequence of linear, continuous, causal, regular and time- heme-hooogeeeuus functionals defined on X. Consider the output of constant signals
(t) Hi(es) E (la+)) L d, E
(21)
Suppose that for each m 4., there exists a sequence of width-m RNN functionals (H, : R} Hmmear approximating H₃ in the following sense:
lim sup Ni.m (1) v/ (8) (1) - 0, i= k a+1,
(K)
(22)
+00000 120
where
mm Hi(e:), i=
(23)
Define Wm. ma/m Re(Aş), where {Ag]ī=1 are the eigenvalues of W in {H, E R}. Assume the parameters are uniformly bounded and there exists constant B > 0 such that lim supm-roe Wm. -3, then we have
(k) (t) = o(1) as + t00, i= k at1 e Vi
(24)
A.4 WHY SOLVE CURSE OF MEMORY BY ADDING NONLINEARITY?
In ferd-forward neural networks, the inclusion of nonlinear activation known to fundamentally change the approximation capacities of multi-layer networks. Without this nonlinear activation, the model simply performs a linear transformation. In sequence modeling, linear RNNs serve as universal approximators for linear functionals. However, they struggle to learn linear functionals with polynomial decaying memory. Given this context, one might naturally wonder if incorporating nonlinear activation could expand the hypothesis space in such way to overcome this 'curse of memory' problem.
Section indicates that the presence of nonlinear activation does not fundamentally alter the mem- ory pattern of models. Consequently, for stable approximation, targets must demonstrate an expo- nentially decaying memory. The proofs also show that hardtanh/tanh RNNs require the eigenvalues to be bounded away from 0.
The findings in Section 3.3 lead to the proposal of stable parameterisation a potential solution for long-memory learning. Stable parameterisation ensures that the real parts of eigenvalues for the recurrent weight matrix remain negative, even when the weights undergo perturbations. In Figure 4 we demonstrate that linear RNNs can stably approximate linear functionals with polynomial decay memory when the recurrent weight matrix is parameterised using exponential/softplus parameterisa- tion. Moreover, by selecting linear functionals with either exponential or polynomial decay memory, we can clearly change the targets' memory structures.
A.5 POINT-WISE CONTINUITY LEADS TO DECAYING MEMORY
Here give the proof of decaying memory based the point-wise continuity of dH, and bound- edness and time-homogeneity of H:
Proof.
dHc dt
dHo
dHo dt (x) 0.
lim The first equation comes from homo-homggeneity The second equation is derived from the point- wise continuity where input means constant for all time x. (62-00) By time-homogeneit and boundedness, the output over constant input is the same: H,(x) = Hx(x) for all 8, L. Therefore dlla dt (x) O.
lim
(u")
1/22-11)
dt
A.6 POINT-WISE CONTINUITY OF NONLINEAR RNNS
We prove that nonlinear RNNs with Lipschitz continuous activations are point-wise continuous over bounded, piece-wise constant input sequences, including the Heaviside inputs.
13

---

Published as a conference paper at ICLR 2024
Proof. Without loss of generality, assume t 0. The following refers p norm.
Assume the continuous imputs sequence converges to some bounded piece-wise constant input se- quence in point-wise sense: limg X x. For any bounded interval [-B, B], can see the outputs are well-defined and the point-wise (in t) convergence holds:
Let h and he be the hidden states X and By definition and triangular inequality
dlb hel (o UZK oWh,, + Un,)) [(W]|kk, h |U[| zel)-
dt
Here L the Lipschitz constant of activation
Apply Grönwall inequality to the above inequality, we have:
Ihae hel S / e.(WI((s>) LUU v. /
As the inputs are bounded, by dominated convergence theorem we have RHS converges to 0 there-
fore
lim 1 hel = 0.
Therefore the point-wise convergence of dil, can be achieved:
df
dyr.
dye
lim
lim CL((Wiher hel + |0| 2,l) = 0.
1-500
dt
dt
dHs are point-wise continuous functionals "bounded piece-wise constant input sequence".
So we have: limg
duaat
due. Therefore
A.7 COMPARISON OF DECAYING MEMORY AND FADING MEMORY
The targets with decaying memory is a common assumption in the sense that it can also be de- rived from the uniformly asymptotically incrementally stable assumption from Hanson & Raginsky (2020), which demonstrated by 'imperfect system models may still be capable of generating out- puts that uniformly approximate the outputs of the original system over infinite time intervals'.
There is a concept of fading memory introduced in nonlinear functional approximation with Volterra series (Boyd et al., 1984). A functional is said to have fading memory if there exists monotonically decreasing function w R_ + (0, 1], lim w(t) = O, such that for any 0, there exists a 8 > 0 such that for any x, x' X,
Hx(x)) - Hx)x') < whenever
X, - #E(-00.1)
sup
----xu x,ww(t - s) < Ó.
(25)
Remark A.5. terms of relations between fading memory and decaying memory, they are independent. On one hand, there exists so-called peak-hold operator (Boyd et al. 1984) with decaying memory (but not fading memory). On the other hand, it is possible for linear functional to only have the fading memory (but decaying memory), where it needs only the requirement [p[e]l2 ds oc, which does not imply lim (p(s)12 Jo mc(s]]
A.8 INVERSE APPROXIMATION THEOREM FOR LIKE ACTIVATIONS
We hereafter call H. A. im. to be the perturbed models.
We will briefly summarize the idea of the proof. Given that approximations are defined be stable, the decaying memory property ensures that the derivative of the hidden states for the perturbed model approaches
time + oo. The decay rate of the memory function characterised by the db, converges to O. Using the Hartman Martman-Grrobmnn theorem, we can obtain bounds on dt
rate at which
the eigenvalues of the matrices W W.. These bounds, in turn, determine the decay rate of di. exponential decay in the model's memory function. Finally, since the models with uniformly
de leading
14

---

Published as a conference paper at ICLR 2024
exponential decaying memory only approximate targets with exponential decay, the memory function of the nonlinear target functionals must also be decaying exponentially.
For simplicity of the notation, strengthen the assumption from lim supm-+so limm-+oo- To get the result for lim supmssumee we only need to consider the subsequence of my with limit.
Proof. Define the derivative of hidden states (for unperturbed model Hz(+, to be Um,t similarly, Em, is the derivative of hidden states for perturbed models (He Hel, 8m,)), Um,t =
dhmat de
de
Since each perturbed model has decaying memory, by Lemma A.6 we have lim un,t = O, Vm.
(26)
+000
In particular, for each m and perturbation within the stability radius, there exists to which depends on m and Zo such that 1m < Zo, 2 to-
If the inputs are limited to Heaviside input, the derivative of perturbed models' hidden states ö,.t satisfies the following dynamics:
dūm.t
= o' (fm,t) WWm = co Wm,tt 1 40
(27)
dt
m,to o (Wmhht + Un bm), 18m,tooo < Zo-
(28)
Select a sequence of perturbed recurrent matrices (W (Wm, satisfying the following two proper- ties:
1. Ca Wm,k is Hyperbolic, which means the real part of the eigenvalues of the matrix are nonzero.
2. limg m, Wm) Bo4m- (Notice that m,,k Wml S Bolm for all k)
Moreover, by Lemma A.7 we know the each hyperbolic matrix co Wm,k is Hurwitz as the system for Um is asymptotically stable.
max (Re(A; (Wn))) <0
(29)
EE ml
max (W.)))(..))) < -Bo.
(30)
iE
Therefore the original unperturbed recurrent weight matrix Wm satisfies the following eigenvalue inequality uniformly in m.
sup max (Re(A:(Wmm)) < -
(31)
xE(m)
As the memory functions of the perturbed models uniformly decaying, we consider a subclass of perturbed models where only the weight of linear readout map Cm are perturbed. In other words, we are considering perturbed models with weights (Wiss Um, bms Gm). Since the supremum of perturbed model memory functions are decaying:
d
lim sup 6-000 vn
dt pm. 0.
(32)
For any c O, there exists a T. > such that for all f > Te.
sup I8..
dt Um,
sup 18. Son-emlat
|8T Um,el
(33)
2 300
We have
Ioy Umel + Bo 2olum,e22 <e;
(34)
Jum,e22
t> Te.
(35)
By'
15

---

Published as a conference paper at ICLR 2024
Select Zo, have the unperturbed derivative |Um,112 < Zu for t Te. Therefore the dynamics of Um,, is a linear system for Te. For 2 Te
lum,l22 = 1e (t- Te) Um,..
(36)
< 1e (mn(t-Ie)) (ol---)))pp 12,
(37)
3 e Bo(t-TT) TT) Um,
(38)
The model memory decays exponentially: For t 2 Te.
IcT Um,el
S cm |2| 12/um,, 12 Ao(t- T.)
(39)
< Cm - - 3o((-T.)
(40)
= Cm 2 70 3oTe e -Pot
(41)
For E [0, as the memory function is continuous, there exists a constant C'
:=
sup @dat cm um such that sE(o,T.]
em um S Aet- t tE [0, T.]
(42)
There exists constant Co == max(sup,,. |mml2 Zoe ,')) such that for any m,
1
d
M( (t) sup
dll Mom.e S umel S Che Bot t2
(43)
|oc
Last, by Lemma A0 the target H has an exponentially decaying memory as it is approximated by a sequence of models [Hm]m=
Joe with uniformly exponentially decaying memory.
A.9 INVERSE APPROXIMATION THEOREM FOR TANH-LIKE ACTIVATIONS
Next we give the proof for RNNs using tanh-like activations.
Proof. Similar to the previous proof, we still have
lim Un.t 0, Vm.
(44)
In particular, for each m and perturbation within the stability radius, there exists to such that lom, < Zo,L 2 lg-
Now, the perturbed hidden states satisfies the following dynamics:
dūm.t d'unh (im,t) o W Dm,t = (I Diaa((m,,)) Dm.e. Om..
(45)
dt
0m Junh (mmro + bm).
(46)
Select a sequence perturbed recurrent matrices D satisfying the following two proper- ties:
1. Wm, mi Hyperbolic, which means the real part the eigenvalues of the matrix are nonzero.
2. limg (Wm,k Wm) = 3o
By Lemma we know each hyperbolic matrix Wm,k is Hurwitz as the target functional sequence has stable approximation. Similarly, we have the following uniform bound on eigenvalues of (Wm):
sup max (Re (W..)))),)) < - xc(m]
(47)
Since every W. is Hurwitz matrix, consider the corresponding (continuous) Lyapunov equation (Khalil 2002)
WI m + Wm. -Q
(48)
16

---

Published as a conference paper at ICLR 2024
For simplicity, select the matrix Qm Im- For any positive definite matrix Qms it is known that Pm has an explicit integral form:
(- W "mm'meee Wm' dt S/² Wii'' emewmtdtt.
Pm
(49)
By Lemma
A.8 we know P.. has uniformly bounded L2 norm
sup pmpll S 250
(50)
We construct Lyapunov function V(v) = Pm S 23, which satisfies the following differ- ential equation:
dV (Um,))
= mm (W. - Diag(Um,r) 3) + Pm (im,)(m,;) W Um,
dl
=0 (. Pm + Pm W Um,t
(51)
-W Diag((umm Pm + Pm Diag(Um..)) (m.
= =- 1mm,,, - Un (W.,) Diag(Um,)) Pm + Pm Diag(Um,)) 2 Wm mmmm.
By Lemma A.9 for any positive I. E 1), there is an Y PaL
O such that the following
inequality holds for any m, 1 (W. ( Pm. Diag (Dmiag(mm..)* (Um,,) (eW)mmmt L Ll
V/em,,12
Tz.
(52)
As the memory functions of the perturbed models are uniformly decaying, we consider a subclass of perturbed models where only the linear readout map Cm are perturbed. Since the limit of perturbed model memory functions are decaying:
d
lim sup m
Um. 0.
(53)
di
For any e O, there exists a T, such that for all 1 Te
sup 1êm Emm
dt Um.t
sup
1c um,l <.
(54)
1mm 1am-eml255
We have
Om Um,el
3o folmmel22 <,,
(55)
|umel22
(56)
Bo
Select < Y,, we have
[um < Ti,
(57)
Bo
The Lyapunov function satisfies the following inequality for 2
dV (Um.))
10m,t12 umm "
(W. Diag(vm..)))) 2 + Pm, D ? )m,t
(58)
dt
< |0m, 1 + L| L/vm,e12
(59)
(1 L))mmm,
(60)
I 2(1 - 30 (Mm,)).
(61)
The Lyapunov function ((mm,t) is decaying exponentially for < To,,, 2 To,
(Umma) <e- - (vm..:)
(62)
Notice that |0m,e/2 5 Tr. Therefore
V(vm,)) -112(1-L)80(t-T1)
r2.
(63)
2,8
17

---

Published as a conference paper at ICLR 2024
Since the model weights uniformly bounded, there is constant M such that
sup mm M < co.
(64)
m
Since |m1/2 1mmll Pml2, this implies
1
min Pml2 2 > 0.
(65)
2M
As (Um,,)) 2
2M 1 there exists a uniform constant Co == V Do r, =
V
ML Mo
such that
10m,112 & Coe -1-1-))11 TT), Vt > Te.
(66)
Since the model weights 6n are uniformly (in m) bounded C = supm Cm//2 0o. Therefore the model memories uniformly (in m) exponentially decaying
d H m, (u*)
de
sup M(H = supsup
S -
(67)
|0 +
=#0
Notice that T. is independent of m, it only depends on
Take + 0, for any B < So there exists a constant C* which depends on / such that
sup.M(Hm)(() < ar m
(68)
Last, by Lemma A0 the target has exponentially decaying memory as is approximated by sequence models with uniformly exponentially decaying memory.
A.10 PROOFS OF LEMMAS
In the following section we include the lemmas used in the proof of main theorems. Lemma A.10 is
used the proof for Theorem 3.9 Lemmas [A.6 a0 applied in Appendix A..
Lemma A.6. Assume the target functional sequence has a Stable approximation and the per- turbed model has a decaying memory, we show that ū,,t - 0 for all m.
Proof. For any fix Wm, and Üm. Since the perturbed model has a decaying memory,
d
lim - Hm (u))
lim
T Gm O.
(69)
dt
According the definition of stable approximation about perturbation, as t co, θn, vanishes over the projection to ém for any 12m Cmloc S B. By linear algebra, there exist (Ac; I A such that C.. Aci, .... Cm + Acm form a basis of Tm We can then decompose any vector u into
u kn (cm Act) + + (cm + Acm).
(70)
Take the inner product u and Ün,t, we have
lim u 0
Σ i=1
Ki lim (cm + Ac;) Th
(71)
t-00
As the above result holds for any vector u. we get
lim
Um, = 0.
(72)
t-000
Lemma A.7. Consider a dynamical system with the following dynamics:
du
Diag(o Diag(o'(x:)) (v:))
dt Un a (Uxo + b).
(73)
If W E mm is hyperbolic and the system in Equation 73 is asymptotically stable over any bounded Heaviside input |ra] < B, then the matrix W is Hurwitz.
18

---

Published as a conference paper at ICLR 2024
Proof. When is the linear- like activation, (2) Co for |2| < 1, Diag(o' Diag(o"(Pm.))) colm- When is the tanh-like activation, d'(z) a bo (z)². Also, a is continuous at O, therefore a is an open mapping around For sufficiently large B, there exists 6.n > such that a small ball centered at 0 is contained in the initializations that are stable for the system in Equation (73)
E B(0, 5m) S {o(Uxo + b) | < B}.
(74)
0 for any uo E B(0, 6,), it implies the local asymptotic stability at the origin. If W has an eigenvalue with positive real part, according theorem, 8/ has an unstable manifold locally at the origin. However, this contradicts the asymptotic stability around the origin with the initialization vy B(0, 6m) C E
For systems with linear-like activations, since lim
to
For systems with tanh-like activations, again by Hartman-Grobnnn theorem, the asymptotic stability determined by the linearized system, therefore W is Hurwitz.
Lemma A.8. Given a sequence of Lyapunov equation with Hurwitz matrices {wn, [Wm)ir 1000
m=1
W...m m + Pm = -Im-
(75)
Assume the eigenvalues of Wm are uniformly bounded away from 0:
sup Re (e()::Wm)) S -oo iE(m)
(76)
Show that the L2 norm of Pm. are uniformly bounded
sup
|| Pm 1l S
(77)
2,30
m
Proof. By the theory of Lyapunov equation metric dositive-definite matrix
Khalil 2002, 136), it can be verified that the sym-
W T T Wmldd dl.
P.
(78)
is the solution to the above Lyapunov equation.
Assume Wm eigenvalue-eigenvectoo couples are us), i E [m]] Without loss of generality, we assume v, are all unit eigenvectors.
||0:||2 1, S i < m.
(79)
For simplicity, we first assume the eigenvalues are distinct. Therefore, any unit vector can be decomposed into linear combination of eigenvectors
1.
(80)
We have
P 11
||e Wint 1|2dt
(81)
000
ce 2h
(82)
1=1
m
c
2hxt dt
(83)
1=1
m
C
23ot dt
(84)
1
280t dt
(85)
2,30
19

---

Published as a conference paper at ICLR 2024
Therefore, || l22 I uniform.
1- Notice the bound on Lg norm is uniform as the eigenvalue bound W.. 2/%
Next, Wm has repeated eigenvalues, we can consider Wm with slight perturbations such that the perturbed Wm, are diagonalizable. In this case the eigenvalues might not be distinct but it's feasible to construct the eigenvectors to be orthogonal to each other. We can bound the perturbed matrix's 's L2 norm with the previous argument. The corresponding Pn. converges to Pm by the continuity of explicit form in Equation 78
Lemma A.9, Assume {Wm Rmxm] bounded away from 0:
Jm=1 is a sequence of Hurwitz matrices with eigenvalues
sup max (Re( S - m iE(m)
(86)
Assume the max norms for matrices {W. m 1m
uniformly bounded:
sup sup
[W S Mo.
(87)
m Isijsm
Define the solution to the following Lyapunov equation to be Pmm
W Pm P. -I
(88)
We show that for any positive constant L, there exists T > O such that the following inequality holds for any m and [Uml2 S T:
1m (W. Diag(Um) (m)) ) Pm + Pm.Daag(v..) (m W m)mml I T/uml?. m
(89)
Proof. First, by the property matrix and vector norm:
Iu Pm Diag(Um)) 2 m Uml S |mm/2 Pm Diag(Um ) ? Uma
(90)
1
S
Imm la Diag (im) 2 Um
(91)
2,30
Notice that the second inequality holds as a direct result for Lemma A.8
Then,
Diag(Um) ? um12
Min.j W Wm.
(92)
m W Wmmilllmm.l
(93)
m. Mo 1l2
(94)
j=1
Mo
m. | 1m,
(95)
1=1
m
Mo
Umm (2)
(96)
1=1
Mo
2 um.
Um (2)
(97)
Mol Umm
12
(98)
Y |Umm 22-
(99)
20

---

Published as a conference paper at ICLR 2024
For any 0 < T $ /
BuL Mo
we have
| (W m (mm) + Pm Diag((mm) (vm) (Um) 2 )mml
2
Um |m (inlaDDag(((m)) W Uma
(100)
2,50
1
MM r 12mm
(101)
80
Lluml.
(102)
Lemma A.10. Consider continuous function f [0, oo) + R. assume it can be approximated by
sequence of continuous functions {fm m= universally:
lim sup fm (4) O. m-
(103)
Assume the approximators fm are uniformly exponentially decaying with the same 3o > 0:
lim sup e0 - 1oo mEN.
(104)
Then the function J is also decaying exponentially:
lim e (f(()) 0, 0A < B < Bo- t-000
(105)
Proof. Given function f E C((0, we consider the transformation TJ [0,1] + R defined
as:
{
O,
8 ==
(Tf)(s) =
Ιl Inr
(106)
(0, 1).
Under the change of variables e 9ot, we have:
f(t) = Fot (Tf)(e Sot), (oot)) t2 0.
(107)
According to uniformly exponentially decaying assumptions on fm:
lim (T lim fm)(t) s *-00
lim efot (t) 0,
(108)
--t Oyt
which implies Jm E C(10, 1]). For any B < So let 8 = 30
B 0. Next we have the following estimate
sup
[T (m, (s) - (mfm))(s)
(109)
se [0.1]
Jm
fiz (t)
sup 120
(110)
e-
e-3t 8t
Smy (1)
Smg
< mmx
sup UUSIST
Coe 820
(111)
e e-it St
e e-
<max
9To
sup 0S1STo
1fm, (t) fmy (t)l, One -8T
(112)
where Co is constant uniform in
In(
we have Coe 8Th < e. For sufficiently large M which depends on and To, by universal approximation (Equation (103) ), we have Vm,, m2 M,
For any >> 0, take Tú =
sup |m (t) fma (t) S BToe,
(113)
Ust5T:
sTD sup |/m, (!) Smg (1) S USt5%
(114)
Therefore, {fm) is Cauchy sequence in C((0, oo)).
21

---

Published as a conference paper at ICLR 2024
Since {ffm) } is Cauchy sequence in C([O, oo)) equipped with the sup-norm, using the above esti- mate we can have fm] } is a Cauchy sequence C[(0, 11) equipped with the sup-norm. By the completeness of C(O,, 1]), there exists f E C((0, 11) with (0) = 0 such that
lim sup ((T - (s) O.
(115)
m m0000 sE(O.1]
Given any >> O, we have
( lim (Tfm)(s) (Tf)ss).
(116)
m m=+00
hence
lim el(()) t100
s(1)
lim (=) = O.
(117)
5-0+
B MEMORY QUERY IN SENTIMENT ANALYSIS BASED ON IMDB MOVIE REVIEWS
In the following example, show the memory function of sentiment score's for single repeated word using LSTM and fine-tuned BERT model. In Figure it can be seen that the memory function of simple words such "good" and "bad" is decaying exponentially. However, the memory of sentiment in "ha" can be complicated as it's not decaying fast. This phenomenon also holds for stacked Bidirectional LSTM models.
As comparison, we can see the memory pattern of BERT over repeated characters or words can be decaying relatively slower. At the same time, the fluctuation of memory of "ha", "bad" and "good" can fluctuate lot (compared with LSTM models). These phenomena indicate that the transformer- type architectures might not have exponential decaying memory issues. (See Figure
10'
Mamay Sattthon Machoaseeeee
9oed
bad
X2+1
sood
Lod
20
42-4
30-4
12-4
30-4
Bezear 190ee
Separt Eimes
(a) Bidirectional LSTM
(b) Stacked Bidirectional LSTM
Figure 5: Memory function of sentiment scores for different words based on IMDB movie reviews using Bidirectional LSTM and stacked Bidirectional LSTM
C RESCALING IS NOT AN A PRIORI SOLUTION TO STABLE APPROXIMATION
Now consider the special case: Assume W is diagonal W diag([w1, wa ..... Wn)) Element of matrix U is 1. And the vector = [C1, C2,..., Cmu)
In this section, compare the vanilla linear RNN with memory function p(t) En t and a rescaled linear RNN with memory function p(t) Σ Cgekwee wet, They are represented in the simplest form with ej and wa the trainable weights. It can be seen that the target linear functional with memory function p(t) Σx 12 e it cannot be stably approximated by linear RNN but can be stably approximated by rescaled linear RNN. (For rescaled linear RNN, one just need pick w 1.)
1
22

---

Published as a conference paper at ICLR 2024
repeat of
repeat "b"
10-1
10
mmnn wwmm wwwmmmm
10
10-1
10-1
10-1
20
40
60
80
1000
0
20
40 repeat
60
80
100
repeat of C
10-
10-2
My
10
W ww
10-3
10-1
10
10-a
20
60 repeat of "ha"
100
40 repeat of 'bad
10-1
10-1
10
10-1
10
repeat of 'yes"
20
30
repeat 'godd
10
25
30
10-
Memory of sertiment
10-2
10-1
10-2
10
10-1
10
15 times
20
25
30
0
10 15
20
Figure 6: Memory for sentiment scores based on IMDB movie reviews The z-axis is the inputs repeated times, which can be viewed as the input length. The y-axis is the derivative of sentiment score over repeated inputs, which is the memory of this sentiment analysis model. This tiny example implies that the memory function required in application can be in various patterns. The decaying pattern can be fluctuating in terms of the scale.
However, this rescaling does not work for all memory functions. Take the memory function p(f) E 42 # an example, may not be possible to stably approximate target with this memory
function with linear RNN or the rescaled version.
Based on the above argument, there does not exists a rescaled RNN that can work for linear func- tional with arbitrary memory function. In particular, it's always feasible to construct slow decay target that fixed rescaled linear RNN cannot stably approximate. This result indicates that rescaling is not an priori solution to achieve stable approximation. In practice, it's hard to get the memory function decay speed therefore it's impractical to use the rescaling method.
D NUMERICAL EXPERIMENTS DETAILS
Here we give the numerical experiments details for both the linear and nonlinear RNN experiments.
The linear functional approximation equiv- alent to the approximation of function p(t) by exponential sum c TeW For simplicity, we con- duct the approximation in the interpolation approach and consider the one-dimensional input and one-dimensional output case. Furthermore the least square fitting over the discrete time grid. We fit the coefficients of polynomial and evaluate the approximation error over [1, 2, .,., 100).
Linear functionals approximated by linear RNNs
reduce the approximation problem (numerically) into
23

---

Published as a conference paper at ICLR 2024
The exponential decaying memory function is manually selected show the significance across different hidden dimensions:
p(t) 0.9
(118)
while the polynomial decaying memory function is p(() (+41)HT The additional 1 is added require the memory function to be integrable.
The perturbation list 3 E [o, 5.0 10 5.0 * 10-4 2 ..... 5.0 * 10-4 220 Each evaluation of the perturbed error is sampled with 10 different weight perturbations to reduce the variance.
The approximation of linear functional by linear RNN has simple structures. So we did not use gradient-based optimisation. The approximation of linear functional via linear RNN is equivalent to the minimisation problem min.,w;r: [H, Hell, which can be simplified into the following function approximation problem min..w.U sup Jo (p(s)
e Ulds. After eigenvalue decompositions of W and change of variables, the above problem can be reduced to the polynomial approximation of function
In p over interval (0, 1]. Therefore we solve this approximation problem via linear regression instead of the gradient-ban badie optimisation. The code are attached in the supplementary materials.
Nonlinear functionals approximated by nonlinear RNNs Still, we consider the dimensional input and one-dimensional output case. We train the model over timestamp 0.2. .... 10.0).
(0.1,0.2, ... ... ..2.] and evaluate the approximation error over the same horizon 10.1,
In the experiments to approximate the nonlinear functionals by nonlinear RNNs, we train each model for 1000 epochs, the stopping criterion is the validation loss achieving 10-8, The optimizer used is Adam with initial learning rate 0.005. The loss function mean squared error. The batch size is 128 while the train size and test size are 12800.
The polynomial decaying memory function is p(t) = (f+1) equals to 1 at = 0. The only difference is the decaying speed.
The perturbation list 8 [0, 10-11 2", 10,11 21, .'..... 10-11 2 Each evaluation of the perturbed error is sampled with 3 different weight perturbations (and take the maximum) to reduce the variance of the perturbation error.
E ADDITIONAL NUMERICAL RESULTS
Curse of memory over ReLU activation Despite the activation relu is not smooth at (0)) O, numerically verify that the curse of memory phenomenon also holds. In Figure 7 the left RNN using ReLU cannot stably approximate target with polynomial memory while the RNN with Softplus reparameterization can stably approximate the target.
Stable e-parameterization as a potential solution In Figure we show that stable reparame- terization such exponential reparameterization and softplus reparameterization enables the stable approximation of linear functional with polynomial memory by linear RNNs. As shown in Figure g we further verify that stable re-parameterization enables the stable approximation of targets with polynomial decaying memory by hardtanb/tanh RNNs.
24

---

Published as a conference paper at ICLR 2024
Perturbation Emor for Different Hidden Dimensions
Hidden Dimension 8
10
Midden Dimension
Hidden
Hidden Dimersion 64
1044
10t
Perturbation enor
1015
10
Perturattion
Without reparameterization ReLU RNN
Perturbation Error for Different Hidden Dimensions
Hidden Dimension
Hidden Dimersion 16
Hidden Dimersion
10a
102
erior
10
-
10-
10-
10
10"
Perturbation
(b) Softplus reparameterization ReLU RNN
Figure 7: When the activation used is ReLU, vanilla nonlinear RNN does not have stable approxi- mation while the softplusRNN can be stably approximated.
25

---

Published as a conference paper at ICLR 2024
Perturbation Error for Different Hidden Dimensinns
Fidden Drowmssnn
10a
Hidden Dimension 16
Dimcnsion
101
Perurbatonn onur
10
10
10
10
10
20
10'
Pn
(a) Softplus reparameterization + Hardtanh RNN
Perturbetion Error Dimensions
Hiddew Dimensinn
10r
Hidden Dimonsion 16
Hidden Limens 32
Hidden Dimension 64
10
Nettrbation o7
105
10
10
10-
Pertmbatton
(b) Softplus reparameterization Tanh RNN
Figure 8: Linear functionals with polynomial memory can be stably approximated by hardtanh/tanh RNNs using Softplus parameterisation for W. These empirical findings underscore that stable pa- rameterisation is pivotal for attaining a stable approximation for targets with long-term memory. The experiments build upon and extend the results presented in Figure 4]
26

---

Published as a conference paper at ICLR 2024
porametentation-Direct parameterrtation-Exp
2.25
porameteriationninneer paramnttortationn-orppus
67-
1.75
art (veept
1.50
6.3
param eterization -Drect
1.00
param eteriiationnnnuurtt
Sof
500
1000
1.500
2000
S0o
1:00
1506
2000
Steps
Steps
(a) train loss
(b) train accuracy
2.4
paramiteriaationnDiinc parameterizationEEg paramaterrationnnnneers
67-
2.2
porammteeiaationnsotppss
0.6
Val lass (epoch)
1.4-
6.5
aCc
param eterizationnEss
1.8
param eterizationnSofttte
3.8
252
590
150
1000
1250
1520
1750
2003
230
500
750
1100
1250
1500
1750
2010
Steps
Steps
(c) validation loss
(d) validation accuracy
Figure 9: Image classification on MNIST. The performance of stable reparameterization is better than the direct parameterizatton of recurrent weight g (MM M. Under the same weight initializa- tion, the stable reparameterization can speed the optimization. The shadow corresponds to the standard error evaluated over repeats.
Test loss(std err)
Test accuracy (std err)
softplus (stable)
0.8903 (0.0004)
71.36(0.03)
exp (stable)
0.9028 (7.2E-05)
70.55(0.01)
inverse (stable)
0.9082 (0.0005)
70.77(0.05)
direct (unstable)
0.9177 (0.0105)
68.47(0.06)
Table Test loss and accuracy of different parameterization methods over MNIST
Stable e-parameterization facilitate the optimization In this subsection, demonstrate the optimization advantages provided by stable re-parameterization enhancing long-term memory learning. We train the nonlinear RNNs the MNIST dataset for 10 epochs. The models initialized with identical weight configurations, underscoring the impact of recurrent weight param- eterization. As illustrated in Figure the implementation of stable reparameterization significantly expedites the optimization process. Tr's important to note that this parameterization technique does not alter the inherent capacity of the model, resulting comparable final performance outcomes (Table I..
F
MEMORY FUNCTION DEFINED VIA IMPULSE INPUTS
Besides the Heaviside inputs, it's also feasible define the memory function via the impulse inputs.
Let Idd and consider the following impulse inputs input sequence i 0 +
Hereafter
27

---

Published as a conference paper at ICLR 2024
call the following memory function to be impulse-inputs induud- induced memory function.
(t) = sup
[1((1=)
(119)
10
In the linear functional case, notice that according to Equation 3
Hi( 00
x p(t)
sup #
sup 200
lp(t))
(120)
|0/00
Based on the peppuls-iinuus--nnddue memory function, if we assume this memory function and its derivative are decaying, then we have similar result as Theorem 3.9
Sketch proof for Theorem 3.9 based on impulse-input---nduee memory function Assume 3o is the stability radius, apply the proof of Theorem 3.9 we have for any 3 < Po
d M/2
lim
.x
+ O.
(121)
dl
Fix C O, there exists lo such that any 2 lo,
Ce-9t
Since the target has decaying
memory Yoo = lim y O. Then have
J. ds
lim e yool = lim 60000
Uodsl
(122)
100
J. Ce C
< lim 600
(123)
S co.
(124)
Therefore the memory function based the impulse inputs is also decaying exponentially.
lim St yel S C. t0
(125)
G MEMORY FUNCTION DEFINED VIA REVERSED INPUTS
x
t t< 0, Hereafter
Let Rd and consider the following reversed inputs input sequence rf
0 t2 0.
we call the following memory function to be impulse-inputs-ineee memory function.
(() = sup x
He(r")
(126)
a 00
dt
In the linear case, notice that according to Equation
3
Hr)
x T p(() = lp(())1-
sup
sup z70
(127)
|
0=
Based on the reversed-inputs-inddee memory function, if we assume this memory function and its derivative are decaying, then we have Theorem 3.9
Sketch proof for Theorem 3.9 based reversed-inputs--nnee
memory function
Assume
30 the stability radius, apply the proof of Theorem 3.9 we have for any B < 30
d
3r t-000
lim
y dt
+ 0.
(128)
Therefore the memory function based on the reversed inputs is also decaying exponentially. The memory function defined over reversed inputs can be harder to evaluate the outputs of different input sequences (x, 0, .......... (x, x, O..., 0), (x, x, x, O, ..... .,,....,,.. need to evaluated.
28

---

Published as a conference paper at ICLR 2024
Systied
16
kyen-3
Exme
10-
10-
momury
10-
memary
10-11
time
time
(a) RNN Heaviside memory
(b) RNN Impulse memory
38.
Syenet lyerrsn
16-
30-
mamory
20
10-
05
24
1:10
120
26
01
101
120
Emter
(c) GRU- Hcaviside memory
(d) GRU- Impulls memory
185
Syene
16-
16-1
menoryy
10
mamory
30-4
10-4
10-0
10-1
(e) LSTM Heaviside memory
(1) LSTM Impulse memory
10-
Ryyning
12-1
11-4
Pamoryy
10
memors- 8
20-4
20-
16-1
30:00 Lime
5.00
506
1000
Uime
(g) S4 Hcaviside memory
(h) S4 Impulse memory
Figure 10: Memory functions of randomly-initializee recurrent networks evaluated over Heaviside inputs and impulse inputs. The memory functions evaluated over different inputs are numerically equivalent. The shadow indicates the error bar for 20 repeats.
H QUALITATIVE EQUIVALENCE OF DIFFERENT MEMORY FUNCTION DEFINITIONS
Apart from the previous sections that study the equivalence of memory functions over linear func- tionals. In Figure 10 we show that the memorr9unctions evaluated over different test inputs

---

Published as a conference paper at ICLR 2024
qualitatively equivalent. Since the reversed inputs are harder to evaluate numerically, only com- pare the memory functions evaluated over Heaviside inputs and impulse inputs.
Besides the qualitative comparison that different memory functions are "cquivalent", here we show they all characterize the decay speed of the model's ' memory a impulse change at time t = O.
Relation between memory decaying speed and target dependence on early imputs An intuitive explanation is that current memory functions characterize how fast the memory about the sudden decays grows. Inputs such Heaviside inputs, reversed inputs, and impulse inputs all have this feature. Therefore the memory function evaluated over these inputs can be interpreted as measure for "dependence of the target function on early inputs".
input change
yr (i")
H1 (z.))
PT sup
sup
hmpulse-inputs-basse based memory
#
2
We show the "equivalence" of different memory functions in linear functional sense in Appendix and G. Since memory functions over Hcaviside imputs casier to evaluate numerically (as shown in Appendix H), we adopt the corresponding derivative form (as shown in Equation 5) to define the memory function.
Here we explain the reason that the memory function is evaluated over certain subclass of inputs rather than all continuous inputs:
Why special inputs A natural question is why we need a particular set of inputs rather than use any continuous input. The identity functional H₂(x) = zy takes the input sequence 2; 1, > to a polynomial decaying output y/+ = J. However, this does not mean the functional has a polynomial- decaying memory. In fact, this identity functional has no memory of past inputs in the sense that changing To does not influence the output of Ye with > 0. The above example indicates the selection of inputs to extract the memory pattern needs be chosen properly. This is also one of the reasons we select the Heaviside inputs as the test inputs to construct the derivative form.
I ADDITIONAL NUMERICAL RESULTS FOR THE FILTERING EXPERIMENT
In this section, we first show the existence of nonlinewar RNNs with non-decaying memory. There- fore in Figure we need to filter the targets. Then the example of learning transformer with nonlinear RNN is included. This example shows that transformer in general does not have decaying memory. Therefore the learning of transformer highly difficult that cannot achieve the approximation with 1000 epochs training.
1.1 EXISTENCE OF NONLINEAR RNNS WITHOUT DECAYING MEMORY
In Figure we show that filtering of nonlinear RNNs with stable approximation presents target with only exponentially decaying memory. Here we present in Figure II that nonlinear RNNs with randomly initialized weights have diverse memory patterns. Morcover, consider the following examples.
30

---

Published as a conference paper at ICLR 2024
10-1
memory function eva evaluated
10:2
10"
10
10
10
10
10a
10
10a
10a
Time t
(a) Examples of nonlinear RNNs have non-decaying memory
Trajectory hoddo states derivatives
1.5
10
05
(b) Example 2D RNN with periodic memory W
4
3
Figure 11: the left panel, we show the existence of tanh RNNs with non-decaying memory. In the right panel, we use specific 2D tanh RNN to show the existence of periodic trajectory. In the figure, [0, 0), [1, 1], [-1, -1] the attractor for the trajectories of (vI, (=a dhu,1 dha.2 di Therefore the boundary of the different converging set will be a periodic trajectory over the 2D plane. The periodic trajectory of hidden state derivative indicates periodic memory function.
1.2 FILTERING TOWARDS TRANSFORMER
Apart from the nonlinear RNNs targets, we also construct targets with polynomial decaying memory. It can be seen in Figure 12 that the transformers with non-decaying memory function cannot be stably approximated by tanh RNNs.
31

---

Published as a conference paper at ICLR 2024
10-1
10-2
10-3
20
40
60
80
100
(a) Memory function of the target randomly initialized transformer
Hidden Dimension
105
Hidden Dimension 16
Perturbation error
10
Hidden Dimension 32
Hidden Dimension 64
10a
10
10
10
10
10 4
10-3
10-2
10 11
10
Perturbation
(b) Inexistence of stable approximation
Figure 12: If the target functional does not have an exponentially decaying memory, then the targets cannot be stably approximated. The largest RNN with hidden dimension m 64 failed achieve an approximation error smaller than the case for 32 and m 16.
J DISCUSSION ON EXTENDING THE THEOREM 3.9TO GRU/LSTM
We will analyze GRU LSTM comes with more complicated structure. The classical GRU of the following structure:
2t (W + U,hh + bz),
(129)
rt (W,Ie + U,h,-1 br), h <(W,3, + Un(r: @ 14-1) + bn):
(130)
(131)
h2 (1 2x) ① h ① h4.
(132)
32

---

Published as a conference paper at ICLR 2024
Here is sigmoid activation and ø is the tanh activation. The hidden state equations can be refor-
mulated into
h4-1 + 24 O (he h4-1).
(133)
The corresponding continuous-time version be given by
dh
= @ (h+ - h
(134)
dt
=o(,, + Ugh+ + b.) o (he- hh)
(135)
=o(_ + U2h, + b.) @ (#(Wnar + Un(rs @ ha) + bn) 14))
(136)
- U2h, bz)
(137)
c (6(Wnzz+ Un + Uphe + b,) o he) + bb)) ht).
(138)
Let E Rd and we consider the Heaviside inputs u = x [(0,00)(t) (0 t << 0.
x
t z 0,
After change
of variable over the bias term b, == -, + bz, br = o + br, bn = W2 + bn. the corresponding hidden dynamics can be simplified into
dhe
=o(Uh b,)
(139)
dt
@ (UU, + b,) @ h4) + bn. - h4),
(140)
Notice that /² = 0 an equilibrium point by = 0:
a(b)) @ (Đ(U,. (a(b,) @ 0) + 0) 0)
(141)
Similar linearization can be utilized analyse the corresponding first-order system:
dhg = o ) (U,
(142)
dt
Our stable approximation argument be used to show Diag(o Blag(o((b)))( (iag((a(((b)) I) is Hur- witz. However, h²" = 0 might not be the only equilibrium point. Furthermore, when b, * 0, it's harder to find all equilibrium points therefore further analysis are needed.
33


Reviews:
[{"review_id": "88bDPNR93J", "reviewer": "Reviewer_NURo", "summary": "The authors provides an inverse approximation theory for a certain class of nonlinear recurrent neural network (RNN), showing that, for the class of nonlinear RNN to approximate the sequence, the sequence should have an exponential decaying memory structure. It demonstrates the difficulties of RNN in learning and representing a longer-time dependence in the data.", "questions": "NA", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is relatively well written and it extends the previous theories in linear RNN. While heuristically it is not difficult to show that a popular RNN, such as LSTM or GRU, has an exponentially decaying memory, by approximating the internal state of the RNN with a relaxation equation, this manuscript provides a robust proof about such behavior.", "weaknesses": "While it the manuscript is clearly written with well defined problem set up, my concern is the fit to the scope of ICLR. On one hand, I believe that the analysis and definitions provided in the manuscript can be of interest in developing theories about RNN. On the other hand, the scope of the manuscript is too narrow and it is unclear what insight this study provides to benefit a broader class of RNNs or Deep Learning in general. I believe that the authors need to consider giving more insights from their results for a broader context. The stable parameterization section is not very convincing. Can you give a more concrete example about the effects of the reparameterization? Possibly, using a dynamical system or real data?", "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": "", "extra_scores": {}}, {"review_id": "zJwK9K6L0T", "reviewer": "Reviewer_aNtd", "summary": "This paper demonstrates a Bernstein-type result for nonlinear Recurrent Neural Networks, meaning that it characterizes the type of functions that can be approximated by RNNs. The result shows that if a target sequence can be approximated by a RNN, then it has an exponentially decaying memory (for a notion of memory made precise in the paper). A similar result was proven in the literature for linear RNNs and this paper extends the result to the non-linear case.", "questions": "Do the authors think their proof technique could also be applied to LSTMs/GRUs? I imagine there would be many technical difficulties, but conceptually do the authors think it would be possible? Giving this insight in the paper might be interesting for readers.\n\nSee also weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well presented and pleasant to read. Extending previously known results to the non-linear case is interesting and brings added value. It gives a theoretical framework to understand the common saying that RNNs are unable to learn long-time dependencies in time series. A modification of the parametrization of RNNs is proposed to remedy this problem.\n\nTechnically, the paper introduces a new notion of memory that holds for nonlinear functionals and which extends the linear case, as well as a notion of stable approximation (which corresponds to the existence of a ball of parameters with uniformly good approximation properties). This proof technique is interesting and could perhaps be applied to other architectures.\n\nExperiments support the theoretical findings.", "weaknesses": "I have no strong reservations about the paper. I do have a question about Figure 3, which I did not understand. I am willing to raise the rating should this interrogation be answered. [Update on Nov. 18: the authors clarified this point in their comments below, and I updated my rating accordingly].\n\nI do not understand the filtering part of the experiment. Since we know from the theoretical results that RNNs can only represent exponentially decaying functions, the teacher models should all be exponentially decaying? So why is any filtering required? Furthermore, if indeed filtering is required, is it also performed before plotting the left-side plot? Otherwise we should be seeing some non-converging data points?\nAs a consequence, I am wondering if the takeaway of the experiment should be “stable approximation implies exponential decay” or rather “exponential decay implies stable approximation”.\n\n**Minor remarks that do not influence the rating**\n+ Page 5: I found the paragraph above Definition 3.2 hard to follow. I am not sure to understand the reason for introducing the terminology  “queried memory”. The experiments of Appendix B are important in my opinion because they suggest that RNNs may share the exponential decay property with LSTMs, but not Transformer. But I do not understand why they are introduced at this point in the paper, and not later on, e.g. in the conclusion.\n+ Page 7: the proof sketch is difficult to follow, and I am not sure it brings significant added value. If you need additional space in the main paper, I’d suggest putting the proof sketch in the Appendix just before the proof.\n+ Page 7, line -2: “In order” -> “in order”\n+ Page 8: “approaching 0” -> “approaching 0 on the negative side”?\n+ Page 8: “Take exponential…” -> “Taking exponential”\n+ Page 8, figures 2 and 3: please avoid using plus sign and arrow inside the text. Consider replacing it by “and” and “implies”.\n+ Page 16: “acivations” -> “activations”\n+ Page 16: could you briefly explain or give a reference for Lyapunov equations?", "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": "", "extra_scores": {}}, {"review_id": "DlFPNFP97G", "reviewer": "Reviewer_dqeg", "summary": "The paper introduces an inverse approximation theorem for non-linear recurrent neural networks, extending known, results for the linear case. After introducing new tools that enable analyzing nonlinear dynamics, it shows a somewhat negative result that nonlinear RNNs suffer from the same curse of memory as linear RNNs. Finally, the authors suggest a type of reparametrization that could possibly enable stability and good approximation properties.", "questions": "I am a bit confused with the Heaviside input at the end of Page 4. Intuitively, I would have put it the other way around: the network is submitted to an input $x$ until 0, and then evolves autonomously later. This would allow us to measure how fast the network forgets about $x$. Can you elaborate on the choice in the paper?\n\nThe reparametrization that you propose reminds me of the one used in the LRU architecture (Orvieto et al. 2023, ICML) and present in some deep-state space models (see references in the LRU paper), it may be nice to mention this. I’m not sure I fully understand what your theoretical results show for the reparametrization. To the best of my understanding, even with such a reparametrization, RNN would still only be able to learn in the same manner targets with decaying memory. Can you elaborate more on that?", "limitations": "", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "As an outsider to the field, the paper introduces/uses formal concepts that I find insightful:\n\n- The memory function that is used in the paper mathematically characterizes the intuitive behavior of RNNs.\n- The notion of stable approximation is an interesting proxy for how a function can be learned by gradient descent which, from my very limited knowledge, seems to be rare in approximation theory.\n\nOverall, I found overall the paper well written, in a way that is accessible to a decently large audience.", "weaknesses": "I am not qualified enough to identify the weaknesses of the paper.", "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": "", "extra_scores": {}}, {"review_id": "22szj8Qzry", "reviewer": "Reviewer_6cRG", "summary": "This paper investigates the inverse approximation theory for nonlinear recurrent neural networks (RNN) and extends the curse of memory from linear RNNs to nonlinear RNNs. The contribution of this paper can be summarized as follows.\n1. Authors define the memory of nonlinear RNNs, which is consistent with the memory of linear RNNs.\n2. Authors introduce a notion of stable approximation.\n3. Authors prove a Bernstein-type approximation theorem for nonlinear functional sequences through nonlinear RNNs, which says that if a target function can be stably approximated by nonlinear RNNs, then the target function must have exponential decaying memory.\n4. Based on the theoretical result, the authors propose a suitable parameterization that enables RNN to stably approximate target functions with non-exponential decaying memory.", "questions": "See weakness.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. To the best of my knowledge, this is the first paper studying the inverse approximation theorem for nonlinear RNNs.\n2. The approximation of neural networks determines the existence of a low-error solution and has been widely investigated. The inverse approximation theorem, which is harder and less studied, concerns the efficiency of approximation, which is a crucial aspect of utilizing neural networks in practice.\n3. The nonlinearity is of central interest in empirical implementations and requires more challenging proofs.", "weaknesses": "1. The definition of memory for nonlinear RNNs is consistent with that for linear RNNs, but the rationality of the proposed definition needs more explanations. The authors review the definition of memory for linear RNNs and observe that if the memory decays fast, then the target has short memory, and vice versa. The observation can be obtained directly from the definition and satisfies the intuition of memory. But for the memory for nonlinear RNNs, authors motivate it from a derivative form. This motivation is too mathematical and lacks an intuitive explanation. What is the relationship between the decaying speed of memory and the dependence of the target function on early inputs?\n2. The parameterization motivated by the theories should be explained in more detail. The parameterization is based on an important claim that the eigenvalue real part being negative leads to stability, which is not explained in section 3. This makes the logic in section 3.4 incomplete and the parameterization hard to understand. Can authors provide an intuitive explanation for this?\n----\nThe authors' answers are convincing and I have updated my ratings.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)