On the Predictability of Pruning Across Scales
Authors: Jonathan S Rosenfeld
Jonathan Frankle
Michael Carbin
Nir Shavit
Venue:  (2021)
Keywords: neural networks
deep learning
generalization error
scaling
scalability
pruning

Abstract: We show that the error of iteratively-pruned networks empirically follows a scaling law with interpretable coefficients that depend on the architecture and task. We functionally approximate the error of the pruned networks, showing that it is predictable in terms of an invariant tying width, depth, and pruning level, such that networks of vastly different sparsities are freely interchangeable. We demonstrate the accuracy of this functional approximation over scales spanning orders of magnitude in depth, width, dataset size, and sparsity. We show that the scaling law functional form holds (generalizes) for large scale data (CIFAR-10, ImageNet), architectures (ResNets, VGGs) and iterative pruning algorithms (IMP, SynFlow). As neural networks become ever larger and more expensive to train, our findings suggest a framework for reasoning conceptually and analytically about pruning.

Under review as a conference paper at ICLR 2021
ON THE PREDICTABILITY OF PRUNING ACROSS SCALES
Anonymous authors Paper under double-blind review
ABSTRACT
We show that the error of iteratively-prunee networks empirically follows scaling law with interpretable coefficients that depend on the architecture and task. We functionally approximate the error of the pruned networks, showing that it is predictable in terms of an invariant tying width, depth, and pruning level, such that networks of vastly different sparsities are freely interchangeable. We demonstrate the accuracy of this functional approximation over scales spanning orders of magnitude in depth, width, dataset size, and sparsity. We show that the scaling law functional form holds (generalizes) for large scale data (CIFAR- 10, ImageNet), architectures (ResNets, VGGs) and iterative pruning algorithms (IMP, SynFlow). As neural networks become ever larger and more expensive to train, our findings suggest a framework for reasoning conceptually and analytically about pruning.
INTRODUCTION
For decades, neural network gruning-eliminating unwanted parts the network- has been popular approach for reducing network sizes or computational demands of inference (LeCun et al. 1990 Reed 1993 Han et al. 2015). In practice, pruning can reduce the parameter-counts of contemporary models by 2x (Gordon et al. 2020) to 5x (Renda et al.) (2020) with no reduction in accuracy. More than 80 pruning techniques have been published in the past decade (Blalock et al. 2020), but, despite this enormous volume of research, there remains little guidance important aspects of pruning. Consider a seemingly simple question one might ask when using a particular pruning technique:
Given a family of neural networks (e.g.. ResNets on ImageNet of various widths and depths), which family member should we prune (and by how much) to obtain the network with the smallest parameter- count such that error does not exceed some threshold ex?
As a first try, we could attempt to answer this question using brute force: member of a family (i.e., perform grid search over widths and depths) and select the smallest pruned network that satisfies our constraint on error. However, depending on the technique, pruning one network (let alone grid searching) could take days or weeks expensive hardware.
we could prune every
If we want a more efficient alternative, we will need to make assumptions about pruned networks: namely, that there is some structure to the way that their error behaves. For example, that pruning a particular network changes the error in a predictable way. Or that changing the width or depth of a network changes the error when pruning in predictable way. We could then train a smaller number of networks, characterize this structure, and estimate the answer to our question.
We have reason to believe that such structure does exist for pruning: techniques already take advantage of it implicitly. For example, Cai et al. (2019) create a single neural network architecture that can be scaled down to many different sizes; to choose which subnetwork to deploy, Cai et al. train an auxiliary, black-box neural network to predict subnetwork performance. Although this black-box approach implics the existence of structure, it does not reveal this structure explicitly or make possible to reason analytically in fashion that could answer research question.
Outside the context of pruning algorithms, such structure has been observed and further codified ssplicitlyyyelldding insights and predictions in the form of scaling laws. (Tn and Le (2019) design the EfficientNer family by developing a heuristic for predicting efficient tradeoff's between depth, width, and resolution. Hestness et al. (207)) observe a power-law relationship between dataset size

---

Under review as a conference paper at ICLR 2021
and the error of vision and NLP models. Rosenfeld et al. (2020) power scaling law to predict the error of all variations of architecture families and dataset sizes jointly, for computer vision and natural language processing settings. Kaplan et al. (2020) develop a similar power law for language models that incorporates the computational cost of training.
Inspired by this line of work, scaling law to predict the error of networks as they are pruned. To the best of our knowledge, no explicit scaling law holding over pruning algorithms and network types currently exists. In order to formulate such predictive scaling law, we consider the dependence of generalization error on the pruning cuniinginduued induced density for networks of different depths and width trained on different dataset sizes.
address research question about pruning by developing
We begin by developing functional form that accurately estimates the generalization error of a specific model as it pruned (Section 3) We then account for other architectural degrees of freedom, expanding the functional form for pruning into a scaling law that jointly considers density alongside width, depth, and dataset size (Section 4 The basis for this joint scaling law an invariant we uncover that describes ways that we can interchange depth, width, and pruning without affecting error. The result is a scaling law that accurately predicts the performance of pruned networks across scales. Finally, we use this scaling law to answer our motivating question (Section 7
The same functional form can accurately estimate the error for both unstructured magnitude pruning (Renda et al. 2020) and SynFlow (Tanaka al.) 2020 when fit to the corresponding data, suggesting we have uncovered structure that may be applicable to iterative pruning more generally. And now that we have established this functional form, fitting it requires only small amount of data (Appendix 5) In summary, our contributions are as follows:
We develop a scaling law that accurately estimates the error when pruning a single network.
We observe and characterize an invariant that allows error-preserving interchangeabiiity among depth, width, and pruning density.
Using this invariant, we extend our single-network scaling law into joint scaling law that predicts the error of all members of a network family at all dataset sizes and all pruning densities.
In doing so, we demonstrate that there is structure to the behavior of the error of iteratively pruned networks that we can capture explicitly with a simple functional form.
Our scaling law enables a framework for reasoning analytically about pruning, allowing us to answer our motivating question and similar questions about pruning.
EXPERIMENTAL SETUP
Pruning. We study two techniques for pruning neural networks: iterative magnitude pruming (IMP)
(Janowsky] 1989; Han et al.) 2015) Frankle et al. 2020) in the main body of the paper and SynFlow
(Taakaa et al., 2020) in Appendix E We describe IMP in detail here and SynFlow in Appendix A IMP prunes by removing fraction typically 20%, as we do vere-of individual weights with the lowest magnitudes at the end of training l
We choose these weights globally throughout the network, i.., without regard specific layers. We use per-weight magnitude pruning because it is generic, well-studied (Han et al. 2015), and matches the sparsity/accuracy tradeoff's of more complicated methods Gaae al. 2019 Blalock et al. 2020 Renda et al. 2020).
Pruning weights typically reduces the accuracy of the trained network, so it is standard practice to further train after pruming to recover accuracy. For IMP, we use a practice called weight rewinding, in which the values of unpruned weights are rewound to their values at epoch 10 and the training process repeated from there to completion. To achieve density levels below 80%, this process repeated iteratively pruning by 20%, rewinding, and retraining-ume until a desired density level is reached. Renda et al. (2020) demonstrate that IMP with weight rewinding achieves state-of-the-an tradeoffs between sparsity and accuracy. For a formal statement of this pruning algorithm, see Appendix A
Datasets. We study the image classification tasks CIFAR-10 and ImageNet. Our scaling law predicts the error when training with the entire dataset and smaller subsamples. To subsample dataset to size of n, we randomly select n of the training examples without regard to individual classes such
We do not prune biases BatchNorm, so pruning 20% of weights prunes fewer than 20% of parameters.
2

---

Under review as a conference paper at ICLR 2021
that in expectation we preserve the original dataset distribution (we always retain the entire test set). When performing iterative pruning, we maintain the same subsample for all pruning iterations.
Networks. We study three families of neural networks: ResNets for CIFAR-10, ResNets for Ima- geNet, and (in Appendix E VGG-style networks for CIFAR-10 10 We develop a scaling law that predicts the error (when pruned) of an entire family of networks with varying widths and in the case MeNNets--epths To vary width, we multiply the number of channels in each layer
of the CIFAR-10 by a width scaling factor. To vary depth of the CIFAR-IO ResNets, we vary the number of residual blocks. We refer to a network by its depth / (the number of layers in the network, not counting skip connections) and its width scaling factor w.
Notation and terminology. Throughout the paper, we use the following notation and terminology:
y {æ yi J is labeled training set with N examples. A subsample of size n is a subset of DDx containing n examples selected uniformly at random.
I and w are, respectively, the depth (i.e., the number of layers, excluding skip connections) and the width scaling factor of particular network.
A collection of networks that vary by width and depth are a network networ,family.
8 is the sparsity of pruned network (i.e., the fraction of weights that have been pruned) and
d - 1 - is the density (i.e., the fraction of weights that have not been pruned). e (d,, 1, w, n) is the test error of a network with the specified density, depth, width scaling factor, and dataset size.
Emp (1, wc n) = (1, w, n)) is the test error of the unpruned network with the specified depth, width scaling factor, and dataset size. When clear from context, we omit (w,2, n) and write Eap-
ē(Enp, I, w. n) is an estimate of the error of a pruned model for a scaling law that has been fit specific network with the specified depth, width scaling factor, and dataset size (Section 3).
é (empp d, I, w, n) is an estimate of the error of a pruned model with the specified depth, width scaling factor, and dataset size for a scaling law that has been fit to a network family (Section +
Dimensions. In developing scaling laws, we vary four different dimensions: dataset subsample size (n) and network degrees of freedom density (d), network depth (I), and width scaling factor (w). We consider the following ranges of these values in our experiments in the main body of the paper:
Network Family
Nem
Nu
Densities (d)
Depths (1)
Width Scalings (w)
Subsample Sizes (r))
CIFAR-10 ResNet
50K
40) 8, 14, 20, 26, 50, 98 50K 0.8", E (O......0 30)
10K 0.8%, à (0. 40)
2 E ( (-......22
2) N.
(1, (1, 2,4,8 16, 64)
ImageNot RosNet
1.28M
50
2 E (-4....
1. (1,
We use sanity checks to filter infeasible or unusual configurations from this table. In many cases, networks become disconnected before we reach the lowest density (e.g., ~300 of the CIFAR-10 10 ResNet configurations). We also eliminate configurations where increasing width or depth of the unprumed network lowers test accuracy (e.g., 144 of the 294 CIFAR- 10 ResNet configurations of I, w, and n)): these are typically unusual, imbalanced configurations (e.g., g.., = 98, w 1 ). Of the 12,054 possible CIFAR-10 ResNet configurations, about 8,000 are eliminated based on these sanity checks.
3 MODELING THE ERROR OF A PRUNED NETWORK
Our goal in this section is to develop a functional form that accurately models the error of a member of network family as it is pruned (using IMP here and SynFlow in Appendix Eb based on its unpruned error (ap(U) 1, n). In other words, we wish to find function 2(Gup, d | I, w. n) that predicts the error at each density d for network with particular depth I, width scaling factor w, and dataset size n.
Intuition. Since IMP prunes a network 20% at a time, it produces pruned networks at intermediate levels of density da = 0.8* in the process of creating final pruned network at density dx 0.8 In Figure (left). we plot the error of these pruned networks for members of the CIFAR-10 ResNet family with different widths w. All of these curves follow similar pattern!
SSe Appendix for full details on architectures and hyperparameters. Thhe same patterss occur when varying I and n for CIFAR- 10 and and n for ImageNet (Appendix C. We focus on varying width for CIFAR-10 here for illustrative purposes.
3

---

Under review as a conference paper at ICLR 2021
El High plateau
-17
Slope: Y
1og tap1 eir
lag1D| top err
-244
Power-law region
-14
r(d) = od
1og1
W=
Vnp
W= 1/4
== 1/2
Low error plateau Eap
Eap
1/8
eq. asymptotic
20
log10 density)
-34
-29 -25 log10 density)
log10r x [a.u.]
-1o -02
Figure I: Relationship between density and error when pruning CIFAR-I0 ResNets; varies, - =0, N (left). Low-error plateau, power-law region, and high-error plateau for CIFAR-10 ResNet N (center). Visualizing Equation I and the roles of free parameters (right).
1 = 20, w
Observation 1: Low-error plateau. The densest pruned networks (right part of the curves) have approximately the same error as the unpruned network: (mp(w). We call this the low-error plateau.
Observation 2: Power-law region. When pruned further, error increases in a linear fashion on the logarithmic axes of the figure. Linear behavior on a logarithmic scale the functional form of power law, in which error relates to density through an exponent and coefficient c(d, w) = cd In particular, y controls the slope of the line on the logarithmic axes.
Observation 3: High-error plateau. When pruned further, error again flattens; we call this the high-error plateau and call the error of the plateau et.
Figure (center) labels these regions for CIFAR-10 10 ResNet-20 (width scaling factor 1, dataset size N) and shows an approximation of these regions that is piece-wiee wise linear on logarithmic axes. These observations are our starting point for developing a functional form that estimates error when pruning.
Functional form. Our next task to find a functional form that accurately captures these observations about the relationship between density and error. In prior work, Rosenfeld et al. (2020) observe that the relationship between width and error shares the same general shape: it has a region of lower error, power-law region, and region of higher error. However, this relationship is different enough from the one we observe (see Appendix to merit an entirely new functional form.
To develop this functional form, we note that the three regions of the curves in Figure I (the low-error plateau, the power-law region, and the high-error plateau) can be described by three power laws: two plateaus with exponent zero and one intermediate region with exponent ry A functional family that arises frequently the context systems that exhibit different power-law regions is the rational family. The particular family member consider is follows
ct
E(Enp; 1, n) = Eop
Cxp
where j =
d ip
This function's 's shape controlled by Caps et, 7% and p (visualized in Figure I right). Cap and ct are the values of the low and high-error plateaus. is the slope of the power-law region on logarithmic axes. p controls the density which the high-error plateau transitions to the power-law region.
Fitting, To fit éfrmp, d I, n) to the actual data e (d, w. nt), we estimate values for the free parameters et, 7, and p by minimizing relative error A (ic..:dll...aa-c((dd..
using least squares regression. The fit is performed separately for each configuration (1, w,,) n) for all 30 densities, resulting per-configuration estimates of éT, 7. and p.
c(d,1,w..)
Evaluating fit. For qualitative view we plot the actual e w, n.) and the estimated error é(Enp: w. n) as a function density for CIFAR-10 ResNets varying widths (Figure left). Our
"The expression
La meaning Eq. can be rewritten Enp
<Ptp (c7 /<mp)
2/7
6/2
d''4p"
$ 'Since the error is a 4-dimensional function, projections of it yield qualitative analysis- see Appendix 'We compute the the across three replicates with different random seeds and dataset subsamples.
4

---

Under review as a conference paper at ICLR 2021
fit
111.3% a:3. a:3.7%
14.
fit
1:1.1% 0:3.4%
28-
log100 tsp1 eir
-24-
estimated error
estimated arror
-3 -20
3.
22
06
15
03
04
Ing10 density)
actual orror
actual prrar
Figure 2: Estimated (blue dots) and actual error (solid lines) when pruning CIFAR- -- ResNets; w varies, I = 20, = N (left). Estimated versus actual error for the same networks (center). Estimated versus actual error for all CIFAR- 10 ResNet configurations (right).
log? (okp(hh
(wictt)))
-22 -15
log7 (density)
log2ldensity)
Figure 3: Projections of c(d, I, w, n) onto wwoddimensional planes for the CIFAR- ResNets, showing contours of constant error. For low enough densities, the contours have linear slopes on the logarithmic axes axes- depicted by reference black-dotted line. The density/depth plane (left). The density/width plane (right).
estimated error appears to closely follow the actual error. The most noticeable deviations occur at large densities, where the error dips slightly when pruning whereas we treat it as flat (see Section 6).
Quantitatively, measure the extent to which estimated error departs from the actual error using the mean μ and standard deviation a of the relative deviation Figure (center) compares the estimated and actual errors for the networks in Figure (left); Figure (right) shows the same comparison for all configurations of 1, w. and n on CIFAR-TO TO and the more than 4000 pruned ResNets that result. The relative deviation on all configurations has μ 2% and standard deviation 4%; this means that, if the actual error is 10%, the estimated error is 9.8 + 0.4% (E (1 5)e).
4 JOINTLY MODELING ERROR ACROSS ALL DIMENSIONS
In Section 3 found functional form éEEmp, d I, w.)) (Fquation 1 that accurately predicts the error when pruning specific member of a network family (with depth and width w) trained with a dataset size n. The parameters governing Equation [I (Et, p. and 7 ) were allowed vary between different configurations and depend on w, However, we are interested in a single joint scaling law ë(Cmp. d, 1, w. n) that, given the unpruned network error (xp(1, w, n), accurately predicts error across all dimensions we consider: all members of network family that vary in depth and width, all densities, and all dataset sizes. Importantly, the parameters of such a joint scaling law must be constants function of all dimensions. In this section, we develop this joint scaling law.
Intuition: the error-preserving invariant. Our desired scaling law é(Cnp: d, 1, w, n) will be a four- dimensional function of d, I, and n. To develop this, study the interdependence between density and depth or width by examining two-dimensional projections the actual error e(d, I, w, w,n) (Figure 3) These plots display contours of constant error as density and depth width vary.
Consider the projection onto the plane density and depth (Figure 3 left). The constant-erro contours linear except for in the densest networks, meaning each contour traces a pawer-law relationship between d and l. In other words, we can describe all combinations of densities and widths that produce error e, using dd v, where is constant which network emro e, and

---

Under review as a conference paper at ICLR 2021
-07
log10
-1x
slope: y
slope: y
slope: y
p'
log10( m
log10(
log10
Figure 4: Relationship between m² and error when pruning CIFAR-10 ResNets and varying (left,
1 20, n - N), I (center, w 1, n N), n (right, / 20, w 1). 7, et, and p' are annotated.
is the slope of the contour on the logarithmic axes. The contours of density and width also have this pattern (Figure right), meaning we can describe similar relationship w d v'. Finally, we can combine these observations about depth and width into the expression [ " = v".
We refer to the expression 1w d as the error-presee prroe-preseviigg invariant, and we denote m This invariant captures the observation that there exist many interchangeable combinations of depth, width, and density that achieve the same error and tells us which combinations do so. For example, networks of vastly different densities reach the same error if we vary and according to the invariant.
Functional form. The invariant allows us to convert the functional form ē(Cnp. d 1, (,,.. n) for specific I, and from Section 3 into joint functional form é(Emp. d, w, n) for all I, w. and n. Rewriting the definition of the invariant, d form from Section
m
We can substitute this for d in the functional
Tony.
Finally, by rewriting as 1ow and canceling, we arrive at the expression:
m jp'
1wd d ip
E(Emp, d | (.w.n. = eap
jp
Cxp
Exp
bowvd jp
Enp
E(Enp, d, w, (2)
which is the joint functional form é(Cmps d, w, n) of all four dimensions d, 1, w, and n. Critically, for this to be useful joint form, the free parameters ex p', and y must be constants shared across all possible values of d, w, and n. We will assume this the case and directly quantify how well this assumption holds in the fit section to follow. To glean some qualitative intuition as to why this may be a reasonable assumption, we can examine the relationship between m and the generalization vary depth, width, and dataset size (Figure 4. Across all projections,
error of pruned networks the annotated et (error of the high-error plateau), y (slope of the power-law region) and p' (value of m" where the high-error plateau transitions the power-law region) are the same. Note that in Eq. the dependence on n implicit, through Cap- We retain the explicit form ě(..., n) to stress that the lack of explicit dependency on non-trivial and not known prior our work.
Fitting, To fit ((Emp, d, I, w, n) to the actual data <(d, 1, w, n), we estimate values for the free using least squares regression. The fit performed jointly over all configurations of d, I, w. and n, resulting in
parameters e,, 7, p and vi by minimizing the relative error ò (
eld.l,w.n)
joint estimates of ēt, 9, Ø, and v. One can also perform partial fit for a subset of dimensions (e.g.. just d, I, and n) by omitting e and/or & (see Appendix DD.
Evaluating fit. In Figure 5 É(Enp: d, w. n) for the CIFAR-10 ResNets and ImageNet ResNets (single depth). As in Section 3. our estimated error appears closely follow the actual error. Deviations arise mainly at high densities where error dips below Eap and low densities approaching high error saturation.
we plot the actual error e(d, ((d,,ww, w., and the estimated error
We again quantify the fit of the estimated error using the mean μ and standard deviation of the relative deviation The relative deviation on the joint scaling laws for the CIFAR-10 10 and Imagenet networks has mean μ 2% and standard deviation of < 6%.
To contextualize these results, Figure 5 (right) quantifies the variation in error we see over multiple trials of the CIFAR-10 experiments due to using different random seeds. It plots the minimum,

---

Under review as a conference paper at ICLR 2021
34
fit
111.2%
0.2.6%
fit
p=0.9% a:5 5:5.8% 8%
baseline
0o0.0% o:3.4%
4.3
actuual error (no mman)
estimatted error
-4
estimated
8.4-
-4
02 actual error (mean)
33
80 82
actual error (mean)
actual error (mean)
Figure 5: Estimated versus mean actual error for all configurations (d, w, n) for ImageNet (left) and (d, w, n,) for CIFAR-I0 (center). The variation in error when running the same experiment on CIFAR-10 three times with different random seeds (right).
maximum, and mean errors across the three trials we ran The variation across trials has a standard deviation of 3.4%, sizeable relative the estimation error This indicates that significant portion of our error may stem from measurement noise.
5.8% for the joint scaling law.
The functional form has just five parameters and obtains an accurate fit over 4000 points, suggesting it is good approximation. In Appendix E., we show that it achieves similarly good fit for VGG-style networks and for the SynFlow pruning algorithm. good fit with far fewer points and that the fit has low sensitivity to the choice of points.
Section []] we show that possible to get
5 ANALYZING THE SENSITIVITY OF THE FIT TO NUMBER OF POINTS
In Section 4 we showed that our scaling law was accurate when we fit on all of the available data. Now that possess the functional form and know that it can accurately model the behavior of IMP, we study the amount of data necessary to obtain a stable accurate fit. This question is especially relevant when the functional form is applied to new settings new networks, datasets, or pruning algorithms-and we must collect new data to do so. The functional form has only five parameters, suggesting that few experiments will be necessary.
To evaluate the effect of the number of points on the stability and accuracy of the fit, we randomly sample varying numbers of points, fit the scaling law those points, and evaluate the quality of the fit over all points. We sample these points in two ways.
Experiments.
Experiment I. Randomly sample T network configurations (w, I, n, d). This experiment captures the use case of algorithms such as SynFlow (Appendix E)), where obtaining data at any density d relies only on possessing the unpruned network, not other densities d' d.
Experiment 2. Randomly sample T network configurations (w, I,) and include all densities d for each configuration. This experiment captures the use case of algorithms such as IMP, where obtaining data at density d requires obtaining all densities d' > d. As such, we anticipate that data will be obtained by iteratively pruning small number of configurations (w, n.) to low density.
Results. We perform each experiment for many different values of T on the CIFAR-10 ResNets pruned with IMP. We repeat the experiment at each value of 7 30 times (with a different sample of points) and report the mean and standard deviation of μ and for the fit. Experiments and appear in Figure 6 The shaded areas represent one standard deviation from the mean each direction. On Experiment 1, when just 40 configurations of (w, I, d, n)) are available, the standard deviation both y1 and a is just one percentage point. On Experiment 2, when just 15 random configurations of (w, I, n) are available at all densities, similarly achieve standard deviation below 1%. In both cases, as the number of networks increases, the standard deviation decreases further.
7 We only ran a single trial of the ImageNet experiments due to the significant cost collecting data. $Stability is defined as small change in output relative change input. The requirement here is that change choice of points leads small expected change estimation accuracy in expectation.
7

---

Under review as a conference paper at ICLR 2021
15. 100 points (M).dn))
i number configurattons twiin
Figure 6: The effect of the number of points used to fit our scaling law (on the CIFAR-10 ResNets pruned with IMP) on and σ. Left: experiment I from Section 5 (random points L, d, n.) Right: experiment from Section (random configurations w, I, n. and all densities).
lop10/ top1 er
-04
Loo1 simulater antulateddd
104
lo tog1 erT
-00
-1.0
Ours
Gap
min simulated
min: pruning
log10 dersity)
log10t #noo-zzer param
log10r #non-zero param
Figure 7: Error of the CIFAR- 10 ResNets width varies (left); actual error (black), error of our scaling law (blue), and error the scaling law adapted from Rosenfeld et al. (2020) (red). Estimated error from scaling law width varies for the CIFAR- 10 ResNets (center); in dotted black is the minimal number of parameters for each error eg. Same as center but using actual error (right).
These results show that, now that scaling law is known, it is possible to obtain accurate (and stable) estimation using far less data than we used to evaluate the quality of the fit in the main body of the paper. Importantly, the experiments make no effort to ensure that the configurations we select represent a diverse range widths, depths, dataset sizes, and densities. By selecting these configurations in strategic way, we believe it would be possible to further reduce the number of configurations necessary to obtain similarly accurate fit.
perform in this section particularly naive. We
6 PRINCIPLES FOR SELECTING A FUNCTIONAL FAMILY
In this section, we discuss some of the key criteria that led us to select this particular functional form and opportunities for further refinement.
Criterion Transitions. Section we observe that, when pruning a neural network, error has a low-error plateau, power-law region, and high-error plateau. Between these regions transitions where error varies smoothly from one region to the next. Matching the shape of these transitions was a key consideration for selecting our function family. To illustrate the importance of properly fitting the transitions, Figure (left) shows two possible functional families for fitting the relationship between density and error for CIFAR-I0 ResNets. Actual error is in gray, and the functional form from Section 3 is in blue. In red is the fit for a functional form adapted from the one that Rosenfeld al. 2020) use model the relationship between width and error. The difference between these functional families is the way they model transitions, and the one we choose in this paper better models the transitions in our setting. For further discussion of this comparison, see Appendix G
Criterion 2: A small number of interpretable parameters. Selecting functional form is not merely a curve-fitting exercise. We seek the underlying structure that governs the relationships between d, 7, n, and error in a manner akin to law of physics. As such, our functional form should have small number of parameters that are interpretable. In our functional form (Equation 2), each parameter has clear meaning. The parameters el, p', and control the high-error plateau, the transition to the power-law region, and the slope the plwer-law region. & and & control the interchangeability of width and depth with density. We approximate error over multiple orders
8

---

Under review as a conference paper at ICLR 2021
of magnitude and over 4,000 configurations of ResNet-20 on CIFAR- 10 with just five parameters, indicating we have distilled key information about the behavior of pruning into our functional form.
Sources of systemic error and limitations of our approximation form. By seeking to minimize the number of parameters in our functional form, we leave some phenomena unmodeled. In particular, there are two phenomena we have chosen not to model that introduce systemic error. First, the low-error plateau is not a plateau. Error often improves slightly at high densities before returning to Enp during the transition to the power-law region. Our model treats the region as flat and treats error as monotonically increasing as density decreases. This source of error accounts for a bias of 1% relative error in our estimation (Appendix H). Second, we model both transitions (between the power-law region and each plateau) with single shape and the same transition rate. If we treated each transition separately and used higher-order terms in the rational form, we could potentially reduce some of the residual error in our estimation at the cost of additional complexity.
IMPLICATIONS AND CONCLUSIONS
Our main contribution is a functional form É(emp: d, I, w.n) that accurately predicts the error when pruning members of network family using both IMP and SynFlow. There are several broader implications of our ability to characterize pruning in this way. The mere existence of this functional form means there is indeed structure to the way pruning affects error. Although prior work (Cai et al. are the first to explicitly describe it. This functional
2019) has implicitly relied such structure, form enables a framework in which we can reason conceptually and analytically about pruning. In doing so, we make new observations about pruning that non-obvious or costly to exhaustively demonstrate empirically. For example, recall our motivating question:
Given family of neural networks, which should we prune (and by how much) obtain the network with the smallest parameter-coue such that its error does not exceed some threshold eg?
This is an optimization problem- find the configuration of d, I, and that minimizes parameter-count subject to an error constraint: argmin m s.t. é Ek. For ResNets m & dlw?, yielding:
L, W. d = argmin IwPd d s.t. Enp [ d dddddjpi jo /emp)) ( [1 d- j 11'" Ex
1,w,d
which is solvable directly without running any further experiments.
Using this approach, we can derive a useful insight. In the pruning literature, it is typical report the minimum density at which the pruned network can match the error enp(1, w) of the unpruned network (Han et al. 2015). However. our scaling law suggests that this is not the smallest model that achieves error Enp(4 (l, w). Instead, it is better to train a larger network with depth l' and width w' and prune until error reaches (np(1, w:), even as that results in error well above Cxp (?', w'). This analytic result parallels and extends the findings of Li et al. (2020) on NLP tasks.
Figure (center) illustrates this behavior: it shows the error predicted by our scaling law for CIFAR- 10 ResNets with varying widths. The dotted black line shows the minimal parameter-coum at which we predict it possible to achieve each error. Importantly, none of the low-error plateaus intersect this black dotted line, meaning a model cannot be minimal until it has been pruned to the point where it increases in error. This occurs because the transitions of our functional form are gradual. On the other hand, if we start with model that is too large, it will no longer be the black line when it has been pruned to the point where its error reaches Cap (1, w) In Figure 7 (right), we plot the same information from the actual CIFAR-10 data and see the same phenomena occur in practice. The difference between the estimated and actual optimal parameter count is no more than 25%.
Looking ahead, there are several opportunities for future work. Better understanding the sources of systematic error (error dips and transition shape) is a promising avenue for making it possible to extrapolate from small-scale settings large-scale settings (see Appendix [Forr forward looking discussion of extrapolation). Furthermore, although we focus on pruning for image classification and networks and pruning methods differ in other contexts (e.g., NLP), the generality of our functional form to different pruning strategies and network families suggests it may have broader applicability.
Thiis hehavior occurs since mm for IMP. Interestingly, for SynFlow x m" such that sufficiently large networks are equivalent.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Conference on Machine Learning and Systems, 2020.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Voossert-Voss,, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
Han Cai, Chuang Gan, and Song Han. Once for all: Train network and specialize it for efficient deployment. arXiv preprint 1xXiv:1908.09991, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In International Conference on Machine Learning, 2020.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574 09574, 2019.
Mitchell A Gordon, Kevin Duh, and Nicholas Andrews. Compressing bert: Studying the effects of weight pruning on transfer learning. arXiv preprint arXiv:2002.00 08307, 2020.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances neural information processing systems, pages 1135-1143, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition. pages 770-778, 2016.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang. and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv:1712.004400 2017.
Steven A. Janowsky. Pruning versus clipping in neural networks. Phys. Rev. A, 19:66000-6603,,.. Jun 1989. doi: 10.1 10.1003/Pyyseev.339..o A.3.6666000..60 URL htttp:://iin...ps.rrg////. PhysRevA. 39.6000..9.660000 6600
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08.0 000001,003611.. 2020.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pages 598 605, 1990.
Zhuohan Li, Eric Wallace, Sheng Shen, Kevin Lin, Kurt Keutzer, Dan Klein, and Joseph E Gon- zalez. Train large, then compress: Rethinking model size for efficient training and inference of transformers. arXiv preprint 1rXiv:2002.11794 2020.
Russell Reed. Pruning algorithms-a survey. IEEE transactions on Neural Networks, 4(5)7740-747, 1993.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference Learning Representations, 2020. URL htttps://openzeviees n wwwe/fouuun wwo.umiid=Si.. JONKBB
Jonathan S. Rosenfeld, Amir Rosenfeld. Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In International Conference on Learning Representations, 2020.
ew http://wwwww.e...ee.eeeeeeeeeee wtt.eeeeooorrrmmt/eerrreaaaaeee
10

---

Under review as a conference paper at ICLR 2021
Mingxing Tan and Quoc V Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint arXiv:1905//1946, 2019.
Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow, 2020.

---

Under review as a conference paper at ICLR 2021
CONTENTS OF APPENDICES
Appendix
Details on the IMP and SynFlow pruning algorithms.
Appendix
Details on the models, datasets, and training hyperparameters.
Appendix
Full data for the observations we make in Section
Appendix Partial fits (c.g.. just width, depth, dataset size) for the joint scaling law in Section 4
Appendix Demonstrating that our functional form applies to VGG-style networks for CIFAR-10 and to the Flow pruning technique.
Appendix A discussion of extrapolation for our scaling law.
Appendix A more detailed comparison between scaling law and that of Rosenfeld al. (0220)
following up on Section 6
Appendix How computed the effect of error dips estimator in Section
12

---

Under review as a conference paper at ICLR 2021
A PRUNING ALGORITHMS
A.1 FORMAL STATEMENT OF ITERATIVE MAGNITUDE PRUNING (IMP)
Algorithm Iterative Magnitude Pruning (IMP) with weight rewinding to epoch 10 and N iterations.
I: Create neural network with randomly initialized weights Wo IR and initial pruning mask 1d
2: Train Wo epoch 10, resulting in weights W10
for E {L, .L.....d
...... N} do
4: Train m @ Wio (the element-wise product of m and Wio) to final epoch T and weights y O WT,
5: Prune the 20% of weights in @ Wr,n. with the lowest magnitudes. m[i] = if Wr, is pruned
6: Return and Wr.n
A.2 SYNFLOW
Unlike IMP, SynFlow is a pruning algorithm that prumes neural networks before any training has taken place (Tanaka et al. 2020). To do so, SynFlow computes the "synaptic strengths" of each connection and prunes those weights with the lowest synaptic strengths (see Algorithm 2 below for the details on computing the synaptic strengths).
Importantly, SynFlow prunes iteratively. It prunes small number of weights, recalculates the synaptic strengths once those weights have been fixed zero, and then prunes again. To prune to =-1 sparsity 8, SynFlow iteratively prunes from sparsity Tou to sparsity 8 s for n E (1,..., 100).
After pruning, SynFlow trains the network normally using the standard hyperparameters. SynFlow computes the synaptic strengths as follows
Algorithm 2 Computing the synaptic strengths of a network with weights W.
1: Replace all weights w E W' with their magnitudes |w].
2: Forward propagate an input of all I's
3: Take the sum of the logits R.
4: The synaptic strength for each weight the gradient die
Note that this algorithm leads to exploding activations on deeper networks, so we do not vary network depths in any of our experiments involving SynFlow.
13

---

Under review as a conference paper at ICLR 2021
B EXPERIMENTAL DETAILS
B.1 RESNETS
We study the residual networks (ResNets) designed by He bee ResNets for CIFAR-10 10 are composed of an initial convolutional layer, three sets of B residual blocks (each with two convolutional layers and skip connection), and a linear output layer. The sets of blocks have 16, 32, and 64 convolutional channels, respectively.
al. (2016) for CIFAR-10 10 and ImageNet.
ResNets for ImageNet are composed of an initial convolutional layer, a max-pooling layer, four sets of residual blocks (each with three convolutional layers and skip connection), and linear output layer. The sets of blocks have 64, 128, 256, and 512 convolutional channels, respectively.
We place batch normalization before the ReLU activations.
To vary the width the networks, we multiply the number of convolutional channels by the width scaling factor w. To vary the depth of the CIFAR-10 ResNets, vary the value of B. The depth of the network the total number of the layers in the network, not counting skip connections.
B.2
VGG NETWORKS
We study the VGG-16 variant of the VGG networks for CIFAR-I0 as provided by the OpenLTH repository [1 The network divided into five sections, each of which is followed by max pooling with kernel size 2 and stride The sections contain 3x3 convolutional layers arranged as follows:
Section Layers
1
64
2
2
128
2
3
256
3
4
512
5
512
3
The network has ReLU activations and batch normalization before each activation. To vary the width of VGG-16, we multiply each of the per-segment widths by the width scaling factor w.
When pruning VGG, we consider the following configurations:
Family
Muan
Nis
Densities (d)
Depths (1)
Scalings (w)
Subsample Sizes (r)
CIFAR 10 VGG 16|
50K 10K 0.8". i E (0.....37)
2 E (-...-4...... 1......0 0)
{1}
B.3 TRAINING HYPERPARAMETERS
We train CIFAR- ResNets and VGG-16 16 for 160 epochs with a batch size of 128. The initial learning rate is 0.1, and it drops by order of magnitude at epochs 80 and 120. We optimize using SGD with momentum (0.9). We initialize with He uniform initialization. Data is augmented by normalizing, randomly flipping left and right, and randomly shifting by up four pixels in any direction (and cropping afterwards). All CIFAR-10 networks are trained on GPUs.
We train ImageNet ResNets for 90 epochs with a batch size of 1024. The initial learning rate is 0.4, and it drops by an order of magnitude at epochs 30, 60, and 80. We perform linear learning rate warmup from 0 to 0.4 over the first 5 epochs. We optimize using SGD with momentum (0.9). We initialize with He uniform initialization. Data is augmented by normalizing, randomly flipping left and right, selecting a random aspect ratio between 0.8 and 1.25, selecting random scaling factor between 0.1 and 1.0, and cropping accordingly. All ImageNet networks are trained on GPUs.
"I htw.ghh...ccooo/eieeeeeee hatthbb.cc//aacbbbbrreeer/e////e
14

---

Under review as a conference paper at ICLR 2021
C FULL DATA FOR KEY OBSERVATIONS IN SECTION 3
In this appendix, we show that our observations from Section 3 hold when varying all dimensions (depth, width, and dataset size) both the CIFAR-IO and ImageNet ResNets for IMP. Figure shows the error versus density when changing width (left) depth (center) and data (right). In Figure 9 we similarly show the dependency of the enror on density for Imagenet when varying width (left) and dataset size (right).
In Figure 8 we observe that all curves have similar slope in the power-law region. Equation [ this implies that while is allowed to vary with I, w and it is in practice approximately a constant. Similarly, the high-error plateau < is also shared across curves such that too approximately constant. In contrast, the transition from high-error plateau to the power-law region is not constant as a function density, Section finds exactly this dependency the transition parameter p.
-44
log10t top]
Wm
n=
==
-10
W
W- 1/2
n= 1/4
1/8
W= 1/8
n= 1/32
1/16
== 1/64
log10 density)
log10 density
density)
Figure 8: Relationship between density and emorr when pruning CIFAR-10 ResNets and varying (left, 1 20, n N), (center, w = 1, n = N), n (right,
20, w = 1)
log10
W=
1/4 w=
n=
1/8
-65
66
-2
-00
-2
-05
log10( density)
log10(
density
Figure 9: Relationship between density and error when pruning Imagenet ResNet-50 and varying w (left, N), and (right, 1)
15

---

Under review as a conference paper at ICLR 2021
D PARTIAL (PROJECTIONS) FIT RESULTS FOR SECTION 4
In Section 4 we fit the error jointly as a function of all dimensions showing that Equation good approximation to the error in practice. In this appendix, we consider important sub-cases, such as the case when one wishes to scale only one degree of freedom while pruning. This serves both a practical scenario, but also allows for a qualitative visualization of the (and typical sources of error), which is otherwise difficult to perform over all dimensions jointly. From practical standpoint, this case one need not estimate the parameters associated with the fixed degree of freedom.
2 provides
Recall that, given the non-pruned network error Exp. all dependencies the individual structural degrees of freedom 1, w captured by the invariant m & 1 d. This means that, if one wishes to estimate the error while pruning when holding width fixed, we need not estimate ab. Similarly depth is held constant, need not estimate Φ.
Figure TO shows these partial fits. Shown from left to right are the fits done while pruning and varying width, depth and data respectively. Correspondingly, these fits omit separately & when depth nor width are scaled. The fits were performed with all available density points for each dimension. For CIFAR-I0:
omit both
widths, 224 points for the width partial fit; 7 dataset fractions, 240 points for the data partial fit; 4 depths, 164 points for the depth partial fit. For ImageNet: 5 widths, 83 points for the width partial fit; 3 dataset fractions, 86 points for the data partial fit.
This exercise, apart from its practical implications, highlights the fact that there are in effect two groups of parameters comprising the estimation. The first are the parameters et, 7 and p' which control the dependency as function of density (or more generally, as function of the invariant). The second are & and & which are properties of the architectural degrees of freedom captured by the invariant. Moreover, within the first group of parameters et, 7 can be isolated and found from single pruning curve, as they are not a function of L, W. n2.
24
-02
log10/ top1 err)
104
-06
fit
-09
W 4
n=
W-2 2
n=
1/2
1/4
fit
W= 1/4
n=
1/16
20
1/8
n= 1/32
14
1/64
log10/ m²)
log10(
log10(( m
-11
-12
log10( top1 err
W= 1
W= 1/2
fit
1/8
1/2
W- 1/16
n= 1/4
20
25
log10(
log10(
Figure 10: Top row: CIFAR-10. Bottom row: ImageNet. Left: varying width. Center: varying dataset size. Right: varying depth. Lines are the actual error and dots are the estimated error.
16

---

Under review as a conference paper at ICLR 2021
E ADDITIONAL PRUNING ALGORITHMS AND ARCHITECTURES
In this appendix, we show that our functional form applies to both an additional network architecture (VGG-16 on CIFAR-10) and additional pruning algorithm (SynFlow). We add these additional comparisons in the following Figures:
Figure 11
VGG-16 on CIFAR- 10 with IMP width varies. < 3%, a < 7%. Notably, the measurement error in this case large (o 12%), dominating (over the approximation error) the total fit error. The fit averages out some of this emoor resulting in fit error which is lower than the measurement error.
Figure 12
ResNet-20 on CIFAR-10 with SynFlow width varies. # 1%, o 4%.
Figure 1
VGG-16 on CIFAR- 10 with SynFlow as width varies. 1%, 4%.
Note that SynFlow suffers from exploding activations deeper networks, do not vary ResNet depth in any of our SynFlow experiments.
fit
M.2.7% a.6.7%
f.066% 0:12.5%
actual error (ne mean)
top3
04
-12
log10( zero param
orror (mean)
66
C4
crror (mcan)
Figure 11: Fit for VGG-16 CIFAR-10 with IMP pruning.
1tt
fit
120.1% 433.3%
baseline
M.O. a:2.7%
Wi
W
actual error (no meen))
W- 1/2
eztimann BTTOT
W 1/4
W 1/8
W
1/16
log100
-10
log10( peram)
actual emror (mean)
actual emror (mean)
Figure 12: Fit for ResNet-20 on CIFAR-10 with SynFlow pruning.
fIt
#F. 0:3.8%
baseline
a:3.1%
actual error (ne mean)
logi0( top1
estimated
-12
log10 #non-zero param)
actual etror (mean)
65
actual error (mean)
Figure 13: Fit for VGG-16 on CIFAR-I0 with SynFlow pruning.
17

---

Under review as a conference paper at ICLR 2021
F TOWARDS EXTRAPOLATION
Background. the main body, we showed that our scaling law accurately fits the error of pruned neural networks, As, such it has predictive power, allowing to reason in a principled manner about pruning trade-off's. Similarly, it allows to make predictions about what would happen at larger model and data scales than explored here. Importantly. only a few experiments need be performed find the coefficients for the scaling law (see Appendix [5)
However, we could ask, how accurately can we estimate the scaling law parameters from even smaller scales? That is, is it possible to fit our scaling law to data from networks with deliberately smaller depths, widths, and dataset sizes and accurately predict the error of larger-scale models? If so, we could make informed decisions about pruning large-scale scale models through small-scale experiments alone, saving the costs associated with large scale training and pruning.
Outside the context of pruning, the scaling laws of Rosenfeld et al. (2020) (for both language models and image classification) and Kaplan et al. (2020) (for predicting the expected performance of GPT-3 (Brown et al. 2020) very large scale) have been shown to extrapolate successfully in this manner.
Results on CIFAR-10, In Figure 14 we show the result of extrapolating from small-scale networks on CIFAR-I0 (w : 1:: 1 = 14, 20) all widths and depths CIFAR- 10. Extrapolation prediction still accurate: < 7%, a < 6% (vs. P < 1%, a < 6% the main body).
Future work. However, extrapolation is particularly sensitive systemic emror. Specifically, the transitions and the error dips can lead to large deviations when extrapolating. For ImageNet, the error small dataset sizes) especially pronounced, preventing stable extrapolation. In order to improve extrapolation performance, future work should explore the challenges we discuss in Section 6 approaches to either model or mitigate these dips and improve the fit of the transitions.
dips (especially
extrap
fit
4r0.6%
fit
extrap 6.6 0:5.8%
co-
estim estimated ated error
log101 top1 err
C4
65 24
log10( 0( #non-zero param)
actual error (mean)
Figure 14: Extrapolation results from four pruned networks CIFAR10 1 14, to all larger networks (n = 1). Fit results are in blue, extrapolation in red, actual in black. Error versus number of non-zero parameters (left). Estimated versus actual errors (right).
18

---

Under review as a conference paper at ICLR 2021
G COMPARISON OF PRUNING AND NON-PRUNING SCALING LAWS
In this appendix, we contrast the behavior of the error when pruning with the behavior of the error in the non-pruning setting. Hestness al. (2017) show the the error follows saturating power-law form when scaling data (with both low and high-error plateaus) but does not model them. Rosenfeld et al. (2020) unify the dependency on data and model size while approximating the transitions between regions; they propose the following form:
E(m, n))
brr + Coo
(3)
E(m, n.)
E(m,n) 60
(4)
ē(m, n)) - -j
where is the total number of parameters and is the dataset size. a, b, a, B, Coo, and yj constants, and plays the role of e in our notation.
Rosenfeld al. model the upper transition-from power-law region to the high-error plateau-by rational form in fashion similar to the approach we take. The key difference is that we consider a power the polynomials in the numerator and denominator of the rational form, where Eq. the power is hidden in the term é.
The biggest difference arises when considering the lower transition (between the low-error plateau and the power-law region). This transition is captured by Eq. 3 Considering either the width or depth degrees of freedom x E {w. 1]. Eq. can be re-written as:
E(x) = by.
Ax + Cg
Where by and 8n are constants and ex is a constant as a function of x (it is only a function of the data size ni).
Figure 15 (right) shows the error versus depth for different dataset sizes. In grey the actual error, while red the best fit when approximating the error by Eq. [S] Qualitatively, one sees that the fit using Eq. does indeed closely match the еттоr in practice.
Recall that any functional form used to model the dependency on the density is to degenerate to the error of the non pruned model Exp at d We adapt Eq. 5 by solving the relation between by and c₂ meeting this constraint, to arrive at:
interested in comparing the errors
function of the density. A requirement from
E(x) by 9o
Enp
b
(6)
Contrast Eq. 5 with the functional form we propose in Eq.
re- re-written here for convenience:
- jp cap
é(d, Eup 1, n.) = eop
where j = V-1
d ip
This can be simplified to capture only the lower transition far enough from the upper transition (d >> p)
to:
- jp
E(d, Cup 1, n) = Cup
(8)
d
Figure 15 (left) shows versus density for different widths. In blue is the fit with Eq. 8 which follows closely the actual error (black) while red is the fit with Eq. [6 which deviates noticeably in comparison.
19

---

Under review as a conference paper at ICLR 2021
non-pruned law actual
log10 top cr
log10 top3
Ours Adapted from Resenfeld
logi0 density)
log2:
Figure 15: (Left) Error versus density for different widths. In blue is the fit eq. follows closely the actual error (black) while in red the for the adapted from Rosenfeld al. (2020) which deviates noticeably in comparison. (Right) error of non-pruned networks versus width for different data, fit shown (solid red) for the non-pruning scaling from Rosenfeld et al. (2020).
We have seen that in practice that the form of Eq. does not match well the pruning case, where the mismatch originates from lower transition shape. We have thus reached phenomenological observation distinguishing the pruning and non-pruning forms; we leave the study of the origins of this phenomenon for future work.
20

---

Under review as a conference paper at ICLR 2021
H THE EFFECT OF ERROR DIPS ON ESTIMATION BIAS
In this appendix, we consider the effect of the error dips on our estimator as discussed Section As mention in that section, when pruning network, error often dips below Enp during the low-error plateau.
Recall that we find the parameters in estimator (Equation 2) by minimizing the MSE of relative eπrоr 8. Our estimation has bias if E (2 e) # 0 where the expectation is over all model and data configurations. Equivalently, the relative bias is - ES 0 iff the estimator is unbiased. The Estimator captured by the joint form in Equation 2 is monotonically increasing function of the density. It is also constrained such that at density d = 1 it is equal to the non-pruned error énp- It thus, can not reduce The MSE to zero, as it can not decrease to match the actual error dips. This results in the bias of the relative error which in practice is 1%.
21


Reviews:
[{"review_id": "yIozBfW8RpX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies how to estimate the performance of pruned networks using regression models. The authors first empirically observe that there exist three distinct regions of sparsity: (1) In the low-sparsity regime, pruning does not decrease the accuracy (2) In the mid-sparsity regime, a linear relationship between the sparsity and the accuracy is observed (3) In the high-sparsity regime, pruning does not decrease the accuracy again. Under this observation, the authors proposed a regression model called the rational family and empirically verified its performance. The authors further extended this model to incorporate the network width and depth under some empirical observation called the error-preserving invariant. The authors performed experiments to verify different perspectives of the proposed functional form.\n\nOverall, I like the main idea and experiments on the interpolation/extrapolation using the proposed functional form. However, I believe that the following concerns are critical.\n- The authors removed a huge amount of test configurations: about 8000 configurations among 12000 configurations are eliminated for CIFAR-10 ResNet. It significantly reduces the reliability of estimations from the proposed functional form as the removed cases are occasionally observed in practice. \n- The authors only consider limited experimental setups. For example, the effects of network architectures, rewinding weights, iterative pruning, and training epoch to their observation (e.g., having three different phases, error-preserving invariant) are not verified. I am curious whether the proposed functional form is still valid for other architectures (e.g., DenseNet, recurrent networks, language models) and without rewinding.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "m5gYYoD8u1w", "reviewer": "AnonReviewer5", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThis paper explores the possibility to fit power laws to the behaviour of  a neural network's test error under weight pruning and modifying the architecture (depth and width) and subsampling the dataset. This is interesting for practitioners when determining how to change an architecture to achieve desired performance by fitting the proposed power law to a few trained networks.\n\n# Strong and weak points\n\n## Pros\n- The fit of the free parameters yields a very high accuracy for the architectures considered.\n- The resulting parameters of the functional forms yield a direct interpretation.\n- The work is self-contained and well-written\n\n## Cons\n- This is a very high bar, but let me phrase this distant goal anyway: This work does not provide an ab initio derivation of how network depth, width, dataset size and pruning are related to the test error\n- There is room for considering more datasets, architectures. From my side, you don't need to do this to be accepted. But the weight of an empirical paper with structural claims grows with the number of experiments performed.\n\n# Questions\n- Do you have any failure cases for when you are not able to successfully fit the free parameters? I would imagine that e.g. different choices of hyper parameters might yield different laws.\n- If the primary goal in the pruning literature is badly chosen in terms of resulting number of parameters, does it still serve as a benchmark for comparing pruning methods?\n\n# Recommendation\nThis work reduces finding architecture hyperparameters by fitting parameters of a surrogate problem using a small amount of training instances. This can prove useful in practice and the surrogate problem seems to capture the main dynamics well.\nThis makes the work a useful tool and I recommend accepting it to ICLR.\n\n# Minor remarks\nI have some suggestions for the figures in the paper: Please make the lines in legends thicker, like the lines in Figure 6. I had to zoom in significantly to distinguish the colours in most other plots, especially for the dotted lines in Figure 4.\nInstead of taking log10(X) in your figures, please use logarithmic ticks so that one can immediately grasp the values. For example, I took out my calculator to know what $10^{-1.2}$ is in Figure 1.\n\nMaybe you can reduce the number of footnotes in the paper. Personally, I am a huge fan of in-or-out – state it in the main text if important and leave out completely if not.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y45Wb7CuWvt", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper investigates the behavior of the test error as a function of the density of the\nnetwork after pruning and identifies 3  regimes:\n1) a low-density high error plateau; 2) a high-density low error plateau; 3) a power-law behavior for intermediate density. \nThe authors propose a functional form that captures the test error behavior in all these regimes, \nalong the lines of Rosenfeld et al. ICLR 2020. The approximating function contains the unpruned network's error and other 3 parameters that have to be fitted on each architecture.\nThe functional form had to be slightly modified with respect to Rosenfeld et al. to better describe \nthe density dependence near the low error transition. \n\nMoreover, they generalize the approximation to take into account also the width and depth scaling factor,\nand the dataset size as well. The generalized functional form is still relatively simple,\ncontaining only 2 extra parameters. In fact, the authors were able to identify a roughly invariant\nquantity characterizing constant error manifolds. This greatly simplifies the modeling.  \n\nNumerical experiments are performed on CIFAR10  and ImageNet datasets, using VGG and\nResNet architectures. \nTwo algorithms, iterative magnitude pruning and SynFlow, are used for pruning.\nThe proposed functional form is in good agreement with the experiments on each combination of\narchitecture, dataset and pruning algorithm presented.\n\n\nThere are a few drawbacks to the paper. \nNumerical experiments involve only image classification tasks, on a small set of datasets and architectures. \nAlso, one of the applications motivating this kind of analysis, neural architecture search,\nis in my opinion unpractical under the framework proposed, as I argue below. \n\nOn the other hand, the experiments available are quite convincing,  \nand the scaling form proposed is helpful in the qualitative and quantitative understanding and reasoning about the test error surface as a function of pruning and architecture.\nTherefore, I suggest acceptance of the manuscript.\n\n\nMajor Comments\n- End of Section 2:\n\"\"\"\nWe also eliminate configurations where increasing the width or depth of the\nunpruned network lowers test accuracy (e.g., 144 of the 294 CIFAR-10 ResNet configurations of l, w,\n1 and n); these are typically unusual, imbalanced configurations (e.g., l = 98, w = 1/16\n). Of the 12,054 possible CIFAR-10 ResNet configurations, about 8,000 are eliminated based on these sanity checks.\n\"\"\"\nThis seems to be a very delicate point. It implies that the region of parameters for which the prediction\nis a good approximation to the error is not well characterized. Minimization of the approximating function may well give configurations that lie outside those boundaries and that in practice give a much worse error. \n\n- Appendix D. The section explains how to obtain the fit coefficient by varying only a few dimensions at a time. \nUnfortunately, experimental details (e.g. number of points used) are missing. \nNo indication is given of the minimum number of points that one has to acquire in order to have robust fit. \nThe main concern here is that the fitted parameters, and the solution of the minimization problem in Section 6 as well,  may be very unstable until a very high number of points is acquired.\n\n- Since the construction of the fitting function relies on a high number of point acquisitions to perform the fit,\nit seems that the motivating question \"Given a family of neural networks, which should we prune (and by how much) to obtain the network\nwith the smallest parameter-count such that its error does not exceed some threshold \u000f k ?\"\ncould be better answered by direct black-box optimization or pruning. Therefore the applicability of this\ntheoretical framework seems very limited. \n\nMinor Comments:\n\n- Fig.3: would you consider adding depth vs width? Does the invariant w*l^\\alpha = v hold? I'm aware that discretization could be a problem.\n- pag. 2: \"To achieve sparsity levels beyond 20%\" -> \"To achieve density levels below 80%\"\n- pag. 3: \"has been fit\" -> \"has been fitted\"\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JIANHEB56t", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper summary\n\nThe authors propose a functional approximation to the error of pruned convolutional neural networks as a function of network hyperparameters. This functional approximation depends on a number of hyperparameters that are fit on the error of already trained and pruned networks on a certain task (in this case, image classification on CIFAR-10 and ImageNet are the tasks under consideration). The authors demonstrate that this fit is very accurate over many orders of magnitude, which demonstrates their hypothesis on the power law nature of the error distribution as a function of the hyperparameters under consideration.\n\n---------------------------------------------------------------------------------------------------------------------------\nPositives and negatives\n\n+The paper is very well written. It is very easy to follow the author’s argument and the figures illustrate the point in a concise manner.\n+The experimental section is very strong. The authors do a good job of motivating their hypothesis with empirical data, and explaining why they propose a power law.\n+After proposing the power law hypothesis, the authors fit the expression on a large amount of data, and convincingly show that the power law expression holds over multiple orders of magnitude.\n-The contribution of this paper is not as significant as I was lead to believe after reading the title and the abstract. While the authors have convinced me that the behavior of a network after pruning under different densities does follow a power law, the expression they derive depends on fitting 5 hyperparameters (equation 2), and after the fit can only be used only for that specific architecture and dataset.\n-The generalization of this expression is not well explored. The authors only consider one type of CNN and two datasets. Trying different CNN architectures and datasets (small datasets such as SVHN, mnist or fashion-mnist would have been fine, as long as quite different architecture types would have been probed).\n\n---------------------------------------------------------------------------------------------------------------------------\nRecommendation\n\nI recommend a weak accept for this paper, in light of the following considerations: the paper is well written and it provides an interesting insight (the power law structure of the error as networks are pruned), the paper’s formula could be useful to applied practitioners. However, I believe the way the results are presented are strongly overstated. I would like to see the abstract changed to reflect that the functional approximation derived is an empirical fit dependent on architecture and task; and I would like to see a little more variation in network architectures investigated. If those issues are addressed I would be willing to upgrade my recommendation.\n\n---------------------------------------------------------------------------------------------------------------------------\nQuestions\n\n* I am a bit confused as to why n is a hyperparameter in eq 2 at all as it only seems to feature indirectly via the error. Could you add a bit more explanation as to why that is considered?\n* Given that the formula is fitted with empirical data I find it surprising that the study of fit quality as a function of data points is relegated to the appendix. I think this point is important enough to feature in the main text, and would like to see results as the number of points trends towards 5 (the minimum number of points for which we’d expect a consistent fit). Maybe a plot with fit residual as a function of fit points?\n\n---------------------------------------------------------------------------------------------------------------------------\nFeedback (not related to the score)\n\n* Figure 3 is not very informative. I guess the point is to compare the quality of the fit contours with the empirical data. In that case the information about the fit is not enough ( a single line). I would rework the figure to contain full iso-lines for both fit and empirical data. And the caption could be more informative too (why do we need to see the density/depth plane and density/width plane if they are almost identical)?\n* In Eq. 1, it would have been useful if p had been introduced in the notation section.\n* In figure 4, please add legends to the different colors in each plot.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a functional approximation of the error of ResNets and VGGs pruned with IMP and SynFlow on CIFAR-10 and ImageNet, showing that it is predictable in terms of an invariant tying width, depth, and pruning level.  In particular, it formulates the test error as a function of the density of the network after pruning and identifies a low-density high error plateau, a high-density low error plateau, and a power-law behavior for intermediate density. It further demonstrates that networks of different sparsities are freely interchangeable. The paper provides an interesting insight on the power law structure of the error as networks are pruned, however the results are very limited to specific types of networks (ResNets and VGGs), pruning methods (IMP and SynFlow) and datasets (CIFAR-10, ImageNet). Hence, it's not clear if the proposed functional approximation generalizes to other network families, pruning methods, and datasets. I understand that adding a new architecture or dataset is expensive, but fitting the proposed scaling law (the five parameters) requires pruning only a small number of networks, as mentioned by the authors. Comparing the calculated error and the actual error of the pruned network for different architectures and datasets can help verify the findings in the paper, and significantly widens its scope.
Decision: Reject