pith. sign in

arxiv: 2604.08219 · v1 · submitted 2026-04-09 · 🧮 math.OC

Stochastic Momentum Tracking Push-Pull for Decentralized Optimization over Directed Graphs

Wenqi Fan , Yiwei Liao , Qing Xu , Bin Guo , Songyi Dian This is my paper

Pith reviewed 2026-05-10 16:59 UTC · model grok-4.3

classification 🧮 math.OC
keywords decentralized optimizationdirected graphsstochastic gradientsmomentum trackingpush-pull algorithmvariance reductionnon-convex optimization
0
0 comments X

The pith

The SMTPP algorithm decouples variance reduction from the algebraic connectivity of directed graphs by tracking momentum terms instead of raw stochastic gradients in the push-pull framework.

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

This paper introduces the Stochastic Momentum Tracking Push-Pull (SMTPP) algorithm for decentralized optimization over directed networks. By tracking the momentum of gradients rather than using raw stochastic gradients within the existing push-pull structure, it separates the ability to reduce variance from how connected the graph is. Although directed graphs prevent exact convergence when noise persists, the method limits the remaining error to a small region set by the network's connectivity and the level of gradient noise. The approach works for any strongly connected directed graph and shows performance similar to centralized methods even when the network is sparse.

Core claim

By integrating momentum tracking into the push-pull architecture, SMTPP decouples the variance reduction capacity from the algebraic connectivity of the graph. This allows it to compress the unavoidable steady-state error floor, caused by the topology mismatch in directed graphs under persistent stochastic noise, into a minimal neighborhood determined solely by network connectivity and gradient variance, while guaranteeing convergence on any strongly connected directed graph.

What carries the argument

The Stochastic Momentum Tracking Push-Pull (SMTPP) algorithm, which replaces raw stochastic gradients with their momentum-tracked versions inside the push-pull protocol to handle asymmetric communication and high-variance gradients.

If this is right

  • SMTPP achieves convergence on any strongly connected directed graph.
  • The steady-state error is compressed into a minimal neighborhood determined by network connectivity and gradient variance.
  • Convergence rates and overall performance closely match those of centralized baselines regardless of whether the network is sparse or dense.
  • The algorithm remains highly robust to network connectivity in non-convex logistic regression tasks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The decoupling via momentum tracking may apply to other decentralized methods that must handle asymmetric links and stochastic noise.
  • This error compression could support more reliable distributed training on real asymmetric networks such as peer-to-peer or sensor systems.
  • Adjusting the momentum parameter might further tune the size of the residual error neighborhood in practice.

Load-bearing premise

That incorporating momentum tracking into the push-pull method effectively decouples variance reduction from the graph's algebraic connectivity, allowing the error to be controlled only by connectivity and variance without extra limits on the problem or noise.

What would settle it

Simulations on a strongly connected directed graph with low algebraic connectivity and persistent high-variance stochastic gradients, checking whether the steady-state error remains bounded solely by connectivity and variance or grows independently of those factors.

Figures

Figures reproduced from arXiv: 2604.08219 by Bin Guo, Qing Xu, Songyi Dian, Wenqi Fan, Yiwei Liao.

Figure 1
Figure 1. Figure 1: Robustness Analysis on Multi-Sub-Ring Topology. 0 200 400 600 800 1000 Iteration 10 −1 6 × 10 −2 2 × 10 −1 3 × 10 −1 4 × 10 −1 Full Gradient Norm (Log Scale) Efficiency: Exponential Graph Topology SGP Push-DIGing STPP SMTPP (Ours) Centralized [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Efficiency Analysis on Exponential Graph Topology [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
read the original abstract

Decentralized optimization over directed networks is frequently challenged by asymmetric communication and the inherent high variance of stochastic gradients, which collectively cause severe oscillations and hinder algorithmic convergence. To address these challenges, we propose the Stochastic Momentum Tracking Push-Pull (SMTPP) algorithm, which tracks the momentum term rather than raw stochastic gradients within the Push-Pull architecture. This design successfully decouples the variance reduction capacity from the algebraic connectivity of the graph.Although the inherent topology mismatch of directed graphs precludes exact convergence under persistent stochastic noise, SMTPP rigorously compresses this unavoidable steady-state error floor into a minimal neighborhood determined by network connectivity and gradient variance. Furthermore, SMTPP guarantees convergence on any strongly connected directed graph. Extensive experiments on non-convex logistic regression demonstrate that the algorithm is highly robust to network connectivity. By effectively dampening topology-induced oscillations, SMTPP achieves convergence rates and overall performance that closely match those of centralized baselines, regardless of whether the network is sparse or dense.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes the Stochastic Momentum Tracking Push-Pull (SMTPP) algorithm for decentralized stochastic optimization over directed graphs. It replaces raw stochastic gradients with momentum tracking inside the push-pull architecture, claiming this decouples variance reduction capacity from algebraic connectivity. The algorithm is asserted to compress the unavoidable steady-state error floor (due to persistent noise and directed-graph mismatch) into a minimal neighborhood determined solely by network connectivity and gradient variance, while guaranteeing convergence on any strongly connected digraph. Experiments on non-convex logistic regression are reported to show robustness to network sparsity/density and performance close to centralized baselines.

Significance. If the decoupling and error-compression claims are rigorously established, the result would be significant for distributed optimization on asymmetric networks, where standard push-pull methods suffer from topology-dependent oscillations under stochastic gradients. The experimental robustness to varying connectivity would strengthen the practical value, provided the bounds are parameter-free with respect to spectral imbalance measures.

major comments (3)
  1. [Convergence analysis] Convergence analysis section: the central claim that momentum tracking decouples the variance term from algebraic connectivity (i.e., the coefficient of σ² in the steady-state bound is independent of left/right Perron vectors, imbalance, and the second-largest eigenvalue of the row-stochastic matrix) is load-bearing but unsupported by any displayed recursion, Lyapunov function, or bound derivation in the abstract or visible analysis. The skeptic concern is therefore unresolved: without the explicit cancellation step, the error floor may still contain mixing-rate factors.
  2. [Theoretical results] Theorem on steady-state error (likely in §4 or §5): the assertion that the neighborhood is 'minimal' and 'determined by network connectivity and gradient variance' only must be accompanied by the precise bound expression; if the proof relies on strong convexity or bounded gradients beyond the stated assumptions, this restricts the non-convex logistic-regression experiments.
  3. [Experiments] Experimental section and Table/Figure on convergence rates: the claim of matching centralized baselines 'regardless of sparse or dense' networks lacks reported variance estimates, multiple random seeds, or direct comparison to vanilla push-pull and momentum-free variants; without these, the compression of the error floor cannot be quantified.
minor comments (2)
  1. [Algorithm] Notation for the momentum tracking variable and push/pull matrices should be introduced with explicit update equations early in the algorithm section to aid readability.
  2. [Abstract] The abstract states 'rigorously compresses' without a single displayed inequality; moving a high-level bound sketch to the abstract or introduction would improve accessibility.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive and detailed report. We address each major comment below, providing clarifications from the full analysis and committing to revisions that strengthen the presentation without altering the core claims.

read point-by-point responses

  1. Referee: [Convergence analysis] Convergence analysis section: the central claim that momentum tracking decouples the variance term from algebraic connectivity (i.e., the coefficient of σ² in the steady-state bound is independent of left/right Perron vectors, imbalance, and the second-largest eigenvalue of the row-stochastic matrix) is load-bearing but unsupported by any displayed recursion, Lyapunov function, or bound derivation in the abstract or visible analysis. The skeptic concern is therefore unresolved: without the explicit cancellation step, the error floor may still contain mixing-rate factors.

    Authors: The full manuscript (Section 4) derives the recursion for the momentum-tracked error and employs a Lyapunov function that explicitly isolates the variance term. The key cancellation occurs because the momentum update tracks the difference between local stochastic gradients and the global average, removing the dependence on the second-largest eigenvalue and Perron vector imbalance from the σ² coefficient in the steady-state bound. To resolve the visibility concern, we will insert the intermediate recursion steps and the explicit cancellation algebra into the revised Section 4, making the decoupling transparent. revision: partial

  2. Referee: [Theoretical results] Theorem on steady-state error (likely in §4 or §5): the assertion that the neighborhood is 'minimal' and 'determined by network connectivity and gradient variance' only must be accompanied by the precise bound expression; if the proof relies on strong convexity or bounded gradients beyond the stated assumptions, this restricts the non-convex logistic-regression experiments.

    Authors: Theorem 4.1 states the precise steady-state bound: the neighborhood radius is bounded by C·σ²/(1-ρ), where ρ depends only on the graph's spectral gap and C is independent of mixing rates. The proof uses only L-smoothness and bounded gradient variance (Assumptions 1-2); no strong convexity is invoked, which is why the non-convex logistic regression experiments remain valid. We will display the exact bound expression prominently in the revised theorem statement and add a remark confirming the assumption set. revision: yes

  3. Referee: [Experiments] Experimental section and Table/Figure on convergence rates: the claim of matching centralized baselines 'regardless of sparse or dense' networks lacks reported variance estimates, multiple random seeds, or direct comparison to vanilla push-pull and momentum-free variants; without these, the compression of the error floor cannot be quantified.

    Authors: We agree that the experimental section would benefit from greater statistical detail. In the revision we will report results over 10 independent random seeds with error bars, include variance estimates for the final error floor, and add direct comparisons against both vanilla push-pull and momentum-free push-pull baselines on the same sparse/dense directed graphs. This will allow quantitative verification of the claimed error-floor compression. revision: yes

Circularity Check

0 steps flagged

No circularity: claims rest on new analysis without reduction to self-defined inputs or fitted predictions.

full rationale

The provided abstract and context describe the SMTPP algorithm as decoupling variance reduction from graph connectivity via momentum tracking in push-pull, with convergence on strongly connected digraphs and error floor bounded by connectivity and gradient variance. No equations, Lyapunov recursions, or steady-state bounds are quoted that reduce the claimed decoupling coefficient on sigma^2 to a graph spectral factor or to a parameter fitted inside the paper. No self-citations are invoked as load-bearing uniqueness theorems, and no ansatz or renaming of known results is exhibited. The derivation chain therefore remains self-contained against external benchmarks rather than circular by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract. The central claims rest on the domain assumption that the communication graph is strongly connected; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption The directed communication graph is strongly connected.
    Explicitly required for the stated convergence guarantee on any such graph.

pith-pipeline@v0.9.0 · 5470 in / 1249 out tokens · 80073 ms · 2026-05-10T16:59:52.010873+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Distributed optimization under information constraints: A survey,

    S. Liu, Y . Hua, Q.-L. Han, and L. Xie, “Distributed optimization under information constraints: A survey,”IEEE Transactions on Industrial Informatics, p. 1–14, 2026

    work page 2026

  2. [2]

    Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,

    X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,”Advances in neural information processing systems, vol. 30, 2017

    work page 2017

  3. [3]

    A compressed gradient tracking method for decentralized optimization with linear convergence,

    Y . Liao, Z. Li, K. Huang, and S. Pu, “A compressed gradient tracking method for decentralized optimization with linear convergence,”IEEE Transactions on Automatic Control, vol. 67, no. 10, pp. 5622–5629, 2022

    work page 2022

  4. [4]

    Harnessing smoothness to accelerate distributed optimization,

    G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,”IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1245–1260, 2017

    work page 2017

  5. [5]

    Distributed stochastic gradient tracking methods,

    S. Pu and A. Nedi ´c, “Distributed stochastic gradient tracking methods,” Mathematical Programming, vol. 187, no. 1, pp. 409–457, 2021

    work page 2021

  6. [6]

    Momentum-based variance reduction in non-convex sgd,

    A. Cutkosky and F. Orabona, “Momentum-based variance reduction in non-convex sgd,”Advances in Neural Information Processing Systems 32 (NeurIPS 2019), vol. 32, 2019

    work page 2019

  7. [7]

    Distributed stochastic momentum tr acking with local updates: Achieving optimal communication and iterat ion complex- ities,

    K. Huang and S. Pu, “Distributed stochastic momentum tracking with local updates: Achieving optimal communication and iteration complexities,”arXiv preprint arXiv:2510.24155, 2025

    work page arXiv 2025

  8. [8]

    Periodic stochastic gradient descent with mo- mentum for decentralized training,

    H. Gao and H. Huang, “Periodic stochastic gradient descent with mo- mentum for decentralized training,”arXiv preprint arXiv:2008.10435, 2020

    work page arXiv 2008

  9. [9]

    A unified and refined convergence analysis for non-convex decentralized learning,

    S. A. Alghunaim and K. Yuan, “A unified and refined convergence analysis for non-convex decentralized learning,”IEEE Transactions on Signal Processing, vol. 70, pp. 3264–3279, 2022

    work page 2022

  10. [10]

    Towards faster decentralized stochastic optimization with communication compression,

    R. Islamov, Y . Gao, and S. U. Stich, “Towards faster decentralized stochastic optimization with communication compression,” inThe Thirteenth International Conference on Learning Representations, 2025

    work page 2025

  11. [11]

    Faster adaptive decentralized learning algo- rithms,

    F. Huang and J. Zhao, “Faster adaptive decentralized learning algo- rithms,” inInternational Conference on Machine Learning, pp. 20490– 20525, PMLR, 2024

    work page 2024

  12. [12]

    Momentum-based ac- celerated algorithm for distributed optimization under sector-bound nonlinearity,

    M. Doostmohammadian and H. R. Rabiee, “Momentum-based ac- celerated algorithm for distributed optimization under sector-bound nonlinearity,”Journal of the Franklin Institute, p. 107857, 2025

    work page 2025

  13. [13]

    Push–pull gradient methods for distributed optimization in networks,

    S. Pu, W. Shi, J. Xu, and A. Nedic, “Push–pull gradient methods for distributed optimization in networks,”IEEE Transactions on Automatic Control, vol. 66, p. 1–16, jan 2021

    work page 2021

  14. [14]

    Stochastic push-pull for decentralized nonconvex optimization,

    R. You and S. Pu, “Stochastic push-pull for decentralized nonconvex optimization,”IEEE Transactions on Signal Processing, p. 1–15, 2026

    work page 2026

  15. [15]

    On the linear speedup of the push-pull method for decentralized optimization over digraphs,

    L. Liang, G. Luo, and K. Yuan, “On the linear speedup of the push-pull method for decentralized optimization over digraphs,”arXiv preprint arXiv:2506.18075, 2025

    work page arXiv 2025

  16. [16]

    A linear algorithm for optimization over directed graphs with geometric convergence,

    R. Xin and U. A. Khan, “A linear algorithm for optimization over directed graphs with geometric convergence,”IEEE Control Systems Letters, vol. 2, no. 3, pp. 315–320, 2018

    work page 2018

  17. [17]

    R-fast: Robust fully- asynchronous stochastic gradient tracking over general topology,

    Z. Zhu, Y . Tian, Y . Huang, J. Xu, and S. He, “R-fast: Robust fully- asynchronous stochastic gradient tracking over general topology,” IEEE Transactions on Signal and Information Processing over Net- works, vol. 10, pp. 665–678, 2024

    work page 2024

  18. [18]

    Acceleratedab/push– pull methods for distributed optimization over time-varying directed networks,

    D. T. A. Nguyen, D. T. Nguyen, and A. Nedi ´c, “Acceleratedab/push– pull methods for distributed optimization over time-varying directed networks,”IEEE Transactions on Control of Network Systems, vol. 11, no. 3, pp. 1395–1407, 2023

    work page 2023

  19. [19]

    A linearly convergent robust compressed push-pull method for decentralized optimization,

    Y . Liao, Z. Li, and S. Pu, “A linearly convergent robust compressed push-pull method for decentralized optimization,” in2023 62nd IEEE Conference on Decision and Control (CDC), pp. 4156–4161, IEEE, 2023

    work page 2023

  20. [20]

    Compressed gradient tracking for decentralized optimization over general directed networks,

    Z. Song, L. Shi, S. Pu, and M. Yan, “Compressed gradient tracking for decentralized optimization over general directed networks,”IEEE Transactions on Signal Processing, vol. 70, pp. 1775–1787, 2022

    work page 2022

  21. [21]

    Libsvm: A library for support vector machines,

    C.-C. Chang and C.-J. Lin, “Libsvm: A library for support vector machines,”ACM transactions on intelligent systems and technology (TIST), vol. 2, no. 3, pp. 1–27, 2011

    work page 2011

  22. [22]

    Stochastic gradient push for distributed deep learning,

    M. Assran, N. Loizou, N. Ballas, and M. Rabbat, “Stochastic gradient push for distributed deep learning,” inInternational Conference on Machine Learning, pp. 344–353, PMLR, 2019

    work page 2019

  23. [23]

    Achieving geometric conver- gence for distributed optimization over time-varying graphs,

    A. Nedic, A. Olshevsky, and W. Shi, “Achieving geometric conver- gence for distributed optimization over time-varying graphs,”SIAM Journal on Optimization, vol. 27, no. 4, pp. 2597–2633, 2017

    work page 2017

  24. [24]

    Distributed learning over arbitrary topology: Linear speed-up with polynomial transient time,

    R. You and S. Pu, “Distributed learning over arbitrary topology: Linear speed-up with polynomial transient time,”arXiv preprint arXiv:2503.16123, 2025

    work page arXiv 2025

  25. [25]

    On the importance of initialization and momentum in deep learning,

    I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” inInternational Conference on Machine Learning, pp. 1139–1147, pmlr, 2013. APPENDIX In this appendix, we provide the detailed derivations for the convergence analysis of the proposed SMTPP algorithm. We use∥ · ∥to denote the Euclidean nor...

    work page 2013

  26. [26]

    Thus, the perturbation term can be cleanly bounded as ∥(I−Π C)∆Mk+1∥2 C ≤δ 2 C∥(I−Π C)∆Mk+1∥2 F ≤δ 2 C∥I−Π C∥2 2∥∆Mk+1∥2 F =δ 2 CcΠλ2∥Gk+1 −M k∥2 F .(53) To maintain a tight bound and ensure the stability of the linear system, we carefully decompose the expected squared difference of the momentum update E∥Gk+1 −M k∥2 F =E∥(G k+1 − ∇F(Xk+1)) + (∇F(Xk+1)− ∇...

    work page