Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors prove universality results for permutation invariant networks: in particular for PointNet and 'normalized DeepSets'. The two classes of networks differ in the pooling layer: max pooling for PointNet and averaging for Normalized DeepSets.

Despite their apparent similarity, the authors show that these two networks approximate a different set of functions and according to different topologies (Haussdorf vs Wasserstein).
A second important contribution is that the paper shows uniform approximation results while allowing for varying number of inputs which can be potentially uncountable (Thm 3.4). This is novel compared to recent prior work which considered fixed input cardinality. It also requires different mathematical tools for achieving this. 

A third contribution comes in the form of thm 3.7 which shows these networks to be Lipschitz. Along with Thm 3.4, this allows to control the approximation error made by the network when the input signal is subsampled.

Finally, the authors identify a failure case where PointNet fails to approximate a seemingly simple function 'average' (Thm 4.2 and Lemma 4.3), thus illustrating the theory from which it is reach the same conclusion as the failure case does not belong to the set of functions that can be approximated by PointNet.

--------------------------------------------------------------------------

Update: After reading all other reviews and the authors' responses, I think still think the paper might be of interest to the community and is thus worth publishing under the condition that the clarifications asked by the reviewers are taken into account.


main_review: General comments:
- Significance: This is a significant work as it provides a clear distinction between the approximating power of two popular set networks : PointNet and DeepSets. The results have practical consequences which can be useful to the ML community for choosing the most appropriate network architecture depending on the task.
- Originality:  The work is original in that it treats both classes of networks using the same theoretical framework while still capturing meaningful qualitative differences between the two classes. 
- Quality: The proof technic relies on standard Stone-Weierstrass theorem as well as the UAT [6] and do not represent a significant challenge, but the results themselves are useful.
- Clarity: This is the weakest point of the paper. The notations are often cluttered and heavy especially in section 2. 

Detailed comments:
Notations: 
-Notations are defined at several places in section 2, which makes it difficult to localize where they are defined especially in a paper with heavy notations.
-The notations seems unnecessarily complicated for a rather simple concept in particular in section 2.4. The authors should simplify or clarify and illustrate these notations using examples.
For instance, it is hard to parse the nuances between the different notations for sets of networks as they only differ in a particular subscript or superscript : $\mathcal{N}^{\sigma}$, $\mathcal{N}^{\sigma,\tau}$, $\mathcal{N}^{\sigma,\tau}_{Max}$, $\mathcal{N}^{\sigma,\tau}_{max}$, etc.

Definitions:
The authors discuss two ways to build deeper networks either inductively or using 'deeper weights' (l:199), however, it is hard to relate these constructions to the notation that is introduced. In particular, the authors use the notation $\mathcal{N}^{\sigma,\tau}$ where sigma and tau are either nonlinearities or a collection of nonlinearities (when written in bold). However, in the latter case (collection of nonlinearities), it not clear how the set of functions $\mathcal{N}^{\sigma,\tau}$ is defined. 


Illustrative figures: 
The authors should illustrate the importance of having an approximation result that is independent on the input dimension. While the authors mention the case of subsampling a signal at different resolutions, it might be beneficial to illustrate this on simple visual examples. In particular, this could give a better intuition for failure cases in section 4.
 


Discussion of related work: 
As the authors point out, Thm 3.1 is a general known result. Can the authors explain further why the result of [11] cannot be applied for PointNet but only to normalized DeepSets?


Approximation power of PointNet:

The phrasing in l 324 suggests that PointNet is less powerful than normalized DeepSet, however, as discussed earlier in the paper, they just approximate different sets of functions (that are not really comparable) using different topologies. In that sense, thm 4.2 which quantifies the error made by a PointNet in approximating an average $ave_f$ might be misleading. Wouldn't it be possible to obtain worst case errors for normalized deepSet using a suitable function like max_f(A)?

Approximation power of standard DeepSets:
On section 3.4 : The authors mention that standard DeepSets are not covered by the proposed framework and provide a nice explanation for why this is the case in general. Could it be possible to express a standard DeepSets as a normalized one when the nonlinearity sigma is positively homogeneous (like ReLU)? In this case, it should be possible to absorb the normalizing constant in the weights of the second network.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develops universal approximation theory for deep sets / pointNet architectures which consist of the composition of a deep network on a permutation invariant aggregation of embeddings (i.e. $f(x) = \rho \circ \text{agg} \circ \phi \circ x$ where 'agg' is sum(), max() or mean()). It was already known from the original Deep Sets paper [Zaheer et al 2017] that these architectures are universal approximators of set functions on finite and countably infinite input sets, and there exist negative results [Wagstaff et al 2019] for the uncountable case. This paper refines the story in the uncountable case: it shows that the choice of aggregation function (max or mean) defines the class of functions that can be approximated in the uncountable case, and they give lower bounds on approximation power in the finite input case.
main_review: [Clarity] I found this paper frustrating to review because it's clear that a lot of careful work has gone into proving the results, but it is written in a way that makes their results almost impenetrable to those without a strong topology background. In many respects, I'm the perfect audience for this paper: I know the related work well, and am very interested in the approximation power of these methods, but honestly - if I was just reading this paper as a researcher (rather than a reviewer), I would have stopped at the end of page 3 (it is very clearly written up to that point). Now, that is a style choice that the authors are free to make, but I think it severely limits the potential audience of this work, and it's a shame because I think it could have been written in a way that teaches those readers who are unfamiliar with topology about how we can leverage existing results from topology in building approximation theorems. The prose in section 3.4 (which explains why it's hard to get the same results with sum pooling) is a good example of well-written, accessible text that I would have liked to see at the beginning of section 2 and section 3.

[Quality / significance] My main takeaway from this paper was that Deep Sets (with average pooling instead of sum pooling) and PointNet can each uniformly approximate different classes of functions (in the uncountable case) --- so the aggregation function matters --- and this difference in approximation power remains for finite sized sets (in the case of PointNet). From the counter example functions (centre of mass & diameter of a point cloud) it's intuitive that max / mean (respectively) would be the wrong choice of aggregation function, but I was not left with a good sense of what the properties of the two classes of functions are in general. I.e., given some new problem do the properties of the respective function classes give some guidance on the choice of aggregation function (as the paper suggests when it alludes to inductive biases)?

I also didn't get a good sense of the relationship between these two classes of functions. For finite sized inputs, we can smoothly vary between the two aggregation functions using a weighted sum, $\sum_{i} \alpha(x_i / T) x_i$, where the $ \alpha(x_i / T)$ is the output of the softmax function with temperature $T$ (mean and max are the limits as $T$ goes to 0 and $\infty$ respectively) --- are there analogous  weighted sums that allow us to approximate both classes of functions in the infinite case? (I am tempted to ask analogous questions about what attention-weighting schemes buy us, but it's not clear how the attention weights are even defined if you have infinitely large sets - feel free to comment if you have thoughts).

Overall, I thought this was a useful contribution that was let down by it's presentation. I don't have the background to evaluate the correctness of the theoretical claims, but assuming that they are correct, I think that it deserves to be published. Still - I would strongly encourage the authors to try make the paper more broadly accessible.
limitations_and_societal_impact: The authors are clear about the limitations of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper study the expressiveness of popular two processing models such as deepset and pointnet. This paper proves that (1) PointNet can uniformly approximate only the functions which are uniformly continuous with respect to the Hausdorff (Wasserstein) metric and (2) Only the constant functions can be simultaneously uniformly approximated by both PointNet and normalized-DeepSets when input sets are allowed to be arbitrarily large. A lower bound of PointNet to approximate the center-of-mass is proved and a toy experiment is performed to confirm this lower bound.

main_review: This is a good theoretical paper that investigates the representation power of set models when the cardinality becomes arbitrarily large. However, I am more interested in what benefit this paper can bring to practical applications.  The lower bound proved in this paper is only for center-of-mass, but in practical applications of the set, the tasks are not limited to estimate the mass center. Practitioners are also doing set compression, point cloud segmentation, classification, etc. Therefore I'd like to know how this paper could lead to the advancement of these application areas.

Also, Set Transformers [1] is the STOA model for set modeling. Can the theory introduced in this paper be applied to set transformers?

[1] Set transformer: A framework for attention-based permutation-invariant neural networks, ICML, 2019
limitations_and_societal_impact: None
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents theoretical results on two prominent architectures for representing functions on sets, PointNet and (a normalised version of) Deep Sets (or equivalently, max-pooled functions and mean-pooled functions). The authors analyse these architectures from the perspective of appropriately-defined metrics on sets of sets, and the associated function spaces. They obtain universal approximation results which show that each architecture is capable of approximating all functions which are uniformly continuous with respect to the appropriate metric. There are also interesting results on the Lipschitz properties of the architectures and on the limitations of PointNet in particular.
main_review: This paper is clearly a valuable, interesting and novel contribution to the theory of models for learning functions on sets. The architectures considered in this paper are of interest to a reasonably wide audience, and the results presented are novel, strong, and say interesting things about the approximation strength of these architectures. I was not able to check the details of the proofs for these results - my review assumes that the proofs are actually correct. I have seen nothing to make me doubt the mathematical competence of the authors.

In general the writing is clear and the paper is well-structured. The paper would benefit from a pass to check for grammar/punctuation/typos (e.g. the word "different" appears as "different different" on lines 42-43). The mathematics is necessarily densely presented, and would benefit from having more room for discussion/explanation - the page limit obviously limits what can be done here, but perhaps the experimental section could be moved to supplementary material to make room? I didn't find the experimental demonstration of Lemma 4.3 necessary to the narrative (though it is certainly an interesting illustration). Nevertheless, I don't have a strong opinion that this needs changing, and the mathematics was presented well given the tight constraints on space.

A minor point on related work: in the introduction subsection Cardinality Limitations, the authors note a lack of previous work on variable-cardinality sets. This is partially addressed (strictly speaking in the case of multisets rather than sets) in On the Limitations of Representing Functions on Sets (Wagstaff et al 2019), which the authors cite elsewhere in this paper but don't mention at this point in the paper.
limitations_and_societal_impact: This work is very mathematically focused and I don't believe it has any potential negative societal impact (except perhaps very indirectly).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the theoretical expressive power of the PointNet and (modified) DeepSets methods, on which many recent point-cloud neural-network methods are based. It proves both universality theorem under specific settings, and shows some of its theoretical limitations.

main_review: The paper clarity could be improved. The abstract could be re-arranged to make the paper's contributions more obvious. In all, I found the paper hard to follow.

The experiment used is an excellent way of showing the error bound from Lemma 4.3

Minor remarks:
1. Line 43 - "different" used twice.
2. Line 213 - the beginning of the sentence is unclear.
3. It will help if it will be stated for each theorem, if its proof is in the appendix.
limitations_and_societal_impact: The limitations are addressed in the paper. The societal impact is irrelevant.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the representation power of two prominent set-learning deep architectures: pointnet and deep sts, that differ in their pooling mechanism (max vs sum/mean). While these two architectures are universal when considering constant-size sets, their expressivity when considering sets of varying cardinalities is not yet well understood. 
The main contribution of this paper is establishing an understanding of which function spaces can be approximated by each of these architectures when set sizes vary (Both in the unbounded and bounded set size cases).

main_review: Positive points:
-- the paper addresses an important and real problem: in practice, in many applications, set sizes vary. The paper analyzes the most fundamental set learning architectures in this case.
The authors did a good job writing the paper. I especially like the introduction which discusses all the key issues and presents good motivations.  
Negative points: 
-- I found it difficult to follow the math from the paper itself without the supp. But this is understandable considering the page limit.

Additional related literature that could be of interest to the authors:
-- Other papers that discuss the universality of set networks. “On Universal Equivariant Set Networks”, “On Learning Sets of Symmetric Elements”.
-- There is an ongoing effort in the graph learning community to understand expressive power with varying graph sizes which seem to be related. “Size-Invariant Graph Representations for Graph Classification Extrapolation” “from local structures to size generalization in graph neural networks”, “Universal invariant and equivariant graph neural networks” “Expressive Power of Invariant and Equivariant Graph Neural Networks” (appendix F).
In particular, there are universality results for high-order graph networks in the variable node set size case. Could be interesting to discuss if this can be leveraged for the set learning case in this paper.

To summarise, this paper studies an important topic in a mathematically rigorous way. I support acceptance,

limitations_and_societal_impact: Discussed.
review_title: null

Meta-review: This paper gives a novel theoretical understanding on what functions "normalized" DeepSets and PointNets can represent, from a topological point of view. The work is novel and provides meaningful guidance to the community about the difference between these approaches; many of the (numerous) reviewers, however, had complaints about the clarity of the presentation as well as confusions on some specific points. It will greatly benefit the paper to take these into account for the camera-ready version.
Decision: Accept (Poster)