本文设计了一种随机算法,使用 O (ε^{-3.25}) 次反向传播来训练任何平滑神经网络到 ε- 近似局部极小值,并能够在不需要凸梯度下降的情况下,以速率 O (ε^{-3.25}) 找到任何平滑非凸函数的 ε- 近似局部极小值。
Aug, 2017
本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率,并在考虑多种采样策略和小批量大小的情况下,探讨有限和优化问题的影响。
Feb, 2020
通过分析,本文展示了当总迭代次数足够大时,随机梯度下降法(SGD)的最终迭代中存在一个 ε- 稳定点,这是一个比现有结果更强的结论,并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度,同时对于目标函数和随机梯度的边界条件,我们恢复了经典的 O (1/√T) 渐进速率,此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说,并提出了一些有启发性的研究方向。
Oct, 2023
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
通过利用指数步长和随机线性搜索等技术,使得随机梯度下降算法适应不同噪声水平和问题相关的常数,可以在强凸函数的条件下,取得与理论最优相近的收敛速度,同时能够有效地处理噪声和数据不凸的情况。
Oct, 2021
研究了随机梯度下降(SGD)算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度,结果表明,Ghadimi 和 Lan 的上限不能得到改进,除非做出额外的假设,即使对于凸二次函数,也是如此;此外还表明,对于非凸函数,SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。
Oct, 2019
本文提出了使用混合随机估算器设计的混合随机梯度算法来解决非凸期望问题,该算法可以获得更好的复杂度,同时考虑不同的扩展,如使用自适应步长和不同的迭代方式。在使用两个非凸模型进行了多个数据集上的比较。
May, 2019
本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析,首先证明了在广泛的步长策略范围内,SGD 生成的迭代序列保持有界并以概率 1 收敛,随后证明了 SGD 避开了严格的鞍点 / 流形的概率是 1,最后证明了算法在采用 Theta (1/n^p) 步长时收敛速度为 O (1/n^p),这为调整算法步长提供了重要的指导建议,并且在 CIFAR 的 ResNet 架构中,展示了此启发式方法加速收敛的效果。
Jun, 2020
采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界,使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型,证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型,我们证明了 ε^ -3 个查询的下界,建立了最近提出的方差缩减技术的最优性。
Dec, 2019
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019