Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls

Zeyuan Allen-Zhu, Elad Hazan, Wei Hu +1

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…