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: Following a Pac-Bayes compression-based approach to generalization bounds developed in prior work, the paper leverages improved compression procedures to derive tight bounds for the compressed models, both in supervised and transfer learning settings. It also provides empirical evaluations of the bound upon variations of several factors known to impact generalization.
strengths_and_weaknesses: The paper digs deeper into a nice approach that leverages a quantitative connection between compressibilty and generalization. Although the paper largely relies on the approach developed in prior work by Zhou et al (ref [59] in the paper), the practical improvements look substantial. I also find the discussion and empricial analysis in Section 6 particularly nice and promising. 

My main reservation concerns a lack of clarity of the approach, which I feel can potentially lead to misinterpretations and misunderstandings. In fact I think these clarifications are important also for the reviewers so as to avoid misjudgements of the significance of the results. 

From my understanding  from Section 3 and Algorithm 1 (please correct me if I'm wrong), the main idea (following Zhou et al) is to combine (i) a Pac-Bayes generalization bound applied to a pointwise posterior at the learned hypothesis and the the universal prior which penalizes predictors' minimum length; and (ii) improved compression schemes applied to the learned network weights.  This provides strong generalization guarantees for the compressed models. I believe the question of the relationship with the generalization gap for the uncompressed classifer is non trivial -- and left open here; I feel this is an important issue (which is addressed e.g in Nagarajan & Kolter (2019a)) which should be explicitly mentioned in the paper to avoid ambiguity. (I see that this limitation is explicitly mentioned and discussed in Arora et al 2018 for example, which also provides bounds for compressed models). 

Note that this distinction is important conceptually: for example, recent analysis (e.g., Nagarajan & , Kolter (2019b),  Negrea et al (2019)) suggest that using suitable surrogates -- randomized or compressed -- versions of the learned predictors can circumvent the limitations of uniform convergence. From this point of view, it seems that the crux of the generalization problem is to explain generalization of the original predictor (e.g. by a suitable coupling that ties its  performance to that of the surrogate).  

Regardless of clarify, a potentially more serious consequence of the above point is the soundness of the comparison with existing bounds. I believe it would not be methodologically fair to compare bounds on compressed models with bounds on uncompressed ones (just like it would not be fair to compare bounds on stochastic predictors  with bounds on deterministic ones). In fact, I would also be curious to see explicit comparisons with other standard existing (e.g., norm based) bounds applied to the compressed network. Could the authors comment on this point?

On the other hand, I do think that obtaining strong guarantees for well performing compressed models is very interesting. Now, if the goal is to obtain competitive compression models with guarantees,  I think the various tradeoffs that usually comes along with compression need to be more thoroughly investigated: in particular, how does the actual generalization performance  compare with the uncompressed network ? What are the computational costs (I would not agree that this issue is unimportant here as suggested on line 122-123) ? etc. 

I think that the paper can potentially yield a  very nice contribution, provided the above ambiguity is correctly clarified and settled. For example, even without theoretical guarantees that tie the performances of the compressed and uncompressed model,  the bound for  the compressed model can still yield a powerful heuristic generalization measure for the uncompressed one. The results in Section 6 suggest that this is the case, but if this point of view is favoured, they would probably deserve a deeper and more thourough investigation, so as to compare well with prior work in the subject (in fact recent large scale correlation analysis revealed key challenges  in identifying actual causal factors for generalization (e.g. Jiang et al, 2019, Dziugaite et al 2020)). 

References: 

Nagarajan & Kolter (2019a). Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience. ICLR 2019. https://arxiv.org/abs/1905.13344.

Nagarajan & Kolter (2019b). Uniform convergence may be unable to explain generalization in deep learning. NeuriPS 2019. https://arxiv.org/abs/1902.04742

Negrea, Dziugaite, Roy (2019). In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors.  ICML 2010. https://arxiv.org/abs/1912.04265

Jiang et al (2019). Fantastic Generalization Measures and Where to Find Them. ICLR 2010. https://arxiv.org/abs/1912.02178

Dzuigaite et al (2020) In search of robust measures of generalization. NeurIPS 2020. https://arxiv.org/abs/2010.11924
questions: Answering the above concerns (which justifies my low rating for now) would be a good starting point for a discussion. 

Miscellaneous (minor points):

* Line 99: "relative entropy" and "entropy" could be named explicitly  

* In the $KL$ bound below line 113: I believe $h$ should be $h^\ast$ in the right hand side expressions. 

*  Fig 2 has no (a) or (b) as named on lines 290 and 296. 

*  Role of implicit regularization: to dig deeper into the role of the optimizer, it would be interesting to see how the bound evolve during training compared to the actual test error.   
limitations: The conclusion does include a discussion on the limitations of the results.
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: The paper demonstrates a novel combination of compression schemes that lead to significantly better generalization bounds derived from PAC-Bayes bounds. This approach is based on known bounds that were previously used by other works, but is combined with a more powerful compression scheme. The compression scheme is based on limiting the parameter space of model to a d-dimensional random subset represented by the addition of a random starting point in the parameter space plus the random project of a d-dimensional vector of learnable parameters. Such a representation was used in prior works to estimate the "inherent dimension" of a dataset / task. The d-dimensional vector is then optimized with quantization-aware training techniques, followed by quantization at the end of training. Finally, arithmetic coding is employed to retrieve the end compressed code of the classifier, which also includes additional hyperparameters on which the compression scheme is dependent (e.g., the seed). The estimated code-length is then plugged into the known bounds to result in the estimated generalization bounds.

The paper demonstrate how this method can obtain data-independent bounds that are sufficiently small to explain (to some extent) performance on MNIST, FMNIST, and CIFAR10, as well as additional phenomena, e.g., generalization of transfer learning, the importance of structure in the dataset for generalization of fully-connected vs. convolutional networks, and double descent. The paper also highlights some of the limitations of the current approach, for example, the estimated bounds do not correlate with the empirical observation that larger models generalize better.
strengths_and_weaknesses: The paper gives strong evidence to support a long standanding conjecture that NN can be sufficiently compressed to a degree where compression-based bounds are close to their empirically observed accuracy. While not the first to follow this path or reach non-vacuous bounds, it obtains bounds that are far closer to real-world observations, and does so without relying on data-dependent bounds. The paper shows the limitations of data-dependent bounds that many prior works have focused on, that they are not as explanatory and are closer to bounds obtained by considering the estimation of the validation accuracy. The results on more complex tasks (CIFAR-10, CIFAR-100) are still far from what is desired, but the paper also shows the potential of this approach (its applicability for explaining a wide variety of phenomena) and indicates the area where researchers should focus. In addition, the paper is exceptionally well-written, clearly explaining PAC-Bayes bounds and their proposed compression scheme.

The main weakness of the paper is that many of its components are either wholly-based or lightly-derived from prior works, including the compression-based bounds and the individual components of the compression scheme. From that perspective, it is not as novel of an approach. It is also worth noting that the authors slightly misrepresent the degree to which using the "inherent dimension" factorization is novel in the context of model compression for estimating compression-based bounds. One could interpret Algorithm 1 in [1] as following such a factorization which appeared even prior to [2] that coined the term "inherent dimension". Of course the analyses and methods in that paper are far different from this submission. Regardless of the above, the specific combination of approaches (and their slight improvements) is novel, and it leads to the strong results mentioned above.

[1] - Arora et al., Stronger generalization bounds for deep nets via a compression approach, ICML 2018.

[2] - Li et al., Measuring The Intrinsic Dimension Of Objective Landscapes, ICLR 2018.
questions: Think of the things where a response from the author can change your opinion, clarify a confusion or address a limitation. This can be very important for a productive rebuttal and discussion phase with the authors. ====

Are there any benefits to the Kroncker Projector beyond the runtime? Does it not harm model compression (in the "from scratch" scenario)? It would appear that Figure 1 (right) should also include a plot for the training accuracy when using the dense projector. While faster runtime is nice in practice, for theoretical exploration it seems secondary. If it leads to worse generalization bounds, then it will be detrimental to the main goal of the paper.

Also, some references are not properly cited, e.g., [2] above is cites by its arxiv number, not as an ICLR paper. I would advised making sure the citations are all updated and correct.
limitations: The authors gave a sufficient description of the limitations of their work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors propose a new method for compressing deep learning models which is adaptive to the level of structure in the model and the training dataset. In their research, the authors follow the Occam razor paradigm with which they are able to explain why deep learning models generalize on structured data sets such as CIFAR-10.
strengths_and_weaknesses: Strengths:
- the proposed method is based on theoretical foundations,
- the subject of the research is interesting.

Weaknesses:
- poor comparison with other methods, many results of competing methods are not entered in the tables,
- there are no results confirming the statistical advantage of the proposed approach (it is worth running the method several times and presenting the mean and statistical deviations, it may perform a statistical test confirming the effectiveness of the method),
- the authors focused on the compression methods of the subspace dimension and the Occam razor paradigm, but there are many methods in the literature that reduce the number of model parameters in other ways. Couldn't you comment on them?  Here are some of them:
   * https://arxiv.org/pdf/1812.08928.pdf
   * https://openaccess.thecvf.com/content/CVPR2021/papers/Li_Dynamic_Slimmable_Network_CVPR_2021_paper.pdf
   * https://papers.nips.cc/paper/2017/file/a51fb975227d6640e4fe47854476d133-Paper.pdf
   * https://proceedings.neurips.cc/paper/2019/file/68b1fbe7f16e4ae3024973f12f3cb313-Paper.pdf
   * https://arxiv.org/pdf/1810.05331.pdf
- the presented charts are not sufficiently clearly described.
questions: 1. Can you type values for the missing values in the tables or explain why you can't do this?
2. Can an experiment be conducted to confirm the statistical effectiveness of the proposed approach?
limitations: Yes
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes to apply model compression into an existing PAC-Bayes bound to obtain non-vacuous to obtain "better" prior from data (a portion of or the whole training dataset) to make the bound non-vacuous. The proposed method is based on the random subspace compression [38] that projects the high-dimensional parameter vector onto a lower-dimensional subspace with a fixed but random matrix projection, corresponding to the intrinsic dimension of the learning task. Such projected model parameter is then quantized to compress the model further.
strengths_and_weaknesses: **Strengths**

The main difference of the current work from the literature, to me, is the integration of model compression into existing PAC-Bayes bound to make the bound non-vacuous.

Another contribution of the current work is to present some ad-hoc methods based on either Kronecker product or the observation about Batch Normalization layers to improve the random subspace projection to find a better intrinsic dimension of the task of interest. It is then followed by a quantization technique to compress the model further to regularize the model of interest further according to the Occam's razor.

**Weaknesses**

The proposed random subspace projection in Section 4.1, despite improving the running time significantly, seems as an engineering technique to optimize [38].

Another suggestion is that the evaludation is quite simple with a limited number of baselines (both Tables 1 and 2). It seems that previous methods on non-vacuous PAC-Bayes bounds do not include results on several datasets, but it would make the paper more convincing if those methods could be reproduced and evaluated on the datasets of interest.
questions: The contribution of the paper is not very clear to me. I wonder if it could be clarified further, especially differentiating the conventional random subspace projection and quantization with what are proposed in the current work.

Another suggestion is about the evaluation of other baselines in the literature. And since the current work includes two things: lower-dimensional projection and quantization, could the authors provide an ablation study to see the effect of using only the projection without the quantization. In such case, we could understand further how influence each of the proposed factors leads to the final result.
limitations: The authors explicitly stated the limitation where the current work only helps to unveil a part of the performance observed in deep learning models. There are certain aspects regarding to the generalization of deep learning models remained unexplained.
review_title: null

Meta-review: metareview: After reading the submission and reviews, my understanding is that this submission combines the compression approach of Zhou et al with PAC-Bayes theory to obtain tight generalization bounds. While the approach is a mere combination of pre-existing approach, the insight that led to this method provides compelling results for generalization bounds and discussion with reviewers has strengthened the submission. 
Therefore, I recommend this paper for acceptance.
confidence: Certain
Decision: Accept