Stochastic Primal Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes

Antonin Chambolle (1, 2) , Claire Delplancke (3) , Matthias J Ehrhardt (4) , Carola-Bibiane Schönlieb (5) , Junqi Tang (5)

1 CEREMADE - CEntre de REcherches en MAthématiques de la DEcision
2 MOKAPLAN - Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales
3 EDF R&D - EDF R&D
4 Department of Mathematical Sciences [Bath]
5 DAMTP - Department of Applied Mathematics and Theoretical Physics [Cambridge]

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. Upto-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 parametersupdating 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.

Domaines: Mathématiques [math]

Antonin Chambolle, Claire Delplancke, Matthias J Ehrhardt, Carola-Bibiane Schönlieb, Junqi Tang. Stochastic Primal Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes. 2023. ⟨hal-03927644v1⟩