Title: DIFFERENTIABLE ARCHITECTURE COMPRESSION

Abstract: In many learning situations, resources at inference time are much more constrained than resources at training time. This paper studies a general paradigm, called Differentiable ARchitecture Compression (DARC), that combines model compression and architecture search to learn models that are resource-efficient at inference time. Given a resource-intensive base architecture, DARC utilizes the training data to learn which sub-components can be replaced by cheaper alternatives. The high-level technique can be applied to any neural architecture, and we report experiments on state-of-the-art convolutional neural networks for image classification. For a WideResNet with 97.2% accuracy on CIFAR-10, we improve single-sample inference speed by 2.28× and memory footprint by 5.64×, with no accuracy loss. For a ResNet with 79.15% Top1 accuracy on ImageNet, we improve batch inference speed by 1.29× and memory footprint by 3.57× with 1% accuracy loss. We also give theoretical Rademacher complexity bounds in simplified cases, showing how DARC avoids overfitting despite over-parameterization.

1. INTRODUCTION:

In machine learning, resources at inference time are often much more constrained than at training time. For example, while neural networks for computer vision and natural language processing (NLP) are routinely trained using GPUs, trained networks are often deployed on embedded systems or mobile devices with limited memory and computational power. As another example, it is common to train a model that will be applied continuously in production; while training occurs for a limited time, the machine performing inference may run indefinitely, and so learning a more efficient model can directly reduce costs associated with hardware or energy usage. As a result, many recent papers have studied deep model compression and acceleration. Most of these papers provide resource efficient model components (Jaderberg et al., 2014; Zhang et al., 2016; Wu et al., 2017) or methods to prune or quantize parameters (LeCun et al., 1990; Polyak & Wolf, 2015; Li et al., 2016a; He et al., 2017; Luo & Wu, 2017; Luo et al., 2017; Zhuang et al., 2018) .

We propose a general paradigm called Differentiable ARchitecture Compression (DARC) for learning in the context of constrained resources at inference-time. Rather then suggesting a specific cheap component and using it blindly throughout a neural network, or trying to tune layer hyperparameters as in network pruning or quantization, our approach is inspired by Neural Architecture Search (NAS) (Zoph & Le, 2016; Liu et al., 2018a; Pham et al., 2018; Kandasamy et al., 2018; Liu et al., 2018b) . DARC starts with a resource-intensive network design and uses training data to learn which components can be replaced with efficient alternatives, while maintaining model output quality. The resource requirement of the final model is controlled via a regularization term, which can be flexibly defined depending on the objective, such as minimizing inference time or memory footprint.

DARC has a clear intuitive advantage when compared to methods that quantize or prune parameters; these approaches are inherently restricted in their search space. They cannot replace a layer with a structurally different layer, or replace two or more layers with a shallow alternative. As examples, it might be the case that a convolutional layer cannot be pruned without hurting performance but can be replaced with a depthwise-separable convolution, or an LSTM layer might not be amenable to weight pruning, but could be replaced with a more efficient self-attention layer. DARC, applied to deep networks, offers a way to search a rich space in the context of model compression.

The high-level idea is to partition the network into components, and explore alternatives to these components simultaneously. Replacing all components simultaneously is crucial, as it provides a data-driven way to decide which components can be replaced with cheap alternatives. Indeed, replacing layers blindly may sacrifice too much prediction performance, as can be seen in Mo-bileNets (Howard et al., 2017; Sandler et al., 2018) , which exclusively use depthwise-separable convolutions; although computationally efficient, even the most accurate MobileNet model is far less accurate at ImageNet classification than, say, ResNet50.

We frame the problem of learning good replacement components as a sparse ensemble learning problem. This view allows us to draw guidelines from simpler analyzable cases, leading to a simple, gradient-based learning scheme that avoids over-fitting and is fast enough to apply DARC directly to large datasets such as ImageNet. This contrasts from most NAS methods, which first learn an architecture on a small dataset and then fit this architecture on the larger dataset.

We present experiments on networks commonly used in computer vision. By applying our techniques on the ResNet Architecture (He et al., 2016) , we outperform state-of-the-art models on both ImageNet and CIFAR-10 datasets, in terms of accuracy vs. throughput and accuracy vs. model size. A few results from our compression framework: for a WideResNet model achieving 97.2% accuracy on CIFAR-10, we improve single-sample inference speed by 2.28× and memory footprint by 5.64×, with no loss in accuracy. For a modified ResNet50 model with 79.15% Top1 accuracy on ImageNet, we improve inference speed by 1.29× and memory footprint by 3.57× with 1% loss in accuracy. Both base models are publicly available from the GluonCV Model Zoo (Mod, 2018) . Our experiments empirically demonstrate an intuitive observation that 'you get what you optimize for', in that models minimizing model size tend to be quite different from those maximizing throughput.

We note that, while our experiments are limited to image classification, DARC is applicable to any deep learning architecture, including models with recurrent cells or transformers, or indeed any sufficiently modular learning algorithm, as described in Section 2, and any task with a well-defined objective function in which we would like to reduce inference costs. We see this work as a proof-ofconcept for capabilities of the DARC framework, and the results in this paper give a strong indication that DARC can be applied to NLP architectures, or optimized for metrics other than those we try here (e.g. for latency on devices other than GPU, or energy consumption).

2. GENERAL SETTING AND DARC ESTIMATOR:

The intuition and motivation for our method starts with a task of model selection. Given a task and J function families corresponding to candidate models, we are interested in finding the best model type for the task. We relax this combinatorial optimization problem to a more tractable differentiable optimization problem (whence the name "differentiable architecture compression"), by allowing convex combinations of these candidates. This can be thought of as a constrained form of ensemble learning in which weights are restricted to represent a convex combinations of individual learners.

Then, we posit a budget constraint: each model type has an associated cost (e.g., memory consumption or latency), and the overall cost of the ensemble is the sum of costs of the used models. Our task is then to learn a convex ensemble over a subset of candidates, with total cost within budget. We now formalize this approach, with modifications to address technical challenges as they arise.

In the sequel, for any positive integer J, [J] = {1, 2, ..., J} denotes the set of positive integers at most J, and ∆ J := x ∈ [0, 1] J : j∈[J] x j = 1 denotes the probability simplex over J elements.

Consider the conventional supervised learning setting, in which we have an i.i.d. training dataset

(X 1 , Y 1 ), ..., (X n , Y n ) IID ∼ P (X,Y ) from some joint distribution P (X,Y ) on X × Y. Fix a loss function L : R × Y → [0, ∞],

and a hypothesis class H of R-valued functions. We would like to learn a function h :

X → R, h ∈ H that minimizes the risk R(h) := E (X,Y )∼P (X,Y ) [L (h(X), Y )].

The usual empirical risk minimization (ERM) estimator is h ERM := arg min h∈H R(h) where, for any hypothesis h ∈ H, R(h) := 1 n n i=1 L (h(X i ), Y i ) denotes the empirical risk. To derive our resource-constrained objective, we impose a few structural assumptions on our hypothesis class H:

(A1) H = Conv j∈[J] H j is the convex hull of a union of J classes H 1 , ..., H J .

(A2) Each class H j class has a known cost C j ≥ 0 of using a hypothesis h j ∈ H j at test-time.

(A3) Costs are additive: hypothesis:

h = J j=1 α j h j ∈ H has cost C 0 (α) = J j=1 C j 1 {αj >0} . (A4)

We have a known budget B ≥ 0 for the final model at test-time.

As we show in Section 3, these assumptions arise naturally in architecture compression. Given assumptions equation A1-equation A4, the constrained ERM estimate is g = j∈[J] α j h j , where

( α 0 , h 0 ) := arg min α∈∆ J , hj ∈Hj R   j∈[J] α j h j   , subject to C 0 (α) ≤ B.

(1)

The above estimator is difficult (NP-hard) to compute, due to the non-smooth, non-convex budget constraint C 0 (α) ≤ B. Since this constraint bounds the 0 norm of α (weighted by C), the usual remedy would be to relax the constraint to one on the 1 norm of α (weighted by C), namely C 1 (α) := j∈[J] C j α j ≤ B. Unfortunately, due to the constraint that α lies in the probability simplex ∆ J (which implies j∈[J] α j = 1), the 1 constraint is insufficient to induce sparsity on α. Fortunately, sparse optimization on ∆ J is well-studied, with many solutions proposed (Pilanci et al., 2012; Kyrillidis et al., 2013; Li et al., 2016b) . Due to ease of implementation, we adopt a simple but effective solution proposed by (Kyrillidis et al., 2013) , which involves alternating gradient updates with a projection operation P ∆ J : R J \R J -→ ∆ J , given by P ∆ J (α) = α+ α+ 1 , where α + = (max{0, α 1 }, ..., max{0, α j }) ∈ R J + . P ∆ J is easy to compute, enforces the simplex constraint α ∈ ∆ J exactly, and induces sparsity on α. For an intuition of how this works, one can note that ∇ α 2 2 /2 = α, so that the update α/ α 1 = α -(1 -1/ α 1 ) α can be viewed as a gradient step for minimizing -α 2 2 /2 with adaptive step size (1 -1/ α 1 ). As a technicality, we note that the projection P ∆ J (α) is undefined when α ∈ R J -has no positive components. However, for realistic gradient step sizes η, this never occurs, since, after each gradient update, j∈

[J] α j ≥ 1 -O(η).

Finally, a natural initial point for our procedure is one where C 1 (α) > B, hence we reexpress the constraint C 1 (α) ≤ B as a penalty λC 1 (α). Since the value of λ corresponding to B is not known a priori, we iteratively increase λ until the solution of the optimization problem satisfies the budget constraint. The resulting DARC procedure is shown Algorithm 1. We note that the "stopping criterion" for the inner loop can be as simple as a fixed number of training epochs (as in our experiments), or a more sophisticated early-stopping criterion.

Algorithm 1: DARC algorithm for general hypotheses Data: Training Data {(X i , Y i )} n i=1 , J candidates h 1,w1 , ..., h j,wj with initial parameters w 1 , ..., w j and costs c 1 , ..., c j ≥ 0, initial cost penalty parameter λ 0 > 0, budget B. Result: α, w 1 , ..., w j such that h = j∈[J] α j h j,wj has small risk R(h) and cost

C 0 (α) ≤ B α ← (1/J, ..., 1/J), λ ← λ 0 ; while C 0 (α) > B do while stopping criterion is not met do (α, w 1 , ..., w J ) ← (α, w 1 , ..., w J ) -η ∇ α,w1,...,w J R j∈[J] α j h j,wj + C 1 (α) ; α ← P ∆ J (α); end λ ← 2λ end

3. APPLYING DARC TO DEEP NETWORKS:

DARC can be applied in a myriad of ways to compress deep neural networks. In all of these ways, the basic premise is to intelligently replace components of the network with cheaper components.

Consider a Neural Network (NN) with L layers. For layer , let W be the parameters of the layer, and g be the function mapping inputs and parameters to the output (in layers having no parameters, W can be an empty token). For example, for a fully connected layer, W is a matrix, the input x is a vector, and g is the matrix-vector multiplication function. We can write the NN as a function:

f (x) = g L (W L , g L-1 (W L-1 , • • • g 1 (W 1 , x) • • • )),

(2) To apply DARC, we consider a set of replacement candidates (g ,2 , W ,2 ), . . . , (g ,J , W ,J ) for each layer (with g ,1 , W ,1 denoting the original function and weight of the layer). For each candidate j in layer , DARC takes as input an associated cost C ,j ≥ 0. Examples of such costs include parameters count, FLOPs, or latency, which are usually easy to calculate or estimate experimentally. Applying DARC to neural network compression then involves four main steps: 1. Layerwise Continuous Relaxation: First, we replace each g , W with a weighted average g ( W , α , x) = J j=0 α ,j g ,j (W ,j , x), where α ∈ ∆ J . The original network is replaced by f

(x) = g L ( W L , α L , • • • g 1 ( W 1 , α 1 , x) • • • ).

2.. DARC Model Initialization::

Before training the DARC model, we need to initialize the α weights and the parameters of the compression candidates. We initialized the α parameters as uniform vectors α = (1/J , 1/J , ..., 1/J ). The other option we considered was to put all weight on the original candidate (α = (1, 0, ..., 0)), so that the initial model was equivalent to the original model being compressed. However, this makes the gradient of the loss 0 with respect to all parameters of the compression candidate, preventing these from training. Furthermore, the non-convex regularization discourages the weights of α to shift towards a value that makes use of the compression candidates. As for candidate parameters, we initialized each compression candidate to mimic the original layer, which we know gives good prediction results. In some cases, this can be done analytically (e.g. via PCA for lower dimensional fully-connected layers); more generally, this can be done via SGD, training the new candidate to minimize squared loss between its outputs and those of the original layer g ,1 (W ,1 , x). Since this is only for initialization, it suffices to use a small training sample and crude optimization procedure. 3. Training the Relaxed Model: We minimize the empirical risk, simultaneously over the mixture weights (αs) and the candidate weights ( W s) as described in Algorithm 1. 4. Selecting a Sub-Model: As discussed above, for sufficiently large λ, Algorithm 1 converges to a solution with small (weighted) 0 norm; i.e., α will have a small number of non-zero entries. Thus, we remove candidate g ,j (and its weight α ,j ) from the network if α ,j = 0. During optimization, we jointly optimize α and the model parameter on the same data, contrasting from other gradient based NAS approaches (Liu et al., 2018b) that split data into two training sets, optimize model parameters on one and α weights on the other. In Section 4 we analyze the Rademacher complexity of our procedure in a simple setting and show that under the condition that the original model class defined by g ,1 is richer than the alternatives, optimizing all parameters jointly does not hurt generalization guarantees when compared to the original optimization objective where J = 1. Unlike for NAS, this condition holds naturally for model compression.

Efficient Approximate Convolutions Computation in most deep networks used in computer vision problems, such as image classification, image segmentation, and object detection, is dominated by convolutional layers. This has motivated several papers on efficient approximations to convolution, such as depthwise-separable convolution (Jaderberg et al., 2014; Zhang et al., 2016; Howard et al., 2017) , bottleneck convolution (Sandler et al., 2018) , and shifts (Wu et al., 2017) .

In a standard convolution layer we have k × k filters for every input and output channel. Denoting the output channels by Y i and the input channels by X j , the i'th output channel is defined as Y i = j X j * F i,j . Here F i,j is the appropriate filter and * is the convolution operator. Restricting the discussion to the setting where the number of output and input channels are the same, a fully-grouped convolution is a more constrained alternative in which the filter is k × k but each output is computed based on a single input channel. A depthwise-separable convolution consists of a full-grouped convolution followed by a standard 1 × 1 convolution. In most setting this operation requires less compute and memory resources. A shift layer is an even cheaper alternative to depthwise-separable where the F i 's are fixed and have only a single non-zero element, resulting in computational complexity equivalent to a single 1 × 1 convolution. We use DARC to compress CNNs by considering alternatives from among the above options, for each convolution layer.

4. THEORETICAL RESULTS:

Here, we discuss generalization power models learned by DARC. We restrict our attention to the simple case of learning an ensemble of models; as described below, the result has implications for our algorithm for training DARC. This setting actually applies not only for DARC but also for various NAS methods such as DARTS (Liu et al., 2018b) or ENAS (Pham et al., 2018) . Indeed, these methods aim to choose one out of several options in each layer. While these methods differ in how this ensemble is learned, our generalization bound is independent of the learning technique.

Recall that DARC learns a convex combination of functions from J classes H 1 , . . . , H j . Here, we analyze generalizability of this process via Rademacher complexity Bartlett & Mendelson (2003) : Definition 1 (Rademacher Complexity). Let H be a class of functions mapping X → R and let n ∈ N. Denote by X n 1 = (X 1 , ..., X n ) n IID samples from X . Let σ a uniform random vector in

{-1, 1} n . The Rademacher complexity of H is R(H) = E σ,X n 1 sup h∈H 1 n i∈[n] σ i h(X n,i ) .

It is well known that the Rademacher complexity of a class H is equal to that of the convex hull of H. Based on this fact, for h = (h 1 , . . . , h J ) ∈ J j=1 H j , α • h = J j=1 α j h j , we have a generalization bound on the difference between true risk R and empirical risk R:

Theorem 1. Suppose we jointly estimate α, h 1 , ..., h J ; i.e., α, h 1 , ..., h J := arg min hj ∈Hj ,α∈∆

J :C•α≤B n i=1 L (α • h(X i ), Y i ). Let L(h(x), y) = 1 {f (x) =y} be 0-1 loss. Then, w.p. ≥ 1 -δ (over n training samples), R α • h -R α • h ≤ R j∈[J] H j + log 1 /δ n .

Since Theorem 1 follows from standard Rademacher generalization bounds (e.g., (Bartlett & Mendelson, 2003, Theorem 5(b) )), we omit its proof. Even if H 1 j∈[J] H j , in the setting of model compression the alternative families H j , j > 1 are cheaper replacements for H 1 suggesting that R(H 1 ) ≈ R( j∈[J] H j ). This observation motivates our learning framework -it shows us that there is no need to split the training set, train the model parameters on one split and the control parameters on the other, as in many NAS papers (Cai et al., 2018; Liu et al., 2018b) .

We note that does not motivate a change in the learning framework of NAS. A key difference between NAS and DARC is that candidate models H 1 , ..., H J in NAS are intentionally diverse; their union is much richer than any individual. This translates to large R j∈[J] H j , motivating a need to avoid jointly optimizing α and model parameters on a single training set. When keeping a validation set aside for training α, given the limited number of update steps typical in NAS papers, generalization error may be closer to the setting of fixed α, wherein Rademacher complexity is bounded by j α j R(H j ) (Cortes et al., 2014) , potentially much smaller than in Theorem 1.

5. EXPERIMENTAL RESULTS:

We applied DARC to a number of deep networks from the GluonCV Model Zoo (Mod, 2018) for image classification on the CIFAR-10 and ImageNet (Russakovsky et al., 2015) datasets; this section presents quantitative and qualitative results. We report three performance metrics (model size, single-sample throughput, and batch throughput), and we specifically considered using DARC to minimize two of these (model size and batch throughput). Below, "DARC(S)" denotes DARC with a model (S)ize penalty, and "DARC(T)" denotes DARC with batch (T)hroughput penalty.

Choice of Compression Candidates:

For each convolutional layer, besides the original (full) convolution, we considered 3 compression candidates: a (fully-grouped) depthwise-separable convolution with 3 × 3 kernels (abbreviated henceforth as "3x3DS"), a full convolution with 1 × 1 kernels ("1x1FC"), and a 2-layer candidate consisting of a 3x3DS layer followed immediately by a 1x1FC layer ("3x3+1x1"). In ResNet50, which was already implemented using bottleneck convolutions (He et al., 2016) consisting of a sequence of 1 × 1, 3 × 3, and 1 × 1 convolutions, the entire bottleneck sub-network was treated as a single component (i.e., all 3 convolutions were replaced with a single block from the above mentioned alternatives). We intentionally limited the choice of alternatives to maintain a simple system that can enjoy high throughput without special implementation. Our precise choice of alternatives is motivated by them already being an established component for deep networks, proven to work in some settings even without architecture search.

DARC Training Details:

To maximize fairness when comparing with models in the GluonCV Model Zoo (Mod, 2018), most aspects of training DARC were based on the training scripts provided publicly by the Model Zoo1 . Due to space constraints, these implementation details are decribed in Appendix A; a few specific differences from these scripts are described below.

Student-Teacher Initialization: As described in Section 3 we initialized compression candidates to mimic original layers using student-teacher training. While this training had to be performed separately for each compression candidate in each layer of the original model, since each compression candidate has few parameters, each candidate's training converged quite quickly. Thus, in CIFAR-10 experiments, we simply ran 1 epoch of the entire training dataset; in ImageNet experiments, we ran only 1000 batches. A relatively large step size of 0.1 was used, since teacher-student initialization is only for initialization and fine-tuning can be performed during model-selection.

Main Training Phase: As noted in Algorithm 1, training occurred in blocks of epochs (20 epochs/block for CIFAR-10, 10 for ImageNet), with the compression penalty λ increased after each block, to obtain a spectrum of compressed models. For each dataset, penalty type, and model size, the initial value of λ was selected to roughly balance the orders of magnitude of the empirical loss and the regularization term at the beginning of training. After each block, we: 1) remove candidates j with α j = 0l, 2) save (for evaluation later) a copy of the DARC model, in which, in any layer with multiple non-zero α entries, all but the most expensive remaining candidate are removed, and 3) decrease learning rate η and increase compression penalty λ (each by a factor of 2).

This "iterative compression" was repeated until only one compression candidate per layer remained in the DARC model. Finally, each saved model was fine-tuned for 20 epochs using only prediction loss (i.e., with λ = 0). This procedure enabled us to obtain a sequence of compressed models at progressively increasing compression levels. Moreover, this "warm-starting" improved compression speed since we only perform a total of 30 epochs per λ value, rather than the > 100 epochs needed for convergence at high levels of compression.

5.1. CIFAR-10 RESULTS:

By all metrics, DARC gave the best results when applied to very wide models such as the WideRes-Net series (specifically, the WideResNet16 10, WideResNet28 10, and WideResNet40 8 models (Mod, 2018)). Moreover, unlike results on other ResNets, results on WideResNets were relatively similar for both DARC(S) and DARC(T); both versions of DARC selected the 3x3+1x1 candidate for every layer. The reason for this is that very wide convolutions in WideResNet models can be replaced by depthwise separable convolutions with essentially no loss in accuracy, and improvement in throughput for both batches and for single samples (1.4-1.6× for each) and memory footprint (4-6×). In the case of WideResNet16 10, DARC produces a model with latency (single sample throughput) comparable to on of the fastest CIFAR-10 model (ResNet20 v1; see Figure 1 ), while having accuracy within 0.8% of the best model (ResNeXt29 16x64d), 3.2% accuracy points above the performance of ResNet20 v1. For complete CIFAR-10 results see Appendix tables 3-4.

5.2. IMAGENET RESULTS:

For ImageNet we compressed several ResNet models. To present the size compression results we provide Table 2 comparing accuracy change as a function of parameter reduction. We compared to previous published results compressing ResNet50 on ImageNet. To our knowledge these are the state-of-the-art results among those compressing ResNet50 on ImageNet. For compression as aggressive as 3×, we incur an accuracy drop of 0.86% while the baseline suffers a drop of 3.26%. Table 1 gives throughputs of our compressed ResNet34 and ResNet50 models and throughputs of state-of-the-art competing models, on identical hardware; our compressed models outperform these competing models, due to our initialization based on pre-trained ResNet34 and ResNet50 models.

While further details, including other compressed versions, are available in the Appendix (Figures 2 and 3 and Table 5 ), Table 2 compares prediction performance of DARC(S) with that of state-of-theart network pruning techniques applied to ResNet50 on ImageNet, at various compression levels. In the light (1.5×) compression regime, the result of (Zhuang et al., 2018) outperforms ours. The work of (Zhuang et al., 2018) complements ours, in that their novelty is in warm-starting the compressed alternative not only to mimic the original, but also to be informative w.r.t. the label. Since this work does not have an architecture search component, we suggest that future work combine this clever warm-start with an architecture search component such as DARC. Once the compression becomes more aggressive, DARC outperforms the baseline, likely since in that regime (smaller network with more training epochs), a good architecture is more important than a good warm-start.

Model:

Accuracy (Top-1) Throughput ( 224 (Zhuang et al., 2018) and ThiNet (Luo et al., 2017) , when compressing ResNet-50 trained ImageNet for ResNet-50. (S)ize denotes models optimized by DARC to minimize model size. Top1/Top5 accuracy of pretrained model were 79.15%/94.58% respectively.

In both ResNets and WideResNets, model size tends to be dominated by a small number of the largest layers in the model, and is relatively insensitive to the depth of the network. Thus, significant compression can be achieved by replacing these large layers with 3x3+1x1 candidates, which offer compression of nearly 9× (for 3 × 3 convolutions). Since the sizes (number of convolutional kernels) of ResNet layers increases from bottom to top (i.e., from input to output) DARC(S) tends to first replace the top-most layers (i.e., layers closest to the output) of the network with 3x3+1x1 candidates, proceeding towards the bottom of the network as the compression parameter λ increases.

In contrast, model latency is relatively uniformly distributed throughout the layers of the network -the time taken to compute each convolutional layer scales only weakly with the number, size, and grouping of filters. Thus, in ResNets (but not in WideResNets) 3x3+1x1 candidates, which replace 1 layer with 2 smaller layers, tend to offer little or no benefit in throughput; of the compression candidates we considered, only the smallest (3x3DS) candidates offer significant acceleration (typically of about 2×) over full convolutions. As a result, the acceleration offered by DARC(T) scales primarily with the number of layers that can be replaced by 3x3DS layers. Moreover, the replaced layers tend to be scattered throughout the network (rather than clustered near the output of the network). As noted earlier, in WideResNets, each layer is so large that the 3x3+1x1 candidate is much faster than full convolution, and DARC(T) selects this candidate for all layers.

Overall, we see that the optimal compression strategy depends on whether one is optimizing for size or for speed. This implies that some sort of intelligent replacement of components, as in DARC, is needed to obtain reliable performance improvements (as opposed to, say random baselines that have been shown to perform well in pruning). This parallels recent work (Cai et al., 2018) showing (for NAS) that optimizing for speed on different hardware (GPU, CPU, or mobile) leads to different models. While we focused on GPU throughput, we note that the speedup of depthwise-separable convolution over full convolution is typically larger on CPU and embedded devices than on GPU devices. Thus, DARC should also produce efficient architectures for these alternative hardware.

6. RELATED WORK:

Work on compressing deep networks has abounded in recent years, with diverse approaches including pruning (LeCun et al., 1990; Polyak & Wolf, 2015; Li et al., 2016a; He et al., 2017; Luo & Wu, 2017; Luo et al., 2017; Zhuang et al., 2018) , low-rank factorization (Jaderberg et al., 2014; Zhang et al., 2016; Howard et al., 2017) , fast approximate convolutions (Bagherinezhad et al., 2017; Wu et al., 2017) , knowledge distillation (Hinton et al., 2015; Romero et al., 2014) , and quantization (Gong et al., 2014; Han et al., 2015; Zhou et al., 2017; Lin et al., 2016) ; (Cheng et al., 2018) survey common approaches. In contrast, DARC searches a richer space of alternative models and has the ability to replace multiple components by a single one (e.g. replacing a bottleneck sub-network of 3 convolutions with a single convolution). Indeed, though beyond the scope of this paper, DARC can incorporate or complement many of these methods. Our initialization of compression candidates by mimicking the original layer is also reminiscent of knowledge distillation.

Another closely-related line of papers concerns Neural Architecture Search (NAS) (Pham et al., 2018; Kandasamy et al., 2018; Liu et al., 2018b; Gordon et al., 2018; Cai et al., 2018) . The most relevant papers are (Liu et al., 2018b) , (Gordon et al., 2018) , and (Cai et al., 2018) , who all use a sparse linear component weighting scheme similar to DARC. (Liu et al., 2018b) focused on pure architecture search, in which the goal is simply to find an architecture maximizing prediction performance, without consideration of inference-time efficiency. (Gordon et al., 2018) do not aim to replace layers with general alternatives but rather discover parameters in a data-driven way; their experiments are restricted to results in channel pruning. Recently, (Cai et al., 2018) performed NAS with a latency regularization term similar to ours.

Our methods differ from these NAS papers in two main ways (summarized in Table 3 ). First, our architecture search is guided by an established base model that was already tested and proven useful. This distinction allows a simpler and more efficient learning scheme (motivated in Section 4) that avoids iterating between training sets, to optimize model and α parameters. Furthermore, starting with a pre-trained model allows us not only to reach an effective architecture, but to warm start the weight parameters. As evidence of the advantage of starting with a pretrained model, our compressed model ResNet50(T) on ImageNet has Top1 accuracy ≥ 3% more than models obtained by these NAS papers; thus, it seems that starting architecture search with a highly accurate base model can improve the efficiency/accuracy trade-off of the learned model. Another distinction from gradient-based NAS results is our use of sparsity-inducing regularization. Previous methods make the choice between the candidates via a softmax layer; this restricts the output to be a convex combination of inputs without optimizing sparsity. Since these methods also aim to find a sparse combination, they might benefit from a non-convex regularization term as in DARC. 

:

train imagenet.py, train mixup cifar10.py

Figures and Tables:

Figure 2: Compression of ImageNet models, in terms of size, throughput, and latency, when size is used as the computational penalty in DARC.

According to Theorem 1, generalization error depends on a standard (log 1 /δ)/n term and Rademacher complexity of the union of classes H 1 , ..., H J . If H 1 , ..., H J are diverse, this union can be quite rich and so R ∪ j∈[J] H j might be large, leading to overfitting. However, consider an example where H 1 is the family of full convolutions, H 2 is the family of depthwise-separable convolutions, H 3 is the family of sparse convolutions, etc. Here, we actually have H 1 = j∈[J] H

Table content: <table/>

Comparison of ResNet34/ResNet50 compressed by DARC(T) with models from state-ofthe-art competing methods (as reported byCai et al. (2018) in an identical runtime environment).

Table content: <table><tr><td>× 224px/s)</td></tr></table>

Comparison of DARC and state-of-theart pruning methods, Disc

Table content: <table/>

Comparison of DARC with NAS methods. "SGD" denotes stochastic gradient descent. "RL" denotes reinforcement learning. Intelligently making only some layers of the net-work depthwise-separable results in compressed models with much better predictive performance than simply making all convolutions depthwise-separable, as in(Howard et al., 2017).While depthwise-separable convolutions are easily implemented in existing deep learning packages and already offer substantial compression, future work may benefit from more sophisticated approximate convolutions, with efficient implementations. For example, shift operations(Wu et al., 2017) are promising, as they require no stored parameters and replace the slow multiplications in convolution with fast indexing. Another venue worth pursuing is to compress a model into a shallower version. Although there are a few ways this could be attempted, such as an Identity candidate or replacing entire blocks of layers, it is unclear which technique would work best. Finally, we hope to apply DARC to models other than CNNs (e.g., models with recurrent cells or transformers).

Table content: <table><tr><td>Method</td><td>Optimizer</td><td>Efficient</td><td>Resists</td><td>Exploits</td><td>Iterative</td></tr><tr><td/><td colspan="2">architecture</td><td>Overfit-</td><td>pre-</td><td>com-</td></tr><tr><td/><td/><td/><td>ting</td><td>training</td><td>pression</td></tr><tr><td>DARTS (Liu et al., 2018b)</td><td>SGD</td><td/><td/><td/><td/></tr><tr><td>ENAS (Pham et al., 2018)</td><td>RL</td><td/><td/><td/><td/></tr><tr><td colspan="2">ProxylessNAS (Cai et al., 2018) SGD/RL</td><td/><td/><td/><td/></tr><tr><td>MNasNet (Tan et al., 2019)</td><td>SGD</td><td/><td/><td/><td/></tr><tr><td>FBNet (Wu et al., 2019)</td><td>SGD</td><td/><td/><td/><td/></tr><tr><td>DARC (proposed method)</td><td>SGD</td><td/><td/><td/><td/></tr><tr><td colspan="2">7 CONCLUSIONS AND FUTURE WORK</td><td/><td/><td/><td/></tr></table>

Results of applying size-penalized DARC to CIFAR-10 models. (O)riginal Denotes an original model taken from the GluonCV Model Zoo (Mod, 2018). (S)ize denotes a model optimized by DARC to minimize model size. (T)hroughput denotes a model optimized by DARC to maximize model throughput. Model Size is provided in MB on disk. Throughput numbers are provided in 32px ×32px images/second.

Table content: <table><tr><td>Model</td><td colspan="4">Top-1 Model Size Throughput (1 Im/batch) Throughput (256 Im/batch)</td></tr><tr><td>ResNet20 v1 (O)</td><td>92.9</td><td>1.05</td><td>684.32</td><td>52239.12</td></tr><tr><td>ResNet20 v1 (T)</td><td>91.4</td><td>1.03</td><td>749.98</td><td>34743.19</td></tr><tr><td>ResNet20 v1 (T)</td><td>90.6</td><td>0.93</td><td>1144.10</td><td>48822.26</td></tr><tr><td>ResNet20 v1 (T)</td><td>88.3</td><td>0.92</td><td>1233.44</td><td>69868.65</td></tr><tr><td>ResNet20 v2 (O)</td><td>92.7</td><td>1.05</td><td>737.07</td><td>52336.75</td></tr><tr><td>ResNet20 v2 (T)</td><td>91.9</td><td>1.01</td><td>691.04</td><td>60078.59</td></tr><tr><td>ResNet20 v2 (T)</td><td>90.7</td><td>0.83</td><td>1178.61</td><td>59269.61</td></tr><tr><td>ResNet20 v2 (T)</td><td>90.2</td><td>0.83</td><td>1275.66</td><td>70498.54</td></tr><tr><td>ResNet56 v1 (O)</td><td>94.2</td><td>3.31</td><td>377.22</td><td>18966.31</td></tr><tr><td>ResNet56 v1 (T)</td><td>93.5</td><td>3.05</td><td>389.21</td><td>19175.07</td></tr><tr><td>ResNet56 v1 (T)</td><td>92.9</td><td>2.97</td><td>398.94</td><td>24985.82</td></tr><tr><td>ResNet56 v1 (T)</td><td>92.5</td><td>2.94</td><td>399.47</td><td>25682.29</td></tr><tr><td>ResNet56 v2 (O)</td><td>94.6</td><td>3.31</td><td>389.76</td><td>18966.31</td></tr><tr><td>ResNet56 v2 (T)</td><td>94.4</td><td>3.16</td><td>398.09</td><td>20293.55</td></tr><tr><td>ResNet56 v2 (T)</td><td>94.3</td><td>3.16</td><td>409.56</td><td>20382.47</td></tr><tr><td>ResNet56 v2 (T)</td><td>94.3</td><td>3.15</td><td>409.78</td><td>21752.16</td></tr><tr><td>ResNet110 v1 (O)</td><td>95.2</td><td>6.68</td><td>213.59</td><td>9615.24</td></tr><tr><td>ResNet110 v1 (T)</td><td>94.5</td><td>5.50</td><td>222.80</td><td>10161.07</td></tr><tr><td>ResNet110 v1 (T)</td><td>93.1</td><td>5.48</td><td>229.85</td><td>12565.72</td></tr><tr><td>ResNet110 v1 (T)</td><td>90.3</td><td>5.47</td><td>237.86</td><td>13032.99</td></tr><tr><td>ResNet110 v2 (O)</td><td>95.5</td><td>6.68</td><td>174.33</td><td>9160.58</td></tr><tr><td>ResNet110 v2 (T)</td><td>94.9</td><td>5.35</td><td>225.93</td><td>10892.03</td></tr><tr><td>ResNet110 v2 (T)</td><td>94.5</td><td>5.20</td><td>226.46</td><td>11331.41</td></tr><tr><td>ResNet110 v2 (T)</td><td>94.3</td><td>5.19</td><td>233.13</td><td>11472.62</td></tr><tr><td>WideResNet16 10 (O)</td><td>96.7</td><td>65.34</td><td>349.98</td><td>5019.10</td></tr><tr><td>WideResNet16 10 (T)</td><td>96.1</td><td>16.23</td><td>601.01</td><td>7699.13</td></tr><tr><td>WideResNet28 10 (O)</td><td>97.2</td><td>139.24</td><td>158.52</td><td>2553.99</td></tr><tr><td>WideResNet28 10 (T)</td><td>96.8</td><td>24.67</td><td>455.45</td><td>4339.26</td></tr><tr><td>WideResNet40 8 (O)</td><td>97.3</td><td>136.47</td><td>155.67</td><td>2643.25</td></tr><tr><td>WideResNet40 8 (T)</td><td>96.4</td><td>21.31</td><td>395.71</td><td>4269.20</td></tr></table>

Results of applying speed-penalized DARC to CIFAR-10 models. (O)riginal Denotes an original model taken from the GluonCV Model Zoo (Mod, 2018). (S)ize denotes a model optimized by DARC to minimize model size. (T)hroughput denotes a model optimized by DARC to maximize model throughput. Model Size is provided in MB on disk. Throughput numbers are provided in 32px ×32px images/second.

Table content: <table/>

Peer review (iclr2020):
This paper proposes a new architecture search method called *DARC* that utilizes a differentiable objective function. Since a naive formulation of architecture search is reduced to a combinatorial optimization which is not differentiable, the optimization requires much computational cost. To overcome this difficulty, this paper proposes a L1-norm relaxation and apply such relation in a layer-wise manner. The method shares a similar spirit with NAS, but the proposed model is more like *model selection* from a fixed candidates, and thus there is a Rademacher complexity guarantee. The effectiveness of DARC is justified by thorough numerical experiments. Although the idea is rather straight-forward, the effectiveness of the method is well supported by the thorough experiments. In particular, it works as a model compression method and shows a favorable performances compared with SOTA methods. The pros and cons are summarized as follows. Pros: - The proposed method is simple and rather easy to implement. - The numerical experiments show the proposed method gives favorable performances compared with the existing methods. Cons: - The idea itself is rather straight-forward. - The theoretical analysis is instructive but its derivation does not require new techniques. - Compared with NAS, the proposed method should prepare a set of candidates which restrict the search space. This ensures generalization but limits its flexibility. More comments: - I could not see how efficient the method is in terms of memory. It prepares several models in each layer, thus it requires large memories. Can it be performed on more large networks? - The setting of C_j affects the result. How did you set C_j in the experiments?