论文标题
非Convex-Nonconcave minimax优化的近端点方法的景观
The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization
论文作者
论文摘要
Minimax优化已成为机器学习的中心工具，并在强大的优化，强化学习，gans等方面进行了应用。这些应用通常是非convex-nonconcave，但是现有理论无法识别并处理这构成的基本困难。在本文中，我们研究了应用于非Convex-Nonconcave minimax问题的经典近端方法（PPM）。我们发现，通过Attouch和Wets对Moreau信封的经典概括提供了关键的见解。至关重要的是，我们表明该包膜不仅可以平滑目标，而且可以根据最小化和最大化变量之间的相互作用水平进行凸出和凹入。由此，我们确定了非Convex-Nonconcave问题的三个不同区域。当相互作用足够强大时，我们会得出全局线性收敛的保证。相反，当相互作用相当较弱时，我们会通过适当的初始化得出局部线性收敛的保证。在这两个设置之间，我们表明ppm可能会发散或收敛到极限周期。
Minimax optimization has become a central tool in machine learning with applications in robust optimization, reinforcement learning, GANs, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties this poses. In this paper, we study the classic proximal point method (PPM) applied to nonconvex-nonconcave minimax problems. We find that a classic generalization of the Moreau envelope by Attouch and Wets provides key insights. Critically, we show this envelope not only smooths the objective but can convexify and concavify it based on the level of interaction present between the minimizing and maximizing variables. From this, we identify three distinct regions of nonconvex-nonconcave problems. When interaction is sufficiently strong, we derive global linear convergence guarantees. Conversely when the interaction is fairly weak, we derive local linear convergence guarantees with a proper initialization. Between these two settings, we show that PPM may diverge or converge to a limit cycle.
