Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper studies the loss landscape of two-layer neural networks on global- and self-attention models.  It shows that attention helps reduce sample complexity.  I went through the all the theorem part of the paper, but only checked the intuition and did not dig into the detailed proof.   I am less familiar with reviewing papers that are theorem-oriented, which is hard for me to justify the contributions of these bounds.  My concerns and suggestions are mainly focused on the empirical part, which I think authors need to improve.  

First, the authors need to provide more detail about the baseline model, especially for the experiment on 5.1.1.  Also, please list the number of parameters for different models.  And please justify whether the reported results (sample complexity in table 1 & 2) are affected by the difference of number parameters if they are not the same.  The authors also need to clarify the meaning of the "number of training samples" in the tables.  Does it mean the number of unique training examples seen by the model or the total number of training samples?  If the authors mean the former one, then, what is the training procedure?  What are optimizers used between different models?  Are these will affect the test loss difference.  How does the author make sure the comparisons are fair?  Also, in the main text of section 5.1.1, the authors said they construct a dataset of 200,000 examples.  How are the 200,000 samples distributed?  What is the size of the testing set?   Do the reported results average over multiple runs? Similarly, in section 5.1.2 authors need to clarify these questions and the experiments are fair to support their claim.  

Given the theoretical part is a contribution, the experiments at the current version do not support their claim fully.  I will consider raising my scores if authors can clarify my questions.  
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: Summary: This paper endeavors to develop some theoretical understanding of why attention mechanisms improve the performance of neural networks. It includes some theory around the sample complexity of models which have a multiplicative mask in them, as well as a few related experiments.

Review: Having some theoretical analysis of the benefits of attention is definitely needed and I commend the authors for working towards this goal. The main issue that I have with the paper is that the model initially considered (introduced in section 2) is unrelated to attention mechanisms because the attention weights "a" do not depend on the input in any way. If I understand correctly, the ground-truth function y_i = f*(a* . x_i) assumes there is a single globally-correct attention mask a* for all examples. This is not attention. Every attention mechanism that I am aware of depends on the input in some way (in other words, instead of a*, you'd have a function a*(x_i) which changes according to the input). Some additional discussion is needed to explain why it is interesting to study this dramatically simplified (to the point of not being relevant) model. For example, if it was explicitly described as a preliminary for the a*(x_i) case (section 3.2 onwards) it would make more sense. Similarly, the assumption ||a_0|| ≤ s_0 is not true for most attention masks in pratice. There are some hard attention mechanisms which try to induce binary masks/hard sparsity but they are extremely rarely used in practice. The combination of these two assumptions makes for what appears to me (if I'm understanding correctly) a somewhat trivial result that the "attention mechanisms constrain the parameters in a smaller space". Note that this criticism does not apply to section 3.2 where the attention mask is specified as a function of the input. Similarly section 4.2 relies on the "single attention mask" idea, which is the sole result considering generalization in the paper. Finally 5.1.1 consists of an experiment which assumes a model of the form G*(x . a*), where a* is a fixed random binary mask. Training a model to learn G* and a* has very little to do with attention - it is a learning problem where you have removed a subset of the features and are trying to determine the parameters of the function and which features were removed. The L_1 penalty on "a" is certainly a good way to learn to only include a sparse subset of your features, but again has very little relevance to most attention mechanisms (i.e. I know of almost no work which regularizes the attention mask in this way).

Overall I think most of the results in this paper are not relevant to attention models and as such it has limited impact. I would suggest reframing the paper around a focus on what the authors call the "self-attention" case (which is really just normal attention), possibly using the fixed a* case as a preliminary/motivation. I also would suggest removing the discussion of regularization the attention mask as I am not aware of this being used in practice. Finally I would suggest some more direct discussion of how the results apply to models which are used in practice.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper studies attention and self-attention networks from the theoretical perspective, giving the first (as far as this reviewer knows) results proving that attention networks can generalize better than non-attention baselines. This has been observed empirically before and it is very good to start the analysis of foundations of this phenomenon.

The results cover fixed-attention (as we understand both single-layer and multi-layer) and self-attention in the single layer setting. One interesting part that is not covered (and may be very hard) though is multi-layer self-attention networks. What is the equivalent of condition (A9) there? In other words: can we prove that the attention will learn correct attention masks if they exist, or do we need to assume that?

On the experimental side, the paper introduces L1 loss on the attention mask. This is (to the knowledge of this reviewer) a new idea and it would be interesting to see larger models (e.g., a Transformer on a translation task) trained with this additional loss. Does the analysis suggest L1 loss in any way, more than say L2?

I am grateful to the authors for their reply. The new multi-layer theorem is impressive and I'm grateful for clarifying the L1 loss. Have the authors considered variants of hard attention as well (e.g., training with attention that attends to at most 10 or 100 elements), could that play the role of L1 loss? I stand by my recommendation to accept this paper.
review_title: Official Blind Review #3

Meta-review: This paper aims to theoretically understand the the benefit of attention mechanisms. The reviewers agreed that better understanding of attention mechanisms is an important direction. However, the paper studies a weaker form of attention which does not correspond well to the attention models using in the literature. The paper should better motivate why the theoretical results for this restrained model would carry over to more realistic mechanisms.
Decision: Reject