Efficiently Computing Similarities to Private Datasets

arXiv:2403.08917v1 Announce Type: new
Abstract: Many methods in differentially private model training rely on computing the similarity between a query point (such as public or synthetic data) and private data. We abstract out this common subroutine and study the following fundamental algorithmic problem: Given a similarity function $f$ and a large high-dimensional private dataset $X \subset \mathbb{R}^d$, output a differentially private (DP) data structure which approximates $\sum_{x \in X} f(x,y)$ for any query $y$. We consider the cases where $f$ …

arxiv computing cs.cr cs.ds cs.lg data dataset datasets function high large model training point private private data problem public query similarity study synthetic synthetic data training