Memory-Efficient Backpropagation Through Time
We propose a novel approach to reduce memory consumption of the backpropagation through time (BPTT) algorithm when training recurrent neural networks (RNNs). Our approach uses dynamic programming to balance a trade-off between caching of intermediate results and recomputation. The algorithm is capable of tightly fitting within almost any user-set memory budget while finding an optimal execution policy minimizing the computational cost. Computational devices have limited memory capacity and maximizing a computational performance given a fixed memory budget is a practical use-case. We provide asymptotic computational upper bounds for various regimes. The algorithm is particularly effective for long sequences. For sequences of length 1000, our algorithm saves 95% of memory usage while using only one third more time per iteration than the standard BPTT.
Training recurrent neural networks requires unfolding the network in time and computing the backpropagation "through time". In order to perform it efficiently and to avoid recomputing intermediate values, these are usually stored in memory. However, as considered sequences increase in length and networks grow in size, the amount of available memory might not be sufficient. An usual solution is to truncate the backpropagation, resulting in approximate weight updates. It is also possible to recompute the forward pass, which is inefficient in computation time. Finally, heuristical "divide-and-conquer" approaches have been proposed to trade off between computation time and memory efficiency. The authors of this paper propose a new solution, in order to find the optimal strategy to get an algorithm both memory-efficient and not too expensive in terms of computation. More particularly, they define a cost as the number of forward operations needed to compute BPTT given a fixed memory budget. This cost is minimized with dynamic programing, in terms of when to store the intermediate results in memory versus when to recompute them. They study storing the hidden state of recurrent networks (i.e. output of the recurrent neurons), the internal state (needed to compute this output) or both, which each correspond to a different formulation of the cost. They show that this simple method can achieves 95% memory saving while being only 33% slower, and derive theoretical bounds in terms of the sequence length and memory budget. Their method is compared to naive baselines and to an handcrafted heuristical method. 
This paper is very well written and pleasant to read. Although the figures supporting the explanations take some room, every bit is important and adds to the clarity of the paper.  The idea to use dynamic programing to define when to store the intermediates in order to limit the number of forward operations in fixed memory budget scenarii is quite simple and well defined. The notation is clear and the figures are helpful. The chosen baselines are relevant (limit cases + heuristical divide-and-conquer method previously published). More importantly, this paper addresses a real problem, given the popularity of recurrent neural networks these days, along with the increasing size of models designed and sequences processed. I believe that in that scenario, many experimenters give up exact computation and use a truncated version of the backpropagation through time (quite a few papers in the last few years). This paper provides a simple and elegant solution, with all necessary details to implement it, including pseudo-code, which is highly appreciable. Following are a few remarks and cosmetic issues:  - I did not quite understand how the 33% time increase can be deduced from Fig.5a. (end of p4)  - Sect. 3.2 : typo in second paragraph ( "on less memory slot" )  - Fig 2b (in caption) : "per time step. sured in ms"  - Sect. 4.2 : missing cap "in figure 7" (last paragraph)  - Suppl., p3, last line : pb with ref: "Section ??"  - Right-hand side of Fig.7 I guess the point was to show that curves overlap, but one can hardly see those curves. More generally, a legend on the figures rather than inside the captions would be appreciated, and increase the clarity of the figures. The titles and axes labels could also be bigger.