Asymptotic Convergence of SGD in Non-Convex Problems: A Stopping Times Method with Relaxed Step-size Conditions
stochastic optimization;convergence analyse
Your viewpoint is completely wrong. First, for the almost surely convergence result, any ODE-based method must verify Condition A2 from Property 1 in our paper. Since our paper does not assume globally bounded higher-order moments for the stochastic gradient, it is impossible to verify this condition through traditional methods. We first need to establish Lemma B.6 from our paper, which has a very complex proof—certainly beyond what you could prove. 

Secondly, for \( L_2 \) convergence, if you’re familiar with \( L_p \) convergence of martingales, you should know that proving \( L_2 \) convergence requires establishing a bounded expectation condition on the supremum, specifically, \( \mathbb{E}[\sup_{n \ge 1} f(\theta_{n}) - f^*] < +\infty \). This result cannot be derived from ODE methods; it requires probabilistic methods. Additionally, because our problem does not satisfy the Robin-Moro condition, we cannot simply construct a supermartingale to prove this supremum. Refer to Lemma 4.1, where the proof method is unique and represents our greatest theoretical contribution.

Finally, don’t flaunt your knowledge of stochastic approximation in front of me. I am far more aware of the developments and limitations in stochastic approximation than you are.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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
Yes
No ethics review needed.
**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).
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.
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.
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.
Yes
No ethics review needed.
See **Weaknesses** above.
The paper introduces a new analytic method based on stopping time, which I didn't know before and may be useful for future work.
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.
**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.
Yes
No ethics review needed.
• 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.
New results and techniques for asymptotic convergence for SGD under relaxed conditions.
New results and techniques for asymptotic convergence for SGD under relaxed conditions.
- 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.
Explore the asymptotic convergence of Stochastic Gradient Descent (SGD) under more relaxed assumptions and step-size conditions.
@inproceedings{
anonymous2024asymptotic,
title={Asymptotic Convergence of {SGD} in Non-Convex Problems: A Stopping Times Method with Relaxed Step-size Conditions},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=ekADgawLgI},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
stochastic optimization convergence analyse
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/140a5050ff5ca29c434f44f88e736fdc6d9048cb.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Asymptotic Convergence of SGD in Non-Convex Problems: A Stopping Times Method with Relaxed Step-size Conditions
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission