Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 

### Summary
This paper studied two continuous time methods called  rescaled-gradient flow and the signed gradient flow and proposed three efficient discretization, namely the forward-Euler, Runge-Kutta and Nesterov discretization. The paper demonstrated the finite-time convergence of the proposed methods under gradient dominance assumption, and use experiments to show that the proposed methods outperform standard stochastic gradient algorithms in many deep learning tasks.

### Comments

The paper is clearly structured; the related work in the dynamical systems and control are well presented; experiments are detailed and rigorous, it is good to see detailed report on hyperparameters in appendix.


While the paper claims that the study is in the context of deep learning, it is unclear to me whether the theoretical analysis is well suited for deep learning models. In particular, the algorithm and main convergence result (Theorem 2) require full gradient. It would be more interesting to show  convergence result for stochastic setting where only mini batch of samples are provided each time. 

In abstract, the paper claims the flows include  non-Lipscthiz or discontinuous system, can the paper give a few examples of such cases? If I understand correctly,  the gradient in example 1 is continuous due to Lipschitz continuity, and the proximal mapping in example 2 is continuous due to nonexpansiveness. 


The main result Theorem 2 seems to be problematic. It claims that after finite number of iteration, the iterates $x_k$ will eventually fall in a small $\epsilon$ neighborhood for some $\epsilon$ error. However, it does not specify how small $\epsilon$ is. By using sufficiently large $\epsilon$, the weak bound is always valid. Can we prove the weak convergence bound (eq. 21) for arbitrarily small  $\epsilon$?

The main convergence property is established on the gradient dominance condition (13), which seems to be relatively strong because it requires isolated saddle points. Can the authors elaborate the intuition of (13) for deep learning models?

In the experiment (Figure 8, appendix) both training loss and testing loss are plotted. However,  it appears that testing loss is much smaller than the training loss. Is it normal or does it have any underfitting issue?

Since the main focus (theory part) is on deterministic setting, to confirm the theoretical finding and  to show the advantage of continuous time methods,  it would be more interesting to compare with Nesterov method or other gradient method for deterministic optimization.  I feel that this work would be more interesting to the field of dynamic control or optimization rather than deep learning.

Typo:
In 4.2.2. 
"Nesterov's Nesterov accelerated gradient descent" should be "Nesterov's  accelerated gradient descent" 
review_title: Review of continuous time methods

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper provides several discretization strategies for three optimization flows. The main contribution comes from the convergence guarantee for the discrete system.
1. The convergence guarantee for continuous flow comes from previous work. Moreover, I understand that the author may wish to present the results as general as possible. However, since all the F is continuous and singleton in the main part (if I do not miss some parts), there is no need to introduce the differential inclusion based discontinuous dynamic system, which causes the appendix to be hard to read. All the auxiliary lemmas and theorems have a simple and intuitive version.
2. Eq. (32) is wrong. The order should be 1/(1-\alpha). Therefore, so do Theorem 2 also has a similar typo. At the end of page 15, "Therefore, Bala Bala...", it should be X \in D\\{x_0} not D\\{0}.
3. In the context of deep neural networks, transferring the convergence guarantee from the continuous optimization flow to the discrete system is quite important. However, this paper does not utilize any detailed information on DNNs; hence it is more like a general optimization paper. Considering there is rich work investigating the discretizations, I can't judge the contribution's significance of this paper.
4. In the experiment, the format and the resolution of the figures are not consistent.
review_title: This paper provides several discretization strategies for three optimization flows. The main contribution comes from the convergence guarantee for the discrete system.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The submission analyzes convergence behavior of three numerical discretizations (forward Euler, explicit Runge-Kutta, and Nesterov-based) of the q-rescaled gradient flow proposed by Wibisono et al. and a variant (q-signed gradient flow), and performs experiments to demonstrate improved convergence speed.


The paper is written clearly, and its relation with prior work is adequately addressed to the best of my knowledge.
However, I also believe that the paper has a few serious drawbacks, which makes it a stretch to include it in the conference in the current form. In general, I feel the submission has the potential in becoming a good paper after some non-trivial updates. 


The first issue is with regards to the motivation. After reading the paper, I don’t fully see the benefit that finite-time continuous time convergence provides. What’s more is that the submission does not well motivate the reason to use the particular flows and the techniques of analyses which rely on differential inclusion. 


The second issue I’d like to raise is perhaps more important and really is the deal breaker in my opinion. It seems the only new theoretical contribution (i.e. theorem 2) does not provide a converging bound with which a convergence rate can be derived. This is demonstrated by the fact that the authors acknowledge in the theorem that epsilon is chosen, i.e. it cannot be arbitrary. It is also unclear how small a step size eta is required for this bound to hold. Skimming the proof in the appendix, it is clear that the analysis is based on bounding the error between the cont. time solution and the optimum and the error between the cont. time solution and its discrete counterpart. However, it is unclear how the discretization error varies as the step size and number of iterations vary. 


The theorem also does not provide any basis to compare the three discretizations, since the same bound is provided, and the same set of assumptions is used for all discretization considered. An ideal analysis would likely distinguish different discretizations based on different assumptions (most likely smoothness of the loss function a la “Direct Runge-Kutta Discretization Achieves Acceleration”), and provide some meaningful non-asymptotic analysis of the magnitude of errors based on characteristics of the discretization. 


The experiments section seems well-planned in general. Though the wall-time experiments could be inflating the gains vs Adam, since the first-order and second-order ema moments can be accumulated in parallel on a GPU (and this doesn’t require much effort to implement with standard frameworks, since most dispatches are async.). 


Minor typos:
bottom of pg 5: “The analysis summarized in Theorem 2 is based on tools form hybrid control…” form -> from 
middle of pg 6: “to achieve finite-time convergence in conitnuous-time” conitnuous-time -> continuous time

review_title: Official Blind Review #1

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: This paper studies inertial algorithms motivated from discretization of continuous-time systems. The focus of this paper is on rescaled gradient flows and studies three different numerical discretization schemes. The performance of the thus obtained schemes is tested on standard test instances in deep learning. 

Evaluation: 
The paper treats a very important and interesting topic. I very much like the idea of using rescaled gradient flows for optimization problems. However, the scheme described is conceptual in nature as many unexplained hyper parameters play a key role in the optimization and no indication of how to choose these hyper parameters is given. Furthermore, I am missing a discussion with a comparison between the described method and the other first-order methods under the stated gradient-dominance condition. Furthermore, the writing is partly a bit imprecise and I am not quite sure to fully understand the main arguments used in the proof of Theorem 2. If the authors are able to explain this a bit better, then I would be in principle willing to increase my evaluation of this paper. 


Pros: 
+ The analysis of numerical discretization techniques of rescaled gradient flows is a topic that received a lot of attention and definitely is an important subject. 
+ A complexity estimate of the numerical schemes is given. 
+ Numerical results 
+ Detailed technical details are provided in the appendix. 

Cons: 
- The meaning of Eqs. (6a),(6b) is unclear to me. The map $G$ seems to be not really playing any role in the Examples 1-3. 
- The gradient dominance condition reduces in the case $p=2$ to the well-known Polyak-Lojasiewicz condition. Polyak proved already in 1963 that simple GD features linear convergence under this condition. Attouch-Bolte (2009) generalized this to significantly. These connections are not mentioned at all but are central to the approach here. 
- I don't understand why the algorithms stops once and $\epsilon$-neighborhood of the solution is reached. Is this a stopping condition in the numerical approach? If so, it must be stated explicitly. Also, do you really mean $\Delta f(x^{*})=0$ for the equilibrium condition on p. 6? 
- I don't understand why the connection between the numerical scheme and hybrid systems has to be made to prove that approximation property. There is a solid theory of stochastic approximation of set-valued dynamical systems due to Benaim, Hofbauer and Sorin (SIAM J. CONTROL OPTIM. 2005, Vol. 44, No. 1, pp. 328–348) where the needed tubular estimates are provided in quite some generality using the theory of perturbed solutions to differential inclusions. I belief that it is more natural to relate the approximation results to these techniques. However, I might miss this point as the authors write on p. 16 that they consider the dynamics as a hybrid system with a possible jump at the optimum. In my opinion this is an imprecise formulation and should be reconsidered. 
- The methods are not really algorithms but rather conceptual computational schemes. 
- I don’t understand the statement in Theorem 2 why the bound is a „weak convergence statement“. Can you explain this terminology?
- There is no discussion on the efficiency of the method although gradient dominated functions have been studied in the literature to quite some extend. 

review_title: Report

Meta-review: The paper proposes three discretization schemes for two first-order optimization flows, and proves the "convergence" to the minimizers of the problem that the optimization flows approach. The methods are tested on the DNN training problem and show comparable performance.

Pros:
1. The problem being studied, the discretization of optimization flows, is of interest to the community.
2. "Convergence" guarantee is provided.

Cons:
1. The theoretical analysis is somewhat preliminary, as the authors have admitted. There is a prescribed \epsilon in the approximation error (23) that prevents the right hand side of (23) from approaching zero. The parameter \eta, depending on the chosen accuracy \epsilon, should be provided so that a user can implement the discretization schemes if s/he is interested. Moreover, by specifying \eta, it may be possible to compare the numbers of iterations to approach an \epsilon-solution between the proposed discretization schemes and other optimization methods for solving the original optimization problem. By doing this, the motivation issue from Reviewer #1 (and the AC) can be resolved. Purely discretizing an optimization flow is of less interest to the machine learning community.
2. Although the comparison on academic problem is obviously advantageous, the comparison on DNN training is only comparable or marginally better. 

The author responses resolved part of the challenges from the reviewers, but the key issues remained (as communicated in confidential comments). Since the final average score is below threshold, the AC decided to reject the paper.
Decision: Reject