Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of neural network compression using analysis in the high-dimensional NTK regime. Their main results show that under this regime, the spectral properties of both NTK and CK matrices are independent of the distribution of the weights up to normalization and centering. Instead they depend on a number of parameters that define the activation functions at each layer. This finding informs a new compression technique where a new (compressed) network can match the activation parameters at each layer to enjoy the same spectral properties as the original net. This NTK-LC technique is evaluated on synthetic data by qualitatively comparing the distribution of eigenvalues and on real data by comparing test accuracy with naive baselines.
strengths_and_weaknesses: Strengths:

The paper has a clear motivation in the field of neural network compression, a relevant problem that is lacking theory. It is clearly written with thorough theoretical results and experiments on both synthetic and real-world data.

Weaknesses:
1. The claim in line 49 seems to be a central theme of the paper but has no follow-up discussion on its meaning and implications.
2. Theoretical claims are presented in the asymptotic regime of infinite n and p (Assumption 1).
3. A particular GMM distribution is chosen for the input data of the studied model without justification for why it is the relevant distribution to be analyzing.
4. The results in Figure 2 rely on a qualitative measure of "closeness" to evaluate the method instead of a metric that can be quantified and compared. Many of the markings in the top histograms are barely noticeable and require magnification to be seen.
5. The results in Figure 3 are compared with "naive" baselines instead of competitive state of the art methods.

questions: Question: What is the novelty of the NTK-LC approach and how does it compare with state of the art methods?

Suggestion: As mentioned in Weakness 1, the paper would benefit from a discussion on how the convergence and generalization properties of ultra-wide DNNs can depend only on the eigenspectra.

Suggestion: As mentioned in Weakness 3, the paper would benefit from a quantitative metric of eigenvalue closeness.
limitations: The authors have addressed the limitations of using NTK theory to explain the behavior of modern neural networks.
review_title: null

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: The authors showed asymptotic eigen-spectral equivalence conditions for fully-connected NTK given GMM data and certain assumptions, based thereon they proposed a net compression scheme with sparse and low-precision random weights, and demonstrated with examples.  

strengths_and_weaknesses: [+] Results linking NTK and random matrix theory with DNN compression is of timely interest to the field.

[+] Though I cannot say I followed all proofs, the main ideas and motivations are well presented.

[-] A lack of comprehensive experimental comparison with baseline approaches is limiting the practical significance of the findings.

questions: - The authors ran experiments on real not-so-wide DNNs that also break the assumptions, e.g. taking real image data that is not GMM and taking convolutional nets that are not fully-connected.  And they reported, in their own words "unexpected close match" to the theory.  This, in its own right, is an important observation that future theoretical relaxations might address.  But the gap is rather inadequately characterized by experiment here: e.g. any empirical characterization of the notion of "unexpectedness"?  
- Another thing I do not appreciate is the trickiness of the scalar calibration due to nonlinearities.  This seems to stem from the requirement of unity Gaussianity.  Is there any empirical data supporting the near-Gaussianity under real data?  Does there exist any badly behaved nonlinearities that significantly deviated from theory?  Does this mean NNs trained with normalization layers are more conducive to such compression, or could the procedure be simpler in those cases?
- I find the naive sparse/quantized baselines presented in experiments inadequate.  Of course this is a post-training compression technique, but since it is derived from NTK, it is natural and important to ask how it generalizes compared to much stronger, non-post-training baselines, such as, say, a winning lottery ticket--does there exist any other compressed nets that generalizes better regardless of how expensive the compression procedure was?  
- "Lossless" (used not in quotation marks) might be a false advertisement.
- Figure 2, missing axes labels.

limitations: See above.
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 characterizes the asymptotic spectral equivalence between NTKs of dense and quantized networks. It shows that under certain assumptions of data (high-dim, Gaussian mixture data) and network architectures (wide MLPs), quantized networks have the same NTK eigenspectra of unquantized ones. This finding allows the authors to perform model quantization with little performance degradation.
strengths_and_weaknesses: The paper is very well written -- the authors crafted their paper with immense care and taste for mathematical detail. The main results of the paper (Theorem 1 and Theorem 2) are novel and subsume previous studies [2, 32] as special cases. Overall, I think this is a high-quality paper. 

One weakness of this paper is in its numerical evaluation. As I detailed below, the baselines used for the model pruning (randomly removing weights) seem to be too brutal and too weak. It is beneficial to incorporate more realistic baselines such as magnitude-based pruning.




questions: * Quantized neural networks in the current theoretical and empirical results focus on ternary-valued weights, i.e., NNs with weights that take values in {-1, 0, 1}. Would it be possible to extend the results to binary networks, that is, {-1, 1}-valued networks? It seems that such binary-valued weights (up to a proper scaling) can still satisfy assumptions for Theorem 1 and 2. 
* In Figure 3 in Section 4, the proposed lossless compression approach is numerically compared with two heuristic sparsification and quantization approaches.  The heuristic sparsification approaches uniformly zero out 80% of the weights. This approach is very brutal. Would it be possible to add a more realistic baseline of magnitude-based pruning -- remove a fraction of weights that have the lowest magnitude (absolute value) and keep other weights. This baseline is used more often as a baseline for model pruning and is sometimes surprisingly strong (see, e.g., https://arxiv.org/pdf/1902.09574.pdf)
* If I understand correctly, the current lossless compression approach uses layerwise pruning and quantization. That is, all layers share the same sparsity level in Algorithm 1. Would it be possible to use the same theoretical insights to perform global compression; that is, compress weights in MLP layers collectively without regard for the specific layer. This may lead to better compression results since it gives more freedom to the weight selection. 
limitations: One limitation of the paper, as mentioned in my questions above, is its lack of natural baselines for model pruning in the experiment sections. I encourage the authors to consider incorporating them.
review_title: null

Meta-review: metareview: In the paper, the authors provide theorems that establish that for GMM input data, the NTK matrices of dense and quantized DNNs have the same eigenspectra in the asymptotic limit of high input data dimension and sample size.  These results motivate network compression algorithms which demonstrate good empirical performance even outside the regime for which the proofs are established.  The theorems provide a novel extension that contains previous studies as special cases.  The baseline comparisons included in the paper are somewhat limited in nature, and the authors should re-evaluate their choice to use the word "lossless" with quotes, and instead use a more accurate term that does not require quotes.
confidence: Certain
Decision: Accept