Title: LEARNING RNNS WITH COMMUTATIVE STATE TRAN-SITIONS

Abstract: Many machine learning tasks involve analysis of set valued inputs, and thus the learned functions are expected to be permutation invariant. Recent works (e.g., Deep Sets) have sought to characterize the neural architectures which result in permutation invariance. These typically correspond to applying the same pointwise function to all set components, followed by sum aggregation. Here we take a different approach to such architectures and focus on recursive architectures such as RNNs, which are not permutation invariant in general, but can implement permutation invariant functions in a very compact manner. We first show that commutativity and associativity of the state transition function result in permutation invariance. Next, we derive a regularizer that minimizes the degree of non-commutativity in the transitions. Finally, we demonstrate that the resulting method outperforms other methods for learning permutation invariant models, due to its use of recursive computation.

1. INTRODUCTION:

Many of the successes of deep learning can be attributed to a choice of architecture that fits the application domain. A key example of this are convolutional neural nets (Krizhevsky et al., 2012) that employ extensive parameter tying across the image, reflecting the shift invariance of visual labels. It is clear that such inductive bias is necessary for any domain if one needs to learn from a limited number of examples. This has prompted much recent interest in the question of modeling architectures that capture invariances of particular domains.

One such example is the setting where the input to the network is a set of objects and the true output does not depend on the order of the objects in the set. In this case, the function that we seek to learn is permutation invariant. It would thus be advantageous to retrict learning to models that are permutation invariant by design. This was the observation in the work on Deep Sets (Zaheer et al., 2017) , which gave necessary and sufficient conditions for a network to be permutation invariant.

The underlying idea in many of the permutation invariant architectures is to apply the same network N 1 to all items in the set, then sum the outputs and apply another network N 2 to the summation. Clearly this is permutation invariant. Similarly other models using attention (Vinyals et al., 2016; Lee et al., 2019) are permutation invariant since they only rely on comparisons between elements in the set.

Although the above approaches results in invariant models, these are not clearly the smallest models that can compute a given invariant function. For example, consider the problem of computing the permutation invariant function f px 1 , . . . , x n q " max i x i . In order to calculate it with a DeepSet approach, one would need to set N 1 pxq " x k for large k and then N 2 pzq " z 1{k . This would approximate the 8 metric and therefore the max function. However, in order to implement these two functions N 1 , N 2 with ReLU networks, one would need Op k q to achieve accuracy (e.g., see Telgarsky, 2017, Lemma 3.4) , and thus calculating this seemingly simple function to good accuracy would take a fairly large network. Clearly, if one uses max as the aggregation function in DeepSets, this could be avoided, but the same would then be true for other aggregation functions.

On the other hand, the max function can be easily implemented via a simple RNN. Consider an RNN with the following state update s t`1 " max ps t´1 , x t q and set s 0 " ´8. Then clearly we would have s n " max i"1 x i . Namely, we will implement the permutation invariant max function. Furthermore, the s t`1 state update can be very easily be implemented using a one hidden layer ReLU network, because maxps, xq " ReLUps ´xq `ReLUpxq ´ReLUp´xq.

The above example demonstrates that RNNs can in some cases be a natural computational model for permutation invariant functions. The goal of this paper is to ask which RNNs compute permutation invariant functions, and how they can be learned.

Clearly, most RNNs are not permutation invariant, as their state has the capability of tracking temporal patterns, and is thus sensitive to changes in ordering. Here we show that by restricting RNN state updates to commutative-associative functions, RNNs do become invariant, and the resulting set of functions is very expressive.

After establishing the commutative-associative constraints, we turn to ask how one can learn RNNs that satisfy the latter constraint. We show that for ReLU activation functions the commutative constraint corresponds to a closed form regularizer on the parameters of the RNN and suggest learning with this regularizer in order to achieve commutativity.

We show empirically that learning with commutative regularization leads to architectures that are permutation invariant in practice and that outperform DeepSets on several benchmarks.

Taken together, our results highlight the importance of the function class used for learning permutation invariant functions, and the important role of recursive computation for these tasks.

2. PROBLEM FORMULATION:

We consider the problem of learning functions that map a sequence of inputs x 1 , . . . , x n to an output y. We note we could have also addressed the problem of generating an output sequence y 1 , . . . , y n but use a single output for simplicity.

We say that such a function f px 1 , . . . , x n q is permutation invariant if for any permutation π of rns and for all x inputs we have: f px 1 , . . . , x n q " f px πp1q , . . . , x πpnq q

(2.1)

We next ask: how should an RNN be constructed such that it is guaranteed to be permutation invariant.

We consider standard RNNs, parameterized as follows. Let s t P R r be the state vector at time t.

Then the state update rule is: s t`1 " Aσ pW ψpx t q `Θs t q (2.2) where ψpxq P R d is a "pre-processing" network (of arbitrary architecture), σ is a pointwise nonlinearity such as ReLU or tanh, and A, W, Θ are matrices which transform to the appropriate dimensions, specifically, A P R rˆk , W P R kˆd and Θ P R kˆr . We note that we add a matrix A to allow the non-linearity to be taken in R k such that k ‰ r.

Finally, the output is obtained via:

y " gps t q (2.3) where g is any multilayer neural net (the specific architecture will not be important for our derivation).

To simplify the derivation of permutation invariance we make the assumption that the dimension of the RNN state, and the dimension of the transformed input ψpxq are the same, i.e. r " d.1 

Next, we introduce the following notation for the RNN state transition: s t`1 " Aσ pW ψpx t q `Θs t q " ψpx t q ˝st

(2.4) Thus, the ˝operation takes two vectors in R d and outputs a vector in

R d . Namely ˝: R d , R d Ñ R d . 2

With this notation it is clear that: s t " p. . . pps 0 ˝ψpx 1 qq ˝ψpx 2 qq . . . ˝ψpx t qq (2.5)

We use parentheses to emphasize that the order of applying ˝does matter and these operations are neither commutative nor associative for general RNNs.

3. PERMUTATION INVARIANT RNNS:

In this section we relate properties of the state transition operator ˝to the permutation invariance properties of the RNN. Without loss of generality we assume that the ψpxq " x, since this is just a pre-processing step.

Definition 3.1. An RNN is permutation invariant if the function f px 1 , . . . , x n q " gps t q implemented by the RNN is permutation invariant.

We begin with basic definitions.

Definition 3.2. The operator ˝is commutative if for all x, x 1 it holds that x ˝x1 " x 1 ˝x Definition 3.3. The operator ˝is associative if for all x, x 1 , x it holds that px ˝x1 q˝x " x˝px 1 ˝xq Definition 3.4. If an RNN has a ˝operator that is both commutative and associative we refer to it as a Commutative-Associative RNNs.

Theorem 3.5. If an RNN is Commutative-Associative then it is permutation invariant. Namely s t does not depend on the order of x 1 , . . . , x n .

Proof. The associativity property of the ˝operator implies that we can remove the parentheses in Eq. 2.5 and commutativity implies that we can then switch the order of the x i arbitrarily. Thus we have that for all permutations π:

s t " s 0 ˝x1 ˝x2 . . . ˝xt " s 0 ˝xπp1q ˝xπp2q . . . ˝xπt (3.1)

Therefore the state is invariant to the input order, and so is the output y.

A complementary question is that of universality. Namely, are the above permutation invariant RNNs sufficiently expressive to capture any permutation invariant function?

Theorem 3.6. Let f px 1 , . . . , x n ) be a permutation invariant function. Then it can be implemented with Commutative-Associative RNNs.

Proof. Since the function f is permutation invariant, it follows from Theorem 2 in the DeepSets paper (Zaheer et al., 2017) that there exist two functions φ and ρ such that f px 1 , . . . , x n q " ρ p ř i φpx i qq. We can now implement this architecture with a Commutative-Associative RNNs as follows: set ψ " φ, g " ρ and x˝x 1 " x`x 1 . Clearly this implements the DeepSet function and is Commutative-Associative because ˝is just addition.

We conclude that Commutative-Associative RNNs implement permutation invariant functions and are also sufficiently expressive to capture all permutation invariant functions.

4. COMMUTATIVE REGULARIZATION:

In the previous section we highlighted the importance of having an RNN operator ˝that is both commutative and associative. This suggests that in order to learn a permutation invariant RNN we would like to learn RNNs under the constraint that ˝is associative and commutative. In this section and the remainder of the paper, we focus on the latter, namely introducing a constraint (or equivalently, regularizer) that ˝is commutative.

Formally, the constraint that ˝is commutative corresponds to requiring:

x ˝x1 " x 1 ˝x @x, x 1 P R d (4.1)

Recall that ˝depends on the matrices A, W, Θ and thus the above constraint translates to a non-linear constraint on these three matrices. However, it is not clear how to write this constraint in a way that facilitates optimization. This will be our goal in what follows.

We begin by replacing requirement 4.1 with a more convenient proxy.

Lemma 4.1. If there exists a distribution, D, over R d , R d with non-zero density over its support,3 then

E x,x 1 "D " }x ˝x1 ´x1 ˝x} 2 2 ı " 0 ðñ P " x ˝x1 " x 1 ˝x, @x, x 1 P R d ı " 1 (4.2)

Proof. The proof relies on the fact that for a continuous non-negative random variable, X, is holds that (see Section A):

E " X ı " 0 ðñ PrX " 0s " 1 (4.3)

We now use 4.3 in order to complete the proof. Denote by R the random variable Rpx, x 1 q " }x ˝x1 ´x1 ˝x} 2 2 . Obviously, R is non-negative by definition. Note also that for any pair x, x 1 we have }x ˝x1 ´x1 ˝x} 2 2 " 0 ðñ x ˝x1 " x 1 ˝x. It follows that:

E " R ı " 0 ðñ P " R " 0 ı " 1 ðñ P " x ˝x1 " x 1 ˝x, @x, x 1 P R d ı " 1 (4.4)

The above lemma already gives the strong result that with probability one the network is commutative.

In fact a stronger result is possible, stating that the network is commutative for all inputs. We only need to add the restriction of the network A, W, Θ is Lipschitz. This will hold for example, if we restrict A, W, Θ to any compact set (e.g., see similar argument in Arjovsky et al., 2017) . Lemma 4.2. Assume the network defined by A, W, Θ has a Lipschitz constant bounded by K, and that Eq. 4.2 holds under the conditions therein. Then @x, x 1 it holds that x ˝x1 " x 1 ˝x.

Proof. Denote f px, x 1 q " }x ˝x1 ´x1 ˝x} 2 2 . Then f also has a Lipschitz constant bounded by L that is a function of K. Assume in contradiction that there exists x 0 , x 1 0 such that f px 0 , x 1 0 q " for some ą 0. Let Bpc, rq denote an 2 ball centered at c with radius r. Then because f is Lipschitz it follows that for all z P Bprx 0 , x 1 0 s, 2L q it holds that f pzq ě 2 . Let γ denote the minimal density value at Bprx 0 , x 1 0 s, 2L q. By assumption on D we have that γ ą 0. It therefore follows that P " f pXq ě 0.5

ı ě P " z P Bprx 0 , x 1 0 s, 2L

ı q ě 0.5γ ą 0 and therefore P " f pXq " 0 ı ă 1 and we have a contradiction with Lemma 4.1.

As a conclusion of lemma 4.1, we can express E " }x ˝x1 ´x1 ˝x} 2 2 ı in terms of matrices A, W, Θ for a specific distribution and derive conditions under which it is equal to zero. Definition 4.3. Consider an RNN parameterized by matrices A, W, Θ as in 2.2 with ReLU activation.

∆pA, W, Θq " E x,x 1 "D " }x ˝x1 ´x1 ˝x} 2 2 ı (4.5)

Below we show that ∆pA, W, Θq can be expressed as a simple function of A, W, Θ when using the ReLU non-linearity.

Let D be a multivariate Gaussian distribution with zero mean and covariance identity. In order to calculate ∆pA, W, Θq we will make use of the following integral (Cho & Saul, 2009 ):

E " σpu ¨xqσpv ¨xq ı " 1 π }u} 2 }v} 2 psin pθ u,v q `pπ ´θu,v q cos pθ u,v qq " gpu, vq (4.6)

It turns out that ∆pA, W, Θq is a simple function of the above gpu, vq function, as stated next.

Let w i denote the i th row of W , θ i the i th row of Θ and a i the i th column of A. Also, denote the following horizontal stacking of the vectors as

u i " rθ i w i s , v j " rw j θ j s (4.7)

and the matrices with these as columns by U and V respectively.

Theorem 4.4. Assume x, x 1 are independent Gaussian vectors, each with a unit covariance. Then:

∆pA, W, Θq " h ÿ i"1 h ÿ j"1

a i ¨aj ´gpu i , u j q ´2gpu i , v j q `gpv i , v j q ¯(4.8)

Proof. Define the stacked vector: z " ˆx1 x ˙. The function ∆pA, W, Θq is given by:

E " › › ›Aσ `W x `Θx 1 ˘´Aσ `W x 1 `Θx ˘› › › 2 2  (4.9)

We can write 4.9 using definitions in Eq. 4.7 as:

E " ´Aσ `U T z ˘´Aσ `V T z ˘¯2  " E " σ `zT U ˘AT Aσ `U T z ˘ı ´2E " σ `zT U ˘AT Aσ `V T z ˘ı `E" σ `zT V ˘AT Aσ `V T z ˘ı

Denoting ũ " σ pU zq, ṽ " σ pV zq, we can now write:

EQUATION

.10):

Letting A T A " Q, we can now write the above as:

E « h ÿ i"1 h ÿ j"1 ũi Q ij ũj ´2 h ÿ i"1 h ÿ j"1 ũi Q ij ṽj `h ÿ i"1 h ÿ j"1 ṽi Q ij ṽj ff (4.11)

and more compactly

h ÿ i"1 h ÿ j"1 E " Q ij p ũi ũj ´2 ũi ṽj `ṽ i ṽj q ı (4.12)

writing back ũi " σpu i ¨zq and ṽj " σpv j ¨zq we have

h ÿ i"1 h ÿ j"1 Q ij E

" σpu i ¨zqσpu j ¨zq ´2σpu i ¨zqσpv j ¨zq `σpv i ¨zqσpv j ¨zq ı (4.13) Using Eq. 4.6, we have that Eq. 4.13 results in the expression in Eq. 4.8.

Theorem 4.4 provides an interesting characterization of when an RNN is commutative. As mentioned earlier, an RNN is commutative iff ∆pA, W, Θq " 0. Since the theorem gives a closed-form expression for ∆ it provides a measure of non-commutativity which we will optimize in what follows.

The function in Eq. 4.8 does not provide clear structual constraints on the matrices A, W, Θ but a rather elaborate dependence between their elements. The function ∆ indeed achieves a value of zero for the ReLU implementation of the max function discussed in the intro, as well as (infinitely) many other commutative state transition functions.

5. LEARNING COMMUTATIVE RNNS:

In the previous section we obtained a function ∆pA, W, Θq whose value reflects the degree to which the state transition operator ˝is commutative.

If we could enforce the constraint ∆pA, W, Θq " 0 we could optimize over commutative RNNs.

Here we follow a standard approach to learning with constraints and add ∆pA, W, Θq as a regularizer multiplied by a regularization coefficient λ ą 0 to whatever training loss is being optimized (e.g., squared error for regression, cross entropy for classification etc). We note that if we have training data for which zero training loss can be achieved with a commutative RNN, then the optimum of the regularized objective will be a commutative RNN regardless of the value of λ. We have indeed found this to be the case in our experiments.

6. RELATED WORK:

In recent years, the question of invariances and network architecture has attracted considerable attention, and in particular for various forms of permutation invariances. Several works have focused on characterizing architectures that are "by-design" permutation invariant (Zaheer et al., 2017; Vinyals et al., 2016; Qi et al., 2017; Hartford et al., 2018) .

While the above works address invariance for sets, there has also been work on invariance of computations on graphs (Maron et al., 2019; Herzig et al., 2018) . In these, the focus is on problems that take a graph as input, and the goal is for the output to be invariant to all equivalent representations of the graph. Another approach to graph invariant computations are so called neural message passing architectures (Gilmer et al., 2017) . Finally, there is also recent work on graph-based representations and their relation to graph-isomorphism (Xu et al., 2018) .

Our work is a departure from these ideas in two respects. First, the typical approach is to consider an architecture that is invariant by design. Here we depart from this by considering an architecture that is not generally invariant, but can be invariant for a particular setting of its parameters. This also allows us to handle cases of "near invariance" where ordering may affect the output in some cases. Second, the typical approach is non temporal, whereas ours puts a specific emphasis on state based computation. This is in fact a natural approach for processing data streams, where many algorithms store a sketch of the data and update it as samples arrive (e.g., see Alon et al., 1999) .

7. EXPERIMENTS:

In order to demonstrate the versatile nature of commutative RNNs we evaluate our method on several tasks. For each task we compare performance to a relevant DeepSet architecture. In order to fairly compare our method to Zaheer et al. (2017) we implemented our own version of DeepSets in TensorFlow. We also explored two aggregation (i.e., pooling) methods for DeepSets: max and sum, both of which were considered in Zaheer et al. (2017) .

7.1. SEQUENCES OF DIGITS:

Perhaps the simplest suite of problems over sets are basic operations involving sets of digits, as done in Zaheer et al. (2017) . We evaluate our method over three such tasks, Sum, Max and Parity (the latter was not used in the DeepSets paper). we show that commutative RNNs are able to capture all functions easily whereas other baselines struggle and require adaptations to the specific problem at hand. We treat the sum and max experiments as regression problems. Given a set tx 1 , . . . , x n u where the output, f ptx 1 , . . . , x n uq is 1-dimensional, we apply the mean square error loss, `f ptx 1 , . . . , x n uq ´y˘2 where y is the ground truth. Namely, y " ř n i"1 x i and y " maxtx 1 , . . . , x n u for the Sum and Max experiments respectively. In 1a and 1b, a prediction f ptx 1 , . . . , x n uq, is considered correct if its rounded value is equal to the ground truth, i.e., |f ptx 1 , . . . , x n uq ´y| ď 0.5.

7.1.1. SUM OF DIGITS:

We follow the exact setting described in Zaheer et al. (2017) . We randomly generate 100k sequences of between 3 to 10 digits long where the label is the sum of the digits of the sequence. We evaluate the performance over sequences of lengths of 10 up to 100 digits long. Results are shown in Figure 1a and demonstrate that DeepSets with sum-aggregation and commutative RNNs behave similarly, as expected. However DeepSets with max aggregation does not generalize well.

7.1.2. MAX OF DIGITS:

We perform the exact same experiment as 7.1.1 with the change that the label of a sequence is assigned with the maximal digit in the specific sequence. Results are shown in Figure . 1b and are similar to 7.1.1, except here the DeepSet sum does not generalize well.

7.1.3. PARITY:

For the parity experiment we generate 100k binary sequences of lengths 1 up to 10 where the assigned label is 1 if the number of 1's in the binary sequence is odd and 0 otherwise. As before, we evaluate over sequences with length up to 100. Since the parity is a binary classification problem, we apply the cross-entropy loss. Results are shown in figure 1c . Here both variants of DeepSets do not generalize well, whereas the commutative architecture has a simple solution for the parity aggregation, and therefore generalizes well. 

8. EVALUATION ON ECG RECORDINGS:

We also evaluate on the ECG5000 dataset (Chen et al., 2015) , which is a sequence classification problem between normal and abnormal ECG activity. There is no reason to expect this task is pertmutation invariant, but since our method only regularizes for invariance, it can also handle variant data. Results on this data for DeepSets, plain RNN and Commutative RNNs gives errors 0.9, 0.944, 0.952 respectively. Thus, indeed the regularizing effect of our methods leads to improved results on variant data as well. To summarize the empirical comparisons above, our results demonstrate that using recurrent methods to handle sets provides results that are more robust to the underlying aggregation method, and can outperform DeepSets in several settings.

9. DISCUSSION:

We have introduced an approach to permutation invariant computation that relies on recursive architectures. While recursive architectures are generally non permutation-invariant we give conditions on their parameters such that they become invariant. The two conditions are that the state transition is associative and commutative. Of these, we focus on the latter, which we show is equivalent to minimizing a certain function of the RNN parameters. To do so we integrate the "non-commutativity" of inputs with respect to a Gaussian distribution. We believe this is a promising approach for other constraints on input space, which may be likewise represented via an appropriate measure over space.

A first natural extension of our approach is to seek a regularizer for the associative property. We explored using the Gaussian integration for this purpose but the integrals do not seem to have a closed form expression, and are related to integrating multivariate Gaussians under linear constraints, which is considered a hard problem (Miwa et al., 2003) . However, it is possible that under other distributions the integral will become feasible, or that some distributions will allow faster mixing of sampling techniques.

Another extension is to other activation functions. Our derivation for the commutative regularizer relies on the structure of the ReLU function, but variants such as leaky ReLU can also be analyzed similarly. We leave analysis of other alternatives such as tanh, or more broadly LSTM like architectures for further work.

Here we consider the case of a single hidden layer state transition, although we have no constraint on the depth of the networks for ψpxq (the input processing stage) and the gpsq (the state to output mapping). We note that one layer transitions are often used in practice, but it would be interesting to explore regularizers for transitions with more layers.

Another interesting learning-theoretic question is what is the sample complexity of learning with commutative and associative regularizers. For example, it might happen that in some cases the commutative constraint is sufficient to ensure a low enough sample complexity such that generalization is good even without enforcing associativity. Finally, it would be interesting to apply our approach to problems that are not "strictly permutation invariant" where regularization is expected to be more effective than a hard constraint on permutation invariance.

A PROOF OF EQ. 4.3.

Here we prove Eq. 4.3. Let pΩ, A, Pq be a probability space. Let X be a continuous random variable such that @ω P Ω it holds that Xpωq ě 0 (non-negative). Assume E " X ı " 0, from Markov inequality, where both terms evaluate to zero. ş E XpωqdPpωq " 0 since E has zero measure with respect to P and ş ΩzE XpωqdPpωq " 0 since @ω P ΩzE Xpωq " 0.

:

It is always possible to achieve by padding either s or x by zeros as necessary.

For the reminder of this paper we omit the ψ notation as it does not affect our derivations.

e.g. @x, x 1 P R d , fDpx, x 1 q ą 0

Figures and Tables:

(a) Sum of Digits (b) Max of Digits (c) Parity of Digits

Figure1: Experiments on digit sets. All graphs depict accuracy as a function of the sequence length. In 1a and 1b, a prediction f ptx 1 , . . . , x n uq, is considered correct if its rounded value is equal to the ground truth, i.e., |f ptx 1 , . . . , x n uq ´y| ď 0.5.

IMAGE BASED SEQUENCE OF DIGITS MNIST8m(Loosli et al.)  is a collection of 8 million 28 ˆ28 grey-scale images of digits t0, . . . , 9u.We repeat experiments 7.1.1 and 7.1.2 where instead of sets of numerical values, we use sets of images drawn randomly to create sequences of length up to 10. We evaluate the performance of the learned models on sequences up to length 50. Figure.2 shows that in both cases the commutative architecture performs well, whereas DeepSets only work when using the true underlying aggregation scheme.(a) Sum of a set of MNIST digits.(b) Max of a set of MNIST digits.

Figure 2: Experiments on MNIST digits. As seen in the plots, Commutative RNNs without any adaptations perform equally to a DeepSet architecture with a modified pooling scheme.

denote by E Ă Ω the set on which Xpωq ‰ 0.

Point-cloud Classification

Table content: <table><tr><td>Method</td><td>Accuracy</td></tr><tr><td>DeepSets</td><td>0.83</td></tr><tr><td colspan="2">Commutative RNNs 0.822</td></tr></table>

Accuracy on the ModelNet40 dataset.8.1 POINT CLOUD CLASSIFICATIONPoint clouds are sets of 3-dimensional vectors which represent objects. Such representations of objects are useful in various fields such as robotics, computer graphics, 3D scanners, etc. The nature of point-clouds suggests that these are order-less objects and thus a natural candidate for evaluation of methods designed to handle sets. As inZaheer et al. (2017) we use ModelNet40Wu et al. (2015), a collection of 12k 3D representations of 40 different categories. We treat this as a 40-way classification problem. From each 3D representation we produce a point-cloud which consists of 100 3-dimensional vectors. Results are shown in Table2, and are comparable for DeepSets and Commutative RNNs.

Table content: <table/>

Peer review (iclr2020):
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).