Nov, 2017

逃离近乎线性时间的鞍点的一阶随机算法

PDF
TL;DR本文提供了一种新的噪声加入技术的视角，即将噪声添加到一阶信息中可以帮助从 Hessian 矩阵中提取负曲率，并通过分析一个简单的一阶过程提供了此视角的正式推理，然后提出了一种基于此技术和现有算法的一阶随机算法，实现了以几乎线性的时间复杂度（与问题的维度有关）找到接近于二阶稳定点的解的目标，从而在随机非凸优化上取得了最佳理论结果，甚至与凭借二阶信息的现有随机算法相媲美。
saddle pointshessian matrixnoise-adding techniquestochastic algorithmsnon-convex optimization
发现论文，激发创造
  • 逃离鞍点的通用方法

    本文介绍了一种通用框架，该框架在最小化 Hessian 基础计算的同时，能够收敛到二阶临界点，侧重于解决非凸优化中的关键问题：鞍点。经实证，该策略具有较好的实际性能。

    Sep, 2017

  • 如何高效地逃离鞍点

    本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点，收敛速率与梯度下降到一阶稳定点的收敛速率匹配，当所有鞍点都是非退化的时，所有的二阶稳定点都是局部最小值，该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点，并可直接应用于许多机器学习应用中，包括深度学习。

    Mar, 2017

  • 约束优化中逃离鞍点

    本研究研究了非凸优化中的鞍点问题，提出了一个通用的框架，该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外，还将研究结果扩展到了随机情形下，以更好地适应实际问题。

    Sep, 2018

  • 基于牛顿法的非凸优化算法：快速躲避鞍点

    本文介绍一种修改了牛顿法更新方式的二阶方法，通过替换海森矩阵的负特征值为绝对值，并使用其截断版本来考虑目标的曲率，以获得比随机梯度下降更快的局部最小值收敛速度。

    Jul, 2017

  • 非凸随机零阶优化：处理约束、高维度和鞍点

    本文提出了针对非凸和凸优化的零阶随机逼近算法，并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点，并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法，并讨论了它们的收敛率。

    Sep, 2018

  • 非凸随机梯度下降逃离鞍点的尖锐分析

    本文将通过对随机梯度下降进行深入分析，证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时，SGD 能够在 O（ε^ -3.5）次随机梯度计算中逃离鞍点并找到（ε，O（ε^ 0.5））- 近似二阶稳定点，从而推翻了 SGD 至少需要 O（ε^ - 4）的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配，如 Nesterov 的动量加速，负曲率搜索，以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解，并可潜在地推广到广泛的随机优化算法类。

    Feb, 2019

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

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

    Oct, 2019

  • 非凸优化中随机梯度下降的二阶保证

    本文研究了梯度下降算法在非凸优化问题中的性能保证，发现梯度噪声对逃脱鞍点和到达二阶稳定点的效率起到了关键作用，提出了一个基于均方方法的替代方案来保证梯度噪声的相对方差较小就足以确保逃脱鞍点，而不需要注入其他噪声或采用全局分散噪声假设。

    Aug, 2019

  • 非凸优化中逃离高阶鞍点的高效方法

    本文提出了一种使用高阶导数的算法，能够逃离高维复杂的鞍点结构，并保证能够收敛到三阶局部最优解，是现有技术的两倍，同时也证明了进一步寻找四阶局部最优解是 NP-hard 的。

    Feb, 2016

  • 一阶方法几乎总是避免鞍点

    本研究表明，几乎所有初始化的一阶方法都可以避免鞍点问题，并且这种算法可以通过动态系统视角来研究，通过合适实例化的 Stable Manifold Theorem 进行全局稳定性分析。因此，除了初始化外，无需访问二阶导数信息或随机性即可证明避免鞍点。

    Oct, 2017