User-Level Local Differential Privacy

由于不断增长的用户需求和保护个人数据隐私的法律的要求，对数据私有化和匿名化方法的研究越来越多。删除个人身份信息（如姓名或电子邮件地址）的特别方法已被证明是不够的，因为它能够链接一系列来源的数据。特别是，在高维数据集中，通常情况下，每个人都拥有独特的特征组合，即使删除了个人标识符，也可以进行识别。正因为如此，隐私的严格数学公式是可取的。差分隐私就是这样一种表述，通常被视为黄金标准，其中可信的数据聚合器用随机噪声干扰输出统计，使得恶意攻击者无法以高度的置信度推断出数据集中任何个体的原始值。本地差分隐私（LDP）是一种更严格的条件，其中没有可信的数据聚合器，因此每个人在将其数据发送到（可能是恶意的）数据聚合器之前都会对其数据进行干扰，以便无法以高度的置信度推断原始值。如果每个人都拥有多个数据，那么私有化他们的数据的问题就变得更加困难，因为不仅需要私有化每个数据，而且还需要私有化这些数据之间可能的交互。另一方面，如果每个人都拥有多个数据，理论上应该可以构建比每个用户只有一个数据更好的估计器，因为有更多的可用数据。这种设置，其中每个人持有多个数据片段，我们寻求私有化整个集合，被称为用户级LDP。到目前为止，我们的研究的目的是在用户级LDP下的一系列估计问题下构造统计量的估计量，并证明这些估计量是极小极大率最优的。虽然在用户级LDP下已经有一些问题的估计器的例子，但目前缺乏对其中一些是否是最小最大最优的理解。由于现有的工具来证明标准LDP问题的极大极小最优性不直接适合用户级LDP，因此需要开发新方法或以谨慎和创造性的方式应用现有方法。

Due to growing user demands and legal requirements to protect the privacy of individuals' data, there is an increasing body of research in methods of privatising and anonymising data. Ad-hoc methods of removing personal identifying information such as names or email addresses have been shown to be inadequate due to ability to link data across a range of sources. In particular, in high dimensional datasets, it is often the case that each individual holds a unique combination of characteristics, making identification possible even with personal identifiers removed. Because of this, rigorous mathematical formulations of privacy are desirable. Differential Privacy is one such formulation, often seen as the gold standard, where a trusted data aggregator perturbs the output statistic with random noise such that a malicious adversary cannot deduce with a high degree of confidence the original value of any individual in the dataset. Local Differential Privacy (LDP) is an even more stringent condition where there is no trusted data aggregator, and so each individual instead perturbs their data before sending it to a (possibly malicious) data aggregator so that the original value cannot be deduced with a high degree of confidence. If each individual holds multiple pieces of data, then the problem of privatising their data becomes harder, as not only does one need to privatise each piece of data, but also the possible interactions of those data. On the other hand, if each individual holds multiple pieces of data, it should be possible in theory to construct better estimators than if each user only had a single piece of data, due to the simple fact that there is more available data. This setup, where each individual holds multiple pieces of data and we seek to privatise the entire collection, is referred to as User-Level LDP. The aim of our research thus far is to construct estimators of statistical quantities under a range of estimation problems under User-Level LDP, and to prove that these estimators are minimax rate optimal. Whilst there are already a few instances of estimators for some problems under User-Level LDP, there is currently a lack of understanding of whether some of these are minimax optimal or not. As existing tools to prove the minimax optimality of standard LDP problems are not directly suited for User-Level LDP, either new methods will need to be developed or existing ones applied in careful and creative manners.