论文标题
鞍点问题的无梯度方法
Gradient-Free Methods for Saddle-Point Problem
论文作者
论文摘要
在本文中，我们概括了Gasnikov等人的方法。 Al，2017年，它允许使用不精确的无梯度的甲骨文解决（随机）凸优化问题，以解决凸形 - concave鞍点问题。所提出的方法至少像最好的现有方法一样有效。但是，对于特殊的设置（单纯类型的约束和1和2规范中Lipschitz常数的紧密度），我们的方法降低了$ \ frac {n} {\ log n} $ timple所需的Oracle呼叫数量（函数计算）。我们的方法通过有限差异使用梯度的随机近似。在这种情况下，该函数不仅必须在优化集本身上，而且在其某个邻域中指定。在本文的第二部分中，我们分析了无法做出这样的假设时，我们提出了一种有关如何现代化解决此问题的方法的一般方法，并且我们也将这种方法应用于某些经典集合的特定情况。
In the paper, we generalize the approach Gasnikov et. al, 2017, which allows to solve (stochastic) convex optimization problems with an inexact gradient-free oracle, to the convex-concave saddle-point problem. The proposed approach works, at least, like the best existing approaches. But for a special set-up (simplex type constraints and closeness of Lipschitz constants in 1 and 2 norms) our approach reduces $\frac{n}{\log n}$ times the required number of oracle calls (function calculations). Our method uses a stochastic approximation of the gradient via finite differences. In this case, the function must be specified not only on the optimization set itself, but in a certain neighbourhood of it. In the second part of the paper, we analyze the case when such an assumption cannot be made, we propose a general approach on how to modernize the method to solve this problem, and also we apply this approach to particular cases of some classical sets.
