凸-凹极小极大优化问题的零阶梯度下降上升算法

Zeroth-Order Gradient Descent Ascent Algorithm for General Convex Concave Min-Max Problems

[目的]为了解决基于梯度下降上升算法在某些应用中,目标函数的梯度信息计算昂贵或难以获取的问题。[方法]基于此,针对一类凸-凹极小极大优化问题,在梯度下降上升算法(OGDA)的框架下,基于均匀分布的平滑化方法用差商来近似函数梯度信息,提出了一类零阶梯度下降上升算法(ZO-OGDA)。[结果]基于带误差的邻近点算法的收敛性分析理论,证明得到所提算法ZO-OGDA取得ε-稳定点的迭代复杂度为O(ε-1)。[结论]最后通过数值仿真,实验结果表明所提出的算法ZO-OGDA在数值上与算法OGDA表现相近。

[Purposes]The generate adversarial network models in machine learning are proposed by a min-max optimization problem,which has attracted extensive attention of scholars.At present,most of optimization algorithms are designed based on the standard gradient descent ascent algorithm.However,in some applications,the gradient information of the objective function is often computationally expensive or difficult to obtain.[Methods]Therefore,for a class of convex-concave min-max optimization problems,a zero-order optimistic gradient descent ascent algorithm(ZO-OGDA)is proposed by using the information of function values to approximate the gradient information based on a smoothing method.The proposed ZO-OGDA algorithm extends the OGDA algorithm to the gradient-free case.[Findings]Then,based on the convergence analysis theory of the proximal point algorithm with errors,the iteration complexity of the proposed ZO-OGDA algorithm to obtainε-stationary points with order of O(ε-1)is obtained.[Conclusions]Finally,numerical experiments on the matrix game model is performed.The numerical results show that the performance of the proposed ZO-OGDA algorithm is similar to that of the OGDA algorithm.