Recent trends of incorporating attention mechanisms in vision have led researchers to reconsider the supremacy of convolutional layers as a primary building block. Beyond helping CNNs to handle long-range dependencies, Ramachandran et al. (2019)  showed that attention can completely replace convolution and achieve state-of-the-art performance on vision tasks. This raises the question: do learned attention layers operate similarly to convolutional layers? This work provides evidence that attention layers can perform convolution and, indeed, they often learn to do so in practice. Specifically, we prove that a multi-head self-attention layer with sufficient number of heads is at least as expressive as any convolutional layer. Our numerical experiments then show that the phenomenon also occurs in practice, corroborating our analysis. Our code is publicly available 1 .
The paper claims that 1. multi-head self-attention(MHSA) is at least as powerful as convolutions by showing that a CONV can be cast as a special case of MHSA and 2. that in practice, MHSA often mimic convolutional layers.
These claims are interesting and timely, given that there has been a fair amount of recent work that have explored the use of self-attention(SA) on image tasks, either by composing SA with convolutions or replacing convolutions altogether with self-attention (examples of each are referenced in the paper). So should these claims be true, they would give theoretical evidence that SA can completely replace convolutions.
However, I think that the claims are exaggerated and misleading.
1. The theory shows an arguably contrived link between self-attention and convolution. Theorem 1 says that a convolution can be seen as a special case of MHSA, and the constructive proof (that chooses SA parameters to derive a convolution) shows a correspondence between the output of each head of MHSA and a D_out by D_in linear transform applied to the D_in features of a single pixel, with attention weight given entirely to this pixel (i.e. hard attention). The derivation relies heavily on the use of a relative encoding scheme that sets W_qry=W_key = 0 (usually referred to as W^Q, W^K in the self-attention literature, the linear maps applied to the queries and keys) i.e. the attention weights do not depend on the key/query values, but only their relative positions. Moreover, the softmax temperature (an interpretation of 1/alpha) is set arbitrarily close to 0 to make the softmax saturate and attain hard-attention. With these two constraints, I am sceptical as to whether you can really say that you are implementing self-attention. In standard practice when MHSA is used, W^Q and W^K are never set to zero, and the scale of the logits for the self-attention weights are controlled by normalising them with sqrt(D_k) (or sqrt(D_k/N_h), depnding on how you choose to deal with multiple heads). Furthermore, the derivation only holds for when stride=1 and padding=“SAME”, such that the spatial dimensions of the input (H & W) remain unchanged. In fact the padding is not really dealt with in the derivation, and it is unclear whether the result can generalise to convolutions with stride > 1, making the claim “MHSA layer … is at least as powerful as any convolutional layer” problematic. Hence although I think the derivation is mathematically correct, I think that the link that the derivation makes between convolutions and MHSA is somewhat contrived and not a useful observation in practice. I expect MHSA with learned W_qry and W_key will behave differently to when they are set to 0, and it would be much more interesting/relevant to see how their behaviour compares with convolutions in this more realistic setting.
2. The heavy dependence of the experiments on the quadratic encoding, the aforementioned contrived form of MHSA that was used to derive the link between convolutions and MHSA, makes the results not very relevant and the claim that "MHSA often mimic convolutional layers" rather misleading. It could be more relevant if quadratic encoding can replace standard MHSA parametererisations with learned W_qry and W_key, but I’m not convinced that this is the case. Although Figure 4 suggests that this SA with quadratic encoding gives similar test performance to ResNet18, I think that CIFAR-10 classification is too simple a task to claim that quadratic encoding can replace standard SA with learned W_qry and W_key, and I think results can look very different for harder problems e.g. ImageNet, MSCOCO - explored in Ramachandran et al - made possible because they use local SA as opposed to full SA. Experiments on these problems would be much more interesting and relevant. Note that the experiments using the learned relative positional encoding have “attention scores (are) computed using only the relative positions of the pixels and not the data” (I’m guessing this means W_qry=W_key=0 again). Hence the qualitative similarities between MHSA and convolutions only hold for the rather restricted case where I get the impression that self-attention has been unrealistically constrained only to increase its chance of behaving similarly to convolutions. Also the comparison in Figure 4 and Table 1 is being used to support the claim that self-attention can be as “powerful” as convolutions, but I think this is misleading because both quadratic and learned SA uses full SA, where each pixel attends to all pixels - this means the time & memory complexity of the algorithm is O((HW)^2), whereas for convolutions it is O(HW). So the expressiveness of SA that matches convolutions for this particular problem comes at a significant cost, to the extent that for bigger problems (ImageNet, MSCOCO) full SA is not feasible due to its quadratic memory requirement, whereas convolutions don’t face this problem. I think this should be pointed out more explicitly in the text, and think the claim that “self-attention is at least as powerful as convolutions” should be replaced with a more moderate statement such as “self-attention defines a family of functions that contains convolutions (of stride 1)”
Summary: Although the writing of the paper is clear and the derivation is mathematically correct as far as I can see, the link between self-attention and convolutions in the paper are fairly contrived, hence the contribution of the paper to the field is not so significant in my honest opinion.
********************
I appreciate the authors' response, and understand that the maths suggests a single head of MHA (in the original form) cannot exactly emulate a general convolution. But empirically, the localised attention patterns do seem to suggest that each head can behave similarly to a restricted form of convolution, where similar weights are given to the receptive field (the local patch) in the neighbourhood each input pixel. Perhaps an analysis of what special case of convolution each head can emulate would be interesting, given the empirically observed similarities in the qualitative behaviour. 
With the more justified nuance of the findings of the paper, and together with the authors' significant efforts to make the evaluation more relevant and thorough, I will increase my score to "weak accept".