We theoretically prove that learning with permutation invariant deep neural networks largely improves their generalization performance. Learning problems with data that are invariant to permutations are frequently observed in various applications, for example, point cloud data and graph data. Numerous methodologies have been developed and they achieve great performances, however, understanding a mechanism of the performance is still a developing problem. In this paper, we derive a theoretical generalization bound for invariant deep neural networks with a ReLU activation to clarify their mechanism. Consequently, our bound shows that the main term of their generalization gap is improved by √ n! where n is a number of permuting coordinates of data. Moreover, we prove that an approximation power of invariant deep neural networks can achieve an optimal rate, though the networks are restricted to be invariant. To achieve the results, we develop several new proof techniques such as correspondence with a fundamental domain and a scale-sensitive metric entropy.
This paper presents a derivation of a generalization bound for neural networks designed specifically to deal with permutation invariant data (such as point clouds). The heart of the contribution is that the bound includes a  1/n! (i.e. 1 / (n-factorial)) factor to the major term, where n is the number of permutable elements there are in a data example (think: number of points in a point cloud). This term goes some way towards making the bound tight.
The 1/n! factor in the bound may be an interesting development  but the novelty does appear to be limited.  Also, the authors fail to discuss that --  as part of that same term -- there is a factor: (1 / (epsilon^p)), where p is the dimension of the input and epsilon is a small error term. As p is proportional to n, and epsilon is quite small, this term could well dominate the factorial in many practical settings. A discussion of the relation between these terms is appropriate and seems to be missing.
Clarity:
In general the paper is fairly well written, but there are multiple instances of missing articles and strange idiom violations (eg. p. 4, remark 1: "such the bound" versus "such a bound")
More seriously, the proof of Lemma 1 was quite hard to follow (esp. the second paragraph). I would suggest putting less emphasis on the relatively straightforward construction of the sorting mechanism in Propositions 2 and 3, and use the space to more clearly detail the proof of Lemma 1, which is, after all, the heart of the contribution.
I also found the proof of proposition 4 too confusing to easily follow. What is the interpretation of the indices (1, ..., K) on the functions?
Finally, I would have liked to see some interpretation of the findings in a discussion section (or in an extended conclusion).   
Minor issues:
- First sentence of the abstract is difficult to parse and does not seem like an accurate assessment of the contribution of the paper. 
- Paragraph 2 of the introduction presents a sequence of argument whose logic seems inconsistent to me. There is a drift from a discussion of generalization of neural networks to a mention of work on the very distinct topic of the representational capacity of neural networks (i.e. universal approximation property of neural networks). The linking text "To tackle the quesiton, ..." is not appropriate.
- Unlike Example 1, Example 2 (p.3) is not helpful in motivating the permutation invariant neural networks. The definition makes direct reference to Proposition 2 that will not be introduced for another 3 pages. 
- In Sec. 4.1, it seems like a phi symbol is used when I believe a null symbol was intended
- Proposition 3: "max( z_1, z_1 )"  should be "max( z_1, z_2 )" with the adjustment carrying through to the other side of the equals.