A Primal-Dual Framework for Transformers and Neural Networks
Authors: Tan Minh Nguyen
Tam Minh Nguyen
Nhat Ho
Andrea L. Bertozzi
Richard Baraniuk
Stanley Osher
Venue: ICLR 2023 notable top 25% (2023)
Keywords: attention
transformer
neural network
support vector regression
primal
dual

Abstract: Self-attention is key to the remarkable success of transformers in sequence modeling tasks including many applications in natural language processing and computer vision. Like neural network layers, these attention mechanisms are often developed by heuristics and experience. To provide a principled framework for constructing attention layers in transformers, we show that the self-attention corresponds to the support vector expansion derived from a support vector regression problem, whose primal formulation has the form of a neural network layer. Using our framework, we derive popular attention layers used in practice and propose two new attentions: 1) the Batch Normalized Attention (Attention-BN) derived from the batch normalization layer and 2)  the Attention with Scaled Head (Attention-SH) derived from using less training data to fit the SVR model. We empirically demonstrate the advantages of the Attention-BN and Attention-SH in reducing head redundancy, increasing the model's accuracy, and improving the model's efficiency in a variety of practical applications including image and time-series classification. 

Published as a conference paper at ICLR 2023
A PRIMAL-DUAL FRAMEWORK FOR TRANSFORMERS
AND NEURAL NETWORKS
Tan M. Nguyen Department of Mathematics University of California, Los Angeles Sammnguyen@9@uca....
Tam Nguyen Department of ECE Rice University
www.yeeminhttmm522888e .com com
Nhat Ho
Andrea L. Bertozzi
Department of Statistics Data Sciences University of Texas at Austin mi minhnhatt@uexxas edu
Department of Mathematics
University of California, Los Angeles
bertozzi @ma thathhhn uula edu
Richard G. Baraniuk**
Stanley J. Osher
Department of ECE
Department of Mathematics
Rice University
University of Califoria, Los Angeles s sjo@math. ucla edu
ri richbe ri rice... .eu
ABSTRACT
Self-attention is key to the remarkable success transformers in sequence model- ing tasks including many applications in natural language processing and computer vision. Like neural network layers, these attention mechanisms are often developed by heuristics and experience. To provide a principled framework for constructing attention layers transformers, we show that the self-attention corresponds to the support vector expansion derived from support vector regression problem, whose primal formulation has the form of neural network layer. Using our framework, we derive popular attention layers used in practice and propose two new atten- tions: 1) the Batch Normalized Attention (Attention- -BN)) derived from the batch normalization layer and 2) Attention with Scaled Head (Attention-Si) derived from using less training data to fit the SVR model. We empirically demonstrate the advantages of the Attention- BN and Attention -Ho in reducing head redundancy, increasing the model's 's accuracy, and improving the model's 's efficiency in variety practical applications including image and time-series classification.
INTRODUCTION
Transformer models (Vaswani al., 2017) have achieved impressive success with state-of-the-art per- formance in a myriad of sequence processing tasks, including those in computer vision (Dosovitskiy al., 2021; Liu et al., 2021; Touvron al., 2020; Ramesh et al., 2021; Radford al., 2021; Arnab et al., 2021; Liu et al.. 2022; Zhao et al., 2021; Guo et al., 2021), natural language processing (Devlin
al., 2018; Al-Rfou al., 2019; Dai et al., 2019; Child et al., 2019; Raffel et al., 2020; Baevski &
Auli, 2019; Brown et al., 2020; Dehghani et al., 2018), reinforcement learning (Chen et al., 2021;
Janner et al., 2021), and other important applications (Rives et al., 2021: Jumper al., 2021: Zhang et al., 2019; Gulati et al., 2020; Wang & Sun, 2022). Transformers can also effectively transfer knowledge from pre-trained models to new tasks with limited supervision (Radford et al., 2018: 2019; Devlin et al., 2018; Yang et al., 2019; Liu et al., 2019). The driving force behind the success of transformers is the self-attention mechanism (Cho et al., 2014; Parikh et al., 2016; Lin et al., 2017), which computes weighted average of feature representations of the tokens in the sequence with the weights proportional to similarity scores between pairs of representations. The weights calculated by the self-attention determine the relative importance between tokens and thus capture the contextual representations of the sequence (Bahdanau et al., 2014; Vaswani et al., 2017; Kim et al., 2017). has
CCo-firtt authors. Co-last authors. Please correspond tanmnguyen89@@ull..de

---

Published as a conference paper at ICLR 2023
been argued that the flexibility in capturing diverse syntactic and semantic relationships is critical for the success of transformers (Tenney et al., 2019; Vig & Belinkov. 2019; Clark et al., 2019).
1.1 BACKGROUND: SELF-ATTENION
For given input sequence X [= _NI
RNXD= of N feature vectors, self-attention
transforms X into the output sequence H in the following two steps:
Step 1. The input sequence X is projected into the query matrix Q the key matrix K, and the value matrix V via three linear transformations
Q = XW Qi K X XWT,
where W Qq
Wx K E R DxD= and Wv E D. are the weight matrices. We denote Q := 41 ... qN K = k,, , and V == [0 uNy'" where the vectors qı ks 2/ for
N are the query, key, and value vectors, respectively.
Step 2. The output sequence = [h1, ... hN]
T is then computed as follows
H softmax QKK /VD/ :- AV,
where the softmax function is applied to each row of the matrix QK /VD. The matrix A softmax OK T
ERN NXN and its component aij for i, j -- 1, NN are called the attention matrix and attention scores, respectively. For each query vector qi for = 1, .. .N, an equivalent form of Eqn. (1) to compute the output vector h; is given by
h; Σ softmax (g.
(2)
The self-attention computed by Eqn. (1) and (2) is called the scaled dot-product softmax attention. In our paper, we call a transformer that uses this attention the softmax transformer. The structure that the attention matrix A learns from training determines the ability of the self-attention to capture contextual representation for each token. Additionally, residual connection can be added to the
output of the self-attention layer, h, = 24 + Σラ= softmax
k Rt//VD) v/--
Multi-head Attention (MHA). In MHA, multiple heads concatenated compute the final output. This MHA mechanism allows transformers to capture more diverse attention patterns and increase the capacity of the model. Let H be the number of heads and Wmmiiti (Wo-- O:.... W RDD DD.xHD,
be the projection matrix for the output where W1 O....y W IR D., The MHA is defined
MultiHead (H) H a=)) = Concat
Σ
H'W = AA'' (3)
a=1 Despite their remarkable success, most attention layers developed based heuristic approaches, and coherent principled framework for synthesizing attention layers has remained elusive.
1.2 CONTRIBUTION
We derive the self-attention as the support vector expansion of a given support vector regression (SVR) problem. The primal representation of the regression function has the form of a neural network layer. Thus, we establish a primal-dual connection between an attention layer in transformers and neural network layer in deep neural networks. Our framework suggests principled approach to developing an attention mechanism: Starting from a neural network layer and a support vector regression problem, we derive the dual as a support vector expansion to attain the corresponding attention layer. We then employ this principled approach to invent two novel classes of attentions: the Batch Normalized Attention (Attention- BNN) derived from the batch normalization layer in deep neural networks and the Attention with Scaled Heads (Attention-She SHH) resulting from solving the support vector regression model with less amount training data. Our contribution is three-fold.
1. We derive self-attention as a support vector expansion that solves a SVR problem, thus providing a principled primal-dual framework to study and develop self-attentions.
2. We re-derive popular attentions, such the linear attention (Katharopoulos et al., 2020). the sparse attention (Child et al., 2019), and the multi-head attention (Vaswani et al., 2017), from proposed framework.
2

---

Published as a conference paper at ICLR 2023
3. We develop two new attention mechanism: the Batch Normalized Attention (Attention-Bi) and the Attention with Scaled Heads (Attention-SH) using our proposed framework.
We empirically demonstrate that 1) the Attention-BN significantly outperforms the baseline softmax and linear attention and 2) the Attention-SH performs better while being more efficient than the same baselines on a variety of practical tasks including image and time-series classification.
2 HEMAL-DUAL INTERPRETATION OF SELF-ATTENTION
We first provide a primal-dual interpretation of self atff-attention as a support vector regression problem in Section 2.1. Based on that primal-dual framework, derive popular attention mechanisms as the support vector expansion in Section 2.2. Finally, we introduce two new attention mechanisms in Section 2.3, the Attention-BN and Attention-SH.
2.1 ATTENTION AS A SUPPORT VECTOR REGRESSION MODEL
In this section, derive self-attention from a support vector regression problem. Suppose we given a training data {(k), yn...... (kx yN)) C K. x V, where K. = RD and y = IR.,. Here, ki...., ky are attention keys in self-attention, and y1...... yN are the training targets. We consider the function f, taking the form
y = f(x) = W ((x)
+ b, h(x)
where K = RP, ((x) (.) b RDD, and h(ar) is vector-scalar function. We fit the function to the training data {(k), yi).... (KN, Dv)} with an IL regularization on W, i.e. ridge regression, by solving the following convex optimization problem:
[x)]
R Ds W = wW w WD.I "p.l E RoxPe
N De
D. Σ
N Dg Σ
minimize W
WIF + +C
Σ
wall 2 +C
+E)())
2 d=1
j=1
j=1d=1
(d) T 2 (k2))/((k)))) b(d) s (d) w. (k,)) ()(k)))))))))))))))))))))))))) + b(d)) (d(d) & (d)
subject to
,J= I,..,,,,, N,, ===1,,. I,..., Dv.
(d), (d) 20
(5) The Eqn. 5 implies that there exists a function that can approximates all pairs (k,, yj) with precision. The additional slack variables Ej. E, relax this assumption and allows some of the training set data points to have the training error greater than just in the soft-margin SVM (Cortes & Vapnik, 1995; Schölkopf et al., 2002). C > complexity penalizer Ee= || i.e., the flatness of f, and the amount up to which deviations larger than are tolerated.
is constant determining the trade between the
In order to derive the self-attention from the support vector regression defined by the optimization problem 5, the key idea construct the Lagrangian from Eqn. and find the representation of the Wa. d = 1, I,..., Dr, in terms of the dual variables. We define the Lagrangian function as follows:
D.
N D2
N
L:
+C
Ed(d) + +((()) - ΣΣ
(1))))
2
d=1d=1
d=
N D.
( (dd) - (d(() + +w (kk))
aj(d)
+ b(d)
(6)
h(kk))
==
N D. ΣΣ (d) j=1d=1
+ (d) (d) w $ (k))
b(d))
h(k,)
where 77, ni. aj and â are Lagrange multipliers. These dual variables have to satisfy positivity
constraints, i.e., ni n (d), (d),, (d) 2 0, vj=jj l,,.., N,, Vd 1,..., D,. It follows from the saddle point condition that the partial derivatives of the Lagrangian function L with respect to the primal variables (wa, b(d), (d), (d)) .d = I,..., D., have to vanish for optimality,
3

---

Published as a conference paper at ICLR 2023
namely, we have:
N Ooca ((as(d)-ay(())) = (a)(d)-(a((()) = =0,
N
j=1
j=1
Σ (d) - -d)(d)) ((kk))
N
N
((k;))
Ow = wd -
hi(k;) = 0 = wt = > (a)(d) - -āz(d)
(8)
h((k;)
j=1
j=1
(d) =C -a,(d)- - 7j (d) = 0, (a) C C (d(d) (,(d) =0
(9)
(1, a, (,(D,) - (T j ,..., N, and substitute Eqn. 8 into Eqn.
Let 1 h(kk)
k(k,)
obtain the following support vector expansion of the linear basis function f:
N
(1) - (1) ((x))
( (k,)
ag (D.) -ā,( 2(x)) ( (kk) h(kg)
f(z)
+ +,,
h(k,)
h(x)
h(x)
4 (x) T ((k;))
Uj +b
(10)
h(x)
Remark Notice that from Equ. and the conditions ny (d), nj (d), ar ad(d), ā,(d) 2 we can prove that (y(d), ay(d) C). Furthermore, can show that a (d) Cg (d) 0 (Smola & Schölkopf, 2004; Schölkopf et al., 2002). As result, vy(d) k(ky) 2 k(k,)
C C d 1, D...
Deriving Softmax Attention. Choosing the appropriate h(x) and ((x) allows us to derive the popu- lar softmax attention given in Eqn. and 2. In particular, if we choose h(x)) = ΣS (1x) Eqn. 10 becomes
((x) (k₂)
Dj + bb= Σn ((x) (kk))
((x)
+ b.
(11)
1=1 Eg ((x) (Kk)))
Σ ((
We then select ((x) = 1o ai
(0) (1)
(1)
,.... where 4, = (D+--1) and
(t) (11/ / mD (ED/ VD
... + uD = 15 4
(12)
Vni... un!
Since
exp
[ T y)
(x"y)'
Σ
Vnn.... .......p!
I1 .... nn!
vi ... VD
(13)
t! 1=0 my tab=t
Vnnl.. nn!
then Eqn. 27 becomes N
exp (x k//VD)
N
f(x) Σ
=1=100 exp (x ky/VD) Uj +b +
Σ softmax (xTKy/VD) Uj +
(14)
expeepp
Let qi. b = O and relax the boundness constraint of B in Remark 1. Eqn. 30 becomes Eqn. 2 of the softmax attention (Vaswani et al., 2017). We summarize our results in the following theorem.
Theorem (Softmax Attention a Support Vector Expansion) Given the function f defined in Eqn. 4 with h((x:) == Σ3 (ax) t (k,) and the support vector regression problem defined in Eqn. 5, we set b = O, choose ((x) as in Eqn. 28, and relax the boundness constraint of the variables Uj = (1) ..... (D ( k(k:,)
where a and o, are dual variables of Eqn. 5. ==jl I....,N. Then, the support vector expansion of f derived from Eqn. 5 has the form of a softmax attention
k(k,)
[(x) Σ softmax (xr (oT (oTk:/VD) vg-
(15)
Remark 2
Since is set O, the centering constraint of oij and ō, in Eqn. can be ignored.
Remark 3 Theorem 1 and its derivation can be easily extended capture the form of the softmax attention with the residual connection, the query matrix projection W Q. the key matrix projection W k, and the value matrix projection Wv. We include this result in Appendix F.
4

---

Published as a conference paper at ICLR 2023
Remark 4 The prinal representation the function in Eqn. 4 has the form of neural network layer where W is the weight, b is the bias term, ((x) is the input, and h( (x)) is the normalization term. Thus, attention layer and neural network layer primal-dual of each other.
principled approach to developing an attention mechanism. The observation in Remark suggests a principled way to construct an attention layer: Starting from neural network layer and a support vector regression problem, we derive the dual as a support vector expansion to altain the corresponding attention layer. Using this approach, we derive popular attention mechanisms in Section 2.2 and propose our new attention mechanisms in Section 2.3.
2.2 DERIVING POPULAR ATTENTION MECHANISMS AS THE SUPPORT VECTOR EXPANSION
In this section, we derive popular attentions such as the linear attention (Katharopoulos et al., 2020), the sparse attention (Child al., 2019), and the multi-head attention (Vaswani et al., 2017).
2.2.1 LINEAR ATTENTION
The Eqn. 27, which is obtained when choosing h(x=)= Σj (())"<(k)))))))) already matches the formula of the linear attention. Here, we can let b above and select the function t that results in positive similarity function, e.g. (x)) = clu(x) + 1, as in (Katharopoulos et al., 2020).
2.2.2 SPARSE ATTENTION
The sparse attention (Child et al., 2019) can be derived by fitting the function f in Eqn. 4 using a differ- ent subset {(km=(1): (1)) .., (Dt); (m)) of training data {(k,, yi),..., (KN, yN)} for each input data æ, where Ma {mo .....,................. m. (M)) C {I....,N} NJ. The support vector expansion of f is then given by
N
F(x)) (kkg)
f(x)
Σ
( (i)
Dj +
(16)
h(x)
f=1
where M. = M²] = [ Ma
Note that the subsets Ma are different for
otherwise
different When letting qi where q: i- N. are the query vectors and choosing &, h, b as in Section 2.1, we can obtain sparse attention in (Child et al., 2019) where the binary matrix
M (IM ())) lf=1 becomes the sparse masking matrix.
2.2.3 MULTI-HEAD ATTENTION (MHA)
The MHA can be derived by solving multiple support vector regression problems and then linearly combining their outputs. In particular, given H training datasets {(k), y!)...,, , (k ,,))...,, {k&f "f", )...... (K } C KKX where K. = Rº and y
RP. We define the function f applied on the input vector [x [x',...,""] as follows
W T TT('')) Σ W
y= f(x) Σ Wov" = = w Wof
h" + bz
(17)
where each function (=(x))
W (x')
+ ba is fitted to the training dataset
h"(=")
{(ki, yf)...., (k ). Following the same derivation and choosing {Ø*, h², b" in Sec- tion 2.1, we can rewrite f(x) in terms of the support vector expansions of the individual functions f*(x") which are the individual softmax attentions
(x(x') 1 (k;))
H
f(x)
W
05 + b"
WO
Σ
softmax (x. (TTT///V)
Vj
(xxx))
(18)
Comparing Eqn. 18 and Eqn. 3, we see that Eqn. 18 computes the MHA when choosing x= where qf, I,..,,N, N, are the query vectors at the 4t head.
-
2.3 DERIVING NEW ATTENTION MECHANISMS: BATCH NORMALIZED ATTENTION AND MULTIRESOLUTION HEAD ATTENTION
In this section, we employ our primal-dual framework to develop new attention mechanisms. In par- ticular, we derive: 1) the Batch Normalized Attention from employing the batch normalization (Ioffe & Szegedy, 2015); and 2) the Attention with Scaled Heads from using different amounts of training data. By 1) and 2), we demonstrate that new attentions can be invented by modifying the primal neural network layer and the support vector regression problem in our framework, respectively.
5

---

Published as a conference paper at ICLR 2023
2.3.1 BATCH NORMALIZED ATTENTION
We incorporate the batch normalization into the primal form of the function f in Eqn. Given training data (1),91),.... y1),..., (kv, yN'} C K. x V where K. = IR and y Dv as in Section 2.1, the resultant/ f is defined as follows
[(x) = W Φ((x 14) 2 ssss
(19)
h((2 14) 2 1-
where
N N
N Σ (k)(d) -(d()) (20)
1
Vo +
oo +
N
Here, d = I,...,, D, and the mean subtraction and division by the standard deviation is performed element-wise along the feature dimension of æ. Following the same derivation as Section 2.1, we derive the following support vector expansion of
c((2 11) C S TT((T(())))))) 15)
f(x)
Uy + b.
(21)
h((x 11) 1
where a, and Ø5 are the dual variables, j = 1, ...... ... Same in Section 2.1, in Eqn. 21, we choose + in Eqn. 28, h(z) == ΣS (x)))((k))
Here, Vj (1) (1)
a. a, (D.)
h((k; 14
A((R; 1000
and b 0 to obtain the the Batch Normalized Attention, which is defined as follows.
Definition (Batch Normalized Attention) Given a set of the key and value vectors (kj, 0j و for each query vector qu = I,...,N, NN the Batch Normalized Attention (Attention-BN) computes the corresponding output vector h4 of the query qi by the following attention formula:
N
h softmax ((a: 14) :s ((ke 1)) os ())D) Ez.
(22)
where
N N
N N
kz,
0
Σ
(kg(d) - u(d))
(23)
Vot
+
Voh +
The Effect of Normalization. Expanding the dot product in the Attention-Be BN (see Appendix E), Eqn. 22 becomes
N
(d)) 1 N ky
h; Σ softmax
Uz.
(24)
VD c))
Eqn. 24 implies that in the Attention-BN, the similarity between the query qi and the key k, is adjusted by the similarity between the key k, and all the keys ky. I,...,N, N. In particular, if the key kj is too similar to other keys, the query qi will attend to it less and vice versa.
2.3.2 ATTENTION WITH SCALED HRADS
The Attention with Scaled Heads, named Attention-SH, is derived based on the derivation of the MHA in Section 2.2.3. The key idea underlying the Attention-SH is to train multiple sup- port vector regression problems using different amounts of training data. Attention-SV SH follows Eqn. 17 in Section 2.2.3 and defines the same regression function f as the MHA. However, the Attention-SH fits the function f², $ 1,...,, H. in Eqn. 17 with training sets {(kt, vt),..., (, y }},........,. ..., {(ff f )..., N vN C K. y of different sizes Ni...., NH, where I. RD. and y R.P. The resultant support vector expansion yields the formula of the Attention-SH as in the following definition.
particular, the
Definition (Attention with Scaled Heads) Given H sets of the key and value vectors (k), " (k
o Nu jj=v for each set of H query vectors ......,hht i= =1 I, the Attention with Scaled Heads (Attention-Sh) computes the corresponding output vector h; of the queries q......f d by the following attention formula:
H
N₂
h2 = Σ W
Σ
softmax (oiTk//VD)u)
(25)
1

---

Published as a conference paper at ICLR 2023
Table I: Test Accuracy (%) of the Attention BN/SH/BN+SH vs. the baseline softmax attention on a subset of the UEA Time Series Classification Archive benchmark (Bagnall et al., 2018). Our proposed attentions significantly outperform the haseline. We also include the reported results from (Zerveas et al., 2021) and (Wu al., 2022) (in parentheses) in addition our reproduced results.
Datasct/Model
Baseline Softmax
Attention- BN
Attention-S0
Attention BN+SH
ETHANOL CONCENTRATOO
32.08 + 1.24 (33.70)
33.33 + 0.44
33.59
0.58
34,35 0.53
FACEDETECTION
68.70 + 0.61 (68.10)
68.62 + 0.26
68.83
0.16
68.67 0.13
HANDWRITING
32.08 +: 0.88 (30.50)
33.17 + 0.20
33.29 + 0,42
33,45 0.61
HEARTBEAT
75.77 +: 1.01 (77.60)
76.10 + 0.98
76.25
1.02
76.26 1.07
JAPANESEVOWER
99.46:1:..77 (99,40)
99.55 +:
99,46
0.27
99,55 0.31
PEMS-SE
+2.66+0.551 (82.10)
84.77 + 0.33
83.04
0.86
83.81 0.62
ATIONSSCI
91.46 0.35 (92.50)
91.58 +: 0.33
91.70 + 0.39
92.04 +: 0.36
CELFREGULATIONSCI
54.72 :: 0.74 (53.90)
56.11 0.71
55,93 0.85
57.04 0.82
BROKENARABICDIGIT
99.33 + (99.30)
99.23++000
99.34
0.11
99,42 0.28
WWAVEGESTURELIIXE
84.45 + 0.72 (85.60)
86.46 + 0.81
86.77
0.78
87.60 0.67
AVERAGE ACCURACY
72.07 0,47(72227)
| 72.89 1 0.09
72.82
0.12
73.22 0.33
Remark 5 For a given input sequence X := [a= [ E NxDx of N feature vectors in self-attention, in order to generate the sets of bf N, the input X. before projecting into the key matrix K and the value matrix V. There are multiples approaches to downsampling X, such as using the average-pooling max-pooling, I-D convolution, or K-means clustering. In this paper, we employ the average ppooagg to downsample X.
at the scale 8h, we can downsample
Linear Attention with Batch Normalization and Scaled Heads. The Attention- BN//SH can be extended to use with the linear attention. In particular, in the Linear iieetton-BNNSSEE we replace the softmax kernel in Eqn. 22 and Eqn. 25 by the linear kernel, respectively.
3 EXPERIMENTAL RESULTS
In this section, we empirically demonstrate the advantages of our Attention-BAl Attention-SEe and their combination -BHHH) over the baseline softmax attention the UEA time- series classification benchmark (Bagnall et al., 2018), the Long Range Arena benchmark (Tay et al., 2021), and the image classification task on the Imagenet dataset (Deng et al., 2009; Russakovsky et al., 2015). We aim to show that: (i) Attention-BN significantly outperforms the softmax baseline achieves better or comparable accuracy while saving computation
across tasks; (ii) Attention and memory compared to the baseline; (iii) Attention Attention-BN+SH which combines both Attention -BN and Attention-SiP SH, results in the best model performance in term of accuracy and efficiency; (iv) all our proposed models help reduce the redundancy in multi-head attention and benefit learning of the long-term dependency long input sequences; (v) Attention-BN and Attention-SH can be applied on other attention mechanisms beyond the softmax attention. When combined with the linear attention (Katharopoulos et al., 2020), the resultant Linear Attention- and Linear Attention yield similar advantages mentioned in (i), (ii), (iii) and (iv) over the baseline linear attention.
In our experiments, we compare the proposed models with the baseline softmax and linear attentions of the same configuration. For the Attention BN and Attention-BN+SHI we observe that recentering queries and keys alone is sufficient for improving the model performance. In addition, weighting l with a constant (3, as in Eqn. 26 in the Appendix, enables the Attention-BB/BNN-SS effect of normalization to the attention score and help increase the accuracy. Our results are averaged over 5 runs. Details on datasets, models, and training are provided in Appendix A.
adjust the
UEA Time Series Classification. Table I compares the accuracy of the Attention-BN and Attention- SH with the baseline softmax attention on 10 tasks in the UEA Time Series Classification bench- mark (Bagnall et al., 2018). Both Attention- BN and Attention-SE significantly outperform the softmax baseline on most tasks and on average among all tasks. When combining two models, the resulting Attention-BN-SH yields the best accuracy with more than 1% overall improvement over the softmax baseline. Notably, the Attention-SH and Aitention-BN+SI are much more efficient than the baseline since they need much fewer keys and values in computing the attention output. The efficiency advantage of the Attention-SH/BNNSSI SH/BB+SH is discussed and analyzed in detail in Section 4.
Long Range Arena (LRA) benchmark. In this experiment, we verify the advantage of our methods over the softmax baseline on tasks that involve very long sequences (c.g., the sequence length can be up to 4K) in the LRA benchmark (Tay et al., 2021). Those tasks require the model capture long-range dependency in the input sequence. The summarized results in Table 2 indicate significant improvements of KientionBNNSSH/BS.
over the baseline softmax attention. Same as in the UEA
7

---

Published as a conference paper at ICLR 2023
Table 2: Test Accuracy (%) of the Attention BN/SH/BN+SH vs. the baseline softmax attention on the LRA benchmark (Tay et al., 2021). Our models significantly outperform the softmax baseline.
Datase//Model
Baseline Sofimax
Atiention- BN
Attention-SH
AttentionBN-SSH
LISTÖrs
36.76 +: 0,42
37.32 = 0.06
37.08 + 0.48
37.33 +: 0.53
TEXT
64.90 + 0.07
65.07 = 0.08
65.19 + 0.19
65.03 + 0.35
RETRIEVAL
79.68 0.52
81,05 + 0.08
80.74
1: 0.32
81.20 0.11
IMAGE
39.23 1.35
39.75 = 1.21
38.87
1.24
39.18 1.27
PATHFINDER
72.72 +: 0.75
73,24 + 0.67
74.00
+ 0.29
73.98 + 0.55
AVERAGE ACCURACY
58.66 0.26
59.28 + 0.25
59.18
0.22
59.35 0.29
Table 3: T and top-5 accuracy (%) of the Attention- BN/SSHSHHBBN Deit vs. the baseline softmax attention Deit on the ImageNet benchmark. The Attention -BN Deit outperforms the baseline in terms of accuracy. The Deit achieve comparable accuracy with the baseline while being more efficient.
Metric/Model
Baseline Softmax Deir
Attention- BN Deit
Attention-SH Deit
Attention-BN-SH Deit
Top-1 Acc (%) Top-5 Ace (%)
72.23 : 0.23
72.79 + 0.21 91.43 + 0.12
72.08 + 0.23 91.05 + 0.14
72.25 - 0.22
91.13 + 0.15
91.14 + 0.12
A Training
B Teating
C Thaniing
D Teailig
Menoay nalo
6.0
FLOPS
0.0
1034 2043
1024
2021
2.01
2011 $14/
Sequonce Langth
Sequence Longth
Sequence Langth
Secuario Langth
Figure 1: (Left) FLOPS ratios and (Right) memory usage ratios between the Sttention-BN+SH and the softmax baseline trained on retrieval task different model dimensions and sequence lengths. The reduction in computation and memory when using our models improves with sequence length. When scaling up the model, our methods remain significantly more beneficial than the baseline.
Time Series experiment, on this LRA benchmark, Attention-BN BN and Attention-SH both outperform the softmax attention on most five tasks. Moreover, Attention-BN+HH which combines these two attention mechanisms, results in the most accurate models on average across tasks. Specifically, for the retrieval task, the most challenging task with the largest sequence length in the LRA benchmark, Attention-BN+SS achieve a remarkable improvement of more than 1.5% over the baseline.
Image Classification on Imagenet. We corroborate the advantage of our proposed attention over the baseline softmax attention when scaled up for the large-scale ImageNet image classification task. We summarize the results in Table 3. The Deit model (Touvron et al., 2021) equiped with the Attention-BN yields better performance than the sofumax baseline. Meanwhile, Attention-SH/BN-SH Deit perform on par with the baseline while being more efficient. These results, together with other results above justify the benefits of our proposed methods across various tasks and data modalities, proving the effectiveness of our primal-dual approach to develop new attentions.
4 EMPIRICAL ANALYSIS
Efficiency Analysis. The Attention-BN+STt not only improves the accuracy of the model remarkably but also help reduce the computational and memory cost significantly. Fig. presents the efficiency benefits of our CitentionBBN+SH trained on the retrieval task when the model dimension D and sequence lengths N grow. The efficiency advantage of our model increase as N increase. In addition, the scaled-up models (with large D) remains significantly more efficient than the baseline. When the model dimension is 64 and sequence length is 4096, which is the standard configuration of the task, the model's 's FLOPS, in both training and inference, reduce almost 25% whereas the reductions for memory usage in training and testing are 31.9% and 47.3%, respectively. Notably, this efficient model also outperforms the baseline with more than 1.5% improvement in accuracy. These results prove the benefits of applying the Mioention-NN-SI for long-sequence tasks and large-scale models.
New Attentions Helps Reduce Head Redundancy. We compute the average L2 distances between heads to analyze the attention diversity. Given our trained models for the retrieval task, the layer- average mean and standard deviation of distances between heads are reported in Table 4. All our introduced attentions attain greater L2 distances compared the baseline, reducing the risk of learning redundant heads. In particular, Attention-SD SH has the highest head difference, indicating the model's 's attention patterns most spread out between heads.
8

---

Published as a conference paper at ICLR 2023
Table 4: Layer-average mean and standard deviation of La distances between heads of Attentin-BNN/HHBBNN BN/SH/BB+SHH versus dot-product attention transformer trained on the retrieval task. Our attentions attain greater La distances between heads than the baseline, suggesting that they capture more diverse attention patterns.
MetricModel
Baseline Softmax
Atlention-SH Attention-BN
AttentionBNN-HH
Mcan
2.01
2.45
3.81
3.19
Sid
0.39
0,66
0.75
1.01
Combining Attention-BN and Attention-SH with Other Attentions. Our methods be extended to combine with other attention mechanisms. We study the Linear Attention-BN/SH/BNN with the linear attention (Katharopoulos al., 2020) as
that
combine the explained at the end of Section 2.3. We summarize our results in Table 5 in Appendix B.1.
RELATED WORK
Interpretation of Attention Mechanism. Recent works have focused understanding the attention mechanism in transformers from different perspectives. (Tsai et al., 2019) considers attention as weighted moving average over the inputs via smoothing kernel. (Nguyen et al., 2022) draws a connection between self-attention and nonparametric kernel regression. With this understand- ing, the work explores better regression estimators, e.g. the generalized Fourier nonparametric regression estimator, to improve transformers. In addition, (Cao, 2021) then shows that the linear transformer (Katharopoulos et al., 2020) corresponds to a Petrov-Galerkin projection (Reddy, 2004) and proves that the softmax normalization in the softmax attention is sufficient but not necessary. Other works that employ ordinary/partial differential equations to provide an interpretation for atten- tion include (Lu al., 2019; Sander et al., 2022). From probabilistic perspective. (Tang & Matteson, 2021; Gabbur et al., 2021; Zhang & Feng, 2021) propose Gaussian mixture model frameworks to study the self-attention in transformers. Using graph-structured learning and message passing in graphical models is another attempt at understanding the attention mechanism Wang et al. (2018); Shaw et al. (2018); Kreuzer et al. (2021). Optimization perspectives of attention mechanisms are recently explored. (Sander et al., 2022) connects transformers with an optimization process across iterations by specifically constructing the core energy function. (Sahiner et al., 2022) derive finite- dimensional convex equivalence of attentions that can be solved for global optimality. Different from these approaches, our primal-dual framework focuses on deriving attention as the dual expansion of primal neural network layer via solving support vector regression problem. This framework allows us to not only explain many different types of attention mechanisms but also create new ones.
Efficient Transformers. Recently, efficient transformers have been studied (Roy et al., 2021). Among them are sparse transformers which incorporate sparse structures into the attention matrix (Parmar et al., 2018; Liu et al., 2018; Qiu et al., 2019; Child et al., 2019; Beltagy et al., 2020). Another class of efficient transformers are models that aim to have better coverage by integrating different access patterns (Child et al., 2019; Ho al., 2019), which can also be learned from the data (Kitaev et al., 2020; Roy et al., 2021: Tay et al., 2020). An emerging body of work is proposed to distill and prune the model, including (Sanh et al., 2019; Sun et al., 2019; Voita et al., 2019; Sajjad al., 2020). In other works, a side memory module is utilized in order to access multiple tokens simultancously (Lee et al., 2019; Sukhbaatar et al., 2019; Asai & Choi, 2020; Beltagy et al., 2020). Low-rank and kernelization methods have been proposed to improve the efficiency of self-attention calculation (Tsai al., 2019; Wang et al.. 2020; Katharopoulos al., 2020; Choromanski al., 2021; Shen al., 2021: Peng et al., 2021). Our Attention-SHiie SH/BN+SH is orthogonal to these methods.
CONCLUDING REMARKS
In this paper, we derive self-attention a support vector expansion that solves support vector regression (SVR) problem and provide a principled primal-dual framework to analyze and synthesize attention mechanisms. We then use our framework invent two new attention mechanisms, the Batch Normalized Attention (Attention-BM) and the Attention with Scaled Heads (Attention-SHr that improve the accuracy and the efficiency of the baseline softmax attention. In our work, we approximate and learn the dual variables a and 5 using the value vector øj. j = 1....,N N in self-attention. It natural to include more inductive biases and structures of those dual variables from solving the dual optimization problem of SVR into the value vectors Vj. Furthermore, extending our framework to explain the attention modules that compute the attention using neural network layers or convolutional neural network layers applying the input feature, such as the Convolutional Block Attention Module (Woo et al., 2018) 8), is an interesting research direction. We leave these exciting research ideas future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This material based on research sponsored by the NSF under Grant# 2030859 to the Computing Research Association for the CIFellows Project (CIF2020-UCLA-3)) SJO acknowledges support from the ONR N00014-20- 1-209 and N00014-20-1-2788 and the NSF DMS 2208272 and 1952339, RGB acknowledges support from the NSF grants CCF- 191 1094, IIS- 183317877 and IIS- 1730574; ONR grants N00014- 18- 12571, N00014-022 1--00-1-2534, and MURI 1000014220-1-7888 AFOSR grant FA9550-22-1 1-000;; and a Vannevar Bush Faculty Fellowship. ONR grant N00014-18-1-22 acknowledges support from the NSF grants DMS-2152717 and DMS-1952339, NH acknowledges support from the NSF IFML 2019844 and the NSF AI Institute for Foundations of Machine Learning.
ALB
REFERENCES
Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3159-3166, 2019.
Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučié, and Cordelia Schmid. Vivit: A video vision transformer. In 2021 IEEE/CVF International Conference Computer Vision (ICCV), pp. 6816-6826, 2021. doi: 10.1009/CCV449922222..000
Akari Asai and Eunsol Choi. Challenges in information seeking qu: Unanswerable questions and paragraph retrieval. arXiv preprint arXiv:2010.119155 2020.
Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling, In International Conference on Learning Representations, 2019. URL http://ppenteviee.ne//oomm
id-ByxZX20qFO.
Anthony Bagnall, Hoang Anh Dau, Jason Lines, Michael Flynn, James Large, Aaron Bostrom, Paul Southam, and Eamonn Keogh. The uea multivariate time series classification archive, 2018. arXiv preprint arXiv:1811.0000 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint
2014.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprini 20xxx:2004.05/555 2020.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005.1 141155500...165. 2020.
Shuhao Cao. Choose a transformer: Fourier or galerkin. Advances in Neural Information Processing Systems, 34, 2021.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems, 34:15084-1500 2021.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: 11.00.100000 10509, 2019.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1734, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/v1/D14-1111 URL https://www.aclwehh org/anthology/D44- 1179.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021. URL hitps:
10

---

Published as a conference paper at ICLR 2023
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. What does BERT look at? an analysis of BERT's attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 276-286, Florence, Italy, August 2019. Association for Computational Linguistics. doi: 10. 10.18653/1/W19-44222 wwwp://wwww....goooooo/o///////
URL https:
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273-277, 1995.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdi- nov. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprini MrXiv:190I.02860 2019.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL httpss//opennrview.neel Yorumniid-YiebFaNTTY
Prasad Gabbur, Manjot Bilkhu, and Javier Movellan. Probabilistic attention for interactive segmenta- tion. Advances in Neural Information Processing Systems, 34, 2021.
Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al. Conformer: Convolution-aggmented transformer for speech recognition. arXiv preprint arXiv:2005.08 2020.
Meng-Hao Guo, Jun-Xiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R Martin, and Shi-Min Hu. Pet: Point cloud transformer. Computational Visual Media, 7(2):187-199, 2021.
Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidi- 2019.
mensional transformers. arXiv preprint arXiv:
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 1704004861 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456 PMLR, 2015.
Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcement learning as one big sequence modeling problem. Advances neural information processing systems, 34:1273-1286, 2021.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvuakooo,, Russ Bates, Augustin Židck, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873)5583-558)) 589, 2021.
Angelos Katharopoulos. Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns:: Fast autorcgressive transformers with linear attention. In International Conference on Machine Learning, pp. 5156-5165. PMLR, 2020.
Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. Structured attention networks. arXiv preprint arXiv: 2017.
11

---

Published as a conference paper at ICLR 2023
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04455 2020.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Scungjin Choi, and Yee Whye Teh. Set trans- former: framework for attention- based permutation invoonnnnniiinnt neural networks. In International Conference Machine Learning, pp. 3744-375. PMLR, 2019.
Zhouhan Lin, Minwei Feng, Cícero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. A structured self-attentive sentence embedding. CoRR, abs/1703.03130, 2017. URL http://arxiv.org/abb// 1ttps////1000333333 130.
Drew Linsley, Junkyung Kim, Vijay Veerabadran, Charles Windolf, and Thomas Serre. Learn- ing long-range spatial dependencies with horizontal gated recurrent units. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biance Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems. volume 31. Curran Associates, Inc., 2018. URL pappadd////cccceeeeappp...
Peter Liu, Mohammad Saleh, Ftienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. arXiv preprint a1Xiv:1801.10198 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
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 IEEF/CVF International Conference on Computer Vision, pp. 10012-10022, 2021.
Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu. Video swin transformer. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2022.
Yiping Lu, Zhuohan Li, Di He, Zhiqing Sun, Bin Dong, Tao Qin, Liwei Wang, and Tie-Yan Liu. Understanding and improving transformer from a multi-particle dynamic system point of view. arXiv preprint arXiv: wttp:/9900000000 2019.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguisties: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL https: www.acclee.org/antholoyyy 10-5.
Nikita Nangia and Samuel Bowman. ListOps: A diagnostic dataset for latent tree learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pp. 92-99, New Orleans, Louisiana, USA, June 2018. Association for Computational Linguistics. doi: 10.1865//1/N1184400 URL
http://www..elwwboogg//bbggg////
Tam Minh Nguyen, Tan Minh Nguyen, Dung DD Le, Duy Khuong Nguyen, Viet-Anh Tran, Richard Baraniuk, Nhat Ho, and Stanley Osher. Improving transformers with probabilistic attention keys. In International Conference on Machine Learning, pp. 16595-16621. PMLR, 2022.
Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit. A decomposable attention model for natural language inference. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2249 2255, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10. 10.18663/v//D16. 1244. URL https://www..ddw...r//aaaaaaaa
D16- 1244.
12

---

Published as a conference paper at ICLR 2023
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 4055-4064. PMLR, 10-15 Jul 2018. URL http://proceedingg.ml...mm v80/parmar 8a.html.
Hao Peng, Nikolaos Pappas, Dani Yogatama. Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. International Conference on Learning Representations, 2021. URL
Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint (rXiv:/911.02972. 2019.
Dragomir R Radev, Pradeep Muthukrishnan, Vahed Qazvinian, and Amjad Abu-Jbara. The acl anthology network corpus. Language Resources and Evaluation, 47(4):919-944, 2013.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training. OpenAl report, 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9 2019.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. PMLR, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020. URL http:///mll.orr//aperss//// 1atp://12200000..mm..
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pp. 8821-8831 PMLR, 2021.
JN Reddy. An introduction to the finite element method, volume 1221. McGraw-Hill New York, 2004.
Alexander Rives, Joshua Meier, Tom Sercu, Siddharth Goyal, Zeming Lin, Jason Liu, Demi Guo, Myle Ott, C Lawrence Zitnick, Jerry Ma, al. Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences. Proceedings of the National Academy of Sciences, 118(15), 2021.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 6853-68,70 2021. URL.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 1 115(3)22112553 2015.
Arda Sahiner, Tolga Ergen, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Un- raveling attention via convex duality: Analysis and interpretations of vision transformers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 19050-19088. PMLR, 17-23 Jul 2022. URL https://proceedings.uu mir. prr.prsss/v. 1tw. 62/sshhiner22.hum..
Hassan Sajjad, Fahim Dalvi, Nadir Durrani, and Preslav Nakov. Poor man's bert: Smaller and faster transformer models. arXiv e-prints, pp. arXiv-2004, 2020.
13

---

Published as a conference paper at ICLR 2023
Michael E Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkfonmers: Transformers with doubly stochastic attention. In International Conference on Artificial Intelligence and Statistics, pp. 0113351153331 PMLR, 2022.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert. a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01108, 2019.
Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp. 464-468, New Orleans, Louisiana, June 2018, Association for Computational Linguistics. doi: 10. 10.18653/v/ N18-2074. URL https///clamthooog..oogg 2074444.
Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention: Attention with linear complexities. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 3531-3539 2021.
Alex Smola and Bernhard Schölkopf. A tutorial on support vector regression. Statistics and computing, 14(3):199-22) 2004.
Sainbayar Sukhbaatar, Edouard Grave, Guillaume Lample, Herve Jegou, and Armand Joulin. Aug- menting self-attention with persistent memory. arXiv preprint 1907vv9907.0//1 2019.
Siqi Sun, Yu Cheng, The Gan, and Jingjing Liu. Patient knowledge distillation for bert model compression. arXiv preprint PrXiiv:/08.09:0 2019.
Chang Wei Tan, C. Bergmeir, François Petitjean, and Geoffrey I. Webb, Monash university, uea, uer time series regression archive. ArXiv, abs/2006. 10996, 2020.
Binh Tang and David S. Matteson. Probabilistic transformer for time series analysis. In A. Beygelz- imer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse Sinkhorn attention. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 9438-9447. 19/t1a
PMLR, 13-18 Jul 2020. URL http://proceedings..r..reese
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena A benchmark for efficient transformers. In International Conference on Learning Representations, 2021. URL. https: wttpr//www...eeoooomnd///ereeeee
Ian Tenney, Dipanjan Das, and Ellie Pavlick. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp- 4593-4601, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/ v1/P19-1452. URL
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers and distillation through attention. arXiv preprint 2012:22012.12877 2020.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers distillation through attention, 2021.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philipee Morency, and Ruslan Salakhut- dinov. Transformer dissection: An unified understanding for transformer's 's attention via the lens of kernel. arXiv preprint arXiv: /908. /775, 2019.
14

---

Published as a conference paper at ICLR 2023
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 2998-6008 2017.
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in transformer language model. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP. pp. 63-76, Florence, Italy, August 2019. Association for Computational Linguisties. doi: Nww.8663////111-44330
URL
http:///ooooooo119//90090 19-4808.
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. arXiv preprint arXiv:1905.00418. 2019.
Sinong Wang, Belinda Li, Madian Khabsa, Han Fang. and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint (rXiv:2006.0477 2020.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7794-7803, 2018.
Zifeng Wang and Jimeng Sun. TransTab: Learning Transferable Tabular Transformers Across Tables. In Advances in Neural Information Processing Systems (NeurIPS 2022), 2022.
Sanghyun Woo, Jongchan Park, Joon-ooune Lee, and In So Kweon. Cham: Convolutional block attention module. In Proceedings of the European conference on computer vision (ECCV), pp. 3-19, 2018.
Haiping Wu, Bin Xiao, Noel Codella, Mengchen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang. Cvt: Introducing convolutions to vision transformers. In Proceedings of the IEFF/CVF International Conference on Computer Vision, pp. 22-31, 2021.
Haixu Wu, Jialong Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Flowformer: Linearizing transformers with conservation flows. In International Conference on Machine Learning, 2022.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V
Le. Xlnet: Generalized autoregressive pretraining for language understanding. arXiv preprint 1xXiv:1906.08237.. 2019.
George Zerveas, Srideepika Jayaraman, Dhaval Patel, Anuradha Bhamidipaty, and Carsten Eickhoff. A transformer-based framework for multivariate time series representation learning. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 2114-2124, 2021.
Shaolei Zhang and Yang Feng. Modeling concentrated cross-attention for neural machine translation with Gaussian mixture model. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 1401-1411, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties. doi: 10.18653/v122211 1.0././i///.....iinnng..... findings--mmin 121. URL https//acclathhoooyy org/2021 findinngs------ii findings-emmlp.122.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys (CSUR), 52(1):1-38, 2019.
Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun. Point transformer. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 16259-16268, 2021.
Chen Zhu, Wei Ping, Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandkumar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision. In NeurlPS, 2021.
15

---

Published as a conference paper at ICLR 2023
Supplement to "A Primal-Dual Framework for Transformers and Neural Networks"
A ADDITIONAL DETAILS ON THE EXPERIMENTS
This section provides datasets, models, and training details for experiments Section 3. As mentioned in Section 3, for Attention-BN models, recentering queries and keys alone is sufficient for accuracy improvement, and we weight the mean 1a in Eqn 22 with a constant B. Hence Eqn 22 is simplified to:
N
h
softmax ((: - (pp B1//vDD) n..
(26)
In our experiments, we consider the constant 3 in Biention-BN/BNN-II and the different downsam- pling scales in Attention-SH/SHHHDD as hyper-parameters to finetune. All of our experiments are conducted on server with 4 NVIDIA A100 GPUs.
A.1 UEA TIME SERIES CLASSIFICATION
Datasets and metries The benchmark (Bagnall et al., 2018) consists of 30 datasets. Following (Wu et al., 2022), we choose datasets, which vary in input sequence lengths, the number of classes, and dimensionality, to evaluate models on temporal sequences. We report the test accuracy as evaluation for the benchmark.
Models and baselines The experiment setups and configurations for the softmax/linear baseline and models the same as in (Wu et al., 2022) (for the PEMS-SF, SelfRegulationSCP2, UWaveGestureLibrras datasets) and (Zerveas et al., 2021) 2 (for the other tasks). In all models, the number of heads is 8, whereas the model dimension and number of transformer layers are varied. For heads.
we downsample keys and values by the factor of 2, after every two successive
A.2 LONG RANGE ARENA BENCHMARK
Datasets and metrics We adopt the tasks: Listops (Nangia & Bowman, 2018), byte-level IMDb reviews text classification (Maas et al., 2011) byte-level document retrieval (Radev et al., 2013), CIFAR-10 image classification (Krizhevsky et al., 2009) and the Pathfinder challenge (Linsley et al., 2018) in the LRA benchmark for our experiments. They consist of long sequences of length 2K, 4K, 4K, 1K, and 1K respectively. The evaluation protocol and metric are the same as in (Tay et al., 2021).
Models and baselines our models and softmax/linear baselines follow the same architecture and configuration in (Zhu et al., 2021)². Each model consists of two layers and 64 embedding dimensions. While one head at each layer remains intact, the keys and values of the other heads are experiments.
halved in our Aitention-SH/SHHHH
A.3 IMAGE CLASSIFICATION ON IMAGENET
Datasets and metrics The ImageNet dataset (Deng et al., 2009; Russakovsky et al., 2015) consists of 1.28M training images and 50K validation images. The task is to classify 1000 categories. Top-1 and top-5 accuracies reported.
Models and baselines Our baseline is DeiT-tiny model (Touvron al., 2021) with 12 transformer layers, 4 attention heads per layer, and the model dimension of 192. For model setting and setting and configuration, we follow (Touvron et al., 2021)*. The downsampling scales in SoaniionSSHBN+SEE models are 1, 2, 4] for 4 heads at each layer, respectively.
IImlleenntttinn available at https://ithb..com///u/////oooooo
"Implementation available https//ggthbb.com//eeervavaavaa transformer. "Implementation available at http://ggthbbccmm///illAAttttttt
Implementation available at hutp://ihhhn.commicchoorrececccc
16

---

Published as a conference paper at ICLR 2023
Table Test Accuracy (%) of the Linear tion (Katharopoulos et al., 2020) on the UEA Time Series Classification Archive benchmark (Bagnall et al., 2018). Our proposed attentions outperform the baseline.
BNISH/BN+SH vs. the baseline Linear Atten-
Dataset/Model
Baseline Linear
Linear Attention-Bh
Lineur Attention-SH
Linear AltentionBNN-HH
BTHANOLCONCENTRATIIO
33.84 0.66
34,98 + 0.74
34.76 0.69
34.15 0.70
FACEDETECTION
69.17 0.32
69.22 + 0.17
69.38 : 0.17
69.12 0.19 0.19
HANDWRITING
32.87 0.27
32.86 + 0.49
32.82 : 0.12
32.98 1: 0.36
75.61
75.78
75.94
VAPANESEVOWELS
99.37 0.16
99.60 + 0.19
99.28 0.41
99.33 0.19
PEMS- SF
83.43 +: 0.88
85.74 + 0.67
86.51 +: 0.88
84,97 + 0.76
SELFREGUI ATIONSCC1
90.90 0.40
91.81 +: 0.69
90.76 0.59
91.92 0.60
SELFREGULLTIONNCFF
55.18 0.89
56.11 +
54.44
55.74
SPOKENARARICDiGIIS
99.07 0.10
99.01 + 0.07
99.03 0.18
98.91 0.17
UWANRRESTURELLBBARRY
85.63 0.81
86.04 +: 0.86
84.89 + 1.00
85.78 + 0.75
AVERAGE ACCURACY
72.51 0.34
73.12 + 0.20
72.68 + 0.40
72.90 + 0.23
Table 6: Top-1 and top-5 accuracy (%) of the (iennton-Conv2]] Deit vs. the baseline Deit with the softmax attention the ImageNet image classification task. The Piention-Conv2]1 Deit significantly outperforms the baseline in both top-1 and top-S accuracy.
Metric/Model
Baseline Softmax Deiz
Ontention-Con-221 Deit
Top-1 Ace (%)
72.23 + 0.23
73.18 +: 0.24
Top-5 Ace (5)
91.13 + 0.15
91.52 0.13
Table 7: Test Accuracy (%) of the Attention-Conv ID the baseline softmax attention 5 tasks of the LRA benchmark (Tay et al., 2021). Our models outperform softmax baseline.
Model
Baseline Softmax
Attention- ID
LiSTOPS
36.76 0.42
37.20 0.05
TEXT
64,90
RETRIEVAL
79.68 + 0.52
80.75 0.15
IMAGE
39.23 + 1.35
39.18 + 0.59
PATHFINDER
72.72 0.75
73.01 0.24
AVERAGE ACCURACY
58.66 1: 0.26
59.01 + 0.20
B ADDITIONAL EXPERIMENTAL RESULTS
B. UEA TIME SERIES CLASSIFICATION USING LINEAR AITENTION-BNISH/BNNSS and the baseline
Table 5 summarizes the comparison between the Linear Linear Attention on the UEA Time Series Classification task. The Linear Attention-BN/St BN/SH/BN+SH achieve better accuracy than the Linear Attention baseline while being more efficient.
B.2 CONVOLUTION ATTENTION
Table 6 demonstrates the advantage of Attention-Conv2D (Def. 3, Section G) over softmax Deit on the ImageNet image classification task. Furthemore, as shown in Table the Attention-Conv ID (Def. 4, Section G) outperforms the baseline softmax attention on 5 tasks of the LRA benchmark (Tay al., 2021).
B.3 ADDITIONAL. EXPERIMENTS ON THE UEA TIMESERIES CLASSIFICATION BENCHMARK AND THE UCR TIME SERIES REGRESSION ARCHIVE
In this section, we further demonstrate the advantage of our 15 tasks in the UEA Time Series Classification benchmark and on 6 tasks in the UCR Time Series Regression benchmark. The results in Table 8 and 9 show that our Attention-BN and Attention- SH+BN outperform the baseline softmax transformers significantly on both of these benchmarks, while the attention-SH has comparable performance with the baseline but being more effiiciett.
on additional
B.4 UEA TIME SERIES CLASSIFICATION USING THE SPARSE ATTENTION-BN/SH/BNNN and the Sparse
Table 10 summarizes the comparison between the Sparse Attention baseline on a subset of the UEA Time Series Classification benchmark. Our models when combined with Sparse Attention achieve significantly better accuracy than the Sparse Atten- tion baseline while the Sparse Attention-SH/B5 Appendix C).
are more efficient (See Fig. and Fig. 4 in
17

---

Published as a conference paper at ICLR 2023
Table Root mean square error (RMSE) of the Attention- CeantionBNNSSHBB-AAA vs. the baseline softmax attention on 6 UCR Time Series Regression tasks (Tan et al., 2020). Smaller RMSE indicates better performance.
Dataset/Model
Baselime Sofmmax
Atlention-Bi BN
Attention-Si SH Attention-BN
APPLIANCESENEROY
3.44 1 0.06
3.38 + 0.34
3.39 1: 0.02
3.37 0.23
BENZENECONCENTROEER
0.91 = 0.03
0.89 + 0.17
1.00 2 0.09
0.90 = 0.08
BEUINGPMIO
92.31 + 1.06
92.00
92.82 :: 0.92
92.40 +: 0.85
BEUINGPM25
59.73
59.35 0.92
59.66 +: 0.88
39.24 1: 1.22
ENEEFUELMOISTURE
43,08 +: 0.17
43.01 0,50
43.65 + 0.09
43.79 + 0.49
IEEEPPG
32.12 + 1.25
30.69 = 0.64
31.38 +: 1.02
30.73 + 1.20
AVERAGE RMSE
38.60 + 0.67
38.25 0.30
38.65 + 0.27
38.40 +: 0.51
Table 9: Accuracy (%) of the Attention BN/SH/BN++H vs. the baseline softmax attention on other 15 UEA Time Series classification tasks (Bagnall et al., 2018).
Datase/MMoel
Baseline Softmax
Attention- BN
Attention SH
Attention-BN-SH
ARTICULARY WORDRECOGNTTION
97.44 + 0.42
98.22 = 0.87
97.22 + 0.95
98.44 + 0,41
BASICMOTIONS
98.75
99.38
1,08
99.37 + 1.06
+
EPILEPSY
93.71 1.23
92.27 0,74
89.13 + 1.07
92.02 + 1.02
ERING
95.18 + 0.52
95.18 0,37
94.72 + 0.66
95.46 : 0.40
FINGERMOVEMENTS
59.67 0.47
63.00 = 0.41
61.33 + 0.70
63.66 + 0.64
85.37
NATOPS
95.00
95.37 0.26
96,29 +: 0.69
95.74 1: 0.94
RACKETSPORTS
87.28 0.88 0.82
87.93 0.31
88.16 + 0.54
89.03 : 0.64
FIBRILFIBRRIAA LABRILLATION
33.33 +
41.67 2,88
35.00 + 2.89
41.68 + 2.80
CRICKET
0.65
95.37 0.65
0.65
STANDWALKJUMP
50.00
55.55 2.14
50.01 + 2.34
55.00 + 2.08
SONDMMVVEEETDDREEEEEE
63.96
64.41 = 2.76
61.71 + 2.64
66.66 : 2.54
LSST
0.55
$7.05 0.26
60.34 + 0.73
59.91 +
DUCKDUCKGEESE
64,50 1.96
65.00 1.73
64.50 1.95
65.50 1.66
MOTORIMAGERY
58.66 : 1.25
60.67 1.69
59.00 + 1.41
62,00 = 0.81
AVERAGE ACCURACY
75.73 0.51
77.10 0.22
75.61 + 0.18
77.74 + 0.24
Table 10: Test Accuracy (%) of the Sparse Attention-B.//SIINN al., 2019) subset of the UEA Time Series Classification Archive benchmark (Bagnall al., 2018). Our proposed attentions outperform the baseline.
vs. the baseline Sparse Attention (Child
Dataset/Model
Baseline Sporse
Sparse Attention- BN
Sparse Attention
Sparse Attention-BN-ee BN+SH
ETHANNLL GrIIAOOLCONCENTR.CO CONCENTRATION
33.33 1.23
33.33 + 0.78
32.50 0.57
33,46 1 0,71
FACEDETECTION
68.58 + 0.95
68.65 + 0.44
68.67 = 0.78
68.44 + 0.51
HANDWRITING
31.08 + 0.38
31.79 + 0.44
32.75 0.39
33.37 : 0.61
HEARTBEAT
74.95
75.98 +
74.96
+
JAPANESE
99.45 1 0.10
99.54 0.12
99.18 0.14
99.36 1: 0.34
PEMS-SF
82.08 0.63
83.81 + 0.47
82,66 : 0.63
84,01 + 0.89
91.24 + 0.85
91.69 + 0.42
91.47 +
91.70 +: 0.16
SELFREEGULATIONSCCP
55.18
55.92
1:
SPOKENARABICDIGITS
99.04 + 0.06
99.10 + 0.15
99.06 0.13
99.15 + 0.09
(WWAFRGESTTIRELLRRRRR
84.90 + 0.39
85.73 +: 0.38
85,31 + 0188
86.56 + 0.25
AVERAGE ACCURACY
71.98 + 0.38
72.81 + 0.15
72.25 1 0.24
72.88 1: 0.35
Table 11: Test Accuracy (%) of the Attention-BN/NN-SH with / is learnalle or set as hyperparameter on the retrieval task (Tay et al., 2021).
Model
Retrieval
Attention-BN (leurn ()
80.77 +: 0.23
Attention- Allention-BN+SS5 BH (learn 3)
81.31 +: 0.25
Atlention- BNN (9 as hyperparameter)
81.05 + 0.08
Attention-Be BN+SH (6 as hyperparameter)
81.20 +:
B.5 ATTENTION-BNIIN BN/BN+SH WITH LEARNABLE /
We experiment with our Attention BNRiiin--BBBBNHHH with learnable on the retrieval task. Table 11 shows that learning does not improve much over setting 3 to be hyperparameter.
C ADDITIONAL RESULTS ON EFFICIENCY ANALYSIS
This section provides more efficiency analysis models.
18

---

Published as a conference paper at ICLR 2023
A Training
8 Tasting
Training
Testing
3.93
0.00
2.03
0.00
FLOPS
Merrory
0.00
0.71
Sequence Lorgth
Sequence Length
Sequeence Length
Secueence Length
080 04
120
den- 25g
din- 512
Figure 2: (Left) FLOPS ratios and (Right) memory usage ratios between the Attention-SH and the softmax attention baseline trained the LRA retrieval task for different model dimensions and sequence lengths.
D
Training
Testing
Training
Testing
0.56
FLOPS ratlo
0.94
3.54
0:00
0.10
3024
612
1002
20355
4714
Sequence
Sequence Lergth
Sequuencs Os Length
$12
Figure 3: (Left) FLOPS ratios and (Right) memory usage ratios between the Sparse Attention BN+SH and the Sparse Attention baseline trained on the LRA retrieval task for different model dimensions and sequence lengths. When using our models, the reduction in computation and memory improves with sequence length. When scaling up the model with greater model dimension, our methods remain significantly more efficient than the baseline.
D Testing
Training
Teeting
Trainin
01900
0.50
FLOPS nallo
0.94
Memory ratio
0:00
0.7
0.50
3334
0.58
512
1004
2045
4735
Sequence
Secuence Length
Sequence Length
dim
din- din 124
dim- 256
ditn 612
Figure 4: (Left) FLOPS ratios and (Right) memory usage ratios between the Sparse Attention-SH and the Sparse Attention baseline trained the LRA retrieval task for different model dimensions and sequence lengths. When using our models, the reduction in computation and memory improves with sequence length. When scaling up the model with greater model dimension, our methods remain significantly more efficient than the baseline.
Attention-SH. Fig.2 shows the efficiency benefits of our Attention-SH when trained on the retrieval task. Same as in the case of AttentionSH++By the efficiency benefits of our Attention-SE over the baseline Softmax attention grows when N and D increase.
Fig.3 and Fig.4 show that the efficiency advantages of our Sparse Attention-BN-So and Sparse Attention- SH, respectively, increase as the model dimension and sequence length N grow. All models are trained on the LRA retrieval task. In addition to the efficiency advantage, the Sparse Eicention-BN+SS also significantly outperforms the Sparse Attention baseline in terms of accuracy in this task (79.86% vs. 78.20%) while the Sparse Attention-SH achieves comparable result to the baseline. More accuracy advantages of the Sparse Attention BiattionnBB/SHBNN-SH over the Sparse Attention baseline are given in Table 10.
Sparse Attention-SH/BNNe
D DERIVING SOFTMAX ATTENTION.
Choosing the appropriate h(w) and (xx) allows us to derive the popular softmax attention given in Eqn. 1 and 2. In particular, if we choose h(z)) == Σ & (x))TT()) Eqn. 10 becomes
N
((x) (kk,
U + b = プ (xx) $(k))o
f(x) =
+ b.
(27)
1=1 p (kx)
N
Σn (T))T(p)))
19

---

V. Published as a conference paper at ICLR 2023
We then select ((x) = (a/ (0) (1)
0/1 ai ..... (1)
(1)
(t) ,...) where 4 = (D+--1) and
(a) / VD) n (DD/ VD)m
n1 + nn = 4, 151s
(28)
vng... np!
Since
20 (x y)
80 Σ
exp (x y)
Σ
I ... DD
Vi ... VD
(29)
t!
Vng... nD
Vny! nD
then Eqn. 27 becomes
11
uD
Ki "1
K nD
Ei=o Enp
N
VuI!...np!
Vni!....!
f(x)
Uj +
==1
11
21== Eng Enntunnnost
f/=1
Vai!..nn!
Vn!!..n!
exp
VD
VD
exp (x k//VD)
Uj
b
1j b.
(30)
by
j'=1 exp (x ky/VD)
=1 exp
+
D
Let x - qı, b= 0 and relax the boundness constraint of oy in Remark 1. Eqn. becomes Eqn. 2 of the softmax attention (Vaswani et al., 2017).
E BATCH NORMALIZED ATTENTION: DERIVATION OF EQN. 24
(q:(d) (kd))( mld))
h4
softmax
VD(03+ +()
(d(d)k)(d) q: qc(d)u(d) ((dd))s(d) m(d)/(d) ((d)(())
Σ softmax
Vj
VD(O} +
Ebm
(d)k (d) (dd) (d))))()) VD(o+t))
cxp
Edm qiddk, (d) (d)p)d) (alpudd)=(ddkerre (d) Vj
.
j'
exp
VD(o)+e)
Eb
(diik (d) (d))
exp Σ -
exp
VD(o++e)
VD(o3+e)
p(d) -(d)u(()- Vj
Eb (d) y (())
EE
=1=
exp
VD(a
exp
vD(az+e)
(diik,, ((d)k,
N
exp
dm
VD(a]+e)
ED (d)
===1 cxp
VD(o3-o)
(d))k (d) (d)
softmax
U/
VD(03 +))
==1
(d)kk, - Eg= by (d)
softmax
(31)
VD +c)
F ATTENTION WITH THE RESIDUAL CONNECTION AND MATRIX PROJECTIONS
In this supplement, we first discuss attention with the residual connection and matrix projections in Appendix F.
Suppose we are given a training data {(x) yi....., (x yN)} C. X x V, where R and y' = D.. Here, .1,... y are the training inputsd, and y1,--.: : UN are the training targets. In
20

---

Published as a conference paper at ICLR 2023
order to derive the attention with the residual connection and query, key, and value matrix projections, we define the function f as follows
Φ ((Wprolz)
y = f(z) = W
+ x + b.
(32)
h(x))
where x: E X' RRD, W = T majj w proj T E DDD= ((..) = (0)()), 2D,(()) (-) TRD - RD, W -|w].-.. [w]..... Wp
I7 E DD,, E R., and h(x²) is vector-scalar function. We fit the function f to the training data ((+1,))) y)),...,. (æN, yr]} with an L2 regularization on W and
Werof by solving the following convex optimization problem: N D.
D.
D.
minimize W. W N....N
1
2
1
2 1| + + L
(d)()) + EE)(d)
2
2
d=1
d=1
8, E,,
Ui (d) w DD (( )/b(z))))))))))))))))))))))))) - 2; b(d) S c (dd
subject to
wo 2 ( 2))((xx)))) + +2 + b(d) - (d) S c (d)
. 1. 1...., N, d=1, 1...., De.
(d), (d) 20
(33)
The Lagrangian of the optimization problem 33 given by N D.
D.
D.
N De
L
Iwall
2 +
1
Σ
proj
112 C
Σ
Σ
(d(d) + Ed)
ΣΣ
(d(d)E + (
d=1
d=1
d=1
j=1
ΣΣ add (y))) + wa $ (W
+ 23 + b(d))
h(x,)
d=1
N D. ΣΣ (d) d=1
*(WPo))))) (+ (d) + yd) wi h(æ,)
Tj - b(d)
(34)
Similar to the derivation in Section 2.1, the partial derivatives of Li with respect to the primal variable Wa. d = 1,..... Dv, have to vanish for optimality, which leads to
Ow L1 wa- [(ay(d) - (a)))) O ()oo),))
N
N
+ (Wor)n)))
h(x,) = 0 + w. = (a, - (d)(d)
h(æ,)
(35)
Note that here we only find the form of the optimal solution for W [w]..... WD.J The optimal value of WPwj can then be found by optimization algorithm such as the (stochastic) gradient descent when training the transformer.
Let ; = [1:1 ..... h(m;)
av(D.)-a;(D)jT .j = 1,..., N, we obtain the following support vector h(mz)
expansion of the function f:
Σ (ay(1) - o1(()) Φ (WP))))))
N
Σ (a,(D))) (D.)) Φ (P xx,)
f(x)
b,
h(
h(x;))
h(x²)
N (1) Φ (P)ol))) T (WPrio)
N Or (D.) -āz( $ (WWpll))
T x (B
+ x + b.
h(ær)
h(x)
h(z²)
h(x))
db ((Wrmiz)) x) T 4 (Wrwj x)
U2 + +b.
(36)
h(x))
Residual connection
Here, the support vector expansion of f already includes a residual connection. The softmax attention can then be derived by selecting h()) = Σn & (WFro) Φ (WProlzy) and choosing & as in Eqn. 28 in Section 2.1. Note that in Eqn. 36, {zz ( and x are the training samples and test sample, respectively. In order to derive the key, query, and value matrix projections in attention, we can then relax Eqn. 36 by letting W W WRæ, W Woæ, by Wvæ, and choosing the test sample among the training samples {
21

---

Published as a conference paper at ICLR 2023
Remark 6 Here, for self- attention, choose the test sample x among the training samples { { to compute the attention score of a token to other tokens in the same sequence. For pross-attention where token in sequence attends to tokens in another sequence, this constraint can be removed.
G 2D-CONVOLUTION ATTENTION
In this section, we discuss attention with 2D-convolution. Suppose we are given a training data {(xfrain yr )...., NN gaain XN C X x V. where == R. and ) RD: Here, afrain
N are the training inputs, and yfrain ..... y
the training tar-
gets. Let Xtrain E RN NNw xD= be the 3D-tensor of training inputs, where Xtrasn (h, w.d)
(d). Given new set of inputs { NNx NNw C X' and the corresponding
NWw x(h-1)+w
3D-tensor X E RN x Nw x Dr of these inputs, where (hh, w, d) = 2 NN x (I- ((h--))w((d)) We consider the function f applying on the 3D-tensor X and taking the following form
Φ (Flatten (Conn2D(X, 8))()) i i= 1, i::...,,NN No x Nw
f(æ,) = W
(37)
h(æ,))
where Conv2D is the depth-wise 2D-convolution (Howard et al., 2017), with the kernel size 8 x 8 and identical kernel channels, applied on the input tensor X. Here, the last dimension of X. ie., D., is the depth. Also, ((x) = [0)(x)..., ŌD, E Re, W = [wi...., WD.] E DDxDD, bE RDD, and h is a vector-scalar function. We fit the function f to the training data frasn
grasa N) with an L2 regularization on W, i.e. a ridge regres- sion, by solving the following convex optimization problem:
(artrain y( ), .... (ar N2 N NN N
Nux.Nw D. Σ
D. Σ
NuxNN D.
minimize W
W CC
+
Σ
+(())+$((()))))
1
ua 12 +C
Σ
Σ
(s,(d) - E5((0)
2
2
e, E, M NW
d=1
d=1
j=1
d=l
(Flateen (CnvvDD train .s)(()) b(d) S < (,)
y grain (d) w
1ax Tramn
subject to
w
① (Flltteen (Conv2D
train
5) s))())
+ b(d) y train (d) S E (d)
h( Frass)
(d) 2 0, j 1. NH x Nw, d -....,, D
(38)
The Lagrangian of the optimization problem 38 is given by
Nu x Nw
D,
NaxNN De Σ
C ::=:
1
+C
Σ
[d(d) + E,())
(d(5) + (d(d)(;
2
d=1
d=1
Nu
D.
+ (Flatten(Conv2DD train
train .8)(())
Σ
(d(())
6 6 Edd
U traón (d) + w
+ b(d)
h(2)
j=1
d=1
NuxNw
D.
(Tlaaten(Conv2D.. trtrann train 8))(s))
Σ
Σ
(d)d)
( E+(E + U train (d) wi
b(d)
(rain)
(39)
Similar to the derivation in Section 2.1 in the main text, the partial derivatives of L with respect to the primal variable wa, d = 1,..., Dr, have to vanish for optimality, which leads to
NH Σ
$ & (Flatten (Conv2D train train ,))(()) 0
Ow L = LWWd
(az(d) (d)
(40)
(x train)
1=1
NuxNw
train +))
+ Wid =
Σ
(a,(d) - az(())
h( h (rain)
(41)
1=1
22

---

Published as a conference paper at ICLR 2023
Let 2y ( h(a)
a, (iDD))_;(DD.. j ,u. x Nw, and substitute Equ. 41 into hi= ((a))
Eqn. 38, we obtain the following support vector expansion of the linear basis function f:
Nu
a2(1) -,(1)=ā(11) Aij h(a,)
NH
Aij h(æz;)
f(x;) =
Σ
+ b,,
h(ar)rann)
j=1
2
Nu x Nw
Aij 0/ -b,
(42)
h(x;)
where A.j == ((Flatten (Cnn si) T (CatateenCoo2(((("") .))()))
Same as in Section 2.1, set b, 0. To derive the softmax normalization in attention, we choose h(x;)= j= Aij and select Tb as in Eqn. 28. Let the training inputs {afrain, ..... Nx NNw X be the attention keys {ki..... kN x Nw C XC, where ÆC = RD, in self-attention. Also, let the new inputs { Nr XNw J C X be the attention queries {q1 (q).-... NNN,NNN K. in self-attention. We define the ID-Convolution Attention AttenttionCCnn2D) as follows:
Definition 3 (2D-Convolution Attention) Given set of the key and value vectors {k;, Vj " NNw
and a set of the query vectors { NNxNNw Denote the key tensor and the query tensor by K E R N xD and Q NR x xD respectively, where K(h, w. d) = x(b-)(b (dd) and
Qhh, w. d) 4Nw x(hh-)+w((l)) (d). The 2DDConvolution Attention Iattention-Con/e computes the corresponding output vector h, of the query qi by the following attention formula:
ho Σ softmax (oaitten(oon2(((... (i) Flatten(Con/2De s))G)/D) Uj.
(43)
where the Cono2D( s) is the depth-wise 2D-convolution (Howard et al., 2017) with the kernel size X and identical kernel channels.
Remark 7 (Convolutional Projection for Attention in the Convolutional vision Transformer)
The convolutional projections used in the Convolutional vision Transformer (CvT) (Wu et al., 2021) can be derived from Eqn. 42 by letting the training input tensor ttrasn to be the 2D input matrix of size N X Da of the self-attention layer (see Section 1.1 in the main text) reshaped into a 3D tensor of size NH X Nw Da where N- Nu Nw. Here, to avoid confusion, we denote the inpul of the self-attention layer by Xinput and its reshaped version by Reshape2 ( xinput). We then replace the depth-wise -D-covvolution by the depth-wise separable 2D-convolution in (Wu et al., 2021) and remove the constraint that the kernels have identical channels. In order to derive the convolutional projections for the keys, queries, and values in CVT, for i, 1...., N, we let kj Flatten Conv2D ( train ;s))(i)) ((Flatten( (ConnDCC (Reshape2De) imput), 8, W k))
Conv2D q: Flatten Flatten(Conv)) (Dx, s))( 4 (ooatten (ReshapeeRe X imput) s, WQ))(i),
(ximput) (miputt)
2y = Flatten Flatten(Comm20) CD train traii (rrronnns))))))) s)) = 4FFlateen (aateen(Coo222DD0 Conv2D (X imput), s, W ()).
(44)
Here, we specify the kernel/filter W K. Wo, and Wv v to emphasize that the convolutional projec- tions in CvT uses different kernels to compute keys, queries, and values in self-attention. Eqn. 44 matches the convolutional projects in CvT. By choosing h and & similar to above, can derive the convolutional attention in CvT.
H ID-CONVOLUTION ATTENTION
Following the derivation for the Attention-Conv2D in Appendix G above, can derive the ID- Convolution Attention (Attention-Cony ID) in a similar way by letting Xtrain E ND and X Nx, be 2D-matrices of training inputs and new inputs, respectively, and by replacing Conv2D by Conv ID, which is the depth-wise ID-oonvolution, with the kernel size x 1 and identical kernel channels, applied on the input tensor X. Here, the last dimension of X, i.e., Dz, is the depth. We define the ID-Convolution Attention Iitention-Convllle as follows:
N. Definition 4 (ID-Convolution Attention) Given set of the key and value vectors (kj, Uz 15) and set of the query vectors (g)) Denote the key matrix and the query matrix by K
23

---

Published as a conference paper at ICLR 2023
(kI....,yy] RN and Q iq...... qx1 E RNXD, respectively. The ID- D--Covvlutiinn
Attention (Atention-Com ConvID) computes the corresponding output vector h2 of the query qi by the following attention formula:
N
h, Σ
softmax (ComID(Q,.)))) Com:ID(K, >WD/VD) V/.
(45)
1=1
where the Conw D(,,8) 8) is the depth-wise ID-convolution with the kernel size 8 x and identical kernel channels.
I ATTENTION WITH BATCH NORMALIZATION AND SCALED HEADS
combines both the Attention-Be BN and Attention-SH. The The BN+SH fits the function f³ ) ).... (k uNH }} C KC x y of different sizes {(k), vih..., (Ny, )..... {((K( -1
Attention
Attention-BN+SH
1..... H. in Eqn. 17 with training sets
Ni...., ,H, where K. = RDD and y = -R. The function f is defined as:
f*(x) W 8((x 2²) o s
b"
(46)
h< 12t)
where
1
1
Td
(e(d))="(dd))
Vof te
VOB +e
(47)
Following the same derivation as in Section 2.1, we derive the following support vector expansion of f
N₂ (((x (1)) @ ((k) -1a) = O5*
(x)x)) =
D5 b".
(48)
h<((x 11) O 1
(1))-)
((DD))a;110 ((k; jos
where aá and āj are the dual variables, N. Same as Section 2.1. in Eqn. 48, we choose in Equ. 28, h*(x) ΣS (kf)) and ba = 0 to obtain the Batch Normalized Attention with Scaled Heads (Attention- Atteettio-BNN+SH), which defined as follows:
Here, 03- ((ke - )0x"
j
Definition 5 (Batch Normalized Attention with Scaled Heads) Given H sets of the key and value
vectors {k) v N j=1..... (k V -- for each set of H query vectors q...... q." i I.....N. N, the Batch Normalized Attention with Scaled Heads (Attention-BN) -SH+ computes the corresponding output vector h; of the queries q. ,.....,
g by the following attention formula:
H
No
h;
--
WO
Σ
softmax ((g) - -2) 1 ) [(k)) - v²) Os" (/Oo))//VD))))
(49)
==1
where
N.
[
N. (k)(d) 11" (d))²
1
11a
o
N
Vot tc
VoD tc
N
(50)
Following the same Remark 5 Section 2.3.2, given input sequence X = [ N E NxD. of feature vectors in self-attention, in order to generate the sets of (kj. v3 1 at the scale st we can downsample the input X before projecting into the key matrix K and the value matrix V. In this paper, we use the average-pooling to downsample X.
As in the same case of Attention-BN, for Miention-BN+SIL recentering queries and keys alone are sufficient for accuracy improvement, and we weight the mean f in Eqn 49 with a constant 8. Hence Eqn. 49 is simplified to:
h4 Σ W
Σ softmax (aa: - -8p) (k5 3/t)\VD) 0z
(k
(51)
24

---

Published as a conference paper at ICLR 2023
Table 12: The values of / for Linear Attention BBH and Sparse Attention Attention-BN/BN-aa BI-BB+BBBHHHH trained on the selected 10 UEA tasks.
Dataset/Model
Lincar Attention-Bi
Linear Attention- BN+SH
Sparse Attention BN
Sparse Attention IitettionBN-SH
ETHANOLCONCENTRAIE
0.15
0.95
0.8
0.2
FACEDETECTION
HANDWRITING
0.25
0.3
0.3
HEARTBEAT
01.
0.15
0.4
0.5
VAPANESEVOWELS SF
0.6
0.6
0.6
0.6
0.35
0.65
SELFREGULAATIONSCC)
0.35
0.25
0.1
0.9
SELFREGUULATIONSSCF2
0.75
0.15
0.5
0.3
SPOKENARARICDDGGI
01.6
0.6
0.6
UWAVEGESTURSLLBRAYY
0.65
0.55
0.3
Table 13: The values of 3 for Attention- AttentionBN/BBN-HH trained on 25 UEA Time Series classification tasks (Bagnall et al., 2018) and 6 UEA Time Series Regression tasks.
Dutaset/Model
Attention-BN
Mitetion-BN--Se
ETHANOL CONCENTRATION
0.25
0.15
FACEDETECTION
0.6
0.6
RITDNGI
0.65
0.25
HEARTBEAT
0.55
0.85
JAPANESEVOWEL
0.6
0.6
PEMS-SF
0.25
0.35
SELFREGULATIONSCII
SELFREGULATIONSCF2
1.2
0.9
PPOKENARABICDIGITSS
0.65
0.6
UWAVEGESTTURELIBRARY
0.1
0.2
ARTICULARY WETTCULARYWORRRRCOGGNNTTO
0.6
BASICMOTIONS
0.1
EPILEPSY
0.3
0.2
ERING
0.1
0.9
FINGER
LIBRAS
0.3
0.7
NATOPS
1.0
0.4
RACKETSPORTS
1.0
0.4
ATRIALFFIBIILLATION
CRICKET
0.2
1.0
S STANDWALKJUMP
1.0
0.6
MANDMOVEEENTDDRECTII
0.5
LSST
0.3
0.2
DuCKDUCKGEESE
0.6
0.3
MOTORIMAGERY
0.2
0.3
APPLIANCESÉNERGY
0.4
0.2
BENZENECONCENTRAATION
BEIINGPM25
0.1
0.2
HIVEFUELMOISTUREE
0.1
0.3
JEEEPPG
0.2
Table 14: The values of 3 of Attention-BNBNNASH trained on the tasks of the LRA benchmark (Tay et al., 2021).
Dataset/Moel
Attention- BN
Attention BN+SH
LiSTÖPS
0.5
(1.2
TEXT
0.5
0.8
RETRIEVAL
1.0
IMAGE
PATHFINDER
0.2
0.4
J HYPERPARAMETERS
In this section, provide the parametarss for our best models.
J.1 UEA TIME SERIES CLASSIFICATION AND REGRESSION
For these two benchmarks, use the set of downsampling factors 1,, 2, for Attention- SH/BN+SH and Linear/Sparse Attention-SH/BNN4SS SH/BN+SH models trained on the UEA benchmark. Ta- ble 13 and Table 12 provide the values of 3 used for our best Attention-BN/BN-SS BN/BN+SH and Linear AttentionBNN/BN--S SN, Sparse Attention Birionn-B/BNN-E models trained on subsets of the two bench- marks.
25

---

Published as a conference paper at ICLR 2023
J.2 LONG RANGE ARENA BENCHMARK
For all tasks of the LRA benchmark, we set the downsampling factors s of SSentioonSH/BN+SH.. Linear/Sparse Attention-SH/BBNE
is [1. 2] and kernel size of Attention-Conv ID models is 5. In addition, Table 14 provides the values / of Attention- Bittiion-B/BN+SEE models trained on the benchmark.
J.3 IMAGENET CLASSIFICATION
This task's 3 of AttentionBBN/BN-SI is 1. [1, 1, 2, 4), and the kernel size of (tteniin-Coon2)) is (2, 2).
has the downsampling factor of
26


Reviews:
[{"review_id": "yDsQ796QNeJ", "reviewer": "Reviewer_ZNRr", "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": "The paper proposes the primal-dual framework to derive popular self-attention mechanisms. The framework bases on a support vector expansion by solving a support vector regression problem. The paper shows that several popular self-attention mechanisms can be derived under the framework. It also invents two new self-attention mechanisms by employing the batch normalization and different amounts of training data, respectively. Experiments demonstrate the advantages of the proposed two self-attention mechanisms by comparing with the softmax self-attention. ", "summary_of_the_review": "The paper presents a framework to derive some popular self-attention mechanisms. It also invents two new self-attention mechanisms, which outperform the softmax self-attention. These two contributions are novel and well-supported. However, the proposed framework lacks practical and theoretical guidance, which needs to be further strengthened.", "strength_and_weaknesses": "Strength:\nThe paper presents a framework to derive the popular self-attention mechanisms, which is based on support vector expansion. Then one may develop self-attention mechanisms that do not rely on heuristics and experience. Notably, the proposed framework could derive many popular self-attention mechanisms. Also, it invents two new mechanisms. These demonstrate the effectiveness of the proposed framework.\n\nWeaknesses:\nThe main weakness is that the proposed framework lacks practical and theoretical guidance. \nFirst, what is the motivation of the used function in (4)? Why is the function \\Phi(x) divided by the vector-scalar function h(x)? \nSecond, are there any rules for choosing \\Phi(x) and h(x)? Can any function be used as \\Phi(x) or h(x)? The invented two new self-attention mechanisms still from the existing experiences.\nThird, what makes one self-attention mechanism performs better? Could this be explained by the support vector expansion?\nForth, the paper shows that some self-attention mechanisms can be combined together. Can the proposed framework derive these combinations?\n\nOther comments:\nIt is better to include the linear, sparse, multi-head self-attentions in all the comparisons. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uPFdNFNsbY", "reviewer": "Reviewer_ipYM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 shows that self-attention mechanisms can be derived by finding the support vector expansion of a support vector regression (SVR) problem. The key contribution of this paper is the framework proposed in Section 2, which links attention mechanisms to support vector regression problems, and provides a different way of deriving attention mechanisms. The paper re-derives softmax, sparse, and multihead attention mechanisms using their proposed framework, and derives two new attention mechanisms: batch normalized and multiresolution head attention.", "summary_of_the_review": "Overall, I believe this paper proposes a new \"interpretation\" of self-attention by theoretically linking it to support vector expansion, and provides empirical evidence that new attention mechanisms derived using this link perform well. However, I believe the proposed framework still involves the usage of heuristics and intuition to derive new attention mechanisms. Nevertheless, the framework paves the way towards a more principled way of deriving new self-attention mechanisms in the future.", "strength_and_weaknesses": "This paper has several strengths:\n\n1. It is very well written: The problem is well motivated, the background on self attention is useful for optimization researchers who are not familiar with transformers, and the notation and theoretical results are clearly described.\n\n2. The problem considered is important: Since self attention plays such an important role in the performance of transformers, new and more principled ways to discover better attention mechanisms will further improve this performance.\n\n3. The theoretical results are novel: I am not aware of the connection between support vector expansions and transformers derived in this paper, and I believe this is a clever observation that is backed up theoretically.\n\nHowever, it has a few weaknesses:\n\n1. Is the proposed framework really principled? Deriving new attention mechanisms using the proposed framework involves changing the the SVR problem and the primal neural network layer. However, *how* to change the SVR problem and the primal neural network layers still appears to involve intuition and heuristics. In Section 2.3, the paper derives 2 new attention mechanisms, but there is nothing to foretell which of these attention mechanisms is superior to the other (without empirical evaluation). As such, I am not sure whether the proposed framework (in its current form) is really more principled than current practice.\n\n2. The empirical evaluation of the new attention mechanisms is not conclusive: Based on the results in Table 1, it is unclear whether Attention-BN or Attention-BH is to be preferred overall, which undermines the goal of this paper of providing a principled way to design attention mechanisms. The baselines are also fairly sparse (just one attention mechanism) and arbitrary subsets of public datasets were used for evaluation (without justification).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "Not applicable"}, "extra_text": {}}, {"review_id": "lbsW1-eAupq", "reviewer": "Reviewer_fLYg", "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": "This paper first proves that the self-attention mechanism in neural networks is a special form of support vector regression. Based on this conclusion, the authors proposed a principle to develop attention and designed the Attention-BN and the Attention-SH for improving accuracy and efficiency. Experimental results demonstrated that their methods have better performance than conventional attention methods.", "summary_of_the_review": "This paper gives me a new perspective to understand attention. This research is meaningful to deep learning, and my score is 6.", "strength_and_weaknesses": "Strength: This paper gave detailed mathematical proof of the relation between the attention mechanism and the support vector regression, which inspired me a lot because most previous attention methods were designed based on intuition and experiences. This paper also proposed a framework for how to develop attention that is meaningful for future research.\n\nWeaknesses: The motivation and intuitive interpretation of Attention-BN and Attention-SH should be discussed more. I can not fully understand what inspired you to design these two novel attention methods. More insightful discussion can be provided. And one thing comes to my mind, can these two attention methods benefit some practical vision problems, such as semantic segmentation?  Can the proposed framework help develop some CNN-related attention modules, such as CBAM?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "fM_uQXKSZRR", "reviewer": "Reviewer_2btF", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper proposes a primal-dual interpretation between neural network layers and self-attention through support vector expansion from a Support Vector Regression (SVR) problem. Based on this insight, the paper derives well-known attention mechanisms such as linear, sparse, and multi-head attention. The paper also proposes two new attention methods, 1) Batch Normalized Attention (Attention-BN) and 2) Attention with Scaled Head (Attention-SH), leveraging the SVR interpretation. Experiments on UEA Time-Series, Long Range Arena, and ImageNet benchmarks show that the proposed methods show improvements in performance as well as efficiency compared to the baseline softmax attention.", "summary_of_the_review": "The paper proposes an interesting direction of interpreting self-attention as a dual formulation of the SVR problem on a neural network layer. However, the newly proposed attention mechanisms as well as presented experiments are not convincing enough to fully assert the significance of the primal-dual framework.", "strength_and_weaknesses": "### Strengths\n\n- The paper presents an interesting discovery that connects neural network layers and self-attention via a primal-dual formulation of the SVR problem.\n- A wide range of experimentation has been conducted across multiple well-known benchmarks, together covering various input modalities such as time-series and images. \n- The advantage of proposed methods is also supported with comprehensive analyses measuring the empirical efficiency as well as redundancy across attention heads.\n\n### Weaknesses\n\n- The motivation is a bit unclear: the introduction mentions that \"most attention layers are developed based on intuitions and heuristic approaches\", but the SVR formulation and presented experiments do not provide much further insight, as to whether utilizing the dual-formulation of a neural network layer can bring significant benefit towards better attention-based model diversity and/or performance.\n- Related to the previous comment, the new attention mechanisms, Attention-BN and Attention-SH, somewhat overlap with existing methods to be considered empirically novel. For instance, Attention-SH with sequence subsampling is similar to existing work on convolution-augmented attention [1,2]. Further utilizing the different design choices in the SVR formulation (e.g. choosing a different normalization $h(x)$) could bring a larger impact and increase the value of the primal-dual interpretation.\n- Experimental results are slightly lacking as it does not show results across all 30 and 5 tasks available in UEA Time-Series and Long Range Arena benchmarks, respectively. Is there a specific reason why experiments were run on subsets from the two benchmarks instead of the entire set of tasks? If not, could the comprehensive results from all tasks be shared as well?\n\n[1] Gulati et al., 2020. Conformer: Convolution-augmented Transformer for Speech Recognition.  \n[2] Wu et al., 2021. CvT: Introducing Convolutions to Vision Transformers.\n\n\n### Other questions/comments\n\n- What are the hyperparameter setups tested for 1) the mean weighting factor $\\beta$ and 2) downsampling scales for Attention-SH/SH+BN? For better reproducibility, what were the actual values used for the results presented?\n- Is there a reason behind having the weighting factor $\\beta$ as a constant given as hyperparameter? In order to have Attention-BN/BN+SH \"flexibly adjust the effect of normalization\", letting $\\beta$ be a trainable parameter similar to the scale and shift parameters in BatchNorm seems more suitable than fixing it as constant.\n- Given that all experimental results are averaged over 5 runs with different seeds, could the standard deviations be added in Tables 1, 2, and 3?\n- How is the head redundancy measured with average $\\mathcal{L}_2$-distance? What do the \"distances between heads\" exactly measure? \n- In Equation 12, gathering all the $D^{1/4}$ terms in the numerator results in $D^{j/4}$, which doesn't lead to the $\\sqrt{D}$ term in Equation 14. Is there an additional step that is missing?\n- Duplicate indexing by $j$ in Equation 11.\n- Typo in Remark 1: \"As a results\" &rarr; \"As a result\"\n- Typo after Equation 24: \"... less and vice versus.\" &rarr; \"... less and vice versa.\"\n- Typo in Table 1 (Attention-BN+SH on HeartBeat): Should it be 76.26 instead of 72.26?\n- Typo in Section 4: \"... more efficiency than the baseline.\" &rarr; \"... more efficient than the baseline.\"\n- Typo in Appendix A: \"... recentering keys and values alone ...\" &rarr; Should it be \"... recentering queries and keys alone ...\"?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Hgpa_EzWZL", "reviewer": "Reviewer_W46E", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper provides a primal-dual formulation to derive self-attention as a solution to the support vector regression problem having the primal formulation in the form of a neural network layer. The formulation allows the authors to derive various types of attention: linear, softmax, sparse, and multi-head attention using different design choices/ constraints. Two new attention mechanisms are then proposed in the paper. Performance is evaluated on 3 benchmarks with small (seemingly statistically significant) improvements in accuracy and impressive improvements in efficiency.\n", "summary_of_the_review": "The paper self-attention as a solution to the SVR problem which unifies several attention mechanisms in a single optimization framework. The contribution is novel and has a potential for high technical impact. Two new types of attention are proposed using this framework along with combined attention which shows modest improvement in accuracy but with significant efficiency gains. The quality of submission is good. Overall, it is a good contribution to the field.\n", "strength_and_weaknesses": "## Strengths\n- The paper makes novel connections between attention mechanisms in DNNs and SVR - support vector regression. It shows that formulating the network layer as a solution to the ridge regression convex optimization problem, the support vector expansion has the form of self-attention.\n- It shows that several different attention types can be derived from different design choices in the SVR formulation thus unifying the approach to designing different types of attention.\n- It then proposes two new attention mechanisms - one inspired by batch normalization, and another with scaled (multiresolution) attention heads.\n- The paper has a potential for high technical impact. \n- It evaluates the performance of the new attention mechanisms (and a combined one) on three benchmarks, demonstrating improvement in both accuracy and performance (efficiency). The performance evaluation is convincing. \n\n## Weaknesses\n- __(W.1)__ While it is clear that different design choices lead to different kinds of attention, the paper doesn’t provide intuition or meta-level criteria that could be used to make these design choices. It would be great if the authors provide a discussion of these.\n- __(W.2.1)__ The paper mentions that the results are averaged over 5 runs. It is recommended that the spread around the mean is also added to the performance tables to allow the assessment of statistical significance of the gain in accuracy.\n- __(W.2.2) UEA TMC__: In Table 1, (a) Most results (~50%) are within one percent of each other. Is this statistically significant? Kindly explain using the spread over 5/ 10 runs. (b) For the HeartBeat dataset, the Attention-BN+SH model is not only significantly worse than the Softmax attention baseline but also Attention-BN and Attention-SH which are both better than the baseline. Kindly explain the anomaly.\n- __(W.2.3) LRA__: In Table 2,  only results on the Retrieval dataset seem to be significantly better (I’m assuming significant if performance improvement is > 1%). Kindly explain the results using the spread over 5/ 10 runs. \n- __(W.2.4) ImageNet__: In Table 1, (a) Results are within one percent of each other. Is this statistically significant? Kindly explain using the spread over 5/ 10 runs. (b) For Top-5 accuracy, the Attention-BN+SH model is not only significantly worse (almost 20% in absolute terms) than the Softmax attention baseline but also Attention-BN and Attention-SH. Kindly explain the anomaly.\n- __(W.3) Combining Attentions__: Explain the intuition behind combining Attention-BN+SH with Linear Attention and why it’s expected to perform better.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "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: Accept: notable-top-25%