{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T02:15:54Z","timestamp":1790648154010,"version":"4.1.0"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We develop and analyze an asynchronous algorithm for distributed convex optimization when the objective can be written as a sum of smooth functions, local to each worker, and a nonsmooth function. Unlike many existing methods, our distributed algorithm is adjustable to various levels of communication cost, delays, machines' computational power, and functions' smoothness. A unique feature is that the step sizes do not depend on communication delays nor number of machines, which is highly desirable for scalability. We prove that the algorithm converges linearly in the strongly convex case, and provide guarantees of convergence for the non-strongly convex case. The obtained rates are the same as the vanilla proximal gradient algorithm over some introduced epoch sequence that subsumes the delays of the system. We provide numerical results on large-scale machine learning problems to demonstrate the merits of the proposed method.<\/jats:p>","DOI":"10.1137\/18m1194699","type":"journal-article","created":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T16:32:55Z","timestamp":1584462775000},"page":"933-959","source":"Crossref","is-referenced-by-count":15,"title":["A Distributed Flexible Delay-Tolerant Proximal Gradient Algorithm"],"prefix":"10.1137","volume":"30","author":[{"given":"Konstantin","family":"Mishchenko","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franck","family":"Iutzeler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e9r\u00f4me","family":"Malick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,3,17]]},"reference":[{"key":"atypb1","unstructured":"A. Aytekin, H. R. Feyzmahdavian, and M. Johansson,\n                      Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server\n                      , preprint,https:\/\/arxiv.org\/abs\/1610.05507(2016)."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000015"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"H. H. Bauschke and P. L. Combettes,\n                      Convex Analysis and Monotone Operator Theory in Hilbert Spaces\n                      , Springer, New York, 2011.","DOI":"10.1007\/978-1-4419-9467-7"},{"key":"atypb4","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice Hall, Englewood Cliffs, NJ, 1989."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"atypb6","unstructured":"C. Calauz\u00e8nes and N. L. Roux,\n                      Distributed Saga: Maintaining Linear Convergence Rate with Limited Communication\n                      , preprint,https:\/\/arxiv.org\/abs\/1705.10405(2017)."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"atypb8","first-page":"1646","author":"Defazio A.","year":"2014","journal-title":"NY"},{"key":"atypb9","first-page":"1125","author":"Defazio A.","year":"2014","journal-title":"NY"},{"key":"atypb10","unstructured":"J. C. Duchi, S. Chaturapruek, and C. R\u00e9,\n                      Asynchronous Stochastic Convex Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1508.00882(2015)."},{"key":"atypb11","unstructured":"R. Hannah and W. Yin,\n                      More Iterations Per Second, Same Quality-Why Asynchronous Algorithms May Drastically Outperform Traditional Ones\n                      , preprint,https:\/\/arxiv.org\/abs\/1708.05136(2017)."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-017-0628-z"},{"key":"atypb13","first-page":"315","author":"Johnson R.","year":"2013","journal-title":"NY"},{"key":"atypb14","unstructured":"J. Kone\u010dn\u1ef3, H. B. McMahan, D. Ramage, and P. Richt\u00e1rik,\n                      Federated Optimization: Distributed Machine Learning for On-device Intelligence\n                      , preprint,https:\/\/arxiv.org\/abs\/1610.02527(2016)."},{"key":"atypb15","unstructured":"J. D. Lee, Q. Lin, T. Ma, and T. Yang,\n                      Distributed Stochastic Variance Reduced Gradient Methods and a Lower Bound for Communication Complexity\n                      , preprint,https:\/\/arxiv.org\/abs\/1507.07595(2015)."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2016.1278445"},{"key":"atypb17","first-page":"1973","author":"Ma C.","year":"2015","journal-title":"NY"},{"key":"atypb18","first-page":"3587","author":"Mishchenko K.","year":"2018","journal-title":"NY"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101702"},{"key":"atypb20","first-page":"55","author":"Pedregosa F.","year":"2017","journal-title":"NY"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024950"},{"key":"atypb22","first-page":"693","author":"Recht B.","year":"2011","journal-title":"NY"},{"key":"atypb23","first-page":"378","author":"Shalev-Shwartz S.","year":"2013","journal-title":"NY"},{"key":"atypb24","first-page":"1310","author":"Shokri R.","year":"2015","journal-title":"New York"},{"key":"atypb25","first-page":"6182","author":"Sun T.","year":"2017","journal-title":"NY"},{"key":"atypb26","unstructured":"M. Tak\u00e1\u010d, P. Richt\u00e1rik, and N. Srebro,\n                      Distributed Mini-Batch SDCA\n                      , preprint.https:\/\/arxiv.org\/abs\/1507.08322(2015)."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/16M1094415"},{"key":"atypb29","unstructured":"N. D. Vanli, M. Gurbuzbalaban, and A. Ozdaglar,\n                      A Stronger Convergence Result on the Proximal Incremental Aggregated Gradient Method\n                      preprint,https:\/\/arxiv.org\/abs\/1611.08022(2016)."},{"key":"atypb30","first-page":"1701","author":"Zhang R.","year":"2014","journal-title":"NY"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1194699","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:58:32Z","timestamp":1787338712000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1194699"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1194699"],"URL":"https:\/\/doi.org\/10.1137\/18m1194699","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}