Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
Authors: Arthur da Cunha
Francesco D'Amore
Emanuele Natale
Venue: NeurIPS 2023 poster (2023)
Keywords: lottery ticket hypothesis
convolutional neural network
network pruning
structured pruning
random subset sum

Abstract: The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised neural networks likely contain subnetworks that perform well without any training. Although unstructured pruning has been extensively studied in this context, its structured counterpart, which can deliver significant computational and memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the limitations of the underlying mathematical tools used in formal analyses of the SLTH.

In this paper, we overcome these limitations: we leverage recent advances in the multidimensional generalisation of the Random Subset-Sum Problem and obtain a variant that admits the stochastic dependencies that arise when addressing structured pruning in the SLTH. We apply this result to prove, for a wide class of random Convolutional Neural Networks, the existence of structured subnetworks that can approximate any sufficiently smaller network.

This result provides the first sub-exponential bound around the SLTH for structured pruning, opening up new avenues for further research on the hypothesis and contributing to the understanding of the role of over-parameterization in deep learning.

Polynomially Over-Parameterizet Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
Arthur da Cunha Université Côte d' Azur, Inria, CNRS, I3S
Francesco d' d'Amore
Aalto University
Aarhus University Aarhus, Denmark dacθcs au dk
Bocconi University Espoo, Finland
francesco damoredaaltooo
Emanuele Natale
Université Côte Azur, Inria, CNRS, I3S Sophia Antipolis, France emanuele. natale@inria
Abstract
The Strong Lottery Ticket Hypothesis (SLTH) states that mandooly-initiaiise neural networks likely contain subnetworks that perform well without any training. Although unstructured pruning has been extensively studied in this context, its structured counterpart, which can deliver significant computational and memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the limitations of the underlying mathematical tools used in formal analyses of the SLTH. In this paper, we overcome these limitations: we leverage recent advances in the multidimensional generalisation of the Random Subset-Sum Problem and obtain variant that admits the stochastic dependencies that arise when addressing structured pruning in the SLTH. We apply this result to prove, for wide class of random Convolutional Neural Networks, the existence of structured subnetworks that can approximate any sufficiently smaller network.
This result provides the first sub-ext nub-exponential bound around the SLTH for structured pruning, opening up new avenues for further research on the hypothesis and contributing the understanding of the role of over-parameterizzaionn in deep learning.
1 Introduction
Much of the success of deep learning techniques relies on extreme parametrrizatonnnn [Zhang et al., 2017, 2021, Novak al., 2018, Brutzkus al., 2018, Du al., 2019, Kaplan et al., 2020]. While such excess of parameters has allowed neural networks to become the state of the art many tasks, the associated computational cost limits both the progress of those techniques and their deployment in real-world applications. This limitation motivated the development methods for reducing the number of parameters of neural networks; both in the past [Reed, 1993] and in the present [Blalock et al., 2020, Hoefler et al., 2021].
Although pruning methods have traditionally targeted reducing the size of networks for inference purposes, recent works have indicated that they can also be used to reduce parameter counts during training
initialisation without sacrificing model accuracy. In particular, Frankle and Carbin [2019] proposed the Lottery Ticket Hypothesis (LTH), which conjectures that sandomly-intiallee
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Figure 1: Illustration of neuron pruning. The left side shows the effect of pruning of neurons in the weight- matrix of a fully-connected layer. The rows in white correspond to neurons pruned in the associated layer while the columns in white represent the effect of removing neurons from the previous layers. On the right, we allude to the possibility of collapsing the pruned matrix into a smaller, dense one.
networks contain sparse subnetworks that can be trained and reach the performance of the fully- trained original network. Empirical investigations on the LTH [Zhou et al., 2019, Ramanujan et al., 2020, Wang et al., 2020] pointed towards an more striking phenomenon: the existence of subnetworks that perform well without any training. This conjecture was named the Strong Lottery Ticket Hypothesis (SLTH) by Pensia al. [2020].
While the SLTH has been proved for many different classes of neural networks (see Section 2), those works are restricted to unstructured pruning, where the subnetworks are obtained by freely removing individual parameters from the original network. However, this lack of structure can significantly reduce the gains that sparsity can bring, both in terms of memory and computational efficiency. The possibility of removing parameters at arbitrary points of the network implies the need to store the indices of the remaining non-zero parameters, which can become significant overhead with its own research challenges [Pooch and Nieder, 1973]. Moreover, the theoretical computational gains of unstructured sparsity can also be difficult to realise in standard hardware, which is optimised for dense operations. Most notably, the irregularity of the memory access patterns can lead both data and instruction cache misses, significantly reducing the performance of the pruned network.
The limitations of parameter-level pruning have motivated extensive research on structured pruning. which constrain the sparsity patterns to reduce the complexity of parameter indexation and, more generally, to make the processing the pruned network more efficient. A simple example of structured pruning is neuron pruning of fully-connected layers: deletions in the weight matrix are constrained to the level of whole rows/columns. As illustrated by Figure 1, pruning under this constraint produces smaller network that is still dense, directly reducing the computational costs without any need for extra memory to store indices. Similarly, deleting entire filters in Convolutional Neural Networks (CNNs) [Polyak and Wolf, 2015] or "heads" in attention- based architectures [Michel et al., 2019] also produces direct reductions in computational costs.
It is important to note that structured pruning is a restriction of unstructured pruning so, theoretically, the former is bound perform at most as well as the latter. For example, by deleting whole neurons one can remove about 70% of the weights in dense networks without significantly affecting accuracy, while through unstructured pruning one can usually reach 95% sparsity without accuracy loss [Alvarez and Salzmann, 2016, Liu et al., 2019]. In practice, however, the computational advantage of structured pruning can offset this difference: a suitably structured sparse network can be more efficient than an sparser one that lacks structure. This trade-off between sparsity and actual efficiency has motivated the study of less coarse sparsity patterns since weaker structural constraints such as strided sparsity [Anwar et al., 2017] (Figure 2b) or block sparsity [Siswanto, 2021] (Figure 2c) are already sufficient to deliver the bulk of the computational gains that structured can offer.
Despite its benefits, structured pruning has received little attention in the context of the SLTH. In fact, the work that first proved a version of the SLTH, Malach et al. [2020], has remained the only one to study this scenario, to the best of our knowledge. Moreover, it brings a negative result: the authors prove that removing neurons from a randomly-initialised shallow neural network (a single hidden layer) is equivalent to the random features model (c.g., Rahimi and Recht [2007, 2008]),

---

Unstructured sparsity
Structured sparsity
(a) No pattern.
(b) Strided pattern.
(c) Block pattern.
Figure 2: Examples of different pruning patterns.
which cannot efficiently approximate even single ReLU neuron [Ychudai and Shamir, 2019]. As most proof's around the SLTH involve pruning shallow random network build the desired approximations, those results show that the SLTH can be challenging to tackle when restricted to neuron pruning.
In addition, we believe that factor hindering progress toward structured versions the SLTH more generally is limitation of result underlying almost all of the theoretical works the SLTH: theorem by Lueker on the Random Subset-Sum Problem (RSSP).
Theorem 1 ([Lueker, 1998, Da Cunha et al., 2023]). Let , Xn be independent uniform random variables over [-1, 1]. and let (0, 1/3). There exists universal constant C' >> 0 such that, if n 2 C' ('og))))),, then, with probability at least E, for all E [-1, 1] there exists S S [n]] for which
Σ X S. SE.
In general terms, the theorem states that given a rather small number of random variables, there is high probability that any target value within interval of interest be approximated by of subset the random variables. An important remark is that even though Theorem is stated in terms of uniform random variables, it is not hard to extend
wide class of distributions."
While Theorem closely matches the setup of the SLTH, only concerns individual random variables and directly applying to entire random structures, needed when considering structured pruning, would require an exponential number of random variables. The recent works by Borst al. [2022], Becchetti et al. [2022] reduced this gap by proving multidimensional versions of Theorem 1. Still, the intricate manipulation of the network parameters in proofs around the SLTH imposes restrictions that are not covered by those results.
Contributions
In this work, we overcome those obstacles and prove that random networks wide class of CNNs likely contain structured subnetworks that approximate any sufficiently smaller CNN. To the best of our knowledge, our results provide the first sub-exponential bounds around the SLTH for structured pruning of deep neural networks of any kind. More precisely,
We prove a multidimensional version Theorem that is robust to some dependencies between coordinates, which is crucial for structured pruning (Theorem 5);
We leverage this result and, by combining two types of structured sparsity (block and neu- ron/filter sparsity), we show that, with high probability and for a wide class of architectures, polynomially werrparamettrizzd random networks can be pruned in structured manner to approximate any target network (Theorem 2);
In random features model, one can only train last layer the network.
Diittributions whose probability density function f satisties f(x) 2 6 for all x [-a, a). for some constants 6 0 (see Lucker [1998, Corollary 3.3]).

---

Our results cover CNNs, which generalise fully culne-connected networks as well as many layer types commonly used in modern architectures, such as pooling and normalisation layers; Additionally, our pruning scheme focuses on filter pruning, which, like neuron pruning, allows for a direct reduction of the size and computational cost relative to the original CNN.
2
Related Work
SLTH Put roughly, research on the SLTH revolves around the following question:
Question. Given an error margin > and a target neural network ftarget. how large must an architecture frandom be to ensure that, with high probability the sampling of its parameters, one can prune frandom to obtain a subnetwork that approximates ftarget up to output error E?
Malach et al. [2020] first proved that, for dense networks with ReLU activations, it was sufficient for fraudom to be twice as deep and polynomially wider than ftarget. Orseau et al. [2020] showed that the width overhead could be greatly reduced by sampling parameters from hyperbolic distribution. Pensia et al. [2020] improved the original result for wide class of weight distribution, requiring only a logarithmic width overhead, which the authors proved be asymptotically optimal. Da Cunha et al. [2022] generalised those results with optimal bounds to CNNs with non-negative inputs, which Burkholz [2022a] extended to general inputs and to residual architectures. Burkholz [2022a] also reduced the depth overhead to single extra layer and provided results that include whole class of activation functions. Burkholz [2022b] obtained similar improvements to dense architectures. Fischer and Burkholz [2021] modified many of the previous arguments to take into consideration networks with non-zero biases. Ferbach et al. [2022] further generalised previous results on CNNs to general equivariant networks. Diffenderfer and Kailkhura [2021] obtained similar SLTH results for binary dense neural networks within polynomial depth and width overhead, which Sreenivasan et al. [2022] improved to polylogarithmic overhead.
Structured pruning Works on structured pruning date back to the early days of the field of neural network sparsification with works such as Mozer and Smolensky [1988] and Mozer and Smolensky [1989]. Since then, a vast literature has been built around the topic, particularly for the pruning of CNNs. For a survey of structured pruning in general, we refer the reader to the associated sections of Hoefler et al. [2021], and to He and Xiao [2023] for a survey on structured pruning of CNNs.
RSSP Pensia et al. [2020] introduced the use of theoretical results on the RSSP in arguments around the SI.TH, namely Lueker [1998, Corollary 3.3]. The work by Da Cunha et al. [2023] provides an alternative, simpler proof of this result. Borst et al. [2022] and Becchetti et al. [2022] proved multidimensional versions of the theorem. Theorem 5 diverges from those results in that it supports some dependencies between the entries of random vectors.
3 Preliminaries and contribution
Given E N. we denote the set (1....,n) by [n]] The symbol * represents the convolution operation, C represents the element-wise (Hadamard) product, and Φ represents the ReLU activation function. The notation |I-II, refers to the sum of the absolute values of each entry in a tensor. Similarly, II-112 refers to the square root of the sum of the squares of each entry in a tensor. I| denotes the maximum norm: the maximum among the absolute value of each entry. Sometimes We denote the normal probability distribution with mean and variance o² by Mi,, We write U ~ A/d, (/dxxx-x< x-. xd,, to denote that U is random tensor of size dj x x... d, with independent and identically distributed (i.i.d)) entries, each following NTO, 1). We refer to such random tensors as normal tensors. Finally, we refer to the axis of a 4-D tensor as rows, columns, channels, and kernels (a.k.a. filters), in this order.
represent
a tensor X E ds dd. by the notation X = (X,, Di
For the sake of simplicity, we assume CNNs to be of the form N: [-1, DxDxx0 DxDxxe given by
N(X) = K² ((K' .... (K * X)),
where K' E xd for E [?], and the convolutions have no bias and are suitably padded with zeros. Moreover, when the kernels K are normal tensors, say that N is a random CNN.

---

Our main result is the following. Theorem 2 (Structured SLTH), Let co. l N. and R2 For E [0, let di, C, n4 E.N. LetF be the class of functions from |- 11x11 to Dxxxx such that, for each E F
f(x) = K * ((K(-1)) * *... x)):
(1)
where, for i E 10, K(0 E pd gdxxdxx--Xe Xc: and | S
Let also No: 111,1] + +R DxDxc be 28 2l-layered random CNN given by No(X)= = ( (( ((L (1) * X)),
(2)
where for i [6] the kernels ( and L(20) are normal tensors of shape x 1 x C 21:0-11 and d, x de X 2n:4-11 X C, respectively.
Finally, let G be the class of subnetworks that can be obtained by pruning contiguous blocks of parameters and removing entire filters from No-
There exists a universal constant C > 0, such that if. for E [e]
n4 2 Ca. & log Reaci-il E then, with probability at least 1 e, we have that, for all f EEEEEEE F,
min [I((X) - g(X) S. xe|-1,1jxxDxo SEg
sup
The filter removals ensured by Theorem take place at layers 1, 28 and imply the removal of the corresponding channels in the next layer. The overall modification yields CNN with kernels _(),..., [(0)) such that, for i E [f], the kernels ( and (2:) have shape 1 x x C--1 X 22;-177 17; and d, x d, x 2c,-1m, X c,, respectively, where m, V //t://C/ie log(1/))) for universal constant C1. Moreover, our proof ensures that the kernels ī (22-1)) be required to have a specific type of block sparsity: they can be structured as if pruned by 2m.-channel channel---bbocceed masks, defined as follows.
Definition 3 (n-channel- mask). Given positive integer n, a binary tensor S (0, 1) dxxdxxxen is called -looked and only if
[ if [+] = 0
otherwise,
for all i.j E [d]. & E [c), and I E [en].
We remark that, from broader perspective, the central aspect of Theorem 2 is that the lower bound on the size the random CNN depends only on the kernel sizes the CNNs being approximated.
In subsection 4.2 we discuss the proof of Theorem 2. It requires handling subset-sum problems on multiple random variables at once (random vectors). Furthermore, the inherent parameter-sharigg of CNNs creates a specific type of stochastic dependency between coordinates of the random vectors, which we capture with the following definition.
Definition 4 (NSN vector). A d-dimensional random vector Y follows a normally-scaled normal (NSN) distribution if, for each i E [d] Y, = 7 Z, where Z, 71,..., Za are i.i.d. random variables following standard normal distribution.
key technical contribution of ours is Multidimensional Random Subset Sum (MRSS) result that supports NSN vectors. In subsection 4.1 we discuss the proof of the next theorem, which follows a strategy similar that of [Borst al., 2022, Lemmas 15].
Theorem 5 (Normally-scales MRSS). Let 0 < e S 1/4, and let d, k, and n be positive integers such that n 2 k22 and l 2 Cd3 log & for some universal constans C E RRyo- Furthermore, let X,,..., X be d-dimensional i.i.d. NSN random vectors. For any z E Rd with || S Vk, there exists with constant probability a subset C [n] of size ie such that (Eies iEs X.) E
max S..
While it is possible to naïvely apply Theorem I to obtain version of Theorem doing so leads to an exponential lower bound on the required number of random vectors.
5

---

4 Analysis
In this section, after proving MRSS result (Theorem 5), discuss how it to obtain main result on structured pruning (Theorem 2). Full proofs are deferred to Appendix B.
4.1 Multidimensional Random Subset Sum for normally-scaled normal vectors
Notation. Given a S and a positive integer n, we denote by (+)) the family of all subsets of S
containing exactly elements of S. Given E R>a, we define the interval Ie (2:) = [z; e, 2 + e]
and the multi-interval 1 (z) - + =1], where 1 = (1, 1) E Rd. Moreover, for any event &, we denote its complementary event by E.
In this subsection, we estimate the probability that set of n random vectors contains a subset that sums to a value that is E-close to a given target. The following definition formalises this notion. Definition (Subset-sum number). Given (possibly random) vectors X Xn and vector we define the E-subset-sie sum number of X1,..... Xn for x as
T xx.... Xn (8)
1 p())
SE((W))
where E denotes the event || (Eies Xz) - mmmxx S. and E are clear from the context.
We write simply Ta, when XI,..., Xn
To prove Theorem we use the second moment method to provide a lower bound on the probability
that the subset-sum number Tn is strictly positive, which implies that at least one subset of the random vectors suitably approximates Hence, we seek lower bound on [T[,,,,]² /EE[T
Our first lemma provides a lower bound on the probability that of NSN vectors is E-close to target vector, through which one can infer a lower bound on E [Tn,,]-
Lemma 7 (Sum of NSN vectors). Let k E N. (0, 1), z E Rd such that ||²|,, < vk and k Z 16. Farthermore, let XI...., Xy be d-dimensional i.i.d. NSN random vectors with d S k, and 1 It holds that
let ca min d 16
k Pr Σ
d
x, (
16 (1 2//aa 2ca) k.
Overview of the proof. The main technical difficulty lies in the fact that the random vectors X1...., Xx are NSN vectors. Bounds can be casily derived for the case where the X; are i.i.d. normal random vectors by observing that the sum normal random variables also normal.
For i E [k)] each entry of X; can be written as Z; Zi,j where Z; and Zi.j are i.i.d. normal random variables. Conditional on Zi..... Zu. the d entries of X = -E X₁ are independent and distributed as M(O k 2. By noticing that 2 is a chi-squared random variable and employing standard concentration inequalities (Lemma 17 in Appendix A) combined with the law of total probability, we can proceed as if the entries of X were normal. up to some correction factors.
Bounding ET requires handling stochastic dependencies. Thus, we estimate the joint probability that subsets of l elements of XI,...p Xn sum e-close the same target, taking into account that the intersection of the subsets might not be empty. The next lemma provides an upper bound on this joint probability that depends only the size of the symmetric difference between the two subsets.
Lemma 8 (Sum of NSN vectors). Let k,j E No with 1 < j < k Furthermore, let XI,..., X be i...d. d-dimensional NSN random vectors with & 2 Cd log L. Let ca = min { 2z 1.1. A
Ei X,, Ex X,, and = ー X,, Then, holds that
4
Pr (2) <3
2 2//od)
We adopt the convention that D X; 0.

---

Overview of the proof. Let = k + j. We exploit once more the fact that, for all E [nx], each entry X, can be written as Z; Z where Z; and Zi are i..d. normal random variables. Conditional on Zi...., Zk+j. the d entries of A, B, and C' are independent and distributed as AOO, Z M(, Σ Si=j+1 72), and V(. Ei ZF), respectively. Hence, by the concentration inequalities for the sum of chi-squared random variables (Lemmaa 17 in Appendix A) and by the law of total probability, we can focus on the term
Pr Pr + B; E Le (z),, C. (2)) Z1 Zn),
where A, B;, and C. indicate the i-th entries of A, B, and C, respectively.
Another concentration argument for normal random variables (Lemma 14 in Appendix A), allow us show that
Pr (A; + B; E (
7,....,,, .,,)
-Ea,
[Pr(A; [Pr
B,), C, E I, (z: - B,) 71,..., 7,,, B:)] 6 Te
= EB, E (2, B,) Z Zn. B.) Pr (C; E L. (a - -B,) Zi..... Zn B() Br) Pr (C, E (0) Z1. Z....., Zn, B,)] = Pr (A, E Le (0) Z,....,,, P,) (C; Le (0) Z,.
S EB, [Pr (A; Ie Z0) Zn, B,)
Thus, we have reduced our argument to the estimation of probabilities of independent normal random variables being close to zero.
The following lemma provides explicit expression for the variance of the e-subset-sum number.
Lemma 9 (Second moment of Ta,k). Let n be positive integers. Let So Si,..., be subsets of [n]] such that SSo SS] ||| = k - j-j
0, 0.1...., ,k. Let S,S' be two random variables yielding two subsets of [n] of size k drawn independently and uniformly at random. Let X1...., Xn, be d-dimensional ii.dd NSN random vectors. For any >> O and E Rd, the second moment of the e-subset sum number is
& Σ 1=0
E (T2
12 k
= k- Pr ((()) (Eg)) Pr Pr((Sn''=
=
where c( denotes the event
||
(Eies X,) - S.
Proof. Let S,S' two random variables yielding two elements of (2) drawn independently and uniformly random. By the definition of T T,A we have that
(E
]
E T = E
Σ
Σ
(E(l
('E(!r))
= E
E
(m])
= Σ
Pr (1(3) n nega
(1))
Σ
( Pr
n
n
S= = 5) P =,5
S,S' = S,-'= SS)
eg)
(.))
Pr
c
|sss = k k-) Pr = k k-)),
as Pr (E( n ( depends only on the size of Snns..
7

---

Overview of the proof of Theorem 5
We use the second moment method (Lemma 15 in Appendix A) on the e-subset-sum number Ta of X Xu. Thus, we want to lower bound the right-hand side of
& E[T n.
Pr Pr > 0) 2
BTT x
Equivalently, we can provide an upper bound on the inverse,
By Lemma 9,
2 &
[TT,k]] = n1
Σ
Pr -
= k- &
NE
0=0
where S,S', S and ? are defined as in the statement of the lemma. Observe also that
E [Tax]
Σ E E =
((2) = Pr
n1)
Pr
(( 5o
(E(
By using the two above observations, we have
E
P k) Pr ( n (E)
(3))
nES,)
E E
E K
n,
Pr |L n nEg,
Σ P
=
e(5) So
==
Pr
Lemma provides lower bound the term Pr(e(() while Lemma 8 gives upper bound on the term Pr(e (2) NES,).
In the full proof, we then show that Pr (SS (Lemma 16 in Appendix A) even if we do not deal directly with binomial random variables. This allows discard the indices j for which Pr(g()) n n&s)) is large, which leads the result after some technical manipulations.
S 2 k/d) can be bounded using the Chernoff bound
4.2 Proving SLTH for structured pruning
To prove Theorem 2, we first show how to obtain the same approximation result for single-layer CNN. Then, we iteratively apply the same argument for all layers of a larger CNN and show that the approximation етror stays small.
We define the positive and negative parts of a tensor.
Definition 10. Given tensor X [Rd x..xx.. the positive and negative parts of X respectively defined as X = 1x-xxxxxxx 1x,20 and X =x. 1x,50, where i E [d1] x x... [dm]] points at generic entry of X.
Approximating a single-layer CNN
We first present a preliminary lemma that shows how prune single-layer convolution & (V X) in way that dispenses us from dealing with the ReLU ø.
Lemma 11. Let D, d, c, n E N be positive integers. V E BlxIxex2ng and X Dxx Let S E (0.zee) be rechanne-bblocked mask. There exists mask S, E {0, 1]siee(V) which only removes filters such that, for each (i.j. k)) E [D] [D] x [2nc], iʃ = S
SS ④ S2, then
(0( (v(vv))) * xx)) ig
= ((vo))* x + (vo 5) x
ig
8

---

Overview of the proof. S2 E (0, ( is such that that Voš (Vo.S) contains only non- negative edges going from each input channel to the output channels +l (2) (2 and only non-positive edges going from each input channel to the output channels (2t- +1, +,,..... Notice that, after applying the 2n-channel-blocken k-th filter is located its t = 2n -th channel. Hence, for each
..... 2tn. mask S1. the only possible non-zero entry of the
[2nc], we keep filter i if the entry of its 1-th channel is non-negative and 21. - 1 = k or it is non-positive and 21 = [ [ 17
We approximate single convolution K * X by pruning polynomially larger neural network of the form U * ΦVV * X) exploiting only a channel-blocke mask and filter removal: this is achieved using the MRSS result (Theorem 5).
Lemma 12 (Kerell pruning). Let D, co. n E N be positive integers, (0. 1) .M M e Rso. and C' E Ryo be a universal constant with
de d'c
n 2 Cd of log
E
Let U _Ndxdx2nexxx, V ~ XIxxxxxxxx000
and S {0, 1) 1)aize(V), with S being a 2n-channel- blocked mask. We define No (X)= = U + & (V * X)) where X E RDDDXx, and its pruned version No0) (X) = U & ((V S) X). With probability 1 for all K RRdxdxexos with | 1, it is possible to remove filters from No55) to obtain CNN ((9)) for which
K N:55 (x)
sup X=||X|| SM
<.M.
SM
max
Overview of the proof. Exploiting Lemma 11, for each 81) [d]] x [d]] x [ca], one can show that
(U (U* ((vo * xx) nam =
Σ
Σ
Uniiket
Vit Vith,oo))
x xtt
kE(nool
E
Uej.kd Villook) X---t11-541000
kE|nncl
where 5 = S1 @ S2, with S₁ being a 2n-channel-blocke mask and S2 being a mask that removes filters. Through a Chernoff bound, we show that Viti. has at least n//3 non zon- entries. Up to reshaping the tensor as dineennnall vector, we observe that U... V+ (Lemma 18 in Appendix A). Hence, can apply boosted version of the MRSS result (Corollary 19 in Appendix A) and show that, with high probability, for all target filters K with | S 1, we can
L.L.fg.k is NSN vector
prune all but roughly / /n/((Cidden !) positive entries of Vit I, with C1 being a universal constant, such that ExE(nca) U...k. Vi, approximates the channels K...t.: up to error e/(2dcog1)) The same holds for Eke(ne)) U. V.. This pruning can be achieved by applying third mask Sa that only removes filters. Through some non-trivial calculations and by applying the Tensor Convolution Inequality (Lemma 20 in Appendix A), one can combine the above results to get the thesis. Notice that the overall pruning can be represented by the mask S₁ O (S2 @ Sz), where S, O Sy is a mask that only removes filters, and S = S is a 2n-channel blocked mask.
Remark 13. From the proofs of Lemmas 12 and 11, we can see that the overall modification yields a pruned CNN Ú o(V X) with V glx1xroX2me and Ú dx 2meg x0a where
m Vn/ /C !) for universal constant C₁. Moreover, the kernel V obtained through a mask Sj. Second, we remove filters based on entries' signs through a mask S2. Third, we remove filters according to the MRSS result through a mask S3- Masks S2 and S₃ can be combined into single mask S2 @ S3 that only removes filters: overall the pruning process consists of 2n-channel-blocken mask and filter removal, which justifies the statement of Theorem 2.
3-stage pruning process: First, we apply a 2n-channel-

---

Overview of the proof of Theorem 2
We iteratively apply Lemma 12 each layer while carefully controlling the approximation error via tools such as the Lipschitz property of ReLU and the Tensor Convolution Inequality (Lemma 20). More precisely, we show that (i) the approximation error does not increase too much each layer; and (ii) all layer approximations can be combined to approximate the entire target network. Notice that Lemma 12 guarantces that, with high probability, we can approximate all possible target filters K (with || ||, I 1) from the same 2-layered network. Hence, we get the result for the supremum over all possible choices of target filters.
5 Limitations and future work
In previous works [da Cunha et al., 2022, Burkholz, 2022a] the assumption that the kernel of every second layer has shape 1 x x is only an artifact of the proof since one can readily prune entries of an arbitrarily shaped tensor to enforce the desired shape. In our case, however, the concept of structured pruning can be quite broad, and such reshaping via pruning might not fit some sparsity patterns, depending on the context. The hypothesis on the shape can a relevant limitation for such use cases. The constructions proposed by Burkholz [2022a.b] appear promising direction to overcome this limitation, with the added benefit of reducing the depth overhead.
The convolution operation commonly employed in CNNs can be cumbersome at many points of our analysis. Exploring different concepts of convolution can be an interesting path for future work could lead to tidier proofs and more general results. For instance, employing 3D convolution would spare a factor in Theorem
Another limitation of our results is the restriction to ReLU as the activation function. Many previous works on the SLTH exploit the fact that ReLU satisfies the identity x = x(x) o(-z). Burkholz [2022a] leveraged that to obtain an SLTH result for CNNs with activation functions f for which fxx)- x around the origin. Our analysis, on the other hand, does not rely on such property, so adapting the approach of [Burkholz, 2022a] to our setting is not straightforward.
Finally, remark that the assumption of normally distributed weights might be relaxed. Borst et al. [2022] provided an MRSSP result for independent random variables whose distribution converges "fast enough" Gaussian one.* We believe our arguments can serve well as baselines generalise our results to support random weights distributed as such.
Acknowledgments and Disclosure of Funding
Francesco d' Amore is supported by the MUR Fare2020 Project "PAReCoDi" CUP J43C220097000.
References
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. 5th International Conference on Learning Representations, ICLR 2017, Toulon. France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: http:::////ppeeeie////e net mtt//oorrmiiee---yyydd00
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3):107-115, 2021. doi: 10.1 145/3446776. URL hhttps://aae org/10.
1145/3446776.
Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sensitivity and generalization in neural networks: an empirical study. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Truck Proceedings. OpenReview.net, 2018. URL htwph:t/////ttt htttpp:///peeeeeviee net/ forum? Herumm?dd=HJ22222c.
'The required convergence rate higher than that ensured by the Berry-Esseen theorem.
10

---

wttpccppppppe/////. Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize on linearly separable data. In 6th Interna- lional Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May- 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: //openreview.oo
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizes neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:// openreview net/ www.ooodddeeeeeeee KK33000 1
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, abs/2001.088 000661, 2020. URL https: www.waiww...aaaaaaaaaaa.
08361. Russell Reed. Pruning algorithms-a survey, IEEE Trans. Neural Nenworks, 4(5):740-747, 1993. doi: 10.1109/72.24855.. URL attps://ddo org/10. 1109972..994485555
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, editors, Proceedings of Machine Learning and Systems 2020, MI.Sys 2020, Austin, TX, USA, March 2-4, 2020. misys.org, 2020. URI. / httpttpss//prrcceednnngs mll..llsssssssmnn.mmmmmmmmmmmm.s www.mmllrgs/pppe.....eee. org/paper files/
paper/2022 2020 httphhhhhhh//////0/0 410.477700044111a99922244480000 Abstract. .htm..
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. J. Mach. Learn. Res., 22:241:1-2411 124, 2021. URL http: http://mmmorrromppppeee pttppp/ppp///1-00//// html. 1.4
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL httpp:://pppereeeeeeee/// net/forummid rJ1-b3RcF7.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tick- ets: Zeros, signs, and the supermask. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pages 3592-3602, 2019. URL https: h/proceednns 1113d7776ffceeeee www.cceaawbbbbbbbeeeeeeee 4500000et....777--b-bbrrrettttt Abstract.hmml. 2
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in randomly weighted neural network? In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 11890-1 1899. Computer Vision Foundation IEEE, 2020. doi: 10. 100.10/222422200...00 2020. 01191. URL https: /twpa//cppaaccseeeeeeepe/ssssssa thecvf. com/ wttp/ettttttcccceeeeeeee CVPR_ 2w2000022//ii Whats_Hidden in_ wtw_aaadnooll_eeeeeeeeeee wwtptWeeeehteeeeerrreeee Metrree__eeeraaaaeettt___._ SUUUPR_2220__ppPPP__ .tmll. 2
/aaal///aaaaaaaaaaaaaaaaaaaaaaaa an_
Yulong Wang, Xiaolu Zhang, Lingxi Xie, Jun Zhou, Hang Su, Bo Zhang, and Xiaolin Hu. Pruning from scratch. In The Thirty-Fourth AAAI Conference 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- 2020, pages 12273-12280, AAAI Press, 2020. URL https: //aaai. hetg/jss/nnded hwtpppppt/ttaicc//eepppeppp wtt.://iii.eeeee//11/..2.2
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris S. Papail- iopoulos. Optimal lottery tickets via subset sum: Logarithmic pareeerratttiinnatoonn suf- ficient. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: httpsss//prooeeiiigggg wtwpeeeddinnnnnnnnineeeeeeeeeeee www.wns....pppprrrr..re... wwtppppppp///.......///// /hash/ 1wt.:2/2500001105444444662222220 www.aaaaaaaaaaaaaaaataaaaaaaaaaa Abstract html. 2, 4
11

---

Udo W. Pooch and Al Nieder. A survey of indexing techniques for sparse matrices, ACM Comput. Surv. 5(2):109-133) 1333, 1973. doi: 10. 011133356666633666... URL https:///oi..... org/ 1145/ 656616.356611 2
Adam Polyak and Lior Wolf. Channel-level acceleration of deep face representations. IEEE Access, 3:2163-2175, 2015. doi: 10. 100//ACCSSS URL ACCESS 2015 2494536.
Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Alché-Bus Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 14014-14024, 2019. URL https: htattts:/pproceeedeee /ptp//eeeeeeeg...e///// wewpiiinnnnnuuuuuineee neur cc/cc//p// 2019 2019/hash/
www.raaddteeeeettaaaaaattt...a.. tatbstract.hml..... 2
Jose M. Alvarez and Mathieu Salzmann. Learning the number of neurons in deep networks. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Gar- nett, editors, Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages
2016. URL (7772266235336887771144443 400440000054--bbrraacttt Abstract html. 2
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In 7th International Conference on Learning Representations, ICLR 2019, New Orleuns, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL CorumPid==:InB3CSST
net/
Sajid Anwar, Kyuyeon Hwang. and Wonyong Sung. Structured pruning of deep convolutional neural networks. ACM J. Emerg. Technol. Comput. Syst., 13(3):32:1-3243 18::118, 2017. doi: 10.1145/3005344
URL https:t//ti....oo org/ 10. 1141 1145/3005348. 2
Arlene Elizabeth Siswanto. Block sparsity and weight initialization in neural network pruning. PhD thesis, Massachusetts Institute of Technology, 2021.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning, pages 6682-669 6691. PMLR, 2020. 2, 4
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In John C. Platt, Daphne Koller, Yoram Singer, and Sam Roweis, editors, Advances Neural Information Processing Systems 20, Proceedings of the Twenty-Firs! Annual Conference Neural Information Processing Syxtems, Vancouver, Brilish Columbia, Canada, December 3-6, 2007, pages 1 1177-1184, Curran Associates, Inc., 2007. URL https: /ttp///eeeigs...////e//p/e/s.ssp www.iiriipp is. cc. paper/2007/hash/ 011a006f03abc55322fffffee 18f Abstract html.
Ali Rahimi and Benjamin Recht. Uniform approximation of functions with random bases. In 2008 46th annual allerton conference on communication, control, and computing, pages 555-561. IEEE, 2008. 2
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for derstanding neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-BBu,, Emily B. Fox, and Roman Garnett, editors, 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, pages 6594-6604, 2019. URL https: https://pree /ttp://///cceee...////o Abstract. html.
wwwriis.cc/aapeeee wwtpcpppp///111//// //thh/ah///hhhh///////////
George S. Lueker. Exponentially small bounds on the expected optimum of the partition and subset sum problems. Random Structures and Algorithms, 12:51-62, 1998. 3,4
Arthur Carvalho Walraven Da Cunha, Francesco d' Amore, Frédéric Giroire, Hicham Lesfari, Emanuele Natale, and Laurent Viennot. Revisiting the Random Subset Sum Problem. In Inge Li
12

---

Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual Euro- pean Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics (LJPlcs), pages 37:1 17:1-17:11, Dagstuhl, Germany, 2023. Schloss Dagstuhl- - Leibniz- Zentrum für Informatik. ISBN 978-3-95977-295.2 doi: D0.4230r..Pics..SAA..2. https: bttps:///rops. dagstuhl de/
Gørtz, Martin
URI.
18690. 3,
Sander Borst, Daniel Dadush, Sophie Huiberts, and Samarth Tiwari. On the integrality gap of binary integer programs with Gaussian data. Mathematical Programming, 2022. doi: 10. 1007//10107-
022-01828-14 1. 3, 4. 10
Luca Becchetti, Arthur Carvalho Walraven da Cunha, Andrea Clementi. Francesco d' Amore, Hicham Lesfari, Emanuele Natale, and Luca Trevisan. On the Multidimensional Random Subset Sum Problem. report, Inria & Université Cote d' Azur, CNRS, 13S, Sophia Antipolis, France: Sapienza Università Roma, Rome, Italy Università Bocconi, Milan, Italy: Università di Roma Tor Vergata, Rome, Italy, 2022. 3,
Laurent Orseau, Mareus Hutter, and Omar Rivasplata. Logarithmic Pruning is All You Need. In Advances in Neural Information Processing Systems, volume 33, pages 2925-2934. Curran Associates, Inc., 2020.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the strong lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations, 2022. URL
4, 10
Rebekka Burkholz. Convolutional and residual networks provably contain lottery tickets. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 1414-2433 PMLR, 2022a. URL https: httttps::/ppre http:s:://ccceeingg/e .mr............m................
httpe///11eebbuuoooo2/ee html. 4, 10
Rebekka Burkholz. Most activation functions can win the lottery without excessive depth. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 18707-18720. Curran Associates, Inc., 2022b. URL https: http::/e00000ccc00000eeeeeeearee
newrips. cwtprippsccppppprrreeeeee of files/ paper/2022/fille/ pdf. 4, 10
Jonas Fischer and Rebekka Burkholz. Towards strong pruning for lottery tickets with non-zero biases.
CoRR, abs/2110. 11150, 2021. URL http:: org abs /tt.://........................1 11150. 4
Damien Ferbach, Christos Tsirigotis, Gauthier Gidel, and Avishek Jocy Bose. A general framework for proving the equivariant strong lottery ticket hypothesis. CoRR, 024/2206004270 2022. doi: 10.445500arXiv.2266.00 04270. URL http::tt:::/e //to::::://d..ooo org/ 10. 48550/ arvvvv 2206. 04270. 4
James Diffenderfer and Bhavya Kailkhura. Multi-priza lottery ticket hypothesis: Finding accurate binary neural networks by pruning A randomly weighted network. In 9th International Conference on Learning Representations, ICI. 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL http:: httpep:ss///pppeeeiieee
forfoormmdduuaaaaaaa dit-ummiiddmmmat0biii.. 4
Kartik Sreenivasan, Shashank Rajput, Jy-yong Sohn, and Dimitris S. Papailiopoulos. Finding nearly everything within random binary networks. In Gustau Camps Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 3531-3541. PMLR, 2022. URL https: http://///occee.e..///m mlr, wwwpppresssvveee /eeess/vvi//e html.
Michael Mozer and Paul Smolensky, Skeletonization: technique for trimming the fat from a network via relevance assessment. In David S. Touretzky, editor, Advances in Neural Information Processing Systems [NIPS Conference, Denver, Colorado, USA, 1988), pages 107-115. Morgan Kaufmann, 1988. URL http::t/tpp:pee trimming- wat.-aroooaaaaattttttraaaaaaarer wttp:eeeevaanceeeseeeeeeeeete assessment.
httpppppeeeret-eeeeeeeeeeeeeeeee on a- fochnique-for-
Michael Mozer and Paul Smolensky. Using relevance to reduce network size automatically. Connection Science, 1(1):3-16, 1989. 4
13

---

Yang He and Lingao Xiao. Structured pruning for deep convolutional neural networks: A survey. CoRR, abs/2303.00566, 2023. doi: 10.48500/uxii2333300566. URL https://áoks org/10. 48550/ arXiv
Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. ISBN 378-0-521-88427-3 URL 15
http::/www cambridge org/
B. Laurent and P. Massart. Adaptive estimation of quadratic functional by model selection. The Annals of Statistics, 28(5): 1302-1338, 2000. doi: 00.121//a///0155557999 15
Benjamin Doerr. Probabilistic Tools for the Analysis of Randomized Optimization Hcuristics.
arXiv:1801.06733, 2020. 22
14

---

Appendix
A
Technical tools
A.1
Concentration inequalities
Lemma 14 -oobb-peobable normal interval). Let X follow a zero-mean normal distribution with variance o², For any 2, E R
e - + 2 Pr Pr (-E,E))
Proof. Let (p(x) denote the probability density function of X. Then,
Pr E [-,, - Pr (X E 2a - -, [ (p(x) da fret
at (p(x) dz.
- 2 e or 2 + 8 < -E, the thesis is trivial as (0(1z)) decreases x. W.l.ogg. suppose is positive and < Then, < <E 2 It follows that
[ p(x) (())dr- dr f
at ((x) dr
((x)) dr - 2+5 ((x)) dr
2-6
(0x) - pp(a + 25) do
which is non-negative p(x) p(r 2c) for -E.
Lemma 15 (Second moment method). If Z is non-negative random variable then
E 2
Pr (Z 0)
Lemma 16 (Chernoff-Hoeffe bounds [Dubhashi and Panconesi, 2009]). Let X1, X2,..., Xn be independent random variables such that Pr (0 < X, 1) =
1 for all E [n]. Let X = Eizl X
and [[ = μ. Then, for any d (0, 1) the following holds:
1. if p S pt+, then Pr (X 2 (1 + 8)p4) exp
(-ox-)
8'
2. 0 < μー S 14, then Pr (X S (1 - ) < exp
Lemma 17 (Corollary of [Laurent and Massart, 2000, Lemma 1J). Let X ~ xa be chi-squared random variable with d degrees of freedom. For any t > 0, it holds that
1. Pr X 2 d+ 2/ + 21 S exp (-t);
2. Pr x < d dt S (-t)
A.2 Supporting results
Lemma 18 (NSN with positive scalar). If a d-dimensional random vector Y is such that, for each E [d], Y; Z Zn. where Zi...., ., Zn are identically distributed random variables following standard normal distribution, Ž is half-normal distribution, and Z, Zi...., ..,,, are independent, then Y follows an NSN distribution.
Proof. By Definition 4, Y is NSN if, for each [d], Y; Z Z, where Z, Zi,.... Zn are i.i.d. random variables following a standard normal distribution. We know that Z |2], therefore 2, = sign (2) sign (2,) [Z| for each i = 1,.... n, where Z, Zz,.... Zn are i.i.d. standard normal
$Le. 2 |Z| where Z is standard normal distribution.
15

---

random variables, as sign (igsig (2,) is independent of sign (Z) and of sign (2) sign (Zj) for i o j. Then,
Y = - Z;
Z sign (Z) sign (4)) Z,
= sign (Z) / sign (7:) 2
Z Zi,
implying the thesis.
Corollary 19 (of Theorem 5). Let d, ki and n be positive integers with 2 Cydk3 (t) and k 2 O2d log & for some universal constants Ci, C2 E Ess. Let Xis...y Xn be d-dimensional i.i.d.
NSN random vectors. For any 0 S it holds
Pr YEER"
|| SS |S|= = k.
Σ X
S 21-E.
Proof. Observe that the |-1, 11dh can be "partitioned" in 1/E" many oc-norm balls radius E. Let [Cd (2) and let partition the vectors Xi,..., X,, in disjoint sets Gi.-.., G2 of least h2 vectors each. By Theorem there is a constant E (0, 1) such that for each group G; (i E [s])
|
Pr SS c G. =
=1=k,
Xi
z
2 c.
(3)
iES
max
It follows that
Pr
VZ Rd || $ 1,35: |S| = k.
Σx,
SE
VEE
2 Pr
AA E R.d || < 11 ( EE C G |8|= k;
Σxi
Σ
Xi
S
E
IES
maX
=1 Pr
2 || 1, (S) G. |8|= =
Σ X;
E
2 1 ed
Pr ViE E c G.: |S|= k;
-
> 8
(4)
IES
max
21- ed (1 - c)) (iddoc)))
1
(5)
where Eq. 4 holds by the union bound, Eq. 5 comes from Eq. 3 and the independence of the variables across different G., By choosing C₁ large enough,
-- (1 c) (id]oe(+)] = 1 2d & - [C1))o(())] log T 2 1 -E
Lemma 20 (Tensor Convolution Inequality). Given real tensors K and X of respective sizes d x d' x co ci and D D' x Co. it holds
[[ X Imax S [K]h ||X max
Proof. We have
K * X max
16

---

LJE D),eE(o) (.J'((d)eeld)
max J.E ())
||X Imaxx
P.j'Eld,
max i,f D),
| ||
||||| || max
B Omitted proofs and results
B.1 Multidimensional Random Subset Sum for normally-scaled normal vectors
Proof of Lemma 7. By Definition 4, the j-th entry of each vector X; is (Xi)) Z - Zz,s where each Zi and Zi,j are i.i.d. random variables following a standard normal distribution. Let (()) be the event that & (1 - //) Σ z S k 21+2/ca + 2ca). and denote X Σ X,. By the law of total probability, holds that
Pr E I2 = Ez,,.... 2,..... [P E Ie (2) Z1. Z+)l
As, conditional on Zi...., Zk. the entries of are independent, it follows that Ez EZ...... Zn Pr (X E 17 (2)
Ex)]
d
II Pr ((X); E le (zi) 21, 21,..., 21) y=1
E EZ .... Zn
II Pr ((),, E (z)) Zi,... Ze. S(1)) j=1
Pr (Ews)
2 .n...
(6)
where the inequality in Eq. 6 holds by applying again the law of total probability. Conditional on Z Zz. we have that (X); ~NO0, E. Z7). Hence,
d II
Pr (()), E Ic (zi) 2i...., Zk, E(D))
Pr (E(0)
Eg Zn
5=1
d
(|2/ + E)²
2 Ez E2 Zu
II
exp
E(T)
2 Σ5 2?
1=1
Pr (((0))
Notice that the term Σ. 73 is sum of chi-square random variables, for which there are known concentration bounds (Lemma 17). By definition of g(t) and by applying Lemma 17 to estimate the term Pr (E(D), we get that
E 7
Ze
II
25
exp
(125) + =)² 2 Σ
E(()
===1 2?
E
π
Pr
(
17

---

2E
Σ 221 + 2: E, |2/| + dE²
Pr (E(0)
exp
2 211-2/ca) k
(1 + 2/co + 20a) b
28
| + 22 11211, + ds²
Pr (((13))
exp
(1 + 2/ + 2ca) k
2 - 2/coa) k:
d
2
EE + 28 ||=11, + de²
(1-20 caly
exp
(1 + ca + 2ca)
2 - 2/eaa k
As cak by hypotheses, 1 1 -ak 2 1/4. Then,
d
28
|| + 2e 1|21| de?
(1 (1-24 2e cekk
exp
2 ((1-2ve) K
ạ (1 2/aa 2ca) k
28
||=12 + 2e 1/21, + de²
2
exp
4
(1 + 2/ + 2cd)
2 (1- -1-22veh 2/ k:
2
k+ V + de? 2 2/ca)
M
44
exp
π (1 + 2/eed + 2cd)
1 25 + d= vk
2=
4
π (1 + 2/coa + 2cd)
exp
2 2//0)
d
1
2z
1+ 1 + 1 16
4
V (1 + 2 + 2cd) k
exp
(1 2/)08)
(8)
d
1
28
2
(9)
16
π (1 + 2/0 Ca 2ca)) k
where we have used that | S 11 S V in Ineq. 7, that 2 16, k 2 d, and E < 1/4 in Ineq. 8,
and that
11 3 + T6
+ + TO
exp
> exp
2 2/ca)
2 - 2/ 16
16
in Ineq. 9.
Proof of Lemma 8. Let n k+ j. j. Since the X,s are NSN random vectors, for each i E [n] and j E [d] we can write the j-th entry of X; as (X,); = Z, Zij where the variables in {2 kefn) and in (eehheenljje are i.i.d. random variables following standard normal distribution. By the law of total probability, we have
(A + B (2), B
Ez,...,, Zn Pr
Zz..,, Zn)l
d
Ez,...... 2n
II
(A; + B E 1. (2)) B, B. (z)) Zi.... Zn) : (10)
18

---

where the latter equality holds by independence.
Then,
1i,.... (4) kn) =En [Pr (A, E (2, B,), ( - B.))
(A + B, E (z.), B, + Q E
=
Zn; B:)]
= EB, [Pr (A, le (B.-B.) , Zn, B.) Pr (C; E 1g (zi - B:) Zi,..., Zn: B:)] where the latter inequality holds by independence of A; and C.. By Lemma 14, it holds that
EB, [Pr E 1e (24 B:) LI...., Zn. .,. B,) Pr (C2 E Ie (2 B.) Zz,.... Zn B.)] - EB, [Pr (A, E Ie (0) Zz.... Zn B,) Pr (C; E 1. (0) Zi,.... Zn B:)l (A; E I (0) Z1. 71...., Pr(; I (0) Z....... ;Zn)
2E
2
(11)
V (Ei z?
E E Z?
πT
where the latter inequality comes from the fact that, conditional on E....., Zn. we have that A; ~ Mo, Ei= 22). B, ~ MO, Σデ=j+1 22), and C, ~ NNO, Σ 22) for each E [d].
We now proceed similarly to the proof of Lemma 7. We denote the event that (1 - 21c2)/)) j s
E 23 1i 2 by (L)) Then, by Eq. 10 and the law of total probability, we have that
Pr (A B 1g (2) B 1 (2))
Ezy..., Ten
Pr (A + B, E (2)) + ( .,.... 2n,
iil
< Ezz.... Ze
II Pr A, + B, B, - E
Z1 Zn, El1)
+ Pr {(1)
Eq. 11 implies that
Ez 2n
Pr
A + B,, B, e. (2))
Zi...., EWI
+ Pr (E())
Liml
2s
< E2 B2 Zn
1I
g(4)
+ Pr (E(
i=1
Ei=
2
VT
D 2?
4s
Pr (Ew)
233
(Ckti 23
By independence of Ei Zz and D 2F and by Lemma 17, we obtain that
d
2
E 2 Zn Zu
((4)
+ Pr ((4)
TT m
(//(2> Ei_ 22²
EE 2F
4ea
+ Pr (((3)
T (1 2/ca)
d
4
+ 2 exp (-caj)
ブ (1 - 2/ea)
19

---

Tÿ (1 (1-2vea)
exp
-dlog
eexp (-cak).
4s2
=k 22
Finally, for large enough constant C, the hypothesis on is implies that k 2 Hence,
2 log
1sa
ブj (1 2/(aa
4=a
d
exp
-dlog
+ 2 exp (-cak) 53
4g2
T - 2/
Proof of Theorem 5. We use the second moment method (Lemma 15) the e-subset-sum number Tn,k of X1, XI,..., X Thus, we aim to provide a lower bound on the right-hand side of
E n
Pr (T > 0) Z E
(12)
n.
1 TT
Equivalently, we can provide an upper bound on the inverse
By Lemma 9
2 &
[ = 12
Σ
Pr
(
neg,
(13)
1=
where S,S', S; and Eg? are defined as the statement of the lemma. Observe also that
E [T
Σ E
Σ
Pr
n
Pr
(())
(14)
k
Se
(E(
By Eq.s 13 and 14, we have
E
T2
Σ
= Pr (15))) ne(
E
T
n.
E
[T n
5=
Pr (Z) ( & nE
Σ
Pr((Sns)
(15)
==
Pr
50
As for the denominator of the second term in Eq. 15, by Lemma 7 we have
4
Pr
8
(16)
256
π (1+ 2/ ca + 2ca) k
As for the numerator of the second term in Eq. 15, Lemma implies that we have
&
cl2) S,
53
4
(17)
(1 - 2//o) i
By plugging Eq. 17 and Eq. 16 in Eq. 15, for j 2 k (1 2) and d > 1 upper bound the
Pr (e(
factor Pr (()
of the summation as follows:
(55 Pr
(2)
2+
Eg
s 111-2var ((1-))o))
(2)
d
S0
256
20

---

(1+ 2 + 2cd) 13
768
(1 2/ea) j
As 2 k(1 2) with 1, then
(1 [1+2//a 2/c
+ 2cd) 1b
(1+ (1+2 2/ca + 2ca)
768
S 768
(1 2/dc)
(1- /ca) (1 2)
2 7277va
- 768
2 - /v
- 270801,
(18)
(142 because (1-2))=)(1-t)
is maximised for d Let C" 270801. If d 1, by plugging Eq. 18 in Eq. 15, we have that
RK -1
(E(E) n
c( nes)"
E
n,k
Pr
P
E
[T
(E)
Pr
So
Pr
So
S,
P = k-
(E)
1= $
Pr
So
kk
(c(E) So
Pr
n&g,
s
Σ
= =k))
C.
==
Pr
So
As Pr
50
(3)
< Pr
(3)) 50
then
kー $ -1
Pr cl)) (
cl3)
& NES,
=(($ns(=k=s)
+ +C
(E))
2
Pr
So
Pr([Sns' = k- j) C²
(E) Pr
So
1=0
Pr Pr(SnS' S
k
+ C
(19)
((()) Pr
So
Notice that, d 1, the same bound holds Pr (ISnS)> b) 0. We now observe that, by the law of total probability
k. Pr (SssS))
Σ
Pr (s Pr
SSSS
k S= s=$) $)
(20)
d
SE(T.)
Conditional on S = $$ S' is hypergeometric random variable with
1.2
E |
s = 5 = Σ
= k E =
n
S
21

---

Since 2 k2, then A² < 1. Hence, since Chernoff bounds holds for the hypergeometric distribution [Doerr, 2020, Theorem 1.10.25]
k d
k22 + 1 1) (
Pr [SnS
S $ Pr
SNs'
s= $
7
1)
S exp
-2
k
2
S exp
(21)
d2
Substituting Eq. 21 in Eq. 20 get
k
k
d 2
Pr SSSS
s exp
-2
1
(22)
d
d2
We can now keep bounding from above
by plugging Eq. 22 in Eq. 19:
exp (-2 k (1 2)²
Pr (ISI SosnS1Z 5
+ C²
+ C²
(23)
(55) Pr
((() Pr
Sp
8o
By Lemma 7, and since 1 + 2/caa + 2ca S 2, we have
(1- 4)²)
exp
2/
+
(5) Pr
S
(-2 k (1 1)²))
16exp
C
d
Vi2k
k
d
2
2x
=xpexp
-2
1
+ d d
C
(24)
d2
k
2s
By the hypothesis, since k 2 Cdl
Coglog for large enough C, it holds that
d'
16exp
-2
1
dlog
C'
da
(ddlog' d)
C 16exp
16
<
(25)
where the latter inequality holds as < 1/4.
Plugging the inverse of the expression in Eq. 25 in Eq. 12 we obtain the thesis.
B.2
Kernel Pruning
Proof of Lemma 11. S2 E {0, 1) size is such that = =V
contains only non-
negative edges going from each input channel to the output channels 2(t-l)n++,,... 12t-1) 1)m, and only non- non-positive edges going from each input channel to the output channels (2t-1) 1mm--,mm+-...- 2tn, while all remaining edges are set to zero. Let us define some convenient notations before proceeding
We consider 0 to be both non-negative and non- non-positee positivie
22

---

with the proofs. By [n m] we denote the set {n, n .......,! mm } for each pair of integers n S m E N. In formulas, we obtain a tensor such that, for each (t, k:) E [c] x [2nc]:
Vi.I. Viaasso ViLLe
if E [(21 2) + 1: (21 1) n|
(vo$) S
Vi
if [ 1) + +1: ::2mm]
(26)
111k
otherwise.
To simplify the notation, we define the following indicator functions: for any (t, k) E [c] [2nc].
In [[--1,1- = 1 iff k E [(21 - 2) n + + (21 n] and
1 2m
E = iff k E [(2t 1) n + 1 2tm].
(27)
For each ki,j,k) E [D] [D] x [2nc]. applying Eq. 26 and using Definition 10, then holds
④
V + 3 * xx)
i.
Ca V.I.i.Xiisis
0
(Vi., Inaaaaol An 1(t-1,1-)) =
Vi,. In =c((-3a1)
(ViLi (Xist X(g.)1 an 1(1-111-)]
(X x an elt- (1))
(28)
Observe that only one term survives in the summation in Eq. 28, as there exists only one f E [co] such that &s E [(tt 2)n 1: 2tn], say t², Moreover, of the four additive terms in the expression
(X 1. x1 d. 1,---1--- "
X )1
at most one non-zero, due to Definition 10. The ReLU cancels out negative ones, implying that Eq. 28 can be rewritten without the ReLU of only non-negative terms (out of which, at most one is non-zero) as follows
Σ (Vitia XTjell an (1-11_11)]
"I -x &
an (e((t-b)))
Σ 1=1
ijtt an [(1-1,11]] + V V Kize in (.((-11)))
(29)
& Finally, by Eq. 26 and Eq. 27, I.1., = 0if
Vi
žn & (t - 1, f] and Vi O In (t ( t,
which means that in Eq. 29 we can ignore the indicator functions and further simplify the expression
Vitnne ((((-1111]] + NTsic in (E(()))))
23

---

Kilee ligt +
Σ
t=1
(++ x x
V * x-)
Proof of Lemma 12. Adopting the same definitions as in Lemma 11 (and Eq. 26), for each (r, 8, (1) E [d] x [d] [ci] have, by Lemma 11,
U *
(
+ 5) * x)) r,8,t1
U
(i+ X + (i- xx xx=))) r,a,
Σ
Uniiiiies ((it +v-(( (0=xx))
iJE (JE](),
Σ
Σ
V+ 1,1,ook Xp-et1,054110
iJE (Ennel
foEleal
Vi
X
Σ
Σ
(Ursaner V+t (1t11om)) x
toEleal kE|2noo)
+
Σ
E
X - (Ueskm Vileok)
[oE[ca]
(E(encl
Σ
Σ kE/2ncal
X X Uijkktt Vitsoo
foEccl
Uniibies Vi..Sook RE(2mco)
Σ
We remind the reader that $ = S1 @ S2, with S1 being bn-channe- mask and S2 being mask that removes filters. Detine L Lisoo. Ene(nol Uijik.t V V.L.ta. and, similarly, Li
Eke[ne] Uiijktt Vi.a Then,
Σ
Σ
Uijkkt Visso
X X
Ar [mca]
Unihhte V..t.ook
-X
to
AE|nool
Σ
x
+
I X--t111-5+166
We now show that, for each to E [co], K...to.: can be e-approximated by L L. by suitably pruning + i.c by further zeroing entries of Š, and that such pruning corresponds solving an instance of MRSS according to Theorem 5, The same reasoning applies to K and L-
For each E [co], let
((t)
{R= ((21) 2) 1,...,,21,,, - 1) n) : $11160.k11
24

---

Observe that m consists of the strictly positive entries of Vi, i. Since the entries of V follow standard normal distribution, each entry is positive with probability 1/2. By a standard application of Chernoff bounds (Lemma 16 in Appendix A), we then have
Pr
(1)
12 3
2
(30)
4'
provided that the constant C' in the bound on n is sufficiently large.
For each & E r(ta), up to reshaping the tensor as one-dimensional vector, U...k,."" V. 1,1.to.& is an NSN vector (Definition 4) by Lemma 18 (Appendix B). Thus, for each to E [co] and sufficiently- value of C, since we have n 2 Cd log" do we can apply an amplified version of Theorem 5 (i.e. Corollary 19 in Appendix B with vectors of dimension ef to show that, with probability 1 __ for all target filter K such that II: S 1, there cxists way zero the entries indexed by T440) of $ (and thus Vil....). so that the pruned version of L Liitta Exe(noo] UniAk. V 1.,..
approximates K, In particular, there exists another binary mask Sg E {0, 1 & such that L : = Exe(nea) U...; Vi,1, approximates K, where V = V O Sg An analogous
argument carries on for a binary mask Sz and -L More formally, let
(kemel)
(0, 10, S JK: || 1 S 1.3
[ Kendooi ||
E 2dcccco
to.-
max
tto--
(kemel)
AK |||]| S 1,3355 f0, 1
Lisntos + Kisitosi
e 2d2c100
and
max
g(kemel)
(kermel) tto.-
elkernet) Eto,- [oE(Co]
[oE[co]
Then, by Corollary 19,
(kernel) tta+t
- [ta]
71
E
Pr
2 1
-
and
3
4co
(kemee)
[tab
n 3
E
Pr
to.-
2
4co
By the union bound, we have the following:
Pr
E
(kermel)
[ta)
=1 Pr
E (kernel) &toit
U
(kemel)
[x(oo)
n2 |r(t))
f0,-
3
M0E(co)
[oE(ro)
2 1 Σ
Pr
(kerne)) Etart
[(o))
(10)
12
+ Pr
(elhemel)
|
1
n
3)
(oE(co)
2 1 - 2
Σ
4co
toE/oo]
8
21
2
Since Pr (1r400)
| > 3) z 1-
S. then we can remove the conditional event obtaining
Pr (g(kernet))
> Pr (Elkemel))
|.| |
3 Pr
| (0)
"Notiee that excluding zero entries implies conditioning on the event that the entry is not zero. However. such an event has zero probability and, thus, does impact the analysis.
'The negative sign in front of L, does not affect the random subset sum result as each entry is indepen- dently negative or positive with the same probability.
25

---

5 2
2
(31)
To rewrite the latter in terms of the filter K and mask S, we notice that pruning L L and L, separately, with two binary masks, is equivalent to say that there exists single binary mask S3 E [0,ies such that, Ly can be written as L.,,t Exe(nou) U.A.k V1.1, where V = V S3 Ineq. 31 implies that, with probability 1 - E, for all target filters K with ||]]| S 1 such S3 exists and hence,
K - 1+
+
K
i
(32)
deccoo
max
Let S = $ o Sy: then S = S1 o S2 O S3 is the combination of 2n-chamnel-blocked mask $ = S and a mask S2 @ S3 that only removes filters.
Also, whenever such binary mask $ exists, whe have that
K * X -2( (x)
sup X: [XI SM
max
K * X - + (V (VOS)- x)) max
sup X: || SM
K * X - U ( 50 Sz) + +x) max
sup X= | S.
K (x+ - -x-) U -U ((+*x**) x + (v * x xx)) max
sup SM
X:
where the latter holds by Lemma 11.² Then, by the distributive property of the convolution and the triangle inequality.
K * (x+ (x+-x- xx- -U ((V+ * xxt) +
sup X-I| mmne SM
max
K K*x+ + (p+*x*) K * x (v- * xx-) max
11=xx-)
sup
XI SM
K X U (pt (p+*xt) Imnx
$ sup
SM Il
K*X +U (v~xx*
x x xx) max
sup
One can now apply the Tensor Convolution Inequality (Lemma 20) and obtain
K K* -U U (v+*** xx++)
sup
X:
SM
K*X +Ux+ * (v- x
sup
X mlx ZM
max
||xt
max KK U v+ |1|
sup
X:IIX Ilaae S.M
sup
X
[K+U+0 v 1,
max
X:I|X Imax <M
M
K - U V+
M
K + V
Now, observing that the number of entries of the two tensors in the expression above is decroo and using Ineq. 32, we get that
M
K
- U * V+
+ + K- U U V- -
K-
Thh presence of So does not influence the proof of Lemma 11.
26

---

c10 (1 (K- V+
U
+
K U V-
max
max
S c &2cico
=eM.
proving the thesis.
Proof of T'hhorrm 2. To bound the emror propagation across layers, define the layers' outputs
X X, X (K() * x( for ssise.
(33)
Notice that X is the output of the target function, i.c., f X(O.
For brevity's 's sake, given masks 5(2i-1) {0, (iizz([ (2--1) 1. for each i I...., E, let us denote
[ L (2i 3 s(2i-1)
(34)
We now show that the random network approximates the target one after being pruned only at layers (2(2i1)) for all 1,....& f, by masks S(2i-1) which are the composition of 2 blocked mask and mask that only removes filters. The key idea is to iteratively applying Lemma 12. Since the ReLU function is I-Lipschitz, for all it holds
0 [K00 xx((-1) - Φ (I * (i(20-1) (x(-11) < | * x((11) (2200 * (1,00-1) x((i1)) max
max
(35)
The key step of the proof is that, for each layer i, since n, > Cd log dan 1f for suitable constant C,, we can apply Lemma 12 to get that, with probability at least 28. choices of target filters (0) E Rd:x; xe; 1xe it holds
for all i and for all
|K(O ((-1) (26) (i x max
E
|
(36)
28
Hence, combining Eq. 35 and Eq. 36 we get that, with probability at least 1 choices of target filters ((t)) [ddxxixxa 1xe: with | 11
28. for all i and all
o é x((-1)) - (L ( (i x x
(x(() (K
max
| max
(37)
2/
By union bound, with probability at least 1 e, we get that Eq. 37 holds for all layers i and all choices of target filters ((O) E xdxxdxxe--xx0 Analogously, we can define the pruned layers' outputs
(0) X,
( = 0 (1 * (i ( (1zii1)) x((-1))) for sise.
(38)
Notice that (1) the output of the pruned network, i.e. ( s(20))
(X)=
By the same reasoning employed to derive Eq. 36 and Eq. 37 we have that, with probability 1 for all layers and all choices of target filters (()) E Rd xd,xxxxx-- xx-xxxx-10 1x6, the output of all pruned layers satisfies
1xx,
0 K10 * x((-11) - o (1220 * (((2i-1) x(6-1)) max
8 |
|
(39)
28
max
27

---

Moreover, for each 1 si by the triangle inequality and by Eq. 39,
=
|| (K x( + + (K * x((-1)
max
max
$ | @ (K(1) x11-111 + -116 (x1)) x(1-))
max
< X (i(1)))
+ +110 (K(0) * f((-))
20
max
By the Lipschitz property of Φ and Lemma 20
E
X
1)
+
(r = -
2
max
max
(Ki) * (((-))
+
2
max
max
|
maX |
+
2/
max
x
(1+
max
2/
By unrolling the recurrence, we get that, with probability K00 E xedxxxxes-ixei
E, for all choices of target filters
<
X (0)
(1 +
E 2
(40)
max
Thus, combining Eq. 39 and Eq. 40, with probability - 5 we get that, for each E [$] and for all choices of target filters (())) E Rdd xd, xex Xe.
[ x(- - [(20) & ((2i11) x((-1)
8
8 1-111 (1+ )
|
(41)
28
28
We then see that with probability 1 E, for < i i l and for all choices of target filters (0()) e Rd x6 1xG, by Eq. 33 and Eq. 38, and by the triangle inequality.
( x
max
(K x((e
(1 & (I +1(00)(( xX x max
K x(((11)
(K(0) x(((11) max
10 ( x((-1)) - (1.2)) x (1 X x(- max
+
Again by the I-Lipschitz property of the ReLU activation function, and by the distributive property of the convolution operation.
( ( + Φ (K10, x I
| (K10 x((-1)) - -0(1120) @b (i,06-1), x((-1)))
max
R(0 ()e-1) k(9,, x((-11) max
+ | ()) 1100) o (i * xx00xxx((11111)1 x((-1))
k100 & (x((-1) - x((-1))
+ +||x(0) x((-1) 11200, o (i,20-1)) x(e-1) max
Lemma 20 and the hypothesis
|K(00| 5 imply that
|r10), (x(c-1) - x((-1)) max
28

---

1110 x((-11 -(20) * & (i x((-11)
K 1 (xx(6-1) - -x((-11) max
10(00 * x((e1) - I(20) * * (i((-1) x((-11)
( (x((-11 - -
[100 x(e-1) (2))) (i x((-1)) max
Now, we first apply Eq. 41 and then we unroll the recurrence for all layers (as, with probability 1- E, Eq. 41 holds for all layers and for all choices of target filters K(6) Rd,xdx xdxx-xxxex) obtaining
(((-1)) x((-11
max
+ [r x(e-1)
I((20
* Φ [1126-1) x((-1)
max
x((-11 8 max
(1+ E E)(-1 t-1
+
28
< Σ
(1 E)
5-1 j-1
1=1 26
20
By summing the geometric series and observing that 1, conclude that
j-1
Σ
1 +
1
2
1=1
S -1
E.
Hence,
|x(0 |x(0- - x10)
-x10)
E,
max
yielding the thesis.
29


Reviews:
[{"review_id": "0GfZ0PtP7n", "reviewer": "Reviewer_LtV9", "summary": "This paper extends analytical work on the strong lottery ticket hypothesis from unstructured to structured pruning, and shows the applicability to Convolutional Neural Networks.", "questions": "- In Lemma 8, you deal with variables X_1 through X_{k+j}, but then only condition on Z_1 through Z_k in the text, and Z_1 through Z_n in the statements. It's entirely possible that I misunderstand, but is all of this correct? For example, n is never even introduced as a number.\n- I don't quite understand why the n-channel-blocked-masks are needed. In definition 2 you mention that this defines the structured sparsity of the networks, but doesn't the removal of entire filters by itself already constitute structured sparsity?\n- Related to above: In Lemma 12 you describe the network including the channel-blocked-masks as the \"pruned\" network, but from this we still need to remove filters to obtain the smaller network that appropriately approximates K. So which action exactly constitutes the pruning?\n- In Lemma 11, you state that V * S-tilde \"contains only non-negative edges going from each input channel t [...]\". How can that be? V has arbitrary real numbers, and S-tilde is a binary mask. Maybe I've missed something here, I could see that statement be made when including the ReLU in some way, but I'm a bit lost the way it is now.", "limitations": "The authors have appropriately addressed limitations in Section 5. Questions on societal impact do not apply here.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I'm not an expert in this domain, but both the contribution looks strong to me.\n\nClarity:\nThe introduction is extensive and appropriately places the current paper into the existing research landscape. I could follow well, even though I'm not directly in this domain. In the analysis section, proofs and other statements are appropriately accompanied by explanatory statements, which makes following them easier.\n\nQuality:\nThe paper is of high quality. It advances a subfield that is actively being researched.\n\nOriginality:\nTo my knowledge, the work is original. It extends various previous work in a non-trivial manner. The authors place the contributions appropriately among previous results and reference related work.\n\nSignificance:\nI really cannot accurately estimate the significance of this work. The overall question around whether structured sparsity in CNNs can induce strong lottery tickets is certainly significant. I'm not sure how much the used structures in this work (for example, every other layer being a 1x1 layer) limit the significance of the results.", "weaknesses": "- I would have liked to see at least a small experimental section, as the discussed topic lends itself well to empirical evaluation.\n- As I said above, just reading the paper gives me very little insight into the meaning and significance of these results, which could be discussed more extensively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work and the valuable comments. We try to address all concerns.\n\nWeaknesses\n1. Please refer to point 3 of the general answer.\n2. We will expand the text in the main body of our document to further discuss the significance of our results by recovering some of the contextualisation from previous works. \n\nQuestions\n1. We apologise for the typo. There, $n = i + k$ and all the shown probabilities are conditional on the outcomes of $X_1, \\dots, X_n$. In the supplementary material, the indices in the conditional event are correct (but we forgot to explicitly state $n = i + k$). We updated the main text and the SM accordingly.\n2. The removal of entire filters does constitute structured sparsity. However, besides choosing which of the (random) filters to keep, we also need to ensure that those are effectively combined in a way that allows us to leverage our MRSSP results to approximate target filters. We achieve this through the $n$-channel-blocked structure. Put loosely, while filter pruning allows us to select subsets (of filters), we need other structures to ensure the subset is “summed” in a suitable way. Of course, the desired operation has many more nuances than a simple sum.\n3. (and 4) We agree that the text around Lemma 11 is unclear. There are two ways of looking at the pruning in Lemma 11. The mask can be seen as a channel-blocked mask that is applied only to some filters, i.e., we keep filter $k$ if its $t = \\lceil \\frac{k}{2n} \\rceil $-th channel is non-negative and $2t-1 = \\lceil \\frac{k}{n} \\rceil $  or it is non-positive and $2t = \\lceil \\frac{k}{n} \\rceil $. Formally, one can again use a combination of two masks: the first one is a $2n$-channel blocked mask, the second one removes filters. We clarified this explicitly in the statement and proof.  \nThe pruning in Lemma 12 consists of the actions described in Lemma 11 – the application of the channel blocked mask and the filter removal based on entries’ signs – plus another step of filter removal given by the MRSSP result. We realise that this might cause some confusion, and we added some sentences that explain that all these three parts define the final pruning.  When looking at Lemma 11 and 12 together, one can see a three-stage pruning process: application of $2n$-channel blocked masks (1st stage), filter removal according to entries' signs (2nd stage), filter removal given by the MRSS result (3rd stage). Since masking is both associative and commutative, one can look at the whole process as follows: First, we apply channel blocked masks (1st stage). Second, we remove filters (combination of the 2nd and the 3rd stage).\n"}, {"review_id": "e8Qw1K4Ldq", "reviewer": "Reviewer_ryBt", "summary": "The authors show that structured Strong Lottery tickets are contained within convolutional neural networks.\nIn order to construct this proof, the authors propose the Multidimensional Random Subset Sum lemma which approximates a target vector by using a set of random vectors which are normally scaled normally distributed.\nThis results builds on the Subset Sum approximation by Lueker, which is commonly used in proving the Strong Lottery Ticket hypothesis for standard architectures.\nThe authors further leverage this lemma to approximate a target function with a structurally pruned CNN which is twice as deep and wider by a factor.\n\nOverall this paper provides an important existence proof for strong lottery tickets in structurally pruned CNNs as a first step in trying to understand structured pruning theoretically.", "questions": "1. The construction requires a layer of width $n c_0$ such that after pruning the width is $m c_0$. These factors would effectively determine the overall sparsity a network can achieve. Would this translate to structured pruning results we observe in practice?\n\n", "limitations": "The authors provide their construction for ReLU networks. However, Burkholz et al. [1] show existence results for different activation functions.\nDo the proposed existence results also transfer to other activations?\n\n[1] Burkholz, Rebekka. \"Most activation functions can win the lottery without excessive depth.\" NeurIPS 2022", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors for the first time have proven the existence of SLTs in structurally pruned networks giving hope that a computationally efficient and trainable SLT might exist that can be leveraged for efficienct on existing hardware (contrary to current empirical results in literature which are worse than unstructured pruning).\n2. The authors also extend the result of Lueker for random vectors.\n3. The paper is clearly written.", "weaknesses": "1. The bounds provided by the authors still require twice the depth in order to approximate a target function. Burkholz et al have proposed a way to use only L + 1 depth to approximate a target function. Is this still possible with structural pruning in CNNs?\n2. As mentioned by the authors, the proposed construction looks at structured pruning where entire channels are pruned away. Would block sparsity (eg; N:M sparsity) allow for a better Subset Sum bound potentially i.e. are there specific sparsity patterns which can allow sparser constructions. This might guide us towards a identifying layerwise sparsity ratios for training sparse networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for all the observations pointed out in the review. We try to address the weaknesses, the question and the limitation.\n\nWeaknesses\n1. We believe it is possible, but so far we could not check all the necessary adaptations. Such improvement requires further investigation.\n2. In principle, yes. The size of the “structure” to be pruned (be it a filter, a “block” or something else) decides the dimensionality of the Random Subset-Sum Problem to be solved, so, in general, one can expect better bounds from more fine grained pruning. Of course, in the limit, one would obtain the best bounds by considering “blocks” with a single weight, recovering the unstructured pruning case. Thus, one must keep in mind the trade-off we discuss in the paragraph from lines 51-59. Overall, we have not considered $N:M$-sparsity, but we think this is a promising direction for future work.\n\nQuestions\n1. We do not think so. To recapitulate, our results involve transforming a dense convolutional layer with $nc$ filters to obtain a (still dense) one with $mc$ filters, where $m = O(\\sqrt{n/\\log 1/\\epsilon})$, so that the final network is potentially much smaller than the original one (see, e.g., lines 147-150). However, we expect improved bounds on $n$ to bring $m$ closer to $n$.\n\nLimitations\n1. We do believe the result holds for a more general class of activation functions: however, we do not see a trivial way to prove this and further investigation is required. We remark that, as discussed in the limitations section, we do not think that the technique used by Burkholz [2022] can be immediately adapted to our case because we use the fact that the ReLU function gets rid of negative terms.\n"}, {"review_id": "yQlJoACDIU", "reviewer": "Reviewer_TQCH", "summary": "The paper investigates a structured version of strong lottery ticket hypothesis (SLTH) for CNNs, which is important for its computational efficiency against the standard unstructured counterpart. For this purpose, they prove a variant of subset-sum lemma for their situation. Using their subset-sum lemma and splitting lemma for ReLU activations, SLTH for CNNs is proven by combining block-pattern pruning and neuron pruning under the assumption that the network size is polynomially larger than a target network.", "questions": "1. Can the proof also work for the easier case of MLPs instead of CNNs? Is the variant of subset-sum lemma in this paper also needed even for MLPs? If so, providing some intuition for MLP case may be helpful to understand the structured SLTH. If not, discussing why your version of subset-sum lemma is needed for CNNs would be helpful for readers.\n\n2. Is the structured version of SLTH with polynomial over-parameterization really practical? I wonder if we can find such a structured subnetwork in randomly initialized CNNs (or MLPs) in a similar way to Ramanujan et al. 2020, where the unstructured version of SLTH is actually observed.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. SLTH by structured pruning is an important topic in terms of applicability and computational efficiency of SLTH. The authors are the first to prove the structured version of SLTH for CNNs.\n\n2. They extend the subset-sum lemma, which is a key lemma for SLTH with logarithmic over-parameterization as shown in Pensia et al. 2020, for their purpose.", "weaknesses": "Presentation:\n\n1. Although the overview of their proof is straightforward, the presented proof does not provide any intuition for the evaluation of the required network size.\n\n2. No experiments are provided. Since the structured version of SLTH itself has not yet observed empirically even for MLPs or CNNs, some experiments would be helpful for supporting their claim.\n\n3. They claimed that `To the best of our knowledge, this is the first result around the SLTH for structured pruning of neural networks of any kind` in Introduction, but the previous work by Malach et al. 2020 already provided results on the equivalence between SLTH by neuron pruning and random feature NNs in the 2-layer case.\n\nResults:\n\n4. Even though they use a variant of subset-sum lemma following the approach by Pensia et al. 2020 for logarithmic over-parameterization, the required width in this paper is still polynomially larger than the target one. In this point, I wonder that, If one allows such polynomially large width, the structured version of SLTH might be easily proven by simply extending the previous discussion in Malach et al. or Pensia et al., at least for MLPs. Also I wonder that whether their claim is still valid in practice due to such polynomial over-parameterization. Nevertheless, the first attempt to prove the structured version of SLTH is worthful in itself. I hope the authors would emphasise which technique in their proof is important for either structured pruning or handling CNNs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful to the reviewer for their time and comments. We address all main concerns.\n\nWeaknesses\n1. We apologise, but we are not sure we understood the issue brought by the reviewer. The polynomial overparameterization comes from recent results on the multidimensional random subset sum problem for independent input random vectors ([Borst et al. 2022; Becchetti et al. 2022]) which we extended to the case of dependent inputs (Corollary 19 in SM A) and used in Lemma 12. We remark that Corollary 19 deals with roughly $d^{6}$ input vectors of dimension $d$, while in Lemma 12 we have vectors of dimension $ \\approx d^2$: that is why we get a bound of the form $ n \\ge d^{12} \\dots$\n2. Please refer to point 3 of the general answer.\n3. We thank the reviewer for spotting this mistake. We rephrased the sentence in the abstract to specify that we tackle networks of arbitrary depth, and in the main body to credit Malach et al.\n4. Please refer to the first point of our global reply.\n\nQuestions\n1. We directly approached the CNN case to obtain a more general result. Nonetheless, the structure used in our argument does not produce particularly meaningful results for the MLP case, where one would ideally be able to prove the SLTH for pure neuron pruning. We are currently working on this. Regarding the subset-sum lemma, formulating any type of structured pruning as an instance of the subset-sum problem would require a multidimensional version of the problem. Yet, the specific variant will depend on the target structure.\n2. Empirical studies with a structured version of edge pop-up [Ramanujan et al., 2020] is a natural and very interesting direction for future work. We also highlight that we provide worst-case bounds and that we do not believe they are optimal. So, much like what we see with unstructured SLTH algorithms, we expect structured versions of them to perform better than the theoretical worst-case guarantees.\n"}, {"review_id": "XkyPwUF7Hd", "reviewer": "Reviewer_Ewpx", "summary": "This paper tries to discuss the Strong Lottery Ticket Hypothesis (SLTH) in the context of structured pruning in convolutional neural networks (CNNs). The SLTH suggests that randomly-initialized neural networks possess subnetworks that can perform well without any training. While unstructured pruning has been extensively studied, the paper explores the less explored area of structured pruning, which can offer significant computational and memory efficiency gains. The authors overcome the limitations of existing mathematical tools by leveraging recent advancements in the multidimensional generalization of the Random Subset-Sum Problem. By introducing a variant that accounts for stochastic dependencies in structured pruning, the paper proves the existence of structured subnetworks in random CNNs that can approximate smaller networks. This theoretical contribution extends the understanding of the role of overparameterization in deep learning and opens new avenues for further research on the SLTH for structured pruning.", "questions": "See weakness.", "limitations": "The limitations of the proposed analysis have been discussed in this paper.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses an important research gap by focusing on structured pruning in the context of the Strong Lottery Ticket Hypothesis. This expands the understanding of lottery ticket mechanisms beyond unstructured pruning.\n- The authors make use of recent advancements in the multidimensional generalization of the Random Subset-Sum Problem, demonstrating their ability to leverage and adapt existing mathematical tools to overcome limitations in formal analyses of the SLTH.", "weaknesses": "The SLTH theory is important in both the pruning and neural network architecture search domains. However, I'm not familiar with the specific analysis methods proposed in this paper, so I can't provide professional advice.\n\n- Line 118, \"Preliminaries and contribution\" -> \"Preliminaries\"?\n- In this paper, if the convolution kernel $K$ relies on the normality assumption, as mentioned in Line 131, I suggest the author can cite the Convolution Weight Distribution Assumption discussed in [1].\n- If possible, I recommend that the author use more intuitive language when writing Section 4 and the introduction. This would help researchers in the pruning and neural network architecture search fields to better understand the contributions of this paper.\n\n[1] Huang Z, Shao W, Wang X, et al. Rethinking the pruning criteria for convolutional neural network[J]. Advances in Neural Information Processing Systems (NeurIPS), 2021, 34: 16305-16318.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and the comments.\n\nWeaknesses\n1. We can change the section’s title but we remark that in Section 3 we state our contribution more formally and, to do so, we need to introduce some preliminaries.\n2. We thank the reviewer for the reference. We will add it to the text.\n3. We will try to improve it.\n"}, {"review_id": "nd5B1Bm9Gp", "reviewer": "Reviewer_Up5n", "summary": "The central theme of this paper is the Strong Lottery Ticket Hypothesis (SLTH), which conjectures that « randomly initialised networks contain sparse subnetworks […] that perform well without any training » (lines 26-30). Pruning large networks in order to obtain those « strong lottery tickets » would be a way to limit the computational costs associated to those over-parameterised networks and facilitate their deployment in real-world applications. The SLTH has already been theoretically verified for various classes of networks, but never while restraining the way the pruning must be done in order to obtain those « strong lottery tickets ». The authors aim to theoretically verify that « strong lottery tickets » can be obtained via structural pruning of a certain class of convolutional neural networks. The way they do it is by proving that « networks in a wide class of CNNs are likely to contain structured subnetworks that approximate any sufficiently smaller CNN in the class » (lines 77-79), based on the assumption that their exists a «  sufficiently smaller CNN in the class » that performs well.", "questions": "1. Exactly which lemmas are original and which have been taken from the literature?\n\n2. Is there a reason why you specifically chose having filters (or channels) being removed as structured pruning technique?\n\n3. The third contribution states that « Additionally, our pruning scheme focuses on filter pruning, which, like neuron pruning, allows for a direct reduction of the size of the original CNN » (lines 86-87) (which is not a contribution, but an argument assessing the relevance of the work). It is also stated that « through unstructured pruning [...] one can usually reach 95% sparsity without accuracy loss » (lines 54-55). One could argue that by reaching 95% sparsity, the size of the original network is likely to diminish too. From that perspective, why would channel-pruning still be more desirable?", "limitations": "Limitations have been discussed properly, apart from what has been raised in the Weaknesses part of the review.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The manipulated concepts, such as the LTH, the SLTH, or the RSSP are well-explained.\n\n2. A clear understanding of the many proofs can be obtained by reading Section 4.", "weaknesses": "_Major_\n\n1. The proof ideas are not that novel. Many cited works from the Related Work section use the same technique in order to obtain similar results, and Theorems 3 and 5 are the only contributions of the paper (lines 81-85; see Question 3).\n\n2. The goal is to demonstrate that winning tickets from the SLTH can be obtained by removing channels from a deep and wide CNN. The underlying assumption here being that there exists a CNN having the same restrictions as discussed in the article AND that is significantly smaller than an over-parameterised one is in fact capable of obtaining good results on given tasks. Considering those limitations (no classification head, that is, no fully-connected layer; no pooling layer; no batch norm layer; ReLU activations only; etc.), such an assumption is not trivial and questions the whole process.\n\n3. The justification for the approach is that for over-parameterised networks, « [their] associated computational cost limits both the progress of [the neural networks in general] and their deployment in real-world applications. » (lines 19-20). Therefore, the justification is on a practical level. But considering the size of the kernels needed for the network to be pruned (with $n_i \\geq Cd^{12}c^6_i ...$, line 139), from the practical point of view, it is virtually impossible to encode such a network even before considering pruning it (which would then be a fastidious process and would imperatively be done in an efficient manner, which is not discussed in the article). \n\n4. The end-goal is to obtain a relatively small network, but taking $n_i \\geq Cd^{12}c^6_i ...$ (line 139), and plugging it into $m_i = \\sqrt{n_i / (C₁ log \\frac{1}{e})}$ (line 150) leads to $m_i \\geq d^6c_i^3...$, which do not seem to produce a network that would be smaller.\n\n\n\n_Typos / Minor_\n\n1. The way the citations are made is inconsistent throughout the paper; their are both appropriate (« The constructions proposed by Burkholz [2022a,b] », line 290) and inappropriate (« both in the past Reed [1993] and in the present [...]. », line 21) inline text citation format.\n\n2. Line 58 : or block sparsity Siswanto [2021] (Figure 1$\\underline{c}$).\n\n3. Some statements are not supported; for example : « Much of the success of deep learning techniques relies on extreme over-parameterisation. » (line 17).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their time and valuable comments. We hope to clarify some issues brought up by the reviewer.\n\nWeaknesses (major)\n1. While our proof is based on a well-known probabilistic technique (the second moment method), our analysis is entirely novel, except for the Young’s Convolution Inequality (underlying Lemma 20) and the technical tools in SM A.1 (Lemmas 14 to 17). All other lemmas and corollaries are new, including those in the main paper. Most notably, our work explores the MRSSP in the presence of dependencies, which is of interest on its own, as appreciated by other reviewers. Despite being similar in spirit to previous works [Borst et al. 2022; Becchetti et al. 2022], the need to overcome stochastic dependencies required new proof strategies in all lemmas related to the SSP. Moreover, we remark that the average behaviour of the multi-dimensional SSP is an active field of research and that attempts to tackle it with more sophisticated probabilistic tools have, so far, not been fruitful (see, e.g., section 3.1 of Becchetti et al. [2022]). As for the pruning section, despite apparent similarities with previous works (e.g., Pensia et al. [2020], da Cunha et al. [2022], and Burkholz [2022]) in applying subset sum results to convolutions, the change from unstructured to structured pruning requires a different formalisation of the problem. Those arguments are closely tied to the structures obtained when pruning the network and we had to devise a new one to obtain a set up that allowed for selecting and summing subsets of entire filters.\n2. We highlight that convolutional layers are quite expressive and generalise many other transformations, such as dense layers, batch normalisation and average pooling. Our restriction to ReLU activations is in line with most works in the field and, as discussed with Reviewer ryBt, there are reasons to believe it can be relaxed. \nWe also believe that an alternative (but equivalent) framing of our results may make the relevance of our contribution more clear to the reviewer. For **any** given random CNN, we wish to know how well it can perform after pruning (without any training). Our results imply that, under suitable hypothesis, it can perform almost as well (if not better) as **the best** CNN among all those that are sufficiently smaller than the random CNN and whose weights can be tuned. In particular, such class includes traditionally trained networks.\n3. (and 4) Please refer to points 1 and 2 of the general answer.\n\nWeaknesses (minor)  \nWe thank the reviewer for the notes about minor issues. We have addressed all of them.\n\nQuestions\n1. Please refer to the answer to weakness number 1.\n2. (and 3) We attempted to convey the reasoning behind it in our introduction (mainly in the paragraph starting at line 51), but we acknowledge that this aspect can indeed be counter-intuitive. Concentrating on dense layers for the sake of simplicity, the key point is that making an $n \\times n$ matrix 95% sparse does not translate directly into a speed-up of the associated matrix multiplication. For example, if one naively performs the multiplication directly, there are no computational gains whatsoever (the BLAS pipeline is oblivious to the sparsity of the matrix). Of course there are nuances to the matter, as we discuss in the introduction. On the other hand, if the sparsity in the matrix is conveniently structured, even if the degree of sparsity is much lower, the sparsity directly translates into computational performance, potentially offsetting the difference in sparsity. E.g., if 50% of the rows/columns are filled with zeros, rather than storing those rows/columns, we can simply drop them to obtain a (still dense) smaller matrix. Doing so requires no memory overhead, directly translating into a 50% reduction in the memory footprint, while also speeding up the associated matrix multiplication regardless of software/hardware intricacies.\n\nWe hope that we have responded satisfactorily to the reviewer's comments and that our response will lead them to appreciate our work more. We look forward to answering any questions the reviewer may still have."}]

Author rebuttal:
We thank all reviewers for their valuable comments. We are pleased that reviewers appreciated our contribution. Only one of the evaluations leaned towards the negative, and it seemed to be due to misunderstandings that we hope to have solved.

Some reviews brought similar questions, to which we reply below. We also modified the text to further clarify those points.

1. **Our bounds are not optimal**: Directly applying techniques from previous works on the unstructured SLTH to the structured setting would yield exponential bounds (even for the MLP case). Thus, our contribution extends the field qualitatively by showing that polynomial overparameterization suffices. Much like the original polynomial bounds for the unstructured case by Malach et al. [2020] were improved by subsequent works [Orseau et al., 2020; Pensia et al., 2020], we expect our contribution to pave the way for further research and consequent sharper bounds.
2. **We offer a theoretical contribution**: While our work is motivated by the practical concerns underlying structured sparsity, we do not propose a practical algorithm for finding strong lottery tickets. In line with many works related to ours (e.g., Pensia et al. [2020], da Cunha et al. [2022], and Burkholz [2022a,b]), we instead offer theoretical insights about the problem. For example, we establish a baseline for the potential performance of SLTH algorithms. Such a contribution opens the door for valuable future directions, including the extension of SLTH algorithms such as edge pop-up to the structured setting. Finally, our analysis and that of previous works investigate the worst possible case for those algorithms. Thus, they do not set an upper-bound on their practical performance on common architectures.
3. **Experiments are unfeasible for this work**: We agree that experiments would be interesting to see. However, performing meaningful experiments by directly solving subset-sum problem with solvers such as Gurobi (as in, e.g., [da Cunha et al. 2022] or [Pensia et al. 2020]) would be prohibitively expensive as the multidimensional version of the SSP is much harder to solve directly. An alternative would be to extend an algorithm such as edge pop-up [Ramanujan et al., 2020] to our setting (structured pruning). This is a natural and very interesting direction for future work, but it is worth a whole paper on its own.


Meta-review: This paper proposes a version of the "Strong Lottery Ticket Hypothesis" that works for convolutional networks and other forms of structured pruning like block sparsity. The reviewers were generally in favor of acceptance (especially after very productive conversations during the discussion period) and I see no reason to overrule them. I think this is a niche problem with limited applicability, but I respect that it is an interesting problem to many and this paper is a productive contribution to that area.
Decision: Accept (poster)