Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper starts with presenting an RNN formulation and essentially writing out the sequence of RNN applications. Not surprisingly, if these applications were associative and commutative the RNN would be permutation invariant.  Then a condition for commutativity is formulated in terms of an expectation of a difference.  Based on a prior result, it is shown that the expectation can be computed in closed form.  Although it is not shown if an RNN regularized that way is permutation invariant, since the associativity is not demonstrated, empirically it is shown that it may be already of use.

   Contributions:
   1. A regularizer for RNNs that enforces commutativity
   2. A closed form for computing it
   3. A fully learnable permutation invariant "deep" network, per an empirical demonstration

   The main contribution is the empirical demonstration of the learnable nature of the obtained function unlike the prior art (e.g.  DeepSets) where a choice of the aggregation function severily affects the results.

    The theoretical component of the paper is unclear:
      1. Section 3 is rather trivial.
      2. Theorem 3.6 is hard to connect to an RNN and the rest of the paper. Unclear why bother learning the RNN at all if it needs to converge to addition of the input and hidden state to be universal anyway.
      3. In essence, the result of the paper is a way to encourage commutativity in an RNN and a demonstration that it works in practice for encouraging permutation invariance. The other explanations make things confusing and do not seem to contribute to the rest of the paper.

Could it be that the network indeed learns addition operator?  RNNs usually are only able to operate on very small sequences because of the vanishing gradient problem, yet the proposed approach will not directly work on the more robust LSTM.

Significance or lack of the difference between the proposed method and DeepSets is unclear as the plots are missing the error bars.

 The table and the accuracies reported in Section 8 are impossible to interpret. It is unclear whether the authors done cross validation.  If so, it would be helpful to see standard deviations of the reported numbers

review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: The rebuttal did not address my concerns convincingly. There were also simple fixes that the authors could have implemented but they decided not to update the paper. I will keep my original assessment. 

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

The premise of the work is very interesting: RNNs that are permutation-invariant. Unfortunately, the paper seems rushed and needs a better justification for not having a RNN memory that is associative. It also should cast the contributions in light of other existing work (not cited). The paper says "In this section and the remainder of the paper, we focus on the latter [commutative RNN memory operator], namely introducing a constraint (or equivalently, regularizer) that is commutative", but it never talks about the impact of a RNN memory using a non-associative operator. Being commutative is easy, isn't Equation (2.4) commutative if \Theta = W? Being associative is hard, since non-linear activations are not easily amenable to associativity.

Section 4: "The above example demonstrates that RNNs can in some cases be a natural computational model for permutation invariant functions." => Janossy pooling (Murphy et al., 2019) gives an alternative way to use RNNs, with a way to make their method tractable. Actually, my guess to why the RNNs experiments work well, even without an associative memory, is because the training examples come in multiple permuted forms, which is the data-augmentation version of the pi-SGD optimization described in Janossy pooling. 

On page 1, "consider the problem of computing the permutation invariant function f(x_1, . . . , x_n) = max_i x_i", what follows is not a proof of necessity. It is an informal argument that either should be made formal or should be described as informal.

There is a lot of missing related work for sets:
Murphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. "Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs." ICLR 2019.
Wagstaff, Edward, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, and Michael Osborne. "On the limitations of representing functions on sets." ICML 2019.
Lee, Juho, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. "Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks." ICML 2019.

Also missing related work for graphs:
Bloem-Reddy, Benjamin, and Yee Whye Teh. "Probabilistic symmetry and invariant neural networks." arXiv:1901.06082 (2019).
Murphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. "Relational Pooling for Graph Representations." ICML 2019.

The paper has an interesting question but needs to build on prior work. As of now, I am unconvinced that not having an associative operator for the RNN memory will lead to a good nearly permutation invariance function (unless there is data augmentation, per Janossy pooling).

review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: Summary: this paper proposes a new principled methodology for deriving and training RNN neural networks for prediction of permutation invariant functions. Authors show on simple tasks their method may outperform DeepSets, the state of the art.


Although the idea is interesting and the paper reflects thorough work, I believe in its current form results are too weak to deserve publication. More specifically.

1)Mathematical results and statements are mostly trivial and may well be omitted or included as an appendix. They don't seem to convey anything profound (with the exception of theorem 3.6, but this follows from results on deepsets paper). Some of these results are also mostly anectodal 

2)The regularization idea seems interesting, but I am concerned it is showing that the final learned networks have a deepset-like architecture: more specifically, theorem 3.6 shows RNN can implement permutation invariant functions by making identifying the parameters with the ones of deepperm. Also, as the authors mentioned, when learning a permutation invariant function then for any degree of regularization the regularization loss can be made zero. So for me, results seem to indicate that the network might have learned a deepperm kind of representation, which equivalently can be expressed as a RNN. Authors should make clear there are fundamental differents between both frameworks

3)Overall, the experimental validation section is weak and an extensive description of network architectures is lacking. Without them it is hard to resolve my concerns on 2). 
review_title: Official Blind Review #2

Meta-review: This paper examines learning problems where the network outputs are intended to be invariant to permutations of the network inputs.  Some past approaches for this problem setting have enforced permutation-invariance by construction.  This paper takes a different approach, using a recurrent neural network that passes over the data. The paper proves the network will be permutation invariant when the internal state transition function is associative and commutative.  The paper then focuses on the commutative property by describing a regularization objective that pushes the recurrent network towards becoming commutative.  Experimental results with this regularizer show potentially better performance than DeepSet, another architecture that is designed for permutation invariance.

The subsequent discussion of the paper raised several concerns with the current version of the paper. The theoretical contributions for full permutation-invariance follow quickly from the prior DeepSet results.  The paper's focus on commutative regularization in the absence of associative regularization is not compelling if the objective is really for permutation invariance.  The experimental results were limited in scope.  These results lacked error bars and an examination of the relevance of associativity. The reviewers also identified several related lines of work which could provide additional context for the results that were missing from the paper.

This paper is not ready for publication due to the multiple concerns raised by the reviewers.  The paper would become stronger by addressing these concerns, particularly the associativity of the transition function, empirical results, and related work. 
Decision: Reject