Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the complexity of the first-order algorithms with being able to find the global optimal solution of nonconvex objective functions which satisfy the KL condition. This work uses a dynamic system to characterize the evolution of the iterates generated by the proposed algorithms. It is shown in this paper that the derived convergence rate of the variants of SGD is tight and further a variance reduced algorithm is also proposed with a convergence rate of matching the lower bound.
strengths_and_weaknesses: Strengths:
This paper studies a recent popularized question of showing the convergence rate of the first-order algorithms to the global optimal solutions of the nonconvex objective functions under the KL condition. This class of problems indeed covers a wide range of problems in machine learning. Especially, it is good to see that this work has already listed several motivating examples whose objective functions satisfy the KL condition. 

More importantly, this paper provides the convergence rate of a variant of the SGD algorithm in this setting and proposes a new algorithm that can achieve the improved rate to find the global optimal solution. Theorem 1. is general, which gives the iteration complexity of the SGD with restarts under the KL condition.

Weaknesses:
Even though I believe that this is a truly interesting work and studying a worth well optimization problem, the main concerns are the quality of the presentation, significance of the theoretical results, and numerical justification of the algorithms. To be more specific, please see below.

1, The presentation of this work needs more attention. A thorough comparison between this work and existing ones should be addressed in multiple dimensions, e.g., learning rates, hyper-parameters if any, complexity of the algorithm. Also there are other issues. See the next session.

2,  Although the convergence rate achieved by the SGD with restarts is applicable for general case (KL), the rate matches the existing ones for the PL case which is the most practical setting for applications. How this extension is important to the machine learning problems is not clearly discussed or what are the challenges of showing the convergence beyond PL are not particularly discussed. Note that some discussion included in page 6 mainly focuses on the generality of the assumption 4 rather than KL. So, which assumption or condition is the truly restrict/general one that needs to be conveyed in this work is not clear. 

3, it is not surprising that PAGER can achieve a better convergence as the variance reduction has been applied. In practice, VR based algorithm would not perform well in terms of the generalization error. Also, the theoretical results are only applicable to the PL case rather than the KL case, but I presumably the main topic of this work is about showing the iteration complexity of the algorithms under the KL condition. 

4, Both alg.1 and alg.2 are variants of the existing ones. It is necessary to showcase the numerical performance of these algorithms with a comparison with the baselines.


============================= After rebuttal ====================

Thanks for the authors' detailed response. I have increased the score. The concern regarding the small step size remains, which is not about the correctness of the proof but a concern about the dependence of the step size on the hyper-parameters, e.g., $n$.

questions: 1, it is quite confusing that why $g_k$ needs to be dependent on $k$? how does $K$ take the role in the convergence rate?

2, in theorem 1, how many $\omega_j$s? it seems that there is only one $\omega_k$ show in eq. 9. How about others?

3, in theorem 1, whether $\nu$ is also nonnegative?

4, in theorem 1, when $\zeta$ is large, then $\delta_k$ shrinks fast but $\eta_k$ is small, which contradicts the intuition that a large step size gives a fast convergence rate.

5, line 230, when $\beta=0$, [14] gives the result but corollary 1 requests $\beta\in(0,1]$ which means that $\beta$ cannot be 0 or corollary does not cover the existing results. 

6, I agree that the convergence result built upon the last iterate makes more sense, but how does the stochasticity of the gradient estimate take place in the final convergence result?

7, what is the main reason of using the restart strategy? how to compare the step size $\eta$ with the classic one in SGD? is this choice of the learning rate critical to show the convergence? 

8, line 297, how is $D$ obtained in the analysis? is it dependent on $\mu$ or $L$?

9, in theorem 3, why is the step size $\eta_t$ dependent on $n$? when $n$ is large, the learning rate will be extremely small, right?

10, why did not include some numerical results?


limitations: The limitations of this work are not mentioned, but I think it is fine as it is a truly theoretical one of discussing some math properties.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper provides rates of convergence under various assumptions for global KL functions - which is rich enough to include many popular loss functions in practice. The authors provide rates for SGD algorithm, and then provide a new algorithm called PAGER which enjoys improved rates due to variance reduction. They then show how to apply this algorithm for finite sum optimization problems. 

strengths_and_weaknesses: Strengths: The class of global KL is fairly rich and stochastic optimization is not well understood in this class. 

Weaknesses: I found the contributions of the paper to be a bit underwhelming and lacking novelty. Let me explain: 

1. The upper bound provided in Corollary 1 and the lower bound in Proposition 1 do not fit well with each other. The lower bound only holds for a particular step-size sequence and does not say much about the minimax rates for SGD for this class. 

2. Given the above, I am not sure how valuable is the contribution of improved rates under variance reduction. 

3. Lemma 2 is vacuous as it seems to be based on just comparing upper bounds which may not be tight. 


4. The theoretical ideas used in the SGD analysis, variance reduction, etc are not novel. In the end, the paper seems to be combining various previously known technical ideas, without any new high-level algorithmic insights. The paper seems to be missing an important reference: Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations, Arjevani et. al. 2020. 

5. There are still many gaps in the corresponding rates for KL functions. 


questions: Please refer to other sections! 
limitations: No foreseeable negative societal impacts.
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 studies the convergence of SGD and PAGE under smoothness, the Kurdyka-Lojasiewicz inequality, and the expected smoothness assumption. The authors show that the iterates generated by SGD follow a dynamic (Lemma 1) that can be tuned to ensure the optimal convergence rate using a certain step size scheme (Theorem 1 and Corollary 1). The authors show that using (with-replacement) mini-batching in the online setting can not improve the convergence rate of SGD further, and that their solution of the SGD dynamic they start with is optimal, although whether the dynamic they start with is optimal is not known. By extending the variance-reduced PAGE algorithm to the KL setting, the authors obtain improved convergence rates for online as well as finite-sum problems.

strengths_and_weaknesses: Main points:
- (Strength) The setting studied (convergence under KL and Assumption 4) is very general, it covers several interesting applications that are not covered by existing analysis, and extends the applicability of results on the convergence of SGD and PAGE to several new applications (e.g. those mentioned in lines 44-46).
- (Strength) The rates provided by the paper (in Corr. 1 and Thm. 3) recover the best prior rates when specialized to the setting of \(\alpha = 2\), and extend these settings for general \(\alpha\) and for SGD, under assumption 4 specifically. This means we gain more generality at no additional cost. Furthermore, generalizing the proofs is not straightforward from the prior work.
- (Weakness) Sec. 3.3 talks about tightness, but in my opinion it is very misleading. The notion of tightness used here is the tightness of solving the particular recurrence the authors get in (eq. 7); But the result of Lemma 1 may not itself be tight at all.
- (Weakness) While Sec 3.2 shows that minibatching cannot improve the convergence of SGD, this is only for minibatching with-replacement in the online setting. There are other forms of minibatching that can potentially improve the convergence rate of SGD, see e.g. [1].

Overall: I think that while the paper has some drawbacks, it presents a nice contribution to the literature on SGD and PL. Therefore, I recommend acceptance.

[1] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtárik. SGD: General Analysis and Improved Rates, PMLR 97 (2019).


questions: - Can your result be used to handle other forms of minibatching as in [1]?
- What about the dependence on the condition number? It is hard to parse and compare how your condition number dependence differs from prior work.
- Lemma 4 seems to use a similar step size scheme to [2], can you discuss the similarities/differences?



Post-rebuttal:
I thank the authors for their clarifying remarks, I have raised my score as the response is satisfactory.

[1] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtárik. SGD: General Analysis and Improved Rates, PMLR 97 (2019).
[2] Sebastian U. Stich Unified Optimal Analysis of the (Stochastic) Gradient Method, arXiv:1907.04232 (2019).

limitations: See the previous sections for limitations. Potential negative societal impacts are not applicable here.
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: The paper considers the stochastic optimization problem under the $\alpha$-PL condition and the order k expected smoothness condition. The paper establishes the finite-time convergence for the SGD with a restart algorithm. The result generalizes the previous analysis to a wider range of \alpha, and the sample complexity is later proven to be tight for restarting SGD. The paper then further improves the sample complexity by incorporating the variance reduction method PAGE into the restarting SGD algorithm.
strengths_and_weaknesses: * Strengths:

The paper is well-structured and easy to understand. Section 3 offers an interesting analysis of the dynamics of stage-wise SGD under \alpha-PL condition. The work is sound and thorough—it contains a tight analysis of stage-wise SGD, and in addition, it also provides an analysis of the variance reduced variant and establishes an improved sample complexity for different \alpha.

* Weaknesses:

The theoretical generalization claimed by this paper lacks applications, e.g., the generalization of $\alpha=1 or 2$ to $\alpha \in [1,2]$ and the generalization of $h(t)=t$ to a concave $h(t)$ do not include more real-world applications. The extension of stage-wise SGD to PAGER lacks unique challenges therefore the improvement of sample complexity seems expected. 

questions: 1. How generalized is Assumption 4 compared to the expected smoothness assumption [23,18,47]? Specifically, are there any applications with a concave h(t) other than $h(t)=t$? In addition, are there any applications where $\alpha \in (1,2)$?

2. The restart process in Algorithm 1 is important for establishing the sample complexity. Yet it seems there is only one condition on $N=KT$, while the explicit conditions on T and K, which captures the impact of the restarting process, cannot be found in the analysis of section 3.1. It would be great if the authors can explicitly discuss the choice of $T, K$.

3. The main results (Corollary 1, Proposition 1, and Theorem 2-3) hold for \alpha-PL functions. Why do the authors claim results hold under the more general KL-condition (e.g., in the title, in section 1.1)?

4. What are the theoretical challenges arising from incorporating PAGE into the stage-wise SGD? What is the techniques used to overcome the challenge? What is the reason for using PAGE instead of other variance-reduction methods?

Minor questions:

 There are typos in the paper:  ‘Assumption 7’ should be changed to ‘Assumption 6’, and there are question marks in line 620.

limitations: Yes.
review_title: null

Meta-review: metareview: This paper offers an analysis for SGD, and then a variance reduced method PAGER, under the general KL assumption. This is a very large family of functions, that includes many interesting non-convex objectives, and thus is interesting for the community. And quoting one of the reviewers "The rates provided by the paper (in Corr. 1 and Thm. 3) recover the best prior rates when specialised to the setting of (\alpha = 2), and extend these settings for general (\alpha) and for SGD, under assumption 4 specifically. This means we gain more generality at no additional cost." The reviewers also eventually agreed that the technical novelties introduced to establish the proof are also interesting and new.
confidence: Less certain
Decision: Accept