Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ### Problem

This paper considers the effect of label noise on stochastic gradient descent. The setup is that there is a vector $v \in R^d$. We observe samples from $v^2\cdot x$. We only have $n < d$ samples but $v$ is $r$-sparse for $r < n < d$ which makes recovery possible information theoretically. The main result is that stochastic gradient descent with label noise, and without any explicit regularization will recover the ground truth. whereas adding spherical Gaussian noise does not.

### Pros and Cons

The problem is a clean toy problem with which to illustrate the gap between algorithms. It shows a clean separation between the power of label noise and that of random Gaussian noise. The model appears to be the simplest model where one can hope to see the regularization effects of noise (the simpler linear regression model wouldnt show these effects).  One possible criticism could be to ask if understanding this model is truly getting us closer to understanding what happens in deep nets. At this point it is hard to say, but proving such a result even in this simple model is not trivial, and is definitely a contribution.


### Evaluation
I think this is a solid theoretical contribution on an important problem, and the paper should be accepted.


### Further comments

I was a little confused by the comment that the coefficients are assumed to be in ${0,1}$ since they then satisfy $v_i^2 = v_i$ as this seems to linearize the model. The authors should probably clarify that this is actually not what is going on. It might be better to use a different setting of parameters even for exposition. 




review_title: Weak accept

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper demonstrates that for a particular model SGD with label noise and proper learning rate schedule recovers the (sparse) data generating model while GD with or without Gaussian noise does not. In the latter case, it fails because a stationary distribution is not achieved. The proofs in the appendix are quite involved, and as a result I did not carefully study them. But the authors provide helpful intuition for the results in the main text. 

While I think there is value in the work, I am not sure whether the fairly specific setting studied has much to say about neural networks. (Of course, not every paper needs to be about neural networks, but that's certainly the motivation of the paper.) There are a number of aspects to the work that limit its generality: the model, the label noise, the objective of reconstruction of sparse ground truth from the same model class, and the dataset modeling. The authors justify the model by saying that other works that have studied it, but don't otherwise try to justify its relevance. In Figure 1, the authors argue that label noise behaves similar to SGD, but I don't find this thorough or convincing enough that any results on label noise and the mechanism by which it operates should generalize to SGD. Also, whether studying an objective of learning as identifying the sparse ground truth model seems far from standard training of a neural network. As an example of my concern that the specifics by which the results are achieved may not apply in other scenarios, do the authors believe that GD with Gaussian noise fails for neural networks because a stationary distribution is never achieved, whereas it is achieved for SGD?

Overall, I think that the work is a bit too narrow and doesn't change our understanding of what non-spherical noise from SGD does to neural networks beyond what is already known.


Minor presentation points:

The paper became rushed at the end, as if the authors ran out of space. Subsections 3.2 "Stage 0" and 3.3 "Stage 1" are then followed by a very short paragraph inside 3.3 titled "Stage 2". 

Figure 1 is fairly difficult to parse with the number of noisy curves overlapping each other. Perhaps the authors could make their point with the minimal amount of experimental data here and relegate the rest to the appendix.
review_title: Rigorous results but on a limited problem

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors study the problem quadratically parameterized (linear) regression and study the behavior of SGD to solve it when the stochasticity added is in terms of label noise. They show that SGD (with this kind of noise) with arbitrarily large initialization converges to the ground truth solution, whereas there exist settings where Langevin dynamics or gradient descent would fail to converge to this solution. The proofs are carried out carefully and are correct as best as I could verify. The authors also provide experiments on synthetic data to support and motivate their theory.


Some questions/comments:
1. Why are three stages with decreasing step-sizes needed for the analysis? Can we expect a similar result to hold if a constant, but, small step-size is chosen instead?
2. The generative model assumes that the label y has no added noise. Are the theoretical result robust to additive noise?
3. The authors point out on page 4 that the sample complexity is worse that LASSO (which is fine), but, do not remark why this is the case. It would be insightful if the authors could add a comment about why this is the case, and if this was experimentally observed as well.
review_title: the authors study an interesting problem and provide sound theoretical analysis

final_score: rating: 7: Good paper, accept
review_content: This paper considers the implicit regularization of stochastic gradient decent (SGD). The authors analyze SGD with label nose in the quadratically-parameterized model and prove that it converges to the sparse ground-truth even if started with large initialization. The authors also prove that SGD with Gaussian noise (Langevin dynamics) does not converge to the ground truth at zero under the overparameterized regime.

This is a solid contribution with theoretical insights on SGD with label noise. While the theoretical results are deep with long proofs, their outlines and meanings are well explained.

- The difference (affinity) between the deep neural network and the quadratically-parameterized model is mainly discussed numerically (Figure 1). It would be nicer to discuss gaps between them theoretically, if possible. For example, the contraction of SGD in the initial phase (Thm 3.1) is reminiscent of the effect of singularities in neural networks discussed in references such as:
Guo et al.: Numerical Analysis near Singularities in RBF networks, JMLR, 19(2018), 1-39.
It would be nicer to discuss if this analysis of the initial phase has something to do with singularities.

- p.7, footnote 7: What is the second-order effect (of zero-mean noise)?

Minor:
p.4, Langevin dynamics/diffusion: The last sentence is duplicated.

review_title: Solid contribution with theoretical insights on SGD with label noise

Meta-review: The paper shows that for a simple nonlinear (quadratically parametrized linear) model, stochastic gradient descent (SGD) with a certain label noise and learning rate schedule recovers the data generating model. In contrast, gradient descent with or without Gaussian noise fails. While the results are novel and interesting, they hold for a rather specialized model, which may not reveal anything about deep neural networks, which was the original motivation for this work. Given the narrow focus of the work, unfortunately, I cannot recommend that the paper be accepted. 
Decision: Reject