Frank-Wolfe Algorithms for Saddle Point Problems

Author name not available (Why is that?)

Publication date: 25 October 2016

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.

Has companion code repository: https://github.com/MindCode-4/code-12/tree/main/Frank-Wolfe-Algorithm

Mathematics Subject Classification ID

No records found.

This page was built for publication: Frank-Wolfe Algorithms for Saddle Point Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6279017)