TY - JOUR
T1 - Linear convergence of a Frank-Wolfe type algorithm over trace-norm balls
AU - Allen-Zhu, Zeyuan
AU - Hazan, Elad
AU - Hu, Wei
AU - Li, Yuanzhi
N1 - Funding Information:
Elad Hazan was supported by NSF grant 1523815 and a Google research award. The authors would like to thank Dan Garber for sharing his code for [6].
Publisher Copyright:
© 2017 Neural information processing systems foundation. All rights reserved.
PY - 2017
Y1 - 2017
N2 - We propose a rank-k variant of the classical Frank-Wolfe algorithm to solve convex optimization over a trace-norm ball. Our algorithm replaces the top singular-vector computation (1-SVD) in Frank-Wolfe with a top-k singular-vector computation (k-SVD), which can be done by repeatedly applying 1-SVD k times. Alternatively, our algorithm can be viewed as a rank-k restricted version of projected gradient descent. We show that our algorithm has a linear convergence rate when the objective function is smooth and strongly convex, and the optimal solution has rank at most k. This improves the convergence rate and the total time complexity of the Frank-Wolfe method and its variants.
AB - We propose a rank-k variant of the classical Frank-Wolfe algorithm to solve convex optimization over a trace-norm ball. Our algorithm replaces the top singular-vector computation (1-SVD) in Frank-Wolfe with a top-k singular-vector computation (k-SVD), which can be done by repeatedly applying 1-SVD k times. Alternatively, our algorithm can be viewed as a rank-k restricted version of projected gradient descent. We show that our algorithm has a linear convergence rate when the objective function is smooth and strongly convex, and the optimal solution has rank at most k. This improves the convergence rate and the total time complexity of the Frank-Wolfe method and its variants.
UR - http://www.scopus.com/inward/record.url?scp=85047001701&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047001701&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85047001701
SN - 1049-5258
VL - 2017-December
SP - 6192
EP - 6201
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 31st Annual Conference on Neural Information Processing Systems, NIPS 2017
Y2 - 4 December 2017 through 9 December 2017
ER -