Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence rates of the two first-order methods, named $q$-RGF and $q$-SGF. These are constructed by forward Euler discretizing the $q$-rescaled gradient flow ($q$-RGF) [Wibisono et al., 2016] and $q$-signed GF ($q$-SGF) [Romero-Benosman, 2020], respectively. These gradient flows are shown to converge in finite time in [Romero-Benosman, 2020], under the gradient dominant condition of order $q$. The authors show that their forward Euler discretized versions have linear rates, under an additional Lipschitz smoothness of order $q$. The paper also considers their stochastic variants. Numerical experiments on toy examples and practical example illustrate that the proposed method might have practical advantage over existing methods such as GD and ADAM.
main_review: **Strength**
- Fundamental methods: This paper studies two (discrete) fundamental methods, which are gradient methods (with or without sign function) with gradient norm dependent step sizes. Many practical gradient methods in deep learning use such step sizes, so studying their fundamental versions are of interest.
- Experiments: Although only one very practical problem is considered, the experiments illustrate that the proposed methods outperform ADAM and Nesterov's accelerated GD.

**Weakness**
- Motivation: Although this work has merit, it is not well motivated. For example, it would have been nice if the authors provided references to the sentence "Concerning that many ~" in page 1. In specific, I have hoped to see some reasoning why we need to study such two specific gradient flows (and their discretization) over the standard gradient flow in Introduction and Related work sections. In addition, why is the gradient dominant condition of interest, over existing standard conditions, especially considering the authors' interest in applying their method to deep learning?
- Finite-time convergence in continuous time translates to acceleration in discretization: The authors mention that many existing related analyses focus on matching convergence rates from the continuous-time domain into the discrete-time domain. Instead, this paper states that (e.g., in page 8) finite-time convergence in continuous time translates to some acceleration in the associated discretized algorithm. I think matching the convergence rates as other papers did would have better convinced the readers on the theoretical justification of acceleration (in early iterations).
- Gradient dominant condition: There is no comparison to convergence rates of other methods under the same condition. Since the authors claim that their methods are faster than other methods in experiment, it would be nice to have some theoretical comparison. 
- Experiment: Intuition behind the practical acceleration of the proposed methods is barely given. Therefore, I am not optimistic that this trend will appear in other experiments. What does the tuned parameter $q$ mean in the experiment on SVHN dataset? 

**Minor**
- Page 3 below (6b): $F_d: Z_+ \times R^m \to R^m$
- Page 3 Examples 1 and 2: A feedback-based step size, component-wise step size and a backward Euler discretization are not used in the paper hereafter, so I think it is better to make this page concise, and state something more related to the main part.
- Page 6: Do the rates of the discretized methods match those of their continuous ones?
- Page 6: Could you explain further about the choice of $\ell_\infty$-norm, rather than $\ell_2$?
- Page 7 Example 1: For the case $q>1$ in example 1, it does not seem Lipschitz smooth given in Assumption 2. For an "academic" example, I think one would hope to see an example satisfying all of the considered conditions.
- Page 8 Figure 1 left: How did you define the optimality gap in the figure? (e.g., after certain number of iterations?)
- Page 9: How about the vanilla GD or the heavy-ball momentum? Using acronym GD (and SGD) for Nesterov's method seems odd.
- Page 9: How did you get 40 min here?
- Page 9 Figure 3: Why do we have drastic drops in the right figure?
summary_of_the_review: While the theoretical results seem new, they are not well motivated (at least practically), and the paper does not seem to provide sufficient justification of the success of the proposed methods in practical applications.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Motivated from the finite-time convergence of two first-order gradient flows, the submitted paper studied the convergence properties of discrete iteration schemes in both deterministic and stochastic settings. Convergence results are proved for these algorithms, and numerical experiments are provided to demonstrate the performance of the schemes. 
main_review: The submitted paper studies the convergence properties of discretized gradient flows, and provides some convergence results which is the main strength of the paper. To me, there are few points which are not clear
1. In Theorem 2, we have $k^\star = \frac{(f(x_0)-f(x^\star))^{(1-\alpha)}}{\tilde{c}(1-\alpha) \eta}$. Now denote $C = \frac{(f(x_0)-f(x^\star))^{(1-\alpha)}}{\tilde{c}(1-\alpha)}$ which is a constant. Suppose $\epsilon$ is some chosen accuracy and $\eta$ is some sufficiently small time step-size. The condition $|t-k\eta|<\epsilon$ means that $$ \frac{t-\epsilon}{\eta} < k < \frac{t+\epsilon}{\eta}  . $$ For $t$ large enough, it can happen that $$ t - \epsilon > C $$ where $C$ is defined above. Corresponding we have $k > k^\star$. Then Equation 16 would fail since $k \leq k^\star$? I'm wondering if I missed something here?
2. The results for stochastic gradient descent are $\epsilon$-dependent, such as the batch size which is $O(\frac{1}{\epsilon})$ for stochastic $q$-RGF and $q$ closed to $2$. So in the numerical experiments, what are the choices of $\epsilon$? And the result is not very practical in the sense that if sufficiently high accuracy solution is desired, then the batch size would be too large such that it will be close or equal to the full gradient descent. As a result, is it possible to establish result for accuracy independent batch size or for the vanishing step-size?

Also I have two side questions
1. Since the discrete algorithms fails the finite-time convergence, is it possible to have other type of discretization which can provide finite convergence? Or at least numerically.
2. Suppose we consider second-order dynamic systems, can the finite-time convergence still hold in this case? 


summary_of_the_review: Motivated from continuous dynamical system, the authors studied the convergence behaviors of discrete first-order methods. However, there is a gap between the continuous and discrete setting, and the obtained results need to be clarified. 


edit: the responses look good to me, and i raised my score by 1.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the author study two first-order optimization methods, which are the Euler discretizations of rescaled gradient flow and signed gradient flow. They prove the convergence rates for both methods under both deterministic and stochastic settings. 
main_review: Strength: 
1. Convergence behavior of the discretization of gradient flows is an important question in optimization. 
2. The paper is well written and very good to follow.
3. The methodology is validated via empirical experiments and theoretical analysis.

Weakness:
1. The convergence rate of Euler discretizations of rescaled gradient flow and signed gradient flow under the deterministic setting exists in the literature. (The author do point out this.) The only difference is the generalization of the Lipschitz smoothness. The author should illustrate why such generalization is important and what is the main technical difficulty in extending the existing theoretical result. 
2. Under the stochastic setting, the result is not convincing in the sense that although the epsilon can be arbitrary small, the batch size will go to infinity, which is not good especially under the stochastic setting. 
summary_of_the_review: I found the manuscript to be clearly written and technically sound. I am, rather unfortunately, inclined to recommend that the manuscript be rejected on the grounds that the work may not have sufficient merit / novelty to warrant publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the analysis of two discrete time schemes derived from gradient flows named q-RGF and q-SGF. The topic fits more generally into continuous time perspectives for optimization and the relations between ODE theory and optimization. This is an interesting direction with many interesting promises.
main_review: My comments are as follows.

1) The paper starts well but in Eq. (6a)-(6b), when authors describe the state-space form of the optimization algorithms, I think there might be a typo in (6b): Is it supposed to be $G(X_{k+1})$? Thiis notation is confusing as it is not made clear what $x_k$ and $X_k$ actually denote.

2) The following examples are meant to be helpful but they all consider the case $G(x) = x$. It is really unclear what (6a)-(6b) describes. Authors should put an example with a clear case where $G$ is not identity (e.g. a proximal-gradient scheme?)

I also don’t understand the introduction of this notation, as it looks like it’s not used elsewhere in the paper and not central.

3) The authors then introduce the fundamental assumption of the cost functions considered, that is, gradient dominance of order $p$. I strongly suggest authors to motivate this assumption beyond strong convexity. What kind of non-convex functions does satisfy this inequality? Is it similar to, e.g., weak-convexity or dissipativity conditions usually used in non-convex optimization literature?

4) The toy examples in the paper are helpful but their connection to theory is not exploited: In particular, in this section, I’d strongly suggest authors to verify their assumptions for these toy examples precisely by working out relevant constants. Then, plotting the errors vs. actual error bound computations would really be insightful about the meaning of the results derived in this paper.
summary_of_the_review: These results can be potentially useful for advances in this field. I found the paper clear and insightful in general.
review_title: null

Meta-review: This paper starts from the observation that a certain class of rescaled gradient flows - referred to in the paper as RGF and SGF - converge to a solution in finite time (Wibisono et al., 2016; Romero and Benosman, 2020). As a result, it is plausible to ask whether the Euler discretizations of these flows - viewed now as optimization algorithms - enjoy superior convergence properties or not. The authors' main results establish a linear convergence rate under a certain gradient dominance condition, as well as linear convergence to an $\epsilon$-neighborhood of a solution if the algorithms are run with minibatch gradients of size $O(1/\epsilon^\rho)$ for some positive exponent $\rho>0$.

The reviewers raised several concerns regarding the motivation of the authors' work and the comparison of the rates they obtain to other related papers in the literature. The reviewers that raised these concerns were not convinced by the authors' rebuttal and maintained their original assessment during the discussion phase.

From my own reading of the paper, I was perplexed by the fact that the authors did not compare the rates they obtained to existing results in the context of KL optimization, such as the cited paper by Attouch and Bolte and many follow-up works in the area. Also, in the stochastic part, while the authors argue that "utilizing batches with size dependent on $1/\epsilon$ is absolutely reasonable and usual, in both theory and practice", it should be noted that a high accuracy requirement (small $\epsilon$) could lead to completely unreasonable batch sizes (effectively exceeding the size of the dataset, especially when $\psi$ is small). Thus, while it is possible to achieve convergence to arbitrarily high accuracy with a sufficiently small step-size for a _fixed_ batch size, the rate of this convergence cannot be linear overall - in contrast to the way that the authors frame their result.

In view of the above, I concur that the paper does not clear the bar for ICLR, so I am recommending rejection at this stage (but I would encourage the authors to resubmit a suitably revised version of their paper at the next opportunity).
Decision: Reject