Convergence Rate of Distributed ADMM over Networks

Understand

We propose a distributed algorithm based on Alternating Direction Method of Multipliers (ADMM) to minimize the sum of locally known convex functions using communication over a network.

• This optimization problem emerges in many applications in distributed machine learning and statistical estimation.
• We show that when functions are convex, both the objective function values and the feasibility violation converge with rate $O(\frac{1}{T})$, where $T$ is the number of iterations.
• We then show that if the functions are strongly convex and have Lipschitz continuous gradients, the sequence generated by our algorithm converges linearly to the optimal solution.