Differentially Private Compressive k-Means

Vincent Schellekens (1) , Antoine Chatalic (2) , Florimond Houssiau (3) , Yves-Alexandre de Montjoye (3) , Laurent Jacques (1) , Rémi Gribonval (2)

1 ICTEAM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
3 Imperial College London

This work addresses the problem of learning from large collections of data with privacy guarantees. The sketched learning framework proposes to deal with the large scale of datasets by compressing them into a single vector of generalized random moments, from which the learning task is then performed. We modify the standard sketching mechanism to provide differential privacy, using addition of Laplace noise combined with a subsampling mechanism (each moment is computed from a subset of the dataset). The data can be divided between several sensors, each applying the privacy-preserving mechanism locally, yielding a differentially-private sketch of the whole dataset when reunited. We apply this framework to the k-means clustering problem, for which a measure of utility of the mechanism in terms of a signal-to-noise ratio is provided, and discuss the obtained privacy-utility tradeoff.

Mots clés: Sketched Learning; Clustering; Differential Privacy; Sketching; Compressive Learning

Domaines: Machine Learning [stat.ML]; Apprentissage [cs.LG]; Traitement du signal et de l'image [eess.SP]; Cryptographie et sécurité [cs.CR]

Vincent Schellekens, Antoine Chatalic, Florimond Houssiau, Yves-Alexandre de Montjoye, Laurent Jacques, et al.. Differentially Private Compressive k-Means. ICASSP 2019 - IEEE International Conference on Acoustics, Speech, and Signal Processing, May 2019, Brighton, United Kingdom. pp.7933-7937, ⟨10.1109/ICASSP.2019.8682829⟩. ⟨hal-02060208⟩