Block-proximal methods with spatially adapted acceleration

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