Deep Neutral Networks(DNNs) require huge GPU memory when training on modern image/video databases. Unfortunately, the GPU memory as a hardware resource is always finite, which limits the image resolution, batch size, and learning rate that could be used for better DNN performance. In this paper, we propose a novel training approach, called Re-forwarding, that substantially reduces memory usage in training. Our approach automatically finds a subset of vertices in a DNN computation graph, and stores tensors only at these vertices during the first forward. During backward, extra local forwards (called the Re-forwarding process) are conducted to compute the missing tensors between the subset of vertices. The total memory cost becomes the sum of (1) the memory cost at the subset of vertices and (2) the maximum memory cost among local re-forwards. Re-forwarding trades training time overheads for memory and does not compromise any performance in testing. We propose theories and algorithms that achieve the optimal memory solutions for DNNs with either linear or arbitrary computation graphs. Experiments show that Re-forwarding cuts down up-to 80% of training memory on popular DNNs such as Alexnet, VGG, ResNet, Densenet and Inception net.
I took a look at the revision.  I am glad to see that the authors clarified the meaning of "optimality" and added time complexity for each algorithm. The complexities of the algorithms do not seem great (3rd or 4th order polynomial of N) as they appear to be checking things exhaustively, but perhaps they are not a big issue since the decomposition algorithm is run only once and usually N is not huge. I wonder if more efficient algorithms exist.
It is also nice to see that the time overhead for one training step is not huge (last column of Table 1). While I still think it is better to see more complete training curves, the provided time overhead is a proxy. 
I hope the authors can further improve the algorithm description, for example, the pseudo-code of Algorithm 1 is very verbal/ambiguous, and it would be better to have more implementation-friendly pseudo-code.
Despite the above-mentioned flaws, I think this work is still valuable in handling the memory consumption of arbitrary computation graph in a principled manner. 
=============================================================================
This paper presents a method for reducing the memory cost of training DNNs. The main idea is to divide the computational graph into smaller components (close sets), such that the dependency between components is low, and so one can store only tensors at key vertices in each component during the forward pass. In the backward pass, one needs to re-forward the data within each close set for computing the gradient. 
The idea is quite intuitive and the example in linear computational graph in Section 3 clearly demonstrates the basic idea. The main technical development is in the case of arbitrary computation graph (Section 4), where the authors explain how to divide the computational graph into different types of close sets. I have not read the proofs in appendix, but it is clear that the technical development is mainly in discrete math rather than machine learning. For this part, my suggestions are:
1. give better algorithm description: what are the inputs and outputs of each algorithm, for the examples in Figure 2-4 (and perhaps with costs for each vertex), which vertices do the final algorithm decide to store
2. analyze the complexity of each algorithm
3. provide clear definition of "optimality" and its proof: the authors mentioned in a few places about the method being "optimal", but the paper needs to be crystal clear about "for what problem is the method optimal", "optimal in what sense (the objective)".  
The more concerning part is the experimental evaluation. While I believe that the proposed method can save memory cost, there is no result on the additional time cost for re-forwarding. Therefore, it is not clear if it is worth the extra complication of using re-forwarding in an end-to-end sense: the authors motivated in Section 1 that saving memory cost allows one to use larger mini-batches, and an important benefit of large mini-batch is to accelerate training, see, e.g.,
Goyal et al. Accurate, large minibatch SGD: Training imagenet in 1 hour. 
Hoffer et al. Train longer, generalize better: Closing the generalization gap in large batch training of neural networks.
It is less desirable to use re-forwarding it if it causes significant latency in the backward pass and training. An good demonstration of the memory vs. time tradeoff would be the training curves of loss vs. running time.
The other detail I would appreciate is how the authors implemented the algorithm, and whether the proposed method is likely to be deployed on popular ML frameworks, which would improve the significance of the work.