Recurrent neural networks: vanishing and exploding gradients are not the end of the story

Summary

This paper studies the vanishing and exploding gradient phenomenon in RNNs. In particular, it answer the question: "is solving those issues really enough to ensure well-behaved loss landscapes?" This paper reveals the importance of the element-wise recurrence design pattern combined with careful parametrizations in mitigating the scale issue of hidden states.

Strengths

1. It is good to see people discuss the complex eigenvalue setting as previous work seems to be limited to real eigenvalues (such as HiPPO) 2. The teacher-student analysis is well-presented and clarifies the understanding of complex systems within this context.

Weaknesses

1. The assumption of inputs being wide-sense stationarity seems strong. Does it include the setting such as the Cifar10 dataset? 2. The argument of input normalization seems hand-waving. 1. When $\lambda \to 1$, the forward pass and backward pass are exploding with a different speed: Forward is asymptotically $1/(1-\lambda)$ while backward is (at least) asymptotically $1/(1-\lambda)^2$. 2. It should be proper to say normalization can relax one scale issue but it cannot achieve the scaling both at the same time. 3. The paragraph "On the Importance of Adaptive Learning Rates" addresses an essential topic but lacks direct training curves. 1. While the local Hessian analysis provided is valuable, it doesn’t assure improved global performance. 2. It would be more effective and indeed necessary to include training curves comparing results using SGD and adaptive learning rates (such as AdamW). This would clearly illustrate the advantages and need for adaptive optimizers. 4. Related works on parameterizations and orthogonal matrix is limited: 1. https://proceedings.mlr.press/v80/zhang18g.html 2. https://arxiv.org/abs/1909.09501: This work proposes a parameterised approach to train orthogonal matrix. 3. https://arxiv.org/abs/1901.08428 4. https://openreview.net/pdf?id=ryxepo0cFX 5. https://arxiv.org/abs/2311.14495: This work proposes the relationship between parameterization and gradient in RNNs/SSMs. 6. https://arxiv.org/pdf/2006.12070 5. I am willing to increase the score if the above issues are addressed.

Questions

1. On Page 4, Equation 5 focuses on the second-order expectation of $h_t$​. It would be helpful to understand the specific reason for choosing a second-order expectation over a first-order one. Generally, implementations do not involve the second moment of hidden states. Why is the first-order expectation not considered in this case? Does first-order suffer from the same problem? 1. A similar forward-pass blow-up has been proved in the LRU(Orvieto, 2023) paper, proposition 3.3. What is the difference in terms of assumption and technique between your result and the LRU result? 2. On Page 5, in the paragraph titled "What About Complex Numbers?", you discuss the concept of polar parametrization. This raises an important question: do all parametrizations encounter the same issues as the polar parametrization? If they do, demonstrating this could effectively highlight the limitations of using complex numbers in a polar setting. If not, it may be worthwhile to find the good parameterization. Currently, the exploration of polar parametrization seems quite restricted. 3. Your title is "vanishing and exploding gradients are not the end of the story". A question based on the saying in Page 9 Figure 5 Panel C is: 1. Does layer normalization and batch normalization resolves the all problems? 2. If not, I think it's hard to claim "Layer normalization keeps the overall gradient magnitude under control".

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

1. This paper investigates how the hidden states of recurrent models contribute to learning long-term memory. There is very little research available to explain why the mamba model, which uses both gating and state-space models, is successful. 1. The discussion on Gated RNNs in lines 205-220 lacks rigorous substantiation, relying primarily on speculative assertions to illustrate the impact of gating mechanisms. 2. The paper does not clearly establish whether the proposed methodology is effective within a gated framework.

Summary

In this work, the authors present an analysis of Recurrent Neural Networks (RNNs), focusing on problems which impede optimization as the length of input sequences and model memory increase. The authors first focus on the well-studied problem of vanishing/exploding gradients, arguing that this problem by itself does not explain the difficulties in optimization. The authors turn to the less studied "curse of memory", and argue that this issue persists for RNNs even when gradients are controlled to not explode or vanish. Finally, the authors study how some of the alternative recurrent architectures such as LSTMs and SSMs mitigate the curse of memory, and provide some suggestions for how optimization can be improved.

Strengths

I am very intrigued by the approach taken in this work. The analysis seems novel and the arguments provided are given in a straightforward and convincing manner. The theoretical and empirical results in the main body of the work all seem sound, and are augmented by substantial additional experiments in the appendices. The authors' analysis results in clear explanations both for how current architectures mitigate the issues studied in this work, and the analysis suggests some directions that may lead to new architectural innovations in the future. Despite many technical issues in the writing, the argument is presented in a clear way and the flow of the paper makes sense. See below.

Weaknesses

I have three major issues with the paper in its current form. If issue 1 is addressed, I am willing to increase the score of the presentation from fair to excellent, which would bring the paper to a borderline reject. Issues 2 and 3 are more relevant to the soundness of the work, and I've lowered the score to a 2. If the authors address these, I will consider raising the score; however, I can't go above a 3 without a more substantial discussion of limitations, which I think might not be feasible within the rebuttal period; however, I am still open to adjusting this score depending on the discussion. 1. One of the more glaring issues with this work is with the writing. The authors need to take some time to carefully check for typos, incomplete sentences, and correct grammar. I have listed a few particular issues here: * line 30: remains -> remain * line 69: You say here that you are showing the gradients can explode, but in the next section say you are controlling the gradients so that they do not explode (lines 83-86). Am I missing something conceptually here that makes this not an inconsistency? * line 70: remains -> remain * Figure 1: the last sentence of the caption is unclear and seems to be missing some words. * line 86: should be "studying this behavior quantitatively", not the other way around * line 192: alleviates -> alleviate * line 283: characteristic -> are characteristic if these issues are all fixed and the authors will take some time to carefully edit, I will update my score to reflect this effort. Overall the typos only affect clarity in a few spots. 2. In section 2.2 - you justify assumptions A) and B), but I couldn't find any justification of assumption C). Unless I am missing something, this needs to be provided, as assuming Wide-sense stationarity is not necessarily standard. At the very least, this assumption could be acknowledged as a limitation and room for future work. 3. There is no real discussion section at all, and there is particularly no discussion of limitations.

Questions

See above - why is the assumption of Wide sense stationarity needed, and how is your analysis affected by not adopting the assumption?

Rating

5

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

No limitations are presented or discussed in the paper as far as I could find. I see no ethical issues with this work.

Summary

The paper explores challenges RNNs face in learning long-term dependencies. While generally attributed to the exploding and vanishing gradients problem (EVGP), the authors reveal that as a network's memory increases, parameter changes cause an explosion of the second moment of hidden states and their gradients, making gradient-based learning highly ill-posed. They study different design choices in recurrent architectures such as element-wise recurrence, gating mechanisms and careful parameterization with respect to the curse of memory. They apply their theoretical findings to successful architectures such as state-space models (SSMs) and LSTMs, offering new insights into why some RNN architectures perform better in gradient-based learning.

Strengths

- The paper addresses a fundamental problem, the curse of memory, and connects it through theoretical analysis and experimental validation to the success of recent architectures, which makes the insights incredibly valuable to the machine learning community - I like how the authors connect the dots between multiple facets of model training, e.g. investigating the implications of RNN recurrence parametrization on adaptive LR optimizers, which are actually used in practice - The paper is also well structured and generally well written.

Weaknesses

- To add to EVGP mitigation techniques (l. 61 - 64): There also exist regularization techniques based on dynamical systems theory, see especially [1] - There are quite some typos across the document, see the list below. I recommend running the paper through some sort of language checker to improve the manuscript from a readability and presentation side. - The authors repeatedly call $\mathbb{E}[X^2]$ a variance (where $X$ here is a placeholder for any RV, i.e. $h_t$ and $d_\theta h_t$ in the paper), which is technically not correct. It is the second moment. I’d consider fixing this or explaining why the missing term for the variance, $\mathbb{E}[X]^2$ (first moment squared), can be neglected. Typos / text-bugs: - l. 119: “[...] a low a pass filtered [...] - l. 191: “[...] does not hurts [...]” - l. 192 “Several RNN architectures implicitly alleviates [...]” - l. 200 “While such models can can approximate any smooth mappings [...]” - l. 219 “anaylsis” - l. 257 “Both network are trained [...]” - word missing in l. 283 “[...] that characteristic of the curse of memory, [...]”? - l. 298 consistently -> consistent [1] Schmidt et al., Identifying nonlinear dynamical systems with multiple time scales and long-range dependencies (ICML 2021)

Questions

- in l. 180 you assume $\gamma$ is independent of $\lambda$ yet in the Diff. eq. in l. 182 you introduce the dependency again ($\gamma(\lambda)$)? Is this connected to what you write in the caption of Fig. 2 where you decouple $\gamma$ from $\lambda$ when differentiating? Can you explain the reason for this in more detail? - in l. 289 you mention that you probe ADAM’s effective learning rate by providing a vector of ones to the optimizer - does that mean you simply read out ADAM’s (corrected) second-moment estimates and report $\frac{\eta}{\sqrt{v_n} + \epsilon}$, where $\eta$ is the global learning rate and $v_n$ the second moment estimates at iteration $n$? If so, at which iteration/epoch do you query the effective learning rate?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

While an explicit section on limitations is missing, the authors mention their limitations and specific assumptions throughout the manuscript.

Summary

The paper discusses "the curse of memory" which is the hypersensitivity of hidden states to parameters as the memory increases. This can lead to optimization issues, even if the exploding/vanishing gradient issue is addressed. The authors discuss solutions to this problem: complex diagonalization, normalization, and reparametrization. To this end, the authors derive closed-form solutions for the variance of the hidden state and its sensitivity to the parameters and discuss how the solutions can prevent the variances from diverging. This can give insights into why certain families of RNNs are performant. In particular, they show that both the variance of the hidden state and its derivative wrt to the parameters diverges as the memory goes to infinity (although at different rates). Therefore, normalizing the hidden state and reparametrizing the variable representing the memory's temporal scale can avoid the divergence issue.

Strengths

- The paper puts forward closed-form solutions for the variance of hidden state and the sensitivity of hidden state to parameters. This is interesting and can provide insights into RNN dynamics and possibly network design. - The results and the discussion on adaptive learning rate and how it relates to the Hessian of fully connected and complex diagonal RNNs are interesting and, to my knowledge, novel.

Weaknesses

- The main weakness of the paper is the presentation. It is unclear what the contribution of papers is. At many points in the manuscript, it is unclear if the authors are discussing previous results on LRUs or putting forward new results. It would be good if the authors explicitly spell out their contributions. - Although the paper is presented as discussing the curse of memory and the solutions to it, it reads more like "why LRUs are performant" The solution discussed: exponential reparametrization, normalization, and diagonalization, are all introduced and employed in LRU architecture [20]. However, the authors only discuss SSMs and gated RNNs as networks that implicitly address "the curse of memory". Meanwhile, LRUs employ the same solution discussed in the paper explicitly. Although LRUs can be thought of as a subclass of SSMs, vanilla SSMs [17] do not use the normalization, diagonalization, and exponential reparametrization discussed in the paper. Therefore, discussing LRUs only in experiments "to represent SSMs due to its simplicity" is not justified. - If the solution to the curse of memory is not the contribution of the paper, then the novelty and contribution become limited. As I mentioned earlier, LRUs employ the same solution and sometimes with the same justification, for example, exponential parametrization is used for higher granularity around 1 [20]. - To motivate their results, the authors mention that "We answer negatively by showing that gradients can explode as the memory of the network increases, even when the dynamics of the network remains stable." but it is unclear where this is shown. - minor comments: L117: the paragraph on backward pass is confusing and hard to understand. L139: check wording. Could not understand it.

Questions

- What are the main contributions of the paper? Which results and which sections? - What are other types of normalization and reparametrization, other than the ones employed by LRUs, that can address the curse of memory?

Rating

4

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

NA

Summary

The paper provides a theoretical and practical analysis on the difficulties of training recurrent neural networks. In particular, given the current rise of interest in leveraging recurrent mechanisms for long sequence processing -- due to novel architectural components and solutions (deep state-space models, linear/diagonal recurrences, exponential parametrizations), identifying the crucial components allowing to preserve long range information is a very important research avenue.

Strengths

The paper provides an interesting theoretical analysis that highlights which are the key components allowing modern solutions (Deep SSMs) and gated models (LSTMs/GRU) to achieve good performances. Moreover, it provides some proof-of-concept practical results that help to confirm the analysis. The paper is well written (apart from few typos, I suggest a proofreading).

Weaknesses

I have some concerns with some of the paper initial framing and setting (see the Questions section) and the experimental analysis, which has been carried on very synthetic tasks which I am not sure are capable to represent real learning scenarios, thus possibly hindering the analysis validity.

Questions

1) (Minor) While I understand that recent literature has completely overriden this notion, the term "state-space model" refers [1,2,3] to a very general broad concept which is common in control theory and dynamical systems -- which simply refers to a model equipped with state variables controlled by first-order differential equations or difference equations. Such definition covers the typical feedback connection of Recurrent Models. Thus, stating in the abstract and in the main text "state-space models, a subclass of RNNs" seem a bit too strong to me -- even if several recent works highlighted the connections. I would be completely fine with specifying "Deep" SSMs (just to highlight that the authors are referring to modern models) or "Structured" SSMs and to mention the suggested references, to better frame the paper to the readers. 2) In Eq. 1, the authors consider a model not equipped with an output mapping (that was instead considered in Eq. 10, i.e. y_t = Ch_t + Dx_t) -- the hidden state h_t is directly provided to the loss function. Why is that the case, and do the considered analysis still hold when considering such mapping (that is common in RNNs and SSMs)? 3) The authors refers to an Infinite time horizon/infinite sequences (lines 98/100) as the basis for their analysis. Practically, how long the learning process necessitates to be to the considered issue to emerge/is this something that also the experimental analysis considers? In such case, does this have relation with recent literature highlighting the difficulties of sequential models when dealing with Infinite length sequences [3, 4]? I would like a comment by the authors on this. 4) Line (40): the notation (x_t)_t is not very clear to me. 5) Could the authors give an intuition on lines (113/116)? Why an higher correlation in the input data should imply an higher variance in the model state (in my understanding, similar inputs imply similar loss function, thus smaller gradients) 6) In line 135, the authors use yet another form for the state update that do not consider the B linear mapping. Why is that the case? 7) The teacher-student task should be better described and justified. Why did the authors chose to tackle such task instead of other synthetic tasks (such as selective copy, induction heads etc. see recent surveys [3] for references on synthetic datasets ). And do the authors believe that the teacher-student task is general enough (i.e., points sampled from a normal distribution) to represent a setting where the state has to learn meaningful long range dependencies? Do the conclusions still hold when dealing with tasks requiring to store more informative data? I believe that experiments could benefit from experimentations on more "difficult" settings (selective copy, Long Range Arena) to confirm the theoretical considerations with real learning scenarios. [1] Genshiro Kitagawa. A self-organizing state-space model. Journal of the American Statistical Association, pages 1203–1215, 1998. 4 [2] Anton Schafer and Hans Georg Zimmermann. Recurrent neural networks are universal approximators. In Proceedings of ICANN, pages 632–640. Springer, 2006. [3] Tiezzi, Matteo, et al. "State-Space Modeling in Long Sequence Processing: A Survey on Recurrence in the Transformer Era." arXiv preprint arXiv:2406.09062 (2024). [4] Tiezzi, Matteo, et al. "On the resurgence of recurrent models for long sequences: Survey and research opportunities in the transformer era." arXiv preprint arXiv:2402.08132 (2024).

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper does not discuss limitations.

Re: Rebuttal

I thank the authors for the clarifications, elaborate rebuttal and additional experiments in the general response. I think this work is of great value for the community. Hence, I increased my score to 7.