Feb, 2019

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

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

    本文针对优化算法问题，研究了一种AGD变体，通过使用一个启发式的Hamiltonian函数以及一个新的框架improve or localize，证明了其找到hessian-free的二阶稳定点的速度比GD更快，证明了其具有更好的收敛速度特性，加深了人们对加速算法和非凸优化的理解。

    Nov, 2017

  • 非凸优化中动量 SGD 的扩散近似理论

    本文通过对非凸优化问题的扩散逼近，分析了Momentum随机梯度下降算法的算法行为，发现该算法对于强鞍点的逃逸具有帮助，但在优化器的周围区域内妨碍了收敛（未进行步长退火或动量退火），本文的理论发现部分验证了MSGD在训练深度神经网络中的实证成功。

    Feb, 2018

  • 用随机梯度逃离鞍点

    本文研究了在某些非凸机器学习模型中，随机梯度沿负曲率方向的方差，并展示了这些方向上的随机梯度表现出强烈的分量；此外，本文提出了一种新的假设，根据这个假设，注入显式同方差噪声的普通随机梯度下降可以成功地替代梯度下降逃脱鞍点；最后，本文提出了基于相同假设的简单SGD步骤的第一个收敛率，此收敛率独立于问题的维度。

    Mar, 2018

  • SSRGD: 逃离鞍点的简单随机递归梯度下降

    我们分析了用于优化非凸问题的随机梯度算法及其中简单的 SSROD 算法，在此基础上证明了 SSROD 算法可以有效地寻找非凸问题中的局部最小值点，并给出了相关的复杂度分析。

    Apr, 2019

  • 使用随机梯度下降法找到稳定点的复杂度

    研究了随机梯度下降（SGD）算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度，结果表明，Ghadimi和Lan的上限不能得到改进，除非做出额外的假设，即使对于凸二次函数，也是如此；此外还表明，对于非凸函数，SGD最小化梯度的可行性需要根据所选择的最优性标准而定。

    Oct, 2019

  • 非凸世界中SGD的更好理论

    本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率，并在考虑多种采样策略和小批量大小的情况下，探讨有限和优化问题的影响。

    Feb, 2020

  • 一枚硬币的两面：未调节的 SGD 的局限性和自适应方法的威力

    本文探讨了随机梯度下降法与多项式衰减步长之间的关系，并证明无调谐的随机梯度下降法具有渐进最优的收敛速率，但需要面临指数级的平滑度常数；而规范化SGD、AMSGrad和AdaGrad方法可以在不知道平滑度参数和随机梯度边界条件的情况下消除梯度爆炸问题。

    May, 2023

  • 非凸优化的加速梯度算法：从严格鞍点的逃逸轨迹到局部极小值的收敛

    本文研究了加速梯度方法在光滑非凸函数上的行为，提出了一类Nesterov型加速方法，并通过显式和隐式分析证明了其能够避免滑点并收敛于局部最小值。

    Jul, 2023

  • 非光滑非凸优化中随机次梯度方法的收敛性保证

    本研究论文探讨了随机梯度下降（SGD）方法及其变种在训练非光滑激活函数构建的神经网络中的收敛性质，提出了一种新的框架，分别为更新动量项和变量分配不同的时间尺度。在一些温和条件下，我们证明了我们提出的框架在单一时间尺度和双时间尺度情况下的全局收敛性。我们展示了我们提出的框架包含了许多著名的SGD类型方法，包括heavy-ball SGD、SignSGD、Lion、normalized SGD和clipped SGD。此外，当目标函数采用有限和形式时，我们证明了基于我们提出的框架的这些SGD类型方法的收敛性质。特别地，在温和的假设条件下，我们证明了这些SGD类型方法以随机选择的步长和初始点找到了目标函数的Clarke稳定点。初步的数值实验表明了我们分析的SGD类型方法的高效性。

    Jul, 2023

  • 解密SGD非凸收敛的神话与传说

    通过分析，本文展示了当总迭代次数足够大时，随机梯度下降法（SGD）的最终迭代中存在一个 ε-稳定点，这是一个比现有结果更强的结论，并且可以在 SGD 的最终迭代中度量 ε-稳定点的密度，同时对于目标函数和随机梯度的边界条件，我们恢复了经典的 O(1/√T) 渐进速率，此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说，并提出了一些有启发性的研究方向。

    Oct, 2023