{"id":"fe5e1865-101b-42c0-a48e-03a742ef6ae3","arxiv_id":"2502.08964","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A two-timescale compressed primal-dual algorithm, TiCoPD, provably converges on random, noisy, bandwidth-limited networks without the bounded-heterogeneity assumption.","lead":"This paper introduces a decentralized optimization algorithm that keeps agents coordinated even when communication links fail, are bandwidth-limited, or add noise. It is proven to converge for smooth nonconvex objectives and is tested on linear regression, synthetic losses, and ImageNet training.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem IV.5 analyzes the global surrogate recursion (19), but Algorithm 1's per-edge local copies are neither shown to realize (19) nor made well-defined without an extra assumption; an inactive-edge example shows they diverge.","rationale":"The paper's central theoretical claim is that the TiCoPD algorithm, as presented in Algorithm 1, achieves the stated convergence rates. The proof, however, is built on the global surrogate recursion (19), where a single vector X̂ is updated every iteration and is used directly in the primal-dual updates. Algorithm 1 is described as a decentralized implementation of that recursion via per-edge local copies, but the connection between the two is asserted rather than proven. The divergence is concrete: inactive edges freeze the local copies, while the global recursion continues to update; independent per-message noise can also make copies initialized identically drift apart. Without an argument that the local-copy aggregate is stochastically dominated by the analyzed quantity, Theorem IV.5 does not cover the implemented algorithm. This is a load-bearing gap because the theorem, not the numerics, is the paper's main evidence that Algorithm 1 converges under unreliable networks. The numerical experiments are encouraging and the overall framework is plausible, but they do not resolve the mismatch, especially since no code is provided. The reader's weakest-assumption analysis identifies the same gap, and the proposed conditional verdict remains the appropriate outcome: the authors should either prove that Algorithm 1 realizes (19) under the stated assumptions, or revise the analysis to match the local-copy implementation.","tokens_in":28183,"tokens_out":20290,"duration_ms":192629,"concrete_test":"Consider the one-edge graph {1,2} and any iteration t where the edge is inactive. Global (19) updates X̂_2^{t+1} = X̂_2^t + γQ_2(X_2^{t+1}-X̂_2^t), while Algorithm 1 leaves x̂_{1,2}^{t+1} = x̂_{1,2}^t because no message is received. Initialize both identically; for any realization with nonzero Q_2, the local copy and the global component differ. Implement this example with the paper's randomized quantization (15) and one inactive slot, and record that the difference is nonzero; this directly falsifies the claim that Algorithm 1 realizes (19) and shows that Lemma IV.11's premise fails for Algorithm 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem IV.5 and its supporting Lemmas IV.8-IV.12 analyze the global surrogate recursion X̂^{t+1} = X̂^t + γQ(X^{t+1}-X̂^t; ξ_q^{t+1}) from (19), with Lemma IV.11 bounding E‖X̂^{t+1}-X^{t+1}‖² under exactly that recursion. Algorithm 1 instead maintains per-directed-edge local copies x̂_{i,j}^t, updated only on active edges by x̂_{i,j}^t = x̂_{i,j}^{t-1} + γQ(x_j^t - x̂_{i,j}^{t-1}; ξ_{q,j}^t), and then feeds x̂_{j,i}^t - x̂_{i,j}^t into (20)-(21). The paper never proves that the aggregate ∑_{j∈N_i^t}(x̂_{j,i}^t - x̂_{i,j}^t) equals (Ā^T Ā(ξ_a^{t+1})X̂^t)_i for some X̂^t satisfying (19). It does not: if edge (i,j) is inactive at iteration t, Algorithm 1 keeps x̂_{i,j}^t = x̂_{i,j}^{t-1}, while the global component X̂_j in (19) continues to evolve; stale copies therefore diverge from the analyzed sequence. Moreover, the message argument in step 6 is Q(x_j^t - x̂_{i,j}^{t-1}), a quantity stored at the receiver i; the pseudo-code does not explain how transmitter j can evaluate this receiver-dependent value, so Algorithm 1 is not a self-contained distributed protocol without an additional assumption such as identical synchronized copies. Consequently, the convergence bound (29) is established only for the idealized global recursion, not for Algorithm 1 as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TiCoPD, a two-timescale compressed primal-dual method for decentralized minimization of a smooth (possibly nonconvex) sum of local objectives over random time-varying graphs with compressed and possibly noisy communication. A surrogate sequence is updated on a fast timescale using a contractive compressor, while primal and dual variables move on a slow timescale. Theorem IV.5 gives, under Assumptions III.1 and IV.1-IV.4 and step-size conditions (28), an expected squared-gradient bound (29); the authors specialize it to O(sqrt(sigma_bar^2/(nT))) for noiseless compressed communication and O((1+sigma_xi^2)/T^{1/3}) for noisy compressed communication, without bounded data heterogeneity. Numerical experiments on linear regression, nonconvex sigmoid loss, and ResNet-50/ImageNet training are reported.","tokens_in":28563,"tokens_out":11148,"duration_ms":103668,"significance":"If Theorem IV.5 covers the algorithm as implemented, the contribution is significant: TiCoPD would be the first stochastic primal-dual method to handle time-varying random graphs, general contractive compressors, and noisy communication simultaneously, with rates comparable to centralized SGD in the noiseless case. The proof is largely self-contained, the step-size conditions are explicit, and the claimed rates follow from stated choices rather than from fitted parameters. However, the certificate currently applies to an idealized global surrogate recursion and not to the local-copy protocol in Algorithm 1; this gap must be closed before the advertised claims are established.","major_comments":[{"comment":"No equivalence is shown between the per-edge local copies updated in Algorithm 1, Step 6 and the global surrogate recursion (19) analyzed in Lemma IV.11. In Algorithm 1, xhat_{i,j}^t is updated only when edge (i,j) is active and uses x_j^t - xhat_{i,j}^{t-1}; if the edge is inactive at iteration t, the copy remains frozen, whereas the corresponding component of the global Xhat^t in (19) continues to evolve. Consequently, the quantity E||Xhat^t - X^t||^2 bounded in Lemma IV.11 need not control the surrogate error actually entering (20)-(21), and Theorem IV.5's bound (29) is not established for Algorithm 1 as written.","section":"Section III (Algorithm 1) vs Section IV (Lemmas IV.8-IV.12, Theorem IV.5)"},{"comment":"The implemented surrogate update is one step ahead of the analyzed one: Algorithm 1 updates xhat_{i,j}^t before computing x_i^{t+1}, using x_j^t, and then uses xhat^t in (20)-(21), while the global recursion (19) uses Xhat^t in the X-update and forms Xhat^{t+1} only from X^{t+1}. Even under a hypothetical identification of the local copies with a global Xhat, the sequence entering the primal-dual update is not the sequence whose tracking error Lemma IV.11 bounds; the authors need to align the indexing or prove a separate bound for the shifted sequence.","section":"Section IV, Lemma IV.11 and equation (19); Algorithm 1, Steps 6-7"},{"comment":"The protocol is not self-contained as written: Step 6 instructs agent i to receive Q(x_j^t - xhat_{i,j}^{t-1}; xi_{q,j}^t), but xhat_{i,j}^{t-1} is a quantity defined at the receiver i, and the pseudo-code does not specify how transmitter j knows this receiver-dependent value. The remark that the step is 'also performed at the transmitter side' is insufficient; either a mirrored-copy assumption must be added, or the update rule must be redefined in terms of information available to the transmitter.","section":"Algorithm 1, Step 6"}],"minor_comments":[{"comment":"The caption refers to a 'non-sigmoid loss minimization problem'; this appears to be a typo for 'non-convex sigmoid loss minimization problem'.","section":"Section V-B, Figure 3 caption"},{"comment":"The text says the randomized quantizer in (15) uses s=24 levels, while the figures and legends describe the method as '4-bits'; for QSGD, the per-coordinate cost is about log2(s) bits plus the transmitted norm, so 24 levels is not 4 bits, and the labeling should be reconciled.","section":"Section V, randomized quantization parameters"},{"comment":"ResNet-50 has approximately 25.6 million parameters, not 2.56 x 10^9 parameters as stated; the number should be corrected.","section":"Section V-C"},{"comment":"Line 5 draws the compressor randomness xi_{q,i}^{t+1}, while Step 6 uses xi_{q,j}^t; the time indexing of the compressor randomness should be unified.","section":"Algorithm 1, lines 5-6"},{"comment":"In the rate specializations, the free constant a is only described as being of a given order in T; to make the bounds fully explicit, the authors should state the concrete values of a used in each case, since the step-size condition (28) involves a through theta_lb.","section":"Section IV, Remark after Theorem IV.5"}],"recommendation":"major_revision","confidential_remarks":"I see no indication of citation manipulation or scope mismatch; the main issue is technical. The paper could become publishable if the authors close the gap between Algorithm 1 and the analyzed global recursion, either by proving an equivalence or by modifying the algorithm and analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the quick read. The paper has a real contribution: TiCoPD is, as far as this comparison table shows, the first decentralized stochastic primal-dual method that handles random graphs, general contractive compressors, and noisy channels all at once, without bounded heterogeneity. The rates are right: O(1/sqrt(nT)) for noiseless compressed communication and O(T^{-1/3}) with communication noise. The majorization-minimization reading of error feedback is a nice conceptual lens and should be useful beyond this paper. The proof is dense but explicit; step-size conditions are spelled out. If the analysis is sound, the rates are state-of-the-art for this problem class.\n\nThe main problem is that the theorem and the algorithm as written are not the same object. Theorem IV.5 analyzes the global surrogate recursion (19), where \\hat X updates every iteration. Algorithm 1 maintains per-edge local copies \\hat x_{i,j} that are updated only when the edge is active. No argument shows the local copies realize the global recursion, and they do not in general: an inactive edge leaves the copy frozen while the global \\hat X keeps evolving. There's also a distributed-communication issue in step 6: the message Q(x_j^t - \\hat x_{i,j}^{t-1}) depends on the receiver's private copy, so the transmitter cannot evaluate it. The note that the same step is performed at the transmitter side doesn't resolve this without an extra assumption like synchronized copies. So the convergence guarantee (29) is established for an idealized recursion, not for the pseudo-code. The stress-test note is right. This is a load-bearing gap, not a typo.\n\nMinor things: the experiments have a few reporting inconsistencies (s=24 quantization levels versus the 4-bit label; the 'non-sigmoid' typo in Fig. 3), and no code is released. Those are secondary.\n\nNet: the idea is worth taking seriously and the gap looks repairable—either prove the local-copy implementation satisfies the analyzed recursion (perhaps under a different edge-activation model) or change the algorithm to match the analysis. A serious referee should get this, with a request for major revision and code. I wouldn't cite it as-is, but I'd follow it.","headline":"TiCoPD is a novel and well-analyzed primal-dual method with state-of-the-art rates, but the convergence theorem analyzes a global surrogate recursion that Algorithm 1's local-copy implementation does not provably realize; the gap is repairable.","tokens_in":29128,"tokens_out":6367,"would_cite":false,"duration_ms":58155,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C26","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a two-timescale compressed primal-dual algorithm, TiCoPD, finds epsilon-stationary solutions of smooth nonconvex decentralized optimization problems at centralized-SGD speed, even when networks have random links…","keywords":["decentralized optimization","compressed communication","two-timescale update","primal-dual algorithm","nonconvex optimization","random graphs","noisy channels","stochastic gradients"],"falsifier":"Implement Algorithm 1 exactly on a two-agent network with one alternating active edge, random quantization, exact gradients, and noiseless channels; measure the consensus error $\\|X^t\\|_K^2$ over $T$ iterations. The noiseless-exact-gradient case of Theorem IV.5 predicts a decay rate $O(1/(\\delta^2 T))$; if the measured quantity consistently decays slower than the constants in (29) allow, the implemented local-copy algorithm is not the global recursion being analyzed.","tokens_in":27959,"feed_emoji":"📡","tokens_out":9125,"duration_ms":80731,"temperature":0.7,"pith_summary":"The paper introduces TiCoPD, a two-timescale compressed primal-dual algorithm for decentralized stochastic optimization over unreliable networks. It claims that, for smooth and possibly non-convex objective functions, TiCoPD finds an epsilon-stationary solution: the averaged squared gradient norm decays like $O(\\sqrt{\\bar\\sigma^2/(nT)})$ when communication is compressed but noiseless, matching centralized SGD with a minibatch of size $n$, and degrades to $O((1+\\sigma_\\xi^2)/T^{1/3})$ when channels add noise. These rates hold over random time-varying graphs and general contractive compressors, and they do not require the bounded data-heterogeneity assumption used by earlier compressed decentralized algorithms. The key design is a majorization-minimization step that moves the network-consensus penalty onto a surrogate sequence updated on a fast timescale, leaving a slow primal-dual recursion to handle the objective.","feed_headline":"Two-timescale updates match SGD speed on unreliable networks","feed_subtitle":"Compressed primal-dual hits 1/sqrt(nT) stationarity, or 1/T^(1/3) with noisy links—no heterogeneity assumption.","key_machinery":"The central mechanism is the two-timescale surrogate tracking loop $\\hat X^{t+1} = \\hat X^t + \\gamma Q(X^{t+1} - \\hat X^t; \\xi_q)$ running in parallel with the slow primal-dual recursion (19). $Q$ is a contractive compressor with additive zero-mean noise satisfying Assumption III.1: it can be a randomized quantizer, a top-$k$ sparsifier, or an adaptive quantizer, and the parameter $\\delta \\in (0,1]$ measures contraction while $\\sigma_\\xi^2$ bounds transmission noise. The majorization-minimization step replaces the quadratic penalty $\\theta\\|\\bar A(\\xi_a)X\\|^2$ with a term linear in the surrogate, $\\theta(\\bar A^\\top\\bar A(\\xi_a)\\hat X)^\\top X$, so agents only need to exchange compressed differences of $\\hat X$. The proof builds a potential function $F_t = f(\\bar x^t) + a\\|X^t\\|_K^2 + b\\|v^t\\|^2_{\\bar Q+cK} + d\\langle X^t, v^t\\rangle_K + e\\|\\hat X^t - X^t\\|^2$ and shows via Lemmas IV.7-IV.12 that it decreases by at least $\\alpha \\|\\nabla f(\\bar x^t)\\|^2/16$ per iteration, up to gradient-variance and communication-noise terms.","core_discovery":"TiCoPD is a stochastic primal-dual method whose updates are the recursion (19): $X^{t+1}=X^t-\\alpha(\\nabla f(X^t;\\xi^{t+1})+\\lambda^t+\\theta\\bar A^\\top\\bar A(\\xi_a)\\hat X^t)$, $\\lambda^{t+1}=\\lambda^t+\\eta\\bar A^\\top\\bar A(\\xi_a)\\hat X^t$, and $\\hat X^{t+1}=\\hat X^t+\\gamma Q(X^{t+1}-\\hat X^t;\\xi_q)$. The surrogate $\\hat X$ tracks $X$ through compressed differences $Q(\\cdot)$, an auxiliary recursion that converges faster than the optimization steps because $\\gamma \\gg \\max\\{\\alpha,\\eta\\}$. Theorem IV.5 bounds the average squared gradient norm by $(F_0-f^\\star)/(\\alpha T/16)+16\\alpha\\omega_\\sigma\\bar\\sigma^2+128a\\gamma^2\\sigma_\\xi^2\\tilde\\rho_{\\max}/(\\alpha\\rho_{\\min})$, and the corollaries give $O(\\sqrt{\\bar\\sigma^2/(nT)})$ for noiseless compressed communication and $O((1+\\sigma_\\xi^2)/T^{1/3})$ for noisy communication. The paper argues this is the first stochastic primal-dual algorithm for decentralized optimization on random graphs that supports general contractive compressors and noisy compressed transmission without a bounded-heterogeneity assumption, and it interprets the construction as a majorization-minimization derivation of error-feedback compression linked to nonlinear gossiping.","pith_inferences":["Editorial inference: a gap the paper leaves open is that the per-edge local copies in Algorithm 1 may not coincide with the global surrogate recursion studied in the proof, so the theory's coverage of the implemented algorithm is not established.","Editorial inference: if the local-copy gap is real, it could be closed by showing the local copies are stochastic approximations of the global sequence with controlled variance, or by re-deriving the bounds for the local update.","Editorial inference: the MM view suggests that other consensus-constrained formulations, such as ADMM or accelerated primal-dual schemes, could gain compressed and noise-robust variants by introducing a similarly fast surrogate loop.","Editorial inference: a testable extension would replace the fixed step sizes with a decreasing schedule for $\\gamma$, which might push the noisy-communication rate closer to $O(1/\\sqrt{T})$."],"forward_implications":["With noiseless compressed transmission, TiCoPD achieves the same asymptotic bound on $\\mathbb{E}[\\|\\nabla f(\\bar x_R)\\|^2]$ as centralized SGD with a minibatch of size $n$, giving linear speedup over random graphs.","With noisy compressed transmission, the algorithm still converges at rate $O((1+\\sigma_\\xi^2)/T^{1/3})$ and to a neighbourhood whose radius is controlled by $\\gamma^2 \\sigma_\\xi^2/(\\alpha \\rho_{\\min})$.","TiCoPD supports general contractive compressors, including random quantization, top-$k$ sparsification, and adaptive quantizers, under a single assumption and without requiring bounded gradient heterogeneity.","The majorization-minimization derivation gives a principled recipe for adding compression to primal-dual schemes that lack an explicit averaging step."],"supporting_citations":[{"why":"Supplies the proximal primal-dual recursion that TiCoPD extends with a surrogate variable and compression.","marker":"[18]"},{"why":"Defines the contractive compressor model and the CHOCO-SGD baseline that TiCoPD improves upon.","marker":"[32]"},{"why":"Inspires the nonlinear gossip view that justifies the fast surrogate recursion.","marker":"[43]"},{"why":"Provides the randomized quantization operator used as a canonical compressor example in the paper.","marker":"[46]"},{"why":"The DIMIX baseline for noisy communication whose rate TiCoPD is compared against and improves.","marker":"[38]"},{"why":"The primal-dual algorithm on random graphs that TiCoPD extends to general compressors and noise.","marker":"[36]"},{"why":"The DSGD baseline that provides the uncompressed random-graph comparison and the known $O(\\bar\\sigma/\\sqrt{nT})$ rate.","marker":"[10]"}],"fun_headline_variants":["Two-timescale compressed method matches SGD on unreliable nets","No heterogeneity assumption: compressed decentralized optimization works","First algorithm for random-graph decentralized learning with noisy compression","Compressed primal-dual: robust to noise, no bounded heterogeneity","Two-timescale primal-dual achieves optimal rates under compressors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof analyzes the global surrogate recursion in equation (19), but Algorithm 1 actually implements per-edge local copies $\\hat x_{i,j}$; no argument in the paper shows those local copies realize the analyzed global recursion, so the convergence theorem may not cover the algorithm as written.","fun_headline_variants_meta":{"raw":{"variants":["Two-timescale compressed method matches SGD on unreliable nets","No heterogeneity assumption: compressed decentralized optimization works","First algorithm for random-graph decentralized learning with noisy compression","Compressed primal-dual: robust to noise, no bounded heterogeneity","Two-timescale primal-dual achieves optimal rates under compressors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000316,"raw_usage":{"total_tokens":1815,"prompt_tokens":999,"completion_tokens":816,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":615,"completion_tokens_details":{"reasoning_tokens":736}},"tokens_in":615,"tokens_out":816,"duration_ms":8945,"temperature":1.0,"reasoning_tokens":736,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T23:05:21.676061+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement Algorithm 1 exactly on a two-agent network with one alternating active edge, random quantization, exact gradients, and noiseless channels; measure the consensus error $\\|X^t\\|_K^2$ over $T$ iterations. The noiseless-exact-gradient case of Theorem IV.5 predicts a decay rate $O(1/(\\delta^2 T))$; if the measured quantity consistently decays slower than the constants in (29) allow, the implemented local-copy algorithm is not the global recursion being analyzed.","supporting_citations":[{"cited_title":"Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization,","cited_arxiv_id":null,"evidence_quote":"Supplies the proximal primal-dual recursion that TiCoPD extends with a surrogate variable and compression."},{"cited_title":"Decentralized stochastic op- timization and gossip algorithms with compressed communication,","cited_arxiv_id":null,"evidence_quote":"Defines the contractive compressor model and the CHOCO-SGD baseline that TiCoPD improves upon."},{"cited_title":"Nonlinear gossip,","cited_arxiv_id":null,"evidence_quote":"Inspires the nonlinear gossip view that justifies the fast surrogate recursion."},{"cited_title":"Qsgd: Communication-efficient sgd via gradient quantization and encoding,","cited_arxiv_id":null,"evidence_quote":"Provides the randomized quantization operator used as a canonical compressor example in the paper."},{"cited_title":"Dimix: Diminishing mixing for sloppy agents,","cited_arxiv_id":null,"evidence_quote":"The DIMIX baseline for noisy communication whose rate TiCoPD is compared against and improves."},{"cited_title":"A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks","cited_arxiv_id":"2410.18774","evidence_quote":"The primal-dual algorithm on random graphs that TiCoPD extends to general compressors and noise."},{"cited_title":"A unified theory of decentralized sgd with changing topology and local updates,","cited_arxiv_id":null,"evidence_quote":"The DSGD baseline that provides the uncompressed random-graph comparison and the known $O(\\bar\\sigma/\\sqrt{nT})$ rate."}],"review_version":1}