Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: This paper provides generalization bounds for permutation invariant neural networks where the learning problem is invariant to the permutation of input data. 

Unfortunately, the technical value of the content and its novelty is very limited since the proof reduces to a very basic argument that counts invariances (which is simply n! where n is the number of invariant dimensions) and uses a standard approach to give a generalization bound. Therefore, I don't think the results does not help us with better understanding of permutation invariant neural networks. 

Unfortunately, the paper has several typos and mistakes as well. Another non-technical issue is that apparently authors have removed the ICLR format and reduced margin to fit the paper in 10 pages which is against the spirit of page limit.

***********************************

After author rebuttals:

After reading authors' response and reading the proofs, I realize that the formal proof is not trivial and requires more work that I assumed. However, I do not understand how this work can improve our understanding of permutation invariant networks. Therefore, I think the contributions are not significant enough for publication and my evaluation remains the same.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper derives a generalization bound for permutation invariant networks. The main idea is to prove that the bound is inversely proportional to the square-root of the number of possible permutations to the input. The key result is Theorem 3 that bounds the covering number of a neural network (defined under an approximation control bound, Thm 4) using the number of permutations. The paper proves the theorem by showing that the space of input permutations can reduced to group actions over a fundamental domain, and deriving a bound for the covering number of the fundamental domain (Lemma 1), which is then extended to derive the same for the neural network setting. For the permutation invariance setting, the fundamental domain is obtained via the sorting operator. 

Pros:
1. The paper appears to be mathematically rigorous, and at the same time, is straightforward to follow, with useful intuitions provided whenever required. 
2. The provided theoretical result perhaps extends the work on universal approximation theorem for permutation invariant networks in Sennai et al, and Maron et al., 2019. Further, the generalization bound for permutation invariance is new to my knowledge.

Cons:
1. While, the proof appears to be novel for permutation invariance per se, however I do not think the main findings in this paper or the proof approach are sufficiently novel. For example, generalization bounds under invariances have been explored previously, perhaps the most related to this paper is [a] below that already shows (in a similar vein as this paper) that the bound decreases proportional to 1/\sqrt(T), where T is the number of invariances used. While, that work uses affine transformations of the input from a base space for the invariances (which this paper calls fundamental domain), the current paper uses permutation invariance and thus gets the bound proportional to 1/sqrt(n!). In the context of this prior work, the contribution of this paper appears incremental. The paper should cite this work and contrast against the results and proof methods in it.

[a] Generalization Error of Invariant Classifiers, Sokolic et al., ICML 2017.

2. The paper has several typos and grammatical errors through out, which are easily fixable though!

Overall, this paper is technically rigorous, and novel in its very specific context of deriving the generalization bounds for permutation invariant networks. However, in the broader context of invariances in general and their bounds, the contribution appears to be marginal. 
review_title: Official Blind Review #1

Meta-review: This work proves a generalization bound for permutation invariant neural networks (with ReLU activations). While it appears the proof is technically sound and the exact result is novel, reviewers did not feel that the proof significantly improves our understanding of model generalization relative to prior work. Because of this, the work is too incremental in its current form.
Decision: Reject