Block-proximal methods with spatially adapted acceleration

Valkonen, Tuomo ORCID: 0000-0001-6683-3572 (2016) Block-proximal methods with spatially adapted acceleration. ETNA - Electronic Transactions on Numerical Analysis, 51. pp. 15-49.

Text 1609.07373v2.pdf - Submitted version Download (4MB)

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.

Item Type:	Article
Uncontrolled Keywords:	math.OC, math.OC, cs.NA
Depositing User:	Symplectic Admin
Date Deposited:	26 Apr 2017 08:09
Last Modified:	19 Jan 2023 07:27
DOI:	10.1553/etna_vol51s15
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004008