{"id":"facdb1d0-3453-4ea8-8de2-f5915e29b3c2","arxiv_id":"2505.10322","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"ADSGD converges for non-convex decentralized optimization with computation-delay-independent step sizes and no bounded-heterogeneity assumption, via a reduction to asynchronous stochastic block coordinate descent.","lead":"This paper presents an asynchronous version of decentralized stochastic gradient descent (ADSGD) in which each worker updates at its own pace and mixes only with its neighbors, then proves convergence for non-convex machine learning objectives.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the reader's tilde-W concern rests on an inverted ratio; Corollary 3.12's beta/alpha is 1/(8(D+1/2)K^{1/3}), so tilde W is a valid stochastic matrix.","rationale":"The paper's central theorem and corollary follow a plausible ASBCD-based proof template, with no fatal internal inconsistency that I can identify. The reader's only concrete attack is algebraically incorrect: it inverts the beta/alpha ratio. The actual ratio is small and decreases with K, so the tilde-W matrix used in the corollary is a valid symmetric stochastic matrix. The proof of Theorem 3.9 is also independent of tilde-W stochasticity, since it applies ASBCD directly to L_alpha, so even the missing beta <= alpha condition in the theorem statement is a presentation issue rather than a correctness threat to the corollary. I checked the main proof steps: Lemma C.1's staleness bound is sound, Lemma C.3's Lyapunov argument gives the claimed O(1/(alpha K)) + O(alpha sigma^2) bound for ASBCD, and Theorem 3.9's conversion to the average model correctly separates the consensus error using the spectral gap of W. The corollary's constants are loose and there are small typographical slips in Appendix C, but the rate O(K^{-1/3}) and the step sizes' independence of the computation-delay bound B are supported. The main genuinely useful revision would be to state beta <= alpha explicitly and to clarify that the empirical Algorithm 2 is the beta = alpha special case, which is not covered by the corollary; however, this concerns the paper's presentation and experimental alignment, not the validity of the central mathematical claim.","tokens_in":20258,"tokens_out":46306,"duration_ms":421536,"concrete_test":"Evaluate the ratio r = beta/alpha = 1/(8(D+1/2)K^{1/3}) and compute the minimum entry of tilde W = (1-r)I + rW for representative K in {1, 10, 100, 1000}, D in {0, 1, 10}, and a concrete symmetric stochastic W (e.g., the Metropolis weights on a 3x3 grid). If min_{i,j} tilde W_ij >= 0 and row sums are 1 for all cases, the reader's proposed rejection condition is refuted and the corollary's parameters are valid for Algorithm 2's tilde-W instance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central convergence claim survives scrutiny. The reader's weakest-assumption concern does not land: Corollary 3.12 sets alpha = 2/(L_F K^{1/3}) and beta = 1/(4 L_F (D+1/2) K^{2/3}), so beta/alpha = 1/(8 (D+1/2) K^{1/3}), not K^{1/3}/(8(D+1/2)). For every K >= 1 and D >= 0 this ratio is at most 1/4 (and tends to 0), so tilde W = (1 - beta/alpha)I + (beta/alpha)W is a convex combination of I and W and inherits symmetry, row-stochasticity, and nonnegativity from W. Moreover, the proof of Theorem 3.9 never actually uses the stochasticity of tilde W: it applies the ASBCD lemma to L_alpha with step beta, and only the original W is required to satisfy Assumption 3.7 for L_alpha to be smooth and lower bounded and for the simplifying identity sum_i [(I-W)x]_i = 0 to hold. The theorem statement could add beta <= alpha to make the 'instance of Algorithm 2' interpretation unconditional, and the appendix contains minor constant slips (e.g., the displayed 1/(8(...)) term in the step-size verification appears to undercount 2*beta/alpha by a factor of 2, and some constants in Corollary C.4 are loose), but these do not change the O(K^{-1/3}) rate or the delay-independence of the step sizes. A presentational gap remains between the analyzed double-step-size variant and the single-step-size Algorithm 2 used in experiments, but the mathematical claim about sequence (7) is internally consistent.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies asynchronous decentralized SGD under bounded computation and communication delays. It first analyzes Asynchronous Stochastic Block Coordinate Descent (ASBCD) with stochastic gradients in non-convex smooth problems, obtaining an O(1/sqrt(K)) rate to a neighborhood (Lemma 3.8 and Corollary C.4). It then maps ADSGD to ASBCD on the surrogate L_alpha(x) = F(x) + x^T(I-W)x/(2 alpha), introduces a double-step-size update (7), and proves an O(1/K^{1/3}) bound on the average squared gradient norm at the average iterate (Theorem 3.9 and Corollary 3.12), with step sizes independent of the computation-delay bound B and without a bounded-data-heterogeneity assumption. The paper also proposes a memory-efficient implementation and reports experiments on MNIST and CIFAR-10 comparing ADSGD with ADPSGD, RFAST, DSGD, and parallel SGD.","tokens_in":20556,"tokens_out":26604,"duration_ms":255693,"significance":"If the analysis holds, the paper delivers a genuinely new guarantee: for non-convex smooth decentralized problems with partial asynchrony, the main corollary's step sizes depend on the communication-delay bound D and the horizon K but not on the computation-delay bound B. The proofs are self-contained, follow a standard Lyapunov argument, and prescribe step sizes in closed form rather than fitting constants to data; there is no circularity in the derivation. The experimental study is broad, covering heterogeneity, scalability, and several delay scenarios. I checked the stress-test concern about the tilde-W ratio: Corollary 3.12 gives beta/alpha = 1/(8(D+1/2)K^{1/3}), so tilde-W is a convex combination of I and W for all K and D, and the reader's inverted-ratio concern does not land. The central convergence claim survives scrutiny; the remaining issues are local presentation and verification details.","major_comments":[],"minor_comments":[{"comment":"The assertion that tilde-W 'satisfies Assumption 3.7' is guaranteed only when beta <= alpha, which is not implied by the theorem's condition beta < 1/((D+1/2)L_L). Corollary 3.12 is safe because its schedule gives beta/alpha = 1/(8(D+1/2)K^{1/3}) <= 1, but the theorem statement should either impose beta <= alpha or explicitly note that the proof uses only the original W and does not require tilde-W to be stochastic.","section":"Section 3.3, Eq. (7)"},{"comment":"In the display bounding L_L beta, the second term should be 1/(4(D+1/2)K^{1/3}), not 1/(8(D+1/2)K^{1/3}), because (2/alpha)beta = 1/(4(D+1/2)K^{1/3}). The final inequality still holds, but the displayed intermediate inequality is not correct as written.","section":"Appendix C.4"},{"comment":"Algorithm 2 as used in the experiments (with W and with alpha = beta = 0.01) is a special case of the double-step-size family, but it is not the decaying (alpha, beta) schedule analyzed in Corollary 3.12; the paper should state explicitly that the experiments evaluate a fixed-step-size instance of the same family and do not directly test the corollary's schedule.","section":"Sections 2.2 and 3.3"},{"comment":"The constant C2 contains 3B^2/D, so the statement should explicitly record that Assumption 3.3 assumes D > 0 or provide a separate handling for the D = 0 case.","section":"Appendix C.4, Corollary C.4"},{"comment":"The citation '[Wu et al.]' appears in the text but has no corresponding entry in the reference list; the bibliography should be completed.","section":"Section 1.1"},{"comment":"The explanation that the third equality follows from doubly stochasticity of W is terse; since Assumption 3.7 states symmetry and row-stochasticity, it would be clearer to say that column stochasticity follows from symmetry and row stochasticity.","section":"Eq. (24)"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is within scope and the central convergence result appears sound. No citation-ethics concerns beyond the missing [Wu et al.] entry. The theory/experiment parameter gap noted in the minor comments should be addressed in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is stronger than the reader's report suggests. The tilde-W concern is a false alarm. Corollary 3.12 sets beta/alpha = 1/(8(D+1/2)K^{1/3}), not the inverse, so tilde-W is a convex combination of I and W and inherits symmetry, stochasticity, and nonnegativity. The stress-test note is right about that. The proof of Theorem 3.9 is also self-consistent once you notice that in ASBCD/ADSGD the agent's own block in its own buffer is always current, so the double-step-size update's effective gradient estimator is unbiased for L_alpha. The central convergence claim holds up.\n\nWhat is genuinely new: the stochastic-gradient extension of Sun-Hannah-Yin's ASBCD, and the double-step-size device that yields a B-independent step size for nonconvex async decentralized SGD without bounded heterogeneity. That is a real step beyond prior tracking-based methods, which need step sizes scaling with B and often absurdly small constants. The O(1/K^{1/3}) rate is plausible and the proof follows a standard Lyapunov template.\n\nSoft spots, in order of severity. First, the gap between what is analyzed and what is run: the theorem covers the double-step-size update with modified weights tilde-W and step beta, while the experiments use Algorithm 2 with the original W and a fixed step size 0.01. The authors say the variant is 'effectively' Algorithm 2 with a different W, which is true when beta<=alpha, but that requires knowing K in advance to set alpha and thus tilde-W. The experiments do not do this, so the empirical support is suggestive rather than directly backed by the theorem. Second, no code is released, and the appendix says the experiments took about 1200 GPU hours, so independent reproduction is heavy. Third, there are small constant-factor slips in the appendix (e.g., in the step-size verification of Corollary C.4), none affecting the rate or delay-independence. Finally, the reference to '[Wu et al.]' is not numbered in the bibliography and the entry is incomplete.\n\nWho it's for: people working on asynchronous decentralized optimization, especially those who care about practical step sizes. The paper deserves a serious referee. I'd send it to review, but with an eye toward requiring the authors to either prove convergence for the exact single-step-size Algorithm 2 with a practical schedule, or clearly separate the theoretical variant from the experimental one, and to fix the reference and loose constants.","headline":"Solid theory paper with a real first: computation-delay-independent step sizes for nonconvex async decentralized SGD, but the analyzed double-step-size variant is not what the experiments run.","tokens_in":21134,"tokens_out":10746,"would_cite":true,"duration_ms":93159,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15","90C06"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that fully asynchronous decentralized SGD converges for non-convex objectives at rate $O(1/K^{1/3})$ with step sizes independent of the computation-delay bound, achieved through a block-coordinate descent reformulation.","keywords":["asynchronous decentralized SGD","block coordinate descent","non-convex optimization","computation delay","communication delay","gossip averaging","delay-independent step sizes","stochastic gradient descent"],"falsifier":"Take a 9-agent grid network with uniform gossip weights ($W_{ii} = 0.2$ at the center node), set $D = 1$ and $B = 1$, and run the Corollary 3.12 schedule out to $K = 20{,}000$ iterations. Then $\\beta/\\alpha = K^{1/3}/(8(D+1/2)) \\approx 2.26$, and the constructed matrix has center-node diagonal entry $1 - \\beta/\\alpha + (\\beta/\\alpha)(0.2) \\approx -0.81$, a negative value that violates stochasticity. Simply computing $\\tilde{W}$ for these parameters and checking nonnegativity and row sums settles whether the theorem analyzes a legal instance of Algorithm 2.","tokens_in":19990,"feed_emoji":"🧩","tokens_out":16350,"duration_ms":133513,"temperature":0.7,"pith_summary":"This paper claims that a fully asynchronous decentralized SGD, in which a node averages its own model with neighbors' models only after finishing a gradient step, converges for non-convex objectives at rate $O(1/K^{1/3})$ with step sizes that ignore the computation-delay bound while scaling with the communication-delay bound $D$ and total steps $K$. The guarantee needs no bounded data heterogeneity, only each local loss bounded below. The argument works by viewing ADSGD as a special case of asynchronous stochastic block coordinate descent on a modified objective, then introducing a double-step-size trick to control noise accumulation. If correct, this is the first non-convex convergence guarantee for asynchronous decentralized SGD using a computation-delay-independent step size, and it comes with a simple closed-form schedule.","feed_headline":"Async decentralized SGD converges with delay-free step sizes","feed_subtitle":"A block-coordinate reformulation frees step sizes from computation-delay bounds in nonconvex training.","key_machinery":"The load-bearing object is the equivalence between ADSGD and asynchronous stochastic block coordinate descent. Defining $F(x) = \\sum_i f_i(x_i)$ and the augmented objective $L_\\alpha(x) = F(x) + x^\\top(I-W)x/(2\\alpha)$, the ADSGD update (6) is exactly one block update of ASBCD with step size $\\alpha$ on $L_\\alpha$, because each node mixes its own block with the stale neighbor blocks in its buffer. Because $L_\\alpha$ is itself step-size-dependent, the paper introduces a double-step-size scheme (7): taking a step of size $\\beta$ on $L_\\alpha$ is equivalent to mixing with $\\tilde{W} = (1-\\beta/\\alpha)I + (\\beta/\\alpha)W$ followed by a step-$\\beta$ local gradient update. As long as $\\beta \\le \\alpha$, $\\tilde{W}$ inherits symmetry and stochasticity from $W$, so the ASBCD convergence machinery transfers to ADSGD, with the rate determined by the consensus-error term of size $O(\\alpha)$.","core_discovery":"On its own terms, the paper establishes the convergence of double-step-size ADSGD: under bounded computation delay $B$ and communication delay $D$, $L$-smooth local losses, unbiased gradient estimators with bounded variance, and a symmetric stochastic gossip matrix $W$, the update (7) with $\\alpha = 2/(L_F K^{1/3})$ and $\\beta = 1/(4 L_F (D+1/2) K^{2/3})$ satisfies $\\frac{1}{K}\\sum_{k=0}^{K-1}\\mathbb{E}\\|\\nabla f(\\bar{x}^k)\\|^2 \\le O(1/K^{1/3})$, with both step sizes independent of $B$. A companion theorem states that ASBCD converges at rate $O(1/\\sqrt{K})$ under a suitably chosen step size, matching standard non-convex SGD and claimed as the first such result for asynchronous coordinate descent with stochastic gradients. The analysis also removes the bounded-data-heterogeneity assumption common in prior DSGD analyses. Empirically, the paper reports that ADSGD reaches target test accuracy faster than asynchronous and synchronous baselines under several delay and straggler scenarios.","pith_inferences":["A direct repair of the parameter-schedule gap would be to impose $\\beta \\le \\alpha$ explicitly (equivalently $K^{1/3} \\le 8(D+1/2)$) or to extend the proof to signed, non-stochastic mixing weights; the same Lyapunov argument may survive signed weights because only symmetry and spectral properties enter the consensus term.","The gap between the $O(1/K^{1/3})$ rate and SGD's $O(1/\\sqrt{K})$ is entirely the consensus-error term $O(\\alpha)$, so a testable extension is whether a gradient-tracking or momentum variant of the same ASBCD equivalence closes that gap while keeping delay-free step sizes.","The equivalence suggests a recipe for other decentralized methods: any update that is a gossip mix plus a local stochastic step can be analyzed as block coordinate descent on an augmented objective, potentially transferring delay-robustness results between algorithms.","An easy empirical isolation: run the method with the ratio fixed at $\\beta/\\alpha = 1$ so that $\\tilde{W}$ is always a true averaging matrix, and compare with the unconstrained Corollary 3.12 schedule to see whether the theoretical invalidity at large $K$ shows up in practice."],"forward_implications":["If the bound is right, non-convex asynchronous decentralized SGD no longer needs step sizes that shrink with the computation-delay bound $B$; the schedule $\\beta = 1/(4L_F(D+1/2)K^{2/3})$ is explicit and implementable.","The convergence guarantee covers arbitrarily skewed data partitions, since only each local loss must be bounded below rather than bounded data heterogeneity being assumed.","Per-iteration communication drops to one model broadcast per node update and memory to $O(|N_i|)$ plus the local iterate, about half to a third of the budget of gradient-tracking alternatives.","ASBCD achieves the $O(1/\\sqrt{K})$ non-convex rate of standard SGD, bringing asynchronous stochastic coordinate descent in line with the synchronous baseline for the first time.","In the reported experiments, ADSGD reaches target test accuracy 15–70% faster than asynchronous baselines and 30–85% faster than synchronous ones under straggler settings, with larger advantages under communication delays."],"supporting_citations":[{"why":"Supplies the asynchronous-coordinate-descent template whose Theorem 1 is generalized to stochastic gradients in Lemma 3.8.","marker":"[19]"},{"why":"Establishes the DGD-as-block-coordinate-descent equivalence, which the paper extends to asynchronous stochastic settings.","marker":"[26]"},{"why":"Presents the prior asynchronous decentralized SGD (ADPSGD) that requires partial synchronization and serves as the main comparison baseline.","marker":"[10]"},{"why":"Gives the tracking-based fully asynchronous method (RFAST) whose delay-dependent, extremely small step-size bound motivates the delay-free schedule.","marker":"[29]"},{"why":"Analyzes a tracking-based asynchronous non-convex method whose step-size bound is contrasted with ADSGD's schedule.","marker":"[7]"},{"why":"Achieves the closest prior computation-delay-independent step-size result, but only for strongly convex objectives with diminishing step sizes.","marker":"[18]"}],"fun_headline_variants":["Delay-free steps for async decentralized SGD","Nonconvex async SGD: step sizes free of delay bounds","Block-coordinate proof: delay-free async decentralized SGD","ADSGD converges without compute-delay-dependent steps","Async decentralized SGD: delay-free step sizes for nonconvex"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the assertion in Section 3.3 that the effective mixing matrix $\\tilde{W} = (1-\\beta/\\alpha)I + (\\beta/\\alpha)W$ satisfies Assumption 3.7, namely symmetry and stochasticity, which holds only while the two step sizes obey $\\beta \\le \\alpha$; the paper's own Corollary 3.12 schedule has $\\beta/\\alpha = K^{1/3}/(8(D+1/2)) > 1$ for large $K$, so in that regime the recursion being analyzed is not a well-defined instance of the algorithm the assumptions describe.","fun_headline_variants_meta":{"raw":{"variants":["Delay-free steps for async decentralized SGD","Nonconvex async SGD: step sizes free of delay bounds","Block-coordinate proof: delay-free async decentralized SGD","ADSGD converges without compute-delay-dependent steps","Async decentralized SGD: delay-free step sizes for nonconvex"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001893,"raw_usage":{"total_tokens":7412,"prompt_tokens":926,"completion_tokens":6486,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":6410}},"tokens_in":542,"tokens_out":6486,"duration_ms":41596,"temperature":1.0,"reasoning_tokens":6410,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:13:29.706178+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a 9-agent grid network with uniform gossip weights ($W_{ii} = 0.2$ at the center node), set $D = 1$ and $B = 1$, and run the Corollary 3.12 schedule out to $K = 20{,}000$ iterations. Then $\\beta/\\alpha = K^{1/3}/(8(D+1/2)) \\approx 2.26$, and the constructed matrix has center-node diagonal entry $1 - \\beta/\\alpha + (\\beta/\\alpha)(0.2) \\approx -0.81$, a negative value that violates stochasticity. Simply computing $\\tilde{W}$ for these parameters and checking nonnegativity and row sums settles whether the theorem analyzes a legal instance of Algorithm 2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the asynchronous-coordinate-descent template whose Theorem 1 is generalized to stochastic gradients in Lemma 3.8."},{"cited_title":"and Yin, W","cited_arxiv_id":null,"evidence_quote":"Establishes the DGD-as-block-coordinate-descent equivalence, which the paper extends to asynchronous stochastic settings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents the prior asynchronous decentralized SGD (ADPSGD) that requires partial synchronization and serves as the main comparison baseline."},{"cited_title":"Robust Fully-Asynchronous Methods for Distributed Training over General Architecture","cited_arxiv_id":"2307.11617","evidence_quote":"Gives the tracking-based fully asynchronous method (RFAST) whose delay-dependent, extremely small step-size bound motivates the delay-free schedule."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Analyzes a tracking-based asynchronous non-convex method whose step-size bound is contrasted with ADSGD's schedule."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Achieves the closest prior computation-delay-independent step-size result, but only for strongly convex objectives with diminishing step sizes."}],"review_version":1}