State-space models with layer-wise nonlinearity are universal approximators with exponential decaying memory
Authors: Shida Wang
Beichen Xue
Venue: NeurIPS 2023 poster (2023)
Keywords: state space
approximation theory
sequence modelling
TL;DR: State-space models with layer-wise nonlinearity are universal approximators

Abstract: State-space models have gained popularity in sequence modelling due to their simple and efficient network structures. However, the absence of nonlinear activation along the temporal direction limits the model's capacity. In this paper, we prove that stacking state-space models with layer-wise nonlinear activation is sufficient to approximate any continuous sequence-to-sequence relationship. Our findings demonstrate that the addition of layer-wise nonlinear activation enhances the model's capacity to learn complex sequence patterns. Meanwhile, it can be seen both theoretically and empirically that the state-space models do not fundamentally resolve the issue of exponential decaying memory. Theoretical results are justified by numerical verifications.

State-space Models with Layer-wise Nonlinearity are Universal Approximators with Exponential Decaying Memory
Shida Wang Department of Mathematies National University of Singapore e0622338cu. nus edu
Beichen Xue
Department of Statistics and Data Science National University of Singapore e07737690u, nus. edu
Abstract
State-space models have gained popularity in sequence modelling due to their simple and efficient network structures. However, the absence of nonlinear ac- tivation along the temporal direction limits the model's capacity. In this paper, we prove that stacking state-space models with layer-wise nonlinear activation sufficient to approximate any continuous sequence- cociccettt--oppee to-sequence relationship. Our findings demonstrate that the addition of layer-wise nonlinear activation enhances the model's capacity to learn complex sequence patterns. Mcanwhile, it can be seen both theoretically and empirically that the state-space models do not fundamentally resolve the issue of exponential decaying memory. Theoretical results are justified by numerical verifications.
Introduction
State-space model 1+5 is an emerging family of neural networks specialized in learning long sequence relationships. achieves significantly better performance compared with attention-based transformers in the long range arena (LRA) dataset [6] 77. Despite its effectiveness. the state- space model is built on a relatively simple foundation of Linear-RNN-lis layers. One of the key advantages of state-space models is their simple recurrence, which enables efficient acceleration. In fact, this recurrence allows for an asymptotic computational complexity of only O(T log T), which is significantly better than the ( complexity of traditional full-attention approaches B natural question would be whether SSM achieves this speedup with certain sacrifices in model capacity or memory property. It is currently unclear whether the state-space model's linear architecture with layerwise nonlinearity possesses sufficient expressive capacity to approximate any target sequence-to- sequence relationship. This knowledge would be important answer pertinent questions regarding the model's ability to handle the complexity of real-world datasets characterized by diverse and intricate sequence relationships. In particular, considering the speed advantage of SSM over attention- based transformers, the universal approximation property impacts whether state-space model could be a suitable replacement for a transformer.
In this paper, we study the universality of state-space model. Furthermore, the memory property is investigated and we show that state-space models also have an asymptotically exponential decaying memory.
The main contributions can be summarized as follow
1. We give constructive proof for the universal approximation property for multi-layer state- space models. The width dependency on sequence length analyzed.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Temporal direction
22
323
2T
recurrent actiyation
(1)
(1)
h
ft2
h
hT
Depth direction
Layer-wise nonlinearity
h
(2)
h
(2)
h
(2)
h
3/1
1/2
y/3
yr
Figure 1: Network structure of two-layer state-space model.
2. The state-space models are shown to have an exponentially decaying memory, which coincides with usual recurrent neural networks.
3. Numerical verifications for the memory property are given on synthetic datasets.
Background
In this section, we introduce the general form of the state-space models. The classical results universal approximation for recurrent neural networks are summarized, Based on the approximation result, the well-documented challenge of learning long-term memory via recurrent networks is summarized. In particular, we give the definition of memory function which we shall use in the derivation of memory decay.
2.1 State-space models
Single-layer state-space model can be viewed as a recurrent neural network without nonlinear recurrent activation. As is shown in Figure the discrete time version of SSM 9 is
hx+1 = Whh + U2E+1,
ho =
yk Chi + Drc CW*
CWk-iUs Drk.
where x E Rddi,, y E BRdout h E Rm, W E Rmxm U RRdd C Rdeux xm, E Rdous Notice that drop the bias term for simplicity. For multi-layer state-space model, the nonlinear activation is added layer-wise.
The continuous time version of a single layer is
dhe Wh, + Uni,
ho =
(3)
dt
V: Ch. + Dx, (' Ce Co + Dzy.
(4)
can be seen in Equation that the first component of output y is the convolution between kernel function p(t) (t and æ. discrete case, the convolution operator * represented by
Vo.T = p(t) * Flo. + U/
(5)
Compared with temporal convolution network (TCN) 100, which has finite kernel size, state-space models can be regarded as implementing global convolution (p(t) Ce (r-s)) > 0) over the

---

temporal axis. Numerically, since the kemel size is the same as the sequence length, the convolution implemented via fast Fourier transform can lead to significant accelerations [T]. Compared with attention-based transformer, it is shown that SSM can speed up the training 100x in learning sequences with length 64K [12]. The state-space model's s temporal efficiency is achieved by eliminating the nonlinear activation function in its recurrent layers hg+1 = Whg + Urz + b, resulting in faster processing of sequential data via parallel sean [[]]
2.2 Universal approximation in RNN
It is long-knon long-known that recurrent neural networks with nonlinear sigmoidal activations (such as tanh and sigmoid) are universal approximators.
Theorem 2.1 (Simplified universality statement). For any sequence sequence map: H - y and tolerance there exists a hidden dimension m and weights c, W. U, b such that the RNN with weights (c, W, U,b) b) can approximate the target sequence to sequence map:
11
511 SE
(6)
where prediction sequence ý is given by
hx+1 = o oWh; + Un + b),
(7)
9k = C h4-
(8)
Universal approximation establishes the feasibility of learning sequence to sequence relationships via recurrent neural networks. However, typical approximation rate results depend on the sequence length [3]. Sequence length dependent approximation rate does not generalize to the case of sequence of infinite length. In learning sequences with infinite length, Li et al. [14] shows that linear RNNs have difficulty in learning non-exponential decaying memory. Various numerical experiments [[5] confirm that adding nonlinear recurrent activation does not fundamentally change the decay. In state-space models, the nonlinearity is included in a layer-wise approach. is unknown whether such layer-wise nonlinearity alone is sufficient to approximate any sequence to sequence relationships.
2.3 Memory function and curse of memory
In this paper we study the memory property of state-space model. Before we introduce the main results, we present simple memory function definition in sequence modelling. Li et al. [044 proves that bounded causal continuous regular homogenoogsssous linear functional has the following Riesz representation:
1
V/ H+(x)
p(t s)x,ds.
Here p: p IR is an -i-integrable function. If Pr rapidly decreases with 1, then the target sequence relationship has short-term memory.
Since Pe fully captures the memory property of linear functional 14, we call it the memory function (of the linear functional). In particular, when approximating the linear functional with linear RNNs, the model's 's memory function is p(t - s) = C (t-s))
The curse of memory refers to the phenomenon that if a target linear functional can be approximated by a sequence of linear RNNs, the memory function or decays exponentially.
{
t 0, Notice that the derivative of the linear functional at <<0.
Take the test input to be Xtest
test input extracts the memory function dt H2 lp())]2 Therefore natural extension of the memory function [16] the bounded causal continuous regular time-homogeneuus nonlinear
functionals will be:
die dt
P(()
H, (Xtet).
(10)
It can be seen this definition is compatible with the memory function definition of linear functional. Also, this memory function can be evaluated by computing the models' derivative the test input using finite difference method.
3

---

21
22
4/3
2T
1
(1)
h0
hg
())
T
(1)
h = U2 + bj
h
(2)
hz
(2)
hg
(2)
hT
(2)
h h411 (20
1/1
1/2
y/3
yT
yk+1 1000=0(0U10 +
Figure 2: Two-layer state-space model can approximate any continuous element-wise function
Main results
In this section, first give simple constructive proof to show that any element wise function on imput sequence can be approximated by a two-layer state-space model. Next, we show any temporal convolution can be approximated nonlinear sequence to sequence functional is given based on the above propositions. Moreover, as the watrggoooo--mmoooodrrrreeeeeaaae
state-space model. The constructive proof for general
construction has weight number dependent sequence length, can be highly inefficient to construct shallow wide network to learn long sequences. To reduce the widths dependency on the sequence length, Sotteraa-serees-bseed construction is demonstrated.
3.1 Two-layer SSM approximates element-wise function
By element-wise function, we mean learning sequence relationship with form (ei,...,.77) ((,))...,,,(TT))
Proposition 3.1. For any given continuous function f over a compact set K, let the activation be sigmoidal function. functiio..
lim 11 lim a(2) -.
(11)
There exists sequence of two-layer state-space model with weights {W1, W2, U1, U2, b1, b2 that can approximate sequence relationship H
+ (yI...., MT.)
sup [((x - y Sc.
(12)
Here the two-layer state-space model is constructed by
( = Win + U1 + b,,
(13)
Ak+1 W2h (2) + U20 - b2
(14)
(2)
yk
(15)
The proof is included in Appendix B.2
The main idea approximate clement-wise function f() with (21 + b1). A graphical demonstration is given in Figure 2, It can be seen the two-layer state-space model can approximate any element- wise function by setting W, W2 bz
3.2 SSM approximates temporal convolution
In this part we show that state-space models can approximate temporal convolution: y = E Pk- < k < T. According to Equation (3) the hidden state of SSM is the con- volution between input sequence and exponentially decaying function Pa = CW 2k Et CWk- CW*hg D

---

Therefore the approximation problem of temporal convolution by state-space models is reduced the approximation problem of general convolution kernel Pk. I k T by exponentially decaying convolution kernel PR. 1 S k < T. The optimal weights are defined by C, C,W,U arg min,;w;U sup; IPt- CW*UI.
Proposition 3.2. For any given convolution kernel Pk. pk. T, the single-layer state-space model is universal approximator for temporal convolution.
In other words, for any O, there exists hidden dimension and corresponding weights C, W, such that Pk = CW*U satisfies
sup
Pk
(16)
See Appendix B.3 for the proof. The main idea is to represent the single-layer state-space model output as convolution between input and kernel function. The approximation of temporal convolution is then reduced to the approximation of general kernel with the SSM-induced kernels.
Remark 3.3. Although the Proposition 3.2 indicates that we can single-layer sate-space model to approximate any convolution, it does not reveal the necessary hidden dimension m for such approximation.
3.3 Universality of SSM
Now we show that five-layer state-space model universal. Without loss of generality, assume the output y onc-dimensional. The main proof is based on the famous colmogorov-Amold repre- sentation theorem [7].. By Kolmogorov-Amoll representation theorem, we know any multivariate continuous function f Rd > R can be represented by
2d
d
f(e f
xd)
4
Σ
@pp(op)
(17)
Remark 3.4. George Lorentz 18 shows that we can use the same Φ: f(r1..... .a)
Eg + (Ep= (n Sprecher
19 proves that it can be further reduced to the same di
f(21...., Id) = Eg 4 (Epz Sp==>>p<E + mp) + Cq) Braun and Griebel 20 gives the first con- structive proof for the superposition. Moreover, the inner function shown to be independent of target function f. It means the learning of function ó can be approximated without retraining for different target functionals.
summarize the Kolmogorov-Armold theorem as follow:
Theorem 3.5
[17 20
Fix dimension d 2 There are real numbers a, bp: Cq. and continuous
and monotone function & E + 12, such that for any continuous function f [0, 1]d + R. there
exists a continuous function 4 IR + R with
2d
[(I x.)
+
Σ bpo(u ga) + cg
(18)
Proposition 3.6. For any bounded causal continuous sequence to sequence relationship (æx 1k=1 + {yk Vi= and tolerance >> O, there exists hidden dimension and correspond- ing state-space model (as constructed in Figure such that the ervor of approximation
lyk
UKl S, (1......,
(19)
See the proof in Appendix B.4 The main idea is demonstrated in Figure 3 the nonlinear functions are separately approximated by two-layer state-space model. Remark 3.7. The Kolmogorov theorem provides a construction for achieving universality in five- layer state-space model. However, the quantity of hidden neurons increases linearly with the sequence length. This can become exceedingly burdensome when the sequence length escalates.
Another approach is from the perspective of Volterra Series, which features the sequence-length independent neurons.
5

---

"1... E R Txdia
9
==
2T dm
+ 9a
37
37 +
27
Element-wise function
de +.0
de oz)
Ka+ o4)
Ke++ oa)
d( o0)
dim
2
din
Σ resdiau on)
Σ + 00)
Σ Prudimee oo)
3 hredie ool
Σ Sbuttlest + 98)
Audley go)
Convolution
7-
T da
T du
6 + aq)
(azs aq)
1-1
I- 6-1
+
Element-wise function
badlay oz) H4)
budlas + og) -4
VD....
Figure 3: Multi-layer state-space models are universal approximators: Drawing from the Kolmogorov-
Armold representation theorem, we have f Fa) = Ege +b
[Ep ( bpo(I, + qa) + Cg)
Here, both element-wise nonlinear functions & and can be approximated by a two-layer state-space model, as shown in Proposition 3.1. Additionally, the temporal convolution is represented by single-layer state-space model, as detailed in Proposition 3.2.
Theorem 3.8 ((21). For any continuous time-invariant system with xx1) as input and y(t) as output can be expanded in the Volterra series as follow
1''
v(1) - ho Σ
h (T (T
Tnd II
x(1 Tj)d
(20)
n=
j=1
In particular, we call the expansion order N be the series' order.
simplified interpretation of the N-th Volterra Series expansion is the "N-th Taylor expansion the sequence variable x".
Proposition 3.9. For any bounded causal continuous time-homgeneous sequence to sequence relationship H {xx)T=1 {yk)T_ and tolerance >> O, there exists hidden dimension and corresponding state-space model (as constructed in Figure such that the error of approximation
lyk - Uul S,
t (T..
(21)
Moreover, the neurons of the state-space model do not explicitly depend on the sequence length T.
The main idea to approximate the convolution kernels hn (Ti...., Fr) by the low-rank tensor product of first-order convolution kemnl.
See the proof in Appendix B.5

---

X = [1TTT)
SSM, P1
SSM, P2
SSM, Ps
P1 * x
P2 x
P3 * x
Element-wise product
(0l x) (02 x)
Element-wise product
(P1 * x) (p2 * x) (p3 * x)
Linear combination
V1:71
Figure 4: Volterra-series-yye construction for state-space models
Remark 3.10. The advantage Volterra-series-tye series-tteeee construction is the approximation of the convolu- tion kernel with SSM-induced kernel as well as the approximation of multivariable convolution kernel with tensor product one-dimensional convolution kernel do not explicitly depend on the sequence length. Similar approaches have been adopted by idea of implicit convolution in CKConv [22
3.4 Memory decay of SSM
In the ensuing discourse, we turn our focus towards an examination of the memory property inherent in state-space models. It has been thoroughly studied in literature that recurrent neural networks exhibit a phenomenon of exponential memory decay [14). An intriguing question that naturally arises in this context is whether state-space models plagued by similar challenges. Upon careful investigation, it is concluded that state-space models, much like their neural network counterparts, do possess an asymptotically exponential decaying memory.
Proposition 3.11. Assume there exists a constani Co > 0 such that
lim co c000 - x01| + 0. = lim Tt- 1-500
(22)
t-00
Assume the output yt is the output of single-layer state-space model with parameters C, W, U. Then, for the same constant co, if the output's derivative satisfies dy dt
lim eo Ily, v"
0.
(23)
At the same time, general smooth nonlinear activation does not change the exponential decay property of sequence:
Proposition 3.12. Assume there exists a constant > 0 such that
lim e - x= + 0, x" = lim Tt-
(24)
1
t-000
For given Lipschitz continuous layer-wise activations there exists a positive constant such that dyr + 0 dt
the output memory function
lim c0ol ecollly y" +
(25)
14000
7

---

See the proofs for above two propositions in Appendix B.6 and Appendix B.7
Based the above propositions, by induction have the following theorem:
Theorem 3.13. Assume H is multi-layer state-space model with Lipschitz continuous function as the layer-wise activations. Assume the state-space model is stable the sense that matrix W's eigenvalue are bounded by I.
There exists a positive constant co such that the memory function (defined Equation 10p of
state-space model is decaying exponentially
lim e00 e(t)p(t) + 0. 4-000
(26)
4 Numerical verifications
Based on the generalization of memory function p in linear functional, we verify the asymptotic memory decay of state-space models with simple randomly generated models. The definition is given one-dimensional case, but can generalized to multi-variable case by taking different unit inputs in various coordinates. The motivation for the above definition is based on the idea of measuring the earlier input at the later output.
In our experiment, we construct various RNN models and SSM with random generated weights. can seen in Figure 5 that the memory of naive state-space models also has an exponentially decay memory. It is consistent with the previous theorem that state-space model has an asymptotic exponentially decaying memory. Notice that here the naive SSM is simply adding a tanh activation across layers without specially tuning the weights. Such random initialization can expose the memory issue more significantly as the $4 layer constructed with several parameterization techniques. However, the manually constructed S4 still has asymptotic exponential decaying memory as is shown in Figure
Related Work
In this section, we introduce the previous works on state-space models. As the single-layer state- space model is a linear RNN, we summarize the related approximation work RNN. In particular, the approximation result and memory result emphasized as this paper works on the universal approximation property and memory decay property of SSM.
State-space models State-space models originate from the HIPPO matrix which optimal in the online function approximation sense 42 The Hippo matrix initialization for recurrent matrix W enables the state-space model to have a slow decaying memory. The universal approximation idea heuristically demonstrated in Orvieto al.
(23) However, the proof from the Koopman theory perspective only guarantees the existence of universal approximation. Our proof is a constructive proof which can be further generalized study the approximation rate with respect the hidden
dimensions and network depths.
Recurrent neural networks Recurrent neural networks (RNNs) 24 are one of the most popular neural networks for sequence modelling. Various results have been established in RNNs approx- imation theory, see Sontag (25), Hanson et [3]. Apart from the universal approximation, the exponential decaying memory property is the notorious phenomenon in recurrent neural networks which prohibits the scale up of the models in terms of the sequence length [14 26
Discussion
In Table we compare the classical sequence models including RNN, TCN and attention-baser transformer. The state-space model can be considered as an enhancement of Recurrent Neural Networks (RNNs) due to its superior optimization and inference speed. Despite maintaining a similar network topology, inference cost, and memory pattern, it provides more efficient and streamlined approach. The effort to extend the long-memory learning is also carried out in convolutional networks and attention- based transformers. Romero et al. [22] proposes to parameterize the convolution

---

197
11-
10-
memory
107
10:0
10
22:41
G3
120
20
46
26
100
150
time
time
(a) RNN
(b) GRU
10-1
Roertel
15a
15"1
mamory
16-
22
20
65
160
126
23
45
100
120
time
time
(c) LSTM
(d) Naive SSM
Figure 5: Memory functions of a randomly initialized recurrent networks. The shadow indicates the error bar for 100 repeats.
kernel implicitly, which utilizes the power of spline function approximation y = Win(wo(W' + b)). Similar idea has been adopted in Poli et al. [12]. To summarize, regard SSM, CKConv and linear transformer as the sequence models' improvement in learning long-memory for long sequences.
Comparison of sequence models: T the sequence length, L is the number of layers, m is the hidden dimension, C' and K are the total number of channels and convolution kernel sizes in TCN. Input and output dimensions are dingut and dompput- Despite TCN's inference cost is independent of sequence length, it depends on the kernel size K, which typically bears a similar scale to T.
Table 1:
RNN
TCN
Transformer
Number of weights Single-step inference cost Memory pattern Memory improved version
Lm(m + dinpat + doutpa) O(1) exponential decay
LCK LCKdi diaput 0(1)
3Lmdhppu O(T2) no restriction Linear Transformer
low rank
SSM
CKConv
7 Conclusion
In this paper, we give a constructive proof for the universal approximation property of multi-layer state-space models. It is shown that the nonlinear recurrent activations in classical recurrent neural networks are not necessary when there are nonlinear activations across different hidden layers. This result implies state-space model is as powerful as the classical recurrent neural networks in the approximation sense. Furthermore, we study the memory decay in multi-layer state-space models, which is notorious issue in classical recurrent neural networks. While empirical evidence suggests

---

10
layers=1
layers=2
layers=3
10-2
10-3
memory p
10-4
10-5
10
10-7
10 8
500
1000 time t
1500
2000
Figure 6: Memory function of randomly initialized S4. For each model, as the time increases, the memory function can be "capped" by a straight line, which indicate that the memories are decaying exponentially. Compared with Figure ((d)) the results indicate that the smart initialization from S4 provides the memory function with slower decay,
that state- space models do not experience significant memory decay, they nonetheless exhibit memory pattern that decays exponentially
asymptotic sense.
Our research has exciting implications for future work in state-space models. By extending our work the approximation rate of state-space models, we can obtain better understanding of state-space models' hypothesis space. Such result is important to further optimize the architecture in various real-world applications. We aim unlock the full potential of state-space models by identifying the ideal network structure (including depth and hidden dimension) for specific tasks and applications.
10

---

References
[1] V. Siivola and A. Honkela. A state-space method for language modeling. In 2003 IEEE Workshop on Automatic Speech Recognition and Understanding (IEEE Cat. No.03EX721), pages 548-553. St Thomas, VI, USA, 2003. IEEE. ISBN 978-0-7803--988-0. doi: 10.1109/ ASRU.2003.. 188499.
[2] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. HiPPO: Recurrent Memory with Optimal Polynomial Projections. In Advances in Neural Information Processing Systems, volume 33, pages 1474-1487. Curran Associates, Inc., 2020.
[3] Jimmy T. H. Smith, Andrew Warrington, and Scott Linderman. Simplified State Space Layers for Sequence Modeling. International Conference on Learning Representations, February 2023.
[4] Daniel Y. Fu, Tri Dao, Khaled Kamal Saab, Armin W. Thomas, Atri Rudra, and Christopher Re. Hungry Hungry Hippos: Towards Language Modeling with State Space Models. In The Eleventh International Conference on Learning Representations, February 2023.
[5] Junxiong Wang, Jing Nathan Yan, Albert Gu, and Alexander M Rush. Pretraining without attention. arXiv preprint arXiv:22/2.10544 2022.
[6] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long Range Arena : A Benchmark for Efficient Transformers. In International Conference on Learning Representations, January 2021.
[7] Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the Parameterization and Initialization of Diagonal State Space Models. Advances in Neural Information Processing Systems, 35:35971-35989 December 2022.
[8] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[9] Albert Gu, Isys Johnson, Aman Timalsina, Atri Rudra, and Christopher Re. How to Train your HIPPO: State Space Models with Generalized Orthogonal Basis Projections. In International Conference Learning Representations, February 2023.
[10] Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv: 1803002/0 2018.
[11] Eric Martin and Chris Cundy. Parallelizing Linear Recurrent Neural Nets Over Sequence Length. In International Conference on Learning Representations, February 2018.
[12] Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y. Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Re. Hyena Hierarchy: Towards Larger Convolutional Language Models. In International Conference on Machine Learning, June 2023.
[13] 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, pages 425 425- PMLR, May 2021.
[14] Zhong Li, Jiequn Han, Weinan E, and Qianxiao Li. Approximation and Optimization Theory for Linear Continuous-TT Time Recurrent Neural Networks. Journal of Machine Learning Research, 23(42):1-85, 2022. ISSN 1533-7928.
[15] Y. Bengio, P. Simard, and P. Frasconi. Learning long-term term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157-166, March 1994. ISSN 1941-0093. doi: 10.1 1,.1109972.299881
[16] Shida Wang, Zhong Li, and Qianxiao Li. Inverse approximation theory for nonlinear recurrent neural networks. arxiv preprint arXiv:2305. 2023.

---

[17] A. N. Kolmogorov. On the representation of continuous functions of many variables by superposition of continuous finctions of one variable and addition, volume 28, pages 55-59. American Mathematical Society, Providence, Rhode Island, 1963. ISBN 978-0-8218--7722 978-1-4704-323--3 doi: 10. 10.10900rran22/028444.
[18] Lothar Collatz and Werner Krabs. Approxiimationstheorie:: Tschebbscheffschee Approximation mit Anwendungen. Springer- Opringer-Verlag, April 2013. ISBN 978-3-322 94885-4.
[19] David A Sprecher. ON THE STRUCTURE OF REPRESENTATIONS OF CONTINUOUS FUNCTIONS OF SEVERAL VARIABLES AS FINITE SUMS OF CONTINUOUS FUNC- TIONS OF ONE VARIABLE. Proceedings of the American Mathematical Society, 1965.
[20] Jürgen Braun and Michael Griebel. On a Constructive Proof of Kolmogorov's Superposition Theorem. Constructive Approximation. 30(3):653-61) 675, December 2009. ISSN 0176-4276, 1432-0940. doi: 10.1007/s00365-009 00..0009--92222
[21] 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.109//mamcci/1.33. 1.3.243.
[22] David W. Romero, Anna Kuzina, Erik J. Bekkers, Jakub Mikolaj Tomezak, and Mark Hoogen- doom. CKConv: Continuous Kernll Convolution For Sequential Data. In International Conference on Learning Representations, January 2022.
[23] Antonio Orvieto, Samuel I. Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. arXiv preprint arXiv: 2023.
[24] David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back-propagating errors. Nature, 323(6088):533-536) October 1986. ISSN 1476-4687. doi: 10. 10.1038/323533a0.
[25] Eduardo D. Sontag. A learning result for continuous-time recurrent neural networks. Systems & Control Letters, 34(3):151-158, June 1998. ISSN 01676911. doi: 10.101660016-6691199)) 00006-1.
[26] Haotian Jiang, Qianxiao Li, Zhong Li, and Shida Wang. A Brief Survey on 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.2212211
[27] Andrew R. Barron. Approximation and estimation bounds for artificial neural networks. Ma- chine Learning, (4(1):115-133, January 1994. ISSN 1573-0565, doi: 10. 10.1007/BF00993114
[28] G. Cybenko.
Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, December 1989. ISSN 1435-568X. doi: 10.1007/ SI02251274.
[29] Ronen Eldan and Ohad Shamir. The Power of Depth for Feedforward Neural Networks. In Conference on Learning Theory, pages 907-940. PMLR, June 2016.
12

---

A Memory of multi-layer linear RNNs
In this section, we study the memory function of linear RNN. The depth of linear RNN does not directly expand the memroy pattern as the memory are still decaying exponentially. Nonetheless, although the depth does not increase the approximation capacity, a deeper model is endowed with more structural property.
Take the two-layer Linear RNN as an example:
L CeWWlt-olus S( Walle
de
(27)
CP S'" Pzedale-n) drds
(28)
Ce ( e Uatt-
(29)
Jocreest drds (Cohit-brUjebllo-Nll
(30)
Jocrea Jreeee drds Ue
(31)
S( dr [: ds Te
(32)
dui duz p
10 dr S ds (C
(33)
dui duz
Σ I dr S: ds ds ( (x CU2F7)
(34)
Σ S dr S(" ds U
(35)
Σ L(-
dr (f. ds dlee U1,
(36)
Σ 1/¹ dr (
1
(elday-dill - cldos- ) Un
(37)
A22 - A1s
85
Σ [ dr
- (o>s)((-)) (drll-rr () U1s
1
(38)
Aaj - -11i
[ dr Σ
-ddultr)) Ir
(39)
Aaj - A1i
ij
The memory function of two-layer linear RNN is
P. Σ Sf
1 A2j A1s ( - 2uut))
(40)
The main advantage of two-layer linear RNN, compared with single-layer linear RNN, is that it can learn unbounded combination exponential decay function as long as X25 and Å are close enough. Notice that for simplicity we do not include the bias term in the evaluation of memory function. The multi-layer linear Recurrent Neural Network (RNN), including a bias term, can be perceived as linear combination of various depth-specific linear RNNs, devoid of bias term.
13

---

B
Proof
B.1
Universal approximation
Here we include the universal approximation from Barron 27 it is frequently used in the later constructive proof for state-space models.
Theorem B.1 (Cybenko (28), Barron (27)). For any continous function f : Rd + and compact
set K C R2 Assume the activation function or IR + RR is bounded and sigmoidal:
lim (() = 1, lim o(2) = -1 2-000
(41)
2-0-00
For any e >> 0, there exists m E N, A E Rm be RR,, C Rm such that
sup [lf(z) - g(x) S e,
(42)
æEK
where
g(z) Co b).
(43)
B.2 Proof for Proposition 3.1
Proof. Fix the bounded continuous function f.
For any O, according the universal approximation theorem in Theorem B.1 there exists U1, U2 b such that
If(z) U200 +b)l e.
(44)
Take W1 W22 by = O, the two-layer state-space model can approximate element- continuous functions. (Here the element-wise function mean the sequences that for each k; Yk only depends on xk-)
B.3 Proof for Proposition 3.2
Proof. The original statement is given in the discrete index. We prove the result for the continuous index and the discrete case can be derived by discretization.
Without loss of generality, assume the input output sequence are all one-dimensional. Otherwise we shall stacking the C, W, U for different input-output channels.
Since the input and output are one- dimensionnl, we know c, u are vectors and W a square matrix. To approximate the target convolution:
y1 S Pt-
(45)
by state-space model
0s S c. w(t-)) us,ds.
(46)
Since the prediction error can be decomposed into following form
De = S (p---- cT x,ds.
y4
(47)
Approximating the temporal convolution with state- space model over all bounded inputs x can be reduced function approximating problem:
m
max (0.7)
P+
Ge des
<6,
A 2
(48)
In other words, approximating convolution layer with state-space model equivalent to approxi-
mating general integrable function by function with exponential form ò. Em C - X,8
14

---

By change of variable, we have
(5(T) rE(e-
max
Σ c <e
(49)
Here f(r) p- log(r)- Since polynomials universal approximators compact intervals, know there exists C₁, A such that the aforementioned inequality is satisfied. (For example, f is smooth, take the Taylor expansion of function f-)
L
B.4 Proof for Proposition 3.6
Our proof based on Equation 18 for any sequence relationship H [xx)]== - {yr J we need to approximate & and Φb and subsequently approximate the representation prescribed by the Kolmogorov-Amin theorem.
Proof.
Fix tolerance 6.
As is shown in Figure B the first element-wiss function 6(-) can be approximated by two-layer state-space model. This is a result from the direct application of Proposition 3.1 In math terms, there exists U1. U2 bj such that two-layer state-space model approximate function
[ - (21 + bi)ll S 6.
(50)
We shall denote (21 + b1) by 6(z).
Next, according Proposition 3.2, know the (temporal) convolution be approximated via single-layer state-space model. There exists weights C3, W3, U3 such that
T
PT pō(o + ga)=
Σ C&w Cuslous + qa) Sc.
(51)
The last layer is again an element-wise function (.), which can be approximate by two-layer state-space model with weights U4, Us, by- (Figure
+ qa)) Us( C.W -UsT-"Us qa)) + ba) Sc.
(52)
Based on the above result, without loss of generality we assume the outer function & is Lipschitz continuous with coefficient L,, then the final approximation error bounded by a + +
PT pr-po(z; qa)) Ub(UA
SW + qa)) + 64)
(53)
p=1
p=1
r
pr PT-p61 p00 : +a)))==
Σ
pr (op qa))
(54)
+
PT p6 qa)) +
C2Wa - UUg(( ga))
(55)
1=1
T
+
4
C2W - PUgŌ( + ga)) - (ss( - Pz00(x + qa)) + bb)
(56)
1=1
<Lppe|late LE+e.
(57)
To summarize, achieve the approximation of general nonlinear sequence toaeeetto-eeeee so-sequence relationship with representation (with Lipschitz continuous b) via five-layer state-space model.
Since the Lipsethiz continuous function is dense in the set of continuous function, therefore the universal approximation can be generalized the representation with + not necessarily Lipschitz continuous.
D
15

---

B.5 Proof for Proposition 3.9
Proof. For simplicity, we will only present the approximation of an n-th order component of the Volterra Series. The general approximation of nonlinear sequence-to- -o-eeeen--e relationship can be achieved by approximating different order component separately and taking the linear combination.
Consider the target functional
Vo Vt S (n((t.......m))
" Tnd II + Ty)dTz
(58)
The state-space model's n-th order term can be represented by
Dn Σ S.
I1 (m)) (Tx)
II x(t Ty)dT,.
(59)
can be seen the kernel function of state-space model is (T, Fn) = ETh IT h A/ (T))
while the original n-th order kernel is multi-variable function hn (T Tn).
For any tolerance there exists a sufficiently large hidden dimension m such that the multi-variable function is approximated by the single-variable function's 's product:
m
Σ i=
(1m) (T₁) hn (TI Se.
(60)
For example, may consider h2 to be polynomial of Ty and take the Taylor expansion of kernel hn-
Remark B.2. While the aforementioned proof for approximation is provided through a polynomial method, it's commonly accepted that polynomials may not be the most efficient means to parameterize kernel functions. Consequently, a variety of techniques have been empirically investigated to represent convolutional layers (22).
B.6
Proof for Proposition 3.11
Proof. As na converges to x² exponentially and p is integrable, know the limit of ye exists
lim y1 lim / PaTt p 100
/
Ps lim It- ds [o Psa ds. t-000
(61)
1-000
Here Pa = C U 0 is the memory function for (continuous) state-space model.
By the dominated convergence theorem, as p integrable and eaat put| x= is bounded sequence,
lim co |1yr v"1l lim cot
Ps(xr= x )ds
(62)
|ps lim en (orf x ds
(63)
t0000
1 [pal 0ds
0.
(64)
B.7 Proof for Proposition 3.12
Proof. Since som J2 by continuity of the activation function (+:)
lim lim o(x,) of lim xx) = axx)).
(65)
100 6-000
t000
Hereafter define y" o2*).
16

---

Since o is Lipschitz continuous, let L be its Lipschitz constant
lim co 11 - y²1l = lim e (1] - o(x") 7000
(66)
7-0
< lim e00 L||sg e t00
x²1
(67)
L lim e eot 1|2c x²1l
(68)
0.
(69)
The Lipschitz continuity is weak assumption that most of the activations such ReLU, GeLUU, tanh, hardtanh satisfy.
C Limitations
Theoretical results on approximation do have quantitative results. Therefore it is not easy to directly compare the efficiency of different types of models over a specific task. The good news is that the general memory function servers as guideline in constructing models. Take the Hyena [12 architecture as an example, as the implicit representation of convolution kernel is utilized in the network, Hyena is not recurrent model. If we replace the convolution layer by state-space model, we can "translate" a non-recurrent neural network into a recurrent neural network without sacrificing approximation capacity. The main advantage of recurrent networks, compared with implicit convolution form, lies in the lower inference memory cost.
This study primarily explores the qualitative attributes of the state space model within the context of approximation theory. To better delineate it from other architectures like linear transformers, a more in-depth investigation into the rate of approximation necessary.
D Comparisons between RNNs, SSMs and S4
In Table we compare different recurrent models in terms of the recurrence, universality, temporal parallel and the memory decay speed.
Our core findings are established for SSM; however, we argue that they are applicable to S4 as well. The primary differences between the vanilla state-space models (SSMs) and S4 involve model parameterisation, weight initialisation, discretisation, normalisation, dropout, and residual connections. The model architectures of SSMs and S4 are almost identical, as both alternately stack linear RNNs and nonlinear activation layers. Therefore, in terms of universal approximation, the approximation capacities of both SSMs and S4 are equivalent.
Linear RNN
Nonlinear RNN
SSMs
S4
Recurrence Universality
Yes
Yes
Yes
Yes Yes (ours) Yes Yes, moderated (ours)
No
Yes (hardtanh, tanh)
Yes (ours)
Temporal Parallel
Yes
No
Yes
Exponential decay
Yes 14
Yes
16
Yes (ours)
Table 2: Comparisons between RNNs, SSMs and $4
E Further discussion on the two proofs for universality of SSMs
We provided comparison between the two proof methods: An analogy between caannogrov-thhorree and classical fully-connected neural networks can be drawn because of the finite number of layers in both. It shown Eldan and Shamir 22 that a simple function expressible by small 3-layer feed- forward neural networks cannot be approximated to certain accuracy unless the network's 's width is exponential in the dimension. contrast, Volterra-Serier shares similarities with deep learning, and as result, the advantages of deep learning classical fully-connected neural networks carry over
17

---

to this approach. The authors are inclined to consider Volterra-Series based construction as relatively superior, and increasing the depth to be more efficient way to scale up the model.
18


Reviews:
[{"review_id": "m1EYsjJAj4", "reviewer": "Reviewer_rFCc", "summary": "The paper presents universal approximation results for state-space models (SSM) with layer-wise nonlinearity. In particular, two-layer SSMs with layer-wise nonlinearity can approximate any continuous function over a compact set. Moreover, SSMs can approximate elementwise function and convolution. The paper also characterizes the memory behavior of SSMs, showing that their memory still decays exponentially when the eigenvalues of the A matrix is bounded from 1. These theoretical results are validated with numerical experiments.", "questions": "1. What are the dimensions of input/output of the SSMs? The notation is unclear on this.\n2. Eq (9): What's H(x_test). Why is rho_hat defined this way?\nMore generally I don't understand this section.\n3. Why does the paper focus on approximation results for elementwise function and convolution?\nElementwise function has no recurrent so it's all about the layer-wise non-linearity?\n4. I don't understand Prop 3.12. Is it the same constant c0?\n", "limitations": "Not necessary.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Universal approximation results are helpful to theoretically characterize the expressive power of SSMs. These models are becoming more popular and these results are not yet known to the best of my knowledge. Consequently the paper could help better understand these models.\n\n2. The presentation is quite clear. Even though this paper is theory-heavy, the main proof ideas are summarized in the main paper. This helps readers understand the technical challenges and the idea of the approach.", "weaknesses": "1. Lacking connection to linear RNNs. SSMs are a special case of linear RNNs, and universal approximation results of linear RNNs are available. Moreover, one can show that almost any linear RNNs can be written as SSMs (e.g. Sec 2.2 of Gupta et al. 2022). This is simply because almost any matrix A can be diagonalized, and put into RNNs. Could the university approximation results of linear RNNs be used to prove university approximation results of SSM through this connection?\n\n2. Lack of applications, or a direction to help with applications. While the theoretical results could help with the understanding of these models, the paper does not point out potentially applications of these theoretical results. This might limit the significance of these results.\n\n\n[1] Simplifying and Understanding State Space Models with Diagonal Linear RNNs. Ankit Gupta, Harsh Mehta, Jonathan Berant. 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive comments for us to clarify details in our work. Below is our response to the points raised:\n### **Weaknesses:**\n1. \"Lacking connection to linear RNNs. SSMs are a special case of linear RNNs, and universal approximation results of linear RNNs are available. Moreover, one can show that almost any linear RNNs can be written as SSMs (e.g. Sec 2.2 of Gupta et al. 2022). This is simply because almost any matrix A can be diagonalised, and put into RNNs. Could the university approximation results of linear RNNs be used to prove university approximation results of SSM through this connection?\"\n\n- Thank you for your suggestion. We have attached a table comparing linear RNNs, nonlinear RNNs, state-space models, S4 in detail in 'Response to all Reviewer' section. \n- Sec 2.2 of Gupta et al. 2022 claims that `Diagonal Linear RNNs (DLRs) are as expressive as general linear RNNs`. Indeed we may consider diagonal case of SSMs, but it is important to note that the result in Gupta et al. 2022 does not contribute to the universality of linear RNN, and therefore is not directly relevant with the proof of SSMs universality. Moreover, there is more to SSMs than linear RNN that we have taken into consideration, such as the unique architecture of alternating linear and non-linear layers. Therefore, the connection between the two might not be as strong unfortunately.\n\n2. \"Lack of applications, or a direction to help with applications. While the theoretical results could help with the understanding of these models, the paper does not point out potentially applications of these theoretical results. This might limit the significance of these results.\"\n\n- While universal approximation theorem doesn't guarantee the ease of learning or the speed of convergence in training a network, it does provide a theoretical underpinning for understanding why, given enough data and computational power, neural networks are capable of excellent performance. \n- While it is straightforward that linear RNN can only approximate linear functionals, we proved that state-space models (linear RNN with layer-wise nonlinearity) has the universal approximation property. This property is a theoretical guarantee for various applications. In practice, State Space Models (SSMs) demonstrate performance comparable to transformer models (see [1] [2]). Practitioners often question whether a model's success on one task extends to new tasks. **Our findings support the viability of using SSMs for these new tasks.**\n\n### **Questions:**\n\n1. \"What are the dimensions of input/output of the SSMs? The notation is unclear on this.\"\n\n- Thank you for pointing this out. We have updated variable dimension in SSM single layer general form as follows: $x \\in \\mathbb{R}^{d_{in}}, y \\in \\mathbb{R}^{d_{out}}, h \\in \\mathbb{R}^m, W \\in \\mathbb{R}^{m \\times m}, U \\in \\mathbb{R}^{m \\times d_{in}}, b \\in \\mathbb{R}^m, C \\in \\mathbb{R}^{d_{out} \\times m}, D \\in \\mathbb{R}^{d_{out} \\times d_{in}}$. For multi-layer state-space model, the nonlinear activation is added layer-wise as shown in Figure 1.\n\n2. \"Eq (9): What's H(x_test). Why is rho_hat defined this way? More generally I don't understand this section.\"\n\n- Thank you for pointing out the typo in the paper. We have modified this in the full paper version in supplementary material as $\\hat{y}_t = \\mathbf{H}_t (\\mathbf{x}^{\\textrm{test}})$.\n- For consistency with the memory function $\\rho$ in linear functional analysis, we substitute the test input with the Heaviside inputs denoted by $\\mathbf{x}^{\\textrm{test}}$ where $\\mathbf{x}^{\\textrm{test}}(t) = x,$ if $t > 0$, and $\\mathbf{x}^{\\textrm{test}}(t) = 0,$ if $t \\leq 0$.\n- Due to the word limitations in individual responses, we have moved our reply to this question to the \"Response to all Reviewer\" section, specifically under the topic \"Definition of Memory Function and How to Evaluate It.\"\n\n3. Why does the paper focus on approximation results for elementwise function and convolution? Elementwise function has no recurrent so it's all about the layer-wise non-linearity?\n\n- In our paper, the main result of universal approximation theorem is established in section 3.3 based on Kolmogorov-Arnold representation theorem and Volterra Series. In particular, our proof relies heavily on element-wise nonlinear functions and temporal convolutions - these serve as the primary building blocks in our theoretical structure. Therefore, in the section 3.1 and 3.2, we first establish the feasibility of approximating element-wise nonlinear functions and temporal convolutions with state-space models. While it is true that element-wise functions lack recurrence, they provide nonlinearity without breaking the recurrence. It is important to highlight that the nonlinearity between layers alone is sufficient to achieve universality of state-space models. For example, it can approximate nonlinear RNNs with nonlinear recurrent activations. We are happy to elaborate further on any point.\n\n4. I don't understand Prop 3.12. Is it the same constant c0?\n\n- As is shown in appendix B.7, it is the same constant $c_0$. \n\n---\n[1] Albert Gu, Karan Goel, and Christopher Re. \"Efficiently Modeling Long Sequences with Structured State Spaces.\" In International Conference on Learning Representations. 2021.\n\n[2] Jimmy TH Smith, Andrew Warrington, and Scott Linderman. \"Simplified State Space Layers for Sequence Modeling.\" In The Eleventh International Conference on Learning Representations. 2022."}, {"review_id": "Se84Mr1zcd", "reviewer": "Reviewer_KVQv", "summary": "The authors set out to analyze state space models, which have been gaining popularity as alternatives to transformer based systems that can better model long range dependencies and are more computationally efficient. Since such models do not utilize a non-linear activation function along the temporal access, it is important to analyze if this poses a restriction to their modeling capabilities. The paper provides a construction-based argument to prove that as long as there are layer-wise nonlinearities in the model, it becomes a universal approximator for any sequence model and thus does not require activation functions in the temporal domain to improve model capacity. Further, the authors also show that like the earlier recurrent networks (RNN, GRU, etc.), these models also suffer from an exponentially decaying memory.\n\nWhile the paper tackles quite a relevant topic on a family of models that are becoming widely popular, the draft itself could use some work. In particular, the presentation and clarity of the work needs to be improved, and it would be very helpful to also get some intuition behind the propositions mentioned and proved. That is, to understand what the propositions imply and why they are important.", "questions": "- Line 48: Why is this relationship nonlinear? It looks like a linear function of $x$.\n- Line 83: Does the definition of $\\hat{\\rho}_t$ involve $t$ in the exponential or $(t-s)$ which is written in the draft (mistakingly, I believe?)\n- Could the authors provide some clarification and their reasoning on their construction of the memory function? Why is this reasonable? How is this computed?\n- For universality results in Section 3.3, could the authors provide some intuition behind Remark 3.4, what it implies and how is it achieved?\n- Is there a difference in some assumptions between Kolmogorov-theorem based construction with Volterra-Series based construction? Is the latter always superior? What cost does it come with?", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors show that the state space models (SSMs) which have no non-linearity in their temporal axis can still universally approximate any sequential mapping up to some arbitrary error. This is proved by construction.\n- The authors also show that like RNNs, such models also suffer from the exponential memory decay problem.\n- Some preliminary numerical experiments are conducted to test the memory decay problem across different recurrent models.", "weaknesses": "- The writing of the draft can be substantially improved. It would be good to include some explanations into the implications of each proposition and theorem, as to understand why exactly it is meaningful and important. The plots are currently taking a lot of extra space which can be freed to add this content.\n- It would be nice if the authors could provide some kind of rates of memory decay to better understand if it is better or worse in SSMs than other RNN-based methodologies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive feedback on providing more explanation and intuition behind the mathematical proof.  Below is our response to the points raised:\n\n1. \"The writing of the draft can be substantially improved. It would be good to include some explanations into the implications of each proposition and theorem, as to understand why exactly it is meaningful and important. The plots are currently taking a lot of extra space which can be freed to add this content.\"\n\n- Thank you for the suggestions on the paper writing. We have incorporated the following implications into the final revision:\n- The implications of Propositions 3.1 and 3.2 are modest yet vital: Proposition 3.1 works on the approximation of element-wise (or layer-wise) nonlinear functions, while Proposition 3.2 focuses on temporal convolution. The findings demonstrate that these two types of operators can indeed be approximated using state-space models. While the proof approach may appear elementary, it plays a pivotal role, laying the groundwork for the more advanced findings presented in Propositions 3.6 and 3.9.\n- Implications of Theorem 3.5 and Proposition 3.6: The Kolmogorov-Arnold theorem shows the feasibility to **decompose any continuous multi-variable function into single-variable functions and addition operators.** In state-space model, the target causal time-homogeneous sequential relationship can be viewed as a multi-variable function where each input is a variable. Since linear RNN provides the addition across different inputs, the element-wise nonlinearity corresponds to the single-variable function. \n- Implications of Theorem 3.8 and Proposition 3.9: The Volterra Series approach is a more deep-learning flavour construction while the Kolmogorov-Arnold theorem provides a classical finite-layer approximation result. See the answer to question 7 on the comparison of two approaches. \n- Implications of Proposition 3.11 and Proposition 3.12: Despite the state-space model's proficiency in managing numerous long-sequence tasks, including those within the long-range arena, it exhibits an inherent exponential memory decay. **Our findings, however, suggest that the smart initialisation from S4 can moderate this issue, resulting in a slower memory decay function.**\n\n2. \"It would be nice if the authors could provide some kind of rates of memory decay to better understand if it is better or worse in SSMs than other RNN-based methodologies.\"\n\n- Thank you for your valuable suggestion. We acknowledge the importance of understanding how memory decay in SSMs compared to other RNN. However, according to the survey paper [1], there is limited work on the rate of memory rate for different SSMs. Direct comparisons of these rates could be complex, given that they might hinge on multiple factors, including the number of parameters. We consider this as a topic for future exploration.\n\n### **Questions:**\n\n3. \"Line 48: Why is this relationship nonlinear? It looks like a linear function of $x$.\"\n\n- Yes, it is a typo. Thank you for pointing this out. We have modified it into `the first component` in the revision.\n\n4. \"Line 83: Does the definition of $\\hat{\\rho}_t$ involve $t$ in the exponential or $(t-s)$ which is written in the draft (mistakingly, I believe?)\"\n\n- Thank you so much for pointing out the mistake in the notation, it should be $\\hat{\\rho}_{t-s}$. We have modified it in the revision of the paper. \n\n5. \"Could the authors provide some clarification and their reasoning on their construction of the memory function? Why is this reasonable? How is this computed?\"\n  \n- Due to word limitations, we have moved the reply to this question to the \"Response to all Reviewer\" section, specifically under the topic \"Definition of Memory Function and How to Evaluate it\". \n\n6. \"For universality results in Section 3.3, could the authors provide some intuition behind Remark 3.4, what it implies and how is it achieved?\"\n\n- We first clarify a typo in the Remark 3.4: `we use the same` $\\Phi$. The first Kolmogorov theorem is proved for different $\\Phi_q$ and $\\phi_{q, p}$. Subsequent studies refine this process, minimising the variety of functions required to achieve the final form of Equation (16). This refinement can be interpreted as an application of **weight sharing** in the approximation of functions $\\Phi$ and $\\phi$. Essentially, the practice of weight sharing in SSMs is substantiated by the diverse results cited in Remark 3.4.\t\n\n7. \"Is there a difference in some assumptions between Kolmogorov-theorem based construction with Volterra-Series based construction? Is the latter always superior? What cost does it come with?\"\n\n- Thank you so much for your very thoughtful and inspiring question. There is no direct difference in terms of assumptions between Kolmogorov-theorem based construction and Volterra-Series based construction. Both constructions work for causal regular time-homogeneous nonlinear functionals, in other words, sequence relationships. \n- Please refer to \"Response to all Reviewers\" , under \"Highlights of Other Modifications\" section, point number 2 for a detailed comparison between the two proof methods.\n- Certainly, the Volterra-Series based construction comes with a cost similar to that of deep learning. Its complex structure makes the analysis of the model dynamics difficult to analyse. \n\n---\n[1] Haotian Jiang, Qianxiao Li, Zhong Li & Shida Wang. (2023). A Brief Survey on the Approximation Theory for Sequence Modelling. _Journal of Machine Learning_. _2_ (1). 1-30."}, {"review_id": "FaZtlTlx0D", "reviewer": "Reviewer_gZh5", "summary": "This paper analyzes properties of state space models (SSMs) and verifies the analytic results with numerical simulations.\n\nThe primary result is that SSMs have the same basic properties as classic RNNs.  They perform temporal convolution on their inputs, with exponentially decaying memory and are universal function approximators.", "questions": "Why do SSMs work well empirically?  Is it just that they more easily find long time constants in their exponential decay?   I think it's really important to say something substantive about this.", "limitations": "Why do SSMs work well?", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "My overall assessment is that this paper is an important contribution to our understanding of SSMs.  It raises really important questions about how SSMs are apparently able to learn long-range dependencies and points to the generality of exponentially-decaying memory.  \n\nThe exposition was pretty clear; although the math is challenging for a broad audience, the simulations give confidence that the results are sound.  ", "weaknesses": "It's worth thinking more about presentation of the figures.  Figure 4 was pretty helpful but Figure 3 was pretty baffling.   Generally speaking my suggestion is that the captions could be more explicit and all of the terms in the expressions should appear in the figures.\n\nThe paper raises a really important question that should be addressed more explicitly.  If SSMs have basically the same properties as generic RNNs, why do they apparently work so much better?  I appreciate that it may not be possible to answer this question with certainty, but some thoughtful discussion would really enhance the impact of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive review and insightful questions regarding the reasons behind the outstanding performance of SSMs. Below is our response to the points raised:\n\n### **Weaknesses:**\n\n1. \"It's worth thinking more about presentation of the figures. Figure 4 was pretty helpful but Figure 3 was pretty baffling. Generally speaking my suggestion is that the captions could be more explicit and all of the terms in the expressions should appear in the figures.\"\n\n- We greatly appreciate your helpful feedback regarding the presentation of our figures. We have enhanced Figure 3 by revising its captions and incorporating the necessary equations into the figure itself. Please let us know if this addresses your question or if you have any other feedback. \n\n2. \"The paper raises a really important question that should be addressed more explicitly. If SSMs have basically the same properties as generic RNNs, why do they apparently work so much better? I appreciate that it may not be possible to answer this question with certainty, but some thoughtful discussion would really enhance the impact of this paper.\"\n\n- Since both of SSM and RNN have universal approximation capabilities, their difference in performance mainly stems from the training process. Unlike traditional RNNs with recurrent nonlinearity, the linear RNN structure of SSM significantly reduces the time cost of forward and backward operations, scaling it down from $O(T)$ to $O(\\log T)$. While RNNs such as [4] used a sequence length of 100, the fast training speed of SSM helps handle longer input sequences. Besides training speed, there could also be some other underlying reasons that require further ablation studies to pinpoint.\n\n### **Questions:**\n\n3. \"Why do SSMs work well empirically? Is it just that they more easily find long time constants in their exponential decay? I think it's really important to say something substantive about this.\"\n\n- Thank you for the inspiring question. We will incorporate the following discussion into the revision. \n- In response to the inquiry on why SSMs (or specifically S4) perform well empirically, there are several dimensions to consider. Primarily, both SSMs and S4s possess a universal approximation property that forms the theoretical foundation of their numerical performance. Secondly, the parameterisation of the recurrent matrix and the time discretisation in S4 maintains stability as elucidated in [1]. This stability ensures the model's capability in approximating long-memory targets, even when the model's memory undergoes exponential decay. Thirdly, SSMs benefit from the parallelisation capabilities of linear RNNs through techniques like the fast Fourier transform or associative scan, which scale the time complexity down from $O(T)$ to $O(\\log T)$. Moreover, the weight initialisation method illustrated in [2,3] further augments the model's capacity to learn long-term memory. Lastly, the success of S4 can be attributed to the integration of widely used techniques such as layer normalisation, dropout, and residual connections.\n\n### **Limitations:**\n\n4. \"Why do SSMs work well?\"\n\n- In response to the query regarding the efficacy of SSMs, we have delved into an analysis encompassing various aspects such as universality, parameterisation, training methodology, initialisation, and other prevalent techniques, as elucidated in our reply to Question 3. While we acknowledge that our insights might not offer a comprehensive explanation, we are optimistic that our analysis provides a valuable contribution towards the community's evolving understanding of the model. \n\n---\n[1] Shida Wang,  Zhong Li, and Qianxiao Li. \"Inverse Approximation Theory for Nonlinear Recurrent Neural Networks.\" _arXiv preprint arXiv:2305.19190_ (2023).\n\n[2] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. \"Hippo: Recurrent memory with optimal polynomial projections.\" _Advances in neural information processing systems_ 33 (2020): 1474-1487.\n\n[3] Albert Gu,  Karan Goel, and Christopher Re. \"Efficiently Modeling Long Sequences with Structured State Spaces.\" In _International Conference on Learning Representations_. 2021\n\n[4] Jack Rae, Chris Dyer, Peter Dayan, and Timothy Lillicrap. \"Fast parametric learning with activation memorization.\" In _International Conference on Machine Learning_, pp. 4228-4237. PMLR, 2018."}, {"review_id": "9uyqtfOGgy", "reviewer": "Reviewer_QCvt", "summary": "This paper attempts to show several properties of SSMs: a) SSMs can approximate element-wise functions and temporal convolutions b) Universality of SSMs c) Exponential memory decay. The authors also show experiments of SSM's exponential memory decay and compare them against variants of RNN architectures.", "questions": "Authors may address my comments above.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 1, "strengths": "* Thorough background section and clear introduction of the RNN and SMM architecture.\n\n* Clear writing.\n\n* The usage of the Kolmogorov-Arnold thoerem and Volterra series is interesting.\n", "weaknesses": "* My main concern is most of the main results seems trivial: When taking away the tricks that makes SSMs work such as smarter initialization and diagonal parameterisation, architecture wise, SSMs are simply an RNN without non-linearly between hidden states. Hence, the theory results (i.e. proposition 3.1, 3.2, 3.12 and theorem 3.13) seems to transfer very trivially from RNNs.\n\n*  The 2 formulations for showing universality of SMMs in section 3.2 seems to deviate greatly from the SSM architecture (i.e. figure 3 and 4 does not follow the definition of SSMs in equation 1 and 2). It is unclear how much the result transfers for standard SSMs used in practice.\n\n* In figure 5 and 6 there are no error bars or mentioning of number of seeds. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your helpful comments for us to provide clarifications on the SSM architecture, its relation to RNNs, and therefore the significance of our findings. Below is our response to the points raised:\n\n1. \"My main concern is most of the main results seems trivial: When taking away the tricks that makes SSMs work such as smarter initialisation and diagonal parameterisation, architecture wise, SSMs are simply an RNN without non-linearly between hidden states. Hence, the theory results (i.e. proposition 3.1, 3.2, 3.12 and theorem 3.13) seems to transfer very trivially from RNNs.\"\n\n-  SSM is similar to RNN in the sense that it stacks linear RNN and layer-wise nonlinearity alternately. **However, SSMs are different from linear RNNs as linear RNNs are not universal approximators. While general nonlinear RNNs are universal, they introduce nonlinearity differently, leading to distinct dynamics between SSMs and nonlinear RNNs.** Therefore SSMs are different from linear RNNs and traditional nonlinear RNNs. In hindsight, the universal approximation and exponential memory decay might seem simple. However, these results shall contribute to the understanding of SSMs' excellent performance over various long-sequence modelling. \n- Since proposition 3.1 is the direct application of universal approximation property of one hidden-layer neural network and proposition 3.2 is the inherent property of linear RNN, they might seem simple from the proofs. However, these two propositions are the indispensable building blocks to achieve the main results (proofs for universality of SSMs) in proposition 3.6 and proposition 3.9. The exponential memory decay results in proposition 3.12 and theorem 3.13 show that layer-wise nonlinearity does not change the qualitative memory pattern of recurrent models. \n\n2. \"The 2 formulations for showing universality of SSMs in section 3.2 seems to deviate greatly from the SSM architecture (i.e. figure 3 and 4 does not follow the definition of SSMs in equation 1 and 2). It is unclear how much the result transfers for standard SSMs used in practice.\"\n\n- Equations 1 and 2 only illustrate the structure of single-layer state-space models. The constructions in Propositions 3.6 and 3.9 for multi-layer state-space models correspond to the structures demonstrated in Figures 3 and 4, respectively. **They show that by alternating between stacking simple linear RNNs and applying layer-wise nonlinearity, universality can be achieved.** **In practice, multi-layer state-space models are commonly used for various sequence modelling tasks (e.g., 2~32 layers in [1], 6 layers in [2], 4 layers in [3])**. Additionally, a single-layer state-space model without nonlinear activation is not universal and cannot be used to learn general nonlinear sequence-to-sequence relationships. Consequently, our theory characterises the standard SSM models prevalent in practical use.\n\n3. \"In figure 5 and 6 there are no error bars or mentioning of number of seeds.\"\n\n- Thank you for bringing this oversight to our attention. Error bars and seed counts are indeed critical for interpreting experimental results. We have updated figures 5 and 6 to include error bars. The experiments are repeated 100 times to obtain the error bars. \n\n---\n[1] Albert Gu, Karan Goel, and Christopher Re. \"Efficiently Modeling Long Sequences with Structured State Spaces.\" In _International Conference on Learning Representations_. 2021.\n\n[2] Eric Nguyen, Karan Goel, Albert Gu, Gordon Downs, Preey Shah, Tri Dao, Stephen Baccus, and Christopher Ré. \"S4nd: Modeling images and videos as multidimensional signals with state spaces.\" _Advances in neural information processing systems_ 35 (2022): 2846-2861.\n\n[3] Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. \"On the parameterization and initialization of diagonal state space models.\" _Advances in Neural Information Processing Systems_ 35 (2022): 35971-35983."}, {"review_id": "zyw5y4qnZi", "reviewer": "Reviewer_nePh", "summary": "The paper provides a constructive proof that state-space models (SSMs) are universal approximators of sequence-to-sequence mappings.\nMoreover, it shows that SSMs (and even empirically S4) suffer from exponentially decaying memory just like standard RNNs.", "questions": "See weaknesses", "limitations": "The paper provides an interesting and important proof that SSMs are universal, as well as that the memory functions decay exponentially. However, the proof does not include S4 models. Moreover, the quality of writing is very poor, which makes it hard to follow. Overall, the provided proof is very simple, which makes it appealing. \n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "Up to my knowledge this is the first (constructive) proof that SSMs are universal. I find it in particular interesting that SSMs also suffer from exponentially decaying memory (given the provided definition of such).", "weaknesses": "Regrettably, the paper exhibits a significant lack of quality in its writing, containing numerous grammatical errors and typos. It is imperative that it undergoes a comprehensive proofreading process to address these issues.\n\nFrom my understanding, the paper proves universality for SSMs, which does not include universality for S4 (i.e., SSMs with specific structure of the matrices). This is a major limitation, as in practice no one uses simple SSMs, but only S4. Can S4 be included in the proof? I presume one has to show that also S4 can approximate element-wise functions up to any precision.\n\nThe section about the curse of memory is very hard to follow. Can you please rewrite it and properly introduce the concept of memory functions?\n\nThe paper is not rigorously written. For instance, it would be much more readable, if the authors would define every variable, e.g., $W \\in \\mathbb{R}^{m\\times m}$ and so on. This would also help the authors avoid using variables that haven't been introduced before.\n\nThe provided full paper in the appendix and the main paper differ: for instance in equation 9: $\\mathbf{H}$ depends on $t$ in the full paper, but not in the main paper. \n\nForm what I understood, the universality proof of proposition 3.6 approximates functions, where the target value at every index depends on all elements in the full input sequence. However, this is not realistic, as mainly causal operators between sequences have to be learned, i.e., operators that are independent of the future values of the input sequence at every index. Can you please change the proof accordingly? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your important questions regarding our proof, as well as your constructive suggestions for enhancing the writing quality. Below is our response to the points raised:\n\n1. \"Regrettably, the paper exhibits a significant lack of quality in its writing, containing numerous grammatical errors and typos. It is imperative that it undergoes a comprehensive proofreading process to address these issues.\"\n\n- Thank you for bringing the writing concern to our attention. We have undertaken thorough proofreading and incorporated the necessary updates in the final revision.\n\n2. \"From my understanding, the paper proves universality for SSMs, which does not include universality for S4 (i.e., SSMs with specific structure of the matrices). This is a major limitation, as in practice no one uses simple SSMs, but only S4. Can S4 be included in the proof? I presume one has to show that also S4 can approximate element-wise functions up to any precision.\"\n\n- We have prepared a table in the 'Response to all Reviewer' section to compare SSMs with linear RNNs, nonlinear RNNs, and S4. The primary differences between the vanilla state-space models (SSMs) and S4 involve model parameterisation, weight initialisation, discretisation, normalisation, dropout, and residual connections. However, with the exception of the residual connection, the model architectures of SSMs and S4 are almost identical, as both alternately stack linear RNNs and nonlinear activation layers. Therefore, in terms of universal approximation, the approximation capacities of both SSMs and S4 are equivalent.\n\n3. \"The section about the curse of memory is very hard to follow. Can you please rewrite it and properly introduce the concept of memory functions?\"\n\n- We have rewritten the section on the curse of memory to improve the introduction of the memory function, as well as the phenomenon of the curse of memory. Due to word constraints in the reply section, the revised fragments are presented in the 'Response to all Reviewer' under the section 'Definition of Memory Function and How to Evaluate It'.\n\n4. \"The paper is not rigorously written. For instance, it would be much more readable, if the authors would define every variable, e.g., $W \\in \\mathbb{R}^{m\\times m}$ and so on. This would also help the authors avoid using variables that haven't been introduced before.\"\n\n- Thank you for pointing this out. We have updated variable dimension in SSM single layer general form as follows: $x \\in \\mathbb{R}^{d_{in}}, y \\in \\mathbb{R}^{d_{out}}, h \\in \\mathbb{R}^m, W \\in \\mathbb{R}^{m \\times m}, U \\in \\mathbb{R}^{m \\times d_{in}}, b \\in \\mathbb{R}^m, C \\in \\mathbb{R}^{d_{out} \\times m}, D \\in \\mathbb{R}^{d_{out} \\times d_{in}}$. \n\n5. \"The provided full paper in the appendix and the main paper differ: for instance in equation 9: $\\mathbf{H}$ depends on $t$ in the full paper, but not in the main paper.\"\n\n- Thank you for the careful reading and pointing out the difference. We discovered the missing subscript $t$ and added it in the full paper. \n\n6. \"Form what I understood, the universality proof of proposition 3.6 approximates functions, where the target value at every index depends on all elements in the full input sequence. However, this is not realistic, as mainly causal operators between sequences have to be learned, i.e., operators that are independent of the future values of the input sequence at every index. Can you please change the proof accordingly?\"\n\n- Thank you so much for raising this important question. In proposition 3.6, we did not explicitly specify assumptions for the targets other than the **continuity** w.r.t. the inputs. Here we discuss several other important properties expected from the targets. In the context of proposition 3.9, we explore these properties as defined in paper [1] Definition 3.1. \n    1. **Causality**. Autoregressive problems such as language modelling focus on the cases that output $y_t$ only depend on the inputs $x_{0, \\dots, t}$. The causality of the targets guarantees the temporal convolution kernels $\\rho_k$ in Figure 4 having the property $\\rho_k (t) = 0, t \\leq 0.$ This causal temporal convolution, together with proposition 3.2, ensures that state-space model can be implemented in a recurrent form. \n    2. **Time-homogeneous**. In sequence modelling, the concept of being time-homogeneous is fundamental. This is because time-inhomogeneous targets may not be approximated to an arbitrary level of accuracy, regardless of how much data or computational resources are available. \n    3. **Bounded & Regular**. These two properties are usually assumed from the theoretical consideration. As shown in [1], continuous causal regular and time-homogeneous linear functionals have a convolution form based on the Riesz representation. \n\n### **Limitations:**\n\n7. \"The paper provides an interesting and important proof that SSMs are universal, as well as that the memory functions decay exponentially. However, the proof does not include S4 models. Moreover, the quality of writing is very poor, which makes it hard to follow. Overall, the provided proof is very simple, which makes it appealing.\"\n\n- As mentioned in response to the second comment, the primary differences between SSMs and S4 models lie in aspects other than the model architecture. Therefore, the universality proof for SSMs should also naturally extend to S4 models.\n- We apologise for the current state of our manuscript's writing. We are dedicated to improving this aspect significantly in the final revision. \n- We are glad to know that you found our proof's simplicity appealing. Our aim is to maintain rigour while ensuring comprehensibility. \n\n---\n[1] Zhong Li,  Jiequn Han, E. Weinan, and Qianxiao Li. \"On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis.\" In International Conference on Learning Representations. 2020."}]

Author rebuttal:
## Response to all Reviewers
We thank all the reviewers for their insightful reviews. The reviewers thought the work tackles **"quite a relevant topic on a family of models that are becoming widely popular"**, provides result that **"is an important contribution to our understanding of SSMs"**, with **"an interesting and important proof"**. The experiments demonstrate a memory decay phenomenon that is **”particular interesting”** and **”give confidence that the results are sound”**.

Below we present a summary of our response and the corresponding major changes.

### Comparisons Between RNNs, SSMs and S4
**Memory decay**: All the recurrent models in the table suffer from exponential decay in memory. However, S4 has a slower decay (as shown in experiments) with a suitable initialisation. 

| | Linear RNN| Nonlinear RNN| SSMs| S4|
|---|---|---|---|---|
| Recurrence| Yes| Yes| Yes| Yes|
| Universality| No| Yes (hardtanh,tanh) [1]| Yes (ours) | Yes (ours)|
| Temporal Parallel| Yes| No | Yes| Yes|
| Exponential decay| Yes, [2]| Yes, [3]| Yes (ours) | Yes, moderated (ours)|

### Definition of Memory Function and How to Evaluate It
- As a motivation for the memory function, [2] proves that a bounded causal continuous regular time-homogeneous linear functional has the following Riesz representation: $y_t = \mathbf{H_\mathrm{t}} (\mathbf{x}) = \int_{-\infty}^t \rho_{t-s} x_sds.$ Here $\rho_t$ is an $L_1$ integrable function. If $\rho_t$ rapidly decreases with $t$, then the target sequence map $\mathbf{H}_t$ has a short-term memory. Consequently, we refer to $\rho_t$ as the memory function, since it captures the memory property of a linear functional in its entirety.
- For consistency with the memory function $\rho$ in linear functional analysis, we substitute the original impulse test input $(1, 0, 0, \dots)$ with the Heaviside inputs denoted by $\mathbf{x}^{\textrm{test}}$ where $\mathbf{x}^{\textrm{test}}(t) = x,$ if $t > 0$, and $\mathbf{x}^{\textrm{test}}(t) = 0,$ if $t \leq 0$.
- Notice that the derivative of a linear functional at test input extracts the memory function $|\frac{d}{dt} H_t( \mathbf{x}^{\textrm{test}} ) | = |\rho(t)|_2$. Therefore a natural extension of the memory function $\rho_t$ to the nonlinear functionals is given in Section 2.3.
$\displaystyle \hat{\rho}(t) = |\frac{d \hat y_t}{dt}|_2$ where $\hat{y}_t = \widehat{\mathbf{H}}_t ({\mathbf{x}^{\textrm{test}}}).$
- Memory function can be evaluated by computing the model's derivative at the test input using finite difference method.

### Highlights of Other Modifications 
1. We added discussion on **possible reasons for the good performance of SSMs**:
	 Primarily, both SSMs and S4s possess a universal approximation property that forms the theoretical foundation of their numerical performance. Secondly, the parameterisation of the recurrent matrix and the time discretisation in S4 maintains stability as elucidated in [3]. This stability ensures the model's capability in approximating long-memory targets, even when the model's memory undergoes exponential decay. Thirdly, SSMs benefit from the parallelisation capabilities of linear RNNs through techniques like the fast Fourier transform or associative scan, which scale the time complexity down from $O(T)$ to $O(\log T)$. Moreover, the weight initialisation method illustrated in [4,5] further augments the model's capacity to learn long-term memory. Lastly, the success of S4 can be attributed to the integration of widely used techniques such as layer normalisation, dropout, and residual connections.
	 
2. We provided comparison between the two proof methods: 
	**An analogy between Kolmogorov-theorem and classical fully-connected neural networks can be drawn because of the finite number of layers in both.** It is shown in [6] that a simple function expressible by a small 3-layer feedforward neural networks cannot be approximated to a certain accuracy unless the network's width is exponential in the dimension. **In contrast, Volterra-Series shares similarities with deep learning**, and as a result, the advantages of deep learning over classical fully-connected neural networks carry over to this approach. **The authors are inclined to consider Volterra-Series based construction as relatively superior, and increasing the depth to be a more efficient way to scale up the model.**
	
3. Dimension of variables are attached to the paper, typos and grammar errors are resolved. 
---
[1] Lukas Gonon and Juan-Pablo Ortega. "Reservoir computing universality with stochastic inputs." IEEE transactions on neural networks and learning systems 31, no. 1 (2019): 100-112.

[2] Zhong Li, Jiequn Han, E. Weinan, and Qianxiao Li. "On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis." In International Conference on Learning Representations. 2020.

[3] Shida Wang, Zhong Li, and Qianxiao Li. "Inverse Approximation Theory for Nonlinear Recurrent Neural Networks." _arXiv preprint arXiv:2305.19190_ (2023).

[4] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. "Hippo: Recurrent memory with optimal polynomial projections." _Advances in neural information processing systems_ 33 (2020): 1474-1487.

[5] Albert Gu, Karan Goel, and Christopher Re. "Efficiently Modeling Long Sequences with Structured State Spaces." In _International Conference on Learning Representations_. 2021

[6] Ronen Eldan and Ohad Shamir. "The power of depth for feedforward neural networks." In Conference on learning theory, pp. 907-940. PMLR, 2016.

Meta-review: This paper provides theory for sequence-to-sequence models based on state space layers, which have achieved state-of-the-art performance on a challenging benchmarks. The reviewers agree that the universal approximation and exponential memory decay results are valuable contributions to the field, and many concerns were addressed through the discussion period.
Decision: Accept (poster)