Pith. sign in

REVIEW 3 major objections 5 minor 21 references

Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that SGD with non-increasing step sizes satisfying ∑ε_t = ∞ and ∑ε_t^p < ∞ for some p>2 converges almost surely to critical points of the loss, without assuming the loss is globally Lipschitz.

desk verdict A serious attempt at relaxing SGD step-size conditions to sum ε^p < ∞ for p > 2, with a genuinely new stopping-time proof technique, but Lemma 3.4 has a real gap that currently leaves Theorems 3.1 and 3.3 unproved as written. read the letter →

arxiv 2504.12601 v1 pith:3WO6ZWTH submitted 2025-04-17 cs.LG math.OCmath.PR

Ruinan Jin , Difei Cheng , Hong Qiao , Xin Shi , Shaodong Liu , Bo Zhang This is my paper · ORCID
classification cs.LGmath.OCmath.PR MSC 62L2090C1590C2660G40
keywords stochasticgradientdescentalmostsureconvergencenon-convexoptimizationstoppingtimemethodrelaxedstepsizesL2martingaleapproximation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Stochastic gradient descent is shown to converge almost surely in non-convex problems under step-size schedules that are strictly more general than the classical Robbins–Monro condition: non-increasing positive step sizes with $\sum_t \epsilon_t = \infty$ and $\sum_t \epsilon_t^p < \infty$ for some $p>2$. Under these schedules, the loss values $f(\theta_t)$ converge almost surely to a critical value, and the gradient norms $\|\nabla f(\theta_t)\|$ converge to zero almost surely and in $L^2$. The proof removes the global Lipschitz continuity of the loss function, which earlier almost-sure convergence results required, and replaces global bounds on high-order moments of the stochastic gradient by local bounds. This matters because schedules such as $\epsilon_t = 1/\sqrt{t}$, which violate $\sum_t \epsilon_t^2 < \infty$, now carry a convergence guarantee for a class of smooth coercive losses.

What carries the argument

The engine is a stopping-time count of up-crossings of the sequence $f(\theta_t)$ over a fixed interval $[h_1,h_2]$. The proof defines stopping times $\mu_{3k-2}$, $\mu_{3k-1}$, $\mu_{3k}$ that mark the entrances into, exits from, and returns below the interval, then bounds the expected number of up-crossings by telescoping along the descent lemma whose martingale noise is $M_t = \epsilon_t \nabla f(\theta_t)^\top (\nabla f(\theta_t) - g_t)$. A companion quadratic-variation lemma bounds $\mathbb{E}\big[\sum_t \epsilon_t^m \|\nabla f(\theta_t)\|^2\big]$ over the stopping intervals and recursively reduces the exponent $m$ using $\sum_t \epsilon_t^p < \infty$; once value convergence is known, an ODE pseudotrajectory argument forces the gradient norm to zero.

What would settle it

A concrete test is the smooth coercive function $f(x) = \int_0^x \tfrac12(1+\sin u)\,du$, whose gradient is $\tfrac12(1+\sin x)$, a bounded $1/2$-Lipschitz map. Its critical set is $\{3\pi/2 + 2\pi k\}$ with values $f(x_k) \to \infty$, so $\{x: |\nabla f(x)| < \eta\}$ contains intervals at arbitrarily high function values and Assumption 3.1(d) fails; running SGD on this function with $\epsilon_t = t^{-0.45}$ directly tests whether the conclusion of Theorem 3.1 can still hold once the proof's compactness/critical-value step has no measure-zero critical value set to use.

Watch

Extended reading notes

Core claim

The central result is Theorem 3.2: under Assumptions 3.1 and 3.2 together with $\sum_t \epsilon_t = \infty$ and $\sum_t \epsilon_t^p < \infty$ for some $p>2$, the SGD iterates satisfy $\lim_{t\to\infty} \|\nabla f(\theta_t)\| = 0$ almost surely. Theorem 3.1 establishes the preceding value convergence, $f(\theta_t) \to f(\theta^*)$ a.s. for a critical point $\theta^*$, using only the local $p$-th moment bound; Theorem 3.3 upgrades the gradient convergence to $\lim_{t\to\infty} \mathbb{E}\|\nabla f(\theta_t)\|^2 = 0$. The assumptions on the loss are lower boundedness, Lipschitz gradient, coercivity, and the nonstandard boundedness near critical points; the stochastic gradient is unbiased, has a weak second-moment growth condition, and has locally bounded higher moments. A fair reading is that the paper establishes the same asymptotic convergence guarantees as the strongest prior almost-sure analysis under weaker analytic hypotheses.

Load-bearing premise

The load-bearing premise is Assumption 3.1(d): there is a fixed level $D_\eta$ such that any point whose gradient norm is smaller than $\eta$ must have function value below $f^* + D_\eta$; if a smooth coercive loss contained a long flat region at a higher function value, the up-crossing and boundedness arguments would fail.

Editorial extensions

If this is right

  • Schedules $\epsilon_t = 1/t^q$ with $q \in (1/p, 1/2]$ become covered for any $p>2$, a range where the Robbins–Monro sum $\sum_t \epsilon_t^2$ diverges.
  • Squared, exponential, and logarithmic loss functions, which are not globally Lipschitz, can enter the theorem's scope when they are smooth and coercive.
  • $L^2$ convergence of the gradient norm does not require applying dominated convergence to a Lipschitz loss; the proof shows $\mathbb{E}[\sup_t \|\nabla f(\theta_t)\|^2] < \infty$ directly.
  • The stopping-time/up-crossing machinery is advertised by the paper as a template for convergence proofs of adaptive and momentum-based stochastic optimizers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The local moment orders are tied to $p$: Assumption 3.2(d) asks for a bounded $(2p-2)$-th moment near critical values, so letting $p$ approach 2 demands almost no more than second moments locally; this suggests a trade-off between the sharpness of the step-size exponent and the order of stochastic-gradient moments one must control.
  • Assumption 3.1(d) effectively rules out long flat regions at high function values. A plausible extension would replace it by a probabilistic escape condition for such plateaus, yielding a theorem for loss landscapes with high flat critical sets.
  • Because the bounds in Lemma 3.2 and Lemma 3.3 are quantitative (via Young's and Burkholder inequalities), the method could be pushed to give explicit rates for $\mathbb{E}\|\nabla f(\theta_t)\|^2$ in terms of $p$, $L$, $G$, and the tail of $\sum_t \epsilon_t^p$.
  • The proof never uses the full distribution of the noise beyond the martingale difference $M_t$, so the same up-crossing argument may transfer to settings with biased but controllable gradient noise, e.g., asynchronous or compressed SGD.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies asymptotic convergence of SGD in non-convex smooth optimization under step sizes satisfying sum_t epsilon_t = infinity and sum_t epsilon_t^p < infinity for some p > 2. It claims to remove the global Lipschitz continuity assumption on the loss and to replace global high-order moment bounds with local ones, using coercivity, a new boundedness-near-critical-points assumption (Assumption 3.1(d)), a weak growth condition on second moments, and local p-th and (2p-2)-th moment conditions (Assumption 3.2(c)-(d)). The main results are almost sure convergence of f(theta_t) to a critical value (Theorem 3.1), almost sure convergence of ||grad f(theta_t)|| to zero (Theorem 3.2) via the ODE method of Benaim, and L2 convergence (Theorem 3.3). The proof is built on a stopping-time up-crossing argument and a recursive bound on the gradient quadratic variation.

Significance. If the results hold, they constitute a meaningful generalization of Mertikopoulos et al. (2020): the stopping-time framework avoids the global Lipschitz loss assumption and uses only local high-order moment control, and the relaxed step-size condition (p>2) is of interest. The paper is explicit that Assumption 3.1(d) is a nonstandard premise, and the proof is largely self-contained. However, the central up-crossing engine contains a genuine gap in Lemma 3.4, and an indicator identity in Eq. (4) requires an additional choice that the proof does not justify; these issues are repairable in context but currently leave the main theorems unsupported as written.

major comments (3)
  1. [Section 3.3, proof of Lemma 3.4] The proof of Lemma 3.4 begins by asserting, by continuity, that there exists z<x with min_{theta in f^{-1}([z,x])} ||grad f(theta)|| >= delta_{x,y}/2. This is not justified under the lemma's stated hypotheses, which exclude Assumption 3.1(c) (coercivity) and (d). The lemma's hypothesis gives a positive gradient lower bound only on f^{-1}([x,y)), not below x, and without coercivity f^{-1}([z,x]) need not be compact. The asserted property can fail even for smooth coercive functions satisfying Assumption 3.1(d): take coercive f with local minima at values f*+D_eta-1/k; for x=D_eta, the minimum of ||grad f|| on f^{-1}([z,D_eta]) is 0 for every z<D_eta. This is exactly the situation that can arise in Theorem 3.3, where the lemma is applied with x=M and M can equal D_eta. Consequently the base interval [z0,z1] in Eq. (13) may contain critical points, and the finiteness of limsup [grad f]^1_{T,x,y} is not established. Since Lemma 3.4 is used in the up-crossing bound of Theorem 3.1 and in the L2 bound of Theorem 3.3, this is a load-bearing gap. The argument can be repaired in the context of the theorems by using coercivity and choosing a buffer below h1 that avoids f(Crit(f)), but Lemma 3.4 as stated and proved is not sound.
  2. [Section 3.3, Eq. (4)] In bounding Sigma_{T,mu,1}, the proof uses the identity I_{f(theta_{mu_{3k-2,T}-1})-f*<D_eta}=1 for all k>=2. This identity requires h1<D_eta, because mu_{3k-2,T}-1 can only be guaranteed to satisfy f-f*<h1. The construction of H_x=[h1,h2] subset I_{x,delta} with x in [0,D_eta) does not impose h1<D_eta; for some admissible choices, h1>=D_eta. The proof should explicitly choose H_x with h1<D_eta, which is possible because x<D_eta, or handle the case h1>=D_eta separately. Without this, Eq. (4) and the resulting recursion for Sigma_{T,mu} do not cover all intervals considered in Statement (b).
  3. [Section 3.3, Statement (b), after Sard's theorem] The text claims that 'by the coercivity assumption, f(Crit(f)) is compact.' This is false: a coercive smooth function such as f(x)=x^2+sin(x^2) has critical values tending to +infinity, so f(Crit(f)) is unbounded. What is needed for the argument is not compactness but that f(Crit(f)) has empty interior, so that any open interval contains a smaller closed interval avoiding it. This follows from Sard's theorem together with closedness of f(Crit(f)), which holds because coercivity makes f proper; alternatively one can restrict to a bounded value range. The current justification is incorrect, although the intended conclusion is repairable. Please correct the proof.
minor comments (5)
  1. [Section 3.4.1, Proposition 2] Proposition 2 states the ODE as theta_dot = -f(theta), but f is the scalar loss; the ODE method is applied to the gradient flow theta_dot = -grad f(theta), or the proposition should use the vector field F. In Phase III, the text should read theta_dot = -grad f(theta) rather than theta_dot = -f(theta).
  2. [Section 3.3, Eq. (13)] In the second term of the displayed backward iteration, the factor C2(ceil(p)-1-j, z_j, z_{j+1}) uses the summation index j inconsistently with the outer sum over i; the backward recursion appears to require C2(ceil(p)-1-i, z_i, z_{i+1}). Please correct the indices.
  3. [Assumption 3.1 and Section 3.3] Assumption 3.1 says f is 'd-times differentiable' and the proof invokes Sard's theorem. Standard Sard for f: R^d -> R requires C^d differentiability for d>=1, so the differentiability hypothesis should be stated as C^d; the current wording is ambiguous and weaker than what the proof uses.
  4. [Section 3.4.1, Phase II] In the proof of Theorem 3.2, the sentence 'there exists a finite time T0 < +infinity a.s.' should specify that T0 is path-dependent and depends on delta; as written it could be read as a uniform stopping time.
  5. [Throughout Sections 3.3 and 3.4.1] There are typographical errors that should be fixed: 'corecivity' should be 'coercivity' and 'Cric(f)' should be 'Crit(f)'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence theorems are derived from the stated assumptions using standard external results, and the only self-citation is contextual and not load-bearing.

full rationale

The paper's derivation chain is self-contained and does not reduce any claimed result to its inputs. Theorem 3.1 is proved via two statements: liminf||grad f(theta_t)||=0 follows from the descent lemma and the divergence of sum epsilon_t, while the finite-upcrossing bound follows from Doob's stopping theorem, Burkholder/AM-GM inequalities, the local p-th moment bound, and sum epsilon_t^p<infinity. Theorem 3.2 verifies the three hypotheses of the ODE-method Proposition 2 (Benaim 2006), using Sard's theorem plus coercivity for the nowhere-dense condition. Theorem 3.3 uses the a.s. result plus an E[sup ||grad f||^2] bound obtained from Lemma 3.4 and the local moment assumptions. No parameter is fitted to data, no auxiliary quantity is renamed as a prediction, and no theorem is invoked from the authors' own prior work to force a conclusion. The only self-citation, Jin et al. (2022), appears in the related-work comparison and is not used to justify any theorem. The skeptical concern about Lemma 3.4's 'By continuity, it is easy to prove...' existence of z<x is a potential correctness gap in the proof, not a circularity: the lemma does not assume its own conclusion, and the asserted auxiliary fact is an intermediate claim, not an input equivalent to the lemma's conclusion. Therefore no circular step is exhibited, and the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no free parameters fitted to data and no new theoretical entities. It relies on standard external theorems (Sard, Benaim's ODE method, Doob, Burkholder) and on a nonstandard assumption (3.1(d)) that is invented for this proof.

assumptions (5)
  • standard math Sard's theorem: the image of critical points under f has Lebesgue measure zero
    Used in Theorem 3.1 proof and Theorem 3.2 Phase III to show f(Crit(f)) is nowhere dense, enabling the up-crossing interval selection.
  • standard math Benaim's ODE method (Proposition 2) for almost sure convergence of stochastic approximations
    Invoked in Theorem 3.2 proof to conclude that limit points of SGD iterates are fixed points of the ODE θ̇ = -∇f(θ).
  • standard math Doob's stopping theorem and Burkholder's inequality for martingales
    Used throughout the up-crossing and noise-control estimates.
  • ad hoc to paper Assumption 3.1(d): boundedness near critical points
    Nonstandard joint condition on gradient and function value used to prevent divergence and bound up-crossing intervals; not a classical assumption.
  • domain assumption Assumption 3.2(c)-(d): local boundedness of p-th and (2p-2)-th moments of stochastic gradients
    Imposed locally near critical points or sublevel sets to control high-order noise without global moment bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods." pith.science (2026). https://pith.science/paper/3WO6ZWTH

@misc{pith2026250412601,
  author       = {Pith},
  title        = {Pith review of: Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3WO6ZWTH}},
  note         = {Machine review of arXiv:2504.12601}
}
abstract

Stochastic Gradient Descent (SGD) is widely used in machine learning research. Previous convergence analyses of SGD under the vanishing step-size setting typically require Robbins-Monro conditions. However, in practice, a wider variety of step-size schemes are frequently employed, yet existing convergence results remain limited and often rely on strong assumptions. This paper bridges this gap by introducing a novel analytical framework based on a stopping-time method, enabling asymptotic convergence analysis of SGD under more relaxed step-size conditions and weaker assumptions. In the non-convex setting, we prove the almost sure convergence of SGD iterates for step-sizes $ \{ \epsilon_t \}_{t \geq 1} $ satisfying $\sum_{t=1}^{+\infty} \epsilon_t = +\infty$ and $\sum_{t=1}^{+\infty} \epsilon_t^p < +\infty$ for some $p > 2$. Compared with previous studies, our analysis eliminates the global Lipschitz continuity assumption on the loss function and relaxes the boundedness requirements for higher-order moments of stochastic gradients. Building upon the almost sure convergence results, we further establish $L_2$ convergence. These significantly relaxed assumptions make our theoretical results more general, thereby enhancing their applicability in practical scenarios.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 11 canonical work pages

  1. [1]

    Toward a precise smoothness hypothesis in sard’s theorem

    Sean M Bates. Toward a precise smoothness hypothesis in sard’s theorem. Proceedings of the American Mathematical Society, 117 0 (1): 0 279--283, 1993

    work page 1993

  2. [2]

    Dynamics of stochastic approximation algorithms

    Michel Bena \" m. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pages 1--68. Springer, 2006

    2006

  3. [3]

    Adaptive algorithms and stochastic approximations, volume 22

    Albert Benveniste, Michel M \'e tivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012

    work page 2012

  4. [4]

    Stochastic approximation: a dynamical systems viewpoint, volume 9

    Vivek S Borkar and Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 9. Springer, 2008

    work page 2008

  5. [5]

    Large-scale machine learning with stochastic gradient descent

    L \'e on Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, pages 177--186. Springer, 2010

    2010

  6. [6]

    Optimization methods for large-scale machine learning

    L \'e on Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60 0 (2): 0 223--311, 2018

    2018

  7. [7]

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming

    Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23 0 (4): 0 2341--2368, 2013

    2013

  8. [8]

    Understanding the role of momentum in stochastic gradient methods

    Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

Show all 21 references
  1. [9]

    A practical guide to training restricted boltzmann machines

    Geoffrey E Hinton. A practical guide to training restricted boltzmann machines. In Neural Networks: Tricks of the Trade: Second Edition, pages 599--619. Springer, 2012

    2012

  2. [10]

    Revisit last-iterate convergence of msgd under milder requirement on step size

    Ruinan Jin, Xingkang He, Lang Chen, Difei Cheng, and Vijay Gupta. Revisit last-iterate convergence of msgd under milder requirement on step size. In Proceedings of the 36th International Conference on Neural Information Processing Systems, pages 36559--36570, 2022

    2022

  3. [11]

    Adam: A method for stochastic optimization

    Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

    2014 arXiv

  4. [12]

    Stochastic approximation algorithms and applications, vol

    HJ Kushner and GG Yin. Stochastic approximation algorithms and applications, vol. 35 of stoch. modelling and appl. Prob., Springer-Verlag, New York, 1997

    1997

  5. [13]

    Efficient backprop

    Yann LeCun, L \'e on Bottou, Genevieve B Orr, and Klaus-Robert M \"u ller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9--50. Springer, 2002

    2002

  6. [14]

    Analysis of recursive stochastic algorithms

    Lennart Ljung. Analysis of recursive stochastic algorithms. IEEE transactions on automatic control, 22 0 (4): 0 551--575, 1977

    1977

  7. [15]

    Theory for the user

    Lennart Ljung et al. Theory for the user. System identification, 1987

    1987

  8. [16]

    On the almost sure convergence of stochastic gradient descent in non-convex problems

    Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure convergence of stochastic gradient descent in non-convex problems. Advances in Neural Information Processing Systems, 33: 0 1117--1128, 2020

    2020

  9. [17]

    Sgd and hogwild! convergence without the bounded gradients assumption

    Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richt \'a rik, Katya Scheinberg, and Martin Tak \'a c. Sgd and hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, pages 3750--3758. PMLR, 2018

    2018

  10. [18]

    A stochastic approximation method

    Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22 0 (3): 0 400--407, 1951

    1951

  11. [19]

    An overview of gradient descent optimization algorithms

    Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747, 2016

    2016 arXiv

  12. [20]

    The measure of the critical values of differentiable maps

    Arthur Sard. The measure of the critical values of differentiable maps. Bulletin of the American Mathematical Society, 48 0 (12): 0 883--890, 1942

    1942

  13. [21]

    Towards theoretically understanding why sgd generalizes better than adam in deep learning

    Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoretically understanding why sgd generalizes better than adam in deep learning. Advances in Neural Information Processing Systems, 33: 0 21285--21296, 2020

    2020

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.