Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.

The 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.

The authors tried on many tasks across different domains, and the proposed methods consistently outperformed the baselines. The benefits are pretty significant in some tasks.
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:

One 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.

-- 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.

-- 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.

-- 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.

My second minor concern is the experiments.

-- One suggestion is to compare with some existing ODE-based methods in more tasks, if possible.

-- 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.

Finally, I am not sure if I aligned with some claims in the draft.

-- 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.
For 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.

-- 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.

[1] https://www.cs.toronto.edu/~graves/icml_2006.pdf
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
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.

The 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.

It 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).
The results are very good across the board, with LEM beating LSTM/GRU in particular across the board.

This 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.

In 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).

[A] Tallec, C., & Ollivier, Y. (2018). Can recurrent neural networks warp time?. arXiv preprint arXiv:1804.11188.

—
Update: 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

The 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$.

The 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?

Finally, 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:
- 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.
- 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.
- 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?

Other comments:
- 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.
- 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$. 
- 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_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.

UPDATE: Following the authors' responses to this review and others, I have improved my evaluation of the technical significance and my overall recommendation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

They 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.
main_review: Strengths:

1. 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. 
2. They justified their claims with experiments that demonstrate the benefits of the architecture on some small datasets.
3. They proved some expressivity theorems and bounded the size of the resulting gradients. 


Comments: 

1. 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.
2. 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).
3. 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.
4. 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. 

5. 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_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. 


UPDATE:

Thanks for the clarifications, I updated my correctness score and still vote to accept.
review_title: null

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)