Inexact Accelerated Proximal Gradient Algorithms For Matrix l_{2,1}-Norm Minimization Problem in Multi-Task Feature Learning
Abstract
In this paper, we extend the APG method to solve matrix l_{2,1}-norm minimization problem in multi-task feature learning. We investigate that the resulting inner subproblem has closed-form solution which can be easily determined by taking the problem's favorable structures. Under suitable conditions, we can establish a comprehensive convergence result for the proposed method. Furthermore, we present three different inexact APG algorithms by using the Lipschitz constant, the eigenvalue of Hessian matrix and the Barzilai and Borwein parameter in the inexact model, respectively. Numerical experiments on simulated data and real data set are reported to show the efficiency of proposed method.References
A. Argyriou, T. Evgeniou and M. Pontil, Convex multi-convex feature learning, Machine Learning, 73(2008), 243-272.
D.P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, New York: Academic Press, 1982.
J. Barzilai and J.M. Borwein, Two point step size gradient method, IMA Journal of Numerical Analysis, 8(1988), 141-148.
A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sciences, 2(2009), 183-202.
J. Duchi and Y. Singer, Efficient online and batch learning using forward backward splitting, Journal of Machine Learning Research, 10(2009), 2899-2934.
K. Jiang, D. Sun and K.C. Toh, An Inexact Accelerated Proximal Gradient Method for Large Scale
Linearly Constrained Convex SDP, SIAM Journal on Optimization, 22(2012), 1042-1064.
M. Kowalski, Sparse regression using mixednorms, Applied and Computational Harmonic Analysis, 27(2009), 303-324.
M. Kowalski, M. Szafranski and L. Ralaivola, Multiple Indefinite Kernel Learning with Mixed Norm regularization, Proceedings of the 26th Annual International Conference on Machine Learning, 2009.
J. Liu, S. Ji and J. Ye, Multi-Task Feather Learning Via Efficient l_2,1-norm Minimization, in Conference on Uncertainty in Artificial Intelligence, 2009.
Y. Nesterov, A method of solving a convex programming problem with convergence rate O(1/k2), Soviet Mathematics Doklady, 27(1983), 372-376.
Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE report, 2007.
F. Nie, H. Huang, X. Cai and C. Ding, Efficient and Robust Feature Selection via Joint l2;1-Norms minimization, Neural Information Processing Systems Foundation, 2010.
G. Obozinski, B. Taskar and M. I. Jordan, Multi-Task Feature Selection, Technical Report, UC Berkeley, 2006.
M. Raydan, On the Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, IMA Journal of Numerical Analysis, 13(1993), 321-326.
M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 7(1997),26-33.
Y. Saeys, I. Inza and P. Larranaga, A review of feature selection techniques in bioinformatics, Bioinformatics, 23(2007), 2507-2517.
Z. Shen, K.C. Toh, and S. Yun, An Accelerated Proximal Gradient Algorithm for Frame-Based
Image Restoration via the Balanced Approach, SIAM Journal on Imaging Sciences, 4(2011),
-596.
K.C. Toh and S.W. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pacific Journal of Optimization, 6(2010), 615-640.
Y. Xiao, S. Wu and B. He, A proximal alternating direction method for l_2,1-norm least squares problem in multi-task feature learning, Journal of Industrial and Management Optimization, 8(2012), 1057-1069.
G. Yuan and Z. Wei, The Barzilai and Borwein gradient method with nonmonotone line search for nonsmooth convex optimization problems, Math. Model. Anal., 17(2012), 203-216.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
