Efficient Block-coordinate Descent Algorithms for the Group Lasso

We present two algorithms to solve the Group Lasso problem [Yuan & Lin]. First, we propose a general version of the Block Coordinate Descent (BCD) algorithm for the Group Lasso that employs an efficient approach for optimizing each subproblem. We show that it exhibits excellent performance when the groups are of moderate sizes. For large group sizes, we propose an extension of ISTA/FISTA [Beck & Teboulle] based on variable step-lengths that can be viewed as a simplified version of BCD. By combining the two approaches we obtain an implementation that significantly outperforms other state-of-the-art approaches for this problem. We show how these methods fit into a globally convergent general block coordinate gradient descent framework in [Tseng & Yun]. We also show that due to a difference in the step computation, the proposed approach is more efficient in practice than the one implemented in [Tseng & Yun]. In addition, we apply our algorithms to the Multiple Measurement Vector (MMV) recovery problem, which can be viewed as a special case of the Group Lasso problem, and compare their performance to other methods in this particular instance.



View Efficient Block-coordinate Descent Algorithms for the Group Lasso