Title: Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls,
Abstract: 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.