Memory-Efficient Backpropagation Through Time

By Audrunas Gruslys, R´emi Munos, Ivo Danihelka, Marc Lanctot, Alex Graves. 2016

273 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Efficiency & Compression

Citations in the corpus

Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer (2017, methodology): “Gruslys et al. (2016) describe a technique for drastically reducing the number of stored activations in an unrolled RNN, at the cost of recomputing forward activations.”
Train Large, Then Compress: Rethinking Model Size for Efficient Training and Inference of Transformers (2020, background): “, 2019; Tan & Le, 2019), backpropagation storage requirements (Gruslys et al., 2016), or learning rate schedules (Loshchilov & Hutter, 2017; Li et al.”
Generating Long Sequences with Sparse Transformers (2019, background): “Gradient checkpointing has been shown to be effective in reducing the memory requirements of training deep neural networks (Chen et al., 2016), (Gruslys et al., 2016).”
The Reversible Residual Network: Backpropagation Without Storing Activations (2017, methodology): “Checkpointing [22, 5, 12] is one well-known technique which (3)We assume for notational clarity that the residual functions do not share parameters, but Algorithm 1 can be trivially extended to a network with weight sharing, such as a recurrent neural net.”
UberNet: Training a Universal Convolutional Neural Network for Low-, Mid-, and High-Level Vision Using Diverse Datasets and Limited Memory (2016, methodology): “We propose instead an algorithm that trades off computation time with memory complexity, adapting the work of [12, 21] to exploit the particularities of our multi-task setup.”
In-place Activated BatchNorm for Memory-Optimized Training of DNNs (2017, methodology): “In [8] this is further optimized with dynamic programming, where a storage policy is determined that minimizes the computational costs for re-computation at a fixed memory budget.”
Supporting Very Large Models using Automatic Dataflow Graph Partitioning (2018, methodology): “If output tensor B is partitioned along i, with each worker computing B over range [0, 4] (or [5, 9]), we can easily deduce that the worker needs A’s data over [2, 6] (or [7, 11]).”
Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization (2019, background): “This generalizes checkpointing [9, 16, 22, 23, 51], as values can be retained and deallocated many times in our schedules.”
Demystifying Parallel and Distributed Deep Learning (2018, methodology): “pendencies have been met. Overall, these optimizations result in ∼11× performance increase over the high-level implementation. From the memory consumption perspective, dynamic programming was proposed[86] for RNNs (see Fig.13a) in order to balance between caching intermediate results and recomputing”
Full-Resolution Residual Networks for Semantic Segmentation in Street Scenes (2016, background): “The idea of recomputing some intermediate results on demand is also used in [22] and [10].”
SwapAdvisor: Pushing Deep Learning Beyond the GPU Memory Limit via Smart Swapping (2020, background): “Some other solutions discard intermediate data and recompute them later when needed [2, 11, 29].”
Spatially Parallel Convolutions (2018, methodology): “Other approaches reduce working memory size but increase computation time: these include simply executing convnets on overlapping slices of the input, as well as sophisticated checkpointing techniques (Chen et al., 2016; Gruslys et al., 2016).”
TinyTL: Reduce Memory, Not Parameters for Efficient On-Device Learning (2020, methodology): “One typical approach is to re-compute discarded activations during backward [28, 29].”
Buddy Compression: Enabling Larger Memory for Deep Learning and HPC Workloads on GPUs (2019, methodology): “Similarly, Buddy compression could be used in conjunction with other strategies like checkpointing [37] and Gist [18], where the performance-to-capacity trade-offs would be improved.”
Unbiased Online Recurrent Optimization (2017, background): “Gruslys et al. (2016). However, storage of all past inputs is necessary.”
Gist: Efficient Data Encoding for Deep Neural Network Training (2018, background): “[4], [14] presents details of MxNet’s memory sharing and inplace optimizations.”
Layer-Centric Memory Reuse and Data Migration for Extreme-Scale Deep Learning on Many-Core Architectures (2018, background): “Memory allocation for DNNs can be treated as a less general case of the graph optimization problems where the graph of forward computation is a chain and gradients have to be chained in a reverse order [15].”
Dynamic Tensor Rematerialization (2020, methodology): “[11] Audrunas Gruslys, Rémi Munos, Ivo Danihelka, Marc Lanctot, and Alex Graves.”