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

Abstract

Recent applications that arise in machine learning have surged significant interest in solving min-max saddle point games. This problem has been extensively studied in the convex-concave regime for which a global equilibrium solution can be computed efficiently. In this paper, we study the problem in the non-convex regime and show that an \varepsilon--first order stationary point of the game can be computed when one of the player's objective can be optimized to global optimality efficiently. In particular, we first consider the case where the objective of one of the players satisfies the Polyak-Łojasiewicz (PL) condition. For such a game, we show that a simple multi-step gradient descent-ascent algorithm finds an \varepsilon--first order stationary point of the problem in \widetilde{\mathcal{O}}(\varepsilon^{-2}) iterations. Then we show that our framework can also be applied to the case where the objective of the "max-player" is concave. In this case, we propose a multi-step gradient descent-ascent algorithm that finds an \varepsilon--first order stationary point of the game in \widetilde{\cal O}(\varepsilon^{-3.5}) iterations, which is the best known rate in the literature. We applied our algorithm to a fair classification problem of Fashion-MNIST dataset and observed that the proposed algorithm results in smoother training and better generalization.

Cited by in corpus (63)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Game-Theoretic Multiagent Reinforcement Learning
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Near-Optimal Algorithms for Minimax Optimization
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Convergence of Learning Dynamics in Stackelberg Games
• GANs May Have No Nash Equilibria
• Task-Robust Model-Agnostic Meta-Learning
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Learning to Continuously Optimize Wireless Resource In Episodically Dynamic Environment
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• An Optimal Transport Approach to Personalized Federated Learning
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Improved Algorithms for Convex-Concave Minimax Optimization
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Rényi Fair Inference
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• On Tilted Losses in Machine Learning: Theory and Applications
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
• Improved OOD Generalization via Adversarial Training and Pre-training
• A mean-field analysis of two-player zero-sum games
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Information Obfuscation of Graph Neural Networks
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Saddle Point Optimization with Approximate Minimization Oracle
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Generative Minimization Networks: Training GANs Without Competition
• Regret minimization in stochastic non-convex learning via a proximal-gradient approach
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Tilted Empirical Risk Minimization
• A Hölderian backtracking method for min-max and min-min problems
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
• Low-rank Matrix Recovery With Unknown Correspondence
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Efficient Projection-Free Algorithms for Saddle Point Problems
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• Output Perturbation for Differentially Private Convex Optimization: Faster and More General
• Randomized Stochastic Gradient Descent Ascent
• Towards Accurate Quantization and Pruning via Data-free Knowledge Transfer
• Three Operator Splitting with a Nonconvex Loss Function
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
• Minimax Optimization with Smooth Algorithmic Adversaries
• Pure Characteristics Demand Models and Distributionally Robust Mathematical Programs with Stochastic Complementarity Constraints
• Complex Momentum for Optimization in Games
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
• Direct-Search for a Class of Stochastic Min-Max Problems