Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization

Abstract

We study stochastic decentralized optimization for the problem of training machine learning models with large-scale distributed data. We extend the widely used EXTRA and DIGing methods with variance reduction (VR), and propose two methods: VR-EXTRA and VR-DIGing. The proposed VR-EXTRA requires the time of $O(({\kappa }_s+n)\log \frac{1}{\epsilon })$ stochastic gradient evaluations and $O(({\kappa }_b+{\kappa }_c)\log \frac{1}{\epsilon })$ communication rounds to reach precision $\epsilon$, which are the best complexities among the non-accelerated gradient-type methods, where ${\kappa }_s$ and ${\kappa }_b$ are the stochastic condition number and batch condition number for strongly convex and smooth problems, respectively, ${\kappa }_c$ is the condition number of the communication network, and $n$ is the sample size on each distributed node. The proposed VR-DIGing has a little higher communication cost of $O(({\kappa }_b+{\kappa }_c^2)\log \frac{1}{\epsilon })$. Our stochastic gradient computation complexities are the same as the ones of single-machine VR methods, such as SAG, SAGA, and SVRG, and our communication complexities keep the same as those of EXTRA and DIGing, respectively. To further speed up the convergence, we also propose the accelerated VR-EXTRA and VR-DIGing with both the optimal $O((\sqrt{n{\kappa }_s}+n)\log \frac{1}{\epsilon })$ stochastic gradient computation complexity and $O(\sqrt{{\kappa }_b{\kappa }_c}\log \frac{1}{\epsilon })$ communication complexity. Our stochastic gradient computation complexity is also the same as the ones of single-machine accelerated VR methods, such as Katyusha, and our communication complexity keeps the same as those of accelerated full batch decentralized methods, such as MSDA.

References in corpus (7)

• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• 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
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• Dual-Free Stochastic Decentralized Optimization with Variance Reduction

Cited by in corpus (9)

• Recent theoretical advances in decentralized distributed convex optimization
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• ADMM-Tracking Gradient for Distributed Optimization over Asynchronous and Unreliable Networks
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
• A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction
• A fast randomized incremental gradient method for decentralized non-convex optimization
• An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints