Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes scaling-invariant prior and posterior distributions for PAC Bayes generalization bounds. It supports these empirically and, based on these, introduces a practical uncertainty estimation method that compares competitively with the linearized Laplace approximation.
strength_and_weaknesses: Strengths:
* The range of contributions is quite broad, from a PAC Bayes bound to a practical approximate inference method.
* The paper is overall well-structured.
* The bounds seem to be empirically reasonably tight.
* The uncertainty estimation method performs competitively.

Weaknesses:
* I found it quite difficult to follow what the paper is doing in detail and would not be confident that I would be able to implement the paper just based on the manuscript. In particular, I don't really understand which dataset split is used for calculating which quantities.
* There are a lot of grammatical mistakes in the manuscript (as far as I can tell as a non-native English speaker), to the extent that it made the paper difficult to read for me (I'd usually just mention this as a minor comment, but in this instance I find that it is to a degree that it negatively impacts the already lacking clarity of the paper).
* There is no discussion of computational cost. It seems like the method needs to evaluate a lot (100 Lanczos iteration; inside of an optimization problem) of Jacobian-vector products, which is not cheap (especially in case each product requires a pass over the training set, although I'm not sure if this is the case).

**************************************************
POST REBUTTAL UPDATE

The authors have extensively updated the paper, addressing the concerns around presentation. I therefore increase my score.
clarity,_quality,_novelty_and_reproducibility: **Clarity** Good in terms of the overall flow and structure, but quite underwhelming when it comes to the details. There is just too much notation that is introduced inline throughout the paper, without any aids for the reader, such as a notation table or an algorithm box with pseudocode that recaps things concisely.

**Quality** Overall I'm willing to give the paper the benefit of the doubt and assume that it is good work with interesting empirical and theoretical contributions (although I will caveat this with saying that I did not check the proofs on the PAC Bayes bounds).

**Novelty** The ideas in this work are new.

**Reproducibility** Hyperparameters are vaguely described as a table of ranges in the appendix, however I did not find any final values. Given the further lack of clarity on the method itself, I doubt I would be able to reproduce any of the results in the paper.
summary_of_the_review: An in principle interesting paper with glaring weaknesses in its presentation, which all things considered make me lean towards a rejection.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper tackles the characterisation of the local curvature of NN loss landscapes in the face of scale-symmetries that appear in these models’ loss landscapes. Specifically, the authors build upon recent work in the linearised Laplace method for uncertainty estimation with neural networks by extending it to account for scale invariance in the NN parameter space. 

The authors first use their construction, dubbed the connectivity tangent Kernel (CTK), to build a PAC-Bayes bound with a data-dependent prior that is invariant to the scale of the NN weights. The authors show this bound to be non-vacuous empirically on CIFAR10 and CIFAR100 with ResNet-18. The authors then propose the trace of the  CTK as an easy-to-compute surrogate quantity for estimating models’ generalisation. They show this quantity to correlate more strongly with test performance than previously proposed quantities, such as the trace of the Fisher information matrix. 

Finally, the authors use their connectivity tangent kernel for uncertainty estimation within the linearised Laplace framework. They apply their approach to UCI regression datasets and to CIFAR10+100 with ResNet18. The proposed method provides a modest but significant performance boost on top of the standard linearised Laplace approach. 
strength_and_weaknesses: **Strengths**

* This paper makes 2 technically strong contributions, each of which could almost be a paper on its own.
	* A new non-vacuous PAC-based bound for a linear model built on a basis chosen to be the Jacobian of a pre-trained NN.
	* A formulation of the above linear model that avoids pathologies related to scale invariance in neural networks 

* The experimental validation is also quite strong. I was impressed that the authors evaluated both their generalisation bound and uncertainty estimation methods using ResNet18 (an 11M parameter model) on the CIFAR100 dataset. 


**Weaknesses**

* Motivation / Problem exposition. The scale-variance issues this paper addresses are quite subtle and are not explained in enough detail. I was lucky to be familiar with these issues as I have dealt with them in my own work. However, I think that the average reader will be quite confused about what problem the authors are solving. I would recommend including a specific example of the Jacobians of a NN changing when the scale of the weights changes, despite the NN output not changing at all. 

* The authors evaluate their bound and show it gives very similar results for different scalings of the NN parameters. However, no other non-invariant bounds are shown. I think that it would be illustrative for the reader to see how the tightness of alternative bounds is lost due to the invariance pathologies addressed by this paper.

* A potential issue with the proposed approach is that the re-scaling of the Jacobian basis that is proposed depends on the linearisation point. This vector contains information about the (potentially arbitrary) scaling of the dimensions of the NN Jacobian and information about how to fit the data well with the NN. It is not clear that the latter will be helpful to scale the Jacobian basis and it could in fact introduce some bias into the linearised model. 


* I found the experimental details provided lacking, even after reading the appendix. In this regard, I found the ResNet-18 CIFAR100 experiments particularly surprising. The dimensionality of the Jacobian basis expansion for a single input point is NOutputs x Nweights and evaluating this expansion requires as many backward passes as output dimensions. Additionally, a single step of Lanczos iteration requires a pass through the whole dataset and asymptotically the method requires as many steps as the rank of the kernel matrix being decomposed. How did the authors deal with these challenges?

* I would suggest the authors repeat the evaluations from tables 1 and 2 for multiple seeds and add errorbars. 

* I found the clarity of writing to be poor, partly due to the text being full of grammatical mistakes.  I provide more details below. 
clarity,_quality,_novelty_and_reproducibility: **Clarity**

I found this paper difficult to read due to the abundance of grammatical errors. I would recommend the authors employ a free online grammar checker.

The issue of scale-invariance in neural networks with normalisation layers was only discussed in the introduction and at a very high level. I would recommend the authors provide a more concrete description of this problem, which is a central motivation of the proposed techniques.  

**Novelty**

The issue of scale-invariance in NNs with normalisation layers is known within both the optimisation community (https://arxiv.org/abs/1706.05350) and the Bayesian deep learning community (https://arxiv.org/pdf/2206.08900.pdf). However, to the best of my knowledge, the solution proposed in this paper is novel. 

To the best of my knowledge, the PAC-Bayes bound used by the authors, where a NN is trained and a linear model is built on top of its Jacobian features, is novel. 

**Reproducibility**

The authors do not provide a code release or a very detailed experimental setup description. Given that I have some experience in this field, I think that reproducing this work would be challenging but not impossible. 
summary_of_the_review: 
I think this is a technically strong paper which I would like to see accepted. The paper has some major issues regarding clarity but I am confident that the authors can address these in a revision. When they do, I will be happy to raise my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work centers around the relationship between sharpness (scaling invariance) and generalization in DNNs under the PAC-Bayesian framework. This work decomposes the scale and connectivity parameters, derive the related connectivity tangent kernel (CTK), and builds the PAC-Bayesian generalization bounds. The trace of CTK can be regarded as a good indicator to show the correlation between sharpness and generalization.

strength_and_weaknesses: **Pros:** 

1. Propose an (empirical) connectivity tagenet kernel (CTK) to demonstrate the sharpness and scaling invariance, which can be regarded an weighted NTK by $\theta^*$ and Jacobian wr.t. $c$
2. Build the PAC-Bayesian bound via CTK for generalization and connect it to invariance for flatness


**Cons:** 

There are several points on the motivation of Laplace approximation and the extension to over-parameterization that require more refinement. In my view, this work is built on a certain type of Taylor expansion, obtains the corresponding NTK matrix, assumes the posterior distribution to be Gaussian via Laplace approximation, and derives the PAC-Bayesian bound for under-parameterized deep neural networks. The detailed comments are as below.

clarity,_quality,_novelty_and_reproducibility: This is well-written, and has good quality. But there are several issues that are unclear to me.

1. I understand the motivation of using Laplace approximation for tractable inference. Nevertheless, is this equivalent to assume that the posterior distribution over parameters is Gaussian? I think the application scope of Laplace approximation needs to be well discussed.

2. The so-called scale-invariance is based on $\theta^* \odot c$ instead of a single parameter $\delta$. Intuitively, the invariance is based on $\theta^* + c \theta^*/ || \theta^*||_2$, which appears feasible to Proposition 2.2. What’s the difference between these two settings?

3. Theorem 2.3 is incomplete as $\sum_{i=1}^P h(\beta_i)$ can be further estimated. More importantly, the results are only valid for the $P \ll N$ case, can not be applied to the commonly-used over-parameterized DNNs due to $\mu_{\mathbb{Q}} \in \mathbb{R}^P$. How to ensure  $|| \mu_Q ||_2^2 \ll N_Q $? 

4. In Section 2.4, the experiments work in $|S_P| \gg |S_Q|$. What is the result of the opposite setting? E.g., few training data for $S_P$.


Minor issues:
Table 1 and 7 can be incorporated into one figure for better illustration in the main text.

summary_of_the_review: This work introduces new ideas/insights to analyze the relationship between sharpness and generalization bounds, but leaves some issues that I am concerned about. I'm hesitant to give a 5 or 6, and would like to see the authors’ rebuttal.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors construct a PAC-Bayes bound that is insensitive to the fact that some parameters of neural nets can be arbitrarily rescaled due to normalization layers rectifying such rescalings. In a second step, they design a variant of the Laplacian approximation and evaluate both on a series of experiments.

strength_and_weaknesses: ## Strengths
The proposed PAC-Bayes bound stays stable and independent wrt rescalings of parameter rescalings compared to the baseline bound. The authors are encouraged to move Table 7 to the main paper as it clearly demonstrates the improvement provided by their approach. Keeping it in the appendix essentially hides this.

A major weakness of the draft is its written structure. There are a lot of grammatical mistakes (primarily missing articles), lots of typos, and partially repeated sentences,... Thorough proofreading is very necessary for any revision.


### Questions
- In the abstract, the authors discuss the flatness hypothesis as being widely accepted, while the first two paragraphs of the introduction then consist of summarizing an ongoing discussion in the literature. Can the authors comment on this?
- Can the authors explain what they mean by the decomposition of scale and connectivity? The connectivity is modified in the Lee et al. paper you cite c is a binary mask, whereas for you it is a continuous vector. In which sense do you get a decomposition between scale and connectivity by the $\theta(1+c)$ formulation? I seem to be misunderstanding a basic point of your setup. E.g., a c=0 via your prior changes nothing in any weight connectivity.
-  Table 1: Why do only some rows contain standard deviations (or standard errors?) and over which number of repetitions are these computed? (Same question for any other table containing stds)
- What is the relation between Table 4 and Figure 1? From my reading, they show the same experimental setting, but if so then the results in the table are misrepresentative as, e.g., for ECE Figure 1 clearly shows lower values for LL than claimed there. 

### Further comments
- before eq (2) speaks about "_our_ data-dependent prior" vs _a_ data-dependent prior making it sound as if the split of training data to get a data-dependent prior was a contribution of the current paper.
- $P_c$ appears in the line before (2) without any introduction and then disappears again for the remainder of the paper
- Table 3's formatting makes it look as if CL were to improve also about deep ensembles as well as MC dropout. This needs a major restructuring! (E.g. in the direction of Table 4)
clarity,_quality,_novelty_and_reproducibility: See the comments above. Clarity and quality have several problems. Given the details provided in the appendix the approach should be reproducible. Unfortunately, my knowledge of the current PAC-Bayes literature is too limited to properly comment on the proposal's novelty, but as far as I can see, novelty is given.
summary_of_the_review: A paper with some potential whose main problems are currently in its presentation.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the local curvature of NN loss landscapes in the existence of scale-symmetries. The main contributions are on the theoretical side, i.e., the paper proposes the concept of connectivity tangent kernel (CTK) to build a non-vacuous PAC-Bayes bound with a data-dependent and scale-invariant prior. The theory is validated by empirical computation of the bounds vs practical errors using an accompanied Linear Laplace algorithm, and such algorithm is also tested on some Bayesian NN benchmarks to show practical usefulness.

Reviewers all agree that the theoretical contributions of the paper are novel and significant, for which I agree. The provided bound is non-vacuous, and the insights there also lead to a practical algorithm for BNNs.

The main concerns within reviewers are the clarity of presentation (beyond grammar issues) as well as unclear descriptions on the algorithm's implementation details.

I recommend the authors to go for a careful revision process for the final camera ready. The paper's presentation was improved during the discussion period, but still it needs edits to achieve better communication of the results.
justification_for_why_not_higher_score: Theoretical contributions are great, however, the developed algorithm following the theoretical insights doesn't seem to show significant advantages yet. Also the current presentation is still a bit difficult to read and understand.
justification_for_why_not_lower_score: I think the new concept of connectivity tangent kernel and the new theoretical results with non-vacuous bounds are great to be recognised by the Bayesian Deep Learning community and beyond.
Decision: Accept: notable-top-25%