基于差分隐私机制和单点反馈的分布式在线优化算法

doi:10.6040/j.issn.1672-3961.0.2024.231

摘要/Abstract

摘要： 针对有向网络上具有隐私保护特性的分布式在线优化问题,基于差分隐私机制提出一种分布式在线优化算法。通过符合拉普拉斯分布的随机噪声对节点的状态进行扰动,有效保护节点的隐私信息。针对梯度信息显式未知的问题,引入单点反馈估计真实的梯度,利用估计的梯度信息指导决策变量的更新,使算法能够适应梯度信息不可用的场景。理论结果表明,所提出的算法不仅能够保护节点的隐私信息同时能够实现次线性Regret,能够有效解决分布式在线优化问题。仿真结果验证了算法的有效性。

关键词: 分布式优化, 在线优化, 多智能体系统, 差分隐私机制, 单点反馈

Abstract: For distributed online optimization problem with privacy protection on directed networks, this research proposed a distributed online optimization algorithm based on differential privacy mechanism. The state of the node was disturbed by random noise which conformed to the Laplacian distribution, and the privacy information of the node was effectively protected. To solve the problem of unknown gradient information explicitly, this research introduced an one-point feedback to estimate the real gradient, and used the estimated gradient information to guide the update of decision variables, so that the algorithm could adapt to the scenario where the gradient information was unavailable. The theoretical results showed that the proposed algorithm could not only protect the privacy information of nodes but also realize the sublinear regret, and the distributed online optimization problem could be effectively solved. The simulation results verified the effectiveness of the algorithm.

Key words: distributed optimization, online optimization, multi-agent system, differential privacy mechanism, one-point feedback

中图分类号:

TP181

张波,徐悦,康乐,张贵军. 基于差分隐私机制和单点反馈的分布式在线优化算法[J]. 山东大学学报 (工学版), 2026, 56(1): 14-25.

ZHANG Bo, XU Yue, KANG Le, ZHANG Guijun. Distributed online optimization algorithm based on differential privacy mechanism and one-point feedback[J]. Journal of Shandong University(Engineering Science), 2026, 56(1): 14-25.

参考文献

[1] ZHAO Z Y, XIA L C, JIANG L Y, et al. Zeroth-order gradient tracking for decentralized learning with privacy guarantees[J]. ISA Transactions, 2024, 152: 1-14.
[2] 王程, 刘念. 基于交替方向乘子法的互联微电网系统分布式优化调度[J]. 电网技术, 2016, 40(9): 2675-2681. WANG Cheng, LIU Nian. Distributed optimal dispatching of interconnected microgrid system based on alternating direction method of multipliers[J]. Power System Technology, 2016, 40(9): 2675-2681.
[3] WANG S N, LI C G. Distributed robust optimization in networked system[J]. IEEE Transactions on Cybernetics, 2016, 47(8): 2321-2333.
[4] ZHAO Z Y. Sample-based dynamic event triggered algorithm for optimization problem of multi-agent systems[J]. International Journal of Control, Automation and Systems, 2022, 20(8): 2492-2502.
[5] 杨涛, 徐磊, 易新蕾, 等. 基于事件触发的分布式优化算法[J]. 自动化学报, 2022, 48(1): 133-143. YANG Tao, XU Lei, YI Xinlei, et al. Event-triggered distributed optimization algorithms[J]. Acta Automatica Sinica, 2022, 48(1): 133-143.
[6] XI C G, KHAN U A. Distributed subgradient projection algorithm over directed graphs[J]. IEEE Transactions on Automatic Control, 2017, 62(8): 3986-3992.
[7] LI H Q, WANG Z, CHEN G, et al. Distributed robust algorithm for economic dispatch in smart grids over general unbalanced directed networks[J]. IEEE Transactions on Industrial Informatics, 2020, 16(7): 4322-4332.
[8] 陈刚, 李志勇. 集合约束下多智能体系统分布式固定时间优化控制[J]. 自动化学报, 2022, 48(9): 2254-2264. CHEN Gang, LI Zhiyong. Distributed fixed-time optimization control for multi-agent systems with set constraints[J]. Acta Automatica Sinica, 2022, 48(9): 2254-2264.
[9] YAN F, SUNDARAM S, VISHWANATHAN S V N, et al. Distributed autonomous online learning: regrets and intrinsic privacy-preserving properties[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 25(11): 2483-2493.
[10] 刘洋. 时变非平衡图下多智能体分布式优化算法设计[D]. 大连: 大连理工大学, 2021: 35-43. LIU Yang. Design of distributed optimization algorithm for multi-agent systems over time-varying unbalanced graphs[D]. Dalian:Dalian University of Technology, 2021: 35-43.
[11] MATEOSNU(~overN)EZ D, CORTÉS J. Distributed online convex optimization over jointly connected digraphs[J]. IEEE Transactions on Network Science and Engineering, 2014, 1(1): 23-37.
[12] 吴庆涛, 朱军龙, 葛泉波, 等. 一种基于条件梯度的加速分布式在线学习算法[J]. 自动化学报, 2024, 50(2): 386-402. WU Qingtao, ZHU Junlong, GE Quanbo, et al. An accelerated distributed online learning algorithm based on conditional gradient[J]. Acta Automatica Sinica, 2024, 50(2): 386-402.
[13] PANG Y P, HU G Q. Randomized gradient-free distributed online optimization with time-varying cost functions[C] //2019 IEEE 58th Conference on Decision and Control(CDC). Nice, France:IEEE, 2019: 4910-4915.
[14] PANG Y P, HU G Q. Randomized gradient-free distributed optimization methods for a multiagent system with unknown cost function[J]. IEEE Transactions on Automatic Control, 2020, 65(1): 333-340.
[15] WANG C, XU S Y, YUAN D M, et al. Push-sum distributed online optimization with bandit feedback[J]. IEEE Transactions on Cybernetics, 2022, 52(4): 2263-2273.
[16] DWORK C. Differential privacy[C] // International Colloquium on Automata, Languages, and Programming. Berlin, Germany: Springer, 2006: 1-12.
[17] DING T, ZHU S Y, HE J P, et al. Differentially private distributed optimization via state and direction perturbation in multiagent systems[J]. IEEE Transactions on Automatic Control, 2022, 67(2): 722-737.
[18] XIONG Y Y, XU J M, YOU K Y, et al. Privacy-preserving distributed online optimization over unbalanced digraphs via subgradient rescaling[J]. IEEE Transactions on Control of Network Systems, 2020, 7(3): 1366-1378.
[19] WEI M L, YANG Z Q, JI Q T, et al. Privacy-preserving distributed projected one-point bandit online optimization over directed graphs[J]. Asian Journal of Control, 2023, 25(6): 4705-4720.
[20] ZHAO Z Y, YANG J, GAO W, et al. Differentially private distributed online optimization via push-sum one-point bandit dual averaging[J]. Neurocomputing, 2024, 572: 127184.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed