Plant 'n' Seek: Can You Find the Winning Ticket?
Authors: Jonas Fischer
Rebekka Burkholz
Venue: ICLR 2022 Poster (2022)
Keywords: lottery tickets
ground truth
planting
LTH

Abstract: The lottery ticket hypothesis has sparked the rapid development of pruning algorithms that aim to reduce the computational costs associated with deep learning during training and model deployment. Currently, such algorithms are primarily evaluated on imaging data, for which we lack ground truth information and thus the understanding of how sparse lottery tickets could be. To fill this gap, we develop a framework that allows us to plant and hide winning tickets with desirable properties in randomly initialized neural networks. To analyze the ability of state-of-the-art pruning to identify tickets of extreme sparsity, we design and hide such tickets solving four challenging tasks. In extensive experiments, we observe similar trends as in imaging studies, indicating that our framework can provide transferable insights into realistic problems. Additionally, we can now see beyond such relative trends and highlight limitations of current pruning methods. Based on our results, we conclude that the current limitations in ticket sparsity are likely of algorithmic rather than fundamental nature. We anticipate that comparisons to planted tickets will facilitate future developments of efficient pruning algorithms.

Published as a conference paper at ICLR 2022
PLANT 'N' SEEK: CAN YOU FIND THE WINNING TICKET?
Jonas Fischer
Rebekka Burkholz
Max Planck Institute for Informatics fi fische scherrmpi -inf mpg. de
CISPA Helmholtz Center for Information Security burkhol 1 z @ spa. de
ABSTRACT
The lottery ticket hypothesis has sparked the rapid development of pruning al- gorithms that perform structure learning by identifying a sparse subnetwork of a large randomly initialized neural network. The existence of such 'winning tick- ets' has been proven theoretically but at suboptimal sparsity levels. Contemporary pruning algorithms have furthermore been struggling to identify sparse lottery tickets for complex learning tasks. Is this suboptimal sparsity merely an artifact of existence proofs and algorithms or a general limitation the pruning approach? And, if very sparse tickets exist, current algorithms able find them are fur- ther improvements needed to achieve effective network compression? To answer these questions systematically, we derive framework to plant and hide target ar- chitectures within large randomly initialized neural networks. For three common challenges in machine learning. we hand-craft extremely sparse network topolo- gies, plant them in large neural networks, and evaluate state-of-the-ie of-the-art lottery ticket pruning methods. We find that current limitations of pruning algorithms identify extremely sparse tickets are likely of algorithmic rather than fundamental nature and anticipate that our planting framework will facilitate future develop- ments of efficient pruning algorithms, baselines in the field raised by Frannle et al. (2021). I. Our code is publicly available at www. gi github. com/ Relattaaa ona 1ML PSek
we have addressed the issue of missing
INTRODUCTION
Deep learning has achieved breakthroughs in multiple challenging areas pertaining to machine learn- ing, in particular areas for which we lack competitive hand-crafted algorithms. The benefits of overparameterization for training with SGD (Belkin et al. 2019) seem to call for ever wider and deeper neural network (NN) architectures, which are computationally demanding to learn and de- ploy. Training smaller, adequately regularized NNs from seratch could be remedy but it commonly seems to fail due to inadequate parameter initialization, as Frankle & Carbin (2019) noted in their seminal paper. As proof of concept that this problem is solvable, they proposed the lottery ticket (LT) hypothesis, which states that small, well trainable subnetwork can be identified by pruning large, randomly initialized NN, opening the field to discover such subnetworks or 'winning tickets'.
Based on the findings of Zhou et al. (2019). Ramanujan et al. 2020) went even further and conjec- tured the existence of strong lottery tickets, i.e., subnetworks of randomly initialized NNs that do not require any further training. This strong LT hypothesis holds the promise that training NNs could potentially be replaced by efficient NN pruning, which simultaneously performs structure learning by identifying task specific sparse neural network architecture. The existence of strong LT' has also been proven formally for networks without (Malach et al.] 2020 Pensia et al.) 2020 Orseau et al. 2020) and with potentially nonzero biases (Fischer al. 202 Burkholz et al.
2022
While these types of proofs show existence in realistic settings, the sparsity of the constructed tick- ets is likely not optimal, as they represent a target parameter by multiple neurons of degree 1. The construction and proof of the generalized strong LT hypothesis raises two question- is the subopti- mal sparsity merely artifact of existence proofs general limitation of the pruning approach? And, very sparse tickets exist, are current algorithms able to find them or are further improvements needed achieve effective network compression? These questions cannot be answered by compar-

---

Published as a conference paper at ICLR 2022
ing LT pruning algorithms solely on standard benchmark datasets (Frankle et al. (021), but demand the comparison with known ground truth LTs. To fill this gap and generate baselines with known ground truth, we here propose an algorithm to plant and hide arbitrary winning tickets in randomly initialized NNs and construct sparse tickets that reflect common challenges in machine learning. We use this experimental set-up to compare state-of-the-art pruning algorithms designed to search for lottery tickets.
Our results indicate that state-of-the-art methods achieve only sub-optimal sparsity levels. This sug- gests that previous challenges to identify highly sparse winning tickets as subnetworks of randomly initialized dense networks (Frankle et al., 2020 Ramanujan al., 2020) can be explained by al- gorithmic limitations rather than fundamental problems with LT existence. In our experiments, the qualitative trends how methods compare to each other are consistent with previous results on image classification tasks (Tanaka et al., 2020 Frankle et al. (221) indicating that our experimental set-up exposes pruning algorithms to realistic challenges.
addition, we identify an opportunity to im- prove state-of-the-ar pruning algorithms in order to find strong LTs of better sparsity. Our proposed planting framework will enable the evaluation of future progress in this direction.
Contributions 1) We prove the existence of strong lottery tickets with sparse representations. 2) Inspired by the proof, we derive a framework that allows us to plant and hide strong tickets in neural networks and thus create benchmark data with known ground truth. 3) We construct sparse represen- tations of four types of tickets that reflect typical machine learning problems. 4) We systematically evaluate ofate-of-the-art pruning methods that aim to discover tickets on these three problems against the ground truth tickets and highlight key challenges.
1.1 RELATED WORK
LT pruning approaches for neural networks can be broadly categorized into three groups, pruning
before, during, or after training.
While methods that sparsify the network during (LeCun et al.
1990 Mozer & Smolensky 1989
Han et al.] 20155] Frankle & Carbin
2019;
Srinivas & Babu 2016
Lee et 20220) or after training
(Savarese et al. LeCun et al. 1990; Hassibi & Stork 1992,
Dong al. [217 Li et al. 2017 Molchanov al.
2017) help in reducing computational resources
required for inference, they are, however, less helpful in reducing resources at training time but
can make difference if they prune early aggressively YYou et al. 2020). They are most useful for
structure learning at lower sparsity levels (Su et al.) 2020: Lee et al. [0020].
The LT hypothesis (Frankle & Carbin| 2019) has also promoted the development of neural network pruning algorithms that prune before training (Wang et al., 2020 Lee et al., [219 Verdenius et al.) 2020 Tanaka et al.) 20200 RRaaaujjn et al.) 2020). Usually, these methods try to find LT's a "weak" (but powerful) sense, that is to identify a sparse neural network architecture that is well trainable starting from its initial parameters. These methods score edges in terms of network flow, which can be quantified by gradients at different stages of pruning, prune all edges with the lowest scores until the desired sparsity is achieved (Frankle et al., 202T). Strong LTs sparse sub-networks that perform well with the initial parameters, hence do not need to be trained any further (Zhou et al.] 2019 Ramanujan et al., 2020). Their existence has been proven by providing lower bounds the width of the large, randomly initialized neural network that contains them (Malach et al.) 2020 Pensia et al.) 2020) Orseau et af.) [2220] Fischer et al.) [02T]] Burkholz al. 2022). In addition, was shown that multiple candidate tickets exist that are also robust to parameter quantization (Diffenderfer & Kailkhura| 2021).
based on edge weights, and
Beyond LT pruning, many more methods have been developed to reduce computational resources and perform structure learning, including dynamic sparse training (Evci et al. 2020 Liu et al. 2021b), adaptations (Frankle et al.) 22200] Renda al., 2020 Liu et al. (021a) of Iterative Magni- tude Pruning (IMP) /Han et al. (2015); Frankle & Carbin (201) and sparse regularization techniques (Weigend et al. 1991 (Savarese et al. (020). As these approaches do not identify LT's as subnet- works of randomly initialized NNs, they do not rely on the existence of planted tickets and are therefore beyond the scope of our experimental analysis. However, the ground truth tickets which we derived for planting could still provide an interesting baseline to explore whether sparse training of deep NNs can identify extremely sparse, hand designed NN architectures. Dense NNs are known to find NN representations that are less sparse than hand crafted architectures (Denker et al. 1987), yet, the explicit objective of sparse training is to address this issue. We provide the tools to evaluate progress in this direction by planting known ticket architectures. While the ultimate goal of deep
2

---

Published as a conference paper at ICLR 2022
learning is to solve problems with otherwise unknown solutions like image classification (Frankle
ct al. 2021) or protein structure prediction (Tunyasuvunakool et al. 2021). the design of NN ar- chitectures for human solvable problems has already in the past provided important insights into
NN properties, including universal approximation (Scarselli & Tsoi, 1998; Yarotsky (018)) or the
importance of algorithmic alignment (Xu et al., [2020). NNs that compute polynomials (Scarselli &
Tsoi. 1998, Yarotsky] 2018)) xor gates (Rumelhart et al. 1986), discrete fast fourier transformation
[Velik] 2008), symmetry groups (Sejnowski et al.] 1986). general piecewise linear functions (Arora
et al. 2018), or argmax (Xu et al., 2020) could also present interesting candidates for planting in future investigations.
1.2 NOTATION AND TERMINOLOGY
Let f(x) denote a bounded function, without loss of generality ʃ [-1 - 1-1,1]% that is parameterized as a deep neural network with architecture ñ [no. Ri, ".,,,,,,,,............ ng]. i.c., depth L and widths n, for layers
0, ..., with ReLU activation function o(x) == max(æ, 0). maps an input vector (0)) to neurons x x(1) = à (w() + b()), where W E RT xmi is the weight matrix, and b(9) R' is the bias vector of Layer We will establish approximation results with respect to the supremum norm I|gll.o == su, l|9l12 defined for any function g on the domain [-1, 1] Assume furthermore that LT fo can be obtained by pruning large mother network f. which we indicate by writing f. C fo- If f. achieves a similar performance after training the non-zero parameters as training all parameters of fo. call fc weak LT. f. does not require any further training, we call it a strong LT. Note that every strong LT is automatically also a weak LT and any algorithm that prunes the initial network fo identifies a LT that could, in principle, be strong LT. The sparsity level p of fc is then defined as the fraction of non-zero weights that remain after pruning, i.e., p = E W! 11) (E,
[ w ll.) where I1-1lo denotes the lg lo-norm, which counts the number of non-zero elements vector or matrix. Another important quantity that influences the existence probability of lottery tickets is the in-degree of node in layer I of the target ʃ, which we define as the number of non-zero connections of neuron to the previous layer
plus if the bias is non-zero, i.e., k(() w (1)
1.: D
where W!l) s, is the i-th row of W
The maximum degree of all neurons in layer l is denoted as ka,
2 EXISTENCE OF STRONG LOTTERY TICKETS
Pruning algorithms that search for strong LTs achieve sparsity levels of around 0.5 but not sub- stantially smaller the resulting models should be able to compete with the accuracy of the entire, trained mother network (Ramanujan et al. 2020). Proofs of the existence of strong lottery tickets give no clear indication whether this is an algorithmic shortcoming, which could be overcome, or a fundamental limitation of pruning randomly initialized networks alone. The reason is that existing proofs (Malach et al. 2020; |Pnsia et al., 2020 Orseau et al.) 2020; Fischer et al., 2021 guarantee high existence probabilities of subnetworks that have double the depth and 2 30 times the width of the target network and thus non-optimal sparsity. Based on their 2L construction, Malach et al. least as
2020) even went so far to conclude that training by pruning might be computationally hard as training shallower NNs. However, it is well known that specific function classes can be approximated significantly more parameter efficient ways by deeper NNs rather than shallower ones (Mhaskar et al. 2017, Yarotsky 2018) and also be learned more efficiently (Schmidt-Hieber 2020). Thus, by leveraging its full depth, the randomly initialized 27. deep NN might contain a much sparser strong LT than any of the ones whose existence has been proven.
As a first step towards making claims about the existence very sparse representations, we therefore prove next lower bound on the probability that target NN of general architecture is contained in larger, randomly initialized NN with the same depth as the target network. As many relevant targets have known representations of lower sparsity than what is covered by this bound, we will afterwards propose a planting algorithm to design experiments that can distinguish between algorithmic and fundamental limitations of pruning for strong L.T's.
3

---

Published as a conference paper at ICLR 2022
1.00
0.5
0.75
0.00
0.5
0.5
0.25
0.5
-.00
-0.5
0.5
0.5
1
f1
Figure 1: Benchhmark data. Shown are samples from the Circle (left) and Helix (right) task.
2.1 LOWER BOUND ON EXISTENCE PROBABILITY
Pruning randomly initialized NN usually finds a strong LT that is close to target network but does not recover the original parameters exactly. First, we need to understand how these errors in the parameters affect the final network output and what enror sizes are acceptable. For completeness, we restate Lemma of Fischer et al. (2021) that guarantees an approximation the entire network. Lemma (Error propagation). Assume > 0 and let the target network f and its approximation fe have the same architecture. If every parameter of f and corresponding 0₂ of fe layer fulfils |0. - 0 a for
EL = IVTurki,mas
1+
sup zE(-1,1] 20 (0011)
I.)
I. II A=1+1
(|wio + te/l))
then it follows that [If felloo C.
Respecting the allowed errors we can next establish lower bound on the existence probability of a specific target network assuming standard initialization schemes with necessary non-zero bias initialization (Fischer et al.) (02I). The main argument is union bound over matching each target neuron (with K; parameters) with neurons of the mother network the corresponding layer.
Theorem 2 (Lower bound on existence probability). Assume that e (0, 1) and target network with depth and architecture are given. Each parameter of the larger deep neural net- work fo with depth L and architecture no is initialized independently. uniformly at random with
10 ~ - - (t)
ow _o ) and by ~ [[[ -I-m ow _Ik==1 ) Then, fo contains a rescaled
(R)
approximation fo of f with probability least
L
n
P fo I Afello Sc)
II
1=1
where et is defined as in Eq. 1 and the scaling factor is given by X I 1/0
We could obtain similar results for initially normally distributed weights and biases, we would just have to substitute e, by 2//2. A proof is provided in Appendix A.2
Thm. 2 provides with intuition for what kind of targets can expect find. First of all, it tells us that large number of nodes in a layer, and more importantly nodes with large in-degree ky render the existence of a specific network architecture strong LT less likely. Each additional layer reduces the probability further. Moreover, we observe that the last layer is bottleneck, as it usually has the same width in the large initial network. higher width of the mother network clearly advantageous. Note that we could turn this theorem also into a lower bound on the width vu,o of the larger mother network as common in existence proofs. Fig. 6 in Appendix AA. supports this intuition with the visualization of an example. Assuming the same width 74,0 ng and ny
across layers, would receive roughly 2 C' C'log( (Ln/))))) max: (c) (am) Even though it is poly-
nomial the relevant parameters, only provides a practical existence proof for extremely sparse architectures. We therefore have to resort to planting to answer fundamental questions about abil- ities of pruning algorithms. fact, the proof the above theorem inspires the planting algorithm introduced next.

---

Published as a conference paper at ICLR 2022
2.2 PLANTING STRONG LOTTERY TICKETS
As we have discussed, the LTs that exist with high probability rarely fulfill criteria of interest, such as low sparsity, favorable generalization properties, or adversarial robustness. We therefore propose to plant winning tickets with such desirable properties within randomly initialized neural networks. This approach offers the fiexibility to design experiments of different degrees of difficulty and gen- erate training and test data based on a ground truth.
A simple approach to planting a target f in a network fu would be to select a random subset of neurons in each layer and set them to their target values and otherwise randomly initialize the rest. This, however, would usually lead to a trivially detectable ticket because the target parameters are much larger than the initialized parameters of the larger mother network. The reason is that both networks produce output that lies in similar range (ideally the one of the training labels). Yet, the target network has achieve this by adding up much smaller number of parameters. A different perspective on the same issue is that pruned lottery ticket needs to be scaled up to compensate for the lost parameters. Note the scaling factor À in Theorem for that purpose. Thus, at least, we would need to scale the target parameters appropriately during planting.
We follow a more general approach that also applies to networks fo whose parameters have not been randomly initialized and that captures the full variability of possible target solutions by allowing for different scaling factors per neuron. We search in each layer of So for suitable neurons that best match a target neuron in f. starting from the first layer. Given that we matched all neurons in layer 1-L, we try to establish their connections to neurons in the current layer I. A best match is decided by minimizing the 12-distance to its potential input parameters thereby adjusting for optimal scaling factor. For example, let neuron in Layer of the target f have non-zero parameters = (b. w) that point to already matched neurons in Layer 1 - 1. Each neuron j in Layer I of fo that we have not matched yet could be a potential match for i. Let the corresponding parameters of j be m. The match quality between and j is assessed by (m = |0 A(m)mml2. where A(m) = g2mm |mml]2 is the optimal scaling factor. The best matching parameters m arg min,, (p(m) are replaced by rescaled target parameters / 8/Mm")) in fo- We provide pseudocode and details in App. A.3
2.3 CONSTRUCTION OF TARGETS FOR PLANTING
Based on the proposed planting algorithm, we generate sparse tickets for three problems that ex- pose general pruning algorithms to common challenges in machine learning: basic classification problem. regression problem, and manifold learning problem (Bishop) (2066.. On purpose, these are designed to avoid high computational burdens and, most importantly, have sparse neural network architectures with variable depth.
Regression of ReLU unit (ReLU) The ReLU unit d(x) is essential building block of state-of- the-art neural networks. It is particularly interesting to study because we know the optimal solution and can guarantee that it exists with high probability. Assuming mother network So of depth L, a ReLU can be implemented with a single neuron per layer. Any path through the network with positive weights II &f ,i) defines ReLU with scaling factor X = II W;, for indices in Layer 1 with - > O. Note that each random path fulfills this criterion with probability 0.5* so that even random pruning has a considerable chance to find an optimal ticket. A winning path exists with probability II (1 0.5 which is almost I even in relatively small networks. As a ticket with optimal sparsity exists with high probability, we would not need to plant However, to give also pruning algorithms a chance that do not specifically prune biases, we set ticket biases to zero. As we will see in experiments, despite this simplification, pruning algorithms are severely challenged and cannot find an optimally sparse ticket.
Classification of rings (circ..) Another basic building block of many functions, in particular, radial symmetric functions, is the radius or 12-norm of vector. It is also an important operation to We derived a sparse representation
represent products via the relation zy = (x5(x=)))-(--)"> that leverages the full depth of a given network, as its sparsity improves with increasing depth. In Fig. I we visualize the related 4-class classification problem with 2-dimensional inputs. The output is dimensiionl,, where each output unit fa(z) corresponds to the probability fa(z) that an input (z), x2) E [-1, 1 belongs to class c that is computed with softmax activation functions. The decision boundaries are defined in the last layer based inputs of the form g(1,, 222) of +23. The
5

---

Published as a conference paper at ICLR 2022
Layor 1-2 3
slope
Input
Taaee 4
(a) Mirroring along axes for Circle.
(b) Circle architec- ture with depth I. = 5.
(c) Univariate function approximation.
(d) Helix architecture with depth ==
Figure 2: (a) Visualization of the first layers of Circle representing g( x2) x xx. (c) (6) Amy = m - m
Univariate deep neural network parametrization with outer weights 0j
(b+d) Ticket architectures, edge width is proportional the absolute weight value, blue indicates negative sign, yellow a positive sign. Neurons are colored by bias sign, gray indicates zero biases.
high symmetry of g m2) allows us to construct particularly sparse representation by mirroring data points along axes as visualized in Figure 2 (a). Each consecutive layer mirrors the previous layer along the axis (1) (cos(1r/2) (oos(T/22-11)) /2 sin( sin(( 1)) To enable higher precision for networks of smaller depth, the second to last layer approximates h(x) x²² for each component. This is unnecessary for representations of high enough depth. The details of our construction are explained in App. App.[A.4.2] Fig. 2 (b) shows exemplary architecture of the planted ticket, for which we can vary the depth and width of the second to last layer. The lower bound on the existence probability given by Thm. _ (without planting) for the architecture shown in Fig. _ (b) is numerically 0 for mother networks of width n; = 100 as in our experiments and e = 0.005, even when we disregard the last bottleneck layer. For unrealistic high width n; 10 however, the bound is 0.47 and thus detection becomes theoretically feasible for extreme sparsity levels.
Identification of submanifold (Helix) Another common problem in machine learning is to learn lower dimensional functions that are embedded in higher dimensional space. In Fig. we show our minimal regression example in form of helix. As we have observed that many pruning algo- rithms have the tendency to keep a higher number of neurons closer to the input (and sometimes also the output layer), we construct ticket that has similar properties, see Fig. (d). This should case the task for pruning algorithms to find the planted winning ticket but, as we show in our ex- periments, this Hel ix problem surprisingly challenging. The helix has three output coordinates (x) (5x + 3Tx) cos(5m + 3/xx) (8:r,, f2(x)) (5tr + 3Tx) sin(5æ + (/Tr) (88)) and can approximate each of the dxx 8j) + ((0)) with depth L 2 (see Fig. (c) and App. A.4.3), which is achieved by the first layers, while the last layers basically represent the identity. An interesting feature of this example is that highest width could be assigned to almost any layer of the architecture, which makes He ix good candidate to provoke layer collapse different pruning algorithms. The lower bound on the existence probabil- ity given by Thm. 2 (without planting) for the architecture shown in Fig. (d) is numerically 0 for mother networks of any reasonable width, because nodes in the third layer have too large in-degrees. We therefore have to resort planting.
fa(x) = (5x + 33x))/(8x)) for I-dimensional input æ E [-],
components (x) by univariate deep neural network (.( = Σe= (6)
Strong tickets based on trained neural networks Even though we cannot expect to construct sparse baseline solutions for benchmark image classification tasks, we can leverage the fact that weak LTs can currently be identified at lower sparsity levels than strong LTs (see our experiments). To answer the question whether state-of-the-art pruning algorithms can find sparse strong LT's in the setting of standard benchmark data, we plant a trained weak LTT in a randomly initialized (VGG like) neural network. Note that the proposed pruning algorithm can also be applied to convolutional layers in addition to fully connected ones.
EXPERIMENTS
We utilize our planting framework to answer the question whether LT pruning algorithms that iden- tify subnetworks of randomly initialized neural networks able to identify highly sparse L.T',

---

Published as a conference paper at ICLR 2022
Accuracy
0.8
MAGNITUDE
SYNILOW GRASP
RANDOM
0.8
SNIP
Baseline Ticket
0.6
0.6
0.4
0.4
0.2
0.2
10
100
10" 2
10 Sparsity
Spansit
10
109
MSE
10
10 2
10-2
10-3
10-4
10
10
10-2
10
Spursity
Spursity
Figure 3: Singleshot results. Performance of discovered tickets against target sparsities as mean and value ranges (minimum and maximum) across 25 runs. In order of appearance: Circle after pruning (strong ticket), rclee ReLU, and Heliz x after training (weak ticket). Results after pruning look similar across tasks. Baseline ticket (leftmost sparsity) is given by black dashed line.
ideally in strong sense but also analyze weak LTs. Hypothetically, it could be possible that pruming algorithms for weak LTs only have to resort to training the identified LT because highly sparse strong LT does exist with high probability. Yet, if we guarantee the existence of a sparse strong LT, the algorithms would be able to find it and would not require further training. Similarly, we insist on finding extremely sparse architectures. might be necessary to give up the search for initial LT's (Frankle et al. 2020; Renda et al.) 20200 Liu et al., (2021a). If this were true, we should be able to find highly sparse LTs with the original pruning algorithm we ensure the existence of solution by planting.
We reject these hypotheses with our experiments, in which we randomly initialize a dense neural network of width n, 100 and depth L 5 by He initialization with nonzero biases (Fischer ctt al., (02I) and plant one of our constructed targets into the initial network. To show that our experiments reflect realistic conditions, image classification. For reproducibility, we provide details on data, networks, and experimental setup in App. [B.1] In general, report averages over results across 10 independent runs, well as obtained value ranges as minimum and maximum. We compare only pruning methods that identify lottery tickets subnetworks of randomly initialized neural networks, as these could potentially find our planted solution or an equally performing one. GRASP, SNIP, SYNFLOW, MAGNITUDE 2019 Tanaka al. 2020 Frankle &
also compare the general trends results standard
pruning. and RANDOM pruning (Wang al. 2220 Lee Carbin 2019) are thus considered, which are algorithms to discover weak tickets, and EDGE-POPUP, which is designed find strong tickets (Ramanujan et al.) 2020).
We distinguish two different pruning approaches, singleshot (see Fig. 3) and multishot (see Fig, In singleshot pruning, which is originally applied SNIP. SYNFLOW, and GRASP, edges are scored in single pass and then pruned to the desired sparsity. Compared to multishot pruning, this saves a significant amount of resources by preventing training entirely if a strong ticket is found. If a weak ticket is found, only small subnetwork needs to be trained once. Multishot pruning leads usualy to better results (Frankle et al. 202T), because relics on updated gradient information. Analogous to iterative magnitude pruning, for each round r, we iteratively reduce the sparsity to /²/10, where p is the desired network sparsity. Within each round, the current subnetwork is first trained, then pruned to the current target sparsity, and then reset to initial parameters for the next round. We analyze the performance of tickets before training to assess whether they qualify strong LTs and after training to evaluate whether at least pruning for weak LTs is feasible and can identify LT of sparsities that can compete with planted ground truth.

---

Published as a conference paper at ICLR 2022
Accuracy
0.8
0.6
0.4
0.2
10
10
10a
10
10
10
10a
MSE
10
10 10-3
10
10
10
10
10
10a
10
10
10
10
10
10
MSE
10
MAGNITUDE
SYNFLOW
10 10-2
RANDOM
SNIP
GRASP
10-3
RDGB-POP- ANNEAL
Baseline Ticket
10
10
10
10
10
10
Spursity
Spursity
Figure 4: Multishot results. Performance for Circle (top), ReLU (middle), and Helix (bottom) for 10 rounds alternating pruning and training. We provide mean and obtained intervals (minimum and maximum) of accuracies of the final pruned network across 10 repetitions before (strong ticket, left) and after (weak ticket, right) final training. Baseline ticket accuracy indicated in black.
Hand designed ground truth First, we note that training the full network (at sparsity level 1.0) can solve each of our tasks. Thus, planting does not destroy the general trainability of the initial mother network. In fact, we would observe the same performances without planting. Second, we find that none of the approaches able discover strong tickets, in particular not the planted ticket, in single shot. Moreover, only sparsity levels 2 0.1 the methods are able to find weak tickets. One of the problems that arise is layer collapse. While layer-wise pruning, i.c., setting a target sparsity per layer, would prevent this collapse, it still results in an interruption of flow. For Circle classification task, certain multishot methods are able to recover weak tickets, even at extreme sparsities with just marginal performance decrease compared to the ground truth ticket. However, only EDGE-POPUP able to recover strong tickets for this task, and those tickets have only sparsity levels orders of though
magnitude larger than the planted baseline POPUP algorithm using the described iterative pruning scheme. Furthermore, we observe that all considered methods struggle more with regression tasks rather than the classification task, they can only recover weak tickets of sparsity 0.1 or 0.01 and no strong tickets.
able improve the original EDGE-
more detailed analysis for varied network depth, width, noise levels, and pruning strategies, along- side a comparison with results on standard benchmark data is presented in the appendix. In summary, we observe similar trends for varying depth and width and find that the analyzed pruming algorithms seem to be robust to noise in the data. Furthermore, how the methods compare relative to each other in line with experiments on image data as reported the literature (Tanaka et al., 2020 Frankle al.) 202Tb. In particular, for all these methods similar drop around 0.01 sparsity observed for different VGG and Resnet architectures. This suggests that our simplified learning tasks expose pruning algorithms to challenging and in many ways realistic conditions.
VGG with strong tickets While no ground truth solution known for image classification tasks standard benchmark datasets, questions in this context, as we demonstrate next. To test the hypothesis whether EDGE-POPUP limited discover strong tickets of suboptimal sparsity of around 0.5, investigate its capabilities
still use planting framework to answer meaningful
8

---

Published as a conference paper at ICLR 2022
0.8
0.8
0.6
MAGNITUDE
SYNELOW GRASP
0.6
SNIP
HOGE-POPUP
0.2
0.2
Buseline ticket
10
10
10
10
10
10 Ticket sparsity
10
Ticket sparsity
Figure 5: VGG16 CIFARIO results. (Left) Performance for learned weak tickets. (Right) Perfor- mance of strong tickets discovered by EDGE-POPUP for VGG with planted baseline ticket of sparsity 0.01. Baseline ticket performance is indicated by black line.
to recover a planted baseline ticket from VGG16. For that, we use SYNFLOW to discover a weak ticket of sparsity 0.01 from VGG16 with multishot pruning, train the weak ticket on CIFAR10, and plant it back into the network. Running EDGE-POPUP on this network, we observe that it indeed cannot retrieve the baseline ticket of desired sparsity in this real world setting (see Fig. 5 rright)
Comparison with ground truth Our planting framework is designed for the analysis of LT algo- rithms that seek for subnetworks of randomly initialized NNs. Structure learning methods can also follow a different approach. While planting is less relevant in this case, we can still compare their results with our hand-crafted solutions. We show in App. [B.4 that neither dynamic sparse train- ing (Evci et al.] 2020) nor LT fine-tuning techniques (Liu et al. 2021a; Renda et al. 2020) find architectures that competitive with constructed ground truth tickets.
DISCUSSION & CONCLUSION
We investigated the optimality of existing lottery ticket (LT) pruning methods and their potential for improvement, both regarding the discovery of strong tickets subnetworks that perform well at initialization, as well as weak tickets subnetworks that perform well after training. Recent works, in particular by Frankle et al. (022)) evaluated LT pruning methods and showed that no single best method across considered settings and sparsities exists, and raised the issue of missing baselines in the field. To tackle this issue, we here proposed an algorithm that plants and hides target networks within a larger network, thus allowing to generate baseline tickets for rigorous benchmarking. For three common challenges in machine learning, a classification, regression, and manifold learning problem, we hand-crafted extremely sparse network topologies, planted them in large, randomly initialized neural networks, and evaluated the state-of-the-art pruning methods in combination with different pruning strategies.
Our results indicate that state-of-the-art LT pruning methods achieve in general sub-optimal sparsity levels, and are not able to recover I.T's that are competitive with a planted ground truth. This suggests that previous challenges to identify highly sparse winning tickets as subnetworks of randomly initial- ized dense networks (Frankle et al. 2020 Ramanujan et al.) 2020) can be explained by algorithmic limitations rather than fundamental problems with LT existence. While slightly discouraging, these result on benchmark data are coherent with reported as well as reproduced classification results on image data. This shows that our benchmarks, while artificial in nature, reflect realistic conditions that result in similar trends real world image data would. Moreover, we have shown that our planting framework can also be used in real data setting to answer a limited set of questions. For instance, by planting a trained weak ticket back into CNN, we established that the failure of EDGE-POPUP to discover extremely sparse strong lottery tickets is likely an algorithmic rather than a fundamental limitation. This exemplifies how our framework enables experiments beyond relative method comparisons, as typically conducted on standard image benchmark data. As our results in- dicate, several major questions pertaining to neural network pruning are still open: How can pruning approaches for weak tickets be improved to discover tickets of best possible sparsity? How can we find weak tickets of high sparsity that match the performance of the large network without interme- diate training rounds? And how that our contribution can be used and extended to measure progress regarding these questions against independent sparse and well- nell-performing baseline tickets.
discover highly sparse strong lottery tickets? We anticipate

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY
The code for our experiments is available in the Github repository RELLATTONALMM//PPAVNNEEES
which can be accessed with the following url: https: //t: w/ggithubb.... com Re lat iona IML/ P PlantNSeek/ree www.eeelssestgg///eeeeeee 0 betal Pseudocode for the discussed planting algorithm also available in the supplement alongside the proofs of our theoretical statements and a derivation of our planted solutions.
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations (ICLR), 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varinnee trade-off. Proceedings of the National Academy of Sciences, 156632)15889911
2019.
Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statis- tics). Springer- Verlag, Berlin, Heidelberg, 2006. ISBN 0387310738.
Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the existence of universal lottery tickets. International Conference Learning Representations (ICLR), 2022.
John Denker, Daniel Schwartz, Ben Wittner, Sara Solla, Richard Howard, Larry Jackel, and John Hopfield. Large automatic learning, rule extraction, and generalization. Complex Syst., 1(5), 1987.
James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning randomly weighted network. In International Conference on Learning Representations (ICLR), 2021.
Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning prune deep neural networks via layer- wise optimal brain surgeon. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 4857-4867, 2017.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Proceedings of the International Conference on Machine Learning (ICML), pp. 2952,2952, 2020.
Jonas Fischer, Advait Gadhikar, and Rebekka Burkholz. Towards strong pruning for lottery tickets with non-zero biases. arXiv preprint arXiv:2/ 20..::2/00.1// 10000.01111.....11.11 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations (ICLR), 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode con- nectivity and the lottery ticket hypothesis. In Proceedings of the International Conference on Machine Learning (ICML), pp. 3259-3269, 2020.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural net- works initialization: Why are we missing the mark? In International Conference on Learning
Representations (ICLR), 2021.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for effi cient neural network. In Proceedings the Annual Conference on Neural Information Processing Systems (NeurIPS), 2015.
Babak Hassibi and David G. Stork. Second order derivatives for network pruning: Optimal brain surgeon. In Advances in Neural Information Processing Systems (NIPS), 1992.
Diederík P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015.
10

---

Published as a conference paper at ICLR 2022
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in Neural Information Processing Systems (NIPS), pp. 598 605, 1990.
Namhoon Lee. Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations (ICLR), 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip Torr. A signal propa- gation perspective for pruning neural networks at initialization. In International Conference Learning Representations (ICLR), 2020.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. International Conference on Learning Representations (ICLR), 2017.
Ning Liu, Geng Yuan, Zhengping Che, Xuan Shen, Xiaolong Ma, Qing Jin, Jian Ren, Jian Tang, Sijia Liu, and Yanzhi Wang. Lottery ticket preserves weight correlation: desirable or not? In Proceedings of the International Conference Machine Learning (ICML), pp. 7011-7020, 2021a.
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. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2021b. 20211.
Eran Malach, Gilad Ychudai, Shai Shalev-Schwartz and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In Proceedings of the International Conference on Machine Learning (ICML), pp. 6682-669) 2020.
Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? In Proceedings of the AAAI Conference Artificial Intelligecce (AAAI), pp-
2343-2349, 2017.
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. In International Conference on Learning Repre- sentations (ICLR), 2017.
Michael C Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from a network via relevance assessment. In Advances in Neural Information Processing Systems (NIPS), pp. 107-115, 1989.
Laurent Orseau, Mareus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. Pro- ceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pp- 2925-2934 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic premmttraettiintoonnnn is sufficient. In Pro- ceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pp- 2599-2610, 2020.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in randomly weighted neural network? In Proceedings of the IEEE Con- ference on Computer Vision and Pattern Recognition (CVPR), pp. 1 11890-1 11000-11999..11 1899, 2020.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations (ICLR), 2020.
D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning internal representations by error propagation. In Parallel Distributed Processing, chapter 8. 1986.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 11380-1 1390, 2020.
11

---

Published as a conference paper at ICLR 2022
Franco Scarselli and Ah Chung Tsoi. Universal approximation using feedforward neural networks: A survey of some existing methods, and some new results. Neural Networks, 11(1):15-37, 1998.
Johannes Schmidt-Hiele Nonparametric regression using deep neural networks with ReLU acti- vation function. The Annals of Statistics, 48(4):1875-1897, 2020.
Terrence Sejnowski, Paul K. Kienker, and Geoffrey E. Hinton. Learning symmetry groups with hidden units: beyond the perceptron. Physica D: Nonlinear Phenomena, 2:260-275, 1986.
Suraj Srinivas and R. Venkatesh Babu. Generalized dropout. arXiv preprint arXiv:1611.0679,, 2016.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L.. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Kathryn Tunyasuvunakool. Jonas Adler, Zachary Wu, Tim Green, Michal Zielinski, Augustin Zidek, Alex Bridgland, Andrew Cowie, Clemens Meyer, Agata Laydon, Sameer Velankar, Gerard Kley- wegt, Alex Bateman. Richard Evans, Alexander Pritzel, Michael Figurnov, Olaf Ronneberger, Russ Bates, Simon Kohl, and Demis Hassabis. Highly accurate protein structure prediction for the human proteome. Nature, 596:1-9, 08 2021.
Rosemarie Velik. Discrete fourier transform computation using neural networks. In Proceedings of the International Conference on Computational Intelligence and Security, pp. 200-123, 2008.
Stijn Verdenius, Maarten Stol, and Patrick Forré. Pruning via iterative ranking of sensitivity statis- tics. arXiv preprint arXiv:2006. 00896, 2020.
Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference Learning Representations (ICLR), 2020.
Andreas Weigend, David Rumelhart, and Bernardo Huberman. Generalization by weight- elimination with application to forecasting. In Advances in Neural Informution Processing Sys- tems (NIPS), 1991.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representa- tions (ICLR), 2020.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Proceedings of the Conference On Learning Theory (COLT), pp. 699- 2018.
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 (ICLR), 2020.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Ze- ros, signs, and the supermask. In Proceedings of the Anmual Conference on Neural Information Processing Systems (NeurIPS), pp. 3597-3607, 2019.
A THEORY
In the following section, present the proofs of the theorems and lemmas of the main manuscript.
12

---

Published as a conference paper at ICLR 2022
A.1 ERROR PROPAGATION: PROOF OF LEMMA
Statement. Assume > and let the target network f and its approximation Se have the same
architecture. If every parameter 0 of I and corresponding 0, of Se layer I fulfils 10, S es for
(Wimi
(e1-->111 11.
II (/wo +e/l) A=++1
I.
61 :-
1+
sup =E|-1,1]00
then it follows that If felloo S.
Proof. Our objective is to bound ||ʃ - Selloo S. We frequently use the triangle inequality and that 16(x) d(v)l S |r y/ is Lipschitz continuous with Lipsehitz constant to derive
|xx(10) _1(
- n0 _
$ || (w(1) w("))
x x(1-1)
-0000 -11000-b?01-- + w!o (2ll-1) x²(-1)) -z(--))\| 11 + +aymi (1ww + +a) ( - x((11)) 11a
+
x x
x 11
cl
sup -
with er S Se/L. L. my denotes the number of parameters layer that are smaller than e, and W I j |magl- Note that my S mykitmmx-- The last inequality follows from the fact that all entries of
the matrix (w w!)) and of the vector (b(() be are bounded by ez and maximally
of these entries are non-zero. Furthermore, [w(0| - (I) ex) follows again from the
fact that each entry of (w()) (V:(-
w!") is bounded by Et.
Thus, at the last layer it holds for all x E [-1, 10 that
[If(x) f((x)]l2 (2) xc!1) 1|2
Σ aa/m 1+ sup
(111 11,
II k=1+1
(/w0l + cc(l) s T =6
using the definition e in the last step.
A.2 EXISTENCE OF SPARSE LOTTERY TICKETS: PROOF OF THEOREM
Next, we prove the following lower bound the probability that very sparse lottery ticket exists. Statement. Assume that E (0.1) and target network f with depth T, and architecture ñ are given. Each parameter of the larger deep neural network fo with depth L and architec- ture no is initialized independently, uniformly random with w [[[[-
(1) o000 and
1). Then, fo contains a rescaled approximation Se of ʃ with ( -I[-TT'- (k) II'-n 11
probability at least
L P(f C fo - -fello Sc)
14
II 1=1
11-
1-
1--2
6 k
where E is defined as in Eq. 1 and the scaling factor is given by X I 1/0
Proof. As shown by Fischer et al. (002I). the scaling of the output by À simplifies the above pa- rameter initialization to equivalent setting, in which each parameter is distributed as Wij. by U[-1,1]. while the overall output is scaled by the stated scaling factor X, again assuming that all parameters bounded by 1 e. Each parameter in Layer I needs to be approximated up to error ε according to Lemma] [[ To match the same sparsity level of f. for each neuron in each Layer / of f, we have to find exactly neuron in the same layer (Layer 1) of fo that represents i. We start
13

---

Published as a conference paper at ICLR 2022
with matching neurons at Layer (given the input in Layer 0) and proceed iteratively by matching neurons in Layer given the already matched neurons in Layer [ 1.
Let us pick random neuron in Layer 1 of fo- How high is the probability that it is a match with a given target neuron in layer 1 of f? The neuron i consists of k; parameters that have to be matched. Since the corresponding neurons in layer 1 - of f and fo have already been matched according to our assumption, we only have one possible candidate fg for each of the h; parameters 0c. For uniformly distributed parameters, we have 10; - - S e with probability Et. For normally distributed 0g ~ (O, 1). the probability is at least <1/2 (as long as 10n + el < 1. This can be seen by Taylor approximation of the edf of standard normal 4 + Az) 4(2 A²) in 2. For the remainder of the proof, however, we assume uniformly distributed parameters. Thus, all ky independent parameters are a match with probability k; Accordingly, none of the available nt,0
neurons in Layer is match with probability (1-+)) 11,0
With the help of a union bound we can deduce that the probability that at least one of the neurons n1.0
i in Layer of f has no match in fo is smaller or equal to Σn= (1 (1- ++
Therefore, the
converse probability that we find match for every single neuron in Layer / of f is at least 1 mi.d
Σ
Since we have to guarantee a match for each single layer and the matching probability of a new layer is conditional the previous layer, obtain lower bound on the existence probability of lottery ticket by multiplying the layerwise bounds.
This bound is only practical for very sparse target networks f with neurons of small in negeeeess k; still shows that the existence of very sparse lottery tickets is possible under the right conditions. To provide an intuition how this bound on the existence probability depends on the relevant parameters, we visualize the bound when one component is varied in a simple example, in which all nodes and layers are homogeneous so that they have identical properties like degree, width, etc. Fig. 6 shows that the bound most critically depends on the degree of a node and the width of the mother network. Yet, all parameters matter and can make the existence of a LT unlikely. Extreme sparsity can pose significant challenges to pruning algorithms, as we also see in experiments with planted solutions. Inspired by this proof, we therefore explain next how to plant tickets (which could have variable sparsity levels).
A.3 PLANTING ALGORITIIM
The idea of layerwise matching neurons starting with the layer closest to the input can be transferred to planting. The approach applies to general initial networks So whose parameters have not necessar- ily been randomly initialized and captures the full variability of possible target solutions by allowing for different scaling factors per neuron. Why are scaling factors necessary? The target network and the initial mother network need to produce output that lies in similar range (ideally the one of the training labels). Yet, the target network has to achieve this by adding up a much smaller number of parameters spanning larger range. A different perspective lottery ticket needs to be scaled up to compensate for the lost parameters. Note the scaling factor in Theorem 2 for that purpose. To cover natural degrees of freedom in ReLU networks, we instead allow for different neuron-wise scaling factors Xラ= > O. Note that such a scaling can be compensated by rescaling of parameters in the next layer, as
the same issue is that pruned
1+1) Ik
Φ (w (1+1) (wwtt///))) /21)0
Eiw (- + +00))))) (1+1)
To apply only small change to the random mother network during planting, we choose A together with matching target neurons and mother network neurons. We search in each layer of fo for suitable neurons that best match a target neuron in f. starting from the first hidden layer. Given that we matched all neurons in layer - 1. we try to establish their connections to neurons in the current layer I. A best match is decided by minimizing the 12-distance to its potential input parameters thereby adjusting for an optimal scaling factor. For example, let neuron i in Layer of the target f have non-zero parameters (b. wr) that point already matched neurons in Layer 1. With each of
14

---

Published as a conference paper at ICLR 2022
P[SLT oxiss)
0.8
0.6
0.6
0.4
0.2
0.0025
0.005
0.0075
0.01
k
(a) Varying approximation
(b) Varying in-degree l: in
0.8
0.8
0.6
F(SLT
0.4
0.4
0.2
(c) Varying network depth
(d) Varying target network width
P(SLT exiss)
0.8
0.4
logio 11,0
(e) Varying mother network width ver,o
Figure 6: Visualization of lower bound. Bound on SLT existence probability Eq. (A.2) for 6 0.005, k; 2, L 3, n4 2, and nıo0 remaining ones are kept fixed.
10 In each plot, one single variable is varied while the
15

---

Published as a conference paper at ICLR 2022
Algorithm 1: Planting
input : target f. larger neural network So output: fo with planted f J C Jo), output scaling factors À Initialize Vold = %
// scaling factors for input are
for /= 1 L
do
for all neurons i of f Layer do 0 = (b, w Aula)
// scaled parameters of neuron in // find best match for in fu
m = arg minm g0(m)
Replace m in fo by 0/\(m*)
A X(m*)
// remember scaling factor of in Jo
end
Asid A
end
11 return fo,
Algorithm 2: Faster planting by random matching
input target f. larger neural network fo output: fo with planted f (f C fo), output scaling factors Initialize Aold [o
// scaling factors for input
for = 1 to L do
for all neurons i of f in Layer do
0 = (b, w Aold)
// scaled parameters of in f
m parameters of random unmatched neuron fo Replace m in fo by 0/ 0/\(m*)
X; X(m*)
// remember scaling factor of in So
end
Auid = X;
10 end
return fo,
the matched neurons j' in Layer ( - has been previously associated scaling factor Aold, that the corrected 0 = (b, w Aota parameters would compute the correct neuron in fo. Layer of fu- each neuron that have not matched yet could be potential match for i. Let the corresponding parameters of be m. The match quality between and j is assessed by
qo (m) = ||e A(m)ml12
where X(m) = 0T m/ m the optimal scaling factor. The best matching parameters m arg min,, go(m) are replaced by rescaled target parameters 0/A(m") in So and remember the scaling factor X(m") to consider matches of neurons in Layer + 1. Note that this rescaling is necessary ensure that the neuron is properly hidden and attains similar values other non-planted neurons in fo- In addition to the provided pseudocode (Algorithm I Python implementation is provided online.
Matching neurons thoroughly can be computational resource intensive, if the target network f con- sists of high number of neurons, because each neuron needs to be compared with most of the neurons in the mother network or at least significant share of candidate neurons. A fast alternative to pick a random neuron in the mother network as match and choose an appropriate scaling factor (see Algorithm 2
A.4 CONSTRUCTION TARGETS FOR PLANTING
We propose three toy examples for planting lottery tickets that pose different challenges for pruning algorithms. Here, we explain the main idcas behind their construction in more detail. A Python
www.giithub.comm/eeetttiooo antNSSek
16

---

Published as a conference paper at ICLR 2022
implementation of related regression and classification problems is provided alongside the supple- mentary manuscript.
A.4.1 RELU UNIT
Apart from a trivial function f(x) = 0, a univariate ReLU unit = +(z)= max(æ, 0) is the most sparse lottery ticket that is possible. Assuming mother network fo of depth L, ReLU can be implemented with a single neuron per layer. Any path through the network with positive weights I ((wa)11)7) defines ReLU with scaling factor À I Wh-1h for indices it in Layer / with w/-4
Note that each random path fulfills this criterion with probability 0.5" so that even random pruning could have a considerable chance to find an optimal ticket. A winning path exists with probability IT (1- 0.5*h.), which is almost 1 even in small mother networks. Thus, planting is not really necessary in this case. Since not all pruning algorithms set biases to zero, however, we still set all randomly initialized biases along winning path to zero to make the problem easier.
As we see experiments, despite this simplification, pruning algorithms are severely challenged in finding an optimally sparse ticket. Even though basic, ReLU unit seems to be a suitable benchmark that is a common building block of other tickets.
A.4.2 CIRCLE
For simplicity, we restrict ourselves to a 4-class classification problem with 2-dimensional input. The output is therefore 4-dimensional, where each output unit fa(x:) corresponds to the probability fe(x) that an input (II, 22) E [_1, belongs to the corresponding class e with c = 0, 1, 2, 3. As common, this probability is computed assuming softmax activation functions in the last layer. The decision boundaries are defined in the last layer based on inputs of the form g z2). The role of the first layers with ReLU activation functions of Circle target to compute the function g( x2) = xî + z2. which is fundamental to many problems, in particular to the computation of radial symmetric funetions.
The high symmetry of g( allows us to construct particularly sparse representation by mir- roring data points along axes as visualized in Figure 2 (a). With the first two layers (1 = 1,2),
we map each input vector (21, to the first quadrant by defining zi e (œ + Φ (-21)
and x/2 o (12) + (-22). Thus, Layer 1 consists of neurons, i.c.. x]
(z1),
(1) $ (-22), while Layer I 2 consists of 2 neurons, i.e., mg (1) +b( (-r1), xz (1) o =x2), x1
(2) = ó (x1 + +x2 x2 = o 43 + +x21)) =
(1) (2)
Each consecutive layer 1 mirrors the previous layer (x1 .2l ( along the axis (1)
(1=
(cos(a/21-1)) sin(m/2(-1)), achieves this by mapping the neurons the previous layer to three neurons, one representing the component of z (i-1) that parallel (1), and two neurons that each represent the positive negative signal component that is perpendicular to the axis (!), The last two neurons could be added to single neuron in the next layer if we want to decrease the width of some layers in between. To take more advantage of the allowed depth L, we map three neurons immediately to the next three neurons that represent the mirroring by defining
(1) 11) 1) 11 = (af 21 (1-1) + a2 x2 02 13 12
(1) (1-1)
2 = (a (22 x1 (1-1)
(1) (1-1) (1-1)
(9 -) + ta 23
ai x22
2/3 d( -
()) If the depth of our network is high enough, we could use the parallel component x as estimate of the radius of the input. To enable higher precision for networks of smaller depth, however, we also apply to each remaining component a piecewise linear approximation of the univariate function h(z)) x² and add those two components. Note that any univariate function can be easily approximated by a neural network of depth L = 2. The precise approach is explained in our next example.
17

---

Published as a conference paper at ICLR 2022
A.4.3 HELIX
To test the ability of pruning algorithms to detect lower dimensional submanifolds, we approximate helix with three output coordinates fi (2) (5л 3πæ) cos(5m + 3xxr f2()) = (5T + 3Tx) sin(5x + 3 and [x(x) = (5T + 33x))/(8T) for I-dimensional input I E [-1, 1 1]. As we have observed that many pruning algorithms have the tendency to keep a higher number of neurons closer to the imput (and sometimes also the output layer), we construct a ticket that has similar properties. This should ease the task for pruning algorithms find the planted winning ticket.
Each of the components fx(z)) is an univariate function that we can approximate by an univariate deep neural network (I) that encodes a piece-wise linear function (see Figure (c) for an expla- nation). As neural networks are generally overparameterized, we have multiple options represent
(z).). For simplicity, we write it as composition of the identity with a depth L = 2 univariate network ga (z) of width N in the hidden layer, which can be written as
(x(x)
Σ oo of Mp - 8,))+++ +60,
where the signs Pj E {-1, 1 can be chosen arbitrarily (and we chose alternating signs to create diversity). The knots s = (8))JE(M) mark the boundaries of the linear regions and a = (0) ]JE[N]
indicate changes in slopes m = (fi($)+1) f(s))) / ($j+1 - 85) (with SN+1 == SN + c) from one linear region to the next. aj = m) (0) -m for 2 S S N. a
= m (0) and 6(9) =
fe(51) - Σكك aj (sp 8y)). Note that only the outer parameters a are function specific, while the inner parameters P, and sy can be shared among the functions f..
We thus create helix ticket by first mapping the input E [-1,1] to [0,2]. This allows us to represent the identity in the later layers by ø(x) = J. as x 2 0. We can always compensate for the bias +1 by subtracting bias -1 when needed. fa(x) represented by a path from the input to the output that only contains a single neuron per layer. We concatenate this path with a neural network that consists of layers that approximate fi fi)) and fa(r) and otherwise identity functions. At Layer / = 2, this network creates neurons of the form (x- where the knots sj mark an equidistant grid of [0. 2). Layer I = 3 creates two neurons,
(5x 3rx)
therefore be
(2) f2(x)). These can be computed by linear combination of the previous neurons using the parameters aj and b(t), All the remaining
one corresponding to x{? fi (xr) and one corresponding to 422
layers basically encode the identity.
B EXPERIMENTS
In this section, we discuss all relevant parameters and set-ups to reproduce the experimental results. Furthermore, we provide additional results obtained for singleshot learning spanning different ar- chitectures and pruning schemes. All source code to run pruning algorithms and to generate the data made publicly available.
B.I HYPERPARAMETERS AND DATA
For each experiment, we generate = 10000 samples, where input data is sampled from |-1, 1] for ReLU and belix and from [-1, 1]3 for Circle. The output for ReLU is computed by f(x) mar(0, 2). For He lix, we compute the three output coordinates as fi (x) (5 + +3TZz) (0r)+3///87 For ci rirce.,
and fa(x) we consider circles centered at the origin with radius v0.2, v 0.5,, and v0.7 as decision boundaries for the classes. We additionally introduce small amount of noise to simulate real world data more closely. For Circle we flip approximately 1% of samples to the next closest class, and for the two regression problems we introduce additive noise drawn from (0, 0.01) to each output dimension. To assess the accuracy respectively mean squared error of the tickets and trained models, we split off 10% of the data that acts hold out test set.
3Tx) (8m). (xx) = (5m+-3 (att://)eein(553+3333333333
18

---

Published as a conference paper at ICLR 2022
In general, all initial networks for each specific task generated using the algorithm explained in App. B.I For Circle, we use 10 knots for the piecewise linear approximation, and 30 knots for the piccewise linear approximations done in Helix. To prune by GRASP, SNIP, SYNFLOW, MAGNITUDE, and RANDOM and train the derived tickets, we use Adam Kingma & Ba (2015) with learning rate of 0.001. We found that this learning rate performed well over all experiments, and leading to accurate models when there is no pruning. It also corresponds to the default settings suggested by the authors of SYNFLOW Tanaka al.) (2020). Training of the discovered tickets was done for 10 epochs across all experiments, where we could always observe a convergence of the respective score on the validation sets (accuracy or MSE). We measured loss by MSE respectively cross entropy loss and used a batch size of 32 for all experiments. We report obtained intervals as minimum and maximum as well as mean across 10 repetitions for multishot, and across 25 repetions for the main singleshot experiments, all measured on the hold out test set.
Singleshot pruning For singleshot pruning, we considered networks of depth 3, 5, 10 each with layer width 100 for all three data sets on target sparsities {0.01, 0.5, 1] and the sparsity of the ground truth ticket. Additionally, we tested for network of depth 6 and width 1000 on Ci Circle for the same sparsity levels. As suggested by Tanaka et al., (2020). we also test SYNFLOW in com- bination with 100 rounds of pruning for network of depth 6 and width 100 on Circle. For all additional singleshot experiments, we provide results in the next section.
Multishot pruning For multishot pruning, we alternated pruning and training for 10 rounds, where each training step was carried out for 5 epochs, which consistently lead to convergence of accuracy on the considered Circle data set. Similar to singleshot pruning, we considered target sparsities (0.01, 0.1, 0.5, 1} and ground truth ticket sparsity.
EDGE-POPUP pruning To prune with EDGE-POPUP, we here used the parameters suggested in the original code of [Ramanujan et al. (2020), which is SGD with momentum of 0.9 and weight decay 0.0005, combined with cosine annealing of the learning rate. To establish a comparison to the multishot pruning results, we train the scores for 10 epochs. Additionally, for the experiment extending EDGE-POPUP by annealing the sparsity level, we slowly reduce the sparsity over time to p1/10, where p is the desired network sparsity, and is the current epoch.
B.2 DETAILED DISCUSSION OF RESULTS
Singleshot pruning In singleshot pruning, which is originally applied in SNIP, and GRASP, edges are scored in a single pass and then pruned to the desired sparsity. Compared to multishot pruning, this saves significant amounts of resources by preventing training entirely, if a strong ticket is found, or only training a small subnetwork once, in case a weak ticket is found. For our benchmark data, construct networks of depth 5 and width 100 and test the ability of algorithms to discover both strong and weak tickets. The key results are visualized in Fig. 3 reporting performance of the algorithms trying to discover tickets at varying sparsity levels across 25 repetitions.
We find that all approaches, including RANDOM pruning, are able to find weak tickets for moderate sparsity levels for Circle and ReLU, but fail recover them on the manifold learning task Helix entirely. Although MAGNITUDE pruning was originally not designed for this pruning strategy, it is on par with state-of-the-art singleshot methods. For lower sparsity levels S 0.01, in particular baseline ticket sparsity, all methods fail to recover good subnetworks. Dissecting the results, we observe layer collapse, meaning that entire layers are masked, thus disrupting flow through the network. Despite that SYNFLOW was proposed as a solution to this issue, we observe that it also experiences layer collapse for extreme sparsities, even when pruning for 100 rounds as suggested in the original paper, performing only slightly better than with one round of pruning (see Supp. B.5). In summary, with only a single pruning round, most pruning algorithms discover weak tickets at moderate sparsity, however fail to recover weak tickets of low sparsity and any strong tickets.
Robustness to noise To model real-world settings, all our datasets contain small amounts of noise as described in Supp. B. To rule out that noise in the data is the primary source for issues with discovering tickets, we generated Circle datasets with varying levels of noise. The results indicate that on the hand, without noise we do not see much of an improvement in terms of discovered
19

---

Published as a conference paper at ICLR 2022
tickets, but on the other hand observe that the algorithms robust even large amounts of noise, finding tickets with almost similar performance as with no noise at all (see Supp. B.5).
Comparison to results image data The reported results are in line with experiments on image data as reported in the literature (anaka et al. 2020p. In particular, for all these methods a similar drop around 0.01 sparsity is observed for different VGG and Resnet architectures and image data sets. Similarly, layer collapse has been reported for image data. The main difference is that for our data, we know the obtainable sparsity well performance of tickets, setting these results into context beyond trendline differences of methods for selected sparsity values.
B.3 PRUNING COMBINED WITH TRAINING
While much more resource intensive, iteratively training followed by pruning and resetting to initial weights, slowly annealing to the desired sparsity, has been proven successful approach to discover lottery tickets. Here we extend this pruning scheme to other approaches beyond magnitude pruning-
Multishot pruning To investigate the effect of multishot pruning, we run each of the previous methods iteratively for 10 rounds on our benchmark datasets (see Fig. A.. Analogous to iterative magnitude pruning, for each round r. we iteratively reduce the sparsity to p²/10, where p is the desired network sparsity. Within each round, the current subnetwork is first shortly trained, then pruned to the current target sparsity, and then reset to initial parameters for the next round. Com- pared to the singleshot results, we observe that for the classification task, MAGNITUDE, SNIP, and SYNFLOW are able to retrieve weak tickets of much higher sparsity. Furthermore, these three ap- proaches are now able to recover weak tickets of moderate sparsities also for the challenging He Heliix dataset. Overall, SYNFLOW consistently performs best in discovering weak tickets, even recovering the extremely sparse baseline ticket for Circle. We also observe that GRASP performs poor over- all, noting that it is a method designed for singleshot pruning. Examining the results, we see that GRASP experiences layer collapse already in early iterations with large target sparsities. None of the above approaches is able to discover a strong ticket.
To discover strong tickets, |Ramanujan et al. (0200) proposed EDGE-POPUP, which falls in the same category of multishot pruning approaches. EDGE-POPUP assigns each model parameter a score value, which is then actively trained for several rounds while freezing all original parameters, re- quiring similar computational effort as multishot pruning. Training EDGE-POPUP for 10 rounds, we observe that it discovers a strong ticket of sparsity 0.5 for Circle however fails to discover tickets of different sparsity, which is in line with their original results Ramanujan et al. (2020). Sim- ilar to other algorithms, we observe layer collapse. We can extend their original algorithm using annealing as in multishot pruning by slowly decreasing the sparsity in every round, which increases performance allowing it to discover a subnetwork with reasonable accuracy at 0.1 sparsity. Interest- ingly, EDGE-POPUP is not able to find any good subnetwork for the regression tasks.
GRASP with local sparsity constraints As observed before, GRASP seems unsuitable for mul-
tishot pruning due to carly layer collapse. Several works (You et al.) 2020 Tanaka al. 2020 considered local sparsity constraints, having a target sparsity for each layer, or even channel. These however impose unrealistic architecture constraints as layer sparsity is usually imbalanced (Tanaka et al. 2020), which also holds true for our Ci rcle e and He Helix benchmarks. With the goal to avoid layer collapse, we still equipped GRASP with local sparsity constraints per layer (see Supp. B.5). Yet, the flow through the layers stays interrupted. A possible explanation is that GRASP incorpo- rates information about weight couplings via the hessian in its pruning strategy, which makes it more sensitive to removing individual connections from the mask as it happens during iterative pruning.
Comparison to results on image data Our results are coherent with the reported relative trends on image tasks both for strong and weak tickets (Ramanujan et al., 2020 Tanaka et al. 2020). We
further reproduced results for VGG16 on CIFARTO with non-zero bias initialization (Fig. 5 left).
In particular, for strong tickets we observe the same trends for EDGE-POPUP spiking at 0.5 sparsity, performing less well at sparsity 0. and not recovering tickets for higher and lower sparsity. Again consistent with previously reported results, other methods are neither suited nor designed to find strong tickets. For weak tickets, SYNFLOW performs best, with only a slight margin towards SNIP and MAGNITUDE. This margin is however much tighter then originally reported in SYNFLOW, as we allow both SNIP and MAGNITUDE to learn in a multishot fashion, which closely resembles the approach of iterative magnitude pruning, so that we do not observe layer collapse for these methods.
20

---

Published as a conference paper at ICLR 2022
MACNITUDDE
SYNELOW
RANDOM
SNIP finetuned
GRASP
Baseline Ticket
vomilla
Accuracy
0.8
0.6
0.4
0.2
10-2
10
109
Sparsity
10
10
MSE
10-2
10
10
10
10
10 Sparsity
10
100
10a
10
MSE
10
10
10
10
Sparsity
Figure 7: Finetuning vs initialization. Performance for Circle (top), ReLU (middle), and Helix (bottom) for 10 rounds of alternating pruning and training. Visualized are weak ticket performances (i.e training on initialized weights) against finetuned subnetworks (i.e. no reset of weights after final pruning round). Baseline ticket performance in black.
VGG with strong tickets Finally, to put the hypothesis to that EDGE-POPUP is limited to discover strong tickets of suboptimal sparsity of around 0.5, we investigate its capabilities to recover a planted baseline ticket from VGG16. For that, we use SYNFLOW discover weak ticket of sparsity 0.01 from VGG16 with multishot pruning, trained the weak ticket, and planted it back into the network. Running EDGE-POPPU on this network, we observe that it indeed cannot retrieve the baseline ticket of desired sparsity in this real world setting (see Fig. right..
B.4 OTHER PRUNING APPROACHES
Finetuning Recent results indicated that finetuning discovered subnetworks yields better models than training these subnetworks from scratch (Liu al.] 2021a). In particular, they proposed to use iterative (magnitude) pruning and skip the resetting of the parameters to their initial values, but rather continue training the current parameter set, which incurs no additional computational over- head. Here, we investigate how finetuning affects results our benchmark data for all considered methods. We repeat the multishot learning experiments in combination with finetuning and visualize the results in Fig. 7 For the considered classification task, finetuning matches the performance of classical 'weak ticket' -training with parameter reset, achieving almost perfect accuracy levels for up to .01 target sparsity. For even sparser target networks,
marginal improvement of MAG- NITUDE and SYNFLOW by using finetuning, which is however within the confidence the original prediction. For the regression tasks we get slightly different view: here, the original weak tick-
21

---

Published as a conference paper at ICLR 2022
True Ticket
Accuncy
0.8
0.6
0.4
10-3
10-4
10
Sparsity
(a) RIGL on Circle.
10a
10
MSI
10-2
10
10
10-3
10-2
10-1
Sparsity
(b) RIGL on ReLU
109
MSE
10
10
10-3
10
10
10
Sparsity
(c) RIGL on Holix.
Figure 8: RIGL. Performance for Ci rclce (top), ReLU (middle), and Hel x (bottom) for 60 rounds of training with default parameters. We report mean and minimum and maximum values across 10 repetitions. Baseline ticket performance is indicated black dashed line.
already detoriate in performance for relatively dense target networks of 55 or .1 target sparsity. Notably, for the ReLU task, finetuning does improve ticket performance for those sparsity levels, such that the algorithms can match the performance of the ground truth ticket. For more extreme sparsity levels, we see a drastic improvement for MAGNITUDE pruning, but no improvement for other algorithms or at ground truth ticket performance. For Helix, the results are mixed, where we observe an improvement at dense target sparsities of 55 similar to before, but no improvement or even a decrease of performance for smaller target sparsity levels. In summary, on our benchmarks, finetuning helps to improve performance at relatively large target sparsity levels (> .1), but does not provide an advantage compared the common training after parameter reset for extreme sparsities.
RIGL While the main focus of our paper are lottery tickets, we here briefly discuss results for RIGL (Evii et al., 2020), a state-of-the-arr dynamic sparse training approach, which results sparsified and trained network architectures which are comparable to trained 'weak' tickets. For our bench- mark data, we construct similar networks as for the multishot experiments - i.e. depth 6 and width 100 fully connected networks and run the available implementation of RIGL with default param- eters as suggested in the paper, and Adam optimization with the same parameter settings as for all other considered methods. We train networks for 60 epochs, which results in comparable amount
22

---

Published as a conference paper at ICLR 2022
of training time as in the multishot experiments, and note that good performance is reached much earlier.
The original results reported in Evci et al. (2020) indicate that for their considered (classification) tasks, RIGL outperforms other dynamic sparse training methods, and that for target sparsity levels of 2 In the original paper, there was exploration of the more extreme sparsities considered here, nor a comparison to ticket pruning other than SNIP. Our results on Circle match those results, with RIGL being able to match ground truth ticket performance for sparsity .5 and .1. The performance, however, decreases quickly with more extreme sparsity levels (see Fig. B). In comparison with the multishot results, we observe that SYNFLOW, SNIP, and MAGNITUDE pruning outperform RIGL on this task for the extreme sparsity levels (compare Fig. +. Note that the version of SNIP used in the original paper is essentially the singleshot approach, which indeed performs worse than RIGL. (compare Fig. 33.. For regression tasks, we see similar trend, with RIGL performing comparably good SNIP for sparsity levels 2 .1, but the performance decreases rapidly for more extreme target sparsitiy levels. Generally, for the regression tasks we observe that RIGL is outperformed by the state-of-the-arr ticket pruner SYNFLOW and iterative MAGNITUDE pruning. Yet, RIGL allows for efficient computations, saving FLOPS by only infrequently updating gradients, which render it the method of choice for target sparsities of 2 in specific applications.
.1 and lower, performance quickly deteriorates for all methods
B.5 ADDITIONAL RESULTS SINGLESHIOT LEARNING
Model depth In this section, we provide all results from the singleshot learning for depths 3, 10 and width 100 in Figure 1 and I1] respectively. We observe that all methods have problems to deal with smaller networks, while the results for the larger networks are consistent.
Model width To investigate the effect of layer size, we run an experiment with a network of depth 6 and width 1000 on Ci rcle as the layer size is an important factor for the theoretical probability of the existence of tickets- and report the results in Figure [2] We observe that although the network much larger, there is barely any change in comparison the previous results. Note that the results after training of tickets of individual sparsities cannot be directly compared directly to the other singleshot results, the tickets are much larger (due the much larger number of parameters) and hence easier to train.
Multiple pruning rounds We report the results of running SYNFLOW with 100 rounds of pruning network of depth and width 100 for Circle in Figure 13 We find that there is again barely any change to the original singleshot results after pruning. but there is a slight increase in performance after training compared to the single-round singleshot results.
Noise experiments To test the robustness of pruning algorithms to noise in the data, we considered the Circle problem with a network of depth 6 and width 100 and varied the amount of noise in the data to be {0, 0.001, 0.01, 0.1}. We report the results before and after training in Fig. 14
B.6 ADDITIONAL RESULTS ON MULTISHOT LEARNING
To test whether we can reach an improvement of the performance of tickets discovered by GRASP using multishot pruming approach and avoid layer collapse, we additional experiments using a local pruning rate. In particular, we used layer-wise pruning setting the target sparsity of the parameters of each individual layer to the global sparsity level. We report results in Fig. 15
Note that Evci et al. 2020) use percentage of pruned parameters for their plots, i.e. spaasiity compared
our paper.
23

---

Published as a conference paper at ICLR 2022
MAGNETDE
SYAPLOW
Accurccy
0.8
RANDOM
SNIP
0.6
0.4
0.2
10
10
10
10
10
109
Sparsity
Sparsity
10
10
MSE
10
10
109
109
Spursity
Spursity
10a
MSE
10-1
10-2
10-3
10
10
10"
10
Sparsity
Sparsity
Figure 9: Singleshot results depth 3. Performance of discovered tickets for Circle, ReLU, and Helix against target sparsities as mean and obtained intervals (minimum and maximum) across 25 runs. order of appearance from top to bottom: Circle. ReLU, and Helix post pruning (left) and post training performance (right). Baseline tickets have sparsities of 16,, and .999 and their performance given by black dashed line.
24

---

Published as a conference paper at ICLR 2022
MAGNITUDE
SYNFLOW
Accurccy
0.8
RANDOM
SNIP
0.6
GRASP
Ticket
0.4
0.2
10"
10
100
10"
10 Sparsity
109
Sparsity
10
10
MSE
10
10-3
10
10 -4
10 2
10
10
4
10
10
10 1
10
Spursity
Spursity
10a
MSE
10-1
10-2
10-3
10a
10
10a
Sparsity
Sparsity
Figure 10: Singleshot results depth 5. Performance of discovered tickets for Circle, ReLU, and Helix against target sparsities as mean and obtained intervals (minimum and maximum) across 25 runs. order of appearance from top to bottom: Circle. ReLU, and delix post pruning (left) and post training performance (right). Baseline ticket with leftmost sparsity and performance given by black dashed line.
25

---

Published as a conference paper at ICLR 2022
MAGNITUDE
SYNELOW
Accuracy
0.8
RANDOM GRASP
SNIP Truc Ticket
0.6
0.2
10 2
10
10
10
2
10
10
Spursity
Sparsity
10a
10
MSB
10-3
10
10
10
10
10
10
10
10
10 Spursity
10
10
Spursity
10
MSE
10
10-2
10
10 -
10"
10 10
10a
Sparsity
Sparsity
Figure 11: Singleshot results depth 10. Performance of discovered tickets for Circle, ReLU, and Helix against target sparsities as mean and obtained intervals (minimum and maximum) across 25 runs. order of appearance from top to bottom: Circle. ReLU, and Helix post pruning (left) and post training performance (right). Baseline ticket has leftmost sparsity and its performance given by black dashed line.
MAGNIFUDE
SYNELOW
RANDUM
Accuracy
0.8
0.6
0.2
mmy
10-4
10
10
10
10
10-3
10-2
10a
Sparsity
Sparsity
Figure 12: Singleshot results, depth width 1000. Performance on test data are plotted for Circle against target sparsities. We report mean and obtained intervals (minimum and maximum) across 10 repetitions of ticket performance right after pruning (left) and after training (right). The baseline ticket performance is indicated by the black dashed line, leftmost sparsity correspond to planted ticket sparsity.
26

---

Published as a conference paper at ICLR 2022
True
Accuracy
0.8
0.8
0.4
0.4
0.2
0.2
10
10
10"
10
10
10
Sparsity
Sparsity
Figure 13: Singlehhot results for SYNFLOW with 100 pruming rounds. Performance on test data are plotted for Circle against target sparsities. We report mean and obtained intervals (minimum and maximum) across 10 repetitions of ticket performance right after pruning (left) and after training (right). The original network is of depth 6 and width 100. The baseline ticket performance indicated by the black dashed line, leftmost sparsity corresponds to planted ticket sparsity.
MAGNITUDE
SYNELOW
RANDOM
SNIP
GRASP
Baseline ticket
noise
0001 noise .... 01 noise
.I noise
0.8
Accurey
0.6
0.4
0.2
10
10
10a
Sparsity
0.8
Accuracy
0.6
0.4
10-2
10
10a
Spansity
Figure 14: Varying noise. Performance of methods for Circle e with varying noise for 10 rounds of alternating pruning and training. We report and obtained intervals (minimum and maximum) of accuracies of the final pruned network across 10 repetitions before (left) and after (right) the final training. The noise level is indicated by line type. Baseline ticket accuracy is given in black.
27

---

Published as a conference paper at ICLR 2022
GRASP True Ticket
Accunacy
0.8
0.6
0.4
0.2
0
2
1
10a
10
10
Sparsity
Spursity
Figure 15: Multishot with local pruming. Performance test data plotted for Ci rale against target sparsities. We report mean and obtained intervals (minimum and maximum) across 10 repe- titions of performance after pruning (left) and after training (right). Baseline ticket performance is indicated by the black line, second to left sparsity correspond to planted ticket sparsity.
28


Reviews:
[{"review_id": "Z82z-laH6nG", "reviewer": "Reviewer_2wJr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the idea of embedding hidden tickets inside a network to evaluate lottery ticket hypothesis is interesting, but this paper is let down by the mismatch between the proposed method and experiments section:\n\nThe derived lower bound applies to strong lottery ticket hypothesis but the experiments section mostly focuses on pruning-at-initializaton methods such as SNIP, GraSP, and SynFlow that were clearly designed for a different (e.g. weak LTH) setup. Given that one of the claimed aims of this paper is to analyze the ability of state-of-the-art pruning methods in finding tickets, the authors should elaborate on how the insights from their approach are transferable to these methods. The authors do note this gap but claim that the insights are similar to known trends in image classification and therefore the insights are transferable. However, I'm not sure how this setup can be used to make any new claims about pruning-at-init methods.\n\nI'm also not convinced about the three designed tasks in the experiments section. The authors claim they construct tickets for tasks that represent \"typical machine learning problems\" but these tasks are not typically used in the LTH literature. It would be great if authors discuss how these are relevant to the image classification task that LTH literature mainly targets. Some citations to where similar tasks are used would also be great.\n\n### Lower bound on existence probability\n\n- The authors prove the lower bound for MLPs but say it can also be applied to convolutions. Does this include architectures that include BatchNorm and/or residual connections. Given that these are the most commonly used architectures, the authors should discuss in more detail how the proof applies to these models. \n- I think it would be great if authors could provide plots that give better intuition for theorem 2 in terms of what kind sparsities one can expect for typical architectures. Perhaps as a function of in-degree and width of the parent network? Basically it's not immediately obvious to me how tight these bounds are.\n- The authors exclude the last layer from the strong lottery ticket hypothesis and mention it is common practice. Could you cite some of the references where this is common? I believe the original paper by Ramanujan did include the last layer (and BN layers). It would be great if the authors could also provide ablations to show how much this assumption skews the results?\n\n### Planting the ticket\n- This seems to be a core idea of the paper but I don't think it's well described in the paper. I think the authors should elaborate on the role of scaling factors in the method. I'm assuming the whole point behind them is to do the actual \"hiding\" part of the method but that aspect has been somewhat lost in the current version.\n- I think a diagram could be very useful in explaining the ticket planting here.", "summary_of_the_paper": "This paper argues that one reason evaluating the strong Lottery Ticket Hypothesis is difficult is the lack of ground-truth tickets. They circumvent this by embedding a winning ticket in the weights at initialization and evaluating how well different methods can recover it. ", "summary_of_the_review": "Interesting idea but there's a mismatch between the proposed theorem and the experiments.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H1ekn4cv8rK", "reviewer": "Reviewer_RZKn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "##########################################################################\n\nPros: \n\n(1) The paper gives a lower bound of strong winning tickets with the same depth as the target network, which reduces the dependence on the larger model depth.\n\n(2) The winning ticket planting is quite interesting and can provide ground truth for pruning before training. \n\n##########################################################################\n\nCons: \n\n(1) I miss the motivation of planting the winning ticket to the large network. How was the target network selected? Will this winning ticket still win after being planted into the larger network? A further experiment to validate the effectiveness of winning ticket planting is required. What's more, as shown in \"Stabilizing the Lottery Ticket Hypothesis\", the initialization might not be enough to guarantee the matching performance. If this planted ticket can not match the full accuracy, it is reasonable that various pruning methods e.g., SNIP, GraSP, achieve unsatisfied performance. \n\n(2) We are missing the experiments without ticket planting. Will the accuracy of various pruning methods remain similar or not? This will help us understand the role of ticket planting better.\n\n(3) It's not clear the novelty of this work to me. The empirical findings in the paper seem already be presented in the previous work Frankle2021, which includes larger architecture and datasets. Is the bound provided tighter than the existing works? \n\n(4) How are neurons matched in the lottery ticket planting? I suppose that the matching between the target ticket after training and the initial network is difficult.\n\nMinor typos:\n\n(5) Most quotation marks in the paper are used incorrectly, e.g., ’winning tickets’.\n\n## After rebuttal\n\nThanks a lot for the response! \n\nAfter reading the response, the motivation and contribution are clearer to me. However, I am not convinced about the effectiveness of ticket planting. I believe more elaborate sentences/figures/diagrams are necessary to help explain the whole process of ticket planting, as the core contribution of the paper. I notice that I am not the only one who is confused by this planting process. I encourage the authors to add the empirical results to support the effectiveness of ticket planting as well. Overall, I decided to increase my grading to 5.", "summary_of_the_paper": "This paper develops a framework that allows planting and hiding winning tickets within a randomly initialized network and can be further used to assess the state-of-the-art pruning before training methods. Their empirical results of three common challenges are in line with the previous findings in Frankle2021. ", "summary_of_the_review": "The motivation and the correctness of the lottery ticket planting are not clear to me. And the empirical findings in this paper are already presented in the previous paper Frankle2021.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DAEughBm-fD", "reviewer": "Reviewer_HJLz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Well written paper overall, with clear motivation, experimental method and interesting results/conclusions.\n- Proposed idea is, as far as I'm aware, novel when applied to sparse neural networks.\n- The experimental setup is overall very well thought out (save the potential issues below), and interesting. It is complementary to the many papers that explore this topic in real models/datasets empirically.\n- The paper presents a novel take on the ability to find good sparse subnetworks before and after training, with the results suggesting that the state-of-the-art methods for finding \"strong\" (before training) subnetworks do not perform as well as those for finding \"weak\" subnetworks even in for these toy problems — results matching the conclusion of other recent works in the field, but from a very different angle.\n- Common wisdom for the lack of good results at high sparsity is, I believe, that at extremely high sparsity, there are just not enough weights to solve the problem. However this work shows that in cases where we know there are extremely sparse solutions, and we have enough weights, these solutions are still not found; it seems in part due to layer collapse. This result is actionable, and provides an interesting research direction for improving sparsity in neural networks, can we find methods that better avoid mode collapse and are able to discover these \"planted\" tickets, and does this generalize to real-world problems?\n\nWeaknesses:\n- The abstract, unlike the rest of the paper, is relatively poorly written and does not do the paper justice as it is. For example, \"for which we lack ground truth information\" is very ambiguous, this should read, \"for which we lack knowledge of ground-truth solution subnetworks\" or something similar. I would suggest the authors replace this with an abstract based on the first paragraph of their conclusion, which presents a much better summary of the paper than the current abstract.\n- This work shares some similarity with \"Large Automatic Learning, rule extraction and generalization\", Denker et al., 1987. In that work small neural networks were trained on the toy binary problem of identifying binary sequences as either having \"one\" or \"two or more\" clumps/clusters. The solutions were compared with ground-truth human proposed solutions much like in this work. *However* that work showed that dense NNs do not necessarily identify weights/structure (i.e. subnetworks) that humans would identify/hand design, but they do find equally performant solutions (that weren't as compact) — an important finding that seems relevant to this work, and suggests an important, but missing issue with the author's experimental setup: **Can dense NN find these hand-designed tickets/solutions?** Perhaps this is not a restriction of sparse DNN search/training algorithms, but a problem with NN training in general?\n- I would have liked to have seen the result from dynamic sparse training methods for finding weak tickets (such as RiGL), which are state-of-the-art in (weak) post-training sparsity. In particular the ability of DST methods to potentially avoid layer collapse would make them an intestine avenue to being explored (just as the authors explored iterative methods). This is a major weakness in the evaluation in my opinion.\n- It's unclear how much the results on these toy problems have bearing on the issues in finding subnets for real problems/datasets, the authors try to address this concern, but not enough that the reader can discount the issue — I found the experimental setup for planting subnetworks found from real models into randomly initialized models less convincing however.\n- The authors should also cite previous work looking at training NNs on toy problems where the solutions are known (not necessarily the above reference, it's just the first that came to mind).\n- There is very little space in the main paper dedicated to the results, with the results only being presented in 3 figures that are relatively small, although there are a lot more results in the appendices.\n", "summary_of_the_paper": "The authors identify that contemporary methods for finding very sparse subnetworks in deep neural networks (DNNs), including both methods for finding either \"weak tickets\" (after training) or \"strong tickets\" (before training), do not find very sparse (and good) solutions. They question if this is a fundamental limitation (i.e. these very sparse solutions don't exist), or if this is a limitation of current methods in finding such solutions. To answer this question, the authors propose to either \"plant\" known good very sparse subnetworks in DNNs, or to try and find solutions for toy problems for which the authors could identify good hand-made very sparse subnetworks - including a classification problem (Circle), function regression (ReLU), and manifold-learning problem (Helix) . The experimental results analyze the performance of strong and weak sparse subnetwork search methods, including GraSP, SNIP, SYNFLOW, alongside magnitude and random pruning in finding these planted tickets. None of the strong ticket methods are able to find the \"planted\" tickets for any sparsity level, while the weak methods are able to find tickets, but not at extreme sparsity. Further analysis reveals layer collapse in particular to be a problem. The authors conclude that rather than a fundamental limitation, current methods (in particular for strong tickets) are limited in finding very sparse tickets even if they are known to exist at that sparsity level.", "summary_of_the_review": "This is overall a very well written paper (strangely with the exception of the abstract), with a clear motivation and experimental method that I believe is novel in the sparse NN realm. The paper asks fundamental questions on the ability of contemporary methods for finding sparse subnetworks both before training, with an interesting experimental setup, and finds results (in the toy problem setting) that suggest these methods are lacking. Layer collapse specifically is identified as one of the problems leading to this issue, and the paper is somewhat convincing that the problem of finding very sparse solutions is algorithmic rather than a fundamental limitation. \n\nUnfortunately the paper loses some relevance in that it lacks any analysis of dynamic sparse training methods in addressing this problem, also it's not clear that the author's implicit assumption that a dense DNN could find these hand-designed solutions is true — perhaps this is not a restriction of sparse DNN methods but NNs in general. Nevertheless, overall it remains interesting and relevant overall, and I recommend its acceptance - although I encourage the authors to revise the abstract.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "97gVGzAvwBQ", "reviewer": "Reviewer_kf7j", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors provide an interesting new avenue for evaluating pruning methods, with the use of ground truth sparse networks.  This contribution relies on a theoretical result, which allows us to place a lower bound on the probability of a strong, sparse network.  These both are useful contributions.\n\nFrom a practical, empirical perspective, I do have concerns about the impact of this result, as the authors note that strong networks are currently still difficult to find.  Moreover, I also have some concerns that the outcome of using ground-truth strong networks largely confirms prior work (Frankle et al., 2021, Ramanujan et al. 2020) and yet relies on much smaller networks for evaluation than the networks evaluated in prior work.  The VGG-16 task is presented as a bit of an afterthought and is not central to the experiments, so I am uncertain how this planting algorithm can be scaled to similarly larger tasks. At the same time, I share the author's hope that using ground truth strong networks will spur new methods for the finding of strong, sparse networks.\n\nMy suggestions for the paper are mostly cosmetic in nature.  First, the inclusion of Zhou et al 2019, would provide a fuller picture of the history of research into strong lottery tickets, as Ramanujan et al. 2020 write that their work was inspired by the results shown in Zhou et al 2019.  Additionally, the description of \"confidence\" in the plots is not only vague, but not visible based on the format of the plot markers.  These markers are too large for the current \"confidence\" metric, which is not explicitly described in the paper.  Organizationally, information from A2, A3, and B1 were most helpful to me personally in understanding the paper.   In fact, I found section A3 and B1 more useful to understand the experiments than sections 2.2 and 2.3. I believe that content from these sections would better help the reader if they were presented in the main sections of the paper.  Whitespace used in the main paper could be reorganized, and figures 1 and 2, I believe were less helpful in understanding the paper and could therefore be moved to the appendix.\n\n----\n\nBased on the additional information provided by the authors in response to reviewer feedback, I would also like to increase my review score.\n", "summary_of_the_paper": "The authors note a distinction between kinds of sparse networks in the literature. \"Weak tickets\" require training to perform comparably to the original network, while \"strong tickets\" do not.  The authors prove a lower bound for the probability that a strong ticket exists, and note that instead of training, this \"strong ticket\" need only be scaled by some constant to achieve similar performance to the larger network.  Using the insights of this proof, the authors propose three benchmark tasks to find a ground truth sparse network.  They evaluate common pruning methods to find both weak and strong tickets using these tasks, and find that most methods perform well on 2 out of the three weak ticket finding tasks.  They also note that the only method designed specifically for strong ticket finding performs well on these tasks.  For further evaluation, they additionally share weak and strong ticket finding results for VGG-16.\n\n\n", "summary_of_the_review": "Overall, this work I believe would be a useful contribution to the community.  I think however, further streamlining of the manuscript to improve clarity would strengthen the paper.  First, citation of Zhou et al https://arxiv.org/abs/1905.01067 would strengthen the related work, as  Ramanujan et al. note the influence of the paper on their work.  Second, re-plotting the figures so that \"confidence\" is both clearly defined (percentile value for the confidence is not defined) and visible within the plots, would allow the reader to better interpret the plots on their own.  Third, information from Appendix A2, A3, and B1 are useful experimental details and would help the reader if they were presented in the main section of the paper instead of the appendix.  In fact, I found section A3 and B1 more useful to understand the experiments than sections 2.2 and 2.3. Whitespace used in the main paper could be reorganized, and figures 1 and 2, I believe were less helpful in understanding the paper and could therefore be moved to the appendix.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "844oawdeVIA", "reviewer": "Reviewer_vW7Q", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strength:**\n1. This paper provides a framework for benchmarking different pruning methods on their abilities to identify strong/weak lottery tickets, which can provide rich insights for the lottery ticket community.\n2. The proposed framework is driven by theoretical analysis.\n\n**Weakness:**\n1. One major concern is what's the practical usage of the proposed framework in real-world tasks like image classification, considering the optimal solution is no more available. Can the framework still plant near-optimal solutions and provide useful insights in these cases? Although the paper analyzes some general trends, it's not clear whether such observations can be consistently scaled up to large-scale datasets. \n2. The paper is not well-written and the logical flow can be improved. For example, it's not clear the \"lottery ticket\" in Sec. 2 denotes strong or weak lottery tickets, leading to many confusions. The wording in Sec. 2.1/2.2 can be improved with more structural logic. In addition, the title of Sec. 2 is not accurate as \"existence of lottery tickets\" has been discussed in the first lottery ticket work.\n3. Other questions: \n- For the problems proposed in Sec. 2.3, are there any references? It's not clear why they can \"reflect typical machine learning algorithms\" as described in the contributions.\n- It's a common practice of existing pruning methods to further fine-tune the pruned networks with inherited weights. In addition, a recent work [1] also shows that fine-tuning the identified tickets can achieve better results than retrained lottery tickets or rewinded lottery tickets, which also aligns with the common practice in network pruning. Can the proposed framework indicate what's the best pruning algorithm with the best final accuracy beyond the scope of lottery tickets?\n\n[1] \"Lottery Ticket Preserves Weight Correlation: Is it Desirable or Not?\", N. Liu et al., ICML'21.", "summary_of_the_paper": "This paper proves the existence of strong lottery tickets and further develops a framework to plant and hide winning lottery tickets with desirable properties in randomly initialized networks to help analyze the ability of state-of-the-art pruning methods for identifying tickets of extreme sparsity.", "summary_of_the_review": "Given the concerns about the practical usage of the proposed framework, I tend to deem this paper marginally below the acceptance threshold. I'm willing to adjust my scores if the concerns are addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper takes on (in my view) one of the most important questions in the lottery ticket literature today: how small are the smallest lottery tickets that exist in our neural networks? Many methods have been proposed for finding weak lottery tickets (those that require training to reach full accuracy) and strong lottery tickets (those that do not), but we have no idea how close they come to finding the smallest lottery tickets. Moreover, in many cases, we only know how to find lottery ticket subnetworks early in training rather than at initialization. Is this a fundamental limitation on the existence of lottery tickets, or is this simply a limitation of our methods for finding them? I am personally very involved in lottery ticket conversations in the literature, and I believe I can speak with some authority when I say that these are vital questions where any progress is important.

Moreover, these are exceedingly difficult research questions, and (again, in my view) the authors should be commended for taking them on. A naive approach to these questions would involve brute force search over all possible subnetworks, which is infeasible even on the smallest of toy examples, let alone the meaningful computer vision tasks where lottery ticket work typically focuses.

I am sharing all of this information to provide background for my confident recommendation to accept this paper over the many legitimate concerns expressed by reviewers and those that I saw when reading the paper in detail. Those include that:
* This paper does not solve any of these research problems in their entirety.
* It focuses on toy networks smaller than those traditionally studied in the lottery ticket literature, and it is well known that lottery ticket behavior changes in character at larger scales.
* Planting good subnetworks may be an unrealistic proxy for the kinds of subnetworks that actually emerge naturally.
* There may be multiple good subnetworks in a network, not just the one that was planted.
* The graphs are a bit hard to read.
* I find the mix of pruning methods studied, which were designed with very different goals (pruning after training, pruning before training, finding strong lottery tickets), a bit confusing.

**The bottom line:** With all of that said, in my view, the paper asks good questions and provides an initial foothold that other researchers will be able to build on as we seek more general answers. This is similar to the contributions made by Zhou et al., which started the conversation on strong lottery tickets, and potentially even Frankle & Carbin, which kicked off the lottery ticket discussion but got many things wrong. Both papers were good first attempts at solving big problems, and both were highly influential despite their flaws. Similarly, even if this submission isn't perfect in every way, this is among the most important kinds of contributions that a paper can make. For that reason, I strongly recommend acceptance under the belief that this paper will help to foster a valuable conversation in the literature.

P.S. I really, truly, strongly beg the authors to redo their graphs following the style of some of the more user-friendly lottery ticket or pruning papers they have cited (e.g., Frankle et al., 2021). The graphs in this paper were really hard to parse. Really really really hard to parse. They're too small, the y-axis is often squished, gridlines would be helpful, the lines are overlapping in ways that are difficult to distinguish because the colors blend, etc. etc. This is quite possibly the biggest impediment I see to this paper's ability to have broader influence.
Decision: Accept (Poster)