Dong Gong
Home
Publications
Projects
Group
Services

Dong Gong

MPGL: An Efficient Matching Pursuit Method for Generalized LASSO

Dong Gong, Mingkui Tan, Yanning Zhang, Anton van den Hengel, Qinfeng Shi

framework 

Abstract

Unlike traditional LASSO enforcing sparsity on the variables, Generalized LASSO (GL) enforces sparsity on a linear transformation of the variables, gaining flexibility and success in many applications. However, many existing GL algorithms do not scale up to high-dimensional problems, and/or only work well for a specific choice of the transformation. We propose an efficient Matching Pursuit Generalized LASSO (MPGL) method, which overcomes these issues, and is guaranteed to converge to a global optimum. We formulate the GL problem as a convex quadratic constrained linear programming (QCLP) problem and tailor-make a cutting plane method. More specifically, our MPGL iteratively activates a subset of nonzero elements of the transformed variables, and solves a subproblem involving only the activated elements thus gaining significant speed-up. Moreover, MPGL is less sensitive to the choice of the trade-off hyper-parameter between data fitting and regularization, and mitigates the long-standing hyper-parameter tuning issue in many existing methods. Experiments demonstrate the superior efficiency and accuracy of the proposed method over the state-of-the-arts in both classification and image processing tasks.

Model

Classical Generalized LASSO Problem

framework 

Proposed Formulation with a Binary Indicator for Generalized LASSO

framework 

Proposed QCLP formulation for Generalized LASSO

framework 

Algorithm

MPGL for Solving the Generalized LASSO Problem in QCLP Formulation

framework 

Papers

Dong Gong, Mingkui Tan, Yanning Zhang, Anton van den Hengel, Qinfeng Shi. MPGL: An Efficient Matching Pursuit Method for Generalized LASSO. In Thirty-First AAAI Conference on Artificial Intelligence (AAAI), 2017.

[Paper] [Supp]

Code

[Github] [Code]

*Accessing the code via the Github project page is recommended.

Bibtex

@inproceedings{gong2017mpgl,
  title={MPGL: An Efficient Matching Pursuit Method for Generalized LASSO},
  author={Gong, Dong and Tan, Mingkui and Zhang, Yanning and van den Hengel, Anton and Shi, Qinfeng},
  booktitle={AAAI Conference on Artificial Intelligence},
  year={2017}
}

Our Related Work