Convergence Rate of Distributed ADMM over Networks
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....
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121529 |
| _version_ | 1826212310326181888 |
|---|---|
| author | Makhdoumi Kakhaki, Ali Ozdaglar, Asuman E |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Makhdoumi Kakhaki, Ali Ozdaglar, Asuman E |
| author_sort | Makhdoumi Kakhaki, Ali |
| collection | MIT |
| description | 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 O(1/T), where $T$ 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 psilon-optimal solution can be computed with O(κ (1)) iterations, where κ 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. |
| first_indexed | 2024-09-23T15:19:42Z |
| format | Article |
| id | mit-1721.1/121529 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:19:42Z |
| publishDate | 2019 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1215292022-10-02T02:12:03Z Convergence Rate of Distributed ADMM over Networks Makhdoumi Kakhaki, Ali Ozdaglar, Asuman E Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 O(1/T), where $T$ 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 psilon-optimal solution can be computed with O(κ (1)) iterations, where κ 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. 2019-07-09T13:02:38Z 2019-07-09T13:02:38Z 2017-10 2019-06-28T16:04:29Z Article http://purl.org/eprint/type/JournalArticle 0018-9286 https://hdl.handle.net/1721.1/121529 Makhdoumi, Ali and Asuman Ozdaglar. "Convergence Rate of Distributed ADMM over Networks." IEEE Transactions on Automatic Control 62, no. 10 (October 2017): pages 5082 - 5095. en 10.1109/TAC.2017.2677879 IEEE Transactions on Automatic Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Makhdoumi Kakhaki, Ali Ozdaglar, Asuman E Convergence Rate of Distributed ADMM over Networks |
| title | Convergence Rate of Distributed ADMM over Networks |
| title_full | Convergence Rate of Distributed ADMM over Networks |
| title_fullStr | Convergence Rate of Distributed ADMM over Networks |
| title_full_unstemmed | Convergence Rate of Distributed ADMM over Networks |
| title_short | Convergence Rate of Distributed ADMM over Networks |
| title_sort | convergence rate of distributed admm over networks |
| url | https://hdl.handle.net/1721.1/121529 |
| work_keys_str_mv | AT makhdoumikakhakiali convergencerateofdistributedadmmovernetworks AT ozdaglarasumane convergencerateofdistributedadmmovernetworks |