{"id":"b80bcee2-a031-47fc-bcac-70fe329c9d2e","arxiv_id":"2412.19529","paper_version":4,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Batched normalized SGD with momentum reaches the optimal heavy-tailed nonconvex rate without gradient clipping, and attains a slower but parameter-free rate when the tail index is unknown.","lead":"This paper proves that a standard normalized stochastic gradient method with momentum converges at the optimal theoretical rate for nonconvex optimization even when noise has heavy tails and no gradient clipping is used. It also gives the first convergence guarantee when the tail index is unknown, a common practical situation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The core vector-valued martingale inequality (Lemma 4.3) is load-bearing, but its proof in Appendix C rests on a dimensionally inconsistent identity; as printed, Lemma C.1 does not establish the lemma, and the no-clipping rates are unsupported unless this is corrected.","rationale":"Both the reader and I identify Lemma 4.3 as the load-bearing step: all convergence rates are obtained by plugging Lemma 4.5/D.5, which are consequences of Lemma 4.3, into the descent inequality. The reader states that the proof of Lemma 4.3 via Lemma C.1 appears consistent; my re-reading of Appendix C finds a concrete algebraic inconsistency in the proof of Lemma C.1 as printed. The issue is not the novelty/priority overclaim, which Footnote 1 already concedes, but the internal validity of the core inequality. I am not claiming Lemma 4.3 is false; it is plausibly true for Hilbert-space martingales by Burkholder-Davis-Gundy with a constant like 2*sqrt(2), which would make the paper's rates correct. The concern is that the manuscript's only proof is invalid as written, and no external verification is supplied. For a central lemma on which the entire paper rests, this should be fixed or replaced by a standard citation before the claim can be taken as established. I therefore keep the reader's CONDITIONAL verdict, since the mathematical program is credible and likely repairable, but with a stronger condition: correct the Appendix C proof of Lemma 4.3, not merely adjust the 'first' claim. If the numerical test were to find a genuine counterexample, the correct verdict would be REJECT.","tokens_in":28703,"tokens_out":19568,"duration_ms":181659,"concrete_test":"Independently verify Lemma C.1/Lemma 4.3: (1) recompute the T=1 check of inequality (11) with the printed γ_t to confirm the dimensional failure; (2) run a numerical search for a p=2 vector-valued MDS counterexample to Lemma 4.3 with T<=3 and d>=2, sampling conditional distributions over finite atoms; if any instance has E||sum_t v_t|| > 2*sqrt(2)*E[sqrt(sum_t ||v_t||^2)], the lemma is false and the rates collapse. If no counterexample is found, re-prove Lemma 4.3 from the standard Burkholder-Davis-Gundy inequality or from the corrected AdaGrad regret bound with η_t = 1/sqrt(2*sum_{s<=t} ||v_s||^2), and state the resulting constant; if the constant exceeds 2*sqrt(2), recompute the constants in Theorems 3.2 and 3.6 to see whether the claimed O-dependence survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Every rate in Theorems 3.2 and 3.6 flows through Lemma 4.3, a dimension-free MDS bound. The proof of Lemma 4.3 depends on Lemma C.1. As printed in Appendix C, γ_t is defined as sqrt(2 * sum_{s<=t} ||v_s||^2), and inequality (11) asserts that sum_t γ_t ||v_t||^2 / 2 = sum_t γ_t (1/γ_t^2 - 1/γ_{t-1}^2) <= 2/γ_T. With the printed definition, γ_t is nondecreasing, so the right-hand summand is non-positive while the left-hand summand is non-negative; the equality is false. The units also mismatch: the left side scales as ||v||^3 and the right side as ||v||^{-1}. For T=1 and v_1=10e_1, the claimed chain would require 707.1 <= 0.141. If γ_t is meant to be the inverse AdaGrad stepsize, the definition and all displayed inequalities must be corrected. In either case, the derivation of Lemma 4.3 from Lemma C.1 (taking expectations and canceling sum_t E<v_t,w_t>) depends on which reading is intended; the printed version does not establish the lemma. Because Lemmas 4.5 and D.5 reduce every noise accumulation bound to Lemma 4.3, the optimal no-clipping rates are only as secure as this unverified inequality. The lemma may be true via Burkholder-Davis-Gundy, but the manuscript's only proof is internally inconsistent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) for nonconvex optimization under heavy-tailed noise with only a finite p-th moment. It claims the first optimal convergence rate O(T^{-(p-1)/(3p-2)}) without gradient clipping, a first O(T^{-(p-1)/(2p)}) rate when the tail index p is unknown, extensions to generalized (L0,L1)-smoothness and generalized heavy-tailed noise, and a refined lower bound with sharp dependence on problem parameters. The main technical novelty is Lemma 4.3, a dimension-free vector-valued martingale inequality proved in Appendix C through an AdaGrad regret argument.","tokens_in":28951,"tokens_out":9666,"duration_ms":93703,"significance":"If correct, the paper would be a significant contribution: it would show that gradient clipping is not necessary for optimal heavy-tailed nonconvex convergence, provide a partially parameter-agnostic guarantee, extend the theory to relaxed smoothness, and give a lower bound with matching parameter dependence. The paper is generally well structured, the appendix is detailed, and the high-level proof strategy via normalization is natural and interesting. However, the central martingale inequality is proved through Appendix C, and the printed proof contains an algebraic inconsistency; since Lemma 4.3 is the single tool behind all noise-accumulation bounds, Theorems 3.2 and 3.6 are not established as printed.","major_comments":[{"comment":"The proof of Lemma C.1 is not valid as printed. With gamma_t defined as sqrt(2 * sum_{s<=t} ||v_s||^2), gamma_t is nondecreasing, and ||v_t||^2 = (gamma_t^2 - gamma_{t-1}^2)/2. The displayed identity gamma_t ||v_t||^2 / 2 = gamma_t (1/gamma_t^2 - 1/gamma_{t-1}^2) is then false: the right-hand side is nonpositive while the left-hand side is nonnegative. A one-step numeric check, T=1 and v_1=10e_1, gives 707.1 on the left and 0.141 on the right if the chain were true. Consequently the bound sum_t gamma_t ||v_t||^2/2 <= 2/gamma_T does not follow. If gamma_t is intended to be the inverse AdaGrad stepsize, the definition and every subsequent display must be corrected. Because Lemma 4.3 is invoked in Lemmas 4.5 and D.5, and those lemmas underlie Theorems 3.2 and 3.6, the central no-clipping rates rest on an unproved inequality as printed.","section":"Appendix C, Lemma C.1 and Eq. (11)"},{"comment":"Even apart from the algebraic error in Eq. (11), the proof of Lemma 4.3 requires Lemma C.1 to produce random vectors w_t that are measurable with respect to F_{t-1}, so that E[<v_t,w_t>] = 0. The construction via AdaGrad can yield such a predictable sequence, but the proof as written does not clearly separate the predictable iterate w_t from the updated iterate w_{t+1}, and the flawed inequality in Eq. (11) is an essential step in the displayed bound. The lemma itself is plausible and likely true by known Hilbert-space martingale inequalities, but the manuscript's only proof needs to be repaired before the derived rates can be accepted.","section":"Appendix C, derivation of Lemma 4.3 from Lemma C.1"}],"minor_comments":[{"comment":"The abstract and contribution list describe the result as 'the first convergence result under heavy-tailed noises without gradient clipping,' but footnote 1 acknowledges two independent and concurrent works with similar results. The wording should be adjusted to avoid an overclaim, e.g., by saying 'independently and concurrently.'","section":"Abstract and Section 1.1"},{"comment":"The statement allows sigma_0 >= 0, but the choice of beta divides by sigma_0. The noiseless case sigma_0 = 0 should be stated separately or handled by a limiting argument, since the displayed formulas are undefined at sigma_0 = 0.","section":"Theorem 3.2"},{"comment":"There are small presentation issues in the appendix, including the notation 'Delta L_0 T' in Eq. (16) where 'Delta_1' is meant, and the indicator '1_{s>=2}' is used without a prior definition. These should be cleaned up.","section":"Appendix D, proof of Theorem D.1"},{"comment":"Lemma 2.5 is stated without proof and delegated to a cited work. Since it is used repeatedly in the main proof, a short proof or a precise pointer to the cited lemma would improve self-containedness.","section":"Lemma 2.5"},{"comment":"The proof says 'W.l.o.g.' and then handles the case ||v_1|| > 0, but the treatment of the first nonzero v_t is abbreviated; it would be clearer to spell out the indexing shift in the statement of Lemma C.1 so that the subsequent summation over t is unambiguous.","section":"Appendix C, proof of Lemma C.1"}],"recommendation":"major_revision","confidential_remarks":"The technical flaw in Appendix C is load-bearing but appears fixable: the intended inverse-AdaGrad definition of gamma_t and the corrected summation identity are standard, and the lemma itself is plausible via known martingale inequalities. I would not reject on this basis, but the proof must be corrected and re-verified. The priority claim also needs editorial attention given the admitted concurrent work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the genuinely new piece here is the unknown-tail-index rate O(T^{-(p-1)/(2p)}) and the analysis under (L0,L1)-smoothness. The known-p no-clipping rate is already in Hübler et al. and Sun et al., which the paper acknowledges in a footnote but still calls 'first' in the abstract. Second, and more serious: the proof of Lemma 4.3, the vector-valued martingale inequality that all the noise accumulation bounds reduce to, is internally inconsistent as printed. In Appendix C, gamma_t is defined as sqrt(2 * sum ||v_s||^2), which makes gamma_t nondecreasing; then inequality (11) claims sum gamma_t ||v_t||^2 / 2 <= 2/gamma_T, which is false—for T=1 and ||v_1||=10, the left side is about 707 and the right side is 0.14. The intended definition is almost certainly the reciprocal, and the proof could be repaired, but that is not what the manuscript shows. Since Lemmas 4.5 and D.5 simply invoke Lemma 4.3, the headline rates are not established by the displayed proof.\n\nWhat the paper does well: the structure is clear, the lower-bound refinement is plausible, and the idea of using normalization rather than clipping to survive heavy tails is worth taking seriously. The paper also flags its own limitation that Theorem 3.6 needs L1, which is honest.\n\nBut the soft spots are more than cosmetic. The 'first' claim is overstated. More importantly, the core lemma's proof has a sign and dimension error. If the lemma is true—and it likely is, via vector-valued Burkholder-Davis-Gundy—the paper needs a correct proof before the results can be trusted. I would not rely on the rates as they stand.\n\nWho this is for: people working on heavy-tailed nonconvex optimization, especially those charting when clipping is avoidable. It deserves a serious referee, because the questions are real and the conjectured results are plausible. But the referee should insist on a corrected Appendix C before acceptance.\n\nMy recommendation: send it out, but mark it 'major revision' and make the authors fix Lemma 4.3. As it stands, the central claim is not proven.","headline":"Genuinely new unknown-p result and a serious proof gap: the load-bearing martingale inequality in Appendix C does not work as printed.","tokens_in":29577,"tokens_out":4820,"would_cite":false,"duration_ms":43239,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C26","62L20","60G42"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that Batched NSGDM, a normalized SGD with momentum, achieves optimal heavy-tailed convergence without any gradient clipping.","keywords":["heavy-tailed noise","nonconvex optimization","gradient normalization","gradient clipping","stochastic gradient descent","martingale inequality","generalized smoothness"],"falsifier":"To decide whether the central claim holds, one can check Lemma 4.3 numerically: simulate a martingale difference sequence in $R^{2}$ with p close to 1 and heavy-tailed increments, and see whether E[||sum v_t||] is bounded by 2 $\\sqrt$(2) E[(sum ||v_t||^p)^{1/p}]. A counterexample would invalidate the proof and the theorem.","tokens_in":1553,"feed_emoji":"📉","tokens_out":4275,"duration_ms":63358,"temperature":0.7,"pith_summary":"This paper claims that gradient clipping is not a necessary ingredient for optimal convergence under heavy-tailed noise in nonconvex stochastic optimization. It studies the existing Batched NSGDM algorithm, which normalizes the momentum update to unit length, and proves that it achieves the optimal rate O($T^{{-(p-1)/(3p-2)}}$) when the noise has a finite p-th moment, matching the known lower bound. It also provides the first convergence guarantee when the tail index p is unknown, with a rate O($T^{{-(p-1)/(2p)}}$). The central insight is that normalization changes the error term that must be controlled from a second moment to a first moment, which falls within the range of the heavy-tailed assumption.","feed_headline":"Optimal heavy-tailed convergence without gradient clipping","feed_subtitle":"Batched NSGDM achieves the known lower bound, even when the tail index is unknown.","key_machinery":"The central object is Lemma 4.3, a new vector-valued martingale inequality: for a martingale difference sequence (a sequence of random vectors whose conditional mean given the past is zero) v_t in R^d and any p in [1,2], E[||sum_{t=1}^T v_t||] <= 2 $\\sqrt$(2) E[(sum_{t=1}^T ||v_t||^p)^{1/p}]. This inequality is proved in Appendix C via an AdaGrad-style regret bound, and it extends the scalar Burkholder-Davis-Gundy inequality to high dimensions with an explicit constant. It is what allows the accumulated noise in the momentum error to be controlled using only a p-th moment, which is the exact information available under heavy-tailed noise. The normalization step in Batched NSGDM makes the descent inequality depend on the first moment of the error rather than the second, so this inequality becomes the key substitute for clipping.","core_discovery":"The paper proves that Batched NSGDM, a normalized SGD with momentum, achieves the optimal convergence rate O($T^{{-(p-1)/(3p-2)}}$) for nonconvex stochastic optimization under heavy-tailed noise, meaning the stochastic gradient noise only has a finite p-th moment with p in (1,2]. This rate matches the existing lower bound, and the result holds under the more general (L0,L1)-smoothness condition. The same algorithm, with parameters chosen independent of p, also achieves the first convergence rate O($T^{{-(p-1)/(2p)}}$) when the tail index is unknown. The proof relies on a new dimension-free vector-valued martingale inequality that bounds the expected norm of a martingale sum by a p-th moment of its increments.","pith_inferences":["The new martingale inequality may be of independent interest and could simplify analyses of other stochastic algorithms with heavy-tailed noise, such as sign-based or adaptive methods.","A natural next step, suggested by the paper, is to determine whether the optimal O(T^{-(p-1)/(3p-2)}) rate is achievable without knowing p, or to prove a lower bound for the unknown-p setting.","The paper's claim that normalization is a robust primitive suggests that gradient clipping might only be a proxy for a more fundamental first-moment control; similar arguments may apply to other normalized updates."],"forward_implications":["If the paper is correct, gradient clipping is not necessary for optimal heavy-tailed nonconvex convergence; normalized SGD with momentum achieves the same O(T^{-(p-1)/(3p-2)}) rate.","When the tail index p is unknown, Batched NSGDM still converges at O(T^{-(p-1)/(2p)}) with parameters that depend only on the horizon and, in the worst case, on L1.","The analysis extends to generalized smoothness and affine noise, so the result covers settings beyond the classical Lipschitz-gradient and finite-variance assumptions.","The refined lower bound matches the upper bound in Delta_1, L0, and sigma_0, showing the dependence is tight."],"supporting_citations":[{"why":"Introduces Batched NSGDM, the algorithm analyzed in this paper.","marker":"Cutkosky & Mehta (2020)"},{"why":"Establishes the heavy-tailed noise setting, the lower bound, and Clipped SGD as the main baseline.","marker":"Zhang et al. (2020c)"},{"why":"Provides the lower-bound framework and zero-chain construction used in the refined lower bound.","marker":"Arjevani et al. (2023)"},{"why":"Supplies the AdaGrad regret inequality that is used to prove the core martingale lemma.","marker":"Rakhlin & Sridharan (2017)"},{"why":"Provides the function construction that the lower-bound proof adapts to include the noise level.","marker":"Carmon et al. (2020)"}],"fun_headline_variants":["Batched NSGDM optimal without gradient clipping","No clipping, optimal rate under heavy-tailed noise","Optimal heavy-tailed SGD without gradient clipping","Batched NSGDM: optimal despite unknown tail index","No clipping needed for optimal heavy-tailed optimization"],"cache_read_input_tokens":31488,"weakest_assumption_plain":"The proof hinges on the new martingale inequality in Lemma 4.3; if that inequality fails for some p in [1,2] or in some dimension, the claimed rates would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Batched NSGDM optimal without gradient clipping","No clipping, optimal rate under heavy-tailed noise","Optimal heavy-tailed SGD without gradient clipping","Batched NSGDM: optimal despite unknown tail index","No clipping needed for optimal heavy-tailed optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000687,"raw_usage":{"total_tokens":3142,"prompt_tokens":1001,"completion_tokens":2141,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":617,"completion_tokens_details":{"reasoning_tokens":2070}},"tokens_in":617,"tokens_out":2141,"duration_ms":14127,"temperature":1.0,"reasoning_tokens":2070,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:15:48.208420+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To decide whether the central claim holds, one can check Lemma 4.3 numerically: simulate a martingale difference sequence in $R^{2}$ with p close to 1 and heavy-tailed increments, and see whether E[||sum v_t||] is bounded by 2 $\\sqrt$(2) E[(sum ||v_t||^p)^{1/p}]. A counterexample would invalidate the proof and the theorem.","supporting_citations":[{"cited_title":"Momentum improves normalized SGD","cited_arxiv_id":null,"evidence_quote":"Introduces Batched NSGDM, the algorithm analyzed in this paper."},{"cited_title":"On equivalence of martingale tail bounds and deterministic regret inequalities","cited_arxiv_id":null,"evidence_quote":"Supplies the AdaGrad regret inequality that is used to prove the core martingale lemma."},{"cited_title":"Lower bounds for finding stationary points i","cited_arxiv_id":null,"evidence_quote":"Provides the function construction that the lower-bound proof adapts to include the noise level."}],"review_version":1}