{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:43Z","timestamp":1740109303225,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T00:00:00Z","timestamp":1599436800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T00:00:00Z","timestamp":1599436800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation","award":["CCF-1527568"],"award-info":[{"award-number":["CCF-1527568"]}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217989","CCF-1909538"],"award-info":[{"award-number":["CCF-1217989","CCF-1909538"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"DOI":"10.1007\/s10107-020-01552-8","type":"journal-article","created":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T14:02:45Z","timestamp":1599487365000},"page":"615-677","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup"],"prefix":"10.1007","volume":"190","author":[{"given":"Yun Kuen","family":"Cheung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Cole","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0573-1369","authenticated-orcid":false,"given":"Yixin","family":"Tao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,7]]},"reference":[{"issue":"6","key":"1552_CR1","doi-asserted-by":"publisher","first-page":"51:1","DOI":"10.1145\/2814566","volume":"62","author":"H Avron","year":"2015","unstructured":"Avron, H., Druinsky, A., Gupta, A.: Revisiting asynchronous linear solvers: provable convergence rate through randomization. J. ACM 62(6), 51:1\u201351:27 (2015)","journal-title":"J. ACM"},{"issue":"2","key":"1552_CR2","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1145\/322063.322067","volume":"25","author":"GM Baudet","year":"1978","unstructured":"Baudet, G.M.: Asynchronous iterative methods for multiprocessors. J. ACM 25(2), 226\u2013244 (1978)","journal-title":"J. ACM"},{"key":"1552_CR3","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"DP Bertsekas","year":"1989","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice Hall, Upper Saddle River (1989)"},{"issue":"3","key":"1552_CR4","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/S1052623497331063","volume":"10","author":"DP Bertsekas","year":"2000","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: Gradient convergence in gradient methods with errors. SIAM J. Optim. 10(3), 627\u2013642 (2000)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1552_CR5","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1137\/S0363012995282784","volume":"36","author":"VS Borkar","year":"1998","unstructured":"Borkar, V.S.: Asynchronous stochastic approximations. SIAM J. Control Optim. 36(3), 662\u2013663 (1998)","journal-title":"SIAM J. Control Optim."},{"issue":"2","key":"1552_CR6","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0024-3795(69)90028-7","volume":"2","author":"D Chazan","year":"1969","unstructured":"Chazan, D., Miranker, W.: Chaotic relaxation. Linear Algebra Appl. 2(2), 199\u2013222 (1969)","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"1552_CR7","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1137\/0803026","volume":"3","author":"G Chen","year":"1993","unstructured":"Chen, G., Teboulle, M.: Convergence analysis of a proximal-like minimization algorithm using Bregman\u2019s function. SIAM J. Optim. 3(3), 538\u2013543 (1993)","journal-title":"SIAM J. Optim."},{"key":"1552_CR8","doi-asserted-by":"publisher","unstructured":"Cheung, Y.K., Cole, R.: Amortized analysis of asynchronous price dynamics. In: 26th Annual European Symposium on Algorithms, ESA 2018, August 20\u201322, 2018, pp. 18:1\u201318:15, Helsinki, Finland (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.18","DOI":"10.4230\/LIPIcs.ESA.2018.18"},{"key":"1552_CR9","doi-asserted-by":"crossref","unstructured":"Cheung, Y.K., Cole, R., Devanur, N.R.: Tatonnement beyond gross substitutes? Gradient descent to the rescue. In: STOC, pp. 191\u2013200 (2013)","DOI":"10.1145\/2488608.2488633"},{"key":"1552_CR10","unstructured":"Cheung, Y.K., Cole, R., Tao, Y.: Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism (2018). arXiv e-prints arXiv:1811.05087"},{"key":"1552_CR11","unstructured":"Cole, R., Tao, Y.: An analysis of asynchronous stochastic accelerated coordinate descent (2018). arXiv e-prints arXiv:1808.05156"},{"issue":"3","key":"1552_CR12","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1023\/A:1022627411411","volume":"20","author":"C Cortes","year":"1995","unstructured":"Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20(3), 273\u2013297 (1995). https:\/\/doi.org\/10.1023\/A:1022627411411","journal-title":"Mach. Learn."},{"key":"1552_CR13","unstructured":"Fang, C., Huang, Y., Lin, Z.: Accelerating asynchronous algorithms for convex optimization by momentum compensation (2018). arXiv preprint arXiv:1802.09747"},{"issue":"1\u20132","key":"1552_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0377-0427(00)00409-X","volume":"123","author":"A Frommer","year":"2000","unstructured":"Frommer, A., Szyld, D.B.: On asynchronous iterations. J. Comput. Appl. Math. 123(1\u20132), 201\u2013216 (2000). Numerical Analysis 2000. Vol. III: Linear Algebra","journal-title":"J. Comput. Appl. Math."},{"key":"1552_CR15","unstructured":"Hannah, R., Feng, F., Yin, W.: A2BCD: Asynchronous acceleration with optimal complexity. In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, 6\u20139 May 2019. OpenReview.net. https:\/\/openreview.net\/forum?id=rylIAsCqYm"},{"key":"1552_CR16","first-page":"81:1","volume":"19","author":"R Leblond","year":"2018","unstructured":"Leblond, R., Pedregosa, F., Lacoste-Julien, S.: Improved asynchronous parallel optimization analysis for stochastic incremental methods. J. Mach. Learn. Res. 19, 81:1\u201381:68 (2018)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"1552_CR17","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/140961134","volume":"25","author":"J Liu","year":"2015","unstructured":"Liu, J., Wright, S.J.: Asynchronous stochastic coordinate descent: parallelism and convergence properties. SIAM J. Optim. 25(1), 351\u2013376 (2015)","journal-title":"SIAM J. Optim."},{"key":"1552_CR18","first-page":"285","volume":"16","author":"J Liu","year":"2015","unstructured":"Liu, J., Wright, S.J., R\u00e9, C., Bittorf, V., Sridhar, S.: An asynchronous parallel stochastic coordinate descent algorithm. J. Mach. Learn. Res. 16, 285\u2013322 (2015)","journal-title":"J. Mach. Learn. Res."},{"issue":"1\u20132","key":"1552_CR19","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s10107-014-0800-2","volume":"152","author":"Z Lu","year":"2015","unstructured":"Lu, Z., Xiao, L.: On the complexity analysis of randomized block-coordinate descent methods. Math. Program. 152(1\u20132), 615\u2013642 (2015)","journal-title":"Math. Program."},{"issue":"4","key":"1552_CR20","doi-asserted-by":"publisher","first-page":"2202","DOI":"10.1137\/16M1057000","volume":"27","author":"H Mania","year":"2017","unstructured":"Mania, H., Pan, X., Papailiopoulos, D., Recht, B., Ramchandran, K., Jordan, M.: Perturbed iterate analysis for asynchronous stochastic optimization. SIAM J. Optim. 27(4), 2202\u20132229 (2017). https:\/\/doi.org\/10.1137\/16M1057000","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1552_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1111\/j.1467-9868.2007.00627.x","volume":"70","author":"L Meier","year":"2008","unstructured":"Meier, L., Van De Geer, S., Bhlmann, P.: The group lasso for logistic regression. J. R. Stat. Soc. Ser. B (Stat. Methodol.) 70(1), 53\u201371 (2008)","journal-title":"J. R. Stat. Soc. Ser. B (Stat. Methodol.)"},{"key":"1552_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Springer, Berlin (2004)"},{"issue":"2","key":"1552_CR23","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"key":"1552_CR24","unstructured":"Niu, F., Recht, B., Re, C., Wright, S.J.: Hogwild: a lock-free approach to parallelizing stochastic gradient descent. In: NIPS, pp. 693\u2013701 (2011)"},{"issue":"1\u20132","key":"1552_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-012-0614-z","volume":"144","author":"P Richt\u00e1rik","year":"2014","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1\u20132), 1\u201338 (2014)","journal-title":"Math. Program."},{"key":"1552_CR26","unstructured":"Saunders, C., Gammerman, A., Vovk, V.: Ridge regression learning algorithm in dual variables. In: Proceedings of the Fifteenth International Conference on Machine Learning, ICML \u201998, pp. 515\u2013521. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1998). http:\/\/dl.acm.org\/citation.cfm?id=645527.657464"},{"key":"1552_CR27","first-page":"6182","volume-title":"Advances in Neural Information Processing Systems","author":"T Sun","year":"2017","unstructured":"Sun, T., Hannah, R., Yin, W.: Asynchronous coordinate descent under more realistic assumptions. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 30, pp. 6182\u20136190. Curran Associates, Inc., New York (2017)"},{"key":"1552_CR28","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1994","unstructured":"Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267\u2013288 (1994)","journal-title":"J. R. Stat. Soc. Ser. B"},{"issue":"1\u20132","key":"1552_CR29","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10107-007-0170-0","volume":"117","author":"P Tseng","year":"2009","unstructured":"Tseng, P., Yun, S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117(1\u20132), 387\u2013423 (2009)","journal-title":"Math. Program."},{"issue":"9","key":"1552_CR30","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1109\/TAC.1986.1104412","volume":"31","author":"JN Tsitsiklis","year":"1986","unstructured":"Tsitsiklis, J.N., Bertsekas, D.P., Athans, M.: Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Trans. Autom. Control 31(9), 803\u2013812 (1986)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"1","key":"1552_CR31","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","volume":"151","author":"SJ Wright","year":"2015","unstructured":"Wright, S.J.: Coordinate descent algorithms. Math. Program. 151(1), 3\u201334 (2015)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01552-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01552-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01552-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T09:08:08Z","timestamp":1723540088000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01552-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,7]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1552"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01552-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,9,7]]},"assertion":[{"value":"7 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}