Label Noise SGD Provably Prefers Flat Global Minimizers
Authors: Alex Damian
Tengyu Ma
Jason D. Lee
Venue: NeurIPS 2021 Poster (2021)
Keywords: stochastic gradient descent
implicit regularization
non-convex optimization

Abstract: In overparametrized models, the noise in stochastic gradient descent (SGD) implicitly regularizes the optimization trajectory and determines which local minimum SGD converges to. Motivated by empirical studies that demonstrate that training with noisy labels improves generalization, we study the implicit regularization effect of SGD with label noise. We show that SGD with label noise converges to a stationary point of a regularized loss $L(\theta) +\lambda R(\theta)$, where $L(\theta)$ is the training loss, $\lambda$ is an effective regularization parameter depending on the step size, strength of the label noise, and the batch size, and $R(\theta)$ is an explicit regularizer that penalizes sharp minimizers. Our analysis uncovers an additional regularization effect of large learning rates beyond the linear scaling rule that penalizes large eigenvalues of the Hessian more than small ones. We also prove extensions to classification with general loss functions, significantly strengthening the prior work of Blanc et al. to global convergence and large learning rates and of HaoChen et al. to general models.

Label Noise SGD Provably Prefers Flat Global Minimizers
Alex Damian Princeton University ad27@princeton.co edu
Tengyu Ma Stanford University
tengyuma@stannfrrd edu
Jason Lee
Princeton University
jasomlee@princetoo.eed
Abstract
In overparametrized models, the noise in stochastic gradient descent (SGD) implic- itly regularizes the optimization trajectory and determines which local minimum SGD converges to. Motivated by empirical studies that demonstrate that training with noisy labels improves generalization, we study the implicit regularization effect SGD with label noise. We show that SGD with label noise converges to a stationary point of regularized loss L(0) XR(O), where L(0) the training loss, A is an effective regularization parameter depending on the step size, strength of the label noise, and the batch size, and R(0) sharp minimizers. Our analysis uncovers an additional regularization effect of large learning rates beyond the linear scaling rule that penalizes large eigenvalues of the Hessian more than small ones. We also prove extensions to classification with general loss functions, significantly strengthening the prior work of Blanc et al. [3] to global convergence and large learning rates and of HaoChen et al. [12] to general models.
explicit regularizer that penalizes
Introduction
One of the central questions in modern machine learning theory is the generalization capability of overparametrized models trained by stochastic gradient descent (SGD). Recent work identifies the implicit regularization effect due the optimization algorithm one key factor in explaining the generalization of overparameterized models 27 11 19 10]. This implicit regularization is controlled
by many properties of the optimization algorithm including search direction [1I, learning rate 200) batch size [26), momentum
21 and dropout
The parameter-dependent noise distribution in SGD is crucial source of regularization [16 18
Blanc et 3 initiated the study of the regularization effect of label noise SGD with square los by characterizing the local stability of global minimizers of the training loss. By identifying data-dependent regularizer R(O). Blanc et al. B proved that label noise SGD locally diverges from the global minimizer 8* if and only if 8* is not first-order stationary point of ming R(0) subject to L(0) = The analysis is only able to demonstrate that with sufficiently small step size 7, label noise SGD initialized at 6* locally diverges by distance of 7 0.4 and correspondingly decreases the regularizer by n This is among the first results that establish that the noise distribution alters the local stability of stochastic gradient descent. However, the parameter movement of 77 is required to
LLabel noise SGD computes the stochastic gradient by first drawing sample (Ir, v:). perturbing vf yi + with e { {-a, .). and computing the gradient with respect to (I., v().
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

be inversely polynomially small in dimension and condition number and is thus too small to affect the predictions of the model.
HaoChen et al. 12 motivated by the local nature of Blanc et al. 3 analyzed label noise SGD in
the quadratically parameerrid linear regression model 29 32 23
Under well-specified sparse linear regression model and with isotropic features, HaoChen et al. [12 proved that label noise SGD recovers the sparse ground-trui truth despite overparametrization, which demonstrated a global implicit bias towards sparsity in the quadratically-paaamettizz linear regression model.
This work seeks to identify the global implicit regularization effect of label noise SGD. Our primary result, which supports Blanc et al. [3]. proves that label noise SGD converges to a stationary point of L(0) XR(O), where the regularizer R(+) penalizes sharp regions of the loss landscape.
The focus of this paper is on label noise SGD due to its strong regularization effects in both real and synthetic experiments [25]
28 31. Furthermore, label noise is used in large-batch training as an additional regularizer [25] when the regularization from standard regularizers (e.g. mini-batch,
batch-norm, and dropout) is not sufficient. Label noise SGD is also known to be less sensitive to initialization, as shown HaoChen et al. [12]. In stark contrast, mini-batch SGD remains stuck when initialized at any poor global minimizer. Our analysis demonstrates global regularization effect of label noise SGD by proving it converges to a stationary point of a regularized loss L(0) + AR(0), even when initialized at zero error global minimum.
The learning rate and minibatch size in SGD are known to be important sources of regularization 9 Our main theorem highlights the importance of learning rate and batch size as the hyperparameters that control the balance between the loss and the regularizer - larger learning rates and smaller batch sizes lead to stronger regularization.
Section 2 reviews the notation and assumptions used throughout the paper. Section 2.4 formally states the main result and Section sketches the proof. Section 4 presents experimental results which support our theory. Finally, Section discusses the implications of this work.
2 Problem Setup and Main Result
Section 2.1 describes our notation and the SGD with label noise algorithm. Section 2.2 introduces the explicit formula for the regularizer R(O). Sections 2.3 and 2.4 formally state our main result.
2.1 Notation
We focus on the regression setting (see Appendix E for the extension to the classification setting). Let
{(r,, 9:) Je]m be n datapoints with x; E 'D and y/ E R. Let f D x Rdd + R and let fx(0) = f 0) denote the value of on the datapoint 24. Define (0) 1/ (f)(0) y²)² and L(0) 1 Σー (0). Then we will follow Algorithm I which adds fresh additive noise to the labels at every step before computing the gradient:
Algorithm 1: SGD with Label Noise
Input: 0g step size 77, noise variance o², batch size B, steps T
for 1s = 0 to T 1 do
Sample batch (k) C l uniformly and label noise e (k)
(-o,0) for B(4).
Let (*)) (8) {1)(())
2 (f) - ys - -c( x and (h) = B Eiegu) ((k)
0x+1 t 02 (+))))
end
Note that a controls the strength of the label noise and will control the strength of the implicit
regularization in Theorem [ Throughout the paper we will use ||- -|. We make the following
standard assumption on f:
Assumption 1 (Smoothness). is Lipscchtt with respect to
We assume that each Si is Liisschhi, Vi is -ippschhit and /
|| for i ,,..., n.

---

We will define = E to be an upper bound on || E; V [()lll any global minimizer 0. Our results extend to any learning rate v E (0, 2). However, they do not extend to the limit as 1 - z. Because we still want to track the dependence on #.- we do not assume 1 is a fixed constant and instead assume some constant separation:
ll,, which is equal to
Assumption 2 (Learning Rate Separation). There exists constant
(0, such that r S 37"
In addition, we make the following local Kurdyka- -ajjsssewwwiiizzz assumption (KL assumption) which ensures that there are no regions where the loss is very flat. The KI. assumption is very general and holds for some 8 >> O for any analytic function defined on compact domain (see Lemma[1] Assumption 3 (KL). Let 0 be any global minimizer of L. Then there exist CKL > 0, p > 0 and 0 < 8 S 1/2 such that if L(0)- L(O")= S EKT, then L(0) L(0") S Mll V[))] 1+6
We assume L(0*) for any global minimizer 6*, Note that if L satisfies Assumption 3 for some 5 then it also satisfies Assumption for any 8' < 5. Assumption 3 with 8 = 1 is equivalent to the much stronger Dojai---oasieewic condition which is equivalent to local strong convexity.
We will use O, 6, hide any polynomial dependence μr, 2, 1/0, n, d and Ô to hide additional polynomial dependence on log 1/1, log B.
2.2 The Implicit Regularizer R(0)
For o2 B, 17 as defined above, we define the implicit regularizer R(Ø), the effective regularization parameter A, and the regularized loss L(0):
no² A
R(O)= 21)
log 1 -2-
i(0) L(0) AR(O). (1)
B
Here log refers to the matrix logarithm. To better understand the regularizer R(0),, let XI,..., da be
the eigenvalues of 2 (0) and let R(A:) 2n log(1 (1-
T2:). Then,
R(O) Σ R()) Σ
A;
2 1²
+ +...)
4
16
48
In the limit as 17 + O, R(0) + 1 V(L,), which matches the regularizer in Blanc al. 33 for infinitesimal learning rate near a global minimizer. However, in additional to the linear scaling rule, which is implicit in definition of X, our analysis uncovers an additional regularization effect of large learning rates that penalizes larger eigenvalues more than smaller ones (see Figure and Section 1.
Regulatization Strength
XR(0)
The goal of this paper is to show that Algorithm converges to stationary point of the regularized loss i. = T. + AR. In particular, we will show convergence to an (e. (sttatiity point, which is defined in the next section.
1/8
2/f
Learning rate
Figure/ 1: Regularization strength as function of n
2.3 (e, Statioonayy Points
We begin with the standard definition of an approximate stationary point: Definition (c-stationary point). 0 is an c-stationary point of f [V c.
B scale with to reach an e-stationary point 88 [5] (c.g.. À may need to be less than e²). However, for X = O(e), any local minimizer 8" is an e-stationary point of L L + XR. Therefore, reaching c-stationary point of L would be equivalent to finding a local minimizer and would not be evidence for implicit regularization. To address this scaling issue, consider the rescaled regularized loss:
In stochastic gradient descent it is often necessary to allow X no²
L + R.
3

---

Local Coupling
h
Figure 2: Local Coupling: We decompose as the sum of regularized trajectory Φ (0)), a mean zero oscillating process Er,, and an error term A1. Global Convergence: We repeat the coupling with sequence of reference points {6 Im prove convergence stationary point of L..
Reaching an e-stationary point of } requires non-trivially taking the regularizer R into account. However, it is not possible for Algorithm to reach an e-stationary point of A even in the ideal setting when is initialized near global minimizer 6* of L. The label noise will cause fluctuations of order Vă around f" (see section so |L will remain around vX. This causes 1 VL become unbounded for À (and therefore c) sufficiently small, and thus A I converge to an e-stationary point. We therefore prove convergence to an (c, -sstatiorrar point:
Definition ((e, -ttatioaay point). 0 is an (e, -ttationray point of f if there exists some 0- such that ((*)l Σ and ||0 l*ll S
Intuitively, Algorithm I converges to an (e, -tsatiooaay point when it converges to neighborhood of some e-stationary point 0"
2.4 Main Result
Having defined an (c, -stattioyy point we can now state our main result:
Theorem Assume that I satisfies Assumption b satisfies Assumption 2 and satisfies
Assumption
3 i.e. L(0) & |]|V[(0)]]= 1+5 for L(O) S EKL- Let q, B be chosen such that = 10 éminn (2/8,,2)) and let = O ( = polyonn 1- Assume that
B
initialized within O( O(v21+8) of some 6* satisfying L(0*) 0(21+6). Then for any S (0, 1), with probability at least 1 - S, if {0x} follows Algorithm with parameters n) a, T, there exists k < T such that 0g is an (4,7) --stationayy point of LT.
Theorem guarantees that Algorithm 1 will hit an (e, sttttionnary point of } within polynomial number of steps in - In particular, when 8 2. Theorem guaranttes convergence within Ō + 3-- steps. The condition that 0g is close to an approximate global minimizer is not a strong assumption recent methods have shown that overparameterized models can easily achieve zero training loss the kernel regime (see Appendix C). However, in practice these minimizers of the training loss generalize poorly [I] Theorem I shows that Algorithm c then converge to a stationary point of the regularized loss which has better generalization guarantees (see Section 6.2). Theorem I also generalizes the local analysis in Blanc al. (3] global result with weaker assumptions on the learning rate v). For a full comparison with Blanc et al. [3], see section 3.1
3
Proof Sketch
The proof of convergence an (e, -ssttttotrr point of 1 has components. In Section 3.1 we pick reference point 8* and analyze the behavior of Algorithm[ i neighborhood of 0* Im Section 3.2
we repeat this local analysis with sequence of reference points {0:.).
3.1
Local Coupling
Let (.). denote k steps of gradient descent on the regularized loss i,, i.e.
( = 0
and O
(0) +x (())))))

---

where L(0) L(Ø) + AR(O) is the regularized loss defined in Equation Lemma states that if initialized at an approximate global minimizer 0 and follows Algorithm there a small mean zero random process such that 0₁ & 4 (0*) + Ex:
Lemma 1. Lel
Φ = (2 = ==
6 6= clog
XC
2 2n
where c is a sufficiently large constant. Assume f satisfies Assumption I and satisfies Assumption 2 Let A follow Algorithm [starting at 6 and assume that L((") S L for some 0 < 5 < 1/2. Then there
exists a random process {Ex} such that for any T I I satisfying max;<r (1xx(())) 8" - S.M. with probability at least 10dre - we have simultaneously for all S, and
| EN (
E[EN] =
[1Ex S 2.
Note that because Ml > 9, the error term 9 is at least 8 times smaller than the movement in direction of the regularized trajectory Φ, (0"), which will allow us to prove convergence to an (e, -ttationny point 1 in Section 3.2
Toward simplifying the update in Algorithm we define (a) to be the true loss without label noise on batch B(k) The label-noise update (,(k)( (px) is an unbiased perturbation of the mini-batch update:
v (00 (0x) (k -B EiEBoo 6 fe(Ox). We decompose the update rule into three parts:
0k+1 = O2 - V((O)) M (R) (0x) VL(0))
+
7 Σ ((((0))
(3)
B TEB
gradient descent
minibatch noise
label noise
Let my = = vL(Os)] denote the minibatch noise. Throughout the proof we will show that the minibatch noise is dominated by the label noise. We will also decompose the label noise into two terms. The first, G. will represent the label noise if the gradient were evaluated at 6* whose distribution does not vary with k. The other term, 24 represents the change in the noise due to evaluating the gradient at 0g rather than 8". More precisely, we have
E
"
Σ
(K) V(
and
ZK
Σ (k) &
(V)(()))))))))))))))))))))))){)) v.())')
B
B SEB(M)
iEBOO)
We define G(0) E. VI to be the covariance of the model gradients. Note that cj has covariance 77 ( (."). To simplify notation in the Taylor expansions, we will use the following shorthand to refer various quantities evaluated at 0":
G = G(0')
VL VLL
V V L(0"),
VR = VR(0").
First we need the following standard decompositions of the Hessian:
Proposition 1. For any 8 Rdd we can decompose (2 G(0) + E(0) where E(l) E (0) - ys) 22 (0) satisfies |E())] s L(p where oj is defined in Assumption !
The matrix G in Proposition I is known as the Gauss-Newton term of the Hessian. We can now Taylor expand Algorithm and Equation 22) to first order around 6":
k
4 (0*) 7 [VL + v V²L( 0²)],
0 P-1 ~ 0 " [V L - 8*)] +
We define Us = 0 - & ) to be the deviation from the regularized trajectory. Then subtracting these two equations gives
Uk+1 (I - m)²)) + c R (I r)yb + c.
where we used Proposition we define the random process { by
to replace L with G. Temporarily ignoring the higher order terms,
Ex+1 = - Gf + +
and Eo = 0.
The process is referred as Ornstein Uhlenbeck process and it encodes the movement of to first order around 0*, We defer the proofs of the following properties of & to Appendix
5

---

Proposition 2. For any k 2 O. with probability at least 1 2de k co, B (2 r/ where Hg the projection onto the span ofG G.
|Ex S L. In addition, as
We can now analyze the effect of &L. on the second order Taylor expansion. Let -0 (00) En be the deviation of 0 from the regularized trajectory after removing the Ornstein Uhlenbeck process Ç. Lemma equivalent to Pr[[|, 2 Φ) S 10rde
We will prove by induction that ||r || - 9 for all k S t with probability at least 10tde -1 for all t & r. The base case follows from To = O so assume the result for some & > 0. The remainder of this section will be conditioned on the event ||rx|l - 9 for all t. O(-) notation will only be used to hide absolute constants that do not change with and will additionally not hide dependence on the absolute constant c. The following proposition fills in the missing second order terms in the Taylor expansion around 8 of rR:
Proposition 3. With probability at least 1 - 2de
1 Tk-1 = (1 r)G)rx - L Ex) AVR + m. + 2x +0 (
The intuition for the implicit regularizer R(0) is that by Propositions and 2
E[(ASf] + 12 - n/G) Rs X(2 - 1/
Therefore, when averaged long timescales,
F L(Ex, Re A (2
AV
1 2m
Lr log (1-2v"1(0
RVR.
1==0-
The second equality follows from the more general equality that for any matrix function A and any scalar function that acts independently on each eigenvalue, V(rr ((A())) = (V (VA(O)((((A(O)) which follows from the chain rule. The above equality is the special case when A(0) L() and
f(x)= = - log (1 - z), which satisfies h' h'(x)= mpp
The remaining details involve concentrating the mean zero error terms mg, 2n and showing that E[ does concentrate in the directions with large eigenvalues and that the directions with small eigenvalues, in which the covariance does not concentrate, do not contribute much to the error. This yields the following bound:
Proposition 4. With probability at least 1 10de ||re ò (~ (A1R2t0122
The proof of Proposition 4 can be found in Appendix B Finally, because (c² x/222/1/24//2)
||retl|| 9 for sufficiently large This completes the induction and the proof of Lemma]
Comparison with Blanc et al. [3] Like Blanc et al. [3], Lemma shows that & locally follows the trajectory of gradient descent implicit regularizer R(0). However, there are few crucial differences:
Because do not assume start near global minimizer where L we couple regularized loss L. = L + XR rather than just the regularizer R(0). In this setting there is an additional correction term to the Hessian (Proposition I that requires carefully controlling the value of the loss across reference points prove convergence
stationary point.
The analysis in Blanc et al. 3 requires 7), t to be chosen in terms of the condition number of V which can quickly grow during training as 2 is changing. This makes it impossible to directly repeat the argument. We avoid this by precisely analyzing the error incurred by small cigenvalues, allowing us to prove convergence an (E, stationary point of $ for fixed A even if the smallest nonzero eigenvalue of V converges to 0 during training.
Unlike in Blanc et al. B3, we do not require the learning rate 77 to be small. Instead, we only require that À scales with e which can be accomplished either by decreasing the learning rate v or increasing the batch size B. This allows for stronger implicit regularization in the setting when is large (see Section 6. Tp. In particular, our regularizer R(0) changes with r and is only equal to the regularizer in Blanc et al. (3 in the limit 17 + 0.

---

3.2 Global Convergence
In order to prove convergence to an (e, -sstttionay point of J VL, we will define a sequence of reference points 0% and coupling times {Tm] and repeatedly use version of Lemma to describe the long term behavior of O. For notational simplicity, given a sequence of coupling times {Tm) define Tm Ekem Tk be the total number of steps until we have reached the reference point 8
7
To be able to repeat the local analysis in Lemma I with multiple reference points, we need a more general coupling lemma that allows the random process & defined in each coupling to continue where the random process in the previous coupling ended. To accomplish this, we define & outside the scope of the local coupling lemma:
Definition 3. Given sequence of reference points {0rm) and a sequence of coupling times {Tm), we define the random process & by ED- and for l [T'm 1m+1).
E VEBOS
(K) 4
and
Ek+1 (1- c
Then we can prove the following more general coupling lemma:
Lemma 2. Let 2t L, 9, I be defined as in Lemmal 7 Assume satisfies Assumplion and 1 satisfies Assumption 2 Let Am = Or,, - -.r.. -0% and assume that || Am || S 2 and L(O m
S L for some ō S 1/2. Then for any Tm T satisfying maxxe[[m..Tmt) | Tm (0t + Am)) 0x S
S.M, with probability at least 1 10dTme we have simultaneously for all k E (Tm, T 1m.
|10g - D (0 Am)l
B[Ex] 0, and
||Ex|1 S 2.
Unlike in Lemma we couple to the regularized trajectory starting at 0% + Am rather than at 0%, to avoid accumulating errors (see Figure 2). The proof is otherwise identical to that of Lemmal
The proof of Theorem [ easily follows from the following lemma which states that we decrease the regularized loss L by at least. F after every coupling:
92 Lemma 3. Let F nu Let Am &T.,. - Er... - 6", and assume || Am S D and L( S L.
Then Or,, is not (c,7)- point, there exists some Tm < I such that if we define
on 2r, 10 + Am)
and Am+1 -TTmi ETm+1 m
then with probability 1 10dTme
L(8 S L(O%)) F,
|mm+ill S
and L(fm+1) S L.
We defer the proofs of Lemma and Lemma repeated applications of Lemma
3 to Appendix
B Theorem now follows directly from
Proof of Theorem 7 By assumption there exists some of such that T.(0)) < L and 1 0 < 2
Then so long as fr.. is not an -staaiityy point, we can inductively apply Lemma 3 to get the existence of coupling times } and reference points {0r such that for any
0, with
probability 1 10dT we have L(et.) s L((h) m.F. As L(( L(e = 0(A), this
can happen for at most m O ( reference points, at most T = 0 ( 0
iterations of Algorithm I
By the choice of e, this happens with probability 1- 10dTe- - 2 1-c. O
4 Experiments
In order to test the ability of SGD with label noise to escape poor global minimizers and converge to better minimizers, we initialize Algorithm [ at global minimizers of the training loss which achieve 100% training accuracy yet generalize poorly to the test set. Minibatch SGD would remain fixed at these initializations because both the gradient and the noise minibatch SGD vanish at any global minimizer of the training loss. We show that SGD with label noise escapes these poor initializations and converges to flatter minimizers that generalize well, which supports Theorem T We run experiments with two initializations:
7

---

Full Batch Initialization
Veett Acetrnuy
Thore Iessian
16
Test: Accurury
80-
5
1 2
1
900
10
epoch
epoch
0.2 Trace of Hessian
0.5
Adversarial Initialization
Tesr: Aucurary
Troce Fiessinn
201
Tos:: Aocurucy
0.1
7 0.05
62-
0.02
60
250
500
750
1000
250
300
700
1600
161
16
epoch
epoch.
Trace of Bessian
Figure 3: Label Noise SGD escapes poor global minimizers. The left column displays the training accuracy over time, the middle column displays the value of tr V²L(0) over time which we use to approximate the implicit regularizer R(0), and the right column displays their correlation. The horizontal dashed line represents the minibatch SGD) baseline with random initialization. We report the median results over random seeds and shaded error bars denote the min/max over the three runs. The correlation plot uses a running average of 100 epochs for visual clarity.
Full Batch Initialization: We run full batch gradient descent with random initialization until convergence global minimizer. We call this minimizer the full batch initialization. The final test accuracy of the full batch initialization was 76%.
Adversarial Initialization: Following Liu al. 21. generate adversarial initialization with final test accuracy 48% that achieves zero training loss by first teaching the network to memorize random labels and then training it on the true labels. See Appendix for full details.
Experiments were run with ResNet18 on CIFARIO [17] without data augmentation or weight decay. The experiments were conducted with randomized label flipping with probability 0.2 (see Appendix for the extension of Theorem [ to classification with label flipping), cross entropy loss, and batch size 256. Because of the difficulty in computing the regularizer R(0), approximate it by its lower bound tr (0). Figure shows the test accuracy and tr L throughout training.
SGD with label noise escapes both zero training loss initializations and converges to flatter minimizers that generalize much better, reaching the SGD baseline from the fullbatch initialization and getting within 1% of the baseline from the adversarial initialization. The test accuracy in both cases is strongly correlated with tr L2 The strength of the regularization is also strongly correlated with n,. which supports Theorem I
5
Extensions
5.1 SGD with momentum
We replace the update in Algorithm with heavy ball momentum with parameter 9:
0k+1 = 02 - 7, v (0x) (e) + 3(0, - 02-1).
(5)
We define:
R(O) 1
17 2(1 3)
V=(()))
1102
log
X
(6)
21
B(1 - 3)
and as before f.(0) (.) + AR(0). Let
2 0,
U (0) = 4 (0) v vV (3)))))))))))))))))))))))))) -
-) Φx1((0))
represent gradient descent with momentum on L. Then have the following local coupling lemma:

---

Lemma 4. Let
12 =
2' =
= cd cd
9 9= -t,
g 1
(8)
2
where e iss a sufficiently large constant. Assume f satisfies Assumption I and (2-1)(1+.) Let
follow Algorithm with momentum 3 starting at 0 and L(0*) S L for some 0 < 8 8
< 1/2. Then
there exists a random process {Eu] such that for any T S. I satisfying maxesr (00)0)) 0- 82. with probability at least 1 - 10dre we have simultaneously for all k ST.
|00- E tb (0') 2,
[[GA]] = O, and
||Ex| S L.
As in Lemma 1 the error is 8 times smaller than the maximum movement of the regularized trajectory. Note that momentum increases the regularization parameter À by T-3- For the commonly used momentum parameter / = 0.9, this represents a 10x increase in regularization, which is likely the cause of the improved performance in Figure ( = 0.9) over Figure (3 = 0).
5.2 Arbitrary Noise Covariances
The analysis in Section 3.1 is not specific to label noise SGD and can be carried out for arbitrary noise schemes. Let 0 follow 0k+1 02 v/V ((xx) + Eg starting at On where E (O, ()xx) and 12/2 is Lipschitz. Given matrix S we define the regularizer Rs(
(S, V (()). The
matrix S controls the weight of each eigenvalue. As before we can define (s( = L(0) + (Rs
and $ (0) = T (0) 1/ L. (+) (0)) to be the regularized loss and the regularized trajectory respectively. Then we have the following version of Lemma D
Proposition 5. Let 0 be initialized at a minimizer 0 T.. Assume L is Lipschitz, let H (2T
and assume that Σ160) 3 CH for some absolute constant C. Let X =
/Cdx =Voclr 9 = 3/4 and T -, for a sufficiently large constant c. Then there exists a mean zero random process & such that for any T < I satisfying maxker [1*) - 0- s 82 and with probability 1 10dre we have simaltaneously for all k S::
110, - En-
T (0o)]) < 9
and
||El|| S 2;
where S is the unique fixed point of S + - (1- - - + =)=((0)) restricted to span(!),
As in Lemma [ the error is 8 times smaller than the maximum movement of the regularized trajectory. Although Proposition 5 couples to gradient descent Rts, S is defined in terms of the Hessian and the noise covariance at 0" and therefore depends on the choice of reference point. Because Rs is changing, we cannot repeat Propositionsaas in Section 3.2 to prove convergence to a stationary point because there is no fixed potential. Although is sometimes possible to relate Rs to a fixed potential R. we show in Appendix F2 that this is not generally possible by providing an example where minibatch SGI) perpetually cycles. Exploring the properties of these continuously changing potentials and their connections generalization an interesting avenue for future work.
Discussion
6.1 Sharpness and the Effect of Large Learning Rates
Various factors can control the strength of the implicit regularization in Theorem 1 Most important is
the implicit regularization parameter À ng² TBT This supports the hypothesis that large learning rates
and small batch sizes are necessary for implicit regularization [9] 26]. and agrees with the standard linear scaling rule which proposes that for constant regularization strength, the learning rate 17 needs
to be inversely proportional to the batch size [B).
However, our analysis also uncovers additional regularization effect of large learning rates. Unlike the regularizer in Blane et al. ( the implicit regularizer R(()) defined in Equation {1) is dependent on n7. It is not possible to directly analyze the behavior of R(() 17 + 21 where A is the largest

---

eigenvalue of L2L, as in this regime, R(0) - oo (see Figure Dp. If we let 1) better understand the behavior of R(O) by normalizing by log 2/v. This give A
then we can 2-"
R(A:) - [() +0 log 2/v log 2/v
R(O)
log 2/v/
so after normalization, R(0)) becomes a better and better approximation of the spectral norm [()]] + 2/ R(0) can therefore be seen as interpolating between tr ((), when ? R O, and [[)]2 when r) ~ 2/A,. This also suggests that SGD with large learning rates may be more resilient to the edge of stability phenomenon observed in Cohen et al. 4 as the implicit regularization works harder to control eigenvalues approaching 2/n.
The sharpness-aware algorithm (SAM) of (7) is also closely related to R(0). SAM proposes to minimize maxijolass I(O + 8). global minimizer the training loss,
? max L( + + max ('V'L +(() 2 |V2 ó
| 2
The SAM algorithm is therefore explicitly regularizing the spectral norm of L²)( which is closely connected to the large learning rate regularization effect of R(0) when R 2/A1.
6.2 Generalization Bounds
The implicit regularizer R(0) is intimately connected to data-dependent generalization bounds, which measure the Lipschitzness of the network via the network Jacobian. Specifically, Wei and Ma (3
propose the all-layer margin, which bounds the generalization error -يك where C, depends only on the norm of the parameters and is the all- all-layer margin. The norm of the parameters is generally controlled by weight decay regularization, so we focus our discussion on the all-layer margin. Ignoring higher-order secondary terms, Wei and Ma [30 Heuristic derivation of Lemma 3.1] showed for a feed-fon forwardd network f(0; x) = 00 (()xx)) the all-layer margin satisfie
Ci
/ mp(...g))
vn
1
0f II output margin of (æ,y)
38, hetzil2
Σle Ci vn V
R(0) output margin
generalization error
mp(x,y)
R(0) is upper bound the squared norm of the Jacobian at any global minimizer 6. We emphasize this bound is informal as we discarded the higher-order terms in controlling the all-layer margin, but it accurately reflects that the regularizer R(0) lower bounds the all-layer margin me up to higher-order terms. Therefore SGD with label noise implicitly regularizes the all-layer margin.
Acknowledgments and Disclosure of Funding
AD acknowledges support from NSF Graduate Research Fellowship. TM acknowledges support of Google Faculty Award and NSF IIS 2045685. JDL acknowledges support of the ARO under MURI Award W911NF-11-1-0303 the Sloan Research Fellowship. NSF CCF 2002272, and an ONR Young Investigator Award.
The experiments in this paper were performed computational resources managed and supported by Princeton Research Computing, a consortium of groups including the Princeton Institute for Computational Science and Engineering (PICSciF) and the Office of Information Technology's High Performance Computing Center and Visualization Laboratory at Princeton University.
We would also like thank Honglin Yuan and Jeff Z. HaoChen for useful discussions throughout various stages of the project.
Heee we assume A > A2. If instead A₁ = =... = A > A this limit will be k|] v 'The output margin defined min; f((0)y. The following approximation provided Wei and Ma 30 and the chain rule of
Equation (3.3) and the first-order
2f 8h
af h A
36,
She 36 8h
10

---

References
[1] S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with infinitely wide neural net. arXiv preprint arXiv:/904. 1955, 2019.
[2] I.. Biewald. Experiment tracking with weights and biases, 2020. URL http:: Sthpps://wwwr wandb com/ Software Coftwareevaailee available from wandb.com.
[3] G. Blane, N. Gupta, G. Valiant, and P. Valiant. Implicit regularization for deep neural networks driven by an censtenn-uhlentee like process. arXiv preprint
2019.
[4] J. M. Cohen, S. Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar. Gradient descent neural networks typically occurs at the edge of stability, 2021.
[5] S. S. Du, J. D. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks, 2019.
[6] W. Falcon et al. Pytorch lightning. GitHub. Note: http://giiiuuu.ooo//////oooiainn lighting, 3, 2019.
[7] Foret, A. Kleiner, Mobahi, and B. Neyshabur, Sharpness- aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020.
[8] R. Ge, Huang, C. Jin, and Y. Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 797-842, 2015.
[9] P. Goyal, P. Dollár, R. Girshick. P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia. and K. He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv:1706.0260 2017.
[10] S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pages 6151, 2017.
[11] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprint 1rXiv:1802.08:3 2018.
[12] J. Z. HaoChen, C. Wei, J. D. Lee, and T. Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv:2006. 200000000000,000, 2020.
[13] D. Hendrycks and K. Gimpel. Gaussian error linear units (gelus), 2020.
[14] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571 1571- 2018.
[15] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. Stochastic gradient descent escapes saddle points efficiently. arXiv preprint urXiv:1902.048) 2019.
[16] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch train- ing for deep learning: Generalization gap and sharp minima. arXiv preprint 1609 2016.
[17] A. Krizhevsky, Learning multiple layers of features from tiny images. Technical report, 2009.
[18] Y. A. LeCun, L. Bottou, G. B. Oir, and K.-R. Müller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9 48. Springer, 2012.
[19] Y. Li, T. Ma, and H. Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. arXiv preprint
2017.
[20] Y. Li, C. Wei, and T. Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in Neural Information Processing Systems, pages I 11669-11688 2019.
11

---

[21] S. Liu, D. Papailiopoulos, and D. Achlioptas. Bad global minima exist and sgd can reach them. arXiv preprint arXiv: 1906.02666,.. 2019.
[22] P. Mianjy, R. Arora, and R. Vidal. On the implicit bias of dropout. arXiv preprint arXiv:1806.097 097777 2018.
[23] E. Moroshko, S. Gunasekar, B. Woodworth, J. D. Lee, N. Srebro, and D. Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy, Neural Information Processing Systems (NeurIPS), 2020.
[24] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. Vito,, M. Raison, A. Tejani, Chilamkurthy, B. Steiner, L. Fang, Bai, and S. Chintala. Pytorch: An imperative style. high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems 32, pages
Curran Associates, Inc., 2019. URL http:: hppp::://pppprrr.....pppssss nwwrips....... wwwpenisss.cppppppeeeeeeeepp cc/paper/ 9015-pytorch- an- pdf
library
[25] C. J. Shallue, J. Lee, J. Antognini, Sohl-Dickstein, Frostig, and G. E. Dahl. Measuring the effects of data parallelism on neural network training. arXiv preprint 1.X1v:///11033000 2018.
[26] S. L. Smith, P.-J. Kindermans, C. Ying, and Q V. Le. Don't decay the learning rate, increase the batch size. arXiv preprint arXiv:1711.004440 2017.
[27] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-2878, 2018.
(28) C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the inception archi- tecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818-2826, 2016.
[29] T. Vaskevicius, V. Kanade, and P. Rebeschini, Implicit regularization for optimal sparse recovery. In Advances in Neural Information Processing Systems, pages 2968-2979, 2019.
[30] C. Wei and T. Ma. Improved sample complexities for deep networks and robust classification via all-layer margin. arXiv preprint 19Ivv:910.04200 2019.
[31] Y. Wen, K. Luk, M. Gazeau, G. Zhang, H. Chan, and J. Ba. Interplay between optimiza- tion and generalization of stochastic gradient descent with covariance noise. arXiv preprint arXiv:1902.08234, 2019.
[32] B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro. Kernel and rich regimes in overparametrized models. arXiv preprint arXiv:2002.09277 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 2 for list of
assumptions made in this paper and see Appendix A for a full discussion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is mainly theoretical and focuses on understanding an existing algorithm (Label Noise SGD).
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2 for list of assumptions made in this puper.
(b) Did you include complete proofs all theoretical results? [Yes] A proof sketch of Theorem I is provided in Section however full proofs of all claims in the paper be found in Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URLY? [Yes] The instructions needed reproduce the experiments in Section 4 can be found in Appendix D Code
will be submitted through the supplementary material and will be made available (through Github) upon acceptance.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and Appendix
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Figure and Figure
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix [D]
4. If you are using existing assets (e.g., code, data, models) or curating/releesing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] For CIFARIO we cite Krizhevsky [17], as requested by the creators on https://www.cs www.cstooroto..duu kriz/cifar. html. In Appendix D we additionally cite Py-
Torch (24]. Py ToTchh Lightning [6], and Wandb [2].
(b) Did you mention the license of the assets? CIFARIO in Appendix D
[Yes] We mention the MIT license for
(C) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "gZUyqQX32uI", "reviewer": "Reviewer_n6Kd", "summary": "## Post-rebuttal    \nI thank the authors for their clarifications. We had a long discussion about the technical details, and some aspects became more clear to me, but it did not lead to a resolution of the concern that the theory is somewhat weak. I remain concerned about the restrictive nature of the assumptions regarding the quality of the local minimizer. The authors argue that existing theory guarantees us convergence to such minimizes, but there seems to be a mismatch between the requirements of this work and the proved statements in the cited papers.    \n######\n\nThis paper studies the question of minimizing a smooth loss function with noise injection inside labels. The authors show that SGD with label noise converges to a stationary point of a certain regularized loss function, where the regularization depends on the amount of noise, batch size, and the stepsize. The paper improves the results of prior work, namely it does not need small stepsizes of the work by Blanc et al., and the model is much more general compared to the paper of HaoChen et al. I find the topic of the work to be quite interesting and worthy of investigation, although it is hard for me to call this paper very insightful.\n\nThe results have a lot of novelty but they are also somewhat incremental and many limitations are still present in this paper. I particularly criticize the following aspects of the results: restrictive assumptions, requirement for local initialization (close to a global solution), and decreasing effect of regularization when the target stationarity is small.", "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": "My main concern about this work is that it does move towards a good answer but the results are still under restrictive assumptions. First of all, in contrast to standard guarantees on convergence of SGD, the theory additionally requires Lipschitzness of stochastic functions and Hessians in addition to the standard assumption on Lipschitz gradients, which are all not applicable to non-smooth deep networks. I understand that at least some assumptions are required and I could see this as a necessary requirement to keep the theory somewhat simple, but the function also needs to be KL for global minima and Theorem 1 assumes that initialization is close to a global minimum. This essentially eliminates the possibility of encountering a local minimum by assumptions rather than by analysis, and I find this unrealistic to apply the obtained results to practical scenarios such as training neural networks. I understand the authors' argument that it is fine to assume local initialization since overparameterization helps to achieve almost zero loss, but the resulting local theory is not that interesting when combined with local-KL assumption. \n\nIt is also disappointing to see that one needs to have smaller lambda for smaller epsilon, which, as far as I can see, also requires decreasing the stepsize. Ideally I'd hope to see a result that allows to leverage overparameterization and achieve guarantees for non-decreasing regularization. Otherwise, it is not even clear why we should want to eliminate the assumption on small stepsizes of Blanc et al.\n\nI still give the paper a weak accept because I think that the results may lead us towards understanding generalization and the factors that contribute to it. However, I cannot recommend a higher score as so many limitations are currently present.\n\n### Minor\nI have difficulty with understanding the right column in Figure 3. The figure caption reads \"the right column displays their correlation\" while the y-label is \"Test accuracy\". Could the authors clarify what exactly is shown there?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SDP-72yWZtz", "reviewer": "Reviewer_oFfo", "summary": "-The paper studies the behavior of SGD with label noise for over-parametrized models. The label noise setting is linked to an implicit regularization scheme, which is helpful to improve the search for \"better\" optimal as well as to understand the optimization landscape. The study focuses on the analysis for the \"flat\" regions. Theoretical analysis has been provided and empirical studies on ResNet18 and CIFAR10 are shown.", "questions": "", "limitations": "", "rating": 5, "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": "-The paper studies an interesting idea on optimization landscape with perturbation from noise. Specifically, the work presents the behavior of optimization for regions where the gradient is small, which is termed as \"flat\" region. The notion of flatness is described via \\epsilon. The neighborhood of the \"flat\" region, within norm \\gamma in parameter space, has been considered. The idea is to link SGD optimizing procedure for data with the presence of label noise to implicitly regularized learning objectives and studies the conditions where the algorithm reaches the \"flat\" region or its neighborhood. It is a concrete study that provides fruitful theoretical insights on the particular analysis. I believe this can be useful for the community to better understand the SGD procedure in various stances. However, there are some questions to be further addressed as well as related concerns (please see below).\n\n-In the classification setting, label noise the class-conditional noise is coherent with the setting. However, in the regression setting in the main paper, label noise may not be the best term. As this setting is related to the denoise score matching (SM) scheme, how does the analysis related to denoise SM? Algorithm 1 is presenting noise in the uniform labels, which is confusing.\nMoreover, in the regression setting, what is the distribution of noise? and how does the distribution or property of the noise (e.g. variance) affect the analysis or the results, (for instance, in terms of strength of implicit regularization)? Maybe linking to the behavior of denoise SM will be helpful for the community to further understand SGD with the type of regularization presented, as well as linking the important ideas for learning procedures.\nIn Theorem 1, the analysis shows that the optimization reaches the (\\epsilon,\\gamma)-stationary region. Is such a region always better than a sharp local optimal?\n\n-I am not an expert in the area of this type of analysis. Overall, the idea and analysis are interesting. The proof is not carefully checked. The major significance and impact of the analysis are not clear enough. For people who may not be familiar with the particular analysis methodology, it is not easy to understand and appreciate the setting. It is also unclear that what goes next when SGD reaches (\\epsilon,\\gamma)-stationary region. Adding more explanations would help understand the full SGD procedure better.\n\n-Some minor clarifications\n\nIn section 2.2, it will be useful to provide more explicit links between the trace log regularization scheme to the noisy label setting to support the implicit regularizer claim. \nIn definition2, more intuition can be provided for better understanding. It is an interesting metric to consider for the convergence analysis, but it will be easier to have both technical claims and interpretable explanations.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-The main social and practical issue of deep learning schemes is associated with the misuse of optimization procedures. As discussed in Section 5, understanding the sharpness of the local optimal as well as the effect of learning rate is of interest in mitigating these issues, or at least provide some form of guidance to avoid less useful local optimal. Moreover, it will also be better to discuss more on the effect of how SGD behaves after reaching the locally flat region.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5hours"}, "extra_text": {}}, {"review_id": "O0ZrePYkwRr", "reviewer": "Reviewer_Yasg", "summary": "This paper studies the global convergence of SGD/GD with label noise. Under suitable assumptions, it shows that if initialized properly and with suitable stepsize/batch size, label noise SGD/GD converges approximately to some stationary point of a regularized loss function. The results reveal a novel implicit regularization effect of label noise that approximately equals to adding an explicit regularizer. Notably, this regularization effect is more favorable than the implicit bias of vanilla SGD, as vanilla SGD cannot escape from poor global minima, while adding label noise regularizes certain Hessian norm and thus helps the iterates to escape and converge to flat/good minima (that achieve both small main loss and small regularization loss). Empirical results are provided to demonstrate this advantage of label noise regularization.", "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": "# Pros:\n+ The theoretic results provide intuition to understand the implicit regularization effect of adding label noise, which is shown empirically to be better than SGD implicit bias in some cases (like initialization from poor minima).\n+ The introduced $(\\epsilon, \\gamma)$-stationary points that characterize a neighbor of a stationary point seem to be interesting for understanding the properties of a regularized objective.\n+ Empirical observations about label noise are partly justified by the presented theory.\n\n# Cons:\n- l.50. Based on my knowledge, the initial learning rate is generally large for large batch SGD (e.g. linear scaling rule). Could you provide references here?\n- Definition 2. The order of $\\epsilon$ vs. $\\gamma$ seems to be important, could you elaborate on this? What prevents us from setting $\\gamma \\approx \\epsilon$ as happening in linear regression? I am trying to interpret Thm1 for linear regression but find several places are not fully clear. Discussions on how the theorem applies to linear regression could be helpful (e.g., how to setup the parameters in the thm when the considered model is linear regression).\n- I am not sure how Thm1 helps in terms of justifying the title. The title claims label noise SGD prefers flat global \"minimizers\", but thm1 only shows convergence to approximate stationary point. Please elaborate.\n- I am not sure how Thm1 helps in terms of justifying the experiments. Indeed $\\theta^*$ could be a poor global minimizer of $L$ so that SGD cannot escape. But it remains unclear to me why $\\theta_k$ in thm 1 is a good minimizer.\n- I am not sure how Thm1 helps in terms of justifying the claims on the effect of initial large learning rate. Note that Thm1 requires $\\eta/B \\lesssim \\gamma^2$, then why $\\eta$ is considered to be \"large\" (e.g., l.276)? Are you allowing some annealing learning rate here?\n- My next question is also about Thm1: it seems to me the whole considered iterates are in a neighbor of $\\theta^*$ (please correct me if not). Then why thm1 could justify the \"escaping\" behavior of label noise SGD in the experiments?\n- l.267. In the experiment a lower bound is adopted in order to compute the proposed regularizer. As we are considering a minimization problem, why does it make sense to minimize a lower bound (instead of an upper bound) of the objective?\n\n\n\n\n\n# Small issues:\n* l.125. $\\theta^*$ -> $\\theta$\n* l.138. $\\phi$ -> $\\gamma$\n\n\n# Overall\nMy current feeling for this paper is a weak reject, as the claims/title/experiments are not properly justified by the theorem. Authors' feedback is welcome to help me better understand this paper. \n\n\n\n\n----\n\nPost-rebuttal: after further discussions with the authors, my initial concerns are all solved. Therefore I would like to raise the score and recommend to accept the paper. \n\nA suggestion for future revision is to provide examples to illustrate the order of the important quantities in the theorem, e.g., $\\epsilon$ and $\\gamma$ and others.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "8Rk2lifnoz", "reviewer": "Reviewer_C2mG", "summary": "This work investigates the implicit regularization effect of stochastic gradient descent (SGD) with noisy labels.  The authors show that SGD with label noise converges to a stationary point of a regularized loss function. The regularization weight can be controlled with the step size, the batch size, and the noise level of the labels.  The authors assume that the loss function to be minimized satisfies standard regularity conditions, e.g., lipschitness and smoothness,  the step size is not too large (relative to the lipschitzness constant), and that the loss is not too flat around any global minimizer.\n\nAssuming that the SGD is initialized close to an approximate global minimizer of the loss $L$ satisfying the above properties, the authors show that SGD with noisy labels will converge to an approximate stationary point of the regularized loss $\\widetilde{L}$ (they give the expression of the regularized loss as a function of the step size, batch size, and noise level).  Since the authors do not assume the step size to tend to $0$ as in [1] they find that the reguralization term interpolates between penalizing all eigenvalues of $\\nabla^2 L$ equally that happens for small learning rates and penalizing larger eigenvalues more (happens for large learning rates).", "questions": "", "limitations": "", "rating": 7, "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": "I think the result presented in this work is interesting and a good step towards better understanding of the implicit regularization effect of SGD.  Moreover, I found interesting the interplay between step size and regularization showed in this work (in [1] the step size had to be very small).  The paper is well-written, easy to follow in general, and the results are technically non-trivial and interesting.  I believe that this work meets the standards of NeurIPS and I recommend acceptance.\n\nIn Theorem 1 it is assumed that SGD is initialized close to some approximate minimizer of $L$.  Since, at a high level, it seems that initializing the SGD at the global minimizer of $L$ makes it harder for it to escape, is this assumption really necessary?\n\nSince we have that if the KL condition holds for some $\\delta$ it also holds for any $\\delta'< \\delta$, is $\\delta$ supposed to be in $(0, 1/2]$ in Assumption 3? Why not simply have $\\delta \\in (0, 1]$?\n\n[1]:G. Blanc, N. Gupta, G. Valiant, and P. Valiant.  Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the convergence of SGD in the presence of label noise. The authors show that SGD with label noise converges to a stationary point of a certain regularized loss function, where the regularization depends on the amount of noise, batch size, and the stepsize. The assumptions on size of regularization and starting points are somewhat restrictive, but the paper increases the understanding of generalization for this set of problems.
Decision: Accept (Poster)