We extend the Frank-Wolfe (FW) optimization algorithm to solve constrained smooth convex-concave saddle point (SP) problems. The method only requires access to linear minimization oracles. Building on recent advances in FW opti- mization, 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 current gaps in the theoretical underpinnings of FW-style algorithms. Motivating applications are explored in- cluding structured prediction with combinatorial penalties as well as games over unipartite matching polytopes that require an exponential number of constraints.
@InProceedings{gidel2017saddle, author = {Gidel, Gauthier and Jebara, Tony and Lacoste-Julien, Simon}, title = {Frank-{W}olfe Algorithms for Saddle Point Problems}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS)}, year = {2017} }
This work was partially supported by a Google Research Award, DARPA N66001-15-2-4026, N66001-15-C-4032 and NSF III-1526914, IIS-1451500, CCF-1302269.