用于非凸优化任务的方差缩减分布式自适应随机梯度追踪算法,适用于无向网络

《Neurocomputing》:Variance reduced distributed adaptive stochastic gradient tracking for non-convex optimization over undirected networks

【字体: 大 中 小 】 时间:2026年05月13日 来源:Neurocomputing 6.5

编辑推荐:

  曹正然|王星|张可可|严登伟|周洋|李华清|李传东 重庆师范大学计算机科学与信息科学学院,中国重庆401331 摘要 本文研究了分布式随机优化问题,重点关注在无向通信网络上解决非凸优化问题。在优化理论和机器学习中,具有局部数据的代理如何协作最小化全局目标至关重要,这

  曹正然|王星|张可可|严登伟|周洋|李华清|李传东
重庆师范大学计算机科学与信息科学学院,中国重庆401331

摘要
本文研究了分布式随机优化问题,重点关注在无向通信网络上解决非凸优化问题。在优化理论和机器学习中,具有局部数据的代理如何协作最小化全局目标至关重要,这是大规模分布式感知和机器学习系统等现代应用的核心挑战。然而,如何在快速收敛和低计算成本之间取得平衡仍然是一个关键问题。为了解决这个问题,我们开发了一个统一的分布式随机优化框架,称为方差缩减的分布式自适应梯度跟踪(VRDAGT)算法。VRDAGT算法集成了三种核心技术:自适应动量机制用于加速收敛;受SVRG启发的方差缩减技术用于减轻梯度噪声并允许更大的学习率;以及梯度跟踪技术用于纠正数据异质性并协调代理之间的优化方向。在分布式图像去模糊和学习任务上的实验结果表明,VRDAGT算法表现出色,在分布式非凸优化中的标准评估指标上取得了可靠的性能。

引言
在无向网络上进行分布式随机非凸优化的研究引起了广泛关注,因为它在联邦学习系统[1]、多机器人协调[3]和智能电网[4]等应用中具有基础性的重要性。在这个框架中,代理们在没有中央协调器的情况下协作解决全局优化问题,仅依赖于点对点通信[5]。数据通常是局部的或在线的,因此随机梯度(即真实梯度的无偏但有噪声的估计)是主要的计算基础。利用这些梯度的分布式方法解决了可扩展性和隐私挑战[7]。先前的工作开发了通信效率高的分布式随机梯度下降算法[8]、[9]、[10]、[11],并引入了梯度跟踪技术用于非凸设置[12]。然而,在温和的假设下实现通信效率、快速收敛和稳健的理论保证仍然是一个未解决的挑战,这也是本研究的动机。

非凸优化是现代机器学习的核心,但由于存在鞍点和局部最小值等复杂情况,因此本质上具有挑战性。数据异质性和通信限制在分布式环境中加剧了这些困难,需要算法能够高效地导航复杂的损失表面。鉴于其在深度网络训练、矩阵分解和传感器定位等应用中的普遍性,开发高效的分布式非凸问题方法是一项紧迫的实际需求。

分布式优化的发展提供了必要的背景。早期在确定性环境下的共识优化研究[13]、[14]、[15]促成了DGD算法的诞生,该算法结合了局部次梯度更新和邻域平均[11]、[16]。然而,DGD在恒定步长下存在残余收敛误差[17]。引入梯度跟踪机制是一个突破,使得EXTRA[21]和NIDS[23]等算法能够通过动态估计全局梯度来实现强凸问题的线性收敛。同时,分布式ADMM通过双分解[24]解决了受限共识问题。随着大规模数据的出现,研究重点转向了随机优化。DSGD算法[25]及其梯度跟踪变体DSGT[28]、[29]成为标准算法,促进了两个关键路径上的进步:第一个路径采用动量加速来处理非凸问题;虽然经典方法如Heavy-ball和Nesterov加速[30]在凸设置中有效,但直接应用于非凸问题具有挑战性,这促使人们开发了DSGT-HB和DSGT-NAG[29]等结合动量的分布式算法,以及SUM[28]、[32]、[33]等提供可调加速的统一框架。第二个路径侧重于使用变分随机(VR)技术来减少随机梯度中的噪声。尽管分布式随机算法降低了每次迭代的成本[35]、[36],但由于持续方差的存在,它们的收敛可能会不稳定。来自集中式优化的VR技术(如SAGA[37]、SVRG[38]和SARAH[39])通过重用历史梯度来构建低方差估计器。这些技术的分布式版本最初是为强凸问题开发的,后来与梯度跟踪技术结合在GT-VR[40]等算法中用于协调优化方向并抑制方差。最近的混合方法,如GTSADAM[41]和分布式自适应梯度跟踪(DAGT)算法[42],在一个框架内集成了梯度跟踪、VR和自适应动量。

进一步的进展解决了异步通信、时变拓扑和有向图[32]、[43]等实际问题。最近,自适应学习率方法在分布式环境中受到了关注[44]。包括Distributed-Adam[45]、[46]在内的算法将自适应动量估计纳入共识优化,而最近的工作将自适应梯度方法与梯度跟踪相结合[47]。尽管取得了这些进展,但在高度异构的环境中仍存在三个主要挑战:(i)存储历史梯度的VR技术的内存开销[48];(ii)非凸设置中分布式自适应方法的有限理论保证[49];(iii)动态网络中的有限鲁棒性[50]。在具有非独立同分布(non-IID)数据和异构客户端的情况下进行联邦学习时,这些挑战尤为突出。与此同时,在相关优化范式中也取得了显著进展,包括用于无约束问题的新型割线方法[57]、基于学习的复杂系统控制[58]、[59]、不确定性下的决策技术[60]以及复杂的资源分配框架。然而,这些重要工作主要集中在集中式设置或与本文关注的问题类别不同的问题类别上。

为此,我们提出了VRDAGT算法。我们的主要贡献有三个方面:
•本文提出了VRDAGT算法,这是一种用于无向网络上非凸问题的高效分布式随机优化方法。在标准假设下,我们证明了其非渐近收敛速率,并通过实验进行了验证。
•与现有技术[28]、[29]、[30]、[31]不同,VRDAGT算法独特地将方差缩减与自适应梯度跟踪相结合,显著提高了收敛速度、最终准确性和对数据异质性的鲁棒性。
•与仅结合这些技术子集的先前工作[42]、[47]不同,VRDAGT算法提供了一个统一的框架,系统地集成了方差缩减、自适应动量和梯度跟踪,为非凸设置提供了严格的保证。

组织结构:
本文的其余部分组织如下。第2节介绍必要的理论基础。第3节介绍VRDAGT算法,第4节提供其收敛性分析。第5节通过数值实验评估VRDAGT的性能,第6节总结本文。

数学符号
引入以下符号:用于表示实数,用于表示正实数。维度为的实值列向量属于,而实矩阵属于。对于矩阵,表示其转置,表示其第个元素。矩阵范数包括谱范数和Frobenius范数,表示方阵的谱半径。对角矩阵和块对角矩阵由...构成。

算法构建
本节介绍了专门为方程(1)中的分布式优化问题设计的VRDAGT算法框架。它结合了自适应动量和方差缩减技术,以提高随机环境中的收敛性能。如图1所示,该算法结合了三个核心模块:自适应动量更新、方差缩减的梯度估计以及通过邻居通信进行的梯度跟踪,从而实现高效且稳健的分布式随机优化。

收敛性分析
本节致力于确立我们的方法在非凸设置中的收敛性质,其中使用(2)中定义的最优性差距来量化性能。我们的分析从引入以下辅助向量开始:
表示代理集上所有局部向量的串联。网络中的相应平均值表示为,其中可能表示集合中的任何变量。此外,设...

数值示例
本节通过数值模拟建立理论框架与实际应用之间的联系。数值实验使用Python在配备16 GB内存的Intel(R) Core(TM) i7-10510U系统和Windows 10(64位)上进行。模拟重点关注分布式图像去模糊问题[53]、[55]、[56],以验证所提出的VRDAGT算法的性能。在此实验设置中,VRDAGT与其他五种代表性算法进行了比较。

结论
本文提出了VRDAGT算法,这是一个统一的分布式非凸优化框架,系统地结合了自适应动量、方差缩减和梯度跟踪。理论上,在标准平滑性假设下,该算法实现了亚线性收敛率,有效对抗了随机梯度噪声和数据异质性带来的偏差。在合成数据和基准数据集上的实证评估证实了收敛性的显著改进。

未引用的参考文献
[18]、[19]、[20]、[22]、[26]、[34]

作者贡献声明
曹正然:资金获取、形式分析、概念化。
王星:撰写——原始草稿。
张可可:概念化。
严登伟:形式分析。
周洋:资金获取。
李华清:研究。
李传东:方法论。

利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。

致谢
本工作部分得到了重庆科学技术局自然科学基金项目(编号CSTB2025NSCQ-GPX0258、2024NSCQ-MSX3120和CSTB2023NSCQ-LZX0139)、重庆市教育委员会科学研究计划(编号KJQN202400548、KJQN202500509)的支持。

曹正然2013年在中国德州市的德州大学获得电子信息科学和技术学士学位,2018年在重庆西南大学获得信号与信息处理硕士学位,2021年在同一所大学获得计算智能与信息处理博士学位。他目前是重庆师范大学计算机与信息科学学院的副教授。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号