Primal-Dual Block Generalized Frank-Wolfe
Abstract
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.
Cite
Text
Lei et al. "Primal-Dual Block Generalized Frank-Wolfe." Neural Information Processing Systems, 2019.Markdown
[Lei et al. "Primal-Dual Block Generalized Frank-Wolfe." Neural Information Processing Systems, 2019.](https://mlanthology.org/neurips/2019/lei2019neurips-primaldual/)BibTeX
@inproceedings{lei2019neurips-primaldual,
title = {{Primal-Dual Block Generalized Frank-Wolfe}},
author = {Lei, Qi and Zhuo, Jiacheng and Caramanis, Constantine and Dhillon, Inderjit S and Dimakis, Alexandros G},
booktitle = {Neural Information Processing Systems},
year = {2019},
pages = {13866-13875},
url = {https://mlanthology.org/neurips/2019/lei2019neurips-primaldual/}
}