Frank-Wolfe Algorithms for Saddle Point Problems.



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.


[paper] [arXiv]


  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} 


[github] [zip]


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.