(Corrected Version) Push-LSVRG-UP: Distributed Stochastic Optimization over Unbalanced Directed Networks with Uncoordinated Triggered Probabilities

Abstract

Distributed stochastic optimization, arising in the crossing and integration of traditional stochastic optimization, distributed computing and storage, and network science, has advantages of high efficiency and a low per-iteration computational complexity in resolving large-scale optimization problems. This paper concentrates on resolving a large-scale convex finite-sum optimization problem in a multi-agent system over unbalanced directed networks. To tackle this problem in an efficient way, a distributed consensus optimization algorithm, adopting the push-sum technique and a distributed loopless stochastic variance-reduced gradient (LSVRG) method with uncoordinated triggered probabilities, is developed and named Push-LSVRG-UP. Each agent under this algorithmic framework performs only local computation and communicates only with its neighbors without leaking their private information. The convergence analysis of Push-LSVRG-UP is relied on analyzing the contraction relationships between four error terms associated with the multi-agent system. Theoretical results provide an explicit feasible range of the constant step-size, a linear convergence rate, and an iteration complexity of Push-LSVRG-UP when achieving the globally optimal solution. It is shown that Push-LSVRG-UP achieves the superior characteristics of accelerated linear convergence, fewer storage costs, and a lower per-iteration computational complexity than most existing works. Meanwhile, the introduction of an uncoordinated probabilistic triggered mechanism allows Push-LSVRG-UP to facilitate the independence and flexibility of agents in computing local batch gradients. In simulations, the practicability and improved performance of Push-LSVRG-UP are manifested via resolving two distributed learning problems based on real-world datasets.

16 pages, 30 figures

References in corpus (9)

• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• ADD-OPT: Accelerated Distributed Directed Optimization
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Multi-consensus Decentralized Accelerated Gradient Descent
• The Barzilai-Borwein Method for Distributed Optimization over Unbalanced Directed Networks
• PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction

Cited by in corpus (2)

• ADMM-Tracking Gradient for Distributed Optimization over Asynchronous and Unreliable Networks
• Distributed Online Private Learning of Convex Nondecomposable Objectives