Proving the Lottery Ticket Hypothesis for Convolutional Neural Networks
Authors: Arthur da Cunha
Emanuele Natale
Laurent Viennot
Venue: ICLR 2022 Poster (2022)
Keywords: lottery ticket hypothesis
convolutional neural network
network pruning
random subset sum
random neural network

Abstract: The lottery ticket hypothesis states that a randomly-initialized neural network contains a small subnetwork which, when trained in isolation, can compete with the performance of the original network. Recent theoretical works proved an even stronger version: every sufficiently overparameterized (dense) neural network contains a subnetwork that, even without training, achieves accuracy comparable to that of the trained large network. These works left as an open problem to extend the result to convolutional neural networks (CNNs).
In this work we provide such generalization by showing that, with high probability, it is possible to approximate any CNN by pruning a random CNN whose size is larger by a logarithmic factor.

Published as a conference paper at ICLR 2022
PROVING THE STRONG LOTTERY TICKET HYPOTHESIS FOR CONVOLUTIONAL NEURAL NETWORKS
Arthur C. W. da Cunha & Emanuele Natale
Inria Sophia Antipolis Sophia Antipolis, France farthur. www.aaaoooaoo..a raven-da---uunee wuw.ede-uuuuhammaaelleele iatauuull..atalleiiiii....f
Laurent Viennot
Inria Paris, IRIF Paris, France
lau rent. wiennoteiniia fr
ABSTRACT
The lottery ticket hypothesis states that a randomly-inittalized neural network con- tains a small subnetwork which, when trained in isolation, can compete with the performance of the original network. Recent theoretical works proved an even stronger version: every sufficiently overparameterized (dense) neural network contains subnetwork that, even without training, achieves accuracy comparable to that of the trained large network. These works left as an open problem to extend the result to convolutional neural networks (CNNs). In this work we provide such generalization by showing that, with high probability, it is possible to approximate any CNN by pruning random CNN whose size is larger by a logarithmie factor.
INTRODUCTION
Many impressive successes in machine learning are reached through neural network architectures with a huge number of trainable parameters. Consequently, substantial research in the field aims at reducing the size of such networks while maintaining good accuracy; e.g., for deployment in resource constrained devices (Yang et al. 2017).
A major empirical fact of such endeavour is the contrast between the initial model overparametriza- tion, which appears necessary for effective training, and the extent which the size of the resulting model can be reduced through compression techniques. Among the latter, praning methods appear as a mature and efficient way achieving significant compression, often without incurring any ac- curacy loss (Blalock et al. 2020). Recently, the aforementioned contrast between the initial and final number parameters has been addressed by the lottery ticket hypothesis (Frankle & Carbin (019)), LTH for short, which states that any randomly initialized network contains lottery tickets; that is, sparse subnetworks that can be trained just once and reach the performance of the fully-trained original network. This hypothesis was first verified experimentally. leveraging pruning methods to identify the lottery tickets (Frankle & Carbin 2019 Lee et al. 2019).
Ramanujan al. (2020) then proposed stronger version of the hypothesis, named strong lottery ticket hypothesis (SLTH) by |Pensia et al. (2020): it stipulates that a network with random weights contains, with high probability, sub-networks that can approximate any given sufficientlyssmallee neural network. In other words, sufficiently large and randomly initialized network that can be successfully trained for a task, could instead be suitably pruned to obtain network that, even with- out training, achieves good accuracy. Experimental support for this stronger version were reported by |Ramanujan et al. 2200);; Zhou et al. 2019); Wang et al. (020)), which find lottery tickets in range of architectures, including convolutional neural networks (CNNs). A first rigorous proof of the SLTH was given by Malach et al. (2000) for the case dense networks (i.e., consisting of fully connected layers). Pensia et al. (2020) and Orseau et al. (002)) successively improved this result by showing that logarithmic over pwe-paraamtrizzaionn is sufficient. Their results are also restricted to dense networks and they leave open problem extend it to CNNs.

---

Published as a conference paper at ICLR 2022
Our contributions. We extend and complete the proof of the SLTH (and thus, also, of the LTH), for classical network architectures which can combine convolutional and fully connected layers. More precisely, we prove that any CNN with given weights can be approximated by pruning CNN with random weights (random CNN for short), with the latter being larger than the former by a logarithmic factor. We also provide basic experiments showing that starting from a random CNN which is roughly 30 times larger than LeNet5, it is possible to compute in few hours pruning mask that allows to approximate the trained convolutional layers of LeNet5 with relative error 10 even when ignoring some hypothesis of our theoretical result. Our theoretical analysis follows the approach Malach et al. (2020) and make use of two layers to approximate one. We borrow from Pensia et al. (2020) the use of random subset sum (RSS) (Lueker) 1998) to approximate given weight via the sum of a subset of sample of random weights, and carefully design instances of RSS via combination of two convolutional layers. By controlling the error accumulated by each layer with Young's 's convolution inequality, we establish the following result.
Informal version of Theorem 1 Given E, ò > O, any CNN with & parameters and l layers, and kernels with & norm most 1, can be approximated within error g by pruning a random CNN with ( log min(r. parameters and 2 layers with probability at least 1 - 6.
kt
This result generalizes those by Pensia al. 20200) Orseau et al. (2020), and Malach et al. (2020) as dense layers can be regarded as convolutional layers where kernel and input sizes match.
Roadmap. After discussing related work in the next section, we state our theoretical results along- side high-level idea of the proofs. Successively, report our experimental results. Finally, in Section we provide detailed proof's of our statements.
1.1 RELATED WORK
Pruning methods are classical neural network compression strategies that date back to the 80s (Le- Cun et al., 1989b; Mozer & Smolensky 1988). We recommend the recent survey Blalock et al. (2020) for an overview of the current state of research on these techniques.
As for the lottery ticket hypothesis, Lange (2020) summarizes the progress on the topic until the results by Malach et al. (2020). In the following we briefly mention works which are not discussed in [Lange (2020). Cosentino et al. (2019) shows that lottery tickets can be adversarially trained, yielding sparse and robust neural networks. Soelen & Sheppard (2019) shows that lottery tickets are transferable, in the sense of showing remarkable accuracy for tasks other than the original one for new task allows lottery tickets to often achieve better generalization than models trained ad-hoc for the task. Yu et al. (2020) empirically supports that the LTH holds also in the context of reinforcement learning and natural language processing. Fischer & Burkholz (202I) extends works on the SLTH to accommodate biases in practical settings. Diffenderfer & Kailkhura (202I) shows that lottery tickets are robust to extreme quantization of the weights. Alladaoo & Torresani (202T) provides a method to train networks where each initial weight is restricted to few possible random values. An extreme case of the latter is to share only a single (random) value among all weights, and focus the training solely on finding the best architecture (Gaier & Ha 2019).
which they have been found. (Sabatelli et al. (2021) further shows that minimal retraining
Our work also relates to recent papers investigating properties of random CNNs, such as Ulyanov ct al. al. which observes that random CNNs already seem to capture some natural image statistics required for tasks such as de-noising and inpainting.
2 THEORETICAL RESULTS
We start by introducing some of our notation. The rest of it follows Goodfellow et al. (2016) with minor modifications, so we defer a full description to Section 4.1
Given n N. denote the set (1...., n by [n]. The symbol represents the convolution oper- ation, @ represents the clement-wise (Hadamard) product, and a represents ReLU activation func- tion. Finally, the notation ||-I]1 refers to the sum of the absolute values of each entry in tensor while
2

---

Published as a conference paper at ICLR 2022
Illlmmxx denotes the maximum norm: the maximum among the absolute value of each entry. Those are akin to vector norms and should not be confused with operator norms.
We restrict our setting to convolutional neural networks f: [0, DXDxco - DDDXX of the form f(X) = = o(K t- ....o( X)).
where K' E IR4. Xe,- and the convolutions have no bias and are suitably padded with zeros. The restrictions tensor sizes and the exclusion of bias term@ aim only
presentation.
Our initial goal is to approximate a convolution with a single kernel, as depicted Figure | using convolutions with (pruned) random kernels. We achieve this by the means of the structure presented in Figure using two convolutions with random tensors.
D
D
X
K
K X
Figure I: Schematics of the convolution between an input X E DxDex and kernel K E Rdxdxe resulting in x D matrix.
Lemma 1 asserts that, with high probability, we can prune this structure to approximate the output of convolution with any given kernel as long as the amount of random kernels is large enough.
D
D
D
D
d
X
U
U X
V
V (U=X
Figure 2: Schematics the use of two convolutions to approximate the operation depicted in Fig- ure The elements of the set = {U())..... U and are random tensors. Notice that the intermediate tensor U X has size D x D and yet the final output is D matrix.
Lemma (Single kernel). Let D,d, c, N. and e, C. R>0 where E Rdxxxxex, V e IR Rixixxx1, and S E (0,1]sime where the entries of U and V are iid. Unif([-1,11) random variables. Moreover, define the random CNN gi [0, [] 1|xxDxx DxD1 and its pruned version gs by
Cllog de
g(X) = V (U and gs (x) = V o ((U (U@S) SS)
Then, can choose conslant C independently from other parameters so that, with probability at axxxxxx with |||] 1, there exists a pruning mask S such that
least e, for all K E [-1, dxxxxxx dxdxexl
K x X 9s( <.
sup Xxxxx
Proof idea. We leverage the absence of negative entries in the input and an initial pruning of to bypass the ReLU non-linearity. This allows to virtually replace the operations in g by single
IIf biases present, the structures used in the proofs also them in RSS configuration. Thus the results he readily adapted by replacing the df terms by de +

---

Published as a conference paper at ICLR 2022
convolution with random kernel obtained by combining U and V. Each entry of this resulting kernel the sum of n random variables, where we can choose to include/exclude each term in the sum by choosing to keep/prune the relevant weights. We finish the proof by applying Theorem 2 to conclude that n variables suffice to approximate all entries, simultaneously. with enough precision ensure the thesis.
We now extend Lemma to an entire layer. As before, detailed proof is provided in Section 4.3
Lemma (Convolutional Layer). Let D, co, co,C1, C E N, and s, E Rs0, where n 2 Cc₁ log d'te U Rdxdxeex", V 1xxxxxxa, S E {0, 13siimi)) and T E {0, 1jsieei,, where the entries of and are i.dd Unif([-1,1] random variables. Finally, define the random CNN g: [0, D D x I DxDes and its prumed version (x) by
g(X) = V o(UxX) and IT. = * ( =))
Then, we can choose constant C independently from other parameters so that, with probability at least 1 - E, for all K E [-,,, 1]xxxxxxxxxxxxe Xc1 with ||K|| S 1, there exist masks S and T such that
sup x
K X (X]s(X)]lmal) <.
Proof Idea. The lemma follows by applying Lemma | to each kernel independently, that all of them are approximated by a factor of at most e/C1. Such approximation allows to apply the union bound so that the desired approximation holds simultancously for all e₁ output kernels with probability at least 1
O
Next, we extend Lemma from a single layer to the entire network, thus proving our main result. A detailed proof is given in Appendix
Theorem 1 (Convolutional Network). Let Co,, E N, and e, C E Ryo- For each i E
[G) let C4. 74 E N, where n4 2 Ce. log e--eiddee oft and 2 Rddxdixe--xx minte,of
2i
R plxIxn,xe. xe, 2 E {0, ] S²i E (0, ( where the entries LL i.dd Unif([-1, 1]) random variables and define the random 21-layer CNN g: [0, 1xxxxx DD Dxer and its pruned version Is1 !s!.....s² (X) by
28 are
((x) = L * oo(.-..(LL. X)) and 9s' !s! (X) = (L 1 o ol. [(L o S') * X]].
Finally, let F. be the class of functions from (0, 1 Dxxx0 R Dxcce such that, for each f E F
f(X) = K (KKK ..... oK' X)),
xxe where, for each i E [4]. K' E (-1, xex and |K $
Then, choose constant C independently from other parameters so that, with probability at least 1 - 8, the theffollwingg holds for every f E F.F;
inf WE ('
|| !s"..... .s....ss' Xxx
sup
max <.
Proof Idea. The proof leverages Lemma] in analogous way how the latter relied on Lemma I namely, we apply Lemma[bby requiring an approximation factor that guarantees, with sufficient probability, that suitable approximation is reached across all layers simultancously. The latter requirement is responsible for the factor which appears the logarithms of the dimensions each random tensor L.
2.1 DISCUSSION ON THEOREM
Size analysis. For each layer, we emulate a 4-D kernel K with size d, x G--xXc with two 4-D kernels and with size d, x x c-1 xn and 1x xxxx, respectively with n 2 Cc,, log 1oufee
min
Under the technical assumption G Odf for i [4]. the size of V is within constant factor
4

---

Published as a conference paper at ICLR 2022
kf of that of U, and the whole random network we prune has size Okklog min(e,8) ) where l is the size of the network we want to approximate. This technical assumption met for all classical convolutional networks used for image processing with a reasonably small constant in the big O notation. We come back on this assumption below.
Limitations. The properties of convolutional layers require stronger hypotheses in Theorem when compared with the results for dense AntersMMaacc et al. (2020) or Pensia et al. (2020). First, require non-negative inputs for all layers, however, since the output of the ReLU function is never negative, this restriction is only relevant for the input of the first layer. The mentioned works avoid this restriction by exploiting the identity a a(a) o to deal separately with the positive and negative entries. The fact that each entry of the output of a convolution is affected by potentially multiple input entries prevents from employing a similar strategy. Nonetheless, we remark that, while this is a relevant theoretical indication of the challenges imposed by the operation of convolution, in practice the inclusion of biases suffices to easily convert any CNN with a domain including negative values into an equivalent CNN that takes only non-negative inputs. Finally, the possibly multidimensional entries of convolutions also motivates the restriction on the norm of the target weight tensors in terms of the 1-norm.
Generalizations. For the sake of simplicity, we state and prove Theorem | in a restricted setting. It is worth remarking series of generalizations that can be obtained at the mere cost of making the proofs more technically involved. We defer a more complete treatment of such extensions to a journal version of this work. First, the proof could consider also other parameters, such as stride, padding, average pooling and other operations that can be seen as convolutions. Moreover, we could consider more general convolutions, not necessarily 2-D, operating on tensors of any sufficiently large dimension. In particular, it is not necessary to assume that V has size 1 x 1 x X q; in the above analysis. Using 5-D tensor with size d d x c-11 x (n/ca) X 6₁ for U, an appropriate convolution U would result in a D X D (n/c,) X tensor, and we could use a 1x1x (n/c:) x e; tensor for V without the need for the mask by performing in parallel e appropriate convolutions. Note that the size of V is then smaller than the size of U. The technical assumption used in the above size analysis thus not necessary to guarantee that logarithmic over-parametrization is sufficient. Finally, observe that that our results generalize to any probability distribution for the weights that contains b-scaled Unif([- a, al) for some constant a > 0 (in the sense of Definition 2 in Appendix C where the parameters and b only impact the constants in the theorem.
EXPERIMENTS
As networks with higher parameter count tend to be more robust to noise, we stick to the small CNN architecture used by Pensia et al.] (2020), namely, LeNet5 (LeCun et al. 1989a) with ReLU activations. We conduct our experiments by first training the network to 98.99% test accuracy on MNIST dataset (Lecun et al. 1998). To avoid well-known limitations of the MNIST dataset (in particular its large number of zero entries), we also trained it on the Fashion-MNIST dataset (Xiao) ett al. 2017) to 89.12% test accuracy. We adopted Kaiming Uniform (He et al. 2015) for weight initialization, a batch size of 64 and trained for 50 epochs using ADAM optimizer (Kingma & Baj 2015) with learning rate of 0,001, exponential decay of 0.9 and momentum estimate of 0.999, the default values in Flux.jl (Innes et al. 2018) machine learning library.
Once the network is trained we change its weights for a random subset sum approximation of them. More precisely, for each weight w we sample æ from Unif([-1, 1]") and use Gurobi optimization software (Gurobi Optimization, L.I.C. 2021) to solve the mixed-integer program
T
min @1 Se.....
w
Σ
04 24
s.t. a E 10 Vi Vie [n].
where n is the sample size. Solving this subset sum problem with = 30 for the 2572 parameters in the convolutional layers of LetNet takes around 1 hour on 32 cores of a Intel Xeon@ Gold 6240 CPU @ 2.60GHz.
Figure 3 shows the accuracy of the approximation for different sample sizes. We start to obtain good approximations (error smaller than 10-2) from sample sizes around 15-20. Also, when comparing
5

---

Published as a conference paper at ICLR 2022
maddmum weloot coror
maddmum wwi.he
22-
sample
Figure 3: Relative error of random subset sum approximation of the convolution weights of LeNet5 trained on MNIST (left) and on Fashion-MNIST (right). The error is given in logarithmic scale as the maximum distance between weight and its approximation for different sample sizes.
the weights obtained for MNIST and for Fashion-MNIST, we have better approximations for the smaller sample sizes for MNIST. We believe this is due to the fact that the training on Fashion- MNIST resulted filters with larger weights (up to a factor 2, roughly), since larger sample size is necessary to approximate larger interval of values (see Theorem 2
The high precision the approximation most weights leads to negligible change in the accuracy of the network. For this reason, we focus on studying the error at the output of the convolutional section of LeNet5, right before the flattening. Also, at this point the activation tensor has dimension 7 x 7 16 as opposed to the vector of size 10 at the end of LeNet5,
PER
maximun output unor
maximum cmor
12:7
sample Si2E
5omple size
Maximum relative output error for the convolutional portion of LeNet5 trained on MNIST (left) and Fashion-MNIST (right) for different sample sizes. The maximum computed over all images in the dataset.
Figure 4:
Figure shows the maximum relative error for all approximated outputs compared to original ones. The relative error of the output for an input image is computed as the maximum activation error divided by the maximum original activation (both maxima are taken over all x x 16 activations). Once again. MNIST leads to better precision for the smaller sample sizes. This can be explained by the fact that weights are better approximated in that range with MNIST as seen in Figure In both cases, we get relative error close to 10-3 with sample size 20, and even better with larger sample sizes. Within the settings of Theorem [ this corresponds to expanding the convolutional portion of the network by factor of, roughly, 30 if we take into account kernel sizes and number of channels. This high precision is achieved even though the trained weights do not satisfy the norm restrictions of Theorem Indeed, kernels obtained are quite high (from 50 to 15000 roughly for both datasets).
do not any explicit regularization, the 1 1-norms of the
TECHNICAL ANALYSIS
4.1 NOTATION AND CONVENTIONS
We employ the notation from Goodfellow et al. (016)) with minor adjustments. For self- containment, we detail below not only our adaptations but all the relevant notation inherited from the textbook.

---

Published as a conference paper at ICLR 2022
We identify the type of the objects with the font used for their symbols. This applies to scalars (e.g. z), to vectors (e.g. a) and its entries (c.g. 2;), to tensors (e.g. X) and its entries (e.g. x.), and sets (e.g. X). We denote slices of tensors by indexing it with colons. For example, the expression _.,,; represents 2-D slice of a 3-D) tensor. Finally, we refer to the axis of a 4-D tensors as rows, columns, channels, and kernels (a.k.a. filters), in this order
This work considers explicitly only 2-dimensional convolutions with multiple channels, multiple kernels and enough zero- saro-igdding to preserve the output size. However, as we discuss in Section 2.1 results can be generalized in many ways.
Definition 1 (Convolution). Given lensors K E IRdxdxe and X E DxDe, the 2-dimensional discrete convolution between K and X is the D matrix with entries given by
(K ()j.
Σ
K Xx-rt1s-5'tkk for i.j [D].
where X is suitably zero-padded. Similarly, i E Rexdxeoxes is a 4-dimensional tensor, we define K X as the x D C1 tensor with entries
(K X) x.
Ke.'' X1- for E [D] [e]]. X.
E
The output of convolution with a 4-D kernel can also be can be expressed in terms of the 3-D case using tensor slices. For instance, the equality above can be rephrased as
(K X) K K X for l [c]]-
4.2 SINGLE KERNEL APPROXIMATION (PROOF OF LEMMA
Our first goal is to bypass the non-linearity we can combine the two convolutions in g(X) * (UU= X) into a single one. Given that the activation function under consideration is the ReLU, it suffices to ensure that its imput has negative entry. Hence, prune all negative entries of U, obtaining the tensor U max (0, U}. where the maximum is applied entry-wise. Since, by hy- pothesis, the entries of the input X are non-negative, it follows that the entries of the tensor U X are also non-negative. Therefore,
V*o(U* X)
V
(U* X).
We now look the first convolution on the right side of Equation By Definition i
we have
VV (U+ X)
V1111.11 (U+ X)r,at
V1.1,111
Σ
Uti X--1t1,0522,
(V1,1.1 UtsueN) X X
t=1 A.ld
Σ VI.1. UTghet
Xx-
The equation above shows that performing V (U+ X) equivalent to performing single convo- lution between X and tensor L xddxxexx whose coordinates are given by
Lijk,1
VLL1 U
(2)
1=1
Goodfellow al. (016) different ordering.
7

---

Published as a conference paper at ICLR 2022
This reveals RSS configuration where we can choose to include/exclude each value V1,,1,111 K.K.k. in the sum by choosing to keep/prune U &.j.k.t" Since Equation continues to hold after further pruning U finish our proof by doing exactly that: we leverage Theorem 2 to ensure that, with high probability, we can solve this RSS problem for each entry of L to approximate the respective entry of K.
To see that we can apply Theorem in this setting, for E' > 0, 2,J E [d]. and l E [c]. denote by E.g. the event
1 3 3 [m]
Vi..o.1
Ut
< <E'}.
EES
We now use the RSS result, Lueker (1988 there exists constants a, such that
Corollary 3.3) (Theorem 2 in Appendix C to show that
V1,1,11 Unsnae) S bac
E
max
min mg
=El-n/32,m/s2
It is not hard to show that, since (V1.1,1)ssssn and (U (Usneesssn are ii.dd Unif([-1, 1]) random
variables, then the value of the density of (V1,1,11 Ut Ussenn is at least log on 1/2 1/2],
2
and, thus, it contains a log -scaled Unif([-1/2,1/2) (see Lemma in Appendix C for details).
In particular, setting X = V1.1..1 U we have that μ = E(xxso))
Jog < -1/16
and 14+ = [1 2 log2 > 1/16. Therefore, we can apply Theorem 2 with g 1/32:
8
there exist constants a, 6 > 0 such that the expected value of the [-n/32, n /2] subset-sum gap for (V1.1,..1 U Ussss is at most ac -b- That is,
bbn
E
max sel-n/322m/31 SCIn
min 2
Σ EEB
V1..
U Utiade) S ae bn
Assuming 2 32, Markov's inequality yields PP P(F....))))
S ae Setting e' = dāc and C =
: loga and supposing without loss of generality that e' <e the condition C log 1 implies
bn 2 2lloge' + log and -on E', and get
(Eissintt 2
E dec
Now define the simultaneous event E = Nisek Eiiihie'. above for i.j E [d], k E [c], we have
By union bound over the inequality
P P(E 24
2 1-
Finally, conditioning on E. .... it holds that
sup Ke|0.1juxaxIx1 SE( (iix x=(0.1]0xDxx
sup inf
K * X
V
[ O S)
X
(a)
sup inf sup
K X V
S) X
K
X
max
(
sup inf sup K
K
V
(U+
S)] X
S
1 sup inf sup
|K
- V (U+
5)
|X
max
K
x
sup inf |K
V (U
K
(c)
2 &e. - sup
inf
K
* (U S
K
s
(
d
E =E,
dc
8

---

Published as a conference paper at ICLR 2022
where (a) follows from Equation I (b) from the distributivity of the convolution operation, (c) from
Proposition 1 (d) from the fact that X E [0. 1)xxxx, (e) from the inequality ||>]|1 S m ø max for x E R" and (f) from the definition of E od?
4.3 CONVOLUTIONAL. LAYER APPROXIMATION (PROOF OF LEMMA 2
The general goal of this argument is to choose binary masks and so that (o a sufficiently close approximation of K X.
For E [cr] let (8) be K's (-th kernel. That is,
K....e-
Notice that K X is the concatenation along the third dimension of each K() * X, i.e, for l E [c]]
we have (K X)...e K( X.
We fix T a priori to be the block diagonal matrix with entries given by BI, = (e- for E [n], & E [cı], where n' n//1. the rest of the proof, we show how to choose S, based on
and V, in order to approximate the kernels k(
We perform the approximation of each K (*) using different sections of the tensors. To this end, for l [ct], let
Uº (:::((t-hn''ttttr'
S' S (e::(((1)n'<tstte
and v V V=::((-11nn<tgttr
As we did in the proof of Lemmal 1 we perform an initial pruning on U by restricting S to the space of masks that prune all of its negative entries. This allows us ignore the ReLU activation and conclude that
((V + B)
[IU 6 S) X)
Σ VLLI
O S).jkk.t X
wE(d]Akll
( * I(U @ )S') *)*x ris
V * *oU @ S * x)
For f E [c]] and gl 0, denote by Eg,e' the event
( sup kk] ('iiiiu x
K( x V vo (V) *X] max <o).
inf
sup
Consider the event Fejcs = 0g Fit.//c Since n' =nce = C log dooo for each E [e]], Lemma e/c ensures that (P(E,,c/a) 2 -21--/1 E/c1, which implies P(Ec//)) 1-E.
Finally, conditioning on Ezje; and using the fact that the output channels of convolutional layer are calculated independently, we conclude
inf xe|-1,1] x Se (0. ) X xx
sup
K (VX-(VoT) I S) x
max
Te (0.1 (0,1) (V)
<
inf Ke[-1.1|xxxxppep Sc (t) x
sup
sup
K x - @ B)OB o U 6 S) X
|K()) * X V * R S X
maxx
sup
inf
sup
/E(e)) K S (0 x Xx
max
6.

---

Published as a conference paper at ICLR 2022
5 REPRODUCIBILITY STATEMENT
We made our best effort to describe in detail all the relevant parameters for Section 3 took care to initialize the random number generator not only for Julia but also for Gurobi, so that the experiments can be reproduced using the source code available at https:: /t/itttii hiu..b..... com/ ArthurWalraven/ heaeee//enslti The latter also include a BSON serialized version of our trained models and solutions to RSS instances, that can readily be imported with Julia.
We also
ACKNOWLEDGMENTS
This work has been supported by the AID INRIA-DGA agreement 22199550072.. The authors are grateful to the OPAL, infrastructure from Université Côte d' Azur for providing resources and support.
REFERENCES
Maxwell Mbabilla Aladago and Lorenzo Torresani. Slot machines: Discovering winning combina- tions of random weights in neural networks. In Marina Meila and Tong Zhang (eds.). Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 163-174, PMLR, 2021. URL
w.ppess/v133///// alaaaaaaaagaaaa html
Davis W. Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John V. Guttag. What the state of neural network pruning? In Inderjit S. Dhillon, Dimitris S. Papailiopoulos, and Vivienne Sze (eds.), Proceedings of Machine Learning and Systems 2020, MLSys 2020, Austin, TX, USA, mwsys. org/book/
March 2-4, 2020. mlsys.org, 2020. URL 296. pdf
Justin Cosentino, Federico Zaiter, Dan Pei, and Jun Zhu. The search for sparse, robust neural networks. CoRR, abs/1912.00238,, 2019. /ttp::::://ax wwg. 1tt.hpcpp///axx..ooor//////1.211 02386
James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruming A randomly weighted network. In 9th International Confer- ence on Learning Representations, ICLR 2021, Viriual Event, Austria, May 3-7, 2021. OpenRe- net. fttt/foorm?i10 batorrmmiddu_mmmeee 0b9iv
view.net, 2021. Uttstt
Jonas Fischer and Rebekka Burkholz. Towards strong pruning for lottery tickets with non-zero 11150
biases. CoRR, abs/21 150, 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neu- ral networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA. May 6-9, 2019. OpenReview.net, 2019. URL htttps:/
lnt//fo fort/forum?? i d== J1 7
Adam Gaier and David Ha. Weight agnostic neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- fion P Processing Systems 2019, NewrlPS 2019, December 14, 2019, Vancouver, BC, Canada, pp_ 5365 5379, 2019. URL https: http:::::/ppocceediigg nwwrpps......................... http://www...........o.///////// 4
wtw.:stbffi---sttttctttte html
Abst
lan J. Goodfellow. Yoshua Bengio, and Aaron C. Courville. Deep Learning. putation and machine learning. MIT Press, 2016. ISBN 978-0-262-03561-3.
Adaptive com- URL http:
/www www.deepplerniingboo... org/
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https: /wwww.
gurobi com
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpass- ing human- performance on imagenet classification. In 2015 IEEE International Confer- ence Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pp. 1026-1034.
10

---

Published as a conference paper at ICLR 2022
IEEE Computer Society, 2015, doi: 10.1109//0C.22015..2.. URL https:://o...co//////
Michael Innes, Elliot Saba, Keno Fischer, Dhairya Gandhi, Marco Concetto Rudilosso, Neethu Mariya Joy, Tejan Karmali, Avik Pal, and Viral Shah. Fashionable modelling with flux.
CoRR, abs/181 11 1.01457, 2018. URLhttps: //tp//aaavvv//.////a/eee/..wev.a /ttttp::///xxx.ooog/abb///////// wtt.aa////11111//...11 01457
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.). 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:
7/ www.vv.orgabss///oo /4112 6980
Robert Tjarko Lange. The lottery ticket hypothesis: A survey. https://ooberttongeggiiieee
onthae/poss2200ooollooeereeeeeep 2020. URL bttps::/roberttiinm cithab..cc//ossss//200//////ooo0
hypothhssss
Y. Lecun, L. Bottou, Y. Bengio, and
Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(1 (6((1)):228-23244 1998. doi: 10.1109/5.726791 URL
Bttps://ieeexp:
leee org/ wrtg///cccmeet/2277911
Yann LeCun, Bernhard E. Boser, John S. Denker, Donnie Henderson, Richard E. Howard, Wayne E. Hubbard, and Lawrence D. Jackel. Backpropagation applied handwritten zip code recogmition. Neural Comput., 1(4):541-551 1989a. doi: 10.1162/neco 198te 1.4.541. URL hhttps://don
oxg/10.1162/nie www.://eec.... 1989. 4411
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. David S. Touret- zky (ed.), Advances in Neural Information Processing Systems 2, [NIPS Conference, Den- ver, Colorado, USA, November 27-30, 1989], pp- 598-605. Morgan Kaufmann, 1989b. URL
attp::/ppt http::/pppprrs...i. wtwppppeeepppppp//ppppppppaapeee 250 opt
httppppper/oo-opppma---e---e-eee iwai-mraia-------eaeaaaa damage)
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. Torr. Snip: single-shot network pruning based connection sensitivity. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:
/poenreview. ner/ffoum?? i d=B1 VZ
George Lueker. Exponentially small bounds on the expected optimum of the partition and subset sum problems. Random Struct. Algorithms, 12(1):51-62, 1998. doi: 10. (SICC) 018-22488819881111 1011::/::1:::::AAAAAAAAAEE 1002/(SIC1) 1098 2418 (199801 2T1.://5SS.111122222220011111111
URL htt.h:t/p/:/d.. orr
:AID -SAIADDRRS333..00
Eran Malach, Gilad Yehudai, Shai Shwarz,, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruming is all you need. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 6682-6691. PMLR, 2020. htt:: /tthttp: http:::///pocceenng.....
mlr. wwwps/swssii....p. wttps///11//aaaaetteoeoaa .hmmmlma...mmmmm.mmmmmmmm
Michael Mozer and Paul Smolensky. Skeletonization: technique for trimming the fat from a network via relevance assessment. In David S. Touretzky (ed.), Advances Neural Informa- tion Processing Systems 1, (NIPS Conference, Denver, Colorado, USA, 1988J, pp. 107-115. Morgan Kaufmann, 1988. URL https:: /ttpps:/pproeeedng. hww.r/eeeerrpp... wwtppppppppppeee//eeeeppppppp pdf
F1le/07elcd7der 9a1 18800011011101111111000031331333
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.). Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual, 2020. URL https: http::/pppoceedd...neeeee. 01144147077995550 3tw.07//5500.0e111eeeeeee2...2.0 2tw.:a00b2220007--baaaaaaa- -bst html
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris S. Papailiopou- los. Optimal lottery tickets via subset sum: Logarithmic wverpparamtterizzatonn is suffi- cient. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and

---

Published as a conference paper at ICLR 2022
Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. 1b742ae21 f 4673444466222226222--43333
www.aaip.....pppppeeeeee cc/paper/2020/aaa.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden a randomly weighted neural network? 2020 IEEE/CVF
Conference Computer Vision and Pattemn Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 11890-11899. Computer Vision Foundation / IEEE, 2020.
doi: N0.109//CVP422000222200. 200.4442000020001119...
URL htttps://openaccesss wwwcthee...cccco comm
content_ _Cptt___PP_____ RtI___CCCR________ 20002222202mm111 (tt200/htm///aamaaaaa Raammmmmmaaaaaaa jawwhaattaaaaaaaaaaaaaaaaaaa Schats_Hiddees in in_ Randomly.
Weighted Neural Network CVPR 2020 paper.
Matthia Sabatelli, Mike Kestemont, and Pierre Geurts. On the transferability of winning tick- in non-natural image datasets. In Giovanni Maria Farinella, Petia Radeva, José Braz, and Kadi Bouatouch (eds.), Proceedings of the 16th International Joint Conference on Computer Vision, Imaging and Computer Gruphics Theory and Applications, VISIGRAPP 2021, Volume 5: VISAPP, Online Streaming, February 8-10, 2021, pp. 59-69. SCITEPRESS, 2021. doi: 10.52200011016330599000000 URL /KLL/ttss///oii http:///oo..rgg1/// 10. T0w.://///00000000052000000
Ryan Van Soelen and John W. Sheppard. Using winning lottery tickets in transfer learning for convolutional neural networks. In International Joint Conference Neural Networks. IJCNN 2019 Budapest, Hungary, July 14-19, 2019, pp. 1-8. IEEE, 2019. doi: 10.1109/UNN..2199 8852405. URL htt.h:ttp:/ddet org 1109/1100CCCM 2019 8852405
Dmitry Ulyanov, Andrea Vedaldi, and Victor S. Lempitsky, Deep image prior. Int. J. Comput. Vis., BRLhhtpss: //to///oii org/10.
128(7):1867-1888, 2020. doi:
Yulong Wang, Xiaolu Zhang, Lingxi Xie, Jun Zhou, Hang Su, Bo Zhang, and Xiaolin Hu. Pruning from scratch. In The Chirty-Fourdh AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 11273-12228 AAAI Press, 2020. BtLLttts:/// /estts://aaai... .org/ о tss/indes ae//inex.
AAAI htwplexxppp/A.att/tttiiieeeeeeee
6910
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. CoRR, abs//108.00747, 2017. URL httt::tttt///iil org/
abs 1100/100000 07747
Tien-Ju Yang, Yu-Hsin Chen, and Vivienne Sze. Designing energy-efficient convolutional neural networks using energy-aware pruning. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 6071-6079, IEEE Computer Society, 2017. doi: 10. 10.1109/CPR.2217..66 URL https: doi orw. 110./CVPR. 12017. 643
Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S. Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htttps:://peerreieeett net www.:/eotottddssileeien.. 8
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Ze- ros, signs, and the supermask. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Buuc Emily B. Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3592-3660 3602, 2019. URL ht o
12

---

Published as a conference paper at ICLR 2022
A BOUND ON THE NORM OF A CONVOLUTION
The following proposition can be seen as special case of Young's Convolution Inequality for func- tions over Z" where the norms in the inequality the & and & norms.
Proposition 1 (Tensor Convolution Inequality). Given K E RRxxdxaxxe and X E DDDxx we have
K X max S
|K|| ||
max..
Proof. We have
K X|| max
<
max P.
E
Ke.gi -410
V.y' e.j'Eld,
< max
|K sr |||||
Inax
P
< max k.3
Σ KK meel |
max
S max
|K|] [X|
|K |
max.
B CNN APPROXIMATION (PROOF OF THEOREM 1
Since Lemma) provide bounds in termss of the output of a layer, the study of the propagation of this emoor through the network is mostly independent of the layer type. Hence, the next proof follows the structure of Pensia et al. [2020] Theorem 1), where our LemmaaJassumes the role of their Lemma 3, and where we leverage our Proposition I inn order to address the problem of bounding the maximum norm of convolution.
Proof (of Theorem 7 For the sake of brevity, in the proof we denote the max-norm simply by ||-I]- Let X be the input of the i-th layer of the network f. Thus,
1. = X.
2. x oK'' * X') for SisE- and
3. s(X) = K2 X
By applying Lemma
to each layer, we choose masks 2 and 2
so that
sup x
K' X (L 2:
2i
a[(L
2i-1 c S 2i 12 x
<
E
(3)
2
with probability at least
28
Since the ReLU function is 1 1-Lipschitz with respect to the max norm, the above event implies the following for all i 1]:
sup
[K' * X) a[(L 2: @ S [[(L 21-1 o 22i-1 *
(4)
2
By union bound, with probability 1 Equation 3 and Equation 4 hold for all layers simultane- ously. In the rest of the proof, we implicitly condition on the latter event.
For any fixed function f. let g be the pruned network constructed layer-wise, by pruming with binary masks which satisfy Equation 3 and Equation 4 Let these pruned tensors be L' and let X be the input to the (2i 1) layer of g.
We note that x satisfies the the recurrence relation
13

---

Published as a conference paper at ICLR 2022
1. X = X.
2. X i+1 = o(L 24
* *o(L +oLL 21-1 * x') for forl
Because |XX|| S 1, Equation implies that ||
|1
S
(1+
1-1
To see this, note that Equation
27
implies, for 1 S S (- 1,
x
X i+1
E
X
x
28
thus
llo( x')
x
||
X
||-
2
By the reverse triangle inequality, the last inequality implies
X
+
lo(
x
28
XX
+ JK x II
$
X
|| +
|K |1 |X
28
X || + |X
28
(1
+
E
| ||.
2
Applying this incquality recursively, get that || || < [1+ 1/)
for 1 airlise-1 This allows
us bound the error between X' and X" For 1 S i 5 1, we have
X
x #+
= (K * x*) - [L 2i
* (L 21-1
* x )]
< (Ko(K' * x*) - oK' * x Il + llo(K'
x
o(L" 2i [[ 2
x II
*
K |X x + llo(K' x a( 22 =o(L 2i-1
x xI))
x X'| + ||oK'
x))
a(L
aL 2i-1
x
||
e e x x || + (1 +
(5)
28
28
where for the last inequality we use Equation
3 Unrolling Equation
we get
E i-1 E
x'
1 +
28
28
1=1
14

---

Published as a conference paper at ICLR 2022
Finally, this last inequality leads, with probability at least to
K X L 22
t 2
( g(xil
X ||
K X
K
IK
x
L 28
ooL
28-1
X
K |X x11 IIK
x
LL
_
* o(L 28-1
x x3)11
X
x"1 + iK"
* x
28
L(L
28-1
x)) ||
X
x11 + (1
8-1
2
2
4-1
8
&
+ (1
+
28
28
2
20
1-1
8) 28
< // e,
where the last inequality holds because < 1.
Replacing e in this proof with min(e, 8) concludes the proof of the theorem.
C RANDOM SUBSET-SUn THEOREM
For the sake of completeness, in this section we recall a result by Lueker (1988 together with the necessary definitions.
Definition 2. Given two positive constants and b, we say that a distribution with density f contains b-scaled Unif([-a,d) distribution if for each [-a,a] holds f(z) b. We simply say that distribution F contains uniform distribution if there exist positive constants a and b such that F contains a b-scaled Unif([-a,d) aa))) distribution.
The following is weaker version of Corollary in the Appendix Pensia al. (2020).
Lemma 3. Let X1 and X2 be two independent random variables following Unif([-1, 1]) distri-
bution. Then X1 X2 contains log scaled Unif([ } 21) distribution.
2
We say that is ty-subeetsummapppoiinate with S = {XI..... ".)....,) if there exists subset I, S [n] s.t. Eier, X; - 2| S 2np.
Definition 3. The (a, bj-subset-sum gap of S (X....., is the smallest value of v) such that each E [a, 6). can be pyyssubbettum-pppoommmatt with S.
Theorem (Corollary 3.3 in Lucker 1998)). Let S (X Xx) } be i.i.d. bounded random variables and & > O any constant. Suppose that the distribution of X1 contains a uniform distribu- tion. Let _ E E[1xgoX] 1+ Exxx20 pabs E||X]]= = p+ p__. The expected value of the [p__ + n) (14 - SJnj-subbs--sum gap of S is exponentially small with respect to n.
15


Reviews:
[{"review_id": "y59e6SOj2ut", "reviewer": "Reviewer_DkZV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ Convolutional layers are a frequently used building block in lottery ticket pruning. Related theoretical results have the potential to explain the empirical success in this area and derive conditions that enable pruning.\n+ The paper is well written and explains all steps carefully.\n\nWeaknesses:\n- The proof only applies to positive inputs. This is a significant limitation, since neural ReLU networks can often be only successfully trained if the input is standardised and thus transformed to a range [-a,a]^n for a > 0. \n- The parameter initialisation is unrealistic (iid from Unif([-1,1])) and does therefore not reflect the standard setting, in which pruning is conducted or neural networks are trained.\n- The proof ideas are not novel. They main steps follow the work by Pensia et al. for fully connected layers with the simplification that only positive inputs are considered.\n- The purpose of the experiments is unclear. It has been shown before that the subset sum approximation can be solved with roughly n=30 samples per parameter. This is not a new insight.\nNo neural networks are trained or actually pruned in the process. Why wouldn't the authors at least use the pruning algorithm edge-popup to show that they can approximate a target network?\nFurthermore, why don't the authors report at least the test accuracy of the final lottery ticket to show that the approximation error of the complete pruned network is not too large and that their parameter-wise approximation error is not too high?\n(The answer is probably that the proof does apply to a setting (i.e. parameter initialisation and positive inputs), in which edge-popup or any other gradient based algorithm would have a chance to find lottery tickets.)\n\nPoints of minor critique and open questions:\n- How much larger is the initial large network than the target network in the experiments? The \n- Why are the experiments restricted to only these small datasets (MNIST and Fashion-MNIST)? As no neural network needs to be trained, there is no strong computational overhead associated with experiments on more realistic image classification data.\n- The proof is restricted to ReLU activation functions.\n- The proof only applies to 2d convolutions. Extensions are reserved for a journal version.\n", "summary_of_the_paper": "The lottery ticket hypothesis is proven for 2-dimensional convolutional network layers and positive inputs. It is shown that a given convolutional neural network can be approximated by pruning a randomly initialised larger network of two times the depth of the target network and width that is larger by a logarithmic factor.\n", "summary_of_the_review": "Because of the lack of novel theoretical ideas and the fact that the proofs are limited to positive inputs and an unrealistic parameter initialisation approach, I recommend that the paper is not accepted for publication at ICLR at this stage.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "r-hdg2nIJa", "reviewer": "Reviewer_7cVT", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper proves the STLH for convolutional neural networks (CNNs). The existing papers have all focused on proving the SLTH for fully connected networks, so this paper fills the gap by proving that SLTH also holds for convolutional networks. The overparameterization required is logarithmic in the approximation error and the network depth and number of parameters, which matches the existing results for fully connected networks by Pensia et al. (2020). The importance of this result is that this proves that (sufficiently large) randomly initialized CNNs can be 'trained' solely by pruning, without actually updating the weights of the CNN.\n\nThe proof technique and construction uses the Subset Sum approach, similar to Pensia et al. (2020), and overall the paper is well written.\n\nI have the following questions:\n1. It is not clear to me why the negative input situation cannot be handled similar to prior work. Even if the same kernel is applied to multiple inputs, as long as the kernel is well approximated, the outputs will also be well approximated, respectively for each input. Could the authors please provide some more explanation or an example?\n\n2. The theorem and lemma statements say \"... we can choose constant $C$ independently from other parameters ...\". Does this mean that $C$ is a universal constant?\n\nTypos:\nIn the Limitations paragraph on page 5, it should be $a=\\sigma(a)-\\sigma(-a)$ instead of $a=\\sigma(a)-\\sigma(a)$.", "summary_of_the_paper": "The Strong Lottery Ticket Hypothesis (SLTH) says that any (sufficiently large) randomly initialized network can be pruned to obtain a network which performs well on a given task. This paper proves the Strong Lottery Ticket Hypothesis for convolutional neural networks by showing that given a target convolutional network, a logarithmically wider and twice deeper randomly initialized network can be pruned to approximate it. ", "summary_of_the_review": "The paper fills an important gap in existing research by proving that the Strong Lottery Ticket Hypothesis holds for Convolutional Neural Networks with only logarithmic overparameterization. However, the proof and construction is very similar to that in Malach et al. (2020) and Pensia et al. (2020), and hence the technical novelty in terms of proof techniques could be considered incremental.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lPc967uWZ-C0", "reviewer": "Reviewer_ifdf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is an extension of previous theoretical results on SLTH from fully connected layers to convolutional layers. The proving technique is similar to that used in Malach et al. (2020) and Pensia et al. (2020). While I am a LTH practitioner, I am not very familiar with LTH and SLTH theory and hence I am not sure how significant the technical contribution it is to extend the theoretical analysis from Malach et al. (2020) and Pensia et al. (2020) and whether it suffices to reach the bar of this venue.\n\nThe paper is well written and easy to follow. I roughly went through the mathematical proofs and found no issue. The main theorem is well supported by the empirical experiments.", "summary_of_the_paper": "This paper proves for the convolutional neural networks (CNNs) the strong Lottery Ticket Hypothesis, which previously is brought out based on empirical findings that a substantially overparameterized random neural network (with fully connected layers or convolutional layers) can be pruned to match the performance of a well-trained smaller network, even without training the remaining parameters. The main theorem states that a CNN with any given weights can be approximated well with high probability with a larger CNN with a doubled number of layers and a logarithmic number of parameters, and a proper pruning mask on random weights.", "summary_of_the_review": "Overall, this work fills the gap between the empirical success of SLTH in CNNs and the lack of theoretical interpretation. However, the review is not sure if the technical contribution is significant enough compared to previous theoretical work on neural networks with fully connected layers.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "8vAq-9NCyr", "reviewer": "Reviewer_dycZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "To begin with, I appreciate the efforts made by the authors that can help people to understand the mechanism behind the LTH. I am not an expert on theory nor random subset sum, but I can grasp some sense of the proof after reading the paper. However, there is still something that confuses me and I hope the authors can help me figure them out: Given a neural network, does the authors' theorem suggest that we need to use a pruned network of two times larger before we can approximate the real output of the original one? Theorem 1 seems to indicate that a pruned neural network of depth 2l approximates the output of f, whose depth is only l. In practice, such approximation can be done by the same architecture (same depth). There is a similar question for the number of parameters, whose bound seems to be controlled by the precision of approximation. I am not sure if this is nitpicking, but they do confuse me when I try to connect this theorem with LTH.\n\nMinor problems:\n- Figure 2, V * U * X should be V * (U * X) I suppose?\n- In Lemma 1, g(X) was defined but never used afterward. The same for Lemma 2.\n- Assumptions are too strong as indicated by the authors. \n", "summary_of_the_paper": "The authors provide theoretical analysis on the lottery ticket hypothesis for convolutional neural networks. The techniques of the random subset sum are used to prove theorems. The authors start with introducing the case of a single convolutional kernel and then generalize to the case of the whole convolutional neural networks. By specifying multiple constraints and assumptions on the models' parameters and inputs, the error between the approximated and the true convolution results can be limited to a small number. \n", "summary_of_the_review": "My score only indicates the initial opinion and I am willing to change my score if the authors can address my concern. Currently, I cannot clearly see the connection between the theorems and the LTH, so I would give a score of 5 at this time. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents interesting new results for pruning random convolutional networks to approximate a target function. It follows a recent line of work in the topic of pruning by learning. The results are novel, and the techniques interesting. There are some technical issues that are easy to fix within the camera ready timeline (see comments of reviewers below). I would also suggest refining the title of the paper: the lottery ticket hypothesis has an algorithmic component too, which clearly is not covered by existence results.
Decision: Accept (Poster)