{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:06:45Z","timestamp":1775736405512,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T00:00:00Z","timestamp":1684281600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T00:00:00Z","timestamp":1684281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["861137"],"award-info":[{"award-number":["861137"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block-coordinates are updated asynchronously and randomly according to an arbitrary probability distribution. We prove that the iterates generated by the algorithm form a stochastic quasi-Fej\u00e9r sequence and thus converge almost surely to a minimizer of the objective function. Moreover, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type. Under the same condition strong convergence of the iterates is provided as well as their linear convergence rate.<\/jats:p>","DOI":"10.1007\/s10589-023-00489-w","type":"journal-article","created":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T11:02:07Z","timestamp":1684321327000},"page":"303-344","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3114-4835","authenticated-orcid":false,"given":"Cheik","family":"Traor\u00e9","sequence":"first","affiliation":[]},{"given":"Saverio","family":"Salzo","sequence":"additional","affiliation":[]},{"given":"Silvia","family":"Villa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,17]]},"reference":[{"key":"489_CR1","unstructured":"Agarwal, A., Duchi, J.C.: Distributed delayed stochastic optimization. In: Shawe-Taylor, J., Zemel, R., Bartlett, P., Pereira, F., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 24 (2011)"},{"issue":"6","key":"489_CR2","doi-asserted-by":"publisher","first-page":"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), 1\u201327 (2015)","journal-title":"J. ACM"},{"key":"489_CR3","doi-asserted-by":"crossref","unstructured":"B\u00e4ckstr\u00f6m, K., Papatriantafilou, M., Tsigas, P.: Mindthestep-asyncpsgd: adaptive asynchronous parallel stochastic gradient descent. In: 2019 IEEE International Conference on Big Data (Big Data), pp. 16\u201325. IEEE (2019)","DOI":"10.1109\/BigData47090.2019.9006054"},{"issue":"1","key":"489_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"issue":"2","key":"489_CR5","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1214\/14-AOS1204","volume":"42","author":"A Belloni","year":"2014","unstructured":"Belloni, A., Chernozhukov, V., Wang, L.: Pivotal estimation via square-root Lasso in nonparametric regression. Annal. Stat. 42(2), 757\u2013788 (2014)","journal-title":"Annal. Stat."},{"key":"489_CR6","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, vol. 23. Prentice hall Englewood Cliffs, NJ (1989)"},{"issue":"2","key":"489_CR7","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10107-016-1091-6","volume":"165","author":"J Bolte","year":"2017","unstructured":"Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From error bounds to the complexity of first-order descent methods for convex functions. Math. Program. 165(2), 471\u2013507 (2017)","journal-title":"Math. Program."},{"key":"489_CR8","doi-asserted-by":"crossref","unstructured":"Cannelli, L., Facchinei, F., Kungurtsev, V., Scutari, G.: Asynchronous parallel algorithms for nonconvex optimization. Math. Program. 184, 121\u2013154 (2020)","DOI":"10.1007\/s10107-019-01408-w"},{"issue":"2","key":"489_CR9","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":"2","key":"489_CR10","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1109\/TAC.2021.3056535","volume":"67","author":"S Chen","year":"2021","unstructured":"Chen, S., Garcia, A., Shahrampour, S.: On distributed non-convex optimization: projected subgradient method for weakly convex problems in networks. IEEE Trans. Autom. Control 67(2), 662\u2013675 (2021)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"1","key":"489_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1137\/S003614450037906X","volume":"43","author":"SS Chen","year":"2001","unstructured":"Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Rev. 43(1), 129\u2013159 (2001)","journal-title":"SIAM Rev."},{"issue":"1","key":"489_CR12","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/s10107-016-1044-0","volume":"168","author":"PL Combettes","year":"2018","unstructured":"Combettes, P.L., Eckstein, J.: Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions. Math. Program. 168(1), 645\u2013672 (2018)","journal-title":"Math. Program."},{"issue":"2","key":"489_CR13","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1137\/140971233","volume":"25","author":"PL Combettes","year":"2015","unstructured":"Combettes, P.L., Pesquet, J.-C.: Stochastic quasi-Fej\u00e9r block-coordinate fixed point iterations with random sweeping. SIAM J. Optim. 25(2), 1221\u20131248 (2015)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"489_CR14","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1137\/050626090","volume":"4","author":"PL Combettes","year":"2005","unstructured":"Combettes, P.L., Wajs, V.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168\u20131200 (2005)","journal-title":"Multiscale Model. Simul."},{"issue":"4","key":"489_CR15","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1137\/050626090","volume":"4","author":"PL Combettes","year":"2005","unstructured":"Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168\u20131200 (2005)","journal-title":"Multiscale Model. Simul."},{"key":"489_CR16","unstructured":"Davis, D.: The asynchronous PALM algorithm for nonsmooth nonconvex problems. Optim. Control. https:\/\/doi.org\/10.48550\/arXiv.1604.00526 (2016)"},{"issue":"4","key":"489_CR17","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D Donoho","year":"2006","unstructured":"Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"489_CR18","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1287\/moor.2017.0889","volume":"43","author":"D Drusvyatskiy","year":"2018","unstructured":"Drusvyatskiy, D., Lewis, A.S.: Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3), 919\u2013948 (2018)","journal-title":"Math. Oper. Res."},{"key":"489_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/9781108591034","volume-title":"Probability: theory and examples","author":"R Durrett","year":"2019","unstructured":"Durrett, R.: Probability: theory and examples, vol. 49. Cambridge University Press (2019)"},{"issue":"12","key":"489_CR20","doi-asserted-by":"publisher","first-page":"3740","DOI":"10.1109\/TAC.2016.2525015","volume":"61","author":"HR Feyzmahdavian","year":"2016","unstructured":"Feyzmahdavian, H.R., Aytekin, A., Johansson, M.: An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Trans. Autom. Control 61(12), 3740\u20133754 (2016)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"1","key":"489_CR21","doi-asserted-by":"publisher","first-page":"1\u201322","DOI":"10.18637\/jss.v033.i01","volume":"33","author":"J Friedman","year":"2010","unstructured":"Friedman, J., Hastie, T., Tibshirani, R.: Regularization paths for generalized linear models via coordinate descent. J. Stat. Softw. 33(1), 1\u201322 (2010)","journal-title":"J. Stat. Softw."},{"issue":"3","key":"489_CR22","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1080\/10618600.1998.10474784","volume":"7","author":"WJ Fu","year":"1998","unstructured":"Fu, W.J.: Penalized regressions: the bridge versus the lasso. J. Comput. Graph. Stat. 7(3), 397\u2013416 (1998)","journal-title":"J. Comput. Graph. Stat."},{"issue":"1","key":"489_CR23","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10915-017-0628-z","volume":"76","author":"R Hannah","year":"2018","unstructured":"Hannah, R., Yin, W.: On unbounded delays in asynchronous parallel fixed-point algorithms. J. Sci. Comput. 76(1), 299\u2013326 (2018)","journal-title":"J. Sci. Comput."},{"issue":"5","key":"489_CR24","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1198\/0003130042836","volume":"58","author":"D Hunter","year":"2004","unstructured":"Hunter, D., Lange, K.: A tutorial on mm algorithms. Am. Stat. 58(5), 30\u201337 (2004)","journal-title":"Am. Stat."},{"issue":"4","key":"489_CR25","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1109\/JSTSP.2007.910971","volume":"1","author":"S-J Kim","year":"2007","unstructured":"Kim, S.-J., Koh, K., Lustig, M., Boyd, S., Gorinevsky, D.: An interior-point method for large-scale $${\\ell }_1$$-regularized least squares. IEEE J. Sel. Top. Signal Process. 1(4), 606\u2013617 (2007)","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"489_CR26","doi-asserted-by":"crossref","unstructured":"Kress, R.: Ill-conditioned linear systems. In Numerical Analysis, pages 77\u201392. Springer, (1998)","DOI":"10.1007\/978-1-4612-0599-9_5"},{"key":"489_CR27","unstructured":"Lee, C.-P., Wright, S.: First-order algorithms converge faster than $$o(1\/k)$$ on convex problems. In K.\u00a0Chaudhuri and R.\u00a0Salakhutdinov (Eds.) Proceedings of the 36th International Conference on Machine Learning, volume\u00a097 of Proceedings of Machine Learning Research, pages 3754\u20133762. PMLR, (2019)"},{"key":"489_CR28","unstructured":"Lian, X., Huang, Y., Li, Y., Liu, J.: Asynchronous parallel stochastic gradient for nonconvex optimization. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 28, pp. 2737\u20132745. Curran Associates, Inc. (2015)"},{"key":"489_CR29","unstructured":"Lian, X., Zhang, H., Hsieh, C.-J., Huang, Y., Liu, J.: A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order. In: Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 29. Curran Associates, Inc. (2016)"},{"key":"489_CR30","unstructured":"Liu, J., Wright, S., R\u00e9, C., Bittorf, V., Sridhar, S.: An asynchronous parallel stochastic coordinate descent algorithm. In: International Conference on Machine Learning, pages 469\u2013477. PMLR, (2014)"},{"issue":"1","key":"489_CR31","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":"489_CR32","unstructured":"Liu, J., Wright, S.\u00a0J., Sridhar, S.: An asynchronous parallel randomized kaczmarz algorithm. arXiv preprint arXiv:1401.4780, (2014)"},{"issue":"1","key":"489_CR33","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02096261","volume":"46","author":"Z-Q Luo","year":"1993","unstructured":"Luo, Z.-Q., Tseng, P.: Error bounds and convergence analysis of feasible descent methods: a general approach. Ann. Oper. Res. 46(1), 157\u2013178 (1993)","journal-title":"Ann. Oper. Res."},{"key":"489_CR34","unstructured":"Mai, V., Johansson, M.: Convergence of a stochastic gradient method with momentum for non-smooth non-convex optimization. In: International Conference on Machine Learning, pages 6630\u20136639. PMLR, (2020)"},{"issue":"2","key":"489_CR35","first-page":"381\u2013421","volume":"13","author":"S Marcellin","year":"2006","unstructured":"Marcellin, S., Thibault, L.: Evolution problems associated with primal lower nice functions. J. Conv. Anal. 13(2), 381\u2013421 (2006)","journal-title":"J. Conv. Anal."},{"issue":"C","key":"489_CR36","first-page":"381","volume":"8","author":"A Nedi\u0107","year":"2001","unstructured":"Nedi\u0107, A., Bertsekas, D.P., Borkar, V.S.: Distributed asynchronous incremental subgradient methods. Stud. Comput. Math. 8(C), 381\u2013407 (2001)","journal-title":"Stud. Comput. Math."},{"key":"489_CR37","volume-title":"Introductory lectures on convex optimization: a basic course","author":"Y Nesterov","year":"2003","unstructured":"Nesterov, Y.: Introductory lectures on convex optimization: a basic course, vol. 87. Springer Science & Business Media (2003)"},{"issue":"1","key":"489_CR38","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125\u2013161 (2013)","journal-title":"Math. Program."},{"key":"489_CR39","unstructured":"Niu, F., Recht, B., R\u00e9, C., Wright, S.J.: Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. In: Advances in Neural Information Processing Systems, vol. 24 (2011)"},{"key":"489_CR40","unstructured":"Paine, T., Jin, H., Yang, J., Lin, Z., Huang, T.: Gpu asynchronous stochastic gradient descent to speed up neural network trainingtraining (2013). https:\/\/doi.org\/10.48550\/arXiv.1312.6186"},{"issue":"5","key":"489_CR41","doi-asserted-by":"publisher","first-page":"A2851","DOI":"10.1137\/15M1024950","volume":"38","author":"Z Peng","year":"2016","unstructured":"Peng, Z., Xu, Y., Yan, M., Yin, W.: Arock: an algorithmic framework for asynchronous parallel coordinate updates. SIAM J. Sci. Comput. 38(5), A2851\u2013A2879 (2016)","journal-title":"SIAM J. Sci. Comput."},{"key":"489_CR42","doi-asserted-by":"crossref","unstructured":"Salzo, S., Villa, S.: Parallel random block-coordinate forward\u2013backward algorithm: a unified convergence analysis. Math. Program. 193(1), 225\u2013269 (2022)","DOI":"10.1007\/s10107-020-01602-1"},{"key":"489_CR43","volume-title":"Harmonic and applied analysis: from radon transforms to machine learning","author":"S Salzo","year":"2022","unstructured":"Salzo, S., Villa, S.: Proximal gradient methods for machine learning and imaging. In: Mari, F.D., Vito, E.D. (eds.) Harmonic and applied analysis: from radon transforms to machine learning. Springer International Publishing, Cham (2022)"},{"key":"489_CR44","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press (2014)"},{"key":"489_CR45","unstructured":"Sun, T., Hannah, R., Yin, W.: Asynchronous coordinate descent under more realistic assumptions. In: Advances in Neural Information Processing Systems, vol. 30 (2017)"},{"issue":"1","key":"489_CR46","first-page":"3385","volume":"14","author":"T Sun","year":"2013","unstructured":"Sun, T., Zhang, C.-H.: Sparse matrix inversion with scaled lasso. J. Mach. Learn. Res. 14(1), 3385\u20133418 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"489_CR47","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1996","unstructured":"Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Series B (Methodol.) 58(1), 267\u2013288 (1996)","journal-title":"J. R. Stat. Soc. Series B (Methodol.)"},{"issue":"3","key":"489_CR48","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1109\/TIT.2005.864420","volume":"52","author":"JA Tropp","year":"2006","unstructured":"Tropp, J.A.: Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52(3), 1030\u20131051 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"489_CR49","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1023\/A:1017501703105","volume":"109","author":"P Tseng","year":"2001","unstructured":"Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109(3), 475\u2013494 (2001)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"489_CR50","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10107-010-0394-2","volume":"125","author":"P Tseng","year":"2010","unstructured":"Tseng, P.: Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math. Program. 125(2), 263\u2013295 (2010)","journal-title":"Math. Program."},{"key":"489_CR51","unstructured":"Um, K., Brand, R., Holl, P., Thuerey, N.: et\u00a0al. Solver-in-the-loop: learning from differentiable physics to interact with iterative pde-solvers. Adv. Neural Inf. Process. Syst. 33, 6111\u20136122 (2020)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00489-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00489-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00489-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T15:14:22Z","timestamp":1729437262000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00489-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,17]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["489"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00489-w","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,17]]},"assertion":[{"value":"1 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}