线性收敛随机重球法用于最小化泛化误差
本文通过建立随机重球方法在二次目标函数和异性梯度噪声条件下的非渐近收敛界,证明了重球动量可以在 SGD 的偏差项上提供加速收敛,同时与随机方差项相比,仍然能够实现接近最优的收敛速度,从而在统计极小化速度的对数因素范围内整体收敛,该结果意味着带有重球动量的 SGD 在大批量设置中(例如分布式机器学习或联邦学习)中非常有用,其中更少的迭代次数可以显著减少通信轮数,进而加速实践计算。
Dec, 2023
本文研究了一种自然随机优化程序,该程序由所谓的 Heavy-ball 方法微分方程推导而来,旨在最小化凸函数,提出了随机 Heavy-ball 方法,描述了其收敛性和极限定理。
Sep, 2016
本文研究了随机梯度下降法和随机重球法在一般随机逼近问题上的收敛速度和最后迭代时的表现,证明了加权平均的迭代数的 收敛率,以及在非超参数区域内使用随机线性搜索和随机 Polyak 步进时的收敛性,并证明了最后一个重球的迭代收敛于极小化器,最后在非凸设置中证明了关于 SGD 轨迹下最低梯度范数的相似速率结果。
Jun, 2020
本文提出了改良后的重球法收敛复杂度分析,对高度矫正的目标函数证明了具有常数步长的重球算法的非遗传 O(1/k)率结果,同时在简化其步长和惯性参数的条件下,证明了更弱的适用条件下的线性收敛性。研究展开成多块版本的重球算法,结果适用于循环和随机更新规则。本研究结果已成功扩展到分散式优化问题中。
Nov, 2018
本文探讨了二阶稳定线性差分方程的解及其对无约束优化方法 - Heavy Ball 方法的削弱效果的影响,提出了改进算法,通过引入新的 Lyapunov 函数,使方法的收敛性在较少的限制条件下得到确立,并建议了一些重新启动技术来加速方法的收敛。
Nov, 2018
本论文研究了凸优化中的 Heavy-ball 方法,当目标函数具有 Lipschitz 连续梯度时,证明了迭代的 Cesaro 平均值以 $O (1/k)$ 的速度收敛于最优解;当目标函数还是强凸时,证明了 Heavy-ball 迭代线性收敛于唯一的最优解。
Dec, 2014
该论文针对随机动量法在非凸优化领域中的收敛性分析不足,通过对两种随机动量法(随机重球法和随机版 Nesterov 加速梯度法)的基本收敛性分析,提出了一种统一框架,展示了它们与随机梯度法之间的相似性和差异性,并在深度学习的测试误差收敛行为中解释了连续变化现象。同时,对深度神经网络的优化实验结果表明,随机版 Nesterov 加速梯度法在训练误差收敛速度和测试误差收敛鲁棒性方面取得了很好的平衡。
Apr, 2016
本文研究随机动量方法,包含随机梯度法(SG),随机重球方法(SHB)和随机 Nesterov's 加速梯度方法(SNAG)。我们提出了一个框架,统一了这三种方法,并通过一致稳定性方法推导了梯度范数的收敛速率和推导了非凸优化问题。同时,我们也分别分析了这三个方法的收敛率和泛化性能。研究结果表明,动量项可以提高学习模型的稳定性和泛化性能。
Aug, 2018
研究了 Polyak 重球法,Nesterov 加速梯度以及加速投影梯度法等动量方法在梯度噪声情况下的收敛性,证明了其在小于一定噪声上限后仍能保持加速线性速率的收敛性并且提出了步长、动量参数和噪声幅度与加速线性速率之间的关系模型。此外,还对 APG 方法和弱凸函数进行了扩展研究。
Jan, 2019
我们在光滑、强凸的设置中分析了随机重球 (SHB) 动量的收敛性,证明了当小批量大小大于某个阈值时,SHB 可以获得加速收敛率。特别地,在具有条件数 κ 的强凸二次函数中,SHB 伴随标准步长和动量参数具有 O (exp (-T/√κ) + σ ) 收敛率,其中 T 是迭代次数,σ^2 是随机梯度的方差。为了确保收敛到最小值,我们提出了一种多阶段方法,得到了一种噪声自适应的 O (exp (-T/√κ) + σ/T ) 收敛率。对于一般的强凸函数,我们利用 SHB 的均值解释和指数步长证明了一种噪声自适应的 O (exp (-T/κ) + σ^2/T ) 最小值收敛率。最后,我们实证了所提出算法的有效性。
Jan, 2024