Accelerated Parallelizable Projection-Free Algorithm for the Nuclear-Norm Ball Constraint


We consider smooth convex optimization over the nuclear norm ball constraint. The classical algorithm for solving this class of problems is the Frank-Wolfe method, which only needs a top eigenvector computation for its linear optimization oracle and hence avoids the expensive projection on the nuclear norm ball. However, the Frank-Wolfe method is known to have a slow $O(1/T)$ convergence rate and is notoriously hard to accelerate for the nuclear norm ball problem. In this paper, we propose an accelerated projection-free algorithm which can achieve a faster convergence rate and avoids the expensive projection that requires a full matrix decomposition. Our method relies on a different oracle from the linear optimization oracle of Frank-Wolfe, which avoids an existing lower bound result for algorithms that rely on the linear optimization oracle. Still, the cost of our oracle is similar to the cost of the linear optimization oracle of Frank-Wolfe. Furthermore, the calls to the oracle in our method are easily parallelizable and consequently another level of acceleration can be achieved by exploiting multiple computational resources, while parallelization of the calls to the oracle remains an obstacle to the Frank-Wolfe method.

in submission