Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper aims to establish novel theoretical properties of known point-based architectures for deep learning, PointNet and DeepSets. To this end, the authors prove a series of theoretical results and establish limitations of these architectures for learning from point clouds. 

Unfortunately, due to a delay with my review, I cannot afford the joy of carefully examining the proofs. 

I do not find significant practical value in the obtained results. While the theorems proved in the paper are original and novel, they are a refinement of the already known results regarding approximation theorems for PointNet and DeepSets, respectively, hence only a marginal improvement in understanding these function classes. 
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This work examines the fundamental properties of two popular architectures -- PointNet and DeepSets -- for processing point clouds (and other unordered sets). The authors provide a new universal approximation theorem on real-valued functions that doesn't require the assumption of a fixed cardinality of the input set. They further provide examples of functions that can't be mutually approximated by PointNets and DeepSets.

- It is important in order to know the representational power and fundamental limitations of basic algorithmic building blocks. However, for the two base architectures that are examined in this work, UATs where already provided in the original manuscripts. The presentation in this paper does remove the assumption of a fixed cardinality, but since this seems to be a mild assumption, it is not clear what is gained by this (beyond mathematical elegance). The paper doesn't give any hints here.

- The paper shows two specific functions, where one can be approximated by PointNet but not by DeepSets and vice-versa. The authors again note that this might vanish when a fixed cardinality of the input point cloud is assumed. Again, it seems that this is a mild restriction and I'd like the authors to elaborate on the importance of removing this restriction.

- The paper is clearly targeted at a specialist audience and invokes dense and advanced mathematical concepts. It might find a better audience at a venue that is more specialized in this type of work (e.g. applied mathematics or more theory-focused machine learning venues).

Summary: UATs are important and interesting, however, they do exist for the architectures that are targeted in this paper. It is not clear what is gained by the main difference, i.e. removing the cardinality. I'd be grateful if the authors could comment on this. 

Disclaimer: While I believe to have a reasonable mathematical background, I'm not an expert in this field and my assessment is primarily based on the bottom line of these proofs.

=== Post rebuttal update ===
I'd like to thank the authors for their efforts and additional insights. The additional illustration improves the accessibility of the paper. However, the rebuttal does not alleviate my concerns about additional impact beyond the UATs in the original paper. I thus maintain my recommendation of weak reject
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: PointNet (Qi et al, 2017) and Deep sets (Zaheer et al, 2017) have allowed to use deep architectures that deal with point clouds as inputs, taking into account the invariance in the ordering of points. However, existing results on their approximation abilities are limited to fixed cardinalities. This paper removes the cardinality limitation and gives two kinds of results:

1.	PointNet (resp. Deep sets) can approximate uniformly real-valued functions that are uniformly continuous with respect to the Hausdorff (resp. Wasserstein) metric;
2.	Only constant functions can be uniformly approximated by both (PointNet, Hausdorff metric) and (Deep sets, Wasserstein).

This paper brings a valuable theoretical contribution to the existing state of the art of their approximation abilities. With some improvements, I am willing to increase the score.

1.	The introduction lacks insight into the literature on point cloud or measure networks, including in practice, which would motivate the subject and place it more precisely within the literature.
2.	Notations in the section 2.4 make the reading particularly unclear. Notations should showcase the result that theoretically, only two hidden layers (with appropriate definitions) are needed.
3.	The paper lacks an experimental section. It would be interesting to investigate empirically the limitations of these architectures, for instance by playing with the diameter and center of mass functions as suggested in 3.3.

- Post rebuttal: the authors have addressed 3., therefore I am leaning towards accept.
review_title: Official Blind Review #2

Meta-review: The present paper establishes uniform approximation theorems (UATs) for PointNet and DeepSets that do not fix the cardinality of the input set. 

Two nonexperts read the paper and came away not understanding what this exercise has taught us and why the weakening of the hypotheses was important. The authors made no attempt to argue these points in their rebuttals and so I went looking at the paper to find the answer in their revisions, but did not find it after scanning through the paper. I think a paper like this needs to explain what is gained and what obstructions earlier approaches met, and why the current techniques side step those. One of the reviewers felt that the fixed cardinality assumption was mild. I'm really not sure why the authors didn't attack this idea. Maybe it is mild in some technical sense?

What I read of the paper seemed excellent in term of style and clarity. I think the paper simply needs to make a better case that it is not merely an exercise in topology. I think the result here is publishable on its own grounds, but for the paper to effectively communicate those findings, the authors should have revised it to address these issues. They chose not to and so I recommend ICLR take a pass. Once the reviewers revised the framing and scope/impact, provided it doesn't sound trivial, I think it'll be ready for publication.


Decision: Reject