# Frank-Wolfe Algorithms for Saddle Point Problems

arXiv: https://arxiv.org/abs/1610.07797 · HTML: https://mlsanity.com/paper/1610.07797/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2016.

## Built on by (most cited first, 18 of 18)

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Smooth Tchebycheff Scalarization for Multi-Objective Optimization](https://mlsanity.com/paper/2402.19078/) (2024)
- [A Max-Min Entropy Framework for Reinforcement Learning](https://mlsanity.com/paper/2106.10517/) (2021)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)
- [Scaling the Convex Barrier with Sparse Dual Algorithms](https://mlsanity.com/paper/2101.05844/) (2021)
- [Solving a class of non-convex min-max games using adaptive momentum methods](https://mlsanity.com/paper/2104.12676/) (2021)
- [A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems](https://mlsanity.com/paper/2106.06075/) (2021)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Robust Entropy-regularized Markov Decision Processes](https://mlsanity.com/paper/2112.15364/) (2021)
- [Solving Constrained Variational Inequalities via a First-order Interior Point-based Method](https://mlsanity.com/paper/2206.10575/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Projection-Free Functional Constrained Optimization for Risk Aversion and Sparsity Control](https://mlsanity.com/paper/2210.05108/) (2022)
- [Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games](https://mlsanity.com/paper/2304.12768/) (2023)
- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2603.06369/) (2026)

## Abstract (arXiv)

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.