【论文学习4】BiSample: Bidirectional Sampling for Handling Missing Data with Local Differential Privacy

0.abstract

LDP近年来受到广泛关注。现有的LDP保证的协议中，用户在将数据分享给聚合器之前，在本地对数据进行编码和扰动。然而，由于对于不同问题的不同隐私保护偏好，用户不愿意回答所有的问题。在本论文中，我们提出了一种方法来解决数据扰动的挑战，同时考虑用户的隐私偏好。具体来说，我们首先在LDP的框架上提出了一种双向采样技术值扰动。然后，我们结合双采样机制和用户隐私偏好，以避免丢失数据的扰动。理论分析和一组数据集上的实验证明所提机制的有效性。

1.introduction

LDP已经作为一种解决方法对于隐私保护数据收集和分析，因为他提供了可证明的隐私保护。LDP保证的协议一般可以分为Encode-Perturb-Aggregate范式。用户将数据编码成一种特俗的数据格式，然后出于隐私考虑扰动编码值，最后，所有扰动的值聚合到不信任的收集者。

虽然LDP可以平衡用户的隐私和数据可用性，但是现存的方法认为被调查的用户会遵循收集过程的真实性。然而，在调查过程中，用户可能拒绝吐露一些问题，由于一下担心：1）隐私保护水平不符合预期；2）用户仅仅就是不想告诉。由于扰动机制需要输入，所以用户可能会随机选择答案（或者NO）来进行扰动（我们称其为假答案）。在扰动空间中，假答案会导致回避偏见。在论文中，我们考虑了“提供空值”应用程序去考虑假答案。首次考虑了用户协作对估计精度的理解，首次提出了双采样样本机制并将其用于数值扰动，然后将双向样本推广到空值扰动。

创新点：

第一次考虑到并不是所有的用户都会提供真实数据，提出的缺失数据扰动框架为提高数据可用性提供了新的见解。
我们提出了一种数据扰动的双向采样机制。可以代替Harmony进行均值估计。此外，扩展了双样本，能够扰动空值数据。
提出的框架可以估计在隐私预算下提供真实数据用户的比率，该机制可以研究如何通过聚合器去设置合理的隐私预算。

2.Preliminaries and problem definition

2.1 Local Differentital Privacy(LDP)

LDP的标准解决方法是随机响应RR（randomized response）。特别的是，为了收集用户的敏感信息，例如，用户是HIV携带者，RR被用来扰动真实数据，同时仍可以保证

i）每个用户的答案提供了可信的可否认性
ii）聚合者可以得到整个人群的无偏估计

很多前沿的机制使用RR作为中心部分来提供隐私保证，例如[13],[14]和 [8]。为了用任意数量的可能值处理分类数据，提出了K-RR。在传统的RR算法中，每个用户以P概率分享真实值，以1-P概率提供相反的答案，故在LDP中：

用Fr表示收集者接受到真实答案的概率，在扰动之前概率可以估计为：

f*是f的无偏估计。
近年来，有文献研究了LDP下均值估计的数值扰动问题。我们引进了Harmony和Piecewise机制。