In this paper, we develop a theory about the relationship between Ginvariant/equivariant functions and deep neural networks for finite group G. Especially, for a given G-invariant/equivariant function, we construct its universal approximator by deep neural network whose layers equip G-actions and each affine transformations are G-equivariant/invariant. Due to representation theory, we can show that this approximator has far fewer free parameters than usual models.
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)