Efficient Projection-Free Algorithms for Saddle Point Problems

The Frank-Wolfe algorithm is a classic method for constrained optimization problems. It has recently been popular in many machine learning applications because its projection-free property leads to more efficient iterations. In this paper, we study projection-free algorithms for convex-strongly-concave saddle point problems with complicated constraints. Our method combines Conditional Gradient Sliding with Mirror-Prox and shows that it only requires $\tilde{O}(1/\sqrt{\epsilon})$ gradient evaluations and $\tilde{O}(1/\epsilon^2)$ linear optimizations in the batch setting. We also extend our method to the stochastic setting and propose first stochastic projection-free algorithms for saddle point problems. Experimental results demonstrate the effectiveness of our algorithms and verify our theoretical guarantees.

• Publication year

  2020

• Venue

  Neural Information Processing Systems

• Publication date

  2020-10-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2010.11737
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods

  2019cited by this paper
• Stochastic Conditional Gradient++

  2019cited by this paper
• One Sample Stochastic Frank-Wolfe

  2019cited by this paper
• Efficient Algorithms for Smooth Minimax Optimization

  2019cited by this paper
• Reducing Noise in GAN Training with Variance Reduced Extragradient

  2019influential reference
• Complexities in Projection-Free Stochastic Non-convex Minimization

  2019cited by this paper
• Conditional Gradient Methods via Stochastic Path-Integrated Differential Estimator

  2019cited by this paper
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

  2019cited by this paper
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization

  2019cited by this paper
• Efficient Projection-Free Online Methods with Stochastic Recursive Gradient

  2019cited by this paper
• Online Compact Convexified Factorization Machine

  2018cited by this paper
• Non-convex Conditional Gradient Sliding

  2017cited by this paper
• Variance-based Regularization with Convex Objectives

  2016cited by this paper
• Frank-Wolfe Algorithms for Saddle Point Problems

  2016influential reference
• From Duels to Battlefields: Computing Equilibria of Blotto and Other Games

  2016cited by this paper
• Stochastic Variance Reduction Methods for Saddle-Point Problems

  2016cited by this paper
• Variance-Reduced and Projection-Free Stochastic Optimization

  2016influential reference
• Conditional Gradient Sliding for Convex Optimization

  2016influential reference
• Stochastic Frank-Wolfe methods for nonconvex optimization

  2016cited by this paper
• Semi-Proximal Mirror-Prox for Nonsmooth Composite Minimization

  2015cited by this paper
• Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators

  2015cited by this paper
• On the Computational Efficiency of Training Neural Networks

  2014cited by this paper
• Solving variational inequalities with monotone operators on domains given by Linear Minimization Oracles

  2013cited by this paper
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

  2013cited by this paper
• An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms

  2013cited by this paper
• Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

  2013influential reference
• Accelerated Training for Matrix-norm Regularization: A Boosting Approach

  2012cited by this paper
• Projection-free Online Learning

  2012cited by this paper
• Lifted coordinate descent for learning with trace-norm regularization

  2012cited by this paper
• A Simple Algorithm for Nuclear Norm Regularized Problems

  2010cited by this paper
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems

  2004cited by this paper
• Solving asymmetric variational inequality problems and systems of equations with generalized nonlinear programming algorithms

  1984cited by this paper
• A method for solving the convex programming problem with convergence rate O(1/k^2)

  1983cited by this paper
• The extragradient method for finding saddle points and other problems

  1976cited by this paper
• An algorithm for quadratic programming

  1956cited by this paper

• A Frank-Wolfe algorithm for strongly monotone variational inequalities

  2025influential citation
• Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis

  2025cites this paper
• Single-Loop Projection-Free and Projected Gradient-Based Algorithms for Nonconvex-Concave Saddle Point Problems with Bilevel Structure

  2024cites this paper
• Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities

  2024cites this paper
• Projection-Free Methods for Solving Nonconvex-Concave Saddle Point Problems

  2023influential citation
• Federated Composite Saddle Point Optimization

  2023cites this paper
• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization

  2023influential citation
• Breaking the Complexity Barrier in Compositional Minimax Optimization

  2023cites this paper
• Distributed Conditional Gradient Algorithm for Two-Network Saddle-point Problem

  2022cites this paper
• Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problems

  2022cites this paper
• A survey of decision making in adversarial games

  2022cites this paper
• On the Convergence of Stochastic Compositional Gradient Descent Ascent Method

  2021cites this paper
• Optimal Nonsmooth Frank-Wolfe method for Stochastic Regret Minimization

  2020cites this paper