Unveiling the Hidden Structure of Self-Attention via Kernel Principal Component Analysis

Q1. My main concern is about the practicality of the novel RPC-Attention mechanism. In your experiments, RPC-SymViT can only scale to a small size, and it does not show a significant performance advantage compared to ViT-Small.

I am also concerned about the scalability of this model, which can outperform ViT by ~1% on ImageNet at the tiny size, but the performance becomes very close at the small size. What happens if the model is scaled up even more? Do the assumptions in the paper still hold when the feature dimension is higher?

Did the authors try larger models for RPC-Attention?

Answer: We have conducted an additional experiment on RPC-SymViT-Base for the ImageNet object classification task to address the reviewer's concern about the scalability and practicality of our RPC-Attention and reported our results in Table 1 and 2 in the attached PDF. Our RPC-SymViT-Base outperforms the baseline in terms of clean accuracy and is also more robust to data perturbation and adversarial attacks than the baseline. Specifically, we improve on ImageNet-O by over 2 AUPR and on PGD and FGSM by more than 1% in top-1 accuracy. These results further demonstrate the effectiveness of RPC-Attention even in larger models.

Our assumptions in Remark 2, do not hold when the feature dimension is higher than the sequence length as the number of principal components cannot exceed the rank of the covariance matrix. But in practical tasks, the feature dimension is very often smaller than the sequence length since, in those tasks, transformers are used to capture long-range dependency in the input sequence.

Q2. Additionally, RPC-SymViT does not have an advantage in computational speed; for example, in Table 11, the inference time for RPC-SymViT (2iter/layer) is 70% higher than that of ViT. As it stands, the authors have not convinced me to abandon the traditional ViT in favor of RPC-SymViT.

Answer: In Table 11, in our first three settings, RPC-SymViT (4iter/layer1, 5iter/layer1, 6iter/layer1), we only apply RPC-Attention to the first layer of the transformer model. This adds minimal cost to the inference speed. In particular, in Table 11, we show the inference runtime cost (in second/sample) of our RPC-Attention. As can be seen in that table, during inference ("Test" column in Table 11), our RPC-Attention with 4iter/layer1 (4 Principal Attention Pursuit (PAP) iterations at layer 1) and 5iter/layer1 (5 PAP iterations at layer 1) have the same inference runtime as the baseline SymViT, 0.01 second/sample. Our RPC-Attention with 6 iter/layer1 (6 PAP iterations at layer 1) only requires slighly more inference time than the baseline, 0.011 second/sample vs. 0.01 second/sample. Due to the effectiveness of our RPC-Attention, applying it at the first layer of a transformer model is already good enough to improve the model's robustness significantly (see Tables 1, 2, and 3 in our main text and Tables 4, 5, 6, 7, 8, 9, 10, and 12 in our Appendix). Note that results reported in Table 11 also show that our RPC-Attention is as memory, parameter, FLOP, and training efficient as the baseline SymViT.

While applying RPC at all layers, as in RPC-SymViT (2iter/layer), leverages more advantages of RPC, it is not really necessary in most settings due to its small improvement over applying RPC at the first layer and its higher computational overhead, as the reviewer mentioned.

We would like to thank the reviewer again for your thoughtful reviews and valuable feedback.

We would appreciate it if you could let us know if our responses have addressed your concerns and whether you still have any other questions about our rebuttal.

We would be happy to do any follow-up discussion or address any additional comments.

Dear Reviewer rAS8,

We sincerely appreciate the time you have taken to provide feedback on our work, which has helped us greatly improve its clarity, among other attributes. This is a gentle reminder that the Author-Reviewer Discussion period ends in less than two days from this comment, i.e., 11:59 pm AoE on August 13th. We are happy to answer any further questions you may have before then, but we will be unable to respond after that time.

If you agree that our responses to your reviews have addressed the concerns you listed, we kindly ask that you consider whether raising your score would more accurately reflect your updated evaluation of our paper. Thank you again for your time and thoughtful comments!

Sincerely,

Authors

Thanks for your reply. We respectfully disagree with the reviewer that scalability is a concern about our work. Please allow us to explain why scalability is not an issue below.

In practice and also in our experiments, transformers use multihead attention with $H$ heads. The feature dimension mentioned in our assumptions in Remark 2 is the feature dimension at each head, which is $D/H$, where $D=768$ and $H=12$ in ViT-Base. Thus, in this case, the feature dimension ($768/12=64$) is smaller than the sequence length ($197$). For ViT-Base, our RPC-Attention model works with sequences longer than $64$. Furthermore, we can always reduce this number ($64$) by introducing more heads, but tasks with sequence lengths less than $64$ are not very practical. The same holds for ViT-Tiny, which has $D=192$ and $H=3$. As a result, we believe our statement that "in practical tasks, the feature dimension is very often smaller than the sequence length" is correct, and our assumptions in Remark 2 are still valid and should not raise any concern about the scalability of our RPC-Attention. Below, we provide a table that contains the feature dimensions, the number of heads, and the number of feature dimensions per head of each ViT model.

Q1. The RPC-Attention uses an iterative algorithm PAP to solve the convex formulation of principal component pursuit. How is back-propagation via PAP algorithm calculated? Does it lead to any instability?

Answer: As shown in Algorithm 1 in the main text, the Principal Attention Pursuit (PAP) in our RPC-Attention is quite simple. Most operators in PAP are linear except for the softmax operator and the shrinkage operator $S_{\lambda/\mu}$. Like the softmax operator in self-attention, the softmax operator in RPC-Attention is easy to differentiate through. Similarly, like the ReLU operator in feedforward layers, the shrinkage operator $S_{\lambda/\mu}$ is also easy to differentiate through. We do not encounter any instabilities with RPC-Attention, and the standard backpropagation algorithm is used to handle gradient propagation in RPC-Attention. As can be seen in Figure 1 (Right) in the attached PDF, the training and validation loss curve of the transformer with RPC attention is quite stable.

Q2. The appendix E8 shows the runtime and memory of RPC-Attention is comparable to baseline despite using an iterative algorithm. I am curious about why it is not much slower. Is there any analysis?

Answer: Since we only apply RPC-Attention to the first layer of the transformer model, it adds minimal cost to the runtime and memory. In particular, in Table 11 in our Appendix, we show the inference runtime cost (in second/sample) of our RPC-Attention. As can be seen in that table, during inference ("Test" column in Table 11), our RPC-Attentions with 4iter/layer1 (4 Principal Attention Pursuit (PAP) iterations at layer 1) and 5iter/layer1 (5 PAP iterations at layer 1) have the same inference runtime and use the memory during inference as the baseline SymViT, 0.01 second/sample and 1181MB, respectively. Our RPC-Attention with 6 iter/layer1 (6 PAP iterations at layer 1) only requires slighly more inference time than the baseline, 0.011 second/sample vs. 0.01 second/sample, and uses the same memory during inference as the baseline, 1181MB. Due to the effectiveness of our RPC-Attention, applying it at the first layer of a transformer model is already good enough to improve the model's robustness significantly (see Tables 1, 2, and 3 in our main text and Tables 4, 5, 6, 7, 8, 9, and 10 in our Appendix). Note that results reported in Table 11 also show that our RPC-Attention is as parameter, FLOP, and training efficient as the baseline SymViT.

Q3. I noticed that the baseline SymViT that uses symmetric attention has significantly worse accuracy compared to vanilla ViT on clean ImageNet (for the tiny model, SymViT accuracy is 70.44, while vanilla ViT is around 75). I am wondering what would be the reason. If this is caused by the use of symmetric attention, is there a way to adopt RPC-Attention for vanilla ViT?

Answer: Thanks for your comments. For the ImageNet object classification task, as the reviewer pointed out and as reported in our paper (see Tables 1 and 12), SymViT has worse performance than the asymmetric vanilla ViT. However, for other tasks, such as neural machine translation (NMT) [Vaswani, 2017] and sequence prediction (SP) [Dai et al., 2019], symmetric attention has comparable or even better performance than asymmetric attention, as reported in [Tsai, 2019]. These evidences show the promise of applying our RPC-Attention to practical models for enhancing their accuracy and robustness.

In Appendix E.9, we discuss the extension of RPC-Attention to asymmetric attention. We report the results of the RPC-Asymmetric ViT (RPC-AsymViT) vs. baseline asymmetric ViT in Table 12. Our RPC-AsymVit improves over the baseline on most of the corrupted datasets. However, as explained in Appendix E.9, as the PAP in Algorithm 1 in our manuscript is not designed for multiple data matrices, it is not as effective in the asymmetric case as in the symmetric case.

Additionally, in Table 4 of the attached PDF, we provide positive results of finetuning an asymmetric Sparse Mixture of Experts (SMoE) language model using RPC on the downstream natural language understanding tasks, Stanford Sentiment Treebank v2 (SST2) and IMDB Sentiment Analysis (IMDB). The significant improvements over the baseline SMoE validate the effectiveness of both of our methods, symmetric RPC-Attention and asymmetric RPC-Attention.

Q4. Given that RPC-Attention is more robust and as efficient as baseline, why the majority of experiments only apply it on the first few layers or the first layer, but not apply RPC-Attention on all layers (for example, like 6iter/all-layer).

Answer: As mentioned in our answer to your Q2 above, due to the effectiveness of our RPC-Attention, applying it at the first layer of a transformer model is already good enough to improve the model's robustness significantly (see Tables 1, 2, and 3 in our main text and Tables 4, 5, 6, 7, 8, 9, and 10 in our Appendix). This strategy also adds minimal cost to the runtime and memory.

While applying RPC at all layers, as in RPC-SymViT (2iter/all-layer) in Table 1, 2, 4, and 6 leverages more advantages of RPC, it is not really necessary in most settings due to its small improvement over applying RPC at the first layer and its higher computational overhead (see Table 11).

References

Vaswani, A., et al. Attention is all you need. 2017.

Dai, Z., et al. Transformer-xl: Attentive language models beyond a fixed-length context. 2019.

Tsai, Y. H. H., et al. Transformer dissection: a unified understanding of transformer's attention via the lens of kernel. 2019.

We would like to thank the reviewer again for your thoughtful reviews and valuable feedback.

Regarding applying RPC for more iterations at all layers, as we mentioned, this results in higher computational overhead and may only lead to small improvements. We conducted an additional experiment with 4 iterations in all layers (RPC-SymViT (4iter/all-layer)) and provide the results in Table 1 and 2 below. We observe that RPC-SymViT (4iter/all-layer) indeed does outperform RPC-SymViT (2iter/all-layer) on almost all robustness benchmarks but still does not perform as well as RPC-SymViT(5/6iter/layer1). Interestingly, while RPC-SymViT (4iter/all-layer) performs significantly better than the baseline and RPC-SymViT(4/5/6iter/layer1) on PGD and FGSM attacked ImageNet-1K, RPC-SymViT (2iter/all-layer) still has the best accuracy.

Table 1: Top-1, top-5 accuracy (%) , mean corruption error (mCE), and area under the precision-recall curve (AUPR) of RPC-SymViT and SymViT on clean ImageNet-1K data and popular standard robustness benchmarks for image classification. RPC-SymViT ($n$iter/layer1) applies $n$ PAP iterations only at the first layer. RPC-SymViT ($n$iter/all-layer) applies $n$ PAP iterations at all layers.

Table 2: Top-1, top-5 accuracy (%) on PGD and FGSM attacked ImageNet-1K validation data with the highest perturbation. RPC-SymViT ($n$iter/layer1) applies $n$ PAP iterations only at the first layer. RPC-SymViT ($n$iter/all-layer) applies $n$ PAP iterations at all layers.

We would appreciate it if you could let us know if our responses have addressed your concerns and whether you still have any other questions about our rebuttal.

We would be happy to do any follow-up discussion or address any additional comments.

Dear Reviewer 85Cd,

We sincerely appreciate the time you have taken to provide feedback on our work, which has helped us greatly improve its clarity, among other attributes. This is a gentle reminder that the Author-Reviewer Discussion period ends in less than two days from this comment, i.e., 11:59 pm AoE on August 13th. We are happy to answer any further questions you may have before then, but we will be unable to respond after that time.

If you agree that our responses to your reviews have addressed the concerns you listed, we kindly ask that you consider whether raising your confidence score (3 currently) would more accurately reflect your updated evaluation of our paper. Thank you again for your time and thoughtful comments!

Sincerely,

Authors

Q1. [minor] The experiments use relatively small-scale models and short training runs (e.g. 50 epochs on Imagenet). While not a core issue given the objective of the paper, it would be nice to see results in more standardized settings (e.g. ViT-Base with 300 epochs)

Answer: Thanks for your suggestion. All of our models are trained on 300 epochs, we provide the plot of 50 epochs in the main text for emphasis on the faster initial convergence during training. A plot of the full training curve with 300 epochs is provided in Appendix E.1, Fig. 4. Following the reviewer's suggestion, we have conducted an additional experiment on ViT-Base for the ImageNet object classification task with 300 epochs and reported our results in Table 1 and 2 in the attached PDF. Our RPC-ViT-Base outperforms the baseline in terms of clean accuracy and is also more robust to data perturbation and adversarial attacks.

Q2. Given the new perspective provided in the paper, do the authors have any insights into how to reduce the complexity of self-attention while retaining the same quality?

Answer: Our kernel principal component analysis (kernel PCA) framework allows the development of efficient attentions. In the following, we will show how to derive two popular efficient attentions: the linear attention in [Katharopoulos, 2020] and the sparse attention in [Child, 2019]. Combining linear and sparse attentions helps reduce the complexity of self-attention while maintaining its quality [Nguyen, 2021; Zhu, 2021; Chen, 2021].

Deriving the linear attention: The self-attention output in Eqn. (8) in our main text can be re-written as follows:

$$h_{i} = \sum_{j=1}^{N}\frac{\phi(q_i)^{\top}\phi(k_j)}{g(q_i)}v_j = \frac{\sum_{j=1}^{N}\phi(q_i)^{\top}\phi(k_j)v_j}{\sum_{j'=1}^{N}\phi(q_i)^{\top}\phi(k_{j'})}.$$

Here, we again choose $g(x) := \sum_{j=1}^{N}\phi(x)^{\top}\phi(k_j)$. Following the derivation in [Katharopoulos, 2020], we use the associative property of matrix multiplication to obtain

$$h_{i} = \frac{\phi(q_i)^{\top}\sum_{j=1}^{N}\phi(k_j)v_{j}^{\top}}{\phi(q_i)^{\top}\sum_{j'=1}^{N}\phi(k_{j'})}.$$

We can then choose $\phi(x) = \text{elu}(x) + 1$ to achieve the linear attention in [Katharopoulos, 2020], which is one of the most popular efficient attentions.

Deriving the sparse attention: For each query $q_i$, we consider a subset $\mathcal{M_{i}}=\\{k_{\ell_{i}(1)}, k_{\ell_{i}(2)},\dots, k_{\ell_{i}(L)}\\}$ of the dataset $\mathcal{M}=\\{k_1, k_2, \dots, k_N\\}$, where $\mathcal{L_{i}} = \\{\ell_{i}(1), \ell_{i}(2), \dots, \ell_{i}(L)\\} \subset \\{1, 2, \dots, N\\}$. Following Eqn. (8) and (9) in our main text, the projection $h_i$ of the query $q_i$ onto $D_v$ principal components of $\mathcal{M_i}$ is given by:

$$h_{i} = \sum_{j=1}^{N}1_{\mathcal{L_{i}}}(j)\frac{k(q_i, k_j)}{g(q_i)}v_j,$$

where $1_{\mathcal{L_{i}}}(j) = 1 \text{ if } j\in \mathcal{L_{i}}$. Note that the subsets $\mathcal{M_i}$ are different for different $q_i$, $i=1,\dots,N$. Again, as in Section 2.1 in our manuscript, selecting $g(x) := \sum_{j=1}^{N} k(x,k_j)$ and $k(x, y) = \exp(x^{\top}y/\sqrt{D})$, we obtain a formula of the sparse attention in [Child, 2019] where the binary matrix $(1_{\mathcal{L_{i}}}(j))_{i,j=1}^{N}$ becomes the sparse masking matrix.

References

Katharopoulos, A, et al. Transformers are rnns: Fast autoregressive transformers with linear attention. 2020.

Child, R., et al. Generating long sequences with sparse transformers. 2019.

Nguyen, T., et al. Fmmformer: Efficient and flexible transformer via decomposed near-field and far-field attention. 2021.

Zhu, C., et al. Long-short transformer: Efficient transformers for language and vision. 2021.

Chen, B., et al. Scatterbrain: Unifying sparse and low-rank attention. 2021.

We would like to thank the reviewer again for your thoughtful reviews and valuable feedback.

We would appreciate it if you could let us know if our responses have addressed your concerns and whether you still have any other questions about our rebuttal.

We would be happy to do any follow-up discussion or address any additional comments.

Dear Reviewer hhSg,

We sincerely appreciate the time you have taken to provide feedback on our work, which has helped us greatly improve its clarity, among other attributes. This is a gentle reminder that the Author-Reviewer Discussion period ends in less than two days from this comment, i.e., 11:59 pm AoE on August 13th. We are happy to answer any further questions you may have before then, but we will be unable to respond after that time.

If you agree that our responses to your reviews have addressed the concerns you listed, we kindly ask that you consider whether raising your confidence score (2 currently) would more accurately reflect your updated evaluation of our paper. Thank you again for your time and thoughtful comments!

Sincerely,

Authors

Q1. The results in Table 1 show that the best performance on different tasks is achieved with varying settings. For example, RPC achieves the best performance with 6 iterations/layer 1 on IN-1K, while RPC achieves the best performance with 2 iterations/all layers on IN-A. Moreover, for IN-1K top-5, 2 iterations/all layers even performs worse than the baseline attention. This suggests that more RPC attention is not always better for different tasks, and sometimes even performs worse than the baseline. Can authors provide an explanation for this phenomenon?

Answer: Our RPC-Attention needs more iterations to converge. While applying RPC to all layers leverages more advantages of RPC, 2 iterations/layer is too little for convergence. Also, for 4-5-6 iter/layer1, more iterations tend to give better results since the algorithm converges better. However, sometimes 6 iters perform worse than 5 iters. This might be due to overshooting.

Q2. As shown in Appendix Table 11, the computational cost of RPC attention increases substantially with the number of iterations/layers. This raises concerns about its practical applicability when extended to multi-layer settings. Specifically, it is unclear whether the performance gains will be sufficient to justify the increased computational cost. This directly affects the method's usability in applications.

Answer: Since we only apply RPC-Attention to the first layer of the transformer model, it adds minimal cost to the inference speed. In particular, in Table 11 in our Appendix, we show the inference runtime cost (in second/sample) of our RPC-Attention. As can be seen in that table, during inference ("Test" column in Table 11), our RPC-Attentions with 4iter/layer1 (4 Principal Attention Pursuit (PAP) iterations at layer 1) and 5iter/layer1 (5 PAP iterations at layer 1) have the same inference runtime as the baseline SymViT, 0.01 second/sample. Our RPC-Attention with 6 iter/layer1 (6 PAP iterations at layer 1) only requires slighly more inference time than the baseline, 0.011 second/sample vs. 0.01 second/sample, which is not a "major deficiency" as the reviewer suggested. Due to the effectiveness of our RPC-Attention, applying it at the first layer of a transformer model is already good enough to improve the model's robustness significantly (see Tables 1, 2, and 3 in our main text and Tables 4, 5, 6, 7, 8, 9, 10, and 12 in our Appendix). Note that results reported in Table 11 also show that our RPC-Attention is as memory, parameter, FLOP, and training efficient as the baseline SymViT.

Q3. For language tasks, ppl may not accurately reflect the final performance. Have the authors conducted experiments on other downstream natural language understanding tasks to evaluate the effectiveness? Will RPA be applicable to pre-trained language models?

Answer: Thanks for your suggestion. We have conducted additional experiments on downstream natural language understanding tasks and their results can be found in Table 4 of the attached PDF. RPC-models outperform the baseline models significantly on these tasks. Particularly, we use 2 baseline Sparse Mixture of Experts (SMoE) models, one with symmetric attention (SymSMoE) and one with asymmetric attention (SMoE), pretrained on WikiText-103 without RPC. We finetune these models on the Stanford Sentiment Treebank v2 (SST2) task and IMDB Sentiment Analysis (IMDB) task, without RPC as our baseline and with RPC for comparison. Due to the tight schedule, we did not report SymSMoE's results on IMDB and will do so during the discussion period. We further aim to test our method on more downstream tasks and will continue updating the results in the mean time. From the current results presented, we observe strong advantages of RPC on downstream tasks with large increases in training and validation accuracies.

We would like to thank the reviewer again for your thoughtful reviews and valuable feedback.

We would appreciate it if you could let us know if our responses have addressed your concerns and whether you still have any other questions about our rebuttal.

We would be happy to do any follow-up discussion or address any additional comments.

Dear Reviewer 8tie,

We sincerely appreciate the time you have taken to provide feedback on our work, which has helped us greatly improve its clarity, among other attributes. This is a gentle reminder that the Author-Reviewer Discussion period ends in less than two days from this comment, i.e., 11:59 pm AoE on August 13th. We are happy to answer any further questions you may have before then, but we will be unable to respond after that time.

If you agree that our responses to your reviews have addressed the concerns you listed, we kindly ask that you consider whether raising your score would more accurately reflect your updated evaluation of our paper. Thank you again for your time and thoughtful comments!

Sincerely,

Authors

To further address your concerns, we have conducted an additional experiment on another downstream natural language understanding task in addition to those in Table 4 in the attached PDF. We use a pre-trained transformer language model from the NAACL 2019 tutorial on "Transfer Learning in Natural Language Processing" and finetune the model on the 5-class sentiment classification task, Stanford Sentiment Treebank (SST-5). We implement RPC-Attention during finetuning only (RPC-LM) and compare the results with the baseline model (Baseline-LM) on SST-5 in Table 1 below. As can be seen from the table, our RPC-Attention is applicable to pre-trained language models and performs significantly better than the baseline. Hence, RPC-Attention is highly effective in downstream natural language understanding tasks.

Table 1: Validation and test accuracy of RPC-Attention implemented in a pre-trained transformer language model during finetuning versus the baseline transformer language model. We finetune both models on the 5-class Stanford Sentiment Treebank (SST-5) task.

We are happy to answer any further questions you may have. If you agree that our responses to your reviews have addressed the concerns you listed, we kindly ask that you consider whether raising your score would more accurately reflect your updated evaluation of our paper. Thank you again for your time and thoughtful comments!

Q1. Related works. The manuscript omits several relevant works such as those below

[1] Is Attention Better Than Matrix Decomposition?

[2] Graph Neural Networks Inspired by Classical Iterative Algorithms

[3] OptNet: Differentiable Optimization as a Layer in Neural Networks

[4] Deep Equilibrium Models

Answer: Thanks for your suggestion. We agree with the reviewer that [1], [2], [3], and [4] should be discussed in the Related Work section.

Hamburger in [1] models the global context discovery as the low-rank recovery of the input tensor and solves it via matrix decomposition. Both Hamburger and our Attention with Robust Principal Components (RPC-Attention) try to recover clean signal subspaces via computing a low-rank approximation of a given matrix. The key differences between our RPC-Attention and Hamburger are: (1) Our RPC-Attention finds a low-rank approximation of the key matrix $K$ while Hamburger finds a low-rank approximation of the input matrix $X$, and (2) Our RPC-Attention models the corruption by a sparse matrix while Hamburger does not enforce this condition. The entries of this sparse corruption can have an arbitrarily large magnitude and help model grossly corrupted observations in which only a portion of the observation vector is contaminated by gross error. Numerous critical applications exist where the data being examined can be naturally represented as a combination of a low-rank matrix and a sparse contribution, such as video surveillance, face recognition, and collaborative filtering [Candes, 2009].

[2] derives each component in a Graph Neural Network (GNN) from the unfolded iterations of robust descent algorithms applied to minimizing a principled graph regularized energy function. In particular, propagation layers and nonlinear activations implement proximal gradient updates, and graph attention results from iterative reweighted least squares (IRLS). While this is an interesting approach, it has not been extended to explaining the architecture of transformers, including self-attention, yet. Even though graph attention in GNNs and self-attention in transformers share many similarities, they are not the same. For example, query, key, and value matrices are introduced in the transformer's self-attention but not GNN's graph attention. In contrast, our kernel principal component analysis (kernel PCA) allows us to derive self-attention in transformers, showing that the attention outputs are projections of the query vectors onto the principal components axes of the key matrix $K$ in a feature space.

[3] and [4] implement each layer as an optimization and fixed-point solver, respectively. In particular, an OptNet layer in [3] solves a quadratic program, and a Deep Equilibrium layer in [4] computes the fixed point of a nonlinear transformation. Different from these layers, our RPC attention solves a Principal Component Pursuit - a convex program. Also, both OptNet layer in [3] and Deep Equilibrium layer in [4] do not shed light on the derivation and formulation of self-attention, which our kernel PCA framework does.

Also, we would like to point out that our RPC-attention aims at improving the robustness of self-attention mechanism to data contamination (See Tables 1, 2, and 3 in our main text and Tables 4, 5, 6, 7, 8, 9, 10, and 12 in our Appendix). None of the methods proposed in [1], [2], [3], and [4] addresses the model's robustness, neither theoretically nor empirically.

Following the reviewer's suggestion, we will include the discussion above in the Related Work section of our revision.

Q2. Speed. RPC-Attention adds cost to the inference speed.

Answer: Please see our answer to Q1 in the Global Rebuttal.

Q3. Gradient Flow: How does RPC-Attention handle gradient propagation through the layer? Does it utilize implicit differentiation [3,4], inexact gradient methods [1], or Backpropagation Through Time (BPTT)? Are there any instabilities when differentiating through the softmax operator?

Answer: As shown in Algorithm 1, the Principal Attention Pursuit (PAP) in our RPC-Attention is quite simple. Most operators in PAP are linear except for the softmax operator and the shrinkage operator $S_{\lambda/\mu}$. Like the softmax operator in self-attention, the softmax operator in RPC-Attention is easy to differentiate through. Similarly, like the ReLU operator in feedforward layers, the shrinkage operator $S_{\lambda/\mu}$ is also easy to differentiate through. We do not encounter any instabilities with RPC-Attention, and the standard backpropagation algorithm is used to handle gradient propagation in RPC-Attention. Fig. 1 (Right) in the attached PDF in Global Rebuttal shows that training/validation loss curve of the transformer with RPC attention is quite stable.

Q4. Convergence: RPC-Attention layer's convergence in the forward pass when using 4 or 6 iters? What if training the layer using 4 iters and performing inference with 6 iters? Would improved convergence at test time enhance the results?

Answer: In Figure 1 (Left) in the attached PDF, we plot the objective loss given in Eqn. (14) in the main text of our manuscript versus the number of PAP iterations in RPC-Attention (see Algorithm 1 in our manuscript) for models that use 4 and 6 PAP iterations. In Table 3 in the attached PDF, we report the results of using 6 iterations at inference on a model trained with 4 iterations.

Q5. Further exploration of RPC-Attention applied to graph data.

Answer: Thanks for your suggestion. We agree with the reviewer that given the connection between the attention mechanism and GNNs, as pointed out in [Joshi, 2020], our RPC-Attention can be extended to apply to GNNs. For example, RPC-Attention can be incorporated into the graph attention of Graph Attention Networks [Veličković, 2018].

References

Candès, E. J., et al. Robust principal component analysis? 2011.

Veličković, P, et al. Graph Attention Networks. 2018

We would like to thank the reviewer again for your thoughtful reviews and valuable feedback.

Regarding your suggestion on further exploration of RPC-Attention applied to graph data, we have implemented RPC-Attention in a GAT model to replace Edge Attention. We train the baseline GAT model and RPC-GAT on the Cora dataset with the same settings as in [Veličković, 2017] for 10 seeds and report the average, best validation accuracy, as well as their standard deviation, in Table 1 below. Our RPC-GAT outperforms baseline GAT by 0.76%.

Table 1: RPC-GAT vs. GAT on the Cora dataset.

We would appreciate it if you could let us know if our responses have addressed your concerns and whether you still have any other questions about our rebuttal.

We would be happy to do any follow-up discussion or address any additional comments.

References

Veličković, Petar, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. "Graph attention networks." arXiv preprint arXiv:1710.10903 (2017).

The demonstration of robustness gain from RPC-Attention is sound, considering RPCA is designed for arbitrarily large sparse corruptions.

I have raised my score to 5.

Dear Reviewer 9vVz,

We sincerely appreciate the time you have taken to provide feedback on our work, which has helped us greatly improve its clarity, among other attributes. This is a gentle reminder that the Author-Reviewer Discussion period ends in less than two days from this comment, i.e., (11:59 pm AoE on August 13th). We are happy to answer any further questions you may have before then, but we will be unable to respond after that time.

If you agree that our responses to your reviews have addressed the concerns you listed, we kindly ask that you consider whether raising your score would more accurately reflect your updated evaluation of our paper. Thank you again for your time and thoughtful comments!

Sincerely,

Authors