Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a theoretical bound on inductive biases self-attention module can represent. It gives detailed walkthrough about how such bound can be derived and the result complements conclusion from prior works. The conclusion of this paper is very interesting that the complexity of sparse boolean function that a self-attention module can capture is logarithmically dependent of the context size. It could cast insights on future probing works and dataset designs. A downside, however, is the experiment part which only focused on a synthetic task. Analysis is largely absent.

main_review: 1. The writing might need some improvements. The notation m and T were initially very hard to understand, until to the final page, I realize m denotes sample size while T denotes context length.

2. At Corollary 4.4, the paper mentioned "...highlighting the inductive bias of the transformer towards selecting sparse functions of the context" and then later in section 5, "The theory predicts the sample complexity of learning a bounded-norm transformer should match this scaling in T". This is very interesting to me, but not sure how it is verified in Fig 2. There are some log-scaled correlation in the middle figure, but don't know what it says. For instance, the sample complexity should match the scaling of T, but for what goal?

3. Based on the main takeaway I learnt from this paper, I wonder if it means, imagine in a coreference resolution task, the mention coreference is super dense while the context length is short. This could be challenging for a transformer to handle. But what if keeping the same amount of coreference links but synthetically increase the context size, would the task become easier? I imagine this can be a more real task (even though it might still be synthetic, but more realistic than a dataset of boolean functions) to experiment with. Furthermore, having a realistic data is good to show if the main conclusion of this paper is valid and the bound is a tight one in real application. Otherwise, the logarithmic dependency might not be established.

summary_of_the_review: I think this paper proposes an interesting conclusion from its derivation of the theoretical bound on self-attention modules. The amount of contribution on the theoretical part seems substantial. But the verification part is weak. I don't feel I am confident to eat the takeaway from what I see in the experiment section.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper provides a theoretical analysis of the functioning of the self-attention modules. The paper shows that the Transformer architectures with some modifications (for ex. bounded norm) can create sparse variables. The paper proposes an experimental protocol to support the analysis. 

main_review: Pros:

- The paper is very well written.
- The paper tackles an important problem of studying the inductive bias of attention module.
- The idea of sparse variable creating is interesting and relevant to the larger deep learning community in general. 

Cons:

- The experimental results are only on a synthetic task. It would be useful to study it on more complex tasks (as mentioned in the future work section of the paper). 

Related Work:

- The basic idea involves the  sparsity of functions learned by attention systems, and more precisely attention heads as found in Transformers. The analogy to "attention heads" as functions in typed argument programming languages and representation of different "positions" as different variables has been made before such that different heads only need to attend to sparse subset of positions [1, 2].

- [1] RIMs, https://arxiv.org/abs/1909.10893
- [2] NPS, https://arxiv.org/abs/2103.01937 
summary_of_the_review: The paper presents a theoretical analysis of the inductive bias of self-attention models, showing that the transformer architecture can learn sparse functions with some modifications.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper claim that they contribute to the norm-based generalization bound of the Transformer model. The paper uses its Lipschitzness to get the bound of self-attention model. With this bound, the paper analyses the inductive biases of self-attention modules; it investigates which function and the long-range dependencies the self-attention modules represent. This paper aims to answer this new question. It presents a theoretical finding that bounded-norm TransformerTransformer can fit sparse functions of the input sequence with sample complexity scaling only logarithmically with the context size. This paper also empirically validates this finding and the scaling law. 

main_review: Strengths:  
1 This paper asks an essential question about the expressive power of attention and derives low-norm-based bounds for attention head, self-attention head, and the transformer model.

2 The bound in this paper has logarithm dependence on sequence length. These results indicate a finding that Transformer selects sparse functions of context and validates them with empirical analysis.

3 The theoretical analysis is rigorous with assumptions and detailed proofs.
 
Weaknesses: 

1 The paper is not clear enough. The formulation is a little complicated, although the authors describe the well-known methods. 
On page 5, the authors use the term tf-head before defining them; It would be better if the authors describe the two experimental tasks in detail;

2 This paper could do more practical experiments to show the usage of the bound or the finding of sub-linear scaling law.

3 The Related Work subsection has discussed many previous studies, but the paper does not compare or discuss previous methods in the theoretical analysis or in the empirical comparison.

Typos:
" (for eg, linear functions"-> e.g. linear functions, page 5


summary_of_the_review: I like the contribution of generalization bounds for Attention and Transformer models. But there are some weaknesses. Therefore, my recommendation is marginal above the borderline.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides rigorous norm-based bounds on the expressivity and inductive biases attention and self-attention provides when learning complex functions. The authors leverage established analytical tools involving complexity measurements, together with novel derivations for standard attention heads transformations,  to provide novel into generalization properties of Transformers, and into the types of functions they prefer to learn. Finally, the authors provide a set of simple numerical experiments using Boolean functions that serve as basic checks on their theory.
main_review: This paper adresses an important gap in theoretical understanding of attention-based systems that are widely used in state of the art models. It is very clearly written, despite the complexity of the subject matter and the difficulties inherent to the notation of attention methods. The motivation of the main findings is clear and timely, and I believe the general community will be interested and benefit from this contribution. Although I am not an expect in all the tools used in the derivations of the main results, I believe the work is correct, novel, and significantly contributes to our understanding of Transformer-like systems. 

I believe there are two main points that could be improved to further strengthen this contribution.

1- Sparcity:
One of the central findings of this paper involves the sparsity of functions learned by attention systems, and more precisely attention heads as found in Transformers. Indeed, on page 6 immediately following Corollary 4.4, the authors write 
"Our bounds have a logarithmic dependence on T highlighting the inductive bias of the transformer towards selecting sparse functions of the context"
I think the link between the bounded covering numbers and representation sparsity is not clearly fleshed out and could be unpacked a little further to appeal to a broader audience. Two things could be done. 
First, for the interested non-expert, why does logarithmic dependence of bounds governing covering numbers lead to *sparse* functions ? Some context and details here would be welcome. 
Second, most would already know informally that the softmax operation in attention weight computation leads to sparsity. This proof formalizes this in some way, and a discussion about the important role of the "Norm" component in the bounds, which is crucial, could be especially enlightening. Given these novel bounds, what would be the impact of using different Norm operations ? (e.g. Gumbel softmax v.s. softmax). Furthermore, not only is the softmax operation key in this result, it is also the major bottleneck for computational complexity, and a lot of work has been devoted to circumvent this problem (e.g. approximation of softmax by random kernels). How do the proposed bounds shed light on these issues ?

2- Experiments:
I understand that his is a theoretical contribution and that experiments play an supporting role in this paper. Nevertheless, the boolean functions experiments are Taylor-made to fit the bounds presented, and do not necessarily address the generalization properties associated with these bounds. A serious discussion about the type of experiments that could be carried out at scale by STOA systems, that would confirm the theoretical results, would strengthen the message. Moreover, two minor issues with regards to the experiment section remain. (1) While the finding of "sub-linear" scaling of sample complexity is consistent with scaling rates found analytically, the experimental results are far from confirming the same scaling. Sublinear can mean many things and is somewhat loose, and the experiments are noisy in that regard. A discussion about this limitation and what could be done to improve them would be welcome. (2) It appears this section might have been shortened or was added hastily as the main figure (Fig 2) has an incomplete caption (no description of the Left or center panel), and it appeals to the "{overfitting, correct} regimes" which are not discussed in the text (unless I missed it).

Some minor issues to correct:

* In definition 3.1, the Norm function definition involves a \Delta, I'm not sure what this represents. Is this a typo ? I might be mistaken but I don't recognize this as standard notation.

* In the proof overview of Thm 4, the second sentence is misswritten: "This property allows us to construct the cover by into covering..."

* The paragraph following Lemma 4.3 also suffers the same faith: "The key observation here is that the attention part of the network is computes using Norm..."

* In the description of the first numerical experiment in Section 5, it may be be good to explicitly refer to the appendix section containing more details as it is not clear how the task is implemented from the short description.

*In the Related work section, Theory for attention models, the authors might consider citing recent work directions establishing gradient norm bounds for (self-)attentive systems. e.g. "Untangling tradeoffs between recurrence and self-attention in artificial neural networks. Kerg et al., NeurIPS 2020"
summary_of_the_review: This paper is well-written, correct, and provides results that are significant and advance our understanding of attention mechanisms. I recommend publication. The reason I do not give it the highest score is because of two slight weaknesses: (1) lack of interpretation of the obtained bounds with respect to choices of Norm operation (2) Simplistic and only mildly convincing experiments.
review_title: null

Meta-review: This paper presents a theoretical analysis of self-attention modules, using Lipschitz conditions.

It suffers from two main weaknesses: the clarity of the presentation, and the weak experimental section.
Decision: Reject