Primal-Dual Block Frank-Wolfe | Center for Big Data Analytics

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.

Download: pdf

Citation

Primal-Dual Block Frank-Wolfe (pdf, software)
Q. Lei, J. Zhuo, I. Dhillon, C. Caramanis, A. Dimakis.
To appear in Neural Information Processing Systems (NIPS), 2019.

Bibtex:
@inproceedings{lei2019primaldua, author = "Qi Lei AND Jiacheng Zhuo AND Inderjit S. Dhillon AND Constantine Caramanis AND Alexandros G. Dimakis", title = "Primal-Dual Block Frank-Wolfe", booktitle = "Neural Information Processing Systems (NIPS)", year = "2019", 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." }