Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems

DOI10.1137/20M1337600zbMath1480.91016arXiv2002.07919OpenAlexW3206964102MaRDI QIDQ5158768

Andrew Lowy, Meisam Razaviyayn, Dmitrii M. Ostrovskii

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

stationary pointsfirst-order Nash equilibrianonconvex min-max problems

Mathematics Subject Classification ID

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

Related Items (7)

Zeroth-order single-loop algorithms for nonconvex-linear minimax problems ⋮ Decentralized Gradient Descent Maximization Method for Composite Nonconvex Strongly-Concave Minimax Problems ⋮ 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 ⋮ Unnamed Item ⋮ An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems

Uses Software

• SBEED
• NC-OPT

Cites Work

• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• Gradient methods for minimizing composite functions
• First-order methods of smooth convex optimization with inexact oracle
• On general minimax theorems
• Sharp uniform convexity and smoothness inequalities for trace norms
• 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
• Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
• Uniformly convex functions on Banach spaces
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• On first-order algorithms forl₁/nuclear norm minimization
• The Theory of Max-Min, with Applications
• A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications

This page was built for publication: Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems