{"id":"b47ca595-d2eb-44e7-9651-07b7479c9add","arxiv_id":"2506.18075","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Stochastic Push-Pull achieves linear speedup, O(1/(nε^2)) iteration complexity, over arbitrary strongly connected digraphs in the nonconvex setting.","lead":"A new proof framework shows that the stochastic Push-Pull method for decentralized optimization over directed networks converges at the same rate as one large pooled machine, with iteration count decreasing as nodes are added. The result closes a long-standing gap between the method's strong empirical performance and its incomplete theory.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Linear speedup is not established: the m and alpha constraints force T to grow polynomially in n before the sigma/sqrt(nT) term can dominate, so the advertised O(1/(n epsilon^2)) complexity does not follow as an n-scaling statement.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing issue: Theorem 1's final rate treats c, s_A, s_B, s_{Bm}, C_m, and C_{Delta,1} as constants independent of n, but the proof's own m lower bound (42) contains c^{-2} n^2 s_B^2, and C_{Delta,1} in (53) grows polynomially in n and inversely in c^2. The multi-step descent identity (20) is a real and interesting technical contribution, and the derivation of Lemma 3 and Lemma 4 appears internally structured, so the concern is not about algebraic soundness. The problem is the interpretation of the final complexity: linear speedup is an n-scaling claim, and the theorem only proves the sigma/sqrt(nT) term dominates in a regime T >= poly(n) that is not stated and is incompatible with T = O(n/epsilon^2) for fixed epsilon and large n. The paper's own footnote 1 acknowledges that the simplified m condition is insufficient, but Section 5 does not quantify how the additional constraints affect the n-dependence of the final bound. Because the missing analysis concerns the central advertised claim, the conditional verdict is appropriate: the paper should either state the required threshold explicitly, restrict the speedup claim to a regime where it holds, or prove that C_m and C_{Delta,1} are uniformly bounded for the digraph families of interest.","tokens_in":27270,"tokens_out":11319,"duration_ms":110860,"concrete_test":"Instantiate Theorem 1 on the uniform directed cycle with lazy weights, e.g. A = B = 0.5 I + 0.5 times the cyclic shift, for n = 4, 8, 16, 32. Numerically compute c, s_A, s_B, s_{Bm}, and C_m from equation (42) for each n. For a fixed epsilon (say 0.1), set T_bal = n/epsilon^2 and check whether the two conditions hold: (i) m_expr = 4 c^{-1} s_B^{1.5} s_{Bm} (n T_bal sigma^2/(L Delta))^{1/4} >= C_m, and (ii) the balancing step size sqrt(n Delta sigma)/(10 c sqrt(L T_bal)) is no larger than the step-size bound 1/(10 c m sqrt(s_B s_{Bm}^2 L)). If either fails, evaluate (55) with the actual m = max{m_expr, C_m} and alpha = min{...}; if the resulting term Delta/(c alpha T_bal) or the m^{-1} C_{Delta,1} term exceeds 44 sigma sqrt(L Delta)/sqrt(n T_bal), then the claimed O(1/(n epsilon^2)) rate is not attained in the tested regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 chooses m = ceil(max{4 c^{-1} s_B^{1.5} s_{Bm} (nT sigma^2/(L Delta))^{1/4}, C_m}) and alpha <= 1/(10 c m sqrt(s_B s_{Bm}^2 L)), with C_m defined in (42). The constant C_m contains the term c^{-2} n^2 s_B^2 from the noise-dominance requirement in Appendix B.2. For the chosen m to be the (nT)^{1/4} expression rather than the floor C_m, one needs (nT)^{1/4} >= c^{-2} n^2 s_B^2, i.e. T >= c^{-8} n^7 s_B^8; for a directed cycle with s_B = Theta(n^2) this becomes T >= n^23. In the intended regime T = O(n/epsilon^2), this condition fails for any fixed epsilon once n is large. Then m is effectively the constant C_m, the step-size restriction alpha <= 1/(10 c m sqrt(...)) binds, and the bound (55) is dominated by Delta/(c alpha T) = O(C_m Delta / T) and c alpha L sigma^2 / n = O(sigma^2/(n C_m)), neither of which produces the advertised 44 sigma sqrt(L Delta)/sqrt(nT). Moreover C_{Delta,1} in (53) grows as (10 s_A s_{Am} n^2 + 312 s_B^2 s_{Bm} n)/c^2, so the m^{-1} C_{Delta,1}/T term also carries hidden n-dependence. Thus the claimed O(1/(n epsilon^2)) iteration complexity is not supported as a statement about scaling in n; at best the theorem gives a fixed-digraph asymptotic T^{-1/2} rate with network-dependent constants, which is weaker than the claimed linear speedup for arbitrary strongly connected digraphs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the stochastic Push-Pull method for decentralized optimization over strongly connected digraphs in the stochastic nonconvex setting. It introduces a multi-step descent analysis that aggregates gradient-tracking errors over blocks of m iterations, exploiting a telescoping identity (Eq. (20)) that cancels interior gradient noise and leaves only exponentially attenuated boundary terms. The main result, Theorem 1, bounds the minimum expected squared gradient norm by 44σ√(LΔ)/√(nT) plus lower-order terms of order LΔ/T^{3/4} and LΔ/T, with m chosen as Θ((nT)^{1/4}), and the authors conclude an O(1/(nε²)) iteration complexity and hence linear speedup on arbitrary strongly connected digraphs. The paper also reports experiments on synthetic nonconvex logistic regression, MNIST, and CIFAR-10 across several topologies.","tokens_in":27713,"tokens_out":7700,"duration_ms":76118,"significance":"If the claimed n-scaling were fully established, this would be a notable contribution: it would supply the first general proof of linear speedup for the Push-Pull family over arbitrary strongly connected digraphs in a stochastic nonconvex setting, and the multi-step block-cancellation technique in Eq. (20) is a genuinely novel and potentially transferable analysis tool. The manuscript is also commendable for giving a detailed, structured proof (Appendices B.1–B.3), for explicitly defining the graph-dependent metrics s_A, s_B, c, and s_{Bm}, and for releasing code. However, the advertised O(1/(nε²)) complexity and the 'arbitrary strongly connected digraphs' claim rest on treating C_m and C_{Δ,1} as n-independent constants, and the text does not justify that treatment. The core derivation may be sound as a fixed-network asymptotic statement, but the paper's central claim as written is not supported.","major_comments":[{"comment":"The claimed rate 44σ√(LΔ)/√(nT) is not established as an n-scaling statement. The proof requires m ≥ C_m, and C_m in Eq. (42) contains the term c^{-2}n^2s_B^2 from the noise-dominance requirement in Appendix B.2. With the choice m = ⌈max{4c^{-1}s_B^{1.5}s_{Bm}(nTσ²/(LΔ))^{0.25}, C_m}⌉, the Θ((nT)^{1/4}) expression is active only when (nT)^{1/4} ≳ c^{-2}n^2s_B^2, i.e. T ≳ c^{-8}n^7s_B^8 up to constants. For a directed cycle, where s_B = Θ(n²), this threshold is T ≳ n^{23}. In the advertised regime T = O(1/(nε²)), the floor C_m dominates for large n; then m is effectively constant in T, the step-size constraint α ≤ 1/(10cm√(s_Bs_{Bm}²L)) binds, and the bound (55)/(26) is governed by terms of order C_mΔ/T and σ²/(mn) rather than by the linear-speedup term. The O(1/(nε²)) iteration complexity therefore does not follow from the stated theorem.","section":"Theorem 1, Eq. (42)"},{"comment":"The constant C_{Δ,1} is bounded in Eq. (53) by (10s_As_{Am}n² + 312s_B²s_{Bm}n)/c². This carries explicit n²/c² dependence, and c = nπ_Aᵀπ_B is not uniformly bounded below under Assumptions 1–2. Consequently the m^{-1}C_{Δ,1}LΔ/T term in Eq. (26) need not decay as 1/T with n-independent constants, and the lower-order error can dominate whenever T is chosen according to the advertised O(1/(nε²)) complexity. The manuscript needs either a uniform bound on these graph-dependent quantities or an explicit statement of the thresholds in n beyond which the leading σ/√(nT) term dominates.","section":"Lemma 4 and Eq. (53)"},{"comment":"The classification of Push-Pull as having iteration complexity O(σ²/(nε²)) on arbitrary strongly connected digraphs overstates what Theorem 1 proves. As written, the theorem gives a convergence bound whose lower-order terms depend on C_m and C_{Δ,1} through powers of c^{-1}, s_A, s_B and n; without controlling those dependences, the result is a fixed-network asymptotic rate, not a linear-speedup theorem in n. The authors should either state the theorem with the explicit T ≥ T₀(n) condition under which the σ/√(nT) term is dominant, or include the n-dependence of C_m and C_{Δ,1} in the iteration complexity. The current presentation does not justify the Table 1 entry or the 'first general proof' claim.","section":"Table 1, Section 1.2"}],"minor_comments":[{"comment":"There is a typographical error: min_{t∈{0,1,...,T-1}} E[||∇f(hat{x}(t)||²] is missing a closing parenthesis in the displayed formula.","section":"Eq. (26)"},{"comment":"The subscript 'consent' appears to be a typo for 'consensus'; the same term is used in Eqs. (12), (14), and (18).","section":"Section 4.1, Eq. (12)"},{"comment":"The implementation details are internally inconsistent: the text states L_total = 204800 and then states L_total = 1,440,000 = 3,600·200·2; also the claimed least common multiple 3,600 for n∈{4,6,8,9,12,16,18,24,25} is not the least common multiple of that set. Please correct these numbers.","section":"Appendix C.2"},{"comment":"The caption refers to the 'Extra Error Norm' but does not define the plotted quantity; please define it precisely in the caption or text.","section":"Figure 1"},{"comment":"The informal statement 'm ≥ Const·n²' in the derivation of Eq. (21) is followed by a footnote saying the rigorous condition is more involved. Since the rigorous condition in Eq. (42) is substantially stronger and includes s_B and c, the informal discussion should explicitly defer to Eq. (42) to avoid misleading the reader about the necessary block length.","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The central issue is the n-scaling of the m-floor and of C_{Δ,1}; it is not an algebraic contradiction in the proof itself. The theorem could be repaired by stating an explicit threshold T₀(n) for the leading term to dominate, or by proving uniform bounds on c^{-1}, s_B and the other graph metrics under additional assumptions. Without such a repair, the paper's main advertised contribution would be a fixed-network asymptotic rate rather than the claimed O(1/(nε²)) linear-speedup result, which is a substantial reduction in significance. I recommend that the revision address this head-on before the paper is considered further."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper proposes a multi-step descent analysis for stochastic Push-Pull and claims the first proof of linear speedup on arbitrary strongly connected digraphs. The core idea is worth attention: by grouping iterations into blocks of size m, the gradient-tracking recursion telescopes, interior noise cancels, and only boundary terms remain, each attenuated by mixing powers. That is a plausible and non-routine technique, and Section 3's explanation of why Push-Pull cannot be aligned with centralized SGD is clear and correct.\n\nThe appendix is dense but structured; the constants are explicit, and the proof has honest bookkeeping. The experiments on six topologies support the qualitative claim that gradient noise decreases with n, though they aren't rigorous speedup measurements.\n\nHowever, the main theorem overreaches. In (42) the required block size includes C_m ≥ c^{-2} n^2 s_B^2. Theorem 1 chooses m = max{4c^{-1}s_B^{1.5}s_{Bm}(nTσ^2/LΔ)^{1/4}, C_m}. For the first term to dominate, you need (nT)^{1/4} ≥ c^{-2} n^2 s_B^2, i.e., T ≥ c^{-8} n^7 s_B^8. On a directed cycle, s_B = Θ(n^2), so T ≥ n^{23}. In the intended regime T = O(n/ε^2), this fails for large n. Then m is effectively C_m, the step size α is forced down to O(c^{-1} m^{-1}) ~ O(c/n^2 s_B^2), and the bound (55) is dominated by Δ/(cαT), which is O(n^2 s_B^2 Δ / (c^2 T)), not O(1/(nT)). The term m^{-1} C_{Δ,1}/T also carries explicit n^2 and s_B^2 factors through (53). So the clean 44σ√(LΔ)/√(nT) rate is confined to T growing polynomially (in n) before it applies; as an n-scaling statement, linear speedup is not established.\n\nI also note minor presentational issues: Lemma 3's stated condition \"m ≥ 6c^{-2}s_B^2\" doesn't match the proof's \"m ≥ 6c^{-2}s_B\"; the paper says m ≥ c^{-2} n^2 s_B^2 in one place and m ≥ C_m in the theorem. These are fixable but indicate the proof needs a careful pass. The experiments show accuracy curves without error bars or iteration-to-target plots, so the empirical claim of linear speedup rests on visual inspection.\n\nWho is this for? Researchers working on decentralized optimization over digraphs. The block-analysis framework is a real contribution that may generalize, and the paper correctly identifies a gap in the literature. But the advertised O(1/(nε^2)) complexity is not supported. I'd recommend sending to a serious referee with expertise in stochastic decentralized methods; the referee should focus on the m-dependence of C_m and C_{Δ,1}. The paper deserves major revision, not desk rejection.","headline":"The block-analysis idea is genuinely new, but the m condition forces T to grow like n^7 (or far worse) before the claimed σ/√(nT) term dominates, so the advertised O(1/(nε^2)) linear speedup is not proven.","tokens_in":28239,"tokens_out":3504,"would_cite":false,"duration_ms":33199,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","90C26","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stochastic Push-Pull converges at centralized SGD speed on any strongly connected directed graph.","keywords":["decentralized optimization","Push-Pull method","AB method","directed graphs","linear speedup","stochastic nonconvex optimization","gradient tracking","multi-step descent analysis"],"falsifier":"Take an $n$-node directed cycle with row-stochastic $A$ and column-stochastic $B$ built by the paper's weighting rule, and compute $c=n\\pi_A^\\top\\pi_B$, $s_B$, $s_{Bm}$, $C_m$, and $C_{\\Delta,1}$ for $n=10,20,40$; if $c^{-1}$ or $C_{\\Delta,1}$ grows with $n$, then under the paper's own choice $m=\\Theta((nT)^{1/4})$ the leading $\\sigma/\\sqrt{nT}$ term is dominated by the $L\\Delta C_{\\Delta,1}/(mT)$ term unless $T\\gtrsim n^7$, meaning $O(1/(n\\epsilon^2))$ is not a uniform complexity bound over digraphs.","tokens_in":27050,"feed_emoji":"📉","tokens_out":8781,"duration_ms":82943,"temperature":0.7,"pith_summary":"This paper proves that the stochastic Push-Pull method—a decentralized algorithm in which each node mixes its own model with a row-stochastic matrix $A$ and its gradient tracker with a column-stochastic matrix $B$—achieves linear speedup on any strongly connected directed graph. Linear speedup means the number of iterations needed to reach an $\\epsilon$-accurate solution scales as $O(1/(n\\epsilon^2))$, exactly like centralized SGD, so adding nodes cuts the per-node iteration count proportionally. Earlier work had proved this for push-only and pull-only digraph methods and for Push-Pull on B-ary trees, but the general digraph case in the stochastic nonconvex setting was open. The paper closes that gap with a multi-step descent analysis, and the main theorem gives a concrete bound on the squared gradient norm whose leading term is $44\\sigma\\sqrt{L\\Delta}/\\sqrt{nT}$. If the proof is correct, it restores theoretical support for the empirically favored Push-Pull protocol in directed, heterogeneous networks.","feed_headline":"Push-Pull matches SGD speed on any directed network","feed_subtitle":"A blockwise descent argument cancels gradient-tracking noise, giving O(1/(nε²)) iterations across digraphs.","key_machinery":"The load-bearing object is the $m$-step descent lemma, which replaces the usual one-iteration descent inequality by a blockwise inequality over $m$ consecutive iterations. The key identity is the telescoping sum $$\\sum_{i=0}^{m-1}\\$Delta_y^{{(k+i)}}$ = \\Big(\\sum_{j=0}^{m-1}(B^j-B_\\infty)\\Big)\\$Delta_y^{{(k)}}$ + \\sum_{j=1}^{m-1}($B^{{m-j-1}}$-B_\\infty)($g^{{(k+j)}}$-$g^{{(k)}}$),$$ where $\\Delta_y^{(t)}=(I-B_\\infty)y^{(t)}$ is the part of the gradient tracker orthogonal to the column-stochastic consensus $B_\\infty$. This identity cancels all intermediate stochastic gradients, leaving only boundary differences weighted by exponentially decaying matrices $B^{m-j-1}-B_\\infty$, so the noise contribution stays $O(n\\sigma^2/m)$ rather than $\\Theta(n\\sigma^2)$. The graph enters only through the mixing sums $s_A,s_B$, the same quantity $s_{Bm}$ for $B^m$, and the Perron-overlap constant $c=n\\pi_A^\\top\\pi_B$; the proofs show these constants control both the consensus error and the admissible stepsize.","core_discovery":"The central claim is Theorem 1: under smoothness ($L$), bounded suboptimality ($\\Delta$), and bounded gradient noise ($\\sigma$), for any strongly connected digraph the average squared gradient norm satisfies $$\\min_{0\\le t