Stochastic Proximal Gradient Consensus Over Random Networks

DOI10.1109/TSP.2017.2673815MaRDI QIDQ4620831zbMATH OpenOpenAlexFDO

Authors Mingyi Hong, Tsung-Hui Chang

Publication date 8 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08905

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider solving a convex, possibly stochastic optimization problem over a randomly time-varying multi-agent network. Each agent has access to some local objective function, and it only has unbiased estimates of the gradients of the smooth component. We develop a dynamic stochastic proximal-gradient consensus (DySPGC) algorithm, with the following key features: i) it works for both the static and certain randomly time-varying networks, ii) it allows the agents to utilize either the exact or stochastic gradient information, iii) it is convergent with provable rate. In particular, we show that the proposed algorithm converges to a global optimal solution, with a rate of $mathcalO(1/r)$ [resp. $mathcalO(1/sqrtr)$] when the exact (resp. stochastic) gradient is available, where r is the iteration counter. Interestingly, the developed algorithm bridges a number of (seemingly unrelated) distributed optimization algorithms, such as the EXTRA (Shi et al. 2014), the PG-EXTRA (Shi et al. 2015), the IC/IDC-ADMM (Chang et al. 2014), and the DLM (Ling et al. 2015) and the classical distributed subgradient method. Identifying such relationship allows for significant generalization of these methods. We also discuss one such generalization which accelerates the DySPGC (hence accelerating EXTRA, PG-EXTRA, IC-ADMM).

Cited in

(10)

• On the linear convergence of two decentralized algorithms
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• Distributed composite optimization for multi-agent systems with asynchrony
• Communication-efficient algorithms for decentralized and stochastic optimization
• A randomized incremental primal-dual method for decentralized consensus optimization
• On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation
• Snake: A Stochastic Proximal Gradient Algorithm for Regularized Problems Over Large Graphs
• Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
• Golden ratio proximal gradient ADMM for distributed composite convex optimization
• Decentralized stochastic subgradient projection optimization algorithms over random networks

This page was built for publication: Stochastic Proximal Gradient Consensus Over Random Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620831)