Compressive k-Means with Differential Privacy

Proceedings of SPARS'19

Abstract: In the compressive learning framework, one harshly compresses a whole training dataset into a single vector of generalized random moments, the sketch, from which a learning task can subsequently be performed. We prove that this loss of information can be leveraged to design a differentially private mechanism, and study empirically the privacy-utility tradeoff for the k-means clustering problem.