Title: PARAMETER EFFICIENT TRAINING OF DEEP CONVO-LUTIONAL NEURAL NETWORKS BY DYNAMIC SPARSE REPARAMETERIZATION

Abstract: Modern deep neural networks are highly overparameterized, and often of huge sizes. A number of post-training model compression techniques, such as distillation, pruning and quantization, can reduce the size of network parameters by a substantial fraction with little loss in performance. However, training a small network of the post-compression size de novo typically fails to reach the same level of accuracy achieved by compression of a large network, leading to a widely-held belief that gross overparameterization is essential to effective learning. In this work, we argue that this is not necessarily true. We describe a dynamic sparse reparameterization technique that closed the performance gap between a model compressed through iterative pruning and a model of the post-compression size trained de novo. We applied our method to training deep residual networks and showed that it outperformed existing reparameterization techniques, yielding the best accuracy for a given parameter budget for training. Compared to existing dynamic reparameterization methods that reallocate non-zero parameters during training, our approach achieved better performance at lower computational cost. Our method is not only of practical value for training under stringent memory constraints, but also potentially informative to theoretical understanding of generalization properties of overparameterized deep neural networks.

1. INTRODUCTION:

Deep neural network's success is due in no small part to two of its surprising properties that starkly defy conventional wisdom. First, training of modern deep neural networks is a high-dimensional non-convex optimization problem, a kind prohibitively difficult in general from an optimization theoretic viewpoint. Yet first-order gradient-based methods, stochastic gradient descent (SGD) and its variants, prove to be very effective; training seldom gets trapped in bad local minima. Second, overparameterization (i.e. having more model parameters than training data examples) does not undermine generalization; highly overparameterized models in practice seldom overfit, a phenomenon at odds with traditional principles of statistical learning theory.

Simply put, huge models are not hard to train, and trained huge models are not bad ones.

Emerging evidence has attributed these effects to the geometry of high-dimensional loss landscapes of overparameterized deep neural networks (Dauphin et al., 2014; Choromanska et al., 2014; Goodfellow et al., 2014; Im et al., 2016; Wu et al., 2017; Liao & Poggio, 2017; Cooper, 2018; Novak et al., 2018) , and to the implicit regularization properties of SGD (Brutzkus et al., 2017; Zhang et al., 2018a; Poggio et al., 2017) , though a thorough theoretical understanding is not yet complete. On the other hand, practitioners, blessed in this reality, do not seem to shy away from building gigantic models. Models with parameters in the tens and hundreds of millions are common in practice, with the current record holder having a parameter count in the range of a hundred billion (Shazeer et al., 2017) .

However, huge models are computationally expensive, both spatially (in terms of memory requirements) and temporally (in terms of number of operations), at both training time and inference time. Thus, scalable methods for controlling the computational complexity of deep neural networks are key to making them more useful in practice.

To achieve efficient inference, a number of well-established model compression techniques are highly effective in reducing the post-training model size with little degradation in performance. These include distillation (e.g. Bucilua et al. (2006) ; Hinton et al. (2015) ), quantization (e.g. Hubara et al. (2016) ; McDonnell (2018) ), low-rank decomposition (e.g. Denil et al. (2013) ; Jaderberg et al. (2014) ), and pruning (e.g. Han et al. (2015) ; Zhang et al. (2018b) ), to name a few.

Despite their success, post-training compression methods require the full overparameterized model to be trained in the first place. Training remains expensive. In order to make training more efficient, significant efforts have been invested into numerical innovations for training at limited precision (e.g. Courbariaux et al. (2016) ; Köster et al. (2017) ). In contrast, however, little progress has been made in effective training at significantly reduced number of parameters.

One obvious alternative toward this goal is to seek novel network architectures, ones that are more parameter efficient1 . In fact, recent architectural innovations in deep convolutional neural networks (CNNs) not only achieved better generalization performance, but parameter efficiency as well (see Section 5).

Instead of inventing new networks, an alternative approach is to achieve higher parameter efficiency directly by reparameterizing an existing model architecture. In general, any differentiable reparameterization can be used to augment training of a given model. Let an original network (or a layer therein) be denoted by y = f (x; θ), parameterized by θ ∈ Θ. Reparameterize it by φ ∈ Φ through θ = g(φ; ψ), where g is differentiable w.r.t. φ but not necessarily w.r.t. ψ. Denote the reparameterized network by f ψ , considering ψ as metaparameters2 :

y = f ψ (x; φ) f (x; g(φ; ψ)) .

(

EQUATION

Training of f ψ is done by backpropagation further through g, as ∂ ∂φ = ∂g ∂φ ∂ ∂g . If it is so chosen that dim(Φ) < dim(Θ) and f ψ ≈ f in terms of its generalization performance, then f ψ is a more parameter efficient approximation of f . Sparse reparameterization is a special case where g is a linear projection; φ is the non-zero entries (i.e. "weights") and ψ their indices (i.e. "connectivity") in the original parameter θ. Likewise, parameter sharing (or more generally linear constraints of parameters) is a similar special case of linear reparameterization where φ is the tied parameters and ψ their indices. In this sense a convolution layer can be considered a reparameterization of a fully connected layer.

Further, if metaparameters ψ are fixed during the course of training, the reparameterization is static, whereas if ψ is adjusted adaptively during training, we call it dynamic reparameterization. Now, the question is: given a full model f , is it possible to find a more efficient reparameterization f ψ that, trained de novo, can generalize comparably well? The success of various model compression techniques suggests that such reparameterizations might exist for most well-known models, and a recent study (Frankle & Carbin, 2018) made successful post hoc identifications of sparse reparameterized small networks with precisely such properties. Nevertheless, attempts at training small networks de novo typically yield results significantly underperforming networks obtained by compressing larger models (Zhu & Gupta, 2017) . This has led to a commonly held belief that gross overparameterization is necessary for effective training. Here we argue that this is not true by presenting a dynamic sparse reparameterization technique able to train sparse models de novo without the need to compress a large model, a desirable feature for training on memory-and power-constrained devices.

Our contributions are listed as follows. 1. We showed that it is possible to train a small sparse network directly without a larger than inference-time parameter footprint at any stages of training, yet still achieving generalization performance at least on par with post-training iterative pruning of large dense models, yielding the most parameter efficient model at a given sparsity. 2. We showed that our method is more scalable and efficient, and leads to significantly better accuracy than existing dynamic sparse reparameterization training techniques.

2. RELATED WORK:

Training of differentiably reparameterized networks has been proposed in numerous studies before.

Dense reparameterization Several dense reparameterization techniques sought to reduce the size of fully connected layers. These include low-rank decomposition (Denil et al., 2013) , fastfood transform (Yang et al., 2014) , ACDC transform (Moczulski et al., 2015) , HashedNet (Chen et al., 2015) , low displacement rank (Sindhwani et al., 2015) and block-circulant matrix parameterization (Treister et al., 2018) .

Note that similar reparameterizations were also used to introduce certain algebraic properties to the parameters for purposes other than reducing model sizes, e.g. to make training more stable as in unitary evolution RNNs (Arjovsky et al., 2015) and in weight normalization (Salimans & Kingma, 2016) , to inject inductive biases (Thomas et al., 2018) , and to alter (Dinh et al., 2017) or to measure (Li et al., 2018) (Zhu & Gupta, 2017) .

Frankle & Carbin (2018) successfully identified small and sparse subnetworks post-training which, when trained in isolation, reached a similar accuracy as the enclosing big network. They further showed that these subnetworks were sensitive to initialization, and hypothesized that the role of overparameterization is to provide a large number of candidate subnetworks, thereby increasing the likelihood that one of these subnetworks will have the necessary structure and initialization needed for effective learning.

Most closely related to our work are dynamic sparse reparameterization techniques that emerged only recently. Like ours, these methods adaptively alter, by certain heuristic rules, reparameterization during training. Sparse evolutionary training (Mocanu et al., 2018) used magnitude-based pruning and random growth at the end of each training epoch. NeST (Dai et al., 2017; 2018) iteratively grew and pruned parameters and neurons during training; parameter growth was guided by gradient and pruning by magnitude. Deep rewiring (Bellec et al., 2017) combined sparse reparameterization with stochastic parameter updates for training. These methods were mostly concerned with sparsifying fully connected layers and applied to relatively small and shallow networks. We show that the method we propose in this paper is more scalable and computationally efficient than these previous approaches, while achieving better performance on deep convolutional networks.

3. METHODS:

In this section, we describe our dynamic sparse reparameterization method. Some notations first. Let all reparameterized weight tensors in the original network be denoted by {W l }, where l = 1, • • • , L indexes layers. Let N l be the number of parameters in W l , and N = l N l the total parameter count.

Sparse reparameterize W l = g (φ l ; ψ l ), where function g places components of parameter φ l into positions in W l indexed by

ψ l ∈ Ψ M l ({1, • • • , N l }) 4 , s.t. W l,ψ l,i = φ l,i , ∀i indexing components.

Let M l < N l be the dimensionality of φ l and ψ l , i.e. the number of non-zero weights in W l . Define s l = 1 -M l N l as the sparsity of W l . Global sparsity is then defined as s = 1 -M N where M = l M l . During the whole course of training, we kept global sparsity constant, specified by hyperparameter s ∈ (0, 1). Reparameterization was initialized by uniformly sampling positions in each weight tensor Algorithm 1: Reallocate free parameters within and across weight tensors

Input: φ (t) l , ψ (t) l , M (t) , H (t) From step t Output: φ (t+1) l , ψ (t+1) l , M (t+1) , H (t+1) To step t + 1 Need: K, δ

Target number of parameters to be pruned and its fractional tolerance

1 for l ∈ {1, • • • , L} do For each reparameterized weight tensor 2 Π (t) l ← i : φ (t) l,i < H (t)

Indices of subthreshold components of φ

(t)

l to be pruned

3 K (t) l , R (t) l ← Π (t) l , M (t) l -Π (t) l

Numbers of pruned and surviving weights

4 if l K (t) l < (1 -δ)K then Too few parameters pruned 5 H (t+1) ← 2H (t)

Increase pruning threshold

6 else if l K (t) l > (1 + δ)K then Too many parameters pruned 7 H (t+1) ← 1 2 H (t)

Decrease pruning threshold 8 else

A proper number of parameters pruned 9

H (t+1) ← H (t) Maintain pruning threshold 10 for l ∈ {1, • • • , L} do For each reparameterized weight tensor 11 G (t) l ← R (t) l l R (t) l l K (t) l

Redistribute parameters for growth

12 ψ(t) l ∼ U Ψ G (t) l {1, • • • , N l } \ ψ (t) l,i

Sample zero positions to grow new weights

EQUATION

l New reparameterization at the global sparsity s, i.e.

ψ (0) l ∼ U Ψ M (0) l ({1, • • • , N l }) , ∀l, where M (0) l = (1 -s)N l .

Associated parameters φ (0) l were randomly initialized.

Dynamic reparameterization was done periodically by repeating the following steps during training:

1. Train the model (currently reparameterized by φ

EQUATION

) for P batch iterations; 2. Reallocate free parameters within and across weight tensors following Algorithm 1 to arrive at new reparameterization φ

EQUATION

.

The adaptive reallocation is in essence a two-step procedure: a global pruning followed by a tensorwise growth. Specifically our algorithm has the following key features:

• Pruning was based on magnitude of weights, by comparing all parameters to a global threshold H, making the algorithm much more scalable than methods relying on layer-specific pruning. • We made H adaptive, subject to a simple setpoint control dynamics that ensured roughly K weights to be pruned globally per iteration. This proved to be much cheaper computationally than pruning exactly K smallest weights, which requires sorting all weights in the network. • Growth was by uniformly sampling zero weights and tensor-specific, thereby achieving a reallocation of parameters across layers. The heuristic guiding growth is

EQUATION

where

K (t) l and R (t) l = M (t) l -K (t)

l are the pruned and surviving parameter counts, respectively. This rule allocated more free parameters to weight tensors with more surviving entries, while keeping the global sparsity the same by balancing numbers of parameters pruned and grown 5 . 5 Note that an exact match is not guanranteed due to rounding errors in Eq. 2 and the possibility that

M (t) l -K (t) l + G (t) l

> N l , i.e. free parameters in a weight tensor exceeding its dense size after reallocation. We added an extra step to redistribute parameters randomly to other tensors in these cases, thereby assuring an exact global sparsity. The entire procedure can be fully specified by hyperparameters s, P, K, δ, H (0) . For specific values used in experiments see implementational details in Appendix A.

4. EXPERIMENTAL RESULTS:

We evaluated our method in three sets of experiments (Table 1 ). We chose more modern convolutional networks, Resnet (He et al., 2015) and Wide Resnet (Zagoruyko & Komodakis, 2016) , with parameter efficiency superior to earlier models, e.g. AlexNet (Krizhevsky et al., 2012) and VGG (Simonyan & Zisserman, 2014) , thanks to the adoption of skip connections and use of global average pooling over fully connected layers. Such a setup makes a much stronger case for our method because compression is much harder for these recent models. Pre-activation batch normalization was used in all cases.

Dynamic sparse reparameterization was applied to all weight tensors of fully connected and convolutional layers (with the exception of downsampling convolutions and the first convolutional layer taking the input image), while all biases and parameters of normalization layers were kept dense6 .

At a specific sparsity s, we compared our method (dynamic sparse) against six baselines: LeNet-300-100 on MNIST Like previous work on post-training compression, e.g. Han et al. (2015) , and dynamic reparameterization, e.g. Bellec et al. (2017) , we first experimented with a simple LeNet-300-100 trained on MNIST. We found that static sparse grossly underperformed compressed sparse, a gap effectively closed by our dynamic sparse method (Figure 1a ) with the following nuances. Dynamic sparse slightly outperformed compressed sparse at very high sparsity (i.e. low parameter count), a trend reversed, albeit weakly, at lower sparsities.

A breakdown of post-training sparsities across layers of the network (Figure 1b ) reveals reliable patterns emerged from the dynamics of our adaptive reparameterization algorithm. This is consistent with previous observations (Bellec et al., 2017) that, given a fixed global sparsity, it was wiser to allocate more free parameters to the last layer, than to impose constant sparsity on all layers.

WRN-28-2 on CIFAR10 Next, we experimented with a Wide Resnet model WRN-28-2 (Zagoruyko & Komodakis, 2016) trained to classify CIFAR10 images (see Appendix A for details of implementation). As shown in Figure 2a , static sparse and thin dense significantly underperformed the state-of-the-art compressed sparse model, whereas our method dynamic sparse significantly outperformed it. Deep rewiring significantly lagged all other method. While the performance of SET Numbers in square brackets are differences from the full dense baseline. Romanized numbers are results of our experiments, and italicized ones taken directly from the original paper. Performance of two structured pruning methods, ThiNet and Sparse Structure Selection (SSS), are also listed for comparison (below the double line, see Appendix C for discussion of their relevance); note the difference in parameter counts. was on par with compressed sparse, it lagged behind dynamic sparse at high sparsity levels. At low sparsity levels SET largely closed the gap to compressed sparse.

Residual group Layer sparsity:

Again, consistent sparsity patterns emerged from the adaptive reparameterization dynamics of Algorithm 1 (Figure 2b, c & d ). We observed two rough trends: (a) larger parameter tensors tended to be sparser than smaller ones, and (b) deeper layers tended to be sparser than shallower ones.

Resnet-50 on Imagenet Finally, we experimented with the Resnet-50 bottleneck architecture (He et al., 2015) trained on Imagenet (see Appendix A for details of implementation). We tested two global sparsity levels, 0.8 and 0.9 (Table 2 ). Again, our method (dynamic sparse) outperformed state-of-the-art sparse compression (compressed sparse), which in turn outperformed static sparse and thin dense baselines. We also list in Table 2 two representative methods of structured pruning (see Appendix C), ThiNet (Luo et al., 2017) and Sparse Structure Selection (Huang & Wang, 2017) , which, consistent with recent criticisms (Liu et al., 2018) , underperformed static dense baselines.

Consistent with the aforementioned experiments with LeNet-100-10 and WRN-28-2, reliable sparsity patterns across layers emerged from dynamic parameter reallocation during training, displaying the same empirical trends described above (Figure 3 ).

Computational overhead of dynamic reparameterization:

We assessed the additional computational cost incurred by reparameterization steps (Algorithm 1) during training, and compared ours with existing dynamic sparse reparameterization techniques, DeepR and SET (Table 3 ). Because both SET and ours reallocate parameters only intermittently (every few hundred training iterations), the computational overhead was negligible for the experiments presented here7 . DeepR, however, requires adding noise to gradient updates as well as reallocating parameters every training iteration, and therefore led to a significantly larger overhead.

5. DISCUSSION:

In this work, we described and validated the best known solution so far to the following problem: given a small, fixed budget of parameters for a deep CNN throughout training time, how to train it to yield the best generalization performance. Our method used a dynamic reparameterization technique that adaptively reallocated free parameters across the network based on a simple heuristic. We demonstrated that this method not only fared much better than static reparameterization techniques, but also significantly outperformed even the state-of-the-art sparse compression methods. Note that compression is a much more forgiving situation where the parameter budget is not imposed during the entire course, but only at the end, of training.

Thus, our method yielded the most parameter efficient sparse reparameterization of a given CNN.

The past few years have seen a steady improvement in parameter efficiency of state-of-the-art CNN models thanks to innovations in network architectures. Specifically, the introduction of residual modules and the use of global pooling in place of fully connected layers are largely responsible, as convolutional layers are more parameter efficient than fully connected layers in general. For example, AlexNet (Krizhevsky et al., 2012) had a majority of its parameters in fully connected layers, and this fraction has been decreasing in VGG (Simonyan & Zisserman, 2014) , Inception (Szegedy et al., 2014) , and more recently in Resnets (He et al., 2015) it was reduced to close to none. Meanwhile, compact architectures with far fewer parameters also emerged at reasonable costs of performance degradation, e.g. SqueezeNet (Iandola et al., 2016) and MobileNet (Howard et al., 2017) , for niche use cases where computing resources are limited.

Here we took a different, but complementary, approach. Instead of searching the space of network architectures for new models with superior parameter efficiency, we sought to reparameterize a given model to make it more parameter efficient. Such techniques have a history as long as modern convolutional networks. Most early methods used dense reparameterization (Denil et al., 2013; Yang et al., 2014; Moczulski et al., 2015; Sindhwani et al., 2015) , effective in reducing redundancy in fully connected layers of big sizes, such as in AlexNet. These became less relevant as models became increasingly free of large linear layers but heavy in convolutional ones8 .

Sparse reparameterization, on the other hand, has been shown useful in compression of state-of-the-art deep CNNs (Han et al., 2015; Narang et al., 2017) . However, a prominent empirical observation from these compression studies is that training a small sparse model de novo could never reach the same accuracy achieved by one of the same size compressed down from a large model (Zhu & Gupta, 2017) . Why does it seem impossible to train a compact network but easy to compress a large one?

The "lottery ticket hypothesis" (Frankle & Carbin, 2018) offered a plausible explanation. The authors identified, by post-training pruning, trainable sparse models that, albeit sensitive to initialization, generalized comparably well (called "winning tickets"). They further posited that, the necessity of starting training with a large model is because only a big network with combinatorially a huge number of small subnetworks has a high probability of "winning the initialization lottery". Similarly, here we argue that post hoc identification of trainable compact (not necessarily sparse) reparameterization is actually rather trivial also because the optimization trajectory is typically a very low-dimensional object. Take for example the training of Resnet-152 (parameter count 60.2M) as described by He et al. (2015) : parameter updates for 600K iterations reliably send a random initialization to a state-of-the-art solution. One could simply take a trivial post hoc reparameterization as a linear projection onto the span of the 600K parameter updates which, even if they are all linearly independent from each other, amount to less than 1% of the total parameter count. The low dimensionality of optimization trajectory is consistent with emerging evidence suggesting that optima of overparameterized deep neural networks are usually high-dimensional manifolds with low co-dimensions (Cooper, 2018) , and that such optima have superior generalization properties (Wu et al., 2017) and favored by SGD (Zhang et al., 2018a; Poggio et al., 2017) .

What prohibits any post hoc reparameterized compact model from being effectively trained de novo is however its sensitivity to initialization-though optimization trajectories are each low-dimensional, their linear spans do not necessarily overlap when starting from different initial points. An obvious way "to win the lottery" is to purchase all available tickets (i.e. having a huge model to cover all possible linear spans of optimization trajectories), but it is also conceivably feasible "to cheat" by adaptively changing the number on a single ticket as the lottery result is being announced (i.e. dynamic reparameterization that continually re-orients a low-dimensional parameter manifold tangentially along an optimization trajectory). We believe our method did exactly this.

We were inspired by previous methods of dynamic sparse reparameterization, e.g. DeepR (Bellec et al., 2017) and SET (Mocanu et al., 2018) (also see Appendix C). Compared to these techniques, our method has a number of advantages. First, ours produced better performing sparse CNNs, fully closed the gap to compression of large dense models. Second, our reparameterization incurred the least computational overhead during training by infrequent and cheap parameter reallocation. Finally, our method is highly scalable thanks to its automatic reallocation of parameters across layers, without the need of manually configuring sparsity for each layer9 .

A noteworthy observation from our experiments is that the highest parameter efficiency was achieved by non-structured sparsification (see Appendix C for details). Accuracy suffered significantly when structure was imposed on the sparsity patterns (see Appendix D). Because computations involving fine-grained sparsity cannot be readily accelerated on GPUs, a number of compression methods by structured pruning (see Appendix C) remove entire channels from deep CNNs to yield smaller networks with dense parameter tensors. However, many of these structured pruning methods produced compressed models no better than direct training of a thin dense model (Liu et al., 2018) (also see Table 2 for examples compared with our method).

Our findings suggest that it is possible to train sparse models directly to reach generalization performances equal to or better than those of dense or sparse networks of comparable size produced by compression. This warrants a renewed look at the practical choices of best hardware architectures for training, between computing devices optimized for dense linear algebra versus those suited for sparse operations. 

We also compared our dynamic sparse reparameterization method to a number of static dense reparameterization techniques, e.g. Denil et al. (2013) ; Yang et al. (2014) ; Moczulski et al. (2015) ; Sindhwani et al. (2015) ; Chen et al. (2015) ; Treister et al. (2018) . Instead of sparsification, these methods impose structure on large parameter tensors by parameter sharing. Most of these methods have not been used for convolutional layers except for recent ones (Chen et al., 2015; Treister et al., 2018) . We found that HashedNet (Chen et al., 2015) had the best performance over other static dense reparameterization methods, and also benchmarked our method against it. Instead of reparameterizing a parameter tensor with N entries to a sparse one with M < N non-zero components, HashedNet's reparameterization is to put M free parameters into N positions in the parameter through a random mapping from {1, • • • , N } to {1, • • • , M } computed by cheap hashing, resulting in a dense parameter tensor with shared components.

Results of LeNet-300-100-10 on MNIST are presented in Figure 4a , those of WRN-28-2 on CIFAR10 in Figure 4b , and those of Resnet-50 on Imagenet in Table 5 . For a certain global sparsity s of our method, we compare it against a HashedNet with all reparameterized tensor hashed such that each had a fraction 1 -s of effective parameter count. We found that our method dynamic sparse significantly outperformed HashedNet. Numbers in square brackets are differences from the full dense baseline.

the size of the final sparse model for inference. We make a distinction between these direct training methods (first block) and compression methods (second and third blocks of Table 6 )11 .

This distinction is meaningful in two ways: (a) practically, direct training methods are more memoryefficient on appropriate computing substrate by requiring parameter storage of no more than the final compressed model size; (b) theoretically, these methods, if performing on par with or better than compression methods (as this work suggests), shed light on an important question: whether gross overparameterization is necessary for good generalization performance?

Granularity of sparsity The granularity of sparsity refers to the additional structure imposed on the placement of the non-zero entries of a sparsified parameter tensor. The finest-grained case, namely non-structured, allows each individual weight in a parameter tensor to be zero or non-zero independently. Early compression techniques, e.g. Han et al. (2015) , and more recent pruning-based compression methods based thereon, e.g. Zhu & Gupta (2017) , are non-structured (second block of Table 6 ). So are all direct training methods like ours (first block of Table 6 ).

Non-structured sparsity makes its computations difficult to accelerate on GPUs. To tackle this problem, a class of compression methods, called structured pruning (third block in Table 6 ), constrain "sparsity" to a much coarser granularity. Typically, pruning is performed to an entire convolution channel, e.g. ThiNet (Luo et al., 2017) , even whole layers or residual blocks (Huang & Wang, 2017) . This way, the compressed "sparse" model has essentially smaller and/or fewer dense parameter tensors, and computation can thus be accelerated on GPUs the same way as dense neural networks.

These structured compression methods, however, did not make a useful baseline in this work, for the following reasons. First, because they produce dense models, their relevance to our method (non-structured, non-compression) is far more remote than non-structured compression techniques yielding sparse models, for a meaningful comparison. Second, typical structured pruning methods substantially underperformed non-structured ones (see Table 2 for two examples, ThiNet and SSS), and emerging evidence has called into question the fundamental value of structured pruning: Mittal et al. (2018) found that the channel pruning criteria used in a number of state-of-the-art structured pruning methods performed no better than random channel elimination, and Liu et al. (2018) found that fine-tuning in a number of state-of-the-art pruning methods fared no better than direct training of a randomly initialized pruned model which, in the case of channel/layer pruning, is simply a less wide and/or less deep dense model (see Table 2 for comparison of ThiNet and SSS against thin dense).

In addition, we also performed extra experiments in which we constrained our method to perform "structured sparsification" and obtained significantly worse results, see Appendix D.

Predefined versus automatically discovered sparsity levels across layers The last key feature (rightmost column of Table 6 ) for our classification of methods is whether the sparsity levels of different layers of the network is automatically discovered during training or predefined by manual configuration. The value of automatic sparsification, e.g. ours, is twofold. First, it is conceptually more general because parameter reallocation heuristics can be applied to diverse model architectures, whereas layer-specific configuration has to be cognizant of network architecture, and at times also of the task to learn. Second, it is practically more scalable because it obviates manual configurations of layer-wise sparsity, agnostic of the depth and size of the network, keeping the overhead of hyperparameter tuning constant rather than scaling with model depth/size. In addition to efficiency, we also show in Appendix E extra experiments on how automatic parameter reallocation across layers contributed to its effectiveness.

In conclusion, to the best of our knowledge, our method is unique from all existing ones because it • strictly maintained a fixed parameter footprint throughout the entire course of training, and • automatically discovered layer-wise sparsity levels during training.

:

We formally introduce the notion of parameter efficiency as follows: given a dataset and a task, if model family A achieves a specific level of generalization performance with fewer parameters than model family B, we say A is more parameter efficient than B at that performance level.

We use the term metaparameter to refer to the parameters ψ of the reparameterization function g. They differ from parameters φ in that they are not simultaneously optimized with model parameters, and they differ from hyperparameters in that they define meaningful structures of the model which are required for inference.

Note that these, as well as all other techniques we benchmark against in this paper, impose non-structured sparsification on parameter tensors, yielding sparse models. There also exist a class of structured pruning methods that "sparsify" at channel or layer granularity, e.g.Luo et al. (2017) andHuang & Wang (2017), generating essentially small dense models. We describe a full landscape of existing methods in Appendix C.

By Ψp(Q) σ(Ψ) : Ψ ∈ 2 Q , Ψ = p, σ ∈ Sp we denote the set of all cardinality p ordered subsets of finite set Q.

As described in Section 3, global sparsity s was defined as the overall sparsity of all reparameterized parameter tensors, not the entire model, which had a tiny fraction of dense parameters in our examples.

Because of the rather negligible overhead, the reduced operation count thanks to the elimination of sorting operations did not amount to a substantial improvement over SET on GPUs. However, our method has more prominent strengths over SET in its abilities to produce better sparse models and to reallocate free parameters automatically (see Appendix C).

Note that a dense reparameterization trick, HashedNet(Chen et al., 2015), is closely related to sparse methods and can be readily applied to CNNs. We compared our method with HashedNet in Appendix B.

Dynamic reallocation across layers also contributed to the effectiveness of our method (see Appendix E).

This is a mere implementational choice for ease of experimentation given available hardware and software, which did not save memory because of sparsity. With computing substrate optimized for sparse linear algebra, our method is duly expected to realize the promised memory efficiency.

Note that an intermediate case is NeST(Dai et al., 2017;2018), which started training with a small network, grew it to a large size, and finally pruned it down again. Thus, a fixed parameter footprint is not strictly imposed throughout training, so we list NeST in the second block of Table6.

Figures and Tables:

Figure 1: LeNet-300-100 on MNIST. (a) Test accuracy plotted against number of trainable parameters for different methods. Dashed lines are used for full dense model and for compression methods, whereas all reparameterization methods maintaining a fixed sparsity level throughout training are represented by solid lines.Circular symbols mark the median of 5 runs, error bars standard deviation. Parameter counts include all trainable parameters, i.e. reparameterized sparse paremeter tensors plus all other parameter tensors that were kept dense, such as those of batch normalization layers. For small numbers of trainable parameters, the static sparse model fails to learn (not shown, out of ordinate range). (b) Layer-wise breakdown of final sparsities emerged from our dynamic sparse parameterization algorithm (Algorithm 1) at different levels of overall sparsity. Mean and standard deviation from 5 runs.

Figure 3: Block-wise breakdown of final sparsities of Resnet-50 trained on Imagenet. (a) At overall sparsity 0.8. Similar to Figure 2c. (b) Same as (a) at overall sparsity of 0.9.

Figure 4: Comparison to HashedNet. (a) Test accuracy for LeNet-300-100-10 trained on MNIST. (b) Test accuracy for WRN-28-2 trained on CIFAR10. Conventions same as in Figure 1a.

properties of the loss landscape. All dense reparameterization methods to date are static.

Table content: <table><tr><td>Sparse reparameterization Successful training of sparse reparameterized networks usually employs</td></tr><tr><td>iterative pruning and retraining, e.g. Han et al. (2015); Narang et al. (2017); Zhu &amp; Gupta (2017) 3 .</td></tr><tr><td>Training typically starts with a large pre-trained model and sparsity is gradually increased during the</td></tr><tr><td>course of fine-tuning. Training a small, static, and sparse model de novo always fared much worse</td></tr><tr><td>than training a large one to begin with</td></tr></table>

Datasets and models used in experiments brevity architecture specifications omit batch normalization and activations. Fully connected (F) and convolutional (C) layers are specified with output size and kernel size, Max pooling (MaxPool) with kernel size and none with global average pooling (GlobalAvgPool). Brackets enclose residual blocks postfixed with repetition numbers; downsampling convolution in the first block of a scale group is implied.

Table content: <table><tr><td>Dataset</td><td>MNIST</td><td>CIFAR10</td><td>Imagenet</td></tr><tr><td>Model</td><td>LeNet-300-100</td><td>WRN-28-2</td><td>Resnet-50</td></tr><tr><td/><td>(LeCun et al., 1998)</td><td>(Zagoruyko &amp; Komodakis, 2016)</td><td>(He et al., 2015)</td></tr><tr><td colspan="2">Architecture F300</td><td>C16/3×3</td><td>C64/7×7-2, MaxPool/3×3-2</td></tr><tr><td/><td>F100</td><td>[C16/3×3,C16/3×3]×4</td><td>[C64/1×1, C64/3×3, C256/1×1]×3</td></tr><tr><td/><td>F10</td><td>[C64/3×3,C64/3×3]×4</td><td>[C128/1×1, C128/3×3, C512/1×1]×4</td></tr><tr><td/><td/><td>[C128/3×3,C128/3×3]×4</td><td>[C256/1×1, C256/3×3, C1024/1×1]×6</td></tr><tr><td/><td/><td>GlobalAvgPool, F10</td><td>[C512/1×1, C512/3×3, C2048/1×1]×3</td></tr><tr><td/><td/><td/><td>GlobalAvgPool, F1000</td></tr><tr><td colspan="2"># Parameters 267K</td><td>1.5M</td><td>25.6M</td></tr></table>

DeepR: sparse model trained by using Deep Rewiring(Bellec et al., 2017); • SET: sparse model trained by using Sparse Evolutionary Training (Mocanu et al., 2018). Note that compressed sparse is a compression method that starts training with a dense model, whereas DeepR and SET, like ours, are dynamic reparameterization techniques that maintain sparsity throughout training. See Appendix A for hyperparameters used in the experiments.

Table content: <table/>

Test accuracy% (top-1, top-5) of Resnet-50 trained on Imagenet

Table content: <table><tr><td colspan="8">Final overall sparsity (# Parameters) 0.8 (7.3M) 0.9 (5.1M) 0.0 (25.6M)</td></tr><tr><td>static</td><td>Thin dense Static sparse</td><td>71.6 [-3.3] 70.4 [-4.5]</td><td>90.3 [-2.1] 89.8 [-2.6]</td><td>69.4 [-5.5] 66.4 [-8.5]</td><td>89.2 [-3.2] 87.4 [-5.0]</td><td/><td/></tr><tr><td>Reparameterization</td><td>DeepR</td><td>-</td><td>-</td><td>-</td><td>-</td><td/><td/></tr><tr><td/><td>(Bellec et al., 2017)</td><td>[-]</td><td>[-]</td><td>[-]</td><td>[-]</td><td>74.9</td><td>92.4</td></tr><tr><td>dynamic</td><td>SET (Mocanu et al., 2018)</td><td>72.6 [-2.3]</td><td>91.2 [-1.2]</td><td>70.4 [-4.5]</td><td>90.1 [-2.3]</td><td>[0.0]</td><td>[0.0]</td></tr><tr><td/><td>Dynamic sparse</td><td>73.3</td><td>92.4</td><td>71.6</td><td>90.5</td><td/><td/></tr><tr><td/><td>(Ours)</td><td>[-1.6]</td><td>[ 0.0]</td><td>[-3.3]</td><td>[-1.9]</td><td/><td/></tr><tr><td/><td>Compressed sparse</td><td>73.2</td><td>91.5</td><td>70.3</td><td>90.0</td><td/><td/></tr><tr><td/><td>(Zhu &amp; Gupta, 2017)</td><td>[-1.7]</td><td>[-0.9]</td><td>[-4.6]</td><td>[-2.4]</td><td/><td/></tr><tr><td>Compression</td><td>ThiNet (Luo et al., 2017)</td><td>68.4 [-4.5]</td><td>88.3 [-2.8]</td><td colspan="4">(at 8.7M parameter count)</td></tr><tr><td/><td>SSS (Huang &amp; Wang, 2017)</td><td>71.8 [-4.3]</td><td>90.8 [-2.1]</td><td colspan="4">(at 15.6M parameter count)</td></tr></table>

Computational overhead of dynamic reparameterization during training WRN-28-2 on CIFAR10 Resnet-50 on Imagenet Shown are median ratios of wall-clock epoch times for training with over without reparameterization, standard deviation estimated from 25 epochs. WRN-28-2 on CIFAR10 was trained on a single Nvidia Titan Xp GPU, and Resnet-50 on Imagenet on four with data parallelism (also see Appendix A for implementation details).

Table content: <table><tr><td>DeepR (Bellec et al., 2017)</td><td>4.466 ± 0.358</td><td>5.636 ± 0.218</td></tr><tr><td>SET (Mocanu et al., 2018)</td><td>1.087 ± 0.049</td><td>1.009 ± 0.002</td></tr><tr><td>Dynamic sparse (Ours)</td><td>1.083 ± 0.051</td><td>1.005 ± 0.004</td></tr></table>

Hyperparameters for all experiments presented in the paper

Table content: <table><tr><td>Experiment</td><td colspan="2">LeNet-300-100</td><td colspan="2">WRN-28-2</td><td colspan="2">Resnet-50</td></tr><tr><td/><td colspan="2">on MNIST</td><td colspan="2">on CIFAR10</td><td colspan="2">on Imagenet</td></tr><tr><td colspan="4">Hyperparameters for training</td><td/><td/><td/></tr><tr><td>Number of training epochs</td><td/><td>100</td><td/><td>200</td><td/><td>100</td></tr><tr><td>Mini-batch size</td><td/><td>100</td><td/><td>100</td><td/><td>256</td></tr><tr><td>Learning rate schedule</td><td>1 -25:</td><td>0.100</td><td>1 -60:</td><td>0.100</td><td>1 -30:</td><td>0.1000</td></tr><tr><td>(epoch range: learning rate)</td><td>26 -50:</td><td>0.020</td><td>61 -120:</td><td>0.020</td><td>31 -60:</td><td>0.0100</td></tr><tr><td/><td>51 -75:</td><td>0.040</td><td>121 -160:</td><td>0.040</td><td>61 -90:</td><td>0.0010</td></tr><tr><td/><td>76 -100:</td><td>0.008</td><td>161 -200:</td><td>0.008</td><td>91 -100:</td><td>0.0001</td></tr><tr><td>Momentum (Nesterov)</td><td/><td>0.9</td><td/><td>0.9</td><td/><td>0.9</td></tr><tr><td>L 1 regularization multiplier</td><td/><td>0.0001</td><td/><td>0.0</td><td/><td>0.0</td></tr><tr><td>L 2 regularization multiplier</td><td/><td>0.0</td><td/><td>0.0005</td><td/><td>0.0001</td></tr><tr><td colspan="7">Hyperparameters for sparse compression (compressed sparse) (Zhu &amp; Gupta, 2017)</td></tr><tr><td>Number of pruning iterations (T )</td><td/><td>10</td><td/><td>20</td><td/><td>20</td></tr><tr><td>Number of training epochs</td><td/><td>2</td><td/><td>2</td><td/><td>2</td></tr><tr><td>between pruning iterations</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Number of training epochs post-pruning</td><td/><td>20</td><td/><td>10</td><td/><td>10</td></tr><tr><td>Number of epochs during pruning</td><td/><td>40</td><td/><td>50</td><td/><td>50</td></tr><tr><td>Learning rate schedule during pruning</td><td>1 -20:</td><td>0.0200</td><td>1 -25:</td><td>0.0200</td><td>1 -25:</td><td>0.0100</td></tr><tr><td>(epoch range: learning rate)</td><td>21 -30:</td><td>0.0040</td><td>25 -35:</td><td>0.0040</td><td>26 -35:</td><td>0.0010</td></tr><tr><td/><td>31 -40:</td><td>0.0008</td><td>36 -50:</td><td>0.0008</td><td>36 -50:</td><td>0.0001</td></tr><tr><td colspan="6">Hyperparameters for dynamic sparse reparameterization (dynamic sparse) (ours)</td><td/></tr><tr><td>Number of parameters to prune (K)</td><td/><td>600</td><td/><td>20,000</td><td/><td>200,000</td></tr><tr><td>Fractional tolerance of K (δ)</td><td/><td>0.1</td><td/><td>0.1</td><td/><td>0.1</td></tr><tr><td>Initial pruning threshold (H (0) )</td><td/><td>0.001</td><td/><td>0.001</td><td/><td>0.001</td></tr><tr><td>Reparameterization period (P ) schedule</td><td>1 -25:</td><td>100</td><td>1 -25:</td><td>100</td><td>1 -25:</td><td>1000</td></tr><tr><td>(epoch range: P )</td><td>26 -50:</td><td>200</td><td>26 -80:</td><td>200</td><td>26 -50:</td><td>2000</td></tr><tr><td/><td>51 -75:</td><td>400</td><td>81 -140:</td><td>400</td><td>51 -75:</td><td>4000</td></tr><tr><td/><td>76 -100:</td><td>800</td><td>141 -200:</td><td>800</td><td>76 -100:</td><td>8000</td></tr><tr><td colspan="6">Hyperparameters for Sparse Evolutionary Training (SET) (Mocanu et al., 2018)</td><td/></tr><tr><td>Number of parameters to prune at each re-parameterization step</td><td/><td>-</td><td/><td>20,000</td><td/><td>200,000</td></tr><tr><td>Reparameterization period (P ) schedule</td><td/><td>-</td><td>1 -25:</td><td/><td/><td/></tr><tr><td>(epoch range: P )</td><td/><td/><td>26 -80:</td><td/><td/><td/></tr><tr><td/><td/><td/><td>81 -140:</td><td/><td/><td/></tr><tr><td/><td/><td/><td>141 -200:</td><td/><td/><td/></tr></table>

Test accuracy% (top-1, top-5) of Resnet-50 on Imagenet for dynamic sparse vs. HashedNet

Table content: <table><tr><td>Final overall sparsity (# Parameters)</td><td>0.8 (7.3M)</td><td>0.9 (5.1M)</td></tr><tr><td>HashedNet</td><td colspan="2">70.0 [-4.9] 89.6 [-2.8] 66.9 [-8.0] 87.4 [-5.0]</td></tr><tr><td>Dynamic sparse (ours)</td><td colspan="2">73.3 [-1.6] 92.4 [ 0.0] 71.6 [-3.3] 90.5 [-1.9]</td></tr></table>

Peer review (iclr2019):
 Weaknesses: 1-The authors claim that: "Compared to other dynamic reparameterization methods that reallocate non-zero parameters during training, our approach broke free from a few key limitations and achieved much better performance at lower computational cost." => However, there is no quantitative experiments related to other dynamic reparameterization methods. There should be at least sparsity-accuracy comparison to claim achieving better performance. I expect authors compare their work at-least with with DEEP R, and NeST even if it is clear for them that they produce better results. 2-The second and fourth contributions are inconsistent: In the second one, authors claimed that they are the first who designed the dynamic reparameterization method. In the fourth contribution, they claimed they outperformed existing dynamic sparse reparameterization. Moreover, it seems DEEP R also is a dynamic reparameterization method because DEEP R authors claimed: "DEEP R automatically rewires the network during supervised training so that connections are there where they are most needed for the task, while its total number is all the time strictly bounded." 3- The authors claimed their proposed method has much lower computational costs, however, there is no running time or scalability comparison. Suggestions: 1-Authors need to motivate the applications of their work. For instance, are they able to run their proposed method on mobile devices? 2-For Figure 2 (c,d) you need to specify what each color is. 3-In general, if you claim that your method is more accurate or more scalable you need to provide quantitative experiments. Claiming is not enough. 4-It is better to define all parameters definition before you jump into the proposed section. Otherwise, it makes paper hard to follow. For instance, you didn*t define the R_l directly (It is just in the Algorithm 1).