强高概率二阶收敛的随机非凸优化
本研究讨论了使用第一阶梯度算法进行的非凸随机优化问题,其中梯度估计可能具有重尾特征,结果表明梯度剪裁,动量和归一化梯度下降的组合可以在高概率下收敛于关键点,特别适用于光滑损失的已知最佳速率,适用于任意光滑度规范,并针对克服该领域二阶光滑损失引发的问题进行讨论。
Jun, 2021
本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题,本文提出快速的随机算法,可获得常数迷你批量的收敛性。本文还使用这些算法的变种,证明了比批量近端梯度下降更快的收敛性,并在非凸、非光滑函数的一个子类中证明全局线性收敛率。
May, 2016
本文研究了梯度下降算法在非凸优化问题中的性能保证,发现梯度噪声对逃脱鞍点和到达二阶稳定点的效率起到了关键作用,提出了一个基于均方方法的替代方案来保证梯度噪声的相对方差较小就足以确保逃脱鞍点,而不需要注入其他噪声或采用全局分散噪声假设。
Aug, 2019
本文针对非凸非光滑问题提出新的算法稳定性度量方法,同时建立它们与梯度之间的量化关系,并使用采样确定算法导出了随机梯度下降算法和其自适应变种的误差界。
Jun, 2022
通过分析,本文展示了当总迭代次数足够大时,随机梯度下降法(SGD)的最终迭代中存在一个 ε- 稳定点,这是一个比现有结果更强的结论,并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度,同时对于目标函数和随机梯度的边界条件,我们恢复了经典的 O (1/√T) 渐进速率,此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说,并提出了一些有启发性的研究方向。
Oct, 2023
本文基于凸优化中函数是光滑和非光滑组合的形式,证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质,其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设,证明了一系列强、弱收敛性结果,并得到了期望意义下的 $O (1/n)$ 的有界性结果。
Mar, 2014
本文介绍了一种新的随机逼近方法 —— 随机梯度下降算法,用于解决非线性随机规划问题,并证明了该算法的复杂度和优化收敛速度,指出该算法在问题为凸问题时具有接近最优的收敛速度,同时优化了其大偏差特性,特别针对只有随机零阶信息可用的类模拟优化问题进行了改进。
Sep, 2013
本文提出了针对非凸和凸优化的零阶随机逼近算法,并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点,并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法,并讨论了它们的收敛率。
Sep, 2018