{"id":"c238a2c5-7950-4af7-87d8-467b1e616bc5","arxiv_id":"2509.08726","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"DNSGD is a decentralized normalized stochastic gradient method for (L0,L1)-smooth nonconvex optimization, with complexity bounds that match standard smooth decentralized results when L1=0.","lead":"A new algorithm called DNSGD lets a network of agents minimize a shared nonconvex loss function whose gradients are not Lipschitz by normalizing each agent's gradient before averaging. The paper proves sample and communication bounds that reduce to near-optimal rates in the standard smooth case and tests the method on MNIST.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's proof contains an algebraic inequality that fails in the theorem's parameter regime; the main convergence proof is incomplete as written.","rationale":"The reader's verdict of CONDITIONAL is appropriate, but the most load-bearing concern is not the acknowledged Assumption 3 limitation; it is an internal proof gap in Lemma 3, which is essential for the Lyapunov decrease (5) and hence for Theorem 1. The paper's central claim may still be true, because Lemma 3 can likely be repaired with a less aggressive bound, and the reader's other concerns (zero gradient estimates, no code) remain secondary. However, as written, the proof of a key lemma contains a verifiably false algebraic step in the admissible parameter regime, so the manuscript needs revision before the result can be considered proven. This supports the CONDITIONAL verdict rather than ACCEPT or UNVERDICTED: the issue is concrete and fixable, but it is not merely a stylistic weakness. I agree with the reader that Assumption 3 is a substantive scope limitation and that the open problem it creates is real; I partially disagree with the reader's assessment that 'no fatal error was identified,' since the Lemma 3 proof gap is a correctness issue in the current write-up. The proposed concrete test settles whether the gap is merely a missing constant or whether the communication complexity must change.","tokens_in":22132,"tokens_out":51216,"duration_ms":772330,"concrete_test":"Verify the disputed inequality in Appendix E numerically in the L1 = 0 case: set m = 2, Lf = 1, rho = 0.01, eta = 0.1, and ||X_t - 1 xbar_t|| = 0. Then the left-hand side of (20) equals 3*0.0001*(0.2)^2 + 3*2*0.01 = 0.060012 while the right-hand side equals (1.01)^2*(0.2)^2 = 0.040804, so the claimed bound fails. Then re-derive Lemma 3 using the valid triangle bound C1 <= (1+rho)Lf(||X_t - 1 xbar_t|| + sqrt(m) eta) for L1 = 0 (and the analogous relaxed-smooth version for L1 > 0), and check whether the resulting M2, M3 still satisfy the parameter conditions in Appendix F with K = O(log m/sqrt(gamma)). If the corrected constants force K to grow faster than O(log m/sqrt(gamma)), the stated communication complexity in Corollary 1 would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central Lyapunov argument depends on Lemma 3, whose proof is invalid as written. In Appendix E, the step labeled (20) claims that for A = ||X_t - 1 xbar_t|| + m eta, G = ||grad f(xbar_t)||, and M2 = (rho+1)Lf + rho Lf L1 eta, M3 = rho L1(L1 eta + 1) + L1, we have 3 rho^2 (Lf + ...)^2 A^2 + 3(Lf + L1 G)^2 ||X_t - 1 xbar_t||^2 + 3m(Lf + L1 G)^2 eta^2 <= (M2 + M3 G)^2 A^2. Take the special case L1 = 0, m = 2, Lf = 1, and t = 0 so X_0 = 1 xbar_0 and ||X_0 - 1 xbar_0|| = 0. Then A = m eta. The claimed inequality reduces to 12 rho^2 + 6 <= 4(1 + rho)^2, i.e. (2rho - 1)^2 <= 0, which holds only at rho = 1/2. But the proof of Theorem 1 requires rho to satisfy rho <= O(1/m) (and in fact the explicit conditions in Appendix F force rho to be much smaller than 1/2 for m = 2). Thus the displayed inequality is false throughout the admissible parameter range, so the derivation of the recursion for E||V_{t+1} - 1 vbar_{t+1}|| does not go through. The lemma itself may be salvageable with a tighter triangle bound (e.g., bounding C1 by (1+rho)Lf(||X_t - 1 xbar_t|| + sqrt(m) eta) instead of the lossy squared inequality), but the proof as written is not correct.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decentralized stochastic optimization of a finite average of local functions under (L0,L1)-relaxed smoothness and bounded gradient dissimilarity. It proposes DNSGD, which combines normalized stochastic gradients with gradient tracking and Chebyshev-accelerated gossip. The main theoretical result (Theorem 1 and Corollary 1) is an epsilon-stationarity guarantee for every local agent, with per-agent sample complexity O(m^{-1}(L_f sigma^2 Delta_f epsilon^{-4} + sigma^2 epsilon^{-2} + L_f^{-2} L_1^3 sigma^2 Delta_f epsilon^{-1} + L_f^{-2} L_1^2 sigma^2)) and communication complexity O~( (L_f epsilon^{-2} + L_1 epsilon^{-1}) Delta_f gamma^{-1/2} ). When L1=0, the sample complexity nearly matches known decentralized lower bounds. The analysis introduces a Lyapunov function that includes the product of the gradient norm and the consensus error. The paper also contains a counterexample (Proposition 3) showing that local relaxed smoothness alone does not imply global relaxed smoothness, and it explicitly leaves the decentralized setting without bounded gradient dissimilarity as an open problem.","tokens_in":22524,"tokens_out":13229,"duration_ms":114773,"significance":"The proposed Lyapunov framework is the main novelty: it avoids gradient clipping and handles non-Lipschitz, unbounded local gradients. If the proof gap described below is repaired, the paper would be a useful contribution to decentralized relaxed-smooth optimization. The special-case match to lower bounds in the L1=0 setting is a strong point, and the paper is transparent about the role of Assumption 3. The full proofs and numerical comparisons are also valuable. However, the central lemma used to control the gradient-tracking consensus error contains an invalid algebraic step, so the main theorem is not established as written. The revision should focus on repairing that step rather than on the algorithmic concept, which is sound in outline.","major_comments":[{"comment":"The final inequality in (20) is false in the parameter regime of Theorem 1. Set L1=0, m=2, Lf=1, t=0, and X0=1bar{x}_0. Then A=m eta, G=||grad f(bar{x}_0)||, M2=1+rho, M3=0, and the claimed inequality becomes 3rho^2(2eta)^2 + 6eta^2 <= (1+rho)^2(2eta)^2, i.e. 12rho^2 + 6 <= 4(1+rho)^2, equivalently (2rho-1)^2 <= 0. This holds only at rho=1/2, whereas the conditions in Appendix F require rho <= O(1/sqrt(m)) and, for m=2, force rho to be considerably smaller than 1/2. Hence the displayed bound on ||grad f(X_{t+1}) - grad f(X_t)|| is not valid. Since Lemma 3 is used to derive the Lyapunov recursion (5) and then Theorem 1, the main convergence proof is incomplete as written. The lemma may be salvageable with a tighter triangle bound, but the current proof does not establish it.","section":"Appendix E, Eq. (20)"},{"comment":"The update U_t sets the i-th row to v_i^t / ||v_i^t||. This is undefined whenever ||v_i^t|| = 0. Such an event is not excluded by Assumptions 1-5; it can occur with positive probability for a mini-batch gradient estimate, or deterministically when an agent reaches a stationary point. The authors should specify a convention (for instance, define 0/0 = 0) and check that Lemmas 1-3 and Theorem 1 remain valid under that convention, or modify the algorithm with a small perturbation.","section":"Algorithm 2, line 6"}],"minor_comments":[{"comment":"The title and abstract claim decentralized optimization 'under the (L0,L1)-smoothness', while Theorem 1 requires the additional bounded-gradient-dissimilarity assumption (Assumption 3). This qualification should appear wherever the main claim is stated.","section":"Title and abstract"},{"comment":"The combining step in the proof of Lemma 3 writes 2rho sqrt(m) sigma / b, but Eq. (22) and the statement of the lemma require 2rho sqrt(m) sigma / sqrt(b). Please correct this typo.","section":"Appendix E, after Eq. (22)"},{"comment":"The phrase 'vector AM-QM inequality' is not the correct name for the inequality used in the first bound of the proof of Lemma 5; the intended step is the triangle inequality. Please correct the terminology.","section":"Appendix A, Lemma 5 proof"},{"comment":"The numerical comparison appears to be based on single runs and no error bars are reported. The claim that DNSGD outperforms all baselines would be more convincing with multiple seeds and standard deviations.","section":"Section 6"},{"comment":"The abstract refers to a connected network of n agents while the rest of the paper uses m for the number of agents; please make the notation consistent.","section":"Abstract and notation"}],"recommendation":"major_revision","confidential_remarks":"The error in Lemma 3 is concrete and load-bearing: the inequality (20) fails in the admissible parameter regime, and the Lyapunov recursion depends on it. I do not recommend rejection because the L1=0 version of the algorithm is likely correct and the Lyapunov idea is promising. The authors should be given the opportunity to repair the proof with a sharper bound and to address the zero-gradient division. If the revised proof still relies on an incorrect inequality, the paper should not be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read the DNSGD paper. The high-level idea is genuinely useful: a Lyapunov function that multiplies the gradient norm by the consensus error to handle (L0,L1)-smoothness in a decentralized stochastic setting. The rates are plausible, and the L1=0 limit matching near-optimal decentralized nonconvex bounds is a good sanity check. The m=1 comparison with prior clipping analysis is also sensible, and the discussion of why Jiang et al. is not truly decentralized/stochastic is fair.\n\nBut the earlier take missed a real problem. The stress-test found a concrete counterexample to the display (20) in Appendix E. With L1=0, m=2, and X_0 already at consensus, the claimed inequality reduces to (2rho-1)^2 <= 0, which forces rho = 1/2. The theorem's parameter choices in Appendix F require rho to be much smaller than 1/2. So Lemma 3's proof does not go through, and the Lyapunov recursion built on it is not justified. This is load-bearing, not a cosmetic issue.\n\nWhat the paper does well: the product Lyapunov function is a new analysis framework, the paper is self-contained, and Proposition 3 cleanly shows why bounded gradient dissimilarity (Assumption 3) is needed. The discussion of the open problem without Assumption 3 is honest. Assumption 3 being strong is not itself a flaw; it is acknowledged as needed.\n\nOther soft spots: the normalized update divides by ||v_i|| without handling v_i=0, which is a minor gap but easy to patch. The experiments ship no code and are limited to MNIST/Fashion-MNIST; for a theory paper that is secondary but worth noting.\n\nOverall: the main theorem is unproven as written. The error is a specific algebra falsehood, not a vague concern, and the lemma may be salvageable with a tighter bound. This is exactly the kind of paper that deserves a serious referee: the idea is worth engaging with, and the proof just needs to be repaired. I recommend sending to peer review with a request to fix Lemma 3 before publication.","headline":"Smart Lyapunov idea, but the proof of the load-bearing Lemma 3 contains an algebraic inequality that fails in the admissible parameter range, so the main theorem is not established as written.","tokens_in":23022,"tokens_out":4227,"would_cite":false,"duration_ms":34356,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Under relaxed smoothness, the decentralized algorithm DNSGD brings every agent to an $\\epsilon$-stationary point, with per-agent sample cost spread as $1/m$ and communication cost set by the network spectral gap.","keywords":["decentralized optimization","relaxed smoothness","(L0,L1)-smoothness","normalized stochastic gradient descent","nonconvex stochastic optimization","consensus error","gradient tracking","Chebyshev acceleration"],"falsifier":"Run DNSGD in the centralized limit ($m=1$, exact gradients, $\\zeta=0$), where it reduces to normalized gradient descent and the paper predicts iteration complexity $O(L_0\\Delta_f\\epsilon^{-2}+L_1\\Delta_f\\epsilon^{-1})$ for any nonconvex $(L_0,L_1)$-smooth function. Exhibiting one such function that needs more iterations to reach $\\|\\nabla f\\|\\le\\epsilon$, or numerically detecting a violation of the Lyapunov descent inequality (5), would defeat the claimed rates.","tokens_in":21952,"feed_emoji":"🌐","tokens_out":13309,"duration_ms":103564,"temperature":0.7,"pith_summary":"Relaxed smoothness, the condition that a gradient may change arbitrarily fast when the gradient itself is large, models neural-network training better than classical Lipschitz smoothness but has mostly been studied on a single machine. This paper claims the same guarantee is achievable in a decentralized network: a new algorithm, DNSGD, combines normalized stochastic gradients, gradient tracking, and Chebyshev-accelerated gossip, and proves each agent reaches an $\\epsilon$-stationary point. The per-agent sample complexity is $O(m^{-1}(L_f\\sigma^2\\Delta_f\\epsilon^{-4}+\\sigma^2\\epsilon^{-2}+L_f^{-2}L_1^3\\sigma^2\\Delta_f\\epsilon^{-1}+L_f^{-2}L_1^2\\sigma^2))$ with $L_f=L_0+L_1\\zeta$, and the communication complexity is $\\tilde{O}((L_f\\epsilon^{-2}+L_1\\epsilon^{-1})\\gamma^{-1/2}\\Delta_f)$. When $L_1=0$ these rates nearly match known lower bounds for standard-smooth decentralized nonconvex optimization; when $m=1$ they match the best-known complexity for exact-gradient relaxed-smooth problems.","feed_headline":"DNSGD hits epsilon-stationarity under relaxed smoothness","feed_subtitle":"Per-agent sample cost falls as 1/m, and the guarantee matches known lower bounds in the standard-smoothness case.","key_machinery":"The load-bearing object is the Lyapunov function $\\Phi_t=f(\\bar{x}_t)+3\\eta\\sqrt{m}(M_0+M_1\\|\\nabla f(\\bar{x}_t)\\|)\\|X_t-\\mathbf{1}\\bar{x}_t\\|+2\\eta\\sqrt{m}\\|V_t-\\mathbf{1}\\bar{v}_t\\|$, where $X_t$ stacks the local iterates, $V_t$ stacks the local gradient estimators, and $\\bar{x}_t,\\bar{v}_t$ are their averages; $M_0=\\sqrt{2(L_0^2+L_1^2\\zeta^2)}$ and $M_1=\\sqrt{2}L_1$. The product $(M_0+M_1\\|\\nabla f(\\bar{x}_t)\\|)\\|X_t-\\mathbf{1}\\bar{x}_t\\|$ mirrors the right-hand side of the relaxed-smoothness inequality, so the descent analysis can absorb consensus error even though $\\nabla f$ has no Lipschitz bound. Around this Lyapunov function the algorithm uses normalized descent steps $v_t^i/\\|v_t^i\\|$, a gradient-tracking update $V_{t+1}=\\mathrm{AccGossip}(V_t+G_{t+1}-G_t,K)$, and multi-consensus Chebyshev acceleration that contracts consensus error by a factor $\\rho\\le O(1/\\sqrt{m})$ after $K=O(\\gamma^{-1/2}\\log m)$ rounds.","core_discovery":"The central claim is that under the paper's formal assumptions, DNSGD computes, for every agent $i$, a point $\\hat{x}_i$ sampled from that agent's local history with $\\mathbb{E}[\\|\\nabla f(\\hat{x}_i)\\|]\\le\\epsilon$. The proof sets the step size to $\\eta=\\min\\{\\epsilon/(4L_f+1), 1/(2L_1)\\}$, the mini-batch size to $b\\ge\\max\\{256(4L_f+1)^2\\sigma^2/(mL_f^2\\epsilon^2), 1024L_1^2\\sigma^2/(mL_f^2)\\}$, the iteration count to $T\\ge\\max\\{8(4L_f+1)\\Delta_\\Phi/\\epsilon^2, 16L_1\\Delta_\\Phi/\\epsilon\\}$, and the number of Chebyshev communication rounds to $K=\\tilde{O}(1/\\sqrt{\\gamma})$, so the consensus error is small enough that every local iterate, not only the hidden average, satisfies the stationarity guarantee. The analysis is driven by a Lyapunov function that couples function value, gradient norm, and consensus error, avoiding any need to bound the local gradients or assume they are Lipschitz continuous.","pith_inferences":["The Lyapunov product structure is likely reusable in other non-Lipschitz decentralized settings; pairing DNSGD with variance-reduced estimators could plausibly turn the $\\epsilon^{-4}$ sample term into an $\\epsilon^{-3}$ term, a route the paper itself identifies.","Without bounded gradient dissimilarity, a proof cannot rely on the averaged objective being relaxed smooth, since Proposition 3 shows the average of two relaxed-smooth exponentials leaves the class; a gradient-tracking analysis that uses only local relaxed smoothness would be the natural next step.","A direct stress test is to run DNSGD on mixtures of rapidly growing exponentials and increase the heterogeneity parameter $\\zeta$; the theory predicts the difficulty should appear exactly where the averaged objective loses relaxed smoothness."],"forward_implications":["Every agent can certify an $\\epsilon$-stationary point from its own iterates, so the guarantee is fully decentralized and does not depend on a globally available mean.","The $1/m$ factor in the sample complexity means linear speedup: doubling the number of agents halves the per-agent sample requirement when heterogeneity and spectral gap are held fixed.","In the standard-smoothness limit $L_1=0$, the bounds reduce to $O(m^{-1}(L_0\\sigma^2\\Delta_f\\epsilon^{-4}+\\sigma^2\\epsilon^{-2}))$ samples per agent and $\\tilde{O}(L_0\\Delta_f\\gamma^{-1/2}\\epsilon^{-2})$ communications, nearly matching the lower bounds.","In the single-agent limit, the method matches the best-known iteration complexity for exact-gradient relaxed-smooth nonconvex optimization and improves on the clipping-based stochastic bound in the regime where that bound dominates."],"supporting_citations":[{"why":"Supplies the relaxed smoothness condition that the paper extends from centralized to decentralized stochastic optimization.","marker":"[56]"},{"why":"Provides the gradient-based form of $(L_0,L_1)$-smoothness and the descent lemma that opens the proof of Lemma 1.","marker":"[55]"},{"why":"Gives the lower bounds for standard-smooth decentralized stochastic nonconvex optimization that DNSGD nearly matches when $L_1=0$.","marker":"[33]"},{"why":"Contributes the normalized SGD analysis and the lemma on averages of normalized vectors used in the consensus-error control.","marker":"[26]"},{"why":"Supplies the Chebyshev-accelerated multi-consensus contraction result (Proposition 2) that controls consensus errors in DNSGD.","marker":"[52]"},{"why":"Gives the best-known iteration complexity for centralized exact-gradient relaxed-smooth optimization that DNSGD's single-agent limit matches.","marker":"[47]"},{"why":"Supplies the gradient-tracking update that maintains the global-gradient estimator $V_t$ in DNSGD.","marker":"[40]"}],"fun_headline_variants":["DNSGD: new decentralized nonconvex method for (L0,L1)-smooth","Relaxed smoothness? DNSGD still finds epsilon-stationarity","DNSGD: per-agent epsilon-stationarity for nonconvex decentralized problems","DNSGD: overcoming (L0,L1)-smoothness in decentralized optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument stands on the assumption that each local gradient stays within a fixed distance $\\zeta$ of the global gradient everywhere; if this fails, the averaged objective can stop being relaxed smooth even when every local objective is, and the paper leaves decentralized convergence in that case open.","fun_headline_variants_meta":{"raw":{"variants":["DNSGD: new decentralized nonconvex method for (L0,L1)-smooth","Relaxed smoothness? DNSGD still finds epsilon-stationarity","DNSGD: per-agent epsilon-stationarity for nonconvex decentralized problems","DNSGD: overcoming (L0,L1)-smoothness in decentralized optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001311,"raw_usage":{"total_tokens":5476,"prompt_tokens":1213,"completion_tokens":4263,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":829,"completion_tokens_details":{"reasoning_tokens":4177}},"tokens_in":829,"tokens_out":4263,"duration_ms":30965,"temperature":1.0,"reasoning_tokens":4177,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:00:31.767084+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DNSGD in the centralized limit ($m=1$, exact gradients, $\\zeta=0$), where it reduces to normalized gradient descent and the paper predicts iteration complexity $O(L_0\\Delta_f\\epsilon^{-2}+L_1\\Delta_f\\epsilon^{-1})$ for any nonconvex $(L_0,L_1)$-smooth function. Exhibiting one such function that needs more iterations to reach $\\|\\nabla f\\|\\le\\epsilon$, or numerically detecting a violation of the Lyapunov descent inequality (5), would defeat the claimed rates.","supporting_citations":[{"cited_title":"1 T T−1X t=0 ∇f( ¯xt) # ≤E 8(Φ0−Φ T ) 5ηT + 6ηLf 5 ≤ 8∆Φ 5ηT + 6ηLf 5 , where the last step holds due to E[Φ0−Φ T ] =E","cited_arxiv_id":null,"evidence_quote":"Supplies the relaxed smoothness condition that the paper extends from centralized to decentralized stochastic optimization."},{"cited_title":"Improved analysis of clipping algorithms for non-convex optimization","cited_arxiv_id":null,"evidence_quote":"Provides the gradient-based form of $(L_0,L_1)$-smoothness and the descent lemma that opens the proof of Lemma 1."},{"cited_title":"Optimal complexity in decentralized training","cited_arxiv_id":null,"evidence_quote":"Gives the lower bounds for standard-smooth decentralized stochastic nonconvex optimization that DNSGD nearly matches when $L_1=0$."},{"cited_title":"Multi-consensus decentralized accelerated gradient descent.Journal of Machine Learning Research, 24(306):1–50, 2023","cited_arxiv_id":null,"evidence_quote":"Supplies the Chebyshev-accelerated multi-consensus contraction result (Proposition 2) that controls consensus errors in DNSGD."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the best-known iteration complexity for centralized exact-gradient relaxed-smooth optimization that DNSGD's single-agent limit matches."}],"review_version":1}