Unveil Benign Overfitting for Transformer in Vision: Training Dynamics, Convergence, and Generalization

Thanks for your constructive feedback! We address your questions and concerns as follows.

Q1. The sparsity assumption is too strong, as it relies on the signal being contained within one patch and the noise being contained within another, which may not align with real-world data distributions.

A1. The data generation model in this paper follows the common assumptions made in previous studies of benign overfitting ( Cao et al. (2022) [1], Kou et al. (2023) [2]). This assumption is not so strong for recent studies on benign overfitting, especially when we investigate on more complex ViT models. As Reviewer UpG9 says, "To the best of my knowledge, this is the first work to successfully address the learning dynamics of even a simple transformer architecture without unrealistic assumptions".

We also acknowledge that the data generation model may not align perfectly with real-world data distributions. In our perspective, the signals in the data model simulate the targets within an image, while the noises simulate the background in the image. We perform some experiments on MNIST dataset to verify our theoretical results (see next question), and we will try to make our theoretical results helpful for more practical applications.

Q2. The authors are suggested to explore scenarios that deviate from these assumptions to understand the limitations of the theoretical results. For example, more signal patches and more noise patches are contained in all patches. Tests on real-world tasks are better.

A2. We perform some experiments on MNIST dataset. In these experiments, we used different dataset, different noise, and different network model than in this paper. So the results regarding N and SNR may be different, which shows the limitations of our theoretical results.

One of our important conclusion is valid, that is, the larger the sample size $N$ and signal-to-noise ratio SNR, the better the generalization performance. Please refer to the uploaded PDF file.

Reference

[1] Cao, Y., Chen,Z., Belkin,M., and Gu,Q. Benign overfitting in two-layer convolutional neural networks. In NeurIPS 2022

[2] Kou, Y., Chen, Z., Chen, Y., and Gu, Q. Benign overfitting in two-layer ReLU convolutional neural networks. In ICML 2023

It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.

Thanks for your constructive feedback! We address your questions and concerns as follows.

Q1. Only considers the linearly separable setting, which is already solvable by existing vision and language models, so the conclusions are not very surprising even if initialization and model details differ.

A1. We follows the common assumptions made in previous studies of benign overfitting ( Cao et al. (2022)[1], Kou et al. (2023)[2] ) for the data generation model in this paper. Although this problem seems simple, rigorously proving these conclusions to show benign overfitting phenomenon is very challenging when considering the complexity of ViTs. In addition, rather than only presenting benign overfitting conclusion as most existing works, we also present harmful overfitting conclusion to show that the ViT cannot even learn a linearly separable dataset when the sample size $N$ and signal-to-noise ratio SNR is low.

Q2. Lacks clear takeaways for practitioners. What guidance can the authors provide to practitioners based on these theoretical results?

A2. Our theoretical results mainly focuse on the impact of different $N$ and SNR on the generalization performance. So we can provide guidance from the perspective of increasing $N$, SNR and $N \cdot \mathrm{SNR}^2$. The following are some practical scenarios.

• Data Augmentation: Researchers sometimes employ the technique of data augmentation by introducing controlled noise into their datasets. From the perspective of our paper's results, this method reduce SNR but improve N because we generate "new" data point by adding noises. As reducing SNR may be harmful to generalization performance, we must make sure that we use enough data points to train the model( enough sample size $N$ ).
• Semi-Supervised Learning: Semi-supervised learning is useful when you have a small amount of labeled data and a large amount of unlabeled data. Labeled data can be seen as data with high SNR, while unlabeled data with low SNR because for some unlabeled samples, we may mistake their labels, making them equivalent to noises. In this scenario, we need to ensure that we have sufficient unlabeled data (enough sample size $N$) and make full use of labeled data (high SNR data points).

Overall, we need to consider both the sample size $N$ and the signal-to-noise ratio SNR to train the model.

Q3. Could the authors provide a more rigorous perspective on transformer bias (e.g. low rank structure) from an optimization perspective under their model?

A3. We present a brief discussion about the rank of matrix $W_V$ under some conditions as follows:

Suppose that $SNR \rightarrow \infty$, then we have $\Vert \mu \Vert / \Vert \xi \Vert \rightarrow \infty$. Recall Equation (9) (Line 583), we have:

$\lim \ \nabla_{W_V}L_S(\theta) = ( a \mu_+ + b \mu_- ) w_O^\top$

where a and b are linear combination coefficients for $\mu_+$ and $\mu_-$. Note that $\mu_+$, $\mu_-$ and $w_O$ are vectors (rank = 1), so we have:

$R(\lim \ \nabla_{W_V}L_S(\theta)) = 1$

Considering that the weights of model are usually initialized to be very small, matrix $W_V$ tends to decrease its rank during training because it changes towards its gradient direction $\nabla_{W_V}L_S(\theta)$. The analysis of QK is also similar.

As for a more rigorous proof, we will consider developing new theoretical techniques to prove it.

Q4. If an MLP with ReLU activation was used instead of the simple linearly separable task, would the optimization dynamics converge faster or slower?

A4. Kou et al. (2023)[2] investigate the benign overfitting phenomenon in two-layer ReLU CNN. Note that their data model only contains one patch of signal and one patch of noise, we can consider their CNN model to be a special MLP, especially in cases of very high or low SNR. Their results show that their model can converge to training loss $\epsilon$ at $t = \eta^{-1} poly(\epsilon^{-1}, d, n, m)$, while the ViT model we consider can converge at $t = \eta^{-1} poly(\epsilon^{-1}, \Vert \mu \Vert, \Vert w_O \Vert)$. Ignoring parameters such as network size, sample size, norm of input and so on, we found that their convergence time is proportional to $\eta^{-1}$ and $\epsilon^{-1}$. So we can think that their convergence speed is of the same order.

Q5. Would the SNR requirements be stricter or more relaxed?

A5. According to Condition 4.1. in Kou et al. (2023)[2], they require $\mathrm{SNR}^2 \le \tilde{O}(1/N)$ and require $\Vert \mu \Vert_2$ to be large enough, which is stricter than our condition.

Reference

[1] Cao, Y., Chen,Z., Belkin,M., and Gu,Q. Benign overfitting in two-layer convolutional neural networks. In NeurIPS 2022

[2] Kou, Y., Chen, Z., Chen, Y., and Gu, Q. Benign overfitting in two-layer ReLU convolutional neural networks. In ICML 2023

It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.

Thanks for your constructive feedback! We address your questions and concerns as follows.

Weakness. Readability issues

A. We realize that readability is important for readers to understand and further apply our techniques. In order to enhance readability, we have made the following efforts:

• We present a proof sketch in the main text, which contains three main challenges and our solutions, allowing readers to quickly access our techniques.
• We provide a notation table in page 16, containing the key shorthand notations in this paper.
• In the appendix, we separate the high-level proof process from the low-level proof process. For example, in appendix F, we present some bounds for $\alpha$, $\beta$ and so on (low-level). In appendix D, we use the bounds in appendix F to complete the proofs for the key steps in the training dynamics (high-level).

We will make more efforts to further improve the readability as follows:

• extend the proof sketch: We consider providing a more comprehensive proof sketch in the appendix to fully describe the key steps in the proof process.

• simplify the notations: The large number of symbols makes it difficult for readers to recall the meaning of a particular symbol. So we will do efforts to make it easier to remember and understand.

• improve the clarity and writing: We will add more textual descriptions and remarks during the proof process to help readers better understand the proofs.

Q1. In the data distribution (Definition 3.1), what is the role of the larger noise $\xi_2$ in the analysis?

A1. By Condition 4.1.(10), we ensure that the norm of $\xi_2$ is sufficiently larger than that of other noises. Then under harmful overfitting regime, it becomes easier to prove that $\xi_2$ attract most of the attention and the model learns little signal, thus the test loss will be high.

Without Condition 4.1.(10), it is much more challenging to prove harmful overfitting results. Next we discuss the difficulty we face when $\xi_2$ share the same variance with other noises ($\tilde{\sigma}_p = \sigma_p$)

To prove harmful overfitting, we must prove that the model learn little signals, i.e., signals attract less and less attention and $W_V$ learn little signals.

To prove that the model learn little signals while the training loss converges, we must prove that the model memorizes the noises, i.e., noises attract most of the attention and $W_V$ memorizes the noises well.

But it is difficult to characterize the attention attracted by the noises. For example, consider the scenario at initialization where there are noises $\xi_i$ and $\xi_j$ satisfy: more attention is paid on $\xi_i$ than $\xi_j$ ( attn($\xi_i$) $>$ attn($\xi_j$) ), and $W_V$ memorizes $\xi_j$ better than $\xi_i$ ( denoted by $\rho_j > \rho_i$ ) (under Gaussian initialization, this situation may occur). As we mention in Section 5.2, QK affect V ,and V affect QK. Therefore, the condition $\rho_j > \rho_i$ may lead to an increase in attn($\xi_j$) and a decrease in attn($\xi_i$) in the next training iteration. Meanwhile, the condition attn($\xi_i$) $>$ attn($\xi_j$) may result in $\rho_i$ growing faster than $\rho_j$. Therefore, in the next iteration, the following situations may happen:

• attn($\xi_i$) $>$ attn($\xi_j$), $\rho_i > \rho_j$
• attn($\xi_i$) $>$ attn($\xi_j$), $\rho_i < \rho_j$
• attn($\xi_i$) $<$ attn($\xi_j$), $\rho_i > \rho_j$
• attn($\xi_i$) $<$ attn($\xi_j$), $\rho_i < \rho_j$

We cannot know which situation will occur, let alone give them precise bounds. New techniques need to be developed to handle this difficulty.

In this paper, we let $\xi_2$ to be stronger than other noises, thus much attention will be paid on $\xi_2$, and $W_V$ will memorize $\xi_2$ well under harmful overfitting regime.

Q2. What would happen if the data distribution were the same as that considered in Cao et al. (2022), which consists of a single signal patch and a single noise patch?

A2. It is a special case of our Condition (number of input tokens M=2), and the conclusion will remain unchanged.

Q3. In the numerical results section, it would be beneficial to compare the results with those for a two-layer convolutional neural network, as considered in Cao et al. (2022), to emphasize the advantages of the transformer architecture.

A3. Thank you for your suggestion. We made the comparison in Lines 176 - 178. We will consider adding numerical results to emphasize it.

Reference

[1] Cao, Y., Chen,Z., Belkin,M., and Gu,Q. Benign overfitting in two-layer convolutional neural networks. In NeurIPS 2022

Thanks for your constructive feedback! We address your questions and concerns as follows.

Q. The current experiments only validate the theoretical results on synthetic datasets. It is recommended that the authors consider adding some experiments on real datasets to test the effects, such as experiments on benign overfitting of the ViT model on MNIST and CIFAR10.

A. We perform some experiments on MNIST dataset. Please find the results in the uploaded PDF file. The experimental result shows a transition between benign and harmful overfitting regimes. The larger the sample size $N$ and signal-to-noise ratio SNR, the better the generalization performance.

It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.

Thanks for your constructive feedback! We address your questions and concerns as follows.

Q1. Lack the introduction of the benign overfitting phenomenon in the first section.

A1. In the first section, we first introduce the Transformers and ViT models, and then the empirical and theoretical studies of ViT, and finally the benign overfitting phenomenon, followed by our contributions. The introduction for benign overfitting is in Lines 35 - 38. Benign overfitting is a phenomenon where "the test error remains small despite overfitting to the training data". A more detailed introduction is in the first paragraph of the second section. We plan to add more explanations for benign overfitting.

Q2. It is better to clarify some notations like $\Omega(\cdot), \Theta(\cdot), \omega(\cdot)$

A2. Thank you for pointing it out, we will add a paragraph to explain them.

Q3. Data generation is specified, thus this model may be a little bit limited.

A3. The data generation model in this paper follows the common assumptions made in previous studies of benign overfitting ( Cao et al. (2022) [1], Kou et al. (2023) [2]). To demonstrate the practicality of our theoretical results in real-world datasets, we perform some experiments on MNIST dataset. The results are detailed in the uploaded PDF file. The experimental result shows a transition between benign and harmful overfitting regimes. The larger the sample size $N$ and signal-to-noise ratio SNR, the better the generalization performance.

Q4. In Theorem 4.1 and Theorem 4.2, the requirement is related to SNR. Why does $\tilde{\sigma}_p$ not occur in the requirement?

A4. In Condition 4.1 (10), we require that $\tilde{\sigma}_p = C_p \sigma_p$ and $C_p = 5 \sqrt{M}$. We do not make any requirement on $\Vert \mu \Vert$ and $\sigma_p$ in Condition 4.1 so that they are flexible. For example, if we want $\mathrm{SNR} = \Theta(1)$, then we can choose: $\Vert \mu \Vert = \Theta(d^{1/2}) , \sigma_p = \Theta(1)$ or $\Vert \mu \Vert = \Theta(1) , \sigma_p = \Theta(d^{-1/2})$. This setting enable the input to be more general. In real-world dataset, the normalization methods for data may not be the same. Sometimes images are normalized to 0 - 1, while sometimes they are 0 - 255.

References

[1] Cao, Y., Chen,Z., Belkin,M., and Gu,Q. Benign overfitting in two-layer convolutional neural networks. In NeurIPS 2022

[2] Kou, Y., Chen, Z., Chen, Y., and Gu, Q. Benign overfitting in two-layer ReLU convolutional neural networks. In ICML 2023

It will be very encouraging that you can reconsider raising your score if we have addressed all the issues you raised. Otherwise, we are happy with the further discussion.