Pith. sign in

REVIEW 3 major objections 6 minor 52 references

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks

T0 review · 3 major / 6 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 This paper claims to settle, up to a logarithmic factor, the optimal convergence rate for nonconvex stochastic decentralized optimization when nodes communicate with row-stochastic mixing matrices—the setting where each node normalizes by…

desk verdict Real algorithmic progress in the row-stochastic setting, but the headline lower bound rests on a transpose argument that does not hold; the optimality claim is unproven as written. read the letter →

arxiv 2506.04600 v1 pith:RA4JBC73 submitted 2025-06-05 math.OC

Liyuan Liang , Xinyi Chen , Gan Luo , Kun Yuan This is my paper
classification math.OC MSC 90C1590C2668W15
keywords decentralizedoptimizationrow-stochasticnetworksconvergencelowerboundgradienttrackinglinearspeedupmulti-stepgossipnonconvexstochastic
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 claims to settle, up to a logarithmic factor, the optimal convergence rate for nonconvex stochastic decentralized optimization when nodes communicate with row-stochastic mixing matrices—the setting where each node normalizes by its in-degree and out-degree information is unavailable. It introduces two metrics, the generalized spectral gap and the equilibrium skewness of the mixing matrix, and proves a lower bound showing that any first-order algorithm of this type must pay a penalty proportional to $(1+\ln\kappa_A)/(1-\beta_A)$ plus the standard stochastic term $\sigma/\sqrt{nK}$. The authors then prove that the Pull-Diag gradient tracking algorithm achieves linear speedup for the first time in this row-stochastic setting, and that a multi-gossip variant reaches the lower bound up to a $\ln n$ gap. If true, this would make row-stochastic decentralized optimization as well understood as the doubly- and column-stochastic cases.

What carries the argument

The load-bearing object is the row-stochastic mixing matrix $A$ with $A\mathbf 1=\mathbf 1$ and its left Perron vector $\pi_A$. Its influence is summarized by two metrics: the generalized spectral gap $\beta_A=\|A-A_\infty\|_{\pi_A}$, which controls how fast $A^k$ converges to its rank-one limit, and the equilibrium skewness $\kappa_A=\max(\pi_A)/\min(\pi_A)$, which controls how far that limit lies from the uniform average. The proof machinery adds the Pull-Diag correction, which uses the diagonal of $A^k$ to convert the biased limit $\mathbf 1\pi_A^\top z$ into the true average, and then replaces one gossip round by $R$ rounds of $A^R$ so the inverted diagonal entries are bounded without extra assumptions.

What would settle it

Compute the two gap measures for $W=\begin{bmatrix}0.9 & 0.3\\0.1 & 0.7\end{bmatrix}$, which is column-stochastic with uniform left Perron vector, and for $A=W^\top$, which is row-stochastic with left Perron vector $(0.75,0.25)$. Direct calculation gives $\beta_W\approx 0.632$ while $\beta_A\approx 0.600$, disproving the equality $\beta_A=\beta_W$ asserted in Proposition 8 and hence invalidating the existence construction behind the lower bound as written.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: in the nonconvex, stochastic, row-stochastic setting, any decentralized first-order algorithm that communicates by partial averaging with a primitive row-stochastic matrix $A$ must satisfy $$\mathbb{E}\|\nabla f(\hat{x}^{(K)})\|^2 = \$\Omega$\!\left(\frac{\$\sigma$\sqrt{L\$\Delta$}}{\sqrt{nK}} + \frac{(1+\ln\kappa_A)L\$\Delta$}{(1-\beta_A)K}\right),$$ where $\beta_A$ is the generalized spectral gap and $\kappa_A$ is the equilibrium skewness. The first summand is the standard linear-speedup noise floor; the second is the network-dependent penalty that is new here. The matching upper bound is obtained by MG-PULL-DIAG-GT, which runs $R=\lceil 3(1+\ln\kappa_A+\ln n)/(1-\beta_A)\rceil$ gossip rounds per communication step and achieves the same rate with an extra $\ln n$ factor, hence near-optimality.

Load-bearing premise

The lower bound rests on the claim that one can build a row-stochastic matrix with any prescribed spectral gap and skewness by transposing a column-stochastic matrix; that step assumes the two gap measures stay equal under transposition.

Editorial extensions

If this is right

  • Every row-stochastic decentralized first-order algorithm inherits the network penalty $(1+\ln\kappa_A)/(1-\beta_A)$, so topology enters the rate through both spectral gap and skewness, not gap alone.
  • Pull-Diag-GT provably achieves linear speedup in $n$ for row-stochastic networks, matching the $\sigma/\sqrt{nK}$ stochastic floor.
  • MG-PULL-DIAG-GT attains the lower bound up to a $\ln n$ gap, making the pair near-optimal for the row-stochastic setting.
  • Setting $\sigma=0$ gives the first deterministic lower bound for row-stochastic decentralized optimization.
  • Numerical tests on synthetic nonconvex logistic regression, MNIST, and CIFAR-10 confirm faster convergence with multi-gossip across ring, grid, geometric, and nearest-neighbor topologies.

Reading between the lines

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

  • The authors leave implicit that a tight lower bound makes ROW-ONLY communication strictly more expensive than COL-ONLY: compared with a column-stochastic matrix of the same spectral gap, a row-stochastic matrix pays an extra $\ln(\kappa_A)$ factor because its consensus limit is skewed away from the uniform average.
  • The $\ln n$ gap between the upper and lower bounds likely comes from the crude bound $[\pi_A]_i \ge 1/(n\kappa_A)$ in the diagonal-stability argument; replacing it by a tighter lower bound on the Perron vector would turn near-optimality into exact optimality.
  • A direct empirical test of the metric pair would fix $\beta_A$ while varying $\kappa_A$ over graphs of equal size and check that the gradient-norm decay shifts by $(1+\ln\kappa_A)$; the paper's experiments vary $n$ and topology together, so they do not isolate this prediction.
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 / 6 minor

Summary. The paper studies nonconvex decentralized stochastic optimization over directed networks with row-stochastic mixing matrices. It proposes two metrics, the generalized spectral gap β_A and the equilibrium skewness κ_A, to characterize the influence of the mixing matrix. The main contributions are: (i) a claimed first convergence lower bound (Theorem 1) for row-stochastic decentralized first-order algorithms; (ii) a new analysis showing that the existing PULL-DIAG-GT algorithm achieves linear speedup (Theorem 2); and (iii) a multi-gossip variant MG-PULL-DIAG-GT that attains the lower bound up to a logarithmic factor (Theorem 3). Numerical experiments on synthetic and image-classification tasks are provided in support.

Significance. If Theorem 1 were valid, it would be the first lower bound for decentralized optimization over row-stochastic networks and would certify near-optimality of MG-PULL-DIAG-GT. The algorithmic analysis in Theorems 2 and 3 appears nontrivial and independent of the lower-bound construction, and the experiments give reasonable empirical support. However, the lower-bound proof contains a demonstrable error in the matrix existence construction (Proposition 8), and the theorem as stated is not supported by the proof. Since the optimality claim of the paper rests on this lower bound, the central novelty is currently unproven.

major comments (3)
  1. [Appendix A.1, Proposition 8] The equality β_A = β_W for A = W^T is false under the definitions stated in Section 1. For a row-stochastic A, β_A = ||Π_A^{1/2}(A − 1_n π_A^T)Π_A^{−1/2}||_2. If W is column-stochastic with right Perron vector π_W = π_A and A = W^T, then the proof computes β_A as the norm of (Π_W^{−1/2}(W − π_W 1_n^T)Π_W^{1/2})^T. However, applying the paper's π-norm definition directly to W gives β_W = ||Π_W^{1/2}(W − π_W 1_n^T)Π_W^{−1/2}||_2, which is not equal to the previous expression when Π_W is nonuniform. A concrete counterexample is W = [[0.9, 0.2], [0.1, 0.8]], for which the two quantities differ. Therefore the chain of equalities in Proposition 8 is invalid, and the existence of the row-stochastic matrix used in Theorem 1 is not established.
  2. [Theorem 1 and Appendix A.2] Theorem 1 states that for every β̃ ∈ [0.01, 1 − 1/n] there exists a row-stochastic A with β_A = β̃ and ln(κ_A) = Ω(n(1 − β_A)). Proposition 8, even if its transpose claim were correct, only constructs a matrix with β_A = √2/2 and κ_A = 2n − 1. Thus ln(κ_A) = O(log n), which is incompatible with the Ω(n) skewness required by Theorem 1 for β_A = √2/2. Moreover, the proof in Appendix A.2 refers to a parameter 'ϵ = 2β_A^2 − 1' and a 'mixing matrix W in Subsection 8' that do not appear in Proposition 8 as stated. Consequently, the full quantification over β̃ in Theorem 1 is unproven; the argument as written establishes at most a special-case bound for a single value of β_A.
  3. [Appendix A.2, Step 3] The lower-bound proof assumes K ≥ n when setting d = 2⌊K/(2n/3)⌋ + 2 ≤ 5K/n, but Theorem 1 does not state a range restriction on K. The statement should either specify K ≥ n or provide an argument for all K, including the small-K regime.
minor comments (6)
  1. [Section 2.1, Assumption 1] The direction convention for a_{ij} is stated both as 'node j can send information to node i' and as 'if (i→j) ∈ E'; since the update z_i^+ = Σ_j a_{ij} z_j uses incoming edges, please make the convention unambiguous.
  2. [Figure 1] The legend entries such as 'A = 0.77, A = 5.3 + e04' appear to have lost the β_A and κ_A symbols; the typesetting should be corrected.
  3. [Appendix A.2] The reference to 'Subsection 8' should be to Appendix A.1, and the parameter ϵ in 'with ϵ = 2β_A^2 − 1' is not defined in the manuscript.
  4. [Lemma 12] The symbol π_A is used both for the Perron vector and for the scalar min_i[π_A]_i; please use separate notation to avoid confusion.
  5. [Theorem 3 and Appendix D] The choice of R is stated as R = ⌈3(1 + ln κ_A + ln n)/(1 − β_A)⌉ in Theorem 3 but derived as R ≈ (1 + 3 ln κ_A + 3 ln n)/(1 − β_A) in Appendix D; these constants should be aligned.
  6. [Lemma 2] The notation d_k uses [D_k]_j for diagonal entries; write [D_k]_{jj} for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithmic convergence proofs are self-contained, and the lower-bound proof's reliance on the authors' prior column-stochastic theorem is an ordinary citation, not an assumption of the row-stochastic result.

full rationale

The upper-bound derivations (Theorems 2 and 3) are carried out from first principles in Appendices C and D: descent, consensus, and descent-deviation estimates are proven with explicit constants depending on β_A, κ_A, θ_A, and s_A, and the final rates are obtained by choosing a learning rate and gossip round R. No parameter is fitted from the quantities being predicted, and the convergence rates are not manufactured by assuming the lower bound. The lower-bound proof in Appendix A does lean heavily on prior work by the same authors: Proposition 8 imports Proposition 2.5 of Liang et al. (2023) to obtain a column-stochastic matrix W and then passes to A = W^T. This is a genuine and load-bearing self-citation, and the transpose step is mathematically delicate (the equality β_A = β_W depends on the π-norm convention used for column-stochastic matrices). However, reliance on a prior theorem is not circularity: the cited result concerns column-stochastic matrices, the present result concerns row-stochastic matrices, and the row-stochastic lower bound is not an input to the cited theorem. If Proposition 8 is wrong, Theorem 1 is unsupported as a matter of correctness, not because the claim reduces to its own assumptions. The paper also explicitly discloses the limitation that the explicit influence of θ_A on PULL-DIAG-GT remains unclear (Section 7) and that Theorem 3 matches the lower bound only up to a logarithmic gap ln(n) (Remark 3). These are honest caveats, not hidden circular steps. No self-definitional metric, no fitted parameter renamed as a prediction, and no self-citation chain that defines the target result was found.

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

The theoretical results use standard smoothness and oracle assumptions plus a specific structural assumption about row-stochastic mixing matrices (Assumption 1) and, for the basic algorithm, a bounded-diagonal condition (Assumption 4). No new physical or mathematical entities are introduced, and no constants are fitted to empirical data.

free parameters (1)
  • experimental learning rate α = manually tuned per topology (e.g., 0.005, 0.01, 0.02)
    Used only in the experiments; chosen by hand rather than derived from theory. Does not affect the theoretical convergence claims.
assumptions (6)
  • domain assumption Assumption 1: row-stochastic primitive mixing matrix with positive self-loop weights
    All results assume A1=1, primitivity, and self-loops. Stated in Section 2.1.
  • domain assumption Assumption 2: L-smoothness of each local loss and bounded initial function gap
    Standard smooth nonconvex assumptions for the function class. Stated in Section 3.1.
  • domain assumption Assumption 3: unbiased stochastic gradients with bounded variance and independent noise across nodes
    Oracle model for stochastic gradients; the variance bound σ^2 is used in all upper and lower bounds. Stated in Section 3.1.
  • domain assumption Assumption 4: bounded diagonals of A^k (bounded θ_A)
    Required for PULL-DIAG-GT to avoid inversion of near-zero diagonal entries; later removed in MG-PULL-DIAG-GT via multiple gossip rounds. Stated in Section 4.1.
  • standard math Linear-spanning property of the algorithm class for the lower bound
    Defines the class of algorithms to which the lower bound applies, following Carmon et al. and prior decentralized lower-bound works. Stated in Section 3.1.
  • domain assumption The generalized spectral gap β_A and equilibrium skewness κ_A fully capture the influence of a row-stochastic mixing matrix on convergence
    The paper's central modeling claim: these two metrics are sufficient to characterize network impact. The proofs of Theorems 1, 2, and 3 all rely on this assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks." pith.science (2026). https://pith.science/paper/RA4JBC73

@misc{pith2026250604600,
  author       = {Pith},
  title        = {Pith review of: Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RA4JBC73}},
  note         = {Machine review of arXiv:2506.04600}
}
read the original abstract

A key challenge in decentralized optimization is determining the optimal convergence rate and designing algorithms to achieve it. While this problem has been extensively addressed for doubly-stochastic and column-stochastic mixing matrices, the row-stochastic scenario remains unexplored. This paper bridges this gap by introducing effective metrics to capture the influence of row-stochastic mixing matrices and establishing the first convergence lower bound for decentralized learning over row-stochastic networks. However, existing algorithms fail to attain this lower bound due to two key issues: deviation in the descent direction caused by the adapted gradient tracking (GT) and instability introduced by the Pull-Diag protocol. To address descent deviation, we propose a novel analysis framework demonstrating that Pull-Diag-GT achieves linear speedup, the first such result for row-stochastic decentralized optimization. Moreover, by incorporating a multi-step gossip (MG) protocol, we resolve the instability issue and attain the lower bound, achieving near-optimal complexity for decentralized optimization over row-stochastic networks.

Figures

Figures reproduced from arXiv: 2506.04600 by the authors.

Figure 1
Figure 1. Convergence of PULL-DIAG protocol on different mix￾ing matrices with varying spectral gaps (βA) and equilibrium skew￾ness (κA). The y-axis represents the consensus error ∥z (k) − 1n1 ⊤ n z/n∥. The left plot shows fixed κA with different βA, while the right plot shows fixed βA with different κA. Function class. We define the function class F∆,L as the set of functions that satisfy Assumption 2, for any given dimensio… view at source ↗
Figure 2
Figure 2. Performance of PULL-DIAG-GT for non-convex logistic regression evaluated across exponential graphs and ring graphs. Number n denotes the number of nodes. 6.2. Neural Network for Multi-Class Classification In the second group of experiment, we focus on a digit￾classification task using the MNIST dataset. We evaluate the performance of MG-PULL-DIAG-GT against the vanilla PULL-DIAG-GT across four distinct network topol… view at source ↗
Figure 3
Figure 3. Averaged training loss of neural networks on MNIST dataset. Networks trained using MG-PULL-DIAG-GT and vanilla PULL-DIAG-GT. Here, “MG” denotes the number of gossip steps [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Averaged training loss of neural networks on CIFAR-10 dataset. Networks trained using MG-PULL-DIAG-GT and vanilla PULL-DIAG-GT. Here, “MG” denotes the number of gossip steps. illustrates the stability of MG-PULL-DIAG-GT when ap￾plied to a larger real-world dataset. In …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

52 extracted references · 43 canonical work pages

  1. [1]

    Alghunaim, S. A. and Yuan, K. A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing, 70: 0 3264--3279, 2022

    work page 2022

  2. [2]

    Penalized likelihood regression for generalized linear models with non-quadratic penalties

    Antoniadis, A., Gijbels, I., and Nikolova, M. Penalized likelihood regression for generalized linear models with non-quadratic penalties. Annals of the Institute of Statistical Mathematics, 63: 0 585--615, 2011

    work page 2011

  3. [3]

    C., Foster, D

    Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. E. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199: 0 165--214, 2019. URL https://api.semanticscholar.org/CorpusID:208637439

    work page 2019

  4. [4]

    Stochastic gradient push for distributed deep learning

    Assran, M., Loizou, N., Ballas, N., and Rabbat, M. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pp.\ 344--353. PMLR, 2019

    work page 2019

  5. [5]

    E., and Nocedal, J

    Bottou, L., Curtis, F. E., and Nocedal, J. Optimization methods for large-scale machine learning. SIAM review, 60 0 (2): 0 223--311, 2018

    work page 2018

  6. [6]

    C., Hinder, O., and Sidford, A

    Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points i. Mathematical Programming, 184 0 (1-2): 0 71--120, 2020

    work page 2020

  7. [7]

    C., Hinder, O., and Sidford, A

    Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185 0 (1-2): 0 315--355, 2021

    work page 2021

  8. [8]

    and Scutari, G

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

    work page 2016

Show all 52 references
  1. [9]

    S., Aguiar, A

    Ghaderyan, D., Aybat, N. S., Aguiar, A. P., and Pereira, F. L. A fast row-stochastic decentralized method for distributed optimization over directed graphs. IEEE Transactions on Automatic Control, 69 0 (1): 0 275--289, 2023

    2023

  2. [10]

    Deep residual learning for image recognition

    He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.\ 770--778, 2016

    2016

  3. [11]

    and Yuan, K

    Huang, X. and Yuan, K. Optimal complexity in non-convex decentralized learning over time-varying networks. arXiv preprint arXiv:2211.00533, 2022

    2022 arXiv

  4. [12]

    Lower bounds and nearly optimal algorithms in distributed learning with communication compression

    Huang, X., Chen, Y., Yin, W., and Yuan, K. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 35: 0 18955--18969, 2022

    2022

  5. [13]

    Gossip-based computation of aggregate information

    Kempe, D., Dobra, A., and Gehrke, J. Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp.\ 482--491. IEEE, 2003

    2003

  6. [14]

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

    Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp.\ 5381--5393. PMLR, 2020

    2020

  7. [15]

    Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks

    Kovalev, D., Gasanov, E., Gasnikov, A., and Richtarik, P. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021

    2021

  8. [16]

    Decentralized asynchronous non-convex stochastic optimization on directed graphs

    Kungurtsev, V., Morafah, M., Javidi, T., and Scutari, G. Decentralized asynchronous non-convex stochastic optimization on directed graphs. IEEE Transactions on Control of Network Systems, 2023

    2023

  9. [17]

    and Lin, Z

    Li, H. and Lin, Z. Accelerated gradient tracking over time-varying graphs for decentralized optimization. Journal of Machine Learning Research, 25 0 (274): 0 1--52, 2024

    2024

  10. [18]

    Row-stochastic matrices based distributed optimization algorithm with uncoordinated step-sizes

    Li, H., Wang, J., and Wang, Z. Row-stochastic matrices based distributed optimization algorithm with uncoordinated step-sizes. In 2019 6th International Conference on Information, Cybernetics, and Computational Social Systems (ICCSS), pp.\ 124--131. IEEE, 2019

    2019

  11. [19]

    Li, W., Lv, T., Ni, W., Zhao, J., Hossain, E., and Poor, H. V. Decentralized federated learning over imperfect communication channels. IEEE Transactions on Communications, 2024

    2024

  12. [20]

    Towards better understanding the influence of directed networks on decentralized stochastic optimization

    Liang, L., Huang, X., Xin, R., and Yuan, K. Towards better understanding the influence of directed networks on decentralized stochastic optimization. arXiv preprint arXiv:2312.04928, 2023

    2023 arXiv

  13. [21]

    A nesterov-like gradient tracking algorithm for distributed optimization over directed networks

    L \"u , Q., Liao, X., Li, H., and Huang, T. A nesterov-like gradient tracking algorithm for distributed optimization over directed networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51 0 (10): 0 6258--6270, 2020

    2020

  14. [22]

    and De Sa, C

    Lu, Y. and De Sa, C. Optimal complexity in decentralized training. In International Conference on Machine Learning, pp.\ 7111--7123. PMLR, 2021

    2021

  15. [23]

    Mai, V. S. and Abed, E. H. Distributed optimization over weighted directed graphs using row stochastic matrix. In 2016 American Control Conference (ACC), pp.\ 7165--7170. IEEE, 2016

    2016

  16. [24]

    and Olshevsky, A

    Nedi \'c , A. and Olshevsky, A. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60 0 (3): 0 601--615, 2014

    2014

  17. [25]

    Achieving geometric convergence for distributed optimization over time-varying graphs

    Nedi\' c , A., Olshevsky, A., and Shi, W. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27 0 (4): 0 2597--2633, 2017. doi:10.1137/16M1084316

    2017 doi

  18. [26]

    Achieving geometric convergence for distributed optimization over time-varying graphs

    Nedic, A., Olshevsky, A., and Shi, W. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27 0 (4): 0 2597--2633, 2017

    2017

  19. [27]

    Nedi \'c , A., Olshevsky, A., and Rabbat, M. G. Network topology and communication-computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106 0 (5): 0 953--976, 2018

    2018

  20. [28]

    and Olshevsky, A

    Nedić, A. and Olshevsky, A. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60 0 (3): 0 601--615, 2015. doi:10.1109/TAC.2014.2364096

    2015

  21. [29]

    Zur theorie der matrices

    Perron, O. Zur theorie der matrices. Mathematische Annalen, 64 0 (2): 0 248--263, 1907. doi:10.1007/BF01449896. URL https://doi.org/10.1007/BF01449896

    1907 doi

  22. [30]

    and Li, N

    Qu, G. and Li, N. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 5 0 (3): 0 1245--1260, 2017

    2017

  23. [31]

    I., Xin, R., Kar, S., and Khan, U

    Qureshi, M. I., Xin, R., Kar, S., and Khan, U. A. S-addopt: Decentralized stochastic first-order optimization over directed graphs. IEEE Control Systems Letters, 5 0 (3): 0 953--958, 2020

    2020

  24. [32]

    Sayed, A. H. Adaptive networks. Proceedings of the IEEE, 102 0 (4): 0 460--497, 2014

    2014

  25. [33]

    T., and Massouli \'e , L

    Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massouli \'e , L. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference on machine learning, pp.\ 3027--3036. PMLR, 2017

    2017

  26. [34]

    Scaman, K., Bach, F., Bubeck, S., Massouli \'e , L., and Lee, Y. T. Optimal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 2740--2749, 2018

    2018

  27. [35]

    and Hong, M

    Sun, H. and Hong, M. Distributed non-convex first-order optimization and information processing: Lower complexity bounds and rate optimal algorithms. IEEE Transactions on Signal processing, 67 0 (22): 0 5912--5928, 2019

    2019

  28. [36]

    I., Lawlor, S., and Rabbat, M

    Tsianos, K. I., Lawlor, S., and Rabbat, M. G. Push-sum distributed dual averaging for convex optimization. In 2012 ieee 51st ieee conference on decision and control (cdc), pp.\ 5453--5458. IEEE, 2012

    2012

  29. [37]

    and Khan, U

    Xi, C. and Khan, U. A. Dextra: A fast algorithm for optimization over directed graphs. IEEE Transactions on Automatic Control, 62 0 (10): 0 4980--4993, 2017

    2017

  30. [38]

    Xi, C., Xin, R., and Khan, U. A. Add-opt: Accelerated distributed directed optimization. IEEE Transactions on Automatic Control, 63 0 (5): 0 1329--1339, 2017

    2017

  31. [39]

    Xin, R., Jakoveti \'c , D., and Khan, U. A. Distributed nesterov gradient methods over arbitrary graphs. IEEE Signal Processing Letters, 26 0 (8): 0 1247--1251, 2019 a

    2019

  32. [40]

    K., Khan, U

    Xin, R., Sahu, A. K., Khan, U. A., and Kar, S. Distributed stochastic optimization with gradient tracking over strongly-connected networks. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp.\ 8353--8358. IEEE, 2019 b

    2019

  33. [41]

    Frost—fast row-stochastic optimization with uncoordinated step-sizes

    Xin, R., xi, C., and Khan, U. Frost—fast row-stochastic optimization with uncoordinated step-sizes. EURASIP Journal on Advances in Signal Processing, 2019, 01 2019 c . doi:10.1186/s13634-018-0596-y

    2019 doi

  34. [42]

    An improved convergence analysis for decentralized online stochastic non-convex optimization

    Xin, R., Khan, U., and Kar, S. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 69: 0 1842--1858, 01 2021. doi:10.1109/TSP.2021.3062553

    2021

  35. [43]

    C., and Xie, L

    Xu, J., Zhu, S., Soh, Y. C., and Xie, L. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. In IEEE Conference on Decision and Control (CDC), pp.\ 2055--2060, Osaka, Japan, 2015

    2015

  36. [44]

    Achieving linear speedup with partial worker participation in non-iid federated learning

    Yang, H., Fang, M., and Liu, J. Achieving linear speedup with partial worker participation in non-iid federated learning. Proceedings of ICLR, 2021

    2021

  37. [45]

    Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., and Johansson, K. H. A survey of distributed optimization. Annual Reviews in Control, 47: 0 278--305, 2019

    2019

  38. [46]

    Yemini, M., Saha, R., Ozfatura, E., G \"u nd \"u z, D., and Goldsmith, A. J. Robust federated learning with connectivity failures: A semi-decentralized framework with collaborative relaying. arXiv preprint arXiv:2202.11850, 2022

    2022 arXiv

  39. [47]

    Exponential graph is provably efficient for decentralized deep training

    Ying, B., Yuan, K., Chen, Y., Hu, H., Pan, P., and Yin, W. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34: 0 13975--13987, 2021

    2021

  40. [48]

    On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization

    Yu, H., Jin, R., and Yang, S. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pp.\ 7184--7193. PMLR, 2019

    2019

  41. [49]

    Decentlam: Decentralized momentum sgd for large-batch deep training

    Yuan, K., Chen, Y., Huang, X., Zhang, Y., Pan, P., Xu, Y., and Yin, W. Decentlam: Decentralized momentum sgd for large-batch deep training. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp.\ 3029--3039, 2021

    2021

  42. [50]

    Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization

    Yuan, K., Huang, X., Chen, Y., Zhang, X., Zhang, Y., and Pan, P. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. Advances in Neural Information Processing Systems, 35: 0 36382--36395, 2022

    2022

  43. [51]

    and Yin, W

    Zeng, J. and Yin, W. Extrapush for convex smooth decentralized optimization over directed networks. Journal of Computational Mathematics, pp.\ 383--396, 2017

    2017

  44. [52]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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