SKTformer: A Skeleton Transformer for Long Sequence Data
Authors: xue wang
Tian Zhou
Jianqing Zhu
Jialin Liu
Kun Yuan
Tao Yao
Wotao Yin
Rong Jin
HanQin Cai
Venue: Submitted to ICLR 2023 (2023)
Keywords: Efficient Trasnformer
Long Sequence Data
CUR decomposition
Robustness
matrix sketching

Abstract: Transformers have become a preferred tool for modeling sequential data. Many studies of using Transformers for long sequence modeling focus on reducing computational complexity. They usually exploit the low-rank structure of data and approximate a long sequence by a sub-sequence. One challenge with such approaches is how to make an appropriate tradeoff between information preserving and noise reduction: the longer the sub-sequence used to approximate the long sequence, the better the information is preserved but at a price of introducing more noise into the model and of course more computational costs. We propose skeleton transformer, SKTformer for short, an efficient transformer architecture that effectively addresses the tradeoff. It introduces two mechanisms to effectively reduce the impact of noise while still keeping the computation linear to the sequence length: a smoothing block to mix information over long sequences and a matrix sketch method that simultaneously selects columns and rows from the input matrix. We verify the effectiveness of SKTformer both theoretically and empirically. Extensive studies over both Long Range Arena (LRA) datasets and six time-series forecasting show that SKTformer significantly outperforms both villain Transformer and other state-of-the-art variants of Transformer.  Code is available at
https://anonymous.4open.science/r/SKTFormer-B33B/

Under review as a conference paper at ICLR 2023
SKTFORMER: A SKELETON TRANSFORMER FOR LONG SEQUENCE DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Transformers have become a preferred tool for modeling sequential data. Many studies of using Transformers for long sequence modeling focus reducing com- putational complexity. They usually exploit the low-rank structure of data and approximate long sequence by sub-sequence. One challenge with such ap- proaches is how to make an appropriate balance between information preservation and noise reduction: the longer the sub-sequence used to approximate the long sequence, the better the information is preserved but at a price of introducing more noise into the model and of course more computational costs. We propose skele- ton transformer, SKTffrmer for short, an efficient transformer architecture that improves upon the previous attempts negotiate this tradeoff. It introduces mechanisms to effectively reduce the impact of noise while still keeping the com- putation linear the sequence length: smoothing block mix information over long sequences and a matrix sketch method that simultaneously selects columns and rows from the input matrix. We verify the effectiveness of SKTformer both the- oretically and empirically. Extensive studies over both Long Range Arena (LRA) datasets, and six time-series forecasting show that SKTformer significantly outper- forms both vanilla Transformer and other state-of-the-art variants of Transformer. Code is available at
INTRODUCTION
Transformer type models (Vaswani et al., 2017) have achieved many breakthroughs in various artificial intelligence areas, such as natural language processing (NI.P) (Brown et al., 2020; Clark et al., 2020; Devlin et al., 2018 8; Liu et al., 2019), computer vision (CV) (Dosovitskiy et al., 2020; Liu et al., 2021; Touvron et al., 2021; Yuan et al., 2021; Zhou et al., 202 and time series forecasting (Xu et al., 2021; Zhou et al., 2022). The self-attention scheme plays key role in those transformer- models, which efficiently capture long-term global and short-term local correlations when the length of the token sequence is relatively small. Due to the quadratic complexity of standard self-attention, many approaches have been developed to reduce the computational complexity of Transformer for long sequences (e.g., (Zhu et al., 2021)). Most of them try exploit the special patterns of attention matrix, such as low-rankness locality, sparsity, or graph structures. One group of approaches is to build linear approximation for the softmax operator (c.g., (Chen al., 2021; Choromanski et al., 2020; Chowdhury et al., 2021; Qin et al., 2021)). Despite the efficiency of the linear approximation, these approximation methods often perform worse than the original softmax based attention. More discussion of efficient transformer for long sequence can be found in the section of related work.
In this work, we will focus on approaches that assume low-rank structure of input matrix. They approximate the global information in long sequence by sub-sequence (i.e., short sequence) of landmarks, and only compute attention between queries and selected landmarks (e.g.. (Ma al., 2021; Nguyen et al., 2021; Zhu et al., 2021; Zhu & Soricut, 2021)). Although those models enjoy linear computational cost and often better performance than vanilla Transformer, they face one major challenge, i.e., how to balance between information preserving and noise reduction. By choosing a larger number landmarks, we are able to preserve more global information but at the price of introducing more noise into the sequential model and more computational cost.
In this work, we propose an efficient Transformer architecture, termed Skeleton Transformer, or SKTformer for short, that introduces two mechanisms explicitly address the balance. First,

---

Under review as a conference paper at ICLR 2023
introduce smoothing block into the Transformer architecture. It effectively mixes global information over the long sequence by the Fourier analysis and local information over the sequence by convolution kernel. Through the information mixture, are able to reduce the noise for individual tokens over the sequence, and at the same time, improve their representativeness for the entire sequence. Second, we introduce matrix sketch technique to approximate the input matrix by a smaller number of rows and columns. A standard self-attention can be seen as reweighing the columns of the value matrix. Important columns are assigned high attention weights and remain in the output matrix, while small attention weights eliminate insignificant columns. The self- attention mechanism equivalent to column selection if we replace the softmax operator with the corresponding argmax operator. However, sampling only columns may not generate good summary of the matrix, and could be subjected to noises to individual columns. We address this problem by exploiting CUR (Drineas et al., 2008) or Skeleton approximation technique (Chiu & Demanet, 2013) in the matrix approximation community. Theoretically. for rank-r matrix X E Rx we can take Or log d) column samples and Or log n) row samples to construct so-called Skeleton approximation X x RU where C' and R are matrices consisting of the columns and rows of X, respectively, and U is the pseudo-inverse of their intersection. By combing these mechanism, found, both theoretically and empirically, that SKTformer is able to preserve global information over long sequence and reduce the impact of noise simultaneously, thus leading to better performance than state-of-the of-the-artttttttoe variants of Transformer for long sequences, without having to sacrifice the linear complexity w.r.t. sequence length.
In short, we summarize our main contributions as follows:
1. We propose a Skeleton Transformer (SKTformer), an efficient model that integrates smoother, column attention and row attention components to unfold a randomized linear matrix sketch algorithm.
2. By randomly selecting a fixed number of rows and columns, the proposed model achieves near-linear computational complexity and memory cost. The effectiveness of this selection method is verified both theoretically and empirically.
3. We conduct extensive experiments over Long-tern sequence, long-term time series fore- casting and GLUE tasks. In particular, the Long Range Arena benchmark (Tay et al., 2021), 1), achieves an average accuracy of 64% and 66% with fixed parameters (suggested setting in Mathieu et al. (2014); Tay et al. (2021)) and fine-tuned parameters respectively. It improves from 62% of the best transformer-tye model. Moreover, it also has comparable perfor- mance with the recent state-of-ar art long-term time series forecasting models for long-term time series forecasting and GLUE tasks
Organization. We structure the rest of this paper as follows: In Section 2, we briefly review the relevant literature efficient transformers and Skeleton approximations. Section 3 introduces the model structure and performs a theoretical analysis to justify the proposed model. We empirically verify the efficiency and accuracy of SKTformer in Section 4. discuss limitations and future directions in Section 5. Technical proofs and experimental details are provided in the appendix.
RELATED WORK
This section provides an overview of the literature focusing on efficient Transformer models. The techniques include sparse or local attention, low-rankness, and kernel approximation. We refer the reader interested in their details to the survey (Tay et al., 2020c).
Sparse Attention. The general idea of these methods is restricting the query token perform attention only within a specific small region, such as its local region or some global tokens. In this setting, the attention matrix becomes sparse compared to the original one. (Qiu et al., 2019) proposes BlockBert, which introduces sparse block structures into the attention matrix by multiplying a masking matrix. (Parmar et al., 2018) applies self-attention within blocks for the image generation task. (Liu et al., 2018) divides a sequence into blocks and uses a stride convolution to reduce the model complexity. However, these block-type Transformers ignore the connections among blocks. To address this issue, Transformer-X (Dai et al., 2019) and Compressive Transformer (Rae et al., 2019) propose a recurrence mechanism to connect multiple blocks. Transformer-L (Zhu et al., 2021) combines local attention with dynamic projection capture long-term dependence. (Tay et al.,
2

---

Under review as a conference paper at ICLR 2023
2020b) uses meta-sorting network to permute sequences and quasi-global attention with local windows to improve memory efficiency.
Another approach in this category is based stride attention. Longformer (Beltagy et al., 2020) uses dilated sliding windows to obtain a sparse attention matrix. Sparse Transformers (Child et al., 2019) consider approximating dense attention matrix by several sparse factorization methods. In addition, some methods reduce the complexity by clustering tokens. For example, Reformer (Kitaey al., 2020b) uses hash similarity measure cluster tokens, and Routing Transformer (Roy et al., 2021) uses k-means to cluster tokens. BigBird (Zaheer et al., 2020) proposes a generalized attention mechanism described by directed graph to reduce attention complexity. (Lee-Thorp et al., 2021) considers using 2D Fourier Transformation to mix the token matrix directly. (Tan et al., 2021) uses max pooling scheme to reduce the computation costs.
Low-rank and Kernel Methods. Inducing low-rankness into the attention matrix can quickly reduce the complexity and the kernel approximation widely applied efficient low-rank approximation. Linformer (Wang et al., 2020) and Luna (Ma et al., 2021) approximate softmax with linear functions, which yield linear time and space complexity. (Choromanski et al., 2020) and (Peng et al., 2021) use random features tricks and reach promising numerical performance. (Winata et al., 2020) proposes Low-Rank Transformer based on matrix factorization. FMMformer (Nguyen et al., 2021) combines the fast multipole method with the kernel method. Synthesizer (Tay et al., 2020a) uses random low-rank matrix to replace the attention matrix. Nyströmformer (Xiong et al., 2021) adopts the Nyström method approximate standard self-attention. Linear Transformer (Katharopoulos et al., 2020) expresses self-attention as a linear dot-product of kernel feature maps. (Zhu & Soricut, 2021) applies the Multigrid method efficiently compute the attention matrix recursively. Cosformer (Qin et al., 2021) develops a cosine- bosine-based re-weighting mechanism to linearize the softmax function. (Chen et al., 2021) proposes the Scatterbrain, which unifies locality-sensitiv hashing and the kernel method into attention for accurate and efficient approximation.
SKTFORMER
We start by going over the vanilla attention. For sequence of length the vanilla self-attention in the transformer is dot-product type (Vaswani et al., 2017). Following standard notation, the attention matrix A Raxn is defined as:
Va Ok)K))
A = softmax
where Q E Rad denotes the queries while K E Raxd denotes the keys, and d represents the hidden dimension. By multiplying the attention weights with the values V Rudd can calculate the new values as V AV.
Intuitively, the attention is the weighted average over the old ones, where the weights are defined by the attention matrix A. this paper, we consider generating Q, K and V via the linear projection of the input token matrix X:
Q = XWo, K= XWK,, V XWv.
where X E Raxd and WΩ. WK. Wy E Raxd
The vanilla procedure has two drawbacks in concentrating the information from V. First, when computing the QKT part, full dense matrix multiplication is involved at a cost of O(n²) vector multiplications. can be prohibitive for long sequence problems. the other hand, if we view the softmax operator as an approximation of the argmax counterpart, V becomes a row selection from V. This column- wise information concentration is ignored.
3.1 SKELETON ATTENTION
We propose a Skeleton self-attention structure motivated by the Skeleton approximation to address those issues. First, we modify the original self-attention build the column self-attention follows:
V softmax (2OKTH P. P.V,
3

---

Under review as a conference paper at ICLR 2023
where P1 R* denotes the sampling matrix and $1 is the number of columns sampled. Let 81 < i2 < < is. be the indices of the randomly sampled columns. Let Plat denote the element located at the a-th column and b-th row and we have Plaa 1 if i, b and 0 otherwise. By these constructions, we can reduce the computational cost to On nssd).
Similarly, we build the row sampling matrix P2 Rd indicating the locations the 82 sample rows. Compute the row self-attention as:
V23 VP2 softmax (H
Finally, we apply the layer-norm on V1 and V2 and then them together generate the final output:
V layernorm, (V1) + layernorm, V2).
(2)
The usage of layer norm balance the output scales of column and row self-attentions. similar trick has been used in (Zhu et al., 2021), where the layer norm is applied to resolve scale mismatches between the different attention mechanisms.
Before going to the detailed analysis, we first introduce incoherence parameter of a matrix, which is commonly used in many low-rank matrix applications.
Definition (f-incoherrence, Given a rank-r matrix X E Rnxd Let = WEVT be its compact singular value decomposition. X is p-incoherent if there exists constant μ such that
max lle W
pr
and
Vel max lle VI
Pr d
n
where e; denotes the i-th canonical basis vector.
The p-incoherence describes the correlation between the column/row spaces and the canonical basis vectors. The larger μ value implies a higher overlapping, which leads to better chance of successful reconstruction from sparse row/column samples. We next use the following proposition to characterize the efficiency of sampling in both columns and rows.
Proposition 1. Let X E Rundd be a rank-r matrix with p-incoherence. Without loss of generality, we assume d. Let E E Raxdd be a noise matrix. By uniformly sampling O log n) columns and rows from the noisy X- E. Skeleton approximation can construct matrix X such that, with probability at least O(n -?))
|BIlvnd Jrr log
X X SO
Several works (e.g., (Chiu & Demanet, 2013; Drineas et al., 2008)) have proposed explicit methods to construct X. Those methods require computing the pseudo-inverse, generally inefficient in deep learning settings. (Xiong et al., 2021) uses an approximation of the pseudo-inverse in the symmetric matrix setting. It is still an open question whether the approximated pseudo-inverse also works for the general matrix in deep learning settings. On the other hand, in the transformer model, good matrix approximation is not our primary goal, and we thus pursue a different way that only maintains sufficient information pass through the network via (2).
3.2 SMOOTHER COMPONENT
Based on the analysis of Skeleton approximation, the matrix incoherence parameter μ plays a crucial role in determining the number of rows and columns to sample. Decreasing in μ leads to smaller sampling size. Furthermore, the p-incoherence condition implies that the "energy" of the matrix is evenly distributed over its entries, i.e., the matrix is "smooth" (Candès & Recht, 2009). In this subsection, we propose a novel smoother component to reduce the incoherence parameter without introducing excessive information loss.
4

---

Under review as a conference paper at ICLR 2023
Add & harm
Food Forward Laye"
x' R
Alleccon
Layerlor
Layorlom
Easolinan lag
Feed Forward Layer
Resd
2
Add & Norm
Bhi RetU
Soff-itention softmannd QQO
convid-
Q E gard"
K e Redd VER R
g g
(a) Vanilla Transformer
(b) SKTformer
Figure I: Illustration of the architecture of Vanilla Transformer versus SKTformer
3.2.1 FOURIER CONVOLUTION
The incoherence parameter can be viewed as a measure of the smoothness of a matrix. A "smoother" matrix tends have smaller incoherence parameter. Intuitively, the adjacent columns rows have similar values for smooth matrix. Thus a few landmark columns or rows can represent the matrix with little error. On the other hand, if the matrix is harsh (e.g.. containing spiky columns rows), more landmarks are required. A common way to smooth a matrix is to convolute it with smoothing kernel, such as a Gaussian kernel. However, directly using fixed smoothing kernel can potentially remove too much details and harm the final performance. In the recent literature (e.g., Guo et al. 2022), large convolution kernel-based attentions show a supreme performance in vision Transformers. In this paper, we propose to use data-driven convolution layer along the sequence dimension with a kernel size equal to the sequence length. In this setting, the information of a given row could be decentralized among the rows. As the input token matrix is computed through FeedForward layer, the information among different rows already adaptive allocated. Hence, we do not perform the convolution along the hidden dimension.
We use the Fast Fourier Transformation (FFT) to implement the convolution. Let Lo E Rax be the convolution kernel matrix. Via the convolution theorem, the circular convolutions in the spatial domain are equivalent to pointwise products in the Fourier domain, and we then have:
smooth X Lo =F= F(Lo)),
(4)
where F, and denote FFT operator, convolution operator, and point-wise product, respectively.
Equation (4) requires 3d times faster Fourier operations which could be prohibited when facing large d. In order to save the computational cost, domain instead and apply segment-average (averaging segments of hidden dimension) to X. To simplify the notation, assume there integers and with d sr. Instead of using (4), apply the following (5) to smooth the token matrix.
the learnable matrix L E C"xdl in the frequency
X smooth = F (F(S). L]
(5)
II practice, we use the 1FFT/iFFFT the fast (inverse) Fourier Transformation of real input instead of the general FFT/IFFT, and the size of the matrix L is reduced Cbv/3++1)xd
5

---

Under review as a conference paper at ICLR 2023
where
1
0
0
0
11
0
S
E Rdxd
(6)
and 1 denotes the x 8 matrix with all elements equal 1. As XS contains repeated rows, in (5), we can reduce the usage of faster Fourier operations to r + times.
In the following proposition, we show the smooth ability of the Fourier convolution.
Proposition 2. Let (#1,...., j. be sequence with maxt [zx] S amax and max, [ S bmax- Let (l,,.., )n be a sequence of i.i.d. = -us--suguassian variables. Let [tt be the convolution of { and (4), Le., f(t) = -Ei 44115 With probability at least - 6, we have:
1 2n
2n (5)
1
2
If(t) f(t -1)1 0
log
Omax
log
2n
The Proposition 2 can be used to describe the Fourier convolution layer's behavior in the early training stage. Vía some standard initialization methods (e.g., Kaiming initialization or Xavier initialization), the variance of elements in learnable matrix L is O(n and the scale of elements is O(n Onn1//2) To simplify our discussion, let us assume we use Kaiming normal initialization and L becomes random complex Gaussian matrix with zero mean and variance n g2 Using the fact that the FFT of a Gaussian sequence remains Gaussian with 2n times larger variance, the n- oz variance Gaussian sequence through inverse FFT (IFFT) would result in a Gaussian sequence with z120² variance. By Proposition 2, the maximum difference between adjacent elements after the convolution is scaled on On -1 1/2 + Om ~ 6maxon 1/2 when sequence length n is large enough. Thus as long as (V))) the sequence smoothed by the Fourier convolution.
During the training process, the elements in learnable matrix L go away from the independent random variables and help generate better representation of segment-average token matrix XS.. We use the following Proposition 3 to describe the potential representation ability of the proposed Fourier convolution component.
Proposition 3. Let X E R be a bounded matrix and S E Rddd constructed by (6). There exist matrices G, L E Rudd such that
11(XS)a X. X., smooth Srs So ( (=g2ttlogg()
(8)
where (-)x: the submatrix of the first rows of given matrix, X Xemooth is the 1-th row of Gitr(s-14 g((). Here
X Xsmoooth FF- (F(XS) L), and G satisfies G.3 Gita.j
is an orthogonal polynomial basis.
The Proposition 3 states that if we properly train the matrix L. the information in XS up row can be compressed into f-th row of Xsmooth with a moderate tolerance. Therefore, when we sample in rows X smooohh they will contain more information than the same number of rows in the original X S. Similar results are also discussed in FNet (Lee-Thorp et al., 2021) and several RRN literature, such as (Gu et al., 2020) and (Voelker et al., 2019). In (Gu et al., 2020), several specific types of polynomials (e.g., Legendre or Chebyshev) are explored, and the corresponding matrix L is predefined instead of data-driven. Recently, (Gu et al., 2021b) propose a sophisticated method that can be used compute X smmnoth We leave it for future work.
3.2.2 CONVOLUTION STEM
The X emmooth may encounter an over-smoothing situation that local details can wiped out. We use convolution stem (CNNs + BN ReLU) to tackle this problem. We first concatenate Xemooth with the original token matrix X into a n x 2d matrix and then apply a ID convolution with kernel size d dimensions. At last, the output is normalized with the Batchnorm layer
to transform it back and truncated by the ReLU activation function to stabilize the training procedure. (Wang et al., 2021) report the ReLU activation coupled with the normalization layer plays an important role in various vision transformers and analyzes this phenomenon theoretically. Here we omit the dependence in for brevity.

---

Under review as a conference paper at ICLR 2023
4 EXPERIMENTS
In this section, we test our SKTformer on Long Range Arena (LRA) datasets (Tay et al., 2021) and six real-world time series benchmark dataset for long term forecasting. We also evaluate the transfer learning ability of SKTformer on GLUE tasks. We implement the SKTformer based on the official codes of (Zhu et al., 2021) and (Zhou et al., 2022) for LRA and time-series forecasting tasks respectively. The implementation detail (source code) for SKTformer is provided in Appendix A.
4.1 LONG-RANGE ARENA
The open-source Long-Ramn Range Arena (LRA) benchmark (Tay et al., 2021) is proposed as a standard way to test the capabilities of transformer variants architectures on long sequence tasks.
Table I: Experimental results Long-Range Arena benchmark. Best model is in boldface and second best underlined. The standard deviation of SKTformer are reported in parenthesis.
Model
ListOps
Text
Retrieval
Image
Pathfinder
Average
Transformer
15.82
52.98
53,39
Local Attention
15.82
52.98
53.39
41.46
66.63
46.06
Sparse Transformer
17.07
63.58
59.59
44.24
71.71
$1.24
Longformer
62.85
56.89
42.22
69.71
Linformer
35.70
53.94
52.27
38.56
76.34
$1.36
Reformer
37.27
56, 56.10
$3,40
38.07
68.50
50.67
Sinkhorn Transformer
61.20)
Syathesizer
36.99
61.68
54.67
41.61
69.45
52.88
BigBird
36.05
64.02
$9.29
40.83
74.87
55.01
Transformer
$3.09
75.30
Performer
18.01
65.40
53.82
42.77
77.05
51.41
Nystromformer
37.34
65.75
81.29
41.58
70.94
$9.38
H- H-Transformer-ID
49.53
78.69
63.99
46.05
68.78
61.41
Transfomerr-LS
38.36
68.40
81.85
45.05
76.48
62.03
FNet
35.33
65.11
59.61
38.67
77.08
$4.42
Luna
65.78
79.56
47.86
78.89
EMMformer
36.74
67.84
81.88
45.10
72.12
60.74
PoNet
38.80
69.82
80.35
46.88
70.39
61.05
Cosformer
37,9
63.41
61.36
43.17
70.33
$5.23
Scatterbrain
38.6
64.55
80.22
43.65
69.91
$9.38
SKYYfrmer (1,51, 8)
38.30(0.40)
69.27(0.83)
83.26(0)45)
$3.90(1.54
75.82(0.97)
64.11(2.07)
SKTYormer (hest)
39.15(0).88
71.58(0.95)
83.73(0.61)
$7.73(1.33)
78.20(1.32)
66.08(2.56)
We benchmark our model with several recent state-of-art efficient transformers, including Sparse Transformer, Longformer, Linformer, Reformers, Sinkhorn Transformer, Synthesizer, BigBird, Linear Transformers, Performer, Nyströmformer, H-Transformer- ID, Transformer-LS FNet, Luna, FMMformer, Cosformer and Scatterbrain. SKTformer achieves the highest 66.08% average accuracy with tuned parameters and second best 64.1 1% result with fixed parameters as shown in Table 1.
In particular, SKTformer significantly outperforms the benchmarks Image tasks by relatively large margins (12.6% and 20.6%, respectively), which support SKTformer's smoothness effect on the low-level features and will benefit the high-level image classification tasks.
Moreover, we want to highlight the sampling efficiency of SKTformer. The sequence length of LRA tasks is over one thousand. The efficient Transformers in literature usually can not project the token matrix to very small size while maintaining comparable numerical performance, by only sampling rows and columns from the token matrix, SKTformer has already obtained 64. 1% average score improving the previous best 62.03% score of Transformer-LS.
4.2 LONG-TERY FORECASTING TASKS FOR TIME SERIES
To further evaluate the proposed SKTformer, we also conduct extensive experiments on six popu- lar real-world benchmark datasets for long-term time series forecasting, including traffic, energy, economics, weather, and disease as shown in table 2
To highlight the relevant comparison, mainly include five -fate-of-the-art (SOTA) Transformer- based models, i.e., (EDoormer(Zhou et al., 2022), Autoformer (Wu al., 2021), Informer (Zhou al., 2021a), LogTrans (Li et al., 2019), Reformer (Kitaev et al., 2020a), and recent state-space
7

---

Under review as a conference paper at ICLR 2023
model with recursive memory S4 (Gu et al., 2021a), for comparison. FEDformer is selected as the main baseline as it achieves SOTA results in most settings. More details about baseline models, datasets, and implementations are described in Appendix.
Compared with SOTA work (FEDformer), our proposed SKTformer yields a comparable performance in those tasks, with 4/6 datasets having relative MSE reductions. It is worth noting that the improve- ment is even more significant on certain datasets, e.g., Exchange (> 30%). Although Exchange does not exhibit an apparent periodicity pattern, SKTformer still achieves superior performance. Table 2: multivariate long-term series forecasting results on six datasets with input length of 96 and prediction length O E [96, 192, 336, 720} (For ILI dataset, we set prediction length O E {24, 36, 48, 60)) with input length 60. A lower MSE indicates better performance. All experiments repeated 5 times.
Methods
SKTYormer
FEDiormer
Autoformer
S4
Informer
Log Truns
Reformer
Metri
MSE
MAE
MSB
MAE
MSE
MAE
MSB
MAE
MSE
MAB
MSE
MAE
MSE
MAB
EThm2
96
0.192
0.283
0.203
0.287
0.255
0.339
0.705
0.690
0.365
0.453
0.768
0.642
0.658
0.619
192
0.255
0.324
0.269
0.328
0.281
0.340
0.924
0.692
0.533
0.563
0.989
0.757
1.078
0.827
336
0.324
0.364
0.325
0,366
0.339
0.372
1.364
0.877
1.363
0.887
1.334
0.872
1.549
0.972
720
0.431
0.433
0.415
0.422
0.419
0.877
1.074
3.379
1.338
3.048
1.328
2.631
1.242
Exchange Electricity
96
0.218
0.332
0.183
0.297
0.201
0.317
0.304
0.405
0.274
0.368
0.258
0.357
0,312
0.402
192
0.361
0.195
0.308
0.222
0.313
0,413
0.296
0.386
0.266
0,368
0.348
336
0.267
0.367
0.212
0,313
0.231
0
0,290
0
0,300
0.394
0,280
0.380
0.350
0.433
720
0.385
0.343
0.254
0.361
0,262
0.373
0.283
0.340
0.420
96
0.086
0.204
0.139
0.276
0.197
0.323
1.292
0.849
0.847
0.752
0.968
0.812
1.065
0.829
192
0.188
0.292
0,255
0.369
0. 0,300
0.369
1.631
0,968
1.204
0.895
0.851
1.188
0.906
336
0.356
0.433
0.426
0.464
0.509
0.524
2.225
1.145
1.672
1.036
1.659
1,081
1.357
0.976
720
0.727
0.669
1,050
0,800
1.447
0.941
2.521
1.245
2.478
1,310
1.94]
1.127
1,510
1,016
Traffic
96
0.592
0.352
0.562
0.349
0.613
0.388
0,824
0.514
0.719
0.391
0.684
0.384
0.732
0.423
192
0.583
0.343
0.562
0,346
0.616
0.382
1.106
0.672
0.696
0,379
0.685
0.390
0,733
0.420
0.508
0.346
0.570
0.323
0.622
1.084
0.627
0.777
0,420
0.733
0,408
0.742
0.420
720
0.641
0.397
0.596
0.368
0.660
0.408
1,536
0.845
0.864
0.472
0.717
0.396
0.755
0.423
ILJ Weather
96
0.262
0.296
0.266
0.406
0.300
0.458
0.490
0.689
0.596
192
0.228
0.306
0.276
0,336
0. 0.307
0.367
0.525
0.527
0.598
0.544
0.658
0.589
0.752
0.638
336
0.295
0.355
0.339
0,380
0.359
0.395
0.531
0.539
0.578
0.523
0.797
0.652
0.639
0.596
720
0.383
0,418
0.403
0.428
0.578
0.578
0,419
0.428
1.059
0.741
0.869
0.675
1.130
0.792
24
2,185
0.926
2.203
0.963
3.483
1.287
4.631
1.484
5.764
1.677
4,480
1,444
4,400
1.382
36
2.155
0.937
2.272
0.976
3.103
1.148
4.123
1.348
4.755
1.467
4.799
1.467
4.783
1.448
48
2.333
0.954
2,209
0.981
2.669
1.085
4,066
1.36
4,763
1.469
4 4,800
1 1468
4,832
1,465
0.958
2.545
1.061
2.770
4.278
5.264
1.564
5.278
1.560
4.882
1.483
4.3 TRANSFER LEARNING IN GLUE TASKS
We evaluate the transfer learning ability of the proposed model in the pretraining- finnuuinnniiinnnninngnnnngg paradigm in NLP tasks. We pretrain vanilla BERT (Devlin et al., 2018), FNet (Lee-Thorp et al., 2021), PoNet (Tan et al., 2021) and our SKTformer with the same MLM loss in (Devlin et al., 2018) on English Wikitext- 103 and BooksCorpus datasets. All models are uncased and pretrained with the same configuration with million steps at most. We report the best GLUE results for each model from multiple hyper-parameters configurations in Table 3, and the detailed training configurations in Table 15 in Appendix K. Our SKTformer reaches 77.01 average scores (96.0% of the accuracy of vanilla BERT). which also outperform FNet by 4.6% % and PoNet by 0.3% relatively.
Table 3: GLUE validation results. We report the mean of accuracy and Fl for QQP and MRPC, matthew correlations for CoLA, spearman correlations for STS-B, and accuracy for other tasks. For MNLI task, we consider the matched test set.
Model
MNLI
QQP
QNLI
SST-2
CoLA
STS-B
MRPC
RTE
Average
BERT-- Base
81.98
89.25
88.22
91.07
48.08
87.98
86.43
69.98
80.37
FNet-Base
73.20
85.83
80.57
88.66
40.67
80.64
80.88
57.41
73.48
PoNet- Base
77.02
87.59
84.37
89.29
45.38
84,66
81.82
64.27
76.80
SKTformer (Ours)
76.86
87.67
84.12
90.14
46.72
84.87
81.84
63.87
77.01
4.4 TRAINING SPEED AND PEAK MEMORY USAGE
We compared the training speed (in terms of steps per second) and peak memory usage with several baseline models. SKTformer achieves 4x time speed advantage and 87% memory reduction
8

---

Under review as a conference paper at ICLR 2023
compared to vanilla transformer models with 3k input setting and has neck-to-nen toekkck performance compared to the most efficient baseline models as shown Table 4.
Table 4: Benchmark results of all Xformer models with consistent batch size of 32 across all models with various input lengths
Train Speed (Steps per second)
Penk Memory
Usage (GB)
Model
1K
2 K
4K
1K
2K
3K
Transformer
23.8
0OM
3.7
22.1
00M
Linforner
37.0(1.5xc)
20.8(2.68) (x)
11.9(3.7x)
11.9
2.3
3.3
4.3
5.2
Reformer
28.5(1.xx)
15.1(1
11.9(3.0x)
9.1
2.2
3.2
4.2
4.9
Nystroformer
33.3(1.4x)
22.7(2.9x)
17.2(4.3x)
14.7
1.6
2.2
2.4
Performer
29.1(1.2x)
16.9(1.9x)
8.7(11.75)
9.3
2.3
3.1
4.0
4.8
SKTformer
32.2(1.4x)
20.4(2.6x)
15.9(4.0x)
12.3
1.8
2.3
2.8
3.2
4.5 ROBUSTNESS ANALYSIS
We conduct noise-resistant experiment for SKTformer and Xformers shown in Table We use the Image experiment setting in LRA datasets. During generating sample sequence, randomly add noise with uniform distribution U(-a, a) to each position in the sequence. We consider [0, 2, 4, 8j and train every model with 5k steps and 5 replicates. Our model's performance remains robust with a high level noise injection. This supports our theoretical robustness analysis and shows SKTformer indeed makes appropriate tradeoff between information preservation and noise reduction.
4.6 ABLATION STUDY
This subsection provides ablation test four components: Fourier Convolution, Convolution Stem, Column Attention, and Row Attention. We use SKTformer with (r, 81, $2 = 8) as the baseline, and the detailed settings in Table 11 in Appendix F. In Table 6 we present the accuracy changes when removing each component. The centommance-derraasii components used in SKTformer necessary to reach promising results. The most significant component is Column Attention which leads 8.28 average accuracy difference. reflects that good summary of the whole sequence important. Similar observations also reported in Transformer- LS (Zhu et al., 2021) and XCIT (Ali et al., 2021), where the spirit of attention over columns is used in the dynamic project and Cross- Covaaiicee Attention, respectively. The second most effective part is Fourier Convolution. It reaches 13.89% accuracy difference in the Retrieval task involving two 4k sequences. Fourier Convolution also works well on shorter sequence tasks (e.g., Image and Pathfinder) and brings 6.12% accuracy difference.
results in Table 6 indicate the four
CONCLUDING REMARKS
We propose SKTformer, a robust and efficient transformer architecture for modeling long sequences with a good balance between feature preserving and noise resistance. aggregates a Fourier convolutional stem smoothing information among tokens and a 3keleton-deccompositionnn-- efficient self- aoff-attention. In particular, our proposed Skeleton Attention directly samples the columns and rows of the token matrix. Such design increases the model's 's robustness and gives us a positive near- -inerr complexity side effect. We conduct a thorough theoretical and experimental analysis of the proposed model and show its effectiveness. Lastly, extensive experiments show that the proposed model achieves the best performance on Long Range Arena compared to all transformer-basee baselines and state-of-art performance in long-term time series forecasting tasks.
Table 5: Average Accuracy Image task (CIFAR-10 dataset) in Long Range Arena with noise injections. The relative performance changes are reported parentheses.
Noise level
Transformer
41.39
40.29 (-2.82%)
28.56 (-31.12%)
28.12 (-32.18%)
Linfommer
38.43
37.99 (-1.49%)
37.04 (-3.95%)
36.65 (-4.97%)
Reformer
38.04
37.64 (-1.12%)
35.26 (-7.37%)
34.88 (-8.37%)
Nystrolormer
41.52
40.89 (.1.66%)
38.39 (-7.67%)
37.84 (-8.99%)
Performer
42.66
(-1.93%)
39.61 (-7.40%)
(-9.15%)
SKTformer
57.47
57.06
(-0.82%)
55.32 (-3.84%)
54.70 (-4.92%)

---

Under review as a conference paper at ICLR 2023
Table 6: Ablation experiments. The SKT (r, $1, $2 8) is used as baseline. The differences by removing each component from the baseline model are reported.
Model
LisOps
Text
Retrieval
Image
Pathfinder
Average
Baseline
38.30
69.27
83.26
53,90
75.82
64.11
Fourier Conv.
-0.47
-4.04
-13.98
-5.64
-6.59
-6.14
Stem
-0.13
40.55
-1.51
-1.76
-0.88
Column Attn.
-1.16
-8.00
-9.16
-10.63
-12.45
-8.28
Row Attn.
-0.38
-1.92
-1.97
-2.64
-2.56
-1.89
One limitation of the current SKTformer is that we need to use both FFT and IFFT in a sequential manner, which is potentially slower than the existing Fourier-based Transformers (c.g., (Lee-Thorp et al, 2022))22) )) that only involve the FFT. As our primary goal using Fourier convolution is to smooth the token matrix and reduce the incoherent parameter,
can the Random Fourier Transformation (Ailon & Chazelle, 2006) to modify SKTformer with only FFT. Another limitation is that the size of L matrix in the Fourier Convolution part is the same as the input sequence. On longer sequence, L will contain more learnable parameters that make the model easier to overfit. We may introduce low-rankness or use a more sophisticated design, such as (Gu et al., 2021b), tackle this issue the future.
REFERENCES
Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast transform. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 557-563, 2006.
Alaaeldin Ali, Hugo Touvron, Mathilde Caron, Piotr Bojanowski, Matthijs Douze, Armand Joulin, Ivan Laptev, Natalia Neverova, Gabriel Synnaeve, Jakob Verbeek, et al. Xcit: Cross-cons covvracov image transformers. Advances in neural information processing systems, 34, 2021.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05// 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
HanQin Cai, Keaton Hamm, Longxiu Huang, and Deanna Needell. Robust CUR decomposition: Theory and imaging applications. SIAM Journal on Imaging Sciences, 14(4):1472-1503, 2021.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 9(6):717-777) 2009.
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song. Atri Rudra, and Christopher Ré. Scatterbrain: Unifying sparse and low-rank attention. Advances in Neural Information Processing Systems, 34, 2021.
Rewon Child, Scott Gray, Alec Radford, and llya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904. 2019.
Jiawei Chiu and Laurent Demanet. Sublinear randomized algorithms for skeleton decompositions. SIAM Journal on Matrix Analysis and Applications, 34(3):1361 1311-33311-13888 2013.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. In International Conference on Learning Representations, 2020.
Sankalan Pal Chowdhury, Adamos Solomou, Avinava Dubey, and Mrinmaya Sachan. On learning the transformer kernel. arXiv preprint arXiv:2110.08323, 2021.
Kevin Clark, Minh- Shah-ThaggTun Luong, Quoc Le, and Christopher D Manning. Electra: Pre-training text encoders discriminators rather than generators. arXiv preprint arXiv:2003. /0055 2020.
10

---

Under review as a conference paper at ICLR 2023
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdi- nov. Transformer-x:: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901.02860, 2019.
Jacob Devlin, Ming-Wel Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:/810.0480) 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
Petros Drineas, Michael W Mahoney, and Shan Muthukrishnan. Relative-error CUR matrix decom- positions. SIAM Jourmal Matrix Analysis and Applications, 30(2):844 (112)):44488112000 2008.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. Advances in Neural Information Processing Systems, 33: 1474-1487, 2020.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces, arXiv preprint wrXiv:2//1.0039/0 2021a.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces, arXiv preprint arXiv:2111.00396, 2021b.
Meng-Hao Guo, Cheng-Ze Lu, Zheng-Ning Liu, Ming-Ming Cheng, and Shi-Min Hu. Visual attention network. arXiv preprint 2rXiv:2202.09774, 2022.
Keaton Hamm and Longxiu Huang. Perturbations of CUR decompositions, SIAM Journal Matrix Analysis and Applications, 42(1):351-335, 2021.
Angelos Katharopoulos. Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pp. 3156-5163 PMLR, 2020.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020a.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint urXiv:2001.0445) 2020b.
Guokun Lai, Wei-Cheng Chang, Yiming Yang, and Hanxiao Liu. Modeling long-and short-term temporal patterns with deep neural networks. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 95-104, 2018.
James Lee- Joshua Ainslie, Ilya Eckstein, and Santiago Ontanon. Fnet: Mixing tokens with fourier transforms. arXiv preprint 105.422.000.0824 2021.
Shiyang Li. Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xiang Wang, and Xifeng Yan. Enhancing the locality and breaking the memory bottleneck of transformer time series forecasting. In Advances in Neural Information Processing Systems, volume 32, 2019.
Peter Liu, Mohammad Salch, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. arXiv preprint arXiv:1801.10199 2018.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 190iv 11692, 2019.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEFF/CVF International Conference Computer Vision pp. 10012-10022, 2021.

---

Under review as a conference paper at ICLR 2023
Xuezhe Ma, Xiang Kong, Sinong Wang, Chunting Zhou, Jonathan May, Hao Ma, and Luke Zettle- moyer. Luna: Linear unified nested attention. Advances in Neural Information Processing Systems, 34, 2021.
Michael Mathieu, Mikael Henaff, and Yann LeCun. Fast training of convolutional networks through fits: International conference on learning representations (iclr2014), cbls, april 2014. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
Tan Nguyen. Vai Suliafu, Stanley Osher, Long Chen, and Bao Wang. Fmmformer: Efficient and flexible transformer via decomposed near-field and far-field attention. Advances in Neural Information Processing Systems, 34, 2021.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In International Conference Machine Learning, pp. 4055 4064. PMLR, 2018.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. Random feature attention. arXiv preprint arXiv:2103.02143, 2021.
Zhen Qin, Weixuan Sun. Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan. Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. In International Conference on Learning Representations, 2021.
Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint arXiv:1911.02972, 2019.
Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy P Lillicrap. Compressive transformers for long-range sequence modelling. arXiv preprint 1rXiv:191..05500 2019.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68, 2021.
Chao-Hong Tan, Qian Chen, Wen Wang, Qinglin Zhang, Siqi Zheng, and Zhen-Hua Ling. Ponet: Pooling network for efficient token mixing in long sequences. arXiv preprint arXiv:2110.02442. 2021.
Y Tay, D Bahri, D Metzler, D Juan, Z Zhao, and C Zheng. Synthesizer: Rethinking self-attention in transformer models. arxiv 2020. arXiv preprint arXiv:2005.00743 2020a.
Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. In International Conference on Machine Learning, pp. 9438-9447, PMLR, 2020b.
Yi Tay, Mostafa Dehghani. Dara Bahri, and Donald Metzler. Efficient transformers: A survey. arXiv preprint arXiv:2009.067322 2020c.
Yi Tay, Mostafa Dehghani. Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena : benchmark for efficient transformers. In International Conference Learning Representations, 2021.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pp. 10347-10357. PMLR, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Aaron Voelker, Ivana Kajić, and Chris Eliasmith. Legendre memory units: Continuous-time repre- sentation in recurrent neural networks. Advances in neural information processing systems, 32, 2019.
Pichao Wang, Xue Wang, Hao Luo, Jingkai Zhou, Zhipeng Zhou, Fan Wang, Hao Li, and Rong Jin. Scaled relu matters for training vision transformers. arXiv preprint 10908:2100,03810, 2021.
12

---

Under review as a conference paper at ICLR 2023
Sinong Wang. Belinda Z Li, Madian Khabsa, Han Fang. and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04700 2020.
Genta Indra Winata, Samuel Cahyawijaya, Zhaojiang Lin, Zihan Liu, and Pascale Fung. Lightweight and efficient end-to-end speech recognition using low-rank transformer. ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6144- 6148. IEEE, 2020.
Haixu Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Autoformer: Decomposition transformers with auto-correlation for long-term series forecasting, In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pp. 101-112, 2021.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nystrômformer: A nyström-based algorithm for approximating self-attention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 14138-14148, 2021.
Jiehui Xu, Jianmin Wang, Mingsheng Long, et al. Autoformer:
Decomposition transformers with auto-correlation for long-term series forecasting. Advances in Neural Information Processing Systems, 34, 2021.
Li Yuan. Qibin Hou, Zihang Jiang, Jiashi Feng, and Shuicheng Yan. Volo: Vision outlooker for visual recognition. arXiv preprint arXiv:2106. 13112, 2021.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, al. Big bird: Transformers for longer sequences. Advances in Neural Information Processing Systems, 01211283--79997 2020.
Haoyi Zhou, Shanghang Zhang. Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In The Thirty- Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Conference, volume 35, pp.
11106-11115, 2021a.
Jingkai Zhou, Pichao Wang. Fan Wang, Qiong Liu, Hao Li, and Rong Jin. Elsa: Enhanced local self-attention for vision transformer. arXiv preprint arXiv:21 12.7866 2021b.
Tian Zhou, Ziqing Ma, Qingsong Wen, Xue Wang, Liang Sun, and Rong Jin. FEDformer: Fre- quency enhanced decomposed transformer for long-term series forecasting. In 39th International Conference on Machine Learning (ICML), 2022.
Chen Zhu, Wei Ping, Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandkumar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision. Advances in Neural Information Processing Systems. 34, 2021.
Zhenhai Zhu and Radu Soricut. H-transformer-ld Id: Fast oineeiinall hierarchical attention for sequences. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 3801-3815, 2021.
13

---

Under review as a conference paper at ICLR 2023
Supplementary Material for SKTformer: An Efficient Skeleton Transformer for Long Sequence Data
A
ALGORITHMS
Algorithm
Skeleton Attention
class
:odulel:
_ini=_(se1,,
head_dim seq_ien, left_rank a,righ__rank
dropout 0.1):
super (eeeeli@kkeeeeoottteeetiio self) (nit_
self. nelf.nun_head nem_head
f.head_dim head_dim
se se_f.seq_len seq len
seif.left_rank left_rank
reif.right_rank right_rank
seif.in_1 nn. (ww.y:/looomeee..eenn....
self.head head_dim)
seif.in_2 (ew.yyyoommmmel....n..
self, celf.hean headfhemmdddm
seif. droppattn torch.na. wrech.t (p-drepout)
seif. set___se______ right torch. randpermisel htt.eermmmee...ee.eeeeeeeee.e head_dim)
we.f.index_eet_righhe se fo.ff.nnex_ees_rit (nself rseol..iggh._rnng
self. fo.f..nnexxaes_riae
leif.index_eet_left self ie.f.index_eer_let
def combine tself, tself, x):
x x.szanspoze (1,
(K (.aize(1), self.num_head self self.head_dde head_ddmm) return X
daf split_headd (self, X): X.reshape (0)e (laize()), self.nun_head, self.head_dim X.:ransposee,, 2)
return X
def (sel,, x, V):
4/44 Row Attention 444
seif.seq_ien: self.left_reaf ind.i.iixxx___teeetee soft, :]
K1 = K[;, sclf.
v1 wtw.riieet..ndeeeeee____te
else:
K1 =
v1 =
dots 0 Kl.transpese (-i, -2)
dots dots / math. sgrt f. head head_dim) fn.functionaa wttoonall.cffmaaee softmax (dots, dim--1)
attr selt.drropattnnaatmm
tft# Column Actention #tft 02 0...ranapos (-1,
1f self.right_rank <- head
k, www.eell..ii.eeeeoe V2 self, indexe__iidee
else:
V2 -
dots_r
dots_r dots_r methh sert (eeeff.se__lleee
attr_r nn. functional. iannctionll.sottmmeet. softmax (dttt trtttt_..iimm-))..rrrooooo .tranposee [-1,-2] attr_r aai..dro_attnnatti
salf, salf.aplit,
hsads f.1n. In In_1 (self, combi ne. heads (torch. motemllmmmmlllocmmmmmmmmm (attn, V1))))/2 self.
split_heedda in_2 (selt. combire
act__r)))))
return X
14

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Smoother component
class Smoothez (nn. :odulel:
eet ini Iselt, hidden_size, aeq_len, cropout 0,5, nun_head 2, t.tranatormer_aae 64, fold - 1):
super (Smoother, self),__nit__ 1n
seif.hidder_sit
hidden_size f...g_g.eoe seq
self. se.f.dropout Gropout
seif.num_head nus_head
self.dim tsansformer_dim se.1.fold tolc
self. we.r.weights_frr fft Paramette
hiddenn si2e,
nu nn. inii kaniii..iiiiiinnnmmmmaa.....
mode-' "aneem''nn nonlinearsty- rele")
te.t.tiny_conv_iie out channels self. salf.hidden_sin kernei_size 3, padding" Lr groups 11
torch.
hidden_sisee22
sel droppet torch.nn Drrooott se-sel.ddropou len)
se_t.bn_1 on..Bachkormld
def (self x):
4+4+ Compute Segment Average H+
8, = x.shaae x.reshape self. ftt........////el..eee..
torch.mean dim -1)
444# Pourier Convolution 4:44
fft_u fft.sfft (2, self.seg_len,
-2)
f*t_u = weeobvieewas______e [fft_u]
Iit_u (1, h.tps//t.///l....l.......
seif.weight_une
wewf.weights_ffttteeeeeoe un..uuueeeee
terp_real repl fft_ul...,, * wwt.ee....iggtttoooooo....
fff_ufl...... sell f.welf weee
[...,
temp_imag imag fft_ul.... set......isi.....iihh..ueeed
fft_uf.......................... ssels wtw.:wwwwss.w....._.u... weightt_wwthtteee
[...,
out_rt - torch. cat ([temp_red u-squeeze-11), tenp_ttaa.uuuuuuueeeeeeee unaqueeze (-11), dim -11
out_ft wtte_asiiee________e______e__eee wwwpppeeeeeeexeeeeeeeaaaee (out
ff=.irfft (out_ft, n self.see_len, axis 2)
*### Convolutionn Stem #tft
Iaput_h torch.cat cat ( (m, x), dim -11
self.tiay_coom htt___ccay_eeeeeeeeeeeeeeeee (input_h.. h.pemutte (0,2,1)) .perutee (0, 2,
salf, dropout (F.rclu (salf.bb_
return h
Algorithm 3 pseudo code for Time-Series Forecasting
det forward x_in):
E1, xhin. for 1 range (sel. (ee.....cccee))) atta_layez self.encoder[1] #standardize the input data
:mp_mean torch. (xiin iy dim 1, k,keepdim True)
smp_std = torch. (torch. worrhh.vrrr in[; i, =, keeppii = True)+le0)
in
tmp_nean) (tmp_ato)
enc_outl self. wnw...ennnebeeddinggg..
ene_outl- attn_layer (eno_out1) enc_out1
tdeceder Fouriae Extropelatiinr dec_euz self. war..oorrrrexxtaalloaaiooo (post (enc_cutl))
autput idaa_dott reshape -1),-1,C)) [tmp_std) #tmp_mean
return output
B PROOF OF PROPOSITION 1
similar result, under a slightly different setting, can be found in (Cai et al., 2021). For the completeness of the paper, provide proof here. We resolve the sampling strategy. We consider clear rank-r matrix X Rxd i.., no additive noise and the rank is exact. Without loss of generality, assume 2 d. Provided X is p-incoherent, (Chiu & Demanet, 2013, Theorem 1.1), Skeleton
15

---

Under review as a conference paper at ICLR 2023
Algorithm 4 Fourier Extrapolation
class TourierExtrepolat:: (on. (onduuuee)
daf iiiii (solfs inw.tnttsssaaaaoo
predict 96)
super (1 -in-:: self.n ImputSize
self.n_harm n_harm
f.f torch.fft. (tt..fffft.tttrregeeelttt.
sel se_f.indexes 11st (range
sort Indexes by Irequeacy, lower >> higher
self, ledfeindexes..eo (key lambda i: torch, absolute (
self.indexes inda.indaxes self.n_hade 2]
se f.n_prediet c_predict
compute init phase
self.t torch. t0, self.n predie_
seif.t1 self, te (C) unsqquezze tto self.f = felf.f.undqueeze unsqueezze (nn.eeee)..nquueeeeeeee.e. cuda")
unsqueeze(-1)) (".oo""))
selt.t.unsqueezell unngueerstt...eeeeeeerrallll
self.g self. iadeee, il (2, .unqqueeee
self ceif.phase_init
3.1415 self.g salf.t
def Eourieristrrppoletinnn (sell) x):
frequency
x *rteedom torch,tit. tx, -21
fregdom torch. viecchiviwwa__eelll. (x__edddd
select importance frequencies
x
freedoo x ww..arddomi,a2. s0,0m, indexes :
[_reddomm torch. view_aa_w_____eeeeeeeeeeeeaeeeee ctt_a___ccmeee____a______
ampli
(xeeggda ebsolute fregdom)
self.n amplitude
phase sarch.anglat (x__gllx__frddomm
phase
ampli ampli. (0,2, unsqueeze
phase phase.pcrmute 10, 1), unsqquezze
self.restored_sig ampli torch. cos ieelf.phase_inn phase]
return torch. sum sww.s wtw. -1)
approximation recovers X exactly, i.e,
X CUR,
with probability at least 1 - 2( if we uniformly sample Our log n) rows and columns to form the submatrices C and R.
Thirdly, we resolve the eπrоr bound estimation. For the noisy matrix X + E, we directly apply (Hamm& & Huang, 2021, Corollary 4.3). Thus, have
(V nd
|X CURI so
|E||
(otR
where Ò and are sampled from the noisy matrix, Ó is the aseudo-inverss of their intersection, and lo (resp. (R) is the number of columns (resp. rows) being sampled in Ó' (resp. R).
Note that this error bound assumes good column and row sampling, i.e., the clear submatrices corresponding to Ò and R can recover exactly. Therefore, by combining the above two results, we show the claim in Proposition 1.
C PROOF OF PROPOSITION 2
As f(t) is the convolution function of {ar} and (4), from the definition of convolution for t = 2, .,, we have
f(1)
4+1-12
1=1
16

---

Under review as a conference paper at ICLR 2023
and
[-1
f(t) f(t)-f(t11)
Σ
(411 4) 11
(9)
(1))
By Hoffelding inequality, term (a) satisfies the following inequality with & > 0.
((((a))) E) P
Σ
(.+1 11)xz 26 I exp (-(t- - 1) # 0²
2ga
(10)
Combine (10) with the union bound over 1, ..., and the following (10) holds with probability at least 1 - 8/2:
1
2n
max [(x))] S Umax
V
log
(11)
2n
8
Similarly, with probability 1 6/2, we have
2 log
max 21 S amax V 2n²
(12)
8
Therefore, via (11) and (12), with probability least 1 d, we have
1
2n
1
2 (8)
max (f(t) f(t - 1)1 S 6max
| 2n
log
8
+
0unaxx
V
2n²
log
(13)
D PROOF OF PROPOSITION 3
The proof contains two parts. In the first part, we view the data sequence as a function of index and construct the coefficients and orthogonal polynomials for function approximation. In the second part, we show such coefficients can be computed with Fourier convolution i.e. (5)).
Function Approximation. We reformulate the matrix XS follow:
XS
[
x,e],
where e E IIx is the one vector and ã; E R is the average from (s(i - 1) + 1)-th column to (si)-th column of X.
Next, we focus vector ž; and view its t-th element as the output of a function h h²(t) Zzz. Via analysis in (Gu et al., 2020, Appendixes C and D). we can form an approximation on h (t) as follow:
(x) ~ Σ (d(0)(()))
(14)
where {g:} is sequence of orthogonal polynomial and
cf E R xx satisfy
d c(t)² c(t) Ao
logn n()bbo
(15)
dt
where Ao R* and by E R xx are predefined matrix and vector respectively. Equation (15) is corresponding to the case with A, log in (Gu et al., 2020).
then use Forward Euler approach to discretize
a(ty ē(t 1 Ao) + log h(t)bu.-
1
(16)
17

---

Under review as a conference paper at ICLR 2023
Via standard enror analysis of Forward Euler approach, have
1
d² di2 c(t))es
c(t + 1) c(t)
ce(t) Ao
h(t)bo
+
is log
1
c(t)) c(t) Ao + ts log
h(t)bu
h(g)'bo
Eslog n
c clyy Ao
1
h(1)bo +0
ts log
18 log
where & E [t, + 1]. implies that for = 1, 1,2.....
logt s $log n2
|1(()) - c(t) S o
(17)
Combine (17) with the similar proof procedure in (Gu et al., 2020, Proposition 6), if he (xx) is quadratic spline interpolation { (zzz), obtain
-0 ( (1
Σ =0 =
(18)
The desirable result in Proposition 3 is obtained by repeatedly using (18) with j = 1,,,2 .....
Coefficients via Fourier Convolution. The remaining task is to show that {ā(t)²} be generated via Fourier convolution. To simplify the notation, we denote A = + AA and = flog by and (16) becomes
a(ty é(t 1y h(t)b.
(19)
We then repeatedly use (19) from 1,2,... ... and one may verify
Σ bA h(()
> bA Z3
i=1
C A, (z,e),
(20)
where
b
bA
C
E n2x
and A,
E
RR
(21)
:
bar
Next we repeatedly use (20) from j = 1,2,.., and one has
C
C2
C"l = [A
Ag
Ap]
Die
Uze
F,
== Xomooth
Lo
XS
X smonth Lo XS
X smooth
F ([(Lo)F((X))
X smonth
F- (L. F(XS))
where use the fact that L is constructed in frequency domain in Fourier convolution in Eq. (5).
E MODEL. PARAMETERS IMPACT
SKTformer introduces three extra hyperparameters, r, S1 and $2. We test the influence when varying them and report results in Table 7. We use SKTformer (r", S1, 82 = 8) as the baseline model and other parameters reported in Table 10 in Appendix F.
18

---

Under review as a conference paper at ICLR 2023
Table Experimental results on varying r, $1 and s2. Best result is in boldface and second best is underlined. And Ablation experiments for each components
(a) Experimental results on varying r parameter in smoothing component.
(b) Experimental results on varying #1 parameter in Row Attention.
LisOps
Text
Retricval
Image
Pathfinder
Average
8:
LisOps
Retrieval
Image
Pathiider
Average
37.30
65.25
78.65
51.36
71.23
60,76
8
38, 30
69.27
83.26
53.90
75.82
64,11
8
38.30
69.27
83.26
53.90
75.82
64.11
38.62
70.02
83.21
54.20
76.15
64.44
64
37 88
70.53
83.02
51.22
78.02
64,35
38.19
69.27
82.05
53.73
75.58
63.76
37.33
81.58
37.89
69.73
81.79
51.28
75.52
63.24
256
37.02
65.72
79.30
46.24
78.14
61.29
(c) Experimental results varying 82 param- eter Column Attention.
(d) The SKT (r, 81, 8) is used baseline.
The differences by removing each component from
baseline model are reported.
TisOps
Text
Retrieval
Image
Pathfinder
Average
Model
LisOps
Toxt
Retriecal
Image
Puthlinde
Avenge
1 37.32
55.28
57.37
40.97
66.25
51.44
4
37.82
52.05
72.58
46.74
73.17
57.47
Baseline
38.30
69.27
83.36
53.90
75.82
64.11
8
38.30
69.27
83.26
$3.90
75.82
64.11
Cony.
-5.64
-6.14
16
37.77
70.24
83,42
54.11
77.92
64,73
37.62
68.32
80.11
51.66
78.18
62.98
Columa Amn..
-1.16
-8.00
-9.16
-10.63
-12.45
-8.28
Row Alta.
-0.38
-1.92
-1.97
-2.44
-2.56
-1.89
Influence of r in Fourier Convolution. The parameter used to determine the number of segment-averages to compute in (5). The smaller r leads the matrix with more duplicate columns, and more details information is lost. On the other hand, according Proposition 3, the larger would potently decrease the memorization ability and yield a high approximation error. In Table 7a, 16. For the case with 1, the token matrix
the best performance is observed when r 8 is smoothed to rank one matrix, and the average accuracy drops 3.55 from the best setting. When r value goes larger than 16, the accuracy all experiments slightly decreases. believe due to the over-fitting since the smoothed token matrix contains more flexibility and more irrelevant information training dataset is learned.
Influence of sample number s in Row Attention. In Row Attention part, randomly sample $1 from key and value tokens. Table 7b reports that the optimal sampling amounts are different among tasks. In Pathfinder task, the optimal result is associated with 81 = 256, while the best performance of other tasks the reached with 81 32. Pathfinder task requires learning extreme long-range dependence (the connectivity between two circles far away from each other). The lack of enough tokens leads to inaccurate long-range dependence estimation and damages the final results. For the tasks like Image or Retrieval, the modest range dependence may already be enough to get promising performance, and we thus could use fewer token samples.
Influence of sample number 52 in Column Attention. In Column Attention, $2 columns selected. The experiment results are shown in Table 7c. When setting = 1, average performance decreases by 13.24%. Similar behavior is also observed in the first row of Table 7a with r 1. The information loss due to lack of rankness limits the final performance. In an average sense, = 16 gives the best result, and further increasing 82 slightly harms the accuracy Pathfinder.
tasks except
F EXPERIMENT CONFIGURATIONS
In this section, we report the configurations for the experiments in Sections 4.1, 4.2, and 4.3.
19

---

Under review as a conference paper at ICLR 2023
Table 8: Experiment Configuration SKTformer (r, 81, 82 8).
Parameters
ListOps
Text
Retrieval
Image
Pathfinder
Epoch
$
30
60
100
Learning Rate
le-4
le-4
lc-4
Ic-3
Ic-4
Weight Decay
0
le-2
lc-2
lc-2
le-2
Batch Size
32
32
32
256
256
r, 8,
8,8,8
8,8,8
8,8,8
8,8,8
8,8,8
dropout in embedding
0
0.5
0.1
0.1
dropout in attention
0
0.1
0.1
0.1
0
dropout in smoother
0
0.5
0.1
0.5
0.5
Table 9: Experiment Configuration of SKTformer (best).
Parameters
ListOps
Text
Retrieval
Image
Pathfinder
Epoch
10
30
15
60
100
Learning Rate
le-4
le-4
le-4
le-3
le-4
Weight Decay Batch Size
1-2
le-2
le-2
lc-2
lc-2
32
32
32
256
256
7, 81, 92
8,8,8
8,8.8
8,32,32
8,16,16
8,128,32
dropout in emhedding
0
0.5
0.1
0.5
0.1
dropout in attention
0
0.1
0.1
0.1
0.1
dropout in smoother
0
0.5
0.1
0.5
0.5
Table 10: Experiment Configuration for Model Parameters Impact.
Parameters
ListOps
Text
Retrieval
Image
Pathfinder
Epoch
5
30
15
Learning Rate
le-4
le-4
le-4
le-3
le-4
Weight Decay
0
le-2
le-2
le-2
le-2
Batch Size
32
32
32
256
256
dropout embedding
0.5
0.1
dropout attention
0.1
dropout in smoother
0
0.5
0.1
0.5
0.5
Table 11: Experiment Configuration for Ablation.
Parameters
ListOps
Text
Retrieval
Image
Pathfinder
Learning Rate
le-4
le-4
le-4
le-3
lc-4
Weight Decay Batch Size
le-2
le-2
le-2
le-2
32
32
32
256
256
r. 8..1.82
8,8,8
8,8,8
8,8,8
8,8,8
8,8,8
dropout in embedding
0
0.5
0.1
0.1
0
dropout in attention
0
0.1
0.1
0.1
0
dropout in smoother
0
0.5
0.1
0.5
0.5
G ADDITIONAL RESULTS ON LRA
We have already provided the average of runs with different random seeds in Table 1. Here we also provide the standard deviations for these experiments in Table 12.
H DATASET AND IMPLEMENTATION DETAILS
In this subsection, summarize the details of the datasets used in this paper as follows:
20

---

Under review as a conference paper at ICLR 2023
Table 12:
Accuracy on Long Range Arena (LRA) with standard errors shown in parenthesis. All
results are averages of 5 runs with different random seeds.
Model
LisOps
Text
Retrieval
Image
Pathfinder
SKTformer (r, 81, 82 = 8)
38.30 (0.40)
69.27 (0.83)
83.26 (0.45)
53.90 (1.54)
75.82 (0.97)
SKTformer (best)
39.15 (0.48)
71.58 (0.95)
83.73 (0.61)
57.73 (1.83)
78.20 (1.32)
Table 13: Details of time series benchmark datasets.
DATASET
LENGTH
DIMENSION
FREQUENCY
ETTM2
69680
8
15 MIN
EXCHANGE
7588
9
1 DAY
WEATHER
52696
22
10 MIN
ELECTRICITY
26304
322
1H
ILI
8
DAYS
TRAFFIC 17544
863
1H
LRA datasets: ListOps(2K length mathematical expression task which investigates the parsing ability); Text (up to 4K byte/character-level document classification task that tests capacity in character compositionality): Retrieval (byte/character--evd) document matching task, which exams the information compression ability with two 4K length sequence); Image (pixel-wise sequence image classification based on the CIFAR-10 10 dataset); Pathfinder (long-range spatial dependency identification task. The input images contain two small points/circles and dash-line paths. The model needs to identify whether two points/cireles are connected); LRA has several desirable advantages that made focus it as the evaluation benchmark: generality (only requires the encoder part); simplicity (data augmentation and pretraining are out of scope); challenging long inputs (difficulty enough and room to improve); diversity aspects (tasks covering math, language, image, and spatial modeling); and lightweight (run with low resource requirement).
Time series datasets:1) ETT (Zhou et al., 2021a) dataset contains two sub-dataset: ETTI and ETT2, collected from two separated counties. Each of them has two versions of sampling resolutions (15min 1h). ETT dataset contains multiple time series electrical loads and one time sequence of oil temperature. 2) Electricity* dataset contains the electricity consumption for more than three hundred clients with each column corresponding to one client. 3) Exchange (Lai et al., 2018) dataset contains the current exchange of eight countries. 4) Traffic dataset contains the occupation rate of freeway systems in California, USA. 5) Weather dataset contains 21 meteorological indicators for a range of one year in Germany. 6) Illness dataset contains the influenza-like illness patients in the United States. Table 13 summarizes all the features for the six benchmark datasets. They are all split into the training set, validation set and test set by the ratio of 7:1:2 during modeling.
The GLUE benchmark covers various natural language understanding tasks and is widely used in evaluating transfering ability. The tasks can be devided in two types, single-sentence tasks (SST-2 and CoLA), and sentence- pecennce-piirraee tasks (MNLI, the same settings (Devlin al., 2018), we exclude WNLI task.
GLUE datasets:
Following
I EXPERIMENTS ON THE SMOOTHNESS EFFECT OF FOURIER CONVOLUTION
In this section, we verify Fourier convolution component in the Smoother block can reduce the incoherence value in the early training stage. We use SKTformer with (r, 81, = 8) the test model and test on an NLP dataset: Text, and a vision dataset: Pathfinder. We compute the μ- incoherence value of the token matrix before and after the Fourier convolution (denoted μ
https://archive.ce..i....o wttps//.....ttteaaaaaaccceteeaad "htt:://pems.doo wwt.ca.goo.oooooooooo
20112014
hhtpp:://ww.bggg wwwp://wwww..jjjaaaa.a..aaa wen..mpp..aa.meemee...e......aae de/wetter
"https://gis.cde www..dd...o...... wttasp//tuviieftppttaaaaadd
Incoherence defined by Definition in Appendix B.
21

---

Under review as a conference paper at ICLR 2023
and jxxemoeth, respectively) for each samples in the validation dataset. Since we do not explicitly force the token matrix to be low-rank required by Definition 1, we report the incoherence value for different rankness settings (rank 16 and rank 32) approximately, and the mean and standard deviation of incoherence value can be found in Table 14. The average incoherence value reduced 30% after the Fourier convolution in both datasets. Moreover, We observe that the standard deviation significantly decreases, which suggests the Fourier convolution may also potentially stabilize the training procedure.
Table 14: The average incoherence parameters after 100 training steps with standard errors shown in the parenthesis.
Dataset
px (rank 32)
smoohh (rank 32)
μX (rank 16)
Mx (rank 16)
Text
2.75 (0.027)
2.05 (0.007)
3.98 (0.046)
3.23 (0,038)
Pathfinder
3.83 (0.221)
1.99 (0.001)
4.88 (0.264)
3.48 (0.001)
J ILLUSTRATION ON EFFECT OF THE SMOOTHER AND SKELETON ATTENTION IN TOKEN MATRIX
In this section, an illustration of the Smoother and Skeleton Attention part is shown Figure 2. We smooth the input token matrix ensure the sampling in rows and columns containing more local and/or global information. Thus, sampling several rows and columns from the smoothed token matrix can be more effective than the samples from the original token matrix.
Row Attention
Column Attention
Smooth
Sample in Row and Column
Figure 2: Illustration effect of the Smoother and Skeleton Attention on Token Matrix.
K TRANSFER LEARNING
Table 15: The training configurations for Pretraining and GLUE tasks
Pre-training
GLUE
Max Steps
1000K
Max Epochs
[4,20]
Learning Rate
le-4
[ee-5
Batch Size
256
[16,32]
Warm-up Steps
5000
Sequence Length
512
128
Learning Rate Decay
Linear
Clip
Dropout
22

---

Under review as a conference paper at ICLR 2023
L EXTRA ALGORITHMS FOR LONGTERM TIMESERIES FORECASTING
Table 16: multivariate long-term series forecasting results six datasets with input length of 96 and prediction length O E {96, 192, 336, 720) (For ILI dataset, we set prediction length O E {24, 36, 48, 60)) with input length 60. A lower MSE indicates better performance. All experiments are repeated 5 times.
Methods
SKTTommer
FEDlormer
Autiformmr
S4
Informer
LogTrams
Refirmer
Performer
Nystrolormer
Metric
MAE
MAE
MAE
MAE
MSE
MSE
MSE
F1TTm2
96
0.192
0.283
0.203
0.287
0.255
0.339
0.705
0.690
0.365
0.453
0.768
0.642
0.658
0.619
2.520
1.220
0.617
0.600
0.324
0.328
0.340
0.989
1.078
0.949
0.856
336
0.324
0.364
0.325
0.366
0.339
0.372
1.364
0.877
1.363
0.887
1.334
0.872
1.549
0.972
1.701
1.001
1.394
0.887
720
0.431
0.433
0.421
0.415
0.422
0:419
0.877
1.074
3.379
1,358
3,048
1.328
2.631
1.242
2,531
1.228
2.466
1.185
Ellctricity
96
0.218
0.532
0.183
0.297
0.201
0.317
0.304
0.405
0.274
0.368
0.258
0.357
0,312
0.402
0.281
0.375
0.273
0.364
192
0.259
0.361
0.195
0.308
0.222
0.334
0.313
0.413
0,296
0,386
0.266
0.368
0.348
0.433
0.283
0.387
0.288
0.370
336
0.267
0.367
0.212
0.313
0.231
0.338
0,290
0.381
0.300
0.394
0,280
0.380
0,350
0,433
0,301
0.387
0.302
0.387
720
0,293
0.385
0.231
0.343
0,254
0.361
0,262
0.344
0,373
0,459
0,283
0.376
0.340
0,420
0,301
0.387
0.292
0.373
Exchange
0.086
0.204
0.139
0.276
0,197
0.323
1.292
0.849
0.847
0.752
0.968
0.812
0.829
0.801
0.729
0.801
0.729
192
0,188
0.292
0.256
0.369
0,300
0.369
16631
0.968
1.204
0.895
1,040
0.851
1. 1.188
0.906
1,284
0,925
1.284
0.925
0.433
0.464
0.524
1,672
1.357
1.408
720
0.727
0.669
1.090
0.800
1.447
0.941
2.521
1.245
2,478
1.310
1.941
1.127
1.510
1.016
1.654
1.017
1.654
1.017
0.592
0.352
0.388
0.732
0.709
0.709
Weather Traffic
192
0.583
0.343
0.562
0.346
0.616
0.382
1.106
0.672
0.696
0.379
0.685
0.390
0.733
0.420
0.681
0.369
1.127
0.611
336
0,598
0.346
0.570
0.323
0.622
0.337
1,084
0.627
0,777
0.420
0.733
0.408
0.742
0,420
0.682
0.366
0.867
0.477
0.641
0.397
0.596
0.368
0.660
0.408
1,536
0.845
0.864
0.472
0.717
0.396
0.755
0.423
0.675
0.360
0.686
0.369
96
0,182
0.262
0.217
0.296
0,266
0.336
0.406
0.444
0,300
0,384
0,458
0.490
0.689
0.596
0.597
0.598
0.701
0.612
0.228
0.306
0.336
0.367
0.527
0.658
0.589
0.606
0.587
0.655
336
0.295
0.355
0.339
0,380
0.159
0.395
0.531
0.539
0.578
0.523
0.797
0.652
0.639
0.596
0.731
0.646
0.746
0.642
0.418
0,428
0.578
0.428
0.741
1.130
0.837
0.961
24
2.185
0.926
2.203
0.963
3.483
1.287
4,631
1-484
5,7641
1.677
4,480
1.444
4,400
1.382
3.937
1.298
4.378
1.364
2.155
0.937
0.976
1.148
1.348
4.755
1.467
4,799
4.783
4.007
1.329
5.332
1.554
2.333
0.954
2.209
0,981
2.669
1.085
4.066
1.36
4.763
1.469
4,800
1.468
4.832
1.465
4.575
1.451
5.575
1.614
2.018
0,958
2.545
1.061
2.770
1.125
4,278
1,41
5,264
1,564
5,278
1.560
4,882
1,483
4,020
1.366
4.742
1.469
23


Reviews:
[{"review_id": "o_1SyhoRZk", "reviewer": "Reviewer_ELnS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a novel SKTformer for long sequence modeling, which reduces the complexity of the vanilla transformer based on the Skeleton approximation. There are two major novelties: Skeleton attention and Fast Fourier Transformation-based smooth convolution. Theoretically, analysis is provided to show the proposed model could reduce the complexity. The experimental results show that SKTformer could outperform existing methods to a certain degree.", "summary_of_the_review": "In general, this paper introduces a novel SKTformer to reduce the complexity of the Transformer. Theoretical analysis is provided and the empirical results demonstrate the effectiveness of SKTformer. However, SKTformer does not consistently outperform SOTA baselines. Thus, it is necessary to conduct t-tests. ", "strength_and_weaknesses": "Strengths:\n1. The proposed Skeleton attention and Fast Fourier Transformation based smooth convolution is novel.\n2. Theoretical analysis is provided to demonstrate SKTformer could reduce complexity and retain sufficient information.\n3. The experimental results show that SKTformer could outperform SOTA methods to a certain degree.\n\nWeaknesses:\n1. It is necessary to perform t-tests for SKTformer since it does not consistently outperform SOTA methods.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "m8JBCTxqEy5", "reviewer": "Reviewer_9G8D", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Through multiple iteration of rebuttal, the authors have provided empirical evidence to address my concern. I am willing to raise my score to 6, conditioned on polishing the method section. The following are my original review:\n\nThis paper proposes to sample rows and columns of key and query matrices to approximate attention matrix in transformer layers. The authors argue that if these matrices are smooth enough, then the downsampled matrix should retain most information. Therefore, the authors propose to smooth input by convolving it with some learnable kernel.", "summary_of_the_review": "This paper has major clarity issues and cannot justify its correctness.", "strength_and_weaknesses": "Clarity is a major concern. The theoretical arguments are decorative but of little relevance and significance. In fact, the lemmas harm clarity. They do not help answer the key question: \"why should we smooth the key matrices?\" We all know that smoothed matrices are easier to approximate via sampling. However, after all, approximating the matrix is not the purpose of learning representations.\n\nEven if we assume smoothing is really helpful, there is still major unclearness in method development. Section 3.2.1 aims to design an efficient smoothing method. However, it is very hard to read. In specific, I don't see why Eq (5) can approximate Eq (4). The $S$ matrix in Eq. (5) essentially applies an averaging pooling mask along the feature dimension. Its effect is unexplained. Note that lemma 2 and 3 do not provide an answer.\n\nAlso, the smoothing is applied to the input, whereas eventually we need smoothed keys and values. There are linear transforms that map input to keys and values. does smoothed input necessarily lead to smoothed keys and values?\n\nMinor: Lemmas are for proving major theorems. But here the authors mainly want to argue for correctness. I'd suggest change \"lemma\" to \"proposition\".", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "V4PuY6RQjD7", "reviewer": "Reviewer_FKSC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new approach to apply transformers to Long Sequence Data, called SKTFormer. The approach combines a CUR matrix approximation technique, a Fourier-convolution based smoother, and a convolution stem to avoid over-smoothing. The authors apply their method to a number of problems, showing promising performance; they also report ablation study results, analyzing the importance of different components of their method.", "summary_of_the_review": "Generally, the paper addresses an important problem, and runs a number of reasonably planned experiments, supplementing them with theoretical results. \n\nIts main issue is the way experimental results are reported. Contrary to how most previous papers approached the topic (see Long Range Arena original paper, section 3.2 \"Philosophy Behind the Benchmark\"), authors fine-tuned the major hyperparameters for each subtask in the Long Range Arena. Given that these hyperparameters do have a major impact on performance (see table 7), such reporting may create a confusing picture of how good the method actually is, and make it harder to compare it with both previous and future results. The authors report a fixed hyperparameter version, but only as a secondary metric, and I suggest that it is reported more clearly either along or instead of the fine-tuned one, e.g. in the abstract and other parts throughout the paper. \n\nAdditionally, even though Appendix G gives the performance variability for each subtask in LRA, it is not mentioned in the main text and does not give the variability of the overall result, which is the most important part (I strongly suggest that it's included for reader's convenience, especially since it can be calculated assuming independence at no additional computational cost).\n\nOverall, however, the pros outweigh the cons, and I believe that the paper is above the acceptance threshold, although, unless the issues above are fixed, I believe that it's borderline. I will stay open to adjust my assessment based on the rebuttal and other reviewer's comments.\n\n** UPD **\n\nI have read other reviews and the authors' responses. They alleviate many of the concerns voiced by me and other reviews. In my opinion, I can not quite improve the score to an \"8\", but I would have given the paper a \"7\" if I could.", "strength_and_weaknesses": "Strengths:\n- The paper addresses a highly important problem\n- The proposed method shows good results on a sufficiently wide range of problems\n- Experiments are thorough, and ablation results are reported\n- The paper is generally clearly organized\n\nWeaknesses:\n- The most impressive results are achieved when hyper parameters of the proposed method are freely varied for each subtask. It may be creating an overly optimistic impression of the model performance. I'd prefer a higher emphasis on the performance of the fixed hyperparameter version (i.e. SKTformer (r, s1, s2 = 8)). For the benchmark used (Long Range Arena), it goes contrary to the established approach.\n- Performance variability from run to run is not reported fully (its reported in the appendix for LRA substasks, but not for the overall performance, and is not referenced in the main text).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "T7B_i9hto8", "reviewer": "Reviewer_6UUx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an efficient transformer architecture, a skeleton transformer (SKTformer), for modeling long sequence data. It contains two main components: a smoothing block to mix information over long sequences through Fourier convolution, and a matrix sketch method that simultaneously selects columns and rows from the input matrix for efficient self-attention. Theoretical and experimental analyses of the proposed method are provided and its performance is validated compared to other Transformer variants on several tasks.", "summary_of_the_review": "The novelty of the proposed method for efficient self-attention attention and other mechanisms introduced could inspire the readers. Also, the authors have conducted many experiments for validation. My concern is mostly on the selection of comparison methods shown in some of the experiments.  If these concerns can be resolved, I think it's worth being introduced at this conference.  ", "strength_and_weaknesses": "[+] This paper proposes a novel idea for modeling long sequences and its performance is well-validated through extensive experiments. \n\n[+]  The idea of using a subset of rows or columns for self-attention and combining both is interesting. It reduces computational complexity and also improves overall performance. It seems meaningful that the proposed model is not only computationally efficient but also robust against noise. \n\n\n[-] The choice of models for comparison is not consistent across Tables. For example, Nystroformer and Performer show good train speeds in Table 4 but are not included in Table 2. There is a tradeoff between performance and computational complexity, so a clearer explanation of why the chosen methods are used in each experiment will make the comparison fairer. \n\n[-] Because the advantage of this model is that it has high computational efficiency as well as good performance, I think it is good to add models with higher performance than the models proposed in the training speed experiment as a baseline model.\n\n[-] The description of the theoretical analysis could be improved. For example, Lemma 1 is included in the last part of section 3.1: skeleton attention, but it’s not well explained in the context of 3.1. In addition, since the concept of mu-incoherence might not be familiar to some readers, it’d be better to introduce it near Lemma 1 in the same section, before using it in a later part. It's defined in the supplementary but not mentioned in the main manuscript. \n\n[-] Table 6 is not referred to elsewhere in the manuscript. \n\n[Q]. The choice for the value of hyperparameters such as s1 and s2 in combination with other hyperparameters seems to affect the performance much. Is there a guideline or suggestion about an efficient search strategy? \n\n[Minor] \n- In abstract: villain -> vanilla\n- Section 4.4, 2nd line: SKTformer achieve -> SKTformer achieves\n- Section 5, 1st line: n robust and efficient transformer architecture -> a robust and efficient transformer architecture\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject