Kronecker Attention Networks
Authors: Hongyang Gao
Zhengyang Wang
Shuiwang Ji
Venue:  (2020)

Abstract: Attention operators have been applied on both 1-D data like texts and higher-order data such as images and videos. Use of attention operators on high-order data requires flattening of the spatial or spatial-temporal dimensions into a vector, which is assumed to follow a multivariate normal distribution. This not only incurs excessive requirements on computational resources, but also fails to preserve structures in data. In this work, we propose to avoid flattening by developing Kronecker attention operators (KAOs) that operate on high-order tensor data directly. KAOs lead to dramatic reductions in computational resources. Moreover, we analyze KAOs theoretically from a probabilistic perspective and point out that KAOs assume the data follow matrix-variate normal distributions. Experimental results show that KAOs reduce the amount of required computational resources by a factor of hundreds, with larger factors for higher-dimensional and higher-order data. Results also show that networks with KAOs outperform models without attention, while achieving competitive performance as those with original attention operators.

Under review as a conference paper at ICLR 2020
KRONECKER ATTENTION NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Attention operators have been applied on both 1-D data like texts and higher-order data such as images and videos. Use of attention operators on high-order data requires flattening of the spatial or spatial-temporal dimensions into vector, which is assumed to follow a multivariate normal distribution. This not only incurs exces- sive requirements on computational resources, but also fails preserve structures in data. In this work, we propose to avoid flattening by developing Kronecker atten- tion operators (KAOs) that operate on high-order tensor data directly. KAOs lead to dramatic reductions in computational resources. Moreover, we analyze KAOs theoretically from probabilistic perspective and point out that KAOs assume the data follow matrix-variate normal distributions. Experimental results show that KAOs reduce the amount of required computational resources by a factor of hundreds, with larger factors for higher-dimennional and higher-order data. Results also show that networks with KAOs outperform models without attention, while achieving competitive performance those with original attention operators.
INTRODUCTION
Deep learning networks with attention operators have demonstrated great capabilities of solving challenging problems in various tasks such as computer vision (Xu et al. 2015; Lu et al.] (2016), natural language processing (Bahdanau et al. 2015: Vaswani al.) 2017), and network embed- ding (Veličković et al. (017). Attention operators are capable of capturing long-range relationships and brings significant performance boosts (Li et al. 2018 Malinowski al., 2018). The application scenarios of attention operators range from 1-D data like texts to high-order and high-dimensional data such as images and videos. However, attention operators suffer from the excessive usage of computational resources when applied on high-order or nigh-dimensional data. The memory and computational cost increases dramatically with the increase of input orders and dimensions. This prevents attention operators from being applied in broader scenarios. To address this limitation, some studies focus on reducing spatial sizes of inputs such as down-sampling input data (Wang et al. (018) or attending selected part of data (Huang et al. 2018). However, such kind of methods inevitably results in information and performance loss.
In this work, we propose novel and efficient attention operators, known Kronecker attention operators (KAOs), for high-order data, which avoid flattening and operate on high-order data directly. Experimental results show that KAOs are effective original attention operators, while dramat- ically reducing the amount of required computational resources. In particular, we employ KAOs to design a family of efficient modules, leading our compact deep models known Kronecker attention networks (KANets). KANets significantly outperform prior compact models on the image classification task, with fewer parameters and less computational cost. We also investigate the above problem from probabilistic perspective. Specifically, regular attention operators flatten the data and assume the flattened data follow multivariate normal distributions. This assumption not only results in high computational cost and memory usage, but also fails to preserve the spatial or ppatial-teppone structures of data. Our KAOs, instead, use matrix-variate normal distributions to model the data, where the Kronecker covariance structure is able to capture relationships among spatial or spatial-temporal dimensions.
BACKGROUND AND RELATED WORK
In this section, we describe the attention and related non-local operators.

---

Under review as a conference paper at ICLR 2020
2.1 ATTENTION OPERATOR
The inputs to an attention operator include a query matrix Q = [qi. 92, "0. Rdxm, a key matrix K = Ke, kn] ]
Rdxn, and a value matrix V [V1. V2: "" y R The attention operation computes the responses of a query vector qi by attending it to all key vectors in K and uses the results to take a weighted sum over value vectors in V. The layer-wise forward-propageen operation of an attention operator be expressed as O Vsoftmax (K* Q). Matrix multiplication between Kf and Q results in coefficient matrix E K'K in which each element Ciy is calculated by the inner product between k. and q, This coefficient matrix E computes similarity scores between every query vector qi and every key vector k, and is normalized by a column-wise softmax operator make every column sum to 1. The output O E R is obtained by multiplying V with the normalized E. In self-attention operators (Vaswani et al. 2017). we have Q = K V. The computational cost in attention operator O(m x n (d p)). The memory required for storing the intermediate coefficient matrix E is ((m)). If d = and m n, the time and space complexities become 0m3 d) and ((m²), respectively. There are several other ways compute E from Q and K, including Gaussian function, dot product, concatenation, and embedded Gaussian function. It has been shown that dot product is the simplest but most effective one (Wang et al.) 2018). Therefore, we focus on the dot product similarity function in this work. In practice, we can first perform separate linear transformations on each input matrix, resulting in the following attention operator: O = W V Softmax (WK K)TWQQ Q), where W R xp, W IR xd and W Rd For notational simplicity, omit linear transformations in the following discussion.
2.2 NON-LOCAL OPERATOR
Non-local operators (Wang et al, 2018 ap- ply self-attention operators on higher-order data such as images and videos. Taking 2-D data as an example, the input the non-local operator is a third-order tensor X e Rxxxxe where h, w, and e denote the height, width, and number of channels, respectively. The tensor is first con- verted into matrix X (3) e Rexho by unfolding along mode-3 (Kolda & Bader 2009). as illus- trated in Figure I Then we perform the attention operation by setting Q = K
Figure 1: Conversion of third-order tensor into matrix by unfolding along mode-3. In this example, a x
tensor unfolded into a hw matrix.
X(3) The output of the attention operator is converted back to a third-order tensor the final output. One practical challenge the non non-local operator is its excessive usage of computational resources. h- w. the computational cost of 2-D non-local operator is Ohh* c). The memory used to store the coefficient matrix incurs (Ir+) space complexity. The time and space complexities are prohibitively high for high- digh-dimensional and high-order data.
3 KRONECKER ATTENTION NETWORKS
In this section, we describe our proposed Kronecker attention operators, which are efficient and effective attention operators on high-order data.
3.1 KRONECKER ATTENTION OPERATORS
We describe the Kronecker attention operators (KAO) in the context of self-attention on 2-D data, but they can be easily generalized to generic attentions. In this case, the input the éth layer is a third-order tensor (x)) hxxxxx We propose to use horizontal and lateral average matrices to represent original mode-3 unfolding without much information loss. The horizontal average matrix H and the lateral average matrix L are computed as
h
W
H
L
T
(1)
where x and X . are the horizontal and lateral slices Kolda & Bader 2009 of tensor x(())
respectively. We then form matrix C by juxtaposing HT and L C H L (h+
2

---

Under review as a conference paper at ICLR 2020
Donzzntal
Honizooaa
Comoliziio (ogtood)
Commizion loptzoa)
Canwo sieon loptical)
Cansoation Esptical:
Ang
Ang
Cafald
Undodd
Uafbld
Undald
Corseltben
Comvocation Oopional
Compoleborn Coptosal
Comrolabonn (ostonsl
(optocall
(opóocal)
1m
K ttention Operator
thention Operator
A tteenton Opeaator
Outar
saam
Pold
G
(b)
(d)
Figure 2: Illustrations of regular attention operator (a), KAO (b) and KAO (c) on 2-D data. In the regular attention operator (a), the input tensor is unfolded into mode-3 matrix and fed into the attention operator. The output of the attention operator is folded back to a tensor as the final output. In KAO (b), juxtapose the horizontal and lateral average matrices derived from the input tensor as the key and value matrices. We keep the mode-3 unfolding of input tensor as the query matrix. In kKv (c), all three input matrices the juxtaposition of two average matrices. In contrast to KAO KV, we use an outer-sum operation to generate the output third-order tensor.
Based on the horizontal and lateral average matrices contained in C, we propose two Kronecker attention operators (KAOs), i.e., KAO kv and KAO In KAO as shown in Figure (b), we use x (2) the query matrix and C' as the key and value matrices (3)
0 = attn C,C)
Reche
(2)
Note that the number of columns in O depends on the number of query vectors. Thus, we obtain hw output vectors from the attention operation. Similar to the regular attention operator, O is folded back to a third-order tensor y()) hxxwxx by considering the column vectors in O as mode-3 fibers the output of layer f. If h w, the time and space complexities of KAO kv are Ohw x c x (h + w)) = O(h x e) and O(hw x (h+ + ()) = O(h)). respectively. Compared to the original local operator on 2-D data, KAO kV reduces time and space complexities by a factor of h.
of ( KAO uses (t())
In order to reduce the time and space complexities further, propose another operator known as KAO In KAO as shown in Figure c), we use C as the query, key, and value matrices as
H - attn(C, C,C) (h+w)) h
The final output tensor y e T hxxaxx is obtained as y( = -. L where H. and L, are the éth rows of the corresponding matrices. That is, the ith frontal slice of ((!) is obtained by computing the outer
of the ith rows of H and L. If w, the time and space complexities of KAO are O(hh + w) x ex wh+ O(h² c) and O((h+ w) (h + ()) O(h²), respectively. Thus, the time and space complexities have been reduced by a factor of h² as compared to the original local operator, and by a factor of h as compared to KAOgy. Note that do not consider linear transformations in our description, but they can be applied to all three input matrices in KAO ky and
KAO AR shown in Figure 2
3

---

Under review as a conference paper at ICLR 2020
3.2 KRONECKER ATTENTION MODULES AND NETWORKS
Attention models have not been used in compact deep models to date, primarily due to their high computational cost. In this section, we design a family of efficient Kronecker attention modules based on KAOS illustrated in Figure in the appendix.
Madele: MobileNetV2 (Sandler et al., 2018) is mainly composed of bottleneck blocks with inverted residuals. Each bottleneck block consists of three convolutional layers; those are, 1 x 1 convolutional layer, 3 x 3 depth-wise convolutional layer, and another 1 x 1 convolutional layer. Suppose the expansion factor is and stride is 8. Given input x((1) e Rexaux for the éth block, the first 1 x convolutional layer outputs re feature maps xx()) R.xxwxree The depth-wise convolutional
layer uses a stride of 8 and outputs re feature maps x)(() E IR 2 o xrc. The last 1 x 1 convolutional layer produces d feature maps y( R 5xd, When 1 and c d, skip connection is added between x((1) and (
To facilitate feature reuse and gradient back pack-propagttion in deep models, we improve the BaseMoodule by adding skip connection. Given input x(()) we use an expansion factor of r- for the first convolutional layer, instead of r as in BaseModule. We then concatenate the output with the original input, resulting in x e hxwwxre The other parts of the BaseSkipModule are the same as those of the Basule Compared to the BaseModule, the BaseSkipModule reduces the number of parameters by c x e and computational cost by h w x c. It achieves better feature reuse and gradient back- pack-propagation.
Masuul:pModuue:
We propose to add an attention operator into the BaseModule to enable the capture of global features. We reduce the expansion factor of the BaseModule by 1 and add a new parallel path with an attention operator that outputs feature maps. Concretely, after the depth-wise wise convolutional layer, the original path outputs x(() é R 4x 2 (x--1)) The attention operator, optionally followed by average pooling of stride if produces x, R =e Concatenating them gives (e( e IR #xrr The final x 1 convolutional layer remains the same. Within the attention operator, we only apply the linear transformation on the value matrix V to limit the number of parameters and required computational resources. In this module, the original path acts as locality-based feature extractors, while the new path with an attention operator computes global features. This enables the module to incorporate both local and global information. Note that in this module, including the regular attention operator and our KAOs.
Atdnle
use any attention operator
Moddle:p We propose to add additional skip connection in the AttnModule. This skip connection can always be added unless & > 1. The AttnSkipModule has the same amount of parameters and computational cost the AttnModule.
In the following sections, we perform some theoretical analysis on the proposed methods.
3.3 FROM MULTIVARIATE TO MATRIX- VARIATE DISTRIBUTIONS
We analyze our solutions for attention operators on high-order data from a probabilistic perspective. We take the non-local operator on 2-D data as an example. Formally, consider self-attention operator with Q = K = V X(3) (3), where X (3) e IR excwww is the mode-3 unfolding of a third-order input tensor
X E R hxxwxx as illustrated in Figure 1 The äth row of X(3) corresponds to vec( X..))" T ho
where X., E hoo denotes the ith frontal slice of X (Kolda & Bader 2009), and vec(-) denotes the vectorization of a matrix by concatenating its columns (Gupta &
The frontal slices X.1, X......, X hxw X are usually known as e feature maps. In this view, the mode-3 unfolding is equivalent to the vectorization of each feature map independently. It is worth noting that, in addition to vec(.), any other operation that transforms each feature map into a vector leads to the same output from the non-local operator, as long as a corresponding reverse operation is performed to fold the output into tensor. This fact indicates that unfolding of X in local operators ignores the structural information within each feature map, i.e., the relationships among rows and columns. In addition, such unfolding results in excessive requirements on computational resources, explained in Section 2.2
4

---

Under review as a conference paper at ICLR 2020
In the following discussions, focus feature map X [Xx1, 2.....,, X_e) by assuming feature maps are conditionally independent of each other, given feature maps of previous layers. This assumption is shared by many deep learning techniques that process each feature map independently. including the unfolding mentioned above, batch normalization, instance normalization (Ulyanov al. 2016), and pooling operations (LeCun et al. (998). To view the problem above from probabilistic perspective (loffe & Szegedy) 2015] Ulyanov et al., 2016), the unfolding yields the assumption that vec (X) follows multivariate normal distribution vec ~ NNh (1t, S2), where 4 R and S2 IR howher Apparently, the multivariate normal distribution does not explicitly model relationships among rows and columns in X. To address this limitation, we propose to model X using a matrix-variate normal distribution (Gupta & Nagar 2018), defined as below.
Definition 1. A random matrix A E R is said to follow a matrix-variate normal distribution MN mxn. (M, S2 @ D) with mean matrix M IR and covariance matrix 22 V, where IR mmxm and V R 0, if vec( AT) NN S (vec( MM) @ V)). Here, denotes the
Kronecker product Van Loan 2000 Graham 2018).
The matrix-variate normal distribution has separate covariance matrices for rows and columns. They interact through the Kronecker product to produce the covariance matrix for the original distribution. Specifically, for two elements Xij and Xzy from different rows and columns X, the relationship between Xij and X is modeled by the interactions between the ith and i' 3'th rows and the jth and j' th columns. Therefore, the matrix-variate variate normal distribution can incorporate relationships among rows and columns.
3.4 THE PROPOSED MEAN AND COVARTANCE STRUCTURES
In machine learning, (Kalaitzis et al. 2013) proposed to use the Kronecker sum to form covariance matrices, instead of the Kronecker product. Based on the above observations and studies, we propose to model X X .MN kxow (M, Ω @ ) where M E R Z R Rixh 0, v guxw > 0, @ denotes the Kronecker sum (Kalaitzis et al. 2013), defined as Q @ v @ [w] [[n] @ W, and identity matrix. Covanance matrices following the Kronecker sum structure can still capture the relationships among rows and columns (Kalaitzis et al.] (003)). It also follows from (Allen & Tibshirani 20T0; Wang et al., (017) that constraining the mean matrix M allows more direct modeling of the structural information within a feature map. Following these studies, we assume X follows a variant of the matrix-variate normal distribution as
[m]] denotes
X ~ MN hxw [, S + V
(4)
where the mean matrix M e Rhhx is restricted to be the outer sum of two vectors, defined as M μ 2 v =1("n] + I[aje"" where μ R,A,, e R" and [(n] denotes an all-one vector of size n.
Under this model, the marginal distributions of rows and columns are both multivariate normal (Allen & Tibshirani 2010). Specifically, the ith row vector X E lxx follows X (N, 4)), and the jth column vector X:; e fxx follows X.j ~N (vi+ μt, + In the following discussion, we assume that Z and V are diagonal, implying that any pair of variables in X are uncorrelated. Note that, although the variables in X are independent, their covariance matrix still follows the Kronecker covariance structure, thus capturing the relationships among rows and columns (Allen & Tibshirani 2010 Wang al. 2017).
3.5
MAIN TECHNICAL RESULTS
Let X EEA,, X/)hh Rd and X (Σ),, X,y\ww e R be the average of row and column vectors, respectively. Under the assumption above, X X and Xeot follow multivariate normal distributions
+ St +
X row No + U, h
(5)
X cot N ,r,
(6)
w
where Tt = (Eh. /h, π = (Eh, 9t ύ= (Σ uz)/w, and v = (Σ L w/)/ Our main technical results can be summarized in the following theorem.
5

---

Under review as a conference paper at ICLR 2020
Table 1: Comparisons between the regular attention operator, the regular attention operator with a pooling operation (Wang et al. 2018), and our proposed KAOkv and kAOgxv in terms of the number of parameters, MAdd, memory usage, and CPU inference time on data of different sizes. The input sizes are given in the format of "batch size spatial sizes x number of channels". "Attn" denotes the regular attention operator. "Attn+Pool" denotes the regular attention operator which employs 2 x 2 pooling operation on K and V input matrices to reduce required computational resources.
Input
Operator
MAdd
Memory
Saving
Time
Speedup
Attn
0.63m
5.2MB
0.00%
5.8ms
1.0x
Attn+Pool
0.16m
1.5MB
71.65%
2.0ms
3.0x
8 14t
KAO
0.09m
0.9MB
82.03%
1.7ms
3.5x
KAO
0.01m
0.3MB
95.06% %
0.8ms
6.8x
Attn
9.88m
79. 999MBB
0.00%
72.4ms
1.0x
Attn+Pool
2.47m
20.7MB
74.13%
20.9ms
3.5x
8 x 28 8
KAO kv
0.71m
6.5MB
91.88%
7.1ms
10.1x
KAO
0.05m
0,9MB
98.85%
1.7ms
40.9x
Attn
157,55m
1,262.6MB
0.00%
1,541.Ims
1.0x
Attn+Pool
39.39m
318.7MB
74.76%
396.9ms
3.9x
8 x 562 8
KAO 5.62m
48.2MB
96.18%
49.6ms
31.1x
KAO
0.21m
3.4MB
99.73%
5.1ms
305.8x
Theorem 1. Given the multivariate normal distributions in Eqs. (5) and (6) with diagonal and L
if (a) ....... ,, Fh are independent and identically distributed (i.id.) random vectors that follow the
distribution in Eq. 5). (b) C1, C2, C2,..., Cw are i.i.d. random vectors that follow the distribution Eq. (6) (c) ..... Th and C1. C2. ................................ Cw are independent, we have X -M [M, x-- @ U-
where X r2. " [c1, C2...., c. M (μ + v) (u+ .. In particular, if w, the (1 a v where tr(-) denotes matrix trace.
covariance matrix satisfies tr V+Ω @ 2-
The proof of Theorem can be found in the appendix. With certain normalization X, we have д V O, resulting in M fu v. As the trace of covariance matrix measures the total variation, Theorem 1 implies that X follows matrix-variate normal distribution with the same mean and scaled covariance as the distribution of X in Eq. (4) We build KAOs based on this conclusion and the process to obtain X from X.
4 EXPERIMENTAL. STUDIES
In this section, evaluate methods and networks on image classification and segmentation tasks.
4.1 COMPARISON COMPUTATIONAL EFFICIENCY
KAOs have efficiency advantages regular attention operators on high-order data, especially for inputs with large spatial sizes. We conduct simulated experiments to evaluate the theoretical results. To reduce the influence of external factors, we build networks composed of single attention operator, and apply the TensorFlow profile tool (Abadi et al. 2016) report the multiply-ade (MAdd), required memory, and time consumed on 2-D simulated data. For the simulated input data, we set the batch size and number of channels both to 8, and test three spatial sizes; those are, 56 x 56, 28 28, and 14 x 14. The number of output channels is also set to 8. Table summarizes the comparison results. On simulated data of spatial sizes 56 56, our KAO Kv and KAO achieve 31.1 and 305.8 times speedup, and 96. 18% and 99.73% memory saving compared to the regular attention operator, respectively. Our proposed KAOS show significant improvements over regular attention operators in terms of computational resources, which is consistent with the theoretical analysis. In particular, the amount of improvement increases as the spatial sizes increase. These results show that the proposed KAOs are efficient attention operators high-dimensional and high-order data.
According the theoretical analysis in Section 3.1

---

Under review as a conference paper at ICLR 2020
4.2 RESULTS ON IMAGE CLASSIFICATION
With the high efficiency of our KAOs, have proposed several efficient Kronecker attention modules for compact CNNs in Section 3.2
To further show the effectiveness of KAOs and the modules, we build novel compact CNNS known as Kronecker attention networks (KANets). Following the practices in [Wang et al.) 2018), we apply these modules on inputs of spatial sizes 28 x 28, 14x 14, and 7. The detailed network architecture is described in Table the appendix due to space constraint. We compare KANets with other CNNs on the ImageNet ILSVRC 2012 image classification dataset. which serves as the benchmark for compact CNNs (Howard et al. 2017 Zhang al., 2017 Gao
et al. 2018 Sandler et al. 2018). Details of the experimental setups are provided in the appendix.
The comparison results between our KANets and other CNNs in terms of the top-1 I accuracy, number of parameters, and MAdd are reported in Table 2 SqueezeNet (landola et al., 2016) has the least number of parameters, but uses the most MAdd and does not obtain competitive per-
Table 2: Comparisons between KANets and other
CNNs in terms of the top-1 accuracy on the Im- ageNet validation set, the number of total pa- rameters, and MAdd. We use KANetxv and
KANetoRV to denote KANets using KAO and
formance as compared to other compact CNNs.
KAO respectiivy.
Among compact CNNS, MobileNetV2 (San-
Model
Top-1
Params
MAdd
dler et al. 2018) is the previous state-of-the- model, which achieves the best trade-off between effectiveness and efficiency. Accord- ing to the results, our KANets significantly out- perform MobileNetV2 with 0.03 million fewer parameters. Specifically, our KANetxv and KANetoRY outperform MobileNetV2 by mar- gins of 0.9% and 0.8%, respectively. More im- portantly, our KANets has the least computa- tional cost. These results demonstrate the effee- tiveness and efficiency of our proposed KAOs.
VGG16
0.715
128m
15300m
AlexNet
0.572
60m
720m
SqueezeNet
0.575
1.3m
833m
MobileNetVI
0.706
4.2m
569m
ShuffleNet 1.5x
0.715
3.4m
292m
ChannelNet-vi MobileNetV2
0.705
3.7m
407m
0.720
3.47m
300m
KANet (ours)
0.729
3.44m
288m
KANeloKV (ours)
0.728
3.44m
281m
The performance of KANets indicates that our proposed methods are promising, since we only make small modifications to the architecture of MobileNetV2 include KAOs. Compared to modules with the regular convolutional layers only, our proposed modules with KAOs achieve better performance without using excessive computational resources. Thus, our methods can be used widely for designing compact deep models. Next, we show that our proposed KAOs are as effective as regular attention operators.
4.3 COMPARISON WITH REGULAR ATTENTION OPERATORS
We perform experiments to compare our pro- posed KAOs with regular attention operators. We consider the regular attention operator and the with pooling operation in (Wang et al. 2018). For the attention operator with pooling operation, the spatial sizes of the key matrix K and value matrix V are reduced by 2 2 pooling operations save computation cost. To com- pare these operators in fair settings, we replace all KAOs in KANets with regular attention op- erators and regular attention operators with pooling operation, denoted as AttnNet and At- tnNet+Pool, respectively.
Table Comparisons between KANets with regular attention operators (denoted as AttnNet), KANets with regular attention operators with pooling operation (denoted as AttnNet+Pool) and KANets with KAOs in terms of the top-1 accuracy the ImageNet validation set, the number of total parameters, and MAdd.
Model
Top-1
Params
MAdd
AttnNet
0.730
3.44m
365m
AttnNet+Pool
0.729
3.44m
300m
KANetgv
0.729
3.44m
288m
KANe
0.728
3.44m
281m
The comparison results are summarized in Table 3 Note that all these models have the same number of parameters. We can see that KANet and KANetakV achieve similar performance as AttnNet and PutneetPPoo with dramatic reductions of computational cost. The results indicate that our proposed KAOs are effective as regular attention operators while being much more efficient. In addition, our KAOs are better than regular attention operators that uses pooling operation to increase efficiency in (Wang al. 2018).
7

---

Under review as a conference paper at ICLR 2020
4.4 ABLATION STUDIES
To show how our KAOs benefit entire networks in different settings, we conduct ablation stud- ies on MobileNetV2 and KANetyy- For Mo- bileNetV2, we replace BaseModules with Attn- Modules as described in Section 3.2 resulting in new model denoted as MobileNetV2+KA9 On the contrary, based on KANetæv, all AtduSkipModules by BaseModules. The re- sulting model is denoted as KANet w/o KAO.
Table 4: Comparisons among KANetRV: MobileNetV2, MobileNetV2 with KAOS (MobileNaV2++KAO1v
and KANet without KAO (KANet w/o KAO) in terms of the top-1 accuracy on the ImageNet validation set, the number of total parameters, and MAdd.
replace
Model
Top-1
Params
MAdd
MobileNetV2 MobileNetV2+KAA
0.720
3,47m
300m
0.726
3.46m
298m
Table Ireports the comparison results. By em- ploying KAOxv, MobileNerV2+KAAO gains performance boost of 0.6% with fewer parame- ters than MobileNetV2. On the other hand, KANelxv outperforms KANet w/o KAO by margin of 0.8%, while KANet w/o KAO has more parameters than KANetxy. KANetxv achieves the best performance while costing the least computational resources. The results indicate that our proposed KAOs are effective and efficient, which is independent of specific network architectures.
KANetxv KANet w/o KAO
0.729
3.44m
288m
0.721
3.46m
298m
4.5 RESULTS IMAGE SEGMENTATION
In order to show the efficiency and effective- ness of our KAOs in broader application sce- narios, perform additional experiments image segmentation tasks using the PASCAL. 2012 dataset (Everingham al.) 2010). With the extra annotations provided by (Hariharan al. 2011), the augmented dataset contains 10,582 training, 1,449 validation, and 1,456 test- ing images. Each pixel of the images is labeled by one of 21 classes with 20 foreground classes and 1 background class. We re-implement the VV2 model (Chen et al.) 2018) our baseline. Following (Wang& Ji, 2018)) using attention operators the output layer, instead of atrous spatial pyramid pooling (ASPP), results a significant performance improvement. In experiments, we replace ASPP with the regular attention operator and proposed KAOs, respectively, and compare the results. For all attention operators, linear transformations are applied on Q, K, and V. Details of the experimental setups are provided in the appendix.
Table 5: Comparisons among DeepLabV2, DeepLabV2 with the regular attention operator (DeepLabV2+Attm)) DeepLabV2 with KAO (DeepLabV2+KAOku)) and DeepLabV2 with KAO (DeepLabV2+KA0ger) in terms of the pixel-wise accuracy, and mean IOU on the PAS- CAL VOC 2012 validation dataset.
Model
Accuracy Mean IOU
DeepLabV2
0.944
75.1
DeepLabV2+Attn
0.947
76.3
DeepLabV2+KAOkr
0.946
75.9
DeeplabV2+KA0gkt
0.946
75.8
Table 5 shows the evaluation results in terms of pixel accuracy and mean intersection over union (IoU) on the PASCAL VOC 2012 validation set. Clearly, models with attention operators outperform the baseline model with ASPP. Compared with the regular attention operator, KAOs result in similar pixel-wise accuracy but slightly lower mean IoU. From the pixel-wise accuracy, results indicate that KAOs are as effective the regular attention operator. The decrease in mean IoU may be caused by the strong structural assumption behind KAOs. Overall, the experimental results demonstrate the efficiency and effectiveness of our KAOs in broader application scenarios.
CONCLUSIONS
In this work, we propose Kronecker attention operators to address the practical challenge of applying attention operators on high-order data. We investigate the problem from a probabilistic perspective and use variiiev normal distributions with Kronecker covariance structure. Experimental results show that our KAOs reduce the amount of required computational resources by factor of and higher-order data. We employ KAOs to
hundreds, with larger factors for higher-dimensionn design family of efficient modules, leading to our KANets. KANets significantly outperform the previous ffate-oftthe-a compact models on image classification tasks, with fewer parameters and less computational cost.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Geoffrey Irving. Michael Isard, et al. Tensorflow: system for large-scale machine learning. In OSDI, volume 16, pp. 265-283, 2016.
Genevera Allen and Robert Tibshirani. Transposable regularized covariance models with an application to missing data imputation. The Annals of Applied Statistics, 4(2):764, 2010.
Dzmitry Bahdanau. Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. International Conference on Learning Representations, 2015.
Liang-Chieh Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L. Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE transactions pattern analysis and machine intelligence, 40(4):834-848, 2018.
J. Deng, W. Dong, R. Socher, L.,J. K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchi- cal Image Database. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009.
Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. International journal of computer vision, 88(2): 303-338, 2010.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Channelnets: Compact and efficient con- volutional neural networks via channel-wise convolutions. In Advances Neural Information Processing Systems, pp. 5203-5211, 2018.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 249-256, 2010.
Alexander Graham. Kronecker products and matrix calculus with applications. Courier Dover Publications, 2018.
Arjun K Gupta and Daya K Nagar. Matrix variate distributions. Chapman and Hall/CRC, 2018.
Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik. Semantic contours from inverse detectors. In Computer Vision (ICCV), 2011 IEEE International Conference on, pp. 991-998. IEEE, 2011.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Andrew 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: 1704.04844, 2017.
Zilong Huang, Xinggang Wang, Lichao Huang, Chang Huang, Yunchao Wei, and Wenyu Liu. Cenet: Criss-cross attention for semantic segmentation. arXiv preprint arXiv:1811.11721 2018.
Forrest N landola. Song Han, Matthew W Moskewicz, Khalid Ashraf, William J Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and; 0.5 mb model size. arXiv preprint arXiv: 1602.07360, 2016.
Sergey Toffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Internationaa Conference on Machine Learning, pp. 448-456, 2015.
Alfredo Kalaitzis, John Lafferty, Neil Lawrence, and Shuheng Zhou. The bigraphical lasso. In International Conference Machine Learning, pp. 1229-1237 2013.

---

Under review as a conference paper at ICLR 2020
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM Review, 51(3): 455-500, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 (:::)8222222224 1998.
Guanbin Li, Xiang He, Wei Zhang, Huiyou Chang, Le Dong, and Liang Lin. Non-locally enhanced encoder-decoder network for single image de-raining. In 2018 ACM Multimedia Conference on Multimedia Conference, pp. 1056-1064. ACM, 2018.
Tsung-Yi Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pp. 740-755. Springer, 2014.
Wei Liu, Andrew Rabinovich, and Alexander C Berg. Parsenet: Looking wider to see better. arXiv preprint arXiv: 050.04999 2015.
Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh. Hierarchical question-image co-attention for visual question answering. In Advances In Neural Information Processing Systems, pp. 289-297, 2016.
Mateusz Malinowski, Carl Doersch, Adam Santoro, and Peter Battaglia. Learning visual question answering by bootstrapping hard attention. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 3-20, 2018.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4510-4520. IEEE, 2018
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1): ((():1929-11988 2014.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. International conference on machine learning, pp. 1139-1147 2013.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint urXiv:1607.08033 2016.
Charles F Van Loan. The ubiquitous kronecker product. Journal of computational and applied mathematics, 123(1-2):85- 100, 2000.
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. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: /710. 10903, 2017.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. The IEEE Conference Computer Vision and Pattern Recognition (CVPR), volume 1, pp. 4, 2018.
Zhengyang Wang and Shuiwang Ji. Smoothed dilated convolutions for improved dense prediction. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 2486-2495. ACM, 2018.
Zhengyang Wang, Hao Yuan, and Shuiwang Spatial variational auto-encoding via matrix-variate normal distributions. arXiv preprint arXiv: 3XXv:17005.082.11 2017.
Kelvin Xu, Jimmy Ba. Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In International conference machine learning, pp. 2057, 2015.
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. arXiv preprint arXiv: 100700088, 2017.
10

---

Under review as a conference paper at ICLR 2020
Appendix
EXPERIMENTAL SETUP FOR IMAGE CLASSIFICATION
As a common practice on this dataset, we use the same data augmentation scheme in (He et al. 2016). Specifically, during training, we scale each image 256 x 256 and then randomly crop 224 x 224 patch. During inference, the center-cropped patches are used. We train our KANets using the same settings as MobileNetV2 (Sandler al., 2018) with minor changes. We perform batch normalization (loffe& & Szegedy 2015) on the coefficient matrices in KAOs to stabilize the training. trainable parameters are initialized with the Xavier initialization (Glorot Bengio 2010). We use the standard stochastic gradient descent optimizer with momentum of 0.9 (Sutskever et al. 2013) to train models for 150 epochs total. The initial learning rate 0. and it decays by 0.1 at the 80th, 105th, and 120th epoch. Dropout (Srivastava et al. 2014) with keep rate of 0.8 is applied after the global average pooling layer. We use TITAN Xp GPUs and a batch size of 512 for training, which takes about 1.5 days. Since labels of the test dataset not available, we train networks on training dataset and report accuracies on the validation dataset.
2 EXPERIMENTAL SETUP FOR IMAGE SEGMENTATION
We train all the models with randomly cropped patches of size 321 x 321 and batch size of 8.
Data augmentation by randomly scaling the inputs for training is employed. We adopt the "poly"
learning rate policy (Liu et al. 2015) with power = 0.9, and set the initial learning rate to 0.00025.
Following DeepLab LablabbV V2b we use the ResNet- model pre-trained on ImageNet (Deng et al. 2009) and MS-COCO (Lin et al. 2014) for initialization. The models are then trained for 25,000 iterations with a momentum of 0.9 and a weight decay of 0.0005. We perform no post-processing such as conditional random fields and do not use multi-scale inputs due to limited GPU memory. All the models are trained on the training set and evaluated on the validation set.
3 ILLUSTRATION OF KRONECKER ATTENTION MODULES
hx wk
bx
hx wxd
Coco 1x1 Stride -1 BN +Red
Coto 1x1 Stride
Comy 1 Stride -1 BN + LGG
Comw 1x
Striee
BN R16
BN Rel.16
KAO
KAO
DWCaar 3 Striee S BN +ULLU6
DW 3 Strde -5 BN + ReLU6
DWCare 3x
Stride =5
DO 3x3
BN ReLU6
Strde =5
Core 1 Stridh 11 Outpudd
Come 1x
Com' Stride =1 Outpad
Corr 1
Stricke =1
Stride =1 Oulpudd
Outpudd
1/
S/ W/
w/
h w
61)
(b)
(
(c)
Figure 3: Architectures of the BaseModule (a), BaseSSipMModul (b), AttnModule (c), and AttnSkip-
Module (d) as described in Section 3.22 The skip connections indicated by single dashed paths are not used when or # d. Those indicated by double dashed paths are not used when s 1.
4 THE KANETS ARCHITECTURE
Table 6 describes the detailed KANets architecture. We use KAOs in every AttSSkipMouul.. In KAOs, multi-head attention with 4 heads and concatenate results for output. The linear
11

---

Under review as a conference paper at ICLR 2020
Table 6: Details of the KANets architecture. Each line describes sequence of operators in the format of "input size / operator name expansion rate r number of output channels c number of operators in the sequence / stride s". "Conv2D" denotes the regular 2D convolutional layer. "AvgPool" and "FC" denote the global average pooling layer and the fully-connected layer, respectively. All depth-wise convolutions use the kernel size of x For multiple operators in a sequence denoted in the same line, all operators produce output channels. And the first operator applies the stride of while the following operators applies the stride of denotes the class number the task.
Input
Operator
2242x3
Conv2D 3 x
32
112'x32
BasuSkipModule
16
112
BaseSkipModule
24
2
56*x24
BaseSkipModule
32
2
28*x32
ModuueepModule
32
x82x32
BaseSkipMoodlee
64
14"x64
AttuSkipModule
64
3
14'x64
AttnSkipModule
96
3
14'x96
BaseSkipModule
160
72x160
AtnSkipMooulle
160
2
7xx160
AtnSkipModule
320
7*x320
Conv2l) 1
1280
12x1280
AvgPool FC
k
transformation is only performed the value matrix V limit the number of parameters and computational resources.
PROOF OF THEOREM
The fact that P and & diagonal implies independence in the of multivariate normal distribu- tions. Therefore, it follows from assumptions (a) and (b) that
Ω W
[ri, P2....... rn. MN hxw Mr. [m)]
h
where M, + [V, v ,.....))' = = Injeo and
[c1, Ca..,, cwl MN h
Mc. + @ I [m]]
(8)
where M. = T [1e,4 ........] = - 11 [m]]
Given assumption (c) and X r2, r2, ........ .n. +[c1, +[,,,C2, ..,, Cwrl we have
T ++Ω Ω
x MN fxx
M,
(9)
where M M, + M, = (n (u + +).
If h W. have
ur v) h (E
S4
(10)
12

---

Under review as a conference paper at ICLR 2020
and
V + 2
f + v
tr
@
h
1 7 22)
( 4) +
11
h
04 Σ Fzj) + h +
2 04 + Σ 1,)
2 tr (Ω 4)
(11)
This completes the proof of the theorem.
REFERENCES
All citations refer to the references in the main paper.
13


Reviews:
[{"review_id": "Syl2rxLq_H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose to reduce the memory and computation complexity of attention networks applied to 2D data (images) by using, in the attention operator, the mean over the rows and columns of images instead of its vectorized version.\nThe paper is relatively well written, based on intuitive ideas and including clear figures. Several experimental results are reported but, in my opinion, they are not convincing enough. \nBelow, a list of issues is presented:\n-\tI think the term “Kronecker” in the name of the model is not well justified or explained. I don’t see a Kronecker product of matrices in the attention operator. Maybe, only in the case of KAO_{QKV} the outer sum could be written as a Kronecker product of some matrices justifying the name. I think this is not a big issue but it is a little bit annoying to use a term that is not naturally introduced to the reader.\n-\tIn my opinion, the main issue is that taking the mean over columns and rows as the only information to construct the attention operator seems not able to capture all relevant information about the underlying dataset. I think there is not a theory that justifies this approach. For example, it could be possible that other linear or nonlinear combination of rows and columns provides better attention operators. \n-\tIt is not clear how the theoretical results (Theorem 1) helps to support the proposed method. Maybe the authors could better explain the implications of their theoretical results. I found the introduction of the method clear but rather disconnected from the theoretical sections 3.3-3.5.\n-\tExperimental results are not convincing. I cannot agree with the author’s claim that “KANets significantly outperform the previous state-of-the-art compact models”. Below I make comments to each of the presented experimental results.\no\tThe experimental results about memory and time used by regular attention operator compared with KAOs is obvious and not relevant because their theoretical complexities are well known.\no\tIn Table 2, it is shown that the proposed method is better than other non-attentional networks. I think this result is not relevant. On the other side, in Table 3, they compare the proposed method against two other attentional networks and show that the proposed method is not better than previous methods in terms of performance. The only advantage seems to be a slight reduction in number of operations which is marginal. \no\tIn the Ablation Studies (Table 4), the method is not compared with other classical attention network. They only compared against MobileNet. I wonder how the performance results would be if classical attention networks were used having the same level of number of parameters.\no\tThe results on Image Segmentation are not relevant because the proposed method is not the best one.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Syg9xOqCKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Akin to previous work introducing tensor regression layers to leverage the tensor/multimodal structure of inputs [Kossaifi et al., 2017], this paper proposes a Kronecker structured attention operator for self attention models acting on tensor data. The proposed operators enforce various constraints on the query key and value matrices of the attention module, where some (or all) of these matrices are obtained as horizontal and lateral averages of the query matrix; in this context, the query matrix is actually the flattening of a 3rd order tensor, whose slices are referred to as \"feature maps\". A theoretical analysis investigates the properties of imposing a Kronecker structured covariance matrix on the feature maps. The main theorem provides a way to efficiently construct feature maps satisfying this covariance structure. Experiments on image classification and segmentation are given where the proposed approach shows competitive performances while maintaining a number of parameters on par with efficient architectures such as neural nets.\n\nI find this paper difficult to follow. In particular, I find it difficult to see the relevance of the theoretical analysis part. I think I got it in the end, but I believe the analysis could be better motivated/presented and the consequences of Theorem 1 on design choices or implementation could be clarified. Similarly, the description of the architecture in Sections 3.1 and 3.2 is sometimes given without much motivation, letting the reader wonder there are particular reasons for the choices made on the architecture. I acknowledge that this may be because I am not very familiar with attention networks (but I am familiar with the literature on tensorization of neural networks).\n\nI am not very confident in my assessment but I have the feeling that the paper could be greatly improved by some restructuring and giving more insights and motivations.\n\nI have a few questions and comments:\n- end of section 2.1: what is the purpose of the seperate linear transformation on each input matrix?\n- after Eq. (3) I don't think the notation [cross in diamond] has been introduced.\n- the reference (Gupta & Nagar 2018) does not seem appropriate (I don't believe the notion of vectorization requires a reference)\n- Some relevant literature may be missing, e.g.,\n[A Tensorized Transformer for Language Modeling]\n[Tensorized Self-Attention: Efficiently Modeling Pairwise and Global Dependencies Together]\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgW4ZBRYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "=== Summary ===\nThe authors propose the Kronecker Attention Operator (KAO), a novel efficient attention mechanism for high order data such as images (height H and width W dimensions). Regular self-attention on images produce HW queries attend to HW keys and their values, resulting in quadratic time/space complexity O((HW)^2).\nIn contrast, KAO applies self-attention after averaging keys, values (and potentially queries) along width or height dimension, resulting in (H+W) keys and values and thus achieving linear time/space complexity in O(HW).\nThe authors analyze their approach from a probabilistic perspective by assuming that the rows and columns follow matrix-variate normal distributions with Kronecker covariance.\nExperimental results on ImageNet classification and PASCAL segmentation show that adding Kronecker Attention Operators to baseline architectures yields improvements with a negligible increase in parameters/computations.\n\n\n\n=== Recommendation ===\nAttention has been shown to provide improvements over convolutions but can indeed incur significant memory costs. Hence, discovering efficient attention mechanisms in an important research direction with practical impact. \nThe proposed method is sound and simple and may achieve significant speedups over regular self-attention.\n\nHowever, there are many experimental presentation/evaluation issues in the draft:\n- An important assumption of the method is that Kronecker factorization preserves structure well while reducing computations. Previous works reduce memory costs by pooling the input to the attention operator (and resizing accordingly the output). A natural baseline would be to pool in such a way that the number of queries is the same as when applying Kronecker factorization. Can the authors report results on such a baseline?\n- Section 4.1 and Table 1 present computational efficiency (memory and latency) in simulated cases. Can the authors additionally report results for the gains obtained on the entire architectures? The rest of the architecture isn't an external factor to ignore.\n- Can the authors also report memory consumption and latency time of KANet vs MobileNetv2?\n- The authors ignore a vast literature on (self-)attention mechanisms used in vision, some of which are relatively cheap. These methods should also be cited as related work and potentially use as baselines (Squeeze-and-Excitation for example).\n\nThe probabilistic analysis does not convincingly motivate the Kronecker Attention Operator. Notably, the assumptions for Theorem 1 are also quite unrealistic for images (nearby pixels are correlated via locality, so rows and columns aren't independent). Can the authors clarify the assumptions and explain why they're reasonable?\n\nIn conclusion, the authors only compare their approach against regular self-attention and do not refer to relevant work on attention mechanisms for vision. They do not provide memory/consumption gains on actual architectures, which makes it hard to evaluate the significance of the work. The theoretical motivation for the method is not convincing. I argue for rejection. \n\n=== Additional questions/comments ===\n- Section 2.1: Self-attention is better described as Q = W^Q X, K = W^K X, V = W^V X, O = V softmax(K^TQ). As opposed to Q=K=V, O = W^V V softmax((W^KK)^TW^QQ)\n- Since the base architecture KANet is MobileNetv2, there is no need to include VGG, AlexNet, SqueezeNet, in Table 2.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission has been assessed by three reviewers who scored it as 3/3/3. The main criticism includes lack of motivation for sections 3.1 and 3.2, comparisons to mere regular self-attention without encompassing more works on this topic, a connection between Theorem 1 and the rest of the paper seems missing. Finally, there exists a strong resemblance to another submission by the same authors which is also raises the questions about potentially a dual submission. Even excluding the last argument, lack of responses to reviewers does not help this case. Thus, this paper cannot be accepted by ICLR2020.
Decision: Reject