{"id":"dddc385c-a921-4256-818e-914c4145b9bc","arxiv_id":"2504.12601","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under step sizes with infinite sum and finite p-th power sum for p>2, SGD's function values and gradients converge almost surely to a critical point in non-convex smooth problems.","lead":"This paper proves that SGD converges almost surely and in L2 even when the step-size decays more slowly than the classic Robbins-Monro condition allows, provided a few geometric assumptions hold. The result justifies using step schedules such as 1/sqrt(t) in non-convex problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.4's proof assumes a z<x with positive gradient lower bound on f^{-1}([z,x]); this fails when critical values accumulate at x from below, undermining Theorems 3.1 and 3.3.","rationale":"The reader correctly identified a gap in the proof of Lemma 3.4 and flagged Assumption 3.1(d) as load-bearing. Our stress-test sharpens this: the specific flaw is the existence of a z<x with a uniform gradient lower bound on f^{-1}([z,x]). This step is essential for initializing the recursive inequality (13) in Lemma 3.4, which is then used to bound up-crossings in Theorem 3.1 and to bound the quadratic variation term in Theorem 3.3. The failure mode is not merely an artifact of missing coercivity; even under the full Assumptions 3.1, critical values may accumulate at Dη from below, and the troublesome case x=Dη is exactly what is needed in Theorem 3.3. Because the reader already gave a CONDITIONAL verdict, our more specific concern does not require a change in verdict, but it does strengthen the condition: the authors must either repair Lemma 3.4 or add an assumption ruling out such accumulation. We did not find a counterexample to the theorem's statement, so the appropriate disposition remains conditional acceptance pending a correct proof.","tokens_in":36891,"tokens_out":14132,"duration_ms":137024,"concrete_test":"Take a smooth coercive f: R→R satisfying Assumptions 3.1(a)-(c),(d) with a sequence of local minima θ_k for which f(θ_k)=Dη - 1/k, all with gradient zero. Set x=Dη, y=+∞, and δ_{x,y}=η (the bound from Assumption 3.1(d)). For every z<Dη, θ_k∈f^{-1}([z,Dη]) for all k large enough, so min_{θ∈f^{-1}([z,Dη])} ||∇f(θ)|| = 0 < η/2. This directly contradicts the claimed z in the proof of Lemma 3.4. Compute the quantity [∇f]^1_{T,Dη,+∞} from Eq. 10 for this f and verify whether it remains bounded (if it does, the lemma may be true by another route; if not, the theorem's conclusion fails).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.4 (Section 3.3) is the engine of the up-crossing argument and of the L2 bound. Its proof begins with the assertion: \"By continuity, it is easy to prove that there exists a constant z < x such that min_{θ∈f^{-1}([z,x])} ||∇f(θ)|| ≥ δ_{x,y}/2.\" This assertion is not justified by the stated assumptions (Assumption 3.1(a)-(b), Assumption 3.2(a)-(c)). It requires that x is not a right-accumulation point of critical values and that f^{-1}([z,x]) is compact; the lemma statement omits coercivity, and even with coercivity plus Assumption 3.1(d), critical values can accumulate at Dη from below. For example, a smooth coercive f with local minima at values Dη - 1/k satisfies Assumption 3.1(d) (these are critical points with f-f*<Dη) but for x=Dη there is no z<Dη for which f^{-1}([z,Dη]) avoids critical points; the minimum of ||∇f|| over that set is 0. This exact case arises in Theorem 3.3, where Lemma 3.4 is invoked with x=M=max{f(θ1)-f*, Dη}, so x=Dη is possible. The inequality (13) then has no starting point, and the claimed finiteness of limsup [∇f]^1_{T,x,y} is unproved. Consequently the a.s. convergence of f(θ_t) (Theorem 3.1) and the L2 convergence (Theorem 3.3) are not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":37277,"tokens_out":19060,"duration_ms":200340,"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":[{"comment":"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.","section":"Section 3.3, proof of Lemma 3.4"},{"comment":"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).","section":"Section 3.3, Eq. (4)"},{"comment":"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.","section":"Section 3.3, Statement (b), after Sard's theorem"}],"minor_comments":[{"comment":"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).","section":"Section 3.4.1, Proposition 2"},{"comment":"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.","section":"Section 3.3, Eq. (13)"},{"comment":"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.","section":"Assumption 3.1 and Section 3.3"},{"comment":"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.","section":"Section 3.4.1, Phase II"},{"comment":"There are typographical errors that should be fixed: 'corecivity' should be 'coercivity' and 'Cric(f)' should be 'Crit(f)'.","section":"Throughout Sections 3.3 and 3.4.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is likely salvageable: the main theorems appear plausible, and the gaps are technical rather than conceptual. I recommend sending the paper back for major revision with emphasis on Lemma 3.4 and on the construction of H_x. The authors should either restate Lemma 3.4 under the full Assumption 3.1 with a correct proof of the buffer interval, or modify the proofs of Theorems 3.1 and 3.3 so that the lemma's hypotheses and proof conditions are satisfied. The incorrect compactness claim for f(Crit(f)) should also be corrected. The relaxed step-size and local-moment framework is a genuine contribution if these gaps can be closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is the stopping-time / up-crossing framework for proving a.s. convergence of SGD under step sizes satisfying sum ε_t = ∞ and sum ε_t^p < ∞ for some p > 2, without assuming global Lipschitz continuity of the loss. That is a real extension of Mertikopoulos et al. (2020) and Jin et al. (2022), and the recursive quadratic-variation bound in Lemma 3.3 is a clever piece of work. If the proof were sound, this would be a significant contribution to the non-convex SGD theory. There are two soft spots. The first is in Eq. (4) of Theorem 3.1: the step that uses I_{f(θ_{µ_{3k-2,T}-1})-f*<Dη} = 1 for all k ≥ 2 is not justified when h1 ≥ Dη. This looks fixable — since x < Dη, you can choose h1 and h2 inside (x, x+δ) ∩ [0, Dη), so I won't dwell on it. The second is more serious. Lemma 3.4 claims that, from inf_{θ: f(θ)∈[x,y)} ‖∇f(θ)‖ ≥ δ_{x,y} > 0, there exists z < x with min over f^{-1}([z,x]) of ‖∇f(θ)‖ ≥ δ_{x,y}/2. That implication is false as stated: critical values can accumulate at x from below, and then for every z < x the set f^{-1}([z,x]) contains points with gradient arbitrarily close to 0. For Theorem 3.1 you could possibly choose h1 in a gap of the critical-value set (which exists by Sard + nowhere dense), but for Theorem 3.3 the lemma is invoked with x = M = max{f(θ1)-f*, Dη}. When M = Dη — which can happen — Assumption 3.1(d) explicitly allows critical values arbitrarily close to Dη from below. So the recursive bound in Eq. (13) has no starting point, and the claimed L2 convergence is not established. This is a load-bearing flaw, not a typo. The paper also relies on a nonstandard assumption (3.1(d)) that forces all critical points below Dη in function value; that is strong and should be acknowledged more prominently. No code or data are involved, so the proofs are the whole story, and the citation pattern looks appropriate. The paper deserves a serious referee, but the authors should be asked to fix Lemma 3.4 or add an explicit non-accumulation condition. As written, I would not cite it.","headline":"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.","tokens_in":814,"tokens_out":910,"would_cite":false,"duration_ms":69694,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","90C15","90C26","60G40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["stochastic gradient descent","almost sure convergence","non-convex optimization","stopping time method","relaxed step sizes","L2 convergence","martingale","stochastic approximation"],"falsifier":"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.","tokens_in":36690,"feed_emoji":"📉","tokens_out":9895,"duration_ms":98907,"temperature":0.7,"pith_summary":"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.","feed_headline":"New proof: SGD converges with step sizes as slow as 1/√t","feed_subtitle":"Relaxed step sizes and no global Lipschitz condition widen the practical guarantees for non-convex SGD.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces SGD and the classical summability conditions whose scope the paper relaxes.","marker":"Robbins and Monro (1951)"},{"why":"Closest prior almost-sure convergence result under global Lipschitz continuity and global moment bounds; the paper weakens both.","marker":"Mertikopoulos et al. (2020)"},{"why":"Supplies the ODE pseudotrajectory proposition used to convert value convergence into gradient-norm convergence.","marker":"Benaïm (2006)"},{"why":"Critical values of a differentiable map have Lebesgue measure zero, used to choose intervals avoiding critical values.","marker":"Sard (1942)"},{"why":"Sharpens Sard's theorem to the smoothness class used in the proof.","marker":"Bates (1993)"},{"why":"Standard reference for the L-smooth descent inequality and unbiased gradient assumptions reused in the proof.","marker":"Bottou (2010)"}],"fun_headline_variants":["SGD converges even with very slow step-size decay","New proof relaxes step-size conditions for SGD","Stopping-time method widens SGD convergence guarantees","No global Lipschitz needed for SGD in non-convex"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["SGD converges even with very slow step-size decay","New proof relaxes step-size conditions for SGD","Stopping-time method widens SGD convergence guarantees","No global Lipschitz needed for SGD in non-convex"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00026,"raw_usage":{"total_tokens":1625,"prompt_tokens":1018,"completion_tokens":607,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":634,"completion_tokens_details":{"reasoning_tokens":544}},"tokens_in":634,"tokens_out":607,"duration_ms":6309,"temperature":1.0,"reasoning_tokens":544,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:28:12.459665+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A stochastic approximation method","cited_arxiv_id":null,"evidence_quote":"Introduces SGD and the classical summability conditions whose scope the paper relaxes."},{"cited_title":"The measure of the critical values of differentiable maps","cited_arxiv_id":null,"evidence_quote":"Critical values of a differentiable map have Lebesgue measure zero, used to choose intervals avoiding critical values."},{"cited_title":"Toward a precise smoothness hypothesis in sard’s theorem","cited_arxiv_id":null,"evidence_quote":"Sharpens Sard's theorem to the smoothness class used in the proof."}],"review_version":1}