Benign Overfitting in Two-layer Convolutional
Neural Networks

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.

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.

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.

Our data generation model is inspired by image data, where the inputs consist of different patches, and only some of the patches are related to the class label of the image. In detail, the patch assigned as $y\cdot\bm{\mu}$ is the signal patch that is correlated to the label of the data, and the patch assigned as $\bm{\xi}$ is the noise patch that is independent of the label of the data and therefore is irrelevant for prediction. We assume that the noise patch 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}))$ to ensure that the noise vector is orthogonal to the signal vector $\bm{\mu}$ for simplicity. Note that when the dimension $d$ is large, $\|\bm{\xi}\|_{2}\approx\sigma_{p}\sqrt{d}$ by standard concentration bounds. Therefore, we can treat $\|\bm{\mu}\|_{2}/(\sigma_{p}\sqrt{d})\approx\|\bm{\mu}\|_{2}/\|\bm{\xi}\|_{2}$ as the signal-to-noise ratio. For the ease of discussion, we denote $\mathrm{SNR}=\|\bm{\mu}\|_{2}/(\sigma_{p}\sqrt{d})$. Note that the Bayes risk for learning our model is zero. We can also add label flip noise similar to Chatterji and Long (2020); Frei et al. (2022) to make the Bayes risk equal to the label flip noise and therefore nonzero, but this will not change the key message of our paper.

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).

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

for $j\in\{\pm 1\}$ and $r\in[m]$, where we introduce a shorthand notation $\ell_{i}^{\prime(t)}=\ell^{\prime}[y_{i}\cdot f(\mathbf{W}^{(t)},\mathbf{x}_{i})]$.

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.

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}$.

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.

Theorem 4.3 characterizes the case of signal learning. It shows that, if $n\cdot\mathrm{SNR}^{q}=\widetilde{\Omega}(1)$, then at least one CNN filter can learn the signal by achieving $\gamma_{j,r_{j}^{*}}^{(t)}\geq\Omega(1)$, and as a result, the learned neural network can achieve small training and test losses. To demonstrate the sharpness of this condition, we also present the following theorem for the noise memorization by the CNN.

Theorem 4.4 holds under the condition that $n^{-1}\cdot\mathrm{SNR}^{-q}=\widetilde{\Omega}(1)$. Clearly, this is the opposite regime (up to some logarithmic factors) compared with Theorem 4.3. In this case, the CNN trained by gradient descent mainly memorizes noises in the training data and does not learn enough signal. This, together with the results in Theorem 4.3, reveals a clear phase transition between signal learning and noise memorization in CNN training:

• •

  If $n\cdot\mathrm{SNR}^{q}=\widetilde{\Omega}(1)$, then the CNN learns the signal and achieves a $O(\epsilon+\exp(-n^{2}))$ test loss. This is the regime of benign overfitting.

• •

  If $n^{-1}\cdot\mathrm{SNR}^{-q}=\widetilde{\Omega}(1)$ then the CNN can only memorize noises and will have a $\Theta(1)$ test loss. This is the regime of harmful overfitting.

The phase transition is illustrated in Figure 1. Clearly, when learning a two-layer CNN on the data generated from Definition 3.1,$n\cdot\mathrm{SNR}^{q}=\widetilde{\Omega}(1)$ is the precise condition under which benign overfitting occurs. Remarkably, in this case the population loss decreases exponentially with the sample size $n$. Under our condition that $n=\Omega(\operatorname{\rm polylog}(d))$, this term can also be upper bounded by $1/\mathrm{poly}(d)$, which is small in the high-dimensional setting. Note that when $\|\bm{\mu}\|_{2}=\Theta(1)$ and $\sigma_{p}=\Theta(d^{-1/2})$, applying standard uniform convergence based bounds (Bartlett et al., 2017; Neyshabur et al., 2018) or stability based bounds (Hardt et al., 2016; Mou et al., 2017; Chen et al., 2018) typically gives a $\widetilde{O}(n^{-1/2})$ bound on the generalization gap, which is vacuous when $n=O(\operatorname{\rm polylog}(d))$. Our bound under the same setting is $O(1/\mathrm{poly}(d))$, which is non-vacuous. This is attributed to our precise analysis of signal learning and noise memorization in Theorems 4.3 and 4.4.

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.

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.

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.