An accelerated inexact proximal point method for solving nonconvex-concave min-max problems

Abstract

This paper presents smoothing schemes for obtaining approximate stationary points of unconstrained or linearly-constrained composite nonconvex-concave min-max (and hence nonsmooth) problems by applying well-known algorithms to composite smooth approximations of the original problems. More specifically, in the unconstrained (resp. constrained) case, approximate stationary points of the original problem are obtained by applying, to its composite smooth approximation, an accelerated inexact proximal point (resp. quadratic penalty) method presented in a previous paper by the authors. Iteration complexity bounds for both smoothing schemes are also established. Finally, numerical results are given to demonstrate the efficiency of the unconstrained smoothing scheme.

References in corpus (4)

• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Accelerated Methods for Non-Convex Optimization
• Near-Optimal Algorithms for Minimax Optimization
• Efficient Algorithms for Smooth Minimax Optimization

Cited by in corpus (9)

• Game-Theoretic Multiagent Reinforcement Learning
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems
• Randomized Stochastic Gradient Descent Ascent