Fast-converging decentralized alternating direction method of multipliers for consensus optimization

Abstract For its well-established convergence properties, simplicity, and applicability to various optimization problems, the alternating direction method of multipliers (ADMM) has been at the center of several research fields. When applied to problems such as consensus optimization in distributed systems, ADMM is often implemented in a centralized manner, which may be challenging due to its dependency on the location and capacity of the node. While decentralized implementations have been proposed, these schemes require all worker nodes to either replicate the synchronization work of all nodes or execute their tasks in sequence, making them computationally and communication-wise expensive or slow. To tackle these challenges, we introduce two novel decentralized ADMM algorithms to enable decentralized learning without incurring redundant computations, excessive message transmissions, or extended convergence time. Through theoretical analysis, we have shown that our algorithms inherit the well-established convergence properties of the classical centralized ADMM while keeping the computational and communication complexity for each node at $${\mathcal {O}}(1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Moreover, we have identified specific conditions under which each of our algorithms is guaranteed to converge faster than the other as well as the classical centralized ADMM. Across several numerical simulations with various settings, our algorithms have converged several times faster than several state-of-the-art decentralized ADMM implementations.