Most Activation Functions Can Win the Lottery Without Excessive Depth
Authors: Rebekka Burkholz
Venue: NeurIPS 2022 Accept (2022)
Keywords: lottery tickets
deep learning
theory
subset sum

Abstract: The strong lottery ticket hypothesis has highlighted the potential for training deep neural networks by pruning, which has inspired interesting practical and theoretical insights into how neural networks can represent functions. For networks with ReLU activation functions, it has been proven that a target network with depth L can be approximated by the subnetwork of a randomly initialized neural network that has double the target's depth 2L and is wider by a logarithmic factor. We show that a depth L+1 is sufficient. This result indicates that we can expect to find lottery tickets at realistic, commonly used depths while only requiring logarithmic overparametrization. Our novel construction approach applies to a large class of activation functions and is not limited to ReLUs. Code is available on Github (RelationalML/LT-existence).

Most Activation Functions Can Win the Lottery Without Excessive Depth
Rebekka Burholz
CISPA Helmholtz Center for Information Security 66123 Saarbrücken, Germany
burkholz&cispa.de
Abstract
The strong lottery ticket hypothesis has highlighted the potential for training deep neural networks by pruning, which has inspired interesting practical and theoretical insights into how neural networks can represent functions. For networks with ReLU activation functions, it has been proven that a target network with depth can be approximated by the subnetwork of a randomly initialized neural network that has double the target's 's depth 27. and is wider by a logarithmic factor. We show that a depth I. + 1 network is sufficient. This result indicates that can expect find lottery tickets at realistic, commonly used depths while only requiring logarithmic overparamettriaation Our novel construction approach applies a large class of activation functions and is not limited to ReLUs. Code is available on Github (ReeltionalMLLLLTexissennc
Introduction
The Lottery Ticket Hypothesis and, in particular, its strong version 38 postulate that pruning deep neural networks might provide a promising alternative to training large, overparameterized neural networks with Stochastic Gradient Descent (SGD). Pruning has the potential to only identify small scale neural networks that possess meaningful, task-specific neural network structure and generalize better due regularization [I] but also to reduce the computational burden associated with deep learning (50)
133
Also from theoretical perspective, it has been shown that for every small enough target network sufficiently large, randomly initialized neural network, the source network, contains a subnetwork, the lottery ticket (LT), that can approximate the target up to acceptable accuracy with high probability. 32 has been the first to provide probabilistic lower bound on the required network width of the larger random network. This bound has been improved by 37 30 to a width that is larger than a target's width only by a logarithmic factor. The limitations of these works are that they all are restricted to ReLU activation functions and assume that the larger random network has twice the depth of the target network L, = 2L,-
However, it is well known that deeper networks tend to have higher expressiveness, they can approximate certain function classes with significantly fewer parameters than their shallow It could therefore reduce the overall sparsity of the target and the LT to allow the target to utilize more of the source depth L, for sparser representation. A lower depth requirment could also []] have therefore derived lower bounds for the width of the random network of depth l_ = L4 + 1, but these can only cover extremely sparse target networks, as the width requirement is polynomial in the inverse approximation error 1/e.
counterparts 3% 49
In contrast, we derive a novel construction that only requires logarithmic factor. While we utilize subset sum approximation results like 37,, we allow target network to have almost the same depth
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

as the source network with depth L3 2 L, + 1 instead of L 2Lz Our derivations further apply to large class of activation functions that includes but not limited ReLUs.
The reduced depth requirement and flexibility in the activation function of our construction can result in significantly sparser neural network target networks and thus also LT's. For example, f(x) = x² can be approximated up to error by shallow ReLU network with (1/e)) parameters, while a deep enough network only needs ([log(]/e) parameters 63 Also the activation function determines the possible target sparsity, e.g., x² can be represented with only 4 parameters for all > if x(œ) = (maxf2: zz 03)². Therefore, the potential sparsity of the final lottery ticket depends critically on the choice of activation functions and architecture of the source network, including its depth and width. We provide a theoretical foundation that provides flexibility regarding these choices.
Contributions 1) We prove the existence of strong lottery tickets as subnetworks of a larger randomly initialized source neural network for a large class of activation functions, including ReLUss 2) We derive a novel construction that requires the source network to have almost the same depth (L + 1) as the target network, thus, allowing it to leverage the potential representational benefits associated with larger depth. 3) Despite the reduced depth requirement we keep the width requirement logarithmic in the approximation error c. 4) Our proofs are constructive and define an algorithm that approximates a given target network by pruning source network. We verify in experiments that this algorithm is successful under realistic conditions.
Related Literature
Many pruning methods have been proposed to reduce the number of neural 50 14 39, 28
network parameters during training [22] 35 19 16
48 40 or thereafter 27
41
23
20
9
26
and have been applied in different contexts, including graph neural Furthermore, pruning can have provable regularization and generalization The algorithms are most useful for structure learning at lower sparsity levels 4A 24
34
52
networks 5 and GANs
properties ST
but at least Iterative Magnitude Pruning (IMP) [9 13 can fail in identifying LTs that perform superior to random or smaller dense networks BT.
can therefore be beneficial start pruning from sparse random architecture rather than a dense network [I0. 22) which saves computational resources. Other options to achieve the latter are to identify and train on core sets [53] and focus on pruning before training [7 25 46 45 388. Yet, iterative pruning methods often perform better 15
but all face challenges in finding highly sparse LTs (
Most of the discussed pruning methods try to find LT's in a 'weak' (but powerful) sense by identifying sparse neural network architecture that is well trainable starting from its initial parameters. Strong LTs are sparse subnetworks that perform well with the initial parameters and, hence, do not need further training 144 B
Their existence has been proven for fully-connected feed forward networks with RELU activation functions by providing lower bounds on the width of the large, randomly 17 In addition, it was shown that multiple candidate tickets exist that are also robust to parameter quantization X Our first objective is to extend the known theory to other activation functions beyond RELUS. Note that the approach that we develop here has also been partially transferred to convolutional and residual architectures [. However, [I does not cover activation functions with nonzero intercept (like sigmoids) and their width dependence on the error is less advantageous.
initialized source network 12
37 36
2 Constructing Lottery Tickets
Informally, our goal is to show that any deep neural network of width n, and depth T., or smaller can be approximated with probability 1-6 8 up to error by pruning a larger randomly initialized neural network of width On, log/ log[n, min d. e)] and depth 2L, or a network of smaller depth L, 4.+1 1 and width O(n, log[neL, log (1/6)/ min(d, e)]), ). as long as the target network and the large random network rely on the same activation functions. Note that we often omit the dependence on 8 in our discussions because we usually care about cases when e < 8. Next we explain the required background to formalize and prove our claims.
Background and Notation Let a fully-connected feed forward neural network f f D C R -> TT be defined compact domain D and have architecture ñ [no, Ri. i.c., depth L and width n; in layer i E (O,..,, L). with continuous activation function Φ(x). On the relevant compact domain let (xx) have Lipschitz constant T'. It maps an input vector x (0) to neurons 2(" as

---

x(1) = (h()) with h = (0 b(), where h is the pre- activation, W R is the weight matrix, and b() E IR is the bias vector of layer 1. Without loss of generality, let us assume that each parameter (weight or bias) 0 is bounded as |0] S 1. Primarily, we distinguish three networks, First, we want to approximate a target network J. with architecture ni, of depth Le consisting of N₂ total nonzero parameters. Second, this approximation is performed by a lottery ticket (LT) fe that obtained by pruning larger source network Sa. which we indicate by writing fo C f.. Third, this source network is larger fully-connected feed-forward, randomly initialized neural network with architecture ni and depth L.. While most LT existence results require exactly L. 2Lg, we show that any L. 2 L + 1 is sufficient.
To simplify the presentation, like most works, assume convenient parameter initialization that we have to choose with respect to the activation function if we approximate target layer with two source network layers. In most cases, make the following assumption.
X
X,(
Assumption 2.1 (Convenient initialization). We assume that the parameters of the source network fa are inde- U ([),,1)), 6.")
pendently distributed as Wij (!)
U ([-1, 1]) and 600) = 0 for ( > 1.
X(
Note that also other parameter distributions, e-g. normal distributions, are covered as long as they contain uniform distribution 77. since this allows to solve subset sum approximation problems (see appendix for a formal def- inition). While most works assume zero biases (o!") 0), as they focus on target networks without biases 32 37),
we initialize the biases in the first layer nonzero. This is sufficient to approximate nonzero target biases, since we can always construct constant neurons each layer (see pink blocks in Fig. (c)).
X
x
The convenient parameter initialization can always be transferred to realistic one by learning or just applying appropriate layer-specific scaling factor Ar, as also pro- posed in LT pruning experiments
(54). For homogeneous activation functions like RELUs,
global parame- ter scaling is sufficient [2]. For instance, let us assume that our initial parameters Layer are distributed U (I-oi, oil). A common choice would be He [21] or Glorot [8] initialization with og 1/yni In this case, we would need to adapt our proofs by replacing {0') LT by (Ae0)) } with
Figure 1: LT construction idea. (a) Tar- get network ft. (b) Lo 2L, construc- tion of fc. (c) Lo = L, + construction of fe. Subset sum blocks are framed (purple corresponding to target neurons, pink to biases). Dashed links only exist if source network biases in layers >> 1 are initialized to zero.
1/a: construct the same func- tion that we have derived for convenient initializations.
For specific activation functions with (0)) 3f (e.g. SIG- MOIDS), instead of Assumption 2.1 we will assume an initialization that has originally been derived to ensure dynamical isometry for RELUS I Interestingly, this initialization also supports LTs.
Assumption 2.2 (Looks-linear initialization). We assume that the weight matrices of the source
MD) - -M()
network fa are initialized W0O - (0
where (1) and ((0) are distributed as in (
Assumptions
In general, measure the approximation error with respect to the supremum norm, which is defined as || := supxed ||g||; for any function g and the Ll-norm || := Σ. [ In the formulation of theorems, also make use of the universal constant C' that can attain different values.
Lottery Tickets as Subnetworks
32 were the first to give probabilistic guarantees and provide
lower bound on the required width of the source network that is polynomial in the width of the target
3

---

network. Their L(e)) requirement, or under additional sparsity assumptions ( has been improved to logarithmic dependency of the form On log(n,L.)/e) for weights that follow an unusual hyperbolic distribution R6 and One log(n, ) for uniformly distributed weights 377. While these assume target networks with zero biases, [ transferred the approach by [37] to nonzero biases. All assume that the source network has exactly twice the depth of the target network (L, = 2L)). Only [I]] prove existence for extremely sparse tickets for L, = Le + but the width requirements are unrealistic for most target architectures. 3 show how to leverage additional depth L 2 2L, but still assume excessive depth in general. Furthermore, all of these works focus on RELU activation functions. Both limitations, the focus on RELUs and the L 2L, requirement rely on the following construction idea that is also visualized in Fig. aa-b). Every layer of the target network ft is represented by two layers in the lottery ticket f. and equipped with RELU activation functions on = max (xr 0} with the possible exception of the last output layer. We can obtain two layers by representing the identity (1-1)
@n(z) 02((- and writing each target neuron T L1,5 [i.j (n(--1) - w
(!)
as o,, = Φπ E; w(() "1, (1))) + (.) = oo E, " UR
( wi,00n on (-
The advantage of this 2-layer representation is that (a) we gain the flexibility to select the neurons in the middle layer among a higher number of available neurons in the source network and (b) these neurons are univariate so that they depend approximate with high probability. The question is how many nodes no in the middle layer of the source network are required to guarantee an accurate selection. The answer distinguishes previous work. 37 achieve a factor (where n2 = -yn+) that is logarithmic in ns. c, 6, etc. by solving a separate subset sum approximation problem for each parameter utilizing results by B0 these results to target networks with nonzero biases.
single nonzero parameter and are thus simple to
transfers
Our first contribution is to extend a similar construction to a wider class of activation functions that is not restricted to RELUS. We need this result to approximate at least the first layer of our target network in our second contribution, layers, we propose to construct the subset sum blocks for the next layer directly from the previous layer by sharing nodes in the construction. This has multiple advantages. The obvious one is that can use the available depth of the source network to start from a potentially sparser target architecture to solve given problem. Also the LT itself consists usually of less neurons. Furthermore, the subset sum approximation of parameters becomes more efficient.
L + 1-construction, as shown in Fig. c).. For the remaining
Subset Sum Approximation In the discussed construction, we generally have multiple random neu- rons and parameters available approximate target parameter = by 2 up error so that [2 3| < c. Let us denote the independent random variables that we can use for this approximation as X1, ..... Xmm- If they contain uniform distributions, Lueker (30] has shown that m 2 C' log(1/ min(e, 6}) is suffi- cient for the existence of a subset / C {1..., m so that the approximation of 2 by 2 = Exe/ X2 is successful with probability at least distributions as well as their products have this property (37]. For convenience, a precise corollary is stated in the appendix as Cor. Aor.A.2 Note that C depends on the distributions of the X₃ and usually larger in the two-layers-for-on foe than in the one- mee-layr--fr-one construction, because the X are given ((+1)
8. Standard distributions of interest like uniform and normal
(I+1) (I)
by products X oosk Woky in the former but X₁ wook in the latter case.
2.1 Two Layers for One
Our first contribution is to transfer the two-layers- for-one- construction to activation functions that can be different from ReLUs. We will utilize this result also in our one-layer-for-one construction to represent the first layer of the target network. This is necessary as the input neurons are fixed. We need to increase their multiplicity in the first layer of the source network to solve subset sum approximation problems that create target Layer I in the LT's Layer 2.
2.1.1 Activation Functions
The main property of ReLUs ΦR that is utilized in LT existence proofs is that we can represent the identity as x = (x)xx) - Φ (-)) This identity is exact and holds for inputs x E R. Yet, we can show that, in combination with the right initialization of the source network, it is sufficient if we can approximate the identity on an interval that contains This approximation is feasible with most continuous activation functions that are not constant zero in neighborhood of O, as we detail next.

---

Assumption 2.3 (Activation function (first layer)). For any given é' > 0 exists neighborhood I=a(e'), of 0 with a(e') > 0 so that the activation function & can be approximated by o(x) on that neighborhood such that su ld(x) x(z)) S c', where ((x) m + d for x 2 0 and
((x)) m_ x + d for x < 0 with m++ - d E IR, and m4 m- + 0. We further assume that, if a(ar) is finite, g(x) = x/ e/a(x)) is invertible on an interval J0, e with e" > 0 and limz-so ((x) = 0.
Most continuous functions and thus most popular activation functions fulfill this assumption. For instance, RELUS (n(x) (2, 0) inflict zero error on I (i.e., 0 = xc) with m4 = 1, m_ = 0, and d = 0. Similarly, LREL.U can be represented without error by m = 1, m a, and d 0 for an a > 0. <(x) = tanh(r)) is approximately linear so that tanh(x) - x|| S /²/3 for [2| < xt / which can be seen by Taylor expansion of tanh. This implies that the choice m4 = 1, m_ 1, and d 0 with
min m (3c') 1/3 TT 7/2] fulfills our assumption. SIGMOIDS x(z) 1/(1+ cxp()))
can be analyzed in the same way with m4 m- 0.25, d 0.5, and min min((48e))1/3, 7) since (bxx) = (tanh(z/2)+ + 1). We should point out that not all continuous functions fulfill this property. Counterexamples include a shifted ReLU x(x)) Φ 1) <(x) = | However, in our L + I-construction, almost all activation functions can be arbitrary continuous functions. We
will only ask the activation functions in the first layer to meet our assumption above. How can we represent the identity with such activation functions?
Lemma 2.4 (Representation of the identity). For any d' > O, for a function ((x) that fulfills Assumption 2.3 with a = a(c') > O, and for every x E a--a,,) a) we have
2c'
x
m+ + m_ (6(x) - -b(=x)) <
(I)
m4 + m
Note that RELUS and LRELUS inflict no approximation error so that the above statement holds also for e' 0 and cc. Some activation functions can have other advantages over RELUs. For instance, functions for which m = m_ m and d = O like TANH can also be approximated by |a (<z)/ml S c'/m and do not need separate approximations of the positive and the negative part. Furthermore, SIGMOIDS and general activation functions with d o 0 do not need nonzero biases in the source network, since we can approximate bias by random variables of the form X₁- = (O).
The challenge in utilizing this lemma is to incorporate the error that is inflicted by the approximation of the identity in addition to the pruning error into the analysis of the total approximation error. The allowed interval size a also influences which variables can enter our subset sum blocks and could affect our width requirement if we would not initialize our parameters in the right way.
2.1.2 Lottery Ticket Existence (Two-for-One)
Our first goal is to identify a LT fe that approximates a single hidden layer neural network f((x): : D C
R + IR with fe(x) = de (E " + b,). We could easily extend this result to approximate each layer of multilayer neural network but we will discuss more promising alternative that uses the following result for approximating the first layer only. fc can be obtained by pruning a fully-connected source network fs of depth I,, 2 with ng,1 hidden neurons that equipped with the activation function do. which can be different from the outer Φi. The additional layer in fa has
the purpose create multiple copies of input nodes that can be used in subset sum approximations.
To achieve this despite the potential non-linear activation function do in the hidden layer, we have to approximate the identity with the help of do. The precise approximation can pose two additional challenges in comparison with the standard construction for RELUS. (a) If the piece-wise linear approximation of do in Assumption 2.3 holds only on finite neighborhood of 0 with a(e) co, we can only use parameters that render the approximation valid. Thus, the success of our approach relies an appropriate parameter initialization in the first layer of the source network fs- (b) A nonzero intercept (d + 0) in the approximation of do demands for a different initialization scheme to avoid the need for large bias approximations. For simplicity, let us first assume that do fulfills Assumption 2.3 with zero intercept (d = 0).
Theorem 2.5 (LT Existence (Two-for-One)). Assume that é', (0,1), a target network fa(x);
D C Th T with f15(x) di (Ej= We,5 + bes). and two-layer source network f. with architecture [no, T2,1, R1] and activation functions @o in the first and de in the second layer
5

---

are given. Let @u fulfill Assumption
2.3 with a(e") > 0 and d = O, 인r have Lipschitz constant
Tu, and M == max maX
[ Let the parameters of fa be conveniently initialized as
wij by Ul- and wij
(1)
(2) U| U1-1/(Im+ + m_ 1/((m + m- [m]] 6.th) 0, where
-= - {1, al(e")/M with e" = ( (CTmn m- +m- log
"t,1 T( ))) Then, with
min
probability at least 1 - 8', So contains a subnetwork fe C Ss so that each oulput component i is approximated as max (f(i(x) - fe' fe))(x)) S
14g
Ra,1 2 Cng log
min(e' 8' 88/m11))
Proof Oullin. The construction of LT consists of three steps. First, we prune the hidden neurons of Ja to become univariate. Second, we identify neurons in the hidden layer for which we can approximate do for small inputs according to Assumption 2.3 Third, if ns,1 is large enough, we can select subsets 1 and / of the hidden neurons with small inputs so that we can use Cor A.2 on subset sum approximation to approximate the parameters of the target. The resulting subnetwork
of Ss is of the following form fe,((x) = Φx ExEr Wik do (way (2) (1)
(1) (u)))s)) 23) + ExeL, Wik (2)
where 1 = UW1 and EnEr, Wik Wkj can be used to approximate Wr,aj. fe, qualifies as LT if (x) fe,,(=) S é'. A forward series of bounds shows that can achieve this if A; [ur,ta ENEI, wit Φu (wkf2z) 235) I </((T((no + 1)) for each j. This also ap- (1)
plies to the approximation of b,, respectively. We would like approximate do (w0)) x3) (1) us (w 2z ( zy + e", where (1(x) = m4x if 2 0 and (=)x) = m_x otherwise. Note m4 + for all x + 0. By construction, the activation function approximation is valid, as [ æyح I Ma(e")/M = a(e"). Hence, we can split the error into two subset sum approximation problems and the activation function approximation error: (2,),
(2)
that pa (2) (=(=x)
m m_+m- Wi, |m+ + -m-IE wik "kj (1) +M
Iut (x,))
(2)
In= (m4+m- |wr,s - |m++
A S M
m- EKEr, Wikk Wky
(1)
(2) + kEI, wix (do(w))) x.)) u1 (w xy ())wk x))]) where Ij is split into (2),
(1)
indices 1 for which Wij
> 0 and 1j all the ones for which wkj < 0. The first two terms can be
(1)
bounded according to Cor. A.2 with probability - 8" if C'log
(2 1)MT21),53)
random (2) (1)
variables X are available to choose from r,t_ since the random variables X2 |m + + wak Wkj distributed as Xg U[-1, 1] or X UI-1, 1|U[-11011 and thus contain a uniform distribution 1] as shown by [37. We can solve 2(no + 1)n,,1 independent subset sum approx- imation problems with probability - 8' if each problem is solved with 8" 8' (2/(2 1)m,,))
and if we have in total Crg log
random variables available.
(in (C/((MT.))))) /m...))
The full proof is given in the appendix. A key result of our construction is that the activation function approximation error does not affect the width requirement. As long we choose the scaling factor small enough, we can achieve a small enough error. Note that for RELUs, the above theorem reduces to known results [12] since
I, m+ + m_ 1, a xc, and d have the same advantageous property and are now covered in addition. The only difference is that m+ + m_
LRELUS
+ a. Another new insight is that also activation functions with finite approximation support a(c") < co support the existence of lottery tickets with the right parameter initialization with a < 1. Interestingly, they can still achieve the same realistic width requirement.
Even though the theorem does not provide details on the universal constant, the minimum width requirement in this construction would be achieved by a linear activation function Φo(x) = x, which does not require a distinction between positive and negative Wiy has a(e") = co, does not inflict any approximation error, and is homogeneous, which makes it easy to transfer the above results to realistic parameter initialization schemes.
Remember that only Φo the first layer needs to fulfill Ass. 2.3 function. However, it is relatively uncommon in practice combine different activation functions in
de is an arbitrary continuous

---

the same neural network so that @ & Φt. Regardless, RELU neural networks have been observed to learn the identity in the first layers (close to the input) 22 For these reasons it could be beneficial in general to equip at least the first layer with linear activation functions.
Also a 'looks-linear' parameter initialization can be of great benefit, in particular, if the intermediary activation function do has a nonzero intercept d of O, as shown next.
Theorem 2.6 (LT Existence (Two-for-One) with Nonzero Intercept). Thm. 2.5 applies also to activation functions @u that fulfill Assumption 2.3 with d F if the parameters are initialized
according to Assumption 2.2 with " distributed as the weights in Thm. 2.5
Proof Outline. We can closely follow the steps of the previous proof. The major difference that we approximate d0 (x) R uu (ar)x + d so that the activation function approximation produces an (2)
additional eтror term, i.e., EREI, dik In principle, we could have modified the bias subset sum
approximation by approximating bt.; + d E, EKEI, wit instead of b,,5. Yet. Σj Eket, wie could
be large number, with which we would need to multiply our width requirement, if each with is
(2)
initialized as in Thm. 2.5 In contrast, with the looks-linear initialization we can choose (1()) w (2)
(2) so that EvEt, Wik Everţ Wit + Ewer, Wik Ekert Wik -Ekei Wik 0.
(2)
(2)
(2)
As for RELUS 12 we could use these results approximate every layer of a target multi-layer
feed-forward neural network for general activation functions by pruning two layers of a source network with double the depth as the target network, as visualized in Fig. [ (b). As alternative, next we propose to prune a source network that has almost the same depth as the target network.
2.2 One Layer for One
Our second major contribution is show how we can approximate intermediate target layers by pruning single layer of the source network. This is achieved by connecting subset sum approximation blocks directly as visualized in Fig. (c). The main idea to create, instead of single target neuron, copies to support subset sum approximations in the next layer.
In comparison with the two-layer-for-one construction, have to solve higher number of subset sum approximation problems but this number is only higher by a logarithmic factor and can be integrated in the universal constant C. is usually negligible. In total, the lottery ticket might also consist of a higher number of parameters, i.e., link weights, but a smaller number of neurons, which the more critical case reduce computational costs B. The benefits usually outweigh the costs, as we need less random variables to guaranty a successful subset sum approximation and, most importantly, can use almost the full depth of the source network to find sparser representation of the target network. Furthermore, source networks of lower depth are easier to train and thus also more amenable to pruming algorithms that utilize gradient based algorithms.
Interestingly, we can further relax our requirements on the activation functions, as they only influence the error propagation through the network but are not involved anymore in creating random variables for the subset sum approximation problems. Let us start with the approximation of a single layer.
Theorem 2.7. Assume that é', 8' E (0, 1), a target network layer fe(x) : 'D C TR - R
with (T) = de (Ei= W1,5JJ + by,)). and one source network layer fa with architecture [N,,441, 12,442] and the same activation function di are given. Let 6, have Lipschitz constant T, and define M = max 1, maXxED, [r:|]. Let the parameters of fa be initialized according to Assumption 2.1 Then, with probability at least 1 1- 8', fs contains a subnetwork fe C. fa so that copies of each output component are approximated max [fe,(()) Se (2:) S é if
nh. min(c/(MT)) 8' 8'm(me.t+)))
ns,1+1 2 CrA.I log
Proof. For each target input neuron j. we assume that we can create multiple copics (with index set I2) that we can use then as basis for subset sum approximations of target weights wi,if Similarly, for biases we reserve neurons Is in the first layer that are pruned so that we have (c)
((+1)
7

---

1 or another constant. Particularly parameter efficient would be 6b( = d. Thus, our lottery ticket is of the form (x))( - Φi ni, 2j Eketg,Ci,
Wek de(c). The [W1,55 EKET,,CI, wys (1(+2)) S d'/(MT(m. 1)) and
Wek (1+2)
+ ExElnnc (1+2)
subsets Fiy and Tys are chosen so that ((+1) 16 EMErpoc (1+2)
Wirk (e S < + 1), which can be achieved by subset sum
approximation based on the random variables X₁ w (1+2) U[-1, 1]. In total, we have solve maximally pm,,141 ( + 1) of these problems and can thus spend (p/(nee,4 + 1)) on each of them. Note that we only need separate subset sum block for each imput target neuron and not for its copies, as we can reuse each block in the construction of each output.
The advantage the construction above that can skip the approximation of the identity func- tion. The real challenge, however, lies in the derivation of the required multiplicative factor p for approximating a multi--ayer target network.
2.3 Multi-layer Lottery Ticket Existence
Our main result is to derive realistically achievable lower bounds on the width of a source network that has depth L, L, +. To prove the existence of LT's that approximate general multi-layer target networks using the last theorems, we have to overcome two challenges. First, when we consider multiple network layers, we need understand how much error we can afford make in each target parameter approximation for general activation functions beyond RELUS to stay below the global error bound, error can get amplified when signal sent through multiple layers. Second, we need to identify the required layer-wise width scaling factor in Thm. 2.7
Lemma 2.8 (Error propagation). Let two networks fi and fz of depth L have the same architecture and activation functions with Lipschitz constant T. Define Mi == supzeD ||a Then, for any
e > O we have [| f2 loo S if every parameter 02 of f1 and corresponding 02 of fa in layer I
fulfils 101 021 S for
L-1 T1-1+ (1 (1+M Mi-1) (1+ +) II k=l+1
| + +
6l
I
For suitable target networks, this requirement essentially becomes e Ce/(m. This is an advanta- geous estimate in comparison with []. which derives a smaller allowed error 6, xx c/(N, II N/O)) that is anti-prop nntioproportional the total number of nonzero parameters N, and a product over nonzero parameters in the upper layers. Our estimate can be used in two-layers-for-one as well as one-layer- for-one LT constructions. The latter follows as main result.
Theorem 2.9 (LT existence (L + construction)). Assume that e, E (0,1), a target network fe(z) : D C Rnte + R with architecture ñu of depth Lt, N, nonzero parameters, and a source network fa with architecture n. of depth L, L, + 1 are given. Let ór be the activation function of St in the layers 12 2 of Is with Lipschitz constant T, do be the activation function of the first layer of fo fulfilling Assumption 2.3 and M max maXxED.
}. Let the parameters of fe be initialized according to Ass. 2.1 for 1 > 2 and Thm. 2.5 or f.o < 2. Then, with probability at least - 8, fs contains a subnetwork Se C Is so that each ouiput component is approximated as max (xr,((r) - fe,((x)] < if
x
(1
n,,++ 2 Cn. log
mrinfel41:0/pl
for 2 1, where 641 is defined by Lemma 2.8 and p CN. +7 log(1/ min(miny a, ()) for any 7 >> Furthermore, we require n,,1 2 Cn log
min(er441
The full proof is presented in the appendix. While the layer-wise constructions are explained by the proofs of Thms. 2.6 2.5 and 2.7] yet with updated et, the main challenge is to determine the increased number of subset sum problems that have to be solved to derive the scaling factor p. Note that p only enters the logarithm and is negligible. By updating C, we in fact have the same asymptotic dependence nl.41 2 Cr log ( min(e, o)) as in the two-layers-for-one construction.
8

---

LeNet on MNIST As our proofs suggest, pruning involves solving multiple subset sum approxi- mation problems. Each is an NP-hard problem in general, as the size of the power set and thus the number of potential solutions scales exponentially in the base set size m, i.e., as 2 However, as a set size of m = 15 and even smaller is sufficient for our purpose, we could solve each problem 3 Experiments
To demonstrate that our theoretical results make realistic claims, we present three sets of experiments that highlight different advantages of the L 1-construction and the 2L-construction. In all cases, we emulate our constructive existence proofs by pruning source networks to approximate a given target network. All experiments were conducted on a machine with Intel(R) Core(TM) i9- 10850K CPU @ 3.60GHz processor and GPU NVIDIA GeForce RTX 3080 Ti.
Table I: LT pruning results on MNIST. Averages and 0.95 standard confidence intervals are reported for 5 independent source network initializations. Parameters are counted in packs of 1000.
CONSTR.
TARGET
+
2L
% ACC.
# PARAM.
% Acc.
# PARAM.
% Acc.
# PARAM.
RELU
97.99
18.6
97.78
0.05
1106.5 0.9
97.96 0.02
119.2 - 0.04
LRELU
97.88
18.6
97.63
0.08
1102.4
97.84 1: 0.06
119.2 1 0.1
TANH
98.2
18.6
98.07
0.07
660.3 = 0.4
98.14 0.03
67.0 1 0.06
SIGMOID
98.08
18.6
98.08 + 0.02
669.7
98.07 = 0.02
67.4 + 0.05
optimally by exhaustively evaluating all 2d solutions. To reduce the size of the associated LTs, we instead identify the smallest subset consisting of up to 10 variables out of m 20 to achieve an approximation error that does not exceed 0.01.
What should be our target network? As the influential work [ we use Iterative Magnitude Pruning (IMP) on LeNet networks with architecture [784, 300, 100, 10) to find LTs that achieve a good performance on the MNIST classification task 77] Using the Pytorch implementation of the Gihub repository open_ 1th with MIT license, we arrive at target network for each of four considered activation functions after 12 pruning steps: RELU,, LRELU, SIGMOID, and TANH. Their performance and number of nonzero parameters are reported in Table M in the target column alongside our results for the (L+ cooostttuttno and our 2L construction, which achieve a similar performance. Note that, while the L + construction relies in this case higher number of parameters, it uses less neurons and a smaller depth, which are the relevant criteria for fast computations and network training.
ResNet18 on -iay-Ima We have obtained more large-scale target networks by fine-tuning& a R8sNet18 model that was originally trained on ImageNet data and available for download on Pytorch for transfer learning. We replaced the last fulle-co classification layer by fully-connected network with widths [512, 512, 200] and activation function of interest in the first layer and trained the full ResNet model on the iiny-ImageNet training data. Similarly to experiments of [. we estimated the pruning error of LT's for the fully-connected classification network based on statistic of solving 10 different subset sum approximation problems. The subset sum base set size in the lne-layer- for-one construction is m 10, while we used m 15 in the ww--ayeer-frroon construction. Note that this difference is possible because the subset sum base set consisting of uniformly distributed random variables in the one-layer-for-ons construction can be smaller than variables that are products construction.
of uniform random variables as in the tvo-layers-for
Both constructions approximate target parameters up to maximum error = 0.001. The reported performance is evaluated on the Eny-ImageNee test data for model that concatenates the residual target layers and fully-connected L.Ts (see Table 2 In this case, because of the different base set sizes, we sometimes find the I. + 1-construction to more parameter efficient.
Representational Benefits of the I. + 1-construction In the previous experiments, we have constructed one target network and used different source networks to demonstrate the validity of our proofs and constructions. The more realistic set-up is, however, that the source network given

---

Table LT pruning results on tiny-ImageNet. Averages and 0.95 standard confidence intervals are reported for 3 independent source network initializations. Parameters are counted in packs of 10
CONSTR.
TARGET
L+1
2L
% Acc.
# PARAM.
% Acc.
PARAM.
Acc.
PARAM.
RELU
73.08
2.06
73.09 + 0.04
19.14 0.005
73.06
0.05
21.8 = 0.004
LRELU
73.0
2.06
72.96
0.04
1.01
72.92
+ 0.03
21.8 = 0.006
TANH
73.73
2.06
73.75 0.04
11.36
73.72 0.08
10.98 0.01
SIGMOID
72.69
2.1
72.69 0.01
19.14
72.67 + 0.06
21.86 + 0.01
and thus the depth of the LT predetermined as L, or L2/2, respectively. As a consequence, the 2L- and the L + 1-construction would approximate different target network representations. If the target of depth L,2 = L - much sparser than the target network of depth I, = L,/2, our L 1-construction might be more effective than our co-counstucction The general challenge with this argument is that we cannot exclude the case that there might exist a much sparser target network of depth L. L than we thought or could identify.
Keeping this caveat in mind, we have still constructed two types of target networks for a problem for which [ has derived a relatively sparse solution. The circle target of depth L, 25 (for the L+ l-costtruction) consists of 190 nonzero parameters and has a maximum width of 16, while the L. = 13 target network (for the 21-construction) consists of 2133 parameters and has maximum width of 1024. Both target networks are equipped with ReLU activation functions and achieve similar test accuracy: 99.86% is achieved by the L, 13 = Lg/2 target and 99.76% by the
L, = 25 L, - 1 target.
In the following we report the properties of the lottery ticket that we identify by pruning the source network with a subset sum base set size of m 15 in the two layer construction and base set size m 10 in the one layer construction as averages over 3 independent runs with 0.95 standard significance intervals.
2L-construction: Ace: 99.5 + 0.6, number of parameters: 98393 + 288, maximum width: 15375.
L + I-consrruction: Acc: 99.8 + 0.01, number of parameters: 18891 + 133, maximum width: 170.
In this example, the L+ I-construction results in sparser lottery ticket consisting of fewer parameters and considerably smaller maximum width. The reason is that we could leverage almost the full depth of source network obtain a much sparser target network representation for the L 1-construction.
4 Discussion
We have shown that randomly initialized fully-connected feed forward neural networks contain lottery tickets with high probability for a wide class of activation functions by deriving two types of construc- tions: (a) The coosstccnttnottion assumes that the larger random source network has at least double the depth of the target network and is wider only by a logarithmic factor O(n, log(n, min (6, c)) in the approximation еиrоr and the LT existence probability. (b) The (L, + 1) consttruuiio allows for potentially sparser target network representations, as these can utilize almost the full available depth L, L, + of the source network. Remarkable about this result is that asymptotically, we can maintain the logarithmic overparametrization. While this suggests a slightly less advantageous scaling in 5 for the (I, + c)-construction, the constant is smaller for the (L, + 1)-construction and We
most of the time we can choose a similar or smaller source width than in the (2L:)-constructtin have also demonstrated in experiments that the LT for the (L, L. 1)-construction will often consist of fewer parameters than the LT corresponding to the (L, (L./2)- /)n/))))nnrtuuttion but this does not always have to be the case.
We have mainly discussed the scenario, in which the source network has exactly depth L, = L, but not all target network representations become sparser with increasing depth. What if the sparsest target representation has depth L,, + 1 < L,? With the help of Lemma 2.4 we could simply add layers that approximate the identity and thus construct target with depth L,p L. - 1. In future, it could be interesting to leverage excessive depth to distribute subset sum blocks on multiple layers instead, it has been proposed for RELUS 3]
10

---

References
[1] Rebekka Burkholz. Convolutional and residual networks provably contain lottery tickets. In International Conference Machine Learning, volume 162, 2022.
[2] Rebekka Burkholz and Alina Dubatovka. Initialization of ReLUs for dynamical isometry, In Advances in Neural Information Processing Systems, volume 32, 2019.
[3] Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the existence of universal lottery tickets. In International Conference on Learning Representations 2022.
[4] Tianlong Chen, Yu Cheng, Zhe Gan, Jingjing Liu, and Zhangyang Wang. Data-efficient GAN training beyond (just) augmentations: lottery ticket perspective. Advances in Neural Information Processing Systems, 2021.
[5] Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, 2021.
[6] Xiaohan Chen, Yu Cheng, Shuohang Wang, Zhe Gan, Jingjing Liu, and Zhangyang Wang. The elastic lottery ticket hypothesis. In Advances in Neural Information Processing Systems, 2021.
[7] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2916)114 2012.
[8] James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning randomly weighted network. In International Conference Learning Representations, 2021.
[9] Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning prune deep neural networks via layer-wise optimal brain surgeon. In Advances in Neural Information Processing Systems, 2017.
[10] Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, 2020.
[11] Jonas Fischer and Rebekka Burkholz. Plant 'n' seek: Can you find the winning ticket? In International Conference on Learning Representations, 2022.
[12] Jonas Fischer, Advait Gadhikar, and Rebekka Burkholz. Lottery tickets with nonzero biases, 2021.
[13] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
[14] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. International Conference on Machine Learning. 2020.
[15] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? In International Conference on Learning Representattions 2021.
[16] Advait Gadhikar and Rebekka Burkholz. Dynamical isometry for residual networks. In a:X02.2200002411, 2022.
[17] Advait Gadhikar, Sohom Mukherjee, and Rebekka Burkholz. How Erdös and Rényi win the lottery. In 2:X02.2110002412, 2022.
[18] Xavier Glorot and Yoshua Bengio. Understanding the diffieulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics, volume 9, pages 249-256. May 2010.
[19] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems, 2015.
11

---

[20] Babak Hassibi and David G. Stork. Second order derivatives for network pruning: Optimal brain surgeon. In International Conference on Neural Information Processing Systems, 1992.
[21] Kaiming He. Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, In Proceedings of the IEEE international conference computer vision, pages 1026-1034, 2015.
[22] Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, 1990.
[23] Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. Advances in neural information processing systems, pages 598-605 1990.
[24] Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Torr. signal propa- gation perspective for pruning neural networks at initialization. In International Conference on Learning Representations, 2020.
[25] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: single-shot network prun- ing based on connection sensitivity. In International Conference on Learning Representations. 2019.
[26] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. In International Conference Learning Representations, 2017.
[27] Ning Liu, Geng Yuan, Zhengping Che, Xuan Shen, Xiaolong Ma, Qing Jin, Jian Ren, Jian Tang, Sijia Liu, and Yanzhi Wang. Lottery ticket preserves weight correlation: Is it desirable or not? In International Conference on Machine Learning.
(28) Ning Liu, Geng Yuan, Zhengping Che, Xuan Shen, Xiaolong Ma, Qing Jin, Jian Ren, Jian Tang, Sijia Liu, and Yanzhi Wang. Lottery ticket preserves weight correlation: desirable or not? In International Conference Machine Learning, 2021.
[29] Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. In Advances in Neural Information Processing Systems, 2021.
[30] George S. Lueker. Exponentially small bounds on the expected optimum of the partition and subset sum problems. Random Structures & Algorithms, 12(1):51-62, 1998.
[31] Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Minghai Qin, Sijia Liu, Zhangyang Wang, and Yanzhi Wang. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? In Advances in Neural Information Processing Systems, 2021.
[32] Eran Malach, Gilad Yehudai, Shai Shalev-Schwart and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning. 2020.
[33] Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? In AAAI Conference on Artificial Intelligence, page
2017.
[34] Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. In International Conference Learning Representations, 2017.
[35] Michael C Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from a network via relevance assessment. In Advances in Neural Information Processing Systems, 1 1989.
[36] Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is you need. Advances in Neural Information Processing Systems, 33, 2020.
12

---

[37] Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic over parapaaamtteiinnooonn is sufficient. In Advances in Neural Information Processing Systems, volume 33, pages 2599-26166 2020.
[38] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in a randomly weighted neural network? In Computer Vision and Pattem Recognition, pages 11893- 11902, 2020.
[39] Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations, 2020.
[40] Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsifi- cation. In Advances in Neural Information Processing Systems, 2020.
[41] Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsifi- cation. In Advances in Neural Information Processing Systems, 2020.
[42] Wenling Shang, Kihyuk Sohn, Diogo Almeida, and Honglak Lee. Understanding and im- proving convolutional neural networks via concatenated rectified linear units. In International Conference International Conference on Machine Learning, 2016.
[43] Suraj Srinivas and R. Venkatesh Babu. Generalized dropout. CoRR, abs/1611 2016
[44] Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. In Advances in Neural Information Processing Systems, 2020.
[45] Hidenori Tanaka, Daniel Kunin, Daniel I.. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Advances in Neural Information Processing Systems, 2020.
[46] Stijn Verdenius, Maarten Stol, and Patrick Forré. Pruning via iterative ranking of sensitivity statistics, 2020.
[47] Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
[48] Andreas Weigend, David Rumelhart, and Bernardo Huberman. Generalization by weight- elimination with application to forecasting. In Advances in Neural Information Processing Systems, 1991.
[49] Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference On Learning Theory, pages 639-649, 2018
[50] Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang. Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Representations, 2020.
[51] Shuai Zhang, Meng Wang. Sijia Liu, Pin- Yu Chen, and Jinjun Xiong. Why lottery ticket wins? theoretical perspective of sample complexity on sparse neural networks. In Advances in Neural Information Processing Systems, 2021.
[52] Zeru Zhang, Jiayin Jin, Zijie Zhang, Yang Zhou, Xin Zhao, Jiaxiang Ren, Ji Liu, Lingfei Wu, Ruoming Jin, and Dejing Dou. Validating the lottery ticket hypothesis with inertial manifold theory. In Advances in Neural Information Processing Systems, 2021.
[53] Zhenyu Zhang, Xuxi Chen, Tianlong Chen, and Zhangyang Wang. Efficient lottery ticket finding: Less data is more. In International Conference on Machine Learning. 2021.
[54] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In Advances in Neural Information Processing Systems, pages 3597-3607, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss detail for which
activation functions our theory holds and discuss advantages and disadvantages of the derived LT constructions.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We do not see any immediate negative societal impact that specific to our contributions.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] See proof outlines in the main paper and full proofs the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplement. (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See section on experiments.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We repeated each experiment with 5 independent random seeds and report standard confidence intervals as error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section 3 experiments. assets... (a) If your work uses existing assets, did you cite the creators? [Yes] We used the open_lth package.
4. If you using existing assets (e.g., code, data, models) or curating/releasing
(b) Did you mention the license of the assets? [Yes].
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
We submitted code in the supplement and will also make it available Github upon publication of the paper.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] We only used MNIST.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "PsFzzxygn28", "reviewer": "Reviewer_NsjM", "summary": "This paper generalizes the lottery ticket hypothesis by (1) extending results beyond ReLU activation functions to a broad class and (2) improving the 2L depth to depth L+1.", "questions": "Is there a reason why practitioners should care about the depth 2L to L+1 improvement, or is the interest merely theoretical?  If it is of practical significance, please provide an experiment demonstrating so.", "limitations": "The main limitation is in the experiments, which are at best just a simple sanity check of the theory with a small network and dataset.  Since the paper focuses on flexibility (many activation functions) and efficiency (reducing depth from 2L to L+1) it would be much more impressive to see the technique applied in a more realistic setting with a larger network and dataset.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: The originality of the paper is twofold: a different network construction allows for depth L+1 instead of 2L, and flexibility in the choice of activation function means this technique can potentially be applied to many more types of architectures.\n\n- Quality: This is a good paper.  There is a clear discussion of the related work and how this paper relates to past papers, and this paper makes a concrete, incremental improvement over the past works.\n\n- Clarity: The writing is clear and well-organized.  No complaints here.\n\n- Significance: The main significance at this point are the theoretical contributions.  I believe there is a potential to make a stronger statement about the practical significance with additional experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EQlkxxMbv_F", "reviewer": "Reviewer_MTH7", "summary": "This paper studies the Strong Lottery Ticket Hypothesis (SLTH) for non-ReLU activation functions, just as its title implies. Previous theoretical works have advanced the SLTH in many aspects. One missing part is that their theories focus on the ReLU case, while this paper extends them to other common activation functions and maintains the L+1 depth and logarithmic width requirements. They mainly focus on FC networks in this work. Empirical study on MNIST is conducted to validate their theory.\n", "questions": "* Please respond to my concerns above\n* Side question: SLTH is interesting itself. However, as the experiments in this paper imply, we need much more parameters to realize it. I am wondering, what possible *practical* meaning it could imply?\n", "limitations": "Yes, they address the limitations and potential negative societal impact of their work. \n", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Pros** \n1. They extend SLTH to non-ReLU activation functions, which is a credible theoretical contribution towards LTH, network pruning, or neural networks themselves.\n2. Meanwhile, the L+1 depth and logarithmic width requirements are maintained.\n3. The paper is well-written and well presented.\n\n**Cons**\nI like this paper on its own. My major concern is that, given the existence of [1] (L71: “While this approach has been transferred to convolutional and residual architectures [1]), what is *truly new* from this work?\n\nThe major construction scheme in this paper (Sec. 2) has a non-trivial overlap with [1] (Sec. 2 and Sec.3). The major novelty of the non-ReLU activation functions for SLTH also has been discussed in [1].\n\nFor the rating - I think this is a good paper in general. But unfortunately, some major content has appeared in previous works. My final rating hinges on how the authors respond to my concerns.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DrkyRytKYHX", "reviewer": "Reviewer_Puqv", "summary": "The authors attempt to extend previous work proving the existence of \"Strong Lottery Tickets\", strong LTs, i.e. subnetworks of a randomly-initialized neural network that show moderate generalization without training. The previous work had proven the existence of strong LTs of depth L within randomly initialized source neural networks of depth 2L, with the restriction of using ReLU activation functions. The authors claim to show a proof of such an existence within a source neural network of depth L+1, and assuming a broader class of activation functions. The authors attempt to validate their claim by finding weak LTs (i.e. LTs from a trained/pruned neural network) in source models of depth 2L and L+1, and comparing the generalization of the weak LTs.", "questions": "* 26-34: unclear, some sentences do not make sense at all -- needs a rewrite\n* 38-40: how do these function approximation results relate to sparse nets?\n* define strong and weak/strong Lottery Ticket Hypothesis, and weak/strong Lottery Tickets in the beginning (currently there are some definitions in the second paragraph of related work, but these need clarification also)\n* it should be emphasized that the target network is trained (at least this is what I have inferred, but I am still unsure!)\nRelated Literature: all of this should be put in a relation to the topic of your work; the second paragraph explains the topic of your work and should rather be in the intro\n* 67-69: “Their existence has been proven [...] by providing lower bounds on the width of the large, randomly initialized source network” -- bounding the width is not an existence proof. proven theoretically or shown empirically? if theoretically, what method was used?\n* 80: \"we usually care about cases where \\epsilon < \\delta\" \\epsilon is approximation error, and \\delta is 1-probability, how/why would we compare these? It's apples v.s. oranges from what I can see.\n* 87-88: Why is a bound on the weight magnitude not a loss of generality?\n* 95-98: “we assume a convenient parameter initialization that we have to choose with respect to the activation function if we approximate a target layer with two source network layers”\n    1) how is the initialization related to the activation function?\n    2) why is a target layer approximated with two source-net layers? is this an assumption, or is this enforced by construction in your approach?\n    3) why is this param init “convenient”?\n* 104-106: the normal distribution (aka Gaussian distribution) is not the same as the uniform distribution; what exactly do you mean here?\n* Figure 1: “Dashed links only exist if source network biases in layers l > 1 are initialized to zero.” -- isn’t it the converse, i.e., only when the biases are non-zero?\nAssumption 2.2: why? what is the purpose of this type of block-diagonal symmetric structure that you impose on the source-net weight matrices?\n* 136-150: this belongs in the related work section; in the following lines are several more repeated mentions of related work\n* 153: explanation unclear. what is the middle layer?\n* Direct citations should be made in the format Author et al. [1], (i.e. \\citet in natbib not \\citep). This formatting should be fixed throughout your work.", "limitations": "No such limitations/negative impacts are discussed by the authors. It's not immediately clear to the reviewer any potential impacts since this work is quite far from application, although pruning in general has been shown to have consequences for bias/robustness of trained models.", "rating": 2, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The authors attempt to reduce the depth provably required to find \"Strong Lottery Tickets\" i.e., subnetworks at initialization with good generalization.\n* Any such guarantee could make a big difference in the feasibility of finding strong Lottery Tickets emperically.\n\nWeaknesses\n* The premise of the paper is entirely based on the (unstated) assumption that Lottery Tickets can approximate an arbitrary subnetwork's weights and structure (i.e. target network $f_t$, from source network $f_s$. This assumption is unproven at best, and in fact all evidence empirically points to this assumption likely being false. As has been shown empirically in multiple works, LTs are extremely restricted in the solutions they can find. In \"Linear Mode Connectivity and the Lottery Ticket Hypothesis\" by Frankle et al. show that all Lottery Ticket solutions are within the same basin, effectively learning very similar solutions. In \"Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win\" by Evci et al, it is further shown that this solution basin is the same as the pruning solution, and a function similarity analysis shows they learn effectively the same function. Empirically we only know how to find one specific subnetwork with Lottery Tickets. Furthermore, we are not given any relationship between $f_t$ and $f_s$ (or any restrictions on $f_t$) to even understand how/if $f_s$ is related to the source model or the pruning solution.\n* Given the small-scale model and dataset, the empirical results (on weak LTs, not strong LTs!) shown do not provide much support for the theoretical claim, notably the ReLU/LReLU results for depth L+1 are 0.2 percentage points lower than 2L and the target models. This might not seem significant, but when one considers how easy the problem is to solve, and how close the 2L solutions are, it is not as convincing. Please note these results are also Weak LTs, not strong LTs as the proof is intended to show the existence of. \n* There are many other assumptions made critical to the proposed proof that are unjustified, not obvious, and in some cases obviously not maintained in real-world neural networks. For example, restricting the weight magnitudes of the model.\n* Paper is very unclear in other sections, with math not well explained in bits, and language of some sections incomprehensible (more details below in Questions).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept