How Erdös and Rényi Win the Lottery
Authors: Advait Harshal Gadhikar
Sohom Mukherjee
Rebekka Burkholz
Venue: Submitted to ICLR 2023 (2023)
Keywords: deep learning
lottery tickets
pruning at initialization
random masks
theory

Abstract: Random masks define surprisingly effective sparse neural network models, as has been shown empirically. The resulting Erd\"os-R\'enyi (ER) random graphs can often compete with dense architectures and state-of-the-art lottery ticket pruning algorithms struggle to outperform them, even though the random baselines do not rely on computationally expensive pruning-training iterations but can be drawn initially without significant computational overhead. We offer a theoretical explanation of how such ER masks can approximate arbitrary target networks if they are wider by a logarithmic factor in the inverse sparsity $1 / \log(1/\text{sparsity})$. While we are the first to show theoretically and experimentally that random ER source networks contain strong lottery tickets, we also prove the existence of weak lottery tickets that require a lower degree of overparametrization than strong lottery tickets. These unusual results are based on the observation that ER masks are well trainable in practice, which we verify in experiments with varied choices of random masks. Some of these data-free choices outperform previously proposed random approaches on standard image classification benchmark datasets. 

Under review as a conference paper at ICLR 2023
How ERDÖS AND RÉNYI WIN THE LOTTERY
Anonymous authors Paper under double-bling review
ABSTRACT
Random masks define surprisingly effective sparse neural network models, as has been shown empirically. The resulting Erdös-Rényi (ER) random graphs often compete with dense architectures and state-of-the-arr lottery ticket pruning algorithms struggle to outperform them, even though the random baselines do not rely on computationally expensive taninngtraiiing iterations but can be drawn initially without significant computational overhead. We offer theoretical ex- planation of how such ER masks can approximate arbitrary target networks if they are wider by a logarithmic factor in the inverse sparsity 1/ log(1/sparsin) While we are the first to show theoretically and experimentally that random ER source networks contain strong lottery tickets, we also prove the existence of weak lottery tickets that require a lower degree of overparametrizationn than strong lottery tickets. These unusual results are based on the observation that ER masks are well trainable in practice, which we verify in experiments with varied choices of random masks. Some of these data- free choices outperform previously proposed random approaches on standard image classification benchmark datasets.
INTRODUCTION
The impressive breakthroughs achieved by deep learning have largely been attributed to the extensive overparametrization of deep neural networks, as it seems to have multiple benefits for their represen- tational power and optimization (Belkin et al.) 2019). The resulting trend towards ever larger models and datasets, however, imposes increasing computational and energy costs that are difficult to meet. This raises the question: Is this high degree of overparameterization truly necessary?
Training general small-scale or sparse deep neural network architectures from scratch remains a challenge for standard initialization schemes Li al. (2016); Han al. (2015). However, |ranklee & Carbin (2019) have recently demonstrated that there exist sparse architectures that can be trained to solve standard benchmark problems competitively. According to their Lottery Ticket Hypothesis (LTH), dense randomly initialized networks contain subnetworks that can be trained in isolation to test accuracy that is comparable with the one of the original dense network. Such subnetworks, the lottery tickets (LTs), have since been identified as weak lottery tickets (WLTs) by pruning algorithms that require computationally expensive et al. (020)) or mask learning procedures Savarese al. (0000); Srrenivassan al. (2022b). While
retrannne iterations (Frankle & Carbin 2019 Tanaka
these can lead to computational gains at training and inference time and reduce memory requirements
(Hassibi et al. 1993 Han et al. 2015), the real goal remains to identify good trainable architectures
before training, as this could lead to significant computational savings. Yet, contemporary pruning at
initialization approaches (Lee et al. 2018 Wang al. 2020 Tanaka al. 2020 Fischer & Burkholz 2022; Frankle et al., 2021) achieve less competitive performance. For that reason it is so remarkable that even iterative state-of-the- approaches struggle to outperform a simple, computationally cheap. and data independent alternative: random pruning at initialization (Su et al. 2020). Liu et al. (2021) have provided systematic experimental evidence for its "unreasonable" effectiveness in multiple settings, including complex, large scale architectures and data.
We explain theoretically why they can be effective by proving that randomly masked networks, so called Rénös (ER) networks, contain lottery tickets under realistic conditions. Our results imply that sparse ER networks are highly expressive and have the universal function approximation property like dense networks. This insight also provides a missing piece in the theoretical foundation for dynamic sparse training approaches (Evci et al.) 2020aa Liu et al., (201..) [ellec et al. (0088) that start pruning from random ER network instead of dense one. The main underlying idea could also

---

Under review as a conference paper at ICLR 2023
be exploited in different sparsification settings to save computational resources. Up to our knowledge, we are the first to utilize it in the search of strong lottery tickets (SLTs).
Most theoretical results pertaining to LTs focus on the existence of such SLTs (Malach al. 2020
Pensia et al., 2020 Fischer et al. 2021 da Cunha et al., 2022, Burkholz 2022a b). These are subnetworks of large, randomly initialized source networks, which do not require any further training after pruning. Raaaanujan et al. (2020) have provided experimental evidence for their existence and suggested that training neural networks could be achieved by pruning alone. By modifying their proposed algorithm, edge-popup (EP), we show experimentally that SLTs are contained in randomly masked ER source networks. We also prove this existence rigorously by transferring the construction of Burkhholz (2022a) to random networks. This introduces an additional factor 1/ log(1/ /sparsity) in the lower bound on the width of the source network that guarantees existence with high probability.
In contrast to previous works on SLTs, we also prove the existence of weak LT's. Since every strong LT is also weak LT, formally, the theory for strong LTs also covers the existence of weak LTs.. However, experiments and theoretical derivations suggest that limiting ourselves to SLTs leads to LTs with lower sparsity than what can be achieved by WLT algorithms (Fischer & Burkholz] (022). In line with this observation, we derive improved existence results for WLTs. However, these cannot overcome the overparameterization factor 1/ log (1/pparsity)) which is even required under ideal conditions, as argue by deriving lower bound on the required width. Our strategy relies property of ER networks that is crucial for their effectiveness: They are well trainable with standard initialization approaches. With various experiments
benchmark image data and commonly used neural network architectures, we verify the validity of this assumption, complementing experiments by Liu et al. (202I) for different choices of sparsity ratios. This demonstrates that multiple choices can lead to competitive results. Some of these choices outperform previously proposed random masks Liu et al. (202I), highlighting the potential for tuning sparsity ratios in applications.
Contributions In summary, our contributions are as follows: 1) We show theoretically and empiri- cally that ER random networks contain LTs with high probability. if the ER source network is wider than a target by a factor 1/ log(1 /sparsity). 2) We prove the existence of strong as well as weak LT' in random ER source networks. 3) In support of our theory, we verify in experiments that ER networks are well trainable with standard initialization schemes for various choices of layerwise sparsity ratios. 4) We propose two data- iettaiinddeeneett, flow preserving and computationally cheap approaches to draw random ER masks defining layerwise sparsity ratios, balanced and pyramidal. These can outperform previously proposed choices on standard architectures, highlighting the potential benefits resulting from tuning ER sparsity ratios. 5) Our theory explains why ER networks are likely not competitive at extreme sparsities. But this can be remedied by targeted rewiring of random edges as proposed by dynamic sparse training, for which we provide theoretical support with our analysis.
1.1 RELATED WORK
Algorithms prune neural networks can be broadly categorized into two groups, pruning before training and pruning after training. The first group of algorithms that prune after training are effective in speeding up inference, but they still rely on computationally expensive training procedure
(Hassibi et al. 1993 LeCun et al.) 1989 Molchanov et al. 2016 Dong et al. [017]] Yu et al., (002)).
The second group of algorithms prune at initialization (Lee al. [0188] Wang et al. 2020 Tanaka
ct al. 2020 Sreenivasan et al. 2022b) or follow a computationally expensive cycle of pruning
and retraining for multiple iterations (Gale et al. 2019 Savarese et al., 2020; You et al. 2019
Frankle & Carbin 2019; Renda et al. Dettmers & Zettlemoyer 2019). These methods find trainable subnetworks, i.e., WLT's (Frankle & Carbin 2019). Single shot pruning approaches are
computationally cheaper but are susceptible to problems like layer collapse which render the pruned network untrainable (Lee et al. 20188) Wang et al.) 2020). (Tanaka et al. (2020) address this issue by preserving flow in the network through their scoring mechanism. The best performing WLTs are still obtained by expensive iterative pruning methods like Iterative Magnitude Pruning (IMP), Iterative Synflow (Frankle & Carbin 2019; Fischer & Burkholz 2022), training mask parameters of dense
networks (Sreenivasan et al. 2022b Savarese et 2020).
However, Su et al. 2020) found that ER masks can outperform expensive iterative pruning strategies in different situations. Inspired by this finding, Goolubva et al. (202T); Chang et al. (202T) have hypothesized that sparse overparameterized networks are more effective than smaller networks with
2

---

Under review as a conference paper at ICLR 2023
the same number of parameters. Liu al. (2021) have further demonstrated the competitiveness of ER masks for two data and pruning free choices of layerwise sparsity ratios across a wide range of neural network architectures and datasets, including complex ones. We show how and when this effectiveness is reasonable. Complementing experiments by Liu et al. (202T), we highlight that ER masks are competitive for various choices of layerwise sparsity ratios.
In addition, we build on the theory for SLT's that prove SLT existence if the widths of the randomly initialized source network (Malach et al. 2020 Pensia et al. 20200 Orseau et al., 2020 Fischer
et al. 2021 Burkhhll et al.) 2022 Burkholz 2022b; Ferbach et al.) 2022) exceeds a value that is proportional to the width of a target network. This theory has been inspired by experimental evidence for SLT's (Ramanujan et al. 2020 Zhou et al. 2019; Diffenderfer & Kailkhura 2021; Sreenivasan et al. 2022a). The underlying algorithm pope- (Ramanujan et al. (2020] finds SL.Tss by training scores for each parameter of the dense source network and is thus computationalyy as expensive as dense training. We show that smaller ER masked source networks can be trained instead, as they also contain SLTs, and avoid training complete network.
However, pruning for SLTs does not seem to achieve as high sparsity ratios as WLT pruning algorithms Fischer & Burkhhlz (2022), which is also reflected in our existence proofs for SLTs and WLTs. Remarkably, even WLTs require that the ER source network and the resulting LTs are overparameterized relative to the target network, required width. Our theory suggests that random ER networks face a fundamental limitation at extreme sparsities, as the overparameterization factor scales in this regime 1/(1 sparsity). ). This shortcoming could be potentially addressed by targeted rewiring of random edges with Dynamical Sparse Training (DST) that starts pruning from ER network (Liu al. 2021.
show by providing lower bound on the
/og((1/ (1/((1/s/p)) (sparsity)) x
Evci et al. 2020a b).
ERDÖS-RÉNY? NETWORKS AS LOTTERY TICKETS
Our main contribution to prove the existence of strong and weak lottery tickets ER networks. In comparison with previous existence results for complete source networks, we require network width that is larger by a factor 1/ /oog(1/ //sparsity).. To formalize our claims, we first introduce our notation.
Background, Notation, and Proof-Setup Let x = (I1, 32, .., v.) E bai, be a bounded dimensional input vector, where @1 bj E R with 01 < bj. f: [a1, bj + I is a fully-connected feed forward neural network with architecture (no, fI,.., n1),, i.e. depth L and ny neurons in Layer l. Every layer E (1.2.... .., L) computes neuron states x!!) (0()) is called the pre-activation, ( E Reuxne- is the weight matrix and g(0) is the bias vector. We also write f(;; 0) to emphasize the dependence of the neural network on its parameters 0 = (W )( For simplicity, we restrict ourselves the common ReLU d(x) max 0} activation function, but most of our results can be easily extended to more general activation functions as in (Burkholz,) a)) In addition to fully-connected layers, we also consider convolutional layers. For convenient notation, without loss of generality, we flatten the weight tensors so that w X where e, e, 1 k are the output channels, input channels and filter dimension respectively. For instance, a 2-dimensional convolution on image data would result in ki = Ki,:k,, where Ki,, define the filter size.
(h) h (((1-))(((1)) (!-11)
We distinguish two kinds of neural networks, a target network Jr and a source network Ss- JT is approximated by lottery ticket (LT) that is obtained by masking the parameters of Is and, in case of a weak LT, learning of the parameters. We assume that fr has depth and parameters ((()) T bif WT,,, NTTA,TT)) are the weight, bias, number of neurons and number of nonzero parameters of the weight matrix in Layer 1 {1, LJ. Note that this implies m4 S m-m41- Similarly, fs (1) 600 n,s,, m.s.) t=n Note that / ranges from 0 to L for the source network, while it only ranges from 1 to L for the target network. The extra source network layer 1 = 0 accounts for extra layer that we need in our LT construction.
has depth L + 1 with parameters (W!"
3

---

Under review as a conference paper at ICLR 2023
ER networks Instead of complete source network, we will consider random Brdös-RRény (ER) networks FER E ER(p) with layerwise sparsity ratios Pt- fER can be defined as subnetwork of a complete source network using binary mask SER E {0, 1000m-1---11 or S {0, 1) x for every layer. The mask entries are drawn from independent Bernoulli distributions with layerwise success probability pt O, i.c., FR Ber(pi). The random pruning is performed initially (1)
with negligible computational overhead and the mask stays fixed during training. Note that pt is also the expected density of that layer. The overall expected density of the network is given as E mcP: = 1 sparsity. In case of uniform pl = p, we also write ER(p) instead of (p)) An 22 mh
ER neural network is defined as SER = fs W SER). We will also call JER E (R(p) the source network, as we might need to prune additional parameters during LT construction. Here p denotes the vector of layerwise success probabilities. This pruning defines another mask SLT, which is a subnetwork of SER, i.e., zero entry ,i, 0 implies also a zero in Stj,T = O, but the converse is not true. We skip the subscripts LT or ER if the nature of the mask is clear from the context.
2.1 EXISTENCE OF STRONG LOTTERY TICKETS
Most strong lottery ticket (SLT) existence proof's construct explicitly a LT that approximates any target network of given width and depth. The LT is defined by a mask that encodes the result of pruning a randomly initialized source network. Most proofs that derive a logarithmic lower bound on the overparametrization factor (i.e., the factor by which the source network is supposed to be wider than the target network) (Pensia et al. 2020 Burkholz et al. 2022 Burkholz] 2022a da Cunha et al., 2022, Burkholz 2022b; Ferbach et al. 2022), solve multiple subset sum approximation problems Lueker 1998). For every target parameter 2, they identify some random parameters of the source network X1 ..... X, that can be masked or not approximate x. In case of ER source network, 1 1 p random connections are missing in comparison with a dense source network. These missing connections also reduce the amount of available source parameters X1,..., X,, To take this into account, we modify the corresponding subset sum approximations according to the following lemma.
Lemma 2.1 (Subset sum approximation in ER Networks). Let XI,... be independent, uniformly distributed random variables so that X; U([-1,1) and MI,..., Mn. be independent, Bernoulli distributed random variables so that M;- ~ Ber(p) for a > 0. Let e, 5 E (0,1) be given. Then for any 2 E [-1,1] 1] there exists a subset I C [n] so that with probability at least 1 8 we have
Iz Eier ier M,X,| < if
1
2 C
1og(1/(1 p)) log
(1)
min (ō,
The proof is given in Appendix A.2 and utilizes the original subset sum approximation result for random subsets of the base set X1 X..... Xn. In addition, it solves the challenge combine the involved constants respecting the probability distribution of the random subsets. For simplicity, we have formulated for uniform random variables and target parameters 2 E [-1, 1] but could be easily extended to random variables that contain uniform distribution (like normal distributions)
and generally bounded targets as in Corollary in (Burkholz et al. 2022).
In comparison with the original subset sum approximation result, we need base set that is larger by a factor Iog(1/11pp1- This exactly the factor by which we can modify contemporary SLT existence results to transfer to ER source networks. By replacing the subset sum approximation construction with Lemma 2.1 we can thus show SLT existence for fully-connected (Pensia al. 2020 Burkholz
2022b), convolutional (Burkholz et al. 2022 | [0022a] da Cunha et al. 20022. and residual ER networks (Burkholz) (202aa) or random GNNs (Ferbach al. (2022). To give an example for the effective use of this lemma and discuss the general transfer strategy. we explicitly extend the SLT existence results by /Burkholz (2022b) for fully-connected networks ER source networks. We thus show that pruning a random source network of depth I, + 1 with widths larger than logarithmic factor can approximate any target network of depth with a given probability 5.
Theorem 2.2 (Existence of SLTs in ER Networks). Lei e, (0, 1), a target network Fr of depth L. an ER(p) source network fs of depth L + with edge probabilities in each layer I and iid initial parameters O with wij ~ U[[-1,1]), (19) U[]),1)) be given. Then with probability at least o, there exists mask SIT so that each target output component is approximated as
(t)
4

---

Under review as a conference paper at ICLR 2023
maX [ - fs We Str)ll S if
ng, 2 C
log (1/(1 p(+1)) log min 5/p}
RTH
for 1 1, where
g(c, is defined in Appendix A.2 and p
log(1/(11 -min P log(1/ min(mmnn G, (,))) for any Y 0. We also require ngg,0
CNT
Cd [o log minte.1705)) where C' > 0 denotes a generic constant that is indepen- dent of NT, L, Pb, 8, and
Proof Outline: The main LT construction idea is visualized in Fig. 3 (b). For every target neuron, multiple approximating copies are created in the respective layer of the LT to serve basis for modified subset sum approximations (see Lemma 2.1] of the parameters that lead to the next layer. In line with this approach, the first layer of the LT consists of univariate blocks that create multiple copies of the input neurons. In addition to Lemma 2.1 also the total number of subset sum approximation problems p that have to be solved needs be re-assessed for ER source networks, as this influences the probability of LT existence. This modification is driven by the same factor as the width increase. The full proof is given in Appendix A.2
Experiments for SLTs To verify the existence of SLTs in ER networks experimentally, we have conducted experiments with a ResNet18 model on CIFARIO 10. Average results based on independent repetitions are shown in Table T We initialize the ResNet18 88 as a sparse ER network and use the edge-popup (Ramanujan et al., 2020) algorithm to find a SLT, restricting edge-popup popup only to the nonzero (unmasked) parameters in the ER network explained in Fig. I Our results show that it is possible to obtain SLTs by starting pruming from a sparse random network instead of a dense network. Importantly, we start with sparse ER network of up 0.8 sparsity and still achieve competetive performance to find a SLT with final sparsity 0.9, without the need to train a dense network from scratch. Additional experiments for R and VGG16 on CIFARIO and Res on CIFAR 100 are presented in the appendix (see, e.g., Table 13 and 15
Sparsity 0 - 0.9
0.5 + 0.9
0.7 0.9
0.5 + 0.95
0.8
0.95
0.5 - 0.99
Test Ace. 87.9 0.2
88.1 + 0.3 88.0 0.3
87.8 0.3
88.1 + 0.1 87.9 + 0.1
Table 1: ER networks for Strong Lottery Tickets: Average results and 0.95 standard confidence intervals for training an ER ResNet18 network with edge popup (Ramanujan et al. 2020) on CIFARIO. 10. The ER network is initialized with uniform initial sparsity, which is gradually annealed to attain SLT of the final sparsity (initial >> final sparsity). Note that the first column serves as baseline.
2.2 EXISTENCE OF WEAK LOTTERY TICKETS
LT existence proofs have been restricted to SLT's, which do not need to be trained after pruning. These proof' (Fischer et 202 Burkholz 2022b Pensia al., 2020) automatically hold for WLTs, as every SLT is also a WLT. Hence, SLTs and WLTs in ER networks exist as we have shown with Theorem 2.2 However, the constructed LTs have usually more parameters than the target network, as the sum over multiple random weight parameters is used to approximate a single target parameter. If we could use only one parameter in the source network for every target we could potentially achieve sparser LT's. The reason that LT theory is primarily focused on SLT' is because it is not well understood what properties and parameter initialization schemes render arbitrarily pruned networks trainable with SGD Li et al. (2016); Han et al. (2015). ER masks, however, do not seem to suffer from this limitation, as they have been found to be well trainable in practice (Su et al. 2020 Ma et al.] 202T Liu al. (021). which we also verify in experiments in Section 3 in broader context with different choices of layerwise sparsity ratios. The following assumption underlying our WLT existence proofs is therefore justified. ER networks are well trainable with SGD for different layerwise sparsity ratios and standard weight initialization schemes.
Assumption 2.3 (ER networks are trainable). An ER network f < FRR(p) with layerwise density vector p is trainable by SGD with standard weight initializations (He et al. 2015).
Based on this assumption, we provide a construction of a LT by deriving an exact representation of the target network that only uses existing edges of random ER network.
5

---

Under review as a conference paper at ICLR 2023
2.3 WLT EXISTENCE FOR A SINGLE HIDDEN LAYER TARGET NETWORK
We start with showing WLT existence for a single hidden layer fully-connected target network. Our proof strategy is visually explained in Figure To approximate target network with a single hidden layer, we use a two hidden layer ER source network. For a given density, the following theorem identifies the width of an ER source network, above which we can show existence.
Theorem 2.4 (Existence of an ER network as a WLT for single hidden layer target network). Let Assumption 2.3 be fulfilled and a single layer fully-comnected target network fr(x) = (
(2) of o(W(") + ) bf 6 E (0, 1), target density p and 2 layer ER source network
fs E ER(p) with widths ns,o = qud, ns,,1 qr ngg = 92 be given. If
2m 191
log(1/(1 p2)) log 22mT22
90 2 (g(11(1-p1)) log
and Q2 1,
then with a probability - 8 the source network fs contains weak LT fW
Proof Outline: Similar to the strategy for SLTs, we create an univariate first layer in the source network as explained in Fig. [ Different from the subset sum approximation case of SLTs, we can now use the trainability assumption 2.3 to choose a weight in the source ER network which exactly learns the value of target weight. The key idea is to create multiple copies (blocks in Fig. (b)) in the source network for each target neuron such that every target link is realized by pointing to at least one of these copies in the ER source. the appendix, we derive the corresponding weight and bias parameters that can be learned by SGD. Thus, our main task is to estimate the probability that we can find representatives
all target links in the ER source network, i.e., every neuron Layer / = has at least one edge to every block in I 0 of size qo, as shown in Fig. (b). This probability is given by (1 - Pi 90) ) 111191 For the second layer, we repeat a similar argument to bound the probability (1
p22) m with 92 1, since we do not require multiple copies of the output neurons. Bounding this probability by 1 - completes the proof, as detailed in Appendix A.3
Theorem 2.4 shows that qu and @1 depend on 1/ log( (1/sparsity) We now generalize the idea to create multiple copies of target neurons in every layer to a fully connected network of depth L, which yields similar result as above and is stated formally in Theorem 2.5
Target Network fr(
Source Network fs (z)
ER with Edge-Popup fs Ws SER)
107,3
1T.11
n18 qud
(a)
(6)
(c)
Figure 1: LT's in ER networks: In (a), (x) is a single layer target network. (b) visualizes the source network fz(x). which contains a WLT. (c) shows a strong LT. The figure shows connections for only one neuron in every layer of fs for simplicity. Dotted and solid lines belong the random mask SER. while the solid lines belong to nonzero weights of the final LT (SLT).
2.4 EXTENSION TO L-LAYER TARGET NETWORKS
Extending our insight from the 2-layer construction of the source network in the previous section, we provide a general result for target network fr of depth L and ER source networks with different layerwise sparsity ratios p:. While we could approximate each target layer separately with two ER source layers, instead present construction that requires only one additional layer that L. = + 1. This transfers the approach for SLTs SLTs|Burte Burkholz (2022bja) to weak ER networks. But have to solve two extra challenges. (a) We need to ensure that sufficient number of neurons is

---

Under review as a conference paper at ICLR 2023
connected the main network and can be used in the LT construction. (b) We have show that the required number potential matches for target neurons qi does not explode for an increasing number of layers. In fact it only scales logarithmically in the relevant variables.
Theorem 2.5 (Existence of weak lottery tickets in ER networks). ). With Assumption 2.3 given fully connected target network fr of depth L. 8 E (0, 1), a target density p and a L + l-layer ER source network fs E ER(p) with widths nig,o qod and nig, =qUTA, {1,2, L.), where
L for 10, L 1} and qr. = 1,
q1 2 log(1/(1 (p(1((11)tt1) log
then with probubility the random source network Is contains a weak LT SWLT-
Proof Outline: Again we follow the same procedure of finding the smallest width for every layer in the source network such that there is at least one connecting edge between target neuron copy and one of the copies in the previous layer. Repeating this argument for every layer starting from the output layer in reverse order gives us the lower bound on the factor qi in every layer I (0, 1,,, L.). We can use the trainability assumption 2.33 to choose the weights of the sparse ER network such that for every target parameter there is at least one nonzero (unmasked) parameter in the source which exactly learns the required value. Full details are given in Appendix A.4
2.5 EXISTENCE FOR CONVOLUTIONAL LAYERS
We can also extend our WLT existence results in ER networks to convolutional layers whose number of channels need to be overparameterized by factor of 1/ log(1 (og((1/spag /sparsity).
Theorem 2.6 (Existence of WLTs for ER networks with convolutional layers). With Assumption 2.3
given target network fr of depth L with convolutional layers (. = =E w
zij at-
T.s: Wr E Rexa-ixk, E (0, 1), target density p and L + 1-layer ER source network fs E ER(p) with convolutional layers his = =Σ w S.ij zij where
(1-1) + bg.. Ws E R Xkk
log LMIr+419411 for 10. I..,,--- 11 and qu = 1,
11 log(1/(1 p)+1))
8
then with probability 1 the source network I's contains a weak LT fWIT.
Main idea: Similarly as in case of fully-connected ER source networks, we create qi copies of every output channel of the target e in the LT. Every filter element of the target can be learnt using the trainability assumption 2.3 Note that any tensor entry that leads to the same block is sufficient, since
the convolution is bi-linear operation so that Σvel. Wv æ; = (Erel. Wvy) * xz. Specifically,
EVEL, w 5 can represent a target element ((()) method is visually explained in Fig. allongside the full proof in Appendix A.5
least one weight w ws.. S je
(I)
is nonzero. Our
Theoretical insights We have shown that ER networks provably good starting point to find SLTs and WLTs without the overhead of multiple prune-train iterations. Our analysis furthermore reveals that ER networks are still overparametrized, many of the random edges get pruned in the LT construction. This insight presents a theoretical justification for pruning approaches that start from random ER masks like Dynamic Sparse Training (Evei et al. 2020a Mocanu et al., 2018).
But how far can we go with random ER masks alone? Our LT constructions suggest a need for considerable overparamettriatton if we wanted to start from ER masks with extreme initial sparsities 2 0.9, since 1/ log(1/(1 Pı)) 2 1/p: for << 1. The next theorem establishes that we cannot expect to get around this 1/ (0g((1/(1 pt)) limitation. Targeted rewiring, however, might improve even extremely sparse random masks, as we demonstrate in experiments.
Theorem 2.7 (Lower bound on overparametriiation in ER networks). There exist univariate target networks (x) o(wFx + by) that cannot be represented by a random 1-hidden-layer ER source network fs E ER(p) (i.e. weak or strong LT) with probability at least - 8, if its width is
ns,1 < 1og(1/(1pp) log [-(1-8)173
7

---

Under review as a conference paper at ICLR 2023
3 EXPERIMENTS FOR WEAK LOTTERY TICKETS
Our existence proofs for WLTs rely on the property that ER networks are trainable in practice. We perform experiments benchmark image datasets to validate this assumption.
Layerwise Sparsity Ratios There are plenty of reasonable choices for the layerwise sparsity ratios and thus ER probabilities Pt- Our theory applies to all of them. The optimal choice for a given source network architecture depends on the target network and thus the solution to a learning problem, which usually unknown a-priori in practice. To demonstrate that our theory holds for different approaches and to provide practical insights into standard image classification problems, we investigate the following layerwise sparsity ratios in experiments. The simplest baseline is a globally uniform choice (Liu et al. 2021 have compared this choice in extensive experiments with their main proposal, ERK, which assigns pl x Pinthouu to linear and pt sttタ-1th
6. 1ht (Mocanu et al. 2017) to a convolutional layer. In addition, we propose a pyramidal and balanced approach, which are visualized in Appendix (nrpendix(A.44fae for VGG19.
RenBaut
Pyramidal: This method emulates a property WLTs that are obtained by IMP (Frankle & Carbin 2019), that is the layer densities decay with increasing depth of the network. For network of depth L,
we use Pl = (pr)² Pt E (0, 1) so that
Ei=k pimm
= p. Given the architecture, we use a polynomial
El=l m:
equation solver Harris et al. (2020) to obtain Pt for the first layer such that p1 E (0, 1).
Balanced: The second layerwise sparsity method aims to maintain the same number of parameters in every layer for a given target network sparsity p and source network architecture. Each neuron has a similar in- and out-degree on average. Every layer has x = f EEE my nonzero parameters. Such an ER network can be realized with pt = =x/m; In case that mi, we set pt
To judge the quality of LT pruning algorithms, ER randomizations of pruned tickets have also been studied as baselines, which challenge state-of-the-an pruning algorithms (Su et al. (2020); Ma et al. (202I). The corresponding sparsity ratios are computationally more cumbersome to obtain and thus of reduced practical interest. We still report comparisons with randomized Snip (Lee al. 2018).
Iterative Synflow (Tankaa et al. 2020). and IMP (Frankle & Carbin 2019).
Sparsity
Pyramidal
Balanced
Uniform
ERK
Snip (ER)
Synflow (ER)
IMP (ER)
0.9
92.9
93.2
91.3
92.7
93.2
91.4
90
0.99
90.4
89.3
82.7
87.8
26.3
86.6
90.2
0.995
87.8
85.9
73.7
84.5
10
84
79
0.999
10
68.7
14.2
59.2
10
63.8
10
Table 2: ER networks with different layerwise sparsities on CIFARIO with VGGI6. We compare test accuracies of our layerwise sparsity ratios balanced and pyramidal with the uniform baseline, ERK and ER networks with layerwise sparsitiy ratios obtained by IMP, Iterative Synflow and Snip (denoted by ER). Confidence intervals reported in Appendix A.8
To complement (Liu et 2021), we conduct experiments in more extreme sparsity regimes 2 0.9 to test the limit up to which ER networks are viable alternative to more advanced but computationally expensive pruning algorithms. We show empirically that even in regimes of reduced performance, rewiring edges by Dynamical Sparse Training (DST) can improve the performance substantially. which highlights the utility of random ER masks even at extreme sparsities.
Experimental Setup We conduct our experiments with two datasets built for image classification tasks: CIFARIO and CIFAR100) Krizhevsky et al. (2009). Additional experiments on Tiny Imagenet (Russakovsky et al.] 2015) are reported in Appendix [2. We train two popular architectures, VGGI6 Simonyan & Zisserman (2015) and ResNet He et al. (2016), to classify images in the CIFARIO 10 dataset. On the larger CIFARIO 100 dataset, we use VGG19 and ResNet50. Each model is trained using SGD with learning rate 0.1 and momentum 0.9 with weight decay 0.0005 and batch size 128. We use the same hyperparameters as Ma et al. (2021) and train every model for 160 epochs. We repeat all our experiments over three runs and report averages and standard 0.95-confidence intervals, which can be found in the appendix due space constraints. Our code builds on the work
8

---

Under review as a conference paper at ICLR 2023
of Liu et al. ); Tanaka et al. (2020) and is included in the supplement. All our experiments were
run with 4 Nvidia A100 GPUs
Results on CIFARIO and CIEAR100 Experiments on the CIFARIO dataset are shown in Table 2 and The pyramidal and balanced methods are competitive and even outperiorm ERK in our experiments for sparsities up 0.99. Importantly, they also outperform layerwise sparsity ratios obtained by the expensive iterative pruning algorithms Synflow and IMP. However, for extreme sparsities p 2 0.99, the performance of ER networks drops significantly and even completely breaks down for methods like ER Snip and pyramidal. We conjecture that ER Snip and pyramidal are susceptible to layer collapse in the higher layers and even flow repair (see Appendix A.. cannot
on CIFARI00 in Table 3
dramatically increase the network's 's expressiveness. Additional results with ResNets on CIFARIO
and 100 are reported in the Appendix A.8
Sparsity
Pyramidal
Balanced
Uniform
ERK
Snip (ER)
Synflow (ER)
IMP (ER)
0.5
73.6
73.9
72.8
73.6
73.8
72.6
71
0.8
73.7
73.5
71.4
72.8
74
71.6
68.2
0.9
72.7
72.5
69.1
71.9
73
70.8
63
0.99
60
65.3
55.8
63.8
62.6
1
Table 3: ER networks CIFARIO0 with VGG19. Extending the comparison in Table accuracies on the CIFAR100 dataset. See Appendix for A.8 for confidence intervals.
2 to test
Dynamical Sparse Training In order to improve the expressiveness of ER networks and achieve extremely sparse WLTs, ER networks can be rewired with the help of DST. Specifically, we use the algorithm RiGL (Evci et al. (2000a). First, we only rewire edges, which allows us to start from relatively sparse networks. Our results on CIFARIO 10 with VGG16 in Table indicaae that DST can improve even extremely sparse architectures. Usually, however, DST is started from ER networks with sparsity 0.5. We show in the appendix that can also be initialized at higher sparsity with insignificant losses in accuracy. In particular, initial balanced pyramidal sparsity ratios seem to be able to improve the performance of RiGL. In Appendix A3.3] we report additional experiments that further illustrate the utility of balanced and pyramidal sparsity ratios for typical DST experiments that prune ER networks. These results suggest that there is potential for tuning ER sparsity ratios to reduce computational costs and increase predictive performance.
Sparsity 0.99
Sparsity 0.995
Sparsity 0.999
ER Method
Original
Rewired
Original
Rewired
Original
Rewired
ERK
87.8
90.8
84.5
88.3
59.2
74.1
Balanced
89.3
91.4
85.9
89.3
68.7
78.9
Pyramidal 90.4
92
87.8
90.6
10
9.8
Table 4: ER networks rewired with DST: Test Accuracies for an ER(p) VGGI6 network initialized
with sparsity = 1 p (original) and after rewiring edges with RiGL (Evei et al.. 2020a Liu et al. 2021 (rewired) on CIFAR 10. Confidence intervals are reported Appendix A.13
4 CONCLUSIONS
We have systematically explained the effectiveness of random pruning and thus provided a theoretical justification for the use of Erdös-Rényi (ER) masks as strong baselines for lottery ticket pruming and starting point of dynamical sparse training (DST). This effectiveness has been demonstrated so far only experimentally for weak lottery tickets (WL.T). We have proven theoretically and experimentally that ER networks also contain strong lottery tickets. This finding is also of practical interest, as initial sparse random sparse masks can avoid the computationally expensive process of pruning a dense network from scratch. Remarkably, as we could assume that ER networks are well trainable in practice, we could also prove the existence of WLTs. Our theory holds for a wide range of sparsity ratios, we have also demonstrated in experiments. Yet, it suggests the necessity of high overparametrization in regimes of extreme sparsity. These limitations could partially be remedied by combination of random pruning and targeted rewiring as, for instance, realized by DST.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mikhail Belkin, Daniel Hsub, Siyuan Maa, and Soumik Mandala. Reconciling modern machine learning practice and the bias-variance trade-off. stat, 1050:10, 2019.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. In International Conference on Learning Representations, 2018.
Rebekka Burkholz. Convolutional and residual networks provably contain lottery tickets. In Interna- tional Conference on Machine Learning, 2022a.
Rebekka Burkholz. Most activation functions can win the lottery without excessive depth. In Advances in Neural Information Processing Systems, 2022b.
Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the existence of universal lottery tickets. In International Conference on Learning Representations, 2022.
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overparameterrization in model compression: From double descent pruning neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6974-6983, 2021.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. convolutional neural networks. In International Conference on Learning Representations 2022.
Proving the lottery ticket hypothesis for
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. 2019.
James Diffenderfer and Bhavya Kailkhura. Multi-prizz lottery ticket hypothesis: Finding accurate binary neural networks by pruning a randomly weighted network. In International Conference on Learning Representations, 2021. URL
mat 0b9iv
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. Advances in Neural Information Processing Systems, 30, 2017.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952. PMLR, 2020a.
Utku Evei, Yani Ioannou, Cem Keskin, and Yann Dauphin. Gradient flow in sparse neural networks and how lottery tickets win. 2020b.
Damien Ferbach, Christos Tsirigotis, Gauthier Gidel, and Bose Avishek. A general framework for proving the equivariant strong lottery ticket hypothesis, 2022.
Jonas Fischer and Rebekka Burkholz. Plant 'n' seek: Can you find the winning ticket? In International Conference on Learning Representations, 2022. URL httpppss://peeeeeeeeee...... httpee/wwwwwe.eeeeeeeeeeeeeeeeee forum?
lid 9n9c8sf0xm
Jonas Fischer, Advait Gadhikar, and Rebekka Burkholz. Towards strong pruning for lottery tickets with non-zero biases, 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable
neural networks. International Conference on Learning Representations, 2019. URL https
net / " b3RcF7
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? In International Conference on Learning Representations, 2021. URL httts::://// httttpps://ppnnrviiee
net/
VyQc MLK
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. CoRR, abs/1902.09574, 2019. URL http: //apivv.//xvv...// wwwp:/iivorr//aaa...o abs wwt.b////11....0 09574
Anna Golubeva, Guy Gui-Ari, and Behnam Neyshabur. Are wider nets better given the same number of parameters? In International Conference Learning Representations, 2021.
10

---

Under review as a conference paper at ICLR 2023
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy, Nature, 581c1585578825555-666.6 September 2020. doi: 10. URL http::ttp::/d/oo
del Río, Mark Wiebe, Pearu Peterson, Pierre
1038/ (12388841111 841 586 020-2649-
B. Hassibi, D.G. Stork. and G.J. Wolff. Optimal brain surgeon and general network pruning. In IEEE International Conference on Neural Networks, pp. 293-299 vol.1, 1993. doi: 10.1199//CN..1999 298572.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leve performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition. pp. 770-778, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 and eifar- 100 datasets. URl: https://www. cs. toronto. edu/kriz/cifar html, 6(1):1, 2009.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. In D. Touret- zky (ed.), Advances in Neural Information Processing Systems, volume 2. Morgan- Kaufmann, 1989. URL htttps::/pprocsedl.nne neurips wttpuuuips.ccpppprer.eeeoa wctpapper/19////1ee.... pdf
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2018.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. 2016.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruming: Return of the most naive baseline for sparse training. In International Conference on Learning Representations, 2021.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 2021.
George S. Lueker. Exponentially small bounds the expected optimum of the partition and subset sum problems. Random Structures and Algorithms, 12:51-62 62, 1998.
Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Minghai Qin, Sijia Liu, Zhangyang Wang, and Yanzhi Wang. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL fnJ
https::/opeereeee
net http://ouummmmmm/eeeee
Eran Malach, Gilad Yehudai, Shai Shalev-Schwand and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6682 6691. PMLR, 13-18 Jul 2020. URL https: httsss//poccceeddeeeeee m wtr.press/wl19// wttp://allaaahcccm ach20a html

---

Under review as a conference paper at ICLR 2023
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Evolutionary training of sparse artificial neural networks: a network science perspective. 2017.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong Nguyen, Madeleine Gibescu, and Antomio Liotta. Scalable training of artificial neural networks with adaptive sparse con- nectivity inspired by network science. Nuture Communications, 9(1), jun 2018. doi: 10.1038/ 1414660011-04316.3.
1038 2F3382FF44100 /tt///o..00011111110090551111110
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. 2016.
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. Advances in Neural Information Processing Systems, 33:2925 13:2925-2293, 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic veer-parameterization is sufficient. Advances in Neural Information Processing Systems, 33:2599-26100 2020.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's 's hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 11893-11900 2020.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations, 2019.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 (3):211-252, 2015, doi: 10.1007/s| 1263-015-0816-y.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification, 2020. BRR.phttss////eeeetttttt ew net. f http://orrmmmm--JJeeeeee d=BJe
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. http:t/t///aaa
org/ abs / 1409. 1556
Kartik Sreenivasan, Shashank Rajput, Jy- Sohn, and Dimitris Papailiopoulos. Finding nearly everything within random binary networks. In Gustau Camps- Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3531-3541. PMLR, 28-30 Mar 2022a.
Kartik Sreenivasan, Jy-yong Sohn, Liu Yang, Matthew Grinde, Alliot Nagle, Hongyi Wang. Kang- wook Lee, and Dimitris Papailiopoulos. Rare gems: Finding lottery tickets initialization, 2022b.
URL http::tt////aatttt http:///xxvvoogg/////// abs/2202. 12002
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao. Liwei Wang, and Jason D Lec. Sanity-checking pruning methods: Random tickets can win the jackpot. Advances in Neural Information Processing Systems, 23:20390-20401, 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks with- out any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33:6377-6389, 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. 2020.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Representations, 2019.
12

---

Under review as a conference paper at ICLR 2023
Xin Yu, Thiago Serra, Srikumar Ramalingam, and Shandian Zhe. The combinatorial brain surgeon: Pruning weights that cancel one another in neural networks, 2022. URL https: //rxivaxvvvvv prq/abs/ 2203. 04466
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
A APPENDIX
A.1 FLOW PRESERVATION
Targeted pruning is known to be susceptible to layer collapse just sub-optimal use of resources (given in form of trainable parameters), when intermediary neurons receive no input despite nonzero output weights or zero output weights despite nonzero input weights. To avoid this issue, (Tanaka ict al. 2020) has derived a specific data-independent pruning criterion, i.c., synaptic flow. Yet, flow preservation can also be achieved with simple and computationally efficient random repair strategy that applies to diverse masking methods, including random ER masking.
The main idea behind this algorithm is to connect neurons (or filters) with zero in- out-degree with at least one other randomly chosen neuron (or filter) in the network. To preserve the global sparsity, new edge can replace random previously chosen edge. Alternatively, ER networks with flow preservation could also be obtained by rejection sampling, which is equivalent to conditioning neurons on nonzero in- and out-degrees. To still meet the target density pt, the ER probability pt would need to be appropriately adjusted. Our experiments reveal, however, that most randomly masked standard ResNet and VGG architectures usually perserve flows with high probability for different layerwise sparsity ratios up to sparsities z 0.95 (see Appendix (A.I). The most problematic layers are the first and the last layer if the number input channels and output neurons relatively small. In consequence, most pruning schemes keep these layers relatively dense in general. In our theoretical derivations, we assume flow preservation in the first layer.
100
Tet Accuracy
60
0-
0.9
0.99
0.995
0.999
Sparsity
balanced (ours)
pyramidal (ours)
uniform
ERK
ER Snip
Figure 2:
Flow Comparison: We compare the results of ER networks for each layerwise sparsity
method with and without flow preservation. Solid lines denote that flow is preserved while dotted lines show the corresponding method without flow preservation for VGG16 CIFAR10.
We propose two methods to achieve flow preservation, which guarantees that every neuron (or filter) has least in-degree and out-degree
We can resample the mask edges s ER of the neurons (filters) that have zero in-degree or a zero out-degree till there at least one in-degree and ont-out-e for that neuron.
Rejection Sampling:
We randomly add an edge to neuron with zero in-degree out-degree. While this method adds an extra edge in the network, the total number edges that need to added are usually negligible in practice.
Random Addition:
13

---

Under review as a conference paper at ICLR 2023
We verify the number of corrections required in an ER network to preserve flow. Notice that in most cases ER networks inherently preserve flow. For each the used layerwise sparsity ratios, we calculate the number of connections (edges) added in the network to ensure that every neuron (or filter) has at least in-degree and one out-degree using the Random Addition method. Tables 5 and show the results.
Sparsity
ResNet50
0.5
0.8
0.9
0.99
0.999
Uniform
0
0.33
1
51.67
108
ERK
0
0
29.33
105.67
ER Snip
0
0
10.67
59
87
Balanced (ours)
0
0
23.33
92.33
Pyramidal (ours)
0
0
1
47.67
91
Table 5: Average number of mask edges added by flow correction the ResNet18 network for CIFARIO 100 across three runs.
Sparsity
VGG19
0.5
0.8
0.9
0.99
0.999
Uniform
0.33
1.33
3
ERK
0
0
0
0
30.33
ER Snip
14.33
25
Balanced (ours)
0
0
0
23.33
Pyramidal (ours)
8
22
Table 6: Average number of mask edges added by flow correction in the VGGI9 network for CIFAR 100 averaged across three runs. Note that the number of flow corrected neurons (filters) is negligible in comparison to the number of nonzero parameters in VGG19 even for the lowest density of 0.001, which is 38, 000 parameters.
Our analysis shows that flow preservation is an important property that avoids layer collapse in sparse networks and is inherently satisfied in reasonable sparsity regimes Ro 0.9. It has a similar effect as making the final layer and the initial layer dense during pruning, which followed in some pruning algorithms (Liu et al. 2021
Figure Segurarcompprrs the different layerwise sparsity methods for ER networks with and without flow preservation. Our results show that flow preservation is especially important in Pyramidal and ER Snip methods. Both these methods have a higher sparsity in the final layer which leads performance problems in case of high global sparsities. Flow preservation is able to address this partially so that clear improvement visible for the pyramidal method sparsities 0.99 and 0.995.
A.2 PROOF FOR EXISTENCE OF STRONG LOTTERY TICKETS IN NETWORKS
As discussed in the main manuscript, most SLT existence proofs that derive a logarithmic lower bound on the overparametrization factor of the source network utilize subset sum approximation (Lucker 1998) in the explicit construction of lottery ticket that approximates target network (Pensia et al. 2020 Burkholz et al., 2022 Burkholz 2022a da Cunha et al., 2022 Burkholz) (022b). We can transfer all of these proofs ER source networks by modifying the subset approximation results to random variables that are set to zero with Bernoulli probability p to account for randomly missing links in the source network. We just have to replace Lueker's subset sum approximation result by Lemma 2.1 in the corresponding proofs. For simplicity, we have formulated it for uniform random variables and target parameters 2 e [-1, 1] but it could be easily extended to random variables that contain uniform distribution (like normal distributions) and generally bounded targets in Corollary 7 in (Burkholz et al. 2022). For convenience, we restate Lemma 2.1 from the main manuscript:
Lemma A.1 (Subset sum approximation ER Networks), Let X,,..., , X,, be independent, uniformly M1,..., .,., M be independent, Bernoulli
distributed random variables so that X, U[[11, 1]) and M1,
14

---

Under review as a conference paper at ICLR 2023
distributed random variables that M, Ber(p) for a > O. Let E (0,1) be given. Then for any 2 E [-1,1] there exists a subset C [n]] so that with probability at least 1 - we have 1 Lier ier M,X;| if
1
2 C log(1/(1 - p))
log
(2)
min (6,
Proof Random variables X; M,X; do not contribute to the approximation of target value if they are zero and thus in particular in the case that M, O. which happens with probability 1 - for each index i. We can thus remove all the variables X; for which M, = After a change of indexing, we arrive at a subset XI,.., Xx of K random variables, which are uniformly distributed as X; M, X, ([[-,,1], since M, independent of X,, The number variables K follows a binomial distribution, K ~ Bin(n, p), since M1 M,, are independent Bernoulli distributed.
For fixed K k. Lueker (1998) has proven that there exists constants ag > 0 and bk 0 so that the probability that the approximation is not possible is of the form
(AI C [R:) 1a Eier X.1 d') I az exp( /////b
Using this result and defining == |aX ag > 0 and = minkeln| by >> O, we just have to take an average with respect to the random variable K ~ Bin(B.
P
C
[n))
Σx1
a exp( bb)k))
k ()
p0(1 -p)
iEI
k=0
a
exp( bbbpp' (1 p)n-
e'
k
k=0
a
マ
- p(1
To ensure the subset sum approximation is feasible with probability of least - 8 we need fulfill
_ 1 p(1 - exp( <
Solving for n leads to
2
log (ge)
log (-p(1-exp(-n))
This inequality satisfied if
1
n 2 C
log(1/(( (1/(1 p)) log
min(f
for generic constant C > that depends on a and b.
With this modified subset sum approximation, we show next that in comparison with a complete source network, an ER network needs be wider by a factor log(1/(1pp)) (P]]] To provide an example of how to transfer an SLT existence proof, we focus on the construction by Burkholz (2022b).
Note that in all our theorems we assume that flow is preserved in the first layer, as it is reasonable to apply a simple and computationally cheap flow preservation algorithm after drawing a random mask (see Appendix AIII. 1b. This algorithm just ensures that all neurons are connected to the main network and are thus useful for training a neural network.
If we do not assume that flow is preserved, some neurons in the first layer might be disconnected from all input neurons with probability (1 - pd Disconnected neurons could simply be ignored in the LT construction. Their share is usually negligible but, technically, without flow preservation, would need to ensure that ns,1 2 C(1 - Pn)* + n where n² denotes the bound on the width that we actually going to derive.
15

---

Under review as a conference paper at ICLR 2023
Theorem A.2 (Existence of SLTs in ER Networks). Let c, (0,1), a target network fr of depth L, an ER(P source network fs of depth + with edge probabiliriess pt in each layer and iid initial parameters 0 with wij least 6, there exisls mask SIT that each target oulput component is upproximated as max [Ifr;((x) - fs,(æ;; Ws LLT) S if
(1) [[[-1,1]); b." -[] be given. Then with probability at
nss 2 C RT.
log (1/(1 p(+1)) log mii((e,,0/p)
for 1 1. where El g(e, fT) is defined in Equation and P CNT log(1/ min El, 61) for any 7 2 0. We also require T1g,0
C'd log(1/(1- [p]] log min(c1,5/05) where C' 0 denotes generic constant that is indepen- dent of nr,, L, Pt, 8, and
Here, g(c) is defined in accordance with Lemma 5.1 in (Burkholz 2022b
L-1
el gl, WT.
(1 (1+ B 11 ; II (I 10 - k=111
B:
sup aED
!1 |
||1
Proof To prove the existence of strong lottery tickets ER networks, we modify the proof by (Burkholz 2022b) for complete fully-connected networks.
We first answer the question, how the fact that random weights are set irreversibly to zero, changes construction. Fig. [1] visualizes the general schematic. The general idea is that we have to create multiple copies Pt of each target neuron in the LT, as these will enable the approximation of target parameters by utilizing subset approximation as modified by Lemma 2.1
First, as Fig. [ visualizes, we have to argue why and how we can create univariate blocks the first layer or in general 2L constructions. In this case, target layer is approximated by appropriately pruned layers of the source network. The first of these two source layers contains only univariate neurons that form blocks that consist of neurons of the same type, which correspond the same input target neuron i. All weights that start in the same block i and end in the same neuron j can then be utitilzed to approximate the target parameter WT, The required univariate blocks can be easily realized by pruning if flow is preserved. The reason is that each neuron in source layer / = 0 has at least one in-coming edge, which can survive the pruning. Since this edge could be adjacent to any of the input neurons with the same probability, we can always find enough neurons in Layer / = 0 that point to any of the input neurons and this allows us to form univariate blocks of similar size B.
Second, we have to analyze how the construction of each following target layer is affected by randomly missing edges the source network. Each target weight w can be approximated by the LT approximates the target neuron and
m() ms S..pp s. where the neuron the neuron j' in the LT approximates the target neuron j. The subset / chosen based on a modified subset sum approximation and informs the mask of the LT. Thus, exists according to Lemma [.
W7. ESer
(i) since the initially random mask entries of the source network ms.rz' are Bernoulli distributed with probability Pt.
The second issue that needs to be modified for ER networks is the analysis of the number of required subset sum approximation problems p. As explained before, the main idea of the construction is to create At copies of each target neuron in target Layer / in Layer I of the LT. These copies serve then multiple subset sum approximations to approximate the target neurons the next layer in a similar way as the univariate blocks of the first layer. This, however, increases the total number of subset sum approximation problems p that need to be solved and that influence the probability with which solve all of them. Using a union bound, modified for ER networks. Similar to (Burkholz)) (2026)) we can derive lower bound on Pi in the subsequent layers, so that the subset sum approximation is feasible for every parameter of layer /
spend 8/p every approximation with
16

---

Under review as a conference paper at ICLR 2023
when the block size B is
1
B Z
log
log( [1((1 pi))
8
so that with an appropriately chosen constant C' we have
C log
B 2
log(1/(1 - pp)))
min p p.
so that it follows in total that
TT,
n.s 2 C log(1/(1 p1+1))
log
The remaining objective is to find p p'= ='= p/. where p' is the factor of increased subset sum approximation problems required to approximate L target layers with an ER source network and pt counts the number of parameters in each LTT layer.
Following Burkholz 2022b)'s method to identify P. we start with the last layer. The num- ber Pr. of subset sum approximation problems that have to be solved to approximate the last layer determines the number of neurons required in the previous layer. This in turn determines the required number of neurons in the layer before it, etc. The last layer requires to solve exactly P'z = 1T.LLT, subset sum problems which can be solved As we would need maximally Iog(1/(1-p.J]] log(1/ min(er, 8/p')) sets of the target parameters CNL-1 log(1/ min 8/p1)). 8/p//1) Repeating CN,
with sufficiently high probability if n,,t-1
Cur.L-1 log(1/ (en,
log(1/(1-P.)
C
in the last layer, can bound P2-11 I log(1/(1-PL)
the same argument for every layer, we derive pi S log(1/ P(+1]] log(1/ min(E44,,8/))
In total, we find that p' Σtn di I Et Tog(1/(1 (1-) log(1/ 8// S ON,
CN
tog(1/()-min p()) log(1/ min min(min/ a, 8/8))) Here, Ni Te, and N, E. A p CN. that fulfills p 2 log(1/(1- min pi) log(1/ min( 5/p}) will be sufficient. It is easy to see that log(1/(1-ming P1) ()) log(1/ min min(mmin (min; 6, 8)) for any Y 2 0 fulfills our requirement.
CN
We have thus shown the existence of SLTs in ER networks following similar ideas as the proof of Theorem 5.2 by Burkholz (2022b). Thus, our construction would also apply to more general activation functions than Us. Note that could also follow the proof strategy of Pensia et al. (2020) to show the existence of strong lottery tickets in ER networks. The key difference between the proofs of Burkholz (2022b) and Pensia al. (2020) is how the subset sum base is created to approximate a target parameter. Pensia et al. (2020) use two layers for every layer in the target and create basis set to approximate every larget weight while Burkholz (2022b) go one step further and create multiple subset sum approximations of every target weight to avoid the two layer construction. In both these cases, the underlying subset sum approximation can be modified as shown above for ER networks and the same proof strategy as (Burkholz) (022b) or (Pensia et al. 2020) can be followed. Similarly, we could also extend our proof's to convolutional and residual architectures (Burkholz) 2022a).
A.3 WLT EXISTENCE PROOF FOR SINGLE HIDDEN LAYER TARGET NETWORK
Theorem A.3 (Existence of an ER network as a WLT for a single hidden layer target net- work). Let Assumption 2.3 be fulfilled and a single layer fully-connected target network fr(x) W (W(")) x + b()) + b. 5 E (0, 1), a target density and a 2 layer ER source network fs E ER(p) with widths ns,o god, Tl,,1 qIT,T,1,55.2 = q2nT222 be given. If
1 90 2 1og(1/(1 - pp)) log
2m
22mT:2
log
and Q2 1,
log(1 [g((1(11 p2))
then with probability 1 the source network Is contains weak LT fWLT fs(æ; Ws SLT)
17

---

Under review as a conference paper at ICLR 2023
Proof of Theorem 2.4 A two hidden layer network can approximate single hidden layer target network as explained in Section 2.4 (9u. q1, 92) are the overparametrriztion factors in each layer in the source network which ensure that we can find the links that we need in our WLT construction. Why would we need any form of overparametrization?? Different from the SLT construction, we do not need employ multiple parameters approximate single parameter and thus do not use any subset sum approximation. Our trainability assumption allows us to define the parameters of the ER source network so that a target network is exactly represented (i.e. with need to prove that we can find all required nonzero entries in our mask. To increase the probability that a target link exists, we also create multiple copies of input neurons. As in the SLT construction, we prune the neurons in first layer to univariate neurons and choose the bias large enough so that the ReLU acts essentially as an identity function. Po > 0 can thus be arbitrary. as long as flow preserved. Note that d22 = 1, as the output neurons for the source and target should be identical nT22 = 2,,2. The last layer (output layer) in the target contain 112,2 neurons and the penultimate layer RT,1- In the source network, we create @i copies of each neuron in the second layer of the target network such that Rs,1 91 X 1r,1- Our goal is to bound the width of Layer I in the ER network such that there is at least one nonzero edge in the ER network for every nonzero target weight. To w122) lower bound 91. each nonzero weight WTij must have at least one nonzero weight (edge) in the source network with sufficiently high probability, i.e., every neuron in the output layer n2,2 must have nonzero edge to every block in the previous layer ns,1 as explained in Figure I The probability that at least one such edge exists for each output neuron is given as (1 - (1 )
0). Yet, we still
Similarly, we can compute the probability that each neuron in the second layer of the source ns,1 has at ) "" X
least one nonzero edge to to each of the univariate blocks in the first layer as (1 - (1 pi) p
Since each layer construction is independent from the other, the above probabilities can be multiplied to obtain the probability that we can represent the entire target network as
II - 1 (1-)) p1) 1) W > 1 - 1=
One way to fulfill the above inequality is to split the error between the two product terms,
(1 (1 91) m
> (1 and (1 - (1 (p2)) ) (1 6)
Both equations above are satisfied with - 1-111 - p2) > 2mer
and 1 (1 pi )0 5
LI
5 m... We can now solve for q; {0, 1}
1 log
2
qu 2
log(1/(1- p1))
and
1
222r2 8
91 Z log(1 (1(1 - p22) log
since q2 = 1
After having identified a representative link in the source ER network for each target weight, we next define the weights and biases for the source ER network leveraging the trainability assumption 2.3 Each representative link in the ER source network is assigned the weight of its corresponding target. For the first layer in the source network, which is an univariate construction of the input, the
weights are defined as W's.jj the ReLU activation function as if it was the identity:
(0)
and the bias is large enough so that all relevant inputs pass through
(0)
1 Vj f1.2....d d} and i E (1,2,.,,
5.43
(0)
01
if
50 0 > 0
for every E {1, 2, nss,0.
0
af
Recall that aj is defined as the lower bound of each input input component æ. We compensate for this additional bias in the last layer. Now for the second layer, every weight w7t in the target network is
18

---

Under review as a conference paper at ICLR 2023
assigned one of the nonzero mask entries in the ER source network that lead to the corresponding input block j and output block i. The remaining extra weights in the source are set to zero.
" 5.yg = WT i' E q1i + 1, Q1 + q1) and j' E {quj. qoí 1,,,, yod + go)
for one pair of ,'. . The remaining connections between i' and block can be pruned away, i.e., masked or set to zero. The bias of the second layer can be chosen so that it compensates for the extra bias added in the univariate construction of the first layer:
(1) (1) Vi' {I,... ns,1) Ug. D WT,6 " S.5"
A.4 WLT EXISTENCE PROOF FOR A TARGET NETWORK OF DEPTH L
In this section, we generalize the idea of constructing source ER network as presented in Section 2.3 to a fully connected target network fr(z) of depth L. Each layer has weight w and bias bT As before, we assume that the target network is equipped with the nonlinear ReLU activation function ((x)) The weight matrix has size w [R Xxny, nr, is the number neurons in each layer and my, R21,1-1 nyy is the number of parameters in the weight matrix. Each layer has a layerwise expected density Pt-
Theorem A.4 (Existence of weak lottery tickets in ER networks ). With Assumption 2.3 given a fully connected target network fr of depth L, 5 E (0, 1), target density p and a L + 1-yyeer ER source network fs E ER(p) with widths nıg,0 = god and ng, qUITT, {1,2, .., L), where
q1 2 log(11(11 (//(1))(+)))
log
for {0, (0. 1] and qr. = 1,
then with probability 1 - 5 the random source network fs contains weak LT fwIr = fs(æ; Ws. S
Proof for Theorem 2.5 We now construct source network fs fx) that contains a random subnetwork which replicates fr (x) with probability 1 8. As explained in Section 2.3 we first construct an univariate layer (with index 1 = 0) in the source network assuming flow preservation.
Next, we calculate the overparametrization factor required for every layer in the source network using the same argument as A.3 starting from the last layer and working our way backwards. The last output layer has the same number of neurons in both the source and the target, n,, = AT,LL Hence, the required width overparametrization factor is qL = 1. In every intermediary layer, create blocks of neurons that consist of q: replicates of the same target neuron. How large should q be? In the second to last layer, the probability that each neuron in the output layer has at least one edge to each of the QL-1 blocks in Layer L is (1 (1 )L 1)--.. We can similarly compute this probability for every layer all the way to the input in the source network which ensures that there is at least one edge between a neuron in every layer and each of the q blocks in the previous layer. The probability that Layer can be constructed thus (1 (1 pt) p1) 2 ) These events
are independent and should hold simultancously with probability 1 6. The following incquality formalizes our argument
L II (1-(1-m) 1=1
p:) m, -1-
21-6
One way to fulfill the above equation would be to ensure that
(1 (1 pr) 0t m1,11 > (1 12-6) 8)2/2
for each layer and thus
(1 (1-(1-p)) p11) (1 5) 1mm
This inequality is fulfilled if
8
1- -1 p1
mT.iqu
19

---

Under review as a conference paper at ICLR 2023
Solving for qi-1 leads to
log
1
Lm 6
gr log(1 1 - pi)
log(1 /(1 pr))
log
We can thus compute the required width overparametrization for every layer starting from the last one, where we know gL = Note, that q depends on the logarithm of gt+1 of the next layer, which ensures that Fi does not blow up as depth increases.
After making sure that the required edges exist in the ER network to represent every target weight, we still have to derive concrete parameter choices. It follows then from the trainability assumption 2.3 that these choices (or equally good ones) could be found proving the existence of WLT in ER networks.
Similar as in the single hidden layer case, each representative link in the ER source network is assigned the weight of its corresponding target and the weights in the first univariate layer are set to 1. The biases in the univariate layer are chosen so that all the inputs pass through the ReLU activation. The biases in the next layer compensate for the additional biases in the first layer.
(0) w S,j = -Vj E (1,2,.,,d) d} and i E {1, 2, ..., ns.o):
a1
if < 0, for every i E (1,2,.... ns.o) if a1 >0 0
5.1
For the subsequent layers in the source network E (1,2,.,, [.} the weights are w 3. T.j" where j' is randomly chosen among all the non-masked connections of i' to block j and j E {q-11, Q-1 + 1,.., -...q11++ + q and i' E {qri qi + I,.., qu + q). The remaining connections between block j and i' can be pruned away or the weight parameters set zero. The biases are set to the corresponding target bias for layers 1 (2..., I.]
w (1)
Vi' E {gri, gri + 1, qri ) b DT.
but the second layer 1 = 1 has an additional term to compensate for the bias in the first (univariate) layer:
(1) Vi' E {ui, qú + 1,.,, qu + a} b b/1 wT.35 DS. "T.
A.5 EXISTENCE FOR CONVOLUTIONAL LAYERS
Theorem A.5 (Existence of WLTs for ER networks with convolutional layers). With Assumption 2.3 given a target network fr of depth L with convolutional layers h = =E W x a1- WT E Raxe-ixki E (0, 1), target density p and T + 1-layer ER source network Is E ER(P) with convolutional layers h = =Σ W!l) S.ij a (1-1) + b Ws E RwaxxLIxXi where
UT.
log LMTT4114+1 for I., 13 and qr. = 1,
@ log(1/(( 1))
then with probability 1 8 the source network fs contains weak LT fw
Proof: The linearity of convolutions allows us to construct a target filter by combining elements that are scattered between different input channels in the ER source network as shown in Figure 3 Using the same argument as the fully connected layer case, we bound the probability that at least one of the qi channels of every filter element in a convolutional weight tensor has a non-masked entry to channel in the next layer. As for fully-connected networks, we can create blocks of channels that correspond to replicates of the same target channel. The first layer can be pruned down to univariate convolutional filters. The probability that each layer can thus be reconstructed in the convolutional network can be bounded as:
(1 (1 --)mmm1) 2 (1 (1- 81-8)
mr,
20

---

Under review as a conference paper at ICLR 2023
Note that for convolutional weights, myy J is the number of nonzero parameters in W Roxx--xxA;, The following width overparametrization of the output channels in convolutional network
log
5 m2
LauT.q
Qt-1
pt) log(1/(1 (1 -p))) log
log(1
allows an ER network to contain a WLT with probability 8.
The weights in the convolutional network can now be chosen using the trainability assumption 2.3 as:
(1) w S k WTisk for every i' {gui qr + 1..., qrè q.).
where E (gt- qt- +1, -t-1--11------ +t+ 1 chosen randomly among all non-masked connections if to block and the remaining connections are pruned away set to zero. The biases are set as in the proof of Theorem 2.3
CT,-1
K
Crr
R2
w
q1
W
(a)
(b)
Figure 3: Construction of a convolutional target in an ER network: For every output channel cr. in the target convolutional weight tensor w create q copies in the source weight tensor W! (() as shown on the left (a). The width overparametrization is further elucidated in (b) where each filter element of target output filter has qi independent copies in the source, least one of which is nonzero (unmasked), Coloured squares in (b) show the nonzero parameters in the source ER network.
A.6 LOWER BOUND ON THE OVERPARAMETRIZZTIOO OF ER NETWORKS
Our theoretical analysis suggests that ER networks require a width overparumetrization by a factor of (1sparsi)t)) to exist as a LTT We also show that we cannot do substantially better than a width that is proportional to log(1 /sparsity).
Theorem A.6 (Lower bound on overparametrization in ER networks). There exist univariate target networks fr(x) o(wffx + br) that cannot be represented by a random 1-hidden- layer ER source network fs E ER(p) with probability at least - 5, if its width is nss <
(01(1/(17))) log
1-(1-8)173
The main idea is to find the minimum width of a single hidden layer network ER(p) which can approximate single output target (x) 0(wffa br). This minimum would be achieved when every target weight in wr is approximated by exactly one path in the ER network from the input to the output (through the hidden layer). We derive the probability that for every weight the target, there is at least one non-masked path in the ER source that can represent this weight as shown in Figure 4 Bounding this probability will give us a lower bound on the minimum width required in the ER network to be able to represent the target network. There ng,1 paths from input neuron to an output neuron the source network and the probability that each of this path exists is p², independently for each path, since both the input and output links in the path must be nonzero
Proof:
21

---

Under review as a conference paper at ICLR 2023
Target Network
Source Network
WT,11
31
WT,11
WT,21
32
U1
1
(1)
WT,31
WT, 31
T&S,1
Figure Lower bound of width of an ER source network shown on the right required to approximate the target network on the left using the trainability assumption 2.3 The solid edges in the source the right are the nonzero (unmasked) edges while the dotted lines are masked away in an ER source network.
and each edge exists independently. Starting from the first input neuron, the probability that there at least one path from input r; to the output is (1 (1- p² p².)s..). The paths exist independelty from each other if they start in different input neurons. Thus, the probability that we can represent an arbitrary target neuron with d input neurons is (1 - (1 pd) m?) In order to find the minimum width required, we lower bound this probability as:
(1- (1 11-pp"y nsa) 8-8
Solving this inequality for nssi proves the statement, since we would need
n1,11
log(1/(1 (111211) log (1- (1- 88)/14))) log(1/(1 - -p) log
(1 - 111-11= 88)118)
A.7 EXPERIMENTAL SETUP
Our code base is built code made available by the authors of Liu et al. (2021) and Tanaka al. (2020).
To train ER networks weak lottery tickets for the different layerwise sparsity ratios, learning rate of 0.1 scheduled by factor of 1/10 at 80 and 120 epochs. We train with batch size of 128 for 160 epochs using SGD with momentum 0.9 and weight decay 0.0005. The same hyperparameter setup is used for both ResNer18 and VGG16.
For experiments on strong lottery tickets using edge popup, we use an iterative version of edge popup as described in (Fischer & Burkholz 2022). We initialize sparse network and anneal the sparsity iteratively while keeping the mask fixed. For the ResNet18 88 we use learning rate in levels and 100 epochs for each level. The batch size is 128 and we use SGD with momentum 0.9 and weight decay 0.0005. We report performances after one run for each of these experiments due to limited computation.
and anneal
In the DST experiments, we use the same setup as for the ER networks stated above, and modify the mask every 100 iterations. For sparse sparse training with DST, weight magnitude as importance score for pruning (with prune rate 0.5) and gradient for growth.
For the weak lottery ticket pruning baselines of Iterative Synflow and IMP, we prune the network in 25 levels with 30 epoch warm up and train the final pruned network for 160 epochs with a learning rate 0.001. The batch size is 256 and the learning rate is scheduled by 0.1 the epochs 80 and 120
22

---

Under review as a conference paper at ICLR 2023
with the Adam<Kingma & Ba 2015) optimizer. We the code base of the authors of Synflow
Tanaaa et al. 2020) for these experiments.
A.8
ADDITIONAL. EXPRIMENTS ON CIFAR 10/100
Along with VGG we report results for different layerwise sparsity ratios for ResNets. We use ResNet 18 for CIFARIO and a ResNet 50 for CIFARI00.
Sparsity
Pyramidal
Balanced
Uniform
ERK
0.9
94.17 0.1
93.97 + 0.13
92.85 + 0.2
93.96 + 0.19
0.99
90.83 + 0.3
90.72 + 0.3
84.7 = 0.2
89.04 + 0.21
0.995
88.57 + 0.12
88.32 + 0.3
77.2 =
85.8 = 0.16
0.999
10 = 0
70.69 = 0.6
35.31 #
61.36 = 0.24
Sparsity
Snip (ER)
Synflow (ER)
IMP (ER)
0.9
94.25 + 0.3
93.95 + 0.13
93.36 + 0.2
0.99
90.33 0.04
91.34 0.27
86.43 0.4
0.995
87.72 + 0.14
88.64 + 0.14
81.2 0.16
0.999
10 0
71.92 0.28
50.46 1.4
Table 7: ER networks with different layerwise sparsities on CIFARIO with ResNer18.
Sparsity
Pyramidal
Balanced
Uniform
ERK
Snip (ER)
0.5
78.09 0.64
76.98 + 0.55
78.12 + 0.33
77.63 + 0.52
78.02 + 0.43
0.8
78.44 0.41
76.59 + 0.33
77.77 = 0.43
77.08 + 0.44
76.21 + 0.77
0.9
76.66 0.01
75.37 0.77
75.94 = 0.27
76.02 0.62
76.35 0.32
0.99
65.44 + 1.2
67.97 + 0.23
55.52 + 2.5
65.52 + 0.3
1 0
Table 8: networks with different layerwise sparsities on CIFARI00 with ResNe150.
Sparsity
Pyramidal
Balanced
Uniform
ERK
0.9
92.92 + 0.31
93.22 + 0.28
91.31 + 0.3
92.72 + 0.46
0.99
90.41 + 0.03
89.31 + 0.1
82.68 0.21
87.81 1 0.38
0.995
87.76 + 0.13
85.92 + 0.4
73.69
= 0.64
84.53 + 0.2
0.999
10 +
68.68
14.24
59.22 2.6
Sparsity
Snip (ER)
Synflow (ER)
IMP (ER)
0.9
93.23 + 0.2
91.4#0.11 0.11
90.05 + 0.3
0.99
26.32 28
86.55 + 0.26
90.15 + 0.05
0.995
10 + 0
84.03 0.06
79.02 8
0.999
10 + 0
63.81
10 + 0
Table ER networks with different layerwise sparsities on CIFARIO with VGGI6. We compare our layerwise sparsity ratios balanced and pyramidal with the uniform bascline, ERK and ER networks with layerwise sparsitiy ratios obtained by IMP, Iterative Synflow and Snip.
A.9 ADDITIONAL EXPERIMENTS FOR STRONG LOTTERY TICKETS ER NETWORKS
To show experimentally that ER networks contain SLTs, (202)) to search for SLTs in ER ResNet18. We gradually anneal the sparsity of the ER network with 5 levels proposed by (Fischer & Burkholz 2022). The results are presented in Table [] As reference, we also report baseline results for dense networks in Table 12
edge popup Ramanujan al.
Additional experiments for ER VGG16 CIFAR10 are shown in Table 13
23

---

Under review as a conference paper at ICLR 2023
Sparsity
Pyramidal
Balanced
Uniform
ERK
0.5
73.63 = 0.1
73.92 + 0.23
72.77 0.01
73.58 + 0.18
0.8
73.65 0.43
73.51 + 0.25
71.39 = 0.07
72.82 0.36
0.9
72.73 + 0.5
72.49 + 0.43
69.06 = 0.35
71.9 0.06
0.99
60.05 = 3.2
65.33 + 0.35
55.79 = 0.22
63.83 = 0.41
Sparsity
Snip (ER)
Synflow (ER)
IMP (ER)
0.5
73.75 + 0.57
72.6 = 0.6
71.03 + 0.4
0.8
74.01 + 0.02
71.56 0.33
68.09 + 0.14
0.9
73.05 + 0.24
70.8 = 0.31
62.97 0.7
0.99
1
62.62 + 0.12
1
Table 10: ER networks with different layerwise sparsities on CIFARIOO with VGGI9. We compare layerwise sparsity ratios balanced and pyramidal with the uniform baseline, ERK and ER networks with layerwise sparsitiy ratios obtained by IMP, Iterative Synflow and Snip.
Sparsity
0.5 - 0.8
0.5 -> 0.9
0.7 + 0.9
Test Acc.
87.83 + 0.25
88.12 + 0.29
87.95 + 0.25
Sparsity
0.5 0.95
0.8 0.95
0.5 0.99
Test Acc.
87.78 + 0.33
88.07 + 0.06
87.94 0.14
Table 11:
ER networks for Strong Lottery Tickets: Average results training ER ResNet18 network with edge popup [Ramanujan et al. (020) on CIFARIO. The ER network is initialized with uniform initial sparsity, which is gradually annealed to attain SLT of the final sparsity (initial final sparsity). Baseline results for initially dense networks are reported Table 12
Final Sparsity
- 0.8
0 > 0.9
- 0.95
0 - 0.99
Test Acc.
87.79 + 0.1 87.86 + 0.2
88 = 0.3
87.7 + 0.56
Table 12:
Baseline for edge popup with ResNer18 on CIFARIO: The results for finding a SLT using edge popup starting from dense network are shown. Our ER results starting from sparse network are comparable to these baseline results which validates the efficiency ER networks.
Sparsity
0.5 > 0.8
0.5 + 0.9
0.5 + 0.95
0.5 > 0.99
Test Acc.
88.03 + 0.26
88.31 + 0.29
88.06 + 0.35
88.12 + 0.2
Table networks for Strong Lottery Tickets: SLTs in VGG16 ER networks on CIFAR10. The ER network is initialized with a uniform initial sparsity and gradually annealed to attain SLT of the final sparsity (initial - final sparsity).
Final Sparsity
- 0.8
- 0.9
- 0.95
- 0.99
Test Acc.
88.2 + 0.15 88.38 + 0.14
88.16 + 0.21
88. 14 + 0.35
Table 14: Baseline for edge popup with VGG16 on CIFARIO: Baseline results of Edge Popup to obtain SLTs CIFARIO with VGG16.
A.9.1 SLTS ER NETWORKS FOR RESNETI 10 CIFARIO0
We find SLTs within ER networks using the Edge Popup algorithm for larger Resnetl 10 model as reported in Table 15
24

---

Under review as a conference paper at ICLR 2023
Sparsity
ER Method
- 0.9
0.5 - 0.9
0.7 0.9
Test Acc.
61.91 + 0.13
61.76 0.53
61.78 0.61
Table 15: Edge popup (SLTs) results on ER networks with Resnetl on CIFARI00. Results are reported for one run due to limited compute.
A.10 COMPARING ER NETWORKS WITH ITERATIVE SYNELOW AND IMP
We have also performed experiments that compare ER networks with state of the pruning algorithms, Iterative Synflow (Tanaka et al.) 2020) and Iterative Magnitude Pruning (Frankle & Carbin 2019). We use the iterative version Synflow (Fischer & Burkholz 2022) and the results are presented in Fig. 5 ER networks with layerwise sparsity ratios, which are chosen independently of the data with negligible computational overhead, are able challenge and even outperform state- of-the-art pruning algorithms, which require computationally highly demanding pruning-tree pruning-training iterations. This highlights the general effectiveness random masks at moderate sparsity levels. While random masks outperform IMP consistently in our experiments, for extreme sparsities of 0.999, Iterative Synflow still performs best among all considered algorithms. Starting Synflow from a random mask instead of a complete network, however, could potentially save computational resources to achieve similar results. We leave this analysis for future work.
80
81
Test Accuracy
Test Accuracy
60-
20
21-
0.99 Sparsity
0.985
0.999
0.99
0.985
0.999
Sparsity
(a) VGG16
(b) ResNer18
Synflow Ref
IMP Ref
balanced (ours)
pyramidal (ours)
Figure 5: Comparing ER networks with Iterative Synflow and IMP: For both VGG16 and ResNet18 models the average and confidence interval over three runs is shown. The legend defines the layerwise sparsity ratio used for masking in the ER network.
A.11 EXPERIMENTS ON CIFAR1O0 WITH DESNET110
To showcase the scaleability of the suggested algorithms, we additionally report experiments for larger model, i.e., Resnetl 10.
A.11.1 FOR WLTs IN ER NETWORKS
We report results for different layerwise sparsities Table 16
As a reference we also report results
on pruning with baseline algorithm Iterative Magnitude Pruning Table 17 We also conducted experiments with an Iterative Synflow algorithm Tanaka et al. (2020) to prune a Resnet 10 but the algorithm fails for such large model.
25

---

Under review as a conference paper at ICLR 2023
Sparsity
ER Method
0.5
0.8
0.9
0.95
Balanced (ours)
70.37 + 0.59
67.88 + 1.01
67.31
0.33
63.80 + 0.09
Pyramidal (ours)
71.16 + 0.22
69.56 0.31
63.23 + 1.29
52.37 0.51
ERK
70.76 + 0.82
69.96 0.58
68.14 0.34
64.92 0.31
Uniform
70.86 + 0.70
69.41 + 0.27
66.32 + 0.42
61.31 + 0.02
ER Snip
69.1 19.14 + 0.46
69.12 + 0.65
65.82 + 0.28
60.15 + 0.34
Table Resulty for WLTs ER networks on CIFARIOO with ResNetl 10. Results are average and standard deviation reported across three runs.
Sparsity
Iterative Magnitude Pruning
0.5
0.9
Test Acc.
65.46
64.77
Table 17:
Results on CIFAR 100 with Resnet 10 pruning with the iterative magnitude pruning (IMP)
algorithm for reference. Only run of IMP was performed for each of these sparsities.
A.12 EXPERIMENTS WITH TINY IMAGENET FOR WLTs
We also report experiments with different layerwise sparsity methods in ER networks for the Tiny Imagenet dataset. We use VGG19 and ResNet20 and show that proposed layerwise sparsity methods for ER networks are competetive for this dataset. Note that we use the validation set provided by the creators of Tiny Imagenet (Russakovsky al. (015)) test set measure the generalization performance of our trained models.
See Table 18 and 19
Sparsity
ER Method
0.5
0.8
0.9
0.99
Balanced (ours)
58.40 + 0.39
57.95 + 0.42
57.47 + 0.64
50.72 + 0.15
Pyramidal (ours)
58.92 0.12
0.15
58.08 0.05
41.06 + 0.28
ERK
58.66 + 0.63
58.39
57.24 0.12
50.52 0.50
Uniform
58.67 + 0.27
0.36
44.96
44.78 1.14
ER Snip
58.66 + 0.29
58.65 + 0.29
17.75
0.5
Table 18: Results for ER networks on Tiny Imagenet with VGG19
Sparsity 0.8
ER Method
0.5
0.9
0.99
Balanced (ours)
46.92 + 0.38
39.25 + 0.57
31.62 + 0.49
9.34 0.46
Pyramidal (ours)
48.24 + 0.01
39.31 + 0.17
25.15 0.08
1.66 = 0.13
ERK
50.36 + 0.47
44.73 + 0.64
0.64
36.81 - 0.32
10.52 + 0.05
Uniform
48.49 = 0.47
41.84 0.38
32.87 0.15
8.70 = 1.14
ER Snip
50.28 + 0.50
44.65 - 0.47
36.92 + 0.20
7.36 = 1.81
Table 19: Results for ER networks on Tiny Imagenet with ResNet20
A.13 DYNAMICAL SPARSE TRAINING ON ER NETWORKS
In addition to the rewiring experiments shown Table we use Dynamical Sparse Training to prune an already sparse ER network to higher sparsity and see if this can achieve the same performance as performing DST starting from a denser network. Similar experiments have been shown by (Liu
et al. 2021. However, report results on ER networks starting much higher sparsities. Our
26

---

Under review as a conference paper at ICLR 2023
Sparsity 0.99
Sparsity 0.995
ER Method
Original
Rewired
Original
Rewired
ERK
87.81 + 0.39
90.78 0.14
84.53 + 0.20
88.28 0.52
Balanced
89.31 + 0.11
91.41 + 0.43
85.91 = 0.40
89.30 + 0.03
Pyramidal
90.41 + 0.03
91.97 0.08
87.76 = 0.13
90.61 + 0.15
Sparsity 0.999
ER Method
Original
Rewired
ERK
59.22 2.57
74.12 + 1.16
Balanced
68.68 0.44
78.90 0.64
Pyramidal
10 +
9.83 + 0.28
Table 20: ER networks rewired with DST: An ER(p) VGG16 network with sparsity p initialized and the mask is modified by rewiring edges with RiGL on CIFARIO.
results shown in Table 21 are able to match the performance of (Liu et al. 2021. while being more
efficient as start a higher sparsity.
Sparsity
ER Method
0.5 + 0.99
0.9 0.99
0.95 > 0.99
Balanced (ours)
93.08 0.01
92.75 = 0.25
92.70 0.10
Pyramidal (ours)
93.13 + 0.05
92.93 + 0.08
92.58 + 0.21
ERK
92.94 0.12
92.77 = 0.01
92.47 = 0.11
Table 21: Sparse to sparse training with DST Final test accuracy for VGG16 on CIFAR1O is reported where the model is initialized with an ER network of some initial sparsity and further pruned to final sparsity (initial >> final) while modifying the mask using the RiGL. (Evei al. 2020a) algorithm.
Notably, observe that it is also possible to start at sparsity of up 0.95 and still achieve competitive test accuracy, only marginally worse than starting with a sparsity of 0.5.
A. 14 VISUALIZING LAYERWISE SPARSITIES FOR ER NETWORKS
We report layerwise sparsity ratios for the proposed methods discussed in Section in comparison to ERK, for VGG19 with CIFAR100.
27

---

Under review as a conference paper at ICLR 2023
100
Density
10-1
5
10
15
Layer Index
uniform
balanced
BRK
pyramidal
Figure 6: Layerwise sparsity ratios for VGG19 trained on CIFARI00 for results reported in Table for target sparsity 0.9 i.e. 10% of the parameters retained.
28


Reviews:
[{"review_id": "pjcOQGfbQKw", "reviewer": "Reviewer_fij2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "The paper studies if LT exists in ER-like connected neural networks. Theoretical and empirical results are provided.", "summary_of_the_review": "see my comments above.", "strength_and_weaknesses": "+: \nThe problem looks interesting for purely theoretical purposes. \nThe theoretical results look solid though I couldn't check the proof. \n\n-: \nThe practical motivation is unclear. Why would one stick with a fixed source sparse network that is randomly drawn? One can probably do much better by not having to stick with a fixed sparsity pattern. \n\nThe weak LT statement is proved with a very strong trainability assumption. Such an assumption would also imply the existence of weak LTs in the dense case too, I guess. \n\nThe theoretical contribution is not clear. Does the ER-version of subset sum result (Lemma 2.1) directly imply Theorem 2.2 using the same proof flow of Pensia et al., 2020? \n\nMoreover, I am not sure if the ER-version of subset sum result interesting/non-trivial. Maybe I am misunderstood. Since $\\frac{1}{\\log{1/(1-p)}} \\approx 1/p$ when $p$ is small, isn't it kinda obvious that you need $1/p$ expansion factor to solve the subset sum problem? \n\nOr more seriously, why do we even need a separate proof for Lemma 2.1? With probability $1-\\delta_1$, we can show that there will be $np(1-\\epsilon_1)$ non-zero terms.  Since $M$ and $X$'s are independent, within those non-zero terms, you can solve the $\\epsilon_2$-subset sum problem with probability $1-\\delta_2$. By combining these two, we can easily get Lemma 2.1. Please correct me if I am wrong.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "YYv3gPLlR5", "reviewer": "Reviewer_x4uC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper provides a theoretical analysis that ER masks can approximate arbitrary target networks if they are wider by a factor of 1/log(1/s), where s denotes the sparsity ratio. The paper prove that ER randomly initialized network contains strong lottery tickets, and also prove the existing of weak lottery tickets that require a lower degree of overparameterization than strong lottery tickets. Additionally, a lower bound on overparameterization in ER networks that illustrates the limits of ER masks. The authors verify their theory on multiple DL applications like VGG on CIFAR10.", "summary_of_the_review": "Overall I think this is a good paper, because it provides detailed theoretical justification to ER networks. I'd appreciate if the authors could provide follow-up explanations of how the provided theory relates to (Evci et al., 2020a).", "strength_and_weaknesses": "**Strength**\n* This paper gives solid theoretical justification on ER random network, the theory partially substantiates why some recent works on sparse networks that use ER initialization is better in practice, like (Evci et al., 2020a). I did not read all the proof, but the main claim in the paper looks correct to me.\n* While I personally am not familiar with the literature in this line of work, the theory looks interesting and novel to me.\n\n**Weakness**\n* It's likely that I missed something in the literature, but it is unclear to me what the definitions for SLT and WLT are. I'd encourage the authors to clearly identify this in the revision.\n* While I appreciate the authors for giving theoretical justification to ER networks, it's still unclear to me how the theory connects to the current success. Take (Evci et al., 2020a), the main success in RigL paper is that the rewiring of weight parameters is signaled by gradients instead of random variables. The authors mentioned in their contributions that theoretical support is provided on targeted rewiring, but I'm not sure how the theory given in Theorem 2.7 is related to (Evci et al., 2020a).\n* The majority of the experiments are done to verify the ER trainable assumption in real-world training applications. On the other hand, I think it'd be interesting to also give evidence on how ER network contains SLT/WLT on toy examples.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VO3Qe6bOc7", "reviewer": "Reviewer_jYYZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proves that the Strong Lottery Ticket Hypothesis holds for FC Neural Networks and CNNs which are initialized as Erdos-Renyi (ER) graphs. It extends on the proofs by *Pensia et al.* and *Burkholz et al.* to show that logarithmic overparameterization (and an additional $\\log$ factor that depends on the sparsity of the ER initialization) is sufficient to approximate any target network by pruning.\n- They also claim to prove a result for the weak LTH but the assumption makes it fairly vaccuous.\n- They run some experiments in the vein of Pensia et al. on CIFAR-10, CIFAR-100 and TinyImagenet. They also show that rewiring edges of a pruned network can improve the performance of the final mask significantly.", "summary_of_the_review": "I do not think the paper in its current state should be accepted as several claims made are exaggerated and imprecise. However, if the literature survey is updated, claims modified and limitations more clearly described, I think it would be a reasonable contribution. I would be happy to change my mind if my concerns are addressed.", "strength_and_weaknesses": "**Strengths:**\n- The premise is very interesting as they claim to prove a result about the remarkable performance of random pruning.\n- As far as I am aware, a theoretical justification of the weak LTH does not exist in the literature. The authors prove a result showing this, although the assumption makes it quite unsatisfactory.\n- The paper is well written and fairly easy to understand.\n\n**Weaknesses:**\n1. The paper makes it seem like they are proving a result explaining the remarkable performance of random pruning, but in reality they do not. The theorem only shows that you can further prune a random subnetwork, given sufficient overparameterization. While this is true, I don't find this particulary interesting or surprising.\n    -  In the abstract as well as Section 1, they state \"We offer a theoretical explanation of how such ER masks can approximate arbitrary target networks if...\" - this is simply untrue. They show that within an ER mask, there exists some sort of *sub-mask* which allows you to approximate abirtrary target networks.\n    -  The results of Su et al., Liu et al. and Frankle et al. show that random pruning **alone** is sufficient to reach competitive results. They do not further prune the random masks. Therefore, this theory does not imply those results whatsover.\n    -  The phrasing of the results is accurate in the contributions section where they state that ER networks contain LTs with high probability. I agree with this statement although I am not sure if it is particulary interesting or surprising.\n    -  The additional $\\log(1/(1-p))$ factor is fairly obvious if you are familiar with the strong LTH literature. It is merely allowing for larger overparameterization to account for the missing edges from the ER mask initialization.\n\n3. The assumption in the result about the weak LTH is far too strong. It almost assumes the theorem that they are trying to prove. I think this makes the result fairly vaccuous.\n    - **Assumption 2.3** assumes that an ER network with layerwise density $p$ is trainable by SGD with standard weight initialization. This is essentially the weak LTH for random pruning. This is the result I would have liked to see proved. But it is just merely assumed. Proving the weak LTH from this seems extremely trivial.\n    - They justify this assumption since it is observed in practice from works like Su et al., Ma et al. etc. However, they use it to prove a statement that supposedly explains the results from this very work. This circular reasoning seems incorrect and is akin to assuming the statement they are trying to prove.\n\n\n5. I understand that the LTH literature has grown quite fast, but Section 1 is missing quite a few citations and is unfair to a few references as well.\n    - The literature survey on LTH and pruning algorithms is missing Renda et al., (Comparing Rewinding and fine-tuning in Neural Network Pruning), Gale et al. (The State of Sparsity in Deep Neural Networks), Savarese et al. (Winning the Lottery with Continuous Sparsification).\n    - The section on Strong LTH is again missing a few papers: Diffenderfer et al. (Multi-Prize Lottery Ticket Hypothesis), Sreenivasan et al. (Finding Nearly Everything within Random Binary Networks).\n    - In Section 1, Tanaka et al. is listed under algorithms that have expensive pruning-retraining iterations but if I'm not mistaken, SynFlow uses a constant number of iterations to identify the mask at initialization. Therefore, it is nearly a single-shot pruning method.\n\n6. There are some minor issues with claims made and terminology used in the paper.\n    - It is mentioned repeatedly that strong LTs are also weak LTs. This is a somewhat imprecise statement. If you assume that weak LTs need to be trainable to high accuracy, then several strong LTs do not satisfy this requirement. Strong LTs can approximate any target network, but they do not provide any guarantees on similar trainability as the target networks. I think the literature has moved quickly and the strong LT term has caught on, but I think it should be used more carefully.\n    - In Section 1.1, it is stated that the best performing WLTs are still obtained by expensive iterative pruning methods like IMP. This is not necessarily true. (See Sreenivasan et al. Rare Gems: Finding Lottery Tickets at Initialization)\n    - In Section 1.1 they state that \"we show that ER masks are competitive for various choices of layerwise sparsity ratios\": But the results involve finding masks within ER masks. The final pruned subnetwork is not an ER graph.\n    - They repeatedly claim that the theorems identify a lower bound on the width of the ER source network for which they can show existence. While this is true, it is really an upper bound on the width of the source network to guarantee existence since we have not yet proved a matching lower bound. Theorem 2.7 is indeed a lower bound.\n\n7. Appendix A.1 Flow Preservation:\n    - How often does flow preservation need to be done? Is this at every gradient step? This could get quite expensive since it needs to check every weight in the network.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject