Benign Overfitting in Classification: Provably Counter Label Noise with Larger Models
Authors: Kaiyue Wen
Jiaye Teng
Jingzhao Zhang
Venue: ICLR 2023 poster (2023)
Keywords: generalization
benign overfitting
mild overparameterization
implicit bias

Abstract: Studies on benign overfitting provide insights for the success of overparameterized deep learning models. In this work, we examine whether overfitting is truly benign in real-world classification tasks. We start with the observation that a ResNet model overfits benignly on Cifar10 but not benignly on ImageNet. To understand why benign overfitting fails in the ImageNet experiment, we theoretically analyze benign overfitting under a more restrictive setup where the number of parameters is not significantly larger than the number of data points. Under this mild overparameterization setup, our analysis identifies a phase change: unlike in the previous heavy overparameterization settings, benign overfitting can now fail in the presence of label noise. Our analysis explains our empirical observations, and is validated by a set of control experiments with ResNets. Our work highlights the importance of understanding implicit bias in underfitting regimes as a future direction.

Published as a conference paper at ICLR 2023
BENIGN OVERFITINGG IN CLASSIFICATION: PROVABLY COUNTER LABEL NOISE WITH LARGER MODELS
Kaiyue Wen' Jiaye Teng 12.3.,, Jingzhao Zhang 1.2.3,t
Teng1.2.3. Institute for Interdisciplinary Information Sciences, Tsinghua University Shanghai Qizhi Institute
Shanghai Artificial Intelligence Laboratory
(wenky20, t jy20) @mails t tsinghua. edu. en, jingzhaazemma..tsinnnn edu, cn
ABSTRACT
Studies on benign overfitting provide insights for the success of overparameterizee deep learning models. In this work, we examine whether overfitting is truly benign in real-world classification tasks. We start with the observation that ResNet model overfits benignly on Cifar 10 but not benignly on ImageNet. To understand theoretically analyze
why benign overfitting fails in the ImageNet experiment, benign overfitting under a more restrictive setup where the number of parameters is not significantly larger than the number of data points. Under this mild overpa- rameterization setup, our analysis identifies a phase change: unlike in the previous heavy overparameterization settings, benign overfitting can now fail in the presence of label noise. Our analysis explains our empirical observations, and is validated by a set of control experiments with ResNets. Our work highlights the importance of understanding implicit bias in underfitting regimes as future direction.
INTRODUCTION
Modern deep learning models achieve good generalization performances even with more parame- ters than data points. This surprising phenomenon is referred to as benign overfitting, and differs from the canonical learning regime where good generalization requires limiting the model complex- ity (Mohri et al. 20.8). One widely accepted explanation for benign overfitting is that optimization algorithms benefit from implicit bias and find good solutions among the interpolating ones under the overparametrized settings. The implicit bias vary from problem problem. Examples include the min-norm solution in regression settings or the max- -magiin solution in classification settings (Gunasekar et al. 2018a Soudry al., 2018 Gunasekar et al. 2018b). These types of bias in optimization can further result in good generalization performances (Bartlett et al. [020 Zou ee al. 2021 Frei et al. 2022). These studies provide novel insights, yet they sometimes differ from the deep learning practice: state-of-the-art! models, despite being overparameterized, often do not interpolate the data points (e.g., He al. Devli: Devlin al. (2018)).
We first examine the existence of benign overfitting in realistic setups. In the rest of this work, we term benign overfitting the observation that validation performance does not drop while the model fits more training data points"] [1] We test whether ResNet (He et al. 2016) models overfit data benignly for image classification on CTFAR1O and ImageNet. Our results are shown Figure below.
In particular, we first trained ResNet18 on CIFARIO for 200 epochs and the model interpolates the training data. In addition, we also trained ResNet50 on ImageNet for 500 epochs, as opposed the common schedule that stops at 90 epochs. Surprisingly, we found that although benign overfitting happens on the CIFARIO dataset, overfitting is not benign on the ImageNet datasel-the test loss increased the model further fits the train set. More precisely, the ImageNet experiment does not overfit benignly since the best model is achieved in the middle of the training. The different
Equal contribution.
Corresponding author.
'A more detailed discussion can he found in Appendix R.2 This definition is slightly different from existing thcoretical literature but can be verified more easily in practice.

---

Published as a conference paper at ICLR 2023
100
Accuracy
80-
Accuracy(%))
75
60
70
Train
Train
65
Validation
Validation
300
400
20
50
100
150
200
Epoch
Epoch
(a) ImageNet
(b) CIFAR10
Figure 1: Different Overfitting Behaviors on ImageNet and CIFAR10. We use ResNet50/ResNe118
to train ImageNes/CIFARIU 10 and plot the training loss as well as the validation loss. We find that ResNet50 overfits the ImageNet non-benignly, while ResNet18 overfits CIFARIO benignly.
Classification
Classification Noisy
Regression Noisy
Noiseless
Mild over- parameterization
Benign (Ours)
Not Benign (Ours)
Not Benign
Bartlett et al.
2020
p = (n)
Benign
Heavy over-
Benign
Benign
(Chatterji ct al.
2021
parameterization
(Cao et al.
2021
Bartlett et al. 2020
(Frei et al. 2022
p = (n)
Wang et al. 202Ia)
Zou al.
2021
(Wang al.
2021a)
Table 1:
For classification problems, previous work (Cao et al.
2021 Chatterji et al. 2021 provided
upper bounds under the heavy overparameterization setting. This paper focuses on mild overpa- rameterization setting, and shows that the label noise may break benign overfitting. Similar results were known in regression problems. For regression with noisy responses. [artlett et al. (2020) shows that the interpolator fails under mild overparameterization regimes while may work under heavy overparameterization, as consistent with the double descent curve. However, the analysis under mild overparameterizztion in the classification task remained unknown.
overfitting behaviors cannot be explained by known analysis for classification tasks, as no negative results have been studied yet.
Motivated by the above observation, our work aims to understand the cause for the two different overfitting behaviors ImageNet and CIFAR10, and to reconcile the empirical phenomenon with previous analysis on benign overfitting. Our first hint comes from the level of overparameterization. Previous results on benign overfitring in the classification setting usually requires that p = wn).. where denotes the number of parameters and n denotes the training sample size (Wang et al.) 2021a Cao et al. 2021 Chatterji et al. 2021 Frei et al. 2022). However, in practice many deep learning models fall in the mild overparameterizattion regime, where the number of parameters is only slightly larger than the number of samples despite overparameterization In our case, the sample size n = 10 in ImageNet, whereas the parameter size 107 in ResNets.
To close the gap, we study the overfitting behavior of classification models under mild overparameter- ization setups where p (n)) (this is sometimes referred
the asymptotic regimes). In partieular, following Wang et al] (2021a): Cao et al. (202T) Chatterji et al. (202T): Frei et al. (2022). we analyze the solution of stochastic gradient descent for the Gaussian mixture models. We found that a phase change happens when we move from
Sn log n) (studied in Wang et al. (2021a)) to p = (()). Unlike previous analysis, we show that benign overfitting now provably fails in the presence of label noise (see Table I and Figure 2 This aligns with our empirical findings as ImageNet is known to suffer from mislabelling and multi-labed (Yun et al. 2021 Shankar et al. 2020).
More specifically, our analysis (see Theorem 3.1 for details) under the mild overparameterization (p (m)) setup supports the following statements that align with our empirical observations in Figure and 2
When the labels are noiseless, benign overfitting holds under similar conditions in previous analyses.
When the labels are noisy, the interpolating solution can provably lead to a positive excess risk that does not diminish with the sample size.
2

---

Published as a conference paper at ICLR 2023
4
0.075
4.
0.075
0.075
5
6-
0.050
Heavy
0.050
6-
Heavy
0.050
1o0
07-
Mild
07
Mild
8.
0.025
8
0.025
8.
0.025
9.
9.
0.000
0.000
0.000
6.6 6 &
9 9999997
6 % 9
log
log p
log
(a) Noiscless
(b) Noisy
(c) Early Stop
Figure 2: Phase Transition in Noisy Regimes: parameter size p vs sample size n. We conduct experiments on simulated Gaussian mixture model (GMM) with signal strength = and noise level o = We use SGD train linear classifier and plot the excess risk. The brighter grid means that the classifier has smaller excess error, and therefore does not overfit. Figure (a) and Figure (b) correspond the classifier at the last epoch. Figure (c) corresponds to the best classifier through the course of training.
When the labels are noisy, early stopping can provably lead better generalization performances compared to interpolating models.
Our analysis is supported by both synthetic and deep learning experiments. First, we train linear classifier in Figure 2 Figure (a) shows that training on noiseless data does not cause overfitting, Figure (b) shows that training on noisy data with a label noise ratio 0.4 causes overfitting with mild overparameterization, and Figure (c) shows that applying strly-stopping
the same noisy data can effectively avoid overfitting. Besides, we find that overfitting consistently happens under noisy regimes, despite the theoretical guarantee that the model overfits benignly when p w(n).
Furthermore, our analysis is validated by control experiments in Section 4 with ResNets. We first show that injecting random labels into the CIFARIO dataset indeed leads to the failure of benign overfitting. We further show that, surprisingly, increasing the width of ResNet alone can alleviate overfitting incorrect labels,
theory predicted.
More broadly, the empirical and theoretical results in our work point out that modern models may not operate under benign interpolating regimes. Hence, it highlights the importance of characterizing implicit bias when the model, though mildly overparameterized, does not interpolate the training data.
RELATED WORKS
Although the benign overfitting phenomenon has been systematically studied both empirically (Belkin) et al.) 20186 2019 Nakkiran et al., 2021b) and theoretically (see later), work differs in that we aim to understand why benign overfitting fails in the classification setup. In particular, among all theoretical studies, the closest
to are Chatterji et al. (2021) Wang et al.) (20216) and Cao et al. (00T)) as the analyses are done under the classification setup with Gaussian mixture models. Our work provides new results by moving from heavy overparameterization p w(n) (n). We found that this new condition leads to an analysis that is consistent with our empirical observations, and can explain why benign overfitting fails. In short, compared to all previous studies on benign overfitting in classification tasks, we focus on identifying the condition that breaks benign overfitting in our ImageNet experiments. The comparison is summarized in Table
to mild overparameterization
More related works on benign overfitting: Researchers have made a lot of efforts to generalize the notation of benign overfitting beyond the novel work on linear regression (Bartlett et al. 2020).
e.g., variants of linear regression (Tsigler et al. 2020 Muthukumar et al. 2020 Zou et al. 202 1 Xu
et al. 2022), linear classification (Liang et al. 2020a Belkin al.) (018a) 8a) with different distribution
assumptions (instead of Gaussian mixture model), basdel-based estimators (Liang et al. 2018 2020b
Mei al.] 2022), neural networks (Frei et al. (022). Among them, Cao al. (2022) also identifies
phase change in benign overfitting when the overfitting can be provably harmful with a different data distribution under noiseless regimes.
3

---

Published as a conference paper at ICLR 2023
Gaussian Mixture Model (GMM) represents the data distribution where the input is drawn from Gaussian distribution with different centers for each class. The model was widely studied hidden
Markov models, anomaly detection, and many other fields (Hastic et al.] 2001 Xuan et al. 2001 Reynolds 2009 Zong et al. 2018). A closely related work is Jin (2009) which analyzes the lower bound for excess risk of the Gaussian Mixture Model under noiseless regimes. However, their analysis cannot be directly extended to either the overparameterization or noisy label regimes. Another closely related work (Mai et 2019) focuses on the GMM setting with mild overparameterization, but they require a noiseless label regime and rely on small signal-to-nokes no-noise ratio on the input, and thus cannot be generalized to our theoretical results.
Asymptotic (Mildly Overparameterized) Regimes. This paper considers asymptotic regimes where the ratio of parameter dimension and the sample size upper and lower bounded by absolute constants. Previous work studied this setup with different focus than benign overfitting (e.g.. double descent), both in regression perspective (Hastie et al. 2019) and classification perspective (Sur et al.) 2019 Mai et al. 2019 Deng et al. 2019). We study the mild overparameterization case because generally happens in realistic machine learning tasks, where the number of parameters exceeds the number of training samples but not extremely.
3 OVERFITTING UNDER MILD OVERPARAMETTERIZATONN
We observed in Figure T that training ResNets on CIFARIO 10 and ImageNet can result in different over- fitting behaviors. This discrepancy was not reflected in the previous analysis of benign overfitting in classification tasks. In this section, provide a theoretical analysis by studying the Gaussian mixture model under the mild overparameterivation setup. Our analysis shows that mild overparamettrization along with label noise can break benign overfitting.
3.1 OVERPARAMETERIZZR GAUSSIAN MIXTURE MODEI.
In this subsection, we study the generalization performance of linear models on the Gaussian Mixture Model (GMM). We assume that linear models are obtained by solving logistic regression with stochastic gradient descent (SGD). This simplified model may help explain phenomenons in neural networks, since previous works show that neural networks converge to linear models as the width goes to infinity (Arora et al. 2019 Allen-Zhu et al., 2019).
We next introduce GMM under two setups of overparameterized linear classification: the noiseless regime and the noisy regime.
Noiseless Regime, Let y ~ Unif(-1, 1, E IR denote the ground truth label. The corresponding feature is generated by
x y I",
where denotes noise drawn from a subGaussian distribution, and μ E R2 denotes the signal vector. We denote the dataset D = {(,,, y/) hie()) where (æ;, V:) are generated by the above mechanism.
Noisy Regime with contamination rate p. For the noisy regime, we first generate noiseless data (x. y) using the noiseless regime, and then consider the data point (x, ÿ) where ÿ is the contaminated version of y. Formally, given the contamination rate p. the contaminated label ğ y with probability p and ÿ = y with probability 1 - p. And the returned dataset is D {(x,, 0:))-
For simplicity, we assume that the data points in the train set are linearly separable in both noiseless and noisy regimes. This assumption holds almost surely under mild overparameterizztion. Besides, we make the following assumptions about the data distribution:
Assumption 1 (Assumptions on the data distribution).
A1 The feature noise is drawn from the Gaussian distribution, i.e., N20
|| 2 eyllogn for a given constant c.
A2 The signal-to-noise ratio satisfies a is a fixed constant.
A3 The ratio p/n
The three assumptions all crucial but can be made slightly more general (see Section 5). The first Assumption [Ai] stems from the requirement to derive a lower bound for excess risk under a noisy regime. The second Assumption [A2] is widely used in the analysis (Chatterji al. 2021 Frei et al.)
4

---

Published as a conference paper at ICLR 2023
For smaller ratio, the model may be unable learn even under the noiseless regime and return vacuous bounds. The third Assumption [A3] differs from the previous analysis, where we consider mild overparameteriiztton instead of heavy overparameterrizaton (i.e., w(n)).
2022).
3.2 TRAINING PROCEDURE
We consider the multi-pass SGD training with logistic loss E(w; y) = log(1 + exp(- you w)). During each epoch, each data is visited exactly once randomly without replacement. Formally, at the beginning of each epoch E, uniformly random sample permutation PE {I,..., [ - {1...., then at iteration t, given the learning rate we have
w(t
(()) - (V)
where at) = x ()) (() = (() given E. + i, sin
Under the above procedure, Proposition 3.1 shows that the classifier under the GMM regime with multi-pass SGD training will converge in the direction of the mar-in interpolating classifier.
Proposition 3.1 (Interpolator of multi-pass SGD under GMM regime, from Nacson al. (2019))
Under the regime of GMM with logistic loss, denote the iterates in multi-pass SGD by w(l). Then for any initialization w(O). the iterates w(t) converges to the max max-margin solution almost surely, namely,
(t)
lim +0
(t)ll
2
where v = argmin
|| s.t. w 0; 2 1, v E [n] denotes the max-margin solution.
For simplicity, we denote w4 (t) as the parameter at iteration in the noiseless setting, and w (t) as the parameter in the noisy setting. By the proposition above, we know that both w (Do) and w- (Do) are max-margin classifiers on the training data points. During the evaluation process, we also focus on the 0-1 loss, where the population 0-1 loss is Loi (w) Py(a 0).
3.3 MAIN THEOREM
Based the above assumptions and discussions, state the following Theorem 3.1 indicating the different performances between noiseless and noisy settings.
Theorem 3.1. We consider the above GMM regime with Assumption [A AAI-33. Specifically, denote the noise level by and the mild overpurameterization ratio by r p/n. Then there exists absolute constant C1, 02 C3, C42 Cs > O such that the following statements hold with probability at least 1 c1/n:
Under the noiseless setting, the max-margin classifier w (xx) obtained from SGD has non-vacuous 0-1 loss, namely,
Lo1 (w=( 5n
2. Under the noisy setting, the max-margin classifier w w- ((x)) has vacuous 0-1 loss with constant lower bound, namely, the following inequality holds for any training sample size n,
Lor (ol 2 min ((-2),
P
Cgr
exp
CgT
3. Under the noisy setting, if the learning rate satisfies r) max, [2 there exists time t such that the trained early-stopping classifier (t) has non-vacuous 0-1 loss, namely,
inf Lo (w= (t)) S -4
Intuitively, Theorem 3.1 illustrates that although SGD leads to benign overfitting under noiseless
regimes (statement 1), provably overfits when the labels are noisy (statement 2). In particular, incurs (1(1) eтror on noiseless data and hence would incur 9(1) + error on noisy labeled data,
"The probability is taken the training and the randomness of the algorithm.

---

Published as a conference paper at ICLR 2023
100-
100
100
Train
Train
Accuracy(%)
Accuracy9%
80
Validation
Accuracy(15)
80
Validation
60
60
Train
40
40
Validation
20
0
50
100
150
200
20
50
100
150
200
20
50
100
150
200
Epoch
Epach
Epoch
p
0.1
(b) p 0.2
(c)
0.3
100
100
100
Train Validation
Train
Train
Accuracy
80-
Accuracy(99
Validation
Accuracy(98
Validation
60
60
40
40
20
20
0
50
100
150
200
100
150
200
50
100
150
200
Epoch
Epoch
Epoch
(d) p 0.4
(c) p
0.5
(f)
0.6
Figure 3: Noisy CIFARIO under mild overparameterization. In each experiment, the validation accuracy first increases and then dramatically decreases. This confirms points 2 and in Theorem 3.1 that model would overfit under noisy label regimes.
since label noise in the test set is independent of the algorithm. Furthermore, statement 3 shows that overfitting is avoidable through early stopping.
One may doubt the fast convergence rate in Statement One and Statement Three, which seems too good to be true. The strange phenomenon happens because the high probability guarantee in order O(1/n) with respect to the randomness in the sampling of the training set and the algorithm, and therefore, the expected 0-1 loss is approximately O(1/n) after union bound. We refer to Cao et al. 20221: Wang et al. (22 for similar types of bounds.
Remark (Comparison against heavy overparamettrizzaioon) Previous work usually analyze the GMM model under the heavy overparameterizzation regime, e.g., p U(n²) (Cao al. 2 Chatterji et al. (021) or p = (n log(n)) (Wang et al. 2021a). In comparison, our paper focuses on the mild overparameterizattin regime, where p H(n). We note that this leads to phase change that the overfitting model under noisy settings now provably overfits.
EXPERIMENTS
Theorem 3.1 claims the crucial role of label noise and overparameterization level in benign overfitting. This section aims at providing experimental evidence to validate the statements. However, as the dataset size is upper bounded, the criterion generalization error converges to zero is hard verify in experiments. Instead, we assume that (1) the gap of verification accuracy between the best-epoch model and the last-epoch model can work as an efficient proxy for the gap between the Bayesian optimal accuracy and the validation accuracy of the last-epoch model, and (2) training the model for long-enough epochs can work as an honest proxy for training for infinite epochs. Therefore, as stated in the introduction part, we adopt different notion of benign overfitting, namely, validation performance does not drop while the model fits more training data points. Specifically, we focus on the noisy CIFAR10 10 dataset, where randomly flip a portion of the labels. From the label noise perspective, Section 4.1 demonstrates that ResNets on noisy CIFAR 10 would dramatically overfit non-benignly (c.f., ResNets on clean CIFARIO overfit benignly). From the overparameterization level perspective, Section 4.2 demonstrates that a heavier overparameterization level helps increase the last-iterate performance and hence leads benign overfitting.
Here the convergence with respect the sample size n, as stated in Theorem 3.1

---

Published as a conference paper at ICLR 2023
66
Acc(%)
100
Validation Acc(%)
65
64
40
63
20
50
100
150
200
62
Epoch (W=1)
61
Acc(%)
100
60
Last Epoch
60
59
Best Epoch
40
58
20
100
150
200
1.0
1.5
2.0
2.5 3.0
3.5 4.0
Epoch (W=
Width Factor
Figure 4: Ablation Study Overparameterrzzaton Level. We fix the label noise ratio p 0.2 and conduct an ablation study varying the width factor W of WideResNetl6-W. The left plot validates that generalization performances in the best iterate keep constant while the performances in the final iterate keep increasing, as the width factor increases. The training trajectories for width factors and 4 are shown in the right two plots.
4.1 LABEL NOISE MATTERS: OVERFITTING NOISY CIFARIO
In Section 3.T we prove that under noisy label regimes with mild overparameterization, early-stopping classifiers and interpolators perform differently. This section aims to verify if the phenomenon empirically happens in the real-world dataset. Specifically, we generate a noisy CIFAR I0 dataset where each label is randomly flipped with probability p. We train the ResNets again and the results show that the test error first increases and then dramatically decreases, demonstrating that the interpolator performs worse than the models in the middle of the training.
Setup. The base dataset is CIFARIO, where each sample is randomly flipped with probability E {0.1, 0.2, 0.3, 0.4, 0.5, 0.6). We use ResNet18 and SGD to train the model with cosine learning rate decay. For each model, we train for 200 epochs, test the validation accuracy and plot the training accuracy and validation accuracy in Figure 3 More details can be found in the code.
Figure 3 illlustaates iilluttatsss similar phenomenon to the results linear models under mild overparameteriza- tion analysis (see Section 3.1 Precisely, the interpolator achieves suboptimal accuracy under the mild overparameterizatton regimes, but we can still find better classifier through early stopping. In Figure 3 such phenomenon is manifested as the validation accuracy curve increases and decreases. also notice that the degree becomes sharper as the noise level increases.
4.2 ACHIEVE BENIGN OVERHITTING BY INCREASING OVERPARAMETERIZATINN LEVEL
Theorem 3.1 implies that although noisy label leads bad overfitting, increasing overparameterization can turn overfitting benign. Specifically, when the overparameterizztion ratio r = p/ increases,
The last-iterate classifier (max-margin classifier) may generalize better (see Argument in Theorem 3.1,, since the lower bound exp( Sxt decreases with r.
(2) The early-stopping classifiers have similar generalization performances (see Argument in Theorem 3.1. since the upper bound is in order -4 which converges to zero the sample size goes to infinity.
Figure 2 demonstrates the two observations on the synthetic dataset (linear models). We next show similar observations on noisy CIFAR-10. Specifically, We conduct an ablation study on CIFARIO dataset with fixed label noise ratio P 0.2. We increase the width of ResNets and effectively turn ResNet into Wide- ResNets. By varying the width factor of WideResNet16- W, we show that these observations remain in the deep learning regime.
7

---

Published as a conference paper at ICLR 2023
Setup. The base dataset is CIFARIO, where each sample is randomly flipped with probability = 0.2. We use the WideResNet16-W for W E {1,1.25, 1.5, 1.75,2,3, 4} and use SGD to train the model with cosine learning rate decay. For each model, train for 200 epochs, test the validation accuracy and compare the best validation performance and the validation performance upon convergence in Figure
Figure 4 verifies our theoretical observation where the early stopped classifier enjoys generalization performance nearly independent of overparameterization level, again stressing the necessity study the bias of neural networks beyond the interpolation regime. Besides, we observe that the validation performance of the converged classifier increases with respect the overparameterization level. Moreover, we notice that the increment is more significant for smaller overparameterization level, which is qualitatively similar A Cgr
Sar)
We further observe the epoch-wise double descent phenomenon in Figure where the accuracy first decreases and then increases while the model reaches interpolation (Nakkiran et al.) [2020] Heckel (et al. 202T). Stephenson al. (021) argues that the phenomenon also closely related to label noise and overparametterization level. Their work differs from ours in that they focus studying the training dynamics and removing the double-descen phenomenon. We do not observe a similar phenomenon in the ImageNet experiment with mild overparameterizationn in 500 epochs. We leave the discussion of epoch-wise double descent under mild overparameterization as future work.
5 CHALLENGES IN PROVING THEOREM 3.1
This section provides more details about the three statements in Theorem 3.1 with milder assumptions than those in Assumption
| We also explain why existing analysis cannot be readily applied.
Assumption 2. The following assumptions are more general.
A4 The noise in is generated from o-subGaussian distribution.
A5 The signal-to-noise ratio satisfies || N (2)²
A6 The signal-to-noise ratio satisfies
w
(
We compare the assumptions in Assumption and Assumption 2 Assumption [A4] is relaxation of
Assumption [A1], and Assumption [A5, A6] can be obtained by Assumption [A2, A3]. Therefore, we conclude that Assumption is weaker than Assumption [ We next introduce the generalized version
of the three arguments in Theorem 3.1 including Theorem 5.1 Theorem 5.2 and Theorem 5.3
Theorem 5.1 (Statement One). Under the noiseless setting.for a fixed ò 2 max{ ,eexp( exp((cxpp) under Assumption [A2, A4, A5], there exists constant C > 0 such that the following statement holds with probability at least 51.
Loi (w+((o))) (oo)) S nn
Theorem 5.1 implies that the interpolator under noiseless regimes converges to zero as the sample size n goes infinity. The proof of Theorem 5.1 depends on bounding the projection the classifier w f1-direction, which relies on sketch of the classification margin. We defer the whole proof to the Appendix due space limitations.
Previous results noiseless GMM (e.g., Cao et al. (2021 Wang et al. (021aa) rely the heavy overparameterizztiin p w(n) and assumption (2)
In contrast, our results only
require |+|| > (2) well |u|l 2 cvlog and therefore, be deployed in the mild overparameterization regimes. Therefore, the existing results cannot directly imply Theorem [.]]
Theorem 5.2 (Statement Two). Under the noisy regime with noisy level and mild overparameteri- zation ratio r = p/n.for fixed 82 2 max(exp(- (ccp)) ey exp(-C107" n)), under Assumption [AI, A3], there exists constant C3 such that the following statement holds with probability at least - 52.
Loi Loi(w-(o0)) 2 min (
P.
exp
(-Ox))
C3r
}
C3T
P
Therefore, w-(0s (00) has constant excess risk, given that and p are both constant.
8

---

Published as a conference paper at ICLR 2023
proves constant lower bound for interpolators in noisy settings. Compared The- orem 5.1 Theorem [5.2] show that noisy and noiseless regimes perform differently under mild overparametterizatonn. The core of the proof lies in controlling the distance between the center of wrong labeled samples and the point μa, which further leads to an upper bound of | w (oo) One then derive the corresponding 0-1 loss for classifier w w-(ww)))))) (oo). We defer the whole proof to the Appendix due to space limitations.
Theorem 5.2
Previous results (e.g., Chatterji et al. (2021): Wang et al. (0211)) mainly focus on deriving the non-vacuous bound for noisy GMM, which also relies on the heavy overparamettrization assumption p (().. Instead, our results show that the interpolator dramatically fails and suffers from constant lower bound under mild overparameterization regimes. Therefore, heavy overparameterization performs differently from mild overparameteriration cases. We finally remark that although it is still an open problem when the phase change happens, we conjecture that realistic training procedures are more close to the mild overparamettrization regime according to the experiment results.
Theorem 5.3 (Statement Three). Under the noisy regime, consider the learning rate TI max, || where (æt; 'D denotes the data point. For a fixed 83 Z
"
max 91l C12 oxp(-c13722)}, under Assumption [A2, A4, A6], the following statement holds with probability least 63.
inf Loi (w-(1) S exp (-ou4
||||
Therefore, the bound converges to zero as sample size n goes to infinity under Assumption [A6].
Theorem 5.3 derives that the bound again converges to zero by considering early-soopping. Studying carly-stopping classifiers meaningful since people usually cannot ideally obtain the interpolation during training in practice. The derivation of Theorem 5.3 relies on the analysis of one-pass SGD, Different from the previous approaches where we can directly assume [[w][ = |>>]l))| without loss of generality, the classifier w- (t)() is trained in this case and we need to first bound it. We then define a surrogate classifier and show that (a) the surrogate classifier is close the trained classifier for a sufficiently small learning rate, and (b) the surrogate classifier can return satisfying projection on the direction μ. Therefore, we bound the term μ w (1)]|[ww(( (B)] which leads the results. We defer the whole proof to the Appendix due space limitations.
One may wonder whether we can apply the results of stability-based bound (Bousquet et al. 2002; Hardt et al., 2016) into the analysis since the training process is convex. However, the analysis might not be proper due to a bad Lipsehitz constant during the training process. Therefore, the stability-basee analysis may only return vacuous bound under such regimes. Besides, the previous results on convex optimization with one-pass SGD (e.g., (Sckhari et al.] (202I) cannot be directly applied to the analysis since most results one-pass SGD are expectation bounds, while we provide a high probability bound in Theorem 5.3
CONCLUSIONS AND DISCUSSIONS
In this work, aim to understand why benign overfitting happens in training ResNet on CIFARI 10, but fails on ImageNet. We start by identifying a phase change in the theoretical analysis of benign overfitting. We found that when the model parameter in the same order as the number of data points, benign overfitting would fail due to label noise. We conjecture that the noise in labels leads to the different behaviors in CIFAR 10 and ImageNet. We verify the conjecture by injecting label noise into CIFAR10 and adopting self- trainiiiin in ImageNet. The results support our hypothesis.
Our work also left many questions unanswered. First, our theoretical and empirical evidence shows that realistic deep learning models may not work in the interpolating scheme. Still, although there larger number of parameters than data points, the model generalizes well. Understanding the implicit bias in deep learning when the model underfits is still open. A closely related topic would be algorithmic stability (Bousquet et al. 2002, Hardt et al. 2016), however, the benefit of overparameterization within the stability framework still requires future studies. Second, the GMM model provides a convenient way for analysis, but how the number parameters in the linear setup relates to that in the neural network remains unclear. Third, although the conclusions in this paper can be generalized to other regimes, e.g.. GMM with Gradient Descent, the possible extension to neural networks as in Cao et al. (2022) is still unclear and will consider that in future works.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Jingzhao Zhang acknowledges support by Tsinghua University Initiative Scientific Research Program.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 242-252. PMLR, 2019. URL http:::/proooooeengggg mlr. www.srrsspppeppppp v9t
len zhu 19al99.. html
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 2019. URL http://
proceedi ngs ml www....reersvvv / aroral 9a html
Hessam Bagherinezhad, Maxwell Horton, Mohammad Rastegari, and Ali Farhadi. Label refinery:
Improving imagenet classification through label progression. CoRR, abs/1805.02641, 2018. URL
http::/arx: wtggga/bb/////// 02641
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063-30070 2020.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint.
Acta numerica, 30:87-201, 2021.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances in neural information processing systems, 31, 2018a.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference Machine Learning, pp. 541-549. PMLR, 2018b.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern Beccine-learning practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, 116632))5589-118854., 2019.
Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499-526, 2002. URL http::ttt//mlmmm wttpppappes/////esseseeees
html
Carla E. Brodley and Mark A. Friedl. Identifying and eliminating mislabeled training instances. In William J. Clancey and Daniel S. Weld (eds.), Proceedings of the Thirteenth National Con- ference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 96, IAAI 96. Portland. Oregon, USA, August 4-8, 1996, Volume 1, pp. 799- 805. AAAI Press / The MIT Press, 1996. URL http: wwww aaai wwwoorg//bbbb.e Litp//arbaaaaaaaaaaaaaaaaaaaaaaa 1996/ 2eto//aaa96-11111 php
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for pver-parameterizze max- imum margin classification sub-gaussian mixtures. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Ad- vances Neural Information Processing Systems 34: Annual Conference on Neural In- formation Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 2021. URL https://proceeeinnn http:///ww....urs..eeeeeea//aaaa http://wweoooooo...oooooo///aaaa
46e 2at.aaaa2222277777effeeee [B wbw.:/bsssoc---Ataaaaaaaaa html
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. arXiv preprint 22X.022202.06526, 2022.
10

---

Published as a conference paper at ICLR 2023
Niladri S. Chatterji and Philip M. Long. sinite-sample analysis of interpolating linear classifiers in the overparameterized regime. J. Mach. Learn. Res., 22: 11:1129:11100 122::30, 2021. URL http: 7/
html
Alex Damian, Tengyu Ma, and Jason D. Lee. Label noise SGD provably prefers flat global minimizers. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 27461, 2021. URL httptttt///prrcccdiiigieooo newrips cctppaptre/02//haaall. e6.1400022211000eaee882266533880
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. CoRR, abs/191 2019. /RLhttp: http://arxiv
org/abs/ 05822
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1 2018.
Spencer Frei, Niladri S. Chatterji, and Peter L. Bartlett. Benign overfitting without lincarity: Neural network classifiers trained by gradient descent for noisy linear data. CoRR, abs/2202.05928,, 2022.
URL htttttt///xxxiii org/ abs 2202. 05928
Donghai Guan, Weiwei Yuan, Young- Koo Lee, and Sungyoung Lee. Identifying mislabeled train- ing data with the aid of unlabeled data. Appl. Intell., 35(3):345-358, 2011. doi: 10. 1001/ s10489-010-0225-4
Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmüsssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1827- 1836. PMLR, 2018a. URL httt:::/prcceeeinnggg// m..r. www.ppeessseee html
Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradi- ent descent on linear convolutional networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9482-9491, 2018b. URL http:ttttp/socceeeeeeeee http:///pppoeeeddnnn...e..p..p cC httpseccppppppppeeeee httppaappp//////a// /201e//211//// 2018//a28/ hash/ De
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1225- 1234. JMLR.org, 2016. URL htttt::/pproceeiinte
mlr walrrpresssee titeess/44//aartee
Trevor Hastie, Jerome H. Friedman, and Robert Tibshirani. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Springer, 2001. ISBN 978- 198-1- doi: 978 387 20666-266666- 60665
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. CoRR, abs/1903.08560, 2019. URLhttp:
//a //arxiv. otg. aba /aaas///1/..... 08560
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV. USA, June 27-30, 2016, pp. 770-778. IEEE Computer Society, 2016. doi: 10.1 109/CVPR.2016.90 6.90. htt.htts::/// //dotps:://o...
http:///oo.oo////////// www.oo.g/..ooooo 09 CVPR R. 20 6. 90
11

---

Published as a conference paper at ICLR 2023
Reinhard Heckel and Fatih Furkan Yilmaz. Early stopping in deep networks: Double descent and how to eliminate it. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL URJjattpss//pppeeeeiiss
forum? 1 1V9 jw7bb
Lang Huang, Chao Zhang, and Hongyang Zhang. Self-adaptive training: beyond empirical risk minimization. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Aesan--Tien Lin (eds.). Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 6-12. 2020, virtual, 2020. URL httpt:s:://occeeeee neurips.
60ab531ec31216131 49012226666551100000000000000220 www.:0000000000eeeeeeeeeeee----0 www.eeewwpp.pppppeeeeeeeeeeeeeee hctpppppprr/222//aaaaaaa
.ttll
Jiashun Jin. Impossibility of successful classification when useful features are rare and weak. Proceedings of the National Academy of Sciences, 106(22):885-88866 2009.
Tengyuan Liang and Alexander Rakhlin. Just interpllate::: Kernel "ridgeless" regressioo generalize. CoRR, abs/ www./808.00 00380,037700000 2018. /
Tengyuan Liang and Pragya Sur. A precise high-dimensionall asymptotic theory for boosting and min-ll-norm interpolated classifiers. CoRR, abs/2022.01586, 2020a. URL htttt:://aaaat
01586
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-nowe norm interpolants and restricted lower isometry of kernels. In Jacob D. Abernethy and Shivani Agarwal (eds.), Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz. Austria]. volume 125 of Proceedings of Machine Learning Research, pp. 2683-2711. PMLR, 2020b. URL http::/prrcceednng/ mlm www.ppresssll... http:/ainn2220. 0tm2mmllll
Xiaoyi Mai and Zhenyu Liao. High dimensional classification via empirical risk minimization: Improvements and optimality. CoRR, abs/1905. 2019. /tt/tttp://rxxi org/ /bs/ 1905.1374
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborová. The role of regularization in classification of high- nigh-dimensional noisy gaussian mixture. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 6874 6883. PMLR, 2020. URL httt::ttt///oceeeeeee
mmlr. www.ppeessvlll https////w11///m/mccc/oo/oo// .html]
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpola- tion of noisy data in regression. IEEE Sel. Areas Inf. Theory, 1(1):67-83, 2020. doi: 10.1109/ 2aa..2020.29847166 URL htt.httpp://dd org 110900....1.a..... 2020. 20t.l22242...2222..2222
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference on Artificial Intelligence and Statisties, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan. volume 89 of Proceedings of Machine Learning Research, pp. 3051- PMLR, 2019. URL http::::/ppoooeeeigggs...t http://rccccccnn......rrreeeeeee nacson 1 9a. html
Preetum Nakkiran and Yamini Bansal. Distributional generalization: Structure beyond test emror. 2021a.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htttttttp:/:/pereeeee ew. net wwt.:/eetett//ae. www.mooommmmrrrmmm 5554t4t
12

---

Published as a conference paper at ICLR 2023
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 202 (121(12) 2021b.
Douglas A. Reynolds. Gaussian mixture models. In Stan Z. Li and Anil K. Jain (eds.), Encyclopedia of Biometrics, pp. 659-663. Springer US, 2009, doi: 10. https: org/10 1007/978 0 387 73003- 196
URL
Ayush Sekhari, Karthik Sridharan, and Satyen Kale. SGD: the role of implicit regularization, batch- size and multiple-epochs. In Mare" Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.). Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 27422 27433, 2021. URL -at.raabdccccaaeeeeeaaaaaaree... .tmml
neur.ps.............p........... cc/ Abst
Vaishaal Shankar, Rebecca Roclofs, Horia Mania, Alex Fang, Benjamin Recht, and Ludwig Schmidt. Evaluating machine accuracy on imagenet. In International Conference on Machine Learning, pp. 8634-8644. PMLR, 2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, and Nathan Srebro. The implicit bias of gra- dient descent on separable data. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. htLhtttps//opeezee/// net.iiewwweeeteeee.ee http:/oooommmddd11g3gg1
Cory Stephenson and Tyler Lee. When and how epochwise double descent happens. CoRR, abs/2108. 12006, 2021. URL hatapp::/aaxxxv..rrr/aba/////
12006
Pragya Sur and Emmanuel J Candès, A modern maximum-likelihodd theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, (16(29):14516-149) 2019.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286, 2020.
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of gaussian mixtures. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2021, Toronto, ON, Canada, June 6-11, 2021, pp. 4030 4034. IEEE, 2021a. doi: 10. 1999CSSSS933 2021.94 .413946.. URL https: doi. wtt.://0../......1.A............ Tww.110//AAASS99990
2021. 9413946
Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass Ranzato, Alina Beygelz-
classification: All roads lead to interpolation. In imer. Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Informa- tion Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 24164 .eriigss...i...... wwwpppppee//2///aaeeeeeee 24179, 2021b. URL wbw.ceeddeoeooeoooooooeeeeeeeeee Abst Abstraaatttbeeettttttttt.. caaa29eab7262311ne (22.333100aa22fff2feee2
Jing Xu, Jiaye Teng, Yang Yuan, and Andrew Chi-Chih Yao. When do models generalize? a perspective from data-algorithm compatibility. arXiv preprint arXiv:2202.00 060044444 2022.
Guorong Xuan, Wei Zhang, and Peiqi Chai. EM algorithms of gaussian mixture model and hidden markov model. In Proceedings of the 2001 International Conference on Image Processing. ICIP 2001, Thessaloniki, Greece, October 7-10, 2001, pp. 145-148. IEEE, 2001. doi: 10.1 0581.95 URL hallhttps://eee
wrg/ooggr/oo..... 10. 1109/ ICIP 2001 958974
Sangdoo Yun, Seong Joon Oh, Byeongho Heo, Dongyoon Han, Junsuk Choe, and Sanghyuk Chun. Re-labeling imagenet: from single to multi-labels, from global to localized labels. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pp.
2021.
Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Dae-ki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver. BC. Canada, April 30- May 3. 2018, Conference Track Proceedings. OpenReview.net, 2018 URL https 7/openrevicn ew net. oopegrrrreer.eee//ooommm........
13

---

Published as a conference paper at ICLR 2023
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Benign overfitting of stnesant-stepsize SGD for linear regression. In Mikhail Belkin and Samory Kpotufe (eds.), Conference Learning Theory. COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 4633-4635. PMLR, 2021. URL http:://rroceedingg m www.sres///ee 000oss/s/34//ou2222 htm
14

---

Published as a conference paper at ICLR 2023
Appendix
A ADDITIONAL RELATED WORKS ON LABEL NOISE
Label noise often exists in real world datasets, e.g., in ImageNet (Yun al. 2021 Shankar et al. 2020). However, its effect generalization remains debatable. Recently, Damian et al. (2021) claim that regression settings, label noise may prefer flat global minimizers and thus helps generalization. Another line of work claims that label noise hurts the effectiveness of empirical risk minimization in classification regimes, and proposes to improve the model performance by explicit regularization (Mignacco et al. 2020) robust training (Brodley al. 1996 Guan et al. 2011 Huang et al. )020). Among them, |Bageeinezzhdd et al. (2018) studies how to refine the labels in ImageNet using label propagation improve the model performance, demonstrating the importance of the label in ImageNet. Besides, Nakkiran et al. (2021a) find that interpolation does harm to generalization in the presence of label noise. However, they do not relate their findings with the scale of overparameterization. This paper mainly falls in the latter branch, which theoretically analyzes how label noise acts the mild overparameterization regimes.
B DETAILED PROOFS
B. PROOF OF THEOREM
The first statement in Theorem 3.1
states that the interpolator has non-vacuous bound in noiseless setting, which is a direct corollary of the following Theorem 5.1 The proof of Theorem [.] mainly depends on bounding the projection of the classifier w μs, which relies on sketch of the classification margin.
Theorem 5.1 (Statement One). Under the noiseless setting, for a fixed ō, 2 max n. exp((cap) under Assumption [A2, A4, A5], there exists constant C2 > 0 such that the following statement holds with probability al least 1 51.
Lorlw+ (0o)) S
denote the classifier w. (oo) by u during the proof for simplicity. Due to Proposition 3.1 the final classifier converges to its max-margin solution. Without loss of generality, let the final classifier w satisfy ||||| since is max max-margin solution:
Proof of Theurem 5.7
1. Therefore, the following equation for margin 7(-) holds
>ww) 2 (p/ (H/llA))
where ( (w) = min; y w denotes the margin of classifier w for the dataset. We next consider the margin for the classifier ///|paa|. Note that the margin be rewritten as
min y pf ||ll
=min (va + o ///llllll
=Ilea]| + min yee p///
|||l|| max lyee p//lpa/l]l
We note that yick /1/ | is o-subGaussian due to the definition of subGaussian random vector. Therefore, due Claim C.I. we have
(w) 2 ( 2 |||||| - o log 2 ||
where the last inequality is due Assumption [A2].
We next bound the term T w via the above margin. From one hand, we notice that by the definition of the margin function,
7ww) = min y w 2 ||
(1)
15

---

Published as a conference paper at ICLR 2023
From the other hand, we rewrite the margin
min y;
w min w
(2)
Sp
T w
y:c, w.
VE(n]
The right hand side can be bounded as
Σ (c(n)
y _ w
1
y:c;
(3)
71 iE|n]
p
Sa
where the final equation due to Claim and Equation 3 we bound the projection of w+ μ
C.2
Therefore, combining the above Equation
Equation
|lll
where the last equation is due Assumption [A5]. We rewrite Equation 4 μ 2 cs |All then we can bound the 0-1 loss as follows for a given constant Co:
Loi (w) = =Pyyx < <0)
=P(μ T w + y:c ur 0)
=P(ye' w S -p w)
<P(ye' 'w S -callall)
S exp (-co ||1112
Due to Assumption [A2], ||pl1/0 > cylog n, and therefore, by setting C2 = c6c?, we have
Loi (w) S =
The proof is done.
B.2
PROOF OF THEOREM 5.2
Theorem 5.1 shows that the interpolator can be non-vacuous under noiseless regimes with mild overparameterization However, things can much different in noisy regimes. Statement Two proves vacuous lower bound for interpolators in noisy settings, which can be derived by the following Theorem 5.2 The core of the proof lies in controlling the distance between the center of wrong labeled samples and the point μ., which further leads to upper bound of | ( One can then derive the corresponding 0-1 loss for classifier w (oc).
Theorem 5.2 (Statement Two). Under the noisy regime with noisy level and mild overparameteri- zation ratio p/n, for a fixed 82 2 max A3], there exists constant C3 such that the following statement holds with probability at least 52.
ey exp(-c1on) n)) under Assumption (AI,
Loi(w- 2 min (-2),
P.
(-car)
C3r
exp
C3T
Therefore, w-(08 (00) has constant excess risk, given that and p are both constant.
16

---

Published as a conference paper at ICLR 2023
Proof. We denote w (-o) as for simplicity, and assume that ||/||| = 1 without loss of generality. Let denote the original label and ý denote its corrupted label.
Without loss of generality, consider those samples with y4 1 while jt 11, which are indexed by = {i: yt 1, Di -1). -1.. Consider the center point of K. which is
Σ x4 KEK
Σ IE
Σ
Ui
5==
E
K
K.
EEK
IEK
Due to the interpolation in Proposition 3.1 and ÿ 1, derive that
= < O.
(5)
Case 1: 14" w < O. In this case, L01 (w) naturally has a lower bound of 1/2 since it even fails in the center point μr.
Case 2: p w > O. In this case, the classifier w satisfies w >> 0 and xx < 0. Therefore, the distance between and æK must be less than the distance from to its projection on the separating hyperplane that perpendicular to through the origin. Formally,
1 T w S | Hill
Σ E FEK
Note that e; is independent and o-subGaussian, and therefore applying Claim
have that Eiec <ill S o I2i Besides, we derive by Claim C.3 that [C]] Z pn. Therefore,
C.2
d [C]
P p
1 w| S
S
o
(6)
SEK
We next consider the corresponding test error w, where we consider the test error on noiseless regime instead of noisy regime. Note that the two arguments are equivalent, we refer to Claim C.4 for
more details. We rewrite Equation as |p= w < c
K S S d. where we abuse the notation
c > 0 as a fixed constant. Therefore,
Plyx w < <0)
=P =Pyye T -14 w)
Pyy T w/ -c
P
pn
- pm
where e is sampled from Gaussian distribution, and t denotes the CDF of standard Gaussian Random Variable.
Case 1. c pa < 2, then 4 (-c
P 4(-2).
pa
Case 2. If c / pn Therefore, Φ1 $1-c,/
note that (--t) > ! }) (xp(())/2) 2 1/xexp(-f/22 if 2.
+ exp(
2 p
- pm
exp( -2 L)
2
Taking the above two cases together and denoting r = p\ n. we have
03
Loi (w) 2 min
क ()-2)) car
exp(
which is constant lower bound under Assumption [A3]. The proof is done.
17

---

Published as a conference paper at ICLR 2023
B.3 PROOF OF THEOREM 5.3
We apologize for the following typos made in Theorem 5.3 in the main text. For consistency, the dimension d should be written as p and the learning rate X should be written as v. Furthermore, Theorem 5.3 needs an initialization from zero during the training, which is widely used in linear models Bartlett et al. 2020).
Statement Two shows that the interpolator fails in the noisy regime with mild overparameterization. How can we derive a non-vacuous bound under such regimes? The key is early-stoppins To show that, Statement Three provides non- vacuous bound for early-stopping classifiers in noisy regimes, which is induced by the following Theorem 5.3
Theorem 5.3 (Statement Three), Under the noisy regime, consider the learning rate con max; ||:1| where (æ,, M.) E 'D denotes the data point. For a fixed 85 z max Sin, probability at least - 63.
12 C12 exp(-c137'n)), under Assumption [A2, A4, A6], the following statement holds with
|| ||| +
inf Lo (t)) cxp (-014 tSn
Therefore, the bound converges zero as sample size n goes to infinity under Assumption [A6].
To show the relationship between Theorem 5.3 and Theorem 3.1
directly Assumption [A2, A3] in Theorem 553 to reach generalization bound in Theorem 3.1 (Statement Three). The derivation of Theorem 5.3 relies the analysis on one-pass SGD, where we show that one-pass SGD is sufficient to reach non-vacuous bound. The proof of Theorem 5.3 again, relies on bounding the but in different way. Different from the previous approaches where [w- [Ic) |--
directly assume 1, the classifier w- (t) is trained in this case and we need to first bound We then define surrogate classifier and show that (a) the surrogate classifier close to the trained classifier for sufficiently small learning rate, and (b) the surrogate classifier can return satisfying projection on the direction μ. Therefore, we bound the term μ w (t) (8)] which leads the results.
Proof. We abuse the notation wn, to represent w-( which is returned by one-pass SGD. We first u. lower bound the term p [[,,] where (s is the optimal classification direction. To achieve the goal, we
bound the term μ wn and ||w,,|| individually.
Before diving into the proof, we first introduce surrogate classifier w., = 3, From the definition, we have that for update step size 17.
exp xxp(-y;a0,00)
Wi-1 Wi + n
+ exp( -y;,,;
(8)
1
i = w. + 2 na.
Therefore, we have that
Wi+1 10:+1 11 Σ
Fzii exp( 1 wi)
2(1 expl a1 w:
(9)
exp( exp(- wi) 1 2(1 + exp( a wi))
W1+1 1 0z+1 1) / x,10
Σ
Bounding the term ft J w. We fist bound the different between μ w. and μ w. We note that
To bound the above different, the fist step is to bound the term max / w.hr Since 2 Tuez) T is o-subGuassian, we have that with probability ô with 8, 1/n
max 112 Gel S 2 (e T cel S $1 2 +||||| (ol((n/1))n)))) & tE[n]
(10)
18

---

Published as a conference paper at ICLR 2023
expí Ni m=)=1 We then bound the term 2 j.m; wx)) Note that [ep(()) - 1 S 2/u when |u| < 2.2 By the
iteration in Equation 8
we have that
max mn]
| S mn( t [|æ:|]),
x wtl & mry(max || x |. - 2
max tE(n]
where the first equation is due the iteration, and the last equation is due to S max, |aas setting Cs 2). Therefore,
(by
exp( 3 wi)
exp( -- we)
S a we S 2
(11)
2(1 + exp( (op(--jehh y w;))
2
Combining Equation 10 and Equation
11
we have that with probability least 51.
max [n]
I w. pe wel S mallaal??
(12)
On the other hand, we show the bound for je w.. Note that wh++ 1/2 FtSt, therefore,
2
|||l1 1
1 E P TTcch.
Σ
L(p)
rry
LEIm]
[E|m]
where denote [x(p) { (-1, 1) random variable which takes value - with probability p and takes value +1 with probability
Due to Claim C.3 have 1 n E. H(p) Z P. where note that I(pp) 13. Besides, since 6 is || o-ubaaassiann have that with probability 1 1-4 m
Σ HTe E.i Te S || log(n).
TEjN
where the term (ng(n) comes from the probability 1/n. In summary, we have that
2 μ w. 2 pl Ialloa/ 2 ||all
(13)
nn
where the last equation follows Assumption [A2]. Combining Equation
12) and Equation 13 we have
μ w. 2 μ4 w T wn μ wnl Z m|||111
(14)
We additionally note that Equation 14 holds by choosing proper constant in Equation choice of r)). Bounding the norm [w, /l- We next bound the norm | Note that
(and in the
[w,)) ||. Before that, we first bound the norm
max <E[T]
|KDe||
max
Σ
x:9ill
#E[T]
xE[e]
||Aa"
Σ T((P) +
Σ
:E[T]
sE(t]
iE[t]
(15)
< max
||.a*
Σ
[e(P)l
+ Σ
6
xE(7]
=E(()
sc[t]
STl| + o /TT
where the last equation is due Claim
C.2 by choosing probability 8 2 exp(-p)/m -p)/n.
19

---

Published as a conference paper at ICLR 2023
Therefore, have
sup xE(x)
||لي|| S mellaal + no /pn.
Note that according to the iteration in Equation we have that
|| r S 1pt max || 1 wrll S |10zell
where the last equation is due 2n max; || Therefore, we bound the norm wo, as
i. + || S 1 1ma 1| + ||
|| |m,
||
|| [2,
24 VA 14 14
Ww- 21l + 1 1ll |
(16)
2mml |al| 110 /
||||
+
170 pnn.
Combining Equation
14 and Equation 16 we derive that with probability at least 1 c/n,
p wn
mym 2
(17)
Ilw,lll
mno
| + V
We next consider the probability on the test point, note that given the dataset (æ;, Vi) and taking probability on the testing point (ær, y), we have
(-c (+ w)²
F(yæ T < 0) IP(y T w/|[w/] -1 -ewT///laeee w//ww/l S exp
(-e 2
| 12r
where yæ T w = μ w + ye'
The w and ye w w/|lw|| o-subGaussian. Plugging Equation 17 into the
above equation, have that with high probability,
Plyæ w 0) exp (-e14
10 ||
20 + 04
If fllll///> Vp/n.
||ll InPooto 2 11111/0.
||||| If [|ll//o < vp/n, 1
||i 2 o² Vn/p, which is large when // w(pp/))
Therefore, the above bound is non-vacuous if || w((p/n)1/4)
Note that for given constant r p/n, under Assumption [A2]. we have
|
Plyæ T w < <0) < exp (-C14
S exp
(cc1 o2
nes
2 + 1
The proof is done.
C TECHNICAL LEMMAS
We next provide some technical claims. The first claims bound the maximum of a sequence of subGuassian random variables:
Claim C.1 (Maximum of sequence of subGuassian random variables.). For a sequence of a- subGaussian random variables XI,...,X, E We have that with probability at least
max X,I S V20 (22o(1log log + Aoggn+Vloglll Vlog(1/8))
Specifically, under the condition that 5 Z 1/n, we have
max [Xil I / llogllog.. logn. n.
20

---

Published as a conference paper at ICLR 2023
Proof of Claim C.7 By taking union bound, have
P(max X; u) PP(3: X; u)
S nPi(X u)
u12
S <nexp(- 20²
By setting (20(Vlog + Vlog(1/6),
we have
PP(max X; 2 20 logn + (log(1/0)))
<nexp( Voo( logn + vlog(1/8))
20²
(oosp(-(Vlogra) + Vlog(1/6))))
/log(n) v1/5)
expl - pepp--log(1//))) log(1/6)
<d.
Therefore, with probability least have
max Xx S V2oll log + Vlog(1/6)
The next claim bounds the norm of sum of epsilon.
Claim C.2. Under Assumption [A4] which assumes that e, subGaussian, have that with probability at least 8,
P + 2
log(1/5)
E,
< 40 V
iEin]
Specifically, under the condition that 5 2 exp( Ap). it holds that
p. n
72
iE(n]
Proof. Note that since e; o-suuGaauss,an, its summation Σie(n) E; is subusuaaan
Therefore, we have that
Σ c: |E(p)
I 40
P
20
log (1/8)
72
n
The next claim shows that the number of noisy data is approximately in the same order with pn. Claim C.3 (Number of noisy data), Denote [K] the number of samples with flipped labels. With probability at least - 8. there exists constant such that
||C| - pm] S / en log(2/8).
Furthermore, when 8 2 2exp 1 p²²n) we have that with probability at least 1 8.
3
AC こツ 2 pn and |C S pn.
21

---

Published as a conference paper at ICLR 2023
Proof. Note that K Σ; Mg where u, are drawn from independent Bernoulli distribution with parameter p. Therefore, by Hoeffding's inequality, there exists constant c such that with probability
ct² 1 2exp n1
| pml S
By setting t V log(?): we have that with probability at least 6,
[ prd - log 5).
We then rewrite the constant to reach the above conclusion.
The next Claim C.4 shows that analyzing Loi loss on noiseless data is sufficient under noisy regimes.
Claim C.4. Under the noisy regime, the 0-1 population loss on noiseless data Loi (w) P(yx w 0) has the same order with the 0-1 population loss (excess risk) on noisy data La (w) 1) Fiw w 0) - 77. Therefore, we analyze Coi (w) in this paper as surrogate of Loi (w)
Proof. Note that we here consider the Coi on the noiseless data, and one can get for on the noisy data by just adding p Coi. That is to say,
Eo1 Pÿx w < 0)
- - yx w < <0)
T < <0)
77 Cos) + (1- n)-
=1 + (1 - 2n) L0t,
And therefore o.1 17 has the same order with Co--
D EXPERIMENTS
D. IMPLAMENTED TASKS
We conduct experiments three public available datasets along with synthetic GMM data. First, briefly introduce each dataset.
ImageNet is image classification dataset containing 1.2 million pictures belonging to 1000 different classes. CIFARIO an image classification dataset containing 60000 pictures belonging 10 different classes. Penn Tree Bank(PTB)
dataset containing natural sentences with 10000 different tokens. We use this dataset for language modelling task. Synthetic GMM data is generated
following the setup in Section 3.1 We generate data for (24 (2.,..., 29 29),y (24 ,..;".. 29) }
{0, 0.4). | = 40, α = 1, n2 S
We then describe experiment details for each dataset.
For ImageNet, we train ResNet50 from scratch. We use standard cross entropy loss. We first train the model for 90 epochs using SGD as optimizer, with initial learning rate le-1, momentum 0.9 and weight decay 1e-4. The learning rate will decay by factor of 10 for every 30 iterations. Then we train the model for another 410 epochs, with initial learning rate 1e-3. 3,momentum 0.9 and weight decay 1e-4 4 and learning rate will decay by a factor of 1.25 for every 50 iterations.
For CIFAR10, we randomly flip the label with probability {0, 0.2, 0.3, 0.4, 0.6) and for each train ResNet18 from scratch. We use standard cross entropy loss. We train each model for 200 epochs using SGD as optimizer, with learning rate 1e-1. momentum 0.9 and weight decay 5e-4. We use cosine learning rate decay scheduler. For ablation study, we fix the flip probability to be 0.2 and train WideResNet16-I W on the noisy dataset with W E 1.25, 1.5, 1.75, 2,3,4. 4. We repeat each experiments for four times. We train each model for 200 epochs using SGD as optimizer, with learning rate 1c-1, momentum 0.9 and weight decay 5e-4. 4. We use a cosine learning rate decay scheduler
22

---

Published as a conference paper at ICLR 2023
20.0
5.5
17.5
15.0
12.5
train
Loss
4.5
train validate
10.0
validate
7.5
5.0
2.5
3.5
0.0
1000
2000 3000 4000 Epoch
0
20
40
60
80
100
120 140
Epoch
(a) PTB Adam
(b) PTB SGD
Figure 5: Overfitting Behavior for language modelling. We transformer train language modelling on Penn Tree Bank and plot the training loss as well as validation loss. We find that transformer overfits Penn Tree Bank significantly.
For Penn Tree Bank, we train standard transformer from scratch. We train one model for 4800 epochs using ADAM optimizer, with learning rate 5e-4, beta (0.9, 0.98) and weight decay 1e-2. use an inverse square learning rate scheduler. We train another model for 140 epochs using SGD optimizer with learning rate 5.0. We use step learning rate schedule with step size I and gamma 0.95.
For Synthetic GMM data, we train linear classifier for each dataset, initialized from 0. We use logistic loss. We train each model using SGD as optimizer with learning rate le-5 until training loss decrease below 0.05.
D.2 OVERFITTING ON PTB WITH LANGUAGE MODELLING
In this subsection, we show that the training a small Transformer on PTB for language modelling also leads to overfitting, shown in Figure 5 This is expected based our analysis. If view language modelling as a classification task: predicting the next word based on a prefixed sequence, then the ground truth label will naturally be noisy.
D.3 MORE GMM EXPERIMENTS
We hereby present more GMM experiments results. We consider signal-to-noise ratio between {10, 20, 40, 80, 160) and the result is shown in figure Notice that according theory, roughly separate the GMM models into three cases ignoring some technical conditions.
Case || (((/n))//1 which corresponds to the case where [A6] doesn't hold. In this case, as the signal-to-noise ratio too small, even on noiseless data, the model will suffer constant excess risk.
Case
||al//o ((p/n)2//4 + vlog n) while p (n). In this case the signal-to-noise ratio is great enough, however the overparameterization is mild, hence although the model can benign overfit on noiseless data, it will fail benigh overfit noisy data. However early stopping on the noisy data will still gives classifier that have nonvacuous generalization guarantee.
Case 3 || ((p/n))1/4 + Vlogn) while p w()). In this heavy overparameteized regime, the model will benignly overfit both the noisy and clean data.
Our simulation aligns with the theoretical prediction as
(1) For small signal-to-nowl noise ratio as 5, we observe that when p/n grows to 27, the linear model starts to suffer constant excess risk even for the noiseless data. For the noisy data, need a larger signal-to-noist ratio compared with the overparameterizztion. This corresponds Case 1 in prediction and explain the constant excess risk in Figure ((a) and the
23

---

Published as a conference paper at ICLR 2023
Heavy
Heavy
8 7-
Mild
Mild
4 10 19
8
12
6 10
12
15
log
log
log
(a) Noiseless ||all/o
(b) Noisy lelll/ =
(c) Early Stop |l
1/o
5
X
5-
5-
Heavy
Heavy
c..
Mild
27.
Mild
log
log
log
(d) Noiseless ||a||/a = 10
(e) Noisy ||al// 10
(I) Early Stop |l / 10
Heavy
Heavy
12
Mild
gy.
Mild
8-
15
8-
5-
10 13
10
12 13
30 12 12 15
log
log
log
Noiseless ||/]1/0 20
(h) Noisy //
(i) Early Stop 1mll//
20
6.
10
Heavy
239
Heavy
Mild
8y.
Mild
4 16 15 1
4 10 1a
1 1 16663
6 10 12
1h
14
log
log
log
(i) Noiseless |||]]/a = 80
(k) Noisy |/ = 80
(I) Early Stop
|| 80
N Mild
Heavy
Heavy
c-- 8,
Mild
p
log
log
(m) Noiscless ||ll// 160
(n) Noisy II /o// 160
(o) Early Stop ||
160
Figure 6: Extended GMM Experiments. The figure is derived in the same way Figure
overfitting in the heavy overparameterized regime in Figure 6(b)
Figure 6(c)
Figure 6(e)
and Figure 6()
(2) We observe similar effect as in Figure for || spanning across {10, 20, 40. 80, 160) that in the mild overparameterized regime, non-benign overfitting happens consistently, while for the heavy overparameterized regime, benign overfitting takes place.
33) We also notes that using technique as early stopping prevents overfitting and gives classifier with generalization guarantee for ||] spanning across {10, 20, 40, 80, 160) as predicted.
24

---

Published as a conference paper at ICLR 2023
E DISCUSSION
E. COMPARISON BETWEEN REGRESSION AND CLASSIFICATION
Although Bartlett et al. (220)) shows similar findings in regression regimes, we emphasize that the techniques can be pretty different. The difference between regression and classification problems can be split into two folds:
(a) technical difference. Regression problem usually permits closed-form solution through matrix pseudo-inverse while classification problem does not. Therefore, one needs to use other terms, e.g., margin, to study the generalization bound. Besides, the commonly-used operations in regression settings, e.g., variance-bias decomposition do not apply in classification settings. Therefore, we need some different techniques during the proof. For example, when proving Theorem 3.1.2 we need to choose those samples with wrong labels, which is impossible in regression regimes.
(b) different label noise type. In regression problems, the label noise is usually subGaussian type. However, the label noise is totally different in classification problems and therefore their results cannot be extended to the classification settings, However, the most commonly-used learning task, the analysis of classification is important.
E.2 DETECTING BENIGN OVERFITTING IN PRACTICE
Benign overfitting refers to that large models can fit data well without giving poor generalization performance (Bartlett et al., 2021). indicating the models operate outside the realm of uniform convergence. There could be multiple mathematical instantiations of the statement. For example, Bartlett et al. (2020) bound the generalization error of the last-epoch model with sample size and model size to characterize benign overfitting, and prove that the validation accuracy approaches Bayesian optimal sample size increases. Our theoretical claims (Statements and of Theorem 3.1) follow the same criterion. We show that the validation error of fully trained linear model approaches the label error, and hence is Bayesian optimal.
However, the criterion generalization error converges to zero is hard to verify in experiments, as it is hard to determine when the model size and sample complexity are large enough for the generalization bound to be sufficiently small, given that the data set size is upper bounded. Hence we adopt two mild assumptions to test whether benign overfitting happens empirically.
1. Training the model for long-enough epochs (at least three times that of the standard practice) can work as an honest proxy for training for infinite epochs.
2. The gap of verification accuracy between the best-epoch model and the last-epoch model work as efficient proxy for the gap between the Bayesian optimal accuracy and the validation accuracy of the last-epoch model. This assumption is supported by our theoretical predictions (Statements 2 and 3 of Theorem 3.1).
Hence we adopt the different notion of benign overfitting, as the reviewer mentioned, 'validation performance does not drop while the model fits more training data points'. This notion is
1. coherent the intuitive definition embed all of the noise of the labels into the parameter estimate wwithout harming prediction accuracy,
2. easily experimentally verifiable;
3. closely related to theoretical predictions in our work and previous works, in the sense that based on theoretical prediction, in the mild overparameterizatio regime (our work), the drop will be significant regardless of model size, and the heavy overparameterriztion regime (previous works), the drop will diminish when the model size and sample complexity increases.
Finally, we would like stress that the similarity between the overparameeerizzatin through model size and training model longer is not required for our analysis.
25


Reviews:
[{"review_id": "mZM6TvQsF15", "reviewer": "Reviewer_k2R8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies benign overfitting with respect to the level of over-parameterization and whether under a noisy regime through implicit bias theory. This study is inspired by the phenomenon that the ResNet model overfits benignly on Cifar10 but not benignly on ImageNet. The authors identify a phase change: unlike in the previous heavy overparameterization settings, benign overfitting can now fail in the presence of label noise. The experimental simulation verifies the theoretical results.\n", "summary_of_the_review": "The paper presented a relatively novel idea (to me) on benign overfitting. It presented a set of thorough theoretical analyses and experiments to validate the method. I tend to accept this paper.", "strength_and_weaknesses": "**Strength**\n\n* This work studies benign overfitting in the mild over-parameterziation regime which is novel and interesting compared to previous works.\n\n* The authors further study the noisy case and present the correspoding results. They find that mild-overparameterization is not enough for classification noisy problem. This result seems important to me.\n\n\n**Weaknesses**\n\n* This work directly use the result from implicit bias theory (Proposition 3.1). It is unclear what will happen when we study the gradient descent training like [1].\n\n[1] Cao, Y., Chen, Z., Belkin, M., & Gu, Q. (2022). Benign Overfitting in Two-layer Convolutional Neural Networks. arXiv preprint arXiv:2202.06526.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gSZNAaSfR9", "reviewer": "Reviewer_P3FZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work analyzes the benign overfitting when the logistic regression is mild over-parameterization, in the setting of label noise. The core theory results are: 1) excess risk can be lower bounded at infinite SGD iteration; 2) the risk with early stopping can be upper bounded by 1/n (the number of samples. The authors also empirically verify the classification error under label noise and with different network widths.", "summary_of_the_review": "In general, I think this is a good paper with solid contributions to both theory and experiments.\nI hope the authors could address my concerns above.", "strength_and_weaknesses": "Strength:\n1. Paper is well-written and easy to follow.\n2. The core idea is demonstrated with both theory and experiments.\n\nWeakness:\n1. “fast convergence rate in Statement One and Statement Three”: forgive my ignorance, I only see the bound on the loss but did not see any results related to the convergence rate. For example, any bound on the difference between $L(t+1)$ and $L(t)$? Is it a linear convergence?\n2. For separable data in the noisy setting, are you considering the flipped labels or their clean labels? I suppose one cannot have noisy data separable on both their flipped labels and their clean labels. If you consider the noisy data with flipped labels to be separable, is this conflict with the noiseless setting? I.e., you make separable noiseless data into noisy by flipping some labels, which will give you inseparable noisy data.\n3. On page 16 case 2, “distance between $\\mu$ and $\\bar{\\mathbf{x}}_\\kappa^{\\top}$ must be less than the distance from $\\mu$ to its projection on the separating hyperplane”. Does that imply $|\\mu^\\top \\mathbf{w}| \\geq \\| \\bar{\\mathbf{x}}_\\kappa^{\\top} − \\mu \\|$?\n4. In proof of Thm 5.3, I suppose the bounds over $\\max_{t \\in [T]}$ (Eq. 10, 12, 15) may not be tight at the same $t$?\n5. To complete the argument in this work, I suppose you should also show that with increasing parameterization, the overfitting becomes benign (e.g. the lower bound of risk becomes diminished)? Current benign overfitting papers do not have this conclusion in label noise classification setting.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EhzNIg4JD_4", "reviewer": "Reviewer_NJij", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the benign overfitting phenomenon of deep neural models, namely over-parameterized deep neural models fitting the training data can still achieve low generalization error. The authors focus on a specific regime where the model is mildly overparameterized and label noise is prevalent. They show that in such a regime, benign overfitting may fail. This explains the observation that ResNet model overfits benignly on CIFAR-10 but not on ImageNet, since ImageNet may be noisier. They also show that early stopping can help avoid overfitting in such a regime.", "summary_of_the_review": "The promises and observations made in this paper are interesting but it would be hard to judge the contribution right now given the clarity issue. I would be willing to increase my score if the authors can address my above concerns. ", "strength_and_weaknesses": "Strength:\n* This paper is well-organized and focused on an important problem in understanding the generalization of deep neural models. The claim is overall clear and the target setting is specific. Some observations made in this paper are also interesting such as deep models on ImageNet and CIFAR-10 have different overfitting phenomena.\n\nWeakness:\n* I believe the clarity of the paper needs to be improved. First, the definition of benign overfitting is rather ambiguous in this paper. I may not be an expert in this field, but based on my understanding, benign overfitting in existing works studies the generalization error as model size increases. However, in the introduction of this paper, benign overfitting is termed as 'validation performance does not drop while the model fits more training data points'. It appears to me that the authors try to study the dynamics of generalization error through model training (i.e. epoch-wisely). This is further corroborated by Figure 1 where the performance curves through training are shown. While I understand overparameterization through model size may bear similarities in training a model longer, it would be better if the authors can make it explicit. \n\n* In the experiment section, the above problem becomes more prominent. For example, in Figure 3 the authors show the performance curves with respect to epochs, while in Figure 4 the authors show the performance curves with respect to model size. \n\n* I might miss something in Theorem 3.1. But why does the lower bound to the generalization error in a noisy setting (Statement 2) show benign overfitting fails? I believe a lower bound to the generalization error should also exist in a noiseless setting. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster