FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization

Abstract

In this paper, we study the problem of minimizing a sum of convex objective functions, which are locally available to agents in a network. Distributed optimization algorithms make it possible for the agents to cooperatively solve the problem through local computations and communications with neighbors. Lagrangian-based distributed optimization algorithms have received significant attention in recent years, due to their exact convergence property. However, many of these algorithms have slow convergence or are expensive to execute. In this paper, we develop a flexible framework of first-order primal-dual algorithms (FlexPD), which allows for multiple primal steps per iteration. This framework includes three algorithms, FlexPD-F, FlexPD-G, and FlexPD-C that can be used for various applications with different computation and communication limitations. For strongly convex and Lipschitz gradient objective functions, we establish linear convergence of our proposed framework to the optimal solution. Simulation results confirm the superior performance of our framework compared to the existing methods.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1903.12601

References in corpus (17)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Distributed Learning in Wireless Sensor Networks
• D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Decentralized Quasi-Newton Methods
• Communication-Efficient Distributed Dual Coordinate Ascent
• ExtraPush for convex smooth decentralized optimization over directed networks
• Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization
• Network Newton-Part I: Algorithm and Convergence
• Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates
• Superlinearly Convergent Asynchronous Distributed Network Newton Method
• Nested Distributed Gradient Methods with Adaptive Quantized Communication
• A Fast Distributed Asynchronous Newton-Based Optimization Algorithm