  We propose a variant of the Frank-Wolfe algorithm for solving a class of
sparse/low-rank optimization problems. Our formulation includes Elastic Net,
regularized SVMs and phase retrieval as special cases. The proposed Primal-Dual
Block Frank-Wolfe algorithm reduces the per-iteration cost while maintaining
linear convergence rate. The per iteration cost of our method depends on the
structural complexity of the solution (i.e. sparsity/low-rank) instead of the
ambient dimension. We empirically show that our algorithm outperforms the
state-of-the-art methods on (multi-class) classification tasks.
