Block-proximal methods with spatially adapted acceleration

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: $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.

References in corpus (6)

• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Local Linear Convergence of Forward-Backward under Partial Smoothness
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Testing and non-linear preconditioning of the proximal point method
• iPiano: Inertial Proximal Algorithm for Non-Convex Optimization

Cited by in corpus (8)

• Relaxed Gauss-Newton methods with applications to electrical impedance tomography
• Acceleration and global convergence of a first-order primal--dual method for nonconvex problems
• Non-planar sensing skins for structural health monitoring based on electrical resistance tomography
• Testing and non-linear preconditioning of the proximal point method
• Inertial, corrected, primal-dual proximal splitting
• First-order primal-dual methods for nonsmooth nonconvex optimisation
• Primal-dual block-proximal splitting for a class of non-convex problems
• Introduction to Nonsmooth Analysis and Optimization