{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:27:53Z","timestamp":1787336873107,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"ASPIRE lab"},{"name":"LGE"},{"DOI":"10.13039\/100008297","name":"Cray Incorporated","doi-asserted-by":"publisher","award":["47277"],"award-info":[{"award-number":["47277"]}],"id":[{"id":"10.13039\/100008297","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004314","name":"Hewlett-Packard Development Company","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004314","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003816","name":"Huawei Technologies","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003816","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE 1106400"],"award-info":[{"award-number":["DGE 1106400"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007065","name":"Nvidia","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007065","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004682","name":"Oracle","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004682","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004358","name":"Samsung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004358","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0010200"],"award-info":[{"award-number":["DE-SC0010200"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0008700"],"award-info":[{"award-number":["DE-SC0008700"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>Primal and dual block coordinate descent methods are iterative methods for solving regularized and unregularized optimization problems. Distributed-memory parallel implementations of these methods have become popular in analyzing large machine learning datasets. However, existing implementations communicate at every iteration, which, on modern data center and supercomputing architectures, often dominates the cost of floating-point computation. Recent results on communication-avoiding Krylov subspace methods suggest that large speedups are possible by re-organizing iterative algorithms to avoid communication. We show how applying similar algorithmic transformations can lead to primal and dual block coordinate descent methods that only communicate every $s$ iterations---where $s$ is a tuning parameter---instead of every iteration for the regularized least-squares problem. We show that the communication-avoiding variants reduce the number of synchronizations by a factor of $s$ on distributed-memory parallel machines without altering the convergence rate and attain strong scaling speedups of up to $6.1\\times$ over the \u201cstandard algorithm\" on a Cray XC30 supercomputer.<\/jats:p>","DOI":"10.1137\/17m1134433","type":"journal-article","created":{"date-parts":[[2019,1,17]],"date-time":"2019-01-17T12:02:40Z","timestamp":1547726560000},"page":"C1-C27","source":"Crossref","is-referenced-by-count":9,"title":["Avoiding Communication in Primal and Dual Block Coordinate Descent Methods"],"prefix":"10.1137","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8251-9150","authenticated-orcid":true,"given":"Aditya","family":"Devarakonda","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kimon","family":"Fountoulakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael W.","family":"Mahoney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,1,17]]},"reference":[{"key":"atypb1","unstructured":"G. Ballard,\n                      Avoiding Communication in Dense Linear Algebra\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, Berkeley, CA, 2013."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492914000038"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7908-2604-3_16"},{"key":"atypb5","unstructured":"E. Carson,\n                      Communication-Avoiding Krylov Subspace Methods in Theory and Practice\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, Berkeley, CA, 2015."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/120893057"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/140990735"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/120881191"},{"key":"atypb9","first-page":"125","volume":"43","author":"Carson E.","year":"2014","journal-title":"Electron. Trans. Numer. Anal."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90062-8"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90045-9"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492916000076"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/080731992"},{"key":"atypb15","volume-title":"Tech. report UCB\/EECS-2007-123, EECS Department","author":"Demmel J.","year":"2007"},{"key":"atypb16","volume-title":"MPI: A Message-Passing Interface Standard","author":"Forum M. P. I.","year":"1994"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322254"},{"key":"atypb18","unstructured":"M. Hoemmen,\n                      Communication-Avoiding Krylov Subspace Methods\n                      , Ph.D. thesis, University of California, Berkeley, Berkeley, CA, 2010."},{"key":"atypb19","first-page":"3068","volume-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems","author":"Jaggi M.","year":"2014"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(92)90085-C"},{"key":"atypb21","first-page":"50048","volume-title":"Proceedings of the 12th International Machine Learning Conference","author":"Lang K.","year":"1995"},{"key":"atypb22","volume-title":"UCI Machine Learning Repository","author":"Lichman M.","year":"2013"},{"key":"atypb24","unstructured":"M. D. Mitzenmacher,\n                      The Power of Two Choices in Randomized Load Balancing\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, Berkeley, CA, 1996."},{"key":"atypb25","unstructured":"M. Mohiyuddin,\n                      Tuning Hardware and Software for Multiprocessors\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, Berkeley, CA, 2012."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654096"},{"key":"atypb27","unstructured":"NERSC,\n                      NERSC Edison Configuration\n                      ,http:\/\/www.nersc.gov\/users\/computational-systems\/edison\/configuration\/."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb29","first-page":"1823","volume-title":"Proceedings of the 33rd International Conference on Machine Learning","volume":"48","author":"Qu Z.","year":"2016"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49543-6_13"},{"key":"atypb31","first-page":"693","volume-title":"Advances in Neural Information Processing Systems","author":"Recht B.","year":"2011"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0614-z"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"atypb34","first-page":"567","volume":"14","author":"Shalev-Shwartz S.","year":"2013","journal-title":"J. Mach. Learn. Res."},{"key":"atypb35","unstructured":"E. Solomonik,\n                      Provably Efficient Algorithms for Numerical Tensor Algebra\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, Berkeley, CA, 2014."},{"key":"atypb36","volume-title":"Distributed Mini-Batch SDCA, preprint, https:\/\/arxiv.org\/abs\/1507.08322","author":"Tak\u00e1\u010d M.","year":"2015"},{"key":"atypb38","volume-title":"Minimizing Inner Product Data Dependencies in Conjugate Gradient Iteration","author":"Van Rosendale J.","year":"1983"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0909010"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.119"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0892-3"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1134433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:34:36Z","timestamp":1787333676000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1134433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1134433"],"URL":"https:\/\/doi.org\/10.1137\/17m1134433","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}