  One of the central goals of Recurrent Neural Networks (RNNs) is to learn
long-term dependencies in sequential data. Nevertheless, the most popular
training method, Truncated Backpropagation through Time (TBPTT), categorically
forbids learning dependencies beyond the truncation horizon. In contrast, the
online training algorithm Real Time Recurrent Learning (RTRL) provides
untruncated gradients, with the disadvantage of impractically large
computational costs. Recently published approaches reduce these costs by
providing noisy approximations of RTRL. We present a new approximation
algorithm of RTRL, Optimal Kronecker-Sum Approximation (OK). We prove that OK
is optimal for a class of approximations of RTRL, which includes all approaches
published so far. Additionally, we show that OK has empirically negligible
noise: Unlike previous algorithms it matches TBPTT in a real world task
(character-level Penn TreeBank) and can exploit online parameter updates to
outperform TBPTT in a synthetic string memorization task. Code availiable on
github.
