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.
---- After the rebuttal ----
I cannot help but notice some similarities of this method and the CLASH method in the vector case:
https://arxiv.org/pdf/1203.2936.pdf
The CLASH authors in effect make a projection onto the rank-k ball (corresponding to Combinatorial part in the CLASH method), followed by the projection onto the rank constraint (Least Absolute SHrinkage part). The latter is now a vector problem thanks to the affine invariance of the Frobenius norm in this paper. The authors in the CLASH work on the vector case directly; however, as opposed to performing the simple shrinkage update as in this paper, the CLASH authors actually solve the "fully corrective problem." Perhaps, this would be of interest to the authors.
-----
The main idea of this paper is based on a simple observation: injecting a rank-k constraint into the subproblem in PGD does not affect 
the convergence rate, as soon as the solution rank is less than or equal to k. This simple observation however leads to an algorithm with linear convergence rate that possess the benefits of FW method: low per iteration computational cost and low-rank updates. Note however, from a purely mathematical standpoint, I would argue calling this method as a Frank-Wolfe variant, as the rigorous description of FW is composed of the computation of a search direction and the application of a linear minimization oracle, followed with an averaging step. This algorithm however is based on a nonconvex quadratic subproblem, but this subproblem can be solved with theoretical guarantees efficiently.
                                        
That would be interesting to see the practical implications of the results section 5 that bounds the rank of the decision variable. Did you try this variant with replacement step in some numerical experiments? I would suggest addition of these results into the appendix. Note that there is a particular recent research direction about the storage efficiency of FW variants, e.g. [1].
 
In the current version of the manuscript, theoretical guarantees hold only if the solution rank is less than or equal to the input rank k. In practice, however, the solution is not exactly low rank due to the presence of the noise and imperfections in tuning the constraint radius. It is approximately low rank with a fast decay in the spectrum. As far as I can see the proof still holds when solution X* is replaced with the best rank-k approximation of the solution [X*]_k (see e.g. the guarantees provided in [1]). This would impose theoretical guarantees when f(X*) – f([X*]_k) is small.
                                                                                                        
The numerical experiments fall short of satisfaction for the nips venue. All the experiments with real data are solved using the auto selection of k heuristic. It is not clear from the text if this heuristic still possesses the theoretical guarantees of the original variant where k is fixed in advance. Plots with #1-SVD computations at x axis are very useful to compare the performance in terms of the overall computational cost. However, I would still suggest adding some information about the k chosen at each iteration while solving the real data problems. It would be also interesting to see some practical evidence of what happens when the input rank k is chosen slightly less than the solution rank, or when the solution is not low rank but it has a fast decay in the singular value spectrum.
 
As noted in the paper, algorithm outperforms other convex competitors in the convergence rate when the constraint radius is small, but there is no significant advantage when the radius is large. This is an expected result as the smaller radius tempts a lower rank solution. However, it is not possible to deduct which values of the radius are practically reasonable in the experiments presented in the paper (i.e. which values of theta results in lower test error).
 [1] Yurtsever et.al. Sketchy decisions: Convex low-rank matrix optimization with optimal storage. AISTATS, 2017.