论文标题
在零阶优化中逃脱鞍点：两点估计器的功率
Escaping saddle points in zeroth-order optimization: the power of two-point estimators
论文作者
论文摘要
两点零订单方法在许多应用中，例如机器人技术，风电场，电力系统，在线优化以及对深度神经网络中的黑盒攻击的对抗性鲁棒性，在此问题中，问题可能是高度的和/或时间变化。这些应用程序中的大多数问题是NonConvex，并且包含鞍点。尽管现有作品表明，每次迭代使用$ω（d）$函数估值（用$ d $表示问题维度）可以有效地逃脱鞍点，但如果基于两点估计器可以逃脱鞍点，则可以有效地逃脱鞍点。在本文中，我们表明，通过在每次迭代时添加适当的各向同性扰动，一种基于$ 200M $的零级算法（对于任何$ 1 \ leq m \ leq d $）函数评估每个迭代均可在迭代中进行评估，不仅可以找到$ε$ - 第二级订购的固定点综合点，但$ \ tilde {o} \ left（\ frac {d} {mε^{2} \ bar单ψ} \ right）$ function评估，其中$ \barψ\ geq \ geq \ geq \tildeΩ\ left（\sqrtε\ right）$是捕获范围的特定范围的参数。
Two-point zeroth order methods are important in many applications of zeroth-order optimization, such as robotics, wind farms, power systems, online optimization, and adversarial robustness to black-box attacks in deep neural networks, where the problem may be high-dimensional and/or time-varying. Most problems in these applications are nonconvex and contain saddle points. While existing works have shown that zeroth-order methods utilizing $Ω(d)$ function valuations per iteration (with $d$ denoting the problem dimension) can escape saddle points efficiently, it remains an open question if zeroth-order methods based on two-point estimators can escape saddle points. In this paper, we show that by adding an appropriate isotropic perturbation at each iteration, a zeroth-order algorithm based on $2m$ (for any $1 \leq m \leq d$) function evaluations per iteration can not only find $ε$-second order stationary points polynomially fast, but do so using only $\tilde{O}\left(\frac{d}{mε^{2}\barψ}\right)$ function evaluations, where $\barψ \geq \tildeΩ\left(\sqrtε\right)$ is a parameter capturing the extent to which the function of interest exhibits the strict saddle property.
