Computational Hardness of Private Coreset

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 \hat{I}\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 $(\hat{I}\mu ,1/n^{\ddot{I}‰(1)})$-DP algorithm can compute a coreset for $k$-means in the ${\ell }_{\infty }$-metric for some constant $\hat{I}\pm >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 $\hat{I}\pm =\hat{I}˜\left(1/d^2\right)$, where $d$ is the dimension.