SSRGD: 逃离鞍点的简单随机递归梯度下降
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
本文针对优化算法问题,研究了一种 AGD 变体,通过使用一个启发式的 Hamiltonian 函数以及一个新的框架 improve or localize,证明了其找到 hessian-free 的二阶稳定点的速度比 GD 更快,证明了其具有更好的收敛速度特性,加深了人们对加速算法和非凸优化的理解。
Nov, 2017
本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点,收敛速率与梯度下降到一阶稳定点的收敛速率匹配,当所有鞍点都是非退化的时,所有的二阶稳定点都是局部最小值,该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点,并可直接应用于许多机器学习应用中,包括深度学习。
Mar, 2017
本文研究了梯度下降算法在非凸优化问题中的性能保证,发现梯度噪声对逃脱鞍点和到达二阶稳定点的效率起到了关键作用,提出了一个基于均方方法的替代方案来保证梯度噪声的相对方差较小就足以确保逃脱鞍点,而不需要注入其他噪声或采用全局分散噪声假设。
Aug, 2019
本研究研究了非凸优化中的鞍点问题,提出了一个通用的框架,该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外,还将研究结果扩展到了随机情形下,以更好地适应实际问题。
Sep, 2018
本研究针对非凸函数的优化问题,通过分析其严格鞍点特性,提出了一种可有效优化的解法 —— 随机梯度下降法,并给出了其多项式迭代次数的局部最小值收敛保证以及应用于正交张量分解问题上的全局收敛保证。
Mar, 2015
研究了随机梯度下降(SGD)算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度,结果表明,Ghadimi 和 Lan 的上限不能得到改进,除非做出额外的假设,即使对于凸二次函数,也是如此;此外还表明,对于非凸函数,SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。
Oct, 2019
我们考虑了一类在没有中央服务器的分散环境中的非光滑强凸 - 强凹鞍点问题。为了解决这类问题的共识形式,我们开发了一种不精确原始对偶混合梯度(inexact PDHG)算法,该算法允许通用梯度计算预言更新原始和对偶变量。我们首先研究了不精确 PDHG 与随机方差减少梯度(SVRG)预言的性能。我们的数值研究揭示出了 IPDHG 与 SVRG 预言的迭代过程中的初始保守进展现象。为了解决这个问题,我们提出了一个简单且有效的切换思想,即在更新的初始阶段使用广义随机梯度(GSG)计算预言来加快迭代过程,然后在适当的时机切换到 SVRG 预言。提出的算法被命名为带压缩的分散近端切换随机梯度方法(C-DPSSG),并被证明以线性速率收敛到一个 ε- 精确的鞍点解。除了提供高精度的解决方案外,我们的研究还揭示出利用 GSG 和 SVRG 预言的最佳收敛阶段使 C-DPSSG 非常适合获得低 / 中等准确度的解决方案,这对某些应用非常有用。对两个基准机器学习应用进行的数值实验显示了 C-DPSSG 的竞争性能,验证了我们的理论发现。
Sep, 2023