通过马尔可夫链实现常数步长 SGD 的收敛和集中特性
本研究探讨了非凸非光滑目标函数中常数步长随机梯度下降算法的渐近正态结果,结果表明只要非凸和非光滑目标函数满足耗散性特性,SGD 算法的迭代平均值就会渐近正态分布,该结果可用于构建对于使用 SGD 算法的非凸问题的置信区间。同时,本文通过对其与马尔可夫链的关系进行了详细地分析,还对目标函数的临界点与其期望值之间的偏差进行了表征。
Jun, 2020
本文应用马尔科夫链理论,通过随机梯度下降(SGD)算法来计算目标函数,并提供了一种新的 Richardson-Romberg 外推方法来优化 SGD 算法,通过渐进展开分析,总结出其与初始条件、噪声和步长的相关性。
Jul, 2017
通过分析,本文展示了当总迭代次数足够大时,随机梯度下降法(SGD)的最终迭代中存在一个 ε- 稳定点,这是一个比现有结果更强的结论,并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度,同时对于目标函数和随机梯度的边界条件,我们恢复了经典的 O (1/√T) 渐进速率,此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说,并提出了一些有启发性的研究方向。
Oct, 2023
本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析,首先证明了在广泛的步长策略范围内,SGD 生成的迭代序列保持有界并以概率 1 收敛,随后证明了 SGD 避开了严格的鞍点 / 流形的概率是 1,最后证明了算法在采用 Theta (1/n^p) 步长时收敛速度为 O (1/n^p),这为调整算法步长提供了重要的指导建议,并且在 CIFAR 的 ResNet 架构中,展示了此启发式方法加速收敛的效果。
Jun, 2020
本文从随机过程的角度出发,论证了常数学习率随机梯度下降算法(constant SGD)可用作一种近似贝叶斯推断算法,其可优化模型中的超级参数,同时分析了 Langevin Dynamics 和 Stochastic Gradient Fisher Scoring 的近似误差以及 Polyak 平均算法的最优性。在此基础上,提出了一种可扩展的近似马尔科夫链蒙特卡罗(MCMC)算法,即平均随机梯度采样算法(Averaged Stochastic Gradient Sampler)。
Apr, 2017
证明在 L - 平滑度条件下,随机梯度下降的迭代收敛速度的数量级为 O (LR2exp [-(mu/4L) T]+sigma2/muT), 其中 sigma2 是随机噪声方差,且收敛速度与最佳已知的 GD 和 SGD 迭代复杂度匹配.
Jul, 2019
本文对随机梯度下降法(SGD)的收敛性进行了分析,提出了一种新的假设随机梯度较真实梯度的范数更小的分析方法,并在多个情境下证明了 SGD 的收敛性,拓展了当前一类可达到收敛性的学习率。
Nov, 2018
提出 SGD 收敛的通用简单定理,该定理可描述与特定概率法相关的各种 SGD 变体的收敛性。该定理是第一次执行这种分析,大多数 SGD 的变体以前从未明确考虑过。论文依赖于最近引入的期望平滑性的概念,并不依赖于随机梯度方差的统一界限。
Jan, 2019
本研究论文探讨了随机梯度下降(SGD)方法及其变种在训练非光滑激活函数构建的神经网络中的收敛性质,提出了一种新的框架,分别为更新动量项和变量分配不同的时间尺度。在一些温和条件下,我们证明了我们提出的框架在单一时间尺度和双时间尺度情况下的全局收敛性。我们展示了我们提出的框架包含了许多著名的 SGD 类型方法,包括 heavy-ball SGD、SignSGD、Lion、normalized SGD 和 clipped SGD。此外,当目标函数采用有限和形式时,我们证明了基于我们提出的框架的这些 SGD 类型方法的收敛性质。特别地,在温和的假设条件下,我们证明了这些 SGD 类型方法以随机选择的步长和初始点找到了目标函数的 Clarke 稳定点。初步的数值实验表明了我们分析的 SGD 类型方法的高效性。
Jul, 2023