Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyond

Introduction

Attention-based architectures, particularly Transformers, have revolutionized artificial intelligence. Large language models such as Llama , Claude-3 , GPT-4 , and et al. have significantly transformed the AI landscape. Besides, vision models like Vision Transformer(ViT) and Data-efficient Image Transformer(DeiT) have revolutionized the visual domain by directly processing image patches, bypassing the limitations of traditional Convolutional Neural Networks (CNNs). These models demonstrate outstanding performance in fields of natural language processing and computer vision, driving advancements across diverse fields, including content creation , software development , multimodal application , machine translation etc.

Time series prediction tasks are crucial for forecasting future trends and have been widely used in making data-driven decisions in various fields, such as finance , healthcare and traffic flow forecasting . In addition to their success in NLP, Transformer models have recently gained significant attention in time series prediction tasks. The ability of Transformers to capture involuted patterns and model long-range dependencies has led to their growing adoption in time series prediction tasks, with several recent studies . These models utilize self-attention mechanisms to focus on relevant time steps, which makes them particularly well-suited for handling time series data with irregular intervals and high dimensions. Furthermore, some transformer-based methods integrate techniques such as temporal fusion , hierarchical attention , and patching process etc., allowing them to better capture multi-scale temporal dependencies and adapt to non-stationary patterns in time series.

However, recent studies have challenged the performance of Transformers in time series prediction tasks. Some researchers have found that simple linear layers can outperform more complex Transformers in terms of both accuracy and efficiency . Many works have provided explanations for why Transformer performs worse than simple linear layers on TSF tasks. argue that the poor performance of Transformer on TSF tasks stems from its permutation-invariant self-attention mechanism, which results in the loss of temporal information. and attribute the issue to the Transformer’s practice of embedding multiple variables into indistinguishable channels, leading to a loss of both variable independence and multivariate correlations. However, there is a lack of theoretical understanding regarding why transformers often perform worse than simple linear models in time series forecasting tasks. To address this gap, we present the first theoretical analysis of this issue, shedding light on the underlying factors contributing to the performance discrepancy.

To demystify the black box, we conducted the following analysis: First, we utilized data generated by the State Space Model (SSM) to model time series data. This approach builds on the work in , which demonstrated the SSM’s robust modeling capabilities for sequential data. Notably, based on our observation that the linear residual network (N-Linear) performs well in fitting sequential data, we designed a simple task. In this task, the model only needs to apply a straightforward linear mapping to the core features of the time series, which results in relatively small errors.

For the sake of subsequent theoretical analysis, we consider an over-parameterized attention network with a $d=1$ in our setting where d denotes the input feature dimension, i.e.,

where $m$ is the hidden neurons number, $a$ and $w$ are the output and hidden layer weights respectively and $x$ is the input data. Our theoretical analysis shows that the training method for next-token prediction induces asymmetric feature updates during gradient descent. Specifically, the parameter $w_{r}$ will be updated in the direction of the parameter $a_{r}$. By connecting our setup with vanilla Attention, the above conclusion means that the weights of $W_{Q}$ and $W_{K}$ will be updated in the direction of $W_{V}$. Our results show that in the case of $d=1$, such asymmetric learning is detrimental to the generalization of sequential data. Then, we introduce inconsistent next-step prediction. Specifically, because $w_{r}$ updates along the direction of $a_{r}$, when the model overfits and $a_{r}=-1$, $w_{r}$ becomes negative, leading to very small weights for the final timestep feature after applying Softmax. This makes it difficult for the model to learn residual features effectively.

Besides, we further propose a theoretical insight: linear models can exhibit exceptional performance on the task in generalization on SSM sequence data. In contrast, no matter how over-parameterized the attention mechanism is, how large the dataset is, or how long the training time is, it will fail to generalize on SSM sequence data.

Our main contributions can be outlined as follows:

We demonstrate that asymmetric learning in transformer-based models is the root cause of their underperformance in time series forecasting. Specifically, when the sign of the previous step conflicts with the current step in next-step prediction, the attention mechanism fails to effectively learn residual features, which limits the model’s ability to generalize on out-of-distribution (OOD) data.

We provide a theoretical analysis showing that linear residual models outperform transformers in generalizing to sequential data, as even over-parameterized attention networks fail to match the generalization capability of simple linear models.

Related Work

Time Series Forecasting (TSF) is a classical task of predicting future values based on historical data, widely used in finance, weather, traffic, and healthcare. Traditional methods like ARIMA and ETS have been reliable due to their solid theoretical foundations, but they are limited by assumptions such as stability and linearity, affecting real-world accuracy. In recent years, the rapid development of deep learning (DL) has greatly improved the nonlinear modeling capabilities of time series forecasting (TSF) methods. For example, Liu et al. utilize LSTM for multi-step forecasting in time series tasks and demonstrate that its performance outperforms traditional models. Li et al. present a bidirectional VAE with diffusion, denoise, and disentanglement, improving time series forecasting by augmenting data and enhancing interpretability, outperforming competitive methods in experiments. With Transformer’s outstanding performance in NLP and CV, it has quickly been applied to time series forecasting tasks, demonstrating superior performance compared to traditional methods. Notable works include Informer , Autoformer , FEDformer , PatchTST , Pyraformer , iTransformer etc.

Neural Tangent Kernel.

The Neural Tangent Kernel (NTK) was initially proposed by Jacot et al. to provide a framework for understanding over-parameterized neural network training behavior. This work showed that, under specific conditions, deep neural network training can be approximated by a linear model, with the NTK governing parameter evolution during gradient descent. Since its introduction, NTK has become a key tool for analyzing training in over-parameterized models. Building on this work, many studies have focused on generalizing the NTK theory to various network architectures at over-parameterization, such as . It has been demonstrated that Gradient Descent can effectively train a sufficiently wide neural network and will converge in polynomial time. The NTK technique has gained widespread application in various contexts, including pre-processing analysis , LoRA adaptation for LLM , federated learning , and estimating scoring functions in diffusion models .

Theory for Understanding Attention Mechanism.

The attention has become a cornerstone in AI, particularly in large language models (LLMs), which excel in NLP tasks such as machine translation, text generation, and sentiment analysis due to their ability to capture complex contextual relationships. However, understanding the attention mechanism from a theoretical perspective remains an ongoing challenge. Several works have explored the theoretical foundations and computational complexities of attention , focusing on areas such as efficient attention , optimization , and the analysis of emergent abilities . Notably, introduced an algorithm with provable guarantees for attention approximation, proved a lower bound for attention computation based on the Strong Exponential Time Hypothesis, and provided both an algorithm and hardness results for static attention computation.

Background: Transformer Fails to Beat Linear Model in TSF

As a crucial research direction for data science and statistics, time series forecasting (TSF) tasks have played an important role in various domains, including finance analysis, health care, energy management, etc. In recent years, with the outstanding performance of Transformers in the field of Computer Vision (CV) and Natural Language Process (NLP), many studies have applied the Transformer architecture to time series forecasting tasks . The primary reason for introducing Transformer-based methods into TSF tasks is their attention mechanism, which effectively models long-range dependencies in the time domain. For instance, Informer introduces the ProbSparse self-attention mechanism and self-attention distilling techniques, enabling Transformer-based methods to handle long sequence time-series forecasting (LSTF) efficiently; FEDformer introduces seasonal-trend decomposition and frequency enhancing techniques, enabling the model to capture global time-series trends; Crossformer introduces the Dimension-Segment-Wise embedding and Two-Stage Attention techniques, enabling Transformer-based models to efficiently capture both cross-time and cross-dimension dependencies for multivariate time series forecasting, etc.

However, it is still debated whether Transformer-based models are more efficient than other deep learning models for time series tasks. The suitability of Transformer-based models for long-term time series forecasting tasks is questioned in . The authors highlight that although these models are effective at capturing semantic correlations, their permutation-invariant self-attention mechanism causes a loss of temporal information. To support this, they introduce a one-layer linear model, LSTF-Linear, which outperforms advanced Transformer-based LTSF models across several TSF Benchmarks. They also suggest revisiting the effectiveness of Transformer-based approaches for TSF tasks. Recently, introduced a novel frequency-domain MLP approach for TSF. By utilizing a global perspective and energy compaction in the frequency domain, this MLP-based method surpasses Transformer-based models, delivering exceptional performance in both short-term and long-term forecasting scenarios. Furthermore, we present the experimental results of existing work on prediction performance on the benchmark datasets ETTh1 and ETTh2, as shown in Figure 1 (a). The data indicates that, despite Transformer-based methods having model parameters 1000 times larger than those of simple linear models, their prediction performance on time series data remains significantly inferior to that of the linear models. This discrepancy raises questions about the effectiveness of such large-scale models in time series forecasting tasks.

Therefore, why vanilla transformers are not efficient for time series prediction tasks has become a hotly debated issue recently. A lot of work has shed light on this question: proposed that permutation-invariant self-attention mechanism may lead to the loss of temporal information. After that, highlights that Transformers in time-series forecasting suffer from overfitting due to their data-dependent attention mechanisms. In contrast, linear models with fixed time-step-dependent weights effectively capture temporal patterns and demonstrate better generalization on datasets with strong temporal dependencies. highlighted the inefficiencies of vanilla Transformer models in time series forecasting, arguing that embedding multiple variables of the same timestamp into a single token results in the loss of crucial multivariate correlations, which hinders the model’s ability to capture variable interactions. The token formed at a single time step may fail to capture useful information due to its limited receptive field and the misalignment of events occurring at the same time.

However, the lack of a theoretical explanation behind why the vanilla Transformer model is less efficient than simple linear models in time series tasks remains unexplained. In our paper, we use the NTK framework to analyze and provide a theoretical explanation for the underlying cause of this issue.

Preliminary: Problem Definition

We present our formal problem definition in this section. In Section 4.1, we introduce the task within our framework, the Residual State Space Model (SSM), and describe how we use the Residual SSM to generate training data. In Section 4.2, we introduce our two-layer attention model and its training details.

In recent years, State Space Models (SSM) have been widely applied in various fields, particularly in time series analysis, computer vision, and machine learning. Specifically, offered a simple mathematical explanation for S4’s ability to model long-range dependencies and demonstrated the strong performance of S4 and its various variants on benchmark tasks. This also indicates that state space models can represent almost all known time series data. To formalize this, in this work, we assume that our training data and testing data are generated by a residual state space model defined as follows.

The state space model is defined as follows:

For $k\in[d]$, the state space model is given by:

And we have the following claim about Residual SSM for generating data:

Besides, by choosing some appropriate value for ${\cal A},{\cal B}$ and ${\cal C}$, we can show that for a certain $\gamma<1$, we have:

Property 3. We especially consider $d_{0}=1$.

With the above definitions, we introduce our data generation model as follows:

Let the residual state space model be defined as Definition 4.1, then we define the data generator, for $i\in[n]$:

Sample $\xi_{i}\sim\mathcal{N}(0,\sigma\cdot I_{d+1})$ where $\sigma\geq 0$ is a small constant.

2 Model and Training.

In this section, we state our model setting and details of its training.

Model. In this paper, we consider a two-layer attention model:

where $w$ and $a$ denote hidden-layer weights and output-layer weights, respectively. Then, we use gradient descent (GD) to update the trainable weights $w(t)$ with a fixed learning rate $\eta>0$. Then for $t>0$, we have

where $\eta$ denotes the fixed learning rate in the training process.

Training Convergence with Asymmetric Learning

In this section, we present the analysis of training convergence with asymmetric learning. In Section 5.1, we will present the key tools we used: the Neural Tangent Kernel (NTK) induced by our model, Kernel Convergence, which is key needed for the NTK analysis, assumptions on NTK, and the associated assumptions. In section 5.2, we present the main result of our paper, which provides a convergence guarantee for asymmetric learning within our framework.

Then, we define the kernel matrix $H(t)$ as an $n\times n$ Gram matrix, and the $(i,j)$-th entry of the block is

Here, we introduce the assumption of NTK, which is widely used in literature.

Assumption on NTK. In the NTK analysis framework for the convergence of training neural networks, one widely used and mild assumption is that $H^{*}:=H(0)$ is a positive definite (PD) matrix, i.e., its minimum eigenvalue $\lambda:=\lambda_{\min}(H^{*})>0$. With this, the theorem of training convergence with Asymmetric Learning is presented as follows.

Next, we introduce the convergence property of the kernel, which is key for the NTK analysis and is formalized below (details in Section F).

For $\delta\in(0,0.1)$, $B=\max\{1,$ $\sqrt{(1+\sigma^{2})\log(nN/\delta)}\}$ and $D=\max\{\sqrt{\log(m/\delta)},1\}$. For any $r\in[m]$, we have $|w_{r}(t)-w_{r}(0)|\leq R$ and let $R\leq\frac{\lambda}{n\operatorname{poly}(\exp(B^{2}),\exp(D)}$ . Then with probability at least $1-\delta$, we have $\|H(t)-H(0)\|_{F}\leq O(nR)\cdot\exp(O(B^{2}D))$ and $\lambda_{\rm min}(H(t))\geq\lambda/2$.

For Part 1, we first decompose $|H_{i,j}(t)-H_{i,j}(0)|$ into the sum of four subparts using the triangle inequality. Then, we apply the inequality proven in Lemma K.3 to the upper bound for each part. Then, using the definition of the Frobenius norm, we prove that $\|H(t)-H(0)\|_{F}\leq O(nR)\cdot\exp(O(B^{2}D))$. For Part 2, we can easily get the result by taking the appropriate value of $R$ and Fact B.7. Please see Lemma F.4 for the detailed proof of Lemma 5.1. ∎

2 Training Convergence with Asymmetric Learning

Now, we are able to present our first theorem regarding the convergence of training with Asymmetric Learning:

Given an error $\epsilon>0$. For $\delta\in(0,0.1)$, $B=\max\{\sqrt{(1+\sigma^{2})\log(nN/\delta)},1\}$ and $D=\max\{\sqrt{\log(m/\delta)},1\}$. Let $m=\Omega(\operatorname{poly}(\lambda^{-1},\exp(B^{2}),\exp(D)),n,d)$ and the learning rate $\eta\leq O(\frac{\lambda\delta}{\operatorname{poly}(\exp(B^{2}),\exp(D)),n,d)})$. Let $T\geq\Omega(\frac{1}{\eta\lambda}\log(nB^{2}/\epsilon)$, we have: $L(T)\leq\epsilon$.

Denote $v_{\min}:=\min\{\frac{1}{d}\sum_{k=1}^{d}(x_{i,k}-\overline{x}_{i})^{2}\}_{i=1}^{n}$ where $\overline{x}_{i}:=\frac{1}{d}\sum_{k=1}^{d}x_{i,k}$. The Asymmetric Learning of model weights is expressed by $w_{r}(t)$ updating with $a_{r}$ as formulated below, for any $t\geq\Omega(\frac{m}{\eta\lambda v_{\rm min}})$:

Part 1. $\Pr[w_{r}(t)>0|a_{r}=1]\geq 1-\delta$.

Part 2. $\Pr[w_{r}(t)<0|a_{r}=-1]\geq 1-\delta$.

Four the upper bound of $L(T)$, we can get the result by combing the result of Part 2 of Lemma H.4, Part 1 of Lemma H.1 and taking the appropriate value of $m,\eta,T$. For the analysis of asymmetric learning, we can get the result by combing the result of Lemma I.3 and taking the appropriate value of $m,\eta,T$. Please see Lemma I.1 for the detailed proof of Lemma 5.2. ∎

Let all pre-conditions in Theorem I.1 hold.For any Gaussian vector $x\sim\mathcal{N}(0,{\sigma^{\prime}}^{2}\cdot I_{d})$. For all $r\in[m]$ that satisfies $a_{r}=-1$, with a probability at least $1-\delta$, we have:

Please see Lemma I.2 for the proof details of this theorem.

Attention Fails in Sign-Inconsistent Next-step-prediction

In this section, we define the sign-inconsistent next-step-prediction evaluation task and provide a theoretical analysis of the attention mechanism and residual linear model based on this task. Specifically, we introduce this task in Section 6.1. We present the Residual Linear Network in Section 6.2. In Section 6.3, we give each model a theoretical boundary on this task.

In this section, we present a new task named Sign-Inconsistent Next-step-prediction. In subsequent sections, we will analyze the theoretical capabilities of the attention mechanism for this task. We define the task formally as follows:

Let the residual state space data model be defined as Definition 4.1, then we define the sign-inconsistent next-step-prediction evaluation task, considering $d=N$:

If $u_{{\rm test},i,d}\cdot u_{{\rm test},i,d+1}\geq 0$, redo 1.

Sample $\xi_{{\rm test},i}\sim\mathcal{N}(0,\sigma\cdot I_{d+1})$ where $\sigma\geq 0$ is a small constant.

2 Residual Linear Network

In this section, we present residual linear network mainly to compare it with the attention mechanism on the Sign-Inconsistent next-step-prediction evaluation task. Specifically, the residual linear network first subtracts the last value of the sequence from the sequence from the input data. This operation removes certain biases or trends in the data, aiming to eliminate unnecessary components that might negatively impact prediction accuracy. Then, the data is passed through a linear layer. This layer can apply more intricate transformations to capture the underlying linear patterns within the data. Finally, the subtracted part will be added back. The purpose of this step is to retain the original characteristics of the data after removing some of the shifts while still benefiting from the transformations applied. The formal definition of the residual linear network is as follows:

3 Generalizations

In this section, We provide a proposition demonstrating the bound on the OOD risk of the residual linear network and attention mechanisms for the Sign-Inconsistent next-step-prediction evaluation task.

Part 2. There exists and exists only one $w_{\rm lin}^{*}$ that satisfies $\sum_{k=1}^{d-1}w_{{\rm lin},k}^{*}\cdot{\cal P}_{k}={\cal P}_{d+1}-{\cal P}_{d}$. Hence, we have ${\cal R}(f_{\rm lin})\leq\widetilde{O}(\sigma^{2})$.

Please see Proposition J.3 for the detailed proof of this proposition.

Remark. Part 1 of Proposition 6.3 shows that even if the width of the hidden layers is sufficient, and the model is trained for a long enough time, the attention mechanism fails to reduce the OOD risk to a sufficiently low level in this task. In contrast, Part 2 shows that a set of parameters exists for the residual linear model that can reduce the OOD risk to the same bound in this task. In conclusion, we theoretically prove that the attention mechanism performs worse than a simple residual linear model on OOD generalization tasks. This proof provides insight into why Transformers underperform on TSF tasks compared to simple linear models.

Conclusion

In this work, we give the first theoretical explanation of the learning mechanism behind the transformer-based models’ inefficient performance on TSF tasks. We focus on the attention network to predict next-step in the time series, whereas we find that the value of output-layer $a_{r}$ (value projection in attention network) will lead the asymmetric learning to the hidden-weights $w_{r}$, and it further leads the softmax scores on some important features unavoidably being low value. That is, attention fails to learn the most common behavior in TSF tasks, residual feature (a.k.a differential feature). We hope our theoretical confirmation could provide more constructive insights for practitioners to design and improve more efficient transformer-based architecture for the field of time series.

References

Appendix A Notations

We denote the Gaussian distribution with mean $\mu$ and covariance $\Sigma$ as ${\cal N}(\mu,\Sigma).$ For any positive integer $n$, we denote the set $\{1,2,...,n\}$ as $[n]$.

Appendix B Probability Tools and Facts

Firstly, we present Hoeffding bound lemma as in .

Then, we present some useful facts which will be used in our paper.

For a variable $X\sim\mathcal{N}(0,\sigma^{2})$, with probability at least $1-\delta$, we have:

For $x\in(-0.01,0.01)$, the following approximation holds

We define $\overline{x}:=\frac{1}{d}\sum_{k=1}^{d}x_{k}$, $v_{x}:=\frac{1}{d}\sum_{k=1}^{d}(x-\overline{x})^{2}$. There exists a small constant $c>0$ such that:

For $x\in(0,1)$, integer $t\geq 0$, we have:

Appendix C Data

The state space model is defined as follows:

For $k\in[d]$, the state space model is given by:

Besides, by choosing some appropriate value for ${\cal A},{\cal B}$ and ${\cal C}$, we can show that for a certain $\gamma<1$, we have:

Property 4. We especially consider $d_{0}=1$.

Above, the first equation is trivially from Definition C.1. The 2nd equation is based on simple algebras and the definition of ${\cal P}_{k},\forall k\in[d]$. ∎

C.2 ID Data Generator

We define the residual state space model as specified in Definition C.1. Then, we are able to define the data generator for $i\in[n]$:

Sample $h_{i,1}\sim\mathcal{N}(0,I_{N})$.

Sample $\xi_{i}\sim\mathcal{N}(0,\sigma\cdot I_{d+1})$ where $\sigma\geq 0$ is a small constant.

C.3 OOD Sign-Inconsistent Next-step-prediction Task

Let the residual state space data model be defined in Definition C.1. Then we can define the sign-inconsistent next-step-prediction evaluation task:

If $u_{{\rm test},i,d}\cdot u_{{\rm test},i,d+1}\geq 0$, redo 1.

Sample $\xi_{{\rm test},i}\sim\mathcal{N}(0,\sigma\cdot I_{d+1})$ where $\sigma\geq 0$ is a small constant.

Appendix D Problem Setup

D.2 Model

D.3 Training

Assuming the following conditions are satisfied:

Define $L(t)$ be specified in Definition D.4.

D.4 Evaluation

Assuming we have the following conditions:

D.5 Assumption 1: Zero Initialization on Training Data

Assuming the following conditions are satisfied:

Appendix E Gradient Descent

Now, We define ${\sf u}_{i,r}(t)$ as the following:

E.2 Gradient Computations

Proof of Part 1. Consider the following reasoning:

where the first equation is due to simple differential rules, and the second step is trivially from Definition E.1.

where the first equation is due to Definition E.2, and the second step is because of part 1 of this lemma.

where is a result of applying the chain rule, the second step is derived from Part 2 of this Lemma, the third step is a consequence of basic algebraic manipulation, and the last step follows from Definition E.3.

where the first step is based on Definition E.3, the second step is derived using basic differentiation rules, the third step is based on Part 1 and 3, and the last two result from straightforward algebraic manipulation.

where the first step is a consequence of Definition E.4, the second step is derived from Part 4 of this lemma, and the third and last steps result from basic algebraic operations.

where the first step is based on Definition D.4, while the second step is derived from Part 5 of this Lemma. ∎

Appendix F Neural Tangent Kernel

Assuming the following conditions are satisfied:

F.2 Assumption 2: NTK is PD

Assuming the following conditions are satisfied:

We assume that $H^{*}$ (defined in Definition F.2) is positive definite, with its smallest eigenvalue, denoted as $\lambda:=\lambda_{\rm min}(H^{)}$, being greater than .

F.3 Kernel Convergence and PD Property during Training

Assuming the following conditions are satisfied:

We define $R:=\max_{t\geq 0}\max_{r\in[m]}|w_{r}(t)-w_{r}(0)|.$

Let $R\leq\frac{\lambda}{n\operatorname{poly}(\exp(B^{2}),\exp(D))}$.

Thus, with probability at least $1-\delta$, the following holds:

Above the first equation is a consequence of Definition F.1 and Definition F.2, and the 2nd step can be obtained by applying the triangle inequality.

Before we bound all terms, we first provide some tools:

Then we are able to bound $U_{1,i,j,r},U_{2,i,j,r},U_{3,i,j,r}$ and $U_{4,i,j,r}$.

where the first and second steps are based on basic algebraic manipulations, the third step is a consequence of the Cauchy inequality, the fourth step can be trivially obtained by applying the triangle inequality, the 5th step is a consequence of Eq. (3), (F.3), (F.3) and (F.3), and the final step results from basic algebraic manipulation.

where the first and second step are based on basic algebraic manipulations, the 3rd step is a consequence of the Cauchy inequality and triangle inequality, the 4th step is due to triangle inequality, the fifth step follows from Eq. (2), (3), (F.3), (F.3) and (F.3), and the last step results from basic algebraic manipulations.

where the first two steps are based on basic algebraic manipulations, the third step is a consequence of triangle inequality, and the 4th step can be obtained by applying Cauchy inequality, the 5th step is a consequence of Eq. (3), (F.3), (F.3) and (F.3), and the final step results from basic algebraic manipulation.

where the first and second steps are the result of basic algebraic manipulations, the third step follows from triangle inequality, the fourth step is derived from Cauchy-Schwarz inequality nad triangle inequality, the fifth step is due to Eq. (2), (3), (F.3), (F.3) and (F.3) and the last step follows from basic algebraic manipulationsic manipulations.

where the 1st step is derived from Eq. (F.3), the 2nd step combines the result of Eq. (F.3), (F.3), (F.3) and (F.3), the third step is based on basic algebraic manipulations, the final step can be obtained from $R\in(0,0.01)$, $B\geq 1$ and then $O(\operatorname{poly}(B))\leq\exp(O(B))$.

this step results from Eq. (F.3) and the definition of Frobenius norm.

Above, the first inequality can be derived from Part 1 of this lemma, and the second inequality is a consequence of the choice value of $R$.

Above the first inequality is a consequence of Fact B.7. The second inequality can be trivially obtained from Eq. (F.3) and the final equation is based on $\lambda_{\rm min}(H^{*})=\lambda$. ∎

Appendix G Training Dynamic

Assuming the following conditions are satisfied:

Define $\eta>0$ as specified in Definition D.5.

Above, the first equation is derived from Definition E.1. Then the second equation follows from Definition D.5 and the third equation is a result of basic algebraic manipulations, the fourth step is because of Definition E.1, and the final step is based on the definition of $\beta_{i,r}(t)$.

Above, the first equation is derived from Definition E.2. And the second step follows from basic algebraic manipulations, the third step is a consequence of Eq. (G.1), the last step is due to basic algebraic manipulations.

where the first step is based on Definition E.3, the second step follows from basic algebraic manipulations, the third step comes from Definition E.3, the fourth step is derived from Eq. (G.1), the fifth step follows from Eq. (G.1).

where the first step is derived from Definition E.4, the second step is a consequence of Eq. (G.1), the third and fourth step follows from basic algebraic manipulations, the last step follows from defining:

Above, the first equation is based on Definition D.4, the second, third, and fourth steps are the result of basic algebraic manipulations, and the last step is due to the statement of lemma and defining:

G.2 Bounding C1C_{1}

Assuming the following conditions are satisfied:

Define $\eta>0$ as specified in Definition D.5.

where the first step is the definition of $C_{1}$, and the second step is derived from Definition F.1, the third step can be obtained from Part 2 of Lemma F.4, the last step is due to Definition D.4. ∎

G.3 Bounding C2C_{2}

Assuming the following conditions are satisfied:

Define $\mathsf{S}_{i,r}(t)$ as specified in Definition E.3.

Define $\mathsf{F}_{i}(t)$ as specified in Definition E.4.

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

Let $m\geq\Omega(\lambda^{-2}n^{7}d\cdot\exp(O(B^{2}D)))$.

Consequently, with probability at least $1-\delta$:

And we proceed to bound $\|\mathsf{F}(t)-y\|_{2}$, we have

where the first step is based on Definition D.4, the second step follows from Lemma H.2, and the third step and fourth step result from basic algebraic manipulations.

We can then use Hoeffding’s inequality (Lemma B.1) for the random variable

Above, the first inequality is derived from Hoeffding Inequality (Lemma B.1) and Eq. (G.3). The second inequality follows from basic algebraic manipulations.

Above, the first inequality combines the result of Eq. (G.3) and Eq. (G.3). The second step can be obtained from basic algebraic manipulations; the third step is due to $R\leq B$ and basic algebraic manipulations, and the fourth step leverages the inequality $\sqrt{\log(m/\delta)}\leq\sqrt{m}$ and $O(B)\leq\exp(O(B^{2}D))$,

G.4 Bounding C3C_{3}

Assuming the following conditions are satisfied:

Define $\mathsf{S}_{i,r}(t)$ as specified in Definition E.3.

Define $\mathsf{F}_{i}(t)$ as specified in Definition E.4.

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

Let $m\geq\Omega(\lambda^{-2}n^{7}d\cdot\exp(O(B^{2}D)))$.

Consequently, with probability at least $1-\delta$:

Firstly, we go to bound $|\langle S_{i,r}(t),(x_{i,d}\Delta w_{r}(t))^{2}\cdot x_{i}^{\circ 2}\rangle|$, we have

We can then use Hoeffding’s inequality (Lemma B.1) for the random variable

where the first step is derived from Eq. (G.4) and Lemma B.1, the second step is due to basic algebraic manipulations.

Above the first inequality is a combination result of Eq. (G.4) and Eq. (G.4). The second and third inequalities follow from basic algebraic manipulations. The fourth step is a consequence of $\eta<1$, $R\ll B$ and $\sqrt{\log(m/\delta)}\leq\sqrt{m}$, and the last step is based on the fact that $O(B)\leq\exp(O(B^{2}D))$.

G.5 Bounding C4C_{4}

Assuming the following conditions are satisfied:

Define $\mathsf{S}_{i,r}(t)$ as specified in Definition E.3.

Define $\mathsf{F}_{i}(t)$ as specified in Definition E.4.

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

Let $m\geq\Omega(\lambda^{-3}n^{5}d^{2}\cdot\exp(O(B^{2}D)))$.

Consequently, with probability at least $1-\delta$:

Firstly, we begin to bound $|\langle\mathsf{S}_{i,r}(t+1)-\mathsf{S}_{i,r}(t),x_{i}\rangle|$, and we have

Above, the first inequality is a result of using Cauchy inequality, and the second inequality combines the result of Part 1, 13 of Lemma K.3, the 3rd step is derived from basic algebraic manipulations and the last step is based on the fact that $O(B^{3})\leq\exp(O(B^{2}D))$.

Then we proceed to bound $\|x_{i,d}\cdot\eta\Delta w_{r}(t)\cdot x_{i}\|_{2}$.

Now we are able to bound to bound $|\langle\mathsf{S}_{i,r}(t),\beta_{i,r}(t)\rangle|$. We have

Next, We use Hoeffding’s Inequality (Lemma B.1) on the random variable

where the first step combines the result of Eq. (G.5), Eq. (G.5) and Lemma B.1, the second step is obtained through basic algebraic manipulations.

Above, the 1st inequality combines the result of Eq. (G.5) and Eq. (G.5), and the second inequality is derived through basic algebraic manipulations. The third step uses the inequality $\sqrt{\log(m/\delta)}\leq m^{\frac{1}{6}}$, the fourth step is based on $R\leq B$ and basic algebraic manipulations, and the final step relies on the fact that $O(B)\leq\exp(O(B^{2}D))$.

Finally, based on the lemma condition, we will get

G.6 Bounding C5C_{5}

Assuming the following conditions are satisfied:

Define $\mathsf{S}_{i,r}(t)$ as specified in Definition E.3.

Define $\mathsf{F}_{i}(t)$ as specified in Definition E.4.

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

Let $\eta\leq O(\lambda n^{-4}d^{-1}\exp(O(B^{2}D))^{-1})$.

Then, with a probability at least $1-\delta$, we have,

To bound $Q_{i,1}$. For the first term, we first bound

where the first step follows from definition of $Q_{i,1}$, the second step follows from Eq. (G.6) and Lemma B.1, the last step follows from basic algebraic manipulations.

To bound $Q_{i,2}$. For the second term, we first bound

where the first step is a consequence of the definition of $Q_{i,2}$, the second step is derived from Eq. (G.6) and Lemma B.1 and the final step is a result of basic algebraic manipulation.

where the first step is based on $Q_{i,1}\leq Q_{i,2}$, the second step is a consequence of Eq. (G.6) and basic algebraic manipulations, the 3rd step is based on Definition K.2 and basic algebraic manipulations, and the final step uses the inequality $O(D^{2})\leq\exp(O(B^{2}D))$. ∎

G.7 Helpful Lemma

Assuming the following conditions are satisfied:

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

With probability at least $1-\delta$, we obtain:

where the first step is derived from Eq. (G.1), the second step is obtained by using Cauchy-Schwarz inequality, the third step combines Part 5 of Lemma K.3 and triangle inequality, the fourth step can be obtained by Eq. (G.5) and Eq. (G.5), the last step is a consequence of basic algebraic manipulations and $\|x_{i,d}\cdot(-\eta\Delta w_{r}(t)\cdot x_{i})\|_{2}\geq\|\Theta(1)\cdot(x_{i,d}\cdot(-\eta\Delta w_{r}(t)\cdot x_{i})^{\circ 2}\|_{2}$.

Appendix H Inductions

Assuming the following conditions are satisfied:

Let $C>0$ be a sufficiently large constant.

With probability at least $1-\delta$, we obtain:

where the first step is based on Lemma G.1, the second step combines Lemma G.2, G.3, G.4, G.5 and G.6, the final step results from basic algebraic manipulations.

Choice of $m$ and $\eta$. Following Lemma G.2, G.3, G.4, G.5 and G.6, we choose:

Let $C>0$ be a sufficiently large constant.

With probability at least $1-\delta$, we obtain:

Above, the 1st equation is based on Definition C.3. The 2nd equation is trivially from Claim C.2. And we have $\xi_{i,d+1}\sim\mathcal{N}(0,\sigma^{2})$ and $h_{i,1}\sim\mathcal{N}(0,I_{N})$ which follows from Definition C.3, and $\|\mathcal{P}_{i,d+1}\|_{2}=1$ which follows from Claim C.2.

where this step comes from Eq. (H.1), Fact B.3 and $\xi_{i,d+1}\sim\mathcal{N}(0,\sigma^{2})$.

Consequently, with probability at least $1-\delta$, we have

where the first inequality is derived from Fact B.5, and the second inequality uses Definition K.1.

Above, the first equation is trivially from Definition D.4. The second equation is due to Assumption D.7, and the last step uses Eq. (H.1) and basic algebraic manipulations.

Proof of Part 2. Firstly, we can show that

H.2 Induction for Gradients

Assuming the following conditions are satisfied:

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

With probability at least $1-\delta$, we obtain:

where the first step is trivially from Lemma I.4 and Part 1 of Lemma K.3, the second step uses the fact $O(\operatorname{poly}(B))\leq\exp(O(B))$.

H.3 Induction for Weights

Assuming the following conditions are satisfied:

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

Choose $m\geq\Omega(\lambda^{-2}n^{7}\operatorname{poly}(\exp(B^{2}),\exp(D)))$.

Then, with probability no less than $1-\delta$, we will get

Above the first step is based on the definition of $R$, the second step results from basic algebra, the third step follows from Lemma H.3, the fourth step use basic algebraic manipulations and Part 2 of Lemma H.1, the fifth step is based on Lemma H.2 Part 1, the sixth step is based on Fact B.9 and $B^{2}\leq\exp(O(B^{2}D))$, last step is a consequence of the choice of $m$. ∎

Appendix I Asymmetric Learning

Assuming the following conditions are satisfied:

Denote $v_{\min}:=\min\{\frac{1}{d}\sum_{k=1}^{d}(x_{i,k}-\overline{x}_{i})^{2}\}_{i=1}^{n}$.

Choose m\geq\Omega\Big{(}\lambda^{-3}n^{7}d^{2}\operatorname{poly}(\exp(B^{2}),\exp(D))\Big{)}.

Choose \eta\leq O\Big{(}\lambda n^{-4}d^{-1}\cdot\operatorname{poly}(\exp(B^{2}),\exp(D))^{-1}\Big{)}.

Choose T\geq\Omega\Big{(}\frac{1}{\eta\lambda}\log(nB^{2}/\epsilon)\Big{)}

Consequently, the following holds with probability at least $1-\delta$:

Asymmetric Learning. We can also show that for any $t\geq\Omega(\frac{m}{\eta\lambda v_{\rm min}})$:

Above, the first inequality is due to Part 2 of Lemma H.1, and the second inequality is due to Lemma H.2 Part 1. The final step uses Fact B.9 and plugging $t=\Omega(\frac{1}{\eta\lambda}\log(nB^{2}/\epsilon))$.

Choice of $m$ and $\eta$. Combining Lemma H.1 and H.4, we have:

Proof of Part 1. When $a_{r}=1$, we have:

Above, the 1st equation is based on Definition D.5, and the 2nd inequality is based on Lemma K.3 Part 1 and Lemma I.3 Part 1. The last inequality follows from plugging $t\geq\Omega(\frac{m}{\eta\lambda v_{\rm min}})$.

Proof of Part 2. When $a_{r}=-1$, we have:

Above, the 1st equation is based on Definition D.5, and the 2nd inequality is based on Lemma K.3 Part 1 and Lemma I.3 Part 1. The last inequality follows from plugging $t\geq\Omega(\frac{m}{\eta\lambda v_{\rm min}})$. ∎

I.2 Main Results 2: Attention Fails in Learning Residual Feature

Let all pre-conditions in Theorem I.1 hold.For any Gaussian vector $x\sim\mathcal{N}(0,{\sigma^{\prime}}^{2}\cdot I_{d})$. For all $r\in[m]$ that satisfies $a_{r}=-1$, with a probability at least $1-\delta$, we have:

Note that $h_{k}(x)$ is a convex function for $[x_{k},x_{d}]$ for any $k\in[d-1]$.

Then following Jensen’s inequality, we have

Above the 2nd step is based on simple algebras.

Since $x\sim\mathcal{N}(0,{\sigma^{\prime}}^{2}\cdot I_{d})$, then we have:

Besides, following Theorem I.1, when $a_{r}=-1$, with probability at least $1-\delta$, we have:

I.3 Gradient Direction

Assuming the following conditions are satisfied:

Denote $v_{\min}:=\min\{\frac{1}{d}\sum_{k=1}^{d}(x_{i,k}-\overline{x}_{i})^{2}\}_{i=1}^{n}$

With probability at least $1-\delta$, we have:

Above the first equation follows from Claim C.2 and Definition C.3, and the 2nd equation is based on $h_{i,k}\sim\mathcal{N}(0,1)$ and $\xi_{i,k}\sim\mathcal{N}(0,\sigma^{2})$ independently. Basic algebras and Claim C.2 can obtain the last step.

Hence, we apply Hoeffding inequality to $\sum_{i=1}^{n}x_{i,d}y_{i}$, we have:

Above the first inequality follows from $x_{i,d}\leq B$ and $y_{i}\leq B$, and the second inequality follows from $\sqrt{\log(n/\delta)}\leq B$.

Above, the inequality can be derived from Eq. (I.3).

Above, the first equation is trivially obtained by simple algebra, and the second inequality follows from Part 1 of Lemma I.5, Part 1 of Lemma K.3 and Eq. (39). The third inequality follows from plugging $R\leq O(\exp(-O(B^{2}D))\cdot/(n^{0.5}B^{4}))$, the last step follows from $n\geq O(N/\gamma)$.

Proof of Part 1. When $a_{r}=1$, following Lemma E.5, we have:

where the second step follows from Lemma I.4, the third step follows from Eq. (I.3).

Proof of Part 2. This proof is similar to the Proof of Part 1 of this Lemma above. ∎

I.4 Basic Lower Bound

Assuming the following conditions are satisfied:

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2.

Denote $v_{\min}:=\min\{\frac{1}{d}\sum_{k=1}^{d}(x_{i,k}-\overline{x}_{i})^{2}\}_{i=1}^{n}$ where $\overline{x}_{i}:=\frac{1}{d}\sum_{k=1}^{d}x_{i,k}$.

Then, with a probability no less than $1-\delta$, we have:

where the first two steps can be derived from simple algebras, the second step follows from Fact B.8, and the last step follows from Part 9 of Lemma K.3 and $R\leq B$. ∎

I.5 Model Outputs Concentration during Training

Assuming the following conditions are satisfied:

Define $B$ as specified in Definition K.1.

Define $D$ as specified in Definition K.2.

Then, with a probability at least $1-\delta$, we have

where the first step is trivially from Definition E.4 and the second step follows from simple algebra.

Then we proceed to show that, $\forall i\in[n]$ and $r\in[m]$,

Now we can use Hoeffding Inequality (Lemma B.1) to random variables $a_{r}\cdot\langle S_{i,r}(t)-S_{i,r}(0),x_{i}\rangle$, for $r\in[m]$. Besides, we have

where this step follows from $a_{r}\sim{\rm Uniform}\{-1,+1\}$.

Above, the 1st inequality is based on Eq. (I.5) and the 2nd inequality is based on $O(\operatorname{poly}(B))\leq\exp(O(B^{2}))$.

Then, with probability at least $1-\delta$:

where the first step is a consequence Hoeffding Inequality (Lemma B.1) and Eq. (I.5), the second step is trivially from simple algebras and Definition K.2 and the last step is derived from the fact $O(\operatorname{poly}(D))\leq\exp(O(D))$.

Appendix J Generalization

Assuming the following conditions are satisfied:

Let all pre-conditions in Theorem I.1 hold.

Define ${\cal R}(\cdot)$ as specified in Definition C.4.

where this step follows from $w_{r}(t)<0$ when $a_{r}=-1$ in Theorem I.2.

J.2 Residual Linear Network

Define ${\cal R}(\cdot)$ as specified in Definition C.4.

Then there exists and exists only one $w_{\rm lin}^{*}$ that satisfies:

where the last step is based on the variance of $\xi_{{\rm test},i,d}-\xi_{{\rm test},i,d+1}$. ∎

Appendix K Taylor Series

Assuming the following conditions are satisfied:

Define $B>1$ as specified in Definition K.1.

Define $D>1$ as specified in Definition K.2

Define $R:=\max_{t\geq 0}\max_{r\in[m]}|w_{r}(t)-w_{r}(0)|$.

$\forall i\in[n],r\in[m],k\in[d],t\geq 0$.

Consequently, with probability at least $1-\delta$, we have:

Part 4. $\exp(-O(B^{2}D))\leq{\sf u}_{i,r,k}(0)\leq\exp(O(B^{2}D))$.

Part 5. $\exp(-O(B^{2}(D+R)))\leq u_{i,r,k}(t)\leq\exp(O(B^{2}(D+R)))$.

Part 6. $d\cdot\exp(-O(B^{2}D))\leq\alpha_{i,r}(0)\leq d\cdot\exp(O(B^{2}D))$.

Part 7. $d\cdot\exp(-O(B^{2}(D+R)))\leq\alpha_{i,r}(t)\leq d\cdot\exp(O(B^{2}(D+R)))$.

Part 8. $\frac{\exp(-O(B^{2}D))}{d}\leq\mathsf{S}_{i,r,k}(0)\leq\frac{\exp(O(B^{2}D))}{d}$.

Part 9. $\frac{\exp(-O(B^{2}(D+R)))}{d}\leq\mathsf{S}_{i,r,k}(t)\leq\frac{\exp(O(B^{2}(D+R)))}{d}$.

Part 10. $|u_{i,r,k}(t)-u_{i,r,k}(0)|\leq\exp(O(B^{2}D))\cdot O(RB^{2})$.

Part 11. $|\alpha_{i,r}(t)-\alpha_{i,r}(0)|\leq d\exp(O(B^{2}D))\cdot O(RB^{2})$.

Part 12. $|\alpha_{i,r}(t)^{-1}-\alpha_{i,r}(0)^{-1}|\leq\exp(O(B^{2}D))\cdot O(RB^{2})/d$.

Part 13. $|\mathsf{S}_{i,r,k}(t)-\mathsf{S}_{i,r,k}(0)|\leq\exp(O(B^{2}D))\cdot O(RB^{2})/d$

Above, the first equation is trivially from Definition C.3, and the second equation is also trivially from Claim C.2. And we have $\xi_{i,k}\sim\mathcal{N}(0,\sigma^{2})$ and $h_{i,1}\sim\mathcal{N}(0,I_{N})$ following from Definition C.3 and $\|\mathcal{P}_{i,k}\|_{2}=1$ from Claim C.2.

where the step is a consequence of Fact B.4.

Above, the first inequality is derived by using Fact B.5, and the second inequality is trivially from the Definition of $B$ (Definition K.1).

Above the step can be trivially from Definition D.2.

Thus, with a probability no less than $1-\delta$, we have

Above the first inequality is a consequence of Fact B.5, and the second equation is trivially from the Definition K.2.

Proof of Part 3. By following Lemma statement, we can show that

where the step can obtained from the definition of $R$.

Above, the first inequality is a result of simple algebra, the 2nd inequality applies triangle inequality, and the last step is trivially from Part 2 of this lemma.

The inequality above can be trivially obtained by using Part 1,2 of this lemma.

Above, the first equation is trivially from Definition E.1, and the second step is derived by using basic algebras.

where this step combines Part 1,3 of this Lemma.

where the 1st step is trivially from Definition E.1, and the 2nd step applies basic algebra.

where the first step is trivially from Definition E.2, and the second step applies simple algebra.

where this step can be trivially derived from Part 4 of this lemma.

where the first step is trivially from Definition E.2, and the second step comes from the definition of the inner product. Thus we have

where this step can be obtained by Part 5 of this lemma.

where this step follows from Definition E.3. Then we have

where this step can be obtained by combining Parts 4,6 of this lemma.

where this step follows from Definition E.3. Then we have

where this step can be obtained by combining Part 5,7 of this lemma.

Above the first equation is trivially from Definition E.1, the second equation can be obtained by using simple algebra, the third equation is a consequence Fact B.6, the fourth inequality combines the result of Part 1 of this lemma and $|w_{r}(t)-w_{r}(0)|\leq R$, the fifth inequality applies simple algebra, the sixth step comes from Definition E.1 and the last step is derived from Part 6 of this lemma.

Above the first equation is trivially from Definition E.2, the second step can be obtained by using triangle inequality, and the last step is derived from Part 10 of this lemma.

Above, the first equation is based on simple algebra, the 2nd step is due to Parts 6, 7, and 10 of this lemma, and the last step can be obtained from applying basic algebras and the fact that $R\ll D$.

Above the first equation is trivially from Definition E.3, the 2nd step is due to simple algebra, the 3rd step can be obtained by applying triangle inequality, the fourth step combines Parts 4, 7, 10, 12 of this lemma, and the final step is based on simple algebra.