Benign Overfitting in Two-layer Convolutional Neural Networks
Authors: Yuan Cao
Zixiang Chen
Misha Belkin
Quanquan Gu
Venue: NeurIPS 2022 Accept (2022)

Abstract: Modern neural networks often have great expressive power and can be trained to overfit the training data, while still achieving a good test performance. This phenomenon is referred to as “benign overfitting”. Recently, there emerges a line of works studying “benign overfitting” from the theoretical perspective. However, they are limited to linear models or kernel/random feature models, and there is still a lack of theoretical understanding about when and how benign overfitting occurs in neural networks. In this paper, we study the benign overfitting phenomenon in training a two-layer convolutional neural network (CNN). We show that when the signal-to-noise ratio satisfies a certain condition, a two-layer CNN trained by gradient descent can achieve arbitrarily small training and test loss. On the other hand, when this condition does not hold, overfitting becomes harmful and the obtained CNN can only achieve a constant level test loss. These together demonstrate a sharp phase transition between benign overfitting and harmful overfitting, driven by the signal-to-noise ratio. To the best of our knowledge, this is the first work that precisely characterizes the conditions under which benign overfitting can occur in training convolutional neural networks.

Benign Overfitting in Two-layer Convolutional Neural Networks
Yuan Cao"
Zixiang Chen'
Department of Statistics & Actuarial Science Department of Mathematics The University of Hong Kong yuancao@hku. hk
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095, USA chenzx19@ca, ucla.
Mikhail Belkin
Quanquan Gu
Haliciolu Data Science Institute University of California San Diego La Jolla, CA 92093, USA mbelkin@ucad, edu
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095, USA qguêcs wwwa.cccccooo.o.. edu
Abstract
Modern neural networks often have great expressive power and can be trained overfit the training data, while still achieving good test performance. This phenomenon referred to as "benign overfitting". Recently, there emerges line of works studying "henign overfitting" from the theoretical perspective. However, they are limited to linear models or kernel/random feature models, and there is still lack of theoretical understanding about when and how benign overfitting occurs in neural networks. In this paper, we study the benign overfitting phenomenon in training a two-layer convolutional neural network (CNN). We show that when the signal-to-noise ratio satisfies certain condition, two-layer CNN trained by gradient descent can achieve arbitrarily small training and test loss. On the other hand, when this condition does not hold, overfitting becomes harmful and the ob- tained CNN can only achieve constant level test loss. These together demonstrate sharp phase transition between benign overfitting and harmful overfitting, driven by the signal-to-noise ratio. To the best of our knowledge, this the first work that precisely characterizes the conditions under which benign overfitting can occur in training 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-parameterizee. These over-parameterized models can be trained to overfit the training data (achieving close to 100% training accuracy), while still making accurate prediction on the unseen test data. This phenomenon has been observed in number of prior works (Zhang et al., 2017 Neyshabur et all, 2019), and often referred as benign overfitting (Bartlett all 2020). It revolutionizes the classical understanding about the bias- variance trade-off statistical learning theory, and has drawn great attention from the community (Belkin et all 2018, 2 Haastie et all 2019).
There exist number of works towards understanding the benign overfitting phenomenon. While they offered important insights into the benign overfitting phenomenon, most of them are limited
Equul contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to the settings of linear models (Belkin et all, 2019h Bartlett et all 2020 Hastic et all 2019 WT
and Xu, 2020; Chatterji and Long, 2020: Zou et all 202T6 Cao et all 202T) and kernel/random features models (Belkin et all, 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: Lretal 2021), which attempted to understand benign overfitring in neural network models. However, they are still limited to the "neural tagent kernel regime" (lacol etall 2018) where the neural network learning problem is essentially equivalent to kernel regression. Thus, 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 highly nonconvex optimization problem. There- fore, while most of the previous works can study the minimum norm interpolators/maximum margin classifiers according to the implicit bias (Soudry et al, 20T8) results for the corresponding models, existing implicit bias results for neural networks (e.g., Lyu and Li (20T9) 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 -I's and polynomial ReLU activation function: (2) max (0. 233, where q > 2 is a hyperparameter. We consider a setting where the input data consist of label dependent signals and label independent noises, and uti- lize 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 ever-parameterized neural networks. We show that under certain conditions on the signal-to-noies to-noose ratio, CNN models trained by gradient descent will prioritize learning the signal over memorizing the noise, and thus achiev- ing 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 new proof technique namely signal-noise decomposition, which decom- poses the convolutional filters into a linear combination initial filters, the signal vectors and the noise vectors. We convert the neural network learning into discrete dynamical system of the coefficients from the decomposition. and perform a two-stage analysis that decouples the com- plicated relation among the coefficients. This enables us 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 concurrent work (Erei et all 2022) studies learning Dog-Concave mixture data with label flip noise using fully-connected two-layer neural networks with smoothed leaky ReLU activa- tion. Notably, their risk bound matches the risk bound for linear models given etal (2(21) when the label flip noise is zero. However, their analysis only focuses upper bounding the risk, and cannot demonstrate the phase transition between benign and harmful overfitting. Compared with (Frei et all 2022), we focus CNNs, and consider different data model to better capture the nature of image classification problems. Morcover, we present both positive and negative results under different SNR regimes, and demonstrate sharp phase transition between benign and harmful overfitting.
Given two sequences [In) and [un), ), we denote a.n O(y,) if there exist some ab- solute constant C1 > O and N > such that [rn S Cilyn for all n 2 N. Similarly, we denote In ((x)) if there exist C2 > 0 and N > 0 such that [x,| 2 O2lyn for all > N. We say
Notation.

---

In = if zf = (y.) and In = l()x)) both holds. We use Ö(-), $2(.), and ( to hide loga- rithmic factors in these notations respectively. Moreover, we denote 2n = poly(y.) if z, O for some positive constant D. and Fa polylog(Un) if zn poly(log(u))) Finally, for two scalars a and b, we denote a V = max (ax b).
2 Related Work
line of recent works have attempted to understand why overfitted predictors can still achieve a good test performance. Belkın et all (MM)) first empirically demonstrated that in many machine learning models such as random Fourier features, decision trees and ensemble methods the popula- tion risk curve has double descent shape with respect to the number of model parameters. Belknn at (2019)) 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. Bartlen et (20220 studied wver-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. Hastre et all (2019); Ww and Xu (2020) studied linear regression in the setting where both the dimension and sample size grow together with fixed ratio, and showed double descent of the risk with respect to this ratio. Chattery and Long (2121T 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-parametent mal population risk. Cao all (202T) tightened the upper bound given by Chatterji and Long (2020) in the case without the label flipping noises, and established matching lower bound of the risk achieved by aver-parameterized maximum margin interpolators. Shamm (2122) proposed a generic data model for benign overfitting of linear predictors, and studied different problem settings under which benign overfitting can or cannot occur.
linear models to achieve nearly opti-
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 al. (20117) first pointed out that overfitting kernel predictors can sometimes still achieve good population risk. Liang Rakhlin (2020) studied how interpolating kernel regression with radial basis function (RBF) ker- nels (and variants) can generalize and how the spectrum of the data covariance matrix affects the
population risk of the interpolating kernel predictor. D al (2021) studied the benign overfitting phenomenon of random feature models defined as two-layer neural networks whose first layer param- eters are fixed at random initialization. Me and Montanar (20T)) Liao al (2022) demonstrated the double descent phenomenon for the population risk of interpolating random feature predictors with respect to the ratio between the dimensions the random feature and the data input. Adlam and
Pennington (2022) shows that neural tangent kernel (lacot et all (01X) based kernel regression has a triple descent risk curve with respect to the total number of trainable parameters. Montanan and Zhong (20200 further pointed out interesting phase transition of the generalization error achieved by neural networks trained in the neural tangent kernel regime.
3 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 D in the following definition.
Definition 3.1. Let μ E Rdd be a fixed vector representing the signal contained in each data point. Then each data point (x, 3) with x = (XT x x( E R22d and E {-1,1} is generated from the following distribution D:
1. The label y is generated as a Rademacher random variable.
A noise vector & is generated from the Gaussian distribution N N 02 (I- -pppp T 11
3. One of (1) (2) is randomly selected and then assigned as y pt, which represents the signal: the other is then given by E. which represents noises.
3

---

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 is the signal patch that is correlated to the label of the data, and the patch assigned as & is the noise patch that 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 NN o3 (1- -1lull2 2) to ensure that the noise vector is orthogonal to the signal vector for simplicity. Note that when the dimension d is large, || l2 s ap d by standard concentration bounds. Therefore, we can treat ||all2//0p = || ||2l2//1| l2 the signal-to-noise ratio (SNR). For the ease of discussion, denote SNR || v Note that the Bayes risk for learning our model is zero. We can also add label flip noise similar to Chattern and Long (2020); Frei et all (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 classifier learns the signal μa and utilizes the signal patch of the data to make predic- tion, it can perfectly fit a given training data set {(x: v1) : E [n]] and at the same time have good performance on the test data. However, when the dimension d is large (d >> n1), classifier that is function of the noises É.. i E [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 B is useful model to study the population loss of overfitted classifiers. Similar models have been studied in some recent works by el (2019); Allen-Zhu and Li (2020alb); Zou et all (202E)).
Two-layer CNNs. We consider a two-layer convolutional neural network whose filters are applied to the two patches x2) and (2) separately, and the second layer parameters of the network are fixed as +1 +1/m and - -1/m respectively. Then the network can be written as J(W, x) (W1(W++.X F-1(W- (W,,, x), where F+1 x1. F1FF--WW11111 are defined as:
F,(W,,X] x) m Elo((
1
(w,,,,,. x ()) + o x ((
m (o((Wor))) 11)) + ((w,,,))))
YIR r=1
for j E (+1,-1}. Here, m is the number of convolutional filters in F+1 and F-I, o(=) (max(0, is the ReLU activation function where q > 2, W,r E Rd denotes the weight for the r-th filter (i.e., neuron), and W, is the collection of model weights associated with Fj. We also use W to denote the collection of all model weights. We note that our CNN model can also be viewed CNN with average global pooling etll 2013). We train the above CNN model by minimizing the empirical cross-entropy loss function
L.s(W) = 1 Σ Clu J(W, x,)],
where {(=) = log(1 + (xxp(==)), and S = {(x,, 11) }) is the training data set. We further define the true loss (test loss) LD W) := Exxx))>Df(l f(W.x)]
We consider gradient descent starting from Gaussian initialization, where each entry of W+1 and W_, is sampled from a Gaussian distribution N oB), and of is the variance. The gradient descent update of the filters in the CNN can be written as
(1+1)
w (t)
Jor 17 Vw5,. L.(sW)))))
jur
(t)
20 d' (W E.)
juLE:
7
g(t) o' d'((w ((w)f)...44) v.14)) ip (3.1)
nm
nm
for j E (+1} and r E [m]), where we introduce a shorthand notation
(/(0 = e'Vv f(W(),
4 Main Results
In this section, we present our main theoretical results. At the core of our analyses and results is signal-noise decomposition of the filters in the CNN trained by gradient descent. By the gradient descent update rule (B.JI), it is clear that the gradient descent iterate w is a linear combination of its random initialization Warr the signal vector and the noise vectors in the training data &..
(t)
i E [n). Motivated by this observation, we introduce the following definition.

---

Definition 4.1. Let j.r for
for E {+13, E [m]] be the convolution filters of the CNN at the 1-th (t)
(0) iteration of gradient descent. Then there exist unique coefficients Yo 2 0 and Pjay such that
n
[ j.r = w // + + (0) 1111122 p + Σ
jurs 116i1122 E.
We further denote (10) J.n. == p 1 ( jrr, 2 0), S..r3 = (0)
gr [ S 0). Then we have that
(1) W J.r
w (0)
Jir + jj || p Pana 115:112 5.7 + Σ 2 116:112
2 E:- (4.1)
We refer to (8 as the signal-noise decomposition of w j.r We add normalization factors
(t)
jirt E:). In this decomposition, (()) (1) characterizes the progress of learning the signal vector μe, and P.. characterizes the degree of Tj.r
(1)) || ||E.112 in the definition so that 33.r (w/ pi), Parrt =e (w!
noise memorization by the filter. Evidently, based on this decomposition, for some iteration (i)
some of (f)-s are large enough while l are relatively small, then the CNN will have small
(t)ss training and test losses; (ii) If some Pj.r,' 's are large and all Ti.r s are small, then the CNN will
achieve small training loss, but a large test loss. Thus, Definition I. provides handle for to study the convergence 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 vn, learning rate 1,, initialization scale
Condition 4.2. Suppose that
1. Dimension d is sufficiently large: d = 2144/2244422 (1(22g2)/1e-22)
Training sample size n. and neural network width m satisfy n, m (polylog(d)).
3. The learning rate satisfies 1 S O'minn|llalll [opp
The standard deviation of Gaussian initialization on is appropriately chosen such that ((nd-1/2) min((o,vd)) [|ll
o S O(m 2/(4-2) -n/01 -1/(4-2
few remarks on Condition 2 are in order. The condition on d is ensure that the learning is in sufficiently over- over-paranee parameterized setting, and similar conditions have been made in the study of learning over-parameterized linear models (Chatterji and Long. 2020; Cao et all 202T). For example, if we choose = 3, then the condition on d becomes d = ((mmn=)) Furthermore, we require the sample size and neural network width to be least polylogarithiic in the dimension to ensure some statistical properties of the training data and weight initialization to hold with probability at least d=1, which is mild condition. Finally, the conditions do and 7 are to ensure that gradient descent can effectively minimize the training loss, and they depend on the scale of the training data points. When op = ((d and |||||| = =O()), the step size can be chosen as large as Ō(1) and the initialization do can be as large as 0(m-2/(e 22(0-2)) -(1//-2) (1](e-)))v In our paper, we only require m, n = ((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. For any > 0, let T 00 (g- (1-2) 1 + m1l111))))) Under Condition E.2 n- SNR" = (1))), then with probability at least d=1, there exists 0 S t ts T such that:
The CNN learns the signal: max, //5 = for (+1).
The CNN does not memorize the noises in the training data: max 1p Ö(aua,Vd).
"Here the (2(-) hides polylog(e factor. This applies Theorem B well.
5

---

3. The training loss converges to i.e. Ls (s(W(()) S
4. The trained CNN achieves small test loss: Lo Lo((())) S 6e exp(-n²))
Theorem characterizes the case of signal learning. It shows that, n. afn-SMi TN-S = 11), then at least (e)
one CNN filter can learn the signal by achieving 7j.r; 22(), and as 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. For any > 0, let T ( m n(o,va) on (9-2) + c
Under Condition F.A if SNR 9 (1)), then with probability at least 1 - d_1, there exists 0 S t & T such that:
The CNN memorizes noises in the training data: max, 711)
(1)))
The CNN does not sufficiently learn the signal: maxg,r Tz - (00llpa122)
3.
The training loss converges to e, i.e., Ls Ls(((t)) S.
The trained CNN has a constant order test loss: Lo
0(1)
Theorem 9 holds under the condition that n n=!
SNR (1). Clearly, this is the opposite regime (up to some logarithmic factors) compared with The- orem E
Benign Overfitting n (SNR) = 52(1)
In this case, the CNN trained by gradi-
Sample Size n
ent descent mainly memorizes noises in the training data and does not learn enough signal. This, together with the results in Theorem R.3. reveals a clear phase transition between signal learning and noise memo- rization in CNN training:
In = (1), then the CNN learns the signal and achieves O exp(-n²)) test loss. This is the regime of benign overfitting.
-1 -SN-)S 2(1)
Harmful Overfitting
If 11 SNR - 5i(1) then the CNN can only memorize noises and will have a O(1) test loss. This is the regime of harmful overfitting.
SNK ||xlla
gov Figure 1: Illustration of the phase transi- tion between benign and harmful overfitting. The blue region represents the setting under which the overfitted CNN trained by gradi- ent descent is guaranteed to have small popu- lation loss, and the yellow region represents the setting under which the population loss is guaranteed to be of constant order. The slim gray band region is the setting where the pop- ulation loss not well characterized.
The phase transition is illustrated in Figure II Clearly, n SNR = ái( is the precise condition under which benign overfitting occurs. Remarkably, in this case the population loss decreases exponen- tially with the sample size n. Under our condition that n = ((polylog(d)) this term can also be upper bounded by 1 1/poly(d). which small in the high- dimensional setting. Note that when || (11)
and op (dd-122, applying standard uniform con- vergence based bounds (Bartlett et all 2017; Neyshabur et al,, 2018) or stability based bounds (Hardi
et 2016 Mou et all, 2017: Chen et all 2013) typically give O(n-1/2) bounds on the general- Oppolylog(d)) Our bound under the same setting is
ization gap. which are vacuous when
O(1/polydd)) which is non-vacuous. This is attributed to our precise analysis of signal learning
and noise memorization in Theorems 4 and E
Comparison with neural tangent kernel (NTK) results. We want 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- parapaaaamtteeeedd neural network to achieve good training and test accuracies (lacot ct al, 2018: Du all 20196 Allen-Zhu et all, 2019: Zou et all 2019% Arora it all 2019a: Cao and Gu, 2019;; Chen et all 2019). However, that the NTK analyses cannot fully explain the success of deep learning, the neural networks in the NTK regime are almost "linearized" (Lee et all 2019 Cao and GiI, 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.c., [W(() ( O(1), so that the NN model
widely believed literature

---

can be approximated by its linearization (Allen-Zhu ct all 2019;; Cao and GiT, 2019; Chen at 2019). In comparison, our analysis does not rely on linearizing the neural network function, and [[(s) || can be as large as O(poly(m)).
5 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 challenging task. The first chal- lenge is the nonconvexity of the training objective function Ls( (W). Nonconvexity has introduced new challenges in the study of benign overfitting particularly because our goal is not only to show the convergence the training loss, but also to study the population loss the over-parameterized setting, which requires precise algorithmic analysis of the learning problem.
5.1 Iterative Analysis of the Signal-Noise Decomposition
In order to study the learning process based the nonconvex optimization problem, we propose key technique which enables the iterative analysis of the coefficients in the signal-noise decomposi- tion in Definition I. This technique is given in the following lemma.
(1) Lemma 5.1. The coefficients Tirr Pjr,ss Jaz
in Definition satisfy the following equations:
(0) (0)
0
(0)
0,
(5.1)
jr
3,r 15.r
(1+1) (t)
(t)
o'((w
j.m 14) |1a4122
(t)
(5.2)
THT
( = -jjra
(1)
11
(0) o' d'w( 3.rt
(1)
E() 11::122 ( = j),
(5.3)
Tm
( 5000
(0) ((w (0) j.rt Ei) 112.112 1() -)).
(5.4)
Remark 5.2. With the decomposition (. the signal learning and noise memorization processes
((t) g(t),, based the dynam- a CNN can be formally studied by analyzing the dynamics of Virr _j.r,
ical system (5)2)) (5.4). Note that prior to our work, several existing results have utilized the inner
products (w" i.r pa) during the neural network training process in order to establish generalization bounds (Brutzkus et all 2018 Chatterji and Long, 2020: Erei all 202T). Similar inner product based arguments are also implemented in Allen Zhu and Li (20200 B) Zou et all (20221), which study different topics related learning neural networks. Compared with the inner product based argument, our method has two major advantages: (i) Based on the definition (5.2)-(5 and the fact (t) P are monotonically increasing, while g,0)) is monotonically jjrr
(e)
that (:0)) < 0, it is clear that Ti
decreasing throughout the whole training process. In comparison, monotonicity does not hold the inner product hased argument, especially for (w (t) enables a clean homogeneity-but
j.s Es)- (ii) Our signal-nois noise decomposition also proof for the convergence of the training loss to an arbitrarily
small error rate >> O, which will be presented in Subsection 5.2
With Lemma 5. can reduce the study of the CNN learning process to the analysis of the discrete dynamical system given by (5..))((5.4)... Our proof then focuses on a careful assessment of the values
of the coefficients 7/.r Pjr.ir
(() c.(t) Lj.r. throughout training. To prepare for more detailed analyses, we
first present the following bounds of the coefficients, which hold throughout training.
Proposition 5.3. Under Condition 2.A for any T - |/ - oo 2 2000000000 n, m,d).
the following bounds hold t [0, T
1. S Tim Pjrj < <4log(T*) for all (+1), r E [ml] and E [r]].
(t) (e)
2 (t) 2 -2 mamx ((w (0)
k),, (w (0)
j.r Ed) 16n /oan/boatgggg 1oo((nn/00) 4loggT")) for all j
(+1), r E [m] and i E [n].

---

We can then prove the following lemma, which demonstrates that the training objective function (s( can dominate the gradient norm ||VLs(W(()) F along the gradient descent path.
Lemma 5.4. Under Condition 2 for any T 17- - poly(e ,11a1122 , oo" 1 n,, m, d), the
following result holds for E J::
IVL ( )| 0( max (1 -s((
Lemma be plays key role in the convergence proof of training loss function. However, note that our study of benign overfitting requires carefully monitoring the changes of the coefficients
in the signal-noise decomposition, which cannot be directly done by Lemma b.4 This is quite
(t) (2)
challenging task, due to the complicated interactions among 7j.r Pj.r. and Lj..."" Note that even
"'p Pji.'' and Pi for j' {=1}, r' [m] and [n]]. This is because the cross-entropy loss derivative term (0 = Ely f(W(), xx)] depends on all the neurons of the network. To overcome this challenge, we introduce in the next subsection decoupling technique based on two-stage analysis.
I, which has the simplest formula (5.2), depends on all the quantities (1) P/
(e)
5.2 Decoupling with Two-Stage Analysis.
We utilize two-stage analysis to decouple the complicated relation among the coefficients 7/00 p(t) and Lj,nt' Intuitively, the initial neural network weights are small enough so that the neural network at initialization has constant level cross-entropy loss derivatives on all the training data: (10) f' f(W(O), xx)] ((1) for all [n]. This is guaranteed under Condition tny and matches neural network training in practice. Motivated by this, we can consider the first stage of the training process where e,(0) ((1), in which case we can show significant scale differences among (()) (t)
Fj
Tj.r Pj.r. and oiah Based on the result in the first stage, we then proceed to the second stage of the training process where the loss derivatives are longer at constant level and show that the training loss can be optimized to be arbitrarily small and meanwhile, the scale differences shown in the first learning stage remain the same throughout the training process. In the following, we focus on explaining the key proof steps for Theorem R. The proof idea for Theorem 4 is similar, so we defer the details to the appendix.
Stage 1. It can be shown that, until some of the coefficients (t)
Ti.r Pjra reach @(1), we have (10 [' (IW(1) (1), xx) = 0(1) for all i E [n). Therefore, we first focus on this first stage of the training process, where the dynamics of the coefficients in (6.2) - (b.44) be greatly simplified by replacing
(c)
the (())) factors by their constant upper and lower bounds. The following lemma summarizes our main conclusion stage 1 for signal learning:
Lemma 5.5. Under the same conditions as Theorem there exists Ti = Ö(n 'mo² 1||111 such that
1. max, 7j
(Tr) for j {+1).
2. j O(aoop dd) for all E {+1}, r E [m], i E [n] and 0 S T..
Lemmas 5.5 takes advantage of the training period when the loss function derivatives remain constant order to show that the CNN can capture the signal. At the end of stage 1 in signal learning, (t) max, 7/. reaches (1)), and is significantly larger than Pj.r.a- After this, it is longer guaranteed
that the loss derivatives ((0)) will remain constant order, and thus starts the training stage 2.
Stage In this stage, we take into full consideration the exact definition e:(0 E'(y. f(W(), x,) and show that the training loss function will converge to Ls (W(()) < c. Thanks to the analysis in (t)
(t) stage 1, we know that some 7 is significantly larger than all j.. 's at the end of stage 1. This scale difference is the key to our analysis in stage 2. Based on this scale difference and the monotonicity (1)
of T/mr Pjrra ((0) in the signal-noise decomposition, it can be shown that there exists W such
that y: (W)(W()) xx). W*) 2 q log(29/e) throughout stage 2. Moreover, since the neural network
8

---

f(W,x) gs g-homogeneous in W, we have (Vf(W(), x)), W = - f(W() x). Therefore,
(Vss(Wi)), w W R
xi), - -W-
y q f(w()) ,x) yi (V/(W()) x.), W (1)
fwu S(W x.)l Iue S(W")) xi) 1og(24/e))
q (e(S xx)) e(oog(2/())
29 9- (w
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.
Lemma 5.6. Let T, be defined in Theorem 3 and Lemma S..5 respectively. Then under the same
conditions as Theorem H.d for any E [Tr,),, holds that |p S ao for all j {+1), r E [m] and E [r]]. Moreover, let W be the collection of CNN parumeters with convolution filters (4/e)
(0) wir w j.r 2qm log (og((4//])
||aa|122 μ.. Then the following bound holds
Σ Ls(())) - I W 1| -
- Ti +
(2g - 1)m(t - 7i + 1)
(2q - 1)
for all t [Ti,]) T), where we denote W +1 11
Lemma 5.6 states two main results signal learning. First of all, during this training period, it guaranteed that the coefficients of noise vectors Dj.r. the signal-noise decomposition remain sufficiently small. Moreover, it also gives an optimization type result that the best iterate in [Ti, T] is small as long as T' is large enough. Clearly, the convergence of the training loss stated in Theo- rems E. directly follows by choosing to be sufficiently large in Lemmas 5.6. The lemma below further gives upper bound on the test loss.
Lemma 5.7. Let T be defined in Theorem B.1 Under the same conditions as Theorem for Jny any t x T with L.5 (W(()) < 1, holds that (W()) < 6 Lg( (W()) + exp(-n²).
Below finalize the proof of Theorem The proof's of other results are in the appendix.
Proof of Theorem 1 The first part of Theorem follows by Lemma and the monotonicity of
(t) The second part of Theorem k follows by Lemma 5.A. For the third part, let W be defned
T5.
in Lemma 5.R. Then by the definition of W we have
[T()) - W < (T)) ( | + || W
(T))
(T)
|
+ +m
||E:ll2
ju
J.r.
j.n.
Ömm 3/2 |
where the first inequality is by triangle inequality, the second inequality is by the signal-noise de- composition of W(T) and the definition of W and the last equality is by Proposition 5.3 and
Lemma 5 Therefore, choosing
0(n--T; -T + n le "=-'mmlllall Ô(1 top (q- |1|2
1 -1e m m 2 in Lemma 5.6 ensures that
T
Ls (s(w())) < [W(] 1 e <
(m |1123
Σ
e
+
2q - <
T-T++ FiT+ +1
(2g 1) - +1+1) 24 - (2g 1)n(T - Ti + +

---

and there exists t E [Ti,T] T] such that Ls(W()) S This completes the proof of the third part of Theorem 9.3 Finally, combining this bound with Lemma 5.7 gives
Lo(w()) 1 L.sssWW)) + exp(-nt n²) & 6 + exp(-n²),
which proves the last part Theorem
6 Conclusion and Future Work
This paper utilizes signal-noise decomposition to study the signal learning and noise memorization process in the training a two-layer CNN. We precisely give the conditions under which the CNN will mainly focus on learning signals or memorizing noises, and reveals 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.
Acknowledgments and Disclosure of Funding
We would like to thank Spencer Frei for valuable comment and discussion on the earlier version of this paper, and pointing out related work. 7C and QG are supported in part by the National Science Foundation CAREER Award 1906169, IIS-2008981 and the Sloan Research Fellowship. MB is grateful for the support from the National Science Foundation (NSF) and the Simons Foundation for the Collaboration on the Theoretical Foundations Deep Learning through awards DMS-2031883 and #8 1884939 as well as NSF IIS 18-1881155 1815697 and the TILOS institute (NSF CCF-2112665).
References
ADLAM, B. and PENNINGTON, J. (2020). The neural tangent kernel high dimensions: Triple descent and multi-scale theory of generalization. In International Conference on Machine Learn- ing. PMLR.
ALLEN-ZHU, Z. and LI, Y. (2020a). Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005.10190.
ALLEN-ZHU, Z. and LI, Y. (2020b). Towards understanding ensemble, knowledge distillation and self-distillation in deep learning, arXiv preprint arXiv:2012.09816
ALLEN-ZHU, Z., LI, Y. and LIANG, Y. (2019a). Learning and generalization in overparameter-
ized neural networks, going beyond two layers. In Advances Neural Information Processing Systems.
ALLEN-ZHU, Z., LI, Y. and SONG, Z. (2019b). A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning.
ARORA, S., Du, S., HU, LI, Z. and WANG, R. (2019a). Fine-grained analysis of optimization and generalization for overparameterizeed two-layer neural networks, In International Conference on Machine Learning.
ARORA, S., DU, S. S., HU, W., LI, Z., SALAKHUTDINOV, R. and WANG, R. (2019b). On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems.
ARORA, S., GE, R., NEYSHABUR, B. and ZHANG, Y. (2018). Stronger generalization bounds for deep nets via a compression approach. International Conference on Machine Learning.
BARTLETT, P. L., FOSTER, D. and TELGARSKY, M. (2017). Spectrally margin bounds for neural networks. In Advances in Neural Information Processing Systems.
httpp://deeppoualattooos..lll
10

---

BARTLETT, P. L., LONG, P. M., LUGOSI, G. and TSIGLER, A. (2020). Benign overfitting in linear regression. Proceedings of the National Academy of Sciences.
BELKIN, M., HSU, D., MA, S. and MANDAL, S. (2019a). Reconciling modern machine-learning practice and the classical bias variance trade-off. Proceedings of the National Academy of Sci- ences 116 33849-18544
BELKIN, M., Hsu. D. and Xu, J. (2019b). Two models of double descent for weak features. arXiv preprint 19033 190300970........
BELKIN, M., MA, S. and MANDAL, S. (2018). To understand deep learning we need to understand kernel learning. In International Conference Machine Learning.
BOUSQUET, O. and ELISSEEFF, A. (2002). Stability and generalization. Journal of machine learn- ing research 2 499-526.
BRUTZKUS, A., GLOBERSON, A., MALACH, E. and SHALEV-SHWARTE S. (2018). Sgd learns over-parameterized networks that provably generalize on linearly separable data. In International Conference Learning Representations.
CAO, Y. and GU, Q. (2019a). Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems.
CAo. Y. and GU, Q. (2019b). Tight sample complexity of learning hidden-layee convolutional neural networks. Advances in Neural Information Processing Systems.
CAO, Y., GU, Q. and BELKIN, M. (2021), Risk bounds for over-parameterized maximum margin classification on sub gaussiasninn mixtures. Advances in Neural Information Processing Systems 34.
CHATTERJI, N. S, and LONG, P. M. (2020). Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. arXiv preprint
12019.
CHEN, Y., JIN, C. and Yu, (2018), Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint 1804.0166
CHEN, Z., CAO, Y., Zou, D. and Gu, Q. (2019). How much over-parameetrrzzaioon is sufficient to learn deep relu networks? arXiv preprint 1x1iv:1911.12366
DENG, L. (2012). The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine 29 141-142.
DU, S., LEE, J., LI, H., WANG, L. and ZHAI, X. (2019a). Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning.
DU, S. S., LEE, J. D. and TIAN, (2018a). When is convolutional filter easy learn? In International Conference on Learning Representations.
DU, S. S., LEE, J. D., TIAN, Y., SINGH, A. and Poczos, B. (2018b). Gradient descent learns one-hidden-layer CNN: Dont afraid of spurious local minima. International Conference on Machine Learning.
DU, S. S., ZHAI, X., Poczos, B. and SINGH, A. (2019h). Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations.
FREI, S., CAO, Y. and GU, Q. (2021). Provable generalization of sgd-trained neural networks of any width in the presence of adversarial label noise. International Conference on Machine Learning. PMLR.
FREI, S., CHATTERII, N. S. and BARTLETT, P. L. (2022). Benign overfitting without linear- ity: Neural network classifiers trained by gradient descent for noisy linear data. arXiv preprint arXiv:2202.05928.
GOLOWICH, N., RAKHLIN, A. and SHAMIR, O. (2018). Size-independent sample complexity of neural networks. In Conference On Learning Theory.

---

HARDT, M., RECHT, B. and SINGER, Y. (2016). Train faster, generalize better: stability of stochas- tic gradient descent. In Proceedings of the 33rd International Conference on International Con- ference Machine Learning- Volume 48. JMLR. org.
HASTIE, T., MONTANARI, A., ROSSET, S. and TIBSHIRANI, R. J. (2019). Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08566
JACOT, A., GABRIEL, F. and HONGLER, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems.
J1, Z. and TELGARSKY, M. (2020). Polylogaritmmic width suffices for gradient descent achieve arbitrarily small test error with shallow relu networks. In International Conference on Learning Representations.
LEE. J., XIAO, L., SCHOENHOLZ, S. S., BAHRI, Y., SOHL-DICKSTEIN, and PENNINGTON, J. (2019). Wide neural networks of any depth evolve linear models under gradient descent. In Advances in Neural Information Processing Systems.
LI, Y. and LIANG, Y. (2018). Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems.
LI, Y., WEI, C. and MA. T. (2019). Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in Neurul Information Prucessing Systems.
LI, Y. and YUAN, Y. (2017). Convergence analysis of wwo-layer neural networks with relu activation. In Advances Neural Information Processing Systems.
LI, Z., ZHOU, Z. and GRETTON, A. (2021). Towards an understanding of benign overfitting in neural networks. arXiv preprint arXiv:2106.032/1
LIANG, T. and RAKIILIN, A. (2020). Just interpolate: Kernel ridgeless regression can generalize. The Annals of Statistics 48 1329-1347.
LIAO, Z., COUILLET, R. and MAHONEY, M. (2020). A random matrix analysis of random fourier features: beyond the gaussian kemel, precise phase transition, and the corresponding double descent. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020).
LIN, M., CHEN, Q. and YAN, S. (2013). Network in network. arXiv preprint arXiv:1312.44 1312.4400
LYU, K. and LI, J. (2019). Gradient descent maximizes the margin homogeneous neural net- works. arXiv preprint 19t.:199000890
MEI, S. and MONTANARI, A. (2019). The generalization error of random features regression:
Precise asymptotics and double descent curve. arXiv preprint arXiv:1908.05335.
MONTANARI, A. and ZHONG, Y. (2020). The interpolation phase transition in neural networks:
Memorization and generalization under lazy training. arXiv preprint 1xXi::0077.12800
Mou, W., WANG, L., ZHAI, X. and ZHENG, K. (2017). Generalization bounds of sgid for non- convex learning: Two theoretical viewpoints. arXiv preprint arXiv:1707.05947.
NEYSHABUR, B., BHOTANAPALLI, S., McALLESTER, D. and SREBRO, N. (2018). A pac- bayesian approach to spectrally-normalizedd margin bounds for neural networks. In International Conference on Learning Representation.
NEYSHABUR, B., LI, Z., BHOJANAPALLI, S., LECUN, Y. and SREBRO, N. (2019). Towards un- derstanding the role of pverpparametiizaiionn in generalization of neural networks. In International Conference on Learning Representations.
NEYSHABUR, B., TOMIOKA, R. and SREBRO, N. (2015). Norm-based capacity control in neural networks. In Conference on Learning Theory.
SHAMIR, O. (2022). The implicit bias of benign overfitting. arXiv preprint 21X.v:2001.11489.
12

---

SOLTANOLKOTABI, M. (2017). Learning ReLUs via gradient descent. In Advances in Neural Information Processing Systems.
SOUDRY, D., HOFFER, E., NACSON, M. S., GUNASEKAR, and SREBRO, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research 19 2822-2878.
WU, D. and Xu, J. (2020). On the optimal weighted l regularization in overparameterized linear regression. Advances in Neural Information Processing Systems 33.
ZHANG, C., BENGIO, S., HARDT, M., RECHT, B. and VINYALS, O. (2017). Understanding deep learning requires rethinking generalization. In International Conference on Learning Representa- fions.
ZHANG, X., YU, Y.. WANG, L. and Gu, Q. (2019). Learning mee-hidden-layer ReLU networks via gradient descent. In The 22nd International Conference on Artificial Intelligence and Statistics.
ZHONG, K., SONG, Z., JAIN, P., BARTLETT, P. L. and DHILLON, I. S. (2017). Recovery guaran- tees for one- one-hidden layer neural networks. In International Conference on Machine Learning.
ZoU, D., CAO, Y., LI, Y. and GU, Q. (2021a), Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint arXiv:2108 113011
ZOU, D., CAO, Y., ZHOU, D. and Gu, Q. (2019). Gradient descent optimizes over parametteede deep ReLU networks. Machine Learning.
Zou, D., WU, J., BRAVERMAN, V., GU, Q. and KAKADE, S. (2021b). Benign overfitting of constant-stepsize sgd for linear regression. In Conference Learning Theory. PMLR.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] This is the first work that precisely characterizes the conditions under which benign overfitting can occur in training convolutional neural
networks
(b) Did you describe the limitations of your work? [Yes] As have discussed in the conclusion, we only analysis two-layer CNNs. It's important to generalize our analysis deep convolutional neural networks.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This paper focuses on theoretical analyses of neural network training, and does not have any direct negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Please check the appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] The purpose of experiments in this paper to back up our theoretical findings. The error bars are not required to verify our theory.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The purpose of experiments in this paper is to back up our theoretical findings. Information about the computation resources are irrelevant our purpose.
4. If you using existing assets (c.g., code, data, models) curating/releasing assets...
13

---

(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/eurating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if
applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "boOPAnW_q6n", "reviewer": "Reviewer_AJsJ", "summary": "This manuscript analyses the benign overfitting phenomenon for deep neural networks. In detail, the authors decompose the signal information and the noise during the training process and derive the corresponding convergence result according to the signal-to-noise-ratio (SNR). According to the theorems, with smaller SNR, the noise will be dropped and the harmful overfitting converts to benign overfitting.", "questions": "Please see Weaknesses.", "limitations": "Please see Weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n- This manuscript deeply investigates benign overfitting and clearly show the transition boundary between harmful overfitting and benign overfitting;\n\n- The signal-noise decomposition is novel and can promote analysis in deep learning theory;\n\n- The paper is well-writting and easy to follow.\n\nCons:\n\nThis paper comprehensively analyse the phase transition of benign overftting via SNR. However, there are two major points that can undermine the contributions of the paper: (1) Lack of ancillary experiments. The results are fully theoretical and rely on many assumptions (Condition 4.2) and Figure 1 is the schematic diagram according to theoretical results. If there are some empirical study based on real models and datasets, the conclusion will be more convincing; (2) Strong assumptions. The paper relys on many assumptions on dimiension, sample size, parameter size, etc. I recommend the authors to apply the assumtions to real empirical situation and show how the assumptions close to the real scenarios.\n\nSome minor writing suggestions:\n- Line 23: \"the the classical\" $\\rightarrow$ \"the classical\";\n- Line 128: \"signal-to-noise ratio\"should be followed by the abbr. SNR for better understandingl;\n- Line 201: \"that$n^{-1}$\" $\\rightarrow$ \"that $n^{-1}$\";\n- Line 211: \",$n$SNR\" $\\rightarrow$ \", $n$SRN\";\n\nThe reason for socre: Though the paper lacks empircal study, I appreciate for its solid theoretical analysis on the transition boundary between harmful and benigh overfitting. The transion boundary will be an important prespective to understand the success of neural nets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "aQJnbHKbdv9", "reviewer": "Reviewer_sf8Q", "summary": "Paper studies the benign overfitting phenomenon in training a two-layer convolutional neural network (CNN).\nAuthors show that when the signal-to-noise ratio satisfies a certain condition, a two-layer CNN trained by gradient descent can achieve arbitrarily small training and test loss. Otherwise, overfitting becomes harmful and the obtained CNN can only achieve constant level test loss. \nThen paper shows a sharp phase transition between benign overfitting and harmful overfitting, driven by the signal-to-noise ratio.", "questions": "It would be nice to have some hint to a general property of benign overfitting.\nHow much do you think this result is general and holds for a wider class of function?", "limitations": "Some practical example would improved the quality of the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- intriguing property\n- experiments convincing\n\nWeaknesses\n- theoretical analysis is very technical and hard to follow\n- some practical example would improved the paper", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JV4nGE_8YQ", "reviewer": "Reviewer_UZNG", "summary": "The paper studies the training dynamics and generalization behavior of GD on two-layer CNNs. In particular, it proves that when the signal-to noise ratio is large enough, GD can achieve small training and test loss; otherwise, the test loss may be large and bad overfitting occurs. Together, it shows a phase transition between benign and harmful overfitting.\n", "questions": "If the position of the signal is not fixed, or if the signal and noise is not separable in the CNN model, will the result keep the same?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The studied problem is important in understanding the generalization power of neural networks, and the result is relatively complete for the phase transition demonstrated. The technical analysis of the GD dynamics looks solid, and the decomposition approach may potentially be applied to other settings.\n\nI have some questions in the setting of the studied problem. In Definition 3.1, the data point is composed of $x_1$ and $x_2$ representing signal and noise, separately. In this definition, the position of the signal is either $x_1$ or $x_2$, indicating that it is fixed in one of the two positions. Moreover, in the expression of CNN (Line 140), $x_1$ and $x_2$ seems to be separable, so the signal and noise seems to be separable in the setting. I am not quite sure whether this is reasonable in practice, as the position of signal usually varies (for example, the “signal” of an image may be in any corner of the image).\n\nAnother minor issue: In Section 3, the subscript of $x$ refer to both the category of signal or noise (with subscript 1, 2) and the index of data (with subscript 1, …, n). This may cause confusion.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0EiCYi_uOGe", "reviewer": "Reviewer_s7mX", "summary": "This paper characterizes when a convolutional neural network with a certain architecture and on a certain data model generalizes well while fitting the data perfectly. The analysis uses a signal-to-noise (SNR) ratio and shows that harmful overfitting can be avoided with a small sample size if SNR is large enough.", "questions": "See weaknesses section", "limitations": "See weaknesses section", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper attempts at an important problem and analyzes the performance of a neural network without approximating it with a convex linear model. I have not check the proofs in the appendix but the math in the main paper is correct and well explained. The two step approach in the analysis might have applications beyond the current problem. Nevertheless I am leaning towards rejection since this machinery relies on the following restrictive assumptions on both the data and the network:\n\n1. The images have a noise patch and a signal patch. Each feature corresponds to either signal or noise through the dataset unlike a real dataset where the signal can be anywhere in the image. The label in the studied data model is a fixed vector $\\mu$ for the positive class and $-\\mu$ for the negative class and the noise patch is a multi-dimensional Gaussian r.v., while in a typical dataset signal and noise are entwined. Does this theory extend to a more realistic data model e.g. by replacing $\\mu$ and $-\\mu$ with the mean of feature vectors in the positive and negative class?\n\n2. In the equation below line 140 it appears that the network's first layer processes the signal and noise separately, that is, it applies the filter on the first patch and then strides to the second patch and applies the filter on it. This large value of stride does not represent any common CNN architecture. A typical CNN would slide over the image in more fine-grained steps.\n\n3. The second layers weights are initialized to $\\pm 1$ and are assumed to be constant through the training. The hidden layer activation is polynomial ReLU with degree at least 2.\n\n4. An important motivation for this work is that removing the large hidden layer width assumption in NTK. The analysis in the submission, however, still requires an overparametrization assumption (Condition 4.2). From the omega notation in the main paper it is not clear how restrictive this requirement is and how large the input and hidden layer width need to be for the results to hold.\n\nMinor comments:\n- In Line 305 the claim that small variations in loss across data points at the beginning of training matches the behavior of neural networks in practice needs citation. \n----------------------------------------------\nUpdate: Thanks for the response. The clarifications in the rebuttal and the discussion with reviewer UZNG answered my first comment. The added experiments also show a consistency between the trend shown by theory and the one that occurs in a realistic setting without any of the unrealistic assumptions.\n\nRegarding comment 4: My understanding is that large-width neural networks (at least some fully-connected ones) can be _well approximated_ with the NTK even if their width is finite. See theorem 3.2 in [1] for example. It is likely that under condition 4.2 one can directly analyze the NTK and then bound the difference between the behavior of a wide convolutional neural network and the NTK without the other assumptions.\n\nRegarding asymptotic notation: The omega notation is completely fine. I was only admitting that, due to the omega notation, I do not have a clear idea if Condition 4.2 makes the behavior of the network close to NTK or not.\n\n[1] Arora, Sanjeev, et al. \"On exact computation with an infinitely wide neural net.\" NeurIPS 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept