A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems

Abstract

Nonconvex-concave min-max problem arises in many machine learning applications including minimizing a pointwise maximum of a set of nonconvex functions and robust adversarial training of neural networks. A popular approach to solve this problem is the gradient descent-ascent (GDA) algorithm which unfortunately can exhibit oscillation in case of nonconvexity. In this paper, we introduce a "smoothing" scheme which can be combined with GDA to stabilize the oscillation and ensure convergence to a stationary solution. We prove that the stabilized GDA algorithm can achieve an $O(1/{\epsilon }^2)$ iteration complexity for minimizing the pointwise maximum of a finite collection of nonconvex functions. Moreover, the smoothed GDA algorithm achieves an $O(1/{\epsilon }^4)$ iteration complexity for general nonconvex-concave problems. Extensions of this stabilized GDA algorithm to multi-block cases are presented. To the best of our knowledge, this is the first algorithm to achieve $O(1/{\epsilon }^2)$ for a class of nonconvex-concave problem. We illustrate the practical efficiency of the stabilized GDA algorithm on robust training.

Accepted by ICML 2020; Correct typos in Proposition B.4, Lemma 4.3, B.6, B.10, B.12, D.1 and Theorem 3.4

References in corpus (12)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Theoretically Principled Trade-off between Robustness and Accuracy
• Agnostic Federated Learning
• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• 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
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Near-Optimal Algorithms for Minimax Optimization
• Frank-Wolfe Algorithms for Saddle Point Problems
• SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems

Cited by in corpus (5)

• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Low-rank Matrix Recovery With Unknown Correspondence
• Randomized Stochastic Gradient Descent Ascent
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization