Communication-Efficient Variance-Reduced Decentralized Stochastic Optimization Over Time-Varying Directed Graphs

In this article, we consider the problem of decentralized optimization over time-varying directed networks. The network nodes can access only their local objectives, and aim to collaboratively minimize a global function by exchanging messages with their neighbors. Leveraging sparsification, gradient...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2022-12, Vol.67 (12), p.6583-6594
Main Authors: Chen, Yiyue, Hashemi, Abolfazl, Vikalo, Haris
Format: Article
Language:English
Subjects:
Convergence
Convex functions
Convex optimization
decentralized optimization
Directed graphs
Graph theory
Linear programming
Networks
Optimization
Signal processing algorithms
stochastic optimization
Stochastic processes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article, we consider the problem of decentralized optimization over time-varying directed networks. The network nodes can access only their local objectives, and aim to collaboratively minimize a global function by exchanging messages with their neighbors. Leveraging sparsification, gradient tracking, and variance reduction, we propose a novel communication-efficient decentralized optimization scheme that is suitable for resource-constrained time-varying directed networks. We prove that in the case of smooth and strongly convex objective functions, the proposed scheme achieves an accelerated linear convergence rate. To our knowledge, this is the first decentralized optimization framework for time-varying directed networks that achieves such a convergence rate and applies to settings requiring sparsified communication. Experimental results on both synthetic and real datasets verify the theoretical results and demonstrate the efficacy of the proposed scheme.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2021.3133372