Taking online decisions is a part of everyday life. Think of buying a house, parking a car or taking part in an auction. We often take those decisions publicly, which may breach our privacy - a party observing our choices may learn a lot about our preferences. In this paper we investigate the online stopping algorithms from the privacy preserving perspective, using a mathematically rigorous differential privacy notion. In differentially private algorithms there is usually an issue of balancing the privacy and utility. In this regime, in most cases, having both optimality and high level of privacy at the same time is impossible. We propose a natural mechanism to achieve a controllable trade-off, quantified by a parameter, between the accuracy of the online algorithm and its privacy. Depending on the parameter, our mechanism can be optimal with weaker differential privacy or suboptimal, yet more privacy-preserving. We conduct a detailed accuracy and privacy analysis of our mechanism applied to the optimal algorithm for the classical secretary problem. Thereby the classical notions from two distinct areas - optimal stopping and differential privacy - meet for the first time.


翻译:在线决策是日常生活的一部分。 想象一下买房子、停车或参加拍卖。 我们经常公开做出那些决定, 这可能侵犯我们的隐私, 观察我们选择的一方可能会从我们的偏好中学到很多东西。 在本文中, 我们从隐私保护的角度来调查在线停止算法, 使用数学上严格的差异性隐私概念。 在不同的私人算法中, 通常有一个平衡隐私和实用性的问题。 在这一制度中, 在大多数情况下, 在同一时间拥有最佳和高程度的隐私是不可能的。 我们建议一种自然机制, 实现可控制的交换, 用参数量化的在线算法的准确性及其隐私。 根据参数, 我们的机制可以优化, 使用较弱的差别性隐私或次优、 更优的隐私保护。 我们对适用于古典秘书问题最佳算法的机制进行详细的准确性和隐私分析。 从两个不同领域 — 最佳停止和差异的隐私—— 的经典概念, 首次见面 。

0
下载
关闭预览

相关内容

移动数字广告与互联网反欺诈蓝皮报告
专知会员服务
26+阅读 · 2021年5月13日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
52+阅读 · 2020年9月7日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
已删除
将门创投
3+阅读 · 2019年9月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Arxiv
0+阅读 · 2021年8月19日
Arxiv
4+阅读 · 2019年12月2日
Arxiv
3+阅读 · 2017年12月14日
VIP会员
相关VIP内容
移动数字广告与互联网反欺诈蓝皮报告
专知会员服务
26+阅读 · 2021年5月13日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
52+阅读 · 2020年9月7日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
已删除
将门创投
3+阅读 · 2019年9月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Top
微信扫码咨询专知VIP会员