标题： 非凸非凹函数的随机零阶外梯度算法的极小极大优化 显示英文标题

标题： Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm

摘要： 本研究探讨了在可能具有非凸-非凹（NC-NC）目标函数的极小极大优化问题中，随机高斯平滑零阶额外梯度（ZO-EG）方案的性能。我们考虑了无约束和有约束、可微和不可微的情况。我们从变分不等式的角度讨论了极小极大问题。对于无约束问题，我们建立了ZO-EG算法收敛到NC-NC目标函数的$\epsilon$-稳定点邻域，其半径可以在方差减少方案下进行控制，同时给出了其复杂度。对于有约束问题，我们引入了新的近似变分不等式概念，并给出了满足该性质的函数示例。此外，我们为有约束问题证明了与无约束情况类似的结果。对于不可微情况，我们证明了ZO-EG算法收敛到目标函数平滑版本的$\epsilon$-稳定点邻域，该邻域的半径可以进行控制，这可以与原目标函数的（$\delta,\epsilon$）-Goldstein稳定点相关联。 显示英文摘要

摘要： This study explores the performance of the random Gaussian smoothing Zeroth-Order ExtraGradient (ZO-EG) scheme considering min-max optimisation problems with possibly NonConvex-NonConcave (NC-NC) objective functions. We consider both unconstrained and constrained, differentiable and non-differentiable settings. We discuss the min-max problem from the point of view of variational inequalities. For the unconstrained problem, we establish the convergence of the ZO-EG algorithm to the neighbourhood of an $\epsilon$-stationary point of the NC-NC objective function, whose radius can be controlled under a variance reduction scheme, along with its complexity. For the constrained problem, we introduce the new notion of proximal variational inequalities and give examples of functions satisfying this property. Moreover, we prove analogous results to the unconstrained case for the constrained problem. For the non-differentiable case, we prove the convergence of the ZO-EG algorithm to a neighbourhood of an $\epsilon$-stationary point of the smoothed version of the objective function, where the radius of the neighbourhood can be controlled, which can be related to the ($\delta,\epsilon$)-Goldstein stationary point of the original objective function.