Feb, 2019

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

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

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

    Sep, 2018

  • 如何高效地逃离鞍点

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

    Mar, 2017

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

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

    Feb, 2020

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

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

    Oct, 2023

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

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

    Apr, 2019

  • 机器学习的非凸优化：梯度、随机性和鞍点

    本文研究梯度下降和随机梯度下降等算法在机器学习中的应用，分析了这些算法在非凸优化问题中收敛到驻点的情况，提出了变形的算法可以更高效地避免出现维数灾难，从而沟通了理论和实践。

    Feb, 2019

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

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

    Oct, 2019

  • 加速梯度下降比梯度下降更快地逃离鞍点

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

    Nov, 2017

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

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

    Aug, 2019

  • 非凸随机优化下的下限界

    采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

    Dec, 2019