Efficient Block-coordinate Descent Algorithms for the Group Lasso
Zhiwei (Tony) Qin (zq2107columbia.edu)
Abstract: 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.
Keywords: Group Lasso, group sparsity, block coordinate descent, iterative shrinkage thresholding, multiple measurement vector recovery, trust-region method.
Category 1: Convex and Nonsmooth Optimization
Entry Submitted: 11/10/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|