Computational Hardness of Private Coreset

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

TL;DR

This paper establishes the first computational lower bounds for creating differentially private (DP) coresets for $k$-means clustering. The authors prove that while these data summaries exist in an information-theoretic sense, finding them in polynomial time is likely impossible under standard cryptographic assumptions (specifically, the existence of one-way functions).

What Problem Does This Paper Address?

In the world of big data, coresets are a powerful tool. They are small, weighted subsets of a larger dataset that act as a "proxy"—if you run a clustering algorithm (like $k$-means) on the coreset, you get nearly the same result as if you had run it on the original, massive dataset.

When dealing with sensitive information, we want these coresets to be differentially private (DP). A private coreset would allow analysts to perform unlimited queries and tuning (like choosing the number of clusters, $k$) without further "consuming" the privacy budget of the original users.

Previous research showed that small private coresets exist, but the algorithms to find them were either incredibly slow (exponential in dimension or $k$) or had massive errors. This paper asks a fundamental question: Is this efficiency barrier a result of poor algorithm design, or is it a fundamental mathematical limit?

Methods

The authors use a technique called reductio ad absurdum via a reduction from cryptography.

  1. The Starting Point: They look at the known hardness of generating "synthetic data" for 3-literal disjunctions (a classic problem in DP research). It is known that if one-way functions exist, no polynomial-time DP algorithm can accurately sanitize such data.
  2. The Reduction: They show that if an efficient algorithm did exist to create a private coreset for $k$-means, that algorithm could be used to solve the "hard" synthetic data problem.
  3. The Gadget: To bridge the gap between discrete logic (disjunctions) and continuous geometry ($k$-means), they design a "gadget"—a specific arrangement of points where the $k$-means objective function effectively "checks" if a logical clause is satisfied.

Datasets

As a theoretical paper focused on computational complexity proofs, it does not use empirical datasets or benchmarks. Instead, it uses a constructed dataset based on the hardness results of Ullman and Vadhan (2020) to prove the mathematical lower bounds.

Key Insights and Ideas

  • The Existence-Efficiency Gap: The paper highlights a striking dichotomy. We have proofs that private coresets exist with small error, but this paper proves we likely cannot compute them efficiently. This is a rare case where the bottleneck isn't the amount of data or the privacy noise, but the computational complexity itself.
  • Privacy as a Hardness Trigger: In a non-private setting, creating a coreset is trivial if size isn't a concern (you just output the original data). However, the requirement of Differential Privacy "breaks" this triviality, forcing the algorithm to actually "understand" the data distribution, which leads to the proven hardness.
  • Metric Matters: The hardness is more severe in the $\ell_\infty$-metric (where they prove a constant error bound is hard) than in the standard Euclidean ($\ell_2$) metric (where the hardness scales with the dimension $d$).

Key Results

  • $\ell_\infty$-Metric Hardness: Assuming one-way functions exist, no polynomial-time $(\varepsilon, \delta)$-DP algorithm can compute a coreset for $k$-means in the $\ell_\infty$-metric with a constant approximation factor $\alpha > 0$, even for just $k=3$ clusters.
  • Euclidean ($\ell_2$) Hardness: For the standard Euclidean metric, the authors rule out efficient algorithms that achieve an approximation factor better than $1 \pm \Theta(1/d^2)$, where $d$ is the dimension.
  • Size Irrelevance: The authors show that this hardness persists even if we don't care about the size of the coreset. Even a "large" coreset is hard to compute privately if it must be accurate.

Limitations and Future Work

  • The $k=2$ Gap: The current proof relies on a "gadget" that requires $k=3$ centers to simulate logical disjunctions. Whether the problem remains hard for $k=2$ is still an open question.
  • Dimension Dependency: The Euclidean lower bound depends on the dimension ($1/d^2$). The authors suggest that future work should investigate if a dimension-independent constant-factor hardness exists for Euclidean space.
  • Beyond $k$-means: The proofs are tailored to the $k$-means objective (sum of squared distances). Extending these results to $k$-median or other clustering objectives remains a promising research direction.

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},
}

Loading related content...

Figure