Nov, 2017

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

PDF
TL;DR本文针对优化算法问题，研究了一种 AGD 变体，通过使用一个启发式的 Hamiltonian 函数以及一个新的框架 improve or localize，证明了其找到 hessian-free 的二阶稳定点的速度比 GD 更快，证明了其具有更好的收敛速度特性，加深了人们对加速算法和非凸优化的理解。
nesterov's accelerated gradient descentmomentum methodsoptimizationgradient descentstationary point
发现论文，激发创造
  • 重新审视归一化梯度下降：快速逃逸鞍点

    本文研究了优化问题中经典梯度下降方法的自然改进版，即归一化梯度下降，特别关注连续时间下降过程，发现 NGD 能够快速跳出鞍点，几乎不会收敛于鞍点。研究结果可以应用到全局收敛时间的界定。

    Nov, 2017

  • 加速额外梯度下降：一种新的加速一阶方法

    提出了一种新的加速一阶方法 (AXGD)，采用了预测 - 校正方法，解决了凸 - 凹鞍点问题，通过隐式欧拉离散化构建了加速连续时间动态模型，并通过原始 - 对偶视角进行了分析，对于其他类别的目标也能够达到最佳收敛速度。

    Jun, 2017

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

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

    Feb, 2019

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

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

    Jul, 2023

  • 如何高效地逃离鞍点

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

    Mar, 2017

  • 归一化之力：更快速地逃离鞍点

    通过选择合适的参数和注入噪音，我们分析了 Normalized Gradient Descent（NGD）这个非凸优化启发式方法，表明此方法能够逃避鞍点，并且证明了 NGD 收敛到局部最小值，而且 NGD 的收敛速度比 Ge 等人 2015 年提出的最快的一阶算法更快，我们将这个方法应用到在线张量分解问题上，并证明了在这个问题中，鞍点逃逸导致收敛到全局最小值。

    Nov, 2016

  • 梯度下降法在逃离鞍点时可能需要指数级的时间

    本文研究了梯度下降法遇到鞍点问题，提出加入微扰可以提高非凸优化的效率，其在理论上和实验上均得到了支持。

    May, 2017

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

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

    Apr, 2019

  • Convex Until Proven Guilty”: 非凸函数上无维度的梯度下降加速

    本研究介绍了一种新的 Nesterov 加速梯度下降法的变体，以应对光滑非凸函数的最小化问题，证明其收敛速度可以接近凸函数，在处理非凸函数方面具有优异的性能，并在此基础上提出了一种基于负曲率的证明非凸性的方法，在具有 Lipschitz 连续梯度和黑塞矩阵的情况下，可以在较少的梯度和函数计算次数内找到目标点。

    May, 2017

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

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

    Feb, 2019