Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
Abstract
We consider decentralized stochastic nonconvex optimization over directed networks. Push--Pull provides an efficient decentralized optimization framework for such networks, but in the stochastic setting, gradient variance can slow its convergence and complicate the analysis of linear speedup. Motivated by this observation, we incorporate recursive momentum into stochastic Push--Pull for variance reduction, yielding the accelerated stochastic Push--Pull (ASPP) algorithm. Under mean-squared smoothness, we prove that ASPP improves the convergence rate of stochastic Push--Pull and achieves asymptotic linear speedup with respect to the number of agents. To further reduce communication, we develop LASPP, a local-update variant of ASPP that allows each agent to perform multiple local updates between communication rounds. We show that LASPP achieves an additional asymptotic linear speedup with respect to the number of local steps. With a suitable number of local steps, LASPP reduces communication complexity while maintaining the same stochastic gradient complexity as ASPP. Numerical experiments on real datasets demonstrate the effectiveness of the proposed algorithms.
Related
- Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks
- Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
BibTeX
@misc{dong2026accelerated,
title = {{Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization}},
author = {Sheng Dong and Weiguo Xia and Huijie Tao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35275},
eprint = {2610.35275},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35275},
}
RIS
TY - UNPB
TI - Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
AU - Sheng Dong
AU - Weiguo Xia
AU - Huijie Tao
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35275
UR - https://arxiv.org/abs/2610.35275
AB - We consider decentralized stochastic nonconvex optimization over directed networks. Push--Pull provides an efficient decentralized optimization framework for such networks, but in the stochastic setting, gradient variance can slow its convergence and complicate the analysis of linear speedup. Motivated by this observation, we incorporate recursive momentum into stochastic Push--Pull for variance reduction, yielding the accelerated stochastic Push--Pull (ASPP) algorithm. Under mean-squared smoothness, we prove that ASPP improves the convergence rate of stochastic Push--Pull and achieves asymptotic linear speedup with respect to the number of agents. To further reduce communication, we develop LASPP, a local-update variant of ASPP that allows each agent to perform multiple local updates between communication rounds. We show that LASPP achieves an additional asymptotic linear speedup with respect to the number of local steps. With a suitable number of local steps, LASPP reduces communication complexity while maintaining the same stochastic gradient complexity as ASPP. Numerical experiments on real datasets demonstrate the effectiveness of the proposed algorithms.
ER -