Jun, 2021

随机梯度下降和随机八卦算法中的 Nesterov 加速算法连续化视角

PDF
TL;DR本文提出了连续 Nesterov 加速法，将 Nesterov 加速法的变量用连续时间参数索引，使两个变量连续混合，其间隔时间内随机进行梯度步骤。我们证明了该变体具有与 Nesterov 原始加速法相似的收敛率，并且具有连续和离散框架的最佳性能。我们展示了连续 Nesterov 加速法在随机 / 确定梯度及其噪声下的应用，并将异步 gossip 算法的问题表示为某种能量函数的随机最小化问题，提供了第一个基于该连续框架的异步 gossip 加速定理。
nesterov accelerationcontinuous time parametergradient stepsdifferential calculusasynchronous gossip algorithms
发现论文，激发创造
  • 关于 Nesterov 加速梯度方法在随机设置下的收敛性

    研究了 Nesterov 加速梯度方法在随机逼近和有限和设置下的表现，发现使用通常的步长和动量参数，该方法在后者可能发散，进而阐明了这种方法在此情况下可能失败的原因。

    Feb, 2020

  • 关于 Nesterov 加速的动态系统视角

    利用动力学系统框架理解 Nesterov 加速梯度方法的原理及机制，探究了半隐式欧拉积分方案离散化普通微分方程的加速效应，分析发现曲率依赖阻尼项是实现加速的关键。同时，建立了离散化和连续时间动态之间的联系。

    May, 2019

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

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

    Apr, 2024

  • 优化加速方法的变分视角

    本文从连续时间的角度研究了加速方法，发现 Bregman Lagrangian 是一种生成各种加速方法的拉格朗日函数，其中包括 Nesterov 成果的系统方法。

    Mar, 2016

  • 关于优化中的加速方法

    本文探讨了凸优化中梯度方法的加速现象，并将高阶梯度方法与拉格朗日泛函等价地联系起来，同时得出拉格朗日量具有时空不变性的结论。

    Sep, 2015

  • Nesterov 的加速梯度和动量作为正则化更新下降的近似

    我们提出了一种适应梯度下降优化方法中更新方向的统一框架，并通过重构经典动量法和 Nesterov 加速梯度法来解释后者算法的新直观解释。我们展示了一种新算法 —— 正则化梯度下降 —— 比 Nesterov 算法或经典动量算法更快地收敛。

    Jul, 2016

  • 加速随机梯度下降算法用于最小二乘回归

    本文研究加速随机梯度方法在最小二乘回归问题中的应用，通过对加速随机梯度下降作为随机过程的深入分析，证明了引入加速能够使其对统计误差具有鲁棒性，并提出了一种优于随机梯度下降的加速随机梯度方法。

    Apr, 2017

  • 用一个微分方程模拟 Nesterov 的加速梯度下降法：理论和洞见

    推导出与 Nesterov 加速梯度方法近似等价的二阶常微分方程，该 ODE 可用于分析，可以重启 Nesterov's 方案并且可以证明在目标函数强凸时，其具有线性收敛速率。

    Mar, 2015

  • Nesterov 加速法的耗散性理论

    本文采用耗散理论的控制理论概念，提供了关于 Nesterov 加速方法的一种自然理解，并利用能量耗散的物理直观概念将严格的收敛率分析与其联系。此外，耗散性理论使得可以有效构建 Lyapunov 函数（数值上或解析上），使用新型供应速率函数，我们展示如何恢复出已知的 Nesterov 方法速率界，并将该方法推广到多种情况下证明线性和次线性速率。最后，将其与算法分析的最近作品相连，应用于常微分方程轨迹离散化等问题。

    Jun, 2017

  • 增强随机梯度下降：更快收敛的统一框架和新的加速方法

    基于 SGD，本文提出了一种统一框架来解决随机优化中非凸条件下的收敛分析问题，并发现了两种插入加速方法：拒绝加速和随机向量加速，理论上证明这两种方法可以直接提高收敛速度。

    Feb, 2024