  In this paper we propose a randomized primal-dual proximal block coordinate
updating framework for a general multi-block convex optimization model with
coupled objective function and linear constraints. Assuming mere convexity, we
establish its $O(1/t)$ convergence rate in terms of the objective value and
feasibility measure. The framework includes several existing algorithms as
special cases such as a primal-dual method for bilinear saddle-point problems
(PD-S), the proximal Jacobian ADMM (Prox-JADMM) and a randomized variant of the
ADMM method for multi-block convex optimization. Our analysis recovers and/or
strengthens the convergence properties of several existing algorithms. For
example, for PD-S our result leads to the same order of convergence rate
without the previously assumed boundedness condition on the constraint sets,
and for Prox-JADMM the new result provides convergence rate in terms of the
objective value and the feasibility violation. It is well known that the
original ADMM may fail to converge when the number of blocks exceeds two. Our
result shows that if an appropriate randomization procedure is invoked to
select the updating blocks, then a sublinear rate of convergence in expectation
can be guaranteed for multi-block ADMM, without assuming any strong convexity.
The new approach is also extended to solve problems where only a stochastic
approximation of the (sub-)gradient of the objective is available, and we
establish an $O(1/\sqrt{t})$ convergence rate of the extended approach for
solving stochastic programming.
