PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction
arXiv:2012.15010
Abstract
This paper considers the decentralized composite optimization problem. We propose a novel decentralized variance-reduction proximal-gradient algorithmic framework, called PMGT-VR, which is based on a combination of several techniques including multi-consensus, gradient tracking, and variance reduction. The proposed framework relies on an imitation of centralized algorithms and we demonstrate that algorithms under this framework achieve convergence rates similar to that of their centralized counterparts. We also describe and analyze two representative algorithms, PMGT-SAGA and PMGT-LSVRG, and compare them to existing state-of-the-art proximal algorithms. To the best of our knowledge, PMGT-VR is the first linearly convergent decentralized stochastic algorithm that can solve decentralized composite optimization problems. Numerical experiments are provided to demonstrate the effectiveness of the proposed algorithms.
arXiv comment16 pages, 4 figures
References in corpus (10)
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
- A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
- Multi-consensus Decentralized Accelerated Gradient Descent
- Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
- An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
- Revisiting EXTRA for Smooth Distributed Optimization
- Dual-Free Stochastic Decentralized Optimization with Variance Reduction