Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a novel set/distribution representation architecture DIDA, which leverages pairwise embedding of the set’s elements. The method can be used to represent discrete and continuous distribution representation. The authors also provide the theoretical proofs of the universality of the invariant layers, the local consistency. The experiments show that the architecture improves some dataset representation tasks

On quality: A single idea was developed and well-executed in this work. The theoretical considerations are on point and improve the understanding of the applicability of the architecture.

On clarity: This idea is rather clear but the writing and the structure of the paper are sometimes difficult to follow. For example, without a previous background in the field, it is quite hard to understand why some theoretical considerations were made. It is also difficult to understand/verify some parts of the proofs that refer to the appendix, which is missing. 

On originality: Previous works on distributions representations, only consider quantities that are related to their first moments. Using pairwise interactions mainly leads to considering second moments when representing a distribution. In that sense, the paper brings some originality to the field. By also making small adjustments in their theoretical analysis, the authors make the method general enough to be applied to distributions instead of points of clouds.

Questions/Concerns:
Building the representation of pairwise interactions alone can lead to representations that ignore the first moments of the distribution. To fully characterize a distribution, all the moments should be considered (or at least the first and the second moments in your case). 
Clearly, the complexity here is O(N^2), so how do you scale your method to large sets/ distributions?
Why didn’t try classical point cloud benchmarks? 

review_title: Official Blind Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper presents a neural network layer designed to process distribution samples that is invariant to permutations of the samples and the features. The proposed method is compared empirically to DSS, which achieves the same types of invariance but is restricted to point sets rather than discrete or continuous probability distributions. The two tasks used for the empirical evaluation in the paper are: a) patch identification (are two blocks of data extracted from the same original dataset?) and b) model configuration assessment (is one configuration of a learning algorithm going to produce a more accurate model for a particular dataset than another one?). On the first task, the paper compares to models built using Dataset2Vec embeddings as well as DSS. On the second task, the paper compares to handcrafted features as well as DSS. In both tasks, the proposed method produces more accurate predictors than DSS, etc. The paper also has some theoretical results regarding the universality of the proposed architecture and its robustness w.r.t. Lipschitz-bounded transformations. 

A weakness of the paper is that its primary theoretical advantage over DSS (according to my limited understanding) is that it is applicable to distributions rather than just point clouds, but the experiments only consider point clouds (presumably to be able to compare to DSS). The main selling point is then that the proposed method outperforms DSS in this setting in the experiments. However, why this is the case is not clearly explained in the paper. The paper itself states that DSS is a special case of the proposed approach. If possible, an ablation study showing which particular aspects of the new method contribute the most to the observed difference in predictive performance seems appropriate.

Page 3 refers to "Remark 5", but this remark does not appear to exist.

Rather than using the handcrafted features directly, it would be useful to train an embedding network (e.g., a Siamese network), to yield better embeddings for the two tasks concerned. This would be an obvious approach from a practical point of view that is not considered in the paper. 

Why are handcrafted features not included in the first task (Table 1)?

Why is Dataset2Vec not included in the second task (Table 2)?

The Dataset2Vec results in Table 1 are from (Jomaa et al., 2019) but Appendix D.2 states that the publicly available implementation of Dataset2Vec was used. For what? Also, are the results shown in the table for DSS, etc., obtained under exactly the same experimental conditions as those used in (Jomaa et al., 2019)? This is important to enable a fair comparison.


review_title: Empirical evaluation could be improved

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary:

The paper proposes a new deep learning architecture that is invariant under permutations of both the data points and the features. The paper shows that this new architecture also has the universal approximation property. Empirical experiments were performed to demonstrate the effectiveness of this new architecture.

Overall, the paper seems to be well-motivated. It is also technically sound and the presentation of the idea is clear. I have some comments that are detailed below.

##########################################################################

Comments: 

- One of the main features of the proposed architecture is that it is invariant under the permutation of the data features. While it is intuitive that the results should be invariant under the permutation of samples, I am not fully convinced why it is desirable for the architecture to be invariant under the permutation of features. Are there some solid motivating use cases? 

- It seems that the proposed architecture is related to kernel methods. Particularly, the interaction functional \phi is similar to a kernel function. The authors should discuss the connection between their method and kernel methods. 



- In Section 2.3, the proposed architecture uses one invariant layer. However, in the experiments, two invariant layers were used. Why do we need one more invariant layer in the experiments? 

 
##########################################################################

Minor comments: 

- Line 6 in abstract: avoid using abbreviations in the abstract ('w.r.t.' --> 'with respect to')

- Section 4 1st paragraph last line: "allocated ca the" --> "allocated the"

review_title: Overall a reasonable paper

final_score: rating: 6: Marginally above acceptance threshold
review_content: The method introduces the DIDA architecture to learn from distributions and be invariant to feature ordering and size.  The authors extend the ideas proposed by Maron et al. (2020) to the continuous domain and generalize their results.  The experiments are done on two tasks.  The patch identification (out-of-distribution test) clearly show the invariance to feature and dataset size. Nevertheless, it is not clear whether the method is invariant to feature permutation.  The performance model task shows properties of the architecture to predict global structures of the dataset within their meta-features.

Pros:
+ The paper is well written and easy to follow (there are some minor errors or descriptions that need to be improved, but they are not major issues).  
+ The extension of Maron et al. (2020) is interesting and provides theoretical arguments.  

Cons:
- On the other hand, the experimental section is weak.  Since the main claim is the invariant meta-features (and architecture) to permutations, I would expect to see some experiments showing it.  I see the theoretical guarantees given, but an experiment showing the improvements and benefits will make the results more robust.
- The experimental protocols need to be clearly defined.  If space is an issue, I recommend using the appendix for the details.  Despite that, authors manage to show improvement over Dataset2Vec and DSS methods.  In their current form, I found it will be difficult to reproduce the experiments.

Due to the problems on the experimental details, and simple tests I'm giving the paper a score 5.

Comments:

- I found the definition of $\sigma_X (x)$ rather strange since it depends on its inverse (i.e., it is circular).  Are you just saying that $\sigma_X$ is a permutation feature-wise of x?
- I found the bracket notation rather misleading in (1).  It seems that you are concatenating the output of $f_\varphi$ instead of creating a set for the discrete distribution $\mathbf{Z}_n$ ($\mathbb{R}^r$).
- It is not clear the shape of the matrix $A_u$.  Assuming the concatenation of the slices of $x$ to be a $2 \times 1$ column vector, and $b_u$ a column vector $t \times 1$, then $A_u$ should be the transposed of what is stated, i.e., $t \times 2$.  Review your notation convention and be clear on what type of vector column/row you are using, and how the dimensions of your matrices are given.

- What is the exact training protocol for the samples in the given datasets when training to extract the meta-features?  
- Are you applying a particular set of permutations $S_{d_X}$ to the inputs (or features) while training?  
- Are the DIDA networks shared for the patch identification task?  Are you training them simultaneously with the "meta cross entropy loss" (5)?  In the case of the patches, how are they selected?  It is not clear what you mean by "retaining samples with index $I \in [n]$".  Are you doing something else than extracting a subset of the features in the original sample?  I can visualize a patch in an image or 2D data, but if the data is in $\mathbb{R}^{d_X}$ is not straightforward.  Hence, a proper protocol for the extraction is needed.

- Your evaluations don't mention if you test for the performance given permutations at testing time.  Are you evaluating your method with different permutations at testing time?  What is the performance in this case?  It will be interesting to see the actual invariance working experimentally.

- In the performance modeling task, it seems from the description that the classifiers are trained directly on the dataset $\mathbf{z}$.  However, the bottom right of Fig. 1 seems to show that the classifiers are trained on the DIDA output, i.e., the meta features.  Which one is it?  Make them consistent.


Minor comments:
- Your abstract shouldn't contain citations, since most of the time it will be read outside of the paper, where the citations are missing.
- Use appropriate textual and parenthetical citations.  E.g., "by (Qi et al., 2017; Zaheer et al., 2017)" should be textual instead of parenthetical.
- Typo P2 p2: "characteristcs"
review_title: Interesting extension of previous work, but the experiments could be more robust to show the claimed invariances

Meta-review: This paper invariantizes distribution based deep networks by using pairwise embedding of the set’s elements.  The idea is inspired from De Bie et al. (2019), which allows invariance to be incorporated through the interaction functional.  Although the paper is well executed with solid theoretical analysis and solid response to the reviewers' comments, the novelty is limited, and reviewers have concerns with experiments and presentation.


Decision: Reject