随机 Polyak 步长和动量:收敛保证和实际性能
我们在光滑、强凸的设置中分析了随机重球 (SHB) 动量的收敛性,证明了当小批量大小大于某个阈值时,SHB 可以获得加速收敛率。特别地,在具有条件数 κ 的强凸二次函数中,SHB 伴随标准步长和动量参数具有 O (exp (-T/√κ) + σ ) 收敛率,其中 T 是迭代次数,σ^2 是随机梯度的方差。为了确保收敛到最小值,我们提出了一种多阶段方法,得到了一种噪声自适应的 O (exp (-T/√κ) + σ/T ) 收敛率。对于一般的强凸函数,我们利用 SHB 的均值解释和指数步长证明了一种噪声自适应的 O (exp (-T/κ) + σ^2/T ) 最小值收敛率。最后,我们实证了所提出算法的有效性。
Jan, 2024
本文旨在解决现实应用中使用随机梯度下降法进行深度学习和凸优化时,普遍使用最后一次迭代作为最终解决方案,但唯独它的可用遗憾分析和恒定动量参数设置只保证平均解的最佳收敛问题,并且探究单独收敛分析问题,最终我们证明了:在约束凸问题中,使用 Polyak's Heavy-ball 方法,它只能通过移动平均策略更新步长,即可获得 O(1 / 根号 T)的最优收敛率,而不是普通 SGD 的 O(log T / 根号 T)的优化。同时,我们的新型分析方法不仅阐释了 HB 动量及其时间变化的作用,还给出了有价值的暗示,即动量参数应如何进行安排。同时,针对优化凸函数和训练深度网络的实证结果,验证了我们收敛分析的正确性,并证明了自适应 HB 方法的改进性能。
Feb, 2021
本文研究了随机梯度下降法和随机重球法在一般随机逼近问题上的收敛速度和最后迭代时的表现,证明了加权平均的迭代数的 收敛率,以及在非超参数区域内使用随机线性搜索和随机 Polyak 步进时的收敛性,并证明了最后一个重球的迭代收敛于极小化器,最后在非凸设置中证明了关于 SGD 轨迹下最低梯度范数的相似速率结果。
Jun, 2020
本文介绍了一种新颖的随机 Polyak 步长方法,称为 SPS,它可以有效地用于随机梯度下降,特别是在训练超参数化模型时表现良好,并且在不需要任何与问题相关的常数或额外计算开销的情况下收敛速度快,并且与其他优化方法相比表现出色。
Feb, 2020
扩展了 Stochastic Gradient Descent with Polyak Step-size (SPS) 方法,使用 Hutchinson's 方法、Adam 和 AdaGrad 等预处理技术来提高其在糟糕缩放和 / 或病态数据集上的性能。
Oct, 2023
本文研究随机动量方法,包含随机梯度法(SG),随机重球方法(SHB)和随机 Nesterov's 加速梯度方法(SNAG)。我们提出了一个框架,统一了这三种方法,并通过一致稳定性方法推导了梯度范数的收敛速率和推导了非凸优化问题。同时,我们也分别分析了这三个方法的收敛率和泛化性能。研究结果表明,动量项可以提高学习模型的稳定性和泛化性能。
Aug, 2018
该研究提出了两种新的变体的随机 Polyak 步长和随机线性搜索算法,名为 AdaSPS 和 AdaSLS,它们保证了在非插值设置下的收敛,并在训练超参数化模型时维持凸函数和强凸函数的次线性和线性收敛速度。此外,通过引入方差缩减技术,这些算法能够在次优情况下进行梯度评估,达到 O(ε)次优性,从而改进了非插值区域 AdaSPS 和 AdaSLS 的较慢 O(1/ε^2)收敛速度。实验验证了算法的理论有效性和稳健性。
Aug, 2023
本文介绍了一种基于 Stochastic Polyak Stepsize 的联邦学习算法 FedSPS,该算法具有局部自适应性和近乎无参数,且可以达到与 FedAvg 相当的优化性能。
Jul, 2023
本文通过建立随机重球方法在二次目标函数和异性梯度噪声条件下的非渐近收敛界,证明了重球动量可以在 SGD 的偏差项上提供加速收敛,同时与随机方差项相比,仍然能够实现接近最优的收敛速度,从而在统计极小化速度的对数因素范围内整体收敛,该结果意味着带有重球动量的 SGD 在大批量设置中(例如分布式机器学习或联邦学习)中非常有用,其中更少的迭代次数可以显著减少通信轮数,进而加速实践计算。
Dec, 2023
研究了 Polyak 重球法,Nesterov 加速梯度以及加速投影梯度法等动量方法在梯度噪声情况下的收敛性,证明了其在小于一定噪声上限后仍能保持加速线性速率的收敛性并且提出了步长、动量参数和噪声幅度与加速线性速率之间的关系模型。此外,还对 APG 方法和弱凸函数进行了扩展研究。
Jan, 2019