A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization

Abstract

In this work, we introduce ADAPD, $\text{A}$ $\text{D}$ecentr$\text{A}$lized $\text{P}$rimal-$\text{D}$ual algorithmic framework for solving non-convex and smooth consensus optimization problems over a network of distributed agents. The proposed framework relies on a novel problem formulation that elicits ADMM-type updates, where each agent first inexactly solves a local strongly convex subproblem with any method of its choice and then performs a neighbor communication to update a set of dual variables. We present two variants that allow for a single gradient step for the primal updates or multiple communications for the dual updates, to exploit the tradeoff between the per-iteration cost and the number of iterations. When multiple communications are performed, ADAPD can achieve theoretically optimal communication complexity results for non-convex and smooth consensus problems. Numerical experiments on several applications, including a deep-learning one, demonstrate the superiority of ADAPD over several popularly used decentralized methods.

arXiv commentIEEE TSP

References in corpus (9)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• Accelerated Distributed Nesterov Gradient Descent
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I