Sep, 2019

误差反馈框架：延迟梯度和压缩通信下提高 SGD 速率

PDF
TL;DR本文研究了在平滑拟凸和非凸函数上的随机梯度下降法（SGD）进行延迟更新，并得出了简洁的非渐近收敛速度。我们证明了在所有情况下收敛速度的由两个项组成：（i）一个随机项，不受延迟的影响，和（ii）一个更高阶的确定性项，只是通过延迟线性减缓。因此，在存在噪声的情况下，延迟的影响在几次迭代后变得微不足道，算法以与标准 SGD 相同的最优速度收敛。我们进一步展示了在使用层压梯度（compressed gradients）进行错误补偿时以及在多个节点上做本地 SGD 之后通信的情况下，与现有最佳算法相比，我们得到了更好的结果。这些结果表明 SGD 对于压缩和 / 或延迟的随机梯度更新是具有鲁棒性的。这对于分布式并行实现特别重要，因为异步和通信高效方法是实现多设备优化的线性加速的关键。
stochastic gradient descentconvergence ratesdelayed updatescompressed gradientsdistributed parallel implementations
发现论文，激发创造
  • 带有延迟更新的随机梯度下降的紧密收敛分析

    本文提供基于生成函数的优化算法收敛性分析技巧，研究了梯度下降以及随机梯度下降在二次函数上的有限时间收敛性，证明了在有随机噪声的情况下，延迟对算法的影响可以被忽略，且在分布式优化问题上，加入延迟不会影响性能，且可和同步方法相媲美。

    Jun, 2018

  • 线性收敛误差补偿 SGD

    本文提出了一种统一的分析分布式 SGD 各种变体的方法，涵盖了不同的量化 SGD、误差补偿 SGD 和延迟更新 SGD 变体，并通过一个定理推导了其所有方法的复杂度结果。在此基础上，我们开发了 16 种新的方法，其中包括第一种基于误差反馈和梯度差分量化的 EC-SGD-DIANA 方法和第一种具有误差反馈和方差缩减的分布式随机方法 EC-LSVRG-DIANA。

    Oct, 2020

  • 延迟反馈下的学习：隐含适应梯度延迟

    针对多台异步运行的机器共同访问的内存环境下的随机凸优化问题，我们提出了一种鲁棒的约束训练方法，其非渐近收敛保证不依赖于更新延迟、目标平滑度和梯度方差的先验知识。与此相反，现有方法严重依赖于这些先验知识，因此不适用于所有共享资源的计算环境，如云和数据中心。与现有方法不同，我们的方法可以隐含地适应动态分配机器所带来的延迟变化。

    Jun, 2021

  • 随机梯度下降法与有偏梯度的收敛性

    分析了带偏差随机梯度方法的复杂性，特别是在非凸函数上的收敛性及更好的速率，探究了偏差大小对达到的准确性和收敛速率的影响，阐述了偏差梯度在分布式学习和无导数优化中的应用广泛性。

    Jul, 2020

  • 压缩梯度的分布式学习

    该论文提出了一种针对大规模机器学习的分布式梯度方法的统一分析框架，通过非渐进界限来推导了几种优化算法的收敛速率和信息交换，并得到了步长的显式表达式，表征了异步度和压缩精度如何影响迭代和通信复杂性保证，数值结果证实了限制信息交换下不同梯度压缩算法的收敛性能，以及快速收敛确实是可能的。

    Jun, 2018

  • 利用压缩更新的时序差分学习：误差反馈与强化学习相遇

    本文研究了带有压缩算子的强化学习过程对经典时间差分学习算法的影响，并证明了在误差反馈机制的作用下，以及与线性函数逼近和马尔可夫采样一起使用时，压缩的时间差分算法可以与 SGD 相似地具有非渐近理论保证。此外，本文还扩展了结果，提出了多智能体 TD 学习的线性收敛速度快速提升的证明。

    Jan, 2023

  • 延迟随机梯度下降的普适性理解探究

    基于生成函数分析工具，我们研究了异步延迟 SGD 的泛化误差上界，结果表明异步延迟减少了延迟 SGD 算法的泛化误差。

    Aug, 2023

  • 非强凸最小二乘问题的加速随机梯度下降

    本文提出了一种基于加速梯度下降的新随机逼近算法，该算法在非强凸情况下取得了最佳预测误差率，并在加速遗忘初始条件方面达到了最优效果，同时在算法的平均迭代次数和最终迭代次数上均提供了收敛结果，该算法还在无噪声环境下提供了一个匹配下界，展示了我们算法的最优性。

    Mar, 2022

  • 分布式延迟随机优化

    该文主要研究基于梯度的优化算法中的延迟随机梯度信息的收敛性，以及如何应用于分布式优化算法中克服通信瓶颈和同步要求的问题，结果表明在平滑随机问题中，延迟是渐近可以忽略的，且能达到最优收敛效果。

    Apr, 2011

  • 强健且通信高效的协作学习

    本文提出了一种名为 QuanTimed-DSGD 的新型分布式渐进优化算法，通过调整每个节点在算法每一步中本地计算梯度的截止时间和节点间交换量化本地模型的机制来解决分布式计算中经常遇到的滞后和通信效率低的问题，数值评估结果表明该算法与最先进的分布式优化方法相比，运行时间可提速至多 3 倍。

    Jul, 2019