Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization

Abstract

The use of min-max optimization in adversarial training of deep neural network classifiers and training of generative adversarial networks has motivated the study of nonconvex-nonconcave optimization objectives, which frequently arise in these applications. Unfortunately, recent results have established that even approximate first-order stationary points of such objectives are intractable, even under smoothness conditions, motivating the study of min-max objectives with additional structure. We introduce a new class of structured nonconvex-nonconcave min-max optimization problems, proposing a generalization of the extragradient algorithm which provably converges to a stationary point. The algorithm applies not only to Euclidean spaces, but also to general ${\ell }_p$-normed finite-dimensional real vector spaces. We also discuss its stability under stochastic oracles and provide bounds on its sample complexity. Our iteration complexity and sample complexity bounds either match or improve the best known bounds for the same or less general nonconvex-nonconcave settings, such as those that satisfy variational coherence or in which a weak solution to the associated variational inequality problem is assumed to exist.

in Proc. AISTATS'21

References in corpus (10)

• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Last-iterate convergence rates for min-max optimization
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
• Accelerated methods for composite non-bilinear saddle point problem

Cited by in corpus (9)

• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• Stochastic Relaxed Inertial Forward-Backward-Forward splitting for Monotone Inclusions in Hilbert spaces
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Stochastic Extragradient: General Analysis and Improved Rates
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
• An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
• Mirror frameworks for relatively Lipschitz and monotone-like variational inequalities
• Minimax Optimization: The Case of Convex-Submodular