Communication-Censored Linearized ADMM for Decentralized Consensus Optimization

Abstract

In this paper, we propose a communication- and computation-efficient algorithm to solve a convex consensus optimization problem defined over a decentralized network. A remarkable existing algorithm to solve this problem is the alternating direction method of multipliers (ADMM), in which at every iteration every node updates its local variable through combining neighboring variables and solving an optimization subproblem. The proposed algorithm, called as COmmunication-censored Linearized ADMM (COLA), leverages a linearization technique to reduce the iteration-wise computation cost of ADMM and uses a communication-censoring strategy to alleviate the communication cost. To be specific, COLA introduces successive linearization approximations to the local cost functions such that the resultant computation is first-order and light-weight. Since the linearization technique slows down the convergence speed, COLA further adopts the communication-censoring strategy to avoid transmissions of less informative messages. A node is allowed to transmit only if the distance between the current local variable and its previously transmitted one is larger than a censoring threshold. COLA is proven to be convergent when the local cost functions have Lipschitz continuous gradients and the censoring threshold is summable. When the local cost functions are further strongly convex, we establish the linear (sublinear) convergence rate of COLA, given that the censoring threshold linearly (sublinearly) decays to 0. Numerical experiments corroborate with the theoretical findings and demonstrate the satisfactory communication-computation tradeoff of COLA.

References in corpus (15)

• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Harnessing Smoothness to Accelerate Distributed Optimization
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• A linear algorithm for optimization over directed graphs with geometric convergence
• Monitoring and Optimization for Power Grids: A Signal Processing Perspective
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Communication Compression for Decentralized Training
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Distributed Clustering and Learning Over Networks
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization

Cited by in corpus (5)

• COKE: Communication-Censored Decentralized Kernel Learning
• Resource-aware Exact Decentralized Optimization Using Event-triggered Broadcasting
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing
• FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data
• Communication-Censored Distributed Stochastic Gradient Descent