Pith. sign in

REVIEW 3 major objections 5 minor 46 references

Stochastic Push-Pull for Decentralized Nonconvex Optimization

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict Solid and genuinely new linear-speedup analysis for Stochastic Push-Pull, with a few peripheral but fixable gaps; worth a serious referee. read the letter →

arxiv 2506.07021 v1 pith:75PIDQD2 submitted 2025-06-08 math.OC

Runze You , Shi Pu This is my paper
classification math.OC MSC 90C2690C1568W15
keywords decentralizedoptimizationStochasticPush-Pullgradienttrackingnonconvexdirectedgraphslinearspeedupgradients
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Appendix A.3, Lemma 3.2 (symmetric case)] 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.
  2. [Corollary 4.3 proof] 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.
  3. [Lemma 3.1] 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.
minor comments (5)
  1. [Remarks 4.1 and 4.2] 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.
  2. [Section 1.3 and Assumption 2.1] 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.
  3. [Section 4.1, paragraph before Corollary 4.3] 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'.
  4. [Figure 3 caption] 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.
  5. [Theorem 4.1 statement] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence rate is derived from the stated assumptions, and the linear-speedup condition is an explicit sufficient condition obtained from the proved bound.

full rationale

Walking the claimed derivation chain: Lemma 2.5 derives pi_R^T pi_C > 0 from Assumptions 2.1 and 2.4; Lemmas 3.10-3.12 bound consensus error and the descent using the finite constants N_i and M_i; Theorem 4.1 then optimizes the step size; Corollary 4.2 states the condition under which the dominant term becomes O((Delta_f sigma^2 L / (n(T+1)))^{1/2}). None of these steps assumes the conclusion. The linear-speedup condition max{M1, tilde M2, M1 tilde M2}/(n(pi_R^T pi_C)^2) <= C is exactly the coefficient of the theorem's leading term, but that is a legitimate sufficient condition extracted from the proved bound, not an input assumed in the proof. There is no fitted parameter renamed as a prediction, and no quantity is fit to data. The citations to the authors' own prior work [42,43] are used for elementary norm inequalities (Lemmas 3.3 and 3.4) and a special-case cancellation for spanning trees defining tilde M2 = 0; these are not unverified uniqueness or existence theorems and are not load-bearing for the central convergence claim. Two textual defects exist but are not circularity: the proof of Corollary 4.3 invokes an undefined constant M9, and Lemma 3.1 only sketches the finiteness of N_2 through N_8 and M_2 ('Hence, we omit those details'). Both are peripheral to Theorem 4.1 and Corollary 4.2, which are otherwise self-contained given the exponential-decay assumption that makes the sums finite.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new entities; all assumptions are standard. The main theoretical contribution is conditional on these network and stochasticity assumptions.

assumptions (6)
  • domain assumption Assumption 2.1: The graphs G_R and G_C^T each contain a spanning tree and there exists a pair sharing a common root.
    Ensures unique root eigenvectors pi_R and pi_C with pi_R^T pi_C > 0 (Lemma 2.5), required by the descent analysis in Lemma 3.12.
  • domain assumption Assumption 2.4: The matrices R and C^T are row/column stochastic and exponentially decaying (Definition 2.3).
    Makes the infinite sums M1, M2, N1-N8 finite (Lemma 3.1), which is the basis for all subsequent bounds.
  • domain assumption Assumption 2.7: Unbiased stochastic gradients with uniformly bounded variance sigma^2.
    Used in Lemmas 3.8-3.11 to bound gradient estimation error.
  • domain assumption Assumption 2.8: Each local objective f_i is L-smooth and lower bounded.
    Standard for nonconvex smooth analysis; used in the descent lemma.
  • standard math Perron-Frobenius theorem and Gelfand's formula.
    Used in Appendix A.1-A.2 to establish existence/uniqueness of root eigenvectors and exponential decay of stochastic matrices.
  • standard math Lemma 3.4 (||AB||_F <= ||A||_2 ||B||_F) and Lemma 3.3 (convexity-style norm bound).
    Cited from [42,43] (same authors) and used throughout the appendix; elementary results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stochastic Push-Pull for Decentralized Nonconvex Optimization." pith.science (2026). https://pith.science/paper/75PIDQD2

@misc{pith2026250607021,
  author       = {Pith},
  title        = {Pith review of: Stochastic Push-Pull for Decentralized Nonconvex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/75PIDQD2}},
  note         = {Machine review of arXiv:2506.07021}
}
read the original abstract

To understand the convergence behavior of the Push-Pull method for decentralized optimization with stochastic gradients (Stochastic Push-Pull), this paper presents a comprehensive analysis. Specifically, we first clarify the algorithm's underlying assumptions, particularly those regarding the network structure and weight matrices. Then, to establish the convergence rate under smooth nonconvex objectives, we introduce a general analytical framework that not only encompasses a broad class of decentralized optimization algorithms, but also recovers or enhances several state-of-the-art results for distributed stochastic gradient tracking methods. A key highlight is the derivation of a sufficient condition under which the Stochastic Push-Pull algorithm achieves linear speedup, matching the scalability of centralized stochastic gradient methods -- a result not previously reported. Extensive numerical experiments validate our theoretical findings, demonstrating the algorithm's effectiveness and robustness across various decentralized optimization scenarios.

Figures

Figures reproduced from arXiv: 2506.07021 by the authors.

Figure 1
Figure 1. Illustration of two network topologies. The weight matrices R and C are constructed by averaging over the in-neighbors and out-neighbors of each node, respectively. Specifically, the entries are given by: [R] ij =    1 1 + d in i , if (j, i) ∈ ER or i = j, 0, otherwise, and [C] ij =    1 1 + d out j , if (j, i) ∈ EC or i = j, 0, otherwise, where d in i and d out j are the in-degree of node i and out-degree of … view at source ↗
Figure 2
Figure 2. Performance of different algorithms using various communication graphs for logistic regression with [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Training loss and test accuracy of different algorithms for training CNN on MNIST. For the training loss, we [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

46 extracted references · 44 canonical work pages

  1. [1]

    S. A. ALGHUNAIM ANDK. YUAN,A unified and refined convergence analysis for non-convex decentralized learning, IEEE Transactions on Signal Processing, 70 (2022), pp. 3264–3279

    work page 2022

  2. [2]

    ASSRAN, N

    M. ASSRAN, N. LOIZOU, N. BALLAS,ANDM. RABBAT,Stochastic gradient push for distributed deep learning, in International Conference on Machine Learning, PMLR, 2019, pp. 344–353

    work page 2019

  3. [3]

    CHEN ANDA

    J. CHEN ANDA. H. SAYED,Diffusion adaptation strategies for distributed optimization and learning over networks, IEEE Transactions on Signal Processing, 60 (2012), pp. 4289–4305

    work page 2012

  4. [4]

    GHARESIFARD ANDJ

    B. GHARESIFARD ANDJ. CORTÉS,When does a digraph admit a doubly stochastic adjacency matrix?, in Proceedings of the 2010 American Control Conference, IEEE, 2010, pp. 2440–2445

    work page 2010

  5. [5]

    R. A. HORN ANDC. R. JOHNSON,Matrix analysis, Cambridge university press, 2012

    work page 2012

  6. [6]

    HUANG, X

    K. HUANG, X. LI,ANDS. PU,Distributed stochastic optimization under a general variance condition, IEEE Transactions on Automatic Control, (2024)

    work page 2024

  7. [7]

    HUANG ANDS

    K. HUANG ANDS. PU,Improving the transient times for distributed stochastic gradient methods, IEEE Transac- tions on Automatic Control, 68 (2022), pp. 4127–4142

    work page 2022

  8. [8]

    KOLOSKOVA, T

    A. KOLOSKOVA, T. LIN,ANDS. U. STICH,An improved analysis of gradient tracking for decentralized machine learning, Advances in Neural Information Processing Systems, 34 (2021), pp. 11422–11435

    work page 2021

Show all 46 references
  1. [9]

    KOLOSKOVA, N

    A. KOLOSKOVA, N. LOIZOU, S. BOREIRI, M. JAGGI,ANDS. STICH,A unified theory of decentralized sgd with changing topology and local updates, in International Conference on Machine Learning, PMLR, 2020, pp. 5381–5393

    2020

  2. [10]

    KOLOSKOVA, S

    A. KOLOSKOVA, S. STICH,ANDM. JAGGI,Decentralized stochastic optimization and gossip algorithms with compressed communication, in International Conference on Machine Learning, PMLR, 2019, pp. 3478–3487

    2019

  3. [11]

    KUNGURTSEV, M

    V. KUNGURTSEV, M. MORAFAH, T. JAVIDI,ANDG. SCUTARI,Decentralized asynchronous nonconvex stochas- tic optimization on directed graphs, IEEE Transactions on Control of Network Systems, 10 (2023), pp. 1796–1804

    2023

  4. [12]

    LECUN, C

    Y. LECUN, C. CORTES, C. BURGES,ET AL.,Mnist handwritten digit database, 2010

    2010

  5. [13]

    Z. LI, W. SHI,ANDM. YAN,A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates, IEEE Transactions on Signal Processing, 67 (2019), pp. 4494–4506

    2019

  6. [14]

    X. LIAN, C. ZHANG, H. ZHANG, C.-J. HSIEH, W. ZHANG,ANDJ. LIU,Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent, Advances in neural information processing systems, 30 (2017)

    2017

  7. [15]

    LIANG, X

    L. LIANG, X. HUANG, R. XIN,ANDK. YUAN,Understanding the influence of digraphs on decentralized optimization: Effective metrics, lower bound, and optimal algorithm, arXiv preprint arXiv:2312.04928, (2023)

    2023 arXiv

  8. [16]

    Y. LIAO, Z. LI, S. PU,ANDT.-H. CHANG,A robust compressed push-pull method for decentralized nonconvex optimization, arXiv preprint arXiv:2408.01727, (2024)

    2024 arXiv

  9. [17]

    NADIRADZE, A

    G. NADIRADZE, A. SABOUR, P. DAVIES, S. LI,ANDD. ALISTARH,Asynchronous decentralized sgd with quantized and local updates, Advances in Neural Information Processing Systems, 34 (2021), pp. 6829–6842

    2021

  10. [18]

    NEDI ´C ANDA

    A. NEDI ´C ANDA. OLSHEVSKY,Distributed optimization over time-varying directed graphs, IEEE Transactions on Automatic Control, 60 (2014), pp. 601–615

    2014

  11. [19]

    NEDI ´C ANDA

    A. NEDI ´C ANDA. OLSHEVSKY,Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Transactions on Automatic Control, 61 (2016), pp. 3936–3947

    2016

  12. [20]

    NEDI ´C, A

    A. NEDI ´C, A. OLSHEVSKY,ANDM. G. RABBAT,Network topology and communication-computation tradeoffs in decentralized optimization, Proceedings of the IEEE, 106 (2018), pp. 953–976

    2018

  13. [21]

    NEDIC, A

    A. NEDIC, A. OLSHEVSKY,ANDW. SHI,Achieving geometric convergence for distributed optimization over time-varying graphs, SIAM Journal on Optimization, 27 (2017), pp. 2597–2633

    2017

  14. [22]

    NEDIC ANDA

    A. NEDIC ANDA. OZDAGLAR,Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, 54 (2009), pp. 48–61

    2009

  15. [23]

    D. T. A. NGUYEN, D. T. NGUYEN,ANDA. NEDI ´C,Accelerated ab/push–pull methods for distributed opti- mization over time-varying directed networks, IEEE Transactions on Control of Network Systems, 11 (2023), pp. 1395–1407

    2023

  16. [24]

    S. PU ANDA. NEDI ´C,Distributed stochastic gradient tracking methods, Mathematical Programming, 187 (2021), pp. 409–457. 28 Stochastic Push-Pull for Decentralized Nonconvex OptimizationAPREPRINT

    2021

  17. [25]

    S. PU, A. OLSHEVSKY,ANDI. C. PASCHALIDIS,Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent, IEEE signal processing magazine, 37 (2020), pp. 114–122

    2020

  18. [26]

    S. PU, A. OLSHEVSKY,ANDI. C. PASCHALIDIS,A sharp estimate on the transient time of distributed stochastic gradient descent, IEEE Transactions on Automatic Control, 67 (2021), pp. 5900–5915

    2021

  19. [27]

    S. PU, W. SHI, J. XU,ANDA. NEDI ´C,Push–pull gradient methods for distributed optimization in networks, IEEE Transactions on Automatic Control, 66 (2020), pp. 1–16

    2020

  20. [28]

    REN ANDR

    W. REN ANDR. W. BEARD,Consensus seeking in multiagent systems under dynamically changing interaction topologies, IEEE Transactions on automatic control, 50 (2005), pp. 655–661

    2005

  21. [29]

    SAADATNIAKI, R

    F. SAADATNIAKI, R. XIN,ANDU. A. KHAN,Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Transactions on Automatic Control, 65 (2020), pp. 4769–4780

    2020

  22. [30]

    SCUTARI ANDY

    G. SCUTARI ANDY. SUN,Distributed nonconvex constrained optimization over time-varying digraphs, Mathe- matical Programming, 176 (2019), pp. 497–544

    2019

  23. [31]

    W. SHI, Q. LING, G. WU,ANDW. YIN,Extra: An exact first-order algorithm for decentralized consensus optimization, SIAM Journal on Optimization, 25 (2015), pp. 944–966

    2015

  24. [32]

    Z. SONG, W. LI, K. JIN, L. SHI, M. YAN, W. YIN,ANDK. YUAN,Communication-efficient topologies for decentralized learning with o(1) consensus rate, Advances in Neural Information Processing Systems, 35 (2022), pp. 1073–1085

    2022

  25. [33]

    SPIRIDONOFF, A

    A. SPIRIDONOFF, A. OLSHEVSKY,ANDI. C. PASCHALIDIS,Robust asynchronous stochastic gradient-push: Asymptotically optimal and network-independent performance for strongly convex functions, Journal of machine learning research, 21 (2020), pp. 1–47

    2020

  26. [34]

    H. TANG, X. LIAN, M. YAN, C. ZHANG,ANDJ. LIU, d2: Decentralized training over decentralized data, in International Conference on Machine Learning, PMLR, 2018, pp. 4848–4856

    2018

  27. [35]

    Y. TIAN, Y. SUN,ANDG. SCUTARI,Achieving linear convergence in distributed asynchronous multiagent optimization, IEEE Transactions on Automatic Control, 65 (2020), pp. 5264–5279

    2020

  28. [36]

    C. XI, R. XIN,ANDU. A. KHAN,Add-opt: Accelerated distributed directed optimization, IEEE Transactions on Automatic Control, 63 (2017), pp. 1329–1339

    2017

  29. [37]

    XIN ANDU

    R. XIN ANDU. A. KHAN,A linear algorithm for optimization over directed graphs with geometric convergence, IEEE Control Systems Letters, 2 (2018), pp. 315–320

    2018

  30. [38]

    R. XIN, S. PU, A. NEDI ´C,ANDU. A. KHAN,A general framework for decentralized optimization with first-order methods, Proceedings of the IEEE, 108 (2020), pp. 1869–1889

    2020

  31. [39]

    R. XIN, A. K. SAHU, U. A. KHAN,ANDS. KAR,Distributed stochastic optimization with gradient tracking over strongly-connected networks, in 2019 IEEE 58th Conference on Decision and Control (CDC), IEEE, 2019, pp. 8353–8358

    2019

  32. [40]

    T. YANG, X. YI, J. WU, Y. YUAN, D. WU, Z. MENG, Y. HONG, H. WANG, Z. LIN,ANDK. H. JOHANSSON, A survey of distributed optimization, Annual Reviews in Control, 47 (2019), pp. 278–305

    2019

  33. [41]

    B. YING, K. YUAN, Y. CHEN, H. HU, P. PAN,ANDW. YIN,Exponential graph is provably efficient for decentralized deep training, Advances in Neural Information Processing Systems, 34 (2021), pp. 13975–13987

    2021

  34. [42]

    YOU ANDS

    R. YOU ANDS. PU,B-ary tree push-pull method is provably efficient for decentralized learning on heterogeneous data, arXiv preprint arXiv:2404.05454, (2024)

    2024 arXiv

  35. [43]

    YOU ANDS

    R. YOU ANDS. PU,Distributed learning over arbitrary topology: Linear speed-up with polynomial transient time, arXiv preprint arXiv:2503.16123, (2025)

    2025 arXiv

  36. [44]

    K. YUAN, S. A. ALGHUNAIM,ANDX. HUANG,Removing data heterogeneity influence enhances network topology dependence of decentralized sgd, Journal of Machine Learning Research, 24 (2023), pp. 1–53

    2023

  37. [45]

    ZHAO ANDY

    S. ZHAO ANDY. LIU,Asymptotic properties of s-ab method with diminishing step-size, IEEE Transactions on Automatic Control, (2023)

    2023

  38. [46]

    Z. ZHU, Y. TIAN, Y. HUANG, J. XU,ANDS. HE,R-fast: Robust fully-asynchronous stochastic gradient tracking over general topology, IEEE Transactions on Signal and Information Processing over Networks, (2024). 29

    2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.