{"id":"b16f8e33-445a-4193-ba45-d524079b8bdf","arxiv_id":"2506.07021","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Stochastic Push-Pull attains O(1/sqrt(T)) convergence and, under a new sufficient condition, linear speedup on smooth nonconvex objectives over directed graphs.","lead":"This paper proves convergence rates for the Stochastic Push-Pull algorithm, which lets agents solve a shared optimization problem by talking only to their neighbors over a directed network. The authors give a condition under which this distributed method matches the speed of centralized stochastic gradient descent, and they test it on nonconvex learning tasks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the common-root condition is load-bearing but explicitly guaranteed; the cited defects are non-central and fixable.","rationale":"The central theorem's proof path is: Lemmas 3.10 and 3.11 bound consensus and tracking error in terms of the finite sums; Lemma 3.12 combines them via the descent inequality; Theorem 4.1 optimizes the step size. The only point where the proof can silently fail is the negative descent term derived in Appendix A.8 Step 2, exactly the pi_R^T pi_C > 0 condition highlighted by the reader. However, this positivity is not an extra hidden assumption: it is part of Assumption 2.1 and proved in Lemma 2.5 as a consequence, so the descent term is valid for every instance covered by the theorem. I audited the displayed inequalities for sign and dimension errors, especially the uses of Lemma 3.3; the weighting choices are consistent. The two real defects are in secondary results: Corollary 4.3's proof relies on an undefined M9, and Lemma 3.1's proof of finiteness stops after M1, saying the rest follows by similar arguments. Since M2 is finite as a weighted geometric series under Assumption 2.4, replacing M9 by M2 makes the Corollary 4.3 argument go through; and N5 through N8 are finite by the product bound norm(tilde R^k tilde C^(t-k)) <= N^2 (1-p)^t. Consequently these are presentation and completeness issues, not threats to Theorem 4.1 or the linear-speedup condition. I therefore leave the reader's CONDITIONAL verdict unchanged.","tokens_in":1005,"tokens_out":1080,"duration_ms":199442,"concrete_test":"Re-derive the omitted N5 through N8 finiteness proof by bounding each term as norm(tilde R^k tilde C^(t-k)) <= norm(tilde R^k) * norm(tilde C^(t-k)) <= N^2 (1-p)^t, and re-run Corollary 4.3 with M9 set to M2. If any N-sum diverges under the stated assumptions, or if the Corollary 4.3 chain fails with that substitution, the constant framework needs revision; otherwise the present verdict stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing flaw found in the central claim. The descent argument in Appendix A.8 Step 2 does hinge on the negative term -gamma n pi / 4, which requires pi_R^T pi_C > 0; this is exactly what Assumption 2.1 plus Lemma 2.5 supplies, and the theorem explicitly assumes that condition. I checked the main derivation chain (Lemma 3.10, Lemma 3.11, Lemma 3.12, Theorem 4.1) for hidden circularity or sign errors and found none. The genuine defects are peripheral: Corollary 4.3 uses an undefined constant M9, and Lemma 3.1 sketches rather than proves finiteness of N5 through N8. The natural reading is M9 = M2, which is finite by Lemma 3.1; the omitted N-sum bounds follow from the same exponential-decay argument because the product norm of tilde R^k tilde C^(t-k) is bounded by N^2 (1-p)^t, giving a convergent weighted geometric series. Fixing these issues would not change Theorem 4.1 or Corollary 4.2.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the Stochastic Push-Pull (S-PP) algorithm for decentralized nonconvex optimization over directed graphs. It relaxes earlier assumptions on the weight matrices to an exponential-decay condition, introduces an analytical framework based on the infinite sums M1, M2, N1, ..., N8, and proves an O(1/sqrt(T)) convergence rate with explicit constants (Theorem 4.1). It then gives a sufficient condition for linear speedup matching centralized SGD (Corollary 4.2), a lower bound stating that no higher-order speedup is possible (Corollary 4.3), and comparisons with existing DSGT analyses for doubly stochastic and symmetric mixing matrices (Corollary 4.1, Remarks 4.1-4.2). Numerical experiments on logistic regression with nonconvex regularization and CNN training on MNIST compare S-PP with SGP and Push-DIGing.","tokens_in":30375,"tokens_out":21619,"duration_ms":213353,"significance":"If the main result is correct, the paper makes a useful contribution: it provides the first explicit linear-speedup condition for Stochastic Push-Pull over general directed graphs, and its infinite-sum framework gives a new way to express network-dependence without relying solely on a spectral gap. The main theorem is supported by a detailed appendix, and the claimed linear-speedup condition is a legitimate sufficient-condition result rather than a fitted relation. However, several supporting proofs are incomplete or contain errors: the proof of Lemma 3.2 has a false inequality in the symmetric-case N7 bound, Corollary 4.3 uses an undefined constant, and Lemma 3.1 leaves the finiteness of N5-N8 to a sketch. These issues do not appear to invalidate Theorem 4.1 itself, but they affect secondary claims in the paper and need to be fixed before the manuscript is publishable.","major_comments":[{"comment":"The proof of the claimed bound N7 <= 10/((1+min{lambda_n,0})(1-lambda)) contains a false inequality. For an eigenvalue x with |x| in (0,1), the derivation obtains (f_t(x))^2 <= 4/(1-sqrt(|x|))^2 |x|^t and then states this is <= 4/(1-|x|) |x|^t. Since 1-|x| = (1-sqrt(|x|))(1+sqrt(|x|)) > (1-sqrt(|x|))^2, the inequality is reversed. For lambda_n = -r with r near 1, the true summand behaves like t^2 r^{2t}, giving N7 = O((1-r)^{-3}) after summation, whereas the claimed bound is O((1-r)^{-2}). This directly affects the estimates used in Corollary 4.1 cases 2 and 3 and the transient-time comparison in Remark 4.2, so the derivation must be corrected or the affected claims withdrawn.","section":"Appendix A.3, Lemma 3.2 (symmetric case)"},{"comment":"The proof applies Lemma 3.3 with weights alpha_i = i ||pi_R^T(C^{i+1}-C^i)|| / M9, but the constant M9 is never defined. The argument can be repaired by taking M9 = M2 in the non-spanning-tree cases, but as written the proof is incomplete; a reader cannot verify that the required condition sum_i alpha_i <= 1 holds or that the final bound is expressed in terms of the quantities appearing in the corollary statement.","section":"Corollary 4.3 proof"},{"comment":"The proof explicitly establishes finiteness only for M1 and says the remaining sums follow by similar arguments. For N5-N8, the summands are convolutions of the form ||tilde R^k tilde C^{t-k}|| or variants, and their finiteness requires a separate argument splitting the summation range into k <= m and k > m (or equivalently using the product decay bound ||tilde R^k tilde C^{t-k}|| <= N^2(1-p)^{t/2}). Since the constants P1-P5 in Lemma 3.12 and Theorem 4.1 are defined using these sums, a complete proof of Lemma 3.1 is load-bearing for the main theorem and should be supplied.","section":"Lemma 3.1"}],"minor_comments":[{"comment":"The transient-time claims O(n^3/(1-lambda)^6), O(max{n^3/(c^2(1-lambda)^2), n/(1-lambda)^{8/3}}), and the comparison with [8] are asserted without derivation; they should be derived from the displayed bounds in Corollary 4.1 or stated as conjectures.","section":"Remarks 4.1 and 4.2"},{"comment":"The graph G_C^T is used in Assumption 2.1 but is defined only in a footnote; please define it explicitly in the notation section.","section":"Section 1.3 and Assumption 2.1"},{"comment":"The sentence 'Corollary 4.3 indicates that Theorem 4.1 does not allow for higher-order speedup' would be clearer if it explicitly said 'the leading 1/sqrt(T) term cannot be improved to a higher power of T under the given assumptions'.","section":"Section 4.1, paragraph before Corollary 4.3"},{"comment":"The caption says divergent algorithms are plotted with 'their first non-NaN values in the records', but it is unclear whether this means only the first recorded value is shown or whether the curves are truncated; please clarify.","section":"Figure 3 caption"},{"comment":"The proof uses the notation C0 = 2*10^6 inside the 'less than or similar to' bound; please state explicitly that the hidden constant is C0 and that all 'less than or similar to' symbols in the theorem refer to this constant.","section":"Theorem 4.1 statement"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's central Theorem 4.1 appears internally consistent and the linear-speedup condition is a reasonable sufficient-condition result. However, the paper relies on two earlier arXiv preprints by the same authors for a key zero cross-term (Lemma 3.4 in [43]) and for the spanning-tree constants; if those preprints are not yet peer-reviewed, the authors should either include the needed arguments in the appendix or make the dependence explicit. The N7 error in Lemma 3.2 is a genuine mathematical mistake that affects the comparison with prior DSGT results, so the authors should be asked to correct it before acceptance. No code or data availability statement is provided, which limits reproducibility of the numerical experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper delivers a genuinely new sufficient condition for linear speedup of Stochastic Push-Pull on general directed graphs, without the spanning-tree construction their earlier work relied on. Second, the new infinite-sum framework (M1, M2, N1–N8) is real and reproduces or sharpens existing DSGT bounds, including the non-symmetric doubly stochastic case. I checked the main derivation chain (Lemma 3.10 through Theorem 4.1) and found no circularity or sign error. The common-root condition in Assumption 2.1 is load-bearing—it gives the negative gradient term in the descent lemma—but the paper explicitly assumes it and Lemma 2.5 guarantees it. That is not a hidden weakness.\n\nThe genuine soft spots are peripheral. Corollary 4.3 uses an undefined constant M9; the natural reading is M9 = M2, which is finite by Lemma 3.1. The proof of Lemma 3.1 sketches the finiteness of N5–N8 as “similar arguments”; the missing sums do converge by the same exponential-decay argument, but the reader shouldn't have to fill that in. The transient-time claims in Remarks 4.1–4.2 are asserted rather than derived. And the experiments are not reproducible from the manuscript alone: no code, no data, and the stepsize rescaling by nπ is explained only loosely.\n\nNone of this breaks the central claim. The paper is a serious contribution to decentralized nonconvex optimization and the analysis is long but coherent. The fixable issues should be cleaned up before publication, but they don't warrant rejection. I'd send it to a qualified referee, with the expectation of a minor revision.","headline":"Solid and genuinely new linear-speedup analysis for Stochastic Push-Pull, with a few peripheral but fixable gaps; worth a serious referee.","tokens_in":30901,"tokens_out":1901,"would_cite":true,"duration_ms":20390,"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":"Stochastic Push-Pull, a decentralized two-graph optimizer, converges for smooth nonconvex objectives and matches centralized speed whenever the two graphs share a common root.","keywords":["decentralized optimization","Stochastic Push-Pull","gradient tracking","nonconvex optimization","directed graphs","linear speedup","stochastic gradients"],"falsifier":"On a smooth nonconvex problem with fixed noise variance $\\sigma^2$, smoothness $L$, and gap $\\Delta_f$, run S-PP over a family of balanced directed graphs (doubly stochastic, non-symmetric $W$, e.g., directed rings with known $\\lambda = \\|W - \\mathbf{1}\\mathbf{1}^T/n\\|$) doubling $n$ each time; Corollary 4.1 predicts the gradient norm obeys $\\sqrt{\\Delta_f \\sigma^2 L/(nT)}$ once $T$ passes the transient $O(n^3/(1-\\lambda)^6)$, so if the measured $T$ needed to reach a target gradient norm fails to shrink like $1/n$, or the transient exponent departs from $6$, the claimed speedup regime is mischaracterized. A second check targets the root assumption directly: build $R$ and $C$ that are exponentially decaying but have disjoint root sets, so $\\pi_R^T \\pi_C = 0$ and the theorem's hypotheses fail, and test whether S-PP still converges at a comparable rate — if it does, the common-root condition is not necessary.","tokens_in":29966,"feed_emoji":"🌐","tokens_out":22181,"duration_ms":193603,"temperature":0.7,"pith_summary":"The paper studies Stochastic Push-Pull (S-PP), a decentralized algorithm for minimizing the average $f(x) = \\frac{1}{n}\\sum_{i=1}^n f_i(x)$ in which each agent alternates a pull step over one directed graph (updating its model with the row-stochastic matrix $R$) and a push step over another (updating a gradient-tracking variable with the column-stochastic matrix $C$). It proves that under smooth nonconvex objectives with bounded-variance stochastic gradients, S-PP converges at rate $O(1/\\sqrt{T})$ with explicit network-dependent coefficients, and it derives a sufficient condition for linear speedup: when $\\max\\{M_1, \\tilde{M}_2, M_1 \\tilde{M}_2\\} / (n(\\pi_R^T \\pi_C)^2)$ is bounded by a constant that does not grow with the number of agents $n$, the dominant error term shrinks like $\\sqrt{\\Delta_f \\sigma^2 L / (nT)}$, matching a single centralized SGD run. The significance is practical: linear speedup is what makes adding agents equivalent to adding iterations, and the paper's condition is a concrete, checkable criterion built from the two mixing matrices. The condition holds automatically for doubly stochastic mixing, which yields what the paper reports as the first linear-speedup guarantee for decentralized stochastic gradient tracking over balanced directed graphs with non-symmetric weight matrices.","feed_headline":"Match centralized speed with one shared root","feed_subtitle":"New proof shows the two-graph optimizer scales like a central server once the graphs share a root node.","key_machinery":"The machinery is a family of infinite sums over products of the two mixing matrices, which displace the spectral-gap constant used in most decentralized analyses. With the projections $\\Pi_R = I - \\mathbf{1}\\pi_R^T$ and $\\Pi_C = I - \\pi_C \\mathbf{1}^T$, the paper defines $\\tilde{R}^k = \\Pi_R R^k$, $\\tilde{C}^k = \\Pi_C C^k$, and then $M_1 := \\|\\pi_R^T C\\|^2 + \\sum_{t=1}^\\infty \\|\\pi_R^T (C^{t+1} - C^t)\\|^2$, $M_2 := \\sum_{t=1}^\\infty t \\|\\pi_R^T (C^{t+1} - C^t)\\|$, together with eight further sums $N_1, \\dots, N_8$ of norms of products like $\\sum_{k=1}^{t-1} \\tilde{R}^k \\tilde{C}^{t-k}$. Exponential decay of $R$ and $C$ (Definition 2.3) guarantees all these sums are finite (Lemma 3.1), so the sums, not a spectral gap, carry the network's influence on the rate and reduce to closed forms in $\\lambda = \\|W - \\mathbf{1}\\mathbf{1}^T/n\\|$ when $R = C = W$ is doubly stochastic (Lemma 3.2). The hinge of the whole proof is Lemma 2.5: under the common-root assumption, $\\pi_R^T \\pi_C > 0$, and this scalar enters the descent lemma as the coefficient of the negative gradient term that drives convergence.","core_discovery":"On the paper's own terms, the central claim is Theorem 4.1: for a suitably chosen constant step size, S-PP satisfies $\\frac{1}{T+1}\\sum_{t=0}^{T} \\mathbb{E}[\\|\\nabla f(\\hat{x}(t))\\|^2] \\leq O\\!\\left( \\left(\\frac{Q}{n\\pi^2}\\right)^{1/2} \\left(\\frac{\\Delta_f \\sigma^2 L}{n(T+1)}\\right)^{1/2} + \\frac{(\\Delta_f^2 \\sqrt{\\max\\{P_2,P_3\\}\\max\\{N_4,N_7\\}} L^2 \\sigma^2)^{1/3}}{n\\pi (T+1)^{2/3}} + \\cdots \\right)$, where $\\hat{x}(t) = \\pi_R^T X(t)$ is the root-weighted iterate and the constants $P_i$, $Q$, and $N_i$ are defined from the mixing matrices. Corollary 4.2 converts this into the headline speedup statement: if $\\max\\{M_1, \\tilde{M}_2, M_1\\tilde{M}_2\\}/(n(\\pi_R^T \\pi_C)^2) \\leq C$ for a constant $C$ independent of $n$, then the $1/\\sqrt{nT}$ term dominates and S-PP matches centralized SGD, a result the paper reports as previously unavailable for Stochastic Push-Pull. The same framework also yields linear speedup for DSGT with merely doubly stochastic, non-symmetric $W$ on balanced directed graphs (claimed as new), recovery of the bound of [1] and an improved transient time over [8] when $W$ is symmetric, and a relaxation of the standard positive-diagonal requirement on $R$ and $C$ to an exponential-decay property that admits zero-diagonal $(0,1)$-mixing matrices from spanning trees.","pith_inferences":["The constants $M_1, M_2, N_1, \\dots, N_8$ are computable from powers of $R$ and $C$, so the paper's condition doubles as a design criterion: a search over spanning trees and edge weights could keep $Q/(n\\pi^2)$ bounded, offering a practical alternative to spectral-gap-based topology design for directed graphs.","The common-root condition is weaker than strong connectivity, so the proof should carry over to hierarchies or broadcast-style networks where some agents only send or only receive, and whether time-varying graphs whose unions share a root inherit the same rates is a natural extension the paper does not address.","The special case $\\tilde{M}_2 = 0$ for tree-structured graphs shows the delay-induced noise terms vanish when information flows without cycles, which suggests cycle-heavy topologies such as rings might be reweighted to mimic the tree cancellation, a modification that could shorten their transient phase and is directly testable.","Because $\\pi_R^T \\pi_C$ appears squared in the denominator, the ratio $Q/(n\\pi^2)$ reads as an effective network-inefficiency factor for directed topologies, and comparing this factor across graphs such as rings, Erdős–Rényi, and multi-sub-ring topologies could serve as a practical ranking tool for choosing communication structures."],"forward_implications":["When $\\max\\{M_1, \\tilde{M}_2, M_1 \\tilde{M}_2\\}/(n(\\pi_R^T \\pi_C)^2) \\le C$ holds, doubling the number of agents halves the attainable gradient norm at a fixed iteration count, so training over directed networks carries no asymptotic penalty relative to a central server.","For doubly stochastic mixing $W$, the analysis yields linear speedup for DSGT, and the paper claims the non-symmetric, balanced-directed-graph case as new, with an explicit transient phase of $O(n^3/(1-\\lambda)^6)$.","For symmetric $W$ on undirected graphs, the constants collapse to closed spectral forms, reproducing the DSGT bound of [1] and improving the transient time stated in [8].","Because only exponential decay is required of $R$ and $C$, zero-diagonal $(0,1)$-matrices built from spanning trees become admissible, and Lemma 2.6 shows the earlier strictly-positive-diagonal assumption was strictly stronger.","Corollary 4.3 shows the ratio $\\max\\{M_1, \\tilde{M}_2, M_1 \\tilde{M}_2\\}/(n(\\pi_R^T \\pi_C)^2)$ is always at least $1/10$, so the sufficient condition is tight up to a constant and the theorem cannot be sharpened to a higher-order speedup."],"supporting_citations":[{"why":"introduces the Push-Pull/AB method and its two-graph setup in which the pull graph and the reversed push graph each contain a spanning tree sharing a common root; this becomes Assumption 2.1 and the algorithm skeleton of S-PP","marker":"[27]"},{"why":"the state-of-the-art DSGT convergence analysis for symmetric doubly stochastic matrices that Corollary 4.1 claims to improve on, and the source of the step-size tuning lemma used in Theorem 4.1","marker":"[8]"},{"why":"the unified DSGT bound that the symmetric and positive-semidefinite mixing cases of Corollary 4.1 recover, serving as the comparison target in Remark 4.2","marker":"[1]"},{"why":"the earlier B-ary tree Push-Pull analysis achieving linear speedup with explicit transient times that depend on global knowledge of the spanning tree, a case the new sufficient condition subsumes and where one of the paper's constants is set to zero","marker":"[42]"},{"why":"the arbitrary-topology construction with zero-one mixing matrices on spanning trees, giving the case where the speedup ratio equals one, supplying the norm lemma used in the bounds, and the setting where a delay constant vanishes for tree graphs","marker":"[43]"},{"why":"the prior stochastic-gradient analysis of the S-AB variant under strong convexity that this paper extends to the smooth nonconvex regime while relaxing the weight-matrix assumptions","marker":"[45]"},{"why":"defines distributed stochastic gradient tracking, the algorithm S-PP reduces to when the two mixing matrices coincide, so its rate is the benchmark Corollary 4.1 compares against","marker":"[24]"}],"fun_headline_variants":["Stochastic push-pull hits centralized speed with shared root","Shared root unlocks centralized speed for push-pull","Linear speedup for decentralized push-pull under shared root","Push-pull matches central SGD scaling with shared root","Decentralized optimizer linear speedup: shared root suffices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the pull graph $G_R$ and the reversed push graph $G_C^T$ each contain a spanning tree and that two such trees share a common root node, so that the stationary left-eigenvectors $\\pi_R$ and $\\pi_C$ of the mixing matrices overlap with $\\pi_R^T \\pi_C > 0$ — if the graphs have no common root this overlap is zero, the descent lemma loses its negative downhill term, and the proof's contraction argument collapses.","fun_headline_variants_meta":{"raw":{"variants":["Stochastic push-pull hits centralized speed with shared root","Shared root unlocks centralized speed for push-pull","Linear speedup for decentralized push-pull under shared root","Push-pull matches central SGD scaling with shared root","Decentralized optimizer linear speedup: shared root suffices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000826,"raw_usage":{"total_tokens":3677,"prompt_tokens":1077,"completion_tokens":2600,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":693,"completion_tokens_details":{"reasoning_tokens":2521}},"tokens_in":693,"tokens_out":2600,"duration_ms":20097,"temperature":1.0,"reasoning_tokens":2521,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:44:25.816025+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a smooth nonconvex problem with fixed noise variance $\\sigma^2$, smoothness $L$, and gap $\\Delta_f$, run S-PP over a family of balanced directed graphs (doubly stochastic, non-symmetric $W$, e.g., directed rings with known $\\lambda = \\|W - \\mathbf{1}\\mathbf{1}^T/n\\|$) doubling $n$ each time; Corollary 4.1 predicts the gradient norm obeys $\\sqrt{\\Delta_f \\sigma^2 L/(nT)}$ once $T$ passes the transient $O(n^3/(1-\\lambda)^6)$, so if the measured $T$ needed to reach a target gradient norm fails to shrink like $1/n$, or the transient exponent departs from $6$, the claimed speedup regime is mischaracterized. A second check targets the root assumption directly: build $R$ and $C$ that are exponentially decaying but have disjoint root sets, so $\\pi_R^T \\pi_C = 0$ and the theorem's hypotheses fail, and test whether S-PP still converges at a comparable rate — if it does, the common-root condition is not necessary.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the Push-Pull/AB method and its two-graph setup in which the pull graph and the reversed push graph each contain a spanning tree sharing a common root; this becomes Assumption 2.1 and the algorithm skeleton of S-PP"},{"cited_title":"KOLOSKOVA, T","cited_arxiv_id":null,"evidence_quote":"the state-of-the-art DSGT convergence analysis for symmetric doubly stochastic matrices that Corollary 4.1 claims to improve on, and the source of the step-size tuning lemma used in Theorem 4.1"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"the unified DSGT bound that the symmetric and positive-semidefinite mixing cases of Corollary 4.1 recover, serving as the comparison target in Remark 4.2"},{"cited_title":"B-ary Tree Push-Pull Method is Provably Efficient for Distributed Learning on Heterogeneous Data","cited_arxiv_id":"2404.05454","evidence_quote":"the earlier B-ary tree Push-Pull analysis achieving linear speedup with explicit transient times that depend on global knowledge of the spanning tree, a case the new sufficient condition subsumes and where one of the paper's constants is set to zero"},{"cited_title":"ZHAO ANDY","cited_arxiv_id":null,"evidence_quote":"the prior stochastic-gradient analysis of the S-AB variant under strong convexity that this paper extends to the smooth nonconvex regime while relaxing the weight-matrix assumptions"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines distributed stochastic gradient tracking, the algorithm S-PP reduces to when the two mixing matrices coincide, so its rate is the benchmark Corollary 4.1 compares against"}],"review_version":1}