Volume 51, pp. 15-49, 2019.

Block-proximal methods with spatially adapted acceleration

Tuomo Valkonen

Abstract

We study and develop (stochastic) primal-dual block-coordinate descent methods for convex problems based on the method due to Chambolle and Pock. Our methods have known convergence rates for the iterates and the ergodic gap of $O(1/N^2)$ if each block is strongly convex, $O(1/N)$ if no convexity is present, and more generally a mixed rate $O(1/N^2)+O(1/N)$ for strongly convex blocks if only some blocks are strongly convex. Additional novelties of our methods include blockwise-adapted step lengths and acceleration as well as the ability to update both the primal and dual variables randomly in blocks under a very light compatibility condition. In other words, these variants of our methods are doubly-stochastic. We test the proposed methods on various image processing problems, where we employ pixelwise-adapted acceleration.

Full Text (PDF) [2.6 MB], BibTeX

Key words

PDHGM, Chambolle–Pock method, stochastic, doubly-stochastic, blockwise, primal-dual

AMS subject classifications

49M29, 65K10, 65K15, 90C30, 90C47

ETNA articles which cite this article

Vol. 52 (2020), pp. 509-552 Stanislav Mazurenko, Jyrki Jauhiainen, and Tuomo Valkonen: Primal-dual block-proximal splitting for a class of non-convex problems

< Back