Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proves for the convolutional neural networks (CNNs) the strong Lottery Ticket Hypothesis, which previously is brought out based on empirical findings that a substantially overparameterized random neural network (with fully connected layers or convolutional layers) can be pruned to match the performance of a well-trained smaller network, even without training the remaining parameters. The main theorem states that a CNN with any given weights can be approximated well with high probability with a larger CNN with a doubled number of layers and a logarithmic number of parameters, and a proper pruning mask on random weights.
main_review: This paper is an extension of previous theoretical results on SLTH from fully connected layers to convolutional layers. The proving technique is similar to that used in Malach et al. (2020) and Pensia et al. (2020). While I am a LTH practitioner, I am not very familiar with LTH and SLTH theory and hence I am not sure how significant the technical contribution it is to extend the theoretical analysis from Malach et al. (2020) and Pensia et al. (2020) and whether it suffices to reach the bar of this venue.

The paper is well written and easy to follow. I roughly went through the mathematical proofs and found no issue. The main theorem is well supported by the empirical experiments.
summary_of_the_review: Overall, this work fills the gap between the empirical success of SLTH in CNNs and the lack of theoretical interpretation. However, the review is not sure if the technical contribution is significant enough compared to previous theoretical work on neural networks with fully connected layers.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The Strong Lottery Ticket Hypothesis (SLTH) says that any (sufficiently large) randomly initialized network can be pruned to obtain a network which performs well on a given task. This paper proves the Strong Lottery Ticket Hypothesis for convolutional neural networks by showing that given a target convolutional network, a logarithmically wider and twice deeper randomly initialized network can be pruned to approximate it. 
main_review: This paper proves the STLH for convolutional neural networks (CNNs). The existing papers have all focused on proving the SLTH for fully connected networks, so this paper fills the gap by proving that SLTH also holds for convolutional networks. The overparameterization required is logarithmic in the approximation error and the network depth and number of parameters, which matches the existing results for fully connected networks by Pensia et al. (2020). The importance of this result is that this proves that (sufficiently large) randomly initialized CNNs can be 'trained' solely by pruning, without actually updating the weights of the CNN.

The proof technique and construction uses the Subset Sum approach, similar to Pensia et al. (2020), and overall the paper is well written.

I have the following questions:
1. It is not clear to me why the negative input situation cannot be handled similar to prior work. Even if the same kernel is applied to multiple inputs, as long as the kernel is well approximated, the outputs will also be well approximated, respectively for each input. Could the authors please provide some more explanation or an example?

2. The theorem and lemma statements say "... we can choose constant $C$ independently from other parameters ...". Does this mean that $C$ is a universal constant?

Typos:
In the Limitations paragraph on page 5, it should be $a=\sigma(a)-\sigma(-a)$ instead of $a=\sigma(a)-\sigma(a)$.
summary_of_the_review: The paper fills an important gap in existing research by proving that the Strong Lottery Ticket Hypothesis holds for Convolutional Neural Networks with only logarithmic overparameterization. However, the proof and construction is very similar to that in Malach et al. (2020) and Pensia et al. (2020), and hence the technical novelty in terms of proof techniques could be considered incremental.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The lottery ticket hypothesis is proven for 2-dimensional convolutional network layers and positive inputs. It is shown that a given convolutional neural network can be approximated by pruning a randomly initialised larger network of two times the depth of the target network and width that is larger by a logarithmic factor.

main_review: Strengths:
+ Convolutional layers are a frequently used building block in lottery ticket pruning. Related theoretical results have the potential to explain the empirical success in this area and derive conditions that enable pruning.
+ The paper is well written and explains all steps carefully.

Weaknesses:
- The proof only applies to positive inputs. This is a significant limitation, since neural ReLU networks can often be only successfully trained if the input is standardised and thus transformed to a range [-a,a]^n for a > 0. 
- The parameter initialisation is unrealistic (iid from Unif([-1,1])) and does therefore not reflect the standard setting, in which pruning is conducted or neural networks are trained.
- The proof ideas are not novel. They main steps follow the work by Pensia et al. for fully connected layers with the simplification that only positive inputs are considered.
- The purpose of the experiments is unclear. It has been shown before that the subset sum approximation can be solved with roughly n=30 samples per parameter. This is not a new insight.
No neural networks are trained or actually pruned in the process. Why wouldn't the authors at least use the pruning algorithm edge-popup to show that they can approximate a target network?
Furthermore, why don't the authors report at least the test accuracy of the final lottery ticket to show that the approximation error of the complete pruned network is not too large and that their parameter-wise approximation error is not too high?
(The answer is probably that the proof does apply to a setting (i.e. parameter initialisation and positive inputs), in which edge-popup or any other gradient based algorithm would have a chance to find lottery tickets.)

Points of minor critique and open questions:
- How much larger is the initial large network than the target network in the experiments? The 
- Why are the experiments restricted to only these small datasets (MNIST and Fashion-MNIST)? As no neural network needs to be trained, there is no strong computational overhead associated with experiments on more realistic image classification data.
- The proof is restricted to ReLU activation functions.
- The proof only applies to 2d convolutions. Extensions are reserved for a journal version.

summary_of_the_review: Because of the lack of novel theoretical ideas and the fact that the proofs are limited to positive inputs and an unrealistic parameter initialisation approach, I recommend that the paper is not accepted for publication at ICLR at this stage.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 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. 

main_review: To begin with, I appreciate the efforts made by the authors that can help people to understand the mechanism behind the LTH. I am not an expert on theory nor random subset sum, but I can grasp some sense of the proof after reading the paper. However, there is still something that confuses me and I hope the authors can help me figure them out: Given a neural network, does the authors' theorem suggest that we need to use a pruned network of two times larger before we can approximate the real output of the original one? Theorem 1 seems to indicate that a pruned neural network of depth 2l approximates the output of f, whose depth is only l. In practice, such approximation can be done by the same architecture (same depth). There is a similar question for the number of parameters, whose bound seems to be controlled by the precision of approximation. I am not sure if this is nitpicking, but they do confuse me when I try to connect this theorem with LTH.

Minor problems:
- Figure 2, V * U * X should be V * (U * X) I suppose?
- In Lemma 1, g(X) was defined but never used afterward. The same for Lemma 2.
- Assumptions are too strong as indicated by the authors. 

summary_of_the_review: My score only indicates the initial opinion and I am willing to change my score if the authors can address my concern. Currently, I cannot clearly see the connection between the theorems and the LTH, so I would give a score of 5 at this time.
review_title: null

Meta-review: The paper presents interesting new results for pruning random convolutional networks to approximate a target function. It follows a recent line of work in the topic of pruning by learning. The results are novel, and the techniques interesting. There are some technical issues that are easy to fix within the camera ready timeline (see comments of reviewers below). I would also suggest refining the title of the paper: the lottery ticket hypothesis has an algorithmic component too, which clearly is not covered by existence results.
Decision: Accept (Poster)