Explicit Convergence Rate of a Distributed Alternating Direction Method of Multipliers

2013/12/04 by Iutzeler, Franck, Bianchi, Pascal, Ciblat, Philippe +1 · 1 citation
#Distributed #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1312.1085

Abstract

Consider a set of N agents seeking to solve distributively the minimization problem inf_x ∑_{n = 1}^N f_n(x) where the convex functions f_n are local to the agents. The popular Alternating Direction Method of Multipliers has the potential to handle distributed optimization problems of this kind. We provide a general reformulation of the problem and obtain a class of distributed algorithms which encompass various network architectures. The rate of convergence of our method is considered. It is assumed that the infimum of the problem is reached at a point x_⋆, the functions f_n are twice differentiable at this point and ∑ ∇² f_n(x_⋆) > 0 in the positive definite ordering of symmetric matrices. With these assumptions, it is shown that the convergence to the consensus x_⋆ is linear and the exact rate is provided. Application examples where this rate can be optimized with respect to the ADMM free parameter ρ are also given.

Cited by

• Decentralized Federated Learning with Distributed Aggregation Weight Optimization

Related

• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• Convergence Rate of Distributed ADMM over Networks
• Improving Rate of Convergence via Gain Adaptation in Multi-Agent Distributed ADMM Framework
• Asynchronous Distributed Optimization using a Randomized Alternating Direction Method of Multipliers
• DN-ADMM: Distributed Newton ADMM for Multi-agent Optimization