Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: # Pros:
+ 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).
+ 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.
+ Empirical observations about label noise are partly justified by the presented theory.

# Cons:
- 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?
- 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).
- 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.
- 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.
- 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?
- 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?
- 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?





# Small issues:
* l.125. $\theta^*$ -> $\theta$
* l.138. $\phi$ -> $\gamma$


# Overall
My 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. 




----

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

A 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.
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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).

-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.
Moreover, 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.
In 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?

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

-Some minor clarifications

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

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.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

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

In 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?

Since 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]$?

[1]:G. Blanc, N. Gupta, G. Valiant, and P. Valiant.  Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process.
limitations_and_societal_impact:  The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: ## 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.
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. 

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

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

### Minor
I 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?
limitations_and_societal_impact: Yes
review_title: null

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)