zbMATH — the first resource for mathematics

Block-proximal methods with spatially adapted acceleration. (English) Zbl 1420.49034
Summary: 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.

MSC:
 49M29 Numerical methods involving duality 65K10 Numerical optimization and variational techniques 65K15 Numerical methods for variational inequalities and related problems 90C30 Nonlinear programming 90C47 Minimax problems in mathematical programming
ARock; iPiano
Full Text: