该文主要研究基于梯度的优化算法中的延迟随机梯度信息的收敛性,以及如何应用于分布式优化算法中克服通信瓶颈和同步要求的问题,结果表明在平滑随机问题中,延迟是渐近可以忽略的,且能达到最优收敛效果。
Apr, 2011
该研究探讨并分析了实际分布式计算网络情况下的延迟梯度模型,允许参数更新对实际延迟进行敏感处理以产生更大的步长,从而在保持相同渐近复杂度的同时实现更快收敛,针对包含数十亿个数据和特征的真实数据集展开分布式实验,并取得鼓舞人心的改进。
Aug, 2015
本文提供基于生成函数的优化算法收敛性分析技巧,研究了梯度下降以及随机梯度下降在二次函数上的有限时间收敛性,证明了在有随机噪声的情况下,延迟对算法的影响可以被忽略,且在分布式优化问题上,加入延迟不会影响性能,且可和同步方法相媲美。
Jun, 2018
基于生成函数分析工具,我们研究了异步延迟 SGD 的泛化误差上界,结果表明异步延迟减少了延迟 SGD 算法的泛化误差。
Aug, 2023
本文表明,渐进地,完全异步的随机梯度程 序可以在几乎与标准随机梯度程 序的渐进最优性相同的条件下实现解决凸优化问题的最优(甚至是常数因子)收敛率。大体而言,随机近似方案固有的噪音支配了任何来自异步的噪音。我们还提供了经验性 证据,证明了异步、并行的随机优化方案的强大性能,这表明随机近似问题固有的稳健性允许更快的并行和异步解决方法。
采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界,使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型,证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型,我们证明了 ε^ -3 个查询的下界,建立了最近提出的方差缩减技术的最优性。
Dec, 2019
针对多台异步运行的机器共同访问的内存环境下的随机凸优化问题,我们提出了一种鲁棒的约束训练方法,其非渐近收敛保证不依赖于更新延迟、目标平滑度和梯度方差的先验知识。与此相反,现有方法严重依赖于这些先验知识,因此不适用于所有共享资源的计算环境,如云和数据中心。与现有方法不同,我们的方法可以隐含地适应动态分配机器所带来的延迟变化。
Jun, 2021
研究了随机梯度下降(SGD)算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度,结果表明,Ghadimi 和 Lan 的上限不能得到改进,除非做出额外的假设,即使对于凸二次函数,也是如此;此外还表明,对于非凸函数,SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。
Oct, 2019
研究了非平稳环境下具任意延迟的在线凸优化问题,提出了一个简单的算法 DOGD,通过运用多个学习率的 DOGD,并跟踪最佳 one 的延迟性能,将动态遗憾边界降至 O (根号下 d*T*(P_T+1)) 和 O (根号下 S (1+P_T)),并毫无例外地证明了这是最优的。
May, 2023
本文研究了在平滑拟凸和非凸函数上的随机梯度下降法(SGD)进行延迟更新,并得出了简洁的非渐近收敛速度。我们证明了在所有情况下收敛速度的由两个项组成:(i)一个随机项,不受延迟的影响,和(ii)一个更高阶的确定性项,只是通过延迟线性减缓。因此,在存在噪声的情况下,延迟的影响在几次迭代后变得微不足道,算法以与标准 SGD 相同的最优速度收敛。我们进一步展示了在使用层压梯度(compressed gradients)进行错误补偿时以及在多个节点上做本地 SGD 之后通信的情况下,与现有最佳算法相比,我们得到了更好的结果。这些结果表明 SGD 对于压缩和 / 或延迟的随机梯度更新是具有鲁棒性的。这对于分布式并行实现特别重要,因为异步和通信高效方法是实现多设备优化的线性加速的关键。
Sep, 2019