Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data

Thank you for your supportive review. Please find our responses to your comments as follows.

Q1: It would be good to cite Hu & Lu, 2022 and Xiao et al., 2022 alongside Misiakiewicz (2022); Xiao & Pennington (2022) when discussing multiple descents in kernel ridge regression.

A1: Thank you for pointing out the missing references. We have cited them in the revision.

Q2: More discussions on the linearity of the Bayes-optimal classifier. The motivation of XOR.

A2: Previous studies investigating the benign overfitting phenomenon in learning neural networks may not fully demonstrate the power of neural networks compared to linear models, as the data used in those studies can also be well classified by linear models. In order to showcase the power of ReLU neural networks, we need to carefully select a dataset that cannot be effectively classified by linear models. The XOR data is a natural choice for such a dataset, as it can not be classified by any linear model, but can be classified by a two-layer ReLU CNN.

For learning the XOR-type data, our analysis of benign overfitting demonstrates that different neurons in the network can learn different signal directions. This is in contrast to previous works that rely on learning a single signal direction (in which case all neurons with the same second layer sign may be almost the same after training). Therefore, the XOR setting better highlights the strength of the non-linear structure of neural networks. We have added this discussion in the contribution part on page 2 to emphasize the significance of our approach in demonstrating the power of ReLU neural networks.

Q3: In condition 3.1, is a max or min missing in the $\Omega$ notation?

A3: Thanks for pointing it out. We have corrected the typo and the correct version should be $d= \widetilde{\Omega}(\mathrm{max}\\{n^2,n||\boldsymbol{\mu}||_2^2\sigma_p^{-2}\\})\cdot \mathrm{polylog}(1/\varepsilon)\cdot \mathrm{polylog}(1/\delta)$.

I thank the authors for the clarifications. I remain in favour of acceptance and maintain my score.

Thank you for your supportive comments and suggestions. We address your comments as follows.

Q1: 2 input patches seem very restrictive. Can the results be extended to CNNs with a larger number of patches? Why study CNNs instead of MLPs? Do similar results hold for standard MLPs?

A1: The two-layer CNN model considered in this paper follows the same definition as in [1,2,3]. Considering a case with two patches is just for the simplicity of the presentation, and our analysis can be easily extended to the case where the data inputs consist of multiple patches. The proof will be almost identical to the current proof given in the paper.

The primary goal of this paper is to explore the capabilities of non-linear neural networks in learning complex and "non-linear" data. We believe our analysis can be extended to MLPs with some necessary modifications, and the condition for benign overfitting can still be derived as a function of signal strength, noise level, sample size and data dimension, similar to what we have presented in Theorem 3.2.

Q2: Why is the Gaussian covariance matrix chosen to be dependent on the "true" XOR vectors? What about standard Normal distribution?

A2: We define the covariance matrix of the Gaussian vector in this way so that the noise vectors are orthogonal to the signal vectors. This is to simplify the setting and give a clearer and more refined analysis. Similar definitions have been studied in [1,2,3]. If the noise is given by standard Gaussian, the general proof idea does not change but we will need to rely on the fact that in the high dimensional setting (when $d$ is sufficiently large), the noise and signal vectors will be almost orthogonal to each other (with high probability). Therefore, the proof details will be more complicated and stronger assumptions on $d$ may be required.

Q3: In Condition 3.1, it seems that the dimension should grow with the sample complexity. It is better to separate conditions on the learning problem from choices of hyper-parameters and sample complexity. It makes more sense to assume a problem given with some fixed dimension, and then adapt the sample size. Does it mean that the sample size needs to be upper bounded?

A3: We clarify that this paper indeed studies the case where the dimension $d$ grows with the sample size $n$. This is because the goal of this paper is to study the phenomena of benign and harmful overfitting. Achieving overfitting necessitates the growth of dimension $d$ alongside sample size $n$. And we indeed need to assume that the sample size $n$ is upper bounded by a quantity related to $d$ so that the problem setting allows overfitting. It is noteworthy that the setting where $d$ increases with $n$ is also a common scenario studied in learning theory (e.g., [4,5,6]).

Q4: Condition for benign overfitting is $n||\boldsymbol{\mu}||_2^4=\Omega(\sigma_p^4d)$. Can you interpret this result? In what regimes of parameters does this hold? Is this always compatible with Condition 3.1?

A4: To interpret the results, we can see that the condition in Theorem 3.2 indicates that large $||\boldsymbol{\mu}||_2$ and sample size $n$ can help achieve benign overfitting, while large noise level $\sigma_p$ and data dimension $d$ can lead to harmful overfitting. The regime for Theorem 3.2 to hold is exactly Condition 3.1. Regarding whether Condition 3.1 is compatible with the benign overfitting condition $n|||\boldsymbol{\mu}||_2^4=\Omega(\sigma_p^4d)$, we can see that Condition 3.1 imposes a condition on the signal strength $||\boldsymbol{\mu}||_2$ requiring $||\boldsymbol{\mu}||_2\leq \sigma_p\sqrt{d/n}$, and the condition for benign overfitting in Theorem 3.2 is $||\boldsymbol{\mu}||_2\geq \sigma_p (d/n)^{1/4}$. Clearly, these two conditions do not conflict with each other as long as $d>n$.

Q5: Typos.

A5: Thank you for pointing out the typos. We have revised the paper and fixed the typos.

References:

[1] Yuan Cao, Zixiang Chen, Mikhail Belkin and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. NeurIPS, 2022.

[2] Xuran Meng, Yuan Cao and Difan Zou. Per-example gradient regularization improves learning signals from noisy data. arXiv:2303.17940, 2023.

[3] Samy Jelassi and Yuanzhi Li. Towards understanding how momentum improves generalization in deep learning. ICML, 2022.

[4] Spencer Frei, Niladri S Chatterji and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. COLT, 2022.

[5] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. CPAM, 2022.

[6] Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. FOCS, 2022.

Thank you for your review and feedback. We address your questions and concerns as follows.

Q1: Compared to Section 3.1, the results in Section 3.2 are of greater interest.

A1: We believe that the classic XOR regime (Section 3.1) and the asymptotically challenging XOR regime (Section 3.2) are equally important. As commented in our paper, Section 3.1 studies the regime that covers the standard XOR problem, and therefore it is more appropriate to compare the results in Section 3.1 with previous works. In comparison, Section 3.2 discusses a less standard, but more challenging setting, which requires different theoretical analyses. Therefore, we believe that the two regimes are both important.

Q2: Section 3.2 relies on strong assumptions. Condition 3.3 and the condition for benign overfitting in Theorem 3.4 are stronger than [1].

A2: We respectfully disagree with your comment. We strongly believe this comparison is unfair, and the weakness pointed out here is unreasonable. Our work investigates the XOR-type data, where the Bayes optimal classifier is nonlinear. For this XOR-type learning problem, the difficulty of learning (or how the noiseless samples are separated) depends on both the norms of the signal vectors and the angle between them. And the setting studied in Section 3.2 is a particularly challenging setting where the angle can be asymptotically small. In comparison, [1] only studied a much simpler learning problem where the Bayes-optimal classifier is linear, and in the setting of [1], there is no such concept of the angle between signals. Therefore, the settings in [1] and our work are not comparable, and the comparison between the rates in [1] and in Section 3.2 is unfair.

Q3: The transition between benign and harmful overfitting is not necessarily a phase transition but rather a continuous change.

A3: We would like to explain that the terminology "sharp phase transition" has been used in existing works [3,4] to describe the same type of transition between benign and harmful overfitting. Therefore, "sharp phase transition" is not invented by this paper, and we use this terminology mainly to highlight that the same type of transition between benign and harmful overfitting also happens in learning the XOR-type data.

We have also clarified in the revision (on Page 5) that by "sharp phase transition", we mean that in "boundary cases", an increase of the sample size $n$ or the signal strength $|| \boldsymbol{\mu} ||\_2$ by a logarithmic factor is sufficient to change the test error from a constant level to the optimal rate $p+o(1)$.

Q4: The relationship and differences between this work and [2].

A4: We would like to first point out that our paper was submitted to ICLR before the appearance of [2] on arXiv, and it is generally unreasonable to make a comparison between our paper and [2]. To answer your questions, we list several key differences between our work and [2] as follows:

Differences in problem settings:

• Our data model covers varying angles between the signal vectors, while [2] assumes that the signal vectors in the XOR data are orthogonal (therefore, [2] may be more comparable with our results in Section 3.1). Moreover, we consider the setting where the signals and noises are on different patches, while [2] considers the setting where the signals and noises are added together.

• We analyze CNN models, while [2] studies fully connected neural networks.

Differences in results:

• [2] requires $||\boldsymbol{\mu} ||_2^2 = \Omega( n^{0.51} \sqrt{d} )$, and the signal strength needs to increase as the sample size increases. In comparison, our results indicate that if the sample size $n$ increases, then a smaller signal strength $|| \boldsymbol{\mu} ||_2$ may be sufficient to achieve benign overfitting.

• [2] does not give any direct guarantees of training loss minimization, while our results show that gradient descent can achieve an arbitrarily small training loss.

• The results in [2] are for neural networks trained up to $\sqrt{n}$ iterations. In comparison, our results are for CNNs trained until convergence.

• [2] establishes an upper bound of the test error of the trained network, while we establish upper and lower bounds of the test error under complimentary conditions, demonstrating that these upper and lower bounds are both tight.

References:

[1] Spencer Frei, Niladri S Chatterji and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. COLT, 2022.

[2] Zhiwei Xu, Yutong Wang, Spencer Frei, Gal Vardi and Wei Hu. Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data. arxiv 2310.02541.

[3] Yiwen Kou, Zixiang Chen, Yuanzhou Chen and Quanquan Gu. Benign overfitting for two-layer relu networks. COLT, 2023.

[4] Yuan Cao, Zixiang Chen, Mikhail Belkin and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. NeurIPS, 2022.

Thank you for your thoughtful review and support. We address your comments as follows.

Q1: It is unclear how the test error changes as the number of samples and CNN width change. A figure of test accuracy versus the neural network width $m$ should be included.

A1: Our results in Theorem 3.2 suggest that as the sample size increases, the test error should decrease. Regarding the CNN width $m$, Theorem 3.2 indicates that the test error is not sensitive to $m$ as long as $m$ is large enough ($m = \Omega(\log(n/\delta))$ as is given in Condition 3.1). This is because in learning XOR problems, the test error is mainly affected by how much "signal" (the $\boldsymbol{\mu}$ vectors in Definitions 2.1 and 2.2) the CNN filters can learn from the training data. As long as $m$ is large enough to ensure a diverse enough random initialization of the CNN filters, further increasing $m$ does not significantly change the training dynamics of the CNN model. We also added a new set of experiments in Appendix I to demonstrate the relation between $m$ and the test error. As shown in Figure 3, for $m \geq 3$, the test error does not significantly change with $m$. This backs up our claim that as long as $m$ is large enough, the test error is not sensitive to $m$.

It is worth noting that the conditions of benign and harmful overfitting in Theorem 3.4 explicitly depend on $m$. This is because our proof technique for the asymptotically challenging XOR regime can only cover a specific initialization scale $\sigma_0$ that depends on $m$. For general initialization scales that do not depend on $m$, we believe that the test error should not be sensitive to $m$.

Q2: A result like Lemma 4.1 in a highly unbalanced case? Any requirements on the number difference between different data points?

A2: The balance among different types of data is implicitly given in Definitions 2.1 and 2.2. Following the definition of $\mathcal{D}\_{\mathrm{XOR}}(\mathbf{a},\mathbf{b})$ in Definition 2.1, it is easy to see that the different types of data are generated equally likely.

Our results in both the "classic XOR regime" and the "asymptotically challenging XOR regime" rely on the balance of the data. In the "classic XOR regime", we believe that Lemma 4.1 will still hold with unbalanced data. However, the subsequent analysis on the training dynamics will be significantly affected by unbalanced data. For instance, Lemma E.1 in Appendix E, which is a key lemma to show how much "signals" (the $\boldsymbol{\mu}$ vectors in Definitions 2.1 and 2.2) the CNN filters can learn from the training data, will no longer be valid. Similarly, in the "asymptotically challenging XOR regime", when the data are highly unbalanced, the results in Lemma G.17 will no longer hold.

Q3: I am not clear about the high-level understanding of Lemma 4.1.

A3: Lemma 4.1 shows that during training, the loss derivatives at each data point (i.e., $\ell’^{(t)}_i$, $i\in [n]$) maintain a constant level ratio over each other. This implies that each training data point is learned by the CNN model at a similar speed. The intuition that this result can hold is that in the high dimensional setting (where $d$ is sufficiently large), with high probability, the training data points should contain noise patches ($\boldsymbol{\xi}_i$) that are almost orthogonal to each other, and are almost of the same length. This maintains a level of “symmetry” in the training data, which enables us to prove Lemma 4.1.

Thank you for your detailed review and constructive comments. We address your questions as follows.

Q1: Comparison with the learning of 2-sparse parity is not rigorous: $n = \Omega(d)$ is not covered in Condition 3.1. The SNR in this paper needs to be larger than (Ji & Telgarsky (2020); Barak et al. (2022); Telgarsky (2023)), Ba et al. (2023).

A1: Thank you for pointing this out. We have revised the manuscript to emphasize that the comparison is not rigorous because Condition 3.1 requires $d = \tilde\Omega(n^2)$, which excludes the case $n=\omega(d)$. We have also discussed that the condition $d = \tilde\Omega(n^2)$ in Condition 3.1 is only a technical requirement to enable our current theoretical analysis (e.g. the proof of Lemma D.3). Therefore, Condition 3.1 can potentially be relaxed to cover the case $n=\omega(d)$ with different analysis tools, which can be an interesting future work direction. We have also cited the missing references in our discussion.

Q2: The initialization scale is small. How is the small initialization required in the analysis??

A2: We assume a relatively small initialization to ensure sufficient "feature learning": If the initialization is sufficiently small, the training updates (which consist of features from training data) of neural network parameters can quickly dominate their random initialization, thus during training, the neural network can achieve sufficient feature learning. On the other hand, if the initialization is large, then it may dominate the training updates, which can lead to the "Neural Tangent Kernel (NTK) regime" where the model essentially uses kernels or random features [1] to fit the training data. Our analysis in this paper does not fall in the NTK regime, and we study the case where training updates dominate the random initialization. This is why we assume that the initialization is sufficiently small. Similar conditions of small initialization have been widely assumed such as [2,3,4,5].

Q3: I do not see the necessity to extend the problem into the small angle case, where two axes of the input XOR distribution are much closer.

A3: Theorem 3.4 aims to study a more challenging case where the data are less separated. For simplicity, here we can consider a case without label flipping. In this case, the angle $\theta$ can be understood as the metric of the margin of the data, and a smaller angle means a smaller margin. For this more challenging case, our proof technique in Theorem 3.2 can no longer be applied, and therefore Theorem 3.4 and its proof may also have their unique technical value. This is why we also cover this setting in our paper.

Q4: More explanations about the motivation of the "loss derivative comparison" technique.

A4: The loss derivative comparison results serve as the key to analyze the training of the CNN with equation 4.1. Specifically, the result of loss derivative comparison in the "classic XOR regime" is given in Lemma 4.1 and the result in the "asymptotically challenging XOR regime" is given by Lemma 4.4.

The motivation of these results is that in equation 4.1, we hope to show that the terms without the $\cos\theta$ factor can dominate the terms with the $\cos\theta$ factor, which can significantly simplify our analysis. For example, with Lemma 4.1, we can see that in the "classic XOR regime" where $\cos\theta < 1/2$, for any $i,i'\in[n]$, a non-zero $\ell'^{(t)}\_i\cdot\boldsymbol{1}\\{\langle\mathbf{w}^{(t)}\_{+1,r},\boldsymbol{\mu}\_i\rangle>0\\}||\boldsymbol{\mu}||\_2^2$ will always dominate $\ell'^{(t)}\_{i'}\cdot \boldsymbol{1}\\{\langle\mathbf{w}^{(t)}\_{+1,r},\boldsymbol{\mu}\_{i'}\rangle>0\\}||\boldsymbol{\mu}||\_2^2\cos\theta$. For the "asymptotically challenging XOR regime", since a larger $\cos\theta$ that is close to $1$ is considered, we need the tighter bound on the ratios between loss derivatives given in Lemma 4.4.

We have added more explanations of the motivation of "loss derivative comparison" in the revision.

References:

[1] Arthur Jacot, Franck Gabriel and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS, 2018.

[2] Yiwen Kou, Zixiang Chen, Yuanzhou Chen and Quanquan Gu. Benign overfitting for two-layer relu networks. COLT, 2023.

[3] Yuan Cao, Zixiang Chen, Mikhail Belkin and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. NeurIPS, 2022.

[4] Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. FOCS, 2022.

[5] Spencer Frei, Niladri S Chatterji and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. COLT, 2022.