{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:42:26Z","timestamp":1776832946113,"version":"3.51.2"},"reference-count":12,"publisher":"American Mathematical Society (AMS)","issue":"325","license":[{"start":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T00:00:00Z","timestamp":1616803200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-13-1-0129"],"award-info":[{"award-number":["N00014-13-1-0129"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["1740707"],"award-info":[{"award-number":["1740707"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["1634597"],"award-info":[{"award-number":["1634597"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["1628384"],"award-info":[{"award-number":["1628384"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["8F-30039"],"award-info":[{"award-number":["8F-30039"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["N00014-13-1-0129"],"award-info":[{"award-number":["N00014-13-1-0129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1740707"],"award-info":[{"award-number":["1740707"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1634597"],"award-info":[{"award-number":["1634597"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1628384"],"award-info":[{"award-number":["1628384"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["8F-30039"],"award-info":[{"award-number":["8F-30039"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["N00014-13-1-0129"],"award-info":[{"award-number":["N00014-13-1-0129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1740707"],"award-info":[{"award-number":["1740707"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1634597"],"award-info":[{"award-number":["1634597"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1628384"],"award-info":[{"award-number":["1628384"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["8F-30039"],"award-info":[{"award-number":["8F-30039"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["N00014-13-1-0129"],"award-info":[{"award-number":["N00014-13-1-0129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1740707"],"award-info":[{"award-number":["1740707"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1634597"],"award-info":[{"award-number":["1634597"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1628384"],"award-info":[{"award-number":["1628384"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["8F-30039"],"award-info":[{"award-number":["8F-30039"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["N00014-13-1-0129"],"award-info":[{"award-number":["N00014-13-1-0129"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["1740707"],"award-info":[{"award-number":["1740707"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["1634597"],"award-info":[{"award-number":["1634597"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["1628384"],"award-info":[{"award-number":["1628384"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["8F-30039"],"award-info":[{"award-number":["8F-30039"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["N00014-13-1-0129"],"award-info":[{"award-number":["N00014-13-1-0129"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["1740707"],"award-info":[{"award-number":["1740707"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["1634597"],"award-info":[{"award-number":["1634597"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["1628384"],"award-info":[{"award-number":["1628384"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["8F-30039"],"award-info":[{"award-number":["8F-30039"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>We consider coordinate descent methods for minimization of convex quadratic functions, in which exact line searches are performed at each iteration. (This algorithm is identical to Gauss-Seidel on the equivalent symmetric positive definite linear system.) We describe a class of convex quadratic functions for which the random permutations version of cyclic coordinate descent (RPCD) is observed to outperform the standard cyclic coordinate descent (CCD) approach on computational tests, yielding convergence behavior similar to the fully random variant (RCD). A convergence analysis is developed to explain the empirical observations.<\/p>","DOI":"10.1090\/mcom\/3530","type":"journal-article","created":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T09:26:38Z","timestamp":1581499598000},"page":"2217-2248","source":"Crossref","is-referenced-by-count":14,"title":["Analyzing random permutations for cyclic coordinate descent"],"prefix":"10.1090","volume":"89","author":[{"given":"Stephen","family":"Wright","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ching-pei","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2020,3,27]]},"reference":[{"issue":"4","key":"1","doi-asserted-by":"publisher","first-page":"2037","DOI":"10.1137\/120887679","article-title":"On the convergence of block coordinate descent type methods","volume":"23","author":"Beck, Amir","year":"2013","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"2","first-page":"3","article-title":"Normierte Ringe","volume":"9(51)","author":"Gelfand, I.","year":"1941","journal-title":"Rec. Math. [Mat. Sbornik] N.S."},{"issue":"3","key":"3","doi-asserted-by":"publisher","first-page":"1246","DOI":"10.1093\/imanum\/dry040","article-title":"Random permutations fix a worst case for cyclic coordinate descent","volume":"39","author":"Lee, Ching-pei","year":"2019","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"key":"4","first-page":"Paper No. 184, 24","article-title":"On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization","volume":"18","author":"Li, Xingguo","year":"2017","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","article-title":"Efficiency of coordinate descent methods on huge-scale optimization problems","volume":"22","author":"Nesterov, Yu.","year":"2012","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"6","unstructured":"B. Recht and C. R\u00e9, Toward a noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences, Proceedings of the 25th Annual Conference on Learning Theory, vol. 23, 2012, pp. 11.1\u201311.24."},{"key":"7","first-page":"567","article-title":"Stochastic dual coordinate ascent methods for regularized loss minimization","volume":"14","author":"Shalev-Shwartz, Shai","year":"2013","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"8","unstructured":"R. Sun and M. Hong, Improved iteration complexity bounds of cyclic block coordinate descent for convex problems, Advances in Neural Information Processing Systems, 2015, pp. 1306\u20131314."},{"key":"9","unstructured":"R. Sun, Z.-Q. Luo, and Y. Ye, On the efficiency of random permutation for admm and coordinate descent, Tech. Report arXiv:1503.06387 (2019). To appear in Math. Oper. Res."},{"key":"10","doi-asserted-by":"crossref","unstructured":"R. Sun and Y. Ye, Worst-case complexity of cyclic coordinate descent: \ud835\udc42(\ud835\udc5b\u00b2) gap with randomized version, Mathematical Programming (2019), 1\u201334, Online first.","DOI":"10.1007\/s10107-019-01437-5"},{"key":"11","unstructured":"S. J. Wright, Computations with coordinate descent methods, Presentation at Workshop on Challenges in Optimization for Data Science, \\url{https:\/\/pcombet.math.ncsu.edu\/data2015\/}, July 2015."},{"key":"12","doi-asserted-by":"crossref","unstructured":"S. J. Wright, Coordinate descent methods, Colloquium, Courant Institute of Mathematical Sciences, December 2015.","DOI":"10.1007\/s10107-015-0892-3"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-325\/S0025-5718-2020-03530-3\/mcom3530_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/earlyview\/#mcom3530\/.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-325\/S0025-5718-2020-03530-3\/S0025-5718-2020-03530-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:45:51Z","timestamp":1776829551000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-325\/S0025-5718-2020-03530-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,27]]},"references-count":12,"journal-issue":{"issue":"325","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S0025-5718-2020-03530-3"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3530","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2020,3,27]]}}}