计算机科学 ›› 2026, Vol. 53 ›› Issue (6A): 250700050-10.doi: 10.11896/jsjkx.250700050
吕庆国1,2, 贺成龙1, 胡汉卿2, 张伟1,3, 代祥光1, 张可可3, 管明宇1
LYU Qingguo1,2, HE Chenglong1, HU Hanqing2, ZHANG Wei1,3, DAI Xiangguang1, ZHANG Keke3, GUAN Mingyu1
摘要： 研究了有向通信网络中分布式随机组合优化问题,其中网络中的每个节点拥有一个私有的组合型目标函数,目标是通过局部计算与有限通信协作最小化所有节点目标函数的加权和。由于通信拓扑为有向图结构,节点间的信息交互具有非对称性,同时随机组合优化带来的内层函数估计噪声也对算法的收敛性与计算效率构成挑战。为此,提出了一种适用于有向网络的基于方差缩减的分布式随机组合优化算法。该算法在梯度跟踪框架下融合了方差缩减策略,一方面有效提升了内层函数估计的准确性,降低了由估计误差引发的稳态偏差;另一方面显著降低了每轮迭代的计算负担。此外,算法设计考虑了有向图结构,利用推和协议以适应非对称网络环境。在理论方面,证明了所提算法可实现线性收敛到全局最优解的性能。数值实验进一步验证了算法在收敛速度、稳态误差及通信效率方面的优越性。
中图分类号:
| [1] WANG M,FANG E X,LIU H.Stochastic compositional gra-dient descent:algorithms for minimizing compositions of expected-value functions[J.] Mathematical Programming,2017,161(1/2):419-449 [2] BOTTOU L,CURTIS F E,NOCEDAL J.Optimization methods for large-scale machine learning[J].SIAM Review,2018,60(2):223-311. [3] RAJA H,BAJWA W U.Cloud K-SVD:A collaborative dictionary learning algorithm for big,distributed data[J].IEEE Transactions on Signal Processing,2016,64(1):173-188. [4] DRIGGS D,TANG J,LIANG J,et al.A stochastic proximal alternating minimization for nonsmooth and non convex optimization[J].SIAM Journal of Imaging Sciences,2021,14(4):1932-1970. [5] CHEN T,SUN Y,YIN W.Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization[J].IEEE Transactions on Signal Processing,2021,69:4937-4948. [6] FINN C,ABBEEL P,LEVINE S.Model-agnostic meta-learning for fast adaptation of deep networks[C]//International Confe-rence on Machine Learning.PMLR,2017:1126-1135. [7] SUTTON R S,BARTO A G.Reinforcement learning:An introduction[M].MIT Press,2018. [8] NIU F,RECHT B,RE C,et al.Hogwild!:A lock-free ap-proach to parallelizing stochastic gradient descent[J].arXiv:1106.5730,2011. [9] ZHANG K K,LYU Q G,LIAO X F,et al.Zeroth-Order Decentralized Dual Averaging for Online Optimization With Privacy Consideration[J].IEEE Transactions on Emerging Topics in Computational Intelligence,2024,8(6):3754-3766. [10] CHENG H Q,LYU Q G,HU J,et al.Decentralized Online Dual Averaging Optimization Ensuring Differential Privacy and Expected Regret [C]//2024 International Conference on Neuromorphic Computing(ICNC).2025. [11] CHEN Y,ZHAI Q,ZHOU Y,et al.A Traffic Simulation Algorithm for Time-Trigger Flows in Asynchronous Time-Sensitive Networking[C]//2023 China Automation Congress(CAC).2023. [12] LUO X,LI X,LI S,et al.Consensus for linear multi-agent systems with constant and time-varying communication delays via delay-decomposition approach[C]//Proceeding of the 11th World Congress on Intelligent Control and Automation.2015. [13] SONG Q,MENG D,LIU F.Consensus-based iterative learning of heterogeneous agents with application to distributed optimization[J].Automatica,2022,137:110096. [14] GAO H,HUANG H.Fast training method for stochastic compositional optimization problems[C]//Advances in Neural Information Processing Systems.Curran Associates Inc.,2021:25334-25345. [15] ZHAO S,LIU Y.Distributed stochastic compositional optimization problems over directed net works[J].Computational Optimization and Applications,2024,87(1):249-288. [16] MONARDO V,IYER A,DONEGAN S,et al.Plug-And-PlayImage Reconstruction Meets Stochastic Variance-Reduced Gradient Methods[C]//2021 IEEE International Conference on Image Processing(ICIP).2021. [17] BULUSU S,LI Q,VARSHNEY P K.On Convex StochasticVariance Reduced Gradient for Adversarial Machine Learning[C]//2019 IEEE Global Conference on Signal and Information Processing(GlobalSIP).2020. [18] NIU Y,LI H,WANG Z,et al.A Distributed Stochastic Proximal-Gradient Algorithm for Composite Optimization[J].IEEE Transactions on Control of Network Systems,2021,8(3):1383-1393. [19] WANG Z,LI H.Edge-Based Stochastic Gradient Algorithm for Distributed Optimization[J].IEEE Transactions on Network Science and Engineering,2023,7(3):1421-1430. [20] WANG X,ZHU Q.Research on Stochastic Gradient and Recursive Least Squares Deck Motion Prediction Fusion Algorithm Based on Autoregressive Model[C]//2022 IEEE International Conference on Mechatronics and Automation(ICMA).2022. [21] DONG R,ZHANG Y,ZHANG Y.Recursive and iterative stochastic gradient algorithms based on two-step update estimation for wiener systems[C]//2017 11th Asian Control Conference(ASCC).2017. [22] QURESHI M I,XIN R,KAR S,et al.Variance Reduced Sto-chastic Optimization Over Directed Graphs with Row and Co-lumn Stochastic Weights[C]//2023 57th Asilomar Conference on Signals,Systems,and Computers.2023. [23] SUN A T.Research on Big Data Distributed Computing Model and Algorithm Optimization for Complex Network Analysis[C]//2025 International Conference on Digital Analysis and Processing,Intelligent Computation(DAPIC).2025. [24] HUANG Z,LIU F,TANG M,et al.A distributed computingframework based on lightweight variance reduction method to accelerate machine learning training on blockchain[J].China Communications,2020,17(9):77-89. [25] ERCIYES K.A parallel closed centrality algorithm for complex networks[C]//2021 2nd International Informatics and Software Engineering Conference(IISEC).2021. [26] LI S,LIANG X,CHEN Y,et al.A Centralized Block Placement Algorithm Based on Sequence Pair Representation[C]//2024 13th International Conference on Communications,Circuits and Systems(ICCCAS).2024. [27] HUANG H,CHEN X,WANG L,et al.EH-SCSD:A Semi Centralized and Semi Distributed Clustered Routing Algorithm Based on EHWSN[C]//2023 2nd International Conference on Sensing,Measurement,Communication and Internet of Things Technologies(SMC-IoT).2024. [28] BRACKRTT P,LIU S,LIU Y.SC-MAIRL:Semi-CentralizedMulti-Agent Imitation Reinforcement Learning[J].IEEE Access,2023,11:57965-57976. [29] XIN R,KHAN U A,KAR S.Variance-reduced decentralizedstochastic optimization with accelerated convergence[J].IEEE Transactions on Signal Processing,2020,68:6255-6271. |
|
||
首页