{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T10:10:45Z","timestamp":1790763045887,"version":"4.1.0"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Gaspard Monge Program for Optimization and Operations Research"},{"DOI":"10.13039\/100012952","name":"Universit\u00e9 Grenoble Alpes","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012952","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Journal on Mathematics of Data Science"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In distributed optimization for large-scale learning, a major performance limitation stems from the communications between the different entities. To the extent that computations are performed by workers on local data while a coordinator machine coordinates their updates to minimize a global loss, we present an asynchronous optimization algorithm that efficiently reduces the communications between the coordinator and workers. This reduction comes from a random sparsification of the local updates. We show that this algorithm converges linearly in the strongly convex case and also identifies optimal strongly sparse solutions. We further exploit this identification to propose an automatic dimension reduction, aptly sparsifying all exchanges between coordinator and workers.<\/jats:p>","DOI":"10.1137\/20m1347772","type":"journal-article","created":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T12:44:41Z","timestamp":1623674681000},"page":"715-735","source":"Crossref","is-referenced-by-count":3,"title":["Distributed Learning with Sparse Communications by Identification"],"prefix":"10.1137","volume":"3","author":[{"given":"Dmitry","family":"Grishchenko","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2537-380X","authenticated-orcid":true,"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"}]},{"given":"Massih-Reza","family":"Amini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,14]]},"reference":[{"key":"atypb1","unstructured":"D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli,\n                      The convergence of sparsified gradient methods\n                      , in Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), Curran Associates, 2018."},{"key":"atypb2","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":"atypb3","first-page":"1","volume":"4","author":"Bach F.","year":"2012","journal-title":"Found. Trends Mach. Learn."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"D. Basu, D. Data, C. Karakus, and S. Diggavi,\n                      Qsparse-local-sgd: Distributed SGD with Quantization, Sparsification and Local Computations\n                      , in Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), Curran Associates, 2019.","DOI":"10.1109\/JSAIT.2020.2985917"},{"key":"atypb5","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":"atypb6","unstructured":"R. Bellman, R. Kalaba, and J. Lockett,\n                      Numerical Inversion of the Laplace Transform: Applications to Biology, Economics, Engineering and Physics\n                      , Elsevier, New York, 1966."},{"key":"atypb7","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , rentice Hall, Englewood Cliffs, NJ, 1989."},{"key":"atypb8","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"Bubeck S.","year":"2015","journal-title":"Found. Trends Mach. Learn."},{"key":"atypb9","unstructured":"I. S. Dhillon, P. K. Ravikumar, and A. Tewari,\n                      Nearest Neighbor based Greedy Coordinate Descent\n                      , in Advances in Neural Information Processing Systems 24, NIPS, 2011."},{"key":"atypb10","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1109\/18.382009","volume":"41","author":"Donoho D. L.","year":"1995","journal-title":"IEEE Trans. Inform. Theory"},{"key":"atypb11","first-page":"1236","volume":"89","author":"Fadili J. M.","year":"2019","journal-title":"Proceedings of Machine Learning Research"},{"key":"atypb12","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1007\/s10589-012-9461-3","volume":"53","author":"Fuentes M.","year":"2012","journal-title":"Comput. Optim. Appl."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0802032"},{"key":"atypb15","first-page":"1","author":"Hannah R.","year":"2016","journal-title":"J. Sci. Comput., ("},{"key":"atypb16","first-page":"251","volume":"11","author":"Hare W. L.","year":"2004","journal-title":"J. Convex Anal."},{"key":"atypb17","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/s11228-020-00561-1","volume":"28","author":"Iutzeler F.","year":"2020","journal-title":"Set-Valued Var. Anal."},{"key":"atypb18","unstructured":"P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D'Oliveira, H. Eichner, S. El Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gasc\u00f3n, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Kone\u010dn\u00fd, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. \u00d6zg\u00fcr, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tram\u00e8r, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao,\n                      Advances and Open Problems in Federated Learning\n                      , preprint,https:\/\/arxiv.org\/abs\/1912.04977, 2019."},{"key":"atypb19","first-page":"166","author":"Khirirat S.","year":"2018","journal-title":"IEEE"},{"key":"atypb20","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":"atypb21","first-page":"777","volume":"10","author":"Langford J.","year":"2009","journal-title":"J. Mach. Learn. Res."},{"key":"atypb22","first-page":"1705","volume":"13","author":"Lee S.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"atypb23","unstructured":"M. Li, D. G. Andersen, and A. Smola,\n                      Distributed delayed proximal gradient methods\n                      , in NIPS Workshop on Optimization for Machine Learning, 2013."},{"key":"atypb24","unstructured":"T. Li, A. K. Sahu, A. Talwalkar, and V. Smith,\n                      Federated Learning: Challenges, Methods, and Future Directions\n                      , preprint,https:\/\/arxiv.org\/abs\/1908.07873, 2019."},{"key":"atypb25","first-page":"7854","volume":"18","author":"Lin H.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/17M1125157"},{"key":"atypb27","unstructured":"Y. Lin, S. Han, H. Mao, Y. Wang, and W. J. Dally,\n                      Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training\n                      ,https:\/\/arxiv.org\/abs\/1712.01887, 2017."},{"key":"atypb28","first-page":"285","volume":"16","author":"Liu J.","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"atypb29","first-page":"885","author":"Loshchilov I.","year":"2011","journal-title":"ACM"},{"key":"atypb30","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1080\/10556788.2019.1650361","volume":"36","author":"Ma C.","year":"2021","journal-title":"Optim. Methods Softw."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"B. Martinet,\n                      R\u00e9gularisation d'in\u00e9quations variationelles par approximation successives\n                      , Revue Fran\u00e7aise d'Informatique et de Recherche Op\u00e9rationelle, R3 (1970), pp. 154-158.","DOI":"10.1051\/m2an\/197004R301541"},{"key":"atypb32","unstructured":"M. Massias, A. Gramfort, and J. Salmon,\n                      Celer: A Fast Solver for the Lasso with Dual Extrapolation\n                      , preprint,https:\/\/arxiv.org\/abs\/1802.07481, 2018."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/18M1194699"},{"key":"atypb34","first-page":"3587","volume":"80","author":"Mishchenko K.","year":"2018","journal-title":"Proceedings of Machine Learning Research"},{"key":"atypb35","first-page":"2574","volume":"70","author":"Namkoong H.","year":"2017","journal-title":"Proceedings of Machine Learning Research"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb37","unstructured":"J. Nutini, I. Laradji, and M. Schmidt,\n                      Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence\n                      , preprint,https:\/\/arxiv.org\/abs\/1712.08859, 2017."},{"key":"atypb38","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1007\/s11590-018-1325-z","volume":"13","author":"Nutini J.","year":"2019","journal-title":", Optim. Lett."},{"key":"atypb39","unstructured":"F. Pedregosa, R. Leblond, and S. Lacoste-Julien,\n                      Breaking the nonsmooth barrier: A scalable parallel method for composite optimization\n                      , in Advances in Neural Information Processing Systems 30, NIPS, 2017."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024950"},{"key":"atypb41","first-page":"4124","volume":"80","author":"Poon C.","year":"2018","journal-title":"Proceedings of Machine Learning Research"},{"key":"atypb42","first-page":"11","author":"Renggli C.","year":"2019","journal-title":"Storage and Analysis"},{"key":"atypb43","first-page":"2657","volume":"17","author":"Richt\u00e1rik P.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"atypb44","doi-asserted-by":"crossref","first-page":"1233","DOI":"10.1007\/s11590-015-0916-1","volume":"10","author":"Richt\u00e1rik P.","year":"2016","journal-title":"Optim. Lett."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"atypb46","first-page":"1058","author":"Seide F.","year":"2014","journal-title":"Proceedings of the Fifteenth Annual Conference of the International Speech Communication Association"},{"key":"atypb47","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/s101070050022","volume":"88","author":"Solodov M. V.","year":"2000","journal-title":"Math. Program."},{"key":"atypb48","first-page":"4447","author":"Stich S. U.","year":"2018","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb49","first-page":"4381","author":"Stich S. U.","year":"2017","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb50","first-page":"1488","author":"Strom N.","year":"2015","journal-title":"Poceedings of the Sixteenth Annual Conference of the International Speech Communication Association"},{"key":"atypb51","unstructured":"T. Sun, R. Hannah, and W. Yin,\n                      Asynchronous coordinate descent under more realistic assumptions\n                      , in Advances in Neural Information Processing Systems, 2017."},{"key":"atypb52","first-page":"1110","author":"Sun Y.","year":"2019","journal-title":"Artificial Intelligence and Statistics"},{"key":"atypb53","first-page":"103","author":"Vaiter S.","year":"2015","journal-title":"Springer"},{"key":"atypb54","unstructured":"T. Vogels, S. P. Karimireddy, and M. Jaggi,\n                      Powersgd: Practical low-rank gradient compression for distributed optimization\n                      , in NeurIPS, 2019."},{"key":"atypb55","first-page":"3636","author":"Wang J.","year":"2017","journal-title":"International Conference on Machine Learning"},{"key":"atypb56","first-page":"1306","author":"Wangni J.","year":"2018","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/0331048"},{"key":"atypb58","first-page":"1","volume":"37","author":"Zhao P.","year":"2015","journal-title":"Proceedings of Machine Learning Research"}],"container-title":["SIAM Journal on Mathematics of Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1347772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:06:56Z","timestamp":1787332016000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1347772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1347772"],"URL":"https:\/\/doi.org\/10.1137\/20m1347772","relation":{},"ISSN":["2577-0187"],"issn-type":[{"value":"2577-0187","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}