Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
  Alternating Direction Method of Multipliers (ADMM) has become a widely used
optimization method for convex problems, particularly in the context of data
mining in which large optimization problems are often encountered. ADMM has
several desirable properties, including the ability to decompose large problems
into smaller tractable sub-problems and ease of parallelization, that are
essential in these scenarios. The most common form of ADMM is the two-block, in
which two sets of primal variables are updated alternatingly. Recent years have
seen advances in multi-block ADMM, which update more than two blocks of primal
variables sequentially. In this paper, we study the empirical question: {\em Is
two-block ADMM always comparable with sequential multi-block ADMM solving an
equivalent problem?} In the context of optimization problems arising in
multi-task learning, through a comprehensive set of experiments we surprisingly
show that multi-block ADMM consistently outperformed two-block ADMM on
optimization performance, and as a consequence on prediction performance,
across all datasets and for the entire range of dual step sizes. Our results
have an important practical implication: rather than simply using the popular
two-block ADMM, one may considerably benefit from experimenting with
multi-block ADMM applied to an equivalent problem.
