Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE
© 2019 American Automatic Control Council. We develop a distributed algorithm for convex Empirical Risk Minimization, the problem of minimizing large but finite sum of convex functions over networks. The proposed algorithm is derived from directly discretizing the second-order heavy-ball differentia...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148596 |
| _version_ | 1826201840787652608 |
|---|---|
| author | Zhang, J Uribe, CA Mokhtari, A Jadbabaie, A |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Zhang, J Uribe, CA Mokhtari, A Jadbabaie, A |
| author_sort | Zhang, J |
| collection | MIT |
| description | © 2019 American Automatic Control Council. We develop a distributed algorithm for convex Empirical Risk Minimization, the problem of minimizing large but finite sum of convex functions over networks. The proposed algorithm is derived from directly discretizing the second-order heavy-ball differential equation and results in an accelerated convergence rate, i.e., faster than distributed gradient descent-based methods for strongly convex objectives that may not be smooth. Notably, we achieve acceleration without resorting to the well-known Nesterov's momentum approach. We provide numerical experiments and contrast the proposed method with recently proposed optimal distributed optimization algorithms. |
| first_indexed | 2024-09-23T11:57:48Z |
| format | Article |
| id | mit-1721.1/148596 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:57:48Z |
| publishDate | 2023 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1485962023-03-18T03:28:38Z Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE Zhang, J Uribe, CA Mokhtari, A Jadbabaie, A Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society © 2019 American Automatic Control Council. We develop a distributed algorithm for convex Empirical Risk Minimization, the problem of minimizing large but finite sum of convex functions over networks. The proposed algorithm is derived from directly discretizing the second-order heavy-ball differential equation and results in an accelerated convergence rate, i.e., faster than distributed gradient descent-based methods for strongly convex objectives that may not be smooth. Notably, we achieve acceleration without resorting to the well-known Nesterov's momentum approach. We provide numerical experiments and contrast the proposed method with recently proposed optimal distributed optimization algorithms. 2023-03-17T16:05:25Z 2023-03-17T16:05:25Z 2019-07-01 2023-03-17T15:57:55Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/148596 Zhang, J, Uribe, CA, Mokhtari, A and Jadbabaie, A. 2019. "Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE." Proceedings of the American Control Conference, 2019-July. en 10.23919/acc.2019.8814686 Proceedings of the American Control Conference Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE MIT web domain |
| spellingShingle | Zhang, J Uribe, CA Mokhtari, A Jadbabaie, A Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE |
| title | Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE |
| title_full | Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE |
| title_fullStr | Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE |
| title_full_unstemmed | Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE |
| title_short | Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE |
| title_sort | achieving acceleration in distributed optimization via direct discretization of the heavy ball ode |
| url | https://hdl.handle.net/1721.1/148596 |
| work_keys_str_mv | AT zhangj achievingaccelerationindistributedoptimizationviadirectdiscretizationoftheheavyballode AT uribeca achievingaccelerationindistributedoptimizationviadirectdiscretizationoftheheavyballode AT mokhtaria achievingaccelerationindistributedoptimizationviadirectdiscretizationoftheheavyballode AT jadbabaiea achievingaccelerationindistributedoptimizationviadirectdiscretizationoftheheavyballode |