Approximating Real-Time Recurrent Learning with Random Kronecker Factors
Despite all the impressive advances of recurrent neural networks, sequential data is still in need of better modelling. Truncated backpropagation through time (TBPTT), the learning algorithm most widely used in practice, suffers from the truncation bias, which drastically limits its ability to learn long-term dependencies.The Real-Time Recurrent Learning algorithm (RTRL) addresses this issue, but its high computational requirements make it infeasible in practice. The Unbiased Online Recurrent Optimization algorithm (UORO) approximates RTRL with a smaller runtime and memory cost, but with the disadvantage of obtaining noisy gradients that also limit its practical applicability. In this paper we propose the Kronecker Factored RTRL (KF-RTRL) algorithm that uses a Kronecker product decomposition to approximate the gradients for a large class of RNNs. We show that KF-RTRL is an unbiased and memory efficient online learning algorithm. Our theoretical analysis shows that, under reasonable assumptions, the noise introduced by our algorithm is not only stable over time but also asymptotically much smaller than the one of the UORO algorithm. We also confirm these theoretical results experimentally. Further, we show empirically that the KF-RTRL algorithm captures long-term dependencies and almost matches the performance of TBPTT on real world tasks by training Recurrent Highway Networks on a synthetic string memorization task and on the Penn TreeBank task, respectively. These results indicate that RTRL based approaches might be a promising future alternative to TBPTT.
SUMMARY:  This paper proposes a Kronecker factored variant of the Real-Time Recurrent Learning algorithm (RTRL) proposed by Ollivier et al, called KF-RTRL. The main obstacle of using RTRL in place of Truncated Back-Propagation Through Time (BPTT) to train RNN is its computational complexity of O(n^4) where n is the number of units. To address this issue, the Unbiased Online Recurrent Optimization (UORO) algorithm proposed to approximate RTRL using a rank one matrix to approximate the matrix of derivatives of the hidden state h_t wrt the parameters (henceforth denoted by G_t, of size n x n^2), reducing the complexity to O(n^2) at the cost of introducing variance to the unbiased estimator of the gradient. Instead, KF-RTRL approximates G_t by the Kronecker product of a 1xn vector and an nxn matrix, to obtain an unbiased estimator with less variance with a complexity of O(n^3), thus trying to find a middle ground between UOFO and RTRL. The correctness of the proposed algorithm is analyzed but only informal theoretical arguments are given for the improvement in terms of variance wrt UORO. Still, the experiments on the synthetic copy/paste task and on the Penn tree bank show that KF-RTRL performs better than UORO in terms of convergence rate of the training algorithm.   OPINION:  The contribution is interesting and the idea to replace the restrictive rank one approximation of UORO by a more expressive factorization while still achieving better computational complexity than RTRL is worthwhile. Regarding clarity the paper could be first improved by a careful proof reading and polishing. The exposition of the results could also be improved: it is for example clumsy to defer the definition of the class of RNN for which Theorem 1 holds to Lemma 1, when Lemma 1 actually has not much to do with Theorem 1 (it only serve the argument that the class of RNN considered is not too restrictive); the actual definition of the class of RNN in Lemma 1 is also difficult to grasp/parse and would necessitate more discussion (see my questions below). I also find the arguments used to claim that the variance introduced by KF-RTRL is smaller than the one of UORO very 'hand-wavy' and I would have appreciated a more formal analysis. On the positive side, the experiment section indeed suggests that KF-RTRL is an attractive alternative to both BPTT and UORO and the code is directly supplied as supplementary material.   REMARKS/QUESTIONS:  - line 106-108: I don't understand what is meant here, could you clarify?   - Algorithm 1: It may be worth precising what the z^k_j are, what SGDopt is, and which norm is used.  - Lemma 1 - definition of the RNN class: What do the matrices W^1,...,W^R correspond to? Is it correct that for vanilla RNN with one hidden layer we would have r=1 and W^1 would be the concatenation of the input and recurrent matrices? How is the bias term of the hidden layer handled in this definition? Does this class encompasses multi-layer RNNs? I think more attention should be put on this definition and more discussion/intuition given.  - line 178: what are the distributions over u_{t-1} and A_{t-1} mentioned here?  - I think RTRL should be included in the comparison for the experiments in Sections 5.1 and 5.2. Is there a reason why it is not the case?   MINOR COMMENTS/TYPOS:  -line 51: that -> than -line 58: on -> in -line 164: this sentence is a bit misleading, maybe add 'in expectation' somewhere. -line 176: the phrasing is strange, maybe use 'since u_{t-1}' is a row vector' instead. -line 203: $UORO$ -> UORO -line 230: with out -> without -line 236: do you mean 'validation error' instead of 'RNN error'? -line 240: RHN -> RNN -footnote 1 p.6: it is not clear to me how this simplify the implementation.  -caption of Fig 1: an -> a -Fig 1 x-axis legend: what is 'data time'? -line 403: Equqtion