On the Linear Convergence of the ADMM in Decentralized Consensus Optimization

Abstract

In decentralized consensus optimization, a connected network of agents collaboratively minimize the sum of their local objective functions over a common decision variable, where their information exchange is restricted between the neighbors. To this end, one can first obtain a problem reformulation and then apply the alternating direction method of multipliers (ADMM). The method applies iterative computation at the individual agents and information exchange between the neighbors. This approach has been observed to converge quickly and deemed powerful. This paper establishes its linear convergence rate for decentralized consensus optimization problem with strongly convex local objective functions. The theoretical convergence rate is explicitly given in terms of the network topology, the properties of local objective functions, and the algorithm parameter. This result is not only a performance guarantee but also a guideline toward accelerating the ADMM convergence.

11 figures, IEEE Transactions on Signal Processing, 2014

References in corpus (1)

• On the Linear Convergence of the Alternating Direction Method of Multipliers

Cited by in corpus (195)

• Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• DP-ADMM: ADMM-based Distributed Learning with Differential Privacy
• Accelerated Distributed Nesterov Gradient Descent
• ADD-OPT: Accelerated Distributed Directed Optimization
• D${}^2$: Decentralized Training over Decentralized Data
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Decentralized Quasi-Newton Methods
• Distributed Nash Equilibrium Seeking under Partial-Decision Information via the Alternating Direction Method of Multipliers
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Distributed Optimization for Smart Cyber-Physical Networks
• Asynchronous Distributed Optimization over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
• ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning
• Distributed Radio Interferometric Calibration
• Decentralized Collaborative Learning of Personalized Models over Networks
• FROST -- Fast row-stochastic optimization with uncoordinated step-sizes
• Distributed Discrete-time Optimization in Multi-agent Networks Using only Sign of Relative State
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
• ExtraPush for convex smooth decentralized optimization over directed networks
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Privacy-Preserving Distributed Optimization via Subspace Perturbation: A General Framework
• Privacy-preserving Distributed Machine Learning via Local Randomization and ADMM Perturbation
• Sl-EDGE: Network Slicing at the Edge
• Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms
• Supervised Learning Under Distributed Features
• Quantized Consensus ADMM for Multi-Agent Distributed Optimization
• A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
• Analysis of Distributed ADMM Algorithm for Consensus Optimization in Presence of Node Error
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• Quantized Consensus by the ADMM: Probabilistic versus Deterministic Quantizers
• DiNNO: Distributed Neural Network Optimization for Multi-Robot Collaborative Learning
• Decentralized Joint-Sparse Signal Recovery: A Sparse Bayesian Learning Approach
• A unitary distributed subgradient method for multi-agent optimization with different coupling sources
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• Distributed Optimal Power Flow for VSC-MTDC Meshed AC/DC Grids Using ALADIN
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• Confederated Learning: Federated Learning with Decentralized Edge Servers
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• An Asynchronous, Decentralized Solution Framework for the Large Scale Unit Commitment Problem
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Multi-consensus Decentralized Accelerated Gradient Descent
• DC-DistADMM: ADMM Algorithm for Constrained Distributed Optimization over Directed Graphs
• On the Linear Convergence of Distributed Optimization over Directed Graphs
• Learning Privately over Distributed Features: An ADMM Sharing Approach
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• A Fair and Privacy-Aware EV Discharging Strategy using Decentralized Whale Optimization Algorithm for Minimizing Cost of EVs and the EV Aggregator
• Network Newton-Part II: Convergence Rate and Implementation
• Network Newton-Part I: Algorithm and Convergence
• Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization
• Decentralized Sparse Multitask RLS over Networks
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
• How is Distributed ADMM Affected by Network Topology?
• A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
• RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets
• Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• Projected Gradient Method for Decentralized Optimization over Time-Varying Networks
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Personalized Graph Federated Learning with Differential Privacy
• Stochastic Proximal Gradient Consensus Over Random Networks
• Distributed Variational Bayesian Algorithms for Extended Object Tracking
• Distributed ADMM with Synergetic Communication and Computation
• Implicit Tracking-Based Distributed Constraint-Coupled Optimization
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Private Learning on Networks: Part II
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Convergence Rates Analysis of The Quadratic Penalty Method and Its Applications to Decentralized Distributed Optimization
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
• Fast and Robust Sparsity Learning over Networks: A Decentralized Surrogate Median Regression Approach
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• A two-level distributed algorithm for nonconvex constrained optimization
• On Nonconvex Decentralized Gradient Descent
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
• The Barzilai-Borwein Method for Distributed Optimization over Unbalanced Directed Networks
• Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks
• A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization
• Decentralized Consensus Optimization with Asynchrony and Delays
• Distributed Safe Control Design and Probabilistic Safety Verification for Multi-Agent Systems
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• Robust and Communication-Efficient Collaborative Learning
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
• Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• Automatic Performance Estimation for Decentralized Optimization
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication
• Linear Convergence of First- and Zeroth-Order Primal-Dual Algorithms for Distributed Nonconvex Optimization
• Privacy-preserving Decentralized Aggregation for Federated Learning
• Differentially Private ADMM for Convex Distributed Learning: Improved Accuracy via Multi-Step Approximation
• Decentralized Markov Chain Gradient Descent
• Asynchronous decentralized accelerated stochastic gradient descent
• Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking
• Inferring Parameters Through Inverse Multiobjective Optimization
• Optimized Transmission for Consensus in Wireless Sensor Networks
• Distributed Aggregative Optimization over Multi-Agent Networks
• COKE: Communication-Censored Decentralized Kernel Learning
• On the Distributed Optimization over Directed Networks
• Exponentially Convergent Algorithm Design for Constrained Distributed Optimization via Non-smooth Approach
• Differentially Private ADMM for Distributed Medical Machine Learning
• Asynchronous distributed collision avoidance with intention consensus for inland autonomous ships
• Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
• A Survey of Distributed Optimization Methods for Multi-Robot Systems
• Markov Chain Lifting and Distributed ADMM
• Fast Saddle-Point Algorithm for Generalized Dantzig Selector and FDR Control with the Ordered l1-Norm
• Decentralized Recommender Systems
• Consensus Multi-Agent Reinforcement Learning for Volt-VAR Control in Power Distribution Networks
• Hierarchical Continuous Time Hidden Markov Model, with Application in Zero-Inflated Accelerometer Data
• Fully Distributed Alternating Direction Method of Multipliers in Digraphs via Finite-Time Termination Mechanisms
• Distributed Subgradient Projection Algorithm over Directed Graphs
• NEXT: In-Network Nonconvex Optimization
• ADMM for Multiaffine Constrained Optimization
• A Generic online acceleration scheme for Optimization algorithms via Relaxation and Inertia
• Privacy Preservation in Distributed Subgradient Optimization Algorithms
• ADMM Based Privacy-preserving Decentralized Optimization
• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution
• A Simple Effective Heuristic for Embedded Mixed-Integer Quadratic Programming
• D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems
• Communication-Efficient Algorithms For Distributed Optimization
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Decentralized Riemannian Gradient Descent on the Stiefel Manifold
• Geometric Convergence for Distributed Optimization with Barzilai-Borwein Step Sizes
• Enabling Distributed Optimization in Large-Scale Power Systems
• Distributed Linear Model Clustering over Networks: A Tree-Based Fused-Lasso ADMM Approach
• Local Differential Privacy in Decentralized Optimization
• Privacy-Preserving Distributed Zeroth-Order Optimization
• Accelerating Gossip SGD with Periodic Global Averaging
• Dual Descent ALM and ADMM
• Essentially Decentralized Conjugate Gradients
• Alternating Stationary Iterative Methods Based on Double Splittings
• Linearly Convergent Asynchronous Distributed ADMM via Markov Sampling
• Linear convergence in optimization over directed graphs with row-stochastic matrices
• Tight Linear Convergence Rate of ADMM for Decentralized Optimization
• Distributed Convex Optimization With Coupling Constraints Over Time-Varying Directed Graphs
• Subgradient-Free Stochastic Optimization Algorithm for Non-smooth Convex Functions over Time-Varying Networks
• Toward Model Parallelism for Deep Neural Network based on Gradient-free ADMM Framework
• Multi-frequency calibration for DOA estimation with distributed sensors
• A general framework for decentralized optimization with first-order methods
• Distributed Spatial-Temporal Trajectory Optimization for Unmanned-Aerial-Vehicle Swarm
• Dual decomposition for multi-agent distributed optimization with coupling constraints
• Recycled ADMM: Improve Privacy and Accuracy with Less Computation in Distributed Algorithms
• Resource-aware Exact Decentralized Optimization Using Event-triggered Broadcasting
• A Bregman Splitting Algorithm for Distributed Optimization over Networks
• FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
• Bregman Parallel Direction Method of Multipliers for Distributed Optimization via Mirror Averaging
• Accelerated Consensus via Min-Sum Splitting
• Contraction Analysis on Primal-Dual Gradient Optimization
• Fast Decentralized Optimization over Networks
• Distributed Stochastic Model Predictive Control for Large-Scale Linear Systems with Private and Common Uncertainty Sources
• Distributed Robust Subspace Recovery
• Systematic Design of Decentralized Algorithms for Consensus Optimization
• On linear convergence of two decentralized algorithms
• Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling
• Communication-Efficient Projection-Free Algorithm for Distributed Optimization
• Stabilizing Deep Tomographic Reconstruction
• Tuning Over-Relaxed ADMM
• Distributed Stochastic Optimization With Unbounded Subgradients Over Randomly Time-Varying Networks
• Distributed Sparse Regression via Penalization
• A Distributed Parallel Optimization Algorithm via Alternating Direction Method of Multipliers
• From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning
• Large Language Model-Assisted Planning of Electric Vehicle Charging Infrastructure with Real-World Case Study
• Distributed Average Consensus with Bounded Quantizer and Unbounded Input
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT
• Decentralized Learning with Lazy and Approximate Dual Gradients
• A Newton Tracking Algorithm with Exact Linear Convergence Rate for Decentralized Consensus Optimization
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing
• A Distributed and Privacy-Aware Speed Advisory System for Optimising Conventional and Electric Vehicles Networks
• BFGS-ADMM for Large-Scale Distributed Optimization
• Online decentralized decision making with inequality constraints: an ADMM approach
• MPC-CSAS: Multi-Party Computation for Real-time Privacy-preserving Speed Advisory Systems
• Decentralized Optimization over Tree Graphs
• A Fast Proximal Gradient Algorithm for Decentralized Composite Optimization over Directed Networks
• A Distributed Methodology for Approximate Uniform Global Minimum Sharing
• Distributed Linearized ADMM for Network Cost Minimization
• A Stabilizing Control Algorithm for Asynchronous Parallel Quadratic Programming via Dual Decomposition
• Decentralized Consensus Optimization Based on Parallel Random Walk
• Gradient-push algorithm for distributed optimization with event-triggered communications
• Decentralized Composite Optimization in Stochastic Networks: A Dual Averaging Approach with Linear Convergence
• Distributed Prediction-Correction ADMM for Time-Varying Convex Optimization
• Distributed Dual Coordinate Ascent in General Tree Networks and Communication Network Effect on Synchronous Machine Learning
• Dynamic Sharing Through the ADMM
• Model Linkage Selection for Cooperative Learning
• Random Graph-Based Neuromorphic Learning with a Layer-Weaken Structure
• Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE
• RC Circuits based Distributed Conditional Gradient Method