Published as a conference paper at ICLR 2018 UNBIASED ONLINE RECURRENT OPTIMIZATION
The novel Unbiased Online Recurrent Optimization (UORO) algorithm allows for online learning of general recurrent computational graphs such as recurrent network models. It works in a streaming fashion and avoids backtracking through past activations and inputs. UORO is computationally as costly as Truncated Backpropagation Through Time (truncated BPTT), a widespread algorithm for online learning of recurrent networks Jaeger (2002). UORO is a modification of NoBackTrack Ollivier et al. (2015) that bypasses the need for model sparsity and makes implementation easy in current deep learning frameworks, even for complex models. Like NoBackTrack, UORO provides unbiased gradient estimates; unbiasedness is the core hypothesis in stochastic gradient descent theory, without which convergence to a local optimum is not guaranteed. On the contrary, truncated BPTT does not provide this property, leading to possible divergence. On synthetic tasks where truncated BPTT is shown to diverge, UORO converges. For instance, when a parameter has a positive short-term but negative long-term influence, truncated BPTT diverges unless the truncation span is very significantly longer than the intrinsic temporal range of the interactions, while UORO performs well thanks to the unbiasedness of its gradients.
Current recurrent network learning algorithms are ill-suited to online learning via a single pass through long sequences of temporal data. Backpropagation Through Time (BPTT Jaeger (2002)), the current standard for training recurrent architectures, is well suited to many short training sequences. Treating long sequences with BPTT requires either storing all past inputs in memory and waiting for a long time between each learning step, or arbitrarily splitting the input sequence into smaller sequences, and applying BPTT to each of those short sequences, at the cost of losing long term dependencies. This paper introduces Unbiased Online Recurrent Optimization (UORO), an online and memoryless learning algorithm for recurrent architectures: UORO processes and learns from data samples sequentially, one sample at a time. Contrary to BPTT, UORO does not maintain a history of previous inputs and activations. Moreover, UORO is scalable: processing data samples with UORO comes at a similar computational and memory cost as just running the recurrent model on those data.
Like most neural network training algorithms, UORO relies on stochastic gradient optimization. The theory of stochastic gradient crucially relies on the unbiasedness of gradient estimates to provide convergence to a local optimum. To this end, in the footsteps of NoBackTrack (NBT) Ollivier et al. (2015), UORO provides provably unbiased gradient estimates, in a scalable, streaming fashion.
Unlike NBT, though, UORO can be easily implemented in a black-box fashion on top of an existing recurrent model in current machine learning software, without delving into the structure and code of the model.
The framework for recurrent optimization and UORO is introduced in Section 2. The final algorithm is reasonably simple (Alg. 1), but its derivation (Section 3) is more complex. In Section 6, UORO is shown to provide convergence on a set of synthetic experiments where truncated BPTT fails to display reliable convergence. An implementation of UORO is provided as supplementary material.
Current recurrent network learning algorithms are ill-suited to online learning via a single pass through long sequences of temporal data. Backpropagation Through Time (BPTT Jaeger (2002)), the current standard for training recurrent architectures, is well suited to many short training sequences. Treating long sequences with BPTT requires either storing all past inputs in memory and waiting for a long time between each learning step, or arbitrarily splitting the input sequence into smaller sequences, and applying BPTT to each of those short sequences, at the cost of losing long term dependencies. This paper introduces Unbiased Online Recurrent Optimization (UORO), an online and memoryless learning algorithm for recurrent architectures: UORO processes and learns from data samples sequentially, one sample at a time. Contrary to BPTT, UORO does not maintain a history of previous inputs and activations. Moreover, UORO is scalable: processing data samples with UORO comes at a similar computational and memory cost as just running the recurrent model on those data.
Like most neural network training algorithms, UORO relies on stochastic gradient optimization. The theory of stochastic gradient crucially relies on the unbiasedness of gradient estimates to provide convergence to a local optimum. To this end, in the footsteps of NoBackTrack (NBT) Ollivier et al. (2015), UORO provides provably unbiased gradient estimates, in a scalable, streaming fashion.
Unlike NBT, though, UORO can be easily implemented in a black-box fashion on top of an existing recurrent model in current machine learning software, without delving into the structure and code of the model.
The framework for recurrent optimization and UORO is introduced in Section 2. The final algorithm is reasonably simple (Alg. 1), but its derivation (Section 3) is more complex. In Section 6, UORO is shown to provide convergence on a set of synthetic experiments where truncated BPTT fails to display reliable convergence. An implementation of UORO is provided as supplementary material.
Post-rebuttal update:
I am happy with the rebuttal and therefore I will keep the score of 7.
This is a very interesting paper. Training RNN's in an online fashion (with no backpropagation through time) is one of those problems which are not well explored in the research community. And I think, this paper approaches this problem in a very principled manner. The authors proposes to use forward approach for the calculation of the gradients. The author proposes to modify RTRL by maintaining a rank one approximation of jacobian matrix (derivative of state w.r.t parameters)  which was done in NoBackTrack Paper. The way I think this paper is different from NoBackTrack Paper is that this version can be implemented in a black box fashion and hence easy to implement using current DL libraries like Pytorch. 
Pros.
- Its an interesting paper, very easy to follow, and with proper literature survey.
Cons:
- The results are quite preliminary. I'll note that this is a very difficult problem.
- "The proof of UORO’s convergence to a local optimum is soon to be published Masse & Ollivier (To appear)."  I think, paper violates the anonymity.  So, I'd encourage the authors to remove this. 
Some Points: 
- I find the argument of stochastic gradient descent wrong (I could be wrong though). RNN's follow the markov property (wrt hidden states from previous time step and the current input) so from time step t to t+1, if you change the parameters, the hidden state at time t (and all the time steps before) would carry stale information unless until you're using something like eligibility traces from RL literature. I also don't know how to overcome this issue. 
- I'd be worried about the variance in the estimate of rank one approximation. All the experiments carried out by the authors are small scale (hidden size = 64). I'm curious if authors tried experimenting with larger networks, I'd guess it wont perform well due to the high variance in the approximation. I'd like to see an experiment with hidden size  = 128/256/512/1024. My intuition is that because of high variance it would be difficult to train this network, but I could be wrong. I'm curious what the authors had to say about this. 
- If the variance of the approximation is indeed high, can we use something to control the dynamics of the network which can result in less variance. Have authors thought about this ? 
- I'd also like to see experiments on copying task/adding task (as these are standard experiments which are done for analysis of long term dependencies) 
- I'd also like to see what effect the length of sequence has on the approximation. As small errors in approximation on each step can compound giving rise to chaotic dynamics. (small change in input => large change in output)
- I'd also like to know how using UORO changes the optimization as compared to Back-propagation through time in the sense, does the two approaches would reach same local minimum ? or is there a possibility that the former can reach "less" number of potential local minimas as compared to BPTT. 
I'm tempted to give high score for this paper( Score - 7) , as it is unexplored direction in our research community, and I think this paper makes a very useful contribution to tackle this problem in a very principled way.  But I'd like some more experiments to be done (which I have mentioned above), failing to do those experiments, I'd be forced to reduce the score (to score - 5)