Practical Acceleration of the Condat–Vũ Algorithm

Authors:
Publisher website
Google Scholar
Abstract
The Condat–Vũ 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ũ, 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–Vũ algorithm allows it to recover accelerated PGD (APGD) as a special case, instead of PGD. We prove that this accelerated Condat–Vũ algorithm achieves optimal convergence rates and significantly outperforms the traditional Condat–Vũ algorithm in regimes where the Condat–Vũ algorithm approximates the dynamics of PGD. We demonstrate the effectiveness of our approach in various applications in machine learning and computational imaging.
Funding Information
  • H2020 Marie Skłodowska-Curie Actions (777826)
  • Gates Cambridge Trust
  • Leverhulme Trust (ECF-2019-478)
  • Engineering and Physical Sciences Research Council (EP/S026045/1, EP/T026693/1, EP/V026259/1)
  • Engineering and Physical Sciences Research Council (EP/S026045/1, EP/T003553/1, EP/N014588/1, EP/T017961/1)
  • Wellcome (RG98755)

This publication has 28 references indexed in Scilit: