MPGL: An efficient matching pursuit method for generalized LASSO
Date
2017
Authors
Gong, D.
Tan, M.
Zhang, Y.
Van Den Hengel, A.
Shi, Q.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the ... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence, 2017, pp.1934-1940
Statement of Responsibility
Dong Gong, Mingkui Tan, Yanning Zhang, Anton van den Hengel, Qinfeng Shi
Conference Name
31st AAAI Conference on Artificial Intelligence (AAAI-17) (4 Feb 2017 - 9 Feb 2017 : San Francisco)
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.