CUTTING DOWN TRAINING MEMORY
Year: 2018

Abstract:
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.

heading: 1 INTRODUCTION
text: The standard DNN training process consists of two alternated stages: forward and backward. Fig. 1 (a) illustrates an example of feed-forward neural networks. In the forward stage, the network takes an input tensor, [BatchSize× Channel ×Width×Height], and computes the tensors at each layer until producing the output. In the backward stage, difference between the output and ground truth is passed back along the network to compute the gradients at each layer. The regular training approach saves tensors at all layers during forward, because they are all needed to compute gradients during backward. The total memory cost is the sum of cost over all layers.
In popular backbone DNNs for feature extraction of images, such as AlexNet (Krizhevsky et al. (2012)), VGG (Simonyan & Zisserman (2014)) and ResNet (He et al. (2016)), the memory cost increases quadratically with the input image resolution and network depth. For example, given an median size input tensor of (32, 3, 224, 224), ResNet101 requires around 5000 MB. In more challenging tasks, DNNs that detect small objects and large number of object categories require input image resolution of more than 600 × 600 (Ren et al. (2015); Singh et al. (2017); Redmon & Farhadi (2018)). The memory issue is worse for video-based DNNs, such as CDC (Shou et al. (2017)), C3D (Ji et al. (2013)) and 3D-ResNet (Hara et al. (2017)). To model complex activities in video, the input tensor may contain 64 frames. Moreover, DNN training takes much more memory than testing. In order to train DNNs with large databases and big learning rate, the batch size can be up to 64. In training DNN compositions, such as Generative adversarial networks (GANs), multiple generator and discriminator networks are simultaneously stored in GPU memory.
Existing efforts to address memory issues presented three main approaches: (1) Better single GPUs. Recent GPUs provide larger memory at the expense of exponentially growing price and power consumption. For instance, from TitanXp, Quadro P6000 to Tesla V100, for 1-2.7 times increase in memory, the prices increase 2.8-8.5 times. (2) Parallelization among multiple GPUs (Dean et al. (2012); Shi et al. (2009); Langford et al. (2009); Mcdonald et al. (2009); McDonald et al. (2010); Zinkevich et al. (2010); Agarwal et al. (2014); Agarwal & Duchi (2011)), which requires expensive
clusters, introduces substantial I/O cost, and does not reduce the total memory cost. (3) Low-level heuristic techniques. Optimization of computation graphs (Aho et al. (1986)), which merges inplace operations into non-inplace operations to cut down memory. Liveness analysis (Aho et al. (1986)), which dynamically recycles garbage tensors in training epochs. These approaches are specific to certain DNN structures, data and tasks.
To address above issues, we propose a fundamental approach that explores trade-off between memory and computation power of GPUs. Note that recent affordable GPUs, although limited in memory ( 12GB), provide exceptional improvement in GPU cores and FLOPS. Trading computational time for memory is a very attractive solution that make it possible to train very heavy DNNs with finite GPU memory. Our approach only saves tensors at a subset of layers during the first forward, and conduct only extra local forwards to compute the missing tensors needed during backward. We call the extra forward process as Re-forwarding. The total memory cost is the sum of (1) the cost at the subset of layers and (2) the maximum memory cost among local re-forwards. Training with Reforwarding, see Fig. 1 (b), leads to substantial memory reduction. We propose sophisticate theories and efficient algorithms that achieve the optimal memory solution of arbitrary computation graphs.

heading: 2 RELATED WORK
text: To alleviate the memory pressure from a single GPU processor, many researchers utilized the wellestablished techniques for distributed computation (Dean et al. (2012); Shi et al. (2009); Langford et al. (2009); Mcdonald et al. (2009); McDonald et al. (2010); Zinkevich et al. (2010); Agarwal et al. (2014); Agarwal & Duchi (2011)). These techniques distribute memory pressure to possibly infinite GPUs or server clusters, but do not reduce the total memory cost of DNNs.
Other researchers reduced the memory on finite hardware by optimizing computation graph of DNN and performing liveness analysis. The computation graph of DNNs describes the dependencies of tensors among layers. Liveness analysis recycles garbage to manage memory. These ideas were originated from compiler optimization (Aho et al. (1986)) and has been widely adopted by deep learning frameworks: Theano (Bastien et al. (2012); Bergstra et al. (2010)), MXNet (Chen et al. (2015)), Tensorflow (Abadi et al. (2016)) and CNTK (Yu et al. (2014)). Some other techniques efficiently swap data between CPU and GPU (Wang et al. (2018); Rhu et al. (2016)). These techniques usually cost extra I/O time and still do not actually reduce the total memory cost.
The closest work to our approach, Chen et al.(Chen et al. (2016)), uses the gradient checkpoints (similar to the subset of layers in Re-forwarding). However, (Chen et al. (2016)) only worked on linear computation graph via a heuristic algorithm. Our approach generates optimal solutions for both linear and arbitrary computation graphs. Our algorithm reduces training memory by manipulating high-level tensors, therefore is generalizable to any DNNs and their compositions. All previous techniques are compatible to our approach and can further improve the memory efficiency of DNN training.

heading: 3 LINEAR COMPUTATION GRAPH (LCG)
text: Denote a computation graph as G = ( E, V ) . E = {ei} and V = {vi} are the edges and vertices in the computation graph, respectively. In deep neural networks, the vertices represent the tensors and the edges represent operations. Denote function l(·) as a measure of memory cost. VR is the subset of vertices saved during the first forward. l(vi) is defined as the memory cost of storing vertex vi. For two adjacent vertices vi and vj in set VR, the memory cost during re-forwarding from vi to vj is defined as l(vi, vj) = ∑j−1 t=i+1 l(vt), which is the sum of cost over all the vertices between vi and vj . Using these notations, the memory cost of training with re-forwarding is formulated as
min VR ∑ i l(vi) + max j l(vj , vj+1), (1)
where the first term is the sum of the memory cost of all the stored tensors, and the second term is the maximal cost among the re-forwards.
For easy illustration, we start by formulating Re-forwarding on Linear Computation Graphs (LCG) (Fig. 2 (a)). For LCGs, Eqn. 1 can be solved in two cases.
Case(1) LCG with Identical Vertex Cost: Suppose a LCG has N vertices, each of which has the same cost l(vi) = 1N and the total cost is 1. Obviously, the optimal solution is reached when vertices in VR are distributed evenly in the LCG. Suppose the number of vertices in VR is k. The total cost is then kN + 1 k . The optimal solution of Eqn. 1 is k = √ N , and the optimal total cost is 2√ N .
Case (2) LCG with Non-identical Vertex Cost: When the assumption of identical cost does not hold, the solution to Eqn. 1 does not have an analytic form. Denote the maximal Re-forward cost max
j l(vj , vj+1) as a constant C, and the solution to Eqn. 1 is reduced to solving for min
VR
∑ i l(vi).
Algorithm 1 Linear Computation Graph (LCG) Solver 1: for each vertex pair (vi, vj) in G do 2: Set the maximal term as l(vi, vj) 3: Construct Accessibility Graph 4: Find the shortest path in the Accessibility Graph as the solution 5: Compute the actual total cost of the solution 6: Save the solution if it’s better. 7: Suppose the actual max term of this solution is B, and l(vi, vj) = C, skip the loops where
B ≤ l(vi, vj) < C
All the Re-forward costs in an optimal solution satisfy the constraint l(vj , vj+1) ≤ C. We solve Eqn. 1 by constructing a new graph, called Accessibility Graph GA = ( EA, V ) . The edges of GA,
called Accessibility Edge eAij , exists between vertex vi and vj if and only if l(vi, vj) ≤ C. Now the problem of solving min
VR
∑ i l(vi) is equivalent to finding the shortest path from the source vertex
and the target vertex in the Accessibility Graph. Notice that in the optimal solution, the max term equal the one maximal term among all l(vi, vi+1) terms. To traverse all possible max terms, we can simply compute the loss of every vertex pair and use it as a possible max term. Given a max term C, suppose the actual max term of the solution under C is B and B < C. It’s obvious that for all the max terms B ≤ max < C, the solution would be the same solution. Therefore, these max terms can be skipped. Algorithm 1 summarizes the process for searching an optimal solution for
LCG. Suppose there are N vertices in the computation graph, the time complexity of Algorithm 1 is O(N4)1.

heading: 4 ARBITRARY COMPUTATION GRAPH(ACG)
text: As generalization of DNNs with LCG, we present theory2 and algorithms for DNNs with Arbitrary Computation Graphs (ACG), in particular the acyclic directed graphs(Fig. 2 (b)).

heading: 4.1 ASSUMPTION FOR OPTIMALITY
text: The optimal solution of Re-forwarding corresponds to an optimal division of ACG, such that memory cost (Eqn. 1) is minimum. We denote that an ACG is divided into end-to-end segments by a set of vertices. These end-to-end segments can have multiple endpoint vertices, for example, multiple source vertices and multiple target vertices. In this paper, as an assumption and also for simplification, these end-to-end segments are narrowed down to those with only one source vertex and one target vertex.
Another assumption in the case of ACG is imposed on the operation that has multiple inputs: one can compute the gradients of output with respect to the gradients of inputs without using the current value of inputs. Examples of operations that meet this assumption are: concatenation (the gradient of output is also the concatenation of the gradient of input), add (the gradient of output equals the gradient of input), etc. An example that breaks this assumption is multiplication (the gradient of input depends on the input). Fortunately, most of the popular networks meet this assumption. A simple way to remove this assumption is to store all the input tensors of this multi-input operation. However, this is not modeled by our loss function and may lead to sub-optimal solution.
In summary, there are only two assumptions in our approach: (1) the segment in a solution only has two endpoints (source and target). (2) the multi-input operation can compute the gradients of output without using the current value of input. Under these two assumptions, our approach is optimal for ACGs.

heading: 4.2 DEFINITION AND THEOREM
text: Definition 2. [sij ] = sij ∪ {vi, vj}. [sij) = sij ∪ {vi}. (sij ] = sij ∪ {vj}
In the definition of Closed Set, property 1 corresponds to the two endpoint assumption in section 4.1 where the two endpoints become vi and vj in the definition. Property 2 confines the edge subsets of
1More detailed complexity analysis is in the appendix due to space limitation 2All proofs are in the appendix due to space limitation.
s to be one of two cases: E′ or E′ − {eij}. Both cases are valid although they have different edges. Property 3 guarantees the independence of such a set s, meaning that the vertices within s have no connections with other vertices outside s ∪ {vi, vj}. As there might be multiple valid closed sets between vi and vj , which corresponds to the Branched Closed Set in Definition 5, we denote the largest closed set between vi and vj as sij and denote smaller closed set with an extra superscript, such as s1ij . Definition 3. Splitting Vertex: A vertex vt ∈ sij is a splitting vertex of sij if and only if sit exists, stj exists and sij = sit ∪ stj ∪ {vt} and sit ∩ stj = ∅ Definition 4. Splittable Closed Set (Type 1): closed set with at least 1 splitting vertex.
The definition of Splitting Vertex is to describe whether a closed set can be divided into two linearly arranged closed set. A closed set is splittable if it has at least 1 splitting vertex and is defined as Closed Set Type 1. Definition 5. Branched Closed Set (Type 2): A closed set is branched if it has 0 splitting vertex and can be divided into branches: sij = s1ij ∪ s2ij and s1ij ∩ s2ij = ∅ Definition 6. Non-branched Closed Set (Type 3): A closed set sij is non-branched if it has 0 splitting vertex and no branch: 6 ∃s1ij $ sij
Among closed set with no splitting vertex, we categorize closed set with branches as Closed Set Type 2, and closed set without branches as Closed Set Type 3. The examples of different types of closed set are shown in Fig. 3.
Definition 7. Maximal Split: {[spq]} is a maximal split of non-branched sij if [sij ] = ∪{[spq]} and ∀sab, scd ∈ {[spq]}, sab ∩ scd = ∅ and 6 ∃{[s′pq]} $ {[spq]} such that ∪{[s′pq]} = [skt] $ [sij ] Definition 8. Division of Closed Set: For type 1, its division is the linear segments separated by all its splitting vertices; for type 2, its division is all its branches, any of which cannot be divided into more branches; for type 3, its division is its maximal split.
For closed set type 1, it can be divided into linearly arranged segments. For closed set type 2, it can be divided into branches. So here we investigate the division of closed set type 3. As we don’t want trivial division, for example, division that is formed by every edge in the closed set, we define Maximal Split to describe the split such that each member of the split is as large as possible. An example of maximal split is shown in Fig. 4 (c). In the definition of maximal split, the term maximal is implied by saying that any subset of this split cannot be combined into a single closed set. If it can, then the maximal split will be formed by this larger closed set and all the rest of the previous split. For closed set type 3, we use its maximal split as its division. Definition 9. Division Tree: Division tree is a representation of a computation graph, where the root node is the whole computation graph, the leaf nodes are all the single tensors in the computation graph, and for a non-leaf node, its children is the members of its division.
With the division of 3 types of closed sets, the computation graph can be reorganized into a division tree (Figure 5) where a non-leaf node would be a closed set and its children would be its corresponding division. The root node is the whole computation graph, the largest closed set, and the leaf nodes would be single tensors in the computation graph. With division tree, we can apply divide-and-conquer to search for optimal solution.
Theorem 1. The division tree of a computation graph is unique and complete.
The uniqueness of the division tree indicates that the optimal solution of the division tree would also be the optimal solution of the whole computation graph. The completeness indicates that the division tree has included all the possible members of solution and represents the whole search space for the optimal solution. Theorem 1 is proved in the appendix.

heading: 4.3 ALGORITHM
text: We search optimal solutions for ACGs by solving several sub-problems using Algorithm 2-4 respectively. Based on these components, we present our final solver as Algorithm 5.
Algorithm 2 judges whether a vertex is a splitting vertex of a closed set. This algorithm mainly follows the Definition 3 and uses vertex set to check the property of a splitting vertex. With this algorithm, we can judge whether a closed set is type 1 and get its division if it is. Suppose there are N vertices in sij , the time complexity of Algorithm 2 is O(N2). Algorithm 2 Judge whether a vertex vt is a splitting vertex of closed set sij
1: Let {vin} be the vertices of all the vertices within [sij ] that have paths to vt. Let {vout} be the vertices of all the vertices within [sij ] that have paths from vt. 2: if {vin}∪{Vout}∪{vt} = {v|v ∈ [sij ]} and {vin}∩{Vout} = ∅ and 6 ∃v1 ∈ {vin}, v2 ∈ {vout}, v1, v2 have connections then 3: Return true 4: else 5: Return False
Algorithm 3 examines whether a closed set is branched. It uses a growing algorithm to check whether an independent subpart of this closed set can form a closed set. If a non-trivial closed set sij has an edge from vi to vj , then it’s branched because this edge itself can be treated as a closed set. Combined with Algorithm 2, we can know the type of a closed set and get its division if it’s type 2. Suppose there are N vertices in sij , the time complexity of Algorithm 3 is O(N2).
Algorithm 4 addresses the problem of finding the maximal split, the division of a closed set type 3 sij . First get all the possible closed sets within sij and use a property of maximal split to judge whether this closed set is a member of the maximal split. The property is: there cannot exist another closed set sab $ sij but contains any member of this maximal split. This property is proved in Lemma 6 of the appendix. Suppose there are N vertices in sij , the time complexity of Algorithm 4 is O(N4).
Algorithm 5 is the solver for ACGs. First, the division tree of the computation graph is built. Similar to the linear solver, a max term list is formed by the cost of all the possible closed sets for traverse. Given a max term, we propose a greedy idea: for a closed set, never expand it unless the its cost exceed the max term. In other word, if the max term doesn’t allow a leap over this closed set, we expand it, otherwise, do not expand it. Because once expanded, some cost of other vertices inside this closed set might be introduced, and the cost will never be smaller than unexpanded. If some children of the closed set type 1 are expanded, the rest reforms a few linear segments and still can be solved by the linear solver. If some children of the closed set type 2 or 3 are expanded, the other
Algorithm 3 Judge whether sij is branched 1: if sij has at least 1 vertex then 2: if sij includes an edge from vi to vj then 3: Return true 4: else 5: Initialize a vertex set s = {vk}. vk ∈ sij is a randomly chosen vertex. 6: while True do 7: For any vt ∈ sij , vt 6∈ s that has connection to any vk ∈ s, add vt to s. 8: if No more vertex can be added to s then 9: Break 10: if s = {v ∈ sij} then 11: Return false 12: else 13: Return true 14: else 15: Return false
Algorithm 4 Find the maximal split of a non-branched sij with 0 splitting vertex
1: for each vertex pair (vk, vt) except (vi, vj) in [sij ] do 2: For all the vertices {v} that have paths from vk and have paths to vt. 3: if 6 ∃v2 6∈ {v} and v2 6= vk, vt, v2 has connection to a v1 ∈ {v} then 4: Form a closed set skt with all these vertices. 5: for each formed closed set skt do 6: If there doesn’t exist a sab such that skt $ sab $ sij , put skt into the maximal split.
members remain unexpanded and need no changes. Suppose there are N vertices in computation graph, the time complexity of Algorithm 5 is O(N4). Algorithm 5 Arbitrary Computation Graph (ACG) Solver
1: Get all possible closed set and their costs. Use their costs to form the max term list. 2: Reorganize the computation graph into a division tree: from the root node (the computation
graph), build its children from its division, until all the leaf nodes are single tensors. 3: for each possible max term m in max term list {m} do 4: if current closed set is type 1 then 5: For all the children that have cost larger than current max term. Expand them and solve the next level. 6: All the expanded children have separated the current closed set to linear segments. Solve all the linear segments with current max term. 7: else 8: For all the children that have cost larger than current max term. Expand them and solve the next level. 9: All the other members remain unexpanded.
10: Summarize the total loss, save the current solution if it’s better.

heading: 5 EXPERIMENT
text: We evaluated Re-forwarding on two main groups of neural networks (1) networks with linear structures, such as Alexnet (Krizhevsky et al. (2012)) and vgg series (Simonyan & Zisserman (2014)). (2) networks with non-linear structures, such as Resnet series (He et al. (2016)), Densenet series (Huang et al. (2017)) and Inception net (Szegedy et al. (2016)). For each network in Table 1, an computation graph is built such that every vertex is a Float32 tensor, every edge is an operation, and the memory cost of a vertex is its tensor size (measured in MB). We compared Re-forwarding with Chen (Chen et al. (2016)) and the regular training approach. Note that Chen et al. (2016) only worked on linear computation graphs. To compare with (Chen et al. (2016)) on non-linear networks, we manually re-organized all the non-linear computation graphs into linear computation graphs with their splitting vertices, and fed them to Chen et al. (2016) (see Table 1 “Chen et al. (2016) manual
(MB)”). Our Re-forwarding approach directly works on arbitrary computation graphs. We have also included a customized network (“CustomNet”), on which even the manual version of Chen’s approach is not applicable. Our approach directly works on all networks. The computation graph of this network is visualized in the appendix.
All experiments were conducted in Pytorch. To remove irrelevant GPU memory cost, such as model and Pytorch CUDA interface cost, all training memory costs were measured with two different input sizes and compute the difference between two measurements. For example, to measure the memory cost of Alexnet with input size [BatchSize, Channel,Width,Height]= [16, 3, 224, 224], we first record the training memory of input [16, 3, 224, 224] as r1, and input [32, 3, 224, 224] as r2. The actual memory cost given [16, 3, 224, 224] input is measured as r2 − r1. To use existing DNN implementations, the input of Inception net is [BatchSize, 3, 300, 300], and the input of all other networks is [BatchSize, 3, 224, 224]. We also measure the training time (time of 1 training iteration) for the regular approach and our approach. Each time is measured as the average of 20 iterations. Our approach has the same training time as Chen’s approach and its manual version, see “Space Efficient Training Time” in Table 1.
Table. 1 shows that Re-forwarding cuts down huge amount of memory from the regular approach at reasonable time overheads: 26% space off and 40% time overhead for Alexnet, around 40% space off and 40% time overhead for Vgg series. For Resnet series, the deeper network, the more memory was cut down. On the deepest Resnet152, 80% space off was achieved with only 39% time overhead. For Densenet series, more than 80% space off was achieved with around 40% time overhead. Notice that, Chen et al. (2016) only works on linear networks. Its results on non-linear networks were manually synthesized. Re-forwarding directly works on non-linear networks and constantly outperformed Chen et al. (2016) and its “manual” version. This supports our claim that Re-forwarding is optimal.

heading: 6 CONCLUSION
text: Re-forwarding is a fundamental approach that explores trade-off between memory and computation power of GPUs. By saving tensors at a subset of layers during forward, and conducting extra local forwards for backward, Re-forwarding makes it possible to train very heavy DNNs with finite GPU memory. To our knowledge, our theoretical and algorithmic results are the first top-down work that achieve an optimal memory solution for arbitrary computation graphs in DNNs. Re-forwarding can be further embedded and optimized with any low-level techniques such as distributed computing, GPU/CPU swapping, computation graph optimization and liveness analysis.

heading: A PROOF

heading: A.1 LEMMAS
text: Lemma 1. If sij ∩ skt 6= ∅ and sij 6⊂ skt and skt 6⊂ sij , then sij ∩ skt = skj or sij ∩ skt = sit
Proof. Let [sij ] ∩ [skt] = s = {v, e}. Let vp be the source vertex of s, vq be the target vertex of s. If vp 6= vi and vp 6= vk and vq 6= vj and vq 6= vt, then vi, vk has path to vp and vj , vt has path from vq . Therefore, vp has at least 2 immediate parents va, vb with va ∈ [sij ], va 6∈ [skt], vb ∈ [skt], vb 6∈ [sij ]. If so, the independence of sij and skt is violated. Therefore, vp must be vi or vk.
Same on vq , vq must be vj or vt.
If vp = vi, vq = vj , then sij ⊂ skt. If vp = vk, vq = vt, then skt ⊂ sij . Therefore, vp = vi, vq = vt or vp = vk, vq = vj . Suppose vp = vk, vq = vj , let’s prove s is a closed set.
With s ⊂ skt, ∀v1 ∈ s, v1 has no edge with v2 6∈ [skt]. With s ⊂ sij , ∀v1 ∈ s, v1 has no edge with v2 6∈ [sij ]. Therefore, ∀v1 ∈ s, v1 has no edge with v2 6∈ [s]. The independence of s is guaranteed. In the discussion before, we can see the source vertex vp of s must be either vi or vk. If vi and vk are both the source vertices of s, then vi ∈ [skt] and vk ∈ [sij ], vi has path to vk and vk has path to vi, which will force vi = vk because the sij , skt is acyclic. Same on vq , s can only have 1 source vertex and 1 target vertex. Therefore, s is closed set.
Therefore, sij ∩ skt = skj or sij ∩ skt = sit.
Lemma 2. The intersection of two closets s = si ∩ sj 6= ∅ is also a closet
Proof. Given the independence of si and sj , the independence of s is obvious. The remaining thing is whether s only has 1 source vertex and 1 target vertex. In the proof of Lemma 1, we can see any source or target vertex of s will eventually become source or target vertex of si and sj . With simple discussion, we can have this lemma.
Lemma 3. If sij ∩ skt = skj 6= ∅, then vk is the splitting vertex of sij and vj is the splitting vertex of skt
Proof. Let’s first prove that vk is the splitting vertex of sij .
Let s = sij − [skj). Obviously, sij = s∪ skj ∪ {vk} and s∩ skj = ∅. We only need to prove that s is closed set. For convenience, let’s denote [s] = s ∪ {vi, vk} vi is obviously the only source vertex of [s] because vi is source vertex of [sij ]. We discuss the target vertex here. If vk is not the target vertex of [s], as vk ∈ [s], vk must have path to the target vertex v of [s] and v also has path to vj as v ∈ sij . Because v /∈ [skj ], in the path from v to vj , there exists an edge that connects a vertex v1 ∈ s with a vertex v2 ∈ skt which violates the independence of skt. Therefore, the target vertex of [s] can only be vk.
As s ⊂ [sij), ∀v1 ∈ s, v1 has no edge with v2 6∈ [sij). As skj is close, ∀v1 ∈ s, v1 has no edge with v2 ∈ skj . ∀v1 ∈ s, v1 can only have edge with v2 ∈ [s]. Thus the independence of s is guaranteed. Therefore, s is closed set, vk is the splitting vertex of sij .
Same on vj , vj is the splitting vertex of skt
Lemma 4. If sij has n splitting vertices {v1, v2, ..., vn}, then sij = si1 ∪ s12 ∪ ... ∪ snj ∪ {v1, v2, ..., vn}
Proof. If n = 2, the splitting vertices are v1, v2, sij = si1 ∪ s1j ∪ {v1} = si2 ∪ s2j ∪ {v2}. Let v1 ∈ si2, v1 6= v2, then s1j ∩ si2 = s12 6= ∅. According to Lemma 3, v1 is splitting vertex of si2 and v2 is splitting vertex of s1j . Therefore, sij = si1 ∪ s12 ∪ s2j ∪ {v1, v2}. For n > 2, the lemma can be proved by repetitively using the conclusion in n = 2.
Lemma 5. If the non-branched sij has a maximal split {[spq]}, and |{[spq]}| > 2, denote {v} as all the endpoint vertices of [s] ∈ {[spq]}. Then ∀v ∈ {v}, v 6= vi, vj , v is the endpoint vertex of at least 3 members of the maximal split.
Proof. If vb is the endpoint vertex of only 2 members of the maximal split, suppose the 2 members are sab and sbc. If so, sab and sbc can be merged into sac. If sac 6= sij , this violates the definition of maximal split. Otherwise, it violates the condition that sij is non-branched and |{[spq]}| > 2. It is impossible that the 2 members are sab and scb because in this way vb has no path to vj and violates the definition of closed set. If vb is the endpoint vertex of only 1 member of the maximal split, then vb must be either vi or vj . Therefore, this lemma is proved.
Lemma 6. Any member of a maximal split can not be the subset of another closed set s $ sij .
Proof. Suppose the source vertex of s is v1 and target vertex is v2, a member sxy of the maximal split is inside s.
Suppose a member sab of the maximal split has its source vertex va inside s and target vertex vb outside s. Then the boundary vertex (the vertex that has edges to the non-overlapping parts of both sets) must be v2, otherwise the independence of s will be violated. Notice that v2 is inside sab and the independence of sab needs to be guaranteed, for ∀vp ∈ s, vp /∈ s ∩ sab, vq ∈ s ∩ sab, vp has no edge with vq . Therefore, va is a splitting vertex of s.
Similarly, if sba has its target vertex va inside s and source vertex vb outside s, the boundary vertex must be v1 and va is a splitting vertex of s.
For the closed set s, from the discussion above, we know that there are at most 2 members of the maximal split that can overlap with s. Other members must be either completely inside s or completely outside s. Let’s discuss the number of members that overlaps with s.
If there are 0 member that overlaps with s, s is the union of a subset of members of the maximal split, which violates the definition of maximal split.
If there is 1 member that overlaps with s, suppose the corresponding splitting vertex is vb, and the boundary vertex is actually v2. Then s1b is a closed set containing sxy and corresponds to the situation of 0 member overlapping. s1b is the union of a subset of members of the maximal split, and violates the definition of maximal split.
If there are 2 members that overlaps with s, suppose they generate two different splitting vertex va and vb. Then sab is a closed set containing sxy and corresponds to the situation of 0 member overlapping. sab is the union of a subset of members of the maximal split, and violates the definition of maximal split.
If they generate the same splitting vertex vb, from lemma 5, vb is also the endpoint vertex of at least 1 other member sab which has to be inside s. Suppose the two overlapping members are scb that contains v1, and sbd that contains v2. As the source vertex of s, v1 has path to vb and v1 has path to va, which implies vb has path to va. As the target vertex of s, v2 has path from vb and v2 has path from va, which implies vb has path from va. This conflicts with the fact that s is acyclic. Therefore, this case is not possible.
Therefore, this lemma is proved.
Lemma 7. If non-branched sij has at least 1 vertex but has 0 splitting vertex, then its maximal split has length > 2
Proof. As sij is not branched, the members of its maximal split cannot have the starting vertex as vi and the ending vertex as vj at the same time. If sij has at least 1 vertex, and its maximal split has length 2, then its maximal split must be {[sik], [skj ]}, and vk will be the splitting vertex of sij , which violates that sij has no splitting vertex.
If sij has at least 1 vertex without splitting vertex, it has at least 2 edges and cannot have a trivial length 1 maximal split. Therefore, its maximal split has length > 2

heading: A.2 UNIQUENESS OF DIVISION TREE
text: To prove this uniqueness, we simply discuss the division uniqueness of closed set type 1, 2 and 3.

heading: A.2.1 UNIQUENESS OF DIVISION OF CLOSED SET TYPE 1
text: Proof. By the definition of this division and Lemma 4, the uniqueness of the division is equivalent to the uniqueness of the splitting vertex set of a closed set type 1. The splitting vertex set is obviously unique.

heading: A.2.2 UNIQUENESS OF DIVISION OF CLOSED SET TYPE 2
text: Proof. If there exists another division, there must be a branch member s1ij in division 1 and a branch member s2ij in division 2, where s 1 ij ∩ s2ij 6= ∅ and s1ij 6= s2ij .
Denote s = s1ij ∩ s2ij . By Lemma 1 and 2, s = s3ij is also a closed set. As s1ij and s2ij cannot be divided into more branches, s = s1ij = s 2 ij . Therefore, the division of closed set type 2 is unique.

heading: A.2.3 UNIQUENESS OF DIVISION OF CLOSED SET TYPE 3
text: Proof. As the closed set in the division tree has at least 1 vertex, with Lemma 7, we know that the division, i.e. maximal split of a closed set type 3 sij within the division tree will have length > 2. Denote this maximal split as {[spq]}, we only need to prove this maximal split is unique. Suppose there is a another different maximal split {[s′pq]}, let us only check the difference between {[spq]} and {[s′pq]}. Denote {[skt]} and {[s′kt]} with {[spq]} − {[skt]} = {[s′pq]} − {[s′kt]} and 6 ∃s ∈ {[skt]}, s′ ∈ {[s′kt]}, s = s′. As {[spq]} − {[skt]} = {[s′pq]} − {[s′kt]}, we have ∪{[skt]} = ∪{[s′kt]} Obviously, |{[skt]}| ≥ 2 and |{[s′kt]}| ≥ 2. Denote {v} as all the endpoint vertices of [s] ∈ {[skt]}, and {v′} for {[s′kt]}. Obviously {v} 6= ∅ and {v′} 6= ∅. As sij is non-branched, {v} ∪ {vi, vj} − {vi, vj} 6= ∅ and {v′} ∪ {vi, vj} − {vi, vj} 6= ∅. Suppose sab, sbc ∈ {[skt]}, according to Lemma 5, there’s at least 1 other member that has vb as endpoint vertex. Suppose the other endpoint of this member is vd. Let’s discuss whether vb ∈ {v′} and whether vd ∈ ∪{[skt]}. If vd 6∈ ∪{[skt]}, then vb must occur in {v′}. Otherwise, vb would be inside a closed set which would be violated by vd. Given vb ∈ {v′}, as sab 6∈ {[s′kt]}, suppose seb ∈ {[s′kt]} and sab ∩ seb 6= ∅. If va ∈ seb, from Lemma 1, seb cannot be close. If ve ∈ sab, from Lemma 5, sab cannot be close. In this case, there cannot exist another different maximal split.
If vd ∈ ∪{[skt]}, then sbd ∈ {[skt]}. If vb ∈ {v′}, we can use the same logic above to show this is impossible. Therefore, vb 6∈ {v′} and sbd is included by a closed set s. From Lemma 6, this is impossible. In this case, there cannot exist another different maximal split.
In all the cases, there cannot exist another different maximal split. Therefore, the maximal split is unique.

heading: A.3 COMPLETENESS OF DIVISION TREE
text: Similar with the uniqueness, the completeness of division tree is equivalent to the completeness of the division of a closed set. To prove this completeness, we simply discuss the division completeness of closed set type 1, 2 and 3.
An equivalent statement of the division completeness is: there doesn’t exist a closed set whose head is in one member of the division and whose tail is in another member of the division.

heading: A.3.1 COMPLETENESS OF DIVISION OF CLOSED SET TYPE 1
text: Proof. Suppose there exists a closed set s whose head vp is in one member s1 and whose tail vq is in another member s2.
If vp is not an endpoint of s1, then according to Lemma 3, vp is also a splitting vertex in s1 and can break s1 into smaller segments, which makes vp also the splitting vertex of the whole closed set. However, vp is not the splitting vertex of the whole closed set sij . This also applies to vq . Therefore, the division of closed set type 1 is complete.

heading: A.3.2 COMPLETENESS OF DIVISION OF CLOSED SET TYPE 2
text: Proof. Suppose there exists a closed set s whose head vp is in one branch s1ij and whose tail vq is in another branch s2ij . As s crosses s 1 ij and s 2 ij , there exists a boundary vertex v in s, which belongs to [s1ij ] and has direct connection with a vertex outside [s 1 ij ]. If v is not vi or vj , it will violate the independence of sij . If v = vi, as vi is the head of both s1ij and s 2 ij , it cannot be the boundary vertex, same when v = vj . Therefore, there cannot exist such a closed set s. The division of closed set type 2 is complete.

heading: A.3.3 COMPLETENESS OF DIVISION OF CLOSED SET TYPE 3
text: Proof. Suppose there exists a closed set s whose head vp is in one member s1 and whose tail vq is in another member s2. Same with closed set type 2, the boundary vertex v has to be the endpoint vertex of s1 or the independence of s1 will be violated. According to Lemma 5, v is the endpoint vertex of at least 3 members, meaning that v will at least have 1 connection with another closed set s3. To maintain the independence of s, s has to include s3 as well. However, s3 also has its endpoints. This will propagate until s becomes the whole closed set. Therefore, there cannot exist such a closed set s. The division of closed set type 3 is complete.

heading: B COMPLEXITY ANALYSIS

heading: B.1 ALGORITHM 1
text: Suppose there are N vertices in the computation graph. There are O(N2) vertex pairs. For each vertex pair, the time cost is mainly on constructing accessibility graph and finding the shortest path. Denote the source vertex of the whole computation graph as v0. To construct an accessibility graph, first we traverse the linear computation graph, record the accumulated sum l(v0, vi) for each vertex vi, and form a table of l(vi, vj) = l(v0, vj)− l(v0, vi)− l(vi). These steps will cost O(N2). Then we traverse each (vi, vj) pair to form the edges of the accessibility graph, which also cost O(N2). Solving the shortest path problem in accessibility graph will also cost O(N2) as the accessibility graph has N vertices. Therefore, the overall time complexity of Algorithm 1 would be O(N4).
The space complexity would be O(N2) for the table of l(vi, vj) and the accessibility graph itself.

heading: B.2 ALGORITHM 2
text: Suppose there are N vertices in the closed set sij . In step 1, getting {vin} and {vout} will cost O(N) time for traversing the ancestors and descendents of vt. In our implementation, an array a of length N is used to represent {vin} and {vout}: ai = 1 indicates vi ∈ {vin}, ai = 2 indicates vi ∈ {vout} and ai = 0 indicates vi /∈ {vin} ∪ {vout}. Then the union check and intersection check in step 2 can be done in O(N). The connection check in step 2 traverses the edges and costs O(N2). Other steps are O(1). Therefore, the overall time complexity of Algorithm 2 would be O(N2).
The space complexity would be O(N) for the array to represent {vin} and {vout}.

heading: B.3 ALGORITHM 3
text: Suppose there are N vertices in the closed set sij . The most time consuming part will be from step 5 to step 13. Other steps are O(1). In step 5 to step 13, every edge between two vertices in sij is at most visited once and there are O(N2) edges. Therefore, the overall time complexity of Algorithm 3 would be O(N2).
In our implementation, an array of length N is used to represent the vertex set s = {vk}. Therefore, the space complexity would be O(N).

heading: B.4 ALGORITHM 4
text: Suppose there are N vertices in the closed set sij and there are O(N2) vertex pairs. For each vertex pair, the connection check in step 2-4 will cost O(N2), similar to the connection check in Algorithm 2. Thus step 1-4 will cost O(N4). In our implementation, for each vertex in the closed set sij , we select the largest formed closed set skt that contains this vertex. The closed set number is then reduced to O(N) and step 5-6 can be done in O(N3). Therefore, the overall time complexity of Algorithm 4 would be O(N4)
As O(N2) closed sets can be formed in step 1-4 and each closed set is a smaller DAG with O(N) vertices and cost O(N2) space, the space complexity would be O(N4) for all these closed sets.

heading: B.5 ALGORITHM 5
text: Step 1 is similar to step 1-4 in Algorithm 4 with sij being the whole computation graph. Therefore, the overall time complexity for step 1 is O(N4).
In step 2, the complexity of building division tree is related to the complexity of getting the division of a closed set. For closed set type 1, Algorithm 2 is called for each vertex to get all splitting vertices. Thus getting the division of closed set type 1 cost O(N3) time. For closed set type 2, Algorithm 3 is used to solve for its division and costs O(N2) time. For type 3, Algorithm 4 is called to solve for its division. Notice that we have already stored all possible closed sets in step 1, step 1-4 in Algorithm 4 can be skipped and thus the time complexity of getting the division of closed set type 3 is reduced to O(N3). Therefore, getting the division of an arbitrary closed set costs O(N3) time. In depth i of the division tree, suppose there are k closed sets, and the number of vertices of jth closed sets is aj . To build depth i+ 1 of the division tree, we need to get the division of all these closed sets, which will cost ∑ j O(a 3 j ). As ∑ j aj ≤ N , we have ∑ j O(a 3 j ) ≤ O(N3). As the depth of division tree is at most N , the overall time complexity of step 2 would be O(N4).
For step 3-10, if the computation graph is linear, the ACG solver will reduce to LCG solver and has complexity O(N4). If the computation graph is non-linear, the length of {m} would be O(N2) for there are O(N2) vertex pair. For a max term m, from step 4-10, the actual time costing part will be step 6 which calls the LCG solver, and other steps would be O(1). Suppose the LCG solver is called k times, solving problems of a1, a2, ..., ak vertices. The total complexity of this would be O(a41) +O(a 4 2) + ...+O(a 4 k). Notice that a1 + a2 + ...+ ak ≤ N for the fact that any vertex in the computation graph would not be solved twice by LCG solver, we have a41 + a 4 2 + ... + a 4 k ≤ N4. Therefore the time complexity of step 3-10 is O(N4).
Step 1 would cost O(N4) space to store all the possible closed sets. Step 2 would cost O(N2) space for the division tree. Step 3-10 would cost O(N2) space for calling LCG solver.
In conclusion, the overall time complexity of Algorithm 5 is O(N4) and the overall space complexity of Algorithm 5 is O(N4).

heading: C RUNTIME AND THEORETICAL ANALYSIS
text: The number of vertices in the computation graph and the runtime of ACG Solver (Algorithm 5) for each network are listed in Table 2. All the runtimes were measured on a single core of CPU i7-8700.
Notice that the runtime is measured on only 1 cpu core, it can be massively reduced by parallelization on multiple cpu cores. The runtime can also be further reduced through a better implementation as our implementation is a prototype.
Although it might be concerning that the runtime is too much for some deep networks, it is still relatively small compared to training processes which might cost days or even weeks. More importantly, solving the optimal solution for a network is an one-time effort. The optimal solutions for all popular networks will be released online for people to use without taking the time to run ACG solver.
To see how well the reality matches with the theory, we also compare the measured memory cut off and theoretical memory cut off (given by Algorithm 5) in Table 2. Observe that all the measured memory cut off are slightly lower than theoretical memory cut off. This is because, in implementation, we assume that the whole input tensors of each operation are always stored for backward. In reality, some operations only need to store small tensors for backward. For example, batchnormalization only needs a few statistics for backward and doesn’t need the whole input tensor.
D VISUALIZATION
We visualize the computation graph of Alexnet, vgg11, vgg13, vgg16 ,vgg19 and CustomNet and the solution of our approach (in green) and the solution of Chen’s approach (in red). In the computation graphs, the cost of each vertex and the actual operation of each edge are also marked. The cost of each vertex is the size of this tensor during forward given the input as [1, 3, 224, 224] ([1, 3, 300, 300] for inception v3). For example, in Alexnet, the input is [1, 3, 224, 224] and thus the source vertex has the cost 150528 = 1 × 3 × 224 × 224. After 2D convolution and relu, the tensor becomes [1, 64, 55, 55] and thus the second vertex has the cost 193600 = 1×64×55×55.

Review summaries:
The paper suggests a method to reducing the space consumption of training neural nets, in exchange for additional training time. The method stores in memory only a subset of the intermediate tensors computed in the forward step, and then in the backward step it re-computes the missing tensors as they are needed by interpolating forward (again) between the stored tensors. The paper also gives a combinatorial algorithm for choosing which tensors to store on a given computation DAG annotated with vertex costs.