Title: Asynchronous parallel primal-dual block update methods,
Abstract: Recent several years have witnessed the surge of asynchronous (async-)
parallel computing methods due to the extremely big data involved in many
modern applications and also the advancement of multi-core machines and
computer clusters. In optimization, most works about async-parallel methods are
on unconstrained problems or those with block separable constraints.
In this paper, we propose an async-parallel method based on block coordinate
update (BCU) for solving convex problems with nonseparable linear constraint.
Running on a single node, the method becomes a novel randomized primal-dual BCU
with adaptive stepsize for multi-block affinely constrained problems. For these
problems, Gauss-Seidel cyclic primal-dual BCU needs strong convexity to have
convergence. On the contrary, merely assuming convexity, we show that the
objective value sequence generated by the proposed algorithm converges in
probability to the optimal value and also the constraint residual to zero. In
addition, we establish an ergodic $O(1/k)$ convergence result, where $k$ is the
number of iterations. Numerical experiments are performed to demonstrate the
efficiency of the proposed method and significantly better speed-up performance
than its sync-parallel counterpart.