TRAINING RECURRENT NEURAL NETWORKS ONLINE BY LEARNING EXPLICIT STATE VARIABLES
Year: 2020

Abstract:
Recurrent neural networks (RNNs) allow an agent to construct a staterepresentation 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.

text: Recurrent neural networks (RNNs) allow an agent to construct a staterepresentation 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.

heading: 1 INTRODUCTION
text: 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 a history can improve accuracy, but can require a long history when there are long-term dependencies back in time. Recurrent Neural Networks (RNNs) (Elman, 1990; Hopfield, 1982) learn a 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 et 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 et 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 to make a new prediction. RNNs are typically trained either using Backpropagation-through-time (BPTT) (Werbos, 1990) or approximations to 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 is truncated BPTT (T-BPTT) (Williams and Peng, 1990) which only computes the gradient up to 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-term 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.
Recently, there have been some efforts towards approximating gradients for back-propagation, both for feedforward NNs and RNNs. Synthetic gradients and BP(λ) (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 et al., 2017). There are several methods that approximate RTRL—which is itself an approximation of the true gradient back in time—including 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 a Kronecker product decomposition to 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 et 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, we investigate an alternative optimization strategy that does not attempt to approximate the gradient back in time. Instead we learn the state variables in the RNN explicitly. These new variables are optimized to both improve prediction accuracy, and to maintain consistency in producing the next learned state variables. This second constraint is a fixed-point formula for the states under the given RNN dynamics.1 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—across a 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-term dependencies, and improves over T-BPTT, particularly in terms of stability and computation.

heading: 2 PROBLEM SETTING AND BACKGROUND
text: We consider a partially observable online setting, where an immediate observation is not sufficient for prediction. More formally, assume there is a sequence of n observations, o1, . . . ,on, which provide only partial information about an unknown underlying sequence of states. After obtaining an observation oi, the agent makes a prediction ŷi and sees the actual outcome yi. The goal is to minimize this prediction error. Given only oi, the agent is unlikely to make accurate predictions about yi, because oi is not a sufficient statistic to predict yi: p(y|oi,oi−1,oi−2, . . .) 6= p(y|oi). The agent could obtain a lower prediction error using a history of observations. Unfortunately, the agent may require a prohibitively long history, even if this history could have been summarized compactly.
An alternative is to construct state using a Recurrent Neural Network (RNN), by learning a stateupdate function. Given the current (constructed) state st−1 ∈ Rk, and a new observation ot ∈ Rd, the parameterized state-update function fW : Rk×Rd → Rk, with parameters W, produces the next (constructed) state st = fW(st−1,ot). For example, fW could be a linear weighting of st−1 and ot, with a ReLu activation: fW(st−1,ot) = max([st−1,ot]W,0). More complex state-updates are 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 gβ : Rk → Rm with learned parameters β. For example, the prediction could be a linear weighting of the state, gβ(s) = β>s. We denote the prediction error as `β : Rk × Rm → R for a given β. For example, this loss could be
`β(st;yt) = ‖gβ(st)− yt‖22. 1Recurrent 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 a different way. These algorithms only address a restricted class of RNNs, that assume a fixed input and converge to a single low-energy state—a fixed point of the dynamics for that given input. These RNNs are actually highly related to Graph NNs (Scarselli et al., 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 so we do not further discuss this class of RNN algorithms.
The goal in RNNs training is to minimize, for some start state s0,
min β,W n∑ i=1 `β(fW(...fW(fW(s0,o1)︸ ︷︷ ︸ s1 ,o2), ...,oi);yi). (1)
Computing gradients for this objective, however, can be prohibitively expensive. A large literature on optimizing RNNs focuses on approximating this gradient, either through approximations to RTRL or improvements to BPTT. RTRL (Williams and Zipser, 1989b) uses a 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(k4) computation per observation (recall k is the dimension of 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 is truncated T steps back in time. T-BPTT is suitable for the online setting, and requires O(Tk2) computation per step, i.e., 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 Ollivier, 2017), as we affirm in our experiments. Yet, the need for simple algorithms remains. In this 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 to 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 et al., 2014), phased LSTMs (Neil et al., 2016), hierarchical multi-scale RNNs (Chung et al., 2016), dilated RNNs (Chang et al., 2017), and skip RNNs (Campos et 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.

heading: 3 A NEW FIXED-POINT OBJECTIVE FOR RNNS
text: 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 a set of observations that are deterministic function of the state. We denote the set of statesH = {1, . . . , n}, and the observations from each state as o1, . . . ,on . The goal is to find state vectors s1, . . . , sn ∈ Rk that satisfy two goals. One is to enable the state to be updated
fW(si,oj) = sj ∀ j where P(i, j) > 0 (2) for P : H × H → [0, 1] the transition dynamics. Another criterion is for these state vectors to facilitate accurate predictions. In particular, the learned state should minimize `β(sj ;yj) for all h, where yj ∈ R is the expected target for a true state j. Together, this results in the following optimization, with the relationship between states encoded as a constraint
min β,W,s ∑ i,j∈H P(i, j)`β(fW(si;oj),yj) s.t. fW(si,oj) = sj ∀ i, j where P(i, j) > 0
The satisfiability of this will depend on fW and if si and oj can uniquely determine sj .
More generally, we will not know the underlying state, nor is it necessarily discrete. But, we can consider a similar objective for observed data. Assume n observations have been observed, o1, . . . ,on, with corresponding targets y1, . . . ,yn. Let the state variables be stacked in a matrix S ∈ Rk×n and observations as a matrix O ∈ Rd×n, with S = [s0, . . . , sn] and O = [o1, . . . ,on]. The constraint on the states becomes S = FW(S,O) for operator
FW(S,O) def = [S:,0,fW(S:,0,O:,1),...,fW(S:,n−1,O:,n)] . (3)
We call this the fixed-point constraint, since a solution S to the constraint is a fixed point of the system defined by FW(·,O). The resulting optimization, for this batch, is
min β,W,S n∑ i=1 `β(fW(si−1,oi);yi) s.t. S = FW(S,O). (4)
The solution to this new optimization corresponds to the solution for the original RNN problem in (1)—when also optimizing over s0 in (1)—because the fixed-point constraint forces variables si to be representable by fW. Therefore, the reformulation as a fixed point problem has not changed the solution; rather, it has only made explicit that the goal is to 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 (1). 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 so facilitate decentralized optimization.
Such auxiliary variable methods have even been previously considered for optimizing neural networks. Carreira-Perpiñán 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 an additional set of auxiliary variables to 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 a stochastic gradient descent update for distributed updates to blocks of weights in a neural network. Our proposed optimization can be seen as a variation of the objective considered for MAC (Carreira-Perpiñán and Wang, 2014, Equation 1), though we arrived at it from a different perspective: with the goal to learn explicit state vectors.
The objective in (4) still has two issues. First, it is not amenable to online updating: it is a batch optimization with a 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 on the target two steps in the future. We develop a more general objective below to address both issues.
We can rewrite the objective so that it is clear how to stochastically sample it, and so enable online updating. As in MAC-QP (Carreira-Perpiñán and Wang, 2014), we reformulate this constrained objective into an unconstrained objective with a quadratic penalty, with λ > 0
L(β,W,S) def =
1
n n∑ i=1 `β(fW(si−1,oi);yi) + λ 2n n∑ i=1 ‖si − fW(si−1,oi)‖22 (5)
Once in this unconstrained form, we can perform stochastic gradient descent on this objective in terms of β,W and S to reach a stationary point. To use stochastic gradient descent, the objective needs to break up into a sum of losses, L(β,W,S) = 1n ∑n i=1 Li(β,W,S), where we define
Li(β,W,S) def = `β(fW(si−1,oi);yi) +
λ 2 ‖si − fW(si−1,oi)‖22.
We can stochastically sample i from our buffer of n samples and update our variables with ∇Li. Fortunately, because the state variables break connections across time, this gradient is zero for most variables, except β,W, si−1 and si. 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 T -step fixed point problem S = FT,W(S,O) where
FT,W(S,O) def = [ S:,0,S:,1, . . . ,S:,T−1, fW(. . . fW(fW(S:,0,O:,1),O:,2), . . .),O:,T )︸ ︷︷ ︸
Ŝ:,T
, . . .
fW(. . . fW(fW(S:,n−T−1,O:n−T ),O:,n−T+1), . . .),O:,n) ] .
For T = 1, we 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 a budget of T updates per step, we could use T 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 a sum 1n−T+1 ∑n i=T Li(β,W,S) for
Li(β,W,S) = `β(ŝi(si−T ,W);yi) + λ
2 ‖si − ŝi(si−T ,W)‖22 (6)
where ŝi(si−T ,W) def = fW(. . . fW(fW(si−T−1,oi−T ),oi−T+1), . . .),oi).
For each stochastic sample i, ∇Li is only non-zero for β,W, si−T and si. Though these updates can simply be computed using automatic differentiation on Li, the explicit updates are simple so we include them here, using shorthand ŝi for ŝi(si−T ,W):
∇si−TLi = [∇ŝi`β(ŝi;yi)− λ(si − ŝi)]>∇si−T ŝi ∇siLi = λ(si − ŝi) ∇WLi = [∇ŝi`β(ŝi;yi)− λ(si − ŝi)]>∇Wŝi (7) ∇βLi = ∇β`β(ŝi;yi)
The online algorithm uses these updates on a sliding window buffer, instead of a fixed buffer. This algorithm—called Fixed Point Propagation (FPP)— is summarized in Figure 1 and Algorithm 1.
As alluded to, the advantage of FPP over T-BPTT is that we are not restricted to focusing all computation to estimate the gradient T -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 on computing a 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 on the fixed point objective makes it a sound strategy—as 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.

heading: 4 CONVERGENCE RESULTS
text: In this section we show two theoretical results. First, we show that the FPP algorithm converges to a stationary point, for a fixed buffer. This result is a relatively straightforward application of recent theory for nonconvex optimization (Ghadimi et al., 2016), mainly requiring us to show that our
Algorithm 1 Fixed Point Propagation (FPP) Input: a truncation parameter T , mini-batch size B, and number of updates per step M Initialize weights W and β randomly Initialize state s0 ← 0 ∈ Rd Initialize an empty buffer B of size N for t← 1, 2, ... do
if B is full then Remove the oldest transition end if Observe ot, yt, and compute st = fW(st−1,ot) Add (st,ot,yt) to buffer B if t ≥ T then
for j ← 1, · · · ,M do . Multiple updates Sample a mini-batch of size B, of trajectories of length T , from the buffer: {(sil−T ,oil−T , . . . , sil ,oil ,yil)}Bl=1 where il is the index of the l-th mini-batch
Compute the average mini-batch loss and update {sil−T , sil}Bl=1,W and β Update {sil−T , sil}Bl=1 in the buffer
end for end if
end for
algorithm can be written as an instance of that framework and to show that each stochastic gradient update is unbiased. This convergence result, nonetheless, is key, as 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 et al., 2019), which is to be expected as truncated BPTT updates on a buffer may not be sound.
Additionally, we 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 λ = 1, as obtaining precisely the same solutions as 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 to that for MAC-QP (CarreiraPerpiñá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 are in Appendix A.

heading: 4.1 CONVERGENCE OF FPP TO A STATIONARY POINT FOR A FIXED BUFFER
text: 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 are (W,β,S) ∈ Rz , where z 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, we will analyze our update with the addition of a projection operator onto a closed ball C in Rz of radius r > 0 about the origin. r can be very large, and we emphasize that C is only a convenience used for theoretical analysis. In practice, we do not project our iterates. Since Rd is a Hilbert space and C is closed and convex, we have the existence of a unique projection operator Γ
Γ(W0,β0,S0) def = arg min (W,β,S)∈C ‖(W0,β0,S0)− (W,β,S)‖2. (8)
Our objective is L(W,β,S) def= 1n−T+1 ∑n i=T Li(W,β,S), for Li defined in Equation (6), for n > T samples. Each time we perform an update, we randomly sample kt ∼ uniform-(T, n), inclusive of both endpoints. The update to parameters at time t, for stepsize αt, is
(Wt+1,βt+1,St+1) def = Γ((Wt,βt,St)− αt∇Lkt(Wt,βt,St)). (9)
Theorem 1. Let D be a Lipschitz constant of∇L(W,β,S). Define probability mass functions
PN (k) := αk −Dα2k∑N j=1 αj −Dα2j .
for each N ∈ N. Let R be distributed according to PN . Assume αt = 12D for all t and that we perform N stochastic updates. Write xR = (WR,βR,SR). Then
E [ 1
α2R ‖Γ(αR∇L(xR))‖2
] = O ( 1
N
) .

heading: 4.2 RECOVERING RNN SOLUTIONS
text: Consider the standard RNN problem,
min β,W,s0
E(W,β, s0) for E(W,β, s0) def = n∑ i=1 `β(fW(· · · fW(fW(s0,o1),o2), · · · ,oi);yi) (10)
where we also optimize over s0. Our goal is to show that for increasing λ, 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 {λk} → ∞, a non-negative sequence { k} → 0, and a sequence of points {(Wk,βk,Sk)} such that ‖∇L(Wk,βk,Sk);λk)‖ ≤ k for
L(Wk,βk,Sk);λk) def = 1n n∑ i=1 `β(fW(si−1,oi);yi) + λk 2 ‖si − fW(si−1,oi)‖22 (11)
Assume further that {(Wk,βk,Sk)} has a convergent subsequence {(Wki ,βki ,Ski)} with limit (W∗,β∗,S∗). Then (W∗,β∗,S∗) is a KKT point of the constrained FPP objective (see (12)) and (W∗,β∗, s∗0) is a KKT point of the RNN objective (10). Further, if (W
∗,β∗,S∗) is a local min of the constrained FPP objective, then (W∗,β∗, s∗0) is a local min of (10).

heading: 5 EXPERIMENTAL RESULTS
text: We designed a sequence of experiments in real and synthetic problems to evaluate our new method compared with several common baselines and to highlight the robustness of our method to different truncation lengths, buffer sizes and number of updates. In particular we 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, a common a variant of T-BPTT that updates on disjoint partitions of the data; and (3) FPP without the state update, which is similar to the Stored State T-BPTT algorithm (Kapturowski et al., 2019). We begin by describing the problems we used to evaluate our 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 two small simulation problems to highlight the robustness of each method to increasing temporal delay in online training. The first tasks is a 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 objective is to predict the next observation, which is difficult without a memory of length equal to the length of the cycle. With a 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 in 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, we measure the prediction accuracy for the next observation.
We also experimented with a stochastic prediction task, where correct prediction requires remembering 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 1, in Appendix C. This task is called Stochastic World.
For this problem, a 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 a 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 an 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 a stream of pixel inputs. On each timestep the input is one row (1x28) 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 to predict the target image base on a 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 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 a vocabulary size of 10000. The Target Loss function used here is a weighted cross-entropy loss for a sequence of logits. We used an LSTM with 200 hidden nodes as this architecture was found to perform well in previous work (Zaremba et al., 2014).
Comparison to T-BPTT We compare FPP to 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-BPTT(overlap and no overlap versions) and FPP. All algorithms use O(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 approximation to approximate RTRL. It is a 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 StochasticWorld.
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 = p and T = p/2 for increasing p. To make the results comparable across p, we report performance as the ratio to a simple baseline of predicting 0 at every time step. From Figure 2, we can see that FPP is more robust to T , whereas T-BPTT with T = 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)).
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 40-BPTT. Similar conclusions can be made for T ∈ {3, 5} in (a), T ∈ {10, 15, 20, 30} in (b), T ∈ {7, 14, 21, 28} in (c) and T ∈ {1, 5, 10, 20} in (d). Benefits of mini-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 ∈ {1, 2, 4, 8, 16}. To show the effect of mini-batch update, we fix M and vary B ∈ {1, 2, 4, 8, 16}. We use a 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 a 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 on a fixed buffer whereas no such result exists for FPP without state
updating. Here, the buffer is not fixed, but performing more updates per step should move the FPP solution closer to 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 StochasticWorld and T = 1 and T = 2 in CycleWorld. The theory suggests that more updates, even with T = 1, should allow FPP to converge to a reasonable solution. We test this on CycleWorld (with Figure 7 in Appendix C), and find that for both larger mini-batch and number of updates FPP can get the error down to zero, whereas FPP without state updating cannot.

heading: 6 CONCLUSION
text: The main objective of this paper is to 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—and potentially unstable—gradients back in time for each state. We introduce a new objective to explicitly learn state variables for RNNs, which breaks gradient dependence back in time. The choice of T to compute gradients back in time is used only to improve training speed, rather than to 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 our algorithm converges to a stationary point, under a fixed buffer, and so is a sound approach to using a buffer to train RNNs. Further, we chose simple optimization choices in this work; there are clear next steps for benefiting more from the decoupled update, such as by parallelizing updates across state variables. Overall, this work provides evidence that FPP could be a promising direction for robustly training RNNs, without the need to compute or approximate long gradients back in time.

heading: A FULL PROOFS

heading: A.1 CONVERGENCE ON A FIXED BUFFER
text: 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 a stochastic sample of L and let α > 0. Write x = (W,β,S). Then
arg min u∈C
{ 〈∇f(x), u〉+ 1
2α ‖x− u‖2
} = arg min
u∈C
{ ‖u− (x− α∇f(x))‖2 } =: Γ(x− α∇f(x)).
Proof. The proof is a straightforward calculation.
arg min u∈C
{ ‖u− (x− α∇f(x))‖2 } = arg min
u∈C
{ ‖u− x‖2 + α2‖∇f(x))‖2 + 2〈u− x, α∇f(x)〉 } = arg min
u∈C
{ ‖u− x‖2 + 2α〈u,∇f(x)〉 } = arg min
u∈C
{ 〈∇f(x), u〉+ 1
2α ‖x− u‖2
}
Our goal is to apply Corollary 3 of Ghadimi et al. (2016, p. 282). We must show that∇g is Lipschitz on C and demonstrate that Assumption A1 in Ghadimi et al. (2016, p. 268) holds. Lemma 2. ∇L is Lipschitz on C.
Proof. A function is Lipschitz if it gradient is bounded. Since L is smooth and C is compact (continuous functions on compact sets are bounded), this lemma follows.
Lemma 3. ∇Lk is an unbiased estimate of∇L, where k ∼ uniform-(T, n).
Proof. The terms in∇Lk corresponding to the gradients of W and β are exactly∇WL and∇βL in expectation, given that k ∼ uniform-(T, n). Let us consider the gradient elements corresponding to the parameters s0:n. For shorthand, define [a : b] := {a, a + 1, · · · , b − 1, b}. Define P0 := [0 : n − T ], P1 := [T : n]. If j ∈ P0, then sj predicts future states. If sj ∈ P1, then sj is predicted by other states in the regularizer terms of L. Note that P0 and P1 are not disjoint. First, we calculate.
∇sjL(W,β,S) :=  1 n−T+1 (∇ŝj+T `β(ŝj+T ; yj+T )− λ(sj+T − ŝj+T ))>∇sj ŝj if j ∈ P0 ∩ P {1 1 n−T+1λ(sj − ŝj) if j ∈ P {0 ∩ P1 1 n−T+1 [λ(sj − ŝj) + (∇ŝj+T `β(ŝj+T ; yj+T )− λ(sj+T − ŝj+T ))>∇sj ŝj ]
if j ∈ P0 ∩ P1 0 if j ∈ P {0 ∩ P {1
If j ∈ P0 ∩ P {1 , then sj does not show up as the target (i.e., the term that is not ŝk) in any regularizer term of L. Hence, ∇sjLk is zero with probability 1 − 1n−T+1 , and is (∇ŝj+T `β(ŝj+T ; yj+T ) − λ(sj+T − ŝj+T ))>∇sj ŝj with probability 1n−T+1 .
If j ∈ P {0 ∩ P1, then sj only shows up as a target in a regularizer term, so ∇sjLk is zero with probability 1− 1n−T+1 and is otherwise 1n−T+1λ(sj − ŝj).
If j ∈ P0 ∩P1, then∇sjLk is zero with probability 1− 2n−T+1 , λ(sj − ŝj) with probability 1n−T+1 , and (∇ŝj+T `β(ŝj+T ; yj+T )− λ(sj+T − ŝj+T ))>∇sj ŝj with probability 1n−T+1 .
The case for j ∈ P {0 ∩ P {1 is trivial. Consequently, E[∇sjLk] = ∇sjL for all j ∈ {0, · · · , n}.
Lemma 4. The variance of ∇Lk is bounded on C.
Proof. This follows because∇Lk and∇L are both smooth functions on a compact set C, and thus bounded.
Theorem 1. Let D be a Lipschitz constant of∇L(W,β,S). Define probability mass functions
PN (k) := αk −Dα2k∑N j=1 αj −Dα2j .
for each N ∈ N. Let R be distributed according to PN . Assume αt = 12D for all t and that we perform N stochastic updates. Write xR = (WR,βR,SR). Then
E [ 1
α2R ‖Γ(αR∇L(xR))‖2
] = O ( 1
N
) .
Proof. The gX,R (defined in Ghadimi et al. (2016, p. 271, 274)) in Corollary 3 of Ghadimi et al. (2016, p. 282) corresponds in our case to the following.
gX,R := 1
αR
( xR − arg min
u∈C
{ 〈∇f(x), u〉+ 1
2α ‖x− u‖2 }) = 1
αR (xR − Γ(xR − αR∇L(xR))).
In the last line, we use Lemma 1. Since we project based on squared norm distance in (8) (corresponding to ω(x) = 12‖x‖22 in Ghadimi et al. (2016)), the α in Ghadimi et al. (2016, p. 271) (not our step-size αt) can be set to 1.
After applying our Lemma 2, Lemma 3, and Lemma 4, we have from Corollary 3 of Ghadimi et al. (2016, p. 282) that
E [ 1
α2R ‖Γ(xR − αR∇L(xR))− xR‖2
] = O ( 1
N
) .
The only thing left to check is that Γ(xR − αR∇L(xR))− xR = Γ(∇L(xR)). Γ(xR − αR∇L(xR))− xR = arg min
u∈C
{ ‖u− (xR − αR∇L(xR))‖2 } − xR
= arg min u∈C
{ ‖u− ∇L(xR))‖2 } = Γ(αR∇L(xR)).

heading: A.2 RECOVERY OF RNN SOLUTIONS
text: Recall our goal is to compare to the RNN solutions of (10).
E(W,β, s0) := n∑ i=1 `β(fW(· · · fW(fW(s0,o1),o2), · · · ,oi);yi) (10 revisited)
min β,W,s0 E(W,β, s0),
Let us also write a constrained version of the above problem, which we will use in the analysis of FPP.
Efpp(W,β, s0, · · · , sn) := n∑ i=1 `β(fW(si−1,oi);yi) (12)
s.t. ∀ 1 ≤ i ≤ n,fW(si−1,oi) = si min
W,β,s0:n Efpp(W,β, s0, · · · , sn)
The idea is that FPP can be viewed as a way to solve the problem (12) and thus (10) through quadratic regularization.
We will use s0:n as shorthand for {s0, · · · , sn}, 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,β, s0:n) : W ∈ Rw; si ∈ Rk;β ∈ Rb;∀ 1 ≤ i ≤ n, si = fW(si−1,oi)}.
Proposition 1. Let (W∗,β∗, s∗0) be a local min of (10). For 1 ≤ i ≤ n, define recursively s∗i := fW∗(s ∗ i−1,oi). Then (W ∗,β∗, s∗0:n) is a local min of (12).
Let (W∗,β∗, s∗0:n) be a local min of (12). Then (W ∗,β∗, s∗0) is a local min of (10).
Proof. First, let N ⊂ Rw+b+k be a neighbourhood of (W∗,β∗, s∗0) such that ∀(W,β, s0) ∈ N , we have E(W∗,β∗, s∗0) ≤ E(W,β, s0). 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∗,β∗, s∗0) by definition of a neighbourhood and call that set N .
Let s∗i be defined as above. Define M := N ×Rnk, which is an open neighbourhood of (W∗,β∗, s∗0) since N is open. Let (W,β, s0:n) ∈ M ∩ Ω. Note that (W,β, s0) ∈ N . By definition of Ω, we have that fW(si−1,oi) = si. Hence, Efpp(W,β, s0:n) = E(W,β, s0).
By definition of (12), (10), we have E(W∗,β∗, s∗0) = Efpp(W ∗,β∗, s∗0:n). Finally,
Efpp(W ∗,β∗, s∗0:n) = E(W ∗,β∗, s∗0) ≤ E(W,β, s0) = Efpp(W,β, s0:n). For the second part of the proof, assume (W∗,β∗, s∗0:n) is a local min of (12), meaning there is a neigbourhood M ⊂ Rw+b+(n+1)k of (W∗,β∗, s∗0:n) such that for every (W,β, s0:n) ∈M ∩ Ω,
Efpp(W ∗,β∗, s∗0:n) ≤ Efpp(W,β, s0:n).
Similarly, without loss of generality, we can assume that M is an open ball, so we may write for some > 0, M = B (W∗,β∗, s∗0:n). We will construct an open set N ⊂ Rw+b+k such that (W∗,β∗, s∗0) is a local min with respect to N . Define the projection π onto the first w + b+ k indices. Define N := π(M ∩ Ω). Let us show that N is open.
We will write fW(s0:n−1,o1:n) to mean {fW(s0,o1), · · · , fW(fW(· · · (s0,o1),o2), · · · ,on))}. We can write N as
N = {(W,β, s0) : (W,β, s0:n) ∈ Ω ∩B (W∗,β∗, s∗0:n)} = {(W,β, s0) : (W,β, s0, fW(s0:n−1,o1:n)) ∈ B (W∗,β∗, s∗0:n)} = {(W,β, s0) : ‖(W,β, s0, fW(s0:n−1,o1:n))− (W∗,β∗, s∗0:n)‖ < }
On the second line, we used the fact that si = fW(si−1,oi) in Ω. Since the norm and f are continuous and (−∞, ) is open, we have that N , a continuous preimage of an open set, is open. Now, let (W,β, s0) ∈ N such that ∃ s1:n with (W,β, s0:n) ∈M ∩ Ω.
E(W∗,β∗, s∗0) = Efpp(W ∗,β∗, s∗0:n) ≤ Efpp(W,β, s0:n) = E(W,β, s0)
The claim follows.
Proposition 2. The first order KKT equations for (10) and for (12) are the same.
Proof. Given (W∗,β∗, s∗0), for 1 ≤ i ≤ n define s̃i := fW(s̃i−1,oi), where s̃0 := s∗0. If we write ∂fW∗ (s̃l,ol+1)
∂sl for instance, this is taken to mean the gradient of fW∗(s̃l,ol+1) with respect to the
function arguments corresponding to s̃l. Furthermore, when writing ∂fW∗ (s̃j ,oj+1)
∂W , we only mean the gradient with respect to the parameters of the outer fW∗ , and not with respect to any of the parameters of s̃j .
Using the chain rule for the first and third equations below, the first order KKT conditions for (10) are given by
∂E(W∗,β∗, s∗0) ∂W = ∂`β∗(fW∗(s ∗ 0,o1); y1)
∂fW
∂fW∗(s ∗ 0,o1)
∂W + (13)
n−1∑ j=1 ∂`β∗(fW∗(s̃j ,oj+1); yj+1)
∂fW( ∂fW∗(s̃j ,oj+1)
∂W + j∑ i=1 j∏ l=i ∂fW∗(s̃l,ol+1) ∂sl
) ∂fW∗(s̃i−1,oi)
∂W
= 0
∂E(W∗,β∗, s∗0) ∂β = n∑ i=1 ∂`β∗(fW∗(s̃i−1,oi);yi) ∂β = 0 (14)
∂E(W∗,β∗, s∗0) ∂s0 =
( ∂`β∗(fW∗(s ∗ 0,o1); y1)
∂fW + ( n−1∑ i=1 ∂`β∗(fW∗(s̃i,oi+1); yi+1) ∂fW (15)
i∏ l=1 ∂fW∗(s̃l,ol+1) ∂sl
)) ∂fW∗(s ∗ 0,o1)
∂s0
= 0
The Lagrangian for (12) is
Lfpp(W,β, s0:n) = n∑ i=1 `β(fW(si−1,oi);yi)− λTi (fW(si−1,oi)− si), (16)
where λi ∈ Rk for 1 ≤ i ≤ n are Lagrange multipliers. We define λ0 := 0 for convenience. The KKT equations for (16) are
∂Lfpp(W∗,β ∗, s∗0:n)
∂W = n∑ i=1 ∂`β∗(fW∗(s ∗ i−1,oi);yi) ∂fW ∂fW∗(s ∗ i−1,oi) ∂W (17)
− λTi ∂fW∗(s
∗ i−1,oi)
∂W = 0
∂Lfpp(W∗,β ∗, s∗0:n)
∂β = n∑ i=1 ∂`β∗(fW∗(s ∗ i−1,oi);yi) ∂β = 0
∂Lfpp(W∗,β ∗, s∗0:n)
∂sj =  λTn if j = n λTj + ( ∂`β∗ (fW∗ (s ∗ j ,oj+1);yj+1) ∂fW − λTj+1 ) ∂fW∗ (s ∗ j ,oj+1) ∂sj
if 0 ≤ j < n (18)
= 0
s∗i = fW∗(s ∗ i−1,oi), ∀ 1 ≤ i ≤ n
First, let us find a closed-form expression for λi.
Lemma 1. Let 0 ≤ j ≤ n. Then
λTj = − n−1∑ i=j ∂`β∗(fW∗(s ∗ i ,oi+1); yi+1) ∂fW i∏ l=j ∂fW∗(s ∗ l ,ol+1) ∂sl  Proof. We proceed by induction. The base case and the case j = n− 1 are trivial. Assume the claim is true for m + 1 > 0. We will show the claim for j = m. Using the KKT equations (17) and the induction hypothesis,
λTm := − ( ∂`β∗(fW∗(s ∗ m,om+1); ym+1)
∂fW − λTm+1
) ∂fW∗(s ∗ m,om+1)
∂sm = − ( ∂`β∗(fW∗(s ∗ m,om+1); ym+1)
∂fW + n−1∑ i=m+1 ∂`β∗(fW∗(s ∗ i ,oi+1); yi+1) ∂fW
i∏ l=m+1 ∂fW∗(s ∗ l ,ol+1) ∂sl
) ∂fW∗(s ∗ m,om+1)
∂sm
= −∂`β∗(fW∗(s ∗ m,om+1); ym+1)
∂fW
∂fW∗(s ∗ m,om+1)
∂sm −
n−1∑ i=m+1 ∂`β∗(fW∗(s ∗ i ,oi+1); yi+1) ∂fW i∏ l=m+1 ∂fW∗(s ∗ l ,ol+1) ∂sl ∂fW∗(s ∗ m,om+1) ∂sm
= − ( n−1∑ i=m ∂`β∗(fW∗(s ∗ i ,oi+1); yi+1) ∂fW i∏ l=m ∂fW∗(s ∗ l ,ol+1) ∂sl )
Now, we will show that the sets of equations are the same. First, it is clear that the two equations involving gradients of β 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.
∂Lfpp ∂W = n∑ i=1 ∂`β∗(fW∗(s ∗ i−1,oi);yi) ∂fW ∂fW∗(s ∗ i−1,oi) ∂W +
n∑ i=1 n−1∑ j=i ∂`β∗(fW∗(s ∗ j ,oj+1); yj+1) ∂fW j∏ l=i ∂fW∗(s ∗ l ,ol+1) ∂sl  ∂fW∗(s∗i−1,oi) ∂W
= n∑ j=1 ∂`β∗(fW∗(s ∗ j−1,oj); yj) ∂fW ∂fW∗(s ∗ j−1,oj) ∂W +
n−1∑ j=1 ( j∑ i=1 ∂`β∗(fW∗(s ∗ j ,oj+1); yj+1) ∂fW j∏ l=i ∂fW∗(s ∗ l ,ol+1) ∂sl ) ∂fW∗(s ∗ i−1,oi) ∂W
= ∂`β∗(fW∗(s
∗ 0,o1); y1)
∂fW
∂fW∗(s ∗ 0,o1)
∂W + n−1∑ j=1 ∂`β∗(fW∗(s ∗ j ,oj+1); yj+1)
∂fW( ∂fW∗(s ∗ j ,oj+1)
∂W + j∑ i=1 j∏ l=i ∂fW∗(s ∗ l ,ol+1) ∂sl
) ∂fW∗(s ∗ i−1,oi)
∂W
= 0.
By substituting in the constraint equations s∗i = fW∗(s ∗ i−1,oi), this recovers exactly the gradient with respect to W in (13).
Finally, consider the gradient with respect to s0.
∂Lfpp(W∗,β ∗, s∗0:n)
∂s0 = λT0 +
( ∂`β∗(fW∗(s ∗ 0,o1); y1)
∂fW − λT1
) ∂fW∗(s ∗ 0,o1)
∂s0
=
( ∂`β∗(fW∗(s ∗ 0,o1); y1)
∂fW + ( n−1∑ i=1 ∂`β∗(fW∗(s ∗ i ,oi+1); yi+1) ∂fW
i∏ l=1 ∂fW∗(s ∗ l ,ol+1) ∂sl
)) ∂fW∗(s ∗ 0,o1)
∂s0
= 0.
This matches the corresponding equation in (13).
Proposition 3. Let (W∗,β∗, s∗0:n) be a local min of (12). Write the constraints of (12) as a vector:
h(W, s0:n) := [ [(fW(s0,o1)− s1)T · · · (fW(sn−1,on)− sn)T ] (19)
Index each element of h by hi. Then the vectors∇hi(W∗, s∗0:n) are linearly independent.
Proof. In the following, we will write ∂[g]l ∂xij to mean the derivative of the l-th component of g with respect to the i-th component of xj . For compactness, write g(i) := fW∗(s∗i−1,oi) − s∗i . We can write the Jacobian∇h(W∗, s∗0:n) as
∇h(W∗, s∗0:n) =  ∂[g(1)]1 ∂W1 · · · ∂[g(1)]1 ∂Ww ∂[g(1)]1 ∂s11 · · · ∂[g(1)]1 ∂sk1 · · · ∂[g(1)]1 ∂skn ... ... ... ... ... ... ... ∂[g(1)]k ∂W1 · · · ∂[g(1)]k ∂Ww ∂[g(1)]k ∂s11 · · · ∂[g(1)]k ∂sk1 · · · ∂[g(1)]k ∂skn ∂[g(2)]1 ∂W1 · · · ∂[g(2)]1 ∂Ww ∂[g(2)]1 ∂s11 · · · ∂[g(2)]1 ∂sk1 · · · ∂[g(2)]1 ∂skn ... ... ... ... ... ...
... ∂[g(n)]k ∂W1 · · · ∂[g(n)]k ∂Ww ∂[g(n)]k ∂s11 · · · ∂[g(n)]k ∂sk1 · · · ∂[g(n)]k ∂skn  We will show that the rows of ∇h(W∗, s∗0:n) are linearly independent. To this end, let λij ∈ R for i ∈ {1, · · · , n}, j ∈ {1, · · · , k} be such that:
k∑ j=1 n∑ i=1 λij∇[fW∗(s∗i−1,oi)− s∗i ]j = 0.
In particular, for 1 ≤ a ≤ n, 1 ≤ b ≤ k,
k∑ j=1 n∑ i=1 λij ∂[fW∗(s ∗ i−1,oi)− s∗i ]j ∂sba = k∑ j=1 n∑ i=1 λij ( δi−1a ∂[fW∗(s ∗ i−1,oi)]j ∂sba − δiaδjb ) (20)
= 1a<n k∑ j=1 λa+1,j ∂[fW∗(s ∗ a,oa+1)]j ∂sba+1 − λab (21)
= 0 (22)
By setting a = n, we have that λnb = 0 for all 1 ≤ b ≤ k. Setting a = n − 1, we similarly have that λn−1,b = 0. Proceeding in this fashion, we have that λab = 0 for all 1 ≤ a ≤ n, 1 ≤ b ≤ k. Actually, we did not at any point use the fact that (W∗,β∗, s∗0:n) is a local min, so that the constraint gradients are linearly independent everywhere, and in particular at (W∗,β∗, s∗0:n).
Theorem 2. Assume we have a positive, increasing sequence {λk} → ∞, a non-negative sequence { k} → 0, and a sequence of points {(Wk,βk,Sk)} such that ‖∇L(Wk,βk,Sk);λk)‖ ≤ k for
L(Wk,βk,Sk);λk) def = 1n n∑ i=1 `β(fW(si−1,oi);yi) + λk 2 ‖si − fW(si−1,oi)‖22 (11)
Assume further that {(Wk,βk,Sk)} has a convergent subsequence {(Wki ,βki ,Ski)} with limit (W∗,β∗,S∗). Then (W∗,β∗,S∗) is a KKT point of the constrained FPP objective (see (12)) and (W∗,β∗, s∗0) is a KKT point of the RNN objective (10). Further, if (W
∗,β∗,S∗) is a local min of the constrained FPP objective, then (W∗,β∗, s∗0) is a local min of (10).
Proof. By Proposition 3 and Proposition 2.3 from Bertsekas (1982), We have the existence of a Lagrange multiplier vector λ such that
∇Efpp(W∗,β∗, s∗0:n)−∇h(W∗, s∗0:n)λ = 0, h(W∗, s∗0:n) = 0,
where h(W∗, s∗0:n) is as in Proposition 3. Hence, (W ∗,β∗, s∗0:n) is a KKT point of (12). By Proposition 2, (W∗,β∗, s∗0) is a KKT point for (10). Finally, if (W ∗,β∗, s∗0:n) is a local min of (12), then by Proposition 1 we have that (W∗,β∗, s∗0) is a local min of (10).

heading: B PARAMETER STUDY
text: 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 5 show that FPP is robust to buffer size and truncation length. As expected, for very small T, performance degrades, but otherwise the move from T= 10 to T= 50 does not result in a 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.
We also investigated how performance changes when changing λ. Throughout all previous experiments, 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 λ.

heading: C EXPERIMENTAL DETAILS
text: The dynamics for the Stochastic World environment are in Table 1.
For all experiments, we use RMSprop optimizer and the learning rate is chosen over the set {0.0001, 0.0003, 0.001, 0.003, 0.01, 0.03} based on the average accuracy/loss. For real datasets, we use multiple trajectories to speed up training. The details of each task are provided below:

heading: C.1 CYCLEWORLD
text: Network Type = simple RNN Hidden Units = 4

heading: C.2 STOCHASTIC WORLD
text: Network Type = simple RNN Hidden Units = 32

heading: C.3 SEQUENTIAL MNIST
text: Network Type = simple RNN Hidden Units = 512 Image Size = 784 pixels Input Dimension = 28 pixels Number of Steps = 28000 (1000 images of 28 steps)
Number of Trajectories = 20

heading: C.4 PTB
text: 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

Review summaries:
Background: 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.