Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems

DOI10.1137/20M1337600MaRDI QIDQ5158768zbMATH OpenOpenAlexFDO

Authors Andrew Lowy, Meisam Razaviyayn, D. Ostrovski

Publication date 26 October 2021

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.07919

zbMATH Keywords

first-order Nash equilibrianonconvex min-max problemsstationary points

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Equilibrium refinements (91A11)

Abstract: We propose an efficient algorithm for finding first-order Nash equilibria in min-max problems of the form $mi{n}_{xinX}ma{x}_{yinY}F(x,y)$, where the objective function is smooth in both variables and concave with respect to $y$; the sets $X$ and $Y$ are convex and "projection-friendly," and $Y$ is compact. Our goal is to find an $(varepsilo{n}_x,varepsilo{n}_y)$-first-order Nash equilibrium with respect to a stationarity criterion that is stronger than the commonly used proximal gradient norm. The proposed approach is fairly simple: we perform approximate proximal-point iterations on the primal function, with inexact oracle provided by Nesterov's algorithm run on the regularized function $F(x_t,cdot)$, $x_t$ being the current primal iterate. The resulting iteration complexity is $O(varepsilo{n}_x{}^{-2}varepsilo{n}_y{}^{-1/2})$ up to a logarithmic factor. As a byproduct, the choice $varepsilo{n}_y=O(varepsilo{n}_x{}^2)$ allows for the $O(varepsilo{n}_x{}^{-3})$ complexity of finding an $varepsilo{n}_x$-stationary point for the standard Moreau envelope of the primal function. Moreover, when the objective is strongly concave with respect to $y$, the complexity estimate for our algorithm improves to $O(varepsilo{n}_x{}^{-2}{kapp{a}_y}^{1/2})$ up to a logarithmic factor, where $kapp{a}_y$ is the condition number appropriately adjusted for coupling. In both scenarios, the complexity estimates are the best known so far, and are only known for the (weaker) proximal gradient norm criterion. Meanwhile, our approach is "user-friendly:" (i) the algorithm is built upon running a variant of Nesterov's accelerated algorithm as subroutine and avoids extragradient steps; (ii) the convergence analysis recycles the well-known results on accelerated methods with inexact oracle. Finally, we extend the approach to non-Euclidean proximal geometries.

Recommendations

• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
• scientific article; zbMATH DE number 6822826
• On some approaches to find Nash equilibrium in concave games
• scientific article; zbMATH DE number 165423

Cites work

• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• Convex optimization: algorithms and complexity
• First-order methods of smooth convex optimization with inexact oracle
• Gradient methods for minimizing composite functions
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Lower bounds for finding stationary points I
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• On first-order algorithms for \(\ell_{1}/\)nuclear norm minimization
• On general minimax theorems
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Sharp uniform convexity and smoothness inequalities for trace norms
• Smooth minimization of non-smooth functions
• Stochastic block mirror descent methods for nonsmooth and stochastic optimization
• The Theory of Max-Min, with Applications
• Uniformly convex functions on Banach spaces

Cited in

(24)

• Learning how to play Nash, potential games and alternating minimization method for structured nonconvex problems on Riemannian manifolds
• Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• scientific article; zbMATH DE number 7625189 (Why is no real title available?)
• An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems
• Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
• Zeroth-order single-loop algorithms for nonconvex-linear minimax problems
• Decentralized Gradient Descent Maximization Method for Composite Nonconvex Strongly-Concave Minimax Problems
• Optimality Conditions for Nonsmooth Nonconvex-Nonconcave Min-Max Problems and Generative Adversarial Networks
• Conservative parametric optimality and the ridge method for tame min-max problems
• Adaptive constraint satisfaction for Markov decision process congestion games: application to transportation networks
• Alternating Proximal-Gradient Steps for (Stochastic) Nonconvex-Concave Minimax Problems
• Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems
• An approximation proximal gradient algorithm for nonconvex-linear minimax problems with nonconvex nonsmooth terms
• Efficient first order method for saddle point problems with higher order smoothness
• Accelerated minimax algorithms flock together
• A first-order method for nonconvex-strongly-concave constrained minimax optimization
• Nonsmooth nonconvex-nonconcave minimax optimization: primal-dual balancing and iteration complexity analysis
• Gradient norm regularization second-order algorithms for solving nonconvex-strongly concave minimax problems
• Single-loop projection-free and projected gradient-based algorithms for nonconvex-concave saddle point problems with bilevel structure
• Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization
• An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems
• A minimization approach for minimax optimization with coupled constraints
• An alternating proximal gradient algorithm for nonsmooth nonconvex-linear minimax problems with coupled linear constraints

Describes a project that uses

Uses Software

• SBEED
• NC-OPT

This page was built for publication: Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158768)