Inverse Approximation Theory for Nonlinear Recurrent Neural Networks
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. The code has been released in
https://github.com/radarFudan/Curse-of-memory
Shida Wang, Zhong Li, Qianxiao Li
# Inverse Approximation Theory for Nonlinear Recurrent Neural Networks

###### Abstract

We prove an inverse approximation theorem for the approximation of nonlinear sequence-to-sequence relationships using 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, viewed as functional sequences, that can be stably approximated by RNNs with hardtanh/tanh activations 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.

## 1 Introduction

Recurrent neural networks (RNNs) [1] are one of the most basic machine learning models to learn the relationship between sequential or temporal data. They have wide applications from time series prediction [2], text generation [3], speech recognition [4] to sentiment classification [5]. However, when there are long-term dependencies in the data, empirical results [6] 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 (7, p. 32) and Jackson-type theorem (7, p. 187) provide basic guarantees of approximation and error estimates of sufficiently regular target functions by a particular hypothesis space. A number of such results are available for sequence modelling, including the RNN [8, 9]. On the other hand, a relatively under-investigated domain in the machine learning literature are Bernstein-type theorems [10, 9], which are also known as inverse approximation theorems. These results aims to characterize the regularity of target relationships, assuming that they can be approximated efficiently with a hypothesis space. These regularity notions intimately depends on, thus gives important insights into, the structure of the hypothesis space under study.

This paper establishes a Bernstein-type result for the approximation of nonlinear functionals via RNNs. Previous works [8, 9] indicate that linear functionals that can be universally approximated by linear RNNs must have exponential decaying memory. This phenomena 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 a 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 [11]. Thus, it is worthwhile to investigate whether the linear Bernstein result generalizes to the case of approximating nonlinear sequence relationships with nonlinear RNNs. In this paper, we prove that nonlinear RNNs still suffer from a curse of memory in approximation. In particular, we show that nonlinear functionals that can be stably approximated by RNNs with hardtanh/tanh activations must have an exponential decaying memory structure. The notions of stable approximation and memory structure can be concretely defined. Our results make precise the empirical observation that the RNN architecture has inherent limitations when modelling long-time dependencies.

In summary, our main contributions are:

1. We extends the concept of memory function in the linear settings [8, 9] to the nonlinear setting. This memory function can be numerically quantified in sequence modelling applications.
2. We introduce a notion of stable approximation, which ensures that an approximant has the possibility to be found by a gradient-based optimisation 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 a sequence of \(d\)-dimensional vectors indexed by \(\mathbb{R}\), \(\mathbf{x}=\{x_{t}\in\mathbb{R}^{d}:t\in\mathbb{R}\}\), we denote the supremum norm by \(\|\mathbf{x}\|_{\infty}:=\sup_{t\in\mathbb{R}}|x_{t}|_{\infty}\). Here
\(|x|_{\infty}:=\max_{i}|x_{i}|,|x|_{2}:=\sqrt{\sum_{i}x_{i}^{2}},|x|_{1}:=\sum_{i }|x_{i}|\) are the usual max (\(L_{\infty}\)) norm, \(L_{2}\) norm and \(L_{1}\) norm. Notice that the bold face represents sequence while the normal letters are scalars, vectors or functions. Throughout this paper we use \(\|\cdot\|\) to denote norms over sequences of vectors, or function(al)s, while \(|\cdot|\) (with subscripts) is used to represent 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).

## 2 Related work

Various results have been established in RNNs approximation theory, see Sontag [12], Hanson et al. [13] and references therein. For unbounded input index sets, \(L_{p}\) approximation is established by Gonon and Ortega [14]. In Gonon and Ortega [15], the universal approximation theorem is constructed for functionals with fading memory in the discrete time setting. In Li et al. [8], 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 relevance is the Bernstein-type result proved in Li et al. [9], 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. In general sequence modelling with other architectures (see Jiang et al. [16]), forward (Jackson-type) approximation results have been obtained in a number of settings, including dilated convolutional neural networks [17] and encoder-decoder models [18].

The notion of approximation stability is one of the central concepts we exploit in this paper. We note that in classical approximation theory, stable approximation has numerous definitions depending on the setting [19]. For example, in nonlinear approximation [20], a stably approximating sequence \(\{H_{m}\}\) of \(H\) is one that satisfies \(|H_{m}|\leq C|H|\) for some absolute constant \(C>0\) and all \(m\). This approach is taken to show the non-existence of stable procedure to approximating functions from equally-spaced samples with exponential convergence on analytic functions [21]. This notion of stability is on the conditioning of the approximation problem. In contrast, our notion of stability introduced in Section 4.2 is more similar to a uniform continuity requirement. Pertaining to sequence modelling, a related but different notion of dynamic stability [22] was used to prove a Jackson-type results for universal simulation of dynamical systems. There, the stability is akin to requiring the uniform (in inputs) continuity of the flow-map of the RNN hidden dynamics. This is again a different notion of stability.
Problem formulation and prior results on linear RNNs

In this section, we introduce the problem formulation of sequence modelling as a functional sequence approximation problem. We pay particular attention to distinguish two types of results: forward (Jackson-type) and inverse (Bernstein-type) approximation theorems. For approximation theory in machine learning, most existing results focus on forward theorems. However, inverse approximation theorems are of significant importance in revealing the fundamental limitations of an approximation approach. The present 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 4.1. The relationship between memory and approximation is central to our results.

### The approximation problem for sequence modelling

The goal of sequential modeling is to learn a relationship between an input sequence \(\mathbf{x}=\{x_{t}\}\) and a corresponding output sequence \(\mathbf{y}=\{y_{t}\}\). For ease of analysis, we adopt the continuous-time setting in [8], where \(t\in\mathbb{R}\). This is also a natural setting for irregularly sampled time series [23]. The input sequences belong to the bounded input sequence \(\mathcal{X}=C_{0}(\mathbb{R}^{d})\). We assume the input and output sequences are related by a sequence of functionals \(\mathbf{H}=\{H_{t}:\mathcal{X}\mapsto\mathbb{R};t\in\mathbb{R}\}\) via \(y_{t}=H_{t}(\mathbf{x}),t\in\mathbb{R}\). The sequential approximation problem can be formulated as the approximation of the target functional sequence \(\mathbf{H}\) by a functional sequence \(\widehat{\mathbf{H}}\) from a model hypothesis space such as RNNs.

Forward and inverse approximation theorems.Given a hypothesis space \(\widehat{\mathcal{H}}^{(m)}\) of complexity \(m\geq 1\) (e.g. width-\(m\) RNNs), forward approximation theorems, also called Jackson-type theorems, bound the optimal approximation error \(\inf_{\widehat{\mathbf{H}}\in\widehat{\mathcal{H}}^{(m)}}\|\mathbf{H}- \widehat{\mathbf{H}}\|\leq C(\mathbf{H},m)\).

Inverse approximation (Bernstein-type) results are "converse" statements to Jackson-type results. From the starting assumption of the existence of efficient approximation for a given target \(\mathbf{H}\), Bernstein-type results deduce the approximation spaces that \(\mathbf{H}\) ought to belong to, i.e. it identifies a complexity or regularity measure \(C(\cdot)\) and show that \(C(\mathbf{H})\) is necessarily finite. Take the trigonometric polynomial approximation as an example, Bernstein [7, p. 187] proved that if \(\inf_{\widehat{H}\in\widehat{\mathcal{H}}^{(m)}}\|H-\widehat{H}\|\leq\frac{c} {m^{\alpha+\delta}}\), for all \(m\geq 1\) and some \(\delta>0\), \(c>0\), then \(C(H)=|H^{(\alpha)}|<\infty\), i.e. \(H\) must be \(\alpha\)-times differentiable with \(\delta\)-Holder continuous derivatives.

Bernstein-type inverse approximation results are important in characterizing the approximation capabilities for hypothesis spaces. For trigonometric polyno
mial example, it says that _only_ smooth functions can be efficiently approximated, thereby placing a concrete limitation on the approximation 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 - a notion that we will make precise subsequently.

### The RNN architecture and prior results

The continuous-time RNN architecture parameterizes functional sequences by the introduction of a hidden dynamical system

\[\begin{split}\frac{dh_{t}}{dt}&=\sigma(Wh_{t}+Ux_{t }+b),\\ \hat{y}_{t}&=c^{\top}h_{t}.\end{split} \tag{1}\]

Here, \(\hat{y}_{t}\in\mathbb{R}\) is the predicted output sequence value, and \(h_{t}\in\mathbb{R}^{m}\) denotes the hidden state. As a common practice, we set the boundary condition \(h_{-\infty}=0\).1 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,U,b,c)\), where \(W\in\mathbb{R}^{m\times m}\) is the recurrent kernel, \(U\in\mathbb{R}^{m\times d}\) is the input kernel, \(b\in\mathbb{R}^{m}\) is the bias and \(c\in\mathbb{R}^{m}\) is the readout. The complexity of the RNN hypothesis space is characterized by the hidden dimension \(m\). The nonlinearity arises from the activation function \(\sigma(\cdot)\), which is a scalar function performed element-wise, such as _tanh_, _hardtanh_, _sigmoid_ or _ReLU_. In this paper, we shall focus on the hardtanh and tanh activations as they are the most commonly used activations in RNNs. The hypothesis space of RNNs is thus the following functional sequence space

Footnote 1: This is consistent with practical implementations such as TensorFlow and PyTorch, where the initial value of hidden state is set to be zero by default.

\[\begin{split}\widehat{\mathcal{H}}_{\text{RNN}}^{(m)}& =\{\mathbf{x}\mapsto\mathbf{\hat{y}}\text{ via Equation }(\ref{eq:kernel}):\\ &\quad\quad W\in\mathbb{R}^{m\times m},U\in\mathbb{R}^{m\times d}, b\in\mathbb{R}^{m},c\in\mathbb{R}^{m}\}.\end{split} \tag{2}\]

Before presenting our main results, we review known Jackson and Bernstein-type results established for linear RNNs, corresponding to setting \(\sigma(z)=z\) and \(b=0\) in (1). We shall pay attention to the definition of memory for a target functional sequence, and how it relates to approximation properties under the RNN hypothesis space.

We begin with some definitions on (sequences of) functionals as introduced in [8].

**Definition 3.1**.: Let \(\mathbf{H}=\{H_{t}:\mathcal{X}\mapsto\mathbb{R};t\in\mathbb{R}\}\) be a sequence of functionals.

1. (**Linear**) \(H_{t}\) is linear if for any \(\lambda,\lambda^{\prime}\in\mathbb{R}\) and \(\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}\), \(H_{t}(\lambda\mathbf{x}+\lambda^{\prime}\mathbf{x}^{\prime})=\lambda H_{t}( \mathbf{x})+\lambda^{\prime}H_{t}(\mathbf{x}^{\prime})\).
2. (**Continuous**) \(H_{t}\) is continuous if for any \(\mathbf{x},^{\prime}\mathbf{x}\in\mathcal{X}\), \(\lim_{\mathbf{x}^{\prime}\rightarrow\mathbf{x}}|H_{t}(\mathbf{x}^{\prime})-H_{ t}(\mathbf{x})|=0\).
3. (**Bounded**) \(H_{t}\) is bounded if \(\sup_{\{\mathbf{x}\in\mathcal{X},\|\mathbf{x}\|_{\mathcal{X}}\leq 1\}}|H_{t}( \mathbf{x})|<\infty\).
4. (**Time-homogeneous**) \(\mathbf{H}=\{H_{t}:t\in\mathbb{R}\}\) is time-homogeneous (or shift-equivariant) if the input-output relationship commutes with time shift: let \([S_{\tau}(\mathbf{x})]_{t}=x_{t-\tau}\) be a shift operator, then \(\mathbf{H}(S_{\tau}\mathbf{x})=S_{\tau}\mathbf{H}(\mathbf{x})\)
5. (**Causal**) \(H_{t}\) is causal if it does not depend on future values of the input. That is, if \(\mathbf{x},\mathbf{x}^{\prime}\) satisfy \(x_{t}=x^{\prime}_{t}\) for any \(t\leq t_{0}\), then \(H_{t}(\mathbf{x})=H_{t}(\mathbf{x}^{\prime})\) for any \(t\leq t_{0}\).
6. (**Regular**) \(H_{t}\) is regular if for any sequence \(\{\mathbf{x}^{(n)}:n\in\mathbb{N}\}\) such that \(x_{s}^{(n)}\to 0\) for almost every \(s\in\mathbb{R}\), then \(\lim_{n\rightarrow\infty}H_{t}(\mathbf{x}^{(n)})=0\).

The works in Li et al. [8, 9] study the approximation of functional sequences satisfying Definition 3.1 by linear RNNs. A key idea is showing that any such functional sequence \(\mathbf{H}\) admits a Riesz representation (see Appendix A.1 and Appendix A.2)

\[H_{t}(\mathbf{x})=\int_{0}^{\infty}\rho(s)^{\top}x_{t-s}ds,\qquad t\in\mathbb{ R}. \tag{3}\]

In this sense, \(\rho\) completely determines \(\mathbf{H}\), and its approximation using linear RNNs can be reduced to the study of the approximation of \(\rho\in L^{1}([0,\infty),\mathbb{R}^{d})\) by exponential sums of the form \((c^{\top}e^{Ws}U)^{\top}\). An important observation here is that \(\rho\) captures the memory pattern of the target linear functional sequence: if \(\rho\) decays rapidly, then the target has short memory, and vice versa. The forward approximation theorem simply says that a target with exponentially decaying memory admits an efficient approximation using RNNs.

A natural question is whether linear RNNs can efficiently approximate targets without an exponential decaying memory. The Bernstein-type result in [9] answers this question. By assuming that a target functional sequence \(\mathbf{H}\) can be approximated uniformly by stable RNNs, then the memory of the target functional sequence must satisfy

\[e^{\beta_{0}t}|\rho(t)|_{2}=o(1)\text{ as }t\rightarrow\infty \tag{4}\]

for some \(\beta_{0}>0\). Just like the classical Bernstein theorem for trigonometric polynomials, this result effectively constrains the approximation space of linear RNNs to linear functional sequences with exponentially decaying memory. Together with the Jackson-type estimate, one concludes that efficient approximation by linear RNN is possible if and only if the target linear functional sequence has exponential decaying memory in the sense defined above. This was coined the "curse of memory" [8, 9] 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 a larger hypothesis space may relax such constraints. A significant challenge in the nonlinear setting is the lack of a Riesz representation result, and thus one needs to carefully define a notion of memory that is consistent with \(\rho\) in the linear case, but can still be used in the nonlinear setting to prove inverse approximation theorems. Moreover, we will need to introduce a 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.

## 4 Main results

In this section, we establish a Bernstein-type approximation result for nonlinear functional sequences using nonlinear RNNs.

We first give a definition of memory function for nonlinear functionals. 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 requirement from the perspective of approximation, but a desirable one from the view of optimization. Moreover, we show that any linear functional with an exponential decaying memory can be stably approximated.

Based on the memory function definition and stable approximation framework, we prove a Bernstein-type theorem. The theorem shows that any nonlinear functionals that can be stably approximated by general hardtanh/tanh RNNs must have an exponentially decaying memory, which confirms that the curse-of-memory phenomenon is not limited to the linear case.

Numerical verifications are included to demonstrate the result.

### Memory function for nonlinear functionals

Recall that the memory for a linear functional sequence is defined by its Riesz representation in Equation (3). While there are no known general analogues of Riesz representation for nonlinear functionals, we may consider other means to extract an effective memory function from \(\mathbf{H}\).

Let \(x\in\mathbb{R}^{d}\) and consider the following Heaviside input sequence \(\mathbf{u}_{t}^{x}=x\cdot\mathbf{1}_{[0,\infty)}(t)=\begin{cases}x&t\geq 0,\\ 0&t<0.\end{cases}\) In the linear case, notice that according to Equation (3)

\[\sup_{|x|_{2}\leq B}\frac{1}{B}\left|\frac{d}{dt}H_{t}(\mathbf{u}^{x})\right| =\sup_{|x|_{2}\leq B}\frac{1}{B}|x^{\top}\rho(t)|=|\rho(t)|_{2}. \tag{5}\]

Hence, conditions on \(|\rho(t)|_{2}\) may be replaced by conditions on the left hand side, which is well-defined also for nonlinear functionals. This motivates the following definition of memory function for nonlinear functional sequences.
**Definition 4.1** (Memory function of nonlinear functional sequences).: For continuous, causal, regular and time-homogeneous functional sequences \(\mathbf{H}=\{H_{t}(\mathbf{x}):t\in\mathbb{R}\}\) on \(\mathcal{X}\), define the following function as the _memory function_ of \(\mathbf{H}\) over bounded Heaviside input \(\mathbf{x}\):

\[\mathcal{M}_{B}(\mathbf{H})(t):=\sup_{|x|_{2}\leq B}\frac{1}{B}\left|\frac{d}{ dt}H_{t}(\mathbf{u}^{x})\right|,\quad B>0. \tag{6}\]

If the oracle of the target functional is avaiable, the memory function can be queried directly and the result is named queried memory. Without target functional oracle, we may approximate the target functional with the learned model and still evaluate the memory function. If the queried memory are decaying for all \(B>0\), 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 sequence-to-sequence models in sentiment analysis on IMDB movie reviews.

**Definition 4.2** (Decaying memory).: For continuous, causal, regular and time-homogeneous functional sequences \(\mathbf{H}=\{H_{t}(\mathbf{x}):t\in\mathbb{R}\}\) on \(\mathcal{X}\), we say it has a _decaying memory_ if:

\[\lim_{t\to\infty}\mathcal{M}_{B}(\mathbf{H})(t)=0,\quad\forall B>0. \tag{7}\]

In particular, we say a functional sequence \(\mathbf{H}\) has an _exponential decaying memory_ if for some \(\beta>0\),

\[\lim_{t\to\infty}e^{\beta t}\mathcal{M}_{B}(\mathbf{H})(t)=0,\quad\forall B>0. \tag{8}\]

We say a family of functional sequences \(\{\mathbf{H}_{m}\}\) has an _uniformly decaying memory_ if the memory functions for these functional sequences are uniformly converging to \(0\):

\[\lim_{t\to\infty}\sup_{m}\mathcal{M}_{B}(\mathbf{H}_{m})(t)=0,\quad\forall B>0. \tag{9}\]

_Remark 4.3_.: The requirement of decaying memory on time-homogeneous functionals is mild since it is satisfied if \(\frac{dH_{t}}{dt}\) is continuous at Heaviside input, under the topology of point-wise convergence. Another notion of fading memory is discussed in the Appendix A.3.

### Stable approximation

We now introduce the stable approximation framework. Let us write the hypothesis space \(\widehat{\mathcal{H}}^{(m)}\) as a parametric space

\[\widehat{\mathcal{H}}^{(m)}=\{\widehat{\mathbf{H}}(\cdot;\theta):\theta\in \Theta_{m}\} \tag{10}\]

where for each \(m\), \(\Theta_{m}\) is a subset of a Euclidean space with dimension depending on \(m\), representing the parameter space defining the hypothesis and \(\widehat{\mathbf{H}}\) is a
parametric model. For example, in the case of RNNs, the parameter \(\theta\) is \((W,U,b,c)\in\Theta_{m}:=\{\mathbb{R}^{m\times m}\times\mathbb{R}^{m\times d} \times\mathbb{R}^{m}\times\mathbb{R}^{m}\}\) and \(m\) is the hidden dimension of the RNN.

Let us consider a collection of functional sequences \(\{\widehat{\mathbf{H}}_{m}=\widehat{\mathbf{H}}(\cdot;\theta_{m}):m\geq 1\}\) serving to approximate a target functional sequence \(\mathbf{H}\). Stable approximation requires that, if one were to perturb each parameter \(\theta_{m}\) by a small amount, the resulting approximant sequence should still have a continuous perturbed error. For the gradient-based optimization, this condition is necessary for one to find such an approximant sequence, as small perturbations of parameters should keep perturbed error continuous for gradients to be computed. We now define this notion of stability precisely.

**Definition 4.4**.: For target \(\mathbf{H}\) and parameterized model \(\widehat{\mathbf{H}}(\cdot,\theta_{m})\), we define the perturbed error for hidden dimension \(m\) to be:

\[E_{m}(\beta):=\sup_{\tilde{\theta}_{m}\in\{\theta:|\theta-\theta_{m}|\leq\beta \}}\|\mathbf{H}-\widehat{\mathbf{H}}(\cdot;\tilde{\theta}_{m})\| \tag{11}\]

Moreover, \(E(\beta):=\limsup_{m\to\infty}E_{m}(\beta)\) is the perturbed error for a sequence of parameterized models with increasing hidden dimensions.

**Definition 4.5** (Stable approximation via parameterized models).: Let \(\beta_{0}>0\). We say a target functional sequence \(\mathbf{H}\) admits a \(\beta_{0}\)-stable approximation under \(\{\widehat{\mathcal{H}}^{(m)}\}\), if there exists a sequence of parameterized approximants \(\widehat{\mathbf{H}}_{m}=\widehat{\mathbf{H}}(\cdot,\theta_{m})\), \(\theta_{m}\in\Theta_{m}\) which are continuous (in input \(\mathbf{x}\)) in point-wise topology such that

\[\lim_{m\to\infty}\|\mathbf{H}-\widehat{\mathbf{H}}_{m}\|\to 0, \tag{12}\]

and for all \(0\leq\beta\leq\beta_{0}\), the perturbed error satisfies that \(E(\beta)\) is continuous in \(\beta\) for \(0\leq\beta\leq\beta_{0}\).

_Remark 4.6_.: It can be seen that approximation only requires \(E(0)=0\). Therefore the stable approximation condition generalizes the approximation by requiring the continuity of \(E\) around \(\beta=0\). If an approximation is unstable (\(E(0)=0,\lim_{\beta\to 0}E(\beta)>0\)), it is difficult to be found by gradient-based optimizations.

Next, we demonstrate that the stable approximation condition is not too stringent in the sense that, for linear functional sequence with exponential decaying memory (Equation (8)) admits a stable approximation. We show the numerical verification of this result in Figure 1. The approximation of linear functional with exponential decay can be seen in the left panel at \(\beta=0\) since increasing the hidden dimension \(m\) will make the estimated error decrease to \(0\) over \(\beta\in[0,\beta_{0}]\). Stable approximation can be verified that for positive perturbation \(\beta\), adding the hidden dimension does not increase the perturbed error \(E(\beta)\). In contrast, for linear functional with polynomial decaying memory, the perturbed error \(E(\beta)\) is not continuous at \(\beta=0\).
### Bernstein-type 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 of nonlinearity alleviates the curse of memory limitation and allows an efficient approximation of functionals with slow 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 hardtanh/tanh activations.

**Definition 4.7**.: Next we consider the Sobolev norm defined over \(W^{1,\infty}(\mathbb{R})\):

\[\left\|\mathbf{H}-\widehat{\mathbf{H}}\right\|_{W^{1}}=\sup_{t}\left(\|H_{t}- \widehat{H}_{t}\|_{\infty}+\left\|\frac{dH_{t}}{dt}-\frac{d\widehat{H}_{t}}{ dt}\right\|_{\infty}\right). \tag{13}\]

**Theorem 4.8**.: _Assume \(\mathbf{H}\) is a sequence of continuous, causal, regular and time-homogeneous functionals on \(\mathcal{X}\) with decaying memory. Suppose there exists a sequence of **hardtanh** RNNs \(\widehat{\mathbf{H}}=\{\widehat{\mathbf{H}}(\cdot,\theta_{m})\}_{m=1}^{\infty}\)\(\beta_{0}\)-stably approximating \(\mathbf{H}\) in the Sobolev norm defined in Equation (13)._

_Then, the memory function \(\mathcal{M}_{B}(\mathbf{H})(t)\) of the nonlinear functional decays exponentially for any \(\beta<\beta_{0}\):_

\[\lim_{t\rightarrow\infty}e^{\beta t}\mathcal{M}_{B}(\mathbf{H})(t)=0,\quad \forall B>0. \tag{14}\]

Figure 1: Perturbation errors for linear functionals with different decaying memory. The anticipated limiting curve \(E(\beta)\) is marked with a black dashed line. (a) For linear functional sequences with exponential decaying memory, there exists a perturbation radius \(\beta_{0}\) such that the perturbed error \(E(\beta)\) for \(0\leq\beta<\beta_{0}\) 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 a \(\beta_{0}\) achieving the stable approximation condition. The intersections of lines are shifting left as the hidden dimension \(m\) increases. The anticipated limiting curve \(E(\beta)\) is not continous for the polynomial decaying memory target.
The proofs are included in the Appendix A.4. A similar result can be proved for \(\tanh\) activation under more assumptions in Theorem A.6. We will briefly summarize the idea of the proof. Since the approximations are stable, consider \(\tilde{v}_{t}=\frac{d\tilde{h}_{t}}{dt}\), we know \(\lim_{t\to\infty}\tilde{v}_{t}=0\) over constant inputs. Furthermore, by Hartman-Grobman theorem we can get a bound on the eigenvalues of matrices \(W_{m}\) (with a sequence of perturbation \(\Delta W\)). Finally, since the models with uniformly exponential decaying memory can only approximate targets with exponential decay, we prove the memory function of the nonlinear target functionals must also be decaying exponentially.

Interpretation of Theorem 4.8 and Theorem A.6.Our main result (Theorem 4.8 and Theorem A.6) extends the previous result from Li et al. [9]. Instead of smoothness (measured by the Sobolev norm) as a regularity measure, the RNN Bernstein-type result identifies exponential decaying memory (\(e^{\beta t}\mathcal{M}_{B}(\mathbf{H})(t)\to 0\)) as the right regularity measure. If we can approximate some target functionals stably using hardtanh/tanh 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 fix the essential memory limitation of RNN.

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 a target functional sequence decays slower than exponential (e.g. \(\mathcal{M}_{B}(\mathbf{H})(t)=\frac{C}{(t+1)^{1.5}}\)), the optimization is difficult and the approximation in Figure 2 is achieved at 1000 epochs while typically exponential decaying memory achieves the approximation at 10 epochs. When the approximation is achieved, it can be seen in Figure 2 that, for larger perturbation scale \(\beta\), there is no perturbation stability. Second, if a target functional sequence can be well-approximated and the approximation's stability radius \(\beta_{0}\) 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 in Appendix B for the validation of memory over general sentiment classification task.)

### Suitable parametrization enables stable approximation

The key insight of Theorem 4.8 and Theorem A.6 can be summarized as follow: In order to approximate targets with non-exponential decaying memory, the recurrent weights of RNNs have to have eigenvalue real part approaching 0. If the eigenvalues are bounded away from zero, the target must be exponentially decreasing. However, if the largest eigenvalue real part are approaching zero, then its stability under perturbation will decrease, then we'll not have a finite limit. This is why the approximation and stability cannot be achieved at the same time if the target's memory does not decay exponentially.

If we can reparameterize the recurrent weights so that it can both approach zero and remain stable (i.e., eigenvalue real part being non-positive) under
perturbations, then this architecture will maintain stability while having the possibility of approximation. In general, we can achieve this by replacing recurrent weight by a continuous matrix function

\[g:\mathbb{R}^{m\times m}\rightarrow\mathbb{R}^{m\times m,-},\quad g(M)=W. \tag{15}\]

This reparameterized RNN is always stable as the eigenvalues' real part are always negative.

We show there are several methods to achieve this reparameterization: Take exponential function \(g(M)=-e^{M}\) or softplus function \(g(M)=-\log(1+e^{M})\) maps the eigenvalues of \(M\) to positive range (see Figure 4 for the stable

Figure 3: Approximation + stable \(\rightarrow\) Exponential decaying memory. We construct several randomly-initialized RNN models as teacher models with large hidden dimension (\(m=256\)). When approximating the teacher model with a 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 are stable (with perturbed error \(E_{m}(\beta)\) having a positive stability radius). We found that the only teachers that remain are those with exponential decaying memory functions. An example of corresponding is shown in the right panel.

Figure 2: Polynomial decaying memory + approximation (achieved at 1000 epochs) \(\rightarrow\) 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.
approximation of linear functional with polynomial decay memory). Project map \(W=g(M)=\arg\min_{W\leq 0}\|W-M\|_{2}\) is another option to keep the recurrent matrix stable. A slightly different exponential parameterization idea is empirically investigated in Lezcano-Casado and Martinez-Rubio [24].

## 5 Conclusion

In summary, we derive the first known Bernstein-type result in the setting of sequence modelling using nonlinear RNNs. We show that, assuming that a given target sequence relationship (mathematically understood as a nonlinear functional sequence) can be stably approximated by RNNs with hardtanh/tanh activations, then the target functional sequence's memory structure must be exponentially decreasing. This places a priori limitations on the ability of RNNs to learn long-term memory in long sequence modelling problems, 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 the RNN hypothesis space. This points to a principled approach to achieve stable approximation. At the same time, our analysis points to reparameterization as a principled methodology to remedy the limitations of RNN when it comes to long-term memory and we demonstrate it's effectiveness in by learning linear functionals with polynomial memory.

## 6 Acknowledgements

This research is supported by the National Research Foundation, Singapore, under the NRF fellowship (project No. NRF-NRFF13-2021-0005).

Figure 4: Stable approximation of linear functionals with polynomial decay memory via exponential reparameterization and softplus reparameterization. It can be seen the limiting curve \(E(\beta)\) shall be continuous.