{"id":"1f9ecd14-d95d-48f5-bd76-c117e7143378","arxiv_id":"2505.09279","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A clipping-based distributed subgradient method is proven to converge for non-smooth weakly convex problems under heavy-tailed noise, with an O(1/log T) stationarity rate.","lead":"This paper designs a distributed algorithm that uses gradient clipping to let many agents jointly minimize a non-smooth, weakly convex objective when their gradient estimates have heavy-tailed noise with infinite variance. The authors prove convergence to a stationarity measure and show a slow O(1/log T) rate, with a small experiment on MNIST phase retrieval.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's displayed expectation bound is not justified as written: the proof turns a martingale-difference sum into V_{k0}-theta outside the expectation and then divides by an infinite denominator, while the claimed O(M/log T) rate requires a finite-T statement that is never derived.","rationale":"I read the paper as a theoretical convergence analysis of a clipping-based distributed subgradient method for non-smooth weakly convex problems under heavy-tailed noise. The central claim is Theorem 2: convergence of the Moreau-envelope gradient of the averaged iterate at rate O(M/log T). The strongest parts are the self-contained proof structure, the explicit parameter condition (15), and the use of a growing clipping threshold to control the bias. The reader's choice of Assumption 8 as the weakest assumption is reasonable: if alpha <= 1, Lemma 3's bias bound fails to vanish and the series condition sum alpha_k tau_k^{2-2 alpha} diverges. However, Assumption 8 explicitly states alpha in (1,2], so that issue is a scope limitation rather than an internal inconsistency. My independent reading identified a more direct gap in the main theorem's proof: the passage in Appendix F from the almost-sure potential inequality to the expectation bound on the infimum is not justified as written. The sum of V_k - E[V_{k+1}|F_k] is a martingale-difference sum plus a telescoping term; taking expectation before truncation, and then dividing by an infinite denominator, loses the finite-T rate that Remark 4 claims. This is a genuine rigor gap in the central claim, but it is repairable by a standard finite-T argument followed by monotone convergence. Therefore the reader's CONDITIONAL verdict remains appropriate; my concern does not change the verdict, though it shifts emphasis away from Assumption 8.","tokens_in":15095,"tokens_out":26023,"duration_ms":264057,"concrete_test":"Rewrite the proof of Theorem 2 with finite T: establish the inequality E[inf_{k0<=k<=T} ||nabla phi_mu(xbar_k)||^2] <= C * (sum_{k=k0}^T alpha_k)^{-1} * ( E|V_{k0} - theta| + sum_{k=k0}^T b_k + (1/(2 mu)) sum_{k=k0}^T tau_k^2 alpha_k^2 + (1/(2 mu)) sum_{k=k0}^T alpha_k (2 gamma)^{2 alpha} tau_k^{2-2 alpha} ). If this finite-T inequality cannot be derived because the martingale-difference sum M_{T+1} is not controlled in L^1, then the O(M/log T) rate in Remark 4 is unsupported. If it can be derived, restate Theorem 2 with finite T and with all random quantities placed inside the expectation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Appendix F, the authors sum inequality (F.1) from k0 to infinity and divide by the infinite sum of the stepsizes. The key numerator term is sum_{k=k0}^T (V_k - E[V_{k+1}|F_k]). This is not a telescoping sum almost surely: it equals V_{k0} - V_{T+1} + M_{T+1}, where M_{T+1} = sum (V_{k+1} - E[V_{k+1}|F_k]) is a martingale-difference sum. Only after taking expectation and only for finite T does the martingale part vanish. As printed, Theorem 2 keeps the random quantities \\|V_{k0}-theta\\| and the b_k terms outside the expectation, and it divides by an infinite denominator, which under condition (15) formally makes the displayed upper bound 0 rather than a rate. The remark then switches to a finite-T O(M/log T) statement that was not established by the displayed proof. This is the critical step connecting the almost-sure potential-function convergence to the claimed expectation bound on the Moreau gradient. The gap is repairable by writing the finite-T inequality first, taking expectations, and then applying monotone convergence to the infimum, but the central theorem as stated is not yet proven at this point.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a distributed stochastic subgradient method with gradient clipping for non-smooth, weakly convex objectives over time-varying networks, allowing heavy-tailed gradient noise with only a finite alpha-th moment. The main theoretical claims are Theorem 1, an almost-sure convergence of the Moreau envelope along the averaged iterates, and Theorem 2, an expectation bound on the squared norm of the Moreau-envelope gradient together with an O(M/log T) rate for a particular choice of parameters. The paper also reports numerical experiments on a phase-retrieval problem using MNIST measurements.","tokens_in":15331,"tokens_out":7566,"duration_ms":77608,"significance":"If the results were rigorously established, this would be a useful contribution: it extends clipping-based heavy-tailed stochastic optimization from smooth/convex settings to non-smooth, weakly convex distributed problems, and it avoids the bounded-variance assumption that much of the distributed stochastic optimization literature relies on. The paper also provides explicit parameter conditions and a direct comparison with centralized or server-based clipping algorithms. The Moreau-envelope potential-function argument is appropriate for the problem class, and the experimental section gives evidence of heavy-tailed noise in the phase-retrieval application. However, the central rate statement in Theorem 2 is not proved as written, and one technical lemma is stated inconsistently; these issues affect the main claims and require repair.","major_comments":[{"comment":"The proof of Theorem 2 sums inequality (F.1) from k0 to infinity and then divides by the infinite sum of the stepsizes. This step is not justified as written. For a finite horizon T, the key numerator term is sum_{k=k0}^T (V_k - E[V_{k+1}|F_k]), which equals V_{k0} - V_{T+1} plus a martingale-difference sum; only after taking expectations does the martingale term vanish, and then the numerator is E[V_{k0}] - E[V_{T+1}], not the random quantity ||V_{k0}-theta|| displayed in Theorem 2. Dividing by an infinite denominator would also formally send the displayed upper bound to zero under condition (15), rather than producing the rate stated in Remark 4. The finite-T inequality should be written first, then expectations taken, then monotone convergence applied to pass from inf_{k0<=k<=T} to inf_{k>=k0}; Remark 4's O(M/log T) claim should be stated as a finite-T bound with explicit T dependence. The theorem statement should also define theta, since Theorem 1 as stated does not introduce it.","section":"Appendix F, Theorem 2, and Remark 4"},{"comment":"Lemma 4 is dimensionally inconsistent: the left-hand side is a sum of norms, sum_i ||x_{i,k+1} - \\hat v_{i,k}||, while the first term on the right-hand side is a sum of squared norms, sum_i ||v_{i,k} - \\hat v_{i,k}||^2, and the final term N tau_k^2 alpha_k^2 also has squared units. The proof in Appendix C derives an inequality with squared norms on the left. The lemma statement should be corrected to the squared-norm form actually proved, and the subsequent use of the lemma in Appendix E should be checked against the corrected statement.","section":"Section 4.2, Lemma 4"},{"comment":"The quantity b_k is introduced in Appendix E as a random bound involving the consensus errors, and later replaced by a deterministic O(...) bound. In Theorem 2, however, sum b_k appears as a term in the bound without a clear definition or an explicit replacement by the deterministic bound. The theorem is only well-defined if b_k is a deterministic sequence; otherwise the right-hand side of Theorem 2 contains unintegrated random variables. Please state the definition of b_k in the theorem, or make explicit that the O(...) bound from Appendix E is substituted and spell out the resulting constants.","section":"Theorem 2 and Appendix E"}],"minor_comments":[{"comment":"The definition of the subgradient in (1), ∂f(x) = ∂h(x) - ρ||x||, is not dimensionally consistent: the term should be -ρx, not -ρ||x||. The inequality in (2) uses the inner-product form, so the intended definition is clear, but the displayed formula should be corrected.","section":"Section 2.2, Eq. (1)"},{"comment":"The condition 1 < μ < 1/ρ in the definition of the Moreau envelope should likely be 0 < μ < 1/ρ, since Theorem 1 later uses 0 < μ < 1/(2(ρ+1)). The printed interval also excludes all cases with ρ >= 1, which would be inconsistent with the rest of the paper.","section":"Section 2.3, Eq. (4)"},{"comment":"The symbol α is used both for the moment exponent in Assumption 8 and, as α_k, for the stepsize sequence. This creates confusion in condition (15), where α_k τ_k^{2-2α} mixes the two uses. A different symbol for the moment exponent would improve readability.","section":"Assumptions 8 and Theorem 1"},{"comment":"The statement 'there exists μ < 1/ρ satisfies ...' should be 'for all μ < 1/ρ' or 'whenever μ < 1/ρ', since the proof and applications use the inequality for arbitrary admissible μ, not merely for one specially chosen value.","section":"Section 2.3, Lemma 2"},{"comment":"The baseline algorithms 'DPSM' and 'stoDPSM' are not defined in the text; a brief description or reference is needed. In addition, the captions of Fig. 2 and Fig. 3 should indicate what is plotted on the axes, especially the meaning of 'linear rate' in Fig. 3.","section":"Section 5, numerical experiments"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the headline: the paper is the first to combine gradient clipping, decentralized consensus, non-smooth weakly convex objectives, and heavy-tailed noise; that combination is worth taking seriously. The main convergence claim is plausible, but the proof of Theorem 2 as written has a real gap, and the stress-test note correctly identifies it.\n\nWhat is genuinely good: the problem setting is meaningful and not covered by prior work. The algorithm is simple and natural—clip the local subgradient, then do a projected consensus step. The use of the Moreau envelope as a potential function follows the right template, and the paper gives explicit conditions on stepsize and clipping parameter. Assumption 8 (finite alpha-th moment, alpha in (1,2]) is the appropriate weak-noise model. The consensus lemma and the bias bound from clipping are standard and mostly sound.\n\nThe soft spots are concentrated in the proof of Theorem 2 and in the experiments. In Appendix F, the authors sum (F.1) from k0 to infinity and divide by the infinite sum of stepsizes. The term sum_{k=k0}^\\infty (V_k - E[V_{k+1}|F_k]) is not telescoping; it equals V_{k0} - theta plus a martingale difference sum. Only after taking expectation over a finite horizon do the martingale terms vanish. As printed, the RHS of Theorem 2 contains random variables (V_{k0}-theta) outside the expectation, and dividing by an infinite denominator makes the bound formally zero rather than a rate. This is a load-bearing gap, but it is repairable: write the finite-T inequality, take expectations, then take the limit. Lemma 4 also has a dimensional typo—the LHS should be a sum of squared norms. The experiment uses a stepsize alpha_k = 30/NK that does not match the theoretical condition (15); no code or error bars are provided, so it is illustrative only.\n\nNet: this is a paper for researchers in decentralized optimization under heavy-tailed noise. It deserves a serious referee because the setting is important and the approach is plausible, but it needs major revision before the main theorem is trustworthy. I would send it out.","headline":"The paper is the first to combine clipping, consensus, non-smooth weakly convex objectives, and heavy-tailed noise, but the proof of the main theorem has a repairable gap that must be fixed before the rate claim is trustworthy.","tokens_in":15888,"tokens_out":5196,"would_cite":false,"duration_ms":50748,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a gradient-clipping distributed subgradient algorithm converges almost surely to a stationary point of non-smooth weakly convex objectives under heavy-tailed noise, with rate O(M/log T) on the Moreau-envelope…","keywords":["distributed stochastic optimization","weakly convex problems","heavy-tailed noise","gradient clipping","Moreau envelope","consensus","subgradient method","phase retrieval"],"falsifier":"Run the proposed algorithm on a single agent ($N=1$, so consensus is trivial) with synthetic subgradient noise drawn from a symmetric Lévy-stable distribution with tail index $\\alpha=1.5$ and a non-smooth weakly convex objective such as $f(x)=|x^2-1|$; record $\\inf_{k\\le T}\\|\\nabla\\varphi_\\mu(\\bar{x}_k)\\|^2$ over many seeds. The theorem predicts decay at least $O(M/\\log T)$, so observing the metric level off at a positive constant, or decay slower than logarithmic, would refute Theorem 2.","tokens_in":14855,"feed_emoji":"📉","tokens_out":7942,"duration_ms":72371,"temperature":0.7,"pith_summary":"The paper tries to establish that a purely decentralized, consensus-based stochastic subgradient method—where each agent clips its local gradient before communicating—can solve distributed optimization problems whose objectives are only weakly convex and non-smooth, and whose stochastic subgradient noise may have unbounded variance. It proves that the Moreau envelope of the average iterate converges almost surely, and that the expected squared norm of its gradient decays like O(M/log T) for stepsize alpha_k = 1/(k+1) and clipping threshold tau_k = 2C0(k+1)^0.4. This matters because most existing heavy-tailed distributed algorithms assume convexity and smoothness, while many machine-learning tasks are weakly convex and non-smooth, and real gradient noise is often heavy-tailed. A phase-retrieval experiment on MNIST supports the claim.","feed_headline":"Clipping tames heavy-tailed noise in distributed optimization","feed_subtitle":"For non-smooth weakly convex objectives, the clipped distributed subgradient method reaches stationarity at O(M/log T).","key_machinery":"The load-bearing object is the Moreau envelope $\\varphi_\\mu(x)=\\min_{y\\in\\Omega}\\{f(y)+\\frac{1}{2\\mu}\\|y-x\\|^2\\}$ and its proximal map $\\widehat{x}=\\arg\\min_{y\\in\\Omega}\\{f(y)+\\frac{1}{2\\mu}\\|y-x\\|^2\\}$, whose gradient satisfies $\\nabla\\varphi_\\mu(x)=\\frac{1}{\\mu}(x-\\widehat{x})$; a small gradient norm certifies near-stationarity. The second component is the clipping map $\\widehat{g}_{i,k}=g_{i,k}\\min\\{1,\\tau_k/\\|g_{i,k}\\|\\}$, which truncates each local subgradient at level $\\tau_k$ and, under the $\\alpha$-th moment bound, has bias at most $(2\\gamma)^\\alpha \\tau_k^{1-\\alpha}$. The consensus estimate of Lemma 5 keeps the disagreement $\\|\\bar{x}_k-x_{i,k}\\|$ small enough that all consensus error terms are summable, so the Moreau potential decreases modulo bias terms that vanish as $\\tau_k\\to\\infty$.","core_discovery":"The central assertion is Theorem 2: under Assumptions 1–8 and condition (15), the averaged iterates $\\bar{x}_k$ satisfy\n$$E\\Big[\\inf_{k_0\\le k\\le \\infty}\\|\\nabla \\varphi_\\mu(\\bar{x}_k)\\|^2\\Big]\\le \\frac{2}{1-2\\mu(\\rho+1)}\\Big(\\frac{\\|V_{k_0}-\\$\\theta$\\|+\\sum_{k=k_0}^\\infty b_k}{\\sum_{k=k_0}^\\infty \\alpha_k}+\\frac{\\sum_{k=k_0}^\\infty \\$tau_k^{2}$\\$alpha_k^{2}$/(2\\mu)+\\sum_{k=k_0}^\\infty \\alpha_k(2\\gamma)^{2\\$\\alpha$}\\$tau_k^{{2-2\\alpha}}$/(2\\mu)}{\\sum_{k=k_0}^\\infty \\alpha_k}\\Big),$$\nand with $\\alpha_k=1/(k+1)$, $\\tau_k=2C_0(k+1)^{0.4}$, this is $O(M/\\log T)$. In words, the sequence approaches a stationary point of the non-smooth weakly convex global objective even though each local stochastic subgradient may have infinite variance; only a finite $\\alpha$-th moment for some $\\alpha\\in(1,2]$ is required.","pith_inferences":["A direct extension the paper leaves implicit: per-agent clipping levels $\\tau_{i,k}$ could be tuned to the local tail index $\\alpha_i$, which may improve constants when agents observe noise of different heaviness.","The logarithmic rate is governed by the constant $M$, which depends on the initial Moreau gap and consensus transients; one could test whether a short warm-up with larger clipping thresholds reduces $M$ and accelerates practical convergence.","Because the proof only needs the tail probability of $\\|g_{i,k}-G_{i,k}\\| > \\tau_k/2$, it suggests convergence may survive for noise with slowly varying tails whose $\\alpha$-th moment exists only asymptotically, but the rate would degrade—a claim not made in the paper.","The analysis treats the averaging step as one consensus round per gradient step; for federated settings with multiple local updates between communications, the consensus-error bound would need reworking, but the clipping-bias argument would carry over."],"forward_implications":["The algorithm reaches a stationary point almost surely for any distributed weakly convex non-smooth problem whose local stochastic subgradients have a finite moment of order $\\alpha>1$; neither smoothness nor bounded variance is required.","With stepsize $\\alpha_k=1/(k+1)$ and clipping threshold $\\tau_k=2C_0(k+1)^{0.4}$, the expected squared Moreau gradient of the averaged iterate decays as $O(M/\\log T)$, so only logarithmically many iterations are needed to drive the stationarity metric to a given tolerance up to the constant $M$.","Consensus and clipping coexist: the result holds over strongly connected, time-varying, doubly stochastic graphs, so the method needs no central server.","The heavy-tailed regime includes infinite-variance noise ($\\alpha<2$), and the bounded-variance case is recovered as the limit $\\alpha=2$.","In the robust phase-retrieval experiment on MNIST, the clipped method reconstructs the image where unclipped distributed baselines do not, indicating practical usefulness beyond the proof."],"supporting_citations":[{"why":"Supplies the clipping operation and the idea that clipping controls heavy-tailed gradient noise.","marker":"[22]"},{"why":"Provides the distributed projected subgradient framework for weakly convex problems, including Lemmas 1 and 2.","marker":"[32]"},{"why":"Gives the smoothness of the Moreau envelope and the single-valued proximal mapping that define the stationarity measure.","marker":"[37]"},{"why":"Provides the almost-sure convergence theorem for distributed stochastic subgradient projection used in Theorem 1.","marker":"[16]"},{"why":"Supplies the consensus error bound used in Lemma 5 for time-varying graphs.","marker":"[48]"},{"why":"Provides the convergence rate analysis for distributed projected subgradient algorithms that underlies Lemma 5's rate.","marker":"[47]"},{"why":"Establishes the distributed heavy-tailed noise setting that this paper extends beyond smooth convex objectives.","marker":"[33]"},{"why":"Gives the robust phase retrieval formulation used in the numerical experiment.","marker":"[28]"}],"fun_headline_variants":["Clipping beats heavy tails in non-smooth distributed optimization","Distributed clipping handles unbounded noise on weakly convex problems","Heavy-tailed noise? Clipped subgradients still converge","Taming infinite variance in distributed non-smooth optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 8: each local stochastic subgradient must have a finite moment of some order $\\alpha>1$ (variance may be infinite); if even that moment fails, the clipping bias term $(2\\gamma)^\\alpha\\tau_k^{1-\\alpha}$ does not vanish as $\\tau_k\\to\\infty$, so the convergence argument collapses.","fun_headline_variants_meta":{"raw":{"variants":["Clipping beats heavy tails in non-smooth distributed optimization","Distributed clipping handles unbounded noise on weakly convex problems","Heavy-tailed noise? Clipped subgradients still converge","Taming infinite variance in distributed non-smooth optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001069,"raw_usage":{"total_tokens":4493,"prompt_tokens":971,"completion_tokens":3522,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":3455}},"tokens_in":587,"tokens_out":3522,"duration_ms":25957,"temperature":1.0,"reasoning_tokens":3455,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:35:20.682156+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed algorithm on a single agent ($N=1$, so consensus is trivial) with synthetic subgradient noise drawn from a symmetric Lévy-stable distribution with tail index $\\alpha=1.5$ and a non-smooth weakly convex objective such as $f(x)=|x^2-1|$; record $\\inf_{k\\le T}\\|\\nabla\\varphi_\\mu(\\bar{x}_k)\\|^2$ over many seeds. The theorem predicts decay at least $O(M/\\log T)$, so observing the metric level off at a positive constant, or decay slower than logarithmic, would refute Theorem 2.","supporting_citations":[{"cited_title":"On distributed nonconvex optimization: Projected subgradient method for weakly convex problems in networks","cited_arxiv_id":null,"evidence_quote":"Provides the distributed projected subgradient framework for weakly convex problems, including Lemmas 1 and 2."},{"cited_title":"Efficiency of minimizing compositions of convex functions and smooth maps","cited_arxiv_id":null,"evidence_quote":"Gives the smoothness of the Moreau envelope and the single-valued proximal mapping that define the stationarity measure."},{"cited_title":"Distributed stochastic subgradient projection algorithms for convex optimization","cited_arxiv_id":null,"evidence_quote":"Provides the almost-sure convergence theorem for distributed stochastic subgradient projection used in Theorem 1."},{"cited_title":"Constrained consensus and optimization in multi-agent networks","cited_arxiv_id":null,"evidence_quote":"Supplies the consensus error bound used in Lemma 5 for time-varying graphs."},{"cited_title":"Convergence rate analysis of distributed optimization with projected subgradient algorithm","cited_arxiv_id":null,"evidence_quote":"Provides the convergence rate analysis for distributed projected subgradient algorithms that underlies Lemma 5's rate."},{"cited_title":"Distributed Stochastic Optimization under Heavy-Tailed Noises","cited_arxiv_id":"2312.15847","evidence_quote":"Establishes the distributed heavy-tailed noise setting that this paper extends beyond smooth convex objectives."},{"cited_title":"Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval","cited_arxiv_id":null,"evidence_quote":"Gives the robust phase retrieval formulation used in the numerical experiment."}],"review_version":1}