Practical Real Time Recurrent Learning with a Sparse Approximation
Authors: Jacob Menick
Erich Elsen
Utku Evci
Simon Osindero
Karen Simonyan
Alex Graves
Venue: ICLR 2021 Spotlight (2021)
Keywords: recurrent neural networks
backpropagation
biologically plausible
forward mode
real time recurrent learning
rtrl
bptt

Abstract: Recurrent neural networks are usually trained with backpropagation through time, which requires storing a complete history of network states, and prohibits updating the weights "online" (after every timestep). Real Time Recurrent Learning (RTRL) eliminates the need for history storage and allows for online weight updates, but does so at the expense of computational costs that are quartic in the state size. This renders RTRL training intractable for all but the smallest networks, even ones that are made highly sparse.
We introduce the Sparse n-step Approximation (SnAp) to the RTRL influence matrix. SnAp only tracks the influence of a parameter on hidden units that are reached by the computation graph within $n$ timesteps of the recurrent core. SnAp with $n=1$ is no more expensive than backpropagation but allows training on arbitrarily long sequences. We find that it substantially outperforms other RTRL approximations with comparable costs such as Unbiased Online Recurrent Optimization. For highly sparse networks, SnAp with $n=2$ remains tractable and can outperform backpropagation through time in terms of learning speed when updates are done online.

Published as a conference paper at ICLR 2021
PRACTICAL REAL TIME RECURRENT LEARNING WITH A SPARSE APPROXIMATION TO THE JACOBIAN
Jacob Menick DeepMind
Erich Elsen" DeepMind eriche@google.com
University College London jmenick com
Utku Evci Google
Simon Osindero DeepMind
Karen Simonyan DeepMind
Alex Graves DeepMind
ABSTRACT
Recurrent neural networks are usually trained with backpropagation through time, which requires storing complete history of network states, and prohibits updating the weights 'online' (after every timestep). Real Time Recurrent Learning (RTRL) eliminates the need for history storage and allows for online weight updates, but does so at the expense of computational costs that are quartic in the state size. This renders RTRL training intractable for all but the smallest networks, are made highly sparse. We introduce the Sparse n-step Approximation (SnAp) the RTRL influence matrix. SnAp only tracks the influence of parameter hidden units that are reached by the computation graph within n timesteps of the recurrent core. SnAp with n is more expensive than backpropagation but allows training on arbitrarily long sequences. We find that it substantially outperforms other RTRL approximations with comparable costs such Unbiased Online Recurrent Optimization. For highly sparse networks, SnAp with n 2 remains tractable and can outperform backpropagation through time terms learning speed when updates are done online.
ones that
INTRODUCTION
Recurrent neural networks (RNNs) have been successfully applied to wide range of sequence learning tasks, including text-to-speech (Kalchbrenner et al., 2018), language modeling (Dai al., 2019), automatic speech recognition (Amodei et al. (016). translation (Chen et al. 2018) and reinforcement learning (Espeholt et al., 2018). RNNs have greatly benefited from advances in computational hardware, dataset sizes, and model architectures. However, the algorithm used to compute their gradients almost all practical applications has not changed since the introduction of Pack-Propag Through Time (BPTT). The key limitation of BPIT that the entire state history must be stored, meaning that the memory cost grows linearly with the sequence length. For sequences too long to fit in memory, as often occurs in domains such as language modelling long reinforcement learning episodes, truncated BPTT (TBPTT) (Williams & Peng 1990) can be used. Unfortunately the truncation length used by TBPTT also limits the duration over which temporal structure can be realiably learned.
Forward-mode differentiation, or Real-Time Recurrent Learning (RTRL) as is called when applied to RNNs (Williams & Zipser 1989). solves some of these problems. It doesn't require storage of any past network states, can theoretically learn dependencies of any length and can be used to update parameters at any desired frequency, including every step (i.e. fully online). However, its fixed storage requirements are O(k [0]). where the state size and [0 is the number of parameters 0 in the core. Perhaps even more daunting, the computation it requires is O(k2 10]). This makes impractical for even modestly sized networks. The advantages of RTRL have led to search for more efficient approximations that retain its desirable properties, whilst reducing its computational and memory costs. One recent line of work introduces unbiased, but noisy approximations the influence update. Unbiased Online Recurrent Optimization (UORO) (Tallec)

---

Published as a conference paper at ICLR 2021
& Ollivier 2018) is approximation with the cost TBPIT - O((0l) however its gradient estimate is severely noisy (Cooijmans & Martens 2019) and its performance has practice proved worse than TBPTT (Mujika et al.) 2018). Less noisy approximations with better accuracy variety of problems include both Kronecker Factored RTRL (KF-RTRI) (Mujika et al.) (018)) and Optimal Kronecker-Sum Approximation (OK) (Benzing al.! 2019). However, both increase the computational costs to (k))).
The last few years have also seen resurgence of interest in sparse neural networks both their properties (Frankle & Carbin 2019) and new methods for training them (Evci et al. 2019). A number of works have noted their theoretical and practical efficiency gains over dense networks (Zhu & Gupta 2018 Narang et al.
2017; Elsen et al. (019). Of particular interest is the finding that scaling the state size of an RNN while keeping the number of parameters constant leads to increased performance (Kalchbrenner et al. 2018).
In this work we introduce new sparse approximation to the RTRL influence matrix. The approx- imation is biased but not stochastic. Rather than tracking the full influence matrix, we propose to track only the influence of parameter on neurons that are affected by it within n steps of the RNN. increases. The cost of the algorithm
The algorithm is strictly less biased but more expensive the Jacobian the recurrent cell. We study the
controlled by n and the amount of sparsity nature of this bias in Appendix C. Larger can be coupled with concomitantly higher sparsity to keep the cost fixed. This enables us to achieve the benefits of RTRL with a computational cost per step comparable in theory to BPTT. The approximation approaches full RTRL increases. Our contributions are as follows:
We propose SnAp- practical approximation RTRL, which is is applicable to both dense and sparse RNNs, and is based on the sparsification of the influence matrix.
We show that parameter sparsity in RNNs reduces the costs of RTRL in general and SnAp in particular.
We carry out experiments on both wollworld and synthetic tasks, and demonstrate that the SnAp approximation: (1) works well for language modeling compared to the exact unapproximated gradient; (2) admits learning temporal dependencies on a synthetic copy task and (3) can learn faster than BPTT when fully online.
2 BACKGROUND
We consider recurrent networks whose dynamics are governed by h4 = =ooo-oo fo where ha TR the state, 22 E R is an input, and f E IR? are the network parameters. It assumed that each step & E {1. 7, the state is mapped to output y/ (h+)), and the network receives loss (e. vi) The system optimizes the total loss L Σ L, with respect to parameters by following
the gradient VoL. The standard way compute this gradient is BPTT rumning backpropagation on the computation graph "unrolled time" over number of steps T::
I
OL Oh, The 00,
Oc Oh aLi
Thu
VoL Σ
Σ
0he+1 Oh,
Th.
00,
The recursive expansion Sh. nonstandard notation 6 refers to the copy of the parameters used at time but the weights are shared for timesteps and the gradient adds over all copies.
0c ac Ohet1 + 8C. is the backpropagation rule. The slightly ah+t1 8h, Sh;
2.1 REAL TIME RECURRENT LEARNING (RTRL)
Real Time Recurrent Learning Williams & Zipser 1989) computes the gradient as:
T 0c, Oh.
T dL. Ohg
Th. δly-1
VeL
+
(2)
Oh 30
Oh.
00,
ah,-1 30
2

---

Published as a conference paper at ICLR 2021
This can be viewed as iterative algorithm, updating &h, from the intermediate quantity 8h. simplify equation 2 we introduce the following notation: have J, = 0h, 86 It = 89,
To
80
Sh, and D; = ah.
8h.
stands for "Jacobian", I for "immediate Jacobian". and D for "dynamics". We sometimes refer to J as the "influence matrix". The recursion can be rewritten Jj 4. D,J,-1-
Cost analysis Jg is matrix in R which can be on the order of gigabytes for even modestly sized RNNs. Furthermore, performing the operation D involves multiplying a k x matrix by a k |0] matrix each timestep. That requires (8] times more computation than the forward pass of the RNN core. To make explicit just how expensive RTRL is this is a factor of roughly one million for vanilla RNN with 1000 hidden units.
2.2 TRUNCATED RTRL AND STALE JACOBIANS
In analogy to Truncated BPTT. one can consider performing a gradient update partway through training sequence (at time t) but still passing forward a stale state and stale influence Jacobian Je rather than resetting both to zero after the update. This enables more frequent weight updating at the cost of staleness bias. The Jacobian Jr becomes "stale" because it tracks the sensitivity of the state to old parameters. Experiments (section 5.2) show that this tradeoff can be favourable toward more frequent updates in terms of data efficiency. In fact, much of the RTRL literature assumes that the parameters are updated at every step ("fully online") and that the influence Jacobian is never reset, at least until the start of a new sequence. All truncated BPTT experiments in our paper pass forward stale state if an update is done before the end of the sequence.
2.3 SPARSITY IN RNNs
One of the early explorations of sparsity in the parameters of RNNs (i.e. many entries of are exactly zero) was Ström (1997), where one-shot pruning based on weight magnitude with subsequent retraining was employed in a speech recognition task. The current standard approach to inducing sparsity in RNNs (Zhu & Gupta 2018) remains similar, except that magnitude based pruning happens slowly over the course of training so that no retraining is required.
Kalchbrenner et al. (2018) discovered a powerful property of sparse RNNs in the course of investi- gating them for text-to-speech. for a constant parameter and flop budget sparser RNNs have more capacity per parameter than dense ones. This property has so far only been shown to hold when the sparsity pattern is adapted during training (in this case, with pruning). Note that parameter parity is achieved by simultaneously increasing the RNN state size and the degree of sparsity. This suggests that training large sparse RNNs could yield powerful sequence models, but the memory required to store the history of (now much larger) states required for BPTT becomes prohibitive for long sequences. In this paper, we simplicity. In particular, we pick uniformly at random which indices weight matrices to force to zero and hold this sparsity pattern constant over the course of training.
fixed sparsity pattern rather than pruning (see Appendix B), for
3 THE SPARSE N-STEP APPROXIMATION (SNAp)
Our main contribution in this work is the development of an approximation to RTRL called the Sparse n-Step Approximation (SnAp) which reduces RTRL's computational requirements substantially.
SnAp imposes sparsity on J even though it is in general dense. We choose the sparsity pattern to be the locations that are non-zero after n steps of the RNN (Figure J. We also choose to use the same pattern for all steps, though this is not requirement. This means that the sparsity pattern of J/ is known and can be used to reduce the amount of computation in the product D See Figure 2 for visualization of the process. The costs of the resulting methods note an alternative strategy would be to perform the full multiplication of D.J 1 and then only keep the top-k values. This would reduce the bias of the approximation but increase its cost.
compared in Table I1 We
More formally, we adopt the following approximation for all l:
{
(Jeys if (0:), influences hidden unit (he+n);
(J))ss
otherwise
3

---

Published as a conference paper at ICLR 2021
SnAp dense (bottom) and sparse (top) graphs: As the figure proceeds the right we propagate the influence of the red connection on the nodes j of the graph through further RNN steps. Nodes are colored in pink they are influenced on or before that step. The entry J is kept node is colored pink, but all other entries in row are set to zero. When one node is influenced. the dense case the red connection influences all nodes when n >=
Figure 1:
in both cases only
3.1 SPARSE ONE-STEP APPROXIMATION (SNAr-1)
Even for fully dense RNN, each parameter will in the usual case only immediately influence the single hidden unit it is directly connected to. This means that the immediate Jacobian I tends to be extremely sparse. For example, Vanilla RNN will have only one nonzero element per column, which is a sparsity level of k-I Storing only the nonzero elements of I, already saves significant amount of memory without making any approximations: is the same shape as the daunting Je matrix whereas the nonzero values are the same size as 0.
I can become more dense in architectures (such as GRU and LSTM) which involve the composition of parameterised layers within single core step (see Appendix A for in-depth discussion of the effect of gating architectures on Jacobian sparsity). In the Sparse One-Step Approximation, we only keep entries in J, if they nonzero in 4. After just two RNN steps, given parameter has influenced every unit of the state through its intermediate influence on other units. Thus only SnAp with is efficient for dense RNNs because dense networks SnAp-2 already reduces to full RTRL. (N.b.: SnAp-1 is also applicable to sparse networks.) Figure depicts the sparse structure of the influence parameter for both sparse and fully dense cases.
does not result in any sparsity in J; for
SnAp-1 is effectively diagonal, in the sense that the effect of parameter j on hidden unit maintained throughout time, but ignoring the indirect effect of parameter
unit i via paths through other units Y' More formally, is useful to define u(j) as the one component the state h2 connected directly to the parameter j (which has at the other end of the connection some other entry i' within ht-1 or r.). Let i w(j). The imposition of the step sparsity pattern means only the entry in row will be kept for column j in Jr. Inspecting the update for this particular entry, we have
(J));= (T). + Σ (De)im (Je-1) (Ta)sj + (D.)a(Je-1))
(3)
The equality follows from the assumption that (J:-1)m) 0 m Diagonal entries in D, are thus crucial for this approximation to be expressive, such as those arising from skip connections.
3.2 OPTIMIZATIONS FOR FULL RTRL WITH SPARSE NETWORKS
When the RNN is sparse, the costs of even full (unapproximated) RTRL can be alleviated to surprising extent; we save computation proportional to a factor of the sparsity squared. Assume proportion of the entries in both 0 and D, are equal to zero and refer to this number as "the level of sparsity in the RNN". For convenience, := s. With a Vanilla RNN, this correspondence between parameter sparsity and dynamics sparsity holds exactly. For popular gating architectures such as GRU and LSTM the relationship is more complicated so we include empirical measurements of the computational cost in FLOPS (Table 2 in addition to the theoretical calculations here. More
4

---

Published as a conference paper at ICLR 2021
Method
memory
time per step
BPTT
Tk + p k+
k² +
(5)
UORO
k² + p
RTRL
k + kip
k² + h2p
(4)
Sparse BPTT
Tk + dp
d(k2 + p)
Sparse RTRL
k + dkp
d(k² + dk²p)
SnAp-1
k ++ dp
d(k2 + p)
(6)
SnAp-2
K: dekp
d(k2 + d2k2p)
Figure 2: Depiction of RTRL, RTRL with spar- sity and SnAp. White indicates zeros. (a)
Table I: Computational costs (up to a proportion- ality constant) of gradient calculation methods for dense and sparse RNNs. Below 'T' refers to the se- quence length, the number of hidden units, p the number of dense recurrent parameters, 8 the level sparsity, and d compute cost is for going forward and the second term is for either going backward or updating the influence matrix.
++DDJiL (b) + D:Ji-1 when W is sparse (c) T + D.Ji-1 (d) SnAp-2 (e) SnAp-1. Rose colored squares are non-7ero in Dr but not used in updating J.
s. The first term of the
complex recurrent architectures involving attention (Rae al. 2016) would require an independent mechanism for inducing sparsity in Da; we leave this direction to future work and assume in the remainder of this derivation that sparsity
corresponds to sparsity in D₃-
If the sparsity level of 0 is then so is the sparsity in J because the columns corresponding to parameters which are clamped to zero have no effect on the gradient computation. We may extract the columns of J containing nonzero parameters into a new dense matrix J used place of everywhere with no effect on the gradient computation. We make the same optimization for J and use the dense matrix I, in its place, leaving us with the update rule (depicted in Figure 2):
J, D.J.
These optimizations taken together reduce the storage requirements by 1 size of J) and the computational requirements by t because D, in the sparse matrix multiplication D.Jo-1 has density d, saving extra factor of
a (because J is d times the
3.3 SPARSE N STEP APPROXIMATION (SNAP-N)
Even when D, is sparse, the computation "graph" linking nodes (neurons) in the hidden state over time should still be connected, meaning that J eventually becomes fully dense because after enough iterations every (non-zers zero) parameter will have influenced every hidden unit in the state. Thus sparse approximations are still available in this setting and indeed required to obtain efficient algorithm. For sparse RNNs, SnAp simply imposes additional sparsity on J, rather than J,. SnAp-N for N both strictly less biased and strictly more expensive, but its costs can be reduced by increasing the degree of sparsity in the RNN. SnAp-2 is comparable with UORO and SnAp-I if the sparsity of the RNN is increased so that d < n 3 e.g. 99% or higher sparsity for a 1000-unit Vanilla RNN. If this level of sparsity is surprising, the reader is encouraged to see our experiments in Appendix B.
4 RELATED WORK
SnAp-1 is actually similar to the original algorithm used to train LSTM (Hochreiter & Schmidhuber) 1997). which employed doward-mode differentiation to maintain the sensitivity to each parameter of single cell unit, over all time. This exposition was expressed in terms coupled the LSTM architecture whereas our formulation is general. SnAp-I was also described in (Bellec et al.) 2019) 1prop-1. The exposition in that paper goes into great depth regarding its biological plausibility and
5

---

Published as a conference paper at ICLR 2021
relation to spiking neural networks and may be somewhat unfamiliar to readers from pure machine learning background. The -1 postfix in eprop refers to it being the first of three present algorithms, not the number of connections as in SnAp. Biological plausibility of RTRL variants has also been studied in (Zenke & Neftci 2021). An idea similar to SnAp was also proposed in (Bradbury) 1997). aiming overcome poor local minima during optimization.
Random Feedback Local Online (Murray 2019) (RFLO) amounts to accumulating I terms in equation whilst ignoring the product D.J,-I. It admits an efficient implementation through operating on Ie as in section 3.2 but is strictly more biased than the approximations considered in this work and performs worse in our experiments. The original paper also used random matrices to propagate errors backward, thus avoiding the weight transport problem (Lillicrap et al. 2016). However, for a fair comparison, our re- re-implementation uses the same weights that are used for the forward pass, as in standard backpropagation. As mentioned in section stochastic approximations to the influence matrix are alternative to the methods developed in our work, but suffer from noise in the gradient estimator (Cooijmans & Martens 2019). A fruitful line of research focuses on reducing this noise (Cooijmans & Martens 2019), Muujika et al. 2018), (Benzing al. 2019).
is possible to reduce the storage requirements of TBPTT using a technique known as "gradient checkpointing" or "rematerialization,, This reduces the memory requirements of backpropagation by recomputing states rather than storing them. First introduced in Griewank & Walther (2000) and later applied specifically to RNNS in Gruslys al. (2016), these methods are not compatible with the fully online setting where T may be arbitrarily large as even the optimally small amount of re-computation can be prohibitive. For reasonably sized T, however, rematerialization is a straightforward and effective way to reduce the memory requirements of TBPTT, especially if the forward pass can be computed quickly.
5 EXPERIMENTS
We include experimental results on the real world language-modelling task WikiText103 (Merity et ( and the synthetic 'Copy' task (Graves et al. (0166) of simply repeating an observed binary string. Whilst the first is important for demonstrating that our methods can be used for real, practical problems, language modelling doesn't directly measure model's s ability to learn structure that spans long time horizons. The Copy task, however, allows us to parameterize exactly the temporal distance over which structure is present in the data. In terms of, respectively, task complexity and RNN state size (up to 1024) these investigations are considerably more "large-scale" than much of the RTRL literature.
5.1 WIKITEXT103
All of our WikiTextt033 experiments tokenize at the character (byte) level and use SGD to optimize the log-likelihood of the data. We use the Adam optimizer (Kingma & Ba 2014) with default hyper- parameters 31 = 0.9, 32 = 0.999, and e = le We train on randomly cropped sequences of length 128 sampled uniformly with replacement and do not propagate state across the end-of-sequence boundary (i.e. no truncation). Results are reported on the standard validation set.
5.1.1 LANGUAGE MODELLING WITH DENSE RNNs: SNAP1
In this section, we refrain from performing a weight update until the end of a training sequence (see section 2.2 so that BPTT is the gold standard benchmark for performance, assuming the gradient is the optimal descent direction. The architecture is Gated Recurrent Unit (GRU) network (Cho) cet al. 2014) with 128 recurrent units and a one-layer readout MLP mapping to 1024 hidden relu units before the final 256-unit softmax layer. The embedding matrix is not shared between the input and output. All weights are initialized from a truncated normal distribution with standard deviation equal to the inverse square root of the fan in. Learning curves in Figure 33 (Left) show that SnAp-I outperforms RFLO and UORO, and that in this setting UORO fails to match the surprisingly strong baseline of not training the recurrent parameters at all and instead leaving them at their randomly initialized value. This random bascline is closely related to the Echo-State network (Jaeger) 2001). and the strong readout network is intended to help keep the comparison this baseline fair.
5.1.2 LANGUAGE MODELING WITH SPARSE RNNs: SNAP-1 AND SNAP-2
Here we use the same architecture as in section 5.1.I except that we introduce 75% sparsity into the weights of the GRU, in particular the weight matrices (more sparsity levels are considered in

---

Published as a conference paper at ICLR 2021
Erain readiout only
L000
Smmpp2
train reddiau only LiCo
5mhp-2
Dense GRU
75% Sparse GRU
18
teratts Figure 3: Left: Comparing various RTRL approximations based upon their ability to train dense GRU network to do character-level language modelling, On the y-axis is Negative Log Likelihood. Right: Same left with 75% parameter-sparsity.
teration
later experiments). Biases are always kept fully dense. order to induce sparsity, we generate sparsity pattern uniformly at random and fix it throughout training. As would be expected because is strictly less biased, Figure (Right) shows that SnAp-2 outperforms SnAp-1 but only slightly. Furthermore, both closely match the (gold-standard) accuracy of model trained with BPTT. Table showws that SnAp-2 actually costs about 600x more FLOPs than BPTT/SnAp- at 75% sparsity, but higher sparsity substantially reduces FLOPs. It's unclear exactly how the cost compares UORO, which though O((0) does have constant factors required for e.g. random number generation, and additional overheads when approximations rank higher than one.
5.2 COPY TASK
Our experiments on the Copy task (Graves et al. 2016) aim to investigate the ability of the proposed sparse RTRL approximations to learn about temporal structure. In this synthetic task, a sequence of bits 6, E (0, 1} is presented one at time, and then special token is presented, denoting the end of the input pattern. Subsequently, the network receives a series of special tokens indicating that an output desired, at which time it must output, token time, the same binary string it received as input. Unlike language modelling, there is nothing going on in this problem except for (simple) temporal structure over known temporal distance: the length of the input sequence.
We follow Mujiia et af. 2018) and adopt a curriculum-learning approach over the length of sequences to be copied, starting with T. 1. When the average bits per character of training minibatch drops below 0.15, we increment L by one. We sample the length of target sequences uniformly between [max(L 5, 1), L] in previous work. We measure performance versus 'data- time', i.e. we give each algorithm time budget in units of the cumulative number of tokens seen throughout training. consequence of this scheme that full BPTT is no longer an upper bound on performance because, for example, updating once on a sequence of length 10 with the true gradient may yield slower learning than updating twice on two consecutive sequences of length 5, with truncation.
In these experiments we examine SnAp performance for multiple sparsity levels and recurrent archi- tectures including Vanilla RNNs, GRU, and LSTM. Table 2 includes the architectural details. The sparsity pattern is again chosen uniformly at random. As result, comparison between sparsity levels discouraged. For each configuration and compare average performance over three seeds with the best chosen learning rate (all methods performed best with learning rate 10-3). The minibatch size 16. We train with either full unrolls or truncation with = 1. This means that the RTRL approximations update the network weights at every timestep and persist the RNN state along with a stale Jacobian (see section 2.2
sweep over learning rates in {10-2.. 10 10 10-3.5 10 10-4)
Fully online training One striking observation is that Truncated BPTT completely fails to learn temporal structure in the fully online (T = 1) regime. Interestingly. the SnAp methods perform better with more frequent updates. Compare solid versus dotted lines of the same color in Figure Fully online SnAp-2 and SnAp-3 mostly outperform or match BPTT for training LSTM and GRU architectures despite the "staleness" noted in Section 2.2 We attribute this to the hypothesis

---

Published as a conference paper at ICLR 2021
advanced in the RTRL literature that Jacobian staleness can be mitigated with small learning rates but leave more thorough investigation of this phenomenon to future work.
Bias versus computational expense For SnAp there is tradeoff between the biasedness of the approximation and the computational costs of the algorithm. We see that correspondingly. SnAp-1 outperformed by SnAp-2, which is in turn outperformed by SnAp-3 3 in the Copy experiments. The RFLO baseline is even more biased than SnAp-1, but both methods have comparable costs. SnAp-1 significantly outperforms RFLO in all of our experiments. The nature of the bias introduced by SnAp is investigated in Appendix C.
Here we augment the asymptotic cost calculations from Table with empirical measurements of the FLOPs, broken out by architecture and sparsity level in Table 2 Gating architectures require high degree of parameter sparsity in order keep a commensurate amount of of Jacobian sparsity due to the increase in density brought about by composing linear maps with different sparsity patterns (see Appendix A). For instance, the 75% sparse GRU considered in the experiments from Section 5.1.2 lead to SnAp-2 parameter Jacobian that is only 70.88% sparse. With SnAp-3 it becomes much less sparse - only 50%. This may partly explain why SnAp performs best compared to BPTT in the LSTM case (Figure + though it still significantly outperforms BPTT in the high sparsity regime when SnAp-2 becomes practical. Also, LSTM twice as costly to train with RTRL-like algorithms because it has two components to its state, requiring the maintenance of twice as many jacobians and the performance of twice as many jacobian multiplications (Fquations 3/5). For 75% sparse LSTM, the SnAp-2 Jacobian is much denser at 38.5% sparsity and SnAp-3 has essentially reached full density (so it is as costly as RTRL).
Empirical FLOPs requirements
Figure also shows that for Vanilla RNNs, increasing n improves performance, but SnAp does outperform BPTT with this architecture. In summary, Increasing n improves performance but costs more FLOPs.
Architecture
Vanilla
GRU
LSTM
Number of Units
128
256
512
128
256
512
128
256
512
Param. Sparsity
75.0%
93.8%
98.4%
75%
93.8%
98.4%
75.0%
93.8%
98.4%
SnAp-2 Sparsity
83.0%
95.6%
98.9%
70.9%
91.1%
97.8%
38.5%
79.9%
95.1%
SnAp-3 Sparsity
33.3%
59.2%
92.8%
50.0%
52.5%
71.6%
2.4%
5.9%
38.7%
SnAp-1 BPTT
1x
1x
1x
1x
1x
1x
2x
2x
2x
SnAp-2 BPTT
349x
90.4x
22.1x
597x
183x
44.8x
2518x
824.8x
200.
SnAp-3 BPTT
1365x
835.8x
147.5x
1024x
972x
582x
3996x
3855x
2513x
SnAp-2 vs RTRL
0.17x
0.044x
0.011x
0.291x
0.089x
0.022x
0.615x
0.201x
0.049x
Table 2: Empirical computational costs of SnAp, determined by the sparsity level in the Jacobians.
The "X vs BPTT" rows express the FLOPS requirements of X as multiple of BPTT training FLOPs. The "SnAp-2 vs RTRL" row shows the FLOPS requirements of SnAp-2 as a multiple of those required by optimized Sparse RTRL (section 3.2 Lower is better for all of these entries.
CONCLUSION
We have shown how sparse operations can make form of dense parameter Jacobians with approximate sparse ones. We introduced SnAp-1, an efficient RTRL approximation which outperforms comparably-expensive alternatives on popular language- modeling benchmark. We also developed higher orders of SnAp including SnAp-2 and SnAp-3, approximations tailor-made for sparse RNNs which can be efficient in the regime of high parameter sparsity, and showed that they can learn temporal structure considerably faster than even full BPTT.
especially when replacing
Our results suggest that training very large, sparse RNNs could be promising path toward more powerful sequence models trained on arbitrarily long sequences. This may prove useful for modelling whole documents such as articles or even books, or reinforcement learning agents which learn over an entire lifetime rather than the brief episodes which are common today.
few obstacles stand the way scaling up our methods further:
The need for highhpeerfomiig sparse training strategy that does not require dense gradient information.
8

---

Published as a conference paper at ICLR 2021
algorithm
truncetion
BPTT
SnAp1
SnAp2
SnAp3
rflo
mome no fruncation
0.0%
75.0% sparse
93.8% sparse
sparse
curriculum max
2333000 4000000
2006c00
4353050
SECOCC6
2039930
4000000
data time
Figure 4: Copy task results by sparsity and architecture. Solid lines indicate that updates are done fully online (at every step). Dotted lines indicate that updates are done at the end of sequence. See the heading "Fully online training" within section 5.2 for more details.
Sparsity support in both software and hardware that enables better realization of the theo- retical efficiency gains of sparse operations.
It may also be fruitful to further develop our methods for hybrid models combining recurrence and attention (Dai et al. 2019 Rae et al. 2016) or even feedforward architectures with tied weights (Lan al. 2019) Dehghani et al. 2018).
REFERENCES
Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, and et al. Deep speech 2: End-to-end speech recognition in english and mandarin. In Proceedings of the 33rd Interna- tional Conference on International Conference on Machine Learning Volume 48, ICML' 16, pp- 173-182. JMLR.org, 2016.
Guillaume Bellec, Franz Scherr, Elias Hajek, Darjan Salaj, Robert Legenstein, and Wolfgang Maass. Biologically inspired alternatives to backpropagation through time for learning in recurrent neural nets. arXiv.org e-Print archive, 2019:1-37, 1 2019.
Frederik Benzing, Marcelo Matheus Gauy, Asier Mujika, Anders Martinsson, and Angelika Steger. Optimal kronecker-sum approximation of real time recurrent learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 604-613, PMLR, 2019. URL httphhttp//prrcceeiingg mlr. press/v97/beezingg1a html
David Bradbury, A methodology for the development of recurrent networks for sequence processing wwwp................ uk/66146//
tasks. October 1997. URL http:://tt/// open. ac. ac.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclau- rin, and Skye Wanderman-Milne. JAX: composable transformations of Python+NumPy programs, 2018. htwllapp://ggttuub..oo/ooo//////
Mia Xu Chen, Orhan Firat, Ankur Bapna, Melvin Johnson, Wolfgang Macherey, George Foster, Llion Jones, Mike Schuster, Noam Shazeer, Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz

---

doi: 10.1145/347837.447888 Published as a conference paper at ICLR 2021
Kaiser, Zhifeng Chen, Yonghui Wu, and Macduff Hughes. The best of both worlds: Combining recent advances in neural machine translation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 76-86, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.18653/v 1/P1// 1008.
http:::ps: /www. www.wwwwwbbb....... www.wwwwwwwwwa.w...e..... htt.//bb..ogg.aatooooo////////// 1068.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1734, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.31 1/D14-11999 URL https:://///
anthology/D14 1179
Tim Cooijmans and James Martens, On the variance of unbiased online recurrent optimization. CoRR, abs/ abs//992.00245, 2019. UtL.tttpp//axxivorr/// wrwp:rgggaaa/.../// 02405
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Lc, and Ruslan Salakhutdinov. Transformer-Xe XL: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. Italy, July 2019. Association for Computational Linguistics. doi: 10. 10.11 1285. URL https: //ww://wwww awwwwb..wcc.cc... www.:orgggaagggogoogoooo
Florence,
1285
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. CoRR, abs/ 807 03819, 2018, URLhttp://arxiv.orgg wtwpg//aaa///0//// 03819
ConwNets. Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast Conveets AxXiv, 2019.
URL httpt::/axxti....o/tta http://axxvvoogg////////
Jesse Engel.
Optimizing rmns with differentiable graphs. UWL.atpss/svaal..gibb...oo graphs/ Accessed: 2020-06-02.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. IMPALA: Scalable Distributed Deep-RI. with Importance Weighted Actor-Learner Architectures. In Proceedings of the International Conference on Machine Learning (ICML), 2018
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the Lottery: Making All Tickets Winners, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019. W www.:eeetoooeae.e (ato:oorrmmiidd1rd--dd b33ccF7
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwiñska, Sergio Gómez Colmenarejo. Edward Grefenstette, Tiago Ramalho, John Agapiou, AdriaPuigdomènech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626): 471 2016. doi: 10. 10.1038/nturee20001
https://:: org/10/..1000 1038/nature201000
Andreas Griewank and Andrea Walther. Algorithm 799: Revolve: An implementation of check- pointing for the reverse or adjoint mode of computational differentiation. ACM Trans. Math. Softw.. 26(1):19-45, March 2000. ISSN 0098-3500.
URL
https://doi. becooi.org///
orgoorg//100 10. 1145/347837 347846
Audrunas Gruslys, Remi Munos, Ivo Danihelka, Marc Lanctot, and Alex Graves. Memory- efficient backpropagation through time. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 4125-4133. Curran Associates, Inc., 2016. URL lhttp://papers: http://pppers..iis.com www.. hwps.cc/pappr.. 6221-memory- effi 1e1l-memrr---ffiiientt wwtpe//fiiieeetaacprppaaaaaaaaae backpooaagatiioooo-coooooo whwpappaaaaaaaaaoooooooooaaaoeae through-time
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 98):1733-
1780, November 1997. ISSN 0899-7667. doi: 10.1162/neco.1997
URL htttp://dx.
doi.org/11 100 162 2t/62//eeee 199..9...999...........
10

---

Published as a conference paper at ICLR 2021
Herbert Jaeger. The "echo state" approach analysing and training recurrent neural networks. EMDDRepprt 148, German National Research Institute for Computer Science, 01 2001.
Nal Kalchbrenner, Erich Elsen, Karen Simonyan, Seb Noury, Norman Casagrande, Edward Lockhart, Florian Stimberg, Aäron van den Oord, Sander Dieleman, and Koray Kavukcuoglu. Efficient Neu- ral Audio Synthesis. Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 2415-2424, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL URLhttp: //arxiv. .rrgii.orr//ooooo ooro/org/ss... hagg//b///// abs//412. 1412. 6980) cite wrxiv:1412.66:: 4rxxv11412268800mmmmm m.880mmmmmtn Published as conference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, Radu Soricut, Google Research, and Mailton de Carvalho. Albert: A lite bert for self-supervised learning of language representations. 10 2019.
Timothy P Lillicrap, Daniel Cownden, Douglas B Tweed, and Colin J Akerman. Random synaptic feedback weights support error backpropagation for deep learning. Nature communications, 7(1):
1-10, 2016.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: //openreview httpriiwwweeeeeeeee net/ sett//oouumiid-yyy2ddad
Asier Mujika, Florian Meier, and Angelika Steger. Approximating real-time recurrent learning with random kronecker factors. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, and R. Garnett (eds.), Advances Neural Information Processing Systems 31, pp. 6594-6603, Curran Associates, Inc., 2018. URL http: http://pappps..o wippprrsssssss....pppppppppppppm nips. cctpaper pdf
N.
real- time- reweereccurretttee -eeenntteeeanngggge wi th random kww.ekker- factors.
James M Murray. Local online learning in recurrent networks with random feedback. eLife, 8: e43299, may 2019. ISSN 2050-084X, doi: 10.7554/eL.ife.43299 URLL/ttts:///oo.orrg/// f554/eLife.4325 43299
Sharan Narang, Gregory F. Diamos, Shubho Sengupta, and Erich Elsen. Exploring sparsity in recurrent neural networks. In International Conference on Learning Representations, 2017.
Jack W Rae, Jonathan Hunt, Tim Harley, Ivo Danihelka, Andrew Senior, Greg Wayne, Alex Graves, and Timothy P Lillicrap. Scaling memory-augmented neural networks with sparse reads and writes. Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS' 16, pp. 3628-3636, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Nikko Ström. Sparse connection and pruning in large dynamic artificial neural networks. In EUROSPEECH, 1997.
Corentin Tallec and Yann Ollivier. Unbiased online recurrent optimization. International
Conference Learning Representations, 2018. URL http:///ppppeeeeeeeeeeefeoeeeeee rJQDjk-0 Ob)
R. J. Williams and D. Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 1(2):270-280, June 1989. ISSN 0899-7667. doi: 10.1 16./ 1.2..1.
Ronald J. Williams and Jing Peng. An efficient gradient-based algorithm for on-line training of recurrent network trajectories. Neural Computation, 501, 1990.
F. Zenke and E. O. Neftci. Brain-inspired learning on neuromorphic substrates. Proceedings of the IEEE, pp. 1-16, 2021. doi: 10. 10.100//PR0C.2000344663.
Michael Zhu and Suyog Gupta. To Prune, or Not Prune: Exploring the Efficacy of Pruning for Model Compression In International Conference on Learning Representations Workshop, 2018.
11

---

Published as a conference paper at ICLR 2021
APPENDIX A: JACOBIAN SPARSITY GRUs AND LSTMs
Unlike vanilla RNNs whose dynamics Jacobian D, has sparsity exactly equal to the sparsity of the weight matrix, GRUs and LSTMs have inter-cell interactions which increase the Jacobians' density. In particular, the choice of GRU variant can have very large impact the increase in density. This relevant to the "dynamics" jacobian Dr and the parameter jacobians 4e and Jr.
Consider standard formulation of LSTM.
4 o (WRz, + Whihh + b,)
ft = (W.f2 + Whyhe-1 + by)
0 (Wio Whoht-1 bo)
(5)
9t < (Wig + W + kg)
C f. C-1 4 + 9t.
h4 = 02 o p(c))
Looking at LSTM's update equations, we can see that an individual parameter (W, 6) will only directly affect one entry in each gate (i,, ft. 0z) and the candidate cell gr- These in turn produce the next cell o and next hidden state h, with element-wise operations (a is the sigmoid function applied element-wise and ø is usually hyperbolic tangent). In this case Figure is accurate depiction of the propagation of influence of parameter as the RNN is stepped.
However, for GRU there multiple variants in which parameter or hidden unit can influence many more units of the next state. The original variant (Cho et al. 2014) is as follows:
2t a (Wi + Whahi + by)
Tt oW + Wh 6,)
(6)
= < + Wha(Pz @ h1-1) + bu)
h2 (1 z)) @ h111 24 0..
For our purposes the main thing to note is that the parameters influencing r, further influence every unit of ae because the matrix multiplication by Wha- They therefore influence every unit of he within one recurrent step, which means that the dynamics jacobian D, is fully dense and the immediate parameter jacobian 4, for Wa. Whr, and b, are all fully dense as well.
An alternative formulation which was popularized by Engel and also used in the CuDNN library from NVIDIA is given by:
2: = a (W. + Wheht- + +b)
Ft (War. Whrle by)
0: o( Wi + @ Whalu- + ba)
h4 (1 21) h4-1 2
The second variant has moved the reset gate after the matrix multiplication, thus avoiding the composition parameterized linear maps within single RNN step. As the modeling performance of the two variants has been shown to be largely the same, but the second variant is faster and results sparser D, and I, we adopt the second variant throughout this paper.
APPENDIX B: SPARSITY STRATEGY
Our experiments do not use state-of-the-art strategies for inducing sparsity because there is no such strategy compatible with SnAp at the time writing. The requirement of a dense gradient in EEcii et al. (2019) and Zhu & Guptal (2018) prevents the use of the optimization in Equation 4, which is strictly necessary to fit the RTRL training computations on accelerators without running out of memory.
12

---

Published as a conference paper at ICLR 2021
1550
1525
1590
units
bpe
sparsity
|0
1.455
base
1.55
0%
1x
1440
2x
1.48
75%
1x
14455
4x
1.43
93.75%
1x
8x
1.42
98.4%
1x
1400
16x
1.40
99.6%
1x
32x
1.38
99.9%
1x
2.5x
1.39
0%
6.25x
Figure 5: BPC vs Sparsity for Constant Param- eler Count. Shows the same results as Table 3 The biggest, sparsest GRU performs better than dense network with 6. 6,25x many (nonzero) parameters.
Table 3: Final performance of sparse WikiText103 language mod- eling GRU networks trained with progressive pruning. Each row rep- resents a single training run. The 'bpe' column gives the validation set negative log-likelihood in units of bits per character. The |0] col- umn gives the number of parameters in the network as a multiple of the 'base' 128-unit model.
To further motivate the development of sparse training strategies that do not require dense gradients, we show that larger sparser networks trained with BPTT and magnitude pruning monotonically outperform their denser counterparts in language modelling, when holding the number of parameters constant. This provides more evidence for the scaling law observed in Kalchbrenner et al. (2018).
The experimental setup is identical to the previous section except that all networks are trained with full BPTT. To hold the number parameters constant, we start with a fully dense 128-unit GRU. We make the weight matrices 75% sparse when the network has 256 units, 93.8% sparse when the network has 512 units, 98.4% when the network has 1024 units, and so on. The sparsest network considered has 4096 units and over 99.9% sparsity, and performed the best. Indeed it performed better than a dense network with 6.25x as many parameters (Figure [5. Pruning decisions are made on the basis of absolute value every 1000 steps, and the final sparsity reached after 350,000 training steps.
APPENDIX C: ANALYSIS OF THE BIAS INTRODUCED BY SNAP
Finally, we examine the empirical magnitudes of entries which are nonzero in the true, unapprox- imated influence matrix but zero by SnAp. For the benefit of visualization we train small GRU network (8 units, 75% sparsity) on a non-curriculum variant of the Copy-task with target sequences fixed in length to 16 timesteps. This enables to measure and display the bias of SnAp. The influence matrix considered is the final value after processing an entire sequence. The network optimized with full (untruncated) BPTT. We find (Table 4 that the beginning of training the influence entries ignored by SnAp are small in magnitude compared to those kept, even after the influence has had many RNN iterations to fill in.
This analysis complements the experimental results concerning how useful the approximate gradients are for learning; instead shows where - and by how much - the sparse approximation to the influence differs from the true accumulated influence. Interestingly, despite the strong task performance of SnAp, the magnitude of ignored entries in the influence matrix is not always small (see Figure The accuracy, measured by such magnitudes, trends downward over the course of training. We speculate that designing methods to temper the increased bias arising later in training may be beneficial but leave this to future work.
13

---

Published as a conference paper at ICLR 2021
Notan
Training Step
SnAp-1
SSnAp-2
100
1.0E-2 (73%)
4.0E-3 (97%)
5k
2.3BB- (22%)
2.6E-1 (78%)
10k
1.1E-1 (23%)
1.2E- (85%)
50k
3.3E-1 (34%)
2.5E-1 (87%)
100k
2.4B-1 (6%)
6.5E- (51%)
Figure 6: Influence matrix for 75% sparse GRU with 8 units after processing a full sequence with 35 timesteps (target length 16), various points during training ("step" corresponds to training step, e.g. the step within a sequence). This Hinton-diagram shows the magnitude of an entry with the size square. Grey entries are near zero. Entries filled in with red are those included by SnAp-I. Blue entries are those included by SnAp-2. and white ones ignored by both ap-
Table 4: Approximation Quality of SnAp-1 and SnAp-2. Average magnitudes in the influence ma- trix versus whether or not they are kept by an ap- proximate method. The "SnAp-1" and "SnAp-2" columns show the average magnitude of entries kept by the SnAp-1 and SnAp-2 approximations respectively. parentheses is sum the mag- nitudes of entries in this category divided by the sum of all entry magnitudes in the influence ma- trix.
proximations.
APPENDIX D: CODE SNIPPET FOR SNAP-1
We include below a code snippet showing how RTRL and SnAp can be implemented Jax (Bradbury et al.) 2018). While it is real and working Jax code, this is just sketch for pedagogical purposes and does not take full advantage of the optimizations in section 3.2.
Please take note of the license at the top of the snippet.
Copyright The Authors of "Practical Real Time Recurrent Learning wi th a Sparse Approximation the Jacobian", 2020
mox--License-Identiffi import jax
Apache-2.0
import jax. numpy jnp
def ged__fd__and updaatte influence influence_fuunccorreeee use_snapl___ __snanaapprro-Faasss) """Tranfform core_f into a one which maintains influence jacobian w/ RTRL.
def and_aand_ppee www.uuuudeeeflueeeeeeeeeeee www.uueneeeeree.iiiinee infl, params, state, inpt):
Run the forward pass on a batch of data.
batched_modell jax. vmapplamdda s, i: core_ fore_f(params, s, i))
f_out, state_new = sircched_mdee__ff((ttteeeeee
inpt)
Compute jacobians of state w.r.t. prev state and params. jac_ fn = jax. jacrev p. s, i: f(,,_f(p, s, i)[]], argnums=(0,, 1))
batched_jac. fn jax. vmap (lamdda s, i: jac_fn fn(prrsms, s, i)) p_jac, s_jac batched_jacc jatt__ssttt_tseee inpt)
Update the influence matrix according to RTRL learning rule. new_infl = jax. weexxtree_nnee mueemapppm
lambda j_i, infl_i: j_i + jnp. erpsumn bHh, "hh....>H...... s_jac, infl_i), p-jac, prev_infl)
SnAp-1: Keep only the entries of the influence matrix which are nonzero after single core step. This is not an efficient implementation.
if aise_ssapl_aae approo; mestepp_nff_maat tax.trreemap((
lambda abs() * (i).aattpejjnn.fflo P-jac)
14

---

Published as a conference paper at ICLR 2021
new_infl jax. tree_ mul mimap
lambda matrix, mask: matrix * mask, new_infl, oneseep_infl_re
return fout, state_new, new_infl return fwd undLaandudaate__nfflee
def compute, compute_grraientte grads = jax, trre_marr
nest, delta):
1 lambda influence_ii i: jnp.einsumm"bil .bl.....l->...'' influence i, delta),
influence_nest)
return grads
def make_zen zero infl (paraa_eeeapppppppaa state_exemplar):
def infl_ for (o____oooooo___tt(()))
return jax. tree__aeeppp
lambda p: (er.errrrr(sppp-llstttsspppp list(p.shape)) param_exemplass exemplar)
infl jax. _app__ppppp (make, fnrerinnf_ll___ttttaeeeeee etate_exemplar)
return infl
def get ger_rrrrlrreeeeeeeeeeeeeeeerreee gradd_grrra_aer hereigggaaaafuuncoooooo func f, readout_f, loss f, use_snapl_ approx): a
forr functions into one which computes the gradient RIRL."" "".
wno_Land_pddat__infleee
= wtw.:enaaanduuddre_iifleeeeeeee core_f, httpssaappppproruusssspppppppppp
def rtrl_gradd ferrd fcncpccre_parmms, readout_ readout_params, state, data):
def rtrl scan_ (carryy x):
"""Function which can be unrolled with jax. mex.lax.sco scan.
# Unpack state and input.
old_state, infl_acc, aore_grad_acc, readout_grad_ loss_acc carry inpt, targt, msk
# Update influence matrix. htt, new_state, new_infl_acc doo_aad_upddaeeiinfleeee infl_acc, core_params, old_state, inpt)
# Compute output, loss, and backprop gradients for RNN state. def losp_ h, t. m):
"""Compute the loss for RNN step."""
y readout_f(ps, return loss_f(y, t, m), y
s srr_outt_an_ggrr__fiii func = jax. valuevalue_nne saallee_andggrddd
step_loss, has_aux=True, argnums=(0, 1)) step_out, step_grad readout_params, h.t, targt, msk) loss_t, y_out step_out readout_grad__t delta_t step-grad
Update accumulated gradients.
core_grad_t compute_ wnw.eraaeeetseeeeinllllll delta_t)
new_core per_core__gra_aace grwd_aaadddeeeee jax. tree (
add, core_grad_acc, core_grad_t)
new_readout_grad.c jnp.add, readout_grad_acc, readout_grad_
tree_rre_mul timap(
# Repack carried state and return output. new_carry (new_state new_infl_acc,
lee__core_grad_ace new_readout.graa_.cc, loss_ace loss_t) return new_carry, y_out
irfo make_zero infl (core__c_ppag params, state)
aero_core_grad jax. tree map map(jnp. (jnp. zeros like, core_params)
15

---

Published as a conference paper at ICLR 2021
pero_readout_grad jax. tree_ wwwetterrepppeee mapee_pappippp.... petpp....e.o.... zeros like, readout_params final_carry, output_seq sacan
rtrl_scan_func,
init= iero, aaro_core_graat zero_ wer.rreddutggaaa 0. 0..), xs=taa input_sseq I,, data[' "ata["target_seq"1 I "aaaammms__ee""" }})
final_state, - core_grads, readout_grads, loss final_carry return (loss, (final_state, output_seq)), (core_grads, readout_grads) return sarl_grad__at func
16


Reviews:
[{"review_id": "w51Nms2hUSG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Post response update\nThe author's response has clarified most of the missing details in the paper. I still have an issue with reporting results for 3 runs --- even if the variance is small for 3 runs, that does not imply that there won't be outliers when one does more runs. Nonetheless, the proposed method is insightful and the paper has significant pedagogical value. I'm moving my score from 6 to 7 and I hope the paper is accepted. \n\n## Summary\nThe paper tackles the structural credit-assignment problem for a recurrent network when parameter values in earlier time-steps can impact the prediction in the future. The most common approach to achieve this structural credit-assignment, in the current deep learning literature, is BPTT. BPTT, however, is not suitable for online learning. First, the computation and memory requirements of BPTT grow with the length of the sequence. Second, BPTT does not spread computation uniformly --- all the computation happens at the end of an episode. This is not suitable for an online learner that has to learn and react in real-time. An alternative to BPTT is RTRL. The computation and memory needs of RTRL is distributed uniformly across time-steps and RTRL makes it possible to learn at every step, but it requires an intractable amount of memory and compute for even modestly sized networks. \n\nThe limitation of both BPTT and RTRL necessities research on new algorithms. Ideally, we want algorithms that spread the computation uniformly and are still scalable. SnAp, the methods proposed in this paper, is one such algorithm. The general idea behind SnAp is to approximate the gradient by only taking into account the impact of a parameter $w_j$ on an activation $h_i$ only if $w_j$ influences $h_i$ with-in n steps. A similar algorithm was used in the original LSTM paper that was equivalent to SnAp with n=1 for the LSTM architecture. This paper generalizes the algorithm used in the original LSTM paper in two dimensions. First, it generalizes it to methods beyond the specific LSTM architecture, and second, it can keep track of influence of parameters across $n$ steps instead of just 1. While the cost of SnAp increases quickly as $n$ increases, the authors propose a promising direction for keeping the cost down. They argue and show that for highly sparse RNNs, SnAp can be scaled to $n > 1$. \n## Review \n\n### Strengths \nThe paper is well written. It summarizes the prior work concisely and explains the two views of computing the gradient for an RNN --- the recursive view used by RTRL and the unrolling view used by BPTT --- clearly. The need for sparsity in RNNs is well-motivated and the observation that sparsity in RNN slows down the propagation of influence of a parameter on a state is interesting. The new algorithm, SnAp, is clearly presented as an approximation to RTRL. The paper also does not make unsubstantiated claims and explains the merits and limitations of the proposed method clearly. Overall, I'm highly impressed by the quality of the paper and the merits of the idea. \n\n\n### Weaknesses \nWhile the paper excels in writing quality and the proposed method is sound, the empirical evaluation of the method has several issues. First, it's not clear how the hyper-parameters for all the methods were tuned. Were the parameters tuned for SnAp and inherited for other methods? Were they tuned independently? The paper mentions that it used $\\beta_1=0.9$ and $\\beta_2=0.999$ for the Adam Optimizer without explaining how they were chosen. \n\nMany details of the experiment setup are not fully specified. For example, in page 6 the authors mentioned that they use a one-layer MLP to get 1024 hidden units which are mapped to 256 unit software, but do not clarify if a non-linearity is applied to the 1024 units. The paper also omits how $\\theta$ is initialized. \n\nThe experimental results have no error margins, and are the mean of only 3 runs. Ideally, authors should repeat the experiments for over 20 runs and report the standard error of the mean. Even if they are limited by available compute and are unable to do many runs, they should at-least report the standard-error for however runs they do (Note that standard error computation is biased for few runs and it might be a good idea to apply bias correction. More details here: https://en.wikipedia.org/wiki/Standard_error). \n\nParameters sweeps should be extended if the optimal parameter is at the edge. The authors report that they tried $10^{-3}, 10^{-3.5},$ and $10^{-4}$ and found $10^{-3}$ to be best. However, all this tells me is that a higher learning rate could have been even better. They should include larger learning rates in the sweep for the experiment. \n\nIt's not clear if the authors are (1) finding the best learning rate and then re-running for 3 seeds for the best learning rate or (2) simply running the experiments for 3 different seeds for all learning rates and reporting the best results. The former is a sound strategy whereas the latter suffers from over-estimation bias. \n\nGiven the issues in the experiment methodology, I'm giving the paper a weak accept for now even though I think that the paper excels in many ways. The issues identified can easily be fixed during the discussion period and I would be more than happy to change my score to an accept or a strong accept after a revision that fixes the experimental issues. \n\n\n### Questions \n1. In page two, the paper introduces a function $g_{\\phi}$ for mapping the state to the target and then says that the goal of the learner is to minimize loss with respect to $\\theta.$ Shouldn't the loss be minimized with respect to both $\\theta$ and $\\phi$? Or are the authors implying that the readout layer is fixed? (Or perhaps $\\phi$ is a subset of $\\theta$?)\n\n2. It's not clear to me from the write-up how the sparsity pattern is choosen empirically. Is the idea to run the RNN for n-steps, empirically observe enteries in $J_n$ that are zero, and fix those enteries to be zero for all future steps? If yes, could the initial weights of the RNN and the data make an entry in $J_n$ to be zero even if it would not have been zero for a different initialization and data-stream? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "R5dyJMrzI1a", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work presents a method, named SnAp, that takes Real-time Recurrent Learning derivations and proposes to approximate its computations with sparse approximations to make them more computational tractable. The method is an alternative to overcome the truncation in backpropagation through time (BPTT) over long term temporal structure. The method assumes a sparsity pattern on the parameters of the network that leads to the relationship on how the gradients could be updated. Finally, the method is evaluated against BPTT, UORO and RTRL on character-level language modeling and a copy task.   \n\n=================\n\nThe method is simple and a complexity analysis has been included. The experimental section seems limited in only showing a performance comparison with other methods. A better analysis in aspects of the method (like capacity for learning long-term temporal patterns) is lacking.\n\n==================\n\nWhen does the Snap/RTRL is not applicable? Are there cases where BPTT is applicable and Snap/RTRL is not? It would be nice to clarify such cases so readers can understand when Snap, RTRL, or BPTT are the right or better solutions. \n\nThe motivation behind the method is to overcome the limitation of the truncation behind BPTT for learning long term temporal structure. However this seems to be evaluated with very short sequences overall (128 for language modeling and maybe less than that for the copy task, the length is not present). How well the Snap method would work when training for sequences of thousands of elements, where BPTT is well known to struggle?\n\nThe relationship between neurons can vary every time the parameters are updated. Is it assumed to be fixed over the entire training? What would happen if the pattern is updated every few gradient updates? Also, complexities for Snap in table 1 don’t seem to consider the computational time of computing the sparsity pattern (even for a random pattern).\n\nWhen n is big, the experimental results show a better and competitive performance to BPTT. However, in such cases (like Snap-3) the computational cost becomes very expensive compared to BPTT by at least 2 orders of magnitude, and the matrices become more dense. What are the results of TBPTT when stateful training is applied and how do they compare in such case? Also, the copy task has been solved with fewer neurons in previous works. \n\nThe Copy task details are unclear for someone that doesn’t know the work from Mujika et al., 2018. Please describe all the details. What is the length L used in the experiments? What is the length of the overall sequence? What does “data time” mean in the plots of Figure 4?\n\n==================\n\nMy concerns behind the limited practicality of the method, and the limited experimental results given the hypothesis that the method can learn long-term temporal patterns. These are my considerations not to accept this paper.\n\n==================\n\nMinor issues:\n\n-Use bigger fonts in the plots, and diagrams.\n\n-In 5.1, do you use SGD or Adam?\n\n-Figure 3: leave space between caption and figures\n\n-Table 1 caption: “Below” -> “Above”\n\n-It would be nice to mention the relationship between |\\theta| and k, for each recurrent cell case.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9MvVOSfxl2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Second Review\nThe author's thoughtful response has clarified most of the missing details in the paper. It is true that idea is interesting and theoretical analysis are promising. However, I still have issues understanding failure conditions. If the method is purely based on trial and error to determine optimal threshold for sparsity, then it requires many engineering tricks. Thus I would request authors to provide such details, such that young researchers can extend this work to create better training paradigm for RNNs. Other issue as pointed out by other reviewers is using only 3 runs to report results.  I really appreciate explanation about difference between 2 variants of GRU and how it adds sparsity to the model. Additionally JAX code helped in understanding many key apsects of the work. I would encourage authors to make it public, and provide key insights for training RNNs using snap. Nonetheless, the proposed method and theoretical analysis are insightful and I believe this to be a first step towards building scalable RNNs which efficiently gets rid of credit assignment issue. This paper does add significant pedagogical value, which can benefit complex task such as grammatical inference. I'm increasing my score from 5 to 7 and I hope this paper is accepted. \n\n## Summary\nPaper introduces snap which adds sparsity to the influence matrix extracted from RTRL which acts as a practical approximation for RTRL, snap is extension of prior work on snap-1 used to train LSTM, and authors have shown that one can train dense as well as sparse RNNs using snap achieving similar performance as BPTT on real as well as synthetic dataset. Few clarifications in terms of snap working and few key information w.r.t to parameters are missing.\n\n## Clarification\n\nHow does one evaluate level of sparsity required for any given task? At what n (sparsity ratio) optimal performance is observed which leads to better performance. It is well known that full RTRL (forward propagation helps compared with backward propagation), especially in case of continual or online learning [Ororbia and Mali 2020] and copy task (KF-RTRL, UORO). Does current sparsity measure work on variant of RTRL? And how do you determine top k to select k elements for creating a sparse matrix? is it random like 70-80-99? Many key details are missing, and authors are requested to provide more information to better understand model flow.\n\nIn appendix authors talk about “modeling performance of the two variants of GRU. which has been shown to be largely the same, but the second variant is faster and results in sparser D_t and I_t”. I am confused, what is the relationship between sparsity and two variants? Please provide some numbers explaining how sparsity is increased by moving reset gate after the matrix multiplication.\n\nHow does sparsity measure is introduced in this work? Does model stay consistent whenever regularization approaches such as zoneout or dropout are used or introduced into the model? Do you observe the similar performance? Does network roughly converge to similar performance with optimal sparsity or sparsity measure changes as other regularization approaches are introduced? Did you do grid search for language modelling task or copy task (beside learning rate)? If so please provide details? Citation and comparison missing with Sparse attentive backtracking, which in theory can work with sparse networks and its temporal credit assignment mechanism can help in introducing sparsity [ke and goyal 2019]. \n\nAuthors states that “In order to induce sparsity, we generate a sparsity pattern uniformly at random and fix it throughout training” What is the range for random uniform? Is model sensitive whenever sparsity pattern is changed while training (may be per epoch or k epochs). How can one ensure that the sparsity pattern at start is the optimal one for any network? Does similar pattern work for all GRU, LSTM, RNN or one needs to adapt scheme based on architecture?\n\nAdvantage of snap-2 and 3 over snap-1, snap-1 is similar to (Hochreiter & Schmidhuber, 97) work on training LSTM, what modification is introduced on snap-1 beside training it on GRU? And sparse networks. It is still unclear what advantage these 3 variants add. It is important to show speed (with various sparsity, convergence plots or else these variants would have similar performance and memory requirement compared with vanilla RTRL\n\n\n[Ke and Goyal 2018] Ke, N.R., GOYAL, A.G.A.P., Bilaniuk, O., Binas, J., Mozer, M.C., Pal, C. and Bengio, Y., 2018. Sparse attentive backtracking: Temporal credit assignment through reminding. In Advances in neural information processing systems (pp. 7640-7651).\n\n[Ororbia and Mali 2020] Ororbia, A., Mali, A., Giles, C.L. and Kifer, D., 2020. Continual learning of recurrent neural networks by locally aligning distributed representations. IEEE Transactions on Neural Networks and Learning Systems", "extra_scores": {}, "extra_text": {}}, {"review_id": "0UIaJprNIhM", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Second review\n\nThanks for taking all my comments seriously. After clarification of the difference with RFLO I see that this work is even richer than I thought and I increase my grade to 8. It seems that other reviewers did not appreciate that training a network without back-prop requires nontrivial engineering and theoretical considerations which are well described in this paper, I truly think it is a pity if this work is not accepted.\n\nI fully agree with the difference between RFLO and Snap-1 that you describe in your reply, and I think it would be really great to put that somewhere in the paper. As you suggest it would be great to explain that you did not use random feedback weights for RFLO.\n\nThis would also be a great opportunity to explain how did you extend RFLO to a GRU network in Figure 3. I find it a bit puzzling, that RFLO appears worse than an untrained network in Figure 3 (even early in training as in seen in Figure 3.B). Is there any additional difference in the network model for these two baselines, like one is using leaky RNN and the other one GRU or something like that?\n\nI find the piece of JAX code incredibly rich. It would be great to publish that along with the paper! JAX is not yet very well spread, and we see here that it is a very promising tool for custom gradient in RNNs.\n\n## Summary\n\nThe authors describe new algorithms to train sparse recurrent neural networks, these algorithms are described as variants of RTRL. These methods, called SNAP-$n$, use the same induction as in RTRL but approximate the true Jacobian matrix $J$ by a sparse matrix where each coefficient is set to zero if the corresponding parameter does not influence the corresponding state variable within $n$ steps. These alternatives to BPTT alleviate the memory consumption growing otherwise linearly with the sequence length. \n\nA theoretical complexity analysis and simulation experiments are carried out. The simulations are performed on the character prediction task and a synthetic copy task. The authors report that the network reaches performance comparable to BPTT and sometimes better (snap-3 leads to better copy task performance with GRU, snap-2 seems already better with LSTMs, however it requires many more FLOPS).\n\n##  General opinion\n\nCongratulations to the authors. This is an important topic since recurrent networks are not efficiently trained with BPTT. More intensive and rigorous research are needed to find suitable alternatives. The SNAP idea is simple and appealing, and the results encouraging (even though it still requires a large number of FLOPS).\n\nI recomputed rather carefully the complexity analysis for sparse RTRL, snap 1 and snap 2 and arrived at similar results. Theoretical results seem to be correct and the experiments are credible. \n\n##  Requires clarification\n\nOne negative comment is that snap-1 has been published before in other forms as explained below The writing makes it sounds more novel that it actually is and some comparisons with other algorithms are unfair. It would be great to correct the shot but snap deserves publication anyway since it also provides a rigorous analysis of the full snap family and snap-1 had not been explored in such details in the interesting context of sparse networks.\n\nRFLO for leaky RNNs is basically exactly snap-1 with the additional burden of carrying random feedbacks. It is written three times that snap-1 is better than RFLO but it would be great to comment on the differences and explain where is the difference of performance coming form. The random feedback was introduced in RFLO to avoid the transport problem for biological plausibility. It does not seem relevant to do this extra approximation step if RFLO is used for performance and not plausibility. If the random feedback is the main difference, one should clearly say that the algorithm are otherwise identical. If the authors see other differences, it would be great to indicate what they are.\n\nThis very same algorithm (snap-1, RFLO) was also published under the name e-prop 1 [a] although the theory was derived differently. The authors had shown that e-prop 1 (aka snap-1) works well on the copy task, a word prediction task with LSTMs (Figure 4 in [a]), ATARI games and TIMIT (more recent work).  The authors had also suggested an amelioration called e-prop 3 that improved the performance and kept the same time complexity as BPTT unlike snap-2 and snap-3. Maybe it is relevant to comment on the relationship between snap and this paper [a] ?\n\nIn case the authors were not aware of this, an other interesting approximation to RTRL was published in [b], the authors may or may not comment about that too.\n\nThere are technical details that should be given for clarification:\n- The authors might want to provide details on the computation of the complexity of one or two of the essential component of the table to make it more accessible to the reader. If I am not mistaken I think that the complexity results are true \"up-to a proportionality constant\" for a general RNN model, maybe it would be great to write that in the caption for instance. The complexity is written in the table in the form A + B, I understood than A is the complexity in the forward pass and B is the complexity in the backward pass, but maybe it should be explained. Maybe there is also an easy way to confirm those numbers with the empirical number of FLOPS given later in the paper ?\n\n- In Figure 4, I cannot find out what the colored dash lines are meant to be. This caption is rather short and there is an opportunity to add some information: for instance what is \"curricula max\".\n\n- In Figure 2, the author use k^2 by they have also introduce the letter p. Is that not meant to be the same thing? It probably depends on the RNN model? Before doing the calculation of the complexity myself I did not know whether p included already the coefficient d, I do not think that it obvious that zeroed coefficients are still considered as \"parameters\" in the \"number of parameters\" p. Maybe this can be said in the caption?\n\n- If I understand correctly the pruning method in appendix B, the network is first trained until convergence with BPTT and then, the best architecture is fixed to be retrained with snap? It would be great to clarify this paragraph because it is not easy to read. If that's the case there could be a substantial transfer of information by passing on the \"winning\" architecture from BPTT to the SNAP training, in particular for very sparse networks. Is that really necessary? How much would the performance decrease? As a control, I would guess that for something like 75% sparsity the network can be trained from a random matrix. Also I do think that there are now simple methods available for training much sparser networks from scratch, and it would not require this pre-BPTT step.\n\n- It would be so great to have some details about the implementation: what software did you use to perform this \"remake\" of a forward propagation? Did you have to implement a custom C++/cuda code, maybe use JAX ? Did you use sparse matrix cuda kernel, how good was it? Maybe the code will be shared, if not any details are welcome.\n\n\n[a] Biologically inspired alternatives to backpropagation through time for learning in recurrent neural nets\nGuillaume Bellec, Franz Scherr, Elias Hajek, Darjan Salaj, Robert Legenstein, Wolfgang Maass\nhttps://arxiv.org/abs/1901.09049\n\n[b] Kernel RNN Learning (KeRNL)\nChristopher Roth, Ingmar Kanitscheider, Ila Fiete\nhttps://openreview.net/forum?id=ryGfnoC5KQ\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a method for approximating real-time recurrent learning (RTRL) in a more computationally efficient manner. Using a sparse approximation of the Jacobian, the authors show how they can reduce the computational costs of RTRL applied to sparse recurrent networks in a manner that introduces some bias, but which manages to preserve good performance on a variety of tasks.

The reviewers all agreed that the paper was interesting, and all four reviewers provided very thorough reviews with constructive criticisms. The authors made a very strong effort to attend to all of the reviewers' comments, and as a result, some scores were adjusted upward. By the end, all reviewers had provided scores above the acceptance threshold.

In the AC's opinion, this paper is of real interest to the community and may help to develop new approaches to training RNNs at large-scale. As such, the AC believes that it should be accepted and considered for a spotlight.
Decision: Accept (Spotlight)