Venue: NeurIPS 2022 Conference

Reviews:

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 analyzes the global convergence of SGD under more practical assumptions, for the ease of studying the realistic performance for training with non-convex function and noisy feedback. Specifically: 1) it relaxes the global Lipschitz continuity of the gradient function to local $\alpha$-Holder continuity; 2) it relaxes the bounded variance assumption to that the $(1+\alpha)$-moment of the stochastic gradient is bounded by an arbitrary upper semi-continuous function. Hence, the authors provide a new analysis that SGD will either converge to a stationary point or diverge. To ensure the convergence, an additional assumption that generalizes the notion of expected smoothness is introduced.
strengths_and_weaknesses: Strengths:

1. The authors provide three typical losses: linear regression, feed-forward neural networks and recurrent neural networks, to demonstrate the invalidation of current assumptions for analyzing the global convergence of SGD. This shows that current analyses can be applied to practical machine learning problems.
2. The authors give a solid analysis of the global convergence and high-level descriptions for the proof. 
3. Theorem 1 is a strong result than I thought when I just read the introduction. Provided that the model parameters are usually finite, we can infer that the model converges globally from Theorem 1. 

Weakness:

1. Proposition 1 is built by setting $\|\theta\|_2 \rightarrow \infty$, which is not the typical situation for training deep learning models, since the model parameters usually are finite during the training process. 

questions: 1. How does assumption 5 hold for the cases in Example 1,2,3?
2. It is better to give full definitions of $\alpha$-holder continuous and semi-continuous function.

limitations: The main limitation is the interpretation of Assumption 5, which is left for future works.
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 stability of SGD under more general conditions noise models than have been considered before. The paper first  demonstrates three common ML optimization were the convergence of SGD has not been established. Then the paper explores the convergence of SGD under quite general condition, e.g., relaxing both the assumption of Lipschitz continuous gradients and bounded variance, which are usually critical in establishing convergence results for SGD. The results establish that under such general conditions, SGD either convergence to a stationary point or they diverge to infinity. Finally, the paper suggests a technical condition that, if met, ensures convergence to a stationary point.
strengths_and_weaknesses: Strengths: The paper is mostly well written. The paper is very upfront about the limitations of the work.  The mathematical results seem solid. The problem that is considered here is very general and it is indeed that it is possible to establish some convergence results in this case.

Weaknesses: It is difficult to see how the results could be useful in practice, because it is impossible to say before running the algorithm whether it converges to stationary point or diverges. In fact, the only thing the results in the paper exclude is that the iterate move around without diverging and without settling on a stationary point. 

There are no-indepth discussion about how the insights here could be used in practice. There are also no experimental results.
questions: I am a bit surprise that the SGD will always converge to a unique stationary point (given that it does not diverge). If there is a connected set of stationary points, is it not possible that the iterates do not converge to any one of them but rather move around around that set? I mean, e.g., if F:R—>R, if [0,1] is the set of stationary points with F’(\theta)=0 for all \theta in [0,1], I could imagine that the iterates of SGD would after some time start to move around randomly in [0,1]. According to your results, this is not possible? or I am I misunderstanding something? 
limitations: No major limitations that I could see.
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: The paper presents an analysis of stochastic gradient descent for a wide range of applications by removing several usual but problematic assumptions from the analysis, replacing them with more acceptable alternatives. The issues with the current assumptions are illustrated for 3 common problems. Somewhat surprisingly, the authors are able to prove convergence and stability under the new, more permissive assumptions, though not a convergence rate (which wouldn't be possible under these assumptions anyway).
strengths_and_weaknesses: The paper is well written and easy to follow (at least superficially). The improved assumptions mean that the analysis is a lot more widely applicable than previous attempts, which relied on violated assumptions and were thus of less value. The results are original and significant, as are the new methods used to prove the theoretical results.

I do have a few suggestions for improvements though:
- when presenting the 'counter-examples' in the main text, all the authors say is that they have a result that shows there is a counter-example, without even referring to the Appendix for the actual example. I wonder if a simplified version of the counter-examples themselves wouldn't improve the main text, which currently reads as 'trust me on this'.
- there is a lot of introductory space in the paper, and we only get to the meat of it on page ~6, with many results devolved to the Appendix. If the authors want a self-contained paper, then a journal format would be a better fit. For a conference paper, summarizing the first few pages more succinctly might read better.
questions: 1. For 2 counter-examples, a Ridge penalty is mentioned. Is it strictly necessary? If that's the case, then this weakens the argument that previous assumptions were not good enough.
2. l92, where the authors claim that SGD basically always converges, seems somewhat surprising for deep learning practitioners. Can the authors shed some light as to why there seems to be a difference with practice (where SGD certainly can blow up)?
limitations: The authors mention the limitations of their work several times, notably making clear that the technical assumption that they require for their analysis cannot easily be interpreted. In that sense, I think limitations are honestly and properly addressed.
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: This paper studies the convergence of stochastic gradient descent for smooth non-convex stochastic optimization. The main contribution of this paper is that it relaxes the commonly-used assumptions in proving the convergence: (1) global smoothness of the objective function, (2) bounded variance of the stochastic gradient. They are replaced by a much weaker assumption, i.e. local Hölder continuous of the gradient and bounded $1+\alpha$ moment of the stochastic gradient. The authors prove that SGD with a diminishing step size must either converge to a stationary point or diverge. They further add a technical assumption and prove a stability result, showing that the objective function cannot diverge even if the iterates diverge.
strengths_and_weaknesses: **Strengths**:
1. This paper is well-written. The motivation is clear and the presentation is concise.
2. It seems that the results and technical contribution are non-trivial.

**Weaknesses**:
The results seems to be not very interesting. While it gives convergence results, it does not say anything about the convergence speed (while the authors have pointed out that it is impossible under such general assumptions). In such a situation, my concern is that are the general assumptions really necessary? For example, modern optimization problems for neural networks are clearly not globally smooth, but relaxing it by locally Hölder continuous in gradients seems too general. Several works considered more restrictive assumptions, e.g. the generalized smoothness [1,2], under which optimal algorithms have been proved. Analogously, several works relax the assumption of bounded gradient variance by unbounded one that is locally proportional to the gradient magnitude [3,4] (which is satisfied by your first example), in which case optimal algorithms are also developed. 

But this paper clearly has its own values. Currently I haven't delved into the proof details and I may not correctly understand the implications of these results, so I toned down the level of confidence.

[1] Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.

[2] Improved Analysis of Clipping Algorithms for Non-convex Optimization. NeurIPS 2020.

[3] The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance. COLT 2022.

[4] Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis. NeurIPS 2021.
questions: N/A
limitations: N/A
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 authors analyze the convergence and stability of stochastic gradient descent under certain assumptions. In particular, they consider the function to be *locally* Holder-continuous (in opposition to global assumptions), and they relax the boundedness of the variance. In particular:

Under reasonable assumptions on the stochastic gradient descent (SGD) algorithm (with diminishing step size),  the authors show the iterates of SGD either converge (to a stationary point) or diverge to infinity. Under another technical assumption, they also show convergence with probability one.
strengths_and_weaknesses: The paper claims it uses less restrictive assumptions than other existing results. I agree with the authors; they generalize the analysis of SGD to a broader class of functions. However, my biggest concern is the (kind of hidden) assumption that most results hold under |theta_k|<infty.

Moreover, the result of Theorem 1 seems intuitive, given that we are working with diminishing stepsize. I may be wrong on this point, however. Here is my intuition. 
Either:
the iterates are unbounded,
the iterates are bounded and, in that case, contained in a compact set of radius at most R. Since we have diminishing stepsize and a bounded variance, it seems reasonable to believe that, eventually, the iterates stop moving. Moreover, I think that in such a case, it is possible to write a rate of convergence for SGD to a stationary point that depends on R (which justifies Theorem 2).
In particular, the assumptions made in this paper are that f is locally Holder-smooth, and the variance is locally bounded - the authors justify introducing those hypotheses to contrast with similar results that assume global bounds. However, combining local assumptions and |theta_k|<R is (almost) the same as assuming global constants, as we can take the worst-case of those constants over R.
questions: Do the authors believe it is possible to remove the assumption that max_k |theta_k| < infinity?
limitations: See the "strengths & weaknesses" section.
review_title: null

Meta-review: metareview: This paper analyzes the asymptotic convergence behavior of SGD on the class of locally Hölder continuous functions, by generalizing the technique and results of Patel [2021]. The paper extends and generalizes prior SGD analyses that were conducted under the assertion that certain conditions (e.g. smoothness or continuity) hold globally.

The reviewers found that the results are well presented, correct, and of interest to the community. The results could stipulate further research on SGD analyses on function classes more relevant to neural network training or deep learning, and also on non-asymptotic analyses of SGD on the function class studied in this paper.

The internal discussion brought up a few concerns should be carefully addressed when preparing the final version:
- some reviewers found the examples a bit overclaimed and not clearly showing the necessity of considering locally Hölder continuous functions. For instance, analyses that do not require a bounded variance assumption have become standard in recent years (see for instance the textbook by Bottou, Curtis, & Nocedal that is cited in the paper) and thus Example 1 (Linear Regression) could be a bit misleading as it is bringing up an already solved issue. Please relate the examples carefully to the (novel) contributions in this paper,
- and please mention and explain the relation to the arXiv preprint https://arxiv.org/abs/2104.00423.
confidence: Less certain
Decision: Accept