{"id":"5230c1fc-7a72-469e-b0a3-352e794b6e34","arxiv_id":"2602.05657","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"For non-convex smooth costs, the tail probability that SGD's best gradient remains above a fixed threshold decays at speed t/log(t) (bounded noise), and clipped SGD achieves t^{4(p-1)/(3p-2)}/log(t) under p-th moment noise; the claimed matching lower bound runs only at speed t, so it does not prove","lead":"This theory paper proves that, in the long run, the failure probability of SGD and clipped SGD decays as roughly e^{-t/polylog(t)} for non-convex problems, faster than previous finite-time bounds suggested. It also claims these rates are optimal, but the lower-bound argument it gives only bounds the tail from below at a different speed and does not support that optimality claim.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower bound in Theorem 3 is at speed e^{-t}, while the upper bounds are e^{-t/log t} (vanilla SGD) or e^{-t^{β_p}/log t} / e^{-t/log^2 t} (clipped SGD); it is far too weak to show these rates are tight, so the abstract's central tightness claim is unsupported.","rationale":"I read the paper in good faith. The upper-bound machinery is a plausible extension of prior finite-time high-probability analyses: the authors correctly identify that a Gartner-Ellis type argument requires MGF finiteness for all λ and use a.s. bounded noise for vanilla SGD and a carefully chosen clipping threshold for c-SGD to control the MGF. The proofs of Theorems 1 and 2 appear internally coherent at the level of the displayed estimates, and the acknowledgment that bounded noise is stronger than the sub-Gaussian condition in [12] is honest. However, the paper's own 'Contributions' and abstract claim that the rates are tight up to polylog factors, and that claim is the central advertised result. The lower bound in Theorem 3 is not at the same speed as the upper bounds. For vanilla SGD, the upper bound is e^{-c t/log t}; the lower bound is e^{-a2 t}. Since e^{-a2 t} is exponentially smaller than e^{-c t/log t}, the lower bound is compatible with the actual tail decaying much faster than the upper bound and does not rule out an improved upper bound at speed t (or any speed between t/log t and t). The same issue is worse for c-SGD with p∈(1,2), where the upper speed is t^{β_p}/log t with β_p<1. The internal constant swap between Theorem 2 and Corollary 2 is secondary but reinforces that the manuscript is not yet in a state where the tightness claim can be accepted. The appropriate verdict is therefore REJECT for the stated claim; a revised version that either removes the tightness overclaim or supplies matching lower bounds at the same speeds, and fixes the constant inconsistency, could be reconsidered. Since the reader already reached REJECT, my recommendation is UNCHANGED. My main concern differs from the reader's stated weakest_assumption (bounded noise vs. the lower-bound mismatch), although the reader's rationale also flags the tightness gap, hence partial agreement.","tokens_in":28000,"tokens_out":12491,"duration_ms":127201,"concrete_test":"Re-evaluate the Theorem 3 construction under the same normalization as the upper bounds. Compute liminf_{t→∞} (log t / t) log P(F_t > ε) for the Huber/Rademacher instance for vanilla SGD; the proof gives log P(F_t > ε) ≥ -(t-1)ln 2, so the normalized liminf is -∞, not a positive finite constant. A matching lower bound at the claimed rate would require liminf (log t / t) log P(F_t > ε) ≥ -C for some finite C>0. Repeat for c-SGD with p=2 at normalization log^2(t)/t; the same check shows the lower bound does not certify the t/log^2 t speed. If no instance yielding P(F_t>ε) ≥ e^{-C t/log t} (or the corresponding c-SGD rate) is produced, the tightness claim should be removed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised central claim is that the upper-bound rates in Theorems 1 and 2 are tight up to polylogarithmic factors. Theorem 3 does not establish this. Its constructed instance gives P(F_t > ε) ≥ a1 e^{-a2 t}. Under the normalization used in Corollary 1, i.e., (log t / t) log P(F_t > ε), this lower bound yields liminf = -∞, not a finite negative constant. A lower bound of the form e^{-a2 t} is compatible with P(F_t > ε) decaying like e^{-C t/log t}, e^{-C sqrt t}, or even e^{-C t}; it does not rule out an upper bound at a faster speed than t/log t. For p ∈ (1,2) the speed mismatch is polynomial: the claimed upper rate is t^{4(p-1)/(3p-2)}/log t, while the lower bound is only e^{-a2 t} relative to the e^{-t} scale; for p=2 the gap is between e^{-t/log^2 t} and e^{-t}. Thus Eq. (6) compares two different normalizations and cannot be read as tightness. The upper-bound results may survive as standalone large-deviations bounds, but the paper's central 'tight' conclusion is not supported by the provided lower bound. In addition, Theorem 2 and Corollary 2 swap the constants 384 and 768 for the p=2 and p∈(1,2) cases, which is an internal inconsistency that should be corrected if the paper is revised.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the long-term tail decay of the best-iterate gradient norm squared, F_t = min_{k<=t} ||grad f(x_k)||^2, for vanilla SGD under bounded noise and for clipped SGD under bounded p-th moment noise. Using MGF estimates and the Gartner-Ellis theorem, Theorem 1 gives an LDP upper bound for SGD with rate t/log(t), and Theorem 2 gives upper bounds for clipped SGD with rates t^{4(p-1)/(3p-2)}/log(t) for p in (1,2) and t/log^2(t) for p=2. Theorem 3 constructs a specific Huber-cost/Rademacher-noise instance and proves P(F_t>eps) >= a_1 e^{-a_2 t}. The paper advertises these results as showing that the upper-bound rates are tight up to polylogarithmic factors.","tokens_in":28337,"tokens_out":15670,"duration_ms":161043,"significance":"If the upper-bound derivations are correct, they are a genuine technical contribution: they obtain large-deviations upper bounds with global rate functions for non-convex SGD, improving on the tail decay implied by existing finite-time high-probability bounds, and the extension to clipped SGD under heavy-tailed noise is nontrivial. The Gartner-Ellis route and the control of the global MGF are interesting and largely self-contained. However, the advertised central claim of tightness is not established. The lower bound in Theorem 3 is at speed e^{-t}, while the upper bounds are at slower speeds e^{-t/log t} and e^{-t/log^2 t} / e^{-t^{beta_p}/log t}. Such a lower bound does not rule out upper bounds at speed e^{-O(t)}, so it cannot support the conclusion that the stated rates are tight. The upper-bound theorems may be publishable as standalone large-deviations bounds, but the paper as submitted overclaims its main result.","major_comments":[{"comment":"The lower bound P(F_t>eps) >= a_1 e^{-a_2 t} is at decay speed n_t=t, while Theorem 1's upper bound is at speed n_t=t/log(t). Under the normalization of Corollary 1, this lower bound only implies liminf (log t / t) log P >= -infinity, not a finite negative constant. Indeed, P(F_t>eps) >= e^{-a_2 t} is compatible with P(F_t>eps) <= e^{-c t}, i.e. with an upper bound at speed t, so it does not rule out a faster tail than the claimed t/log(t). To prove tightness one would need a lower bound at the same scale, e.g. P >= e^{-C t/log t}. The same mismatch holds for clipped SGD: for p=2 the comparison is e^{-t} versus e^{-t/log^2 t}, and for p in (1,2) it is e^{-t} versus e^{-t^{beta_p}/log t}, a polynomial gap. Thus Eq. (6) compares two different normalizations and cannot be read as showing tightness; the abstract's 'tight up to poly-logarithmic factors' claim is unsupported.","section":"Section 3.4, Theorem 3 and Eq. (6)"}],"minor_comments":[{"comment":"The constants in Corollary 2 are reversed relative to Theorem 2. Theorem 2 gives rate function x^2/(768 G^4) for p in (1,2) and x^2/(384 G^4) for p=2, but Corollary 2 states -eps^2/(384 G^4) for p in (1,2) and -eps^2/(768 G^4) for p=2. The corollary should match the theorem.","section":"Section 3.3, Corollary 2"},{"comment":"For p=2, the clipping threshold in (5) is gamma_t = 2G sqrt(log(t+1)); at t=1 this is about 1.66G, so gamma_1/2 < G and the condition ||grad f(x_t)|| <= gamma_t/2 used in Proposition 2 may fail at t=1. The proof of Theorem 3 states that the threshold (5) 'clearly' satisfies gamma_t >= 2G, which is not true at t=1. Finite initial exceptions do not affect the limsup, but the statements should be modified.","section":"Lemma 3.2 / Theorem 3 proof"},{"comment":"In the proof, the sequence is defined as n_t = t/log(T), later used as t/log(t); the capital T is a typo.","section":"Appendix E, proof of Theorem 1"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Top line: the LDP upper bounds are the real content here, and they look plausible; the \"tight up to poly-log\" claim is not supported by the lower bound in Theorem 3.\n\nThe upper-bound rates for vanilla SGD (t/log t) and clipped SGD (t^{beta_p}/log t for p in (1,2), t/log^2 t for p=2) are genuinely faster than what finite-time HP bounds imply. The MGF/Gartner-Ellis route is self-contained and mostly clean: Lemma 3.1/3.2 give the needed MGF control, and the proofs track. That is a useful contribution for people working on large-deviations guarantees for stochastic gradient methods.\n\nThe trouble is Theorem 3. It constructs a Huber-cost/Rademacher-noise instance where P(F_t > eps) >= a1 e^{-a2 t}. That is a lower bound at speed t. The upper bounds are at speed t/log t or t^{beta_p}/log t. A lower bound of e^{-a2 t} does not rule out an upper bound at any speed between t/log t and t; it only says the tail is no smaller than an exponentially fast-decaying quantity. Normalizing by log(t)/t, as Corollary 1 does, the lower bound gives liminf = -infinity, not a finite negative constant. So Eq. (6) compares different normalizations and does not show tightness. For p in (1,2) the gap is polynomial, not polylog. The abstract's central tightness claim is therefore unsupported.\n\nThere is also a real internal inconsistency: Theorem 2 gives the rate function constant 768 for p in (1,2) and 384 for p=2, but Corollary 2 swaps them (384 for p in (1,2), 768 for p=2). Easy to fix, but confusing.\n\nThe assumptions are stronger than prior HP work: a.s. bounded noise for vanilla SGD and bounded gradients everywhere. The paper acknowledges the bounded-noise point. That restricts practical scope, but it is not fatal; the clipped-SGD result still gives a meaningful heavy-tailed relaxation.\n\nWho this is for: researchers doing large-deviations analysis of SGD or HP guarantees in non-convex stochastic optimization. The upper-bound parts deserve a serious referee and likely could be published after the overclaim is removed and the constants fixed. I would not cite the tightness claim as-is, but the upper bounds alone might be citable in a corrected version.\n\nRecommendation: send to peer review. The referee should focus on the upper-bound proofs and require either a matching lower bound at the same speed or an honest restatement that the current lower bound only gives e^{-t} and does not establish tightness.","headline":"The upper-bound LDP rates for SGD and clipped SGD are plausible and genuinely faster than prior finite-time bounds, but the advertised 'tight up to polylog' claim is not supported: the Theorem 3 lower bound decays at speed e^{-t} while the upper bounds are e^{-t/log t} or slower.","tokens_in":29007,"tokens_out":3268,"would_cite":false,"duration_ms":32588,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60F10","62L20","90C15","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"For non-convex costs, the probability that the best iterate of vanilla or clipped SGD fails to reach stationarity by time t decays like e^{-t/log t} — an order of magnitude faster than earlier finite-time bounds implied.","keywords":["large deviations","stochastic gradient descent","clipped SGD","heavy-tailed noise","non-convex optimization","tail bounds","failure probability","moment-generating function"],"falsifier":"The proof of the main upper bound reduces to inequality (19): after dividing by n_t = t/log t, all terms except 6λ^2M^2G^2 must vanish. If one can exhibit a cost and noise satisfying Assumptions 1–3 for which the empirical limsup of (log t / t) log P(F_t > ε) exceeds -ε^2/(24M^2G^2), or for which the stated log-MGF inequality fails at some λ, the t/log t rate is wrong. For the lower bound, the constructed event that the iterate stays at x_1 for t steps has probability 2^{-t+1}; verifying the piecewise-quadratic recursion with two-point noise at finite t is a direct check.","tokens_in":27769,"feed_emoji":"📉","tokens_out":9189,"duration_ms":86166,"temperature":0.7,"pith_summary":"The paper asks a sharp question about individual runs: what is the probability that, after t iterations, no SGD iterate has gradient norm below a fixed threshold? It proves that this failure probability decays like e^{-t/log t} for vanilla SGD with almost-surely bounded noise, and like e^{-t^{β_p}/log t} (with β_p=4(p-1)/(3p-2), or e^{-t/log^2 t} when p=2) for clipped SGD with heavy-tailed noise having a bounded p-th moment. These rates are exponentially faster than the √t and t^{β_p/2} decays implied by earlier finite-time high-probability bounds, so the prediction for long training runs is qualitatively different. A constructed example with a piecewise-quadratic cost and symmetric two-point noise shows the rates are tight up to logarithmic factors.","feed_headline":"SGD failure tails decay at t/log t, far faster than prior bounds","feed_subtitle":"For fixed error thresholds, per-run failure odds of SGD shrink like e^{-t/log t}, not e^{-sqrt t}.","key_machinery":"The engine is a sequence of uniform bounds on the log-moment-generating function of F_t, evaluated at λ n_t for every real λ, combined with the Fenchel–Legendre transform from large-deviations theory. For vanilla SGD, L-smoothness turns F_t into a sum of deterministic, noise, and squared-noise terms, and a sub-Gaussian inequality for the a.s. bounded noise yields a quadratic rate function. For clipped SGD, the clipping error is decomposed into an unbiased sub-Gaussian component with scale γ_t and a bias component bounded by 4σ_p γ_t^{1-p}; choosing γ_t to grow at the right rate balances the two and produces the exponent β_p. The lower bound is carried by a probabilistic invariant: for the co","core_discovery":"The paper shows that under deterministic initialization, a smooth lower-bounded cost with gradients bounded by G, and unbiased noise bounded almost surely by M, vanilla SGD with step-size a/√(t+1) satisfies a large-deviations upper bound on F_t = min_{k≤t} ||∇f(x_k)||^2 at rate n_t = t/log t, with rate function I_v(x)=x^2/(24M^2G^2) for x≥0. Under heavy-tailed noise with a bounded moment of order p, clipped SGD with a suitably growing clipping threshold achieves rate t^{4(p-1)/(3p-2)}/log t for p∈(1,2) and t/log^2 t for p=2. The paper also constructs an instance — a piecewise-quadratic cost with symmetric two-point noise and a deterministic nonzero-gradient initialization — for which the tra","pith_inferences":["The logarithmic factors in the upper rates look like artifacts of the summation step that replaces ∑_{k=1}^t 1/(k+1) by log(t+1); closing that gap would likely yield e^{-ct} upper bounds that exactly match the constructed lower bound.","The bounded-gradient and almost-sure-bounded-noise assumptions exist to make the moment-generating function finite on the whole real line; if the argument can be reworked for sub-Gaussian or unbounded-gradient costs, the same t/log t prediction may hold more broadly.","A natural extension is to adaptive methods whose updates normalize or clip the gradient estimate, since the clipped-SGD analysis already produces a sub-Gaussian unbiased component with growing scale; similar large-deviations bounds may hold under only weak moment assumptions.","The constructed lower-bound instance is simple enough to simulate at finite t, so one could check numerically how quickly the e^{-t/log t} regime sets in and whether the asymptotic rate is visible at realistic iteration counts."],"forward_implications":["If Theorem 1 is right, the asymptotic chance that a vanilla SGD run misses every ε-stationary point in its first t steps is at most exp(-ε^2 t / (24M^2G^2 log t)), much smaller than the exp(-c√t) decay implied by prior finite-time bounds.","For clipped SGD under heavy-tailed noise, the long-run tail rate improves from order t^{β_p/2} to order t^{β_p} (with an extra log^2 t factor at p=2), so clipping provides both robustness to unbounded noise and faster per-run failure decay.","Because the bounds fix the error threshold ε and let t grow, they speak directly to modern training regimes of millions of iterations, where finite-time bounds valid for every t are overly conservative in the long run.","The same proof technique delivers bounds on the average squared gradient norm, not just the minimum, so the result is not an artifact of the min-over-first-t metric.","The lower-bound instance shows some problems genuinely have P(F_t>ε) ≥ 2e^{-t ln2}, so no general upper bound can decay faster than exponential in t; the presented rates are tight up to logarithmic factors."],"fun_headline_variants":["SGD tails decay at e^{-t/log t}, beating prior e^{-√t}","Long-term SGD tails: e^{-t/log t}, tighter than finite-time bounds","Clipped SGD tails tight: e^{-t^{β}/log t} under heavy noise","Tail decay for SGD tightened to e^{-t/log t}, not e^{-√t}"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the noise is almost surely bounded (for vanilla SGD) or has a bounded p-th moment with uniformly bounded gradients (for clipped SGD): the proof must control the moment-generating function at every real λ, and these boundedness conditions are what make that global control possible.","fun_headline_variants_meta":{"raw":{"variants":["SGD tails decay at e^{-t/log t}, beating prior e^{-√t}","Long-term SGD tails: e^{-t/log t}, tighter than finite-time bounds","Clipped SGD tails tight: e^{-t^{β}/log t} under heavy noise","Tail decay for SGD tightened to e^{-t/log t}, not e^{-√t}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001539,"raw_usage":{"total_tokens":6115,"prompt_tokens":989,"completion_tokens":5126,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":733,"completion_tokens_details":{"reasoning_tokens":5034}},"tokens_in":733,"tokens_out":5126,"duration_ms":39164,"temperature":1.0,"reasoning_tokens":5034,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T04:12:20.478331+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The proof of the main upper bound reduces to inequality (19): after dividing by n_t = t/log t, all terms except 6λ^2M^2G^2 must vanish. If one can exhibit a cost and noise satisfying Assumptions 1–3 for which the empirical limsup of (log t / t) log P(F_t > ε) exceeds -ε^2/(24M^2G^2), or for which the stated log-MGF inequality fails at some λ, the t/log t rate is wrong. For the lower bound, the constructed event that the iterate stays at x_1 for t steps has probability 2^{-t+1}; verifying the piecewise-quadratic recursion with two-point noise at finite t is a direct check.","supporting_citations":[],"review_version":1}