Asymptotic Convergence of SGD in Non-Convex Problems: A Stopping Times Method with Relaxed Step-size Conditions

Authors: Ruinan Jin, Xin shi, ShaoDong Liu, Difei Cheng
Primary area: optimization
Keywords: stochastic optimization, convergence analyse

Abstract:
Stochastic Gradient Descent (SGD) is widely used in machine learning research. In previous research, the convergence analyses of SGD under vanishing step-size settings typically assumed that the step sizes satisfied the Robbins-Monro conditions, which is to say, the sum of the step sizes was infinite, while the sum of the squares of the step sizes was finite. In practical applications, a wider variety of step sizes is often used, but these may not meet the Robbins-Monro step-size conditions, thus lacking theoretical guarantees of convergence. To bridge the gap between theory and practical application, this paper introduces a novel analytical method—the stopping time method based on probability theory—to explore the asymptotic convergence of SGD under more relaxed step-size conditions. In the non-convex setting, we prove that the almost sure convergence of the sequence of iterates generated by SGD when step sizes satisfy \(\sum_{t=1}^{+\infty} \epsilon_t = +\infty\) and \(\sum_{t=1}^{+\infty} \epsilon_t^p < +\infty\) for some \(p > 2\). Compared to previous works, our analysis eliminates the need to assume global Lipschitz continuity of the loss function, and it also relaxes the requirement of global boundedness of the high-order moments of the stochastic gradient to local boundedness. Additionally, we prove \(L_2\) convergence without the need for assuming global boundedness of loss functions or their gradients. The assumptions required for this work are the weakest among studies with the same conclusions, thereby extending the applicability of SGD in various practical scenarios where traditional assumptions may not hold.

Decision: reject
Reviewer scores: 6, 3, 6, 3, 3

Reviews and discussion:
<thread>
creation date:
1730286949617

thread_type:
official_review

<thread_object>
creator: reviewer_eomm

<content>
summary:
New results and techniques for asymptotic convergence for SGD under relaxed conditions.

strengths:
New results and techniques for asymptotic convergence for SGD under relaxed conditions.

weaknesses:
- Uncertain about contributions and relevance to ICLR

    - I am not sure how relevant is this result to ICLR and the authors could spend a bit more effort detailing the significant of their contributions (especially when the cited most recent related works is from 2020). I am not sure why (from reading the paper) that we should care about asymptotic behaviors while finite-time results are much more applicable (and with weaker assumptions), especially for deep learning related optimization where time is severely limited. 

- Not too well written

    - Many typos. For example, lines 99-101 for the definition of the algorithm, the use of n and t is not consistent. Capitalization and spacing typos are present in many places too.

    - Writing is bit vague and redundant at times and can use more editing to make the paper more concise.

questions:
• The Boundedness Near Critical Points assumption (3.1d) is unfamiliar to me and deserve some more comments and examples. 

• Similarly, assumption 3.2c and c' are strange and seem a bit strong. The authors should give more intuition and comparisons.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730586060725

thread_type:
official_review

<thread_object>
creator: reviewer_dpft

<content>
summary:
This paper aims to prove the asymptotic convergence of SGD (in the almost sure and $L_2$ sense) under the relaxed Robbins-Monro condition. The analysis relies on the stopping time method and the tool from stochastic approximation. However, as stated later, many points should be further discussed, and the writing can be improved.

strengths:
The paper introduces a new analytic method based on stopping time, which I didn't know before and may be useful for future work.

weaknesses:
**Major points**.

1. I am confused by Assumption 3.2 (c'), where the authors said $x$ is an arbitrarily small constant, do you mean $x$ is not fixed? But if $x$ can be changed, this assumption seems very strong. Could the authors clarify this assumption further?

2. Line 782, the author claimed that $\epsilon_t$ is non-increasing. However, I cannot find why. If this is an assumption, please clearly state it. Moreover, if this is necessary, this is an extra condition compared to the original Robbins-Monro condition and the existing works, which weakens the impact of the paper.

3. Line 789, there should be some coefficient in front of $\epsilon_t^{p-1}$ on both L.H.S. and R.H.S. to make the inequality hold, for example, $1/2$. Subsequently, Line 796 should be changed accordingly.

4. Line 803, please define $\theta_{\xi_t}$, which I assume is a convex combination of $\theta_t$ and $\theta_{t+1}$.

5. In Eq. (19), what is $\epsilon$? Do the authors mean $x$? Additionally, I can't find why Line 859 is a direct consequence of Eq. (19). Could the authors elaborate more on this step?

6. The proof is not unified as it is separated by two cases, $p \leq 3$ and $p>3$. What is the obstacle to finding a unified proof?

7. Instead of making assumptions on $g_t$, is it possible to only impose conditions on the stochastic noises, i.e., $g_t-\nabla f(\theta_t)$, like Mertikopoulos et al. (2020)?

**Minor points**.

1. The subscripts $t$ and $n$ are confusing. For example, in the description of Algorithm 1, Lines 120-122, Lines 270-271. Please carefully proofread and make them consistent.

2. The statement for each theorem and for $2<p\leq 3$ still uses Item (c), which I believe should be Item (c') instead.

3. It's better to mention that $\\|\cdot\\|$ denotes $2$-norm somewhere.

4. In Assumptions 3.2 (c) and (c'), please either use $\theta$ (like $f(\theta)-f^*<C_p$) and $\nabla f(\theta_t:\xi_t)$ (to replace $g_t$) or $\mathbb{E}[\\|g_t\\|^{2p-2}\mathbb{I}_{event}]\leq M_p^{\frac{2p-2}{p}}$ directly since the current statement is not mathematical rigorously.

5. Line 166, the authors stated ''while Item (c) and Item (d) together are fully equivalent to...'', could you provide proof or a reference?

6. Line 208, ''we'' should be ''We''.

7. Line 247, replace ''.'' by ''and''?

8. Line 256, ''Appendix'' should be ''appendix''.

9. In addition to the above typos, many others exist. I suggest the authors carefully go through the paper again.

questions:
See **Weaknesses** above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730622366981

thread_type:
official_review

<thread_object>
creator: reviewer_pvdn

<content>
summary:
This paper advances the understanding of asymptotic convergence of SGD by relaxing traditional convergence conditions associated with step sizes. It introduces a stopping time method based on probability theory, proving that SGD can achieve almost sure convergence in non-convex settings under less stringent conditions than the Robbins-Monro framework. The analysis eliminates the need for global Lipschitz continuity of the loss function and allows for local rather than global boundedness of high-order moments of the stochastic gradient.

strengths:
1. **Novel Theoretical Framework**: The introduction of the stopping time method based on probability theory provides a fresh and innovative approach to analyzing the convergence of SGD, expanding the theoretical foundations of the field.

2. **Weaker Assumptions and *Strong Results**: The paper successfully demonstrates convergence under significantly weaker assumptions than previous works, such as eliminating the need for global Lipschitz continuity and allowing for local boundedness of high-order moments. This broadens the applicability of the findings in real-world scenarios. In addition, the results presented are robust, proving almost sure convergence in non-convex settings and L2 convergence without the stringent requirements typically imposed. This strengthens the practical relevance of SGD.

3. **Clear and Well-Written**: The paper is well-organized and clearly articulated, making complex concepts accessible. It provides sufficient materials, including detailed proofs and explanations, to support its claims, enhancing the reader's understanding and facilitating further research.

weaknesses:
The paper is primarily theoretical, offering detailed proofs and explanations, and I did not identify any specific weaknesses from a theoretical standpoint. However, it lacks discussion of practical examples that meet the proposed assumptions, despite claiming that these assumptions enhance applicability.

questions:
**Potential Conflicts of Interest**: The reviewer came across another paper available online **prior** to the ICLR submission which also conducted an asymptotic analysis of AdaGrad using a stopping time-based approach. While I acknowledge that the contributions are distinct, could the authors discuss the novelty of their work in relation to this prior research?


Jin, Ruinan, Xiaoyu Wang, and Baoxiang Wang. "Asymptotic and Non-Asymptotic Convergence Analysis of AdaGrad for Non-Convex Optimization via Novel Stopping Time-based Analysis." arXiv preprint arXiv:2409.05023 (2024).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730662175734

thread_type:
official_review

<thread_object>
creator: reviewer_t8yw

<content>
summary:
The paper under review provides an analysis of stochastic gradient descent 
$$
\theta_{n+1} = \theta_n - \epsilon_n g_n ,
$$
where $(\epsilon_n)$ are a sequence of step sizes and $(g_n)$ a sequence of iid stochastic gradients of an objective function $f$.

The main purpose of the paper is to establish conditions upon which the SGD iterates satisfies that $(\Vert \nabla f(\theta_n) \Vert)$ converges to $0$ almost surely and in $L^2$. 

These conditions  laid out are relatively standard:
- The sequence of step sizes satisfies $\sum_{n} \epsilon_n = \infty$ and $\sum_{n} \epsilon_n^2 < \infty$
- $f: \mathbb{R}^d \to \mathbb{R}$ is $d$-times continuously differentiable,  with a Lipschitz continuous gradient.
- $f$ is lower bounded and coercive: $\inf f > - \infty$ and $\lim_{\Vert \theta\Vert \to \infty} f(\theta ) =  \infty$
- A boundedness condition on $f$  in neighborhoods where its gradient is small.
- Unbiased stochastic gradients: $\mathbb{E}(g_n |F_n) = \nabla f(\theta_n)$
- A variance condition on the $(g_n)$, $\mathbb{E}(\Vert g_n \Vert^2 |F_n) \leq C(1+\Vert \nabla f(\theta_n)\Vert^2)$ for some constant $C \geq 0$
- $L^p$ moments bounds for $p >2$ on the $(g_n)$ are required when $\theta_n$ is in a neighborhood where the gradient norm is small, or near some minimizers.

Under these assumptions, the authors do not require the iterates to remain in a compact set almost surely. The main proof strategy leverages results from [1], combined with a particular probabilistic Robins-Siegmund lemma using the objective function as Lyapunov function. 

[1] Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pp. 1–68. Springer, 2006.

strengths:
The authors claim that they provide the weakest assumptions ensuring convergence of SGD, almost surely and $L^2$. However, I disagree with their claim (see weakness) regarding the almost sure convergence.

weaknesses:
The authors claims that they get rid off  the commonly assumed boundedness conditions on the SGD iterates and achieve the weakest conditions ensuring SGD convergence. I disagree with this claim regarding almost sure convergence. As noted in [1], stability conditions for stochastic approximation have been established long ago in works such as [2–5]. In addition, it seems to me that the results of this paper (specifically the almost convergence) are already implied by Theorem 5 in [2] and could be readily derived by verifying the conditions of Theorem 6 in [4], using an adaptation of Proposition 9 from the same reference.

Additionally, since almost sure convergence is not novel, I believe that the $L^2$ convergence result is not particularly surprising.

Finally, the paper contains several typos, even in Algorithm 1, where, for instance, the variable $t$ should be replaced by $n$, or vice versa. The paper would benefit from a thorough proofreading. 

[1] Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pp. 1–68. Springer
[2] Fort J-C, Pagès G. (1996), Convergence of stochastic algorithms: from the Kushner–Clark theorem to the Lyapounov functional method. Advances in Applied Probability
[3] Delyon, B. (1996), General convergence results on stochastic approximation. IEEE trans. on automatic control
[4] Delyon, B. (2000). Stochastic approximation with decreasing gain: Convergence and asymptotic theory. Unpublished lecture notes
[5] Duflo M. (1997), Random Iterative Models

questions:
If I am not mistaken, Assumption 3.1 (d) is equivalent to $\{\Vert \nabla f \Vert \leq \eta \}$ is compact for some $\eta>0$. If so I encourage the authors to make this remark.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721614991

thread_type:
official_review

<thread_object>
creator: reviewer_trxu

<content>
summary:
The paper analyzes Stochastic Gradient method under more relaxed step-sizes that does not satisfy Robbins-Monro step-size conditions. More specifically, the step size considered satisfy $\sum_{t=1}^{+\infty} \epsilon_t = \infty, \sum_{t=1}^{+\infty} \epsilon^p_t< \infty$ for $p>2$. Almost sure convergence and $L_2$ convergence is proven for SGD under this relaxed step size condition. Furthermore, the result is proven under weaker requirements on the stochastic gradients. Another key contribution is introducing a novel analytical method called the stopping time method to prove the results.

strengths:
The paper attempts to fill an important gap between theory and practice, namely by giving guarantees for non-Robbins-Monro steps-sizes it is a step forward in understanding step-size choice in practical scenarios. The technical strengths of the paper are as follows:
1. The results that are presented are true under weaker conditions and so are an improvement over the previous work. The assumption that the $p$-th moment of the stochastic gradients are bounded only in a local region is weaker than assuming global boundedness of the same.
2. The results presented are mathematically precise in the sense that they distinguish between almost sure and $L_2$ convergence and prove them both.

weaknesses:
One of the claims of the paper is introducing a novel stopping time method for analysis. However, it does not give sufficient explanation for it. For instance, to construct sequence of stopping times parameters $a,b$ are introduced but the effect of their choice is not explained adequately.

questions:
1. Various repeated typos have been committed like in the theorems and the lemmas a common line is ‘when $p>3$ use Item (c); when $p\in(2,3], use Item (c)$’ whereas the correct statement should have item (c’) when $p\in (2,3]$. While this does not make the paper harder to understand but too many of such errors could lead to confusion.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper provides an analysis of stochastic gradient descent. Authors aim to drive minimal set of conditions under which SGD iterates evaluated at the function gradient converges to 0 almost surely in L2 (i.e. first order convergence).


This paper was reviewed by five expert reviewers and received the following Scores/Confidence: 3/2, 3/4, 6/3, 6/2, 3/3. I think paper is studying an interesting topic but authors are not able to convince the reviewers sufficiently well about the novelty of their results. The following concerns were brought up by the reviewers:

- Novelty is the main issue. Results in this paper can be obtained using prior work without too much effort.
  
- Poor writing and unclear proofs: Some technical details are stated in a vague way.


No reviewers championed the paper and they are not particularly excited about the paper.
As such, based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend not including this paper to the ICLR 2025 program.