论文标题
在用户级隐私下的持续平均估计
Continual Mean Estimation Under User-Level Privacy
论文作者
论文摘要
我们考虑不断释放对用户级别差异私有（DP）样本流的估算平均值的估计的问题。每次瞬间，用户都会贡献样本，用户可以任意顺序到达。到目前为止，孤立地考虑了这些持续释放和用户级隐私的要求。但是，实际上，这两个要求都会汇总在一起，因为用户经常反复贡献数据并进行了多个查询。我们提供了一种算法，每次即时$ t $输出均值估算值，以使整个发行版是用户级$ \ varepsilon $ -dp，并且具有以下错误保证：用$ m_t $表示用户贡献的最大样本数量，只需$\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\释格。 $ \ tilde {o}（1/\ sqrt {t}+\ sqrt {m} _t/t/t \ varepsilon）$。这是通用错误保证，对用户的所有到达模式有效。此外，它（几乎）（几乎）与用户贡献相同数量的样本数量时的单个释放设置的现有下限匹配。
We consider the problem of continually releasing an estimate of the population mean of a stream of samples that is user-level differentially private (DP). At each time instant, a user contributes a sample, and the users can arrive in arbitrary order. Until now these requirements of continual release and user-level privacy were considered in isolation. But, in practice, both these requirements come together as the users often contribute data repeatedly and multiple queries are made. We provide an algorithm that outputs a mean estimate at every time instant $t$ such that the overall release is user-level $\varepsilon$-DP and has the following error guarantee: Denoting by $M_t$ the maximum number of samples contributed by a user, as long as $\tildeΩ(1/\varepsilon)$ users have $M_t/2$ samples each, the error at time $t$ is $\tilde{O}(1/\sqrt{t}+\sqrt{M}_t/t\varepsilon)$. This is a universal error guarantee which is valid for all arrival patterns of the users. Furthermore, it (almost) matches the existing lower bounds for the single-release setting at all time instants when users have contributed equal number of samples.
