Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes an alternative to softmax attention using the sinc function. The authors were well-motivated using the sinc function from the Fourier integral estimator and provided theoretical support for approximation error. They have done experiments on two datasets showing improvement over softmax attention.
strengths_and_weaknesses: Strengths:
1. The paper is a pleasant read and clear to understand.
2. The established connection between non-parametric kernel density estimator and self-attention.
3. The authors have provided well-motivated intuition for their proposed approach.
4. Related work has been moderately covered.
5. The evaluation is convincing to show the benefit of sinc-based attention.

Weaknesses:
1. The authors only experimented with one choice of $\phi$. It would be great to see what other suitable candidate of $\phi$ is possible.
2. How do they determine the value of $R$? Is it dataset-specific?
3. There are no quantitative results on the runtime of the proposed attention mechanism.

questions: 1. What is the connection and differences between the proposed sinc function-based attention and the Fnet [1], which uses Fourier transform instead of softmax attention?
2. Eq. 6. is derived upon considering only $\mathbf{v}$ and $\mathbf{k}$. How is it justified to replace $\mathbf{k}$ with $\mathbf{q}$ in line 119?
3. What was the rationale and practical reason to consider $\mathbf{k}_j$ s are i.i.d? In practice, when they went through an MLP, the channels became dependent on each other.

[1] Lee-Thorp, James, et al. "Fnet: Mixing tokens with Fourier transforms." arXiv preprint arXiv:2105.03824 (2021).

limitations: Authors have not adequately commented on the known limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors demonstrate the FourierFormer, a new class of transformers in which the novel generalized Fourier integral kernels replace the dot-product kernels. The FourierFormer can capture correlations between query features and key self-attention vectors. The authors empirically corroborate the advantages of FourierFormers over the baseline transformers in various practical applications, including language modeling and image classification.
strengths_and_weaknesses: Strengths:
The ideas that the authors put forward are novel, and the mathematical arguments are complete and ingenious.
Weaknesses: 
The experiments in this paper are insufficient and, therefore, not convincing enough to demonstrate the effectiveness of the FourierFormer. The experiment only involves two basic tasks based on WikiText-103 and ImageNet.

questions: In the paper, the authors say ‘However, equations (1) and (2) imply that the dot-product attention assumes the features (qi1, . . . , qiD) in qi, as well as the features (kj1, . . . , qjD) in kj , are independent’. This description also implies that v is not included in the consideration of the correlation. However, even it's straightforward to consider q, k as independent variables and v as dependent variables, in my opinion, q, k, and v don’t have a clear statistical relationship in Transformer, partially due to its poor interpretability. Hence, according to the author's idea, v may also be part of considering the correlation.
limitations: Although the authors have given detailed proof mathematically, due to the poor interpretability of the Transformer itself, I still need to see more experimental results to agree with their point of view. The current experimental results are insufficient and not persuasive.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors provide a new perspective to interpret the self-attention mechanism in Transformers. In particular, with the assumption that the query and key vectors are normalized, the self-attention mechanism coincides with the well-known Nonparametric Kernel Regression with kernel density estimation. Motivated by this, the authors instead use the Generalized Fourier Integral Theorem to build more powerful estimators for capturing the interaction between features in different dimensions. Experiments on some benchmarks are conducted.
strengths_and_weaknesses: **Strengths** 
- The interpretation of seeing the self-attention mechanism as using the isotropic Gaussian kernels for kernel density estimation and nonparametric regression estimation seems to be novel, which provides a new perspective to the community to understand the behavior of self-attention.
- The motivation seems to be reasonable to use the generalized Fourier Integral Theorem to capture the feature interaction instead of using the multivariate Gaussian kernels with proper covariance matrices.
- The theoretical analysis is thorough, including approximation error of the generalized Fourier density estimator (Theorem 1) and the generalized Fourier nonparametric regression estimator (Theorem 2). 

**Weaknesses**
- **Regarding the background**: the authors should consider adding a preliminary section to introduce the background knowledge on the nonparametric kernel regression, kernel density estimation, and the generalized Fourier Integral theorem, which could help the readers easily follow the derivation of Section 2 and understand the motivation to use the Fourier Integral theorem as a guide to developing a new self-attention mechanism.
- **Regarding the experimental evaluation**: the issues are three-fold. 1) since the authors provide an analysis of the approximation error between estimators and true functions (Theorem 1 and 2), it is informative to provide an empirical evaluation of these quantities on real data as further verification. 2)  The experiments should be more comprehensive and general. For both the language modeling task and image classification task, the model size is limited and the baselines are restrictive. 3) Since the FourierFormer need customized operators for implementation, the authors should also provide the memory/time cost profiling compared to popular Transformer architectures. Based on these issues, the efficiency and effectiveness of the FourierFormer are doubtful.

-------After Rebuttal-------
Thank authors for the detailed response. Most of my concerns have been addressed. I have updated my scores to 6.
questions: See the issues in the Strength And Weaknesses. If the authors could address these issues, I would like to increase my scores accordingly.
limitations: No negative societal impact
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes the FourierFormer, in which the dot-product kernels are replaced by the generalized Fourier integral kernels. Unlike the dot-product kernels, where we need to choose a good covariance matrix to capture the dependency of the features of data, the generalized Fourier integral kernels can automatically capture such dependency and remove the need to tune the covariance matrix. This paper theoretically prove that the proposed Fourier integral kernels can efficiently approximate key and query distributions and verify this point through experiments on two transformer-based tasks.
strengths_and_weaknesses: 1.This paper introduces a new angle to interpret transformer and its key module. This work provides a nonparametric regression interpretation to study self-attention in transformers and formulate self-attention from the viewpoint of kernel regression.
2.This work adopts the generalized Fourier integral estimators to replace the traditional dot-product self-attention and provide theoretical guarantees for the estimator.
3.Overall, the paper is well organized and technically sound. The experimental results on multiple transformer-based tasks verify the efficiency of the proposed Fourier Former.

Weaknesses
1.The derivation process and the presentation need to be improved. Some important symbol annotations or explanation is missing during the algorithm description, which make readers hard to follow the derivation process. For example, in the equation (9), some important symbol annotations are missing, e.g. ‘s’, ‘R’. It is difficult for readers to catch up the derivation, and the derivation of p(k) is crucial to the following interpretation.
2.Some pitfalls in the paper: a) in line 100, “are i.i.d samples from.” ; b) in equation (6) one of /psi is written as /phi; c)line 185, the C’ in text are in wrong format.


questions: 1. In line 144, the subsection title is “(Generalized) Fourier Integral Theorems”. Why do authors bracket the word “generalized” ？

limitations: The paper didn't address the limitation and potential negative societal impact of the work.
review_title: null

Meta-review: metareview: Overall, the reviews about this paper are very positive. The authors spent great effort engaging in discussions and improving the paper with clarifications and additional experiments. We recommend accepting the paper.
confidence: Certain
Decision: Accept