Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work aims to understand how Transformers learn inductive biases as convolution when trained on large datasets with gradient descent. They provide detailed analysis and find that ViT relies on the positional attention mechanism that disentangles patches and positional encodings. And it also provides experimentS on the Gaussian data that show that ViTs do not learn the correct inductive bias under the assumption that "characterizing the distributions under which ViTs recover the structure of the function is an important question." Lastly, it also provides experiments on CIFAR and ImageNet.
strengths_and_weaknesses: Strengths:

1. The analysis of this work is completed and somehow interesting.
2. The definition and theorem on the patch association are good.


Weaknesses:
1. Even though the analysis is complete, the final results are not surprising and the improvement on downstream tasks is incremental. I think good work should be simple but effective or complex but effective. This work does not give me any new insight.
2. In Figure 1(a), why does the author state that ViTs learn the convolution inductive bias in vision datasets? I do not see any convolution inductive bias in this figure.


questions: Please refer to Weaknesses.
limitations: Please refer to Weaknesses.
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 paper provides a theoretical analysis of gradient descent on logistic loss under simplified formulations of model and data (represented as a collection of $D$ tokens/patches). The assumptions and their relevance are detailed below, but briefly at high level the data assumption models presence of structured association between patches, and the model captures a (significantly) simplified attention mechanism that is loosely motivated from transformer models.  
The key result shows that gradient descent in a range of hyperparameters learn the patch associations under the model and data assumptions (more details below). 

strengths_and_weaknesses: The main results to my knowledge are correct except for the point under “Technical questions” below – although I did not check all the proof details. This work is in the line of results that aim to identify interesting inductive biases of models learned using gradient descent. Modern neural networks are extremely complex to theoretically capture in full generality and inevitably any mathematical analysis would rely on significant simplifications. My evaluation of the paper relies on to what extent the paper provides new ideas/insights into the workings of attention based models and I discuss the strengths and weaknesses of the assumptions below.

*Data assumption:* The data distribution in Definition 3.1 captures scenarios where learning patch/token associations are important, in a sense that the labels as well as marginals depend on certain grouping of tokens. In a nutshell, the $D$ data patches are grouped into L disjoined sets ${S_l:l=1,2,…,L}$ where each set has $C$ patches, with $C<<D$. The goal is to understand when a model/algorithm can learn the patch association/groupings $S_l$.  The dimension scaling in the data model captures high SNR scenarios with spurious features. 
This is a good simple data model to theoretically understanding of learning structures present in data and is of interest beyond this paper. Secondary results in the paper establish that this model is *not* learnable by any generalized linear model, and moreover it is possible for a one-layer transformer model can represent the labeling distribution even without learning the patch association structure (Thm 3.1 & 3.2). 

*Model and hyperparameter assumption:* The model on inputs denoted as $X\in\mathbb{R}^{d\times D}$ that is studied by the paper can be written as 
$$ F(X)=\sigma(\langle X, v\cdot s_i^\top\rangle),\text{ where } s_i=softmax(a_i)$$
where $a_i\in\mathbb{R}^D$ for $i=1,2,\ldots, D$ and $v\in\mathbb{R}^d$ are unconstrained parameters over which gradient descent is performed, and $\sigma$ is polynomial activation. $S,A$ are $D\times D$ matrices with ${s_i},{a_i}$ along the rows. 

In my evaluation, the main shortcoming of the paper is that the simplifications in model and hyperparameter assumptions do not capture aspects of transformer/attention-based models to a sufficiently satisfactory extent. The authors acknowledge that in their paper in multiple places and I am not opposed extreme simplifications if they capture some new insight about the models the paper aims to address. Unfortunately, with the combination of above modeling choice, it is not clear what aspects of attention model are still being captured. 

1.	The motivation for the formulation is based loosely on transformers, where A and S correspond to attention and score matrices. However, the connection is very loose in that A does not depend on the inputs at all.  Even with the simplification that the attentions only depend on the positional encoding (which I think is reasonable for image tasks and is also justified with experiments), the standard form would involve parametrizing $A$ in factorized form as $P^\top W_QW_K^\top P$ -- even though the factorized form does not change representation, it is certainly known to change the gradient descent dynamics which is not captured in this form. As stated in the above equation, it is unclear how the model even distinguishes attention mechanism from any other simplification of fully connected networks.

2.	A more important concern for me arises from the choice of initialization hyperparameters. With initialization $a_{ii}=polyloglog(d)$ and $a_{ij}=1/poly(d) $. This provides a strong prior on initial score matrices as $s_ii\approx 1-o(1)$ and $s_ij=O(1/d)$ -- i.e., the scores are explicitly chosen to be diagonally dominant. This in comparison to even the simplified parametrization as $A=P^\top W_QW_K^\top P$ would lead to a more balanced scores at initialization—thus the initialization is truly agnostic to structure and the mechanism if learns patch association at all will have to learn from scratch.


questions: Technical questions:

In proof of Lemma 4.2 in Appendix I.1, I believe the second line in eq. in 205 does not hold $\xi$ also appears as part of $X$ in other terms. To elaborate, from Definition 3.1, X depends on samples of $\xi_j, \delta_j, l(X)$, so the expectation is of the form $E_{\xi,l(X),\delta_j) g(X)X$ cannot in general be split as $E[g(X)E_\xi[X]]$. From briefly checking the options, I think we need $\xi_j=0$ as assumption for he lemma to go through.  

Other comments:

(a)	In the context of the analysis and results in the paper, it’s unclear what the significance of the the Gaussian noise $\xi_j$ in the data model in Defn. 3.1. From my understanding of the proof, although the noise technically captures a more general model, it does not provide any new insight into the analysis/results itself and merely leads to complicated bookkeeping. If I had missed their significance, I request the authors to clarify in their response. If not, having a simpler analysis without the noise as the main result would improve the readability of the paper significantly (the noisy general analysis could be deferred to separate appendix section). 
   
(b)	Definition 2.3 might need slight modification of wording to ensure there are no-tie breaking required for top_C, for example for a model that learns all position encoding as the same, say $p_i=p$, whether it learns patches or not according to this definition depends on how we do the tie breaking. 

(c)	Definition 2.1: where each *patch* X -> *input* X 

(d)	Fig 2: what is the kernel size of f^*? Also, it is unclear what exactly is being plotted in UpperRight in the  DxD matrix – if it is the ideal convolutional structure, why is it not all 1 in the diagonally entries? For LowerRight, what is the normalization used (not that P^\top P  is not intrinsically normalized)

(e)	One way to rephrase the insight of Fig 2. Is that the patch learning may not happen when merely $f^*(X)=y|X$ has a patch structure, but rather we might require conditions on marginals of distribution over X to have patch structure – this might have been obvious to the authors and experts, but I believe some readers might benefit from explicitly stating this intuition. 

limitations: Yes
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: As observed by the authors, the advent of the vision transformer architecture is surprising given that their network structure has nothing specifically curated for vision problems. This raises the question of how it is that, in training a vision transformer, certain desirable properties for vision problems are obtained in the resulting models.  In the abstract authors refer to these as "convolutional-like patterns", by which they mean the patches of the image are embedded with high cosine similarity to adjacent patches. The question the authors seek to address is how it is that there resulting positional encodings are learnt.

The model considered is called by the authors "positional attention" which, if I understand correctly, consists of a single self-attention layer where only the positional embeddings are fed into the attention mechanism when computing the attention matrix. In this setting, when the query and key matrices are held fixed as identities (Assumption 3.1), the one-layer model learns to associate patches in a manner consistent with the assumed data generating process, (1), i.e. Theorem 4.1.
strengths_and_weaknesses: I will preface this section by observing that I believe the term "convolutional pattern" to be a misnomer and misleading. The defining quality of the convolutional layer is translation invariance. What the authors study instead is how transformers learn positional embeddings with high local cosine similarity; which is quite different from a more interesting question which is how transformer models adapt to domains where convolutional architectures have remained dominant. For my review I will use the terminology consistent with the paper. The confusion extends to the description of the partitions $(\mathcal{S}_\ell)_\ell$ being "convolutional".

#### Strengths
* While I have not examined the supplementary material in detail, the authors have a technical work with nontrivial results which I applaud. 

* The paper is well written with good, clear notation. 

* In Section 3 that the authors make an effort to show the nontrivially of the data generating process in sense that it cannot be fit with low error by a GLM. (Theorem 3.1) . I.e. learning the positional embeddings is necessary generalisation given the data generating process. 

* The permutation experiments in Section 4 are interesting. 

#### Weaknesses
The biggest weakness for this work I feel is the overall style. The original question posed by the authors "****how**** do ViTs learn [convolutional patterns] by solely minimizing their training loss?" is an interesting one. However it is not clear to me how the (well written) theorems and results shed light on this question. 



#### Typographic:
- [90] $\mathcal{S}_\ell  \subsetneq  D$ should read $\mathcal{S}_\ell  \subsetneq  [D]$ and a quantifier over $\ell$ should be inserted: "for all $\ell \in [L]$"
- [195] Observe your hyperlink to "Assumption 3.1" is linking to a theoremlike environment titled "Simplification 3.1"
questions: * What is missing from this paper are two things, one which may be more easily addressed than the other: 
	1. what the relationship is between this simplified structured partitioning problem and and the real phenomenon of local cosine similarity among positional embeddings in a vision transformer; and
	2. what these results tell us about the "*how*" portion of the question posed above. 

* Supposing (1) is answered, the results in the paper appear merely to prove that the phenomenon happens, rather than answering questions about how or why it happens.

* The closest insight to (2) this appears to be Theorem 3.1 which says that GLM's cannot solve these structured problems. Okay, so we must need something more complicated than a GLM? Is it a ViT? is it a single layer positional attention model? Is it something else we haven't even thought of?

* By removing the inputs from the attention mechanism, is it really fair to call the resulting architecture "attention" at all? 

* The conclusion reads *"Our work is a first step towards understanding how Transformers learn tailored inductive biases when trained on large datasets with gradient descent."* What exactly the first that first step? What new understanding should I take away from this work about the behaviour of vision transformers. 

limitations: * The work would be strengthened by an analysis of the limitation of the data generating process assumption. Since this is not the way labels yielded conventionally for vision transformers. I.e. in the case of the ViT the features were extracted from the `[pad]` token output. 

* Much of the discussion about "competitiveness" of "positional attention" seems like it would have benefitted by an analysis looking at how much of the error gradient flowed to the original input matrix $X$ in the sum $X+P$ in the pre-transformer layer. In the sense that if really it makes no difference to tweak the architecture in this fashion then $\mathrm{SA}(X;P) \approxeq \mathrm{PA}(X; P)$. Really the point here should be to argue for the modifications to the architecture for positional attention, which I am not observing. 

* Still the more fundamental question about translation invariance of convolution seems to be have forgotten despite "convolution" appearing throughout.

* Given the implications and assumptions made here, and the claim that this is a first step towards understanding something, what are the possible next steps? What is the next step get more of a handle on features of the transformer architecture that either make it unique, or ordinary?
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Vision Transformers

The paper focuses on trying to explain how Vision Transformers learn the spatial locality biases on images. To do so, authors mathematically analyze the learning of convolution-like structures on ViT and test their idea with some synthetic datasets based on CIFAR.


strengths_and_weaknesses: PROS:
- the paper seem to be very detailed and provides a mathematical analysis of ViT

CONS:
- very hard to read
- limited/niche contribution

DETAILS:
Generally speaking, this paper is VERY difficult to follow. My background is computer science but I found it hard to read this paper that is FULL of definitions, assumptions, definitions, theorems but, most importantly, the paper introduces many many letters in each section.

The math seems reasonable but I have to admit that around line 200 I was already a bit lost and I could not follow the paper so well. I might have missed something. This raises also a problem for me: I did not understand how ViT learns the spatial inductive bias after reading 9 pages only about that. Moreover, I am not even sure that the tests done with 1-layer ViTs are generalizable to more layers.

Moreover, I think the paper misses one main point: explaining WHY it is important to learn how ViT learns the inductive biases. I know it sounds a stupid comment, but without this explanation a reader is not intrigued by the paper and the heavy math inside it. Then, once we know that “ViT do not just group nearby pixel together” why is it useful? I mean, I am very naive but self-attention is based on content, so I am not surprised that it does not group nearby pixel together.

Here some details from my review:
- L29: not clear. Are you just saying that near pixels are more similar to distant pixels? Because it not so clear that distant pixels encode “abstract" features. 
- Figure 1 b should not be there. Better to move it near the text.
- L80 this notation is not a related work, is it?
- L90 at this point is not clear what C is
- L91 why is a definition expected to be an assumption? L90-94 is not clear at all
- The test of L116-129 is not so clear to me. Where is the cubic activation applied? Why 1 layer? Would you have the same result with more layers? not clear to me
- L140 is Threshold_0.9C might be Threshold_0.9
- I would modify the title in something more clear like “How do Vision Transformers learn…"
questions: - The test of L116-129 is not so clear to me. Where is the cubic activation applied? Why 1 layer? Would you have the same result with more layers? not clear to me
- Why do we need to learn so well how positional encodings are learned?
limitations: I think the authors do not have major limitations or negative societal impact.
review_title: null

Meta-review: metareview: This paper provides a theoretical analysis of the empirical finding that Vision Transformers learn position embeddings that recapitulate the spatial structure of the training data, even though this spatial structure is no longer explicitly represented after the image is split into patches. The reviewers are generally satisfied by the soundness of the theory, but there is some disagreement regarding the significance of the contribution. The AC believes this paper asks an interesting theoretical question, even if (as is often true) it can only be answered in a simplified setting, and the answer is nontrivial. The AC thus recommends acceptance.
confidence: Less certain
Decision: Accept