Online learning of long-range dependencies

Summary

The paper looks at the problem of online learning in RNNs from a perspective of exact gradient computation: it looks for network architectures for which exact gradients can be computed. It uses the recently proposed LRU (Orvieto et. al., 2023) to show that with linear and diagonal structure in recurrent dependencies, one can tractably compute the exact gradients online for a single layer network. For multi-layer networks, this simplified structure combined with truncation of gradient signal (only considering current time step) results in an approximate gradient. The paper performs two sets of experiments. The first set examines the difference in the approximate gradient computed using the proposed method with the exact gradient. The second set of experiments focuses on learning tasks that require capturing long range dependencies. In both set of experiments the proposed method closes the gap to BPTT compared to the baselines used in the paper.

Strengths

### Originality The paper combines two known ideas, independent linear recurrent modules (LRU from Orvieto et. al., 2023) and gradient sparsification for online learning (Menick et. al., 2021), and presents them in new light. ### Quality 1. The paper is technically sound, has carefully designed experiments that support the claims well. 2. claims supported by theory and/or experiments ### Clarity 1. The paper is well organized and clear for most part. There are some parts that can be improved (see weaknesses). ### Significance 1. The well designed experiments make the results presented in the paper useful for the community.

Weaknesses

### Quality 1. Along with other claims that are well supported, the authors claim that they have pushed the standard for what is possible through online recurrent learning. However, I believe that the current experiments, which are limited to simple long range dependency tasks, are not sufficient for such a grand claim. Specifically, since all the experiments in the paper use synthetic data, it will be nice, for example, to include an experiment on real world data like small scale language modeling and compare the results to an LSTM language model, and discuss the limitations of the work in terms of performance on real world data that has complex dependency structure that is not simple long-range structure. Such an experiment will show the limitations of online learning and help guide further research on the topic. 2. Why does table 1 not contain sparse approximation method like SnAp-n applied to dense RNNs? ### Clarity Following are some mistakes/typos in the paper that can throw a reader off. 1. There is a mix-up in the symbols in equation 1, and line 103. I think $x_t$ should be replaced with $h_t$ in Eq 1, and line 103 should state that $u_t$ is the input at time $t$. 2. Line 109-111: I think you mean to say *absence of temporal non-linearity* in line 110. Following are some suggestions that could improve the paper: 1. While the authors provide through discussion for single-layer networks (Sec 3.1), the more important case of multi-layer networks does not get the same amount of care. The entire discussion in section 3.2 happens without the use of detailed expressions. Figure 1 does provide some support to the discussion but I find it to be insufficient. At the least, the authors should accompany the pictorial description in Fig 1 with expression for $\delta$ at each layer. This will help with the discussion of various points that come up in the experiment section 4.1 that centers around effect of dept. Specifically, an expression for $\delta$ at a lower layer it will help the point made in line 201-205, that is later discussed in section 4.1 around line 245.

Questions

### Typos and suggestions 1. Line 130: Using them for complex differentiation allows using calculus rules that are similar to those for real valued functions. 2. Line 167: "Those" as a vague reference here might cause confusion. It might be better to say $e^\lambda$ and $e^B$ explicitly.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Along with other claims that are well supported, the authors claim that they have pushed the standard for what is possible through online recurrent learning. However, I believe that the current experiments, which are limited to simple long range dependency tasks, are not sufficient for such a grand claim. Specifically, since all the experiments in the paper use synthetic data, it will be nice, for example, to include an experiment on real world data like small scale language modeling and compare the results to an LSTM language model, and discuss the limitations of the work in terms of performance on real world data that has complex dependency structure that is not simple long-range structure. Such an experiment will show the limitations of online learning and help guide further research on the topic.

Summary

The authors provide an online learning algorithm for linear recurrent units [23]. They take advantage of the fact that each unit of the LRU is an ‘independent recurrent module’ and thus RTRL for each LRU layer simplifies substantially in this case and becomes tractable. They test on some long-range dependency tasks.

Strengths

- The authors have combined insights from recent developments like LRUs being as good as RNNs while being easier to train, and approximations of RTRL for online local learning as in biology. - They demonstrate good results on some long-range dependency tasks as compared to RNNs.

Weaknesses

- The learning algorithm proposed seems to me just e-prop [13] applied to the LRU. Indeed, e-prop also takes into account self-recurrence of each unit and 1-step lateral recurrence. With LRU, since there is no lateral recurrence, e-prop becomes exact within one LRU layer. - Their algorithm still relies on spatial backprop between layers, so this is still not local in space. - The authors claim that “numerous biological implementations and alternatives for spatial backpropagation have been proposed [e.g., 50–59], while essentially none exist yet for backpropagation-through-time [60].”. But various approximations for BPTT have also been proposed like [13].

Questions

- The authors should study the relation with e-prop and inform if there are any differences with it. To me, their algorithm is the same. - In Fig. 3, I expect that BP is BPTT, and Spat. Is just the spatial BPTT without temporal dependencies? If not, was BPTT not used? Minor: - Mistakes in equation (1)! Cf. appendix A. I’ve classified this as minor, but it does not inspire confidence that the very first equation has many mistakes. - L304: inference -> inference

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A.

Summary

The authors show that applying an online learning algorithm to independent recurrent modules of linear recurrent units, drastically reduces the algorithm’s computational and memory requirements. They then show numerically that the algorithm’s gradient approximation for multi-layer networks is close to the “real gradient” (as provided by BPTT) and that the algorithm performs well across a range of tasks despite the approximation and using decoupled recurrent units.

Strengths

The authors take a promising path towards effective and efficient gradient-based online learning of recurrent neural networks: Instead of deriving a new approximation of BPTT or RTRL, they choose a network architecture that drastically reduces the computational and memory requirements when deriving online gradient updates for them. The paper provides a comprehensive overview and discusses relations and differences to previous work. The authors compare their proposed network architecture to other architectures and learning algorithms on the copy task. They further evaluate their architecture for three different learning algorithms on the sCIFAR and ListOps task. The paper is very well structured, written and accessible. The algorithm is derived in great detail, including a very helpful primer on complex differentiation, which is very helpful for understanding the research question, results and potential limitations. The figures are generally clear and accessible.

Weaknesses

- While I want to strongly emphasise that I think it is awesome that the authors flag that the SnAp-1 algorithm is reducing to the proposed algorithm when being applied to the proposed network architecture; this opens questions about the contributions made by the paper. In how far is the proposed algorithm new? How is it different from SnAp-1? Maybe a list of contributions at the beginning of the paper could bring clarity? I also would like to flag here that I am not familiar with SnAp-1. - The authors write that the “most remarkable result” is that their online learning algorithm significantly outperforms learning of networks with densely connected recurrent neurons on the copy task. Given that the copy task requires to memorise a sequence of patterns with i.i.d. sampled entries, is it really surprising that having no interference between hidden units is helpful? - To show that the decoupled network architecture is performing reliably and well and is a promising alternative to coupled RNNs, in my opinion a comparisons on the more complex tasks, i.e., sCIFAR and ListOps, are missing (i.e. like the data in figure 3) . Minor: - Two typos in equation 1 (formula for yt) - No description for panels A-D in caption of figure 2 - Maybe adding h-lines for 100% and 70% accuracies in figure 2?

Questions

- Where is the high variance of the proposed algorithm in the ListOps task coming from? - In order to make an online task out of sCIFAR, the authors provide the label at every timestep. How is target encoded / scaled over time? What is the influence on performance of providing the target at each time step? - In lines 61-62 the authors write “Finally, in Section 4, we analyse our algorithm and relevant baselines [...] with sequence lengths up to over 1000 steps” – what experiment is this referring to and how are 1000 steps required?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

A discussion of limitations of the work is missing.

Summary

The authors introduce a forward-only approach to gradient computation in linear recurrent layers. The approach yields exact gradients for a single layer and approximate gradients for multilayer networks. They show that their approach yields more accurate gradients and results in more successful learning than alternative approximations that enable forward-only gradient computation in recurrent layers, and they illustrate how their method is particularly adapted to the structure of linear recurrent layers. They show that their approach yields test performance similar to that of backpropagation through time for a multilayer LRU-based model on two tasks in the long-range arena (LRA) benchmark.

Strengths

The context, relevant background, and main contribution are presented clearly. The contribution itself is technically insightful and leverages a view specific to linear, complex-valued recurrent units. The topic of efficient learning in RNNs is well-motivated and contributes to a growing literature on linear recurrent parameterizations for sequence models. The experiments, particularly the illustrations on the copy task, are well-documented and show an insightful framing of both the performance advantages and the anticipated challenges of the proposed method.

Weaknesses

- While the illustration of the method on the method on the copy task is informative, the broader empirical evaluation is limited. Apart from the copy task results, the entire basis for the claim that the algorithmic contribution enables learning of long-range dependencies is a small set of results on a subset of the LRA benchmark. The authors do not disclose why only a subset of LRA is used. The results are difficult to contextualize as it’s not clear what values indicate successful learning of the long-range dependencies in the data. Other comparative evaluations, e.g. in terms of computational or memory costs, are absent. This contribution would be impactful even without state-of-the-art performance along any of these dimensions, but a lack of context is harder to overcome. - The paper relies heavily on the LRU of Orvieto et al. (2023) and appears to contain some overlap in content with that work (e.g. Fig 1 left is nearly identical to Fig 1 left in Orvieto et al.). At some points, for example $\S$4.2, the evaluation and analysis appears to be at least as much about the LRU itself as the algorithmic contribution of this submission. The authors could improve this work by more clearly delineating the present contribution from that of Orvieto et al. (2023). - The authors spend half of the discussion arguing for the potential importance of their work for neuroscience, which seems somewhat implausible and at odds with a relatively tight architectural and algorithmic focus up to that point (save for a brief aside on lines 170-171). The similarities in terms of locality, complex values, and modularity seem mostly superficial in light of the larger differences separating forward-only learning of LRUs from computational models of spiking neurons, to say nothing of actual, biological networks of neurons. If this analogy is important, it deserves more careful development in the main body of the paper.

Questions

- Can the authors clarify the evidence for learning of long-range dependence and offer some additional context in line with the first point above? Do *any* of the results in Table 1 suggest that the model has learned long-range dependencies? Can the authors share their reasons for limiting evaluation to a subset of the LRA benchmark? - What is the relevance of the two paragraphs spanning lines 270-287 with respect to the contribution of the present paper? They seem to be largely focused on an (important) detail for initialization of linear RNN weights. Could this finding be interpreted as evidence that the comparisons are performed suboptimally, and other initialization schemes should have been explored? - Typically, “online” learning refers to contexts in which data continuously streams from a source and low-cost updates are made in real time, after which an observation is not revisited. Do the experiments here follow this setup, or are multiple forward passes over the data required? If the latter, what is the advantage in practice of this method over BPTT?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

There is no direct potential for negative social impact. Potential limitations for the method and results are either discussed or covered above.

Summary

This paper introduces an online learning algorithm for recurrent neural networks, particularly targeting the learning of long-range dependencies. It builds upon the linear recurrent units and independent recurrent modules in multi-layer networks with complex-valued neural activities. The online update approach, originally proposed in the SnAp-1 algorithm for real values, is here extended to handle complex-valued neural activities the reduces the memory and computational requirements of training. As a result, this approach outperforms both spatial (online) backpropagation and prior approximate real-time recurrent learning approaches in copy task benchmark with sequence of 50 while having marginal improvement over spatial backpropagation for the long-range arena benchmarks.

Strengths

The proposed online learning algorithm effectively optimizes both single-layer and multi-layer recurrent neural network architectures. By transitioning from real-valued to complex-valued neural activities and employing a diagonal recurrent connectivity matrix, it maintains good performance on long-range temporal tasks and enhances online gradient estimation. It accomplishes exact online gradient computation within a single layer using only double the resources required for inference. In managing multi-layer linear recurrent units, proposed approach adeptly approximates backpropagated errors and augments hidden states, mitigating the memory-scaling issue inherent in real-time recurrent learning. Furthermore, it can be thought of a refinement to the SnAp-1 algorithm that can handle independent recurrent units online, offering robust theoretical guarantees despite the approximation used, and accurately computes gradients for all layers, thereby improving gradient alignment and boosting overall performance.

Weaknesses

* The proposed algorithm, while innovative, has some limitations acknowledged by the authors. Its approximation of the error variable, δ, can degrade over time, particularly when the neural activity values converge around 1, leading to a disregard of future error information. This approximation error is compounded when backpropagated through multiple layers, resulting in only partial error signal backpropagation. Hence, the algorithm's effectiveness can be reduced, particularly when managing complex dynamics across many layers. * The novelty of the algorithm is also somewhat constrained, as it builds upon existing concepts of Linear Recurrent Units (LRUs) and online Recurrent Neural Network (RNN) training methodologies, adapting the mechanisms of the SnAp-1 algorithm to handle complex-valued entities in independent recurrent units. * The proposed algorithm's performance, while impressive on tasks like the copy task, still lags significantly behind full backpropagation-through-time (BPTT) on longer sequence tasks such as the long-range arena benchmarks with a sequence length of 1000. * Finally, the methodology employed for hyperparameter selection — using the hyperparameters from BPTT as a basis — isn't practically applicable in an online learning scenario where BPTT won't be available.

Questions

* How would the hyperparameters be optimized for the online learning setting where BPTT results are not available? * There seems to be a significant drop in accuracy in LRA benchmarks compared to the BPTT. Does this mean that the proposed approach doesn’t scale well to larger sequences? If so, it would be good to discuss the typical sequence lengths that this approach would be ideal for.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

limitations of the works has been discussed briefly, but not the potential negative societal impact

read rebuttal

I have read the authors' rebuttal. They have accepted the issues pointed out by others and me and agree to elaborate on / clarify these issues. I maintain my rating of 6: weak accept. Minor point: Instead of feedback alignment (Lillicrap et al 2015) for local spatial backprop, look at Akrout et al 2019 and the earlier references therein -- far before ML discovered feedback alignment with some fanfare, computational neuroscientists were just learning the feedback weights to align correctly which works much better than feedback alignment!

Thank you for the thorough response

I thank the authors for their thorough response and for providing additional results. With the additional information, I now think that the paper can have significant impact, at least on RTRL community. I've increased my score by one point to reflect this.