Frank-Wolfe Algorithms for Saddle Point Problems
Gauthier Gidel, Tony Jebara, Simon Lacoste-Julien
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.
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.}
}