Year: 2021

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

heading: 1 INTRODUCTION
text: Many impressive successes in machine learning are reached through neural network architectures with a huge number of trainable parameters. Consequently, substantial research in the field aims at reducing the size of such networks while maintaining good accuracy, e.g. for deployment in resource constrained devices (Yang et al., 2017).
A major empirical fact of such endeavour is the contrast between the initial model overparametrization, which appears necessary for effective training, and the extent to which the size of the resulting model can be reduced through compression techniques. Among the latter, pruning methods appear as a mature and efficient way of achieving significant compression, often without incurring any accuracy loss (Blalock et al., 2020). Recently, the aforementioned contrast between the initial and final number of parameters has been addressed by the lottery ticket hypothesis (Frankle & Carbin, 2019), or LTH for short, which states that any randomly initialized network contains lottery tickets, that is, sparse subnetworks that can be trained just once and reach the performance of the fully-trained original network. This hypothesis was first verified experimentally, leveraging pruning methods to identify the lottery tickets (Frankle & Carbin, 2019; Lee et al., 2019).
(Ramanujan et al., 2020) then proposed a stronger version of the hypothesis, named strong lottery ticket hypothesis (SLTH) by (Pensia et al., 2020): it stipulates that a network with random weights contains, with high probability, sub-networks that can approximate any given sufficiently-smaller neural network. In other words, a sufficiently large and randomly initialized network that can be successfully trained for a task, could instead be suitably pruned to obtain a network that, even without training, achieves good accuracy. Experimental support for this stronger version were reported by Ramanujan et al. (2020); Zhou et al. (2019); Wang et al. (2020), making use of pruning methods to find lottery tickets in a range of architectures, including convolutional neural networks (CNNs). A first rigorous proof of the SLTH has been given by Malach et al. (2020) for the case of dense networks (i.e. consisting of fully connected layers). Pensia et al. (2020) and Orseau et al. (2020) successively improved this result by showing that logarithmic over-parametrization is sufficient. Their results are also restricted to dense networks and they leave as an open problem to extend it to CNNs.
Our contributions. We extend and complete the proof of the SLTH (and thus, also, of the LTH), for classical network architectures which can combine convolutional and fully connected layers. More precisely, we prove that any CNN with given weights can be approximated by pruning a CNN with random weights (random CNN for short), with the latter being larger than the former by a logarithmic factor. We also provide basic experiments showing that starting from a random CNN
which is roughly 30 times larger than LeNet5, it is possible to compute in few hours a pruning mask that allows to approximate the trained convolutional layers of LeNet5 with relative error 10−3, even when ignoring some hypothesis of our theoretical result. Our theoretical analysis follows the approach of Malach et al. (2020) and make use of two layers to approximate one. We borrow from Pensia et al. (2020) the use of random subset sum (RSS) (Lueker, 1998) to approximate a given weight via the sum of a subset of a sample of random weights, and carefully design instances of RSS via a combination of two convolutional layers. By controlling the error accumulated by each layer with Young’s convolution inequality, we establish the following result.
Informal version of Theorem 1. Given ε, δ > 0, any CNN with k parameters and ` layers, and kernels with `1 norm at most 1, can be approximated within ε by pruning a random CNN withO(k log( k`min{ε,δ} )) parameters and 2` layers with probability at least 1− δ.
This result generalizes those by Pensia et al. (2020), Orseau et al. (2020) and Malach et al. (2020), as the dense-network case is retrieved as a special case of our theorem, when the kernel size matches the input size.
Roadmap. After discussing related work in the next section, we state our theoretical results alongside a high-level idea of the proofs. Successively, we report our experimental results. Finally, in Section 4, we provide detailed proofs of our statements.

heading: 1.1 RELATED WORK
text: Pruning methods are classical neural network compression strategies that date back to the 80’s (LeCun et al., 1989b; Mozer & Smolensky, 1988). We recommend the recent survey Blalock et al. (2020) for an overview of the current state of research on these techniques.
As for the lottery ticket hypothesis, Lange (2020) provides a survey which summarizes the progress on the topic until the results by Malach et al. (2020). In the following we briefly mention works which are not discussed in Lange (2020). Cosentino et al. (2019) shows that lottery tickets can be adversarially trained, yielding sparse and robust neural networks. Soelen & Sheppard (2019) shows that lottery tickets are transferable, in the sense of showing remarkable accuracy for tasks other than the original one for which they have been found. Sabatelli et al. (2021) further shows that minimal retraining on a new task allows lottery tickets to often achieve better generalization than models trained ad-hoc for the task. (Yu et al., 2020) empirically supports that the LTH holds also in the context of reinforcement learning and natural language processing. (Diffenderfer & Kailkhura, 2021) shows that lottery tickets are also robust against extreme quantization of the weights. Aladago & Torresani (2021) provides a method to train networks where each initial weight is restricted to few possible random values.
An extreme case of the latter is to share only a single (random) value among all weights, and focus the training solely on finding the best architecture (Gaier & Ha, 2019).
Our work also relates to recent papers investigating properties of random CNNs, such as Ulyanov et al. (2020) which observes that random CNNs already seem to capture some natural image statistics required for tasks such as de-noising and inpainting.

heading: 2 THEORETICAL RESULTS
text: We start by introducing some of our notation. The rest of it follows Goodfellow et al. (2016) with minor modifications, so we defer a full description to Section 4.1.
Given n ∈ N, we denote the set {1, . . . , n} by [n]. The symbol ∗ represents the convolution operation, represents the element-wise (Hadamard) product, and σ represents ReLU activation function. Finally, the notation ‖·‖1 refers to the sum of the absolute values of each entry in a tensor while ‖·‖max denotes the maximum norm: the maximum among the absolute value of each entry. Those are akin to vector norms and should not be confused with operator norms.
We restrict our setting to convolutional neural networks f : [0, 1]D×D×c0 → RD×D×c` of the form
f(X) = K` ∗ σ(K`−1 ∗ · · ·σ(K1 ∗ X)),
where Ki ∈ Rdi×di×ci−1×ci , and the convolutions have no bias and are suitably padded with zeros. The restrictions on tensor sizes and the exclusion of bias terms1 aim only to ease presentation.
Our initial goal is to approximate a convolution with a single kernel, as depicted in Figure 1, using convolutions with (pruned) random kernels. We achieve this by the means of the structure presented in Figure 2, using two convolutions with random tensors.
Lemma 1 asserts that, with high probability, we can prune this structure to approximate the output of a convolution with any given kernel as long as the amount of kernels is large enough.
Lemma 1 (Single kernel). Let D, d, c, n ∈ N, and ε, C ∈ R>0, where n ≥ C log d 2c ε , U ∈ Rd×d×c×n, V ∈ R1×1×n×1, and S ∈ {0, 1}d×d×c×n. Let us further assume that the entries of U and V are i.i.d. random variables following a Unif([−1, 1]) distribution, and define
g(X) = V ∗ σ(U ∗ X) and gS(X) = V ∗ σ((U S) ∗ X) thus yielding a random CNN g : [0, 1]D×D×c → RD×D×1 and its pruned version gS w.r.t. the mask S.
Then, we can choose constant C independently from other parameters so that, with probability at least 1− ε, for all K ∈ [−1, 1]d×d×c×1 with ‖K‖1 ≤ 1, there exists a pruning mask S such that
sup X∈[0,1]D×D×c ∥∥K ∗ X− gS(X)∥∥max < ε. Proof idea. We leverage the absence of negative entries in the input and an initial pruning of U to bypass the ReLU non-linearity. This allows us to virtually replace the operations in g by a single
1If biases are present, the structures used in the proofs also puts them in a RSS configuration. Thus the results can be readily adapted by replacing the d2i terms by d 2 i + 1.
convolution with a random kernel obtained by combining U and V. Each entry of this resulting kernel is the sum of n random variables, where we can choose to include/exclude each term in the sum by choosing to keep/prune the relevant weights. We finish the proof by applying Theorem 2 to conclude that n variables suffice to approximate all entries, simultaneously, with enough precision to ensure the thesis.
We now extend Lemma 1 to an entire layer. As before, a detailed proof is provided in Section 4.3. Lemma 2 (Convolutional Layer). Let D, d, c0, c1, n ∈ N, and ε, C ∈ R>0, where n ≥ C c1 log d2c0c1 ε , U ∈ Rd×d×c0×n, V ∈ R1×1×n×c1 , S ∈ {0, 1}d×d×c0×n and T ∈ {0, 1}1×1×[n]×[c1]. Let us further assume that the entries of U and V are i.i.d. random variables following a Unif([−1, 1]) distribution, and define
g(X) = V ∗ σ(U ∗ X) and gT,S(X) = (V T) ∗ σ((U S) ∗ X) thus yielding a random CNN g : [0, 1]D×D×c0 → RD×D×c1 and its pruned version gT,S(X) w.r.t. the masks S and T.
Then, we can choose constant C independently from other parameters so that, with probability at least 1− ε, for all K ∈ [−1, 1]d×d×c0×c1 with ‖K‖1 ≤ 1, there exist masks S and T such that
sup X∈[0,1]D×D×c0
‖K ∗ X− gT,S(X)‖max < ε.
Proof Idea. The lemma follows by applying Lemma 1 to each kernel independently, so that all of them are approximated by a factor at most εc1 ; the latter approximation allows to apply the union bound so that the desired approximation holds simultaneously for all c1 output kernels with probability at least 1− ε.
We are now ready to extend the previous approximation result from a single layer to the entire network, thus proving our main result. A detailed proof is given in Section B. Theorem 1 (Convolutional Network). Let D, d, c0, c1, ` ∈ N, and ε, C ∈ R>0. For each i ∈ [`], let L2i−1 and L2i be tensors with size di × di × ci−1 × (Cci log ci−1cid 2 i `
min{ε,δ} ) and 1 × 1 × (Cci log ci−1d 2 i ci` min{ε,δ} )×ci, respectively. Furthermore, for each i ∈ [2`], let S i ∈ {0, 1}size(Li). Finally, let us assume that the entries of L1, ...,L2` are i.i.d. random variables following a Unif([−1, 1]) distribution, and define
g(X) = L2` ∗ σ(L2`−1 ∗ · · ·σ(L1 ∗ X)) and gS1,...,S2`(X) = (L 2` S2`) ∗ σ[(L2`−1 S2`−1) ∗ · · ·σ[(L1 S1) ∗ X]]
thus yielding a random 2`-layer CNN g : [0, 1]D×D×c0 → RD×D×c1 and its pruned version gS1,...,S2`(X) w.r.t. masks S 1, ...,S2`.
Let F be the class of functions from [0, 1]D×D×c0 to RD×D×c` such that, for each f ∈ F f(X) = K` ∗ σ(K`−1 ∗ · · ·σ(K1 ∗ X)),
where, for each i ∈ [`], Ki ∈ [−1, 1]di×di×ci−1×ci and ‖Ki‖1 ≤ 1. Then, we can choose constant C independently from other parameters so that, with probability at least 1− δ, the following holds for every f ∈ F:
inf ∀i∈[2`],Si∈{0,1}size(Li) sup X∈[0,1]D×D×c0 ∥∥∥f(X)− gS1,...,S2`(X)∥∥∥ max < ε.
Proof Idea. The proof leverages Lemma 2 in an analogous way to how the latter relied on Lemma 1; namely, we apply Lemma 2 by requiring an approximation factor that guarantees, with sufficient probability, that a suitable approximation is reached across all layers simultaneously. The latter requirement is responsible for the ` factor which appears in the logarithms of the dimensions of each random tensor Li.

heading: 2.1 DISCUSSION ON THEOREM 1
text: Size analysis. For each layer, we emulate a 4-D kernel K with size di×di×ci−1×ci with two 4-D kernels U and V with size di×di×ci−1×n and 1×1×n×ci respectively with n = Cci log ci−1cid 2 i `
min{ε,δ} . Under the technical assumption ci = O(d2i ci−1) for i ∈ [`], the size of V is within a constant factor of that of U, and the size of the whole random network we prune has size O(k log k`min{ε,δ} ) where k is the size of the network we want to approximate. Note that this technical assumption is met for all classical convolutional networks used for image processing with a reasonably small constant in the big O notation. We come back on this assumption below.
Limitations. The properties of convolutional layers require stronger hypotheses in Theorem 1 when compared with the results for dense layers Malach et al. (2020) or Pensia et al. (2020). First, we require non-negative inputs for all layers, however, since the output of the ReLU function is never negative, this restriction is only relevant for the input of the first layer. The mentioned works avoid this restriction by exploiting the identity a = σ(a) − σ(−a) to deal separately with the positive and negative entries. The fact that each entry of the output of a convolution is affected by potentially multiple input entries prevents us from employing a similar strategy. Nonetheless, we remark that, while this is a relevant theoretical indication of the challenges imposed by the operation of convolution, in practice the inclusion of biases suffices to easily convert any CNN with a domain including negative values into an equivalent CNN that takes only non-negative inputs. Finally, the possibly multidimensional entries of convolutions also motivates the restriction on the norm of the target weight tensors in terms of the 1-norm.
Generalizations. For the sake of simplicity, we state and prove Theorem 1 in a restricted setting. It is worth remarking a series of generalizations that can be obtained at the mere cost of making the proofs more technically involved. We defer a more complete treatment of such extensions to a journal version of this work. First, the proof could consider also other parameters, such as stride, padding, average pooling and other operations that can be seen as convolutions. Moreover, we could consider more general convolutions, not necessarily 2-D, operating on tensors of any sufficiently large dimension. In particular, it is not necessary to assume that V has size 1×1×n×ci in the above analysis. Using a 5-D tensor with size d× d× ci−1× (n/ci)× c1 for U, an appropriate convolution U ∗ X would result in a D × D × (n/ci) × ci tensor, and we could use a 1 × 1 × (n/ci) × ci tensor for V without the need for mask T by performing in parallel ci appropriate convolutions. Note that the size of V is then smaller than the size of U. The technical assumption used in the above size analysis is thus not necessary to guarantee that logarithmic over-parametrization is sufficient. Finally, observe that that our results generalize to any probability distribution for the weights that contains a b-scaled Unif([−a, a]) for some constant a > 0 (in the sense of Definition 2 in Section C), where the parameters a and b only impact the constants in the theorem.

heading: 3 EXPERIMENTS
text: As networks with higher parameter counts tend to be more robust to noise, we stick to the small CNN architecture used by Pensia et al. (2020), namely LeNet5 (LeCun et al., 1989a). We conduct our experiments by first training a LeNet5 with ReLU activations to 98.99% test accuracy on MNIST dataset (Lecun et al., 1998) and, to avoid well-known limitations of the MNIST dataset (in particular its large number of zero entries), we also trained it on the Fashion-MNIST dataset (Xiao et al., 2017) to 89.12% test accuracy. We adopted Kaiming Uniform (He et al., 2015) for weight initialization, a batch size of 64 and trained for 50 epochs using ADAM optimizer (Kingma & Ba, 2015) with learning rate of 0.001, exponential decay of 0.9 and momentum estimate of 0.999, the default values in Flux.jl (Innes et al., 2018) machine learning library.
Once the network is trained we change its weights for a random subset sum approximation of them. More precisely, for each weight w we sample x from Unif([−1, 1]n) and use Gurobi optimization software (Gurobi Optimization, LLC, 2021) to solve the mixed-integer program
min a1,...,an ∣∣∣w − n∑ i=1 ai · xi ∣∣∣ s.t. ai ∈ {0, 1} ∀i ∈ [n],
where n is the sample size. Solving this subset sum problem with n = 30 for the 2572 parameters in the convolutional layers of LetNet takes around 1 hour on 32 cores of a Intel® Xeon® Gold 6240 CPU @ 2.60GHz.
Figure 3 shows the accuracy of the approximation for different sample sizes. We start to obtain good approximations (error smaller than 10−2) from sample sizes around 15-20. Also, when comparing to the weights obtained for MNIST and for Fashion-MNIST, we have better approximations for the smaller sample sizes for MNIST. We believe this is due to the fact that the training on FashionMNIST resulted in filters with larger weights (up to a factor 2, roughly), since a larger sample size is necessary to approximate a larger interval of values (see the statement of Lueker (1998, Corollary 3.3) in Appendix C).
The high precision in the approximation of most weights leads to negligible change in the accuracy of the network. For this reason, we focus on studying the error at the output of the convolutional section of LeNet5, right before the flattening. Also, at this point the activation tensor has dimension 7× 7× 16 as opposed to the vector of size 10 at the end of LeNet5.
Figure 4 shows the maximum relative error for all approximated outputs compared to original ones. The relative error of the output for an input image is computed as the maximum activation error divided by the maximum original activation (both maxima are taken over all 7× 7× 16 activations). Once again, MNIST leads to better precision for the smaller sample sizes. This can be explained by the fact that weights are better approximated in that range with MNIST as seen in Figure 3. In both cases, we get a relative error close to 10−3 with sample size 20, and even better with larger sample sizes. Within the settings of Theorem 1, this corresponds to expanding the convolutional portion of the network by a factor of, roughly, 30 if we take into account kernel sizes and number of channels. Note that this high precision is achieved even though the trained weights do not satisfy the norm restrictions of Theorem 1. Indeed, as we do not use any explicit regularization, the 1-norms of the kernels obtained are quite high (from 50 to 15000 roughly for both datasets).

heading: 4 TECHNICAL ANALYSIS

heading: 4.1 NOTATION AND CONVENTIONS
text: We employ the notation from Goodfellow et al. (2016) with minor adjustments. For selfcontainment, we detail below not only our adaptations but all the relevant notation inherited from the textbook.
We identify the type of the objects with the font used for their symbols. This applies to scalars (e.g. x), to vectors (e.g. x) and its entries (e.g. xi), to tensors (e.g. X) and its entries (e.g. Xi,j,k), and to sets (e.g. X). We denote slices of tensors by indexing it with colons. For example, the expression X:,:,i represents a 2-D slice of a 3-D tensor. Finally, we refer to the axis of a 4-D tensors as rows, columns, channels, and kernels (a.k.a. filters), in this order.2
This work considers explicitly only 2-dimensional convolutions with multiple channels, multiple kernels and enough zero-padding to preserve the output size. However, as we discuss in Section 2.1, our results can be generalized in many ways. Definition 1 (Convolution). Given tensors K ∈ Rd×d×c and X ∈ RD×D×c, the 2-dimensional discrete convolution between K and X is the D ×D matrix with entries given by
(K ∗ X)i,j = ∑
i′,j′,k∈[d]×[d]×[c]
Ki′,j′,k · Xi−i′+1,j−j′+1,k for i, j ∈ [D]× [D].
where X is suitably zero-padded. Similarly, if K ∈ Rd×d×c0×c1 is a 4-dimensional tensor, we define K ∗ X as the D ×D × c1 tensor with entries
(K ∗ X)i,j,` = ∑
i′,j′,k∈[d]×[d]×[c]
Ki′,j′,k,` · Xi−i′+1,j−j′+1,k for i, j, ` ∈ [D]× [D]× [c1].
Notice that the output of a convolution with a 4-D kernel can also be can be expressed in terms of the 3-D case using tensor slices. For instance, the last equality in the previous definition can be rephrased as
(K ∗ X):,:,` = K:,:,:,` ∗ X for ` ∈ [c1].

heading: 4.2 SINGLE KERNEL APPROXIMATION (PROOF OF LEMMA 1)
text: Our first goal is to bypass the non-linearity so we can combine the two convolutions in g(X) = V ∗ σ(U ∗ X) into a single one. Given that the activation function under consideration is the ReLU, it suffices to ensure that its input has no negative entry. Hence, we prune all negative entries of U, obtaining the tensor U+ = max{0,U}, where the maximum is applied entry-wise. Since, by hypothesis, the entries of the input X are non-negative, it follows that the entries of the tensor U+ ∗ X are also non-negative. Therefore,
V ∗ σ(U+ ∗ X) = V ∗ (U+ ∗ X). (1)
We now look at the first convolution on the right side of Equation 1. By Definition (1), we have [V ∗ (U+ ∗ X)]r,s,1 = n∑ t=1 V1,1,t,1 · (U+ ∗ X)r,s,t
= n∑ t=1 V1,1,t,1 · ( ∑ i,j,k∈[d]×[d]×[c] U+i,j,k,t · Xr−i+1,s−j+1,k )
= n∑ t=1 ∑ i,j,k∈[d]×[d]×[c] ( V1,1,t,1 · U+i,j,k,t ) · Xr−i+1,s−j+1,k = ∑
i,j,k∈[d]×[d]×[c] ( n∑ t=1 V1,1,t,1 · U+i,j,k,t ) · Xr−i+1,s−j+1,k.
2Goodfellow et al. (2016) uses a different ordering.
The equation above shows that performing V ∗ (U+ ∗X) is equivalent to performing a single convolution between X and a tensor L ∈ Rd×d×c×1 whose coordinates are given by
Li,j,k,1 = n∑ t=1 V1,1,t,1 · U+i,j,k,t. (2)
This reveals a RSS configuration where we can choose to include/exclude each value V1,1,t,1 ·U+i,j,k,t in the sum by choosing to keep/prune U+i,j,k,t. Since Equation 1 continues to hold after further pruning U+, we finish our proof by doing exactly that: we leverage Theorem 2 to ensure that, with high probability, we can solve this RSS problem for each entry of L to approximate the respective entry of K.
To see that we can apply Theorem 2 in this setting, for ε′ > 0, i, j ∈ [d], and k ∈ [c], define the event Ei,j,k,ε′ to be the event{
∀z ∈ [−1, 1], ∃S ⊆ [n] : ∣∣∣z −∑
t∈S V1,1,t,1 · U+i,j,k,t ∣∣∣ < ε′}. We now use the RSS result Lueker (1998, Corollary 3.3) (Theorem 2 in Section C) to show that there exists constants a, b such that
E ( max
z∈[−n/32,n/32] min S⊆[n] ∣∣∣z −∑ t∈S V1,1,t,1 · U+i,j,k,t ∣∣∣) ≤ ae−bn.
It is not hard to show that, since (V1,1,t,1)1≤t≤n and (U+i,j,k,t)1≤t≤n are i.i.d. Unif([−1, 1]) random variables, then the value of the density of (V1,1,t,1 · U+i,j,k,t)1≤t≤n is at least log 22 on [−1/2, 1/2], and it thus contains a log 22 -scaled Unif([−1/2, 1/2]) (see Lemma 3 in Section C for details). In particular, setting X = V1,1,t,1 · U+i,j,k,t, we have that µ− = E(1X≤0X) ≤ − log 28 < −1/16 and µ+ = E(1X>0X) ≥ log 2 8 > 1/16. We can thus apply Theorem 2 with ξ = 1/32: there exist constants a, b > 0 such that the expected value of the [−n/32, n/32]-subset-sum gap for (V1,1,t,1 · U+i,j,k,t)1≤t≤n is at most ae−bn, that is E ( maxz∈[−n/32,n/32] minS⊆[n]
∣∣∣z −∑t∈S V1,1,t,1 · U+i,j,k,t∣∣∣) ≤ ae−bn. Assuming n ≥ 32, Markov’s inequality yields P(Ei,j,k,ε′) ≤ ae −bn ε′ . Setting ε ′ = εd2c and C = 2 b + log a b , and supposing w.l.o.g. ε
′ < e−1, the condition n ≥ C log 1ε′ implies bn ≥ 2 log ε′+log a and ae −bn
ε′ < ε ′, and we get
P ( Ei,j,k, ε
d2c
) ≥ 1− ε
d2c .
Now define the simultaneous event Eε′ = ⋂ i,j,k Ei,j,k,ε′ . By a union bound over the inequality above for i, j ∈ [d], k ∈ [c], we have
P ( E ε
d2c
) ≥ 1− ε.
Finally, conditioning on E ε d2c , it holds that
sup K∈[0,1]d×d×1×1 inf S∈{0,1}d×d×1×n sup X∈[0,1]D×D×1
∥∥K ∗ X− V ∗ σ[(U S) ∗ X]∥∥ max
(a) = sup
K inf S sup X
∥∥K ∗ X− V ∗ (U+ S) ∗ X∥∥ max
(b) = sup
K inf S sup X
∥∥[K− V ∗ (U+ S)] ∗ X∥∥ max
(c) ≤ sup K inf S sup X
(∥∥K− V ∗ (U+ S)∥∥ 1 · ‖X‖max ) (d) ≤ sup K inf S ∥∥K− V ∗ (U+ S)∥∥ 1
(e) ≤ d2c · sup K inf S
∥∥K− V ∗ (U+ S)∥∥ max
(f) ≤ d2c ε d2c = ε,
where (a) follows from Equation 1, (b) from the distributivity of the convolution operation, (c) from Proposition 1, (d) from the fact that X ∈ [0, 1]D×D×1, (e) from the inequality ‖x‖1 ≤ m‖x‖max for x ∈ Rm, and (f) from the definition of E ε
cd2 .

heading: 4.3 CONVOLUTIONAL LAYER APPROXIMATION (PROOF OF LEMMA 2)
text: Our goal is to approximate K ∗ X with (V T) ∗ σ[(U S) ∗ X] where T and S are binary masks.
For ` ∈ [c1] let K(`) be K’s `-th kernel. That is, K(`) = K:,:,:,`.
Notice that K ∗ X is the concatenation along the third dimension of each K(`) ∗ X: for ` ∈ [c1], we have (K ∗ X):,:,` = K(`) ∗ X. We fix T a priori to be the block diagonal matrix B with entries given by B1,1,t,` = 1(`−1)n′<t≤`n′ for t, ` ∈ [n]× [c1], where n′ = n/c1. In the rest of the proof, we show how to choose S, based on U and V, in order to approximate the kernels K(`).
We perform the approximation of each K(`) using different sections of the tensors. To this end, for ` ∈ [c1], let
U` = U:,:,:,(`−1)n′<t≤`n′ , S ` = S:,:,:,(`−1)n′<t≤`n′ , and V ` = V:,:,(`−1)n′<t≤`n′,:. As we did in the proof of Lemma 1, we perform an initial pruning on U by restricting S to the space of masks that prune all of its negative entries. This allows us to ignore the ReLU activation and conclude that
((V B) ∗ σ[(U S) ∗ X])r,s,` = ∑ (`−1)n′<t≤`n′ V1,1,t,` ∑ i,j,k∈[d]×[d]×[c] (U S)i,j,k,t · Xr−i+1,s−j+1,k
= ( V` ∗ [(U` S`) ∗ X] ) r,s
= ( V` ∗ σ[(U` S`) ∗ X] ) r,s .
For ` ∈ [c1] and ε′ > 0, define the event E`,ε′ to be the event{ sup
K(`)∈[−1,1]d×d×c0×1 inf S`∈{0,1}d×d×c0×n′ sup X∈[0,1]D×D×c0 ∥∥∥K(`) ∗X−V` ∗σ[(U` S`)∗X]∥∥∥ max < ε′ } .
Now define the event Eε′ = ⋂ `E`,ε′ and consider the event Eε/c1 . Since n ′ = n/c1 = C log d2c0 ε/c1
, for each ` ∈ [c1], thanks to Lemma 1 we have P(E`,ε/c1) ≥ 1 − ε/c1, which implies P(Eε/c1) ≥ 1− ε. Finally, conditioning on Eε/c1 and using the fact that the output channels of a convolutional layer are calculated independently, we conclude
sup K∈[−1,1]d×d×c0×c1 inf S∈{0,1}d×d×c0×n
T∈{0,1}1×1×n×c1
sup X∈[0,1]D×D×c0 ∥∥∥K ∗ X− (V T) ∗ σ[(U S) ∗ X]∥∥∥ max
≤ sup K∈[−1,1]d×d×c0×c1 inf S∈{0,1}d×d×c0×n sup X∈[0,1]D×D×c0 ∥∥∥K ∗ X− (V B) ∗ σ[(U S) ∗ X]∥∥∥ max
= max `∈[c1] sup K(`)∈[−1,1]d×d×c0 inf S`∈{0,1}d×d×c0×n′ sup X∈[0,1]D×D×c0 ∥∥∥K(`) ∗ X− V` ∗ σ[(U` S`) ∗ X]∥∥∥ max
< ε.

heading: 5 REPRODUCIBILITY STATEMENT
text: We made our best effort to describe in detail all the relevant parameters for Section 3. We also took care to initialize the random number generator not only for Julia but also for Gurobi, so that the experiments can be reproduced using the source code available at https://shared03. opsone-cloud.ch/index.php/s/mWPK8AMRrrdJr8E. The latter also include a BSON serialized version of our trained models and solutions to RSS instances, that can readily be imported with Julia.

heading: A BOUND ON THE NORM OF A CONVOLUTION
text: The following proposition can be seen as a special case of Young’s Convolution Inequality for functions over Zn where the norms in the inequality are the `1 and `∞ norms. Proposition 1 (Tensor Convolution Inequality). Given K ∈ Rd×d×c0×c1 and X ∈ RD×D×c0 , we have
‖K ∗ X‖max ≤ ‖K‖1 · ‖X‖max.
Proof. We have
‖K ∗ X‖max ≤ max i,j,`∈[D]×[D]×[c1] ∑ i′,j′,k∈[d]×[d]×[c] ∣∣Ki′,j′,k,`Xi−i′+1,j−j′+1,k∣∣ ≤ max
i,j,` ∑ i′,j′,k ∣∣Ki′,j′,k,`∣∣‖X‖max ≤ max
i,j,` ( ∑ i′,j′,k |Ki′,j′,k,`| ) ‖X‖max
≤ max i,j,` ‖K‖1‖X‖max = ‖K‖1 · ‖X‖max.

heading: B CNN APPROXIMATION (PROOF OF THEOREM 1)
text: Since Lemma 2 provide bounds in terms of the output of a layer, the study of the propagation of this error through the network is mostly independent of the layer type. Hence, the next proof follows the structure of Pensia et al. (2020, Theorem 1), where our Lemma 2 assumes the role of their Lemma 3, and where we leverage our Proposition 1 in order to address the problem of bounding the maximum norm of a convolution.
Proof (of Theorem 1). For the sake of brevity, in the proof we denote the max-norm simply by ‖·‖. Let Xi be the input of the i-th layer of the network f . Thus,
1. X1 = X,
2. Xi+1 = σ(Ki ∗ Xi) for 1 ≤ i ≤ `− 1 and
3. f(X) = K` ∗ X`.
By applying Lemma 2 to each layer, we choose masks S2i and S2i−1 so that
sup X ∥∥∥Ki ∗ X− (L2i S2i) ∗ σ[(L2i−1 S2i−1) ∗ X]∥∥∥ < ε 2`
(3)
with probability at least 1− ε2` . Since the ReLU function is 1-Lipschitz with respect to the max norm, the above event implies the following for all i ∈ [`− 1]:
sup X ∥∥∥σ(Ki ∗ X)− σ[(L2i S2i) ∗ σ[(L2i−1 S2i−1) ∗ X]]∥∥∥ < ε 2` . (4)
By a union bound, with probability 1 − ε, Equation 3 and Equation 4 hold for all layers simultaneously. In the rest of the proof, we implicitly condition on the latter event.
For any fixed function f , let g be the pruned network constructed layer-wise, by pruning with binary masks which satisfy Equation 3 and Equation 4. Let these pruned tensors be L̃ i , and let X̃ i be the input to the (2i− 1)-th layer of g.
We note that X̃ i satisfies the the recurrence relation
1. X̃ 1 = X,
2. X̃ i+1 = σ(L̃ 2i ∗ σ(L̃2i−1 ∗ Xi)) for 1 ≤ i ≤ `− 1.
Because ‖X‖ ≤ 1, Equation 4 implies that ‖X̃i‖ ≤ ( 1 + ε2` )i−1 . To see this, note that Equation 4 implies, for 1 ≤ i ≤ `− 1, ∥∥∥σ(Ki ∗ X̃i) ‖X̃i‖ − X̃ i+1 ‖X̃i‖ ∥∥∥ ≤ ε 2` ,
thus ‖σ(Ki ∗ X̃i)− X̃i+1‖ ≤ ε
2` ‖X̃i‖.
By the reverse triangle inequality, the last inequality implies
‖X̃i+1‖ ≤ ε 2` ‖X̃i‖+ ‖σ(Ki ∗ X̃i)‖
≤ ε 2` ‖X̃i‖+ ‖Ki ∗ X̃i‖ ≤ ε 2` ‖X̃i‖+ ‖Ki‖1 · ‖X̃ i‖ ≤ ε 2` ‖X̃i‖+ ‖X̃i‖
≤ ( 1 + ε
2`
) ‖X̃i‖.
Applying this inequality recursively, we get that ‖X̃i‖ ≤ ( 1+ ε2` )i−1 for 1 ≤ i ≤ `−1. This allows us to bound the error between Xi and X̃ i . For 1 ≤ i ≤ `− 1, we have
‖Xi+1 − X̃i+1‖ = ‖σ(Ki ∗ Xi)− σ(L̃2i ∗ σ(L̃2i−1 ∗ X̃i))‖ ≤ ‖σ(Ki ∗ Xi)− σ(Ki ∗ X̃i)‖+ ‖σ(Ki ∗ X̃i)− σ(L̃2i ∗ σ(L̃2i−1 ∗ X̃i))‖ ≤ ‖Ki‖1‖Xi − X̃
i‖+ ‖σ(Ki ∗ X̃i)− σ(L̃2i ∗ σ(L̃2i−1 ∗ X̃i))‖ ≤ ‖Xi − X̃i‖+ ‖σ(Ki ∗ X̃i)− σ(L̃2i ∗ σ(L̃2i−1 ∗ X̃i))‖
≤ ‖Xi − X̃i‖+ ( 1 + ε
2` )i−1 ε 2` , (5)
where for the last inequality we use Equation 3. Unrolling Equation 5 we get
‖X` − X̃`‖ ≤ `−1∑ i=1 ( 1 + ε 2` )i−1 ε 2` .
Finally, this last inequality leads, with probability at least 1− ε, to ‖f(X)− g(X)‖ = ‖K` ∗ X` − L̃2` ∗ σ(L̃2`−1 ∗ X̃`)‖
≤ ‖K` ∗ X` − K` ∗ X̃`‖+ ‖K` ∗ X̃` − L̃2` ∗ σ(L̃2`−1 ∗ X̃`)‖ ≤ ‖K`‖1‖X` − X̃
`‖+ ‖K` ∗ X̃` − L̃2` ∗ σ(L̃2`−1 ∗ X̃`)‖ ≤ ‖X` − X̃`‖+ ‖K` ∗ X̃` − L̃2` ∗ σ(L̃2`−1 ∗ X̃`)‖
≤ ‖X` − X̃`‖+ ( 1 + ε
2` )`−1 ε 2`
≤ ( `−1∑ i=1 ( 1 + ε 2` )i−1 ε 2` ) + ( 1 + ε 2` )`−1 ε 2`
≤ ∑̀ i=1 ( 1 + ε 2` )i−1 ε 2`
= ( 1 + ε
2`
)` − 1
< eε/2 − 1 < ε,
where the last inequality holds because ε < 1.
Replacing ε in this proof with min{ε, δ} concludes the proof of the theorem.

heading: C RANDOM SUBSET-SUM THEOREM
text: For the sake of completeness, in this section we recall a result by Lueker (1998) together with the necessary definitions. Definition 2. Given two positive constants a and b, we say that a distribution with density f contains a b-scaled Unif([−a, a]) distribution if for each x ∈ [−a, a] it holds f(x) ≥ b. We simply say that a distribution F contains a uniform distribution if there exist positive constants a and b such that F contains a b-scaled Unif([−a, a]) distribution.
The following is a weaker version of Corollary 1 in the Appendix of Pensia et al. (2020). Lemma 3. Let X1 and X2 be two independent random variables following a Unif([−1, 1]) distribution. Then X1 ·X2 contains a log 22 -scaled Unif([− 12 , 12 ]) distribution. We say that z is 2η-subsetsum-approximated with S = {X1, ..., Xn} if there exists a subset Iz ⊆ [n] s.t. |∑i∈Iz Xi − z| ≤ 2η. Definition 3. The [a, b]-subset-sum gap of S = {X1, ..., Xn} is the smallest value of η such that each z ∈ [a, b], can be 2η-subsetsum-approximated with S. Theorem 2 (Corollary 3.3 in Lueker (1998)). Let S = {X1, ..., Xn} be n i.i.d. bounded random variables and ξ > 0 any constant. Suppose that the distribution of X1 contains a uniform distribution. Let µ− = E[1X≤0X], µ+ = E[1X≥0X], µabs = E[|X|] = µ+ − µ−. The expected value of the [(µ− + ξ)n, (µ+ − ξ)n]-subset-sum gap of S is exponentially small w.r.t. n.

Review summaries:
The authors provide theoretical analysis on the lottery ticket hypothesis for convolutional neural networks. The techniques of the random subset sum are used to prove theorems. The authors start with introducing the case of a single convolutional kernel and then generalize to the case of the whole convolutional neural networks. By specifying multiple constraints and assumptions on the models' parameters and inputs, the error between the approximated and the true convolution results can be limited to a small number.