Aug, 2020

差分隐私聚类：紧密逼近比率

PDF
TL;DR本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。
differentially private clusteringeuclidean densestballk-meansk-mediansample and aggregate privacy framework
发现论文，激发创造
  • 一轮局部隐私 k 均值

    本文提出了一种算法，用于在差分隐私（DP）的一轮（也称非交互式）本地模型中进行 k 均值聚类，该算法实现的逼近比接近于最佳非私有逼近算法，改进了以前已知的仅保证大（常数）逼近比率的算法。此外，这是第一个仅需要一轮本地 DP 模型通信的 k 均值常数逼近算法，积极地解决了 Stemmer（SODA 2020）提出的一个开放性问题。我们的算法框架非常灵活；我们通过展示在（一轮）洗牌 DP 模型中也会产生类似于最优解的逼近算法来证明这一点。

    Apr, 2021

  • 带有恒定乘性误差的差分隐私 k 均值算法

    本研究针对欧几里得 k 均值问题，设计了新的差分隐私算法，其在中心模型和本地模型中均获得了显著提高的误差保证，并且还能计算私有 corsets 来处理 k 均值聚类问题。

    Apr, 2018

  • 本地隐私 k-Means 聚类

    该研究设计了一种新的算法，用于处理欧几里得 k - 均值问题的差分隐私，通过本地模型，可以大幅降低加性误差，同时保持乘性误差不变。

    Jul, 2019

  • 易实例的不同 ially-Private 聚类

    本文研究的是隐私保护聚类算法，提出了一个依据难易程度来组合本来不带保护性质的聚类算法和隐私保护结果的框架，并在高斯混合数据和 $k$-means 算法中实现了样本复杂度较小的聚类效果进行了实证评估。

    Dec, 2021

  • 集中式和本地式模型的聚类算法

    该研究提出了关于最小囊括圆问题的差分隐私算法，达到了在中心模型和本地模型下不错的精度，并演示了如何在这两个模型中使用该算法来近似 $k$-means。

    Jul, 2017

  • 具有稳定性假设的差分隐私聚类算法

    本文研究了在输入稳定性假设下的差分隐私聚类问题，提出了一种简单的算法，分析了其在 Wasserstein 距离和 k-means 代价等方面的效用，可直接应用于 “好” 的 k - 中位数实例和本地模型的差分隐私。

    Jun, 2021

  • 多样性感知聚类：计算复杂度和近似算法

    在这项研究中，我们研究了多样性感知聚类问题，其中数据点与多个属性相关联，导致交叉组。聚类解决方案需要确保从每个组中选择最少数量的聚类中心，同时最小化聚类目标，可以是 $k$-median、$k$-means 或 $k$-supplier。我们提出了参数化逼近算法，逼近比例分别为 $1+ rac {2}{e}$、$1+ rac {8}{e}$ 和 $3$，用于多样性感知 $k$-median、多样性感知 $k$-means 和多样性感知 $k$-supplier。这些逼近比例在假设 Gap-ETH 和 FPT $ eq$ W [2] 的情况下是紧密的。对于公平 $k$-median 和公平 $k$-means 与不相交设施组，我们分别提出了参数化逼近算法，逼近比例为 $1+ rac {2}{e}$ 和 $1+ rac {8}{e}$。对于公平 $k$-supplier 与不相交设施组，我们提出了一个多项式时间逼近算法，其因子为 $3$，改进了先前已知的逼近比例因子为 $5$。

    Jan, 2024

  • 离散分布身份和接近性的差分隐私测试

    该研究提供了关于差分隐私下 k 个元素分布的标识检测和接近度检验的上下界。他们提出了一般框架以建立隐私统计任务的样本复杂度的下界，同时通过构建精心选择的先验概率来证明隐私算法的下界。

    Jul, 2017

  • 连续观察下的聚类差分隐私

    我们考虑在 $ R^d $ 中进行隐私数据集聚类的问题

    Jul, 2023

  • 基于分层分离树的可扩展差分隐私聚类

    通过利用树嵌入和标准的降维技术，我们提出了一种高效易实现的算法，能够解决 $k$- 中位数和 $k$- 均值的私有聚类问题，具有很好的时间和空间复杂度，适用于大规模分布式计算环境，并有可观的隐私保障.

    Jun, 2022