{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T22:30:06Z","timestamp":1768257006632,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T00:00:00Z","timestamp":1722038400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T00:00:00Z","timestamp":1722038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["Project-ID 432680300 SFB 1456"],"award-info":[{"award-number":["Project-ID 432680300 SFB 1456"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We present a Markov-chain analysis of blockwise-stochastic algorithms for solving partially block-separable optimization problems. Our main contributions to the extensive literature on these methods are statements about the Markov operators and distributions behind the iterates of stochastic algorithms, and in particular the regularity of Markov operators and rates of convergence of the distributions of the corresponding Markov chains. This provides a detailed characterization of the moments of the sequences beyond just the expected behavior. This also serves as a case study of how randomization restores favorable properties to algorithms that iterations of only partial information destroys. We demonstrate this on stochastic blockwise implementations of the forward\u2013backward and Douglas\u2013Rachford algorithms for nonconvex (and, as a special case, convex), nonsmooth optimization.<\/jats:p>","DOI":"10.1007\/s10107-024-02124-w","type":"journal-article","created":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T06:02:36Z","timestamp":1722060156000},"page":"763-798","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Convergence in distribution of randomized algorithms: the case of partially separable optimization"],"prefix":"10.1007","volume":"212","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4508-7360","authenticated-orcid":false,"given":"D. Russell","family":"Luke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,27]]},"reference":[{"key":"2124_CR1","volume-title":"Gradient flows in metric spaces and in the space of probability measures","author":"L Ambrosio","year":"2005","unstructured":"Ambrosio, L., Gigli, N., Savar\u00e9, G.: Gradient flows in metric spaces and in the space of probability measures, 1st edn. Birkh\u00e4user, Basel (2005)","edition":"1"},{"issue":"1","key":"2124_CR2","first-page":"1","volume":"4","author":"JB Baillon","year":"1978","unstructured":"Baillon, J.B., Bruck, R.E., Reich, S.: On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces. Houston J. Math. 4(1), 1\u20139 (1978)","journal-title":"Houston J. Math."},{"key":"2124_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF03007664","volume":"26","author":"J-B Baillon","year":"1977","unstructured":"Baillon, J.-B., Haddad, G.: Quelques propri\u00e9t\u00e9s des op\u00e9rateurs angle-bornes et n-cycliquement monotones. Isr. J. Math. 26, 137\u2013150 (1977)","journal-title":"Isr. J. Math."},{"key":"2124_CR4","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316962","volume-title":"Convergence of probability measures","author":"P Billingsley","year":"1999","unstructured":"Billingsley, P.: Convergence of probability measures, 2nd edn. Wiley, Chichester (1999)","edition":"2"},{"issue":"3","key":"2124_CR5","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s10589-019-00060-6","volume":"72","author":"Luis M Brice\u00f1o-Arias","year":"2019","unstructured":"Brice\u00f1o-Arias, Luis M., Chierchia, Giovanni, Chouzenoux, Emilie, Pesquet, Jean-Christophe.: A random block-coordinate Douglas-Rachford splitting method with low computational complexity for binary logistic regression. Comput. Optim. Appl. 72(3), 707\u2013726 (2019)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"2124_CR6","first-page":"459","volume":"3","author":"RE Bruck","year":"1977","unstructured":"Bruck, R.E., Reich, S.: Nonexpansive projections and resolvents of accretive operators in Banach spaces. Houston J. Math. 3(4), 459\u2013470 (1977)","journal-title":"Houston J. Math."},{"issue":"1","key":"2124_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1515\/JAA.1995.93","volume":"1","author":"D Butnariu","year":"1995","unstructured":"Butnariu, D.: The expected-projection method: its behavior and applications to linear operator equations and convex optimization. J. Appl. Anal. 1(1), 93\u2013108 (1995)","journal-title":"J. Appl. Anal."},{"key":"2124_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1023\/A:1008654413997","volume":"8","author":"D Butnariu","year":"1997","unstructured":"Butnariu, D., Censor, Y., Reich, S.: Iterative averaging of entropic projections for solving stochastic convex feasibility problems. Comput. Optim. Appl. 8, 21\u201339 (1997)","journal-title":"Comput. Optim. Appl."},{"issue":"5 &6","key":"2124_CR9","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1080\/01630569508816635","volume":"16","author":"D Butnariu","year":"1995","unstructured":"Butnariu, D., Fl\u00e5m, S.D.: Strong convergence of expected-projection methods in Hilbert spaces. Numer. Funct. Anal. and Optim. 16(5 &6), 601\u2013636 (1995)","journal-title":"Numer. Funct. Anal. and Optim."},{"issue":"2","key":"2124_CR10","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."},{"key":"2124_CR11","unstructured":"Eckstein, J.: Splitting Methods for Monotone Operators with Applications to Parallel Optimization. PhD thesis, MIT, Cambridge, MA, (1989)"},{"issue":"5","key":"2124_CR12","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2315474","volume":"73","author":"M Edelstein","year":"1966","unstructured":"Edelstein, M.: A remark on a theorem of M. A. Krasnoselski. Amer. Math. Mon. 73(5), 509\u2013510 (1966)","journal-title":"Amer. Math. Mon."},{"issue":"4","key":"2124_CR13","doi-asserted-by":"publisher","first-page":"1997","DOI":"10.1137\/130949993","volume":"25","author":"O Fercoq","year":"2015","unstructured":"Fercoq, O., Richt\u00e1rik, P.: Accelerated, parallel, and proximal coordinate descent. SIAM J. Optim. 25(4), 1997\u20132023 (2015)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2124_CR14","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/18M1168480","volume":"29","author":"Olivier Fercoq","year":"2019","unstructured":"Fercoq, Olivier, Bianchi, Pascal: A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions. SIAM J. Optim. 29(1), 100\u2013134 (2019)","journal-title":"SIAM J. Optim."},{"key":"2124_CR15","first-page":"299","volume-title":"Augmented Lagrangian methods: applications to the Solution of Boundary- Value Problems, chapter Applications of the method of multipliers to variational inequalities","author":"D Gabay","year":"1983","unstructured":"Gabay, D.: Augmented Lagrangian methods: applications to the Solution of Boundary- Value Problems, chapter Applications of the method of multipliers to variational inequalities, pp. 299\u2013331. North-Holland, Amsterdam (1983)"},{"issue":"R\u20132","key":"2124_CR16","first-page":"41","volume":"9","author":"R Glowinski","year":"1975","unstructured":"Glowinski, R., Marroco, A.: Sur l\u2019approximation, par elements finis d\u2019ordre un, et las resolution, par penalisation-dualit\u00e8, d\u2019une classe de problemes de dirichlet non lineares. Revue Francais d\u2019Automatique, Informatique et Recherche Op\u00e9rationelle 9(R\u20132), 41\u201376 (1975)","journal-title":"Revue Francais d\u2019Automatique, Informatique et Recherche Op\u00e9rationelle"},{"key":"2124_CR17","unstructured":"Hairer, M.: Convergence of Markov processes. Lecture notes, University of Warwick, p. 39 (2021)"},{"issue":"4","key":"2124_CR18","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1080\/01630563.2018.1535507","volume":"40","author":"N Hermer","year":"2019","unstructured":"Hermer, N., Luke, D.R., Sturm, A.: Random function iterations for consistent stochastic feasibility. Numer. Funct. Anal. Opt. 40(4), 386\u2013420 (2019)","journal-title":"Numer. Funct. Anal. Opt."},{"issue":"4","key":"2124_CR19","first-page":"1073","volume":"30","author":"N Hermer","year":"2023","unstructured":"Hermer, N., Luke, D.R., Sturm, A.: Nonexpansive Markov operators and random function iterations for stochastic fixed point problems. J. Conv. Anal. 30(4), 1073\u20131114 (2023)","journal-title":"J. Conv. Anal."},{"issue":"1","key":"2124_CR20","first-page":"tnad001, 12","volume":"7","author":"N Hermer","year":"2023","unstructured":"Hermer, N., Luke, D.R., Sturm, A.: Rates of convergence for chains of expansive Markov operators. Trans. Math. Appl. 7(1), tnad001, 12 (2023)","journal-title":"Trans. Math. Appl."},{"issue":"18","key":"2124_CR21","doi-asserted-by":"publisher","first-page":"4868","DOI":"10.1109\/TSP.2014.2339801","volume":"62","author":"R Hesse","year":"2014","unstructured":"Hesse, R., Luke, D.R., Neumann, P.: Alternating projections and Douglas-Rachford for sparse affine feasibility. IEEE Trans. Signal. Process. 62(18), 4868\u20134881 (2014)","journal-title":"IEEE Trans. Signal. Process."},{"key":"2124_CR22","unstructured":"Kartamyschew, I.: Random forward-backward algorithm in the context of random function iteration. Master\u2019s thesis, Universit\u00e4t G\u00f6ttingen (2020)"},{"issue":"1","key":"2124_CR23","first-page":"123","volume":"63","author":"MA Krasnoselski","year":"1955","unstructured":"Krasnoselski, M.A.: Two remarks on the method of successive approximations. Math. Nauk. (N.S.) 63(1), 123\u2013127 (1955). (Russian)","journal-title":"Math. Nauk. (N.S.)"},{"issue":"1\u20132(A)","key":"2124_CR24","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(A)), 615\u2013642 (2015)","journal-title":"Math. Program."},{"key":"2124_CR25","volume-title":"Distributed and Large-Scale Optimization","author":"DR Luke","year":"2018","unstructured":"Luke, D.R., Malitsky, Y.: Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints. In: Giselsson, P., Rantzer, A. (eds.) Distributed and Large-Scale Optimization. Springer Verlag, Cham (2018)"},{"issue":"3","key":"2124_CR26","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1137\/18M1193025","volume":"1","author":"DR Luke","year":"2019","unstructured":"Luke, D.R., Sabach, S., Teboulle, M.: Optimization on spheres: models and proximal algorithms with computational performance comparisons. SIAM J. Math. Data Sci. 1(3), 408\u2013445 (2019)","journal-title":"SIAM J. Math. Data Sci."},{"key":"2124_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-018-1343-8","volume":"180","author":"DR Luke","year":"2018","unstructured":"Luke, D.R., Teboulle, M., Thao, N.H.: Necessary conditions for linear convergence of iterated expansive, set-valued mappings. Math. Program. A 180, 1\u201331 (2018)","journal-title":"Math. Program. A"},{"issue":"4","key":"2124_CR28","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1287\/moor.2017.0898","volume":"43","author":"DR Luke","year":"2018","unstructured":"Luke, D.R., Thao, N.H., Tam, M.K.: Quantitative convergence analysis of iterated expansive, set-valued mappings. Math. Oper. Res. 43(4), 1143\u20131176 (2018)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"2124_CR29","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":"2124_CR30","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1090\/S0002-9939-1953-0054846-3","volume":"4","author":"WR Mann","year":"1953","unstructured":"Mann, W.R.: Mean value methods in iterations. Proc. Amer. Math. Soc. 4, 506\u2013510 (1953)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"3","key":"2124_CR31","doi-asserted-by":"publisher","first-page":"273","DOI":"10.24033\/bsmf.1625","volume":"93","author":"JJ Moreau","year":"1965","unstructured":"Moreau, J.J.: Proximit\u00e9 et dualit\u00e9 dans un espace Hilbertian. Bull. de la Soc. Math. de France 93(3), 273\u2013299 (1965)","journal-title":"Bull. de la Soc. Math. de France"},{"issue":"1","key":"2124_CR32","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1137\/130950288","volume":"26","author":"I Necoara","year":"2016","unstructured":"Necoara, I., Clipici, D.: Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds. SIAM J. Optim. 26(1), 197\u2013226 (2016)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2124_CR33","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-011-0468-9","volume":"129","author":"A Nedi\u0107","year":"2011","unstructured":"Nedi\u0107, A.: Random algorithms for convex minimization problems. Math. Program. 129(2), 225\u2013253 (2011)","journal-title":"Math. Program."},{"issue":"2","key":"2124_CR34","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Yu Nesterov","year":"2012","unstructured":"Nesterov, Yu.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"issue":"12","key":"2124_CR35","first-page":"2453","volume":"16","author":"J-C Pesquet","year":"2015","unstructured":"Pesquet, J.-C., Repetti, A.: A class of randomized primal-dual algorithms for distributed optimization. J. Nonlinear Convex Anal. 16(12), 2453\u20132490 (2015)","journal-title":"J. Nonlinear Convex Anal."},{"issue":"5","key":"2124_CR36","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1080\/10556788.2016.1190360","volume":"31","author":"Z Qu","year":"2016","unstructured":"Qu, Z., Richt\u00e1rik, P.: Coordinate descent with arbitrary sampling. I: Algorithms and complexity. Optim. Methods Softw. 31(5), 829\u2013857 (2016)","journal-title":"Optim. Methods Softw."},{"issue":"1\u20132(A)","key":"2124_CR37","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(A)), 1\u201338 (2014)","journal-title":"Math. Program."},{"issue":"75","key":"2124_CR38","first-page":"1","volume":"17","author":"P Richt\u00e1rik","year":"2016","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Distributed coordinate descent method for learning with big data. J. Mach. Learn. Res. 17(75), 1\u201325 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"2124_CR39","volume-title":"Variational Analysis","author":"RT Rockafellar","year":"2009","unstructured":"Rockafellar, R.T., Wets, R.J.: Variational Analysis, 3rd edn. Grundlehren Math. Wiss. Springer-Verlag, Berlin (2009)","edition":"3"},{"key":"2124_CR40","doi-asserted-by":"crossref","unstructured":"Salzo, S., Villa, S.: Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis. Math. Program., pp. 1436\u20134646 (2021)","DOI":"10.1007\/s10107-020-01602-1"},{"key":"2124_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974243","volume-title":"Probability Theory: an Analytic View","author":"DW Stroock","year":"2010","unstructured":"Stroock, D.W.: Probability Theory: an Analytic View. Cambridge University Press, Cambridge (2010)"},{"issue":"5","key":"2124_CR42","doi-asserted-by":"publisher","first-page":"1849","DOI":"10.1214\/009117906000000313","volume":"34","author":"T Szarek","year":"2006","unstructured":"Szarek, T.: Feller processes on nonlocally compact spaces. Ann. Probab. 34(5), 1849\u20131863 (2006)","journal-title":"Ann. Probab."},{"key":"2124_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71050-9","volume-title":"Optimal Transport: Old and New","author":"C Villani","year":"2009","unstructured":"Villani, C.: Optimal Transport: Old and New. Springer, Berlin (2009)"},{"issue":"1(B)","key":"2124_CR44","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(B)), 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-024-02124-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02124-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02124-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:03:02Z","timestamp":1750176182000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02124-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,27]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2124"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02124-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,27]]},"assertion":[{"value":"26 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no financial or non-financial interests that are directly or indirectly related to the work submitted for publication.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}