PARALLELIZING LINEAR RECURRENT NEURAL NETS OVER SEQUENCE LENGTH
Recurrent neural networks (RNNs) are widely used to model sequential data but their non-linear dependencies between sequence elements prevent parallelizing training over sequence length. We show the training of RNNs with only linear sequential dependencies can be parallelized over the sequence length using the parallel scan algorithm, leading to rapid training on long sequences even with small minibatch size. We develop a parallel linear recurrence CUDA kernel and show that it can be applied to immediately speed up training and inference of several state of the art RNN architectures by up to 9x. We abstract recent work on linear RNNs into a new framework of linear surrogate RNNs and develop a linear surrogate model for the long short-term memory unit, the GILR-LSTM, that utilizes parallel linear recurrence. We extend sequence learning to new extremely long sequence regimes that were previously out of reach by successfully training a GILR-LSTM on a synthetic sequence classification task with a one million timestep dependency.
# Summary and Assessment
The paper addresses an important issue–that of making learning of recurrent networks tractable for sequence lengths well beyond 1’000s of time steps. A key problem here is that processing such sequences with ordinary RNNs requires a reduce operation, where the output of the net at time step t depends on the outputs of *all* its predecessor. 
The authors now make a crucial observation, namely that a certain class of RNNs allows evaluation in a non-linear fashion through a so-called SCAN operator. Here, if certain conditions are satisfied, the calculation of the output   can be parallelised massively.
In the following, the authors explore the landscape of RNNs satisfying the necessary conditions. The performance is investigated in terms of wall clock time. Further, experimental results of problems with previously untacked sequence lengths are reported.
The paper is certainly relevant, as it can pave the way towards the application of recurrent architectures to problems that have extremely long term dependencies.
To me, the execution seems sound. The experiments back up the claim.
## Minor
- I challenge the claim that thousands and millions of time steps are a common issue in “robotics, remote sensing, control systems, speech recognition, medicine and finance”, as claimed in the first paragraph of the introduction. IMHO, most problems in these domains get away with a few hundred time steps; nevertheless, I’d appreciate a few examples where this is a case to better justify the method.