Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: - This paper applies the numerical analysis of the ODE initial value problem (the fundamental theorem, Thm 2) to explain the relation between continuous gradient flow and discrete gradient descent in deep learning.
- The step size depends on the minimal eigenvalue of the Hessian, and Section 4 gives a lower bound of the minimal eigenvalue for linear networks, then try to extend it to a nonlinear setting.
- For deep linear networks, Section 5 proves a convergence result for the continuous gradient flow, then applies the fundamental theorem to translate it to the discrete gradient descent directly.
main_review: Originality: It is a novel idea to apply the classical numerical analysis results to deep learning. The authors show some preliminary results in this approach. E.g., the fundamental theorem requires the minimal eigenvalue of the Hessian, which can be estimated for linear networks; the authors also illustrate how to translate a gradient flow result to gradient descent in deep linear networks.

Quality: This is a theoretical paper. The theorems and propositions are supported by mathematical proofs, and also illustrated by numerical experiments. Most of the theoretical results focus on the linear networks, and the extension to nonlinearities are discussed.

Clarity: The statements of the theorems and propositions are clear for me.

Significance: It is a good trial to revisit the classical numerical analysis in deep learning. The applications shown here are most in linear cases, and the convergence rate in Section 5 is not optimal since it is exponential w.r.t. the depth $n$. Nevertheless, I think it is still a good starting point.

**UPDATE**

Thanks to the authors for the response, and I have also read others' reviews.

I think the main contribution of this paper is to introduce the numerical analysis theorem to deep learning, and I think it is valuable to provide the fast tool to translate the continuous analysis to discrete GD, if one only requires *a* convergence result instead of *the best* convergence rate. Therefore the goal of Section 5 is to illustrate how to apply this tool to linear networks, and it is okay for me that the convergence rate here is not as good as previous literature.

On the other hand, I agree with reviewer x5V9 that the current presentation of the results may not convince the readers that this framework is not less efficient than other proof strategies.
limitations_and_societal_impact: While the linear results are rigorously proved, the extension to the nonlinear cases are more like discussions and illustrations instead of proofs. For the deep linear networks, the convergence rate given by the fundamental theorem is still not optimal, which may be regarded as future work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper answers the question of how well does gradient flow explain the behaviour of gradient descent. They provide a sufficient condition — upper bound on step size — which when satisified ensures that the tracjectories of graidnet flow and gradient descent track each other. This upper bound is depends upon the minimum eigenvalue of the Hessian along the trajectory gradient flow, i.e., if the minimum eigenvalue is less large (less -ve or more +ve) better the match. 

For FCNs and CNNs they show under certain assumptions, the minimum eigenvalue of the hessian along the trajectory of gradient flow doesn't goto -\infty and is even non-negative around global minima, and therefore can be approximated by gradient descent with the appropriate step size. 

For gradient descent, the authors show that a neural network of a fixed size and near zero initialization convergences, where the number of iterates has an exponential dependence $n$ on the depth of the network.
main_review: The paper is very well written and motivated. The authors do not make many strong assumptions during their analysis. 

Further, the proofs are backed with clear and well motivated proof sketches. Although I did go through most of the proof sketches, I did not go through all the proofs in detail. The proofs that I did go through looked correct to me. 

Few questions/comments for the authors

- The convergence for gradient descent is only considered for networks with linear activation. While the number of iterates in this case is already exponential in $n$, can the authors comment on how the bound would change when we consider the nonlinear activation discussed.?
- Empirically, it would be interesting to see how the minimum eigenvalue behaves throughout a gradient descent run, and if it indeed matches the claims made in section 4.
limitations_and_societal_impact: Negative societal impact is not applicable here. The future work discussed in this paper is to quantify/study the discrepancy between gradient descent with large step sizes.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: For fully connected neural networks with (i) linear activations (ii) homogeneous activations, the authors provide lower bounds on the minimal eigenvalue of training loss's hessian along the trajectory of gradient flow. In the case of linear activations, they leverage this result in order to give a convergence guarantee for gradient descent.
main_review: Trying to translate continuous convergence results into (relevant) discrete ones by using generic discretisation results is in my opinion a challenging and interesting task which the authors want to address. However I have several major problems concerning the paper / results.

Overall the paper is extremely dense and very hard to read. I suspect the use of many \vspaces{-1} which does make the reading very pleasing.  Furthermore the related work is postponed to the appendix, it is therefore very hard for a non-expert reader to have any idea of the context in which the paper is built upon. For example the convergence guarantees from
*A Convergence Analysis of Gradient Descent for Deep Linear Networks* (Arora et al.)  or   *Gradient descent optimizes over-parameterized deep ReLU networks* (Zou et al.) are not given nor discussed which is problematic. 
Several lemmas take space and are non-informative: for instance Lemma 3: what are we supposed to deduce from this expression ?  In general the authors make very little effort in order to make the stated results easily understandable: for instance eq (23) for the condition on the step size: what are the relevant quantities ? is the $\ln$ quantity relevant ? why not simply use a $\tilde{O}$ notation and leave the important quantities such as $\tilde{\varepsilon}$. Though these comments rely purely on the "form" and not on the actual mathematical claims, I believe much more effort must be put in order for the results to be understandable by future readers. All the unnecessary and technical constants / lemmas which complicate and slow down the reading without giving any intuition / relevant information should be postponed to the appendix. This would for instance make a lot of space for the related work which is crucial for the overall understanding of the challenges.

Putting aside the "form" their still remain in my opinion some issues concerning the results:
- l226-227: "We conclude that the lower bound on $\lambda_{min}$ starts off slightly negative, and becomes non-negative": I don't understand what you mean. The lower bound you give seems to always be strictly negative. Do you mean that at convergence (which is in practice never stricltly attained) it is equal to $0$ ? If this is the case your sentence is a bit misleading as I first understood that from some point in the training is becomes positive.
- Theorem 4: the result is not at all compared to the results from (Arora et al.) nor (Zou et al.). What is the improvement if there is one ?  To me it seems as your result is much weaker, their result holds for a step-size which is independent of $\varepsilon$ whereas yours requires having a step size $O(\sqrt{\varepsilon})$ which basically means having to take step sizes infinitely small in order to converge. 

Overall much more effort must be put into the overall form of the paper (less dense and more digestible) and the main result seems weaker than previous results (which are not even discussed). This is why I give an overall grade of 3. 
limitations_and_societal_impact: Limitations are discussed.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes to use bounds on the difference between gradient descent (GD) and gradient flow (GF) [Thm 3] as a general strategy to convert convergence proofs about GF (which is not an implementable dynamics) into convergence proofs about GD. The authors exemplify this strategy by providing a quantitative convergence guarantee for GD on deep linear neural networks [Thm 4], which is deduced from a convergence guarantee for GF [Prop 5]. The general comparison between GD and GF is classical in numerical analysis, so the main contribution is the analysis of GD on deep linear networks.
main_review: There could be two ways to position this paper, both of which are interesting but suffer from weaknesses in their current form:
(i) putting forth [Thm. 3] as a general strategy to convert GF proofs into GD proofs, or
(ii) proving a guarantee to train a deep linear network with GD

- for (i): there are various ways to translate an optimization bound for GF into a bound for GD. The approach via Thm 3 (ie directly bounding the difference between the two trajectories) is maybe the most natural one, but it might degrade the guarantees.  Indeed, this difference grows in general exponentially in time, a commonly known and unavoidable fact (eg. the two trajectories can diverge at a saddle). The approach usually taken in the literature consists in taking the structure of the proof (eg, a Lojasiewicz inequality, a descent lemma, etc) and "making it work" in discrete time, which is not always much technically harder (in the present paper, bounding m(t) is not that easy either). Overall, if (i) is the goal of this paper, then the authors should convince the reader that using [Thm 3] is not less efficient than other proofs strategies; but the paper does not address this question since other strategies are not mentioned (in appendix A it is only written that discrete proofs are "often far more technical and brittle" but that is not convincing). On the positive side, it is a good contribution to make Thm 3 easily accessible in this community.


- for (ii): unfortunately the arguments that make Prop. 5 (and thus Thm 4) true are not mentioned in the main paper. There is a proof sketch in the appendix but it is not very informative (in particular it does not detail the technical novelty compared to [4], which is needed to evaluate the contribution); also  I could not verify the plausibility of the argument due to its length and lack of detailed proof sketch. This is unfortunate because Prop. 5 Eq. (21) is an interesting result, and in particular I am not aware of a similar result where the alignment coefficient "nu" appears (but I am not aware of all the literature analyzing GD for deep linear networks).

Overall, I find that this paper would benefit from a rewriting either focusing on point (i) or point (ii), and adapting the content accordingly.

Here are minor additional remarks:
- the title of section 4 "optimization of deep neural networks is roughly convex" is vague and misleading.
- it is not clear how to interpret Proposition 2 because the natural "time scale" for a gradient flow is when the norm of the gradient of gradient is 1 (ie stepsize=1/gradient norm). So to compare GD and GF, what matters is how the curvature is small *relative* to the magnitude of the gradient. This important point does not seem to be discussed.
- on Figure 1, it is impossible to see the distance between GF and GD as a function of eta. A potential fix is to plot this distance divided by the distance from initialization (and to not plot the distance from init, which has a different order of magnitude).
- Orvieto and Lucchi, Shadowing Properties of Optimization Algorithms (Neurips 2019) is a relevant reference that should be mentioned.


UPDATE AFTER REBUTTAL:
I have read other reviews and the response from the authors. I thank the authors for the time they have spent replying to my comments. I think that they did not answer the core of my concerns which were about the positioning of the paper ((i) vs (ii)) and the lack clarity that results from this unsatisfying positioning. Reviewer jeQC has similar concerns. I acknowledge that the authors suggest various changes to improve the paper but there is little guarantee that the weaknesses will be fixed in a satisfying way in the next version. In short, if Prop 5 (and its consequence Thm 4) is indeed the main contribution of this work, then it is disappointing that after reading the main paper, the reader has almost no idea of how this result is proved. As a side note, I disagree that when the authors write "our paper introduces an additional tool for proving discrete convergence" because these tools are already known (as acknowledged in the article). For these reasons I maintain my score and encourage the authors to improve the presentation of their interesting result.
limitations_and_societal_impact: - there is no forseeable negative societal impact for this work.
- limitations and suggestions are provided in the main review.
review_title: null

Meta-review: This paper proposes to use gradient flow techniques to analyze the convergence of gradient descent in deep neural networks (restricted to deep linear models). The paper receives diverse reviews at the beginning. One of the main criticisms of this paper is that the presentation is not position in a right pace to make the paper more easier understandable. The main paper contains some detailed "intermedia" results that can unnecessarily complicate the paper, e.g., Lemma 3 does not provide too much information to understand the main results and thus can be moved to the appendix. The presentation issue can be also improved by taking Reviewer x5V9 comment to better position the paper, (i) putting forth [Thm. 3] as a general strategy to convert GF proofs into GD proofs, or (ii) proving a guarantee to train a deep linear network with GD. Another weakness is about the limitation of the proposed technique, which only applies to deep linear neural networks, and the extension to the commonly useful non-linear one is not clear.

Overall, after some detailed conversations with the reviewers, we all agree that the presentation and position of the paper is the main weak point and should be significantly improved. I suggest the authors revise the paper according to the comments of the reviewers for next round submission. As a personal comment, it seems to me that the convergence results requires the stepsize to be bounded from above, which might not be the case in real cases, where some useful model usually take a large stepsize in the optimization. This point might need to be discussed.
Decision: Accept (Spotlight)