Primal-Dual Block Frank-Wolfe

Abstract

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.

References in corpus (5)

• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Variance-Reduced and Projection-Free Stochastic Optimization
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• Efficient Greedy Coordinate Descent for Composite Problems