Online learning of long-range dependencies
Authors: Nicolas Zucchet
Robert Meier
Simon Schug
Asier Mujika
Joao Sacramento
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
linear recurrent units
temporal credit assignment
biologically-plausible learning
local learning rules
neuromorphic computing
TL;DR: Independent recurrent units enable tractable online learning of long-range dependencies

Abstract: Online learning holds the promise of enabling efficient long-term credit assignment in recurrent neural networks. However, current algorithms fall short of offline backpropagation by either not being scalable or failing to learn long-range dependencies. Here we present a high-performance online learning algorithm that merely doubles the memory and computational requirements of a single inference pass. We achieve this by leveraging independent recurrent modules in multi-layer networks, an architectural motif that has recently been shown to be particularly powerful. Experiments on synthetic memory problems and on the challenging long-range arena benchmark suite reveal that our algorithm performs competitively, establishing a new standard for what can be achieved through online learning. This ability to learn long-range dependencies offers a new perspective on learning in the brain and opens a promising avenue in neuromorphic computing.

Online learning of long-range dependencies
Nicolas Zucchet', Robert Meier", Mimen Schug" Asier Mujika, João Sacramento
Department of Computer Science, ETH Zürich (nzucchet www.eeeeeescaioeeoeeeeeeee sschug, asierm, oao 0ethz. ch
Abstract
Online learning holds the promise of enabling efficient long-term credit assignment in recurrent neural networks. However, current algorithms fall short of offline backpropagation by either not being scalable failing to learn long-range de- pendencies. Here we present high-performance online learning algorithm that merely doubles the memory and computational requirements of a single inference pass. We achieve this by leveraging independent recurrent modules multi-layer networks, architectural motif that has recently been shown be particularly powerful. Experiments on synthetic memory problems and on the challenging long-range arena benchmark suite reveal that algorithm performs competitively, establishing a new standard for what can be achieved through online learning. This ability to learn long-range dependencies offers perspective learning in the brain and opens a promising avenue in neuromorphic computing.
Introduction
How can the connections between neurons in a neural network be adjusted to improve behavior? This question, known as the credit assignment problem, is central in both neuroscience [1] and machine learning [2], owing to its fundamental importance for elucidating learning mechanisms in the brain and constructing intelligent artificial systems. However, the complex and nonlinear nature of neural network processing makes the precise allocation of credit an intricate task.
Deep learning provides a compelling solution to the credit assignment problem via gradient descent, which refines network parameters along the locally most promising direction. For networks processing temporal sequences, gradient computation made possible by backpropagation-theee throughh-ttouu-iiii [BPTT; 2-4]. BPTT stores and revisits neural activity in reverse- reverse-time order to understand how infinitesimal changes neural activity, and thus network parameters, would have impacted the objective function. One important drawback of this algorithm is its requirement to store the entire activity trajectory memory, which constrains the sequence length for exact gradient computation, impairing the learning of long-term interactions. This constraint becomes a critical bottleneck when working within memory-limine limited systems, such as neuromorphic hardware [5] and presumably the brain [6].
Alternatives to BPTT for gradient computation do exist. One such approach, forward mode differen- tiation [7. 8], involves computing gradients online the input sequence is processed, by keeping track of the sensitivity of neural activity with respect to each of the network parameters. This marks qualitative departure from BPTT, as it prepares for all potential future trajectories simultancously; by contrast, BPTT focuses on improving the activity of a past trajectory. Importantly, the memory footprint this approach does not depend on sequence length. Still, it remains intractable for real-world applications and likely infeasible in the brain due to its cubic memory scaling and quartic computational complexity in the number of neurons. Recent research focused on approximation
'Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

strategies to make online gradient estimation more tractable for general- purpose recurrent networks [9-18]. Our work takes fundamentally different approach: instead of tailoring the learning algorithm to the neural network architecture, we fix the learning algorithm and seek an architecture that makes tractable.
We build upon recent advances in linear state space models, a class of recurrent neural networks (RNNs) employing linear recurrent blocks [19-23]. These blocks are stacked and interconnected through nonlinear networks. The key insights from this line of research are that linear recurrent connections simplify temporal credit assignment and enable parallel temporal processing, while nonlincarities between recurrent blocks ensure that network expressiveness remains comparable to that of densely- censely-connected nonlinear RNNs. Much, if not all, of the state-of oftte--f--hearrr performance of those models on long-range temporal tasks [24] can be maintained by transitioning from real-valued to complex-va -valued neural activities [21-23], and restricting the recurrent connectivity matrix to be diagonal. Recurrent neurons within given layer are now independent of each other. This greatly improves the tractability of online gradient estimation, as the recurrent parameters of a given neuron do not impact other neurons. We leverage this property to achieve exact online gradient computation within a single layer with as little as twice the memory and compute requirements needed for inference. Further, we demonstrate how this leads to improved gradient estimation compared to existing online learning algorithms when recurrent layers are stacked.
This paper is organized as follows. We start by briefly reviewing existing gradient- gradient-based online learning methods in Section 2.1. Next, we introduce the concept of independent recurrent modules, showing how some of the recent high-performance models mentioned above fit in this framework in Section 2.2. Deriving our learning rule requires complex differentiation; we give a concise overview of those tools in Section 2.3. In Section 3, we detail our online learning algorithm that combines exact differentiation within a layer of recurrent independent modules with spatial backpropagation across layers. Finally, in Section 4, we analyze our algorithm and relevant baselines on a synthetic copy task and show that it can learn sequential tasks with sequence lengths up to over 4000 steps.
2 Background
2.1 Online gradient-based RNN learning
We study gradient- learning of recurrent neural networks, which process input data T1...... IT sequentially while maintaining an internal (hidden) state hy. The objective of learning is minimize a cumulative loss T.(0)= = > (0) which measures performance on a task at hand as a function of network parameters 0. The standard algorithm for computing the gradient V (() is the offline method, which requires storing the entire input I1:7. loss LIET and internal activity h1r7 sequences, and then revisiting them proceeding backwards in time. Here, we focus on online algorithms which carry the information needed to compute or estimate (() forward in time. This enables simultaneous processing of inputs and learning for RNNs, without storing past data and network states. In principle, online algorithms can learn arbitrarily long temporal dependencies as well as scamlessly handle sequences of arbitrary length T.
cockpropggaiion-thougg--tte
The classical alternative to BPTT for forward-in in-tmm----ieeeeeee gradient computation known as real-time recurrent learning [KTRL.; 7] in the context of RNNS a method which has its roots in control theory [26]. While RTRL enables online updating it as the RNN processes its inputs. The size of this auxiliary variable is O(r²), where n = ||] is the number of hidden units in the RNN. For comparison, the memory requirements of BPTT are O(nT). In practice, this precludes the usage of RTRL for all but the smallest of models.
cuddient-based learning, requires storing doh; in memory and
There has been much effort in developing memory efficiinn alternatives RTRL. We now briefly discuss these prior efforts while referring to a recent review by Marschall et al. [14] for a more detailed treatment. We divide prior work into three broad categories. One class of algorithms relies on neglecting terms in dgh, to reduce its size, thereby creating biased gradient estimator. Typically this requires introducing crude approximations, which allow going from O(n²) to a tractable (nn) size. Despite such approximations, in many cases, performance still holds in non-trivial tasks [13, 15, 16]. At the end of this spectrum sits instantancous (spatial) backpropagation, which neglects all temporal
2 Moor generally. BPTT can be seen as special case of reverse mode automatic differentiation, and RTRL of forward- mode automatic differentiation [25], applied to the problem of RNN learning.
2

---

dependencies in the hidden state when approximating the gradient. A second class of algorithms relies on stochastic estimation; this allows retaining unbiased gradient estimates, the expense of introducing variance [9-11, 17, 18). Finally, a third class of methods introduces gradient models [critics; 27-29] to produce gradient estimates online. The crities themselves are then either trained separately offline, making such methods hybrid on/offline; or fully online, using temporal difference techniques [30]. We note that despite their widespread use in reinforcement learning, it is not yet well understood whether temporal difference methods can reliably and efficiently improve the performance of a gradient critic on real-world RNN learning problems.
As noted by Irie et al. [31], the RTRL literature mostly focuses on single-layer recurrent networks and remains scarce for deeper networks. Recently. Javed al. [32] developed a greedy learning algorithm where a growing network is progressively frozen and trained one layer at time. Existing approximations such as [13, 15] do not prescribe how learn the parameters of remote layers, and the multi-layer case is not considered in the respective papers. Introducing a powerful RTRL algorithm that scales to networks of multiple layers is the main algorithmic contribution of this paper. This property is of great empirical relevance given the power of depth to learn the temporal structure [e.g. 19, 23].
2.2 Linear recurrent units and independent recurrent modules
Instead of developing approximate, general-purpose forward-mode differentiation methods, our goal shifts towards seeking an expressive architecture allowing exact, tractable online gradient calculation. We propose that networks with linear recurrent units [LRU; 23] and, more generally networks with independent recurrent modules, are particularly well-suited for this purpose.
A linear recurrent unit, depicted in Figure 1, is defined as
h4 G h4 Brs+1, y/ = Re(Ch,,] + Da.,
with @ the element-wise product. Here, 24 E H represents the input received by the LRU time t, h4 E CC denotes its internal state, and yt E R its output. The parameters of the unit include E CN B NN C E " and D E R The version of the LRU we use in our experiments includes an element-wise normalization factor for the input Br and uses an exponential parametrization of for network stability. We omit these details in the main text for conciseness; see Appendix A.1 for more details.
LRUs differ from traditional recurrent layers in deep learning: they have linear neural dynamics, a complex-valus valued state füg, and a diagonal connectivity pattern. Orvieto et al. [23] found that the absence of temporal linearity in networks that stack those units through nonlinear connections (see Fig. 1) does not alter expressivity and eases gradient-basee learning, notoriously difficult process for nonlinear RNNs [33, 34]. In addition, the diagonal structure of the recurrence matrix provides several benefits over fully connected ones. First, it affords an easy way to control the eigenvalues of the Jacobian of the system and thus ensure that neural dynamics remain stable. Due to the linearity, also enables processing the input sequence in parallel [35], significantly accelerating the training of such models on modern computers [22]. Importantly, despite its diagonal parametrization, the LRU remains functionally equivalent to a linear recurrent layer with dense recurrence matrix A, as A can be approximated as accurately as needed by complex-diagonaliian diagonalizzable matrix.
Each complex neuron in an LRU is an independent recurrent module, meaning its current state does impact the dynamics of other modules. This property greatly simplifies online credit assignment (see Section 3). We focus on this specific architecture due to its simplicity and great empirical performance, but our theoretical insights also apply to networks of independent recurrent modules with oow-dimensional state vectors per module.
2.3 A primer on complex differentiation
The use of complex-valus -vauud networks, such as the LRU, and hence complex differentiation remains relatively scarce. In the following, we provide a concise review of the tools of complex differentiation integral to the derivation of our online learning rule. We use ʃ and g to denote complex-valee functions that take the complex variable input.
3

---

Example IRM: the Inear recurrent untt (LRU)
spatial processing
neural activiies
backpropagated emors
D
temporal processing
netural activiies
state sensitvities
D
H
J!
Independent module
B,,,,,CCEC
Ax-1
het1 A he B Re(Chu) + DEc
skip conmection
T
bLa
C1-11-1
ot-li
6t-1-
Inno wrookA
GLU
Ineut NUCAA
11-1
h2-1441
layers
time
time C
Figure 1: (Left) Overview of the class of neural networks we consider in this paper. We stack layers of independent recurrent modules (IRMs), augmented with layer norm [36] and gated linear units [GLU; 37J. Light red indicates instantaneous spatial processing, dark red temporal processing. When examine networks with fully connected recurrent layers, only the dark red block is modified. The linear recurrent unit is the instantiation a layer IRMs we use in our experiments. (Right) Overview of our learning rule. As input sequence is processed, hidden states h, and their sensitivities 6, to the parameters are updated. Learning ensues by combining the sensitivities e, with spatially backpropagated error signals. No information flows in reverse time; our rule is fully online.
The Wirtinger derivatives of are defined through df dRe(z] alm
df df
df 1/ df
df
dz
dz 2dRof
dlm[2]
Using them for complex differentiation allows using similar calculus rules as for real functions. Note that the row convention for derivatives, that is dzf is vector of size |=]. The following formula holds in general f f.
The complex derivative of complex function is similar to a 2 2 real-valued matrix as both d, E C and f E C are necessary to characterize it. Yet, there exists subclass of functions, called holomorphic functions for which it can be reduced to a dimensional realevalued vector, leading to a compact representation of derivatives. A continuous function f is holomorphic if it satisfies the Cauchy-Riemann Riemann equations
dRe[/] dlm[s] and dRe[S] dlm[/]
i.e. df as=0.
dRc[2] dlm(z> dIm[2]
dResz]]
dz
Any affine function, well as the composition of two holomorphic functions, themselves holomorphic.
The chain rule of complex differentiation, crucial for automatic differentiation, is
d(f o g) df dg + dg da dz dg dz
df dg
(4)
When either f or g is holomorphie, the second term vanishes dzf 0 or = is a real-valued function, it can be optimized through gradient descent by iteratively updating its input variable through A= -dRe idmm -212/
= 0. When
3 Online learning of networks of independent recurrent modules
Based on the foundations laid down preceding section we now derive our online gradient- based learning algorithm for multi-layer networks of independent recurrent modules. We first focus single layer, demonstrating that exact forward-mode differentiation is tractable. This insight then guides the derivation of our rule for multi-layer networks.

---

3.1 Single-layer networks
We focus on parameters that influence the hidden states; computing the gradient of any other parameter does not require temporal credit assignment. For the LRU, we have 0 = {), B}. Recall that L(0) Σi= L2 (v)( denotes the loss function that measures how good the outputs yı.r of a network parametrized by 0 are. Its derivative dg (() can be calculated using forward-mode (complex) differentiation:
dL d0
Σ
T
aL dhe aL dh, The db dh, de
T Σ
aL, dhg Th, d0
As mentioned in Section 2.3, the last equality holds as h4+1 is holomorphic function of h, and of hence h, is a holomorphic function of 0 by recursive composition, and L only directly depends on he through L. The term ó, := db, L that is here equal to ds, Ly can easily be computed by spatial backpropagation, as the output 3/2 at time ( only depends on the current hidden state 1tg We are left with computing the sensitivities dgh,, of the states to the parameters.
Independent recurrent modules do not influence each other. The parameters 9 that directly influence the state h4. of module never impact the state he' of another module. As a consequence, the number of non-zero entries of the sensitivity doh, grows linearly with the size of & whenever the number of recurrent neurons within each module is fixed. Applying this to the LRU, dgh; is entirely characterized by e² := (dx, hr,)); and e, == he. Differentiating Equation using the product rule gives the corresponding updates:
e = o e he,
B e = diag())ee + 1x
(6)
with a vector of size |h| filled with ones. More detail on the derivation of Equation 6 and on how to efficiently simulate this update given in Appendix A.2. Keeping track of those quantities only requires considering an additional hidden state of size 10].3 Finally, the and B updates can be obtained by following the gradient, calculated in Equation
T AA Σ
8, O
A Σ diag(6,)ef.
Interestingly, all the e-updates are local to the neuron synapse in question, and no approximations were required to accomplish this. This feature makes the algorithm particularly promising for neuroscience and neuromorphic engineering, where localized computation is highly desirable. The parameter update for À and is also fully local, as combines a parameter-speciffc sensitivity, sometimes considered as an eligibility trace [13], and postsynaptic error term.
The idea that element-wise recurrence simplifies RTRL precedes our work. can be found in early work by Mozer [38] and Gori et al. [39], and has been revisited recently [32, 31]. In this paper, we extend this insight to complex numbers and thus do not lose expressivity, unlike previous work. We also note that some approximations to RTRL such e-prop [13] SnAp-1 [15] end up being exact when applied to networks with independent recurrent modules.
3.2 Multi-layer networks
The derivation in the last section presumes that the loss L only directly depends he through L This assumption no longer holds when layers are stacked, which is crucial to the expressiveness of the model. In the following, we explain how consider layer of the network where we aim to compute the gradient of the loss with respect to its parameters 0'_ The sensitivity dg can be computed before, assuming independent recurrent modules, as 0' does not influence the behavior of the inputs it receives from previous layers. Hence, we are left with computing 5, = dx L The simplification 5f = dyy L, we made in the previous section still holds for the last layer but is violated for the other layers. This is because L, taken as function of the hidden states h' of layer i, now has internal memory through the subsequent recurrent layers. The hidden state hy at time will thus directly affect all future losses Le for 2 t.
extend our rule the multilayer case. Let us
If he is not holomorphic function of 6, one would need to keep 2/0) instead of [0] states.
5

---

As consequence, one has to resort to buckpropagation-ttruuge -ime to compute du L exactly, which breaks causality and rules out the possibility of learning online. To circumvent this issue, we approximate the error signal each layer receives by 6 & dyy L so that it can be computed instantaneously with spatial backpropagation. We emphasize that the only source of approximation of this algorithm is the one above. Given that there is no approximation for the last layer, we will always compute the exact gradient for that layer.
We summarize our learning rule in Figure 1. It prescribes augmenting the hidden state of each recurrent layer with the sensitivity e'. For each input/output sample (Zz, V/ larget), we first update the full entire hidden state (h4, ee) using the previous one (h4-1, ct-1) and current input Pt. We then spatially backpropagate the error signal obtained at the last layer by comparing the prediction of the network to its desired value y/ target. Finally. we combine eş and 6f available at each layer using Equation 7 to compute the current update. So far, we have only described how to update parameters that directly influence the hidden neurons of the recurrent layer. We update the rest of the parameters with the gradient estimate obtained with spatial backpropagation. Importantly, the size of the extended hidden state is upper bounded by the number of neurons plus the number of parameters and is in practice much smaller.
Next, we aim to understand the factors that may degrade the quality of the gradient estimate as a result of the approximation 8/ s da, L, which introduces bias in the gradient estimate. In the LRU, neural activities, and thus error signals, are processed temporally through dynamics similar to the one of Equation 1. When the norm of each X₁ approaches one, neural activity preserves past information, and correspondingly, error signals backpropagated over time contain more information about the future. This suggests that our approximation becomes less accurate the distribution of \y narrows around 1, since it discards future error information. Moreover, 5 worsens as it is backpropagated through more layers. At each layer, backpropagation mixes errors from the next layer and the future state of the layer. Since we neglect future information, only part of the error signal is backpropagated. resulting in less accurate approximation. We delve deeper into these two approximation sources in a memory task in Section 4.1.
4 Experiments
In the following, we analyze the properties of our proposed online learning method empirically and explore how independent recurrent modules aid learning of long-range dependencies. To this end, we first conduct an extensive analysis on the copy task [40], a well-cstablished test bed to study temporal credit assignment in recurrent neural networks. Comparisons to truncated online versions of BPTT and to an extension of SnAp-1 1 to deep recurrent networks, reveal that independent recurrent modules generally beneficial for learning long-range dependencies, as they excel in both the online and the offline setting. Finally, we evaluate our method on three tasks of the Long Range Arena [24]: sequential version of CIFAR [41], LISTÖPS [42] and IMDB [43], scaling online learning to sequence lengths of over 4000 time steps and to deep recurrent neural networks. For additional experimental details and hyperparameter configurations, refer Appendix B.
4.1 Understanding the approximations behind online learning in networks of LRUs
In this first series of experiments, in detail. We recall that our learning rule only approximates the full gradient when the network has two recurrent layers or more, as it ignores the temporal component of backpropagated error signals. Therefore, we expect that the learning signal becomes less accurate as we increase network depth and shift the eigenvalue distribution towards norm of 1. To explore the effects of our approximation in a controlled setting, we consider a copy task [40, 10, 15, 18] in which the network observes a length- 20 sequence of 7-bit patterns that must recall when presented with an output token. Intuitively, temporal credit assignment is critical in this task to, among other things, convert forgetting neurons (A) < 1) into perfect memory units (A) RJ 1) that can solve the task. To ensure that these perfect memory units are scarce at the beginning of training, necessitating learning to create some, we initialize À uniformly at random in the complex unit disk and set the number of recurrent units per layer to N = 64. The default architecture used in this section has four layers.
investigate the approximation introduced by our online algorithm

---

A
Cos similarity [#: std)
layers:
- 2--3- 3
Mimai 0.0
0.75
Trunc. Ours BP
1.00
1.00
0.98
0.98
0.75
0.96
0.50
0.96
0.94
0.25
0.94
25
B
Training loss std)
layers:
Mmmai 0.0
0.75 0.9
Spat Trunc. Ours BP
10a
10
109
10-1
10-1
10-2
10
10
10-3
10
25
10
25
5
20
Epoch
Epoch
Epoch
Figure 2: Impact of depth of the network (left), eigenvalues of the network (middle), and type of approximation on the quality of online learning (right). The cosine similarity measures the alignment between the estimated gradient (with our learning rule for all panels, and with spatial backpropagation (Spat.) and 1-step truncated backpropagation (Trunc.) for panels E and F) and the true gradient, computed with across layers to make a quantitative comparison possible. The encoder and decoder alignments do not influence this metric. This task is solved (100% accuracy) for losses lower than 0.05 and 70% accuracy roughly corresponds to a loss of 0.5. See Section 4.1 for more details.
(BP). It is computed per layer and then averaged
As remarked in Section 3.2, the updates prescribed by our learning rule match the gradient exactly for all parameters in the last LRU layer. We confirm that empirically for network of one layer in Figure 2.A. While the approximation quality deteriorates with increasing depth (Fig. 2.A), alignment remains high, noticeably better than for all baseline online learning rules (Fig. 2.E). Moreover, despite alignment decreasing with depth, performance enhances significantly (Fig. 2.B). BPTT exhibits similar improvements with depth, suggesting that this is likely due to the enhanced capabilities of the model. Our rule can learn useful hierarchical temporal representations online whereas baseline methods, 1-step truncated and spatial backpropagation, which ignore most of temporal dependencies, fail (c.f. Fig. 2.F). Additionally, we found that, despite its bias, our learning rule can decrease the loss to when training 4 layers network a simpler memory task for long enough.
Exact error terms are backpropagated through recurrent units by weighting the current prediction error by 1 and the future error by A. In order maintain an online algorithm, we ignore this dependency on the future. We expect aligmment with the gradient to decrease as the distribution of | shifts towards 1. To test that, we initialize the À uniformly random in the complex ring of radius [[M] Imin 1]. Interestingly, alterations in the initial eigenvalue distribution only slightly affect estimation quality in the beginning of training (Fig. 2.C). The key factor seems to be the degradation associated with learning progress, rather than degradation due to larger cigenvalues. Smaller initial [X]min values slow down training, more perfect memory neurons have to be recruited, but all initializations eventually lead to solving the task (Fig. 2.D).
4.2 Independent recurrent modules improve online learning performance
After dissecting the learning dynamics of our algorithm, we next show the importance of the independence of recurrent modules for online gradient-basee based learning. To this end, we compare linear recurrent units to densely-connectee linear recurrent layers which do not have independent recurrent modules. To make the comparison fair, we ensure all models have the same number of parameters and recurrent neurons. In addition to the baselines we considered in the previous section, we include an extended version of the SnAp-1 algorithm that combines spatially backpropagated errors with the SnAp-1 sensitivity approximation. This algorithm reduces to ours when applied to networks of independent recurrent modules. Therefore, it enables us to isolate the impact of the independent recurrent module design on online gradient-based learning. We report final training losses in Table and refer the reader to Appendix B for experimental details.
7

---

Table 1: Comparison of final training losses of different online learning algorithms on the copy task of Section 4.2. The independent recurrent modules design improves online learning performance. Performance greatly degrades when the LRU replaced with dense recurrent matrix (Linear RNN). Comparison with the SnAp-1 1 algorithm applied to the GRU architecture highlights that online learning of multilayer networks difficult without element- recurrence. Results are averaged
over 5 seeds.
Layer
LRU 4
Linear RNN
GRU 1
GRU 4
Number layers
SPATIAL
4.66 x 10-1
6.20 x 10-1
6.26
10-1
6.55 10
TRUNCATED
2.62 x 10-1
5.81 x 10-1
6.20
10-1
6.49 10
OURS / SNAP-1
8.44 x 10-3
5.82 x 10-1
3.16 x
10-1
3.27 x 10
BPTT
7.59 x 10-6
1.07 x 10-4 2.61 10-1
1.94 10-1
Table 2: Test accuracy on three tasks of the LRA benehmark [24] for spatial backpropagation, 1-step truncated backpropagation, our algorithm, and full backpropagation through-time. While we always use per time step local losses during training, accumulate logits over the sequence during inference. We report the mean and std. for three seeds each.
Table 3: Test accuracy of a lin- ear RNN on the CIFAR task. In- stead of our learning rule, we ap- ply the SnAp- I learning rule ex- tended to the multilayer case, as described in Section 4.2.
Method
SCIFAR
IMDB
LISTOPS
SCIFAR
SPATIAL
58.20 + 0.70
83.50 + 0.20
32.02 + 0.27
50.63 + 0.23
TRUNC.
60.01 + 1.26
84.04 + 0.47
31.88 + 0.59
50.53 + 0.43
OURS
79.59 + 1.01
86.48 + 0.41
37.62 + 0.68
63.71 + 0.33
BPTT
83.40 + 1.54
87.69 + 0.39
39.75 + 0.17
65.23 + 0.56
Our findings confirm the benefits of independent recurrent modules for online learning, in particular for multi-layer networks. To demonstrate that, we first compare our algorithm on the LRU architecture with the SnAp-1 algorithm applied to an equivalent linear recurrent network. The diagonal approxima- tion of the sensitivity tensor in SnAp-1 introduces an additional bias when learning linear RNNs. We found that this additional bias hurts performance: when moving from offline BPTT to online training, the performance drop significantly higher for linear RNNs. Interestingly, sensitivity approximation does not bring any performance gain, in this setting, compared to the cruder approximations that are 1-step truncated BPTT and spatial backpropagation.
Additionally, we run experiments on another RNN architecture, the GRU [44], to better understand the impact of depth in online and offline RNN training, and to confirm the importance of clement- wise recurrence for online learning. In the single layer case, consistent with Menick et al. [15]. we find that the SnAp-1 1 approximation performs competitively with offline BPTT. However, it suffers from depth in contrast to BPTT that benefits from it. This result highlights the importance of depth in this memory task, well as the difficulty learning over depth poses for existing online learning algorithms.
4.3 Scaling online learning to the long-range arena benchmark
While the approximations typically employed to enable online learning prohibit scaling tasks with extended temporal structure, the results from our previous section have demonstrated the potential of independent linear units for online learning of long-range dependencies. We therefore move to tasks from the challenging long-range arena benchmark [24] specifically designed to evaluate this ability. Transformers excel in almost any benchmark today. However, they perform surprisingly subpar in this setting [45] in which deep state-space models [20] and LRUs [23] achieve impressive results.
We run experiments three tasks, sequential CIFAR, IMDB and LISTOPS. In sequential CIFAR, the network receives the 32 32 image as a pixel sequence and has to perform a classification task. In line with Orvicto et al. [23], we use the colored version of SCIFAR instead of the grayscale version
8

---

originally proposed. In the IMDB task, the network is given a text encode in bytes of length at most 4000, and has to perform binary classification. In LISTOPS, the input a sequence of numbers, brackets and operators like MAX which the model needs to evaluate to determine classification target in the range from 10. We do not use the three other tasks of the LRA benchmark: the performance gap between different models is usually small in the RETRIEVAL task (c.f. [23]) and, in our preliminary experiments, we could not reach above chance performance in the PATHFINDER tasks with BPTT and the modifications we made to make the loss causal, as described in the next paragraph.
In order to make the sequence models employed on this benchmark compatible with the causality requirement in online learning, we remove the time pooling operation during training and consider a local loss term at every time step instead. During inference, we then evaluate our models using the average of the last layer logits in time which respects causality. Moreover, we replace batch normalization with layer normalization to avoid sending batch statistics backwards in time and con- sider smaller models to lower the computational burden for online learning. For further experimental details, please refer to Appendix B.
We report results comparing online learning to spatial backpropagation, truncated BPTT and the BPTT upper bound in Table 2. Our online learning algorithm outperforms other online learning approximations, significantly reducing the gap towards BPTT. As in the last section, replacing the LRU with a linear RNN layer in the CIFAR experiment leads to worth online learning performance, c.f. Table 3, providing further evidence for the effectiveness of independent recurrent modules for capturing long-term dependencies.
5 Discussion
We have demonstrated that long-range dependencies can be learned online, allowing recurrent neural networks to reach strong performance set of tasks from the long-range arena benchmark. Moreover, a detailed analysis of a memory problem revealed that our method significantly outperforms both spatial (online) backpropagation as well as prior approaches based on approximate real-time recurrent learning, coming close to full packpoopaattion-trrughh the design of new neuromorphic hardware with on-chip learning capabilities, an application where approximate real-time recurrent learning is garnering significant attention [46-48].
These findings may inform
While most prior related work focused on developing generic gradient approximation schemes, we asked which architecture would simplify online gradient computations. In high-level terms, our philosophy draws from seminal work on long short-term memory networks [LSTMs; 40] or neural Turing machines [49], which established the importance of architecture design for the success of gradient descent. We build this insight, moving to the harder setting of online learning. This led us to consider networks built of recurrent independent modules: decoupled units with low- -iw-dimensional state vectors, for which exact real-time recurrent learning is cheap. Importantly. this design underlies recent models such as deep linear recurrent units [23] and members of the HiPPO family [21, 22] which achieve strong performance in wide array of challenging problems, including language modeling at scale [50] and the long-range arena benchmark [22].
We conclude by noting that modularity, the overarching principle behind our approach, is at the very heart of the influential columnar hypothesis in neuroscience [51]. This hypothesis states that the architecture of the neocortex is modular, with the cortical column as elementary (or canonical, [52]) building block one level of abstraction above neurons. We thus speculate that modularity could be a key neural network design principle discovered by evolution, that considerably simplifies the temporal credit assignment problem. This is inline with our finding that a modular architecture enables learning complicated temporal dependencies through simple local temporal credit assignment mechanisms, letting spatial backpropagation take care of assigning credit over the network hierarchy. We stress this point because numerous biological implementations and alternatives for spatial backpropagation have been proposed [e.g., 53-62), while essentially none exist yet for Our findings provide starting point for understanding how the brain deals with the fundamental problem of learning the temporal structure behind its sensory inputs.
[63].

---

Acknowledgments and Disclosure of Funding
All five authors thank Angelika Steger for her support and overarching guidance. João Sacramento thanks Timothy Lillicrap and Greg Wayne for inspiring early discussion on searching architectures that can learn through limited forms of iikppoopgaiion--trogg---------
and Owen He and Johannes von Oswald for valuable discussions deep state space models. This research was supported by an Ambizione grant (P200P3_186027) from the Swiss National Science Foundation and an ETH Research Grant (ETH-23 21-1). Robert Meier and Asier Mujika were supported by grant no. CRSII5 173721 the Swiss National Science Foundation.
References
[1] Blake A. Richards, Timothy P. Lillicrap, Philippe Beaudoin, Yoshua Bengio, Rafal Bogacz, Amelia Christensen, Claudia Clopath, Rui Ponte Costa, Archy de Berker, Surya Ganguli, Colleen J. Gillon, Danijar Hafner, Adam Kepecs, Nikolaus Kriegeskorte, Peter Latham, Grace W. Lindsay, Kenneth D. Miller, Richard Naud, Christopher C. Pack, Panayiota Poirazi, Pieter Roelfsema, João Sacramento, Andrew Saxe, Benjamin Scellier, Anna C. Schapiro, Walter Senn, Greg Wayne, Daniel Yamins, Friedemann Zenke, Joel Zylberberg, Denis Therien, and Konrad P. Kording. A deep learning framework for neuroscience. Nature Neuroscience, 22(11): 1761-1770, 2019.
[2] David E. Rumelhart and James L. McClelland. Learning internal representations by error prop- agation. In Parallel Distributed Processing: Explorations Microstructure of Cognition: Foundations, pages 318-362. 1986.
[3] Seppo Linnainmaa. Taylor expansion of the accumulated rounding error. BIT Numerical Mathematics, 16(2):146-160, 1976.
[4] Paul Werbos. Backpropagation through time: what it does and how to do it. Proceedings of the IEEE, 78(10):1550-1560 1990.
[5] Charlotte Frenkel, David Bol, and Giacomo Indiveri. Bottom-up and top-down neural pro- cessing systems design: neuromorphic intelligence as the convergence of natural and artificial intelligence. arXiv preprint arXiv:2 106.01288, 2021.
[6] Surya Ganguli, Dongsung Huh, and Haim Sompolinsky. Memory traces in dynamical systems. Proceedings of the National Acudemy of Sciences, (05(48):18970-18) 2008
[7] Ronald J. Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 12):27002800 1989.
[8] R. E. Wengert. A simple automatic derivative evaluation program. Communications of the ACM, 7(8):463 1964.
[9] Corentin Tallec and Yann Ollivier. Unbiased online recurrent optimization. In International Conference on Leurning Representations, 2018
[10] Asier Mujika, Florian Meier, and Angelika Steger. Approximating real-time recurrent learning with random Kronecker factors. Advances in Neural Information Processing Systems, volume 31, 2018.
[11] Frederik Benzing, Marcelo Matheus Gauy, Asier Mujika, Anders Martinsson, and Angelika Steger. Optimal Kronecker-sum approximation of real time recurrent learning. In International Conference on Machine Learning, 2019.
[12] James M. Murray. Local online learning in recurrent networks with random feedback. elife, 8: e43299, 2019.
[13] Guillaume Bellec, Franz Scherr, Anand Subramoney, Elias Hajek, Darjan Salaj, Robert Leg- enstein, and Wolfgang Maass. solution to the learning dilemma for recurrent networks of spiking neurons. Nature Communications, 11(1):3625, 2020.
10

---

[14] Owen Marschall, Kyunghyun Cho, and Cristina Savin. A unified framework of online learning algorithms for training recurrent neural networks. The Journal of Machine Learning Research, 21(1):135:5320-133.2 135:5333, 2020.
[15] Jacob Menick, Erich Elsen, Utku Evei, Simon Osindero, Karen Simonyan, and Alex Graves. A practical sparse approximation for real time recurrent learning, In International Conference on Learning Representations, 2021.
[16] Friedemann Zenke and Tim P. Vogels. The remarkable robustness of surrogate gradient learning for instilling complex function in spiking neural networks. Neural Computation, 33(4):899-925, 2021.
[17] Atlim Güney Baydin, Barak A. Pearlmutter, Don Syme, Frank Wood, and Philip Torr. Gradients without backpropagation. arXiv preprint arXiv:2202.08887, 2022. 2022.
[18) David Silver, Anirudh Goyal, Ivo Danihelka, Matteo Hessel, and Hado van Hasselt. Learning by directional gradient descent. International Conference on Learning Representations, 2022.
[19] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. HiPPO: recurrent memory with optimal polynomial projections. In Advances Neural Information Processing Systems, volume 33, 2020.
[20] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022.
[21] Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective structured states spaces. In Advances in Neural Information Processing Systems, volume 35, 2022.
[22] Jimmy T.H. Smith, Andrew Warrington, and Scott W. Linderman. Simplified state space layers for sequence modeling. In International Conference on Learning Representations, 2023.
[23] Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. arXiv preprint arXiv:2303.063 2023.
[24] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. arXiv preprint arXiv:2011.0400 2020.
[25] Andreas Griewank and Andrea Walther. Evaluating Derivatives. Society for Industrial and Applied Mathematics, 2008
[26] L. McBride and K. Narendra. Optimization of time-varying systems. JEEE Transactions on Automatic Control, 1033):289-294 1965.
[27] Max Jaderberg, Wojciech Marian Czarnecki, Simon Osindero, Oriol Vinyals, Alex Graves, David Silver, and Koray Kavukcuoglu. Decoupled neural interfaces using synthetic gradients. In International Conference on Machine Learning, 2017.
[28] Gregory D. Wayne. Self-modeling neural systems. PhD thesis, Columbia University, 2013.
[29] Schmidhuber. Recurrent networks adjusted by adaptive critics. In JEEE/INS International Joint Conference on Neural Networks, volume 1, 1990.
[30] Richard S. Sutton. Learning predict by the methods of temporal differences. Machine Learning, 3:9-44, 1988.
[31] Kazuki Irie, Anand Gopalakrishnan, and Jürgen Schmidhuber. Exploring the promise and limits of real-time recurrent learning. arXiv preprint arXiv:2305.1904: 2023.
[32] Khurram Javed, Haseeb Shah, Richard S Sutton, and Martha White. Scalable real-time recurrent learning using columnar--cnnsrructvv networks. Journal of Machine Learning Research, 24, 2023.
11

---

[33] Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent difficult. IEEE Transactions on Neural Networks, 5(2), 1994.
[34] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference Machine Learning. 2013.
[35] Guy E. Blelloch. Prefix sums and their applications, 1990.
[36] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint 107.v.160..06455. 2016.
[37] Yann N. Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In International Conference on Machine Learning, 2017.
[38] Michael C Mozer. A focused backpropagation algorithm for temporal pattern recognition. Complex Systems, 3, 1989.
[39] Marco Gori, Yoshua Bengio, and Renato De Mori. BPS: a learning algorithm for capturing the dynamic nature of speech. In International Joint Conference on Neural Networks, 1989.
[40] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, (8):1735-1780, 1997.
[41] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, 2009.
[42] Nikita Nangia and Samuel R Bowman. ListOps: A diagnostic dataset for latent tree learning. arXiv preprint arXiv:1804.0602 2018
[43] Andrew I.. Maas, Raymond F. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 2011.
[44] Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: encoder-decoder approaches. In Proceedings of SSST-8, Eighth Workshop Syntax, Semantics and Structure in Statistical Translation, 2014.
[45] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344-16359, 2022.
[46] Friedemann Zenke and Emre O. Neftei. Brain-inspired learning on neuromorphic substrates. Proceedings of the IEEE, 109(5):935-9)) 950, May 2021.
[47] Charlotte Frenkel and Giacomo Indiveri. ReckOn: 28nm sub-mm2 task-agnostic spiking recurrent neural network processor enabling on-chip learning over second-long timescales. In 2022 IEEE International Solid- State Circuits Conference (ISSCC), volume 65, February 2022.
[48] Yigit Demirag, Charlotte Frenkel, Melika Payvand, and Giacomo Indiveri. Online training of spiking recurrent neural networks with phase-change memory synapses. arXiv preprint arXiv:2108.0188 010000 2021.
[49] Alex Graves, Greg Wayne, and Ivo Danihelka. Neural Turing machines. arXiv preprint arXiv:1410.5400 2014.
[50] Daniel Y. Fu, Tri Dao, Khaled K. Saab, Armin W. Thomas, Atri Rudra, and Christopher Ré. Hungry hungry hippos: towards language modeling with state space models. arXiv preprint arXiv:2212. 14052, 2023.
[51] Vernon B. Mountcastle, Modality and topographic properties of single neurons of cat's somatic sensory cortex. Journal of Neurophysiollgyy 20(4):408-434, 1957.
[52] Rodney J. Douglas, Kevan A.C. Martin, and David Whitteridge. A canonical microcircuit for neocortex. Neural Computation, 1(4):480-488, 1989.
12

---

[53] Dong-Hyon Hyun Lee, Saizheng Zhang, Asja Fischer, and Yoshua Bengio. Difference target prop- agation. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2015.
[54] Timothy P. Lillicrap. Daniel Cownden, Douglas B. Tweed, and Colin J. Akerman. Random synaptic feedback weights support error backpropagation for deep learning. Nature Communi- cations, 7(1):13276, 2016.
[55] Benjamin Scellier and Yoshua Bengio. Equilibrium propagation: bridging the gap between energy-based models and backpropagation. Frontiers in Computational Neuroscience, 11, 2017.
[56] Pieter R. Roclfsema and Anthony Holtmaat. Control of synaptic plasticity in deep cortical networks, Nature Reviews Neuroscience, 19(3):166-180, 2018.
[57] James C. R. Whittington and Rafal Bogacz. Theories of error back- pack-propagation in the brain. Trends in Cognitive Sciences, 23(3):235 250, 2019.
[58] Timothy P. Lillicrap, Adam Santoro, Luke Marris, Colin J. Akerman, and Geoffrey Hinton. Backpropagation and the brain. Nature Reviews Neuroscience, 21(6):335-346, 2020.
[59] Alexandre Payeur, Jordan Guerguiev, Friedemann Zenke, Blake A. Richards, and Richard Naud. Burst-dependent synaptic plasticity can coordinate learning in hierarchical circuits. Nature Neuroscience, 2417))1010-1019, 2021.
[60] Alexander Meulemans, Nicolas Zucchet, Seijin Kobayashi, Johannes von Oswald, and João Sacramento. The least-control principle for local learning at equilibrium. Advances in Neural Information Processing Systems, volume 35, 2022.
[61] Axel Laborieux and Friedemann Zenke. Holomorphic equilibrium propagation computes exact gradients through finite size oscillations. In Advances in Neural Information Processing Systems, volume 35, 2022.
[62] Walter Senn, Dominik Dold, Akos F. Kungl, Benjamin Ellenberger, Jakob Jordan, Yoshua Bengio, João Sacramento, and Mihai A. Petrovici. neuronal least-action principle for real- time learning in cortical circuits. bioRxiv 2023.03.25.534111 2023.
[63] Timothy P. Lillicrap and Adam Santoro. Backpropagation through time and the brain. Current Opinion in Neurobiology, 55:82-89, 2019.
13

---

A Network architecture and algorithm
A.1 The linear recurrent unit (LRU)
In Section 2.2, we used a simplified version of the LRU for brevity. Here, we review the more detailed formulation of Orvieto al. [23]. The LRU is defined as follows:
he+1 x he @ Br.
(8)
3/1 = Re[Ch,] + Dry-
The only difference with Equation is the inclusion of the normalization factor y E RRN. Its purpose to ensure that all units maintain comparable magnitude. Without normalization, hidden states whose À is close to can blow up. We initialize with
/1 IN
(10)
and later update it with our learning algorithm. We use exponential parametrization for A:
À := exp( exp(1/ + ex
(1I)
This parametrization ensures that the norm of X. equal to exp(lox)))) remains below 1, guaranteeing stability the network dynamics. This feature provides an advantage to the LRU compared to the linear RNN, observed in Section 4.2. By representing 0 as exp(0"*), we achieve finer tuning of around O. the following, we focus on computing gradients with respect to However, in simulations, derive the update for foo and f from these gradients through the chain rule, and apply them to update the corresponding parameters. Similarly, we optimize the logarithm of y-
A.2 Complete derivation of our algorithm
We provide more detailed derivation of our online learning rule a single layer of LRUs, as described in Section 3.1. Recall that define e, to be the non-zero terms of the sensitivity dah, of the state fe with respect to the parameters 0, with = {A, y, B} the parameters of the LRU impacting the recurrent dynamics. We show that the sensitivities evolve according
c X et he e Ao e + Bra-
(12)
(13)
t+1
diag + 7=
(14)
and that gradient- parameter updates can be calculated through
T
AA
5n 3 e
(15)
A7
Relōe 3 e7]
(16)
AB x
diag
(17)
with 6, dr, Lt. These updates are the ones used in our simulations. We now derive the updates per coordinate, and the vectorized form can be straightforwardly obtained from there.
Update for X. We have
dh dA;
[Aphe,l + Xçe + h dx;
(18)
The first equality uses the definition of e the second the recurrent update of h as in Equation and the fact that C Brx+1 does not depend on X, and the third is the complex product rule. The
14

---

gradient of the loss with respect to A is then equal
to dL, dhe
dL
(19)
dYp
dhus dA
j
T dLs dhu,i
(20)
dhg dd
(21)
In the first line, we applied forward-mode complex differentiation (combined with he being an holomorphic function of X) in Equation 5. In the second, we used that h; is independent of X for ? { j.
Update for The derivation for the recurrent update of e² being very similar to the one for X, we omit The fact that y is real variable does not change anything to this derivation. However, this makes the gradient computation slightly different, One can act as if was complex variable 7/ and get
dL
(22)
dh
c
Now, looking at the real part of the previous equation, we have
dL
dy = Σ e2
(23)
Note that the factor 2 will also indirectly appear in the update X, although not yet there gradient, as we have real derivative here, when is complex above. Update for B. We have
B dhyti d eti
dhy,
(yyhes + 73s YyBBett+ A
dBj. + 7y
(24)
dB
dB,;
and
T
dL
= Σ
(25)
dB
t=1
Note that the update for B is more general than the one of Equation in the main text in which 7 I.
B Experimental details
We base our implementation on the S5 [22] code base All networks are trained with the A optimizer, with linear learning rate Following common practice, we do not apply weight decay for X, 7, and use smaller learning rate for those parameters (global learning rate times learning rate factor). By default, initialize uniformly at random in the complex disk and 0 uniformly at random in [0, 2T..
up, followed by one-cycle cosine learning decay.
B.1 Copy task experimental details and hyperparameters
We report the hyperparameters we used and scanned over for the copy task in Tables 4 and 5. In Section 4.1, we take the default configuration reported in the LRU paper [23] for backpropagation through-time -ime and apply it the different methods we consider. We use 25 epochs, with linear warmup of 5 epochs. We tuned the learning rate for each method independently Figure 2.E and F and in the one of Table 1. For the I-layer GRU architecture, following Menick et al. [15], we add an extra readout layer: a 1-hidden layer MLP with hidden dimension 1072 processes the hidden state to generate the output.
the comparison of
'https:// peattp://githrn htt.ha/....co.nnnnnaaaaaaaa////a
15

---

Table 4: Hyperparameter configurations for Section 4.1. We use [...] denote hyperparameters. that were scanned over with grid search and {-... denote the variables interest for the figure.
Hyperparameter
FIG.2.A/B
FiG.2.C/D
FiG.2.E/F
Learning rule
Ours
Ours
[Ours, Spat., Trunc., BP)
Pattern length
20
20
Padding
7
7 20000
7
Training samples
20000
20000
Number of layers
{1, 2, 3,44
4
4
Recurrent state size
64
64
64
Model size H
128
128
128
Aanin
0
{0, 0.5, 0.75, 0.9)
Epochs
25
25
25
Warmup
0
0
Batch-size
50
50
50
Base learning rate
10-3
2 x 3
200.1.2.3 10 -3
Learning rate factor
0.5
0.5
0.5
Dropout probability
0.1
0.1
0.1
Weight-decay
0
0
Table 5: Hyperparameter configurations for Section 4.2. We use [...] to denote hyperparameters that
scanned over.
Layer Number layers
LRU
Linear RNN
GRU
GRU
4
4
4
Pattern length
20
20
20
20
Padding
7
7
7
7
Training samples
20000
20000
20000
20000
GLU
Yes
Yes
No
Yes
N
64
64
134
91
128
146
134
91
Extra readout
No
No
1072
No
Number parameters
268,430
267,956
269,488
270,011
Batch-size
20
20
20
20
Base learning rate
200.-=55
10 -3
2.0.
10
200,
50
200.- _5]
10 -3
Learning rate factor
Dropout probability
0.1
0.1
0.1
0.1
Weight-decay
0
16

---

Table Hyperparameter configurations for SCIFAR, IMDB and LISTOPS experiments. We use
[...] to denote hyperparameters that were scanned over with grid search. By default, the {}, 7 parameters have no weight decay and have a slower learning rate (c.f. learning rate factor).
Hyperparameter
CIFAR
IMDB
LISTOPS
Number of layers
4
4
Recurrent state size N
128
128
128
Model size H
256
256
256
Mima
0.9
[0.0, 0.9]
[0.0, 0.9]
A max
0.999
Batch-size
100
32
Base learning rate Learning rate factor
[0.001, 0.004]
[0.001,
0.003]
[0.001, 0.003]
0.5
0.5
0.5
Dropout probability
0.1
0
0.1
Weight-decay
[0.1, 0.5]
0.05
0.05
Epochs
180
40
35
Warmup
18
B.2 Experimental details and hyperparameters for SCIFAR, IMDB and LISTOPS
For all experiments, we first ran a manual coarse-grainge grainerr hyperparameter tuning to identify the most important parameters, and then ran the grid search described in 6. The final hyperparameters were each evaluated on 3 fresh seeds for the results reported in Table 2. The training time for our online learning rule single Nvidia RTX3090 GPU for SCIFAR, IMDB and LISTOPS was respectively 36, 10 and 40 hours.
For the comparison with linear RNNs, we kept the number N of hidden neurons fixed compared to the one used the LRU (c.f. Table 6), but changed the model size to 294 in order obtain the same number of parameters (our Linear RNN has 1,068,086 parameters vs. 1,063, 178 for the LRU). We used the same hyperparameter optimization scheme.
17


Reviews:
[{"review_id": "mF1X9Temlh", "reviewer": "Reviewer_Z8SA", "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.", "questions": "* How would the hyperparameters be optimized for the online learning setting where BPTT results are not available?\n\n* 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.\n", "limitations": "limitations of the works has been discussed briefly, but not the potential negative societal impact", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n\n* 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.\n\n* 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.\n\n* 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the useful questions and comments. We reply below to each of them.\n\n> 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.\n\nThank you for raising this point, which made us realize that we were not precise enough in our comparison with SnAp-1. We will update our manuscript with a detailed discussion, cf. global response [link](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS). Besides being able to learn complex neurons, our rule handles multilayer recurrent neural networks (RNNs) differently, something that we failed to point out previously. More concretely, SnAp-1 does not send detailed spatial credit assignment information in deep RNN models such as the LRU. At best it only broadcasts a global error backwards through skip connections, and in the worst case for networks without skip connections it leads to identically zero updates to deep hidden recurrent neurons (that do not directly influence the loss). Getting a learning signal for such neurons requires raising $k$ in SnAp-$k$, which comes at additional computational and memory costs. In contrast to SnAp, by combining forward sensitivity propagation with spatially backpropagated errors, our hybrid learning rule delivers detailed learning signals even to hidden recurrent neurons, while retaining the cost of a single inference pass.\n\n> 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. [...] 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.\n\nWe reran our experiments after fixing a number of bugs (detailed in the global response, [link](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS)) and retuned hyperparameters for every method separately, no longer perturbing around the hyperparameters that were optimal for BPTT. This widened the gap between our algorithm and spatial backpropagation, in particular on the long-range arena benchmarks, cf. rebuttal results pdf. We note that these results are quite strong in absolute terms, greatly outperforming transformer models, which in turn already require attention spans on the order of hundreds of tokens for these tasks (cf. [24]).\n\nMoreover, to give a better sense of the significance of our results, we performed new sequential CIFAR experiments now using dense stacked linear recurrent networks (the fully-connected counterpart of the diagonal LRU) trained online. These dense models are significantly outperformed by our online-learned diagonal LRU networks.\n\n> 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. [...] How would the hyperparameters be optimized for the online learning setting where BPTT results are not available?\n\nWhile we fully agree with the reviewer that ultimately this question will need to be answered, we feel that it is too difficult of a challenge on its own, and out of the scope of the present study. We will add a remark to the experimental section of our paper emphasizing that our results should read as an upper bound obtained using hindsight knowledge of the best hyperparameters, as is customarily done in the approximate RTRL literature. We will further note that complementary techniques developed in the continual and broader online learning literature may be used to help tune hyperparameters in an online, adaptive fashion.\n\nWe are pleased to answer any further questions that you may have during the ensuing discussion period. We note that we ran additional experiments triggered by other reviews, that we collected in the global response ([here](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS))."}, {"review_id": "U97jj6bzlZ", "reviewer": "Reviewer_XofY", "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.\n", "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?\n\n- 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?\n\n- 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?", "limitations": "There is no direct potential for negative social impact. Potential limitations for the method and results are either discussed or covered above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n", "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.\n\n- 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).\n\n- 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive and useful criticism. We reply point by point below.\n\n> 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.\n\nWhile we find our results promising as a starting point for more biologically realistic models, we agree that the discussion balance pended too much towards neuroscience. We will keep our neuroscience discussion to a single paragraph in the next version of the paper, which will read:\n*\"We conclude by noting that modularity, the overarching principle behind our approach, is at the very heart of the influential columnar hypothesis in neuroscience (Mountcastle, 1957). This hypothesis states that the architecture of the neocortex is modular, with the cortical column as an elementary (or canonical, cf. Douglas et al., 1989) building block one level of abstraction above neurons. We thus speculate that modularity could be a key neural network design principle discovered by evolution, that considerably simplifies the temporal credit assignment problem. This is in line with our finding that a modular architecture enables learning complicated temporal dependencies through simple local temporal credit assignment mechanisms, letting spatial backpropagation take care of assigning credit over the network hierarchy. Our findings provide a starting point for understanding how the brain deals with the fundamental problem of learning the temporal structure behind its sensory inputs.\"*\n\n> 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?\n\nWe also agree that too much space was allocated to this detail and we will remove it in the next version of our paper. Those considerations were a consequence of the initialization bug of the $D$ matrix we had in our code, c.f. the [global answer](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS) for more details, and do not hold anymore.\n\n> 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?\n\nWe will discuss in the next version of the paper the required attention span analysis provided in the original LRA paper [24]. This analysis shows that transformer models need to attend to past inputs on the order of hundreds for the tasks we considered. Our online-learned models greatly outperform transformers, which suggests that long-range dependencies are being captured. While based only on these results we cannot entirely rule out that our models could be making better use of shorter contexts, it seems unlikely that this is the case for LRUs; we will nonetheless add a disclaimer for this point.\n\n> Can the authors share their reasons for limiting evaluation to a subset of the LRA benchmark?\n\nWe now ran an additional set of experiments on the IMDB LRA benchmark, where we observe the same overall pattern of results, with our method coming closer to BPTT than to spatial backpropagation in terms of performance (cf. rebuttal results pdf). We didn’t run experiments on the other datasets of the LRA benchmark. The gap between linear RNNs and LRUs is close to 0 in the retrieval dataset (see Table 8 in [24]) so differences between online learning methods are likely to be small. For the pathfinder tasks, we could not get more than chance level with BPTT and the online version of the loss, suggesting that further algorithmic / architecture developments are needed before being able to learn those tasks online. We will add a short comment explaining this rationale to the next version of the paper.\n\n> 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?\n\nWe indeed allow for multiple passes over a finite training set, as is customarily done in the approximate RTRL literature. We opted for this standard setup to make it easier to gauge how close our method can now get to conventional, offline gradient-based learning via BPTT, which is traditionally far better than approximate RTRL. We will clarify this rationale in the next version of the paper.\n\nWe are fully available to answer any further questions you may have during the discussion period. We note that we ran additional experiments triggered by other reviews, that we collected in the global response ([link](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS))."}, {"review_id": "iPcRaxtNpI", "reviewer": "Reviewer_14Gy", "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.", "questions": "- Where is the high variance of the proposed algorithm in the ListOps task coming from?\n- 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?\n- 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?", "limitations": "A discussion of limitations of the work is missing.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "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.\n- 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?\n- 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) .\n\nMinor:\n- Two typos in equation 1 (formula for yt)\n- No description for panels A-D in caption of figure 2\n- Maybe adding h-lines for 100% and 70% accuracies in figure 2?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your useful review. We reply to your specific questions and concerns individually below.\n\n> 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.\n\nThank you for raising this question, which made us realize that we were not precise enough in our comparison with SnAp-1. We will update our manuscript with a detailed discussion, cf. [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS). Besides being able to learn complex neurons, our rule handles multilayer recurrent neural networks (RNNs) differently, something that we failed to point out previously. More concretely, SnAp-1 does not send detailed spatial credit assignment information in deep RNN models such as the LRU. At best it only broadcasts a global error backwards through skip connections, and in the worst case for networks without skip connections it leads to identically zero updates to deep hidden recurrent neurons (that do not directly influence the loss). Getting a learning signal for such neurons requires raising $k$ in SnAp-$k$, which comes at additional computational and memory costs. In contrast to SnAp, by combining forward sensitivity propagation with spatially backpropagated errors, our hybrid learning rule delivers detailed learning signals even to hidden recurrent neurons, while retaining the cost of a single inference pass.\n\n> 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?\n> \n\nThe independent recurrent module design is indeed well-suited for the copy task. However, we would like to emphasize that (1) our learning rule is still much better than truncated and spatial backpropagation applied to the same architecture (cf. Fig. 2 E/F), and (2) for this task and architecture (at this width), performance still improves with depth (cf. Fig. 2 A/B) when training with our learning rule. Together these two points show that our rule can do deep spatiotemporal credit assignment.\n\n> 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) .\n> \n\nWe now trained dense linear RNNs using BPTT, truncated BPTT, spatial backpropagation and our hybrid learning rule (which combines SnAp-like forward sensitivity propagation with spatial backpropagation) on sequential CIFAR, cf. [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS) results pdf). Our online-learned LRUs greatly outperform online-learned dense linear RNNs. The next version of the paper will include dense linear RNN results for the remaining LRA tasks considered here, ListOps and IMDB.\n\n> Minor:Two typos in equation 1 (formula for yt)No description for panels A-D in caption of figure 2Maybe adding h-lines for 100% and 70% accuracies in figure 2?\n\nThank you for catching the typos and for the helpful figure suggestions that we will take in.\n\n> Where is the high variance of the proposed algorithm in the ListOps task coming from?\n\nAfter our bug fix (cf. [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS)), variance is now much smaller (0.68% for our learning rule, vs. 0.17% for BPTT, 0.59% for truncated BPTT and 0.27% for spatial BP).\n\n> 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?\n> \n\nThe one-hot encoded target is given at every time step and the total loss is the average of all instantaneous losses. We haven’t run any experiments in which targets are given more rarely.\n\n> 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?\n> \n\nThe lengths of the sequences we consider are 1024 in sCIFAR, 2048 in ListOps, and 4096 in IMDB.\n\nWe hope that these clarifications together with the additional results triggered by other reviewers (cf. [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS)) help you see our work in a more positive light. We are very happy to address any further questions that may arise during the discussion period."}, {"review_id": "jpzqRdwApx", "reviewer": "Reviewer_53aD", "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.", "questions": "-\tThe authors should study the relation with e-prop and inform if there are any differences with it. To me, their algorithm is the same.\n-\tIn Fig. 3, I expect that BP is BPTT, and Spat. Is just the spatial BPTT without temporal dependencies? If not, was BPTT not used?\n\nMinor:\n-\tMistakes 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.\n-\tL304: inference -> inference\n", "limitations": "N/A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-\tThe 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.\n-\tThey demonstrate good results on some long-range dependency tasks as compared to RNNs.\n", "weaknesses": "-\tThe 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.\n-\tTheir algorithm still relies on spatial backprop between layers, so this is still not local in space.\n-\tThe 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].\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your useful review. We reply to your specific questions and concerns individually below.\n\n> 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. [...] 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.\n\nOur learning rule is indeed very closely related to e-prop and SnAp. We will update our manuscript with a detailed discussion, cf. [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS). Besides being able to learn complex neurons, our rule handles multilayer recurrent neural networks (RNNs) differently, something that we failed to point out previously. More concretely, e-prop and SnAp-1 do not send detailed spatial credit assignment information in deep RNN models such as the LRU. At best it only broadcasts a global error backwards through skip connections, and in the worst case for networks without skip connections it leads to identically zero updates to deep hidden recurrent neurons (that do not directly influence the loss). By combining forward sensitivity propagation with spatially backpropagated errors, our hybrid learning rule delivers detailed learning signals even to hidden recurrent neurons, while retaining the cost of a single inference pass.\n\n> Their algorithm still relies on spatial backprop between layers, so this is still not local in space.\n\nYes. In this manuscript, we opted to present the architecture and algorithm in its purest form and attack the challenging LRA suite. We will add a comment to the next version of the paper, explicitly suggesting that it would be interesting to explore replacing spatial backpropagation by approximations such as feedback alignment (Lillicrap et al., 2015) in future work.\n\n> 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].\n\nWe originally intended to emphasize that the rule only needs spatial backpropagation and not reverse-mode temporal backpropagation, in the strict sense (not encompassing forward-mode differentiation), but the remark ended up being confusing. We will remove it from the discussion in the next version of the paper.\n\n> 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?\n\nYes, BP is BPTT, and Spat. is spatial backpropagation. This will be clarified.\n\n> 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\n\nThank you for spotting these typos, which will be corrected in the next version of the paper.\n\nWe are more than happy to answer additional questions that you may have during the discussion period. We note that we ran additional experiments triggered by other reviews, that we collected in the [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS)."}, {"review_id": "r7iKwIK46b", "reviewer": "Reviewer_hL6u", "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.\n\nThe 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.", "questions": "### Typos and suggestions\n1. Line 130: Using them for complex differentiation allows using calculus rules that are similar to those for real valued functions.\n2. Line 167: \"Those\" as a vague reference here might cause confusion. It might be better to say $e^\\lambda$ and $e^B$ explicitly.", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Originality\n\nThe 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.\n\n### Quality\n1. The paper is technically sound, has carefully designed experiments that support the claims well.\n2. claims supported by theory and/or experiments\n### Clarity\n1. The paper is well organized and clear for most part. There are some parts that can be improved (see weaknesses).\n### Significance\n1. The well designed experiments make the results presented in the paper useful for the community.", "weaknesses": "### Quality\n1. 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.\n2. Why does table 1 not contain sparse approximation method like SnAp-n applied to dense RNNs?\n\n### Clarity\n\nFollowing  are some mistakes/typos in the paper that can throw a reader off.\n1. 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$.\n2. Line 109-111: I think you mean to say *absence of temporal non-linearity* in line 110.\n\nFollowing are some suggestions that could improve the paper:\n1. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your useful comments and thoughts. We reply below to each point raised individually.\n\n> 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.\n\nWe would like to note that approximate RTRL research is still in a proof-of-concept phase, and prior work has only considered at best only very small-scale language modeling experiments. These would be the experiments within our reach. The problem with this is that it seems likely that such small-scale experiments would not reveal the ability to model long-range dependencies; our impression based on prior work is that most of the capacity is used to learn dominant short-range dependencies with small RNN models. This may be one of the reasons why the SnAp authors found surprisingly good results on small-scale character-level modeling already with reservoir (not learned) GRU networks, and why SnAp almost matched BPTT. We would also note that the LRA is not entirely toyish, and a challenging problem suite; for example, transformer models are not strong performers there, and they require large attention spans on the order of hundreds of tokens [24].\n\nWe have however experimented with single- and multilayer GRU networks on the copy task (cf. [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS)), trained with approximate RTRL (SnAp combined with spatial backpropagation to allow training deep networks, as we did for our models), BPTT, TBPTT and spatial backpropagation, and found that such networks are greatly outperformed by LRU networks when trained online. Interestingly, only BPTT can leverage the additional capacity of deep GRU networks, whereas online approximate RTRL stagnates at some value corresponding to a 1-layer GRU. This again shows the power of approximate online RTRL when paired with networks with independent recurrent modules. We are currently running experiments with both single- and multilayer GRU networks on sequential CIFAR and we will add those results to the next version of the paper.\n\n> Why does table 1 not contain sparse approximation method like SnAp-n applied to dense RNNs?\n\nWe now trained dense linear RNNs using BPTT, truncated BPTT, spatial backpropagation and our hybrid learning rule (which combines SnAp-like forward sensitivity propagation with spatial backpropagation) on sequential CIFAR, cf. [global response](https://openreview.net/forum?id=Wa1GGPqjUn&noteId=HB3E5CrCGS) results pdf. Our online-learned LRUs greatly outperform online-learned dense linear RNNs. The next version of the paper will include dense linear RNN results for the remaining LRA tasks considered here, ListOps and IMDB.\n\n> 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.\n\nThank you for this suggestion with which we agree. We will expand section 3.2 with expressions for the spatially backpropagated error $\\delta$ and improve Fig. 1 following your suggestion.\n\n> 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$.\n> Line 109-111: I think you mean to say absence of temporal non-linearity in line 110.Line 130: Using them for complex differentiation allows using calculus rules that are similar to those for real valued functions.Line 167: \"Those\" as a vague reference here might cause confusion. It might be better to say $e^\\lambda$ and $e^\\gamma$ explicitly.\n\nThank you for catching these mistakes, which we will correct in the next version of the paper.\n\n> 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.\n\nWe did not wish to oversell our claims. We will downtone our discussion presenting our results as promising while clarifying that they are still limited to relatively small-scale image (sequential CIFAR), text (IMDB) classification and symbol manipulation (ListOps) tasks.\n\nWe remain fully available to respond to any further questions you may have during the discussion period."}]

Author rebuttal:
We thank the reviewers for the useful comments and questions. The points raised in the reviews led us to run several new experiments and to clarify certain aspects of our manuscript. We believe that these changes have significantly improved our paper. We summarize below the major changes and reply individually to each reviewer in separate threads.

**Detailed discussion of SnAp-1 and e-prop.** Thanks to the reviewers we realized that we did not explain in sufficient detail the relationship between SnAp-1 [15] and e-prop [13] and our learning rule. While both rules are definitely closely related to ours (and we will stress this accordingly), we will now explain the two innovations introduced in our paper: (1) the extension to the complex domain, and (2) our hybrid gradient computation strategy that leverages spatial backpropagation (together with forward sensitivity recursions) to assign credit over multiple recurrent layers. In particular, a discussion of (2) will be added to the next version of the paper. As we explain below, this innovation enables sending detailed spatial credit assignment information over networks with multiple layers.

For a network comprising a single layer of IRMs, SnAp-1, e-prop, our rule, and in fact exact RTRL, all become identical. However, the important multilayer case is handled differently. On the one hand, SnAp-$k$ uses the standard RTRL gradient decomposition $\nabla_\theta L=\sum_t \frac{\partial L_t}{\partial h_t}\frac{dh_t}{d\theta}$, carrying forward in time an approximation of $\frac{\mathrm{d} h_t}{\mathrm{d} \theta}$ that improves with increasing $k$. The partial derivative $\partial L_t / \partial h_t$ is identically zero for neurons that are not directly connected to the output loss; for hidden recurrent neurons $l$ layers away from the output to receive a learning signal, $k$ has to be at least $l+1$. Thus, for networks with deep recurrent neurons, SnAp-1 would only learn the last recurrent layer. Adding skip connections would only ameliorate this problem, as SnAp-1 would only broadcast a global error through that pathway alone. Such differences do not matter for the shallow networks the SnAp paper focuses on, but become important for us, as we move to deep networks. On the other hand, e-prop starts from the same decomposition as us, $\nabla_\theta L = \sum_t \frac{dL_t}{d h_t}\frac{dh_t}{d\theta}$, also noting that $\frac{d L_t}{dh_t}$ cannot be computed causally. The e-prop rule is then derived by approximating $\frac{d L_t}{dh_t}$ by $\frac{\partial L_t}{\partial h_t}$, which then leads to the same situation as in SnAp-1. We, instead, opted for approximating $\frac{d L_t}{dh_t}$ using spatial backpropagation, enabling credit assignment over multiple IRM layers, and therefore sending detailed errors to models with hidden, deep recurrent neurons. We will add this discussion to the next version of our paper.

**Linear RNN results on sequential CIFAR**. We ran a new set of experiments on sCIFAR, replacing LRUs by dense linear RNN layers, cf. pdf. We find that online-learned complex diagonal networks greatly outperform their dense counterparts.

**Addition of GRU baselines.** We further investigated parameter-matched (wide) single-layer GRU networks on the copy task, essentially the architecture used in the SnAp paper [15], as well as multilayer GRU networks, cf. pdf. We ran these experiments to investigate the impact of depth on approximate RTRL in another popular, powerful architecture studied in previous work [9,15]. To train such networks online, we used SnAp-1 for single-layer GRUs, and our hybrid combination of spatial backpropagation with forward sensitivities for multilayer GRUs, cf. point on SnAp-1/e-prop. We find that neither shallow nor multilayer GRUs match the performance of LRU networks trained with our online learning rule. Moreover, only BPTT can take advantage of multiple GRU layers, whereas online GRU learning stagnates at single-layer performance. This again confirms the importance of the IRM design motif in enabling accurate online gradient estimation. We are currently running similar experiments on the sCIFAR benchmark and will add the results to the next version of the paper.

**New IMDB LRA benchmark.** We ran one more benchmark from the LRA suite, IMDB, to confirm that our trend of results remains (cf. pdf).

**Overall improvement in results.** We noticed some bugs in our code and brought some additional improvements after the submission. We here summarize the changes we made and the impact they have on our results:

- We were initializing the $D$ matrix without proper normalization; we now normalize it. We  observed that, thanks to this change, the explosion phenomenon in linear RNNs no longer appears.
- Beforehand, we ignored the normalization factor $\gamma$ in the backward pass. We fixed this.
- Previously, for all experiments in the LRA benchmark, the prediction for time step t was created by taking the softmax of the current encoding. We now change it to be the softmax of the cumulative mean of all previous encodings, and block gradients for all previous time steps to ensure that our learning rule remains causal. This way, we get closer to the non-causal mean-pooling usually used.

These changes led to an overall improvement in all methods, particularly the online & LRU ones, c.f. pdf.

Interestingly, we additionally observed that it is now possible to reach a 0 training loss on the copy task when training a 4-layer deep LRU network with our learning rule for 250 epochs. This goes against the result that uniformly-biased gradient descent doesn't converge to a global optimum (D’Aspremont, SIAM Journal on Optimization, 2008) and may suggest that the bias of our learning rule has some special structure.

We also retuned hyperparameters (learning rate and weight decay) by performing separate grid searches for every method; details will be shared in the next version of the supplement.

Meta-review: This paper introduces an online learning algorithm for recurrent neural networks, particularly targeting the learning of long-range dependencies. In this regards, 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. All of the reviewers seem to be on the positive side. We thank the authors for providing a detailed response to reviewer concerns. Please include the extended discussion with prior works (i.e. SnAp-1 and e-prop) and all the additional experimental results in the final version of the paper.
Decision: Accept (poster)