{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:16Z","timestamp":1750220896254,"version":"3.41.0"},"reference-count":91,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001321","name":"National Research Foundation","doi-asserted-by":"crossref","award":["AitF-1637598","CNS-1518941","CNS-1254169"],"award-info":[{"award-number":["AitF-1637598","CNS-1518941","CNS-1254169"]}],"id":[{"id":"10.13039\/501100001321","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>Classically, the design of multi-agent systems is approached using techniques from distributed optimization such as dual descent and consensus algorithms. Such algorithms depend on convergence to global consensus before any individual agent can determine its local action. This leads to challenges with respect to communication overhead and robustness, and improving algorithms with respect to these measures has been a focus of the community for decades.<\/jats:p>\n          <jats:p>This paper presents a new approach for multi-agent system design based on ideas from the emerging field of local computation algorithms. The framework we develop, LOcal Convex Optimization (LOCO), is the first local computation algorithm for convex optimization problems and can be applied in a wide-variety of settings. We demonstrate the generality of the framework via applications to Network Utility Maximization (NUM) and the distributed training of Support Vector Machines (SVMs), providing numerical results illustrating the improvement compared to classical distributed optimization approaches in each case.<\/jats:p>","DOI":"10.1145\/3366696","type":"journal-article","created":{"date-parts":[[2019,12,18]],"date-time":"2019-12-18T13:21:11Z","timestamp":1576675271000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Logarithmic Communication for Distributed Optimization in Multi-Agent Systems"],"prefix":"10.1145","volume":"3","author":[{"given":"Palma","family":"London","sequence":"first","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shai","family":"Vardi","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Dimitris Achlioptas Themis Gouleakis and Fotis Iliopoulos. 2018. Local Computation Algorithms for the Lov\u00e1 sz Local Lemma. CoRR Vol. abs\/1809.07910 (2018). http:\/\/arxiv.org\/abs\/1809.07910  Dimitris Achlioptas Themis Gouleakis and Fotis Iliopoulos. 2018. Local Computation Algorithms for the Lov\u00e1 sz Local Lemma. CoRR Vol. abs\/1809.07910 (2018). http:\/\/arxiv.org\/abs\/1809.07910"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124312"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.89"},{"volume-title":"GRASS: Trimming Stragglers in Approximation Analytics. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14)","year":"2014","author":"Ananthanarayanan Ganesh","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129302"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.24"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2807423"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386316"},{"key":"e_1_2_1_9_1","unstructured":"Dimitri P. Bertsekas. 1999. Nonlinear programming .Athena Scientific.  Dimitri P. Bertsekas. 1999. Nonlinear programming .Athena Scientific."},{"key":"e_1_2_1_10_1","unstructured":"Dimitri P. Bertsekas and John N. Tsitsiklis. 1989. Parallel and Distributed Computation: Numerical Methods .Prentice Hall.  Dimitri P. Bertsekas and John N. Tsitsiklis. 1989. Parallel and Distributed Computation: Numerical Methods .Prentice Hall."},{"volume-title":"Proc. of IEEE Conference on Decision and Control. 2996--3000","author":"Blondel Vincent D.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5461964"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_2_1_15_1","unstructured":"CAIDA. 2007. Vol. The CAIDA UCSD AS Relationship Dataset http:\/\/www.caida.org\/data\/as-relationships\/ (2007).  CAIDA. 2007. Vol. The CAIDA UCSD AS Relationship Dataset http:\/\/www.caida.org\/data\/as-relationships\/ (2007)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2016.2537271"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0808-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154503"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.887322"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/050626090"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00994018"},{"key":"e_1_2_1_22_1","unstructured":"George Dantzig. 2016. Linear programming and extensions .Princeton university press.  George Dantzig. 2016. Linear programming and extensions .Princeton university press."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.1.101"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Reza Eghbali and Maryam Fazel. 2016. Designing smoothing functions for improved worst-case competitive ratio in online optimization. In Neural Information Processing Systems. 3287--3295.  Reza Eghbali and Maryam Fazel. 2016. Designing smoothing functions for improved worst-case competitive ratio in online optimization. In Neural Information Processing Systems. 3287--3295.","DOI":"10.1109\/CDC.2016.7798549"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2014.2306495"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2011.2162831"},{"volume-title":"45th International Colloquium on Automata, Languages, and Programming, (ICALP). 50:1--50:14","year":"2018","author":"Feige Uriel","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859906"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2012.2210288"},{"key":"e_1_2_1_31_1","unstructured":"Tom Goldstein Gavin Taylor Kawika Barabin and Kent Sayre. 2016. Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction. In AISTATS. 1151--1158.  Tom Goldstein Gavin Taylor Kawika Barabin and Kent Sayre. 2016. Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction. In AISTATS. 1151--1158."},{"volume-title":"Proc. of the 25th Conf. on UIAI. 203--212","year":"2009","author":"Gonzalez Joseph E.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/984622.984624"},{"key":"e_1_2_1_34_1","volume-title":"Robotics and Automation, 2002. Proceedings. ICRA'02. IEEE International Conference on","volume":"3","author":"Guo Yi","year":"2002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587354"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2018.8619467"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Hugh Everett III. 1963. Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. Operations research Vol. 11 3 (1963) 399--417.  Hugh Everett III. 1963. Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. Operations research Vol. 11 3 (1963) 399--417.","DOI":"10.1287\/opre.11.3.399"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150429"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600523"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2018.8619625"},{"volume-title":"Federated Optimization: Distributed Optimization Beyond the Datacenter. ArXiv","year":"2015","author":"Konecn\u00fd Jakub","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0127-7"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2010.2045501"},{"key":"e_1_2_1_45_1","unstructured":"Leon S Lasdon. 1970. Optimization theory for large systems .Courier Corporation.  Leon S Lasdon. 1970. Optimization theory for large systems .Courier Corporation."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755615"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005345"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/PES.2011.6039082"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSEN.2012.2227704"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.811451"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/37.980245"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2018.2848718"},{"key":"e_1_2_1_53_1","first-page":"1356","article-title":"Convergence of limited communication gradient methods","volume":"63","author":"Magn\u00fasson Sindri","year":"2018","journal-title":"IEEE Journal of Selected Topics in Signal Processing"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_55"},{"key":"e_1_2_1_55_1","first-page":"1395","article-title":"Bandwidth sharing: objectives and algorithms","volume":"3","author":"Massouli\u00e9 Laurent","year":"1999","journal-title":"IEEE INFOCOM"},{"key":"e_1_2_1_56_1","unstructured":"Brendan McMahan and Daniel Ramage. Accessed: 2017-04--10. Federated learning: Collaborative machine learning without centralized training data. https:\/\/ research.googleblog.com\/ 2017\/ 04\/ federated-l earning-collaborative.html.  Brendan McMahan and Daniel Ramage. Accessed: 2017-04--10. Federated learning: Collaborative machine learning without centralized training data. https:\/\/ research.googleblog.com\/ 2017\/ 04\/ federated-l earning-collaborative.html."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/080743706"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2254478"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2007.4434693"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.2009515"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-008-9370-2"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2010.2041686"},{"volume-title":"Proceedings of the 24th International Conference on Neural Information Processing Systems (NIPS'11)","author":"Niu Feng","key":"e_1_2_1_63_1"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2007.4434303"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/507670.507695"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2007.910665"},{"volume-title":"Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS'16)","year":"2016","author":"Pan Xinghao","key":"e_1_2_1_67_1"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPSN.2005.1440895"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_70_1","unstructured":"Qiuyu Peng and Steven H. Low. 2016. Distributed optimal power flow algorithm for radial networks I: Balanced single phase case. IEEE Transactions on Smart Grid (2016).  Qiuyu Peng and Steven H. Low. 2016. Distributed optimal power flow algorithm for radial networks I: Balanced single phase case. IEEE Transactions on Smart Grid (2016)."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2004.1428778"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1756040"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.05.007"},{"key":"e_1_2_1_74_1","unstructured":"Ralph Tyrrell Rockafellar. 1984. Network Flows and Monotropic Optimization .John Wiley and Sons New York.  Ralph Tyrrell Rockafellar. 1984. Network Flows and Monotropic Optimization .John Wiley and Sons New York."},{"volume-title":"Proc. 2nd Sym. on Innov. in Computer Science (ICS). 223--238","year":"2011","author":"Rubinfeld Ronitt","key":"e_1_2_1_75_1"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1137\/080728561"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/SMARTGRID.2010.5622077"},{"volume-title":"Proc. of NIPS. 1273--1280","author":"Sanghavi Sujay","key":"e_1_2_1_78_1"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.906734"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.5555\/1966806.1966812"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2015.2461520"},{"key":"e_1_2_1_82_1","unstructured":"Naum Z. Shor. 2012. Minimization methods for non-differentiable functions. Vol. 3. Springer Science & Business Media.  Naum Z. Shor. 2012. Minimization methods for non-differentiable functions. Vol. 3. Springer Science & Business Media."},{"key":"e_1_2_1_83_1","unstructured":"Rayadurgam Srikant. 2012. The mathematics of Internet congestion control .Springer Science & Business Media.  Rayadurgam Srikant. 2012. The mathematics of Internet congestion control .Springer Science & Business Media."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-009-0179-5"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979628292X"},{"key":"e_1_2_1_86_1","article-title":"Decentralized multi-agent optimization via dual decomposition","volume":"44","author":"Terelius H\u00e5kan","year":"2011","journal-title":"IEEE Trans. Automat. Control"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1986.1104412"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2253218"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.1285"},{"volume":"32","volume-title":"Proceedings of the 31st International Conference on International Conference on Machine Learning -","author":"Zhang Ruiliang","key":"e_1_2_1_91_1"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366696","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:38Z","timestamp":1750203878000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,17]]},"references-count":91,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,12,17]]}},"alternative-id":["10.1145\/3366696"],"URL":"https:\/\/doi.org\/10.1145\/3366696","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,12,17]]},"assertion":[{"value":"2019-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}