Title: Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization,
Abstract: Block Coordinate Update (BCU) methods enjoy low per-update computational
complexity because every time only one or a few block variables would need to
be updated among possibly a large number of blocks. They are also easily
parallelized and thus have been particularly popular for solving problems
involving large-scale dataset and/or variables. In this paper, we propose a
primal-dual BCU method for solving linearly constrained convex program in
multi-block variables. The method is an accelerated version of a primal-dual
algorithm proposed by the authors, which applies randomization in selecting
block variables to update and establishes an $O(1/t)$ convergence rate under
weak convexity assumption. We show that the rate can be accelerated to
$O(1/t^2)$ if the objective is strongly convex. In addition, if one block
variable is independent of the others in the objective, we then show that the
algorithm can be modified to achieve a linear rate of convergence. The
numerical experiments show that the accelerated method performs stably with a
single set of parameters while the original method needs to tune the parameters
for different datasets in order to achieve a comparable level of performance.