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.

该研究介绍了一种与梯度下降上升（GDA）算法相结合的 “平滑” 方案，以解决非凸 - 凹最小 - 最大问题，此方案能够稳定振荡，并确保收敛到一个定值解。实验结果表明，平滑后的 GDA 算法对于 minimizing pointwise maximum of a finite collection of nonconvex functions 可以实现 O (1/ε^2) 的迭代复杂度，对于 general nonconvex-concave problems 可以实现 O (1/ε^4) 的迭代复杂度，并且将该算法扩展到多个区块的情况下。