Title: TRAINING RECURRENT NEURAL NETWORKS ONLINE BY LEARNING EXPLICIT STATE VARIABLES

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.

1. 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 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.

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 a sequence of n observations, o 1 , . . . , o n , which provide only partial information about an unknown underlying sequence of states. After obtaining an observation o i , the agent makes a prediction ŷi and sees the actual outcome y i . The goal is to minimize this prediction error. Given only o i , the agent is unlikely to make accurate predictions about y i , because o i is not a sufficient statistic to predict y i : p(y|o i , o i-1 , o i-2 , . . .) = p(y|o i ). 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 s t-1 ∈ R k , and a new observation

o t ∈ R d , the parameterized state-update function f W : R k × R d → R k , with parameters W, produces the next (constructed) state s t = f W (s t-1 , o t ).

For example, f W could be a linear weighting of s t-1 and o t , with a ReLu activation:

f W (s t-1 , o t ) = max([s t-1 , o t ]

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 s t , a prediction is made by parameterized function g β : R k → R m with learned parameters β. For example, the prediction could be a linear weighting of the state, g β (s) = β s. We denote the prediction error as β : R k × R m → R for a given β. For example, this loss could be

β (s t ; y t ) = g β (s t ) -y t 2 2 .

The goal in RNNs training is to minimize, for some start state s 0 ,

min β,W n i=1 β (f W (...f W (f W (s 0 , o 1 ) s1 , o 2 ), ..., o i ); y i ).

(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(k 4 ) 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(T k 2 ) 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.

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 a set of observations that are deterministic function of the state. We denote the set of states H = {1, . . . , n}, and the observations from each state as o 1 , . . . , o n . The goal is to find state vectors s 1 , . . . , s n ∈ R k that satisfy two goals. One is to enable the state to be updated

EQUATION

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 β (s j ; y j ) for all h, where y j ∈ 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) β (f W (s i ; o j ), y j ) s.t. f W (s i , o j ) = s j ∀ i, j where P(i, j) > 0

The satisfiability of this will depend on f W and if s i and o j can uniquely determine s j .

More generally, we will not know the underlying state, nor is it necessarily discrete. But, we can consider a similar objective for observed data. The constraint on the states becomes S = F W (S, O) for operator

EQUATION

We call this the fixed-point constraint, since a solution S to the constraint is a fixed point of the system defined by F W (•, O). The resulting optimization, for this batch, is

EQUATION

The solution to this new optimization corresponds to the solution for the original RNN problem in (1)-when also optimizing over s 0 in (1)-because the fixed-point constraint forces variables s i to be representable by f W . 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 β (f W (s i-1 , o i ); y i ) + λ 2n n i=1 s i -f W (s i-1 , o i ) 2 2 (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) = 1 n n i=1 L i (β, W, S

), where we define

L i (β, W, S) def = β (f W (s i-1 , o i ); y i ) + λ 2 s i -f W (s i-1 , o i ) 2 2 .

We can stochastically sample i from our buffer of n samples and update our variables with ∇L i . Fortunately, because the state variables break connections across time, this gradient is zero for most variables, except β, W, s i-1 and s i . 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 = F T,W (S, O) where

F T,W (S, O) def = S :,0 , S :,1 , . . . , S :,T -1 , f W (. . . f W (f W (S :,0 , O :,1 ), O :,2 ), . . .), O :,T ) Ŝ:,T , . . . f W (. . . f W (f W (S :,n-T -1 , O :n-T ), O :,n-T +1 ), . . .), O :,n ) . {s i T , o i T +1 , o i T +2 , ..., o i , y i , s i }

Figure 1 : A single update by FPP. It randomly samples i, and performs a gradient descent update to si-T , si, W and β, where the loss on the targets affects si-T , W, β and the loss producing the next state variable si affects si-T , si, W. The state variables are stored in the buffer, but are explicit variables we learn, just like W and β.

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

1 n-T +1 n i=T L i (β, W, S) for L i (β, W, S) = β (ŝ i (s i-T , W); y i ) + λ 2 s i -ŝi (s i-T , W) 2 2 (6) where ŝi (s i-T , W) def = f W (. . . f W (f W (s i-T -1 , o i-T ), o i-T +1 ), . . .), o i ).

For each stochastic sample i, ∇L i is only non-zero for β, W, s i-T and s i . Though these updates can simply be computed using automatic differentiation on L i , the explicit updates are simple so we include them here, using shorthand ŝi for ŝi (s i-T , W):

∇ s i-T L i = [∇ ŝi β (ŝ i ; y i ) -λ(s i -ŝi )] ∇ s i-T ŝi ∇ si L i = λ(s i -ŝi ) ∇ W L i = [∇ ŝi β (ŝ i ; y i ) -λ(s i -ŝi )] ∇ W ŝi (7) ∇ β L i = ∇ β β (ŝ i ; y i )

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.

4. CONVERGENCE RESULTS:

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) 

t = f W (s t-1 , o t ) Add (s t , o t , y t ) 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:

{(s i l -T , o i l -T , . . . , s i l , o i l , y i l )} B l=1

where i l is the index of the l-th mini-batch Compute the average mini-batch loss and update {s i l -T , s i l } B l=1 , W and β Update {s i l -T , s i l } B l=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 (Carreira-Perpiñá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.

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 are (W, β, S) ∈ R z , 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 R z 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 R d is a Hilbert space and C is closed and convex, we have the existence of a unique projection operator Γ Γ(W 0 , β 0 , S 0 )

EQUATION

)

Our objective is L(W, β, S) 6), for n > T samples. Each time we perform an update, we randomly sample k t ∼ uniform-(T, n), inclusive of both endpoints. The update to parameters at time t, for stepsize α t , is

def = 1 n-T +1 n i=T L i (W, β, S), for L i defined in Equation (

EQUATION

Theorem 1. Let D be a Lipschitz constant of ∇L(W, β, S). Define probability mass functions

P N (k) := α k -Dα 2 k N j=1 α j -Dα 2 j .

for each N ∈ N. Let R be distributed according to P N . Assume α t = 1 2D for all t and that we perform N stochastic updates. Write

x R = (W R , β R , S R ). Then E 1 α 2 R Γ(α R ∇L(x R )) 2 = O 1 N .

4.2. RECOVERING RNN SOLUTIONS:

Consider the standard RNN problem,

min β,W,s0 E(W, β, s 0 ) for E(W, β, s 0 ) def = n i=1 β (f W (• • • f W (f W (s 0 , o 1 ), o 2 ), • • • , o i ); y i ) (10)

where we also optimize over s 0 . 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 

{(W k , β k , S k )} such that ∇L(W k , β k , S k ); λ k ) ≤ k for L(W k , β k , S k ); λ k ) def = 1 n n i=1 β (f W (s i-1 , o i ); y i ) + λ k 2 s i -f W (s i-1 , o i ) 2 2 (11) Assume further that {(W k , β k , S k )} has a convergent subsequence {(W ki , β ki , S ki )}

5. EXPERIMENTAL RESULTS:

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 Figure 2 : The ratio error of each of the algorithms with respect to the baseline of predicting 0 at 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 p. The numbers are average over 30 runs with standard error bars. . 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 one standard error with (a) being run for 5000 steps, (b) for 10000 steps, (c) for 1000 images (28000 steps) and (d) for 5000 steps (5000 points in dataset, processed in order). FPP at T = 20, 30, 40 reaches a final solution with optimal performance; it is only above the second line because the plot shows average performance across all steps, rather than final performance.

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. 

6. CONCLUSION:

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.

Lemma 4. The variance of ∇L k is bounded on C.

Proof. This follows because ∇L k 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

P N (k) := α k -Dα 2 k N j=1 α j -Dα 2 j .

for each N ∈ N. Let R be distributed according to P N . Assume α t = 1 2D for all t and that we perform

N stochastic updates. Write x R = (W R , β R , S R ). Then E 1 α 2 R Γ(α R ∇L(x R )) 2 = O 1 N .

Proof. The g X,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.

g X,R := 1 α R x R -arg min u∈C ∇f (x), u + 1 2α x -u 2 = 1 α R (x R -Γ(x R -α R ∇L(x R ))).

In the last line, we use Lemma 1. Since we project based on squared norm distance in (8) (corresponding to ω(x) = 1 2 x 2 2 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 α 2 R Γ(x R -α R ∇L(x R )) -x R 2 = O 1 N .

The only thing left to check is that

Γ(x R -α R ∇L(x R )) -x R = Γ(∇L(x R )). Γ(x R -α R ∇L(x R )) -x R = arg min u∈C u -(x R -α R ∇L(x R )) 2 -x R = arg min u∈C u -∇L(x R )) 2 = Γ(α R ∇L(x R )).

A.2 RECOVERY OF RNN SOLUTIONS:

Recall our goal is to compare to the RNN solutions of (10).

E(W, β, s 0 ) := n i=1 β (f W (• • • f W (f W (s 0 , o 1 ), o 2 ), • • • , o i ); y i ) (10 revisited) min β,W,s0 E(W, β, s 0 ),

Let us also write a constrained version of the above problem, which we will use in the analysis of FPP.

E f pp (W, β, s 0 , • • • , s n ) := n i=1 β (f W (s i-1 , o i ); y i ) (12) s.t. ∀ 1 ≤ i ≤ n,f W (s i-1 , o i ) = s i min W,β,s0:n E f pp (W,β, s 0 , • • • , s n )

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 s 0:n as shorthand for {s 0 , • • • , s n }, 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, β, s 0:n ) : W ∈ R w ; s i ∈ R k ; β ∈ R b ; ∀ 1 ≤ i ≤ n, s i = f W (s i-1 , o i )}.

Proposition 1. Let (W * , β * , s * 0 ) be a local min of (10). For 1 ≤ i ≤ n, define recursively

s * i := f W * (s * i-1 , o i ).

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 ⊂ R w+b+k be a neighbourhood of (W 

:= N × R nk , which is an open neighbourhood of (W * , β * , s * 0 ) since N is open. Let (W, β, s 0:n ) ∈ M ∩ Ω. Note that (W, β, s 0 ) ∈ N . By definition of Ω, we have that f W (s i-1 , o i ) = s i . Hence, E f pp (W, β, s 0:n ) = E(W, β, s 0 ).

By definition of ( 12), (10), we have

E(W * , β * , s * 0 ) = E f pp (W * , β * , s * 0:n ). Finally, E f pp (W * , β * , s * 0:n ) = E(W * , β * , s * 0 ) ≤ E(W, β, s 0 ) = E f pp (W, β, s 0: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 ⊂ R w+b+(n+1)k of (W * , β * , s * 0:n ) such that for every (W, β, We will write f W (s

s 0:n ) ∈ M ∩ Ω, E f pp (W * , β * , s * 0:n ) ≤ E f pp (W, β, s 0:n ).

0:n-1 , o 1:n ) to mean {f W (s 0 , o 1 ), • • • , f W (f W (• • • (s 0 , o 1 ), o 2 ), • • • , o n ))}.

We can write N as 

N = {(W, β, s 0 ) : (W, β, s 0:n ) ∈ Ω ∩ B (W * , β * , s * 0:n )} = {(W, β, s 0 ) : (W, β, s 0 , f W (s 0:n-1 , o 1:n )) ∈ B (W * , β * , s * 0:n )} = {(W, β, s 0 ) : (W, β, s 0 , f W (s 0:n-1 , o 1:n )) -(W * , β * , s * 0:n ) < } On the second line, we used the fact that s i = f W (s i-1 , o i ) in Ω.

Now, let (W, β, s 0 ) ∈ N such that ∃ s 1:n with (W, β, s 0:n ) ∈ M ∩ Ω. E(W * , β * , s * 0 ) = E f pp (W * , β * , s * 0:n ) ≤ E f pp (W, β, s 0:n ) = E(W, β, s 0 )

The claim follows.

Proposition 2. The first order KKT equations for (10) and for (12) are the same.

Proof. , we only mean the gradient with respect to the parameters of the outer f W * , and not with respect to any of the parameters of sj .

Given (W * , β * , s * 0 ), for 1 ≤ i ≤ n define si := f W (s i-1 , o i ),

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 = ∂ β * (f W * (s * 0 , o 1 ); y 1 ) ∂f W ∂f W * (s * 0 , o 1 ) ∂W + (13) n-1 j=1 ∂ β * (f W * (s j , o j+1 ); y j+1 ) ∂f W ∂f W * (s j , o j+1 ) ∂W + j i=1 j l=i ∂f W * (s l , o l+1 ) ∂s l ∂f W * (s i-1 , o i ) ∂W = 0 ∂E(W * , β * , s * 0 ) ∂β = n i=1 ∂ β * (f W * (s i-1 , o i ); y i ) ∂β = 0 (14) ∂E(W * , β * , s * 0 ) ∂s 0 = ∂ β * (f W * (s * 0 , o 1 ); y 1 ) ∂f W + n-1 i=1 ∂ β * (f W * (s i , o i+1 ); y i+1 ) ∂f W (15) i l=1 ∂f W * (s l , o l+1 ) ∂s l ∂f W * (s * 0 , o 1 ) ∂s 0 = 0

The Lagrangian for ( 12) is

EQUATION

where λ i ∈ R k for 1 ≤ i ≤ n are Lagrange multipliers. We define λ 0 := 0 for convenience. The KKT equations for (16) are

∂L f pp (W * , β * , s * 0:n ) ∂W = n i=1 ∂ β * (f W * (s * i-1 , o i ); y i ) ∂f W ∂f W * (s * i-1 , o i ) ∂W (17) -λ T i ∂f W * (s * i-1 , o i ) ∂W = 0 ∂L f pp (W * , β * , s * 0:n ) ∂β = n i=1 ∂ β * (f W * (s * i-1 , o i ); y i ) ∂β = 0 ∂L f pp (W * , β * , s * 0:n ) ∂s j =      λ T n if j = n λ T j + ∂ β * (f W * (s * j ,oj+1);yj+1) ∂f W -λ T j+1 ∂f W * (s * j ,oj+1) ∂sj if 0 ≤ j < n (18) = 0 s * i = f W * (s * i-1 , o i ), ∀ 1 ≤ i ≤ n

First, let us find a closed-form expression for λ i .

Lemma 1. Let 0 ≤ j ≤ n. Then

λ T j = -   n-1 i=j ∂ β * (f W * (s * i , o i+1 ); y i+1 ) ∂f W i l=j ∂f W * (s * l , o l+1 ) ∂s l   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,

λ T m := - ∂ β * (f W * (s * m , o m+1 ); y m+1 ) ∂f W -λ T m+1 ∂f W * (s * m , o m+1 ) ∂s m = - ∂ β * (f W * (s * m , o m+1 ); y m+1 ) ∂f W + n-1 i=m+1 ∂ β * (f W * (s * i , o i+1 ); y i+1 ) ∂f W i l=m+1 ∂f W * (s * l , o l+1 ) ∂s l ∂f W * (s * m , o m+1 ) ∂s m = - ∂ β * (f W * (s * m , o m+1 ); y m+1 ) ∂f W ∂f W * (s * m , o m+1 ) ∂s m - n-1 i=m+1 ∂ β * (f W * (s * i , o i+1 ); y i+1 ) ∂f W i l=m+1 ∂f W * (s * l , o l+1 ) ∂s l ∂f W * (s * m , o m+1 ) ∂s m = - n-1 i=m ∂ β * (f W * (s * i , o i+1 ); y i+1 ) ∂f W i l=m ∂f W * (s * l , o l+1 ) ∂s l

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. This matches the corresponding equation in (13).

∂L f pp ∂W = n i=1 ∂ β * (f W * (s * i-1 , o i ); y i ) ∂f W ∂f W * (s * i-1 , o i ) ∂W + n i=1   n-1 j=i ∂ β * (f W * (s * j , o j+1 ); y j+1 ) ∂f W j l=i ∂f W * (s * l , o l+1 ) ∂s l   ∂f W * (s * i-1 , o i ) ∂W = n j=1 ∂ β * (f W * (s * j-1 , o j ); y j ) ∂f W ∂f W * (s * j-1 , o j ) ∂W + n-

Proposition 3. Let (W * , β * , s * 0:n ) be a local min of (12). Write the constraints of (12) as a vector: h(W, s 0:n

) := [(f W (s 0 , o 1 ) -s 1 ) T • • • (f W (s n-1 , o n ) -s n ) T (19)

Index each element of h by h i . Then the vectors ∇h i (W * , s * 0:n ) are linearly independent.

Proof. In the following, we will write ∂[g] l ∂x i j to mean the derivative of the l-th component of g with respect to the i-th component of x j . For compactness, write g(i) := f W * (s * i-1 , o i )s * i . We can write the Jacobian ∇h(W * , s * 0:n ) as 

∇h(W * , s * 0:n ) =              ∂[g(1)]1 ∂W 1 • • • ∂[g(1)]1 ∂W w ∂[g(1)]1 ∂s 1 1 • • • ∂[g(1)]1 ∂s k 1 • • • ∂[g(1)]1

∂[g(n)] k ∂W 1 • • • ∂[g(n)] k ∂W w ∂[g(n)] k ∂s 1 1 • • • ∂[g(n)] k ∂s k 1 • • • ∂[g(n)] k ∂s k n             

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 ∇[f W * (s * i-1 , o i ) -s * i ] j = 0.

In particular, for 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 ).

1 ≤ a ≤ n, 1 ≤ b ≤ k, k j=1 n i=1 λ ij ∂[f W * (s * i-1 , o i ) -s * i ] j ∂s b a = k j=1 n i=1 λ ij δ i-1 a ∂[f W * (s * i-1 , o i )]

:

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 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.

Figures and Tables:

Learning with More Data (15000 steps)

Figure 3: Average online performance for FPP (red), T-BPTT (orange) and No-Overlap T-BPTT (blue). 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 one standard error with (a) being run for 5000 steps, (b) for 10000 steps, (c) for 1000 images (28000 steps) and (d) for 5000 steps (5000 points in dataset, processed in order). FPP at T = 20, 30, 40 reaches a final solution with optimal performance; it is only above the second line because the plot shows average performance across all steps, rather than final performance.

Figure4: The performance for increase number of updates (with mini-batch of B = 1) and increasing mini-batch size (with number of updates M = 1). The numbers are average over 30 runs with 10000 training steps. The solid line is FPP and the dashed line is FPP without state updating.

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 ⊂ R w+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.

Since the norm and f are continuous and (-∞, ) is open, we have that N , a continuous preimage of an open set, is open.

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.

Assume n observations have been observed, o 1 , . . . , o n , with corresponding targets y 1 , . . . , y n . Let the state variables be stacked in a matrix S ∈ R

Table content: <table/>

, 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 s 0 ← 0 ∈ R d 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 o t , y t , and compute s

Table content: <table/>

Table 1, in Appendix C. This task is called Stochastic World.

Table content: <table><tr><td>p-CycleWorld</td></tr><tr><td>Ratio</td></tr><tr><td>Error with</td></tr><tr><td>respect</td></tr><tr><td>to</td></tr><tr><td>Baseline</td></tr><tr><td>Cycle Length</td></tr></table>

, β * , s * 0 ) such that ∀(W, β, s 0 ) ∈ N , we have E(W * , β * , s * 0 ) ≤ E(W, β, s 0 ). Without lossof 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 .

Table content: <table><tr><td>Let s  *  i be defined as above. Define M</td></tr></table>

where s0 := s * 0 . If we write ∂f W * (s l ,o l+1 ) ∂s

Table content: <table/>

(f W * (s * j , o j+1 ); y j+1 ) ∂f W By substituting in the constraint equations s * i = f W * (s * i-1 , o i ),this recovers exactly the gradient with respect to W in (13).Finally, consider the gradient with respect to s 0 .∂L f pp (W * , β * , s * 0:n ) ∂s 0 = λ T 0 + ∂ β * (f W * (s * 0 , o 1 ); y 1 ) ∂f W λ T 1 ∂f W * (s * 0 , o 1 ) ∂s 0 = ∂ β * (f W * (s * 0 , o 1 ); y 1 ) ∂f W +

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td>n-1</td><td>∂ β  *  (f W  *  (s  *  i , o i+1 ); y i+1 )</td></tr><tr><td/><td/><td/><td/><td/><td/><td>i=1</td><td>∂f W</td></tr><tr><td/><td/><td/><td>i</td><td colspan="3">∂f W  *  (s  *  l , o l+1 )</td><td>∂f W  *  (s  *  0 , o 1 )</td></tr><tr><td/><td/><td/><td>l=1</td><td/><td colspan="2">∂s l</td><td>∂s 0</td></tr><tr><td/><td/><td/><td>= 0.</td><td/><td/></tr><tr><td/><td>1</td><td>j</td><td colspan="4">∂ β  j</td><td>∂f W  *  (s  *  l , o l+1 )</td><td>∂f W  *  (s  *  i-1 , o i )</td></tr><tr><td/><td>j=1</td><td>i=1</td><td/><td/><td/><td>l=i</td><td>∂s l</td><td>∂W</td></tr><tr><td>=</td><td colspan="4">∂ β  *  (f W  *  (s  *  0 , o 1 ); y 1 ) ∂f W</td><td colspan="2">∂f W  *  (s  *  0 , o 1 ) ∂W</td><td>+</td><td>n-1 j=1</td><td>∂ β  *  (f W  *  (s  *  j , o j+1 ); y j+1 ) ∂f W</td></tr><tr><td/><td colspan="3">∂f W  *  (s  *  j , o j+1 ) ∂W</td><td>+</td><td>j i=1</td><td>j l=i</td><td>∂f W  *  (s  *  l , o l+1 ) ∂s l</td><td>∂f W  *  (s  *  i-1 , o i ) ∂W</td></tr><tr><td colspan="2">= 0.</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
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. The 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. The 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. The 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? In 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. One 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}. Other remarks: - the legend in Figure 4 is a dashed line, but the curves in the plots are dotted - the max. cycle length in CycleWorld is not clearly explained in the text, the name CycleWorld is not properly introduced