Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Review:  This paper refines the the truncation error analysis for discretizing the ODE to obtain accelerated optimization method.  The truncation results include higher order term. Built upon the analysis, the authors propose a new method which is claimed to be more stable for large step size and converges faster. Numerical evidence on matrix completion problem is provided.

 
Pros:

+ The truncation error analysis is new.

+ Overall, the paper is clearly written.


 
Cons:

- The biggest concern that I have with the paper is that it is unclear to me whether the convergence rate is really improved or not. From my understanding, truncation error is different from the convergence rate. What does Theorem 3 really imply here? It seems to me that Theorem 3 does not guarantee that there is an improvement in the convergence rate. A rigorous quantification of the convergence rate needs to be provided to justify the claim "the proposed method converges faster."

 
- Even the claim on "stability" is not well justified. Two simple examples do not provide that much evidence here. 

- This paper does not provide enough details such that the numerical results can be easily reproduced.

 

 
Suggestions for improvements:
 It will significantly strengthen the paper if the authors can provide more theoretical justifications for the claim that their proposed method is faster and more stable. It is also important to clarify the true implications of the truncation error analysis on the algorithm performance. 


 
review_title: Review for "A new accelerated gradient method inspired by continuous-time perspective"

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary:
This paper proposes an accelerated method that has a high-order truncation error $O(h^4)$ to the ordinary differential equation $\ddot{x} + \frac{3}{t}\dot{x} + f(x) = 0$ obtained from Nesterov's accelerated method by (Su et al., 2014), while Nesterov's method has $O(h^3)$ error. This implies that the iterates of the proposed method converge to the trajectory of the differential equation faster than those of Nesterov's method. The two toy numerical experiments illustrate such phenomenon for certain large step size. A matrix completion problem experiment is further included.

strong point:
- Finding a method that has a high-order truncation error seems new and interesting, and numerical experiment suggests that such method performs better.

weak points:
- There is no theoretical guarantee on the convergence (rate) to a solution of an optimization problem.
- The reason why we care "large" step sizes seem insufficient, while Nesterov's method is stable for normal step sizes (e.g., $1/L$).
- It is not clear when the step size is considered large, other than using an exhaustive search. Unlike Nesterov's method, the interval of step sizes that guarantee convergence to a solution is not known for the proposed method.
- Numerical experiments are limited. 

minor comments:
- page 1: $||F(x_n) - F(x^*)|| \to F(x_n) - F(x^*)$
- page 6: what is the Lipschitz constant for this experiment?
- a figure of two-dimensional toy example could help better illustrate the effect of the truncation error.
review_title:  

final_score: rating: 4: Ok but not good enough - rejection
review_content: UPDATE: After reading through all other reviews and responses by the authors, I share the concern that the theoretical justification of the paper is lacking as the connection between the truncation error and the improved algorithm performance is not rigorously proven. Therefore, I have reduced my score.


Summary:


The paper studies the well-known Nesterov's accelerated gradient method and shows the rate of convergence to the solution of an ordinary differential equation recently proposed by [Su et al, 2014]. Motivated by the proof, the authors then derive a new accelerated method with a faster rate of convergence than the original Nesterov's method, which is shown to be more stable than the original Nesterov's method when the step size is large. The method is combined with the proximal operator into a new algorithm referred to as modified FISTA, which is then applied to the matrix completion problem. 


Strengths:

- The paper proves the convergence rate of Nesterov's method to the ODE proposed by [Su et al, 2014]. This proof then motivates them to derive a new faster accelerated method where the truncation error has a higher order of $O(h^4)$ compared to $O(h^3)$ in case of Nesterov's method.
- It is shown in two simple examples that the new method is more stable as it can work with larger step sizes. 
- The method is applied to a matrix completion problem, where it is shown to have faster convergence than standard FISTA and Nesterov's gradient method.


Concerns:

- In Section 2.2., the purpose of Lemma 1 and Lemma 2 is not clear without looking into the proof of Theorem 2 in the supplementary material. The flow of the paper could be improved if an intuition was given of which role they play in the proof of Theorem 2.
- Similarly, to understand the motivation for the derivation of the new accelerated method in Section 3, one is required to look at the proof of the convergence in the supplement. Also here it would help to provide a detailed motivation for the derivations already in Section 3.
- In the numerical results in Figure 1, the gap $|F(x_n) − F(x^*)|$ (y-axis) does not seem to monotonically decrease but jump up and down erratically. Also there are periodic wave-like patterns visible in the plot. Why do we see those patterns?
- The resulting accelerated numerical method is never explicitly written down, only the specific version derived for the matrix completion problems. The paper would be better understandable if the general numerical scheme (accelerated method) was written down in form of an algorithm after Section 3.
- In the end of Section 4, a reference to Algorithm 2 is missing. Moreover, Figure 2 and Figure 3 are never referenced in the text.
- Page 2, after (1.2) -> "achive" -> "achieve"


Conclusion:

The proposed method provides a theoretical contribution to the understanding of Nesterov's accelerated gradient method. Moreover, a novel algorithm is proposed which is shown to have a faster convergence to the underlying ODE. In the paper this is shown only for a matrix completion problem but I feel that this new algorithm could be adopted by the community if further experiments prove its worth. On the other hand, the flow and presentation of the paper could be improved. Overall this is a borderline paper but its merits may outweigh its flaws.

review_title: Review on "A new accelerated gradient method inspired by continuous-time perspective"

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper the authors study a version of accelerated gradient method. Inspired by the ODE analysis of Nesterov accelerated gradient method by Su et.al., the authors propose a different discretization of the ODE by Su et al. The truncation order of this scheme is of a higher order, thus the authors claim that the proposed algorithm is more stable and, therefore,  will converge with larger steps. Unfortunately, I found these statements to be vague. 

Apart from the above-mentioned truncation error, the only evidence we have is some simple $2$-dimensional experiment. I believe it is not sufficient. Second, for a new scheme convergence of iterates $(x_n)$ to a solution and the convergence rate $F(x_n) - F(x_*)$ should be proven explicitly, they do not follow automatically. Ideally, we need both sound theory and good experiments to claim that one method is better than another. I am afraid both are missing in this work. The same was done for the modified version of FISTA, where the authors add regularizer without any discussion about convergence of the scheme.

Based on this, I cannot recommend this paper.


I suggest the authors to address the above-mentioned concerns in their revision. I think it would be great if one can show directly the connection between the discretization truncation error and better algorithm performance. Note that, however, already Nesterov's methods have optimal performance. Probably, a significant experimental evidence will help here. 
review_title: Review on "A new accelerated gradient method inspired by continuous-time perspective"

Meta-review: The paper studies a high-order discretization of the ODE corresponding to Nesterov's accelerated method, as introduced by Su-Boyd-Candes. The main claim of the paper is that the more complex discretization scheme leads to a method that is more stable and faster. However, the theoretical claims do not seem sufficiently supported, and the experimental results are insufficient to judge the usefulness of the proposed approach. Thus, the reviews could not recommend acceptance, and I concur. The authors are advised to revise the paper to provide more theoretical and experimental evidence for usefulness/competitiveness of the proposed approach, and resubmit to a different venue. 
Decision: Reject