Frank-Wolfe Algorithms for Saddle Point Problems
arXiv:1610.07797
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.
Appears in: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS 2017). 39 pages
References in corpus (2)
Cited by in corpus (11)
- Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
- Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control
- A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
- Understanding and Stabilizing GANs' Training Dynamics with Control Theory
- Saddle Point Optimization with Approximate Minimization Oracle
- A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
- A Max-Min Entropy Framework for Reinforcement Learning
- Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games
- Efficient Projection-Free Algorithms for Saddle Point Problems
- Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry
- Alternating Direction Method of Multipliers for Decomposable Saddle-Point Problems