Search papers, labs, and topics across Lattice.
This paper establishes computational lower bounds for differentially private (DP) coreset construction for $k$-means clustering, demonstrating inherent limitations in achieving both privacy and efficiency. The authors prove that under the assumption of one-way functions, no polynomial-time $(\epsilon, 1/n^{\omega(1)})$-DP algorithm can compute a coreset for $k$-means in the $\ell_\infty$-metric with a constant approximation factor, even for $k=3$. A similar result is shown for Euclidean $k$-means, but with a weaker approximation factor of $Θ(1/d^2)$, where $d$ is the dimension.
Forget efficient, private $k$-means coresets: this work proves computational lower bounds, showing they're likely impossible to achieve under standard cryptographic assumptions.
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.
