Label Noise SGD Provably Prefers Flat Global Minimizers
Year: 2022

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(θ)+λR(θ), where L(θ) is the training loss, λ is an effective regularization parameter depending on the step size, strength of the label noise, and the batch size, and R(θ) 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. [3] to global convergence and large learning rates and of HaoChen et al. [12] to general models.

heading: 1 Introduction
text: 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 to the optimization algorithm as 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 [11], learning rate [20], batch size [26], momentum [21] and dropout [22].
The parameter-dependent noise distribution in SGD is a crucial source of regularization [16, 18]. Blanc et al. [3] initiated the study of the regularization effect of label noise SGD with square loss1 by characterizing the local stability of global minimizers of the training loss. By identifying a data-dependent regularizer R(θ), Blanc et al. [3] proved that label noise SGD locally diverges from the global minimizer θ∗ if and only if θ∗ is not a first-order stationary point of minθ R(θ) subject to L(θ) = 0. The analysis is only able to demonstrate that with sufficiently small step size η, label noise SGD initialized at θ∗ locally diverges by a distance of η0.4 and correspondingly decreases the regularizer by η0.4. 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 η0.4 is required to
1Label noise SGD computes the stochastic gradient by first drawing a sample (xi, yi), perturbing y′i = yi+ with ∼ {−σ, σ}, and computing the gradient with respect to (xi, y′i).
35th Conference on Neural Information Processing Systems (NeurIPS 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-parametrized linear regression model [29, 32, 23]. Under a well-specified sparse linear regression model and with isotropic features, HaoChen et al. [12] proved that label noise SGD recovers the sparse ground-truth despite overparametrization, which demonstrated a global implicit bias towards sparsity in the quadratically-parametrized 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(θ) + λR(θ), 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 in HaoChen et al. [12]. In stark contrast, mini-batch SGD remains stuck when initialized at any poor global minimizer. Our analysis demonstrates a global regularization effect of label noise SGD by proving it converges to a stationary point of a regularized loss L(θ) + λR(θ), even when initialized at a 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 3 sketches the proof. Section 4 presents experimental results which support our theory. Finally, Section 6 discusses the implications of this work.

heading: 2 Problem Setup and Main Result
text: Section 2.1 describes our notation and the SGD with label noise algorithm. Section 2.2 introduces the explicit formula for the regularizer R(θ). Sections 2.3 and 2.4 formally state our main result.

heading: 2.1 Notation
text: We focus on the regression setting (see Appendix E for the extension to the classification setting). Let {(xi, yi)}i∈[n] be n datapoints with xi ∈ D and yi ∈ R. Let f : D×Rd → R and let fi(θ) = f(xi, θ) denote the value of f on the datapoint xi. Define `i(θ) = 12 (fi(θ)− yi) 2 and L(θ) = 1n ∑n i=1 `i(θ). Then we will follow Algorithm 1 which adds fresh additive noise to the labels yi at every step before computing the gradient:
Algorithm 1: SGD with Label Noise Input: θ0, step size η, noise variance σ2, batch size B, steps T for k = 0 to T − 1 do
Sample batch B(k) ⊂ [n]B uniformly and label noise (k)i ∼ {−σ, σ} for i ∈ B(k). Let ˆ̀(k)i (θ) = 1 2 ( fi(θ)− yi − (k)i )2 and L̂(k) = 1B ∑ i∈B(k) ˆ̀(k) i .
θk+1 ← θk − η∇L̂(k)(θk) end
Note that σ controls the strength of the label noise and will control the strength of the implicit regularization in Theorem 1. Throughout the paper we will use ‖ · ‖ = ‖ · ‖2. We make the following standard assumption on f :
Assumption 1 (Smoothness). We assume that each fi is `f -Lipschitz,∇fi is ρf -Lipschitz, and∇2fi is κf -Lipschitz with respect to ‖ · ‖2 for i = 1, . . . , n.
We will define ` = `2f to be an upper bound on ‖ 1n ∑ i∇fi(θ)∇fi(θ)T ‖2, which is equal to ‖∇2L(θ)‖2 at any global minimizer θ. Our results extend to any learning rate η ∈ (0, 2` ). However, they do not extend to the limit as η → 2` . Because we still want to track the dependence on 1η , we do not assume η is a fixed constant and instead assume some constant separation: Assumption 2 (Learning Rate Separation). There exists a constant ν ∈ (0, 1) such that η ≤ 2−ν` . In addition, we make the following local Kurdyka-Łojasiewicz assumption (KL assumption) which ensures that there are no regions where the loss is very flat. The KL assumption is very general and holds for some δ > 0 for any analytic function defined on a compact domain (see Lemma 17). Assumption 3 (KL). Let θ∗ be any global minimizer of L. Then there exist KL > 0, µ > 0 and 0 < δ ≤ 1/2 such that if L(θ)− L(θ∗) ≤ KL, then L(θ)− L(θ∗) ≤ µ‖∇L(θ)‖1+δ . We assume L(θ∗) = 0 for any global minimizer θ∗. Note that if L satisfies Assumption 3 for some δ then it also satisfies Assumption 3 for any δ′ < δ. Assumption 3 with δ = 1 is equivalent to the much stronger Polyak-Łojasiewicz condition which is equivalent to local strong convexity.
We will use O,Θ,Ω to hide any polynomial dependence on µ, `f , ρf , κf , ν, 1/σ, n, d and Õ to hide additional polynomial dependence on log 1/η, logB.

heading: 2.2 The Implicit Regularizer R(θ)
text: For L, σ2, B, η as defined above, we define the implicit regularizer R(θ), the effective regularization parameter λ, and the regularized loss L̃(θ):
R(θ) = − 1 2η
tr log (
1− η 2 ∇2L(θ)
) , λ = ησ2
B , L̃(θ) = L(θ) + λR(θ). (1)
Here log refers to the matrix logarithm. To better understand the regularizer R(θ), let λ1, . . . , λd be the eigenvalues of ∇2L(θ) and let R(λi) = − 12η log(1− ηλi 2 ). Then,
R(θ) = d∑ i=1 R(λi) = d∑ i=1 ( λi 4 + ηλ2i 16 + η2λ3i 48 + . . . ) .
In the limit as η → 0, R(θ) → 14 tr∇2L(θ), which matches the regularizer in Blanc et al. [3] for infinitesimal learning rate near a global minimizer. However, in additional to the linear scaling rule, which is implicit in our definition of λ, our analysis uncovers an additional regularization effect of large learning rates that penalizes larger eigenvalues more than smaller ones (see Figure 1 and Section 6.1).
The goal of this paper is to show that Algorithm 1 converges to a stationary point of the regularized loss L̃ = L + λR. In particular, we will show convergence to an ( , γ)-stationary point, which is defined in the next section.

heading: 2.3 ( , γ)-Stationary Points
text: We begin with the standard definition of an approximate stationary point: Definition 1 ( -stationary point). θ is an -stationary point of f if ‖∇f(θ)‖ ≤ .
In stochastic gradient descent it is often necessary to allow λ = ησ 2
B to scale with to reach an -stationary point [8, 15] (e.g., λ may need to be less than 2). However, for λ = O( ), any local minimizer θ∗ is an -stationary point of L̃ = L+ λR. Therefore, reaching a -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, we consider the rescaled regularized loss:
1 λ L̃ = 1 λ L+R.
Reaching an -stationary point of 1λ L̃ requires non-trivially taking the regularizer R into account. However, it is not possible for Algorithm 1 to reach an -stationary point of 1λ L̃ even in the ideal setting when θ is initialized near a global minimizer θ∗ of L̃. The label noise will cause fluctuations of order √ λ around θ∗ (see section 3) so ‖∇L‖ will remain around √ λ. This causes 1λ∇L to become unbounded for λ (and therefore ) sufficiently small, and thus Algorithm 1 cannot converge to an -stationary point. We therefore prove convergence to an ( , γ)-stationary point: Definition 2 (( , γ)-stationary point). θ is an ( , γ)-stationary point of f if there exists some θ∗ such that ‖∇f(θ∗)‖ ≤ and ‖θ − θ∗‖ ≤ γ.
Intuitively, Algorithm 1 converges to an ( , γ)-stationary point when it converges to a neighborhood of some -stationary point θ∗.

heading: 2.4 Main Result
text: Having defined an ( , γ)-stationary point we can now state our main result: Theorem 1. Assume that f satisfies Assumption 1, η satisfies Assumption 2, and L satisfies Assumption 3, i.e. L(θ) ≤ µ‖∇L(θ)‖1+δ for L(θ) ≤ KL. Let η,B be chosen such that λ := ησ 2
B = Θ̃(min( 2/δ, γ2)), and let T = Θ̃(η−1λ−1−δ) = poly(η−1, γ−1). Assume that θ
is initialized within O( √ λ1+δ) of some θ∗ satisfying L(θ∗) = O(λ1+δ). Then for any ζ ∈ (0, 1), with probability at least 1 − ζ, if {θk} follows Algorithm 1 with parameters η, σ, T , there exists k < T such that θk is an ( , γ)-stationary point of 1λ L̃.
Theorem 1 guarantees that Algorithm 1 will hit an ( , γ)-stationary point of 1λ L̃ within a polynomial number of steps in −1, γ−1. In particular, when δ = 12 , Theorem 1 guarantees convergence within Õ( −6 + γ−3) steps. The condition that θ0 is close to an approximate global minimizer θ∗ is not a strong assumption as recent methods have shown that overparameterized models can easily achieve zero training loss in the kernel regime (see Appendix C). However, in practice these minimizers of the training loss generalize poorly [1]. Theorem 1 shows that Algorithm 1 can then converge to a stationary point of the regularized loss which has better generalization guarantees (see Section 6.2). Theorem 1 also generalizes the local analysis in Blanc et al. [3] to a global result with weaker assumptions on the learning rate η. For a full comparison with Blanc et al. [3], see section 3.1.

heading: 3 Proof Sketch
text: The proof of convergence to an ( , ϕ)-stationary point of 1λ L̃ has two components. In Section 3.1, we pick a reference point θ∗ and analyze the behavior of Algorithm 1 in a neighborhood of θ∗. In Section 3.2, we repeat this local analysis with a sequence of reference points {θ∗m}.

heading: 3.1 Local Coupling
text: Let Φk(·) denote k steps of gradient descent on the regularized loss L̃, i.e. Φ0(θ) = θ and Φk+1(θ) = Φk(θ)− η∇L̃(Φk(θ)), (2)
where L̃(θ) = L(θ) + λR(θ) is the regularized loss defined in Equation (1). Lemma 1 states that if θ is initialized at an approximate global minimizer θ∗ and follows Algorithm 1, there is a small mean zero random process ξ such that θk ≈ Φk(θ∗) + ξk: Lemma 1. Let
ι = c log d
λζ , X =
√ 2λndι
ν , L = cλ1+δ, D = c
√ L ι, M = D
ν , T =
1
c2ηX ι ,
where c is a sufficiently large constant. Assume f satisfies Assumption 1 and η satisfies Assumption 2. Let θ follow Algorithm 1 starting at θ∗ and assume thatL(θ∗) ≤ L for some 0 < δ ≤ 1/2. Then there exists a random process {ξk} such that for any τ ≤ T satisfying maxk≤τ ‖Φk(θ∗)− θ∗‖ ≤ 8M , with probability at least 1− 10dτe−ι we have simultaneously for all k ≤ τ ,
‖θk − ξk − Φk(θ∗)‖ ≤ D , E[ξk] = 0, and ‖ξk‖ ≤X .
Note that because M ≥ D , the error term D is at least 8 times smaller than the movement in the direction of the regularized trajectory Φτ (θ∗), which will allow us to prove convergence to an ( , γ)-stationary point of 1λ L̃ in Section 3.2.
Toward simplifying the update in Algorithm 1, we define L(k) to be the true loss without label noise on batch B(k). The label-noise update L̂(k)(θk) is an unbiased perturbation of the mini-batch update: ∇L̂(k)(θk) = ∇L(k)(θk)− 1B ∑ i∈B(k) (k) i ∇fi(θk). We decompose the update rule into three parts:
θk+1 = θk − η∇L(θk)︸ ︷︷ ︸ gradient descent − η[∇L(k)(θk)−∇L(θk)]︸ ︷︷ ︸ minibatch noise + η B ∑ i∈B(k) (k) i ∇fi(θk)︸ ︷︷ ︸
label noise
. (3)
Let mk = −η[∇L(k)(θk) − ∇L(θk)] 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, ∗k, will represent the label noise if the gradient were evaluated at θ ∗ whose distribution does not vary with k. The other term, zk represents the change in the noise due to evaluating the gradient at θk rather than θ∗. More precisely, we have
∗k = η
B ∑ i∈B(k) (k) i ∇fi(θ∗) and zk = η B ∑ i∈B(k) (k) i [∇fi(θk)−∇fi(θ∗)].
We define G(θ) = 1n ∑ i∇fi(θ)∇fi(θ)T to be the covariance of the model gradients. Note that ∗k has covariance ηλG(θ∗). To simplify notation in the Taylor expansions, we will use the following shorthand to refer to various quantities evaluated at θ∗:
G = G(θ∗), ∇2L = ∇2L(θ∗), ∇3L = ∇3L(θ∗), ∇R = ∇R(θ∗).
First we need the following standard decompositions of the Hessian: Proposition 1. For any θ ∈ Rd we can decompose ∇2L(θ) = G(θ) + E(θ) where E(θ) = 1 n ∑n i=1(fi(θ)− yi)∇2fi(θ) satisfies ‖E(θ)‖ ≤ √ 2ρfL(θ) where ρf is defined in Assumption 1.
The matrix G in Proposition 1 is known as the Gauss-Newton term of the Hessian. We can now Taylor expand Algorithm 1 and Equation (2) to first order around θ∗:
Φk+1(θ ∗) ≈ Φk(θ∗)− η [ ∇L+∇2L(Φk(θ∗)− θ∗) ] ,
θk+1 ≈ θk − η [ ∇L+∇2L(θk − θ∗) ] + ∗k.
We define vk = θk − Φk(θ∗) to be the deviation from the regularized trajectory. Then subtracting these two equations gives
vk+1 ≈ (I − η∇2L)vk + ∗k ≈ (I − ηG)vk + ∗k, where we used Proposition 1 to replace∇2L with G. Temporarily ignoring the higher order terms, we define the random process ξ by
ξk+1 = (I − ηG)ξk + ∗k and ξ0 = 0. (4) The process ξ is referred to as an Ornstein Uhlenbeck process and it encodes the movement of θ to first order around θ∗. We defer the proofs of the following properties of ξ to Appendix B:
Proposition 2. For any k ≥ 0, with probability at least 1 − 2de−ι, ‖ξk‖ ≤ X . In addition, as k →∞, E[ξkξTk ]→ λΠG(2− ηG)−1 where ΠG is the projection onto the span of G.
We can now analyze the effect of ξk on the second order Taylor expansion. Let rk = θk−Φk(θ∗)−ξk be the deviation of θ from the regularized trajectory after removing the Ornstein Uhlenbeck process ξ. Lemma 1 is equivalent to Pr[‖rτ‖ ≥ D ] ≤ 10τde−ι. We will prove by induction that ‖rk‖ ≤ D for all k ≤ t with probability at least 1− 10tde−ι for all t ≤ τ . The base case follows from r0 = 0 so assume the result for some t ≥ 0. The remainder of this section will be conditioned on the event ‖rk‖ ≤ D for all k ≤ t. O(·) notation will only be used to hide absolute constants that do not change with t 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 θ∗ of rk: Proposition 3. With probability at least 1− 2de−ι,
rk+1 = (I − ηG)rk − η [ 1
2 ∇3L(ξk, ξk)− λ∇R
] +mk + zk + Õ ( c5/2ηλ1+δ ) The intuition for the implicit regularizer R(θ) is that by Propositions 1 and 2,
E[ξkξTk ]→ ΠGλ(2− ηG)−1 ≈ λ(2− η∇2L)−1. Therefore, when averaged over long timescales,
1 2 E[∇3L(ξk, ξk)] ≈ λ 2 ∇3L
[ (2− η∇2L)−1 ] = λ∇ [ − 1
2η tr log
( 1− η
2 ∇2L(θ) )]∣∣∣∣ θ=θ∗ = λ∇R.
The second equality follows from the more general equality that for any matrix function A and any scalar function h that acts independently on each eigenvalue, ∇(trh(A(θ))) = (∇A(θ))(h′(A(θ))) which follows from the chain rule. The above equality is the special case when A(θ) = ∇2L(θ) and h(x) = − 1η log ( 1− η2x ) , which satisfies h′(x) = 12−ηx .
The remaining details involve concentrating the mean zero error terms mk, zk and showing that E[ξkξTk ] 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−ι, ‖rt+1‖ = Õ ( λ1/2+δ/2√
c
) .
The proof of Proposition 4 can be found in Appendix B. Finally, because D = Õ(c5/2λ1/2+δ/2), ‖rt+1‖ ≤ D for sufficiently large c. This completes the induction and the proof of Lemma 1.
Comparison with Blanc et al. [3] Like Blanc et al. [3], Lemma 1 shows that θ locally follows the trajectory of gradient descent on an implicit regularizer R(θ). However, there are a few crucial differences:
• Because we do not assume we start near a global minimizer where L = 0, we couple to a regularized loss L̃ = L + λR rather than just the regularizer R(θ). In this setting there is an additional correction term to the Hessian (Proposition 1) that requires carefully controlling the value of the loss across reference points to prove convergence to a stationary point.
• The analysis in Blanc et al. [3] requires η, τ to be chosen in terms of the condition number of ∇2L which can quickly grow during training as ∇2L is changing. This makes it impossible to directly repeat the argument. We avoid this by precisely analyzing the error incurred by small eigenvalues, allowing us to prove convergence to an ( , γ) stationary point of 1λ L̃ for fixed η, λ even if the smallest nonzero eigenvalue of∇2L converges to 0 during training.
• Unlike in Blanc et al. [3], we do not require the learning rate η to be small. Instead, we only require that λ scales with which can be accomplished either by decreasing the learning rate η or increasing the batch size B. This allows for stronger implicit regularization in the setting when η is large (see Section 6.1). In particular, our regularizer R(θ) changes with η and is only equal to the regularizer in Blanc et al. [3] in the limit η → 0.

heading: 3.2 Global Convergence
text: In order to prove convergence to an ( , γ)-stationary point of 1η∇L̃, we will define a sequence of reference points θ∗m and coupling times {τm} and repeatedly use a version of Lemma 1 to describe the long term behavior of θ. For notational simplicity, given a sequence of coupling times {τm}, define Tm = ∑ k<m τk to be the total number of steps until we have reached the reference point θ ∗ m.
To be able to repeat the local analysis in Lemma 1 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 a sequence of reference points {θ∗m} and a sequence of coupling times {τm}, we define the random process ξ by ξ0 = 0, and for k ∈ [Tm, Tm+1),
∗k = η
B ∑ i∈B(k) (k) i ∇fi(θ∗m) and ξk+1 = (I − ηG(θ∗m))ξk + ∗k.
Then we can prove the following more general coupling lemma: Lemma 2. Let X ,L ,D ,M ,T be defined as in Lemma 1. Assume f satisfies Assumption 1 and η satisfies Assumption 2. Let ∆m = θTm−ξTm−θ∗m and assume that ‖∆m‖ ≤ D and L(θ∗m) ≤ L for some 0 < δ ≤ 1/2. Then for any τm ≤ T satisfying maxk∈[Tm,Tm+1) ‖Φk−Tm(θ∗m+∆m)−θ∗m‖ ≤ 8M , with probability at least 1− 10dτme−ι we have simultaneously for all k ∈ (Tm, Tm+1],
‖θk − ξk − Φk−Tm(θ∗m + ∆m)‖ ≤ D , E[ξk] = 0, and ‖ξk‖ ≤X .
Unlike in Lemma 1, we couple to the regularized trajectory starting at θ∗m + ∆m rather than at θ ∗ m to avoid accumulating errors (see Figure 2). The proof is otherwise identical to that of Lemma 1.
The proof of Theorem 1 easily follows from the following lemma which states that we decrease the regularized loss L̃ by at least F after every coupling:
Lemma 3. Let F = D 2 ηνT . Let ∆m = θTm − ξTm − θ∗m and assume ‖∆m‖ ≤ D and L(θ∗m) ≤ L . Then if θTm is not an ( , γ)-stationary point, there exists some τm < T such that if we define
θ∗m+1 = Φτn(θ ∗ m + ∆m) and ∆m+1 = θTm+1 − ξTm+1 − θ∗m+1,
then with probability 1− 10dτme−ι, L̃(θ∗m+1) ≤ L(θ∗m)−F , ‖∆m+1‖ ≤ D and L(θ∗m+1) ≤ L .
We defer the proofs of Lemma 2 and Lemma 3 to Appendix B. Theorem 1 now follows directly from repeated applications of Lemma 3:
Proof of Theorem 1. By assumption there exists some θ∗0 such that L(θ ∗ 0) ≤ L and ‖θ0 − θ∗0‖ ≤ D . Then so long as θTm is not an ( , γ)-stationary point, we can inductively apply Lemma 3 to get the existence of coupling times {τm} and reference points {θ∗m} such that for any m ≥ 0, with probability 1 − 10dTme−ι we have L̃(θ∗m) ≤ L̃(θ∗0) − mF . As L̃(θ∗0) − L̃(θ∗m) = O(λ), this can happen for at most m = O ( λ F ) reference points, so at most T = O ( λT F ) = Õ ( η−1λ−1−δ
) iterations of Algorithm 1. By the choice of ι, this happens with probability 1−10dTe−ι ≥ 1−ζ .

heading: 4 Experiments
text: In order to test the ability of SGD with label noise to escape poor global minimizers and converge to better minimizers, we initialize Algorithm 1 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 in 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 1. We run experiments with two initializations:
Full Batch Initialization: We run full batch gradient descent with random initialization until convergence to a 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 et al. [21], we generate an 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 D for full details.
Experiments were run with ResNet18 on CIFAR10 [17] without data augmentation or weight decay. The experiments were conducted with randomized label flipping with probability 0.2 (see Appendix E for the extension of Theorem 1 to classification with label flipping), cross entropy loss, and batch size 256. Because of the difficulty in computing the regularizer R(θ), we approximate it by its lower bound tr∇2L(θ). Figure 3 shows the test accuracy and tr∇2L 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∇2L. The strength of the regularization is also strongly correlated with η, which supports Theorem 1.

heading: 5 Extensions

heading: 5.1 SGD with momentum
text: We replace the update in Algorithm 1 with heavy ball momentum with parameter β:
θk+1 = θk − η∇L̂(k)(θk) + β(θk − θk−1). (5) We define:
R(θ) = 1 + β
2η tr log
( 1− η
2(1 + β) ∇2L(θ)
) , λ =
ησ2
B(1− β) , (6)
and as before L̃(θ) = L(θ) + λR(θ). Let
Φ0(θ) = θ, Φk+1(θ) = Φk(θ)− η∇L̃(Φk(θ)) + β(Φk(θ)− Φk−1(θ)) (7) represent gradient descent with momentum on L̃. Then we have the following local coupling lemma:
Lemma 4. Let
X =
√ 2λn2ι
ν , L = cλ1+δ, D = c
√ L ι, T =
1
c2ηX ι , (8)
where c is a sufficiently large constant. Assume f satisfies Assumption 1 and η ≤ (2−ν)(1+β)` . Let θ follow Algorithm 1 with momentum β starting at θ∗ and L(θ∗) ≤ L for some 0 < δ ≤ 1/2. Then there exists a random process {ξk} such that for any τ ≤ T satisfying maxk≤τ ‖Φk(θ∗)−θ∗‖ ≤ 8D , with probability at least 1− 10dτe−ι we have simultaneously for all k ≤ τ ,
‖θk − ξk − Φk(θ∗)‖ ≤ D , E[ξk] = 0, and ‖ξk‖ ≤X . (9)
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 11−β . For the commonly used momentum parameter β = 0.9, this represents a 10× increase in regularization, which is likely the cause of the improved performance in Figure 4 (β = 0.9) over Figure 3 (β = 0).

heading: 5.2 Arbitrary Noise Covariances
text: The analysis in Section 3.1 is not specific to label noise SGD and can be carried out for arbitrary noise schemes. Let θ follow θk+1 = θk − η∇L(θk) + k starting at θ0 where k ∼ N(0, ηλΣ(θk)) and Σ1/2 is Lipschitz. Given a matrix S we define the regularizer RS(θ) = 〈 S,∇2L(θ) 〉 . The
matrix S controls the weight of each eigenvalue. As before we can define L̃S(θ) = L(θ) + λRS(θ) and ΦSk+1(θ) = Φ S k (θ) − η∇L̃S(Φk(θ)) to be the regularized loss and the regularized trajectory respectively. Then we have the following version of Lemma 1:
Proposition 5. Let θ be initialized at a minimizer θ∗ ofL. Assume∇2L is Lipschitz, letH = ∇2L(θ∗) and assume that Σ(θ∗) CH for some absolute constant C. Let X = √ Cdλι ν , D = cλ 3/4ι, and T = 1c2ηX ι for a sufficiently large constant c. Then there exists a mean zero random process ξ such that for any τ ≤ T satisfying maxk<τ ‖Φk(θ∗)− θ∗‖ ≤ 8D and with probability 1− 10dτe−ι, we have simultaneously for all k ≤ τ :
‖θk − ξk − ΦSk (θ0)‖ ≤ D and ‖ξk‖ ≤X , where S is the unique fixed point of S ← (I − ηH)S(I − ηH) + ηλΣ(θ∗) restricted to span(H).
As in Lemma 1, the error is 8 times smaller than the maximum movement of the regularized trajectory. Although Proposition 5 couples to gradient descent on RS , S is defined in terms of the Hessian and the noise covariance at θ∗ and therefore depends on the choice of reference point. Because RS is changing, we cannot repeat Proposition 5 as in Section 3.2 to prove convergence to a stationary point because there is no fixed potential. Although it is sometimes possible to relate RS to a fixed potential R, we show in Appendix F.2 that this is not generally possible by providing an example where minibatch SGD perpetually cycles. Exploring the properties of these continuously changing potentials and their connections to generalization is an interesting avenue for future work.

heading: 6 Discussion

heading: 6.1 Sharpness and the Effect of Large Learning Rates
text: Various factors can control the strength of the implicit regularization in Theorem 1. Most important is the implicit regularization parameter λ = ησ 2
|B| . 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 η needs to be inversely proportional to the batch size |B|. However, our analysis also uncovers an additional regularization effect of large learning rates. Unlike the regularizer in Blanc et al. [3], the implicit regularizer R(θ) defined in Equation (1) is dependent on η. It is not possible to directly analyze the behavior of R(θ) as η → 2/λ1 where λ1 is the largest
eigenvalue of ∇2L, as in this regime, R(θ) → ∞ (see Figure 1). If we let η = 2−νλ1 , then we can better understand the behavior of R(θ) by normalizing it by log 2/ν. This gives2
R(θ) log 2/ν = ∑ i R(λi) log 2/ν = ‖∇2L(θ)‖2 +O ( 1 log 2/ν ) ν→0−−−→ ‖∇2L(θ)‖2
so after normalization, R(θ) becomes a better and better approximation of the spectral norm ‖∇2L(θ)‖ as η → 2/λ1. R(θ) can therefore be seen as interpolating between tr∇2L(θ), when η ≈ 0, and ‖∇2L(θ)‖2 when η ≈ 2/λ1. 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/η.
The sharpness-aware algorithm (SAM) of [7] is also closely related to R(θ). SAM proposes to minimize max‖δ‖2≤ L(θ + δ). At a global minimizer of the training loss,
max ‖δ‖2≤ L(θ∗ + δ) = max ‖δ‖2≤
1 2 δ>∇2L(θ∗)δ +O( 3) ≈
2
2 ‖∇2L(θ∗)‖2.
The SAM algorithm is therefore explicitly regularizing the spectral norm of∇2L(θ), which is closely connected to the large learning rate regularization effect of R(θ) when η ≈ 2/λ1.

heading: 6.2 Generalization Bounds
text: The implicit regularizer R(θ) is intimately connected to data-dependent generalization bounds, which measure the Lipschitzness of the network via the network Jacobian. Specifically, Wei and Ma [30] propose the all-layer margin, which bounds the generalization error . ∑L l=1 Cl√ n √ 1 n ∑n i=1 1 mF (xi,yi)2
, where Cl depends only on the norm of the parameters and mF is the 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-forward network f(θ;x) = θLσ(θL−1 . . . σ(θ1x)), the all-layer margin satisfies3:
1
mF (x, y) . ‖{ ∂f∂θl }l∈[L]‖2 output margin of (x, y) =⇒ generalization error . ∑L l=1 Cl√ n √ R(θ) output margin
as R(θ) is an upper bound on the squared norm of the Jacobian at any global minimizer θ. 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(θ) lower bounds the all-layer margin mF 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 a 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 on computational resources managed and supported by Princeton Research Computing, a consortium of groups including the Princeton Institute for Computational Science and Engineering (PICSciE) and the Office of Information Technology’s High Performance Computing Center and Visualization Laboratory at Princeton University.
We would also like to thank Honglin Yuan and Jeff Z. HaoChen for useful discussions throughout various stages of the project.
2Here we assume λ1 > λ2. If instead λ1 = . . . = λk > λk+1, this limit will be k‖∇2L(θ)‖2. 3The output margin is defined as mini fi(θ)yi. The following uses Equation (3.3) and the first-order
approximation provided Wei and Ma [30] and the chain rule ∂f ∂θl = ∂f ∂hl ∂hl ∂θl−1 = ∂f ∂hl h>l−1.

Review summaries:
## Post-rebuttal     I 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.     ######  This 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.  The 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.

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.

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

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