基于原始对偶框架的去中心化随机优化
现代分散应用中,通信效率和用户隐私是关键挑战。为了训练机器学习模型,算法必须与数据中心进行通信并对其梯度计算进行采样,从而暴露数据并增加通信成本。为了解决这个问题,我们提出了一种分散优化算法,它在通信效率上高效,并通过最优梯度复杂性达到了一个 ε- 近似解,对于凸和强凸的设置分别为 O (1/√ε+σ²/ε²) 和 O (log (1/ε)+σ²/ε),对于两种设置都具有 O (1/ε²) 的 LO (线性优化) 复杂性,给定方差 σ² 的随机梯度预言。与之前的工作相比,我们的框架放宽了最优解是可行集的严格内点的假设,并在使用随机梯度预言进行大规模训练时具有更广泛的适用性。我们还通过各种数值实验证明了我们算法的效率。
Apr, 2024
本文提出了一种适用于任意连接通信网络和任何光滑(可能是非凸的)代价函数的分布式原始 - 对偶随机梯度下降(SGD)算法,证明了该算法实现了常数参数的输出线性收敛到全局最优的邻域并展示了实验结果与基线集中式 SGD 和最近提出的分布式 SGD 算法的比较效率。
Jun, 2020
本文研究分散设置中的非凸函数求和最小化优化问题,提出了 PMGT-SVRG 算法的新的理论分析,证明了其方法的线性收敛性。然而,PMGT-SVRG 算法的收敛速度与条件数呈线性依赖关系,这对于病态问题而言是不理想的。为了解决这个问题,我们提出了一种结合加速、梯度跟踪和多共识混合技术的加速随机分散一阶算法,该方法的收敛速度与条件数呈平方根依赖关系。数值实验验证了我们提出算法在合成和真实数据集上理论保证的有效性。
Feb, 2024
本文提出一种名为 GTVR 的随机分散算法框架,其基于本地方差缩减和全局梯度跟踪的技术,用于解决大规模,有可能无法集中处理私有数据的优化问题。我们在本文中重点研究了 GTVR 并介绍了两种算法 GT-SAGA 和 GT-SVRG,证明它们在解决光滑问题上呈现出线性收敛,并实现了在网络独立下的线性速度提升。
Dec, 2019
本研究提出了一个通用框架,用于统一集中式和分布式场景下的多个基于梯度的随机优化方法,通过引入一个增光图,设计了一种合适的拓扑结构,使得 VR 和 GT 方法能够有效消除设备内外的数据异质性,并提供了一种统一的收敛分析。
Jul, 2022
本文提出了一种新的去中心化一阶方法解决在多代理网络上的非光滑和随机优化问题,其中主要贡献为提出了基于去中心化通讯滑动算法的去中心化原始 - 对偶算法,以解决在去中心化优化中通讯瓶颈。
Jan, 2017
本文提出了两种基于加速的前后向算法的分散优化新算法以解决存储在网络节点上的光滑强凸函数之和的最小化问题,并显示它们是最优的算法,具有复杂性的保证。
Jun, 2020
该研究探讨了分布式网络中拜占庭鲁棒随机优化问题,其中每个代理定期与其邻居通信以交换本地模型,然后通过随机梯度下降(SGD)更新其本地模型。通过引入两种方差减小方法(SAGA 和 LSVRG),该方法在消除了随机梯度噪声的负面影响后,实现了线性收敛速度和随机梯度噪声独立的学习误差,对基于总变异(TV)范数正则化和随机子梯度更新的方法具有最优的学习误差表现,并在广泛的拜占庭攻击实验中得到了验证。
Aug, 2023