SCIENCE@home

Convergence Rate of Distributed ADMM Over Networks

A. Makhdoumi,A. Ozdaglar

Published 2016 in IEEE Transactions on Automatic Control

ABSTRACT

We propose a new distributed algorithm based on alternating direction method of multipliers (ADMM) to minimize 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. Our algorithm allows for a general choice of the communication weight matrix, which is used to combine the iterates at different nodes. We show that when functions are convex, both the objective function values and the feasibility violation converge with rate <inline-formula> <tex-math notation="LaTeX">$O(1/T)$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$T$ </tex-math></inline-formula> is the number of iterations. We then show that when functions are strongly convex and have Lipschitz continuous gradients, the sequence generated by our algorithm converges linearly to the optimal solution. In particular, an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-optimal solution can be computed with <inline-formula><tex-math notation="LaTeX">$O\left(\sqrt{\kappa _f} \log (1/\epsilon) \right)$ </tex-math></inline-formula> iterations, where <inline-formula><tex-math notation="LaTeX">$\kappa _f$</tex-math> </inline-formula> is the condition number of the problem. Our analysis highlights the effect of network and communication weights on the convergence rate through degrees of the nodes, the smallest nonzero eigenvalue, and operator norm of the communication matrix.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-84 of 84 references · Page 1 of 1

CITED BY

Showing 1-100 of 211 citing papers · Page 1 of 3

123
Next