Computer Science ›› 2026, Vol. 53 ›› Issue (6A): 250700050-10.doi: 10.11896/jsjkx.250700050

• Network & Communication • Previous Articles     Next Articles

Variance-reduced Distributed Stochastic Compositional Optimization Algorithm over Directed Networks

LYU Qingguo1,2, HE Chenglong1, HU Hanqing2, ZHANG Wei1,3, DAI Xiangguang1, ZHANG Keke3, GUAN Mingyu1   

  1. 1 Key Laboratory of Intelligent Information Processing and Control,Chongqing Three Gorges University,Chongqing 404100,China
    2 College of Computer Science,Chongging University,Chongqing 400040,China
    3 School of Artificial Intelligence and Big Data,Chongqing College of Electronic Engineering,Chongqing 400015,China
  • Online:2026-06-16 Published:2026-06-12
  • About author:LYU Qingguo,born in 1994,Ph.D,associate researcher.His main research interests include privacy protection,distributed optimization,machine learning and smart grids.
    ZHANG Wei,born in 1970,Ph.D,professor.His main research interests include information security and computational intelligence.
  • Supported by:
    Natural Science Foundation of China(62576053,62302068),Natural Science Foundation of Chongqing Innovation and Development Joint Fund(CSTB2025NSCQ-LZX0085,CSTB2023NSCQ-LZX0135),Chongqing Postdoctoral Researcher Retention (or Recruitment) Support Program(2407013565264386,2411013576434798),Science and Technology Research Program of Chongqing Municipal Education Commission(KJZD-M202201204,KJZD-K202201205,KJQN202401232) and National Foreign Expert Program(S20250332).

Abstract: This paper investigates distributed stochastic compositional optimization over directed communication networks,where each agent holds a private compositional objective function.The goal is to minimize the weighted sum of all agents' objectives through local computation and limited communication.The directed network topology introduces asymmetric information exchange,and the compositional structure leads to noise in inner function estimation,which affects convergence and efficiency.To address these challenges,this paper proposes a variance-reduced distributed algorithm designed for directed networks.It integrates a variance reduction strategy into a gradient tracking framework,improving the accuracy of inner function estimation and reducing steady-state bias,while also lowering the per-iteration computational cost.The algorithm employs a push-sum protocol to handle communication asymmetry.It proves that,under strong convexity and smoothness,the algorithm achieves linear convergence to the global optimum.Numerical experiments validate its advantages in convergence speed,steady-state accuracy,and communication efficiency.

Key words: Distributed optimization algorithms, Gradient tracking, Variance reduction, Directed networks

CLC Number: 

  • TP301
[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.
[1] DAI Xiangguang, HE Chenglong, GUAN Mingyu, ZHANG Wei, ZHOU Yang, LIU Jianfeng, LYU Qingguo. State-decomposition Distributed Dual Averaging Algorithm for Privacy Online ConstrainedOptimization over Directed Networks [J]. Computer Science, 2025, 52(8): 411-420.
[2] LU Shu-xia, CAI Lian-xiang, ZHANG Luo-huan. Robust SVM Based on Zeroth Order Variance Reduction [J]. Computer Science, 2019, 46(11): 193-201.
[3] LI Li-jie,CHEN Duan-bing and WANG Guan-nan. Fast Algorithm for Overlapping Community Detection in Directed Networks [J]. Computer Science, 2014, 41(Z6): 258-261.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!