We design a new algorithm for the Euclidean $k$-means problem that operates
in the local model of differential privacy. Unlike in the non-private
literature, differentially private algorithms for the $k$-means objective incur
both additive and multiplicative errors. Our algorithm significantly reduces
the additive error while keeping the multiplicative error the same as in
previous state-of-the-art results. Specifically, on a database of size $n$, our
algorithm guarantees $O(1)$ multiplicative error and $\approx n^{1/2+a}$
additive error for an arbitrarily small constant $a>0$. All previous algorithms
in the local model had additive error $\approx n^{2/3+a}$. Our techniques
extend to $k$-median clustering.
We show that the additive error we obtain is almost optimal in terms of its
dependency on the database size $n$. Specifically, we give a simple lower bound
showing that every locally-private algorithm for the $k$-means objective must
have additive error at least $\approx\sqrt{n}$.

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

本地隐私 k-Means 聚类

Locally Private k-Means Clustering

Consider an instance of Euclidean $k$-means or $k$-medians clustering. We
show that the cost of the optimal solution is preserved up to a factor of
$(1+\varepsilon)$ under a projection onto a random $O(\log(k / \varepsilon) /
\varepsilon^2)$-dimensional subspace. Further, the cost of every clustering is
preserved within $(1+\varepsilon)$. More generally, our result applies to any
dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our
bound on the dimension is nearly optimal. Additionally, our result applies to
Euclidean $k$-clustering with the distances raised to the $p$-th power for any
constant $p$.
For $k$-means, our result resolves an open problem posed by Cohen, Elder,
Musco, Musco, and Persu (STOC 2015); for $k$-medians, it answers a question
raised by Kannan.

通过投影到随机的 O (log (k/ ε) / ε²) 维子空间上，可以近似保持欧几里得 k-means 或 k-medians 聚类的最优解成本，并且适用于任何满足温和的子高斯尾条件的维度缩减映射，其维数几乎是最优的。此外，该结果适用于所有权重的欧几里得 k - 聚类。

Johnson-Lindenstrauss 变换在 k-Means 和 k-Medians 聚类中的表现

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians  Clustering

The Euclidean k-means problem is arguably the most widely-studied clustering
problem in machine learning. While the k-means objective is NP-hard in the
worst-case, practitioners have enjoyed remarkable success in applying
heuristics like Lloyd's algorithm for this problem. To address this disconnect,
we study the following question: what properties of real-world instances will
enable us to design efficient algorithms and prove guarantees for finding the
optimal clustering? We consider a natural notion called additive perturbation
stability that we believe captures many practical instances. Stable instances
have unique optimal k-means solutions that do not change even when each point
is perturbed a little (in Euclidean distance). This captures the property that
the k-means optimal solution should be tolerant to measurement errors and
uncertainty in the points. We design efficient algorithms that provably recover
the optimal clustering for instances that are additive perturbation stable.
When the instance has some additional separation, we show an efficient
algorithm with provable guarantees that is also robust to outliers. We
complement these results by studying the amount of stability in real datasets
and demonstrating that our algorithm performs well on these benchmark datasets.

本文研究在实际应用中，哪些加性扰动稳定性的实例可以设计有效算法，并证明它们能找到最优聚类。我们提出了一种稳定性定义，并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时，我们显示出一种具有证明保证的鲁棒算法，也能容忍异常值。通过研究真实数据集的稳定性，我们补充了这些结果，并展示了我们的算法在这些基准数据集上的表现。