Back to Search
Start Over
Push-SAGA: A Decentralized Stochastic Algorithm With Variance Reduction Over Directed Graphs
- Source :
- IEEE Control Systems Letters. 6:1202-1207
- Publication Year :
- 2022
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2022.
-
Abstract
- In this paper, we propose Push-SAGA, a decentralized stochastic first-order method for finite-sum minimization over a directed network of nodes. Push-SAGA combines node-level variance reduction to remove the uncertainty caused by stochastic gradients, network-level gradient tracking to address the distributed nature of the data, and push-sum consensus to tackle the challenge of directed communication links. We show that Push-SAGA achieves linear convergence to the exact solution for smooth and strongly convex problems and is thus the first linearly-convergent stochastic algorithm over arbitrary strongly connected directed graphs. We also characterize the regimes in which Push-SAGA achieves a linear speed-up compared to its centralized counterpart and achieves a network-independent convergence rate. We illustrate the behavior and convergence properties of Push-SAGA with the help of numerical experiments on strongly convex and non-convex problems.
- Subjects :
- FOS: Computer and information sciences
Computer Science - Machine Learning
Strongly connected component
Control and Optimization
Computer science
Machine Learning (stat.ML)
Systems and Control (eess.SY)
Directed graph
Electrical Engineering and Systems Science - Systems and Control
Machine Learning (cs.LG)
Exact solutions in general relativity
Computer Science - Distributed, Parallel, and Cluster Computing
Rate of convergence
Statistics - Machine Learning
Control and Systems Engineering
Convergence (routing)
FOS: Electrical engineering, electronic engineering, information engineering
Computer Science - Multiagent Systems
Variance reduction
Distributed, Parallel, and Cluster Computing (cs.DC)
Minification
Convex function
Algorithm
Multiagent Systems (cs.MA)
Subjects
Details
- ISSN :
- 24751456
- Volume :
- 6
- Database :
- OpenAIRE
- Journal :
- IEEE Control Systems Letters
- Accession number :
- edsair.doi.dedup.....00dc1ee96c0ac7690c149c861618d829