Summary
The paper studies the representative properties of DeepSets models, which are networks for length-$N$ sequential modeling that apply identical neural networks to each $D$-dimensional input $x^i$ to obtain $L$-dimensional features, sum up their outputs, and apply an additional neural network to the output. While past results have tightly characterized the setting where $D = 1$, positive results for the $D > 1$ case are less explored. A recent lower bound by Zweig and Bruna shows that $L$ must grow exponentially with $\sqrt{N}$ and $D$ in order to approximate any permutation-invariant function under the condition that the networks use analytic activations.
The primary contribution of the paper Theorem 3.1, which claims that there exists a construction with $L = \mathrm{poly}(N, D)$ that exactly represents any permutation-invariant target as a DeepSets model with $L$-dimensional features.
Weaknesses
In it's current form, I am concerned that the result is not correct as written. There are two primary issues, which I would like to see addressed if I am to reconsider my score for the paper.
First, I think the proof of the second part of Theorem 3.1 is false as written. The proof relies on Lemma 4.9, which claims that parirwise alignment is sufficient for union alignment, and as far as I am aware, is not proved in the paper or the appendix. I believe Lemma 4.9 to be false.
Consider the following counter-example. For $D = 3$ and $N = 4$, let $x_1 = (0, 1, 1, 0), x_2 = (0, 0, 1, 1), x_3 = (0, 1, 0, 1) \in \mathbb{R}^N$ and $x_1' = (1, 0, 0, 1), x_2' = (1, 1, 0, 0), x_3' = (1, 0, 1, 0)$. Note that $X = [x_1^T \ x_2^T \ x_3^T ] \not\sim X' = [x_1'^T \ x_2'^T \ x_3'^T]$, since the first row of $X$, $x^1 = (0, 0, 0)$ does not belong to any row of $X'$. However, the two are pairwise aligned.
* Note that $[x_1^T \ x_2^T] \sim [x_1'^T \ x_2'^T]$, with the permutation $\sigma = (1 \ 3) (2 \ 4) $ as witness.
* $[x_1^T \ x_3^T] \sim [x_1'^T \ x_3'^T]$ with permutation $\sigma = (1 \ 2) (3 \ 4)$.
* $[x_2^T \ x_3^T] \sim [x_2'^T \ x_3'^T]$ with permutation $\sigma = (1 \ 4) (2 \ 3)$.
Since the proof relies on this lemma, the proof of the lemma does not appear, and there exists a simple counter-example, I am unable to accept second part of the main theorem as true.
Second, while I have not pinpointed any major technical flaws with the proof of the first bullet, I am a unsure how the result does not contradict the lower bound on Zweig and Bruna. The theorem claims that the LP architecture (which consists of features with polynomial activations and continuous function that inverts the embedding) with $L = O(N^5 D^2)$ is sufficient to exactly represent any continuous permutation-invariant $f: \mathbb{R}^{N \times D} \to \mathbb{R}$. Theorem 3.4 of ZB suggests that if $L \leq N^{-2} \exp(O(\min(D, \sqrt{N}))$, then there exists some analytic $g$ such that any DeepSets model $f$ with feature dimension $L$ and arbitrary NNs with analytic activations cannot approximate $g$.
As far as I understand both results, the only way these two results do not represent a contradiction would be if the continuous function that inverts the embedding $\rho$ is non-analytic, and hence cannot be represented the networks described by ZB. However, if our input $x$ is from a compact set (like the complex circle, from ZB) (and hence, the aggregated polynomial features $\sum_i \phi(x^i)$ belong to a compact set) and $\rho$ is continuous, then the universal approximation results for two-layer neural nets imply the existence of a sufficiently wide 2-layer neural network with analytic activations (like the sigmoid) that approximates $\rho$ arbitrarily well. I think this would contradict the ZB result on inapproximability.
All that said, it's possible that I've overlooked or misunderstood something. If there is no contradiction or if the authors believe that the result by ZB is incorrect, please let me know, and I'd be happy to discuss further.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.