Unveil Benign Overfitting for Transformer in Vision: Training Dynamics, Convergence, and Generalization

Authors: jiarui  jiang
wei  huang
miao  zhang
taiji  suzuki
liqiang  nie
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 15:00:02

Abstract: Transformers have demonstrated great power in the recent development of large foundational models. In particular, the Vision Transformer (ViT) has brought revolutionary changes to the field of vision, achieving significant accomplishments on the experimental side. However, their theoretical capabilities, particularly in terms of generalization when trained to overfit training data, are still not fully understood. To address this gap, this work delves deeply into the \textit{benign overfitting} perspective of transformers in vision. To this end, we study the optimization of a Transformer composed of a self-attention layer with softmax followed by a fully connected layer under gradient descent on a certain data distribution model. By developing techniques that address the challenges posed by softmax and the interdependent nature of multiple weights in transformer optimization, we successfully characterized the training dynamics and achieved generalization in post-training. Our results establish a sharp condition that can distinguish between the small test error phase and the large test error regime, based on the signal-to-noise ratio in the data model. The theoretical results are further verified by experimental simulation. To the best of our knowledge, this is the first work to characterize benign overfitting for Transformers.

Main paper: 
 introduction: 
 Transformers (Vaswani et al., 2017) have revolutionized numerous fields in artificial intelligence, ranging from natural language processing (Devlin et al., 2018; OpenAI, 2023) 2020) has been developed to advancing the computer vision tasks (Liu et al., 2021; Khan et al., 2022; Guo et al., 2022; Tolstikhin et al., 2021; Lin et al., 2014) compared to Convolutional neural networks. Since then, with the high performance, ViT emerged as a hot area of research and application. Numerous technologies and methods began to surface, including enhancing ViT's data and resource efficiency (Touvron et al., 2021; Hassani et al., 2021; Chen et al., 2021b; Touvron et al., 2022) , reducing heavy computation cost Chen et al. (2022) ; Zhu et al. (2024) ; Wang et al. (2023) .Recent success brought by ViT has been inspiring an increasing number of works to understand the ViT through empirical and theoretical studies. The empirical investigation works study the robustness (Bhojanapalli et al., 2021; Naseer et al., 2021; Paul and Chen, 2022; Bai et al., 2021) ; and the role in self-supervision (Caron et al., 2021; Chen et al., 2021c; Oquab et al., 2023) and others. On the other hand side, the theoretical works have been conducted to understand the ViT from the perspective of expressivity (Vuckovic et al., 2020; Edelman et al., 2022) , optimization (Zhang et al., 2020; Tian et al., 2023a,b) , generalization (Li et al., 2023a) , and in-context learning (Huang et al., 2023c; Garg et al., 2022; Bai et al., 2024; Ahn et al., 2024) .Despite the insightful understanding provided by the above investigations, it remains unclear how ViTs generalize to unseen data when they are trained to overfit the training data. In particular, the conditions under which ViTs can exhibit benign overfitting (Bartlett et al., 2020) , where the test error remains small despite overfitting to the training data, are not well understood. Moreover, prior work on the optimization and generalization of ViTs often focuses on simplified settings, such as linear transformers or unrealistic loss functions, due to technical limitations. In this work, we aim to fill this gap through a feature learning theory (Allen- Zhu and Li, 2020; Cao et al., 2022) . Based on a data generative model with M tokens composed of signal tokens and noise tokens and a two-layer ViT with softmax attention, we characterize the training dynamics from a random initialization and the generalization ability of the ViT after convergence. We establish a sharp separation in condition to distinct the benign overfitting and harmful overfitting regime for ViTs. Our contributions are summarized as follows:• We successfully characterize the optimization of the ViT through three different phases in dynamics that exhibit rich and unique behaviors related to self-attention. Building on the convergence results, we further characterize the generalization bounds on unseen datasets.• Technically, we develop novel methods to handle non-linear attention and the inter-dependent nature of multiple weights in transformer optimization when training from scratch.• We establish a sharp separation condition in the signal-to-noise ratio in data to distinguish the benign overfitting and harmful overfitting regimes of ViTs. This separation is then verified by experimental simulation. 
related work: 
 Benign Overfiting in Deep Learning The most prominent behavior of deep learning is its breaking of bias-variance trade-off in statistical learning theory, i.e., good generalization on unseen data even with overfitting on training data. This line of research starts from Bartlett et al. (2020) who studied benign overfitting in linear regression, learning data generated by a linear model with additive Gaussian noises. It is shown that at large input dimensions (which leads to over-parameterization), the excessive risk of the interpolation can be asymptotically optimal. Hastie et al. (2022) ; Wu and Xu (2020) studied linear regression when both the dimension and the number of samples scale together with a fixed ratio. Timor et al. (2023) proposed a unified data model for linear predictors and studied conditions under which benign overfitting occurs in different problems. Besides the studies on linear models (Wang et al., 2021; Zou et al., 2021; Zhou and Ge, 2023) , several recent works tried to study benign overfitting in neural networks (Frei et al., 2022; Kornowski et al., 2024; Chatterji et al., 2022; Xu et al., 2023) . In particular, Li et al. ( 2021) investigated the benign overfitting in two-layer neural networks with the first layer parameters fixed at random initialization. Furthermore, benign overfitting was characterized in convolution neural networks (Cao et al., 2022; Kou et al., 2023) , OOD (Chen et al., 2024) , federated learning (Huang et al., 2023b) , graph neural network (Huang et al., 2023a) by feature learning theory (Allen- Zhu and Li, 2020; Cao et al., 2022) . Unlike existing research on benign overfitting, this work focuses on ViTs.Optimization of Transformers Towards understanding the optimization of Transformers, Zhang et al. (2020) provided the analysis for adaptive gradient methods. Jelassi et al. (2022) proposed a spatially structured dataset and a simplified ViT model and showed that ViT implicitly learns the spatial structure of the dataset while generalizing. Besides, Li et al. (2023b) provided fine-grained mechanistic understanding of how transformers learn "semantic structure" for BERT-like framework (Devlin et al., 2018) . Furthermore, Tian et al. (2023a,b) characterizes the SGD training dynamics of a 1-layer Transformer and multi-layer Transformer respectively. They focused on the unique phenomena and the role of attention in the training dynamics. Huang et al. (2023c) studied the learning dynamics of a one-layer transformer with softmax attention trained via gradient descent in order to in-context learn linear function classes. In addition, Li et al. (2024) provided a theoretical 1. The label y is generated as a Rademacher random variable.2. If y = 1 then x 1 is given as µ + , if y = -1 then x 1 is given as µ -, which represents signals.3. A noise vector ξ 2 is generated from the Gaussian distribution N (0, σ2 p • (I -µ + µ ⊤ + • ∥µ∥ -2 2 -µ -µ ⊤ -• ∥µ∥ -2 2 )).4. Noise vectors ξ 3 , . . . , ξ M is generated i.i.d from the Gaussian distribution N (0, σ 2 p • (I -EQUATION)). 5. x 2 , . . . , x M are given by ξ 2 , . . . , ξ M , which represent noises.Our data model is envisioned by considering M tokens of the data points: x 1 , x 2 , . . . , x M , which can be seen as patches derived from image data. x 1 embodies the signal that is inherently linked to the data's class label, while x 2 , x 3 , . . . , x M represents the noise, which is not associated with the label. For simplicity, we assume that the noise patches is independently drawn from Gaussian distribution N (0, σ2 p •(I -µ+ µ ⊤ + •∥µ∥ -2 2 -µ -µ ⊤ -•∥µ∥ -2 2 )) and N (0, σ 2 p •(I -µ + µ ⊤ + •∥µ∥ -2 2 -µ -µ ⊤ -•∥µ∥ -2 2 )), ensuring the noise vectors remains orthogonal to the signal vectors µ + and µ -. Also, if σp is sufficiently larger than σ p , the input tokens will become sparse, which is consistent with the empirical observation that the attention and activation values in Transformer-based models are usually sparse (Child et al., 2019; Robinson et al., 2023) . We denote SNR = ∥µ∥ 2 /(σ p √ d) to represent the signal-to-noise ratio.Two-layer Transformer. We consider a two layer Transformer network with a self-attention layer and a fixed linear layer, which is defined as:EQUATIONHere, φ(•) : R M → R M denote the softmax function, W Q , W K ∈ R d×d h , W V ∈ R d×dv denote the query matrix, key matrix, and value matrix, respectively, and w O ∈ R dv denote the weight for the linear layer. We use θ to denote the collection of all the model weights. This model is a simplified version of the ViT model from Dosovitskiy et al. (2020) , making our analysis focus on the self-attention mechanism which is the most critical component of the ViTs.Given a training data set S = {(X n , y n )} N n=1 generated from the distribution D defined in Definition 3.1, where the subscript n represents the n-th sample, we train the two-layer Transformer by minimizing the empirical cross-entropy loss function:L S (θ) = 1 N N n=1 ℓ(y n f (X n , θ)),where ℓ(z) = log(1 + exp(-z)) and f (X, θ) is the two-layer Transformer. We further defined the population loss (test loss) L D (θ) := E (X,y)∼D ℓ(yf (X, θ)).Training algorithm. We consider Gaussian initialization for the network weights W Q , W K and W V , where each entry of W Q and W K is sampled from a Gaussian distribution N (0, σ 2 h ), and W V is sampled from N (0, σ 2 V ) at initialization. We use gradient descent to optimize training loss L S (θ), and the update of W Q , W K and W V can be written as follows:W (t+1) = W (t) -η • ∇ W L S (θ(t)),where W (t) can be designated as W Q , W K or W V .Recalling the ViT defined in Eq. ( 1), we can intuitively analyze its training dynamics and generalization: if more attention is paid to signals, i.e.,x ⊤ l W Q W ⊤ K µ ± ≥ x ⊤ l W Q W ⊤ K ξ i for i ∈ [M ]/{1}, then the vector φ(x ⊤ l W Q W ⊤ K X ⊤)X has a higher similarity with signals µ ± rather than with noises ξ i . In turn, W V together with w O have more chance to learn signals µ ± and utilize them to make prediction. At the same time, if vector W V w O learns signals µ ± more than noises ξ i , i.e., µ ± W V w O ≥ ξ i W V w O , then during the gradient descent training, the gradient send to x ⊤ l W Q W ⊤ K µ ± will be larger than that send to x ⊤ l W Q W ⊤ K ξ i . As a result, more and more attention is paid on signals and the similarity between signals µ ± and W V w O becomes increasingly high. Therefore, the Transformer can perform well on new data points. On the contrary, if much attention is paid to some noises in the training dataset and the model utilizes them for making prediction and optimizing the training loss, then the model can fit the training dataset well but might not perform well on the new test data. 
main results: 
 This section presents our main theoretical results which characterize the convergence and generalization of the ViT model under different sample size N and signal-to-noise ratio SNR = ∥µ∥ 2 /(σ p √ d). The results are based on the following conditions.Condition 4.1. Given a sufficiently small failure probability δ > 0 and a target training loss ϵ > 0, suppose that:(1) Dimension d h = Ω1 max{SNR 4 , SNR -4 }N 2 ϵ -2 . ( 2 ). (7) The standard deviation of Gaussian initialization σ V satisfies:σ V ≤ O ∥w O ∥ -1 2 • min{∥µ∥ -1 2 , (σ p √ d) -1 } • d -1 4 h. (8) The variance of Gaussian initialization Conditions (1) and ( 2) ensure an over-parametrized learning setting, and similar conditions have been made in the theoretical analysis of CNN models (Cao et al., 2022; Kou et al., 2023) . Condition (3) ensures that there are enough samples in each class with high probability. Conditions (4)-( 5) are intended to simplify the calculation, and can be easily generalized to M = Ω(1), ∥w O ∥ 2 = o(1) or ∥w O ∥ 2 = ω(1) setting. Conditions ( 6)-( 8) ensure that the Transformer can be effectively trained well. Condition (9) ensures that the Transformer is sufficiently overfitting the training data. Condition (10) ensures the sparsity of the input token features.σ 2 h satisfies: min{∥µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h • log(6N 2 M 2 /δ) -2 ≤ σ 2 h ≤ min{∥µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h • log(6N 2 M 2 /δ)Theorem 4.1 (Benign Overfiting). Under Condition 4.1, if N • SNR 2 = Ω(1), then with probability at least 1d -1 , there exist T = Θ(η -1 ϵ -1 ∥µ∥ -2 2 ∥w O ∥ -2 2 ) such that:1. The training loss converges to ϵ: L S (θ(T )) ≤ ϵ.2. The test loss is nearly zero: L D (θ(T )) ≤ o(1).Theorem 4.1 characterizes the case of benign overfitting. It shows that as long as N •SNR 2 = Ω(1), the Transformer can generalize well, even though it overfit the training data. To complement the above result and highlight the sharpness of this condition, we present the following theorem for the regime of harmful overfitting.Theorem 4.2 (Harmful Overfiting). Under Condition 4.1, if N -1 • SNR -2 = Ω(1), then with probability at least 1d -1 , there existT = Θ(N η -1 ϵ -1 σ -2 p d -1 ∥w O ∥ -22 ) such that:1. The training loss converges to ϵ: L S (θ(T )) ≤ ϵ.2. The test loss is high: L D (θ(T )) = Θ(1).Theorem 4.2 shows that if N -1 • SNR -2 = Ω(1), the trained Transformer has a high test loss as a result of overfitting the noises in the training data. Theorem 4.1 and Theorem 4.2 reveals a sharp phase transition between benign overfitting and harmful overfitting.Comparison with other results. Firstly, compared with CNNs with ReLU q network result (Cao et al., 2022) , when signal-to-noise ratio is small (SNR ≤ 1), our results show that ViTs require less number of samples to gengeralize well, which reflects the advantage of Transformers. Secondly, previous theoretical benign overfitting analysis of CNNs with ReLU activations rely heavily on signal strength ∥µ∥ 2 and signal-to-noise ratio SNR (Kou et al., 2023; Meng et al., 2023) , i.e., SNR 2 = O(1/N ) and require ∥µ∥ 2 to be large enough, while our analysis does not need to impose restrictions on these conditions. Thirdly, previous works only show when Transformer can generalize well (Li et al., 2023a; Deora et al., 2023) , while we demonstrate harmful overfitting as a complementary, which reflect that our benign overfitting condition is tighter and more precise. 
proof sketch: 
 This section discusses our main challenges in studying ViT's training dynamic, and presents our technical solutions to overcoming them. The complete proofs are given in the appendix.Our first main challenge is to deal with the three matrices W Q , W K and W V . In contrast to CNN models, whose convolutional kernels can be treated as vectors and thus allow for a more straightforward analytical approach (Cao et al., 2022; Kou et al., 2023) , the QKV matrices within the Transformer model are inherently complex to analyze. Moreover, their mutual interactions further complicate the analysis. To circumvent this complexity, Oymak et al. ( 2023 Q = W (0) K = I).Although their approach simplifies the analysis, it is not conducive to showing the dynamics of QKV interactions, i.e., how W Q , W K , and W V affect each other.In order to simplify the analysis of QKV dynamics without losing rigor, we propose key techniques called Vectorized Q & K and scalarized V. The basic idea comes from the property that the product of token feature vectors with the QKV matrices results in vectors, e.g., µ ⊤ + W Q , ξ ⊤ 2 W Q , etc., which are more amenable to analysis. Further, each entry of matrix XW Q W ⊤ K X ⊤ can be regarded as the inner product of two vectors, e.g.,µ ⊤ + W Q W ⊤ K µ + = ⟨µ ⊤ + W Q , µ ⊤ + W K ⟩.Therefore, the dynamics of attention can be studied by analyzing the dynamics of the vectorized Q & K defined as follows:Definition 5.1 (Vectorized Q & K). Let W (t)Q and W (t) K be the QK matrices of the ViT at the t-th iteration of gradient descent. Then we define the vectorized Q and vectorized K as followsEQUATION+ = µ ⊤ + W (t) K , k (t) -= µ ⊤ -W (t) K , k (t) n,i = ξ ⊤ n,i W (t) K , for i ∈ [M ]\{1}, n ∈ [N ].With Definition 5.1, denoting S + := {n ∈ [N ] : y n = 1}, S -:= {n ∈ [N ] : y n = -1}, we further analyze the dynamics of the vectorized Q & K. By carefully computing the dynamic of q (t) + , we haveEQUATIONwhere φ(t) n,i := φ(x ⊤ n,i W (t) Q W (t)⊤ K X ⊤ n ) is a shorthand notation, and w ⊤ O W (t)⊤ V X ⊤ n and X n W (t) Kcan be viewed in the following formsw ⊤ O W (t)⊤ V X ⊤ n = µ ⊤ + W (t) V w O , ξ ⊤ n,2 W (t) V w O , . . . , ξ ⊤ n,M W (t) V w O , X n W (t) K = k (t)⊤ + , k (t)⊤ n,2 , . . . , k (t)⊤ n,M ⊤ .Thus q (t+1) +q (t)+ can be decomposed into a linear combination of k(t)+ and k(t)n,i . Therefore, Eq. ( 2) can be further expanded as q (t+1) + q(t) + = α (t) +,+ k (t) + + n∈S+ M i=2 α (t) n,+,i k (t)n,i , where (αEQUATIONn,+,2 , . . . , α(t) n,+,M ) = η N M n∈S+ -ℓ ′(t) n ∥µ∥ 2 2 w ⊤ O W (t)⊤ V X ⊤ n (diag(φ (t) n,1 ) -φ (t)⊤ n,1 φ (t)n,1 ). Intuitively, if α+,+ is larger enough than α(t)n,+,i , then ⟨qEQUATION+ ⟩ will grow faster than ⟨qEQUATIONn,i ⟩, which means token µ + will pay more attention to µ + rather than ξ n,i . The dynamics of q (t)-, q (t) n,i , k (t) + , k (t)-and k (t) n,i are similar to q (t) + , and we can study the dynamics of QK matries by analysing the linear combination coefficients such as α(t) +,+ , α (t) n,+,i . As x ⊤ n,i W (t)V w O are scalars and their dynamics contain a factor ∥w O ∥ 2 2 , we define the scalarized V as follows. Definition 5.2 (Scalarized V). Let W (t)V be the V matrix of the ViT at the t-th iteration of gradient descent. Then there exist coefficients γ(t) V,+ , γ (t) V,-, ρ (t) V,n,i such that µ ⊤ + W (t) V w O = µ ⊤ + W (0) V w O + γ (t) V,+ ∥w O ∥ 2 2 , µ ⊤ -W (t) V w O = µ ⊤ -W (0) V w O + γ (t) V,-∥w O ∥ 2 2 , ξ ⊤ n,i W (t) V w O = ξ ⊤ n,i W (0) V w O + ρ (t) V,n,i ∥w O ∥ 2 2 for i ∈ [M ]\{1}, n ∈ [N ].With the Vectorized Q & K and scalarized V, one can simplify the study of the Transformer learning process to a meticulous calculation of the coefficients such as α, γ, ρ throughout the training period. So how to calculate the dynamics of these coefficients is a key point in our analysis. In the next subsection we describe how to handle softmax function and further give bounds for these coefficients.Our second challenge is to deal with the softmax function, which is the critical component and introduces non-linear transformation in our Transformer model.As W Q and W K are within the softmax function and W V is outside the softmax function, we divide the dynamic of training process into two key aspects: (1) How W Q and W K affect W V ; (2) How W V affects W Q and W K . Next, we present our approach to addressing these two critical issues.1. How W Q and W K affect W V : Without loss of generality, we take a data point (X n , y n ) with y n = 1 as an example and provide the dynamics for γ (t)V,+ and ρ (t) V,n,i in W V as follows: Lemma 5.1 (Dynamics of γ and ρ). γ (t+1)V,+ -γ (t) V,+ = η∥µ∥ 2 2 N M n∈S+,s∈[M ] -ℓ ′(t) n exp(x ⊤ n,s W (t) Q W (t)⊤ K µ + ) exp(x ⊤ n,s W (t) Q W (t)⊤ K µ + ) + M k=2 exp(x ⊤ n,s W (t) Q W (t)⊤ K x n,k ) |ρ (t+1) V,n,i -ρ (t) V,n,i | ≤ 2ηC 2 p σ 2 p d N M s∈[M ] -ℓ ′(t) n exp(x ⊤ n,s W (t) Q W (t)⊤ K ξ n,i ) exp(x ⊤ n,s W (t) Q W (t)⊤ K µ + ) + M k=2 exp(x ⊤ n,s W (t) Q W (t)⊤ K ξ n,k ) for i ∈ [M ]\{1}, n ∈ S + , where ℓ ′(t) n := ℓ ′ (y n f (X n , θ(t))) is a shorthand notation.In benign overfitting regime where N • SNR 2 = Ω(1), the factor n∈S+ η∥µ∥ 2 2 N M is larger than2ηC 2 p σ 2 p d N M .Therefore, as long asEQUATIONV,+ will grow faster than ρ (t) V,n,i . In other words, if q (t) ± and q (t) n,i prefer to align with k (t) ± rather than k (t) n,i , then W V would prefer to learn signals rather than memorize noises.How W V affects W Q and W K : Recalling that (αEQUATIONn,+,2 , . . . , α(t) n,+,M ) = η N M n∈S+ -ℓ ′(t) n ∥µ∥ 2 2 w ⊤ O W (t)⊤ V X ⊤ n (diag(φ (t) n,1 ) -φ (t)⊤ n,1 φ (t)n,1 ), where the most complicated part is the matrix (diag(φ(t) n,1 ) -φ (t)⊤ n,1 φ (t)n,1 ). We observe that the matrix diag(φ(t) n,1 ) -φ (t)⊤ n,1 φ (t)n,1 has two important properties:1. The diagonal elements are positive, while the elements on the off-diagonal are negative. 2. The sum of each row and column of this matrix is 0.Based on properties 1 and 2, we can deduce the following conclusion: as long as µ ⊤ + W(t)V w O is larger enough than ξ ⊤ n,i W (t)V w O , we have α(t)+,+ ≥ 0 and α(t)n,+,i ≤ 0, implying that q (t)+ prefers to align k (t) + rather than k (t) n,i .In summary, if more attention is paid to signals, W V learns the signals faster than it memorizes the noises; conversely, if W V learns the signals significantly more than it memorizes the noises, more attention will be paid to signals rather than noises. In other words, W Q , W K and W V promote each other.Our third main challenge is to deal with the complicated relation among the coefficients, e.g., γ, ρ, α. Inspired by the two-stage analysis utilized by Cao et al. (2022) to decouple the coefficients in CNN models, we analyze the ViT training process in three stage. In the following, we explain the key steps for proving Theorem 4.1. The proof for Theorem 4.2 is similar and we detail it in the appendix.Stage 1: The analysis in 5.2 shows that W Q , W K and W V can promote each other. But this process of mutual reinforcement requires some conditions, e.g.µ ⊤ + W (t) V w O is sufficiently larger than ξ ⊤ n,i W (t)V w O which does not necessarily hold for Gaussian initialization, complicating the proof. Stage 1 was introduced to solve this problem, and Lemma 5.2 formally describes this stage: Lemma 5.2 (V's Beginning of Learning Signals). Under the same conditions as Theorem 4.1, there existT 1 = 10M (3M +1)N ηd 1 4 h (N ∥µ∥ 2 2 -60M 2 C 2 p σ 2 p d)∥w O ∥ 2 2such that the first element of vector X n W (t)V w O dominate its other elements, that is,µ ⊤ + W (t) V w O ≥ 3M • |ξ ⊤ n,i W (t) V w O | for all n ∈ S + , i ∈ [M ]\{1} and µ ⊤ -W (t) V w O ≤ -3M • |ξ ⊤ n,i W (t) V w O | for all n ∈ S -, i ∈ [M ]\{1}.With Lemma 5.2, we can guarantee the monotonicity of attention on signals for t ≥ T 1 , which allows us to concentrate on analyzing the growth rate of attention in the following stages.Stage 2: Note that the output of softmax function has an upper bound 1, thus the output of ViT can be bounded by max{|µ ⊤ ± W (t)V w O |, |ξ ⊤ n,i W (t)V w O |}. By Lemma 5.1, it can be proved that there exists T 2 = Θ η -1 ∥µ∥ -2 2 ∥w O ∥ -2 2 log(6N 2 M 2 /δ) -1 such that:max{|µ ⊤ ± W (t) V w O |, |ξ ⊤ n,i W (t)V w O |} = o(1), and further get 1/2o(1) ≤ -ℓ′(t) n≤ 1/2 + o(1). Therefore, one can simplify the dynamics of the coefficients (e.g., γ, ρ, α) by plugging the tight bounds of -ℓ′(t)n . The following lemma provides some bounds for the dynamics of W Q , W K andW V in Stage 2. Lemma 5.3 (Dynamics of QKV in Stage 2). Under Condition 4.1, if N • SNR 2 = Ω(1), then with probability at least 1d -1 , there exist constant C, T 1 = Θ η -1 d-1 4 h ∥µ∥ -2 2 ∥w O ∥ -2 2 and T 2 = O η -1 ∥µ∥ -2 2 ∥w O ∥ -22 such that:EQUATION± , k± ⟩ -⟨qEQUATIONn,j ⟩ ≥ log exp ⟨qEQUATION± ⟩ -⟨qEQUATION± ⟩ -⟨qEQUATIONn,j ⟩ ≥ log exp ⟨qEQUATION± ⟩ -⟨q(T1) n,i , k (T1) n,j ⟩ + η 2 Cσ 2 p d∥µ∥ 2 2 ∥wO∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ) 2 • (t -T 1 )(t -T 1 -1) for i, j ∈ [M ]\{1}, n ∈ [N ], t ∈ [T 1 , T 2 ].Lemma 5.3 presents the training dynamics of W Q , W K and W V under benign overfitting regime in two aspects: direction and speed, that is,• direction: W V w O prefer to learn the signals rather than memorize the noises; more and more attention is paid to signals, while the attention on noises is decreasing. • speed: The inner products of µ ± and W V w O grow at a linear rate; the inner products of label-related vectorized Q & K grow at a logarithmic rate.Stage 3: As the training process going on, the loss begins to converge, and the loss derivatives -ℓ′(t)n no longer remain near 1/2. Therefore, the increasing rate of the inner products of vectorize Q & K and µ ⊤ ± W V w O begins to diminish. Based on the analysis in Stage 2, the attention is sufficiently sparse at the beginning of Stage 3. In other words, the attention on the signals is nearly 1, while the attention on the noises is nearly 0. According to this sparsity, µ ⊤ ± W (t)V w O will grow much faster than ξ ⊤ n,i WV w O by Lemma 5.1, and Lemma 5.4 provides the lower bound of µ ⊤ ± W (t)V w O . Lemma 5.4. Under the same conditions as Theorem 4.1, there existsT 3 = Θ η -1 ϵ -1 ∥µ∥ -2 2 ∥w O ∥ -2 2 log(6N 2 M 2 /δ) -1 such that: µ ⊤ + W (t) V w O ≥ log exp(µ ⊤ + W (T2) V w O ) + ηC∥µ∥ 2 2 ∥w O ∥ 2 2 (t -T 2 ) , µ ⊤ -W (t) V w O ≤ -log exp(-µ ⊤ -W (T2) V w O ) + ηC∥µ∥ 2 2 ∥w O ∥ 2 2 (t -T 2 ) for t ∈ [T 2 , T 3 ],where C is a constant, T 2 is the last iteration of stage 2.Convergence: Lemma 5.4 provides logarithmic lower bounds for µ⊤ ± W (t) V w O . Plugging t = T 3 into these inequality, we have |µ ⊤ ± W (t) V w O | ≥ log Θ(1/ϵ) , then as long as |ξ ⊤ n,i W (t) V w O | is sufficiently small, it can be proved that y n f (X n , θ(t)) ≥ log 1/ϵ for all n ∈ [N ], thus ℓ(y n f (X n , θ(t))) = log(1 + exp(-log(1/ϵ))) ≤ ϵ and L S (θ(t)) ≤ ϵ.The convergence of ViT is accordingly obtained.Generalization: Consider a new data point (X, y) generated from the distribution defined in Definition 3.1. Without loss of generality, we suppose that the signal token is µ + and the label is 1, i.e. X = (µ + , ξ 2 , . . . , ξ M ), y = 1. It is clear that ξ ⊤ i W Q W ⊤ K µ ± has a mean zero, which implies that the attention on the signals in the test data may not necessarily be as high as that in the training data. However, the sparsity of attention during training process creates conditions for W V w O to utilize the signals to make predictions, facilitating the generalization of the ViT. We provide the lower bound for the output of ViT on the unseen data with high probability as follows: Lemma 5.5. Under the same conditions as Theorem 4.1, there existsT 3 = Θ η -1 ϵ -1 ∥µ∥ -2 2 ∥w O ∥ -2 2 log(6N 2 M 2 /δ) -1 , with probability at least 1 -δ/N 2 M , yf (X, θ(T 3 )) ≥ log(C/ϵ) C ′ -1,where C and C ′ are constants. Lemma 5.5 shows that yf (X, θ(T 3 )) is large with high probability, and through careful calculation, we can provide a small bound for test loss. More details are in Appendix D.4. 
experimental verification: 
 We present simulation results on synthetic data and MNIST dataset to verify our theoretical results. Synthetic data experiments results: Figure 1a shows that as N and SNR increase, the test loss tends to decrease. As Figure 1b shows, the theoretically derived red curve (N • SNR 2 = 1000) almost follows the experimental dividing line between the yellow area (test loss > 0.2) and the purple area (test loss < 0.2). These experimental results further validate our theoretical results, that is, the sharp condition separation between benign and harmful overfitting, where N • SNR 2 = Ω(1) is a precise condition for benign overfitting and N -1 • SNR -2 = Ω(1) is a precise condition for harmful overfitting. More experimental results on the dynamics of QKV can be found in Appendix A.  
conclusion: 
 This paper studies the training dynamics, convergence, and generalization for a two-layer Transformer in vision. By analyzing the Vectorized Q & K and scalarized V in three-stage decomposition and carefully handling the softmax function, we give the precise increasing rate of the attention and output of the Transformer in the training process, and further analyze its generalization performance. Our theoretical results reveal a sharp condition separation between benign and harmful overfitting. One limitation of our methodology is our proof technique relies heavily on the sparsity of feature strength, e.g., we assume the standard deviation σp is sufficiently larger than σ p , ensuring that more attention is paid to ξ 2 rather than other tokens. One future direction is to generalize our analysis to study other abilities of Transformers, such as in-context learning, prompt-tuning and time series forecasting. In this section, we follow a similar setting as the experiments in Section 6, and add more experiments.All the experiments in this paper can be performed within hours.Experiments setting: We focus on tracking the dynamics of QKV under benign and harmful overfitting regime, and the key parameters are as follows:• M = 4 • d = 2048 • d h = 1024 • d v = 256 • σ p = 0.05 • σp = 1Specifically, we set n = 16, ∥µ∥ 2 = 25 as benign overfitting setting, and set n = 10, ∥µ∥ 2 = 15 as harmful overfitting setting. Experiments results: Figure 3 shows the training dynamics under benign overfitting setting, and Figure 4 shows the training dynamics under harmful overfitting setting. In Figure 3 ,ξ i W(t) Q W(t) K µ+ ξ i W(t) Q W(t) K ξ2x ⊤ l W Q W ⊤ K µ + grow faster than x ⊤ l W Q W ⊤ K ξ 2, and more and more attention are paid on signal µ + . Meanwhile,µ + W V w O grows faster than ξ 2 W V w O . In Figure 4, x ⊤ l W Q W ⊤ K ξ 2 grow faster than x ⊤ l W Q W ⊤ K µ +, and more and more attention are paid on noise ξ 2 . Meanwhile, ξ 2 W V w O grows faster than µ + W V w O . In other words, the ViT prefers to learn the signals rather than memorize the noises under benign overfitting setting, while it prefers to memorize the noises rather than learn the signals under harmful overfitting setting.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: we plot the 2-sigma error bar for the training dynamics in Appendix A Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). 
 
 Appendix: In this section, we introduce some notations for this paper, and give expressions for the exact gradient of loss function L S (θ) with respect to W Q , W K and W V . the i-th row of attention for the n-th sample, i.e., φ(t) n,i := φ(x ⊤ n,i W (t) Q W (t)⊤ K X ⊤ n ) S+, S-the training samples with +1 labels and -1 labels, i.e. ,S+EQUATION-:= µ ⊤ -W (t) V wO, V (t) n,i := ξ ⊤ n,i W (t) V wO α (t) ±,± , α (t) n,±,ilinear combinations coefficients for the dynamics of q (t) + and q (t)-, i.e., q (t+1) ± -q (t) ± = α (t) ±,± k (t) ± + n∈S ± M i=2 α (t) n,±,i k (t) n,i α (t) n,i,± , α (t) n,i,n ′ ,i ′ linear combinations coefficients for the dynamics of q (t) n,i , i.e., q (t+1) n,i -q (t) n,i = α (t) n,i,+ k (t) + + α (t) n,i,-k (t) -+ N n ′ =1 M i ′ =2 α (t) n,i,n ′ ,i ′ k (t) n ′ ,i ′ β (t) ±,± , β (t) n,±,ilinear combinations coefficients for the dynamics of k(t) + and k (t) -, i.e., k (t+1) ± -k (t) ± = β (t) ±,± q (t) ± + n∈S ± M i=2 β (t) n,±,i q (t) n,i β (t) n,i,± , β (t) n,i,n ′ ,i ′ linear combinations coefficients for the dynamics of q (t) n,i , i.e., k (t+1) n,i -k (t) n,i = β (t) n,i,+ q (t) + + β (t) n,i,-q (t) -+ N n ′ =1 M i ′ =2 β (t) n,i,n ′ ,i ′ q (t) n ′ ,i ′ sof tmax(⟨q (t) ± , k (t) ± ⟩)a general references to exp(⟨qEQUATION+ ⟩) exp(⟨q(t) + ,k (t) + ⟩)+ M k=2exp(⟨q(t) + ,k (t) n,k ⟩)for n ∈ S+, and exp(⟨qEQUATION-⟩) exp(⟨q(t) -,k (t) -⟩)+ M k=2 exp(⟨q (t) -,k (t) n,k ⟩)for n ∈ Ssof tmax(⟨qEQUATION± ⟩) a general references to exp(⟨q(t) n,i ,k (t) + ⟩) exp(⟨q (t) n,i ,k (t) + ⟩)+ M k=2 exp(⟨q (t) n,i ,k (t) n,k ⟩) for n ∈ S+, i ∈ [M ]\{1},and exp(⟨qEQUATIONn,j ⟩) a general references to exp(⟨qEQUATIONn,j ⟩) exp(⟨q(t) + ,k (t) + ⟩)+ M k=2exp(⟨q(t) + ,k (t) n,k ⟩) for n ∈ S+, i ∈ [M ]\{1},and exp(⟨q(t) -,k (t) n,j ⟩) exp(⟨q (t) -,k (t) -⟩)+ M k=2 exp(⟨q (t) -,k (t) n,k ⟩) for n ∈ S-, i ∈ [M ]\{1} sof tmax(⟨q (t) n,i , k (t) n,j ⟩) a general references to exp(⟨q (t) n,i ,k (t) n,j ⟩) exp(⟨q (t) n,i ,k (t) + ⟩)+ M k=2 exp(⟨q (t) n,i ,k (t) n,k ⟩) for n ∈ S+, i, j ∈ [M ]\{1},and exp(⟨qEQUATIONn,i,±,j := ⟨q(t) n,i , k (t) ± ⟩ -⟨q (t) n,i , k (t) n,j ⟩ Ψ (t) ± , Ψ (t) n,±,j , Ψ (t) n,i,± , Ψ (t) n,i,j Ψ (t) ± := ⟨q (t) ± , k (t) n,2 ⟩ -⟨q (t) ± , k (t) ± ⟩, Ψ (t) n,±,j := ⟨q (t) ± , k (t) n,2 ⟩ -⟨q (t) ± , k (t) n,j ⟩, Ψ (t) n,i,± := ⟨q (t) n,i , k (t) n,2 ⟩ -⟨q (t) n,i , k (t) ± ⟩, Ψ (t) n,i,j := ⟨q (t) n,i , k (t) n,2 ⟩ -⟨q (t) n,i , k (t) n,j ⟩Gradient of Softmax. Before computing the gradient of QKV, we solve for the gradient of Softmax function. Suppose there is an input vector a = (a 1 , a 2 , . . . , a m ), then the softmax function can be defined as follows:sof tmax(a i ) = exp(a i ) m j=1 exp(a j )Then we calculate the gradient of sof tmax(a i ) with respect to a i and a j for i, jEQUATION(3) and (4) show that the gradient of a Softmax function can be represented as a Jacobi matrix where the elements on the diagonal are sof tmax(a i ) • 1sof tmax(a i ) and the elements on the off-diagonal are sof tmax(a i ) • sof tmax(a j ). With these properties, the gradient of our attention vector φ n,i (i∈ [M ], n ∈ [N ]) can be expressed as followsEQUATIONLemma B.1. the gradients of loss function L S (θ) with respect to W Q , W K and W V are given by∇ W Q L S (θ) = 1 N M n∈S+ ℓ ′ n (θ)(µ + w ⊤ O W ⊤ V X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 ) + M i=2 ξ n,i w ⊤ O W ⊤ V X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i ))X n W K - 1 N M n∈S- ℓ ′ n (θ)(µ -w ⊤ O W ⊤ V X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 ) + M i=2 ξ n,i w ⊤ O W ⊤ V X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i ))X n W K , ∇ W K L S (θ) = 1 N M n∈S+ ℓ ′ n (θ)(X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 )X n W V w O µ ⊤ + + M i=2 X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i )X n W V w O ξ ⊤ n,i )W Q - 1 N M n∈S- ℓ ′ n (θ)(X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 )X n W V w O µ ⊤ - + M i=2 X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i )X n W V w O ξ ⊤ n,i )W Q , ∇ W V L S (θ) = 1 N M N n=1 y n ℓ ′ n (θ)[w O M l=1 φ(x n,l W Q W ⊤ K X ⊤ n )X n ] ⊤ Proof of Lemma B.1. Considering that in the vector x ⊤ n,i W Q W ⊤ K X ⊤ n , the j-th element of x ⊤ n,i , i.e. (x n,i ) [j], is only used to multiply W Q[j,:] , then we have∂(x ⊤ n,i W Q W ⊤ K X ⊤ n ) ∂W Q[j,:] = (x n,i ) [j] • (X n W K )And then we get∇ W Q[j,:] φ(x ⊤ n,i W Q W ⊤ K X ⊤ n )X n W V w O = (x n,i ) [j] ∂(φ n,i X n W V w O ) ∂(x ⊤ n,i W Q W ⊤ K X ⊤ n ) (X n W K ) Considering all j ∈ [d], we get ∇ W Q φ(x ⊤ n,i W Q W ⊤ K X ⊤ n )X n W V w O = x n,i ∂(φ n,i X n W V w O ) ∂(x ⊤ n,i W Q W ⊤ K X ⊤ n ) X n W K (6) ∇ W Q L S (θ) = 1 N N n=1 y n ℓ ′ (y n f (X n , θ))∇ W Q f (X n , θ) = 1 N M N n=1 y n ℓ ′ n (θ) M i=1 ∇ W Q φ(x ⊤ n,i W Q W ⊤ K X ⊤ n )X n W V w O = 1 N M N n=1 y n ℓ ′ n (θ) M i=1 x n,i ∂(φ n,i X n W V w O ) ∂(x ⊤ n,i W Q W ⊤ K X ⊤ n ) X n W K = 1 N M N n=1 y n ℓ ′ n (θ) M i=1 x n,i (X n W V w O ) ⊤ ∂φ n,i ∂(x ⊤ n,i W Q W ⊤ K X ⊤ n ) X n W K = 1 N M N n=1 y n ℓ ′ n (θ) M i=1 x n,i w ⊤ O W ⊤ V X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i )X n W K = 1 N M n∈S+ ℓ ′ n (θ)(µ + w ⊤ O W ⊤ V X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 ) + M i=2 ξ n,i w ⊤ O W ⊤ V X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i ))X n W K - 1 N M n∈S- ℓ ′ n (θ)(µ -w ⊤ O W ⊤ V X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 ) + M i=2 ξ n,i w ⊤ O W ⊤ V X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i ))X n W K (7)where the third equality is by (6), the fourth equality is by chain rule, the fifth equality is by (5), For the last equality, we expand the equality by materializing all the x n,i (e.g., x n,1 = µ + f or n ∈ S + ).Using the similar method, we obtain the gradient of W K .∇ W K L S (θ) = 1 N N n=1 y n ℓ ′ (y n f (X n , θ))∇ W K f (X n , θ) = 1 N M N n=1 y n ℓ ′ n (θ) M i=1 ∇ W K φ(x ⊤ n,i W Q W ⊤ K X ⊤ n )X n W V w O = 1 N M N n=1 y n ℓ ′ n (θ) M i=1 X ⊤ n ∂(φ n,i X n W V w O ) ∂(x ⊤ n,i W Q W ⊤ K X ⊤ n ) ⊤ x ⊤ n,i W Q = 1 N M N n=1 y n ℓ ′ n (θ) M i=1 X ⊤ n ∂φ n,i ∂(x ⊤ n,i W Q W ⊤ K X ⊤ n ) (X n W V w O ) x ⊤ n,i W Q = 1 N M n∈S+ ℓ ′ n (θ)(X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 )X n W V w O µ ⊤ + + M i=2 X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i )X n W V w O ξ ⊤ n,i )W Q - 1 N M n∈S- ℓ ′ n (θ)(X ⊤ n (diag(φ n,1 ) -φ ⊤ n,1 φ n,1 )X n W V w O µ ⊤ - + M i=2 X ⊤ n (diag(φ n,i ) -φ ⊤ n,i φ n,i )X n W V w O ξ ⊤ n,i )W Q (8)The gradient of W V can be obtained using the chain rule as follows∇ W V L S (θ) = 1 N N n=1 y n ℓ ′ (y n f (X n , θ))∇ W V f (X n , θ) = 1 N M N n=1 y n ℓ ′ n (θ)[w O M l=1 φ(x n,l W Q W ⊤ K (X n ) ⊤ )X n ] ⊤ (9) B.3 Update Rules Definition B.1 (Scalarized V). Let W (t)V be the V matrix of the ViT at the t-th iteration of gradient descent. Then there exist coefficients γEQUATION-:= µ ⊤ -W (t) V w O and V (t) n,i := ξ ⊤ n,i W (t)V w O . We refer to it as scalarized V.Definition B.2 (Vectorized Q & K). Let W (t) Q and W (t)K be the QK matrices of the ViT at the t-th iteration of gradient descent. Then we define the vectorized Q and vectorized K as followsEQUATIONEQUATION-= µ ⊤ -W (t) K , k (t) n,i = ξ ⊤ n,i W (t) K for i ∈ [M ]\{1}, n ∈ [N ].). There exist coefficients αEQUATION-,-, α(t) n,-,i , α (t) n,i,+ , α (t) n,i,-, α (t) n,i,n ′ ,i ′ , β (t) +,+ , β (t) n,+,i , β (t) -,-, β (t) n,-,i , β (t) n,i,+ , β (t) n,i,-, β (t) n,i,n ′ ,i ′ such that ∆q (t) + := q (t+1) + -q (t) + = α (t) +,+ k (t) + + n∈S+ M i=2 α (t) n,+,i k (t) n,i , ∆q (t) -:= q (t+1) - -q (t) -= α (t) -,-k (t) -+ n∈S- M i=2 α (t) n,-,i k (t) n,i , ∆q (t) n,i := q (t+1) n,i -q (t) n,i = α (t) n,i,+ k (t) + + α (t) n,i,-k (t) -+ N n ′ =1 M i ′ =2 α (t) n,i,n ′ ,i ′ k (t) n ′ ,i ′ , ∆k (t) + := k (t+1) + -k (t) + = β (t) +,+ q (t) + + n∈S+ M i=2 β (t) n,+,i q (t) n,i , ∆k (t) -:= k (t+1) - -k (t) -= β (t) -,-q (t) -+ n∈S- M i=2 β (t) n,-,i q (t) n,i , ∆k (t) n,i := k (t+1) n,i -k (t) n,i = β (t) n,i,+ q (t) + + β (t) n,i,-q (t) -+ N n ′ =1 M i ′ =2 β (t) n,i,n ′ ,i ′ q (t) n ′ ,i ′ for i, i ′ ∈ [M ]\{1} and n, n ′ ∈ [N ].Remark. With the scalarized V in B.1, we can portray the learning process of W V on signals and noises by analyzing the dynamics of γ(t) V,+ , γ (t) V,-and ρ (t) V,n,i (or V (t) + , V (t) -and V (t)n,i ) . Also, as scalars, the effect of W V on the learning process of W Q and W K is more conveniently to describe. With the Vectorized Q & K in B.2, we can decompose x ⊤ W Q W K X ⊤ into the inner product of vectors q (a generalized reference to q + , q -and q n,i ) and k (a generalized reference to k + , k -and k n,i ), e.g., ⟨q+ , k + ⟩ = µ ⊤ + W Q W K µ + .Then the dynamics of x ⊤ W Q W K X ⊤ can be characterized by analyzing the dynamics of the inner products of q and k, and then further get the dynamics of attentions. The gradient decomposition in B.3 comes from ( 7) and ( 8). Note that (7) ends in X n W K and (8) ends in x ⊤ n,i W Q . This suggests that the dynamics of q (t)± and q(t)n,i can be decomposed into linear combinations of k n,i can be decomposed into linear combinations of q (t) ± and q (t) n,i . We calculate α (a generalized reference to α +,+ , α n,i + , α -,-, etc.) and β (a generalized reference to β +,+ , β n,+,i , β -,-, etc.) in detail in Appendix F.Lemma B.2 (Update Rule for V). The coefficients γ (t) V,+ , γ (t) V,-, ρ (t)V,n,i defined in Definition B.1 satisfy the following iterative equations:γ (t+1) V,+ = γ (t) V,+ - η∥µ∥ 2 2 N M n∈S+ ℓ ′(t)n exp(⟨q(t) + , k (t) + ⟩)exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨qEQUATIONV,-= γEQUATION-⟩) exp(⟨qEQUATIONn,k ⟩)+ M j=2 exp(⟨q (t) n,j , k (t) -⟩) exp(⟨q (t) n,j , k (t) -⟩) + M k=2 exp(⟨q (t) n,j , k (t) n,k ⟩) , ρ (t+1) V,n,i = ρ (t) V,n,i - η N M n ′ ∈S+ ℓ ′(t) n ′ M i ′ =2 (⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) + , k (t) n ′ ,i ′ ⟩)exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨q(t) + , k (t) n ′ ,k ⟩) + M j=2 ⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) n ′ ,j , k (t) n ′ ,i ′ ⟩) exp(⟨q (t) n ′ ,j , k (t) + ⟩) + M k=2 exp(⟨q (t) n ′ ,j , k (t) n ′ ,k ⟩) ) + η N M n ′ ∈S- ℓ ′(t) n ′ M i ′ =2 (⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) -, k (t) n ′ ,i ′ ⟩) exp(⟨q (t) -, k (t) -⟩) + M k=2 exp(⟨q (t) -, k (t) n ′ ,k ⟩) + M j=2 ⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) n ′ ,j , k (t) n ′ ,i ′ ⟩) exp(⟨q (t) n ′ ,j , k (t) -⟩) + M k=2 exp(⟨q (t) n ′ ,j , k (t) n ′ ,k ⟩) ) for i ∈ [M ]\{1}, n ∈ [N ].Proof of Lemma B.2. Base on (9), we havex ⊤ ∇ W V L S (θ)w O = x ⊤ 1 N M N n=1 y n ℓ ′ n (θ)[w O M l=1 φ(x n,l W Q W ⊤ K (X n ) ⊤ )X n ] ⊤ w O = 1 N M N n=1 y n ℓ ′ n (θ) M l=1 x ⊤ X ⊤ n φ(x n,l W Q W ⊤ K (X n ) ⊤ ) ⊤ ∥w O ∥ 2 2 = 1 N M n∈S+ ℓ ′ n (θ) M l=1 ⟨x, µ + ⟩ exp(x ⊤ n,l W Q W ⊤ K µ + ) exp(x ⊤ n,l W Q W ⊤ K µ + ) + M j=2 exp(x ⊤ n,l W Q W ⊤ K ξ n,j ) + M i=2 (⟨x, ξ n,i ⟩ exp(x ⊤ n,l W Q W ⊤ K ξ n,i ) exp(x ⊤ n,l W Q W ⊤ K µ + ) + M j=2 exp(x ⊤ n,l W Q W ⊤ K ξ n,j ) ) ∥w O ∥ 2 2 - 1 N M n∈S- ℓ ′ n (θ) M l=1 ⟨x, µ -⟩ exp(x ⊤ n,l W Q W ⊤ K µ -) exp(x ⊤ n,l W Q W ⊤ K µ -) + M j=2 exp(x ⊤ n,l W Q W ⊤ K ξ n,j ) + M i=2 (⟨x, ξ n,i ⟩ exp(x ⊤ n,l W Q W ⊤ K ξ n,i ) exp(x ⊤ n,l W Q W ⊤ K µ -) + M j=2 exp(x ⊤ n,l W Q W ⊤ K ξ n,j ) ) ∥w O ∥ 2 2 = 1 N M n∈S+ ℓ ′ n (θ) (⟨x, µ + ⟩ exp(µ ⊤ + W Q W ⊤ K µ + ) exp(µ ⊤ + W Q W ⊤ K µ + ) + M k=2 exp(µ ⊤ + W Q W ⊤ K ξ n,k ) + M j=2 ⟨x, µ + ⟩ exp(ξ ⊤ n,j W Q W ⊤ K µ + ) exp(ξ ⊤ n,j W Q W ⊤ K µ + ) + M k=2 exp(ξ ⊤ n,j W Q W ⊤ K ξ n,k ) ) + M i=2 (⟨x, ξ n,i ⟩ exp(µ + W Q W ⊤ K ξ n,i ) exp(µ ⊤ + W Q W ⊤ K µ + ) + M k=2 exp(µ ⊤ + W Q W ⊤ K ξ n,k ) + M j=2 ⟨x, ξ n,i ⟩ exp(ξ n,j W Q W ⊤ K ξ n,i ) exp(ξ ⊤ n,j W Q W ⊤ K µ + ) + M k=2 exp(ξ ⊤ n,j W Q W ⊤ K ξ n,k ) ) ∥w O ∥ 2 2 - 1 N M n∈S- ℓ ′ n (θ) (⟨x, µ -⟩ exp(µ ⊤ -W Q W ⊤ K µ -) exp(µ ⊤ -W Q W ⊤ K µ -) + M k=2 exp(µ ⊤ -W Q W ⊤ K ξ n,k ) + M j=2 ⟨x, µ -⟩ exp(ξ ⊤ n,j W Q W ⊤ K µ -) exp(ξ ⊤ n,j W Q W ⊤ K µ -) + M k=2 exp(ξ ⊤ n,j W Q W ⊤ K ξ n,k ) ) + M i=2 (⟨x, ξ n,i ⟩ exp(µ -W Q W ⊤ K ξ n,i ) exp(µ ⊤ -W Q W ⊤ K µ -) + M k=2 exp(µ ⊤ -W Q W ⊤ K ξ n,k ) + M j=2 ⟨x, ξ n,i ⟩ exp(ξ n,j W Q W ⊤ K ξ n,i ) exp(ξ ⊤ n,j W Q W ⊤ K µ -) + M k=2 exp(ξ ⊤ n,j W Q W ⊤ K ξ n,k ) ) ∥w O ∥ 2 2 (10)where the second equality we expand X n into vectors and make inner products with x, the third equality we materializing all the x n,l (e.g., x n,1 = µ + for n ∈ S + ). Note the orthogonality between µ and ξ n,i , we can remove many of the terms in this equation. Take x = µ + as an example, we haveµ ⊤ + ∇ W V L S (θ)w O = ∥µ∥ 2 2 N M n∈S+ ℓ ′ n (θ) exp(µ ⊤ + W Q W ⊤ K µ + ) exp(µ ⊤ + W Q W ⊤ K µ + ) + M k=2 exp(µ ⊤ + W Q W ⊤ K ξ n,k ) + M j=2 exp(ξ ⊤ n,j W Q W ⊤ K µ + ) exp(ξ ⊤ n,j W Q W ⊤ K µ + ) + M k=2 exp(ξ ⊤ n,j W Q W ⊤ K ξ n,k ) ∥w O ∥ 2 2 (11)Then we haveµ ⊤ + W (t+1) V w O -µ ⊤ + W (t) V w O = µ ⊤ + -η∇ W V L S (θ(t)) w O - η∥µ∥ 2 2 N M n∈S+ ℓ ′(t)n exp(⟨qEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨q(t) + , k (t) n,k ⟩) + M j=2exp(⟨q(t) n,j , k (t) + ⟩) exp(⟨q (t) n,j , k (t) + ⟩) + M k=2 exp(⟨q (t) n,j , k (t) n,k ⟩) ∥w O ∥ 2 2 (12)Dividing by ∥w O ∥ 2 2 we get γ (t+1)V,+ = γ (t) V,+ - η∥µ∥ 2 2 N M n∈S+ ℓ ′(t)n exp(⟨qEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨qEQUATIONn,k ⟩)EQUATIONThis proves the update rule for γ (t)V,+ , The proof for γ (t)V,+ and ρ (t)V,n,i is similar to it. Lemma B.3 (Update Rule for QK). The dynamics of x ⊤ W Q W K x can be characterized as followsEQUATIONEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONn,j ⟩ -⟨qEQUATIONn,i , kn,j ⟩ -⟨q(t) n,i , k (t) n,j ⟩ = α (t) n,i,+ ⟨k (t) + , k (t) n,j ⟩ + α (t) n,i,-⟨k (t) -, k (t) n,j ⟩ + N n ′ =1 M l=2 α (t) n,i,n ′ ,l ⟨k (t) n ′ ,l , k (t) n,j ⟩ + β (t) n,j,+ ⟨q (t) + , q (t) n,i ⟩ + β (t) n,j,-⟨q (t) -, q (t) n,i ⟩ + N n ′ =1 M l=2 β (t) n,j,n ′ ,l ⟨q (t) n ′ ,l , q (t) n,i ⟩ + α (t) n,i,+ k (t) + + α (t) n,i,-k (t) -+ N n ′ =1 M l=2 α (t) n,i,n ′ ,l k (t) n ′ ,l • β (t) n,j,+ q (t)⊤ + + β (t) n,j,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,j,n ′ ,l q (t)⊤ n ′ ,l , for i, j ∈ [M ]\{1}, n ∈ [N ].Proof of Lemma B.3. Based on Definition B.3, we haveEQUATIONEQUATIONThen we getEQUATIONwhereEQUATIONK := W (t+1) K -W (t)K , the second equality is by ∆q(t) + = µ ⊤ + ∆W (t)Q and ∆k(t) + = µ ⊤ + ∆W (t)K , the third equality is by plugging ( 14) and ( 15). This proves the update rule for ⟨q(t) + , k (t) + ⟩, the proof for ⟨q (t) n,i , k (t) + ⟩, ⟨q (t) + , k (t) n,j ⟩, ⟨q (t) n,i , k (t)n,j ⟩ are exactly the same.Remark. In ( 16), note that the magnitude of ⟨kEQUATION+ ∥ 2 2 , and that the magnitude of αEQUATIONn,+,i will not be greater than that of αEQUATION+,+(we will prove it later). Also, since the learning rate η is sufficiently small, the last term of ( 16) will be very small. Then ( 16) can be expressed in the following form EQUATION+ ⟩, ⟨qEQUATIONn,j ⟩, ⟨qEQUATIONn,j ⟩ can be expressed in a similar way. Later we will rigorously explain the so-call {lower order term}.In this section, we will give some concentration inequalities that show some important properties of the data and the ViT parameters at random initialization. Lemma C.1 (Lemma B.1 in Cao et al. (2022) ). Suppose that δ > 0 and n ≥ 8 log(4/δ). Then with probability at least1 -δ, N 4 ≤ |{n ∈ [N ] : y n = 1}|, |{n ∈ [N ] : y n = -1}| ≤ 3N 4 .Lemma C.2 (Initialization of V). Suppose that δ > 0. Then with probability at least 1δ,|V (0) ± | ≤ d -1 4 h , |V (0) n,i | ≤ d -1 4 h for i ∈ [M ]\{1}, n ∈ [N ]. Proof of Lemma C.2. It is clear that µ ⊤ ± W (0)V w O is a random variable with mean zero and variance σ 2V ∥w O ∥ 2 2 ∥µ∥ 2 2 . Therefore, by Gaussian tail bound and the condition thatσ V ≤ O ∥w O ∥ -1 2 • min{∥µ∥ -1 2 , (σ p √ d) -1 } • d -1 4 h, with probability at least 1δ/N M ,|µ ⊤ ± W (0) V w O | ≤ σ V ∥w O ∥ 2 ∥µ∥ 2 log(2N M/δ) ≤ d -1 4 h Moreover, each element of vector w ⊤ O W (0) Vis a random variable with mean zero and variance σ 2V ∥w O ∥ 2 2 . Therefore, by Bernstein's inequality and the condition of σ V , with probability at least1 -δ/N M |ξ ⊤ n,i W (0) V w O | ≤ 2σ V σ p ∥w O ∥ 2 d log(2N M/δ) ≤ d -1 4 hApplying a union bound completes the proof. Lemma C.3 (Initialization of QK). Suppose that δ > 0. Then with probability at least 1δ,EQUATION+ , q (0)EQUATION+ , kEQUATIONn,i , qEQUATION± , kEQUATIONProof of Lemma C.3. It is clear that each element of vector q (0) + is a random variable with mean zero and variance ∥µ∥ 2 2 σ 2 h . By Bernstein's inequality, with probability at least 1δ/3N 2 M 2 , we have|∥q (0) + ∥ 2 2 -∥µ∥ 2 2 σ 2 h d h | = O(∥µ∥ 2 2 σ 2 h d h log(6N 2 M 2 /δ)).Therefore, as long as d h = Ω(log(6N 2 M 2 /δ)), we have∥µ∥ 2 2 σ 2 h d h 2 ≤ ∥q (0) + ∥ 2 2 ≤ 3∥µ∥ 2 2 σ 2 h d h 2 ,Similarly, we haveEQUATION+ , q-⟩ has mean zero. By Bernstein's inequality, with probability at least 1δ/3N 2 M 2 , we have|⟨q (0) + , q (0) -⟩| ≤ 2∥µ∥ 2 2 σ 2 h • d h log(6N 2 M 2 /δ).We can prove the rest of this lemma in a similar way. Lemma C.4 (Lemma B.2 in Cao et al. ( 2022)). Suppose that δ > 0 and d = Ω(log(4N M/δ)). Then with probability at least 1δσ2 p d/2 ≤ ∥ξ n,2 ∥ 2 2 ≤ 3σ 2 p d/2, σ 2 p d/2 ≤ ∥ξ n,i ∥ 2 2 ≤ 3σ 2 p d/2, |⟨ξ n,i , ξ n ′ ,i ′ ⟩| ≤ 2σ 2 p • d log(4N 2 M 2 /δ) for i, i ′ ∈ [M ]\{1}, n, n ′ ∈ [N ], i ̸ = i ′ or n ̸ = n ′ .In this section, we consider the benign overfitting regime under the condition that N • SNR 2 = Ω(1). We analyze the dynamics of V ± , V n,i , the inner product of q ± , q n,i and k ± , k n,i during gradient descent training, and further give the upper bound for population loss. The proofs in this section are based on the results in Section C, which hold with high probability.In Stage I, V (t) ± , V (t) n,i begin to pull apart until |V (t) ± | is sufficiently larger than |V (t)n,i |. At the same time, the inner products of q and k maintain their magnitude.Lemma D.1 (Gradient of Loss). As long as max{|V(t) + |, |V (t) -|, |V (t) n,i |} = o(1), we have -ℓ ′ (y n f (X n , θ(t))) remains 1/2 ± o(1).Proof of Lemma D.1. Note that ℓ(z) = log(1 + exp(-z)) and -ℓ ′ = exp(-z)/(1 + exp(-z)), without loss of generality, we assume y n = 1, we haveEQUATIONn,i |}.Then we have-ℓ ′ (f (X n , θ(t))) ≥ 1 1 + exp(0 + o(1)) ≥ 1 2 + o(1) ≥ 1 2 -o(1), -ℓ ′ (f (X n , θ(t))) ≤ exp(0 + o(1)) 1 + exp(0 + o(1)) ≤ 1 + o(1) 1 + 1 + o(1) ≤ 1 2 + o(1).Lemma D.2 (Bound of Attention). As long as |⟨q(t) ± , k (t) ± ⟩|, |⟨q (t) n,i , k (t) ± ⟩|, |⟨q (t) ± , k (t) n,j ⟩|, |⟨q (t) n,i , k (t) n,j ⟩| = o(1), we have 1 M -o(1) ≤ sof tmax(⟨q (t) ± , k (t) ± ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) ± ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) ± , k (t) n,j ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) n,j ⟩) ≤ 1 M + o(1).Proof of Lemma D.2. It is clear that exp(o(1)) = 1 + o(1). Therefore, as long as |⟨qEQUATION± ⟩| = o(1), we have1 M -o(1) = 1 1 + (M -1) + (M -1)o(1) = 1 1 + (M -1) exp(o(1)) = exp(-o(1)) exp(-o(1)) + (M -1) exp(o(1))≤ sof tmax(⟨q(t) ± , k (t) ± ⟩) ≤ exp(o(1)) exp(o(1)) + (M -1) exp(-o(1)) = exp(o(1)) exp(o(1)) + (M -1) = 1 + o(1) 1 + o(1) + (M -1) = 1 M + o(1)Similarly, we have1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) ± ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) ± , k (t) n,j ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) n,j ⟩) ≤ 1 M + o(1). Lemma D.3 (Upper bound of V). Let T 0 = O( 1 ηd 1 4 h ∥µ∥ 2 2 ∥w O ∥ 2 2). Then under the same conditions as Theorem 4.1, we haveEQUATIONEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨q(t) + , k (t) n,k ⟩) + M j=2 exp(⟨q (t) n,j , k (t) + ⟩) exp(⟨q (t) n,j , k (t) + ⟩) + M k=2 exp(⟨q (t) n,j , k (t) n,k ⟩) ≤ η∥µ∥ 2 2 N M • 3N 4 1 + (M -1) ≤ 3η∥µ∥ 2 2 4 ,where the second inequality is by Lemma C.1 and -ℓ′(t)n ≤ 1. Similarly, we have|γ (t+1) V,--γ (t) V,-| ≤ 3η∥µ∥ 2 2 4 .By Definition B.1, we have|V (t) + | = V (0) + + t-1 s=0 (γ (s+1) V,+ -γ (s) V,+ )∥w O ∥ 2 2 ≤ |V (0) + | + t-1 s=0 |γ (s+1) V,+ -γ (s) V,+ | • ∥w O ∥ 2 2 ≤ d -1 4 h + 3η∥µ∥ 2 2 4 • ∥w O ∥ 2 2 • O( 1 ηd 1 4 h ∥µ∥ 2 2 ∥w O ∥ 2 2 ) = O(d -1 4 h ),where the first inequality is by triangle inequality, the second inequality is by Lemma C.2. Similarly, we have|V (t) -| = O(d -1 4 h ). By Lemma B.2, we have |ρ (t+1) V,n,i -ρ (t) V,n,i | ≤ - η N M n ′ ∈S+ ℓ ′(t) n ′ M i=2 (⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) + , k (t) n ′ ,i ′ ⟩)exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨qEQUATION-⟩)EQUATIONn ′ ,k ⟩)EQUATIONwhere the second inequality is by Lemma C.4 and -ℓ′(t) n ≤ 1, the third inequality is by d = Ω ϵ -2 N 2 d h ≥ 4N log(4N 2 M 2 /δ), the last inequality is by N • SNR 2 = Ω(1).Then by Definition B.1, we have|V (t) n,i | = V (0) n,i + t-1 s=0 (ρ (s+1) V,n,i -ρ (s) V,n,i )∥w O ∥ 2 2 ≤ |V (0) n,i | + t-1 s=0 |ρ (s+1) V,n,i -ρ (s) V,n,i | • ∥w O ∥ 2 2 ≤ d -1 4 h + O(η∥µ∥ 2 2 ) • ∥w O ∥ 2 2 • O( 1 ηd 1 4 h ∥µ∥ 2 2 ∥w O ∥ 2 2 ) = O(d -1 4), where the first inequality is by triangle inequality, the second inequality is by Lemma C.2, which completes the proof.1 ηd 1 4 h ∥µ∥ 2 2 ∥w O ∥ 2 2). Then under the same conditions as Theorem 4.1, we haveEQUATIONn,i , qEQUATIONn,i , qEQUATION∓ ⟩|, |⟨kEQUATION± ⟩|, |⟨k(t) n,i , k (t) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , ∥q (t) ± ∥ 2 2 , ∥k (t) ± ∥ 2 2 = Θ(∥µ∥ 2 2 σ 2 h d h ), ∥q (t) n,i ∥ 2 2 , ∥k (t) n,i ∥ 2 2 = Θ(σ 2 p σ 2 h dd h ) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ] and t ∈ [0, T 0 ]. The proof for Lemma D.4 is in Section F.3. Note that σ 2 h ≤ min{∥µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h • log(6N 2 M 2 /δ) -3 2 , thus O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) = o(1).Lemma D.5 (V's Beginning of Learning Signals). Under the same conditions as Theorem 4.1, there existT 1 = 10M (3M +1)N ηd 1 4 h (N ∥µ∥ 2 2 -60M 2 C 2 p σ 2 p d)∥w O ∥ 2 2such that the first element of vector X n W (t)V w O dominate its other elements, that is,V (t) + ≥ 3M • |V (t) n,i | for all n ∈ S + , i ∈ [M ]\{1} and V (t) -≤ -3M • |V (t) n,i | for all n ∈ S -, i ∈ [M ]\{1}.Proof of Lemma D.5. Let C be a constant larger than 10M (3M + 1), then as long asN • SNR 2 = N ∥µ∥ 2 2 σ 2 p d ≥ 60CM 2 C 2 p C-10M (3M +1) , we have N ∥µ∥ 2 2 -60M 2 C 2 p σ 2 p d ≥ 10M (3M +1)N ∥µ∥ 2 2 C, and further getT 1 = 10M (3M + 1)N ηd 1 4 h (N ∥µ∥ 2 2 -60M 2 C 2 p σ 2 p d)∥w O ∥ 2 2 ≤ C ηd 1 4 h ∥µ∥ 2 2 ∥w O ∥ 2 2 = O 1 ηd 1 4 h ∥µ∥ 2 2 ∥w O ∥ 2 2 ,which satisfies the time condition in Lemma D.3 and Lemma D.4. Then by Lemma D.1 and Lemma D.2 we have-ℓ ′(t) n = 1 2 ± o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) ± , k (t) ± ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) ± ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) ± , k (t) n,j ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) n,j ⟩) ≤ 1 M + o(1) for i, j ∈ [M ]\{1}, n ∈ [N ] and t ∈ [0, T 1 ].Plugging them in the update rule for γ (t)V,+ showed in Lemma B.2 and we haveγ (t+1) V,+ -γ (t) V,+ = - η∥µ∥ 2 2 N M n∈S+ ℓ ′(t) n exp(⟨q (t) + , k (t) + ⟩)exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨qEQUATIONn,k ⟩)EQUATION+ ⟩) exp(⟨qEQUATIONThen by Definition B.1 and taking a summation, we haveEQUATIONSimilarly, we haveEQUATION)Similarly, by |ρ(t+1) V,n,i -ρ (t) V,n,i | ≤ 2ησ 2 p d Nin (17), we haveEQUATIONAccording to ( 19), ( 20) and ( 21), it is easy to verify that V(T1) + -3M • |V (T1) n,i | ≥ 0 and V (T1) - + 3M • |V (T1)n,i | ≤ 0, which completes the proof.In stage II, ⟨q + , k + ⟩, ⟨q n,i , k + ⟩ grows while ⟨q + , k n,j ⟩, ⟨q n,i , k n,j ⟩ decreases, resulting in attention focusing more and more on the signals and less on the noises. By the results of stage I, we have the following conditions at the beginning of stage IIV (T1) + ≥ 3M • |V (T1) n,i |, V (T1) - ≤ -3M • |V (T1) n,i |, |V (T1) + |, |V (T1) - |, |V (T1) n,i | = O(d -1 |⟨q (T1) ± , k (T1) ± ⟩|, |⟨q (T1) n,i , k (T1) ± ⟩|, |⟨q (T1) ± , k (T1) n,j ⟩|, |⟨q (T1) n,i , k (T1) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , |⟨q (T1) ± , q (T1) ∓ ⟩|, |⟨q (T1) n,i , q (T1) ± ⟩|, |⟨q (T1) n,i , q (T1) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , |⟨k (T1) ± , k (T1) ∓ ⟩|, |⟨k (T1) n,i , k (T1) ± ⟩|, |⟨k (T1) n,i , k (T1) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , ∥q (T1) ± ∥ 2 2 , ∥k (T1) ± ∥ 2 2 = Θ(∥µ∥ 2 2 σ 2 h d h ), ∥q (T1) n,i ∥ 2 2 , ∥k (T1) n,i ∥ 2 2 = Θ(σ 2 p σ 2 h dd h ) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ].Some of the proofs at this stage are based on the above conditions. Notations. To better characterize the gap between different inner products, we define the following notations:• denote Λ (t) n,+,j = ⟨q (t) + , k (t) + ⟩ -⟨q (t) + , k (t) n,j ⟩, n ∈ S + . • denote Λ (t) n,-,j = ⟨q (t) -, k (t) -⟩ -⟨q (t) -, k (t) n,j ⟩, n ∈ S -. • denote Λ (t) n,i,+,j = ⟨q (t) n,i , k (t) + ⟩ -⟨q (t) n,i , k (t) n,j ⟩, n ∈ S + . • denote Λ (t) n,i,-,j = ⟨q (t) n,i , k (t) -⟩ -⟨q (t) n,i , k (t) n,j ⟩, n ∈ S -. Lemma D.6 (Upper bound of V). Let T 0 = O 1 η∥µ∥ 2 2 ∥w O ∥ 2 2 log(6N 2 M 2 /δ) .Then under the same conditions as Theorem 4.1, we have|V (t) + |, |V (t) -|, |V (t) n,i | = o(1) for t ∈ [0, T 0 ].The proof of Lemma D.6 is similar to that of Lemma D.3, except that the time T 0 is changed. Let T 2 = Θ 1 η∥µ∥ 2 2 ∥w O ∥ 2 2 log(6N 2 M 2 /δ) ,-o(1) ≤ -ℓ ′(t) n ≤ 1 2 + o(1) for n ∈ [N ], t ∈ [T 1 , T 2 ],which can simplify the calculations of α and β defined in Definition B.3 by replacing -ℓ′(t)n by their bounds. Next we prove the following four propositions B(t), C(t), D(t), E(t) by induction on t for t ∈ [T 1 , T 2 ]:EQUATION+ , qEQUATION± , qEQUATIONn,i , qEQUATION-⟩|, |⟨kEQUATIONn,j ⟩ ≤ ⟨qEQUATIONn,j ⟩ ≤ ⟨q(t) n,i , k (t) n,j ⟩ Λ (t+1) n,±,j ≥ log exp(Λ (T1) n,±,j ) + η 2 C 8 ∥µ∥ 4 2 ∥w O ∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ) 2 • (t -T 1 )(t -T 1 + 1) Λ (t+1) n,i,±,j ≥ log exp(Λ (T1) n,i,±,j ) + η 2 C 8 σ 2 p d∥µ∥ 2 2 ∥w O ∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ) 2 • (t -T 1 )(t -T 1 + 1) for i, j ∈ [M ]\{1}, n ∈ [N ].• E(t) :EQUATION± ⟩|, |⟨qEQUATIONn,j ⟩|, |⟨qEQUATION± ⟩|, |⟨qEQUATIONn,j ⟩| ≤ log(dEQUATION∓ ⟩|, |⟨q(t) n,i , k (t) n,j ⟩| = o(1) for i, j ∈ [M ]\{1}, n, n ∈ [N ], n ̸ = n.By the results of Stage I, we know that B(T 1 ), C(T 1 ), E(T 1 ) are true. To prove that B(t), C(t), D(t) and E(t) are true in stage 2, we will prove the following claims holds for t ∈ [T 1 , T 2 ]:Claim 1. D(T 1 ), . . . , D(t -1) =⇒ B(t + 1) Claim 2. B(T 1 ), . . . , B(t), C(T 1 ), . . . , C(t), D(T 1 ), . . . , D(t -1) =⇒ D(t) Claim 3. B(T 1 ), . . . , B(t), D(T 1 ), . . . , D(t -1), E(T 1 ), . . . , E(t) =⇒ C(t + 1) Claim 4. B(T 1 ), . . . , B(t), C(T 1 ), . . . , C(t), D(T 1 ), . . . , D(t -1) =⇒ E(t + 1) D.2.1 Proof of Claim 1By the results of Stage I, we have|⟨q (T1) ± , k (T1) ± ⟩|, |⟨q (T1) ± , k (T1) n,j ⟩|, |⟨q (T1) n,i , k (T1) ± ⟩|, |⟨q (T1) n,i , k (T1) n,j ⟩| = o(1) Assume that D(T 1 ), . . . , D(t -1) (t ∈ [T 1 , T 2 ]) are true, then ⟨q (s) ± , k (s) ± ⟩, ⟨q (s) n,i , k (s)± ⟩ are monotonically non-decreasing and ⟨q(s) ± , k (s) n,j ⟩, ⟨q (s) n,i , k (s) n,j ⟩ are monotonically non-increasing for s ∈ [T 1 , t -1], so we have ⟨q (s) ± , k (s) ± ⟩, ⟨q (s) n,i , k (s) ± ⟩ ≥ -o(1), ⟨q (s) ± , k (s) n,j ⟩, ⟨q (s) n,i , k (s) n,j ⟩ ≤ o(1), for s ∈ [T 1 , t].Further we have the lower bounds for the attention on signal µ ± as follows for s ∈ [T 1 , t]: sof tmax(⟨qEQUATIONwhere the second equality is by exp(o(1)) = 1 + o(1). Similarly, we have sof tmax(⟨q(s) n,i , k (s) ± ⟩) ≥ 1 M -o(1).Plugging them in the update rule for γ (s)V,+ showed in Lemma B.2 and we haveEQUATION+ ⟩)exp(⟨q(s) + , k (s) + ⟩) + M k=2exp(⟨qEQUATIONn,k ⟩)EQUATIONEQUATIONfor s ∈ [T 1 , t].Then by Definition B.1 and taking a summation, we haveEQUATIONwhere the last inequality is by V (T1) +≥ 0 and M = Θ(1). Similarly, we haveV (t+1) - ≤ -ηC 3 ∥µ∥ 2 2 ∥w O ∥ 2 2 (t -T 1 + 1).By |ρ 17) and taking a summation, we have(t+1) V,n,i -ρ (t) V,n,i | ≤ 2η σ2 p d N in (EQUATION)Combining ( 24) and ( 25) we haveEQUATIONwhere the last inequality is byV (T1) + ≥ 3M • |V (T1) n,i | and requires N • SNR 2 ≥ 60M 2 C 2 p . The proof for V (t+1) - ≤ -3M • |V (t+1) n,i| is the same.Next, we prove the upper bound for V ± and V n,i . Based on the upper bound of attention(<1) and-ℓ ′ n ≤ 1, we have γ (s+1) V,+ ≤ γ (s) V,+ - η N M n∈S+ ℓ ′ n (θ(s))(∥µ∥ 2 2 + M j=2 ∥µ∥ 2 2 ) ≤ γ (s) V,+ + 3η∥µ∥ 2 2 4 ≤ γ (s) V,+ + ηC 4 ∥µ∥ 2 2 (27)Then we can get thatEQUATIONwhere the first inequality is by the monotonicity of γ V,+ and the definition of V + , the last inequality is by the result of stage 1 whereV (T1) + = O(d -1). Similarly, we haveEQUATIONwhich completes the proof for the upper bound of V ± .Expanding (25) yieldsEQUATIONwhere the last inequality is by the result of phase 1 where |V (T1)n,i | = O(d -1 4 h) and the condition that N • SNR 2 > Ω(1).By the results of F.5, we have the dynamic of ⟨q, k⟩ as followsEQUATIONEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONEQUATIONEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONfor s ∈ [T 1 , t]. The seven equations above show that ⟨qEQUATION± ⟩, ⟨qEQUATION± ⟩ are monotonically increasing and ⟨q(s) ± , k (s) n,j ⟩, ⟨q (s) n,i , k (s)n,j ⟩ are monotonically decreasing. Next, we provide the logarithmic increasing lower bounds of Λ (s+1) n,±,j and Λ (s+1) n,i,±,j . By ( 31) and ( 33), we haveEQUATIONwhere the last inequality is byσ 2 h ≥ min{∥µ∥ -2 2 , (σ 2 p d) -1 }d -1 2 h (log(6N 2 M 2 /δ)) -2 .Multiply both sides simultaneously by exp(ΛEQUATION)Taking a summation from T 1 to t and getEQUATION)By the property that Λ (t) n,+,j is monotonically increasing, we haveEQUATIONByEQUATIONSimilarly, we haveEQUATIONBy ( 35) and ( 37), we haveEQUATIONn,j ⟩ -⟨qEQUATIONThen using the similar method as for Λ (t) n,±,j , we getEQUATIONwhich complete the proof. The proof for Claim 3 is in Section F.8By the results of F.6, we haveEQUATION+ ⟩ = o(1) and the monotonicity of ⟨qEQUATIONwhere the last inequality is by plugging ( 46). Taking a summation we have⟨q (t+1) + ,k (t+1) + ⟩ ⟨q (T 1 ) + ,k (T 1 ) + ⟩ exp(x)dx ≤ t s=T1exp(⟨qEQUATION)where the first inequality is due to ⟨qEQUATION+ ⟩ is monotone increasing, the last inequality is byEQUATIONEQUATION+ ⟩), we haveEQUATIONBy the results of F.6, we also haveEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONn,j ⟩ ≥ -EQUATIONn,j ⟩). ( 52)EQUATIONEQUATIONThen using the similar method as for ⟨q(t+1) + , k (t+1) + ⟩, we get ⟨q (t+1) - , k (t+1) - ⟩ ≤ log d 1 2 h , ⟨q (t+1) ± , k (t+1) n,j ⟩ ≥ -log d 1 2 h , ⟨q (t+1) n,i , k (t+1) ± ⟩ ≤ log d 1 2 h , ⟨q (t+1) n,i , k (t+1) n,j ⟩ ≥ -log d 1 2h .Next we provide the upper bound for |⟨qEQUATIONEQUATIONn ′ ,j ⟩|. By the results of F.7, we haveEQUATIONEQUATION) for i ∈ [M ]\{1}, n ∈ S ± . t s=T1 |β (s) n,+,i |, t s=T1 |β (s) n,-,i | = O SNR • N -1 2 d -1 4 h (57) for i ∈ [M ]\{1}, n ∈ S ± . t s=T1 |α (s) n,i,+ |, t s=T1 |α (s) n,i,-|, t s=T1 |α (s) n,i,n,j |, t s=T1 |β (s) n,j,n,i | = O d -1 4 h (58) for i, j ∈ [M ]\{1}, n ∈ S ± . t s=T1 |α (s) n,i,n ′ ,j |, t s=T1 |β (s) n,j,n ′ ,i | = O d -1 2 d -1 for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ], n ̸ = n ′ . Plugging these into the update rule of ⟨q (t) ± , k (t) ∓ ⟩, ⟨q (t) n,i , k (t)n,j ⟩ and assume that propositions C(T 1 ), . . . , C(t) hold, we haveEQUATIONEQUATIONEQUATION-⟩|EQUATIONwhere the first inequality is by triangle inequality, the second inequality is by ( 213), the last equality is by |⟨qEQUATIONn,j ⟩|EQUATIONn,j ⟩|EQUATIONwhere the first inequality is by triangle inequality, the second inequality is by (196) , the secondEQUATION2 , the last equality is by|⟨q (T1) n,i , k (T1) n,j ⟩| = o(1), d = Ω ϵ -2 N 2 d h and d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 .In Stage III, the outputs of ViT grow up and the loss derivatives are no longer at o(1). We will carefully compute the growth rate of V ± and V n,i while keeping monitoring the monotonicity of ⟨q, k⟩. By substitutingt = T 2 = Θ 1 η∥µ∥ 2 2 ∥w O ∥ 2 2 into propositions B(t), C(t), D(t), E(t)in Stage II, we have the following conditions at the beginning of stage IIIEQUATION± ⟩|, |⟨qEQUATION± ⟩|, |⟨q(T2) n,i , k (T2) n,j ⟩| ≤ log(d 1 2 h ) |⟨q (T2) ± , k (T2) ∓ ⟩|, |⟨q (T2) n,i , k (T2) n,j ⟩| = o(1) for i, j ∈ [M ]\{1}, n, n ∈ [N ], n ̸ = n. Let T 3 = Θ 1 ηϵ∥µ∥ 2 2 ∥w O ∥ 2 2, Next we prove the following four propositions F(t), G(t), H(t), I(t)by induction on t for t ∈ [T 2 , T 3 ]:EQUATION± , q(t) n,i ⟩|, |⟨q (t) n,i , q (t) n ′ ,j ⟩| = o(1), |⟨k (t) + , k (t) -⟩|, |⟨k (t) ± , k (t) n,i ⟩|, |⟨k (t) n,i , k (t) n ′ ,j ⟩| = o(1) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ], i ̸ = j or n ̸ = n ′ . • H(t) : ⟨q (t+1) ± , k (t+1) ± ⟩ ≥ ⟨q (t) ± , k (t) ± ⟩, ⟨q (t+1) n,i , k (t+1) ± ⟩ ≥ ⟨q (t) n,i , k (t) ± ⟩, ⟨q (t+1) ± , k (t+1) n,j ⟩ ≤ ⟨q (t) ± , k (t) n,j ⟩, ⟨q (t+1) n,i , k (t+1) n,j ⟩ ≤ ⟨q (t) n,i , k (t) n,j ⟩ for i, j ∈ [M ]\{1}, n ∈ [N ]. • I(t) : |⟨q (t) ± , k (t) ± ⟩|, |⟨q (t) ± , k (t) n,j ⟩|, |⟨q (t) n,i , k (t) ± ⟩|, |⟨q (t) n,i , k (t) n,j ⟩| ≤ log(ϵ -1 d 1 2 h ), |⟨q (t) ± , k (t) ∓ ⟩|, |⟨q (t) n,i , k (t) n,j ⟩| = o(1) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ], n ̸ = n.By the results of Stage II, we know that F(T 1 ), G(T 2 ), I(T 2 ) are true. To prove that F(t), G(t), H(t) and I(t) are true in stage 3, we will prove the following claims holds for t ∈ [T 2 , T 3 ]:Claim 5. H(T 2 ), . . . , H(t -1) =⇒ F(t + 1) Claim 6. F(t), G(t), H(T 2 ), . . . , H(t -1) =⇒ H(t) Claim 7. F(T 2 ), . . . , F(t), H(T 2 ), . . . , H(t -1), I(T 2 ), . . . , I(t) =⇒ G(t + 1) Claim 8. F(T 2 ), . . . , F(t), G(T 2 ), . . . , G(t), H(T 2 ), . . . , H(t -1) =⇒ I(t + 1) D.3.1 Proof of Claim 5The proofs forEQUATION± ⟩ are monotonically non-decreasing and maxEQUATIONΛ (s) n,i,±,j ≥ Λ (T2) n,i,±,j ≥ log exp(Λ (T1) n,i,±,j ) + Θ σ 2 p dd 1 2 h N ∥µ∥ 2 2 log(6N 2 M 2 /δ) 3 (63) for i, j ∈ [M ]\{1}, n ∈ [N ], s ∈ [T 2 , t]. We further get exp(⟨q (s) ± , k (s) n,j ⟩) exp(⟨q (s) ± , k (s) ± ⟩) + M j ′ =2exp(⟨q(s) ± , k (s) n,j ′ ⟩) ≤ exp(⟨q (s) ± , k (s) n,j ⟩) C exp(⟨q (s) ± , k (s) ± ⟩) = 1 C exp(Λ (s) n,±,j ) ≤ 1 C exp(Λ (T1) n,±,j ) + Θ d 1 2 h N log(6N 2 M 2 /δ) 3 ≤ 1 Θ d 1 2 h N log(6N 2 M 2 /δ) 3 = O N log(6N 2 M 2 /δ)For the first inequality, by ( 62) and the monotonicity of ⟨q (s) , k (s) ⟩ (⟨qEQUATION± ⟩ is increasing and ⟨q(s) ± , k (s) n,j ⟩ is decreasing), there exist a constant C such that C exp(⟨q (s) ± , k (s) ± ⟩) ≥ exp(⟨q (s) ± , k (s) ± ⟩) + M j ′ =2 exp(⟨q (s) ± , k (s) n,j ′ ⟩).The second inequality is by plugging (62). Similarly, we have exp(⟨q(s) n,i , k (s) n,j ⟩) exp(⟨q (s) n,i , k (s) ± ⟩) + M j ′ =2exp(⟨qEQUATIONPlugging ( 64) and ( 65) into the update rule of ρ V,n,i in Lemma B.2 and get|ρ (s+1) V,n,i -ρ (s) V,n,i | ≤ η N M |ℓ ′(s) n | • ∥ξ n,i ∥ 2 2 • O N log(6N 2 M 2 /δ) 3 d 1 2 h + O N ∥µ∥ 2 2 log(6N 2 M 2 /δ) 3 σ 2 p dd 1 2 h + η N M n ′ ̸ =n∨i̸ =i ′ |ℓ ′(t) n ′ | • ⟨ξ n,i , ξ n ′ ,i ′ ⟩ • O N log(6N 2 M 2 /δ) 3 d 1 2 h + O N ∥µ∥ 2 2 log(6N 2 M 2 /δ) σ 2 p dd 1 2 h ≤ 3ησ 2 p d 2N M • O N log(6N 2 M 2 /δ) 3 d 1 2 h + O N ∥µ∥ 2 2 log(6N 2 M 2 /δ) 3 σ 2 p dd 1 2 h + η N M N • M • 2σ 2 p d log(4N 2 M 2 /δ) √ d • O N log(6N 2 M 2 /δ) 3 d 1 2 h + O N ∥µ∥ 2 2 log(6N 2 M /δ) σ 2 p dd 1 2 h ≤ 2η N M • O N σ 2 p d log(6N 2 M 2 /δ) 3 d 1 2 h + O N ∥µ∥ 2 2 log(6N 2 M 2 /δ) 3 d 1 2 h = O ησ 2 p d log(6N 2 M 2 /δ) 3 d 1 2 h + η∥µ∥ 2 2 log(6N 2 M 2 /δ) 3 d 1 2 h (66)where the second inequality is by Lemma C.4 and |ℓ′(t) n | ≤ 1. For the last inequality, since d = Ω ϵ -2 N 2 d h , we have N • M • 2σ 2 p d log(4N 2 M 2 /δ) ≤ 1 2 σ2 p d. By Definition B.1 and taking a summation we haveEQUATIONwhere the first equality is by N • SNR 2 ≥ Ω(1), the second equality is by d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . Then we have a constant upper bound for the sum of V n,i as follows:i∈[M ]\{1} |V (s) n,i | = (M -1) • o(1) ≤ C 15 for n ∈ [N ], s ∈ [T 2 , t].Expanding ( 64) and ( 65) we have exp(⟨q(s) ± , k (s) n,j ⟩) exp(⟨q (s) ± , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATIONwhere the equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 .exp(⟨q(s) n,i , k (s) n,j ⟩) exp(⟨q (s) n,i , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATION)where the equality is byEQUATIONsof tmax(⟨qEQUATIONfor i ∈ [M ]\{1}, n ∈ [N ], s ∈ [T 2 , t].Next we provide the bounds for -ℓ′(s) n . Note that ℓ(z) = log(1+exp(-z)) and -ℓ ′ = exp(-z)/(1+exp(-z)), without loss of generality, we assume y n = 1, we haveEQUATIONwhere1 M M l=1 φ(x ⊤ n,l W (s) Q W (s)⊤ K (X n ) ⊤ )X n W (s)V w O can be bounded as follows:1 M M l=1 φ(x ⊤ n,l W (s) Q W (s)⊤ K (X n ) ⊤ )X n W (s) V w O = 1 M sof tmax(⟨q (s) ± , k (s) ± ⟩) + M l=2 sof tmax(⟨q (s) n,l , k (s) ± ⟩) • µ ⊤ + W (s) V w O + j∈[M ]\{1}sof tmax(⟨q(s) ± , k (s) n,j ⟩) + M l=2 sof tmax(⟨q (s) n,l , k (s) n,j ⟩) • ξ ⊤ n,j W (s) V w O = 1 M M • 1 -o(1) • V (s) + + M • o(1) • j∈[M ]\{1} V (s) n,i ≥ V (s) + 2 (73) for s ∈ [T 2 , t].The second equality is by plugging ( 68), ( 69), ( 70) and ( 71), the inequality is byEQUATIONEQUATIONPlugging ( 73) and ( 74) into (72) we haveEQUATIONwhere the first inequality is by plugging (74). For the last inequality, note thatV (T2) + ≥ 0 and V (s)+ is monotonically increasing, so there exist a constant C 16 such that1 1+exp(V (s) + ) ≥ C16 exp(V (s) + ). We also have the upper boundEQUATIONPlugging ( 70), ( 71) and ( 75) into the update rule of γ (t)V,+ and in Lemma B.2 and get γ (s+1)EQUATION+ ⟩)exp(⟨q(s) + , k (s) + ⟩) + M k=2exp(⟨qEQUATIONn,k ⟩)EQUATIONwhere the second inequality is by (75). Then by definition B.1, we getV (s+1) + -V (s) + = γ (s+1) V,+ -γ (s) V,+ ∥w O ∥ 2 2 ≥ ηC 17 ∥µ∥ 2 2 ∥w O ∥ 2 2 exp(V (s) + )Multiply both sides simultaneously by exp(V(s) + ) and get exp(V (s) + ) V (s+1) + -V (s) + ≥ ηC 17 ∥µ∥ 2 2 ∥w O ∥ 2Taking a summation from T 2 to t and getEQUATIONBy the property that V (s)+ is monotonically increasing, we haveEQUATIONByV (t+1) + V (T 2 ) + exp(x)dx = exp(V (t+1) + ) -exp(V (T2) +) we getEQUATIONSimilarly, we haveEQUATIONNext we provide upper bounds for V (t+1) + and V (t+1) -. By the update rule of γEQUATION+ ⟩)exp(⟨q(s) + , k (s) + ⟩) + M k=2exp(⟨qEQUATIONn,k ⟩)EQUATION+ /2) where the second inequality is by (76). Then by definition B.1, we getV (s+1) + -V (s) + = γ (s+1) V,+ -γ (s) V,+ ∥w O ∥ 2 2 ≤ 3η∥µ∥ 2 2 ∥w O ∥ 2 2 4 exp(V (s) + /2) (82)Further we haveEQUATIONFor the last inequality, byη ≤ O(min{µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h ), V (T2) + = Θ(1) and the monotonicity of V (s) + , we have exp( 3η∥µ∥ 2 2 ∥w O ∥ 2 2 8 exp(V (s) + /2) ) ≤ exp(o(1)) ≤ C 18 . Multiplying both sides by V (s+1) + /2 - V (s) + /2 simultaneously gives exp(V (s+1) + /2) V (s+1) + /2 -V (s) + /2 ≤ C 18 exp(V (s) + /2) V (s+1) + /2 -V (s) + /2 ≤ 3ηC 18 ∥µ∥ 2 2 ∥w O ∥ 2 2 8 (84)where the last inequality is by plugging (82). Taking a summation we haveEQUATIONByV (t+1) + /2 V (T 2 ) + /2 exp(x)dx = exp(V (t+1) + /2) -exp(V (T2) +/2) we haveV (t+1) + ≤ 2 log exp(V (T2) + /2) + O( 1 ϵ ) = 2 log O( 1 ϵ )Similarly, we haveV (t+1) - ≥ -2 log O( 1 ϵ ) D.3.2 Proof of Claim 6By H(T 2 ), . . . , H(t -1), we have sof tmax(⟨q(t) ± , k (t) ± ⟩), sof tmax(⟨q (t) n,i , k (t) ± ⟩) = 1 -o(1) and sof tmax(⟨q (t) ± , k (t) n,j ⟩), sof tmax(⟨q (t) n,i , k (t)n,j ⟩) = o(1), which have been proved in D.3.1. By the results of F.4, we have the signs of α and β as follows:α (t) +,+ , α (t) -,-, β (t) +,+ , β (t) -,-, α (t) n,i,+ , α (t) n,i,-, β (t) n,+,i , β (t) n,-,i ≥ 0, α (t) n,+,i , α (t) n,-,i , α (t) n,i,n,j , β (t) n,i,+ , β (t) n,i,-, β (t) n,j,n,i ≤ 0.Then combined with G(T ) and we have the dynamics of ⟨q, k⟩ as follows:⟨q (t+1) + , k (t+1) + ⟩ -⟨q (t) + , k (t) + ⟩ = α (t) +,+ ∥k (t) + ∥ 2 2 + n∈S+ M i=2 α (t) n,+,i ⟨k (t) + , k (t) n,i ⟩ + β (t) +,+ ∥q (t) + ∥ 2 2 + n∈S+ M i=2 β (t) n,+,i ⟨q (t) + , q (t) n,i ⟩ + α (t) +,+ k (t) + + n∈S+ M i=2 α (t) n,+,i k (t) n,i • β (t) +,+ q (t)⊤ + + n∈S+ M i=2 β (t) n,+,i q (t)⊤ n,i = α (t) +,+ ∥k (t) + ∥ 2 2 + β (t) +,+ ∥q (t) + ∥ 2 2 + {lower order term} ≥ 0 (86) Similarly, we have ⟨q (t+1) - , k (t+1) - ⟩ -⟨q (t) -, k (t) -⟩ ≥ 0. (87) ⟨q (t+1) n,i , k (t+1) + ⟩ -⟨q (t) n,i , k (t) + ⟩ = α (t) n,i,+ ∥k (t) + ∥ 2 2 + α (t) n,i,-⟨k (t) + , k (t) -⟩ + N n ′ =1 M l=2 α (t) n,i,n ′ ,l ⟨k (t) + , k (t) n ′ ,l ⟩ + β (t) +,+ ⟨q (t) + , q (t) n,i ⟩ + n ′ ∈S+ M l=2 β (t) n ′ ,+,l ⟨q (t) n,i , q (t) n ′ ,l ⟩ + α (t) n,i,+ k (t) + + α (t) n,i,-k (t) -+ N n ′ =1 M l=2 α (t) n,i,n ′ ,l k (t) n ′ ,l • β (t) +,+ q (t)⊤ + + n ′ ∈S+ M l=2 β (t) n ′ ,+,l q (t)⊤ n ′ ,l = α (t) n,i,+ ∥k (t) + ∥ 2 2 + β (t) n,+,i ∥q (t) n,i ∥ 2 2 + {lower order term} ≥ 0. (88)Similarly, we haveEQUATIONEQUATIONn,j ⟩ -⟨q(t) + , k (t) n,j ⟩ = α (t) +,+ ⟨k (t) + , k (t) n,j ⟩ + n ′ ∈S+ M l=2 α (t) n ′ ,+,l ⟨k (t) n,j , k (t) n ′ ,l ⟩ + β (t) n,j,+ ∥q (t) + ∥ 2 2 + β (t) n,j,-⟨q (t) + , q (t) -⟩ + N n ′ =1 M l=2 β (t) n,j,n ′ ,l ⟨q (t) + , q (t) n ′ ,l ⟩ + α (t) +,+ k (t) + + n ′ ∈S+ M l=2 α (t) n ′ ,+,l k (t) n ′ ,l • β (t) n,j,+ q (t)⊤ + + β (t) n,j,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,j,n ′ ,l q (t)⊤ n ′ ,l = α (t) n,+,j ∥k (t) n,j ∥ 2 2 + β (t) n,j,+ ∥q (t) + ∥ 2 2 + {lower order term} ≤ 0 (90)Similarly, we haveEQUATIONn,j ⟩ -⟨qEQUATIONwhich completes the proof. The proof for Claim 7 is in Section F.11D.3.3 Proof of Claim 8By the results of F.9, we haveEQUATIONFurther we have exp(⟨q 1) and the monotonicity of ⟨q(t+1) + , k (t+1) + ⟩) ≤ exp ⟨q (t) + , k (t) + ⟩ + ηC 10 ∥µ∥ 4 2 σ 2 h d h log O( 1 ϵ ) exp(⟨q (t) + , k (t) + ⟩) = exp ⟨q (t) + , k (t) + ⟩ • exp ηC 10 ∥µ∥ 4 2 σ 2 h d h log O( 1 ϵ ) exp(⟨q (t) + , k (t) + ⟩) ≤ C 11 exp ⟨q (t) + , k (t) + ⟩ . (94) 52 For the last inequality, by η ≤ O(min{µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h ), σ 2 h ≤ min{∥µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h • log(6N 2 M 2 /δ) -3 2 , ⟨q (T1) + , k (T1) + ⟩ = o(EQUATIONwhere the last inequality is by plugging (93). Taking a summation we have⟨q (t+1) + ,k (t+1) + ⟩ ⟨q (T 2 ) +,k(T 2 ) + ⟩ exp(x)dx ≤ t s=T2exp(⟨q(s+1) + , k (s+1) + ⟩) ⟨q (s+1) + , k (s+1) + ⟩ -⟨q (s) + , k (s) + ⟩ ≤ t s=T2 ηC 12 ∥µ∥ 4 2 σ 2 h d h log O( 1 ϵ ) ≤ T 3 • ηC 12 ∥µ∥ 4 2 σ 2 h d h log O( 1 ϵ ) = O d 1 2 h log O( 1 ϵ ) ϵ(log(6N 2 M 2 /δ)) 3 2 (96)where the first inequality is due to ⟨q(s) + , k (s)+ ⟩ is monotone increasing, the last equality is byT 3 = Θ(η -1 ϵ -1 ∥µ∥ -2 2 ∥w O ∥ -2 2 ), ∥w O ∥ 2 2 = Θ(1) and σ 2 h ≤ min{∥µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h • log(6N 2 M 2 /δ) -3 2 . By ⟨q (t+1) + ,k (t+1) + ⟩ ⟨q (T 2 ) +,k(T 2 ) + ⟩ exp(x)dx = exp(⟨q (t+1) + , k (t+1) + ⟩)-exp(⟨q (T2) + , k (T2) + ⟩), we have ⟨q (t+1) + , k (t+1) + ⟩ ≤ log exp(⟨q (T2) + , k (T2) + ⟩) + O d 1 2 h log O( 1 ϵ ) ϵ(log(6N 2 M 2 /δ)) 3 2 ≤ log(ϵ -1 d 1 2 h ), (97)where the last inequality is by ⟨q(T2) + , k (T2) + ⟩ ≤ log d 1 2h . By the results of F.9, we also haveEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONThen using the similar method as for ⟨q(t+1) + , k (t+1) + ⟩, we get ⟨q (t+1) - , k (t+1) - ⟩ ≤ log(ϵ -1 d 1 2 h ), ⟨q (t+1) ± , k (t+1) n,j ⟩ ≥ -log(ϵ -1 d 1 2 h ), ⟨q (t+1) n,i , k (t+1) ± ⟩ ≤ log(ϵ -1 d 1 2 h ), ⟨q (t+1) n,i , k (t+1) n,j ⟩ ≥ -log(ϵ -1 d 1 2 h ),Next we provide the upper bound for |⟨qEQUATIONn ′ ,j ⟩|. By the results of F.10, we haveEQUATIONEQUATIONwhere the first inequality is by triangle inequality, the second inequality is by ( 213), the last equality is by |⟨qEQUATION)where the first inequality is by triangle inequality, the second inequality is by (196) , the secondequality is by σ 2 h ≤ min{∥µ∥ -2 2 , (σ 2 p d) -1 } • d -1 2 h • log(6N 2 M 2 /δ) -32 , the last equality is by|⟨q (T2) n,i , k (T2) n,j ⟩| = o(1), d = Ω ϵ -2 N 2 d h and d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . Lemma D.7 (Convergence of Training Loss). There exist T = C19 ηϵ∥µ∥ 2 2 ∥w O ∥ 2 2 such that L S (θ(T )) ≤ ϵProof of Lemma D.7. Recall ( 68), ( 69), ( 70) and ( 68), we have sof tmax(⟨qEQUATIONsof tmax(⟨qEQUATIONsof tmax(⟨qEQUATIONsof tmax(⟨q(t) n,i , k (t) ± ⟩) = 1 -O N • SNR 2 • log(6N 2 M 2 /δ) 3 d 1 2 h (111) Substituting t = T = C19 ηϵ∥µ∥ 2 2 ∥w O ∥ 2 2into propositions F(t) and getEQUATIONEQUATION)For n ∈ S + , we bound f (X n , θ(t)) as followsf (X n , θ(t)) = 1 M M l=1 φ(x ⊤ n,l W Q W ⊤ K (X n ) ⊤ )X n W V w O 1 M • exp(⟨q (t) + , k (t) + ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)+ M i=2 exp(⟨q (t) n,i , k (t) + ⟩) exp(⟨q (t) n,i , k (t) + ⟩) + M j=2exp(⟨q(t) n,i , k (t) n,j ⟩) • V (T ) + + M i=2exp(⟨q(t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)EQUATIONwhere the first inequality is by plugging ( 108), ( 109), ( 110) and ( 111). For the second inequality, byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 , we have O N •SNR 2 • log(6N 2 M 2 /δ) 3 log C 20 ϵ d 1 2 h = o(1) = log(1 + o(1)) ≤ log(C 20 )as long as C 20 is sufficiently large. Then we haveℓ (t) n = log 1 + exp(-f (X n , θ(t))) ≤ exp(-f (X n , θ(t))) ≤ exp -log 1 ϵ ≤ ϵ. (115)Similarly, we have ℓ(t) n ≤ ϵ for n ∈ S -. Therefore, we have L S (θ(T )) = 1 N N n=1 ℓ (t) n ≤ ϵ.Consider a new data point (X, y) generated from the distribution defined in Definition 3.1. Without loss of generality, we suppose that the signal token is µ + and the label is 1, i.e. X = (µ + , ξ 2 , . . . , ξ M ), y = 1. We will first give the bounds of attention, then the bounds of the output of ViT, and finally the bound of the expectation of loss. Lemma D.8 (Bound of Attention). Under the same conditions as Theorem 4.1, with probability at least 1δ/2N 2 M , we have thatexp(µ ⊤ + W (T3) Q W (T3)⊤ K µ + ) exp(µ ⊤ + W (T3) Q W (T3)⊤ K µ + ) + M i=2 exp(µ ⊤ + W (T3) Q W (T3)⊤ K ξ i ) ≥ 1 2M .Proof of Lemma D.8. By the result of D.2 and D.3,µ ⊤ + W (T1) Q W (T1)⊤ K µ + = o(1),and µ ⊤ + W (t) Q W (t)⊤ K µ + is monotonically non-decreasing for t ∈ [T 1 , T 3 ], we have µ ⊤ + W (T3) Q W (T3)⊤ K µ + ≥ -o(1).By proposition G(t) in D.3, we have ∥µ ⊤ + W (T3) Q ∥ 2 2 = Θ ∥µ∥ 2 2 σ 2 h d h .In order to give bounds forEQUATIONK . According to the properties of F-norm, we have∥W (T3) K -W (0) K ∥ F ≤ ∥W (T1) K -W (0) K ∥ F + ∥W (T2) K -W (T1) K ∥ F + ∥W (T3) K -W (T2) K ∥ F (116)Next, we will provide the bounds of ∥WEQUATIONWe bound |ℓ′(t) n |, ∥X n ∥ F , ∥(diag(φ (t) n,i ) -φ (t)⊤ n,i φ (t) n,i )∥ F , ∥X n W (t) V w O ∥ F , ∥µ ⊤ ± W (t) Q ∥ F and ∥ξ ⊤ n,i W (t) Q ∥ F respectively. • |ℓ ′(t) n | ≤ 1 • By Lemma C.4, ∥X n ∥ F ≤ ∥µ∥ 2 2 + (M -1) 3σ 2 p d 2 = O max{∥µ∥ 2 , σ p √ d}• Note that each element of vector φ n,i has an upper bound 1, and the number of tokens has a constant upper bound (M = Θ(1)), then we have ∥(diag(φ(t) n,i ) -φ (t)⊤ n,i φ (t) n,i )∥ F = O(1).• By Lemma D.3, we have|V (t) + |, |V (t) -|, |V (t) n,i | = O(d -1 4 h), so we have∥X n W V w O ∥ F = V (t) + 2 + M i=2 V (t) n,i 2 = M • d -1 4 h 2 = O d -1 4 h • By Lemma D.4, we have ∥µ ⊤ ± W (t) Q ∥ F = Θ ∥µ∥ 2 σ h d 1 2 h , ∥ξ ⊤ n,i W (t) Q ∥ F = Θ σ p σ h d 1 2 d 1 2 hPlugging them into (117) and get∥W (t+1) K -W (t) K ∥ F ≤ η N M • N M • O max{∥µ∥ 2 , σ p √ d} • O d -1 4 h • O max{∥µ∥ 2 , σ p √ d}σ h d 1 2 h = O η • max{∥µ∥ 2 2 , σ 2 p d} • σ h d 1 4 h (118)Taking a summation we haveEQUATIONwhere the last inequality is byN • SNR 2 = Ω(1). Bounding ∥W (T2) K -W (T1)K ∥ F : By F.7, we know that each element of matrix (diag(φ(t) n,1 ) - φ (t)⊤ n,1 φ (t) n,1 ) have upper bound O 1 1+ η 2 ∥µ∥ 4 2 ∥w O ∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ) 2 •(t-T1)(t-T1-1), and each element of matrix(diag(φ (t) n,i ) -φ (t)⊤ n,i φ (t) n,i ) have upper bound O 1 1+ η 2 σ 2 p d∥µ∥ 2 2 ∥w O ∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ) 2 •(t-T1)(t-T1-1). Considering that the number of tokens has a constant upper bound (M = Θ(1)), we haveEQUATIONBy B(t) in D.2, we have|V (t) ± |, |V (t) n,i | ≤ O(d -1 4 h ) + ηC 4 ∥µ∥ 2 2 ∥w O ∥ 2 2 (t -T 1 ) for t ∈ [T 1 , T 2 ]. We further have ∥X n W (t) V w O ∥ F = O d -1 4 h + η∥µ∥ 2 2 ∥w O ∥ 2 2 (t -T 1 ).Then we haveEQUATIONThe reason for the last equation is similar to (256). We also haveEQUATIONPlugging them into (117) and getEQUATIONTaking a summation we haveEQUATIONBounding ∥WEQUATION))exp(⟨q(t) ± , k (t) n,j ⟩) exp(⟨q (t) ± , k (t) ± ⟩) + M j ′ =2exp(⟨q(t) ± , k (t) n,j ′ ⟩) = O N log(6N 2 M 2 /δ) 3 d 1 2 h , exp(⟨q (t) n,i , k (t) n,j ⟩) exp(⟨q (t) n,i , k (t) + ⟩) + M j ′ =2exp(⟨qEQUATION∥(diag(φEQUATIONBy F(t) in D.3, we have|V (t) ± | ≤ 2 log O( 1 ϵ ) |V (t) n,i | = O(1) we further have ∥X n W (t) V w O ∥ F = O log O 1 ϵ .Plugging them into (117) and get∥W (t+1) K -W (t) K ∥ F ≤ η N M • N • O max{∥µ∥ 2 , σ p √ d} • O N log(6N 2 M 2 /δ) 3 d 1 2 h • O ∥µ∥ 2 σ h d 1 2 h + (M -1) • O N ∥µ∥ 2 2 log(6N 2 M 2 /δ) 3 σ 2 p dd 1 2 h • O σ p √ dσ h d 1 2 h • O log O( 1 ϵ ) = O η • max{∥µ∥ 2 2 , σ 2 p d} • N ∥µ∥ 2 log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) σ h σ p d 1 2 (128)Taking a summation we haveEQUATION)Combining ( 116), ( 119), ( 125) and ( 129) and getEQUATIONwhere the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . Bounding µ ⊤ + W (T3) Q W (T3)⊤ K ξ i : We decompose W (T3) K into W (0) K + W (T3) K -W (0) K, then we haveµ ⊤ + W (T3) Q W (T3)⊤ K ξ i = µ ⊤ + W (T3) Q W (0)⊤ K ξ i + µ ⊤ + W (T3) Q W (T3)⊤ K -W (0)⊤ K ξ i Now we bound µ ⊤ + W (T3) Q W (0)⊤ K ξ i and µ ⊤ + W (T3) Q W (T3)⊤ K -W (0)⊤ K ξ i respectively. Bounding µ ⊤ + W (T3) Q W (0)⊤ K ξ i : Note that ∥µ ⊤ + W (T3) Q ∥ 2 2 = Θ ∥µ∥ 2 2 σ 2 h d h and each element of W (0)⊤ K is sampled from a Gaussian distribution N (0, σ 2 h ), we have that each element of µ ⊤ + W (T3) Q W (0)⊤ Kis a random variable with mean zero and standard deviation smaller thanC 21 ∥µ∥ 2 σ 2 h d 1 2h . Therefore, for any i ∈ [M ]\{1} by Bernstein's inequality, with probability at least1 -δ/3N 2 M 2 , µ ⊤ + W (T3) Q W (0)⊤ K ξ i = O(∥µ∥ 2 σ p σ 2 h d 1 2 h d log(6N 2 M 2 /δ)) = o(1),where the last equality is by EQUATION) Therefore µ ⊤ + W (T3) Q W (T3)⊤ K -W (0)⊤ K ξ i is-δ/6N 2 M 2 , µ ⊤ + W (T3) Q W (T3)⊤ K -W (0)⊤ K ξ i ≤ C 22 ∥µ∥ 2 σ p σ 2 h d h 2 log 12N 2 M 2 /δ) = o(1),where the last equality is byEQUATION2 . Applying a union bound, with probability at least 1δ/2N 2 M ,µ ⊤ + W (T3) Q W (T3)⊤ K ξ i = µ ⊤ + W (T3) Q W (0)⊤ K ξ i + µ ⊤ + W (T3) Q W (T3)⊤ K -W (0)⊤ K ξ i = o(1) + o(1) = o(1).Therefore, we haveexp(µ ⊤ + W (T3) Q W (T3)⊤ K µ + ) exp(µ ⊤ + W (T3) Q W (T3)⊤ K µ + ) + M i=2 exp(µ ⊤ + W (T3) Q W (T3)⊤ K ξ i ) ≥ exp(-o(1)) exp(-o(1)) + (M -1) exp(o(1)) ≥ 1 1 + (M -1) exp(o(1)) ≥ 1 1 + (M -1) + (M -1)o(1) ≥ 1 M -o(1) ≥ 1 2M ,which complete the proof. Lemma D.9 (Bound of V). Under the same conditions as Theorem 4.1, with probability at least 1δ/2N 2 M , we have that|ξ ⊤ i W (T3) V w O | ≤ 1Proof of Lemma D.9. By (9), we haveEQUATION)Then we haveEQUATION)where the second inequality is by y n ℓ′(t) n ≤ 1, ∥X n ∥ F = O max{∥µ∥ 2 , σ p √ d} and φ(x n,l W (t) Q W (t)⊤ K (X n ) ⊤ ) 2 = O(1). Taking a summation and get∥W (T3) V w O ∥ 2 ≤ ∥W (0) V w O ∥ 2 + T3-1 t=0 ∥W (t+1) V w O -W (t) V w O ∥ 2 = ∥W (0) V w O ∥ 2 + O 1 ηϵ∥µ∥ 2 2 ∥w O ∥ 2 2 • O η • max{∥µ∥ 2 , σ p √ d} • ∥w O ∥ 2 2 = O σ V ∥w O ∥ 2 √ d + O max{∥µ∥ 2 , σ p √ d} ϵ∥µ∥ 2 2 = O σ V ∥w O ∥ 2 √ d + max{∥µ∥ 2 , σ p √ d} ϵ∥µ∥ 2 2 . (134) Then ξ ⊤ i W (T3) Vw O is a Gaussian random variable with mean zero and standard deviation smallerthan O σ V ∥w O ∥ 2 σ p √ d + max{∥µ∥2,σp √ d}•σp ϵ∥µ∥ 2 2 . By Gaussian tail bound, for any i ∈ [M ]\{1}, with probability at least 1 -δ/2N 2 M 2 , |ξ ⊤ i W (T3) V w O | ≤ O σ V ∥w O ∥ 2 σ p √ d + max{∥µ∥ 2 , σ p √ d} • σ p ϵ∥µ∥ 2 2 • 2 log 4N 2 M 2 /δ) ≤ 1,where the last inequality is by σV ≤ O ∥w O ∥ -1 2 •min{∥µ∥ -1 2 , (σ p √ d) -1 }•d -1 4 h , N •SNR 2 = Ω(1)and d = Ω ϵ -2 N 2 d h and d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . Applying a union bound completes the proof. Lemma D.10 (Population Loss). Under the same conditions as Theorem 4.1, we haveL D θ(T 3 ) = o(1)Proof of Lemma D.10. Let event A to be the event that Lemma D.8 holds, and event B to be the event that Lemma D.9 holds. By a union bound, P(A ∧ B) ≥ 1δ/N 2 M . We decompose L D θ(T 3 ) into the following form:EQUATIONThen we boundE[1(A ∧ B)ℓ(yf (X, θ(T 3 )))] and E[1((A ∧ B) c )ℓ(yf (X, θ(T 3 )))] respectively. Bounding E[1(A ∧ B)ℓ(yf (X, θ(T 3 )))]: When event A and event B hold, we haveEQUATIONwhere the first inequality is by Lemma D.8, the second inequality is by ( 112) and Lemma D.9, the last inequality is by M = Θ(1). Therefore,EQUATIONwhere the first inequality is by Cauchy-Schwartz inequality, the second inequality is by log(1 + exp(-z)) ≤ exp(-z).Next we provide a bound forEQUATIONwhere the third inequality is by |x| ≤ max{x, -x}, The fourth inequality is by the independence ofξ i W (T3) V w O . We denote σ = ∥W (T3) V w O ∥ 2 , then ξ i W (T3) Vw O is a Gaussian distribution with mean zero and variance smaller than C 2 p σ 2 σ 2 p . Therefore,EQUATIONwhere the first equality is by ( 134), the third equality is byEQUATIONWe further getEQUATIONPlugging ( 137) and ( 142) into (135), we haveL D θ(T 3 ) ≤ 3 exp log ϵ C20 C 21 + C 24 δ 1 2 N = o(1).In this section, we consider harmful overfitting case under the condition thatN -1 • SNR -2 ≥ Ω(1).The proofs in this section are based on the results in Section C, which hold with high probability.In Stage I, V± , Vn,i begin to pull apart until|V (t) ± | is sufficiently larger than |V (t)n,i |. At the same time, the inner products of q and k maintain their magnitude.Lemma E.1 (Upper bound of V). Let T 0 = O( N ηd 1 4 h σ 2 p d∥w O ∥ 2 2). Then under the same conditions as Theorem 4.2, we haveEQUATIONn,i | = O(d -1 4 h ) for t ∈ [0, T 0 ].Proof of Lemma E.1. By Lemma B.2, we have|γ (t+1) V,+ -γ (t) V,+ | ≤ - η∥µ∥ 2 2 N M n∈S+ ℓ ′(t)n exp(⟨qEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨qEQUATIONn,k ⟩)+ M j=2exp(⟨qEQUATION+ ⟩)exp(⟨q(t) n,j , k (t) + ⟩) + M k=2exp(⟨q(t) n,j , k (t) n,k ⟩) ≤ η∥µ∥ 2 2 N M • 3N 4 1 + (M -1) ≤ 3η∥µ∥ 2 2 4 ,where the second inequality is by Lemma C.1 and -ℓ′(t) n ≤ 1. Similarly, we have |γ (t+1) V,--γ (t) V,-| ≤ 3η∥µ∥ 2 2 4 .By Definition B.1, we have|V (t) + | = V (0) + + t-1 s=0 (γ (s+1) V,+ -γ (s) V,+ )∥w O ∥ 2 2 ≤ |V (0) + | + T0-1 s=0 |γ (s+1) V,+ -γ (s) V,+ | • ∥w O ∥ 2 2 ≤ d -1 4 h + 3η∥µ∥ 2 2 4 • ∥w O ∥ 2 2 • O( N ηd 1 4 h σ 2 p d∥w O ∥ 2 2 ) = d -1 4 h + O( N ∥µ∥ 2 2 d 1 4 h σ 2 p d ) = O(d -1 4 h ),where the first inequality is by triangle inequality and t ≤ T 0 , the second inequality is by Lemma C.2, the last equality is by N -1 • SNR -2 = Ω(1). Similarly, we have|V (t) -| = O(d -1By Lemma B.2, we have|ρ (t+1) V,n,i -ρ (t) V,n,i | ≤ - η N M n ′ ∈S+ ℓ ′(t) n ′ M i=2 (⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) + , k (t) n ′ ,i ′ ⟩)exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨q(t) + , k (t) n ′ ,k ⟩) + M j=2 ⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) n ′ ,j , k (t) n ′ ,i ′ ⟩) exp(⟨q (t) n ′ ,j , k (t) + ⟩) + M k=2 exp(⟨q (t) n ′ ,j , k (t) n ′ ,k ⟩) ) + η N M n ′ ∈S- ℓ ′(t) n ′ M i=2 (⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) -, k (t) n ′ ,i ′ ⟩)exp(⟨q(t) -, k (t) -⟩) + M k=2exp(⟨q(t) -, k (t) n ′ ,k ⟩) + M j=2 ⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) n ′ ,j , k (t) n ′ ,i ′ ⟩) exp(⟨q (t) n ′ ,j , k (t) -⟩) + M k=2 exp(⟨q (t) n ′ ,j , k (t) n ′ ,k ⟩) ) ≤ 3ησ 2 p d 2N M • M + η N M • M N • 2σ 2 p • d log(4N 2 M 2 /δ) ≤ 2ησ 2 p d N = 2ηC 2 p σ 2 p d N (143)where the second inequality is by Lemma C.4 and -ℓ ′(t) n ≤ 1, the third inequality is by d = Ω ϵ -2 N 2 d h ,|V (t) n,i | = V (0) n,i + t-1 s=0 (γ (s+1) V,n,i -γ (s) V,n,i )∥w O ∥ 2 2 ≤ |V (0) n,i | + t-1 s=0 |γ (s+1) V,n,i -γ (s) V,n,i | • ∥w O ∥ 2 2 ≤ d -1 4 h + 2ηC 2 p σ 2 p d N • ∥w O ∥ 2 2 • O( N ηd 1 4 h σ 2 p d∥w O ∥ 2 2 ) = O(d -1 4 ),where the first inequality is by triangle inequality, the second inequality is by Lemma C.2, which completes the proof. Lemma E.2 (Inner Products Hold Magnitude).Let T 0 = O( N ηd 1 4 h σ 2 p d∥w O ∥ 2 2). Then under the same conditions as Theorem 4.2, we haveEQUATION± ⟩|, |⟨qEQUATION± ⟩|, |⟨qEQUATIONn,i , qEQUATIONn,i , qEQUATION∓ ⟩|, |⟨kEQUATION± ⟩|, |⟨k(t) n,i , k (t) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , ∥q (t) ± ∥ 2 2 , ∥k (t) ± ∥ 2 2 = Θ(∥µ∥ 2 2 σ 2 h d h ), ∥q (t) n,i ∥ 2 2 , ∥k (t) n,i ∥ 2 2 = Θ(σ 2 p σ 2 h dd h ) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ] and t ∈ [0, T 0 ].The proof for Lemma E.2 is similar to D.4.Lemma E.3 (V's Beginning of Learning Signals). There existT 1 = 4M (3M +1)N ηd 1 4 h (C 2 p -24M )σ 2 p d∥w O ∥ 2 2 such that the second element of vector X n W (T1) Vw O dominate its other elements, which meansV (T1) n,2 ≥ 3M • max{|V (T1) + |, |V (T1) n,i |} for all n ∈ S + , i ∈ [M ]\{1, 2} and V (T1) n,2 ≤ -3M • max{|V (T1) - |, |V (T1) n,i |} for all n ∈ S -, i ∈ [M ]\{1, 2}.Proof of Lemma E.3. According to Condition 4.1 where C 2 p = 25M , we have Then we haveT 1 = 4M (3M + 1)N ηd 1 4 h (25M -24M )σ 2 p d∥w O ∥ 2 2 = 4(3M + 1)N ηd 1 4 h σ 2 p d∥w O ∥ 2 2 = O N ηd 1 4 h σ 2 p d∥w O ∥ 2 2 ,which satisfies the time condition in Lemma E.1 and Lemma E.2. Then by Lemma D.1 and Lemma D.2 we have-ℓ ′(t) n = 1 2 ± o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) ± , k (t) ± ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) ± ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) ± , k (t) n,j ⟩) ≤ 1 M + o(1), 1 M -o(1) ≤ sof tmax(⟨q (t) n,i , k (t) n,j ⟩) ≤ 1 M + o(1) for i, j ∈ [M ]\{1}, n ∈ [N ] and t ∈ [0, T 1 ].Plugging them in the update rule for γ (t)V,+ showed in Lemma B.2 and we have |γ(t+1) V,+ -γ (t) V,+ | = - η∥µ∥ 2 2 N M n∈S+ ℓ ′(t)n exp(⟨qEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨qEQUATIONn,k ⟩)+ M j=2 exp(⟨q (t) n,j , k (t) + ⟩) exp(⟨q (t) n,j , k (t) + ⟩) + M k=2 exp(⟨q (t) n,j , k (t) n,k ⟩) ≤ η∥µ∥ 2 2 N M • 3N 4 • ( 1 2 ± o(1)) • M ( 1 M ± o(1)) ≤ η∥µ∥ 2 2 2M ≤ 2ησ 2 p d N M (144)where the last inequality is by N -1 • SNR -2 = Ω(1).Then by Definition B.1 and taking a summation, we haveEQUATIONSimilarly, we haveEQUATION)For n ∈ S + , by Lemma B.2, we haveρ (t+1) V,n,2 -ρ (t) V,n,2 = - η N M n ′ ∈S+ ℓ ′(t) n ′ M i ′ =2 (⟨ξ n,2 , ξ n ′ ,i ′ ⟩ exp(⟨q (t) + , k (t) n ′ ,i ′ ⟩)exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨qEQUATION-⟩)EQUATIONn ′ ,k ⟩)+ M j=2 ⟨ξ n,2 , ξ n ′ ,i ′ ⟩ exp(⟨q (t) n ′ ,j , k (t) n ′ ,i ′ ⟩) exp(⟨q (t) n ′ ,j , k (t) -⟩) + M k=2exp(⟨q(t) n ′ ,j , k (t) n ′ ,k ⟩) ) ≥ ησ 2 p d 2N M • M ( 1 M -o(1)) - η N M • M N • 2σ 2 p • d log(4N 2 M 2 /δ) ≥ ησ 2 p d 4N M ≥ ηC 2 p σ 2 p d 4N M (147)where the second inequality is by Lemma C.4 and -ℓEQUATIONfor n ∈ S + . Similarly, for n ∈ S -, we haveEQUATION)By Lemma B.2, we have|ρ (t+1) V,n,i -ρ (t) V,n,i | ≤ - η N M n ′ ∈S+ ℓ ′(t) n ′ M i=2 (⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) + , k (t) n ′ ,i ′ ⟩)exp(⟨q(t) + , k (t) + ⟩) + M k=2exp(⟨q(t) + , k (t) n ′ ,k ⟩) + M j=2 ⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) n ′ ,j , k (t) n ′ ,i ′ ⟩) exp(⟨q (t) n ′ ,j , k (t) + ⟩) + M k=2 exp(⟨q (t) n ′ ,j , k (t) n ′ ,k ⟩) ) + η N M n ′ ∈S- ℓ ′(t) n ′ M i=2 (⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) -, k (t) n ′ ,i ′ ⟩)exp(⟨q(t) -, k (t) -⟩) + M k=2exp(⟨q(t) -, k (t) n ′ ,k ⟩) + M j=2 ⟨ξ n,i , ξ n ′ ,i ′ ⟩ exp(⟨q (t) n ′ ,j , k (t) n ′ ,i ′ ⟩) exp(⟨q (t) n ′ ,j , k (t) -⟩) + M k=2 exp(⟨q (t) n ′ ,j , k (t) n ′ ,k ⟩) ) ≤ 3ησ 2 p d 2N M • M ( 1 M + o(1)) + η N M • M N • 2σ 2 p • d log(4N 2 M 2 /δ) ≤ 2ησ 2 p d N M (150) for i ∈ [M ]\{1, 2}, where the second inequality is by Lemma C.4 and -ℓ′(t) n ≤ 1, the last inequality is by d = Ω ϵ -2 N 2 d h .Then by Definition B.1, we have|V (t) n,i | = V (0) n,i + t-1 s=0 (γ (s+1) V,n,i -γ (s) V,n,i )∥w O ∥ 2 2 ≤ |V (0) n,i | + t-1 s=0 |γ (s+1) V,n,i -γ (s) V,n,i | • ∥w O ∥ 2 2 ≤ d -1 4 h + 4M (3M + 1)N ηd 1 4 h (C 2 p -24M )σ 2 p d∥w O ∥ 2 2 • 2ησ 2 p d N M • ∥w O ∥ 2 2 ≤ d -1 4 h + 8(3M + 1) d 1 4 h (C 2 p -24M ) (151) for i ∈ [M ]\{1, 2}, where the first inequality is by triangle inequality, the second inequality is by Lemma C.2.According to ( 145), ( 146), ( 148), ( 149) and ( 151), it is easy to verify that VEQUATIONn,i |} for all n ∈ S -, i ∈ [M ]\{1, 2}, which completes the proof.In stage II, ⟨q + , k + ⟩, ⟨q n,i , k + ⟩ grows while ⟨q + , k n,j ⟩, ⟨q n,i , k n,j ⟩ decreases, resulting in attention focusing more and more on the signal and less on the noise. By the results of stage I, we have the following condition at the beginning of stage IIEQUATION∓ ⟩|, |⟨k(T1) n,i , k (T1) ± ⟩|, |⟨k (T1) n,i , k (T1) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , ∥q (T1) ± ∥ 2 2 , ∥k (T1) ± ∥ 2 2 = Θ(∥µ∥ 2 2 σ 2 h d h ), ∥q (T1) n,i ∥ 2 2 , ∥k (T1) n,i ∥ 2 2 = Θ(σ 2 p σ 2 h dd h ) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ].Some of the proofs at this stage are based on the above conditions.Notations. To better characterize the gap between different inner products, we define the following notations:• denoteΨ (t) + = ⟨q (t) + , k (t) n,2 ⟩ -⟨q (t) + , k (t) + ⟩, n ∈ S + . • denote Ψ (t) n,+,j = ⟨q (t) + , k (t) n,2 ⟩ -⟨q (t) + , k (t) n,j ⟩, n ∈ S + , j ∈ [M ]\{1, 2}. • denote Ψ (t) -= ⟨q (t) -, k (t) n,2 ⟩ -⟨q (t) -, k (t) -⟩, n ∈ S -. • denote Ψ (t) n,-,j = ⟨q (t) -, k (t) n,2 ⟩ -⟨q (t) -, k (t) n,j ⟩, n ∈ S -, j ∈ [M ]\{1, 2}. • denote Ψ (t) n,i,+ = ⟨q (t) n,i , k (t) n,2 ⟩ -⟨q (t) n,i , k (t) + ⟩, n ∈ S + , i ∈ [M ]\{1}. • denote Ψ (t) n,i,-= ⟨q (t) n,i , k (t) n,2 ⟩ -⟨q (t) n,i , k (t) -⟩, n ∈ S -, i ∈ [M ]\{1}. • denote Ψ (t) n,i,j = ⟨q (t) n,i , k (t) n,2 ⟩ -⟨q (t) n,i , k (t) n,j ⟩, i ∈ [M ]\{1}, j ∈ [M ]\{1, 2}. Lemma E.4 (Upper bound of V). Let T 0 = O N ησ 2 p d∥w O ∥ 2 2 log(6N 2 M 2 /δ) .Then under the same conditions as Theorem 4.2, we have|V (t) + |, |V (t) -|, |V (t) n,i | = o(1) for t ∈ [0, T 0 ].The proof of Lemma E.4 is similar to that of Lemma E.1, except that the time T 0 is changed.Let T 2 = Θ N ησ 2 p d∥w O ∥ 2 2 log(6N 2 M 2 /δ), then by Lemma D.6 and Lemma D.1 we have 1 2 -o(1) ≤ -ℓ ′(t) n ≤ 1 2 + o(1) for n ∈ [N ], t ∈ [T 1 , T 2 ],which can simplify the calculations of α and β defined in Definition B.3 by replacing -ℓ′(t)n by their bounds. Next we prove the following four propositions J (t), K(t), L(t), M(t) by induction on t for t ∈ [T 1 , T 2 ]:• J (t) :EQUATION+ , qEQUATION± , qEQUATIONn,i , qEQUATIONn,2 ⟩ -⟨qEQUATION± ⟩ ⟨qEQUATION± ⟩|, |⟨qEQUATION± ⟩|, |⟨q(t) n,i , k (t) n,j ⟩| ≤ 2 log(d 1 2 h ) |⟨q (t) ± , k (t) ∓ ⟩|, |⟨q (t) n,i , k (t) n,j ⟩| = o(1) for i, j ∈ [M ]\{1}, j ′ ∈ [M ]\{1, 2}, n, n ∈ [N ], n ̸ = n.By the results of Stage I, we know that J (T 1 ), K(T 1 ), M(T 1 ) are true. To prove that J (t), K(t), L(t) and M(t) are true in stage 2, we give the following claims holds for t ∈ [T 1 , T 2 ]: Claim 9. L(T 1 ), . . . , L(t -1) =⇒ J (t + 1) Claim 10. J (T 1 ), . . . , J (t), K(T 1 ), . . . , K(t), L(T 1 ), . . . , L(t -1) =⇒ L(t) Claim 11. J (T 1 ), . . . , J (t), L(T 1 ), . . . , L(t -1), M(T 1 ), . . . , M(t) =⇒ K(t + 1) Claim 12. J (T 1 ), . . . , J (t), K(T 1 ), . . . , K(t), L(T 1 ), . . . , L(t -1) =⇒ M(t + 1)The proofs of Claim 9-12 are similar to the proofs of Claim 5-8. Next, we show some important procedures for proving Claim 10.Similar to D.2.2, we have the dynamic of Ψ as followsEQUATIONEQUATIONEQUATIONEQUATION) for n ∈ [N ], i ∈ [M ]\{1}, j ∈ [M ]\{1, 2}, s ∈ [T 1 , t].Next, we provide the logarithmic increasing lower bounds of Ψ. Recall thatEQUATIONMultiply both sides simultaneously by exp(Ψ+ ) and get exp(ΨEQUATION)Taking a summation from T 1 to t and getEQUATIONBy the property that Ψ+ is monotonically increasing, we haveEQUATIONByEQUATIONEQUATION) for n ∈ [N ], i ∈ [M ]\{1}, j ∈ [M ]\{1, 2}.In Stage III, the outputs of ViT grow up and the loss derivatives are no longer at o(1). We will carefully compute the growth rate of V ± and V n,i while keeping monitoring the monotonicity of ⟨q, k⟩. By substitutingt = T 2 = Θ N ησ 2 p d∥w O ∥ 2 2 into propositions J (t), K(t), L(t), M(t)in Stage II, we have the following conditions at the beginning of stage III|V (T2) + |, |V (T2) - |, |V (T2) n,i | = o(1) for all n ∈ [N ], i ∈ [M ]\{1}. V (T1) n,2 ≥ 3M • max{|V (T1) + |, |V (T1) n,i |} for all n ∈ S + , i ∈ [M ]\{1, 2}. V (T1) n,2 ≤ -3M • max{|V (T1) - |, |V (T1) n,i |} for all n ∈ S -, i ∈ [M ]\{1, 2}. ∥q (T2) ± ∥ 2 2 , ∥k (T2) ± ∥ 2 2 = Θ ∥µ∥ 2 2 σ 2 h d h , ∥q (T2) n,i ∥ 2 2 , ∥k (T2) n,i ∥ 2 2 = Θ σ 2 p σ 2 h dd h , |⟨q (T2) + , q (T2) -⟩|, |⟨q (T2) ± , q (T2) n,i ⟩|, |⟨q (T2) n,i , q (T2) n ′ ,j ⟩| = o(1), |⟨k (T2) + , k (T2) -⟩|, |⟨k (T2) ± , k (T2) n,i ⟩|, |⟨k (T2) n,i , k (T2) n ′ ,j ⟩| = o(1), for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ], i ̸ = j or n ̸ = n ′ . Ψ (T2) ± ≥ log exp(Ψ (T1) ± ) + C 7 ∥µ∥ 2 2 ∥w O ∥ 2 2 d 1 2 h σ 2 p d log(6N 2 M 2 /δ) 3 Ψ (T2) n,±,j ≥ log exp(Ψ (T1) n,±,j ) + C 7 ∥µ∥ 2 2 ∥w O ∥ 2 2 d 1 2 h σ 2 p d log(6N 2 M 2 /δ) 3 Ψ (T2) n,i,± ≥ log exp(Ψ (T1) n,i,± ) + C 7 ∥w O ∥ 2 2 d 1 2 h log(6N 2 M 2 /δ) 3 75 Ψ (T2) n,i,j ≥ log exp(Ψ (T1) n,i,j ) + C 7 ∥w O ∥ 2 2 d 1 2 h log(6N 2 M 2 /δ) 3 |Ψ (t) ± |, |Ψ (t) n,±,j ′ |, |Ψ (t) n,i,± |, |Ψ (t) n,i,j ′ | ≤ log(d 1 2 h ) |⟨q (T2) ± , k (T2) ± ⟩|, |⟨q (T2) ± , k (T2) n,j ⟩|, |⟨q (T2) n,i , k (T2) ± ⟩|, |⟨q (T2) n,i , k (T2) n,j ⟩| ≤ 2 log(d 1 2 h ) |⟨q (T2) ± , k (T2) ∓ ⟩|, |⟨q (T2) n,i , k (T2) n,j ⟩| = o(1) for i, j ∈ [M ]\{1}, j ′ ∈ [M ]\{1, 2}, n, n ∈ [N ], n ̸ = n. Let T 3 = Θ N ηϵσ 2 p d∥w O ∥ 2 2, Next we prove the following four propositions N (t), O(t), P(t), Q(t) by induction on t for t ∈ [T 2 , T 3 ]:• N (t) :V (t) n,2 ≥ 3M • max{|V (T1) + |, |V (T1) n,i |} for all n ∈ S + , i ∈ [M ]\{1, 2}. V (t) n,2 ≤ -3M • max{|V (T1) - |, |V (T1) n,i |} for all n ∈ S -, i ∈ [M ]\{1, 2}. |V (t) ± |, |V (t) n,i | = o(1), for i ∈ [M ]\{1, 2}, n ∈ [N ]. log exp(V (T2) n,2 ) + ηC 17 σ 2 p d∥w O ∥ 2 2 (t -T 2 ) N ≤ V (t) n,2 ≤ 2 log O( 1 ϵ ) ,for all n ∈ S + .-EQUATION± , qEQUATIONn,i , qEQUATIONn,2 ⟩ -⟨q(t) ± , k (t) n,2 ⟩ ≥ 2 ⟨q (t+1) ± , k (t+1) ± ⟩ -⟨q (t) ± , k (t) ± ⟩ ⟨q (t+1) ± , k (t+1) n,2 ⟩ -⟨q (t) ± , k (t) n,2 ⟩ ≥ 2 ⟨q (t+1) ± , k (t+1) n,j ⟩ -⟨q (t) ± , k (t) n,j ⟩ ⟨q (t+1) n,i , k (t+1) n,2 ⟩ -⟨q (t) n,i , k (t) n,2 ⟩ ≥ 2 ⟨q (t+1) n,i , k (t+1) ± ⟩ -⟨q (t) n,i , k (t) ± ⟩ ⟨q (t+1) n,i , k (t+1) n,2 ⟩ -⟨q (t) n,i , k (t) n,2 ⟩ ≥ 2 ⟨q (t+1) n,i , k (t+1) n,j ⟩ -⟨q (t) n,i , k (t) n,j ⟩ Ψ (t+1) ± ≥ Ψ (t) ± Ψ (t+1) n,±,j ≥ Ψ (t) n,±,j Ψ (t+1) n,i,± ≥ Ψ (t) n,i,± Ψ (t+1) n,i,j ≥ Ψ (t) n,i,j for i ∈ [M ]\{1}, j ∈ [M ]\{1, 2}, n ∈ S ± . • Q(t) : |Ψ (t) ± |, |Ψ (t) n,±,j ′ |, |Ψ (t) n,i,± |, |Ψ (t) n,i,j ′ | ≤ log(ϵ -1 d 1 2 h ) |⟨q (t) ± , k (t) ± ⟩|, |⟨q (t) ± , k (t) n,j ⟩|, |⟨q (t) n,i , k (t) ± ⟩|, |⟨q (t) n,i , k (t) n,j ⟩| ≤ 2 log(ϵ -1 d 1 2 h ) |⟨q (t) ± , k (t) ∓ ⟩|, |⟨q (t) n,i , k (t) n,j ⟩| = o(1) for i, j ∈ [M ]\{1}, j ′ ∈ [M ]\{1, 2}, n, n ∈ [N ], n ̸ = n.By the results of Stage II, we know that N (T 1 ), O(T 2 ), Q(T 2 ) are true. To prove that N (t), O(t), P(t) and Q(t) are true in Stage III, we will prove the following claims holds for t ∈ [T 2 , T 3 ]:Claim 13. P(T 2 ), . . . , P(t -1) =⇒ N (t + 1) Claim 14. N (t), O(t), P(T 2 ), . . . , P(t -1) =⇒ P(t) Claim 15. N (T 2 ), . . . , N (t), P(T 2 ), . . . , P(t -1), Q(T 2 ), . . . , Q(t) =⇒ O(t + 1) Claim 16. N (T 2 ), . . . , N (t), O(T 2 ), . . . , O(t), P(T 2 ), . . . , P(t -1) =⇒ Q(t + 1)= C19N ηϵσ 2 p d∥w O ∥ 2 2 such that L S (θ(T )) ≥ 0.1Proof of Lemma E.5. Similar to D.7, we have sof tmax(⟨qEQUATIONsof tmax(⟨qEQUATIONsof tmax(⟨qEQUATIONsof tmax(⟨qEQUATIONsof tmax(⟨qEQUATIONsof tmax(⟨qEQUATIONEQUATIONEQUATIONwe bound f (X n , θ(t)) as followsEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)EQUATIONn,2 ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)+ M l=2 exp(⟨q (t) n,l , k (t) n,2 ⟩) exp(⟨q (t) n,l , k (t) + ⟩) + M j=2 exp(⟨q (t) n,l , k (t) n,j ⟩) • V (t) n,2 + M i=2exp(⟨qEQUATIONn,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)EQUATIONn,i ⟩) exp(⟨qEQUATIONFor the second inequality, byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 , we have O σ 2 p d log(6N 2 M 2 /δ) 3 ∥µ∥ 2 2 ∥w O ∥ 2 2 d 1 2 h = o(1) = log(1 + o(1)) ≤ log(C 20 )as long as C 20 is sufficiently large.Then we have , we haveℓ (t) n = log 1 + exp(-f (X n , θ(t))) ≤ exp(-f (X n , θ(t))) ≤ exp -log 1 ϵ ≤ ϵ.L D θ(T 3 ) ≥ 0.1Proof of Lemma E.6. Similar to ( 133)EQUATION)Taking a summation, we haveEQUATIONThenξ ⊤ i W (T3) Vw O is a Gaussian random variable with mean zero and standard deviation smallerthan O σ V ∥w O ∥ 2 σ p √ d + N ϵ √ d . By Gaussian tail bound, for any i ∈ [M ]\{1}, with probability at least 1 -1/2M , |ξ ⊤ i W (T3) V w O | ≤ O σ V ∥w O ∥ 2 σ p √ d + N ϵ √ d • 2 log 4M ) ≤ 1/2,where the last inequality is by σV ≤ O ∥w O ∥ -1 2 • min{∥µ∥ -1 2 , (σ p √ d) -1 } • d -1 4 h and d = Ω ϵ -2 N 2 d h . Applying a union bound, with probability at least 1 -1/2, |ξ ⊤ i W (T3) V w O | ≤ 1/2.Recall that V (T3) ±= o(1), with probability at least 1 -1/2, we haveEQUATIONThus, L D (θ(t)) ≥ log(1 + e -1/2 ) • 0.5 ≥ 0.1.In this section, we show more calculation process under benign overfitting regime. The calculactions for harmful overfitting is similar.In this subsection, we give the calculactions for α and β defined in Definition B.3.Restatement of Lemma B.1. the gradients of loss function L S (θ) with respect to W Q , W K and W V are given byEQUATIONEQUATION)We will give expressions for α and β defined in Definition B.3 based on these two equations above.By ( 178) and the orthogonal relation between µ and ξ, we haveEQUATIONwherew ⊤ O W (t)⊤ V X ⊤ n and X n W (t)K can be viewed in the following formsEQUATIONn,2 , . . . , Vn,M ,X n W (t) K = k (t)⊤ + , k (t)⊤ n,2 , . . . , k (t)⊤ n,M ⊤ .Then we can express α (t) +,+ and α(t)n,+,i as followsEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨q(t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONn,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,i ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) -( exp(⟨q (t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) ) 2 - k̸ =i V (t) n,k • exp(⟨q (t) + , k (t) n,i ⟩) exp(⟨q (t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨q(t) + , k (t) n,k ⟩) exp(⟨q (t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONUsing the similar method as for ∆q (t) + , we get the other α and β as followsEQUATION-⟩) exp(⟨qEQUATION-⟩)exp(⟨qEQUATION-⟩) exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONEQUATION-⟩) exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONEQUATIONEQUATIONEQUATIONn,j ⟩)EQUATIONfor n ∈ S + ,EQUATIONn,j ⟩)• exp(⟨qEQUATIONn,l ⟩) exp(⟨qEQUATIONfor n ∈ S -,EQUATIONn,j ⟩)• exp(⟨qEQUATIONEQUATIONEQUATIONEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONn,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)+ M k=2 V (t) n,k ⟨ξ n ′ ,i ′ , ξ n,k ⟩ exp(⟨q (t) + , k (t) n,k ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) - M i=2 ⟨ξ n ′ ,i ′ , ξ n,i ⟩ exp(⟨q (t) + , k (t) n,k ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONn,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨qEQUATIONEQUATION-⟩) exp(⟨qEQUATIONn,j ⟩)EQUATIONn,j ⟩)• exp(⟨qEQUATIONEQUATIONn,j ⟩)EQUATIONfor n ∈ S + ,EQUATION-⟩) exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONn,j ⟩)EQUATIONfor n ∈ S -.In this subsection, we give the update rules for the inner products of q and k.Restatement of Lemma B.3. The dynamics of xW Q W K X ⊤ can be characterized as followsEQUATIONEQUATIONEQUATIONn,i , kEQUATIONn,j ⟩ -⟨q(t) + , k (t) n,j ⟩ = α (t) +,+ ⟨k (t) + , k (t) n,j ⟩ + n ′ ∈S+ M l=2 α (t) n ′ ,+,l ⟨k (t) n,j , k (t) n ′ ,l ⟩ + β (t) n,j,+ ∥q (t) + ∥ 2 2 + β (t)n,j,-⟨qEQUATIONn,j ⟩ -⟨q(t) -, k (t) n,j ⟩ = α (t) -,-⟨k (t) -, k (t) n,j ⟩ + n ′ ∈S- M l=2 α (t) n ′ ,-,l ⟨k (t) n,j , k (t) n ′ ,l ⟩ + β (t) n,j,-∥q (t) -∥ 2 2 + β (t) n,j,+ ⟨q (t) + , q (t) -⟩ + N n ′ =1 M l=2 β (t) n,j,n ′ ,l ⟨q (t) -, q (t) n ′ ,l ⟩ + α (t) -,-k (t) -+ n ′ ∈S- M l=2 α (t) n ′ ,-,l k (t) n ′ ,l • β (t) n,j,+ q (t)⊤ + + β (t) n,j,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,j,n ′ ,l q (t)⊤ n ′ ,l , ⟨q (t+1) n,i , k (t+1) n,j ⟩ -⟨q (t) n,i , k (t) n,j ⟩ = α (t) n,i,+ ⟨k (t) + , k (t) n,j ⟩ + α (t) n,i,-⟨k (t) -, k (t) n,j ⟩ + N n ′ =1 M l=2 α (t) n,i,n ′ ,l ⟨k (t) n ′ ,l , k (t) n,j ⟩ + β (t) n,j,+ ⟨q (t) + , q (t) n,i ⟩ + β (t) n,j,-⟨q (t) -, q (t) n,i ⟩ + N n ′ =1 M l=2 β (t) n,j,n ′ ,l ⟨q (t) n ′ ,l , q (t) n,i ⟩ + α (t) n,i,+ k (t) + + α (t) n,i,-k (t) -+ N n ′ =1 M l=2 α (t) n,i,n ′ ,l k (t) n ′ ,l • β (t) n,j,+ q (t)⊤ + + β (t) n,j,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,j,n ′ ,l q (t)⊤ n ′ ,l , for i, j ∈ [M ]\{1}, n ∈ [N ].In addition to these equations above, we give the complete inner product update rule as followsEQUATIONn,j ⟩ -⟨qEQUATIONEQUATIONEQUATIONEQUATION+ ⟩ + ⟨∆kEQUATION+ ⟩(t) +,+ ⟨qEQUATIONEQUATIONEQUATIONEQUATIONn,i ⟩ -⟨k(t) + , k (t) n,i ⟩ = ⟨∆k (t) + , k (t) n,i ⟩ + ⟨k (t) + , ∆k (t) n,i ⟩ + ⟨∆k (t) + , ∆k (t) n,i ⟩ = β (t) +,+ ⟨q (t) + , k (t) n,i ⟩ + n ′ ∈S+ M l=2 β (t) n ′ ,+,l ⟨q (t) n ′ ,l , k (t) n,i ⟩ + β (t) n,i,+ ⟨q (t) + , k (t) + ⟩ + β (t) n,i,-⟨q (t) -, k (t) + ⟩ + N n ′ =1 M l=2 β (t) n,i,n ′ ,l ⟨q (t) n ′ ,l , k (t) + ⟩ + β (t) +,+ q (t) + + n ′ ∈S+ M l=2 β (t) n ′ ,+,l q (t) n ′ ,l • β (t) n,i,+ q (t)⊤ + + β (t) n,i,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,i,n ′ ,l q (t)⊤ n ′ ,l , (209) ⟨k (t+1) - , k (t+1) n,i ⟩ -⟨k (t) -, k (t) n,i ⟩ = ⟨∆k (t) -, k (t) n,i ⟩ + ⟨k (t) -, ∆k (t) n,i ⟩ + ⟨∆k (t) -, ∆k (t) n,i ⟩ = β (t) -,-⟨q (t) -, k (t) n,i ⟩ + n ′ ∈S- M l=2 β (t) n ′ ,-,l ⟨q (t) n ′ ,l , k (t) n,i ⟩ + β (t) n,i,+ ⟨q (t) + , k (t) -⟩ + β (t) n,i,-⟨q (t) -, k (t) -⟩ + N n ′ =1 M l=2 β (t) n,i,n ′ ,l ⟨q (t) n ′ ,l , k (t) + ⟩ + β (t) -,-q (t) -+ n ′ ∈S- M l=2 β (t) n ′ ,-,l q (t) n ′ ,l • β (t) n,i,+ q (t)⊤ + + β (t) n,i,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,i,n ′ ,l q (t)⊤ n ′ ,l , (210) ⟨k (t+1) n,i , k (t+1) n,j ⟩ -⟨k (t) n,i , k (t) n,j ⟩ = ⟨∆k (t) n,i , k (t) n,j ⟩ + ⟨k (t) n,i , ∆k (t) n,j ⟩ + ⟨∆k (t) n,i , ∆k (t) n,j ⟩ = β (t) n,i,+ ⟨q (t) + , k (t) n,j ⟩ + β (t) n,i,-⟨q (t) -, k (t) n,j ⟩ + N n ′ =1 M l=2 β (t) n,i,n ′ ,l ⟨q (t) n ′ ,l , k (t) n,j ⟩ + β (t) n,j,+ ⟨q (t) + , k (t) n,i ⟩ + β (t) n,j,-⟨q (t) -, k (t) n,i ⟩ + N n ′ =1 M l=2 β (t) n,j,n ′ ,l ⟨q (t) n ′ ,l , k (t) n,i ⟩ + β (t) n,i,+ q (t) + + β (t) n,i,-q (t) -+ N n ′ =1 M l=2 β (t) n,i,n ′ ,l q (t) n ′ ,l • β (t) n,j,+ q (t)⊤ + + β (t) n,j,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,j,n ′ ,l q (t)⊤ n ′ ,l , (211) ⟨k (t+1) n,i , k (t+1) n,j ⟩ -⟨k (t) n,i , k (t) n,j ⟩ = ⟨∆k (t) n,i , k (t) n,j ⟩ + ⟨k (t) n,i , ∆k (t) n,j ⟩ + ⟨∆k (t) n,i , ∆k (t) n,j ⟩ = β (t) n,i,+ ⟨q (t) + , k (t) n,j ⟩ + β (t) n,i,-⟨q (t) -, k (t) n,j ⟩ + N n ′ =1 M l=2 β (t) n,i,n ′ ,l ⟨q (t) n ′ ,l , k (t) n,j ⟩ + β (t) n,j,+ ⟨q (t) + , k (t) n,i ⟩ + β (t) n,j,-⟨q (t) -, k (t) n,i ⟩ + N n ′ =1 M l=2 β (t) n,j,n ′ ,l ⟨q (t) n ′ ,l , k (t) n,i ⟩ + β (t) n,i,+ q (t) + + β (t) n,i,-q (t) -+ N n ′ =1 M l=2 β (t) n,i,n ′ ,l q (t) n ′ ,l • β (t) n,j,+ q (t)⊤ + + β (t) n,j,-q (t)⊤ - + N n ′ =1 M l=2 β (t) n,j,n ′ ,l q (t)⊤ n ′ ,l (212) for n ̸ = n, ⟨q (t+1) + , k (t+1) - ⟩ -⟨q (t) + , k (t) -⟩ = ⟨∆q (t) + , k (t) -⟩ + ⟨q (t) + , ∆k (t) -⟩ + ⟨∆q (t) + , ∆k (t) -⟩ = α (t) +,+ ⟨k (t) + , k (t) -⟩ + n∈S+ M i=2 α (t) n,+,i ⟨k (t) n,i , k (t) -⟩ + β (t) -,-⟨q (t) + , q (t) -⟩ + n∈S- M i=2 β (t) n,-,i ⟨q (t) n,i , q (t) + ⟩ + α (t) +,+ k (t) + + n∈S+ M i=2 α (t) n,+,i k (t) n,i • β (t) -,-q (t)⊤ - + n∈S- M i=2 β (t) n,-,i q (t)⊤ n,i , (213) ⟨k (t+1) + , k (t+1) - ⟩ -⟨k (t) + , k (t) -⟩ = ⟨∆k (t) + , k (t) -⟩ + ⟨k (t) + , ∆k (t) -⟩ + ⟨∆k (t) + , ∆k (t) -⟩ = β (t) +,+ ⟨q (t) + , k (t) -⟩ + n∈S+ M i=2 β (t) n,+,i ⟨q (t) n,i , k (t) -⟩ + β (t) -,-⟨q (t) -, k (t) + ⟩ + n∈S- M i=2 β (t) n,-,i ⟨q (t) n,i , k (t) + ⟩ + β (t) +,+ q (t) + + n∈S+ M i=2 β (t) n,+,i q (t) n,i • β (t) -,-q (t)⊤ - + n∈S- M i=2 β (t) n,-,i q (t)⊤ n,i . (214) F.3 Proof of Lemma D.4 Let T 0 = O( 1 ηd 1 4 h ∥µ∥ 2 2 ∥w O ∥ 2 2). By Lemma D.3, we have Lemma D.3 . Plugging this into the expression for α and β gives|V (t) + |, |V (t) -|, |V (t) n,i | = O(d -1 4 h ) for t ∈ [0, T 0 ] byEQUATION+ ⟩) exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) -( exp(⟨q (t) + , k (t) + ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) ) 2 - M i=2 V (t) n,i • exp(⟨q (t) + , k (t) + ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) • exp(⟨q (t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) ≤ η∥µ∥ 2 2 N M • 3N M 4 • O(d -1 4 h ) = O( η∥µ∥ 2 2 d 1 4 h ),where the inequality is by -ℓ′(t) n≤ 1 and the property that attention is smaller than 1 ( e.g.(t) + ,k (t) + ⟩)exp(⟨q(t) + ,k (t) + ⟩)+ M j=2exp(⟨q(t) + ,k (t) n,j ⟩)≤ 1 ). We also have|α (t) n,+,i | = - η N M ℓ ′(t) n ∥µ∥ 2 2 97 • -V (t) + • exp(⟨q (t) + , k (t) + ⟩) exp(⟨q (t) + , k (t) + ⟩) + M j=2 exp(⟨q (t) + , k (t) n,j ⟩) • exp(⟨q (t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) + V (t) n,iexp(⟨q(t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) -( exp(⟨q (t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) ) 2 - k̸ =i V (t) n,k • exp(⟨q (t) + , k (t) n,i ⟩)exp(⟨q(t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) • exp(⟨q (t) + , k (t) n,k ⟩) exp(⟨q (t) + , k (t) + ⟩) + M j=2exp(⟨q(t) + , k (t) n,j ⟩) ≤ η∥µ∥ 2 2 N M • M • O(d -1 4 h ) = O( η∥µ∥ 2 2 d 1 4 h N ),where the inequality is by -ℓ′(t)n ≤ 1 and the property that attention is smaller than 1. We also have|α (t) n ′ ,i ′ ,+ | = η N M n∈S+ -ℓ ′(t) n M i=2 ⟨ξ n ′ ,i ′ , ξ n,i ⟩ • V (t) + exp(⟨q (t) n,i , k (t) + ⟩) exp(⟨q (t) n,i , k (t) + ⟩) + M j=2 exp(⟨q (t) n,i , k (t) n,j ⟩) -( exp(⟨q (t) n,i , k (t) + ⟩) exp(⟨q (t) n,i , k (t) + ⟩) + M j=2 exp(⟨q (t) n,i , k (t) n,j ⟩) ) 2 - M k=2 V (t) n,i • exp(⟨q (t) n,i , k (t) + ⟩) exp(⟨q (t) n,i , k (t) + ⟩) + M j=2 exp(⟨q (t) n,i , k (t) n,j ⟩) • exp(⟨q (t) n,i , k (t) n,k ⟩) exp(⟨q (t) n,i , k (t) + ⟩) + M j=2 exp(⟨q (t) n,i , k (t) n,j ⟩) ≤ η N M 3σ 2 p d 2 + 3N 4 • σ2 p • d log(4N 2 M 2 /δ) • M • O(d -1 = O( ησ 2 p d d 1 4 h N ),where the inequality is by -ℓ′(t)n ≤ 1, Lemma C.4 and the property that attention is smaller than 1. Similarly, we have|α (t) -,-|, |β (t) +,+ |, |β (t) -,-| = O η∥µ∥ 2 2 d 1 4 h , |α (t) n,-,l |, |β (t) n,+,l |, |β (t) n,-,l | = O η∥µ∥ 2 2 d 1 4 h N , |α (t) n,l,-|, |β (t) n,l,+ |, |β (t) n,l,-|, |α (t) n,l,n ′ ,l ′ |, |β (t) n,l,n ′ ,l ′ | = O ησ 2 p d d 1 4 h N for t ∈ [0, T 0 ].A(t) holds for t ∈ [0, T 0 ] A(t) : |⟨q (t) ± , k (t) ± ⟩|, |⟨q (t) n,i , k (t) ± ⟩|, |⟨q (t) ± , k (t) n,j ⟩|, |⟨q (t) n,i , k (t) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , |⟨q (t) ± , q (t) ∓ ⟩|, |⟨q (t) n,i , q (t) ± ⟩|, |⟨q (t) n,i , q (t) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , |⟨k (t) ± , k (t) ∓ ⟩|, |⟨k (t) n,i , k (t) ± ⟩|, |⟨k (t) n,i , k (t) n ′ ,j ⟩| = O max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ) , ∥q (t) ± ∥ 2 2 , ∥k (t) ± ∥ 2 2 = Θ(∥µ∥ 2 2 σ 2 h d h ) ∥q (t) n,i ∥ 2 2 , ∥k (t) n,i ∥ 2 2 = Θ(σ 2 p σ 2 h dd h ) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ].By Lemma C.3 we know that A(0) is true. Now we assume A(0), . . . , A(T ) is true, then we need to proof that A(T + 1) is true. We first proof |⟨qEQUATION)Taking a summation, we obtain thatEQUATIONEQUATIONEQUATIONSimilarly to ⟨qEQUATION+ ⟩, it is easy to know that the inner product does not change by a magnitude more than the product of max{α, β} and max{⟨q, q⟩, ⟨k, k⟩} in a single iteration, which can be expressed as follows⟨q (t+1) , k (t+1) ⟩ -⟨q (t) , k (t) ⟩ = O max{ η∥µ∥ 2 2 d 1 4 h , ησ 2 p d d 1 4 h N } • Θ(max{∥µ∥ 2 2 σ 2 h d h , σ 2 p σ 2 h dd h }) = O η∥µ∥ 2 2 d 1 4 h • Θ(max{∥µ∥ 2 2 σ 2 h d h , σ 2 p σ 2 h dd h }) = O η∥µ∥ 2 2 σ 2 h d 3 4 h • max{∥µ∥ 2 2 , σ 2 p d} (217) 100where the second equality is by the condition that N • SNR 2 = Ω(1).Taking a summation, we obtain thatEQUATION)It is clear that the magnitude of ⟨q(T +1) , k (T +1) ⟩ -⟨q (0) , k (0) ⟩ is smaller than max{∥µ∥ 2 2 , σ 2 p d} • σ 2 h • d h log(6N 2 M 2 /δ),Thus the magnitude of the bound for ⟨q (T +1) , k (T +1) ⟩ is the same as that of ⟨q (T ) , k (T ) ⟩. The proof for ⟨q (T +1) , q (T +1) ⟩ and ⟨k (T +1) , k (T +1) ⟩ is exactly the same, and we can conclude the proof by an induction.In this subsection, we present some bounds for α and β which can be used in D.2 and D.3. All the calculations in this subsection are based on the precise expression for α and β in F.1 and assume that B(T 1 ), . . . , B(s), D(T 1 ), . . . , D(s -1) hold (s ∈ [T 1 , t]). Then the following propositions hold:EQUATIONn,j ⟩), sof tmax(⟨q(s) n,i , k (s) n,j ⟩) ≤ 1 M + o(1).Now we give the bounds respectively for α(s) +,+ , α (s) n,+,i , α (s) -,-, α (s) n,-,i , α (s) n,i,+ , α (s) n,i,-, α (s) n,i,n ′ ,i ′ , β (s) +,+ , β (s) n,+,i , β (s) -,-, β (s) n,-,i , β (s) n,i,+ , β (s) n,i,-, β (s) n,i,n ′ ,i ′ . α (s) +,+ = η N M n∈S+ -ℓ ′(s) n ∥µ∥ 2 2 • exp(⟨q (s) + , k (s) + ⟩) exp(⟨q (s) + , k (s) + ⟩) + M j=2 exp(⟨q (s) + , k (s) n,j ⟩) • V (s) + 1 - exp(⟨q (s) + , k (s) + ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) - M i=2 V (s) n,i • exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) ≥ η N M n∈S+ -ℓ ′(s) n ∥µ∥ 2 2 • exp(⟨q (s) + , k (s) + ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) • V (s) + 1 - exp(⟨q (s) + , k (s) + ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) - 1 2 • V (s) + M i=2 • exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATION+ ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• 1 -exp(⟨q(s) + , k (s) + ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) (219)where the first inequality is byV (s) + ≥ 3M • |V (s)n,i |, the second inequality is by the fact that the sum of attention equal to 1. Similarly, we haveβ (s) +,+ ≥ η 2N M n∈S+ -ℓ ′(s) n ∥µ∥ 2 2 V (s) + • exp(⟨q (s) + , k (s) + ⟩) exp(⟨q (s) + , k (s) + ⟩) + (M -1) exp(max j {⟨q (s) + , k (s) n,j ⟩}) • exp(max j {⟨q (s) + , k (s) n,j ⟩}) exp(⟨q (s) + , k (s) + ⟩) + (M -1) exp(max j {⟨q (s) + , k (s) n,j ⟩}) , (220) α (s) -,-≥ η 2N M n∈S- ℓ ′(s) n ∥µ∥ 2 2 V (s) -• exp(⟨q (s) -, k (s) -⟩) exp(⟨q (s) -, k (s) -⟩) + (M -1) exp(max j {⟨q (s) -, k (s) n,j ⟩}) • exp(max j {⟨q (s) -, k (s) n,j ⟩}) exp(⟨q (s) -, k (s) -⟩) + (M -1) exp(max j {⟨q (s) -, k (s) n,j ⟩}) , (221) β (s) -,-≥ η 2N M n∈S- ℓ ′(s) n ∥µ∥ 2 2 V (s) -• exp(⟨q (s) -, k (s) -⟩) exp(⟨q (s) -, k (s) -⟩) + (M -1) exp(max j {⟨q (s) -, k (s) n,j ⟩}) • exp(max j {⟨q (s) -, k (s) n,j ⟩}) exp(⟨q (s) -, k (s) -⟩) + (M -1) exp(max j {⟨q (s) -, k (s) n,j ⟩}) . (222) α (s) n,+,i = - η N M ℓ ′(s) n ∥µ∥ 2 2 • exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) • -V (s) + • exp(⟨q (s) + , k (s) + ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) + V (s) n,i 1 - exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) - k̸ =i V (s) n,k • exp(⟨q (s) + , k (s) n,k ⟩) exp(⟨q (s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) ≤ - η N M ℓ ′(s) n ∥µ∥ 2 2 • exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) • -V (s) + • exp(⟨q (s) + , k (s) + ⟩) exp(⟨q (s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) + |V (s) n,i | + k̸ =i |V (s) n,k | • ( 1 M + o(1)) ≤ - η N M ℓ ′(s) n ∥µ∥ 2 2 • exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) • -V (s) + • exp(⟨q (s) + , k (s) + ⟩) exp(⟨q (s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) + 2M max l |V (s) n,l | ≤ - η N M ℓ ′(s) n ∥µ∥ 2 2 • exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) • -V (s) + • exp(⟨q (s) + , k (s) + ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) + 3 4 V (s) + exp(⟨q (s) + , k (s) + ⟩) exp(⟨q (s) + , k (s) + ⟩) + M j=2 exp(⟨q (s) + , k (s) n,j ⟩) = η 4N M ℓ ′(s) n ∥µ∥ 2 2 V (s) + • exp(⟨q (s) + , k (s) n,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨q(s) + , k (s) + ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩),where the third inequality is byV (s) + ≥ 3M • |V (s)n,i | and sof tmax(⟨qEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩)EQUATIONEQUATIONn,j ⟩)EQUATIONEQUATIONn,j ⟩)• exp(⟨qEQUATIONEQUATION+ ⟩) exp(⟨qEQUATIONEQUATIONEQUATIONEQUATIONEQUATION+ ⟩)exp(⟨qEQUATIONEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2 exp(⟨q (s) n,i , k (s) n,j ⟩) ,where the first inequality is byEQUATIONEQUATION+ ⟩) . Similarly, we haveEQUATION-⟩) exp(⟨qEQUATIONn,j ⟩)• 1 -exp(⟨qEQUATION-⟩)exp(⟨qEQUATION+ ⟩) exp(⟨qEQUATIONEQUATION+ ⟩) exp(⟨qEQUATIONEQUATIONEQUATIONEQUATIONn ′ ,j ⟩)EQUATIONEQUATIONEQUATIONn ′ ,j ⟩)+ {lower order term} ≥ η∥ξ n ′ ,i ′ ∥ 2 2 N M -ℓ ′ n ′ (θ(s))exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATIONEQUATION+ ⟩)exp(⟨qEQUATIONEQUATIONEQUATIONn ′ ,j ⟩)EQUATION+ ⟩) exp(⟨qEQUATIONEQUATIONn ′ ,j ⟩)• 1 -exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATIONEQUATIONn ′ ,j ⟩)EQUATION+ ⟩) exp(⟨qEQUATIONEQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M j=2 exp(⟨q (s) n ′ ,i ′ , k (s) n ′ ,j ⟩), where the {lower order term} is by the property that∥ξ n ′ ,i ′ ∥ 2 2 is much larger than ⟨ξ n ′ ,i ′ , ξ n,i ⟩ in Lemma C.4 and the condition d = Ω ϵ -2 N 2 d h , the first inequality is by V (s) + ≥ 3M • |V (s) n,i |, the last inequality is by ∥ξ n ′ ,i ′ ∥ 2 2 ≥ σ 2 p d2 and we absorb the {lower order term}. Similarly, we haveEQUATION-⟩) exp(⟨qEQUATIONEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATIONn ′ ,j ⟩)• exp(⟨q(s) + , k (s) n ′ ,i ′ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATIONn ′ ,j ⟩)+ V (s) n ′ ,i ′ exp(⟨q (s) + , k (s) n ′ ,i ′ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATIONn ′ ,j ⟩)• 1 -exp(⟨qEQUATIONEQUATIONn ′ ,j ⟩)EQUATIONn ′ ,i ′ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATIONn ′ ,j ⟩)EQUATIONEQUATIONn ′ ,j ⟩)EQUATION+ ⟩) + M j=2exp(⟨qEQUATION+ ⟩) exp(⟨qEQUATIONEQUATIONn ′ ,j ⟩)EQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M j=2 exp(⟨q (s) + , k (s) n ′ ,j ⟩) ≤ η∥ξ n ′ ,i ′ ∥ 2 2 2N M ℓ ′ n ′ (θ(s))V (s) + • exp(⟨q (s) + , k (s) n ′ ,i ′ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATIONn ′ ,j ⟩)• exp(⟨qEQUATION+ ⟩) exp(⟨qEQUATIONn ′ ,j ⟩)+ {lower order term} ≤ ησ 2 p d 5N M ℓ ′ n ′ (θ(s))V (s) + • exp(⟨q (s) + , k (s) n ′ ,i ′ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATIONn ′ ,j ⟩)• exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATIONn ′ ,j ⟩), where the {lower order term} is by the property that∥ξ n ′ ,i ′ ∥ 2 2 is much larger than ⟨ξ n ′ ,i ′ , ξ n,i ⟩ in Lemma C.4 and the condition d = Ω ϵ -2 N 2 d h , the first inequality is by V (s) + ≥ 3M • |V (s) n,i |, the last inequality is by ∥ξ n ′ ,i ′ ∥ 2 2 ≥ σ 2 p d2 and we absorb the {lower order term}. Similarly, we haveEQUATIONEQUATIONEQUATIONEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONEQUATIONn,l ′ ⟩)EQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨q(s) n,k , k (s) n,l ′ ⟩) = - η∥ξ n,i ∥ 2 2 N M ℓ ′(s) n • exp(⟨q (s) n,i , k (s) n,j ⟩) exp(⟨q (s) n,i , k (s) + ⟩) + M l ′ =2exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨q(s) n,i , k (s) n,l ′ ⟩) + |V (s) n,j | + l̸ =i |V (s) n,l | • ( 1 M + o(1))+ {lower order term}EQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONEQUATIONn,l ′ ⟩)EQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩)EQUATIONEQUATIONn,l ′ ⟩)EQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATION+ ⟩) exp(⟨q(s) n,i , k (s) + ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩)EQUATION+ ⟩) + M l ′ =2exp(⟨q(s) n,i , k (s) n,l ′ ⟩) • exp(⟨q (s) n,i , k (s) + ⟩) exp(⟨q (s) n,i , k (s) + ⟩) + M l ′ =2 exp(⟨q (s) n,i , k (s) n,l ′ ⟩), where the {lower order term} is by the property that ∥ξ n,i ∥ 2 2 is much larger than ⟨ξ n ′ ,i ′ , ξ n,i ⟩ in Lemma C.4 and the condition d = Ω ϵ -2 N 2 d h , the third inequality is byV (s) + ≥ 3M • |V (s) n,i | and sof tmax(⟨q (s) n,i , k (s) + ⟩) ≥ 1 M -o(1), the last inequality is by ∥ξ n,i ∥ 2 2 ≥ σ 2 p d2 and we absorb the {lower order term}. Similarly, we haveEQUATIONn,j ⟩) exp(⟨q(s) n,i , k (s) -⟩) + M l ′ =2exp(⟨qEQUATION-⟩)exp(⟨q(s) n,i , k (s) -⟩) + M l ′ =2exp(⟨qEQUATIONEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩)EQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONEQUATIONn,l ′ ⟩)• exp(⟨qEQUATIONn,l ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨q(s) n,i , k (s) n,l ′ ⟩) = η∥ξ n,j ∥ 2 2 N M -ℓ ′(s) n • exp(⟨q (s) n,i , k (s) n,j ⟩) exp(⟨q (s) n,i , k (s) + ⟩) + M l ′ =2exp(⟨q(s) n,i , k (s) n,l ′ ⟩) -V (s) + exp(⟨q (s) n,i , k (s) + ⟩) exp(⟨q (s) n,i , k (s) + ⟩) + M l ′ =2exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩)EQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩)EQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩)EQUATIONEQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩)EQUATIONEQUATIONEQUATIONEQUATIONn,l ′ ⟩), where the {lower order term} is by the property that ∥ξ n,i ∥ 2 2 is much larger than⟨ξ n ′ ,i ′ , ξ n,i ⟩ in Lemma C.4 and the condition d = Ω ϵ -2 N 2 d h , the second inequality is by V (s) + ≥ 3M • |V (s) n,i |, the last inequality is by ∥ξ n,j ∥ 2 2 ≥ σ 2 p d2 and we absorb the {lower order term}. Similarly, we haveβ (s) n,j,n,i ≤ - ησ 2 p d 5N M ℓ ′(s) n V (s) -• exp(⟨q (s) n,i , k (s) n,j ⟩) exp(⟨q (s) n,i , k (s) -⟩) + M l ′ =2exp(⟨qEQUATION-⟩) exp(⟨q(s) n,i , k (s) -⟩) + M l ′ =2exp(⟨qEQUATIONn,l ′ ⟩) .Summarizing the above equations, we have the signs of α and β as follows:EQUATION+,+ , β-,-, αn,+,i , β(s) n,-,i ≥ 0, α (s) n,+,i , α (s) n,-,i , α (s) n,i,n,j , β (s) n,i,+ , β (s) n,i,-, β (s) n,j,n,i ≤ 0.F.5 Lower Bounds of ⟨ q, k ⟩ In order to give the lower bounds for ⟨q, k⟩, we need to rewrite the bounds of α and β in a more concise form. We first expand the equations in F.4 under the assumption that B(s) holds for sEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ′ ⟩)• 1 -exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨qEQUATIONEQUATIONEQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ′ ⟩)• exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨q(s) + , k (s) n,j ′ ⟩) ≥ η 2N M -ℓ ′(s) n ∥µ∥ 2 2 V (s) + • 1 M -o(1)• exp(⟨qEQUATION+ , kEQUATIONexp(⟨qEQUATIONwhere the ⟨qEQUATIONn,j ⟩ in the second inequality is a particular choice (we will characterize the dynamic of ⟨qEQUATIONn,j ⟩), the third inequality is by sof tmax(⟨q(s) + , k (s) + ⟩) ≥ 1 M -o(1). In the fourth inequality, by ⟨q (T1) , k (T1) ⟩ = o(1) and the monotonicity of ⟨q (s) , k (s) ⟩ (⟨q(s) + , k (s) + ⟩ is increasing and ⟨q (s) + , k (s)n,j ⟩ is decreasing), there exist a constant C such that C exp(⟨qEQUATIONn,j ′ ⟩). In the last inequality, we plugging the lower bounds ofV (s) + and -ℓ ′(s)n and then absorb all the constant factors. Similarly, we haveEQUATIONEQUATIONEQUATIONEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ′ ⟩)• exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨q(s) + , k (s) n,j ′ ⟩) ≤ η 4N M ℓ ′(s) n ∥µ∥ 2 2 V (s) + • 1 M -o(1)• exp(⟨qEQUATION+ , kEQUATIONexp(⟨qEQUATIONwhere the inequalities is similar to (223). Similarly, we haveEQUATIONEQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨q(s) n,i , k (s) n,j ′ ⟩) ≥ - η∥µ∥ 2 2 2N M ℓ ′(s) n V (s) + • 1 M -o(1) • M j ′ =2exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨qEQUATIONEQUATIONEQUATIONn,j ⟩) C exp(⟨qEQUATIONwhere the inequalities is similar to (223), and ⟨qEQUATIONn,j ⟩ is a particular choice (we will characterize the dynamic of ⟨q(s) n,i , k (s) + ⟩ -⟨q (s) n,i , k (s)n,j ⟩). Similarly, we haveEQUATIONEQUATIONEQUATIONn,j,+ ≤ -EQUATIONn,j,-≤ -EQUATIONn,i,n,j ≤ -EQUATIONn,j,n,i ≤ -EQUATION)With the concise lower bounds for α and β above and proposition C(s), we will give the lower bounds for the dynamics of ⟨q, k⟩.EQUATION⟩ -⟨qEQUATIONEQUATIONEQUATIONEQUATION+,+ qEQUATIONEQUATIONEQUATIONwhere the first inequality is by ( 223), ( 224), the bound of ∥qEQUATION+ ∥ 2 2 in stage II, the second inequality is by absorbing the {lower order term} and the constant factors. Similarly, we haveEQUATIONEQUATIONn,j ⟩ -⟨qEQUATION+,+ ⟨kEQUATIONEQUATIONEQUATION+ , q (s)EQUATIONEQUATIONwhere the first inequality is by ( 227), ( 232), the bound of ∥kEQUATION+ ∥ 2 2 in stage II, the second inequality is by absorbing the {lower order term} and the constant factors. Similarly, we haveEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere the first inequality is by ( 230), ( 228), the bound of ∥kEQUATIONn,i ∥ 2 2 in stage II, the second inequality is by absorbing the {lower order term} and the constant factors. Similarly, we haveEQUATIONn,j ⟩ -⟨qEQUATIONEQUATION-, q (s)EQUATIONwhere the first inequality is by ( 234), ( 235), the bound of ∥kEQUATIONn,i ∥ 2 2 in stage II, the second inequality is by absorbing the {lower order term} and the constant factors. EQUATION+ ⟩) exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATION+ ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)EQUATION+ ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONn,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATION+ ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATIONn,i ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) ≤ η N M n∈S+ ∥µ∥ 2 2 • V (s) + • M j=2exp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)+ max i |V (s) n,i | • M j=2exp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATION+ ⟩)EQUATION+ ⟩),where the first inequality is by -ℓ′(s) n≤ 1 and sof tmax(⟨qEQUATION+ ⟩) ≤ 1. For the second inequality, we first considerM j=2exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩)+ M j=2exp(⟨q(s) + ,k (s) n,j ⟩) ≤ M j=2exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩), then by the monotonicity of ⟨q EQUATION+,+ ≤ ηC 9 ∥µ∥ 2 2 exp(⟨qEQUATION-,-≤ ηC 9 ∥µ∥ 2 2 exp(⟨qEQUATION+ ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ′ ⟩)• exp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨q(s) + , k (s) n,j ′ ⟩) + V (s) n,iexp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ′ ⟩)• exp(⟨qEQUATIONn,k ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATION+ ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩) + M j ′ =2exp(⟨qEQUATION+ , kEQUATIONexp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j ′ =2exp(⟨q(s) + , k (s) n,j ′ ⟩) ≥ - 2η N M ∥µ∥ 2 2 V (s) + • exp(⟨q (s) + , k (s) n,j ⟩) C ≥ - ηC 9 ∥µ∥ 2 2 N • exp(⟨q (s) + , k (s) n,j ⟩),where the second inequality is byV (s) + ≥ 3M • |V (s) n,i |, -ℓ ′(s) n≤ 1 and the property that attention < 1.For the third inequality, we consider exp(⟨qEQUATIONn,j ⟩) exp(⟨qEQUATION+ ⟩)+ M j ′ =2exp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) + ,k (s) + ⟩)first, then by the monotonicity of ⟨q n,j ⟩).EQUATION+ ⟩) exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATION+ ⟩)exp(⟨q(s) n,i , k (s) + ⟩) + M j=2exp(⟨qEQUATION+ ⟩)exp(⟨qEQUATIONEQUATION+ ⟩)EQUATIONEQUATION+ ⟩)exp(⟨q(s) n,i , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)EQUATIONn,j ⟩) , then by the monotonicity ofEQUATIONEQUATIONn,j ⟩ and ⟨qEQUATIONn,i = o(1) for s ∈ [T 1 , t] and absorbing the constant factors. Similarly, we haveEQUATIONEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩)EQUATIONEQUATIONn,j ⟩)EQUATION+ ⟩) exp(⟨q(s) n,i , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONn,j ⟩)EQUATION+ ⟩) exp(⟨qEQUATIONn,j ⟩)EQUATION+ ⟩) exp(⟨qEQUATIONn,j ⟩)EQUATIONn,j ⟩) exp(⟨qEQUATIONn,j ⟩)+ |V (s) n,i | • M k=2 exp(⟨q (s) n,i , k (s) n,k ⟩) exp(⟨q (s) n,i , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)EQUATION+ ⟩) + {lower order term}≤ ηC 9 σ 2 p d N exp(⟨q (s) n,i , k (s) + ⟩), where most of these processes are similar to the other equations above, and the last inequality we absorb the constant factors and the {lower order term}. Similarly, we haveEQUATIONn,i,-≥ -EQUATIONn,i,n,j ≥ -EQUATIONn,j,n,i ≥ -EQUATIONn,j ⟩), Similar to F.5, we apply the bounds of α and β above to give the upper bounds for the dynamics ⟨q, k⟩. EQUATIONEQUATIONn,j ⟩ -⟨qEQUATION+ , q (s)EQUATIONsimilarly, we haveEQUATIONn,j ⟩ -⟨qEQUATIONn,j ⟩ ≥ -EQUATIONn,j ⟩). ( 246)EQUATIONsimilarly, we haveEQUATIONEQUATIONn,j ⟩ -⟨qEQUATION-, q (s)EQUATIONn,j ⟩).(249) F.7 Bounds for the Sum of α and βThe gradients of the inner products of q and k contain a lot of coefficients α and β, and in order to conveniently give the upper bounds of some lower order inner products, we will give upper bounds for the summation of α and β (e.g. Note that in the Jacobi matrix of the Softmax function, the elements on the diagonal are sof tmax(a i )• 1sof tmax(a i ) and the elements on the off-diagonal are sof tmax(a i ) • sof tmax(a j ). In Stage II, the attentions on signals µ ± increase and the attentions on noises ξ decrease, then we can consider the following cases • if a i = ⟨q + , k + ⟩ or a i = ⟨q i , k + ⟩, sof tmax(a i ) has a constant upper bound 1, 1sof tmax(a i ) decreases as sof tmax(a i ) increases. So the upper bound of sof tmax(a i ) • 1sof tmax(a i ) decreases as sof tmax(a i ) increases.• if a i = ⟨q + , k j ⟩ or a i = ⟨q i , k j ⟩, 1-sof tmax(a i ) has a constant upper bound 1. So the upper bound of sof tmax(a i ) • 1sof tmax(a i ) decreases as sof tmax(a i ) decreases.• if a j = ⟨q + , k j ⟩ or a j = ⟨q i , k j ⟩, sof tmax(a i ) has a constant upper bound 1. So the upper bound of sof tmax(a i ) • sof tmax(a j ) decreases as sof tmax(a j ) decreases.Based on the above cases, we first study the bounds of the following terms• 1sof tmax(⟨qEQUATION+ ⟩)• 1sof tmax(⟨qEQUATION+ ⟩)• sof tmax(⟨qEQUATIONn,j ⟩)• sof tmax(⟨qEQUATIONn,j ⟩)Note that 1sof tmax(⟨qEQUATION+ ⟩) = j sof tmax(⟨qEQUATIONn,j ⟩) and 1sof tmax(⟨qEQUATIONn,j ⟩), we only need to give the upper bounds for sof tmax(⟨qEQUATIONn,j ⟩) and sof tmax(⟨qEQUATIONn,j ⟩). Assume that the propositions B(T 1 ), . . . , B(s), D(T 1 ), . . . , D(s -1) hold (s ∈ [T 1 , t]), we haveEQUATIONEQUATIONEQUATION) for i, j ∈ [M ]\{1}, n ∈ [N ], s ∈ [T 1 , t].Then we have exp(⟨qEQUATIONn,j ⟩) exp(⟨q(s) ± , k (s) ± ⟩) + M j ′ =2exp(⟨qEQUATION)For the first inequality, by ⟨q (T1) , k (T1) ⟩ = o(1) and the monotonicity of ⟨q (s) , k (s) ⟩ (⟨qEQUATION± ⟩ is increasing and ⟨q(s) ± , k (s)n,j ⟩ is decreasing), there exist a constant C such that C exp(⟨q (s) ± , k (s) ± ⟩) ≥ exp(⟨q (s) ± , k (s) ± ⟩) + M j ′ =2 exp(⟨q (s) ± , k (s) n,j ′ ⟩).EQUATION)Plugging ( 250),( 253) and ( 254) into the expressions of α, β we haveEQUATION+ ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨qEQUATION+ , k+ ⟩) exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)EQUATION+ ⟩)exp(⟨q(s) + , k (s) + ⟩) + M j=2exp(⟨qEQUATIONn,j ⟩)• exp(⟨qEQUATIONn,i ⟩)exp(⟨qEQUATION+ ⟩) + M j=2exp(⟨q(s) + , k (s) n,j ⟩) ≤ η∥µ∥ 2 2 N M • 3N 4 • O(d -1 4 h ) + ηC 4 ∥µ∥ 2 2 ∥w O ∥ 2 2 (s -T 1 )• O 1EQUATION)where the third equality is byη 2 C13∥µ∥ 4 2 ∥w O ∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ) 2 • (s -T 1 )(s -T 1 -1) ≥ 0 for s ∈ [T 1 , t]. Next,we give an upper bound forη 2 ∥µ∥ 4 2 ∥w O ∥ 2 2 (s-T1) C13+ η 2 C 13 ∥µ∥ 4 2 ∥w O ∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ) 2 •(s-T1)(s-T1-1)as follows:EQUATIONwhere the inequality is by ax + b x ≥ 2 √ ab for x > 0, the third equality is by absorbing the lower order termη 2 C13∥µ∥ 4 2 ∥w O ∥ 2 2 d 1 2 h N log(6N 2 M 2 /δ)2 , the last equality is by ∥w O ∥ 2 = Θ(1). Plugging this into (255) and getEQUATIONSimilarly, we haveEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONfor i ∈ [M ]\{1}, n ∈ S ± , the last equality is by N • SNR 2 ≥ Ω(1).EQUATIONEQUATIONfor i, j ∈ [M ]\{1}, n ∈ [N ], the last equality is by N • SNR 2 ≥ Ω(1). EQUATION) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ], n ̸ = n ′ ,EQUATIONwhere the last equality is by ∥w O ∥ = Θ(1). Similarly, we haveEQUATIONEQUATIONfor i ∈ [M ]\{1}, n ∈ S ± . t s=T1 |β (s) n,+,i |, t s=T1 |β (s) n,-,i | = O SNR • N -1 2 d -1 4 h (268) for i ∈ [M ]\{1}, n ∈ S ± . t s=T1 |α (s) n,i,+ |, t s=T1 |α (s) n,i,-|, t s=T1 |α (s) n,i,n,j |, t s=T1 |β (s) n,j,n,i | = O d -1 4 h (269) for i, j ∈ [M ]\{1}, n ∈ S ± . t s=T1 |α (s) n,i,n ′ ,j |, t s=T1 |β (s) n,j,n ′ ,i | = O d -1 2 d -1 4 h log(6N 2 M 2 /δ) (270) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ], n ̸ = n ′ .With these sums of α and β above, we can easily prove Claim 3 and Claim 4.In this subsection, we assume that E(T 1 ), . . . , E(t) hold, and then proof that C(t + 1) is true with the result of F.7. n,i ⟩| + {lower order term}= O N 1 2 d -1 4 h • O(log(d 1 2 h )) + N • M • O N -1 2 d -1 4 h • O(log(d 1 2 h )) = O N 1 2 d -1 4 h log(d 1 2 h )where the first inequality is by triangle inequality, the second inequality is by 199. SinceEQUATIONn,i ∥ 2 2 -∥qEQUATIONn,i ∥ 2 2 = Θ(σ 2 p σ 2 h dd h ) for i ∈ [M ]\{1}, n ∈ [N ]. |⟨q (t+1) + , q (t+1) - ⟩| ≤ |⟨q (T1) + , q (T1) -⟩| + t s=T1 ⟨q (s+1) + , q (s+1) - ⟩ -⟨q (s) + , q (s) -⟩ ≤ |⟨q (T1) + , q (T1) -⟩| + t s=T1 α (s) +,+ ⟨q (s) -, k (s) + ⟩ + n∈S+ M i=2 α (s) n,+,i ⟨q (s) -, k (s) n,i ⟩ + α (s) -,-⟨q (s) + , k (s) -⟩ + n∈S- M i=2 α (s) n,-,i ⟨q (s) + , k (s) n,i ⟩ + α (s) +,+ k (s) + + n∈S+ M i=2 α (s) n,+,i k (s) n,i • α (s) -,-k (s)⊤ - + n∈S- M i=2 α (s) n,-,i k (s)⊤ n,i ≤ |⟨q (T1) + , q (T1) -⟩| + t s=T1 |α (s) +,+ ||⟨q (s) -, k (s) + ⟩| + n∈S+ M i=2 t s=T1 |α (s) n,+,i ||⟨q (s) -, k (s) n,i ⟩| + t s=T1 |α (s) -,-||⟨q (s) + , k (s) -⟩| + n∈S- M i=2 t s=T1 |α (s) n,-,i ||⟨q (s) + , k (s) n,i ⟩| + {lower order term} ≤ |⟨q (T1) + , q (T1) -⟩| + O N 1 2 d -1 4 h • o(1) + N • M • O N -1 2 d -1 4 h • log(d 1 2 h ) = |⟨q (T1) + , q (T1) -⟩| + O N 1 2 d -1 4 h log(d 1 2 h ) = o(1),where the first inequality is triangle inequality, the second inequality is by (198) , the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . |⟨q (t+1) + , q (t+1) n,i ⟩| ≤ |⟨q (T1) + , q (T1) n,i ⟩| + t s=T1 ⟨q (s+1) + , q (s+1) n,i ⟩ -⟨q (s) + , q (s) n,i ⟩ ≤ |⟨q (T1) + , q (T1) n,i ⟩| + t s=T1 α (s) +,+ ⟨q (s) n,i , k (s) + ⟩ + n ′ ∈S+ M l=2 α (s) n ′ ,+,l ⟨q (s) n,i , k (s) n ′ ,l ⟩ + α (s) n,i,+ ⟨q (s) + , k (s) + ⟩ + α (s) n,i,-⟨q (s) + , k (s) -⟩ + N n ′ =1 M l=2 α (s) n,i,n ′ ,l ⟨q (s) + , k (s) n ′ ,l ⟩ + α (s) +,+ k (s) + + n∈S+ M i=2 α (s) n,+,i k (s) n,i • α (s) n,i,+ k (s)⊤ + + α (s) n,i,-k (s)⊤ - + N n ′ =1 M l=2 α (s) n,i,n ′ ,l k (s)⊤ n ′ ,l ≤ |⟨q (T1) + , q (T1) n,i ⟩| + t s=T1 |α (s) +,+ ||⟨q (s) n,i , k (s) + ⟩| + M l=2 t s=T1 |α (s) n,+,l ||⟨q (s) n,i , k (s) n,l ⟩| + n ′ ∈S+∧n ′ ̸ =n M l=2 t s=T1 |α (s) n ′ ,+,l ||⟨q (s) n,i , k (s) n ′ ,l ⟩| + t s=T1 |α (s) n,i,+ ||⟨q (s) + , k (s) + ⟩| + t s=T1 |α (s) n,i,-||⟨q (s) + , k (s) -⟩| + M l=2 t s=T1 |α (s) n,i,n,l ||⟨q (s) + , k (s) n,l ⟩| + n ′ ̸ =n M l=2 t s=T1 |α (s) n,i,n ′ ,l ||⟨q (s) + , k (s) n ′ ,l ⟩| + {lower order term} ≤ |⟨q (T1) + , q (T1) n,i ⟩| + O N 1 2 d -1 4 h • log(d 1 2 h ) + M • O N -1 2 d -1 4 h • log(d 1 2 h ) + N • M • O N -1 2 d -1 4 h • o(1) + O d -1 4 h • log(d 1 2 h ) + M • O d -1 4 h • log(d 1 2 h ) + N • M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • log(d 1 2 h ) = |⟨q (T1) + , q (T1) n,i ⟩| + O N 1 2 d -1 4 h + O N d -1 2 d -1 4 h log(6N 2 M 2 /δ) log(d 1 2 h ) = o(1),where the first inequality is triangle inequality, the second inequality is by ( 202), the last equality is by d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 and d = Ω ϵ -2 N 2 d h . Similarly, we have|⟨q (t+1) - , q (t+1) n,i ⟩| = o(1). |⟨q (t+1) n,i , q (t+1) n,j ⟩| ≤ |⟨q (T1) n,i , q (T1) n,j ⟩| + t s=T1 ⟨q (s+1) n,i , q (s+1) n,j ⟩ -⟨q (s) n,i , q (s) n,j ⟩ ≤ |⟨q (T1) n,i , q (T1) n,j ⟩| + t s=T1 α (s) n,i,+ ⟨q (s) n,j , k (s) + ⟩ + α (s) n,i,-⟨q (s) n,j , k (s) -⟩ + N n ′ =1 M l=2 α (s) n,i,n ′ ,l ⟨q (s) n,j , k (s) n ′ ,l ⟩ + α (s) n,j,+ ⟨q (s) n,i , k (s) + ⟩ + α (s) n,j,-⟨q (s) n,i , k (s) -⟩ + N n ′ =1 M l=2 α (s) n,j,n ′ ,l ⟨q (s) n,i , k (s) n ′ ,l ⟩ + α (s) n,i,+ k (s) + + α (s) n,i,-k (s) -+ N n ′ =1 M l=2 α (s) n,i,n ′ ,l k (s) n ′ ,l • α (s) n,j,+ k (s)⊤ + + α (s) n,j,-k (s)⊤ - + N n ′ =1 M l=2 α (s) n,j,n ′ ,l k (s)⊤ n ′ ,l ≤ |⟨q (T1) n,i , q (T1) n,j ⟩| + t s=T1 |α (s) n,i,+ ||⟨q (s) n,j , k (s) + ⟩| + t s=T1 |α (s) n,i,-||⟨q (s) n,j , k (s) -⟩| + M l=2 t s=T1 |α (s) n,i,n,l ||⟨q (s) n,j , k (s) n,l ⟩| + n ′ ̸ =n M l=2 t s=T1 |α (s) n,i,n ′ ,l ||⟨q (s) n,j , k (s) n ′ ,l ⟩| + t s=T1 |α (s) n,j,+ ||⟨q (s) n,i , k (s) + ⟩| + t s=T1 |α (s) n,j,-||⟨q (s) n,i , k (s) -⟩| + M l=2 t s=T1 |α (s) n,j,n,l ||⟨q (s) n,i , k (s) n,l ⟩| + n ′ ̸ =n M l=2 t s=T1 |α (s) n,j,n ′ ,l ||⟨q (s) n,i , k (s) n ′ ,l ⟩| + {lower order term} ≤ |⟨q (T1) n,i , q (T1) n,j ⟩| + O d -1 4 h • log(d 1 2 h ) + M • O d -1 4 h • log(d 1 2 h ) + N • M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • o(1) = |⟨q (T1) n,i , q (T1) n,j ⟩| + O d -1 4 h log(d 1 2 h ) + o N d -1 2 d -1 4 h log(6N 2 M 2 /δ) = o(1) for i, j ∈ [M ]\{1}, i ̸ = j, n ∈ [N ]. The first inequality is triangle inequality, the second inequality is by (204), the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 and d = Ω ϵ -2 N 2 d h . |⟨q (t+1) n,i , q (t+1) n,j ⟩| ≤ |⟨q (T1) n,i , q (T1) n,j ⟩| + t s=T1 ⟨q (s+1) n,i , q (s+1) n,j ⟩ -⟨q (s) n,i , q (s) n,j ⟩ ≤ |⟨q (T1) n,i , q (T1) n,j ⟩| + t s=T1 α (s) n,i,+ ⟨q (s) n,j , k (s) + ⟩ + α (s) n,i,-⟨q (s) n,j , k (s) -⟩ + N n ′ =1 M l=2 α (s) n,i,n ′ ,l ⟨q (s) n,j , k (s) n ′ ,l ⟩ + α (s) n,j,+ ⟨q (s) n,i , k (s) + ⟩ + α (s) n,j,-⟨q (s) n,i , k (s) -⟩ + N n ′ =1 M l=2 α (s) n,j,n ′ ,l ⟨q (s) n,i , k (s) n ′ ,l ⟩ + α (s) n,i,+ k (s) + + α (s) n,i,-k (s) -+ N n ′ =1 M l=2 α (s) n,i,n ′ ,l k (s) n ′ ,l • α (s) n,j,+ k (s)⊤ + + α (s) n,j,-k (s)⊤ - + N n ′ =1 M l=2 α (s) n,j,n ′ ,l k (s)⊤ n ′ ,l ≤ |⟨q (T1) n,i , q (T1) n,j ⟩| + t s=T1 |α (s) n,i,+ ||⟨q (s) n,j , k (s) + ⟩| + t s=T1 |α (s) n,i,-||⟨q (s) n,j , k (s) -⟩| + M l=2 t s=T1 |α (s) n,i,n,l ||⟨q (s) n,j , k (s) n,l ⟩| + M l=2 t s=T1 |α (s) n,i,n,l ||⟨q (s) n,j , k (s) n,l ⟩| + n ′ ̸ =n∧n ′ ̸ =n M l=2 t s=T1 |α (s) n,i,n ′ ,l ||⟨q (s) n,j , k (s) n ′ ,l ⟩| + t s=T1 |α (s) n,j,+ ||⟨q (s) n,i , k (s) + ⟩| + t s=T1 |α (s) n,j,-||⟨q (s) n,i , k (s) -⟩| + M l=2 t s=T1 |α (s) n,j,n,l ||⟨q (s) n,i , k (s) n,l ⟩| + M l=2 t s=T1 |α (s) n,j,n,l ||⟨q (s) n,i , k (s) n,l ⟩| + n ′ ̸ =n∧n ′ ̸ =n M l=2 t s=T1 |α (s) n,j,n ′ ,l ||⟨q (s) n,i , k (s) n ′ ,l ⟩| + {lower order term} = |⟨q (T1) n,i , q (T1) n,j ⟩| + O d -1 4 h • log(d 1 2 h ) + M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • log(d 1 2 h ) + M • O d -1 4 h • o(1) + N • M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • o(1) = |⟨q (T1) n,i , q (T1) n,j ⟩| + O d -1 4 h log(d 1 2 h ) + o N d -1 2 d -1 4 h log(6N 2 M 2 /δ) = o(1) for i, j ∈ [M ]\{1}, n, n ∈ [N ], n ̸ = n.The first inequality is triangle inequality, the second inequality is by (205), the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 and d = Ω ϵ -2 N 2 d h . |⟨k (t+1) + , k (t+1) - ⟩| ≤ |⟨k (T1) + , k (T1) -⟩| + t s=T1 ⟨k (s+1) + , k (s+1) - ⟩ -⟨k (s) + , k (s) -⟩ ≤ |⟨k (T1) + , k (T1) -⟩| + t s=T1 β (s) +,+ ⟨q (s) + , k (s) -⟩ + n∈S+ M i=2 β (s) n,+,i ⟨q (s) n,i , k (s) -⟩ + β (s) -,-⟨q (s) -, k (s) + ⟩ + n∈S- M i=2 β (s) n,-,i ⟨q (s) n,i , k (s) + ⟩ + β (s) +,+ q (s) + + n∈S+ M i=2 β (s) n,+,i q (s) n,i • β (s) -,-q (s)⊤ - + n∈S- M i=2 β (s) n,-,i q (s)⊤ n,i ≤ |⟨k (T1) + , k (T1) -⟩| 134 + t s=T1 |β (s) +,+ ||⟨q (s) + , k (s) -⟩| + n∈S+ M i=2 t s=T1 |β (s) n,+,i ||⟨q (s) n,i , k (s) -⟩| + t s=T1 |β (s) -,-||⟨q (s) -, k (s) + ⟩| + n∈S- M i=2 t s=T1 |β (s) n,-,i ||⟨q (s) n,i , k (s) + ⟩| + {lower order term} = |⟨k (T1) + , k (T1) -⟩| + O N 1 2 d -1 4 h • log(d 1 2 h ) + N • M • O SNR • N -1 2 d -1 4 h • log(d 1 2 h ) = |⟨k (T1) + , k (T1) -⟩| + O SNR • N 1 2 d -1 4 h log(d 1 2 h ) = o(1),where the first inequality is triangle inequality, the second inequality is by ( 214), the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . |⟨k (t+1) + , k (t+1) n,i ⟩| ≤ |⟨k (T1) + , k (T1) n,i ⟩| + t s=T1 ⟨k (s+1) + , k (s+1) n,i ⟩ -⟨k (s) + , k (s) n,i ⟩ ≤ |⟨k (T1) + , k (T1) n,i ⟩| + t s=T1 β (s) +,+ ⟨q (s) + , k (s) n,i ⟩ + n ′ ∈S+ M l=2 β (s) n ′ ,+,l ⟨q (s) n ′ ,l , k (s) n,i ⟩ + β (s) n,i,+ ⟨q (s) + , k (s) + ⟩ + β (s) n,i,-⟨q (s) -, k (s) + ⟩ + N n ′ =1 M l=2 β (s) n,i,n ′ ,l ⟨q (s) n ′ ,l , k (s) + ⟩ + β (s) +,+ q (s) + + n ′ ∈S+ M l=2 β (s) n ′ ,+,l q (s) n ′ ,l • β (s) n,i,+ q (s)⊤ + + β (s) n,i,-q (s)⊤ - + N n ′ =1 M l=2 β (s) n,i,n ′ ,l q (s)⊤ n ′ ,l ≤ |⟨k (T1) + , k (T1) n,i ⟩| + t s=T1 |β (s) +,+ ||⟨q (s) + , k (s) n,i ⟩| + M l=2 t s=T1 |β (s) n,+,l ||⟨q (s) n,l , k (s) n,i ⟩| + n ′ ∈S+∧n ′ ̸ =n M l=2 t s=T1 |β (s) n ′ ,+,l ||⟨q (s) n ′ ,l , k (s) n,i ⟩| + t s=T1 |β (s) n,i,+ ||⟨q (s) + , k (s) + ⟩| + t s=T1 |β (s) n,i,-||⟨q (s) -, k (s) + ⟩| + M l=2 t s=T1 |β (s) n,i,n,l ||⟨q (s) n,l , k (s) + ⟩| + N n ′ ̸ =n M l=2 t s=T1 |β (s) n,i,n ′ ,l ||⟨q (s) n ′ ,l , k (s) + ⟩| + {lower order term} = |⟨k (T1) + , k (T1) n,i ⟩| + O N 1 2 d -1 4 h • log(d 1 2 h ) + M • O SNR • N -1 2 d -1 4 h • log(d 1 2 h ) + N • M • O SNR • N -1 2 d -1 4 h • o(1) + O N 1 2 d -1 4 h • log(d 1 2 h ) 135 + M • O d -1 4 h • log(d 1 2 h ) + N • M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • log(d 1 2 h ) = |⟨k (T1) + , k (T1) n,i ⟩| + o SNR • N 1 2 d -1 4 h + O N 1 2 d -1 4 h log(d 1 2 h ) + O N d -1 2 d -1 4 h log(6N 2 M 2 /δ) • log(d 1 2 h ) = o(1)where the first inequality is triangle inequality, the second inequality is by ( 209), the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 and d = Ω ϵ -2 N 2 d h . Similarly, we have |⟨k (t+1) - , k (t+1) n,i ⟩| = o(1). |⟨k (t+1) n,i , k (t+1) n,j ⟩| ≤ |⟨k (T1) n,i , k (T1) n,j ⟩| + t s=T1 ⟨k (s+1) n,i , k (s+1) n,j ⟩ -⟨k (s) n,i , k (s) n,j ⟩ ≤ |⟨k (T1) n,i , k (T1) n,j ⟩| + t s=T1 β (s) n,i,+ ⟨q (s) + , k (s) n,j ⟩ + β (s) n,i,-⟨q (s) -, k (s) n,j ⟩ + N n ′ =1 M l=2 β (s) n,i,n ′ ,l ⟨q (s) n ′ ,l , k (s) n,j ⟩ + β (s) n,j,+ ⟨q (s) + , k (s) n,i ⟩ + β (s) n,j,-⟨q (s) -, k (s) n,i ⟩ + N n ′ =1 M l=2 β (s) n,j,n ′ ,l ⟨q (s) n ′ ,l , k (s) n,i ⟩ + β (s) n,i,+ q (s) + + β (s) n,i,-q (s) -+ N n ′ =1 M l=2 β (s) n,i,n ′ ,l q (s) n ′ ,l • β (s) n,j,+ q (s)⊤ + + β (s) n,j,-q (s)⊤ - + N n ′ =1 M l=2 β (s) n,j,n ′ ,l q (s)⊤ n ′ ,l ≤ |⟨k (T1) n,i , k (T1) n,j ⟩| + t s=T1 |β (s) n,i,+ ||⟨q (s) + , k (s) n,j ⟩| + t s=T1 |β (s) n,i,-||⟨q (s) -, k (s) n,j ⟩| + M l=2 t s=T1 |β (s) n,i,n,l ||⟨q (s) n,l , k (s) n,j ⟩| + N n ′ ̸ =n M l=2 t s=T1 |β (s) n,i,n ′ ,l ||⟨q (s) n ′ ,l , k (s) n,j ⟩| + t s=T1 |β (s) n,j,+ ||⟨q (s) + , k (s) n,i ⟩| + t s=T1 |β (s) n,j,-||⟨q (s) -, k (s) n,i ⟩| + M l=2 t s=T1 |β (s) n,j,n,l ||⟨q (s) n,l , k (s) n,i ⟩| + N n ′ ̸ =n M l=2 t s=T1 |β (s) n,j,n ′ ,l ||⟨q (s) n ′ ,l , k (s) n,i ⟩| + {lower order term} = |⟨k (T1) n,i , k (T1) n,j ⟩| + O N 1 2 d -1 4 h • log(d 1 2 h ) + M • O d -1 4 h • log(d 1 2 h ) + N • M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • o(1) = |⟨k (T1) n,i , k (T1) n,j ⟩| + O N 1 2 d -1 4 h log(d 1 2 h ) + o N d -1 2 d -1 4 h log(6N 2 M 2 /δ) = o(1) for i, j ∈ [M ]\{1}, i ̸ = j, n ∈ [N ]. The first inequality is triangle inequality, the second inequality is by (211), the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 and d = Ω ϵ -2 N 2 d h . |⟨k (t+1) n,i , k (t+1) n,j ⟩| ≤ |⟨k (T1) n,i , k (T1) n,j ⟩| + t s=T1 ⟨k (s+1) n,i , k (s+1) n,j ⟩ -⟨k (s) n,i , k (s) n,j ⟩ ≤ |⟨k (T1) n,i , k (T1) n,j ⟩| 136 + t s=T1 β (s) n,i,+ ⟨q (s) + , k (s) n,j ⟩ + β (s) n,i,-⟨q (s) -, k (s) n,j ⟩ + N n ′ =1 M l=2 β (s) n,i,n ′ ,l ⟨q (s) n ′ ,l , k (s) n,j ⟩ + β (s) n,j,+ ⟨q (s) + , k (s) n,i ⟩ + β (s) n,j,-⟨q (s) -, k (s) n,i ⟩ + N n ′ =1 M l=2 β (s) n,j,n ′ ,l ⟨q (s) n ′ ,l , k (s) n,i ⟩ + β (s) n,i,+ q (s) + + β (s) n,i,-q (s) -+ N n ′ =1 M l=2 β (s) n,i,n ′ ,l q (s) n ′ ,l • β (s) n,j,+ q (s)⊤ + + β (s) n,j,-q (s)⊤ - + N n ′ =1 M l=2 β (s) n,j,n ′ ,l q (s)⊤ n ′ ,l ≤ |⟨k (T1) n,i , k (T1) n,j ⟩| + t s=T1 |β (s) n,i,+ ||⟨q (s) + , k (s) n,j ⟩| + t s=T1 |β (s) n,i,-||⟨q (s) -, k (s) n,j ⟩| + M l=2 t s=T1 |β (s) n,i,n,l ||⟨q (s) n,l , k (s) n,j ⟩| + M l=2 t s=T1 |β (s) n,i,n,l ||⟨q (s) n,l , k (s) n,j ⟩| + n ′ ̸ =n∧n ′ n M l=2 t s=T1 |β (s) n,i,n ′ ,l ||⟨q (s) n ′ ,l , k (s) n,j ⟩| + t s=T1 |β (s) n,j,+ ||⟨q (s) + , k (s) n,i ⟩| + t s=T1 |β (s) n,j,-||⟨q (s) -, k (s) n,i ⟩| + M l=2 t s=T1 |β (s) n,j,n,l ||⟨q (s) n,l , k (s) n,i ⟩| + M l=2 t s=T1 |β (s) n,j,n,l ||⟨q (s) n,l , k (s) n,i ⟩| + n ′ ̸ =n∧n ′ n M l=2 t s=T1 |β (s) n,j,n ′ ,l ||⟨q (s) n ′ ,l , k (s) n,i ⟩| + {lower order term} = |⟨k (T1) n,i , k (T1) n,j ⟩| + O N 1 2 d -1 4 h • log(d 1 2 h ) + M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • log(d 1 2 h ) + M • O d -1 4 h • o(1) + N • M • O d -1 2 d -1 4 h log(6N 2 M 2 /δ) • o(1) = |⟨k (T1) n,i , k (T1) n,j ⟩| + O N 1 2 d -1 4 h log(d 1 2 h ) + o N d -1 2 d -1 4 h log(6N 2 M 2 /δ) = o(1) for i, j ∈ [M ]\{1}, n, n ∈ [N ], n ̸ = n.The first inequality is triangle inequality, the second inequality is by (212), the last equality is byd h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 and d = Ω ϵ -2 N 2 d h .F.9 Upper Bounds of ⟨ q, k ⟩ In order to give the upper bounds for ⟨q, k⟩ in stage III, we need to give the upper bounds of α and β based on the equations in F.1. The main difference between this subsection and F.6 is that the boundsof |V ± |, |V n,i | is log O( 1 ϵ ) in this subsection, while the bounds of |V ± |, |V n,i | is log O( 1 ϵ ) in F.6, resulting in different bounds for α and β. Now we take α (s) +,+ as an exampleEQUATION+ ⟩) exp(⟨qEQUATIONEQUATIONn,j ⟩),EQUATIONn,i,-≥ -EQUATIONn,i,n,j ≥ -EQUATIONn,j,n,i ≥ -EQUATIONn,j ⟩).Similar to F.5, we apply the bounds of α and β above to give the upper bounds for the dynamics ⟨q, k⟩.EQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONsimilarly, we haveEQUATIONn,j ⟩ -⟨qEQUATIONn,j ⟩ ≥ -EQUATIONn,j ⟩). ( 274)EQUATIONsimilarly, we haveEQUATIONEQUATIONn,j ⟩ -⟨qEQUATIONF.10 Bounds for the Sum of α and βAssume that the propositions F(T 2 ), . . . , F(s), H(T 2 ), . . . , H(s -1) hold (s ∈ [T 1 , t]), we haveEQUATIONEQUATIONEQUATIONΛ (s) n,i,±,j ≥ Λ (T2) n,i,±,j ≥ log exp(Λ (T1) n,i,±,j ) + Θ σ 2 p dd 1 2 h N ∥µ∥ 2 2 log(6N 2 M 2 /δ) 3 (281) for i, j ∈ [M ]\{1}, n ∈ [N ], s ∈ [T 2 , t].Similar to ( 64) and ( 65), we have exp(⟨qEQUATIONEQUATIONPlugging ( 282 EQUATION+ ⟩) exp(⟨qEQUATIONEQUATION+ , k+ ⟩) exp(⟨qEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere the last equality is by ∥w O ∥ = Θ(1). Similarly, we haveEQUATIONEQUATION) for i ∈ [M ]\{1}, n ∈ S ± . t s=T2 |α (s) n,+,i |, t s=T2 |α (s) n,-,i |, t s=T2 |α (s) n,i,+ |, t s=T2 |α (s) n,i,-|, t s=T2 |α (s) n,i,n,j |, t s=T2 |β (s) n,j,n,i | = O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h , (295) for i, j ∈ [M ]\{1}, n ∈ S ± . t s=T2 |α (s) n,i,n ′ ,j |, t s=T2 |β (s) n,j,n ′ ,i | = O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd 1 2 d 1 2 h (296) for i, j ∈ [M ]\{1}, n, n ′ ∈ [N ], n ̸ = n ′ .With these sums of α and β above, we can easily prove Claim 7 and Claim 8.In this subsection, we assume that I(T 2 ), . . . , I(t) hold, and then proof that G(t + 1) is true with the result of F.10.EQUATION+,+ ⟨q+ , k EQUATIONn,i ⟩| + {lower order term}= O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + N • M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) = O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 hwhere the first inequality is by triangle inequality, the second inequality is by 199, the third inequality is by t ≤ T 3 . Since σ 2 h ≥ max{σ 2 p d, ∥µ∥ + N • M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) 145 = |⟨q (T2) + , q (T2) -⟩| + O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 h = o(1),where the first inequality is triangle inequality, the second inequality is by (198) , the last equality is by d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . n,i ⟩| + O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + N • M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • o(1) + M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + N • M • O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd 1 2 d 1 2 h • log(ϵ -1 d 1 2 h ) = |⟨q (T2) + , q (T2) n,i ⟩| + O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 h + O N log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 d 1 2 h 146 = o(1),where the first inequality is triangle inequality, the second inequality is by (202), the last equality is by d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 and d = Ω ϵ -2 N 2 d h . Similarly, we have h ) ϵdn,i , q (T2) n,j ⟩| + O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + N • M • O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd 1 2 d 1 2 h • o(1) = |⟨q (T2) n,i , q (T2) n,j ⟩| + O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 h + o N log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵdn,i , q (T2) n,j ⟩| + O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + M • O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd 1 2 d 1 2 h • log(ϵ -1 d 1 2 h ) + M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • o(1) + N • M • O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd 1 2 d 1 2 h • o(1) = |⟨q (T2) n,i , q (T2) n,j ⟩| + O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 h + o N log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd1 2 h + O N • SNR 2 log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 h = o(1),where the first inequality is triangle inequality, the second inequality is by (214), the last equality is by d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . n,i ⟩| + O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + M • O SNR 2 log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + N • M • O SNR 2 log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • o(1) + O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + N • M • O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd 1 2 d 1 2 h • log(ϵ -1 d 1 2 h ) = |⟨k (T2) + , k (T2) n,i ⟩| + O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) log(ϵ -1 d 1 2 h ) ϵd 1 2 h + o N • SNR 2 log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h = o(1)where the first inequality is triangle inequality, the second inequality is by (209), the last equality is by d h = Ω max{SNR 4 , SNR -4 }N 2 ϵ -2 . Similarly, we have |⟨k + O N log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • log(ϵ -1 d 1 2 h ) + M • O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵd 1 2 d 1 2 h • log(ϵ -1 d 1 2 h ) + M • O log(6N 2 M 2 /δ) 3 log O( 1 ϵ ) ϵd 1 2 h • o(1) + N • M • O log(6N 2 M 2 /δ) 4 log O( 1 ϵ ) ϵdIn this section, we provide some explanations of lower order terms to demonstrate the rigor of our proof.To bound the so-call {lower order term}, we condition that dimensions d, d h are sufficiently large and learning rate η is sufficiently small. Next, we show how we utilize these three parameters.Sufficiently mall learning rate η : Recall the dynamics of QK ⟨q (t+1) , k (t+1) ⟩ -⟨q (t) , k (t) ⟩ = ⟨∆q (t) , k (t) ⟩ + ⟨q (t) , ∆k (t) ⟩ + ⟨∆q (t) , ∆k (t) ⟩ Note that terms ⟨∆q (t) , k (t) ⟩, ⟨q (t) , ∆k (t) ⟩ contain factor η, and term ⟨∆q (t) , ∆k (t) ⟩ contains factor η 2 . Therefore, as long as η is sufficiently small, ⟨∆q (t) , ∆k (t) ⟩ is sufficiently small than ⟨∆q (t) , k (t) ⟩ and ⟨q (t) , ∆k (t) ⟩. Now we take the dynamic of ⟨q (298)Data Augmentation: Researchers sometimes employ the technique of data augmentation by introducing controlled noise into their datasets. From the perspective of our paper's results, this method reduce SNR but improve N because we generate "new" data point by adding noises. As reducing SNR may be harmful to generalization performance, we must make sure that we use enough data points to train the model( enough sample size N ).Semi-Supervised Learning: Semi-supervised learning is useful when you have a small amount of labeled data and a large amount of unlabeled data. Labeled data can be seen as data with high SNR, while unlabeled data with low SNR because for some unlabeled samples, we may mistake their labels, making them equivalent to noises. In this scenario, we need to ensure that we have sufficient unlabeled data (enough sample size N ) and make full use of labeled data (high SNR data points).Overall, we need to consider both the sample size N and the signal-to-noise ratio SNR to train the model. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material.We use Ω(•) and O(•) to omit logarithmic terms in the notation.h ),h ) + ηC 4 ∥µ∥ 2(t -T 1 ) for i ∈ [M ]\{1}, n ∈ [N ].h log(6N 2 M 2 /δ)(59)d 1 2 h . (64)h ).h ) 


Decision: The reviewers unanimously agree that this paper should be accepted and presented at neurips, and the AC sees no reason to overturn this recommendation. However, as noted by the reviewer, there are two caveats:
1) Real experimental results are needed to empirically validate the derivations. The authors added MNIST experiments during the rebuttal, which need to be included in the final version of the paper.
2) The proofs are difficult to read, follow, and verify. It sounds like none of the reviewers, nor the AC, was able to fully follow and verify them. Hence, improved clarity is needed. However, we hope that the publication of this paper attracts further scrutiny by the community and leads to follow-up works.

Reviews: review: paper_summary: paper_summary: The paper studies the benign overfitting phenomenon for a two-layer Transformer in vision. The paper characterizes the optimization of the ViT through three different phases in training dynamics and finds a sharp separation condition of the signal-to-noise ratio to distinguish the benign and harmful overfitting of the ViT.
strength_weakness: strength_weakness: 1. Lack the introduction of the benign overfitting phenomenon in the first section.
2. It is better to clarify some notations like $\Omega(\cdot)$, $\Theta(\cdot)$, $\omega(\cdot)$...
3. Data generation is specified, thus this model may be a little bit limited.
4. A small typo: (Line 149) $\mu||_2^{-2}$ --> $||\mu||_2^{-2}$
questions: questions: In Theorem 4.1 and Theorem 4.2, the requirement is related to SNR. Why does $\tilde{\sigma}_p$ not occur in the requirement?
limitations: limitations: The authors have stated the limitations.
paper_summary: paper_summary: This study investigates the theoretical aspects of Vision Transformers (ViT) with a focus on their generalization capabilities, particularly under conditions of benign overfitting. Through a detailed analysis of the optimization process involving a self-attention layer and a fully connected layer, optimized using gradient descent on a specific data distribution modal, this work addresses the complexities introduced by softmax functions and the interdependencies of multiple weight configurations in transformer models. By developing novel techniques, the researchers delineate the training dynamics that lead to effective generalization in post-training scenarios. A key contribution is the establishment of a sharp condition based on the signal-to-noise ratio within the data, which predicts whether a small or large test error will occur. These theoretical findings are supported by experimental simulations, enhancing our understanding of transformers' performance in vision tasks.
strength_weakness: strength_weakness: The current experiments only validate the theoretical results on synthetic datasets. It is recommended that the authors consider adding some experiments on real datasets to test the effects, such as experiments on benign overfitting of the ViT model on MNIST and CIFAR10.
questions: questions: See in Weaknesses.
limitations: limitations: N/A
paper_summary: paper_summary: The paper investigates **the benign overfitting phenomenon in Vision Transformers**. The authors adopt a theoretical framework similar to that proposed by Cao et al. (2022), which use **a data model consisting of label-dependent signal and label-independent noise**, but employ **a two-layer Transformer architecture** instead of a two-layer convolutional neural network. They provide conditions under which benign and harmful overfitting occur.
strength_weakness: strength_weakness: While I believe that the vectorized Q&K and scalarized V techniques are significant contributions, **it is difficult to verify the correctness of the proofs** due to readability issues in both the main text and the appendix. I suggest that the authors **improve the clarity and writing of their technical terms and proofs**.

Minors and Typos
* The notion of $\mu$ in Definition 3.1 seems unnecessary
* Line 9: modal→model
* Line 541: Eexperimantal Rresults → Experimental Results
questions: questions: * In the data distribution (Definition 3.1), what is **the role of the larger noise $\xi_2$ in the analysis**? What would happen if the data distribution were the same as that considered in Cao et al. (2022), which consists of a single signal patch and a single noise patch?
* In the numerical results section, it would be beneficial to compare the results with those for a two-layer convolutional neural network, as considered in Cao et al. (2022), to emphasize the advantages of the transformer architecture.

Reference

[1] Cao, Y., Chen,Z., Belkin,M., and Gu,Q. Benign over fitting in two-layer convolutional neural networks. In NeurIPS 2022
limitations: limitations: N/A
paper_summary: paper_summary: This paper provides a sharp theoretical characterization of the transition between benign and harmful overfitting regimes for Vision Transformers trained on linearly separable data. The authors carefully analyze the optimization dynamics and provide generalization bounds that depend on the signal-to-noise ratio of the data. Extensive experiments validate the theory.
strength_weakness: strength_weakness: * Only considers the linearly separable setting, which is already solvable by existing vision and language models, so the conclusions are not very surprising even if initialization and model details differ
* Lacks clear takeaways for practitioners - how can these theoretical insights be used to improve real-world vision models?
* Could the authors provide a more rigorous perspective on transformer bias (e.g. low rank structure) from an optimization perspective under their model?
questions: questions: * If an MLP with ReLU activation was used instead of the simple linearly separable task, would the optimization dynamics converge faster or slower? Would the SNR requirements be stricter or more relaxed?
* What guidance can the authors provide to practitioners based on these theoretical results?
limitations: limitations: The authors acknowledge focusing only on the simplified linearly separable setting. More discussion on how the insights could extend to real-world nonlinear problems would be valuable.
paper_summary: paper_summary: The paper investigates the benign overfitting phenomenon in Vision Transformers. By examining the training dynamics and generalization of a two-layer Transformer model, it establishes a condition to differentiate between benign and harmful overfitting based on the signal-to-noise ratio in the data model. Theoretical results are supported by experimental simulations.
strength_weakness: strength_weakness: 1. The sparsity assumption is too strong, as it relies on the signal being contained within one patch and the noise being contained within another, which may not align with real-world data distributions.
2. Experiments are limited to settings that perfectly align with theoretical assumptions. The paper should also explore scenarios that deviate from these assumptions to understand the limitations of the theoretical results.
questions: questions: The authors are suggested to explore scenarios that deviate from these assumptions to understand the limitations of the theoretical results. For example, more signal patches and more noise patches are contained in all patches. Tests on real-world tasks are better.
limitations: limitations: See Questions and Weaknesses.

Comments: comment: It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.
It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.
It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.
It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.
Thank you for your response and for acknowledging that our response adequately addressed your questions. We appreciate your constructive comments and suggestions.

We will consider your suggestion and try to improve the readability of the overall technical components, including the appendix, in the next version of our manuscript. We will ensuring that our paper is as clear and accessible as possible, and we will carefully review and revise the text to enhance its clarity and coherence.

Once again, thank you for your valuable input. It has been instrumental in helping us improve our work.
Thank you for the authors' response. It adequately addresses my questions. I hope the readability of the overall technical components, including the appendix, will be improved in the next version based on the points discussed in your response.