Robust Pruning at Initialization
Authors: Soufiane Hayou
Jean-Francois Ton
Arnaud Doucet
Yee Whye Teh
Venue: ICLR 2021 Poster (2021)
Keywords: Pruning
Initialization
Compression

Abstract: Overparameterized Neural Networks (NN) display state-of-the-art performance. However, there is a growing need for smaller, energy-efficient, neural networks to be able to use machine learning applications on devices with limited computational resources. A popular approach consists of using pruning techniques. While these techniques have traditionally focused on pruning pre-trained NN (LeCun et al.,1990; Hassibi et al., 1993), recent work by Lee et al. (2018) has shown promising results when pruning at initialization. However, for Deep NNs, such procedures remain unsatisfactory as the resulting pruned networks can be difficult to train and, for instance, they do not prevent one layer from being fully pruned. In this paper, we provide a comprehensive theoretical analysis of Magnitude and Gradient based pruning at initialization and training of sparse architectures.  This allows us to propose novel principled approaches which we validate experimentally on a variety of NN architectures.

Published as a conference paper at ICLR 2021
ROBUST PRUNING AT INITIALIZATION
Soufiane Hayou, Jean-Francois Ton, Arnaud Doucet & Yee Whye Teh
Department of Statistics
University of Oxford
United Kingdom
{soufiane hayou, ton, doucet, teh]@stats. ac.. uk
ABSTRACT
Overparameterized Neural Networks (NN) display state-of-the-art performance. However, there is a growing need for smaller, energy-efficient, neural networks to be able to use machine learning applications on devices with limited computational resources. A popular approach consists of using pruning techniques. While these techniques have traditionally focused on pruning pre-trained NN (LeCun et al., 1990; Hassibi et al., 1993), recent work by Lee et al. (2018) has shown promising results when pruning at initialization. However, for Deep NNs, such procedures remain unsatisfactory as the resulting pruned networks can be difficult to train and, for instance, they do not prevent one layer from being fully pruned. In this paper, provide comprehensive theoretical analysis of Magnitude and Gradient based pruning at initialization and training of sparse architectures. This allows to propose novel principled approaches which we validate experimentally on variety of NN architectures.
INTRODUCTION
Overparameterized deep NNs have achieved state of the art (SOTA) performance in many tasks (Nguyen and Hein, 2018; Du et al., 2019; Zhang et al., 2016; Neyshabur et al., 2019). However, it is impractical implement such models on small devices such as mobile phones. To address this problem, network pruning is widely used to reduce the time and space requirements both at training and test time. The main idea to identify weights that do not contribute significantly to the model performance based on some criterion, and remove them from the NN. However, most pruning procedures currently available can only be applied after having trained the full NN (LeCun et al., 1990; Hassibi et al., 1993; Mozer and Smolensky, 1989; Dong et al., 2017) although methods that consider pruning the NN during training have become available. For example, Louizos al. (2018) propose an algorithm which adds Lo regularization on the weights to enforce sparsity while Carreira-Perpitaa and Idelbayev (2018), Alvarez and Salzmann (2017); Li et al. (2020) propose the inclusion of compression inside training steps. Other pruning variants consider training a secondary network that learns a pruning mask for a given architecture (Li et al. (2020); Liu et al. (2019)).
Recently, Frankle and Carbin (2019) have introduced and validated experimentally the Lottery Ticket Hypothesis which conjectures the existence of a sparse subnetwork that achieves similar performance to the original NN. These empirical findings have motivated the development of pruning at initialization such as SNIP (Lee et al. (2018)) which demonstrated similar performance to classical Importantly, pruning at initialization never requires
pruning methods of pruning-affer-traiiing training the complete NN and is thus more memory efficient, allowing to train deep NN using limited computational resources. However, such techniques may suffer from different problems. In particular, nothing prevents such methods from pruning one whole layer of the NN, making it untrainable. More generally, it is typically difficult to train the resulting pruned NN (Li et al., 2018). To solve this situation, Lee et al. (2020) try to tackle this issue by enforcing dynamical isometry using orthogonal weights, while Wang et al. (2020) (GraSP) uses Hessian based pruning to preserve gradient flow. Other work by Tanaka et al. (2020) considers data-agnostic iterative approach using the concept of synaptic flow in order to avoid the laler-collapse phenomenon (pruning a whole layer). In our work, we use principled scaling and re- parameterizztion solve this issue, and show numerically that algorithm achieves SOTA performance on CIFAR1O, CIFAR100, TinyImageNet and ImageNet in some scenarios and remains competitive in others.

---

Published as a conference paper at ICLR 2021
Table I: Classification accuracies CIFARIO for Resnet with varying depths and sparsities using SNIP (Lee et al. (2018)) and our algorithm SBP-SR
ALGORITHM
90%
96%
98%
39.5%
99:955
RESNEY32
SNIP
92.26
1.36=0.33 0.32
$7.78
0.16
77.56:10.36
9,98
SBP-SR
91.21
0:300
0.35
79.54::1.12
RESNE150
SNIP
01166=0.13
92.12=0.34
89.26 0.23
80.49=2.44
19.98=14.12
SBP-SR
92,05
0.06
92.742 0.32
89.57
0.21
82.68:00.52
1..76::1.82
RESNET104
SNIP
92.98
33.63-333227
10.119
SBP-SR
94.69 0.13
93.88
0.17
92.08
0.14
87.47.0.225
72.70:00488
In this paper, provide novel algorithms for Sensitivity -Bsed Pruming (SBP), i.c. pruning schemes that prune a weight W based on the magnitude of IW 8C at initialization where L. is the loss. Experimentally, compared other available one-shot pruning schemes, these algorithms provide state-of the-art results (this might not be true in some regimes). Our work is motivated by new theoretical analysis of gradient back-propagation relying on the mean-field approximation of deep NN (Hayou et al., 2019; Schoenholz et al., 2017; Poole et al., 2016; Yang and Schoenholz, 2017; Xiao al., 2018; Lee et al., 2018; Matthews al., 2018). Our contribution is threefold:
atV
For deep fully connected FeedForward NN (FFNN) and Convolutional NN (CNN), it has been previously shown that only an initialization on the so-called Edge of Chaos (EOC) make models trainable; see e.g. (Schoenholz et al., 2017; Hayou et al., 2019). For such models, we show that an EOC initialization also necessary for SBP to be efficient. Outside this regime, one layer can be fully pruned.
For these models, pruning pushes the NN out of the EOC making the resulting pruned model difficult to train. We introduce a simple rescaling trick to bring the pruned model back in the EOC regime, making the pruned NN easily trainable.
Unlike FFNN and CNN, we show that Resnets are better suited for pruning at initialization since they 'live' on the EOC by default (Yang and Schoenholz, 2017). However, they can suffer from exploding gradients, which we resolve by introducing re- parameterization, called "Stable Resnet' (SR). The performance of the resulting SBP-SR pruning algorithm illustrated in Table I: SBP-SR allows for pruning up to 99.5% of ResNet104 on CIFARIO 10 while still retaining around 87% test accuracy.
The precise statements and proofs of the theoretical results are given in the Supplementary. Appendix H also includes the proof of weak version the Lottery Ticket Hypothesis (Frankle and Carbin, 2019) showing that, starting from randomly initialized NN, there exists subnetwork initialized on the EOC.
SENSITIVITY PRUNING FOR FFNN/CNN AND THE RESCALING TRICK
2.1
SETUP AND NOTATIONS
Let be input in Rd. A NN of depth L is defined by
)'(x) = FiW"",
-/-((()) + BB, 151SL,
(1)
where (²) the vector of pre-activations, W and B¹ are respectively the weights and bias of the 7th layer and Fi is mapping that defines the nature of the layer. The weights and bias are initialized with I in N'0 oz 2//1)), where v is a scaling factor used to control the variance of y/ AO0 af). Hereafter, M, denotes the number of weights in the 1th layer, & the activation and Bd Rid
function and (m n)] == {m, m 1,....n} for m S n. Two examples of such architectures are:
Fully connected FFNN. For FENN of depth L and widths (Ni)osigL, we have is Ni-1- Mi = 1 N₂ and
N11 W W/ + B for l 2 2.
(x) Σ 1=1
Whan + Bl, x(x)=
Σ
(2)
1=1
2

---

Published as a conference paper at ICLR 2021
CNN. For ID CNN of depth L, number of channels (ni)ss and number of neurons per channel (N we have
14
my Σ 1=1 BEkery
(1)
E
Σ Σ
W Wis (x) [
Σ
w Wis.o + +b/, for / 2 2,
1=1 BEker!
(3) the neuron location, ker = (-kz ky] is the filter range, and 2k + 1-1s is the filter size. To simplify the analysis, we assume hereafter that Ni N and for all Here, we have t 14-1 (2k 1) and Mi 14-14 (2k + 1). We assume periodic boundary conditions; so vi,a = vi,+N = -- Generalization to multidimensional convolutions is straightforward.
where i E [1 mi] is the channel index, [0: N211] 1]
When no specific architecture is mentioned, (W))ssigM, M, denotes the weights of the 1th layer. In practice, a pruning algorithm creates binary mask 8 over the weights force the pruned weights to be zero. The neural network after pruning is given by
(4) where is the Hadamard (i.e. element-wise) product. In this paper, focus pruning initialization. The mask is typically created by using a vector g of the same dimension as W using mapping of choice (see below), to the top & values in the sequence (g)),,) where k is fixed by the sparsity that we want to achieve. There are three popular types of criteria in the literature:
y' (z) = Fi(8' a W W/',y/-(()) (x))++++
then prune the network by keeping the weights that correspond
Magnitude based pruning (MBP): We prune weights based on the magnitude [W
Sensitivity based pruning (SBP): We prune the weights based on the values of IW &C 3t where L
is the loss. This is motivated by Lw x Lw= + W ac used in SNIP (Lee et al. (2018)).
aW
Hessian based pruning (HBP): We prune the weights based on some function that uses the Hessian of the loss function as in GraSP (Wang al., 2020).
In the remainder of the paper, we focus exclusively on SBP while our analysis of MBP is given in Appendix E. We leave HBP for future work. However, include empirical results with GraSP (Wang et al., 2020) in Section 4.
Hereafter, we denote by the sparsity, i.e. the fraction of weights want to prune. Let A be the set of indices the weights in the 1th layer that are pruned, i.e. A = {i [1 Mi], s.t. 8 = 0}. We define the critical sparsity Ser by
Ser min{s E (0, s.t. |A = Mr).
where |Ay] is the cardinality of A,. Intuitively, Ser represents the maximal sparsity we are allowed to choose without fully pruning at least one layer. Ser is random as the weights are initialized randomly. Thus, we study the behaviour of the expected value E[ser] where, hereafter, all expectations are taken w.rt. to the random initial weights. This provides theoretical guidelines for pruning at initialization.
For all / E [1 L). we define by N where N > 0. and G > O such that Mr C where we recall that by is a scaling factor controlling the variance of y and Mj is the number of weights in the 1th layer. This notation assumes that, in each layer, the number of weights is quadratic in the number neurons, which is satisfied by classical FFNN and CNN architectures.
2.2 SENSITIVITY-BASEI PRUNING (SBP)
SBP is data-dependent pruning method that uses the data to compute the gradient with backpropa- gation at initialization (one-shot pruning). We randomly sample a batch and compute the gradients of the loss with respect each weight. The mask is then defined by 8f I([W? DC
aw! > t.x,, where
t. W sw (1e)) and k, = (1 - s) E Mt and IW sw (ks) is the with order statistics of the sequence ([W) aw? DIsISLISIMM.
ac
However, this simple approach suffers from the well-known exploding/vanishing gradients problem which renders the first/last few layers respectively susceptible to be completely pruned. We give a formal definition to this problem.
3

---

Published as a conference paper at ICLR 2021
Definition 1 (Well- codeiloond & ill-connitioned NN). Let my BilWi ac aw! fl I [1 L]. We say that the NN is well-conditioned if there exist A, B > 0 such that for all L 2 1 and E [1 L] we have A S m//m S B, and it is ill-conditioned otherwise.
Understanding the behaviour of gradients at initialization is thus crucial for SBP to be efficient. Using mean-field approach, such analysis has been carried out in (Schoenholz et al., 2017; 7; Hayou et al., 2019; Xiao et al., 20 Poole et al., 2016; Yang, 2019) where it has been shown that an initialization known the EOC is beneficial for DNN training. The mean-field analysis of DNNs relies on two standard approximations that we will also use here.
Approximation 1 (Mean-Field Approximation). When No > 1 for FFNN my >> for CNN, we use the approximation of infinitely wide NN. This means infinite number of neurons per layer for fully connected layers and infinite number of channels per layer for convolutional layers.
Approximation 2 (Gradient Independence). The weights used for forward propagation are indepen- dent from those used for back- prooppropagation.
These two approximations are ubiquitous in literature on the mean-field analysis of neural networks. They have been used to derive theoretical results on signal propagation (Schoenholz et al., 2017 7: Hayou et al., 2019; Poole et al., 2016; Yang. 2019; Yang and Schoenholz, 2017; Yang et al., 2019) and are also key tools in the derivation of the Neural Tangent Kernel (Jacot et al., 2018; Arora et al., 2019; Hayou et al., 2020). Approximation simplifies the analysis of the forward propagation as allows the derivation of closed-fome formulas for covariance propagation. Approximation 2 does the same for back- propaggatogg..nn.... See Appendix A for a detailed discussion of these approximations. Throughout the paper, we provide numerical results that substantiate the theoretical results that derive using these two approximations. We show that these approximations lead to excellent match between theoretical results and numerical experiments.
Edge of Chaos (EOC): For inputs x, ,', let c'(x,2z) ) be the correlation between (x) and y (x²). From (Schoenholz et al.. 2017: Hayou et al., 2019), there exists so-called correlation function that depends on (aw, ox) such that (x, x²) = f(e((x, x')). Let x Tw) [()).. The EOC the set of hyperparameters (Tw., σ6) satisfying X( )w)) 1. When X( )w) 1, we are in the Chaotic phase, the gradient explodes and (I. converges exponentially to some c < 1 for A x' and the resulting output function is discontinuous everywhere. When X aw) < 1, we are in the Ordered phase where e' (ar, x²) converges exponentially fast to 1 and the NN outputs constant functions. Initialization on the EOC allows for better information propagation (see Supplementary for more details).
Hence, by leveraging the above results, we show that an initialization outside the EOC will lead to an ill-conditioned NN.
Theorem (EOC Initialization is crucial for SBP). Consider NN of type (2) or (3) (FFNN or CNN).
Assume (aw, σb) are chosen on the ordered phase, i.e. X(a,, σw) < 1, then the NN is ill-conditioned. Moreover, we have
E[Ser] S 1 / (1+ log(kLN33
+0
RVVLN
R2
where k. = 1log x(o If (aw:Dt) are on the EOC, i.e. X(ar,, (w),,ow) = 1, then the NN is well-conditioned. In this case, K = O and the above upper bound no longer holds.
The proof of Theorem relies on the behaviour of the gradient norm at initialization. On the ordered phase, the gradient norm vanishes exponentially quickly as it propppropag,tes, thus resulting in an illcoonditioned network. We use another approximation for the sake of simplification of the proof (Approximation 3 in the Supplementary) but the result holds without this approximation although the resulting constants would be bit different. Theorem 1 shows that the upper bound decreases the farther ( aw)) is from 1, i.e. the farther the initialization is from the EOC. For constant width FENN with L = 100, N = 100 and ạ = 0.2, the theoretical upper bound is E[(er] S 27% while we obtain E[sor] x 22% based on 10 simulations. A similar result can be obtained when the NN is initialized on the chaotic phase; in this case too, the NN is ill-conditioned. To illustrate these results, Figure shows the impact of the initialization with sparsity s = 70%. The dark area in Figure ((b) corresponds to layers that are fully pruned in the chaotic phase due to exploding gradients. Using an EOC initialization, Figure ((a) shows that pruned weights are well distributed in the NN, ensuring that no layer is fully pruned.
4

---

Published as a conference paper at ICLR 2021
6.0
6.7
60
65
24
03
26
(a) Edge of Chaos
(b) Chaotic phase
Figure Percentage weights kept after SRP applied to randomly initialized FFNN with depth 100 and width 100 for 70% sparsity on MNIST. Each pixel (? corresponds to neuron and shows the proportion of connections to neuron (i.j) that have not been pruned. The EOC (a) allows us to preserve uniform spread of the weights, whereas the Chaotic phase (b), due exploding gradients, prunes entire layers.
2.3 TRAINING PRUNED NETWORKS USING THE RESCALING TRICK
We have shown previously that an initialization the EOC is crucial for SBP. However, we have not yet addressed the key problem of training the resulting pruned NN. This can be very challenging in practice (Li al., 2018), especially for deep NN.
Consider as an example a FFNN architecture. After pruning, we have for an input x:
(((x) = W (0 (x)) B% for 2
(5)
where 5 is the pruning mask. While the original NN initialized on the FOC was satisfy- ing (2,
(z, for (1) X )w) 1, the pruned architecture leads to af (x, Spuuea (x, x²)) with pprnne (1) * 1, hence pruning destroys the EOC. Consequently, pruned NN will difficult to train (Schoenholz et al., 2017; Hayou et al., 2019) especially it is deep. Hence, we propose to bring the pruned NN back on the EOC. This approach consists of rescaling the weights obtained after SBP each layer by factors that depend on the pruned architecture itself.
Proposition 1 (Rescaling Trick). Consider a NN of type (2) or (3) (FFNN CNN) initialized on the EOC. Then, after pruning, the pruned NN not initialized on the EOC anymore. However, the rescaled pruned NN
=F(p 8' W -- + BB, forl21, 1,
(6)
where
(W)) for FFNN, P (E[m-- 11,9) ( 2o),. for CNN,
(7)
initialized on the EOC. (The scaling is constant across j).
The scaling factors in equation 7 are easily approximated using the weights kept after pruning. Algorithm (see Appendix I) details a practical implementation of this rescaling technique for FFNN. We illustrate experimentally the benefits of this approach in Section
SENSITIVITY-BASE PRUNING FOR STABLE RESIDUAL NETWORKS
Resnets and their variants (He et al., 2015; Huang et al., 2017) are currently the best performing models on various classification tasks (CIFARIO, CIFARI00 ImageNet etc (Kolesnikov et al., 2019)). Thus, understanding Resnet pruming at initialization of crucial interest. Yang and Schoenholz (2017) showed that Resnets naturally 'live" on the EOC. Using this result, show that Resnets are actually better suited to SBP than FFNN and CNN. However, Resnets suffer from an exploding gradient problem (Yang and Schoenholz, 2017) which might affect the performance of SBP. We
5

---

Published as a conference paper at ICLR 2021
Proniin furter ochectt
hearn Sast the eoccting 100 that
Fou We are aoing
Figure 2: Percentage of non-pruned weights per layer in a ResNet32 for our Stable ResNet32 and standard Resnet32 with Kaiming initialization on CIFARIO. With Stable Resnet, we prune less aggressively weights in the deeper layers than for standard Resnet.
address this issue by introducing a new Resnet parameterizaatin. Let standard Resnet architecture be given by
(²) - F(W' .)), (((x) = - F(W", w/ for 1 2,
(8)
where F defines the blocks of the Resnet. Hereafter, we assume that F is either of the form (2) or (3) (FFNN or CNN).
The next theorem shows that Resnets are well-conditioned independently from the initialization and thus well suited for pruning at initialization.
Theorem 2 (Resnet are Well-Conditioned) Consider a Resnet with either Fully Connected or Convolutional layers and ReLU activation function. Then for all T. > 0, the Resnet is well- conditioned. Moreover, for all E {1, L}, we have m = O )
The above theorem proves that Resnets are always well-conditioned. However, taking closer look at m', which represents the variance of the pruning criterion (Definition 1), we see that it grows exponentially in the number of layers Therefore, this could lead 'higher variance of pruned networks' and hence high variance test accuracy. To this end, we propose a Resnet parameterization which we call Stable Resnet. Stable Resnets prevent the second moment from growing exponentially as shown below.
Proposition 2 (Stable Resnet). Consider the following Resnet parameterization (x(x) y' + 1
.T. F(W. for 22
then the NN is well-conditioned for all ow > O. Moreover, for all S we have ml (T.
In Proposition 2, L is not the number of layers but the number of blocks. For example. ResNet32 has 15 blocks and 32 layers, hence L 15. Figure shows the percentage of weights in each layer kept after pruning ResNet32 and Stable ResNet32 at initialization. The Tumpu correspond to limits between sections in ResNet32 and are caused by max-pooling. Within each section, Stable Resnet tends to have more uniform distribution of percentages of weights kept after pruming compared to standard Resnet. In Section 4 we show that this leads to better performance of Stable Resnet compared to standard Resnet. Further theoretical and experimental results for Stable Resnets are presented in (Hayou et al., 2021).
In the next proposition, establish that, unlike FFNN or CNN, we do not need rescale the pruned Resnet for to be trainable as it lives naturally on the EOC before and after pruning. Proposition 3 (Resnet live on the EOC even after pruning). Consider Residual NN with blocks of type FFNN or CNN. Then, after pruming. the pruned Residual NN is initialized on the EOC.
EXPERIMENTS
In this section, we illustrate empirically the theoretical results obtained in the previous sections. We validate the results on MNIST, CIFAR1O, CIFAR 100 and Tiny ImageNet.
4.1 INITIALIZATION AND RESCALING
According to Theorem 1, an EOC initialization is necessary for the network to be well-conditioned. We train FENN with tanh activation MNIST, varying depth I. {2, 22, 40, 60, 80, 100) and

---

Published as a conference paper at ICLR 2021
Sonay
Swary
(a) EOC Init & Rescaling
(b) EOC Init
(c) Ordered phase Init
Figure 3: Accuracy MNIST with different initialization schemes including EOC with rescaling. EOC without rescaling, Ordered phase, with varying depth and sparsity. This shows that rescaling be on the EOC allows train not only much deeper but also sparser models.
sparsity & E {10%, 20%. 90%). We use SGD with batchsize 100 and learning rate 10-3, which we found be optimal using grid search with an exponential scale of 10. Figure shows the test accuracy after 10k iterations for 3 different initialization schemes: Rescaled EOC, EOC, Ordered. On the Ordered phase, the model is untrainable when we choose sparsity s > 40% and depth L > 60 as one layer being fully pruned. For an EOC initialization, the set (s, L) for which NN are trainable becomes larger. However, the model still untrainable for highly sparse deep networks as the sparse NN is no longer initialized on the EOC (see Proposition 1). As predicted by Proposition 1, after application of the rescaling trick to bring back the pruned NN on the FOC, the pruned NN can be trained appropriately.
Table 2: Classification accuracies for CIFARIO and CIFARION 100 after pruning
CIFAR
CIFAR 100
SPARSITY
90%
96%
98%
90%
93%
98%
INO PRUNING)
74.64
OBD LECUN ET AL. (1990)
93.74
93.58
93.49
73,83
71.98
67.79
89.95:0.23
89.68:0.155
86.1310.21 25
63.13=2.94
64.5510..3
19.83=3.21
MBP
90.21=0.55
88.35:20775
86.83-20.22
67.07=0.31
64.92220.7
59.53=2.19
SNIP (2018)
0.332
87.78 +
0.52
0.15
55.70
GRASP WANG ET AL. (2020)
92.20=0.31
91.39:20.25
88.70:0.42
69.21 0.21
66.50
58.43
0.43
GRASP-SR
92. 02.
01.16:20.13
87.8 0.32
69. + 0.15
65.49
= 0.21
58.63 + 0.23
SYNFLOW TANAKA AL. (2020)
91677:0.17
58.73
SBP-SR (STABLE RuSNET)
92.56 0.06
91. = 0.30
88.25 =: 0.35
69,51 0.21
66.72 - 0.12
59.51 = 0.15
ResNet50 (NO FRUNING)
94,90
RANDOM PRUNING
85.11=4.51
88. 76:20.221
85.3240.49
60.2342..1 63.67=0.57
28.32=10.35
MBP
89.06
0.16
G8
0.21
55.21
SNIP
91.95 2 0.13
92.12 0.34
69.26 0.23
70.43 0.43
67.85 1.02
60.38 + 0.78
GRASP
92.10 0.21
91.74 0.35
89,97 0,25
70.53=0.32
67 84.8440.22 25
63.88=0.45
SYNFLOW
92.05
91
89.61 0.17
70.43=0.30
67.95-40.22
63.95-0.11
SBP-SR
92.05 1. 0.06
92.74 0.32
0.21 89.57
71.79 0.13
68.98 1. 0.15
64.45 :: 0.34
ResNet104 (NO PRUNING)
94.92
75.24
RANDOM PRUNING
89 89.80:20.33
87. 8..86:11.22
85.5242.12
66.73=1.32
64.98:10.11
30.31=4.51
MBP
90.05
88.95:00.5
87.83+11.21
69.57=0.35
64.31:10778
60.21=2.41
SNIP
93.25 0.53
92.98 0.12
91.58 0.19
71.94 + 0.22
68. 68.73--0.000
63.31 0.41
GRASP
93.06 + 0.11
92.93 19993:000 0.09
91.19:20.35
73.33=0.21
70.95 1112
60.9120.33
SYNFLOW
0.10
92.85
0.18
91.03 21.03---0:40
72.85=0.20
70.33
67.02=0.10
SBP-SR
94.69 0.13
93.88 + 0.17
92.08 0.14
74.17 0.11
71.84 + 0.13
67.73 # 0.28
4.2 RESNET AND STABLE RESNET
Although Resnets are adapted to SBP (i.e. they are always well-conditioned for all ow > 0). Theorem 2 shows that the magnitude of the pruning criterion grows exponentially w.r.t. the depth L. To resolve this problem we introduced Stable Resnet. We call our pruning algorithm for ResNet SBP-SR (SBP with Stable Resnet). Theoretically, we expect SBP-SR to perform better than other methods for deep Resnets according to Proposition 2. Table 2 shows test accuracies for ResNet32, ResNet50 and ResNet104 with varying sparsities experiments, we use a setup similar to (Wang et al., 2020), i.c we use SGD for 160 and 250 epochs for CIFAR 10 and CIFAR 100, respectively. We initial learning rate of 0.1 and decay it by 0.1
(90%. 95%, 98%) CIFAR10 and 1IFAR100. For all our
7

---

Published as a conference paper at ICLR 2021
1/2 and 3/4 of the number of total epoch. In addition, more stable and reliable test accuracies. As in (Wang et al., 2020), we adopt Resnet architectures where doubled the number of filters in each convolutional layer. As baseline, we include pruning results with the classical OBD) pruning algorithm (LeCun et al., 1990) for ResNet32 (train + prune repeat). We compare our results against other algorithms that prune at initialization, such as SNIP (Lee et al., 2018), which is SBP algorithm, GraSP (Wang et al., 2020) which is Hessian based pruning algorithm, and SynFlow (Tanaka et al., 2020), which is an iterative data-agnostic pruning algorithm. As we increase the depth, SBP-SR starts to outperform other algorithms that prune at initialization (SBP-SR outperforms all other algorithms with ResNet104 on CIFARIO and CIFAR 100). Furthermore, using GraSP on Stable Resnet did not improve the result of GraSP on standard Resnet, as our proposed Stable Resnet analysis only applies to gradient based pruning. The analysis of Hessian based pruning could lead to similar techniques for improving trainability, which we leave for future work.
all our experiments 3 times obtain
Table 3: Classification accuracies on Tiny ImageNet for Resnet with varying depths
ALGORITHM
85%
95% 90%
REsNET32
SBP-SR
57.25 0.09
55.67 +: 0.21
50.63++0.21
SNIP
$6.92 0.33
54.9910.37
49.48:10.44
GRASP
07.25-10.11
55.53+20.11 11
51.34:10,29
SYNFLOW
56.75=00009
55.60++0.07
51.50++.21
RESNET50
SBP-SR
59.8:10.18
57.7410.00
53,97:1.277
SNIP
58.91=0.23
56.15
51.1940.4
GRASP
58.46:1.229
57.4840.35
$2.5+0.41
SYNFLOW
59.31=00117
57.67:10.15
53.1440.31
RESNET104
SBP-SR
0..84-00113
61.96:+0.11
57.940.31
SNIP
59.94=0.34
58.14+0.28
54.9+00.2
GRASP 61.140.41
60.14:0.38
56.3610.51
SYNFLOW
61.71=0.08
60.81+1014
55.9140.43
To confirm these results, we also test SBP-SR against other pruning algorithms on Tiny ImageNet. We train the models for 300 training epochs to make sure all algorithms converge. Table 3 shows test accuracies for SBP-SR, SNIP, GraSP, and SynFlow for E (85%, 90%. 95% J. Although SynFlow competes or outperforms GraSP in many cases, SBP-SR has clear advantage over SynFlow and other algorithms, especially for deep networks as illustrated on 0es
Additional results with ImageNet dataset are provided in Appendix F.
4.3 RESCALING TRICK AND CNNS
The theoretical analysis of Section 2 valid for Vanilla CNN i.c. CNN without pooling layers. With pooling layers, the theory of signal propagation applies to sections between successive pooling layers; each of those section can be seen as Vanilla CNN. This applies to standard CNN architectures such as VGG. As toy example,
show in Table 4 the test accuracy of pruned V-CNN with sparsity 8 = 50% on MNIST dataset. Similar to FFNN results in Figure 3, the combination of the EOC Init and the ReScaling trick allows for pruning deep V-CNN (depth 100) while ensuring their trainability.
Table 4: Test accuracy on MNIST with V-CNN for different depths with sparsity 50% using SBP(SNIP)
L L-10 10
L= 50
L 100
ORDERED PHASE INIT
98.12=0.11 13
10.0010.0
10. 10.00:10.0
BOC INIT EOC RESCALING
98.20=00.1
98.75=0.11
10.00:10.0
18.18+0.21
98.90=00.07
99.15#0.08
However, V-CNN is a toy example that is generally not used in practice. Standard CNN architectures such as VGG are popular among practitioners since they achieve SOTA accuracy on many tasks. Table shows test accuracies for SNIP, SynFlow, and our EOC+ReScaling trick for VGG16 on CIFAR1O 10. Our results are close the results presented by Frankle al. (2020). These three
8

---

Published as a conference paper at ICLR 2021
algorithms perform similarly. From theoretical point of view, ReScaling trick applies to vanilla CNNs without pooling layers, hence, adding pooling layers might cause a deterioration. However, we know that the signal propagation theory applies vanilla blocks inside VGG (i.e. the sequence of convolutional layers between two successive pooling layers). The larger those vanilla blocks are, the better ReScaling trick performs. We leverage this observation by training modified version of VGG, called 3xVGG16, which has the same number of pooling layers as VGGI6, and times the number of convolutional layers inside each vanilla block. Numerical results in Table show that the EOC initialization with the ReScaling trick outperforms other algorithms, which confirms our hypothesis. However, the architecture 3 is not a standard architecture and does not seem to improve much the test accuracy of VGG16. An adaptation of the ReScaling trick to standard VGG architectures would be of great value and left for future work.
Table Classification accuracy on CIFAR1O for VGG16 and VGG16 with varying sparsities
Al GORITHM
85%
90%
95%
VGG16
SNIP
93.09=0.1 11
92.97=0.08
92.61=0.11
SYNELOW
93.21=0.13
93.05=0.11
92.19:0.12
EOC RESCALING
93.15:10.12
92.90-0.155
92.70.10.06
3XVGG16
SNIP 93.30=0.10
93.12-0.20
92.85
SYNFLOW
93.95:00.13
92.91
02.70-10.20
EOC RESCALING
93.97=0.17
93.75-0.15
03.40=00166
Summary of numerical results. We summarize in Table 6 our numerical results. The letter 'C' refers to 'Competition" between algorithms in that setting, and indicates clear winner is found, while the dash means no experiment has been run with this setting. We observe that our algorithm SBP-SR consistently outperforms other algorithms in variety of settings.
Table 6: Which algorithm performs better? (according to results)
DATASET
ARCHITECTURE
85%
90%
95%
98%
CIFARIO
RESNET32
C
C
GRASP
RESNET50
C
SBP-SR
GRASP
RuSNET104
SBP-SR
SBP-SR
SBP-SR
VGG16
3XVGG16
ROC+RESC
EOC+RESC
EOC+RESC
CIFARIO0
RESNET32
SBP-SR
SBP-SR
SBP-SR SBP-SR SBP-SR
RESNET5O
SBP-SR
SBP-SR SBP-SR
RusNer104
SBP-SR
TINY IMAGENET
RisNer32
SYNPLOW
RESNET5O
SBP-SR
C
SBP-SR
RESNETI04
SBP-SR
SBP-SR
SBP-SR
5 CONCLUSION
In this paper, we have formulated principled guidelines for SBP at initialization. For FNNN and CNN, we have shown that initialization the EOC is necessary followed by the application of simple rescaling trick to train the pruned network. For Resnets, the situation markedly different. There no need for specific initialization but Resnets in their original form suffer from an exploding gradient problem. We propose an alternative Resnet parameterization called Stable Resnet, which allows for more stable pruning. Our theoretical results have been validated by extensive experiments on MNIST, CI,AROO, CIFAR100, Tiny ImageNet and ImageNet. Compared to other available one-shot pruning algorithms, we achieve of the-art results in many scenarios.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Alvarez, J. M. and M. Salzmann (2017). Compression-aware training of deep networks. In 31st Conference in Neural Information Processing Systems, pp. 856-867.
Arora, S., Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang (2019). On exact computation with an infinitely wide neural net. In 33rd Conference on Neural Information Processing Systems.
Carreira-Perpiñán M. and Y. Idelbayev (2018, June). Learning- net pruning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
Learning-compressine compression algorithms for neural
Dong, X., S. Chen, and S. Pan (2017). Learning to prune deep neural networks via layer-wise optimal brain surgeon. 31st Conference on Neural Information Processing Systems, pp. 4860-4874 4874.
Du, S., X. Zhai, B. Poczos, and Singh (2019). Gradient descent provably optimizes over- parameterized neural networks. In 7th International Conference Learning Representations.
Frankle. J. and M. Carbin (2019). The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference on Learning Representations.
Frankle, J., G. Dziugaite, D. Roy, and M. Carbin (2020). Pruning neural networks at initialization: Why are we missing the mark? arXiv preprint arXiv:2009.0857.
Hardy, G., J. Littlewood, and G. Pólya (1952). Inequalities, Volume 2. Cambridge Mathematical Library.
Hassibi, B., D. Stork, and W. Gregory (1993). Optimal brain surgeon and general network pruning. In IEEE International Conference on Neural Networks, pp. 293 299 vol.1.
Hayou, E. Clerico, B. He, G. Deligiannidis, A. Doucet, and J. Rousseau (2021). Stable resnet. In 24th International Conference on Artificial Intelligence and Statistics.
Hayou, S., A. Doucet, and Rousseau (2019). On the impact of the activation function on deep neural networks training. In 36th International Conference on Machine Learning.
Hayou, S., A. Doucet, and J. Rousseau (2020). Mean-fiell behaviour of neural tangent kernel for deep neural networks. arXiv preprint 1905
He, K., X. Zhang, S. Ren, and J. Sun (2015). Deep residual learning for image recognition. In IEEE
Conference on Computer Vision and Puttern Recognition (CVPR), pp. 770-778.
Huang, G., Z. Liu, L. Maaten, and K. Weinberger (2017). Densely connected convolutional networks.
In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2261-2269,
Jacot, A., F. Gabriel, and C. Hongler (2018). Neural tangent kernel: Convergence and generalization in neural networks. In 32nd Conference on Neural Information Processing Systems.
Kolesnikov, A., L. Beyer, X. Zhai, J. Puigcerver, J. Yung, S. Gelly, and N. Houlsby (2019). Large scale learning of general visual representations for transfer. arXiv preprint 19Xiv:1912.11370
LeCun, Y., J. Denker, and S. Solla (1990). Optimal brain damage. Advances in Neural Information Processing Sstems, pp. 598-605.
Lee, J., Y. Bahri, R. Novak, S. Schoenholz, J. Pennington, and J. Sohl-Dickstein (2018). Deep neural networks as Gaussian processes. In 6th International Conference on Learning Representations.
Lee, J., L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington (2019). Wide neural networks of any depth evolve as linear models under gradient descent. In 33rd Conference on Neural Information Processing Systems.
Lee, N., T. Ajanthan, S. Gould, and P. H. S. Torr (2020). A signal propagation perspective for pruning neural networks at initialization. In 8th International Conference on Learning Representations.
Lee. N., T. Ajanthan, and P. H. Torr (2018). Snip: Single-shot network pruming based on connection sensitivity. In 6th International Conference on Learning Representations.
10

---

Published as a conference paper at ICLR 2021
Li, H., A. Kadav, I. Durdanovic, H. Samet, and H. Graf (2018). Pruning filters for efficient convnets. In 6th International Conference on Learning Representations.
Li, Y., S. Gu, C. Mayer, L. V. Gool, and R. Timofte (2020). Group sparsity: The hinge between filter pruning and decomposition for network compression. Proceedings of the IEEE/CVE Conference on Computer Vision and Puttern Recognition, pp. 8018-8027.
Li, Y., Gu, K. Zhang, L. Van Gool, and R. Timofte (2020). Dhp: Differentiable meta pruning via hypernetworss. arXiv preprint arXiv:
Lillicrap, T., D. Cownden, D. Tweed, and Akerman (2016). Random synaptic feedback weights support error backpropagation for deep learning. Nature Communications 7(13276).
Liu, Z., H. Mu, X. Zhang, Z. Guo, X. Yang, K.-T. Cheng, and J. Sun (2019). Metapruning: Meta learning for automatic neural network channel pruning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 3296-3305.
Louizos, C., M. Welling, and D. Kingma (2018). Learning sparse neural networks through lo regularization. In 6th International Conference Learning Representations.
Matthews, A., Hron, M. Rowland, R. Turner, and Ghahramani (2018). Gaussian process behaviour in wide deep neural networks. In 6th International Conference on Learning Representa- tions.
Mozer, M. and P. Smolensky (1989). Skeletonization: A technique for trimming the fat from a network via relevance assessment. In Advances in Neural Information Processing Systems, pp. 107-115.
Neal, (1995). Bayesian Learning for Neural Networks, Volume 118. Springer Science & Business Media.
Neyshabur, B., Z. Li, S. Bhhjanappali,, Y. LeCun, and N. Srebro (2019). The role of over- parametrization generalization of neural networks. In 7th International Conference on Learning Representations.
Nguyen, Q. and M. Hein (2018), Optimization landscape and expressivity of deep CNNs. In 35th International Conference Machine Learning.
Pečarić, J., Proschan, and Y. Tong (1992). Convex Functions, Partial Orderings, and Statistical Applications. Academic Press.
Poole, B., S. Lahiri, M. Raghu, Sohl-Dickstein, and Ganguli (2016). Exponential expressivity in deep neural networks through transient chaos. In 30th Conference on Neural Information Processing Systems.
Puri, M. and S. Ralescu (1986). Limit theorems for random central order statistics. Lecture Notes- Monograph Series Vol. 8, Adaptive Statistical Procedures and Related Topics.
Schoenholz, S., J. Gilmer, S. Ganguli, and Sohl-Dickstein (2017). Deep information propagation. In 5th International Conference on Learning Representations.
Tanaka, H., D. Kunin, Yamins, and S. Ganguli (2020). Pruning neural networks without any data by iteratively conserving synaptic flow. In 34th Conference on Neural Information Processing Systems.
Van Handel, R. (2016). Probability in High Dimension. Princeton University. APC 550 Lecture Notes.
Von Mises, R. (1936). La distribution de la plus grande de n valeurs. Selected Papers Volumen II, American Mathematical Society, 271-294.
Wang, C., G. Zhang, and R. Grosse (2020). Picking winning tickets before training by preserving gradient flow. In 8th International Conference Learning Representations.
11

---

Published as a conference paper at ICLR 2021
Xiao, L., Y. Bahri, J. Sohl-Dickstein, S. S. Schoenholz, and P. Pennington (2018). Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. In 35th International Conference Machine Learning.
Yang, G. (2019). Scaling limits of wide neural networks with weight sharing: Gaussian process behav- ior, gradient independence, and neural tangent kemel derivation. arXiv preprini arXiv:1902.0477
Yang, G., J. Pennington, V. Rao. J. Sohl-Dickstein, and S. S. Schoenholz (2019). A mean field theory of batch normalization. In 7th International Conference on Learning Representations.
Yang, G. and S. Schoenholz (2017). Mean field residual networks: On the edge chaos. In 31st Conference in Neural Information Processing Systems, Volume 30, pp. 2869-2869.
Zhang, C., S. Bengio, M. Hardt, B. Recht, and O. Vinyals (2016). Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations.
12

---

Published as a conference paper at ICLR 2021
A DISCUSSION ABOUT APPROXIMATIONS AND 2
A. APPROXIMATION 1: INFINITE WIDTH APPROXIMATION
FeeaForward Neural Network
Consider a randomly initialized FFNN of depth L, widths (Nt) weights W rid NO )
and bias B sid N(O, of),, where (1, o²) denotes the normal distribution of mean μ and variance σ². For some input R., the propagation of this input through the network is given by
(x
Wij B
(10)
5=1
NL-1 v((x) Σ W 0(1 (x))
(x)) + B for 2
(11)
Where Φ R + R is the activation function. When we take the limit N1-1 - oc, the Central Limit Theorem implies that (x) is a Gaussian variable for any input æ. This approximation by infinite width solution results in an error of order (1/ V /Ni-1 (standard Monte Carlo error). More generally, an approximation the random process v.(.) by Gaussian process was first proposed by Neal (1995) in the single layer case and has been recently extended to the multiple layer case by Lee et al. (2018) and Matthews et al. (2018). We recall here the expressions of the limiting Gaussian process kernels. For any input x E TR. [[y(
that for any inputs x, x Rdd
(x, x') (lyl())//('))
of + a Elo (w)) (z))
=o + - Fo (z. (x, (x, n. (x',
where Fg is a function that only depends on Φ. This provides a simple recursive formula for the computation of the kernel n²; see, e.g., Lee et al. (2018) for more details.
Convolutional Neural Networks
Similar to the FFNN case, the infinite width approximation with ID CNN (introduced in the main paper) yields a recursion for the kernel. However, the infinite width here means infinite number of channels, and results in an error (/1/// The kernel in this case depends on the choice of the neurons in the channel and is given by
(x, x')
Elyi. (x) (x')) = of 2k +
Σ Beker
(w) (x)))
so that
22 2k
Ra (2, x') of +
Σ Fal x), 1 BatB + (x, x'), 2 a ( x()).
Beker
The convolutional kernel o has the 'self-averaging' property: i.e. kernels corresponding to different combination of neurons in the previous layer. However, it is easy simplify the analysis in this case by studying the average kernel per channel defined by A N Ea a "a Indeed, by summing terms in the previous equation and using the fact that we use circular padding, we obtain
average
the
R'(x, x'(x,'')= of o No
Fo (1, Ne. (x, (I, a (z)x))).
a.a'
This expression similar in nature to that of FFNN. We will use this observation in the proofs.
Note that our analysis only requires the approximation that, in the infinite width limit, for any two inputs 2,, x', the variables yf (ar) and y (ar) are Gaussian with covariance s² (x. x') for FFNN, and
13

---

Published as a conference paper at ICLR 2021
(x) and (x") are Gaussian with covariance Ka (x, for CNN. We do not need the much stronger approximation that the process (x) (x) for CNN) Gaussian process.
Residual Neural Networks
The infinite width limit approximation for ResNet yields similar results with an additional residual terms. It is straighforward to see that, in the case ResNet with FFNN-type layers, we have that
(x,x'') x¹) = xx'111x (x,,x') x²) + of + a F (n (x, x)) wo/---1xx (x, x'), x 1 x²)),
whereas for ResNet with CNN-type layers, we have that
( Na (z, (x, x²) + oo
(x,,x)) Fol x), aat (2 x')
" a + ( ,x')).
2k +
Beker
A.2 APPROXIMATION 2: GRADIENT INDEPENDENCE
For gradient back- propaggaton,,,,, an essential assumption in prior literature in Mean-Field analysis of DNNs is that of the gradient independence which is similar in nature the practice of feedback aligmment (Lillicrap et al., 2016). This approximation allows for derivation of recursive formulas for gradient back- pocc-propagation, and it has been extensively used in literature and verified empirically; references below.
Gradient Covariance back-propagation: this approximation was used to derive analytical formulas
for gradient covariance back-propagation in (Hayou et al., 2019; Schoenholz et al., 2017; Yang and Schoenholz, 2017: Lee et al., 2018; Poole et al., 2016; Xiao et al., 2018; Yang. 2019). was shown empirically through simulations that it is an excellent approximation for FFNN in Schoenholz et al. (2017), for Resnets in Yang and Schoenholz (2017) and for CNN in Xiao al. (2018).
Neural Tangent Kernel (NTK): this approximation was implicitly used by Jacot et al. (2018) to derive the recursive formula of the infinite width Neural Tangent Kernel (See Jacot et (2018), Appendix A.1). Authors have found that this approximation yields excellent match with exact NTK. was also exploited later in (Arora et al., 2019; Hayou et al., 2020) to derive the infinite NTK for different architectures. The difference between the infinite width NTK θ and the empirical (exact) NTK θ was studied in Lee et al. (2019) where authors have shown that ||e Ô| F O(N-1) where N is the width of the NN.
More precisely, use the approximation that, for wide neural networks, the weights used for forward propagation are independent from those used for pookppropagation. When used for the computation of gradient covariance and Neural Tangent Kernel, this approximation computation for standard architectures such as FFNN, CNN and ResNets, without BatchNorm in Yang (2019) (section D.5). Even with BatchNorm, in Yang al. (2019), authors have found that the Gradient Independence approximation matches empirical results.
proven give the exact
This approximation can be alternatively formulated as an assumption instead of an approximation as in Yang and Schoenholz (2017).
Assumption (Gradient Independence): The gradients are computed using an i.i.d. version of the weights used for forward propagation.
B PRELIMINARY RESULTS
Let x be an input in Rd In its general form, a neural network of depth L is given by the following set of forward propagation equations
v'(x) = y/ BB, IS1SL.
(12)
where y (x) is the vector of pre-activations and W and B' are respectively the weights and bias of the 7th layer. Fi a mapping that defines the nature of the layer. The weights and bias are initialized with o W dd (O, (i where en is scaling factor used control the variance of y' and Bi did N/(0, of)- Hereafter, we denote by M, the number of weights in the th layer, é the activation function and [n m] the set of integers (n, n + 1,...,m for & m. Two examples of such architectures are:
14

---

Published as a conference paper at ICLR 2021
Funne-ceneected Forard Neural Network (FFNN) For a fully connected feedforward neural network of depth L and widths (Nuossis the forward propagation of the input through the network is given by
d
v+(x) Σ
Wij + Bi:
j=1
(13)
NL11
((xx) = Σ
w
(x)) + B for 2.
j=1
Here, we have 21- N and Mr Ni
Convolutional Neural Network (CNN/ConvNett)
For a 1D convolutional neural network of depth I,, number of channels (nr)igz and number of neurons per channel (Nı)ISL- we have
R1-1
(z) = Σ
Σ
W Wig + +,j,
j=1 BEker
(14)
(x) = Σ
Σ
W
1 (1) + t/, forl 2 2,
BEkerz
where i E [1 my] is the channel index, E [0 N₁ - is the neuron location, ker: = [-k; ky the filter range and 2k: + the filter size. To simplify the analysis, we assume hereafter that N N and k = k for all I. Here, we have i = 12k + 1) and Mj = (2 + 1). We assume periodic boundary conditions, so vi.o = VaaNN V Vi Generalization to multidimensional convolutions is straighforward.
Notation:
Hereafter, for FFNN layers, we denote by (x) ) the variance of 3 (r) (the choice of the index is not crucial since, by the mean-field approximation, the random variables (x)())))))) are iid Gaussian variables). We denote by g (z. x²) the covariance between v (x) and yf (x'), and of (xxx²) the corresponding correlation. For gradient kuck-propagations for some loss function L. we denote by q' (z, 2²) the gradient covariance defined by q' (z, x²) E ac ovi
(x) Oc By! (z") Similarly,
(x() denotes the gradient variance at point
For CNN layers, we use similar notation accross channels. More precisely, we denote by da (x) the variance of vi.a, (x) (the choice of the index 1 is not crucial here either since, by the mean- field approximation, the random variables (v/,a (x))xe(IoN))) are iid Gaussian variables). We denote by Le (x, x²) the covariance between ( and vi.ar (x'), and (2,a((x,2') the corresponding correlation.
As in the FFNN case, we define the gradient covariance by (2r, x²)
E
OC Uvi.a
(I)
8C
(x')
Jut
B. WARMUP SOME RESULTS FROM MEAN-FIELD THEORY OF DNNS
We start by recalling some results from the reen-field theory of deep NNs.
B. COVARIANCE PROPAGATION
Covariance propagation for FFNN:
In Section A. presented the recursive formula for covariance propagation in FFNN, which derive using the Central Limit Theorem. More precisely, for two inputs x, x' E Rdd, we have
o (x,x0)) of - (c))ou
This can be rewritten
(x,x') of + o Φ (Vd(o)z)) & (Vdlo)(d-1z) 111111111/0 (dd1)11222)) )
15

---

Published as a conference paper at ICLR 2021
where c'-l := d (x,z)=,).
With a ReLU activation function, we have
on (a,xz)) -
where / is the ReLU correlation function given by (Hayou et al. (2019))
f(c) 1 π
(caresinc+ vI -²) 2
Covariance propagation for CNN:
Similar to the FENN case, it is straightforward to derive recusive formula for the covariance. However, this case, the independence is across channels and not neurons. Simple calculus yields
(1, = al (1)) of +
o
Σ BEker
2k
Using ReLU activation function, this becomes
(x, = 2h
Σ BEker
Covariance propagation for ResNet with ReLU
This case is similar to the non residual case. However, an added residual term shows up in the recursive formula. For ResNet with FFNN layers, we have
oh
oin
dxx,x') = o' (x, (x, of
and for ResNet with CNN layers, we have
o (2, (x, (2, oi 2k+1
Σ Vo (as
Beker
B.1.2 GRADIENT COVARIANCE BACK-PROPAGATIOE
Gradiant Covariance back prok-propngation for FFNN:
Let be the loss function. Let be input. The back propagation of the gradient is given by the set
of equations
N441
ac oyg = o'(2))
dC
Σ
w
Oul
1+1
Using the approximation that the weights used for forward propagation are independent from those used in backpropagation, we have as in Schoenholz et al. (2017)
N4 (x)
(x).
N
where = =
Gradient Covariance back-propagation for CNN: Similar to the FFNN case, we have that
Oc
OL Σ
oW! 1.j.8
Oyt.n
and
OL
OL
Σ
0y/t (3.0'((Va)))
W4+1
Oy!.n.
/=1
Beker
16

---

Published as a conference paper at ICLR 2021
Using the approximation of Gradient independence and averaging over the number of channels (using CLT) we have that
OC 2
o (V
OC
2
B
1=
Σ
E
Oyj,a
2k +
BEker
We can get similar recursion to that of the FFNN case by summing over a and using the periodic boundary condition, this yields
E Oc ay
OC
Σ
= ((2x(z))
Σ
B
].
Oy.,a
B.1.3 EDGE OF CIIAOS (EOC)
Let E Rd be an input. The convergence of (z) as increases has been studied by Schoenholz et al. (2017) and Hayou et al. (2019). In particular, under weak regularity conditions, is proven point q(0b, ow) > 0 independent of x as I +
that g' (x)) converges behaviour of the correlations d' (x,xx') between y' (z) and (xx' for any two inputs x and x' is also driven by (w): the dynamics of el is controlled by function f i.e. c f(c') called the correlation function. The authors define the EOC as the set of parameters (at, aw) such that o Elo' ((5,. Two) [)} 1 where Z ~ (O, 1). Similarly the Ordered, resp. Chaotic, phase defined by Eld' (V V 2)?] 1, resp. a 1o' (V Z.) 1. On the Ordered phase, the gradient will vanish as it backpropagates through the network, and the correlation c1(rr, x²) converges exponentially to 1. Hence the output function becomes constant (hence the name 'Ordered phase"). ) On the Chaotic phase, the gradient explodes and the correlation converges exponentially to some limiting value < 1 which results in the output function being discontinuous everywhere (hence the 'Chaotic' phase name). On the EOC, the second moment of the gradient remains constant throughout the backpropagation and the correlation converges to at a sub-exponential rate, which allows deeper information propagation. Hereafter, I will always refer the correlation function.
The asymptotic
1.1.4 SOME RESULTS FROM THE MEAN-FIELD THEORY DEEP FENNS
Let E E (0, 1) and B. = ((z, x') x')RR et (z, x < +} (For now B, is defined only for FFNN),
Using Approximation 1, the following results have been derived by Schoenholz et al. (2017) and Hayou et al. (2019):
There exist À > 0 such that suprer* Ig -ql S -
On the Ordered phase, there exists 7 >> 0 such that sup (xx,2") 1 S Se
On the Chaotic phase, For all e E (0, 1) there exist 7 > and < such that SuP(a,=") (xr, cl S x-1
For ReLU network on the EOC, we have
2
((x) xー1 +
(1 - x//3/2 + 0((1 =2)5/2).
3x
In general, have
f(x) = of + 02 E (Z
(15)
q
where Z(z) 2Zi + VI Zz and Z1, Zg are iid standard Gaussian variables.
On the EOC, have f'(1)= =1
On the Ordered, resp. Chaotic, phase have that (1( 1, resp. f'(1) >
For non-linear activation functions, f is strictly convex and f(1)
f is increasing [-1, 1).
17

---

Published as a conference paper at ICLR 2021
On the Ordered phase and EOC, has one fixed point which is 1. On the chaotic phase, has two fixed points: which is unstable, and E (0, 1) which a stable fixed point.
On the Ordered/Chaotic phase, the correlation between gradients computed with different inputs converges exponentially to 0 as we back- nack-progapagate the gradients.
Similar results exist for CNN. Xiao et al. (2018) show that, similarly to the FFNN case, there exists such that d' (x) converges exponentially to for all æ, a, and studied the limiting behaviour of correlation between neurons the same channel (x, (same input x). These correlations describe how features are correlated for the same input. However, they do not capture the behaviour of these features for different inputs (i.e. c2 (4r,2 x') where x'). We establish this result in the next section.
B.2 CORRELATION BEIIAVIOUR IN CNN IN THE LIMIT OF LARGE DEPTII
Appendix Lemma (Asymptotic behaviour of the correlation in CNN with smooth activation functions). We consider ID CNN. Let (ah, Tn) (IR+)2 and F x' be two inputs R4. (ob, ow) are either on the Ordered or Chaolic phase, then there exists 3 >> O such that
sup (2, -0= OEe-)t 0,,0!
where c = if (0b, σw) is in the Ordered phase, and E (0, 1) (o aw) in the Chaotic phase.
Proof. Let x A be two inputs and a, a' two nodes the same channel i. From Section B. 1, we have that
(x, Elyl, (x)vl (x'))
Σ
+ of.
2k
BEker
This yields
ca 2k +
Σ ((
BEker
where f is the correlation function.
We prove the result in the Ordered phase, the proof in the Chaotic phase is similar. Let (os, Tw, be in the Ordered phase and c/n mina, ca (Ir, x'). Using the fact that f is non-decreasing (section
B.I), we have that ca (I, x²) 2 26+1 Eneker d-1 dath,a' x²)) 2 f(c())) Taking the min again over a', we have e 2 f(cl-1). therefore d4p, is non-decreasing and converges to stable fixed point of f. By the convexity of f. the limit is (in the Chaotic phase, / has two fixed point, stable and 0 - unstable). Moreover, the convergence is exponential using the fact that 0 (1) 1. We conclude using the fact that supa,a Ida.rr (0, x') 1|
point
C PROOFS FOR SECTION 2 SBP FOR FFNN/CNN AND THE RESCALING TRICK
In this section, we prove Theorem and Proposition 1. Before proving Theorem state the degeneracy approximation.
Approximation 3 (Degeneracy on the Ordered phase). On the Ordered phase, the correlation d' and the variance q' converge exponentially quickly their limiting values 1 and q respectively. The degeneracy approximation for FFNN states that
Vx + x' (,,e(rx)))
Yx, (x)) =3
For CNN.
Vx x', # da 21
18

---

Published as a conference paper at ICLR 2021
Vz, d (2) q
The degeneracy approximation essential in the proof of Theorem as it allows us to avoid many unnecessary complications. However, the results holds without this approximation although the constants may be a bit different.
Theorem (Initialization crucial for SBP). We consider a FFNN (2) or a CNN (3). Assume (Ow)@h) are chosen on the ordered, i.e. X( Tw) then the NN is ill-condiioned. Moreover, have
1 7 -(1+ log(kLN2)
(
B[ser] S
+0
L
R2V
where = llg X 1/88. If (a 0b) are on the EOC, i.e. X(Ob, = 1, then the NN is well-conditioned. In this case, K. 0 and the above upper bound no longer holds.
Proof. We prove the result using Approximation 3.
Case : Fully connected Feedforward Neural Networks
To simplify the notation, assume that N₁ N and Mi N2 (i.e. oj = 1 and Çi for all I. We prove the result for the Ordered phase, the proof for the Chaotic phase is similar. Let Lo > 1, (0, to L 2 Lo and E & e, 1). With sparsity æ, keep h [(1 - LND weights. We have
Oc OW! 1j
P( ~)) 2 P(max [W]]
(ka))
where (Haa) is the hith order statistic of the sequence (lW || mwe |. 0,1
ac
0, (1.5) E [1:
We have
dc
ac 0y((a)
OW!
D
( aw!
FED
dL
Hy, (x)).
D
(x) FED
On the Ordered phase, the variance g' (z) and the correlation d' (xx x²) converge exponentially to their limiting values q. (Section B.1). Under the degeneracy Approximation 3, we have
Yx & x,, d,, x') Rv
Yr, (xx:)(())
Let (x(x) = El - 21 (the choice of i is not important since (x)) are iid Using these approximations, have that (x)) y (z') almost surely for all x'. Thus
0C 2
E
= B[o( Elo(vaZ)))d')))
Owi
where æ is an input. The choice of x is not important in our approximation. From Section 1.1.2, we have
d = 241 Ni+1
X.
N₁
Then we obtain
No 1-t oth x b-1 N
d =
1 x
where X = o' as we have assumed N: N. Using this result, we have
dc 2
A x
OW! ij
19

---

Published as a conference paper at ICLR 2021
where A El for input Recall that by definition, one has X < on the Ordered phase.
In the general case, i.c. without the degeneracy approximation on é' and q'. we can prove that
ac 2 aw bj
E
-(x"=1)
which suffices for the rest of the proof. However, the proof of this result requires many unnecessary complications that do not add any intuitive value to the proof.
In the general case where the widths are different, qf will also scale as x--1 up to a different
constant.
Now we want to lower bound the probability
Oc TW
P(max (
< t(ka)).
Let ((ta)) be the kidh order statistic of the sequence ( ]. It clear that ((ka) (koo), therefore
ac ow
1,2 (1.5) E [1
15
Oc
dC OWh ij
P(max [W]] (J
< (kx)) P(max [W
< ((+x))
ow!
Using Markov's 's inequality, we have that
OC P(
E
ac aw
2 a)
S
(16)
Tw!
a²
Note that Var(x 1- 8C
1) = A. In general, the random variables x
1-4 8c have law;
aw!
density fiy for all 1 > 1 + cL, (i,j) e [1: NJ3, such that f1 # O. Therefore, there exists a constant X such that for æ small enough.
Oc oW!
P(x
x) 2 1 Ax.
O 1/312 1
By selecting x
we obtain
x x x (11ck)
1/2
x1/2
X
Therefore, for L large enough, and all l cT. (i, E [1 Ni) [1: Nr-1), we have
PP(
dc
a1 e/212
2 1 -x
(62/211)
21 x
DwT
0-e/s)1-11 in inequality (16) yields
Now choosing = x
P(
ac
c/4)L
121 1/4
dw!
Since we do not know the exact distribution of the gradients, the trick is to bound them using
the previous concentration inequalities. We define the event B == { [1 N] [1
d].
awy < 1/9/// n [vl > 1 el, (i,j) [1 NJ
BC
ac
aw!
We have
dL
d
Pmmax b.
W
TW6
< f
(kz)
>
(max i.j
WW31
TWe
< ((kz)
B)P((B.
20

---

Published as a conference paper at ICLR 2021
But, by conditioning on the event B, we also have dc
P(max [
< ! (B) > P(max ( < (1118((()))))
Tw?
1.
where ee (kx)) is the k order statistic of the sequence [ eL, (i, E [1: N.
Now, as in the proof of Proposition 4 in Appendix E (MBP section), define J(,m min E (0, 1) Ve > y, m2 > Q 1- =1- 2-5 ) where 7% = < Since limç-22 7(m = 0. then there exists Se < such that 22,,2 = = +
As grows, 1. (kx) converges to the quantile of order I_c Therefore, I-c"
1
P(max [ <x (f 2 P(max 1)
W < Q
1- -11-12 2- 2-4 + 0
/LN2
- -
0
1
VLN2
Using the above concentration inequalities on the gradient, obtain
P(B) 2 (1 x"//4) (1 <2/22LN2
Therefore there exists constant > 0 independent of such that
P(B) 2 - nLN2
Hence, we obtain
P(ser 2 x) S N2
2-te
+ + LL/1 +01
/L
Integration of the previous inequality yields
1 I
N²
E[serl S t
+ 2-c + ?LN X cL/4 + O
1+7L
V
Now let K log(x)] and set log(
By the definition of rc., we have
Quc
1- 1-(1-2c mp 22
r
For the left hand side, we have
m nnQue 07I.. 1og(kLL22)
kT.
where >> 0 is the derivative at 0 of the function + Q.. Since nr. KLN2, we have 2x aN2 log(xLN3)
Which diverges as L goes to infinity. In particular this proves that the right hand side diverges and therefore we have that (1 xz.., )r converges to 0 as L goes to infinity. Using the asymptotic equivalent of the right hand side as L
co, we have
Q Q1 r " V -2 log((11 xxc.ma) )
7t. 1--./2 / -2 xc.)))
Therefore, we obtain
2log(=L
Q Q- 1--
1-1./2
kL
Combining this result to the fact that To Quenn
log(xLN kb
obtain
log (
7 ~
KL
21

---

Published as a conference paper at ICLR 2021
where 3 is positive constant. This yields
log(kLN22
P
1
E [cr]
KL LLN22og(HLLN') (1+ [[])
-0(
KL
2
VLN2
(1+ log(nIN2) 0
K
R2 VVVNN
where log(x) and ju a constant.
2. Case : Convolutional Neural Networks
The proof for CNNs in similar to that of FFNN once we prove that
Oc
- Ax 1-1
Ow! 18.8
where A is constant. We have that
ac
Σ
dL
ow!
dyka
13.8
and
0C
OL Wi+1 13.0
(v1,a)
Oy.
j=1 Beker
Using the approximation of Gradient independence and averaging over the number of channels (using CLT) we have that
UC 2
('' (VQZ)²1
Oc 1+1
1
}.
Oyl.a
2k +
Vv.a-8
BEker
Summing over and using the periodic boundary condition, this yields
OL
OC
Σ 1
=
X
Σ
E
Oyl
Oyh
1+1
Here also, on the Ordered phase, the variance q' and the correlation e' converge exponen- tially to their limiting values and respectively. As for FFNN, we use the degeneracy approximation that states
Yx + x', at a', do (ar 1,
gx()) q.
Using these approximations, we have
ac
2
E
Elo(V (x)
OW!
1,1.8
where (1(x) = E. Ei
oc
2,
for an input x. The choice of is not important in our
(x)
approximation.
From the analysis above, we have
1-!
so we conclude that
ØL
E
= A --
ow!
1,,88
where A (((((172))11(()))
22

---

Published as a conference paper at ICLR 2021
After pruning, the network is usually 'deep' in the Ordered phase in the sense that X = (1) < 1. To re-place on the Edge of Chaos, the Rescaling Trick.
Proposition 1 (Rescaling Trick). Consider NN of the form (2) (3) (FFNN CNN) initialized on the EOC. Then, after pruning, the sparse network is not initialized on the EOC. However, the rescaled sparse network
y'(x) F(p' o8 W o/ (x)) + B¹, for 2
(17)
where
Prj (W for FFNN of the form (2),
Pig.a VElm- 1. 28 (8..) for CNN of the form (3),
is initialized the EOC.
Proof. For two inputs x, x', the forward propagation of the covariance is given by
(xxx²)) x¹)
Ely((x)
N1-1
E
of
We have
7c
1
Oc 0v((x)
ow!
D
0y((x) ow
ij
Oc
(z)(x) (x))
D
Under the assumption that the weights used for forward propagation are independent from the weights used for back-propagation, W and ac (v{(z) are independent for all D. We also have that W!j and
(x)) are independent for all x D. Therefore, W!J and ac are independent for all 1, i. aw
This yields
where au = E (z0
(the choice of i, does not matter because they are iid). Unless we do not prune any weights from the 1t layer, have that a < 1.
These dynamics are the same as a FFNN with the variance of the weights given by o? = o an. Since the EOC equation is given by a o (VQ)) A in general. Hence, the network is no longer on the EOC and this could be problematic for training.
1, with the new variance, it is clear that
With the rescaling, this becomes
d'(2, = - (
=0 (z)))(t (<')) oo
Therefore, the new variance after re-scaling is 82 = 02. and the limiting variance q = g remains also unchanged since the dynamics the same. Therefore 0² Eld' (v = of Elo' ( = 1. Thus, the re-scaled network is initialized on the EOC. The proof is similar for CNNs.
23

---

Published as a conference paper at ICLR 2021
D PROOF FOR SECTION 3 SBP FOR STABLE RESIDUAL NETWORKS
Theorem (Resnet is well-conditioned), Consider a Resnet with either Fully Connected or Convo- lutional layers and ReLU activation function. Then for all ow the Resnet is well-conditioned. Moreover, for all E [I..... J.. m' = @((1 + )²)
Proof. Let us start with the case of a Resnet with Fully Connected layers. we have that
ac
1
Σ
ac 0y((x) aw 0zf(x)
ow
[D]
xED
1
dc
D
dy((z)
ZED
and the backpropagation of the gradient given by the set of equations
NE Σ
0C
ac
ac
6((1/)
W jz
oy!
0y
I+I
==1
Recall that ('(x) = [x))(x)) and ((x x²) = El
ac
for some inputs x, x'. We have that
(z)
(x)()")
a (1+ )
d'(x) = Blul (x)
2
and
(',,x')= (1 o E (1 (v/(=))) ((
We also have
OC
E
Σ than
aW!
D
where r! ",. = x') ((to) (z,x))) and f is defined in the preliminary results (Eq 15).
Let l E {1,2, } be fixed. We compare the terms e for l = k and I = L. The ratio between the two terms is given by (after simplification)
T- (1+ oh f(d(zz2))) (z,x")
I.
(1+ o
f(c'-1(zxxx))
We have that f'd x)) = (() = 1. A Taylor expansion of f near yields (', x')) =
1 1-1-1 + o(I-1) and f(d(x,, x)) =1 - sl-2 + oll (() (see Hayou et al. (2019) for more details).
Therefore, there exist two constants A, B 0 such that A 11 114 2 ((d((')))
< B for all L
(1+ " D
and l E {1,2.... L}. This yields
Oc 2
E
OW!
A <
B,
IV
ac BW 1J
which concludes the proof.
For Resnet with convolutional layers, we have
ac
ΣΣ
0L
OW 1..8
D
Oy. (x)
ZED
24

---

Published as a conference paper at ICLR 2021
and
0C
dL
ac
W
(V),a).
dyl
=
oyi,a
1+1
By δyj
j=1 BEker
Using the hypothesis of independence of forward and backward weights and averaging over the number of channels (using CLT), we have
Oc Recall the notation la (z,x') = El oui (x) Bo (
ac
f (2,
(2, x') To (I,
Σ
ght Tat tg
2(2k + 1)
Let K, = D be a vector in IR Writing this previous equation in matrix form, we obtain
Pur 2 (ca x2)
Ki = (1+
2(21: + 1)
and
0C
2
E
Σ
Σ
l (1,
OW!
D
13.3
I,,'ED ara
where (2) an (z, x') Sata (2) +or+)(()))
(f x'), Since we have
(1,,ar(1, - 1, then by fixing and letting L goes to infinity, it follows that
o2 KI ~ (1+ L-1
b- elet Kr.
and, from Lemma we know that
02 (1+
Vatol
- )1-
"0. 40.
Therefore, for a fixed k < L, we have the (I, ~ (1+ aat (t, (ee (tth,ar(1, This concludes the proof.
Proposition 2 (Stable Resnet), Consider the following Resnet parameterization
(x))=//
VT. --F("" F(W".g1)) for 1 2,
1
(18)
then the network is well-conditioned,.e for all choices of ow > 0. Moreover, for all I E {1, L} have m' = (.-
Proof. The proof similar to that of Theorem with minor differences. Let us start with the case of a Resnet with fully connected layers, we have
Ø 1 OW! ;j
Σ
OL 0v)(4) 0y,(x) aW! ig
DVL
D
RED
OL
(())1(()
DVLL
(y.(x)
RED
and the backpropagation of the gradient is given by
N dL
ac
ac
(1))
Σ
W
1+1 + vI
0yh
0y,
,y
[+1
1=1
25

---

Published as a conference paper at ICLR 2021
Recall that ('(x) [x) and (x,,'') = [l ac Oc for some inputs 2, x'. We have
ao)(ar)
d(x) = Ely (x)) 7 Blo
( - -1 (1+
21, ) (x)
and
(1,,x')= (1+ I (())))))))))))))))))0)0))))1))))
We also have
0C
E
Σ L,
aW!
L
where t x (( (x, and is defined in the preliminary results (Eq. 15).
Let (1, L.} be fixed. We compare the terms L for I k and L. The ratio between the two terms is given after simplification by
tk
IL (1 f(d (1,xx)x1) f(ct-
L
(1+ oz 2f. --
(2,=-1(2,21))
As in the proof of Theorem 2, we have that ('d x)) = 1, l'd (z, = 1 1-1 + o(l- and (x, x)) =1-2 + o(1-2). Therefore, there exist two constants A, > such that
1 (1+ c (r,ax) B for all and {1, ..., LJ. This yields
< (1+ y2-k
E
9C
OW!
A
S
B.
E
OW
Moreover, since (1+ 5z 2212 then m' = (1) for all fl,... L}. This concludes the proof.
For Resnet with convolutional layers, the proof is similar. With the scaling, we have
Oc
ΣΣ
OC
d (()))t0(x))
OW! 1J
vT|D
dy (x)
and
OC
OC
Σ OC W (1
Oy.
VL
dyj
j=1 BEker
Let (x, E Byg (a) By
Using the hypothesis of independence of forward and backward weights and averaging over the number of channels (using CLT) we have
8C
8C
(zr)).
20 (r
(x, Vora (I,,
glt1 Vat (2r (2,,
2(2k + +]]
Let K₁ = ((do x' ) (1) is vector in NR Writing this previous equation in matrix form, we have
2f (c U)K441,
Ki (I+
2(2k: 1)L
and
0c 2
E
=
Σ Σ (z, Z acad"
OW!
L|D
26

---

Published as a conference paper at ICLR 2021
where (2, = (x, (x)a (aa+)))(((()())))))))))))))
Since we have
(2, 1, then by fixing and letting L goes to infinity, we obtain
o L- eief K
K₁ LL (1 +
2L
and we know from Appendix Lemma (using 03 = 21.
for all (] that
V
= (1+ a
- 1-1
40..=
2L
Therefore, for fixed & < L, we have th (x, x') ~ (1 + 2t @tt (2,x²)) x')) which proves that the stable Resnet is well conditioned. Moreover, since (1
)
-. f(e fl (e)
o2 1-1 + 2i/ then m' O(L=') for all I. 2L
In the next Lemma, we study the asymptotic behaviour of the variance d/a We show that, a phenomenon self averaging shows that y becomes independent of a.
Appendix Lemma 2. Let RR., Assume the sequence (at,a)),a is given by the recursive formula
Σ
01 01-1,0 +
BEker
where Ag > for all B. Then, there exists
>> 0 such that for all x E R and a,
(z)) = (1+ ass)oa + O((1 + E ag)' (1)),,
3
3
where ag is a constant and the is uniform in a.
Proof. Recall that
01,a 01-1,a +
Σ
A901-1,048-
Beker
We rewrite this expression in matrix form
A UA
where A = (at,aaa is vector in R and U the the convolution matrix. As an example, for
k 1, U given by
1 +
Ao
A
0
0
X
A-1
1 + Ao
0
0
A-1
1 1 Xo
X1
U
0
0
A
1 +
A
A-1
1 Ao
is a circulant symmetric matrix with eigenvalues b1 b2 2 by... 2 by. The largest eigenvalue
of U is given by by 1 Eg Åg and its equivalent eigenspace is generated by the vector 61 VN 1I., 1) E R. This yields
' = + (()
where Ç = ==og(()) bt) Using this result, we obtain
b A (6 U0 AA ele7 Ao + O(e -e)
This concludes the proof.
27

---

Published as a conference paper at ICLR 2021
Unlike FFNN or CNN, we do not need to rescale the pruned network. The next proposition establishes that a Resnet lives on the EOC in the sense that the correlation between (z) and (xx) converges to at a sub-exponential O(1 rate.
Proposition 3 (Resnet live on the EOC even after pruning). Let + x' be two inputs. The following statments hold
1. For Resnet with Fully Connected layers, let è' (Ir, x') be the correlation between if (a)) and (x') after pruning the network. Then have
- (x,
R 12
where >> O is a constant.
2. For Resnet with Convolutional layers, let èl (2,x²)) Ea.a' E'v, (z')) Enool V (v) (x')
be 'average'
correlation after pruning the network. Then we have
1 1- -- x') 2-2
Proof.
1. Let and x' be two inputs. The covariance of (x)) and (x') is given by
(1xxx')) (z,
where Q²-1 [ (x) (2,x')
and a E[N [1]
0 (x, (x-((x")
Consequently, we have (x()) (1 + ) (z). Therefore, we obtain
A
d(x,,') = 1+ X
ج (x, x + 1+ (xr,
where and f(x) = ( (1x2 + v1 x Zz)] and Z1 and Zz are iid standard normal variables.
Using the fact that f is increasing (Section B.1), it is easy to that d (x, - 1. Let S = 1 (xx, x'). Moreover, using a Taylor expansion of f near (Section B.1)
[(x) = + ((1 - x/3322 + O((1 //)5)), follows that --1-
S G1- - 77-11
3/2
0(522)
where 17 X-X- Now using the asymptotic expansion of & 1/2 given
A8
G 1/2 - + O(G-1),
this yields G
L. We conclude that - 2 (x, x') ~ اाा
10000
2. Let z be an input. Recall the forward propagation of a pruned ID CNN
(z) = vi (x) + Σ Σ
W
W
10 + 6).
j=1 Beker
Unlike FFNN, neurons in the same channel are correlated since we use the same filters for all of them. Let x, x' be two inputs and a, a' two nodes in the same channel Using the Central Limit Theorem in the limit of large (number of channels), we have
Ely (z)al=
Σ Beker
2k
where ag Elo WT 1,,,, 2 2n-
28

---

Published as a conference paper at ICLR 2021
Let (x) = E (2) The choice of the channel is not important since for given a, neurons (V/, (z))e((d are iid. Using the previous formula, we have
da(x) = da (x) + 2k +
(0 (z))
Beker
la lots(() ag
(x) + 2k
Beker
Therefore, letting d(xx) N/ Eae(N| (x) and o
Σg ag
obtain
2h+1
d(x) = (x) +
1
Σ 03
(a+)(r)
2k +
Beker
nE(n]
= = (z) = (1 2 31-1g"(a) (x),
(x)
where we have used the periodicity do d'11 = 1-1 Morcover, we have
mina (x) 2 (1 + /) mina (x) 2 (1+ 1-)-1ming d
The convolutional structure makes hard to analyse the correlation between the values of a neurons for two different inputs. Xiao et al. (2018) studied the correlation between the values of two neurons in the same channel for the same input. Although this could capture the propagation of the input structure (say how different pixels propagate together) inside the network, it does not provide any information on how different structures from different inputs propagate. To resolve this situation, we study the 'average" correlation per channel defined as
dxx Ea.or (1)i,
Ena V (z) V (a((z")
for any two inputs x + x'. We also define ((x, x') by
1 (x,,')) N2 En.or Elyl (x) uu (x¹) E N E. da(x))
Using the concavity of the square root function, we have
Σ (z)
Σ
dd(x))
N Σ d'd (x)
N
a.a"
V (ct) odlla
N
a,a!
Elyl (x)h
N2
This yields (I,x²) < (x, x') < 1. Using Appendix Lemma 2 twice with ata = (z).
01 (x'), and Ag 2(2++J-
as
there exists Ç > 0 such that
d e x1) O(e-())
(19)
This result shows that the limiting behaviour of c' (z, x²) ) is equivalent that of è' (z, xx) up to an exponentially small factor. We study hereafter the behaviour of d' (z, x²) and use this result to conclude. Recall that
Elyh. (z) (a') (x)o)
Σ
ag (z) (z)) (o
2 +
Beker
29

---

Published as a conference paper at ICLR 2021
Therefore,
Σ 0,00
Σ Elyi (x)
Σ E
2k +
a,a' BEker
Σ a,a'
E (z)a)
+
Σ
a,a
V
(x)
where is the correlation function of ReLU.
Let us first prove that & (ar x') converges to 1. Using the fact that f(z) 2 2 for all 2 E (0, 1)
(Section B.1), we have that
Σ
Σ (syld
Σ 4a (x) da (xd))
Σ a.a'
Elyi
(z)) (x))
Σ
2
a.
+ (syl (x'))
Combining this result with the fact that En da(x) = (1+ (). da (x), we have é x²) 2 (=)(xx, Therefore (xx,'') is non-decreasing and converges to a limit- ing point
Let us prove that c= 1. By contradiction, assume the limit c < 1. Using equation (19), goes to infinity. This yields cx x') - c. There- fore, there exists onp an and constant such that for all I, cao.at (2r, S 8 < 1.
we have that c'(2xx') f(2,²") converge
Knowing that ʃ is strongly convex and that f'(1) = 1, we have that S( (I, 2 Laging x') ('5xx+++0 + (()) 8. Therefore,
2 q00 (x) (x)9 (x')
(x,,2)2² (x,
+
N (x) (x') (x') (f(0) - 8)
2 min, ohe (x) min, do (2')
2 2 (z.
(f(i) 5).
N2 / (z) (z)
By taking the limit / + 20, we find that c 2 c+ 2 /mming (2) min, o (wr)
(f(ō) - 8). This
N2 (1
cannot be true since f(8) d. Thus we conclude that 1.
Now we study the asymptotic convergence rate. From Section B. we have that
2v2 x/3/2 + O(11 - =/33)).
f(x) x-1
+
3T
Therefore, there exists such that, close to 1 we have that
f(x) < x + x(1 - 3/2.
Using this result, upper bound d' (x,
30

---

Published as a conference paper at ICLR 2021
ga (z) 1a (x)) (1-cano (I, x'1)
(x, S (x,z') +
No
V((e)//(<"))
a,a"
To get a polynomial convergence rate, we should have an upper bound of the form < -' + + (sce below). However, the function /// is convex, so the sum cannot be upper-bounded directly using Jensen's 's inequality. We use here instead (Pečarié et al., 1992, Theorem 1) which states that for any I1, I2, ... > O and > r > 0, we have
Σ
x
(20)
Let z
V 90 (1) F (1r)
we have
a,a"
Vg'(z)/ ('(x))
aa (F, < G1 Eisan
a,a
a
where Gi maxa,a
Using the inequality (20) with 3/2 and have
Σ Eleaaar (1 - (x, <
E
ar - (x,
0,0'
a,a'
2aw d (2,x2))))3
Moreover, using the concavity of the square root function, have Σ Ea, 2 S 1. This yields
d1,,²' - (x,
where ( is constant. Letting 7 = 전t (w, x'), can conclude using the following
inequality (we had an equality in the case of FFNN)
3/2
Y z ύ-1 - (91-1
which leads to
11/2 11/2 31 S 9-11
(71 1/3
Vi-1
-1/2 C
+ o(l).
2
Hence we have
71 1-
Using this result combined with (19) again, we conclude that
1 1- e- x') 1-2
E THEORETICAL ANALYSIS OF MAGNITUDE BASED PRUNING (MBP)
In this section, we provide theoretical analysis of MBP. The two approximations from Appendix A are not used here.
MBP is data independent pruning algorithm (zero-shot pruning). The mask is given by
(
if
W 2 las W < ta
=
31

---

Published as a conference paper at ICLR 2021
where t, is threshold that depends the sparsity By defining k2 (1-5) by [W](k) where (W] is the kith order statistic of the network weights (IW? DissLssisM (WW))) |W [W
5) E, Mr t, is given
With MBP, changing does not impact the distribution of the resulting sparse architecture since is a common factor for all the weights. However, the case of different scaling factors u,, the variances E used to initialize the weights vary across layers. This gives potentially the erroneous intuition that the layer with the smallest variance will be highly likely fully pruned before others as we increase the sparsity s. This is wrong in general since layers with small variances might have more weights compared to other layers. However, we can prove a similar result by considering the limit of large depth with fixed widths.
Proposition (MBP the large depth limit). Assume N fixed and there exists to E [|1,IA] such that ala aip,
ai for all + lo. Let Qu be the 2hh quantile of [X] where X sid NN(0,) and y mint on For E (0,2), define Ie, = =inffy (0, Vx > y, v,TQu > Q1-(1-0772-1)
and Te, = 0o for the null set. Then, for all E E {0,,) 2), Ten is finite and there exists a constant v such that
E[ser| S inf (ren + cE(0.2)
1 1+ 1-g2-c Te,T) 1422 O+0
N2
1
VLN
Proposition gives an upper bound on [F(scr] the large depth limit. The upper bound easy to approximate numerically. Table 7 compares the theoretical upper bound in Proposition 4 to the empirical value of [[[ar] over 10 simulations for a FFNN with depth L = 100, N 100, 0₁ = and 02 a3
az 1. Our experiments reveal that this bound can be tight.
Table 7: Theoretical upper bound of Proposition 4 and empirical observations for FFNN with N 100 and L = 100
GAMMA
2
5
10
UPPER BOUND
5.77
0.81
0.72
EMPIRICAL OBSERVATION
R=
0.79
0.69
Proof. Let x E (0, and k2 =(1 -1- = where rú
-Ei4t G. We have
P(ser 5x) 2 P(max [W < (W)(k)))
where (ka) is the 1ith order statistic of the sequence (WW)), l # 1o, E [1 Mi]:: ie [W] (W > (W](k))
Let (X, (Xi)ee(I)M))) and (Z))ie(I.r Nen be two sequences of iid standard normal variables. It is easy to that
Pmmax i.
W < (w](k)) 2 P(max X < (()))
where 7 = min alp.
Moreover, we have the following result from the theory of order statistics, which is a weak version of Theorem 3.1. in Puri and Ralescu (1986)
Appendix Lemma 3. Let X2,,,,,, be lid random variables with edf F. Assume F is differentiable and let p E (0, and let Op be the order quantile of the distribution F, i.e. F(Q,)) =p Then have
(m(((mm) - F)))o D 1(,,
where the convergence is in distribution and op p(1 p).
32

---

Published as a conference paper at ICLR 2021
Using this result, we obtain
P(max
[X,] < <))((k=) = P(max X < 722) + +0
VLN
where Oz is the quantile of the folded standard normal distribution.
The next result shows that de, is finite for all (0, 2).
Appendix Lemma 4. Let > 1. For all e E (0, 2), there exists Le E (0, 1) such that, for all x > De. 7Q2 Q1-(1-u)72
Proof. Let > O, and recall the asymptotic equivalent Q1- given by
I-x ~ V
72, Therefore, Q, 111--a ~0-1 v Hence z, exists and finite.
Let c > 0. Using Appendix Lemma 4, there exists Ie > 0 such that
P(mmx |x < 7Q2) 2 P(max [ < Q Q1-(1-0))2-)
x) 7² = )so0 2 1 So. 2 x))²²
(1
where we have used the inequality (1-t)a 2 1 - st for all (t, 2) E [0, 1] x 00) and B = 0% 01
Using the last result, we have
P(ser 20)5 x)7²" + +0(
/LN
Now have
= 1/' P(ser 2 x)de
E E[Ser]
xe. /' P(ser x)dr
BN2
1
$ x.
1 1+g2-e xI.)
O
LN
This is true for e E (0, 2), and the additional term O
does not depend on e. Therefore
VLN=
there exists constant E IR such that for all
ON2
Eis S x +
2-c (1 (1-xx)'
-+1
2-1
VL
We conclude by taking the infimum over
Another interesting aspect of MBP when the depth fixed and the width goes to infinity. The next result gives lower bound the probability of pruning at least one full layer.
Proposition 5 (MBP in the large width limit), Assume there exists lo E [1 L] such that an," > au
Min (i.e. via > vi) for all I, and let so -,,M. is fully pruned before other layers, i.e.
M. For some sparsity let P (R) (s) be the event that layer
PRio (s) [|Aiol Mio} Niel--L] {AAi) Mi).
and let PR, = =sse(so. PRi, (s) be the event where there exists a sparsity s such that layer lo fully pruned before other layers. Then, we have
Lx
1
P(PR.) 21 4(7 1)2 log (N)2 + + log(N)))
ata where 7 minkgll ox
33

---

Published as a conference paper at ICLR 2021
Proposition 5 shows that when the width is not the same for all layers, MBP will result in one layer being fully pruned with a probability that converges to 1 as the width goes to infinity. The larger the ratio y (ratio of widths between the largest and the second largest layers), the faster this probability goes to 1.
The intuition behind Proposition comes from result in Extreme Value Theory stated in Appendix Lemma 6. Indeed, the problem of pruning one whole layer before the others is essentially a problem of maxima: we prune one whole layer lo before the others if and only if for all max; |W < minzz max; [W The expected value of n iid standard Gaussian variables is known to scale as vlogn n for large n; see e.g. Van Handel (2016).
The proof of Proposition 5 relies the following two auxiliary results.
Appendix Lemma (Rearrangement inequality (Hardy et al., 1952)). Let f.g functions which are either both non non-decreasing or aon-increasing and let X be random variable. Then
- be
gg 2 Blgx)-)
Appendix Lemma 6 (Von Mises (1936)). Let (Xi) be iid random variables with common ](2)
density f and cumulative distribution function F. Assume limg->F-1 (1-F(ul), O, then limn-roo Pmmma;; X; I a, ba) G(x) where G is the Gumbel cumulative distribution function and series On and by are given by b,, = F- 11-(111-11 1.) and on nf(b)))
We are now in position to prove Proposition 5.
Proof. Assume there exists lo E [1 L] such that on, > oz for all (. The trick is to see that
PR.,- {Ak o lo, max | < max [W?1].
Let us prove that
P(PR))) 2 II
P(max W max (W
k
Let X = max; [W!o]. We have that
P(PR),) = E
II P(X < max [W]]
ky
using the rearrangement inequality presented in Appendix Lemma 5 with functions f((x) PP(X max, | = z) which are all non-increasing, we obtain
P(PR)))) Z II E[P(X < max W/[lx)] = II
P(max [W!1| < max (W*1)
In order to deal with the probability P(max, [ < max, [W,)), we use Appendix Lemma 6 which result from Extreme Value Theory which provides comprehensive description of the law of max; X; needed in our analysis. In our case, we want to characterise the behaviour of max; X where X; are iid Gaussian random variables.
Let V and v be the edf and density of standard Gaussian variable X. The cdf of |X] is given by F= 24 1 and its density is given by f = 2 on the positive real line. Thus, L-F - I- and it is sufficient to verify the conditions of Appendix Lemma 6 for the standard Gaussian distribution. We have lim,--F- d (x)) lim x (1-V(=))
= x/x 0, where we have used
(())
*(x)
the fact that xx1 - (x)) ((x) in the large x limit.
Let us now find the values of a, and bn In the large limit, we have
- F(x) =
dt
v
2m
2
1
+
2
2
34

---

Published as a conference paper at ICLR 2021
Therefore, one has
x²
log(1 Og(11F(x)))
2
This yields
b = F1 - ~ v 2og
Using the same asymptotic expansion of F(x), we can obtain a more precise approximation of by
b, = 2 log (1 log(log n) log log( n)
+ of log(log n)) )). (logn)²
4 logg
2 log
8(lggn)2
Now let us find an approximation for ag. We have
V2 nn
(bb))
v
log n.
Therefore, it follows that
T
On
Vllgn
We these results lower bound the probability P(max; [W max; [W?1). We have
P(max W 2 max (W*)) (max X,| 7 max [Y])::
where 7/k Llo and (X₃) and (Yi) are standard Gaussian random variables. Note that 74 1. Let or
AN = max; |X; and BN = max, Yi]. We have that
PPANN 2 7/ BN) ) = TP(AN [[[AN] 2 7ke BN - B[BN]) + [e[[BN] - R[(NN)
(AN B[AN))²
n
E
(Ne(BN - B[B + [BE[BN] - E[AN]))) N= 4(7h 1)2 log(
We conclude that for large N
La
P(PR))) 21 4(7 - 1)2 log(N)2 o( (og(NN)
olo where 7 mingoelo ax
F IMAGENET EXPERIMENTS
To validate results large scale datasets, prune ResNet50 using SNIP, GraSP, SynFlow and our algorithm SBP-SR, and train the pruned network on ImageNet. We train the pruned model for 90 epochs with SGD. The training starts with learning rate 0.1 and it drops by a factor of 10 epochs 30, 60, 80. We report in table 8 Top-1 test accuracy for different sparsities. Our algorithm SBP-SR has clear advantage other algorithms. We currently running extensive simulations on ImageNet to confirm these results.
Table 8: Classification accuracy ImageNet (Top-1) for ResNet50 with varying sparsities (TODO: These results will updated include confidence intervals)
ALGORITHM
85%
90%
95%
SNIP
69.05
64.25
44,90
GRASP
69.45
66.41
62.10
SYNFLOW
69.50
66.20
62.05
SBP-SR
69.75
67.02
62.66
35

---

Published as a conference paper at ICLR 2021
Table 9: Test accuracy of pruned neural network on CIFAR10 with different activation functions
Resnet32
Algo
90
98
99.5
99.9
Relu
SBP-SR
92.56(0.06)
88.25(0.355
79.54(1.12)
51.56(1.12)
SNIP 92.24(0.255)
87.63(0.16)
77.56(0.36)
10(0)
Tanh
SBP-SR
90.97(0.2)
86.62(0.38)
75.04(0.49)
51.88(0.56)
SNIP
90.69(0.28)
85.47(0.18)
10(0)
10(0)
Resnet50
Relu
SBP-SR
(2.05(0.06)
89.57(0.21)
82.68(0.52)
58.76(1.82)
SNIP 91.64(0.14)
89.20(0.54)
80.49(2.41)
19.98(14.12)
Tanh
SBP-SR
90.43(0.32)
88.18(0.10)
80.09(0.0.55)
58.21(1.61)
SNIP 89.55(0.10)
10(0)
10(0)
10(0)
G ADDITIONAL EXPERIMENTS
In Table 10, we present additional experiments with varying Resnet Architectures (Resnet32/50), and sparsities (up to 99.9%) with Relu and Tanh activation functions Cifar10. We see that overall, using our proposed Stable Resnet performs overall better that standard Resnets.
In addition, we also plot the remaining weights for each layer to get a better understanding on the different pruning strategies and well understand why some of the Resnets with Tanh activation functions are untrainable. Furthermore, we added additional MNIST experiments with different activation function (ELU, Tanh) and note that our rescaled version allows to prune significantly more for deeper networks.
Puaning
Pranig Oraam 2000
Planng Rilo
Figure Percentage of pruned weights per layer in ResNet32 for our sealed ResNet32 and standard Resnet32 with Kaiming initialization
36

---

Published as a conference paper at ICLR 2021
(a) ELU with FOC Init & (b) ELU with EOC Init Rescaling
(c)
ELU with Ordered phase
Init
(d) Tanh with EOC Init (e) Tanh with EOC Init Rescaling
(f) Tanh with Ordered phase Init
Figure 5: Accuracy on MNIST with different initialization schemes including EOC with rescaling, EOC without rescaling, Ordered phase, with varying depth and sparsity. This figure clearly illustrates the benefits of rescaling very deep and sparse FFNN.
Table 10: Test accuracy of pruned vanilla-CNN on CIFARIO with different depth/sparsity levels
Resnet32
Algo
90
98
99.5
99.9
Relu
SBP-SR
92.56(0.06)
88.25(0.35)
79.54(1.12)
51.56(1.12)
SNIP 92.24(0.25)
87.63(0.11)
77.56(0.36)
10(0)
Tanh
SBP-SR
90.97(0.2)
86.62(0..8)
75.04(0.49) 10(0)
51.88(0.56)
SNIP
90.69(0.28)
85.47(0.18)
10(0)
Resnet50
Relu
SBP-SR
92.05(0.06)
89.57(0.21)
82.68(0.52)
58.76(1.82)
SNIP
91.64(0.14)
89.20(0.54)
80.49(2.41)
19.98(14.12)
Tanh
SBP-SR
90.43(0.32)
88.18(0.10)
80.09(0.0.55)
58.21(1.61)
SNIP
(9.55(0.10)
10(0)
10(0)
10(0)
37

---

Published as a conference paper at ICLR 2021
H ON THE LOTTERY TICKET HYPOTHESIS
The Lottery Ticket Hypothesis (LTH) (Frankle and Carbin, 2019) states that "randomly initialized networks contain subnetworks that when trained isolation reach test accuracy comparable the original network". We have shown so far that pruning a NN initialized on the EOC will output sparse NNs that can be trained after rescaling. Conversely, we initialize a random NN with any hyperparameters (aw ob), then intuitively, we can prune this network in way that ensures that the pruned NN on the EOC. This would theoretically make the sparse architecture trainable. We formalize this intuition as follows.
Weak Lottery Ticket Hypothesis (WLTH): For any randomly initialized network, there exists subnetwork that is initialized on the Edge of Chaos.
In the next theorem, we prove that the WLTH is true for FENN and CNN architectures that are initialized with Gaussian distribution.
Theorem 3. Consider FFNN or CNN with layers initialized with variances o > 0 for weights and variance for
for bias. Let Fw EOC be the value of ow such that (a EoC, 0%) EOC. Then, for
all ow > EOC, there exists a subnetwork that is initialized on the EOC. Therefore WLTH is true.
The idea behind the proof of Theorem 3 is that by removing fraction of weights from each layer, we changing the covariance structure in the next layer. By doing in precise way, we can find subnetwork that is initialized on the FOC.
We prove slightly
general result than the stated.
Theorem 4 (Winning Tickets the Edge of Chaos). Consider neural network with layers ini- tialized with variances ow, E IR+ for each layer and variance σ > 0 for bias. We define Eoc be the value of such that (0w,EOC σb) EOC. Then, for all sequences (aw,)) such that T >
EWC for all I, there exists a distribution of subnetworks initialized on the Edge of Chaos.
Proof. We prove the result for FFNN. The proof for CNN similar. Let x. x' be two inputs. For all 1, let (ō')sj be collection of Bernoulli variables with probability pt. The forward propagation of the covariance is given by
22(2,2')= = (x)((
N
E
Σ
(40)000)0)00000000000000"00 of.
jik
This yields
d' (x,xx) -th in (c) o
a soc this becomes
By choosing
d (z,x') = oe, (
or.
Therefore, the new variance after pruning with the Bernoulli mask 5 is o = o² Eoc- Thus, the subnetwork defined by is initialized on the EOC. The distribution of these subnetworks is directly linked to the distribution of 8. We can see this result as layer-wise pruning, i.e. pruning each layer aside. The proof is similar for CNNs.
Theorem is special case of the previous result where the variances a.e are the same for all layers.
38

---

Published as a conference paper at ICLR 2021
1 ALGORITHM FOR SECTION 2.3
Algorithm 1 Rescaling trick for FFNN
Input: Pruned network, size m
for L 1 to L do for = 1 to N; do
af - > (W 8
Pgj < 1/1 o for all j
end for end for
39


Reviews:
[{"review_id": "oOcruYYVCmO", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "The theoretical analysis is clearly stated in an well-organized way and the derived sparsity bound is reasonable. With FFNN and CNN, a theorem is given to show that the model is trainable only when the initialization on Edge of Chaos (EOC) and also provided a rescaling method to make the pruned NN into EOC regime. With Resnet, it proves the pruning satisfies the EOC condition by default and further provides re-parameterization method to tackle exploding gradients. The experiments well support theoretical results for both FFNN/CNN and resNet. \n\nI would recommend an accept on this paper.\n\nQuestions during rebuttal period: \nThe theorem 2 is stated for resNet with ReLU activation function. Is proposition 2 and section 4.2 only for ReLU as well? Please state the dependence on activation function more clearly in the paper. \n\nOne typo: In section 4.1, the figure should be Figure 3 rather than Figure 5. \n\n      ", "extra_scores": {}, "extra_text": {}}, {"review_id": "k-Hd1FXlgHB", "reviewer": "AnonReviewer2", "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": "### Contents of the paper\n\nThe contributions of the paper are three folded: 1) It proposes an essential for pruning at initialization, namely the NN must be initialized with EOC. 2) It proposes a trick to pull the pruned network back into EOC. 3) Some specific research about  ResNet.\n\n### Advantages of the paper\n\n1. The paper seems to be solid with enough motivation and proofs.\n2. The experimental results show that the proposed algorithm achieves about 1% higher accuracy on ResNet than other algorithms.\n\n### Weakness\n\n1. Lack of experiments on larger datasets such as ImageNet\n2. The authors claim an exploration on FFNN and CNN. However, only results on ResNet are provided. In other words, the effectiveness of the algorithm on other networks are doubtful.\n3. Lack of ablation study or case study experiments. For example, what if we prune a CNN without EOC? \n\n#### Updates after rebuttal\n1. The authors have provided more results I concerned, which seems to be accord with their conclusions in the paper.\n2. Initialization of CNN or other networks is an interesting topic which affects the performance of pruned models. However, there are few papers about the topic. I think the paper is a good example which may arouse more concerns about it.\n3. I am willing to increase my rating to 6.\n\n### Question\n\n1. In table 1, why the results on ResNet104 are far better than those on ResNet32 and ResNet50? Especially when the pruning rate is 90%\n\nI'll consider to increase my rating if the authors can provide more convicing results", "extra_scores": {}, "extra_text": {}}, {"review_id": "ESWHa7Nkl_e", "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": "The given paper carries two main contributions: 1) theoretical study of the pruning at initialization (i.e. before training); 2) proposing a new rescaling trick to avoid issues (namely, entire layer pruning) that are common for such pruning mechanisms. \n\nMajor concerns:\\\n  . Theoretical contribution: First of all, I would like to mention that I am not an expert in one-shot pruning and pruning at initialization. However, I strongly believe that the layer pruning problem is commonly observed and studied phenomena (which is stated by authors as well) and it was theoretically studied before. For example, I suggest authors refer to the recent work from [1] where they call it \"layer collapse\". Furthermore, it was shown that layers with the smaller size have more likelihood of getting entirely pruned. Here, we observe similar behavior (called \"layer ill-conditioning\") but due to EOC.\\\n  . Methodological contribution: again, as it is done in [1], the main propose of the rescaling trick is to make sure that the sensitivity score is uniformly distributed to avoid layer pruning. I believe, there are other ways to achieve this goal and thus, contribution is marginal.\n\n[1] Tanaka et al. Pruning neural networks without any data by iteratively conserving synaptic flow. June, 2020.\n\nMajor advantageous:\\\n  . Authors theoretically justify their proposed method;\\\n  . Experiments show a consistent improvement over the SoA baselines (Snip, Grasp). The improvement is even drastic for ResNet104; However, it will be nice to have a comparison with [1].\n\n\n---- update after authors' response ----\\\nThanks for clarification and providing additional experiments. I'm changing my final evaluation to weak accept. Yes, this paper does provide some interesting insights, but I still think that it has a limited potential impact (see above for major drawbacks).\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a sensitivity-based pruning method at initialization. For fully connection and and convolutional neural networks, it shows that the model is trainable only when the initialization satisfies Edge of Chaos (EOC). The paper also provided a rescaling method so that the pruned network is initialized on the EOC. For Resnet, the paper shows that the proposed pruning satisfies the EOC condition by default and further provides re-parameterization method to tackle exploding gradients. The experiments show the performance of the proposed method on fully connected and convolution neural network, as well as ResNet. There were some concerns about the contribution of the paper compared to that of [1]. I read the two papers carefully and while both papers aim at addressing a similar problem, i.e., pruning at initialization while avoiding layer collapse, the paper provides a different perspective on the problem, and provides enough theoretical contribution and insights to be found helpful and interesting by the community. 

Decision: Accept (Poster)