Private k-Means Clustering with Stability Assumptions

Moshe Shechner, Or Sheffet, Uri StemmerAISTATS 2020 · OpenReview

Abstract

Clustering is a fundamental task in data science, yet performing it under the constraints of Differential Privacy (DP) often introduces significant noise that degrades utility. This paper investigates private clustering under input-stability assumptions, where the dataset possesses a clear inherent structure. We present a simplified, efficient algorithm for $k$-means and $k$-median clustering that achieves state-of-the-art utility bounds. Furthermore, we provide the first-ever solution for stable clustering in the Local Differential Privacy (LDP) model, where users do not trust a central aggregator with their raw data.

Introduction

Differential Privacy (DP) has become the gold standard for protecting individual privacy in data analysis. It ensures that the presence or absence of a single data point does not significantly alter the output of an algorithm. However, applying DP to $k$-means clustering is notoriously difficult. Standard $k$-means is NP-hard, and the sensitivity of cluster centers to individual points often necessitates the addition of large amounts of noise, which can obscure the underlying patterns.

Many real-world datasets are "stable" or "well-separated," meaning the optimal $k$-way partition is significantly more descriptive than any $(k-1)$-way partition. This paper leverages these stability properties to bypass the complexities of general-purpose private clustering, offering a more practical and robust algorithmic framework.

The Stability Framework

This research focuses on $\phi$-well separated instances. In these datasets, the ratio of the optimal $k$-means cost to the optimal $(k-1)$-means cost is at most $\phi^2$. This mathematical condition implies that the clusters are distinct enough that even a noisy approximation can identify the general "neighborhood" of the true centers.

One of the paper's key theoretical contributions is the unification of various stability definitions. The authors prove that several disparate definitions of clustering stability used in previous literature are actually equivalent up to a constant factor, providing a more cohesive foundation for future research in the field.

The Private-Stable-k-Means Algorithm

Previous attempts to solve private clustering for stable instances relied on the "sample-and-aggregate" framework. While theoretically sound, this framework is complex to analyze and difficult to implement, particularly in decentralized settings.

The authors propose a significantly simpler approach called Private-Stable-k-Means. The algorithm follows a refined Lloyd-style logic:

  1. Coarse Initialization: The algorithm begins by running an existing, potentially low-accuracy private $k$-means algorithm to establish a set of initial centers.
  2. Core Point Identification: For each initial center, the algorithm identifies a subset of data points that have a "clear preference" for that center—meaning they are significantly closer to it than to any other center.
  3. Private Refinement: The algorithm calculates the average of these "core" points for each cluster. To maintain privacy, Gaussian noise is added to these averages.
  4. Selection: Finally, a private comparison determines whether the refined centers or the initial centers yield a better $k$-means cost, ensuring the algorithm never performs worse than the baseline.

This method is also adapted for $k$-median clustering by replacing the averaging step with private convex optimization.

Local Differential Privacy (LDP)

A major breakthrough of this work is the extension of stable clustering to the Local Differential Privacy model. In LDP, data is privatized on the user's device before being sent to a server. Because the Private-Stable-k-Means algorithm avoids the complex sample-and-aggregate framework, it can be implemented using standard LDP-compliant averaging and counting tools. This results in the first LDP protocol for stable $k$-means, achieving an error bound that scales with $n^{0.51}$ (where $n$ is the number of users).

Key Results and Utility

The proposed algorithm achieves a $(1 + O(\phi^2))$ approximation for the $k$-means cost on stable instances. Additionally, the centers returned are within $O(\phi^2)$ distance (Wasserstein distance) of the true optimal centers. These results match the best known theoretical limits while requiring significantly less "separability" in the data than previous state-of-the-art methods.

Limitations and Future Work

While the algorithm provides high utility for stable datasets, its performance is fundamentally tied to the stability parameter $\phi$. If a dataset lacks clear cluster separation, the algorithm reverts to the performance of the coarse initialization.

Furthermore, the current approach does not yet provide a private analogue for handling "expensive" clusters—those with high internal variance. Developing a private version of sampling-based approximation schemes (such as the PTAS by Inaba et al.) remains an open challenge for the community. Nevertheless, this work represents a significant step forward in making private clustering both simpler and more effective for real-world applications.

Summary updated

Abstract

We study the problem of differentially private clustering under input-stability assumptions. Despite the ever-growing volume of works on differential privacy in general and differentially private c...
BibTeX
@inproceedings{shechner2020private,
  author = {Moshe Shechner and Or Sheffet and Uri Stemmer},
  title = {{Private k-Means Clustering with Stability Assumptions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=uUSMVTkod8F},
}
Figure