On arbitrary compression for decentralized consensus and stochastic optimization over directed networks

We study the decentralized consensus and stochastic optimization problems with compressed communications over static directed graphs. We propose an iterative gradient-based algorithm that compresses messages according to a desired compression ratio. The proposed method provably reduces the communica...

Full description

Saved in:
Bibliographic Details
Published in:European journal of control 2022-11, Vol.68, p.100682, Article 100682
Main Authors: Toghani, Mohammad Taha, Uribe, César A.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Communication
Compression ratio
Convergence
Convex optimization
Decentralized consensus
Decentralized optimization
Distributed algorithms
Gradient-push
Graph theory
Iterative methods
Messages
Non-convex optimization
Optimization
Push-sum
Random variables
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:We study the decentralized consensus and stochastic optimization problems with compressed communications over static directed graphs. We propose an iterative gradient-based algorithm that compresses messages according to a desired compression ratio. The proposed method provably reduces the communication overhead on the network at every communication round. Contrary to existing literature, we allow for arbitrary compression ratios in the communicated messages. We show a linear convergence rate for the proposed method on the consensus problem. Moreover, we provide explicit convergence rates for decentralized stochastic optimization problems on smooth functions that are either (i) strongly convex, (ii) convex, or (iii) non-convex. Finally, we provide numerical experiments to illustrate convergence under arbitrary compression ratios and the communication efficiency of our algorithm.
ISSN:0947-3580
1435-5671
DOI:10.1016/j.ejcon.2022.100682