Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper gives a theoretical characterization of the underlying cause that makes the neural networks amenable to common compression schemes in the over-parameterized regime. It is done by connecting the dynamics of the learning algorithms such as SGD to the heavy tails of the weights of a network, which leads to better compressibility. The main contribution is to provide sufficient conditions for the compressibility from the limiting distribution of SGD, and show how the compressibility of a network can lead to better generalization. 

main_review: The paper is very well written, and is addressing an important topic of the field of why and when a pruning method is useful. It also makes several technical contributions by borrowing classical results to prove new theorem. However, the following points need to be considered: 

My main concern is that the main result is based on a condition / conjecture (Definition 1) that seems to be too ideal. The remark on l.163  is not exact: note that [DBDFS20] proved that a similar form of (4)  indeed holds … I think that it remains still an open question. In DBDFS20, L=2, and W_L is fixed, only W_1 is considered to be learnt by SGD. Thus it is very hard to believe why (4) holds in more complicated cases such as the heavy tails. Such kind of details needs to be mentioned so that your readers have a clear view of the current state-of-the-art. 

About the generalization bounds, what are the contributions compared to the work mentioned on line 275? Are you using a very different technique to prove the similar results? How similar the Theorem 4 compared to the existing results?

The assumption on SGD in Definition 1 is for eq. (2), however, in the reference GSZ20, it seems that ergodic averaging SGD is proved to converge to a stable distribution (l.340). Is the SGD limit of (2) also converging to a heavy-tailed distribution? Why in the numerical results, the ergodic averaging SGD is chosen rather than (2) for evaluation? 

Theorem 2 eq. (5), the w_l should be W_l as the norm ||. || is for Frobenius norm, thus there is a typo? It would be good to give some intuition why there is division by 2 in the condition p>=max_l alpha_l / 2. This is not the case for Theorem 1 and 3. 

Which p norm is taken in Figure 3 to compute the compression error?

line 323, what it means to be ‘consistent’ with the results of … ?

In Figure 1-7, sometimes write Mean estimated tail index, sometime write estimated tail index, are they the same? 


limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyze the compressibility of over-parameterized neural networks using the heavy-tail property of SGD. The authors show that when the network weights are approximately sampled from a heavy-tailed distribution, the weights are more compressible. The authors also provide a generalization guarantee showing that more compressible networks have smaller generalization gap.
main_review: I think overall this is a good paper. I like the connection between the heavy-tail property of SGD on large network and the compressibility of the network (the l_p compressibility from the compressed sensing literature). The results seem to be new in the literature and I believe the results will strengthen our understanding of neural network compression.

The paper is clearly written. The notation is slightly heavy (which happens to most neural network theory papers) but mostly clearly defined. I am able to follow most parts of the paper.

I have some concerns on the generalization bound in Theorem 4. It seems to say that if the network has smaller kappa (more compressible), then its generalization gap will be smaller. However, this is only an upper bound for the population risk of the compressed network (R_0(\hat{w})). When kappa decreases, the upper bound decreases, but it does not necessarily mean R_0(\hat{w}) also decreases. The authors should either prove a lower bound or clearly state this limitation in the paper.

Minor:

Line 85: Y is defined as a discrete set of integers {1, …, d_Y} on line 81. So f_w(x) should be a function that maps from X_B to R^{d_Y} rather than Y; similar thing on line 93.

Line 212-213: “how would the smallest kappa_l would differ…” it seems to be a grammar error—two “would”.

limitations_and_societal_impact: This paper mentioned a few possible future directions which can be considered as resolving the limitations of the current work.
I did not observe immediate societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The main contribution of this paper is to link the two properties of compressibility and SGD. (i) as the network size goes to infinity, the system can converge to a mean-field limit, where the network weights behave independently, (ii) for a large step-size/batch-size ratio, the SGD iterates can converge to a heavy-tailed stationary distribution. In the case where these two phenomena occur simultaneously, we prove that the networks are guaranteed to be ‘lp-compressible’. Further experiments on fully connected and convolutional neural networks and show that the results are in strong accordance with the theory.
main_review: Originality: Novel. This work links compressibility with SGD, and theoretically explains that simple pruning strategies in some networks are also effective.

Quality: The theoretical proof is quite sufficient.

Clarity: well written. 

Significance: Moderately significant. This paper does theoretical derivation and experimental verification on the convolutional layer and the fully connected layer.
limitations_and_societal_impact: 1.	The theoretical framework proposed in this article is not applied to the Resnet layer, which is widely used in recent works.
2.	This paper only experimented on the mnist and cifar10 datasets, which seems relatively small for pruning experiments.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper looks at the compressibility and generalization ability of multi-layer neural networks under the heavy tailed mean-field limit. The mean-field condition is invoked to simplify the analysis of the distribution of weight parameters as the distributions of individual weights are independent, while the heavy-tailed condition is needed to ensure an abundance of small weights (weights at the tail) whose removal would result in bounded relative error. Compression error is defined in weight space as the relative distance between the compressed weight vector (weight vector where small weights are set to zero) and the original weight vector.

The paper shows that arbitrarily low compression errors can be achieved under a range of pruning strategies (global pruning, layer-wise pruning, singular value pruning, and neuron pruning) if the network is sufficiently large. Another condition is for the p-norm used to calculate the error to have p larger than the heavy tail coefficients.

main_review: The paper is well-written and the authors are to be commended for providing the necessary background for making their theoretical contributions accessible to readers who are new to this subject area. I believe the theoretical results are novel, even if the main results follow in a rather straightforward manner from a standard result on the compressibility of heavy-tailed i.i.d random variables (Lemma S2 in the appendix). In general the compressibility results are largely intuitive: The larger the number of weights is, and the more heavy-tailed their distribution is, the more probable that there will be enough small weights so that their removal would have minimal impact on the weight vector norm. The results are thus not surprising, especially that they follow from standard results in the statistics of heavy-tailed distributions.

In the empirical results, the authors convincingly demonstrate that in several cases, there is a correlation between the tail indices and the prunability and generalization ability of the network.
However, the authors do not control the tail indices directly. Rather, they vary the learning rate and batch size to obtain the desired tail indices. As such, the empirical results do not categorically prove that tail indices have a causal influence on the prunability and generalization ability of the network. There could be other confounding factors here as the tail indices are not controlled directly. The authors, however, phrase the discussion as if heavier tail indices lead to better generalization and prunability. The empirical evidence certainly points in that direction, but it is not categorical. The authors need to either 1)devise experiments where they can directly control tail indices while other factors are constant and observe the effects, 2) modify the discussion to highlight that the empirical results are circumstantial (but not definite) evidence that heavier tails are the causal factors leading to more prunable and generalizable networks in the experimental results.

Finally, it is not clear what the practical benefits of the theoretical results are. The effect of $\eta/b$ (ratio between learning rate and batch-size) on generalization accuracy is known, as is the fact that a larger ratio leads to heavier tailed weight . While deeper theoretical understanding is a worthy goal in itself, the paper would benefit from discussing any novel practical implications of the theoretical results.



Minor comments:
1)L198: remove duplicate $\epsilon > 0$
2)L357: remove confirm

limitations_and_societal_impact: The paper has no negative societal effects that I am aware of.
review_title: null

Meta-review: Four reviewers recommend this paper to be accepted. The paper provides result addressing why and when pruning is possible. A concern is that the main result is based on a condition that might be too ideal. Taking the discussion into consideration, I find that the manuscript makes valuable contributions outweighing its limitations. Hence I am recommending the submission for publication. I ask the authors to implement the improvements promised in their responses and to carefully consider the reviewers comments in the preparation of the final manuscript.
Decision: Accept (Poster)