Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a novel transformer model for dealing with point set data, with the main focus on achieving linear time complexity in the attention mechanism. By utilizing the idea of random sampling-based approximation to the vanilla attention from sampled Hamiltonian cycle attention, the authors show that the proposed model can be a universal function approximator of set-to-set functions. Experiments on point cloud data are studied with comparison to several baseline methods, showing that the proposed model can achieve comparable performance with better efficiency.
strength_and_weaknesses: - This paper is well written and easy to follow. The motivation is clear and the overall structure is well organized.
- It seems like the theoretical discussion on the universal approximation property is heavily based on the work of [1,2], while the authors also briefly touched on the role of contextual map. However, the definition 3.1 and the paragraph followed do not seem very self-explanatory to me and it's in fact a bit confusing about what are the novel part exactly in the proof. I wonder if the authors can provide more details on this part.
- One major contribution of this work focuses on achieving linear time complexity on set data. However, the experiments are only conducted on point cloud data, which is a special case of set data. I wonder if the authors can provide more experiments on other set data, such as graph data, to show the generalization of the proposed model. Also, there exists a lot of works on efficient attention in the past few years, but in recent benchmarks and scaling studies, the vanilla transformer is still the best performing one. In a similar spirit, how do the authors think about the contributions of the proposed model in this context?

[1] Yun, Chulhee, et al. "Are transformers universal approximators of sequence-to-sequence functions?." arXiv preprint arXiv:1912.10077 (2019).
[2] Yun, Chulhee, et al. "O (n) connections are expressive enough: Universal approximability of sparse transformers." Advances in Neural Information Processing Systems 33 (2020): 13783-13794.
clarity,_quality,_novelty_and_reproducibility: Please see above comments.
summary_of_the_review: I believe the problem studied in this work is interesting and this work made some contributions.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed an O(n) complexity sampled transformer that can process point set elements directly without additional inductive bias. The sampled transformer introduces random element sampling, which randomly splits point sets into subsets, followed by applying a shared Hamiltonian self-attention mechanism to each subset. The overall attention mechanism can be viewed as a Hamiltonian cycle in the complete attention graph, and the permutation of point set elements is equivalent to randomly sampling Hamiltonian cycles. This mechanism implements a Monte Carlo simulation of the dense attention connections. The paper shows that it is a universal approximator for continuous set-to-set functions.  Experimental results for classification and few-shot learning on point-clouds show comparable or better accuracy with significantly reduced computational complexity compared to the dense transformer or alternative sparse attention schemes.
strength_and_weaknesses: +: The sampled attention mechanism which maps the random permutation of set elements to the random sampling of Hamiltonian cycle attention matrices, permitting the direct processing of point sets.
+: It proves that the proposed sampled transformer is a universal approximator of continuous set-to-set functions.
+: Compared to previous transformer architectures, the empirical results show that our proposed sampled transformer achieves comparable (or better) performance with less inductive bias and complexity.
clarity,_quality,_novelty_and_reproducibility: The paper is rather theoretical and a little hard to read especially the proofs. Overall it does seem to be a good paper that is technically sound.
summary_of_the_review: This paper proposed an O(n) complexity sampled transformer that can process point set elements directly without additional inductive bias.  Experimental results for classification and few-shot learning on point-clouds show comparable or better accuracy with significantly reduced computational complexity compared to the dense transformer or alternative sparse attention schemes.

Overall I feel this is a good paper and hopefully can be very useful for a lot of follow up works.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an O(n) self-attention layer based on the sparse transformer that is permutation equivariant. The paper shows that their proposed architecture is a universal approximator, and present experiments on set-input datasets.
strength_and_weaknesses: The sparse transformer requires only O(n) computation but is not permutation invariant. This paper proposes a randomized linear-compute method that is permutation invariant in expectation and is a universal approximation of set-to-set functions.

The narrative around inductive bias is not clear to me. As the authors point out, existing works (Zhao et al, Lee et al) propose O(n) operations that are permutation invariance. Both papers prove the universal approximation property. The paper claims in the introduction that these methods “introduced additional inductive biases” and “a research question naturally arises to avoid introducing unneeded inductive bias”. Can you elaborate more on (1) why the inductive bias imposed by nearest neighbor search or learned inducing points is unneeded and (2) what evidence or intuition you have for your sampled attention having less of an inductive bias than both of these approaches?

I skimmed through the theory and proofs, and I did not find any major errors.

For some of the experiments such as Tables 3 and 5, you could also consider the learned inducing point method from Lee et al as a baseline, which I think can be better suited to this problem setting compared to kNN attention.

For Table 1, 3, 5: do you have error bars?
clarity,_quality,_novelty_and_reproducibility: The writing is clear. To my knowledge, the proposed architecture is new.
summary_of_the_review: The main narrative around "inductive biases" is unclear to me, and the experiments lack a comprehensive comparison to O(n) attention mechanisms.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an efficient sampled transformer with O(n) complexity. The developed method splits the point set into subsets, each one being processed by a shared Hamiltonian self-attention mechanism. The proposed strategy is well-supported theoretically. The method is evaluated on ModelNet40 under self-supervised learning and few-shot learning. 
strength_and_weaknesses: === strength ===

1. this paper is well-written and organized clearly. 

2. the proposed method is efficient, according to Tab.3. the proposed method is well supported theoretically.

=== weaknesses ===

1. From Tab.3, we can observe that the proposed method is efficient. I would like to see the performance on large-scale point cloud, such as S3DIS and SemanticKitti for segmentation. In addition, the performance on other datasets, like ScanObjectNN is also expected to show the effectiveness. 

2. As the proposed method splits point sets into subsets, maybe it would be better if the authors could show the difference from the window-based transformer, like Stratified Transformer [1].

[1] Lai et al., Stratified Transformer for 3D Point Cloud Segmentation.
clarity,_quality,_novelty_and_reproducibility: See above

Reproducibility: code is not available in the submission, but the implementation details might be useful for reproducibility.
summary_of_the_review: This paper is well-written and the proposed method is interesting. However, more experiments are needed.

== Post-Rebuttal ==

In the response, the authors respond that they do not conduct experiemnts on the large-scale data, and only on the 2048 points, due to the limited time and computational resources. Alothugh the reported results can show that the proposed method yields comparable performance in comparison with previous methods while requiring less resources, I still think it would be better to conduct comparison on large-scale data, which is important for the application of transformer on large-scale data.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper seeks to develop an attention mechanism for sets that does not have any additional biases. The paper attempts to do this by splitting the points into subsets and using a specific attention pattern that forms a Hamiltonian path where each element is visited exactly once. There's a universal approximation theorem. The results look good relative to the methods that were compared to. Each of the reviewers sent me individual comments when I wrote them that moved me away from thinking this paper was borderline. The main criticism highlighted in the discussion centered around the motivation for the approach and whether the goals for the motivation were actually met. Some concrete issues raised were:

- Experiments on different kinds of data
- Precision on what is meant by "biases"
- Comparison with other methods like SetTransformer and other O(n) attention mechanisms
- Experiments on large-scale data with 10000 points

The reviewers, however, were positive about the general idea and think it warrants for clarification in motivation and a broader set of experimental results.
justification_for_why_not_higher_score: The main criticism highlighted in the discussion centered around the motivation for the approach and whether the goals for the motivation were actually met. Some concrete issues raised were:

- Experiments on different kinds of data
- Precision on what is meant by "biases"
- Comparison with other methods like SetTransformer and other O(n) attention mechanisms
- Experiments on large-scale data with 10000 points
Decision: Reject