Personalized Privacy Amplification via Importance Sampling
This work addresses privacy concerns for scalable machine learning practitioners, but it appears incremental as it builds on existing importance sampling and differential privacy methods.
The paper tackles the privacy properties of importance sampling in machine learning, proposing two approaches to optimize the privacy-efficiency trade-off and showing that they outperform uniform sampling in differentially private k-means across various datasets.
For scalable machine learning on large data sets, subsampling a representative subset is a common approach for efficient model training. This is often achieved through importance sampling, whereby informative data points are sampled more frequently. In this paper, we examine the privacy properties of importance sampling, focusing on an individualized privacy analysis. We find that, in importance sampling, privacy is well aligned with utility but at odds with sample size. Based on this insight, we propose two approaches for constructing sampling distributions: one that optimizes the privacy-efficiency trade-off; and one based on a utility guarantee in the form of coresets. We evaluate both approaches empirically in terms of privacy, efficiency, and accuracy on the differentially private $k$-means problem. We observe that both approaches yield similar outcomes and consistently outperform uniform sampling across a wide range of data sets. Our code is available on GitHub: https://github.com/smair/personalized-privacy-amplification-via-importance-sampling