Frank-Wolfe Algorithms for Saddle Point Problems
This work addresses a theoretical gap in optimization for researchers, offering a novel approach to saddle point problems with applications in structured prediction and game theory, though it is incremental in extending an existing method.
The authors tackled the problem of solving constrained smooth convex-concave saddle point problems by extending the Frank-Wolfe algorithm, providing the first proof of convergence over polytopes and partially answering a 30-year-old conjecture.
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.