本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
本文介绍了一种通用框架,该框架在最小化 Hessian 基础计算的同时,能够收敛到二阶临界点,侧重于解决非凸优化中的关键问题:鞍点。经实证,该策略具有较好的实际性能。
Sep, 2017
本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点,收敛速率与梯度下降到一阶稳定点的收敛速率匹配,当所有鞍点都是非退化的时,所有的二阶稳定点都是局部最小值,该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点,并可直接应用于许多机器学习应用中,包括深度学习。
Mar, 2017
我们提出了一种使用 Hessian 矩阵 - 向量积的方差约简二阶方法,其样本复杂度为~O (ε^(-3)),并收敛于近似二阶稳定点 (SOSP)。该方法通过使用 HVP 项在不使用 IS 权重的情况下改善了达到近似 SOSPs 的最佳已知样本复杂度的速率,实验结果表明该算法优于现有技术,并对随机种子变化更稳健。
Nov, 2023
本文提供了一种新的噪声加入技术的视角,即将噪声添加到一阶信息中可以帮助从 Hessian 矩阵中提取负曲率,并通过分析一个简单的一阶过程提供了此视角的正式推理,然后提出了一种基于此技术和现有算法的一阶随机算法,实现了以几乎线性的时间复杂度(与问题的维度有关)找到接近于二阶稳定点的解的目标,从而在随机非凸优化上取得了最佳理论结果,甚至与凭借二阶信息的现有随机算法相媲美。
Nov, 2017
本研究提出一种基于强化学习的优化方法,并使用二阶导数的技术证明了其收敛到二阶稳定点,从而避免了算法陷入鞍点或局部最小值。
Dec, 2020
本文介绍一种修改了牛顿法更新方式的二阶方法,通过替换海森矩阵的负特征值为绝对值,并使用其截断版本来考虑目标的曲率,以获得比随机梯度下降更快的局部最小值收敛速度。
Jul, 2017
本文提出了一种使用高阶导数的算法,能够逃离高维复杂的鞍点结构,并保证能够收敛到三阶局部最优解,是现有技术的两倍,同时也证明了进一步寻找四阶局部最优解是 NP-hard 的。
Feb, 2016
文章介绍了一种面向凸 - 凹鞍点问题的方法,使用梯度有限差分进行随机逼近,在某些条件下可以将所需的 oracle 调用次数降低至原来的 1/(log n)倍
May, 2020
我们分析了用于优化非凸问题的随机梯度算法及其中简单的 SSROD 算法,在此基础上证明了 SSROD 算法可以有效地寻找非凸问题中的局部最小值点,并给出了相关的复杂度分析。
Apr, 2019