Rethinking Benign Overfitting in Two-Layer Neural Networks
Authors: Ruichen Xu
Kexin Chen
Venue: ICML 2025 poster (2025)
Keywords: Benign overfitting
long-tailed data
two-layer neural networks
Primary area: deep_learning->theory
TL;DR: We re-examine benign overfitting in two-layer neural networks and prove that while data can be classified by explicit features, long-tailed data can also be classified base on implicit features learned from class-dependent noise.

Abstract: Recent theoretical studies (Kou et al., 2023; Cao et al., 2022) revealed a sharp phase transition from benign to harmful overfitting when the
noise-to-feature ratio exceeds a threshold—a situation common in long-tailed data distributions where atypical data is prevalent. However, such harmful overfitting rarely happens in overparameterized neural networks. Further experimental results suggested that memorization is necessary for achieving near-optimal generalization error in long-tailed data distributions (Feldman & Zhang, 2020). We argue that this discrepancy between theoretical predictions and empirical observations arises because previous feature-noise data models overlook the heterogeneous nature of noise across different data classes. In this paper, we refine the feature-noise data model by incorporating class-dependent heterogeneous noise and re-examine the overfitting phenomenon in neural networks. Through a comprehensive analysis of the training dynamics, we establish test loss bounds for the refined model. Our findings reveal that neural networks can leverage "data noise" to learn implicit features that improve the classification accuracy for long-tailed data. Our analysis also provides a training-free metric for evaluating data influence on test performance. Experimental validation on both synthetic and real-world datasets supports our theoretical results.

Rethinking Benign Overfitting in Two-Layer Neural Networks
Ruichen Xu
Kexin Chen
Abstract
over weer-pramettrizze neural networks, models can perfectly fit the training data while still exhibiting improved general- ization as model complexity increases. When and why this benign overfitting phenomenon happens garnered signifi- cant interest within the learning theory community, Recent works, e.g., Frei et al. (2022); Cao et al. (2022); Kou et al. (2023), showed sharp phase transition between benign and harmful overfitting in two-layer neural networks with feature-noise data model (Allen-Zhu Li, 2020), which assumes data is composed of a feature vector as its mean and random Gaussian vector its data-specific noise. Specifically, when the magnitude of the noise exceeds threshold, neural networks memorize the data noise, lead- ing to harmful overfitting. Nevertheless, such harmful overfitting is rarely observed in modern over-parameterizee neural networks.
Recent theoretical studies (Kou al., 2023; Cao et al., 2022) revealed a sharp phase transition from benign to harmful overfitting when the noise-to-feature ratio exceeds threshold-a sit- uation common in long-tailed data distributions where atypical data prevalent. However, such harmful overfitting rarely happens in overparam- eterized neural networks. Further experimen- tal results suggested that memorization is nec- essary for achieving near-optimal generalization error in long-tailed data distributions (Feldman & Zhang, 2020). We argue that this discrepancy be- tween theoretical predictions and empirical ob- servations arises because previous feature-noiss data models overlook the heterogeneous nature of noise across different data classes. In this pa- per, we refine the feature-noise data model by in- corporating
Empirical evidence (Feldman & Zhang, 2020; Hartley & Tsaftaris, 2022; Wang al., 2024; Garg & Roy, 2023) in- dicates that memorization tion, especially in long-tailed data distributions character- ized by substantial data-specific noise. These findings con- tradict current theories of the phase transition to harmful overfitting. Consequently, the following problem remains open:
heterogeneous noise and re-examine the overfitting phenomenon in neural networks. Through a comprehensive anal- ysis of the training dynamics, we establish test loss bounds for the refined model. Our findings reveal that neural networks can leverage "data noise" to learn implicit features that improve the classification accuracy for long-tailed data. Our analysis also provides a training-fre free metric for evaluating data influence on test performance. Experimental validation on both synthetic and real-world datasets supports our theoretical re- sults.
in fact, enhance generaliza-
How can we theoretically explain benign overfitting in overparumeterized neural networks?
Inspired by the heterogeneous intra-class distributions in real-world datasets (as shown in Figure 1), we refine the Prature-noise data model by incorporating class-dependent noise and re-examine the benign overfitting phenomenon in two-layer ReLU convolutional neural networks (CNNs). In this paper, we make the following contributions:
1. Introduction
Overfitting, also known memorization, had long been considered detrimental to model generalization perfor- mance (Hastic et al., 2009). However, with the advent of
We establish an enhanced feature-noise model by con- sidering heterogeneous noise across classes. Our re- sults with this model theoretically explain how mem- orization of long-tat toigetailed data boosts model perfor- mance, which cannot be predicted by existing theo- retical frameworks for neural networks.
'Department of Information Engineering, The Chinese Uni- versity of Hong Kong. Hong Kong, China "School of Science and Engineering, The Chinese University Hong Kong, Shenzhen, China. Correspondence to: Ruichen Xu <rcxu642 @ gmail.com com..
We derive general theoretical phase transition results between benign and harmful overfitting by analyzing the test error bounds of the refined model. Our results demonstrate that although the trained neural networks
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
can classify data through explicit features, they can additionally utilize implicit features learned through memorization of class-dependent noise to classify long-tailed data. The findings are well-supported by real-world datasets. Our results also show a proba- bly counterintuitive result that a class's classification accuracy for long-tailed data may decrease with the dataset sizes of other classes, giving an explanation to the observations in Sagawa et al. (2020).
8
S
9
7
6
6
6
6
2
?
2
7
0
6
Figure 1. Left: Examples of MNIST long-tailed atypical data, which tend to be memorized by neural networks (Feldman & Zhang, 2020). Right: t-SNE visualization of MNIST. The hetero- geneous shapes imply real-world datasets, such as MNIST, prac- tically show heterogeneously correlated structures, providing ex- perimental evidence for our theory.
We derive new proof techniques to tackle the random- ness involved in feature learning. Unlike explicit fea- ture learning, which exhibits stable activation states and magnitudes, data noise has random activation states and magnitudes. Specifically, to tackle the ran- dom activation states, we explore the singular value distributions of neural networks to characterize the variability. Moreover, we demonstrate that the output strength of neurons randomly activated by data noise is influenced by intra-class covariance matrices.
research failed explain learning dynamics and general- ization performance in non-convex and non-smooth neural networks.
Our analysis provides a simple training-free metric for evaluating data memorization, unlike previous met- ries that rely training storing multiple models. The data with high scores on our metric correspond to visually atypical samples, which are memorized to benefit model generalization. aligning with Feldman & Zhang (2020); Garg & Roy (2023).
Another line of work theoretically studied memorization in neural networks by analyzing the feature learning pro- cess during training, providing analytical frameworks that extend beyond the neural tangent kernel (NTK) regime (Ja- cot et al., 2018; Allen-Zhu et al., 2019; Du et al., 2018). For example, Cao et al. (2022) and Kou et al. (2023) plored benign overfitting in two-layer neural networks us- ing the feature-noise data model with homogeneous data noise distributions and showed a sharp phase transition be- tween benign and harmful overfitting. However, they all assumed that the data-specific noise is homogeneous, lead- ing to the conclusion that it is harmful to memorize data- specific noise. They thus fail to explain the empirical ob- servations with long-tailed data.
1.1. Related Work
We review the topics of empirical observations and theoret- ical studies of memorization.
Empirical observations of memorization. A lot of re- cent empirical studies showed that memorization inevitably happens in modern aver-parameterized neural networks. For instance, Feldman& & Zhang (2020); Garg & Roy (2023) studied the memorization of training examples and found that neural networks tend to memorize visually atypical examples, i.e., those are rich in data-specific information. These observations motivate us study the impact of data- specific information on benign overfitting. Our results pro- vide theoretical justification for these empirical observa- tions in neural networks.
1.2. Notation
We lowercase letters, lowercase boldface letters, and uppercase boldface letters to denote scalars, vectors, and matrices, respectively. We use [m] to denote the set (1, ,m}. Given two sequences { and {gn), we de- note x, = (v.) if |z,1| S C1lyn1 for some positive con- stant C₁ and Hn = (yy,) if [am 2 C2lyn1| for some pos- itive constant C2.. We use In O(y,) if xn ((va) and x, = S(y,.) both hold. We use O(-), ( and (2-)) to hide the logarithmic factors in these notations. Given ma- trix A, we use || to denote its Frobenius norm, | to denote its operator norm, Tr(A) to denote its trace, > ) to denote its 7th largest singular value, (A) and X (A) ) to denote its maximum and minimum absolute values of non-zero singular values, and rank(A) to denote its rank. We use the notation (x, y) ~ D to denote that the data sample (x, y) generated from distribution D.
Theoretical analyses for memorization. A body of work theoretically examined memorization within classi- cal machine learning frameworks, demonstrating its sig- nificance for achieving near-optimal generalization perfor- mance across various contexts, including high-dimensional linear regression (Cheng et al., 2022), prediction models (Brown et al., 2021), and generalization on discrete distri- butions and mixture models (Feldman, 2020). This line of
2

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
2. Problem Setup
train the neural network by minimizing the empirical risk with the cross-entropy loss:
In this section, we introduce the problem setup, including the data model, CNNs, and the training algorithm.
Ls (W)
L(W, C(,
Given the evidence that real-world datasets have heteroge- neous class-dependent structures (as shown in Figure 1), we consider data distribution as follows.
71
where L(W, x, x) - loggigiit, (W, x)), and logit(-) represents the output probability of the neural network:
Data distribution. We define a data distribution 'D that each sample (x. y) is generated as
exp(F (W, x))
logit, (W,x)
k- exp(Px (W,
1. Sample the label y following distribution K, whose support is [K] (K = (()).
Initialization. The initial weights of the neural network's parameters are generated i... from Gaussian distribu- tion, i.c. wj.r (O aîI), for all j E [K], E [m]]
2. The data (x )x where x()), xx() ()) Rd con- tains either feature or class-dependen noise patch:
Feature patch: One patch is randomly selected as the feature patch, containing feature vector Uy E Rd.
Training algorithm. We train the neural network by gradient descent (GI) with learning rate 1/, i.e.,
Noise patch: The remaining patch is generated A,S. where each coordinate of Ç is i..dd drawn from De, a symmetric op = (11) sub-Gaussian distri- bution' with variance 1, and A, E IRdxd satisfies u Ay = 0, for any k E [K].
w(++) = -W() "
Σ vL(W"",,,y) (4) (x.Y)ES
3. Main Results
In this section, we present our main theoretical results. We start by introducing some conditions for our theory. Condition 3.1. Suppose there exists sufficiently large constant C. For certain probability parameter 8 E (0, the following conditions hold:
Without loss of generality, we assume that the feature vectors " uu are orthogonal and their norms are bounded, i.e. (u, u,) 0, /|lll ((1) for all i,j E [K] and i # j. Remark 2.1. The sub-Gaussian distribution of noise patches is general. In practice, pixel magnitudes in the clas- sification tasks are bounded and thus are uub-Gaussian.
(a)
To ensure that the neurons can learn the data patterns,, for any i,j [K], the noise patch distributions sat- isfy:
Learner model. We consider a two-layer CNN with ReLU activation as the learner model. Given an input x = (x(1), x( the model with weights W outputs a K-length vector [Fi.... FFR] whose elements are
Tr(AT 2 On max {|| A log(n?/0)
/2 3 (E]KTAAAAA, ATA, 1/2 Hog 1/2 (n? (/22/8/165/ /8)/
|AT A F ||AT A 2 Colog(K/0) (K/)), | A, 2 C-1 max + As A
( (Wh,r;((1)
(W, x)
(1)
Moreover, there exists threshold d' > such that IP[ç > c] 0.4.
2} denotes the ReLU activation function, and Wk.r denotes the weight vector for the yth neuron (totally neurons) associated with F2 x).
where (2)) 00
(b) To ensure that the learning problem is in sufficiently over wee-parameterized setting, the training dataset size n, network width m, and dimension d satisfy:
Training objective. Given training dataset with n sam- ples S = [xx, 9:) 1 drawn from the distribution D, we
2 C Clo((n/0) max, max: ((A (A.)) min (2, n 2 Cllo(mm/)) /0), m 2 Ω (log(n) (n/5) (TTTT//2nn] min(m, d, rank(A,)) 0.9m 2 Cn. d Clog(mm/66).
sub-Gaussian variable as sub- Gaussian variable with variance proxy a.
Here, we simply refer
"This condition ensures that the noise patch is orthogonal to the feature patch. Our data distribution includes the widely adopted feature-noise data distribution with homogeneous data noise (Cao et al., 2022; Zou al., 2023; Jelassi Li, 2022) as a special case. By setting K = 2 and A = 1 ΣX u.uu ||ug|| 212 for all k; y [K], our data distribution be- comes the same as theirs.
*Conditions (a) on the noise patches generalize the conditions on dimension d in Kou et al. (2023). Setting A+A = Σ kmm unuu / ||m for all ls E [K], Condition (a) is similar to the dimension condition Kou al. (2023).
3

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
To ensure that gradient descent can minimize the training loss, the learning rate y) and initialization do satisfy:
ing loss difference resulting from the removal of a spe- cific sample from the dataset. Garg & Roy (2023) de- fined the long-tailedness of data using a curvature met- ric that approximates loss Hessian matrix-related quan- tity of trained models averaged over all training epochs. In a similar manner, our definition leverages the trained model W(T) to map high-dimensional samples to a one- dimensional metric, allowing us to identify long- data points from the perspective of the network's learned repre- sentations.
-1 7 (imaxse(x) (IuAlle Sallll+t1/151 (A (A))s))
" mn log(T)/ ja( (Tr A5)}
ou sc-t
log(K (| Anllet)
where @ ==
AT, Ak. p. ll 122)
We denote S as the set containing training data with label in the training dataset S. We present our main result in the following theorem.
Based on Condition 3.1, we study the model convergence and generalization performance by bounding the training loss and the zero-one test loss (accuracy) of the trained model W(2) on distribution DR whose probability density function PD. [(x, y)] PDl(x, y)ly kt., i.c., for all l E [K].
Theorem 3.4. For any K]. under Condition 3.1, there exists T On mmxx(n (a A,)), vndoo.ymK)
> and k
with probability at least 1 - 8, the following holds:
C%. (W-((W(T))
The training loss satisfies: Ls Ls( (s((T))) SE.
2. Benign overfutinn:
1P (x)))D
Fy (W x) + max
x)]
je K
(a) (For all data) When the signal-to-noise ra-
tio is large, iee, |S&] 1
2 C1
Before presenting the main theorem, we define the set of long-tailed data with respect to the trained model WTT)
max |A] A, I the zero-one test loss satisfies:
Definition 3.2 (T--Long-tailed data set), The T--long-tailed data distribution Tj for each j E [K] with model (TT) is defined as
S 12
|ug
C% (8-((W())
Pry [xx, y)1
exp
-c
|
F
PD,
(x,x)K( Σ w(T),) 2 L|IAT Σ rER(E
signul-to-noise ratio
(ER(E)
(b) (Only for long- -ailed data) When the noise cor- relation ratio is large, Le. All Z
where R(E) (r [m] (Wy., E > 0}.
C2 max (15, || A the zero-one test loss satisfies:
Definition 3.2 identifies data whose equivalent noise ç' exceeds a threshold. Specifically, for data (x,y) D, the inner product term (ErERiE) w satis- fies (ETEREE) Wy. 4) = e (||TT ErER(E) w ()) where C' is an equivalent random sub-Gaussian variable with variance 1.
0-1 T
(W()))
(T)
S A A SS I
5 Σ exp j
L02L2.
AT A
Remark 3.3. Classical definitions of long-tailedness often hinge on simple one-dimensional statistics (such as Zipf distribution). However, such metries may fail to capture the nuances of high-dimensional data. For instance, for sub-Gaussie Gaussian data, norms alone cannot capture which sam- ples are "rare" or "hard" to learn due to concentration ef- fects. To address this, we draw inspiration from prior work that uses trained models to identify "long-tailed" samples. Specifically, Feldman & Zhang (2020) defined the long- tailed data using an influence score that quantifies the train-
noise correlation ratio T
3. Harmful overfitting: When the iignal-tonnois ra- tio and noise correlation ratio are small, i.e., | < C3 max # ||S A,,,, 12 and | Ax < C3 max f (S AT 11 the zero-one test loss satisfies Co -0-1( (W(T)) C3.
Here, C1, C2 C3. C12 022 C3 are some absolute constants.
4

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Noisc strength ||A, A, 1
classification accuracy of long-tailed data increases with the noise correlation ratio. This result implies that incor- porating more long-tailed data into the training dataset en- hances test accuracy, providing theoretical explanation for the empirical observation in Feldman & Zhang (2020) that including long-tailed data in the training dataset is nec- essary for neural networks to achieve near-optimal gener- alization performance.
Benign
Harmful
Increasing majority hurts minority. Statement 2(b) of Theorem 3.4 implies that as the dataset size of class j. [Sy] increases, the upper bound on test loss of other classes k + j increases. This leads to a possibly surprising result: The classification accuracy for long- taig-tailed data of a spe- cific class may decline when the sizes of other classes in- crease. The reason is that during training, the memorization of majority class-depended noise (classes with more data) dominates the memorization of minority class-dependent noise. Our result theoretically explains counter-intuitive observation in neural networks that subsampling the major- ity group empirically achieves low minority error (Sagawa et al., 2020).
Signal strength ||æ|l2
Figure 2. Illustration of the generalized phased transition between benign and harmful overfitting (memorization). The blue region represents benign overfitting regime where the test loss is small. The orange region represents a harmful overfitting regime where the test loss is constant order. The gray band region is the setting where the test loss is not well characterized.
Theorem 3.4 characterizes sharp phase transition be- tween benign and harmful overfitting (memorization), vi- sualized Figure As per Theorem 3.4, after T itera- tions, CNNs converge to nearly optimal training loss (State- ment 1). When the tggnal-to-ooise ratio is high, the trained CNNs can achieve optimal test loss by effectively detecting explicit features Uı (Statement 2(a)). This result extends the previous benign overfitting results, which characterize the horizontal dimension in Figure 2. Furthermore, CNNs also classify long-tailed data by seeking to detect features learned from class-dependent noise so that the performance benefits from high noise correlation ratios (Statement 2(b)). This result at the first time characterizes the vertical dimen- sion in Figure 2, showing that the model can also leverage the noise patch to achieve benign overfitting. Conversely, when both noise correlation ratios and signal-to-noise ra- tios are small, the trained CNNs incur test loss at least a constant (Statement 3). Notably, longer-tailed data (with larger L) benefits more from the class-dependent noise patch.
4. Proof Overview
In this section, we present a proof sketch of Statement and Statement 2(b) in Theorem 3.4 (Statement 2(a) uses similar but simpler proof). Due to the space limit, we defer the complete proofs to Appendices A, B, and C.
4.1. Proof Sketch of Statement 1 in Theorem 3.4
We analyze the training loss in two stages. In training Stage I, the training loss of each example decreases exponentially and stays at a constant order ((1). Stage 2, the model converges
arbitrarily small constant.
Stage 1. decreases exponentially, characterized by the following lemma.
By the nature of cross-entropy, the training loss
I ΣK / / for all j E [K], our Statement 2(a) recovers the same convergence orders in the standard benign overfitting results (Kou et al., 2023). However, our results are more general as our results cover the whole class of sub-Gaussian data noise, K > number of classes, and data imbalance, which is common in modern image classification tasks.
Remark 3.5. By choosing A,A]
Lemma 4.1. Under Condition 3.1, there exists an iteration number To 0(mn/1) /1), so that for any (x, y) E Sand < To, the following holds:
((W(++1)
.x,
(5)
$ (1 (11-
S (1)))))) L (WW))x,)))
mn
The results of Theorem 3.4 theoretically explain the fol- lowing two empirical observations in neural networks for the first time.
Stage 2. We show that the training loss converges to an arbitrarily small constant at a rate of O(L/T).
Lemma 4.2. Let W be the network parameters with each
Long-tailed (atypical) data is important for generaliza- tion. In Statement 2(b) of Theorem 3.4, we show that the
neuron w), = 2.5 (4(K - 1)/e) u,/ ||uy Under Condition 3.1, I, for any E [To, T) and (x, y) S, the
5

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
sollowing result holds:
Irained model W satisfies:
W W E
1 1- To +1
Cs(W(()) s
Σ I
(T) (w (. 0.1m.
(6)
17l To + 1) 2
Lemma 4.4 indicates that, with high probability, at least non-negligible amount of neurons are able detect the noise patch of the test data.
After T =
[ [Tr(A] A2));
Vmdoo, VmK}) iterations, the training loss converges to Our analysis extends that of Kou et al. (2023)* by provid- ing the convergence rate for Stage I and a comprehensive convergence analysis for K-class classification problems using cross-entropy loss.
Next, we quantify the activation magnitude of the correlation coefficients
and (?)) ,)) In the following lemma, we Σr=1 ((w) j.r prove that the neurons for class j [K] mainly learn the data noise patch from class j.
4.2. Proof Sketch of Statement 2(b) in Theorem 3.4
By the definition of zero-one test loss, for any long-tailed data v) E Ti i [K], its test loss satisfies:
Lemma 4.5. Under Condition 3.1, for any j E [K], [K], (xx) Wy) E Sj,, (Xa, Na) E St, existing a suffi- ciently large constant C² > 0, we have:
F7.1 (W()) S Σ
m
$$
Σ (o(()) (.w.PP.s)) 220)2 C' Σ ((w ((WW)) Ea)). jar
(7)
77
P(x.u)7T Σ
4) 9.7.
Σ ((
(2') j. to (( j.r: (.rr)))) E))
(2)
As a result, the order of activation magnitudes is controlled by the intra-class correlations and inter-class correlations, quantified by ||A AylIF F and ||A A,l|F.
Roughly speaking, since the neurons for a class do not learn
explicit features of other classes, i.e., 1 ((w j.r ug)) is small for j * y, the key to quantifying the test loss is
Lemma 4.6. Under Condition 3.1, for any (x. ~ To and E [K].] E [K]M(V), the following holds:
to compare the correlation coefficients E ((w (T) p.r E))
and Σ ((w j.r
(T) 3)
Σ
(T) (T) 5 = mmm ||A A IM(s)) Mir
First, we need to quantify the number of neurons that can be activated by the random noise patch g. We leverage the properties of the rank and singular values of the neu- rons corresponding to each class j E [K]. i.c., w!?)-
Σ
(w(?)
Jor E) = ( 1pm
(T)
| 1 (( b(8))K.))
o
(w(T) 211
(T) in the following lemma. j.m
where b(-) is a function defined as:
Lemma 4.3. Under condition 1,1, the matrix w for all j E [K] satisfies:
2 Σ (1 logit, ( (W()),)) (8)
b(AA) = V
Σ
rank W (T) Aj) > 0.9m,
(X.))EA
X1 (W,) Amin (ann((m,..onx(,A))))))
A2) < O ( log (T))
and Ç1 is a uub-Gaussian variable with variance 1.
(T) (w) A,) 2 0.1 /mo
Finally, to compare b(S,,) and b(S,), we prove that the loss gradient coefficients are balanced.
With Lemma 4.3, we can prove that the probability that (WF..) E) remains in an orthant decreases exponentially with the number of neurons m. Consequently, we derive the following lemma for the number of activated neurons.
Lemma 4.7. For all E [T] and for any i,j E [n], there exists a positive constant ks such that:
1 logit, (W()) x;)
Lemma 4.4. Under condition for any j E [K] and any (x, y) ~ Dj. with probability at least 1 - exp( [(m)), the
1 logit (W()) X²) S k.
"Kou et al. (2023) provided convergence analysis for train- ing loss in two-layer CNNs with binary classification and logistic loss.
Leveraging Hoeffding's inequality, Lemma 4.6, and 4.7, we derive Statement 2(b) in Theorem 3.4.
6

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
1400
accuracy
1.0
1400
Test
1200
1200
09
Noise cozrvatiion ratio T
Noise corrlation zabio
1000
1000
0.7
900
0.6
2.6
400
200
200
03
0.3
1.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Fasture strength ||u||
Fesatue sirength ||ul|z
(a) Test accuracy heatmap under Gaussian data noise. Each entry (b) Test accuracy heatmap under uniform data noise. Each entry of of follows (0, 1).
Ç follows (3, v3).
Figure 3. Impacts of fcature strength and noise correlation ratio on test accuracy.
Test accumey
Test accurncy
200
0.9
0.8
150
150
0.
Delasel size
125
Dataget size
125
100
0.5
75
0.4
50
03
50
25
02
1.0
1.5
2.0
2.5
3.0
3,5
300
400
500
600
700
800
Feuture strengrh [ulla
Noise corrolation ratio
(a) Test accuracy heatmap with feature strength and dataset size. (b) Test accuracy heatmap with noise correlation ratio and dataset Each entry of follows (0, 1).
size. Each entry of follows (00, 1).
Figure 4. Impacts of data size on test accuracy.
5. Experiments
accordingly.
In this section, first validate theory in Theorem 3.4 by constructing datasets and models following our problem setup in Section 2. We further verify our conclusions with real-world datasets MNIST (LeCun et al., 1998), CIFAR- 10, and CIFAR-100 (Krizhevsky et al., 2009).
Setup. We train a two-layer neural network as defined in Section with m = 100 neurons. We use the default ini- tialization method in PyTorch initialize the neurons' pa- rameters. We train the neural networks using GD with learning rate y 0.05 over 20 epochs. To explore the effects of feature strength ||u:|la- noise correlation ratio Pig. and dataset size [S), we simply fix ||uil|2 ||u||
5.1. Synthetic Datasets
T& = T, and |S,| = s, where ||u|| I, and are tunable parameters for all class i, [K] ().
Synthetic data generation. We generate a synthetic dataset following the data distribution outlined in Section The dataset comprises total of K 5 classes with dimensionality of d 1000. We set the feature patches for each E [K] u; U |u Zg. where Z keeps the Rthh entry to be one and other entries zeros, and U is randomly generated unitary matrix. Without loss of gener- ality, we consider A to be matrices with all but one non- zero eigenvalue fixed as 0.5. Then, we tune the non-fixed non-zero eigenvalue change the noise correlation ratio
Effects of noise correlation and feature strength. We simulate with feature strength ||u||| ranging from 0.001 to 3.8 and noise correlation ratio I' ranging from 1 to 1400. We fix the dataset size of each class as |S,| 100, for all E [K]. The resulting heatmap of test accuracy in rela- tion to data feature size and noise correlation is presented in Figure 3. As illustrated, the loss decreases not only with increasing feature strength but also with higher noise

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Influence score
2
3
3
2
2
3
3
Digit
Digit 3
Plane
Cat
Figure 5. Visualization of images with different influence scores.
correlation ratios. Notably, with high noise correlation ra- tios, neural networks can achieve near-optimal test accu- racy even when feature strength approaches nearly zero.
1900C
INE
1901
TWH-
1500C
41D0C
Effect of dataset size. We verify the impact of the dataset sizes in the two types of benign overfitting in Statements 2(a) and 2(b) of Theorem 3.4. We fix the noise correlation ratio as r 1.2 with following Gaussian distribution and vary the feature size ranging from 0.01 to 4 and dataset size ranging from 10 to 200 to explore the effect of dataset size versus feature strength on test accuracy (Figure 4a). We fix the feature strength as ||u||2 = le and tune noise correlation ratio (with following Gaussian dis- tribution) ranging from 1 to 800 and dataset size ranging from 10 to 200 to explore the effect of dataset size versus noise correlation ratio (Figure 4b). These results verify our theory. Specifically, for classification utilizing explicit fea- tures (Figure 4a), the test accuracy increases with increas- ing dataset size, matching our Statement 2(a) in Theorem 3.4. contrast, for classification utilizing implicit features (Figure 4b), the accuracy remains in constant order with the dataset size, matching Statement 2(b) in Theorem 3.4.
1200
4
7948
MSW
40M1
PATE
1000C
6-
1501
3553
8000
7.40
351
3119
679
11 90-
3971
9141
R154
2234
Digits
Figure Visualization of squared Frohenius norm among classes in MNIST.
have large noise correlation ratios, satisfying the conditions for long-tailed data benign overfitting predicted in our the- ory (Statement 2(b) of Theorem 3.4).
5.2. Real-World Datasets
Data influence score. We quantify the impact single data sample (x, y) by measuring its impact on || Ag (A determining factor of the long-tailed data loss as in Statement 2(b) of Theorem 3.4). We observe that A.J A,yIF is, in fact, the same as the Frobenius norm of the covariance matrix of class y's distribution and hence we consider an influence of image (x, y) E S as:
We verify the effects of noise correlation MNIST (Le- Cun et al., 1998), CIFAR-10, 10, and CIFAR-100 (Krizhevsky et al., 2009).
Noise correlation ratio verifications. To verify our re- sults in Theorem 3.4, we compute the squared Frobenius norm, i.e., ||A A among different classes of MNIST. We provide the computation details Appendix As shown in Figure 6, real datasets such MNIST indeed
infi(x)) ((S,)) |
(10)
8

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
ple training-free metric for evaluating data influence on test performance. Experiments both synthetic and real- world datasets further validate our theory.
1.0
0.9
0.8
Test necuracy
Impact Statement
0.7
Benign overfitting one of the most fundamental phe- nomena for neural networks. Our work discovers new mechanism of benign overfitting, providing new insights not only theoretical studies but also on improving train- ing pipelines, such as designing data collections to achieve desired properties. Additionally, we proposed training- free metric to evaluate the influence of data on test perfor- mance.
0.6
MNIST nenone
0.5
CLAA 10 scueve liga
oemove low
0.4
renove bigl.
CIFAR 100 nunve kew
0.0
0.1
0.2
0,3
0,4
0.5
0.6
0.7
0.8
Remeval percenlage
Figure 7. Effect on the test accuracy of removing fraction of ex- amples with high and low influence scores.
References
Allen-Zhu, Z. and Li, Y. Towards understanding ensem- ble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.09816, 2020.
where (S, denotes the estimated covariance of the un- derlying data distribution within the dataset Sy,"'
What influence scores indicate. We visualize the data with high and low influence scores in Figure 5. The data with high influence scores are atypical data, which can be interpreted by scrawly written digits and hard-to-oe hard-to-classify objects in the experimental datasets.
Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over pverpparamtteiization.. In Interna- tional conference on machine learning. 2019.
Brown, G., Bun, M., Feldman, V., Smith, A., and Talwar, K. When is memorization of irrelevant training data nec- essary for high-accuracy learning? In ACM SIGACT symposium on theory of computing, 2021.
Inspiration from influence scores. We sort the data from MNIST, CIFAR- 10, and CIFAR-I00 100 based on the influence score defined in Eq. (10). In Figure 7, remove a por- tion of data with high and low influence scores and train the remaining data on LeNet (LeCun et al., 1998), ResNet- 18, and ResNet-101 (He et al., 2016) to assess their impact on model accuracy. We observe that the accuracy drop of removing data with high influence scores is significantly larger than that of removing data with low influence scores. This observation verifies our theory (Statement 2(b) in The- orem 3.4) that reducing the squared Frobenius norm sig- nificantly hurts the model's test performance as it reduces accuracy on long-tailed data.
Cao, Y., Chen, Z., Belkin, M., and Gu, Q. Benign overfit- ting in two-layer convolutional neural networks. In Ad- vances in neural information processing systems, 2022.
Cheng, C., Duchi, J., and Kuditipudi, R. Memorize to gen- eralize: the necessity of interpolation in high dimen- sional linear regression. In Conference on Learning The- ory, 2022.
Damian, A., Ma, T., and Lee, J. D. Label noise sgd prov- ably prefers flat global minimizers. In Advances in Neu- ral Information Processing Systems, 2021.
6. Conclusions
In this paper, we re-examine the overfitting phenomenon in overparameterized neural networks. Specifically, enhance the widely used feature-noise data model by in- corporating heterogeneous noise across classes. Our find- ings reveal that neural networks can learn implicit fea- tures from class-dependent noise and leverage these fea- tures to enhance classification accuracy long-tailed data distributions. These findings align with the practical ob- servations that memorization enhance generalization performance. Furthermore, our analysis provides sim-
Du, S., Zhai, X., Poezos, B., and Singh, Gradient de- scent provably optimizes over-parameterizeed neural net- works. arXiv preprint arXiv:1810.02054,, 2018.
Feldman, V. Does learning require memorization? short tale about a long tail. ACM SIGACT Symposium on Theory of Computing, 2020.
Feldman, V. and Zhang, C. What neural networks mem- orize and why: Discovering the long tail via influence estimation. In Advances in Neural Information Process- ing Systems, 2020.
'ee estimate the covariance matrix using the sample covari- ance matrix.

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Frei, S., Chatterji, N. S., and Bartlett, P. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference Learning Theory, 2022.
Wang, W. Kaleem, M. A., Dziedzic, A., Backes, M., Pa- pernot, N., and Boenisch, F. Memorization in self- supervised learning improves downstream generaliza- tion. In International Conference on Learning Repre- sentations, 2024.
Garg, I. and Roy, K. Memorization through the lens of cur- vature of loss function around samples. arXiv preprint arXivv2307.05881, 2023.
Xie, S. and Li, Z. Implicit bias of adamw: -nom strained optimization. In International Conference Machine Learning, 2024.
HaoChen, J. Z., Wei, C.,, Lee, J., and Ma, T. Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, 2021.
Zou, D., Cao, Y., Li, Y., and Gu, Q. The benefits of mixup for feature learning. arXiv preprint arXiv:2303 2303:33303.8433, 08433, 2023.
Hartley, J. and Tsaftaris, S. A. Measuring unintended mem- orisation of unique private features in neural networks. arXiv preprint arXiv:2202.08009 2022.
Hastie, T., Tibshirani, R., Friedman, J. H., and Friedman, J. H. The elements of statistical learning: data mining, inference, and prediction. Springer, 2009.
He, K. Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In IEEE conference on com- puter vision and pattern recognition, 2016.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent ker- nel: Convergence and generalization in neural networks. In Advances in neural information processing systems, 2018.
Jelassi, S. and Li, Y. Towards understanding how momen- tum improves generalization in deep learning. Inter- national Conference on Machine Learning, 2022.
Kou, Y., Chen, 7., Chen, Y., and Gu, Q. Benign overfit- ting in two-layer relu convolutional neural networks. International Conference on Machine Learning, 2023.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Pro- ceedings of the IEEE, 1998.
Sagawa, S., Raghunathan, A., Koh, P. W., and Liang, P. An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning. 2020.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on sepa- rable data. Journal of Machine Learning Research, 2018.
Vershynin, R. tion with applications in data science. 2018.
probability: An introduc-
10

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
A. Additional Related Work
Implicit bias in neural networks. line studies found that training algorithms of neural networks prefer solutions with certain properties, such as flatness (Damian et al., 2021), sparsity (HaoChen et al., 2021), max margin (Soudry al., 2018), and bounded &oo norm (Xie & Li, 2024), leading better generalization. In contrast, this paper focuses on studying the training dynamics, which detailedly characterizes how neural networks learn features to boost generalization.
B. Key lemmas
In this section, we present some important lemmas that illustrate the key properties of the data and neural networks. Lemma B.1. Let Z E Rmx" (m > n) be a matrix whose entries are independent and identically distributed Gaussian variables, Le., Z ~ NNO, 1) for all E J E [n]. With probability at least - 6, all singular values of Z, (Z), for all E [n] satisfies
( (Z) m 2 8 logg { + 8log(9)n.
(11)
Lemma B.1 follows from the concentration inequality of Gaussian random matrices (Vershynin, 2018). Lemma B.2. For random oy mub-Gaussien variable "1, En with probability 1 6, have
f2
F||æ| 2 $ S exx
(12)
20
Proof. Based on the definition of nub-Gaussian distribution, with probability - 8/n, we have
2n
[as| 2 V 20 logl
(13)
By Union bound, we finishes the proof.
Lemma B.3. Suppose two zero-mean random vectors x,y E Rdd are generated as x = AC1, = AA where S each coordinate is independent, symmetric, and o, sub-Gaussian with B B[( = L, for any i E [2],] E [d]. Then, x and y satisfy
2exp ( min
t
t |ATA| A up 1)
(14)
AATAI2 P
Proof. We have
(x,y) = (AC1: AC2) ATATAc, SUUTUUG = ATA = Tr (AC=ČI)
(15)
As ? and 2 are isotropic, by Bernstein's incquality, we have
t2 |
P Tr (AC2ši) 2 <2exp -Ω min
(16)
2 of |
A
o
op
Lemma B.4. Suppose a zero-mean random vector x RRd generated as x AÇ, where Ç's each coordinate independent, symmetric, and op Sabb-anssian with E [<?] for any j [d] Then, x satisfies
P P1Ix122 - - (ATAA)) <2exp
-Ω
min
t2 |
t
(17)
A of
A
A
up

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Proof. We have
|x||
= = Tr (ATACiCT)
(18)
Then, expectation of ||x|| satisfies
E |x|| 2
IT (ATA).
(19)
By Bernstein's inequality, have
t2 [|ATA|| A of
P x Tr (A 2t
22exp
-Ω
min
(20)
Lemma B.5. Suppose two zero-mean random vectors X1, X2 T&d are generated as x1 A BC where Si's each coordinate is independent, symmetric, and op sub-Gaussian with E[GEj] for any E [2], [d]. Then, xi and X2 satisfy
P (2) <2exp
-Ω min
(21)
||TBI|
|A B up
Proof. We have
(x,y) = (ASI, BG2) = AC,
= TY (A (A BC2GT)
(22)
Then, by Bernstein's inequality, we have
[|] (x1, x2) 2 =|= Tr A (BC 21
(-1)
||AT|| - of | of 1)
t2
(23)
<2exp
min
Lemma B.6. Let 01." i.e., for all E [m]]
Fm Fm
be m independent zero-mean Gaussian variables. Denote 2; as indicators for signs of Di.
3; 0, 0,
1,
2;
(24)
T4 0.
Then, we have
(- 8
Pr Σ
2 0.4m
2 1 exx
m
(25)
25
Proof. Because 24 í E [m]] are bounded in [0, 1). 24, E [m]] are sub-Gaussian variables. By Hoeffding's inequality, we have
1
-e)
-c)]
( 2m22
Pr
m
m71
24
S m
2
< exp
m(1166)
(26)
Let é = 0.1, we have
m
(-
8
Pr
Σ
23
< 0.4m
S Sexp
(-2
(27)
12

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Therefore, have
(-
8
Pr
Σ A=
2
0.4m
2 2 exp
(28)
25
This completes the proof.
Lemma B.7. For any constant t (0, and [-a, al > 0. have
log(1 + t(cxp(x:) 1)) [(x)a,
(29)
where [(x) I[x 2 0) + [Iog(1 + ((exp(-a) 1))/ aj 0).
Proof. First, considering x 2 0, we have
Olog(1 + t(exp(x) - 1)) exp(x) -
1+ t(exp(x) - 1) 2 0.
(30)
Thus, log (1 + t(exp(x) 1)) & x, Vz > Second, considering O, we have
8 log(1 + t(cxp(x) - 1))
(1 - (i-)
[] + t(exp(x) - 1)}² 2 0.
(31)
dx²
So log(11 + ((exp(x)) - 1)) is a convex function of x. We can conclude that
log(1 + ((ex((x) 1)) log(1 + t(exp(-o) 1)) N, Vx O.
(32)
-a
This completes the proof.
Lemma B.8. With input E R the function f(x) log(exp(x:)/ ) exp(x;)) with any i E [K] is convex.
Proof. For any X1 E R and a E [0, 1]. we have
exp(x1,1)
exp(1225)
af(x)) + (1 fxx()x) a log
-(1 - (1) a) log
ΣjE[K] exp(21.5)
ΣjE(K] exp(122))
1-a
cxp(21,1)
cxp(12,5) Σ (E(K] exp(122)
-
log
EjelK] exp(x1s)
exp(axr1;)
exp((1 - a)x2)1)
log
JE(K] exp(1115))
Σ ]E[K] exp((22))) 1)
(33)
exp(ox1,5
log
E JE(K) exp(11,)) ( (Σ{E[K] expl (I2,)))
explar1, (1 a) a))
2 - log
Σje(k) exp(ax1. + (1 42222))
=f(axı + +(1 - a)xx).
This finishes the proof.
Lemma B.9. A vector z uniformly sampled from Sd-1 satisfies
d
1
P
II
(2))
2
t
< exp (-2dt²).
(34)
d
2
13

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
This lemma directly follows from Hoeffding's ss inequality.
Lemma B.10. For constant < t < 1, a op Sub-Gaussian variable I with variance 1 satisfies
||
>
f 2 2((1 -)))).
(35)
Proof. Since x is sub-Gaussian variable with variance we have E[a] = 1. Applying Paley-Zygmunt inequality to x², have
Piz 2 t
t)²
(36)
E[x-]
As the fourth moment of sub-Gaussian variable [[xx"] is bounded by O(og)) (Vershynin, 2018), we have
C4
PP 2
t
(1- -)
(37)
p
where C4 is a constant. This completes the proof.
Lemma B.11 Let A Ruxn be matrix with rank M. Suppose 8
0 and
((log(n/0)(X)))) (X (a))) (A)) random sau-Gaussian vector with each coordinate follows DE, we have
(A))))). With probability 1 5, for any orthant T E I and vector R
P [Ax TI 5(0.6)
(38)
Proof. Using singular value decomposition for A, for any orthant T E IR" we have
P [[Ax T| =P 7].
(39)
Without loss of generality, we assume the orthant T is that with all positive entries. Then, we have
P|Ax E T SP [ E TT]
(40)
where
1 1//m
U²
Üm}
(41)
and
X
max (A)
0
0
0
min
(A)
0
(42)
0
0
x (A)
Here, E is generated by replacing the non-zero singular values other than the largest one with > (A). 1 vector with all one entries. In the following, abbreviate Xttux (A) and A (A) A and A+ for convenience. Then, we have
M
UΣx
1 21 + A
Σ
U
(43)
max
Vm
1=2
Here, as each coordinate of x is generate from De. by Lemma B.2, we have
2n
|>g| 5
v 2 log
(44)
14

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
with probability 6. Then, we have
P
ÜUE
T|
=PP
(X
) 1
Vm
21
+
X
min
2 Ü,
ET
M
IP
A max
20 log
+ A
min
2. U, ET
(45)
/m
20 log (0ggg2n/o) / ))>
P
x min x XET
ET
m
As the entries of x are independent, ((log(n/0)AAme. (²/x/ we have
we
can
bound
each
entry independently.
Then, when
m
V 20 log (2m / (6) max
min +
< 2 0.4,
(46)
m
by the property of De, resulting in
PP [ E T| 5(0.6)M.
(47)
This completes the proof.
Lemma B.12. Let A E Rmax be matrix with rank M. Suppose [(log(m//0((tttx(()))))) probability 1 - 6, we have
With
P
Σ T((Ax); $ 0) 2 0.9m
S <cxp(-0.07m)
(48)
Proof. By Lemma B.9, the number N, of orthants that have more than 0.9m negative entries satisfies
No 2 exp((0.32m) exp( 2 0.32)m).
(49)
Then, by Lemma B11,, we have
m
P
I(xx)); 50) 2 0.9m
$0.6 exx((1ogg 2 0.32)m)
(50)
ex)((og(0.6)M + (log 2 0.32)m)
I <cxp(-0.51M) 0.38m).
As long as M 2 0.9m, we have
[(Ax);; 5) 2 0.9m
< (-0.07m).
(51)
This completes the proof.
Lemma B.13. Suppose that and (T((AAA))= max {1IAT [[]ATA|122 of log((n/8))) 1/2 |AT A of logg(6n/))) }}
For all i,j E [K], with probability 8, we have
3
Tr(A v. Ag..) < 11 2
Ir
(52)
((..E.)) 50 max {
(IAT
6n 1/2 -
6n
))
12 log(
.IIAT, Aus log(
(53)
15

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Proof. By Lemma B.4, with probability at least
8/33,, there exists constant C₁ such that
12 - A,, max {1AJ, 1: PC log( ))
1/2 A Av. op CC
6n log(
8
and
|| 112 Tr(AA. A.) max (IATA le o o/C log( Gin )
1/2
6n log(
.IIAT Av. op o pr 8
In addition, by Lemmas B.5 and B.3, with probability at least 1 - 8/3n², there exists a constant C2 > such that
S max {IATA 1| pC, log(
6n² b
))
1/2
6n log(
1| Av, 1lpp of
Applying op = (1) finishes the proof.
Lemma B.14. Suppose that d = (((og(mn/8)) and (2log((/66) With probability at least 1 1- 1. for all r E [m], [2), E [n].
(w (0) un)) S 2
4Kmm || 0o.
{
(54)
(w j.r: E.) S o log
(0)
Km
| 1F 00
(55)
Proof. We prove the first bound (54) with Hoeffding's inequality. For all j [K], E [m], [n], with probability 1 - 6/(2Km),
4Km 8
ut)l $
2
| oo.
(56)
j.r
Then, we prove the second bound (55) leveraging Lemma B.5. For all j [K], e [m]. [n]. with probability
1 - 62K2mm)
||A llop 000 200)
Km
Km
Kw j.r:
G.)l
50
max
log
A pelll,logg
5
(57)
Km
50
log
||A 1l 50
8
Lemma B.15. Suppose 8 and m 2 ((log(n/5)). With probability at least 1 5, we have
S 00) 2 0.4m.
(58)
Lemma 1.15 follows from Lemma B.6 and union bound.
Lemma B.16. Suppose 8 and 2 2(log(m/5)) For any neuron w [2], [m]] with probability at least 1 6, we have
I((w Jart E.) 2 0.4n.
(59)
Lemma B.16 follows from Lemma B.6 and union bound.
16

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
C. Two-Stage Training Loss Analysis
In this section, we analyze the training loss. These results are based on the high probability conclusions in Appendix B. We divide the convergence of neural networks trained on each data into two stages. The training dynamics stage I first and then enters stage afterward. In Stage we consider that the training data (x, y) & satisfies 1 logit,, (W,i,, (1).
C.I. Network Gradient
The full-batch gradient on the neuron War at iteration is
2
w 10 L(W(),
,,,))
1
Σ
Ily = k)) (1 logit, (W(t), x))
Σ o' (1w/)))(())) x(6
Ar
mn (x,))SS
(60)
2
Σ (x,))ES
[y * k) logit, (W(1), .x)
Σ o' (m x(6)
mn
j=1
C.2. Training Loss Bounds at Stage
First, we consider the training loss dynamics of stage 1 : For any data (x, v) E S, we have L(W(t), xx,)) = O(1). First, we characterize the training loss.
L(W(++1)) x, L(W())) x, :))
-o log probb, (w(++))x) x)) + +log (prob, (w(),x)
prob,, (W())x)
= loog
prob,, (W(++1), x)
exp ( (x))
exp (1(1) (x)) + E idv exp (F!)) (x)
logg
(1(1)) (x)
( (x))
+Ejty exp (p(6tl) (x)
exp
exp
(61)
1+ Eivn exp (1/00) (x) 1:00 (x)
exp (A (x) -1 (x)
log
1 Σ Ciyy cxp ( (x)
F (x))
Eity exp (I/10) (x) 1/(00 (x)
(exp (A
(8) (x) - (x)) (x)) -1)
= log
1+ ++Eitn exp ( (x) - FF/ (x)
1+ --proby (wrl)),) xx)
exp 4 j (x) 4/0 (x)) -1))
(1)
< log
max ンチツ
where A14) (x) = 1 1) (x) - 12(t) (x), (1 (x) = p((+1 (x) - (x)())). (x).
By Lemma B.7, we have
C (w((t)),x1)) - L (wro), x) 1 0(1) max
(A (x) - (x))
(62)
j#
To measure how training loss changes over iterations, we need to characterize the change of (000 (x) 15((x))
17

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
C.2.1. UPPER BOUND OF 4 ( (x) (x)
We first rearrange
(x) - (1 - (x) as follows.
4/9 (x) 1 (x)
1 m
2
(
(+t))
xx(1)) -o
-o -o ((w5)
Jirt ( }
m
i=1
2
(( (w
(((=,,((())) xx(0)) -0 x(()),((())) |1
( (w (11)) , ),)) - (( un
m Σ o ( ((w)t (+t))) .5) - 0 (( (w....()) =
1
m
(63)
B
w/(tt!) 1 m²)) -a (mm50) p.r. uy ))
o (( orr
(ott).)))) - ((m52 ((mb)--))) {
We then bound A, B, C, D in Stage 1.
Bound of A
1 m
Σ
(1)
7
Σ
d'(w (1) un)) logit, (W(), xx) uy unl
A
σ
m
mN
(ES,
(64)
1
o
(w/..) jir:
)ny)) )
<0,
where the inequality is by the fact that (uy Uy) 2 O.
Bound of B
B
W (t)
Σ o' "'w//2 E.) logit, iirr, (W()), x:)6;
Eii) (1 (1- logit, (w((), E.. E b)
Σ (XSS
o'
1
Σ o
(ww.2-)))
mn
7
Σ o' (Iw.7 logit, (w()) x;)
m
mn
(x
(65)
((w(t (1 (1-1oge) logit, .xi)) E.. b)1
1 m
+ mn
17
Σ
d'
m Σ o (ww/)) E)
(XSS))SSS
11 mn (S)
Σ
((w.). E.))
logit, (W(1), x:),,, E
7
o' ((w/) (1- ( (w())x)) ((5., 4)
mi
(xxM))
where the inequality by the 1-Lipschitz property of the ReLU function.
18

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Bound of C
o'(ww (t) Mirs (n)) (1- logit, (1-logit, (W((),x)) .x)) uy uw u. ))
W (t) v.r
+
7
Σ
1=1
(x..
m
(wwf)) Mir mpi))
(66)
m
2m
Σ
(1- logit, (W ( ,x,)) | 12
5mn
(X,
where the inequality is by the fact that ||uyl| 2 0.
Bound of D
((m5)
D
(w
7
Σ
d((wlor E.) ( xx (w)))
(W(!),
((m sil (1- (1-o (w()) E E s)) 6::5))
11
Σ
mn
(w
s. :s)]
(w(0) g {)
"1
Σ d'(ww(0) E.) logit, (W(1), x;)] (E,, E)
m
mn
d' (ww!th E)) (1 (logt,,,
logit, (w(), xx) |E112
(67)
mn
Σ o' ((w5)) (1- logit, (w((),,,) lo (6 E) )
mn
(ES ((6.))
(w(l)
(1) M.m {
1)
logit, (W(1), x:)l (E:: E) +
2n
(1 (1- logit, (w(),x)) xx)x 11el2
mn (XS,)))
5mn
1
Σ
(1 logit, (W(1), vx()),,))) (E:, E)
mn
(
20,
where the last inequality is by that fact that the incremental term is larger than zero a neuron is activated, by Lemmas 4.7, 1.1,, at least 0.4m neurons are activated, and o'(-) <
19

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Substituting (64), (65), (66), (67) into (63), by Lemma B.13 and Condition 3.1, have
A (1)
(x)
A (x)
27
Σ
(1 (1- logit, (w(O),,)) xx)) |
5mn
(X.))ES,
21)
Σ
logit, (W(), xx) (E 5mn (1 (1- logit, (W((,, x)) |IEl2
21j
mn
(x,,
(68)
+ 21
Σ
(1 (1- logit, (W (E,; E)
$ 2m
Σ
(1-logit, logit,( (w((),x.)) |/
5mm
(X
Combining (68) and (62), for any (x, 3) S we have
((W(++1) x. v) <L(W(t) ,x,))
2m
Σ
(1 (1-logit, (W(1), (x,)
||
5mm
(xiN))ESs
(69)
(a)
1
|S,l | 122) ((W(()) v).
mn
where (a) is obtained from Lemma 4.7. This finishes the training loss analysis in Stage 1.
C.2.2. ANALYSIS OF STAGE 2
In stage 2, the loss of certain data is no longer (1).
First, let W be
4(K - 1) uj
w 2.5
(70)
| ?
E
where e > is a small constant. We have
- w-1. = 2n (VL)(W())) W -W+) -n² VLs (W())
w0 w
(71)
For the first term A, we have
A 2n
(Ls((W()), W(O) W
2n
Σ (VC(W(), x.
(.C(W",,,M)) 8), Wi) - W
(XI))ES
21
Σ
Σ
OL(WiO, X, v)
(F2 x,,), W W
OFF
(x,))SS K
2m
Σ
Σ
(C(W(), v)
(FL((( x,)), W(O)
(72)
OF
(X:I) KE(K)
2n
Σ
OL(WL) x,
(FF((W() ,x,)) W
n
OF
(x.0)ESKEl))
2n
Σ Σ
OL(W(), ..,))
F.(1(),, xx,)
(VFL(W(O) x,3). W
OFk
(E
20

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
where the last equality is based the homogeneity of F.(.) for any [K]. Then, we need to bound C. First, for any & [K], we have
V (9) ((((())
x, - ( (d((w(2)))) E+ o' ((w (w/n un 1(k i).
(73)
By the definition of W in (70), we can get the components of as
Kolg(4(K-11)) 2 o' ((w!)r 1n)))) | if =
VE(WO, X. v). W
(74)
i
Next, we bound B.
2
B = FLs(WWl0)
2
1
Σ kE|K
aL(W(), x.u)
FF W x,
1i
n1
OFk
(75)
OL(W(), x. v)
| x,
OF,
1=1
kE|K]
where the first and the second incqualities are all based on triangle inequality. For any lo [K] and (x,8) E S, we have
|FA x, v)
= o' (( (w (w)..,,))) uy + o' ((m))-)))
=100
(1)
< |uyll + ||E1|2
(76)
3
< Julll + V 2 Tr (ATAA))
where the first inequality by triangle inequality and the fact that o' ((whi ( s and the second inequality is obtained from Lemma B.13.
o' ((w2r
Then, we can bound B as
2
OL(W()) x.
B
Sm
(W(("
xx, x0,0
n1
OFF
i=1 KE(K]
||ue|l2 + Tr (ATAs) ))²
1 1 logit, (w(),))) ]
.4
1 Σ
11-io
(77)
KE[K]
n i=1
<An²
max
||ux|| 11 + V Ir (A Ax)
Ls((()))
kE[K]
where the first inequality is by (75), the second inequality is by (76) and the third inequality is by Jensen's ' inequality. Combining them together, we have
Σ OL(W(0,x,) x,,))
- -VFF(W(O)xx))) x,9), W.))
A
n
OF.
(x.))ES
> 2n
Σ (C(WO)) x. x.,() 4
(78)
(x,))ES
-2n (Cs(W)(0)) -
21

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
where the first inequality is based on the convex property (Lemma B.8) of the cross-entropy function and (74). Hence, have
w - - 1| w((+1)=
W
)) (s((()))
||uella + V Tr (ATAs)
22n ((s(W(())) - -4x2²
1x7²
(79)
max ke[k]
EnCs(W(9g 17E
2
where the first inequality is by the bounds of A and and the second inequality is obtained by the condition that S
(4 (maxxe(k) (luell2 + 1.5Th (AT)))
Taking summation over all the iterations yields
(W()) < w - w +
(T- - To + 1)me
2
(=
(80)
(s(W()) < 1| W
12 C
F
T To +
1/( - To + 1)
2
To
By the definition of W we have
W - -
w(()) - + 10 wio
+ 10
1
(81)
For W(2)) w ||,- we have
w(T)) 1000- w
< 00
Ti max (//u,112 (T(AAA))) = =ō max jE[K]
(Tr A ,,
(82)
m [JE[K]
Therefore, we have
| - W
<0
max (Tr(AA A:))) 1 O(VVdoo)) + +0 Vmk log jE[K]
4(K -1) ((K-1)
(83)
max(n max (Tr(AJ A,)), Vmdoo, VmK) jE[K]
This finishes the training loss analysis in Stage 2.
D. Test Loss Analysis
In this section, we analyze the test loss. Similar to the proof in Appendix C, the results are based on the high probability conclusions in Appendix B. In order to characterize the test loss, we first prove the following key lemmas.
D.1. Key Lemmas for Test Loss Analysis
Lemma D.1. Define
5 (r [m] (w!l). E2) > 0},
(84)
for all (xi,y)) E S. For any (x,,)), (x), E S, t E [T') we have
logit, v (W(t), x;)
1 logit, (W()), x;) S
(85)
for a constant x. > 1 and
s(t) C s(tt))
(86)
22

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Proof. We prove the first statement by induction. First, show the conclusions hold at iteration 0. At iteration with probability least 1 6, for all (x.y) E S, Condition 3.1 and Lemma B. B.14, we have
0 (W (0) x) SC
(87)
where C' > 0 is a constant. Therefore, there exists constant such that
1 - logit,, (W("),, x;) logit,, 3 (W(0), xj) S k.
(88)
Suppose there exists such that the conditions hold for any S t S f. We aim to prove that the conclusions also hold for t t= + 1. We consider the following two cases.
Case 1: loggghty (W
0.9r. First, we have
logit, (W)))xs)
1 logit,, (W x;)
Exetr exp(Ft (f (x:) exp() (x.)) Exeu. exp(F (xi) (xi))
EkE(K] exp (F (xx)(x)))
(89)
1 logit,, (W(),x) xx,
Exe[K] exp (F( (xx) exp (4 (xx))
indicating that
max K exp (1 (x;;
logit, y: (W(++),, x.)
(90)
logit,, y, (Wit), x1)
min exp (
(t) (xx))
Moreover, have
AA b
(x:)1 S 1) max
||u
2 + [|
S n
max kE[K]
||ul|2 + Ir (AI (AT An) $ $0.02,
(91)
kE[K]
where the inequalities are by Lemma B.13 and Condition 3.1. Then, we have
logit,, (W(++),, x:)
I logit,, (W(+1)), xx,)
1 logit,,, (W+++)), .x.) 1 - -ogitt,, (W(t), (x)) 1 - logit, 1/
(W((), x;)
1 logit,, (W()),,) x;) 1 - -logit,, (W(+-), x;) logit,, (W(),x) x,)
(92)
1 logit,, (W(+),x)
logit, by (W(t), x,) -exp(0.09)
<R.
23

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
1 y (Wil), xx) 1 I-lngit,, (W()),,))
Case 2:
0.9% 1. We have
1 logit,, (Wit+1,, xi)
1 - logit,, (W(+)),x,))
Ensu, exp(Pr (1( (xz)) + exp (re)) (xz))
exp (A (xx)
ming (0) (x;))
Ekty. exp(Pk (x+) + exp (F (x+)
exp <
(t) yi
(x.) maxx3
(e) k (x;)
Ekju. kty. cxp(F( (x:))
(93)
E E exp(F) (xx))
1 +
1 logity, (W()),,) - exp [A
(1) (x²) min 1/ (xx))
1- logit (WI))xx) - < 1xxpp, (x²) - min A (xx) - 00 (x;) + max A (x:))
1+
exp A (xx) max Ak
(1) (xx)
Denote 1 = arg min 1 and 1/ = arg max
(1) k (x,). We have
(x:) 10 (x,) - D (10 (x,) + - (x,)
7
(1 logit ub (W(1), x xx(( ) Ex)
21 (1 logit, v. (W())x,)) || 5n
71
7
logit (w xx () Ex) + ? (1 logit y; (W()) ,x,)) ||5, 2
(94)
n
20
(1 logit (W x.)) x.)) |1.112 2 logit, (W(+), xx)),,)))))))))))) u l2
5n
<0,
logit, (Wi)) xx
by letting K > @(max A/TrAA A.)) ///1////111//// (1.))))))
Then the last inequality is by T Tolggi (W()),y)
0.9x and Lemma B.13. Therefore, we have
1 logit,, (W(++1), xi)
logit,, ;, (W(++), xx)) S k.
(95)
This completes the proof of the induction.
Next, we prove the second statement. For data sample (x;, E S and neuron in s!0), we have
(w (1+1) Yerr
EEi) ((w())
Bert E.) + 7
mn (1 logit,, (x:)) ((w (2., (.)) 11))21
"
logit, v, ((ww(( Man (Ep))
(96)
mn P
(() Bir E.).
where the inequality is by Lemma B.13, Condition 3.1 and (88). Thus, we have 5:0) S s((+1). This completes the proof.
24

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Lemma D.2. Under Condition 3.1, I. for any j E [K].ee [K]MS), (x4, E Sg. (Xaz E St and S
logit,, v. (x,))'''((w)) (w Egy)
M=
(97)
Tr(AJ A.)
=Ω
g (W(1), xx))o' ((w jor Ea))
[ A At, 1/2 1og(3n2/8)u)
Proof. By the update rule of gradient descent, we have
(w (1+1)
5r w (2)
j.r Sa) I
"
Σ
(.)) (1- logit,(W(()) (W("),:)) o' (((W))))))) (a)
(x Je..eeESsss (ES
(98)
" mn
(- logit, (W()), x))oo (..).r E.)) 115.112
+
By Lemma B.13, we have
(w (t+1)
Jrr
jir Ea)
+
17
(logity (W(1),x, xx)))o(( ((w (aa))) Ea))
Σ Ea
(1- logit, (W()), x))
max
A A yyl |/
1/2
log(
3n²
11/2
(99)
[yE(R]
6
(x.y)E5 (xt. Ha)
K==0
Ei
Additionally, by the nature of ReLU activation function, the magnitude of (w jir
(1+1)
(0)
Ea) satisfies
(++1)
Ea) 2
Σ
Eo logit, ( (W((), x))
7
15.112.
(100)
J.r
mn
(x. t'=0
As the learnign rate is small (by Condition 3.1), combining (99) and (100), for any (x, 8) ~ D. we have
n
(logit, (W(C), (sa))o'((W))) Ea)) IE..
mn
(101)
=0
1]
E (1 logit, (w((), ,)) x))FF Fr
mm
(xx))
e'=0
(0)
By Lemma D.1, for E have
logit M4
(Wl(') (W(()xx)))'' (w E.))) (E))))
(102)
E.a)) 1l
=Ω
(logit, (logit((W(''), xxa))o ((w (
By Lemma B.13, we have
&E 2
Tr(A7 Ai)
(103)
ATJ A || log(3n? /2
Combining (102) and (103) yields the conclusion. This completes the proof.
25

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Lemma D.3. Under Condition 3.1. for any j [K], we have
(w/?2) A S Olvmlog(T))
(104)
Proof. We bound it with two phases. The first phase
E [0, Ti] is before the loss of data (x, v) E 8 satisfying
logit, (x) S cs.
(105)
where C5 is constant. Then, the loss satisfies
(o
(1 c5) exp
<1 Cs) exp
0
w (T1)
((w17)) k))) (fi)
yor
Ses Σ exp (o
(
(w (w)r)) U1
(fi)
jir )
ta
1&y
(106)
Scz K exp
(v
2
4Km
||ux|l2 0o 0 (log
Km
AA 00)
mn 1
31
Tr (AJ AA)
$1.les Keep exp
22m
where the first inequality is by the fact that a function and (105), the third inequality is by Lemma B. 14 and the fourth inequality is by Lemma B.13 and Condition 3.1, Letting cs be T/(1.K + T) yields
w yor my) 2 O, the second inequality is by the definition of softmax
(1)
.) S log (w (1) 9.
K
+
37 Tr (A. Ay) S O (log(T))
(107)
C5
2mn
Moreover, for T Tú, we have
(w 5) =(w((f)) (fi)
(w
w (Ti)
y.r .E)
p.r
y.r
10 (T)g +2
n (1 logit, (W(',x) ||E||
t=
mn
(108)
3TT 1 mn 'Tr (AJA,)
<0 (log(T))
< <O(log(T))
where the first inequality is by (107), the second inequality by Lemma B.13 and condition of the second phase that (x) cs. With probability of for n randomly sampled data (x', y) Dy. we have
(W(T) 1)
so
"
(1 logit x)) 5")) 511)
mm
iES
t=0
(109)
T-1
logit w ((), x|)1 = (((w = (w T AyS.
mn
With probability 1 - 8, at least one sample (x', y) satisfies (w E²) θ (((m(??) (.b.?)
Ayy A
by the property of De.
Therefore, we have
(|(((())) (hrr)
T A, A,1))
(w (T) v.r
( =
(110)
Combining (108) and (110) completes the proof.
26

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
Lemma D.4. Under condition 3.1, for a random vector & generated from A S De any [K], with probability at least 5, we have
Σ T En((w ( (5)) 2 0.1m.
(111)
Proof. First, we can concatenate the neuron weights for class j E [K] as
(w
311
B1111
E1
W A, =
:
A
A +
Aj
(112)
(2)
w (0)
8j.m
Lnn
5,m
j.m
D2
where Bj,na == Ev=00 o' o(w logit ((),, x.). The rank of matrix D2Aj satisfies
(1)
rank(D2A,) S min n, d, rank rank(A,)) = n. In addition, as the matrix D is Gaussian random matrix, it has full rank almost surely. We have rank (DiA)) min(m, d, rank(A)));
(113)
(114)
almost surely. Then by Condition 3.1, the rank of w (?) A satisfies
rank(W)7 W ( Ay) 2 min(m, d, rank (ank(A)) 2 0.9m.
(115)
In addition, by Lemma B.I and Condition 3.1, the singular value of w Aj satisfies
Amiuf (.nnm.m.....A)))----a11 W Aj) 2 0.1vmo..
(116)
Moreover, by Lemma D.3, have Therefore, according to Condition 3.1, we have
A (w (T AA)) W A <0(vmlog(T) (og())g(T))
(117)
m 2 log(n/6) 1og na
(118)
By Lemma 1.12 and Condition 3.1, with probability at least - 6, we have
m
Σ
(w
(T') j.r .5) 2 0.1m.
(119)
This completes the proof.
D. PROOF OF STATEMENT 2(A) IN THEOREM 3.4
In this part, we prove Statement 2(a) Theorem 3.4. For data samples following (x, y) ~ D, the test loss satisfies
LD (D(W(0) -P arg max F& (T)) xx,) # y
(T() x, v) < (,(W(T), .x,1)
(120)
m
nn)) + (((w(7)))
{)) s Σ a (W (
(y)) + a(w (T)
jo .3)
9.
jr
27

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
For the features, we bound the loss for any (x, y) DD through
m
o(w yor (y)) S m
((W(T) ,x,y) S
Σ
Σ o(( ,y)) + [( E))
(121)
jzy
Then, we can bound the model outputs as
m
Σ
(2) Nir
ug )
m
Σ
((())
7
Σ
Σ (1 logit, logit,(W(()) (W(1), (x((),,1))o'' ((W))) g,r, (u)) uy uy uy
(122)
71
(XL,
T
3m 1
Σ
Σ
logit, (W(1),)) x1)) ||u
10 m
e' (XS,
and
m
(T) E)) S m
Σ
(T) 4 Σ A
(')
(123)
12
where Ç' is a sub-Gaussian variable. Suppose that > and || A, 11 /t.//I/AAllll... 2 ((V/oo For the term
AJ T w/ (T) 9 j.r with probability at least 1 - 5, we have
A w (T) 1
A
Σ
(1 - logit, (w((),))o''
x)]o' ((w52.5)
jr
(X)
logit, logit, (Wit') x)o x))'()w)( (( <))E
ESi,,
<
A
Aj
(1 - logit, (W((') x))o''( S E)
(2)
P=0 (x.y)eS;
(124)
+
Σ
A
A
Σ (x.))ES.
logit, (W(1), x)o' ((W E))
(1 - logit, Aogii,(WW (w(r), (w((),x))o'' (( (1') EE)E |
A
Σ
M== (x,))SS,
T-1
2
Σ (x,y)ES)
Σ (1 logit, (W(O),x) x)), ==
where the inequality is by Lemma D.2 and Condition 3.1, (a) is based on Lemma D.2, and (b) is based on the concentration
of random vectors (Theorem 6.2.6 in (Vershynin, 2018)). Substituting (122) and (123) into (121), for any (x, y) ~ we
28

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
have
((W(T) x, v)
m 7 T-1
m
Σ
Σ
Σ
(1 - logit, (w(+), x)) |/ 11 -
(w)) (2)
E)I + 1(
fr اyy!
2
5 n 0==0 (x
J.r
j7y
= =
m イ T-1
5
Σ
Σ
(1 - logit, (w(t), x)) || u 11 - Σ
m
A w 30
1|
15' + 1w 100 السس
2
jテy
p= (X.v)ESx
$ > P
Σ
Σ
(1 - logit, (W()), x)) 1
(125)
jzy
m==0 (x,))ES
2
( n
S c cc|AJA,11 A F
Σ
Σ (1 logit, (W(r),x))
1
log
4km
||lرس|| (0)
7
5
(x.V)Ss;
A²=0
Ss, 1 ||uاسl |s A,
exp
-11
jzy
where C, > 0 are some constants and the last inequality is obtained from Hoeffding's inequality.
D.1.2. PROOF OF STATEMENT 2(B) IN THEOREM 3.4
Furthermore, for long- tailed data distribution, by Lemma D.2 and union bound, we have
C (W x. v)
P
(( (w/)) () s Σo ((w/37
(2) wy)) + (m/hh)))
(126)
j&y
Suppose 5 > 0, by Condition 3.1, w have || A A pl ||A Av Allap 2 e(v(logg (o/oo((220 K2
for any y E [K]. With probability
at least 1 - 6, for all E [K]. we have
(2) M.r
W
2
T-1
T
W
(0)
Σ n2
1
Σ (1 - logit, (W((), ())o ((wl)) (
9.T
='=0 (S,
2
Σ
Σ
logit, y (W((), (y((),x)'' gir E))E
TI === (x
2
A A
1 Σ
Σ
(1- loi (o (W x))o x))o'((w((?) ((W!t? 3or <)
(127)
T1 P== (X.))ES,
2
Σ
AJA,
Σ
logit, (w(t), ,x) ((w E))
j4y
#=0 (X,))ES,
Ω
22
"1AATAule
Σ
Σ (1 (o-to (W('), x))
(xW))SS
W/=
where (a) is obtained by the condition || AnT = S -1 A for all j.y E [K] and j + y, K = 0(1), and (85).
Similarly, we also have A (T)
< 0 (1/////A) A///lllAAAwllli VEonness (E==d(1 logit, (W(1), x()),))) Then,
29

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
have
A w
=
! A
Aullo
Σ (X.i)ES,
Σ
logit (Wit,,
(128)
Similar to the proof of (124), we also have
2
A W 3
=
Σ (x.y)Es;
(1 logit, (W()),) x))
(129)
with probability at least Moreover, we have
J W jr
=
7 A AF
Σ (X,))SS
Σ (1 logit (W(+),)) xx)x
(130)
Denote S,(5) = {r [m] : :(w) (T)
> 0}. We have
Σ
J ( TT)
= mpm ||A |ATA
Σ
Σ logit, (W(+), (x)((()))) x))
(131)
rE)
(x.D)ES
because Lemma 4.4 holds.
We have
_ _0 (W((TT)), x) 5
Σn P
1
((w(7)
()
((w (2))
j.r (,)) + [((w 977 -))
gr:
jzy
Σ
(T)
N E -
+ +
14y
SE)
m
m
L
Σ
AJ
(T)
Σ A
(w Jir
(T)
4)
E w (2)
<) + ((
/,0 uny
j.r
(132)
jfy
(E)
1=1
L.
EreS
A. (T)
A w
(
0
(Vlog (4Km/8)
|lyl|l2 o0 )²
1.r
cd'
exp
j4y
m -=
A w
(7)
L2 |Sy1 ||A A
exp
SS ||A A
jfy
where > 0 is constant, the first inequality is by the condition for long-tailed data that (T) ( 2 cs |.
the third inequality is by Hoeffding's inequality and the last inequality is by (128) and (129).
30

---

Rethinking Benign Overfitting in Two-Layer Neural Networks
D.1.3. TEST LOSS LOWER BOUND (STATEMENT 3 IN THEOREM 3.4) For any (x, D, we have
( x, 2 max P
of ((W yor
Uy)) + (W g.rr () a jr my c(( (7)
(. .))
3F8
max TP A
((w War Uy)) + (w 1 {) o a jo 5x. -g)
(2)
(0)
max P 1 y
2mpm 5n
Σ
(1 logit, (W(r), xx) |
-'=0 (x.
2 Σ (1 logit, (W())x)) x])
(133)
mpm
AA A A
Σ (x.D)ES,
15'
n1
B1
am || AFF
Σ (X,))
Σ (1
logit, (W(', xi)
15"1
B2
where (a) is based on (127) and (124). ç' and ç" are sub-Gaussain variables with variance 1. For any (x, y) ~ DD when A
there exists E [K] and constant C3 satisfying ||u 112 < C3 || B.10, we have
|| and || A S Css || A, by Lemma
(W(T), x. 2 max PP
2pm
Σ (1
logit, (W(t), x)) | - B2(5"1 - B115'l
(134)
jły
5n
(X,Y)ES,
Choosing a constant C5 = (O)p), we have
(5' S cs with probability at least 1 - exp(S2(c3/ /,))) resulting in
_ (T x, ma
+
Σ V S |1.111
O(1AA) )())) (1- (1-cxp(((@//03))
(oa)
j&y
=((1).
(135)
E. Computation of Squared Frobenius Norm for Real- World Datasets
To estimate quantity A, for real-world datasets, we decompose the intra-class data covariance matrix. Recall that in our data model, the covariance matrix of data sample (x. y) within class is
Σ, A,A..
(136)
To estimate the A, for real-worke datasets, we first compute the sample covariance matrix:
Σ (x - -)
(137)
S
(x.))ES,
where |Sp] is the size of class in the training dataset and the sample mean.
Next, perform eigendecomposition of the sample covariance matrices Σ. Q,A.Q, where Q contains the eigenvectors and A, is the diagonal matrix of eigenvalues.
We then estimate A, as A, Q.A!/² Using the estimated A, for each class, we can estimate |A] A, Fr
31


Reviews:
[{"review_id": "Ow7GCgZdoK", "reviewer": "Reviewer_SW6r", "summary": "This work investigates the phenomenon of benign overfitting in two-layer neural networks by rdiscussing a  feature-noise model. The authors introduce a class-dependent heterogeneous noise model to attempt to explain why neural nets can leverage long-tailed data distributions for generalization. The paper claim to provide theoretical results demonstrating a phase transition between benign and harmful overfitting and supports these findings with empirical evaluations on synthetic and real-world datasets. The authors argue that neural nets can learn implicit features from data-specific noise, which enhances classification accuracy, particularly for long-tailed distributions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for recognizing our contributions and for the insightful comments. We will answer your questions in the following.\n\n**Discussion on Datasets**:\nThanks for your comment. Please see the reply to Reviewer pfPE due to the space limit.\n\n**Clarification of Noise Memorization**:\n    Typically, memorization (overfitting) of a data sample is defined by achieving near-optimal training loss on that sample [1], a definition commonly adopted in the literature.\nFurthermore, the term 'memorization of noise' originates from feature learning studies [2,3], where it refers to situations in which classification relies heavily on data-specific information rather than the explicit feature.\nHowever, we agree that the term \"noise\" might be misleading, especially when it implicitly carries label-related signals. \nWe will revise the terminology throughout the paper, replacing 'noise' with 'data-specific information' and explicitly clarifying its class-dependent nature.\n\n**Clarification of the Illustrative Figure**:\nIn Figure 2, we clarify the feature strength as $||\\mathbf{u}_i||_2$ and noise strength as $||\\mathbf{A}_i^\\top\\mathbf{A}_i||_F$. Our paper includes settings and explanations for each figure, and we are happy to provide additional clarifications for any other figures that may require further elaboration.\n\n**Justification of the Proposed Model**:\nOur refinement is supported by two key observations. \nFirst, from the t-SNE visualization in Figure 1, we observe that different classes exhibit distinct intra-class distributions.\nSecond, Figure 6 further verifies this by showing that real-world datasets, such as MNIST, have higher intra-class squared Frobenius norms compared to their inter-class counterparts.\n\n**Comparison with Other Benign Overfitting Models**:\nDue to the space limit, for a comparison with other models of benign overfitting, please see 'Comparison with Other Noise Models' for reviewer 5giJ. \n\n**Discussion on Implicit Bias/Regularization**:\nWe will include an overview of studies and comparisons of implicit bias/regularization in the appendix.\nHowever, we would like to emphasize that our work is less relevant to implicit bias and regularization research.\nImplicit regularization is a broad research area focused on identifying high-level regularization effects of optimization algorithms, such as *max-margin, low-rank, and flat biases*, which display good generalization properties. \nIn contrast, our paper is more aligned with research on feature learning, which detailedly characterizes how the *features are learned during training and how these learned features contribute to generalization*.\n\n**Discussion on Noise Structure**:\nWe appreciate your comment regarding the applicability of sub-Gaussian distributions.\nSub-Gaussian distributions are widely applicable in practice, as they encompass a broad range of real-world data distributions (e.g., ImageNet). Specifically, many natural and empirical data distributions are bounded, and such bounded distributions inherently exhibit sub-Gaussian characteristics. While other noise structures may exhibit different properties, sub-Gaussian distributions provide a strong and general framework that captures the behavior of most real-world data, making them a reasonable assumption in many contexts. Exploring the impact of alternative noise structures would undoubtedly be an interesting direction for future work.\n\n**Extension to Deeper Neural Networks and Modern Techniques**:\nFrom a theoretical perspective, analyzing neural networks with more than two layers presents significant challenges due to the non-convex and non-smooth nature of the loss function, as well as the complex interdependencies of parameters across layers.\nFrom an empirical perspective, we found that the main conclusions of our two-layer neural network analysis generally extend to deeper architectures.\nIn our experiments with CIFAR-10 and CIFAR-100, we employ ResNet architectures with batch normalization, demonstrating that our theoretical predictions regarding covariance structure are applicable beyond simple two-layer models.\n\n[1] Cheng, Chen, John Duchi, and Rohith Kuditipudi. \"Memorize to generalize: on the necessity of interpolation in high dimensional linear regression.\" Conference on Learning Theory, 2022.\n\n[2] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"Towards understanding ensemble, knowledge distillation and self-distillation in deep learning.\" arXiv preprint arXiv:2012.09816.\n\n[3] Cao, Yuan, et al. \"Benign overfitting in two-layer convolutional neural networks.\" Advances in neural information processing systems, 2022.", "claims_and_evidence": "The central claim of the paper is that neural networks can use data-specific noise as an implicit feature to improve classification performance. While the theoretical results are rigorous, the paper’s framing of memorization is somewhat misleading. To me, the so-called \"memorization of noise\" is, in reality, learning from well-separated covariances rather than pure memorization of useless noise. The experimental results generally align with the theoretical findings, but the paper lacks a clear discussion on why its proposed model is the right one for studying benign overfitting in practical scenarios.", "methods_and_evaluation_criteria": "he authors use a combination of theoretical analysis and experimental validation. The theoretical methods appear sound and build upon prior work, extending it to the heterogeneous noise setting. However, the experimental evaluation could be improved by including comparisons with alternative models of benign overfitting, rather than focusing exclusively on their own framework. The evaluation criteria for success are reasonable but could be more explicitly tied to real-world applications (CIFAR is ok, but MNIST does not really count in myopinion).", "theoretical_claims": "The theoretical results appear correct and are well-supported by the provided proofs. The use of singular value distributions and covariance matrix properties seems to be an extension of previous work. However, the claim that memorizing noise is beneficial should be reconsidered; what is actually being demonstrated is that certain types of structured noise contain class-relevant information, making it part of the learnable signal rather than harmful noise.", "experimental_designs_or_analyses": "This is a theory paper, so this kind of question seems ill-defined. The author do perform experiements, and the experimental setup is generally well-structured, with evaluations on both synthetic and real-world datasets (MNIST, CIFAR-10), even though i do not really count MNIST as meaningful. However, the key illustrative figures are unclear, particularly regarding the interpretation of \"noise\" and how it contributes to learning. It would be helpful to clarify how increasing the noise strength without a signal component affects performance and whether the conclusions hold for different model architectures.", "relation_to_broader_scientific_literature": "The paper builds upon prior work on benign overfitting and feature-noise models, referencing key studies such as those by Kou et al. (2023) and Feldman & Zhang (2020). However, it does not sufficiently engage with alternative explanations for benign overfitting, such as implicit regularization effects in overparameterized models. These are classical and widely accepted. More discussion on the relationship between this work and theories of representation learning would strengthen its contribution.", "essential_references_not_discussed": "he paper should include more discussion of recent work on implicit regularization and the role of covariance structures in deep learning. Some relevant studies on feature learning dynamics in deep networks and their relation to benign overfitting are missing. Additionally, work on the role of batch normalization and other architectural choices in mitigating harmful overfitting should be considered.\n\nOn the top of my head, i can thnkg of work such as Srebro's\n\nThe Implicit Bias of Gradient Descent on Separable Data\nDaniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, Nathan Srebro; 19(70):1−57, 2018.\n\nOr\n\nThe Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks", "other_strengths_and_weaknesses": "Strengths: The paper presents an interesting refinement of existing models and contributes new theoretical insights into overfitting in long-tailed distributions. The analysis of singular values and covariance structures is a valuable addition.\n\nWeaknesses: The framing of \"memorization of noise\" is somewhat misleading, as what is actually observed is learning from informative covariances. The motivation for the specific model chosen could be stronger, and the empirical results would benefit from comparisons to alternative benign overfitting models.", "other_comments_or_suggestions": "Clarify what is meant by \"memorizing noise\"—if the noise contains label information, then it is not purely noise but an implicit feature.\n\nImprove the illustrative figures to make it clearer how noise and signal interact in the proposed model.\n\nInclude a discussion on why this specific refinement of the feature-noise model is preferable to other potential explanations for benign overfitting.\n\nCompare results against other recent theories of benign overfitting, such as those related to implicit regularization.", "questions_for_authors": "Can you clarify why you refer to learning from structured noise as \"memorization\" when it appears to be leveraging class-dependent covariance information?\n\nHow would your results change if the noise distribution was not sub-Gaussian but had a different structure?\n\nWould your findings hold in deeper networks beyond two-layer models, and how would they interact with batch normalization or dropout?\n\nCould you include comparisons with other models of benign overfitting to contextualize your results?", "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": "", "extra_scores": {}}, {"review_id": "gDsxK29EMv", "reviewer": "Reviewer_pfPE", "summary": "This paper explores overfitting in neural networks, challenging the common belief that it harms generalization. Specifically, the authors argue that certain forms of overfitting can be benign and demonstrate—both mathematically and empirically—that benign overfitting can enhance performance on long-tailed data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for recognizing our contributions and for the insightful comments. Below, we address your concerns in detail:\n\n**Clarification on the Choice of Datasets**: We would clarify the reason for experiments on MNIST.\n - While MNIST may be considered simpler in comparison to other datasets, it remains a highly relevant choice for studying long-tailed data distributions. The long-tailed examples in MNIST—often corresponding to poorly written digits—offer clear physical interpretability [1].\n\n- Moreover, existing theoretical analyses in feature learning often rely on simplified synthetic data models (e.g., combining features with class-independent sub-Gaussian noise). Unlike those simpler models, our approach incorporates realistic intra-class covariance structures, similar to those in MNIST, providing new insights into the mechanism behind benign overfitting.\n\n**Applicability to More Complex Datasets**: We understand your concern about the applicability of our findings to larger and more complex datasets.\nTo address this, we extended our experiments to CIFAR-100, a more challenging dataset, using a deeper network architecture, ResNet-101. We replicate the experimental settings from Figure 7 and present the updated results below:\n\n| Remove percentage | 0% | 20% | 40%| 60%| 80%|\n|----------|----------|----------|----------|----------|----------|\n|Remove images with high influence scores | 66.48% | 64.77% | 55.34% | 46.53% | 34.38%|\n|Remove images with low influence scores | 66.48% | 65.52% | 60.52% | 55.34% | 38.20% |\n\nThese results further validate our theoretical predictions (particularly Statement 2(b) in Theorem 1). As shown, removing high-score samples results in a more significant accuracy drop compared to removing low-score samples. This trend aligns with our theoretical expectations, demonstrating that our framework applies to more challenging datasets like CIFAR-100, as well as deeper network architectures like ResNet-101.\n\nDue to time constraints, we plan to include additional experiments on Tiny ImageNet in an updated version of our work.\n\nWe hope that these extended experiments clarify the broader applicability of our results to more complex datasets. \nThank you again for your valuable comment.\n\n[1] Feldman, Vitaly, and Chiyuan Zhang. \"What neural networks memorize and why: Discovering the long tail via influence estimation.\" Advances in Neural Information Processing Systems 33 (2020): 2881-2891.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes. But analysis on more complex dataset such as ImageNet would further strengthen the claim made by the paper.", "theoretical_claims": "No", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper is trying to explore the phenomenon of overfitting where it helps the model's performance. This is quite broad topic and can be applied to many research area.", "essential_references_not_discussed": "None that I know of", "other_strengths_and_weaknesses": "## Strengths\n- The paper is well-written and easy to follow.\n- It presents a novel perspective on overfitting, challenging conventional wisdom in the field.\n- The claims are rigorously supported through both mathematical analysis and empirical validation, strengthening the arguments.\n\n## Weaknesses\n- The experimental section could be strengthened by evaluating more complex datasets, such as ImageNet, rather than relying solely on MNIST and CIFAR-10.", "other_comments_or_suggestions": "None found", "questions_for_authors": "One of the major concern is regarding the dataset used for evaluation. Is there any reason for not performing experiments on more complex dataset?", "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": "", "extra_scores": {}}, {"review_id": "Tg3CduYPpm", "reviewer": "Reviewer_NBdR", "summary": "This paper establishes an enhanced feature-noise model by considering class-dependent heterogeneous noise across classes. Under this model, the paper demonstrates how memorization of long-tailed data boosts model performance. Additionally, it provides a phase transition of test error between benign and harmful overfitting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for recognizing our contributions and for the insightful comments.\nBelow, we address your concerns in detail:\n\n**Clarification of Long-Tailed Data Definition**:\nOur definition is not recursive but instead relies on a fixed value of $T$, with no new data being introduced post-training, nor does it alter the training process.  Instead, we use the final model $\\mathbf{W}^{(T)}$\n—obtained after a sufficient number of optimization steps $T$—to assess the long-tailedness of individual samples.\n\nClassical definitions of long-tailedness often hinge on simple one-dimensional statistics (e.g., sample counts or Zipf distribution). However, such metrics may fail to capture nuances of high-dimensional data (e.g., 3\\*32\\*32 images in CIFAR). \nFor instance, for Sub-Gaussian data, norms alone do not always capture which samples are “rare” or “hard” to learn due to concentration effects. \n\nTo address this, we draw inspiration from prior work that uses trained models to identify \"long-tailed\" samples. \nFor example, Feldman and Zhang [1] evaluated long-tailedness by measuring the accuracy changes when training with or without a specific data sample.\nSimilarly, Garg et al. [2] computed a curvature-based measure using trained models.\n\nIn a similar manner, our definition leverages the trained model $\\mathbf{W}^{(T)}$ to map high-dimensional samples to a one-dimensional metric, allowing us to identify long-tailed data points from the perspective of the network’s learned representation.\n\nWe hope this explanation clarifies that conditioning on $\\mathbf{W}^{(T)}$\ndoes not introduce a recursive definition and is instead a post-hoc method for characterizing long-tailed data distributions in high-dimensional settings. \n\nThank you again for your feedback; please let us know if further elaboration is needed.\n\n[1] Feldman, Vitaly, and Chiyuan Zhang. \"What neural networks memorize and why: Discovering the long tail via influence estimation.\" Advances in Neural Information Processing Systems, 2020.\n\n[2] Garg, Isha, Deepak Ravikumar, and Kaushik Roy. \"Memorization Through the Lens of Curvature of Loss Function Around Samples.\" International Conference on Machine Learning, 2024.", "claims_and_evidence": "Yes, the analysis is clear, rigorous, and thorough. Additionally, experiments are provided for further support.", "methods_and_evaluation_criteria": "Yes, the model is more reasonable and closer to real-world applications than previous work. The experiment covers both synthetic data generated from the model and real-world datasets.", "theoretical_claims": "I didn't check the correctness of the proofs, but I am familiar with the proof technique, and the results look reasonable to me. So, it is very likely to be correct.", "experimental_designs_or_analyses": "Yes, I checked the experimental design section.", "relation_to_broader_scientific_literature": "The generalization to heterogeneous data is good. For me, the interesting part is the results for long-tailed data, where the authors show that the classification accuracy of long-tailed data increases with the noise correlation ratio. This provides a theoretical explanation for the empirical observation of the necessity of long-tailed data in the training dataset.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength:\n1. Novel Generalization: The paper extends the feature-noise model to class-dependent heterogeneous noise, making it more applicable to real-world scenarios.\n2. Theoretical Insights: It provides a rigorous analysis demonstrating how memorization of long-tailed data boosts model performance.\n\nWeaknesses:\n1. Definition of Long-Tailed Data: The conditioning of the L-long-tailed data distribution on the neural network model at time step T may introduce a recursive or non-intuitive aspect. It is unclear why conditioning on W_T is justified when no new data is generated after optimization begins. Please refer to questions for detail.", "other_comments_or_suggestions": "No.", "questions_for_authors": "I have questions about the definition of long-tailed data. The L-long-tailed data distribution (Definition 1) is defined by conditioning on the neural network model at time step T. I feel there might be an intrinsic tricky part, like a recursive definition, because the training data is generated first, and the neural network parameters are then optimized using this data. It seems odd to condition on W_T because no new data is generated after the optimization process starts. This is different from using SGD, where new data is introduced in each iteration. It would make more sense to me if a long-tailed data subset of the entire training dataset were defined independently of the distribution, and then this subset’s specific role throughout the training dynamics were analyzed. Please correct me if I have any misunderstanding.", "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": "", "extra_scores": {}}, {"review_id": "fDfOqD3QyB", "reviewer": "Reviewer_5giJ", "summary": "This paper analyzes the training dynamics of a two-layer CNN which can lead to benign overfitting. By analyzing a new data model with feature-specific noise, they claim that neural networks can learn \"implicit features\" that improve the accuracy when training on long-tailed data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for recognizing our contributions and for the constructive feedbacks. \nBelow are our point-by-point responses:\n\n**Clarification on \"Data Noise\" Definition**:\nWe agree with your point and will revise the term 'noise' to 'data-specific information' and clarify its class-dependent nature. \nWe will also clarify this distinction throughout the paper to avoid any potential confusion.\n\n**Relationship to Adversarial Robustness**:\nWe agree with your assessment that the implicit features discussed in our paper could be interpreted as non-robust features.\nAs demonstrated in paper [1], standard training learns non-robust features from data-specific information, while adversarial training purifies these features to enhance model robustness.\n\nIn this context, our theoretical framework has the potential to extend results in [1].\nSpecifically, while adversarial training removes non-robust features, our paper posits that this process negatively impacts plain accuracy, particularly in long-tailed data. This corollary is empirically supported by the findings in [2], further supporting our theory.\n\n**Comparison with Other Noise Models**:\nWe acknowledge the extensive research on the effect of label and data noise on benign overfitting. To clarify the distinctions between our model and prior work, we provide a comparison with existing studies on benign overfitting, focusing on two-layer non-linear neural networks incorporating data noise.\n\nStudies [3-7] (a representative selection due to space constraints) focus on the 'explicit feature + class-independent Gaussian data noise' model (similar to the feature-noise model developed by [8]).\nWhile these studies explore various training settings, they consistently show that excessive data-specific noise leads to overfitting. \nHowever, they fail to explain the empirical results that memorizing data-specific information can enhance generalization, particularly in the context of long-tailed data.\n\nIn contrast, our work refines these models by incorporating the data-specific information with heterogeneous covariance. We theoretically prove that neural networks can leverage the implicit features learned from data-specific information to improve classification performance on long-tailed data. Our theory greatly extends the traditional understanding of overfitting.\n\n\n**Calculation of $||\\mathbf{A}_i^\\top\\mathbf{A}_j||_F$**:\nTo estimate the quantity $\\mathbf{A}_i$ for real-world datasets, we decompose the intra-class data covariance matrix.\n\nRecall that in our data model, the covariance matrix of a data sample $(\\mathbf{x},y)$ within class $i$ is $\\boldsymbol{\\Sigma}_i = \\mathbf{A}_i\\mathbf{A}_i^\\top$.\nTo estimate $\\mathbf{A}_i$ for real-world datasets, we first compute the sample covariance matrix:\n\\begin{align}\n\\tilde{\\boldsymbol{\\Sigma}}_i = \\frac{1}{|\\mathcal{S}_i|-1}\\sum\\_{(\\mathbf{x},y)\\in\\mathcal{S}_i} (\\mathbf{x} -\\bar{\\mathbf{x}})(\\mathbf{x} - \\bar{\\mathbf{x}})^\\top,\n\\end{align}\nwhere $|\\mathcal{S}_i|$ is the size of class $i$ in the training dataset and $\\bar{\\mathbf{x}}$ is the sample mean.\n\nNext, we perform eigendecomposition of the sample covariance matrices $\\tilde{\\boldsymbol{\\Sigma}}_i = \\mathbf{Q}_i \\boldsymbol{\\Lambda}_i\\mathbf{Q}_i^\\top$,\nwhere $\\mathbf{Q}_i$ contains the eigenvectors and $\\boldsymbol{\\Lambda}_i$ is the diagonal matrix of eigenvalues.\n\nWe then estimate $\\mathbf{A}_i$ as $\\tilde{\\mathbf{A}}_i = \\mathbf{Q}_i\\boldsymbol{\\Lambda}_i^{1/2}$.\nUsing the estimated $\\tilde{\\mathbf{A}}_i$ for each class, we can estimate $||\\mathbf{A}_i^\\top\\mathbf{A}_j||_F$.\n\nWe will add this detailed explanation in the appendix.\n\n[1] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"Feature purification: How adversarial training performs robust deep learning.\" IEEE Annual Symposium on Foundations of Computer Science, 2022.\n\n[2] Wu, Tong, et al. \"Adversarial robustness under long-tailed distribution.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2021.\n\n[3] Cao, Yuan, et al. \"Benign overfitting in two-layer convolutional neural networks.\" Advances in neural information processing systems, 2022: 25237-25250.\n\n[4] Kou, Yiwen, et al. \"Benign overfitting in two-layer relu convolutional neural networks.\" International conference on machine learning, 2023.\n\n[5] Shang, Shuning, et al. \"Initialization Matters: On the Benign Overfitting of Two-Layer ReLU CNN with Fully Trainable Layers.\" arXiv preprint arXiv:2410.19139 (2024).\n\n[6] Karhadkar, Kedar, et al. \"Benign overfitting in leaky relu networks with moderate input dimension.\" Advances in Neural Information Processing Systems, 2024.\n\n[7] George, Erin, et al. \"Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?.\" Advances in Neural Information Processing Systems, 2023.\n\n[8] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"Towards understanding ensemble, knowledge distillation and self-distillation in deep learning.\" arXiv preprint arXiv:2012.09816.", "claims_and_evidence": "The theoretical results in section 3 on the test loss for the two-layer CNN and the experiments in section 5 support the paper's main claim about benign overfitting in the proposed data model.\n\nOne claim that I find slightly misleading is that this paper shows that memorizing data noise, which was previously deemed harmful, can help classification accuracy. The \"data noise\" in the model presented in this behavior is class-dependent and can essentially be interpreted as containing class-specific information that transfers over to the dataset. This is different from prior works, in which the \"data noise\" class-independent noise. From this point of view, it is not surprising that memorizing data noise can help in the setting presented in this paper while being harmful in other works, and I am not sure to what extent calling the two different types of noise both \"data noise\" is accurate.", "methods_and_evaluation_criteria": "The analysis of the test loss in Section 3 makes sense for the problem statement. The construction of the synthetic dataset in Section 5.1 mirrors the theoretical setting, and the benchmark datasets for noise correlation (MNIST, CIFAR-10) are commonly used.", "theoretical_claims": "Proofs were checked at a high level, details were not carefully checked.", "experimental_designs_or_analyses": "The design and analysis of the experiments on the synthetic dataset in Section 5.1 make sense and support the theoretical results from the previous section. \n\nI do not quite understand the noise correlation verification in section 5.2, in particular how $||A_i^{\\top}A_j||_F$ is calculated for real-world datasets such as MNIST and CIFAR-10 when these datasets do not exactly follow the data model presented in section 3 for which the quantities are defined.", "relation_to_broader_scientific_literature": "This paper mainly belongs to a line of work theoretically analyzing benign overfitting in neural networks. The main difference in this work is the new data model, from which the authors derive new results about the effect of memorizing said noise.\n\nThe authors also connect some of their results to the spurious correlation literature by showing that their results imply that class imbalance can hurt group accuracy.\n\nOne interesting connection which the authors do not mention is to adversarial robustness. Specifically, the feature hypothesis \"that adversarial examples can be directly attributed to the presence of non-robust features: features (derived from patterns in the data distribution) that are highly predictive, yet brittle and (thus) incomprehensible to humans\" [1].  Indeed, if what the authors call data noise or implicit features can be recast as non-robust features, then there could be some connection there. I would be curious about the authors' thoughts on the same.\n\n[1] Ilyas, A., Santurkar, S., Tsipras, D., Engstrom, L., Tran, B., & Madry, A. (2019). Adversarial examples are not bugs, they are features.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "This paper provides an interesting new perspective on benign overfitting by considering a data model with a new form of class-dependent feature noise. The paper is somewhat easy to follow, although some of the assumptions (e.g. Condition 1) are a bit opaque at first glance and could use more explanation.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "My main questions are\n\n1. Making comparisons about the effect of data noise when the \"data noise\" is fundamentally different in this work.\n\n2. How $||A_i^{\\top}A_j||_F$  is calculated for real-world datasets.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates benign overfitting of two-layer neural networks by introducing a new concept of class-dependent heterogeneous noise and shows the signal-to-noise ratio threshold between benign-overfitting and harmful-overfitting. Through the analysis, they show that the class dependent noise enhances classification accuracy, particularly for long-tailed distributions.   
  
The paper is well written and easy to follow. The idea of class-dependent heterogeneous noise is novel. This perspective mitigates the gap between theory and practice. The authors conducted solid theoretical analyses. Indeed, the reviewers did not raise a critical theoretical fault.  
  
 As a summary, this paper can be accepted as a solid theoretical paper that contributes to the series of papers on benign overfitting.
Decision: Accept (poster)