Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper found a simple (but effective) variant of the continuized Nesterov acceleration (Even et al., 2021) that achieves the optimal complexity (with high probability) under the quasar convex condition for the first time. (Quasar convexity is a non-convex condition that some gradient methods are known to find a global solution.) Previous results, built upon the standard (discrete) Nesterov acceleration, required multiple gradient evaluations at each iteration, and thus only had the near-optimal complexity. This paper then provides several quasar convex examples, such as generalized linear models (GLM), to support the importance of studying the quasar convexity.
strength_and_weaknesses: - This is the first first-order method that has the optimal complexity for quasar convex minimization.
- Various examples satisfying the (strong) quasar convex condition are provided.
---
- One might view this as a simple modification of the continuized Nesterov acceleration.
- An intuition behind the success of the proposed randomized method over the existing method for quasar convex minimization is not clearly given (other than the final proof), and this could be of interest to some readers.
clarity,_quality,_novelty_and_reproducibility: This paper is well written, and its contribution is clearly novel and interesting.
summary_of_the_review: Finding an optimal first-order method for the (strong) quasar convex minimization has been an open question in the optimization community, and this paper has resolved it. Momentum has been the main workhorse for training "non-convex" machine learning models, and this work provides a nice contribution on expanding our knowledge on accelerated non-convex minimization.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose a randomized acceleration method based on the continuized scheme proposed in [1]. The method targets the nonconvex optimization problems  with quasar convex structure, and obtains the optimal complexity rate in expectation. The authors also illustrate that for a class of generalized linear models the quasar property holds and provides theoretical analysis to estimate the quasar convexity constants.




[1] Even, Mathieu, et al. "A continuized view on Nesterov acceleration for stochastic gradient descent and randomized gossip." arXiv preprint arXiv:2106.07644 (2021).
strength_and_weaknesses: Strength:
This paper not only improves the complexity of first-order methods for quasar convex optimization, but also identifies a large class of problems satisfying quasar convexity. It shows the great potential of developing algorithms in continuous time and I believe it will have growing impact to the community


Weakness

I am a bit curious whether quasar convexity is useful beyond the setting discussed in this paper. 
GLM is a motivating application for the proposed continuized method. However, it looks like the quasar convexity assumption relies on the fact that there is a perfect $w_*$ that interpolate all the data (i.e. the overparameterized setting), this seems to suggest some limitation of in real applications. 

In example 3, the relu link function is not differentiable at z=0. Can you still apply the gradient based algorithm for such setting?

Typo

Page 4

On the last line: there exists a $w_*\in\mathbb{R}^d$


Notations are inconsistent: Both $\|\cdot\|$ and $\|\cdot\|_2$ stands for Euclidean norm; they should be unified.
clarity,_quality,_novelty_and_reproducibility: 
Clarity:
The paper is well-written and is easy to follow, though I did not fully go through the technical proof. 
The paper also uses many examples to illustrate the application of quasar convexity and the potential impact of the proposed method.



Novelty
The result is new but the technique seems to be standard as it is based on putting the continuized technique and complexity analysis of quasar-convex optimization together, both of which have been well-established in the prior work. 


summary_of_the_review: The paper is of good quality, it provided a unified and justified quasar convex framework for many important nonconvex functions, and developed a novel accelerated method with improved complexity rate. While there is some limitation in the application, the theoretical contribution of this paper is sufficient, which has great potential to the development of nonconvex optimization.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied minimizing quasar convex functions. Authors studied the relationship between quasar convexity and many common structure assumptions in nonconvex optimization, and verify that GLM satisfies quasar convexity under mild conditions. Then they proposed a new algorithm based on the continuized discretization technique in literature, the continuized Nesterov acceleration improves over existing algorithms and achieves the optimal complexity.
strength_and_weaknesses: Strength:
1. Connect quasar convexity with many existing structural nonconvex assumptions, and real application GLM
2. Provide a complexity result which is claimed to outperform existing works.

Weakness:
1. The comparison with existing works is a little confused to me.
clarity,_quality,_novelty_and_reproducibility: I think the paper is well-written and easy to follow. The paper considers both theory and real applications, the main technique, continuized discretization, is relative new in literature, which reveals novelty.
summary_of_the_review: Generally I am satisfied with this work. My main concern lies in that:

1. How do you choose $T_k$ in Theorem 1, you mentioned that $T_k$ are random times. Are you referring it as a "stochastic stepsize", or you will predefine the $T_k$ (or the total iteration number as in many classical optimization literature) before running the algorithm?
2. When comparing to Hinder's work, you mentioned they need an extra log complexity in the function evaluations. First I feel that such logarithmic difference is a bit incremental; second for me such binary search subroutine seems to be more toward a practical preference, if we just follow their "General AGD Framework" (Algorithm 1 therein), then the results in your work and Hinder's work should be basically the same.

Thank you for the effort.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper has three main contributions.

Firstly, under quasar convexity (an assumption weaker than convexity that still guarantees local minima are global minima) and smoothness, authors develop an optimization algorithm using the continuized framework of Even et al 2021 and obtain optimal rates with high probability, in contrast with Hinder et al. 2020 that have an extra log factor (although their convergence was deterministic).  They note that the convexity inequality in the analysis of Even et al is only used once and can be easily replaced by the quasar convexity inequality which leads to their result. 

The second contribution is extending the GLMtron paper (Kakade et al) to use this framework as well for Generalized Linear Models. Some empirical comparisons are provided for algorithms in both contributions.

Thirdly, contribution is showing that certain classes of functions that had been used before satisfy quasar convexity, expanding the set of applications of this framework.
strength_and_weaknesses: This is a nice paper. Realizing that the continuized framework of Even et al. does not require the progress-regret balancing step that leads to needing the binary search of Hinder et al. is a nice result. I would phrase the "our contributions include" and would not say that you "improve" over Hinder et al., since this result is in high probability (or with this E[T_k^2 * gap] result) and their result is deterministic

I found really interesting that with this framework one can show that for the class of functions in Gille-Escuret et al. 2022, for which gradient descent is optimal, if you substitute the gradient Lipschitzness condition by smoothness then you can accelerate.

On the other hand, there is a small error/typo in your interpretation. You say that "$L$-smoothness implies the $L$-Lipschitness of the gradients". But it is the other way around. $L$-Lipschitness of the gradients implies smoothness. 
EDIT: I think I got confused and concluded that despite of this fact, what you said made sense to me. But now that I read it again it does not make sense. Since $L$-Lipschitness of the gradients implies smoothness, the class of smooth functions is larger. So it seems to me you are not getting any improvement under any additional assumptions. You are just showing "better rates" but because it is a different optimization metric (i.e., additive error in function value instead of multiplicative error in iterates, and also your result only holds with high probability). I would appreciate a clarification. 

It would be better if you had error bars in the plots of your experiments.

clarity,_quality,_novelty_and_reproducibility: The paper is well written, and I already commented on the quality. Of course, most of the analyses in the proofs are borrowed from Even et al. and Kakade et al. 2011 since the algorithms are modifications of those, but this is fine.

Some typos:

Section 3.1.3 Guassian

page 7 "c.f." -> "cf."

page 8 "and that the derivative" -> "and when the derivative" 

page 8 cae -> can
summary_of_the_review: The paper contains a nice idea that was well developed to show algorithms and their convergence in some quasar-convex frameworks and also adds new examples of quasar convex functions to the literature, which is another nice contribution.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a randomized acceleration method for quasar convex optimization, which is a nonconvex setting where local minima are global minima. The method is based on the continuized discretization technique of Even et al. (2021) and achieves the optimal complexity rate in expectation, improving over the previous work of Hinder et al. (2020) that required an extra logarithmic factor. The paper also shows that a class of generalized linear models (GLMs) satisfy quasar convexity under mild conditions, and provides empirical evidence of the effectiveness of the proposed method on synthetic and real data. Moreover, the paper connects quasar convexity with several existing structural assumptions in nonconvex optimization, such as the Polyak-Lojasiewicz condition and the restricted strong convexity condition, and identifies new examples of quasar convex functions.

The paper received positive reviews from all the reviewers, who appreciated the novelty and significance of the contributions, the clarity and quality of the writing, and the potential impact of the paper to the optimization community. The reviewers also praised the paper for providing a unified and justified quasar convex framework for many important nonconvex functions, and for developing a novel accelerated method with improved complexity rate. The reviewers raised some minor issues and questions, such as the choice of the random times in the algorithm, the comparison with the existing works, the applicability of quasar convexity beyond the overparameterized setting, and the use of the relu link function in the GLM example. However, none of these issues were considered as major flaws or obstacles for accepting the paper. The reviewers also suggested some minor corrections and improvements, such as adding error bars to the plots, clarifying some notations and statements, and providing more intuition behind the success of the randomized method.

Based on the reviews, we recommend to accept the paper, as it is a well-written, novel, and significant contribution to the field of nonconvex optimization, and it has the potential to stimulate further research and applications of quasar convexity and continuized acceleration.
justification_for_why_not_higher_score: - The paper does not provide much intuition or insight behind the success of the randomized method over the existing method for quasar convex optimization, other than the final proof, and this could be of interest to some readers.
- The paper does not explore the limitations or challenges of quasar convexity and the proposed method in more realistic or noisy settings, where the overparameterized assumption or the smoothness condition may not hold, or where the quasar convexity constants may be hard to estimate or verify.
- The paper does not compare the proposed method with other existing methods for nonconvex optimization that do not rely on quasar convexity, such as gradient descent, stochastic gradient descent, or adaptive gradient methods, and it is not clear how the proposed method would perform in terms of robustness, scalability, or generalization.
justification_for_why_not_lower_score: - It addresses an open and important problem of finding an optimal first-order method for quasar convex optimization, which is a general and relevant nonconvex setting that encompasses many practical problems.
- It proposes a simple but effective variant of the continuized Nesterov acceleration, which achieves the optimal complexity rate with high probability, and improves over the previous state-of-the-art method that required an extra logarithmic factor.
- It provides a comprehensive and rigorous theoretical analysis of the proposed method, as well as the quasar convexity condition, and shows how it relates to other existing structural assumptions in nonconvex optimization.
- It demonstrates the applicability and usefulness of quasar convexity and the proposed method to a class of generalized linear models, which are widely used in machine learning and statistics, and provides empirical evidence of the superior performance of the method on synthetic and real data.
- It is well-written, clear, and easy to follow, and it uses many examples and illustrations to support the main claims and results.
Decision: Accept: notable-top-25%