We propose to execute deep neural networks (DNNs) with dynamic and sparse graph (DSG) structure for compressive memory and accelerative execution during both training and inference. The great success of DNNs motivates the pursuing of lightweight models for the deployment onto embedded devices. However, most of the previous studies optimize for inference while neglect training or even complicate it. Training is far more intractable, since (i) the neurons dominate the memory cost rather than the weights in inference; (ii) the dynamic activation makes previous sparse acceleration via one-off optimization on fixed weight invalid; (iii) batch normalization (BN) is critical for maintaining accuracy while its activation reorganization damages the sparsity. To address these issues, DSG activates only a small amount of neurons with high selectivity at each iteration via a dimensionreduction search and obtains the BN compatibility via a double-mask selection. Experiments show significant memory saving (1.7-4.5x) and operation reduction (2.3-4.4x) with little accuracy loss on various benchmarks. Deep Neural Networks (DNNs) BID23 have been achieving impressive progress in a wide spectrum of domains (Simonyan & Zisserman, 2014; BID0 Redmon & Farhadi, 2016; , while the models are extremely memory-and compute-intensive. The high representational and computational costs motivate many researchers to investigate approaches on improving the execution performance, including matrix or tensor decomposition BID44 Novikov et al., 2015; Garipov et al., 2016; BID47 BID3 , data quantization (Courbariaux et al., 2016; BID51 BID27 BID24 BID39 BID33 , and network pruning BID4 BID8 a; BID30 BID13 Molchanov et al., 2016; BID13 Spring & Shrivastava, 2017; BID28 BID49 BID12 Chin et al., 2018; BID31 BID14 . However, most of the previous work aim at inference while the challenges for reducing the representational and computational costs of training are not well-studied. Although some works demonstrate acceleration in the distributed training BID29 BID6 BID47 , we target at the single-node optimization, and our method can also boost training in a distributed fashion. DNN training, which demands much more hardware resources in terms of both memory capacity and computation volume, is far more challenging than inference. Firstly, activation data in training will be stored for backpropagation, significantly increasing the memory consumption. Secondly, training iteratively updates model parameters using mini-batched stochastic gradient descent. We almost always expect larger mini-batches for higher throughput FIG0 ), faster convergence, and better accuracy (Smith et al., 2017) . However, memory capacity is often the limitation factor FIG0 Upper and lower one are the feature maps before and after BN, respectively. However, using BN damages the sparsity through information fusion; (f) There exists such great representational redundancy that more than 80% of activations are close to zero.that may cause performance degradation or even make large models with deep structures or targeting high-resolution vision tasks hard to train BID42 .It is difficult to apply existing sparsity techniques towards inference phase to training phase because of the following reasons: 1) Prior arts mainly compress the pre-trained and fixed weight parameters to reduce the off-chip memory access in inference BID9 , while instead, the dynamic neuronal activations turn out to be the crucial bottleneck in training BID17 , making the prior inference-oriented methods inefficient. Besides , during training we need to stash a vast batched activation space for the backward gradient calculation. Therefore , neuron activations creates a new memory bottleneck (Figure 1(c) ). In this paper, we will sparsify the neuron activations for training compression.2) The existing inference accelerations usually add extra optimization problems onto the critical path Molchanov et al., 2016; BID30 BID27 BID49 BID31 , i.e., 'complicated training ⇒ simplified inference', which embarrassingly complicates the training phase. 3) Moreover , previous studies reveal that batch normalization (BN) is crucial for improving accuracy and robustness FIG0 ) through activation fusion across different samples within one mini-batch for better representation (Morcos et al., 2018; BID16 . BN almost becomes a standard training configuration; however, inference-oriented methods seldom discuss BN and treat BN parameters as scaling and shift factors in the forward pass. We further find that BN will damage the sparsity due to the activation reorganization FIG0 ). Since this work targets both training and inference, the BN compatibility problem should be addressed.From the view of information representation, the activation of each neuron reflects its selectivity to the current stimulus sample (Morcos et al., 2018) , and this selectivity dataflow propagates layer by layer forming different representation levels. Fortunately , there is much representational redundancy, for example, lots of neuron activations for each stimulus sample are so small and can be removed FIG0 ). Motivated by above comprehensive analysis regarding memory and compute, we propose to search critical neurons for constructing a sparse graph at every iteration. By activating only a small amount of neurons with a high selectivity, we can significantly save memory and simplify computation with tolerable accuracy degradation. Because the neuron response dynamically changes under different stimulus samples, the sparse graph is variable. The neuronaware dynamic and sparse graph (DSG) is fundamentally distinct from the static one in previous work on permanent weight pruning since we never prune the graph but activate part of them each time. Therefore, we maintain the model expressive power as much as possible. A graph selection method , dimension-reduction search, is designed for both compressible activations with elementwise unstructured sparsity and accelerative vector-matrix multiplication (VMM) with vector-wise structured sparsity. Through double-mask selection design, it is also compatible with BN. We can use the same selection pattern and extend our method to inference. In a nutshell, we propose a compressible and accelerative DSG approach supported by dimension-reduction search and doublemask selection. It can achieve 1.7-4.5x memory compression and 2.3-4.4x computation reduction with minimal accuracy loss. This work simultaneously pioneers the approach towards efficient online training and offline inference, which can benefit the deep learning in both the cloud and the edge. In this work, we propose DSG (dynamic and sparse graph) structure for efficient DNN training and inference through a dimension-reduction search based sparsity forecast for compressive memory and accelerative execution and a double-mask selection for BN compatibility without sacrificing model's expressive power. It can be easily extended to the inference by using the same selection pattern after training. Our experiments over various benchmarks demonstrate significant memory saving (up to 4.5x for training and 1.7x for inference) and computation reduction (up to 2.3x for training and 4.4x for inference). Through significantly boosting both forward and backward passes in training, as well as in inference, DSG promises efficient deep learning in both the cloud and edge. DISPLAYFORM0 Further recalling the norm preservation in equation (3) of the main text: there exist a linear map f : R d ⇒ R k and a 0 ∈ (0, 1), for 0 < ≤ 0 we have DISPLAYFORM1 Substituting the equation FORMULA0 into equation FORMULA0 yields DISPLAYFORM2 Combining equation FORMULA0 and FORMULA0 , finally we have DISPLAYFORM3 It can be seen that, for any given X i and W j pair, the inner product can be preserved if the is sufficiently small. Actually, previous work BID1 BID5 BID36 discussed a lot on the random projection for various big data applications, here we re-organize these supporting materials to form a systematic proof. We hope this could help readers to follow this paper. In practical experiments, there exists a trade-off between the dimension reduction degree and the recognition accuracy. Smaller usually brings more accurate inner product estimation and better recognition accuracy while at the cost of higher computational complexity with larger k, and vice versa. Because the X i 2 and W j 2 are not strictly bounded, the approximation may suffer from some noises. Anyway, from the abundant experiments in this work, the effectiveness of our approach for training dynamic and sparse neural networks has been validated.
We construct dynamic sparse graph via dimension-reduction search to reduce compute and memory cost in both DNN training and inference. The authors propose to use dynamic sparse computation graph for reducing the computation memory and time cost in deep neural network (DNN). This paper proposes a method to speed up training and inference of deep neural networks using dynamic pruning of the compute graph.