Poster
Primal-Dual Block Generalized Frank-Wolfe
Qi Lei · JIACHENG ZHUO · Constantine Caramanis · Inderjit S Dhillon · Alexandros Dimakis

Wed Dec 11th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #165
in Optimization -- Convex Optimization »

We propose a generalized variant of 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 Generalized 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.

Keywords: Algorithms -> Large Scale Learning · Algorithms -> Classification; Optimization -> Convex Optimization

Author Information

Qi Lei (University of Texas at Austin)
JIACHENG ZHUO (University of Texas at Austin)
Constantine Caramanis (UT Austin)
Inderjit S Dhillon (UT Austin & Amazon)
Alex Dimakis (University of Texas, Austin)

More from the Same Authors