# Block-proximal methods with spatially adapted acceleration

arXiv: https://arxiv.org/abs/1609.07373 · HTML: https://mlsanity.com/paper/1609.07373/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2016.

## Built on by (most cited first, 1 of 1)

- [Accelerated nonlinear primal-dual hybrid gradient methods with applications to supervised machine learning](https://mlsanity.com/paper/2109.12222/) (2021)

## Abstract (arXiv)

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/N2) if each block is strongly convex, O(1/N) if no convexity is present, and more generally a mixed rate O(1/N2)+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.