基于有向图的去中心化分布式拟牛顿法

Decentralized quasi-newton method based on directed graphs

摘要

在处理大规模数据优化任务时,有中心的分布式优化算法在信息传递过程中易产生信息损失,导致精度下降。另外,受安全等级、信任机制和访问权限等因素影响,实际应用场景中的信息交互往往呈现非对称的有向图拓扑结构,与现有研究的无向图预设场景存在显著偏差。针对上述问题,本文提出一种有向图拓扑上的去中心化分布式拟牛顿法(AB-DQN),用于最小化分布在有向图上的光滑强凸函数的有限和。该方法融合了通信拓扑的去中心化特征和信息传递的有向性,适用于无法在集中式服务器上收集或处理的海量、潜在私密数据的场景。每个节点通过实时监测并更新最优决策变量、智能体目标函数平均梯度和本地Hessian矩阵的逆近似三类估计值,协同推进整个有向网络的优化结果向全局最优收敛。数值实验结果验证了AB-DQN方法的有效性,表明其更契合大规模私密数据优化的实际需求。

Abstract

When tackling large-scale data optimization tasks, distributed optimization algorithms that rely on a central coordinator are prone to information loss during data transmission, leading to reduced accuracy. Moreover, influenced by factors such as security levels, trust mechanisms, and access permissions, information exchange in practical applications often exhibits an asymmetric directed graph topology, which differs markedly from the undirected graph assumptions prevalent in existing research. To address these issues, this paper proposes a decentralized distributed quasi-Newton (AB-DQN) method over directed graph topologies, aimed at minimizing the finite sum of smooth strongly convex functions distributed across directed graphs. The method integrates the decentralized nature of communication topologies with the directed nature of information propagation, making it suitable for scenarios involving massive and potentially private datasets that cannot be aggregated or processed on a centralized server. Each node continuously monitors and updates three categories of estimates—the decision variable, the average gradient of the agents’ objective functions, and an inverse approximation of the local Hessian matrix—and through cooperation drives the optimization of the entire directed network toward the global optimum. Numerical experiments validate the effectiveness of the AB-DQN method, demonstrating its closer alignment with the practical requirements of large-scale private data optimization.

关键词

多智能体系统 / 拟牛顿法 / 有向图 / 去中心化优化

Key words

multi-agent systems / quasi-Newton method / directed graph / decentralized optimization

[1] BOYD S P, VANDENBERGHE L. Convex optimization[M]. Cambridge:Cambridge University Press, 2004.
[2] GOODFELLOW I, BENGIO Y, COURVILLE A, et al. Deep learning[M]. Cambridge, Mass: MIT Press, 2016.
[3] NOCEDAL J, WRIGHT S J. Numerical optimization[M]. New York: Springer, 2006.
[4] 苏爱玲.基于Hession矩阵稳定性统计点的通信抗干扰算法[J].科技通报,2014,30(4):152-154.
SU A L. Communication anti-interference algortihm based on stability statistics of hession matrix[J]. Bull Sci Technol, 2014,30(4):152-154.
[5] NAJAFABADI M M, KHOSHGOFTAAR T M, VILLANUSTRE F, et al. Large-scale distributed L-BFGS[J]. Journal of Big Data, 2017, 4(1): 22.
[6] BOTTOU L, CURTIS F E, NOCEDAL J. Optimization methods for large-scale machine learning[J]. SIAM review, 2018, 60(2): 223-311.
[7] SHI W, LING Q, WU G, et al. Extra: An exact first-order algorithm for decentralized consensus optimization[J]. SIAM Journal on Optimization, 2015, 25(2): 944-966.
[8] CHANG T H, HONG M Y, WANG X F. Multi-agent distributed optimization via inexact consensus ADMM[J]. IEEE Transactions on Signal Processing, 2015, 63(2): 482-497.
[9] XU J M, ZHU S Y, SOH Y C, et al. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes[C]//2015 54th IEEE Conference on Decision and Control (CDC). IEEE, 2016: 2055-2060.
[10] SHORINWA O, SCHWAGER M. Distributed quasi-Newton method for multi-agent optimization[J]. IEEE Transactions on Signal Processing, 2024, 72: 3535-3546.
[11] LI B Y, CEN S C, CHEN Y X, et al. Communication-efficient distributed optimization in networks with gradient tracking and variance reduction[J]. Journal of Machine Learning Research, 2020, 21(180): 1-51.
[12] DANESHMAND A, SCUTARI G, DVURECHENSKY P, et al. Newton method over networks is fast up to the statistical precision[C]//International Conference on Machine Learning. PMLR, 2021: 2398-2409.
[13] WANG L P, WU H, ZHANG H C. A decentralized primal-dual method with quasi-newton tracking[J]. IEEE Transactions on Signal Processing, 2025, 73: 1323-1336.
[14] ZHANG J J, LIU H K, SO A M, et al. Variance-reduced stochastic quasi-Newton methods for decentralized learning[J]. IEEE Transactions on Signal Processing, 2023, 71: 311-326.
[15] ZHU M H, MARTÍNEZ S. Discrete-time dynamic average consensus[J]. Automatica, 2010, 46(2): 322-329.

基金资助

国家自然科学基金项目(62166013),广西自然科学基金项目(2022GXNSFAA035499)