Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes a universal approximation theorem for functions invariant and equivariant to finite group actions. It constructs the approximations using fully-connected deep neural networks with ReLU activations. It proves a bound on the number of parameters in the build equivariant model. The proof structure uses a decompostion of G-equivariant functions into Stab(1)-invariant functions, which are represented by a particular network. 

The proof structure is reasonably well written, however more context and examples could help a reader unfamiliar with the literature. This could be achieved by proposing applications of the construction of the approximating network to a few concrete applications where equivariant representations are needed.

As-is the paper is difficult for a newcomer to the field, compared e.g. with (Maron et al. 2019b) and (Keriven & Peyré 2019) which have clearer expositions. On the other hand, the equivariant representation problem is given in more generality, stemming from finite group actions represented by actions of permutation groups.

My current assessment is “borderline” and might change in light of author responses and reviews from reviewers with more experience in this field to judge the significance of the results.

I think it is necessary to do a more in-depth comparison with respect to the existing work of (Keriven & Peyré 2019).
In this regard, I think the following could be done:
- Giving an application and the corresponding construction where the increased generality w.r.t. the graph networks of (Keriven & Peyré 2019)
- In the case of a graph network already addressed by (Keriven & Peyré 2019) , how would this construction apply and how would the constructed network compare?

What do the authors call "usual models" in the discussion of Theorem 2.3? I assume this means models that do not exploit the equivariance of the function, but this could be more explicit.

Typos:
p.5, in the discussion of Theorem 2.1: "> Then, by ... we may assume"
p.8, Prop 4.1 Proof: n devides M
p.11: Prop A.1 Proof: can be realized as a permutation action on R^n: R should be in \mathbb
p.17: “ane” instead of “and”

***
Updated review

I have the impression all 3 reviewers have had some trouble going through the main messages of the paper. Although - at least in my case - this might be partly due to limited in-depth expertise, this seems to indicates some deeper shortcomings in the writing, as well as the insights and intuitions offered by the paper, in order to be accessible to a larger audience.

I still believe the approach may have merits, however I do not recommend acceptance of the paper at its current state. In my opinion, the following points should be considered for a future resubmission:
* A friendlier introduction to the matter with more intuitions and examples where the method has interest and distinguishes itself from existing papers, e.g. (Maron et al. 2019b), (Keriven & Peyré 2019) (Review #2, review #3)
* At least 1 example (and possibly more) where the proposed method leads to a practical architecture (Review #1)
* A clearer explanation of the particular role played by Sn w.r.t. general finite groups in the construction (Review #1)

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper proposes a universal approximator for functions equivariant to finite group action. The idea is to draw a bijection between such equivariant universal approximators and those for functions that are “invariant” to the stabilizer subgroup of the output indices. Using existing results for designing universal invariant approximators, the paper then seems to suggest universal equivariant approximators in the form of neural networks. 

While this is an important topic and the paper -- to the extent that I could follow -- seems to be technically sound, I found the paper very hard to read in part due to numerous grammatical errors.

Another issue is that I don’t see why the symmetric group is treated separately from the general finite groups. If in the end, the goal is to plug in “a” universal G-invariant function, the paper could leave those details out and focus on clarifying its proposed bijection. Could you please comment? Also is there a setting in which this setup leads to a practical architecture?

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: *Paper summary* 

The authors develop a universal approximation theorem for neural networks that are symmetric with respect to the symmetric group (permutations). They also formally show that the number of free parameters is to train an equivariant network is smaller that the number in a non-equivariant network, leading to better sample complexity.

*Paper decision* 

I have decided to give this paper a weak reject. The contributions are clear and the paper is written well enough for publication. That said, the significance of the contribution is not clear to me, since there are other papers in the literature doing the same.

I must admit that the subject material is out of my region of expertise, so my judgement may be a little miscalibrated.

*Supporting arguments and questions for the authors* 

The paper is clearly written by people who have a firm grasp of their subject. The contributions are well laid out and the following proofs are clearly placed in the paper. In terms of constructive criticism, I think it would be helpful to readers to give an intuition behind why the contributions are necessary and to add a sense of the motivation behind them. This would open up the paper to a broader audience.

For me, something that was not clear was how exactly this work is different from Zaheer et al., (2017). It would be nice if these differences were spelled out for me. It was also not clear why it was necessary to present the contribution that with each symmetry you introduce you reduce the number of parameters exponentially? I guess the intuition behind this is clear, but I was wondering why this is necessary to spell out with a Theorem (2.3 I believe). What exactly doe this result imply?

In terms of clarity, the preliminaries section is well written and quite clear. I enjoyed the summary. That said, it is quite advanced, and it would be useful to point more novice readers to elementary texts, where they could brush up on their group theory. Furthermore, the grammar in places is a bit tenuous, but on the whole the writing is understandable.
review_title: Official Blind Review #3

Meta-review: The article studies universal approximation for the restricted class of equivariant functions, which can have a smaller number of free parameters. The reviewers found the topic important and also that the approach has merits. However, they pointed out that the article is very hard to read and that more intuitions, a clearer comparison with existing work, and connections to practice would be important. The responses did clarify some of the differences to previous works. However, there was no revision addressing the main concerns. 

Decision: Reject