Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions

2022/01/28 by Axel Böhm, Böhm, Axel · 4 citations
Computer Science · Engineering · #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2201.12247

openalex publication_date 2022/01/28 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28

Abstract

We investigate a structured class of nonconvex-nonconcave min-max problems exhibiting so-called weak Minty solutions, a notion which was only recently introduced, but is able to simultaneously capture different generalizations of monotonicity. We prove novel convergence results for a generalized version of the optimistic gradient method (OGDA) in this setting, matching the 1/k rate for the best iterate in terms of the squared operator norm recently shown for the extragradient method (EG). In addition we propose an adaptive step size version of EG, which does not require knowledge of the problem parameters.

Cited by

• Worst-case generation via minimax optimization in Wasserstein space
• Extragradient Method for (L₀, L₁)-Lipschitz Root-finding Problems
• New Classes of Non-monotone Variational Inequality Problems Solvable via Proximal Gradient on Smooth Gap Functions
• A first-order method for constrained nonconvex-nonconcave minimax optimization

Related

• Doubly Smoothed Optimistic Gradients: A Universal Approach for Smooth Minimax Problems
• Escaping limit cycles: Global convergence for constrained\n nonconvex-nonconcave minimax problems
• Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems
• Beyond first-order methods for non-convex non-concave min-max optimization
• AGDA+: Proximal Alternating Gradient Descent Ascent Method with a Nonmonotone Adaptive Step-Size Search for Nonconvex Minimax Problems