Mar, 2016

非凸优化的快速增量方法

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

    介绍了一种新的优化方法 ——SAGA，它是在最近提出的一组具有快速线性收敛率的增量梯度算法：SAG、SDCA、MISO 和 SVRG 的基础上提出的。SAGA 改进了 SAG 和 SVRG 的理论，具有更好的理论收敛率，并支持在规则化器上使用近端算子的复合目标。与 SDCA 不同，SAGA 直接支持非强凸问题，并且适应于问题的任何内在强凸性。 我们给出了实验结果，表明我们的方法的有效性。

    Jul, 2014

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

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

    Nov, 2020

  • 一种简单实用的有限和加速方法

    该研究提出了一种针对小批量优化问题的新优化方法 SAGA，通过引入一种步长参数，在强凸光滑问题上获得了加速收敛率，同时应用于分割算子方法难以解决的许多领域。

    Feb, 2016

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

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

    Oct, 2013

  • 任意采样的 SAGA

    通过提出一种新的 SAGA 变体，并构建新的随机 Lyapunov 函数，我们展示了一种通用和灵活的方法，可用于训练监督学习模型中极大数量的平滑函数之和的平均值的最小化问题，这种方法可以包括任意的重要性抽样和小批量处理方法，并展示了该方法的迭代复杂度分析和平滑和强凸情形下的线性收敛率，从而在对于有限总和问题的原始 / 对偶方法的复杂性的理解上迈出了重要一步。

    Jan, 2019

  • ASAGA: 异步并行 SAGA

    ASAGA 是 SAGA 的异步并行版本，具有快速线性收敛率。通过重新访问并澄清了一些细微但重要的技术问题，ASAGA 不需要稀疏假设即可在多核系统上获得线性加速，并通过 40 核架构的实现结果展示了实际加速以及硬件开销。

    Jun, 2016

  • 随机平均梯度下降法最小化有限和

    本文提出了基于随机平均梯度方法的优化算法，它克服了黑匣子随机梯度方法的缺点，具有更快的收敛速度和更少的梯度评估数量。实验表明，该算法在许多情况下都优于现有的随机梯度方法和确定性梯度方法，并且可以通过非均匀采样策略进一步提高表现。

    Sep, 2013

  • 使用负动量采样直接加速 SAGA

    本文提出了使用新型负采样动量的加速 SAGA 算法，以实现直接加速 SAGA 的目的，并在已知强凸性参数的强凸问题上实现了最优的预期复杂度。

    Jun, 2018

  • 加速随机梯度下降求解有限和最小化

    本论文提出了一种优化方法，该方法融合了加速梯度下降、随机方差减少梯度的优点，适用于非强凸和强凸问题，并在效率和收敛速率上都有优异表现。

    Jun, 2015

  • 突破不光滑障碍：复合优化可扩展并行方法

    本研究提出了一种基于 ProxASAGA 算法的并行异步稀疏方法，用于解决多核架构下大规模优化问题中的非光滑目标，并在实验中取得了多项实际加速。

    Jul, 2017