极小极大优化问题的一类自适应三次正则化牛顿法

One Class of Cubic Regularized Newton Methods for Min-Max Optimization Problems

摘要: 许多机器学习问题，如对抗学习、强化学习和图像处理的一些典型问题大都可归结为极小极大优化问题。因此，极小极大优化问题最近已经成为最优化领域与机器学习交叉领域中的一个重要研究前沿和热点，吸引了众多学者的关注和研究。如何有效求解极小极大优化问题，是优化领域及应用中的关键科学问题之一。考虑到极小极大三次正则化牛顿法中，三次正则化项的系数是相对固定的，会影响算法的收敛性。本文首先针对非凸–强凹极小极大优化问题，采用信赖域半径的选取策略，提出了一类自适应极小极大三次正则化牛顿法。然后证得了算法的迭代复杂度为O（T^-1/3）。最后，通过一类对抗攻击神经网络问题，验证了该算法的有效性。

Abstract: Many machine learning problems, such as adversarial learning, reinforcement learning and image processing, can be reduced to min-max optimization problem. Therefore, min-max optimization has recently become an important research frontier and hot spot in the intersection of optimization and machine learning, attracting the attention and research of many scholars. How to effectively solve min-max problem is one of the key scientific problems in optimization field and application. Considering that the coefficient of cubic regularization term in min-max cubic regularization Newton method is relatively fixed, it will affect the convergence of the algorithm. In this paper, a class of adaptive min-max cubic regularization Newton method is proposed based on the selection strategy of the radius of the trust region for the nonconvex-strongly concave minimax optimization problem. Then, the iterative complexity of the algorithm is bounded by O（T^-1/3）. Finally, the effectiveness of the proposed algorithm is verified by a class of adversarial attack neural network problems.