Training Recurrent Neural Networks Online by Learning Explicit State Variables
Authors: Somjit Nath
Vincent Liu
Alan Chan
Xin Li
Adam White
Martha White
Venue:  (2020)
Keywords: Recurrent Neural Network
Partial Observability
Online Prediction
Incremental Learning

Abstract: Recurrent neural networks (RNNs) allow an agent to construct a state-representation from a stream of experience, which is essential in partially observable problems. However, there are two primary issues one must overcome when training an RNN: the sensitivity of the learning algorithm's performance to truncation length and and long training times. There are variety of strategies to improve training in RNNs, the mostly notably Backprop Through Time (BPTT) and by Real-Time Recurrent Learning. These strategies, however, are typically computationally expensive and focus computation on computing gradients back in time. In this work, we reformulate the RNN training objective to explicitly learn state vectors; this breaks the dependence across time and so avoids the need to estimate gradients far back in time. We show that for a fixed buffer of data, our algorithm---called Fixed Point Propagation (FPP)---is sound: it converges to a stationary point of the new objective. We investigate the empirical performance of our online FPP algorithm, particularly in terms of computation compared to truncated BPTT with varying truncation levels. 

Published as a conference paper at ICLR 2020
TRAINING RECURRENT NEURAL NETWORKS ONLINE BY LEARNING EXPLICIT STATE VARIABLES
Somjit Nath, Vincent Liu, Alan Chan, Xin Li, Adam White and Martha White Department of Computing Science University of Alberta (somjit, vl wliul, achan4, xzli, amw8, whi (immtmmaa @ua bberta.ca
ABSTRACT
Recurrent neural networks (RNNs) allow an agent to construct state- representation from a stream of experience, which is essential in partially ob- servable problems. However, there are two primary issues one must overcome when training an RNN: the sensitivity of the learning algorithm's 's performance to truncation length and and long training times. There are variety of strategies improve training in RNNs, the mostly notably Backprop Through Time (BPTT) and by Real-Time Recurrent Learning. These strategies, however, are typically computationally expensive and focus computation on computing gradients back in time. In this work, we reformulate the RNN training objective to explicitly learn state vectors; this breaks the dependence across time and so avoids the need to estimate gradients far back in time. We show that for a fixed buffer of data, our algorithm-calle called Fixed Point Propagation (FPP) is sound: it converges to a stationary point of the new objective. We investigate the empirical performance of our online FPP algorithm, particularly in terms of computation compared truncated BPTT with varying truncation levels.
INTRODUCTION
Many online prediction problems are partially observable: the most recent observation is typically insufficient to make accurate predictions about the future. Augmenting the inputs with history can improve accuracy, but can require long history when there are long-term dependencies back in time. Recurrent Neural Networks (RNNs) (Elman, 1990; Hopfield, 1982) learn state which summarizes this history. Specifically, RNNs contain recurrent connections to their hidden layers which allow past information to propagate through time. This state need not correspond to a true underlying state: rather, the state is subjective and constructed to facilitate prediction. RNNs have been widely used, in speech recognition (Hinton et al., 2012; Graves et al., 2013; Miao et al., 2015; Chan et al., 2016), image captioning (Mao et al., 2014; Lu al., 2016; Vinyals et al., 2014), speech synthesis (Mehri et al. 2016) and reinforcement learning (Hochreiter and Schmidhuber, 1997; Düll et al., 2012).
Despite these success, there are significant stability and computational issues in training RNNs online (Pascanu el al., 2013; Tallec and Ollivier, 2017). In the online setting, the agent faces an unending stream of data and on each step the agent must update its parameters make new prediction. (BPTT) (Werbos, 1990) or
RNNs are typically trained either using backkropagatiionttrrugg----- approximations an algorithm called Real-Time Recurrent Learning (RTRL) (Williams and Zipser, 1989a; Pearlmutter, 1995), although there are methods that appeal to other principles (see Murray (2019) for instance). The update for BPTT is a variant of standard backpropagation, computing gradients all the way back in time. This approach is problematic because the computational cost scales linearly with the number of time-steps. A more common alternative truncated BPTT (T-BPTT) (Williams and Peng, 1990) which only computes the gradient up some maximum number of steps: we truncate how far back in time we unroll the network to update the parameters. This approximation, though, is not robust to long-temn dependencies (Tallec and Ollivier, 2017). Approximate gradients can also be computed online by RTRL (Williams and Zipser, 1989b). This online algorithm, however, has high computational complexity per step and therefore is not commonly used in practice.

---

Published as a conference paper at ICLR 2020
Recently, there have been some efforts towards approximating gradients for backk-poopagaie both for feedforward NNs and RNNs. Synthetic gradients and BP(A) (Jaderberg et al., 2017) use an idea similar to returns from reinforcement learning: they approximate gradients by bootstrapping off estimated gradients in later layers (Jaderberg et al., 2017: Czarnecki el al., 2017). There are several methods that approximate RTRL- which is itself approximation of the true gradient back in ince-incuuding NoBacKTrack (Ollivier and Charpiat, 2015), Unbiased Online Recurrent Optimization (UORO) (Tallec and Ollivier, 2017) which uses an unbiased rank-1 approximation to the full matrix gradient, and Kronecker Factored RTRL (Mujika et al., 2018) which uses Kronecker product decomposition approximate the RTRL update for a class of RNNs. Finally, there are some methods that use selective memory back in time to compute gradients for the most pertinent samples, using skip connections (Ke el al., 2017). All of these methods, however, attempt to approximate the gradient back in time, for the current observation and state, and so suffer to some extent from the same issues as BPTT and RTRL.
In this paper, investigate an alternative optimization strategy that does not attempt approximate the gradient back in time. Instead we learn the state variables in the RNN explicitly. These new variables optimized to both improve prediction accuracy, and to maintain consistency in producing the next learned state variables. This second constraint is a fixed-poing point formula for the states under the given RNN dynamics. We develop a provably sound stochastic update for the new fixed-point objective, which we then use to develop an online algorithm for training RNNs. The algorithm explicitly optimizes state vectors and RNN parameters with many efficient one-step-or short term multi-step updates-acros acrioss buffer. Instead of focusing computation to get a more accurate gradient estimates for this time-step, our algorithm, called Fixed Point Propagation (FPP), can more effectively use computation to update prediction accuracy across states. We demonstrate that the algorithm is effective on several problems with long-tern dependencies, and improves over T-BPTT, particularly in terms of stability and computation.
2 PROBLEM SETTING AND BACKGROUND
We consider a partially observable online setting, where an immediate observation is not sufficient for prediction. More formally, assume there is sequence of n observations, 01,...; On, which provide only partial information about an unknown underlying sequence of states. After obtaining an observation O,, the agent makes a prediction ý; and sees the actual outcome y;. The goal is to minimize this prediction error. Given only o, the agent is unlikely to make accurate predictions about yi, because o not a sufficient statistic to predict y;: p(y|o,, 0,- o;-2....) * p(y o.). The agent could obtain a lower prediction error using history of observations. Unfortunately, the agent may require a prohibitively long history, even this history could have been summarized compactly.
An alternative is to construct state using a Recurrent Neural Network (RNN), by learning a state- update function. Given the current (constructed) state S, R. and new observation o, E Rd the parameterized state-update function fw : R x Rd - RR* with parameters W, produces the next (constructed) state 8, = (w, (8,,-1,o)),, o.). For example, /w could be a linear weighting of 8,- and o,, with ReLu activation: fw o,) max mnax([s;-1,0 o, W, .). More complex state-updates possible, like the gating in Long Short-Term Memory (LSTM) (Hochreiter and Schmidhuber, 1997).
The objective is to adapt these parameters W for the state-update to minimize prediction error. For the current state St, a prediction is made by parameterized function g3 R$ - I with learned parameters B. For example, the prediction could be a linear weighting of the state, ga(s) = 3 ss. We denote the prediction error as fgz ; I2 x 1nm + IR for given B. For example, this loss could be
fg(s ye) = (s:)(s:) 1r112.
'Recurrent Backpropagation and related variants (Almeida, 1987; Pineda, 1987; Scellier and Bengio, 2017: Liao et al., 2018) also use fixed points for their optimization, but in different way. These algorithms only address restricted class of RNNs, that assume fixed input and converge a single low-energy state-a fixed point of the dynamics 2008), because the temporal nature only arises from cyclic connections, rather than from temporal data. Their problem setting is fundamentally different from our online prediction setting, and is usually used for associative memory with Hopfield networks or semi-supervised problems. Recurrent Backpropagation cannot be used for our setting and do not further discuss this class of RNN algorithms.
that given input. These RNNs are actually highly related Graph NNs (Scarselli al.,
2

---

Published as a conference paper at ICLR 2020
The goal in RNNs training is to minimize, for some start state Su,
Σ LawSw( (Sw 01): o;);::))) B.W
min
Computing gradients for this objective, however, can be prohibitively expensive. A large literature optimizing RNNs focuses on approximating this gradient, either through approximations to RTRL or improvements to BPTT. RTRL (Williams and Zipser, 1989b) uses recursive gradient form, which can take advantage of gradients computed up until the last observation to compute the gradient for the next observation. This estimate, however, is only exact in the offline case and thus RTRL is an approximation of the true gradient in our online setting. Further, in either online or offline, RTRL requires O(a²)) computation per observation (recall is the dimension the state). In BPTT, gradients are computed back in time, by unrolling the network. In the online setting, it is infeasible to compute gradients all the way back to the beginning of time. Instead, this procedure truncated T steps back in time. T-BPTT is suitable for the online setting, and requires O(Tk?) computation per step, i.c. for each observation.
Arguably the most widely-used strategy is T-BPTT, because of its simplicity. Unfortunately, T-BPTT has been shown to fail in settings where dependencies back in time are further than T (Tallec and affirm in our experiments. Yet. the need for simple algorithms remains. In this
Ollivier, 2017), work, we investigate an alternative direction for optimizing RNNs that does not attempt to estimate the gradients of (1).
Note that in addition to a variety of optimization strategies, different architectures have also been proposed facilitate learning long-term dependencies with RNNs. The most commonly used are LSTMs (Hochreiter and Schmidhuber, 1997), which use gates to remember and forget components of the state. Other architectures include clockwork RNNs (Koutník al., 2014), phased LSTMs (Neil et al., 2016). hierarchical multi-scale RNNs (Chung et al., 2016), dilated RNNs (Chang er al.. 2017), and skip RNNs (Campos al., 2017). In this work, we focus on a general purpose RNN algorithm. that could be combined with each of these architectures for further improvement.
3 A NEW FIXED-POINT OBJECTIVE FOR RNNS
In this section we introduce our new formulation for training RNNs. We begin with an idealized setting to introduce and explain the ideas. Later we will generalize our approach to partially observable online training tasks.
First, assume the observations are produced by an underly Markov Chain with a discrete set of states, and the agent has access to set of observations that deterministic function of the state. We denote the set of states H = {l..... n., and the observations from each state as O1,.... .,.,.n The goal is to find state vectors 81, ..... Sn RR that satisfy two goals. One is enable the state be updated
fw(s.. S; V where P(i,j) > 0
for P H. x H. + [0. the transition dynamics. Another criterion is for these state vectors to facilitate accurate predictions. In particular, the learned state should minimize (s(s);y,) for all h, where yj E IR is the expected target for true state j. Together, this results in the following optimization, with the relationship between states encoded as a constraint
Σ P(c.))ss(((ss:)) J.W.s
min
fw o,) =s Vi where P(í,)) >
IJEK
The satisfiability of this will depend on fw and if s; and oy can uniquely determine sj.
More generally, we will not know the underlying state, nor is it necessarily discrete. But, can consider a similar objective for observed data. Assume n observations have been observed, Oj...., On, with corresponding targets y1.... ......... .n.- Let the state variables be stacked in matrix E |lxxn and observations as a matrix O E gddn with = [sp...., sn] and O = [o),..., o.]] The constraint the states becomes S Fw O) for operator
Fw (S. 0) /S.::/(SS.oo O. (wal))...WSSS....... -..
(3)
3

---

Published as a conference paper at ICLR 2020
We call this the fixed-pont - constraint, since solution S to the constraint is fixed point of the system defined by F: O). The resulting optimization, for this batch, is
min Σ (() B.W.S
s.t. S (S.)).).
(4)
1=1
The solution to this new optimization corresponds to the solution for the original RNN problem in (I) (I)-when also optimizing over Sy because the fixed-point constraint forces variables S; to be representable by /w. Therefore, the reformulation as a fixed point problem has not changed the solution; rather, it has only made explicit that the goal learn these states and facilitates the use of alternative optimization strategies.
Reformulations like the one in (4) have been widely considered in optimization, because (4) is actually an auxiliary variable reformulation of (I). In this case, the auxiliary variables are the states S. Using auxiliary variables is a standard strategy in optimization under the general term method of multipliers to decouple terms in an optimization and facilitate decentralized optimization.
Such auxiliary variable methods have even been previously considered for optimizing neural networks. Carreira- Periiiraa and Wang (2014) introduced the Method of Auxiliary Coordinates (MAC), which explicitly optimize hidden vectors in the neural network. Taylor et al. (2016) proposed a similar strategy, but introduced additional set of auxiliary variables obtain further decoupling and a particularly efficient algorithm for the batch setting. Scellier and Bengio (2017) introduced Equilibrium Propagation for symmetric neural networks, where the state of the network is explicitly optimized to obtain a stationary point in terms of the energy function. Gotmare et al. (2018) built on these previous ideas to obtain stochastic gradient descent update for distributed updates to blocks of weights in neural network. Our proposed optimization can be seen variation of the objective considered for MAC (Carreira-Perpiial and Wang, 2014, Equation 1), though we arrived from a different perspective: with the goal to learn explicit state vectors.
The objective (4) still has two issues. First, it is not amenable to online updating: it is a batch optimization with constraint. Second, it does not allow for any training back in time. But, this stringent computational restriction is unnecessary. We could have instead asked: learn states so that when iterated twice through the RNN, the resulting state enables accurate predictions the target two steps in the future. We develop more general objective below to address both issues.
We rewrite the objective that it is clear how to stochastically sample it, and enable online updating. As in MAC-QP (Carreira- CCarreiraPPerpinán and Wang, 2014), we reformulate this constrained objective into unconstrained objective with quadratic penalty, with X >
L(B, W) def
Eo fo(fw(s: (s: o.): +
st fw(s
(5)
2n
Once in this unconstrained form, we can perform stochastic gradient descent on this objective in terms of (3, W and S to reach a stationary point. To use stochastic gradient descent, the objective needs to break up into sum of losses, L(B, W,S) E/= L,(,, W.S), S), where we define
LB3, W, 8) del (glfw(ss-1.0)::1)
, 1|s - fw f.)s
We can stochastically sample i from our buffer of samples and update variables with V;,- Fortunately, because the state variables break connections across time, this gradient is zero for most variables, except B, W 8; and s, Therefore, each stochastic update can be computed efficiently.
Second, we can generalize this objective to incorporate more than one step of propagation back in time, simply by generalizing the fixed-point operator. Consider the more general 7 -ttep fixed point problem S = Fr.w (S, O) where
Fr. w (S, 0) def S.o. S...... S.T-1. I. fw (ww.wWSwWSo.oo O..). )..
S
fw(... Ww(.: O
.......))
4

---

Published as a conference paper at ICLR 2020
butter Before updali)
(8t-n;
-t-n+ -/t--n-ttl St-n+1 n- n1
82
Oz, Dt:
sample S
7
T
O2
T1
O4
W
(utter updite) (5)- 15t-ro O1-n+1 Mt-x++1111 0,-1+1 1/ 1+1.
O++1 (..1...,,.
Figure 1: single update by FPP. randomly samples and performs gradient descent update S:-T: S,, W and B, where the loss on the targets affects 8:-T, W, 3 and the loss producing the next state variable s; affects 8 Si, W. The state variables are stored in the buffer, but are explicit variables we learn, just like W and B..
For T = 1, recover the operator provided in (3). This generalization mimics the use of T-step methods for learning value functions in reinforcement learning. This generalization provides more flexibility in using the allocated computation per step. For example, for budget of T updates per step, we could use 7" 1-step updates, T/2 2-step updates, all the way up to one T step update.
The loss for general T' similarly decomposes into sum 7 E LB W, S) for
(3, S) = (S.S. W):y,) + 11s - (s W)l2
(6)
where $,(s;TT, W) def fw(.. www.:.ff((f((s---1..0001111 o ...)))
For each stochastic sample VL, only non-zero for 3, W, W, s;-r and s,. Though these updates can simply be computed using automatic differentiation on Li, the explicit updates are simple so we include them here, using shorthand for (s, W):
Vx G La = (a(nn))) - A(s; - 6,)] Vx
V Li A(s: -i)
VwL, = [V - A(s - -1]] T
(7)
pLL: Vola($;yy))
The online algorithm uses these updates on sliding window buffer, instead of a fixed buffer. This algorithm-called Fixed Point Propagation (FPP)-is summarized in Figure I and Algorithm
As alluded to, the advantage of FPP over T-BPTT is that we are not restricted to focusing all computation to estimate the gradient 7 7-steps back in time for one state-observation pair. Rather, instead of sweeping all the way back, we spread value by using updates on random transitions in the buffer. This has three advantages. First, it updates more states per step. including updates towards their targets. Second, this ensures that targets for older transitions are constantly being reinforced, and spends gradient computation resources towards this goal, rather than spending all computation computing more exact gradient for the recent time step. This distributes updates better across time, and should likely also result in a more stable state. Third, the formulation as stochastic gradient descent the fixed point objective makes it sound strategy opposed to truncation which is not sound. FPP, therefore, maintains the simplicity of T-BPTT, but provides a more viable direction to obtain sound algorithms for training RNNs.
4 CONVERGENCE RESULTS
In this section we show two theoretical results. First, show that the FPP algorithm converges to stationary point, for a fixed buffer. This result is relatively straightforward application of recent theory for nonconvex optimization (Ghadimi al., 2016), mainly requiring us to show that
5

---

Published as a conference paper at ICLR 2020
Algorithm Fixed Point Propagation (FPP)
Input: a truncation parameter T, mini-batch size B, and number of updates per step M Initialize weights W and ,3 randomly
Initialize state So <- 0 E IRd
Initialize an empty buffer B size N for è 4- 1, do is full then
Remove the oldest transition
end if
Observe Or, Yr, and compute S, (w(()
Add (st, Yt) to buffer B
ift T then
for j + 1......... ,.M...M do
4 Multiple updates
Sample mini-batch of size B, of trajectories of length from the buffer:
[(s o; -........ S Oi (i,)) where i is the index of the /-th mini-batch
Compute the average mini-batch loss and update {s Si, 1 W and /
Update {s,, S, 18 l==1
in the buffer
end for
end if end for
algorithm can written as an instance of that framework and to show that each stochastic gradient update is unbiased. This convergence result, nonetheless, is key, it suggests that FPP is a sound strategy for using replay with RNNs. Previous attempts to use replay for RNNs, in reinforcement learning, were not able to show convergence (Kapturowski al., 2019), which is to be expected as truncated BPTT updates on a buffer may not be sound.
Additionally, show that as À approaches infinity, the set of stationary points of the FPP objective approaches the set of stationary points for the RNN objective. In our experiments, we use X = 1, obtaining precisely the same solutions the RNN objective is not our goal. We include this theoretical result nonetheless for completeness to characterize the relationship between the stationary points of FPP objective and the RNN objective. The proof is similar that for MAC-QP (Carreira- Perpiñián and Wang. 2014), with the main novelty in checking the KKT conditions for our objective and for linear independence in the Jacobian. Full proofs for both results
Appendix
4.1 CONVERGENCE OF FPP TO A STATIONARY POINT FOR A FIXED BUFFER
Recent work uses the idea of randomized gradient descent to show convergence to a stationary point for nonconvex objectives (Ghadimi et al., 2016), as opposed to typical restrictions such as convexity or the PL condition (Karimi et al., 2016). The randomized approach uses a random stopping time R, and characterizes the norm of the expected gradient for the variables at this random time. The variables we learn (W, S) R where is the appropriate dimension.
For the proof we also require the variables to remain in a closed, convex set, to ensure that our objective is Lipschitz. To do so, will analyze our update with the addition of projection operator onto a closed ball C in TR of radius > about the origin. r can be very large, and we emphasize that C' only convenience used for theoretical analysis. In practice, we do not project our iterates. Since d is Hilbert space and C² is closed and convex, we have the existence of unique projection operator T
T(Wo. Bg So)
arg min I(W So) (W3,,)) (W (W
(8)
Our objective is L(W33 N LWW B,S), for L, defined in Equation (6), for > T' samples. Each time we perform an update, we randomly sample k, ~ uniform-(T, inclusive of both endpoints. The update parameters time t, for stepsize a,,
(W Se4t
S.11) del
LL, (W 3,,
(9)

---

Published as a conference paper at ICLR 2020
Theorem 1. Let D be Lipschitz constant of VL(W.BB.. B.S). Define probability mass functions
a Da
(k((k=
2j=1 aj Da
for each N E N. Let R be distributed according to PN. Assume perform N stochastic updates. Write IR = (W R. BR: SR). Then
20 for all t and that we
[[an\V()n))]] =0 =0(N)
R
4.2 RECOVERING RNN SOLUTIONS
Consider the standard RNN problem,
min E(W,B,s) for E C.W.B,so) s0) def B.W.so
o.)).))))))) (10)
where we also optimize over 8n- Our goal is to show that for increasing A, the set of stationary points of the FPP objective in Equation (5) approach stationary points of the RNN objective in Equation (10), We assume T = 1 in our analysis of FPP.
Theorem 2. Assume we have a positive, increasing sequence {>a] + oo, a non-negative sequence {(x) O, and sequence of points ((W,; { such that [VT[(We Sz); Xx)1 S e
A |ss 2
L(W k. Bx. AE))
+ Σ (eUUw(SL1.0.):x)))
(11)
Assume further that {(W k., Bg, Su)} hus a convergent subsequence {(W ku BRG St,)} with limit (W' ). Then (W*, SS) is a KKT point of the constrained FPP objective (see (12)) and (W* , 8)) a KKT point of the RNN objective (10). Further, if (W*, W3,"". "*)) is a local min of the constrained FPP objective, then (W*, (6) is local min of (10).
5 EXPERIMENTAL RESULTS
We designed sequence of experiments in real and synthetic problems to evaluate new method compared with several common baselines and to highlight the robustness our method to different truncation lengths, buffer sizes and number of updates. In particular compare (1) against T-BPTT with a variety of truncation lengths greater and lesser than the temporal delay required to solve each problem; (2) No-Overlap T-BPTT, common variant of T-BPTT that updates disjoint partitions of the data; and (3) FPP without the state update, which is similar to the Stored State T-BPTT algorithm (Kapturowski al., 2019). We begin by deseribing the problems used to evaluate methods, and why they were chosen. Unless otherwise stated, we report average performance over all training steps (online performance), averaged over 30 independent runs.
Simulation Problems We used small simulation problems highlight the robustness each method to increasing temporal delay in online training. The first tasks is simple ring of states, called Cycle World. On each timestep the agent deterministically transitions to the next state in the chain. The agent's observation is zero in every state, except the last. The agent's 's objective is to predict the next observation, which is difficult without memory of length equal to the length of the cycle. With shorter memory, the agent cannot tell when the last non-zero observation, which is essential for predicting the next observation. This task has been used exclusively benchmarking k-Markov methods, POMDPs, and predictive state representations (Tanner and Sutton, 2005). The complexity of the task can be easily varied, and yet the determinism ensures the variance does not introduce confounding factors. At each time step, measure the prediction accuracy for the next observation.
We also experimented with a stochastic prediction task, where correct prediction requires remem- bering two independent observation's from the past. In particular, the target on the next timestep is probabilistically dependent on the one-dimensional observation 15 timesteps ago and 30 timesteps ago. The dynamics are summarised in Table in Appendix C. This task is called Stochastic World.
7

---

Published as a conference paper at ICLR 2020
For this problem, cross-entropy loss of 0.66 or higher indicates that the learned state did not capture the observation from either 15 or 30 steps in the past. If the state captures the observation from 15 time-steps ago the cross entropy loss is about 0.51. Optimal performance in this problem results in cross-entropy loss is about 0.46. Like Cycle World, Stochastic World requires a long and detailed memory of past observations, but the stochastic nature of the target pose additional challenge.
Real DataSets We also performed experiments on two fixed datasets, to gain insights into how each method performed on better known benchmark tasks. In both cases the data was processed and performance evaluated in an online fashion. The first problem is Sequential MNIST. The objective is to classify numerical digits based on stream of pixel inputs. On each timestep the input is one row (Ix28) of the image, and the target is the label of the image. We used an RNN architecture with 512 hidden units as in previous work (Arjovsky et al., 2015). It is not possible predict the target image base on few samples, so we wait until 15 steps (corresponding to 15x28 pixels) to begin measuring the error. Here, we report these incorrect predictions for the last 15 time-steps for every image. We ran this on 1000 images, which correspond to 28000 steps.
Finally, we also include results on a character prediction problem called Penn Tree Bank dataset. This problem is relevant because language modelling remains an important application of recurrent learning systems, and robust performance on this dataset can provide insight into the utility of our new method in application. We used vocabulary size of 10000. The Target Loss function used here a weighted cross-entropy loss for a sequence of logits. We used an LSTT with 200 hidden nodes as this architecture was found to perform well in previous work (Zaremba al., 2014).
Comparison to T-BPTT We compare FPP T-BPTT for varying truncation levels. For all the algorithms, we used a constant buffer size of 100 and the trajectory length T for both T-BPTTooverlap and no overlap versions) and FPP. All algorithms use (T) computation per step. For overlap T-BPTT, we employ T-BPTT online by taking each observation and updating with respect to the loss at that time-step, using a T-step truncated gradient. The no-overlap version of T-BPTT performs a batch update for every T observations, such that these observations do not overlap.
Additionally, we include UORO (Tallec and Ollivier, 2017) as another baseline. UORO uses an unbiased rank-1 I approximation to approximate RTRL. It is relatively new method for training RNN online, and has only been tested on small scale datasets. In our experiment, we include memory-1 and rank-1 UORO in Cycleworld and StochasticWorkks
We first compare the performances of FPP and T-BPTT on Cycleworld with varying p. We expect T-BPTT to degrade with T less than the dependence back in time (the length of the cycle p): we therefore test both T = and T = p/2 for increasing p. To make the results comparable across p. we report performance as the ratio we can see that FPP is more robust to T, whereas T-BPTT with '' = p/2 performs poorly even when given more data (Figure 2(b)). In early learning, with fewer samples, FPP has an even more clear advantage. Even though T-BPTT can eventually learn optimal predictions for T = p, it takes longer than FPP which learns near optimal predictions in early learning (Figure 2(a)).
simple baseline of predicting 0 at every time step. From Figure
We additionally compare FPP and the two variants of T-BPTT across all four problems, under different settings of T, shown in Figure 3. Across all problems, FPP outperforms the other two for every T, except T = 1 in CycleWorld where all three methods perform similarly. The performance of FPP is notably better for smaller T, as compared to T-BPTT. For example, in Figure 3(b) 20-BPTT has a high loss and is unable to learn both the dependencies, whereas FPP with T=20, performs almost as well as 40T. Similar conclusions can be made for T E {3, 5} in (a), T E {10, 15, 20, 30} in (b), T E (7, 14, 28} in (c) and T E (1,5, 5, 10, 20} in (d).
Benefits of manc-batch updates and multiple updates per step One of the advantages of using a buffer is the ability to perform mini-batch updates and multiple updates per step. We evaluate the performance of FPP with and without state updates using M updates per step and a mini-batch of size B. We show the performance with varying T'. To show the effect of multiple update, we fix B and vary M E {1, 2, 4, 8, 16). To show the effect of mini-batch update, we fix M and vary B E (1, 4, 8, 16). We use buffer size of 1000 and 10000 training steps.
We also include FPP without state updating, to determine if the benefits of FPP are mainly due to using buffer rather than due to the new objective to learn explicit state variables. We particularly expect FPP to outperform FPP without state updating under more updates per step, because we showed converge for FPP a fixed buffer whereas no such result exists for FPP without state
8

---

Published as a conference paper at ICLR 2020
p-Cyelhhorre
p-Cydlettoii
TGPFT(TTP))
T-8PT(T-p))
T@PTT(T-p(21
1.0
T-8-IT/T-(21
pesTept
PPRT-P)
(PPIT-p/2)
PARI-pP22)
Rato Eror
Enor 0.6-
Rado
neppes
reppert
044
me
Boad
0.2
0.2
p-d
p-3
p-12
p-16
Cycle Langth
Cyclo Langth
(a) Early Learning (2500 steps)
(b) Learning with More Data (15000 steps)
Figure 2: The ratio error each the algorithms with respect the baseline of predicting every time step is our measure of performance. For all the values of p. FPP seems to be more robust to T., especially with larger The numbers are average over 30 runs with standard error bars.
20
HPP JOAD
Crasa
Predictiona (96)
Entropy
Loes
kans sutt Opperimcns
T-1
T-2
T63
T-40
T-20 Trunsation
Truncation parameter
(a) CycleWorld
(b) StochastieWorde World
T-IFIT no sectip BPIT
1:21
revovaata T-FTT
7.2
Incorect Predictions
Cross Entropy Loss
(56)
Truncation paramator
Truncation pansmeter
(c) Sequential MNIST
(d) Penn-Tree Bank
Figure 3: Average online performance for FPP (red), T-BPTT (orange) and No- No-Overlap T-BPTT (bluc), Across all the domains, FPP seems to be more robust to T, and it does much better than T-BPTT especially for small T. The numbers are average over 30 runs with standard error with (a) being steps, (c) for 1000 images (28000 steps) and for 5000 steps (5000 points in dataset, processed in order). FPP 20, 30, reaches final solution with optimal performance; it only above the second line hecause the plot shows average performance across all steps, rather than final performance.
for 5000 steps. (b) for 10000
updating. Here, the buffer is not fixed, but performing more updates per step should move the FPP solution closer a stationary point of the current buffer.
Figure 4 (a) and (b) shows the effect of multiple updates and (c) and (d) the effect of mini-batch updates. For both, increasing the number of updates and the size of the mini-batch improves performance, except for a bit of overfitting we observed in Stochastic World for increasing updates (B 1, M = 16). However, in general, FPP can better take advantage of both multiple updates and mini-batch updating. The most noticeable gaps are for T 16 and T' 32 in Stochastic in CorleWorld. The theory suggests that more updates, even with T = 1, should allow FPP to converge Appendix C), and find that for both larger mini-bane batch and number of updates FPP can get the error down zero, whereas FPP without state updating cannot.
and T = 1 and
reasonable solution. We test this Cycle World (with Figure 7 in

---

Published as a conference paper at ICLR 2020
T=1
10
Incorrect Predictions
Incorrect
Predictions
(%)
(96)
FPP
FPP vithout state updating
16
16
M
(a) Multiple Updates CycleWorld (B 1)
(c) Mini-batch Updates in CycleWorld (M
1)
0.70
T=8
0.68
T=8
5. T=16
0.64
Cross 0.66
Cross
Entropy 0.64
Entropy
Loss
0.62
T=16
Loss
T=32
0.60
T=32
0.59
0.56
2
16
M
B
(b) Multiple Updates in StochasticWorld (B
(d) Mini-batch Updates in Stochastic World (M 1)
Figure The performance for increase number of updates (with mini-batch of B = 1) and increasing mini-batod size (with number of updates M 1). The numbers are average over 30 runs with 10000 training stops. The solid line is FPP and the dashed line is FPP without state updating.
CONCLUSION
The main objective of this paper reformulate RNN training to explicitly learn state variables. In particular, the goal is to investigate methods that can better distribute computation, and improve state updating without having to compute expensive-ant potentially unstable unstable-gradients back in time for each state. We introduce new objective to explicitly learn state variables for RNNs, which breaks gradient dependence back in time. The choice of T to compute gradients back time is used only to improve training speed, rather than effectively approximate gradients. We found that our algorithm, called FPP, was indeed more robust to T, than truncated BPTT was to its truncation level. We proved that algorithm converges to stationary point, under fixed buffer, and is sound approach to using buffer to train RNNs. Further, we chose simple optimization choices in this work; there clear next steps for benefiting more from the decoupled update, such by parallelizing updates across state variables. Overall, this work provides evidence that FPP could be promising direction for robustly training RNNs, without the need compute or approximate long gradients back in time.
REFERENCES
Luis B Almeida. A learning rule for asynchronous perceptrons with feedback combinatorial environment. In International Conference Neural Networks, 1987.
Martín Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. CoRR, abs/151 1.06464, 2015.
Dimitri P. Bertsekas. Constrained Optimization and Lagrange Multiplier Methods. Academic Press, 1982.
Victor Campos, Brendan Jou, Xavier Giró Nieto, Jordi Torres, and Shih-Fu Chang. Skip RNN: learning to skip state updates in recurrent neural networks. CoRR, 700.00448.,684, 2017.
Miguel Á Carreira- Pereiira-eerpnnn and Weiran Wang. Distributed optimization of dceply nested systems. In International Conference on Artificial Intelligence and Statistics, 2014.
10

---

Published as a conference paper at ICLR 2020
W. Chan, N. Jaitly, Q. Le, and O. Vinyals. Listen, attend and spell: A neural network for large vocabulary conversational speech recognition. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2016.
Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael J. Witbrock, Mark Hasegawa-Johnson, and Thomas S. Huang. Dilated recurrent neural networks. CoRR, abs/1710.00222 2017.
Junyoung Chung, Sungjin Ahn, and Yoshua Bengio. Hierarchical multiscale recurrent neural networks. CoRR, abs/1609.01704 2016.
Wojciech Marian Czarnecki, Max Jaderberg. Simon Osindero, Oriol Vinyals, and Koray Kavukcuoglu. Understanding Synthetic Gradients and Decoupled Neural Interfaces.
2017.
Siegmund Düll, Steffen Udluft, and Volkmar Sterzing. Solving partially observable reinforcement learning problems with recurrent neural networks. In Neural Networks: Tricks of the Trade, 2012.
Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):79-211, 1990.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):267-305 2016.
Akhilesh Gotmare, Valentin Thomas, Johanni Brea, and Martin Jaggi. Decoupling Backpropagation using Constrained Optimization Methods. 2018.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey E. Hinton. Speech recognition with deep recurrent neural networks. CoRR, abs/ 303.5778, 2013.
G. Hinton, L. Deng, D. Yu, G. E. Dahl, Mohamed, N. Jaitly, A. Senior, Vanhoucke, P. Nguyen, T. N. Sainath, and B. Kingsbury. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, (9(6):82 97, Nov 2012.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 1997.
J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedingss of the National Academy of Sciences, 7954):2554-2558 1982.
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 Machine Learning, 2017.
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney, Recurrent experience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewccz condition. In European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2016.
Nan Rosemary Ke, Anirudh Goyal, Olexa Bilaniuk, Jonathan Binas, Laurent Charlin, Chris Pal, and Yoshua Bengio. Sparse Attentive Backtracking: Long-Range Credit Assignment in Recurrent Networks. I 250900220022,..... 2017.
Jan Koutník, Klaus Greff, Faustino J. Gomez, and Jürgen Schmidhuber. A clockwork RNN. CoRR, abs/1402.3511, 2014.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard S Zemel. Reviving and Improving Recurrent Back-Propagation. In International Conference on Machine Learning, 2018
Jiasen Lu, Caiming Xiong, Devi Parikh, and Richard Socher. Knowing when to look: Adaptive attention via A visual sentinel for image captioning. CoRR, abs/1612.01887, 2016.
11

---

Published as a conference paper at ICLR 2020
Junhua Mao, Wei Xu, Yi Yang, Jiang Wang, and Alan L. Yuille. Explain images with multimodal recurrent neural networks. CoRR, abs//1110. 1090, 2014.
Soroush Mehri, Kundan Kumar, Ishaan Gulrajani, Rithesh Kumar, Shubham Jain, Jose Sotelo, Aaron C. Courville, and Yoshua Bengio. Samplernn: An unconditional end-to-end neural audio generation model. CoRR, abs/ http//1120777777 2016.
Yajie Miao, Mohammad Gowayyed, and Florian Metze, Eesen: End-to-end speech recognition using deep models and wfst-based decoding. CoRR, abs/1507.08240, 2015.
Asier Mujika, Florian Meier, and Angelika Steger. Approximating real-time recurrent learning with random kronecker factors. In Advances in Neural Information Processing Systems, pages 6594-6603, 2018.
James M Murray. Local online learning in recurrent networks with random feedback. eLife, 8:e43299, 2019.
Daniel Neil, Michael Pfeiffer, and Shih-Chii Liu. Phased LSTM: accelerating recurrent network training for long or event-based sequences. CoRR, abs/1610.09513. 2016.
Yann Ollivier and Guillaume Charpiat. Training recurrent networks online without backtracking. arXiv, 2015.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning. 2013.
B. A. Pearlmutter. Gradient calculations for dynamic recurrent neural networks: a survey. IEEE Transactions on Neural Networks, 1995.
Fernando J Pineda. Generalization of back propagation to recurrent neural networks. Physical review letters, 1987.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61 2008
Benjamin Scellier and Yoshua Bengio. Equilibrium Propagation: Bridging the Gap between Energy- Based Models and Backpropagation. Frontiers in Computational Neuroscience, 2017.
Corentin Tallec and Yann Ollivier. Unbiased Online Recurrent Optimization. arXiv:1411.40002 [cs.LG], 2017.
Brian Tanner and Richard S. Sutton. Td(lambda) networks: Teepporll-differencce networks with cligibility traces. 2005.
Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, and Tom Goldstein. Training neural networks without gradients: A scalable admm approach. In International Conference Machine Learning, 2016.
Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator. CoRR, 0bss/141..44 1.4555, 2014.
P. J. Werbos. Backpropagation through time: what it does and how to do it. Proceedings of the IEEE, 18510):150011560, Oct 1990.
Ronald J. Williams and Jing Peng. An efficient gradient- based algorithm for on-line training of recurrent network trajectories. Neural Computation, 1990.
R. J. Williams and D. Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 1989.
Ronald J Williams and David Zipser. A Learning Algorithm for Continually Running Fully Recurrent Neural Networks. Neural Computation, 1989.
Wojeiech Zaremba, Ilya Sutskever, and Oriol Vinyals. Recurrent neural network regularization. CoRR, 0tt//409.2332/ 2014.
12

---

Published as a conference paper at ICLR 2020
A FULL PROOFS
A.1 CONVERGENCE ON A FIXED BUFFER
At first glance, the update (9) is different than the update in Ghadimi et al. (2016, p. 276). Nevertheless, the following lemma guarantees that they are indeed the same.
Lemma 1. Let f be L or stochastic sample of and les >> 0. Write (W,,3)) Then
arg min uEC
(V](o): u) + 2a x
1
=: w1l2 = arg min = uEC
Proof.
The proof is straightffrrwad calculation.
arg min {||u (x [V\(()))) arg min MEC
{Iuu- x=12 a² (2(1V[(x))) 2
NEC
arg min [llu~~||* 2a vf())))
REC
arg min
(V)())) + 2a
x - 2 12
wEC
Our goal apply Corollary 3 of Ghadimi et al. (2016, p. 282). We must show that Vg is Lipschitz on C' and demonstrate that Assumption A1 in Ghadimi et al. (2016, 268) holds.
Lemma 2. L Lipschitz on C.
Proof. A function is Lipschitz. if it gradient is bounded. Since I. is smooth and C' is compact (continuous functions on compact sets are bounded), this lemma follows.
Lemma 3. Li is unbiased estimate of LL, where k uniform-(T, n).
Proof. The terms in VL corresponding to the gradients of W and β3 are exactly Vw L and VgL in expectation, given that i uniform- (T,
Let us consider the gradient elements corresponding to the parameters sp.-- For shorthand, define Ja b) := {a, a + 1,... b 1, b). Deñin P. == n - T]. P: == [T n]. If Po, then 8y predicts future states. If sj E Pı, then sy is predicted by other states in the regularizer terms of L. Note that Po and P1 are not disjoint. First, we calculate.
( ((( - M(Sj+T 8y+T)) ( if E P
M(s; 8n) if E PC nP
V,, ((W. :
MMss -b,) + (V
- V
if E P
0 if pC pf
j Po n Pf, then sy does not show up the target (i.e., the term that is not šy) in any regularizer term of L. Hence, Vs, Ly is zero with probability n-74I- and is Lo 4/+T) X(5++- - (V with probability R-74I
If j Pf n P1, then sy only shows up target in regularizer term, so V La is zero with probability - and is otherwise - A(s, šy).
j E Pon then V,, La is zero with probability - T- M(s, - -5,) with probability 7-7
and (V ( (o(5)T3:84+)
A(5HTT - $)+r)) T V,, with probability --7+I
The case for j E P8 n PC is trivial. Consequently, E[V,, La] V L for all j E (0....,,1 ,n).
13

---

Published as a conference paper at ICLR 2020
Lemma 4. The variance of V Ly is bounded C.
This follows because VL and VL are both smooth functions on compact set C, and thus bounded.
Proof.
Theorem 1. Let D be Lipschitz constunt WWW.WBWB... Define probubility mass functions
Pn(k)= = akk Da
ΣE=1 a3 Da
for each N E N. Let R be distributed according to Pn. Assume perform N stochastic updates. Write In = (W n. Fz. Sn). Then
2D for all t and that we
E
[[RR\L(E)))] =
N
Proof. The 9x.8 (defined in Ghadimi et al. (2016, 271, 274)) in Corollary 3 of Ghadimi et al. (2016, p. 282) corresponds in our case the following.
1
2a || u11 })
O'R arg min (Vf(z), + REC
9x.8 ==
(IR - P(ZR- - aRVL(zR)))
OR
In the last line, we use Lemma Since we project based on squared norm distance in (8) (corre-
sponding to w(x) } || in Ghadimi al. (2016)), the in Ghadimi al. (2016, p. 271) (not step-size a²) can be set to
After applying Lemma 2, Lemma 3, and Lemma have from Corollary 3 of Ghadimi et al. (2016, p. 282) that
E
[(IR ag VL
=πIl? =
The only thing left to check is that l'IRR oR V((RR) IR I(VL(xR)).
T(æR - aR C. VL(xn)) - TR = arg min
{||u (I - ([)))\)) FR
uEC
arg min
{||u- vl(xx))]
NEC
= [(axVL((R))
A.2 RECOVERY OF RNN SOLUTIONS
Recall our goal is to compare to the RNN solutions (10).
U(W,3,s) = Σ follw( (--. (f 01), 1 ,.);y:)
(10 revisited)
1=1
min ((W.3.8))
8, W,W.
Let us also write constrained version of the above problem, which we will use in the analysis of FPP.
Epp W, So, ... ,.) = Σ (aal/w(s-1100):.1
(12)
1=1
s.t. visiS nnn.nnff(ss111 =s;
min Esp (W WWB, so. ,k)))
W W.B.von
14

---

Published as a conference paper at ICLR 2020
The idea is that FPP can be viewed as way solve the problem (12) and thus (10) through quadratic regularization.
We will use 80m shorthand for (so.... ... S. which in the main paper we labeled as S, but for this proof it will be convenient to use explicit variables. Define the feasible set of (12) as
Ω = ((W, So:) W E :s E R;; V1 n, 8; -
Proposition 1. Let (W", 3"" (t) be local min of (10). For 1 S i S n, define recursively sf == fw- 1,, 0z). Then (W", G s.n) ) is a local min of (12).
(W*, 3 sh.)) be local min of (12). Then (W", , a local min of (10).
Proof. First, let N Ru+b+k be neighbourhood of (W*, f si) such that v(W, B,so) E N, have
F(W" ,,",, F(W, 8p))
Without loss of generality, we may take N to be open. Otherwise, by definition of a neighbourhood. we may take a smaller open set around (W*, , si) by definition of neighbourhood and call that set N.
Let st defined as above. Define M since N is open. Let (W, 3, Su.n) E M N... Note that (W, B, so) E N. By definition of Q we have that fw (8;-1, 0;) S;. Hence, Es (W 80.n) = E E(W; B, so).
Rink which is an open neighbourhood (W', ,33,sh
By definition of (12), (10), we have ([WW", .)) = Efpp W , ,.m)) Finally,
Fr W* ,ū.)) E(W", ,3" si) S F(W, 3, so) = E (Tpp(W. (W W. S..n).
For the second part of the proof, assume (W*, ,"" Sū.n) is a local min of (12), meaning there is neigbourhood M C R (a+1)) of (W", , si..) such that for every (W, 3, sp:n) E NΩ2
Esppl ( ,3" s Espp (W B, som).
Similarly, without loss of generality, we can assume that M is an open ball, so we may write for some 0, M BeW S.:.)
We will construct an open set N C Rw-b+h such that (W* 3", 8h) is local min with respect to N. Define the projection onto the first w + b + k indices. Define N 7M (T). Let show that N is open.
We will write (5 mean {fw(so, 01), fw(ww(... (So. o1), 02), ....,))))
We can write N as
N ((W,3,so) (W,3, Som) SNn (W" ,
(,W,3,ss) (W, W, www.::wwwnnoooooooo 01m1) (.W"" 3 spm))
((W,3, (p))) [I(W, 33 So, hww////mmmm...
(W* 3 smn) < c)
On the second line, we used the fact that s; fw(s,-1, in Ω. Since the norm and f are continuous and (-oo, e) is open, we have that N, continuous preimage of an open set, is open. Now, let (WBB,s
(, so) N such that Esis with (W, B, 8om) E M n
E(W". sh) Efpp (W* 3 s.n) Espp (W, B, Sum) E.W, 3,
The claim follows.
Proposition 2. The first order KKT equations for (10) andfor (12) are the same.
Proof. Given (W*, s)), for < S n define ă; = fw fw(1,-1, o,), where än := sj. If we write afw- (81,041) for instance, this is taken to mean the gradient of fw- (5t, 0141) with respect to the Us:
function arguments corresponding št Furthermore, when writing 9fw- (Z,,0.))
only mean the gradient with respect to the parameters of the outer fw-, and not with respect to any of the parameters of 85.
SW
15

---

Published as a conference paper at ICLR 2020
Using the chain rule for the first and third equations below, the first order KKT conditions for (10) are given by
OE(W', 3 8b)
Ob (/w- (So. 01);21)
0.w- (sh: +
(13)
OW
Ofw
OW
deg. (fw- (3,, 0f+1)::4)1111
Ofw
O.w- (3j. Oj+1)
0 0sw 06,,0
05w- (st- 0:)
EII
OW
Os:
ow
OE(W", ,8")))
Obg- (fw (1-11,0)::11)
=0
(14)
0
03
1=1
OE(W*, ,W",,""","" ,8",)) ..)
Ol (Jw- (s6. 01)iv1)
Obp (5,,
(15)
Ofw
Ofw
3 fw. (5), 01+1)
))
① fw- (si, 01)
Os
Oso
The Lagrangian for (12)
fpp W B. S0.n)
Σ (alUw(ss-100):))) (W - -s;),
(16)
where A E R for 13 are Lagrange multipliers. We define À = for convenience, The
KKT equations for (16) are
fp pmp W H Sun)
n Ol (Jw- (s v:): Ofw- (s 0:)
(17)
OW
Ofw
OW
05w- (s) =0
X
OW
0. pp (W*, 0 )
n
06 (Jw- (
03
0
XI
if j = n
0.L lvpl 110 W- ,9" (
X
+
Ogge (sw- (8, 00:11)11111)) {f+11
0/w- (8) 00411
(18)
0s;
Jjw
iosjjnn
5 fw 1,), visisn
First, let find closed-fome fore expression for X;-
Lemma 1. Let S $ n. Then
O6z. (fw- (s), o.+1): Mit1)
0fw (st, Os:
27= =
05w
[m]
Proof. We proceed by induction. The base case and the case true for m + 1 > 0. We will show the claim for j = m. Using the KKT equations (17) and the induction hypothesis,
are trivial. Assume the claim
16

---

Published as a conference paper at ICLR 2020
O6 (fw- (S 000 0 Vm++l)
0fw-(s mm
Xm+1
Ofw
dsm
Olg- (fw (s Om+1): vm++1
Olz. (fw- (5,, 0 M6t1)
Ofw
Ofw
1=++1
Ofw (111))1))
Ofw- (s Om+1)
Üst
3mm
[=++1
Olg (sw- (sin Om 1) vm++1
Ofw- (s Om++1)
Ofw
dsm
Bl (fw- (s,, 0.411:
① ffw- 0141) 0fw- (s 0m+1)
II
Ofw
Os:
Osm
i=#+1
1=m+1
Obg (Sw- (s", oc 0.+1):9441
3 ff (5/ 01+1)
Σ
Ofw
Øs:
Now, we will show that the sets of equations are the same. First, it is clear that the two equations involving gradients of 3 in (13) and (17) are the same given that the constraint must be satisfied in (17). Now consider the equations involving gradients with respect to W.
0.L. fpp OW
Ol (fw- (s o.):y;) Ofw (s
0jw
OW
Olg. (5).
i
(fw. Osi
0fw- (s o;) aW
J/w
1=1
Olg (fw- (8 0,): 0fw- (5)- +
Ofw
aw
Ol (Sw 1541)
i fw 0141)
0f.. o.)
Ofw
Os
OW
1=1
Gg (ww-(s) 01): Ofw (5% 01)
n-1
Oég (fw- (8) 0541):3/1)))
+
0ßw
OW
0ʃw
Ofw 05+1)
2 0fw (5),
Ofw. (s
EI 1=
ow
Os:
ow
0.
By substituting in the constraint equations S = (s this recovers exactly the gradient with respect to W in (13).
17

---

Published as a conference paper at ICLR 2020
Finally, consider the gradient with respect So-
1 pp (W*, (..))
OEl (fw-(sh: 01):11)
Ofw- (s..
No. +
27)
080
Osw
Oso
Olg (fw- 01):31)
dez (Sw- (8, 01+1):
Ofw
Ofw
ww (57, (81,
)
3 w- (sh
Os:
Oso
This matches the corresponding equation (13).
Proposition 3. Let (W*, Sünn) be a local min of (12). Write the constraints of (12) as vector: h(W, Sq:) == [[, 01) - $1)
(fw(s=-1, - s
(19)
Index each element of h by h2 Then the vectors h,; (W ,80)) are linearly independent.
Proof. In the following, will write Ølg). az)
to mean the derivative of the 1-th component of g with
respect to the i-th component of 2y.. For compactness, write g(i) fw- fw- s. We can write the Jacobian V/ (W", sün)) as
8(g(1)); 8W
8[g(1))
0[o(1) ast
0(o(1))
8|g(1]
8w
0x
((g(1)
(g(())
(1(()))
8 d le d 0x
8 (la dakk #|a(2) Jehi
Vh( W' .
OW
Ow"
8a [|a(2) da
8(g(2))
0la(2))
ow
aw
Big(n)a l
ala(n
[g(nn] def
Hig(n)]
OW
oW
0sf
Oshi
We will show that the rows of Vh W
si.) are linearly independent. To this end, let Azy R for
i (1, ,n). j E (I. 1} such that:
Xi (l - -s, = 0.
In particular, for 1 < a < n, 15 Sb
Øffw (s -771
b
81 1 Ölf (5)
A
Aij
82
(20)
0sh
Ost
1=1
j=1
Ølfw (s on
lazn
Aat1.
-ab
(21)
0sh
j=1
=
(22)
By setting a = n, we have that Ans for all 1 < b < k. Setting a = - 1, we similarly have that Ax-1,b 0. Proceeding in this fashion, have that Aub 0 for all S I n, 1 < b < k. Actually, we did not at any point use the fact that (W*, ",",, st.n) gradients are linearly independent everywhere, and in particular (W*, H )
a local min, so that the constraint
18

---

Published as a conference paper at ICLR 2020
Theorem 2. Assume we have positive, increasing sequence {Ax} cc, nen-ntat sequence {c+} - 0, and a sequence of points {(W Br. } such that [VL(W Be, Sa); >s)1l I Ej e
L(W k. Bg. Sa); AR) 06t Σ (e(fw(s-1,,.):x))) + ss - ,,
(1I)
Assume further that {(W k. Bg. } has a convergent subsequence {(Wk: k.s 3R.- Sk,)) with limit
(W* (* Then (W*, ",,"")) is a KKT point of the constrained FPP objective (see (12)) and
(W*, 8 (8,)) a KKT point of the RNN objective (10). Further, if (W", ,3"" ,S*) is a local min of the constrained FPP objective, then (W", 8%) is local min of (10).
(W",3",
Proof. By Proposition 3 and Proposition 2.3 from Bertsekas (1982), We have the existence of a Lagrange multiplier vector À such that
5 (W , S(.. Vh(W', . ) 0, (W"
h ((W" .p.)) = 0,
where h (W', , .Sin) is as in Proposition 3. Hence, (W*, Som) is a KKT point of (12).
By Proposition 2, (W*, W"',"", .8)) is a KKT point for (10). Finally, (W*, , s.n) is local min of (12), then by Proposition 1 we have that (W", s)) is local min of (10).
B PARAMETER STUDY
We investigate the sensitivity of FPP to its two key parameters: the length of the trajectory T, and the buffer size N. Overall, the losses on y-axis of Figure show that FPP is robust buffer size and truncation length. As expected, for very small T. performance degrades, but otherwise the move from T= 10 T= 50 does not result in large difference. The algorithm was quite invariant to buffer size, starting from a reasonable size of 100. For too large a buffer with a small number of updates, performance did degrade somewhat. Overall, though, across this wide range of settings, FPP performed consistently well.
10-OychWAbrid
StochasticWaiid
un g0o
122
Rulo un -0000
craditionn
Entopy Loss
(%)
12
713
Truncasion pararrate star
Truncation parameter
(a) Wolld
(b) Stochastic World
Figure 5: Sensitivity to buffer length and trajectory length in FPP, for buffer sizes 100, 1000 and 10000 and truncations of 1, 5,10,15 and 50.
We also investigated how performance changes when changing X. Throughout all previous exper- iments, we simply set À = 1, to avoid unfairly tuning our method to each problem. Interestingly, tuning does enable further performance improvements, though the algorithm worked well for quite a large range of X.
C EXPERIMENTAL DETAILS
The dynamics for the Stochastic World environment are in Table
For all experiments. (0.0001, 0.0003, 0.001, 0.003, 0.01, 0.03) based on the average accuracy/loss. For real datasets, use multiple trajectories to speed up training. The details of each task are provided below:
RMSprop optimizer and the learning rate is chosen over the set
19

---

Published as a conference paper at ICLR 2020
10 CyckiWordd
StochsslcWWbrd
T-t
incornet Predictions
Cross
(6)
Erroyy
Tw10
T+3
T+20
T=00
Twd0
61
(a) 10-CycleWorld
(b) Stochastic World
Figure Sensitivity of Lambda various values For small T, higher lambda works better suggesting impact of propagation of state values across the buffer.
P(Y.
1100-1,001-1
O1-T;
Op-Ta
50%
0
0
100%
1
0
25%
75%
1
Table 1: The conditional probability the target output given the past ohservations.
FPP without updating
Incorrect 8-
Predictions
(%6)
0
M
Figure 7: performance FPP and without state updating with T' 1, B 16 50000 training steps, for varying M. This result highlights that FPP can better take advantage more updates and larger mini-batches, with its sound updating strategy on buffer.
C.1 CYCLEWORLD
Network Type simple RNN Hidden Units 4
C.2 STOCHASTIC WORLD
Network Type simple RNN
Hidden Units 32
C.3 SEQUENTIAL MNIST
Network Type simple RNN
Hidden Units 512 Image Size 784 pixels
Input Dimension = 28 pixels
Number of Steps 28000 (1000 images of 28 steps)
20

---

Published as a conference paper at ICLR 2020
Number of Trajectories 20
C.4 PTB
Network Type LSTM
Hidden Units = 200
Vocabulary Size 10000
Embedding Size 200
Number of Steps 5000 (5000 samples in the dataset)
Number of Trajectories = 20
21


Reviews:
[{"review_id": "SyeisMCatH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "The paper proposes an alternative to the truncated back-propagation through time (BPTT) algorithm for training RNNs. An online setting is assumed, which I understand as training RNN as data arrives and not storing too much of the arriving data (although notably the proposed method uses a buffer). The proposed Fixed-Point Propagation algorithm works as follows. It maintains a buffer of the last N RNN states that can be updated. From this buffer at every time step it samples two states that are T steps apart from each other (s_i and s_{i - T}). The RNN is run for T steps starting from s_{i - T}. A loss function is constructed that takes into account the output loss at time i as well as the mismatch between s_i and the new state constructed by running the RNN. The states s_i and s_{i-T}, as well as the RNN parameters are updated based on this loss function. \n\nThe novel idea of the paper is therefore a modifiable state buffer for the RNN states. The goal is better computational efficiency than that of T-BPTT. \n\nThe paper is mostly clearly written, but I think it is absolutely necessary to move Algorithm 1 to the main text, as well as to add the mini-batch processing (B) and multiple updates (M) to it. This pseudocode was very instrumental for me to understand the algorithm. I confess that I did not read the theory; I don’t think it’s super relevant because in practice convergence to fixed-point will require too many updates. \n\nThe empirical comparison with T-BPTT is substantial, but the waters are muddied a bit by imprecise presentation of baselines. For example, when T-BPTT is used for e.g. language modelling, it doesn’t make sense for back-propagate the loss from only the last time step, losses from all time-steps can be back-propagated together. Was this done in T-BPTT and/or FPP? Does T-BPTT use the 100 step buffer somehow? NoOverlap T-BPTT is not explained very well. A very interesting and absolutely necessary baseline is FPP without state updates, but for such a baseline the loss comparing s_t and s_{i-T} should be disabled. Was this done?\n\nIn short, the paper must clear show that updating the states in the buffer allows to get same performance with smaller T, compared to the best possible baseline that also uses the buffer but does not update states in it. I am not sure this case is clearly made at the moment.\nOne further direction authors could explore is that using a very small T but larger B could be more computationally inefficient because parallel computations would be used instead of sequential ones. Besides, from a practical viewpoint and I think it could make sense to also update intermediate states, and not just s_i and s_{i-T}. \n\nOther remarks:\n- the legend in Figure 4 is a dashed line, but the curves in the plots are dotted\n- the max. cycle length in CycleWorld is not clearly explained in the text, the name CycleWorld is not properly introduced\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SkeYFd2EqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "In this paper, the authors reformulate the RNN training objective to explicitly learn the state vectors, and propose an algorithm called Fixed Point Propagation (FPP Algorithm 1). The authors motivate the derivation of FPP in Section 3, provide some theoretical convergence results in Section 4, and demonstrate experiment results in Section 5.\n\nIn general, this paper is interesting and well written. The experiment results in Section 5 seem to be very strong. However, I am not familiar with the relevant literature, thus, I am not sure if the authors have compared with the strongest baselines in this field. \n\nI think the paper suffers from the following limitations:\n\n1) Theorem 1 shows that the FPP algorithm converges to a stationary point. However, this result seems to be too weak. Can we say something about the stationary point? Is it a local minimum under some conditions?\n\n2) In the experiments, the authors choose \\lambda=1. My understanding is that \\lambda is a key meta-parameter of FPP. Please do a better job in justifying this choice.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lOzsLcFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "\nBackground: The authors consider the problem of training RNNs in an online fashion. The authors note that RNNs are trained using BPTT, which prevents them from being trained in an online fashion.  There have been various approximations which has been proposed which are based on RTRL or approximations to RTRL, as current approximations based on RTRL has high computational complexity. \n\nProposed Method: The authors propose to learn the state of the RNNs explicitly by improving the prediction accuracy at each time step as well as predicting the \"next\" state of the RNN. The authos note that the constraint of predicting the next state  is a fixed-point formula for the states underthe given RNN dynamics.\n\nClarity of the paper: The paper is clearly written. \n\nRelated work : Most of the relevant related work has been covered in the paper and discussed. I like it. These two related work could also be cited. Here, authors approximate the RTRL with random kronecker factors.\nhttps://papers.nips.cc/paper/7894-approximating-real-time-recurrent-learning-with-random-kronecker-factors\nhttps://www.biorxiv.org/content/10.1101/458570v1\n\nExperiment section: The authors evaluate the proposed method on both synthetic as well as real experiments. \n\nSimulation Problems: The authors use simulation problems to note the robustness of the proposed method to increasing termporal delay in online learning. These tasks show the soundness of the proposed method. Its actually difficult to tell how the proposed method is performing because of the selection of tasks. It might be more interesting to choose same tasks as in UORO paper (https://arxiv.org/abs/1702.05043) and it could be another \"baseline\" for the proposed method.\n\nAblations: I liked the fact that the authors consider conducting experiments without state updating, as it could also be  due to using a large buffer rather than explicitly optimizing for the prediction objective.\n\n Positive: The proposed method could be interesting for learning the state representation for policy gradient RL methods (specifically POMDPs) as the proposed method can leverage use of mini-batches, as well as multiple-updates which is a crucial ingredient to make best use of data collected by the agent interacting with the environment. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an alternative to BPTT for training recurrent neural networks based on an explicit state variable, which is trained to improve both the prediction accuracy and the prediction of the next state. One of the benefits of the methods is that it can be used for online training, where BPTT cannot be used in its exact form. Theoretical analysis is developed to show that the algorithm converges to a fixed point. Overall, the reviewers appreciate the clarity of the paper, and find the theory and the experimental evaluation to be reasonably well balanced. After a round of discussion, the authors improved the paper according to the reviews. The final assessments are overall positive, and I’m therefore recommending accepting this paper.
Decision: Accept (Poster)