Frank-Wolfe Algorithms for Saddle Point Problems

By Gauthier Gidel, Tony Jebara, Simon Lacoste-Julien. 2016

81 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Optimization & Training

Citations in the corpus

A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “To deal with unbounded constraint sets (leading to a potentially inﬁnite valued function outside of the optimal set), we use the restricted merit function (Nesterov, 2007): This function acts as merit function for (VIP) on the interior of the open ball of radius R around ω 0 , as shown in Lemma 1…”
Subspace Robust Wasserstein distances (2019, methodology): “Computations are greatly facilitated by adding smoothness, which allows the use of saddle point Frank-Wolfe algorithms (Gidel et al., 2017).”
Variance Reduction for Matrix Games (2019, background): “In recent years, minimax formulations for neural network training rose to prominence [14, 20], leading to intense interest in algorithms for solving large scale minimax games [10, 13, 18, 9, 16, 21].”
A Variational Inequality Perspective on Generative Adversarial Nets (2018, background): “It can be 0 for a non optimal point, see for instance the discussion on the differences between (12) and P in (Gidel et al., 2017, Section 3).”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, methodology): “In convex-concave games, such a Nash equilibrium always exists [28] and several algorithms were proposed to find Nash equilibria [23, 26].”