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: This manuscript provides a unified asymptotic convergence analysis framework for several centralized stochastic optimization methods such as SGD, random reshuffling, proximal SGD and stochastic model-based methods. By introducing two sets of general conditions on the abstract convergence measure as well as the sequence generated by stochastic optimization algorithms, they derive both the expected and almost-sure convergence to the stationary points, respectively. The authors then apply this result to the abovementioned algorithms to obtain asymptotic convergence guarantees in the expected and almost-sure senses, which either recover existing convergence results (possibly under weaker assumptions) or generate new results.
strengths_and_weaknesses: Originality: The main novelty of this paper relies on the generality of the proposed unified convergence analysis based on the abstract stationarity measure \Phi, which seems new to the reviewer. The major comments are summarized as follows:

Strengths:
- By introducing general conditions on the abstract stationarity measure \Phi, their theoretical analysis enjoys high flexibility to recover or complete the expected and  almost-sure asymptotic convergence results of existing stochastic optimization methods under several problem settings, thus is potential to simplify algorithm design and analysis.

- This paper is well written and easy to follow. The convergence analysis for SGD, RR, prox-SGD and SMM methods is clear and reveals some insights among these methods.

Weaknesses:
- On technical novelty: Since the considered stochastic optimization methods in this work have been well studied, and the proof techniques used in this paper are standard, thus the technical contribution is limited to some extent.
- On the obtained rate results: For non-convex problems, the convergence to a stationary point of the objective function is not very informative since the result cannot declare any optimality, from this understanding, the obtained asymptotic convergence results in this work are even weaker than the existing iteration complexity results which further shows the  non-asymptotic convergence rates under certain measures.

questions: - On the generality of the proposed framework: To show the generality of the proposed unified theorem, the reviewer would like to see if it can be applied to other recently developed stochastic optimization algorithms that employs variance-reduction techniques and varying sizes of mini-batches.
- On significance of contribution: It is not very clear how this proposed framework will improve the existing analysis. The reviewer would thus suggests adding a table to compare the convergence results of the existing stochastic algorithms and that obtained from the proposed framework with respect to different assumptions and problem settings to illustrate generality and reveal some insights if any.

limitations: The generality of the proposed framework is not very clear to the reviewer. The authors are thus suggested to make clear the scope of stochastic optimization algorithms that can be incorporated into this unified convergence analysis.
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: This paper derives general convergence results for stochastic optimization methods. The results include the cases where the cost function is nonconvex and nonsmooth.
strengths_and_weaknesses: Strength: The approach is general and can be applicable to several settings.

Weakness: The results are only asymptotic and about the gradient norm (as such, not "global" optimization results).
questions: I have the following questions about writing as well as the nature of the results:

1) Please give an example, before providing your main theorem in Sec. 2, what an abstract convergence measure \Phi could be.

2) In convex and nonconvex optimization, asymptotic results are somewhat of secondary importance, as nonasymptotic bounds could provide reasonable heuristics to optimize the parameters of optimization methods. Why do the authors provide only asymptotic results in this paper? In other words, what was the difficulty in getting nonasymptotic results?

3) Related to my second question, if authors manage to convert some of these results into nonasymptotic ones, is it clear that the rates of convergence would match standard rates? In other words, someone can derive a very slow convergence rate for these optimization methods (which would all converge in the same way asymptotically), but would not be very useful otherwise.

I would be inclined to reconsider my rating if the authors provide a convincing discussion whether their technique can lead to nonasymptotic bounds.
limitations: Not applicable.
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 work provides a unified theorem for analyzing several stochastic optimization methods. Both expected and almost sure convergence are derived. For applications, the authors recover the convergence results for stochastic gradient descent (SGD) and random reshuffling (RR). In addition, this paper also obtains the convergence result for the stochastic proximal gradient method (prox-SGD) by using the proposed framework.
strengths_and_weaknesses: This paper is well written and easy to follow in general. The structure of the paper is good and provides some new insights into the convergence results for the stochastic optimization methods. The core theorem 2.1 is very important and its proof makes sense to me. Furthermore, the prox-SGD is analyzed via this framework to obtain some convergence results.

The main weakness is that the proposed method only provides an asymptotic convergence result, which is less informative compared to the finite-time type of bounds. In addition, the function value convergence might be also interested.


questions: Is there a typo in assumption (B.2)? Why do you require the sum of alpha^3 < infinity. The description for random reshuffling is rather rough, I would suggest the authors provide more details in the appendix for this method. 

Some minors: in line 54 the hessian and gradient, in line 350 analyses. 


EDIT: after the authors' response, I increased my score to 7.
limitations: Yes.
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 authors analyze the convergence of SGD-like methods such that the norm of the gradient in the last iterate convergence to zero in expectation and almost surely. They provide the general framework to analyze the convergence for SGD-like methods, including SGD, Random Reshuffling, Prox-SGD, and Model-Based methods. Using this framework, they show the convergence of these methods.
strengths_and_weaknesses: i) The authors prove the main Theorem 2.1, which generalizes results from, e.g. https://parameterfree.com/2020/10/05/almost-sure-convergence-of-sgd-on-smooth-non-convex-functions/
or Gradient convergence in gradient methods with errors. Bertsekas et al. 

Strengths: The generalization can be useful and give insights into the community.

Weaknesses: Yes, it can help to analyze a broad family of methods, but I think that the paper doesn't have enough examples to be sure that Theorem 2.1 is the "Unified Convergence Theorem."

ii) As the authors noted, the last-iterate convergence of SGD and RR was analyzed before, so, qualitatively, the paper's contribution is the analysis of Prox-SGD and SMM.
 
Strengths: Even the fact that it is possible to prove the convergence of Prox-SGD is interesting. 

Weaknesses: To prove the convergence, the authors use Assumption (C.3) that $\varphi$ is $L$-Lipschitz. For instance, one of the most popular regularizers $\varphi(x) = \frac{1}{2} ||x||^2_2$ is not $L$-Lipschitz.

I think the paper is good. It provides proof that Prox-SGD and SMM converge. At the same time, I'm not sure that Theorem 2.1 can be considered the "Unified Convergence Theorem," but it can be helpful for the community.
questions: Suggestion: In the proof of Theorem 2.1, I think that it is possible not to differentiate $q = 1$ and $q > 1$. Can we in (16) use the boundness of $\beta_t$ and $\mu_k,$ and then use the same arguments as for the case $q = 1$? This can simplify the proof.
limitations: NA
review_title: null

Meta-review: metareview: The authors provide a blanket convergence analysis for several stochastic optimization methods. The techniques are interesting and will be useful. 

The authors may want to be a bit more careful on the details on some of their convergence results when they make comparisons. For instance, the main difference between [3] and [26] is in the noise assumptions in [26], which allow to use more aggressive step-size policies. Otherwise, the difference in assumptions that the paper alludes to is reflected in the fact that [26] is getting a stronger convergence result (to a component of critical points), whereas [3] leaves open the possibility that the process escapes to infinity (the assumptions in [26] rule out this behavior). The authors also miss the recent work, which provide a tighter, general characterization:

Y.-P. Hsieh, P. Mertikopoulos, and V. Cevher. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. In ICML '21: Proceedings of the 38th International Conference on Machine Learning, 2021.

confidence: Certain
Decision: Accept