Venue: NeurIPS 2022 Conference

Reviews:

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: This paper studies the mixing time of scale invariant models whose parameters are governed by a stochastic differential equation that approximates SGD + weight decay. Under certain regularity assumptions, the paper shows convergence of parameters to a unique distribution with a rate
 $$ \Theta( \frac{T+ln( \lambda/\eta) }{ \eta \lambda}) $$
strengths_and_weaknesses: Under the setting of scale invariant models whose parameters are governed by a SDE approximation of SGD + WD, the paper proves the direction of SGD iterates converge in distribution to a solution of an SDE. The main technical strategy is to employ 1) time rescaling 2) scaling factor that closely mimics the normalization factor for the parameters.

As in  Z. Li (2021), time rescaling is used to ensure that the main workhorse (Katzenberger theorem) can be applied. Essentially, by rescaling time by $$ O(t/\eta^2) $$, the negative gradient loss becomes the dominant term in the SDE (for small learning rate eta) which results in the parameters being close to manifold \Gamma. 

Furthermore, the paper shows a cool corollary that shows that scale-invariant models with no weight decay converge exponentially slower. 


Weaknesses:
The main weaknesses are the strong technical assumptions (e.g. constant noise covariance trace, asymptotic results, smoothness assumptions) but understandable given the difficulty of the problem. 

questions: 
If the trace of the noise covariance matrix is upper bounded by a constant, could we still have similar results?

Although the paper critically rely on scale invariance, would we expect any similar theorems if the model had homogeneity degree L > 0? 

limitations: Yes
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 main contributions of the paper are 1) providing a characterizing SDE limiting the SGD+WD by using a time-rescaling technique so that the results by Katzenberger are applicable 2) showing that SGD without WD for stochastic scale invariant loss has the same limiting dynamics as SGD+WD, but is exponentially slowed down 3) under the assumption of all minimizers forming a compact manifold and noise being non-degenerate in the tangent space of the manifold, the authors show that from any initialization, the limiting diffusion process converges to a unique stationary distribution 4) lastly, the authors conduct experiments to empirically show that these results hold.
strengths_and_weaknesses: Strengths:
The authors are able to show the limiting dynamics for SGD+WD and devise a novel time rescaling scheme to make the results of [1] applicable as they claim that the results of [2] does not hold since there is no true minimizer in the usual sense.

Weaknesses:
It seems that the time rescaling approach is the only notable contribution of the paper. The derivation of the SDE and other results seem to follow from [2]. While there seem to be novelties, the framework to analyze these dynamics have been provided by [2] so on that ground the contribution seems to be marginal.

[1] G. S. Katzenberger. Solutions of a stochastic differential equation forced onto a manifold by a large drift. The Annals of Probability, pages 1587–1628, 1991.
[2] Z. Li, T. Wang, and S. Arora. What happens after sgd reaches zero loss?–a mathematical framework. arXiv preprint arXiv:2110.06914, 2021.


questions: 1) What are the implications of this paper for the training of ML/DL models?

limitations: Mentioned in weaknesses.
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 provided the dynamic convergence of SGD combined with the popular weight-decay technique (SGD-WD) for scaled-invariant loss functions (e.g., neural networks with normalization). Specifically, 1) the authors showed the iterates of SGD converge in distribution to some random variable in $\mathcal{O}\left(\frac{1}{\eta \lambda}\ln \left( \frac{2\lambda}{\eta}(e^{2T}-1) +1\right)\right)$ steps, where $\eta$ is step-size, $\lambda$ is the weight-decay parameter, and $T$ is the budget of the iterations. 2) In the regime of $\eta = \mathcal{O}(1/\lambda)$ when $(\eta, \lambda \rightarrow 0)$, the authors showed that SGD without WD has the same limiting diffusion as SGD with WD but its convergence is slower. 3) Under the assumptions on the manifold and the noise covariance, the authors partially proved the faster equilibrium conjecture of [26].
strengths_and_weaknesses: In general, the paper is clear and well-written. As I know, the interplay of normalization, gradient noise, and weight decay of SGD focused in this paper is a very important and interesting problem. The study of their interplay is beyond the optimization theory. The main contribution is that the authors provided the limiting dynamics convergence of SGD with weight decay and gave empirical evidence to verify their results.  However, I am not an expert in the dynamic theory of SDE. I am afraid that I can not give a fair assessment of the theoretical parts. But I checked the numerical results carefully and gave my concerns.

**About the experiments on the toy example:**
- In line 262, Equality (24) has not been mentioned in the main content. The authors may use (10) instead.  The same problem appears in line 290.
- in line 267, the authors said that as long as no $z_i$ is in the same direction with $x^{\ast}$, $\cdots$, then Assumption 6.4 holds. My question is how to ensure that no $z_i$ is in the same direction with $x^{\ast}$. In general, it is difficult to gain knowledge about $x^{\ast}$. 
**The results on CIFAR10:**
- From Figure 1(a), the values of test accuracy and training accuracy change a lot and the algorithm is unstable. I am afraid it is hard to say that the algorithm has converged around 100 epochs. I guess because the initial step-size $\eta = 0.8$ is too large. I am curious how do you select the initial step size? Are you based on the best performance of the algorithm?
- As I know, a lot of papers studied that decaying the step size improves the performance. I think the interesting result is that the authors claimed that they can use the time scaling in (24) as an upper bound to decide the proper time of LR decay. Have you used this time scaling (24) to decide when to drop the step size in your experiments? I did not see that the selection of 100 epochs is based on their theory.  
- Recently, there are some studies about step-decay step size, which is very efficient in practice. This step size keeps a constant at first and then drops by a constant factor after some iterations. For example, in [1], the authors analyzed this step-decay step size with the knowledge of the total number of iterations $T$. And they drop the step size every the same time period. I think the interesting thing is that the authors can use this theory of time scaling (24) to drop the step size adaptively. The authors have claimed this point but I am not very sure if the formula of (24) can be used in practice and achieve good performance in deep neural networks. I think more experiments are needed if the authors verify this claim.

[1] Wang, Xiaoyu, Sindri Magnússon, and Mikael Johansson. "On the convergence of step decay step-size for stochastic optimization." Advances in Neural Information Processing Systems 34 (2021): 14226-14238.

questions: The questions are addressed above. 
limitations: Yes, they have mentioned their limitations.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This papers theoretically proves the fast equilibrium conjecture that SGD for scale invariant loss mixes in  O(1/\lambda eta) steps by con sidering a new time rescaling limiting SDE. The limiting SDE of SGD without WD mixes much slower than SGD with WD justifies the benefit of weight decay for generalization performance.  The paper also provide some empirical results showing that the fast mixing obtains in asymptotic analysis does appear in pratical setting. 

strengths_and_weaknesses: Strengths:
Overall, this is an excellent paper that provides important theoretical results in understanding the behavior of SGD in training deep neural networks. More specifically,
Originality: The fast equilibrium conjecture was proposed to explains the interesting generalization performance as mentioned in line 33. As the name suggested, this conjecture has not been proved before. Therefore, the proof in this paper is original. Moreover, the new time rescaling SDE has never been studied in the existing literature, which is totally new to my best knowledge.
Quality: All the results in this paper is clearly stated and justified. I briefly checked the proof and it looks sound to me. 
Clarity: A well written paper with main results highlighted. 
Significance: The proof of this conjecture  provide us a reliable tool to understand SGD, which is theoretically significant. 

Weakness: 
1. It would be better to provide some intuitive explanations of the assumption made to prove the main result. Can these assumptions be satisfied in the realized case? 
2. Beyond the proof of the conjecture, it would be more interesting to see what this mixing property can lead to some new conclusions. (Though I agree the content is already enough for one paper. )
3. Section 5.2 provide some discretization analysis. More work should be done on this, e.g., the discretization error. 
4. Please correct typos in the paper, e.g., line 27 affect -> effect.




questions: As stated in weakness. 
limitations: The major two limitations of the current results is:
1. The technical assumptions may not be satisfied.
2. The asymptotic approximation does not necessarily fully characterize SGD.

However, as I have stated in Strengths and Weakness, the current results are already enough for a good NeurIPS paper.
review_title: null

Meta-review: metareview: This paper continues a line of works studying SGD via a similar SDE, this time employing a variety of tools not used before, for instance time-rescaling and normalization layers.  The reviewers on one hand were concerned at times that this was incremental, but also uncovered a variety of interesting contributions.  As such, I feel this paper is a clear accept, and am excited to see it in the conference.  That said, the discussions between reviewers and authors were quite detailed and I feel the authors could greatly strengthen their presentation by carefully adjusting for them, making their intended message more clear for future readers.
confidence: Certain
Decision: Accept