Stochastic Primal-Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes

Antonin Chambolle; Claire Delplancke; Matthias J. Ehrhardt; Carola-Bibiane Schönlieb; Junqi Tang

doi:10.1007/s10851-024-01174-1

Stochastic Primal-Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes

Antonin Chambolle, Claire Delplancke, Matthias J. Ehrhardt, Carola-Bibiane Schönlieb, Junqi Tang

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

1 Citation (SciVal)

Abstract

In this work we propose a new primal-dual algorithm with adaptive step-sizes. The stochastic primal-dual hybrid gradient (SPDHG) algorithm with constant step-sizes has become widely applied in large-scale convex optimization across many scientific fields due to its scalability. While the product of the primal and dual step-sizes is subject to an upper-bound in order to ensure convergence, the selection of the ratio of the step-sizes is critical in applications. Up-to-now there is no systematic and successful way of selecting the primal and dual step-sizes for SPDHG. In this work, we propose a general class of adaptive SPDHG (A-SPDHG) algorithms, and prove their convergence under weak assumptions. We also propose concrete parameters-updating strategies which satisfy the assumptions of our theory and thereby lead to convergent algorithms. Numerical examples on computed tomography demonstrate the effectiveness of the proposed schemes.

Original language	English
Pages (from-to)	294-313
Number of pages	20
Journal	Journal of Mathematical Imaging and Vision
Volume	66
Issue number	3
Early online date	16 Mar 2024
DOIs	https://doi.org/10.1007/s10851-024-01174-1
Publication status	Published - 30 Jun 2024

Funding

CD acknowledges support from the EPSRC (EP/S026045/1). MJE acknowledges support from the EPSRC (EP/S026045/1, EP/T026693/1, EP/V026259/1) and the Leverhulme Trust (ECF-2019-478). CBS acknowledges support from the Philip Leverhulme Prize, the Royal Society Wolfson Fellowship, the EPSRC advanced career fellowship EP/V029428/1, EPSRC grants EP/S026045/1 and EP/T003553/1, EP/N014588/1, EP/T017961/1, the Wellcome Innovator Awards 215733/Z/19/Z and 221633/Z/20/Z, the European Union Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No. 777826 NoMADS, the Cantab Capital Institute for the Mathematics of Information and the Alan Turing Institute.

Funders	Funder number
Cantab Capital Institute for the Mathematics of Information
Alan Turing Institute
Horizon 2020
Leverhulme Trust	ECF-2019-478
Engineering and Physical Sciences Research Council	EP/V026259/1, EP/S026045/1, EP/T026693/1
Royal Society	EP/N014588/1, EP/T003553/1, EP/T017961/1, EP/V029428/1
H2020 Marie Skłodowska-Curie Actions	777826
The Wellcome Trust	215733/Z/19/Z, 221633/Z/20/Z

Keywords

math.OC
47N10, 49J40, 65D18, 65K10, 90C06, 90C15, 90C25, 92C55, 94A08

Access to Document

10.1007/s10851-024-01174-1Licence: CC BY

Cite this

@article{a189c631b3be4c459b8b09e7f2bb07de,

title = "Stochastic Primal-Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes",

abstract = "In this work we propose a new primal-dual algorithm with adaptive step-sizes. The stochastic primal-dual hybrid gradient (SPDHG) algorithm with constant step-sizes has become widely applied in large-scale convex optimization across many scientific fields due to its scalability. While the product of the primal and dual step-sizes is subject to an upper-bound in order to ensure convergence, the selection of the ratio of the step-sizes is critical in applications. Up-to-now there is no systematic and successful way of selecting the primal and dual step-sizes for SPDHG. In this work, we propose a general class of adaptive SPDHG (A-SPDHG) algorithms, and prove their convergence under weak assumptions. We also propose concrete parameters-updating strategies which satisfy the assumptions of our theory and thereby lead to convergent algorithms. Numerical examples on computed tomography demonstrate the effectiveness of the proposed schemes.",

keywords = "math.OC, 47N10, 49J40, 65D18, 65K10, 90C06, 90C15, 90C25, 92C55, 94A08",

author = "Antonin Chambolle and Claire Delplancke and Ehrhardt, {Matthias J.} and Carola-Bibiane Sch{\"o}nlieb and Junqi Tang",

year = "2024",

month = jun,

day = "30",

doi = "10.1007/s10851-024-01174-1",

language = "English",

volume = "66",

pages = "294--313",

journal = "Journal of Mathematical Imaging and Vision ",

issn = "0924-9907",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - Stochastic Primal-Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes

AU - Chambolle, Antonin

AU - Delplancke, Claire

AU - Ehrhardt, Matthias J.

AU - Schönlieb, Carola-Bibiane

AU - Tang, Junqi

PY - 2024/6/30

Y1 - 2024/6/30

N2 - In this work we propose a new primal-dual algorithm with adaptive step-sizes. The stochastic primal-dual hybrid gradient (SPDHG) algorithm with constant step-sizes has become widely applied in large-scale convex optimization across many scientific fields due to its scalability. While the product of the primal and dual step-sizes is subject to an upper-bound in order to ensure convergence, the selection of the ratio of the step-sizes is critical in applications. Up-to-now there is no systematic and successful way of selecting the primal and dual step-sizes for SPDHG. In this work, we propose a general class of adaptive SPDHG (A-SPDHG) algorithms, and prove their convergence under weak assumptions. We also propose concrete parameters-updating strategies which satisfy the assumptions of our theory and thereby lead to convergent algorithms. Numerical examples on computed tomography demonstrate the effectiveness of the proposed schemes.

AB - In this work we propose a new primal-dual algorithm with adaptive step-sizes. The stochastic primal-dual hybrid gradient (SPDHG) algorithm with constant step-sizes has become widely applied in large-scale convex optimization across many scientific fields due to its scalability. While the product of the primal and dual step-sizes is subject to an upper-bound in order to ensure convergence, the selection of the ratio of the step-sizes is critical in applications. Up-to-now there is no systematic and successful way of selecting the primal and dual step-sizes for SPDHG. In this work, we propose a general class of adaptive SPDHG (A-SPDHG) algorithms, and prove their convergence under weak assumptions. We also propose concrete parameters-updating strategies which satisfy the assumptions of our theory and thereby lead to convergent algorithms. Numerical examples on computed tomography demonstrate the effectiveness of the proposed schemes.

KW - math.OC

KW - 47N10, 49J40, 65D18, 65K10, 90C06, 90C15, 90C25, 92C55, 94A08

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

U2 - 10.1007/s10851-024-01174-1

DO - 10.1007/s10851-024-01174-1

M3 - Article

SN - 0924-9907

VL - 66

SP - 294

EP - 313

JO - Journal of Mathematical Imaging and Vision

JF - Journal of Mathematical Imaging and Vision

IS - 3

ER -

Stochastic Primal-Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this