Computational Hardness of Private Coreset

Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi

Abstract

We study the problem of differentially private (DP) computation of coresets for the $k$-means objective. For a given input set of points, a coreset is another set of points such that the $k$-means objective for any candidate solution is preserved up to a multiplicative $(1 \pm \alpha)$ factor (and some additive factor). We prove the first computational lower bounds for this problem. Specifically, assuming the existence of one-way functions, we show that no polynomial-time $(\epsilon, 1/n^{\omega(1)})$-DP algorithm can compute a coreset for $k$-means in the $\ell_\infty$-metric for some constant $\alpha > 0$ (and some constant additive factor), even for $k=3$. For $k$-means in the Euclidean metric, we show a similar result but only for $\alpha = \Theta(1/d^2)$, where $d$ is the dimension.

Introduction

In the era of massive datasets, coresets have emerged as a vital tool for scalable machine learning. A coreset is a small, weighted summary of a dataset that acts as a proxy: running an algorithm—such as $k$-means clustering—on the coreset yields a result nearly identical to running it on the full dataset. This allows for significant reductions in storage and computational overhead.

When these datasets contain sensitive personal information, it is essential that the coresets themselves are differentially private (DP). A private coreset is particularly valuable because it allows analysts to perform an unlimited number of queries, such as hyperparameter tuning or exploring different values of $k$, without further depleting the privacy budget of the original data subjects. While previous theoretical work established that small private coresets exist in an information-theoretic sense, the algorithms to find them have remained either prohibitively slow or highly inaccurate. This research investigates whether this efficiency barrier is a fundamental mathematical limit.

The Computational Gap

This paper establishes the first computational lower bounds for the private coreset problem. The central finding is a striking dichotomy: although private coresets with small error are mathematically guaranteed to exist, they are likely impossible to compute in polynomial time under standard cryptographic assumptions.

In a non-private setting, creating a coreset is trivial if size is not a constraint—one could simply output the original dataset. However, the requirement of Differential Privacy "breaks" this triviality. To satisfy DP, an algorithm must effectively "understand" the underlying data distribution rather than just copying points. This requirement triggers a computational hardness that makes the problem intractable for efficient algorithms.

Methodology: From Cryptography to Geometry

The authors prove these lower bounds using a technique known as reductio ad absurdum via a reduction from cryptography. The proof follows three main steps:

  1. The Hardness Source: The authors leverage the known hardness of generating "synthetic data" for 3-literal disjunctions. It is established that if one-way functions exist, no polynomial-time DP algorithm can accurately sanitize such data.
  2. The Reduction: They demonstrate that if an efficient algorithm existed to create a private coreset for $k$-means, that algorithm could be repurposed to solve the aforementioned "hard" synthetic data problem.
  3. The Gadget Design: To bridge the gap between discrete logical disjunctions and continuous geometry, the authors designed a specific "gadget." This gadget is a spatial arrangement of points where the $k$-means objective function effectively "checks" whether a logical clause is satisfied by a given set of centers.

Key Results

1. Hardness in the $\ell_\infty$-Metric

Assuming the existence of one-way functions, the research proves that no polynomial-time $(\epsilon, \delta)$-DP algorithm can compute a coreset for $k$-means in the $\ell_\infty$-metric with a constant approximation factor $\alpha > 0$. Remarkably, this hardness holds even for a very small number of clusters ($k=3$).

2. Hardness in the Euclidean ($\ell_2$) Metric

For the standard Euclidean metric, the results are slightly different but still restrictive. The authors rule out efficient algorithms that achieve an approximation factor better than $1 \pm \Theta(1/d^2)$, where $d$ is the dimension of the data. This suggests that as the dimensionality of the data increases, the ability to compute accurate private coresets diminishes significantly.

3. Irrelevance of Coreset Size

Crucially, the authors show that this hardness persists regardless of the coreset's size. Even if the algorithm is allowed to produce a "large" coreset, the computational difficulty of ensuring accuracy while maintaining privacy remains the bottleneck.

Conclusion and Future Directions

This work provides a rigorous explanation for why researchers have struggled to develop efficient algorithms for private coresets. It shifts the focus from algorithmic design to the fundamental limits of privacy-preserving summaries.

Several open questions remain:

  • The $k=2$ Case: The current proof requires $k=3$ centers to simulate logical disjunctions. Whether the problem remains hard for $k=2$ is currently unknown.
  • Dimension Independence: Future research may investigate whether a constant-factor hardness exists for Euclidean space that does not depend on the dimension $d$.
  • Other Objectives: While this study focuses on $k$-means, the techniques could potentially be extended to other clustering objectives, such as $k$-median or $k$-center clustering.

Summary updated

Abstract

We study the problem of differentially private (DP) computation of coreset for the $k$-means objective. For a given input set of points, a coreset is another set of points such that the $k$-means objective for any candidate solution is preserved up to a multiplicative $(1 \pm α)$ factor (and some additive factor). We prove the first computational lower bounds for this problem. Specifically, assuming the existence of one-way functions, we show that no polynomial-time $(ε, 1/n^{ω(1)})$-DP algorithm can compute a coreset for $k$-means in the $\ell_\infty$-metric for some constant $α> 0$ (and some constant additive factor), even for $k=3$. For $k$-means in the Euclidean metric, we show a similar result but only for $α= Θ\left(1/d^2\right)$, where $d$ is the dimension.
BibTeX
@inproceedings{ghazi2026computational,
  author = {Badih Ghazi and Cristóbal Guzmán and Pritish Kamath and Alexander Knop and Ravi Kumar and Pasin Manurangsi},
  title = {{Computational Hardness of Private Coreset}},
  booktitle = {FORC},
  year = {2026},
  doi = {10.4230/lipics.forc.2026.1},
}
Figure