{"id":"e8583432-2e33-4eef-92b3-f52430be2abb","arxiv_id":"2501.07967","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Convergence bounds for decentralized gradient tracking using approximate finite-time consensus matrices show that approximation error continuously degrades consensus and steady-state error.","lead":"The paper derives convergence bounds for decentralized gradient tracking when agents use approximate finite-time consensus matrices, showing that approximation error degrades performance in a quantified way. It matters because approximate consensus matrices can be constructed for arbitrary graphs, unlike exact finite-time consensus sequences, which are only known in closed form for special graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1 is false: the full-period product of the block-triangular consensus matrices has norm ∥P∥·∥T_τ∥ with ∥T_τ∥>1 for τ≥2, so the claimed contraction factor ϵτ in Theorem 1 is unsupported.","rationale":"The reader's weakest assumption identifies exactly the load-bearing defect. I independently re-derived the full-period product: because each term B_τ⋯B_{j+1}B_jB_{j-1}⋯B_1 equals the same product P_τ, the upper-right block of G_τ⋯G_1 is -τP_τ, not 0. Therefore the block-triangular norm identity is misapplied: it bounds the diagonal blocks, not the full product after multiplication. The paper marks Theorem 1's proof as omitted, and Lemma 1 is the only stated justification for the exponential contraction; no other argument or numerical validation of the contraction rate is supplied. The simulations show qualitative agreement with the claimed dependence on ϵτ, but they do not test Lemma 1 or the sizes of the off-diagonal terms. The idea may be salvageable by replacing Lemma 1 with a corrected bound of the form ∥G product∥ ≤ ∥T_τ∥·ϵτ and imposing a correspondingly stronger smallness condition, but that is not in the manuscript. Hence the verdict of REJECT is appropriate, and no adjustment is needed.","tokens_in":7725,"tokens_out":8017,"duration_ms":81416,"concrete_test":"Take any approximate-FTC sequence with τ=2 and ϵτ=δ>0, e.g., two doubly-stochastic matrices on a 4-agent cycle. Form B_i = bI A_i and compute the spectral norm of G_2G_1 = [[B₂B₁, -2B₂B₁],[0,B₂B₁]]. The exact formula gives ∥G_2G_1∥ = δ·√(3+2√2) ≈ 2.414δ, contradicting Lemma 1's claim that ∥G_2G_1∥ ≤ δ. This is a one-line numerical check that settles the issue for any nonzero δ.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 1 is the linchpin: Theorem 1's exponentially decaying consensus term requires ∥G_{i:mτ+1}∥ ≤ ϵτ. But the product over one full FTC period has the exact structure [[P, -τP],[0,P]] with P = bA_{mτ+τ}⋯bA_{mτ+1}. Writing it as (I₂⊗P)(T_τ⊗I), with T_τ = [[I,-τI],[0,I]], its spectral norm is ∥P∥·∥T_τ∥. For τ≥2, ∥T_τ∥ = sqrt((τ²+2+τ√(τ²+4))/2) > 1 (τ=2: √(3+2√2) ≈ 2.414), so ∥G_{i:mτ+1}∥ = ϵτ·∥T_τ∥ > ϵτ. The off-diagonal block in the product is not zero; it scales as -τP. Thus Lemma 1's assertion, and its appeal to the block-triangular norm identity, are incorrect, and the contraction factor in Theorem 1 is not established. Since Theorem 2 inherits this step through the consensus bound, the central quantitative claim of the paper does not follow from the stated argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the Aug-DGM decentralized optimization algorithm when the combination matrices form an approximate finite-time consensus (FTC) sequence, i.e., a cyclic sequence whose τ-step product equals (1/K)11^T plus an error of norm ϵτ. It states two theorems: Theorem 1 bounds the mean-square consensus error by an exponential term with contraction factor (3/8)ϵτ(2+3ϵτ) plus steady-state terms proportional to μ²Kτ²B²/(1-ϵτ)² and μ²τ²σ²/(1-ϵτ)²; Theorem 2 bounds the centroid error to the optimum, with similar 1/(1-ϵτ)² dependencies. The paper also provides simulation results for logistic regression on a path graph and a hypercube, and argues that larger ϵτ or larger τ degrades performance. The central analytical tool is Lemma 1, which claims that the product of the block-triangular consensus-error matrices over a τ-period has spectral norm at most ϵτ.","tokens_in":8011,"tokens_out":16816,"duration_ms":149857,"significance":"The question addressed — how approximation error in finite-time consensus matrices degrades the performance of decentralized learning — is a sensible and timely one, since exact FTC sequences are known only for special graphs and a theory for approximate FTC would broaden applicability. If the bounds were correct, they would provide a useful design rule: faster mixing (smaller ϵτ) and smaller consensus number τ are beneficial, and performance degrades continuously with ϵτ. The paper also gives clear empirical demonstrations that the predicted monotonicity in ϵτ and τ holds in simulation. However, the correctness of the theoretical claims is not established: Lemma 1 is false, and the main theorems are stated without proofs. The empirical observations may be valid, but the theoretical contribution as stated is not supported.","major_comments":[{"comment":"The asserted bound ∥G_{i:mτ+1}∥ ≤ ϵτ is not justified and is in fact false in general. The argument relies on the claim that the spectral norm of a block triangular matrix equals the maximum spectral norm of its diagonal blocks; this is true for the spectral radius but not for the spectral norm. For the specific structure G_i = [[bA_i, -bA_i],[0,bA_i]] in (14c), an induction shows that the product over r steps equals [[Q, -rQ],[0,Q]] with Q = bA_i...bA_{i-r+1}. Its spectral norm is ||T_r ⊗ Q|| = ||T_r|| · ||Q||, where T_r = [[1,-r],[0,1]]. For one full period (r = τ), Q = bI(A_τ...A_1) = bI E, and since E in (5) has zero row and column sums, ||Q|| = ||E|| = ϵτ. Hence ∥G_{i:mτ+1}∥ = ||T_τ|| · ϵτ > ϵτ for every τ ≥ 1 (e.g., ||T_2|| ≈ 2.414, ||T_3|| ≈ 3.303). The off-diagonal block -τQ is not negligible and cannot be discarded. Because Lemma 1 is the sole stated basis for the per-period contraction, the exponential decay term in Theorem 1 (Eq. (19a)) and the (1-ϵτ)^-2 denominators in (19a) and (23a) are unsupported. Theorem 2 inherits this gap through its dependence on Theorem 1.","section":"Section II-C, Lemma 1 (Eq. (16))"},{"comment":"The two main results are not proven in the manuscript. Theorem 1 ends with 'Proof: Omitted due to space limitations', and Theorem 2 is stated without any proof. The constants (432, 144, 1728, 576, β4, β5) and the step-size conditions μ ≤ min{ν/δ², (1/(12δ²))√((1-ϵτ)/(τ(2τ-1)(1+ϵτ)))} are therefore not verifiable. Even if Lemma 1 were correct, a journal submission must either include the proofs or provide them in a separately accessible supplement. The current omission leaves the reader unable to check the chain of inequalities leading to (19a)–(23b), and it is particularly problematic for a paper whose main contribution is exactly these bounds.","section":"Sections II-C and II-D (Theorems 1 and 2)"}],"minor_comments":[{"comment":"The phrase 'The evolution of the consensus error error' contains a duplicated 'error'; it should read 'The evolution of the consensus error'.","section":"Section II-C, first paragraph"},{"comment":"The matrix norm ∥·∥ is not defined. The subsequent bounds require the spectral norm; please state this explicitly and use the same norm throughout the paper.","section":"Eq. (5)"},{"comment":"The quantity γ2 is defined just below (23a) but it is not used in the bound; the expression uses γ3 = max(γ1,γ2). Please remove γ2 or use it consistently.","section":"Theorem 2 (Section II-D)"},{"comment":"Given that the proofs are omitted, the paper would benefit from at least a proof sketch for Theorems 1 and 2 to indicate how the stated constants and step-size conditions arise, and in particular how Lemma 1 is intended to be used.","section":"General"}],"recommendation":"reject","confidential_remarks":"The false Lemma 1 is a load-bearing mathematical error, not a typo: the norm of the τ-step product of the block-triangular consensus matrices is inflated by the factor ||T_τ|| > 1, so the claimed contraction is not a consequence of the stated assumptions. In addition, the absence of proofs for Theorem 1 and Theorem 2 makes it impossible to assess whether a corrected contraction bound could still yield the claimed rates. This motivates rejection rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper addresses a real gap: exact finite-time consensus (FTC) sequences are known only for structured graphs, so a theory for approximate FTC sequences would be broadly useful. The authors correctly identify epsilon_tau as the right quality measure, and the qualitative prediction that approximation error degrades performance continuously is plausible and consistent with the simulations. The reformulation of Aug-DGM follows the sensible precedent in Nguyen et al. So the problem is well chosen and the narrative is honest.\n\nThat is where the good news ends. The central contraction step, Lemma 1, is false. It claims that the spectral norm of the full tau-period product of the block-triangular consensus matrices is bounded by epsilon_tau, citing the textbook claim that the norm of a block triangular matrix equals the maximum norm of its diagonal blocks. That identity is not true in general, and here the off-diagonal block is not zero. Over one period the product has the form [[P, -tau P],[0,P]] with P the product of the diagonal blocks, so its norm is ||P|| * ||T_tau||, where ||T_tau|| > 1 for tau >= 2. For tau=2 the factor is about 2.414. Thus ||G_{i:m tau+1}|| is not bounded by epsilon_tau, and the exponential contraction term in Theorem 1 is unsupported. The stress-test note is correct, and it lands directly on the main theorem.\n\nThe other major problem is that neither main theorem is actually proven. Theorem 1 ends with \"Proof: Omitted due to space limitations,\" and Theorem 2 has no proof at all. In a conference paper that is sometimes acceptable if the full proof is in an appendix or supplementary material, but here it is simply absent. The reader is being asked to take the two central results on faith. The simulations are illustrative, but they cannot substitute for a derivation, especially when the one lemma that is stated turns out to be wrong.\n\nThere are smaller issues too: the step-size condition and constants seem to come out of nowhere, and the comparison with the exact-FTC case is not enough to establish the claimed O(tau^2) behavior. None of that matters much, because the false lemma already sinks the argument as written.\n\nWho is this for? A researcher actively working on finite-time consensus might want to know that the approximate-FTC direction is worth pursuing, and the experimental evidence for the qualitative trend is mildly encouraging. But as a source of quantitative guarantees, the paper is not usable.\n\nMy recommendation: desk reject with a clear explanation. The central lemma is demonstrably false, so sending this to referees would waste their time. The right path is to invite the authors to resubmit a complete version with a corrected contraction proof and the full derivations for Theorems 1 and 2. The underlying idea is salvageable, but this manuscript does not yet carry the weight of its claims.","headline":"The qualitative question is worth asking, but the paper's central convergence bounds rest on a false lemma and omitted proofs, so the results do not stand as stated.","tokens_in":8497,"tokens_out":3740,"would_cite":false,"duration_ms":37378,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Approximate finite-time consensus sequences retain provable convergence bounds for decentralized gradient tracking.","keywords":["decentralized optimization","finite-time consensus","gradient tracking","approximate consensus","Aug-DGM","mean-square convergence","combination matrices","distributed learning"],"falsifier":"Compute $\\|\\mathcal{G}_{i:m\\tau+1}\\|$ for a small graph with a known approximate FTC product whose diagonal block product has norm $\\epsilon_\\tau$ but whose off-diagonal blocks are nonzero; if the full norm exceeds $\\epsilon_\\tau$, Lemma 1 fails. A numerical check of Theorem 1 would run Aug-DGM on a graph with $\\tau=4$, measure the consensus error every $\\tau$ iterations, and see whether the decay factor obeys $\\frac{3}{8}\\epsilon_\\tau(2+3\\epsilon_\\tau)$ or is controlled by the true product norm instead.","tokens_in":7549,"feed_emoji":"🤝","tokens_out":6471,"duration_ms":61344,"temperature":0.7,"pith_summary":"This paper asks whether decentralized optimization still has provable guarantees when the combination matrices only approximately achieve finite-time consensus (FTC), meaning their product is close to the scaled all-ones matrix but not exactly equal to it. Exact FTC sequences are known in closed form only for special graphs, so an approximation is the practical route for general networks. The authors study the Aug-DGM gradient-tracking algorithm with approximate FTC matrices and derive mean-square bounds showing that consensus error decays every $\\tau$ iterations at a rate controlled by $\\epsilon_\\tau$, with steady-state error growing like $\\mu^2 \\tau^2/(1-\\epsilon_\\tau)^2$. The conclusion is positive: approximate FTC sequences can be certified by a single scalar $\\epsilon_\\tau$ and remain viable on arbitrary graphs.","feed_headline":"Approximate FTC keeps decentralized learning bounded","feed_subtitle":"Bounds show consensus error shrinks every τ steps; steady-state loss grows smoothly with approximation error.","key_machinery":"The argument is carried by the block-triangular product matrix $\\mathcal{G}_{i:m\\tau+1}$ that propagates the joint consensus error over a full cycle of the FTC sequence. Because the combination matrices are cycled modulo $\\tau$, the product over $\\tau$ steps is expected to contract by the FTC property; the paper measures the quality of an approximation by $\\epsilon_\\tau = \\| A_\\tau\\cdots A_1 - (1/K)\\mathbf{1}\\mathbf{1}^T\\|$. Lemma 1 asserts that the spectral norm of this block-triangular product is bounded by the norm of its diagonal block product, turning approximate consensus into the contraction rate $\\epsilon_\\tau$. Lemmas 2 and 3 bound the gradient-heterogeneity and noise contributions to the error recursion, and Theorem 1 assembles these into the $\\tau$-block contraction bound that Theorem 2 uses for the centroid error.","core_discovery":"The central claim is that approximate finite-time consensus sequences, not just exact ones, are compatible with Aug-DGM gradient tracking and yield explicit mean-square convergence bounds. For $0<\\epsilon_\\tau<2/3$, the mean-square consensus error is bounded by an exponentially decaying term $O(\\epsilon_\\tau)^{\\lfloor i/\\tau\\rfloor}\\|\\widehat{\\mathbf{x}}_0\\|^2$ plus steady-state terms proportional to $\\mu^2 K \\tau^2 B^2/(1-\\epsilon_\\tau)^2$ and $\\mu^2 \\tau^2 \\sigma^2/(1-\\epsilon_\\tau)^2$; the exact case $\\epsilon_\\tau=0$ recovers the earlier exact-FTC bound. The centroid error obeys a similar bound with $\\tau^2/(1-\\epsilon_\\tau)^2$ factors plus the usual $\\mu \\sigma^2/K$ stochastic term. The paper states that the proof of Theorem 1 is omitted due to space limitations, so the quantitative bound rests on Lemmas 1 through 3. The message is that approximation error degrades performance continuously and can be quantified, making numerically inferred or learned FTC sequences usable for general graphs.","pith_inferences":["If Lemma 1's norm bound fails, the contraction rate should be replaced by the actual spectral norm of the $\\tau$-step product; the structure of Theorems 1 and 2 suggests the bounds would survive with $\\epsilon_\\tau$ redefined as that true norm.","The bounds imply a practical design rule: when choosing candidate approximate FTC sequences, minimize $\\tau^2\\epsilon_\\tau/(1-\\epsilon_\\tau)^2$ rather than $\\epsilon_\\tau$ alone, since the steady-state error weights approximation error quadratically in $\\tau$.","The analysis could plausibly extend to time-varying or directed graphs by tracking whether the $\\tau$-step product still contracts on the disagreement subspace, and to non-convex objectives by combining the consensus bound with standard descent lemmas."],"forward_implications":["General graphs can use numerically inferred or learned approximate FTC sequences; the only certification needed is the scalar $\\epsilon_\\tau$ defined in (5).","The closer the matrix product is to the scaled all-ones matrix, the faster the consensus error decays each $\\tau$ cycle and the smaller the steady-state error.","If $\\epsilon_\\tau$ approaches the stated thresholds, the admissible step size shrinks and the steady-state terms grow like $1/(1-\\epsilon_\\tau)^2$, so poor approximations force slower optimization.","Larger $\\tau$ worsens performance: both bounds contain $\\tau^2$ factors, so for some graphs it may be better to deliberately underestimate $\\tau$ and accept a nonzero $\\epsilon_\\tau$.","In the limit $\\epsilon_\\tau=0$, the bounds reduce to the exact finite-time consensus analysis, showing the new result is a strict generalization of the earlier one."],"supporting_citations":[{"why":"Provides the exact-FTC gradient-tracking analysis that this paper generalizes to approximate sequences.","marker":"[12]"},{"why":"Defines the Aug-DGM algorithm whose coupled recursion is analyzed here.","marker":"[21]"},{"why":"Reports empirical evidence that learned approximate FTC sequences benefit gradient tracking, motivating the theory.","marker":"[13]"},{"why":"Supplies the spectral-norm property invoked in Lemma 1 for block triangular matrices.","marker":"[22]"},{"why":"Gives the consensus-number bounds used to discuss the range of $\\tau$ for general graphs.","marker":"[10]"}],"fun_headline_variants":["Approximate FTC keeps decentralized learning bounded","Approximate consensus sequences still bound decentralized learning","Explicit bounds for approximate FTC in decentralized learning","Approximate FTC yields quantifiable consensus error bounds","Decentralized learning tolerates approximate finite-time consensus"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the norm of the whole $\\tau$-step update matrix is no larger than the norm of its diagonal blocks; if the off-diagonal couplings across agents make the true product norm larger, the advertised contraction rate at rate $\\epsilon_\\tau$ does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Approximate FTC keeps decentralized learning bounded","Approximate consensus sequences still bound decentralized learning","Explicit bounds for approximate FTC in decentralized learning","Approximate FTC yields quantifiable consensus error bounds","Decentralized learning tolerates approximate finite-time consensus"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001026,"raw_usage":{"total_tokens":4316,"prompt_tokens":930,"completion_tokens":3386,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":3317}},"tokens_in":546,"tokens_out":3386,"duration_ms":25367,"temperature":1.0,"reasoning_tokens":3317,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:29:12.007552+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $\\|\\mathcal{G}_{i:m\\tau+1}\\|$ for a small graph with a known approximate FTC product whose diagonal block product has norm $\\epsilon_\\tau$ but whose off-diagonal blocks are nonzero; if the full norm exceeds $\\epsilon_\\tau$, Lemma 1 fails. A numerical check of Theorem 1 would run Aug-DGM on a graph with $\\tau=4$, measure the consensus error every $\\tau$ iterations, and see whether the decay factor obeys $\\frac{3}{8}\\epsilon_\\tau(2+3\\epsilon_\\tau)$ or is controlled by the true product norm instead.","supporting_citations":[{"cited_title":"On graphs with finite-time consensus and their use in gradient tracking","cited_arxiv_id":"2311.01317","evidence_quote":"Provides the exact-FTC gradient-tracking analysis that this paper generalizes to approximate sequences."},{"cited_title":"Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes,","cited_arxiv_id":null,"evidence_quote":"Defines the Aug-DGM algorithm whose coupled recursion is analyzed here."},{"cited_title":"Learned finite-time consensus for distributed optimization,","cited_arxiv_id":null,"evidence_quote":"Reports empirical evidence that learned approximate FTC sequences benefit gradient tracking, motivating the theory."},{"cited_title":"Spectral properties of matrices,","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral-norm property invoked in Lemma 1 for block triangular matrices."},{"cited_title":"Graph diameter, eigenvalues, and minimum-time consensus,","cited_arxiv_id":null,"evidence_quote":"Gives the consensus-number bounds used to discuss the range of $\\tau$ for general graphs."}],"review_version":1}