一轮局部隐私 k 均值

ICMLApr, 2021

Locally Private k-Means in One Round

Alisa Chang, Badih Ghazi, Ravi Kumar, Pasin Manurangsi

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

Abstract

We provide an approximation algorithm for k-means clustering in the one-round (aka non-interactive) local model of →

k-means clustering differential privacy approximation algorithm local model communication

发现论文，激发创造

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

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

Aug, 2020

本地隐私 k-Means 聚类

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

Jul, 2019

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

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

Apr, 2018

FastLloyd: 基于差分隐私的联邦式、准确、安全、可调整的 $k$-Means 聚类

在水平联邦环境中，我们研究了隐私保护的 k-means 聚类问题，并通过综合差分隐私和安全计算的方法提出了一个更快速、更加隐私安全和更准确的设计。

May, 2024

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

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