mlsanityData to 7 Oct 2026

Frank-Wolfe Algorithms for Saddle Point Problems

arXiv 1610.07797 ↗First posted 25 Oct 2016math.OC cs.LG stat.MLcited by 18

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 3; 2023: 2; 2024: 3; 2025: 1; 2026: 1.

18 papers.

Sort:

By area:

  1. 2023Nash Learning from Human Feedbackcited by 220
  2. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 54
  3. 2024Smooth Tchebycheff Scalarization for Multi-Objective Optimizationcited by 50
  4. 2021A Max-Min Entropy Framework for Reinforcement Learningcited by 28
  5. 2021Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimizationcited by 18
  6. 2021Scaling the Convex Barrier with Sparse Dual Algorithmscited by 10
  7. 2021Solving a class of non-convex min-max games using adaptive momentum methodscited by 10
  8. 2021A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problemscited by 9
  9. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  10. 2021Local and Global Uniform Convexity Conditionscited by 4
  11. 2021Robust Entropy-regularized Markov Decision Processescited by 4
  12. 2022Solving Constrained Variational Inequalities via a First-order Interior Point-based Methodcited by 3
6 more
  1. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  2. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  3. 2022Projection-Free Functional Constrained Optimization for Risk Aversion and Sparsity Controlcited by 2
  4. 2023Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Gamescited by 2
  5. 2025Pure Exploration via Frank-Wolfe Self-Playcited by 1
  6. 2026Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1