Gradient-Free Methods for Saddle-Point Problem
Gradient-Free Methods for Saddle-Point Problem
复制标题
鞍点问题的无梯度方法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Gasnikov
中科院分区：
文献类型：
--
作者：
Aleksandr Beznosikov;Abdurakhmon Sadiev;A. Gasnikov
在本文中，我们推广的方法Gasnikov等。al，2017，它允许用不精确的无梯度预言来解决（随机）凸优化问题，到凸-凹鞍点问题。所提出的方法至少像现有的最佳方法一样有效。但是对于一个特殊的设置（单纯形类型的约束和1和2范数的Lipschitz常数的封闭性），我们的方法减少了$\frac{n}{\log n}$倍所需的oracle调用（函数计算）。我们的方法通过有限差分使用梯度的随机近似。在这种情况下，函数必须指定不仅在优化集本身，但在一定的邻域it. In第二部分的文件，我们分析的情况下，当这样的假设不能，我们提出了一个一般的方法，就如何现代化的方法来解决这个问题，我们也将这种方法应用到一些经典集的特殊情况。
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.
DOI：
--
发表时间：
2016-12
期刊：
ArXiv
影响因子：
--
作者：
I. Goodfellow
通讯作者：
I. Goodfellow