{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:38:45Z","timestamp":1787323125379,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["777826"],"award-info":[{"award-number":["777826"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005370","name":"Gates Cambridge Trust","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005370","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["ECF-2019-478"],"award-info":[{"award-number":["ECF-2019-478"]}],"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\/S026045\/1"],"award-info":[{"award-number":["EP\/S026045\/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\/T026693\/1"],"award-info":[{"award-number":["EP\/T026693\/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\/V026259\/1"],"award-info":[{"award-number":["EP\/V026259\/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\/S026045\/1"],"award-info":[{"award-number":["EP\/S026045\/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\/T003553\/1"],"award-info":[{"award-number":["EP\/T003553\/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\/T017961\/1"],"award-info":[{"award-number":["EP\/T017961\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004440","name":"Wellcome Trust","doi-asserted-by":"publisher","award":["RG98755"],"award-info":[{"award-number":["RG98755"]}],"id":[{"id":"10.13039\/100004440","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The Condat\u2013V\u0169 algorithm is a widely used primal-dual method for optimizing composite objectives of three functions. Several algorithms for optimizing composite objectives of two functions are special cases of Condat\u2013V\u0169, including proximal gradient descent (PGD). It is well known that PGD exhibits suboptimal performance, and a simple adjustment to PGD can accelerate its convergence rate from [Formula: see text] to [Formula: see text] on convex objectives, and this accelerated rate is optimal. In this work, we show that a simple adjustment to the Condat\u2013V\u0169 algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat\u2013V\u0169 algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat\u2013V\u0169 algorithm in regimes where the Condat\u2013V\u0169 algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.<\/jats:p>","DOI":"10.1137\/23m159473x","type":"journal-article","created":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T04:00:49Z","timestamp":1728964849000},"page":"2076-2109","source":"Crossref","is-referenced-by-count":3,"title":["Practical Acceleration of the Condat\u2013V\u0169 Algorithm"],"prefix":"10.1137","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1582-5884","authenticated-orcid":true,"given":"Derek","family":"Driggs","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, CB3 0WA, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8523-353X","authenticated-orcid":true,"given":"Matthias J.","family":"Ehrhardt","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, University of Bath, Bath, BA2 7AY, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carola-Bibiane","family":"Sch\u00f6nlieb","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, CB3 0WA, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4996-6079","authenticated-orcid":true,"given":"Junqi","family":"Tang","sequence":"additional","affiliation":[{"name":"Corresponding author.\u00a0School of Mathematics, University of Birmingham, Birmingham, B15 2TT, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,10,15]]},"reference":[{"key":"ref1","unstructured":"Z. Allen-Zhu and L. Orecchia, Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent, preprint, arXiv:1407.1537, 2016."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/22M1504305"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(67)90040-7"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-015-0746-4"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291600009X"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0957-3"},{"key":"ref9","first-page":"1","volume":"1","author":"Chen P.","year":"2016","journal-title":"Fixed Point Theory Appl."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/130919362"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9569-8_10"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s11228-011-0191-y"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/050626090"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-012-0245-9"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/20M1379344"},{"key":"ref16","unstructured":"L. Condat and P. Richt\u00e1rik, RandProx: Primal-dual optimization algorithms with randomized proximal updates, in Proceedings of International Conference on Learning Representations (ICLR) 2023, ICLR, 2023, pp. 1\u201327."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.02.001"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"ref19","first-page":"315","volume-title":"Advances in Neural Information Processing Systems 26","author":"Johnson R.","year":"2013"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01643-0"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/28\/11\/115005"},{"key":"ref22","unstructured":"A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, New York, 1983."},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0629-5"},{"key":"ref25","unstructured":"H. Ouyang, N. He, L. Q. Tran, and A. Gray, Stochastic alternating direction method of multipliers, in Proceedings of the 30th International Conference on Machine Learning, PMLR 28, 2013, pp. 80\u201388."},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"Y. Ouyang and Y. Xu, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Math. Program.Ser A, 185 (2021), pp. 1\u201335.","DOI":"10.1007\/s10107-019-01420-0"},{"key":"ref27","unstructured":"J. Park and E. K. Ryu, Exact optimal accelerated complexity for fixed-point iterations, in Proceedings of the 39th International Conference on Machine Learning, Baltimore, MD, PMLR 162, 2022, pp. 17420\u201317457."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp218"},{"key":"ref29","unstructured":"A. Salim, L. Condat, D. Kovalev, and P. Richt\u00e1rik, An optimal algorithm for strongly convex minimization under affine constraints, in Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), Valencia, Spain, PMLR 151, pp. 4482\u20134498."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-022-02061-8"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2005.00490.x"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-011-9254-8"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-018-0680-3"},{"key":"ref35","unstructured":"T. Yoon and E. K. Ryu, Accelerated algorithms for smooth convex-concave minimax problems with \\(O(1\/k^2)\\) rate on squared gradient norm, in Proceedings of the 28th International Conference on Machine Learning, PMLR 139, 2021, pp. 12098\u201312109."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1175"},{"key":"ref37","unstructured":"R. Zhao, W. B. Haskell, and V. Y. F. Tan, An optimal algorithm for stochastic three-composite optimization, in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), Naha, Okinawa, Japan. PMLR: Volume 89, 2019, pp. 428\u2013437."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2005.00503.x"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M159473X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:43:23Z","timestamp":1787319803000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M159473X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,15]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/23M159473X"],"URL":"https:\/\/doi.org\/10.1137\/23m159473x","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,15]]}}}