Efficient Algorithms for Smooth Minimax Optimization

Abstract

This paper studies first order methods for solving smooth minimax optimization problems ${\min }_x{\max }_{y}g(x,y)$ where $g(\cdot ,\cdot )$ is smooth and $g(x,\cdot )$ is concave for each $x$. In terms of $g(\cdot ,y)$, we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. For strongly-convex $g(\cdot ,y),\forall y$, we propose a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in $\tilde{O}(1/k^2)$ iterations, improving over current state-of-the-art rate of $O(1/k)$. We use this result along with an inexact proximal point method to provide $\tilde{O}(1/k^{1/3})$ rate for finding stationary points in the nonconvex setting where $g(\cdot ,y)$ can be nonconvex. This improves over current best-known rate of $O(1/k^{1/5})$. Finally, we instantiate our result for finite nonconvex minimax problems, i.e., ${\min }_x{\max }_{1\le i\le m}{f}_i(x)$, with nonconvex $f_i(\cdot )$, to obtain convergence rate of $O(m(\log m{)}^{3/2}/k^{1/3})$ total gradient evaluations for finding a stationary point.

References in corpus (8)

• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Potential-Function Proofs for First-Order Methods
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
• Accelerated Primal Dual Method for a Class of Saddle Point Problem with Strongly Convex Component

Cited by in corpus (34)

• 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
• A Dual-Dimer Method for Training Physics-Constrained Neural Networks with Minimax Architecture
• Near-Optimal Algorithms for Minimax Optimization
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Improved Algorithms for Convex-Concave Minimax Optimization
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Variable Smoothing for Weakly Convex Composite Functions
• Fast First-Order Algorithm for Large-Scale Max-Min Fair Multi-Group Multicast Beamforming
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Generalized Energy Based Models
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Efficient Projection-Free Algorithms for Saddle Point Problems
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• Randomized Stochastic Gradient Descent Ascent
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
• Convex-Concave Min-Max Stackelberg Games