Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a new way of developing the convergence analysis of gradient descent (GD) and stochastic gradient descent (SGD) by leveraging the convergence of the gradient flow (GF). The main tool of the paper is to construct a Lyapunov potential which implies a convergence rate of the GF, formalized as a general converse Lyapunov like theorem. With additional self-bounding regularity conditions, the convergence of GF is sufficient to imply the convergence of GD and SGD. This framework is so general that it provides a unified analysis of GD and SGD that match the best convergence rate of convex functions or PL/KL functions, but also for phase retrieval and matrix square root problems.
strengths_and_weaknesses: The paper is well-written, highlights their contribution clearly, provides lots of interpretations and simple examples of their general framework. The framework and the way to show convergence of GD and SGD are creative. There is a lot of conceptual value to the community that allows to develop new convergence analysis of GD and SGD in more complex models (e.g. neural networks). I am not familiar with the optimization theories of GF. The mathematical derivation of convergence seems solid.

My evaluation for the work is mostly positive. It may be better for the authors to write a paragraph how this work can be applied in the future. For instance, how SGD convergence analysis for the neural networks can be established under this framework ? More generally, can this framework be extended to other optimization methods, such as second-order methods and other variants of SGD (e.g. Adam, stochastic variance reduced gradient) ?
questions: Typos:

Duplicate references: [21] & [22]; [41] & [42]
limitations: The authors have adequately addressed the limitations of their work.
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: This work presents a novel framework for analyzing SGD via Lyapunov analyses of continuous-time gradient flow. The authors first establish that, loosely speaking, a Lyapunov function must exist if gradient flow converges. Then the authors show convergence of SGD using the same Lyapunov function. Some interesting and illustrative examples are provided, but there are no experimental results, which makes this a theory paper.
strengths_and_weaknesses: The level of abstraction regarding Lyapunov functions is not something I have seen in the optimization and SGD literature, and the first result establishing the necessity and sufficiency of Lyapunov functions is interesting, at least to me. However, it is unclear to me what benefit this abstraction brings. The rates established for SGD are not better than any of the prior rates, and, in fact, many of the state-of-the-art rates are established not with the plain SGD but with some minor variation, such as certain varying stepsizes, appropriate batch sizes, or some non-uniform averaging schemes. Such variations probably can be considered under this framework, but this has not been done in this paper yet.

The control-theoretic framework feels like an interesting framework to me, but there's no key result that validates the strength of this viewpoint. The insistence on considering Lyapunov functions of gradient flow may be a key insight that future research on SGD will benefit from, but I don't think this work has sufficiently demonstrated the usefulness of this framework beyond its novelty.
questions: What is the key main result that demonstrates the effectiveness of this Lyapunov analysis framework?
limitations: The justification of the usefulness of the Lyapunov analysis framework is not sufficiently convincing, since many researchers in the field are already aware that many (if not all) discrete analyses have nice continuous-time counterparts with gradient flow or SDEs.
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 present paper show the following contributions:
- They provide an equivalence between satisfying certain convergence rates and geometric conditions
- They apply their framework to gradient descent and stochastic gradient descent, requiring  more assumptions on the function to be optimised to derive convergence rates.
- They apply their overall framework to matrix square root and phase retrieval where rates of convergence for the gradient flow have been shown in the literature.
strengths_and_weaknesses: ### **Strengths**

- The paper appears to be original, introduce a very nice idea from the ODE's literature with converse Lyapunov theorems (ref 25). The link with gradient descent and stochastic gradient descent is nicely introduced and seems to enable direct analysis from rates of convergence for discrete analysis.
- The papers show a large diversity of results, which is rare in nowadays paper in conference. 
- The authors really try to apply their machinery to concrete and hard problems in the last section.
- The hypothesis on the stochastic gradient descent (Assumption 3) is a nice and covers a lot of cases.

### **Weaknesses**

- The paper is overall hard to follow: the progression is okay and technical contributions are understandable but it is hard to understand where the authors want to bring us. As an example of this, I think that the paper lacks some comments in the fifth section where they apply their method: there is absolutely no discussion on knowing whether the rates are tight, whether they are new (for gradient and stochastic gradient descent). Another striking example is the subsection 5.3 where Lemma 4 seems to nicely improve on recent Chatterjee condition without application or explication on this result (even the authors write: "*With a wider choice of g and r we can extend these to more general models (eg. neural networks with milder assumptions on the activation function)*". 
- Adding to the previous comment, there is no conclusion, and many times, the paper seems to have been written in a hurry, see some minor flaws below.
- For the result to hold, there is a need to know in advance rates of convergence, which limit the applicability of the results.


### **Minor flaws**

- Why talking of implicit regularisation in the introduction (ligns after 24) ?
- In lign 38, the cited papers do not provide convergence analysis and only focus on implicit regularisation
- lign 87, it is not standard that the estimator is not the final iterate, precise that this is your way to see gradient descent. Same lign 96.
- lign 97, $(w)$ is a weird notation for a process. Prefer $w$ or $(w_t)_{t \geqslant 0}$ 
- lign 108 ,what is the $p$-th derivative ? Isn't it simply the gradient ?
- For all theorem, comment the fact that Admissible rate functions could not exist
- It would be nice to have a commentary on what is $g$ in Corollary 1 

questions: - Theorem 4 shows 1/T or 1/\sqrt{T} rates of convergence for the gradient descent whereas Theorem 6 and 7 show exponential rates if the gradient descent case. I understand some PL inequality seems to be hidden here, but this needs to be precised as these theorems are not an application of the Theorem of the previous section.
- The SGD noise scales like the function value for the phase retrieval example, hence I would expect an exponential rate of convergence for SGD also (Theorem 6). Can the authors comment on this ?
- In terms of the two applications, it would be nice to refer to known rates of convergence for GD and a comparison with what you obtain with your technique.
limitations: I use this paragraph to conclude as I already discussed the limitations on the two previous boxes. My opinion is that it could be a super nice paper: I like the overall idea to go from gradient flow with rates to geometrical implications on the lost and then to (stochastic) gradient descent rates. However, the implication of such results on concrete examples could be more referenced and the writing improved.

For now, I give a borderline accept but I will gladly improve my score if the authors give me some evidence that they can improve the paper in such a short notice.
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: This paper aims at providing conditions for the convergence of GD/SGD schemes when there is a rate of convergence for Gradient Flow on population loss, and this is done by deriving a potential function and checking the geometric property. Also this potential should satisfy certain properties, called self-bounding regularity conditions, in order to give us the desired convergence for GD/SGD methods. Authors verify that this is indeed applicable not only to convex and PL functions, but also to non-convex problems.
strengths_and_weaknesses: As authors mention, using admissible potential functions for getting a convergence rate for GF is studied before. Identifying the one-to-one correspondence between admissible rate and potential functions that satisfy the geometric property in (4) seems interesting. Propositions 1 and 2 also provide simple examples on how admissible rates and potentials exist in easy-to-prove scenarios.
As I read all of the proofs, there are lots of typos and some derivations, which I will mention in below, are not carried out correctly, and I hope after revision they will not be problematic for the main claims to hold. However, overall the main results are clear and easy to read and providing examples like propositions 1,2 and touching on Phase retrieval and matrix square root problems makes this converse Lyapunov strategy interesting for analysis of GD/SGD using the GF convergence rate. I think this paper aims at connecting GF and GD analysis which is currently a hot research topic in optimization.
questions: grammatical and mathematical typos:

line 108 derivative. line 112 extra "in". line 121 shown. line 144 such that. line 215, $F(w(t))\leq\frac{\lVert w_0 \rVert^2}{2t}$. line 226, satisfied. lines 587, 592, it should be $\Phi(w_0)$. line 611, the negative signs in lines 3-4-5 should be removed, as $|r'(z)|=-r'(z)$. line 625, extra "from", also $R(w,t)=F(w)e^{-\lambda t}$. line 630, $\frac{\lVert \nabla F(w) \rVert ^2}{\lambda}$. line 634, 3rd line, missing "=". line 643, it should be $\lVert u \rVert_{3/2}$. line 651, $F(w(T)) - F^*\leq \frac{\Phi(w_0)}{T}\leq \frac{\lVert w_0 \rVert ^2}{2T}$. line 657, "many ensure". line 662, proof. line 700, extra "defined". line 705, $\theta''(z)=\frac{-\rho'(z)}{\rho(z)^2}$. line 712, $u=-\frac{\nabla \Phi(w)}{\rho(\Phi(w))}$. line 732, since "$\theta$" is "monotonic", this implies that "$\Phi(w_{t+1})\leq \Phi(w_t)$". 

in line 752 equation (33), 2nd line is wrong. we don't know if $F(w_t)\leq F(w_0)$. Instead you should use $F(w_t) \leq \zeta(\Phi(w_t)) \leq \zeta(\Phi(w_0))$. However final conclusion of equation (34) is correct.

line 772, $\psi(F(w))$ instead of $\lVert \nabla F(w) \rVert^2$. line 783, $\kappa > 1 $. line 792, 3rd line is duplicate. line 796 and afterward, you should replace $\Phi(w_0)$ with $\theta(\Phi(w_0))$. line 809 $"M="$. line 810, $\text{log}^2$ seems to be $\text{log}^3$. line 819, "note that" and "when".  line 826, "$g$" is missing. 

In line 947, I couldn't derive second inequality. maybe there should be a larger coefficient.

lines 1018 and 1025, $\lVert M \rVert$ instead of M.



Questions:

regarding line 207-8, can you provide such examples, or mention some papers? 

In line 614, $\underset{\epsilon \rightarrow 0}{\text{lim }}  \epsilon ^{-\frac{1}{\epsilon}}$ seems to be infinity, but for your result to hold it should be zero. This also happens in other places like line 181. Please explain. 

My most important question is regarding the exponential rate of GD in theorems 6 and 7. In the proofs you say combining Lemma 1 with Theorem 4 will give the result. However Theorem 4 has a $1/T$ rate and $g(z)=z$. Please carefully explain it and also update the paper to contain more details of this proof.

In line 722, please explain (if needed by writing equation) that why 27 is valid if 26 is violated. I think there must be some $"g"$ and $"\psi"$ missing in (27), by looking at line 741.

In Theorem (4) you mention $O(\frac{1}{\sqrt{T}})$ rate of convergence, but in line 741, I can see $1/T$ as well as a constant term. Please explain. it seems that line 741 and 761 only differ by a constant and both of them are $O(1/T)$ except that 741 is suboptimal assuming g is zero at optimum. 

In line 798, I couldn't use Markov to get (39). I'd like to see one line of proof.

line 804, where do you set $\kappa$ in the paper?

Line 853 there is a serious issue with derivation of line 5, because we don't know $\theta(\Phi(w_{t+1})) - \theta(\Phi(w_t))\geq 0$, hence equation (50) may not be true. Please revise/explain the proof.

In proof of Lemma 11 needs serious revision. The derivation in lines 890 is incorrect and you should write $\overset{-}{R}(w(s),t)=R(w(s),\sigma(h(w(s)))t)\leq R(w,\sigma(h(w(s)))t +s) \leq R(w,\sigma(h(w(s)))t + \sigma(h(w(s)))s)\leq=R(w,\sigma(h(w(s))) (t+s) )\leq R(w, h(w(s)) (t+s) )= \overset{-}{R}(w,s+t)$.
More importantly, I see an inconsistency in using $\sigma(h(w))$ and $h(w)$. For example you define $\overset{-}{R}(w,t)=R(w,\sigma(h(w))t)$, but after line 892 suddenly there is no sign of $\sigma$ in derivations of $\nabla \Phi_g(w)$ and $\nabla ^2 \Phi_g(w)$. As you use $\sigma$ in lines 306 and 336, I think $\sigma$ is kinda absored in $h$ but I can't wrap my head around this issue. in line 895 equation (51) $\Phi_g(w)$ uses $h(w)$ instead of $\sigma(h(w))$. Also in line 911 the second term is used incorrectly and should be modified.

In line 1028, how do you calculate the bound on hessian? I assume hessian would be complicated.

in line 1048 line 3, do you assume $\text{min }F=0$?
 
Suggestion:
I urge you to state the result of Chatterjee more rigorously in the Appendix, and explain (mathematically in appendix) how in the lines 374-378 you can recover his result. I also expected a conclusion part at the end of the paper, but I assume you couldn't fit it.
limitations: As this is a completely theoretic paper, I cannot think of anything related to social impact.
review_title: null

Meta-review: metareview: This paper provides a new way of developing the convergence analysis of gradient descent (GD) and stochastic gradient descent (SGD) by leveraging the convergence of the gradient flow (GF). This framework is very general and provides new insight that future research on SGD will benefit from. All reviewer have positive feedback and I would like to recommend acceptance. 
confidence: Certain
Decision: Accept