Benign Overfitting in Two-layer Convolutional Neural Networks

Introduction

Modern deep learning models often consist of a huge number of model parameters, which is more than the number of training data points and therefore over-parameterized. These over-parameterized models can be trained to overfit the training data (achieving a close to $100\%$ training accuracy), while still making accurate prediction on the unseen test data. This phenomenon has been observed in a number of prior works (Zhang et al., 2017; Neyshabur et al., 2019), and is often referred to as benign overfitting (Bartlett et al., 2020). It revolutionizes the the classical understanding about the bias-variance trade-off in statistical learning theory, and has drawn great attention from the community (Belkin et al., 2018, 2019a, 2019b; Hastie et al., 2019).

There exist a number of works towards understanding the benign overfitting phenomenon. While they offered important insights into the benign overfitting phenomenon, most of them are limited to the settings of linear models (Belkin et al., 2019b; Bartlett et al., 2020; Hastie et al., 2019; Wu and Xu, 2020; Chatterji and Long, 2020; Zou et al., 2021b; Cao et al., 2021) and kernel/random features models (Belkin et al., 2018; Liang and Rakhlin, 2020; Montanari and Zhong, 2020), and cannot be applied to neural network models that are of greater interest. The only notable exceptions are (Adlam and Pennington, 2020; Li et al., 2021), which attempted to understand benign overfitting in neural network models. However, they are still limited to the “neural tagent kernel regime” (Jacot et al., 2018) where the neural network learning problem is essentially equivalent to kernel regression. Thus, it remains a largely open problem to show how and when benign overfitting can occur in neural networks.

Clearly, understanding benign overfitting in neural networks is much more challenging than that in linear models, kernel methods or random feature models. The foremost challenge stems from nonconvexity: previous works on linear models and kernel methods/random features are all in the convex setting, while neural network training is a highly nonconvex optimization problem. Therefore, while most of the previous works can study the minimum norm interpolators/maximum margin classifiers according to the implicit bias (Soudry et al., 2018) results for the corresponding models, existing implicit bias results for neural networks (e.g., Lyu and Li (2019)) are not sufficient and a new analysis of the neural network learning process is in demand.

In this work, we provide one such algorithmic analysis for learning two-layer convolutional neural networks (CNNs) with the second layer parameters being fixed as $+1$’s and $-1$’s and polynomial ReLU activation function: $\sigma(z)=\max\{0,z\}^{q}$, where $q>2$ is a hyperparameter. We consider a setting where the input data consist of label dependent signals and label independent noises, and utilize a signal-noise decomposition of the CNN filters to precisely characterize the signal learning and noise memorization processes during neural network training. Our result not only demonstrates that benign overfitting can occur in learning two-layer neural networks, but also gives precise conditions under which the overfitted CNN trained by gradient descent can achieve small population loss. Our paper makes the following major contributions:

We establish population loss bounds of overfitted CNN models trained by gradient descent, and theoretically demonstrate that benign overfitting can occur in learning over-parameterized neural networks. We show that under certain conditions on the signal-to-noise ratio, CNN models trained by gradient descent will prioritize learning the signal over memorizing the noise, and thus achieving both small training and test losses. To the best of our knowledge, this is the first result on the benign overfitting of neural networks that is beyond the neural tangent kernel regime.

We also establish a negative result showing that when the conditions on the signal-to-noise ratio do not hold, then the overfitted CNN model will achieve at least a constant population loss. This result, together with our upper bound result, reveals an interesting phase transition between benign overfitting and harmful overfitting.

Our analysis is based on a new proof technique namely signal-noise decomposition, which decomposes the convolutional filters into a linear combination of initial filters, the signal vectors and the noise vectors. We convert the neural network learning into a discrete dynamical system of the coefficients from the decomposition, and perform a two-stage analysis that decouples the complicated relation among the coefficients. This enables us to analyze the non-convex optimization problem, and bound the population loss of the CNN trained by gradient descent. We believe our proof technique is of independent interest and can potentially be applied to deep neural networks.

We note that a concurrent work (Frei et al., 2022) studies learning log-Concave mixture data with label flip noise using fully-connected two-layer neural networks with smoothed leaky ReLU activation. Notably, their risk bound matches the risk bound for linear models given in Cao et al. (2021) when the label flip noise is zero. However, their analysis only focuses on upper bounding the risk, and cannot demonstrate the phase transition between benign and harmful overfitting. Compared with (Frei et al., 2022), we focus on CNNs, and consider a different data model to better capture the nature of image classification problems. Moreover, we present both positive and negative results under different SNR regimes, and demonstrate a sharp phase transition between benign and harmful overfitting.

Related Work

A line of recent works have attempted to understand why overfitted predictors can still achieve a good test performance. Belkin et al. (2019a) first empirically demonstrated that in many machine learning models such as random Fourier features, decision trees and ensemble methods , the population risk curve has a double descent shape with respect to the number of model parameters. Belkin et al. (2019b) further studied two specific data models, namely the Gaussian model and Fourier series model, and theoretically demonstrated the double descent risk curve in linear regression. Bartlett et al. (2020) studied over-parameterized linear regression to fit data produced by a linear model with additive noises, and established matching upper and lower bounds of the risk achieved by the minimum norm interpolator on the training dataset. It is shown that under certain conditions on the spectrum of the data covariance matrix, the population risk of the interpolator can be asymptotically optimal. Hastie et al. (2019); Wu and Xu (2020) studied linear regression in the setting where both the dimension and sample size grow together with a fixed ratio, and showed double descent of the risk with respect to this ratio. Chatterji and Long (2020) studied the population risk bounds of over-parameterized linear logistic regression on sub-Gaussian mixture models with label flipping noises, and showed how gradient descent can train over-parameterized linear models to achieve nearly optimal population risk. Cao et al. (2021) tightened the upper bound given by Chatterji and Long (2020) in the case without the label flipping noises, and established a matching lower bound of the risk achieved by over-parameterized maximum margin interpolators. Shamir (2022) proposed a generic data model for benign overfitting of linear predictors, and studied different problem settings under which benign overfitting can or cannot occur.

Besides the studies on linear models, several recent works also studied the benign overfitting and double descent phenomena in kernel methods or random feature models. Zhang et al. (2017) first pointed out that overfitting kernel predictors can sometimes still achieve good population risk. Liang and Rakhlin (2020) studied how interpolating kernel regression with radial basis function (RBF) kernels (and variants) can generalize and how the spectrum of the data covariance matrix affects the population risk of the interpolating kernel predictor. Li et al. (2021) studied the benign overfitting phenomenon of random feature models defined as two-layer neural networks whose first layer parameters are fixed at random initialization. Mei and Montanari (2019); Liao et al. (2020) demonstrated the double descent phenomenon for the population risk of interpolating random feature predictors with respect to the ratio between the dimensions of the random feature and the data input. Adlam and Pennington (2020) shows that neural tangent kernel (Jacot et al., 2018) based kernel regression has a triple descent risk curve with respect to the total number of trainable parameters. Montanari and Zhong (2020) further pointed out an interesting phase transition of the generalization error achieved by neural networks trained in the neural tangent kernel regime.

Problem Setup

In this section, we introduce the data generation model and the convolutional neural network we consider in this paper. We focus on binary classification, and present our data distribution $\mathcal{D}$ in the following definition.

The label $y$ is generated as a Rademacher random variable.

A noise vector $\bm{\xi}$ is generated from the Gaussian distribution $N(\mathbf{0},\sigma_{p}^{2}\cdot(\mathbf{I}-\bm{\mu}\bm{\mu}^{\top}\cdot\|\bm{\mu}\|_{2}^{-2}))$.

One of $\mathbf{x}_{1},\mathbf{x}_{2}$ is given as $y\cdot\bm{\mu}$, which represents the signal, the other is given by $\bm{\xi}$, which represents noises.

Intuitively, if a classifier learns the signal $\bm{\mu}$ and utilizes the signal patch of the data to make prediction, it can perfectly fit a given training data set $\{(\mathbf{x}_{i},y_{i}):i\in[n]\}$ and at the same time have a good performance on the test data. However, when the dimension $d$ is large ($d>n$), a classifier that is a function of the noises $\bm{\xi}_{i}$, $i\in[n]$ can also perfectly fit the training data set, while the prediction will be totally random on the new test data. Therefore, the data generation model given in Definition 3.1 is a useful model to study the population loss of overfitted classifiers. Similar models have been studied in some recent works by Li et al. (2019); Allen-Zhu and Li (2020a, b); Zou et al. (2021a).

Two-layer CNNs. We consider a two-layer convolutional neural network whose filters are applied to the two patches $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ separately, and the second layer parameters of the network are fixed as $+1/m$ and $-1/m$ respectively. Then the network can be written as $f(\mathbf{W},\mathbf{x})=F_{+1}(\mathbf{W}_{+1},\mathbf{x})-F_{-1}(\mathbf{W}_{-1},\mathbf{x})$, where $F_{+1}(\mathbf{W}_{+1},\mathbf{x})$, $F_{-1}(\mathbf{W}_{-1},\mathbf{x})$ are defined as:

We consider gradient descent starting from Gaussian initialization, where each entry of $\mathbf{W}_{+1}$ and $\mathbf{W}_{-1}$ is sampled from a Gaussian distribution $N(0,\sigma_{0}^{2})$, and $\sigma_{0}^{2}$ is the variance. The gradient descent update of the filters in the CNN can be written as

Main Results

In this section, we present our main theoretical results. At the core of our analyses and results is a signal-noise decomposition of the filters in the CNN trained by gradient descent. By the gradient descent update rule (3.1), it is clear that the gradient descent iterate $\mathbf{w}_{j,r}^{(t)}$ is a linear combination of its random initialization $\mathbf{w}_{j,r}^{(0)}$, the signal vector $\bm{\mu}$ and the noise vectors in the training data $\bm{\xi}_{i}$, $i\in[n]$. Motivated by this observation, we introduce the following definition.

Let $\mathbf{w}_{j,r}^{(t)}$ for $j\in\{\pm 1\}$, $r\in[m]$ be the convolution filters of the CNN at the $t$-th iteration of gradient descent. Then there exist unique coefficients $\gamma_{j,r}^{(t)}\geq 0$ and $\rho_{j,r,i}^{(t)}$ such that

We further denote $\overline{\rho}_{j,r,i}^{(t)}:=\rho_{j,r,i}^{(t)}\operatorname{\mathds{1}}(\rho_{j,r,i}^{(t)}\geq 0)$, $\underline{\rho}_{j,r,i}^{(t)}:=\rho_{j,r,i}^{(t)}\operatorname{\mathds{1}}(\rho_{j,r,i}^{(t)}\leq 0)$. Then we have that

We refer to (4.1) as the signal-noise decomposition of $\mathbf{w}_{j,r}^{(t)}$. We add normalization factors $\|\bm{\mu}\|_{2}^{-2},\|\bm{\xi}_{i}\|_{2}^{-2}$ in the definition so that $\gamma_{j,r}^{(t)}\approx\langle\mathbf{w}_{j,r}^{(t)},\bm{\mu}\rangle,\rho_{j,r,i}^{(t)}\approx\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle$. In this decomposition, $\gamma_{j,r}^{(t)}$ characterizes the progress of learning the signal vector $\bm{\mu}$, and $\rho_{j,r,i}^{(t)}$ characterizes the degree of noise memorization by the filter. Evidently, based on this decomposition, for some iteration $t$, (i) If some of $\gamma_{j,r}^{(t)}$’s are large enough while $|\rho_{j,r,i}^{(t)}|$ are relatively small, then the CNN will have small training and test losses; (ii) If some $\overline{\rho}_{j,r,i}^{(t)}$’s are large and all $\gamma_{j,r}^{(t)}$’s are small, then the CNN will achieve a small training loss, but a large test loss. Thus, Definition 4.1 provides a handle for us to study the convergence of the training loss as well as the the population loss of the CNN trained by gradient descent.

Our results are based on the following conditions on the dimension $d$, sample size $n$, neural network width $m$, learning rate $\eta$, initialization scale $\sigma_{0}$.

Dimension $d$ is sufficiently large: $d=\widetilde{\Omega}(m^{2\vee[4/(q-2)]}n^{4\vee[(2q-2)/(q-2)]})$.

Training sample size $n$ and neural network width $m$ satisfy $n,m=\Omega(\operatorname{\rm polylog}(d))$.

The learning rate $\eta$ satisfies $\eta\leq\widetilde{O}(\min\{\|\bm{\mu}\|_{2}^{-2},\sigma_{p}^{-2}d^{-1}\})$.

The standard deviation of Gaussian initialization $\sigma_{0}$ is appropriately chosen such that $\widetilde{O}(nd^{-1/2})\cdot\min\{(\sigma_{p}\sqrt{d})^{-1},\|\bm{\mu}\|_{2}^{-1}\}\leq\sigma_{0}\leq\widetilde{O}(m^{-2/(q-2)}n^{-[1/(q-2)]\vee 1})\cdot\min\{(\sigma_{p}\sqrt{d})^{-1},\|\bm{\mu}\|_{2}^{-1}\}$.

A few remarks on Condition 4.2 are in order. The condition on $d$ is to ensure that the learning is in a sufficiently over-parameterized setting, and similar conditions have been made in the study of learning over-parameterized linear models (Chatterji and Long, 2020; Cao et al., 2021). For example, if we choose $q=3$, then the condition on $d$ becomes $d=\widetilde{\Omega}(m^{4}n^{4})$. Furthermore, we require the sample size and neural network width to be at least polylogarithmic in the dimension $d$ to ensure some statistical properties of the training data and weight initialization to hold with probability at least $1-d^{-1}$, which is a mild condition. Finally, the conditions on $\sigma_{0}$ and $\eta$ are to ensure that gradient descent can effectively minimize the training loss, and they depend on the scale of the training data points. When $\sigma_{p}=O(d^{-1/2})$ and $\|\bm{\mu}\|_{2}=O(1)$, the step size $\eta$ can be chosen as large as $\widetilde{O}(1)$ and the initialization $\sigma_{0}$ can be as large as $\widetilde{O}(m^{-2/(q-2)}n^{-[1/(q-2)]\vee 1})$. In our paper, we only require $m,n=\Omega(\text{polylog}(d))$, so our initialization and step-size can be chosen as an almost constant order. Based on these conditions, we give our main result on signal learning in the following theorem.

The CNN learns the signal: $\max_{r}\gamma_{j,r}^{(t)}=\Omega(1)$ for $j\in\{\pm 1\}$.

The CNN does not memorize the noises in the training data: $\max_{j,r,i}|\rho_{j,r,i}^{(T)}|=\widetilde{O}(\sigma_{0}\sigma_{p}\sqrt{d})$.

The training loss converges to $\epsilon$, i.e., $L_{S}(\mathbf{W}^{(t)})\leq\epsilon$.

The trained CNN achieves a small test loss: $L_{\mathcal{D}}(\mathbf{W}^{(t)})\leq 6\epsilon+\exp(-n^{2})$

The CNN memorizes noises in the training data: $\max_{r}\overline{\rho}_{y_{i},r,i}^{(t)}=\Omega(1)$.

The CNN does not sufficiently learn the signal: $\max_{j,r}\gamma_{j,r}^{(t)}\leq\widetilde{O}(\sigma_{0}\|\bm{\mu}\|_{2})$.

The training loss converges to $\epsilon$, i.e., $L_{S}(\mathbf{W}^{(t)})\leq\epsilon$.

The trained CNN has a constant order test loss: $L_{\mathcal{D}}({\mathbf{W}}^{(t)})=\Theta(1)$.

Comparison with neural tangent kernel (NTK) results. We want to emphasize that our analysis is beyond the so-called neural tangent kernel regime. In the NTK regime, it has been shown that gradient descent can train an over-parameterized neural network to achieve good training and test accuracies (Jacot et al., 2018; Du et al., 2019b, a; Allen-Zhu et al., 2019b; Zou et al., 2019; Arora et al., 2019a; Cao and Gu, 2019a; Chen et al., 2019). However, it is widely believed in literature that the NTK analyses cannot fully explain the success of deep learning, as the neural networks in the NTK regime are almost “linearized” (Lee et al., 2019; Cao and Gu, 2019a). Our analysis and results are not in the NTK regime: In the NTK regime, the network parameters stay close to their initialization throughout training, i.e., $\|\mathbf{W}^{(t)}-\mathbf{W}^{(0)}\|_{F}=O(1)$, so that the NN model can be approximated by its linearization (Allen-Zhu et al., 2019b; Cao and Gu, 2019a; Chen et al., 2019). In comparison, our analysis does not rely on linearizing the neural network function, and $\|\mathbf{W}^{(t)}-\mathbf{W}^{(0)}\|_{F}$ can be as large as $O(\text{poly}(m))$.

Overview of Proof Technique

In this section, we discuss the main challenges in the study of CNN training under our setting, and explain some key techniques we implement in our proofs to overcome these challenges. The complete proofs of all the results are given in the appendix.

Main challenges. Studying benign overfitting under our setting is a challenging task. The first challenge is the nonconvexity of the training objective function $L_{S}(\mathbf{W})$. Nonconvexity has introduced new challenges in the study of benign overfitting particularly because our goal is not only to show the convergence of the training loss, but also to study the population loss in the over-parameterized setting, which requires a precise algorithmic analysis of the learning problem.

In order to study the learning process based on the nonconvex optimization problem, we propose a key technique which enables the iterative analysis of the coefficients in the signal-noise decomposition in Definition 4.1. This technique is given in the following lemma.

The coefficients $\gamma_{j,r}^{(t)},\overline{\rho}_{j,r,i}^{(t)},\underline{\rho}_{j,r,i}^{(t)}$ in Definition 4.1 satisfy the following equations:

With Lemma 5.1, we can reduce the study of the CNN learning process to the analysis of the discrete dynamical system given by (5.1)-(5.4). Our proof then focuses on a careful assessment of the values of the coefficients $\gamma_{j,r}^{(t)},\overline{\rho}_{j,r,i}^{(t)},\underline{\rho}_{j,r,i}^{(t)}$ throughout training. To prepare for more detailed analyses, we first present the following bounds of the coefficients, which hold throughout training.

Under Condition 4.2, for any $T^{*}=\eta^{-1}\text{poly}(\epsilon^{-1},\|\bm{\mu}\|_{2}^{-1},d^{-1}\sigma_{p}^{-2},\sigma_{0}^{-1},n,m,d)$, the following bounds hold for $t\in[0,T^{*}]$:

$0\leq\gamma_{j,r}^{(t)},\overline{\rho}_{j,r,i}^{(t)}\leq 4\log(T^{*})$ for all $j\in\{\pm 1\}$, $r\in[m]$ and $i\in[n]$.

$0\geq\underline{\rho}_{j,r,i}^{(t)}\geq-2\max_{i,j,r}\{|\langle\mathbf{w}_{j,r}^{(0)},\bm{\mu}\rangle|,|\langle\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle|\}-16n\sqrt{\frac{\log(4n^{2}/\delta)}{d}}\cdot 4\log(T^{*})$ for all $j\in\{\pm 1\}$, $r\in[m]$ and $i\in[n]$.

We can then prove the following lemma, which demonstrates that the training objective function $L_{S}(\mathbf{W})$ can dominate the gradient norm $\|\nabla L_{S}(\mathbf{W}^{(t)})\|_{F}$ along the gradient descent path.

Under Condition 4.2, for any $T^{*}=\eta^{-1}\text{poly}(\epsilon^{-1},\|\bm{\mu}\|_{2}^{-1},d^{-1}\sigma_{p}^{-2},\sigma_{0}^{-1},n,m,d)$, the following result holds for $t\in[0,T^{*}]$:

2 Decoupling with a Two-Stage Analysis.

Under the same conditions as Theorem 4.3, there exists $T_{1}=\widetilde{O}(\eta^{-1}m\sigma_{0}^{2-q}\|\bm{\mu}\|_{2}^{-q})$ such that

$\max_{r}\gamma_{j,r}^{(T_{1})}=\Omega(1)$ for $j\in\{\pm 1\}$.

$|\rho_{j,r,i}^{(t)}|=O(\sigma_{0}\sigma_{p}\sqrt{d})$ for all $j\in\{\pm 1\}$, $r\in[m]$, $i\in[n]$ and $0\leq t\leq T_{1}$.

where the second inequality follows by the convexity of the cross-entropy loss function. With the above key technique, we can prove the following lemma.

Let $T,T_{1}$ be defined in Theorem 4.3 and Lemma 5.5 respectively. Then under the same conditions as Theorem 4.3, for any $t\in[T_{1},T]$, it holds that $|\rho_{j,r,i}^{(t)}|\leq\sigma_{0}\sigma_{p}\sqrt{d}$ for all $j\in\{\pm 1\}$, $r\in[m]$ and $i\in[n]$. Moreover, let $\mathbf{W}^{*}$ be the collection of CNN parameters with convolution filters $\mathbf{w}^{*}_{j,r}=\mathbf{w}_{j,r}^{(0)}+2qm\log(2q/\epsilon)\cdot j\cdot\|\bm{\mu}\|_{2}^{-2}\cdot\bm{\mu}$. Then the following bound holds

for all $t\in[T_{1},T]$, where we denote $\|\mathbf{W}\|_{F}=\sqrt{\|\mathbf{W}_{+1}\|_{F}^{2}+\|\mathbf{W}_{-1}\|_{F}^{2}}$.

Lemma 5.6 states two main results on signal learning. First of all, during this training period, it is guaranteed that the coefficients of noise vectors $\rho_{j,r,i}^{(t)}$ in the signal-noise decomposition remain sufficiently small. Moreover, it also gives an optimization type result that the best iterate in $[T_{1},T]$ is small as long as $T$ is large enough.

Clearly, the convergence of the training loss stated in Theorems 4.3 directly follows by choosing $T$ to be sufficiently large in Lemmas 5.6. The lemma below further gives an upper bound on the test loss.

Let $T$ be defined in Theorem 4.3. Under the same conditions as Theorem 4.3, for any $t\leq T$ with $L_{S}(\mathbf{W}^{(t)})\leq 1$, it holds that $L_{\mathcal{D}}(\mathbf{W}^{(t)})\leq 6\cdot L_{S}(\mathbf{W}^{(t)})+\exp(-n^{2})$.

Below we finalize the proof of Theorem 4.3. The proofs of other results are in the appendix.

The first part of Theorem 4.3 follows by Lemma 5.5 and the monotonicity of $\gamma_{j,r}^{(t)}$. The second part of Theorem 4.3 follows by Lemma 5.6. For the third part, let $\mathbf{W}^{*}$ be defined in Lemma 5.6. Then by the definition of $\mathbf{W}^{*}$, we have

where the first inequality is by triangle inequality, the second inequality is by the signal-noise decomposition of $\mathbf{W}^{(T_{1})}$ and the definition of $\mathbf{W}^{*}$, and the last equality is by Proposition 5.3 and Lemma 5.5. Therefore, choosing $T=\widetilde{\Theta}(\eta^{-1}T_{1}+\eta^{-1}\epsilon^{-1}m^{3}\|\bm{\mu}\|_{2}^{-2})=\widetilde{\Theta}(\eta^{-1}\sigma_{0}^{-(q-2)}\|\bm{\mu}\|_{2}^{-q}+\eta^{-1}\epsilon^{-1}m^{3}\|\bm{\mu}\|_{2}^{-2})$ in Lemma 5.6 ensures that

and there exists $t\in[T_{1},T]$ such that $L_{S}(\mathbf{W}^{(t)})\leq\epsilon$. This completes the proof of the third part of Theorem 4.3. Finally, combining this bound with Lemma 5.7 gives

which proves the last part of Theorem 4.3. ∎

Conclusion and Future Work

This paper utilizes a signal-noise decomposition to study the signal learning and noise memorization process in the training of a two-layer CNN. We precisely give the conditions under which the CNN will mainly focus on learning signals or memorizing noises, and reveals a phase transition of the population loss with respect to the sample size, signal strength, noise level, and dimension. Our result theoretically demonstrates that benign overfitting can happen in neural network training. An important future work direction is to study the benign overfitting phenomenon of neural networks in learning other data models. Moreover, it is also important to generalize our analysis to deep convolutional neural networks.

Acknowledgements

We would like to thank Spencer Frei for valuable comment and discussion on the earlier version of this paper, and pointing out a related work.

Appendix A Additional Related Work

There has also been a large number of works studying the optimization and generalization of neural networks. A series of work (Li and Yuan, 2017; Soltanolkotabi, 2017; Du et al., 2018a, b; Zhong et al., 2017; Zhang et al., 2019; Cao and Gu, 2019b) studied the parameter recovery problem in two-layer neural networks, where the data are given by a teacher network and the task is to recover the parameters in the teacher network. These works either focus on the noiseless setting, or requires the number of training data points to be larger than the number of parameters in the network, and therefore does not cover the setting where the neural network can overfit the training data. Another line of works (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2018; Golowich et al., 2018; Arora et al., 2018) have studied the generalization gap between the training and test losses of neural networks with uniform convergence based arguments. However, these results are not algorithm-dependent and cannot explain benign overfitting. Some recent works studied the generalization gap based on stability based arguments (Bousquet and Elisseeff, 2002; Hardt et al., 2016; Mou et al., 2017; Chen et al., 2018). A more recent line of works studied the convergence (Jacot et al., 2018; Li and Liang, 2018; Du et al., 2019b; Allen-Zhu et al., 2019b; Du et al., 2019a; Zou et al., 2019) and test error bounds (Allen-Zhu et al., 2019a; Arora et al., 2019a, b; Cao and Gu, 2019a; Ji and Telgarsky, 2020; Chen et al., 2019) of over-parameterized networks in the neural tangent kernel regime. However, these works depend on the equivalence between neural network training and kernel methods, which cannot fully explain the success of deep learning. Compared with the works mentioned above, our work has a different focus which is to study the conditions for benign and harmful overfitting.

Appendix B Preliminary Lemmas

In this section, we present some pivotal lemmas that give some important properties of the data and the neural network parameters at their random initialization.

Suppose that $\delta>0$ and $n\geq 8\log(4/\delta)$. Then with probability at least $1-\delta$,

By Hoeffding’s inequality, with probability at least $1-\delta/2$, we have

Therefore, as long as $n\geq 8\log(4/\delta)$, we have

This proves the result for $|\{i\in[n]:y_{i}=1\}|$. The proof for $|\{i\in[n]:y_{i}=-1\}|$ is exactly the same, and we can conclude the proof by applying a union bound. ∎

The following lemma estimates the norms of the noise vectors $\bm{\xi}_{i}$, $i\in[n]$, and gives an upper bound of their inner products with each other.

Suppose that $\delta>0$ and $d=\Omega(\log(4n/\delta))$. Then with probability at least $1-\delta$,

By Bernstein’s inequality, with probability at least $1-\delta/(2n)$ we have

Therefore, as long as $d=\Omega(\log(4n/\delta))$, we have

Moreover, clearly $\langle\bm{\xi}_{i},\bm{\xi}_{i^{\prime}}\rangle$ has mean zero. For any $i,i^{\prime}$ with $i\neq i^{\prime}$, by Bernstein’s inequality, with probability at least $1-\delta/(2n^{2})$ we have

Applying a union bound completes the proof. ∎

The following lemma studies the inner product between a randomly initialized CNN convolutional filter $\mathbf{w}_{j,r}^{(0)}$, $j\in\{+1,-1\}$ and $r\in[m]$ and the signal/noise vectors in the training data. The calculations characterize how the neural network at initialization randomly captures signal and noise information.

Suppose that $d\geq\Omega(\log(mn/\delta))$, $m=\Omega(\log(1/\delta))$. Then with probability at least $1-\delta$,

for all $r\in[m]$, $j\in\{\pm 1\}$ and $i\in[n]$. Moreover,

It is clear that for each $r\in[m]$, $j\cdot\langle\mathbf{w}_{j,r}^{(0)},\bm{\mu}\rangle$ is a Gaussian random variable with mean zero and variance $\sigma_{0}^{2}\|\bm{\mu}\|_{2}^{2}$. Therefore, by Gaussian tail bound and union bound, with probability at least $1-\delta/4$,

By Lemma B.2, with probability at least $1-\delta/4$, $\sigma_{p}\sqrt{d}/\sqrt{2}\leq\|\bm{\xi}_{i}\|_{2}\leq\sqrt{3/2}\cdot\sigma_{p}\sqrt{d}$ for all $i\in[n]$. Therefore, the result for $\langle\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle$ follows the same proof as $j\cdot\langle\mathbf{w}_{j,r}^{(0)},\bm{\mu}\rangle$. ∎

Appendix C Signal-noise Decomposition Analysis

The coefficients $\gamma_{j,r}^{(t)},\overline{\rho}_{j,r,i}^{(t)},\underline{\rho}_{j,r,i}^{(t)}$ defined in Definition 4.1 satisfy the following iterative equations:

for all $r\in[m]$, $j\in\{\pm 1\}$ and $i\in[n]$.

By our data model in Definition 3.1 and Gaussian initialization of the CNN weights, it is clear that with probability $1$, the vectors are linearly independent. Therefore, the decomposition (4.1) is unique. Now consider $\widetilde{\gamma}_{j,r}^{(0)},\widetilde{\rho}_{j,r,i}^{(0)}=0$ and

Hence by the uniqueness of the decomposition we have $\gamma_{j,r}^{(t)}=\widetilde{\gamma}_{j,r}^{(t)}$ and $\rho_{j,r,i}^{(t)}=\widetilde{\rho}_{j,r,i}^{(t)}$. Then we have that

Writing out the iterative versions of (C.1) and (C.2) completes the proof. ∎

We can futher plug the signal-noise decomposition (4.1) into the iterative formulas in Lemma C.1. By the second equation in Lemma C.1, we have

Moreover, by the third equation in Lemma C.1, we have

if $j=y_{i}$, and $\overline{\rho}_{j,r,i}^{(t)}=0$ for all $t\geq 0$ if $j=-y_{i}$. Similarly, by the last equation in Lemma C.1, we have

if $j=-y_{i}$, and $\underline{\rho}_{j,r,i}^{(t)}=0$ for all $t\geq 0$ if $j=y_{i}$.

We will now show that the parameter of the signal-noise decomposition will stay a reasonable scale during a long time of training. Let us consider the learning period $0\leq t\leq T^{*}$, where $T^{*}=\eta^{-1}\text{poly}(\epsilon^{-1},\|\bm{\mu}\|_{2}^{-1},d^{-1}\sigma_{p}^{-2},\sigma_{0}^{-1},n,m,d)$ is the maximum admissible iterations. Note that we can consider any polynomial training time $T^{*}$. Denote $\alpha=4\log(T^{*})$. Here we list the exact conditions for $\eta,\sigma_{0},d$ required by the proofs in this section, which are part of Condition 4.2:

Denote $\beta=2\max_{i,j,r}\{|\langle\mathbf{w}_{j,r}^{(0)},\bm{\mu}\rangle|,|\langle\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle|\}$. By Lemma B.3, with probability at least $1-\delta$, we can upper bound $\beta$ by $4\sqrt{\log(8mn/\delta)}\cdot\sigma_{0}\cdot\max\{\|\bm{\mu}\|_{2},\sigma_{p}\sqrt{d}\}$. Then, by (C.7) and (C.8), it is straightforward to verify the following inequality:

Suppose the conditions listed in (C.6), (C.7) and (C.8) hold, we claim that for $0\leq t\leq T^{*}$ the following property holds.

Under Condition 4.2, for $0\leq t\leq T^{*}$, we have that

for all $r\in[m]$, $j\in\{\pm 1\}$ and $i\in[n]$.

We will use induction to prove Proposition C.2. We first introduce several technical lemmas that will be used for the proof of Proposition C.2.

For any $t\geq 0$, it holds that $\langle\mathbf{w}_{j,r}^{(t)}-\mathbf{w}_{j,r}^{(0)},\bm{\mu}\rangle=j\cdot\gamma_{j,r}^{(t)}$ for all $r\in[m]$, $j\in\{\pm 1\}$.

where the equation is by our orthogonal assumption. ∎

Under Condition 4.2, suppose (C.10) and (C.11) hold at iteration $t$. Then

for all $r\in[m]$, $j\in\{\pm 1\}$ and $i\in[n]$.

For $j\not=y_{i}$, we have that $\overline{\rho}_{j,r,i}^{(t)}=0$ and

where the second inequality is by Lemma B.2 and the last inequality is by $|\overline{\rho}^{(t)}_{j,r,i^{\prime}}|,|\underline{\rho}_{j,r,i^{\prime}}^{(t)}|\leq\alpha$ in (C.10) Similarly, for $y_{i}=j$, we have that $\underline{\rho}_{j,r,i}^{(t)}=0$ and

where the first inequality is by Lemma B.1 and the second inequality is by $|\overline{\rho}^{(t)}_{j,r,i^{\prime}}|,|\underline{\rho}_{j,r,i^{\prime}}^{(t)}|\leq\alpha$ in (C.10). Similarly, we can show that $\langle\mathbf{w}_{j,r}^{(t)}-\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle\geq\underline{\rho}_{j,r,i}^{(t)}-8n\sqrt{\log(4n^{2}/\delta)/d}\cdot\alpha$ and $\langle\mathbf{w}_{j,r}^{(t)}-\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle\geq\overline{\rho}_{j,r,i}^{(t)}-8n\sqrt{\log(4n^{2}/\delta)/d}\cdot\alpha$, which completes the proof. ∎

Under Condition 4.2, suppose (C.10) and (C.11) hold at iteration $t$. Then

where the inequality is by $\gamma_{j,r}^{(t)}\geq 0$. In addition, we have

where the first inequality is by Lemma C.4 and the second inequality is due to $\underline{\rho}_{j,r,i}^{(t)}\leq 0$. Then we can get that

where the first inequality is by (C.12), (C.13) and the second inequality is by (C.9). ∎

Under Condition 4.2, suppose (C.10) and (C.11) hold at iteration $t$. Then

for all $r\in[m]$, $j\in\{\pm 1\}$ and $i\in[n]$. If $\max\{\gamma_{j,r}^{(t)},\overline{\rho}_{j,r,i}^{(t)}\}=O(1)$, we further have that $F_{j}(\mathbf{W}_{j}^{(t)},\mathbf{x}_{i})=O(1)$.

where the equation is by Lemma C.3. We also have that

where the inequality is by Lemma C.4. If $\max\{\gamma_{j,r}^{(t)},\overline{\rho}_{j,r,i}^{(t)}\}=O(1)$, we have following bound

where the first inequality is by (C.14), (C.15) and the second inequality is by (C.9) where $\beta=2\max_{i,j,r}\{|\langle\mathbf{w}_{j,r}^{(0)},\bm{\mu}\rangle|,|\langle\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle|\}$. ∎

Now we are ready to prove Proposition C.2.

Our proof is based on induction. The results are obvious at $t=0$ as all the coefficients are zero. Suppose that there exists $\widetilde{T}\leq T^{*}$ such that the results in Proposition C.2 hold for all time $0\leq t\leq\widetilde{T}-1$. We aim to prove that they also hold for $t=\widetilde{T}$.

We first prove that (C.11) holds for $t=\widetilde{T}$, i.e., $\underline{\rho}^{(t)}_{j,r,i}\geq-\beta-16n\sqrt{\frac{\log(4n^{2}/\delta)}{d}}\alpha$ for $t=\widetilde{T}$, $r\in[m]$, $j\in\{\pm 1\}$ and $i\in[n]$. Notice that $\underline{\rho}_{j,r,i}^{(t)}=0,\forall j=y_{i}$. Therefore, we only need to consider the case that $j\not=y_{i}$. When $\underline{\rho}_{j,r,i}^{(\widetilde{T}-1)}\leq-0.5\beta-8n\sqrt{\frac{\log(4n^{2}/\delta)}{d}}\alpha$, by Lemma C.4 we have that

where the last inequality is by induction hypothesis. When $\underline{\rho}_{j,r,i}^{(\widetilde{T}-1)}\geq-0.5\beta-8n\sqrt{\frac{\log(4n^{2}/\delta)}{d}}\alpha$, we have that

Next we prove (C.10) holds for $t=\widetilde{T}$. We have

where the last inequality is due to Lemma C.5. Moreover, recall the update rule of $\gamma_{j,r}^{(t)}$ and $\overline{\rho}_{j,r,i}^{(t)}$,

Let $t_{j,r,i}$ to be the last time $t<T^{*}$ that $\overline{\rho}_{j,r,i}^{(t)}\leq 0.5\alpha$. Then we have that

where the first inequality is by Lemmas C.4 and B.2, the second inequality is by $\beta\leq 0.1\alpha$ and $8n\sqrt{\frac{\log(4n^{2}/\delta)}{d}}\alpha\leq 0.1\alpha$, the last inequality is by $\eta\leq nm/(q2^{q+2}\alpha^{q-2}\sigma_{p}^{2}d)$.

Second, we bound $I_{2}$. For $t_{j,r,i}<t<\widetilde{T}$ and $y_{i}=j$, we can lower bound $\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle$ as follows,

where the first inequality is by Lemma C.4, the second inequality is by $\overline{\rho}_{j,r,i}^{(t)}>0.5\alpha$ and $\langle\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle\geq-0.5\beta$ due to the definition of $t_{j,r,i}$ and $\beta$, the last inequality is by $\beta\leq 0.1\alpha$ and $8n\sqrt{\frac{\log(4n^{2}/\delta)}{d}}\alpha\leq 0.1\alpha$. Similarly, for $t_{j,r,i}<t<\widetilde{T}$ and $y_{i}=j$, we can also upper bound $\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle$ as follows,

where the first inequality is by Lemma C.4, the second inequality is by induction hypothesis $\overline{\rho}_{j,r,i}^{(t)}\leq\alpha$, the last inequality is by $\beta\leq 0.1\alpha$ and $8n\sqrt{\frac{\log(4n^{2}/\delta)}{d}}\alpha\leq 0.1\alpha$. Thus, plugging the upper and lower bounds of $\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle$ into $I_{2}$ gives

where the first inequality is by (C.16), the second inequality is by Lemma B.2, the third inequality is by \eta=O\big{(}nm/(q2^{q+2}\alpha^{q-2}\sigma_{p}^{2}d)\big{)} in (C.6), the fourth inequality is by our choice of $\alpha=4\log(T^{*})$ and the last inequality is due to the fact that $\log(T^{*})^{q}\geq\log(T^{*})$. Plugging the bound of $I_{1},I_{2}$ into (C.17) completes the proof for $\overline{\rho}$. Similarly, we can prove that $\gamma_{j,r}^{(\widetilde{T})}\leq\alpha$ using \eta=O\big{(}nm/(q2^{q+2}\alpha^{q-2}\|\bm{\mu}\|_{2}^{2})\big{)} in (C.6). Therefore Proposition C.2 holds for $t=\widetilde{T}$, which completes the induction. ∎

Based on Proposition C.2, we introduce some important properties of the training loss function for $0\leq t\leq T^{*}$.

Under Condition 4.2, for $0\leq t\leq T^{*}$, the following result holds.

Without loss of generality, we suppose that $y_{i}=1$ and $\mathbf{x}_{i}=[\bm{\mu}^{\top},\bm{\xi}_{i}]$. Then we have that

where the first and second inequalities are by triangle inequality, the third inequality is by Jensen’s inequality and Lemma B.2, and the last inequality is due to Lemma C.5. Denote $A=F_{+1}(\mathbf{W}_{+1}^{(t)},\mathbf{x}_{i})$. Then we have that $A\geq 0$, and besides, $F_{-1}(\mathbf{W}^{(t)}_{-1},\mathbf{x}_{i})\leq 1$ by Lemma C.5. Then we have that

Appendix D Signal Learning

In this section, we consider the signal learning case under the condition that $n\|\bm{\mu}\|_{2}^{q}\geq\widetilde{\Omega}(\sigma_{p}^{q}(\sqrt{d})^{q})$. We remind the readers that the proofs in this section are based on the results in Section B, which hold with high probability.

Under the same conditions as Theorem 4.3, in particular if we choose

where $C=O(1)$ is a positive constant, there exists time

$\max_{r}\gamma_{j,r}^{(T_{1})}\geq 2$ for $j\in\{\pm 1\}$.

$|\rho_{j,r,i}^{(t)}|\leq\sigma_{0}\sigma_{p}\sqrt{d}/2$ for all $j\in\{\pm 1\},r\in[m]$, $i\in[n]$ and $0\leq t\leq T_{1}$.

We first prove the second bullet. Define $\Psi^{(t)}=\max_{j,r,i}|\rho_{j,r,i}^{(t)}|=\max_{j,r,i}\{\overline{\rho}_{j,r,i}^{(t)},-\underline{\rho}_{j,r,i}^{(t)}\}$. We use induction to show that

for all $0\leq t\leq T_{1}^{+}$. By definition, clearly we have $\Psi^{(0)}=0$. Now suppose that there exists some $\widetilde{T}\leq T_{1}^{+}$ such that (D.3) holds for $0<t\leq\widetilde{T}-1$. Then by (C.4) and (C.5) we have

where the second inequality follows by $\widetilde{T}\leq T_{1}^{+}$ in our induction hypothesis. Therefore, by induction, we have $\Psi^{(t)}\leq\sigma_{0}\sigma_{p}\sqrt{d}/2$ for all $t\leq T_{1}^{+}$.

Denote $\widehat{\gamma}_{1,r}^{(t)}=\gamma_{1,r}^{(t)}+\langle\mathbf{w}_{1,r}^{(0)},\bm{\mu}\rangle$ and let $A^{(t)}=\max_{r}\widehat{\gamma}_{1,r}^{(t)}$. Then we have

where the second inequality is by the lower bound on the number of positive data in Lemma B.1, the third inequality is due to the fact that $A^{(t)}$ is an increasing sequence, and the last inequality follows by $A^{(0)}=\max_{r}\langle\mathbf{w}_{1,r}^{(0)},\bm{\mu}\rangle\geq\sigma_{0}\|\bm{\mu}\|_{2}/2$ proved in Lemma B.3. Therefore, the sequence $A^{(t)}$ will exponentially grow and we have that

where the second inequality is due to the fact that $1+z\geq\exp(z/2)$ for $z\leq 2$ and our condition of $\eta$ and $\sigma_{0}$ listed in Condition 4.2, and the last inequality follows by Lemma B.3 and $A^{(0)}=\max_{r}\langle\mathbf{w}_{1,r}^{(0)},\bm{\mu}\rangle$. Therefore, $A^{(t)}$ will reach $3$ within $T_{1}=\frac{\log(6/\sigma_{0}\|\bm{\mu}\|_{2})2^{q+1}m}{C_{1}\eta q\sigma_{0}^{q-2}\|\bm{\mu}\|_{2}^{q}}$ iterations. Since $\max_{r}\gamma_{1,r}^{(t)}\geq A^{(t)}-\max_{r}|\langle\mathbf{w}_{1,r}^{(0)},\bm{\mu}\rangle|\geq A^{(t)}-1$, $\max_{r}\gamma_{1,r}^{(t)}$ will reach $2$ within $T_{1}$ iterations. We can next verify that

where the inequality holds due to our SNR condition in (D.1). Therefore, by the definition of $T_{1,1}$, we have $T_{1,1}\leq T_{1}\leq T_{1}^{+}/2$, where we use the non-decreasing property of $\gamma$. The proof for $j=-1$ is similar, and we can prove that $\max_{r}\gamma_{-1,r}^{(T_{1,-1})}\geq 2$ while $T_{1,-1}\leq T_{1}\leq T_{1}^{+}/2$, which completes the proof. ∎

D.2 Second Stage

By the results we get in the first stage we know that

And at the beginning of the second stage, we have following property holds:

$\max_{r}\gamma_{j,r}^{(T_{1})}\geq 2,\forall j\in\{\pm 1\}$.

$\max_{j,r,i}|\rho_{j,r,i}^{(T_{1})}|\leq\widehat{\beta}$ where $\widehat{\beta}=\sigma_{0}\sigma_{p}\sqrt{d}/2$.

Lemma 5.1 implies that the learned feature $\gamma_{j,r}^{(t)}$ will not get worse, i.e., for $t\geq T_{1}$, we have that $\gamma_{j,r}^{(t+1)}\geq\gamma_{j,r}^{(t)}$, and therefore $\max_{r}\gamma_{j,r}^{(t)}\geq 2$. Now we choose $\mathbf{W}^{*}$ as follows:

Based on the above definition of $\mathbf{W}^{*}$, we have the following lemma.

Under the same conditions as Theorem 4.4, we have that $\|\mathbf{W}^{(T_{1})}-\mathbf{W}^{*}\|_{F}\leq\widetilde{O}(m^{3/2}\|\bm{\mu}\|_{2}^{-1})$.

where the first inequality is by triangle inequality, the second inequality is by our decomposition of $\mathbf{W}^{(T_{1})}$ and the definition of $\mathbf{W}^{*}$, the third inequality is by Proposition C.2 and Lemma D.1, and the last inequality is by our condition of $\sigma_{0}$ in Condition 4.2. ∎

Under the same conditions as Theorem 4.3, we have that $y_{i}\langle\nabla f(\mathbf{W}^{(t)},\mathbf{x}_{i}),\mathbf{W}^{*}\rangle\geq q\log(2q/\epsilon)$ for all $i\in[n]$ and $T_{1}\leq t\leq T^{*}$.

Recall that f(\mathbf{W}^{(t)},\mathbf{x}_{i})=(1/m){\sum_{j,r}}j\cdot\big{[}\sigma(\langle\mathbf{w}_{j,r},y_{i}\cdot\bm{\mu}\rangle)+\sigma(\langle\mathbf{w}_{j,r},\bm{\xi}_{i}\rangle)\big{]}, so we have

where the inequality is by Lemma B.3. Next we will bound the inner-product terms in (D.4) respectively. By Lemma C.6, we have that for $j=y_{i}$

We can also get the upper bound of the inner products between the parameter and the signal (noise) as follows,

where (i) is by Lemma C.3, (iii) is by Lemma C.4, (ii) and (iv) are due to Proposition C.2. Plugging (D.5) and (D.6) into (D.4) gives,

where the last inequality is by $\sigma_{0}\leq\widetilde{O}(m^{-2/(q-2)}n^{-1})\cdot\min\{(\sigma_{p}\sqrt{d})^{-1},\|\bm{\mu}\|_{2}^{-1}\}$ in Condition 4.2. This completes the proof. ∎

Under the same conditions as Theorem 4.3, we have that

We first apply a proof technique similar to Lemma 2.6 in Ji and Telgarsky (2020). The difference between our analysis and Ji and Telgarsky (2020) is that here the neural network is $q$ homogeneous rather than 1 homogeneous.

where the first inequality is by Lemma D.3, the second inequality is due to the convexity of the cross entropy function, and the last inequality is due to Lemma C.7. ∎

Under the same conditions as Theorem 4.3, let T=T_{1}+\Big{\lfloor}\frac{\|\mathbf{W}^{(T_{1})}-\mathbf{W}^{*}\|_{F}^{2}}{2\eta\epsilon}\Big{\rfloor}=T_{1}+\widetilde{O}(m^{3}\eta^{-1}\epsilon^{-1}\|\bm{\mu}\|_{2}^{-2}). Then we have $\max_{j,r,i}|\rho_{j,r,i}^{(t)}|\leq 2\widehat{\beta}=\sigma_{0}\sigma_{p}\sqrt{d}$ for all $T_{1}\leq t\leq T$. Besides,

for all $T_{1}\leq t\leq T$, and we can find an iterate with training loss smaller than $\epsilon$ within $T$ iterations.

By Lemma D.4, for any $t\in[T_{1},T]$, we have that

holds for $s\leq t$. Taking a summation, we obtain that

for all $T_{1}\leq t\leq T$. Dividing $(t-T_{1}+1)$ on both side of (D.7) gives that

where we use the fact that $q>2$ and our choice that T=T_{1}+\Big{\lfloor}\frac{\|\mathbf{W}^{(T_{1})}-\mathbf{W}^{*}\|_{F}^{2}}{2\eta\epsilon}\Big{\rfloor}. Because the mean is smaller than $\epsilon$, we can conclude that there exist $T_{1}\leq t\leq T$ such that $L_{S}(\mathbf{W}^{(t)})<\epsilon$.

Finally, we will prove that $\max_{j,r,i}|\rho_{j,r,i}^{(t)}|\leq 2\widehat{\beta}$ for all $t\in[T_{1},T]$. Plugging T=T_{1}+\Big{\lfloor}\frac{\|\mathbf{W}^{(T_{1})}-\mathbf{W}^{*}\|_{F}^{2}}{2\eta\epsilon}\Big{\rfloor} into (D.7) gives that

where the inequality is due to $\|\mathbf{W}^{(T_{1})}-\mathbf{W}^{*}\|_{F}\leq\widetilde{O}(m^{3/2}\|\bm{\mu}\|_{2}^{-1})$ in Lemma D.2. Define $\Psi^{(t)}=\max_{j,r,i}|\rho_{j,r,i}^{(t)}|$. We will use induction to prove $\Psi^{(t)}\leq 2\widehat{\beta}$ for all $t\in[T_{1},T]$. At $t=T_{1}$, by the definition of $\widehat{\beta}$, clearly we have $\Psi^{(T_{1})}\leq\widehat{\beta}\leq 2\widehat{\beta}$. Now suppose that there exists $\widetilde{T}\in[T_{1},T]$ such that $\Psi^{(t)}\leq 2\widehat{\beta}$ for all $t\in[T_{1},\widetilde{T}-1]$. Then for $t\in[T_{1},\widetilde{T}-1]$, by (C.4) and (C.5) we have

where the second inequality is due to Lemmas B.2 and B.3, and the last inequality follows by the assumption that $d\geq 16n^{2}\log(4n^{2}/\delta)$. Taking a telescoping sum over $t=0,1,\ldots,\widetilde{T}-1$, we have that

D.3 Population Loss

Consider a new data point $(\mathbf{x},y)$ drawn from the distribution defined in Definition 3.1. Without loss of generality, we suppose that the first patch is the signal patch and the second patch is the noise patch, i.e., $\mathbf{x}=[y\bm{\mu},\bm{\xi}]$. Moreover, by the signal-noise decomposition, the learned neural network has parameter

Under the same conditions as Theorem 4.3, we have that $\max_{j,r}|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle|\leq 1/2$ for all $0\leq t\leq T$.

We can get the upper bound of the inner products between the parameter and the noise as follows:

for all $j\in\{\pm 1\}$, $r\in[m]$ and $i\in[n]$, where (i) is by Lemma C.3, (ii) is due to $|\langle\mathbf{w}_{j,r}^{(0)},\bm{\xi}_{i}\rangle|\leq 2\sqrt{\log(8mn/\delta)}\cdot\sigma_{0}\sigma_{p}\sqrt{d}$ in Lemma B.3 and $\max_{j,r,i}|\rho_{j,r,i}^{(t)}|\leq\sigma_{0}\sigma_{p}\sqrt{d}$ in Lemma D.5, and (iii) is due to our condition of $\sigma_{0}\leq\widetilde{O}(m^{-2/(q-2)}n^{-1})\cdot(\sigma_{p}\sqrt{d})^{-1}$ and $d\geq\widetilde{\Omega}(m^{2}n^{4})$ in Condition 4.2. ∎

Under the same conditions as Theorem 4.3, with probability at least $1-4mT\cdot\exp(-C_{2}^{-1}\sigma_{0}^{-2}\sigma_{p}^{-2}d^{-1})$, we have that $\max_{j,r}|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}\rangle|\leq 1/2$ for all $0\leq t\leq T$, where $C_{2}=\widetilde{O}(1)$.

Let $\widetilde{\mathbf{w}}_{j,r}^{(t)}=\mathbf{w}_{j,r}^{(t)}-j\cdot\gamma_{j,r}^{(t)}\cdot\frac{\bm{\mu}}{\|\bm{\mu}\|_{2}^{2}}$, then we have that $\langle\widetilde{\mathbf{w}}_{j,r}^{(t)},\bm{\xi}\rangle=\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}\rangle$ and

where the equality is due to $d\geq\widetilde{\Omega}(m^{2}n^{4})$ by Condition 4.2.

By (D.9), $\max_{j,r}\|\widetilde{\mathbf{w}}_{j,r}^{(t)}\|_{2}\leq C_{1}\sigma_{0}\sqrt{d}$, where $C_{1}=\widetilde{O}(1)$. Clearly $\langle\widetilde{\mathbf{w}}_{j,r}^{(t)},\bm{\xi}\rangle$ is a Gaussian distribution with mean zero and standard deviation smaller than $C_{1}\sigma_{0}\sigma_{p}\sqrt{d}$. Therefore, the probability is bounded by

Applying a union bound over $j,r,t$ completes the proof. ∎