Deep Sets
We study the problem of designing models for machine learning tasks defined on sets. In contrast to traditional approach of operating on fixed dimensional vectors, we consider objective functions defined on sets that are invariant to permutations. Such problems are widespread, ranging from estimation of population statistics [1], to anomaly detection in piezometer data of embankment dams [2], to cosmology [3,4]. Our main theorem characterizes the permutation invariant functions and provides a family of functions to which any permutation invariant objective function must belong. This family of functions has a special structure which enables us to design a deep network architecture that can operate on sets and which can be deployed on a variety of scenarios including both unsupervised and supervised learning tasks. We also derive the necessary and sufficient conditions for permutation equivariance in deep models. We demonstrate the applicability of our method on population statistic estimation, point cloud classification, set expansion, and outlier detection.
Summary of Review:
Although the techniques are not novel, the proofs are, and the paper seems well done overall.
I’m not familiar with the experiments / domains of the tasks, and there’s not enough description for me to confidently judge the experiments, but they appear fairly strong.
Also, the authors missed one key piece of related work (“Learning Multiagent Communication with Backpropagation” - Sukhbaatar et al. 2016).
Overview of paper:
This paper examines permutation-invariant/equivariant deep learning, characterizing the class of functions (on countable input spaces) and DNN layers which exhibit these properties.
There is also an extensive experimental evaluation.
The paper is lacking in clarity of presentation and this may hide some lack of conceptual clarity as well; for instance, in some of the applications given (e.g. anomaly detection), the input is properly thought of as a multiset, not a set.  
The proof of Theorem 2 would not apply to multisets.
Quality:
Overall, the paper appears solid in motivation, theory, and experiments. 
The proofs (which I view as the main contribution) are not particularly difficult, impressive, or involved, but they do provide valuable results.
The other contributions are a large number of experiments, which I have difficulty judging.
The take-aways of the experiments are fairly clear: 
1) expanding deep learning to solve set-based tasks can (yet again) yield improvements over approaches that don’t use deep learning
2) in many cases, a naive application of deep learning is bound to fail (for instance, section 4.3, where the position of the anomaly is, presumably, random, and thus impossible for a permutation *invariant* architecture, which I presume the baseline to be), and permutation invariance / equivariance *must* be considered and properly incorporated into the model design.
Clarity:
While the overall message is clear, the details are not, and I’ll offer a number of corrections / suggestions, which I expect the authors to address or consider.
First of all, notation should be defined (for instance, this is missing in de Finetti’s theorem).
Section 2.3 should, but does not explicitly show how these results relate to the rest of the paper.
Line 136-137: you should mention some specific previous applications, and be clear, later on in the experiments section, about the novelty of each experiment.
Line 144: which results are competitive with state-of-the-art (SOTA)?  Please specify, and reference previous SOTA.
As mentioned before, the tasks are not always explained clearly enough for someone unfamiliar with them (not even in the appendix!).
In particular, I had difficulty understanding the tasks in section 4.1.3 and 4.2.
In 4.2 I ask: How is “set expansion” performed? What does “coherent” mean? Is the data labelled (e.g. with ground-truth set assignments?) What is the performance metric? What is the “Beta-Binomial model”?
detailed comments/questions:
There are many missing articles, e.g. line 54 “in transductive” —> “in the transductive”
The 2nd sentence of the abstract is not grammatical.
line 46: “not” should be removed
line 48: sets do not have an ordering; they are “invariant by definition”.  Please rephrase this part to clarify (you could talk about “ordered sets”, for instance).
Line 151: undefined notation (R(alpha), M).
Lines 161-164 repeat the caption of Figure 1; remove/replace duplicate text.
the enumeration in lines 217-273 is poorly formatted
Line 275 d) : is this the *only* difference with your method?  Max-pooling is permutation invariant, so this would still be a kind of Deep Set method, right??
line 513: the mapping must be a bijection for the conclusions to follow!
As I mentioned, set and multiset should be distinguished; a multiset is permutation invariant but may have repeated elements.  
Multisets may be more appropriate for some machine learning tasks.
BTW, I suspect the result of Theorem 2 would not hold for uncountable sets.
Bayesian Sets is cited twice (35 and 49).
Originality:
I’m a bit out of my depth in terms of background on the tasks in this paper, and I’m not 100% sure the proofs are novel; I would not be particularly surprised if these results are known in, e.g. some pure mathematics communities.
My best guess is that the proofs are novel, and I’m fairly confident they’re novel to the machine learning or at least deep learning community.
Significance:
I think the proofs are significant and likely to clarify the possible approaches to these kinds of set-based tasks for many readers.
As a result (and also due to the substantial experimental work), the paper may also play a role in popularizing the application of deep nets to set-based tasks, which would be quite significant.