We consider the case of derivative-free algorithms for non-convex
optimization, also known as zero order algorithms, that use only function
evaluations rather than gradients. For a wide variety of gradient approximators
based on finite differences, we establish asymptotic convergence to second
order stationary points using a carefully tailored application of the Stable
Manifold Theorem. Regarding efficiency, we introduce a noisy zero-order method
that converges to second order stationary points, i.e avoids saddle points. Our
algorithm uses only $\tilde{\mathcal{O}}(1 / \epsilon^2)$ approximate gradient
calculations and, thus, it matches the converge rate guarantees of their exact
gradient counterparts up to constants. In contrast to previous work, our
convergence rate analysis avoids imposing additional dimension dependent
slowdowns in the number of iterations required for non-convex zero order
optimization.

本文研究了非凸优化中的无导数算法，利用有限差分器进行梯度逼近，最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法，并在收敛速度上达到了与精确梯度接近的性能。

无梯度的零阶方法高效避免鞍点

Efficiently avoiding saddle points with zero order methods: No gradients  required

Game theory finds nowadays a broad range of applications in engineering and
machine learning. However, in a derivative-free, expensive black-box context,
very few algorithmic solutions are available to find game equilibria. Here, we
propose a novel Gaussian-process based approach for solving games in this
context. We follow a classical Bayesian optimization framework, with sequential
sampling decisions based on acquisition functions. Two strategies are proposed,
based either on the probability of achieving equilibrium or on the Stepwise
Uncertainty Reduction paradigm. Practical and numerical aspects are discussed
in order to enhance the scalability and reduce computation time. Our approach
is evaluated on several synthetic game problems with varying number of players
and decision space dimensions. We show that equilibria can be found reliably
for a fraction of the cost (in terms of black-box evaluations) compared to
classical, derivative-based algorithms. The method is available in the R
package GPGame available on CRAN at this https URL

采用 Gaussian-process 和 Bayesian optimization 框架，提出适用于 derivative-free 环境下求解游戏均衡的算法，相比传统的基于导数的算法，可以在可接受的黑盒计算成本下，可靠地求得均衡。

一种贝叶斯优化方法来寻找纳什均衡

A Bayesian optimization approach to find Nash equilibria

We consider derivative-free algorithms for stochastic and non-stochastic
convex optimization problems that use only function values rather than
gradients. Focusing on non-asymptotic bounds on convergence rates, we show that
if pairs of function values are available, algorithms for $d$-dimensional
optimization that use gradient estimates based on random perturbations suffer a
factor of at most $\sqrt{d}$ in convergence rate over traditional stochastic
gradient methods. We establish such results for both smooth and non-smooth
cases, sharpening previous analyses that suggested a worse dimension
dependence, and extend our results to the case of multiple ($m \ge 2$)
evaluations. We complement our algorithmic development with
information-theoretic lower bounds on the minimax convergence rate of such
problems, establishing the sharpness of our achievable results up to constant
(sometimes logarithmic) factors.

该研究探讨了使用函数值而不是梯度的无导数算法在随机和非随机凸优化问题中的应用，同时关注其收敛速率，经实验表明使用随机扰动的梯度估算方法具有比传统随机梯度方法更快的收敛速率，尤其在光滑和非光滑情况下，且可以扩展到多次评估的情况。