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

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.