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

Feb, 2021

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

The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods

Wei Tao, Sheng Long, Gaowei Wu, Qing Tao

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

Abstract

The adaptive stochastic gradient descent (SGD) with momentum has been widely adopted in deep learning as well as convex optimization. In practice, the last iterate is commonly used as the final solution to make d

发现论文，激发创造

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

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

Dec, 2017

关于现有动量方案在随机优化中的不足

本论文通过证明存在简单的问题实例以及提出一种新的基于Nesterov的算法，来对现有的快速梯度方法在随机情况下的局限性以及不足进行研究。实验证明，该新算法比常见的方法更具优势。

Mar, 2018

统一动量的加权AdaGrad算法

通过引入重加权AdaGrad联合动量，AdaUSM在解决难以收敛的随机问题时，其带权高斯平均符合实时梯度下降法 (SGD) 和AdaGrad的学习率下降速度，同时还能实现SGD动量和Nesterov学习率全方位的整合。

Aug, 2018

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

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

Aug, 2018

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

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

Jun, 2020

自适应带动量的 SGD 高概率分析

本文对机器学习应用中广泛使用的随机梯度下降及其变种算法在非凸优化问题中的收敛性做了一系列的理论分析，证明了在弱假设条件下，Delayed AdaGrad with momentum算法可高概率收敛于全局最优解。

Jul, 2020

平均加速随机梯度下降算法：有限样本速率和渐近正态性

本研究分析了随机梯度下降与动量法在强凸设置下的有限样本收敛速度，并证明了 Polyak-averaging 版本的 SGDM 估算器的渐近正态性以及其与平均 SGD 的渐近等价性。

May, 2023

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

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

Dec, 2023

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

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

Jan, 2024

随机Polyak步长和动量：收敛保证和实际性能

在本文中，我们提出了一种基于随机梯度下降算法的新型多步骤选择方法来解决大规模随机优化问题，该方法不需要预先了解问题参数并且具有收敛性保证。

Jun, 2024