--- title: "Fully Nested Neural Network for Adaptive Compression and Quantization" authors: - "Yufei Cui" - "Ziquan Liu" - "Wuguannan Yao" - "Qiao Li" - "Antoni B. Chan" - "Tei-wei Kuo" - "Chun Jason Xue" doi: "10.24963/ijcai.2020/288" url: "https://ijcai.org/proceedings/2020/288" pdf: "https://ijcai.org/proceedings/2020/0288.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "2080-2087" track: "Main track" keywords: - "Machine Learning: Deep Learning" - "Machine Learning: Deep Learning: Convolutional networks" --- # Fully Nested Neural Network for Adaptive Compression and Quantization Yufei Cui, Ziquan Liu, Wuguannan Yao, Qiao Li, Antoni B. Chan, Tei-wei Kuo, Chun Jason Xue *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 2080-2087. DOI: [10.24963/ijcai.2020/288](https://doi.org/10.24963/ijcai.2020/288) ## Abstract Neural network compression and quantization are important tasks for fitting state-of-the-art models into the computational, memory and power constraints of mobile devices and embedded hardware. Recent approaches to model compression/quantization are based on reinforcement learning or search methods to quantize the neural network for a specific hardware platform. However, these methods require multiple runs to compress/quantize the same base neural network to different hardware setups. In this work, we propose a fully nested neural network (FN3) that runs only once to build a nested set of compressed/quantized models, which is optimal for different resource constraints. Specifically, we exploit the additive characteristic in different levels of building blocks in neural network and propose an ordered dropout (ODO) operation that ranks the building blocks. Given a trained FN3, a fast heuristic search algorithm is run offline to find the optimal removal of components to maximize the accuracy under different constraints. Compared with the related works on adaptive neural network designed only for channels or bits, the proposed approach is applicable to different levels of building blocks (bits, neurons, channels, residual paths and layers). Empirical results validate strong practical performance of proposed approach. ## Full text ## 1 Introduction Deep neural networks have achieved great success in various domains, e.g., computer vision, natural language processing and etc [LeCun et al., 2015]. To fit the computation/memory-intensive neural network into mobile devices and embedded hardware, researchers either develop light-weight network architecture [Sandler et al., 2018; Zhang et al., 2018] or compress a pre-trained network through pruning [Han et al., 2016; Neklyudov et al., 2017]. To avoid the huge efforts on tuning hyper-parameter, network architecture search (NAS) is studied to automatically discover the best architecture with computation, memory or power constraints [Cai et al., 2018; Jiang et al., 2019]. Another method to fit the neural network into resource-limited devices is quantization, which quantizes full-precision weights into a small number of bits [Zhou et al., 2016; Yang et al., 2019]. As the optimal bitwidths for different layers might vary, reinforcement learning based automatic search methods are developed to find the optimal bit-width setups [Wang et al., 2019]. The search-based methods alleviate the need to manually tune hyper-parameter in designing network architectures and to determine bit-width in quantization. However, the algorithms should be re-run once the resource budget (CPU clock rate, number of cores, size of RAM, etc.) changes. Recently, there is a rising attention on training one neural network that is adaptive to different resource budgets. These methods are particularly designed for either adaptive channel numbers [Yu et al., 2019b] or adaptive quantization bits [Jin et al., 2019]. As changing the channel numbers or bit widths leads to inconsistent batch normalization (BN) statistics, heuristics like maintaining multiple sets of switchable BN parameters are used, which leads to a quadratic number of BN parameters w.r.t. the number of channels/bits to be updated. [Yu and Huang, 2019] propose to solve this problem by re-collecting BN statistics after training, but the flexibility of the network is still limited (see Sec. 4). The goal of this work is to provide a simple method to train a neural network once and yield optimal sub-networks (SN) for different budgets of resources. The SNs are nested in the sense that any smaller SN forms the basis of a larger one. In other words, whenever some building blocks are removed from a larger SN, the smaller SN comprising the remaining blocks is still complete and accurate. Moreover, the method is unified in that it can be applied to different levels of the network: layers, residual paths, channels, neurons and bits. Our intuition of how to achieve the goal is from the classic boosting techniques [Zhou, 2012; Chen and Guestrin, 2016], where a strong classifier is formed by an expansion of weak classifiers. The weak classifiers are ordered such that the latter classifier approximates error between ground-truth and the prior classifier. From this perspective, boosting is nested in nature as a smaller expansion of classifier forms the basis of a larger one. In a well trained boosting model, removing the latter classifier does not affect the performance much. Thus, we exploit the similarity between several building blocks of a network and the weak classifier in boosting. We further extend this inspiration to quantization bits by constructing nested quantization functions. To rank the building blocks efficiently, we propose an ordered dropout (ODO) operation that samples a nested subnetwork in each mini-batch during training. In contrast to standard dropout that acts on one block, ODO is applied to a sequence of building blocks to make them in order of importance. The intuition of ODO is to mimic the case that, during testing, an arbitrary number of blocks can be removed according to the resource budget. Mathematically, we show that, in expectation, each block maximizes a term of incremental information gain, thus the whole network is fully nested, which we call a fully nested neural network (FN3 ). Note that boosting uses a greedy method to pick the next classifier, and does not update the previous classifiers. In contrast, ODO learns the whole set of nested classifiers simultaneously. During the inference stage, to find the optimal curve of accuracy w.r.t. the number of blocks, we further propose a heuristic search algorithm, which leverages the order of blocks to reduce the search complexity fromO(2N ) to O(N), where N is the number of blocks (see Sec. 3). The experimental results show that FN3 -channel outperforms previous adaptive-channel methods, while FN3 provides more sub-networks and consumes less training time. FN3 -bit also outperforms the adaptive-bit methods. We also show the performance of FN3 on residual paths, for learning an adaptive architecture. An ablation study is conducted to show the effectiveness of the heuristic search algorithm. ## 2 Fully Nested Neural Network The aim of this section is to find the basic building block of a nested neural network and a corresponding training scheme, such that during testing time, a certain number of blocks can be removed according to the resource budget, while maintaining high accuracy without re-training or fine-tuning. Our inspiration comes from the family of boosting techniques, where x is the input data, a classifier fM(x) is composed with a sequence of basis functions bm = b(x; γm),m ∈ {1, . . . ,M}, and γm is the parameter of the m-th basis function. The basis function expansions are combined to produce the final prediction, fM(x) = ∑m βmb(x; γm). Typically, these models are fit by minimizing this goal, min{βm,γm}M1 Ex,y∼px,y L(y, ∑Mm=1 βmb(x; γm)). The additive characteristic of boosting allows us to remove some basis functions, while the remaining part of model still produce useful results. Another characteristic of boosting [Hastie et al., 2009] is that each basis function bm approximates the residual under the current model, i.e., the difference between the groundtruth and the current prediction. For example, for squarederror loss, the m-th term βmb(xi; γm) best fits the residual error rim = yi - fm-1(xi) incurred by the previous expansion. Therefore, each bm contributes less as m goes from 1 to M. The residual characteristic of boosting allows us to rank the basis functions according to the importance such that the less significant basis functions can be removed first. Once the additive basis functions are obtained and made to approximate the residual error, we can stack groups of basis functions to a deep model for better performance. Figure 1: The additive building blocks of a NN with ODO, where b1 . . . b4 indicate the blocks. Network-level: (A.1) the output of a residual network as a sum of sub-networks, gi is a layer; (A.2) unraveled view of the residual network, where bm is composed of a sequence of gi. Layer-level: (B.1) the output of a dense layer as a weighted sum of inputs; (B.2) a pixel in a feature map as a weighted sum of input channels; (B.3) a layer output as a sum of parallel residual blocks in ResNeXt. Bit-level: (C) quantization values as a sum of weighted bits. The dotted lines indicate dropped blocks (in this case the sampled index is c = 2) in one iteration. The solid lines indicate the remained blocks. ![Image](https://ijcai.org/proceedings/2020/fulltext/288/image_000000_47e7d0227e8746cc23ef81ca7d9e4207b1aee5df1d2df25e2f80f3c381b82cf8.png) ## 2.1 Building Blocks Many parameterized building blocks 1 in a convolutional neural network (CNN) possess the additive characteristic (see Fig. 1). They can be classified into several categories: Network-level: [Veit et al., 2016] shows that a CNN with residual connections behaves like the ensemble of shallow networks. As seen in Fig. 1(A.1, A.2), the network output can be seen as the summation of O(2n ) paths, fM(x) = ∑Mm=1 bm(x), M = 2n , where each path is a combination of blocks from the set of n residual blocks, i.e., bm(x) = gIn(m) n (. . . gI0(m) 0 (x)) and In(m) is the indicator function. We denote FN3 with such block as FN3 -layer. 1 In this paper, we use "blocks" and "basis functions" interchangeably. Layer-level: 1) In a dense layer, as shown in Fig. 1(B.1), hl = f(hl-1, Γ) = ΓT hl-1, where hl is the l-th layer activation and Γ is the weight matrix. The i-th dimension of output can be written as the weighted sum of input, i.e., hl,i = ΓTi hl-1. 2) In a convolutional layer, as shown in Fig. 1(B.2), every pixel on an output feature map can be written as the weighted sum of input channels, where the weights are from the channels of a convolutional filter. 3) In a residual block of ResNeXt, the output of a block can be written as sum of different paths, as shown in Fig. 1(B.3). We denote FN3 with such blocks as FN3 -neuron/-channel/-path respectively. Bit-level: An extreme case is to consider a quantization bit as a building block, as shown in Fig. 1(C). As directly training with integer weights is difficult, we instead use a nested quantization function ¯ S(·) which maps the full-precision weight w to ¯w. To construct ¯ S(·), we use the summation of several scaled and transformed Heaviside step functions, i.e., ¯w = ¯ S(wi) = ∑j αjS(wi - zj). Thus, the quantization function possesses the additive characteristic. We denote FN3 with such block as FN3 -bit. ## 2.2 Ordered Dropout Next we provide a unified method to rank the building blocks such that the blocks are nested. A naive approach is to imitate boosting: 1) train a few blocks as the base model; 2) fix the parameters of the base model, add new blocks to the model and train the new blocks; 3) repeat the second step until the total size of model meets the need. However, as the number of blocks varies among different layers, it is not obvious how to determine the number of augmented blocks (granularity) for different layers. Furthermore, the model would lack of flexibility if the granularity is large (e.g., slimmable NN [Yu et al., 2019b]), while it would cause prohibitively long training time if the number is too small. Finally, since the previous blocks are fixed in each step, this naive training method would be not end-to-end trained, which could limit its accuracy. We propose an operation named Ordered DropOut (ODO) that randomly selects nested sub-networks during training batches, which encourages ordering of the importance of each block. We label each block in a group with an index. ODO then samples a block index from a probabilistic distribution and drops all the blocks with indices greater than the chosen block. Specifically, a Categorical distribution C(m) is assigned over index m ∈ {1, . . . ,M} of the blocks bm. During training, we sample the index c ∼ C(m) then disable the blocks with index m > c. The expansion with blocks dropped is written as fc(x) = ∑ci=1 βib(x; γi), dubbed as partial expansion. The parameter of C(m) is set to be uniform, i.e., p(m) = 1M . As the m-th block is kept only when the sampled index ≤ m, the probability of keeping m-th block is βm = M+1-m M . Since βm is a monotonically decreasing function of m, then the blocks are forced to be ordered. During testing, to make the output of a block equal to the expected output at training time, the output is also scaled by βm. So the basis function expansion for a test data x is written M+1-m The intuition of ordered dropout is to mimic the scenario that an arbitrary number of building blocks (bits, neurons, filters, paths, residual blocks etc.) can be removed during testing time. As the blocks with smaller indices are more likely to be kept, they obtain more information compared to higher-index blocks and thus become more important. Furthermore, as the higher-index blocks are disabled frequently, then the small-index blocks must be able to perform the task themselves. The problem of granularity is solved because the granularity is always as small as 1 block, while it does not increase the time/resource consumption. Fig. 1 shows how ODO can be applied to different blocks. The idea of making dropout unit to have order was also explored by [Rippel et al., 2014]. A "nested dropout" was applied to the hidden representation in an auto-encoder for unsupervised learning. The operation was proven to recover PCA under particular constraints. By contrast, we apply the ODO on building blocks of convolutional neural network for supervised learning, with the goal of adaptive deployment of neural network. We also prove that a NN trained with ODO and the MLE objective will lead to each block maximizing an incremental information gain over the previous blocks, yielding residual additive blocks (see next section). ## 2.3 Ordered Information Next, we show that in a one-layer NN for a supervised learning task, training with ODO using the MLE objective leads to disentangled information gain between blocks. We denote the ground truth joint likelihood as x, y ∼ px,y and the discriminative model as pΘ(y|x) = p0(y|fM,Θ(x)), where x ∈ RD , y ∈ R. Assume p0 is probability of ground truth conditioned on the prediction. We define the prediction ˆ y = fM,Θ(x) = vT z = vT σ(UT x), where z is the hidden activation of a neural network and U ∈ RD×M , v ∈ RM are the parameters of the network. The full expansion can be written as ˆ y = fM,Θ(x) = ∑Mi=1 viσ(UTi x), where Ui denotes the i-th column of matrix U. Proposition 1. Under the above setting, maximizing the data log-likelihood is equivalent to maximizing the mutual information between ground-truth y and the prediction ˆ y, i.e., where I(·) is the mutual information 2 . Consider applying the proposed ODO on the elements of v (or equivalently on the columns of weight matrix U), the problem becomes where fc(x) = ∑ci b(x;Ui, vi) = ∑ci viσ(UTi x) is the partial expansion of basis functions. Corollary 1. The maximum likelihood objective is equivalent to where Ic = I(y, fc(x)) is the mutual information between the ground-truth and partial expansion 2 . 2 The proofs can be accessed via http://visal.cs.cityu.edu.hk/static/pubs/conf/ijcai20-fn3-sup.pdf. ![Image](https://ijcai.org/proceedings/2020/fulltext/288/image_000001_480376a457eadd42a92a37b8fd9c216b2f83ef21e99f7bbda0841e6e93b89def.png) w w Figure 2: Comparison of quantization functions: (left) AdaBits; (right) our FN3 . The line thickness indicates the number of coincide curves. Combining NN building blocks and ODO does not explicitly compose a Forward Stage-wise Additive Model, as in boosting in Eq. 1. However, Eq. 4 indicates the training objective is disentangled in a similar way. The objective includes a base mutual information I1 learned by the first block b1 = b(·;U1, v1), as well as Ic - Ic-1, which is the residual information learned by block b(·;Uc, vc). In other words, in expectation, each building block maximizes the incremental information gain and aggregates the results for final prediction. Thus, combining NN building blocks and ODO leads to residual additive blocks. This analysis can be easily extended to FN3 -layer, FN3 -path and FN3 -channel listed in Sec. 2.1. ## 2.4 Nested Quantized Neural Network As shown in Sec. 2.1, the quantization function ¯ S possesses the additive characteristic. ODO can be applied to the translated function Sj(w) = S(w - zj). To complete the quantization scheme, we leverage a factor τ to scale the input and output and make the quantization function zero-centered by using the offset 12 ∑j αj, similar to [Yang et al., 2019]: Recently, [Jin et al., 2019] and [Yu et al., 2019a] adopt the quantization function of DoReFa-Net to achieve a similar goal, and both these methods adopt switchable batch normalization for different bits. We note that these quantization methods are not truly nested, as the quantization function in DoReFa-Net is not nested in terms of different bits. To see this, note that the 2-bit and 3-bit quantization in DoReFa-Net correspond to quantization levels of Q2 = {-1, - 13 , 13 , 1} and Q3 = {-1, - 67 , . . . , - 17 , 17 , . . . , 67 , 1} respectively. Q3 does not include all the elements in Q2. AdaBits [Jin et al., 2019] modify the DoReFa-Net to address this issue. We compare the quantization function of AdaBits and our proposed FN3 in Fig. 2, where the coinciding regions are also visualized. In AdaBits, adding more bits is only backtracking the previous lower-bit quantization function, which undermines the previous mapping. If the weight value indicates the importance of its corresponding feature, then once a weight has a maximal quantization value (+1 or -1), then increasing its importance requires changing bits on all other weights. Thus, in AdaBits, the disordered coinciding regions make the optimization harder, thus switchable BN (multiple sets of BN parameters) is adopted, leading to a semi-nested network. In contrast, in FN3 , adding more bits augments information of the previous quantization function, while keeping the steps in the middle unchanged. Adding a new bit can only increase the magnitude of weights, i.e., the corresponding feature's importance. This allows a more natural ranking of the features as the number of bits increases, and better fits our formulation of using additive blocks. Figure 3: Sketch of the heuristic search algorithm. ![Image](https://ijcai.org/proceedings/2020/fulltext/288/image_000002_7b57ae942a5b81ba42bde62b70a8bee593c800272aaf8efa37eac30ae4b44f32.png) From the regularization perspective, using a limited number of bits for FN3 quantization also limits the magnitude of the weights, which is consistent with the goal of regularization. In contrast to AdaBits, with low bit numbers, the weights are either maximally activated (+1) or not, which counter-productive for regularization. ## 3 Heuristic Search In the hardware-aware NAS papers [Cai et al., 2018; Jiang et al., 2019], given fixed amount of resources, the algorithms search for the best architecture that fits the budget. The algorithm needs to be re-run once the resource budget changes. ## Algorithm 1 Heuristic search algorithm ``` Input: A trained FN3 ; candidate number C; block number per layer {Mi}i; ΔP; P = 100% - ΔP ; T = {tjk}Kk ; tjk = ∅; pool = ∅; W = {(i′ , j ′ )}. 1: whileW ̸= ∅ do 2: for k = 1 to K do 3: for c = 1 to C do 4: sample a new candidate (i∗ , j ∗ ) fromW. 5: pool = pool ∪(tjk ∪(i∗ , j ∗ )). 6: end for 7: end for 8: Evaluate acc. of tj ∈ pool and select top-K {tj∗k }Kk=1 . 9: T = {tj∗k }Kk=1 . 10: W =W \ (W ∪ T). 11: while ∀j ∈W < (P+ΔP)Mi and P ̸= 0 do 12: P = P-ΔP; MoveW by ΔP. 13: end while 14: pool = ∅. 15: end while ``` With a trained FN3 , we can also search for the best architectures for all possible budgets beforehand, at the minimal granularity. We propose a heuristic search method to find the optimal trade-off curve of accuracy w.r.t. number of blocks, as shown in Alg. 1. The main idea is to maintain multiple records of removed blocks, which we denote as "trajectories". The next block to be removed is selected based on the current trajectories with high accuracy, and thus yields an new trajectory that is more likely to be accurate. Specifically, we maintain a set of K trajectory sets T during searching. tjk = {(i, j)} ∈ T is the k-th trajectory set that contains the layer index i and block index j of removed blocks. In every iteration, for one trajectory, C candidate block are sampled from the candidate set and added to the trajectory set. The accuracy of all candidates sets are evaluated and the top-K augmented trajectory sets are selected to update T . As the blocks are highly ordered in FN3 , we leverage a sliding window, W, as the candidate set to restrict the search space, as shown in Fig. 3. The search complexity is reduced from ∑i (Ni ) = 2N - 1 to KN. Note that the number of blocks might be different in different layers, e.g., layer 1 has 128 neurons while layer 2 has 512 neurons. We assign the same proportion (ΔP) of blocks in a sliding window for different layers, e.g., 32 neurons for layer 1 and 128 neurons for layer 2 (25%). ## 4 RelatedWork The idea of nested architecture of neural network was explored by [Baram, 1988], where either square and hexagonal structures are studied. The proposed structures are no longer suitable for modern deep learning tasks. Adaptive channel: Aiming at adaptive channel and neuron, [Kim et al., 2018] propose a NestedNet to build an nin-1 network structure by solving weight connection pruning problem iteratively. This work is limited in flexibility as it provides limited number of sub-networks (3 to 4 levels shown in the experiment), while our work has 27136 with MobileNetV2 in terms of adaptive channel. Our work also outperforms [Kim et al., 2018]; on Cifar10/100, accuracy of [Kim et al., 2018] starts decreasing when half channels are pruned, while our model starts losing accuracy when over 65% components are dropped. [Yu et al., 2019b] proposed slimmable NN that trains a network with multiple setups of channel number (called width) simultaneously, where the weights are shared among different widths. The network switches to another set of batch normalization (BN) parameters once the width changes thus O(M ′2 ) BN parameters should be maintained, where M ′ is the number of channels in a layer. This method is extended (USNet [Yu and Huang, 2019]) to allow more choices of width by only recollecting the BN parameters after training. However, it still requires training multiple widths per iteration, which increases the training time. The widths are consistent for different layers, and therefore the number of sub-networks is limited. By comparison, FN3 -channel samples different number of channels for different layer per iteration, increasing the number of sub-network by 2N-M and indicating a higher level of granularity, where N = ∑i Mi. In addition, the increased number of sub-networks in FN3 -channel does not come at a price of increasing training time, making our method more efficient than the slimmable NN. In FN3 , we observe that, as the importance of blocks keeps decreasing in expectation, the influence of dropping blocks on BN parameters is trivial. Also as observed from the scaling factor during inference βm = M+1-m M (Sec. 2.2), with m growing larger, the activation is scaled to be smaller, which has low influence on BN statistics. Thus, it is not required to modify the BN scheme in FN3 . Adaptive bit: [Jin et al., 2019] proposed Adabits that is adaptive in different quantization bits. A quantization scheme similar to DoReFa-net was proposed and the switchable BN method [Yu et al., 2019b] was adopted, thus the number of sub-networks is limited. We also show the limitation of the Adabits quantization function in Sec. 2.4. More importantly, the order of either channels or bits was not studied in the previous works. We explicitly show that each building block in FN3 maximizes the incremental information gain (see Sec. 2.3). The analysis validates the idea of using residual additive blocks to build the adaptive neural network. Furthermore, the previous methods only train an adaptive network that provides sub-networks, but it is unclear what is the optimal sub-network given fixed hardware resources. In FN3 , a fast heuristic search method that leverages the block ordering is proposed. A trade-off curve of accuracy w.r.t. the number of blocks can be obtained before deployment, with a low cost. Given a fixed budget of resources, the optimal architecture can be simply obtained by checking the trade-off curve and table lookup 3 . ## 5 Evaluation The experiments are conducted on the MNIST, Cifar10, Cifar100 and ImageNet datasets. The FN3 -neuron experiment is conducted on MNIST. On Cifar10/100, we run the ablation study of FN3 -layer/-path/-channel/-bit, as well as the the comparisons of FN3 -bit and Adabits. On ImageNet, we run the experiments FN3 -channels to compare with the US-Net. For FN3 -bit, ODO is realized by adding/dropping Heaviside step functions that constitute different quantization functions. The weights in one layer share a quantization function. Thus, in the heuristic search, the block index is replaced with index of Heaviside step function. For the rest 4 block types, ODO is realized by generating masks of ones and zeros onto the input or output of a block. We run the heuristic search on the training data to get the block order. Note that during searching, one number of block might correspond to multiple results (e.g., 50 accuracy results for "100 channels removed"). We calculate the maximum, mean and standard deviation and show them in the graph. Overview: We show the overview of experimental results and ablation study in Fig. 4. The detailed experimental setups are seen in Sec. A. The blue curves show the accuracy w.r.t. removed building blocks with normal training. The removed building blocks are randomly selected and each random test is repeated for 100 times. In all the tested cases, the accuracy decreases drastically as building blocks are removed. The orange curves show the results of ODO training and random removal. On FN3 -layer/-neuron/-bit, the differences between orange curves and blue curves are significant. This indicates ODO effectively improves the overall classification performance. On FN3 -bit, ODO also improves the quantization performance of the whole network, as observed from the difference of starting points of the orange and blue curves. As for FN3 -path, the mean of accuracy has a similar trend as normal training, while the max accuracy starts decreasing when around 40 paths are removed. Therefore, ODO effectively generates highly accurate and small sub-networks. The orange curve of FN3 -channel shows a similar behavior as FN3 -path's while the fluctuation of max accuracy is more severe, which indicates the unstable performance of random removal. 3 OVIC Benchmark, Tensorflow. Figure 4: Experimental results for FN3 -layer, FN3 -path, FN3 -channel and FN3 -bit on Cifar10/100, FN3 -neuron on MNIST. ![Image](https://ijcai.org/proceedings/2020/fulltext/288/image_000003_0e4c2ee9ee68d0340835bd96d524031795b0e3c47a87be6fcb18393dd12959fb.png) Table 1: Numerical comparisons. | Model | #sub-networks | Training epochs | |--------------|-----------------|-------------------| | US-Net | 226 | 250 × n | | FN3 -channel | 27136 | 400 | The green curves shows the results of ODO training and heuristic search. In general, the heuristic search effectively finds a better trade-off curve. Moreover, as observed from the results of FN3 -channel and FN3 -path, the variance is significantly reduced and useless trajectories are pruned, thus the search complexity is reduced. This indicates the heuristic search can discover good sub-networks efficiently. The heuristic search also helps to reduce the number of evaluations during searching. For example, on FN3 -path, the number of evaluations in random removal is 7200, while that in heuristic search is 1672, reduced by 76.8%. Next, we discuss FN3 -channel and FN3 -bit in detail and show the comparisons with previous works. FN3 -channel: We train FN3 -channel with MobilenetV2 on Imagenet. The ODO mask is multiplied with the output of depth-wise convolution layer in each inverted residual block. Therefore, the zeros in the mask disable the corresponding filters of preceding point-wise convolution, depth-wise convolution and the channels of subsequent point-wise convolution [Sandler et al., 2018]. Figure 5: Performance of FN3 with MobileNetv2 on ImageNet. ![Image](https://ijcai.org/proceedings/2020/fulltext/288/image_000004_4ad7de06afd4b9e4d9a7ff330d99934cff447fb9a0d79421826635e6db2d2583.png) Fig. 5 shows that FN3 achieves a better trade-off of accuracy w.r.t. removed blocks compared with US-Net. This reveals the superiority of ODO over other methods that do not consider order of blocks. As shown in Table 1, as FN3 is fully nested, the theoretical number of sub-networks is much greater than that of US-Net. The training epochs of FN3 is steady at 400, while that of US-Net is 250n, where n is the number of sampled widths per iteration (normally n ≥ 4). FN3 -bit: The experiments on quantization are run on Cifar10/100 datasets with MobileNet-v2. The model is optimized with Adam and a cosine annealing scheduler for 600 epochs. In FN3 -bit, we use a quantization level schedule similar to [Yang et al., 2019], 2-bit: {-1, 0, 1}, 3-bit(±2): {-2, -1, 0, 1, 2}, 3-bit(±4): {-4, -2, -1, 0, 1, 2, 4}, 4-bit: Table 2: Accuracy for the same bit-width for whole network. | Cifar10 | 4-bit | 3-bit (±4) | 3-bit (±2) | 2-bit | |-----------|---------|--------------|--------------|---------| | Adabits | 91.84 | 79.3 | - | 58.98 | | FN3 -bit | 94.28 | 94.2 | 94.2 | 93.64 | | Cifar100 | 4-bit | 3-bit (±4) | 3-bit (±2) | 2-bit | | Adabits | 72.15 | 65.23 | - | 51.67 | | FN3 -bit | 76.65 | 76.34 | 75.35 | 74.97 | Figure 6: Performance of FN3 -bit using MobileNetv2 with removed step functions (bits). (a) Cifar10. (b) Cifar100. ![Image](https://ijcai.org/proceedings/2020/fulltext/288/image_000005_acb2bb2ee8126468e1084dbdc90f4b48faa846e6d56c037124f39e492005b7f8.png) {-8, -4, -2, -1, 0, 1, 2, 4, 8}. τ is initialized to 5p 4q , where p is the max absolute quantization interval and q is the max absolute value of weight. To reproduce the Adabits method, we use the modified DoReFa-net quantization function and switchable BN parameters. Following [Jin et al., 2019], during training of Adabits, we progressively reduce the number of bits, with each bit-width taking 150 epochs. The results of using the same bits for whole network are shown in Table 2. The performance of Adabits on lower bits drop dramatically, while the performance of FN3 -bit only reduces by 0.64% from 4-bit to 2-bit. This validates the idea of composing a nested quantization with multiple step functions. In FN3 , we apply different bit-widths to 7 groups of layers which leads to 47 = 16384 sub-networks while Adabits only provides 3 sub-networks. Thus, with FN3 , different layers can use different bit-widths for more flexible deployment to the given resource constraints, which is not possible with Adabits. Fig. 6 shows the results using mixed bit-widths between layers, obtained by running the heuristic search on the model used in above experiment. The x-axis indicates the bit usage, where the left side corresponds to every layer using 4 bits, the right side is every layer using 2 bits, and in between are mixed bit-widths with different number of bits (or step functions) removed. The accuracy w.r.t. bit-width curve shows that a mixed bit-width can also achieve similar accuracy to using 4-bits for all layers. For example, using around 3 bits (9 step functions removed) has similar performance to using full 4-bits. ## 6 Conclusion We propose the fully nested neural network that generates large amounts of nested sub-network, based on additive network building blocks. The proposed heuristic search is able to efficiently find the optimal sub-network, and experiment results show that our method is widely applicable to compress/quantize a variety of NN building blocks. Future work will consider how to combine different levels of blocks (e.g., channel and bits) to generate more adaptive networks. ## A Detailed Setup of Experiments FN3 -layer: We run standard RexNeXt-Cifar [Xie et al., 2017] on Cifar10 and Cifar100 dataset. ResNeXt-Cifar contains one convolutional layer for feature extraction which is kept active in this experiment, and 9 bottleneck modules each being treated as a block. We assign a uniform probability 19 to the Categorical distribution C(m) where each dimension corresponds to the index of bottleneck module. Therefore, the first bottleneck module is the least likely to be dropped. We use SGD with an initial learning rate 0.1, momentum factor 0.9 and batch size 128. The learning rate is scaled by 0.1 at epoch 150 and 225. The network is trained for 300 epochs. For heuristic search, as the ordered dropout (ODO) is performed on the bottleneck modules (group of layers), the height of sliding window is one. Because these blocks are well ordered, we set the window width to be 1 (ΔP = 19 ). In other words, the algorithm greedily selects the next block to be removed. FN3 -path: We run the same RexNeXt-Cifar as in FN3 - layer on Cifar10 and Cifar100 dataset. In each bottleneck module, 8 paths are treated as the blocks. We assign a uniform probability 1/8 to the Categorical distribution C(m) where each dimension corresponds to the index of blocks. 9 ODO units operate simultaneously. The rest hyper-parameters are the same as FN3 -layer. In such case, for heuristic search, the height of sliding window is 9. ΔP = 12.5%, C=10 and K=3. FN3 -channel: To compare with previous works, this experiment runs with MobileNet-V2 on ImageNet dataset. The ODO mask is applied to the depth-wise convolution layer in each inverted residual block. Therefore, it disables the filters of former point-wise convolution, depth-wise convolution and the channels of subsequent point-wise convolution. We keep 35% channels active during this experiment, for a fair comparison. As there are 17 inverted residual blocks, 17 ODO units operate simultaneously. The model is optimized with Adam optimizer with initial learning rate 0.1 and a cosine annealing scheduler for 400 epochs, on 6 GTX 2080ti GPUs. In each forward pass of the network, for each ODO unit, the sampled index m ∼ C(·) is broadcasted to all GPUs for consistency. For heuristic search, the height of sliding window is 17. ΔP = 12.5%, C=10 and K=3. On Cifar10/100, similar settings are adopted. FN3 -neuron: We run an MLP of structure 784-512-12810 on MNIST. We keep 12.5% neurons active during this experiment. Two ODO units are applied on the rest neurons in two hidden layers, with uniform probabilities 1 448 and 1 112 respectively. The network is trained with SGD with an initial learning rate 1.0 for 100 epochs. The learning rate is scaled by 0.7 every 10 epochs. For heuristic search, we set the height and width of window to be 1, similar to FN3 -layer. The setups for FN3 -bit are shown in Sec. 5. ## References 1. [Baram, 1988] Yoram Baram. Nested neural networks. NASA Technical Memorandum 101032, 1988. 2. [Cai et al., 2018] Han Cai, Ligeng Zhu, and Song Han. Prox- ylessnas: Direct neural architecture search on target task and hardware. arXiv preprint arXiv:1812.00332, 2018. 3. [Chen and Guestrin, 2016] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowl- edge discovery and data mining, pages 785-794. ACM, 2016. 4. [Han et al., 2016] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In International Conference on Learning Representations, 2016. 5. [Hastie et al., 2009] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009. 6. [Jiang et al., 2019] Weiwen Jiang, Xinyi Zhang, Edwin H- M Sha, Lei Yang, Qingfeng Zhuge, Yiyu Shi, and Jing- tong Hu. Accuracy vs. efficiency: Achieving both through fpga-implementation aware neural architecture search. In Proceedings of the 56th Annual Design Automation Con- ference 2019, page 5. ACM, 2019. 7. [Jin et al., 2019] Qing Jin, Linjie Yang, and Zhenyu Liao. Adabits: Neural network quantization with adaptive bit- widths. arXiv preprint arXiv:1912.09666, 2019. 8. [Kim et al., 2018] Eunwoo Kim, Chanho Ahn, and Songh- wai Oh. Nestednet: Learning nested sparse structures in deep neural networks. In Proceedings of the IEEE Confer- ence on Computer Vision and Pattern Recognition, pages 8669-8678, 2018. 9. [LeCun et al., 2015] Yann LeCun, Yoshua Bengio, and Ge- offrey Hinton. Deep learning. nature, 521(7553):436, 2015. 10. [Neklyudov et al., 2017] Kirill Neklyudov, Dmitry Molchanov, Arsenii Ashukha, and Dmitry P Vetrov. Structured bayesian pruning via log-normal multiplicative noise. In Advances in Neural Information Processing Systems, pages 6775-6784, 2017. 11. [Rippel et al., 2014] Oren Rippel, Michael Gelbart, and Ryan Adams. Learning ordered representations with nested dropout. In International Conference on Machine Learning, pages 1746-1754, 2014. 12. [Sandler et al., 2018] Mark Sandler, Andrew Howard, Men- glong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4510-4520, 2018. 13. [Veit et al., 2016] Andreas Veit, Michael J Wilber, and Serge Belongie. Residual networks behave like ensembles of rel- atively shallow networks. In Advances in neural informa- tion processing systems, pages 550-558, 2016. 14. [Wang et al., 2019] Kuan Wang, Zhijian Liu, Yujun Lin, Ji Lin, and Song Han. Haq: Hardware-aware automated quantization with mixed precision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recog- nition, pages 8612-8620, 2019. 15. [Xie et al., 2017] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual trans- formations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recogni- tion, pages 1492-1500, 2017. 16. [Yang et al., 2019] Jiwei Yang, Xu Shen, Jun Xing, Xinmei Tian, Houqiang Li, Bing Deng, Jianqiang Huang, and Xian-sheng Hua. Quantization networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7308-7316, 2019. 17. [Yu and Huang, 2019] Jiahui Yu and Thomas S Huang. Uni- versally slimmable networks and improved training tech- niques. In Proceedings of the IEEE International Confer- ence on Computer Vision, pages 1803-1811, 2019. 18. [Yu et al., 2019a] Haichao Yu, Haoxiang Li, Honghui Shi, Thomas S Huang, and Gang Hua. Any-precision deep neu- ral networks. arXiv preprint arXiv:1911.07346, 2019. 19. [Yu et al., 2019b] Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. In International Conference on Learning Representations, 2019. 20. [Zhang et al., 2018] Xiangyu Zhang, Xinyu Zhou, Mengx- iao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6848-6856, 2018. 21. [Zhou et al., 2016] Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. Dorefa-net: Train- ing low bitwidth convolutional neural networks with low bitwidth gradients. CoRR, abs/1606.06160, 2016. 22. [Zhou, 2012] Zhi-Hua Zhou. Ensemble methods: founda- tions and algorithms. Chapman and Hall/CRC, 2012.