  Block coordinate descent (BCD) methods are widely used for large-scale
numerical optimization because of their cheap iteration costs, low memory
requirements, amenability to parallelization, and ability to exploit problem
structure. Three main algorithmic choices influence the performance of BCD
methods: the block partitioning strategy, the block selection rule, and the
block update rule. In this paper we explore all three of these building blocks
and propose variations for each that can significantly improve the progress
made by each BCD iteration. We (i) propose new greedy block-selection
strategies that guarantee more progress per iteration than the Gauss-Southwell
rule; (ii) explore practical issues like how to implement the new rules when
using "variable" blocks; (iii) explore the use of message-passing to compute
matrix or Newton updates efficiently on huge blocks for problems with sparse
dependencies between variables; and (iv) consider optimal active manifold
identification, which leads to bounds on the "active-set complexity" of BCD
methods and leads to superlinear convergence for certain problems with sparse
solutions (and in some cases finite termination at an optimal solution). We
support all of our findings with numerical results for the classic machine
learning problems of least squares, logistic regression, multi-class logistic
regression, label propagation, and L1-regularization.
