Combining Recurrent, Convolutional, and Continuous-time Models with Linear State Space Layers
Authors: Albert Gu
Isys Johnson
Karan Goel
Khaled Kamal Saab
Tri Dao
Atri Rudra
Christopher Re
Venue: NeurIPS 2021 Poster (2021)
Keywords: recurrent neural networks
convolutions
continuous time models
sequence models
state space
time series
deep learning architecture

Abstract: Recurrent neural networks (RNNs), temporal convolutions, and neural differential equations (NDEs) are popular families of deep learning models for time-series data, each with unique strengths and tradeoffs in modeling power and computational efficiency.  We introduce a simple sequence model inspired by control systems that generalizes these approaches while addressing their shortcomings.  The Linear State-Space Layer (LSSL) maps a sequence $u \mapsto y$ by simply simulating a linear continuous-time state-space representation $\dot{x} = Ax + Bu, y = Cx + Du$.  Theoretically, we show that LSSL models are closely related to the three aforementioned families of models and inherit their strengths.  For example, they generalize convolutions to continuous-time, explain common RNN heuristics, and share features of NDEs such as time-scale adaptation.  We then incorporate and generalize recent theory on continuous-time memorization to introduce a trainable subset of structured matrices $A$ that endow LSSLs with long-range memory.  Empirically, stacking LSSL layers into a simple deep neural network obtains state-of-the-art results across time series benchmarks for long dependencies in sequential image classification, real-world healthcare regression tasks, and speech.  On a difficult speech classification task with length-16000 sequences, LSSL outperforms prior approaches by 24 accuracy points, and even outperforms baselines that use hand-crafted features on 100x shorter sequences.

Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers
Albert Gul, Isys Johnson', Karan Goel', Khaled Saab", Tri A Atri Rudra', Christopher Ré
Department of Computer Science, Stanford University
Department of Electrical Engineering, Stanford University Department of Computer Science and Engineering, University at Buffalo, SUNY falbertgu, karg, ksaab, trid)@stanford. edu, chrismredcs. stanford edu (isysjohn, atri atri)abuffalo. edu
Abstract
Recurrent neural networks (RNNs), temporal convolutions, and neural differential equations (NDEs) are popular families deep learning models for time-series data, each with unique strengths and tradeoff' in modeling power and computational efficiency. We introduce a simple sequence model inspired by control systems that generalizes these approaches while addressing their shortcomings. The Lin- ear State-Space Layer (LSSL) maps a sequence u + by simply simulating a linear continuous-time state-space representation & Ax Bu, y Cz + Du. Theoretically, we show that LSSL models are closely related to the three aforemen- tioned families of models and inherit their strengths. For example, they generalize convolutions to continuous-timg tures of NDEs such as time-scale adaptation. We then incorporate and generalize recent theory on continuous-ting memorization to introduce trainable subset of structured matrices that endow L.SLLs with long-range memory. Empirically, stacking LSSL. layers into a simple deep neural network obtains state-of-the- results across time series benchmarks for long dependencies in sequential image classification, real-world healthcare regression tasks, and speech. On difficult speech classification task with length- 16000 sequences, LSSL outperforms prior approaches by 24 accuracy points, and even outperforms baselines that use hand- crafted features on 100x shorter sequences.
explain common RNN heuristics, and share fea-
Introduction
longstanding challenge in machine learning is efficiently modeling sequential data longer than a few thousand time steps. The usual paradigms for designing sequence models involve recurrence (e.g. RNNs), convolutions (e.g. CNNs), or differential equations (e.g. NDEs), which each come with tradeoffs. For example, RNNs are natural stateful model for sequential data that require only constant computation/storage per time step, but are slow to train and suffer from optimization difficulties (e.g., the "vanishing gradient problem" (31). which empirically limits their ability to handle long sequences. CNNs encode local context and enjoy fast, parallelizable training, but are not sequential, resulting in more expensive inference and an inherent limitation on the context length. NDEs are principled mathematical model that can theoretically address continuous-time problems and long-term dependencies (37] but very inefficient.
Ideally, a model family would combine the strengths of these paradigms, providing properties like parallelizable training (convolutional), stateful inference (recurrence) and time-scale adaptation
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Outsut
Discretize
D
A
- (CA88)
B
B
14
Input
Continuous-time
Recurrent
Convolutional
contmunus
context efficient inference
local information poralilizabl triiing
V imeguior sampling
Figure 1:
(Three views of the LSSL) A Linear State Space Layer layer is a map ue E + yt R. where each feature uı + is defined by discretizing state-space model A, B, C, D with parameter At. space model defines discrete recurrence through combining the
The underlying timescale At into transition matrix A. (Left) As an implicit continuous model, irregularly-spaeed data can he handled hy discretizing the same matrix using different timescale At. (Center) As a recurrent model, inference can be performed efficiently by computing the layer timewise (i.c., one vertical slice at a time (u,, wt, )r (Me+1, 4/41, y.41)..... .... by unrolling the linear recurrence. (Right) As convolutional model, training be performed efficiently by computing the layer depthwise in parallel (i.e., one horizontal slice time (us) )e(4)) (J)))e(L):--.) by convolving with a particular filter.
matrix A and
(differential equations), while handling very long sequences a computationally efficient way. Several recent works have turned this question. These include the CKConv, which models continuous convolution kernel [44]; several ODE-inspired RNNs, such as the UnICORNN [47]; the LMU, which speeds up specific linear recurrence using convolutions [12] [8]; and HiPPO (24). generalization of the LMU that introduces a theoretical framework for continuous-time memorization. However, these model families come the price of reduced expressivity: intuitively, a family that both convolutional and recurrent should be more restrictive than either.
Our first goal is to construct an expressive model family that combines all 3 paradigms while preserving their strengths. The Linear State-Space Layer (LSSL) is a simple sequence model that maps I-dimensional function sequence u(() + y() through an implicit state sx()) by simulating a linear continuous-time state-space representation in discrete-time
a(t) Ax(t) Bu(t)
y(t) = Cxr( + Du(t),
(2)
where A controls the evolution of the system and B, C, D are projection parameters. The LSSL can be viewed as an instantiation of each family, inheriting their strengths (Fig. I
LSSLs are recurrent. a discrete step-size At specified, the LSSL can be discretized into a linear recurrence using standard techniques, and simulated during inference stateful recurrent model with constant memory and computation per time step.
LSSLs are convolutional. The linear time-invariant systems defined by [ are known to be explicitly representable as a continuous convolution. Moreover, the discrete- time version can be parallelized during training using convolutions
LSSLs continuous-time. The LSSL itself is differential equation. As such, it can perform unique applications of continuous-timg models, such as simulating continuous processes, handling missing data [45] and adapting different timescales.
Surprisingly, we show that LSSLS do not sacrifice expressivity, and in fact generalize convolutions and RNNs. First, classical results from control theory imply that all 1-D convolutional kernels can be approximated by an LSSL (5).. Additionally, provide two results relating RNNs and ODEs

---

that may be of broader interest, e.g. showing that some RNN architectural heuristics (such as gating mechanisms) are related to the step-size Åt and can actually be derived from ODE approximations. As corollaries of these results, we show that popular RNN methods are special cases of LSSLLs
The generality of LSSLLs does come with tradeoft'. In particular, challenges that naive LSSL instantiations face when handling long sequences: (i) they inherit the limitations of both RNNs and CNNs remembering long dependencies, and (ii) choosing the state matrix A and timescale At appropriately are critical to their performance, yet learning them is computationally infeasible. We simultaneously address these challenges by specializing LSSLs using a carefully chosen class of structured matrices A, such that (i) these matrices generalize prior work on continuous-tin tiime memory (24] and mathematically capture long dependencies with respect to a learnable family of measures, and (ii) with new algorithms,, LSSLs with these matrices A can be theoretically sped up under certain computation models, even while learning the measure and timescale At.
describe and address two
We empirically validate that LSSLs are widely effective on benchmark datasets and very long time series from healthcare sensor data, images, and speech.
On benchmark datasets, LSSLs obtain SoTA over recent RNN, CNN, and NDE- based methods across sequential image classification tasks (e.g.. by over 10% accuracy sequential CIFAR) and healthcare regression tasks with length-4000 time series (by up to 80% reduction in RMSE).
To showcase the potential of LSSLs to unlock applications with extremely long sequences, we introduce a new sequential CelebA classification task with length-38000 sequences. small LSSLI comes within 2.16 accuracy points of specialized ResNet-18 18 vision architecture that has 10x more parameters and is trained directly on images.
Finally, we test LSSLS on difficult dataset of high-resolutin speech clips, where usual speech pipelines pre-process the signals reduce the length by 100x. When training on the raw length- 1 16000 signals, the LSSL not only (i) outperforms previous methods by over 20 accuracy points in 1/5 the training time, but (ii) outperforms all baselines that use the rrepprceessed length- sequences, overcoming the limitations of hand-crafted feature engincering.
Summary of Contributions
We introduce Linear State-Space Layers (LSSLs), a simple that shares the modeling advantages of recurrent, convolutional, and continuous-time methods. Conversely, we show that RNNs and CNNs can be seen as special cases of LSSLs (Section
transformation
We prove that structured subclass of LSSLs can learn representations that solve continuous-ting memorization, allowing it to adapt its measure and timescale (Section 4.1). We also provide new algorithms for these LSSLs, showing that they can be sped up computationally under an arithmetic complexity model Section 4.2
Empirically, we show that LSSLs stacked into a deep neural network are widely effective on time series data, even (or especially) on extremely long sequences (Section 5).
2 Technical Background
We summarize the preliminaries on differential equations that are necessary for this work. We first introduce two standard approximation schemes for differential equations that we will use to convert continuous-tin time models to discrete-time ttmete and will be used in our results on understanding RNNs. We give further context on the step size or timescale At, which is a particularly important parameter involved in this approximation process. Finally. we provide a summary of the HiPPO framework for continuous-time memorization [24), which will give us a mathematical tool for constructing L.SSLs that can address long-term dependencies.
Approximations of differential equations. Any differential equation a(() (()) has an equivalent integral equation szt) x=(o) Sr f(s xxs)) ds. This can be numerically solved by storing some approximation for x, and keeping fixed inside f((, .)) while iterating the equation. For example, Picard iteration is often used to prove the existence of solutions to ODEs by iterating
3

---

the equation 2(+1(t) == (x( f(s, (s()) ds In other words, it finds a sequence of functions =o(t), 21 (t),... ... that approximate the solution xtt) of the integral equation.
Discretization. On the other hand, for a desired sequence of discrete times 4, approximations to vr(t),, (tt1)..... can be found by iterating the equation z(f++1) = x(44) + pf++1 f((,,(())) ds. Different ways of approximating the RHS integral lead to different discretization schemes. We single out a discretization method called the generalized bilinear transform (GBT) which is specialized to linear ODEs of the form ① Given a step size AI, the GBT update is
(+1 + A!) = (T - abt. AT (1 - at A)a(1) + AI(T ab. BB u(t).
Three important cases are: 0 becomes the classic Euler method which is simply the first-order approximation x(t + At) xxt) + At xt);; = 1 is called the backward Euler method; and
= 1/2 is called the bilinear method, which preserves the stability of the system [T..
In Section 3.2 we will show that the backward Euler method and Picard iteration are actually related to RNNs. On the other hand, the bilinear discretization will be our main method for computing accurate discrete-time approximations of our continuous-ting time models. In particular, define A and 73 to be the matrices appearing in 3 for a
2.2 Then the discrete-tima state-space model is
It = A + Bun
(4)
yt Cr., + Duc.
(5)
At timescale. In most models, the length of dependencies they capture is roughly pro- portional to 1. Thus we also refer to the step size At as a timescale. This is an intrinsic part of converting models have it as an important and non-trainable hyperparameter [24] 47 58 On the other hand, in Section 3.2 we show that the gating mechanism of classical RNNs is version of learning At. Moreover when viewed as a CNN, the timescale At can be viewed as controlling the width of the convolution kernel (Section 3.2p. Ideally, all ODE-based sequence models would be able to automatically learn the proper timescales.
Ar- continuous-tine ODE into discrete-time recurrence, and most ODE-based RNN
Continuous-ting memory. Consider input function u(t), a fixed probability measure w(t), and a sequence of N basis functions such as polynomials. At every time I, the history of u before time I can be projected onto this basis, which yields vector of coefficients sr(t) E RR that represents an optimal approximation of the history of u with respect to the provided measure w. The map taking the function u(t) IR to coefficients xtt) RN is called the High-Order Polynomial Projection Operator (HiPPO) with respect to the measure w. In special cases such as the uniform measure
1[[0, }}} and the exponentially-decaying measure (i)) = exp(-t), Gu al. 24 showed that atf) satisfies differential equation dtt) = ((t)=(t)) + B(f)u(t) (i.e., ) and derived closed forms for the matrix A. Their framework provides a principled way to design memory models handling long dependencies; however, they prove only these few special cases.
3 Linear State-Space Layers (LSSL)
We define our main abstraction, model family that generalizes recurrence and convolutions. Sec- tion 3.1 first formally defines the LSSL, then discusses how to compute it with multiple views. Conversely, Section 3.2 shows that LSSLs are related to mechanisms of the most popular RNNs.
3.1 Different Views of the LSSL
Given a fixed state space representation A, B, C, D, an LSSL is the eequence-to-sequenee mapping defined by discretizing the linear state-space model (1) and (2).
D, and At. It operates on an input u E R representing sequence of length L where each timestep has an H-ddimensional feature vector. Each
Concretely, an LSSL layer has parameters A, B, D,
feature h E [H] defines a sequence (u. (b)) ><{[z]-
( which is combined with a timescale At, to define an
output y (h) E IR via the discretized state-space model (4++5)
Computationally, the discrete-ting time LSSL can be viewed in multiple ways (Fig. I

---

As recurrence. The recurrent state mt-1 E R carries the context of all inputs before time t. The current state 2, and output Y can be computed by simply following equations ( Thus the L.SSL. is a recurrett model with efficient and stateful inference, which can consume a (potentially unbounded) sequence of inputs while requiring fixed computation/storage per time step.
As a convolution.
For simplicity let the initial state be I- = 0. Then
explicitly yields
Uk C (A)* Bug + C (A) Bug + ... + +CABA-- + Buk + Dux.
(6)
Then is simply the (non-circular) convolution y - (A, * Du, where
K,) = (CAA E ERL (CA'B) CCB, CAA-
Thus the LSSL can be viewed as a convolutional model where the entire output E IR MxL can be computed at once by convolution, which can be efficiently implemented with three FFTs.
The computational bottleneck. We make a note that the bottleneck of (i) the recurrence view is matrix-vector multiplication (MVM) by the discretized state matrix A when simulating 4 and (ii) the convolutional view is computing the Krylov function Kr 7 Throughout this section we assumed the LSSL parameters were fixed, which means that A and (A, B, C*) can be cached for efficiency. However, learning the parameters A and At would involve repeatedly re-computing these, which is infeasible in practice. We revisit and solve this problem in Section 4.2
3.2 Expressivity of LSSLS
For model to be both recurrent and convolutional, one might expect it to be limited in other ways. Indeed, while 21 44 also observe that certain recurrences can be replaced with a convolution, they note that it is not obvious if convolutions can be replaced by recurrences. Moreover, while the LSSI. is a linear recurrence, popular RNN models are nonlinear sequence models with activation functions between each time step. We now show that LSSLs surprisingly do not have limited expressivity.
Convolutions are LSSLs. A well-known fact about state-space systems ( is that the output y is related to the input u by a convolution y({) = (TT)u(( r)dr with the impulse response of the system. Conversely, convolutional filter h that is a rational function of degree N can be represented by a state-space model of size N [59]. Thus, an arbitrary convolutional filter h can be approximated by rational function (c.g., by Padé approximants) and represented by an LSSL.
In the particular case of LSSLs with HiPPO matrices (Sections and 4.1p there is another intuitive interpretation of how LSSL relate to convolutions. Consider the special case when A corresponds to a uniform measure (in the literature known the LMU (58] or HiPPO-LegT 24 matrix). Then for a
fixed dt, equation II) is simply memorizing the input within sliding windows of At elements, and equation (2) extracts features from this window. Thus the LSSL can be interpreted as automatically learning convolution filters with learnable kernel width.
RNNs are LSSLS. We show two results about RNNs that may be of broader interest. Our first result says that the ubiquitous gating mechanism of RNNs, commonly perceived as a heuristic to smooth optimization (28), is actually the analog of a step size or timescale At.
Lemma 3.1. A (1-D) gated recurrence I; (1 (z)))=111 + a(z)u, where is the sigmoid function and is an arbitrary expression, can be viewed as the GBT(a = (i.e, backwards-Euler) discretization of a 1-D linear ODE (t)) = =t( + utt).
Proof. Applying a discretization requires positive step size At. The simplest way to parameter- ize a positive function is via the exponential function At exp(2) applied any expression 2. Substituting this into 3 with A = 1, B = 1, a exactly produces the gated recurrence. Li
While Lemma 3.1 involves approximating continuous systems using discretization, the second result is about approximating them using Picard iteration (Section 2). Roughly speaking, each layer of
a deep linear RNN can be viewed as successive Picard iterates xo (f), x1 (4), approximating function ætt) defined by non-linear ODE. This shows that we do not lose modeling power by using
5

---

linear instead of non-linear recurrences, and that the nonlinearity can instead be "moved" to the depth direction of deep neural networks to improve speed without sacrificing expressivity.
Lemma 3.2. (Infinitely) deep stacked LSSL layers of order N with position-wise non-linear functions can approximate any non non-linear ODE a(t) = x f(t,)(t))
We note that many of the most popular and effective RNN variants such as the LSTM 288. GRU [1]] QRNN [5, and SRU [33] involve a hidden state dt E R that involves independently "gating" the H hidden units. Applying Lemma 3.1 they actually also approximate an ODE of the form in Lemma 3.2 Thus LSSLs and these popular RNN models can be seen to all approximate the same type of underlying continuous dynamics, by using Picard approximations in the depth direction and discretization (gates) in the time direction. Appendix gives precise statements and proofs.
3.3
Deep LSSLS
The basic LSSL is defined as a tereenncee---suueneee map from R - R on ID sequences of length L, parameterized by parameters IR N B E NRNxI,CC R IxN E R lx At R. Given an input sequence with hidden dimension H (in other words feature dimension greater than 1), we simply broadcast the parameters B, C, D, At with an extra dimension H. Each of these H copies is learned independently, so that there are H different versions of 1D LSSL processing each of the input features independently. Overall, the standalone LSSL layer is a sequence-to-scqueeee map with the same interface as standard sequence model layers such as RNNs, CNNs, and Transformers.
The full LSSL architecture in deep neural network is defined similarly standard sequence models such as deep ResNets and Transformers, involving stacking LSSL layers connected with normalization layers and residual connections. Full architecture details are described Appendix including the initialization of A and At, computational details, and other architectural details.
4 Combining LSSLs with Continuous-time Memorization
In Section 3 we introduced the LSSL model and showed that it shares the strengths of convolutions and recurrences while also generalizing them. We now discuss and address its main limitations, in particular handling long dependencies (Section 4. and efficient computation (Section 4.2
4.1 Incorporating Long Dependencies into LSSLS
The generality of LSSLs means they can inherit the issues of recurrences and convolutions at address- ing long dependencies (Section [ For example, viewed as a recurrence, repeated multiplication by A could suffer from the vanishing gradients problem [39 44]. We confirm empirically that LSSLs with random state matrices A are actually not effective (Section 5.4] as a generic sequence model.
However, one advantage of these mathematical continuous-time models is that they are theoretically analyzable, and specific A matrices can be derived address this issue. In particular, the HiPPỘ framework (Section 2 describes how to memorize function in continuous time with respect to measure w [24]. This operator mapping function to a continuous representation of its past denoted (w), and was shown to have the form of equation (I) in three special cases. However, these matrices are non-trainable in the sense that no other A matrices were known be hippo operators.
To address this, we theoretically resolve the open question from 24 showing that hippo(w) for any measure w results ( with structured matrix A.
Theorem 1 (Informal). For an arbitrary measure the optimal memorization operator hippo(w) has the form (() = Az(()= + Bu(l) T for a low recurrence-width (LRW) 177) state matrix A.
For measures covering the classical orthogonal polynomials (OPs) [52 (in particular, corresponding to Jacobi and Laguerre polynomials), there even more structure. Corollary 4.1. For corresponding to the classical OPs, hippo(w') is 3-quasiseparable.
Although beyond the scope of this section, we mention that LRW matrices are a type of structured matrix that have linear MVM 17 In Appendix D we define this class and prove Theorem T Quasi-
To be precise, the measures that correspond to orthogonal polynomials
52

---

separable matrices are a related class of structured matrices with additional algorithmic properties.
We define these matrices in Definition and prove Corollary 4.1 Appendix [D3
Theorem teells us that a LSSL. that uses a state matrix within a particular class of structured matrices would carry the theoretical interpretation of continuous-time memorization. Ideally, would be able to automatically learn the best A within this class; however, this runs into computational challenges which we address next (Section 4.2). For now, we define the LSSL-fixed or LSSL-f to be one where the A matrix is fixed to one of the HiPPO matrices prescribed by 24
4.2 Theoretically Efficient Algorithms for the LSSL
Although A and At are the most critical parameters of an LSSL which govern the state-space (c.f. Section 4.1) and timescale (Sections 2 (32). they are not feasible to train in a naive LSSL. In particular, Section 3.1 noted that it would require efficient matrix-veclor multiplication (MVM) and Krylov function ( for A to compute the recurrent and convolutional views, respectively. However, the former seems to involve a matrix inversion (3) while the latter seems to require powering A up L times.
In this section, we show that the same restriction of A to the class of quasiseparable (Corollary 4.1 which gives LSSL the ability to theoretically remember long dependencies, simultaneously grants it computational efficiency.
First of all, it is known that quasiseparable matrices have efficient (linear-tmme) MVM [4]. We show that they also have fast Krylov functions, allowing efficient training with convolutions.
Theorem 2. For any k-quasiseparable matrix A (with constant k) and arbitrary B, C, the Krylov
function (r,A, B, C) can be computed in quasi-linear time and space Ö(N + L) and logarithmic depth (i.e., is parallelizable). The operation count an exact arithmetic model, not accounting for bit complexity or numerical stability.
We remark that Theorem 2 is non-obvious. To illustrate, is easy to see that unrolling 7 for a general matrix A takes time L Even if A is extremely structured with linear computation, it requires LN operations and linear depth. The depth can be reduced with the squaring technique (batch multiply by
A, A?, .).... but this then requires LN intermediate storage. In fact, the algorithm for Theorem 2 is quite sophisticated (Appendix E and involves a divide-and-conquee recursion over matrices of polynomials, using the observation that is related to the power series C(I Ar)-
Unless specified otherwise, the full LSSL refers to an LSSL with A satisfying Corollary 4.1 In conclusion, learning within this structured matrix family simultaneously endows LSSLs with long- range memory through Theorem [ and is theoretically computationally fcasible through Theorem 2 We note the caveat that Theorem 2 is over exact arithmetic and not floating point numbers, and thus treated more as a proof of concept that LSSLS can be computationally efficient in theory. We comment more on the limitations of the LSSL in Section 0
5 Empirical Evaluation
We test LSSL empirically range of time series datasets with sequences from length 160 up to 38000 (Sections and (5.2). where they substantially improve over prior work. We additionally validate the computational and modeling benefits of LSSLs from generalizing all three main model families (Section 5.3), and analyze the benefits of incorporating principled memory representations that can be learned (Section 5.4).
Baselines. Our tasks have extensive prior work and evaluate against previously reported best results. We highlight our primary baselines, three very recent works explicitly designed for long sequences: CKConv continuous-time CNN) (44), UnICORNN (an ODE-inspired RNN) 47 and
Neural Controlled/Rough Differential Equations (NCDE/NRDE) (a sophisticated NDE) 3 37
These are the only models we aware of that have experimented with sequences of length 100k.
5.1 Image and Time Series Benchmarks
7

---

Table I: (Pixel-by-pixel image classification.) (Top) methods. (Middle) recurrent baselines. (Bottom) convolutional + other baselines.
Table 2: (Vital signs prediction.) RMSE for pre- dicting respiratory rate (RR), heart rate (HR), and blood oxygen (SpO2). * "idiccates our own runs to complete results for the strongest baselines.
Model sMNIST
PMNIST
sCIFAR
Model
RR
HR
SpO2
LSSL 99.53
98.76
84,65
LSSL-fixed
99.50
98.60
81.97
LSSL
0.350
0,432
0.141
LSSL-fixed
0.378
0.561
0.221
LipschizZRNN
99.4
96.3
64.2
LMUFFT 12
98.49
UnICORNN
47
1.06
1.39
0.869
UNIcoRNN
98.4
coRNN
47
1.45
1.81
HiPPO-RNN
98.9
98.3
61.1
CKConv
1.214
2.05
1.051*
URGRU 25
99.27
96.51
74.4
NRDE
37
1,49
2.97
1.29
IndRNN 34
99.0
96.0
IndRNN 47
1.47
2.1
Dilated RNN
8
98.0
96.1
expRNN 47
1.57
1.87
L.STMMM 56
98.4
95.2
72.2
LSTM
10.7
Transformer
2.61*
12.2*
3.02*
CKCony
44
99.32
98.54
63.74
TrellisNet
99.20
98.13
73.42
XGBoost
55
1.67
4.72
1.52
TCN B
99.0
97.2
Random Forest
651
1.85
5.69
1.74
Transformer 56
98.9
97.9
62.2
Ridge Regress.
55
3.86
17.3
4.16
Table 3:
(Sequential
CelebA Classification.)
We test on the sequential MNIST, permuted MNIST, and sequential CI- FAR tasks [ popular benchmarks which were originally designed to test the ability of recurrent models to capture long-term dependencies
LSSL-f
ResNet
of length up to 1k 2) LSSL sets SoTA on sCIFAR by more than 10 points. We note that all results were achieved with at least 5x fewer parameters than the previous SoTA (Appendix (F).
Att.
78,89
81.35
MSO
92.36
93.92
Smil.
90.95
92.89
WL
90.57
93.25
We additionally use the BDIMC healtheare datasets (Table 2) a suite of widely studied time series regression problems of length 4000 on estimating vital signs. LSSL reduces RMSE by more than two-thirds on datasets.
5.2 Speech and Image Classification for Very Long Time Series
Raw speech is challenging for ML models due to high-frequene, sampling resulting in very long sequences. Traditional systems involve complex pipelines that require feeding mixed-and-matched hand-crafted features into DNNs 42] Table 4 reports results for the Speech Commands (SC) dataset (3T) for classification of I-sccond audio clips. Few methods have made progress on the raw speech signal, instead requiring pre-processing with standard mel-frequency cepstrum coefficients (MFCC). By contrast, LSSL sets SoTA on this dataset while training on the raw signal. We note that MFCC extracts sliding window frequency coefficients and thus is related to the coefficients ar() defined by L.SL-f (Section 2 Section 4.1 [24], Appendix D). Consequently, LSSL may be interpreted automatically learning MFCC-type features in trainable basis.
To stress-test the LSSL's ability to handle extremely long sequences, we create challenging new sequential-CelebA task, where we classify 178 x 218 images 38000-length sequences for 4 facial attributes: Attractive (Att), Mouth Slightly Open (MSO), Smiling (Smil.), Wearing Lipstick (WL) 36. We chose the 4 most class-balanced attributes to avoid well-known problems with class imbalance. LSSL-f comes close to matching the performance of a specialized ResNet-18 image classification architecture that has 10x the parameters (Table 3). We emphasize are the first to demonstrate that this is possible to do with a generic sequence model.
5.3 Advantages of Recurrent, Convolutional, and Continuous-time Models
We validate that the generality of LSSLs endows it with the strengths of all three families.
Convergence Speed. As a recurrent and NDE model that incorporates new theory for continuous- time memory (Section 4. the LSSL has strong inductive bias for sequential data, and converges rapidly SoTA results on our benchmarks. With its convolutional view, training can be parallelized and it is also computationally efficient in practice. Table compares the time takes the LSSL-f

---

Table 4: (Raw Speech Classification; Timescale Shift.) (Top): Raw signals (length 16000); indicates lest-time change in sampling rate by a factor of f. (Bottom): Pre-processed MFCC features used prior work (length 161). x denotes computationally infeasible.
LSSL.
LSSL--
CKConv
UnICORNN
N(C/R)DE
ODE-RNN
45
GRU-ODE 16
1-1
95.87
90.64
71.66
11.02
16.49
X
X
1-2 2
88.66
78.01
65.96
11.07
15.12
X
MFCC
93.58
92.55
95.3
90.64
89.8
65.9
47.9
Table 5: (Modeling and Computational Benefits LSSLs.)) In each benehmark category, we compare the number of epochs (ep.) it takes L.SSI- to reach the previous SoTA (PSoTTA) results as well as near-SoTA target. We also report the wall clock time it took to reach PSoTA relative the previous best model.
Permuted MNIST
BDIMC Heart Rate
Speech Commands RAW
98% Acc.
PSoTA
Time
1.5 RMSE PSoTA
Time
65% Ace.
PSoTA
Time
LSSL-fixee
16 ep.
104 ep.
0.19x
cp.
ep.
0.07
ep.
10 ep
0.14x
CKConv
118 ep.
200 ep.
1.0x
X
x
188 ep.
280 ep.
1.0x
UnICORNN
ep.
x
x
ep
467 ep.
1.0x
X
x
X
achieve SoTA, in either sample (measured by epochs) or computational (measured by wall clock) complexity. In all cases, I.SSLs reached the target in fraction of the time of the previous model.
Timescale Adaptation. Table also reports the results continuous-ting models that are able to handle unique settings such as missing data in time series, or test-time shift in timescale (we note that this is a realistic problem, e.g., when deployed healthcare models are tested on EEG signals that are sampled at different rate 48 49)). We note that many of these baselines were custom designed for such settings, which is of independent interest. On the other hand, LSSLs perform timescale adaptation by simply changing its At values at inference time, while still outperforming the performance of prior methods with no shift. Additional results on the Character TrajatteTrreecsoriies dataset from prior work
3 44
are in Appendix F where LSSL is competitive with the best baselines.
5.4 LSSL Ablations: Learning the Memory Dynamics and Timescale
We demonstrate that the At and A parameters, which LSSLs are able to automatically learn in contrast to prior work, are indeed critical to the performance of these continuous-time models. We note that learning At adds only O(H) parameters and learning A adds O(N) parameters, adding less than 1% parameter count compared to the base models with (HN) parameters.
Memory dynamics A. We validate that vanilla LSSLs suffer from the modeling issues described in Section 4 We tested that LSSLs with random A matrices (normalized appropriately) perform very poorly (e.g., 62% on PMNIST). Further, we note the consistent increase in performance from LSSL-f LSSL despite the negligible parameter difference. These ablations show that (i) incorporating the theory of Theorem i actually necessary for LSSLs, and (ii) further training the structured A is additionally helpful. which can be interpreted as learning the measure for memorization (Section 4.1)
Timescale Al. Section 3.2 showed that L.SL's ability to learn AL is its direct generalization of the critical gating mechanism of popular RNNs, which previous ODEe- RNN models (12 24 47 58 cannot learn. We note that on SCIFAR, LSSL-f with poorly-specified At gets only 49.3% accuracy. Additional results in Appendix[[shoe that learning At alone provides an orthogonal boost to learning A, and visualizes the noticeable change in At over the course of training.
6 Discussion
In this work we introduced simple and principled model (LSSL) inspired by a fundamental representation of physical systems. We showed theoretically and empirically that generalizes and inherits the strengths of the main families of modern time series models, that its main limitations of long-term memory can be resolved with new theory on continuous-time memorization, and that empirically effective on difficult tasks with very long sequences.

---

Related work. The LSSL is related to several rich lines of work on recurrent, convolutional, and continuous-tiin time models, as well as sequence models addressing long dependencies. Appendix A provides an extended related work connecting these topics.
Tuning. Our models very simple, consisting of identical L(inear)SSL. layers with simple position- wise non-linear modules between layers (Appendix [B. Our models were able to train at much higher learning rates than baselines and were not sensitive hyperparameters, of which we did light tuning primarily on learning rate and dropout. In contrast to previous baselines 4 31 44
we did not use hyperparameters for improving stability and regularization such as weight decay, gradient clipping. weight norm, input dropout, etc. While the most competitive recent works introduce at least one
hyperparameter of critical importance (e.g. depth and step size (37], a and At [47]. w/ [44 that are
difficult to tune, the LSSL-fixed has only At, which the full LSSL can even learn automatically (at the expense of speed).
Sections and and Fig. [ mention that a potential benefit of having the recurrent representation of LSSLS may endow with efficient inference. While this is theoretically possible, this work did not experiment on any applications that leverage this. Follow-up work showed that it is indeed possible in practice to speed up some applications at inference time.
Limitations.
Theorem 2 algorithm is sophisticated (A (Appendix D) and was not implemented in the first version of this work. A follow-up to this paper found that it is not numerically stable and thus not usable on hardware. Thus the algorithmic contributions in Theorem seevvve the purpose of a proof-of- -rooc-tf-concept that fast algorithms for the LSSL. do exist in other computation models (i.e., arithmetic operations instead of floating point operations). and leave an open question as to whether fast, numerically stable, and practical algorithms for the LSSL exist.
As described in Appendix B by freezing the A matrix and At timescale, the LSSL-fiXed is able to be computed much faster than the full LSSL, and is comparable to prior models in practice (Table 5). However, beyond computational complexity, there is also a consideration of space efficiency. Both the LSSL and LSSL-fixed suffer from a large amount of space overhead (described in Appendix using (NL) instead of OLL) space when working on a ID sequence of length L L- that essentially stems from using the latent state representation of dimension N. Consequently, the LSSL can be space inefficient and we used multi-GPU training for our largest experiments (speech and high resolution images, Tables and and
These fundamental issues with computation and space complexity were revisited and resolved in follow-up work to this paper, where new state space model (the Structured State Space) provided new parameterization and algorithms for state spaces.
Conclusion and future work. Modern deep learning models struggle in applications with very long temporal data such as speech, videos, and medical time-series. We hope that our conceptual and technical contributions can lead to new capabilities with simple, principled, and less engineered models. We note that our pixel-level image classification experiments, which use no heuristics (batch norm, auxiliary losses) or extra information (data augmentation), perform similar to early convnet models with vastly more parameters, and is in the spirit of recent attempts at unifying data modalities with a generic sequence model [18]. Our speech results demonstrate the possibility of learning better features than hand-crafted processing pipelines used widely in speech applications. We are excited about potential downstream applications, such as training other downstream models on top of pre-trained state space features.
Acknowledgments
We thank Arjun Desai, Ananya Kumar, Laurel Orr, Sabri Eyuboglu. Dan Fu, Mayee Chen, Sarah Hooper, Simran Arora, and Trenton Chang for helpful feedback on earlier drafts. We thank David Romero and James Morrill for discussions and additional results for baselines used in our experiments. This work was done with the support of Google Cloud credits under HAI proposals 54099417080 77083 and 5781927 19349. AR and IJ are supported under NSF grant CCF- 176441. KS supported by the Wu Tsai Neuroscience Interdisciplinary Graduate Fellowship. We gratefully acknowledge the support of NIH under No. U54EB020405 (Mobilize), NSF under Nos. CCF1 (Beyond Sparsity), CCF1 563078 (Volume to Velocity), and 1937301 (RTML): ONR under No. N00014171 41712266 (Unifying Weak Supervision); ONR N00014-20-1-2488 Understanding and Applying Non-Fuclided Geometry in Machine Learning; N000142012275 (NEPTUNE); the Moore Foundation, NXP, Xilinx,
10

---

LETI-CEA, Intel, IBM, Microsoft, NEC, Toshiba, TSMC, ARM, Hitachi, BASE, Accenture, Ericsson, Qualcomm, Analog Devices, the Okawa Foundation, American Family Insurance, Google Cloud, Salesforce, Total, the HAI-AWS Cloud Credits for Research program, the Stanford Data Science Initiative (SDSI), and members of the Stanford DAWN project: Facebook, Google, and VMWare. The Mobilize Center is a Biomedical Technology Resource Center, funded by the NIH National Institute of Biomedical Imaging and Bioengineering through Grant P41EB027060. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views, policies, endorsements, either expressed or implied, of NIH, ONR, or the U.S. Government.
References
[1] George B. (George Brown) Arfken, Hans Jürgen Weber, and Frank E Harris. Mathematical methods for physicists: : comprehensive guide George B. Arsken, Hans J. Weber, Frank Harris. Academic Press, Amsterdam, 7th ed. edition, 2013. ISBN 0- 0-12-384654-.
[2] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In The International Conference Machine Learning (ICMI.,, pages 1 120-1128, 2016.
[3] Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:183..0122 2018.
[4] Shaojic Bai, J Zico Kolter, and Vladlen Koltun. Trellis networks for sequence modeling. The International Conference Learning Representations (ICLR), 2019.
[5] James Bradbury, Stephen Merity, Caiming Xiong, and Richard Socher. Quasi-recurrent neural networks. arXiv preprint
2016.
[6] John Charles Butcher and Nicolette Goodwin. Numerical methods for ordinary differential equations, volume 2. Wiley Online Library, 2008
[7] Bo Chang, Minmin Chen, Eldad Haber, and Ed H Chi. Antisymmetricrnn: A dynamical system view on recurrent neural networks. In International Conference on Learning Representations, 2019.
[8] Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Withrock, Mark Hasegawa-Johnson, and Thomas S Huang. Dilated recurrent neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[9] Zhengping Che, Sanjay Purushotham, Kyunghyun Cho, David Sontag, and Yan Liu. Recurrent neural networks for multivariate time series with missing values. Scientific reports, 8(1):1-12, 2018.
[10] Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In Advances in neural information processing systems, pages 5553365 2018.
[11] T. S. Chihara. An introduction orthogonal polynomials. Dover Books Mathematics. Dover Publications, 2011. ISBN 9780486479293.
[12] Narsimha Chilkuri and Chris Eliasmith. Parallelizing legendre memory unit training. The International Conference on Machine Learning (ICML),
[13] François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceed- ings of the IEEE conference on computer vision and pattern recognition, pages 1251-1258, 2017.
[14] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv: 14/2.3555
2014.
11

---

[15] Jared Quincy Davis, Albert Gu, Tri Dao, Krzysziof Choromanski, Christopher Ré, Percy Liang, and Chelsea Finn. Catformer: Designing stable transformers via sensitivity analysis. In The International Conference on Machine Learning (ICMI), 2021.
[16] Edward De Brouwer, Jaak Simm, Adam Arany, and Yves Moreau. Gru-ode-bayes: Continuous modeling of sporadically-observe time series. In Advances Neural Information Processing Systems (NeurIPS), 2019.
[17] Christopher De Sa, Albert Gu, Rohan Puttagunta, Christopher Ré, and Atri Rudra. A two- pronged progress in structured dense matrix vector multiplication. In Proceedings of the Twenty-Ninth Annual ACM-SIAN Symposium on Discrete Algorithms, pages 1060-1079. SIAM, 2018.
[18] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
[19] Y. Eidelman and I. Gohberg. On a new class of structured matrices. Integral Equations and Operator Theory, 34, 1999.
[20] N Benjamin Erichson, Omri Azencot, Alejandro Queiruga, Liam Hodgkinson, and Michael W Mahoney. Lipschitz recurrent neural networks. In International Conference on Learning Representations, 2021.
[21] Karl J Friston, Lee Harrison, and Will Penny. Dynamic causal modelling. Neuroimage, 19(4): 1273-1302, 2003.
[22] Ken-ichi Funahashi and Yuichi Nakamura. Approximation of dynamical systems by continuous time recurrent neural networks. Neural networks, 6(6):801-806, 1993.
[23] Gene H Golub and Charles F Van Loan. Matrix computations, volume 3. JHU press, 2013.
[24] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Essun-TTin Lin, editors, Advances in Neural Information
Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL http:::tt///pptttt /ttpps://proceedinggs newrriigg.....nnpooe. neuripp http://000/aaaa111000060eaaaaaa0
htt.aa/cccccccroooo--aatttaat.ta Abstract. html
[25] Albert Gu, Caglar Gulcehre, Tom Le Paine, Matt Hoffman, and Razvan Pascanu. Improving the gating mechanism of recurrent neural networks. In The International Conference on Machine Learning (ICML), 2020.
[26) Ramin Hasani, Mathias Lechner, Alexander Amini, Lucas Liebenwein, Max Tschaikowski, Gerald Teschl, and Danicla Rus. Closed-form continuous-depth models. arXiv preprint arXiv:2106. 13898, 2021.
[27] Ramin Hasani, Mathias Lechner, Alexander Amini, Daniela Rus, and Radu Grosu. Liquid time-constant networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[28] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
[29] Ian D Jordan, Piotr Aleksander Sokót, and Memming Park. Gated recurrent units viewed through the lens of continuous time dynamical systems. Frontiers in computational neuroscience, page 67, 2021.
[30] Anil Kag, Ziming Zhang, and Venkatesh Saligrama. Rnns incrementally evolving on an equilibrium manifold: A panacea for vanishing and exploding gradients? In International Conference on Learning Representations, 2020.
[31] Patrick Kidger, James Morrill, James Foster, and Terry Lyons. Neural controlled differential equations for irregular time series. arXiv preprint arXiv:2005.08920 2020.
12

---

[32] Mathias Lechner and Ramin Hasani. Learning long-term dependencies in irregularly-sappled time series. arXiv preprint Nal:2006.044113 2020.
[33] Tao Lei, Yu Zhang, Sida I Wang, Hui Dai, and Yoav Artzi. Simple recurrent units for highly 2017.
parallelizable recurrence. arXiv preprint
[34] Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently recurrent neural network (IndRNN): Building longer and deeper RNN. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5457-5466, 2018
[35] Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han. Understanding the difficulty of training transformers. The International Conference on Machine Learning (ICML), 2020.
[36] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In ICCV, pages URL URLhttp::/ http:://blpp... uni trier de/ httpa///ooo//cc///cccc//o///////
IEEE Computer Society. 2015, ISBN 978-1-48 10------7---99111
htm
[37] James Morrill, Cristopher Salvi, Patrick Kidger, James Foster, and Terry Lyons. Neural rough differential equations for long time series. The International Conference on Machine Learning (ICML), 2021. 2021.
[38] Murphy Yuezhen Niu, Lior Horesh, and Isaac Chuang. Recurrent neural networks in the eye of differential equations. arXiv preprint arXiv:1904. 12933, 2019.
[39] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310-1318, 2013.
[40] Clément Pernet. Computing with quasiseparable matrices. In Proceedings of the ACM on International Symposium on Symbolic and Algebruic Computation, pages 389-396, 2016.
[41] KB Petersen and MS Pedersen. The matrix cookbook, version 20121115. Technical Univ. Denmark, Kongens Lyngby, Denmark, Tech. Rep, 3274, 2012.
[42] M. Ravanelli, T. Parcollet, and Y. Bengio. The pytorch- speech recognition toolkit. In Proc. of ICASSP, 2019.
[43] David W Romero, Robert-Jan Bruintjes, Jakub M Tomezak, Erik J Bekkers, Mark Hoogendoorn, and Jan C van Gemert. Flexconv: Continuous kernel convolutions with differentiable kernel sizes, arXiv preprint arXiv:2110.08055 2021.
[44] David W Romero, Anna Kuzina, Erik Bekkers, Jakub M Tomczak, and Mark Hoogendoorn. Ckconv: Continuous kernel convolution for sequential data. arXiv preprint arXiv:2 2021.
[45] Yulia Rubanova, Tian Qi Chen, and David K Duvenaud. Latent ordinary differential equations for trregularly-samplee time series. In Advances in Neural Information Processing Systems, pages 5321-5331, 2019.
[46] T. Konstantin Rusch and Siddhartha Mishra. Coupled oscillatory recurrent neural network (cornn): An accurate and (gradient) stable architecture for learning long time dependencies. In International Conference on Learning Representations, 2021.
[47] Konstantin Rusch and Siddhartha Mishra. Unicorn: recurrent model for learning very long time dependencies. The International Conference on Machine Learning (ICML), 2021.
[48] Khaled Saab, Jared Dunnmon, Christopher Ré, Daniel Rubin, and Christopher Lee-Messer. Weak supervision as efficient approach for automated seizure detection in electroencephalog- raphy. NPJ Digital Medicine, 3(1):1-12, 2020.
[49] Vinit Shah, Eva Von Weltin, Silvia Lopez, James Riley McHugh, Lillian Veloso, Meysam Golmohammadi, lyad Obeid, and Joseph Picone. The Temple University hospital seizure detection corpus. Frontiers in neuroinformatics. 12:83, 2018.
13

---

[50] Jie Shen, Tao Tang, and Li-Lian Wang. Orthogonal Polynomials and Related Approximation Results, pages 47-140. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. ISBN 978-
3-540-71041-7. doi: 10. 1011007/978.3554--00001---
URI. httph::t///ooo 2xgg/1.1007/
978-3-540-71041-7.3
[51] Victor Shoup. computational introduction to mumber theory and algebra. university press, 2009.
Cambridge
[52] G. Szegö. Orthogonal Polynomials. Number v.23 in American Mathematical Society colloquium publications. American Mathematical Society, 1967. ISBN 9780821889527.
[53] G. Szegö. Orthogonal Polynomials. American Mathematical Society: Colloquium publications. American Mathematical Society, 1975. ISBN 9780821810231.
[54] Corentin Tallec and Yann Ollivier. Can recurrent neural networks warp time? The Interna- tional Conference on Learning Representations (ICLR), 2018.
[55] Chang Wei Tan, Christoph Bergmeir, Francois Petitjean, and Geoffrey I Webb. Time series extrinsic regression. Data Mining and Knowledge Discovery, pages 1-29, 2021. doi: https: //doi.org/10.100//ss000 100---00011-020-077400 021-00745-9.
[56] Trieu Trinh, Andrew M Dai, Minh-Thang Luong, and Quoc V Le. Learning longer-term dependencies in RNNs with auxiliary losses. In The International Conference on Machine Learning (ICML), 2018.
[57] 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 Informa- tion Processing Systems (NeurIPS). 2017.
[58] Aaron Voelker, Ivana Kajić, and Chris Eliasmith. Legendre memory units: Continuous-time representation in recurrent neural networks. In Advances in Neural Information Processing Systems, pages 15544-15553, 2019.
[59] Robert I. Williams, Douglas A Lawrence, et al. Linear state-space control systems. Wiley Online Library, 2007.
[60] Max A Woodbury. Inverting modified matrices. Memorandum report, 42:106, 1950.
[61] Guofeng Zhang, Tongwen Chen, and Xiang Chen. Performance recovery digital imple- mentation of analogue systems. SIAM journal on control and optimization, 45(6):2207-2223,
2007.
[62] Huaguang Zhang, Zhanshan Wang, and Derong Liu. A comprehensive review stability analysis of continuous-time recurrent neural networks. IEEE Transactions Neural Networks and Learning Systems,
2014.
14


Reviews:
[{"review_id": "wxVZbmDIaQc", "reviewer": "Reviewer_1sLL", "summary": "This paper proposes a sequence-to-sequence model whose main building block is a linear layer called LSSL based on a standard dynamical system in control theory, including an internal ODE. LSSL is shown to implement both a convolutional and recurrent network, and, conversely, to be able, when stacked, to approximate any convolution and recurrent network with gating mechanisms, making the proposed model expressive. By endowing LSSL with the preexisting memory mechanism HiPPO, the resulting model MLSSL, and its counterpart SLLSSL that learns this operator, become computationally tractable and avoid gradient vanishing issues. The models are empirically validated on a number of regression and classification tasks showing their computational and performance advantages.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Contribution\n\nAs described in the submission, the proposed model seems novel, computationally and numerically efficient, and well motivated by theoretical considerations. The extent of the contributions is significant and may be of broad interest for the NeurIPS community. The versatile abilities of MLSSL and SLLSSL and their thorough analysis further strengthen the contribution.\n\nFurthermore, the claims of the paper are validated by a strong set of experiments with a provided code that seems complete and runnable, showing the clear advantage of MLSSL and SLLSSL to tackle long sequences by establishing state-of-the-art results on challenging tasks with reduced number of parameters and computational cost.\n\nUnfortunately, this paper is too long and dense, with a long appendix, to adequately review given the short allocated reviewing time and high number of papers to review. I appreciate the efforts of the authors to provide a strong and well motivated paper, but I am not sure whether the NeurIPS reviewing system can assimilate such papers. Nonetheless, I would have some questions for the authors.\n\n### Learning $\\Delta t$ and Matching the Input and Output Times\n\nThe main issue of the paper as I understand it is how the learned timesteps are handled with respect to the input time series temporality. In Lemma 3.1, the learned $\\Delta t$ most likely does not correspond to the actual temporal discrepancy between $x_t$ and $x_{t+1}$ (i.e., $\\Delta t \\neq 1$). This decorrelates the step size $\\Delta t$ and the temporality of $x$ from the temporality of the input $u$, at least when following the dynamical system interpretation of Equation (3). Could the authors clarify this point, and in particular explain how this does not partly invalidate the dynamical viewpoint of LSSL?\n\n### Sequence to Sequence Tasks\n\nTo the best of my understanding, all considered tasks in the experiments of the paper deal with classification and regression to scalar values. This is unfortunate, given that the proposed architecture is a sequence-to-sequence model. Could any sequence-to-sequence task may be considered?\n\n### Generalization Vs. Approximation\n\nThe claim of lines 57-58 that LSSL generalizes convolutions and CNNs should be corrected, as it is shown in Section 3.2 that it can only approximate them, which is substantially different.\n\n\n## Writing\n\nThis submission can be difficult to read for the uninitiated reader given the information density and high number of introduced notions. Nonetheless, the claims and results presented by the authors are clear and well explained throughout the paper, especially as the submission is fully self-contained thanks to a thorough appendix.\n\n\n\n## Overall Sentiment\n\nWhile the submission externally seems solid, I am unable to commit to a strong acceptation recommendation due to the aforementioned inherent time constraints of the NeurIPS reviewing system. Therefore, and partly because of the concerns expressed above, I am only suggesting a \"Marginally above the acceptance threshold\", but I am strongly willing to change my score following the authors' response and discussion phase with the other reviewers.\n\n\n***\n\n## Post-Rebuttal Update\n\nI acknowledge the authors' response and thank them for their answers. The responses to all reviewers are thorough and seem to tackle the raised concerns, especially regarding readability and positioning. As far as I am concerned, my concerns are appropriately addressed. In particular, I believe that the solutions proposed by the authors will improve the quality of the submission.\n\nTherefore, within the already exposed limits of my appreciation, I think that this paper can be accepted, thus raising my score to \"Good paper, accept\" but keeping my low confidence rating.\n\n**Second update:** Following the authors' convincing responses and further investigation, I still think that this paper should be accepted but with a higher confidence. I consequently choose to raise my confidence score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "UgcI99gqb6D", "reviewer": "Reviewer_LpSP", "summary": "The authors proposed structured learnable linear state-space layers as a way to unify recurrence, convolutions, and continuous-time representations. The performance of SLLSSL is evaluated on a set of sequential benchmarks against a couple of modern and classic baseline deep models. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "remarks:\n+ The experimental framework is properly designed and shows the benefits of the proposed SLLSSL approach. \n+ The theoretical results are insightful; proofs are provided in Appendix and the code is provided in full. Very much appreciated!\n+ Incorporating convolution operators in LSSL is novel.\n\nConcerns:\n\n-\tI believe that the approach proposed here has limited novelty. In particular, the bilinear transformation which is core to the method proposed was historically introduced as dynamic causal models [1] back in 2003, and more recently as Liquid time-constant networks (LTCs) [2]. I believe authors should clearly differentiate their framework from DCMs and LTCs while including them in their experimentation. In particular, 1) I suggest authors formally state what is new in LSSL compared to LTCs? 2) The time-gating discovery of this paper is very similar to that of the liquid time-constant proposed in LTCs. Please comment. 3) The fact that authors find 5x fewer parameters than the previous SoTA was observed for networks comprised of LTCs. 4) The expressivity of the models is thoroughly discussed in LTCs whereas LSSL does not provide formal evidence. What is new here in this regard? 5) How would LTC networks equipped with HIPPO similar to the SLLSSL models perform in the experimental setup provided in the paper. \n\n-\tAll ODE-based models provably suffer from gradient issues [3] ergo learning long-term dependencies (similar to LSSL) and naturally require modules to tackle this shortcoming. The authors use HIPPO in this case. But there are many fundamental approaches proposed for solving the long-term dependency learning capabilities of RNNs and CT-RNNs that are missing in this paper. In particular, orthogonal models [4] Lipschitz RNNs [5], and mixed memory architectures such as ODE-LSTMs [3] are encouraged to be used as baselines in all experiments concerning recurrent networks. \n\n-\t[less critical] In the Intro, the authors draw a solid line between RNN models and continuous-time models which I find inaccurate. RNNs are a discretized version of CT networks. In line 65, the Authors mention the limitations of RNNs in remembering long dependencies, but in fact, all ODE-based RNNs also suffer from this limitation [3], because CT models are where RNNs are originally coming from.  The state-space layer is indeed a continuous-time network, not the other way around.\n\n\n[1] Friston, Karl J., Lee Harrison, and Will Penny. \"Dynamic causal modelling.\" Neuroimage 19.4 (2003): 1273-1302.\n[2] Hasani, Ramin, et al. \"Liquid time-constant networks.\" arXiv preprint arXiv:2006.04439 (2020).\n[3] Lechner, Mathias, and Ramin Hasani. \"Learning long-term dependencies in irregularly-sampled time series.\" arXiv preprint arXiv:2006.04418 (2020). AAAI 2021\n[4] Lezcano-Casado, Mario, and David Martınez-Rubio. \"Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group.\" International Conference on Machine Learning. PMLR, 2019.\n[5] Erichson, N. Benjamin, et al. \"Lipschitz Recurrent Neural Networks.\" International Conference on Learning Representations. 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed partially the limitations of their approach.\nI do not see any potential negative societal impact from this work.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}, {"review_id": "UZg8z3S6aPt", "reviewer": "Reviewer_ZFwG", "summary": "Explored a linear state space dynamical system as a sequence transformation paradigm'\nExplored and discussed the ability of this representation to explain some models like linear convolution and linear RNN\nPresented mathematical analysis and empirical experiments for the proposed model", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity and Quality:\nI think the idea is very interesting and authors have a done descent job in presenting details. However, my main concern with this paper is readability. The 9 pages submitted as main paper was not sufficient for me to understand the whole content and answer some of my basic questions like:\n1. Dimension of y(t):\nIn the model definition y is one dimensional, which is not necessarily that appealing for many deep neural architectures where intermediate dimensions might have different dimensions. However, in appendix A.4, this is generalized to M > 1.  \n2. What is an example of coefficients A, B, C and D?\nThe difficulty of training A has been mentioned multiple times in the paper but A is introduced for first time in appendix A.2, line 521.\n3. Same argument with \\delta t. While it plays really important role in equations and discussions, there is not much details about it until reading appendices. \n4. Reading the first 9 pages and experiments, I did not have any clue how the stack of LSSL look like.\nSection A.4 was needed. And after that I am guessing the class of RNNs discussed here are the ones with non-linearity on depth and not on time. If thats right, I am not sure if the sentencing of the theorems necessarily reflect this point?\n5. Authors seems have used many existing heuristic techniques like residual connections, pre-norm, post-norm, ... And I am wondering if using these will have any impact on the formulation? For example, can we use residual layer and still analyze our model with linear left-to-right system in Eq 1 and 2?\n6. Experiment design is not reflecting the advantages of this model.\n- I enjoyed reading the arguments about modeling long sequences. However, all experiments are some empirical performance comparison and since the architectural details are not clear, it is not clear to me the gains are because this model is more capable of modeling longer sequences or maybe benefited from some architectural detail choices? I was hoping to see some advantage of using LSSL, one can always train aLSTM network and tune all parameters to get state-of-the-art, what LSSL provides that make it better than the simple tuning ?\n- For CelebA task, I dont understand the reasoning to choose ResNet-18 model which is 10X larger that MLSSL model  as baseline. Why not just find two architecture with and without LSSL assumption and show the effectiveness of LSSL?\n7. Through the paper, authors use speech as an example case with long sequences. In practical speech recognition, model do not use raw audio as input, instead a window of signal is used. There are many successful methods using raw signal or FFT of window of signal as input (so line 276 is not completely correct), but the observation has been that these models at the end learn similar filters like Mel filters. Also they perform very similar to standard Mel features thus not beneficial for practical use cases.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not find any.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "Ec7SRc98W48", "reviewer": "Reviewer_Ueff", "summary": "This paper suggests learning a proxy to continuous linear dynamical system. The paper discusses the tradeoffs and considerations and shows that the computations can be made efficiently. The paper demonstrates comprehensive empirical evaluation for the suggested method.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality** - the paper suggests a novel reparameterization for RNNs. The work clearly extends previous work such as HiPPO [1]. Related work is discussed thoroughly, some times to briefly, specifically, relation to prior work in control theory requires a more comprehensive discussion.\n\n**Quality** - The theoretical claims are well support. The empirical evaluation shows remarkable results compared to the baselines considered.\n\n**Clarity** - Overall, the paper is written well. The ideas presented may very well be the basis for future work.\nMy problem here is that the bottom line is not clearly stated, rather it’s implicit and a reader must go back and forth to understand the big picture. I think an implementation subsection may help make things clearer.\n\n**Significance** - The subject of improving recurrent networks for long time dependency is a very important topic. This paper suggests a new scheme, improving on existing ones significantly. In addition, the theoretical analysis may also lead to other parameterizations for continuous linear dynamical systems.\n\nAdditional comments:\n1. Lines 58-59 - this connection is an important part of this work, it should be included at least in the appendix, also in order to implement an arbitrary convolution with a linear dynamical system, the dimensionality of the RNN must be larger than that of the 1d convolution.\n2. Lines 113-116 - something seems wrong here (perhaps one of the $\\Delta t$ is a typo), if you set $\\alpha=0$ you get $x(t+\\Delta t)=(I+\\Delta t A)x(t)+\\Delta tB u(t)\\Delta t$ which can be written as $x(t+\\Delta t)=x(t)+\\Delta t(Ax(t)+ \\Delta t Bu(t))$, but $x’(t)=Ax(t)+Bx(t)$.\n3. Lines 119-120 - this is confusing, it is clear the paper continues with $\\alpha=\\frac{1}{2}$, A and B are not a function of $\\Delta t$, why denote them as such?\n4. Lines 186-188 - this statement is misleading, the overall functions that can be expressed with deep linear RNNs is still linear in the inputs, the statement implies otherwise.\n5. Theorem 1 - the citation of [8] is in italic.\n6. Corollary 4.1 - quasiseparable should be defined prior to the corollary.\n7. Section 5.1 - the margins are so narrow here, reporting std is a must.\n8. Line 310 - shouldn’t $\\Delta t$ be a scalar? why is it O(H) parameters?\n9. The learning setup is not clear from the main paper, what is the eventual optimization problem that is being minimized, how is $\\Delta t$ parameterized in the learning setup. It is clear that the paper discusses special structures for A which are favorable in terms of computation but a reader is left a bit puzzled as to what it actually done in practice. Is it the GBT in equation (3) with \\alpha=1/2?\n\n\n[1] - Hippo: Recurrent memory with optimal polynomial projections, Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The empirical evaluation is lacking more details in order for a fair comparison between the methods - namely a clear experimental protocol and reporting standard deviation.\nThere are no social concerns arising from this submission.", "review_text": "", "extra_scores": {"ethical_concerns": "The paper does not entail any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a continuous time model combining recurrent and convolutional structures. Overall, reviewers are supportive of the paper. The main remaining concerns, after discussion, are mostly with respect to the presentation. It was felt that the paper is dense, heavily relying on the appendix, and could be more clearly communicated in the main text. There was also a perception that the main contributions were in engineering. While the authors push back this notion, there is no need for this to be perceived as a drawback, and could be reasonable to highlight engineering contributions in revisions. There were also some concerns that it was hard to derive clear takeaways from some of the experiments (details in the reviews). Please try to be receptive of reviewer comments in preparing revisions. But generally, this is great work!
Decision: Accept (Poster)