一种满足差分隐私的图赌博机算法
作者:
作者单位:

作者简介:

卢世银(1996-), 男, 博士生, 主要研究领域为机器学习与优化;王广辉(1995-), 男, 硕士, 主要研究领域为机器学习与优化;邱梓豪(1996-), 男, 硕士生, CCF学生会员, 主要研究领域为机器学习与优化;张利军(1986-), 男, 博士, 教授, 博士生导师, CCF专业会员, 主要研究领域为机器学习与优化

通讯作者:

张利军, E-mail: zhanglj@lamda.nju.edu.cn

中图分类号:

TP181

基金项目:

国家自然科学基金(61976112); 江苏省自然科学基金(BK20200064)


Differentially Private Algorithm for Graphical Bandits
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    图赌博机是一种重要的不确定性环境下的序列决策模型, 在社交网络、电子商务和推荐系统等领域都得到了广泛的应用. 目前, 针对图赌博机的工作都只关注如何快速识别最优摇臂从而最小化累积遗憾, 而忽略了在很多应用场景中存在的隐私保护问题. 为了克服现有图赌博机算法的缺陷, 提出了一种满足差分隐私的图赌博机算法GAP (图反馈下的差分隐私摇臂消除策略). 一方面, GAP算法阶段性地根据摇臂的经验平均奖赏更新摇臂选取策略, 并在计算摇臂的经验平均奖赏时引入拉普拉斯噪声, 从而确保恶意攻击者难以根据算法输出推算摇臂奖赏数据, 保护了隐私. 另一方面, GAP算法在每个阶段根据精心构造的反馈图的独立集探索摇臂集合, 有效地利用了图形式的反馈信息. 证明了GAP算法满足差分隐私性质, 具有与理论下界相匹配的遗憾界. 在仿真数据集上的实验结果表明: GAP算法在有效保护隐私的同时取得了与现有无隐私保护的图赌博机算法相当的累积遗憾.

    Abstract:

    Graphical bandit is an important model for sequential decision making under uncertainty and has been applied in various real-world scenarios such as social network, electronic commerce, and recommendation system. Existing work on graphical bandits only investigates how to identify the best arm rapidly so as to minimize the cumulative regret while ignoring the privacy protection issue arising in many real-world applications. To overcome this deficiency, a differentially private algorithm is proposed, termed as graph-based arm elimination with differential privacy (GAP), for graphical bandits. On the one hand, GAP updates the arm selection strategy based on empirical mean rewards of arms in an epoch manner. The empirical mean rewards are perturbed by Laplace noise, which makes it hard for malicious attackers to infer rewards of arms from the output of the algorithm, and thus protects the privacy. On the other hand, in each epoch, GAP carefully constructs an independent set of the feedback graph and only explores arms in the independent set, which effectively utilize the information in the graph feedback. It is proved that GAP is differential private and its regret bound matches the theoretical lower bound. Experimental results on synthetic datasets demonstrate that GAP can effectively protect the privacy and achieve cumulative regret comparable to that of existing non-private graphical bandits algorithm.

    参考文献
    相似文献
    引证文献
引用本文

卢世银,王广辉,邱梓豪,张利军.一种满足差分隐私的图赌博机算法.软件学报,2022,33(9):3223-3235

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-03-31
  • 最后修改日期:2021-05-04
  • 录用日期:
  • 在线发布日期: 2022-06-15
  • 出版日期: 2022-09-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号