非凸优化中随机梯度下降的二阶保证
本文研究了在某些非凸机器学习模型中,随机梯度沿负曲率方向的方差,并展示了这些方向上的随机梯度表现出强烈的分量;此外,本文提出了一种新的假设,根据这个假设,注入显式同方差噪声的普通随机梯度下降可以成功地替代梯度下降逃脱鞍点;最后,本文提出了基于相同假设的简单 SGD 步骤的第一个收敛率,此收敛率独立于问题的维度。
Mar, 2018
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
本文研究带有非凸随机函数的随机非凸优化,并提出一种称为 NCG-S 的新型更新步骤,可以在高概率下实现二阶收敛,所提出的随机算法是首个具有高概率二阶收敛和几乎是线性时间复杂度的方法。
Oct, 2017
研究用于找到凸凹函数鞍点的随机一阶方法的性能。我们提出了一种简单有效的正则化技术,稳定迭代并提供有意义的性能保证,即使域和梯度噪声与迭代的大小成线性关系(可能是无界的)。此外,我们还将算法应用于强化学习中的特定问题,在无偏扩展的平均奖励 MDP 中,即使没有先验知识,也能找到接近最优策略的性能保证。
Feb, 2024
本文研究梯度下降和随机梯度下降等算法在机器学习中的应用,分析了这些算法在非凸优化问题中收敛到驻点的情况,提出了变形的算法可以更高效地避免出现维数灾难,从而沟通了理论和实践。
Feb, 2019
本研究讨论了使用第一阶梯度算法进行的非凸随机优化问题,其中梯度估计可能具有重尾特征,结果表明梯度剪裁,动量和归一化梯度下降的组合可以在高概率下收敛于关键点,特别适用于光滑损失的已知最佳速率,适用于任意光滑度规范,并针对克服该领域二阶光滑损失引发的问题进行讨论。
Jun, 2021
本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点,收敛速率与梯度下降到一阶稳定点的收敛速率匹配,当所有鞍点都是非退化的时,所有的二阶稳定点都是局部最小值,该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点,并可直接应用于许多机器学习应用中,包括深度学习。
Mar, 2017
本文针对非凸非光滑问题提出新的算法稳定性度量方法,同时建立它们与梯度之间的量化关系,并使用采样确定算法导出了随机梯度下降算法和其自适应变种的误差界。
Jun, 2022
该研究探讨了基于梯度的优化算法在机器学习应用中的收敛速度、遗憾界限等指标以及其与稳定性保证之间的关系,并提供了更为通用的稳定性保证,以促进实时学习应用的安全可靠部署。
May, 2024