一种简单实用的有限和加速方法
本文分析了一种用于优化非凸问题的快速递增聚合梯度方法,在递增一阶预言框架中分析了 SAGA 算法,并表明它比梯度下降和随机梯度下降更快地收敛到稳定点。此外,我们还讨论了 Polyak 特殊类的问题,针对这类问题,SAGA 方法的收敛速度为线性收敛到全局最优解。最后,我们分析了实际有用的 SAGA 正则化和小批量变体。据我们所知,这篇论文提出了第一篇关于递增聚合梯度方法快速收敛的分析。
Mar, 2016
本文提出了基于随机平均梯度方法的优化算法,它克服了黑匣子随机梯度方法的缺点,具有更快的收敛速度和更少的梯度评估数量。实验表明,该算法在许多情况下都优于现有的随机梯度方法和确定性梯度方法,并且可以通过非均匀采样策略进一步提高表现。
Sep, 2013
介绍了一种新的优化方法 ——SAGA,它是在最近提出的一组具有快速线性收敛率的增量梯度算法:SAG、SDCA、MISO 和 SVRG 的基础上提出的。SAGA 改进了 SAG 和 SVRG 的理论,具有更好的理论收敛率,并支持在规则化器上使用近端算子的复合目标。与 SDCA 不同,SAGA 直接支持非强凸问题,并且适应于问题的任何内在强凸性。 我们给出了实验结果,表明我们的方法的有效性。
Jul, 2014
通过提出一种新的 SAGA 变体,并构建新的随机 Lyapunov 函数,我们展示了一种通用和灵活的方法,可用于训练监督学习模型中极大数量的平滑函数之和的平均值的最小化问题,这种方法可以包括任意的重要性抽样和小批量处理方法,并展示了该方法的迭代复杂度分析和平滑和强凸情形下的线性收敛率,从而在对于有限总和问题的原始 / 对偶方法的复杂性的理解上迈出了重要一步。
Jan, 2019
该论文研究了关于具有本地数据样本批量的节点网络的分散式非凸有限和最小化问题,并提出了一种名为 GT-SAGA 的单时间尺度随机增量梯度法,通过利用节点级方差、网络级梯度跟踪等手段优化它的性能,这种方法在特定条件下起到了优于现有方法性能的作用,该文对此进行了详细分析。
Nov, 2020
本文通过优化理论,针对平滑且强凸的有限和问题,提出一种新的求解方法,其理论收敛速度是现有方法的 4 倍,同时还可以实现不重复的抽样,提高计算速度,并通过实证研究已达到了最优表现。
Jul, 2014
提出了 VAriance-Reduced Accelerated Gradient 算法来解决求解光滑凸有限和问题,该算法具有良好的收敛性能并且可以用于求解随机有限和问题。
May, 2019