计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (8): 411-420.doi: 10.11896/jsjkx.250300083

• 信息安全 • 上一篇    

有向网络下隐私在线约束优化问题的状态分解分布式对偶平均算法

代祥光1, 贺成龙2, 管明宇1, 张伟1, 周炀3, 刘建峰1, 吕庆国4   

  1. 1 重庆三峡学院智能信息处理与控制重庆高校市级重点实验室 重庆 404100
    2 重庆三峡学院数学与统计学院 重庆 404100
    3 腾讯科技有限公司 广州 510000
    4 重庆大学计算机学院 重庆 400715
  • 收稿日期:2025-03-17 修回日期:2025-05-07 出版日期:2025-08-15 发布日期:2025-08-08
  • 通讯作者: 张伟(weizhang@sanxiau.edu.cn)
  • 作者简介:(daixiangguang@163.com)
  • 基金资助:
    重庆市自然科学基金(CSTB2023NSCQ-LZX0135,CSTB2022NSCQ-MSX1627,CSTB2022NSCQ-MSX1285);重庆市教委科学技术研究项目(KJZD-M202201204,KJZD-K202201205,KJQN202301230)

State-decomposition Distributed Dual Averaging Algorithm for Privacy Online ConstrainedOptimization over Directed Networks

DAI Xiangguang1, HE Chenglong2, GUAN Mingyu1, ZHANG Wei1, ZHOU Yang3, LIU Jianfeng1, LYU Qingguo4   

  1. 1 Key Laboratory of Intelligent Information Processing and Control,Chongqing Three Gorges University,Chongqing 404100,China
    2 School of Mathematics and Statistics,Chongqing Three Gorges University,Chongqing 404100,China
    3 Tencent Technology Co.,Ltd.,Guangzhou 510000,China
    4 Computer Science,Chongging University,Chongqing 400715,China
  • Received:2025-03-17 Revised:2025-05-07 Online:2025-08-15 Published:2025-08-08
  • About author:DAI Xiangguang,born in 1986,Ph.D,professor.His main research interests include optimization algorithms,neural networks,clustering and pattern recognition.
    ZHANG Wei,born in 1970,Ph.D,professor.His main research interests include information security and computational intelligence.
  • Supported by:
    Chongqing Natural Science Foundation (CSTB2023NSCQ-LZX0135,CSTB2022NSCQ-MSX1627,CSTB2022NSCQ-MSX1285) and Chongqing Municipal Education Commission Science and Technology Research Project (KJZD-M202201204, KJZD-K202201205,KJQN202301230).

PDF (PC)

9

摘要： 文中研究了一类具有公共约束集的分布式在线约束优化问题。网络中的各个节点通过局部计算和通信协同求解该问题,每个节点仅能访问自身的局部损失函数,该函数的取值依赖于其每次迭代中的决策变量。然而,由于节点在通信过程中不断广播与隐私相关的信息,大多数现有算法可能面临隐私泄露的风险。为此,提出了一种高效的状态分解分布式对偶平均算法。该算法结合状态分解和梯度调整策略,以增强隐私保护能力,同时消除有向网络中的不平衡性。值得注意的是,该算法无需额外的隐藏信号,也不会显著增加计算量。理论分析表明,该方法不仅能实现次线性遗憾,还能够有效保护各节点损失函数的隐私性。此外,通过仿真实验验证了该算法的收敛性和可行性。

关键词: 在线约束优化, 分布式对偶平均算法, 状态分解, 有向网络, 隐私保护

Abstract: This paper investigates a class of distributed online constrained optimization problems with a common constraint set.In this setting,nodes in the network collaborate to solve the problem through local computation and communication.Each node can only access its own local loss function,whose value depends on its decision variables at each iteration.However,since nodes continuously broadcast information related to their private data during communication,most existing algorithms face the risk of privacy leakage.To address this issue,this paper proposes an efficient state decomposition-based distributed dual averaging algorithm.This algorithm integrates state decomposition and gradient adjustment strategies to enhance privacy protection while mitigating imbalances in directed networks.Notably,it does not require additional hidden signals or significantly increase computational complexity.Theoretical analysis shows that the proposed method achieves the desired sublinear regret while effectively preserving the privacy of each node's loss function.Furthermore,simulation experiments confirm the convergence and feasibility of the algorithm.

Key words: Online constrained optimization, Distributed dual averaging, State decomposition, Directed networks, Privacy protection

中图分类号: 

  • TP301
[1]LIU Q S,LE X Y,LI K X,et al.A distributed optimization algorithm based on multiagent network for economic dispatch with region partitioning[J].IEEE Transactions on Cybernetics,2021,51(5):2466-2475.
[2]YAN JJ,CAO J,CAO Y.Distributed continuous-time algorithm for economic dispatch problem over switching communication topology[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2021,68(6):2002-2006.
[3]XU J M,ZHU S Y,SOH Y C,et al.Convergence of asynchronous distributed gradient methods over stochastic networks[J].IEEE Transactions on Automatic Control,2018,63(2):434-448.
[4]YUAN D M,HONG Y G,HO D W C,et al.Optimal distributed stochastic mirror descent for strongly convex optimization[J].Automatica,2018,90:196-203.
[5]LIANG S,WANG L Y,YIN G,et al.Distributed quasimonotone subgradient algorithm for nonsmooth convex optimization over directed graphs[J].Automatica,2019,101:175-181.
[6]NOTARNICOLA I,NOTARSTEFANO G.Asynchronous distributed optimization via randomized dual proximal gradient[J].IEEE Transactions on Automatic Control,2017,62(5):2095-2106.
[7]XU J M,ZHU S Y,SOH Y C,et al.A bregman splitting scheme for distributed optimization over networks[J].IEEE Transactions on Automatic Control,2018,63(11):3809-3824.
[8]LI X X,XIE L H,HONG Y G,et al.Distributed aggregative optimization over multi-agent networks[J].IEEE Transactionson Automatic Control,2022,67(6):3165-3171.
[9]CHENG SS,LIANG S,HONG Y G,et al.Distributed stochastic algorithm for convex optimization over directed graphs[C]//2019 Chinese Control And Decision Conference(CCDC).IEEE,2019:101-106.
[10]LI Q,LIAO Y X,WU K M,et al.Parallel and distributed optimization method with constraint decomposition for energy management of microgrids[J].IEEE Transactionson Smart Grid,2021,12(6):4627-4640.
[11]JIANG X,ZENG X L,SUN J,et al.Distributed stochastic gradient tracking algorithm with variance reduction for non-convex optimization[J].IEEE Transactions on Neural Networks and Learning Systems,2023,34:5310-5321.
[12]DAI P C,YU W W,WANG H,et al.Distributed Actor-Critic Algorithms for Multiagent Reinforcement Learning Over Direc-ted Graphs[J].IEEE Transactions on Neural Networks and Learning Systems,2022,34(10):7210-7221.
[13]WU J Y,TIAN Y P.Online Distributed Newton Step Algorithm for Multi-agent Optimization Over General Unbalanced Networks[C]//2024 IEEE 18th International Conference on Control & Automation(ICCA).IEEE,2024:174-179.
[14]ZHANG J H,MA D.A Novel State Decomposition-Based Privacy-Preserving Algorithm for Distributed Optimization Over Directed Networks[C]//2024 14th Asian Control Conference(ASCC).IEEE,2024:1145-1150.
[15]MAKRIDIS E,CHARALAMBOUS T.A Linear Push-PullAverage Consensus Algorithm for Delay-Prone Networks[C]//2024 European Control Conference(ECC).IEEE,2024:743-749.
[16]MAI V S,ABED E H.Distributed optimization over directedgraphs with row stochasticity and constraint regularity[J].Automatica,2019,102:94-104.
[17]LYU Q G,ZHANG K K,DENG S J,et al.Privacy-preserving decentralized dual averaging for online optimization over directednetworks[J].IEEE Transactions on Industrial Cyber-Physical Systems,2023,1:79-91.
[18]WANG H J,LIU K,HAN D Y,et al.Privacy-preserving distributed online stochastic optimization with time-varying distributions[J].IEEE Transactions on Control of Network Systems,2023,10(2):1069-1082.
[19]WANG Y Q.Privacy-preserving average consensus viastate decomposition[J].IEEE Transactions on Automatic Control,2019,64(11):4711-4716.
[20]LI J,ZHU X,WU Z,et al.Online distributed dual averaging algorithm for multi-agent bandit optimization over timevarying general directed networks[J].Information Sciences,2021,581:678-693.
[21]DUCHI J C,AGARWAL A,WAINWRIGHT M J.Dual averaging for distributed optimization:convergence analysis and network scaling[J].IEEE Transactions on Automatic Control,2012,57(3):592-606.
[22]YAN JJ,CAO J D.Privacy preservation of optimization algorithm over unbalanced directed graph[J].IEEE Transactions on Network Science and Engineering,2022,9(4):2164-2173.
[23]CARNEVALE G,FARINA F,NOTARNICOLA L,et al.GTAdam:gradient tracking with adaptive momentum for distributed online optimization[J].IEEE Transactions on Control of Network Systems,2023,10(3):1436-1448.
[24]HUANG L Y,WU JF,SHI D W,et al.Differential privacy in distributed optimization with gradient tracking[J].IEEE Tran-sactions on Automatic Control,2024,69(9):5727-5742.
[25]DING T,ZHU S Y,HE J P,et al.Consensus-based distributed optimization in multi-agent systems:convergence and differential privacy[C]//2018 IEEE Conference on Decision and Control.IEEE,2018:3409-3414.
[26]BU X Y,DONG T.Differential privacy optimal consensus formultiagent system by using functional perturbation[C]//2019 6th International Conference on Information,Cybernetics,and Computational Social Systems.IEEE,2019:157-162.
[27]ZHANG C,WANG Y.Enabling privacy-preservation indecen-tralized optimization[J].IEEE Transactions on Control of Network Systems,2019,6(2):679-689.
[28]LU Y,ZHU M.Privacy preserving distributed optimizationusing homomorphic encryption[J].Automatica,2018,96:314-325.
[29]ZANG H R,YANG T T,LIU H B,et al.Study on cryptographic verification of distributed federated learning for internet of things[J].Computer Science,2024,51(SI):1062-1066.
[30]SUN M,DING X N,CHENG Q.Federated learning scheme based on differential privacy[J].Computer Science,2024,51(S1):912-917.
[31]TANG L T,WANG D,ZHANG L F,et al.Federated learning scheme based on secure multi-party computation and differential privacy[J].Computer Science,2022,49(9):297-305.
[32]SUN J M,ZHAO M X.Survey ofapplication of differential privacy in edge computing[J].Computer Science,2024,51(S1):896-904.
[33]HAZAN E.Introduction to online convex optimization[J].Foundations and Trends in Optimization,2016,2(3/4):157-325.
[34]XIONG Y Y,LI X,YOU K Y,et al.Distributed online optimizationin time-varying unbalanced networks without explicit subgradients[J].IEEE Transactions on Signal Processing,2022,70:4047-4060.
[35]HAN D Y,LIU K,LIN Y M,et al.Differentially private distrib-uted online learning over time-varying digraphs via dualaveraging[J].International Journal of Robust and Nonlinear Control,2022,32(5):2485-2499.
[36]LIANG S,WANG L Y,YIN G.Dual averaging push for distributed convex optimization over time-varying directed graph[J].IEEE Transactions on Automatic Control,2020,65(4):1785-1791.
[37]HE X Y,ZHENG Z B,CHEN Z F,et al.Adaptive evolutionstrategies for stochastic zeroth-order optimization[J].IEEE Transactions on Emerging Topics in Computational Intelligence,2022,6(5):1271-1285.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发