ProxSkip:局部梯度步骤可证明提高通信加速!终于!
本文提出一种新的算法,基于 Chambolle 和 Pock (2011) 的方法,在一些非平滑的强凸共轭鞍点问题上的表现优于 ProxSkip。该算法在联邦学习中的应用需要较少的本地步骤,并且是一种确定性方法,而且也适用于连接网络上的优化。
Jul, 2022
基于概率局部更新的分布式优化方法在通信加速方面引起了人们的关注,然而,这种能力只在损失函数平滑且网络连接充分的情况下有效。本文提出了第一种具有概率局部更新的线性收敛方法 MG-Skip 用于非平滑分布式优化,无需额外条件对网络连接性能,大多数迭代可以跳过多轮 “传闲话” 通信,其迭代复杂度为 O (κ log (1/ε)),通信复杂度仅为 O (√(κ/(1-ρ)) log (1/ε)),其中 κ 是损失函数的条件数,ρ 反映了网络拓扑的连通性。据我们所知,当损失函数具有平滑(强凸)+ 非平滑(凸)复合形式时,MG-Skip 实现了最佳的通信复杂度。
Dec, 2023
该研究提出了一种基于分布式近端梯度方法来优化平均凸函数的方法,每个凸函数都是网络中各个代理的本地目标函数。该方法通过交换估计值来实现每个代理迭代更新全局最小值的目标,并使用 Nesterov-type 加速技术和多个通信步骤进行迭代,表明这种方法的收敛速率为 1/k(其中 k 是代理之间的通信轮数),这比现有的分布式方法的收敛速度更快。数值实验也验证了该方法的卓越收敛速度。
Oct, 2012
本文提出了一种利用逐步学习非平滑函数 $g$ 的接近算子的降低三个凸函数之和的方法,可以有效地分离平滑部分和非平滑部分,同时证明了该方法的多个迭代复杂性结果,可以广泛应用于估计 $f$ 的梯度的策略,包括通过标准和方差减少的随机估计以及结合 SGD 或 SAGA 梯度估计用于经验风险最小化,还涵盖了多个现有算法,并得到在特定情况下的新算法。
May, 2019
本文介绍一种新的分布式优化问题的近端 - 梯度算法,用于处理包含平滑和非平滑项的组合目标,我们提出的新算法与以前的算法相比具有一些优势,例如不需要协调步长和可得到线性收敛。
Apr, 2017
本文介绍了一种无需正负数计算和传输的随机梯度下降方法,使用了压缩过的一位元梯度,通过一种基于随机梯度下降的近端梯度方法来证明该方法在非凸优化方面的理论收敛性,实验证明这种可以压缩的方法可以达到未压缩方法相近的收敛速度。
Jul, 2018
本文探讨了凸优化中的两个基本一阶算法,梯度下降法(GD)和近端梯度法(ProxGD)。我们着重于通过利用光滑函数的局部曲率信息,使这些算法完全自适应。我们提出了基于观察到的梯度差异的 GD 和 ProxGD 的自适应版本,因此没有额外的计算成本。此外,我们证明了方法的收敛性,仅需假设梯度在局部利普希茨连续。此外,所提出的版本允许使用比 [MM20] 最初建议的更大的步长。
Aug, 2023
本文提出一种基于变量规约的 Proximal 随机梯度下降算法 (ProxSVRG+), 该算法在非凸性和非光滑性优化问题上具有更好的性能,并在收敛性分析方面比之前的算法更加全面和普适性更强。
Feb, 2018
本文研究了凸函数与唇希茨凸函数的平滑映射组合的最小化算法的全局效率,以及使用近端线性方法结合平滑、快速梯度方案等技术处理只能通过一阶方法解决的子问题时,如何获得高效率。
Apr, 2016