Approximate message-passing for convex optimization with non-separable penalties

2018/09/17 by Manoel, Andre, Krzakala, Florent, Varoquaux, Gaël +2 · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1809.06304

Abstract

We introduce an iterative optimization scheme for convex objectives consisting of a linear loss and a non-separable penalty, based on the expectation-consistent approximation and the vector approximate message-passing (VAMP) algorithm. Specifically, the penalties we approach are convex on a linear transformation of the variable to be determined, a notable example being total variation (TV). We describe the connection between message-passing algorithms -- typically used for approximate inference -- and proximal methods for optimization, and show that our scheme is, as VAMP, similar in nature to the Peaceman-Rachford splitting, with the important difference that stepsizes are set adaptively. Finally, we benchmark the performance of our VAMP-like iteration in problems where TV penalties are useful, namely classification in task fMRI and reconstruction in tomography, and show faster convergence than that of state-of-the-art approaches such as FISTA and ADMM in most settings.

Cited by

• Time-Embedded Algorithm Unrolling for Computational MRI

Related

• A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classification
• Convergence of Message-Passing for Distributed Convex Optimisation with Scaled Diagonal Dominance
• Convergence of Some Convex Message Passing Algorithms to a Fixed Point
• Convergence of the Min-Sum Algorithm for Convex Optimization
• Convergence of Min-Sum Message Passing for Quadratic Optimization