NeurIPS 2021 | 用简单的梯度下降算法逃离鞍点

非凸优化（nonconvex optimization）是优化理论的核心研究领域之一，因为许多前沿机器学习问题都具有非凸的损失函数，包括深度神经网络、主成分分析、张量分解等。在最坏的情况下，找到非凸函数的全局最小值属于 NP-hard 问题。不过最近的许多实证与理论工作都表明，对于大量有着广泛应用的机器学习问题，所有局部最小值几乎都与全局最小值相等。因此，许多理论工作专注于寻找局部最优解而不是全局最优解。在这些工作中，鞍点成为了设计算法的主要障碍，因为高维的非凸目标函数可能含有大量鞍点，且它们往往具有远大于全局最优解的函数值。

因此，逃离鞍点是非凸优化理论中最重要的问题之一。具体来说，对于二阶可导的 维函数 ，我们的目标是找到一个 近似的局部最优解。近期的实证研究表明，现实世界中复杂的机器学习问题往往可以被简单的算法有效解决，这些算法在实践中也可以更容易地实现与维护。与之相反，具有嵌套循环结构的优化算法在问题规模增长时往往具有较大的开销，或存在调参不便、数值稳定性较弱等问题，使它们较难找到实际应用。出于这一考量，现有的逃离鞍点的研究多聚焦于开发基于梯度下降的，具有单循环结构的简单优化算法。在本文之前，最先进的算法为 Jin 等人提出的扰动加速梯度下降算法（perturbed accelerated gradient descent, PAGD），它可以在 次循环内找到一个 近似的局部最优解。