Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the implicit bias of SGD over GD trained solutions for a regression task, with MSE loss, and a quadratic parameterization of the regression coefficients.  Building off recent analysis demonstrating how the initialization for GD toggles between an implicit sparse/L2 regularization on the interpolating solution, they demonstrate that SGD has the same effect but with a strictly smaller initialization (leaning to sparse).  To get this conclusion they model SGD using an SDE with a spatially dependent, anisotropic diffusion.  Lastly, they demonstrate their main claims on synthetic data.
main_review: **Originality/Significance:**
The key qualitative assumption discussed in this paper is "the effect of the implicit bias is controlled by the convergence speed of the loss: the slower it converges, the sparser the selected solution will be."  As far as I am aware, this is a very novel statement and quite significant (even if only made for a constrained class of models).  Overall, this work was very well done, however I think more emphasis could have been on experiments (such as some of the suggestions I give below) and discussing the qualitative takeaways that might apply to the general class of nonlinear networks. I agree with the authors, the most interesting direction for future work would be "whether the integral of the loss also controls the difference of implicit regularisation for more general architectures."  A longer discussion at the end on the connections of this analysis to nonlinear networks (where the benefits of SGD really shine compared to GD) would be very helpful.

**Clarity/Quality:**
The writing and mathematics in this paper are incredibly clear and well done.  I found the flow very natural and the discussion of related work very helpful for grounding their analysis.  The experiments were well documented and explained.

**Areas for Improvement:**
- Throughout the work (such as in abstract) you say "better the bias", but its not clear what "better" means.  Is there another description that might be more specific you can use as your tag line? Such as "sparse"?
- This analysis is done assuming a batch size of 1? Can this be extended to mini-batches?  A discussion about this assumption/limitation should be given.
- In the buildup to the SDEs you never explicitly assume the noise term is Gaussian, as done in many of the "SDE for SGD" papers.  Yet implicitly it seems like you are,  as the Euler-Maruyama discretization of equation (3) would lead to gaussian noise with the same covariance as your noise term.  I think its worth having a discussion about this, as the Gaussian assumption has been one of the major sources for complaint on the "SDE for SGD" literature? 
- The statement on line 206/207 "the recovered solution minimizes the same potential as for gradient flow but with an effective parameter which is strictly smaller" makes me want to see an experiment where you run SGD with $\alpha$ and compute $\alpha_\infty$ from trajectory then run GD with $\alpha_\infty$ and compare overall optimization time and final solution.  An experiment like this would definitely help convince me of the statement "However it is clear experimentally that SGD systematically largely wins the trade-off over GD".  If for example the SGD and GD trajectory both converge to same performing solution but SGD does it faster, then I would be very convinced on this.
- All your experiments used features generated from an isotropic gaussian. I understand that this was done to make distance to sparse solution a measure of validation performance, but I would have been very curious to see how dynamics change with features from an anisotropic gaussian.  Intuitively, I would assume that anisotropy would have a large effect on the SGD dynamics...and maybe even the final solution reached.
- The section "Doping the implicit bias with label noise" is interesting.  I would devote more space to this discussion in revision and pull experiments up from appendix.

**Specific Comments:**
- Consider citing the recent work "ON THE ORIGIN OF IMPLICIT REGULARIZATION IN STOCHASTIC GRADIENT DESCENT"
- [line 105-106] "All inequalities between vectors should be understood value by value" => replace "value by value" with "element-wise"?
- In the section "Implicit bias and hyperbolic entropy" the analysis in [32] you are referencing is for the same quadratic parametrization correct?  If so, can you make this clear.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the implicit bias of SGD in diagonal linear networks. Specifically, through the study of SGD continues time version, i.e., stochastic gradient flow, the authors investigate the noise influence on the generalization performance. The authors show that with high probability stochastic gradient flow converges to zero loss solution that enjoys better generalization properties than the solution obtained by gradient flow. In addition, they show that slower convergence results in better generalization.
main_review: The paper studies the implicit bias of SGD in diagonal linear networks and the square loss. To this end, the authors model SGD dynamics using its continuous time, i.e., stochastic gradient flow (SGF).

The paper main contributions are:
-	The authors prove that with high probability SGF converges to zero loss solution.
-	The authors characterize the obtained solution (similarly to [32]). Specifically, their characterization implies that SGF biases the flow toward solutions with better sparsity inducing properties than GF (smaller effective $\alpha$).
-	The authors provide experimental results that validate their model and theoretical results.

My main question:
-	When modeling SGD the authors assume that all partial losses are approximately uniformly equal to their mean (Appendix A). Can you please elaborate and justify this assumption? Also, this assumption should appear in the main paper.

Clarity/writing: 
-	The paper is well written, and the results are clearly stated.

Minor comment:
-	Figure 2 will be more clear if you include the fact that $\Vert \beta_t - \beta_{\ell_1}^*\Vert_2^2$ corresponds to the validation error in the caption (and not just in section 5.1) 

---

Update: Thank you for the detailed rebuttal. I accept your answer regarding the modeling choices you made.

limitations_and_societal_impact: The authors discussed the limitations of their results.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Summary:
This paper studies the implicit bias of stochastic gradient flow (SGF) over a linear model, re-parameterized as a quadratic difference: $\beta=(w_1)^2 - (w_2)^2$. The paper establishes that in the said setting, SGF has implicit bias towards sparsity (lower $\ell_1$ norm w.r.t regular GF).
main_review: **Originality** - The paper uses original analysis to discuss stochasticity in the specific framework. The paper insinuates that SGF is presented in this work (line 151-154). Yet previous work exists [2] therefore it is difficult to determine exactly how novel are the ideas. In addition, the paper discusses some related work rather superficially (lines 75-77) neglecting to cite relevant works such as [1] that discuss implicit bias of linear regression with SGD vs GD.

**Quality** - Overall, the paper is well written. My biggest concern is the setting, it is not clear to me why diagonal networks are an interesting re-parameterization of linear networks. Additional issues are (1) Unrealistic initialization, the analysis holds for any initialization such that $w_{+}=w_{-}$ which also means $\beta_{w}=0$, it is not clear how this relates to standard initialization schemes. (2) The role of $\alpha$ - as stated in the paper, the tradeoff is between generalization and optimization (line 212), therefore a user can set it to a desired value and control the tradeoff, it is not clear how the $\alpha_{\infty}$ relates to initial $\alpha$ except from being upper bounded by it. Further discussion can be interesting.

**Clarity** - The paper is very clear in an abstract level, the claims in the main manuscript as well as the specific setting are very clearly written. As for the analysis, there seems to be no apparent structure for the mathematical analysis. In the appendix it is not clear what are the important details and which sections are more technical. It made it hard to understand specific claims. For example, I would expect a more clear presentation and discussion of $\alpha_{\infty}$ which is written implicitly in proposition 1.

**Significance** - Understanding the effect of stochasticity on the implicit bias of GD is extremely significant, with that being said, this work is limited to a non-realistic setting which makes this result weaker.

[1] Wu, Jingfeng and Zou, Difan and Braverman, Vladimir and Gu, Quanquan. Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate

[2] Ali, Alnur and Dobriban, Edgar and Tibshirani, Ryan. The Implicit Regularization of Stochastic Gradient Flow for Least Squares


**---------------------------------------------------------------------------**

**Update**: Thank you for the detailed rebuttal.

After reading other reviews and authors' responses - I believe I underestimated the significant of the problem setup and the contribution of the paper. Therefore I chose to change my score accordingly.

Good luck.


limitations_and_societal_impact: Limitations:
- Result applies only to diagonal networks.
- Initialization schemes does not follow standard schemes.

The reviewer does not see any negative social impact of the submitted work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper the authors study the dynamics of SGD for diagonal linear networks. The exact expression of implicit bias is derived, showing that SGD with some initialization scale is equivalent to full batch GD (or gradient flow) will a smaller effective initialization scale. In addition, SGD slows down the convergence speed, and the slower the convergence, the smaller the effective initialization scale. For sparse problems, the smaller effective initialization scale induces better generalization, as also demonstrated empirically on synthetic data.
main_review: Overall, I think this is a good paper. While previous works that study diagonal linear networks only consider the case of full batch GD (or gradient flow), the authors provide a novel analysis for the case of SGD. To this end, the authors model the dynamics through a stochastic differentiable equation, which solution is then analyzed.

The analysis is highly non-trivial and this is an important step forward since in practice SGD is usually used. Also, the effect of label noise on the effective initialization scale is naturally integrated into the proposed analysis.

The paper is well written and easy to read.

Weaknesses:
1.	The analysis only considers the case of batch size = 1 and it is not clear how the batch size affects the effective initialization scale. 
2.	The effect of the step size in Theorem 1 is not clearly discussed. On the one hand, a large step size will accelerate the convergence and thus the integral of the loss will be small, but on the other hand, the step size appears explicitly in the exponent.  So, is increasing step size result in smaller effective $\alpha$ ? If yes, is it correct also for GD or only for SGD ?
3.	It would be good to complement the paper will experiments on real data with real networks. Clearly, the interaction of initialization scale, batch size and step size is an important practical question.

More comments:
- line 130: I don’t think the model is equivalent to the model $\beta=u\odot v$, as discussed in section 4 of [1].
- In Theorem 1 the tradeoff in $p$ is not clear. It seems that $p$ can be arbitrarily small.
- In Theorem 1, can you explain why a bound on the step size is needed ? Is it for stability reasons ?
- Several relevant papers are missing:

On the implicit bias of SGD:

https://arxiv.org/abs/2101.12176

https://arxiv.org/abs/2003.07802

On diagonal linear networks and mirror descent:

https://arxiv.org/abs/2007.06738

https://arxiv.org/abs/2004.01025

- In section 3 the kernel regime is discussed. Is it possible to have a similar discussion for the rich regime ? Is there a difference between SGD and GD in the rich regime ?
- In line 220 the integral goes to 0, I couldn’t find the proof in the appendix. Also, the upper bound of the integral in proposition 3 goes to infinity when $\alpha\rightarrow\infty$. Can you explain this ?
- Can you explain why the equality in line 303 is correct ?
- $\alpha$ is sometimes used as a scalar and sometimes as a vector, and it will be good to distinguish between them, e.g. make vector a bold symbol. For example, in proposition 3 it is not clear if $\alpha$ is a scalar or a vector.
- In section 5.1 please specify what is the step size.
- In section 5.3 will be useful to compare the result to [12].

typos:
- line 160: I think the second diag is not needed.
- line 316: why -> while
- line 348: understand -> understanding
- line 444: $\alpha_t$ is incorrectly defined
limitations_and_societal_impact: N/A
review_title: null

Meta-review: Reviewers generally agreed that the paper is clearly written, technically solid and interesting.  Reservations with regards to the significance of the analyzed setting (diagonal linear neural networks) were raised, but given that this setting already received notable attention, the committee reached a decision by which this paper comprises a meaningful step forward (analysis of stochasticity), and should thus be accepted to the conference.
Decision: Accept (Poster)