Connectivity Matters: Neural Network Pruning Through the Lens of Effective Sparsity
Authors: Artem M Vysogorets
Julia Kempe
Venue: ICLR 2022 Submitted (2022)
Keywords: Neural Networks
Pruning
Sparsity

Abstract: Neural network pruning is a fruitful area of research with surging interest in high sparsity regimes. Benchmarking in this domain heavily relies on faithful representation of the sparsity of subnetworks, which has been traditionally computed as the fraction of removed connections (direct sparsity). This definition, however, fails to recognize unpruned parameters that detached from input or output layers of underlying subnetworks, potentially underestimating actual effective sparsity: the fraction of inactivated connections. While this effect might be negligible for moderately pruned networks (up to $10\times-100\times$ compression rates), we find that it plays an increasing role for thinner subnetworks, greatly distorting comparison between different pruning algorithms. For example, we show that effective compression of a randomly pruned LeNet-300-100 can be orders of magnitude larger than its direct counterpart, while no discrepancy is ever observed when using SynFlow for pruning (Tanaka et al., 2020). In this work, we adopt the lens of effective sparsity to reevaluate several recent pruning algorithms on common benchmark architectures (e.g., LeNet-300-100, VGG-19, ResNet-18) and discover that their absolute and relative performance changes dramatically in this new, and as we argue, more appropriate framework. To aim for effective, rather than direct, sparsity, we develop a low-cost extension to most pruning algorithms. Further, equipped with effective sparsity as a reference frame, we partially reconfirm that random pruning with appropriate sparsity allocation across layers performs as well or better than more sophisticated algorithms for pruning at initialization (Su et al., 2020). In response to this observation, using a simple analogy of pressure distribution in coupled cylinders from thermodynamics, we design novel layerwise sparsity quotas that outperform all existing baselines in the context of random pruning.

Under review as a conference paper at ICLR 2022
CONNECTIVITY MATTERS: NEURAL NETWORK PRUN- ING THROUGH THE LENS OF EFFECTIVE SPARSITY
Anonymous authors Paper under double-blind review
ABSTRACT
Neural network pruning is fruitful area of research with surging interest in high sparsity regimes. Benchmarking in this domain heavily relies on faithful repre- sentation of the sparsity of subnetworks, which has been traditionally computed as the fraction of removed connections (direct sparsity). This definition, however, fails recognize unpruned parameters that detached from input or output layers of underlying subnetworks, potentially underestimating actual effective sparsity: the fraction of inactivated connections. While this effect might be negligible for mod- erately pruned networks (up 10x-100x compression rates). we find that plays an increasing role for thinner subnetworks, greatly distorting comparison between different pruning algorithms. For example, we show that effective compression of randomly pruned I LeNet-300-100 can be orders of magnitude larger than its direct counterpart, while no discrepancy is ever observed when using SynFlow for pruning (Tanaka et al. 2020). In this work, we adopt the lens of effective sparsity reevaluate several recent pruning algorithms on common benchmark architec- tures (e.g., LeNet-300- 300-100, VGG-19, ResNet-181 18) and discover that their absolute and relative performance changes dramatically in this new, and as we argue, more appropriate framework. To aim for effective, rather than direct, sparsity, we de- velop a low-cost extension most pruning algorithms. Further, equipped with effective sparsity reference frame, partially reconfirm that random prun- ing with appropriate sparsity allocation across layers performs as well or better than more sophisticated algorithms for pruning initialization (Su al. 2020). In response to this observation, using simple analogy of pressure distribution in coupled cylinders from thermodynamics, quotas that outperform all existing baselines in the context of random pruning.
design novel layerwise sparsity
INTRODUCTION
Recent successful advances of Deep Neural Networks commonly attributed to their high archi- tectural complexity and excessive size (over-parde (aver-arrmmtrizattoo)) (Denton et al. 2014 Neyshabur et al.] 2019 Arora al. 2018). Modern state-of-the-art architectures exhibit enormous parameter over- head, requiring prohibitive amounts of resources during both training and inference and leaving a significant environmental footprint (Shoeybi et al.) 2019). In response these challenges, much attention has turned to compression of neural networks and, in particular, parameter pruning. While initial approaches mostly focused on pruning models after training (LeCun al. 1990) Hassibi et al. 1993). contemporary algorithms optimize the sparsity structure of a network while training its parameters (Mocanu et al. 2018 Evei et al. (020)) or even remove connections before any training whatsoever (Lee et al. 2019 Wang et al. (020).
Compression rates usually considered the pruning literature usually fall between 10x and 100x of the size of the original model. However, as contemporary model sizes grow into the billions of parameters, studying higher compression regimes becomes increasingly important. Recently, new bold sparsity benchmark was set by Tanaka et al. (2020) with Iterative Synaptic Flow (SynFlow), a data-agnostic algorithm for pruning at initialization. Reportedly, is capable of removing all but only a few hundreds of parameters (a 100, 000 compression for VGG- 16) and still produce trainable subnetworks, while other pruning methods disconnect networks at much lower sparsity levels TTnaka et al. 2020). Related work by de Jorge al. (02T) proposes iterative version of

---

Under review as a conference paper at ICLR 2022
one-shot pruning algorithm, Single-shot Network Pruning (SNIP) (Lee et al. 2019). and evaluates it in a similar high sparsity regime, reaching more than 10, 000x compression ratio.
Effective sparsity. This increased focus on extreme sparsity leads us to consider what sparsity is meant to reprexent in neural networks and computational graphs at large. In the context of neural network pruning, sparsity to date is computed straightforwardyy as the fraction of removed con- nections (direct sparsity) and compression as the inverse fraction of unpruned connections (direct compression). We observe that this definition does not distinguish between connections that have actually been pruned, and those that have become effectively pruned because they have disconnected from the computational flow. In this work, we propose to instead focus effective sparsity- the fraction of inactivated connections, be through direct pruning or through otherwise disconnecting from either input output of a network (see Figure [ for an illustration).
In this work, we advocate that effective sparsity (effective compression) be used universally in place of its direct counter- part since it more accurately depicts what one would reason- ably consider the network's s sparsity state. Using the lens of ef- fective compression for benchmarking allows for fairer com- parison between different unstructured pruning algorithms. Note that effective compression is lower bounded by direct compression, which means that some pruning algorithms will give improved sparsity-accuracy trade-offs in this new frame- work. In Scction we critically recxamine a plethora of recent pruning algorithms for variety of architectures to find that, in this refined framework, conclusions drawn in previous works appear overstated or incorrect. Figure Figure sneak-preview of this effect for three ab-initio pruning algorithms: SynFlow Tanaka al. 2020), SNIP (Lee al. (019) and plain random pruning for LeNet-300-100 on MNIST. While SynFlow ap- pears superior to other methods when evaluated against direct compression, it loses its ad advantage in the effective framework. Such radical performance changes are partly explained by dif- fering gaps between effective and direct compression inherent to different pruning algorithms (Figure 2). We can see that significant departure between direct and effective compression kicks in at relatively low rates below 100x, making our work relevant in these moderate regimes. For example, using random pruning to compress LeNet-300-100 by 100x (spar- sity 99%) results in 1, 000000 effective compression; yet, moving the same number of parameters with SynFlow yields an unchanged 100x effective compression. What makes cer- tain iterative algorithms like SynFlow less likely to amass dis- connected edges? Section 3 we show that they are fortuitously designed to achieve close con- vergence of direct and effective sparsity, hinting that preserving connectivity is an important aspect in the strong performance of nigh-compression pruning algorithms (Tanaka et al., 2020 de Jorge et al. 2021). Moreover, the lens of effective compression gives access to more extreme compression regimes for some pruning algorithms,, which appear to disconnect much earlier when not accounting for inactive connections. For these high effective compression ratios all three pruning methods from Figure 2 perform surprisingly similar, even though they use varying degrees of information on data and parameter values.
Figure I: Pruning 11 edges from fully- fully-connected 21 21-edge network. Top: direct sparsity (11/21) does not account for disconnected edges (compression 21 21/10 2.1). Bot- tom: effective sparsity (16/21) ac- counts for the dashed connec- tions incident to inactivated neu- rons (yielding twice as large effec- tive compression 21 4.2).
Layerwise Sparsity Quotas (LSQQ) and Ideal Gas Quotas (IGQ). A recent thread of research by Frankle et al. (2021) and (Su et al. (2020) shows that performance of trained subnetworks pro- duced by algorithms for pruning at initialization is robust to randomly reshuffling unpruned edges within layers before training. This observation led to the conjecture that these algorithms essentially generate successful distributions of sparsity across layers, while the exact connectivity patterns are unimportant. In Section 4 reexamine this conjecture through the lens of effective sparsity, con- finm for moderate compression regimes (10x-100x) studied by Frankle et al. (202I) and Su et al.) 2020), but find the truth to be more nuanced higher compression rates. Nonetheless, this
2

---

Under review as a conference paper at ICLR 2022
sult highlights the importance of algorithms that carefully engineer layerwise sparsity quotas (LSQ) to obtain very simple and adequately performing pruning algorithms that are data- and parameter- agnostic. Another important motivation to search for good LSQ is that global pruning algorithms frequently remove entire layers prematurely (Lee et al.) 2020) (cf. layer-collapse (Tanaka et al.) 2020),, even before any significant differences between direct and effective sparsity emerge. Well- engineered LSQ could avoid this and enforce proper redistribution of compression across layers (see (Gale et al. 2019 Mocanu al. 2018 Evci et al. 2020) for existing baselines). In Section we propose a novel LSQ coined Ideal Gas Quotas (IGQ) by drawing intuitive analogies from physics. Effortlessly computable for any network- betwork-sparsity combination, IGQ performs similarly or better than any other baseline in the context of random pruning at initialization and of magnitude pruning after training.
10
Derse
101
SNIP
elfective comprooeies
10'
0.6
dinstt
10
0.4
10
SysFlow
0.2
Randoon
10
0.0
10'
10
comprescion
Compresiie
Figure 2: LeNet-300-100 trained on MNIST after pruning with SNIP, SynFlow and layerwise uni- form random pruning. Left: gaps between direct and effective compression. Right: SynFlow has better sparsity-accuracy trade-off than SNIP when plotted against direct compression (dashed), but against effective compression (solid curves fitted dots that represent inidvidual experiments). Dashed and solid curves coincide for SynFlow.
Effective pruning. Pruning to any desired direct sparsity is straightforward: one simply needs to mask out the corresponding number parameters from a network. Effective sparsity, unfortunately, is more unpredictable and difficult to control. In particular, several known pruning algorithms suffer from layer-collapse once reaching a certain sparsity level, leading to unstable effective sparsity just before the disconnection. As result, most pruning methods are unable to deliver certain values of effective sparsity regardless of how many connections are pruned. When possible, however, needs carefully tune the number of pruned parameters that effective sparsity lands near desired value. Scction[5] we suggest a simple extension to algorithms for pruning at initialization after training that helps bring effective sparsity close to any predefined achievable value while incurring costs that are at most logarithmic in model size.
Our contributions. In this study, we (i) clearly formulate and illustrate the importance of effective sparsity by reevaluating several recent pruming strategies; (ii) provide algorithms to prune according and compute effective sparsity; (iii) reconfirm the hypothesis from (Frankle al. 2021 in the new framework and design efficient layerwise sparsity quotas IGQ that perform consistently well across all sparsity regimes.
2 RELATED WORK
Neural network compression encompasses a number of orthogonal approaches such as parameter regularization (Lebedev Lempitsky 2016, Louizos et al. 2018), variational dropout (Molchanov
et al. 2017), vector quantization and parameter sharing (Gong et al. 2014: Chen et al. [015 Han al. 2016). low-rank matrix decomposition (Denton et al. 201 2014 Jaderberg et al. 2014), and knowl- edge distillation (Buciluă et al., 2006 Hinton et al. 2015). Network pruning, however, is by far the most common technique for model compression, and can be partitioned into structured (at the level of entire neurons/units) and unstructured (at the level of individual connections). While the former offers resource efficiency unconditioned on use of specialized hardware (Liu et al. 2019) and consti- tutes a fruitful research area (Li et al. 2017 Liu et al. 2017), focus the more actively studied
3

---

Under review as a conference paper at ICLR 2022
unstructured pruning, which is where differences between effective and direct sparsity emerge. In what follows we give a quick overview, naturally grouping pruming methods by the time they are applied relative to training (see (Frankle & Carbin 2019) and (Wang al. 2020 for similar taxonomy).
Pruning after training. These earliest pruning techniques were designed to remove the least "salient" learned connections without sacrificing predictive performance. Optimal Brain Damage (LeCun et al.) 1990) and its sequel Optimal Brain Surgeon (Hassibi et al. 1993) use the Hessian of the loss estimate sensitivity to removal of individual parameters. Hann al. (2015) popularized magnitude as simple and effective pruning criterion. It proved to be especially successful when applied alternately with several finetuning cycles, which is commonly referred as Iterative Mag- nitude Pruning (IMP), a modification of which was used by Franklle & Carbin (2019) to discover lottery tickets. Later, Dong et al. (2017) showed that magnitude- pruning minimizes lg distor- tion of each layer's s output incurred by parameter removal. Recently, [ee et al. (202T) extend this idea and propose Layer-Adaptive Magnitude-Ban -aased Pruning (LAMP), which approximately mini- mizes the upper bound of the &a distortion of the entire network. While equivalent to magnitude pruning within individual layers, LAMP automatically discovers state-of-the-ar layerwise sparsity quotas (see Section 4 that yield better performance (as function of direct compression) than ex- isting alternatives in the context of IMP.
Pruning during training. Algorithms in this category learn sparsity structures together with pa- rameter values, hoping that continued training will correct for damage incurred by pruning. To avoid inefficient prune-retrain cycles inherent to IMP, Narang et al. (2017) introduce gradual magnitude pruning over single training round. Subsequently, Zhu & Guptal (2018) modify this algorithm by introducing a simpler pruning schedule and keeping layerwise sparsities uniform throughout train- ing. Sparse Evolutionary Training (SET) (Mocanu et al.) 2018) starts with already sparse subnet- work and restructures it during training by pruning and randomly reviving connections. Unlike SET, Mostafa & Wang (2019) allow redistribution of sparsity across layers, while Dettmers & Zettle- moyer (2019) use gradient momentum as the criterion for parameter regrowth. Evci et al. (2020) rely on the instantaneous gradient to revive weights but follow SET to maintain the initial layerwise sparsity distribution during training. A different body of works tackle the general optimization prob- lem with an intractable to parameter sparsity constraint by designing and solving related continuous problems (Zhou et al. 2021; (Savarese et al. 2020 Kusupati et al. (020). For example, Continuous Sparsification (CS) by Savarese et al. (2020) uses a sigmoid of learnable continuous variables as mask values and applies I regularization, effectively forcing them to either 0 or 1 in training.
Pruning before training. Pruning at initialization is especially alluring to deep learning practi- tioners as promises lower costs of both optimization and inference. While this may seem too am- bitious, the Lottery Ticket Hypothesis (LTH) postulates that randomly initialized dense networks do indeed contain highly trainable and equally well-performing sparse subnetworks (Frankle & Carbin 2019). Inspired by the LTH, Lee al. (2019) design SNIP, which uses connection sensitivity as a parameter saliency score. Wang et al. (2020) notice that SNIP creates bottlenecks or even re- moves entire layers and propose Gradient Signal Preservation (GraSP) as alternative that aims to maximize gradient flow in a pruned network. de Jorge et al. (202T) improve SNIP by applying it iteratively, allowing for reassessment of saliency scores during pruning and helping networks stay connected at higher compression rates. A truly new compression benchmark was set by Tanaka al. (2020): their algorithm, SynFlow, iteratively prunes subsets parameters according to their & path norm and helps networks reach maximum compression without disconnecting. For example, SynFlow achieves non-random test accuracy on CIFAR-10 with 100, 000x compressed VGG-16, while SNIP and GraSP fail already at 100x and 1, 0000,, respectively. An extensive ablation study by Frankle et al. (02I) examines SNIP, GraSP and SynFlow within moderate compression rates (up to 100x) and reveals that performance of subnetworks produced by these methods is stable under layerwise rearrange prior to training. Later, this result was independently confirmed by Su et al. 2020) for SNIP and GraSP only. This observation suggests that these algorithms perform well as random pruming with corresponding layerwise quotas, putting the spotlight on designing competitive
LSQ (Mocanu et al. 2018 Gale et al. 2019 Lee al. 2021
4

---

Under review as a conference paper at ICLR 2022
3 EFFECTIVE SPARSITY
In this section, present comparisons of variety of pruning algorithms under the lens of effective compression. To illustrate the striking difference between direct and effective sparsity and expose the often radical change in relative performance of pruning algorithms when switching from the former to the latter, we evaluate several recent methods (SNIP. GraSP, SynFlow, LAMH c and SNIP-iterative) and random pruning with uniform sparsity distribution across layers in both frameworks, Our experiments encompass modern architectures on commonly used computer vision benchmark datasets: LeNet-300- 100 (Lecun et 1998) on MNIST, LeNet-5 (Lecun et 1998) on CIFAR-10, VGG-19 (Simonyan & Zisserman 2015) on CIFAR-100) and ResNet-18 (He et al., 2016 on Imayema We place results VGG-16 (Simonyan & Zisserman 2015) on CIFAR- 10 in Appendix B as they closely resemble those of VGG-19. Further experimental details are presented in Appendix A
Notation. Consider L-layer neural network f(@;z) with weight tensors O = (O,) for Le E L]. A subnetwork specified by set binary masks that indicate unpruned parameters Mr E {0, 1110ol, With M = {M&)]/ is given by f(O @ M; where O indicates pointwise multiplication. Note that biases and batch normalization parameters (loffe & Szegedy 2015) are normally considered unprunable. Direct sparsity, the fraction of pruned weights, is given by s(M) =
Me De Mel and direct compression rate defined as (M))
Figure 3 reveals that different algorithms tend to develop varying amounts of inactive connections. For example, effective compression of subnetworks pruned by LAMP consistently reaches 10x of their direct compression across all architectures, at which point at least nine in ten unpruned connections are effectively inactivated. Other methods (c.g., SNIP on VGG-19) remove entire layers early on, before any substantial differences between effective and direct compression emerge. SNIP- iterative and especially SynFlow, however, demonstrate truly unique property: subnetworks prumed by these two algorithms exhibit practically equal effective and direct compressions, and, in the of SynFlow, disconnect only at very high compression rates. What makes them special? Both SynFlow and SNIP-iterative 300 iterations, respectively. SynFlow ranks connections by their & path norm (sum of weighted paths passing through the edge, where the weight of path is the product of magnitudes of weights of its edges). SNIP uses connection sensitivity scores from Lee et al. (2019) measure, where C is the loss function. Both these pruning criteria assign the lowest possible score of zero to inactive connections, scheduling them for immediate removal in the subsequent pruning iteration. Thus, by virtue of their iterative design, these two methods produce subnetworks with little to difference between effective and direct compression. They fortuitously designed to prune inactivated edges, which might explain their high-compression performance.
multi-shot pruning algorithms that remove parameters over 100 and
ac
O as saliency 86
LoNes-00--100
LoNi--5
VOG-IPACIFAN (00)
Re 11 (TinstrgeNen)
16
11P
Lifective conpresion
10
11F
10'
107
104
101
10
180
107
102
10
100
10
10
10
10
10
10+
(0)
101
10*
Direct compression
Direct compesstion
Dompeesoi
Dinnt conpansae
LAMP
SynFlow
GraSP
SNIP itrative
SNIP
Random
Figure 3: Effective versus direct compression across different pruning methods and architectures (curves and bands represent min/average/max across 3 seeds where subnetworks disconnect last among total of seeds).
aas a state-of-the-art representative of magnitude pruning after training and, in particular, lottery tickets Frankle & Carbin (019)) as representative of methods concerned with Icarnable sparsity
5

---

Under review as a conference paper at ICLR 2022
Tanaka et al. (2020) compare SynFlow to SNIP and GraSP using direct sparsity, claiming it vastly superior in high compression regimes. However, pruning methods that generate large amounts of inactivated connections are clearly at significant disadvantage in the original direct framework. that the performance gap between SynFlow and other methods shrinks on all tested architectures under effective compression. The most dramatic changes are perhaps evident with LeNet-300-100 where SynFlow significantly dominates both SNIP and GraSP in direct comparison, but becomes strictly inferior when taken to the more telling effective compression. On the other hand, differences are not as pronounced on purely convolutional architectures such as VGG-19 19, and ResNet-18. 18. Feature maps convolutional layers are connected via groups of several parameters (kernels), making them more robust to inactivation compared to neurons in fully-connected layers.
Computing effective sparsity: In advocating the use effective sparsity, we must make sure that can be calculated efficiently. We propose easily computable approach leveraging SynFlow. Note that a connection inactive and only it is not part of any path from input to output. Assuming that unpruned weights non-zero, this is equivalent to having zero & path norm. Tanaka et al. 2020 observe that path norms can be efficiently computed with one pass on the all-ones input as 0 where R 1 (' o M, 1) and f' is the linearized version of the original network f. For deep models, rescaling of weights is required to avoid numerical instability (Tanaka et al.) 2020).
LeNe1-300-10 (MNIST)
LeNes- (CIFAR-10)
0.8
0.9
0.7
0.7
0.5
0.5
0.3
0.2
0.1
0.1
10'
10'
10
10
VGG-19 (CIFAR-100)
RoNNd-18 (Taylmgg
0.7
0.6
0.5
0.4
0.4
0.3
0.3
0.2
0.1
10 10"
10
10
10
10
10'
10'
10'
10'
10
Comprossion
Cumpression
LAMP
GnSPP
SNIP-iccrative
SNIP
compnesiun
dinect compresson
Figure 4: Test accuracy (min/average/max) of subnetworks trained from scratch after heing pruned by different algorithms plotted against direct (dashed) and effective (solid) compression. Dashed and solid curves overlap for SynFlow and SNIP-iterative. Solid curves are fitted to scatter data (not shown for clarity of the presentation) in Figure
4 LAYERWISE SPARSITY QUOTAS (LSQ) AND A NOVEL ALLOCATION METHOD (IGQ)
Inspired by Frankle et al. (2021) and Su et al. (2020), we wish to confirm that SNIP, GraSP, and SynFlow work better than random pruning with corresponding layerwise sparsity allocation.

---

Under review as a conference paper at ICLR 2022
While Frankle et al. (2021) and Su et al. (2020) only considered moderate compression rates up to x00x and used direct sparsity as a reference frame, we reconfirm their conjecture in the effective framework and test it across the entire compression spectrum. We generate and train two sets of subnetworks: (t) pruned by either SNIP, GraSP, and SynFlow (original), and (ii) randomly pruned while preserving layerwise sparsity quotas provided by each of these three methods (random).
Our results in Figure Bauue agree with observations made by Frankle et al. (2021) and et al. 2020); in the 10x-100x compression range, all three random pruning algorithms perform similarly (LeNet- 300-100, VGG-19) or better (ResNet-18) than their original counterparts. Effective sparsity allows us to faithfully examine higher compression, where the evidence is more equivocal. Similar pat- terns are still seen on ResNet- 18; however, the original SNIP and GraSP beat random pruning with corresponding layerwise sparsities by a wide margin starting 100x compression on LeNet-300- 100. Random pruning associated with SynFlow matches original SynFlow on the same network for longer, up to 1, x00x compression. On VGG-19, SynFlow bests the corresponding random pruning from about 500 compression onward, while the original SNIP suffers from disconnection early on together with its random variant. Despite these nuances in the high compression regime, random pruning with specific layerwise sparsity quotas fares extremely well in the moderate sparsity regime (up to 99%) and even competitive to full-fledged SynFlow (see Figure ( Therefore, random pruning can be cheap and competitive alternative to more sophisticated and resource-consuning algorithms. Random methods from Figure 5 however, still require running SNIP, GraSP, or Syn- Flow to identify appropriate sparsity quotas and thus are just as expensive. Furthermore, sparsity distributions inherited from global pruning methods frequently suffer from premature removal of entire layers (e.g., SNIP on VGG-19), which is undesired. Can we engineer readily computable and consistently well- werl-performing sparsity quotas?
Lehies 300. (INIST)
VGG 19 (CIFAR-ICC 100)
KeoNes 18 (Egglnggce)))
1.8
066
0.6
0-4
0.4
0.2
0.5
SynFlow
GrsPP
SNIP
original
random
Figure 5: Original methods for pruning at initialization (solid) and random pruning with correspond- ing layerwise sparsity quotas (dashdot). Test accuracy of the unpruned network is shown in grey.
To our knowledge, there are only a few ab-initio approaches in the literature to allocate sparsity in principled fashion. Uniform is the simplest solution that keeps sparsity constant across all layers. Gale et al. (219)) give a modification (denoted Uniform+ following Lee et al. (00II) ) that retains all parameters the first convolutional layer and caps sparsity of the last colle-co layer at 80%. A more sophisticated approach, Tydös-Reeyi-Koee Kernel (ERK), sets the density a convolutional layer with kernel size x h, fan-in nin and fan-out That proportional to (w+h+t7tm mlaa) / //w h-rin -oau)) Although originally used as a sparsity distribution schema for methods with dynamic sparse structres (SET by (Mocanu et al. 2018) and RigL by Evci et al. (2220)) we follow (Lee et al. [02I]) and use ERK as a baseline sparsity distribution for toarse-to-spare training with a fixed subnetwork topology. The last two approaches are unable to support the entire range sparsities: Uniform+ can only achieve moderate direct compression because of the prunability constraints on its first and last layer, while both direct and effective sparsity levels achievable with ERK are often lower bounded. For example, the density of certain layers of VGG-16 set by ERK exceeds I when cutting less than 99% of parameters, unless excessive density redistributed. We suggest formal definition for layerwise sparsity quotas to guide future research into sparsity allocation and avoid problems that riddle Uniform+ and ERK.
Definition 1 (Layerwise Sparsity Quotas). A function Q: 10 + [0, mapping a target sparsity layerwise sparsities {se)fm is called Layerwise Sparsity Quotas (LSQ) if satisfies
7

---

Under review as a conference paper at ICLR 2022
the following properties: (i) total sparsity: for any [0.1]. $ Le Σ, Se(ee) and (ii)
monotonicity: [Q(s1)le E (2(se for any f [L] whenever $1 S 82.
We now present Ideal Gas Quotas (IGQ), formula for sparsity allocation that satisfies Definition
and outperforms the above mentioned baselines. while faring very well (over effective sparsity)
compared to the allocation quotas derived from sophisticated pruning methods such as SynFlow. To develop an intuition on what constitutes a good LSQ construction, we study the layerwise sparsities induced by contemporary pruning algorithms such as LAMP and SynFlow, As rule, they (i) prune larger layers more aggressively than smaller layers, i.e., [[(s]] S [Q()]]r whenever | S |0p| for any E [0, 1], and (di) avoid premature removal of entire layers, i.e., [Q(s)]e 1 and only = - (see Appendix [ for illustration).
Our approach is interpret compression of layers within network as compression of stacked cylinders of unit volume filled with gas, where the height of the cylinder is proportional to the number of parameters in that layer. We then use the Ideal Gas Law to derive the compres- sion of each of the stacked coupled cylinders. More formally, model each layer & E [L] as cylinder height H₃ = [0.] and cross-section area St = |0,1-1, Further, assume that these stacked weightless cylinders with frictionless pistons and filled with the same amount of ideal gas v are thermodynamic equilibrium with common pressure Po = and temperature T. Isother- mal compression of this system using external force F is governed by the Ideal Gas Law: PIV = vRT = VoVo. where P/ = F/S: + Po. Vi = Syhe, and h2 is its new compressed height. Then, PoH,S = (F/Se + So) or, equivalently. He/he Interpreting He/h, as compression ratio of layer f, we arrive at compression quotas (F[0 (or sparsity quotas {1 sparsity of the network. Given target sparsity & E [0, 1]. the needed value can simply be found with binary search to any desired precision. Our IGQ clearly satisfies all conditions of Definition and the other properties identified above.
(Poo.) +1 F +
1)- parameterized by the force F controlling the overall
(RgglaggeNe))
0.5
0.6
0-4
044
Top
0.2
0.8
10'
600
18'
600
Ellesinc oxspronkes
Ellectre coepaneee
(naudon)
SynFlow (randor))
(random)
Uniform
Uniforn (mndom)
SynFlow (original)
dense
Figure 6: Test performance of trained subnetworks after random pruning with different layerwise sparsity distributions. Original SynFlow (black) is shown for reference.
We now evaluate IGQ for random pruning, comparing it against ERK, Uniform, Uniform+, as well as random pruning with the sparsity quotas induced by SynFlow for reference (Figure Across all architectures, random pruning with IGQ and SynFlow sparsity quotas are almost indistinguishable from each other, suggesting that IGQ successfully mimics the quotas produced by SynFlow, which requires substantial effort compute. While ERK sometimes exhibits similar (ResNet-18) or even better (VGG-19 compressed to 1, x000 or higher) performance than IGQ, it yields invalid layerwise sparsity quotas when removing less than 98% and 99% of parameters from ResNet- and VGG- 19, respectively, thus failing satisfy Definition 1. In the moderate sparsity regime (up 99%), subnetworks pruned by IGQ reach unparalleled performance after training. Therefore, judging by a tripartite criterion of test performance, compliance with Definition and computational efficiency, IGQ beats all considered baselines.
In Appendix C test IGQ in the context of magnitude pruning after training. Here, performance of IGQ practically coincides with that LAMP, making it the only known LSQ to consistently perform best and competitive method for layerwise sparsity allocation.
8

---

Under review as a conference paper at ICLR 2022
5 EFFECTIVE PRUNING
Unlike pruning to a target direct spansity, pruning to achieve a particular effectivve sparsity can be non-trivial. Here, we present an extension algorithms for pruning at initialization or after training that achieves this goal efficiently, when possible (see Figure
Ranking-basee pruning. Algorithms like GraSP, Syn- Flow, and LAMP rank parameters by some notion of importance to guide pruning. When such a ranking R: @ + IR is available, the naive solution is to iter- through all scores in order, considering each as a po- tential pruning threshold and recording effective spar- sity of the corresponding subnetwork with parameters {O E O: R(O] < if removed. While provably identi- fying the optimal threshold that yields a subnetwork with effective sparsity as close the desired value possi- ble, this approach requires O(@)) prune-evaluate cycles, which is unreasonable for most contemporary architec- tures. To achieve an efficient overhead of O(log (@l) at the price of minor inaccuracy, we utilize binary search for the cut-off' threshold instead, leveraging the follow- ing monotonicity property: given two pruning thresholds t1, t2 E R and corresponding subnetworks S1, S2, we have t S tz if and only if S2 S S1, which implies S EfffectiveSppariit((S)) (note that in general Sparsity(S1) I (parsity(S2) does not imply the last inequality above). Thus. binary search will branch in the correct direction. In Appendix D inspired by the performance of random pruning as presented in Section 4 rithm to allow for effective random pruning where parameter rankings are not available.
10"
Effeetive compeeiionn
10"
04"
LAMP
Rendorn (Ihiienn)
Kendorn (Symillow)
ollastic pousing
10
10*
16
Target compressiio
Effective compression pro- duced by regular (dashdot) and ef- fective (solid) pruning on ResNet-18 18 ac- cording to ranking-based (left) and ran- dom (right) algorithms. Our procedures help pruning reach target effective spar- sity, falling short only when the subnet- work on the brink of disconnection.
Figure 7:
EffectiveSparsityy55
we describe modification of this algo-
DISCUSSION
In our work, we argue that effective sparsity (effective compression) the correct benchmarking measure for pruning algorithms since it discards effectively inactive connections and represents the true remaining connectivity pattern. Moreover, effective sparsity allows us to study extreme com- pression regimes for subnetworks that otherwise appear disconnected at much lower direct sparsi- ties. We initiate the study of current pruning algorithms in this refined frame of reference and rectify previous benchmarks. To facilitate the use of effective sparsity in future research, describe low- cost procedures to both compute and achieve desired effective sparsity when pruning. Lastly, with effective sparsity allowing to fairly zoom into higher compression regimes than previously possi- ble, we examine random pruning with prescribed layerwise sparsities and propose our own readily computable quotas (IGQ) after establishing conditions reasonable LSQ should fulfill. We show that IGQ, while allowing for any level of sparsity, is more advantageous than all existing similar baselines (Uniform, ERK) and gives comparable performance sparsity quotas derived from more sophisticated and computationally expensive algorithms like SynFlow.
Limitations and Broader Impacts: We hope that the lens of effective compression will spur more research in high compression regimes. One possible limitation is that it is harder to control effective compression exactly. In particular using different seeds might lead to slightly different effective compression rates. However, these perturbations are minor. Another small limitation is that our ef- fective pruning strategies are not immediately applicable to some algorithms that prune while train- ing (e.g., RigL (Evci et al. 2020 However, in most cases our approach can be adapted. Lastly, one might argue that for some architectures accuracy drops precipitously with higher compression thus making very sparse subnetworks less practical. We hope that opening the study of high com- pressions will allow to explore how to use sparse networks as building blocks, for instance using the power of ensembling. Our framework allows principled study of this regime.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan, On the optimization of deep networks: Implicit acceleration by overparameterization In Andreas Krause and Jennifer Dy (eds.), 35th Interna- tional Conference on Machine Learning, ICML 2018, 35th International Conference on Machine Learning, ICML 2018, pp. 372-389, International Machine Learning Society (IMLS), January 2018.
Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizil. Model compression. Proceed- ings of the 12th ACM SIGKDD International Conference Knowledge Discovery and Data Min- ing, KDD '06, pp. 535-541, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933395.
Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In Francis Bach and David Blei (eds.). Proceedings of the 32nd International Conference on Machine Learning. volume 37 of Proceedings of Machine Learning Research, pp. 2285-2294, Lille, France, 07-09 Jul 2015. PMLR.
Pau de Jorge, Amartya Sanyal, Harkirat Behl, Philip Torr, Grégory Rogez, and Puneet K. Dokania. Progressive skeletonization: Trimming more fat from network at initialization. In International Conference on Learning Representations, 2021.
Emily L Denton, Wojeiech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. CoRR, abs/1 9077 004400, 2019.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 2943-2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neu- ral networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural net- works initialization: Why are we missing the mark? In International Conference on Learning Representations, 2021.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv e-prints, arXiv: 1902..9990097444 2019.
Yunchao Gong, Liu Liu, Ming Yang, and Lubomir D. Bourdev. Compressing deep convolutional networks using vector quantization. CoRR, abs//141.6615, 2014.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffiman coding. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
10

---

Under review as a conference paper at ICLR 2022
B. Hassibi, D.G. Stork, and G.J. Wolff. Optimal brain surgeon and general network pruning. In IEEE International Conference on Neural Networks, pp. 293-299 vol.1, 1993.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in a neural network, In NIPS Deep Learning and Representation Learning Workshop, 2015.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei (eds.). Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 448 456, Lille, France, 07-09 Jul 2015. PMI.R
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. In Proceedings of the British Machine Vision Conference. BMVA Press, 2014.
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade. and Ali Farhadi. Soft threshold weight reparameterizzation for learnable sparsity. In Proceedings of the International Conference on Machine Learning, July 2020.
Vadim Lebedev and Victor Lempitsky. Fast convnets using group-wise brain damage. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2554-2564, 2016.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- learning applied to document recog- nition. Proceedings of the IEEE, 86(1 (1:2772228-,,,, 1998.
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, pp. 598-605. Morgan Kaufmann, 1990.
Jacho Lee, Sejun Park, Sangwoo Mo, Sungsoo Ahn, and Jinwoo Shin. Layer- adyeriad sparsity for the magnitude-basee pruning. In International Conference Learning Representations, 2021.
Namhoon Lee. Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: single-shot network pruning based on connection sensitivity. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Torr. A signal propa- gation perspective for pruning neural networks at initialization. In International Conference on Learning Representations, 2020.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang. Shoumeng Yan, and Changshui Zhang. Learn- ing efficient convolutional networks through network slimming. In 2017 IEEE International Conference on Computer Vision (ICCV), pp. 2755-2763. 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In ICLR, 2019.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through lo regularization. In International Conference on Learning Representations, 2018.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H. Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science. Nature Communications, 911):2383. 2018.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pp. 2507. PMLR, 06-11 Aug 2017.
11

---

Under review as a conference paper at ICLR 2022
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In Proceedings of the 36th International Conference on Machine Learning. pp. 4646-4655. PMLR, 2019.
Sharan Narang, Greg Diamos, Shubho Sengupta, and Erich Elsen. Exploring sparsity in recur- rent neural networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-paramettrization in generalization of neural networks. In International Conference Learning Representations, 2019.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 11380-11390. Curran Associates, Inc., 2020.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model par- allelism. CoRR, htss/199.008053 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceed- ings, 2015.
2015.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao. Liwei Wang, and Jason D Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10390-20400
Curran Associates, Inc., 2020.
Hidenori Tanaka, Daniel Kunin, Daniel Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In H. Larochelle, M. Ranzato, R. Had- sell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 6377-6389, Curran Associates, Inc., 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
Xiao Zhou, Weizhong Zhang, Hang Xu, and Tong Zhang. Effective sparsification of neural networks with global sparsity constraint. In Proceedings of the IEEE//VE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3599-3608, June 2021.
Michael Zhu and Suyog Gupta. To prune, not to prune: Exploring the efficacy of pruning for model compression. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Workshop Track Proceedings. OpenReview.net, 2018.
12

---

Under review as a conference paper at ICLR 2022
A EXPERIMENTAL DETAILS
Our experimental work encompasses five different architecture-dataset combinations: LeNet-300- 100 (Lecun et al. 1998) on MNIST (Creative Commons Attribution-hhare Alike 3,0 license), LeNet- (Lecun et al., 1998) and VGG-16 (Simonyan Zisserman 2013) on CIFAR-10 10 (MIT license), VGG-19 (Simonyan & Zisserman 2015) CIFAR-IOW (MIT license), and ResNet-18 (He al., 2016 on TinylmageNet (MIT license). Following Frankle et al.) (202T), we do not reinitialize sub- networks after pruning (we revert back to the original initialization when pruning pretrained model by LAMP). We use our own implementation of all pruning algorithms in TensorFlow except for GraSP. for which we use the original code in PyTorch published by Wang et al. (2020). All runs were repeated 3 times for stability of results. Training was performed on an internal cluster equipped with NVIDIA RTX-8000, NVIDIA V-100, and AMD MI50 GPUs. Hyperparameters and training schedules used in our experiments are adopted from related works and are listed in Table We apply standard augmentations to images during training. particular, we normalize examples per-channel for all datasets and randomly apply: (i) shifts by at most 4 pixels in any direction and horizontal flips (CIFAR-10, CIFAR-I00, and TinylmageNet, or (ii) rotations by up to degrees (MNIST).
Table I: Summary of experimental work. All architectures include batch normalization layers fol- lowed by ReLU activations. Models are initialized using Kaiming normal scheme (fan-avg) and optimized by SGD (momentum 0.9) with a stepwise LR schedule (10x drop factor applied on spec- ified drop epochs). The categorical cross-entropy loss function is used for all models.
Model
Epochs
Drop epochs
Batch
LR
Decay
Source
LeNet-300-100
160
41/83/125
100
0.1
5e-4
Lee et al.
2019
LeNet-5
307
76/153 /20
128
0.1
5e-4
Lee et al.
2019
VGG-16
160
80/120
128
0.1
le-4
Frankle et al. 2022
VGG-19
160
80/120
128
0.1
5e-4
Wang al. (2020)
ResNet-18
200
100/150 150
256
0.2
1e-4
Frankle et al.
2021
B EXPERIMENTS WITH VGG-16
In Figure 8 we display the results of our experiments with VGG-16 on CIFAR-1O, As argued in Section higher sparsities are required for purely convolutional architectures (such as VGG-16) to develop inactive connections since feature maps are harder to disconnect. At the same time, several algorithms (SNIP, SNIP-iterative GraSP) suffer from layer-collapse at modest sparsities (99.9% or less) and, hence, fail develop significant amounts of inactive parameters. For this reason, as evident from Figures(]44 and VGG- arguably showcases the least differences between effective and direct compression among all tested architectures.
compoosion
10
0.8
tn"
Test accorncy
30
10"
10
0.2
10
10'
10'
10
10"
10'
10'
10'
comgression
Cumprosson
LAMP
SynF low
GraSP
SNIP-iterative
SNIP
Random
Dense
vs, direct compression
offective compression
Figure 8: Left: effective versus direct compression of VGG-16 when pruned by different al algorithms. Right: test accuracy (min/average/max) of VGG- 16 trained from scratch after being pruned by dif- ferent algorithms plotted against direct (dashed) and effective (solid) compression. Dashed and solid curves overlap for SynFlow and SNIP-iterative.
13

---

Under review as a conference paper at ICLR 2022
C FURTHER ANALYSIS OF IGQ
To guide the design of new LSQ, take closer look at the layerwise compression quotas arrived at by successful global pruning algorithms such as SynFlow and LAMP. As mentioned in Section and as evident from Figure these methods prune larger, parameter-heavy layers more aggressively than smaller layers. Together with the other desired properties discussed Section this observation partly motivates the design of Ideal Gas Quotas (IGQ), where the number of parameters in the layer corresponds to the height of the cylinder. is surprising how closely the sparsity quotas achieved by IGQ resemble those of SynFlow considering that they describe physical process (Figure
SynFlow
Ideal Gas Quocas (vurs)
LAMP
layer 0.73%%
10'
1.36%
Layenitle compresion (LeNee
layer 3.89%
byyor
10'
bayer 77.71%
1n
10
16
10
10
100
10
10
10
10
10
10
100
layer 1: 0.001%
boyer 0.03%
10'
Jayer 2: 0.25%
byyer 3: 0,5%
layer 1.0%
Layeretie compresson
100
layer 5: 2.0%
laper 6:.0.0%%
10'
Jayer 71:4.01%
Jayer 8:3.02%
00'
keyer 9: 16.01%
beyer 16.00%
leyer II: 16683%
layer 16.08%
Jayer 13: 16.03%
10"
10'
10
10
10"
10
10
10
10
10"
10'
10
10
10
10
Ovcrall compeesssion
comprossion
Ovenill compressio
Figure 9: Layerwise direct compression quotas of LeNet-5 (top) and VGG-16 (bottom) associated with SynFlow (left), our IGQ (middle), and LAMP (right). Percentages indicate layer sizes relative to the total number of parameters; colors are assigned accordingly from blue (smaller layers) to red (larger layers). Curves of LAMP and SynFlow end when the underlying network disconnects.
In addition to the ab-initio pruning experiments in Section 4 we test IGQ in the context of mag- nitude pruning after training. In this set experiments, we pretrain fully-dense models and prune them by magnitude using global methods (Global Magnitude Pruning, LAMP) layer-by-layer respecting sparsity allocation quotas (Uniform, Uniform+, ERK, and IGQ). Then, we revert the un- pruned weights back their original random values and fully retrain the resulting subnetworks to convergence. Results are displayed in Figure i0 the framework of effective compression. Overall, our method for distributing sparsity in the context of magnitude pruning performs consistently well across all architectures and favorably compares to other basclines, especially in moderate compres- sion regimes of 100x or less. Even though Global magnitude pruning can marginally outperform IGQ, it is completely unreliable on VGG-19. ERK appears slighly better than IGQ on VGG-19 19 and ResNet- 18 at extreme sparsities, however, it performs much worse on LeNet-300- 100 and has other general deficiencies as we discussed in Section [ The closest rival of IGQ is LAMP, which performs very similarly but is still unable to reach IGQ's performance on VGG- 19 and ResNet- 18 moderate compression regimes. Note, however, that all presented methods require practically equal compute and time; thus, the evidence in Figure 10 not meant to advertise IGQ as a cheaper alternative to LAMP but rather illustrate the effectiveness of IGQ
14

---

Under review as a conference paper at ICLR 2022
LeNet-300- 100 (MNIST)
L (CIFAR-10)
1.0
849
666
0.8
660
Test socuracy
8.57
0.6
0:50
0.4
0.4
0.2
0.0
0.0
10
10"
10
10
10
10
10
10"
(CIFAR-100)
ResNet-18 (TinylmaeeNet)
0.6
0.6
Top-1 test axcurccy
0.45
0.900
0.4
0.90
0.2
0.0
0.0
10
10'
10'
10"
10²
10"
10'
10"
10"
10"
10
Effcctive compression
Effective compression
Global
ERK
LAMP
Unifbrss
Unifoom
Figure 10: Test performance of retrained subnetworks after pruning with different magnitude-baat based methods. Uniform+ is not shown for LeNet-300-10 100000000000000000000000 since it is designed for convolutional networks.
D EFFECTIVE RANDOM PRUNING
In Section we saw that random pruning with carefully crafted layerwise sparsity quotas Q: [0, 1] 0, _ fares well (especially in the framework of effective sparsity) with more sophis- ticated pruning methods, proving to be cheaper and simpler alternative. Effective random pruning as straightforward as binary search with ranking-based methods (Section 5) because, for any two subnetworks S and S2. Sparsity(S,) < Sparsity(S}) does not imply EffectiveSparsity(S)) < EffectiiesSparsitySS (S2), and random pruning is unlikely to produce a neat chain of embedded subnet- works like ranking- based pruning in Section 5
Algorithm 1: Approximate Effective Random Pruning
Input: Desired effective sparsity LSQ function Q: [0, 1] + 00, 1]
i +- 0; + [+]; ( t 1; (2) t- 0: Pe, Ue O for all f e [4];
while j - - do
m < + (sel/=1 + Q(m θ e|-;;
T < RandomSclect(from U, Pt. size 0 11-101111100 |U]|(221)) for all é [4];
Mj < CreateMask (pruneed pruned- = θ, \ [Ue \ T7), unpruned = U₁ Te) for all e E [Z]]
Edfecttivepparssty (Mr)) < s then
U²= Ue T. for all [L]; M() (Melk-ni m:
else
Pt - Pt P Te for all / [L; (2) + (Molle1s + m,;
end
end
Return: Masks (!) with EffeectiveSpparityyM/ii (M))tttyy(()) and | = 10 [(()))))
15

---

Under review as a conference paper at ICLR 2022
To circumvent this issue, we design an improved algorithm that produces embedded subnetworks on each iteration, allowing binary search to work (see Algorithm [ Starting from the extreme subnetworks S1 (fully-dense, corresponding to masks M and S2 (fully-sparse, corresponding masks M we narrow the sparsity gap between them while preserving S2 S1 so that EfffectiveSpariit(551 I EffectiieSparsiiy((S)) For each layer, we keep track of unpruned con- nections Ug of S and pruned connections Pt S2, randomly sample parameters T, from Ue n Pr according to Q and form another network S by pruning out U Te from S1 (or, equivalently, reviving in S2). Depending on where effective sparsity of S lands relative to target 8, we assign S to either S or S2 and branch. Since connections to be pruned from S₁ (or revived in S2) chosen randomly at each step, weights within the same layer have equal probability of being pruned. Once S and S2 only parameter away from each other, the algorithm returns S1, yielding a connected model.
16


Reviews:
[{"review_id": "wH1dZtTylC", "reviewer": "Reviewer_B6nv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While indirect pruning is a reasonably known phenomenon, it is an interesting question to see whether it can give us any insights when comparing various pruning methods. Unfortunately, this paper doesn't do a thorough job doing that due to choice of baselines and poor motivation of extreme pruning regime:\n\n- I am surprised to see LeNet-300-100 as baselines here. I do not want to be the \"show me imagenet results\" reviewer, but I feel the choice of MNIST, and LeNet architectures are not justified here. Indirect pruning happens in extreme pruning regimes and I am assuming we care about that for very, very large networks. LeNet-300-100 is tiny and does not have convolutions, so is this a good baseline to draw conclusions from?\n- In the introduction, the authors do say that typical compression rates are 10x (0.9 pruning) and 100x (0.99 pruning) and motivate extreme pruning because of models with billions of parameters, yet their biggest models are ResNet-18 and VGG-19, where indirect pruning does not seem to be as big of a problem anyway.\n- Overall, the authors should do a better job motivating extreme pruning regimes. Pruning is interesting because we think models are over-parameterized, and we can get \"comparable performance\" while pruning away a good portion of parameters. However, the performance in this extreme regime is very poor, and the architectures are simply \"trainable\". So why is this an interesting problem to look at?\n\n**Structured pruning and CNNs**\n- I think the authors should also clarify the link between indirect pruning and structured pruning. Isn't the phenomena described by the authors the intended behaviour in structured pruning? It would be great if authors could also compare with structured pruning methods but I think at least the link between the two should be discussed in the paper.\n- The authors do not discuss what happens to the disconnected neurons as a result of indirect pruning. Can you set their value to zero (i.e. actually prune them)? Can their value always be fused into the next layer? or perhaps into the batch norm parameters? \n- The authors also don't discuss convolutional networks in details. I'm assuming indirect pruning is less of a problem there because you'd have to prune an entire channel to have indirect pruning. Given that most of our commonly used architectures and other pruning baselines use CNNs it seems crucial to have it analysed in detail and not rely on MLPs to make conclusions\n\n**Layerwise Sparsity Quotas (LSQ) and allocation method IGQ**\n\nI don't understand the Ideal Gas Law approach at all! What is the motivation for borrowing this from thermodynamics? What is the justification that neural networks behave like gasses? It is one thing to mention this in passing as an inspiration source, but when you go as far as mapping a neural network to a system in thermodynamic equilibrium, the height of a cylinder to the number of weights, and pruning to applying an external force to then you should provide better justifications. Moreover, the final derivation for prune ratio of each layer is $F | \\Theta _l | + 1$. There are two things I don't understand about this: (1) How is $F$ related to the desired pruning target? The authors say $F$ can be found via a binary search from pruning target but do not elaborate. (2) No matter how F is found I'm assuming it's a global value and not a per-layer one. Doesn't this reduce the formula to simply applying pruning uniformly??\n\n**Other things**\n- The authors use VGG19. I have seen different variants of VGG-19 for non-imagenet datasets. In Some variants there's a single dense layer after convolutional layers, and in some other variants there are multiple dense layers. Could the authors confirm which architecture they've used? This makes a big difference in prunability of the network and I'm curious to know if the indirect pruning is mostly happening in the final dense layers or in convolutions as well.\n- In the discussion section the authors argue that \"effective compression\" is the \"correct\" measure for pruning algorithm. I think that's a strong claim that's not well supported in the paper. You should at least clarify that it's aimed at extreme pruning regime (and probably non CNN based architectures?\n- The caption in Figure 2 says \"SynFlow has a better sparsity-accuracy tradeoff than SNIP\" Isn't the opposite true? I guess it's a typo\n- In figure 3, would things look too weird if you use the same units in the x axis and y axis so that we can compare the effect across architectures more easily?\n- In figure 5 could you rename \"Random\" to \"SNIP + RandomReshuffle\" or something. I think random is misleading here given that you're still applying layer-wise pruning ratios.", "summary_of_the_paper": "This paper highlights the fact that when doing unstructured pruning with extreme sparsity targets, we end up pruning entire neurons, which effectively detaches neurons from the input/output. The authors argue that the effective sparsity levels in these cases is higher than our target levels, and taking it into accounts exhibits differences between various pruning method that are otherwise not obvious. ", "summary_of_the_review": "This paper draws too many conclusions based on very small networks, datasets, and for a pruning regime where the network is simply trainable and has nowhere near the performance of the unpruned model. Overall I'm not convinced that \"effective pruning\", and extreme pruning gives us a enough insight to justify accepting the paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "VtEAE5EP-vK", "reviewer": "Reviewer_xGEE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The paper is clear and presents an interesting analysis about the discrepancy between pruning models and the resulting, underlying graph.\n* The detail and analysis is thorough, and the methodology is clear and concise. \n* The presented layer-wise sparsity quota Ideal Gas Quotas (IGQ) are interesting and produce compression distributions very similar to other methods (such as in Fig. 9). \nWeaknesses:\n* Many important points/figures in the paper are on very small datasets where models are extremely over-paramaterised. For example, Fig. 2 on MNIST would be much stronger, I think, on a slightly larger dataset (CIFAR-10, perhaps?)\n* Overall, I found the results largely focused on models that do not reach competitive performance on larger datasets. ResNet18 on TinyImageNet is shown, but it'd be nice if more modern architectures were shown. \n\nComments:\n* Would it be possible to adjust for effective FLOPs in a correctly pruned graph?\n* It would be cool to investigate various choices and their impact on sparsity/effective sparsity during pruning. For example, I imagine models with residual connections will have slightly different dynamics. \n* I'd be interested in a bit of a comparison of different model architectures-- for example, sparsity in convolutional filters will have a different impact in the effective sparsity metric than sparsity in MLPs (if I understand correctly). Therefore, there will be some differences between architectures that allocate parameters differently (and what is pruned). \n* Showing how some of these methods look in another domain such as NLP could be interesting. \n\nMinor comments: \n* I found the caption to Figure 3 slightly confusing. ", "summary_of_the_paper": "The paper points out that in pruning, there is often a difference between the number of zero parameters and the number effective zero parameters due to disconnection during pruning. A thorough analysis is done comparing many pruning methods across MNIST, Cifar-10, and TinyImageNet using various architectures. The authors introduce a new physics inspired layerwise sparsity quota  baseline the \"Ideal Gas quota\" which sets a sparsity per layer. ", "summary_of_the_review": "The paper is well written, very clear, and well presented. The authors raise and clearly document the discrepancy between raw sparsity and the actual effective sparsity of a model. An interesting and compelling new baseline is presented.\nHowever, the results are shown on small datasets without comparison with many modern architectures. \nReplacing the MNIST/LeNet/VGG results with more modern architectures would clearly increase the impact of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "78D5thnfHKs", "reviewer": "Reviewer_B4nR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strong points:**\n\n- From my experience, I recognize this problem of “effective sparsity” and, up to my best knowledge, this is the first time when I see it so well formulated. Thus, the paper was a pleasure to read, providing useful insights in understanding sparse neural networks and pruning techniques.\n\n- Few small innovations are introduced to cope with the concept of “effective sparsity” in order to improve the trade-off model size/accuracy\n\n- The code is provided for easy reproducibility\n\n**Weak points and suggestions for improvement:**\n\n- The paper contributions are hard to derive from the actual text. I suggest adding somewhere in the Introduction section, few short and concise bullet points to present the paper contributions and to sharply discuss what is novel with respect to the literature.\n\n- The Related Work section contains just a categorization of various pruning techniques. I suggest to add an extra paragraph which clearly discuss the related work with respect to the “effective sparsity” concept.\n\n- The experiments are performed just on dense-to-sparse training methods. I suggest considering also sparse-to-sparse training methods with prune and grow strategies. I agree with the authors statement from the Discussion section that it would be more difficult to incorporate their proposed effective pruning strategy in sparse training. This incorporation can be indeed let for future work, but just studying effective sparsity in sparse training should not be so difficult and the results can be of interest (e.g., same as in Figure 3). \n\n- I understand the ERK baseline for the proposed IGQ method but decoupling ERK from sparse training (as it was originally designed) may lead to misleading results interpretation. Nothing to change in the experimental section, but I suggest clarifying (discussing better) this aspect.\n\n- It is not very clear to me if the paper suggests that the connectivity pattern itself is also quite important in ensuring a good trade-off model size/ performance and not just the sparsity distribution. A discussion has been started on this topic in the last paragraph of page 2, but I would expect the Discussion section to come back to this topic and perhaps some empirical validation would be necessarily to support better the statement “…but find the truth to be more nuanced at higher compression rates…”. I wouldn’t expect a detailed study as it is outside of the scope of this paper, but rather some hints in order to avoid cutting from start future works on this topic. \n", "summary_of_the_paper": "This paper raises a warning signal on an aspect which is typically ignored in sparse neural networks, i.e., the “unconnected” connections (the ones which do not belong to the paths connecting the input to the output neurons). Consequently, the paper studies the so-called “effective sparsity”, to formally understand the efficiency of various pruning methods to obtain sparse neural networks while considering the connections which contribute to the neural network inference (the ones which do belong to the paths connecting the input to the output).  Complementary, the paper proposes some (minor) contributions to cope with effective sparsity. Overall, the paper is well written and has well-designed experiments. \n\n", "summary_of_the_review": "Overall, I believe that this is a well-written paper, with a clear message, which also has some space for improvement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "41j5viIyOu1", "reviewer": "Reviewer_Ne1A", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverview:\n\nThe issue of effectively disconnected parameters [Tenaka et. al.], while known, beckons the proper methodological accounting of parameters --- to those 'effectively' contributing. This paper describes this discrepancy and quantifies it at small scale.\nWhile disconnections are known, and to this reviewer at least.--- known to be quantified by practitioners --- such quantification is indeed poorly documented and this paper eloquently captures it. Beyond the methodological importance of such explicit clarification, the practical relevance and expectation of their impact could use further discussion and motivation.\n\nMajor Pros:\n1. The issue of proper methodology in the context of counting of parameters is important and by extension so is accounting for effectively defunct parameters due to disconnection. \n2. The paper is well written and clear.\n\nMajor Cons:\n1. This discrepancy (between effective and direct parameter count) is known (as the authors mention [e.g. Tenaka et al]) and thus the major contribution of this paper is of limited novelty.\n\n2. While the actual methodological claim (one should account for disconnections via effective counting) is very much valid and orthogonal to experimental settings, the practical discrepancy (and thus implications) between direct/effective is very much dependent on the settings:\n\n2.a. As mentioned by the authors (and demonstrated in figure 3), for the iterative pruning of Syntflow and SNIP-iter, no disconnection associated discrepancy appears. Tanaka et al single out the general role of the Iterative nature in upholding continuity even in methods which are not explicitly designed to preserve continuity.\nIn light of such an observation --- for SOTA, such as Iterative Magnitude Pruning (IMP) , it is not clear that in practice a large discrepancy would be present even up to higher than practically employed sparsity levels. \n\n2.b. Further, in terms of architectures, probability of disconnection in modern architectures --- and especially those containing residual connections --- is much reduced. Indeed, in the Resnet experiments (figure 4) there seems to be a relatively small difference between effective and direct. As such, for practical architectures --- the level of actual discrepancy in practice is not demonstrated to be (or as expected to be) meaningful. \n\n2.c. The paper demonstrated the results for small datasets (and weak networks) (mnist/lenet , VGG/cifar10-100, Resnet18/TinyImagenet). \nThe lack of practical large scale (Imagenet) and SOTA architectures limits the conclusions to the applicability.\n\n", "summary_of_the_paper": "The paper highlights the difference between the explicit and effective (through disconnection) number of zeroed parameters in a model --- and argues it is the effective parameters that should be used as the benchmark for comparison.\nFurther comparing pruning methods and re-affirming their performance relative to random pruning equivalents. Finally introducing a layer allocation method which can serve as a better performing random baseline.\n", "summary_of_the_review": "The paper eloquently presents and quantifies --- in the small scale --- the known issue of disconnections as affecting parameter count and pruning methods [Tenaka et al]. The paper can further engage with practical implications. \nI agree that counting effective rather than direct parameters is methogologically good practice. However, the limited scale and demonstration  limits the insight applicability in practice --- especially, as SOTA methods and architectures have structural characteristics which call into question the the level of discrepancy (missing discussion/dimensions of exploration).\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: ### Summary

This work investigates effective sparsity: an assessment of the sparsity of pruned networks that accounts for the fact that unpruned neurons can still be completely disconnected through pruning.  Hence, the effective sparsity of a network may be much lower than otherwise reported.

### Discussion

#### Strengths

- The paper studies an important metric that deserves additional attention in the community, where a change in metric may guide either the theory or practice of pruning.

- The paper evaluates direct versus empirical sparsity for a healthy number of pruning techniques.


#### Weaknesess 

- While this paper appears to be the most direct study of effective sparsity at the moment, it is not the first. Appendix M of [1] defines effective sparsity and shows that direct and effective sparsity are similar for contemporary pruning at initialization techniques. However, that work does not evaluate random pruning. This work here will need to revise its novelty claims to account for these results as its characterization that [1] only considers direct sparsity is incorrect.


- "Computing effective sparsity:" the procedure in question is similar to that of Appendix M in [1], thus its relationship should be detailed.


- With the primary observations residing in the regime of extremely sparse neural networks, the elements of the response (and in the last paragraph of the paper) that claim this regime is productive for ensembling should make a more prominent appearance in the introduction of the work.

[1] Pruning Neural Networks at Initialization: Why Are We Missing the Mark? 
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, Michael Carbin. ICLR, 21


### Recommendation

I recommend Reject. Generally, the paper is well-written and the empirical characterization of direct versus effective sparsity is thorough (except for ResNet-50 results). However, the results and the language around these results need significant rescoping to account for novelty and the relation of the work to an area in which it is anticipated that these results will change theory, practice, or thinking (e.g., ensembling).

Though I cannot speak for future reviewers, IMO, an extension of the results here to ResNet-50+ImageNet should suffice to establish the extent of the discrepancy between direct and effective sparsity. However, to satisfy additional demands from reviewers for more practical relevance, I suggest an evaluation that demonstrates a consequential difference in behavior for a task that maps more closely to the anticipated area of impact (e.g., ensembling)
Decision: Reject