Block-proximal methods with spatially adapted acceleration
This work provides a theoretical and algorithmic framework for accelerating block-coordinate methods in convex optimization, benefiting practitioners in image processing and related fields.
The authors develop block-coordinate primal-dual methods with spatially adapted acceleration, achieving convergence rates of O(1/N^2) for strongly convex blocks and O(1/N) otherwise. Experiments on image processing problems demonstrate practical effectiveness.
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: $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.