Practical Acceleration of the Condat-Vũ Algorithm

Derek Driggs; Matthias J. Ehrhardt; Carola Bibiane Schönlieb; Junqi Tang

doi:10.1137/23M159473X

Practical Acceleration of the Condat-Vũ Algorithm

Derek Driggs, Matthias J. Ehrhardt, Carola Bibiane Schönlieb, Junqi Tang

Research output: Contribution to journal › Article › peer-review

38 Downloads (Pure)

Abstract

The Condat-V\~u 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-V\~u, 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 $\mathcal{O}(1/T)$ to $\mathcal{O}(1/T^2)$ on convex objectives, and this accelerated rate is optimal. In this work, we show that a simple adjustment to the Condat-V\~u algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat--V\~u algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat-V\~u algorithm in regimes where the Condat--V\~u algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.

Original language	English
Pages (from-to)	2076-2109
Number of pages	34
Journal	SIAM Journal on Imaging Sciences
Volume	17
Issue number	4
Early online date	15 Oct 2024
DOIs	https://doi.org/10.1137/23M159473X
Publication status	Published - 31 Dec 2024

Funding

The first author acknowledges support from the Gates Cambridge Trust. The second author acknowledges support from EPSRC (EP/S026045/1, EP/T026693/1, EP/V026259/1) and the Leverhulme Trust (ECF-2019-478). The third author acknowledges support from the Philip Leverhulme Prize; the Royal Society Wolfson Fellowship; the EPSRC advanced career fellowship EP/V029428/1; the EPSRC programme grant EP/V026259/1; the EPSRC grants EP/S026045/1, EP/T003553/1, EP/N014588/1, and EP/T017961/1; the Wellcome Innovator Awards 215733/Z/19/Z and 221633/Z/20/Z; the European Union Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement NoMADS and REMODEL; the Cantab Capital Institute for the Mathematics of Information, and the Alan Turing Institute. This research was also supported by the NIHR Cambridge Biomedical Research Centre (NIHR203312). The views expressed are those of the author(s) and not necessarily those of the NIHR or the Department of Health and Social Care

Keywords

convex optimization
optimal methods
primal-dual algorithms
saddle-point problems

ASJC Scopus subject areas

General Mathematics
Applied Mathematics

Access to Document

10.1137/23M159473X

2403.17100v1
Copyright © 2024 by SIAM. The final publication is available at SIAM Journal on Imaging Sciences via https://doi.org/10.1137/23M159473X
Accepted author manuscript, 1.26 MBLicence: CC BY

https://arxiv.org/abs/2403.17100v1

Cite this

@article{f6c1f8f54c5b46e39b98e025e08518c8,

title = "Practical Acceleration of the Condat-Vũ Algorithm",

abstract = "The Condat-V\~u 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-V\~u, 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 $\mathcal{O}(1/T)$ to $\mathcal{O}(1/T^2)$ on convex objectives, and this accelerated rate is optimal. In this work, we show that a simple adjustment to the Condat-V\~u algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat--V\~u algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat-V\~u algorithm in regimes where the Condat--V\~u algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.",

keywords = "convex optimization, optimal methods, primal-dual algorithms, saddle-point problems",

author = "Derek Driggs and Ehrhardt, {Matthias J.} and Sch{\"o}nlieb, {Carola Bibiane} and Junqi Tang",

year = "2024",

month = dec,

day = "31",

doi = "10.1137/23M159473X",

language = "English",

volume = "17",

pages = "2076--2109",

journal = "SIAM Journal on Imaging Sciences",

issn = "1936-4954",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Practical Acceleration of the Condat-Vũ Algorithm

AU - Driggs, Derek

AU - Ehrhardt, Matthias J.

AU - Schönlieb, Carola Bibiane

AU - Tang, Junqi

PY - 2024/12/31

Y1 - 2024/12/31

N2 - The Condat-V\~u 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-V\~u, 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 $\mathcal{O}(1/T)$ to $\mathcal{O}(1/T^2)$ on convex objectives, and this accelerated rate is optimal. In this work, we show that a simple adjustment to the Condat-V\~u algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat--V\~u algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat-V\~u algorithm in regimes where the Condat--V\~u algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.

AB - The Condat-V\~u 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-V\~u, 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 $\mathcal{O}(1/T)$ to $\mathcal{O}(1/T^2)$ on convex objectives, and this accelerated rate is optimal. In this work, we show that a simple adjustment to the Condat-V\~u algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat--V\~u algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat-V\~u algorithm in regimes where the Condat--V\~u algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.

KW - convex optimization

KW - optimal methods

KW - primal-dual algorithms

KW - saddle-point problems

UR - http://www.scopus.com/inward/record.url?scp=85209172047&partnerID=8YFLogxK

U2 - 10.1137/23M159473X

DO - 10.1137/23M159473X

M3 - Article

SN - 1936-4954

VL - 17

SP - 2076

EP - 2109

JO - SIAM Journal on Imaging Sciences

JF - SIAM Journal on Imaging Sciences

IS - 4

ER -

Practical Acceleration of the Condat-Vũ Algorithm

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this