{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T00:39:28Z","timestamp":1791419968824,"version":"4.3.3"},"reference-count":45,"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":[[2015,1]]},"abstract":"<jats:p>We describe an asynchronous parallel stochastic proximal coordinate descent algorithm for minimizing a composite objective function, which consists of a smooth convex function added to a separable convex function. In contrast to previous analyses, our model of asynchronous computation accounts for the fact that components of the unknown vector may be written by some cores simultaneously with being read by others. Despite the complications arising from this possibility, the method achieves a linear convergence rate on functions that satisfy an optimal strong convexity property and a sublinear rate ($1\/k$) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is $O(n^{1\/4})$. We describe results from implementation on 10 cores of a multicore processor.<\/jats:p>","DOI":"10.1137\/140961134","type":"journal-article","created":{"date-parts":[[2015,2,5]],"date-time":"2015-02-05T12:46:01Z","timestamp":1423140361000},"page":"351-376","source":"Crossref","is-referenced-by-count":119,"title":["Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties"],"prefix":"10.1137","volume":"25","author":[{"given":"Ji","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen J.","family":"Wright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,2,5]]},"reference":[{"key":"atypb1","first-page":"5451","author":"Agarwal A.","year":"2012","journal-title":"Proceedings of the Conference on Decision and Control"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499359178"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"H. Avron, A. Druinsky, and A. Gupta,\n                      Revisiting asynchronous linear solvers: Provable convergence rate through randomization\n                      , in Proceedings of the IEEE International Parallel and Distributed Processing Symposium, 2014.","DOI":"10.1109\/IPDPS.2014.31"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/120887679"},{"key":"atypb6","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1989."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"atypb8","unstructured":"J. K. Bradley, A. Kyrola, D. Bickson, and C. Guestrin,\n                      Parallel coordinate descent for L1-regularized loss minimization\n                      , in Proceedings of the International Conference on Machine Learning, 2011."},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"C. Cortes and V. Vapnik,\n                      Support vector networks\n                      , Machine Learning, (1995), pp. 273-297.","DOI":"10.1023\/A:1022627411411"},{"key":"atypb10","first-page":"1647","volume":"24","author":"Cotter A.","year":"2011","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2161027"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396232"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"F. Facchinei, S. Sagratella, and G. Scutari,\n                      Flexible Parallel Algorithms for Big Data Optimization\n                      , Technical report, arXiv:1311.2444v1, 2013.","DOI":"10.1109\/ICASSP.2014.6854999"},{"key":"atypb14","unstructured":"O. Fercoq and P. Richta\u0301rik,\n                      Accelerated, Parallel, and Proximal Coordinate Descent\n                      , Technical report, arXiv:1312.5799, 2013."},{"key":"atypb15","unstructured":"O. Fercoq and P. Richta\u0301rik,\n                      Smooth Minimization of Nonsmooth Functions by Parallel Coordinate Descent\n                      , Technical report, arXiv:1309.5885, 2013."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/0804047"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00409-X"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/090780705"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.027"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/120863290"},{"key":"atypb21","unstructured":"J. Liu, S. J. Wright, C. Re\u0301, V. Bittorf, and S. Sridhar,\n                      An Asynchronous Parallel Stochastic Coordinate Descent Algorithm\n                      , Technical report, arXiv:1311.1873, 2013."},{"key":"atypb22","unstructured":"J. Liu, S. J. Wright, and S. Sridhar,\n                      An asynchronous Parallel Randomized Kaczmarz Algorithm\n                      , Technical report, arXiv:1401.4780, 2014."},{"key":"atypb23","unstructured":"Z. Lu and L. Xiao,\n                      On the Complexity Analysis of Randomized Block-Coordinate Descent Methods\n                      , Technical report, arXiv:1305.4723, 2013."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939948"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993250256"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"I. Necoara and D. Clipici,\n                      Efficient Parallel Ccoordinate Descent Algorithm for Convex Optimization Problems with Separable Constraints: Application to Distributed MPC\n                      , Technical report, arXiv:1302.3092, 2013.","DOI":"10.1016\/j.jprocont.2012.12.012"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"I. Necoara and A. Patrascu,\n                      A Random Coordinate Descent Algorithm for Optimization Problems with Composite Objective Function and Linear Coupled Constraints\n                      , Technical report, arXiv:1302.3074, 2013.","DOI":"10.1007\/s10589-013-9598-8"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Kluwer Academic, Norwell, MA, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb31","first-page":"693","volume":"24","author":"Niu F.","year":"2011","journal-title":"Adv. Neural Inform. Process. Systems"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"Z. Peng, M. Yan, and W. Yin,\n                      Parallel and Distributed Sparse Optimization\n                      , Technical report, Department of Mathematics, UCLA, 2013.","DOI":"10.1109\/ACSSC.2013.6810364"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"P. Richta\u0301rik and M. Taka\u0301c\u030c,\n                      Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function\n                      , Math. Program. Ser. A (2012).","DOI":"10.1007\/s10107-012-0614-z"},{"key":"atypb34","unstructured":"P. Richta\u0301rik and M. Taka\u0301c\u030c,\n                      Parallel Coordinate Descent Methods for Big Data Optimization\n                      , Technical report, arXiv: 1212.0873, 2012."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/110840054"},{"key":"atypb36","first-page":"28","volume":"25","author":"Scherrer C.","year":"2012","journal-title":"Adv. Neural Inf. Proces. Syst."},{"key":"atypb37","unstructured":"S. Shalev-Shwartz and T. Zhang,\n                      Accelerated mini-batch stochastic dual coordinate ascent\n                      , in NIPS 2013, Adv. Neural Inf. Process. Syst. 26, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, eds., 2013, pp. 378-385."},{"key":"atypb38","unstructured":"O. Shamir and T. Zhang,\n                      Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes\n                      , in Proceedings of the International Conference on Machine Learning, 2013."},{"key":"atypb39","first-page":"26","author":"Sridhar S.","year":"2013","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017501703105"},{"key":"atypb41","unstructured":"P. Tseng,\n                      On Accelerated Proximal Gradient Methods for Convex-Concave Optimization\n                      , Technical report, University of Washington, 2008."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0170-0"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-008-9215-4"},{"key":"atypb44","unstructured":"P.W. Wang and C.J. Lin,\n                      Iteration Complexity of Feasible Descent Methods for Convex Optimization\n                      , Technical report, Department of Computer Science, National Taiwan University, 2013."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016892"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140961134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:00Z","timestamp":1787337420000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140961134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140961134"],"URL":"https:\/\/doi.org\/10.1137\/140961134","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}