论文标题
使用近端梯度方法求解非凸线的非差异性最大最大游戏
Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method
论文作者
论文摘要
Min-Max鞍点游戏在机器倾斜和信号处理中出现在广泛的应用中。尽管它们的适用性广泛，但理论研究大多限于特殊的凸孔结构。 While some recent works generalized these results to special smooth non-convex cases, our understanding of non-smooth scenarios is still limited.在这项工作中，当目标函数（强烈）相对于玩家的决策变量之一时，我们研究了非平滑最小最大游戏的特殊形式。我们表明，一个简单的多步近端梯度下降算法收敛到$ε$ - fir-firt-Fir-firt-firt-Fir-firt-Firt-Firt-Firt-Firt-Firt-Firt-Firt-Firt-Firt-Firt-Firtient Nash均衡，其中梯度评估的数量为$ 1/ε$。我们还将表明，我们的平稳性概念比文献中现有的概念更强。最后，我们通过对套索估计器的对抗攻击来评估所提出的算法的性能。
Min-max saddle point games appear in a wide range of applications in machine leaning and signal processing. Despite their wide applicability, theoretical studies are mostly limited to the special convex-concave structure. While some recent works generalized these results to special smooth non-convex cases, our understanding of non-smooth scenarios is still limited. In this work, we study special form of non-smooth min-max games when the objective function is (strongly) convex with respect to one of the player's decision variable. We show that a simple multi-step proximal gradient descent-ascent algorithm converges to $ε$-first-order Nash equilibrium of the min-max game with the number of gradient evaluations being polynomial in $1/ε$. We will also show that our notion of stationarity is stronger than existing ones in the literature. Finally, we evaluate the performance of the proposed algorithm through adversarial attack on a LASSO estimator.
