Dec, 2023

具向异性梯度噪声的随机重力球法加速收敛

PDF
TL;DR本文通过建立随机重球方法在二次目标函数和异性梯度噪声条件下的非渐近收敛界，证明了重球动量可以在 SGD 的偏差项上提供加速收敛，同时与随机方差项相比，仍然能够实现接近最优的收敛速度，从而在统计极小化速度的对数因素范围内整体收敛，该结果意味着带有重球动量的 SGD 在大批量设置中（例如分布式机器学习或联邦学习）中非常有用，其中更少的迭代次数可以显著减少通信轮数，进而加速实践计算。
heavy-ball momentumdecaying learning ratesstochastic gradient descentquadratic objectivesaccelerated convergence
发现论文，激发创造
  • 线性收敛随机重球法用于最小化泛化误差

    本文针对随机重球方法进行分析与研究，证明了该方法的线性收敛性，并着重探讨了期望损失的最小化以及动量项所起的作用。

    Oct, 2017

  • 噪声适应（加速的）随机重球动量

    我们在光滑、强凸的设置中分析了随机重球 (SHB) 动量的收敛性，证明了当小批量大小大于某个阈值时，SHB 可以获得加速收敛率。特别地，在具有条件数 κ 的强凸二次函数中，SHB 伴随标准步长和动量参数具有 O (exp (-T/√κ) + σ ) 收敛率，其中 T 是迭代次数，σ^2 是随机梯度的方差。为了确保收敛到最小值，我们提出了一种多阶段方法，得到了一种噪声自适应的 O (exp (-T/√κ) + σ/T ) 收敛率。对于一般的强凸函数，我们利用 SHB 的均值解释和指数步长证明了一种噪声自适应的 O (exp (-T/κ) + σ^2/T ) 最小值收敛率。最后，我们实证了所提出算法的有效性。

    Jan, 2024

  • 随机梯度下降法和随机重球法的几乎必然收敛速率

    本文研究了随机梯度下降法和随机重球法在一般随机逼近问题上的收敛速度和最后迭代时的表现，证明了加权平均的迭代数的 收敛率，以及在非超参数区域内使用随机线性搜索和随机 Polyak 步进时的收敛性，并证明了最后一个重球的迭代收敛于极小化器，最后在非凸设置中证明了关于 SGD 轨迹下最低梯度范数的相似速率结果。

    Jun, 2020

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

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

    Jan, 2019

  • 随机动量方法在凸和非凸优化中的统一收敛分析

    该论文针对随机动量法在非凸优化领域中的收敛性分析不足，通过对两种随机动量法（随机重球法和随机版 Nesterov 加速梯度法）的基本收敛性分析，提出了一种统一框架，展示了它们与随机梯度法之间的相似性和差异性，并在深度学习的测试误差收敛行为中解释了连续变化现象。同时，对深度神经网络的优化实验结果表明，随机版 Nesterov 加速梯度法在训练误差收敛速度和测试误差收敛鲁棒性方面取得了很好的平衡。

    Apr, 2016

  • 随机梯度方法中动量的作用理解

    该论文通过使用 QHM 的一般公式来对几种流行的算法进行统一分析，涵盖了它们的渐近收敛条件，稳定区域和其稳态分布的性质，通过结合收敛速度和稳态分布结果，得出了设置学习速率和动量参数的实用指南。

    Oct, 2019

  • 深度学习随机动量方法的统一分析

    本文研究随机动量方法，包含随机梯度法（SG），随机重球方法（SHB）和随机 Nesterov's 加速梯度方法（SNAG）。我们提出了一个框架，统一了这三种方法，并通过一致稳定性方法推导了梯度范数的收敛速率和推导了非凸优化问题。同时，我们也分别分析了这三个方法的收敛率和泛化性能。研究结果表明，动量项可以提高学习模型的稳定性和泛化性能。

    Aug, 2018

  • 自适应 Polyak 重球方法中动量参数在最优收敛中的作用

    本文旨在解决现实应用中使用随机梯度下降法进行深度学习和凸优化时，普遍使用最后一次迭代作为最终解决方案，但唯独它的可用遗憾分析和恒定动量参数设置只保证平均解的最佳收敛问题，并且探究单独收敛分析问题，最终我们证明了：在约束凸问题中，使用 Polyak's Heavy-ball 方法，它只能通过移动平均策略更新步长，即可获得 O（1 / 根号 T）的最优收敛率，而不是普通 SGD 的 O（log T / 根号 T）的优化。同时，我们的新型分析方法不仅阐释了 HB 动量及其时间变化的作用，还给出了有价值的暗示，即动量参数应如何进行安排。同时，针对优化凸函数和训练深度网络的实证结果，验证了我们收敛分析的正确性，并证明了自适应 HB 方法的改进性能。

    Feb, 2021

  • 随机重球

    本文研究了一种自然随机优化程序，该程序由所谓的 Heavy-ball 方法微分方程推导而来，旨在最小化凸函数，提出了随机 Heavy-ball 方法，描述了其收敛性和极限定理。

    Sep, 2016

  • 随机梯度、牛顿、近端点和子空间下降方法的动量和随机动量

    本文研究了几种被重量球动量丰富的随机优化算法，证明了它们的全局非渐进线性收敛速率，并在稀疏数据环境下提出了随机动量，证明了它对于带有动量的算法有更好的整体复杂度。

    Dec, 2017