Frank-Wolfe Algorithms for Saddle Point Problems

Gauthier Gidel, Tony Jebara, Simon Lacoste-Julien
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:362-371, 2017.

Abstract

We extend the Frank-Wolfe (FW) optimization algorithm to solve constrained smooth convex-concave saddle point (SP) problems. Remarkably, the method only requires access to linear minimization oracles. Leveraging recent advances in FW optimization, we provide the first proof of convergence of a FW-type saddle point solver over polytopes, thereby partially answering a 30 year-old conjecture. We also survey other convergence results and highlight gaps in the theoretical underpinnings of FW-style algorithms. Motivating applications without known efficient alternatives are explored through structured prediction with combinatorial penalties as well as games over matching polytopes involving an exponential number of constraints.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-gidel17a, title = {{Frank-Wolfe Algorithms for Saddle Point Problems}}, author = {Gidel, Gauthier and Jebara, Tony and Lacoste-Julien, Simon}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {362--371}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/gidel17a/gidel17a.pdf}, url = {https://proceedings.mlr.press/v54/gidel17a.html}, abstract = {We extend the Frank-Wolfe (FW) optimization algorithm to solve constrained smooth convex-concave saddle point (SP) problems. Remarkably, the method only requires access to linear minimization oracles. Leveraging recent advances in FW optimization, we provide the first proof of convergence of a FW-type saddle point solver over polytopes, thereby partially answering a 30 year-old conjecture. We also survey other convergence results and highlight gaps in the theoretical underpinnings of FW-style algorithms. Motivating applications without known efficient alternatives are explored through structured prediction with combinatorial penalties as well as games over matching polytopes involving an exponential number of constraints.} }
Endnote
%0 Conference Paper %T Frank-Wolfe Algorithms for Saddle Point Problems %A Gauthier Gidel %A Tony Jebara %A Simon Lacoste-Julien %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-gidel17a %I PMLR %P 362--371 %U https://proceedings.mlr.press/v54/gidel17a.html %V 54 %X We extend the Frank-Wolfe (FW) optimization algorithm to solve constrained smooth convex-concave saddle point (SP) problems. Remarkably, the method only requires access to linear minimization oracles. Leveraging recent advances in FW optimization, we provide the first proof of convergence of a FW-type saddle point solver over polytopes, thereby partially answering a 30 year-old conjecture. We also survey other convergence results and highlight gaps in the theoretical underpinnings of FW-style algorithms. Motivating applications without known efficient alternatives are explored through structured prediction with combinatorial penalties as well as games over matching polytopes involving an exponential number of constraints.
APA
Gidel, G., Jebara, T. & Lacoste-Julien, S.. (2017). Frank-Wolfe Algorithms for Saddle Point Problems. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:362-371 Available from https://proceedings.mlr.press/v54/gidel17a.html.

Related Material