TY - GEN
T1 - Efficient generalized conditional gradient with gradient sliding for composite optimization
AU - CHEUNG, Yiu Ming
AU - Lou, Jian
N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2015/7
Y1 - 2015/7
N2 - Generalized conditional gradient method has regained increasing research interest as an alternative to another popular proximal gradient method for sparse optimization problems. For particular tasks, its low computation cost of linear subproblem evaluation on each iteration leads to superior practical performance. However, the inferior iteration complexity incurs excess number of gradient evaluations, which can counteract the efficiency gained by solving low cost linear subproblem. In this paper, we therefore propose a novel algorithm that requires optimal graduate evaluations as proximal gradient. We also present a refined variant for a type of gauge regularized problem where approximation techniques are allowed to further accelerate linear subproblem computation. Experiments of CUR-like matrix factorization problem with group lasso penalty on four real-world datasets demonstrate the efficiency of the proposed method.
AB - Generalized conditional gradient method has regained increasing research interest as an alternative to another popular proximal gradient method for sparse optimization problems. For particular tasks, its low computation cost of linear subproblem evaluation on each iteration leads to superior practical performance. However, the inferior iteration complexity incurs excess number of gradient evaluations, which can counteract the efficiency gained by solving low cost linear subproblem. In this paper, we therefore propose a novel algorithm that requires optimal graduate evaluations as proximal gradient. We also present a refined variant for a type of gauge regularized problem where approximation techniques are allowed to further accelerate linear subproblem computation. Experiments of CUR-like matrix factorization problem with group lasso penalty on four real-world datasets demonstrate the efficiency of the proposed method.
UR - https://www.ijcai.org/Abstract/15/480
UR - https://www.ijcai.org/proceedings/2015
UR - http://www.scopus.com/inward/record.url?scp=84949819099&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84949819099
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 3409
EP - 3415
BT - IJCAI 2015 - Proceedings of the 24th International Joint Conference on Artificial Intelligence
A2 - Wooldridge, Michael
A2 - Yang, Qiang
PB - International Joint Conferences on Artificial Intelligence
T2 - 24th International Joint Conference on Artificial Intelligence, IJCAI 2015
Y2 - 25 July 2015 through 31 July 2015
ER -