{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:28:37Z","timestamp":1792787317801,"version":"4.5.0"},"reference-count":55,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Cantab Capital Institute for the Mathematics of Information"},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-12-IS01-0003"],"award-info":[{"award-number":["ANR-12-IS01-0003"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012338","name":"Alan Turing Institute","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012338","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M00483X\/1"],"award-info":[{"award-number":["EP\/M00483X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N014588\/1"],"award-info":[{"award-number":["EP\/N014588\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N005538\/1"],"award-info":[{"award-number":["EP\/N005538\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We propose a stochastic extension of the primal-dual hybrid gradient algorithm studied by Chambolle and Pock in 2011 to solve saddle point problems that are separable in the dual variable. The analysis is carried out for general convex-concave saddle point problems and problems that are either partially smooth, strongly convex or fully smooth, strongly convex. We perform the analysis for arbitrary samplings of dual variables, and we obtain known deterministic results as a special case. Several variants of our stochastic method significantly outperform the deterministic variant on a variety of imaging tasks.<\/jats:p>","DOI":"10.1137\/17m1134834","type":"journal-article","created":{"date-parts":[[2018,10,2]],"date-time":"2018-10-02T13:36:37Z","timestamp":1538487397000},"page":"2783-2808","source":"Crossref","is-referenced-by-count":134,"title":["Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications"],"prefix":"10.1137","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9465-4659","authenticated-orcid":true,"given":"Antonin","family":"Chambolle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthias J.","family":"Ehrhardt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Richt\u00e1rik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carola-Bibiane","family":"Sch\u00f6nlieb","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,10,2]]},"reference":[{"key":"atypb1","unstructured":"J. Adler, H. Kohr, and O. \u00d6ktem,\n                      Operator Discretization Library (ODL)\n                      , 2017,https:\/\/github.com\/odlgroup\/odl."},{"key":"atypb2","unstructured":"Z. Allen-Zhu, Y. Yuan, P. Richt\u00e1rik, and Y. Yuan,\n                      Even faster accelerated coordinate descent using non-uniform sampling\n                      , in International Conference on Machine Learning, Proc. Mach. Learn. Res. 48, 2016; preprint available fromhttps:\/\/arxiv.org\/abs\/1512.09103."},{"key":"atypb3","unstructured":"P. Balamurugan and F. Bach,\n                      Stochastic variance reduction methods for saddle-point problems\n                      , in Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS'16), 2016, pp. 1416-1424."},{"key":"atypb4","first-page":"27","volume":"4","author":"Bauschke H.","year":"1997","journal-title":"J. Convex Anal."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"H. H. Bauschke and P. L. Combettes,\n                      Convex Analysis and Monotone Operator Theory in Hilbert Spaces\n                      , Springer, 2011,https:\/\/doi.org\/10.1007\/978-1-4419-9467-7.","DOI":"10.1007\/978-1-4419-9467-7"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb7","unstructured":"M. Benning, C.B. Sch\u00f6nlieb, T. Valkonen, and V. Vla\u010di\u0107,\n                      Explorations on Anisotropic Regularisation of Dynamic Inverse Problems by Bilevel Optimisation\n                      , preprint,https:\/\/arxiv.org\/abs\/1602.01278, 2016."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"D. P. Bertsekas,\n                      Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey\n                      , in Optimization for Machine Learning, S. Sra, S. Nowozin, and S. J. Wright, eds., MIT Press, 2011, pp. 85-120.","DOI":"10.7551\/mitpress\/8996.003.0006"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0472-0"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/040615961"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/15M1023865"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1023\/B:JMIV.0000011325.36760.1e"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291600009X"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0957-3"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/140971233"},{"key":"atypb17","first-page":"674","volume":"37","author":"Csiba D.","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"atypb18","unstructured":"C. D. Dang and G. Lan,\n                      Randomized Methods for Saddle Point Computation\n                      , preprint,https:\/\/arxiv.org\/abs\/1409.8625, 2014."},{"key":"atypb19","first-page":"1646","author":"Defazio A.","year":"2014","journal-title":"Curran Associates"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/32\/11\/115014"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/09076934X"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2015.2409562"},{"key":"atypb23","unstructured":"O. Fercoq and P. Bianchi,\n                      A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions\n                      , preprint,https:\/\/arxiv.org\/abs\/1508.04625, 2015."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/130949993"},{"key":"atypb25","unstructured":"X. Gao, Y. Xu, and S. Zhang,\n                      Randomized Primal-Dual Proximal Block Coordinate Updates\n                      , preprint,https:\/\/arxiv.org\/abs\/1605.05969, 2016."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-016-0665-5"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2016.2564989"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2015.2505682"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"R. D. Kongskov, Y. Dong, and K. Knudsen,\n                      Directional Total Generalized Variation Regularization\n                      , preprint,https:\/\/arxiv.org\/abs\/1701.02675, 2017.","DOI":"10.1007\/978-3-319-58771-4_18"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/0716071"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499362111"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1109\/79.560323"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1561\/2400000003"},{"key":"atypb34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4310\/AMSA.2016.v1.n1.a2","volume":"1","author":"Peng Z.","year":"2016","journal-title":"Ann. Math. Sci. Appl."},{"key":"atypb35","unstructured":"J.C. Pesquet and A. Repetti,\n                      A Class of Randomized Primal-Dual Algorithms for Distributed Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1406.6404, 2015."},{"key":"atypb36","first-page":"1762","author":"Pock T.","year":"2011","journal-title":"Proceedings of the IEEE International Conference on Computer Vision"},{"key":"atypb37","first-page":"1133","author":"Pock T.","year":"2009","journal-title":"Proceedings of the IEEE International Conference on Computer Vision"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2016.1190360"},{"key":"atypb39","unstructured":"Z. Qu and P. Richt\u00e1rik,\n                      Quartz: Randomized dual coordinate ascent with arbitrary sampling\n                      , in Proceedings of the 28th International Conference on Neural Information Processing Systems, Volume 1, 2015, pp. 865-873."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0614-z"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0916-1"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0901-6"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/60\/5\/1741"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, 1970.","DOI":"10.1515\/9781400873173"},{"key":"atypb45","unstructured":"L. Rosasco and S. Villa,\n                      Stochastic Inertial Primal-Dual Algorithms\n                      , preprint,https:\/\/arxiv.org\/abs\/1507.00852v1, 2015."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1030-6"},{"key":"atypb47","first-page":"537","author":"Tak\u00e1c M.","year":"2013","journal-title":"Springer"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495294797"},{"key":"atypb49","unstructured":"T. Valkonen,\n                      Block-Proximal Methods with Spatially Adapted Acceleration\n                      , preprint,https:\/\/arxiv.org\/abs\/1609.07373, 2016."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1364\/OE.24.025129"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1016\/j.ultramic.2015.05.002"},{"key":"atypb52","unstructured":"M. Wen, S. Yue, Y. Tan, and J. Peng,\n                      A Randomized Inertial Primal-Dual Fixed Point Algorithm for Monotone Inclusions\n                      , preprint,https:\/\/arxiv.org\/abs\/1611.05142, 2016."},{"key":"atypb53","unstructured":"Y. Zhang and L. Xiao,\n                      Stochastic primal-dual coordinate method for regularized empirical risk minimization\n                      , in Proceedings of the 32nd International Conference on Machine Learning, 2015, pp. 1-34."},{"key":"atypb54","first-page":"46","volume":"32","author":"Zhong L. W.","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"atypb55","first-page":"643","author":"Zhu Z.","year":"2015","journal-title":"Springer"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1134834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:49Z","timestamp":1787338309000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1134834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1134834"],"URL":"https:\/\/doi.org\/10.1137\/17m1134834","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}