Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the Strong Lottery Ticket Hypothesis (SLTH) for non-ReLU activation functions, just as its title implies. Previous theoretical works have advanced the SLTH in many aspects. One missing part is that their theories focus on the ReLU case, while this paper extends them to other common activation functions and maintains the L+1 depth and logarithmic width requirements. They mainly focus on FC networks in this work. Empirical study on MNIST is conducted to validate their theory.

strengths_and_weaknesses: **Pros** 
1. They extend SLTH to non-ReLU activation functions, which is a credible theoretical contribution towards LTH, network pruning, or neural networks themselves.
2. Meanwhile, the L+1 depth and logarithmic width requirements are maintained.
3. The paper is well-written and well presented.

**Cons**
I like this paper on its own. My major concern is that, given the existence of [1] (L71: “While this approach has been transferred to convolutional and residual architectures [1]), what is *truly new* from this work?

The major construction scheme in this paper (Sec. 2) has a non-trivial overlap with [1] (Sec. 2 and Sec.3). The major novelty of the non-ReLU activation functions for SLTH also has been discussed in [1].

For the rating - I think this is a good paper in general. But unfortunately, some major content has appeared in previous works. My final rating hinges on how the authors respond to my concerns.
questions: * Please respond to my concerns above
* Side question: SLTH is interesting itself. However, as the experiments in this paper imply, we need much more parameters to realize it. I am wondering, what possible *practical* meaning it could imply?

limitations: Yes, they address the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: summary: The authors attempt to extend previous work proving the existence of "Strong Lottery Tickets", strong LTs, i.e. subnetworks of a randomly-initialized neural network that show moderate generalization without training. The previous work had proven the existence of strong LTs of depth L within randomly initialized source neural networks of depth 2L, with the restriction of using ReLU activation functions. The authors claim to show a proof of such an existence within a source neural network of depth L+1, and assuming a broader class of activation functions. The authors attempt to validate their claim by finding weak LTs (i.e. LTs from a trained/pruned neural network) in source models of depth 2L and L+1, and comparing the generalization of the weak LTs.
strengths_and_weaknesses: Strengths:
* The authors attempt to reduce the depth provably required to find "Strong Lottery Tickets" i.e., subnetworks at initialization with good generalization.
* Any such guarantee could make a big difference in the feasibility of finding strong Lottery Tickets emperically.

Weaknesses
* The premise of the paper is entirely based on the (unstated) assumption that Lottery Tickets can approximate an arbitrary subnetwork's weights and structure (i.e. target network $f_t$, from source network $f_s$. This assumption is unproven at best, and in fact all evidence empirically points to this assumption likely being false. As has been shown empirically in multiple works, LTs are extremely restricted in the solutions they can find. In "Linear Mode Connectivity and the Lottery Ticket Hypothesis" by Frankle et al. show that all Lottery Ticket solutions are within the same basin, effectively learning very similar solutions. In "Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win" by Evci et al, it is further shown that this solution basin is the same as the pruning solution, and a function similarity analysis shows they learn effectively the same function. Empirically we only know how to find one specific subnetwork with Lottery Tickets. Furthermore, we are not given any relationship between $f_t$ and $f_s$ (or any restrictions on $f_t$) to even understand how/if $f_s$ is related to the source model or the pruning solution.
* Given the small-scale model and dataset, the empirical results (on weak LTs, not strong LTs!) shown do not provide much support for the theoretical claim, notably the ReLU/LReLU results for depth L+1 are 0.2 percentage points lower than 2L and the target models. This might not seem significant, but when one considers how easy the problem is to solve, and how close the 2L solutions are, it is not as convincing. Please note these results are also Weak LTs, not strong LTs as the proof is intended to show the existence of. 
* There are many other assumptions made critical to the proposed proof that are unjustified, not obvious, and in some cases obviously not maintained in real-world neural networks. For example, restricting the weight magnitudes of the model.
* Paper is very unclear in other sections, with math not well explained in bits, and language of some sections incomprehensible (more details below in Questions).
questions: * 26-34: unclear, some sentences do not make sense at all -- needs a rewrite
* 38-40: how do these function approximation results relate to sparse nets?
* define strong and weak/strong Lottery Ticket Hypothesis, and weak/strong Lottery Tickets in the beginning (currently there are some definitions in the second paragraph of related work, but these need clarification also)
* it should be emphasized that the target network is trained (at least this is what I have inferred, but I am still unsure!)
Related Literature: all of this should be put in a relation to the topic of your work; the second paragraph explains the topic of your work and should rather be in the intro
* 67-69: “Their existence has been proven [...] by providing lower bounds on the width of the large, randomly initialized source network” -- bounding the width is not an existence proof. proven theoretically or shown empirically? if theoretically, what method was used?
* 80: "we usually care about cases where \epsilon < \delta" \epsilon is approximation error, and \delta is 1-probability, how/why would we compare these? It's apples v.s. oranges from what I can see.
* 87-88: Why is a bound on the weight magnitude not a loss of generality?
* 95-98: “we assume a convenient parameter initialization that we have to choose with respect to the activation function if we approximate a target layer with two source network layers”
    1) how is the initialization related to the activation function?
    2) why is a target layer approximated with two source-net layers? is this an assumption, or is this enforced by construction in your approach?
    3) why is this param init “convenient”?
* 104-106: the normal distribution (aka Gaussian distribution) is not the same as the uniform distribution; what exactly do you mean here?
* Figure 1: “Dashed links only exist if source network biases in layers l > 1 are initialized to zero.” -- isn’t it the converse, i.e., only when the biases are non-zero?
Assumption 2.2: why? what is the purpose of this type of block-diagonal symmetric structure that you impose on the source-net weight matrices?
* 136-150: this belongs in the related work section; in the following lines are several more repeated mentions of related work
* 153: explanation unclear. what is the middle layer?
* Direct citations should be made in the format Author et al. [1], (i.e. \citet in natbib not \citep). This formatting should be fixed throughout your work.
limitations: No such limitations/negative impacts are discussed by the authors. It's not immediately clear to the reviewer any potential impacts since this work is quite far from application, although pruning in general has been shown to have consequences for bias/robustness of trained models.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper generalizes the lottery ticket hypothesis by (1) extending results beyond ReLU activation functions to a broad class and (2) improving the 2L depth to depth L+1.
strengths_and_weaknesses: - Originality: The originality of the paper is twofold: a different network construction allows for depth L+1 instead of 2L, and flexibility in the choice of activation function means this technique can potentially be applied to many more types of architectures.

- Quality: This is a good paper.  There is a clear discussion of the related work and how this paper relates to past papers, and this paper makes a concrete, incremental improvement over the past works.

- Clarity: The writing is clear and well-organized.  No complaints here.

- Significance: The main significance at this point are the theoretical contributions.  I believe there is a potential to make a stronger statement about the practical significance with additional experiments.
questions: Is there a reason why practitioners should care about the depth 2L to L+1 improvement, or is the interest merely theoretical?  If it is of practical significance, please provide an experiment demonstrating so.
limitations: The main limitation is in the experiments, which are at best just a simple sanity check of the theory with a small network and dataset.  Since the paper focuses on flexibility (many activation functions) and efficiency (reducing depth from 2L to L+1) it would be much more impressive to see the technique applied in a more realistic setting with a larger network and dataset.
review_title: null

Meta-review: metareview: The submission provides a nice extension of the previous work that shows a random network with 2L layer contains a subnetwork (or lottery ticket) that approximates the target network of depth L well. Instead of 2L, they show L+1 layer plus a logarithmic factor wide suffices. Overall it is a nice solid contribution to the community. In the camera ready version, AC would advise the authors to clearly specify the difference between this submission and [1]. 

The concerns raised by reviewer Puqv are due to misunderstanding of lottery ticket hypothesis (LTH) and are largely not valid. For example, "Linear Mode Connectivity and the Lottery Ticket Hypothesis" by Frankle et al, in fact shows *after the initial phase of the network training*, all Lottery Ticket solutions are within the same basin. For different randomly initialized networks, the resulting LTHs can be very different. 
confidence: Certain
Decision: Accept