Long Expressive Memory for Sequence Modeling
Authors: T. Konstantin Rusch
Siddhartha Mishra
N. Benjamin Erichson
Michael W. Mahoney
Venue: ICLR 2022 Spotlight (2022)
Keywords: sequence modeling
long-term dependencies
multiscale ordinary differential equations
dynamical systems

Abstract: We propose a novel method called Long Expressive Memory (LEM) for learning long-term sequential dependencies. LEM is gradient-based, it can efficiently process sequential tasks with very long-term dependencies, and it is sufficiently expressive to be able to learn complicated input-output maps. To derive LEM, we consider a system of multiscale ordinary differential equations, as well as a suitable time-discretization of this system. For LEM, we derive rigorous bounds to show the mitigation of the exploding and vanishing gradients problem, a well-known challenge for gradient-based recurrent sequential learning methods. We also prove that LEM can approximate a large class of dynamical systems to high accuracy. Our empirical results, ranging from image and time-series classification through dynamical systems prediction to speech recognition and language modeling, demonstrate that LEM outperforms state-of-the-art recurrent neural networks, gated recurrent units, and long short-term memory models.

Published as a conference paper at ICLR 2022
LONG EXPRESSIVE MEMORY FOR SEQUENCE MODELING
T. Konstantin Rusch ETH Zürich trusch@ethz.ch
Siddhartha Mishra
N. Benjamin Erichson University of Pinsburgh er criohhpipi tt... edd
ETH Zürich amishha@ette shra@ethz.cch
Michael W. Mahoney
ICSI and UC Berkeley
mmahoney@stat. wtw.:etttt...eeee..eeeee..e
ABSTRACT
We propose a novel method called Long Expressive Memory (LEM) for learn- ing long-term sequential dependencies. LEM is gradient-based, it efficiently process sequential tasks with very long-term dependencies, and it is sufficiently expressive to be able to learn complicated input-output maps. To derive LEM, we consider a system of multiscale ordinary differential equations, as well as a suitable dineeisscetiiaation of this system. For LEM, we derive rigorous bounds to show the mitigation of the exploding and vanishing gradients problem, well- known challenge for gradient-based recurrent sequential learning methods. We also prove that LEM can approximate large class of dynamical systems to high accuracy. Our empirical results, ranging from image and time-series classification through dynamical systems prediction to keyword spotting and language model- ing, demonstrate that LEM outperforms state-of-the-an recurrent neural networks, gated recurrent units, and long short-term memory models.
INTRODUCTION
Learning tasks with sequential data as inputs (and possibly outputs) arise in wide variety of con- texts, including computer vision, text and speech recognition, natural language processing, and time series analysis in the sciences and engineering. While recurrent gradient-based models have been successfully used in processing sequential data sets, it is well-known that training these models to process (very) long sequential inputs is extremely challenging on account of the so-called ploding and vanishing gradients problem (Pascanu et al.) 2013). This arises as calculating hidden state gradients entails the computation of an iterative product of gradients over large number of steps. Consequently, this (long) product can casily grow or decay exponentially in the number of recurrent interactions.
Mitigation of the exploding and vanishing gradients problem has received considerable attention in the literature. A classical approach, used in Long Short-Term Memory (LSTM) (Hochreiter & Schmidhuber 1997) and Gated Recurrent Units (GRUs) (Cho et al. 2014), relies on gating mecha- nisms and leverages the resulting additive structure ensure that gradients do not vanish. However, gradients might still explode, and learning very long-term dependencies remains a challenge for these architectures (Li et al., 2018). An alternative approach imposes constraints on the structure of the hidden weight matrices of the underlying recurrent neural networks (RNNs), for instance by requiring these matrices to be unitary or orthogonal (Henaff et al., 2016) Arjovsky al., 2016: Wis- dom et al. 2016;; Kerg al. (019). However, constraining the structure of these matrices might lead to significantly reduced expressivity, i.c., the ability of the model to learn complicated input- output maps. Yet another approach relies enforcing the hidden weights to lie within pre-specified bounds, leading to control on gradient norms. Examples include Li et al. (2018), based on indepen- dent neurons in each layer, and Rusch & Mishra (202 based network of coupled oscillators. Imposing such restrictions on weights might be difficult to enforce, and weight clipping could reduce expressivity significantly.

---

Published as a conference paper at ICLR 2022
This brief survey highlights the challenge of designing recurrent gradient-basee -bsed methods for quence modeling which can mitigate the exploding and vanishing gradients problem, while at the same time being sufficiently expressive and possessing the ability to learn complicated input-outpu maps efficiently. We seek to address this challenge by proposing a novel gradient- -hased method.
The starting point for method is the observation that realistic sequential data sets often contain information arranged according to multiple (time, length, etc., depending on the data and task) scales. Indeed, if there were only one or two scales over which information correlated, then simple model with a parameter chosen to correspond to that scale (or, e.g., scale difference) should be able to model the data well. Thus, it is reasonable to expect that a multiscale model should be considered to process efficiently such multiscale data. To this end, we propose a novel gradient- based architecture, Long Expressive Memory (LEM), that is based on a suitable dinretticttinntionn of set of multiscale ordinary differential equations (ODEs). For this novel gradient-based method (proposed in Section
we derive bounds on the hidden state gradients to prove that LEM mitigates the exploding and vanishing gradients problem (Section 4
we rigorously prove that LEM can approximate very large class of (multiscale) dynamical systems to arbitrary accuracy (Section and
we provide an extensive empirical evaluation of L.EM on a wide variey of data sets, includ- ing image and sequence classification, dynamical systems prediction, keyword spotting, and language modeling, thereby demonstrating that LEM outperforms or is comparable to sfateoo-the-aae art RNNs, GRUs and LSTMs in each task (Section
We also discuss a small portion of the large body of related work (Section 3). and we provide a brief discussion of our results in broader context (Section 6). Much of the technical portion of our work is deferred to Supplementary Materials.
2 LONG EXPRESSIVE MEMORY
We start with the simplest example of system of two-scale ODEs,
dy
dz
di Ty (a (W,z ,2 + V, u + by) y) di = T. (a (Way V.++b.)) z).
(I)
Here, t [0, T) is the continuous time, < Ty S T3 I 1 are the two time scales, stt R z(t) e Rd are the vectors of slow and variables and u u(t) E RT is the input signal. For simplicity, we set dy = dg = d. The dynamic interactions between the neurons are modulated by weight matrices W y.z. V y.z+ bias vectors by.= and a nonlinear tanh activation function (u)) tanh(u).
Note that O refers to the componentwise product of vectors.
However, two scales (one fast and one slow), may not suffice in representing a large number of scales that could be present in realistic sequential data sets. Hence, we need to generalize ①1 to multiscale version. One such generalization is provided by the following set of ODEs,
dy = à (Way + V2u+ + b2) @ (a (W,22 2 + V uuu+ by) - y),
dt
dz
dt = (Wiy + V bi) c (a (Way + V b.) - 2).
In addition to previously defined quantities, we need additional weight matrices W W1,, V1 bias vectors by.s and sigmoid activation function (u) 0..(1 + tanh(u/2)). As â monotone, we can set W1.2 a (by.:) = Ty. to observe that the two-scale system (1) special case of ② One can read- ily generalize this construction to obtain many different scales in (2). Thus, we can interpret (T= t). T, (y,y)))) = (& (W + Viu+ + b,) (W2y + V2u+ + b2)) in (2) as input and state dependent gating functions, which endow ODE (2) with multiple time scales. These scales can be learned adaptively (with respect to states) and dynamically (in time). Moreover, it turns out that the multiscale ODE system (2) is of the same general form (see SM$C) the well-known Hodgkin- Huxley equations modeling the dynamics of the action potential for voltage-gated ion- channels in biological neurons (Hodgkin & Huxley 1952).
V1.2 = 0 and (b1), = by. (b2); = b., for all 1 < < d, with
2

---

Published as a conference paper at ICLR 2022
Next, propose discrettcrtti of the multiscale ODE system 2). providing circuit to sequential model architecture. As is common with numerical discretizations properly is important preserve desirable properties. To this end, we fix At O, and discretize ( with the following implicit-explicit (IMEX) time-stepping scheme to arrive at LEM, written in compact form as,
ODEs, doing so
n Alõ W y - + V u,, + b1),
f Ato W2y + u2 + b2),
(3)
2 (1 At n At o (W -y-1 + V.u, + b2).
Yn (1 A ① Yn-11
At O 0 ( n.n + Vyu, + by).
For steps < S N, the hidden states in LEM
nn. Zn R with input state u, E R The weight matrices are W1 2,2.9 E [Rdxd and V 22222.9 E R and the bias vectors are b1,2,2y E RRd We also augment LEM 3 with a linear output state Wn E R with Wn = Wyyn. and W, E Roxd
RELATED WORK
We start by comparing our proposed model, LEM to the widely used L.STM of Hochreiter & Schmidhuber (1977). Observe that At,, At,, in 3 similar in form to the input, forget and output gates in an LSTM (see SM&D), and that LEM has exactly the same number of parameters (weights and biases) as an LSTM, for the same number of hidden units. Moreover, as detailed in SM show that by choosing very specific values of the LSTM gates and the Atn; At,, terms in LEM 33. the two models are equivalent. However, this analysis also reveals key differences between LEM (3) and LSTMs, as they are equivalent only under very stringent assumptions. In general, as the different gates in both LSTM and LEM (3) are learned from data, one can expect them behave differently. Moreover contrast LSTM, LEM stems from a discretized ODE system 2 which endows it with (gradient) stable dynamics.
The use of multiscale neural network architectures machine learning has long history. An early example was provided in Hinton & Plaut (1987), who proposed neural network with each connec- tion having fast changing weight for temporary memory and a slow changing weight for long-term learning. More recently, processing multiple spatial scales in data (Bai et al. 2020).
view convolutional neural networks multiscale architectures for
The use of ODE-based learning architectures has also received considerable attention in recent years with examples such as continuuus-tin time neural ODEs (Chen et al. 2018 Queiruga et al. 2020 2021) and their recurrent extensions ODE-RNNs (Rubanova al.) 2019), well RNNs based on discretizations of ODEs (Chang et al. 2018 Erichson et al. 2021 Chen et al. 2020 Lim et al.] 202 Rusch & Mishra 2021a b). In addition the specific details of our archiecture, differ from other discretized ODE-b RNNs in the explicit use of multiple (Icarned) scales in LEM.
RIGOROUS ANALYSIS OF LEM
Bounds on hidden states. The structure of LEM 3 allows us to prove (in SM that hidden states satisfy the following pointwise bound.
Proposition 4.1. Denote t,, ntt and assume that At < 1. Further assume that the initial hidden
states are 2 = yo = O. Then, the hidden states Zu Yn of LEM 3 are bounded pointwise as,
max max ( (222 b2 S min (1,AvTn), V1 S.n, with 1 1+ At ISiS
(4)
/2 A
On the exploding and vanishing gradient problem. the combined hidden state, given by X,, = [z [ y of the exposition, ground truth. The training of our proposed model (3) entails computing gradients of the above loss
For any S let X, 2d denoted
n: y. For simplicity consider loss function: E,, , yn 12 with y,, being the underlying
function with respect to its underlying weights and biases 0 E e [W I V1 b b1,2y.z),
3

---

Published as a conference paper at ICLR 2022
at every step of the gradient descent procedure. Following Pascanu et al. (2013), one uses chain rule to show,
dEn
aell
oelh)
den 0x, θ X₁ 00 0X, ax, 00
(5)
ae
00
I
In general, for recurrent models, the partial gradient 0 30 which measures the contribution to the ae
hidden state gradient at step n arising from step & of the model, can behave as 89 -"= for some 7 > O/Pascanu et al. (2013). If > 1, then the partial gradient grows exponentially in sequence length, for long-term dependencies << n, leading to the exploding gradient problem. On the other hand, if < 1, then partial gradients decays exponentially for k << n, leading to the vanishing gradient problem. Thus, mitigation of the exploding and vanishing gradient problem entails deriving bounds on the gradients. We start with the following upper bound (proved in SM...2).
Proposition 4.2. Let ZnzYr be the hidden states generated by LEM (3) We assume that AL <<> is chosen to be sufficiently small. Then, the gradient of the loss function En with respect any parameter E is bounded as
S (1
Y)an + (1 Y)T γ = 1F
00
(6)
7) max W bc:
W=lloc W2 [
[
[ olooo, 2 + 17) (1 + 3n)
If we choose the hyperparameter At 1n (see SM (77) for the order-notation), then one readily observes from (6) that the gradient 0,E, is uniformly bounded for any sequence length n and the exploding gradient problem is clearly mitigated for LEM (3). Even if one chooses At = O(n ")), for some 0 S < 1, we show in SM Remark E. that the gradient can only grow polynomially (e.g. as (n) for 8 = 1/2), still mitigating the exploding gradient problem.
Following Pascanu et al. (2013), one needs more precise characterization of the partial gradient 0 for long-term dependencies, i.e., k << n. show mitigation of the vanishing gradient problem. In SM we state and prove proposition E.2 which provides a precise formula for the asymptotics of the partial gradient. Here, we illustrate this formula in a special case as a corollary.
Proposition 4.3. Let yn, Zn be the hidden states generated by LEM (3) and the ground truth satisfy yn O(). Then, for any k << (long-term dependencies) we have,
dell
O
At
00
W2lli and are independent of n, k. Here, constants in O(At.) depend on only n 6 and
This formula 7 shows that although the partial gradient can be small, i.e., O(A(²), it is in fact independent of k, ensuring that long-term dependencies contribute to gradients at much later steps and mitigating the vanishing gradient problem.
Universal approximation of general dynamical systems. The above bounds on hidden state gra- dients show that the proposed model LEM (3) mitigates the exploding and vanishing gradients problem. However, this by itself, does not guarantee that it can learn complicated and realistic input-output maps between sequences. To investigate the expressivity of the proposed LEM, we will show in the following proposition that it can approximate any dynamical system, mapping an input sequence uI, to an output sequence On, of the (very) general form,
Φ,, f f un)- On o(Φ.).
S,
(8)
with Φb E dR On E dR. denoting the hidden and output states, respectively. The input signal is un E dR and maps f Rda x Rdd. m Rd and o IRd + Rdd are Lipschitz continuous. For simplicity, we set the initial state O 0. Proposition 4.4. For all < n S N, let Φ.,, on be given by the dynamical system (8) with input signal un- Under the assumption that there exists a R >> such that max [1 uu }} < R. for all 1 < < N, then for any given > O there exists a LEM of the form 3 with hidden states Yn, Zn E Rdy and output state Wn. Wyyn nn E Rdo, for some dy such that the following holds.
loon will S. v
4

---

Published as a conference paper at ICLR 2022
From this proposition, proved in SM.E.4 we conclude that, in principle, the proposed LEM approximate a very large class of dynamical systems.
can
Universal approximation of multiscale dynamical systems. While expressing a general form of
input-output maps between sequences, the dynamical system ( does not explicitly model dynamics
at multiple scales. Instead, here we consider the following two-scale fast-slow dynamical system of the general form,
6n = f(on-1: Un) 4,, = -..=, 1n-1, On = =
(10)
Here, 0 < << and 1 are the slow and fast time scales, respectively. The underlying maps (f. gf.g) : Rdd xd Xd. Rd are Lipschitz continuous.
the following proposition, proved in SMA F..5 we show that LEM (3) can approximate (TO) to desired accuracy.
Proposition 4.5. For any 0 < << L, and for all S n S. N, let Φn. 2n, On be given by the two-scale dynamical system (10) with imput signal un. Under the assumption that there exists
R. > O such that max{] Φ, mll. |u.ll} < R, for all 1 S. n S. NN, then for any given > O, there exists LEM of the form 3). with hidden states Yn. Zn E IR and outuu state wn E Rd with
wn Wyn such that the following holds,
I|on wwll S., visnsN
(11)
Moreover, the weights, biases and size (number of neurons) of the underlying LEM (3) are indepen- dent of the time-scale T.
This argument be readily generalized to more than two time scales (see SM Proposition E.4 Hence, we show that, in principle, the proposed model LEM (3) can approximate multiscale dy- namical systems, with model size being independent of the underlying timescales. These theoretical results for LEM (3) point to the ability of this architecture to learn complicated multiscale input- output maps between sequences, while mitigating the exploding and vanishing gradients problem. Although useful prerequisities, these theoretical properties are certainly not sufficient to demonstrate that LEM B is efficient in practice. To do this, we perform several benchmark evaluations, and we report the results below.
5 EMPIRICAL RESULTS
We present variety of experiments ranging from long-term dependency tasks to real-world applica- tions as well as tasks which require high expressivity of the model. Details of the training procedure for each experiment can be found in SM As competing models LEM, types of architectures-LSSTT language modeling and speech recognition, while not performing well on long-term dependency tasks, possibly due to the exploding and vanishing gradients problem. On the other hand, we choose state-of-the-art RNNs which are tailor-made learn tasks with long-term dependencies. Our ob- jective is to evaluate the performance of LEM and compare it with competing models. All code to reproduce our results can be found at http://tthhu..oo///tuucuhhcaca/t
choose two different and GRUs as they are known to excel at expressive tasks such as
Very long adding problem. We start with the well-known adding problem (Hochreiter & Schmid- huber] [997). proposed to test the ability of model to learn (very) long-term dependencies. The input two-dimensional sequence of length N, with the first dimension consisting of random numbers drawn from ([0, 1)) and with two non-zero entries (both set to 1) in the second dimen- sion, chosen at random locations, but one each both halves of the sequence. The output is the sum of two numbers of the first dimension at positions, corresponding to the two entries in the second dimension. We consider three very challenging cases, namely input sequences with length N = 2000, 5000 and 10000. The results of LEM together with competing models including state- of-the-art RNNs, which are explicitly designed to solve long-term dependencies, are presented in Fig. We observe in this figure that while baseline LSTM is not able to beat the baseline mean- square error of 0.167 (the variance of the baseline output 1) in any of the three cases, a proper weight initialization for LSTM. the so-called
initiaaiziiiiiiiiinnn of Tallec & Ollivier 2018) leads to much better performance in all cases. For N = 2000, all other architectures (except baseline LSTM) beat the baseline convincingly. However for N 5000, only LEM, chrono-L-TTY and coRNN are able
5

---

Published as a conference paper at ICLR 2022
to beat the baseline. In the extreme case of N 10000, only LEM and chrono-LSTM are able to beat the baseline. Nevertheless, LEM outperforms -hrono-LSTM by converging faster (in terms of number of training steps) and attaining a lower test MSE than chrono-LSTM in all three cases.
Sequence length
Sequence length
Sequence length 000
1r1
1314
10%
Troiiing (nundrecs)
Training (hundress)
Training (burdedss)
Figure 1: Results on the very long adding problem for LEM, CORNN, DTRIVoO (Casado 2019) FasGGRNN (Kusupati et al. 2018), LSTM and LSTM with chrono initialization (Tallec Ollivier 2018 based on three very long sequence lengths N, i.., N 2000, N 5000 and N 10000.
Sequential image recognition. We consider three experiments based two widely-used image recognition data sets, ie., MNIST (LeCun et al. 1998) and CIFAR-10 (Krizhevsky et al. 2009), where the goal is to predict the correct label after reading in the whole sequence. The first two tasks are based on MNIST images, which are flattened along the rows to obtain sequences of length N 784. In sequential MNIST (sMNIST), the sequences fed the model one pixel time in streamline order, while in permuted sequential MNIST (psMNIST), a fixed random permutation applied the sequences, resulting in much longer dependency than for sMNIST. We also con- sider the more challenging noisy CIFAR-10 (nCIFAR- 10) experiment (Chang et al. 2018). where CIFAR- 10 images are fed to the model row-wise and flattened along RGB channels, resulting in 96-dimensional sequences, each of length 32. Moreover, a random noise padding is applied after the first 32 inputs to produce sequences of length N 1000. Hence, addition to classifying the underlying image, model has to store this result for a long time. In Table T we present the results for LEM on the three tasks together with other SOTA RNNs, which were explicitly designed to solve long-term dependency tasks, as well as LSTM and GRU baselines. We observe that LEM outper- forms all other methods on sMNIST and nCIFAR-10 10. Additionally on PSMNIST, LEM performs as well as coRNN, which has been SOTA among single-layer RNNs on this task.
Table 1: Test accuracies on sMNIST, PSMNIST and nCIFAR- 10, where M denotes the total number of parameters of the corresponding model. Results of other models are taken from the respective original paper referenced in the main text, except that the results for L.TT are taken from Helfrich et al. 2018), for GRU from Chang et al. (201)) and the results indicated by are added by us.
MNIST
CIFAR-10
Model
sMNIST
PSMNIST
# units / M
nCIFAR-10
# units M
GRU
99.1% %
94.1%
256 / 201k
43.8%
128 88k
LSTM
98.9%
92.9%
256 / 267k
11.6%
128 1 116k
chrono-LSTM
98.9%
94.6%
128 / 68k
55.9%
128 1 116k
anti.sym. RNN
98.0%
95.8%
128 / 10k
48.3%
256 36k
Lipschitz RNN
99.4%
96.3%
128 / 34k
57.4%
128 / 46k
expRNN
98.4%
96.2%
360 / 69k
52.9%
360 / 103k
CORNN 99.3%
96.6%
128/ 34k
59.0%
128 46k
LEM
99.5%
96.6%
128 / 68k
60.5%
128 1 16k
Eigen Worms: Very long sequences for genomics classification. The goal of this task (Bagnall et al. 2018) is to classify worms as belonging to either the wild-type or four different mutants, based on 259 very long sequences (length N 17984) measuring the motion of worm. In addition to the nominal length, was empirically shown in Rusch & Mishral (2021b) that the Eigen Worms sequences exhibit actual very long-term dependencies (i.e., longer than 10k).

---

Published as a conference paper at ICLR 2022
Table 2: Test accuracies Higen Worms using 5 re-trainings of each best performing network (based on the validation set), where all other results are taken from Rusch & Mishra (2021b) except that the NRDE result is taken from Morrill et al. (2021) and the results indicated by are added by us.
Model
test accuracy
# units
# params
NRDE
83.8% + 3.0%
32
35k
expRNN
40.0% + 10.1%
64
2.8k
IndRNN (2 layers)
49.7% 4.8%
32
1.6k
LSTM
38.5% + 10.1%*
32
5.3k
BiLSTM+ Id-con
40.5% 7.3%*
5.8k
chrono-LSTM
82.6 % + 6.4%
32
5.3k
CoRNN
86.7% 3.0%
2.4k
UnICORNN (2 layers)
90.3% = 3.0%
32
1.5k
LEM
92.3% = 1.8%
32
5.3k
Following Morrill al. 2022 and Rusch & Mishra (2021b). we divide the data into train, valida- tion and test set according to a 70%, 15%, 15% ratio. In Table we present results for LEM together with other models. As the validation and test sets, each consist of only 39 sequences, we report the mean (and standard deviation of) accuracy over 5 random initializations to rule out lucky outliers. We observe from this table that LEM outperforms all other methods, even the 2-layer UnICORNN architecture, which has been SOTA on this task.
Healthcare application: Heart-rate prediction. In this experiment, one predicts the heart rate from time-series of measured PPG data, which is part of the TSR archive (Tan et al.) (2200 and has been collected at the Beth Isreal Deaconess medical center. The data set, consisting of 7949 sequences, each of length N = 4000, is divided into train, validation and test set according to a 10%.15%,155 ratio, (Morrill et al.] [202]; Rusch & Mishra (021b). The results, presented in Table 3 show that LEM outperforms the other competing models, including having test L error of 35% less than the SOTA UnICORNN.
Table 3: Test L error heart-rate prediction using PPG data. All results obtained by running the same code and using the same fine-tuning protocol.
Model
test T/2 error
units
# params
LSTM
9.93
128
67k
chrono-LSTM
3.31
128
67k
expRNN
1.63
256
34k
IndRNN (3 layers)
1.94
128
34k
coRNN
1.61
128
34k
UnICORNN (3 layers)
1.31
128
34k
LEM
0.85
128
67k
Multiscale dynamical system prediction.
The FitzHug--Nagumo system (Fitzhugh) 1955)
= 3
Texts w rv= bo),
(12)
prototypical model for a two-scale fast-slow nonlinear dynamical system, with fast variable and slow variable w and - << 1 determining the slow- time scale. This velaxation-oscillata is an approximation to the Hodgkin-Huxley model (Hodgkin
Huxley 1952) of neuronal action- potentials under an external signal Tex: 2 0. With = 0.02, Text = 0.5, = 0.7, b = 0.8 and initial data (Vo, wo) = (c, 0), with randomly drawn from [d[[- (1[[-1,1 1]), we numerically approximate (12) with the explicit Runge-Kutt method of order 5(4) in the interval J0, 400] and generate 128 training and validation and 1024 test sequences, each of length
= 1000, to complete the data set. The results, presented in Table 4 show that LEM not only outperforms LSTM by factor of 6 but also all other methods including CORNN, which is tailormade for oscillatory time-series. This reinforces theory by demonstrating efficient approximation of multiscale dynamical systems with LEM.

---

Published as a conference paper at ICLR 2022
Table 4: Test I error on SttzHugh-Naguma system prediction. All results are obtained by running the same code and using the same fine-tuning protocol.
Model
error (x10-2)
units
# params
LSTM
1.2
16
lk
expRNN
2.3
50
lk
LipschitZRNN
1.8
24
1k
FastGRNN
2.2
34
1k
CORNN
0.4
24
1K
LEM
0.2
16
1k
Google12 (V2) keyword spotting. The Google Speech Commands data set V2 ( (Warden 2018 is a widely used benchmark for keyword spotting, consisting of 35 words, sampled at of 16 kHz from second utterances of 2618 speakers. We focus on the 12-label task (Google 12) and follow the pre-defined splitting of the data set into train/validationntest sets and test different sequential models. In order to ensure comparability of different architectures, we do not use performance- enhancing tools such as convolutional filtering or multi-head attention. From Table we observe that both I.TTM and GRU, widely used models in this context, perform very well with test accuracy of around 95%. Nevertheless, LEM is able outperform both on this task and provides the best performance.
Table 5: Test accuracies on Google12. All results are obtained by running the same code and using the same fine-tuning protocol.
Model
test accuracy
# units
# params
Banh-RNN
73.4%
128
27k
syt..sym. RNN
90.2%
128
20k
LSTM
94.9%
128
107k
GRU
95.2%
128
80k
FastGRNN
94.8%
128
27k
expRNN
92.3%
128
19k
CoRNN
94.7%
128
44k
LEM
95.7%
128
107k
Language modeling: Penn Tree Bank corpus. Language modeling with the widely used small scale Penn Treebank (PTB) corpus (Mareus et al.) 1993), preprocessed by Mikolov al.] (2010), has been identified as excellent task for testing the expressivity of recurrent models (Kerg al.) 2019). this end, Table we report the results of different architectures, with a similar number of hidden units, on the PTB char-level task and observe that RNNs, designed explicitly for learning long-term dependencies, perform significantly worse than LSTM and GRU. On the other hand, LEM is able to outperform both L.STM and GRU this task by some margin (a test bpc of 1.25 in contrast with approximately a bpc of 1.36). In fact, LEM provides the smallest test bpc among all reported single-layer recurrent models this task, to the best of our knowledge. This superior performance is further illustrated in Table 7 where the test perplexity for different models on the PTB word-level task is presented. We observe that only does LEM significantly outperform (by around 40%) LSTM, but also provides again the best performance among all single layer recurrent models, including the recently proposed TARNN (Kag & Saligrama, (021). Moreover, the single- layer results for LEM are better than reported results for multi-layer LSTM models, such as in Gal Ghahramani (016) (2-layer LSTM, 1500 units each: 75.2 test perplexity) or Bai et al. (2018)
(3ylr LSTM. 700 units each: 78.93 test perplexity).
6 DISCUSSION
The design of a gradient- based model for processing sequential data that can learn tasks with long- term dependencies while retaining the ability learn complicated sequential input-output maps is
8

---

Published as a conference paper at ICLR 2022
Table 6: Test biss-per-character (bpe) PTB character-level for single layer LEM and other single layer RNN architectures. Other results are taken from the papers cited accordingly in the table, while the results for coRNN are added by us.
Model
test bpc
units
# params
anti.sym RNN (Erichson et al. 2021
1.60
1437
1.3M
Lipschitz RNN (Erichson et al.
2021
1.42
764
1.3M
expRNN Kerg al. 2019)
1.51
1437
1.3M
CORNN
1,46
1024
2.3M
nnRNN Kerg et 2019
1.47
1437
1.3M
LSTM Krueger et a.
2017
1.36
1000
5M
GRU Bar et al. 2018
1.37
1024
3M
LEM
1.25
1024
5M
Table 7: Test perplexity PTB word-level for single layer LEM and other single layer RNN archi- tectures.
Model
test perplexity
# units
# params
Lipschitz RNN (Erichson et al.
2021
115.4
160
76k
FastRNN Kag & Saligrama (0021)
115.9
256
131k
LSTM (Kag & Salıgrama| 2021)
116.9
256
524k
SkipLSTM (Kag Saligrama 2021
114.2
256
524k
TARNN (Kag & Sahgrama 202T
94.6
256
524k
LEM
72.8
256
524k
very challenging. In this paper, we have proposed Long Expressive Memory (LEM), novel current architecture, with a suitable time-discretization of a specific multiscale system of ODEs (2) serving as the circuit to the model. By combination of theoretical arguments and extensive empin- cal evaluations on diverse set of learning tasks, we demonstrate that LEM is able to learn long- term dependencies while retaining sufficient expressivity for efficiently solving realistic learning tasks.
It is natural to ask why LEM performs so well. A part of the answer lies in the mitigation of the exploding and vanishing gradients problem. Proofs for gradient bounds (7) reveal a key role played by the hyperparameter At. We observe from SM Table g that small values of At might be needed for problems with very long-term dependencies, such as the EigenWorms Worms dataset. On the other hand, no tuning of the hyperparameter AL is necessary for several tasks such language modeling, keyword spotting and dynamical systems prediction and a default value At = yielded very good performance. The role and choice of the hyperparameter At is investigated extensively in SM However, mitigation of exploding and vanishing gradients problem alone does not explain high expressivity of LEM. In this context, proved that LEMs can approximate very large class of multiscale dynamical systems. Moreover, we provide experimental evidence in SM to observe that LEM not only expresses range of scales, it is designed do, but also these scales contribute proportionately to the resulting multiscale dynamics. Furthermore, empirical results presented in SM show that this ability represent multiple scales correlates with the high accuracy of LEM. We believe that this combination of gradient stable dynamics, specific model structure, and its multiscale resolution can explain the observed performance of LEM.
We conclude with comparison of LEM and the widely-used gradient- based LSTM model. In ad- dition to having exactly the same number of parameters for the same number of hidden units, our experiments show that LEMs are better than LSTMs expressive tasks such as keyword spotting and language modeling, while also providing significantly better performance on long-term depen- dencies. This robustness of the performance of LEM with respect to sequence length paves the way for its application to learning many different sequential data sets where competing models might not perform satisfactorily.
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS.
The research of TKR and SM was performed under a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and inno- vation programme (grant agreement No. 770880). NBE and MWM would like to acknowledge IARPA (contract W91 INF20000)))) NSF, and ONR for providing partial support of this work. Our conclusions do not necessarily reflect the position or the policy of our sponsors, and no official endorsement should be inferred.
The authors thank Dr. Ivo Damihelka (DeepMind) for pointing out that the hidden states for LEM satisfy the maximum principles (19) (20)
REFERENCES
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In International Conference on Machine Learning, pp. 1120-118,, 2016.
Anthony Bagnall, Hoang Anh Dau, Jason Lines, Michael Flynn, James Large, Aaron Bostrom, Paul Southam, and Eamonn Keogh. The multivariate time series classification archive, 2018. arXiv preprint arXiv: 1.00075, 2018.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv: 183.001/0 2018.
Shaojie Bai. Vladlen Koltun, and J Zico Kolter. Multiscale deep equilibrium models. In Advances in Neural Information Processing Systems, pp. 770-778, 2020.
A. R. Barron. Universal approximation bounds for superpositions sigmoidal function. JEEE Trans. Inform. Theory., 39(3):930- 945, 1993.
Mario Lezcano Casado. Trivializations for gradient- optimization on manifolds. In Advances in Neural Information Processing Systems, pp. 9154-9164, 2019.
Bo Chang, Minmin Chen, Eldad Haber, and Ed Chi. Antisymmetricrnn: dynamical system view recurrent neural networks. In International Conference on Learning Representations, 2018.
Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Withrock, Mark A Hasegawa-lohnson, and Thomas S Huang. Dilated recurrent neural networks. In Advances Neural Information Processing Systems, pp. 77-87, 2017.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In Advances in Neural Information Processing Systems, pp. 6571-6583, 2018.
Zhengdao Chen, Jianyu Zhang, Martín Arjovsky, and Léon Bottou. Symplectic recurrent neural net- works. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Kyunghyun Cho, van Merrienboer, Caglar Gulcehre, F Bougares, Schwenk, and Yoshua Ben- gio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In Conference on Empirical Methods Natural Language Processing (EMNLP 2014), 2014.
Benjamin Erichson, Omri Azencot, Alejandro Queiruga, and Michael W Mahoney. Lipschitz recurrent neural networks. In International Conference on Learning Representations, 2021.
Richard Fitzhugh. Mathematical models of threshold phenomena in the nerve membrane. Bull.
Math. Biophysics, 17:257-278, 1955.
Yarin Gal and Zoubin Ghahramani. A theoretically grounded application of dropout in recurrent neural networks. Advances in neural information processing systems, 29:1019-1027, 2016.
Felix A Gers, Jürgen Schmidhuber, and Fred Cummins. Learning to forget: Continual prediction with Istm. Neural computation, 12(10)2451-2477 2000.
10

---

Published as a conference paper at ICLR 2022
Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference on Machine Learning, pp. 1978. PMLR, 2018.
Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long memooy tasks. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd In- ternational Conference on Machine Leurning, volume 48 Proceedings of Machine Learning Research, pp. 2034-2042, 2016.
G.E. Hinton and D.C. Plaut. Using fast weights deblur old memories. In Proceedings of the ninth annual conference of the cognilive science society, pp. 177-186, 1987.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
A.L. Hodgkin and A.F. Huxley. A quantitative description of membrane current and its application to conduction and excitation in nerve. Journal of Physiology, 117:500-544, 1952.
Anil Kag and Venkatesh Saligrama. Time adaptive recurrent neural network. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 15149-15158,
June 2021.
Giancario Kerg, Kyle Goyette, Maximilian Puelma Touzel, Gauthier Gidel, Eugene Vorontsov, Yoshua Bengio, and Guillaume Lajoie. Non-normal recurrent neural network (nnrnn); learn- ing long time dependencies while improving expressivity with transient dynamics. In Advances in Neural Information Processing Systems, pp. 13591-13601, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
David Krueger, Tegan Maharaj, János Kramár, Mohammad Pezeshki, Nicolas Ballas, Nan Rose- mary Ke, Anirudh Goyal, Yoshua Bengio, Aaron C. Courville, and Christopher J. Pal. Zoneout: Regularizing rnns by randomly preserving hidden activations. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. Open 2017.
Christian Kuehn. Multiple time scale dynamics, volume 191. Springer, 2015.
Aditya Kusupati, Manish Singh, Kush Bhatia, Ashish Kumar, Prateek Jain, and Manik Varma. Fast- grnn: A fast, accurate, stable and tiny kilobyte sized gated recurrent neural network. In Advances in Neural Information Processing Systems, pp. 9017-9028, 2018.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(18)6(8))) 96(11))2278-2344 1998.
Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently recurrent neural network (indmn): Building a longer and deeper mnn In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5457-5466, 2018.
Soon Hoe Lim, N Benjamin Erichson, Liam Hodgkinson, and Michael W Mahoney. Noisy recurrent neural networks. arXiv preprint arXiv:2 2021.
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313-330, 1993.
Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Eleventh Annual Conference of the International Speech Communication Association, 2010.
James Morrill, Cristopher Salvi, Patrick Kidger, and James Foster. Neural rough differential equa- tions for long time series. In Proceedings of the 38th International Conference Machine Learn- ing, volume 139 of Proceedings of Machine Learning Research, pp. 7829-7838. PMLR, 18-28 24
Jul 2021.
11

---

Published as a conference paper at ICLR 2022
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of ICML'I3, 13, pp. 11-111--111-1118 JMLR.org. 2013.
A. F. Queiruga, N. B. Erichson, D. Taylor, and M. W. Mahoney. Continuous-in-eetth neural net- works. Technical Report Preprint: S.Kiv:2008.023888 2020.
Alejandro Queiruga, N Benjamin Erichson, Liam Hodgkinson, and Michael W Mahoney. Com- pressing deep ode-nets using basis function expansions. arXiv preprint arXiv:2106. 10820, 2021.
Yulia Rubanova, Ricky TQ Chen, and David Duvenaud. Latent odes for iregularly-sampled time series. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 5320-5330, 2019.
T. Konstantin Rusch and Siddhartha Mishra. Coupled oscillatory recurrent neural network (cornn): An accurate and (gradient) stable architecture for learning long time dependencies. Interna- tional Conference on Learning Representations, 202 la.
T. Konstantin Rusch and Siddhartha Mishra. Unicornn: A recurrent model for learning very long time dependencies. Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1168-9178. PMLR, 2021b.
Corentin Tallec and Yann Ollivier. Can recurrent neural networks warp time? In 6th International Conference on Learning Representations, ICLR, 2018.
Chang Wei Tan, Christoph Bergmeir, Francois Petitjean, and Geoffrey I Webb. Monash university, uea, ucr time series regression archive. arXiv preprint arXiv:2006.10996, 2020.
Pete Warden. Speech commands: dataset for limited-vocabulary speech recognition. arXiv preprint urXiv:1804.03209 2018.
Scott Wisdom, Thomas Powers, John Hershey, Jonathan Le Roux, and Les Atlas. Full-capacity unitary recurrent neural networks. In Advances in Neural Information Processing Systems, pp- 4880-4888, 2016.
12

---

Published as a conference paper at ICLR 2022
Supplementary Material for: Long Expressive Memory for Sequence Modeling
A TRAINING DETAILS
CPU, namely Intel Xeon Gold 5118 and AMD EPYC 7H12, except for Google12, PTB character-level and PTB word-level, which were run on a GeForce RTX 2080 Ti GPU. All weights and biases of LEM are initialized according to U(-1/vd, 1/vd), where is the number of hidden units.
All experiments
Table 8: Rounded hyperparameters of the best performing LEM architecture for each experiment. no value is given for Ai, means that Al is fixed to and no fine-tuning is performed on this hyperparameter.
experiment
learning rate
batch size
Al
Adding (N 10000)
2.6 10
50
2.42 x 10-2
sMNIST
1.8 x 10-3
128
2.1 x 10-1
PSMNIST
3.5 x 10
128
10
ICIFAR-10
1.8 10-3
120
9.5 10
EigenWorms
2.3 x 10-3
8
1.6 x 10
Healthcare
1.56 10-3
32
1.9 10
FitzHugh-Nauunn
9.04 10
32
1oogle12
8.9 X 10-4
100
FTB character-level
6.6 10-4
128
PTB word-level
6.8 10
64
The hyperparameters are selected based on a random search algorithm, where we present the rounded hyperparameters for the best performing LEM model (based validation set) on each task in Table g
We base the training for the PTB experiments on the following language modelling code: where we fine-tune, based on random search algorithm, only the learning rate, input-, output- and state-dropout, Li-penalty term and the maximum gradi- ent norm.
We train LEM for 100 epochs on sMNIST, PsMNIST and nCIFAR-10, after which we decrease the learning rate by a factor of 10 and proceed training for 20 epochs. Moreover, we train LEM for 50, 60 as well as 400 epochs on Eigen Worms, Google12 and FizzHugh-Nagumo. learning rate by factor of 10 after 50 epochs on Google 12. On the Healthcare task, we train LEM for 250 epochs, after which we decrease the learning rate by a factor of 10 and proceed training for 250 epochs.
decrease the
B FURTHER EXPERIMENTAL RESULTS
B. ON THE CHOICE OF THE HYPERPARAMETER At.
The hyperparameter At in LEM ( measures the maximum allowed (time) step the discretization of the multi-scale ODE system In propositions 4.1 4.2 and 4.3 this hyperparameter A/ plays a key role in the bounds on the hidden states 44) and their gradients (6). particular, setting At- O(N-1) will lead to hidden states and gradients, that are bounded uniformly with respect to the underlying sequence length N. However, these upper bounds on the hidden states and gradients account for worst-case scenarios and can be very pessimistic for the problem hand.
Thus, in practice, we determine At through a hyperparameter tuning procedure as described in section A To this end, perform random search within At < 2 and present the resulting optimal values of At for each of the considered data sets in Table [ From this table, we observe that for data sets such PTB, FitzHugh-Naguma and Google 12 do not need any tuning of At and
13

---

Published as a conference paper at ICLR 2022
90-
LEM
16-1
N = 500
1000
80
Test accuracy
N = 2000
MSE
Baseline
70
10:7
60
50
10-9
10
10-3
10-"
10
30
100
150
200
250
Ar
Training steps (hundreds)
Figure 2: Sensitivity study on hyperparameter
Figure 3: Average (over ten different initializa- on the adding
At in (3 using the Eigen Worms experiment.
tions each) test mean-square problem of LEM for different sequence lengths N, where the hyperparameter At of LEM (3 is fixed to At 1/VN.
default value of A = 1 resulted in very good empiricial performance. On the other data sets such as sMNIST, aCIFAR-10 and the healthcare example, where the sequence length (N O(10²) is larger, we observe that values of At = 0.1 yielded the best performance. The notable exception to this was for the FigenWorms data set, with very long sequence length of N 17984 as well as demonstrated very long range dependencies in the data, see Rusch & Mishra (222bb). Here, a value of At 1.6 x 10-3 resulted the best observed performance. To further investigate the role of the hyperparameter At in the Eigen Worms experiment, we perform sensitivity study where the value of At is varied and the corresponding accuracy of the trained LEM observed. The results this sensitivity study presented in Fig. [ where
plot the test accuracy (Y-axis) At (X-axis). From this figure, we observe that the accuracy is rather poor for At x 1 but improves monotonically Al is reduced till value of approximately 10-2 after which it saturates. Thus, in this case, value of At O(N- }) (for sequence length N) suffices to yield the best empirical performance.
the value of
Given this observation, we further test whether At = O(N suffices for other problems with long-term dependencies. To this end, consider the adding problem and vary the input sequence length by an order of magnitude, i.e., from N = 250 to N 2000. The value of At is now fixed at VN and the resulting test loss (Y-axis) vs the number of training steps (X-axis) is plotted in We see from this figure that this value of A/ sufficed to yield very small average test errors for this problem for all considered sequence lengths N. Thus, empirically value of At the range VN < At < 1 yields very good performance.
At
Fig. 3
Even if we set At = O ), it can happen for very long sequences N >> that the gradient can be quite small from the gradient asymptotic formula 77. This might lead to saturation in training, resulting long training times. However, we do not observe such long training times for very long sequence lengths in our experiment. To demonstrate this, we again consider Fig. where the number of training steps (X-axis) plotted for sequence lengths that vary an order of magnitude. The figure clearly shows that the approximately the same number of training steps are needed to attain a low the sequence length. This is further buttressed in Fig. where similar
test error, irrespective number of training steps where needed for obtaining the same very low test error, even for long sequence lengths, with N up to 10000. Moreover, from section A] we see that the number of epochs for different data sets is independent of the sequence length. For instance, only 50 epochs were necessary for EigenWorms Worms with a sequence length N 17984 and At 1.6 x 10 -3 whereas 400 epochs were required for the FitzHuuh-Naguma system with At
14

---

Published as a conference paper at ICLR 2022
B.2 MULTISCALE BEHAVOR OF LEM.
LEM B is designed to represent multiple scales, with terms At., At, being explicitly designed to learn possible multiple scales. In the following, we will investigate if practice, LEM learns multiple scales and uses them to yield the observed superior empirical performance with respect to competing models.
To this end, we start by recalling the proposition 4.5 where we showed that in principle, LEM can learn the two underlying timescales of a fastsslww dynamical system (see proposition E.4 for similar result for the universal approximation of a r-time scale (with r 2) dynamical system with LEM). Does this hold in practice ? To further investigate this issue, we consider the FitzHugh- Nagumo dynamical system (12 which serves as prototype for two-scale dynamical system. We consider this system 12 with the two time-scales being 0.02 and and train LEM for this system. In Fig. 4 we plot the empirical histogram that bins the ranges of learned scales A ta, At, S = 2 (for all n and d) and counts the number of occurrences of At,, At, in each bin. From this figure, observe that there is clear concentration of learned scales around the values 1 and 7 = 0.02, which exactly correspond to the underlying fast and slow time scales. Thus, for this model problem, LEM exactly learning what it is designed do and is able learn the underlying time scales for this particular problem.
104
10
10-2
At,. At.
Figure 4: Histogram of (At,), tt and Att,): : for all n 1,... and i 1,.... of LEM after training on the HacHHugh-agunne fast-slow system (12) using At 2.
Nevertheless, one might argue that these learnable mutliple scales At tn At,, are not necessary and single scale would suffice provide good empirical performance. We check this possibility on the FitzHugh-Naagumo Nagumo data set by simply setting At At,, Atl (with being the vector with all entries set to 1), for all n and tuning the hyperparameter Av. The comparative results are presented in Table We see from this table by not allowing for learnable At,, At, and simply setting them to single scale parameter At and tuning this parameter only leads results that are comparable to the baseline LSTM model. On the other hand, learning A At., At,, resulted in an enror that is factor of 6 less than the baseline LSTTM test error. Thus, we demonstrate the importance the ability of the proposed LEM model to learn multiple scales in this example.
Table Test 2 error on FitzHugh- system prediction.
Model
error (x10-²)
# units
params
LSTM
1.2
16
1k
LEM w/o multi-scale
1.1
16
1k
LEM
0.2
16
15

---

Published as a conference paper at ICLR 2022
10a
10a
Approx decay:
Approx. rate decay:
10"
101
10"
109
At
Af
Figure 5: Histogram of t..)) and (At,); for all n -1.... and i l..... of LEM after
training the 12ogle12 data
Hence, the multiscale resolution LEM seems essential for the fast-slow dynamical system. Does this multiscale resolution also appear for other datasets and can it explain aspects of the observed empirical performance To this end, we consider the Google 12 Keyword spotting data set and start by pointing out that given the spatial (with respect to input dimension d) and temporal (with respect to sequence length N) heterogeneities, a priori, it unclear if the underlying data has multiscale structure. We plot the empirical histograms of At,, At, Fig. 5 to observe that even for this problem, the terms At,, At, are expressed over a range of scales, amounting to 2 3 orders of magnitude. Thus, range of scales are present in the trained LEM even for this example, but do they affect the empirical performance of LEM We investigate this question by performing an ablation study and reporting the results Fig. In this study, we clip the values of At., At, to lie within the range [2 1], for i = 0, 1....... 7 and plot the statistics of the observed test accuracy of LEM. We observe from Fig. 6 that by clipping At. At, to lie near the default (single scale) value of results in very poor empirical performance an accuracy of a 65%. Then the accuracy jumps to around 90% when an order of magnitude range for Atn: At,, is considered, before monotonically and slowly increasing to yield the best empirical performance for the largest range of values of Atn kn. considered in this study. closer look at the empirical histograms plotted in Fig. reveal that the proportion occurrences of At,, At, decays as a power law, and not exponentially, with respect to the scale amplitude. This, together with results presented in Fig. 6 suggest that not only do range of scales occur in learned Atn, At,, the small scales also contribute proportionately to dynamics and enable the increase performance shown Fig.
95
Test acouracy in
$G
50
70
mean
65
standard deviation
2
2
2
20
Lower clipping value for At., and At.
Figure 6: Average (and standard deviation of) test accuracies of 5 each for LEM Google
where At., and At, in clipped to the ranges [ for O...., 7 during training.
16

---

Published as a conference paper at ICLR 2022
Finally, in Fig. plot the empirical histograms of At, and At, for the learned LEM the sMNIST data set to observe that again range scales are observed and the observed occurrences of At and At,, at each scale decays as power law with respect to scale amplitude. Hence, we have sufficient empirical evidence to claim that the multi-scale resolution of LEM seems essential to its observed performance. However, further investigation is required to elucidate the precise mech- anisms through this multiscale resolution enables superior performance, particularly problems where the multiscale structure of the underlying data may not be explicit.
10a
Approx. rate of decay: 0.45
Approx. rate decay: 0.53
10a
102.
102
101
161
10-7
10-5
10-3
10-1
10
10
10-2
At
At
Figure 7: Histogram of At,): : and (At,); for all n -...., N and i = .,..., d of LEM 3 training on the sMNIST data set
after
B.3 ON GRADIENT-STARE INITIALIZATION.
Specialized weight initialization is popular tool to increase the performance of RNNs long term dependencies tasks. One particular approach is the so-called chrono initialization (Tallec & Ollivier 2018) for LSTMs, where all biases input gate (by and b, in the LSTM 15) which are sampled from
to except for the bias of the forget gate well the
by log(U[[1, 1])
b, -b,
where Tmax denotes the maximal temporal dependency of the underlying sequential data. We can in Table 2 that the chrono initialization significantly improves the performance of LSTM on the Eigen Worms task. Hence, we are interested extending the chrono initialization to LEMs. One possible manner for doing this is as follows: Initialize all biases of LEM zero except for b in 3 which is sampled from
b1 [1, Tmax At T
1)).
Test accuracies on Eigen Worms using 5 re-trainings of each best performing network (based on the validation set), where train LSTM and LEM with and without chrono intialization, as well as LEM without chrono initialization but with tuned At.
Table 10:
Model
test accuracy
# units
# params
chrono
tuning At
LSTM
38.5% + 10.1 %
32
5.3k
NO
LSTM
82.6 % + 6.4%
32
5.3k
YES
LEM
57.9% + 7.7%
32
5.3k
NO
NO
LEM
88.2% = 6.9%
32
5.3k
YES
NO
LEM
92.3% + 1.8%
32
5.3k
NO
YES
We test the chrono initialization for LEM on the EigenWone dataset, where we train LEM (without tuning At. i.e., setting At 1), with and without chrono initialization. We provide the results in
Table IO, where we show again the results of LSTM with and without chrono initialization as well the I.EM result with tuned Al and without chrono initialization from Table for comparison. We
17

---

Published as a conference paper at ICLR 2022
from Table 10 that when At is fixed to 1, the chrono initialization significantly improves the result of LEM. However, we tune Åt, but do not use the chrono initialization, we significantly improve the performance of LEM again. We further remark that tuning At well using chrono initialization for LEM does not improve the results obtained with simply tuning At LEM. Thus, conclude that chrono initialization (which controls the gradients) is still advisable in order to obtain the best possible results.
successfully be adapted LEM. However, tuning At
C RELATION BETWEEN LEM AND THE HODGKIN- EQUATIONS
We observe that the multiscale ODEs (2. on which LEM is based, are a special case of the following ODE system,
dz
= F (y, (y, dy
dt F @ (y, ty, Oy
(13)
dt
As remarked in the main text, turns out the well-known Hodgkin-Hie Huxley equations Hodgkin & Huxley (1952), modeling the the dynamics of the action potential of biological neuron also be written down in the abstract form (T3). with dy = 1, d2 = 3 and the variables y modeling the voltage and z = (21, 22, 23) modeling the concentration of Potassium activation, Sodium activation and Sodium inactivation channels.
The exact form of the different functions in 13) for the Hodgkin-Huxley equations is given by,
F2(1) = (2()
Gy(y) = (x)(2) + (2))) + +
+ 8a(y))
(1(y) 0.01 + ター (2 0.1 y)
aa(y) 0.07e ~0"
10+
25t8-1
(14)
Bi (v) 0.125e .प B2(y) 4e $10 Ba(y)
+ el
(2 1) = (l) + = 2}23, H = ci (ū y) C2 y), Gyy(y) c3
with input current u and constants g. y. C1,2,3. whose exact values can be read from (Hodgkin & Huxley 1952).
Thus, the multiscale ODEs 2 and the Hodgkin-Huxley equations are special case of the same general family (13 of ODEs. Moreover, the gating functions G. (y), that model voltage-gated ion channels in the Hodgkin Huxley equations, are similar in form to At At,, in (2)
is also worth highlighting the differences between our proposed model LEM (and the underlying ODE system (2) and the
ODEs modeling the dynamics of the neuronal action potential. Given the complicated form of the nonlinearites F Fy.2. G.,z, in the Modgkin-Huxleey equations (4). cannot them in designing any learning model. Instead, building the
abstract form (13), we propose bespoke non-linearities in the ODE (2) to yield a tractable learning model, such LEM 33. Moreover, should be emphasized that the Hodgkin-Huxley equations only model the dynamics of a single neuron (with a scalar voltage and ion channels), whereas the hidden state dimension d of (2) can be arbitrary.
D RELATION BETWEEN LEM AND LSTM
The well-known LST
(Hochreiter & Schmidhuber 1997) (in its mainly-used version using forget is given by,
gate (Gers al. 2000))
y a(Wh f, ā (W
V u, + by)
i, o(W, + Viu, + b.)
o o(W,h + Vou, + b.)
(15)
C, f, @ 10 i @ o (Wh + Vu, + b)
h O. (C.))
Here, for any 1 S n < N. h, E Rd is the hidden state and c, E Rd is the so-called cell state. The
vectors i,, fn, On E R are the input, forget and output gates, respectively. u, I is the input
18

---

Published as a conference paper at ICLR 2022
signal and the weight matrices and bias vectors are given by W, W 1á000 Raxd V, Sio Raxd and b, by.io Rd respectively.
is straightforward to relate LSTM (15) and LEM by first setting the cell state Cp = En, for all 1 S N and the hidden state h, Yn-
We further need to assume that the input state i, = At, and the forget state has to be f, An. Finally, the output state of the LSTM (15) has be
O At., 1, n
Under these assumptions and by setting At = 1, we can readily observe that the LEM and LSTM [15) are equivalent.
A different interpretation of LEM, in relation to LSTM, is as follows; LEM can be thought of variant of LSTM but with two cell states yn; Zn per unit and no output gate. The input gates are At, and At, and the forget gates are coupled to the input gates. Given that the state zn fed into the update for the state yn. one can think of one of the cell states sitting above the other, leading to a more sophisticated recursive update for LEM 3 when compared LSTM (1)
Table 11:
Test accuracies on FigenWorms using 5 re-trainings of each best performing network (based on the validation set) for LSTMs with At-scaled input and forget gates, as well as LSTMs with sub- sub-sampling routines. bascline LSTM and LEM.
Model
test accuracy
# units
# params
1-BPTT LSTM
57.9% + 7.0%
32
5.3k
sub-samp. LSTM
69.2% + 8.3%
32
5.3k
LSTM
38.5% + 10.1%
32
5.3k
At-LSTM vl
53.3% + 8.2%
32
5.3k
At-LSTM v2
56.9% 6.7%
32
5.3k
LEM
92.3% + 1.8%
32
5.3k
Another key difference between LEM and LSTM the scaling of the learnable gates in LEM by the small hyperparameter At. It is natural to examine whether scaling LSTM with such small hyperparameter At will improve its performance on sequential tasks with long-tern dependencies. To this end, we propose to scale the input and forget gate of an LSTM with small hyperparameter in two different ways, where denote the new forget gate as f, and the new input gate i,. The first version (AI-LSTM v1)
i, = Alf,,
i, = Atin,
while the second version is (A/LSTMM v2)
f, =1 - At) i, = Ati,
We can see in Table [1 that both At-scaled versions of the LSTM lead some improvements over the baseline LSTM for very long-sequence Eigenworms dataset, while still performing very poorly when compared to LEM. Moreover, we can see that standard sub-sampling routines, such as a truncation of the BPTT algorithm or random sub-sampling applied to LSTMs lead to better improvements than At-scaling the forget and input gate.
E SUPPLEMENT TO THE RIGOROUS ANALYSIS OF LEM
In this section, we will provide detailed proofs of the propositions in Section 4 of the main article. We start with the following simplifying notation for various terms in LEM 3
A = Wiyn- + Viu, + b
B W2yn-1 + V2u, bg
C = Wayn-1 + V u, + b
D, = W.Z, + Vyu, + by-
19

---

Published as a conference paper at ICLR 2022
Note that for all n N, An. An C.: D, R With the above notation, LEM written componentwise, for each component $ i d as,
3 can be
z = - 1o Ato (A (1-1)//-1 y - Ato Ato (B
Atd
(16)
Moreover, we will use the following order-notation,
8 = O(a), for a, 3 R+ if there exists constants C, C such that Ca S S Ca.
(17)
M O(a), for M Id X22
R+ if there exists constant C such that |M] S Ca.
Note that the techniques of proof in this following three sections burrow heavily from those introduced in Rusch & Mishra (021a))
E.1 PROOF OF PROPOSITION 4.1 OF MAIN TEXT.
First, we prove Proposition 4.1 which yields the bound (4) for the hidden states of LEM.
Proof. The proof of the bound is split into parts. We start with the first equation in 16 and rewrite it as,
/ = (1 Ato (1-AAAAAA); 2 + Ato 1o)
Noting that the activation functions are such that S (xx) s 1, for all and -1 S oxz) S for all and using the fact that At & 1, we have from the above expression that,
z < (1 (A max 1, + Ato max 1:
S max 11
By symmetric argument, one can readily show that,
2 min min(min.))) 11,
Combining the above inequalities yields,
min(-1, 2- 1) S 2/ S max (2
(18)
Iterating 18 over n and using =/ = for all S < d leads to,
- 2 Vn, v1 visisd.
(19)
An argument, identical to the derivation of
19 but for the hidden state y yields,
-1 y Vn, VI sissa d.
(20)
Thus, we have shown that the hidden states remain in the interval [-1, 1]. irrespective of the se- quence length.
Next, we will use the following elementary identities the proof,
a
b² 1
b(a b)
b)²
(21)
2
2
for any b E R, and also,
Ea.
82
ab <
We > 0.
(22)
2
2
We fix SiS dl and multiply the first equation in 16 with 2 and apply 21 obtain,
20

---

Published as a conference paper at ICLR 2022
(2))
(z (zn-1)²
(z)
z 1)
+ AIA AA - (A 11
2
(z)
3
+
(A n- -
AI2
(6(A
( R- )2 ,) (from (T6)
(2
+
DI - (A n- (2,
2
At?
At
.)22
-1)
(as (a - 6)2 S a² + 6² + 2|a|[b])
We fix
2-At in the elementary identity 22 to yield, 1+3t
o (Ch=1)²² e(zg_1)²
Ia(C,, |o(C S
2e
2
Applying this to the inequality for (2 leads to,
(2/)²
(2 12
(AtŌ(A APO(AA o(Cn-1)2
2
2
2c
Ato
Atō (A 1)e
Atd(A
1 1-
6
1
2
2
Using the fact that 0 S (xx) S for all x E RR o² S and that line of the previous equation that,
2- At 1+Ar"
we obtain from the last
( )2 < (z), ) At At
At At) At
(2) )
V1 n.
Iterating the above estimate over n 1,..., i, for any
S and setting ñ = n yields,
A1 Ar)2
(2 < (x)) +
- At
(2,)² < fn (1+ At)²
as z 0, t, AnAt. At Taking square root in the above inequality yields.
x $ Avt Vn, A1 visidd
(23)
with defined in the expression
We can repeat the above argument with the hidden state y to obtain,
ly'll S ATT Vn, visid d.
(24)
Combining
and (24) with the pointwise bounds
19 and 20
yields the desired bound 4
E.2 PROOF PROPOSITION OF MAIN TEXT.
Proof. We can apply the chain rule repeatedly (for instance as in Pascanu et al. (2013) to obtain,
O8,
aE, 0x,, 0 Xx
Σ
(25)
00 18kSn
0x OX, 00
ae (k)
99
21

---

Published as a conference paper at ICLR 2022
Here, the notation X refers to taking the partial derivative of X with respect the parameter 0, while keeping the other arguments constant.
A straightforward application of the product rule yields,
OX,
ax,
(26)
0x
For any k << < tedious yet straightforward computation yields the following representation formula,
0x.
0x.-1 I2dx2 + A APp
(27)
Here E E 2d2dx2d is matrix whose entries are given below. For any 1 S í S d, we have,
22 22-11,2 1,2 1 = 0, j i
f
2 1,2;-1 = -
1,2j (Wi) o' -4- (W)))))())) v1 visisd
f4--1
21 = (Wy)igō (B (B visjsd
E = (W2).y o' B ( vi-1), i
21,2j
1.8-1 - (B (W 2 (B)-1) (o y--1).
2,,2
(28)
Similarly, pê,t1 E 2dx2d is matrix whose entries are given below. For any 1 S < S d, we have,
F = =0, visjs 2d,
26-1
F
--(W (A
ja
1 isisd,
21,21-1
F.-t1 = à (o
Σ (wy) ((o(C)21) - HO
A=1
(29)
Using the fact that,
max (() zE
1
the pointwise bounds the notation t. nAt for all n, the definition of 1 (6) and the definition
of matrix norms, we obtain that,
|E bl S max {1 |l + (1+ (V + W + (1 (Wall))
$ + (2 + (vt))))
(30)
By similar calculations, we obtain,
|| lo < || ol (1+ + (1+ min(), Wi + |[We)
(31)
< 1 + (2 mmin(1,
Applying (30 and 31 in the representation formula 27 and observing that At < and l < we obtain.
0x,
1 + (1 (2n At + (1 +2 min(1, Avte))n At2
OX -
r
< 1 +
At,
With
== 2 (1+ (1 3n)
(32)
Using the expression
26 with the above inequality yields,
0x,,
r
n-
<
At
(33)
0X,
2
22

---

Published as a conference paper at ICLR 2022
Next, we choose At << 1 small enough such that the following holds,
(1 1+ 2
St
51+ 11-T(=-kaa k)
(34)
for any 1 S < n.
Hence applying 34 in (33). obtain,
8X,, 12
<1+I(m K)AI.
(35)
0X
For the sake of definiteness, we fix any S o, 3 < and set (Wy),.8 the following. The following bounds for any other choice of 0 E θ can be derived analogously. Given this, it is straightforward calculate from the structure of LEM that entries of the vector 8(W yWl. given by,
al Xx
8+ O+ D(WWy)ac x+
= 0,
A + 20.
(36)
(WWy),,
2a Hence, by the pointwise bounds we obtain from
36 that
X
$ min(,,,
(37)
a y),.
Finally, it is straightforward calculate from the loss function En fly ynll that
E [0,y] y
y yd]
(38)
Ox,
Therefore, using the pointwise bounds and the notation Ý |o we obtain
OE,
min (1, Avt,).
(39)
ax,
Applying 35 37 and 339 in the definition 25 yields,
(h
< At min,,,
( min(L, (1 I'm k))t).
(40)
O(W )
Observing that 1 < k S we see that n k S n and by < typ Therefore, can be estimated for any n byy.
aclk (k) 0 )a.g
mini (+ min(1, min(1, (1+ 1sksn.
(41)
Applying the bound
in 25
leads to the following bound on the total gradient,
ak!k)
a( y).
a W y),.
fn min(1, A Av
Y min(1, (V,))) (1 lta)
(42)
$ (n + () + ((a)
< <1 Y) (1 + Y)I
which is the desired bound c for 0 (W),...-
23

---

Published as a conference paper at ICLR 2022
Moreover, for long-term dependencies i.e., k << set t2. = kAt < 1, with & independent of sequence length n, in (40) to obtain the following bound on the partial gradient.
aeh (k)
<AIAAV (1+8)( It.); (ta), Isk <<n.
(43)
i a
Remark E.1. The bound 66) on the total gradient depends on in = nAI, with being the sequence length and At S 1, a hyperparameter which can either be chosen a priori or determined through hyperparameter tuning procedure. The proof of the bound (42) relies on At being sufficiently small. would be natural to choose At ~ n for some 8 2 Substituting this expression in (6) leads bound of the form.
iEn = =0 (n((1-5))
(44)
00
If s 1, then clearly 38 gradient problem is mitigated in this case.
02
O(1) i.e., the total gradient is bounded. Clearly, the exploding
On the other hand, takes another value, for instance during the hyperparameter training (see Section B. then we can readily observe from (44) that 8E 88 = On). Thus in this case, the gradient can grow with sequence length n but only linearly and not exponentially, Thus, the exploding gradient problem is also mitigated in this case.
which is empirically observed
E.3 PROOF PROPOSITION 4.3 OF MAIN TEXT.
To mitigate the vanishing gradient problem, we need to obtain more precise characterization of
(*(
the gradient 20 defined in (25) For the sake of definiteness, we fix any 1 S or , < and set
0 = (W v)a.9 the following. The following formulas for any other choice of 0 E: θ can be derived
analogously. Moreover, for simplicity of notation, set the target function X,, 0.
Proposition
4.3 is a straightforward corollary the following.
Proposition E.2. Let yn Un the hidden states generated by LEM then we have the following representation foreeall for the hidden state gradient,
de(k) 00 AIõ A16(B%-)))
(2)22 (y -in)
d
+ )o
Σ
(y.. - vdh Σ
d'(B(_,) (o(D)) (((D))-y(_)) v2-i) (W2)5.2a (45)
ø=
+ A (B
Σ (BBL)) - yi)) + +(AN))
Here, the constants in O could depend y defined in (main text).
(g(h)
Proof. The starting point for deriving an asymptotic formula for the hidden state gradient 38 is
to observe from the representation formula (27). the bound (31) matrices Fê,-11 and the order notation (17 that,
0X.
Indx2d + A 2 +
(46)
0X
as long as y is independent of At.
By using induction and the bounds sentation formula for the product,
30 it is straightforward to calculate the following repre-
0x
0x
n
II k<PEn
I2dx2
At
Σ
B+6-1 + O(A12).
(47)
Ox
0x
24

---

Published as a conference paper at ICLR 2022
Recall that we have set 6 (W wy)a, Hence, by the expressions (38 and (36). direct but tedious
calculation leads to,
0+ X
2dx2d
(B (y% - -
(48)
00
8
0*
Ee,e-1
(49)
0x,
00
k=++1
d
"
(t (D
Σ
(yd
v4)
Σ o' d'(B/_1) (o(D))- - v2-1) (W2) ビ=
Σ
o (y -v
t=
(50)
Therefore, by substituting the above expression into the representation formula sired formula 45).
yields the de-
In order to prove the formula (see Proposition 4.3 of main text), we focus our interest on long- term dependencies i.c., k << n. Then, a closer perusal of the expression in (48). together with the pointwise bounds (4) which implies that Vk-1 = O( At), results in the following,
oE, 0 Xx O (At
2dx2d
(51)
0x,
00
Similarly, we also obtain.
OE, Ox, E
O+ X
O (Av²)
A
(52)
00
Combining 551 and (2) results in the desired asymptotic bound
Remark E.3. The upper bound on the gradient (6) and the gradient asymptotic formula formuul the choice the timestep hyperparameter At. For sequence length n, if we choose At ~ n with s =20 O, we see from Remark E.1 that the upper bound on the total gradient scales like (in())))) On the other hand, from 77. the gradient contribution from long-term dependencies will scale like On Hence, small value of s z O, will ensure that the gradient with respect long-term dependencies will be (1). However, the total gradient will behave like O and possibly blow up fast. Similarly, setting s = 1 leads to a bounded gradient, while the contributions from long-term dependencies decay as fast as - Hence, one has to find value of 8 that balances both these requirements. Equilibrating them leads to -. ensuring that the total gradient grows sub-linearly while long-term dependencies still contribute with a sub-linear decay. This value is very close to the empirically observed value of = 1/2 which also ensures that the total gradient grows linearly and the contribution of long-term dependencies decays sub-linearly in the sequence length n.
7 impact
E.4 PROOF OF PROPOSITION
Proof. To prove this proposition, we have construct hidden states yn. Zn. output state Wn, weight matrices W1.2.9.2. Wy, V1,2,,2 and bias vectors b1,2,y.2 such that LEM (3) with output state Wn Wyy, approximates the dynamical system (8).
Let R² > R >>>> 1 and ex < e, be parameters to be defined later. By the theorem for universal approximation of continuous functions with neural networks with the tanh activation function tanh (Barron 1993), given e", there exist weight matrices W1 E Rd xdn, Vi E xdd W2 e gd xdi and bias vector 61 E 1dd1 such that the tanh neural network defined by.
(h, u) = W2a (W,h- + Vi + b1), approximates the underlying function in the following manner,
(53)
max [[l)
[[ u) - N₂ (h, u)ll S c*
(54)
Similarly, one can readily approximate the identity function g(h, u) h with tanh neural network of the form,
Na(h) W20 (Wah).
(55)
25

---

Published as a conference paper at ICLR 2022
such that
max | <R
(g(h) - -N2(h)] E
(56)
Next, we define the following dynamical system,
Zn W20 Winn-1 + Vn + b1),
(57)
yn W20 (Wiz.),
with initial states Zu = yo =
Using the approximation bound (44) we derive the following bound,
11 yn1 ||e
nn + In Snll |l
If (Øn-1 Un)
W20 (W18n-1 + Viu, + +b1 || + ll((z)) - W20 (Wiz,) ||
If (Øn-11 11 un) -f un) || + |f (In-1, un) W20 (WiYn-1 Viu, + b1)
llg (..) W20 (Wiz.) ||
S Lip(f)
yn- 2E" (from 54). (6
Here, Lip(f) is the Lipschitz constant of the function f on the compact set {(h, u)
Rda xd.. |/]]| |w||| < }. Note that one can readily prove using the fact that Yo = Zn = 0,
bounds (54). (56) and the assumption || ||u, < R, that ||,, ll Vlll R 2R.
Iterating the above inequality over n leads to the bound,
1 Fnll 2c"
Lip(f)*.
(58)
A=
Hence, using the Lipschitz continuity of the output function o in 88. one obtains,
||o, o(yn))l 2 "ip((o) Σ Lip(f)*
(59)
2=
with Lip(o) being the Lipschitz constant of the function o on the compact set {h E Rda ||||| R*}.
<
Next, we can use the universal approximation theorem for neural networks again to conclude that given tolerance there exist weight matrices W3 ddaxda, W1 e Idd Xdg and bias vector bo E Rd such that the tanh neural network defined by.
Na(h) = W40 (Wyh + b2),
(60)
approximates the underlying output function the following manner,
|]o(h) Na S |
max
(61)
Now defining,
Sn W4 (Way,, + bz),
(62)
we obtain from 61 and (59) that,
Io,, Selll 2c (epppo
(63)
2=0
Next, we introduce the notation,
Sn = a (W1yn-1 Viu, + bi), Yn = a (Wizn)
(64)
From (5). we see that
2, W2Bn, yn Way
(65)
26

---

Published as a conference paper at ICLR 2022
Thus from 65 and 63
have
Wn W40 (WzW2yn + bb),
(66)
= Wi (W3W20 (WWW22.) + b2).
Define the function R Rdd x Rd + Rd by,
R(2) Wio (W3W20 (W, + b2)
(67)
The function, defined above, is clearly Lipschitz continuous. We can apply the universal ap- proximation theorem for tanh neural networks find, for any given tolerance weight matrices W, e Rdsxds, We Rdoxds, 1/2 E RRdsxds and bias vector by E I2 such that the following holds,
max mAx (I=x)
[[((2) WW b8) S ē.
(68)
Denote Wn Woo + by). then from 68 and (66). obtain that
| Wn S S.
Combining this estimate with 663 yields,
| اللة S + Lip
Σ Lip(f) A=
(69)
Now, we collect all ingredients to define the LEM that can approximate the dynamical system To this end, we define hidden states Zn: Yn
(
RR 2dh as
2x Bn, 2n),
Yn = 5n
with nn 2n, Nn In Rdh These hidden states are evolved by the dynamical system,
W1 WWW2 0
y + [Viu,, 0J - + [bi, 1b1.00-))
z =
(70)
[WW,
0
2, + +1000 + 10, bsl+t
y =
W/s
0
and the output state is calculated by,
w 10, Woly
(71)
Finally, we can recast the dynamical system 70 (1 as a LEM of the form 3 for the hidden states
Yu; Zn, defined in (70), with the following parameters, Now, define the hidden states yn, nn E Rdy for all 1 < n S N by the LEM B with the following parameters,
At 1, dy 2dh,,
W, W₂ = V1 v2=0 =0
b1 b2 bxo
Wi W2
W
Vg [V1, 0].
b, = [b,, 0]
(72)
0
0
W W2
W
V, 0.
b. bs).
W
[0, Wal.
Here, boc E dR. is defined
b = |boo ...................... be............bbb bool,
with << Doo such that
(bboo)l < 8.
(73)
The nature of the sigmoid function guarantees the existence of such a d for any As 8 decays exponentially fast, set it to in the following for notational simplicity.
27

---

Published as a conference paper at ICLR 2022
It is straightforward to verify that the output state of the LEM (3) with parameters given in Wh Wn. Therefore, from (69 and by setting 3. ē
72 is
and
N
(Tip(o) A=0
Lip(f)A
prove the desired bound 9
E.5 PROOF OF PROPOSITION 4.5
Proof. The proof of this proposition is based heavily on the proof of Proposition 4.4 Hence, we will highlight the main points of difference.
As the steps for approximation of a general Lipschitz continuous output map are identical to the corresponding steps in the proof of proposition (444 (see the steps from Eqns. (59) to (69). we will only consider the following linear output map for convenience herein,
o Weth..
(74)
Let > R>> and Ex e, be parameters be defined later. By the theorem for universal approximation of continuous functions with neural networks with the tanh activation function o = tanh, given c", there exist weight matrices W w Rd Rdixd, Vf E Rddxdd W E Rd xd, and bias vector bf Rdd such that the tanh neural network defined by,
(y c, u) = W a (w/h- W c Vs'ut + bg).
(75)
approximates the underlying function in the following manner,
max max ma <R |lf(h, u) ( Se:
(76)
Next, we define the following map.
G(h. = g(h,c,)) (1-
(77)
for any
By the universal approximation theorem, given e", there exist weight matrices WT. W e Xd,,,,, vi Rdaxd. Wy E Idd xda and bias vector by E dd such that the tanh neural net- work defined by,
(h, = Wif (WPh+ w +
(78)
approximates the function G 77 in the following manner,
max max wtw.lllllllll (=)))) |GG(,, - Ny
(79)
Note that the sizes of the neural network Ng can be made independent of the small parameter 7 by simply taking the sum of the neural networks approximating the functions y and (h, c, u) with tanh neural networks. As neither of these functions depend on the small parameter т, the sizes of the corresponding neural networks are independent the small parameter too.
Next, as in the proof of proposition 4.4 one can readily approximate the identity function f(h, c, u) = h with a tanh neural network of the form,
(h) Wzo (Wih),
(80)
such that
max ||
11 - s
(81)
28

---

Published as a conference paper at ICLR 2022
and with the same weights and biases, one approximate the identity function @(h, c, u) with the tanh neural network,
Ng(c) W20 (Wic).
(82)
such that
max [MI c) Nc((el Sτ.
(83)
Next, we define the following dynamical system,
2n W (Wisn-1 w + bb)
nn = W20 (Wi8n-1).
(84)
yn = (1 - 1-Tr -iynn-in W (W + Wm + U, + b9))
yn = W20 (Wi2n)
with hidden states 2n 2n,8n: Nn. In E Rd and with initial states 20 = 20 = -8o = =5o = 0.
We derive the following bounds,
|| 1 - 2 = [F[ n-1: - un) - w'fo (W/S W + +b/) |I
< [f( 1n- un) - f(ýn-1 1 un)
+ |[f(ín -1 un) - WW3o (W -n W V/'u,, un + bby
< Lip(f) (1 2n- || + 2|| - 2 + || vn-1ll) +e" (by (79)
x Lip(f) (1102-1 - || + || - 8n-1ll) + (1 + (L)p(f))
(by 81 84)
and
8,.l = [1(1 () - 8n + b. - W (W + Wf2, + V/ + 69)) II
2/ un)
< 11 n1 - 8n-1 + + G(Ø,; nn un) - G(2n, 2n un)
+ G 2n, 2n, u,) - W3' (W nn + W/2, 2n + V70 u, + 8P)
< || - 8n- + (l00, 2nl1 + | 8n- || + - + TT=,
< (1 + +7 + Lip G2 2Lpp())--- (f)
(L)
+ -n
22
where the last inequality follows by using the previous inequality together with (84 and 83
As < 1, it is easy to see from 77) that Lip(G) < Lip(g) + 7. Therefore, the last inequality reduces to,
||,b, Snll S (3 + (1 Lipp())) 8--1ll + (2 + rTipp() 2n-1ll
+ ( (2 + rTipg)))) + 2Tip(f)))e*
Adding we obtain.
| 2nl1 + 1|4, Snl S C* (10m-1 2n-1l -
- 8n-1ll)
D'e,
(85)
where,
C - Lix)
(86)
D = + (2 + Lip(g) + 2Típ(f)).
Iterating over leads to the bound,
| - 2n + ||bb, - 8nll S Eoo
(87)
Here, Lip(f), Lip(g) are the Lipschitz constants of the functions f. g on the compact set {(h, c, u) e
Rd, [/hl], [|]]] |ull| < R*). Note that one readily prove using the zero val-
ues of initial states, the bounds 81. 83 and the assumption |0, ||u, < R, that
|| Ib [2,l] [1 Il. || < R 2R.
29

---

Published as a conference paper at ICLR 2022
Using the definition of the output function 111 and the bound
87 that,
I - o(8 [eelle" D R-1
(C
(88)
x=0
Defining the dynamical system,
y = a WW W. WW V/ un
by)
n = a (WiW3y
(89)
y (1 - -)yy TO (WPW3ZZ + w2W2z, + U2 + t(9
nn = W/ 2
By multiplying suitable matrices (84). obtain that,
2 Wg z, 2, WzZ,: Yn Wyy ýn W2y..
(90)
Finally, in addition م0 defined in 588 for any given T E (0, 1]. we introduce b, E defined by obb,)= = T.
(91)
The existence of unique b, follows from the fact that the sigmoid function à is monotone. Next, we define the two vectors bo b, E 2dds as
by_ b
A 1 iis 2dh.
by by,
v S i du,
(92)
by boo: dd + +isis 2dh.
We are now in a position to define the LEM of form (3). which will approximate the two-scale
dynamical system (TO). To this end, define the hidden states Z,.Yn E R2dx such that z,
l2 2n] and yn
y vn]. The parameters for the corresponding LEM of form (3) given by,
Al 1, dy 2dh
W, W2 = V1 = V2 = 0,
b Door b2 b
W, W WW/WW W
W/W, W2
(93)
V. [V/0],
b = [bf. 0),
W
W, W
WWW,
V, = [VP0].
b, [b 0].
W
and with following parameters defining the output states,
W, = [W, 0].
(94)
yields an output state Wn Wyyn.
It is straightforward to observe that wn = o(fx). Hence, the desired bound (11 follows from 87
by choosing,
c" N-1
D Σ (C*)A
4.5 can readily extended to prove the following proposition about general r-scale dynamical system of the form,
The proof of proposition
$ = 7, (+) n- $²
0f un);
&² = n/ ( &²
Φ Un
(95)
6. = 7, (1/ x
Φ un),
O, = 0 Φ² 1%).
30

---

Published as a conference paper at ICLR 2022
Here, 71 S 72 ........ T. 1, with r > 1, are the r-time scales of the dynamical system 9 We assume that the underlying maps fl.2.... are Lipschitz continuous. We can prove the following proposition,
Proposition E.4. For all 1 S n N. let 6)2 ,0, be given by the r-scale dynamical sys- tem (95) with input signal Un. Under the assumption that there exists a R 0 such that [ Il. 1o
[|u, < R. for all 1 S S. N, then for any given 0, there exists a LEM of the form 3.. with hidden states Yns Zo and oulput state wa with wi. Wyn such that the following holds.
Io - e, visnSN.
(96)
Moreover, the weights, biases and size (number of neurons) of the underlying LEM 3 are indepen- dent of the time-scales 22.2....."
F LEMS EMULATE HETEROGENEOUS MULTISCALE METHODS FOR ODES
Following Kuehn 2015), consider the following prototypical example of fast-slow system of ordinary differential equations,
O'(t) = (f( -),
(97)
(t()) = g v))
Here Φb, 2b E Th'" are the fast and slow variables respectively and < << is small parameter. Note that we have rescaled time and are interested in the dynamics of the slow variable sb(t) in the time interval [0, T].
A naive time-stepping numerical scheme for 997 requires time step size öt ~ O(T). Thus, the computation will entail time updates to approximate the solutions of the system (97) One such popular ODE solver can be derived by
((/T). Hence, one needs a multiscale ODE solver
using the Heterogenous multiscale method (HMM); see Kuehn (2015) and references therein. This
in turns, requires using two time stepping schemes, macro solver for the slow variable, with time step At of the form,
(98)
Here, the time step Ât < is independent of the small parameter T.
Moreover, the fast variable is updated using micro solver of the form,
Φ Φa- o (k-1) (t(f(1n-1) - 1SkSK.
(k)
Φ, -0--1
(99)
(0)
Note that the micro time step size and the number of micro time steps K are assumed to indepen- dent of the small parameter 7.
is shown in Kuehn (015) (Chapter 10.8) that for any given small tolerance e > O, one can choose a macro time step At, a micro time step St, the number K of micro time steps, the number N of macro time steps. independent of such that the discrete states s/,, approximate the slow-variable (t,,,) (with L, n.t)) of the fast-slow system (97 the desired accuracy of
Our aim is to show that we can construct a LEM of the form (3) such that the states Φ.,, th,,, defined in (98), (99) can be approximated arbitrary accuracy. By combining this with the accuracy of HMM, we will prove that LEMs can approximate the solutions of the fast-slow system (97) to desired accuracy, independent of the small parameter in (97).
Proposition F.1. Let &.., 2,,, Im " for S n N, be the states defined by the HMM dynamical syslem 198 199.. For any given > O, there exists a LEM of the form (3) with hidden states (Zn, Yn). where Zn Yn Reem and output states wht wh such that the following holds,
max {1lØ, wi 11 will Se, VI
(100)
31

---

Published as a conference paper at ICLR 2022
Proof. We start by using iteration on the micro solver 999 from & 1 to K to derive the following,
Φ, öt n-1 + (1 ( f4)
(101)
öt (1 -ôt) öt)K
As öt L, we have that of < 1.
By the universal approximation theorem for tanh neural networks, for any given tolerance e", there exist weight matrices W/' E Rddxxm Wy Rmxds and bias vector bf IRds such that the tanh neural network defined by,
Ny(c) = o (Wfc+ +b).
(102)
approximates the underlying function f in the following manner,
[If(c) - Ny(e)l st. |||
max
(103)
Next, we define the following map,
=(h,c)=g((4 tc,
(104)
By the universal approximation theorem, given e", there exist weight matrices WP. W Rdaxm, Wa E Rmxd and bias vector by E I2d2 such that the tanh neural network defined by,
(h, W (Wih + Wye+ b9)
(105)
approximates the function G (104) in the following manner,
max la
ch, Ng c)ll S c*.
(106)
Next, as in the proof of propositions 4.4 4.5 one can readily approximate the identity function f(h, c) = h with tanh neural network of the form,
Ny(h) W2a (Wih),
(107)
such that
max I|A | and with the same weights and biases, one can approximate the identity function g(h, = c with the Tanh neural network,
sc.
(108)
Ng(c) W20 (W1c).
(109)
such that
max | I<
se.
(110)
Then, we define the following dynamical system,
z, Ötz, + (1 w/fo (Wism-1+bb))
2, Wzo (Wiýn-1).
(111)
yn (1 Ât)ýn-It StWy (W W.T.,, + +))),
yn Wi0 (W12n).
with hidden states 2,, 2n fn. Fn E Rm and with initial states 2n = 2μ yo = Yu = 0.
Completely analogously as in the derivation of (87). can derive the following bound,
10 2n ll + 11 Snll c"c. with constant C* C (n,
(112)
32

---

Published as a conference paper at ICLR 2022
Defining the dynamical system,
z ötz,, + (1 (1-ôtto ôtjo (WiW33n-1+th)
nn (WaW3yn-.)
(113)
y (1 - (1-A))ynit Âto (WiWfZZ++ WWW22 69)
yn (WiW?
By multiplying suitable matrices
113 we obtaín that,
2, = W3 2
2, WzZn,
Yn = Wyy Yn = W28n.
(114)
In addition to boc defined in 58 for ot E (0, 1], we introduce by E R defined by
ô ((bs) öt.
(115)
Similarly for Á (0. 1]. we introduce ba E defined by
o(ba) = Át.
(116)
The existence of unique by and ba follows from the fact that the sigmoid function is monotone. Next, we define the two vectors boo by, ba E R
by by.
V 1 S i m,
bj- Doon
A m 15is 2m,
(117)
by bai
A1 S m,
b/ = boo
Vm - 1 < 2m.
We define the LEM of form
(3) which will approximate the HMM
To this end, we define
the hidden states Zn, Yn corresponding L.EM of form 3 given by,
IR 2 such that 2, (2, 2 and yn y y The parameters for the
At 1, dy 2m
W = W₂ = V1 = V2=0 =0
b b&, b2 ba:
W, W 0
(118)
V 0,
b, = 16/. 0].
W. W.W
0
WWW
WWW,
W # = W.W!
V, = 0, b. = 141.0].
0
The output states are defined by,
w W 2n
w Wgy"
(119)
straightforward observe that w/t 2n wi yn. Hence, the desired bound TOO follows from (112) by choosing,
C
33


Reviews:
[{"review_id": "yf4x4iabKdW", "reviewer": "Reviewer_AvfW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors give an accessible overview of the variety of RNN modifications already proposed to help capture long-range dependencies. It would be useful to clarify somewhat how their approach (LEM) differs from the variety of ODE-based methods listed in Section 3. I would also note that there exist approaches to RNN analysis and modification entirely outside the 'vanishing gradient\" framework, e.g. those based on statistical definitions of long-range dependence.\n\nThe LEM model is itself clearly motivated and introduced. It is somewhat unclear, however, what happens to the interpretation of $y$ and $z$ (originally slow and fast variables, respectively) when the timescales are parameterized and learned. Instead, as discussed in SM$\\S$C, the interpretation seems much closer to that of the cell and hidden state in an LSTM (also: slight notational typo in the final line of Eq (15)). The main difference to LSTM appears to be a more sophisticated recursion on the hidden state and the introduction of the timescale hyperparameter $\\Delta t$.\n\nThe experiments are extensive and show that LEM consistently achieves better performance on a range of tasks than several recent and state-of-the-art competitor RNN architectures. On the other hand, it seems somewhat concerning that both model performance in practice and some of the analytical results appear sensitive to the choice of $\\Delta t$. Choosing a small $\\Delta t$ practically guarantees that the cell and hidden states will persist over long timescales; rather than being learned, this behavior is directly selected as a hyperparameter. How is this different from adding a hyperparameter to LSTM to control the range of the input and forget gates?\n\nFinally, the notion of multiple timescales is claimed as central to the motivation for the method proposed, but despite the extensive experimentation relatively little is done to understand whether and how such behavior arises in the trained LEM models - in fact only a few sentences on this topic appear outside the supplement. There are some questions here that seem relevant to understanding this method in greater detail:\n- What is the interpretation of results in SM$\\S$A? The observation of a broad range of timescales does not necessarily imply that they are important for model performance. There might be some relatively straightforward ablation experiments here (e.g. clipping or removing this variation in timescales) that could address this question more thoroughly.\n- The power law behavior of timescale frequencies is interesting, but doesn't its slope suggest that the trained models in fact place very little emphasis on representing changes over long timescales? Note that this is exactly the opposite behavior of long memory stochastic processes, which have power-law spectral density functions that *increase* in power at low frequencies.\n- To the extent that the relevant timescale(s) vary across the variety of tasks introduced, is this observed in the learned timescales of the LEM models?\n\nOther comments:\n- Prop. 4.2: Why would there be a \"ground truth\" cell state $z$? It makes sense for $y$ as that's the prediction target, but a ground truth $z$ seems to suggest some assumption on how the data is generated.\n- I don't understand the \"ablation study\" reported in Sec. G of the Supplement. What exactly is being ablated? The figure seems to show test accuracy as a function of $\\Delta t$. \n- The statement in Section 6 that natural language and speech data do not necessarily contain long-range dependencies is contrary to quite a large body of empirical and statistical analysis of such data.", "summary_of_the_paper": "The authors propose a new RNN architecture, long expressive memory (LEM), motivated by a system of ODEs with multiple time constants. They prove that it can avoid the vanishing gradient problem while retaining the flexibility to approximate a broad class of dynamical systems. They report comparable or improved prediction performance of LEM-based sequence models across a very wide variety of tasks, as compared to several recent alternatives.", "summary_of_the_review": "The proposed method is clearly presented and thoroughly demonstrated in terms of prediction performance across many tasks. However, there is surprisingly little investigation as to whether it learns representations at multiple timescales or how important these are to its success, and there is some uncertainty as to the sensitivity of results with respect to the hyperparameter $\\Delta t$. My score reflects these weaknesses but could be improved if they are sufficiently addressed or rebutted.\n\nUPDATE: Following the authors' responses to this review and others, I have improved my evaluation of the technical significance and my overall recommendation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "q03MNrypm8u", "reviewer": "Reviewer_Cggm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. They introduce an architectural gadget for sequence modeling that appears to a) add multi-scale sequence modeling explicitly in the model, b) (somewhat) stabilize gradients in training, and c) be very expressive. \n2. They justified their claims with experiments that demonstrate the benefits of the architecture on some small datasets.\n3. They proved some expressivity theorems and bounded the size of the resulting gradients. \n\n\nComments: \n\n1. What is meant by \"LEM is gradient-based\" and \"gradient-based architecture\"? I would refer to the model in the way I did in the summary of the paper -- you're giving a circuit for the model architecture which is defined by discrete time updates of a system of ODEs.\n2. What is meant by an \"algorithm for your model\" (in the line \"In order to realize a concrete algorithm for our model\")? (see above, circuit is probably a better word here).\n3. I found the notation for X_n unnecessarily complicated. Just say X_n = [x_n, y_n]. Likewise just define E_n as (1/2) \\|y_n - y_n*\\|_2^2.\n4. Originally, before reading Remark D.1, I wrote the following: \"I don't follow the conclusion after Prop 4.2. You just proved a bound on the gradient that depends on the l-infinity norm of (y*, z*), which in Prop 4.1. you showed to be bounded by Theta(sqrt(n)) (where n is the number of iterations). So it seems like the gradient is bounded to grow in l-infinity norm with at most sqrt(n), but as n -> infinity this certainly blows up, just at a sublinear rate. Am I missing something? I see later you assume that the ground truth (y*, z*) norms are constant; why is this a reasonable assumption? I also see that later on in the supplement, you say that t_n <= 1 -- I don't follow why this is. (Also this should be stated in the main text). Aren't you just choosing N bounded in that case, in which case yes, by default anything that grows with N will be bounded?\" Two points after this: 1) You should make these points clearer in the main text; 2) I see it actually grows as a polynomial of T -- why are you saying you can simply rescale T? It seems to me that if the weights/gradients grow with polynomially with T, you have not actually achieved bounded gradients -- this is my main issue with the paper so far, so an explanation would be appreciated. Is it just that the growth is not exponential with T? If that's the point, it should be emphasized. \n\n5. In Eq. 7, should it be Theta instead of big O? Also why include the square term when it is dominated by the 3/2 term?", "summary_of_the_paper": "This paper introduces a model class of neural networks whose architecture is defined by a circuit that computes a discretized step of a pair of multi-scale ODEs. The key novelty is on the multi-scale aspect of this system. In terms of representation capability, this class can represent LSTMs (and vice-versa) and can also approximate any dynamical system from a very broad class of dynamical systems (as well as multi-scale dynamical systems). The authors also prove upper bounds in l_infinity on both the hidden state values and the gradients, and argue this addresses the exploding gradient problem. They also address the vanishing gradient problem by arguing that the magnitude of the partial gradient corresponding to the contribution that depends on step k of the circuit does not depend on k.\n\nThey then present a variety of experiments using this new architectural component for modeling several sequence problems. They include a small study on the multi-scale nature of the datasets they study as well.", "summary_of_the_review": "Overall, I recommend accept conditional on satisfactory explanations to some of my questions -- it's an interesting, relatively principled derivation of an architectural gadget for long range sequence modeling, building on the recurrent network modeling approach rather than the popular attention based approach. I like the idea of deriving the architectural updates from ODEs which have the desired properties you want. I thought the theorems were not that strong, but fine in terms of giving a little motivation for the architecture. Overall the experiments were good, though they tended to only be on rather small datasets. \n\n\nUPDATE:\n\nThanks for the clarifications, I updated my correctness score and still vote to accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kv8lAl8IkQU", "reviewer": "Reviewer_4Tp1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "According to my initial review, it is a nice paper with a lot of empirical and theoretical evidence to support the claims. I have below minor concerns/comments:\n\nOne of my concerns is on the delta_t (not in bold), which is a critical hyper-parameter in discretization ODEs and turns out to be essential for performance.\n\n-- First, the bound of proposition 4.1 could be pretty significant, which is O(sqrt(n)) given the condition that delta_t<=0.5.  With this in mind, it seems the uniform norm in proposition 4.2 could also be large unless delta_t is very small, especially for huge N. However, if delta_t is too small, the value of partial gradient (i.e., equation 7) could be pretty small.\n\n-- Second, it seems delta_t is a key hyper-parameter for performance for different tasks. Although the authors provide some motivations for selecting delta_t, the motivation heavily depends on the understanding (experience) of the tasks and datasets. Not sure if the users have some systematic way of choosing that hyper-parameter. It is still possible that larger delta_t could still lead to exploding gradient issue, while too small delta_t might result in slow learning.\n\n-- One conclusion that the authors have is that small delta_t would benefit tasks that require long dependency. I can imagine that small delta_t could be more friendly to mitigate the gradient exploding issue, especially for the extremely long input sequence. But there should be a sweet spot between 0 and 1 (the default value) for tasks that require long-term dependency.\n\nMy second minor concern is the experiments.\n\n-- One suggestion is to compare with some existing ODE-based methods in more tasks, if possible.\n\n-- The other small thought could be a bit far away from the RNN scope. Basically, for many audio and natural language processing tasks, bidirectional model, CNN, and transformer-style models are pretty common choices. I am not sure if the authors are further interested in comparing in these scenarios. For example, the bidirectional modeling (and using CNN to reduce time resolution) could help handle long-term dependency for LSTM and GRU.\n\nFinally, I am not sure if I aligned with some claims in the draft.\n\n-- I would not prefer that the authors claim that the proposed methods outperform other recurrent models in ASR. I would more prefer directly saying that the proposed methods work very well for keyword spotting.\nFor claiming ASR, the authors could consider using some widely used small/medium-size data sets (TIMIT, WSJ) and try CTC recognizers [1]. It could be interesting to see the delta_t (in bold) distribution for representations learned by phone-CTC, character-CTC, and word-CTC. It could be another piece of evidence to support the multiscale potential of the proposed method.\n\n-- I am also not sure if it is good to claim that language modeling and speech recognition do not need long-term dependency, although there are rich short-term patterns. I would recommend the authors look into the k-word frequency pattern and delta_t (in bold) and their correlation.\n\n[1] https://www.cs.toronto.edu/~graves/icml_2006.pdf", "summary_of_the_paper": "The paper tries to propose a new recurrent architecture that could address the well-known issues (of recurrent models) like vanishing gradient and exploding gradient. The architecture is a kind of a realization of numerical discretization of ODEs using an implicit-explicit time-stepping scheme. The authors clearly explain why the designed model architecture can capture multiscale data. The authors also connect the proposed method to vanilla LSTM, Hodgkin-Huxley equations, and heterogeneous multiscale methods for ODEs.\n\nThe authors also try to provide theoretical evidence that the proposed methods mitigate the gradient exploding and vanishing issues (under some conditions) while learning informative representations for long/short sequence data.\n\nThe authors tried on many tasks across different domains, and the proposed methods consistently outperformed the baselines. The benefits are pretty significant in some tasks.", "summary_of_the_review": "Currently, I think the paper is a good one for ICLR. I incline to accept it. I am also open for further discussions and adjusting my scores if needed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dCEBtnzAzi", "reviewer": "Reviewer_M6L8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found this paper well-written and relatively easy to read, considering the amount of theoretical and experimental results presented. I was able to follow the theoretical arguments well, though I did not check the proofs line-by-line. Intuitively, the proposed LEM is a type of LSTM with no output gates and two cell states per unit instead of one: $z_n$ and $y_n$. $\\Delta t_n$ and $\\overline{\\Delta t_n}$ are the two corresponding input gates, and the forget gates are \"coupled\" to the input gates. Finally the cell inputs for $z$ are $y_{n-1}, u_n$ while those for $y$ are $z_n, u_n$. Thus the $y$ cell \"sits above\" the $z$ cell.\n\nThe design is new and interesting, and I can see the intuitive appeal (which is supported by the theoretical connections/results). The theoretical results related to vanishing/exploding gradients also seem intuitive: they are reliant on small enough values of $\\Delta t$, which will bring both cells close to copy behavior (like in LSTMs) which propagates gradients well.\n\nIt is also a strength that the paper presents experimental results on a variety of benchmarks with different types of data, though it should be noted that all benchmarks are small-scale (which should be sufficient for the purposes of this paper).\nThe results are very good across the board, with LEM beating LSTM/GRU in particular across the board.\n\nThis brings me to my main objections to this paper. I am uncertain that the LSTM baselines are as strong as they should be for various tasks considered, and this might be misrepresenting the performance that can be achieved using LSTMs. I recommend that the authors consider the Chrono initialization [A] as a starting point, and obtain their own baseline results instead simply taking them from other papers that may or may not have been diligent in evaluating baselines. The results in that paper can not be directly compared to those here, but they are very suggestive: at least for $T$=750 on the adding problem, the LSTM was able to learn rapidly (in 500 to 1000 steps), so it would be surprising if it fails completely for longer lengths. This should also be relevant for the EigenWorms dataset etc. For pMNIST, the Chrono init paper reports a result of 96.3% on the val. set (compared to 92.9% reported in the present paper), although that is without tuning model size or hyperparameters.\n\nIn my opinion, the above observations make a strong case that the baseline results (at least for LSTM) might be too weak in this paper, potentially misleading the authors/readers into just how much of an improvement LEM provides in practice. Since this is a nice paper in other aspects, I hope that the authors will invest in addressing this issue so that I can increase my score (if the results remain interesting).\n\n[A] Tallec, C., & Ollivier, Y. (2018). Can recurrent neural networks warp time?. arXiv preprint arXiv:1804.11188.\n\n—\nUpdate: The authors have addressed my concerns related to experimental results, so I am updating my score from 6 to 8. Of course more work is needed to generally prove the wider utility of the new architecture since all tasks here are small scale, but the initial results are interesting enough to warrant a wider examination by the community.", "summary_of_the_paper": "This paper introduces Long Expressive Memory (LEM; Eq. 3) which is a new architecture for recurrent networks derived from discretization of a particular system of multi-scale ODEs (Eq. 2). It presents interesting theoretical results that characterize the properties of the proposed architecture (Sec. 4). The key results are that under certain conditions (e.g. fine discretization) the gradient propagation through time is well behaved, and that it is expressive enough to represent general dynamical systems, and multiscale dynamical systems in particular. Empirical results are presented on the adding problem, a synthetic two-scale dynamical system, sequential MNIST/CIFAR-10 classification, EigenWorms classification of very long time series, heart rate prediction, the Speech Commands dataset, and character-level modeling on Penn Treebank (Sec. 5). Across all tasks, the authors report best performance using the proposed architecture when compared to various methods in the literature. ", "summary_of_the_review": "The paper is well written and the presented architecture is intuitively appealing and supported by reasonable theoretical results. The experimental results are interesting but their significance is unclear since I am not convinced that the LSTM baselines are strong enough, based on prior work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new recurrent architecture based on discretization of ODEs which allow for learning multi-scale representations and help with the vanishing gradient problem.
The reviewers all agree this architecture is novel and provide substantial theoretical and empirical evidence.
A strong accept.
Decision: Accept (Spotlight)