Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs

Abstract

We consider the decentralized optimization problem, where a network of $n$ agents aims to collaboratively minimize the average of their individual smooth and convex objective functions through peer-to-peer communication in a directed graph. To tackle this problem, we propose two accelerated gradient tracking methods, namely APD and APD-SC, for non-strongly convex and strongly convex objective functions, respectively. We show that APD and APD-SC converge at the rates $O\left(\frac{1}{k^2}\right)$ and $O\left({\left(1-C\sqrt{\frac{\mu }{L}}\right)}^k\right)$, respectively, up to constant factors depending only on the mixing matrix. APD and APD-SC are the first decentralized methods over unbalanced directed graphs that achieve the same provable acceleration as centralized methods. Numerical experiments demonstrate the effectiveness of both methods.

arXiv commentSIAM Journal on Optimization, in press

References in corpus (8)

• Convex Optimization for Big Data
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Distributed Recursive Least-Squares: Stability and Performance Analysis
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization

Cited by in corpus (2)

• Recent theoretical advances in decentralized distributed convex optimization
• Optimal Gradient Tracking for Decentralized Optimization