Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the expressivity of a representation constrained by group equivariance. The authors first use a classical notion of the perceptron capacity to offer a quantification of the expressivity. Then, an algorithm is designed to efficiently classify the $\pi$-manifolds. Besides, the authors further apply the theoretical results to some practical examples and give bounds on the capacity when pooling operators exist.
main_review: **Strengths**:
- The authors give a fantastic lemma which implies that classifying the $\pi$-manifolds is equivalent to classifying their centroids.
- The authors give some useful examples to help to understand. They then also compare the expressivity of some different representations.
- The idea is novel. This paper gives a new perception of how to describe the expressivity of a representation.

**Weaknesses**:	
- Some mentioned notations are not defined in the main text, even if they are in the main theorem. It brings some problems for understanding. I can not find the definitions of "in general position" and "range" in theorem 3.2. If there is a notation table, it may be easier for reading and understanding.
- Theorem 3.2 is true only when the centroids are in general position. Since I can not find the mathematical definition of "in general position", I do not know whether this assumption is too strong.
- The authors do not give further theoretical analysis about Eq. (1).
- The authors propose an algorithm to classify the $\pi$-manifolds and claim it is efficient. Although the algorithm seems efficient, the authors did not give any analysis about the time complexity.
summary_of_the_review: Overall, I vote for rejection. The idea is novel and interesting. However, I think this work lack sufficient theoretical and empirical analyses.

-----

The authors have carefully addressed my concern. My score is thus raised to 6.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides an analysis of network capacity of group equivariant NNs. The analysis is based on determining the fraction of linearly separable dichotomies. It is found that this fraction is determined by the the number of trivial irreps that appear in the decomposition of the representations into irreps. I.e., the fraction is determined by the number of sub-spaces that are left-invariant by the group action. The paper is intuitive, well written, and theoretical results are confirmed by experiments.
main_review: Strengths:
- The paper is well embedded in literature and the problem formulation is clear.
- The presentation is clear (though some jargon could be better explained, see below).
- The examples are helpful.
- The paper is reproducible (see attached code).
- The paoer us well written and intuitive.

Weakness:
- The presentation of the main idea could be better organized (see minor comments below).
- The result is quite intuitive in hindsight, but when reading the paper I struggled with notions of averaging representations over G. I started working out what it meant and figured that for non-trivial irreps the average is zero (for compact groups at least). Then, only later on in the paper (page 6) it is indeed mentioned that his is the case. This kind of intuition would have been nice to receive early on since, if I understood correctly, this is at the core of the approach: it explains why it is all about the trivial irreps (all about the invariant subspaces).
- I'm not fully sure about the relevance of the "one-shot learning" section 5.3. It seems to avoid the need to generate (augment?) the entire dataset/orbits from the reference points $r^\mu$. However, since the capacity is determined by invariant subspaces, and one typically indeed designs G-CNNs that are at the final layer invariant, each point in the orbit will be mapped to the same representation anyway. Does the algorithm therefore solve an non-existing problem? (I'm probably misinterpreting here and would be happy to stand corrected if so)

Regarding Jargon:
It would be nice to help readers that are new to these kind of analysis with a bit more intuition on some terminology.
- E.g., it would have been nice to provide a definition of “dichotomy”, it took me a while to figure out what is precisely meant with it (still not fully sure). Is it just the dataset, pairs of equivalence classes + label. Or is it an instance of a possible dataset?
- Hopefully the “fraction of linearly separable dichotomies” (top page 5) is then also clearer. 
- What is “a datapoint in general position”? (general position?)
- Section 4.3. What does coprime mean?

Minor points:
- Section 4.3. What is idea behind the direct sum representations, isn’t this just considering the direct product of two groups that may as well be analyzed independently.
- Typo last sentence 5.1.1. “dichotomies if” -> “dichotomies is”
- I find Figure 2 hard to interpret, mainly because of the vertical axis being “capacity”. When saying things like “max pooling reduces capacity by a factor between ¼ and 1” I expect this factor to be apparent on the vertical axis, but it seems to refer to the bending point (at some alpha) where capacity dives below 0.5. I think the further this point is to the right, the more complex datasets the method could represent and it indeed reflects capacity in that sense. But then the vertical axis is confusing to me, shouldn’t this be the fraction f?
- One of the conclusions is that pooling may reduce capacity. The subsequent sentence says “This quantification of expressivity could prove a valuable tool in building new G-CNNs…” In what sense is it valuable. Could you be more explicit about what possible implications does this have on NN design. 




summary_of_the_review: All in all the paper is a nice read and provides interesting insights. The paper is sound and the proofs are good to follow. I consider it a high quality submission that could, however, still be improved a bit in its presentation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses an underexamined area, the question of expressivity in equivariant neural networks.  In general, there is a large gap between our theoretical understanding of expressivity and generalization for non-equivariant networks and that for equivariant ones; this paper helps to close the gap.  In particular, given a set of equivariant representations coming from an equivariant architecture, the authors determine how expressive these features are for an invariant binary classification problem.  To do so, they define a reasonable generalization of perceptron capacity for invariant classifiers and compute it.  The answer turns out to be relatively simple and is mainly determined by the multiplicity of the trivial representation in the group representation type of the equivariant representation, which is not difficult to compute.  The authors also consider the case of useful but not quite equivariant operations such as pooling. Lastly, they provide a convincing empirical verification of their results.
main_review: ### Strengths
- This paper contributes to an underexamind area, theoretical analysis of expressivity of equivariant neural networks.  In particular, there is a large gap between what we know for non-equivariant and equivariant models, and this papers helps to close that gap. 
- The definition of perceptron capacity for invariant models is logical and useful.
- The result the authors obtain for the capacity of invariant models is simple and easy to compute.  This means it is easier to interpret and potentially useful. 
- I appreciate that operations such as pooling, which do not fit as nicely into the theory of equiv. NNs, but are still important, were considered.
- The empirical evaluation is quite convincing, suggesting the theory is correct.
- The related works section is actually a very nice and comprehensive survey of what (limited) theoretical work has been done on equivariant models. 

### Weakness
- While I think it is important to examine the model capacity of equivariant models under the assumption of symmetrically distributed data, I’m not sure if perceptron capacity is the most relevant measure.  In some sense, this is evidenced by how simple the answer turns out to be depending only on the representation type of the final layer.  I wonder if other measures of capacity might be more relevant for understanding difference in model architecture?
- I’m not sure how much section 4 adds.  The examples are essentially just computing the multiplicity of the trivial rep in some group representations.  This is fairly straightforward using the peter-weyl theorem or characters.  

### Questions
- What are the practical implications of the main theorem?   Is it better to add extra copies of the trivial representation to the final layer of the NN? 
- Would the analysis of local pooling also be relevant to strided convolutions? 
- If we assume the perceptron given by w is invariant, does this affect the result? (I guess not.)  


### Small Notes
- Some of the citations in section 3 are really to references, not to the authors of the results.  This is okay, but it should be clarified. 
- the definition of fixed point subspace does not need “largest”.  The definition is pointwise, so you can just define $W = \lbrace w \in V | g w = w \text{ for all } g \in G\rbrace$.
- Eqn 5 has no quantifier on h 
- I don’t understand the argument for the upper bound in 5.1.2.  In particular, i’m not sure what is meant by “limiting case” or the set of points is that are equal.  Can you clarify it for me? 
- 5.2: Should it be $\rho : H \to GL(V)$ since it acts on V?  
- 5.2: It might be good to state a formal proposition here. 



summary_of_the_review: I tend towards accept due to the importance of making progress on what I see an underserved area.  However, I have some questions about the practical consequences of the work and whether other definitions of expressivity might have more potential.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This is a mainly theoretical paper that studies the capacity of equivariant representations, which is, the ability to linearly classify objects under different transformations of a symmetry group of interest.
The main result in the paper is showing that the number of dichotomies (different binary classifications) is related to the dimension of the fixed subspace of the representations, rather than the dimension of the representation.
The authors discuss several examples and also propose several usages of this theory to deep learning of symmetric objects: analysis of pooling operations and induced representations

main_review: *Strengths*

** Fundamental problem: The paper studies a fundamental property of equivariant representations. To the best of my knowledge, their results are novel. The result is also quite elegant.

** Good writing: The authors did a great job writing the paper. Specifically, the mathematical load is reduced by deferring details to the appendix, and many examples and illustrations are given. For this type of theoretical paper, the authors did a very good job.

*Weaknesses*

** Relevance to current research/challenges: I am not sure how this theoretical question is actually related to the current methods and challenges in geometric/equivariant deep learning, which uses non-linear models. I feel that section 5 is supposed to answer but I am not sure I am convinced. Another question: why is the separation of equivariant (rather than invariant) representations important? Most models use an invariant representation of the object, where (to the best of my understanding) the \pi-manifold is trivial.



summary_of_the_review: The paper targets a fundamental problem regarding the separability of equivariant representations in a pretty general setup. The theoretical results are interesting and new (as far as I know), but the relevance to current research challenges is not clear. If this issue is addressed in a revision, I would be willing to upgrade my score.

after rebuttal:
I appreciate the authors' thoughtful response. I will keep my score at 6 at this point.
review_title: null

Meta-review: The authors' provide a discussion of Cover's Theorem in the setting of equivariance.  The reviewers consider the work well explained and interesting, especially after the revisions, and so I will vote to accept.
Decision: Accept (Poster)