Pith. sign in

REVIEW 3 major objections 5 minor 42 references

On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs

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

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

Pith's one-line read Stochastic Push-Pull converges at centralized SGD speed on any strongly connected directed graph.

desk verdict 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. read the letter →

arxiv 2506.18075 v5 pith:3Q4H5O6T submitted 2025-06-22 math.OC

Liyuan Liang , Gan Luo , Kun Yuan This is my paper · ORCID
classification math.OC MSC 68W1590C2690C15
keywords decentralizedoptimizationPush-PullmethodABdirectedgraphslinearspeedupstochasticnonconvexgradienttrackingmulti-stepdescentanalysis
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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<T}E\|\nabla f(\hat{x}(t))\|^2 \le \frac{44\$\sigma$\sqrt{L\$\Delta$}}{\sqrt{nT}} + \frac{L\$\Delta$(C_{\$\Delta$,1}/m + 10m\sqrt{s_B s_{Bm}^2} + $c^{{-1}}$)}{T},$$ and with $m=\Theta((nT)^{1/4})$ this is $44\sigma\sqrt{L\Delta}/\sqrt{nT} + O(L\Delta/T^{3/4}) + O(L\Delta/T)$, giving $O(1/(n\epsilon^2))$ iteration complexity. The paper argues this is the first general proof that Push-Pull linearly speeds up over arbitrary strongly connected digraphs, and it identifies why earlier one-step analyses failed: unlike push-only and pull-only methods, Push-Pull's weighted average carries a persistent error that never vanishes or decays. The proof shows that when errors are aggregated over blocks of $m$ iterations, the interior gradient noise cancels and only exponentially attenuated boundary terms remain.

Load-bearing premise

The proof assumes that the graph-dependent constants $c$, $s_B$, $s_{Bm}$, $C_m$, and $C_{\Delta,1}$ stay bounded as the number of nodes grows; the paper does not establish those bounds, and its own parameter choice only makes the linear-speedup term dominant at very large $T$.

Editorial extensions

If this is right

  • Stochastic Push-Pull on any strongly connected digraph reaches $\epsilon$-stationarity in $O(\sigma^2/(n\epsilon^2))$ iterations, matching centralized SGD's iteration count.
  • The persistent, non-vanishing error term that blocked earlier analyses is controlled at $O(\sigma^2/n)$ once the block length is set to $m=\Theta((nT)^{1/4})$, so the obstacle is removed by aggregation rather than by changing the algorithm.
  • In the noiseless case ($\sigma=0$), the same framework yields a deterministic nonconvex convergence rate of order $O(1/T)$ for Push-Pull over digraphs.
  • The proof covers arbitrary strongly connected topologies, so the previous special-case guarantee for B-ary trees is superseded by a general statement.

Reading between the lines

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

  • The telescoping mechanism is not tied to the specific Push-Pull update; the same $m$-step block analysis should transfer to alternating row/column-stochastic variants with momentum, local updates, or time-varying graphs, where linear speedup is currently unproven.
  • The theorem's own constants suggest that the asymptotic $O(1/(n\epsilon^2))$ regime may set in only at very large $T$ on poorly conditioned digraphs, because the proof requires $m\ge c^{-2}n^2s_B^2$ while choosing $m=\Theta((nT)^{1/4})$; quantifying this crossover on a directed cycle or exponential graph would tell practitioners when the speedup is visible.
  • A design principle implicit in the bounds is that maximizing the Perron overlap $c=n\pi_A^\top\pi_B$ between the two mixing matrices should shrink the finite-$T$ constants; constructing weights to maximize this overlap is a concrete, untested extension.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

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 (3)
  1. [Theorem 1, Eq. (42)] 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.
  2. [Lemma 4 and Eq. (53)] 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.
  3. [Table 1, Section 1.2] 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.
minor comments (5)
  1. [Eq. (26)] 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.
  2. [Section 4.1, Eq. (12)] The subscript 'consent' appears to be a typo for 'consensus'; the same term is used in Eqs. (12), (14), and (18).
  3. [Appendix C.2] 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.
  4. [Figure 1] The caption refers to the 'Extra Error Norm' but does not define the plotted quantity; please define it precisely in the caption or text.
  5. [Section 4.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the linear-speedup bound is derived from the stated assumptions, and the self-citations are contextual rather than load-bearing.

full rationale

The derivation chain is self-contained. Theorem 1's bound (26) follows from Assumptions 1–4 through Lemmas 3–5 and Proposition 2, with the full proofs given in Appendices B.1–B.3. The quantities s_A, s_B, c, s_{Bm}, C_m, and C_{Δ,1} are defined in the paper (eqs. (4)–(6), (42), (53)) and are not fitted to data. The choices of m and α are made only after the bound (55) is proven, so they optimize an already-derived estimate rather than importing the conclusion as an input. There is no fitted parameter renamed as a prediction: the experiments use a fixed learning rate and report measured gradient norms, without estimating the theoretical constants. The self-citations [38] and [39] are used for context and for comparison with prior Push-Only and Pull-Only analyses; the only cited lemma, [39, Lemma 12], concerns FROST's exponentially decaying residual in Example 2, which is background and not a premise of the Push-Pull proof. Proposition 2's bounds on s_A and s_B are proved in Appendix A from Perron–Frobenius theory, not imported as an unverified self-citation. No uniqueness theorem from the authors is invoked, and no ansatz is smuggled in via citation: the multi-step descent identity (20) is introduced and proved in Section 4 and Appendix B. Finally, the paper's own footnote in Section 4.2 states that the rigorous choice of m is more involved than the simplified condition m ≥ Const·n^2; this indicates a possible scaling weakness in the advertised O(1/(n ε^2)) claim when the matrix constants C_m and C_{Δ,1} are n-dependent, but that is a correctness concern about hidden n-dependence, not a circularity. Accordingly, no circular step can be exhibited, and the honest finding is no significant circularity.

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

No data-fitted parameters exist in this proof. The block length m and step size α are proof-selected hyperparameters, not fitted constants. The effectively unstated premise that graph constants are n-independent is listed as an ad hoc axiom because it is load-bearing for the linear speedup claim.

assumptions (4)
  • standard math Perron-Frobenius theorem
    Used in Proposition 1 to obtain Perron vectors and exponential decay of A^t and B^t; load-bearing for all geometric-decay bounds.
  • domain assumption L-smoothness and bounded variance (Assumptions 3 and 4)
    Standard stochastic optimization assumptions; needed for the descent lemma and noise estimates.
  • domain assumption Bounded suboptimality f_i(x)-inf f_i ≤ Δ (Assumption 4)
    Used to bound f(x(0))-f(x(T)) and to define C_{Δ,1}; can fail for unbounded losses.
  • ad hoc to paper Graph-dependent constants are treated as constants independent of n in the final complexity claim
    The theorem's O(1/(nε^2)) statement requires c^{-2}n^2s_B^2 and C_{Δ,1} not to destroy the 1/n scaling; the paper does not bound their n-growth.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs." pith.science (2026). https://pith.science/paper/3Q4H5O6T

@misc{pith2026250618075,
  author       = {Pith},
  title        = {Pith review of: On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3Q4H5O6T}},
  note         = {Machine review of arXiv:2506.18075}
}
read the original abstract

The linear speedup property is essential for demonstrating the advantage of distributed algorithms over their single-node counterparts. In this paper, we study the stochastic Push-Pull method, a widely adopted decentralized optimization algorithm over directed graphs (digraphs). Unlike methods that rely solely on row-stochastic or column-stochastic mixing matrices, Push-Pull avoids nonlinear correction and has shown superior empirical performance across a variety of settings. However, its theoretical analysis remains challenging, and the linear speedup property has not been generally establishe--revealing a significant gap between empirical success and limited theoretical understanding. To bridge this gap, we propose a novel analysis framework and prove that Push-Pull achieves linear speedup over arbitrary strongly connected digraphs. Our results provide the comprehensive theoretical understanding for stochastic Push-Pull, aligning its theory with empirical performance. Code: https://github.com/pkumelon/PushPull.

Figures

Figures reproduced from arXiv: 2506.18075 by the authors.

Figure 1
Figure 1. With a fixed stepsize α, the error term ϵ (t) in Push-Pull does not vanish but rapidly stabilizes at a non￾negligible constant. Results are shown for logistic regression on a synthetic dataset. 4.1 Limitations of single-step descent analysis Following conventional single-step descent analysis, we establish the descent inequality based on up￾date (11): ∥∇f(ˆx (t) )∥ 2≲ f(ˆx (t) )−Et[f(ˆx (t+1))] cα + cαL n σ 2+αL∥π ⊤… view at source ↗
Figure 2
Figure 2. Linear speedup performance over various topologies on synthetic data, the learning rates are all [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Linear speedup performance over various topologies, the learning rates are the same over the same topology. [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The test accuracy across different numbers of nodes and various topologies. All experiments were conducted [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: Comparison of uniform (left) and heterogeneous (right) data distributions across [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 35 canonical work pages

  1. [1]

    Scaling distributed machine learning with the parameter server

    Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pages 583–598, 2014

    work page 2014

  2. [2]

    Bandwidth optimal all-reduce algorithms for clusters of workstations

    Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing, 69(2):117–124, 2009

    2009

  3. [3]

    Diffusion adaptation strategies for distributed optimization and learning over networks.IEEE Transactions on Signal Processing, 60(8):4289–4305, 2012

    Jianshu Chen and Ali H Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks.IEEE Transactions on Signal Processing, 60(8):4289–4305, 2012

    work page 2012

  4. [4]

    Distributed subgradient methods for multi-agent optimization

    Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009

    2009

  5. [5]

    Stochastic gradient push for distributed deep learning

    Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. InInternational Conference on Machine Learning, pages 344–353. PMLR, 2019. 16 0 150 300 450 Epochs 0% 20% 40% 60% 80% 100%Accuracy Exponential n=1 n=4 n=8 0 150 300 450 Epochs 0% 20% 40% 60% 80% 100%Accuracy Grid n=1 n=4 n=9 0 150 300 4...

    work page 2019

  6. [6]

    Communication- efficient topologies for decentralized learning witho(1) consensus rate.Advances in Neural Information Processing Systems, 35:1073–1085, 2022

    Zhuoqing Song, Weijian Li, Kexin Jin, Lei Shi, Ming Yan, Wotao Yin, and Kun Yuan. Communication- efficient topologies for decentralized learning witho(1) consensus rate.Advances in Neural Information Processing Systems, 35:1073–1085, 2022

    work page 2022

  7. [7]

    B-ary tree push-pull method is provably efficient for decentralized learning on heterogeneous data, 2024

    Runze You and Shi Pu. B-ary tree push-pull method is provably efficient for decentralized learning on heterogeneous data, 2024

    work page 2024

  8. [8]

    Distributed optimization over time-varying directed graphs.IEEE Transactions on Automatic Control, 60(3):601–615, 2015

    Angelia Nedi´ c and Alex Olshevsky. Distributed optimization over time-varying directed graphs.IEEE Transactions on Automatic Control, 60(3):601–615, 2015

    work page 2015

Show all 42 references
  1. [9]

    Achieving geometric convergence for distributed optimiza- tion over time-varying graphs.SIAM Journal on Optimization, 27(4):2597–2633, 2017

    Angelia Nedi´ c, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimiza- tion over time-varying graphs.SIAM Journal on Optimization, 27(4):2597–2633, 2017

    2017

  2. [10]

    Adaptive networks.Proceedings of the IEEE, 102(4):460–497, 2014

    Ali H Sayed. Adaptive networks.Proceedings of the IEEE, 102(4):460–497, 2014

    2014

  3. [11]

    Distributed optimization over weighted directed graphs using row stochastic matrix

    Van Sy Mai and Eyad H Abed. Distributed optimization over weighted directed graphs using row stochastic matrix. In2016 American Control Conference (ACC), pages 7165–7170. IEEE, 2016

    2016

  4. [12]

    Gossip-based computation of aggregate information

    David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 482–

    2003

  5. [13]

    Push-sum distributed dual averaging for convex optimization

    Konstantinos I Tsianos, Sean Lawlor, and Michael G Rabbat. Push-sum distributed dual averaging for convex optimization. In2012 ieee 51st ieee conference on decision and control (cdc), pages 5453–5458. IEEE, 2012

    2012

  6. [14]

    Extrapush for convex smooth decentralized optimization over directed networks.Journal of Computational Mathematics, pages 383–396, 2017

    Jinshan Zeng and Wotao Yin. Extrapush for convex smooth decentralized optimization over directed networks.Journal of Computational Mathematics, pages 383–396, 2017

    2017

  7. [15]

    Dextra: A fast algorithm for optimization over directed graphs

    Chenguang Xi and Usman A Khan. Dextra: A fast algorithm for optimization over directed graphs. IEEE Transactions on Automatic Control, 62(10):4980–4993, 2017

    2017

  8. [16]

    Add-opt: Accelerated distributed directed optimization

    Chenguang Xi, Ran Xin, and Usman A Khan. Add-opt: Accelerated distributed directed optimization. IEEE Transactions on Automatic Control, 63(5):1329–1339, 2017

    2017

  9. [17]

    S-addopt: Decentralized stochastic first-order optimization over directed graphs.IEEE Control Systems Letters, 5(3):953–958, 2020

    Muhammad I Qureshi, Ran Xin, Soummya Kar, and Usman A Khan. S-addopt: Decentralized stochastic first-order optimization over directed graphs.IEEE Control Systems Letters, 5(3):953–958, 2020

    2020

  10. [18]

    Row-stochastic matrices based distributed optimiza- tion algorithm with uncoordinated step-sizes

    Huaqing Li, Jinmeng Wang, and Zheng Wang. Row-stochastic matrices based distributed optimiza- tion algorithm with uncoordinated step-sizes. In2019 6th International Conference on Information, Cybernetics, and Computational Social Systems (ICCSS), pages 124–131. IEEE, 2019

    2019

  11. [19]

    Frost—fast row-stochastic optimization with uncoordinated step-sizes.EURASIP Journal on Advances in Signal Processing, 2019, 01 2019

    Ran Xin, Chenguang xi, and Usman Khan. Frost—fast row-stochastic optimization with uncoordinated step-sizes.EURASIP Journal on Advances in Signal Processing, 2019, 01 2019

    2019

  12. [20]

    A fast row- stochastic decentralized method for distributed optimization over directed graphs.IEEE Transactions on Automatic Control, 69(1):275–289, 2023

    Diyako Ghaderyan, Necdet Serhat Aybat, A Pedro Aguiar, and Fernando Lobo Pereira. A fast row- stochastic decentralized method for distributed optimization over directed graphs.IEEE Transactions on Automatic Control, 69(1):275–289, 2023

    2023

  13. [21]

    Qingguo L¨ u, Xiaofeng Liao, Huaqing Li, and Tingwen Huang. A nesterov-like gradient tracking algo- rithm for distributed optimization over directed networks.IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(10):6258–6270, 2020

    2020

  14. [22]

    Push–pull gradient methods for distributed optimiza- tion in networks.IEEE Transactions on Automatic Control, 66(1):1–16, 2020

    Shi Pu, Wei Shi, Jinming Xu, and Angelia Nedi´ c. Push–pull gradient methods for distributed optimiza- tion in networks.IEEE Transactions on Automatic Control, 66(1):1–16, 2020

    2020

  15. [23]

    A linear algorithm for optimization over directed graphs with geometric convergence.IEEE Control Systems Letters, 2(3):315–320, 2018

    Ran Xin and Usman A Khan. A linear algorithm for optimization over directed graphs with geometric convergence.IEEE Control Systems Letters, 2(3):315–320, 2018

    2018

  16. [24]

    Ab/push-pull method for dis- tributed optimization in time-varying directed networks.Optimization Methods and Software, pages 1–28, 2023

    Angelia Nedi´ c, Duong Thuy Anh Nguyen, and Duong Tung Nguyen. Ab/push-pull method for dis- tributed optimization in time-varying directed networks.Optimization Methods and Software, pages 1–28, 2023

    2023

  17. [25]

    Distributed stochastic optimization with gradient tracking over strongly-connected networks

    Ran Xin, Anit Kumar Sahu, Usman A Khan, and Soummya Kar. Distributed stochastic optimization with gradient tracking over strongly-connected networks. In2019 IEEE 58th Conference on Decision and Control (CDC), pages 8353–8358. IEEE, 2019. 18

    2019

  18. [26]

    Asymptotic properties ofS-ABmethod with diminishing step-size

    Shengchao Zhao and Yongchao Liu. Asymptotic properties ofS-ABmethod with diminishing step-size. IEEE Transactions on Automatic Control, 69(5):3222–3229, 2023

    2023

  19. [27]

    Acceleratedab/push–pull methods for distributed optimization over time-varying directed networks.IEEE Transactions on Control of Network Systems, 11(3):1395–1407, 2023

    Duong Thuy Anh Nguyen, Duong Tung Nguyen, and Angelia Nedi´ c. Acceleratedab/push–pull methods for distributed optimization over time-varying directed networks.IEEE Transactions on Control of Network Systems, 11(3):1395–1407, 2023

    2023

  20. [28]

    Push-pull based distributed primal-dual algorithm for coupled constrained convex optimization in multi-agent networks.arXiv preprint arXiv:2310.15626, 2023

    Kai Gong and Liwei Zhang. Push-pull based distributed primal-dual algorithm for coupled constrained convex optimization in multi-agent networks.arXiv preprint arXiv:2310.15626, 2023

    2023 arXiv

  21. [29]

    Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji 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

  22. [30]

    Exact diffusion for distributed optimization and learning—part i: Algorithm development.IEEE Transactions on Signal Processing, 67(3):708–723, 2018

    Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H Sayed. Exact diffusion for distributed optimization and learning—part i: Algorithm development.IEEE Transactions on Signal Processing, 67(3):708–723, 2018

    2018

  23. [31]

    A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates.IEEE Transactions on Signal Processing, 67(17):4494–4506, 2019

    Zhi Li, Wei Shi, and Ming Yan. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates.IEEE Transactions on Signal Processing, 67(17):4494–4506, 2019

    2019

  24. [32]

    Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes

    Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. InIEEE Conference on Decision and Control (CDC), pages 2055–2060, Osaka, Japan, 2015

    2015

  25. [33]

    Di Lorenzo and G

    P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization.IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016

    2016

  26. [34]

    Harnessing smoothness to accelerate distributed optimization.IEEE Trans- actions on Control of Network Systems, 5(3):1245–1260, 2017

    Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization.IEEE Trans- actions on Control of Network Systems, 5(3):1245–1260, 2017

    2017

  27. [35]

    Distributed stochastic gradient tracking methods.Mathematical Program- ming, 187(1):409–457, 2021

    Shi Pu and Angelia Nedi´ c. Distributed stochastic gradient tracking methods.Mathematical Program- ming, 187(1):409–457, 2021

    2021

  28. [36]

    A unified theory of decentralized sgd with changing topology and local updates

    Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. InInternational Conference on Machine Learning, pages 5381–5393. PMLR, 2020

    2020

  29. [37]

    Decentralized asyn- chronous non-convex stochastic optimization on directed graphs.IEEE Transactions on Control of Network Systems, 2023

    Vyacheslav Kungurtsev, Mahdi Morafah, Tara Javidi, and Gesualdo Scutari. Decentralized asyn- chronous non-convex stochastic optimization on directed graphs.IEEE Transactions on Control of Network Systems, 2023. 19

    2023

  30. [38]

    Understanding the influence of digraphs on decentralized optimization: Effective metrics, lower bound, and optimal algorithm.SIAM Journal on Optimization, 35(3):1570–1600, 2025

    Liyuan Liang, Xinmeng Huang, Ran Xin, and Kun Yuan. Understanding the influence of digraphs on decentralized optimization: Effective metrics, lower bound, and optimal algorithm.SIAM Journal on Optimization, 35(3):1570–1600, 2025

    2025

  31. [39]

    Achieving linear speedup and near-optimal complexity for decentralized optimization over row-stochastic networks

    Liyuan Liang, Xinyi Chen, Gan Luo, and Kun Yuan. Achieving linear speedup and near-optimal complexity for decentralized optimization over row-stochastic networks. InForty-second International Conference on Machine Learning, 2025

    2025

  32. [40]

    Exact and linear convergence for federated learning under arbitrary client participation is attainable.arXiv preprint arXiv:2503.20117, 2025

    Bicheng Ying, Zhe Li, and Haibo Yang. Exact and linear convergence for federated learning under arbitrary client participation is attainable.arXiv preprint arXiv:2503.20117, 2025

    2025

  33. [41]

    Zur theorie der matrices.Mathematische Annalen, 64(2):248–263, 1907

    Oskar Perron. Zur theorie der matrices.Mathematische Annalen, 64(2):248–263, 1907

    1907

  34. [42]

    Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices.IEEE Transactions on Automatic Control, 65(11):4769–4780, 2020

    Fakhteh Saadatniaki, Ran Xin, and Usman A Khan. Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices.IEEE Transactions on Automatic Control, 65(11):4769–4780, 2020. A Linear Algebra Inequalities Lemma 5(Rolling Sum Lemma).For a r...

    2020

Pith tools

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