一类非凸-强凹极小极大问题的零阶优化算法

极小极大问题是博弈论和机器学习中的一类重要问题。目前已有大量基于目标函数的梯度和Hessian阵信息的优化算法来求解这类问题。但在有些应用中，目标函数的梯度或Hessian阵信息往往是计算昂贵或难以获取的。为此，针对一类非凸-强凹极小极大问题，在极小极大三次正则化牛顿算法的框架下，通过基于Stein恒等式的高斯平滑化方法来近似梯度与Hessian阵信息，进而提出一类零阶极小极大三次正则化牛顿算法。分析算法的收敛性，并得到算法达到一个二阶平稳点时的迭代复杂度为O（ε-3/2），其中ε是算法终止所达到的精度。数值仿真实验结果表明：在相同的精度下，所提出的算法在CPU运行时间上优于极小极大三次正则化牛顿算法。

Zeroth-Order Optimization Algorithm for a Class of Non-Convex Strongly Concave Mini-Max Problems

A class of mini-max optimization problems is frequently encountered in machine learning. A large number of optimization algorithms have been designed for mini-max problems based on the gradient and Hessian matrix information of the objective function. However, in some applications, the gradient and Hessian matrix information are possibly computationally expensive or difficult to obtain. Therefore, under the framework of mini-max cubic Newton algorithm (MCN), a zeroth-order mini-max cubic regularized Newton algorithm (ZO-MCN) is proposed for solving the non-convex strongly concave mini-max problem by using Gaussian smoothing method to approximate the gradient and Hessian matrix based on Stein identity.The convergence and iteration complexity of the proposed algorithm are analyzed. The iteration complexity of the algorithm is the order of O（ε-3/2） for achieving a second-order stable point, where ε is the accuracy. The results of numerical simulations show that: under the same accuracy, the proposed algorithm is better than the algorithm MCN in CPU running time.