Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper uses dynamical system theory and inertial manifold theory to validate the Lottery Ticket Hypothesis, that is, a randomly initialized dense network contains a sparse subnetwork that when trained from scratch, can achieve similar performance to the original dense network after comparable training epochs. They provided a method that in one iteration can find the smallest such subnetwork. 

main_review: The paper first uses dynamical system theory and shows that there exists a unique global attractor $A$ of the gradient dynamical system corresponding to the gradient descent procedure. The global attractor contains all local minimum points of loss $L$. Then they introduce the inertial manifold of the dynamical system. The inertial manifolds enclose the global attracter. If the conditions in Theorem 5 hold, there exists an inertial manifold whose dimension is lower than the original space. The authors claim that the condition holds in the empirical data that they test. While the results and claims are impressive, I would like to see more discussion and theoretical justification.

 
Comments:

In stating the Lottery Ticket Hypothesis in section 2.1 on top of page 3, the notations need to be more clear, e.g. does iteration $i$ correspond to the initial state of $W$?

Can the authors clarify if the $W^+$ is the same as the sparse subnetwork in LTH, in which many weights are set to be zero? $W^+$ may lie in a low-dimensional space, but why is it sparse?

It seems that there are many ways to convert the gradient flow to a semi-linear ODE. Can the authors clarify why they chose the particular way in equation (15)? 
 


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work aims to theoretically verify the lottery ticket hypothesis and the existence of winning lottery tickets. Dynamical systems and inertial manifold theory are used.  Lots of mathematical proof and definitions are included in the papers, and experiments are conducted to test the performance of the proposed method. 

main_review: Although the method is not explicitly defined, we can grasp some thoughts from line 267-line 271. The pruning method does not seem to resemble other current score-based pruning methods. They seem to address the problem with sub-space properties. Section 3.2 further shows the condition in Theorem 5 is satisfied and also gives an estimate to the Lipchitz constants. This is a novel and interesting work. 

Main questions:

1. I was wondering if the author can provide a formal definition of the IMC method? An algorithm can be of great help for people to understand how IMC works. 

2. How to control the sparsity of the neural network with the IMC method or is it possible to control the sparsity level? If I understand the method correctly, the size of the pruned networks seems to be decided by $k$, and then $H(W^*)$. So how is the sparsity level controlled?

3. Is it necessary to recover the complete form of $W$ after one finishes training $W^+$ for inference/test? The training process can be done on $W^+$ solely but I am not sure about the inference process. If yes, can the authors give hints on how to use $W^+$ only for inference?

4. Not sure if it is appropriate to put related work in the supplementary files. 

5. Regarding Figure 2, I am curious to see the performance when the training epoch is smaller than 5. For example, is it possible to estimate $W*$ when only train 1 epoch?

6. Can the author provide a visualization of sparsity masks?



Update:

Thanks for the great efforts in addressing the questions. After reading all reviews and responses, I tend to accept this work and keep my score.
limitations_and_societal_impact: No
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This theory paper uses Inertial manifolds theory to verify Lottery ticket hypothesis and the existence of winning lottery tickets, providing useful measures for requirements/scenarios for lossless pruning and one-time pruning. 

main_review: The paper is written clearly, and the connection between inertial manifolds theory, gradient dynamics and lottery ticket hypothesis appears to be original. I have not checked the analytics in supplementary materials extensively, but the optimal sparsity level found by inertial manifolds theory is empirically demonstrated in Fig 1, which appears to be a strong result. 

Questions to the authors 
- Can you provide a pseudo-code and a sample code for computing the optimal sparsity? In the current text, it is unclear how to go from the dynamical theory to the numerical estimation of the optimal sparsity, which would be of great use to the rest of the community. 
- Are there insights on what determines the optimal sparsity from the theory? 

limitations_and_societal_impact: Authors have adequately addressed this issue.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Summary: 

The paper is dedicated to validating the lottery tickets hypothesis and delivering an effective one-time pruning. The authors investigate dynamical systems theory and inertial manifold theory to offer a theoretical justification. Specifically, they reduce the high-dimensional system of dense networks onto inertial manifolds to obtain a low-dimensional system regarding pruned subnetworks. Experiments on CIFAR and ImageNet with ResNet-18 and ResNet-32 validate the effectiveness of the proposal. 
main_review: Pros. 
1. The authors provide pioneering works on the theoretical justifications of LTH.
2. They formulate the problem as a gradient dynamical system. The idea is interesting, although within expectation.

Cons.
1. The paper claim that they validate the LTH. I think it is overclaimed since the classical LTH contains two statements: 1.1 undamaged performance when trained from the same initialization; 1.2 fast convergence. The paper only discusses the first point.
2. The author uses lots of paragraphs to describe the rationale of the formulation, which is great. However, they only describe the detailed methodology or implementation with a few sentences from lines 267-271. I am totally lost about what exact processes are adopted for pruning. For example, I have the following concerns: 2.1 does it only train 10 iterations to estimate the local optimal W* from W? 2.2 all network parameters are flattened to be the W? 2.3 the "prune" in line 270 means reduce W to W+?
3. Although the author compared with diverse previous pruning methods, the experiments are still insufficient. 3.1 As the superior performance of LTH in extreme sparsity levels is the most surprising point of LTH, the authors do not show any extreme sparsity results such as more than 90%/95% sparsity. Table 1/2/3/4 only presents results with sparsity levels lower than 50%.
4. No large model experiments like Res50.
5. What is the detailed platform for report running time results? Since running time is super sensitive to the environment or other uncontrollable factors. Maybe use Meta Flops or Energy.
6. I am very confused and suspicious of the SNIP/GraSP/SynFlow results in table 2. Based on Jonathan Frankle's paper (https://arxiv.org/abs/2009.08576), SNIP/GraSP/SynFlow pruned model with less than 10% sparsity should have almost undamaged performance compared to dense models. However, Table 2 shows that they suffer 1-2 point performance degradation.

Minors.
1. The statement in the abstract "Such heuristic pruning strategies are hard to guarantee that the pruned networks achieve test accuracy comparable to the original dense ones" can be more accurate. It should contain two conditions: a. extreme sparsity; b. hard to train from scratch not hard to fine-tune.

limitations_and_societal_impact: There are no limitations and potential negative societal impacts. The authors need to add extra discussion.
review_title: null

Meta-review: This paper aims to provide theoretical study and justification to the validity of the lottery ticket hypothesis, which indeed has recently been of great interest to the deep learning community. While one reviewer suggested the results or conclusion here are somewhat overclaimed, the work has generally been favorably received by most of the reviewers. The results provided here are somewhat expected, but nevertheless, it is good to see work done to properly derive and establish them. Further, in their responses the authors have addressed most (if not all) major reviewer concerns, and have subsequently also emphasized their commitment to implementing appropriate revisions in their manuscript. In total, three reviewers have scored above acceptance threshold (one outright accept and two marginally leaning to accept). The remaining reviewer has raised their score from reject to marginally below the threshold, but it is my impression that they would not object to the paper being accepted. Therefore, I agree with the majority of reviewers and also lean towards recommending to accept this paper.
Decision: Accept (Poster)