Venue: NeurIPS 2022 Conference

Reviews:

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: This paper gives generalization bounds on equivariant models for general groups.
Generalization bounds for equivariant models in the case of finite groups were given by Sannai et al. but generalization bounds for general groups were not known. The boundary is described by an invariant called multiplicity.
This attempt is new to the best of my knowledge.

strengths_and_weaknesses: The author should first note and cite that generalization bounds are given for finite groups by Sannai et al.

Strengths
This paper differs from Sannai et al. in that it deals with equivariant models that are not limited to finite groups.
Furthermore, the bounds in this paper use information on the multiplicity of irreducible representations used in the model. This is commendable.

Weaknesses
On the other hand, the right-hand side still has some parts that have not been fully calculated, such as multiplicities.
As it is, I do not believe that any useful findings have been obtained.
Overall, the results are not considered significant.
questions: According to Sannai et al. the generalization gap is obtained by the number of coverings of the quotient space for the group action. Can you see that it is tighter than its bounds?
limitations: Properly addressed.
review_title: null

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: The authors provide a generalization bound for a class of equivariant neural networks. The generalization bound extends prior bounds in the PAC Bayes literature. The prior PAC Bayes bounds were achieved by applying perturbations to weight matrices and studying the overlap of the posterior with the prior in the standard PAC Bayes setting. Here, perturbations are applied to parameters in the Fourier regime, which is parameterized much more sparsely than the real regime due to properties of linear equivariant layers as a consequence of Schur's Lemma. Their results indicate that the generalization bound they construct scales better with "group-related" parameters and may help explain generalization for invariant and equivariant models. 
strengths_and_weaknesses: I was asked to review this paper under short notice and only over a couple of days; therefore, I was only able to read through the main paper. Proofs and mathematical details were not checked. 

Overall, I commend the authors for taking on the task of obtaining generalization bounds for equivariant neural networks. A theoretical understanding of GCNNs is mostly lacking and the results here would take a relatively big step in helping to explain why generalization occurs. The results are definitely new and interesting, but I fear at times the organization and presentation of the paper lets it down. In the short time I had to review this paper, I struggled to understand the main theorem enough to really analyze it in full. The notation and basic setting also took too long for me to comprehend. The mathematical results in this paper are potentially very strong, but I think the authors need to re-organize and write the paper more cleanly for the insights to come through. For this reason, I slightly lean towards rejecting the paper, but welcome a discussion from the authors. Since I only have had a very short time to review this paper, I am open to changing my mind.

Strengths:
- Generalization bounds, specifically for GCNNs, are hard to find. I, at least, am not familiar with any that specifically look at the architectures the authors analyze. To me, this is an original contribution of the authors' paper.
- It can be challenging to analyze GCNNs theoretically since the group equivariance property adds yet another constraint to the theoretical analysis. The overall framework and mathematical tools the authors use to attack the problem may be applicable beyond the specific problem of generalization that the authors study.

Weaknesses:
- As a general point, there is little in the way of examples or intuition in this paper. The formula for the generalization bound is quite long. To add onto this, there are multiple norms within the generalization bound which can be challenging to understand even for readers who are familiar with GCNN literature. Comparing this to the bound in the Neyshabur et al. paper, it seems the major difference is in the Frobenius norm term with the dimension of the irrep dividing this factor. Is there anything else that has changed significantly? Is there a simple example where the authors can mathematically show their bound improves upon the Neyshabur et al. bound? For example, what happens with the cyclic group where we know all irreps are dimension 1? 
- After reading through the choice of equivariant neural network in section 3.2 (and a brief foray into appendix B), it took me a very long time to understand the setup of the basic equivariant layer. As I understand, the authors chose the given parameterization to be as general as possible with their equivariant layer. However, it is very challenging to understand this parameterization without digging into the details of the appendix. It would be nice if this part of the paper were self-standing and a visual example would help greatly to understand notation. 
- It seems that the equivariant parameters here are taken in Fourier space. This may be needed for proofs but as far as I can tell, this is only way to parameterize layers and not necessarily the most common. For example, even in standard convolution (i.e. over cyclic group), filters are parameterized over a sparse set of local elements. This is not necessarily "easy" to reconstruct in the Fourier domain as it would require enforcing parameter sharing across frequencies (i.e. just training over parameters in Fourier space will break the locality). Resulting perturbations to obtain generalization bounds may also ignore this locality in this case as enforcing perturbations in Fourier regime will not maintain the locality of the filter. The authors should at least comment on this point and be clear about the parameterization and its relevance to the models used in practice. This, after all, has obvious implications on generalization.


Smaller comments:
- The authors should at least state one commonly used architecture which follows the parameterization that they have selected both to aid intuition and to better ground the findings. 
- Figure 3 is hard to read. The font size is very small and the 3-D plots are hard to follow.
- Similarly, figure 2 is quite crowded and in need of simplification and larger font.
- Line 188: [18] should be [7]?
- Line 240: section reference ??
- Line 218: two periods
- $\beta$ in equation 12 is raised to the power $2L$ but then in the definition of $\beta$, it is taken to the power $1/L$. Why not just ignore the added $L$ factor?




My recommendations to the authors on how to make the paper more readable:
- Adjust section 3.2 to make it clearer how equivariant operations are parameterized. Start from basic definitions of convolution (e.g. in Fourier or real regimes) and then explain how the parameterization that they choose is equivalent to a specific parameterization in the Fourier or real regime. Give an example of an existing architecture to aid intuition. State whether parameterization in the form analyzed can be restricted locally (e.g., restricting to sparse set of irreps is not necessarily equivalent to a sparse real support as stated earlier). Some of the information currently there can be relegated to appendix (e.g. only look at $c_\psi=1$ case and relegate rest to appendix).
- Provide intuition behind the generalization bound by perhaps bounding further parameters or looking at a special case where some of the terms become constant. E.g. fix a certain number of layers and then look at the dependence on the other parameters.
- Figures are too crowded right now. it is hard to read any of the figures as they stand and they take up too much space. I would have preferred to have more details on the architecture used to train networks and how that architecture varied for the various points in the figures. Also, a more complete description of how the comparison bound was calculated would be helpful. 



---
**Post-feedback changes** 
I am upgrading my score to a weak accept after the authors' valuable update to the paper and their comments to my feedback. I still have some concerns about the presentation of the paper and the limitations which I have listed in my response to the authors' comments below. 
questions: - Have the authors compared to existing generalization bounds for CNNs? This could be a nice empirical analysis to compare to a special case of equivariant models.
- Are the y-axis values in figure 1 and figure 2 interpretable in any way. It seems that the complexity quantity is actually an order of magnitude or more smaller for the non-equivariant bound. Perhaps constant factors are not included here? This is concerning if the authors are trying to argue that the equivariant generalization bound outperforms the non-equivariant one it is inspired from.
- I assume results here only hold for finite groups? If so, this should be stated explicitly.
- Do bounds here inherently rely on invariance in the underlying model class one wants to learn? For example, if the final layer is fully connected making the network not invariant to the group action, does the bound suffer?
- From my understanding, it seems the bound is stronger when the dimension of an irrep in the parameterization is large and the multiplicities are small. Is this correct? On a related point, when all mulitplicities are $1$ and all irreps are dimension $1$ like in standard convolution over cyclic group, is there any advantage to the proposed bound in theorem 4? It seems that case reduces to the Neyshabur et al. bound as far as I can tell. If so, this would be nice to point out for intuition. Also, it would be interesting to explore whether architectures used in practice actually follow this type of structure.
limitations: All limitations are stated in other parts of this review.
review_title: null

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 work introduces a novel PAC-Bayes bound for equivariant networks in which the feature transformation is determined in terms of groups irreps.  
The authors propose experiments in which the bound is shown to correlate with the generalization error, and the effect of group size, multiplicity and degree of the layers’ irreps is studied. 
strengths_and_weaknesses: The paper, despite the technical nature of the topic, is mostly clearly written. The assumptions are clearly stated and the proofs in the appendix relatively easy to follow, although I did not check every single step. The paper addresses an interesting topic, that is, the derivation of PAC-Bayes bound for equivariant networks. 

I find it relatively hard to understand the motivation behind some technical assumptions (see section below for an example) about the setting for proving the theorem. I would appreciate if the authors could provide some more motivation behind their choices, or highlight choices that are made purely for a technical standpoint (i.e., it is possible to prove).

questions: I wonder if the assumption of homogeneity is too restricive. Can a bound be derived while relaxing this condition?

I would invite the authors to include some more relevant literature in their related work section. For instance:
“Generalization bounds for deep learning”, Valle-Perez and Louis and reference therein.
limitations: The authors point out that, experimentally, their bounds do not decrease with the size of the training size, a fact that should be actually expected. Do the authors have a theoretical explanations/hypothesis for it?
review_title: null

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 generalization bounds of equivariant networks using the PAC-Bayes framework. The principal contribution of this work is an extension of the generalization bound from Neyshabur et. al 2018 to incorporate equivariant architectures by leveraging group and representation theory which allow the authors to characterize the bound using irreducible representations and their multiplicities. The authors also provide an empirical investigation of their generalization bounds on synthetic datasets as well variations of the MNIST dataset.
strengths_and_weaknesses: The main enjoys many strengths, the first of which is that the main contribution is presented in a clear and coherent way. Characterizing the generalization properties of equivariant networks is both an interesting direction and a needed one as the role of symmetry as powerful inductive biases are missing in the generalization literature. The main theorem and surrounding lemmas seem to be correct---although I did not check the technical details of Theorem 4.4 for correctness in the appendix as I did for the lemmas---and provide a sharp reduction in the hypothesis space and thus give tighter bounds. 


The main weakness of this paper is that it seems that the authors missed the page limit for this year's NeurIPS is 9 pages and the current draft of the paper is considerably shorter (7.5 pages roughly). This is problematic because there are certain areas in the writing which could benefit from more detail. Chief among these is the experimental section, the plots in Fig 1 and 2 are incomprehensible and their explanations in the text don't add important details. For example, it seems row 2 in Fig 1 has a smaller generalization bound but the caption says that this is the bound obtained from a naive application by Neyshabur et. al 2018? There are also minor grievances that add to an overall lack of polish such as Equation 18 referenced in the main text to be an inequality is not the correct one being referenced in the appendix. There are also broken references (e.g. line 240 in the main text) and minor grammar mistakes all over. Given the additional page limit I encourage the authors to do the following, expand the experiment section and add more clarity. Add the details or bound of Appendix E to the main text as a way to contrast the tighter bound derived in the main text. Finally, provide a better proof sketch of the main theorem to the main text as much of the detail is completely committed (e.g. $\eta$ is not defined in the theorem). My current score is a reflection of the current status of this paper which appears to be a bit rushed and not complete. If the authors can adequately improve upon these the score may change accordingly.
questions: From a technical point of view, the authors primarily work with $\rho_{\text{reg}}$ in the experiments which amount to the use of group convolutions as in Cohen et. al 2016. How does the current generalization theory change when we move to Steerable G-CNNs that $\textit{do not}$ use these representations but are built using say irreps, quotient reps, etc ... Secondly, another important symmetry group for ML purposes is $\mathcal{S}_n$ which is the symmetric group on $n$-elements. These can be used to define general permutation equivariant networks [1]. Can the authors bridge how their theory applies to these networks?


[1] H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In
ICLR, 2019
limitations: N/A
review_title: null

Meta-review: metareview: This is a borderline paper studying an interesting question around generalization bounds for equivariant networks. Initially there were significant concerns around presentation of the key results and related work. During the rebuttal phase authors updated the manuscript as per reviewers suggestions, resulting in a significantly better manuscript. I applaud the efforts of all the reviewers who engaged with authors leading to a better submission. One reviewer still kept their negative score, but other reviewers and I believe their concerns were addressed in the updated manuscript. 

Overall I recommend acceptance and it is important that the authors revise the manuscript highlighting the key assumptions upfront about the Fourier space following Reviewer fd7r's suggestions.
confidence: Less certain
Decision: Accept