Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper validates the SDE approximation to SGD under finite (non-infinitesimal) learning rate by proposing a novel algorithm SVAG. This paper theoretically proves that SVAG is an order-1 weak approximation to the SDE, and empirical experiments show that SVAG behaves similarly to SGD. Using SVAG as a theoretical tool, this paper shows new theoretical insights in the linear scaling rule and the necessary condition for the SDE approximation.
main_review: -	It is claimed in this paper that the discrete nature of SGD is not an essential ingredient to the generalization (Line 130—133), as evidenced by Fig. 4. However, recently Smith et al. (2021, https://openreview.net/pdf?id=rq_Qr0c1Hyo) show a contradictory result that discretization influences generalization significantly by proving that discrete time SGD actually minimizes a “modified loss”. Admittedly, the difference in theory may originate from the different minibatch sampling mechanism considered in either paper. The mechanism considered in the current paper is random with replacement, while that in Smith et al. (2021) considers permutation of minibatches in each epoch (sample without replacement in each epoch), which is perhaps more practically relevant. However, I assume the empirical analysis in the current paper is performed with the usual minibatch sampling mechanism that is considered by Smith et al. (2021), but why do the empirical results in the current paper suggest that discretization is not essential? Suppose one considers the permutated minibatches like Smith et al. (2021) for SVAG, would the process that SVAG approximate becomes another continuous-time stochastic process but with the modified loss of Smith et al. (2021)? How can we reconcile the results in the current paper and Smith et al. (2021)?
-	In Fig. 4, SVAG generalizes better and is more stable than SGD as l increases at each effective step. Because SVAG is getting close to SDE as l increases, does it imply that the SDE would provide a good generalization performance given that we can exactly compute it? Would SDE yield a generalization upper bound for SGD?

limitations_and_societal_impact: Limitations of the SVAG algorithm are adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider a discrete time algorithm (SVAG) which is indexed by a parameter $l$ and which exactly corresponds to SGD when $l= 1$.  They show that this algorithm weakly converges to SGD's continuous SDE approximation as $l$ goes to $\infty$, and this without having to take the step-size infinitely small. They also provide a setting in which the SDE approximation provably fails to capture SGD's dynamics. Finally they give a testing rule for the SDE approximation to hold. 
main_review: The paper is well written and easy to read. The motivations underlying their work is clear and are pertinent to me. The related work is concise but relevant. All the results are clear and are discussed. My principle concern relies in the fact that the authors show that SVAG converges weakly to the classical SDE approximation (2), however (except for the experiments Figure 4)  it is not clear how SVAG and SGD compare as soon as $l$ is not equal to $1$. However I still believe that their paper gives some valuable insight on how and when the Itô SDE approximates well SGD for macroscopic step sizes.


Here are some minor concerns: 
- l207: "(independent of $\eta$): I assume you mean "independent of $l$"
- maybe it is just me but it took me some time to understand that SVAG has the same first and second order moments as the Itô SDE (2) **when using a discretisation $\mathrm{d} t = \eta / l$** (and not $\mathrm{d} t = \eta$ as for SGD). This is clear when looking at the theorem but making it more explicit and explaining in the main text would make it easier to understand.
- Figure 1: what is the value of $l$ here ?
- Figure 3: how come there is this accuracy drop for gradient descent at step ~15000 ? 
- Section 5.1: I would have enjoyed a a more in depth discussion around theorem 5.2: do you think this condition or a similar condition holds for other losses than scale invariant losses ? what is particular for scale invariant losses for this results to hold ? why consider a regularising term $\lambda \vert x \vert^2$, does the result still hold without regularisation ?
- Section 5: I am not familiar with scale invariant losses, my overall concern is how relevant are your results outside this class which (to me) seem very specific. 
limitations_and_societal_impact: Limitations are discussed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper has two main contributions. Firstly, it presents a practical simulation algorithm, SVAG, which is shown to converge weakly to the Itô SDE approximation of SGD over finite time horizons (with no restrictions on the learning rate $\eta$). Experimental evidence on deep nets is given to support the claim that SVAG can be used as a diagnostic for empirically testing if SGD and its SDE approximation have similar behaviour. The second main contribution provides sufficient conditions for the failure of the SDE approximation and linear scaling rule when the loss function is scale invariant. This theory is further supported by experiments on deep nets.
main_review: Strengths:

* The SVAG algorithm is new and interesting. It provides a practical methodology for weakly approximating the SDE corresponding to SGD, $\mathrm{d} X_t = -\nabla \mathcal{L}(X_t)\mathrm{d}t + \big(\eta \Sigma(X_t)\big)^\frac{1}{2}\mathrm{d}W_t$. To the best of my knowledge, it is the first algorithm that does so using stochastic gradients and with no restriction on $\eta$. The authors demonstrate how it can be applied as a diagnostic tool for testing if SGD and its SDE approximation have similar behaviour. This is useful as, for example, the linear scaling rule occurs when the SDE approximation holds (Smith et al., 2020).

* The paper gives new theoretical insights into the failure of the SDE approximation and linear scaling rule – which is certainly of practical importance. Their theory fits nicely with a wide array of experiments.

* The authors also discuss the role of non-Gaussian noise in their findings. In particular, they give experimental evidence that SGD and NGD can give similar test performances. This indicates that it is reasonable to model the gradient noise in SGD as Gaussian. Whilst these results are presented as secondary to the main results, they may be very relevant to the wider literature.

* The experiments are thorough.

* The paper is clearly written.

Weaknesses:

* The authors show that SVAG converges to the SDE in a weak sense, however in their experiment (figure 4), it appears they are making conclusions based on a single trajectory (which would only be justified by if SVAG converged to the SDE in a pathwise sense). If this is the case, then one or two sentences clarifying the limitations of the experiments would be helpful.

* Similarly, the authors claim that the convergence of SVAG to the SDE for "small values of $l$" is "confirmed in Figure 4". I find this to be too strong a claim and would prefer the statement to be weaker, for example "consistent with" instead of "confirmed".

Conclusion:

Overall, I believe this is a strong paper. In particular, it provides interesting theory and practical methodologies for testing the effectiveness of SDE approximations (which are already popular tools to studying SGD). The paper supports this with a wide variety of experiments.

Minor comments:

* In the introduction, the authors write "but the proof needs the LR of SGD to be an unrealistically small (unspecified) constant". How do we know if the LR is unrealistic if it is unspecified?

* The authors write "at equilibrium, the gradient norm must be smaller than its variance". Is it not the squared gradient norm?

* I'm not sure if plotting the train and test accuracies of standard gradient descent in Figure 3 is helpful.

* It is not clear (from the main body of text) why the scale invariance of the loss function $\mathcal{L}_\gamma$ is essential to the theory in Section 5.

Typos:

* Stochastic Gradient Gescent (page 1)
* $E\big[\big(\nabla \mathcal{L}_\gamma (X) -  \nabla \mathcal{L}(X))\big(\mathcal{L}_\gamma (X) -  \nabla \mathcal{L}(X)\big)^{\mathsf{T}}\big]$ is missing a $\nabla$ (pages 2 and 5)
* $\sqrt{\frac{\eta}{l}} \Sigma^l(x) = \sqrt{\eta}\Sigma^{1}(x)$ (page 5). Surely it is $\frac{\eta}{l} \Sigma^l(x) = \eta\Sigma^{1}(x)$.
* (ii) is used instead of (iii) in Lemma 4.5 (page 6)
* The left quotation mark in ”equilibrium” is the wrong way round (page 7)
limitations_and_societal_impact: * I believe the authors could better address the potential limitations of their experiments (see "Weaknesses" part of main review).

* Theorem 4.3 only applies on a finite time horizon $[0,T]$, whereas the optimization/MCMC literature is usually concerned with quantities obtained as $t\rightarrow\infty$. It could be worth highlighting this difference.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: SDE has been used as an approximation to help understand the implicit bias of SGD. This paper studies the validity of such approximations, which hasn't been formalized in prior work for realistic choices of learning rates. The contributions are three-folds:
  - Proposing "Stochastic Variance Amplified Gradient" (SVAG), an efficient numerical method to test whether the trajectories of SGD and the corresponding SDE are close.
  - Empirically verifying SVAG can be made to follow SGD. Since SVAG provably follows SDE under certain conditions, this means SDE also tracks SGD well by transitivity.
  - Providing necessary conditions for SDE and LSR to track SGD.

main_review: **Significance**: this work studies the importance question of the validity of approximating SGD with SDE. However, this paper does not provide a formal answer. Rather, the paper provides an indirect argument via the proposed SVAG: SVAG provably follows a certain SDE and empirically tracks SGD well, hence such SDE should also be close to SGD.

On the positive side, since SVAG can be made to track SGD well empirically, this suggests we can potentially study SVAG (or its approximations) instead of SGD. Moreover, the paper provides conditions for the applicability of LSR (i.e. NSR not too small, batch size not too large) which are valuable contributions.

However, the fact that SVAG interpolates between SGD (when taking $l=1$) and SDE (when taking $l \rightarrow \infty$) seems to be a negative result for using SDE to approximate SGD, since this means SDE and SGD sit on opposite sides of the spectrum and are _not_ close to each other. This suggests that SVAG is not the proper tool to study the SDE approximation to SGD, and I would like to have the authors' clarification on this.

**Writing**: the paper states the messages of this work are clear overall, but some 
- Typo: end of line 65: "the benefit of SGD"
- Typo: end of line 266: "the equilibrium distributions"
- The first paragraph of Sec 5: what's the purpose of the discussion on weight decay?
- Fig 4: the figures are a bit too crowded to read; perhaps also consider changing the color scheme since currently it's hard to tell between $l=1$ vs $l=32$.
- Typo: end of line 828 (Thm E.1) should be a stop not a colon.

========
Post-rebuttal update: I thank the authors for their responses and have raised my score.
limitations_and_societal_impact: The authors discuss implications of their theoretical results and potential insights for practitioners. Immediate societal impacts beyond the research community do not apply.
review_title: null

Meta-review: The paper proposes a practical algorithm called SVAG, which is shown to converge in the weak sense
to the SDE approximation of SGD, for even moderately large step sizes.
Authors demonstrate its performance via experiments on neural networks, and show that SVAG can diagnose if SGD and its SDE approximation have similar behaviors. Authors further investigate the conditions in which the SDE approximation fails. 

The motivation of this paper is clear, and very timely. All the assumptions and the results are presented in a clear way. 

All reviewers agree that this paper is well-written and its results are interesting. Authors should address reviewers' suggestions in the final version of their work. Specifically, authors should add a discussion on the limitations of the experiments and amend the statement about SVAG converging for small values of l, clarify the bound in Li et al., 2019, and add more intuition about the importance of scale invariance.
Decision: Accept (Poster)