Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
arXiv:2105.15042
Abstract
Minimax problems, such as generative adversarial network, adversarial training, and fair training, are widely solved by a multi-step gradient descent ascent (MGDA) method in practice. However, its convergence guarantee is limited. In this paper, inspired by the primal-dual hybrid gradient method, we propose a new semi-anchoring (SA) technique for the MGDA method. This makes the MGDA method find a stationary point of a structured nonconvex-nonconcave composite minimax problem; its saddle-subdifferential operator satisfies the weak Minty variational inequality condition. The resulting method, named SA-MGDA, is built upon a Bregman proximal point method. We further develop its backtracking line-search version, and its non-Euclidean version for smooth adaptable functions. Numerical experiments, including a fair classification training, are provided.
References in corpus (20)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Large Scale GAN Training for High Fidelity Natural Image Synthesis
- Spectral Normalization for Generative Adversarial Networks
- Which Training Methods for GANs do actually Converge?
- Agnostic Federated Learning
- A Variational Inequality Perspective on Generative Adversarial Networks
- 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
- A first-order primal-dual algorithm with linesearch
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
- Efficient Algorithms for Smooth Minimax Optimization
- General Resolvents for Monotone Operators: Characterization and Extension
- Independent Policy Gradient Methods for Competitive Reinforcement Learning
- Convergence of Gradient Methods on Bilinear Zero-Sum Games
- Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
- A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
- Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
- Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with Rate on Squared Gradient Norm
- Extragradient Method: Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity