论文标题
用于平滑鞍点问题的零订单算法
Zeroth-Order Algorithms for Smooth Saddle-Point Problems
论文作者
论文摘要
鞍点问题最近引起了机器学习社区的关注，这主要是由于使用随机梯度在培训生成的对抗网络中的应用。同时，在某些应用中，只有一个零订单的甲骨文可用。在本文中，我们提出了几种算法，以解决随机平滑（强）使用零级牙齿牙齿甲壳齿轮问题的凸出式鞍点问题，并估算其收敛速率及其对变量的尺寸$ n $的依赖性。特别是，我们的分析表明，在可行集合是两个简单的直接乘积时，我们的随机项的收敛速率仅比$ \ log n $因子要比一阶方法差。我们还考虑了一个混合设置，并开发了1/2阶方法，该方法将零级甲骨文用于最小化零件和最大化零件的一阶甲骨文。最后，我们证明了零订单和1/2阶方法的实际性能。
Saddle-point problems have recently gained increased attention from the machine learning community, mainly due to applications in training Generative Adversarial Networks using stochastic gradients. At the same time, in some applications only a zeroth-order oracle is available. In this paper, we propose several algorithms to solve stochastic smooth (strongly) convex-concave saddle-point problems using zeroth-order oracles and estimate their convergence rate and its dependence on the dimension $n$ of the variable. In particular, our analysis shows that in the case when the feasible set is a direct product of two simplices, our convergence rate for the stochastic term is only by a $\log n$ factor worse than for the first-order methods. We also consider a mixed setup and develop 1/2th-order methods that use zeroth-order oracle for the minimization part and first-order oracle for the maximization part. Finally, we demonstrate the practical performance of our zeroth-order and 1/2th-order methods on practical problems.
