Frank-Wolfe Algorithms for Saddle Point Problems

2016/10/25 by Gauthier Gidel, Gidel, Gauthier, Tony Jebara +3 · 6 citations
Computer Science · #Machine Learning and Algorithms #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation

paper · pdf · doi:10.48550/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.

Cited by

• A Frank-Wolfe Algorithm for Strongly Monotone Variational Inequalities
• Pure Exploration via Frank-Wolfe Self-Play
• Understanding and Stabilizing GANs' Training Dynamics with Control Theory
• Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for\n Smooth Minimax Games
• A Max-Min Entropy Framework for Reinforcement Learning
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization

Related

• One-sided Frank-Wolfe algorithms for saddle problems
• The Frank-Wolfe algorithm: a short introduction
• The Frank-Wolfe Algorithm: A Short Introduction
• kFW: A Frank-Wolfe style algorithm with stronger subproblem oracles
• On the Global Linear Convergence of Frank-Wolfe Optimization Variants