{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T16:04:54Z","timestamp":1793289894345,"version":"4.5.0"},"reference-count":55,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100003951","name":"Orange","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003951","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>This paper introduces a randomized coordinate-descent version of the Vu\u0342--Condat algorithm. By coordinate descent, we mean that only a subset of the coordinates of the primal and dual iterates is updated at each iteration, the other coordinates being maintained to their past value. Our method allows us to solve optimization problems with a combination of differentiable functions and constraints as well as nonseparable and nondifferentiable regularizers. We show that the sequences generated by our algorithm almost surely converge to a saddle point of the problem at stake, for a wider range of parameter values than previous methods. In particular, the condition on the step sizes depends on the coordinatewise Lipschitz constant of the differentiable function's gradient, which is a major feature allowing classical coordinate descent to perform so well when it is applicable. We then prove a sublinear rate of convergence in general and a linear rate of convergence if the objective enjoys strong convexity properties. We illustrate the performances of the algorithm on a total-variation regularized least squares regression problem and on large-scale support vector machine problems.<\/jats:p>","DOI":"10.1137\/18m1168480","type":"journal-article","created":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T15:47:29Z","timestamp":1546962449000},"page":"100-134","source":"Crossref","is-referenced-by-count":33,"title":["A Coordinate-Descent Primal-Dual Algorithm with Large Step Size and Possibly Nonseparable Functions"],"prefix":"10.1137","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3393-9757","authenticated-orcid":true,"given":"Olivier","family":"Fercoq","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pascal","family":"Bianchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,1,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012902407120"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/120887679"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0472-0"},{"key":"atypb5","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1989."},{"key":"atypb6","first-page":"1895","author":"Bianchi P.","year":"2016","journal-title":"NJ"},{"key":"atypb7","unstructured":"P. Bianchi, W. Hachem, and F. Iutzeler,\n                      A Stochastic Coordinate Descent Primal-Dual Algorithm and Applications to Large-Scale Composite Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1407.0898v1, 2014."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2014.2329397"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"A. Chambolle, V. Caselles, D. Cremers, M. Novaga, and T. Pock,\n                      An introduction to total variation for image analysis\n                      , in Theoretical Foundations and Numerical Methods for Sparse Recovery, Radon Series on Comput. Appl. Math. 9, 2010, Walter De Gruyter, Berlin, pp. 263-340.","DOI":"10.1515\/9783110226157.263"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-015-0746-4"},{"key":"atypb12","unstructured":"A. Chambolle, M. J. Ehrhardt, P. Richt\u00e1rik, and C.B. Sch\u00f6nlieb,\n                      Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Application\n                      , preprint,https:\/\/arxiv.org\/abs\/1706.04957, 2017."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0957-3"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/140971233"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-012-0245-9"},{"key":"atypb18","unstructured":"D. Davis and W. Yin,\n                      A Three-Operator Splitting Scheme and Its Optimization Applications\n                      , preprint,https:\/\/arxiv.org\/abs\/1504.01032, 2015."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0827"},{"key":"atypb20","doi-asserted-by":"publisher","unstructured":"E. Dohmatob, A. Gramfort, B. Thirion, and G. Varoquaux,\n                      Benchmarking solvers for TV-$\\ell_1$ least-squares and logistic regression in brain imaging\n                      , in Proceedings of the 2014 International Workshop on Pattern Recognition in Neuroimaging, IEEE Press, Piscataway, NJ, 2014, DOI: 10.1109\/PRNI.2014.6858516.","DOI":"10.1109\/PRNI.2014.6858516"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/130949993"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOAS131"},{"key":"atypb23","first-page":"299","author":"Gabay D.","year":"1983","journal-title":"New York"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"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.05969v1, 2016."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-016-0131-5"},{"key":"atypb27","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1051\/m2an\/197509R200411","volume":"9","author":"Glowinski R.","year":"1975","journal-title":"RAIRO Analyse Num\u00e9rique"},{"key":"atypb28","first-page":"1","volume":"7","author":"Guyon I.","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/100814494"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1057-8"},{"key":"atypb31","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, Cambridge, 2012."},{"key":"atypb32","first-page":"3671","author":"Iutzeler F.","year":"2013","journal-title":"NJ"},{"key":"atypb33","first-page":"361","volume":"5","author":"Lewis D. D.","year":"2004","journal-title":"J. Mach. Learn. Res."},{"key":"atypb34","first-page":"3059","author":"Lin Q.","year":"2014","journal-title":"NY"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939948"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/140957639"},{"key":"atypb37","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, Politehnica University of Bucharest, 2012.","DOI":"10.1007\/s10589-013-9598-8"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0686-4"},{"key":"atypb40","first-page":"2453","volume":"16","author":"Pesquet J.-C.","year":"2015","journal-title":"J. Nonlinear Convex Anal."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0614-z"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0901-6"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29210-1_5"},{"key":"atypb44","first-page":"233","author":"Robbins H.","year":"1971","journal-title":"New York"},{"key":"atypb45","first-page":"567","volume":"14","author":"Shalev-Shwartz S.","year":"2013","journal-title":"J. Mach. Learn. Res."},{"key":"atypb46","first-page":"736","volume":"32","author":"Suzuki T.","year":"2014","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb47","unstructured":"Q. Tran-Dinh and V. Cevher,\n                      A Primal-Dual Algorithmic Framework for Constrained Convex Minimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1406.5403v1, 2014."},{"key":"atypb48","unstructured":"Q. Tran-Dinh, O. Fercoq, and V. Cevher,\n                      A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1507.06243v4, 2016."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017501703105"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0170-0"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-008-9215-4"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-011-9254-8"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/0111043"},{"key":"atypb55","unstructured":"Y. Zhang and L. Xiao,\n                      Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1409.3257v1, 2014."},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1145\/279232.279236"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1168480","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:00Z","timestamp":1787337480000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1168480"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1168480"],"URL":"https:\/\/doi.org\/10.1137\/18m1168480","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}