Optimization Online


Efficient Block-coordinate Descent Algorithms for the Group Lasso

Zhiwei (Tony) Qin (zq2107***at***columbia.edu)
Katya Scheinberg (katyas***at***lehigh.edu)
Donald Goldfarb (goldfarb***at***columbia.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


Download: [PDF]

Entry Submitted: 11/10/2010
Entry Accepted: 11/10/2010
Entry Last Modified: 02/27/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society