Jul, 2023
连续观察下的聚类差分隐私
Differential Privacy for Clustering Under Continual Observation
Max Dupré la Tour, Monika Henzinger, David Saulpic
TL;DR我们考虑在 $ R^d $ 中进行隐私数据集聚类的问题
Abstract
We consider the problem of clustering privately a dataset in $\mathbb{R}^d$
that undergoes both →
发现论文，激发创造
带有恒定乘性误差的差分隐私 k 均值算法
本研究针对欧几里得 k 均值问题，设计了新的差分隐私算法，其在中心模型和本地模型中均获得了显著提高的误差保证，并且还能计算私有 corsets 来处理 k 均值聚类问题。
Apr, 2018
连续观察下差分隐私的代价
研究差分隐私机制在连续发布模型中的准确性并对一些基本问题的批处理模型下的最优性做了界限，发现连续发布算法的最坏情况误差是最佳批处理算法的大约 T 的三分之一倍，揭示了连续发布模型中涉及求和等问题的困难性。
Dec, 2021
利用指数机制和最大覆盖实现差分隐私的 $k$- 均值聚类
介绍了一种新的差分隐私算法，该算法通过将问题转化为基于网格的最大覆盖问题的一系列实例，实现了较低的加性误差并保持恒定的乘性误差，在 $k$-means 聚类问题上取得了更好的实验效果。
Sep, 2020
差分隐私聚类：紧密逼近比率
本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。
Aug, 2020
差分隐私的几何学：稀疏和近似情况
通过使用关联的高斯噪声和线性回归步骤，我们基于差分隐私机制的多项式对数组进行了矩阵突触连接和遗传差异，从而在线性查询的上下文中研究了准确性和隐私之间的权衡。
Dec, 2012