非凸世界中 SGD 的更好理论
通过分析,本文展示了当总迭代次数足够大时,随机梯度下降法(SGD)的最终迭代中存在一个 ε- 稳定点,这是一个比现有结果更强的结论,并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度,同时对于目标函数和随机梯度的边界条件,我们恢复了经典的 O (1/√T) 渐进速率,此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说,并提出了一些有启发性的研究方向。
Oct, 2023
本文研究证明了随机梯度下降在非凸学习中,无需统一梯度有界性假设也能达到最优收敛率的情况,并在一定程度上对于一般非凸目标函数和梯度主导的目标函数实现了几乎必然收敛。特别地,在方差为零的情况下可以得到线性收敛。
Feb, 2019
本文研究了随机梯度下降(SGD)在优化非凸函数方面的应用,提出了一些收敛理论,说明了在满足结构性假设的非凸问题中,SGD 能够收敛到全局最小值,分析过程基于一个期望残差条件,相比之前的假设更加宽松。
Jun, 2020
本文研究梯度下降和随机梯度下降等算法在机器学习中的应用,分析了这些算法在非凸优化问题中收敛到驻点的情况,提出了变形的算法可以更高效地避免出现维数灾难,从而沟通了理论和实践。
Feb, 2019
本文探讨了在没有光滑假设的情况下,以及通过运行平均方案将 SGD 迭代转换为具有最佳优化精度的解决方案的性能,并证明了对于凸非光滑目标函数,最后一个 SGD 迭代的次优性的程度随 T 的轮次按 O(log(T)/sqrt(T))缩放,对于非光滑强凸情况,次优性的程度随 T 按 O(log(T)/ T)缩放。此外,本文提出了一种新的简单平均方案,并提供了一些实验说明。
Dec, 2012
本文研究了节点网络上的去中心化在线随机非凸优化。通过将梯度跟踪技术集成到去中心化随机梯度下降中,我们证明了该算法具有一定的优势,并分析了其有效性和性能。同时,对于满足 Polyak-Lojasiewics 条件的全局非凸函数,我们确定了 GT-DSGD 的线性收敛性,并且在几乎每条路径上具有最优的全局亚线性收敛速度。
Aug, 2020
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
研究了随机梯度下降(SGD)算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度,结果表明,Ghadimi 和 Lan 的上限不能得到改进,除非做出额外的假设,即使对于凸二次函数,也是如此;此外还表明,对于非凸函数,SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。
Oct, 2019
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023
本研究探讨了非凸非光滑目标函数中常数步长随机梯度下降算法的渐近正态结果,结果表明只要非凸和非光滑目标函数满足耗散性特性,SGD 算法的迭代平均值就会渐近正态分布,该结果可用于构建对于使用 SGD 算法的非凸问题的置信区间。同时,本文通过对其与马尔可夫链的关系进行了详细地分析,还对目标函数的临界点与其期望值之间的偏差进行了表征。
Jun, 2020