Nov, 2018

随机梯度算法的新收敛性特点

PDF
TL;DR本文对随机梯度下降法（SGD）的收敛性进行了分析，提出了一种新的假设随机梯度较真实梯度的范数更小的分析方法，并在多个情境下证明了 SGD 的收敛性，拓展了当前一类可达到收敛性的学习率。
stochastic gradient descentconvergence analysismachine learningdiminishing learning ratestrongly convex objective function
发现论文，激发创造
  • SGD 和 Hogwild!：在无需有界梯度假设的情况下收敛

    该研究论文讨论了随机梯度下降算法的收敛性分析，提出了一种在异步并行环境下使用降低学习率机制的算法，并证明了其收敛性。

    Feb, 2018

  • 解密 SGD 非凸收敛的神话与传说

    通过分析，本文展示了当总迭代次数足够大时，随机梯度下降法（SGD）的最终迭代中存在一个 ε- 稳定点，这是一个比现有结果更强的结论，并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度，同时对于目标函数和随机梯度的边界条件，我们恢复了经典的 O (1/√T) 渐进速率，此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说，并提出了一些有启发性的研究方向。

    Oct, 2023

  • 随机梯度下降在非凸问题中的几乎必然收敛

    本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析，首先证明了在广泛的步长策略范围内，SGD 生成的迭代序列保持有界并以概率 1 收敛，随后证明了 SGD 避开了严格的鞍点 / 流形的概率是 1，最后证明了算法在采用 Theta (1/n^p) 步长时收敛速度为 O (1/n^p)，这为调整算法步长提供了重要的指导建议，并且在 CIFAR 的 ResNet 架构中，展示了此启发式方法加速收敛的效果。

    Jun, 2020

  • 异步共享内存中随机梯度下降算法的收敛性

    本文研究并发训练中 Stochastic Gradient Descent 算法的收敛性，提出了在异步共享内存模型下的新收敛界限，同时指出了最大延迟和算法收敛速度之间的基本权衡关系。

    Mar, 2018

  • 随机梯度下降法在递减步长下期望收敛速率的紧凑维度无关下限

    研究随机梯度下降法（SGD）在强凸目标函数上的收敛性，证明了 ICML 2018 和 2019 提出的降低步长的速率序列在每次迭代后的收敛速度与我们的下限相差不到 32 倍，为最优状态；该下限相较于现有工作大约高出了因子 775×d，其中 d 是维度。

    Oct, 2018

  • （随机）梯度方法的统一最优分析

    证明在 L - 平滑度条件下，随机梯度下降的迭代收敛速度的数量级为 O (LR2exp [-(mu/4L) T]+sigma2/muT), 其中 sigma2 是随机噪声方差，且收敛速度与最佳已知的 GD 和 SGD 迭代复杂度匹配.

    Jul, 2019

  • 驯服野兽：Hogwild! 风格算法的统一分析

    本文通过马丁戈尔分析方法，研究了异步执行和低精度优化技术在随机梯度下降算法中的应用，包括推导了 Hogwild! 收敛速率、分析了非凸矩阵问题的异步 SGD 算法，以及设计了 Buckwild! 算法，并在现代硬件上进行了实验。

    Jun, 2015

  • 非凸区域中恒定步长随机梯度下降的分析：渐近正态性和偏差

    本研究探讨了非凸非光滑目标函数中常数步长随机梯度下降算法的渐近正态结果，结果表明只要非凸和非光滑目标函数满足耗散性特性，SGD 算法的迭代平均值就会渐近正态分布，该结果可用于构建对于使用 SGD 算法的非凸问题的置信区间。同时，本文通过对其与马尔可夫链的关系进行了详细地分析，还对目标函数的临界点与其期望值之间的偏差进行了表征。

    Jun, 2020

  • 随机梯度方法在梯度主导条件下的几乎必然收敛速率

    基于全局和局部梯度支配的随机梯度下降法收敛速度证明及其在监督学习和强化学习中的应用。

    May, 2024

  • 从群体损失的梯度流到随机梯度下降学习

    本文通过分析 Gradient Flow 在目标函数收敛时的性质，提供了 SGD 收敛的一般条件，研究了 Lyapunov potentials 与目标函数几何性质的关联，并给出了 SGD 收敛的保证，适用于一些复杂问题。

    Oct, 2022