On the Sparsity of the Strong Lottery Ticket Hypothesis
Authors: Emanuele Natale
Davide Ferre'
Giordano Giambartolomei
Frédéric Giroire
Frederik Mallmann-Trenn
Venue: NeurIPS 2024 poster (2024)
Keywords: strong lottery ticket hypothesis
random subset sum
neural network pruning
random neural network
Primary area: learning_theory
TL;DR: We provide the first proof of the SLTH in classical settings with guarantees on the sparsity of the subnetworks.

Abstract: Considerable research efforts have recently been made to show that a random neural network $N$ contains subnetworks capable of accurately approximating any given neural network that is sufficiently smaller than $N$, without any training. 
This line of research, known as the Strong Lottery Ticket Hypothesis (SLTH), was originally motivated by the weaker Lottery Ticket Hypothesis, which states that a sufficiently large random neural network $N$ contains sparse subnetworks that can be trained efficiently to achieve performance comparable to that of training the entire network $N$.
Despite its original motivation, results on the SLTH have so far not provided any guarantee on the size of subnetworks.
Such limitation is due to the nature of the main technical tool leveraged by these results, the Random Subset Sum (RSS) Problem.
Informally, the RSS Problem asks how large a random i.i.d. sample $\Omega$ should be so that we are able to approximate any number in $[-1,1]$, up to an error of $ \epsilon$, as the sum of a suitable subset of $\Omega$. 

We provide the first proof of the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity of the subnetworks. Central to our results, is the proof of an essentially tight bound on the Random Fixed-Size Subset Sum Problem (RFSS), a variant of the RSS Problem in which we only ask for subsets of a given size, which is of independent interest.

On the Sparsity of the Strong Lottery Ticket Hypothesis
Emanuele Natale Université Côte d' Azur, CNRS, Inria, 13S, France
Davide Ferré Université Côte d' Azur, CNRS, Inria, I3S, France
Giordano Giambartolomei
Department of Informatics, King's College London
Frédéric Giroire
Frederik Mallmann- Trenn Department of Informatics, King's College London
Université Côte d' Azur, CNRS, Inria, 13S, France
Abstract
Considerable research efforts have recently been made to show that a random neural network N contains subnetworks capable of accurately approximating any given neural network that sufficiently smaller than N. without any training. This line of research, known the Strong Lottery Ticket Hypothesis (SLTH), was originally motivated by the weaker Lottery Ticket Hypothesis, which states that a sufficiently large random neural network N contains sparse subnetworks that be trained efficiently to achieve performance comparable to that of training the entire network N. Despite its original motivation, results the SLTH have so far not provided any guarantee on the size of subnetworks. Such limitation is due to the nature of the main technical tool leveraged by these results, the Random Subset Sum (RSS) Problem. Informally, the RSS Problem asks how large a random i..dd sample Q should be so that we are able approximate any number in 1]. up to an сгтог of e, as the sum of suitable subset of S.
We provide the first proof of the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity the subnetworks. Central results, is the proof of essentially tight bound on the Random Fixed-Size Subset Sum Problem (RFSS), a variant of the RSS Problem in which we only ask for subsets of given size, which is of independent interest.
1 Introduction
The Lottery Ticket Hypothesis (LTH) is research direction that has attracted considerable atten- tion over the years, stemming from the empirical contrast between the fact that, while large neural networks can be successfully trained to achieve good performance on given task and successively pruned to great level of sparsity without compromising their performance, researchers have strug- gled to train sparse neural networks from scratch. The authors of [12] observed that, using a simple pruning strategy (namely Iterative Magnitude Pruning while rewinding the original weights of the remaining edges to their value at initialization). starting from a sufficiently large random neural ner- works, it is possible identify sparse subnetworks that can be trained to achieve the performance achievable by the starting network (see Figure 2 in the appendix for an illustration). The previous stronger one, corroborated by empirical works statement, namely the I.TH, soon gave rise algorithms (see Section 2 for details), providing evi- [29, 26] which proposed training-by-prunine dence that starting from sufficiently large random neural networks, it is possible identify sparse subnetworks that exhibit good performance as they are, without changing the original weights (see Figure 3 in the appendix for an illustration). By removing the need analyze the dynamics of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

training. the last statement, namely the Strong Lottery Ticket Hypothesis (SLTH), allowed fruitful series of rigorous proofs for increasingyy more general architectures (see Section 2 for an overview). Such rigorous results can informally be stated as follows:
Theorem 1 (Informal statement of previous SLTH results). With high probability, a random arti- ficial neural network No with m parameters can be pruned so that the resulting subnetwork Ns e-approximates (i.e., approximates up to an error E) any target artificial neural network N₂ with O (m/ loga (1/E)) parameters.
It is important to note that, to this day, only have proofs the existence of such subnetworks, also called winning tickets, but it remains an open question how to find them reliably.
All theoretical results on the SLTH however have so far not investigated the interplay between the sparsity of the winning ticket Ns and the size of the random neural network Ng. This is in con- trast to the original motivation of the LTH and to the practical application of the aforementioned mainiingbyy-runingg
algorithms that motivated the SLTH, such as [15, 14]. In fact, to approximate target networks with O (m/ logg (1/s)) parameters, essentially all winning tickets Ng have ((m) parameters (see Appendix A), thus being roughly of the same size of the original network No. We thus ask the following natural question:
If we want to s-approximate family of target artificial neural networks with my parameters by pruning fraction a, called sparsity, of the m parameters of a random artificial neural network Ng. how big should m be?
We are particularly interested in the regime in which the density parameter 7 = 1 - a vanishes as the size of the network increases, so that the size of the winning ticket N3 is ym o(m).
The above question has so far remained unanswered as a consequence of the limitation inherited from the core technical tool that has been leveraged so far to prove SLTH results, namely the Random Subset Sum (RSS) Problem [17]. Informally, the RSS asks how large a random i.i.d. sample Q should be so that we are able to approximate any number in [_ as the sum of a suitable subset of St. The applicability of RSS to the SLTH was first recognized by [24] within the proof strategy previously developed in [20].
1.1 Our Contribution
We answer the aforementioned question by introducing and proving a refined variant of the RSS Problem, namely the Random Fixed-Size Subset Sum Problem (RFSS), in which the approximation of the target values should be achieved by only considering subsets of fixed size k from set of samples (Theorem 2). We focus on subsets of fixed size k rather than subsets of size up to k for two main reasons. From theoretical point of view, it a stronger requirement, and practically speaking, using fixed-size subsets enables us to achieve SLTH results where the layers of the lottery ticket exhibit a uniform structure, potentially offering a computational advantage their implementation.
In Section 4, we show how the density y impacts the overparameterization, i.e., the ratio (m/me) between the number of parameters of the original network No and that of the class of target networks N₁ that can be e-approximated by pruning Na down to a subnetwork Ns with ym parameters. In our analysis, we also compare and recover as special cases previous SLTH results such as [24, 20, 8, 3, 9]. For instance, when ym = (m)) we recover up to a logarithmic factor the result of [24], which states that the overparameterization needed is Ologz (m2/e))) )) In the case of Dense Neural Networks, Theorem thus bridges the gap between the two extreme cases of ymm = ((m) and 7m (m)) considered in [20] and [24], respectively. It is worth noting that [24] is often considered an improvement over [20], as it exponentially reduces the overparameterizztton,, albeit at
the cost of trivial sparsity level. Finally, we prove that our bounds the overparameterriaaton as a function of the subnetwork sparsity are essentially tight.
Organization of the paper. After reviewing the literature on the SLTH in Section 2, we introduce the Random Fixed-Size Subset Sum Problem in Section 3. In Section 4, we explore some appli- cations of the RFSS Problem to the SI.HH and finally draw our conclusions in Section 5. Some limitations of our work, along with its potential impact, are discussed in Section 6.

---

2 Related Work
The SLTH is named after the L.TH, which was introduced by Frankle and Carbin in [12]. At the time of writing, this paper has received over 3,300 citations, attesting to the significance and impact of the research topic. Surveying the LTH is thus besides the scope of this work, and we defer the reader to dedicated surveys such as [16].
The SLTH was empirically motivated by work investigating training-by-pruninn algorithms such as [29, 26], namely algorithms that leverage the gradient of the network parameters learn a good mask of the edges to be retained (i.e., good subnetwork, called the winning ticket). [29] achieves this by learning probability associated each edge, which then used to sample the edges that should be included in the subnetwork. [26] gets rid of the stochasticity involved in the aforemen- tioned strategies by learning score associated to each edge; the subnetwork then determined by including the edges with the highest score. Such strategies are leveraged in [15, 14] in federated learning setting, in order to improve the communication cost of distributed training by communi- cating the sampled masks of fixed shared network, rather than the entire weights. However, these trainig-by--runingg
algorithms are generally not computationally less expensive than classical train- ing, since they also make use of backpropagation to update scores and are applied to sufficiently large network to find a winning ticket. To reduce the computational cost of finding a good sub- network, [13] shows, both theoretically and experimentally, that randomly pre- pre-prnnng the source network before looking for a winning ticket can be an effective approach. In [23]. on top of ran- domly pruning the source network, some parameters to be part of the winning ticket and they do not have an associated score, which effectively reduces the search space for the training-by sertiinggb--ruuue pry-punnin algorithms.
also frozen. Frozen parameters are forced
The first rigorous proof the SLTH in the case of dense neural networks has been provided by [20], which establishes a framework that was inherited by the subsequent works. [24] crucially shows that the framework in [20] allows the application of the RSS analysis in [17], proving that, with no constraint on the size of the subnetworks, random network with p-raameeters can be pruned to approximate target networks with m/ log(1/z) parameters (we defer the reader to Theorem for details on further constraints on the parameters). An alternative proof of the result in [24] was simultaneously shown in [22]. [8] and [3] successively extended [24] and [22] to convolutional neural networks (CNNs). By leveraging multidimensional generalizations of RSS [7, 21. [6] further extended the SLTH to structured pruning of CNNs and, as a special case, dense networks. Finally, [9] provided a general framework that proves the SLTH for equivariant networks.
As for refinements and generalizations of the above results, [4] shows that, at the cost of a quadratic overhead in the overparameterization w.r.t. [24], the number of layers of the random network No can be reduced to + 1, where is the number of layers of the target networks Ng: furthermore, while previous results only considered networks with ReLU activation, [4] shows how to extend the proof in [24] to a more general class of activations functions. [5] introduces the notion of universal lottery ticket, and show that it is possible to prune a sufficiently overparameterized random network so that the resulting subnetwork (the lottery ticket) can approximate certain class of functions up to affine transformation of the output of the subnetwork (in this sense being universal). [11] shows how to extend the proof in [24] when neurons have random biases, and adapts the training- by-pruning algorithm of [26) to find a strong lottery ticket with desired sparsity level. Motivated by theoretical insights on the existence of sparse strong lottery tickets, [10] develops a framework to plant the latter in large random network and investigates maining-by-pruning algorithms, providing evidence that sparse strong lottery tickets typically cxists for common machine learning tasks, and the difficulty to find them is of algorithmic nature.
Our proof of the RFSS Problem in Section 3 is based on the second moment method approach first explored by [18), and which has recently been refined to prove multidimensional generalizations of RSS by [7] and [2].
3 Fixed-Size Random Subset Sum
In this section we present our technical contributions on the RFSS, which are the foundation of our proofs regarding the sparsity of the SLTH.
3

---

Let us start by introducing some notation. We denote by [n] the set fl..... n for n E N. Given Lies X, and we omit when
set 92 (X,,..,,X,, and set of indices S S [ni] we define IS - clear from the context. We now define a class of distributions for which our RFSS result holds.
Definition (sum-bounded), We say that probability density function f is sum-bounded if there exist positive constants ej and Cre such that, for all l E M. given & independent samples X1,.., X with density f, the density of their sum Jm satisfies
C VE
Ca
S f (2) S
V
with the lower bound holding for all x E [-VR, Vil and the upper bound holding for all x E
At first, our definition of sum-bounded could look weaker version of classical local limit theorem on the sum of random variables (e.g., see [25, Chapter VII, Theorem 7J). However, that is not the case, since require lower bound on the sum for any k, which is needed prove main result.
Denote, for all x E [0, 1], the binary entropy
H2(x) x logz x (1 x)) log2 2)).
Our main technical result is the following proof of fixed-size subset variant of the RSS Problem.
Theorem 2. Let < < 1, Chyp 2 k n be integers with 1 < k S 2, and let O (X1,... Xn) where the Xs's are Lidd random variables with sum-bounded density. There exists a constant Cahoe such that, if
log2
n 2
Chyp H2 n
then for every fixed z
[-Vk, vkl it holds that
Pr Pr C [m], |S| k: 2| <)) Calm-
Remark. The proof of Theorem 2 is given in Section 3.1, and it actually holds for any 1 S k S An, for an arbitrary X [1/n,), We state the theorem this way for readability and because are primarily interested in high-sparsity settings (i.e., small size ht of the subsets), so considering values of l: 2 does not add much our analysis. The same remark also holds for Corollary
The sum-bounded condition of Definition is easily verified for distributions such as the Gaussian distribution. Previous SLTH results rely classical resampling argument by [17, Corollary 3.3], which shows how RSS results for Uniform 1,, independent random variables naturally extend to independent random variables that contains uniform distribution, in the sense that they can be expressed as the mixture of distributions one of which is Uniform[-1, [_1, 1] with constant probability.' The next lemma thus proves that the Uniform[-1, 1J distribution is sum-bounded". A detailed proof provided in Appendix C.
Lemma 1. The Uniform[-1,1] probability density function is sum-bounded, i.e., given a set Un (Uihee()) of i.idd variables U, with Uniform[-1,1] probability density function, there ist constants e and cu such that the probability density function f(x n) of the sum yLh, of these variables, for all n E N,
C1
S [(x,n) <
Cu
(2)
fn
Vn
with the lower bound holding for all x E sl-vn, vnl,, and the upper bound holding for all x E R.
Finally, in our proofs the Sparse SLTH in Section 4, make use of the following corollary of Theorem which ensures uniform high probability of hitting any target E [-VR, VTj. considering independent random variables that contain uniform distribution.
'The definition in [17, Corollary 3.3] is actually more general, since it concerns a different problem. We believe that Lemma is known, but we could not find reference.

---

and & (0. be constants, k. with 1 < k < 2' and let Q {X Xn) be i.i.d. random variables whose density is a mixture of a Uniform([-1. 1 with probability p. and some other density otherwise. There exists positive constant Camp that only depends on p such that, if
Corollary 1. Let 0
logz B
2 Camp H2 (m)
then
Pr V2 E - -Vk, vk 3S C [5], = k [.s. - 2| <
21- 1-E.
Proof Idea. The corollary follows from three arguments. First, by a standard sampling argument, we can assume that a constant fraction of the sample follows Uniform[-1, distribution. Sec- ondly, by Lemma 1, the uniform probability density function is sum-bounded. We can thus apply Theorem 2, which guarantees success probability of Gimm for approximating given target. Fi- nally, by a standard probability amplification argument and union bound applied to Theorem 2, by paying an extra factor logz (k/e) in Eq. 1, the constant Chm can be assumed to be E, and the existence of a suitable subset S. holds simultaneously for all 2 E [-Vk, vk]. Details are given in Appendix D.
For big enough, can get rid of the squared logarithmic dependency on & in the right hand side of Equation 3, as shown in the following Corollary, whose proof can be found in Appendix E.
Corollary 2. Ler O < S and & E 1/2) be constants, k, n. be integers with < k k 2 and k 2 Camp (log2
2log2k log2?). ) Ler Ω (x...... Xn) be i.id random variables whose density is mixture of a Uniform(l-1, 11) with probability and some other density otherwise. There exists a positive constant Camp that only depends on p such that, if
2 loga
YI 2 2Gamp
H2
(7
then
Pr V2 E - -k,, VK 3S. C [s], =k [Ss. 2| <
2 1-
As customary in conference versions of papers, our proofs adopt the convention of taking ceilings and floors as suitable for non integer fractional terms. This is done in the interest of the reader (and ours), and does not impact the results in any significant way.
3.1 Proof of Theorem 2
Proof of Theorem 2. For simplicity, throughout the proof we will often use c to denote any positive constant. Let S = {S c [n]] [S| = k} and define, for a fixed z [-Vk;, vk).
y = Y(=)=)= Σ Zs
SES,
where Zs (2) 1 ((E Following [18], exploit the second moment method for RFSS, generalising it to arbitrary k.
E Y
Pr(Y 0)
(5)
Y2]
thus suffices to prove that
Y < <E
(6)
We first rewrite Eq. 5 in more convenient form. Let Š and Š' be two independently and uniformly at random chosen subsets of [ni] of size k. and denote (z(z) as the event that Eş e-approximates 2, namely
Hs Hs(z) {|'s - 2 < <e).
5

---

We have
n1)
B| Σ
B|Zs]
Σ
Pr(Hs)
Pr (Hş)
SES
BES
and
E| = E
Σ
Es
Σ
Zs
= Σ
E [sZ
SEEs
S'ESS
S
2
= Σ
Pr(Hs A Hs))
11
Pr (H3 A Hg.)
(8)
k.
S,9'E&,
Using Eqs. 7 and 8 rewrite the r.h.s. of Eq. 5 as follows
(E ( Y
(H(
(H
Pr A Hg.) Pr (H Hg)
Eq. 6 thus becomes
Pr ( Hg) c)Pr(H)).
(9)
Let I denote the event (Iš i] and La.5 the event Un Tt Fix (2, By the law of total probability and independence of J; and Hg. we rewrite the l.h.s. of Eq. 9 as follows:
Pr (H Hg)
Pr (Hg, I Hg) + Pr (Hg. A Hg) Pr (H Jo Hg)
= =Pr(T:) Pr TH (Hg Jk)
(10)
Pr (4 Prr (Hg. Hgg Inh ak
(11)
(Pr(())Prrrt Pr ( Hg. T.))
(12)
To conclude the proof, it suffices to show that each addendum in Eqs. 10, 11 and 12 are upper- bounded by some constant multiple e/ VE, since the lower bound in Definition 1 ensures that
s S ccrr(Hg)
(13)
Vk
As for the first addendum (Eq. 10), since Pr (Hz. Hg. Ix) = 1, then
1
8k(n k) 2 (
Pr (Tx) Pr (H Hg. Ix) Pr =
8k(n k) 2 Cap loga
(0)
S 2/2
(14)
n
Vk
where inequality (a) in Eq. 14 is a standard lower bound on (*) holding for all S n 1; in inequality (6) in Eq. 14 we used Eq. 1, namely nHz (
Chyp log,
k. E. in inequality (c) in Eq. 14
we used that Cryp 2
As for the second addendum (Eq. 11), we next show that
Pr (I Pr (H Hg, Lunkk S - Vi.
(15)
by proving that
Pr $ c
(16)
Vk
and
Pr (Hz. Lykkk cs.
(17)

---

First, observe that I | follows a Hypergeometric(n, k. distribution, thus by Chebyshev's s inequality
(1- 1-
k2
122
Var [7]
Pr(IAAA-1) Pr 2 pk) Pr
pk
n
n
k2
(1-
pr
k- nー k n
n-k
Σ
c'
c
k2
vi'
having set c 2 > O, thus proving Eq. 16. The proof of Eq. 17 is given in Appendix F, concluding the proof of Eq. 15.
As for the third addendum (Eq. 12), in Appendix we show that ak
Pr (I)))) Pr Hg, S c E Σ
(18)
vi
The three bounds the addenda in Eqs. 10, 11, and 12 (Eqs. 14, 15, and 18, respectively), combined with Eq. 13, conclude the proof.
Sparse Strong Lottery Ticket Hypothesis (SSLTH)
We now apply results on the RFSS problem to the SLTH and obtain guarantees on the sparsity of winning tickets for Dense Neural Networks (DNNs, Theorem 3) and Equivariant NNs (Theorem 4).
The next theorem essentially interpolates between the two extremes of [20][Theorem 2.1] (where ym ((m))) and [heorm 1] (where ym = O(m)), where we recall that m and me represent the number of parameters of the overparameterized and the target networks, respectively, and is the density of the winning ticket.
We use a--) to denote the ReLU activation function, i.c., (xx) = x 1220. and ||W] to denote the spectral norm of the matrix W. Let F to be set of target ReLU neural networks f do + R of depth such that
F= f(x) Wio (Wxx))) Vi W. pddid;:- and || 1
(19)
For given f E F, for all i E [q], let p; max(": s/d., 4/d;-1), and max; Pr. Then, recalling that Camp the constant defined in Corollary
have the following result.
Theorem (SSLTH for DNNs). Let g be randomly initialized feed forward 2l-layer neural net- work, in which each weight drawn from a Uniform 1, distribution, of the following form:
g(x) M2jaMMa 21 ... (M,))).
Ler e (0, 1). M2 Rd2x2d 1n; and M 2ddd, inf xd: with nł satisfying
log2 2 2édi-1dir'nn
n Camp
(20)
H2(r')
With probability least 1- E, for every f E F, where F is defined as in Eq. 19, g can be pruned to obtain subnetwork of sparsity at least a = 1--7 - that approximates f up to an error having defined 7 = pY/
Proof Idea. The theorem follows from slight variation of the same approach detailed in [24]. in which we use our Corollary 1 instead of [17][Corollary 2.5] when pruning 9. allowing us to have control over the size of the pruned network. A detailed proof is provided in Appendix G.
Li
To illustrate a simple example of how Theorem addresses the main question asked in the intro- duction, consider the case where we want to approximate target network with m, parameters and layers, each of width d (so p and 7 7), by pruning an overparameterized network to achieve desired sparsity level of a 1-7, The condition expressed by Equation 20 in Theorem
7

---

Overpar Overparameterto aeparammterizaaann eetetteiizaiio
o/llgg?" ollogg m
e 1og Pk.
IN Density y of winning ticket
ex1)
mz
Figure 1: A qualitative plot showing the relationship between the density of a winning ticket and the overparameterrizatoo required by Theorem 3 for a target network with m, parameters. Earlier results from Pensia et al. [24] and Malach et al. [20] are shown for comparison.
comes from the use of Corollary 1 when pruning network g. as shown in the proof. If, instead of Corollary 1, we use its simplified variant Corollary 2, it is easy to observe that Equation 20 would become
log2
(2dd;
n2- = Camp
(21)
H2(7')
Using this condition, Theorem 3 then tells that we need to prune randomly initialized network
with twice as many layers and number of parameters of the order of d2 log d22
H())
We will now clarify the connection between Theorem and the earlier results from [20] and [24]. Figure provides quick visual comparison.
Malach al.[20]. When all layers have the same width d, [20] showed that any target network with | layers and a total of m, = d'l parameters can be e-approximated by pruning a randomly initialized network with 27 layers. The overparameterization of this network, relative to the target
network, is O log2 = (m²
More specifically, the winning ticket found after pruning
has a parameter count of the same order as the target network, resulting in density of = Notably, this density y is the inverse of the overparameterization, as the size of the winning ticket matches that of the target network.
Next, we show that Theorem also yields a density that is polynomial in __ when using an over- m.
parametrization of θ
Let z = me and note that in Theorem 3, since all layers have the same width. ny Theorem represents the overparametrization with respect to the target network, let us set n cz2, for some constant c. Equation 20 then becomes
(c237)
c22
Camp
(22)
H())
(es"") We show that the incquality cz2 2 Camp y llgg (175) holds for some big enough constant e when setting
y Wh L which implies that Equation 22 is also satisfied. We get 2 Camp logzlz) which is
log (c=*)
satisfied for big enough constant (see Appendix I). Overall, when using an overparametrization
θ m we find winning ticket with density __ shown in Figure 1.
m.
Pensia et al./24]. For simplicity, let us still consider target networks where layers have the same width d, and we apply Theorem using the simplified condition from Equation 21. When

---

ym = (m). i.e. the density y is constant as in [24] (see Appendix A), the entropy term H2(7') in the right-side of Equation 21 also becomes a constant. In this setting, we indeed recover the result shown in [24][Theorem IJ. up to a logarithmic factor, as shown in Figure 1.
Quite similarly to Theorem 3, the next result essentially generalizes [9] up to a factor log2 ! The theorem is stated with the understanding that for G-equivariant networks, in order to preserve G- equivariance, pruning is best done not with respect the parameters expressing the network in the canonical basis (i.e. directly on the weights of the network), but with respect to the equivariant parameters, that those coefficients expressing the linear layers of the network as linear combi- nation of the elements of the corresponding equivariant basis [9]. For simplicity, due to the technical set-up, we assune all feature spaces being FF (R ot,, with a the linear representation of the group G, and the same number n of such feature spaces being stacked in each layer. A G-equivariant lin- a corresponding equivariant
ear map from the ith feature space to the + stt can be decomposed basis denoted Bi-ii- B. Since all feature spaces are the same, we omit the layers' indices. When stacking n feature spaces the input and output of the ith layer, the full equivariant basis is denoted kn-nn and finally the basis of the G-equivariant maps from 1" to F" can be written as the Kronecker product kn-in @ B. For any basis B = {bi..... } we denote its cardinality p = |B] and define Ep norm.
|B]|| ||81 - Bybull, with in the r.h.s. being the operator norm inherited from the
Theorem 4 (SSLTH for Equivariant Networks). Let h be random 28-layer G-equivariant network where all equivariant parameters are drawn from a Uniform[- 1] distribution, every odd layer expressed in the associated equivariant basis kü-nn @ B and every even layer expressed in the associated equivariant basis kn-nn @ B. Letr = ((E) E (0,1), with ñ satisfying
logg
28n max [1B.11BB
u Camp
H2 (T)
With probability at least 1 - c. for every E-layer G-equivariant neural network f. with all layers expressed in the associated equivariant basis kn-on @ B, h can be pruned to obtain a G-equivariant subnetwork of sparsity at least = - that approximates f up to an error E.
The proof, which we omit, is analogous to that of Theorem 3, since [9][Theorem 1] exploits the exact same pruning strategy of [24], except for the fact that it is applied not to the original parameters of the equivariant network, but to the network expressed in terms of its equivariant basis (the sparsity a is here also intended with respect to the equivariant parameters count). This allows the construction to apply without losing the property of equivariance in the pruned approximating subnetwork obtained. The crucial step is when Corollary is applied in [9][Lemma 1]. instead of [17][Corollary 2.5]. This is done in parallel, multiple times, across non-overlapping coefficients of the equivariant basis. Thanks to the careful preprocessing devised by the authors, this preserves equivariance and at the same time ensures that each application of Corollary is independent of the others.
To conclude the section, we mention that Theorem 4 applies in particular to vanilla CNNs, which are special case of equivariant neural networks where the group G (Z²,+), recovering previous SLTH results on CNN [8, 3]. Furthermore, we remark that Theorem 3 can be revisited through the improvement upon the 26-depth overparameterization devised in [4], i.e., it is possible
to provide sparsity guarantees also for overparameterizationn requiring depth é+1 only. The analysis
more technical and we omit it, but the ideas are analogous to what shown in [4]. An analogous improvement is suggested as future work in [9].
4.1 Lower bound on the required overparameterization
We now adapt the lower bound of [24] in order to almost match the required overparameterizzaton of our Theorem 3, considering the simple scenario in which we want to approximate the family F of all linear networks with weights forming a matrix having spectral norm less than vi; more formally
= (hw W Rdd |[W|| < Vk). where hw(x)= Wa.
(23)
The formal claim states that, if a network with n parameters can approximate every bw E with probability at least 1/2 (after it is pruned down to & parameters), then the hypothesis of Theorem in Eq. I must hold.
Equivalently, the hypothesis of Corollary must hold up to factor (loga t).

---

Theorem 5. Let n, E N, with S k An, having set À = 1 1/2mt ~ 0.84. Consider neural network g with n parameters, and let GR be the set of neural networks that can be formed by pruning g down to & parameters. Let F be defined in Eq. 23. it holds that, for some & < 1/16,
1
vhw F,P 3g' E Gk
max
[ww(2) - (x)) <
(24)
x:
2
then it holds that
d² log2 x
H₂ (H)
The theorem follows by adapting the packing argument of [24]. A detailed proof is provided in Appendix H.
5 Conclusions
In this work, we have extended previous results on the Strong Lottery Ticket Hypothesis by quan- tifying the required overparameterization as a function of the sparsity of the subnetworks. Central to our results is proof of the Random Fixed-size Subset Sum (RFSS) Problem, a refinement of the seminal Random Subset Sum (RSS) Problem in which the subsets have a required fixed size.
A challenging open problem to extend our analysis of RFSS to the multidimensional case, in which the random samples and targets are vectors in Rd. Previous extension of RSS the Mul- tidimensional RSS have indeed allowed to prove structured-pruning version of the SLTH [8]. A Multidimensional RFSS result would then allow quantify, in the structured pruning case, the dependency of the overparameterization w.r.t. the sparsity of the (structured) subnetworks.
Another future direction is to refine analysis of the RESS in Theorem 2 in order to improve the probability of success to - rather than constant, thus allowing to avoid shaving off the extra factor log2 (1/=) in our corollaries w.r.t. our lower bound, which is due to the amplification done in Corollary to get to probability 1 E.
Finally, an important future direction is to improve bhgniing-b--runiine methods such as [29, 26, 11, 10, 23] or to develop new ones, order allow efficiently find strong lottery tickets of desired sparsity, thus empirically validating our theoretical predictions.
6 Limitations and Impact
Limitations Similar to all the research conducted on the LTH and the SLTH, this work only proves the existence of lottery tickets. To this date, it is not clear if these subnetworks be found reliably (no formal proof exists) in an efficient manner however, empirical evidence suggests that efficient algorithms exist (e.g., [29, 26)).
Impact The contribution of this work is primarily theoretical and not confined to specific do- main. Its potential societal impact would, therefore, be closely tied to the particular scenarios to which it is applied. It could be interesting to compare the environmental impact of finding lottery tickets inside overparameterized networks. We also believe that our work has the potential to have strong environmental impact as sparse NNs have massively reduced inference costs.
10

---

Acknowledgments and Disclosure of Funding
This research is supported by the EPSRC grant EP/W005573/L, and by the France 2030 program, managed by the French National Research Agency under grant agreements No. 0003 and and ANR-22-PEFT-ONE lence dAIEDGE under Grant Agreement Nr. 101 120726. by SmartNet and LearnNet, and by the French government National Research Agency (ANR) through the UCA JEDI (ANR-15) 15-IDEX-0)), EUR DS4H (ANR-17-EURE-004) and the 31A Côte d' Azur Investments in the Future project with the reference number ANR-19-P31A-0002.
It was also funded in part by the European Network of Excel-
References
[1] Giampictro Allasia. "Approximation of the normal distribution functions by means of spline function". In: Statistica 41.2 (1981), Pp. 325-332.
[2] Sander Borst et al. "On the Integrality Gap of Binary Integer Programs with Gaussian Data". In: Mathematical Programming 197.2 (Feb. 2023), pp. 1221-1263. ISSN: 1436-4646. DOI:
10. 00.10077s10107-00222 0182822-011821111 (Visited on 06/05/2023).
[3] Rebekka Burkholz. "Convolutional and Residual Networks Provably Contain Lottery Tick- ets". In: Proceedings of the 39th International Conference on Machine Learming. Baltimore: PMLR, July 2022. pp. 2414-2433. (Visited on 02/27/2023).
[4] Rebekka Burkholz. "Most Activation Functions Can Win the Lottery Without Excessive Depth". In: Thirty-Sixth Conference on Neural Information Processing Systems. Dec. 2022. (Visited on 02/27/2023).
[5] Rebekka Burkholz et al. "On the Existence of Universal Lottery Tickets". In: International Conference on Learning Representations. virtual, Apr. 2022. (Visited 02/27/2023).
[6] Arthur da Cunha, Francesco D' Ammore,, and Emanuele Natale. "Polynomially Over- Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets". In: Thirty-Sevente Conference on Neural Information Processing Systems. Nov. 2023. (Visited on 04/23/2024).
[7] Arthur Carvalho Walraven da Cunha al. "Revisiting the Random Subset Sum Problem"" In: 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Am- sterdam, The Netherlands. Ed. by Inge Li Gørtz al. Vol. 274. LIPIcs. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2023, 37:1-37:11. DOT: 10. 12..4230.222...... 4230/LIPICS ESA 2023. 37.
URL: https: htt:://oo.ogggge.oo org/ /org//0,. 10. 4230/LIPICs, ESA 2023.
[8] Arthur da Cunha, Emanuele Natale, and Laurent Viennot. "Proving the Strong Lottery Ticket Hypothesis for Convolutional Neural Networks". In: ICI.R 2022 10th International Confer- ence on Learning Representations. Virtual, France, Apr. 2022. (Visited on 08/04/2022).
[9] Damien Ferbach et al. "A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis". In: The Eleventh International Conference on Learning Representations. Sept. 2022. (Visited on 03/04/2024).
[10] Jonas Fischer and Rebekka Burkholz. "Plant 'n' Seek: Can You Find the Winning Ticket?" In: International Conference on Learning Representations. Apr. 2022. (Visited on 02/27/2023).
[11] Jonas Fischer, Advait Gadhikar, and Rebekka Burkholz, Lottery Tickets with Nonzero Biases.
June 2022. arXiv: 2110. 11150 [cs]. (Visited 05/13/2024)
[12] Jonathan Frankle and Michael Carbin. "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks". In: International Conference on Learning Representations. Sept. 2018. (Visited on 10/20/2023).
[13] Advait Harshal Gadhikar, Sohom Mukherjee, and Rebekka Burkholz. "Why Random Prun- ing Is All We Need to Start Sparse". In: International Conference Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA. Ed. by Andreas Krause et al. Vol. 202. Proceedings of Machine Learning Research. PMLR, 2023, pp. 10542-10570. URL: https: / //proceedinga mlr. www.m.lp.....eeeemmmmmmmmm ppwps/v20//eaee/ wargggaahiaaaaa... pttp:s///02//aaahaaaa2222222
[14] Berivan Isik et al. " "Adaptive Compression in Federated Learning via Side Information".. In: Proceedings The 27th International Conference Artificial Intelligence and Statistics.
PMLR, Apr. 2024, pp. 487-495. (Visited on 05/16/2024).

---

[15] Berivan Isik et al. "Sparse Random Networks for Communication Effiicient Federated Learn- ing". In: The Eleventh International Conference on Learning Representaaionss. Sept. 2022. (Visited on 01/1 01/18/2024).
[16] Bohan Liu et al. A Survey of Lottery Ticket Hypothesis. Mar. 2024. DOI: 10. 48550/arXiv.
2403. 04861. arXiv: 2403. 04861 [cs]. (Visited on 05/16/2024).
[17] George S. Lucker. "Exponantially small bounds on the expected optimum of the partition and subset sum problem". In: Ramdom Structures and Algorithms 12 (1998), pp. 51-62.
[18] George S. Lueker. "On the average difference between the solutions to linear and integer knapsack problems". In: Applied Probability Computer Science, The Interface. Vol. 1. Birkhäuser, 1982.
[19] Florence Jessie MacWilliams and Neil James Alexander Sloane. The Theory of Error- Correcting Codes. Vol. 16. North-Holland Mathematical Library. North-Holland Publishing Company, 1977.
[20] Eran Malach et al. "Proving the Lottery Ticket Hypothesis: Pruning Is All You Need".. In: Pro- ceedings of the 37th International Conference on Machine Learning. ICML. '20. JMLR.org, July 2020, pp. 6682-6691. (Visited on 03/26/2023).
[21] James E Marengo, David L Farnsworth, Lucas Stefanic, et al. "A geometric derivation of the Irwin-Hall distribution". In: International Journal of Mathematics and Mathematical Sci- ences 2017 (2017).
[22] Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Need". In: Proceedings of the 34th International Conference on Neural Information Process- ing Systems. NIPS'20. Red Hook, NY, USA: Curran Associates Inc., Dec. 2020, pp. 2925- 2934. ISBN: 978-977888 978-1-71382-954-6 (Visited on 03/26/2023).
"Logarithmic Pruning Is All You
[23] Hikari Otsuka al. Partial Search in Frozen Network Is Enough to Find a Strong Lottery Ticket. Feb. 2024. DOI: 10. 2....4850//88 arXiv. 2402 14029.
arXiv: 2402. 14029 [cs, stat].
(Visited on 05/
[24] Ankit Pensia et al. "Optimal lottery tickets via SUBSETSUM: logarithmic over- parameterization is sufficient". In: Proceedings of the 34th International Conference on Neu- ral Information Processing Systems. NIPS '20., Vancouver, BC, Canada, Curran Associates Inc., 2020. ISBN: 9781713829548
[25] Valentin V. Petrov. Sums of Independent Random Variables. Ergebnisse der Mathematik und ihrer Grenzgebiete. 2. Folge. Springer Berlin, Heidelberg, 1975, 348 pages. DOL: https: 1007 ////9/97733622- 9-0------2-66---9
/
[26] Vivek Ramanujan et al. "What's Hidden in a Randomly Weighted Neural Network?" In: 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). June 2020, pp. 11890-11899, DOI: 10. 1109/CVPR42600 2020. 01191.
[27] N. Shakhaidarova. "Uniform local and global theorems for densities". In: Izv. Akad. Nauk UzSSR Ser. Fiz-Mat. Nauk 5 (1966), pp. 90-91.
(28) Irina Shevtsova. On the absolute constants in the Berry Esseen type inequalities for identically distributed summands. 2011. arXiv: 1111.6554 [math.
[29] Hattie Zhou et al. "Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask". In: Advances Neural Information Processing Systems 32: Annual Conference on Neural Infor- mation Processing Systems 2019 (NIPS 2019). 2019, pp. 3592-3602.
12

---

A Lower Bound on the Ticket Size in [24]
The claim a direct consequence of the proof of [24, Theorem 2] (Appendix B). There, in Step 3, it is shown that
1
2 2
where G is the set of subnetworks that can be formed. Let be the number of parameters of the original network. If we consider subnetworks of size at most ym (0 I y I 1), we have
727
|9|
27 loga!
mm
which combined with the previous inequality implies
1 -1
rym log2
d log2
2
we have an overparameterized network size m (dd logz (+) ). as [24], we need rm
(m) for the last inequality to be satisfied (note that log,
(
$ 1, as 0 S 2 = 1).
B Visualizations
reinit
Train
Figure 2: Simplified representation of the procedure for finding Lottery Tickets (LTH). A large random neural network (step 1) is trained by iterative pruning with rewind: when the loss reaches a local minimum (step 2), some weights with smallest absolute value pruned (step 3) and the value of the remaining edges is then reset to that of the initialization (step 4); finally, training is resumed and the final network is obtained (step 5). Remarkably, the sparser subnetwork is consistently able to reach a loss not larger than that right after pruning.
Simplified representation of the procedure for finding Strongly Lottery Tickets (SLTH) Training by pruning. Previous work has shown that it is possible to sparsify large ran- dom neural network in order obtain subnetworks that achieve good performance for task under consideration, motivating the Strong Lottery Ticket Hypothesis. No training is required.
Figure 3:
C Proof of Uniform[-1, 1] being Sum-Bounded
In this section provide a detailed proof of Lemma which states that the uniform distribution in [-1,1] is uum-bounded. as stated in Definition 1. We remark that, while the proof is written for uniform random variables, it should be possible to extend it to family of densities which are unimodal, with bounded variance, and bounded third moment.
follows from the upper bound Σ
<
the partial of binomial coefficients.
13

---

Proof of Lemma 1. Note first that the distribution of the sum of n i..d. variables in [0, 1] is known as the Irwin Hall distribution I,, We will use that Var[4,] = 12. where Var[X] denotes the variance of the random variable X.
For 2 2, [xx; n)
can be defined as the convolution of f(x) f(r, 1) and f(x, 1), i.e.,
f(x /
- 7. ((0-T,n-1)ftl
It is straightforward show, by induction and elementary substitution in the integral above, which is relied upon in the inductive step, that f(2,, n.) is symmetric about 0, that is f(z, n) = f( (2-2, n).
Let us now prove by induction that (z, n²) is nondecreasing on the interval [-n, 0] and nonincreas- ing over [0, ni (for simplicity, since it vanishes outside [-n,, n].. we can consider directly the negative half and positive half of the real line, respectively, in the argument that follows).
The claims hold trivially for fz);; also note that
if - S 1
1 f(x 2 [_] f(x r, 1)dr.
((T)= - a
=
otherwise
If x' S -1. Since x - < 0, by inductive hypothesis we have that f(x T,
f(x' T, n ---1 1) over the whole interval 7 E [-1, Taking integrals yields f(z, n)) < n1),
Now, consider the case when S <-1 S x' S 0. If x + 1 S -I' 1,
S I + <
-I' -1 -I' + T < -I + T. By the symmetry about the origin, the inductive hypothesis is over the whole
f(x T,n f r. 1) < f(-r'(''- + T,n 1)) f(zz -. -.n--1 -1) 11)
interval 5 E [-1, since -1 115-1 -r + 1 Taking integrals yields f(x, n) S f(r',, n). Otherwise, there exists To such that x
To --/-1,,
-x' 1 for all 7 E (-1, and
x r < - - for all 7 E (7o. 1]. By symmetry, using -x = x' + - To. f(x 7, - 1) 2(-
f(x +1 7 To, 1). Thus, for all r E [-1, vo]. via the change of variable (1 T - TO) in the middle integral below, we obtain that
f(x T, - 1)dr = [ f(x' +1 To. 1)dr = [r f(x' - o, 1)da. (25)
-x - + r, by symmetry about the origin we have that f( - T, 1) < f(z' - T, 1) by the inductive hypothesis with the same reasoning
For all r E (To, 1), - 7 < -x' 1 -2 +
of the case x + 5 -x' - 1. Taking integrals over the range [To, 1] for each term the inductive
hypothesis yields
[ f(= - - S [ f(x' - T, n- 1)dr
(26)
Eqs. 25 and 26 imply that f(x n) f('
Trivially, if -1 S x < S O, analogous ideas are put in place as for the previous case, therefore we omit the details. We have thus shown the nondecreasing monotonicity of fzz n2) on the negative half of the real line. By the symmetry of fx, n) about the origin, on the positive half of the real line the nondecreasing monotonicity turns into nonincreasing monotonicity, and the proof is complete.
Lower bound (first inequality in Eq. 2). The variance of 21/1 is n/3 since 2 = 2( (n) n/2)
and (ar[ = n/12. We define Z function. Z, has expectation and standard deviation 1. Consider the probability
and we note with Fn its cumulative distribution
Pn(n) Pr(Vi < 2h < 2 Pr(v3 < 2 < 2V3).
'It should be known that I, is unimodal with mode in n/2,, but we were not able to find reference. It instructive note, assuming that I, unimodal with mode in nz/2, it directly follows that its probability density function increasing on the interval [0, 22] and then decreasing over [n/2, n]. This implies that f (α, (the density of seffe ). is decreasing in the interval [-n,0] has maximum and increasing [0, n] for all n 2 2.
14

---

Now, we use the following form of Berry- Berry-Esseen inequality, discussed in [21][p.2]).
Theorem (Allasia [1]). For all n 2 L,
- V3
20
where (=)) is the cumulative distribution function of the standard normal distribution.
Theorem implies
v3
PL(n) 2(233) - 2((3) - 2.
20
When 2 18.
v3
2 22133 - 2((3) - v3
((233) - 2((3) - 2.
Cis > 0.
20
20v 18
That is Pn(n)) 2 C18 O. When I n 18, (z(n) (2 (v Cn >
We thus
have
Pa(n) 2 min for < S 18) oj 0. Ith |n) s 2 As the density f(x, n) is decreasing on RR+ we have
Recall that P2(nn)Pr(yns$
PL(n) - ((vnn))
Thus,
Pn(n) vn
f(v7,n) 2
Since (m(m)= 2 e then for all n 2
f(Vn,n) 2 & Vn
When = 1. the density f(1,1) 112 So, by setting a min(c,, f), we that, for all n 2 1, for all 0 < vn:
nx, 2 f(Vn,n) 2
4
vn
By a symmetric argument, we also have for all n 2 1, for all vn S x 50:
f(x,n) 2 f( Vn m)
Vn
Upper bound (second inequality in Eq. 2). Here, we bound the probability distribution func- tion f(x, n) of 1// Vn/aZn, where recall that Z Denoting fz the probability distribution function of ZH, we have
(x n) = ((1
12 z,
We use the following local limit theorem, discussed in [25][p:214].
Theorem (Sahaidarova (27]). Let {X,}} be a sequence of independent random variables with a common density p(z), such that E||X|] < oc, [| 0. E[X and sup p(x) < C. Let
Pa(x) be the density of the random variable
Vn 2; X,. Then
1
A,3
sup - x(x)1 < max(1,
Vn
where à is the probability distribution function of a standard gaussian, A is absolute constant, and Bg 131
'It also possible to obtain our result via classical bound of 0.4748 on the absolute constant, provided in [28]. This would require replacing with 900 the cut-off value for which 18 in the current version of the argument.
Esseen inequality, due to the improved upper
15

---

The theorem can be applied to uniform continuous distribution with density p"(x) interval [-v3, v3), which has mean O and variance 1. We thus get, for every E R,
in the
2/3
AB3 vn
1
A3
+ A 3v3
= = - 60) +
cu.
2T
Vn
2m
4
In conclusion, setting Ca = v for every x E holds that
[(x,n) = V (V
v3d
Cu
vn
v
D Proof of Corollary 1
Proof of Corollary 1. As anticipated, we proceed in three steps.
Step I: Hoeffding bound. We start by showing, following the idea at the base of [17, Corollary
3.3], that if n' is large enough, standard Hoeffding bound ensures that with high probability constant fraction of the sample follows a Uniform[ 1-1, 1] distribution. Since we assumed that every X, is a mixture of Uniform[-1. 1] distribution with probability p. and another distribution with density (given by the factors G,). we can rewrite X; = B₁ U, + (1 - B,) G,, with Ug being the uniform random variable, G; being the random variable with density g. B, being independent Bernoulli random variables with probability p.
Fix (p) p. and assume, for now, that n' satisfies Eq. 1, and therefore, since 1/2, choosing Chyp = Chyp (p) 2 (a 2 ensures that, defining s' $/2,
1
1 p)2 In E
n' z Chyp log2
2(a
and therefore
n
Pr
Σ
Bi < an
se 2(a--)))
Se in =
Thus
n' an'
Pr
Σb: Bi
)nd)
21 _
that is, with high probability, there is a set of indices T [n'] of size |7] an', such that for each i I it holds B, = 1, i.c. X; is uniformly distributed.
Step 2: Application of Theorem 2 via rejection-sampling. Lemma 1 ensures that the uniform distribution of the |/] random variables selected in Step 1 is sum-bounded. Conditionally on the event 1 B, an'), we can discard all random variables indexed outside I and apply directly Theorem 2 to an' of the remaining ones, for any fixed and 2 [-Vi, vAl, since (CCypp 2 by construction. This guarantees success probability of cim for approximating the given target 2; thus,
Pr P355 c [n], = k: Es, <2)<
n' Σ
n'
Pr
SSe c [m]. |S.| h: Es, - 2| < r
B, > an'
Pr Σ B, > an'
Pr
SS C S. = k EEs. - <|<<5 | > ani
(1-E') 2 Gla (1 - E²) 2
4 thm Ctm
3
16

---

Step 3: Amplification. Finally, by standard probability amplification argument and a union bound applied Theorem by paying an extra factor loga (k/=) in Eq. 1, the constant Ghm can be amplified to 1 and the existence of a suitable subset S² holds simultaneously for all z E [-VE, Vk
We now give more details on this amplification.
In 5" Recall that e' = 5. and let Camp = -Camp (p) = 8 Oaz and r-
By assumption,
log2 2 l
log2
A loga E
Camp
H2
k
2yy H2 (+)
rOaye H2 (#)
where the last inequality is ensured by < 1/2. By Step 2, we can apply Theorem 2, with e' and long & n' 2 Cbyp Ha [
n", allowing us to prove that we can e' apaproxximtee any target with probability
at least Cinm- The probability of failing to approximate some given is then at most 1 1-Chm- From the sample 92 of sum-bounded random variables take r subsamples (without replacement) of cardinality n" each, -2,,.... Ωr, The probability of failing approximate some given with subsetsums from is less than that of failing to approximate with subsetsums from within every S2 ss and the latter
probability is at most (1 Chmm )"; thus, for every = E [-vk, ViJ.
Pr (AS= C [n], = k: [Es. - 21 < E') S (1 C(m))
By an union bound, we also have that
Pr Vz E [-Vk, K
3S, c
[n],|S,] = k: 1Es. 2| <
-2|<<) <))
2
2 Pr 42 E - -V + i5': :
- V
SSS C [Sa1 = k: [Es. 22 2| -2]=6,)
E
= 1 - Pr
32 E
- Vk + + :
2 Vh
AS C [r].1s.| = k: EEs, - 2/ <t)
21
Σ
Pr(SS, c [n] = k [Es. - =1 <E)
=Ef Vi+tiesieeB [3
2 E'
k
2 1 V - ((hmm (1-(mm) =1 =1
Veeep
In
IIn11
(thm)
Cihm
E
k. 2 Vkexp (-41u
2 8
-
=
2
4 2 E,
where the last inequality is ensured by < 1/2. This completes the proof.
E
Proof of Corollary 2
Proof of Corollary 2. By definition of binary entropy. have
k
k
A:
H₂
log2
loga
(27)
n
72
In particular, since both terms in the previous equation are positive, we get
k
k
H1
logz
(28)
T
7
n
We now use eq. (28) to derive an upper bound for the quantity will be used later:
Comp Hz(
log 2+oglgggk dogg
which
Camp
log l + 2log2k log2 g
Camp
log? k + +logzk log2 e
H2 k
loga
(#)
17

---

logg k + 2log2k log2
1
Camp
(29)
k
loga (7)
log h + 2logzk logz
S
Camp
(30)
k
(31)
where from eq. (29) eq. (30) we used that log2n/k 1 for k 5/2, and then the hypothesis
k 2 2Camp (log2 + 2log2k 2ogz directly gives eq. (31). Let us now rewrite eq. (3) in a more convenient form:
H2 (#)
2 h log2
Camp
E
kk) H2
(n
2 logg k + 2log2k log2 + log2 1
Camp
H2 (#) logž k + 2log2k logz
1
log2
Camp
Camp
log2 + 2logzk: log2 1
Camp
1
log2
(32)
H2 )
H2 ())
log2 1
Camp
(33)
H2 (%)
Gump
log3 k+ 2logs loga
Ha
Using eq. (31) we get
Camp
20mmp
(34)
Gamp
logg 2+oggg2 k loga
H2(N)
To satisfy eq. (33), we can then choose n such that
log2
n 2 2Camp
(35)
H2 (
and then apply Corollary to end the proof.
F
Details for the proof of Theorem 2
Proof of Eq. 17 Define A Š and observe that
Pr (Hg. Hg. Iuk
(36)
Pr (H Hg, I2) Pr (T, Hg, 1pk,k-1)
(37)
k-1
Pr Pr (2- 15-00 =, Pr Pr,, = Hg. I,) dy
Pr (1: (pk,k-1))11)
(38)
Pr (
< =
y H1g. 1,) dy
Pr (1: 1pkkk-)
(39)
< Σ
Pr y1 H 1.) dy Pr (1: Hgg L-k
(40)
18

---

SE
where from Eq. 36 to Eq. 37 and from Eq. 37 to Eq. 38 we used the law of total probability: from Eq. 38 to Eq. 39 we dropped the redundant event Hg in the conditioning, due to conditional independence; finally, from Eq. 39 to Eq. 40 we used Definition 1 which implies that for any i {uk, .... k - 1} it holds
Pr ( (z f)l = E = y. Pr (Epza)- (z-w) w) < E) S ce
Proof of Eq. 18 Let A = (5. Analogously to the calculations from Eq. 37 to Eq. 39, by the law of total probability we have
(T.).) Pr Pr(Hg (gg.
uk
(r(
Pr([EA - (2- (2- <E < y, Pr Pr (E, y Hg. Tc) dy
-00
pk-
Σ (L))
Pr Pr (z -- m)1 <
Pr < Pr
y gg. 1,) dy
(41)
i=
pk-1
[ Pr = y Hg. 11) dy
1 c
Σ
Pr Pr(li)
(42)
Vk
i=0
S c
Vi
where from Eq. 41 to Eq. 42 we used Definition 1, which implies that for any E {0.... 10 1}
it holds
Pr (1=j--1) (z 5) < <s) <
E
S
Vk
VK
G Proof of Theorem 3
In the proof we will refer to the following results, upon which [heorre I] relies (the statement below slightly differ as we fix two small typos in their notation and mixing coefficients). With the understanding that by mixture of a distribution D1 and D2 with probability p it is meant that the pdf (we adopt the convention that this term includes generalised functions, such Dirac deltas for point masses) of D can be written as a convex combination of the pdf of D₁ and that of D2. that is fo PfD, + (1 p) For the unfamiliar reader, we note that in the literature this is often stated in short as D = pD1 + D2.
Lemma 2 ([24][Corollary 1J). Let X ~Uniform (0, 1) (or X UUniform|- -1, 1,0) and ~Uniform 11 1] be independent random variables. Les P be the distribution of the XY and dn the Dirac delta at O. Let D be the distribution obtained mixture of dn and P with probability 1/2. Then is the mixture of a Uniform|- 2/2] and some distribution Q with probability In(2)/4.
Corollary 3 ([24][Corollary 21). Let X1.... Xn be lid with distribution D as defined in Lemma 2,
where n 2 C3l=(//) for some universal constant C. Then
Pr 1-1,11 AS [m] :/2 -
ExIse) 21-6.
Proof of Theorem 3. The key idea is exploiting Corollary at each step of the pruning strategy established in [24][Theorem 1], where Corollary used instead, Without loss of generality, we replace their min(s,5) with e. For the sake of easily following the approach adopted in [24], let us define n² nxx) as the function
log2 (kar)
n (w)
= Camp
(43)
H₂
(<(x))
For simplicity, we denote the density of 2n conditional on H n 1, as Pr (2) y H 4t).
19

---

where k = y'n((x) In the following, we use n² as short for n" (1/E), and we will only explicitely provide an argument for n² when is different than 1/E. For instance, in the last step of the proof, we will use n" (2ed:d41//e), which matches the definition of nę given in Eq. 20.
Consider [24][Lemma 1]. When approximating a single link (that is, weight), after the overpa- rameterization (which creates an additional layer of width 2n in between the input and the output node) via 4n links, instead of pruning via Corollary we prune via Corollary twice in the second layer, that is we ensure that only k = =''" edges yield the desired approximation, both in the edges corresponding to the positive part of the input weights and in those corresponding to the negative part. Thus we obtain at most 4k surviving edges, after the preprocessing step and the pruning mask applied. This yields sparsity of at least a' 1 - 7/ Note that it because of the preprocessing step that we go from distributions Uniform - 1] to distributions D, as defined in Lemma 2, which are shown to be a mixture with Uniform[-1. 1] and therefore can be also handled via Corollary 1.
Consider [24][Lemma 2). When approximating a real-valued multivariate linear function, after the overparameterization (which creates an additional layer of width 2dn" (4/+ in between the di input nodes and the output node) one simply iterates the ideas of the previous case d times. For each input node, the overparameteriiaatoo surviving the preprocessing step on the weights of the input layer is 4n (4/a). Pruning the second layer of the overparameterized link for each input via Corollary with &- = 2'n" (4/e) (again, performing this both on the edges corresponding to the positive part of the input weights and in those corresponding to the negative part), instead of exploiting Corollary 3, yields that at most 4dk edges survive after the pruning mask is applied. This yields a sparsity of at least a' 1-
Finally, consider [24][Lemma 3]. When approximating layer with input dimension dN and output dimension d2, after the overparameterization (which creates an additional layer of width 2din" (dind((d)d/s)) in between the input nodes and the output nodes) one iterates the ideas of the pre- vious case di times in the input layer through the same preprocessing step, and d2 times in the output layer, one for each of the d2 blocks created by the preprocessing (essentially the weights in the input layer are re-used d2 times). For each input node, the overparameterizztion surviving the preprocessing step at most (d2 + 1)m² (d,dafe). Overall, after the preprocessing step. we have at most 2d1 (d2 + 1)n" (dida/e) parameters. We then use Corollary 1 (with k = (did///))))) to prune the number of parameters between the introduced additional layer and the d2 outputs down to 3d,d2''n' n'" (dıda/e). As for the edges between the dj inputs and the additional layer, only those that reach a neuron in the additional layer, from which there at least one outgoing edge towards the d2 outputs, are used; since for each of the di blocks of 2n" (dida/s) neurons in the additional layer we only kept 2-'n" 2y'n"(d:da// (d.da/s) outgoing edges to each of the d2 output neurons, in the worst case (all the nodes involved in the subsetsums are disjoint) we keep 2d27'n' (did//ss) of them for each of the di neurons. Globally, we are left with a total of at most 2d2 / "n" (dida/s) edges both in the input layer and in the output layer, thus a total of idid2'/ne ( (didafe) edges survive the pruning. The density of the surviving edges is then less than
4d/d27'n (d:da//s) (d/da/s) 2dnn (ddnd(d:d//e) (didz/e) + 2d, 2d (ddnn((ddda
2d27
(dl da dz)r
di
S <PIY.
di + d2
d1 + d2
where A1 max [di/d,, ds/d;) } and in the last inequality we used that d/d//d, + d2 S pildi + d2) since Pi 2 1. This ensures sparsity a' 2 21-p17
[24][Theorem 1] consists of performing, for every i E [0] the previous step on layer with input dimension d4-1 and output dimension d;. The overparameteriizaton creates an additional layer of nodes of width 2d,-1n" (2fd:-1d//)) in between the d,-1 input nodes and the de output nodes. Since the construction is stacked times, this generates 26 layers for the overparameterized network, which will therefore have a starting number of parameters
m Σ
+ (
Corollary applied to each stacked overparameterizee layer instead of Corollary 3 in the previous step yields that the total number of parameters left after the pruning is
m 5
4d ddikss
1=1
20

---

where h; = 7'n" (26d:22d/// Recall that p = max; Ps, where P = max di.xfdd//i-1. di-1/d. 2 1.
Recall that 7 = pi/. We obtain that
di di-ikk + 2d;-iddih,
2d
di-1
i=1
- 1ppdi-i -iiiiiki-- +224 idepkk
2dh11k 2d1-iddkk
i=1
pp
Σ
2d nn (2(d--id/))) + 2d.-1d,n" (204--4- rym
1=1
We then get that the density of the edges surviving the pruning mi/m I y, which implies a sparsity of at least a = 1 7.
H Proof of Theorem
Proof of Theorem 5. Consider the space W/ = {W Rddxd ||W] S VkJ. and let Ps be
2e-separated set of Wa, i.e. subset Pk Wy such that for all distinet W. W E Px it holds IW W >
2e. We denote W = W1, P = Pı, and the set of all possible subnetworks of g as g
(note that this does not denote G, the set of all subnetworks of size 1).
Step 1: Packing argument. In [2e][The 2, Step 1], it is shown that any function g' only approximate at most one member of ' for bounded input x (say, || I 1). In particular, this also applies to functions g' representing the elements of Gk.
Step 2: Relation between Gg&| and [Pkl- By Step 1, in [2e][The 2, Step 2] it is shown that [P] I 2| under the assumption of Eq. 24, with G& replaced by 9). Therefore, also by Step I, replacing P with Ps and G with G% in [24][Theorem 2, Step 21, it holds that [Pal 2/ Note that |G& (#). the number of different ways in which we can select k parameters out of
actually get
PA
(44)
2
Step 3: Lower bound on [P&l- Let consider 2e-separated set Pmax of maximal cardi- nality. In [24][Theorem 2, Step 3] it shown that
d²
Vol(W) Vol([W W: || 2=})
pmaax|
2
Here Vol is the Lebesgue measure in ddd identified with dd .y the exact same argument, replac- ing W with Wt and thus pmax with Pmax it holds that
d²
Vol(W)) Vol([W E W4 ||]]| < 2x})
Vh:
P
2s
Combining this fact with Eq. 44 applied to prnax implies that
d²
(45)
2
2=
21

---

Step 4: Lower bound on n. Consider the standard bound found in [19]
m
71
2nHa(M)))
k
2xkk(n k:)
and combine it with with Eq. 45. It follows that
d²
2 2m))
1
2 - k)
vk
2
2
and taking the logarithm of both sides yields the sought lower bound on ni
k
22 k) ) dl loga
vk
nH2
log2
(46)
11
n
d?
loga h: + loge -1)
(47)
d
k
log2
(48)
2
where from Eq. 46 Eq. 47 we exploited the definition of X, which ensures that the first term in the r.h.s. of Eq. 46 is nonnegative; from Eq. 47 to Eq. 48 we used that for all E < 1/16 it holds that
1 - 21.
d²
loga
I Details of comparison with Malach et al. [20]
(c2 holds for a big enough constant c. Recall that m/ so we can
We show that cs 2 Camp [oRg(=)
always assume loga(2 (2) 2 1. We have
logz(c2)) (log2(c) + log, (z))
(49)
log (c) + 4 log, (c) (x) + (z)
(50)
(c) (z)
(51)
12 12 logT
(52)
where in (a) we used that 2ab < a² 12, and (b) that < 2ab for a and b greater than
We can then focus on showing that there is a big enough constant e such that ez
2
120amp (c) (z). We get e 12camp log logi(s) and we have
(c) loga log](c)
(53)
S Ve.
(54)
We can then focus on 2 12camp Vc, which satisfied for e 2 144c
'This term being nonnegative is equivalent to k(1 k/x) 2 1/27, and since 1 < l < An, any X S 1- - 11/27
ensures it.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and the introduction precisely reflect our contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have added discussion on the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Ys]]
23

---

Justification:
Assumptions for all results are accurately stated in our statements.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
oolicylyylyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.c.. cc/ healiiicggidee//oooo
conuubisssii onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://urr.pp.cccppuui//ttttttta
Answer: [Yes]
Justification:
The research conducted confrms in every respect with the NeurIPS Code of
Ehtics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: A small section discussing the potential impacts of our work has been added to the paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: We not releasing any data or models (apart from mathematical models) hence there no risk of misues.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Everything is cited properly and assests required.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswit wwwwwwtheedee...oee cww datastts has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: No assets introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
No such research was conducted.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
There are not study participants.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "r5uHizBZJg", "reviewer": "Reviewer_WaBr", "summary": "This paper studies the strong lottery ticket hypothesis from the perspective of pruning sparsity. In particular, the paper noticed that all previous papers about the strong lottery ticket hypothesis fails to characterize the sparsity of the neural network after pruning, and aims at solving this question in the paper. The paper first extends the random subset sum problem to a case where the selected subset has a cardinality constraint. The paper proves a probability bound in terms of the candidate set's size for the random subset sum to achieve a certain accuracy. Then, the paper utilize this bound to the case of the neural networks by utilizing the technique in previous works, and shows the over-parameterization required to achieve a certain accuracy and sparsity after pruning at initialization. The paper also included a lower bound on such over-parameterization requirement.", "questions": "Why does the paper focus on the exact sparsity constraint $|S| = k$? Would it be more practical to focus on $|S|\\leq k$?", "limitations": "The paper has a good discussion about its limitation from a practical perspective. However, I believe that the paper needs to add some discussion about the limitation from a theoretical perspective (tightness of the bound, strength of the assumptions etc.)", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The topic considered in the paper is quite interesting and significant. Indeed, one draw-back of the strong lottery ticket hypothesis is that there is no guarantee on the sparsity level after pruning.\n2. A major contribution of the paper is that it extended the random subset sum problem to a case that involves a cardinality constraint on the subset. The proof seems quite technical and nontrivial.\n3. The paper also included a lower-bound on the over-parameterization requirement.", "weaknesses": "1. The statement of Theorem 2 and Corollary 1 seems weird. In particular, it should be noticed that for both Eq.(1) and Eq.(3), $n$ appears in both the left hand side and the right hand side of the inequality. With some simplification, it seems that the dependency on $n$ can be completely eliminated, and the size of $n$ does not contribute to whether the statement holds or not. In this case, it would be greatly necessary to understand how big the constant $c_{hyp}$ is, which is not stated in the theorem. Moreover, if $n$ is really not affecting the approximation error, then a better way to state the theorem would be to change Eq.(1) into a condition on $k$.\n2. The proof of Corollary 1 seems problematic. In particular, in Page 15, the first inequality after line 483, the $\\geq$ should be $\\leq$, since $Pr(\\exists z\\in[-\\sqrt{k},\\sqrt{k}],\\dots) \\geq Pr(\\exists z\\in\\\\{-\\sqrt{k} + i\\epsilon':i\\in[\\frac{2}{\\epsilon'}\\sqrt{k}]\\\\},\\dots)$ (because $\\\\{-\\sqrt{k} + i\\epsilon':i\\in[\\frac{2}{\\epsilon'}\\sqrt{k}]\\\\}\\subseteq [-\\sqrt{k},\\sqrt{k}]$). This breaks the whole proof.\n3. The definition of $\\alpha$ (the sparsity) is ambiguous. From the proof it seems that $\\alpha$ denotes the fraction of the zero elements. In this case, however, the result in Theorem 3 seems trivial. In particular, the size of the neural network scales inversely with the $\\gamma'$ (roughly the fraction of the nonzero elements), because to achieve $\\gamma'$ portion of the nonzero elements, one simply need to initialize $\\frac{1}{\\gamma'}$ independent neural networks and prune completely the rest $\\frac{1}{\\gamma'} - 1$. Moreover, the definition of $r$ is problematic since it seems that by defining $r = \\max\\\\{\\frac{d_i}{d_{i-1}}, \\frac{d_{i-1}}{d_i}\\\\}$, we must have that $r\\geq 1$ (instead of $r\\leq 1$ as claimed in the paper).\n4. This is a minor issue: the upper bound on the over-parameterization does not match the lower bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his precious feedback and the points they raised, which we find very valuable in improving the presentation of our result, and for the appreciation he expressed for the merits of our work.  \nIn the following, we address their concerns. \n\n**Weakness 1 (form of Eq. 1).** As the reviewer notices, equations 1 and 2 can be simplified by increasing the constant $c_{hyp}$; e.g. Eq 1 would become $n \\geq const \\frac {\\log(1/\\epsilon}{H(k/n)}$. We will use these simplified forms in the revised version of the manuscript. However, the dependency on $n$ cannot be removed, except when the sparsity ($\\alpha$) is considered constant (and the entropy term $H(\\frac kn = \\gamma)$, with $\\gamma=1-\\alpha$, is thus constant as well). We believe that our answer to Weakness 3 will clarify this point.   \n**Weakness 2.** In the inequality the reviewer is referring to, observe that the event on the l.h.s. (i.e. the existence of a $z\\in [-\\sqrt{k},\\sqrt{k}]$ which cannot be approximated up to $\\epsilon$) implies the event on the r.h.s. (i.e. that exists a $z$ in the given discrete set which cannot be approximated up to $\\epsilon’=\\frac{\\epsilon}2$), thus the probability of the latter event is larger and the direction of the inequality is as given. We emphasize that the second event is considering a different epsilon.   \n**Weakness 3.** We are glad that the reviewer mentions such a strategy of using a sample which is larger by a factor roughly  $1/\\gamma’$ and then actually only using only a fraction $\\gamma’$ of it, since it is a natural approach that we considered when we started working on the problem, and then realized that it was highly suboptimal. To see why, we observe that such a strategy would lead to a bound on the RSS (and thus, on the sparsity of the strong tickets) which essentially matches our Theorem 2 **as long as $\\gamma’$ is a constant independent of $n$**. The interesting regime are, however, sparsity levels which are not constant but scales with the network size; observe that also the classical results on the SLTH would be asymptotically uninteresting when the approximation error $\\epsilon$ is constant. In the latter non-constant regime, our result gets exponentially better. Indeed, as we mention, our bounds allow us to recover the polynomial regime proved by Malach when the desired sparsity scales polynomially in $n$, while the simple strategy wouldn’t.   \nAs for the definition of $r$, we confirm that it is meant to be at least 1, and the direction of the inequality in the manuscript was a typo: the fact that it is greater than 1 is indeed used in the second inequality after line 540.    \n**Weakness 4.** This is the reason in our paper we state that our results are *essentially* tight, since obtaining high probability requires an additional logarithmic factor. We remark that tightness up to logarithmic factors is already seen as significant in the SLTH literature, see for example Ferbach et al. (ICLR23). If instead we are only asked to succeed with constant probability, our results are then tight up to a constant and a factor $d$ in the logarithm (which is the same kind of tightness claimed in the seminal result by Pensia et al. (Neurips’20)). We will add an explicit remark in the introduction to make this point precise. \n\nAs for the **question** on why we consider the exact size rather than an upper bound, there is a theoretical and a practical reason.   \nFrom a theoretical point of view, we find the result on the exact size more valuable, since it is a stronger requirement and implies the other result where only an upper bound is required. If we were to relax the condition, we would only improve our result by a constant factor, since the size of the number of subsets of size at most $k$ (for $k\\leq n/2$) is essentially the same as those of size exactly $k$ (this classical inequality is used for example in the second inequality of the equation after line 580 in appendix).   \nFrom a practical point of view, fixed-size subsets would guarantee that the lottery ticket of a target network whose layer widths satisfy particular proportions (e.g. being all equal), would also have the same layer width proportions, which can lead to a computation time advantage.  \nWe will add the above discussion in the revision of our paper. \n\nTo summarize, we hope to have properly addressed all concerns the reviewer had for our paper, and that the clarifications we provided and the discussion that we will add to the manuscript with the points mentioned above, will lead the reviewer to revise his opinion on our paper. Please let us know if there is anything else we should discuss. \n\nWe take the opportunity to express again our gratitude to the reviewer for the time they invested in reviewing our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w93kSutfKz", "reviewer": "Reviewer_HSXo", "summary": "The authors consider the strong lottery ticket hypothesis (SLTH), which is roughly a statement that a large random neural network contains a sparse subnetwork whose performance is comparable to the entire network. By analyzing a fixed variant of the random subset sum problem, which is about the size of the sample of i.i.d. random variables to approximate a fixed number, they improved the previous results on the SLTH with the guarantee on the sparsity of the subnetwork.", "questions": "- The assumption on the sum-boundedness in Definition 1 must hold for a very general density function $f$, since it is even weaker than the statement of the local limit theorem for density.\n(See, e.g., Theorem 7 in Section 7.2 of \"Sums of Independent Random Variables\" by Petrov.)\nThus, I think some parts of Section 3, especially Definition 1 and Lemma 1, can be changed.\n- Below are small errors and typos:\n1) In line 136, there is something missing in \"we $\\Omega$\".\n2) In line 140, $f_{\\Sigma_{[i]}}$ should be $\\Sigma_{[i]}$.\n3) In line 182, \"independent and uniformly at random\" sounds weird.\n4) In Equation (6) and other places, $X_S$ should be $Z_S$.\n5) In line 186, \"Eqs. 5 and 8\" should be \"Eqs. 6 and 8\".\n6) From Equation (19) to Equation (20), why $H_z(\\tilde{S})$ can be dropped?\n7) The equation below 204 seems wrong. I guess $(z-y)$ should be $z$ in the second line.\n8) In line 219, \"Let $F$ to be\" should be \"Let $F$ be\".", "limitations": "The work does not seem to have potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The idea based on the fixed-size random subset sum problem seems new and works well.\n- The writing is in general very clean, especially the introduction and the related work.", "weaknesses": "- I think the authors should check more about the references for the results in Section 3. (See Questions.)\n- There are many small errors and typos in the manuscript. (See Questions.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful to the reviewer for the time they invested in reviewing our paper, which we find very valuable for improving it.   \nIn the following we address the reviewer’s concerns individually. \n\n**Question 1.** We agree with the reviewer that the assumption of sum-boundedness in Definition 1 holds for a very general density function $f$. In fact, in Appendix B (line 392) we mentioned the possibility of extending our result to a larger family of densities, namely unimodal, with bounded variance, and bounded third moment. In the submitted paper, we focused on the uniform distribution because, together with Gaussian, these are the distributions commonly used in our application (random initialization of neural networks). We will move this remark to the main body, write the result for the sum-boundedness of this more general family of distributions, and give the result for the uniform distribution as a corollary.  \nHowever, we want to point out that sum-boundedness is not weaker than the statement of the local limit theorem for density that the reviewer mentions. Sum-boundedness guarantees a lower bound on the support of the function for any $i$ (rather than asymptotically in $n$). The proof of our main result wouldn't work without such a guarantee. To clarify this, we will briefly compare our condition with the local limit theorem for density. Please let us know if you meant something else.   \nFinally, to prevent any confusion related to the distributions for which our results hold, we would like to emphasize that, by the sampling argument in our paper, the NNs results we obtain apply to any distribution that can be written as a mixture of densities that include a uniform with constant probability, thus recovering all distributions traditionally considered in the SLTH, such as gaussian etc. In practice, extending Lemma 1 to even more general distributions, might just make the argument more technical, without changing much the impact of the result for the SLTH.  \n\n**Question 2 (typos)**. \n1. “we [drop] $\\omega$”, thanks!  \n1. We confirm that it’s not a typo, the definition concerns the value of the probability density function of the sum rather than the actual value of the random variable itself.  \n1. “independent[ly] and uniformly at random chosen subsets”, thanks!  \n1. Thank you, we will correct it!  \n1. It should be “Eqs. 6 and 7”, thanks!  \n1. That’s because $A$ only contains elements which are not in $\\tilde S$, thus the event whose probability we are considering is (conditionally) independent of $\\tilde S$l. Hence,  it is correct to drop the conditioning in the way we do. We will add an explicit explanation for it in the revised version of the manuscript.   \n1. The calculation is using the fact that, given the conditioning, the density of $\\Sigma_A$ is the same as the density of $\\Sigma_{[k-1]}$ (without conditioning), thus the probability that $\\Sigma_A$ is an epsilon-approximation of $z-y$ is the same as the probability that $\\Sigma_{[k-1]}$ is an epsilon-approximation of $z-y$. Please do not hesitate to tell us if such an identity is unclear.   \n1. Thanks!\n\nWe hope to have properly addressed all concerns the reviewer had for our paper, and that the clarifications we provided may improve their opinion of our paper. Please let us know if there is anything else we should discuss.   \nWe take the opportunity to express again our gratitude for the time they invested in reviewing our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G09TAGMCpT", "reviewer": "Reviewer_cEnR", "summary": "This work focuses on the theoretical side of the Strong Lottery Ticket Hypothesis. It proposes and studies a fixed-size version of the canonically used Random Subset Sum (abbreviated RFSS) problem in previous proofs for this hypothesis. Then it applies the result of RFSS to prove that overparameterized networks can be pruned to approximate target networks with guaranteed sparsity. A corresponding lower bound is provided to show the tightness (up to log factor) of the overparameterization needed.", "questions": "- On line 225 Theorem 3, is it $r = \\max_i \\min\\{…\\}$ instead of only $\\max_i$ (in which case it’s always at least 1)?\n- What abbreviates to ANN in Theorem 4?", "limitations": "Addressed by the authors.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed fixed-size version of RSS is an interesting problem and is potentially of independent interest.\n- Based on the literature reviewed here, this work is the first one that provides a (high probability) size guarantee for the pruned subnetwork.\n- A lower bound on the overparameterization size is also provided, which helps complete the picture and matches the high probability guarantee up to a log factor.", "weaknesses": "- Elaboration of Theorem 3 is helpful in the main text. I do not see how it answers the question proposed in Introduction. Namely, for given target network size $m'$, the internal dimensions $d_\\ell$, and a desired sparsity $\\alpha$, how should we pick the number of parameters (or the number of layers) for our networks? Also, how does it imply the previous results?\n- More discussion should be given to the results on the hypothesis (e.g. elaborations) in Section 4 and 5. While the RFSS result is key, instead of having the whole proof in Section 3, the authors can leave a sketch of the proof idea and where it distinguishes / extends RSS results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for the time they invested in reviewing our paper and the appreciation they expressed for our work.   \nIn the following we address the reviewer’s concerns individually. \n\n**Weakness 1 and 2.** We agree with the reviewer that the paper would greatly benefit from a longer discussion on Theorem 3 and on Section 4 and 5. In the submitted version, we felt compelled to give more space to the main proof, since it is our main technical contribution. We like the idea of making more space for discussing the result, and in the revised version of the manuscript we are going to move most of the details in the appendix, so that we can save space for discussions after Theorem 3 and in sections 4 and 5, as well as those resulting from the other reviews.   \nIn particular, regarding Theorem 3, we will add a discussion on how it answers the initial question. In general, the number of layers will be $2\\ell$ where $\\ell$ is the number of layers of the initial network (although it could be improved to $\\ell+1$ as mentioned in line 266 through the strategy discussed in line 115, which we don’t explore in the paper); as for the number of parameters, considering here for simplicity the case in which all layers have width $d$, number of parameters will be of order $d^2\\frac{\\log^2(\\frac{\\ell d^2 (1-\\alpha)}{\\epsilon})}{H(\\alpha)}$. The reason we don’t phrase the results in Section directly as an answer to our question in the introduction, is to keep them in the same form they appeared in previous work, for an easier comparison.   \nFinally, regarding the comparison with previous results, we had a brief discussion in Section 1.1, which we will make more detailed thanks to the space that will be freed by moving the technical details of the proof. In particular, the logarithmic regime in Pensia et al. (Neurips’20) is readily recovered for constant sparsity, since in that case the entropy term is constant. As for the polynomial regime of Malach et al. (ICML’20), the calculation is more involved. To illustrate it more quickly, let us assume all constants are 1 and that we can disregard the dependency on $n^*$ inside the logarithm on the right hand size of the equation (as discussed with reviewer WaBr, we will get rid of the latter dependency when revising the manuscript). Finally, let’s consider a network where all layers have $d$ neurons. With the aforementioned simplifications, we have the equation $n\\geq \\frac 1{H(\\gamma)}  \\log^2\\left(\\frac {\\ell d^2 \\gamma}{\\epsilon}\\right) =  \\frac 1{H(\\gamma)}  \\log^2\\left(x \\gamma\\right)$ where $x = \\frac {\\ell d^2 }{\\epsilon}$. To recover polynomial sparsity, consider e.g. $\\alpha=1-\\gamma=1-\\frac{\\log x}{x}$, for which we get that $n \\geq x \\frac {\\log^2 \\log x}{(\\log x) \\log(x/(\\log x))}$, which is satisfied for  $n \\geq ( \\frac {\\ell d^2}{\\epsilon} )^{const}$ for some $const$. Without the simplifications we made, we would just get a different value of the $const$ in the latter expression.   \n**Question 1.** We confirm that $r$ is defined as a maximum, and the direction of the inequality is a typo ($r$ is used in the second inequality after line 540, where it is important that it is larger than 1). We will correct the direction of the inequality in the revised version of the manuscript.   \n**Question 2**. ANN is an abbreviation of “artificial neural networks”; we apologize for overlooking the definition of the acronym. Unless the reviewer has a different opinion, we will update the name of the theorem with the simpler “SSLTH for Equivariant Networks”.\n\nWe thank the reviewer again for his valuable feedback and suggestions on our work. Please let us know if there is anything else we should discuss.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SiCnD0Vgaw", "reviewer": "Reviewer_1iUR", "summary": "The authors propose an existence proof for Strong Lottery Tickets(SLTs) by improving over the existing method which used the Subset Sum approximation to construct source networks, which involved using subsets of variable sizes in order to approximate target parameters. Instead the authors show the existence of SLTs using subsets with fixed sizes (RFSS) and leverage this results to show the existence of SLTs.", "questions": "See above", "limitations": "The work leverages Random Fixed Subset Sum result to adapt a large body of work showing the existence of SLTs. However, in the context of the existing work, this result seems incremental and lacks numerical validation.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors propose the Random Fixed Subset Sum approximation instead of the previously used Subset Sum approximation to prove the existence of Strong Lottery Tickets. This results allows them to use a subset of a fixed size to approximate parameters in a target network.\n2. The subsequent existence proof interpolated between the result of Malach et. al. [1] (which uses a single parameter) and Pensia et. al. [2] (which uses a subset of parameters) based on the size of the subset being used. The authors also extend this result to equivariant networks.", "weaknesses": "1. Given the theoretical nature of the work, the overall contribution appears limited as it can only connect the existing results established by [1], [2], [3].\n2. The main insight in this paper is that by using a fixed subset size to approximate parameters in the target, one can exactly estimate the number of parameters required in the strong lottery ticket, which was previously not possible due to the variable size of subsets. However, as Burkholz et. al. [3] have shown via numerical simulations, the number of parameters required to satisfy the theoretical conditions for subset sum proofs can be relatively easily approximated. For example, they use a subset of size 15 for their simulations which is sufficient. Given this, the overall contribution of the paper seems incremental \n\nThe following claims in the paper need to be addressed appropriately.\n1. ‘We provide the first proof of the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity of the subnetworks.’ While the existence of SLTs has been shown before in various settings, the sparsity of these networks has also been estimated using numerical simulations by Burkholz et. al. [3]. This is primarily because the size of the subset required to effectively approximate a parameter seems to have a natural upper bound (15 as shown in [3]). Hence, while the authors are able to show this exactly, previous theoretical work did a decent approximation. \n2. ‘It is important to note that, to this day, we only have proofs on the existence of such subnetworks, also called winning tickets, but it remains an open question how to find them reliably.’ While the theoretical framework is laid out by the authors to construct the SLTs, the paper lacks numerical constructions of real world examples of neural networks using the proposed framework. Are the networks found by the proposed method sparser than the one's found by [3]? \n\n\n[1] Malach, Eran, et al. \"Proving the lottery ticket hypothesis: Pruning is all you need.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Pensia, Ankit, et al. \"Optimal lottery tickets via subset sum: Logarithmic over-parameterization is sufficient.\" Advances in neural information processing systems 33 (2020)\n\n[3] Burkholz, Rebekka. \"Most activation functions can win the lottery without excessive depth.\" Advances in Neural Information Processing Systems 35 (2022)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback on our work. \nIn the following we address the reviewer’s concerns individually.   \n\n**Weakness 1**. We are sorry if the discussion in Section 1.1 in which we discuss the links between our results and \\[1,2,3\\] gives the impression that our work only connects the existing results established by \\[1\\], \\[2\\], \\[3\\]. As we explain in the following, this is not the case.   \nThe main contribution of our paper is to provide theoretical guarantees of the existence of subsets of bounded sizes for the random subset problem, and then to use this result to show the existence of lottery tickets of given sparsity. No results of this kind can be found in \\[1\\], \\[2\\] or \\[3\\].  \nWe mention a connection with the results of \\[1,2\\] in Section 1.1, namely that, when the sizes of the subsets are small, the overparametrization is polynomial in $1/\\epsilon$, but when the subsets are large, the overparametrization is logarithmic in $1/\\epsilon$. It is merely a discussion of the order of our results, rather than a statement that the results appear in \\[1\\] or \\[2\\].  \nOur result allows to fill a gap in the LSTH literature, since the existence of winning tickets was proved, but not the existence of sparse tickets.   \n**Weakness 2\\.** From our understanding, the reviewer is arguing that, in their view, the numerical experiments provided in previous work on the sparsity of the subnetworks were satisfying enough for practical applications, and they do not see much value in providing rigorous mathematical results.  We kindly disagree with the view that a theoretical result can be considered incremental on the basis of previous numerical experiments. In fact, we believe that the numerical experiments in Burkholz et al. (Neurips’22) (which we discuss in our related work), further motivates our work by empirically indicating the existence of a phenomenon that was missing a mathematical understanding.   \nAs for the criticism of the first quoted claims, the reviewer seems to imply that a subset of size 15 is enough to approximate any target network within epsilon in practice. While it is true that the RSS states that for a given epsilon, a given subset size is enough to approximate a single weight, it should be noted that this is not the case when the goal is to approximate the output of the entire NN, as the SLTH results show. Indeed, the errors amplify through the layers, thus, the subset size required to approximate the target network within epsilon depends on its depth and width. Our results express this dependency for sparse subsets.  \nAs for the second quoted claim, our work does not provide a constructive algorithm to find the subnetworks, since our results are existential. We further clarify this point in our Limitations section, lines 303-304, where we point out that no theoretical guarantees are available, although we cite promising methods (that have, in fact, provided the motivation for the theoretical research on the SLTH). \n\nWe hope that our rebuttal satisfyingly addresses all the reviewer’s concerns. Please let us know if anything needs further discussion. In the meantime, we thank the reviewer again for reviewing our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to express our gratitude to the reviewers for their thoughtful reviews and valuable feedback. We appreciate the time and effort they have invested in evaluating our work. We've carefully considered their comments and would like to summarize our response to the main points raised:

**On the strengths raised by the reviewers.**   
We are pleased that our work has been recognized as filling a gap in the literature on a *“topic \[…\] quite interesting and significant*”: “*Indeed, one draw-back of the strong lottery ticket hypothesis \[SLTH\] is that there is no guarantee on the sparsity level after pruning*”. “*this work is the first one that provides a (high probability) size guarantee for the pruned subnetwork.*”  
Our method, “*extend\[ing\] the Random Subset Sum (RSS) problem to a case that involves a cardinality constraint on the subset*”, was estimated “*a major contribution*”, “*new and work\[ing\] well*”, “*an interesting problem and \[…\] potentially of independent interest.*”  
The proof was estimated “*quite technical and nontrivial.*”  
We would like to thank the reviewers for this very positive feedback.   
**Clarity and Presentation.** We acknowledge the need for improved clarity in some sections. We'll revise the manuscript to:

* Simplify some equations as discussed;  
* Expand discussions on Theorem 3 and Sections 4-5;  
* Clarify definitions and correct minor typos;  
* Move technical details to the appendix to allow for more comprehensive discussions in the main text.

**Novelty and Contribution**. We want to emphasize that our work provides new theoretical guarantees for the existence of sparse subsets in the random subset sum problem, which we then apply to prove the existence of lottery tickets with specific sparsity levels. This fills a gap in the Lottery Ticket Hypothesis literature by providing rigorous mathematical results where previously only numerical experiments existed.  
**Technical Clarifications**. We'll clarify the dependency on $n$ in our bounds and explain why it cannot be removed except in constant sparsity cases. We'll elaborate on why our approach is more optimal than simpler strategies for non-constant sparsity levels. We'll provide a more detailed comparison with previous results, showing how our work qualitatively recovers and extends earlier findings.   
**Practical Implications**. While our work is primarily theoretical, we believe it provides important foundational understanding that complements and supports existing empirical findings. We acknowledge that our results are existential rather than constructive, as noted in our Limitations section.  
**Technical Accuracy**. We understand that the technical nature of our proofs may have led to some misunderstandings. We're confident in the correctness of our technical steps and have provided detailed clarifications to address these concerns. In the revised version, we'll place additional emphasis on these critical parts of the proof to ensure clarity for all readers.

We're committed to improving our manuscript based on your feedback. We believe these revisions will address the reviewers’ concerns and strengthen the presentation of our work. We welcome the reviewers to let us know if any further discussion and clarification is needed.  
In the meantime, we thank the reviewers again for their constructive criticism and the opportunity to improve our paper.

Meta-review: **Summary:**

The paper provides theoretical guarantees on the existence of sparse subnetworks (strong lottery tickets) in random neural networks. It extends the Random Subset Sum problem to include a fixed-size constraint, allowing analysis of subnetwork sparsity. Results show how overparameterization requirements scale with desired sparsity levels. Lower bounds are also provided to demonstrate tightness of the results

**Strengths:**

- Novel extension of Random Subset Sum to fixed-size case
- First theoretical guarantees on sparsity levels for strong lottery tickets
- Bridges previous results, recovering both polynomial and logarithmic regimes
- Well-written introduction and related work sections
- Technically non-trivial proofs

**Weaknesses:**

- Some lack of clarity in presentation of main results and implications
- Limited discussion of connections to previous work in main text
- Purely theoretical results without empirical validation
- Incremental contribution according to some reviewers

**Key Discussion Points:**

- *Novelty:* Authors clarified this is the first theoretical guarantee on sparsity, not just connecting previous results
- *Practical relevance:* Debate over value of theoretical results vs. previous empirical approximations
- *Clarity:* Agreement to expand discussions of main theorem and implications in revision
- *Technical details:* Some misunderstandings resolved through author explanations
- *Comparison to prior work:* Plans to elaborate more on connections to previous results
- *Generality:* Clarification that results apply to common initialization distributions beyond just uniform

Overall, reviewers generally found the work technically sound and filling an important gap in the lottery ticket literature, though some felt the contribution was incremental. Scores ranged from borderline reject to weak accept initially, with most reviewers increasing scores after author responses clarified key points and agreed to improve exposition. The consensus seems to be that this is a solid contribution.
Decision: Accept (poster)