Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work proposes HSGD as a continuous approximation to SGD (multi pass version). It first shows an approximation theorem that justifies the closeness between the continuous HSGD and the discrete SGD. Then by studying HSGD it characterizes the limiting training and population risks through Volterra dynamics. Based on the theorems, the paper concludes that (1) multi-pass SGD does not have implicit bias over GD, at least in the setting of least square, (2) SGD has an effect of implicitly conditioning, that accelerates the convergence. 
strengths_and_weaknesses: # Strengths
+ The implicit conditioning could be an interesting perspective to understand the effectiveness of SGD.

# Weakness
- I find the statement of related literature could be improved. 

- please correct the bib formate of reference [36]

- Line 49, could have mentioned [55]. In particular, [55] showed a similar result that multi-pass SGD generalizes worse than GD in the linear regression setting. The authors should mention this when stating their contribution and in Sec 3.1

- Thm 1 and Thm2 seem to from [39]. The authors should explicitly mention [39] after their Thms 1 and 2. Moreover, could you please explain the delta of thms 1 & 2 compared to that in [39]? 

- Thms 4 and 5 are from [36, 37, 38] (as explicitly mentioned in line 901 in Appendix). In this sense, the authors should explicitly clarify this issue in their main text. The current writing has caused a huge misunderstanding about its true contribution when I first go through the paper. 

- Line 90. Could you explain why SGD with momentum degenerates to SGD?

- Lemma 1. What is $\gamma$ here? Note that a somewhat related lemma has been shown in [55].

- Line 119-124. I am actually confused, because it has been long known that a continuous SME approximates SGD, see [L 2017] and [H 2017]. 

- Line 148. I believe [21] is a wrong citation here. Could you point out where in [21] iid sub gaussian is assumed? 

- Line 158. The notation is a bit confusing, is $\gamma$ still referring to the stepsize?

- Thm 1 is hard for me to interpret. First of all, how do you compare this result to the SME approximation proved by [L 2017] and [H 2017]? 
Secondly, Could you provide some examplar regime where the approximation error is small? It seems for the error to be small one needs $d$ to be large, but on the other hand that implies $n$ needs to be large. How is the error affected by stepsize?

- Thm 2 is also hard for me to interpret. 













[L 2017] Li Q, Tai C, Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. InInternational Conference on Machine Learning 2017 Jul 17 (pp. 2101-2110). PMLR.

[H 2017] Hu W, Li CJ, Li L, Liu JG. On the diffusion approximation of nonconvex stochastic gradient descent. arXiv preprint arXiv:1705.07562. 2017 May 22.
questions: Please see above.
limitations: Please see above. It seems most of the theorems are from existing works. Thus this particular work presents little delta to me. Another thing bothers me is that, the authors did not try to explicitly discuss this issue in their main text.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the generalization ability of the multi-pass SGD on high-dimensional convex quadratics by relating it to a stochastic differential equation called homogenized stochastic gradient descent (HSGD). The authors show that using the HSGD, a precise risk trajectory of SGD can be established, which reveals the conditions on the data distribution that SGD is more efficient than GD. The authors further extend the analysis to streaming SGD and show its inability to capture certain salient features compared to multi-pass SGD.


strengths_and_weaknesses: Overall, the strengths of this paper include

(1) establishing an approximation result between SGD and HSGD.
(2) showing that SGD negatively impacts generalization performance.
(3) showing how SGD accelerates convergence.
(4) showing the inability of streaming SGD.

Weaknesses are as follows:
(1) Although the authors provide a precise characterization of the generalization error of SGD, the formula of the $Psi_t$ and $\Omega_t$ are still difficult to follow. There lacks a good interpretation of the developed results, especially in the non-asymptotic setting that $t$ is not approaching infinity. Note that for many high-dimensional linear regression problems, GD/SGD with early stopping can give good generalizable solutions while the overfitting will occur if $t\rightarrow \infty$.

(2) Additionally, in some cases the condition number $\kappa$ could be extremely large (when the matrix $T$ or $A$ has a fast decaying eigenspectrum). Then the convergence rate to $\Psi_\infty$ and $\Omega_\infty$ may not be that interesting as they will be super slow and people tend to early stop the optimization algorithm. 

(3) In section 3.2, a detailed explanation about why SGD is more efficient than GD is missing. It seems that the authors only claim that SGD with a constant learning rate can match the convergence of GD, but how this lead to the argument that SGD is more efficient is missing. The authors may need to provide a rigorous comparison between the efficiency of SGD and GD/M-GD.

(4) Lemma 1 is not new in the literature (at least in the case of $\delta=0$). The following work (see their Theorem 1) has shown that for any feasible learning rate, the excess risk of multi-pass SGD must be greater than or equal to GD,  then taking the limit $learning rate \rightarrow 0$ can imply the results of Lemma for the case of $\delta=0$ The authors may need to comment this in the surrounding text.

D. Zou, J. Wu, V. Braverman, Q. Gu, and S. M. Kakade. Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime. arXiv preprint arXiv:2203.03159, 2022.


questions: Please refer to the weakness section.
limitations: Please refer to the weakness section.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors of the paper present the following contributions:
- They show that, in the high dimensional limit, multipass SGD behaves, in terms of empirical and population loss, as a SDE with a particular noise covariance
- They further show that, in the high dimensional limit, this SDE converges to a deterministic Volterra Dynamics
- They analyse this dynamics to compare to the one of the gradient flow showing that noise negatively impact the population loss but can accelerate convergence.

strengths_and_weaknesses: ### **Strengths**

- First I have to say that the paper is well written, pleasant to follow and well illustrated by the experiments.
- Second and more importantly, I really like the results concerning the high dimensional set-up: comparing the losses dynamics to the one of an explicit SDE that can be studied is a good idea. And even I had no time to check the proof, the result seems sound. Then, concentration to Lotka-Volterra dynamics is also a nice development of the analysis!


### **Weaknesses**

- Perhaps the first weakness is the limitation of the result: the authors are very precise in the specific setting of linear regression, provide some good material to analyse it, but it is hard to conclude anything deep from their analysis.
- I know this is a large tendency in the ML community, but I think that overselling the results is counter productive when writing a paper. A good example is the title of the paper where the fact that the focus is on Least-squares should be written. Also, trying to systematically conclude that SGD is "better" or that this can explain the amazing performance of SGD in practice is a bit overselling. The results of the authors being already strong, there is no need to oversell the paper like this. 
- In the same direction, I find the introduction confusing and the references to the literature incomplete. I think that the authors should be more specific and really focus on the least squares literature, and not try to refer to the deep learning one (or maybe just at the end to motivate further investigations). In terms of literature, lign 50, the multipass is not properly covered and [1,2] among others are worth mentioning. 
- The paragraph on **Diffusion approximations and homogenized SGD** should be rewritten. A lot of work has been done to model SGD as a diffusion. [3] properly explains how to model SGD with a SDE, [4] analyses it respecting the geometry of the noise and the sentence *we lack a precise connection between a concrete SLD and a practical nonconvex learning problem* is simply wrong as [5] studied exactly a SDE model in a non-convex setting. Finally, to be consistent with the rest of the paper, it would be great that $\gamma$ appears in the noise term of equation (5). Note also that in the isotropic case, if $\Sigma$ is proportional to the identity, the invariant measure is not proportional to $e^{-f}$ but to $e^{- C_{\gamma} f}$, with $C_{\gamma}>0$ some constant.


[1] Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. Journal of Machine Learning Research, 18(97):1–47, 2017

[2] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, pages 8125–8135, 2018.

[3] Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. Journal of Machine Learning Research, 20(40):1–47, 2019.
 
[4] Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysis, *Preprint*, 2021.

[5] Scott Pesme, Loucas Pillaud-Vivien, and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34, 2021.


### **Minor Flaws**
- [36] is an empty reference
- lign 92: miss a $dt$ in equation (5) for the drift
- lign 166: explain with you take $tn$ as the time for SGD
- lign 250: parenthesis problems
questions: I have one question for the SDE limit of the model: could the authors explain why the quadratic case is special to derive the SDE limit ? How could it be extended to a general convex loss ? or even to a non-convex setup ?


limitations: As I already discussed the limitations in the previous boxes, I'll put the conclusion of my review here. I truly think this is a nice paper, with solid result and an interesting high-dimensional limit dynamics.  I now put a weak accept, but will be happy to raise my score if the authors temper a bit the overselling part, correct the minor flaws and the referencing.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper uses SDE (so-called HSGD) to study the optimization property of both streaming and multi-pass SGD over the quadratic functions. First, they show that the risk of SGD is no better than GD, showing that there is no implicit regularization in this setting. Next, they show the connection between SGD and HSGD, enabling them to use HSGD to study the properties of SGD. Their main contribution is to show that SGD enjoys a different condition number that sometimes leads to a better convergence rate over GD. Moreover, they also study the streaming SGD using the same framework and relate them to compare the generalization.
strengths_and_weaknesses: ### Strengths
* The most interesting result is to show that SGD has a different condition number for **convex quadratic functions**. In particular, SGD outperforms GD if the spectrum of the Hessian has some outliers, which is usual in realistic applications, see Figure 2.
* The Volterra Dynamic, though not first proposed by this paper, its analysis might be of independent interest to study the behavior of SGD.

### Weaknesses
* In Figure 2, they run random feature models for realistic applications, i.e., CIFAR-10, CIFAR-5m, showing that in these cases the Hessian is ill-conditioned, supporting their main arguments that SGD outperforms GD on these realistic applications. However, note that the random feature model is a convex optimization problem, which differs a lot from realistic neural networks. Hence, small ICR on the random feature model cannot be used to show that SGD outperforms GD on realistic optimization problems **directly**. Next, the author should provide the "real" convergence comparison between SGD and GD even for the random feature models to support their main observation. ICR is just an indicator for the comparison between SGD and GD. There might be an approximation error due to the usage of HSGD and also the dimension, iteration time is finite. Hence, without this simulation, I am not convinced that SGD does outperform GD in terms of convergence speed.

* The argument that there is no implicit regularization might be trivial. For convex optimization, **any** algorithms, if convergent, then they should converge to the same function value (for strongly convex cases, they converge exactly to the same point). To my best knowledge, all the previous papers studying the implicit regularization focus on nonconvex optimization.

* The introduction of Volterra Dynamics is limited, which is very unfriendly to those unfamiliar with it. It would be good if additional background information can be provided.
* Missing title in the reference [36].
questions: Please see the weakness.
limitations: Please see the weakness.
review_title: null

Meta-review: metareview: The paper addresses an important question regarding the trajectories of SGD in high-dimensional settings. The theoretical derivations of the paper builds on top of prior works but nonetheless is sound. Most reviewers agree that the paper advances the knowledge in this area.
confidence: Certain
Decision: Accept