{"id":"615531f1-d692-402d-aa4c-0d5512f827ee","arxiv_id":"2506.23335","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A new concentration lemma for almost super-martingales yields a stopping-time convergence rate of O(log(tau)/sqrt(tau)) for a momentum SGD variant, removing one logarithmic factor.","lead":"Stochastic optimization theory usually guarantees error at a fixed iteration count, but real algorithms stop when progress looks good. This paper proves a high-probability error bound at such random stopping times, improving the rate from log^2(tau)/sqrt(tau) to log(tau)/sqrt(tau).","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's step after 'Since γ1S(k)≥...' compares exponentials without the needed M(k)≥0; as written the inequality in (18) is false, though it is repairable by restricting to the event.","rationale":"The paper's central claim is a high-probability stopping-time rate of log(τ)/√τ for a momentum SGD variant, obtained through a new large-deviation lemma for almost supermartingales. The proof structure is coherent: the Lyapunov function, the step-size choice, and the reduction of the stopping-time statement to an all-k bound via Lemma 3 are all explicit and internally consistent. The sub-Gaussian noise assumption (Assumption 3) is strong but standard and explicitly stated, so I do not treat it as a correctness defect; it restricts scope rather than invalidating the argument. The real soft spot is in the proof of Lemma 1 itself. The comparison after 'Since γ1S(k) ≥...' requires M(k) ≥ 0, which is not shown and is not generally true pointwise. The reader's rationale flags this same location, but the reader's formal 'weakest_assumption' names Assumption 3 instead; I see the proof gap as more immediately load-bearing, hence 'partial' agreement. The gap appears repairable with an event-restricted argument, which is why I do not recommend changing the conditional verdict. A secondary concern is that the proof of Lemma 4 combines inequalities (25) and (26) in a way that does not obviously yield the stated exp(3λ²/4) bound; this is likely fixable and is not the primary bridge, so I leave it as secondary. Since the paper is proof-only, with no machine-checked verification or reproducible code, the written proof gaps are the appropriate focus for a conditional acceptance.","tokens_in":14093,"tokens_out":27304,"duration_ms":278013,"concrete_test":"Write out the proof of (18) replacing the unconditional inequality with the event-restricted version: define A_k = {exp(BM(k)/γ2 − Bσ²γ1S(k)) ≥ exp(BE0+log(1/β))}. Show (i) A_k ⇒ M(k)>0, and (ii) for M(k)>0 the inequality with N^{B/γ2}(k) holds. Then verify {sup_k A_k} ⊆ {sup_k N^{B/γ2}(k) ≥ exp(BE0+log(1/β))}. If both hold, Lemma 1 stands with a one-sentence addition; if not, the central theorem lacks proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is the derivation of (18) in the proof of Lemma 1. The paper asserts exp(BM(k)/γ2 − Bσ²γ1S(k)) ≤ exp(Bγ2,k M(k)/γ2 − BΣ a_lσ²S(l−1)) = N^{B/γ2}(k), citing only γ1S(k) ≥ Σ a_lS(l−1). The S-terms do compare in the right direction, but the M-terms require Bγ2,k M(k)/γ2 ≥ BM(k)/γ2, i.e. M(k) ≥ 0. The proof never establishes M(k) ≥ 0; since S(k)=Σ a_l||θ_l||² is nonnegative and M(k)=E(k)−S(k), M(k) is in general signed. Thus the displayed inequality is not a pointwise consequence of the product bound. This is not cosmetic: (18) is the only bridge from the supermartingale N to the event controlling M−σ²γ1γ2S, and the final E(k) bound is the sum of that event and the S(k) tail event. If the bridge fails, the sup bound on E(k) is unsupported. The gap is plausibly repairable: on the event whose probability is being bounded in (18), the exponent exceeds BE0+log(1/β)>0, while the S contribution is nonpositive, forcing M(k)>0; restricting the inclusion in (18) to that event would restore the argument. But this extra event-restriction step is absent, so the proof as written is incomplete.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies high-probability convergence of a stochastic gradient descent with momentum (SGDM) variant, with guarantees expressed in terms of stopping times. Under convex L-smooth objectives and sub-Gaussian gradient noise, it claims an O(log(τ)/√τ) high-probability error bound for any {x_k}-stopping time τ, improving the O(log^2(τ)/√τ) rate that the authors show follows from union-bounding existing per-iterate bounds. The proof introduces a Lyapunov function E(k), a one-step increment inequality (Lemma 2), and a new large-deviation lemma for almost supermartingales (Lemma 1). It also proves an equivalence between simultaneous all-iterate bounds and stopping-time bounds (Lemma 3). The central result is stated as Theorem 1, with a parameterized variant in Proposition 1.","tokens_in":14342,"tokens_out":14825,"duration_ms":134244,"significance":"If correct, the paper closes a logarithmic gap in stopping-time convergence rates for stochastic first-order methods, a topic of practical relevance because algorithms are often terminated by data-dependent rules. The comparison with prior work is quantitative and the claimed improvement is sharp and easily stated. The proof strategy is coherent: the Lyapunov function is natural, the decomposition into a supermartingale and a sub-Gaussian tail term is elegant, and the auxiliary large-deviation lemma for almost supermartingales could be of independent interest. No fitted parameters or circular reductions are involved, and the main theorem yields a concrete, falsifiable rate. However, the proof of Lemma 1 contains a missing event-restriction step at equation (18), and the auxiliary lemmas are stated under an i.i.d. assumption that does not formally cover their application. These are local, repairable issues rather than fundamental obstructions, but they must be fixed before the result can be accepted.","major_comments":[{"comment":"The derivation of the key inclusion after 'Since γ1S(k)≥...' is not valid as written. The difference between the right-hand and left-hand exponents in the displayed comparison equals B(∏_{l=k+1}∞(1+a_lσ^2)−1)M(k)/γ2 + Bσ^2(γ1S(k)−∑_{l=1}^k a_lS(l−1)). The second term is nonnegative, but the first term has the sign of M(k), and M(k)=E(k)−S(k) is not shown to be nonnegative. Consequently the pointwise inequality exp(BM(k)/γ2−Bσ^2γ1S(k)) ≤ N^{B/γ2}(k) is false on paths with M(k)<0. This step is the only bridge between the supermartingale N^{B/γ2} and the event controlling M(k)−σ^2γ1γ2S(k), so the final high-probability bound on E(k) is unsupported as the proof stands. The gap is repairable: on the event in the left-hand side of (18), the exponent is at least BE(0)+log(1/β)>0, and since S(k)≥0 this forces M(k)>0, so restricting the pointwise comparison to that event would restore the argument. This event-restriction step is absent from the manuscript and should be added explicitly.","section":"Section 2.1, Eq. (18)"},{"comment":"Both auxiliary lemmas are stated for a sequence of i.i.d. random variables θ_1,...,θ_k, but the sequence θ_k=∇f(x_k)−g(x_k,ξ_k) arising in the proof of Theorem 1 is not i.i.d. because x_k depends on the past noise. The proofs of the lemmas do not actually use independence; they use only the stated conditional properties (zero conditional mean, boundedness, and conditional sub-Gaussianity). The intended application is therefore valid after replacing 'i.i.d.' by an adapted sequence in the lemma statements, but as written the hypotheses do not formally cover the application. This should be corrected in the statements, since Theorem 1 relies on Lemma 4 for the verification of the almost supermartingale condition in Lemma 1.","section":"Appendix A, Lemma 4 and Lemma 5"}],"minor_comments":[{"comment":"There are several typographical errors, including 'differncing' for 'differencing' and 'conditonal MGF' for 'conditional MGF'; these should be corrected in a revision.","section":"Section 2, Lemma 2 proof"},{"comment":"The phrase 'tightest high-probability convergence result rate' in Section 1.4 is an overclaim unless a matching lower bound is established; 'best known' would be more precise.","section":"Table 1 and Section 1.4"},{"comment":"The notation ≲ is used informally in equations (1)–(3) and (23)–(24); the authors may wish to state the precise polynomial-in-log(1/β) dependencies, since the comparison with Theorem 1 depends on the log factor.","section":"Section 1.2 and Section 3"},{"comment":"In the statement of Proposition 1, the constant C0 absorbs all problem-dependent factors such as L and σ, while hσ(ε) is exhibited explicitly; this is acceptable but the sentence defining C0 should state unambiguously that C0 is independent of k, β, and ε, and may depend on L and σ.","section":"Proposition 1"}],"recommendation":"major_revision","confidential_remarks":"The main result is plausible and the proof strategy is sound, but the missing event-restriction in Lemma 1's proof is a genuine logical gap in a load-bearing step. The fix is local and the underlying argument appears repairable, so I recommend major revision rather than rejection. The i.i.d. mismatch in Lemmas 4 and 5 is also easy to fix by restating the hypotheses. I would ask the authors to add the event-restriction argument and to correct the lemma statements before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper does something real—it removes one logarithm from the high-probability stopping-time bound for a momentum SGD variant, and it contributes a maximal inequality for almost supermartingales that should be useful elsewhere. The main proof has a specific, localized gap that is likely repairable, but as written the key step in Lemma 1 does not go through without an extra argument.\n\nWhat is new: the stopping-time formulation is not just a restatement. Lemma 3's equivalence between uniform-in-k and stopping-time bounds is elementary but makes the contribution precise, and Section 3 correctly shows the prior union-bound route produces log^2 τ. The supermartingale construction in Lemma 1 is a genuine extension of Robbins–Siegmund to high-probability tails under sub-Gaussian noise. The application to SGDM is explicit: step sizes, Lyapunov function, and constants are all stated. No fitted parameters, no circular dependence on the claimed result. The comparison to [32,33] is careful and honest.\n\nWhere it is soft: the proof of Lemma 1, specifically the transition to (18). The paper asserts exp(BM(k)/γ2 − Bσ²γ1S(k)) ≤ N^{B/γ2}(k) using only γ1S(k) ≥ Σ a_l S(l−1). That S-comparison is correct, but the M-terms only compare in the right direction if M(k)≥0, and M(k)=E(k)−S(k) is signed in general. The proof never establishes M(k)≥0. The step is not cosmetic—(18) is the bridge from the supermartingale N to the event bounding M−σ²γ1γ2S. The good news is the gap is plausibly repairable: on the event being bounded, the exponent exceeds BE(0)+log(1/β)>0 while the S-term is nonpositive, forcing M(k)>0, so restricting the inclusion to that event would restore the argument. But that step is absent, so the written proof is incomplete. I'd want the authors to fix that before signing off.\n\nThe sub-Gaussian noise assumption (Assumption 3) is load-bearing; with heavy-tailed noise the result does not follow. That is worth stating prominently, though it is standard for this literature.\n\nBottom line: this is a genuine but incremental advance. The lemma is the most valuable part. A serious referee should engage; the paper deserves revision rather than rejection. If I worked in stochastic optimization, I'd cite it once the gap is closed.","headline":"A real but incremental advance: the paper removes one logarithm from stopping-time high-probability bounds for a momentum SGD variant, with a reusable maximal inequality for almost supermartingales, but the proof of Lemma 1 has a localized gap that needs an extra event-restriction step before it is fully correct.","tokens_in":14923,"tokens_out":4101,"would_cite":true,"duration_ms":40322,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","60G40","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a momentum variant of stochastic gradient descent achieves a high-probability stopping-time convergence rate of order log(τ)/√(τ) for smooth convex objectives with sub-Gaussian gradient noise, removing the extra…","keywords":["stopping time convergence","stochastic gradient descent with momentum","high-probability bounds","almost super-martingales","large deviations","smooth convex optimization","sub-Gaussian noise"],"falsifier":"Take $f(x)=\\|x\\|^2$, $L=2$, run SGDM (4) with $\\eta_k=1/(16L^2\\log^2(k+2))$ and i.i.d. Gaussian noise $\\theta_k$ of variance $\\sigma^2$, and estimate the empirical rate of the event that $\\sup_{k\\le 10^6}(f(x_k)-f^*)\\sqrt{k+1}/\\log(k+2)$ exceeds $C_1+C_2\\log(1/\\beta)$. If the frequency stays at or below $2\\beta$ for constants fitted to the theorem, the claim survives; a sharper check is algebraic: at $k=1$, compute both sides of the conditional moment inequality $E[\\exp(t\\sqrt{a_1}\\langle\\theta_1,\\varphi_1\\rangle)\\mid F_0]\\le\\exp(a_1\\sigma^2tE(0))$ for $t=1$ under any sub-Gaussian law, since a violation would locate a gap in Lemma 1's application.","tokens_in":13844,"feed_emoji":"⏱️","tokens_out":15908,"duration_ms":139661,"temperature":0.7,"pith_summary":"Algorithms are terminated adaptively in practice, often by stopping rules such as \"stop when progress is small,\" but most convergence theory only covers non-random iteration counts. This paper attacks the gap directly: it proves a high-probability bound that holds simultaneously for every iterate, which by an equivalence lemma is exactly the same as holding for any stopping time adapted to the algorithm. For smooth convex problems with sub-Gaussian gradient noise, the bound has the form $C\\log(\\tau+2)/\\sqrt{\\tau+1}$, improving the previously derived $\\log^2(\\tau)/\\sqrt{\\tau}$ stopping-time rate. The engine is a new large-deviation lemma for almost super-martingales, which the authors propose as a reusable tool. If the result is correct, adaptive early-stopping rules for stochastic momentum methods inherit the same near-optimal rate as fixed-horizon runs.","feed_headline":"Stopping-time stochastic optimization drops from log²τ to log τ","feed_subtitle":"A momentum SGD variant matches pointwise guarantees for every adaptive stopping time, with probability at least 1−2β.","key_machinery":"The central object is the discrete Lyapunov function $E(k)$ defined above, together with Lemma 1, a large-deviation extension of the classical almost-super-martingale bound. An almost super-martingale is a nonnegative process whose conditional expected increment is controlled by a summable drift plus a negligible term; Lemma 1 shows that if the increments are conditionally sub-Gaussian, the whole process stays below a threshold with high probability. Lemma 2 proves the algorithm's Lyapunov drift has exactly that structure: $E(k)-E(k-1)\\le a_k\\|\\theta_k\\|^2+\\sqrt{a_k}\\langle\\theta_k,\\varphi_k\\rangle$ with $a_k=16\\eta_k/k$, noise $\\theta_k=\\nabla f(x_k)-g(x_k,\\xi_k)$, and an $F_{k-1}$-measurable $\\varphi_k$. The choice $\\eta_k=1/(16L^2\\log^2(k+2))$ makes $\\sum_k a_k$ finite, which turns the drift bound into the $\\log\\tau/\\sqrt{\\tau}$ rate; the final tail argument uses a supermartingale maximal inequality.","core_discovery":"Under Assumptions 1--3 ($f$ convex and $L$-smooth with finite minimum; stochastic gradients unbiased with bounded variance and conditionally sub-Gaussian noise), the SGDM variant defined by (4) with step-size $\\eta_k=1/(16L^2\\log^2(k+2))$ satisfies, for every $\\beta\\in(0,1/2)$ and every $\\{x_k\\}$-stopping time $\\tau$, $P(f(x_\\tau)-f^*\\le (C_1+C_2\\log(1/\\beta))\\log(\\tau+2)/\\sqrt{\\tau+1})\\ge 1-2\\beta$, where $C_1,C_2$ depend only on problem parameters and the starting point. The proof works through a Lyapunov function $E(k)=\\|x_{k+1}+(k+1)(x_{k+1}-x_k)-x^*\\|^2+4\\sqrt{(k+1)\\eta_k}(f(x_k)-f^*)$, whose drift is shown to fit an almost-super-martingale inequality with sub-Gaussian increments; Lemma 1 converts that drift into a sharp tail bound. A companion proposition gives, for any $\\varepsilon\\in(0,1/2)$, a rate $\\log^{(1+\\varepsilon)/2}\\tau/\\sqrt{\\tau}$ with constants involving $h_\\sigma(\\varepsilon)=\\exp(\\sigma^2\\zeta(1+\\varepsilon))(\\zeta(1+\\varepsilon))^2$. The authors state that this is the tightest stopping-time high-probability rate known for this setting.","pith_inferences":["Editorial inference: the large-deviation lemma is transferable; any stochastic approximation method that can write its Lyapunov drift as $a_k\\|\\theta_k\\|^2+\\sqrt{a_k}\\langle\\theta_k,\\varphi_k\\rangle$ with summable $a_k$ and sub-Gaussian $\\theta_k$ will automatically get a stopping-time high-probability bound of the same shape.","Editorial inference: Proposition 1's $\\varepsilon$-parameterized family suggests a finite-$\\tau$ tuning problem: as $\\varepsilon\\to0$ the exponent approaches $1/2$ but $h_\\sigma(\\varepsilon)$ blows up through the zeta factor, so a practical choice of $\\varepsilon$ should minimize the displayed bound at the horizon of interest.","Editorial inference: since Lemma 3 equates a uniform-in-$k$ high-probability bound with a stopping-time bound, future improvements in pointwise rates will carry over to stopping times automatically; the barrier broken here is therefore a proof-technique barrier rather than a fundamental computational one."],"forward_implications":["For every $\\beta\\in(0,1/2)$ and every stopping time $\\tau$, the SGD-with-momentum iterate satisfies $f(x_\\tau)-f^*\\le O(\\log(\\tau+2)/\\sqrt{\\tau+1})$ with probability at least $1-2\\beta$, under the theorem's assumptions.","The union-bound route that previously turned pointwise guarantees into stopping-time guarantees is no longer needed; the bound holds simultaneously for all $k$ from the start.","Early-stopping rules of the form $\\tau=\\min\\{k:\\|x_k-x_{k-1}\\|\\le\\epsilon\\}$ or based on objective decrease inherit the same rate, aligning theory with how stochastic algorithms are actually deployed.","Lemma 1 supplies a standalone high-probability almost-super-martingale tool that can be applied to other stochastic approximation schemes whose Lyapunov drift has the same shape.","Proposition 1 permits a trade-off between the logarithmic exponent and the constant, giving $\\log^{(1+\\varepsilon)/2}\\tau/\\sqrt{\\tau}$ for any $\\varepsilon\\in(0,1/2)$."],"supporting_citations":[{"why":"supplies the SGDM algorithm whose momentum variant is analyzed and the pointwise high-probability rate used as comparison baseline.","marker":"[25]"},{"why":"gives the textbook treatment of the classic SGDM method and its convergence properties used as the starting point.","marker":"[26]"},{"why":"provides the best prior high-probability bound from which the log-squared-over-root-tau stopping-time rate is derived; this is the baseline Theorem 1 improves.","marker":"[32]"},{"why":"contains the pointwise last-iterate high-probability bound that, after a union bound, produces the old stopping-time rate.","marker":"[33]"},{"why":"states the almost-super-martingale convergence theorem that Lemma 1 extends to a large-deviation bound.","marker":"[38]"},{"why":"supplies the supermartingale maximal inequality used to extract the exponential tail bound from the constructed supermartingale.","marker":"[43]"}],"fun_headline_variants":["Stopping-time SGD: from log² to log","Breaking the log² barrier in stopping-time rates","One log dropped: stopping-time convergence for SGD","Adaptive stopping: cut a log from the rate","Stopping-time analysis: log² becomes log"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 3, that the stochastic gradient noise is conditionally sub-Gaussian; if the noise is only bounded in variance or heavier-tailed, the moment-generating-function control of the Lyapunov drift no longer works and the high-probability stopping-time bound is not established.","fun_headline_variants_meta":{"raw":{"variants":["Stopping-time SGD: from log² to log","Breaking the log² barrier in stopping-time rates","One log dropped: stopping-time convergence for SGD","Adaptive stopping: cut a log from the rate","Stopping-time analysis: log² becomes log"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000434,"raw_usage":{"total_tokens":2216,"prompt_tokens":953,"completion_tokens":1263,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":1190}},"tokens_in":569,"tokens_out":1263,"duration_ms":12848,"temperature":1.0,"reasoning_tokens":1190,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:47:53.880217+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $f(x)=\\|x\\|^2$, $L=2$, run SGDM (4) with $\\eta_k=1/(16L^2\\log^2(k+2))$ and i.i.d. Gaussian noise $\\theta_k$ of variance $\\sigma^2$, and estimate the empirical rate of the event that $\\sup_{k\\le 10^6}(f(x_k)-f^*)\\sqrt{k+1}/\\log(k+2)$ exceeds $C_1+C_2\\log(1/\\beta)$. If the frequency stays at or below $2\\beta$ for constants fitted to the theorem, the claim survives; a sharper check is algebraic: at $k=1$, compute both sides of the conditional moment inequality $E[\\exp(t\\sqrt{a_1}\\langle\\theta_1,\\varphi_1\\rangle)\\mid F_0]\\le\\exp(a_1\\sigma^2tE(0))$ for $t=1$ under any sub-Gaussian law, since a violation would locate a gap in Lemma 1's application.","supporting_citations":[{"cited_title":"An optimal method for stochastic composite optimization.Mathematical Programming, 133(1-2):365–397, 2012","cited_arxiv_id":null,"evidence_quote":"supplies the SGDM algorithm whose momentum variant is analyzed and the pointwise high-probability rate used as comparison baseline."},{"cited_title":"Robbins and D","cited_arxiv_id":null,"evidence_quote":"states the almost-super-martingale convergence theorem that Lemma 1 extends to a large-deviation bound."}],"review_version":1}