利用扰动梯度估计方法逃离鞍点

《Expert Systems with Applications》：Escaping from saddle points with perturbed gradient estimation

针对非凸优化中鞍点逃逸困难及计算成本高的问题，本文提出两步同时扰动随机逼近算法（2-SPSA），仅需4次函数评估迭代即可有效逃离鞍点并收敛到全局最优，显著优于传统零阶方法。

　　

陈静静|刘三阳

中国广州广东金融学院数据科学与人工智能学院

摘要

对于那些难以获取导数信息的非凸函数来说，逃离鞍点仍然是一个重大挑战。现有的零阶优化算法通过使用无偏梯度估计技术、施加零均值随机扰动或探索负曲率方向来近似真实梯度以逃离鞍点。然而，这些方法在鞍点附近会遇到接近零的近似梯度，因此需要多次小幅度扰动才能逃离，从而消耗大量的函数评估次数。在这项工作中，我们提出了两步同时扰动随机逼近（2-SPSA）方法，以减少函数评估次数。在每次迭代中，该方法仅需要4次函数评估就可以估计当前点及其邻近点的梯度，它们的凸组合作为下降方向。这种梯度估计方法中的随机性有助于快速跳出鞍点。实验结果表明，与其它零阶优化算法相比，所提出的方法可以在更少的函数评估次数内逃离鞍点。

引言

在这项工作中，我们旨在解决非凸优化问题${\min }_{x\in R^d}f\left(x\right)，其中$f(x)的梯度信息是不可用的。这个问题在机器学习领域受到了广泛关注，应用场景包括在线学习（Shamir, 2017a）、元学习（Bergstra & Bengio, 2012）、强化学习（Li, Tang, Zhang, & Li, 2022）和黑盒对抗攻击（Chen, Zhang, Sharma, Yi, Hsieh, 2017, Madaan, Shin, Hwang, 2021）。非凸优化中的一个关键挑战是存在次优局部最优解和鞍点。在诸如通用对抗攻击之类的场景中，存在大量的次优解，这给传统的基于梯度的优化算法带来了困难（Tramèr et al., 2017）。另一方面，鞍点会阻碍算法的收敛，因为根据?-近似一阶静止点的标准（‖?f(x)‖?≤??），它们与局部最优解无法区分。收敛到鞍点通常会导致高度次优的解（Jain, Jin, Kakade, Netrapalli, 2017, Sun, Qu, Wright, 2018）。

为了解决这些挑战，零阶优化技术受到了关注，因为它们不依赖于显式的梯度信息，并且能够有效地应对非凸问题的复杂景观（Chen, Zhang, Sharma, Yi, Hsieh, 2017, Lian, Zhang, Hsieh, Huang, Liu, 2016, Liu, Chen, Chen, Hong, 2018）。以往的研究主要集中在使用函数值来近似梯度（Ge, Huang, Jin, & Yuan, 2015）和Hessian信息（Olivares, Moguerza, & Prieto, 2008），这些策略利用了精确的一阶（Lee et al., 2019）或更高阶信息（Nesterov, Polyak, 2006, Yu, Xu, & Gu）。此外，还研究了扰动和负曲率检测技术来帮助逃离鞍点（Akhavan, Chzhen, Pontil, Tsybakov, 2022, Duchi, Jordan, Wainwright, Wibisono, 2015, Shamir, 2017b）。

然而，依赖于无偏梯度估计和随机扰动或负曲率方向的现有算法需要大量的函数评估次数来逃离鞍点。首先，由零均值噪声引入的随机扰动需要指数级的迭代次数才能消除鞍点（Lucchi, Orvieto, & Solomou, 2021）。其次，梯度估计和Hessian矩阵近似分别需要O(d)和O(d²)次函数评估，导致每次迭代都需要大量的函数评估。这使得梯度估计和避免鞍点在计算上变得非常困难，尤其是在具有多个鞍点的高维非凸优化问题中（Du et al., 2017）。

为了说明各种优化方法的局限性，我们对以下鞍点问题进行了研究：$f(x,y)=x^2?y^2$以及猴子鞍点问题$f(x,y)=x^3?2x{y}^2$。我们比较了普通的梯度下降（GD）、扰动近似梯度下降（PAGD）、ZOGD-2pt、SPSA和仅需要8次迭代的2-SPSA。如图1所示，GD（蓝星）被困在鞍点（0,0）处。PAGD（红线）和ZOGD-2pt（绿线）使用有限差分方法和零均值噪声（均匀和高斯分布）来逃离鞍点。然而，由于它们估计的梯度接近零，PAGD和ZOGD-2pt的轨迹很难区分，这使它们保持在鞍点附近，类似于GD。此外，它们采用的随机搜索技术需要大量的迭代次数（Lucchi et al., 2021）来消除鞍点。相比之下，渐进式无偏梯度估计方法SPSA（青线）和扰动梯度估计方法2-SPSA（紫线）更有效地逃离了鞍点。尽管它们的梯度不如真实梯度准确，但它们提供了远离鞍点的明确方向。此外，所提出的算法2-SPSA比SPSA更快地收敛到局部最优解。

考虑到无偏梯度估计方法和随机扰动在逃离鞍点时带来的计算成本，寻找一个可以作为下降方向并快速逃离鞍点的估计梯度是很有前景的。在本文中，我们首先指出了对称伯努利扰动向量在逃离鞍点中的重要性，然后提出了一种扰动梯度估计方法。实验结果表明，扰动梯度估计方法可以显著减少逃离鞍点的计算负担。

本文的主要贡献如下：

•

我们提出了一种称为两步同时扰动随机逼近（2-SPSA）的扰动梯度估计方法来消除鞍点。

•

2-SPSA算法每次迭代只需要4次函数评估，与其它随维度d呈多项式增长的零阶优化算法相比，减少了函数评估次数。

•

实验结果表明，2-SPSA在逃离鞍点和寻找全局最优解方面优于其他零阶优化算法。

本文的其余部分组织如下。第2节介绍了鞍点和SOSP的概念，回顾了专注于逃离鞍点的现有工作，指出了现有工作的局限性，并介绍了一种随机梯度逼近方法SPSA。第3节详细介绍了所提出的扰动梯度方法——两步SPSA。第4节通过实验研究了2-SPSA在逃离和避免鞍点方面的有效性，以及在黑盒对抗攻击问题上的表现，证明了其在近似梯度和优于其他零阶优化方法方面的优势。最后，第5节总结了本文。

节选内容

鞍点和（?, γ）-SOSP

鞍点是函数景观中的一个临界点，在该点梯度为零，但Hessian矩阵既有正特征值也有负特征值，导致某些维度向上弯曲而其他维度向下弯曲（见图1）。二阶静止点概念用于区分鞍点和理想的临界点。SOSP是一个梯度为零且Hessian矩阵为半正定的临界点，这意味着所有特征值都是

动机和算法构建

在前面的章节中，我们强调了无偏梯度估计方法（或梯度下降方法、扰动梯度下降方法）以及随机扰动技术所带来的计算负担。因此，寻找一种更有效的扰动梯度估计方法来规避鞍点并减少函数值是很有前景的。无维度方法SPSA（Spall et al., 1992）可以用来生成

实验结果与分析

在本节中，我们进行了一系列数值实验，包括参数敏感性分析和扰动的效率分析，以实证验证所提出的2-SPSA算法的优势。为了提供全面的性能分析，我们将2-SPSA与一系列相关和有竞争力的基线算法进行了比较：

•

有限差分（FD）/梯度下降（GD）：这种方法使用中心差分方案来计算高度准确的梯度估计。虽然通常

结论

在本文中，我们首先分析了扰动梯度估计在逃离鞍点中的重要性，并介绍了扰动梯度估计（2-SPSA）算法。通过每次迭代仅进行四次函数评估，2-SPSA创建了一个高效且考虑曲率的搜索方向。实验结果表明，2-SPSA算法在逃离鞍点和以更少的函数评估次数达到SOSP方面表现出色

CRediT作者贡献声明

陈静静：概念化、方法论、软件、写作——原始草稿。刘三阳：监督、方法论、验证、写作——审阅与编辑。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。