On the Existence of Universal Lottery Tickets
Authors: Rebekka Burkholz
Nilanjana Laha
Rajarshi Mukherjee
Alkis Gotovos
Venue: ICLR 2022 Poster (2022)
Keywords: theory
deep learning
lottery tickets
universality

Abstract: The lottery ticket hypothesis conjectures the existence of sparse subnetworks of large randomly initialized deep neural networks that can be successfully trained in isolation. Recent work has experimentally observed that some of these tickets can be practically reused across a variety of tasks, hinting at some form of universality. We formalize this concept and theoretically prove that not only do such universal tickets exist but they also do not require further training. Our proofs introduce a couple of technical innovations related to pruning for strong lottery tickets, including extensions of subset sum results and a strategy to leverage higher amounts of depth. Our explicit sparse constructions of universal function families might be of independent interest, as they highlight representational benefits induced by univariate convolutional architectures. 

Published as a conference paper at ICLR 2022
ON THE EXISTENCE OF UNIVERSAL LOTTERY TICKETS
Rebekka Burkholz CISPA Helmholtz Center for Information Security burkhol zêci spa. de
Nilanjana LaHa, Rajarshi Mukherjee Harvard T.H. Chan School of Public Health rmukher jehssh. waw.rddded.....
Alkis Gotoves MIT CSAIL a kisisemitt. t.
ABSTRACT
The lottery ticket hypothesis conjectures the existence of sparse subnetworks of large randomly initialized deep neural networks that can be successfully trained in isolation. Recent work has experimentally observed that some of these tickets be practically reused across variety of tasks, hinting at some form of universality. We formalize this concept and theoretically prove that not only do such universal tickets exist but they also do not require further training. Our proofs introduce couple of technical innovations related to pruning for strong lottery tickets, in- cluding extensions of subset sum results and a strategy leverage higher amounts depth. Our explicit sparse constructions universal function families might be of independent interest, as they highlight representational benefits induced by uni- variate convolutional architectures.
INTRODUCTION
Deep learning has achieved major breakthroughs in variety of tasks (LeCun al. 1990 Schmid- huber 2015). yet, it comes at considerable computational cost (Sharir et al.) 2020). which is exaggerated by the recent trend towards ever wider and deeper neural network architectures. Reduc- ing the size of the networks before training could therefore significantly broaden the applicability of deep learning, lower its environmental impact, and increase access (Dhar) 2020). However, such sparse representations are often difficult to learn, as they may not enjoy the benefits associated with over over-parameen aver-parameterizztion (Belkin et al. 2019).
Frankle & Carbin (219)) provided a proof of concept that sparse neural network architectures are well trainable if initialized appropriately. Their lottery ticket hypothesis states that a randomly- initialized network contains small subnetwork that can compete with the performance of the origi- nal network when trained in isolation. Further, [Ramanjjan al. (2020) conjectured the existence of strong lottery tickets, which do not need any further training and achieve competitive performance at their initial parameters. These tickets could thus be obtained by pruning a large randomly initial- ized deep neural network. Unfortunately, existing pruning algorithms that search for (strong) lottery tickets have high computational demands, which are often comparable to or higher than training the original large network. However, Morcos al. (2019) posited the existence of so-called universal lottery tickets that, once identified, can be effectively reused across a variety of settings.
Contributions.
In this paper, we formalize the notion of universality, and prove a strong version of the original universal lottery ticket conjecture. Namely, we show that a sufficiently over- parameterized, randomly initialized neural network contains subnetwork that qualifies as universal lottery ticket without further training of its parameters. Furthermore, it is adapted to a new task only by linear transformation its output. This view can explain some empirical observations regarding the required size of universal lottery tickets.
Our proof relies on the explicit construction of basis functions, for which we find sparse neural network representations that benefit from parameter sharing, it is realized by convolutional neural networks. The fact that these representations are sparse and universal is the most remarkable insight.

---

Published as a conference paper at ICLR 2022
To show that they also be obtained by pruning larger randomly initialized neural network, we extend existing subset sum results [Lucker] 1998) and develop a proof strat- egy, which might be of independent interest, as it improves current bounds on pruning for general architectures by making the bounds depth dependent. Accordingly, the width of the large random network can scale as no 2 On, Top log (n, To/ (o/(T<))) to achieve maximum eтrоr e, where Le denotes the depth and ny the width of the target network, and Lo the depth of the large network.
In support of existence proofs, we adapt standard parameter initialization techniques to a specific non-zero bias initialization and show in experiments that pruning is feasible in the proposed setting under realistic conditions and for different tasks.
Related work. The lottery ticket hypothesis (Frankle & Carbin 2019) and its strong version (Ra- manujan et al. (0200 have inspired the proposal of a number of pruning algorithms that either prune before (Wang et al. 2020 Lee al. 2019 Tanaka et al.) 2020) during and after training (Frankle & Carbin 2019 Savarese et al.) 2020p. Usually, they try to find lottery tickets in the weak sense, with the exception of the adge-popup algorithm (Ramanujan et al. 2020) that identifies strong lot- tery tickets, albeit at less extreme sparsity. In general, network compression is a problem that has been studied for a long time and for good reasons, see, e.g.. [in e.g.,Linn al. (2000) for recent literature discussion. Here we focus specifically on lottery tickets, whose existence has been proven in the strong sense, thus, they can be derived from sufficiently large, randomly initialized deep neural net- works by pruning alone. To obtain these results, recent work has also provided lower bounds for the required width of the large randomly initialized neural network (Malach et al.) 2020) Pensia et al. 2020 Orseau et al. 2020; Fischer & Burkholz, [021] 2022). In addition, it was shown that multi- ple candidate tickets exist that are also robust to parameter quantization (Diffenderter & Kailkhura 2021]. The significant computational cost associated with finding good lottery tickets has motivated the quest for universal tickets that can be transferred to different tasks (Morcos et al.) 2019 Chen
al. 2020). We prove here their existence.
1.1 NOTATION
For any d-dimensional input x = (d1..... T.)T" let [ax) be a fully connected deep neural network
with architecture ń [mo. R1; m... i.e., depth T. and widths ny for layers = 0, ..., I,, with ReLU
activation function (xx)= == max(x, 0). An input vector (0) is mapped to neurons x as:
(2)
x (1) di 11 h0 ( of (1-1) + 60, w E R ( E R"
(1)
where h/ (1) is called the pre-activation of neuron i, ( the weight matrix, and (() the bias vector of layer I. We also write 0 for the collection of all parameters O = ((W(),))) and indicate a dependence of f on the parameters by fx((0).
We also use 1-dimensional convolutional layers, for which the width ny refers to the number of channels in architecture ň. For simplicity, we only consider 1-dimensional kernels with stride 1. Larger kernels could simply be pruned to that size and higher strides could be supported as they are defined so that filters overlap. The purpose of such convolutional layers is to represent a univariate function, which is applied to each input component.
Typically, we distinguish three different networks: 1) a large (usually untrained) deep neural network fo. which we also call the mother network, 2) smaller target network f. and 3) a close approxi- mation, our lottery ticket (LT) fa, which will correspond to subnetwork of fo- is obtained by pruning fo. as indicated by a binary mask B (bx) (0.13 that specifies for each parameter 0, = by0, whether it is set to zero (b, = 0) or inherits the parameter of fo by 0, = 0c,0 (for 6, = 1).
We usually provide approximation results with respect to the 11-norm |æ||| E. [x; but they hold for any p-norm with p 2 1. C' generally stands for a universal constant that can change its value from equation to equation. Its precise value can be determined based the proofs. Furthermore, we make use of the notation [r]] := (O..., n1 } for n E N, and [n]* for a d-dimensional multi-index with range in [n).
2

---

Published as a conference paper at ICLR 2022
2 UNIVERSAL LOTTERY TICKETS
Before we can prove the existence of strong universal LT's, we have to formalize our notion of what makes strong LT universal. First of all, a universal LT cannot exist in the same way as strong LT, which is hidden in a randomly initialized deep neural network and is identified by pruning, i.e., setting a large amount of its parameters to zero while the rest keep their initial value. For a ticket to be universal and thus applicable to a variety of tasks, some of its parameters, if not all, need to be trained. So which parameters should that be? In deep transfer learning, it is common practice to only train the top layers (close to the output) of large deep neural network. The bottom layers (close to the input) are reused and copied from a network that has been already trained successfully to perform a related task. This approach saves significant computational resources and often leads to improved training results. It is therefore reasonable to transfer it to LTs (Morcos et al. 2019))
Independently from LTs, we discuss conditions when this is a promising approach, i.e., when the bottom layers of the deep neural network represent multivariate (basis) functions, whose linear com- bination can represent a large class of multivariate functions. The independence of the functions is not required and could be replaced by dictionaries, but the independence aids the compression of the bottom layers and thus our objective find sparse LTs. This view also provides an explanation of the empirically observed phenomenon that universal tickets achieve good performance across a number of tasks only moderate sparsity levels and become more universal when trained on larger datasets (Morcos et al.) 2019); Chen et al., [2020). Including higher number of basis functions naturally reduces the sparsity of a LT but also makes it adaptable to richer function families.
2.1 How UNIVERSAL CAN A LOTTERY TICKET BE?
A trivial universal ticket. A trivial solution of our problem would be to encode the identity function by the first layers, which would only require 2d or d neurons per layer or even 1-2 neurons per convolutional layer. This would be an extremely sparse ticket, yet, pointless as the ticket does not reduce the hardness of our learning task. In contrast, it cannot leverage the full depth of the neural network and needs to rely on shallow function representations. How could we improve the learning task? The next idea that comes our mind to reduce the complexity of the function that has to be learned by the upper layers. For instance, we could restrict it to learn univariate functions. To explore this option, our best chance of success might be to utilize the following theorem.
The Kolmogorov-Arnold representation theorem states that every multivariate function can be written as the composition and linear combination of univariate functions. In particular, recent results based on Cantor sets C promise potential for efficient representations. Thm. 2 in (Schmidt- Hieber 2021 shows the existence of only two univariate functions g C - RR. and 1o 10.1
so that any continuous function
[0, 1] + R can be written as f(x) g Furthermore, only y depends on the function S. while vb is shared by all functions f and is hence universal. Could Σ 3' be universal LT? Unfortunately, it seems to be numerically infeasible to compute for higher input dimensions d > 10. In addition, the resulting representation of f seems to be sensitive to approximation errors. On top of this, the outer function g relatively rough even though it inherits some smoothness properties of the function f (cf. [Schmidt- 202T) and difficult to learn. Thus, even restricting ourselves to learning an univariate function g in the last layers does not adequately simplify our learning problem. To make meaningful progress in deriving a notion of universal I.T',, we therefore need stronger simplification.
3 (w.)))
2.2 DEFINING UNIVERSALITY
To ensure that the knowledge of a LT substantially simplifies our learning task, we only allow the training of the last layer. A consequence of this requirement is that we have to limit the family of functions that we are able to learn, which means we have to make some concessions with regard to universality. We thus define strongly universal LT always with respect to family of functions.
We focus in the following on regression and assume that the last layer of a neural network has linear activation functions, which reduces learning task to linear regression after have established the LT. Classification problems could be treated in a similar way. Replacing the activation functions in the last layer by softmax activation functions would lead to the standard setting. In this case,
3

---

Published as a conference paper at ICLR 2022
would have to perform a multinomial logistic regression instead of linear regression to train the last layer. We omit this case here to improve the clarity of our derivations.
Definition (Strong Universality). Let F be a family of functions defined on S C. IRd with F 3 g:
S - R., A function b: I - R is called strongly universal with respect to F up to error e > 0,
for every f E there exists a matrix W Rnnk and a vector E B so that
sup +c f(x)ll Sc #ES
(2)
Note that we have defined the universality property for any function, including neural network. It also applies to general transfer learning problems, in which we train only the last layer. To qualify as (strong) LT, we have to obtain b by pruning larger neural network.
Definition 2 (Lottery ticket). A neural network f IR > S - R² is called lottery ticket (LT) with respect to fo Rd 5 S - IR with parameters G,, if there exists a binary mask B E [[001] 0ol so that (a B0o) (ax) for all x S. We also write fo-
3 EXISTENCE OF UNIVERSAL LOTTERY TICKETS
Our Def. 1 of strong universality assumes that our target ticket b has finite amount of k features, which is reasonable practice but limits the complexity of the induced function family F. However, universal function approximation regarding general continuous functions on [0, 1j can be achieved
by neural networks only if they have arbitrary width (Pinkus 1999 Cybenko 1989 Kurt Hornik,
1991] arbitrary depth (Telgarsky 2016 Yarotsky| [2017] Schmidt-Hieber 2020). Feed forward networks of higher depth are usually more expressive (Yarotsky) (2018) and thus require less pa- rameters than width constrained networks to approximate continuous function with modulus of continuity wy up to maximal error e. |Yarotsky| (2018) has shown that the minimum number of required parameters is of order (wwy (O(E 4)2) but has to assume that the depth of the network is almost linear in this number of parameters. Shallow networks in contrast need (Ow)(O(E-)) parameters. Note that the input dimension d can be quite large in machine learning applications like image classification and the number of parameters depends on the Lipschitz constant of a func- tion via wiy. which can be huge in general. In consequence, we need to narrow our focus regarding which function families we can hope to approximate with finite neural network architectures that have sparse representations and limit ourselves to the explicit construction of basis functions of a family that has the universal function approximation property.
We follow a similar strategy as most universal approximation results by explicitly constructing poly- nomials and Fourier basis functions. However, propose sparser, non-standard construction that, in contrast to the literature on feed forward neural networks, leverages convolutional layers to share parameters. Another advantage of construction is that it is composed of linear multivariate and univariate functions, for which we can improve recent results on lottery ticket pruning. The exis- tence of such sparse representations is remarkable because, in consequence, most functions that occur in practice can be approximated by sparse neural network architectures and that these architectures are often universally transferable other tasks.
would expect that
Polynomials Sufficiently smooth functions, which often occur in practice, can be well approxi- mated by a few monomials of low degree. At least locally this is possible, for instance, by Taylor approximation. How can we approximate these monomials with a neural networks? In principle, we could improve on the parameter sparse construction by Yarotsky (2017); (Sch//dt- based tooth functions by using convolutional layers that approximate univariate monomials in each component separately followed by feed forward fully-connected layers that multiply these pair- wise. This, however, would require unrealistically large depth L O(log(e/ k) log(d) (d) and also considerable width of at least n = (kkd) in many layers. Alternatively, we propose a constant depth solution as visualized in Fig. (a). It has an dependent width that is maximally n O(d in just one layer and = O(v /kd/e) in another. It leverages the following observation. A mul- tivariate monomial b(x) = II 1 0.5" (1 + xz)" which is restricted to the domain [o, 1] can also be written b(x) exp ( r log(1 + x,) log(2) ( rs). r.). It is therefore composition and linear combination of univariate functions b(x)= = 9 (E,r,h(a r,h((,)) where g(z) = exp(x) and hxx) log(1 + x) log(2) as in Kolmogonov-Arnole form. Most importantly, every monomial
(2020)
4

---

Published as a conference paper at ICLR 2022
(a)
f(x)
(b)
f(x)
Input
Whix)
Wb/xi
(x]
by(N)
Input
Ourput
00 08
0
COIN
universal
Output
lottery
Ah(x) + ee
(d)
Input
ticket
COIY
Oecoec
A(mag)
1/1
Uk
2d Ax
Output
Figure 1: Left: Visualization of the proposed architecture for approximating function families. Potentially fully connected networks are colored blue, while green parts can be encoded as con- volutional layers by applying the same function all components. The last orange linear layer can be trained, while all other parameters are frozen to their initialization. (a) Polynomials: h(x)) log((1 + 2)) g exp(y). (b) Fourier series: g(z) = sin(2xr). Right: Visual- ization of the lottery ticket construction for multivariate linear functions. (c) Visualization of an exemplary linear layer. (d) Approximation of the linear layer (a) by subset sum block. Blue nodes with label + represent neurons in the intermediary layer that are pruned to neurons of the form ((wx1/2) with > 0, while green nodes correspond neurons with w < and orange nodes with label to bias neurons of the form @(b). (e) The subset sum block (d) distributed across three layers. Two paths of bounded weight are highlighted in orange.
has the same structure. We can therefore construct a family of monomials efficiently by approxi- mating each univariate function with a convolutional neural network and the linear combinations of the functions potentially fully connected layers. Fig. [ visualizes the architecture and general construction idea. It applies to any composition of functions in form of the Kolmogorov-Amon resentation theorem, which in theory exists for every continuous multivariate function. This makes our construction more general than it may seem at first. In practice, however, the univariate func- tions still need to be amenable to efficient approximation by deep neural networks, which is the for polynomials as we show the next sections.
rep-
Fourier series Fourier analysis and discrete time Fourier transformations seek representations with respect to a Fourier basis f(x) = + Ene(Nj On (ir( n42; + cx)). Fig. (b)
shows how to construct the functions (2n (2 n42;; + cx)) by (affine) linear combinations Ei 0y2; + 6, in the first layers close the input followed by convolutional layers computing the univariate sin, which has quite sparse representations if enough depth is available to exploit its symmetries. Again we use a composition of linear transformations and univariate functions, which share parameters by convolutional layers.
Even though the function families above can be represented efficiently as LTs, we should mention that big advantage of neural networks is that the actual function family be learned. This could also lead to a combination of different families, when this improves the ability of the lottery ticket solve specific tasks efficiently. Accordingly, adding dependent functions to the outputs might also provide advantages. Our universal lottery ticket constructions allow for this as well. We simply focus our discussion on families of independent functions, they usually induce higher sparsity.
3.1 EXISTENCE OF LOTTERY TICKETS LEVERAGING DEPTH
The targets that we propose as strongly universal functions are composed of linear and univariate neural networks. Some of our improvements with respect to the literature on LT existence leverage this fact. While Malach et al. (2020); Pensia et al. (2020); Orseau et al. (020)); Fischer & Burkholz the required width of the mother network fo so that subnetwork
(202)) provide lower bound could approximate our target neural network with depth L, fo would need to have exactly twice the depth T.p 2h,, which would limit universality statement specific architecture. To address
5

---

Published as a conference paper at ICLR 2022
this issue, allow for more flexible mother networks and utilize additional available depth. As Pensia et al. (2020), we approximate each target parameter by a subset sum block, but distribute this block across multiple network layers. This makes the original bound no O log (N/e)) on the width of the mother network depth dependent.
This approach requires, among others, two additional innovations of practical consequence. The first one is our parameter initialization proposal. Most previous work neglects the biases and as- sumes that they are zero. Only FFischer & Burkholz (202T) can handle architectures with non-zero biases, which we need to represent our univariate functions of interest. They propose an initializa- tion scheme that extends standard approaches like He (He et al., 2015) or Glorot (Glorot & Bengio, 2010) initialization to non-zero biases and supports the existence of LTs while keeping the large mother network fo trainable. We modify to enable our second innovation, i.e., paths through the network that connect network subset sum blocks in different layers to the output.
Definition (Parameter initialization). We assume that the purameters of a deep neural network are (1) independently distributed as Wij ~ U (w-ow,, or wij ~ (0, Tw.i) for some ow, > 0 and b(0) U([ II ow,k/ /2. IT. 22) or b ~N -N(0. Twmm/2)
respectively.
Also dependencies between the weights as in (Burkholz & Dubatovka 2019 Balduzzi et al. 2017) supported by our proofs. The above initialization results in rescaling of the output by X I ow. in comparison with an initialization of the weights by w U ([- or w N (0,4) and biases by b ~ U ([) or ~ N (0, 1). As pruning deletes high percentage of parameters, we can expect that the output of the resulting network also scaled roughly by this scaling factor À (see Thm. 2 However, the last linear layer that we concatenate to f and assume to be trained can compensate for this. This rescaling means effectively that we can prune weight parameters from the interval [-2, 2] in contrast to [-1, 1] in (Fischer & Burkholz 2021 2022). We can therefore find weight parameters W; that are bigger or smaller than 1 with high enough probability so that we can prune for paths of bounded weight < II w, S C' through the network, as stated next.
Lemma 1. Define a 3/4 and let wy U1- 2] denote i independently and identically (iid) uniformly distributed random variables with j E [k.. Then wy is contained an interval
Wj
1/
II w
1/
w
with probability at least a = 1/16. If this is fulfilled for each wj. then
II w/ S 1/a.
The same holds true if each w, NO, 4) is iid normally distributed instead.
This defines the setting of our existence proofs as formalized in the next theorem.
Theorem 2 (LT existence). Assume that e, 5 10, a target network f: S RA - R with depth L, and architecture ñgg and mother network fo with depth Lo 2 2 and architecture nr are given. Let So be initialized according
Def. 3 Then, with probability
least 8, So
contains sparse approximation Sc C fo so that each output component is approximated as
max ff(()) Xfex(z)) c with X -[[== if g( each 1 << < Lo 1.
The required width g(n.) needs to be specified to obtain complete results. We start with the construc- tion of a single layer Φ (War + b). which we can also use to represent a linear layer by constructing its positive ø (War x: + b) and negative part & (-Wa: - b) separately. Note that in polynomial architecture, all components of We + are negative.
Theorem 3 (Multivariate LT's (single layer)). Assume the same set-up as Thm. 2 and a larget function f(x)= = @ (Wa x + b) with M := [maxs,, maxxx,maa([luus max([wx,), [b]]] N non-zero parameters, and Q (supres [x]]] + 1). lottery ticket f. exists if
.d
14,0 2 Lo -
log (M/ min (6/(2(m++ d) - 1) + +N+++++ + +1),e/11)

---

Published as a conference paper at ICLR 2022
for each < Lo - whenever Lo > and R1,0 2 CMdlog +1),) when Lo = 2.
Proof idea. The main idea to utilize subset sum approximations for network pruning has been intro- duced by Pensia et al. (2020). Each target layer d(h) o (W> + b) is represented by two layers in the pruned network J. as follows. Using the property of ReLUs that x = 6(x) - o( ((=x), we can write each pre-activation component as hú دド= Wijo(Hy) wij((=x)) sign(b; ) (bbi))- (1) This suggests that intermediate neurons should be pruned into an univariate form (buit x.)) or
)(6(") if by O. Each actual parameter Wiy or b; is. however, approximated by solving subset sum approximation problem involving several intermediate neurons / Fij of the same type so that wij R Eier, wa wig ( Fig. (d) visualizes the approach. Node colors distinguish different neuron
types o(wl) (2) 2,) or bias type ((b(") for bj >> O within a subset sum block.
We split such a block into similarly sized parts and assign one to each available layer in the mother network as shown in Fig.[ (e). The challenge in this construction is collect the different results that are computed at different layers and to send them through the full network along a path. The product of weights p == - Wy along this path is multiplied with the output. Since we can ensure that this factor bounded reasonably by Lemmal []] we can compensate for by solving subset sum problem for Wsy/ ha Wi instead of Way without increasing the associated approximation error. Furthermore, we only need prune C (og((1"") neurons in each layer find such a path. A rigorous proof is presented in Appendix B.1
As every target neural network is composed of Le layers of this form, we have derived a bound ni > On, Lo log (nt La/ [L)e))))) that scales LoLo log( Ln) and highlights the benefits of additional depth in general LT pruning, which might be of independent interest. Yet, the depth of the mother network needs to be considerably larger than the one of the target. For univariate networks, we can again improve on this result in the following way. As explained in the appendix, every univariate neural network can be written as
N-1
fx( = Σ a, - -si) aN
(3)
1=
with respect to 2N + parameters a; and 8; for 0 Siis N - 1, where the width N determines its potential approximation accuracy of continuous univariate function f and enters our bound if want to find a corresponding LT by pruning.
Theorem 4 (Univariate LT). Assume the same set-up as in Thm. 2 and that an univariate target network f S C I + IR in form of Eq. (3) is given. Define M := (1 max (max; (ai), max, (s,[)) and Q = max |z] fo contains a LT Je C fo
n1,0 2 C m mmx(MM, N
M
log
(4)
Lo 2
min (8/ [o +)
1)),e M))J
for Lo 2 3. We require 11,0
C. MQ log
(N for Lo 2. 2.
M
Next, we can utilize our improved LT pruning results to prove the existence of universal LTs.
3.2 EXISTENCE OF POLYNOMIAL LOTTERY TICKETS
In the following, we discuss the existence of polynomial LTs in more detail. Corresponding results for Fourier basis functions are presented in the appendix. Our objective is define a parameter sparse approximation of k multivariate monomials b(x) = II 0.5* (1 + +z)"* as our target neural network (see Fig. (a)) and then prove that it be recovered by pruning larger, but ideally not much larger, randomly initialized mother network. Thus, in contrast to previous results on LT existence, we have take not only the pruning error but also the approximation error into account.
A multivariate linear function can be represented exactly by a ReLU neural network, but we have to approximate the known functions h(x)) = log((1 + 2)) and g(y) = exp(y) in a parameter sparse
7

---

Published as a conference paper at ICLR 2022
way. Thm. 2 Yarotsky (2017) states that univariate Lipschitz continuous function can be approxi- mated by a depth-6 feed forward neural network with no more than c/(elog(1/E) parameters. By specializing our derivation our known functions, in contrast, obtain better scaling c/ Ve with depth = 2, which leads to our main theorem.
Theorem 5. Let C {IIm (1." St, E [0. be subset of the poly-
nomial basis functions with bounded maximal degree q of cardinality ks = [B]. Let F (B) be the family of bounded (affine) linear combinations of these basis functions. For e, E (0, with prob- ability - 5 up to error fu contains a strongly universal lottery ticket fo C fu with respect F if has Ling 2 2 convolutional layers, followed by Lmuiti 2 fully connected layers, and Lesp 2 convolutional layers with channel size or width chosen as Thms. Hand 3 parameters.
with the following set of
Logarithm: 6iog = 1 (1 88/133 Olog
Gilem
Niog
+
V
ckm e
Mog
Q1og =.
Multivariate: 8multi = 1 (1 8))/3, Emudti
Gkmm
Mmulti
= 9.
Qmuiti = d.
Exponential: 8eep = 1 - (1 8)1/3, Geep Gkems
Nexp
IV
km
Mexp 2, Qeep - t loo 2.
1t
As show next in experiments, all our innovations provide us with practical insights into condi- tions under which pruning for universal lottery tickets feasible.
EXPERIMENTS
To showcase the practical relevance of main theorems, we conduct two types of experiments on a machine with Intel(R) Core(TM) i9- 19-10850K CPU @ 3.60GHz processor and GPU NVIDIA GeForce RTX 3080 Ti. First, show that the derived bounds on the width of the mother networks are realistic and realizable by explicitly pruning for our proposed universal lottery tickets. Second, we prune mother network architectures from our theorems for strong winning tickets with the edge- popup algorithm (Ramanujan et al. 2020 to transfer our insights to a different domain.
In the first type of experiment, we explicitly construct universal lottery tickets by following the ap- proach outlined in our proofs. The construction involves solving multiple subset sum approximation problems, which is generally NP-hard. Instead, we obtain an good approximate solution by taking the sum over the best 5-or-less-element subset out of random ground set. Usually, ground sets consisting of 20 to 30-elements are sufficient to obtain good approximation results. The mother network has uniformly distributed parameters according to Def.
Polynomial function family: We construct a polynomial function family consisting of k fea- tures of the form (1 + 2;)6 for any b E [0, 4] assuming d-dimensional inputs. If the mother network has a maximum channel size of 500, we obtain a maximum approximation error of 0.001, which is negligible. Concretely, assuming convolutional (or fully connected) layers of sizes [d, 200, 10, 200, 10, k 30, k 500, 40, 500, 1] (or higher) is sufficient. This further assumes that we Ning 10 and Neep 20 intermediary neurons in the approximation of the respective univariate functions. After pruning. 0.022 of the original parameters remain, which is sparser than the tickets that most pruning algorithms can identify in practice. Note that we can always achieve an even better sparsity relative to the mother network by increasing the width of the mother network.
The most restrictive part the approximation of f(x) = sin (2Tz) on [o, 1J. which can be easily obtained by pruning mother network of depth 4 with architecture [1, 250, 21, 250, 1] with Nain 21 intermediary neurons in the univariate representation. Pruning such a random net- work achieves an approximation error of 0.01 and keeps only 0.038 of the original parameters. Note that we can always achieve a better sparsity by increasing the width of the mother network. For instance, pruning network with architecture [1, 250, 250, 250, would result in 0.0035.
Fourier basis:
In the second type of experiments, we train our mother networks with edge-popup (Ramanujan et al. 2020) on MNIST (LeCun & Cortes 2010) for 100 epochs based on SGD with momentum 0.9, weight decay 0.0001, batch size 128, and target sparsity 0.5. Parameters are initialized from a normal distribution according to Def. 3l As the original algorithm is constrained to zero biases, had to extend to pruning non-zero biases as well. It finds subnetworks of the randomly initialized mother ticket architecture achieving an average accuracy with 0.95 confidence region of 92.4 + 0.5
8

---

Published as a conference paper at ICLR 2022
% (polynomial architecture) and 97.9 0.1 % (Fourier architecture) over 5 independent runs. Note that pruning the polynomial architecture is not always successful on MNIST but such runs can be detected early in training. This implies that our insights can transfer to domain different from polynomial or Fourier regression and attests the architectures some degree of universality. Note that even though edge-pon poppppppppppppp free to learn tickets that are different from the proposed universal function families, the architecture is still constrained to compositions of univariate and linear multivariate functions.
In addition, these experiments highlight that our parameter initialization (with non-zero biases) in- duces trainable architectures, as the success of edge-popup relies on meaningful gradients.
DISCUSSION
We have derived formal notion of strong universal lottery tickets with respect family of fune- tions, for which the knowledge of a universal lottery ticket reduces the learning task to linear re- gression. As we have proven, these universal lottery tickets exist in a strong sense, that is, with high probability they can be identified subset of large randomly initialized neural network. Thus, once a ticket is identified, no further training is required except for the linear regression. We have shown this with explicit construction of deep ReLU networks that represent two major function classes, multivariate polynomials and trigonometric functions, which have the universal approxima- tion property.
These classes consist of basis functions which can be represented by compositions of univariate functions and multivariate linear functions, which amenable to sparse approximations by deep ReLU networks. As we highlight, the use convolutional network layers can significantly im- prove the sparsity of these representations. Up to our knowledge, we have presented the first proof of the existence of universal lottery tickets and of lottery tickets in general in convolutional neural networks. Most remarkable is the fact that these common function classes with the universal ap- proximation property have sparse neural network representations. Furthermore, they can be found by pruning for (universal) lottery tickets. consequence, we should expect that many tasks can be solved with the help of sparse neural network architectures and these architectures transfer poten- tially to different domains.
Our theoretical insights provide some practical guidance with respect to the setting in which sparse universal tickets could be found. We have shown how parameters can be initialized effectively and discussed what kind of architectures promote the existence of universal lottery tickets. In comparison with the theoretical literature on strong lottery tickets, we have relaxed the requirements on the width of the large randomly initialized mother network and made its depth variable. Some of novel proof ideas might therefore be of independent interest for lottery ticket pruning. Interestingly. in contrast to the standard construction of lottery tickets, we derived proof that does not start from representing a function as neural network but as linear combination with respect to a basis. In future, we might be able to use similar insights deepen our understanding of what kind of function classes are amenable to training by pruning in search of lottery tickets.
As word of caution, we would like to mention that strongly universal ticket (whose existence we have proven) is not necessarily also 'weakly' universal ticket (which is more commonly identified in practice). The reason is that in case that we train ticket that represents the right basis functions together with the last layer (i.e. the linear regression weights), also the parameters of the ticket might change and move away from the suitable values that they had initially. In several common initialization settings, however, the parameters of the bottom layers (that correspond to the ticket) change only slowly during training, at all. Therefore, a strong ticket will often be also a weak ticket from practical point of view.
Furthermore, it is important to note that the universal lottery tickets that we have constructed here not necessarily the tickets that are identified by pruning neural networks in common applications related to imaging or natural language processing. It would be interesting to see in future how much redundancy these tickets encode and whether they could be further compressed into basis.

---

Published as a conference paper at ICLR 2022
ETHICS AND REPRODUCIBILITY STATEMENT
We do not have ethical concerns about our work that go beyond the general risks associated with deep learning that are, for instance, related to potentially harmful applications, lack of fairness due to biases in data, or vulnerabilities of deployed models to adversarial examples. The advantage of universal lottery tickets, whose existence we have proven here, is that we might be able to un- derstand and address some of this limitations for specific architectures that can than be reused in different contexts. Code for the experiments publicly available the Github repository Univer- salLT, which can be accessed with the following url https::///////.. httti::://ggtthbt gigggthu...... com lat./eeeaaiiaaaal.. UniversalL
ACKNOWLEDGMENTS
NL and RM were supported by the National Institutes of Health grant P42ES030990. AG was supported by Swiss National Science Foundation Early Postdoc.Mobility fellowship.
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference Learning Representations, 2018.
David Balduzzi, Marcus Frean, Lennox Leary, J. P. Lewis, Kurt Wan-Duo Ma, and Brian McWilliams. The shattered gradients problem: resnets are the answer, then what the ques- tion? In International Conference Machine Learning, 2017.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varinnar trade-off. Proceedings of the National Academy of Sciences, 2019.
Rebekka Burkholz and Alina Dubatovka. Initialization of ReLUs for dynamical isometry. In Ad- vances in Neural Information Processing Systems, volume 32, 2019.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. In Advances in Neural Information Processing Systems, volume 33, pp. 15834-15846. 2020.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals, and Systems (MCSS), 2(4):303-314, December 1989.
Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova. Nonlinear approximation and (deep) relu networks. arXiv, art. 1905.02199, 2019.
Payal Dhar. The carbon impact of artificial intelligence. Nat Mach Intell, 2(8):423-422 2020.
James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning randomly weighted network. In International Conference on Learning Representations, 2021.
Jonas Fischer and Rebekka Burkholz. Towards strong pruning for lottery tickets with non-zero biases. arXiv, 2021.
Jonas Fischer and Rebekka Burkholz. Plant 'n' seek: Can you find the winning ticket? International Conference on Learning Representations, 2022.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics, volume 9, pp. 249-256, May 2010.
10

---

Published as a conference paper at ICLR 2022
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 on computer vision, pp. 1026-1034, 2015.
Kurt and Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251-257, 1991.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http::////// lecun
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances neural information processing systems, pp. 598-598890 008, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based
on connection sensitivity. In International Conference on Learning Representations, 2019.
Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. In International Conference on Learning Representations, 2020.
George S. Lueker. Exponentially small bounds the expected optimum of the partition and subset sum problems. Random Structures Algorithums, 12(1))51-62. 1998.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning, 2020.
Ari Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian. One ticket to win them all: gener- alizing lottery ticket initializations across datasets and optimizers. In Advances in Neural Infor- mation Processing Systems, pp. 4932-4942. 2019.
Laurent Orseau, Mareus Hutter, and Omar Rivasplata. Logarithmic pruning all you need. Ad- vances in Neural Information Processing Systems, 33, 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Op- timal lottery tickets via subset sum: Logarithmic over- paramaterizzaiionnn is sufficient. In Advances in Neural Information Processing Systems, volume 33, pp. 1599-2610, 2020.
Allan Pinkus. Approximation theory of the mip model in neural networks. Acta Numerica, 8: 143-195, 1999.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in randomly weighted neural network? In Computer Vision and Pattern Recognition, pp. 11893-11900 19922, 2020.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification. In Advances in Neural Information Processing Systems, volume 33, pp. 1 11380-11399 2020.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural Networks, 2015.
Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReL.U acti- vation function. The Annals of Statistics, 48(4):1875 1897, 2020.
Johannes Schmidt-Hieber. The kolmogorov-armold representation theorem revisited. Neural Net- works, 137:119-126, 2021.
Or Sharir, Barak Peleg, and Yoav Shoham. The cost of training NLP models: A concise overview. arXiv, 2004.08900, 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Advances in Neural Information Processing Systems, 2020.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory, vol- ume 49, 2016.
11

---

Published as a conference paper at ICLR 2022
Chaoqi Wang. Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference On Learning Theory, 2018.
A RESULTS IN SUPPORT OF EXISTENCE THEOREMS
In the following sections, we represent the proofs our theorems and discuss different representa- tion options of lottery tickets. In particular, we highlight the benefits of additional depth for reducing the maximum required width the mother network fo- We frequently utilize various forms of so- lutions to the subset problem and present novel results with regard to this general problem.
A.1 INITIALIZATION
We derive our proofs by assuming that the parameters the randomly initialized mother network fo are distributed in the following way. In case of uniform parameter initialization, we assume that the weights and biases follow the distributions w - 2] and biases b ~ U[-1, 1]. case of normal parameter initialization, we have w ~ (0, 4) and biases b ~ N 1). The following lemma explains, why we can follow this approach when the parameters are initialized according to Definition 3 and the output of a neural network is corrected by a scaling factor À = 120
Lemma 6 (Output scaling). Let h (6o, σ) denote transformation of the parameters Oo of the deep neural network for where each weight is multiplied by a scalar ds i.e., hig (Wa,z) = a.wo and each bias is transformed to l (1 = II'm=1 Imm= Then, we have f (x h(00, () = I (x 0o)
(1)
For completeness, we present the proof but note that it has been also derived by (Fischer & Burkholzz 2021
Proof. Let the activation function ø of a neuron either ReLU 6(x) = max(æ, 0) or the identity d(x) = x. neuron 2!!) in the original network becomes g (x."² after parameter transformation. We prove the statement by induction over the depth L of deep neural network.
First, assume that L = so that we have x; = & (E, (1 wij Tj 15+00 b(a²) After transformation by
wiy + o1 ( and b(") + o1b(", we receive (21") o (E,ug) σιæ + +rb!") =012("
w
because of the homogeneity of d(.). This proves our claim for 1.
Next, our induction hypothesis is that g (zit-1) = [ oma
(L-1)
follows that
Σ
wig
(L)
oig
(z)
(1(b-1))
(
(L) II Fm
(def. of transformation)
(5)
m=l
L-1
L
Σ
Wig o II
(1-1))
+ b(())
II
Fm
(induction hypothesis)
(6)
m=1
m=
(L) (homogeneity of d).
T
m=1
which to be shown.
12

---

Published as a conference paper at ICLR 2022
A.2 SUBSET SUM PROBLEM
Our proofs frequently rely on solving the subset sum problem (Lueker
1998 which was first uti-
lized in existence proofs of strong lottery tickets without biases (Pensia al. 2020) and then trans-
ferred to proofs of strong tickets with biases (Fischer & Burkholz [202]] 2022 (022 It applies to general
iid random variables that contain uniform distribution, defined next.
Definition 4. A random variable X contains uniform distribution if there exist constants (0, 1), e, > and random variable G1 so that X ~ (C - h C ht + o.G1
Such random variables can be used to approximate any 2 E [-m, ml bounded interval, as our next corollary states.
Corollary 7 (Subset sum approximation ). Let X1,..,, X,, be independent bounded random vari-
ables with |X < B. Assume that each X5 X contains a uniform distribution with (see
Definition 4). Let c, 10 and m E I with m 2 be given. Then for any [[m,, m] there
exists a subset S C [n] so that with probability least 8 we have 12 E Xul cf
n 2 C max 1, T. log
ming (ox)
min
5 max (1.m//1 max (m.
Proof. For m 1 the proof is subset of the proof of Corollary 3.3. by Lueker (1998). To extend these results to m > 1, let us fix 8' and e' that we will later choose depending on e, o, and m. We know that approximating any z' [-1, 1] is feasible with probability - 8' up to error e' based on random variables Xx/h as long as we have at least
B
n1 2 C log a
min (8', (0')e)
(8)
random variables.
Next we distinguish two different cases. 1) Let us start with h/m < 1. To approximate any separate subset sum approximation problems. Note that the variables Xx/h contain uniform distribution U[-1, 1] so that we can approximate z/m E [-1,1] by Iz/m E Xa/h| I e'. It follows that jzh/m - X₂l S e'h. We use this approximation result m' we draw total n [m/h]n; random variables. assign each to one of m' [m/h] independent batches A = (X(x-10 (xmmm))m++ 11mm-1mmm+ "km.
E [-m, m]. we approximate z' zh/m by solving m' = (m/h]
mm/h] times. Accordingly,
Xkme), ) and use each batch A& to approximate zh/m up to error
''h. This approximation is successful for all batches with probability (1 8' y'mm' and identifies index sets Sy so that
Σ SE
X11
l2/mm
Σ SES
X S m/hc'.
A=1
Thus, if we choose 8' and e' that 8'mmm > (1 8), we obtain the desired approximation guarantees with = m m'nj. This is fulfilled for 8 = =8/m' = 8h/m. and = e/(h'') = c/m.
2) The second case assumes h/m 1. Let us define = 2m/h h with m/h h < for which we have [ž/m| < | < 1. Thus, also z/h E [-1, 11, as z/h 2/m. It follows that we can approximate z/h with a subset S of ny random variables / so that 1z/h Σkes Xz/hl I e'. Hence, we have
Σ Xal he' RES
The choice e' e//h meets our approximation objective.
Next, we explicitly state two special cases that we use frequently in our initialization set-up. Lemma (Approximation by products uniform random variables). Let XI..., X,, be iid random variables with distribution X, V2V, where Vi ~ U 1] and V22 U[-2, 2] independently
13

---

Published as a conference paper at ICLR 2022
0.5
04
0.3
0.2
0.1
0.0
1
3
Figure 2: Each standard normal distribution Z NN, 1) contains uniform distribution U1-h, h] with the shown a, where a ((h/o(())) /2///.. We use the highlighted value h = 1 in our proofs.
distributed. Let e, 8 E (0, 1) and m > 0 be given. Then for any 2 E [-m, ml there exists a subset C [mi] so that with probability least 5 have [z Eies Xi
m
n 2 Cm log
min (6,
Proof. Our main proof strategy is the application of Corollary Since X₃ is obviously bounded by B 2, only have show that X, contains uniform distribution. For V22 U1-1, 1] this has been shown already by Pensia et al. (2020) with Corollary 1 and a = log (2) 1/2, and c 0. The same arguments apply our case with log(4)/4, h 1, and into the generic constant C.
which integrate
Alternatively, we might want consider initialization schemes with normally distributed parame- ters. The next lemma confirms that each normal distribution contains uniform distribution.
Lemma 9. A normally distributed random variable 7 ~ (N, o²) contains uniform distribution Ul-a, of with a 0.4.
Proof. From Definition it can be showed that random variable Z contains uniform distribution U[-h, hi if the probability that E [-h, ht is at least as big as if would flip biased coin that turns up heads with probability a 0. In of this event, would further draw element from [-h, h] from a uniform distribution v[-h,, h). In other words, it suffices to show that there exists 0 so that the probability density Pz(a) (z) fulfills P2(x:) (2hh) for all h-.,
Since Z ~ NO0 o²), its density is given by 0(z/o)/o, where <(x) denotes the density of the standard normal distribution. Since ((x) is monotonously decreasing in x for >> O, we need to fulfill < @(h/a)2h/o For h a, this is fulfilled for 0.4 < 2 x Φ(1). Figure 2 shows the different choices of for varying and o 1, which confirms that h in general leads to relatively high values of a.
We can use this proof to show that products of normal distributions are also suitable for approxima- tion with the help of the subset problem.
14

---

Published as a conference paper at ICLR 2022
Lemma 10 (Approximation by products of normal random variables). Let .i.... ...,...,, X, be iid random
variables with a distribution X1 ~ V2V1, where V12 ~ (N N > 0) with ~ (N(0, ()) and
V2 NO0 4) are independently distributed with 01 = or 0n 2. Let 6, d E (0, 1) and >
be given. Then for any E [-m, ml there exists subset S C [rx] so that with probability at least we have lz -iies Xil E
n 2 Cm log
min (6, c) (G.cc)
m
(10)
Proof. To apply Corollary 7 we have to show that the product V2, contains uniform distribution. In addition, have to solve the technical problem that normal distributions not bounded random variables. However, for given bound B, we can simply ignore all variables that exceed that bound [X, and just make sure that enough bounded variables are left with high probability so that we can solve our approximation problem. In fact, let us only use variables with 1/2 < V1 S and [V2| < and assume that we need least "p of variables X; that fulfill these criteria with probability (1 6/2). With the help of union bound,
that need at least n 2 C(n, (2/)) variables to ensure this. Note that C' depends on the bound and decreases for increasing B, while the width requirement in Corollary increases in B log( [B). One could trade-off both with the right choice of B but this not relevant conceptually in our proofs.
Given the variable V1, the random variable V2 is distributed V2 V1 N (0, (V),, which contains U 21-2V,, 2V] with U[ for all 1/2 & Vi < with a = 12(2) so that V/2V V1 contains U[-1, 1] with (2V)) 2 0.2 Thus, V2 also contains U[- with 0.2.
0.4 according to Lemma 9 Note that
contains
Applying Corollary
7 to bound np thus concludes our proof.
Next, we will prove an even stronger result on approximation by solving subset sum problem that allows us to mix random variables with different distributions.
Corollary 11 (Extended approximation with subset sum). Ler X1...,, X be independent bounded random variables with |X,] < B. Assume that each X; X contains a uniform distribution U[-1,1] 1] with potentially different as > 0 (see Definition 4). Let e, E (0, 1) and m E N with m given. Then for any [-m, m] there exists subset S [n] so that with probability at
least 1 8 we have Eies X; S if
hm n N C min (os) min (8,
Bm
log
(11)
Proof. Following the same arguments Lueker 1998) in his proof of Corollary 3.3, we only need to ensure that we can obtain 2 C' log I/c) samples that are drawn from a uniform distribution U[-1,1] 1] approximate
E [-1, 1] up precision with high probability. The probability that an individual sample X; falls into this category is or, and is at least a' min; {oa} for every sample. With this a', we can follow exactly the same steps as Lueker (1998) and arrive at the stated
result.
The following lemma is also stated the main manuscript as Lemma
Lemma 12. Define a 3/4 and let wy Ul-2, 2] denote iid uniformly distributed random variables with E [k]. Then wi is contained in interval
f-1
Wi E
1/
wi
1/
a
wi
with probability at least q = 1/16. If this is fulfilled for each wj. then
II
< 1/a.
i=1
The holds true each wy NO, 4) is iid normally distributed instead.
15

---

Published as a conference paper at ICLR 2022
Proof. We prove the statement by induction. First, let k and note that Σ wi S 1/a with probability (4/3 - 1)/4 1/12 2 1/16 for uniformly distributed w1. For normally distributed W1, 1 W1 S 1/a is fulfilled with probability ((1/(2a)) Φ (1/2) 2 (1/a 1)/4= 1/12 2 1/16.
In the induction step from + we assume that
w
1/
II
w
1/
i=1
with probability q for k which implies that
II Wi
S 1/a.
We have show that also S Wk+11
(I wi
1/a and thus
Wk+1
We
Wi
For uniformly distributed wh+1, this is fulfilled with probability (1/a-11// (4IIi_ me (1/0-
1)a/4= = 1/16 = q. where we used the induction hypothesis. For normally distributed Wk+1, this is also fulfilled with probability (I/a 1)//4 1/16 q.
B EXISTENCE OF LINEAR AND UNIVARIATE LOTTERY TICKETS
At least specific function classes, we can significantly relax the width and depth requirements. The family of functions that are particularly interested in are compositions of univariate functions and multivariate linear functions. This also allows us to leverage the parameter sharing offered by convolutional layers gain further improvements. We first focus on fully-connected mother networks fo. as we can also utilize them along the channel dimension in convolutional layers as well.
B. MULTIVARIATE LINEAR LOTTERY TICKETS
Our first existence results present for affine linear multivariate functions f(æ) W + b. As every layer of a neural network layer is essentially composition of this function and an activation function ob ( the main ideas that we present here could be immediately transferred to pruning for general target networks.
Statement. Assume that c, E (0. 1) and a farget f: 5 S - Rm with f(x = Wa+h
with M := [max,,, max( |.,ll [b.()], N non-zero parameters, and Q (supaes | 1) are given. Let each weight and bias of fo with depth L 2 and architecture ng be initialized according to Def. Then, with probability at least 5, So contains a sparse upproximation Sc C So so that each ouipul component i is approximated as max [f((x)) (x)) S if
Md
14,0
C L --1
log (M/ A//mnn//// min (6/(2(m d) + N 1),c(11)
for L > and
M
11,0 2 C'Mllog
min 18/(N 1),e/Q}
for L = and = 12
(20 12)
Proof. First, we analyze the amount of error e that we can make with each parameter and still meet approximation objective.
16

---

Published as a conference paper at ICLR 2022
Error propagation:
Let us assume we approximate a target function component f((x) = w a + b; with another mul- tivariate affine linear function ge (z) a" x + with close parameters that |a; wil S e, and [b:-c| I et. Then, it follows that supaes [x( (aee))ge,(()) (x))( S supzes اه - [yرlمر +|: S
<l (supxes ||ل||| + 1) = Qe I e, if S e/Q.
Lottery ticket construction:
Next, we have to construct a lottery ticket that computes such a function ge ge(x) for each output component. Our construction strategy depends the available depth L. We start with the case 1
Case 2: 2:
As PPensia et al. (2000, we utilize solutions to the subset sum problem. In addition, however, we have to deal with the fact that our parameters non-zero biases. While Layer 0 and Layer 2 of both fo and our ticket fe are fixed to the input and output neurons respectively, we can only prune Layer 1 of fo. which has width no,1 .. How could we represent our target f in this setting? We can write each output component of our target as
not necessarily bounded by 1 and that have
lixx) = Σ Wjz + b; = Σ wyy(s,)) j=l
+ Σ (-w;))((zz)) + b.o(1), j=1
5=1
utilizing the identity x (xx) - nb{ (x) for ReI.Us. This shows that we can represent ʃ as 2-layer
neural network consisting of 2d + neurons in Layer 1, i.e., ((xz), ø( (-=r)), and ((1).
Let us thus prune np out of the na,1 neurons fo to neurons of the form u,((yzzy) with by > to help represent wy)(2y) and prune np of the neurons in fo to neurons of the form uz0(v)Hz)) with U; < 0 to help represent (--))((z))) and prune np neurons to u,,(v;) with vy > to represent (10(1).
How large must Ro,1 be so that this pruning is feasible with probability at least 1 - for a given np and 8' 0? (Note that this was assumed to be possible in (Pensia et al. 2020) with probability one, which is not entirely correct.) To use the union bound to answer this question, let us first estimate the probability that cannot find ny neurons of each type. If we could not find those then least No,1 n, + neurons in fo must be useless to prevent pruning of a neuron of a specific type. A neuron is useless for specific type with probability 0.5, since 0j > (or vy > 0) with probability 0.5. We only have (d + 1) possible cases of failed pruning, because pruning can only fail for one of the types wy0(x;) or (-w, (w)))((())) but not for both, since each neuron in Layer of fo falls in one of the two categories. It follows that with the help of union bound, we can thus ensure that we can find enough neurons of each type with probability at least 8' if = (d+ 1)0.5 npp11 and thus
no, 2 max (np log(2) log ((d + 1)/8") (2d 1)mp)
(12)
Now that we have ny neurons for each of the 2d + neurons that we want to approximate. We can utilize them as ground set in solving subset sum problem to achieve a small approximation error of each wy (x,,)
Using Lemma 8 or Lemma bility at least 8"
10 we are successful with our approximation up to error e" with proba-
np 2 CM log (M/ min("", "")).
Putting everything together, we have to ensure that the pruning works (see Eq. 12 with probability (1 -1-68 (1) and that every approximation of each of the N non-zero parameters is successful with
probability (1 - 8"). This is achieved with probability (1 8) for 8" = 8' = 8/(N + 1), as we obtain from a union bound. Furthermore, we can allow an approximation error of each single
parameter of é' =/Q, we derived earlier. This can all be achieved by
11,0 2 CMdlog min (6/(N + 1),e/1))
M
Case L > 2:
In comparison to the case I 2, we have the additional advantage that we can also prune Layers
17

---

Published as a conference paper at ICLR 2022
,, 1. As in the proof of the case L = 2, need in total Root (2d + 1)mp neurons for successful approximation. But utilizing Corollary we can distribute these Tro neurons on L layers. Thus, each layer has to cover only nha (L neurons.
Md
M
n1o0 C
L log
min (8V/(N 1),e/Q1)
are therefore sufficient to for a successful approximation with probability at least 1 - 8'.
Our construction that achieves this visualized in Figure (e). It consists of (L - 1) subset sum blocks, i.e., subnetworks with [(dd + 1))p 1)] neurons in the intermediary layer and m out- puts. Each of these intermediary outputs, say y/s (represented by a blue node in the figure), is con- nected to the final corresponding output 2 along path of neurons of the form wL-10(...d wy (1))))
with w/ > O, thus adding 1 y to the final output =t. Exemplary paths are also highlighted in orange the figure.
Corollary 11 states that each of these contributions is valid in subset sum approximation, as long as we can bound the path weight such a way that we can integrate it into our universal constant of each width requirement. This is the case for 1 S I we need to find maximally m + d of such wy. Lemma provides us with the result that a random neuron be pruned to represent such a neuron @ w,)) that path with probability at least g so that a = 3/4. Note that and a are independent of L. This guarantees with the application of a union bound that
T-- j=l wj S 1/a for an a < 1. In each layer,
n1 2 C' C'lo(((m + d)/8")
(13)
neurons need to be available for pruning to find the desired 2(m + d) neurons with probability at least 1 - 8", where C' = log(1/(1 q)).
Putting everything together, using union bound, we can guarantee an overall existence probability of at least - 8 by setting 8" = (22222++m)))
N 1) and 8' 6(N + 1)/ dL
1) + N + 1). which leads to
Md
71.0 2 C T T- log min (M/ 1) 1)),
B.2 UNIVARIATE LOTTERY TICKETS
A similar reasoning for linear multivariate lottery tickets allows prove our results for uni- variate lottery tickets, the second important building block of our representation of basis functions. However, we generally need 3 layers to implement subset sum approximation instead of the layers required in case of linear multivariate lottery tickets. Note that other results on network prun- ing would require at least two blocks and thus exactly 4 layers in the mother network (Fischer & Burkholz 2021) (or could not represent the architecture because they are restricted to zero biases Pensia et al. (2020). Our 3-layer block leverages the specific neural network structure that we use to approximate an univariate function, which we introduce next.
It is well known that every deep neural network with ReLU activation functions d(x) = max(x, 0) is piecewise linear function (Arora et al., 2018). Conversely, each piecewise linear function with a finite number of linear regions can be represented by a ReLU network as long as it has enough neurons (Arora et al., 2018: Daubechies et al. (2019).
Deep neural networks are generally overparametrized. Yet, all parameters of an univariate network f can be mapped to the effective parameter vectors a and that represent f in the following way. The knots s = (si)se[N-11 mark the boundaries the linear regions and a = (a:)se(N) indicate changes in slopes m, = (f(s+41) f(s)) / ($+41 - s;) (with sy == Sx + c) from one linear region to the next. Assuming f(x = aN for x < 8p. we can write
fx(x) - Σ
a, 34) AN
(14)
==0
18

---

Published as a conference paper at ICLR 2022
with a; m, m,-1 S i 1, dg mo, and aN f(s)).
The relevant domain, where f varies non-line non-linearly, is defined by [sp, SN- Without loss of gen- erality, we assume that is positive so that f(z) 2 0 for all I E [s0, SN-1 This can always be achieved by an affine linear transformation of the output that is learned by the last layer. Alterna- tively, the parameters of the deep neural network could be transformed appropriately. The last layer of the randomly initialized mother network fo can have either ReLU or linear activation functions, since we assume f()) 2 0 so that (ff(x)) f(x) holds.
For given / of this form, we want to find a lottery ticket that is an e-approximation of f. The first question that we have answer is how much error order to achieve this.
allowed to make in each parameter in
B.2.1 PRUNING ERROR FOR AN UNIVARIATE LOTTERY TICKET
Lemma 13 (Approximation of univariate piecewise linear function). Let E > 0, f be defined as Eq. 14) and fe be a piecewise linear function whose parameters fulfill |a, ai,el I Co and 18 81.e I with
Co
E,
(15)
(IN + max sol 1s + E [s.1)
2 N EN- la:)
Then maxpe(so.xx [f(x) - fe(x))
Proof. It follows from the definition of f. the triangle inequality, and the fact that (Ø(x) - +(v)) s
xx y that
[f(x)
fc(x)) <
a; di.c1l0(x s:)l + lai,ell0(x: - -si) 6(x -81.)) + IaN aN.d
ca |
85e + las,ells
8t,e + ta
N
N
N|
+
88
ai. les
i=1
N
N
Ea
N
+ 1+
Σ
+
(las) + Ea)es
1=1
D=
Ea
Na. 1++
Σ
[s:]
+
Σ
(las) + 1)cs
1=
N-1
$ 6a
N max[(ssp
+
Σ
|s;|
+ c,
N
Σ
aal
2 2
for all x E [Sp. -1- where we have used Eq. 115) in the second to last inequality and assumed
that |s >
Letting Q max | M (1 + max (max; |as|, maxy (s;1)), and using similar argu- ments, we can more generally derive that
max
zES [fx) fe(x)) & (1 + NQ + (N - 1)M) + NM S N + M) + NM
where used the fact that M in the last step. It is therefore sufficient bound the error in each individual parameter by 10; 0;,l S </(2N + M)).
For convenience, we state again Thm. before we prove it.
19

---

Published as a conference paper at ICLR 2022
Statement (Existence of univariate lottery ticket), Assume that c, () and univariate target network f I S in form of Eq. (14) consisting of N intermediary neurons are given. Define M (1 + max (max; |az], max; (s,l]] and Q mäxfes [z). Let each weight and bias of fo with
depth I. 2 2 and architecture nn be initialized according to Def. 3 Then, with probability at least 1 5, fo contains sparse approximation C that max.xee..eene... (1(1)()))))))))))()) Xfe(x)) S with
11,0 2 C max [M
M
log
(16)
-
min {8/ [L(N + 2) - c/(1
for L 2 and
MQ
M
01,0 2 C
log
min {6/(NV + c) c/(2 MI11)
for L 2, where the output is scaled by x == II (20
Proof. Let start with the case L
Case I. 3:
Note that we can represent target network ((x) Li= 0z6(1 82) + aN univariate neural network consisting of 4 layers
f(x) Σ - -;,(() + sign(ax)
where the first layer has width n1 and the second layer has width n2 = N + 1. (Note that we can also apply another ReLU activation function to the output, (x(()), because we assumed that fz) is positive. We omitteed it for clarity.) Lemmas 8 or I0 let us solve the associated (2N + 1) subset sum problems if the first layer represents enough neurons of type d(x) and 6(1) with
min (5/(3/ + 2), c/(2(( + + )
M
11.0 2 C.M log
(17)
where each parameter (1, 11, -2) is approximated up to error e/ e/(2N + M)). The 11,0 neurons serve the creation of 7220 neurons in the next layer, which are approximately of the form o(x 8,) and oN. These in turn are used to solve another set of subset sum problems that approximate the parameters a, This is feasible for
3N + 2 8
22,00 2 CN log
(18)
Case L, 2 3:
Following the same steps reasoning as in our proof of the existence linear multivariate lottery tickets (see []. we can distribute the approximation of N + neurons on L 2 layers. The approximation of the target is thus successful with probability sum problems is solved and we find the following number of connections (of type wyy) that create paths between our intermediary outputs and final output. The first layer needs one connection 1, the second also 1, and all L 2 remaining layers need maximally N + 2 connections. In total, this results in 8' 5/((N + 2) L - 1) and thus
8 if each of the 2N + 11 subset
n1o0 2 C max ( [M,N]
M L-2 log min (8/ [LN + -1
(19)
Case T.
The case L = 2 is more complicated because we do not have enough layers to construct univariate neurons of the form ((x), (-=x), and d(1). Instead we have to create the required N neurons the form d(x 3) and avv(1) (1) directly in Layer 1. We can still achieve this approximation by utilizing Corollary 7 and thus solving N + subset sum problems. Note that we can associate a neuron wyd( w1 2 + b) in that is used approximate neuron 0, 8t) of f with random variable X. We construct such that it contains a uniform distribution U[- 1]. With n1,0 o of such X, we then approximate our target f using Corollary
20

---

Published as a conference paper at ICLR 2022
Thus, let derive the distribution of X. With probability at least q we have that 1 S W1 S 2. (q = 1/4 for uniformly initialized W1 and = 1/8 for normally initialized w1.) Given this w1, approximate s, within error e' with probability at least f2 2 c'1/2 by pruning neurons to have appropriate W2 contains a uniform distribution U[-1, with a 2 1/4 We can use this uniform distribution 1]
approximate az w1 up to error e//wi I 2/2. All together, the random variable X that reflects the described pruning contains a uniform distribution U[-1, 1] with e8/8. We can use 11,0 random independent copies of X approximate each of the N neurons up to error é' 2 with probability at least 1 - 8'. According to Corollary 7 this is achieved for
min {8//(N + +D,e))
M
11.0 2 CM log a
(20)
where the choice e' = e2(2)) and 8 = proves the claim of the theorem.
C EXISTENCE OF UNIVERSAL LOTTERY TICKETS
In the following, present theorems about the construction of lottery tickets as concatenated basis functions. Both versions, one for polynomial and the other one for Fourier basis functions, share the general set-up so that we start with a joint proof beginning.
Proof. To show that fe is strongly universal lottery ticket with respect to the function family F, we have to prove that if fulfils Definition Thus, for every g E F we have to find W E m and E R so that
sup [[((()) - g(0)) Sc.
(21)
z =
Since g E F, we can write each component as linear combination with respect to our basis functions
b, so that g;()) Σ}= dizby(2) (2x d, with azj. de [-1, If we define waj aijA and
G; = d, for a positive scaling factor O, we receive
sup =E[0,1]0
[[]f(x)+ + c-(())l #E[0,11
sup
loiy (
(22)
km sup mE[o.1]".jE[
(x) (x(x)
(23)
using (ayyl < and the triangle inequality. Note that this inequality holds for any p-norm ||-I| with p 2 1. Thus, fo is a strongly universal lottery ticket with respect to F if each component j is bounded as
sup (x) km =E[0,1]
(24)
To simplify the notation, in the remainder we drop the index j but understand that both fa( and b(xz) have I-dimensional output. To bound the error, we decompose it into two parts, one that captures the approximation of b(x) by a target deep neural network fN (and thus a piece-wise linear function) and one that handles the error related to pruning a mother network fo to obtain the actual lottery ticket fe.
- sup ()())))((a)) =Eju.1]
< sup (ff(()) fx())) sup =E(U,1]
[fx(x) - b(x))
pruning
approximation
(25)
2km
2km
The last inequality needs to be shown. The approximation eтrоr can be controlled by sensible choice of the deep neural network architecture, while the pruning error handled by Theorems and Theorems 3 In both cases, we also have consider, however, how the error propagates through the deep neural network layers. The following arguments depend on the specifics of the construction.
21

---

Published as a conference paper at ICLR 2022
C.I POLYNOMIAL UNIVERSAL LOTTERY TICKETS
We continue with the proof for polynomial basis functions. For convenience, we restate Thm. from the main manuscript.
S e be a subset of the polynomial basis functions with bounded maximal degree q of cardinality k = [B]. Let F (B) be the family of bounded (affine) linear combinations of these basis functions. For c, c, E (0, 1), with probability - 5 up to error 6, fo contains a strongly universal lottery ticket f. C fu with respect to F if f has Liog 2 convolutional layers, sollowed by Liudt 2 2 fully connected layers, and Leep 2 2 convolutional layers with channel size or widlh chosen as in Thms. Fand33 with the following set of parameters.
Statement. Let B C {II 0.5%
Logarithm: :ig (1 5)/13, Clog
Noog =1
Moog
2, Qlog =1
Gikmm
c
Multivariate: 8multi = 1 (1 8)1/3, Emulti
Tkmm
Nomtt
kd, Mmutti 9. Qmali
Exponential: 8eep = (1 8)1/3, Eexp
Nexp = 1
W
km
MMxp 2, Qes = log 2.
Gkm
1t
Proof. Our objective is to bound the approximation and pruning error in Eq. 25 sufficiently.
Approximation error:
First, we bound the approximation error in Eq. 25 by (2kkm). Our basis function b(x:) well as our approximating deep neural network fN (z) can be written as composition of three functions.
b(x) = 9 Eiin a,h((:)). where h(x) = log((1 - 2)) 0 I a, S g. Σí a₁ S t, and g(v) = exp(y) for - log(2)t S y S 0, ( 0.5 for y < - log(2)t, t, and g(v) = 1 for y O. fx -N | (.:)(x))) where gN and hy are piece-wise linear approximations of g and h respectively. As we have restricted our approximation to compact domain, all functions are Lipschitz continuous. Here, and in the sequel. we use the fact that on any interval, the slope of the piecewise linear function IN is bounded by that of g. which follows from the construction of gN in Eq. (4).. Therefore, on any interval, the Lipschitz constant of g is also the Lipschitz constant gN- Thus bound the difference between both functions as
sup [xx(x:)= b(a)) = sup ==
Σ
ach(ars)
Σ ashi aadiv(z))
YN
=E(0,17a
g Σ acti(ars))
Σ actin (xs) (2rs)
Σ cachvolae)
Σ
sup ==
9N
Ligh sup =c(0..]
[m(x) hu (x))
sup =E(-t -
[g(z)
(x)),,
(26)
where we bounded each a; by y and e' denotes the pruning enror for now. T. denotes the I Lipschitz constant of g(y) and (1) (y) on their domain [-t e',''), which is bounded by 1.
Thus, bounding
sup [h(x) hx())) [
and
sup xE| log(2)
10(x) 9N)(
(27)
4kmf
4km
would be sufficient to control our approximation error. To achieve this, we have to allow for large enough number of neurons Neep and Nog in the univariate representation (14) of gN and hx.
Approximation of hxx) log((1 + x)/2)
Let us determine Njo first. We partition the domain Jo. 1] of h
(1:) into intervals I, = [sa, 8,+1) C
[0, 1] and 1x-1 [ 2 2. - [0, 1] of length A I/(N -1) based on equidistant knots 8; with 8o = and 8N = For every æ let in mark the index of the interval in which x E I;, is contained. Since h(x) = log( /)) is concave, have for all
[xx) hew (x)) h(x)) (x) hxx) h(si.) (x si.) (h(si,+1) - h(ss,)))) / (28)
22

---

Published as a conference paper at ICLR 2022
where & arg min; 2-=,20 8; is the index the corresponds to the interval that contains Furthermore, the maximum approximation error is attained on the interval fo [0, A). Accordingly, we have
sup 1h(x) [x(x)) =E
sup log (og(00.(11 + =)) log(0.5) r+m =E(o,A]
sup log(1 + x) 2 =E[O,A]
log(1 A)/4 A. To identify the position of maximum error, we set the first derivative with respect to a of the error objective to zero and obtain x 1/m 1. This results in
with =
A))
sup [h(x) - hx(x)]= = sup log(1 + + - x = log (1 + 1/m 1) - (1/m - =E(0.1]
=E(O,A]
=- log(mm) + m - = 1/2A - 1/822 + 1/244 + - 1/2A
+ 1/342 - 1/442
where we used the series expansion of log(1 + z)) For 0.25A 2 < Abmm
we can therefore guaranty
small enough approximation error. Hence, the choice Nog 1
km!t
is sufficient achieve
the desired bound Eq. 27
Approximation of (x) exp(x)
We can make a similar argument for g(z) = exp(x) on its domain D = (-tlog(2) - Since we cut off 9 and 9N outside of the actual support i log( 2), 0] to avoid amplifying errors that know are errors, we can just focus on the domain [-/ (),)). Note that also exp(-) is monotonously increasing, but since is convex, have
sup =El-tlog(2),0)
1g(z)= (N(x))
sup (N(x) g(x)
sup exp(-A) m(r + A) exp(x) zE|-A,0]
A.]-A.0]
with m = (1 -1- exp(-A))/A ~ (A 0.5A2)/2 = - 0.5A. The maximum is attained at x² = (m) so that we have
1g(x) (N(x)) = exp(-AX + m(log(m) + +A) - m x 1/822,
sup log_tlog(2).0
where we employed series expansions of exp(x) and log(1 + 2). Again, from A
log follows
Noe
that any Neep 2 1
+
would be sufficient to achieve our approximation objective 27
4c
Last but not least we mention also the number of non-zero parameters that want prune in case of the multivariate function. As we can represent this function exactly by deep neural network, we do not inflict any approximation error and we can set Nuulti dk the maximum number of its non-zero parameters.
With this, we have derived the stated N. We still have to bound the pruning error to conclude our proof.
Pruning error:
The pruning error in Eq. (55 has to be smaller equal to c/(2km) which we can achieve by limiting the pruning approximation errors éexp- Emultis and elog in Theorems and 3 to represent the targets gN. hn and the multivariate linear map with matrix A.
Similarly to Eq. (26). we have to consider the error propagation through a composition functions. Yet, this time also the multivariate linear map inflicts error. Recall that our deep neural network
J' (x) can be written as composition of three functions so that [N(x: = gN (Ei- (x))) Analogously, also our lottery ticket is of similar form: f((x) ge (a. a, denotes function from Rd to R. A slight complication is that can approximate each lottery ticket only up to scaling factor X. The scaling factor of each function is not completely arbitrary because all together have harmonize with the initialization of biases, as previously explained. The
where
23

---

Published as a conference paper at ICLR 2022
exact scaling factors in the theorems ensure that with À desp- we write
ON Σ aahr((ss)
sup [fx(x) Afe(=))
sup mE(o.1]a
Axplee (Amutiae (eogte(()))
==(0,
IN Σ ((sh((z))) IN (emutu Digg (2)))
sup # 1e
sup (0,11
19N (Amulrice Doog (2+)) Aeepll (Amuttite (Atog te (x)))
LgN 2E(0,1]
sup
acli (2+) - Amunide (x)))((z)) Σ iml
+ yE ( (2) e'' e',e")
sup
1 (v) - Aapple (t)
Stoo
Lax me 10
sup
Σ at (xx((x)) (si)) + sup LgN i=1
Σ
Aioiog (x))) Amutiia (eogte (x))
Heesp
Stank
sup =E[U,1]
Lax' [xN(x)) (x) + + Emulti + Eoxp
Scme
Lug tling + Lu Emulti + Cexp:
(29)
where we have used Theorems and to bound the difference between a target network and the corresponding lottery ticket. Theorem depends on M (since all parameters are bounded by 4) and Q = d, since h(x)) E [0, 1] and the inputs to the multivariate linear function are bounded this way. Since Lgy I 1, we can thus achieve pruning error of maximally e/(2m) with with flog </(6kmt)), Emuht = e/(6km). and Eexp <66km).
With the stated parameter choice, each of the three parts of the lottery ticket exists independently
with probability at least (1 5)1/3, All three exist thus with probability at least ((1 - 6)133) (1 5), which concludes our proof.
L
C.1.1 FOURIER UNIVERSAL LOTTERY TICKETS
Similarly, we can also bound the approximation and pruning error in case of the second family of functions that we have considered. In doing so, we prove the following theorem.
up to error fo with the specified properties contains a strongly universal lottery ticket fe fo with respect to the function family FF (B), which defined as bounded affine linear combinations with respect to a finite subset of the Fourier basis
Theorem 14. For e, ô E (0, 1), with probability
functions B { sin 2T EE
1433 + +)) 14 E [M][Vi [d], E [0, 11, 24 E [0, 11} with car- dinality k = |B]. fo consists of Limuti 2 2 fully connected layers followed by Luin 2 convolutional
layers whose width or number of channels fulfill the requirements of Thms. and 3 with the follow- ing of parameters.
Multivariate: ômulti = 1 - (1 5)2/2, Emulii
Nmulti = dk: Mmunti = 1 + M, Qmaitii = d.
Skmmn
Sin: dain = =1 1)1
Tkm Nain
1 +
т arcssin (Esin/2) 21 Main + (d + 1)M,
Qsin = (d + 1)M.
Proof. As for polynomial lottery tickets, have to bound the approximation error and the pruning error separately to be smaller or equal to c/(km) to fulfill Eq. 25
Approximation error: The basis function b(x) as well as our approximating deep neural network f.v (æ) can be written as
composition of two functions. b(xx)= EE nept + ex) where g(v) sin 0 S m S M,
24

---

Published as a conference paper at ICLR 2022
and с [0, 1]. Correspondingly, fx(2)= ON (Ei n,z; n, + where 9N is a picce-wise linear
approximations of g. As have restricted our approximation to compact domain, all functions are Lipschitz continuous and we can bound the difference between both functions as
sup [b(x) - fN(())= sup =E|0.1]
Σ T4 +
9N
Σ 74: +
=E
sup -
( - 9N (v)
=
sup yE
Isin (2Ty) 9N
where [0, dM + 1] is the domain of and gN. As in the previous proof, we assume that gN approx- imates equidistant grid with linear regions of size A 1/(NNin 1). Similarly as before, piece-wise linear approximation inflicts the maximal error
sup (sin(2ry) gN (y)1 2 vE[0,dM+1]
sup st. 12-
(2nn(2 sin(y
sup 2.0E(0, k... |
[sin(T(( U)) cos(T(22 + +))1
sup [.]
ssn [Tz) {sin(TA)
using the addition theorem sin(a - () sin (a
3) = sin( cos(a) with <(2 y) and
= <(= y) for the first equality and assuming A v 1/2 to obtain the last equality.
(arcsin (c/(8k)))) -1 Note that Nain is always bigger than 3 so that A < / is fulfilled automatically.
follows that Na 1+
leads to sufficiently small approximation emror.
Pruning error:
The argument for the pruning error is quite similar but the error related the linear transformation a, (x) Σd OgTi + G2 is non-zero and needs be controlled as well. With AminAmuli we
can derive
sup [J((#) - Afc(=)) = sup 1gN (aN())) - Asintle (Amutri (a=) ==[o,1]a
=e(0,1]a
< sup 19N (ax(x)) - 9N ( + sup IAN (Amulua Asiage (A (x))) 00
=E(0.1]a
< LgN sup (xx(x) - a, =]
sup +E(0,dM++1
(N) Asinge())
Scmm
Stan
I Ligx Cmulti + Gsn S c/2km)
for Emulti e/(8mm)) and esin = (/4km)))))))))) where we have used that LgN 2nr, i.e., the Lipschitz constant of the function sin(2
These estimates hold reference Theorems and 3
It might seem strange that these errors do not depend on M. However, in the end, the widths of both mother neural networks does depend on M, as Theorems and 3 consider the domain and maximum value of the parameters of the functions gN and in the error assessment.
We conclude that a lottery ticket and those both parts of the neural network exist with probability at least (1 - 8) 1/2 6. 6.
25


Reviews:
[{"review_id": "tOLF8wFsvxA", "reviewer": "Reviewer_6yJz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As written in the summary above, this paper provides some novel results and intuitive ideas to show the existence of universal lottery tickets - lottery tickets which can be slightly tuned to approximate any function in a function class. However, there are two main concerns that I have:\n\n1. Looking at the theorem statements in the appendix, the parameter $N$ in Theorem 1 might be of the order $dk/\\epsilon$. In that case, the required width $n_{l,0}$ becomes super linear in $d$ and $k$, and no-longer remains logarithmic in $\\epsilon$. This would be bad, particularly since modern ML applications have huge dimension $d$.\n\n2. The paper only talks about approximating the functions in the basis $\\mathcal{B}$, whereas the more interesting case is approximating classes of functions such as Lipschitz-continuous functions. However, I think, applying this paper's results directly for that setting would lead to the classic 'curse of dimensionality', where the basis would need to contain $k=(h(1/\\epsilon))^d$ functions, where $h$ is some monotonically increasing function. While this might be unavoidable, this does put the point of universal lottery tickets into question, that is, can there exist practical, small-sized universal lottery tickets in high dimensions? \n\nNOTE: I might be missing something important here in the two points above, so the authors should feel free to correct me.\n\nOther than this, I think the main paper (first 9 pages) is not able to explain a lot of important aspects and I had to go through the appendix to understand them. One suggestion could be to just focus on one of the bases (say polynomial or fourier) in the main paper, and defer others to the appendix. This would give the readers a more direct understanding of how the construction works.", "summary_of_the_paper": "This paper proves that large enough randomly initialized ReLU networks can contain subnetworks, which can act as universal lottery tickets, that is, only by tuning the last layer of these subnetworks, they can approximate any (reasonably well-behaved) function. The paper does this by showing that large enough randomly initialized ReLU networks contain subnetworks such that their last hidden layer can act as the basis for a class of functions, and hence the output layer can simply take a linear combination of the neurons of the last hidden layer to approximate any function in that class. The paper proves this for polynomial and Fourier basis. Another key contribution of this paper is that it demonstrates that large depth can be leveraged to reduce the width needed for the strong lottery ticket hypothesis to hold.", "summary_of_the_review": "The paper provides some novel results and intuitive ideas to show the existence of universal lottery tickets, and shows that depth can be used to reduce the width required for strong lottery ticket hypothesis. However, I have some concerns regarding the required width of the network, which might limit the overall practicality of the results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JiCb7JA604Z", "reviewer": "Reviewer_rD3v", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this paper provides some interesting ideas on how to study the universal lottery ticket hypothesis. However, I think the paper may have some significant limitations.\n\nThe most important issue I find in this paper is that the results are not rigorous enough and the sparsity level of the lottery ticket is not addressed properly. This paper only has an informal theorem in the main paper, and has more detailed results in the appendix. However, after going over them, it is still not very clear to me what exactly is the sparsity level of the universal lottery ticket that is proven to exist. This is very important, as without guarantees on sufficient sparsity, one can just set the mask $B$ in Definition 2 to be all ones to use the original network as a lottery ticket of itself. Moreover, the authors set a sparsity level of 0.5 in the experiments. I feel that this may not be sparse enough. When the sparsity is just at a constant level, it seems that we can simply randomly delete a constant proportion of the neurons in each layer of the network, and then the universality of the lottery ticket can still be proved based on the universality of random feature models.\n\nTheorem 1 is also a bit confusing. According to Definition 1, if $\\lambda f_{\\epsilon}$ is strongly universal, isn’t $f_{\\epsilon}$ also strongly universal? If this is the case, it seems pointless to introduce $\\lambda$. \n\nThe result of this paper is also a bit incremental, as it is mainly a combination of known results on using polynomial/Fourier bases to approximate smooth functions and using neural networks to approximate polynomial/Fourier bases.\n\nIn terms of the presentation of the results, the authors may consider presenting formal theorems in the main paper, and add discussions to justify the results.", "summary_of_the_paper": "This paper gives proof of the existence of universal lottery tickets. Specifically, a definition of universal lottery tickets is proposed, and then proved based on functions approximation results for polynomials, Fourier series using neural networks. \n", "summary_of_the_review": "For the reasons listed above, I think the current paper needs some further improvement. Therefore I would like to recommend rejection.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BOhUTBn2NPV", "reviewer": "Reviewer_TK28", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall this paper is technically sound and well organized. Besides, my comments are as follows:\n\n---\n\nBy looking at Theorem 1, it seems that the major contribution compared to existing works (in terms of the theoretical results) is that this paper does not require the mother network to have depth $2L$ to approximate the target network with depth $L$, but could be of any depth, at the price of using more neurons per-layer. Could you elaborate on this? It would be better to clarify this technical difference in the introduction.\n\n---\n\nBesides, theorem 1 states that the universal approximation is taken with respect to the function family $F(B)$. But as claimed by the authors, functions in $F(B)$ are not exactly the target neural network function $f$. There seemly has a gap since the lottery ticket hypothesis states that a larger network with pruning can approximate a smaller network. Perhaps the authors state this approximation results with respect to the target network somewhere, but it could be much better if you can directly highlight that as a theorem or corollary.\n\n---\n\nCould you also specifically show the case when the mother network has a smaller depth in the main section? This case is rather interesting to me since existing works cannot cover it.\n\n---\n\nI do not quite get the illustration in Figure 1. It seems that the authors want to show how to develop an architecture to approximate a monomial. However, as stated on page 4, g(x) and h(x) are exponential and logarithmic functions, which I am not clear how to use FC-net and Conv-net to approximate (where we only have linear transformation and ReLU activation).\n", "summary_of_the_paper": "This paper develops a theory to explain the lottery ticket hypothesis based on extensions of subset-sum results and a strategy to leverage higher amounts of depth. The developed proof could be of independent interest since it leverages the power of depth and improves the existing bounds.", "summary_of_the_review": "The authors may need to carefully address my concerns and questions, or I am not sure whether this paper is of good quality or sufficient importance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9_2yPgaE6R", "reviewer": "Reviewer_y2DU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think the paper is well written and studies an interesting direction. However, my main concern is the significance of the result.\n\nAs shown in Theorem 1, the number of neurons is linearly proportional to the number of base functions |B|. Such linear seems to make the result a bit trivial than expected. Specifically, I feel the theory is essentially doing the following thing:\n1. Given a set of base functions, for each function, we prune a randomly initialized network for approximation.\n2. We then concatenate all the randomly pruned networks together (allowing no interaction between those networks in each layer), which gives the universal lottery ticket network.\n\nI didn’t dig into the details of the proof but I think following the above strategy we will end up with the same rate shown in this paper with a linear dependency on k. \nOverall, it seems this paper utilizes the above way for construction with additional effort to deal with the scaling issue, which is not difficult. ", "summary_of_the_paper": "This paper studies the existence of universal lottery tickets, a stronger version of lottery tickets that allows transfer learning.\nThe key idea is to show that, by pruning a network, we are able to approximate a finite set of universal base functions.\n", "summary_of_the_review": "Overall, I think this paper studies an interesting direction. However, due to some concerns on the significance of the result, I am not sure whether the result is above the acceptance bar of ICLR. I currently lean to give a weak rejection but I am happy to adjust the score based on the authors' response.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period. The current consensus suggests the paper be accepted, but could have another round of revisions before it gets published

- Definition of sparsity within theoretical results + clarity of results. This seems to be the main concern by one of the reviewers. 
- The reviewers acknowledged that some of the concerns raised could be found somewhere in the appendix, which raises further the concern of the presentation of the results: reviewers suggest a more focused and proper dissemination of the results (main theorems in main text + explanation of the results obtained, etc), which requires another round of revisions and reviewing. 

Best AC
Decision: Accept (Poster)