Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems

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 (9)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Agnostic Federated Learning
• Efficient Algorithms for Smooth Minimax Optimization
• General Resolvents for Monotone Operators: Characterization and Extension
• Independent Policy Gradient Methods for Competitive Reinforcement Learning
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
• Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity

Cited by in corpus (1)

• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain