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: Building on a series of work that explored alternative assumptions to smoothness and strong-convexity, that still lead to linear convergence of gradient descent but hold more generally, the submission presents an analysis of first order methods on a pair of such conditions; the restricted secant inequality lower bound and smoothness towards the optimum as the upper error bound. The results show that the worst-case convergence of gradient descent on the class of functions satisfying those assumptions is optimal, by providing a matching lower bound for first-order methods. The construction of the lower-bound deviates from the typical construction of quadratic functions using in smooth, convex optimization and uses that the restrictions imposed by the conditions are weaker than smoothness and strong-convexity to hide local deviations.
strengths_and_weaknesses: To my knowledge, the results presented are new and the proof technique used to obtain the lower bound is technically interesting. The overall presentation of the technical results are reasonably clear. My main concern is on the clarity of the motivations, which I expand on in the next section. Regarding significance, althought not explicitly connected to this line of research in the submission, the results are interesting for the study of the possibility of acceleration under looser conditions than smooth/strong-convex which have attracted attention for applications in ML and explaining the effectiveness of momentum-based methods. This study shows the limitations of some relaxations of smoothness and strong-convexity, showing that acceleration beyond gradient descent is not provable without additional structure.
questions: The introduction relies heavily on the work of Guille-Escuret et al. ([12] in the manuscript) for the motivation of the investigation of the limits of the conditions studied. Motivations specific to the current submission are somewhat missing, and the conclusions are somewhat at odd with the motivations of Guille-Escuret et al., leaving me with some unaddressed questions. Those are not points against the results of the paper, and I believe it is a matter of editing to make the motivations clearer and can be addressed during a discussion period.

- Why focus on the specific conditions in this paper, among the many possible combinations of conditions, even if restricted only to the ones discussed by Guille-Escuret et al.? Have other stronger (in the sense that they would imply the studied condition, up to a change of constants) conditions already been studied?
- One of the motivations of Guille-Escuret et al. for the study of those conditions was to address the current limitations of the theory for accelerated methods, as in Polyak's Heavy Ball, where the parameter setting used for quadratics does not extend to smooth, strongly-convex functions. The result that Gradient Descent is optimal for this class of problem would suggest that the class considered is too large to be useful for the design of new methods, or contains pathological functions. For example, the construction given for the interpolation, while interesting, indicates that the function has arbitrary many local deviations that are unrelated to each other, leading to the question of whether this relaxation of smoothness/strong-convexity is a valid model to pursue?

**Applicability of the assumptions**

Some of the limitations of the work are in regard with the level of applicability of the results. The submission makes the point multiple time that, although the assumptions considered are implied by standard smoothness and strong-convexity assumptions, they are not strictly weaker as their condition number can improve.
Thus the improvement in the rates might be worth the degradation in the dependence on the new condition number, "provided we can obtain better constants under these conditions" (L65). This is reiterated in Remark 2.5. While I am sympathetic to this argument---for example, for least-squares, it is known that the strong-convexity constant can be 0 the Polyak-Lojasiewicz condition is always non-zero---the arguments of the paper would be strengthened by a simple, provable example of the gap between pairs of conditions on a problem of interest. Using the notation of Guille-Escuret et al. ([12]), on what problem do we see a benefit from using `(RSI-, EB+)` instead of smoothness/strong-convexity, that is not already captured by `(PL+, *SC-)`?

I acknowledge that the submission also discuss the applicability of the conditions to fitting neural networks (L80-82). However, I would recommend adding a qualifier after "an impressive feat given the highly non-convex nature of neural networks loss function" (L82) to avoid overstating their applicability, similar to the qualifying paragraph found in Appendix A after L420.

limitations: No concern beyond the lack of a clear-cut use-case for the applicability of the assumptions used here noted above.
review_title: null

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 studied the complexity of gradient descent (GD) in RSI- and EB+ settings, which is more general than the common smooth and strongly convex case. The paper provided linear convergence results of GD in this case, and further derived the interpolation conditions and showed the optimality results of GD under this case based on the PEP framework.
strengths_and_weaknesses: Strength:
1. The conciseness of the results, also the analysis covers both upper and lower bound, which is a complete story.
2. The paper is well organized and easy to read.
3. The independence of the interpolation conditions is interesting.

Weakness:
1. The assumptions may be still a little restrictive (to be a little picky)
questions: Basically I only have some minor questions:

1. You mentioned the optimal set $X^*$ should be convex, which means that the set $X^*$ is connected, right? I have the question because in Appendix A you tried to empirically shows that NN enjoys RSI- & EB+ style trajectory. But the landscape of NN may be complicated, and possibly attains disjoint (or nonconvex) optimal set. So I am confused on the statement "and therefore, the convergence guarantees of RSI− & EB+ naturally apply to the optimization of neural networks in this setting."

2. The independence of interpolation conditions look interesting. Following A. B. Taylor's thesis [32], it seems that the interpolation conditions for both strongly-convex smooth and nonconvex smooth are not independent (am I correct?). As a (kind of) "intermediate" setting, the RSI- & EB+ settings will enjoy the independence, which is a little counterintuitive to me. Is there any possible illustration, e.g., analysis technique? It may be better if authors can provide some discussion on the analysis compared to existing literature.

Some minor points:

1. Sec 5.2, I may suggest that authors should present the formal definition of HB algorithm, here the $\beta$ should distinguish with that of $f_{\epsilon, \beta}$
2. Corllary 1, change $\wedge$ to $\cap$?
3. Appendix A, why do you use "extrapolate" here, any difference compared to "interpolate"?
limitations: Yes
review_title: null

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 is a theoretical paper that studies the performance guarantees for gradient descent where the objective satisfies lower restricted secant inequality (weaker than the strong-convexity condition) and an upper error bound (weaker than the smoothness condition) so that this includes some non-convex objectives. The paper also proves that the gradient descent is optimal on this class of functions among all first-order algorithms.
strengths_and_weaknesses: The paper is well written and is a solid theoretical paper. It is remarkable that the authors can show rigorously that the gradient descent is optimal on the class of functions that satisfy a lower restricted secant inequality and among an upper error bound all first-order algorithms.

The weakness of the paper is that even though the paper has a nice theoretical contribution, its practical importance and relevance is less clear to me. The class of objective functions that the author(s) study includes some non-convex functions, but when you have gradient descent, depending on the initialization, the algorithm can easily get stuck at a bad local minimum. Then the optimality discussed in the paper might be restrictive. Also for example, in practice, how do you measure your $\mu$ and $L$? In addition, the optimal stepsize for this class of objective functions is $\alpha=\mu/L^{2}$, which is smaller than the standard choice $\alpha=2/(\mu+L)$ for the $\mu$-strongly convex and $L$-smooth objective. I am wondering what is the intuition behind this because $\mu$-strong convexity and $L$-smoothness can be viewed as a special case under your assumption. What is the intuition that you need to choose smaller stepsize in your setup?
questions: (1) In addition to the questions I mentioned above, one interesting thing I find is that the author(s) show that the gradient descent is optimal on this class of functions among all first-order algorithms. For $\mu$-strongly convex and $L$-smooth objectives, it is known that Nesterov's accelerated gradient descent and heavy ball method can accelerate. So for your class of functions, the gradient descent is already optimal? What is the intuition behind this? Since your class of functions also include non-convex functions, does this indicate that when you have non-convex objectives, gradient descent might outperform Nesterov's accelerated gradient descent or other momentum-based methods?

(2) In equation (9), write ''if'' in the text environment.

(3) In Corollary 1, in the last line, write ''where'' instead of ''Where'' and add a '','' in the equation before the last sentence. Same can be said about Theorem 1.

(4) In the first line in Theorem 2, it should be ''Let $\mathcal{A}$ be''.

(5) In the second line in the proof of Theorem 2, write ''be the sequence introduced in Lemma 1''.

(6) In reference [17], nesterov should be Nesterov and please check the other references as well. 
limitations: It does not seem to me that the author(s) stated the limitations and potential negative societal impacts of their work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this work, the authors considered applying the gradient descent algorithm to functions in the intersection of RSI- and EB+. The intersection set is a generalization of the set of strongly convex and differentiable functions. A matching lower/upper bounds on the convergence rate is derived.
strengths_and_weaknesses: In this work, the authors extended the results of classical convex optimization and showed that the gradient descent algorithm is optimal for functions in RSI- and EB+. I think the results are interesting to audiences in optimization and machine learning. Furthermore, the presentation of this paper is clear and easy to follow.

My major concern is on the importance of the contribution in this work. As the authors mentioned, there are lots of existing literature studying lower/upper conditions. Many of those conditions can also guarantee the linear convergence of gradient-based algorithms; also see my comments in the "questions" section. Hence, I am not sure if the contributions in this work are significant and would suggest the authors provide more discussions on the importance of the results.
questions: Major:
(1) Line 78: since the stochastic gradient descent (SGD) method is considered for the optimization of neural networks, I wonder if the probability of escaping the attraction basin of local minima is sufficiently small. If the escaping probability is non-neglectable, the linear convergence may fail with certain probability and it is unsuitable to claim that RSI- and EB+ provide a guarantee on the linear convergence of SGD.

(2) In Thm.1 and Thm.2, the optimality gap is characterized by x_i - x_i^* and x_i - x^*. It would be better if the authors can provide a comparison between these two metrics, which is important to the tightness of lower/upper bounds.

(3) In the proof of Thm.2, it would be better to explicitly show why {x_i} are different points.

(3) Maybe I missed something, but I think functions in the intersection of RSI- and EB+ also satisfy the Polyak-Łojasiewicz (PL) condition. Under the PL condition, it is already known that descent algorithms with a (small) constant "step size" are optimal and converge linearly. Hence, the advantage of the bounds in this work lie in a matching lower/upper bound without a constant factor of difference, which seems marginal. I would suggest the authors provide a more detailed comparison with existing results on PL functions.

(4) In this experiments, the authors showed that the gradient descent method is better than the heavy-ball method. I wonder if this phenomenon is also observed on other functions in RSI- and EB+, or only appears on this special example. It would be better if more details of this experiments can be provided (e.g., which objective function is constructed).


Minor: 
(1) Ln.20: it would be better to mention that alpha is the step size.

(2) Remark 2.2: I wonder if the authors can provide an example of non-convex functions that satisfy RSI-.

(3) Remark 2.4: the discussion after the first sentence seems unnecessary to me. When comparing RSI- and EB+ to other conditions, people usually assume that the same parameters (mu and L) are used. But I am okay if the authors want to keep this discussion.

(4) Ln.86: I think the Kurdyka-Łojasiewicz and the Polyak-Łojasiewicz conditions do not "take the form of a lower and an upper bound on properties of the objective function", since the gradient and the optimality gap appear on both sides of the inequality. If I am correct, it would be better to revise the statement on Ln.86.

(5) Ln.224: should "learning rates" be "convergence rates"?
limitations: See my comments in the "questions" section.
review_title: null

Meta-review: metareview: A solid theoretical paper with fine execution that establishes the optimality of the vanilla gradient descent method in a class of functions extending the well-studied class of smooth and strongly convex functions. Please make sure to take into account the insightful feedback given by the reviewers in the revised version.
confidence: Certain
Decision: Accept