Sep, 2023

流式数据上增量聚合梯度方法的线性加速

PDF
TL;DR本论文研究了一种用于大规模分布式优化的增量聚合梯度（IAG）方法，证明了基于流式数据的随机变体的 IAG 方法在强凸优化情况下实现了线性加速，并且即使在数据样本在工作者之间分布不均匀的情况下，该方法仍可以保证达到最优解的期望平方距离以 O ((1+T)/(nt)) 的速率衰减。
发现论文，激发创造
  • 非凸优化的快速增量方法

    本文分析了一种用于优化非凸问题的快速递增聚合梯度方法，在递增一阶预言框架中分析了 SAGA 算法，并表明它比梯度下降和随机梯度下降更快地收敛到稳定点。此外，我们还讨论了 Polyak 特殊类的问题，针对这类问题，SAGA 方法的收敛速度为线性收敛到全局最优解。最后，我们分析了实际有用的 SAGA 正则化和小批量变体。据我们所知，这篇论文提出了第一篇关于递增聚合梯度方法快速收敛的分析。

    Mar, 2016

  • 非凸非线性随机规划的加速梯度方法

    该论文将 Nesterov 的加速梯度方法推广到非凸和可能的随机优化问题中，证明该方法可以最优地解决一般的非凸光滑优化问题，并可应用于重要类的复合优化问题和非凸随机优化问题，是文献中第一次确立了 AG 方法解决非凸非线性规划的收敛性。

    Oct, 2013

  • 随机动量方法在 Wasserstein 距离中的加速线性收敛

    研究了 Polyak 重球法，Nesterov 加速梯度以及加速投影梯度法等动量方法在梯度噪声情况下的收敛性，证明了其在小于一定噪声上限后仍能保持加速线性速率的收敛性并且提出了步长、动量参数和噪声幅度与加速线性速率之间的关系模型。此外，还对 APG 方法和弱凸函数进行了扩展研究。

    Jan, 2019

  • LAG：用于通信高效分布式学习的惰性聚合梯度

    本文提出了一种新类的渐变方法，用于分布式机器学习，可以通过自适应地跳过梯度计算来降低通信和计算成本，并经过了数值实验的验证。

    May, 2018

  • 去中心化非凸优化的快速随机增量梯度方法

    该论文研究了关于具有本地数据样本批量的节点网络的分散式非凸有限和最小化问题，并提出了一种名为 GT-SAGA 的单时间尺度随机增量梯度法，通过利用节点级方差、网络级梯度跟踪等手段优化它的性能，这种方法在特定条件下起到了优于现有方法性能的作用，该文对此进行了详细分析。

    Nov, 2020

  • 加速分布式聚合优化

    本文研究了在网络中分布式汇聚优化问题，提出了结合重球和 Nesterov 加速方法的分布式汇聚梯度跟踪的两个新算法 DAGT-HB 和 DAGT-NES，分析这两个算法在目标函数光滑，强凸且参数选择在一定范围内时，能以全局 R 线性收敛速度收敛到最优解，通过最优放置问题的数值实验验证了算法的有效性和优越性。

    Apr, 2023

  • 具有线性收敛速率的循环增量方法的可证明优越性超越梯度下降

    该论文介绍了一种名为 Double Incremental Aggregated Gradient (DIAG) 的优化方法，可以在大规模机器学习问题中应用，并证明了它的收敛速度优于 Gradient Descent 方法。

    Nov, 2016

  • 基于插值的随机加速梯度下降算法的快速收敛

    我们在插值条件下证明了随机 Nesterov 加速的新的收敛速度。不同于以往的分析，我们的方法可以加速任何在期望中取得足够进展的随机梯度方法。证明使用估计序列框架进行，适用于凸函数和强凸函数，并且可以轻松推广到满足强生长条件的加速 SGD。在这种特殊情况下，我们的分析将强生长常数的依赖性从 ρ 减小到√ρ，相对于以前的工作来说，这一改进相当于最坏情况下条件数的平方根，并解决了对于随机加速的保证可能不如 SGD 的批评。

    Apr, 2024

  • 并行平均随机梯度算法收敛率

    介绍了一种并行的平均随机梯度算法，能够高效地递归处理高维空间中的大样本数据，并给出了强凸目标和局部强凸目标的平均收敛速度和渐近正态性。

    Oct, 2017

  • AsGrad: 异步 SGD 算法的锐利统一分析

    异步类型算法在异构设置中被分析，提出了统一的收敛理论，并介绍了基于工人洗牌的新型异步方法，数值评估支持理论发现并展示了该方法的良好实际性能。

    Oct, 2023