Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a novel method named SOFT to calculate the token similarity for self-attention without softmax operation. The authors state that the computational complexity could be reduced to O(n) with SOFT. A family of backbones are designed and evaluated on ImageNet, which achieve SOTA performance. 
main_review: This paper follows the work "Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention" and modifies its computation of attention score to fit in vision task. But this paper is of novelty. 

I have some concerns. 

- In 3.2 the authors state that the time complexity is O(m^2n + m^3) and the space complexity is O((2m+d_e)m + m^2). However, as m = n/k, which is linear w.r.t. n, the complexity could not be linear. The complexity could be reduced by k^2 or k according to the order of m. The paper also states that they could keep m as a fixed constant, but with image size increased, based on the method of average pooling or stride convolution, m would increase as well. 

- There are some writing problems. The complexity in line 167 lacks m as a multiplier. In table 1 there is no introduction to C33 and C31. 

- The convolution layers between stages are not included in many other transformers, and there is no ablation on these convolutional layers. 

- There are other works on ViT like botnet, swin, cvt e.t.c. and CNNs like efficientnet that could be add in table 3 for comparison. 

- As the complexity decreases with SOFT, there could be some experiments to show that the training and inference speed may increases. 
limitations_and_societal_impact: My concerns on the limitations of this paper have been presented in "Main Review". The authors do not discuss the potential negative societal impact of their work. Adding more related discussions will be helpful.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a softmax-free self-attention that replaces the previous dot-product between the query matrix and the key matrix with a Gaussian kernel. To facilitate the proposed softmax-free self-attention, this paper further proposes to decompose the self-attention matrix with Singular Value Decomposition. The robustness of the proposed low-rank decomposition can be theoretically proved by computing the Moore-Penrose inverse with the Newton-Raphson method.
main_review: Introducing kernels/Gaussian kernels to handle self-attention is not new [1]. However, this paper theoretically proves that it’s possible to use low-rank matrix decomposition to approximate such kernel function, which is quite novel and improves the self-attention mechanism. Since I am not an expert in Newton-Raphson methods, I have to kindly ask the other reviewers to verify the correctness of the equations. As for the other parts, the proposed pyramid architecture has outperformed the competitors by large margins in ImageNet classification task and the attention visualizations seem quite intuitive and reasonable to me.

The only question here is on the effectiveness of stacking overlapping convolutions and batch normalizations in L178-L179. It would be better to show some ablation studies comparing the tokenization methods using overlapping/non-overlapping convolution.

[1] Peng, H., Pappas, N., Yogatama, D., Schwartz, R., Smith, N. A., & Kong, L. (2021). Random feature attention. ICLR 2021

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a novel linear complexity self-attention module that
(1)	first replaces the softmax attention with the Gaussian kernel
(2)	then apply Nystrom approximation to calculate the gram matrix with O(n) complexity.
(3)	whose bottleneck samples are calculated using average pooling or convolutional layer.

The proposed method demonstrates good top-1 accuracy on ImageNet classification with low space and time computational complexity.
main_review: Strength

The paper proposes a novel linear complexity self-attention architecture that applies kernel approximation technique to the attention weight.
-	Considers the attention weight calculated by Gaussian kernel.
-	Approximate the gram matrix using Nystrom method.
-	Propose a bottleneck sampling scheme using average pooling and convolutional layer.
-	Propose to calculate the inverse matrix of the gram matrix w.r.t. bottleneck samples using Newon-Raphson method, which is suitable for GPU calculation.

The paper experimentally compares the proposed method with several self-attention with linear complexity. The proposed method demonstrates both good accuracy and low computation complexity.

The proposed method demonstrates comparable accuracy to the state-of-the-art methods on ImageNet dataset.

The author conducts several ablation study with respect to the size of bottleneck samples, sampling methods, and the number of iteration for Newton-Raphson method.


Weakness

In the remarks, the author says that the model with Gaussian kernel weight without does not work well. Since the proposed method is derived as the approximation about the Gaussian kernel, I would like to see the discussion why the true weight does not work well while approximated weight shows good performance.
Regarding this, I would like to see the approximation performance of the gram matrix with the proposed approximation.

It looks like Nystromformer is the method that tries to approximate the true softmax attention. Since softmax weight works well while non-approximated Gaussian weight does not work well, I would like to know the reason of this reversal in the performance after the approximation.


Another Comments

In Table (4) Random Sampling works the same performance as Average Pooling. Though the author prefers average pooling, I personally think random sampling is better since random sampling does not violate the permutation equivariance property of the whole the layer while average pooling depends on the position information.

The proposed Gaussian weighted self-attention may be regarded as the variant of kernel density estimation.


Evaluation

Considers the theoretical and empirical performance of the proposed method, I recommend acceptance.

limitations_and_societal_impact: Limitation of the gaussian weight is briefly described in the remarks paragraph in L111~117.
There are no discussion aout the potential negative social impact. However, since it is the algorithmic paper, the possibility that the paper causes the negative impact may small.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper substitutes softmax self-attention with a Gaussian kernel function. This allows to approximate the self-attention matrix with a low-rank approximation. The robustness of the approximation is supported by theoretical guarantees, while previous works that don't provide these guarantees. The proposed method is evaluated on ImageNet, arguably the most popular benchmark for evaluating computer vision models, and shows impressive results when compared against other Linear Transformer alternatives and even when compared against the standard (full) self-attention approach.
main_review: === UPDATE AFTER DISCUSSION PERIOD ===

In addition to the strengths below, the auhors have clarified my questions and addressed satisfactorily most of my concerns. Thus, I'm advocating for accepting the paper (I'm increasing my score from 6 to 7).

=== Strengths ===

1) The paper addresses an important topic, i.e. efficient self-attention mechanisms, with numerous applications in computer vision, and natural language processing. 

2) The strong results shown on ImageNet accuracy, compared to other popular efficient attention alternatives, makes it a good candidate to be useful to practitioners and influential to future research.

3) The method presented in the paper is built from strong theoretical foundations (assuming the proof of Theorem 1 is correct, see clarifications below).

4) The paper carefully analyses the problems in many existing "efficient" (Linear) transformer alternatives. Mainly focusing on Nyströmformer which is the most similar existing approach.

5) The experimental details are well detailed in section 4.1, which makes easier for other to build on and compare with the results of the paper.

=== Weaknesses ===

1) I find the definition of $n$ a little bit confusing in some parts of the text. $n$ is first defined as the "sequence length" (line 94), but then is referred to as "token length" (Figure 1b and sections 3.3 and 4.2). 

2) Assuming that in all cases $n$ is referring to the same concept (i.e. sequence length, or number of tokens per image), then some of the experiments don't make much sense. In particular the experiments where SOFT is used with the VIT architecture (i.e. Figure 1b). Lengths of 784 x p (with p=1...8) are evaluated, (in all cases using m=49?) but these lengths are unreasonable since the VIT paper uses patches of 32x32 or 16x16, which results in inputs of 49 or 196 tokens in total to the attention layer.

3) In general, I think that a plot/table showing the optimal m (w.r.t. accuracy/time or accuracy/flops) for different sequence lengths should be reported. This is important because the value of m chosen is 49, which is already "large" for typical non-pyramidal transformers. Thus, in this regime it might be that the proposed method does not provide any significant speed-up. An alternative experiment would be to use the PVT architecture with different input resolutions (but same downscaling factors in each stage): e.g. 150,224,280,380,448,...

4) Figure 1a shows accuracy vs. # of paramaters vs. accuracy. This plot seems of little relevance for the goal of this work. A plot showing accuracy vs. training/inference flops; or even better accuracy vs. training/inference time would be preferable. Accuracy and flops are reported in Table 3, but given that the proposed method uses an iterative algorithm to approximate the pseudo-inverse, and iterative algorithms are not ideal for modern accelerators (GPUs/TPUs), I would strongly recommend the authors to report runtime.

5) One of the limitations of the presented of method, as described in lines 115-117, is that "we find that when using our kernel-based self-attention matrix $S$ without linearization, the training of a transformer fails to converge". Do you have an hypothesis that explains why this happens?

6) All the experiments are limited to ImageNet recognition. It's unclear whether they run a single run for each presented result or the reported numbers are the average of multiple independent runs. In any case, I would recommend the authors to perform additional experiments (if time permits) on a different benchmark. For instance, the benchmark presented in the paper "Long Range Arena: A Benchmark for Efficient Transformers" (https://arxiv.org/pdf/2011.04006.pdf), which also highlights that existing "efficient" attention mechanisms are far from perfect, seems like a good benchmark to evaluate the proposed method.

=== Clarifications ===

I can't follow the proof of Theorem 1. In particular going from Eq. (18) in the appendix to Eq. (19).  Eq. (18) reads:
$
||A^\dagger - A_{k+1}|| =  ||(A^\dagger - A_{k})A(A^\dagger - A_{k})||
$

Line 36 reads: "And we left multiply A on the both sides of (17), then norm the equation". Then Eq. (19) reads:
$
||A A^\dagger - A A_{k+1}|| =  ||A(A^\dagger - A_{k})A(A^\dagger - A_{k})||
$

This seems to imply that if $A$ is a symmetric semi-definite positve matrix and $||X|| = ||Y||$, then $||A X|| = ||A Y||$. However, this is false in general. See a counter example: X = [[1, 2], [3, 4]], Y = [[1, 3], [2, 4]], A = [[2, 1], [1, 2]] (apologies, it seems that matrices are not rendered well). $A$ is positive definite.
$||X|| = ||Y|| \approx 5.4649857$ but 
$||A X|| \approx 15.42234 \not\approx 16.18217 \approx ||A Y||$.

I tried to use the fact that $||A B|| \leq ||A||\cdot||B||$ (in the case of matrix $p$-norms), but didn't get too far. Given that $||A|| > 0$ if $A$ is semi-definite positive:

$
||A^\dagger - A_{k+1}|| =  ||(A^\dagger - A_{k})A(A^\dagger - A_{k})|| \Leftrightarrow
||A|| \cdot ||A^\dagger - A_{k+1}|| =  ||A||\cdot||(A^\dagger - A_{k})A(A^\dagger - A_{k})||
$

Then:

$
||AA^\dagger - AA_{k+1}|| \leq ||A|| \cdot ||A^\dagger - A_{k+1}|| \text{  ???  }
||A(A^\dagger - A_{k})A(A^\dagger - A_{k})||
\leq ||A||\cdot||(A^\dagger - A_{k})A(A^\dagger - A_{k})||
$

To summarize, I need additional indications from the authors to follow the proof.

=== Other comments ===

 Please, carefully review the paper looking for typos. Some that I found:
- Main text, line 45: "identity" -> "identify".
- Main text, line 200: "AadmW" -> "AdamW".
- Appendix, equation 19: The first line ends with $|$ to denote the norm, it should end with $||$.
- Appendix, line 41: "multiple" -> "multiply"

Suggestion: $\times$ is typically used to denote the cross-product, I would recommend using $\cdot$ for denoting the product of a scalar by a matrix (Eq. 3, 4, 5) to avoid confusion, but feel free to ignore this suggestion if you strongly prefer otherwise.
limitations_and_societal_impact: The paper does not discuss any potential negative societal impacts of the work. The paper is more on the theory side of the theory-application spectrum of papers, but it targets (and tests the proposed method on) an image recognition task, i.e. ImageNet. In any case, I do not think that this work raises specific concerns that are not present in a large fraction of NeurIPS submissions, or in virtually all publications applying Machine Learning to Computer Vision.
review_title: null

Meta-review: The reviewers unanimously agree that the presented softmax-free transformer and the kernel approximation techniques are novel and interesting. The paper also demonstrates good performance with reduced computation complexity on ImageNet. After the rebuttal, most of concerns from the reviewers are addressed. The authors are encouraged to further improve the paper by 1) comparing with other ViT works/architectures (https://arxiv.org/abs/2103.14030, https://arxiv.org/abs/2101.11605) 2) having more comprehensive discussion regarding related works with softmax-free attention (https://arxiv.org/abs/2103.02143, https://arxiv.org/abs/2103.13076, etc..) 3) discussing potential negative societal impacts of the work.
Decision: Accept (Spotlight)